操作系统部分_如果一个计算机的硬盘为 64g,每个块的大小为 4k,如果用位示图来管理硬盘的空间,则

linux下编译程序

参考1、参考2

gcc和g++并不是编译器，也不是编译器的集合，它们只是一种驱动器，根据参数中要编译的文件的类型，调用对应的GUN编译器而已；

• 编译单个源文件
  g++ hello.cpp -o hello
  当你的程序只有一个源文件时，直接就可以用gcc/g++命令编译它。但是当你的程序包含很多个源文件时，用gcc/g++命令逐个去编译时，工作量大，所以出现了make工具;
• make
  make是一个自动化编译工具，可以使用一条命令实现完全编译。但是需要编写一个规则文件makefile，make依据makefile文件中用户指定的命令来进行编译和链接的。
• cmake
  当工程非常大的时候，手写makefile也是非常麻烦的，如果换了个平台makefile又要重新修改。这时候就出现了Cmake这个工具。CMake是一种跨平台编译工具，比make更为高级，使用起来要方便得多。CMake主要是编写CMakeLists.txt文件，然后用cmake命令将CMakeLists.txt文件转化为make所需要的makefile文件，最后用make命令编译源码生成可执行程序或共享库。

原文件－－camkelist —cmake —makefile —make —生成可执行文件

操作系统的特征点

• 操作系统是什么 参考
  其本质上就是一段计算机程序，用于管理计算机的硬件和软件资源，操作系统需要处理很多事务，如管理与配置内存、决定系统资源的优先次序、控制I/O设备等。
  

• 操作系统的特点
  并发性：是指两个或者多个事件在同一时间的间隔内发生
  共享性：系统中的资源可供多个并发执行的进程使用。（互斥共享，同时共享）
  虚拟性：
  虚拟是指通过某种技术把一个物理上的实体变为若干个逻辑上的对应物。物理实体是实际存在的实体，而逻辑上的对应物则是虚的，是用户感觉上存在的“实体”，用于实现虚拟的技术，称为虚拟技术。操作系统中利用了多种虚拟技术，如虚拟处理器，虚拟内存，虚拟外部设备等。

  (1)虚拟处理器技术中，是通过多道程序设计技术，让多道程序并发执行的方法来分时使用一个处理器的。利用多道程序设计技术把一个物理上的CPU虚拟为多个逻辑上的CPU，称为虚拟处理器。一个处理器同时为多个用户服务，使每个终端用户都认为是有一个CPU在专门为他服务。

  (2)虚拟存储技术中，将一台机器的物理存储器变为虚拟存储器，以便从逻辑上扩充存储器的容量。此时用户所感觉的内存容量是虚的。我们把用户所感觉到的存储器称为虚拟存储器。

  (3)虚拟设备技术，将一台物理I/O设备虚拟为多台逻辑上的I/O设备，这样便可以使原来仅允许在一段时间内由一个用户访问的设备变为一段时间内允许多个用户同时访问的共享设备。

• 不确定性

进程和线程

定义

• 进程：是指在系统中正在运行的一个应用程序，程序一旦运行就是进程；

  进程是系统进行资源分配的最小单位，且每个进程拥有独立的地址空间；一个进程无法直接访问另一个进程的变量和数据结构，如果希望一个进程去访问另一个进程的资源，需要使用进程间的通信，比如：管道、消息队列等

• 线程：是进程的一个实体，是进程的一条执行路径；比进程更小的独立运行的基本单位，线程也被称为轻量级进程，

• 一个程序至少有一个进程，一个进程至少有一个线程；

区别

• 进程是资源分配的最小单位，线程是CPU调度的最小单位；
• 同一进程的线程共享本进程的地址空间和资源，而进程之间则是独立的地址空间和资源；
• 一个进程崩溃后，在保护模式下不会对其他进程产生影响，但是一个线程崩溃整个进程崩溃，所以多进程比多线程健壮；
• 进程创建|切换|销毁的开销也远大于线程（所以引入线程实现并发）；
• 进程编程调试简单可靠性高（进程间独立，同步互斥少），线程相对复杂。
• 两者均可并发执行；
• 线程创建出来的线程是平等的没有上下级，进程创建出来的进程为子进程。

进程/线程的生命周期中有哪些状态

• 新建态：刚刚创建的进程，操作系统还没有把它加入到可执行进程组中，通常是进程控制块已经创建但是还没有加载到内存中的进程。
• 就绪态：进程做好了执行准备，等待分配处理机。
• 执行态：该进程正在执行；
• 阻塞态：进程在某些事件发生前不能执行，等待阻塞进程的事件完成。，如等待 I/O 完成；
• 终止状态：操作系统从可执行进程组中释放出的进程，或由于自身或某种原因停止运行。
  状态转换

进程互斥、同步、通信的关系

在多道程序设计系统中，进程之间存在两种基本的关系，竞争和协作。

进程互斥、同步、通信都是基于这两种基本关系存在的。为了解决进程间的竞争关系引入了进程互斥。为了解决进程间松散的协作关系，引入了进程同步。为了解决进程间紧密的协作关系引入了进程通信。

进程同步是指两个以上进程基于某个条件来协调它们的活动（不协调的话，多个进程同时对共享资源读写，会造成冲突，数据一致性问题），一个进程的执行依赖于另一个协作进程的消息或信号，当一个进程没有得到另一个进程的消息或者信号时需要等待，直到消息或信号到达才被唤醒。 进程同步可以使进程间相互协调和协同工作。但是只传递信号，没有传递数据的能力。

很多情况下,进程间需要交换大批数据，例如传送一批信息或整个文件，这个时候需要进程通信来完成。进程通信可以在协作进程间进行大量的数据交换。
看他看他

进程间通信方式

每个进程各自有不同的用户地址空间,任何一个进程的全局变量在另一个进程中都看不到，所以进程之间要交换数据必须通过内核,在内核中开辟一块缓冲区,进程A把数据从用户空间拷到内核缓冲区,进程B再从内核缓冲区把数据读走,内核提供的这种机制称为进程间通信。

进程间通信方式有管道、信号量、消息队列、共享内存、套接字五种。

（1）管道分为有名管道和无名管道，

• 无名管道是一种半双工的通信方式，数据只能单向流动（具有固定的读端和写段），而且只能在具有亲缘关系的进程间使用。速度慢，容量有限，只有父子进程能通讯.
• 有名管道（FIFO）也是一种半双工的通信方式，但它允许无亲缘关系进程间的通信。 任何进程间都能通讯，但速度慢

（2）信号量是一个计数器，可以用来控制多个进程对共享资源的访问.

• 信号量用于进程间同步，若要在进程间传递数据需要结合共享内存。

• 信号量基于操作系统的 PV 操作，程序对信号量的操作都是原子操作。

• 每次对信号量的 PV 操作不仅限于对信号量值加 1 或减 1，而且可以加减任意正整数。

• 支持信号量组。

  他常作为一种锁机制。因此，主要作为进程间以及同一个进程内不同线程之间的同步手段。

（3）消息队列是消息的链表，存放在内核中并由消息队列标识符标识（一个消息队列一个标识符），

• 消息队列是面向记录的，其中的消息具有特定的格式以及特定的优先级；

• 消息队列独立于发送与接收进程。进程终止时，消息队列及其内容并不会被删除；

• 消息队列可以实现消息的随机查询，消息不一定以先进先出的次序读取，也可以按消息的类型读取。

  容量受到系统限制，且要注意第一次读的时候，要考虑上一次没有读完数据的问题

（4）共享内存

• 映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。
• 共享内存是 最快的IPC方式，它是针对其他进程间通信方式运行效率低而专门设计的。他往往与其他通信机制，如信号量配合使用，来实现进程间的同步和通信。

（5）套接字：与其他通信机制不同的是，它可用于不同机器间的进程通信。

进程调度算法

先来先服务调度算法、短作业优先调度算法、非抢占式优先级调度算法、抢占式优先级调度算法、高响应比优先调度算法、时间片轮转法调度算法；

僵尸进程和孤儿进程

有代码

sleep和wait的区别

sleep() 方法是线程类（Thread）的静态方法，
wait()是Object类的方法
调用了sleep() 方法，线程进入睡眠状态，让出执行机会给其他线程，等到休眠时间结束后，线程进入就绪状态和其他线程一起竞争cpu的执行时间。

2因为sleep() 是static静态的方法，他不能改变对象的机锁，当一个synchronized块中调用了sleep() 方法，线程虽然进入休眠，但是对象的机锁没有被释放，其他线程依然无法访问这个对象。

wait()是Object类的方法，当一个线程执行到wait方法时，它就进入到一个和该对象相关的等待池，同时释放对象的机锁，使得其他线程能够访问，可以通过notify，notifyAll方法来唤醒等待的线程

sleep() 和 wait() 的区别就是 调用sleep方法的线程不会释放对象锁，而调用wait() 方法会释放对象锁.

为什么使用多线程

进程的目的之一是为了提供并发能力，但是进程的创建需要新分配地址空间、物理内存等等，进程创建切换消耗的资源大，因此引入轻量级的并发实体——线程，共享进程资源。

一切为了并发，哦耶

两种线程模型
（1） 用户级线程 ULT：
用户程序实现，不依赖于操作系统核心，应用提供创建、同步、调度和管理线程的函数来控制用户线程。不需要用户态/内核态切换，速度快。内核对ULT无感知，线程由app管理

（2） 内核线程KLT：
系统内核管理线程，内核保存线程的状态和上下文信息。

Java线程创建室依赖于系统内核，通过JVM调用系统库创建内核线程，内核线程与java-Thread是1：1的。

为什么需要线程池

为了避免频繁的线程创建切换销毁，而消耗过多的资源，引入线程池，实现线程重用，节约资源。

例如：服务器需要处理10万个客户端发来的数据，如果为每一个用户创建一个线程来处理用户数据，需要10万个线程，创建线程和线程切换会消耗大量的时间和资源，显然很不合理。

线程池就是一个线程缓存，负责对线程进行统一分配、调度与监控。

什么时候使用线程池？

• 单个任务处理时间比较短
• 需要处理的任务数量很大

死锁

死锁: 是指多个进程在运行过程中因为争夺资源而造成的的一种僵局，造成他们都无法向前推进。

线程死锁是指多线程在运行的过程中，因为竞争资源造成的一种僵局，线程互相持有对方所需要的资源，在该线程释放这个锁之前，其它线程是获取不到这个锁的，而且会一直死等下去，因此这便造成了死锁。

产生死锁的原因：竞争资源，进程间推进顺序非法
（1）必要条件

• 互斥条件 一段时间内某资源被一个进程占用，此时其他请求者只能等待

• 请求和保持条件 进程已经保持了至少一个资源，但又提出新的资源请求，而请求的资源被其他进程占有，此时请求进程阻塞，又不会释放自己已经占用的资源

• 不可剥夺条件 进程已获得的资源，在未使用完之前，不能被剥夺，只能由自己释放

• 环路等待条件 请求资源的进程形成资源环形链.

（2）解决办法

• 预防死锁

  1）破坏互斥条件。即允许进程同时访问某些资源。但是，有的资源是不允许被同时访
  问的，像打印机等等，这是由资源本身的属性所决定的。所以，这种办法并无实用价值。
  2）破坏请求和保持条件 实行资源预先分配策略，进程在运行前一次性地向系统申请它所需要的全部资源，只要有一个资源得不到分配，不给这个进程分配其他的资源。
  3）破坏不可剥夺资源：即当某进程获得了部分资源，但得不到其它资源，则释放已占有的资源。
  4）破坏环路等待条件 实行资源有序分配法，系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反。这样就不会出现环路。

• 避免死锁

  1）加锁顺序（线程按照一定的顺序加锁）
  2）加锁时限（线程尝试获取锁的时候加上一定的时限，超过时限则放弃对该锁的请求，并释放自己占有的锁）
  在尝试获取锁的过程中若超过了这个时限该线程则放弃对该锁请求。若一个线程没有在给定的时限内成功获得所有需要的锁，则会进行回退并释放所有已经获得的锁，然后等待一段随机的时间再重试。
  3）死锁检测
  1
  2
  3
  4

• 检测死锁

• 解除死锁

多线程打印ABC

#include<iostream>
#include<thread>
#include<mutex>
using namespace std;

int state = 1; //各个线程根据state的值判断是否打印
std::mutex mtx;

void funA() { //线程thA的入口函数，负责打印A
	int i = 0;
	while (i < 10) {
		mtx.lock(); //尝试对互斥量加锁，不成功则阻塞，
		if (state == 1) {  
			i++;
			state = 2;
			cout << std::this_thread::get_id() <<": A"<< endl;
		}
		mtx.unlock();
		std::this_thread::sleep_for(std::chrono::milliseconds(100));
	}
}

void funB() { //线程thB的入口函数，负责打印B
	int i = 0;
	while (i < 10) {
		mtx.lock();
		if (state == 2) {
			i++;
			state = 3;
			cout << std::this_thread::get_id() << ": B" << endl;
		}
		mtx.unlock();
		std::this_thread::sleep_for(std::chrono::milliseconds(100));
	}
}

void funC() { //线程thC的入口函数，负责打印C
	int i = 0;
	while (i < 10) {
		mtx.lock();
		if (state == 3) {
			i++;
			state = 1;
			cout << std::this_thread::get_id() << ": C" << endl;
		}
		mtx.unlock();
		std::this_thread::sleep_for(std::chrono::milliseconds(100));
	}
}
int main() {  //一个进程至少一个线程：主线程，用来执行main函数
	
	//多线程打印ABC
	std::thread thA(funA);
	std::thread thB(funB);
	std::thread thC(funC);

	thA.join();  //主线程等待子线程执行完毕
	thB.join();
	thC.join();

	cout << std::this_thread::get_id()<<" main thread...." << endl;
	system("pause");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

同步、通知

#include<iostream>
#include<thread>
#include<mutex>
using namespace std;

int state = 1; //各个线程根据state的值判断是否打印
std::mutex mtx;
std::condition_variable cv;

bool cheackstate1() {
	return state == 1;
}
void funA() { //线程thA的入口函数，负责打印A
	int i = 0;
	while (i < 10) {
		std::unique_lock<std::mutex> lk(mtx); //尝试对互斥量加锁，不成功则阻塞，
		cv.wait(lk, cheackstate1); //cheackstate1函数返回true则继续往下执行，否则释放锁，阻塞。
		//当本线程阻塞在wait语句时，其他线程notify，wait被唤醒，然后不断尝试对互斥量加锁，加锁成功后，判断cheackstate1
		i++;
		state = 2;
		cout << std::this_thread::get_id() << ": A" << endl;
		//std::chrono::milliseconds dura(1000);
		//std::this_thread::sleep_for(dura);
		cv.notify_all();
	}
}

void funB() { //线程thB的入口函数，负责打印B
	int i = 0;
	while (i < 10) {
		std::unique_lock<std::mutex> lk(mtx); //尝试对互斥量加锁，不成功则阻塞，
		while (state != 2)
			cv.wait(lk);   //wait没有第二个参数，无条件释放锁，阻塞
		i++;
		state = 3;
		cout << std::this_thread::get_id() << ": B" << endl;
		//std::chrono::milliseconds dura(1000);
		//std::this_thread::sleep_for(dura);
		cv.notify_all();
	}
}
bool cheackstate3() {
	return state == 3;
}
void funC() { //线程thC的入口函数，负责打印C
	int i = 0;
	while (i < 10) {
		std::unique_lock<std::mutex> lk(mtx); //尝试对互斥量加锁，不成功则阻塞，
		cv.wait(lk, cheackstate3);
		i++;
		state = 1;
		cout << std::this_thread::get_id() << ": C" << endl;
		//std::chrono::milliseconds dura(1000);
		//std::this_thread::sleep_for(dura);
		cv.notify_all();
	}
}
int main() {  //一个进程至少一个线程：主线程，用来执行main函数
	
	//多线程打印ABC
	std::thread thA(funA);
	std::thread thB(funB);
	std::thread thC(funC);

	thA.join();  //主线程等待子线程执行完毕
	thB.join();
	thC.join();

	cout << std::this_thread::get_id()<<" main thread...." << endl;
	system("pause");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

虚拟内存

参考
虚拟内存是一种内存管理技术，它会使程序认为自己拥有一块很大且连续的内存，也就是虚拟内存，由操作系统完成从虚拟内存的虚拟地址到真实内存的真实地址之间的映射工作。然而，这个程序在内存中是不连续的，并且有些还会在磁盘上，在需要时进行数据交换。

• 优点
  可以弥补物理内存大小的不足，一定程度的提高反应速度；减少对物理内存的读取从而保护内存延长内存使用寿命。

• 缺点
  占用一定的物理硬盘空间；加大了对硬盘的读写；设置不得当会影响整机的稳定性与速度。

• 调度方式
  页式调度
  段式调度
  段页式调度

3内存分配分类

连续型分配方式：

（1）单一连续分配

（2）固定分区

• 最早使用的一种可以运行多道程序的存储管理方式。要求把作业全部装入内存，且装入一个连续的存储空间。
• 一个作业只能装入一个分区，既浪费又限制了并发执行的作业数目；

（3）可变分区

• 根据用户作业的大小，在作业要求装入主存时，动态分区，分区大小等于作业大小。提高了内存的使用效率，但是会造成大量的内存碎片。
• 常见的分区分配算法：首次适应算法FF、最佳适应算法BF、最差适应算法WF

非连续型分配方式：

（4）页式存储管理

• 将用户作业分页，相应的内存空间也分成与页大小相同的存储块，成为物理块，以块为单位将作业中的若干页分别装入到多个不相邻的块中。作业执行时根据逻辑地址中的页号找到它所在的块号，再确定当前指令要访问的物理地址。

• 特点：有效解决了碎片多的问题；位示图和页表可能因为内存很大和作业很大导致占用较大存储空间；需要硬件支撑，增加系统成本和开销，例如地址转换机构；要求页的大小固定，不能随程序大小而改变。

  a. 内存空间的分配与回收

  内存分配表（存放作业对应的页表位置）、位示图（那些块使用，哪些没适用）、页表（页号对应的块号）

  64G硬盘，每块大小4K，如果用位示图来管理硬盘空间，则位示图的大小为（2M）字节。

  b. 分页过程

  当需要为用户作业分配内存时，首先计算该作业的页数，然后查看位示图中是否有足够的空闲页数，如果没有，显示内存不足，删除该作业或入作业队尾。如果有，为该作业创建页表，根据位示图将每一页装入块中，修改位示图中的标记，并在页表中记录页号对应的块号。最后在内存分配表中记录该作业对应的页表位置。
  

  c. 地址转换

  页号 = 逻辑地址/页号
  页内地址 = 逻辑地址%页长

  程序的逻辑地址由页号和页内地址组成。
  物理地址 = 块号*块大小+块内地址+用户区基址

  d. 页式虚拟存储

  将作业的部分页装入主存，在作业让运行时再装入所需要的页，因此需要请求调页功能和页面置换功能。

  页面置换算法：
  1）FIFO先进先出
  2）LRU最近最久未使用
  3）LFU最近最不经常使用算法：访问次数最少的页被置换
  4）理想页面置换算法：移除最长时间不需要访问的页
  5）NRU最近未使用页面置换算法
  6）第二次机会页面置换算法：FIFO的改进
  7）时钟页面置换算法

  缺页中断 = 中断次数/页面访问总次数

（5）段式存储管理

• 对一个作业按照逻辑分段，然后这几个段离散地存储到内存空间上，段内部是连续存储。
  

（6）段页式存储管理

• 页式存储内存碎片少，内存块可以不连续，灵活，但是破坏了程序的逻辑性。段式存储将程序按逻辑分段，但是段内地址必须连续，当段很大时，可能没有那么大的连续空间。
• 段页式存储结合了两者的优点。把用户程序先分段再分页，把内存分成与页大小相同的块。每段分配与其页数相同的内存块，内存块可以连续，也可以不连续。