2 进程的描述与控制

前趋图

➢ 有向无循环图，用于描述进程之间执行的先后顺序
➢ 结点表示进程或程序段，有向边表示前趋关系

前趋图(Precedence Graph)是一个有向无循环图，记为DAG(Directed Acyclic Graph)，用于描述进程之间执行的前后关系

图中的每个结点可用于描述一个程序段或进程，乃至一条语句；结点间的有向边则用于表示两个结点之间存在的偏序(Partial Order)或前趋关系(Precedence Relation)“→”

→={(Pi, Pj)|Pi must complete before Pj may start}

如果(Pi, Pj)∈→,可写成Pi→Pj，称Pi是Pj 的直接前趋，而称Pj是Pi的直接后继

在前趋图中，把没有前趋的结点称为初始结点(Initial Node)，把没有后继的结点称为终止结点(Final Node)

前趋图还可表示为：

P={P1, P2, P3, P4, P5, P6, P7, P8, P9}→

={ (P1, P2), (P1, P3), (P1, P4), (P2, P5), (P3, P5), (P4, P6), (P4, P7), (P5, P8), (P6, P8), (P7, P9), (P8, P9)}

程序并发执行

只有不存在前趋关系的程序才有可能并发执行

程序并发执行时的特征

间断性 ➢ 并发程序之间相互制约。 ➢ 执行——暂停执行——执行。

失去封闭性 ➢ 多个程序共享全机资源。 ➢ 执行状态受外界因素影响。

不可再现性 ➢ 程序经过多次执行后，虽然其执行时的环境和初始条件都相同，但得到的结果却各不相同。

进程的描述

多道程序环境下，程序的执行属于并发执行，此时它们将失去封闭性，并具有间断性及不可再现性的特征。因此，通常的程序不能参加并发执行。为此，引入“进程”

进程的定义

➢ 进程是程序的一次执行。

➢ 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。

➢ 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。

➢ 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

进程和程序的区别

进程是程序的一个实例，是程序的一次执行。

程序是进程的代码部分。

进程是活动的，程序是静态的。

进程在内存中，程序在外存中。

进程的特征

动态性（最基本的特征）

➢ 有生命期

并发性

➢ 多个进程可一段时间内“同时”运行

独立性

➢ 进程实体是一个能独立运行的基本单位

➢ 是系统中独立获得资源和独立调度的基本单位

异步性

➢ 按各自独立的、不可预知的速度向前推进

进程的基本状态和切换

基本状态

创建状态（new）

就绪状态（ready）：只需要再获得CPU

➢ 一个较大的程序通常都由若干个程序段组成

➢ 程序在执行时，必须按照某种先后次序逐个执行，仅当前一操作执行完后，才能执行后继操作。

执行状态（running）：已获得CPU，正在执行的状态

➢ 单处理机：一个进程处于执行状态

➢ 多处理机：多个进程处于执行状态

阻塞状态（block / waiting）：进程等待某些事件发生的状态

➢ 正在执行的进程由于发生某事件而暂时无法继续执行的状态

➢ 典型事件：请求I/O、申请缓冲空间

➢ 根据阻塞原因，设置多个阻塞队列

终止状态（terminated）

进程状态的转换

➢ 运行态变为就绪态

强制终止某进程的运行（系统原因）

➢ 运行态变为阻塞态

运行进程等待外部事件发生（自身原因）

➢ 阻塞态变为就绪态

外部事件已经发生，可准备运行

➢ 就绪态变为运行态

停止其他进程运行后，运行该进程占用CPU

挂起操作及进程状态的转换

为什么引入挂起操作？ ➢ 终端用户的请求 ➢ 父进程请求 ➢ 负荷调节的需要（实时系统） ➢ 操作系统的需要

引入挂起操作后三个进程状态的转换

活动就绪——〉静止就绪（挂起）
活动阻塞——〉静止阻塞（挂起）
静止就绪——〉活动就绪（激活）
静止阻塞——〉活动阻塞（激活）
静止阻塞——〉静止就绪

进程管理中的数据结构——PCB

PCB是进程的一部分，是操作系统中最重要的记录型数据结构，是进程存在的唯一标志，常驻内存。

专门的数据结构，与进程一一对应。

➢ 为描述和控制进程的运行，系统为每个进程定义了一个数据结构——进程控制块

➢ PCB（Process Control Block），是进程实体的一部分，记录了操作系统所需的、用于描述进程当前状况以及控制进程运行的全部信息

➢ OS是根据PCB来对并发执行的进程进行控制和管理的

◆进程＝程序＋数据＋PCB ，即进程是一个程序及其数据在处理机上顺序地执行时所发生的活动

◆ 进程控制块是进程存在的唯一标志。当系统创建一个进程时，必须为它设置一个 PCB，然后根据PCB的信息对进程实施控制管理，进程任务完成时，系统收回它的PCB，进程也随之消亡

PCB的作用

➢ 作为独立运行基本单位的标志； ➢ 能实现间断性运行方式； ➢ 提供进程管理所需要的信息； ➢ 提供进程调度所需要的信息； ➢ 实现与其他进程的同步与通信。

PCB中的信息

➢ 进程标识信息：PID, PPID

用于唯一地标识一个进程。一个进程通常有两种标识符： 1）内部标识符，数字标识符；2）外部标识符，它由创建者提供，描述进程的家族关系。

➢ 处理器状态信息：PC, PSW, 堆栈指针、寄存器

➢ 进程调度信息：与进程调度和进程对换有关的信息，包括：进程状态、进程优先级、进程调度所需的其它信息、事件

➢ 进程控制信息：程序和数据的地址、进程同步和通信机制、资源清单、链接指针

创建状态和终止状态——申请和回收PCB

创建状态 ➢申请一个空白PCB；填写PCB；分配资源；设置就绪状态插入就绪队列

终止状态 ➢等待OS善后； ➢收回PCB

PCB的组织方式

线性方式

所有PCB组织在一张线形表，表的首址放在内存专用区域
实现简单
查找效率低

链接方式

通过PCB中的连接字，将具有相同状态的PCB分别链接成一个队列

索引方式

系统根据所有进程状态的不同，建立几张索引表

进程控制

进程的创建

① 申请空白PCB； ② 分配所需资源； ③ 初始化PCB； ④ 插入就绪队列。

进程的层次结构

创建进程的进程是父进程，被创建的进程成为子进程

进程图

➢ 描述进程家族关系的有向树

引起进程创建的事件（负责不同的任务）

➢ 用户登录、作业调度、提供服务、应用请求

进程的终止

引起进程终止的事件：正常结束、异常结束、外界干预

进程的终止过程

1 根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态；

2 若被终止进程正处于执行状态，应立即终止该进程的执行，并设置调度标志为真，用于指示该进程被终止后应重新进行调度；

3 若该进程还有子孙进程，还应将其所有子进程予以终止；（部分级联终止系统）

4 将该进程所拥有的全部资源，或者归还给其父进程或系统；

5 将被终止进程（PCB）从所在队列中移去。

进程的阻塞与唤醒

引起进程阻塞和唤醒的事件

➢ 向系统请求共享资源失败；等待某种操作的完成；新数据尚未到达；等待新任务的到达。

进程阻塞过程

➢ 阻塞原语Block()。

➢ 进程的阻塞是进程自身的一种主动行为。

➢ 具体过程：停止执行；状态由执行改为阻塞；将PCB插入阻塞队列。

进程唤醒过程

➢ 唤醒原语Wakeup()。

➢ 具体过程：从阻塞队列中移出；状态由阻塞改为就绪；将PCB插入就绪队列。

➢ 必须成对使用Block和Wakeup原语。

进程的挂起与激活

Suspend()原语

Active()原语

进程通信

进程通信是指进程之间的信息交换(各进程为了保持联系而交换信息)

高级进程通信：用户可直接利用OS所提供的一组通信命令，高效地传送大量数据的一种通信方式

共享存储器系统（shared memory）

➢ 基于共享数据结构的通信方式（效率低）
➢ 基于共享存储区的通信方式（高级，共享内存）

共享存储器（shared-memory）方法的主要思想是：进程之间通过共享某些数据结构或存储区实现信息传送。
两种类型：

➢ 基于共享数据结构的通信方式（例：生产者—消费者问题中的有界缓冲区，属于低级通信方式）

➢ 基于共享存储区的通信方式：在存储器中划出一块共享存储区，诸进程通过对共享存储区中数据的读或写实现通信（传输大量数据，属于高级通信）

消息传递系统（message passing）

必须要有通信线路

直接通信方式

通信线路是通过系统调用自动建立的。

➢ 发送进程利用OS所提供的发送命令，直接把消息发送给目标进程
➢ 要求发送进程和接收进程都以显式方式提供对方的标识符
➢ 系统提供下述两条通信命令(原语)：
Send(Receiver, message)
Receive(Sender, message)

直接通信原语

某些情况下，接收进程可与多个发送进程通信，因此，它不可能事先指定发送进程。
例如，用于提供打印服务的进程，它可以接收来自任何一个进程的“打印请求”消息。
对于这样的应用，在接收进程接收消息的原语中的源进程参数，是完成通信后的返回值，接收原语可表示为：Receive (id, message)

消息格式

➢ 通常，可把一个消息分成消息头和消息正文两部分。

➢ 消息头包括消息传输时所需的控制信息，如发送进程名、接收进程名、消息长度、消息类型、消息编号及消息的发送日期和时间；

➢ 消息正文则是发送进程实际上所发送的数据。

通信链路

为了在发送进程和接收进程之间能进行通信，必须在它们之间建立一条通信链路。有两种方式建立通信链路：

隐式建立链路。发送进程无需明确提出建立链路的请求，只需利用系统提供的发送命令(原语)，系统会自动地为之建立一条链路。这种方式主要用于单机系统 中
显式建立链路。由发送进程在通信之前，用“建立连接”命令(原语)请求系统为之建立一条通信链路；在链路使用完后，也应用显式方式拆除链路。这种方式主要用于计算机网络中

根据通信方式的不同，又可以把链路分为：

➢ 单向通信链路: 只允许发送进程向接受者进程发送消息

➢ 双向链路: 允许由进程A向进程B发送消息，也允许进程B同时向进程A发送消息

根据通信链路的容量的不同也可以把链路分成：

➢ 无容量通信链路: 在这种通信链路上没有缓冲区，因而不能暂存任何消息

➢ 有容量通信链路: 在这种通信链路上设置了缓冲区，因而能暂存消息，缓冲区数目愈多，通信链路的容量愈大

➢ 利用直接通信原语，来解决生产者-消费者问题

➢ 当生产者生产出一个产品(消息)后，便用Send原语将消息发送给消费者进程；而消费者进程则利用Receive原语来得到一个消息。

可以考虑使用阻塞。例如，阻塞消费者，如果消息尚未生产出来，消费者必须等待，直至生产者进程将消息发送过来。

进程同步方式

在进程之间进行通信时，往往也需要辅以进程同步，以使它们能协调通信

➢ 发送进程阻塞、接收进程阻塞

➢ 发送进程不阻塞、接收进程阻塞

➢ 发送进程和接收进程均不阻塞

间接通信方式（通过邮箱）

通信线路是通过不同进程共享邮箱时建立的。

进程不把消息直接发给接收者进程，而把消息放在某个双方共知的信箱（Mailbox）中
既可以实现实时通信，又可以实现非实时通信
系统提供若干原语，分别用于信箱的创建、撤销和消息的发送、接收

信箱分为以下三类

➢ 私用信箱：用户进程可为自己建立一个新信箱，并作为该进程的一部分。信箱的拥有者有权从信箱中读取消息，其他用户则只能将自己构成的消息发送到该信箱中

➢ 公用信箱：它由操作系统创建，并提供给系统中的所有核准进程使用。核准进程既可把消息发送到该信箱中，也可从信箱中读取发送给自己的消息

➢ 共享信箱：它由某进程创建，在创建时或创建后，指明它是可共享的，同时须指出共享进程(用户)的名字。信箱的拥有者和共享者，都有权从信箱中取走发送给自己的消息

消息缓冲队列通信机制
首先由美国的Hansen提出，并在RC4000系统上实现，后来被广泛应用于本地进程之间的通信中。
基本思想：发送进程利用send原语，将消息发给接收进程；接收进程则利用Receive原语，接收消息。

小结

当前应用最广泛的进程间通信机制
系统提供发送消息Send(message)与接收消息Receive(message) 两个操作，进程间则通过使用这两个操作进行通讯，无需共享任何变量
实现方式的不同分成直接通信方式和间接通信方式两种
进程间的数据交换，以格式化的消息为单位。所谓“信息”通常由消息头和消息正文构成
实现了大量数据的传递，隐藏了实现细节，简化了程序编制复杂性，使用最广泛

管道通信（pipe）

管道：用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名pipe文件。

➢ 管道机制的协调能力：互斥、同步、对方是否存在

所谓“管道”，是指用于连接一个读进程和一个写进程以实现他们之间通信的一个共享文件，又名pipe文件
向管道提供输入的发送进程(即写进程)，以字符流形式将大量的数据送人管道；而接收进程(即读进程)，可从管道中接收数据
这种方式首创于UNIX系统，因它能传送大量的数据，且很有效，故又被引入到许多其它操作系统中

互斥：即当一个进程正在对pipe执行读/写操作时，其它(另一)进程必须等待。
同步：指当写(输入)进程把一定数量的数据写入pipe，便去睡眠等待，直到读(输出)进程取走数据后，再把他唤醒。当读进程读一空pipe时，也应睡眠等待，直至写进程将数据写入管道后，才将之唤醒。
确定对方是否存在，只有确定了对方已存在时，才能进行通信。

客户机-服务器系统

➢ 套接字（Socket）
➢ IP地址（哪一台电脑）+端口号（哪一个程序）

远程过程调用（RPC，Remote Procedure Call）和远程方法调用（RMI，Remote Method Invocation，Java）

线程的基本概念

提出线程的目的

➢ 减少程序在并发执行时所付出的时空开销
➢ 使OS具有更好的并发性

进程是拥有资源的基本单位（传统进程称为重型进程）

线程作为调度和分派的基本单位（又称为轻型进程）

线程和进程的比较

调度的基本单位

➢在传统的OS中，拥有资源、独立调度和分派的基本单位都是进程；
➢在引入线程的OS中，线程作为调度和分派的基本单位，进程作为资源拥有的基本单位；
➢在同一进程中，线程的切换不会引起进程切换，在由一个进程中的线程切换到另一个进程中的线程时，将会引起进程切换。

并发性

➢在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间，也可并发执行。

拥有资源

➢进程是系统中拥有资源的一个基本单位，它可以拥有资源。
➢线程本身不拥有系统资源，仅有一点保证独立运行的资源。
➢允许多个线程共享其隶属进程所拥有的资源。

独立性

➢同一进程中的不同线程之间的独立性要比不同进程之间的独立性低得多。

系统开销

➢在创建或撤消进程时，OS所付出的开销将显著大于创建或撤消线程时的开销。
➢线程切换的代价远低于进程切换的代价。
➢同一进程中的多个线程之间的同步和通信也比进程的简单。

支持多处理机系统

线程状态

➢ 执行态、就绪态、阻塞态

➢ 线程状态转换与进程状态转换一样

线程控制块（thread control block，TCB）

➢ 线程标识符、一组寄存器、线程
运行状态、优先级、线程专有存
储区、信号屏蔽、堆栈指针

线程的实现

内核支持线程KST

在内核空间实现

优点：

➢在多处理机系统中，内核可同时调度同一进程的多个线程
➢如一个线程阻塞了，内核可调度其他线程(同一或其他进程)。
➢线程的切换比较快，开销小。
➢内核本身可采用多线程技术，提高执行速度和效率。

缺点：

➢对用户线程切换，开销较大。

用户级线程ULT

在用户空间实现
优点：

➢线程切换不需要转换到内核空间。
➢调度算法可以是进程专用的。
➢线程的实现与OS平台无关。

缺点：

➢系统调用的阻塞问题。
➢多线程应用不能利用多处理机进行多重处理的优点。

ULT与KST组合方式

多对一模型

多个用户级线程映射到一个内核线程。
多个线程不能并行运行在多个处理器上。
线程管理在用户态执行，因此是高效的，但一个线程的阻塞系统调用会导致整个进程的阻塞。
用于不支持内核线程的系统中。
例子: ➢Solaris Green Threads➢GNU Portable Threads

一对一模型

每个用户级线程映射到一个内核线程。
比多对一模型有更好的并发性。
允许多个线程并行运行在多个处理器上。
创建一个ULT需要创建一个KLT，效率较差。

多对多模型

多个用户级线程映射为相等或小于数目的内核线程。

允许操作系统创建足够多的KLT。

3 处理机调度与死锁

处理机调度概述

在多道程序系统中，一个作业从提交到执行，通常都要经历多级调度
➢ 如高级调度、低级调度、中级调度以及I/O调度等
系统的运行性能在很大程度上取决于调度
➢ 如吞吐量的大小、周转时间的长短、响应的及时性等
调度是多道程序系统的关键

◼CPU资源管理——多道程序设计面临的挑战
 批处理系统：如何安排内存中多个作业的运行顺序？
 交互式系统：如何更好应对不同的交互式请求？
 实时系统：如何保证实时服务的高质量？
◼ 进程调度——有效的管理CPU资源
 When：何时进行进程调度？
 How：遵循何种规则完成调度？
 What：调度过程中需要完成哪些工作？
◼ 进程调度的级别
 高级调度：也称宏观调度，决定哪些程序可以进入系统
 中级调度：也称内存调度，决定内存中程序的位置和状态
 低级调度：也称微观调度，决定CPU资源在就绪进程间的分

处理机调度层次

高级调度（长程调度/作业调度）
中级调度（中程调度/内存调度）
低级调度（短程调度/进程调度）

高级调度

调度对象：作业
根据某种算法，决定将外存上处于后备队列中的作业调入内存，并为它们创建进程和分配必要的资源。然后，将新创建的进程排在就绪队列上等待调度。
主要用于多道批处理系统中

作业：在多道批处理操作系统中，用户提交给系统的一项相对独立的工作

作业（JOB）：是用户在一次算题过程中或一次事务处理中，要求计算机系统所做的工作的集合。在批处理系统中，以作业为单位从外存调入内存
作业和进程的关系：作业是比进程更广泛的概念，不仅包含了通常的程序和数据，而且还配有一份作业说明书，系统根据作业说明书对程序运行进行控制

作业控制块

作业控制块（JCB）:多道批处理系统中，为每个作业设置一个作业控制块。 JCB是一个作业在系统中存在的惟一标志，系统根据JCB 才感知到作业的存在
JCB包含内容：作业控制块JCB中包含了对作业进行管理的必要信息，JCB中的信息一部分是从用户提供的作业控制卡或作业说明书中得到，另一部分是记录作业运行过程中的动态信息
JCB的生成：作业提交给系统后，便由“作业注册”程序为作业建立一个作业控制块JCB，放入后备队列

中级调度

引入中级调度的主要目的，是为了提高内存利用率和系统吞吐量；使那些暂时不能运行的进程不再占用宝贵的内存资源，将它们调至外存上去等待，把此时的进程状态称为就绪驻外存状态或挂起状态；

当这些进程具备运行条件、且内存又稍有空闲时，由中级调度来决定把就绪进程，重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度；

即“对换” 功能；短期调整系统负荷，平顺系统操作

低级调度

调度对象：进程

根据某种调度算法，决定就绪队列中的哪个进程应获得处理机

应用在于多道批处理、分时和实时OS

进程调度的任务

保存处理机现场信息。进程调度程序把当前进程的现场信息，如程序计数器及通用寄存器的内容等保留在该进程PCB的现场信息区中
按某种算法挑选进程。根据一定的调度算法(如先到先服务)，从就绪队列中选出一个进程来，并把它的状态改为运行态，准备把CPU分配给它
把处理器分配给进程。为选中的进程恢复现场信息，并把CPU的控制权交给该进程,它接着上次间断的地方继续运行

进程调度机制

排队器:将就绪进程按一定方式排成队列
分派器（dispatcher，分派程序）:把进程调度程序选定的进程，从就绪队列中取出，进行上下文切换，把处理器分配给它
上下文切换机制:①保存当前进程上下文，装入分派程序上下文，分派程序运行； ②移出分派程序，装入新选进程上

处理机调度三级层次

进程调度的任务

进程调度的任务
➢ 保存处理机的现场信息
➢ 按某种算法选取进程
➢ 把处理器分配给进程

进程调度机制（调度程序分为三部分）
➢ 排队器：用于将就绪进程插入相应的就绪队列
➢ 分派器：用于将选定的进程移出就绪队列
➢ 上下文切换器：进行新旧进程之间的上下文切换

进程调度的方式

非抢占方式：一旦把处理机分配给某进程后，便让该进程一直执行，直至该进程完成或发生某事件而被阻塞时，才再把处理机分配给其他进程，决不允许某进程抢占已经分配出去的处理机。

抢占方式：允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。(现代OS广泛采用)

调度准则

➢ 取决于操作系统的类型和目标
➢ 不同的操作系统，有不同的调度方式和算法
➢ 有面向用户的准则，也有面向系统的准则
Max CPU utilization 最大CPU利用率
Max throughput 最大吞吐量
Min turnaround time 最小周转时间
Min waiting time 最小等待时间
Min response time 最小响应时间

普遍目标： ➢ 资源利用率 ➢ 公平性 ➢ 平衡性 ➢ 策略强制执行

$利用率有效工作时间有效工作时间空闲等待时间$
批处理系统的目标： ➢ 平均周转时间短、系统吞吐量高、处理机利用率高

分时系统的目标： ➢ 响应时间快、均衡性

实时系统的目标： ➢ 截止时间的保证、可预测性

评价指标

周转时间

➢ 从作业提交给系统开始，到作业完成为止的这段时间间隔。
➢ 平均周转时间
➢ 带权周转时间：权值为作业周转时间T与系统为之服务时间TS之比。
➢ 平均带权周转时间

吞吐量

➢ 单位时间内所完成的作业数

等待时间（进程调度）

➢ 进程在就绪队列中等待调度的所有时间之和。

分时系统的目标

响应时间

➢ 从用户通过键盘提交请求开始，直到系统首次显示出处理结果为止的一段时间。

响应时间包括

➢ ①从键盘输入的请求信息传送到处理机的时间
➢ ②处理机对请求信息进行处理的时间
➢ ③将所形成的响应回送到终端显示器的时间

均衡性

➢ 响应时间快慢与用户请求复杂度相适应

实时系统的目标

截止时间

➢ 是指某任务必须开始执行的最迟时间，或必须完成的最迟时间

调度算法

先来先服务（FCFS）调度算法

作业调度和进程调度均可，最简单，本质上属非抢占方式
有利于长作业/进程，不利于短作业
有利于CPU繁忙型的作业(如通常的科学计算)，而不利于I/O繁忙的作业/进程（如大多数的事务处理)

短作业优先（SJF）调度算法

SJF算法：既可用于作业，也可用于进程

➢ 对作业：从后备队列中选择若干个估计运行时间最短的作业。 ➢ 对进程：关联到每个进程下次运行的CPU区间长度，调度最短的进程。

对进程调度，SJF有两种模式

➢ 非抢占式SJF
➢ 抢占式SJF–抢占发生在有比当前进程剩余时间片更短的进程到达时，也称为最短剩余时间优先调度

SJF是最优的（对一组指定的进程而言），它给出了最短的平均等待时间。

SJF比FCFS算法有明显改进

缺点

只能估算进程的运行时间（估值不准确），所以通常用于作业调度
对长作业不利
采用SJF算法时，人-机无法实现交互
完全未考虑作业的紧迫程度

优先级调度算法PR

既可用于作业调度，也可用于进程调度。

基于作业/进程的紧迫程度，由外部赋予作业相应的优先级，调度算法根据优先级进行调度。

➢ 每个进程都有一个优先数，优先数为整数。
➢ 默认：小的优先数具有高优先级。
➢ 目前主流的操作系统调度算法。

高响应比优先调度算法是一种优先级调度算法，用于作业调度。

优先级调度算法的类型

➢ 非抢占式 ➢ 抢占式

优先级类型

➢ 静态优先级
 创建进程时确定优先数(整数)，在进程的整个运行期间保持不变
 简单易行，系统开销小
 不够精确，可能会出现优先级低的进程长期没有被调度的情况
➢ 动态优先级
 创建进程时先赋予其一个优先级，然后其值随进程的推进或等待时间的增加而改变

优点

➢ 实现简单，考虑了进程的紧迫程度
➢ 灵活，可模拟其它算法

存在问题

➢ 饥饿 ——低优先级的进程可能永远得不到运行

解决方法

➢ 老化 —— 视进程等待时间的延长提高其优先数

高相应比优先调度算法（PR的特例）

既考虑作业的等到时间，又考虑作业的运行时间
➢ 优先级： $等待时间要求服务时间要求服务时间$
➢ 响应比： $等待时间要求服务时间要求服务时间响应时间要求服务时间$
➢ 如等待时间相同，运行时间越短，类似于SJF
➢ 如运行时间相同，取决于等待时间，类似于FCFS
➢ 长作业可随其等待时间的增加而提高，也可得到服务
➢ 缺点：每次调度之前，都需要计算响应比，增加系统开销

时间片轮转(Round-Robin，RR)调度算法

专为分时系统设计，类似于 FCFS，但增加了抢占

时间片q （Time Quantum） ➢ 小单位的CPU时间，通常为 10~100毫秒

为每个进程分配不超过一个时间片的 CPU。时间片用完后，该进程将被抢占并插入就绪队列末尾，循环执行

➢ 假定就绪队列中有n个进程、时间片为q ➢ 则每个进程每次得到 1/n的、不超过q单位的成块CPU时间 ➢ 没有任何一个进程等待时间超过(n-1) q单位

特性 ➢ q 大–> FCFS ➢ q 小–> 增加上下文切换的时间

时间片大小的确定

时间片设置应考虑

➢ 系统对响应时间的要求
➢ 就绪队列中进程的数目
➢ 系统的处理能力

一般准则：时间片/10>进程上下文切换时间

多级队列调度算法

就绪队列从一个分为多个，如：➢ 前台[交互式] ➢ 后台[批处理]

每个队列有自己的调度算法 ➢ 前台 – RR ➢ 后台 – FCFS

调度须在队列间进行
➢ 固定优先级调度。即前台运行完后再运行后台，有可能产生饥饿。
➢ 给定时间片调度。即每个队列得到一定的CPU时间，进程在给定时间内执行；如80%的时间执行前台的RR调度，20%的时间执行后台的FCFS调度

进程能在不同的队列间移动

其他调度算法的局限性

➢ 短进程优先的调度算法，仅照顾了短进程而忽略了长进程
➢ 如果并未指明进程的长度，则短进程优先和基于进程长度的抢占式调度算法都将无法使用。

优点：

➢ 不必事先知道各种进程所需的执行时间；
➢ 可以满足各种类型进程的需要。

多级反馈队列调度程序可由下列参数来定义

队列数量
每个队列的调度算法
用以确定合适升级到更高优先级队列的方法
用以确定进程在需要服务时应进入哪个队列的方法
用以确定进程在需要服务时应进入哪个队列的方法

例如，若一个进程总共需运行100个时间片

初始时指定它在优先级最高的进程组中，很快就会在CPU上运行一个时间片，之后优先级也降低一个级别
当它第二次有机会在CPU上运行时，它将运行2t
以后它将在CPU上运行的时间长度依次是4，8，16，32和64个t，最后一次运行时，只须64个t中37个 t 就可完成
总共需调度7次。比较单纯的轮转法，节省了93次切换时间

多级反馈队列调度算法的性能

终端型作业用户
◆ 在第一队列中完成，作业短，交互型；
短批处理作业用户
◆ 周期时间较短，通常三个队列即可完成；
长批处理作业用户
◆ 依次在前n个队列中执行，然后再按轮
转方式运行。

基于公平原则的调度算法

主要考虑调度的公平性。

保证调度算法：
➢ 性能保证，而非优先运行；
➢ 如保证处理机分配的公平性（处理机时间为1/n）。

公平分享调度算法：
➢ 调度的公平性主要针对用户而言；
➢ 使所有用户能获得相同的处理机时间或时间比例。

实时调度

实时调度是针对实时任务的调度
实时任务，都联系着一个截止时间
➢ 硬实时HRT任务
➢ 软实时SRT任务
实时调度应具备一定的条件

实现实时调度的基本条件

1. 提供必要的信息（向调度程序提供）

(1) 就绪时间
(2) 开始截止时间和完成截止时间
(3) 处理时间
(4) 资源要求
(5) 优先级

2. 系统处理能力强

⚫ 实时系统中通常都有着多个实时任务
⚫ 若处理机的处理能力不够强，则有可能因处理机忙不过来而使某些实时任务不得到及时处理，从而导致发生难以预料的后果
⚫ 假定系统中有m个周期性的硬实时任务，它们的处理时间可表示为Ci，周期时间表示为Pi，则在单处理机情况下，必须满足下面的限制条件：

3. 采用抢占式调度机制

⚫ 当一个优先权更高的任务到达时，允许将当前任务暂时挂起，而令高优先权任务立即投入运行，这样便可满足该硬实时任务对截止时间的要求。这种调度机制比较复杂
⚫ 对于一些小的实时系统，如果能预知任务的开始截止时间，则对实时任务的调度可采用非抢占调度机制，简化调度程序和对任务调度时所花费的系统开销。
但在设计这种调度机制时，应使所有的实时任务都比较小，并在执行完关键性程序和临界区后，能及时地将自己阻塞起来，以便释放出处理机，供调度程序去调度那种开始截止时间即将到达的任

4. 具有快速切换机制

⚫ 对中断的快速响应能力。对紧迫的外部事件请求中断能及时响应，要求系统具有快速硬件中断机构，还应使禁止中断的时间间隔尽量短，以免耽误时机(其它紧迫任务)
⚫ 快速的任务分派能力。为了提高分派程序进行任务切换时的速度，应使系统中的每个运行功能单位适当的小，以减少任务切换的时间开销

实时调度算法

根据实时任务性质
◼ HRT调度算法
◼ SRT调度算法

根据调度方式
◼ 非抢占式调度算法
◼ 抢占式调度算法

非抢占式调度算法

非抢占式轮转调度算法
◼ 响应时间：数秒至数十秒
◼ 可用于要求不太严格的实时控制系统

非抢占式优先调度算法
◼ 响应时间：数秒至数百毫秒
◼ 可用于有一定要求的实时控制系统

抢占式调度算法

基于时钟中断的抢占式优先级调度
➢ 响应时间：几十毫秒至几毫秒
➢ 可用于大多数实时系统

最早截止时间优先(EDF)调度算法

EDF根据任务的截止时间确定优先级，截止时间越早，优先级越高
既可用于抢占式调度，也可用于非抢占式调度
EDF根据任务的截止时间确定优先级，截止时间越早，优先级越高
既可用于抢占式调度，也可用于非抢占式调度

抢占式EDF例子

最低松弛度优先LLF算法

根据任务的紧急程度（松弛度）确定任务优先级

➢ 紧急程度越高（松弛度越低），优先级越高
➢ 松弛度=必须完成时间－其本身的运行时间－当前时间

主要用在抢占式调度方式中

例子：➢ 两个周期性实时任务A和B，任务A要求每20 ms执行一次，执行时间为10 ms，任务B要求每50 ms执行一次，执行时间为25 m

优先级倒置现象

采用优先级调度和抢占方式，可能产生优先级倒置。现象：高优先级进程被低优先级进程延迟或阻塞。

解决方法：

➢ 制定一些规定，如规定低优先级进程执行后，其所占用的处理机不允许被抢占；
➢ 建立动态优先级继承

死锁

死锁（Deadlock）：指多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，这些进程都将永远不能再向前推进

可重用性资源和可消耗性资源

➢ 可重用性资源：一次只能分配给一个进程，不允许多个进程共享，遵循：
➢ 请求资源 - 使用资源 - 释放资源（大部分资源）。
➢ 可消耗性资源：由进程动态创建和消耗（进程间通信的消息）。

可抢占性和不可抢占性资源

➢ 可抢占性资源：某进程在获得这类资源后，该资源可以再被其他进程或系统抢占，CPU（处理机）和主存区。
➢ 不可抢占资源：当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自行释放，打印机、磁带机。

死锁原因

竞争不可抢占性资源引起死锁

➢ 系统中的不可抢占性资源，由于它们的数量不能满足诸进程运行的需要，会使进程在运行过程中，因争夺这些资源而陷入僵局。

竞争可消耗性资源引起死锁

➢ 临时性资源，是指由一个进程产生，被另一个进程使用一短暂时间后便无用的资源，故也称之为消耗性资源，它也可能引起死锁

进程推进顺序不当引起死锁

➢ 进程推进顺序合法
➢ 进程推进顺序非法

死锁定义

死锁：一组等待的进程，其中每一个进程都持有资源，并且等待着由这个组中其他进程所持有的资源。

如果一个进程集合中的每个进程都在等待只能由该组进程中的其他进程才能引发的事件，那么，该组进程是死锁的。

产生死锁的必要条件

互斥 ➢ 一段时间内某资源只能被一个进程占用。

请求和保持 ➢ 一个至少持有一个资源的进程等待获得额外的由其他进程所持有的资源。

不可抢占 ➢ 一个资源只有当持有它的进程完成任务后才释放。

循环等待

➢ 等待资源的进程之间存在环 {P0, P1, …, Pn} 。
➢ P0 等待P1占有的资源, P1等待P2占有的资源, …, Pn–1等待Pn占有的资源, P0等待Pn占有的资源

资源分配图

略…（懒…）

处理死锁的方法

确保系统永远不会进入死锁状态

➢ 死锁预防
➢ 死锁避免

允许系统进入死锁状态，然后恢复系统

➢ 死锁检测
➢ 死锁恢复

忽略这个问题，假装系统中从未出现过死锁。这个方法被大部分的操作系统采用，包括UNIX

预防死锁

➢ 破坏死锁的四个必要条件中一个或几个。

避免死锁

➢ 在资源动态分配时，防止系统进入不安全状态。

检测死锁

➢ 事先不采取任何措施，允许死锁发生，但及时检测死锁发生。

解除死锁

➢ 检测到死锁发生时，采取相应措施，将进程从死锁状态中解脱出来。

预防死锁

破坏死锁的四个必要条件中的一个或几个

互斥：互斥条件是共享资源必须的，不仅不能改变，还应加以保证

请求和保持：必须保证进程申请资源的时候没有占有其他资源
➢ 要求进程在执行前一次性申请全部的资源，只有没有占有资源时才可以分配资源
➢ 资源利用率低，可能出现饥饿

非抢占：
➢ 如果一个进程的申请没有实现，它要释放所有占有的资源；
➢ 先占的资源放入进程等待资源列表中；
➢ 进程在重新得到旧的资源的时候可以重新开始。

循环等待：对所有的资源类型排序进行线性排序，并赋予不同的序号，要求进程按照递增顺序申请资源。
➢ 如何规定每种资源的序号是十分重要的；
➢ 限制新类型设备的增加；
➢ 作业使用资源的顺序与系统规定的顺序不同；
➢ 限制用户简单、自主的编程。

避免死锁

预防和避免的差别是什么？

死锁 → 四个必要条件
(4个必要条件)→(死锁)
4个必要条件 → 死锁 (不一定)
死锁防止是严格破坏4个必要条件之一，一定不出现死锁；而死锁的避免是不那么严格地限制死锁必要条件的存在，其目的是提高系统的资源利用率。万一当死锁有可能出现时，就小心避免这种情况的发生。

需要附加先验信息：
设一个简单而有效的模型，要求每一个进程声明它所需要的资源的最大数。

死锁避免算法动态检查资源分配状态以确保不会出现循环等待的情况。

资源分配状态定义为可用的与已分配的资源数，和进程所需的最大资源量。

安全状态

➢ 当进程申请一个有效的资源的时候，系统必须确定分配后是安全的。
➢ 如果存在一个安全序列，则系统处于安全态。
➢ 进程序列<P1, P2, …, Pn>是安全的，如果每一个进程Pi所申请的可以被满足
的资源数加上其他进程所持有的该资源数小于系统总数。
⚫ 如果 Pi 需要的资源不能马上获得，那么Pi 等待直到所有的Pi-1进程结束。
⚫ 当Pi-1 结束后， Pi获得所需的资源，执行、返回资源、结束。
⚫ 当Pi结束后， Pi+1获得所需的资源执行，依此类推。

如果一个系统在安全状态，就没有死锁
如果一个系统不是处于安全状态，就有可能死锁
死锁避免 –> 确保系统永远不会进入不安全状态

银行家算法

➢ 针对资源有多个实例
➢ 每一个进程必须事先声明使用的最大量
➢ 当一个进程请求资源，它可能要等待
➢ 当一个进程得到所有的资源，它必须在有限的时间释放它们

银行家算法的数据结构

n为进程的数目， m为资源类型的数目

Available: 长度为 m的向量。如果available[j]=k,那么资源Rj有k个实例有效
Max: n x m 矩阵。如果Max[i,j]=k,那么进程Pi可以最多请求资源Rj的k个实例
Allocation: n x m 矩阵。如果Allocation[i,j]=k,那么进程Pj当前分配了k个资源Rj的实例
Need: n x m 矩阵。如果Need[i,j]=k,那么进程Pj还需要k个资源Rj的实例
Need [i,j] = Max[i,j] – Allocation [i,j]

安全性算法

让Work和Finish作为长度为m和n的向量初始化
Work := Available
Finish [i] = false for i - 1,3, …, n.

查找i
(a) Finish [i] = false
(b) Need[i,j] ≤ Work[j]
If no such i exists, go to step ④.

Work := Work + Allocationi
Finish[i] := true
go to step ②.

如果对所有i的 Finish [i] = true, 则系统处在安全状态

Requesti =进程 Pi 的资源请求向量，如果Requesti [m] = k 则进程 Pi 想要资源类型为Rjm的k个实例

① 如果 Requesti ≤ Needi 转 step 2. 否则报错, 因为进程请求超出了其声明的最大值
② 如果 Requesti ≤ Available, 转 step 3. 否则 Pi 必须等待, 因为资源不可用
③ 假设通过修改下列状态来试着分配请求的资源给进程Pi

;

④ 系统执行安全性算法
◼ 如果系统安全 –> 将资源分配给 Pi
◼ 如果系统不安全 –> Pi 必须等待，恢复原有的资源分配状态

死锁的检测和解除

当系统为进程分配资源时，若未采取任何限制性措施，则系统必须提供检测和解除死锁的手段。为此，系统必须：
保存有关资源的请求和分配信息；
提供一种算法，以利用这些信息来检测系统是否已进入死锁状态。

死锁定理

对于较复杂的资源分配图，可能有多个既未阻塞、又非孤立的进程结点，不同的简化顺序，是否会得到不同的简化图？有关文献已经证明， 所有的简化顺序，都将得到相同的不可简化图。

S为死锁状态的充分条件是：当且仅当S状态的资源分配图是不可完全简化的。该充分条件称为死锁定理。

死锁的解除

抢占资源。从一个或多个进程中抢占足够数量的资源给死锁进程，以解除死锁状态

终止或撤消进程。终止系统中一个或多个死锁进程，直到打破循环环路，使死锁状态消除为止。
➢终止所有死锁进程（最简单方法）
➢逐个终止进程（稍温和方法）

进程终止

中断所有的死锁进程。
一次中断一个进程，直到死锁环消失。
应该选择怎样的中断顺序，使“代价最小”？
➢ 进程的优先级；
➢ 进程需要计算多长时间，以及需要多长时间结束；
➢ 进程使用的资源，进程完成还需要多少资源；
➢ 进程是交互的还是批处理的。

4 进程同步

软件同步机制——Peterson算法

do{
    flag[i] = TRUE;
    turn = j;
    while(flag[j] && turn == j);
    CRITICAL SECTION;
    flag[i] = FALSE;
    remainder section;
}while(TRUE);

Perterson算法可以实现空闲让进、忙则等待、有限等待，但是无法实现让权等待

硬件同步机制

锁

关中断

➢进入锁测试之前关闭中断，完成锁测试并上锁之后才打开中断
➢可有效保证互斥，但存在许多缺点

Test-and-Set指令

boolean TestAndSet(Boolean *lock) 
{
	boolean old = *lock;
	*lock = TRUE;
	return old;
}

➢ 共享数据: boolean lock = FALSE;

➢ 进程

Swap指令

➢ 原子地交换两个变量

void Swap(boolean *a, boolean *b) {
	boolean temp = *a;
	*a = *b;
	*b = temp;
}

➢ 共享数据 (初始化为 false): boolean lock;

➢ 进程

Test-and-Set和Swap都是原子操作

信号量机制

信号量-软件解决方案：
➢ 保证两个或多个代码段不被并发调用
➢ 在进入关键代码段前，进程必须获取一个信号量，否则
不能运行
➢ 执行完该关键代码段，必须释放信号量
➢ 信号量有值，为正说明它空闲，为负说明其忙碌

类型（发展）
➢ 整型信号量 ➢ 记录型信号量 ➢ AND型信号量 ➢ 信号量集

整形信号量

➢ 信号量S-整型变量
➢ 提供两个不可分割的[原子操作]访问信号量

wait(S)：
	while S<=0 ; /*do no-op*/
	S:=S-1;
signal(S)：
	S:=S+1;

➢ Wait(s)又称为P(S)
➢ Signal(s)又称为V(S)
➢ 缺点：进程忙等

记录型信号量:去除忙等的信号量

每个信号量S除一个整数值S.value外，还有一个进程等待队列S.list，存放阻塞在该信号量的各个进程PCB

➢ 信号量只能通过初始化和两个标准的原语PV来访问－－作为OS核心代码执行，不受进程调度的打断
➢ 初始化指定一个非负整数值，表示空闲资源总数（又称为”资源信号量”）－－若为非负值表示当前的空闲资源数，若为负值其绝对值表示当前等待临界区的进程数

typedef struct {
	int value;
	struct process_control_block *list;
}semaphore;

wait、signal操作定义

wait(semaphores *S) { //请求一个单位的资源
	S->value --; //资源减少一个
	if (S->value<0) block(S->list) //进程自我阻塞
}

signal(semaphores *S) //释放一个单位资源
{
	S->value++; //资源增加一个
	if (S->value<=0) wakeup(S->list); //唤醒等待队列中的一个进程
}

AND型信号量

AND型信号量同步的基本思想：将进程在整个运行过程中需要的所有资源，一次性全部分配给进程，待进程使用完后再一起释放。

对若干个临界资源的分配，采用原子操作。

在wait(S)操作中增加了一个“AND”条件，故称之为AND同步，或同时wait(S)操作，即 Swait(Simultaneous wait)。

AND型信号量操作定义

Swait(S1，S2，…，Sn) {
	while (TRUE) {
		if (Si>=1 && … && Sn>=1) {
			for (i =1;i<=n;i++) Si--;；
		break;
	}
	else {
	place the process in the waiting queue associated with the first Si found with Si<1，and set the program count of this process to the beginning of Swait operation
		}
	}
}

Ssignal(S1，S2，…，Sn) {
	while (TRUE) {
		for (i=1 ; i<=n;i++) {
			Si++；
		Remove all the process waiting in the queue associated with Si into the ready queue.
		}
	}
}

信号量集

在记录型信号量中，wait或signal仅能对某类临界资源进行一个单位的申请和释放，当需要对N个单位进行操作时，需要N次wait/signal操作，效率低下

扩充AND信号量：对进程所申请的所有资源以及每类资源不同的资源需求量，在一次P、V原语操作中完成申请或释放
➢ 进程对信号量Si的测试值是该资源的分配下限值ti，即要求Si≥ti，否则不予分配。一旦允许分配，进程对该资源的需求值为di，即表示资源占用量，进行Si= Si-di操作
➢ Swait(S1，t1，d1，…，Sn，tn，dn)
➢ Ssignal(S1，d1，…，Sn，dn)

信号量的应用

利用信号量实现进程互斥

设置互斥信号量(mutex)

利用信号量实现前驱关系

利用信号量实现进程同步

设置同步信号量

利用信号量实现进程互斥

semaphore mutex; 
    mutex=1; // 初始化为1
    while(1) {
    wait(mutex);
    临界区；
    signal(mutex);
    剩余区；
}

利用信号量实现进程同步

➢ 实现各种同步问题
➢ 例子：P1和 P2 需要代码段 C1 比C2先运行
semaphores s=0; //主要用于传递消息

P1()
{
    C1;
    signal(s);
    …
}

P2()
{
    …
    wait(s); 
    C2;
}	

利用信号量实现前趋关系

main(){
    Semaphore a,b,c,d,e,f,g; 
    a.value=0;b.value=0;c.value=0;
    d.value=0;e.value=0;f.value=0;g.value=0;
    cobegin
        { S1;signal(a);signal(b); }
        { wait(a);S2;signal(c) ;signal(d);}
        { wait(b);S3;signal(e); }
        { wait(c);S4;signal(f); }
        { wait(d);S5;signal(g); }
        { wait(e);wait(f);wait(g);S6; }
	coend
}

管程机制

信号量机制的问题

➢需要程序员实现，编程困难
➢维护困难
➢容易出错
⚫ wait/signal位置错
⚫ wait/signal不配对

解决方法 ➢由编程语言解决同步互斥问题 ➢管程（1970s, Hoare和 Hansen）

信号量：分散式
管程：集中式

管程定义

➢ 一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据

语法描述如下：

Monitor monitor_name { /*管程名*/
    share variable declarations； /*共享变量说明*/
    condition declarations； /*条件变量说明*/
    public: /*能被进程调用的过程*/
        void P1(……) {……} /*对数据结构的操作过程*/
        void P2(……) {……}
        ……
        void (……) {……}
        ……
    { /*管程主体*/ 
    initialization code; /*初始化代码*/ 
    ……
    }
}

管程功能

互斥
➢管程中的变量只能被管程中的操作访问
➢任何时候只有一个进程在管程中操作
➢类似临界区
➢由编译器完成

同步
➢条件变量
➢唤醒和阻塞操作

条件变量

condition x, y;

条件变量的操作
➢ 阻塞操作：wait
➢ 唤醒操作：signal

x.wait(): 进程阻塞直到另外一个进程调用x.signal()

x.signal()：唤醒另外一个进程

问题

管程内可能存在不止1个进程。 ➢例如：进程P调用 signal操作唤醒进程 Q后。

存在的可能处理方式：
➢P等待，直到Q离开管程或等待另一条件（Hoare）。
➢Q等待，直到P离开管程或等待另一条件（Hansen）。

经典进程同步问题

生产者-消费者问题

生产者-消费者问题是相互合作进程关系的一种抽象

利用记录型信号量实现：
➢ 假定，在生产者和消费者之间的公用缓冲池中，具有n个缓冲区，可利用互斥信号量mutex使诸进程实现对缓冲池的互斥使用；
➢ 利用资源信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。
➢ 又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息

其它解决方案：AND信号集、管程

问题描述

➢ 生产者（M个）：生产产品，并放入缓冲区
➢ 消费者（N个）：从缓冲区取产品消费
➢ 问题：如何实现生产者和消费者之间的同步和互斥？

生产者消费者流程

生产者：
{ 
    …
    生产一个产品
    …
    …
    把产品放入指定缓冲区
    …
}

消费者：
{ 
    …
    …
    从指定缓冲区取出产品
    …
    …
    消费取出的产品
    …
}

生产者消费者的互斥分析

生产者

➢把产品放入指定缓冲区
➢in:所有的生产者对in指针需要互斥
➢counter：所有生产者消费者进程对counter互斥

buffer[in] = nextp;
in = (in + 1) % N;
counter++;

消费者

➢从指定缓冲区取出产品
➢out:所有的消费者对out指针需要互斥
➢counter：所有生产者消费者进程对counter互斥

nextc = buffer[out];
out = (out + 1) % N;
counter--;

两者需要协同的部分
➢ 生产者：把产品放入指定缓冲区（关键代码C1）
➢ 消费者：从满缓冲区取出一个产品（关键代码C2）

三种运行次序（不同条件下不同运行次序）
➢ 所有缓冲区空时：
➢ 所有缓冲区满时：
➢ 缓冲区有空也有满时：

同步信号量定义

共享数据
semaphore **full, empty, *mutex; //full:满缓冲区数量 empty：空缓冲区数量

初始化:
full->value = 0; empty->vaule = N; mutex->vaule = 1；

do {
    // produce an item in nextp
    wait (empty);
    wait (mutex);
    // add the item to the buffer
    signal (mutex);
    signal (full);
} while (TRUE)

do {
    // produce an item in nextp
    wait (empty);
    wait (mutex);
    // add the item to the buffer
    signal (mutex);
    signal (full);
} while (TRUE)

解读见PPT

利用AND信号量解决生产者-消费者问题

int in=0,out=0;
item buffer[n];
semaphore mutex=1,empty=n,full=0;

void producer() {
    do {
        produce an item nextp; 
        …
        Swait(empty，mutex)；
        buffer[in]= nextp;
        in = (in+1) % n;
        Ssignal(mutex,full);
    }while(TRUE);
}

void consumer() {
do {
    Swait(full,mutex);
    nextc=buffer[out];
    out= (out+1) % n;
    Ssignal(mutex,empth);
    consume the item in nextc; 
    …
    }while(TRUE);
}

利用管程解决生产者-消费者问题

Monitor producerconsumer { 
item buffer[N];
int in,out;
condition notfull,notempty;
int count;
    
public: 
    void put(item x) {
        if (count>=N) cwait(notfull)；
        buffer[in] = x；
        in = (in+1) % N；
        count++；
        csignal(notempty);
    }
    
    void get(item x) {
        if (count<=0) cwait(notempty)；
        x = buffer[out]；
        out = (out+1) % N；
        count--；
        csignal(notfull);
        }
        { 
        in=0;out=0;count=0;
        }
    }PC;
	
	void producer() {
        item x;
        while(TRUE) {
            ……
            produce an item in nextp；
            PC.put(x)；
        }
    }

    void consumer() {
    	item x;
        while(TRUE) {
            PC.get(x)；
            consume the item in nextc；
            ……
            }
	}

    void main() {
        cobegin
        producer(); consumer();
        coend
    }

哲学家进餐问题

五个哲学家的生活方式：交替思考和进餐共用一张圆桌，分别坐在五张椅子上在圆桌上有五个碗和五支筷子平时哲学家思考，饥饿时便试图取用其左、右最靠近他的筷子，只有在拿到两支筷子时才能进餐进餐毕，放下筷子又继续思考
➢ 解决方案：  记录型信号量；  AND信号量集、管程。

利用记录型信号量

Semaphore chopstick[5] = {1,1,1,1,1}; // array [0..4] of semaphores;
    Philosopher i:
        do {
            wait(chopStick[i]); // get left chopstick
            wait(chopStick[(i + 1) % 5]); // get right chopstick
            …
            // eat
            …
            signal(chopStick[i]); //return left chopstick
            signal(chopStick[(i + 1) % 5]); // return right chopstick
            …
            // think
            …
		} while (true) 

存在问题及解决方案

可能引起死锁，如五个哲学家同时饥饿而各自拿起左筷子时，会使信号量 chopstick均为 0 ；因此他们试图去拿右筷子时，无法拿到而无限期等待。

解决方法：
① 最多允许4个哲学家同时坐在桌子周围
② 仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子。
③ 给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之

利用AND信号量

semaphore chopstick chopstick[5]={1,1,1,1,1}；
do {
    …
    //think
    …
    Sswait(chopstick[(i+1)%5]，chopstick[i])；
    …
    //eat
    …
    Ssignal(chopstick[(i+1)%5]，chopstick[i])；
} while[TRUE]；

利用管程

monitor dp
{ 
enum { THINKING; HUNGRY, EATING) state [5] ;
condition self [5];

void pickup (int i) { 
    state[i] = HUNGRY;
    test(i);
    if (state[i] != EATING) self [i].wait;
}
      
void putdown (int i) { 
    state[i] = THINKING;
    	// test left and right neighbors
    test((i + 4) % 5);
    test((i + 1) % 5);
}
      
void test (int i) { 
    if ( (state[(i + 4) % 5] != EATING) &&
    (state[i] == HUNGRY) &&
    (state[(i + 1) % 5] != EATING) ) { 
        state[i] = EATING ;
        self[i].signal () ;
    }
}

initialization_code() { 
    for (int i = 0; i < 5; i++)
    state[i] = THINKING;
    }
}

哲学家i的活动可描述为：
do {
    dp.pickup (i);
    …
    eat
    …
    dp.putdown (i);
} while[TRUE];