本文章是关于计算机操作系统的学习笔记，笔记主要来自王道的操作系统课程，总共有五个章节：

• 第一章：计算机操作系统（壹）
• 第二章：计算机操作系统（贰）
• 第三章：计算机操作系统（叁）
• 第四章：计算机操作系统（肆）
• 第五章：计算机操作系统（伍）

进程

一、进程的基本概念

1、程序与进程

程序是静态的，代表可执行文件，是一系列指令的集合

进程是动态的，是程序的一次执行过程

比如一个QQ程序，打开3次就产生了3个QQ进程

2、PCB

每个进程创建时，都会分配一个唯一的、不重复的ID，即PID

进程运行时，操作系统要记录PID，进程分配的资源、进程运行情况等等，这些信息被保存在进程控制块的数据结构中，即PCB。

凡是管理进程需要的信息，都会放在PCB中

3、进程的组成

PCB、程序段、数据段

4、进程的组织

链接方式：指针指向不同的队列（就绪队列、阻塞队列等）

索引方式：索引表

5、进程的特征

动态性、并发性、独立性、异步性、结构性

6、进程的切换与过程

狭义的进程调度：指从就绪队列中选一个要运行的进程

进程切换：选择进程时，若选择的不是刚刚被暂停执行的进程，就是进程切换

广义的进程调度：包含选择进程和进程切换两个步骤

二、进程的状态与转换

1、进程状态的转换

创建态、就绪态、运行态、阻塞态、终止态

它们之间的转换图如下：

2、进程的状态

在进程PCB中，会有一个变量state表示进程当前的状态

运行态：占有CPU，并在CPU上运行、单核只能运行一个进程（双核两个）（CPU√，其他资源√）

就绪态：已具备运行条件，但没有空闲的CPU，暂时不能运行（CPU×，其他资源√）

阻塞态：等待某个事件发生，暂时不能执行（CPU×，其他资源×）

创建态：创建PCB、程序段、数据段

终止态：回收内存、程序段、数据段，撤销PCB

三、进程控制

1、进程控制的概念

（1）什么是进程控制：

实现各种进程状态之间的转换

（2）如何实现进程控制：

使用“原语”实现

（3）如何实现“原语”的原子性：

使用“关中断指令”和“开中断指令”这两个特权指令

（4）无论是哪个进程控制原语，都无非要做三类事：

• 更新PCB的信息（修改状态、保存/恢复运行环境 等等）

• 将PCB插入合适的队列

• 分配/回收资源

2、进程控制相关原语

（1）进程的创建：

创建态->就绪态

创建原语：申请空白PCB -> 为新进程分配所需资源 -> 初始化PCB -> 将PCB插入就绪队列

（2）进程的终止：

就绪态/阻塞态/运行态->终止态->无

撤销原语：找到要终止的PCB -> 若进程正在运行，立即剥夺CPU并分配给其他进程 -> 终止所有子进程 -> 归还进程所有资源给父进程或操作系统 -> 删除PCB

（3）进程的阻塞：

运行态->阻塞态

阻塞原语：找到要阻塞的PCB -> 保护进程运行现场，设置PCB为阻塞态，暂时终止进程 -> 将PCB插入等待队列

（4）进程的唤醒：

阻塞态->就绪态

唤醒原语：找到要唤醒的PCB -> 从等待队列中移除PCB，设置为就绪态 -> 插入就绪队列

阻塞原语和唤醒原语必须成对使用，因何事阻塞，就因由何事唤醒。

（5）进程的切换：

运行态->就绪态/就绪态->运行态

切换原语：将运行环境信息存入PCB -> 移入相应队列 -> 选择另外一个进程执行，更新其PCB -> 恢复新进程PCB的运行环境

3、运行环境

运行环境也指进程上下文（Context），就是进程运行过程中寄存器存的一些中间结果，

当进程被切换时，需要将中间结果保存一下，避免被下一个进程覆盖

四、进程通信

1、进程间通信（IPC）

指两个进程之间产生数据交互

2、共享存储

基于数据结构的共享（固定分配，低级）

基于存储区的共享（划分存储区，灵活，高级）

3、消息传递

进程间的数据交换以格式化的消息为单位，通过操作系统的发送和接受消息两个原语进行数据交换

直接通信方式：消息直接挂到接受进程的消息队列里

间接通信方式：消息先发到中间体，间接利用信箱发送消息

4、管道通信

管道只能半双工通信，如果要实现全双工通信，需要设置两个管道

5、写进程与读进程

写进程：只要管道没满，写进程就可以往管道中写数据

读进程：只要管道没空，读进程就可以从管道中读数据

线程

五、线程基本概念

1、为什么引入线程

传统的进程只能串行的执行一系列程序，为了能够“同时”做很多事，因此引入了线程，增加并发度

2、线程的概念

线程是一个基本的CPU执行单元，也是程序执行流的最小单位

引入线程后，进程不再是CPU调度的基本单位，只作为除CPU之外的系统资源的分配单元

3、引入线程后的变化

资源分配调度：进程是资源分配的基本单位，线程是调度的基本单位

并发性：各线程间可以并发，提升了并发度

系统开销：可以只在进程中切换，减小CPU切换环境的系统开销

4、线程重要属性

• 线程是处理机调度的基本单位
• 多 CPU 计算机中，各个线程可占用不同的 CPU
• 每个线程都有一个线程 ID、线程控制块（TCB）
• 线程也有就绪、阻塞、运行三种基本状态
• 线程几乎不拥有系统资源
• 同一进程的不同线程间共享进程的资源
• 由于共享内存地址空间，统一进程中的线程间通信甚至无需系统干预
• 同一进程中的线程切换，不会引起进程切换
• 不同进程中的线程切换，会引起进程切换
• 切换同进程内的线程，系统开销很小
• 切换进程，系统开销较大

5、线程的组织与控制

（1）TCB（线程控制块）

• TID（类似PID）

• 程序计数器PC（线程目前执行到哪）

• 其他寄存器（线程运行中间结果）

• 堆栈指针（保存函数调用信息、局部变量）

• 线程运行状态

• 优先级（线程调度，资源分配参考）

（2）线程表

多个TCB组织成一张线程表

六、线程实现方式

1、线程的实现方式：

用户级线程（ULT）：从用户视角能看到的线程，由线程库实现

通过线程库实现，类似while循环，3个if处理不同逻辑，然后循环依次处理这三个if逻辑。

• 优点：只在用户空间即可切换线程，开销小，效率高

• 缺点：一个用户级线程被阻塞后，整个进程都会被阻塞，影响其他线程，并发度低

内核级线程（KLT）：操作系统视角看到的线程，由操作系统实现（内核级线程才是处理机分配的单位）

• 优点：一个线程阻塞后，别的线程还能继续执行，并发能力强

• 缺点：切换线程成本高，开销大

2、多线程模型

如果使用线程库能够实现将多个用户级线程映射到某一个内核级线程，那么根据映射方式可以得到这三种多线程模型：

（1）一对一模型

一个用户级线程映射到一个内核级线程

• 优：各个线程可以分配到多核处理机并行执行，并发度高

• 缺：线程管理都需要操作系统支持，开销大

（2）多对一模型

多个用户级线程映射到一个内核级线程

• 优：线程管理开销小效率高

• 缺：一个线程阻塞会导致整个进程都被阻塞

（3）多对多模型

n个用户及线程映射到m个内核级线程（n>=m）

• 优缺点：集二者之长

七、线程的状态与转换

线程的状态与转换

就绪态、运行态、阻塞态

状态的转换过程与进程一样

调度

八、调度的概念与层次

1、调度的基本概念

当有一堆任务要处理，由于资源有限，这些事没法同时处理，这时候就需要确定某种规则来决定处理这些任务的顺序，这就是调度研究的问题

2、调度的三个层次

（1）高级调度（作业调度）

概念：按照一定原则从外存作业后备队列中选一个作业调入内存，每个作业只调入一次，调出一次。

作业调入时会建立相应的 PCB，作业调出时才撤销 PCB。调入可由操作系统决定，调出由作业运行结束才调出

作业：一个具体的任务。
用户向系统提交作业=用户让操作系统启动一个程序（处理具体任务）

（2）低级调度（进程调度）

概念：按某种策略从就绪队列中选取一个进程，将处理机分配给它

进程调度是操作系统中最基本的一种调度，进程调度频率很高

（3）中级调度（内存调度）

概念：按照某种策略决定将哪个处于挂起状态的进程重新调入内存

内存不够时，将暂时不用的进程放到外存（PCB 不外放），内存空闲或进程需要运行时再重新调入内存。

调到外存的进程状态为挂起状态，被挂起的进程PCB形成挂起队列

3、三层调度的联系、对比

4、七状态模型

之前学过五状态模型，七状态模型新增了两个挂起状态：

九、进程调度的时机和方式

1、进程调度的时机

（1）什么时候需要进程调度？

• 主动放弃（进程正常终止、运行过程中发生异常而终止、进程主动请求阻塞）

• 被动放弃（分给进程的时间片用完、有更紧急的事需要处理、有更高优先级的进程进入就绪队列）

（2）什么时候不能进行进程调度？

• 在处理中断的过程中

• 访问内核程序临界区时，会影响操作系统内核的工作工作，不可以进行调度和切换

  访问普通临界区时，不会直接影响操作系统内核的管理工作，可以进行调度和切换

• 在操作系统内核程序临界区中

  • 临界资源：一个时段段内各进程互斥地访问临界资源
  • 临界区：访问临界资源的那段代码
  • 内核程序临界区会访问就绪队列，导致其上锁

• 在原子操作过程中（原语）

2、进程调度的方式

非抢占式（非剥夺）：更紧急的任务要执行，依然会让当前正在执行的任务执行，只能进程主动放弃处理机

抢占式（剥夺）：更紧急的任务要执行，会立即暂停当前正在执行的任务，进程被动放弃

3、进程的切换与过程

• 进程的切换：原来的进程暂停执行，切换到另一个进程执行
• 进程的过程
  • 保存原来运行进程的数据
  • 恢复新进程的数据

进程的调度和切换是有代价的

十、调度器和闲逛进程

1、调度器（调度程序）

调度程序决定：让谁运行（调度算法）、运行多长时间（时间片大小）

调度时机：创建新进程、进程退出、进程阻塞、I/O中断

2、闲逛进程

没有其他进程执行时，就会把闲逛进程弄上处理机去运行

十一、调度算法的评价指标

1、CPU利用率
CPU利用率=CPU忙碌时间/总时间
2、系统吞吐量
系统吞吐量 = 总共完成多少道作业 / 总共花了多少时间
3、周转时间

从作业被提交给系统开始，到作业完成的这段时间

包含四个部分：

• 作业在外存后备队列上等待作业调度的时间（高级调度）

• 进程在就绪队列上等待进程调度的时间（低级调度）

• 进程在CPU上执行的时间

• 进程等待I/O操作完成的时间

公式：

周转时间 = 作业完成时间 - 作业提交时间

平均周转时间 = 各作业周转时间之和 / 作业数

带权周转时间 = 作业周转时间 / 作业实际运行时间 = (作业完成时间 - 作业提交时间) / 作业实际运行时间

平均带权周转时间 = 各作业带权周转时间之和 / 作业数

4、等待时间

进程或作业处于等待处理机状态时间之和

5、响应时间

从用户提交请求到首次产生响应所用时间

十二、调度算法

1、先来先服务（FCFS）

• 按照作业/进程到达前后顺序进行排序

• 非抢占式

• 优点：公平、算法简单

• 缺点：对长作业有利、对短作业不利

• 不会饥饿

2、短作业优先（SJF）

• 最短的作业/进程优先服务，时间相同，先到达的先服务

• 非抢占式（有抢占式版本FRTN——最短剩余时间优先算法）

• 优点：“最短的”平均等待时间、平均周转时间

• 缺点：对短作业有利、对长作业不利

• 可能会产生饥饿（短进程源源不断进入）

优点中“最短的”解释：为什么加双引号？因为最短剩余时间优先算法得到的平均等待时间、平均周转时间还会更短，因此直接说SJF最短不太严谨。应该加上前提条件“所有进程同时可运行/几乎同时到达时”，SJF平均等待时间、平均周转时间最短

3、高响应比优先（HRRN）

• 综合考虑作业/进程的等待时间和要求服务时间，每次调度时计算各个作业/进程的响应比，选择响应比最高的
• 非抢占式
• 优缺点：结合了FCFS和SJF的优点，并且对于长作业，等待时间越来越久，响应比也会增大，避免长作业饥饿
• 不会导致饥饿

4、时间片轮转算法（RR）

• 公平的轮流为每个进程服务，让各个进程在一定时间间隔内得到响应。按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片，若进程未在一个时间片内完成，则剥夺处理及并重新放到就绪队列排队
• 抢占式
• 优点：响应快，适用于分时操作系统
• 缺点：高频率进程切换，有开销；不区分任务紧急程度
• 不会饥饿

如果时间片太大，那么就会退化为先来先服务算法，增大响应时间、因此时间片不能太大。

如果时间片太小，那么进程切换就会过于频繁，系统会花大量时间处理进程切换

5、优先级调度算法

• 根据任务紧急程序决定处理顺序，每个进程/作业都有优先级，调度时选择优先级最高的
• 抢占式、非抢占式均有，抢占式在就绪队列发生变化时检查是否要抢占
• 优点：优先级区分紧急程度，适用于实时操作系统，灵活
• 缺点：源源不断的高优先级进程到来，可能会导致饥饿
• 会产生饥饿

静态优先级：不变

动态优先级：可变

6、多级反馈队列调度算法

• 对其他算法调度的折中权衡，设计多级就绪队列（优先级从高到低，时间片从小到大），新进程进入第1级队列，按FCFS原则等待分配时间片，若时间片用完进程未结束，进入下一级队列队尾，以此类推，如果是最后一级队列，则重新放回该队列。只有k级队列为空，k+1级队列队头才可以分配时间片
• 默认抢占式
• 优点：对各个进程相对公平（FCFS优点）、每个新到达进程很快可以响应（RR优点）、短进程使用较少时间可以完成（SPF优点、不必实现估计进程的运行时间（避免用户造假），可灵活调整各类进程偏好程度（CPU密集型进程、IO密集型进程）
• 会产生饥饿（源源不断的短进程进入）

7、多级队列调度算法

系统中按进程类型设置多个队列，队列之间可以按优先级划分（高优先级空时低优先级才能调度）或时间片划分（如3个队列分配时间50%、40%、10%），并且各个队列可采取不同调度策略

十三、多处理机调度

1、单处理机调度和多处理机调度

单处理机：只需决定让哪个就绪队列优先上处理机（CPU）运行

多处理机：除了决定哪些进程上处理机，还需要决定被调度的进程上哪个处理机

2、负载均衡、处理及亲和性

负载均衡：尽可能让每个CPU同等忙碌

处理机亲和性：尽量让一个进程调度到同一个CPU，发挥CPU中缓存的作用（Cache）

3、解决方案：

（1）公共就绪队列

• 每个CPU空闲时都会运行调度程序

• 天然实现了负载均衡，但亲和性较差

（2）私有就绪队列

• 推迁移：周期性检查每个处理器负载，负载不平衡时，将忙碌的CPU就绪队列中“推”一些就绪进程到空闲CPU的就绪队列中

• 拉迁移：周期性检查自身负载与其他CPU负载，CPU负载低时，从其他高负载CPU就绪队列中“拉”一些就绪进程到自己的就绪队列中

• 天然实现了处理机亲和性

进程同步与互斥

十四、同步互斥的概念

1、进程同步

指为了完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调他们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。（比如P1进程的某个代码必须在P2进程的某个代码后执行）

2、进程互斥

把一个时间段内只允许一个进程使用的资源称为临界资源。

对临界资源的互斥访问，可以在逻辑上分为四个部分：

do{
    entry section;    //进入区     对访问的资源检查或进行上锁
    critical section; //临界区(段) 访问临界资源的那部分代码
    exit section;     //退出区     负责解锁
    remainder section;//剩余区     其它处理
} while(true);

实现对临界资源的互斥访问，保证系统整体性能，需要遵循以下原则：

• 空闲让进。临界区空闲，可以直接进去

• 忙则等待。已有进程进入临界区，繁忙不能进去

• 有限等待。不能让进程等待无限长时间

• 让权等待。不能进入临界区时，应立即释放处理机，不要堵着

十五、进程互斥的软件实现方法

1、单标志法

两个进程在访问完临界区后会把使用临界区的权限交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予

int turn = 0; // turn表示当前允许进入临界区的进程号

//p0进程
while(turn!=0);
critical section;
turn = 1;
remainder section;

//p1进程
while(turn!=1);
critical section;
turn = 0;
remainder section;

缺点：p1要访问的话，必须p0先访问，即使临界区空闲p1也无法访问，违背”空闲让进“原则

2、双标志先检查法

设置一个bool数组flag[]来标记自己是否想要进入临界区的意愿

bool flag[2] = {false,false}; // 表示进程是否有进入临界区的意愿

//p0进程
while(flag[1]); // ①
flag[0]=true; // ②
critical section;
flag[0]=false;
remainder section;

//p1进程
while(flag[0]); // ⑤
flag[1]=true; // ⑥
critical section;
flag[1]=false;
remainder section;

缺点：并发问题，如果执行顺序为①⑤②⑥，p0和p1会同时访问临界区，违反”忙则等待“原则

3、双标志后检查法

设置一个bool数组flag[]来标记自己是否想要进入临界区的意愿，不过是先上锁后检查

bool flag[2]={false,false}; // 表示进程是否有进入临界区的意愿

//p0进程
flag[0]=true; // ①
while(flag[1]); // ②
critical section;
flag[0]=false;
remainder section;

//p1进程
flag[1]=true; // ⑤
while(flag[0]); // ⑥
critical section;
flag[1]=false;
remainder section;

缺点：并发问题，如果执行顺序为①⑤②⑥，p0和p1会同时上锁，导致死锁，违反”空闲让进“和”有限等待“原则，而且会产生饥饿

4、Peterson算法

主动让对方先使用处理器，比如p0进程，先表达自己使用处理机的意愿（flag[0]=true），再谦让给对方（turn=1），最后表示谦让的进程会让对方进程先使用

个人理解：flag解决了单标志法的”空闲让进“问题，在双方都想使用处理机时（flag=true），turn可以保证只有一方能够进入临界区，解决了”忙则等待“和”有限等待“问题

bool flag[2]={false,false};
int turn=0;

//p0进程
flag[0]=true;
turn=1;
while(flag[1]&&turn==1);
critical section;
flag[0]=false;
remainder section;

//p1进程
flag[1]=true;
turn=0;
while(flag[0]&&turn==0);
critical section;
flag[1]=false;
remainder section;

优点：遵循空闲让进、忙则等待、有限等待三个原则

缺点：未遵循让权等待的原则（等待的一方会卡在while循环）

十六、进程互斥的硬件实现方法

1、中断屏蔽方法

利用“开/关中断指令”实现（与原语实现思路相同，在某进程开始访问临界区到结束访问为止，不允许被中断）

...
关中断;
临界区;
开中断;
...

优点：简单高效

缺点：不适合多处理机；只适用于操作系统内核进程，不适用于用户进程（“开/关中断指令”只能运行在内核态）

2、TestAndSet指令（TS指令）

或者叫（TestAndSetLock指令，TSL指令）

TSL指令由硬件实现，执行过程不允许中断，一气呵成，C语言描述如下：

// TSL指令：检查是否可以进入临界区并上锁
bool TestAndSet(bool *lock){
    bool old;
    old = *lock; // 记录原来的lock值
    *lock = true; // 加锁
    return old; // 返回原来lock值
}

使用TSL指令实现互斥的算法逻辑：

while (TestAndSet(&lock)); // "检查"并“上锁”
临界区代码段...
lock = false; // 解锁
剩余区代码段...

解释：

TSL指令中：
lock表示当前临界区是否被加锁（true加锁，false不加锁）
TSL指令实现了“检查”并“上锁”，先检查是否可以进入临界区（old值），然后无论是否加锁，都将lock设为true（表示自己要进去）

互斥算法逻辑中：
①若lock已经为true，则其他进程会卡在while循环（其他进程上锁不影响，因为lock本身就为true）
②若lock为false（被解锁或者没有进程用），则其中一个进程会检查成功进入并上锁，其他进程还是继续执行①。

优点：实现简单，无需像软件实现那样严格检查是否由逻辑漏洞；适合多处理机环境

缺点：不满足“让权等待”原则，会导致“忙等”

3、Swap指令

或者叫Exchange指令，检查XCHG指令

Swap指令由硬件实现，执行过程不允许中断，一气呵成，C语言描述如下：

// Swap指令：交换两个变量值
bool TestAndSet(bool *a,bool *b){
    bool temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

使用Swap指令实现互斥的算法逻辑：

bool old = true;
while (old == true){
	Swap(&lock,old);   
}
临界区代码段...
lock = false; // 解锁
剩余区代码段...

解释：

Swap指令中：
用于交换两个变量值

互斥算法逻辑中：
Swap逻辑上和TSL并无太大区别，都是先记录原临界区是否上锁，并将上锁标记lock设为true。
①若lock已经为true，则其他进程会卡在while循环，并且old和lock会不断交换（此时old和lock都一直为true）
②若lock为false，则其中一个进程会检查成功，此时该进程lock=false，old=true，Swap完之后lock=true，old=false。该进程成功进入临界区，其他进程继续执行①。

优点：实现简单，无需像软件实现那样严格检查是否由逻辑漏洞；适合多处理机环境

缺点：不满足“让权等待”原则，会导致“忙等”

十七、互斥锁

解决临界区最简单的工具就是互斥锁，一个进程进入临界区获得锁，退出临界区释放锁。

下面是C语言描述：

acquire(){
	while (!available); // 忙等待
    available = false; // 获得锁
}
release(){
    available = true; // 释放锁
}

acquire和release必须是原子操作，因此互斥锁通常用硬件机制实现

需要连续循环忙等的互斥锁称为自旋锁（spin lock），如TSL指令，Swap指令，单标志法

特点：

• 忙等，违反“让权等待”
• 等待时间不用切换进程上下文，多处理器系统中，若上锁时间短，则等待代价很低
• 常用于多处理器系统，一个核忙等，其他核照常工作，并快速释放临界区
• 不适用于单处理机系统。若一个进程占用处理机并忙等，此过程中是不可能解锁并进入临界区的（只能等时间片用完，让给拥有临界区的进程执行完并解锁，才有机会进入）

信号

十八、信号

1、信号与信号量

信号量（Semaphore）：实现进程间的同步、互斥

信号（Signal）：实现进程间的通信（IPC）

2、信号的概念

信号用于通知进程的某个特定事件已经发生，进程收到信号后，会对信号进行处理。

3、信号的作用

用于通知进程某个特定事件已经发生，实现简单的进程间通信

4、实现原理

（1）信号的发送

每个进程的PCB中，会有下图所示的两个位向量：

一个是待处理信号，另一个是信号掩码

（2）信号的处理

• 信号激活的计算方式

只处理pending中对应激活位的信号，并且不接收掩码blocked中对应位的信号

假设pending为10000001，blocked为00000011，结果为处理信号1，不处理信号8
pending \&\sim blocked = 10000000

• 何时进行信号处理

当进程从内核态转为用户态时，如果有待处理信号，则处理信号

• 如何处理信号

​ ① 执行默认信号处理程序：

​ 操作系统内核对每一种信号都有默认处理程序

​ 某些信号默认是忽略，代表不做任何事

​ ② 执行用户自定义了对应信号处理程序：

​ 允许进程通过系统调用，自定义某些信号的处理程序

​ 自定义信号处理程序会覆盖默认处理

• 特点

  ①信号处理程序运行结束后，通常会返回进程的下一条指令继续执行（除非被信号处理程序阻塞或终止）
  ②当处理完某个信号后，pending位就会重置为0
  ③重复接收到同一个信号，则新的信号会被丢弃
  ④同时有多个信号，通常先处理序号更小的信号
  ⑤每个进程都可以有自己的自定义信号处理程序，它们之间是独立的

3、信号和异常的关系

信号可作为异常处理的补充，如果异常无法全部由内核完成，就可以让用户进程配合，比如发送特定信号

十九、信号量机制

1、回顾

之前学习的这些进程互斥的解决方案，四种软件实现方式、三种硬件实现方式都有些问题：

（1）在双标志先检查法中，进入区的“检查”“上锁”操作无法一气呵成，导致两个进程有可能同时进入临界区的问题；

（2）所有的解决方案都无法实现“让权等待”

1965年，荷兰学者Dijkstra提出了一种卓有成效的实现进程互斥、同步的方法——信号量机制

2、概念：

用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现进程互斥和同步。

信号量：其实就是一个变量，可以用一个信号量来表示系统中某种资源的数量，如系统中只有一台打印机，就可以设置一个初值为1的信号量。

原语：一种特殊的程序段，其执行只能一气呵成，不可被中断，原语是由关中断/开中断指令实现的。

一对原语：wait(S)原语和signal(S)原语，可以把原语理解为函数，函数名分别为wait和signal，信号量S就是函数调用的参数。

wait、signal原语常简称为P、V操作（来自荷兰语proberen和verhogen）。因此，做题时常把wait(S)、signal(S)分别写为P(S)、V(S)，P表示申请，V表示释放。

3、信号量

（1）整型信号量

三种操作：初始化、P操作、V操作

这里wait操作和双标志检查法类似，但是由于“检查”和“上锁“一气呵成，因此不会出现并发导致的问题

int S = 1; // 初始化
void wait(int S){ // P操作
    while (S <= 0); // 检查（资源不够则忙等）
    S = S - 1; // 上锁，占用1个资源
}
void signal(int S){ // V操作
    S = S + 1; // 解锁，释放1个资源
}

// 进程p0
...
wait(S); 	// 进入区
使用资源	 // 临界区
signal(S);  // 退出区
...

缺点：不满足条件会一直判断导致“忙等”，不满足“让权等待”原则

（2）记录型信号量（重点）

通过记录型信号量的数据结构（记录剩余量和阻塞队列），让需要资源但没分配到的进程进入阻塞态，进而解决整型信号量的“忙等”问题

// 记录型信号量定义
typedef struct{
    int value; // 剩余资源数
    Struct process *L; // 等待队列
} Semaphore;
// wait原语
void wait(Semaphore S){
    S.value--;
    if (S.value < 0){ // 如果资源不够了，则阻塞等待
        block(S.L); // block原语：进程进入阻塞态，并记录到信号量S的等待队列中
    }
}
// signal原语
void signal(Semaphore S){
    S.value++;
    if (S.value <= 0){ // 释放资源，发现资源数还是<=0，说明有进程在等待资源
        wakeup(S.L); // wakeup原语：唤醒等待队列中的一个进程，进入就绪态
    }
}

优点：遵循“让权等待”原则，不会出现“忙等”。

这是高频考点，除非特别声明，否则P(S)和V(S)中默认S为记录型信号量

4、答疑解惑

在上面的整型信号量那里，有个不太严谨的地方：

上面这个wait操作里，我们说”检查“和”上锁“一气呵成，不可中断，但如果此时while检查到S<=0，就会卡住，而且因为不可中断，所以进程一直不会切换，岂不是会导致死循环？视频里没讲清楚，经过我的查阅，正确的信号量操作是这样的：

Semaphore S;
wait(S) {
    关中断；
    while(S <= 0) {
        开中断；
        关中断；
    }
    S = S-1;
    开中断；
}
signal(S) {
    关中断；
    S = S+1;
    开中断；
}

可以发现，wait中，我们在while循环里添加了开中断和关中断，这样可以保证在while循环卡住时，依然可以正常切换到其他进程。这里可能有不太理解的地方，我详细说一下：

大家可能会有和我一样的疑惑，就是while循环里开中断了，不是破环了原子性吗，wait怎么会一气呵成呢？

经过我一番捣鼓，我发现信号量wait的原子性不是要求整个函数从开始到结束都不被打断，而是要求 “判断到信号量可用(S>0)” 和 “修改信号量(S=S-1)” 这两个动作必须连续执行，不能打断。

① 当忙等时（S<=0），不会占用资源，此时被中断完全不影响安全性，因此在while循环中开中断，允许被中断并让出CPU
② 当可占用资源时（S>0），下一步必须修改信号量，这两步一气呵成不能被打断，否则导致类似 双标志先检查法 中的并发问题。（S>0不会进入while循环，也就不会开中断，从而保证这两个动作的原子性）

可以看看2021考研408的45题：2021 年 408 真题 | 计算机考研杂货铺

二十、信号量实现进程同步和互斥

1、互斥信号量

① 分析并发进程关键活动，划定临界区

② 设置互斥信号量mutex，初值为1

③ 在进入区P(mutex)，退出区V(mutex)

semaphore mutex = 1; // 信号量
// 进程P1
P1(){
    ...
    P(mutex); // 进入区
    临界区代码段...
    V(mutex); // 退出区
    ...
}
// 进程P2
P2(){
    ...
    P(mutex);
    临界区代码段...
    V(mutex);
    ...
}

2、同步信号量

① 分析同步关系，保证一前一后执行两个操作

② 设置同步信号量S，初值为0

③ 在前操作之后执行V(S)，在后操作之前执行P(S)。（前V后P）

semaphore S = 0; // 信号量
// 进程P1
P1(){
    代码1;
    代码2;
    V(S);
    代码3;
}
// 进程P2
P2(){
    P(S);
    代码4;
    代码5;
    代码6;
}

二十一、经典同步和互斥问题

（一）生产者消费者问题

1、问题描述：

生产者、消费者共享一个初始为空，大小为n的缓冲区。

只要缓冲区没满，生产者就可以把产品放进缓冲区，否则必须等待；

只要缓冲区没空，消费者就可以从缓冲区取出产品，否则必须等待

缓冲区是临界资源，必须互斥等待。

2、解决思路：

变量：

semaphore mutex = 1; // 互斥信号量，实现互斥访问
semaphore empty = n; // 同步信号量，表示空缓冲块数量（空格数量）
semaphore full = 0; // 同步信号量，表示满缓冲块数量（产品数量）

实现：

producer(){
    while (1){
        生产一个产品;
        P(empty); // ①
        P(mutex); // ②
        产品放入缓冲区;
        V(mutex); // ③
        V(full); // ④
	}
}

consumer(){
    while (1){
        P(full);
        P(mutex);
        从缓冲区取出产品;
        V(mutex);
        V(empty);
        使用一个产品;
	}
}

解释：

以生产者为例（消费者同理）：
1、①②能否互换？
P(mutex); // ②
P(empty); // ①
不行。否则当empty为0时，producer会通过P(mutex)上锁并卡在P(empty)，此时必须等consumer释放empty。但此时上锁了，consumer无法进入并释放empty，两进程相互等待，导致死锁。
实现互斥的P操作必须在实现同步的P操作之后。

2、③④能否互换？
可以。这两个是释放资源，实现操作并不会导致进程阻塞。

3、生产产品能否放进临界区
可以，但是不推荐。生产产品是进程独立的操作，不用放在临界区中，放了也没问题，但是会增加临界区占用时间

（二）多生产者多消费者问题

1、问题描述：

桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专放苹果，妈妈专放橘子，儿子专吃橘子，女儿专吃苹果。只有盘子空时，爸爸或妈妈才可放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以取出水果。

假设盘子只能放一个水果（容量为1）

2、解决思路：

变量：

semaphore mutex=1;  //实现互斥访问缓冲区
semaphore apple=0;  //盘子中有几个苹果
semaphore orange=0; //盘子中有几个橘子
semaphore plate=1;  //盘子中还可以放多少个水果（缓冲区）

实现：

解释：

这里mutex可以去掉，因为此时缓冲区大小为1，同一时刻只能有一个进程访问缓冲区（mutex为1的原因应该也是这个）。
但是通常不要去掉，当缓冲区大小>=2时，就必须得要mutex实现互斥访问了

（三）吸烟者问题

1、问题描述

假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、 第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，但每次只将两种材料放桌子上，拥有剩下那种材料的抽烟者会卷烟并抽掉它，并给供应者一个信号表示完成了，供应者就会放另外两种材料再桌上，这个过程一直重复（让三个抽烟者轮流地抽烟）

本质上这也属于“生产者-消费者”问题，是“生产多种产品的单生产者——多消费者”问题。

2、解决思路

理清PV顺序，可以这样理解：

组合1：纸+胶水 -> 第1个抽烟者取东西

组合2：烟草+胶水 -> 第2个抽烟者取东西

组合3：烟草+纸 -> 第3个抽烟者取东西

发出完成信号 -> 供应者将下一个组合放到桌上

变量：

semaphore offer1=0; //桌上组合1的数量
semaphore offer2=0; //桌上组合2的数量
semaphore offer3=0; //桌上组合3的数量
semaphore finish=0; //抽烟是否完成
int i=0; 			//用于实现“三个抽烟者轮流抽烟”

实现：

provider(){
    while(1){
        // 各个V操作放在各自对应的事件的位置
        if(i==0){
            将组合一放桌上;
            V(offer1);
        }elseif(i==1){
            将组合二放桌上;
            V(offer2);
        }elseif(i==2){
            将组合三放桌上;
            V(offer3);
        }
        i=(i+1)%3; // 轮流提供
        P(finish); // 检查完成信号
    }
}

smoker1(){
    while(1){
        P(offer1);
        从桌上拿走组合1,卷烟抽掉;
        V(finish);
    }
}
smoker2(){
    while(1){
        P(offer2);
        从桌上拿走组合2,卷烟抽掉;
        V(finish);
    }
}
smoker3(){
    while(1){
        P(offer3);
        从桌上拿走组合3,卷烟抽掉;
        V(finish);
    }
}

（四）读者写者问题

1、问题描述

有读者和写者两组并发进程，共享一个文件，多个读进程同时访问文件无影响（因为没有类似消费者的取操作），但某个写进程和其他进程（读进程或写进程）同时访问文件时则可能导致错误。

要求：（读者可以一起读文件，写者只能有自己一人写文件）

① 允许多个读者同时对文件执行读操作；

② 只允许一个写者往文件中写信息；

③ 任一写者在完成写操作之前不允许其他读者或写者进入；

④ 写者执行写操作前，应让已有的读者和写者全部退出。

2、解决思路

互斥关系：读进程——读进程，读进程——写进程。（读进程——读进程不影响）

变量：

semaphore rw=1; 	//用于实现对共享文件的互斥访问
int count=0; 		//记录当前有几个读进程在访问文件
semaphore mutex=1;  //用于保证对count变量的互斥访问
semaphore w=1; 		//用于实现“写优先”

实现：（为了增加可读性，我适当增加了缩进）

writer(){
    while(1){
        P(w);
        P(rw); // 写之前加锁
        写文件...
        V(rw); // 写完解锁
        V(w);
    }
}

reader(){
     while(1){
         P(w);
         P(mutex); 			// 读进程互斥访问count
             if(count==0) 	// 由第一个读进程负责
                P(rw); 		// 读之前加锁
             count++; 		// 访问文件的读进程数+1
         V(mutex);
         V(w);
         读文件...
         P(mutex); 		 	// 读进程互斥访问count
             count--; 	 	// 访问文件的读进程数-1
             if(count==0)   // 由最后一个读进程负责
                V(rw); 	 	// 读完了解锁
         V(mutex);
     }
 }

解释：

1、变量解释：
rw是为了实现读写进程的互斥访问，要么读，要么写，两者互斥
count记录当前读进程数量，可以实现由第一个读进程和最后一个读进程控制rw（count==0），这样子如果有多个读者，后来读者就不会被卡在P(rw)，而是很顺利的就可以直接读了（因为后来的count>0，表示有人在读，自己当然就可以读了，只有所有人读完了才关闭rw，即最后一个人释放rw）
mutex是为了实现对count变量的互斥访问，不然多个读进程同时访问count就会导致问题
w用于实现“写优先”，如果没有w，那么如果有源源不断的读进程进入，那么count一直>0，rw一直不会释放，写进程就会产生饥饿，因此w就是为了防止这种事情发生的。
    
2、w解释：
假设按照 读进程1->写进程1->读进程2 的执行顺序：
读进程1先占用了P(w)，写进程1和读进程2都会卡在P(w)，此时若读进程1释放了w，写进程1就会执行P(w)上锁，有种“我要写了，其他进程别进来”的意思，此时读进程2还会卡在P(w)。
由于其他读进程不会源源不断进入了，所以解决了饥饿问题。
    
3、“写优先”解释：
这种算法并不是真正的“写优先”，而是相对公平的“先来先服务”原则。卡在P(w)的进程会按照先后次序形成队列，写进程并非优先在队首。有的书上会写“读写公平法”。

（五）哲学家问题

1、问题描述

一张圆桌上坐着5名哲学家，每两个哲学家之间摆一根筷子，桌子中间是米饭。哲学家们倾注毕生的精力用于思考和进餐，哲学家在思考时，不影响他人。当当哲学家饥饿时，才试图拿起左右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

这个问题与之前遇到的问题不同的是，每个哲学家进程需要同时持有两个临界资源才能开始吃饭。（即一个进程需要两个以上临界区资源）

2、解决思路

信号量设置。定义互斥信号量数组chopstick[5]={1,1,1,1,1}，实现对5个筷子的互斥访问。并对哲学家按0~4编号，哲学家i左边 的筷子编号为i，右边的筷子编号为(i+1)%5。

有以下几种解决思路：

① 可以对哲学家进程施加一些限制条件，比如最多允许4个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子

② 要求奇数号哲学家先拿左边的筷子，再拿右边的筷子，而偶数号哲学家刚好相反。这可以保证如果相邻两个哲学家（奇偶必定不同）都想吃饭，那么就会互相争夺同一根筷子，最后一个进程执行，另一个阻塞

③ 仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子。

我们按③实现

变量：

semaphore chopstick[5]={1,1,1,1,1}; // 临界区资源
semaphore mutex=1; //互斥访问临界区

实现：

Pi(){ //i号哲学家的进程
	while(1){
        P(mutex);
        P(chopstick[i]); //拿左
        P(chopstick[(i+1)%5]); //拿右
        V(mutex);
        吃饭…
        V(chopstick[i]); //放左
        V(chopstick[(i+1)%5]); //放右
        思考…
    }
}

解释：

③这个说法不太准确：
应该是保证哲学家拿筷子是互斥执行的。这样即使一个哲学家在拿筷子拿到一半时被阻塞（比如卡在拿左筷子），也不会有别的哲学家会继续尝试拿筷子（因为mutex==0）。只有当正在吃饭的哲学家放下筷子后，被阻塞的哲学家才可以拿到筷子。避免了死锁

3、总结

哲学家进餐问题的关键在于解决进程死锁。每个进程都需要同时持有两个临界资源，因此就有“死锁”问题的隐患。如果遇到了一个进程需要同时持有多个临界资源的情况，应该参考哲学家问题的思想。

管程

二十二、管程

1、为什么要引入管程

PV操作容易出错、困难，利用管程“封装”的思想，可以让程序员更方便的编写程序

2、管程的定义和基本特征

这个可以用面向对象理解，为了方便理解，我会在括号内填上对应知识

定义

• 局部于管程的共享数据结构说明（属性）
• 对该数据结构进程操作的一组过程（方法）
• 对局部于管程的共享数据设置初始值的语句（构造函数）
• 管程有一个名字（类名）

基本特征

• 局部于管程数据结构只能被局部于管程的过程所访问（私有属性）
• 一个进程只有通过调用管程内的过程才能进入管程访问共享数据（公共方法）
• 每次仅允许一个进程在管程内执行某个内部过程（互斥访问共享缓冲区）

感觉上述还是不太精确，网上找了这个理解方式，需要可以看下：

​ 管程是一种机制，用于强制并发线程对一组共享变量的互斥访问。管程还提供了等待线程满足特定条件的机制，并通知其他线程该条件已满足的方法。

管程两个主要功能

• 互斥访问
• 条件等待和通知

	可以将管程理解为一个房间，这个房间里有一些共享的资源，比如变量、队列等。同时，房间里有一个门，只有一把钥匙。多个线程或进程需要访问房间内的资源时，它们需要先获得这把钥匙，一次只能有一个线程或进程持有钥匙，进入房间并访问资源。其他线程或进程必须等待，直到当前持有钥匙的线程或进程释放钥匙，才能获得钥匙进入房间。
	此外，管程还提供了条件变量，类似于房间内的提示牌。线程在进入房间后，如果发现某个条件不满足（比如队列为空），它可以通过条件变量来知道自己需要等待，暂时离开房间，并将钥匙交给下一个等待的线程。当其他线程满足了等待的条件（比如向队列中添加了元素），它可以通过条件变量通知告诉正在等待的线程，使其重新获得钥匙进入房间，并继续执行。

3、拓展一：用管程解决生产者消费者问题

下面用伪代码的方式描述

管程：monitor和end monitor用于表示管程的范围

monitor producerconsumer
    condition full,empty; // 实现同步的条件变量
    int count = 0; // 缓冲区产品数
	// 产品放入缓冲区
    void insert(Item item){
        if(count == N)
        	wait(full); // 阻塞
        count++;
        insert_item(item);
        if(count == 1)
    		signal(empty); // 唤醒
    }
	// 缓冲区取走物品
    Item remove(){
        if(count == 0)
        	wait(empty); // 阻塞
        count--;
        if(count == N-1)
        	signal(full); // 唤醒
        return remove_item();
    }
end monitor;

使用：使用时只需调用方法，无需关心同步互斥这些问题，由管程自己解决

producer(){
    while(1){
        item = 生产一个产品;
        producerconsumer.insert(item);
    }
}

consumer(){
    while(1){
        item = producerconsumer.remove();
        消费产品 item;
    }
}

java中用synchronized来描述一个函数，这个函数同一时间只能被一个线程调用

死锁

二十三、死锁

1、概念

死锁：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象

2、易混淆概念

• 死锁

  • 定义：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象。

  • 区别：至少两个或两个的进程同时发生死锁

• 饥饿

  • 定义：由于长期得不到想要的资源，某进程无法向前推进的现象。

  • 区别：可能只有一个进程发生饥饿

• 死循环

• 定义：某进程执行过程中一直跳不出某个循环的现象。

• 区别：死循环是程序员的问题

3、死锁产生的条件：（缺一不可）

• 互斥条件：多个进程争夺资源发生死锁
• 不剥夺条件：进程获得的资源不能由其它进程强行抢夺
• 请求和保持条件：某个进程有了资源，还在请求资源
• 循环等待条件：存在资源的循环等待链

4、什么时候会发生死锁

• 对系统资源的竞争
• 进程推进顺序非法
• 信号量的使用不当也会造成死锁

5、死锁的处理策略

• 预防死锁
• 避免死锁
• 死锁的检测和解除

二十三、死锁处理策略

（一）预防死锁

1、破坏互斥条件

把互斥的资源改造为共享资源

缺点：可行性不高，很多时候无法破环互斥条件

2、破坏不剥夺条件

方案1：当请求得不到满足的时候，立即释放手里的资源

方案2：由系统介入，强行帮助剥夺

缺点：实现复杂；可能造成前一阶段的工作失效；降低系统开销；若采用方案1，如果一直得不到某个资源，不断重复放弃资源并申请、会导致饥饿

3、破坏请求和保持条件

静态分配方法：一次性申请全部资源，如果申请未满足，则不运行。一旦运行就不会请求别的任何资源

缺点：运行时一直占有所有资源，资源利用率极低；可能会导致进程饥饿（一直申请不到全部资源）

4、破坏循环等待条件

顺序资源分配法：对资源编号，进程按编号递增顺序请求资源，只有占有小编号资源，才能申请大编号资源，而大编号不能反向申请小编号资源，从而不会导致循环等待。

缺点：不方便增加新的设备，因为要重新编号；实际使用与递增顺序不一致，会导致资源的浪费；必须按规定次序申请资源，编程麻烦

（二）避免死锁

1、安全序列、不安全状态和死锁的关系：

• 安全序列：系统按照这种序列分配资源，每个进程都能顺利完成。安全序列可能有多个。
• 安全状态：只要能找到一个安全序列，系统就是安全状态。
• 不安全状态：系统中找不到任何一个安全序列，则进入不安全状态，后续可能会发生死锁（如果有进程归还资源，则有机会回到安全状态）。

关系

如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能会发生死锁。

2、银行家算法

这是Dijkstra提出的为银行设计的算法，后来运用到操作系统中，可以避免死锁。

实际情况会有多种资源进行分配，类似这样的情景：

安全性算法手算

初始资源分配完成后，优先把全部分配给最少能满足的，并且拿回其占有的资源。接着重复上述步骤直至找出安全序列或者卡住（找不到安全序列）。

银行家算法实现步骤（无代码）

① 检查此次申请是否超过了之前声明的最大需求数（超过了认为出错）

② 检查此时系统剩余的可用资源是否还能满足这次请求（不满足则等待）

③ 试探着分配，更改各数据结构（并非真正修改，只是为了做预判）

④ 用安全性算法检查此次所分配是否会导致系统进入不安全状态

（三）死锁检测和解除

1、死锁的检测

（1）用某种数据结构来保存资源的请求和分配信息

（2）提供一种算法，利用上述信息来检测系统是否已进入死锁状态

死锁检测算法

① 找出既不阻塞又不是孤点的进程（不是孤点意味着至少有一条边与进程相连），并消去所有请求边和分配边，使之成为孤点。

② 释放该进程的资源，可以唤醒一些阻塞的进程。重复上述步骤

若最终能够去除所有边，则代表该图是可完全简化的；否则就是不可完全简化的，此时系统会发生死锁。

2、死锁的解除

① 资源剥夺法：挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。

② 撤销进程法：强制撤销部分，甚至全部死锁进程，并剥夺这些进程的资源。

③ 进程回退法：让一个或多个死锁进程回退到足以避免死锁的地步。