进程、线程、互斥

进程

进程组成与特征

程序与进程

• 程序：是静态的，就是个存放在磁盘里的可执行文件，就是一系列的指令集合
• 进程(Process)：是动态的，是程序的一次执行过程

进程控制块(PCB)：是进程存在的唯一标志，当进程被创建时，操作系统为其创建 PCB，当进程结束时，会回收其 PCB

进程控制块

• 进程描述信息
  • 进程标识符 PID：当进程被创建时，操作系统会为该进程分配一个唯一的、不重复的 "身份证号"
  • 用户标识符 UID：进程所属用户 ID
• 进程控制和管理信息
  • CPU、磁盘、网络流量使用情况统计...
  • 进程当前状态：就绪态/阻塞态/运行态...
• 资源分配清单
  • 正在使用哪些文件
  • 正在使用哪些内存区域
  • 正在使用哪些 I/O 设备
• 处理机相关信息：如 PSW、PC 等等各种寄存器的值（用于实现进程切换）

程序如何运行

进程组成

• 进程控制块(PCB)
• 程序段：程序的代码（指令序列）
• 数据段：运行过程中产生的各种数据（如：程序中定义的变量）

总结：

• 程序段、数据段、PCB 三个部分组成了进程实体（进程映像）
• 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位

进程特征

程序是静态的，进程是动态的，相比较于程序，进程拥有以下特征：

• 动态性：进程是程序的一次执行过程，是动态地产生、变化和消亡的
• 并发性：内存中有多个进程实体，各进程可并发执行
• 独立性：进程是能独立运行、独立获得资源、独立接受调度的基本单位
• 异步性：各进程按各自独立的、不可预知的速度向前推进，操作系统要提供"进程同步机制"来解决异步问题
• 结构性：每个进程都会配置一个 PCB。结构上看，进程由程序段、数据段、PCB 组成

进程状态转换

三种基本状态

• 运行态(Running)：占有 CPU，并在 CPU 上运行
• 就绪态(Ready)：已经具备运行条件，但由于没有空间 CPU，而暂时不能运行
• 阻塞态(Waiting/Blocked，又称：等待态)：因等地啊某一事件而暂时不能运行

另外两种状态

• 创建态(New，又称：新建态)：进程正在被创建，操作系统为进程分配资源，初始化 PCB
• 终止态(Terminated，又称：结束态)：进程正在从系统中撤销，操作系统会回收进程拥有的资源、撤销 PCB

进程状态间转换

• 就绪态->运行态：进程被调度
• 运行态->就绪态：时间片到，或 CPU 被其他高优先级的进程抢占
• 运行态->阻塞态：等待系统资源分配，或等待某件事情发生（主动行为）
• 阻塞态->就绪态：资源分配到位，等待的事情发生（被动行为）

进程组织

• 链接方式

  • 按照进程的状态将 PCB 分为多个队列
  • 操作系统持有指向各个队列的指针

  

• 索引方式

  • 根据进程状态的不同，建立几张索引表
  • 操作系统持有指向各个索引表的指针

  

进程控制

进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能

• 进程控制就是要实现进程状态转换

如何实现进程控制？

• 用原语实现，原语具有"原子性"，一气呵成。如果不能一气呵成，就有可能导致系统中的某些关键数据结构信息不统一，进而影响操作系统进行别的管理工作

如何实现原语"原子性"

• 用"关中断指令"和"开中断指令"这两个特权指令实现原子性

进程的创建

• 创建原语
  • 申请空白 PCB
  • 为新进程分配所需资源
  • 初始化 PCB
  • 将 PCB 插入就绪队列
• 引起进程创建的事件
  • 用户登录：分时系统中，用户登录成功，系统会为其建立一个新的进程
  • 作业调度：多道批处理系统中，有新的作业放入内存时，会为其建立一个新的进程
  • 提供服务：用户向操作系统提出某些请求时，会新建一个进程处理该请求
  • 应用请求：由用户进程主动请求创建一个子进程

进程的终止

• 撤销原语
  • 从 PCB 集合中找到终止进程的 PCB
  • 若进程正在运行，立即剥夺 CPU，将 CPU 分配给其他进程
  • 终止其所有子进程
  • 将该进程拥有的所有资源归还给父进程或操作系统
  • 删除 PCB
• 引起进程终止的事件
  • 正常结束：进程自已请求终止(exit 系统调用)
  • 异常结束：整数除以0、非法使用特权指令，然后被操作系统强行杀掉
  • 外界干预：Ctrl+Alt+delete，用户选择杀掉进程

进程的阻塞和唤醒

• 进程的阻塞
  • 阻塞原语
    • 找到要阻塞的进程对应的 PCB
    • 保护进程运行现场，将 PCB 状态信息设置为“阻塞态"，暂时停止进程运行
    • 将 PCB 插入相应事件的等待队列
  • 引起进程阻塞的事件
    • 需要等待系统分配某种资源
    • 需要等待相互合作的其他进程完成工作
• 进程的唤醒
  • 唤醒原语
    • 在事件等待队列中找到 PCB
    • 将 PCB 从等待队列移除，设置进程为就绪态
    • 将 PCB 插入就绪队列，等待被调度
  • 引起进程唤醒的事件
    • 等待的事情发生

进程的切换

• 切换原语
  • 将运行环境信息存入 PCB
  • PCB 移入相应队列
  • 选择另一个进程执行，并更新其 PCB
  • 根据 PCB 恢复新进程所需的运行环境
• 引起进程切换的事件
  • 当前进程时间片到
  • 有更高优先级的进程到达
  • 当前进程主动阻塞
  • 当前进程终止

进程通信

进程间通信(Inter-Process Communication，IPC)是指两个进程之间产生数据交互

进程是分配系统资源的单位(包括内存地址空间)，因此各进程拥有的内存地址空间相互独立

• 为了保证安全，一个进程不能直接访问另一个进程的地址空间。

进程通信

• 共享存储

  • 基于数据结构的共享：比如共享空间里只能放一个长度为10的数组。这种共享方式速度慢、限制多，是一种低级通信方式
  • 基于存储区的共享：操作系统在内存中划出一块共享存储区，数据的形式、存放位置都由通信进程控制，而不是操作系统。这种共享方式速度很快，是一种高级通信方式

  

• 消息传递

  进程间的数据交换以格式化的消息(Message)为单位。进程通过操作系统提供的"发送消息/接收消息"两个原语进行数据交换

  • 直接通信方式：消息发送进程要指明接收进程的 ID

    

  • 间接通信方式：通过"信箱"间接地通信。因此又称"信箱通信方式"

    

• 管道通信

  

写进程往管道写数据，即便管道没被写满，只要管道没空，读进程就可以从管道读数据

读进程从管道读数据，即便管道没被读空，只要管道没满，写进程就可以往管道写数据

线程

线程概念

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

• 资源分配、调度
  • 传统进程机制中，进程是资源分配、调度的基本单位
  • 引入线程后，进程是资源分配的基本单位，线程是调度的基本单位
• 并发性
  • 传统进程机制中，只能进程间并发
  • 引入线程后，各线程间也能并发，提升了并发度
  • 传统的进程间并发，需要切换进程的运行环境，系统开销很大
• 系统开销
  • 线程间并发，如果是同一进程内的线程切换，则不需要切换进程环境，系统开销小
  • 引入线程后，并发所带来的系统开销减小

线程的属性

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

多线程模型

线程的实现方式

• 用户级线程（User-Level Thread，ULT）

  1. 用户级线程由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责(包括线程切换)
  2. 用户级线程中，线程切换可以在用户态下即可完成，无需操作系统干预
  3. 在用户看来，是有多个线程。但是在操作系统内核看来，并意识不到线程的存在。"用户级线程"就是"从用户视角看能看到的线程"

  优缺点：

  • 优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
  • 缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行

  

• 内核级线程（Kenel-Level Thread，KLT，又称：内核支持的线程）

  1. 内核级线程的管理工作由操作系统内核完成
  2. 线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成
  3. 操作系统会为每个内核级线程建立相应的 TCB(ThreadControlBlock，线程控制块)，通过TCB对线程进行管理。"内核级线程"就是"从操作系统内核视角看能看到的线程"

  优缺点

  • 优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行
  • 缺点：一个用户进程会占用多个内核级线程线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大

  

多线程模型

• 一对一模型

  一个用户级线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程

  • 优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行
  • 缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大

• 多对一模型

  多个用户级线程映射到一个内核级线程。且一个进程只被分配一个内核级线程

  • 优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
  • 缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行

• 多对多模型

  n 用户及线程映射到 m 个内核级线程(n>=m)。每个用户进程对应 m 个内核级线程

  克服了多对一模型并发度不高的缺点(一个阻塞全体阻塞)，又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点

  

线程状态转换

状态转换

线程的组织与控制

调度

调度概念

调度：按某种算法选择一个进程将处理机分配给它

调度三个层次

	要做什么	调度发生在	发生频率	对进程状态的影响
高级调度(作业调度)	按照某种规则，从后备队列中选择合适的作业将其调度内存，并为其创建进程	外存->内存(面向作业)	最低	无->创建态->就绪态
中级调度(内存调度)	按照某种规则，从挂起队列中选择合适的进程将其数据调回内存	外存->内存(面向过程)	中等	挂起态->就绪态
低级调度(进程调度)	按照某种规则，从就绪队列中选择一个进程为其分配处理机	内存->CPU	最高	就绪态->运行态

挂起状态与七状态模型

进程调度时机

进程调度(低级调度)，就是按照某种算法从就绪队列中选择一个进程为其分配处理机

进程在操作系统内核程序临界区中不能进行调度与切换√

(2012年联考真题)进程处于临界区时不能进行处理机调度×

• 临界资源：一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源
• 临界区：访问临界资源的那段代码

内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列(由各就绪进程的PCB组成)

进程调度的方式

• 非剥夺调度方式，又称非抢占方式。即，只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态
• 剥夺调度方式，又称抢占方式。当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程

"狭义的调度"与"进程切换"的区别

• 狭义：从就绪队列中选中一个要运行的进程（这个进程可以时刚刚被暂停执行的进程，也可能是另一个进程，后一种情况就需要进程切换）
• 广义：包含了选择一个进程和进程切换两个步骤

进程切换的过程主要完成了：

1. 对原来运行进程各种数据的保存
2. 对新的进程各种数据的恢复

注意：进程切换是有代价的，因此如果过于频繁的进行进程调度、切换，必然会使整个系统的效率降低，使系统大部分时间都花在了进程切换上，而真正用于执行进程的时间减少

调度器

2、3 由调度程序引起，调度程序决定：

• 让谁运行？————调度算法
• 运行多长时间？————时间片大小

调度时机————什么事情会触发"调度程序"？

• 创建新进程
• 进程退出
• 进行进程阻塞
• I/O 中断发生

调度程序永远的备胎，没有其他就绪进程时，运行闲逛进程(idle)

调度算法1

调度算法评价指标

• CPU 利用率：CPU 忙碌时间占总时间的比例

  CPU利用率=CPU忙碌的时间/总时间

• 系统吞吐量：单位时间内完成作业的数量

  系统吞吐量=总共完成了多少道作业/总共花了多少时间

• 周转时间：从作业被提交给系统开始，到作业完成为止的这段时间间隔

  • 周转时间、平均周转时间

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

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

  • 带权周转时间、平均带权周转时间

    带权周转时间=作业周转时间/作业实际运行的时间

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

• 等待时间：指进程/作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低

  对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待 I/O 完成的期间其实进程也是在被服务的，所以不计入等待时间

  对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间

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

调度算法

• 先来先服务（FCFS, First Come First Serve）
• 短作业优先（SJF, Shortest Job First）
• 高响应比优先（HRRN）

先来先服务

• 算法思想：主要从"公平"的角度考虑(类似于我们生活中排队买东西的例子)
• 算法规则：按照作业/进程到达的先后顺序进行服务
• 作业调度还是进程调度：用于作业调度时，考虑的是哪个作业先到达后备队列;用于进程调度时，考虑的是哪个进程先到达就绪队列
• 是否可抢占：非抢占式的算法
• 优缺点：
  • 优点：公平、算法实现简单
  • 缺点：排在长作业(进程)后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。即：FCFS算法对长作业有利，对短作业不利
• 是否会导致饥饿(某进程/作业长期得不到服务)：不会

短作业优先

• 算法思想：追求最少的平均等待时间，最少的平均周转时间、最少的平均平均带权周转时间
• 算法规则：最短的作业/进程优先得到服务(所谓"最短"，是指要求服务时间最短)
• 作业调度还是进程调度：即可用于作业调度，也可用于进程调度。用于进程调度时称为"短进程优先"算法
• 是否可抢占：SJF 和 SPF 是非抢占式的算法。但是也有抢占式的版本————最短剩余时间优先算法(SRTN, Shortest Remaining Time Next)
• 优缺点：
  • 优点："最短的"平均等待时间、平均周转时间
  • 缺点：不公平。对短作业有利，对长作业不利。可能产生饥饿现象。另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先
• 是否会导致饥饿(某进程/作业长期得不到服务)：会。如果源源不断地有短作业/进程到来，可能使长作业/进程长时间得不到服务，产生"饥饿"现象。如果一直得不到服务，则称为"饿死"

最短剩余时间优先算法

高响应比优先

• 算法思想：要综合考虑作业/进程的等待时间和要求服务的时间
• 算法规则：在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务
• 作业调度还是进程调度：即可用于作业调度，也可用于进程调度
• 是否可抢占：非抢占式的算法。因此只有当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比
• 优缺点：
  • 综合考虑了等待时间和运行时间(要求服务时间)
  • 等待时间相同时，要求服务时间短的优先(SIF 的优点)
  • 要求服务时间相同时，等待时间长的优先(FCFS 的优点)
  • 对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题
• 是否会导致饥饿(某进程/作业长期得不到服务)：不会

调度算法2

• 时间片轮转(RR, Round-Robin)
• 优先级调度算法
• 多级反馈队列调度算法

时间片轮转调度算法

• 算法思想：公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应
• 算法规则：按照各进程到达就绪队列的顺序，轮流让各个进程执行个时间片(如 100ms)。若进程未在一个时间片内执行完则剥夺处理机，将进程重新放到就绪队列队尾重新排队
• 作业调度还是进程调度：用于进程调度(只有作业放入内存建立了相应的进程后，才能被分配处理机时间片)
• 是否可抢占：若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知 CPU 时间片已到
• 优缺点：
  • 优点：公平；响应快，适用于分时操作系统
  • 缺点：由于高频率的进程切换，因此有一定开销；不区分任务的紧急程度。
• 是否会导致饥饿(某进程/作业长期得不到服务)：不会

补充：

• 如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大
• 另一方面，进程调度、切换是有时间代价的(保存、恢复运行环境)，因此如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。可见时间片也不能太小

优先级调度算法

• 算法思想：随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序
• 算法规则：每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程
• 作业调度还是进程调度：既可用于作业调度，也可用于进程调度。甚至，还会用于在之后会学习的 I/O 调度中
• 是否可抢占：抢占式、非抢占式都有。做题时的区别在于:非抢占式只需在进程主动放弃处理机时进行调度即可，而抢占式还需在就绪队列变化时，检查是否会发生抢占
• 优缺点：
  • 优点：用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度
  • 缺点：若源源不断地有高优先级进程到来，则可能导致饥饿
• 是否会导致饥饿(某进程/作业长期得不到服务)：会

补充：

• 就绪队列未必只有一个，可以按照不同优先级来组织。另外，也可以把优先级高的进程排在更靠近队头的位置
• 根据优先级是否可以动态改变，可将优先级分为静态优先级和动态优先级两种
  • 静态优先级：创建进程时确定，之后一直不变
  • 动态优先级：创建进程时有一个初始值，之后会根据情况动态地调整优先级

操作系统更偏好 I/O 型进程。I/O 设备和 CPU 可以并行工作。如果优先让 I/O 繁忙型进程优先运行的话则越有可能让 I/O 设备尽早地投入工作，则资源利用率、系统吞吐量都会得到提升

多级反馈队列调度算法

• 算法思想：对其他调度算法的折中权衡
• 算法规则：
  1. 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
  2. 新进程到达时先进入第1级队列，按 FCFS 原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾
  3. 只有第k级队列为空时，才会为k+1级队头的进程分配时间片
• 作业调度还是进程调度：用于进程调度
• 是否可抢占：抢占式的算法。在k级队列的进程运行过程中，若更上级的队列(1~k-1级)中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列队尾
• 优缺点：
  • 对各类型进程相对公平(FCFS的优点)
  • 每个新到达的进程都可以很快就得到响应(RR的优点)
  • 短进程只用较少的时间就可完成(SPF的优点)
  • 不必实现估计进程的运行时间(避免用户作假)
  • 可灵活地调整对各类进程的偏好程度，比如 CPU 密集型进程、I/O 密集型进程(拓展：可以将因 I/O 而阻塞的进程重新放回原队列，这样 I/O 型进程就可以保持较高优先级)
• 是否会导致饥饿(某进程/作业长期得不到服务)：会

系统进程(如内存管理进程)队列采用优先级调度

交互式(如：游戏、打字软件)队列采用RR

批处理(如：AI模型训练、视频特效渲染)队列采用FCFS

同步、互斥

同步互斥概念

进程同步：指为了完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调他们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

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

两种资源共享方式：

• 互斥共享方式：系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源
• 同时共享方式：系统中的某些资源，允许一个时间段内由多个进程"同时"对它们进行访间

我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备(比如摄像头、打印机)都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源

对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源

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

互斥访问，需要遵循原则：

1. 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
2. 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待
3. 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区(保证不会饥饿)
4. 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待

进程互斥软件实现

• 单标志法

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

  int turn = 0; // turn 表示当前允许进入临界区的进程号
  // p0进程
  while (turn != 0); // 进入区
  critical section;  // 临界区
  turn = 1;          // 退出区
  remainder section; // 剩余区
  // p1进程
  while (turn != 1);
  critical section;
  turn = 0;
  remainder section;

  只能按 PO→P1→PO→P1→… 这样轮流访问。这种必须"轮流访问"带来的问题是，如果此时允许进入临界区的进程是 P0，而 P0 一直不访问临界区，那么虽然此时临界区空闲，但是并不允许 P1 访问

  主要问题是：违背"空闲让进"原则

• 双标志检查

  • 算法思想：设置一个布尔型数组 flag，数组中各个元素用来标记各进程想进入临界区的意愿，比如 "flag[0]=true" 意味着 0 号进程 PO 现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志 flag[i] 设为 true，之后开始访问临界区

  bool flag[2] = { false, false }; // 表示进入临界区意愿的数组
  // p0进程
  while (flag[1]);
  flag[0] = true;
  critical section;
  flag[0] = false;
  remainder section;
  // p1进程
  while (flag[0]);  // 如果此时P0想进入临界区，P1就一直循环等待
  flag[0] = true;   // 标记为P1进程想要进入临界区
  critical section; // 访问临界区
  flag[1] = false;  // 访问完临界区，修改标记为P1不想使用临界区
  remainder section;

  主要问题是：违反"忙则等待"原则

• 双标志后检查

  • 算法思想：双标志先检查法的改版。前一个算法的问题是先"检查"后"上锁"，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先"上锁"后"检查"的方法，来避免上述问题

  bool flag[2] = { false, false };
  // p0进程
  flag[0] = true;
  while (flag[1]);
  critical section;
  flag[0] = false;
  remainder section;
  // p1进程
  flag[0] = true;   // 标记为P1进程池想要进入临界区
  while (flag[0]);  // 如果P0也想进入临界区，则P1循环等待
  critical section; // 访问临界区
  flag[1] = false;  // 访问完临界区，修改标记为P1不想使用临界区
  remainder section;

  因此，双标志后检查法虽然解决了"忙则等待"的问题，但是又违背了"空闲让进"和"有限等待"原则，会因各进程都长期无法访问临界资源而产生"饥饿"现象

• Peterson 算法

  • 算法思想：结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试"孔融让梨"(谦让)。做一个有礼貌的进程

  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;

  Peterson 算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待 三个原则，但是依然未遵循让权等待的原则

进程互斥硬件实现方法

• 中断屏蔽方法

  • 利用"开/关中断指令"实现(与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况)

  优缺点：

  • 优点：简单、高效
  • 缺点：不适用于多处理机；只适用于操作系统内核进程，不适用于用户进程(因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险)

• TestAndSet 指令

  • 简称 TS 指令，也有地方称为 TestAndsetLock 指令，或 TSL 指令 TSL 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成

  // true表示已经上锁
  bool TestAndSet(bool *lock) {
    bool old;
    old = *lock;
    *lock = true;
    return old;
  }
  
  // 以下是使用TSL指令实现互斥的算法逻辑
  while (TestAndSet (&lock));//上锁并检查
  // 临界区代码段...
  lock = false; //解锁

  优缺点：

  • 优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境
  • 缺点:不满足"让权等待"原则，暂时无法进入临界区的进程会占用 CPU 并循环执行 TSL 指令，从而导致"忙等"

• Swap 指令

  • 有的地方也叫 Exchange 指令，或简称 XCHG 指令。Swap 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成

  //true表示已经上锁
  void Swap(bool *a,bool *b) {
    bool temp;
    temp = *a;
    *a = *b;
    *b = temp;
  }
  
  //以下是使用Swap指令实现互斥的算法逻辑
  bool old=true;
  while (old=true)
    Swap(&lock,&old);
  // 临界区代码段
  lock=false; //解锁
  // 剩余代码段

  优缺点：

  • 优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环
  • 缺点：不满足"让权等待"原则，暂时无法进入临界区的进程会占用 CPU 并循环执行 TSL 指令，从而导致"忙等"

进程互斥:锁

互斥锁

解决临界区最简单的工具就是互斥锁(mutexlock)。一个进程在进入临界区时应获得锁:在退出临界区时释放锁。函数 acquire() 获得锁，而函数 release() 释放锁

每个互斥锁有一个布尔变量 available，表示锁是否可用。如果锁是可用的，调用 acquire() 会成功，且锁不再可用。当一个进程试图获取不可用的锁时，会被阻塞，直到锁被释放

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

acquire() 或 release() 的执行必须是原子操作，因此互斥锁通常采用硬件机制来实现

互斥锁的主要缺点是忙等待，当有一个进程在临界区中，任何其他进程在进入临界区时必须连续循环调用 acquire()。当多个进程共享同一 CPU 时，就浪费了 CPU 周期。因此，互斥锁通常用于多处理器系统，一个线程可以在一个处理器上等待，不影响其他线程的执行

需要连续循环忙等的互斥锁，都可称为自旋锁(spinlock)，如TSL指令、swap指令、单标志法

特性：

• 需忙等，进程时间片用完才下处理机，违反"让权等待"
• 优点：等待期间不用切换进程上下文，多处理器系统中，若上锁的时间短，则等待代价很低
• 常用于多处理器系统，一个核忙等，其他核照常工作，并快速释放临界区
• 不太适用于单处理机系统，忙等的过程中不可能解锁

信号量机制

进程互斥的四种软件实现方式(单标志法、双标志先检查、双标志后检查、Peterson算法)

进程互斥的三种硬件实现方式(中断屏蔽方法、TS/TSL指令、Swap/XCHG指令)

1. 在双标志先检查法中，进入区的"检查"、"上锁"操作无法一气呵成，从而导致了两个进程有可能同时进入临界区的问题
2. 所有的解决方案都无法实现"让权等待"

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

信号量机制

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

• 信号量其实就是一个变量(可以是一个整数，也可以是更复杂的记录型变量)，可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为1的信号量
• 原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由"进入区的各种操作无法一气呵成"，因此如果能把进入区、退出区的操作都用"原语"实现，使这些操作能"一气呵成"就能避免问题

一对原语：wait(S)原语和 signal(s)原语，可以把原语理解为我们自己写的函数，函数名分别为 wait和 signal，括号里的信号量S其实就是函数调用时传入的一个参数

wait、signal 原语常简称为P、V操作(来自荷兰语 proberen和 verhogen)。因此，做题的时候常把wait(s)、signal(s)两个操作分别写为 P(S)、V(S)

整型信号量

用一个整数型的变量作为信号量，用来表示系统中某种资源的数量

存在问题：不满足"让权等待"原则，会发生"忙等"

int S = 1;
void wait(int S) {    // wait原语，相当于：进入区
  while (S <= 0);     // 如果资源数不够，就意志循环等待
  S = S - 1;          // 如果资源数够，则占用一个资源
}

void signal(int S) {  // signal原语，相当于"退出区"
  S = S + 1;          // 使用完资源后，在退出区释放资源
}

记录型信号量

整型信号量的缺陷是存在"忙等"问题，因此人们又提出了"记录型信号量"，即用记录型数据结构表示的信号量

// 记录型信号量的定义
typedef struct{
  int value;         // 剩余资源数
  struct process *L; // 等待队列
} semaphore;
// 某进程需要使用资源时，通过wait原语申请
void wait (semaphore S){
  S.value--;
  if (S.value < 0) {
    block (S.L); // 将该进程加入到消息队列中
  }
}
// 进程使用完资源后，通过signal原语释放
void signal (semaphore S){
  S.value++;
  if (S.valie <= 0) {
    wakeup(S.L);
  }
}

生产者——消费者问题

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用(注：这里的"产品"理解为某种数据)

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

• 只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待(缓冲区没满->生产者生产)
• 只有缓冲区不空时，消费者才能从中取出产品，否则必须等待(缓冲区没空->消费者消费)

缓冲区是临界资源，各进程必须互斥地访问

多生产者——多消费者问题

如果缓冲区大小为 1，那么有可能不需要设置互斥信号量就可以实现互斥访问缓冲区

吸烟者问题

解决"可以让生产多个产品的单生产者"问题提供一个思路

读者写者问题

1. 允许多个读者同时对文件执行读操作
2. 只允许一个写者往文件中写信息
3. 任一写者在完成写操作之前不允许其他读者或写者工作
4. 写者执行写操作前，应让已有的读者和写者全部退出

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);    // 第一个读进程的读进程数+1
    count++;	  // 访问文件的读进程数+1
    V(mutex);	
    V(w);
    读文件...
      P(mutex);	// 各读进程互斥访问count
    count--;	  // 访问文件的读进程数-1
    if(count==0)
      V(rw);	  // 最后一个读进程负责"解锁"
    V(mutex);
  }
}

哲学家进餐问题

五个人，必须拿左右的筷子才能吃饭。避免死锁发生

解决方案：

1. 可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐，这样可以保证至少有一个哲学家是可以拿到左右两只筷子的
2. 要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一只后再等待另一只的情况
3. 仅当一个哲学家左右两只筷子都可用时才允许他抓起筷子

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]);
    // 思考...
  }
}

管程

管程是一种特殊的软件模块，有这些部分组成：

1. 局部于管程的共享数据结构说明
2. 对该数据结构进行操作的一组过程
3. 对局部于管程的共享数据设置初始值的语句
4. 管程有一个名字

管程的基本特征:

1. 局部于管程的数据只能被局部于管程的过程所访问
2. 一个进程只有通过调用管程内的过程才能进入管程访问共享数据
3. 每次仅允许一个进程在管程内执行某个内部过程

monitor producerconsumer
  condition full,empty;  // 条件变量用来实现同步(排队)
int count = 0;           // 缓冲区的产品数
void insert(Item 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;
  }
}

引入管程的目的无非就是要更方便地实现进程互斥和同步

1. 需要在管程中定义共享数据(如生产者消费者问题的缓冲区)
2. 需要在管程中定义用于访问这些共享数据的"入口"--其实就是一些函数(如生产者消费者问题中，可以定义一个函数用于将产品放入缓冲区，再定义一个函数用于从缓冲区取出产品)
3. 只有通过这些特定的"入口"才能访问共享数据
4. 管程中有很多"入口"，但是每次只能开放其中一个"入口"，并且只能让一个进程或线程进入(如生产者消费者问题中，各进程需要互斥地访问共享缓冲区。管程的这种特性即可证个时间段内最多只会有一个进程在访问缓冲区。注意:这种互斥特性是由编译器负责实现的，程序员不用关心)
5. 可在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量上等待(此时，该进程应先释放管程的使用权，也就是让出"入口")；可以通过唤醒操作将 等待在条件变量上的进程或线程唤醒。

死锁

死锁概念

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

饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象。比如：在短进程优先(SPF)算法中，若有源源不断的短进程到来，则长进程将一直得不到处理机，从而发生长进程"饥饿"

死循环：某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑 bug 导致的，有时是程序员故意设计的

死锁产生的必要条件

• 互斥条件：多个进程争抢资源才会发生死锁
• 不剥夺条件：进程所获得的资源在未使用完之前，不能由其它进程强行抢夺走，只能主动释放
• 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放
• 循环等待条件：存在一种进程资源的循环等待链。链中的每一个进程已获得的资源同时被下一个进程所请求

什么时候会发生死锁

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

死锁的处理策略

• 预防死锁。破坏死锁产生的四个必要条件中的一个或几个
• 避免死锁。用某种方法防止系统进入不安全状态，从而避免死锁(银行家算法)
• 死锁的检测和解除。允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁

处理策略——预防死锁

1. 不允许死锁发生

   • 静态策略：预防死锁
     • 破坏互斥条件
     • 破坏不剥夺条件
     • 破坏请求和保持条
     • 破坏循环等待条件
   • 动态检测：避免死锁

2. 允许死锁发生

   • 死锁的检测和解除

破坏互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁

• 如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。比如：SPOOLing 技术。操作系统可以采用 SPOOLing 技术把独占设备在逻辑上改造成共享设备
• 缺点：可行性不高，很多时候无法破坏互斥条件

不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放

破坏不剥夺条件：

• 方案一:当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件
• 方案二:当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级(比如：剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用)
• 缺点：实现复杂；剥夺资源可能导致部分工作失效；反复申请和释放导致资源开销大；可能导致饥饿

破坏请求和保持条件：

• 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放
• 可以采用静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了
• 缺点：资源利用率低；可能导致饥饿

循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求

• 可采用顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源(即编号相同的资源)一次申请完
• 缺点：不方便增加新设备；会导致资源浪费；用户编程麻烦

处理策略——避免死锁

1. 不允许死锁发生
   • 静态策略：预防死锁
   • 动态检测：避免死锁
     • 什么是安全序列
     • 什么是系统的不安全状态，与死锁有何联系
     • 如何避免进入不安全状态——银行家算法
2. 允许死锁发生
   • 死锁的检测和解除

安全序列：就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个

如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。当然，如果有进程提前归还了一些资源，那系统也有可能重新回到安全状态，不过我们在分配资源之前总是要考虑到最坏的情况。

如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁(处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态)

因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。这也是"银行家算法"的核心思想

银行家算法

银行家算法是荷兰学者 Dijkstra 为银行系统设计的，以确保银行在发放现金贷款时，不会发生不能满足所有客户需要的情况。后来该算法被用在操作系统中，用于避免死锁

核心思想：在进程提出资源申请时，先预判此次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待

处理策略——检测和解除

如果系统中既不采取预防死锁的措施，也不采取避免死锁的措施，系统就很可能发生死锁。在这种情况下，系统应当提供两个算法:

1. 死锁检测算法：用于检测系统状态，以确定系统中是否发生了死锁
2. 死锁解除算法：当认定系统中已经发生了死锁，利用该算法可将系统从死锁状态中解脱出来