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

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

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

进程的状态转换使用“原语”实现，原语执行具有“一气呵成”的原子性，示例以下，将PCB2从阻塞态转为就绪态
实现步骤：（1）将PCB2的state设为1（2）将PCB2从阻塞队列放到就绪队列中，执行过程中，不能有中断信号

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

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

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

2.3.1 共享存储

（1）基于数据结构的共享-低级共享，其内存可以是系统分配的一个长度为10的4kb数组，其内存大小是固定的，其灵活性不高，访问速度慢
（2）基于存储区的共享-高级共享，系统没有对具体每次存放空间做限制，只是分配了该内存空间供这两个进程使用，灵活性高，访问速度快

2.3.2 消息传递

（1）直接通信方式
两个进程之间点名道姓的传送信息，进程P发送原语，传输消息，消息头包含进程来源者，进程接收者，以及相关信息，后进入到操作系统内核中，该信息会进入进程Q的PCB的消息队列中，此消息队列都是四面八方发送进程Q的消息

（2）间接通信方式
两个进程之间通过一个中间件也就是信箱来操控信息发送，进程P发送只会发送到邮箱中，当进程Q要去邮箱中获取来自进程P的消息时，邮箱会根据信息头的来源目的进行判断进行消息分配

2.3.3 管道通信

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

2.4.1 线程概念

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

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

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

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

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

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

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

3.1.1 高级调度（作业调度）

作业：一个具体的任务，用户向系统提交一个作业，就是用户让操作系统启动一个程序
由于程序的执行要从外存调入内存，而内存空间是有限的，所以操作系统会按照一定的原则从外存的作业后备队列中挑选一个作业加入内存，为该作业创建对应的进程，也就是创建对应的PCB，作业完成后调出时，PCB会撤销回收。

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

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

3.1.3 中级调度（内存调度）

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

3.1.4 三者对比

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

3.3.1 进程调度的时机

3.3.2 进程调度的切换

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

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

（1）当一个进程访问就绪队列后，会对该就绪队列上锁，霸占资源，还没有退出这个内核程序临界区，但是如果进程调度的相关程序也需要访问该就绪队列，而该就绪队列又被上锁了，那么就无法正常访问，影响到 CPU 正常工作，所以需要让进程迅速的访问完内核程序临界区的资源，尽快释放锁，使得进程调度正常运行
（2）当一个进程访问打印机时，对打印机进行上锁，占用打印机，但是打印机属于一种慢速的 I/O 设备，不会影响内核调度相关程序，所以为了增加系统 CPU 利用率，提高并发度，当进程在访问普通临界区时，允许进程调度和切换。

3.3.3 进程调度的方式

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

3.3.4 调度器

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

非抢占式调度策略：只有运行进程阻塞或退出才触发调度程序工作
抢占式调度策略：每个时钟中断或k个时钟中断会触发调度程序工作

作业：作业控制块（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算法

算法思想：结合单标志法和双标志法，表达自己想访问临界资源的意愿，又会检查对方的意愿，在进入区的行为包括（1.主动争取 2.主动谦让 3.检查对方意愿以及是否自己为最后一个谦让）
算法优缺点：遵循了“空闲让进”，“忙则等待”以及“有限等待”原则

4.3.1 中断屏蔽算法

算法思想：利用“开/关中断指令”实现(与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况)
算法优缺点： 简单、高效；但是不适用于多处理机，只适用于操作系统内核进程，不适用于用户进程(因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险)

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

算法思想：
lock初始值为false，表示该临界资源空闲；进程在进入临界区之前，先调用TS指令测试lock，如果值为false，表示没有进程在临界区内，可以进入，并将lock设置为true，相当于关闭了临界资源，使得任何资源都不能进入临界区，循环测试

算法流程：
（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 整型信号量

资源数目：整型S
原子操作：Wait(S) 和 Signal(S)，也称为 P,V 操作

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-王道计算机考研-操作系统

---

持续更新中