大家好，我是讯享网，很高兴认识大家。



 <svg xmlns="http://www.w3.org/2000/svg" style="display: none;"> <path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"></path> </svg> <p></p> 

讯享网

• CPU 有两种状态，“内核态”和“用户态”
• 处于内核态时，说明此时正在运行的是内核程序，此时可以执行特权指令
  处于用户态时，说明此时正在运行的是应用程序，此时只能执行非特权指令
  
• CPU中有一个寄存器叫程序状态字寄存器(PSW)，其中有个二进制位，1表示“内核态”，0表示“用户态”

讯享网

并行： 同时进行，如：一边打电话，一边炒菜
并发： 在一段时间内交替进行，显得好像是“同时”进行，如：在厨房炒菜，听到座机响了，于是去客厅接电话，然后再回到厨房炒菜，再去客厅接电话……
单CPU多线程提供并发能力，而多CPU可以提供并行能力

（1）创建状态：一个系统将 exe 文件从硬盘调度到内存的过程，在内存中为该进程分配起始内存空间，做初始化操作，以及为进程创建 PCB 等等
（2）就绪态：一个进程以及被创建完成，且具有可以上 CPU 的条件，但是 CPU 正在忙碌，需要等待分配时间片
（3）执行态：进程上 CPU， CPU 执行对应进程的指令
（4）阻塞态：该进程在 CPU 上，CPU 在执行指令的过程中，因为该进程的某些请求无法完成，如请求共享打印机等，但是打印机正在忙碌，此时进程无法继续执行下一条指令，因此该进程被迫下 CPU，处于阻塞态，不具有可上 CPU 的条件，如果打印机恢复正常，那么该进程又具备上 CPU 的权利，因此转为就绪态
（5）终止状态：该进程在 CPU 上执行成功

正常情况下，CPU过一条指令就检查有无中断信号，如果开启了“关中断指令”那么不会继续检查，如果有中断信号发送到，也不会做任何处理

无论哪个进程控制原语，流程如下：1.更新PCB中的信息 2.将PCB插入合适的队列 3. 分配/回收资源 在原语切换过程中，设计到的“运行环境”是指，该进程的一系列指令在 CPU 中一系列寄存器的有关本进程的相关信息，类似于一个快照，那么保存运行环境就是建立一个当前的快照存储到 PCB 中

各个进程之间是相互独立的，其内存地址空间也是相互独立的，进程只能访问自身的内存地址

2.3.1 共享存储

2.3.2 消息传递

2.3.3 管道通信

管道：pipe，先进先出原则，其存储特点类似于循环队列，是一个单向的数据传输模式，存储模式是在内存中开辟一个大小固定的内存缓冲区，进程之间访问管道是互斥的
半双工通信：同一时间内，只能有一端向另一端发送数据，单管道单方向发送
全双工通信：同一时间内，两端都能互相发送信息，需要建立两条管道

2.4.1 线程概念

线程是一个基本的CPU执行单元，也是程序执行流的最小单位。引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务(如视频、文字聊天、传文件)

2.4.2 用户级线程-多对一模型：

用户通过基于用户态的线程库完成逻辑上的调度，可以使用一个whille循环来不断执行，然后用if处理不同的逻辑代码；优点：用户级别线程切换在用户空间就可以完成，不需要切换到核空间，效率高；缺点：当有一个线程被阻塞，那么整个线程将无法执行，其并发度不高

2.4.3 内核级线程-一对一模型：

其工作方式管理都由操作系统内核完成，相当于多个main函数，对于不同的程序入口，且线程调度、线程切换都在内核完成；优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强；缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。

2.4.4 多线程模型-多对多模型：

克服了多对一模型的并发度不高缺点，如果一个用户态线程被阻塞的话，那么可以映射到其他的内核态线程中执行，又克服了一对一模型的开销太大缺点，并不会向一对一模型那样占用太多的内核态线程

3.1.1 高级调度（作业调度）

3.1.2 低级调度（处理机调度/进程调度）

进程调度是操作系统中最基本的一种调度方式，其核心思想就是从内存的 PCB 队列中选取 PCB 上 CPU 执行，调度频率很高，让用户层面看起来像是很多程序并发运行

3.1.3 中级调度（内存调度）

内存不够时，可将某些进程的数据调出外存，等内存空闲或者进程需要运行时再重新调入内存；如果将某一进程重新调出内存调入外存，那么这些被调出内存的进程的进程状态为挂起状态，挂起状态的 PCB 会被组织称为挂起队列；一个进程可能会被多次调出、调入内存，因此中级调度发生的频率要比高级调度更高。

3.1.4 三者对比

在五状态模型的基础上，加入了就绪挂起和阻塞挂起，这两个状态和其他状态的区别在于，这两种状态都是因为内存空间不足，从内存被调度到外存，等待激活的状态

3.3.1 进程调度的时机

3.3.2 进程调度的切换

进程在普通资源临界区时可以进行处理机调度与切换，操作系统内核程序临界区不能进行调度与切换

• 普通资源临界区：一个时间段内只允许一个进程进行访问，各个进程之间是互斥地
• 内核程序临界区：访问某种内核数据结构的，类似于就绪队列

3.3.3 进程调度的方式

• 非剥夺调度方式（非抢占式），只允许进程主动放弃处理机，不能强迫进程下 CPU，如果有更加紧急的进程要访问 CPU，也只能处于就绪态等待，直到当前进程终止或者主动要求进入阻塞态
• 剥夺调度方式（抢占式），按照时间片原则进行，如果一个进程的时间片到了，会强迫该进程下 CPU，该方式适用于分时操作系统、实时操作系统等

3.3.4 调度器

调度器决定就绪态与运行态之间的状态改变，也就是处理谁上处理机谁下处理机的问题，调度器重要决定让谁运行？以及运行的时间片大小？
调度时机（什么时候调度器会工作）？
（1）创建新进程，就绪队列放生改变，调度器决定是否让进程上 CPU
（2）进程退出，此时 CPU 空闲，会去就绪队列选取新的进程上 CPU
（3）运行程序阻塞，当前在 CPU 工作的进程进入阻塞状态， CPU 空闲，取就绪队列选取新进程
（4）I/O 中断发生，当在阻塞态的进程被唤醒，重新加入就绪队列，那么就绪队列又改变，CPU 重新做决定

作业：作业控制块（JCB，Job Control Block），作业运行的三种状态，后备状态，运行状态与完成状态；后备状态是指作业还存放在外存中，已经建立了JCB，且放在作业后被队列中等待被调度的过程；运行状态是指作业从后备队列被调度进入内存，放在就绪队列中建立TCB等待运行，包括上 CPU 运行到完成的整个过程；完成状态是指作业完成后下CPU的状态。

核心思想：优先考虑在系统中等待时间最长的进程/服务，先来先服务不管运行时间大小

非抢占式SJF
基于当前时间，进程执行完后查看当前已到达的进程，选择运行时间少的进程上CPU

抢占式SJF（最短剩余时间优先）
每当有进程加入就绪队列时就需要调度，几乎每个时间段都会检查有没有新到达的进程所需时间片较小，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要调度

每个进程/作业都有自己的优先级，每次调度都会选择优先级最高的进程上 CPU
静态优先级：创建进程时确定，之后不做改变
动态优先级：创建进程时有初始值，之后会根据情况做修改
优先级设定：
系统进程优先级高于用户进程，前台进程优先级高于后台进程，I/O进程优先级高于计算型进程
*： I/O型进程与CPU并发执行，I/O设备尽早工作可以提高CPU使用率
*： 前台进程面向用户，提高前台进程优先级有利于用户使用体验
*： 系统进程属于管理者范畴，应提高优先级

• 非抢占式优先级调度算法：
  每次调度时选择当前已到达且优先级最高的进程，当前进程主动放弃处理机时发生调度
  
• 抢占式优先级调度算法：
  每次调度时候选择当前已到达且优先级最高的进程，当前进程主动放弃处理机时，或者就绪队列发生改变时发生调度
  

算法规则

1. 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
2. 新进程到达时进入第一队列，按照FCFS原则排队等待分配时间片，如果时间片用完但是进程还未执行结束，则进程进入下一级就绪队列队尾
3. 只有第k级的就绪队列为空时，才会执行第k+1级的就绪队列
4. 如果出现抢占式现象，被抢占的进程会重新进入当前就绪队列的队尾

算法优点

1. FCFS算法的公平性，先到先服务，每个进程一进入就加入第一级别的就绪队列，第一级别优先级最高优先处理
2. SJF算法优点，由于时间片大小由低到高，所以短进程会被比较快的执行
3. 时间片轮转算法优点，各个进程可以及时的得到响应
4. 优先级调度算法优点，可以将I/O型进程阻塞时重新放回该就绪队列而不是放回下一级，保持较高的优先性

---

讯享网

4.2.1 单标识法

算法思想：两个进程在访问完临界资源后，会把对临界区的使用权交给另一个进程，也就是说一个进程对临界区的权限只能由另一个进程赋予

算法优点：同一时刻最多只允许一个进程访问临界区，例如：只有进程 p0 进入临界区使用完资源后，才会把turn设置为1，如果 p0 时间片用完，处理机调度 p1 上处理机，但是 turn 还是为0，进入不了临界资源，那么时间片用完又会轮到 p0 上处理机，只有等待 p0 对临界区访问完成才有 p1 访问临界区的权限

算法缺点：如果进程 A 使用完临界资源，把使用权交给进程 B ，但是进程 B 迟迟不进入临界资源，而此时进程A又需要进入临界资源，而对临界资源的访问权限只能由进程 B 赋予，此时违背“空闲让进”原则

4.2.2 双标志先检查法

算法思想：设置一个bool型数组flag[]，数组每个元素用来表示进程想要进入临界区的意愿，每个进程在访问临界资源之前会检查有没有别的进程想要进入临界区，如果没有就把自身的flag设置为true，开始访问临界区

算法缺点：如果因为时间片用完发生调度现象，导致执行顺序为：1 5 2 6，那么造成两个进程同时想访问临界资源的情况，违反“忙则等待”原则，因为在进入区域的检查和上锁两个行为不是一气呵成的。

4.2.3 双标志后检查法

算法思想：基于双标志先检查法做的改进，将上锁与检查的顺序发生更换

算法缺点：如果因为时间片用完发生调度现象，导致执行顺序为：1 5 2 6，那么导致两个进程都想上处理机，但是由于检查过程中发现对方想上处理机所以自己不上处理机的情况，导致了”空闲让进”和“有限等待原则”，各个进程可能会发生“饥饿”现象

4.2.4 Peterson算法

4.3.1 中断屏蔽算法

4.3.2 TestAndSet指令-TS指令-TSL指令

算法流程：
（1）当一个进程想要获取锁时，它会调用TSL指令，尝试将锁的状态从“未锁定”改为“已锁定”。
（2）如果锁已经被其他进程持有（即状态为“已锁定”），那么TSL指令会返回一个表示锁已被占用的值，当前进程则需要等待（忙等现象），直到锁变为可用。
（3）一旦锁变为可用，TSL指令会成功地将其状态设为“已锁定”，并返回一个表示成功的值给当前进程，此时该进程获得了对共享资源的独占访问权。
（4）当进程完成对共享资源的操作后，它必须释放锁，使其他等待的进程有机会获取锁并访问资源。

4.3.2 Swap指令-Exchange指令-XCHG指令

算法思想：
（1）获取锁 (acquire_lock)：
初始化 old_value 为 0。
调用 swap(&lock, &old_value)，这会原子地将 lock 的值赋给 old_value，并将 old_value 的值（即 0）赋给 lock。
如果 old_value 为 0，说明锁未被占用，当前进程成功获取锁。
如果 old_value 不为 0，说明锁已被其他进程占用，当前进程需要继续循环等待，直到锁变为可用。
（2）释放锁 (release_lock)：
将 lock 置为 0，表示锁已释放，其他等待的进程可以尝试获取锁。

讯享网

4.4.1 整型信号量

4.4.2 记录型信号量

相对于整型信号量，记录型信号量带有等待队列，拥有阻塞功能，在P操作和V操作中带有block自我阻塞函数和wakeup唤醒等待队列函数

讯享网

4.4.3 利用信号量实现进程互斥

实现过程：
（1）划分并发过程中的临界区代码
（2）初始化信号量，定义可以进入临界区的名额
（3）进入区P(mutex)，申请资源
（4）退出区V(mutex)，释放资源
注意：对不同的临界资源需要设置不同的互斥信号量。P、V操作必须成对出现。缺少P(mutex)就不能保证临界资源的互斥访问。缺少 V(mutex)会导致资源永不被释放，等待进程永不被唤醒。

4.4.4 利用信号量实现前驱关系

利用信号量实现进程同步，在前操作之后执行V操作释放资源，在后操作之前执行P操作申请资源
示例如下：在S1操作完成后（前操作完成后），执行V(a)操作释放资源，让信号量+1，在执行S2操作之前（后操作开始之前），执行P(a)操作申请资源，让信号量-1，同时在S1节点，他需要对两个后继执行V(?)操作，以此类推

---

笔记视频源自： bilibili-王道计算机考研-操作系统

---

持续更新中