操作系统-进程和线程

¶简介

操作系统系列其二，主要是针对中国大陆考研所要求的内容对操作系统的知识体系进行总结和梳理，对于重点内容会使用黑体加粗，本篇内容主要包含以下几点：

• 进程与线程的概念
• CPU调度
  • 经典调度算法
• 同步与互斥
  • 信号量
  • 经典同步问题
• 死锁

¶大纲

¶进程与线程

¶进程的概念

在多道程序环境下，允许多个程序并发执行，此时它们将失去封闭性，并具有间断性及不可再现性的特征。为此引入了进程（Process）的概念，以便更好地描述和控制程序的并发执行，实现操作系统的并发性和共享性（最基本的两个特性）
为了使参与并发执行的每个程序（含数据）都能独立地运行，必须为之配置一个专门的数据结构，称为进程控制块（Process Control Block, PCB）
系统利用 PCB 来描述进程的基本情况和运行状态，进而控制和管理进程，PCB是进程存在的唯一标志。相应地，由程序段、相关数据段和 PCB 三部分构成了进程实体（又称进程映像）
所谓创建进程，实质上是创建进程实体中的PCB，而撤销进程，实质上是撤销进程的PCB。值得注意的是，进程映像是静态的，进程则是动态的。

¶进程的状态与转换

进程在其生命周期内，由于系统中各进程之间的相互制约及系统的运行环境的变化，使得进程的状态也在不断地发生变化。通常进程有以下5种状态，前3种是进程的基本状态。

• 运行态。进程正在处理机上运行。在单处理机中，每个时刻只有一个进程处于运行态。
• 就绪态。进程获得了除处理机外的一切所需资源，一旦得到处理机，便可立即运行。系统中处于就绪状态的进程可能有多个，通常将它们排成一个队列，称为就绪队列。
• 阻塞态，又称等待态。进程正在等待某一事件而暂停运行。即使处理机空闲，该进程也不能运行。系统通常将处于阻塞态的进程也排成一个队列，甚至根据阻塞原因的不同，设置多个阻塞队列。
• 创建态。进程正在被创建，尚未转到就绪态。创建进程需要多个步骤，如果进程所需的资源尚不能得到满足，如内存不足，则创建工作尚未完成，进程此时所处的状态称为创建态。
• 终止态。进程正从系统中消失，可能是进程正常结束或其他原因退出运行。进程需要结束运行时，系统首先将该进程置为终止态，然后进一步处理资源释放和回收等工作。

注意区别就绪态和等待态：就绪态是指进程仅缺少处理器，只要获得处理机资源就立即运行；而等待态是指进程需要其他资源（除了处理机）或等待某一事件。

• 进程的五态图

需要注意的是，一个进程从运行态变成阻塞态是主动的行为，而从阻塞态变成就绪态是被动的行为，需要其他相关进程的协助。

¶进程组成

1. PCB
   • 进程创建时，操作系统为它新建一个PCB，该（数据）结构之后常驻内存，任意时刻都可以存取，并在进程结束时删除。PCB是进程实体的一部分，是进程存在的唯一标志。
   • 进程执行时，系统通过其PCB了解进程的现行状态信息，以便操作系统对其进行控制和管理；进程结束时，系统收回其PCB，该进程随之消亡。
2. 程序段
3. 数据段

¶进程控制

进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销己有进程、实现进程状态转换等功能。
在操作系统中，一般把进程控制用的程序段称为原语，原语的特点是执行期间不允许中断，它是一个不可分割的基本单位。
控制原语所作的事：

1. 更新PCB中的信息
2. 将PCB插入合适的队列
3. 分配、回收资源

¶进程通信

1. 共享存储
   在通信的进程之间存在一块可直接访问的共享空间，通过对这片共享空间进行写/读操作实现进程之间的信息交换。在对共享空间进行写/读操作时，需要使用同步互斥工具（如P操作、V操作），对共享空间的写/读进行控制。
   注意，进程空间一般都是独立的，进程运行期间一般不能访问其他进程的空间，想让两个进程共享空间，必须通过特殊的系统调用实现，而进程内的线程是自然共享进程空间的。
   

2. 信息传递
   在消息传递系统中，进程间的数据交换以格式化的消息 (Message) 为单位。
   进程通过系统提供的发送消息和接收消息两个原语进行数据交换。

   1. 直接通信方式。发送进程直接把消息发送给接收进程，并将它挂在接收进程的消息缓队列上，接收进程从消息缓冲队列中取得消息
   2. 间接通信方式。发送进程把消息发送到某个中间实体，接收进程从中间实体取得消息。这种中间实体一般称为信箱。该通信方式广泛应用于计算机网络中。

   简单理解就是，甲要告诉乙某些事情，就要写信，然后通过邮差送给乙。直接通信就是邮差把信直接送到乙的手上；间接通信就是乙家门口有一个邮箱，邮差把信放到邮箱里。

   

3. 管道通信
   管道通信允许两个进程按生产者一消费者方式进行通信，生产者向管道的一端写，消费者从管道的另一端读。数据在管道中是先进先出的。

   注意：从管道读数据是一次性操作，数据一旦被读取，就释放空间以便写更多数据。普通管道只允许单向通信，若要实现父子进程双向通信，则需要定义两个管道

¶线程和多线程模型

¶线程基本概念

引入进程的目的是更好地使多道程序并发执行，提高资源利用率和系统吞吐量；
而引入线程的目的则是减小程序在并发执行时所付出的时空开销，提高操作系统的并发性能。

线程最直接的理解就是“轻量级进程”，它是一个基本的 CPU 执行单元也是程序执行流的最小单位。

引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务引入线程后，进程只作为除CPU之外的系统资源的分配单元（如打印机、内地址空间等都是分配给进程的）。线程则作为处理机的分配单元。

¶引入线程后的变化

1. 资源分配、调度
   • 传统进程机制中，进程是资源分配、调度的基本单位
   • 引入线程后，线程是资源分配的基本单位、进程是调度的基本单位
2. 并发性
   • 传统进程机制中，只能进程间并发
   • 引入线程后，线程间也能并发
3. 系统开销
   • 传统进程机制中，并发需要切换进程的运行环境，系统开销大
   • 引入线程后，线程间并发，如果是在同一进程内的线程切换，不需要切换运行环境，系统开销小

¶线程的属性

• 每个内核级线程都有一个线程ID、线程控制块（TCB）
• 线程也有就绪、阻塞、运行三种基本状态
• 线程几乎不拥有系统资源，同一进程的不同线程共享进程的资源
• 同一进程内的线程切换，不会引起进程切换；不同进程内的线程切换，会引起进程切换

¶线程的实现方式

线程的实现分为两类：用户级线程和内核级线程

1. 用户级线程
   • 用户级线程由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责（包括线程切换）
   • 线程的切换在用户态下即可完成，不需要系统干预
   • 用户级线程就是从用户视角能看到的线程，操作系统内核意识不到线程的存在
2. 内核级线程
   • 内核级线程的管理工作由操作系统内核完成，线程的调度、切换都由内核完成，所有内核级线程的切换必然需要在核心态下完成
   • 操作系统会为每个内核级线程建立相应的TCB，内核级线程就是从系统内核视角能看到的线程
3. 组合方式
   有些系统使用组合方式的多线程实现。
   在组合实现方式中，内核支持多个内核级线程的建立、调度和管理，同时允许用户程序建立、调度和管理用户级线程。
   一些内核级线程对应多个用户级线程。

¶多线程模型

有些系统同时支持用户线程（“代码逻辑”的载体）和内核线程（“运行机会”的载体），由于用户级线程和内核级线程连接方式的不同，从而形成了下面三种不同的多线程模型。

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

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

   

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

   优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高

   缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行

   ！！！重点：操作系统只“看得见”内核级线程，因此只有内核级线程才是处理机分配的单位。

   

3. 多对多模型
   n用户及线程映射到m个内核级线程（n>=m）。每个用户进程对应m个内核级线程。

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

   

¶例题

1. 线程：
   

答：选B，操作系统会为每个内核级线程建立相应的TCB，意识不到用户级线程的存在

¶CPU调度

¶基本概念

1. 概念
   处理机调度是对处理机进行分配，即从就绪队列中按照一定的算法（公平、高效的原则）选择一个进程并将处理机分配给它运行，以实现进程并发地执行

2. 调度的层次
   作业：一个具体的任务
   用户向系统提交一个作业 ≈ 用户让操作系统启动一个程序（来处理一个具体的任务）

   一个作业从提交到完成，往往要经历以下三级调度

   1. 高级调度（作业调度） （外存->内存，发生频率最低）
      按一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。每个作业只调入一次，调出一次。作业调入时会建立PCB，调出时才撤销PCB

      无->创建态->就绪态

   2. 中级调度（内存调度） （外存->内存，发生频率中等）
      按照某种策略决定将哪个处于挂起状态的进程重新调入内存

      挂起态->就绪态

   3. 低级调度（进程调度） （内存->CPU，发生频率最高）
      按照某种策略从就绪队列中选取一个进程，将处理机分配给它，进程调度是操作系统中最基本的一种调度

      就绪态->运行态

¶进程调度的时机、切换和过程

临界资源：一个时间段只允许一个进程使用的资源。各进程互斥地访问临界资源（例如：打印机）
临界区：访问临界资源的代码

¶进程调度的时机

• 不能进行进程调度和切换的情况：
  1. 在处理中断的过程中。中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换。
  2. 进程在操作系统内核程序临界区中。
  3. 在原子操作过程中（原语）。原子操作不可中断，要一气呵成（如之修改PCB中进程状态标志，并把PCB放到相应队列）
• 需要进行进程调度和切换的情况：
  1. 当前运行的进程主动放弃处理机(进程正常终止、发生异常终止、请求阻塞等)
  2. 当前运行的进程被动放弃处理机(进程时间片耗尽、有优先级更高的进程)

¶进程的切换与过程

进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程

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

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

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

¶进程调度的方式

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

¶调度算法的评价指标

1. CPU利用率。
   $CPU利用率=\frac{CPU有效工作时间}{CPU有效工作时间+CPU空闲等待时间} $
2. 系统吞吐量。表示单位时间内CPU完成作业的数量
   $系统吞吐量=\frac{完成作业总数}{总共花费时间}$
3. 周转时间。是指从作业被提交给系统开始，到作业完成为止的这段时间间隔

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

   • 平均周转时间：所有作业周转时间的平均值
     $平均周转时间=\frac{各作业周转时间之和}{作业数}$

   • $带权周转时间=\frac{作业周转时间}{作业实际运行的时间}=\frac{作业完成时间-作业提交时间}{作业实际运行的时间}$

   • $平均带权周转时间=\frac{各作业带权周转时间之和}{作业数}$

4. 等待时间。指进程/作业处于等待处理机状态时间之和
   等待时间=周转时间-运行时间
5. 响应时间。指从用户提交请求到首次产生响应所用的时间

¶典型的调度算法

注意各个算法的优缺点、性能、概念、是否会导致饥饿(某进程/作业长期
得不到服务)、用于作业调度还是进程调度、抢占式还是非抢占式

• 概念：
• 用于作业调度还是进程调度：
• 抢占式还是非抢占式：
• 优点：
• 缺点：
• 是否会导致饥饿：
• 性能：

¶先来先服务（FCFS）

• 概念：按照作业/进程到达的先后顺序进行服务
• 用于作业调度还是进程调度：既可用于作业调度，也可用于进程调度。
• 抢占式还是非抢占式：非抢占式的算法
• 优点：公平、算法实现简单
• 缺点：对长作业有利，对短作业不利
• 是否会导致饥饿：不会
• 性能：

¶短作业优先（SJF）

• 概念：最短的作业/进程优先得到服务（所谓“最短”，是指要求服务时间最短）
• 用于作业调度还是进程调度：即可用于作业调度，也可用于进程调度。
• 抢占式还是非抢占式：非抢占式（但也有抢占版本）
• 优点：有“最短的”平均等待时间、平均周转时间
• 缺点：对短作业有利，对长作业不利。可能产生饥饿现象
• 是否会导致饥饿：会。如果源源不断地有短作业/进程到来，可能使长作业/进程长时间得不到服务，产生“饥饿”现象
• 性能：
  • 非抢占式：
    
  • 抢占式：
    

注意：

1. 如果题目中未特别说明，所提到的“短作业/进程优先算法”默认是非抢占式的
2. 在在所有进程同时可运行时条件下，采用SJF调度算法的平均等待时间、平均周转时间最少（没有条件的表述是不严谨的）
3. 如果选择题中遇到“SJF算法的平均等待时间、平均周转时间最少”的选项，那最好判断其他选项是不是有很明显的错误，如果没有更合适的选项，那应该选择该选项

¶最高相应比优先

• 概念：在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务
  $响应比=\frac{等待时间+要求服务时间}{要求服务时间}\geq{1}$
• 用于作业调度还是进程调度：即可用于作业调度，也可用于进程调度
• 抢占式还是非抢占式：非抢占式的算法
• 优缺点：综合考虑了等待时间和运行时间,对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题
• 是否会导致饥饿：不会
• 性能：

这三种算法一般适合用于早期的批处理系统，并不区分任务的紧急程度，FCFS算法也常结合其他的算法使用，在现在也扮演着很重要的角色

---

¶时间片轮转

• 概念：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片（如100ms）。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队

• 用于作业调度还是进程调度：用于进程调度

• 抢占式还是非抢占式：抢占式，由时钟装置发出时钟中断来通知CPU时间片已到

• 优点：公平；响应快，适用于分时操作系统

• 缺点：由于高频率的进程切换，因此有一定开销；不区分任务的紧急程度

• 是否会导致饥饿：不会

• 性能：时间片的大小对系统的性能影响很大

¶优先级调度

• 概念：调度时选择优先级最高的作业/进程
• 用于作业调度还是进程调度：既可用于作业调度，也可用于进程调度
• 抢占式还是非抢占式：抢占式、非抢占式都有
• 优点：用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度
• 缺点：若源源不断地有高优先级进程到来，则可能导致饥饿
• 是否会导致饥饿：会
• 性能：

¶多级反馈队列

• 概念：融合了前几种算法的优点
  • 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
  • 新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾
  • 只有第 k 级队列为空时，才会为 k+1 级队头的进程分配时间片
• 用于作业调度还是进程调度：用于进程调度
• 抢占式还是非抢占式：抢占式的算法
• 优点：
  • 对各类型进程相对公平（FCFS的优点）；
  • 每个新到达的进程都可以很快就得到响应（RR的优点）；
  • 短进程只用较少的时间就可完成（SPF的优点）；
  • 不必实现估计进程的运行时间（避免用户作假）；
  • 可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、I/O密集型进程（拓展：可以将因I/O而阻塞的进程重新放回原队列，这样I/O型进程就可以保持较高优先级）
• 缺点：
• 是否会导致饥饿：会
• 性能：

这三种算法适合用于交互式系统，更注重系统的响应时间、公平性、平衡性等指标

---

¶同步与互斥

¶基本概念

¶进程同步

因为进程具有异步性的特征。操作系统要提供“进程同步机制”来解决异步问题，以防止程序产生不可预知的错误

¶进程互斥

各个并发执行的进程不可避免的需要共享一些系统资源（比如内存，打印机、摄像头这样的I/O设备）

资源共享分为：互斥共享方式和同时共享方式

• 互斥共享方式：一个时间段内只允许一个进程访问该资源
• 同时共享方式：允许一个时间段内由多个进程“同时”对它们进行访问

我们把一个时间段内只允许一个进程使用的资源称为临界资源（如摄像头、打印机、一些变量和数据等）。对临界资源的访问，必须互斥地进行。可以把临界资源的访问过程分成四个部分：

1. 进入区（可理解为“上锁”）：负责检查是否可进入临界区，若可进入，则应设置正在访问临界资源的标志
2. 临界区：访问临界资源的那段代码
3. 退出区（可理解为“解锁”）：负责解除正在访问临界资源的标志
4. 剩余区：代码中剩余的其他部分

进入区和退出区是负责实现互斥的代码段;临界区是进程中访问临界资源的代码段

进程互斥：指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。

为了实现对临界资源的互斥访问，同时保证系统整体性能，同步机制应该遵循以下原则：

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

¶实现临界区互斥的基本方法

¶软件实现方法

¶算法一：单标志法

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

int turn = 0; 
//turn表示当前运行进入临界区的进程号（turn 变量背后的逻辑：表达“谦让”）

P0进程：
while(turn!=0);  //1 进入区
critial section;  //2 临界区
turn = 1;  //3 退出区
remainder section;  //4 剩余区

P1进程：
while(turn!=1);  //5 进入区
critial section;  //6 临界区
turn = 0;  //7 退出区
remainder section;  //8 剩余区

运行逻辑：turn 的初值为0，即刚开始只允许0号进程进入临界区。若P1先上处理机运行，则会一直卡在5。直到P1的时间片用完，发生调度，切换P0上处理机运行。代码1不会卡住P0，P0可以正常访问临界区，在P0访问临界区期间即时切换回 P1，P1依然会卡在5。只有P0在退出区将 turn 改为 1 后，P1才能进入临界区。

缺点：两个进程必须交替的进入临界区，若某个进程不再进入临界区，则另一个进程也无法进入临界区（违背“空闲让进”原则）

¶算法二：双标志先检查法

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

bool flag[2];  //表示进入临界区的意愿（背后的含义：“表达意愿”）
flag[0] = false;
flag[1] = false;

P0进程：
while(flag[1]);  //1 进入区，如果此时P1想要进入临界区，P0就一直循环等待
flag[0] = true;  //2 进入区，标记为P0进程想要进入临界区

critial section;  //3 临界区
flag[0] = false;  //4 退出区，修改标记为P0不想进入临界区
remainder section;  //剩余区

P1进程：
while(flag[0]);  //5 进入区，如果此时P0想要进入临界区，P1就一直循环等待
flag[1] = true;  //6 进入区，标记为P1进程想要进入临界区

critial section;  //7 临界区
flag[1] = false;  //8 退出区，修改标记为P1不想进入临界区
remainder section;  //剩余区

算法问题：若按照 1，5，2，6，3，7….的顺序执行，P0 和 P1 将会同时访问临界区。
违反“忙则等待”原则，其原因在于进入区的“检查”和“上锁” ，两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换。

¶算法三：双标志后检查法

算法思想：双标志先检查法的改版。人们又想到先“上锁”后“检查”的方法，来避免上述问题。

bool flag[2];  //表示进入临界区的意愿（背后的含义：“表达意愿”）
flag[0] = false;
flag[1] = false;

P0进程：
flag[0] = true;  //1 进入区，标记为P0进程想要进入临界区
while(flag[1]);  //2 进入区，如果此时P1想要进入临界区，P0就一直循环等待

critial section;  //3 临界区
flag[0] = false;  //4 退出区，修改标记为P0不想进入临界区
remainder section;  //剩余区

P1进程：
flag[1] = true;  //5 进入区，标记为P1进程想要进入临界区
while(flag[0]);  //6 进入区，如果此时P0想要进入临界区，P1就一直循环等待

critial section;  //7 临界区
flag[1] = false;  //8 退出区，修改标记为P1不想进入临界区
remainder section;  //剩余区

算法问题：若按照 1，5，2，6….的顺序执行，P0 和 P1 将都无法进入临界区
因此，双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待”原则，会因各进程都长期无法访问临界资源而 产生“饥饿” 现象

¶算法四：Peterson算法

算法思想：结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试谦让

bool flag[2];  //表示进入临界区的意愿（背后的含义：“表达意愿”）
int turn = 0;  //turn表示优先让哪个进程进入临界区（背后的逻辑：表达“谦让”）
flag[0] = false;
flag[1] = false;

P0进程：
flag[0] = true;  //1 进入区，标记为P0进程想要进入临界区
turn = 1 //可以优先让对方进入临界区
while(flag[1] && turn = 1);  //2 进入区，如果此时P1想要进入临界区并且P0表示谦让，P0就一直循环等待

critial section;  //3 临界区
flag[0] = false;  //4 退出区，修改标记为P0不想进入临界区
remainder section;  //剩余区

P1进程：
flag[1] = true;  //5 进入区，标记为P1进程想要进入临界区
turn = 0 //可以优先让对方进入临界区
while(flag[0] && turn = 0);  //6 进入区，如果此时P0想要进入临界区并且P1表示谦让，P1就一直循环等待

critial section;  //7 临界区
flag[1] = false;  //8 退出区，修改标记为P1不想进入临界区
remainder section;  //剩余区

算法分析：谁最后表达了谦让，谁就失去了行动的优先权
算法问题：Peterson 算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待 三个原则，但是依然未遵循让权等待的原则

¶硬件实现方法

¶中断屏蔽方法

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

关中断；
临界区；
开中断；

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

¶硬件指令方法

1. TestAndSetLock 指令（TSL指令）
   TSL指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。
   简而言之，相比软件实现方法，TSL 指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作

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

2. Swap指令（也叫 Exchange 指令，或简称 XCHG 指令）
   Swap 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成
   逻辑上来看 Swap 和 TSL 并无太大区别
   优缺点同TSL指令

¶互斥锁

解决临界区最简单的工具就是互斥锁。一个进程在进入临界区时应获得锁；在退出临界区时释放锁。
函数 acquire()获得锁，而函数release()释放锁。 acquire()和release()的执行必须是原子操作，因此互斥锁通常使用硬件机制来实现
互斥锁的主要缺点是忙等待。需要连续循环忙等的互斥锁，都可称为自旋锁，如TSL指令、swap指令、单标志法

¶信号量

信号量S其实就是一个变量(可以是一个整数，也可以是更复杂的记录型变量)，可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为1的信号量

信号量只能被两个标准的原语wait(S)和signal(S)访问，其常简称为P、V操作，也即wait(S)称为P(S)，signal(S)称为V(S)，这对原语可用于实现系统资源的“申请”和“释放”。

¶整型信号量

用一个整数型的变量作为信号量，用来表示系统中某种资源的数量
整型信号量的缺陷是存在“忙等”问题

¶记录型信号量

// 记录型信号量的定义
typedef struct{
   int value;//S.value 的初值表示系统中某种资源的数目
   Struct process *L; //链表L用来链接等待该资源的进程
} semaphore;

对信号量 S 的一次P操作意味着进程请求一个单位的该类资源，当
S.value<0 时表示该类资源已分配完毕，因此进程应调用 block 原语进行自我阻塞，并插入该类资源的等待队列S.L中。

对信号量 S 的一次V操作意味着进程释放一个单位的该类资源，若加1后仍是S.value<=0，表示依然有进程在等待该类资源，因此应调用wakeup 原语唤醒等待队列中的第一个进程

注：若考试中出现 P(S)、V(S) 的操作，除非特别说明，否则默认 S 为记录型信号量

¶利用信号量实现同步

用信号量实现进程同步：

1. 分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作（或两句代码）
2. 设置同步信号量S, 初始为0
3. 在“前操作”之后执行 V(S)
4. 在“后操作”之前执行 P(S)

技巧口诀：前V后P
理解：信号量S代表“某种资源”，刚开始是没有这种资源的。P2需要使用这种资源，而又只能由P1产生这种资源

¶信号量机制实现前驱关系

其实每一对前驱关系都是一个进程同步问题（需要保证一前一后的操作）
因此，

1. 要为每一对前驱关系各设置一个同步信号量
2. 在“前操作”之后对相应的同步信号量执行 V 操作
3. 在“后操作”之前对相应的同步信号量执行 P 操作

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

1. 分析并发进程的关键活动，划定临界区（如：对临界资源打印机的访问应放在临界区）
2. 设置互斥信号量 mutex，初值为 1
3. 在进入区 P(mutex)——申请资源
4. 在退出区 V(mutex)——释放资源

注意：对不同的临界资源需要设置不同的互斥信号量。P、V操作必须成对出现。缺少P(mutex) 就不能保证临界资源的互斥访问。缺少 V(mutex) 会导致资源永不被释放，等待进程永不被唤醒

注意：同步和互斥之间的对比

互斥问题，信号量初值为1
同步问题，信号量初值为0

除了互斥、同步问题外，还会考察有多个资源的问题，有多少资源就把信号量初值设为多少。申请资源时进行P操作，释放资源时进行 V 操作即可

¶管程

为了解决信号量机制导致的编写程序困难、易出错问题，引入管程机制来实现进程同步。

管程是一种特殊的软件模块

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

管程的基本特征：

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

¶经典同步问题

PV操作题目分析步骤：

1. 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
2. 整理思路。根据各进程的操作流程确定P、V操作的大致顺序。
3. 设置信号量。并根据题目条件确定信号量初值。（互斥信号量初值一般为1，同步信号量的初始值要看对应资源的初始值是多少）

¶生产者-消费者问题

¶问题描述：

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用（注：这里的“产品”理解为某种数据）
生产者、消费者共享一个初始为空、大小为n的缓冲区。
只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。
只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。
缓冲区是临界资源，各进程必须互斥地访问。

¶问题分析

1. 关系分析。生产者和消费者对缓冲区的互斥访问是互斥关系，同时生产者和消费者也是一个相互协作问题，只有生产者生产后，消费者才能消费，他们是同步关系
2. 整理思路。
3. 信号量设置

   semaphore mutex = 1;//互斥信号量，实现对缓冲区的互斥访问
   semaphore empty = n;//同步信号量，表示空闲缓冲区的数量
   semaphore full = 0;//同步信号量，表示产品的数量，也即非空缓冲区的数量
   
   
   producer (){
      while(1){
         生产一个产品;
         P(empty);//消耗一个空缓冲区
         
         P(mutex);
         把产品放入缓冲区; //实现互斥是在同一进程中进行一对PV操作
         V(mutex);
   
         V(full);//增加一个产品
      }
   }
   
   consumer (){
      while(1){
         P(full); //实现两个进程同步关系，是在其中一个进程中执行P另一个执行V，这里符合“前V后P”
   
         P(mutex);
         从缓冲区取出一个产品; //互斥的访问缓冲区，将缓冲区“夹紧”
         V(mutex);
   
         V(empty);//增加一个空闲缓冲区
         使用产品;
      }
   }

思考：能否改变相邻P、V操作的顺序?
若缓冲区中没有产品，即full=0，empty=n，此时将P(mutex)放在P(full)和P(empty)之前，若是按照P(mutex)、P(full)、P(mutex)的顺序执行就会导致死锁。
因此，实现互斥的P操作一定要在实现同步的P操作之后。
V操作不会导致进程阻塞，因此两个V操作顺序可以交换。

¶多生产者-多消费者问题

¶问题描述

桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。
用PV操作实现上述过程

¶问题分析

互斥关系：对缓冲区（盘子）的访问要互斥地进行
同步关系（一前一后）：

1. 父亲将苹果放入盘子后，女儿才能取苹果
2. 母亲将橘子放入盘子后，儿子才能取橘子
3. 只有盘子为空时，父亲或母亲才能放入水果
   • (“盘子为空”这个事件可以由儿子或女儿触发，事件发生后才允许父亲或母亲放水果)

信号量设置：

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

dad (){
   while(1){
      准备一个苹果;
      P(plate);

      P(mutex);
      把苹果放入盘子;
      V(mutex);

      V(apple);
   }
}
mom (){
   while(1){
      准备一个橘子;
      P(plate);

      P(mutex);
      把橘子放入盘子;
      V(mutex);

      V(orange);
   }
}
daughter (){
   while(1){
      P(apple);

      P(mutex);
      从盘中取出苹果;
      V(mutex);

      V(plate);
      吃掉苹果;
   }
}
son (){
   while(1){
      P(orange);

      P(mutex);
      从盘中取出橘子;
      V(mutex);

      V(plate);
      吃掉橘子;
   }
}

¶要点分析

在分析同步问题（一前一后问题）的时候不能从单个进程行为的角度来分析，要把“一前一后”发生的事看做是两种“事件”的前后关系

比如，如果从单个进程行为的角度来考虑的话，我们会有以下结论：
如果盘子里装有苹果，那么一定要女儿取走苹果后父亲或母亲才能再放入水果
如果盘子里装有橘子，那么一定要儿子取走橘子后父亲或母亲才能再放入水果
这么看是否就意味着要设置四个同步信号量分别实现这四个“一前一后”的关系了？
正确的分析方法应该从“事件”的角度来考虑，我们可以把上述四对“进程行为的前后关系”抽象为一对“事件的前后关系”

盘子变空事件->放入水果事件。
“盘子变空事件”既可由儿子引发，也可由女儿引发；
“放水果事件”既可能是父亲执行，也可能是母亲执行。
这样的话，就可以用一个同步信号量解决问题了

¶吸烟者问题(可以生产多个产品的单生产者问题)

¶问题描述

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

¶问题分析

1. 关系分析：供应者与三个吸烟者分别是同步关系，三个吸烟者对吸烟这个动作互斥（不需要专门再设置一个互斥信号量表示对桌子的使用（桌子可以抽象为容量为1的缓冲区），因为吸烟只能是轮流进行的）
2. 整理思路：显然有四个进程
   
3. 信号量设置

   semaphore offer1 = 0;//桌上组合一的数量
   semaphore offer2 = 0;//桌上组合二的数量
   semaphore offer3 = 0;//桌上组合三的数量
   semaphore finish = 0;//抽烟是否完成
   int i = 0;//用于实现“三个抽烟者轮流抽烟”
   
   provider (){
      while(1){
         if(i==0) {
            将组合一放桌上;
            V(offer1);
         } else if(i==1){
            将组合二放桌上;   
            V(offer2);
         } else if(i==2){
            将组合三放桌上;
            V(offer3);
         }
         i = (i+1)%3; //实现轮流
         P(finish);
      }
   }
   
   smoker1 (){
         while(1){
            P(offer1);
            从桌上拿走组合一；卷烟；抽掉；
            
            V(finish);
         }
      }
   smoker2 (){
         while(1){
            P(offer2);
            从桌上拿走组合二；卷烟；抽掉；
            
            V(finish);
         }
   }
   smoker3 (){
         while(1){
            P(offer3);
            从桌上拿走组合三；卷烟；抽掉；
            
            V(finish);
         }
   }