操作系统总结
作者：Ernest
内容较多，建议收藏，杜绝吃灰！
一、概述
1. 操作系统基本特征
-
并发：包括并发与并行 -
共享：互斥共享与同时共享 -
虚拟：时分复用、空分复用 -
异步：速度不可知
2. 操作系统基本功能
2.1. 进程管理
进程控制、进程同步、进程通信、死锁处理、处理机调度。
2.2. 内存管理
内存分配、地址映射、内存保护与共享、虚拟内存。
2.3. 文件管理
文件存储空间的管理、目录管理、文件读写管理和保护。
2.4. 设备管理
完成用户的 I/O 请求，方便用户使用各种设备，提高设备的利用率，包括缓冲管理、设备分配、设备处理、虚拟设备。
3. 系统调用
一个进程在用户态，需要使用内核态的功能，就要进行系统调用，从而陷入内核，由操作系统代为完成。
4. 大内核、微内核
4.1. 大内核
将操作系统的功能作为一个紧密结合的整体放到内核，由于各模块之间共享信息，因此有很高的性能。
4.2. 微内核
将一部分操作系统功能移出内核，划分若干服务，例如文件 I/O 模块、设备控制模块等。
只有微内核这一个模块运行在内核态，其余都在用户态。
由于需要频繁地切换状态，会有性能损失。
5. 中断分类
5.1. 外中断
由 CPU 执行指令以外的事件引起的中断，如：I/O 完成中断，表示设备输入输出处理已经完成，处理器能够发送下一个输入输出请求，还有其他比如：时钟中断、控制台中断等。
5.2. 异常
由 CPU 执行指令的内部事件引起，如非法操作吗、地址越界、算术溢出等。
5.3. 陷入
用户程序中使用系统调用，可以理解为“委托”。
6. 堆、栈，以及数据存储
6.1. 堆
堆区（heap），一般由程序员分配释放，若程序员不释放，程序结束时可能由 OS 回收。
即在 c++ 中，int* p = new int[1];就是堆区。
6.2. 栈
栈区（stack），由编译器自动分配释放，存放函数的参数值、局部变量的值等，操作方式类似于数据结构中的栈。
即在 c++ 中，int a = 1;就是栈区。
7. 分布式锁
分布式锁是控制分布式系统间同步访问共享资源的一种方式。
在分布式系统中，常需要协调他们的动作，如果不同的系统或同一系统的不同主机之间共享了一个做一组资源，那么访问这些资源的时候，往往需要互斥来防止彼此干扰来保证一致性，这种情况下就需要用到分布式锁。
二、进程管理
1. 进程与线程
1.1. 进程
进程是资源分配的基本单位，用来管理资源，例如内存、文件、网络等资源。
进程控制块（PCB）描述进程的基本信息和运行状态，所谓的创建进程和撤销进程都是指对 PCB 的操作，而 PCB 是一种描述进程的数据结构。
多个进程之间可以并发执行。
1.2. 线程
线程是独立调度的基本单位。
一个进程中可以有多个线程，它们共享进程资源。
例如微信和Chrome是两个进程，它们有各自的线程，微信有消息获取线程、消息更新线程，Chrome有http请求线程、渲染线程等，都可以并行。
1.3. 区别
- 拥有资源
进程是资源分配的基本单位，但是线程不拥有资源，它只是可以访问隶属进程的资源。
- 调度
线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程的切换，而从一个进程的线程切换到另一个进程的线程时，会引起进程切换。
- 系统开销
由于创建或撤销进程时系统要为之分配或回收资源，如存储空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。
同样，在进行进程切换时，涉及到当前进程 CPU 环境的保存以及新调度进程 CPU 环境的设置，而切换线程只需要保存和设置少量寄存器内容，开销很小。
- 通信方面
进程间通信（IPC）需要进程同步和互斥手段的辅助，以保证数据的一致性，而线程间可以通过直接读/写同一进程中的数据段（如全局变量）来进行通信。
2. 进程的状态切换（生命周期）
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7PmLwcUb-1645881523473)(C:\Users\76618\AppData\Roaming\Typora\typora-user-images\image-20220225115231679.png)]
五大状态，只有就绪态（ready）和运行态（running）可以相互转换，其他都是单向转换。
就绪态的进程通过调度算法获得 CPU 时间，转为运行态；运行态的进程在用完分配给它的 CPU 时间后转为就绪态，等待下一次调度。
阻塞态（waiting）是缺少需要的资源从而由运行态转换而来，这个资源不包括 CPU 时间，缺少 CPU 时间会转到就绪态。
进程只能自己阻塞自己，因为只有进程本身知道何时需要等待何种事件的发生来满足自己的运行需求。
3. 进程调度算法
不同环境的调度算法不同，因此需要针对不同环境来讨论调度算法。
3.1. 批处理系统
批处理系统没有太多的用户操作，所以调度算法目标是保证吞吐量和周转时间（从提交到终止的时间）。
- 先来先服务
FCFS，按照请求的顺序进行调度，有利于长作业，但不利于短作业，因为短作业需要一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成短作业等待时间过长。
- 短作业优先
SJF，按估计运行时间最短的顺序进行调度，长作业有可能饿死，处于一直等待短作业执行完毕的状态，因为只要一直有短作业进来，那么长作业永远都得不到调度。
- 最短剩余时间优先
SRTN，按估计剩余时间最短的顺序来执行调度。
3.2. 交互式系统
交互式系统中有大量的用户交互操作，所以调度算法的目标是快速响应。
- 时间片轮转
就是FCFS，然后给它们分配时间片，用完之后排到就绪进程队尾即可。
这个算法的效率主要取决于时间片的大小，因为切换进程（即切换时间片）是要有资源损耗的，如果时间片太大会导致后面的进程等待时间过长，如果时间片太小会导致切换太频繁，浪费 CPU 资源。
- 优先级调度
为每个进程分配一个优先级，按照优先级调度。
为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。
- 多级反馈队列
其实是时间片轮转调度和优先级调度的结合。
比如：一个进程需要执行100个时间片，采用时间片轮转算法的话就要交换100次，多级反馈队列则是把队列时间片分成了不同的大小，比如1,2,4,8。进程在第一个队列没执行完就会移交到下一队列，这样在很短的几个交换之内就能完成执行。
每个队列的优先权也不同，最上面的优先权最高，因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-996wBj8x-1645881523474)(C:\Users\76618\AppData\Roaming\Typora\typora-user-images\image-20220226150743149.png)]
3.3. 实时系统
实时系统要求一个请求在一个确定时间内得到响应。
分为硬实时和软实时，前者必须满足绝对的截止时间，后者可以容忍一定的超时。
4. 进程同步
4.1. 临界区
对临界资源进行访问的那段代码称为临界区。
每个进程在进入临界区之前，需要先进行检查。
4.2. 同步与互斥
同步：多个进程按一定顺序执行。
互斥：多个进程在同一时刻只有一个进程能进入临界区。
4.3. 信号量
信号量是一个整型变量，可以对其执行 down 和 up 操作，也就是常见的 P 和 V 操作。
down：如果信号量大于0，执行-1操作；如果信号量等于0，进程睡眠，等待信号量大于0（阻塞）。
up：对信号量执行+1操作，换新睡眠的进程让其完成 down 操作（唤醒）。
如果信号量的值只能为0和1，那么就成为了互斥量，0表示临界区已经加锁，1表示临界区解锁，示例如下：
typedef int semaphore;
semaphore mutex = 1;
void P(){
down(&mutex);
// 临界区
up(&mutex);
}
使用信号量实现生产者-消费者问题：
有一个注意点，不能先对缓冲区加锁再测试信号量，比如这样:
down(&mutex);
down(&empty);
如果这么做的话，会造成死锁，例如：生产者对缓冲区加锁后，测试信号量发现信号量为0，那么生产者进程就会睡眠，一直等待，而此时消费者又无法进入缓冲区（生产者已经对缓冲区加锁并且在缓冲区中等待），两者都会一直等待下去，最后造成死锁。
正确代码示例如下：
#define N 100
typedef int semaphore;
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;
void producer() {
while(TRUE) {
int item = produce_item(); // 生产一个产品
// down(&empty) 和 down(&mutex) 不能交换位置，否则会造成死锁
down(&empty); // 记录空缓冲区的数量，减少一个产品空间
down(&mutex); // 互斥锁
insert_item(item); // 将产品放入产品队列
up(&mutex); // 互斥锁
up(&full); // 记录满缓冲区的数量，增加一个产品
}
}
void consumer() {
while(TRUE) {
down(&full); // 记录满缓冲区的数量，减少一个产品
down(&mutex); // 互斥锁
int item = remove_item(); // 取出产品
up(&mutex); // 互斥锁
up(&empty); // 记录空缓冲区的数量，增加一个产品空间
consume_item(item); // 消费一个产品
}
}
4.4. 管程
管程是一种数据结构，结构内的多个子程序形成的多个工作线程互斥访问共享资源，它是为了解决临界区上的 PV 操作的配对麻烦问题，直接将配对的 PV 操作集中到一起，生成一种并发编程方法。
c 语言不支持管程，我们暂时先来演示，定义两个方法：
monitor ProducerConsumer
integer i;
condition c;
procedure insert();
begin
// ...
end;
procedure remove();
begin
// ...
end;
end monitor;
管程有一个重要的特性：同一时刻只能有一个进程使用管程，进程无法执行的时候不能一直占用管程。
它引入了条件变量以及相关的操作，wait() 和 signal() 来实现同步操作。对进程调用 wait() 会导致进程阻塞，让出管程；调用 signal() 来唤醒进程。
下面使用管程来实现生产者-消费者问题：
monitor ProducerConsumer
condition full, empty;
integer count := 0;
condition c;
procedure insert(item: integer);
begin
if count = N then wait(full);
insert_item(item);
count := count + 1;
if count = 1 then signal(empty);
end;
function remove: integer;
begin
if count = 0 then wait(empty);
remove = remove_item;
count := count - 1;
if count = N -1 then signal(full);
end;
end monitor;
// 生产者客户端
procedure producer
begin
while true do
begin
item = produce_item;
ProducerConsumer.insert(item);
end
end;
// 消费者客户端
procedure consumer
begin
while true do
begin
item = ProducerConsumer.remove;
consume_item(item);
end
end;
4.5. 经典同步问题
刚刚已经研究过生产者-消费者问题，下面来接着研究几个同步问题。
1. 读者-写者问题
允许多个进程同时读，但不允许读和写、写和写同时发生，且读者优先。
Rcount：读操作的进程数量，初始为0
CountMutex：对于 Rcount 操作进行加锁，初始为1
WriteMutex：互斥量对于写操作的加锁，初始为1
Rcount = 0;
semaphore CountMutex = 1;
semaphore WriteMutex = 1;
void writer() {
while(true) {
sem_wait(WriteMutex);
// 进行写操作
sem_post(WriteMutex);
}
}
// 读者优先策略
void reader() {
while(true) {
sem_wait(CountMutex);
if(Rcount == 0)
sem_wait(WriteMutex);
Rcount++;
sem_post(CountMutex);
// 进行读操作
sem_wait(CountMutex);
Rcount--;
if(Rcount == 0)
sem_post(WriteMutex);
sem_post(CountMutex);
}
}
2. 哲学家进餐问题
共有5个哲学家，围坐在餐桌，哲学家的生活有两种交替活动：吃饭、思考，当一个哲学家吃饭时，需要先拿起自己左右两边的两根筷子，且一次只能拿起一根筷子。
方案一：错误解法，考虑到如果所有哲学家同时拿起左手边的筷子，那么就无法拿起右手边的筷子，造成死锁。
#define N 5 // 哲学家数量
void philosopher(int i) { // 哲学家编号 0-4
while(true){
think(); // 思考
take_fork(i); // 拿左边的筷子
take_fork((i + 1) % N); // 拿右边的筷子
eat(); // 吃饭
put_fork(i); // 放下左边的筷子
put_fork((i + 1) % N); // 放下右边的筷子
}
}
方案二：对拿叉子的过程进行了改进，但还是不对，还是有可能出现方案一的问题
#define N 5 // 哲学家数量
while(true){ // 去拿两根筷子
take_fork(i); // 先拿左边的筷子
if(fork((i + 1) % N)){
// 如果右边的筷子还在
take_fork((i + 1) % N); // 拿右边的筷子
break; // 两根筷子都拿到了
}else{
// 右边的筷子不在了
put_fork(i); // 放下左边的筷子
wait_some_time(); // 等待一会儿
}
}
方案三：等待时间的时长随机变化，可以，但不好
#define N 5 // 哲学家数量
while(1){ // 去拿两根筷子
take_fork(i); // 先拿左边的筷子
if(fork((i + 1) % N)){
// 如果右边的筷子还在
take_fork((i + 1) % N); // 拿右边的筷子
break; // 两根筷子都拿到了
}else{
// 右边的筷子不在了
put_fork(i); // 放下左边的筷子
wait_random_time(); // 等待随机长的一段时间
}
}
方案四：互斥访问，很好的一个解决办法，但是一次只能有一人进餐
semaphore mutex // 互斥信号量，初值为1
void philosopher(int i){ // 哲学家编号 0-4
while(1){
think(); // 思考
P(mutex); // 进入临界区，加锁
take_fork(i); // 拿起左边的筷子
take_fork((i + 1) % N); // 拿起右边的筷子
eat(); // 吃饭
put_fork(i); // 放下左边的筷子
put_fork((i + 1) % N); // 放下右边的筷子
V(mutex); // 退出临界区，释放锁
}
}
实际上，真正合理正确的方案如下：
为了防止死锁的发生，可以设置两个条件（临界资源）：
- 必须同时拿起左右两根筷子
- 只有两个邻居都没有进餐的情况下才允许进餐
// 为了描述哲学家的状态，设定一个数据结构
#define N 5 // 哲学家数量
#define LEFT i // 左邻居
#define RIGHT (i + 1) % N // 右邻居
#define THINKING 0 // 思考中
#define HUNGRY 1 // 等待吃饭中
#define EATING 2 // 吃饭中
typedef int semaphore;
int state[N]; // 跟踪每个哲学家的状态
semaphore mutex = 1; // 临界区的互斥锁
// 一位哲学家吃饱后要唤醒邻居，存在同步关系
semaphore s[N]; // 每个哲学家的信号量
void philosopher(int i) {
while(1){
think();
take_two(i);
eat();
put_tow(i);
}
}
void take_two(int i){
P(&mutex); // 进入临界区
state[i] = HUNGRY; // 该哲学家需要吃饭
test(i); // 试图拿两根筷子
V(&mutex); // 退出临界区
P(&s[i]); // 没有筷子便阻塞
}
void put_tow(i) {
P(&mutex);
state[i] = THINKING;
test(LEFT);
test(RIGHT);
V(&mutex);
}
void test(i) { // 尝试拿起两把筷子
if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] !=EATING) {
state[i] = EATING;
V(&s[i]); // 通知第i个人可以吃饭了
}
}
4.6. 进程通信
两种通信方式：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bi2Xb096-1645881523475)(C:\Users\76618\AppData\Roaming\Typora\typora-user-images\image-20220226170918954.png)]
直接通信
发送进程把消息直接发给接收进程，并把它挂在接收进程的消息缓冲队列上，接收进程从队列中获取，Send 和 Receive 原语的使用：
Send(Receiver, message); // 发送一个 message 给 Receiver
Receive(Sender, message); // 接收来自 Sender 的一个 message
间接通信
额外拿一个实体来共享数据，发送进程存，接收进程取，一般称为“信箱”，对应计网中的电子邮件系统。
1. 管道
管道通过 pipe 函数创建，fd[0] 用于读，fd[1] 用于写。
#include <iostream>
int pipe(int fd[2]);
它只支持半双工通信，且只能在父子进程中使用。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vn6IJueA-1645881523475)(C:\Users\76618\AppData\Roaming\Typora\typora-user-images\image-20220226171600154.png)]
2. 命名管道
去除了管道只能在父子进程中使用的限制。
FIFO 常用于客户-服务器应用程序中，FIFO 作为桥梁。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-NhBJ6jdF-1645881523476)(C:\Users\76618\AppData\Roaming\Typora\typora-user-images\image-20220226171744560.png)]
3. 消息队列
间接的（内核），相比于 FIFO 有以下优点：
- 消息队列可以独立于读写进程存在，避免了 FIFO 中同步管道的打开和关闭时可能产生的困难。
- 避免了 FIFO 的同步阻塞问题，不需要进程自己提供同步方法。
- 读进程可以根据消息类型有选择性地接收消息，而不像 FIFO 那样只能被动默认地接收。
4. 信号量
它是一个计数器，给多个进程提供对共享数据对象的访问。
5. 共享内存
允许多个进程共享一块存储区，这样数据就不用来回复制，速度最快，它需要使用信号量。
6. 套接字
用于不同机器间的进程通信。
4.7. 线程间通信和进程间通信
1. 线程间通信
- synchronized 同步
- while 轮询
- ThreadA 不断地改变条件，ThreadB不停地通过 while 语句检测这个条件，实际上浪费了大量 CPU 资源，好比某个人一直盯着手机看是不是有微信消息，但实际上除了真正消息到来的那一刻，其余时间都在做无用功。
- wait/notify 机制
- 条件未满足时，ThreadA 调用 wait() 放弃 CPU，进入阻塞；
- 条件满足时，ThreadB 调用 notify() 唤醒 ThreadA。
- 管道通信
2. 进程间通信
就是 4.6. 进程通信 的内容。
4.8. 进程操作
进程基本可由三部分组成：代码段（程序），数据段（数据），堆栈段（控制块 PCB）。PCB 是进程存在的唯一标识，系统通过 PCB 的存在而感知进程的存在，通过 PCB 对进程进行管理和调度，PCB 包括进程创建、执行，退出以及改变进程的优先级等。
一般程序转换为进程要经过以下步骤：
- 内核将程序读入内存，为程序分配内存空间
- 内核为该进程分配进程标识符 PID 和其他所需资源
- 内核为进程保存 PID 及相应的状态信息，把进程放到运行队列中去执行
- 程序转化为进程之后就可以被操作系统的调度程序调度执行了
注意，子进程完全复制了父进程的地址空间的内容，包括堆栈段和数据段的内容，子进程并没有复制代码段，而是和父进程共用代码段。因为子进程可能有自己的流程，那么堆栈段和数据段是肯定会改变的，而代码段只是只读内容，不存在被修改的问题。
4.9. 孤儿进程和僵尸进程
基本概念
我们知道，在 Linux 中，正常情况下父进程创建子进程，子进程再创建新的子进程。子进程的结束和父进程的运行是一个异步过程，即父进程永远无法预测子进程到底什么时候结束，当一个进程完成他的工作终止后，它的父进程需要调用 wait() 或 waitpid() 系统调用取得子进程的终止状态。
孤儿进程：一个父进程退出，它的一个或多个子进程还在运行，那么这些子进程就成为了孤儿进程，它们将被 init 进程（进程号为1）所收养，并由 init 进程对它们完成状态收集工作。
僵尸进程：一个进程使用 fork 创建子进程，子进程退出，而父进程并没有调用 wait() 或 waitpid() 获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中，称为僵尸进程。
问题及危害
Unix 提供了一种机制可以保证只要父进程想知道子进程结束时的状态信息，就可以得到。这种机制就是：在每个进程退出的时候，内核释放该进程所有的资源，包括打开的文件，占用的内存等。但是仍然为其保留一定的信息（包括进程号 the process ID，退出状态 the termination status of the process，运行时间 the amount of CPU time taken by the process 等)。直到父进程通过 wait / waitpid 来取时才释放。但这样就导致了问题，如果进程不调用 wait / waitpid 的话， 那么保留的那段信息就不会释放，其进程号就会一直被占用，但是系统所能使用的进程号是有限的，如果大量的产生僵死进程，将因为没有可用的进程号而导致系统不能产生新的进程。此即为僵尸进程的危害，应当避免。
孤儿进程是没有父进程的进程，孤儿进程这个重任就落到了 init 进程身上，init 进程就好像是一个民政局，专门负责处理孤儿进程的善后工作。每当出现一个孤儿进程的时候，内核就把孤 儿进程的父进程设置为 init，而 init 进程会循环地 wait() 它的已经退出的子进程。这样，当一个孤儿进程凄凉地结束了其生命周期的时候，init 进程就会代表党和政府出面处理它的一切善后工作。因此孤儿进程并不会有什么危害。
任何一个子进程（init除外）在exit() 之后，并非马上就消失掉，而是留下一个称为僵尸进程 (Zombie) 的数据结构，等待父进程处理。这是每个子进程在结束时都要经过的阶段。如果子进程在exit()之后，父进程没有来得及处理，这时用 ps 命令就能看到子进程的状态是 Z。如果父进程能及时处理，可能用 ps 命令就来不及看到子进程的僵尸状态，但这并不等于子进程不经过僵尸状态。如果父进程在子进程结束之前退出，则子进程将由 init 接管。 init 将会以父进程的身份对僵尸状态的子进程进行处理。
僵尸进程危害场景：
例如有个进程，它定期的产生一个子进程，这个子进程需要做的事情很少，做完它该做的事情之后就退出了，因此这个子进程的生命周期很短，但是，父进程只管生成新的子进程，至于子进程退出之后的事情，则一概不闻不问，这样，系统运行上一段时间之后，系统中就会存在很多的僵死进程，倘若用 ps 命令查看的话，就会看到很多状态为 Z 的进程。 严格地来说，僵死进程并不是问题的根源，罪魁祸首是产生出大量僵死进程的那个父进程。因此，当我们寻求如何消灭系统中大量的僵死进程时，答案就是把产生大 量僵死进程的那个元凶枪毙掉（也就是通过 kill 发送 SIGTERM 或者 SIGKILL 信号啦）。枪毙了元凶进程之后，它产生的僵死进程就变成了孤儿进程，这些孤儿进程会被 init 进程接管，init 进程会 wait() 这些孤儿进程，释放它们占用的系统进程表中的资源，这样，这些已经僵死的孤儿进程就能瞑目而去了。
僵尸进程解决办法
- 通过信号机制：子进程退出时向父进程发送 SIGCHILD 信号，父进程处理 SIGCHILD 信号，在信号处理函数中调用 wait() 进行处理僵尸进程。
- fork 两次：将子进程称为孤儿进程，从而其父进程变为 init 进程，然后就可以通过 init 进程去处理僵尸进程。
4.10. 守护进程
Linux Daemon（守护进程）是运行在后台的一种特殊进程。它独立于控制终端并且周期性地执行某种任务或等待处理某些发生的事件。它不需要用户输入就能运行而且提供某种服务，不是对整个系统就是对某个用户程序提供服务。Linux系统的大多数服务器就是通过守护进程实现的。常见的守护进程包括系统日志进程syslogd、 web服务器httpd、邮件服务器sendmail和数据库服务器mysqld等。
守护进程一般在系统启动时开始运行，除非强行终止，否则直到系统关机都保持运行。守护进程经常以超级用户（root）权限运行，因为它们要使用特殊的端口（1-1024）或访问某些特殊的资源。
一个守护进程的父进程是init进程，因为它真正的父进程在fork出子进程后就先于子进程exit退出了，所以它是一个由init继承的孤儿进程。守护进程是非交互式程序，没有控制终端，所以任何输出，无论是向标准输出设备stdout还是标准出错设备stderr的输出都需要特殊处理。
守护进程的名称通常以d结尾，比如sshd、xinetd、crond等
编写守护进程的一般步骤步骤：
- 在父进程中执行 fork 并 exit 推出；
- 在子进程中调用 setsid 函数创建新的会话；
- 在子进程中调用 chdir 函数，让根目录
/ 成为子进程的工作目录； - 在子进程中调用umask函数，设置进程的umask 为 0；
- 在子进程中关闭任何不需要的文件描述符
4.11. 上下文切换
就是进程切换或者任务切换，CPU 从一个进程或线程切换到另一个进程或线程。
三、死锁
资源分类：可重用资源、消耗资源。
1. 什么是死锁
造成死锁的原因就是多个线程或进程对同一个资源的争抢或相互依赖，一个最简单的解释就是你去面试，面试官说告诉我什么是死锁，我就录用你，你回答面试官你录用我，我告诉你。
**死锁的概念：**一个进程集合中的每个进程都在等待只能由这个集合中的任意其他一个进程才能引发的时间，这种情况就是死锁。
关于进程所需要的资源，可以分为软资源（代码块）和硬资源（硬件设备如打印机）。资源一般可以分为两种：可剥夺资源和不可剥夺资源，一般来说由可剥夺资源引起的死锁可以由系统的重新分配资源来解决，所以一般大多数的死锁都是由不可剥夺资源引起的。
2. 死锁的必要条件
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AhYHQRhg-1645881523476)(C:\Users\76618\AppData\Roaming\Typora\typora-user-images\image-20220226191757260.png)]
- 互斥：每个资源要么都已经分配给了一个进程，要么就是可用的，没有第三种情况
- 占有和等待：已经得到了某个资源的进程可以再请求新的资源，在这个过程中可以占有现有资源
- 不可抢占：已经分配给一个进程的资源不能强制性地被抢占，它只能占有它的进程显式地释放的资源
- 循环等待：有两个或者两个以上的进程组成一条环路，环路中每个进程都在等待下一个进程所占有的资源
3. 死锁的处理办法
3.1. 处理死锁的策略
- 鸵鸟策略
- 把头埋在沙子里，装作什么都没发生
- 因为解决死锁的代价很大，所以鸵鸟策略相比之下会获得更高的性能，当发生死锁时不会对用户造成多大影响，或发生死锁的概率极低，可以采用这个策略
- 大多数操作系统，包括 Unix、Linux 和 Windows，处理死锁问题的办法就是忽略它
- 检测死锁并且恢复
- 仔细对资源进行动态分配，避免死锁
- 破除死锁产生的必要条件，防止死锁发生
3.2. 死锁检测与死锁恢复
不试图阻止死锁，而是当检测到死锁发生时，采取措施进行恢复。
-
每种类型一个资源的死锁检测 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Np2fc7Od-1645881523477)(C:\Users\76618\AppData\Roaming\Typora\typora-user-images\image-20220226201642134.png)] 这个算法就是检测进程-资源有向图中是否有环的存在，深搜，如果存在有向环，那么说明存在死锁。 -
每种类型多个资源的死锁检测 即优先让能满足其资源需求的进程执行。 -
死锁恢复
3.3. 死锁预防
在程序运行之前预防发生死锁，确保系统永远不会进入死锁状态。
1. 破坏互斥条件
把互斥的封装成可以同时访问的，比如原来打印机一次只能满足一个进程的使用，但是在打印机的上层加一层打印机缓存之后，就可以让进程单独共享缓存就可以，避免了互斥的情况发生。
2. 破坏占有和等待条件
规定所有进程在执行前必须请求其所需要的所有资源，这个策略也有很明显的缺点：
- 许多情况下进程的执行是动态的，无法完美预测
- 资源利用率低，但是占用率高，浪费 CPU 资源
- 降低了进程的并发性，资源本身是有限的
3. 破坏不可抢占条件
允许进程强行从占有者那里夺取某些资源，就是说当一个进程已经占有某些资源，同时申请新的资源而无法立即满足时，必须释放所有现有资源，重新申请。这样的方法实现起来很困难，会降低系统性能。
4. 破坏循环等待
实行资源有序分配策略，把资源实现分类编号，按号分配，使得进程在申请、占用资源时不会形成环路，所有进程对资源的请求必须按照资源序号的递增顺序提出，只有占用了小号资源，才能申请大号资源，这样就不会产生回路，从而预防了死锁，这种策略与前面的策略相比资源的利用率和系统的吞吐量都有很大提高，但是也存在一些缺点：
- 限制了进程对资源的请求，同时给系统中所有资源合理编号也是件困难事，增加了系统开销
- 为了遵循按号申请的次序，暂不使用的资源也需要提前申请，从而增加了进程对资源的占用时间
3.4. 死锁避免
1. 安全状态
如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够是的每一个进程运行完毕，则称该状态时安全的。
安全状态必须要求不能发生死锁。
2. 单个资源的银行家算法
判断对请求的满足是否会进入不安全状态，如果是，就拒绝请求，否则予以分配，例如下图中，图 c 就是不安全状态：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BPxvl2xD-1645881523478)(C:\Users\76618\AppData\Roaming\Typora\typora-user-images\image-20220226203147433.png)]
3. 多个资源的银行家算法
类似于单个资源的银行家算法。
4. 如何在写程序的时候就避免死锁
网易有道面经
所谓死锁，发生的主要原因就在于有多个进程去竞争资源，也就是同时去抢占，只需要自己写一个支持多线程的消息管理类，单开一个线程访问独占资源，其他线程用消息交互实现间接访问，这种机制适应性强、效率高，更适合多核环境。
四、内存管理
1. 虚拟内存
**虚拟内存的目的：**让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。
为了更好的管理内存，操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。当程序引用到一部分不在物理内存中的地址空间时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败的指令。
2. 分页系统地址映射
- 内存管理单元（MMU）：管理着地址空间和物理内存的转换。
- 页表（Page Table）：页（地址空间）和页框（物理内存空间）的映射表。
3. 页面置换算法
在程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中，此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。
页面置换算法和缓存淘汰策略类似，可以将内存看成磁盘的缓存，在缓存系统中，缓存的大小有限，当有新的缓存到达时，需要淘汰一部分已经存在的缓存，这样才有空间存放新的缓存数据。
页面置换算法的主要目标是使页面置换频率最低（也可以说是缺页率最低）。
3.1. 最佳
所选择的被换出的页面将是最长时间内不再被访问，通常可以保证获得最低的缺页率。
这是一种理论上的算法，不可能实现，因为你永远无法知道一个页面将多长时间不被访问。
3.2. 最近最久未使用
LRU，Least Recently Used
虽然无法知道将来要使用的页面情况，但是可以知道过去已经使用的页面情况，LRU 将最近最久未使用的页面换出。
需要在内存中维护一个所有页面的链表，当一个页面被访问是，将这个页面移到链表表头，这样就能保证链表表尾的页面是最近最久未使用的。
每次访问页面都要更新链表，这种方法本身的代价就很高。
3.3. 最近未使用
NRU， Not Recently Used
每一个页面都有两个状态位，当页面被访问时设置页面的 R = 1，当页面被修改时试着页面的 M = 1，其中 R 位会被定时清零，可以将页面分为以下四类：
- R = 0, M = 0
- R = 0, M = 1
- R = 1, M = 0
- R = 1, M = 1
当发生缺页中断时，NRU算法随机地从类编号最小的非空类中挑选一个页面换出。
NRU 优先换出被修改过的脏页面（R = 0，M = 1），而不是被频繁使用的干净页面（R = 1，M = 0）。
3.4. 先进先出
FIFO，First In First Out
就是字面意思，会将经常使用的页面换出，提高了缺页率。
3.5. 第二次机会算法
就是给 FIFO 策略中的老页面第二次机会。
当页面被访问 (读或写) 时设置该页面的 R 位为 1。需要替换的时候，检查最老页面的 R 位。如果 R 位是 0，那么这个页面既老又没有被使用，可以立刻置换掉；如果是 1，就将 R 位清 0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续从链表的头部开始搜索。
3.6. 时钟
第二次机会算法需要在链表中移动页面，降低了效率，时钟算法使用环形链表将页面链接起来，使用一个指针指向最老的页面。
4. 分段
把表分成段，一个段构成一个独立的地址空间，段的长度不固定，可以动态增长。
5. 段页式
段中放页，页大小固定，段动态增长。
6. 分页与分段的比较
- 对程序员的透明性：分页透明，分段需要程序员显式划分每个段
- 地址空间的维度：分页是一维地址空间，分段是二维的
- 大小是否可变：分页不可变，分段可变
- 出现的原因：分页是实现虚拟内存，从而获得更大的地址空间；分段是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护
五、设备管理
1. 磁盘调度算法
读写一个磁盘块的时间的影响因素：
其中寻道时间最长，所以底盘调度的主要目标是降低寻道时间。
1.1. 先来先服务
- 按照磁盘请求的顺序进行调度
- 公平对待所有进程
- 在有很多进程的情况下，接近随机调度的性能
- 优点是公平简单，缺点是平均寻道时间很长
1.2. 最短寻道时间优先
优先调度与当前磁头所在磁道距离最近的磁道。
虽然平均寻道时间比较低，但是不够公平。如果新到达的磁道请求总是比一个在等待的磁道请求近，那么在等待的磁道请求会一直等待下去，也就是出现饥饿现象。具体来说，两边的磁道请求更容易出现饥饿现象。
1.3. 电梯算法
电梯总是保持一个方向运行，直到该方向没有请求为止，然后改变运行方向。
电梯算法（扫描算法）和电梯的运行过程类似，总是按一个方向来进行磁盘调度，直到该方向上没有未完成的磁盘请求，然后改变方向。
因为考虑了移动方向，因此所有的磁盘请求都会被满足，解决了 SSTF 的饥饿问题。
六、链接
1. 编译系统
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-WTSYZfic-1645881523478)(C:\Users\76618\AppData\Roaming\Typora\typora-user-images\image-20220226210226917.png)]
1.1. 预处理阶段（Preprocessing phase）
预处理（cpp）根据以字符 # 开头的命令，修改原始的 c 程序，生成扩展名为 .i 的文件。
gcc -E hello.c -o hello.i
1.2. 编译阶段（Compilation phase）
编译器（cc1）将文本文件 hello.i 翻译成文本文件 hello.s，它包含一个汇编语言程序。
gcc -S hello.i -o hello.s
1.3. 汇编阶段（Assembly phase）
编译器（as）将 hello.s 翻译成机器语言指令，打包成一种叫做可重定位目标程序的格式，并将结果保存在目标文件 hello.o 中。
as hello.s -o hello.o
1.4. 链接阶段（Linking phase）
printf 函数是标准 C 库中的一个函数，在 printf.o 这个单独预编译好的目标文件中。连接器（ld）将 printf.o 和 hello.o 合并，结果得到 hello 可执行目标文件。
gcc hello.o -o hello
2. 静态链接
静态链接以一组可重定向目标文件为输入，生成一个完全链接的可执行目标文件作为输出，链接器主要完成以下两个任务：
- 符号解析：每个符号对应于一个函数、一个全局变量、一个静态变量，符号解析的目的是将每个符号引用与一个符号定义关联起来
- 重定位：链接器通过把每个符号定义与一个内存位置关联起来，然后修改所有对这些符号的引用，使它们指向这个内存位置
3. 目标文件
- 可执行目标文件：可以直接在内存中执行
- 可重定向目标文件：可与其他可重定向目标文件在链接阶段合并，创建一个可执行目标文件
- 共享目标文件：一种特殊的可重定向目标文件，可以在运行时被动态加载进内存并链接
4. 动态链接
静态库有以下两个问题：
- 当静态库更新时整个程序都要重新链接
- 对于 printf 这种标准函数库，如果每个程序都要有代码，会极大浪费资源
共享库是为了解决静态库的这两个问题而设计的，在Linux系统中通常用 .so 后缀来表示，Windows 系统上被称为 DLL，具有以下特点：
- 在给定的文件系统中一个库只有一个文件，所有引用该库的可执行目标文件都共享这个文件，不会被复制到引用它的可执行文件中
- 在内存中，一个共享库的 .text 节（已编译程序的机器代码）的一个副本可以被不同的正在运行的进程共享
|