第二章 进 程 管 理 2.1 前趋图和程序执行 2.2 进程的描述 2.3 进程控制 2.4 进程同步 2.5 经典进程的同步问题

Presentation on theme: "第二章 进 程 管 理 2.1 前趋图和程序执行 2.2 进程的描述 2.3 进程控制 2.4 进程同步 2.5 经典进程的同步问题"— Presentation transcript:

1 第二章 进 程 管 理 2.1 前趋图和程序执行 2.2 进程的描述 2.3 进程控制 2.4 进程同步 2.5 经典进程的同步问题
第二章　进 程 管 理 2.1　前趋图和程序执行 2.2　进程的描述 2.3 进程控制 2.4　进程同步 2.5　经典进程的同步问题 2.6 进程通信 2.7　线程的基本概念 2.8 线程的实现

2 2.1前趋图和程序执行 2.1.1　前趋图 　前趋图(Precedence Graph)：有向无循环图，用于描述程序段（进程)之间执行的前后关系。 结点:用于描述一个程序段或进程，乃至一条语句。 有向边：用于表示两个结点之间存在的前趋关系，用“→”表示。

3 如有Pi→Pj，则称Pi是Pj的直接前趋，而称Pj是Pi的直接后继。 初始结点：没有前趋的结点。 终止结点：没有后继的结点。
重量：用于表示该结点所含有的程序量或结点的执行时间。 例如前面图2-1就是一个前趋关系图。 注意：前趋图中必须不存在循环。

4 P={P1，P2，P3，P4，P5，P6，P7，P8，P9}→={(P1，P2)，(P1，P3)，(P1，P4)，
例题：若有以下前趋关系：P1→P2，P1→P3，P1→P4，P2→P5，P3→P5，P4→P6，P4→P7，P5→P8，P6→P8，P7→P9，P8→P9，求其前趋图。 解：题中前趋关系也表示为：　　 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)} 则前趋图如下所示：

5 图 2-1　具有9节点的前趋图

6 例：某一具有下述四条语句的程序段，求其前趋图。 S1: a:=x+2 S2: b:=y+4 S3: c:=a+b S4: d:=c+b
图 2-2　四条语句的前趋关系

7 一个应用程序可分成若干个程序段，在各程序段之间必须按照某种先后次序顺序执行。例如下述三条语句的程序段:
2.1.2　程序的顺序执行 　1. 程序的顺序执行 　　一个应用程序可分成若干个程序段，在各程序段之间必须按照某种先后次序顺序执行。例如下述三条语句的程序段: S1: a:=x+y； S2: b:=a-5； S3:c:=b+1； 其执行顺序： 图 2-3　程序的顺序执行

8 处理机的操作严格按照程序所规定的顺序执行。 (2) 封闭性： 即程序运行时独占全机资源，程序一旦开始执行，其执行结果不受外界因素影响。
　　 2. 程序顺序执行时的特征 (1) 顺序性： 处理机的操作严格按照程序所规定的顺序执行。 (2) 封闭性： 即程序运行时独占全机资源，程序一旦开始执行，其执行结果不受外界因素影响。 (3) 可再现性： 只要程序执行时的环境、条件相同，当程序重复执行时，都将获得相同的结果。

9 2.1.3　程序的并发执行及其特征 　　1．程序的并发执行 　　若多个程序中的每一个都划分为输入程序Ii 、计算程序Ci和打印程序Pi,则三者之间，存在着Ii→Ci→Pi这样的前趋关系，在对一批程序进行处理时，可使它们并发执行。如图2-4示出。

10 Pi-1、Ci、Ii+1之间，可以并发执行。
图2-4 并发执行时的前趋图 Pi-1、Ci、Ii+1之间，可以并发执行。

11 　　2．程序并发执行时的特征 　　1) 间断性 　　程序在并发执行时，由于它们共享系统资源，以及为完成同一项任务而相互合作，致使在这些并发执行的程序之间，形成了相互制约（即有时序性）的关系。相互制约将导致并发程序具有“执行—暂停—执行”这种间断性的活动规律。

12 程序在并发执行时，由于失去了封闭性，也将导致其再失去可再现性。
　　2) 失去封闭性 　　程序在并发执行时，是多个程序共享系统中的各种资源，因而这些资源的状态将由多个程序来改变，致使程序的运行失去了封闭性。 3) 不可再现性 　　程序在并发执行时，由于失去了封闭性，也将导致其再失去可再现性。

13 若三程序以不同的速度运行。则可能出现下述三种情况(假定某时刻变量N的值为n)。 (1) A B1 B2，得到的N值分别为n+1，n+1，0。
　　例如，有循环程序A、B1、B2，它们共享一个变量N。 A: N:=N+1 B1: Print(N) B2: N:=0 若三程序以不同的速度运行。则可能出现下述三种情况(假定某时刻变量N的值为n)。 (1) A B1 B2，得到的N值分别为n+1，n+1，0。 (2)B1 B2 A，此时得到的N值分别为n，0，1。 (3)B1 A B2，此时得到的N值分别为n，n+1，0。 因此，多程序不能进行并发执行。

14 2.2　进程的描述 2.2.1 进程的定义和特征 1. 进程的定义 　 在多道程序环境下，程序不能并发执行。为使程序能并发执行，且为了对并发执行的程序加以描述和控制，引入了“进程”的概念。 进程定义：是进程实体的运行过程，系统进行资源分配和调度的一个独立单位。

15 OS对进程的管理主要通过进程控制块PCB(Process Control Block)。
进程的结构 进程实体组成 程序段 数据段 PCB OS对进程的管理主要通过进程控制块PCB(Process Control Block)。 PCB是特殊的数据结构，记录了进程的各种信息，是进程存在的唯一标识。

16 进程的实质是进程实体的一次执行过程，因此，动态性是进程的最基本的特征。
　2.进程的特征　 1) 动态性 　进程的实质是进程实体的一次执行过程，因此，动态性是进程的最基本的特征。 “由创建而产生，由调度而执行，由撤消而消亡”。 进程实体有一定的生命期。

17 多个进程实体同存于内存中，且能在一段时间内同时运行。
2) 并发性 多个进程实体同存于内存中，且能在一段时间内同时运行。 是OS引入进程的目的。 3) 独立性 　进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位。 4）异步性

18 思考：阻塞是主动行为还是被动行为？ 2.2.2 进程的基本状态及转换 1) 就绪(Ready)状态 就绪队列。 2) 执行状态
　就绪队列。 2) 执行状态 　进程获得CPU正在执行。 3) 阻塞状态/等待状态/封锁状态 　正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃处理机而处于暂停状态，亦即进程的执行受到阻塞。 阻塞队列（可能有多个）。 思考：阻塞是主动行为还是被动行为？

19 2.三基态间转换 图2-5 进程的三种基本状态及其转换

20 （1）为新进程创建PCB，并填写必要的管理信息；（进行到此步为创建状态） （2）把该进程转入就绪状态并插入就绪队列之中。 2) 终止状态
3．创建状态和终止状态 1) 创建状态 　创建进程步骤： （1）为新进程创建PCB，并填写必要的管理信息；（进行到此步为创建状态） （2）把该进程转入就绪状态并插入就绪队列之中。 2) 终止状态 　进程终止步骤： （1）操作系统进行善后处理； （2）将其PCB清零，并将PCB空间返还系统。

21 图2-6 进程的五种基本状态及转换

22 当系统中的工作负荷较重时把一些不重要的进程挂起。 (4)操作系统的需要。 操作系统挂起某些进程，以便检查运行中的资源使用情况或进行记账。
挂起操作和进程状态转换 1.引入挂起状态的原因 　 (1)终端用户的请求。 程序调试、检测。 (2)父进程请求。 父进程修改子进程或协调各子进程间活动。 　 (3)负荷调节的需要。 当系统中的工作负荷较重时把一些不重要的进程挂起。 　 (4)操作系统的需要。 操作系统挂起某些进程，以便检查运行中的资源使用情况或进行记账。

23 活动就绪 静止就绪 活动阻塞 静止阻塞 2.进程状态的转换 挂起状态/静止状态 非挂起状态/活动状态 挂起 某事件发生 激活
　2.进程状态的转换 　　挂起状态/静止状态 非挂起状态/活动状态　　 活动就绪 静止就绪 活动阻塞 静止阻塞 某事件发生 挂起 激活

24 图 2-7　具有挂起状态的进程状态图

25 图2-8 双挂起6状态进程模型

26 2.2.4进程管理中的数据结构 1.OS中用于管理控制的数据结构（了） 2.进程控制块的作用
　 是进程实体的一部分，是操作系统中最重要的记录型数据结构。 PCB中记录了操作系统所需的、用于描述进程的当前情况以及控制进程运行的全部信息。 OS是根据PCB来对并发执行的进程进行控制和管理的。 PCB是进程存在的惟一标志。

27 3．进程控制块中的信息 ①内符：系统 1)进程标识符 ②外符：用户 ①进程状态 ②进程优先级 2)进程调度信息 ③与调度有关的其他参数
PCB 1)进程标识符 ②外符：用户 2)进程调度信息 ①进程状态 ②进程优先级 3)进程控制信息 ①程序、数据地址 ②进程通信、同步机制 ④链接指针 4)处理机信息 ③与调度有关的其他参数 ④事件（阻塞原因） ③资源清单

28 4. 进程控制块的组织方式 1）线性方式:PCB存放在一张线性表里 2) 链接方式 图 2-9 PCB链接队列示意图
2) 链接方式　 图 2-9　PCB链接队列示意图

29 2) 索引方式　 图 2-10　按索引方式组织PCB

30 2.3 进 程 控 制 1.创建进程 进程控制 2.进程状态转换 3.终止进程 进程控制一般是由OS的内核中的原语来实现的。
2.3　进 程 控 制 进程控制 1.创建进程 2.进程状态转换 3.终止进程 进程控制一般是由OS的内核中的原语来实现的。

31 原子操作：指一个操作中的所有动作要么全做，要么全不做。是一个不可分割的基本单位。 原子操作在管态下执行，常驻内存。
　　2.3.1操作系统内核(了） 原语：由若干条指令组成用于完成一定功能的一个过程。用于实现进程的通信和控制。 原语与一般过程的区别：原语是原子操作。 原子操作：指一个操作中的所有动作要么全做，要么全不做。是一个不可分割的基本单位。 原子操作在管态下执行，常驻内存。 CPU执行状态 管态/系统态/特权态/核心态 目态/常态/用户态

32 2.3.2 进程的创建 1.进程层级结构 2．进程图 描述一个进程家族关系的有向树。 图2-11 进程树
2.3.2　进程的创建 1.进程层级结构 2．进程图 　　描述一个进程家族关系的有向树。 图2-11 进程树

33 3．引起创建进程的事件 (1) 用户登录。 分时系统中增加新用户。 (2) 作业调度。 (3) 提供服务。 (4) 应用请求。 系统创建
　(1) 用户登录。 分时系统中增加新用户。 　(2) 作业调度。 (3) 提供服务。 (4) 应用请求。 系统创建 用户进程自行创建

34 4．进程的创建过程 调用进程创建原语Creat( ) 。 (1)申请空白PCB。 (2)为新进程分配资源。 主要是内存资源
①初始化标识信息 ②初始化处理机状态信息 ③初始化处理机控制信息 使程序计数器指向程序的入口地址 栈指针指向栈顶 设置进程状态为就绪 设置进程优先级为最低级 (4)将新进程插入就绪队列

35 2.2.3 进程的终止 1．引起进程终止的事件 1)正常结束
2.2.3　进程的终止 1．引起进程终止的事件 　1)正常结束 　　在程序结尾一般有一个用于表示进程已经运行完成的指令。当运行到该指令时，将产生一个中断去通知OS本进程已经完成。 2)异常结束 　　运行中出现某些错误和故障 (1)越界错误。 所访问的存储区超出。

36 (2)保护错。 进程对资源的访问方式不当。 (3)非法指令。 进程试图去执行一条不存在的指令。 (4)特权指令错。
进程试图去执行OS的指令。 　(5)运行超时。 进程的执行时间超过了指定的最大值。

37 进程等待某事件的时间超过了规定的最大值。 (7)算术运算错。 进程试图去执行错误的运算。 (8)I/O故障。 在I/O过程中发生了错误等。
(6)等待超时。 进程等待某事件的时间超过了规定的最大值。 (7)算术运算错。 进程试图去执行错误的运算。 (8)I/O故障。 在I/O过程中发生了错误等。

38 由于某种原因，例如，发生了死锁，由操作员或操作系统终止该进程。 (2) 父进程请求。 (3) 父进程终止。
3) 外界干预 　指进程应外界的请求而终止运行。 　(1) 操作员或操作系统干预。 由于某种原因，例如，发生了死锁，由操作员或操作系统终止该进程。 　(2) 父进程请求。 　(3) 父进程终止。

39 OS调用进程撤销原语destroy()。 (1)根据进程标识符，检索出该进程的PCB，从中读出该进程的状态。
2．进程的终止过程 OS调用进程撤销原语destroy()。 　(1)根据进程标识符，检索出该进程的PCB，从中读出该进程的状态。 　(2)若被终止进程正处于执行状态，应立即终止该进程的执行，并重新进行调度。 (3)终止所有子孙进程。 　(4)将全部资源归还给其父进程或系统。 　(5)将被终止进程(PCB)从所在队列(或链表)中移出。

40 2.3.4 进程的阻塞与唤醒 1)等待资源 2)等待I/O 3)新数据尚未到达 4)无新工作可做 如系统中的发送、接受进程。
2.3.4　进程的阻塞与唤醒 1. 引起进程阻塞和唤醒的事件 　1)等待资源 　2)等待I/O 3)新数据尚未到达 4)无新工作可做 如系统中的发送、接受进程。

41 注：block原语和wakeup原语是一对相反的原语，需成对出现。
1)立即停止执行，改变PCB中状态信息 2）将进程放入阻塞队列中 3．进程唤醒过程（wakeup原语过程） 1)把被阻塞的进程从等待该事件的阻塞队列中移出 2)将其PCB中的现行状态由阻塞改为就绪 3)将该PCB插入到就绪队列中 注：block原语和wakeup原语是一对相反的原语，需成对出现。 PC

42 2.3.5 进程的挂起与激活 1．进程挂起的原因（回忆） 1）终端用户请求 2）父进程请求 3）负荷调节需要
2.3.5　进程的挂起与激活 1．进程挂起的原因（回忆） 1）终端用户请求 2）父进程请求 3）负荷调节需要 2.挂起过程（Suspend原语过程） 1）查PCB状态信息，由活动状态改为静止状态。思考：进程能否由执行到挂起？ 2）将PCB中信息复制到内存指定区域。 3）将进程移除内存。 思考：为何要复制PCB中信息到内存？

43 注： Suspend原语和Active原语是一对相反的原语，需成对出现。
　 1)将进程从外存调入内存 2)检查PCB状态，由静止改为活动，并送入相应队列。 3)若进入就绪队列，则与当前进程比较优先级的。 注： Suspend原语和Active原语是一对相反的原语，需成对出现。

44 2.4 进 程 同 步 OS管理进程同步时主要做两个工作： 1.保证多个进程互斥的访问临界资源。
2.4　进 程 同 步 OS管理进程同步时主要做两个工作： 1.保证多个进程互斥的访问临界资源。 2.协调多进程间执行顺序，以实现程序可再现性。

45 进程同步机制 软、硬件方法 信号量 机制 整型信号量 记录型信号量 信号量集 管程机制 AND型信号量集 一般型信号量集

46 2.4.1 进程同步的基本概念 1．并发进程两种关系 (1)共享资源（间接关系、互斥）。 (2)相互合作（直接关系、同步）。
2.4.1　进程同步的基本概念 1．并发进程两种关系 (1)共享资源（间接关系、互斥）。 (2)相互合作（直接关系、同步）。 2. 临界资源：互斥共享 以生产者-消费者问题为例分析为何要互斥共享临界资源。

47 假设由若干个缓冲区首尾相连形成一个环形缓冲区，由生产者进程生产产品放入缓冲区中，由消费者从缓冲区中取走产品。
　　生产者-消费者(producer-consumer)问题：有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。 假设由若干个缓冲区首尾相连形成一个环形缓冲区，由生产者进程生产产品放入缓冲区中，由消费者从缓冲区中取走产品。 过程中遵守的原则： ①若缓冲区中产品满则不能再生产产品放入缓冲区； ②若缓冲区空则不能从缓冲区中取走产品消费

48 1 2 in out 简化问题，形成模型： 每生产一个产品，in的下个取值为 in:=(in+1)mod 3
1 2 in out 假设：3个缓冲区2个指针1个变量 in:指向存放产品的缓冲区。 out:指向取产品的缓冲区。 counter:每生产一个产品值+1； 每取走一个产品，值-1 in/out初值设为1，可能取值0、1、2 每生产一个产品，in的下个取值为 in:=(in+1)mod 3 in,out重逢时可能有两种情况： 1）in=out,缓冲池空 2）(in+1)mod 3=out，缓冲区满

49 P-C问题描述： 1)两进程公用变量： nextp:P进程，存放每次刚生产出来的产品； nextc：C进程，存放每次要消费的产品。
Var n：integer； type item=…； var buffer: array[0，1，…，n-1]of item； in，out: 0，1，…，n-1； counter: 0，1，…，n； 2)两进程局部变量 nextp:P进程，存放每次刚生产出来的产品； nextc：C进程，存放每次要消费的产品。

50 produce an item in nextp；
producer: repeat produce an item in nextp； while counter=n do no-op； buffer［in］:=nextp； in:=(in+1)mod n； counter:=counter+1； until false； … …

51 while counter=0 do no-op； nextc:=buffer［out］； out:=(out+1) mod n；
consumer: repeat 　 　　 while counter=0 do no-op； 　　　　　nextc:=buffer［out］； 　　　　　out:=(out+1) mod n； 　　　　　counter:=counter-1； 　　　　　consumer the item in nextc； 　　　　 until false； …

52 A:register1:=counter； B:register1:=register1+1； C:counter:=register1；
加1操作过程 A:register1:=counter； B:register1:=register1+1； C:counter:=register1； 消费者进程对counter 减1操作过程 D:register2:=counter； E:register2:=register2-1； F:counter:=register2；

53 1)若先P进程再C进程则共享变量counter的值仍为5； 2)若先C进程再P进程则counter值也还是5;
3)若按下述顺序执行：A,B,D,E,C,F ，则counter的值是4； 4)若按下述顺序执行：A,B,D,E,F,C,则counter的值是6； 程序失去了再现性。解决此问题的关键是应把变量counter作为临界资源处理，亦即，令生产者进程和消费者进程互斥地访问变量counter。

54 3．临界区 访问临界资源的进程可分为四个部分： 用于检查临界资源状态 进入区 用于访问临界资源 临界区 退出区 退出临界资源并设立标识
剩余区 退出临界资源并设立标识

55 访问临界资源的循环进程描述如下： repeat entry section critical section； exit section
　　　　remainder section； 　　until false；

56 4．同步机制应遵循的规则（临界区管理原则） (1)空闲让进。 (2)忙则等待。 (3)有限等待。 避免“死等”状态。 (4)让权等待。
避免“忙等”状态。 补:(5)有限时间使用。

57 2.4.2 硬件同步 补充：5.互斥与同步的关系 1.关中断 2.利用test-and-set(ts指令） 3.利用swap指令 1)区别：
互斥：联系松散,取用资源随机,有则用； 同步：联系紧密，按序执行，有资源也不一定能用； 2)联系： 都是进程间的相互制约关系，互斥是特殊的同步，二者统称为进程同步。 2.4.2 硬件同步 1.关中断 2.利用test-and-set(ts指令） 3.利用swap指令

58 2.4.3 信号量机制 最初由Dijkstra提出。 1．整型信号量
2.4.3　信号量机制 最初由Dijkstra提出。 1．整型信号量 　　定义整型信号量S，表示资源数目初值为1。与一般整型量不同，S仅能通过原子操作wait(S)和signal(S)来访问。 早期这两个操作一直被分别称为P、V操作，执行时不可中断。 S ≥0时代表可用资源数 ＜0时代表等待资源的进程数

59 V(S)描述： P操作：申请资源 1)若S ≤0，不做任何操作； 2)若S>0,可进入临界区，同时S自减1变为0，为临资加锁；
　　while S<=0 do no-op； 　　S:=S-1； V操作：释放资源 1)退出临界区；　 2)S自加1，解锁； V(S)描述： S:=S+1；

60 临资互斥访问:s在0和1之间变化 P(S) 临界区 V(S) 整型信号量的缺点： 1）让进程处于忙等状态 2）对于等待的进程没有相应操作
改进思想：增加阻塞、唤醒原语。

61 记录型信号量是由于它采用了记录型的数据结构而得名的。它包含两个数据项： S.value:代表资源数量。 S.L：指向阻塞队列的指针。
2．记录型信号量 记录型信号量是由于它采用了记录型的数据结构而得名的。它包含两个数据项： S.value:代表资源数量。 S.L：指向阻塞队列的指针。 type semaphore=record 　　　　　　　value: integer； 　　　　　　　L: list of process； 　　　　　　　end

62 wait(S)和signal(S)操作可描述为： procedure P(S) var S：semaphore； begin
　　　　S.value:=S.value-1； 　　　　if S.value<0 then block(S.L)； 　　　end procedure V(S) 　　　var S: semaphore； 　　　　begin 　　　　　S.value:=S.value+1； 　　　　　if S.value<=0 then wakeup(S.L)； 　　　　end 整型、记录型信号量用于申请单个临资。

63 当系统中多个进程共同访问多个临资时会发生资源抢夺现象导致“死锁”。
3．AND型信号量集 　　当系统中多个进程共同访问多个临资时会发生资源抢夺现象导致“死锁”。 临资1 P1 P2 临资2 解决方法：对若干个临界资源的分配，采取原子操作方式：要么把它所请求的资源全部分配到进程，要么一个也不分配。 在wait操作中，增加了一个“AND”条件，故称为AND同步，或称为同时wait操作，即Swait。

64 if S1>=1 and … and Sn>=1 then for i:=1 to n do Si:=Si-1； endfor
Swait(S1，S2，…，Sn) 　if S1>=1 and … and Sn>=1 then 　　for i:=1 to n do 　　　 Si:=Si-1； 　　endfor 　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. 　endif

65 Ssignal(S1，S2，…，Sn) for i:=1 to n do Si:=Si+1；
Remove all the process waiting in the queue associated with Si into the ready queue. endfor； 缺点： 1)一次能申请多类资源，但每类只能申请一。 2)有些资源当数量低于某个限制数则不能再进行分配，AND信号量不能实现。

66 　　4．一般信号量集 　 对AND信号量机制加以扩充，形成一般化的“信号量集”机制。Swait操作可描述如下，Swait(… Si ，ti，di，…，)其中S为信号量，t为下限值，而d为需求值。

67 Swait(S1，t1，d1，…，Sn，tn，dn) if Si>=t1 and … and Sn>=tn then
　　for i:=1 to n do 　　　Si:=Si-di； 　　endfor 　else 　　Place the executing process in the waiting queue of the first Si with Si<ti and set its program counter to the beginning of the Swait Operation. endif

68 Ssignal(S1，d1，…，Sn，dn) for i:=1 to n do Si:=Si+di；
　　Remove all the process waiting in the queue associated with Si into the ready queue 　endfor；

69 每次申请d个资源，当现有资源数少于d时不予分配。 (2)Swait(S，1，1)。 当S>1时，记录型信号量；
一般“信号量集”的几种特殊情况： (1)Swait(S，d，d)。 每次申请d个资源，当现有资源数少于d时不予分配。 (2)Swait(S，1，1)。 当S>1时，记录型信号量； 当S=1时，互斥信号量。 (3)Swait(S，1，0)可控开关。 当S≥1时，允许多个进程进入某特定区； 当S=0时，阻止任何进程进入特定区。

70 2.4.4　信号量的应用 1．利用信号量实现进程互斥 　 为临界资源设置一互斥信号量mutex，并设其初始值为1，然后将各进程访问该资源的临界区CS置于wait(mutex)和signal(mutex)操作之间即可。利用信号量实现进程互斥的进程可描述如下：

71 Var mutex: semaphore:=1； begin parbegin process 1: begin repeat
　　　　　　 wait(mutex)；<p(s)> 　　　　　　 critical section 　　　　　　 signal(mutex)；<v(s)> 　　　　　　 remainder section 　　　　　 until false； 　　　　 end

72 process 2: begin repeat wait(mutex)； critical section signal(mutex)；
　　　　remainder section 　　 until false； 　 end parend 注：用于互斥操作时P,V必须成对出现在同一个进程中。

73 2．利用信号量实现前趋关系(同步）

74 a b c d e f g 图2-12 前趋图举例

75 Var a,b,c,d,e,f,g semaphore:=0,0,0,0,0,0,0； begin parbegin
　　 begin S1；signal(a)；signal(b)；end； 　　 begin wait(a)；S2；signal(c) signal(d)； end； 　　 begin wait(b)；S3；signal(e)；end； 　　 begin wait(c)；S4；signal(f)；end； 　　 begin wait(d)；S5；signal(g)；end； 　　 begin wait(e)；wait(f)；wait(g)；S6 　 parend end

76 2.4.5 管程机制 管程的引入原因 1．管程的定义： 把资源以数据结构的形式抽象化，把对资源的操作以过程、函数的形式加以定义。
2.4.5　管程机制 管程的引入原因 1．管程的定义： 把资源以数据结构的形式抽象化，把对资源的操作以过程、函数的形式加以定义。 定义：代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序，共同构成了一个操作系统的资源管理模块，称之为管程。

77 　 进程对共享资源的申请、释放和其它操作，都是通管程来实现的，管程还可以根据资源的情况，或接受或阻塞进程的访问，确保每次仅有一个进程使用共享资源，这样就可以统一管理对共享资源的所有访问，实现进程互斥。
管程被请求和释放资源的进程所调用。

78 ① 管程的名称； 管程组成 ② 管程内共享变量声明； ③ 管程内过程声明； ④ 管程内变量初始化语句；

79 图2-13　管程的示意图

80 type monitor_name = MONITOR； <共享变量说明>； define <过程名列表>；
管程的语法描述如下： 　　type monitor_name = MONITOR； <共享变量说明>； define <过程名列表>； use <过程名列表>； procedure <过程名>(<形式参数表>)； begin end; …

81 function <函数名>(<形式参数表>)：值类型； begin end；
end； <管程的局部数据初始化语句序列>； end …

82 　　管程内变量仅能被管程内过程访问；反之，管程内的过程也仅能访问管程内的变量。
管程相当于围墙，它把管程内的变量和对变量操作的干过程围了起来，所有进程要访问临界资源时，都必须经过管程才能进入，而管程每次只准许一个进程进入管程，从而实现了进程互斥。

83 (1)模块化。管程是一个基本程序单位，可以单独编译。
管程主要有以下特性： 　　 (1)模块化。管程是一个基本程序单位，可以单独编译。 　(2)数据类型抽象化。管程中不仅有数据，而且有对数据的操作。 　(3)信息掩蔽。管程内的变量和过程对于调用管程的进程而言是透明的。

84 (1)二者数据结构不同:进程的PCB是私有数据结构，管程的是公共数据结构；
　　管程和进程不同： 　　(1)二者数据结构不同:进程的PCB是私有数据结构，管程的是公共数据结构； 　　(2)二者操作不同:进程是程序执行有关的操作，管程主要是同步操作和初始化操作； 　　(3)二者设置的目的不同:进程是为了实现系统的并发性，管程则是为了解决共享资源的互斥使用； 　

85 (4)二者工作方式不同:进程可调用管程，但反之不可。进程主动，管程被动；
(5)二者并发性不同:进程之间能并发执行，而管程则不能与其调用者并发执行； (6)二者状态不同:进程具有动态性，管程则是操作系统中的一个资源管理模块静态。

86 在利用管程实现进程互斥同步时，必须设置同步工具，如P和V原语。
　2．条件变量 　 在利用管程实现进程互斥同步时，必须设置同步工具，如P和V原语。 若进程调用管程后接着就执行P,V操作易引发的问题：一旦进程阻塞，则管程不能被及时释放，使得其他进程也不能调用管程。 解决办法:增加条件变量。

87 (2)条件变量需要声明，其形式为：Var x，y：condition，只能在管程中使用；
条件变量： (1)条件变量有多个； (2)条件变量需要声明，其形式为：Var x，y：condition，只能在管程中使用； (3)对条件变量的操作仅仅是wait和signal可表示为x.wait和x.signal； (4)每个条件变量保存一个链表，用于记录因该条件变量而阻塞的进程;

88 ②从x条件队列中重新启动一个进程。 若队列空则继续执行原进程，而不产生任何结果；
条件变量的P,V操作过程： 1)x.p： ①x条件不满足时调用x.p； ②将进程插入到等待x条件的队列上； ③释放管程； 2)x.v： ① x条件变化时调用x.v； ②从x条件队列中重新启动一个进程。 若队列空则继续执行原进程，而不产生任何结果；

89 若进程Q因x条件处于阻塞状态，进程P接着调用管程执行,当P执行了x.v操作后进程Q被重新启动，此时两个进程P和Q如何确定哪个执行哪个等待?
重新启动进程产生的问题：　　 若进程Q因x条件处于阻塞状态，进程P接着调用管程执行,当P执行了x.v操作后进程Q被重新启动，此时两个进程P和Q如何确定哪个执行哪个等待? 可采用下述两种方式之一进行处理： (1)P等待,直至Q离开管程或等待另一条件。 (2)Q等待,直至P离开管程或等待另一条件。

90 2.5 经典进程的同步问题 2.5.1 生产者—消费者问题 1．利用记录型信号量解决P-C问题
2.5　经典进程的同步问题 2.5.1　生产者—消费者问题 1．利用记录型信号量解决P-C问题 问题描述：在生产者和消费者之间有n个缓冲区组成的循环缓冲池，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。

91 empty:空缓冲区数量,决定能否执行P进程， 初值为n； full:满缓冲区数量，决定能否执行C进程， 初值为0；
1)进程互斥、同步分析： P,C进程对缓冲区的访问时互斥； P,C进程之间是同步； 2)信号量分析 若采用记录型信号量，则需3个信号量 mutex:用于互斥访问缓冲区， 初值为1； empty:空缓冲区数量,决定能否执行P进程， 初值为n； full:满缓冲区数量，决定能否执行C进程， 初值为0；

92 Var mutex，empty，full: semaphore:=1,n,0； buffer:array[0，…，n-1] of item；
in，out: integer:=0，0； 　begin 　　　parbegin

93 注：1）互斥信号P,V操作成对出现在一个程序段中
proceducer: begin 　　　　　　　　repeat 　　　　　　　　　 producer an item nextp； 　　　　　　　　　 wait(empty)； wait(mutex)； 　　　　　　　　　 buffer(in):=nextp； 　　　　　　　　　 in:=(in+1) mod n； 　　　　　　　　　 signal(mutex)； 　　　　　　　　　 signal(full)； 　　　　　　　　until false； 　　　　　　　end 注：1）互斥信号P,V操作成对出现在一个程序段中 2）同步信号P,V操作成对出现在两个程序段中 3）应先资源信号再互斥信号P操作，否则易死锁 … …

94 empty=0,则full=n,若mutex=1 执行wait(empty);wait(mutex);
例如缓冲区全满的情况： empty=0,则full=n,若mutex=1 执行wait(empty);wait(mutex); 当empty信号受阻时不会再测试mutex信号 执行wait(mutex); wait(empty); 当mutex满足时再测试empty信号P进程即会受阻，若要执行P进程就必须先由C进程取走消息，但此时缓冲区访问权在P进程C进程无法访问缓冲区，也就无法取走消息，取不走消息，P进程始终不能执行，因此陷入死锁。

95 consumer the item in nextc； until false； end parend end
consumer: begin 　　　　　　　 　repeat 　　　　　　　　　　 wait(full)； 　　　　　　　　　　 wait(mutex)； 　　　　　　　　　　 nextc:=buffer(out)； out:=(out+1) mod n； 　　　　　　　　　　 signal(mutex)； 　　　　　　　　　　 signal(empty)； 　　　　　　　　　　 consumer the item in nextc； 　　　　　　　　　 until false； 　　　　　　　　end 　　　parend 　end

96 2．利用AND信号量集解决P-C问题 wait(empty) Swait(empty,mutex) wait(mutex)
Ssignal(mutex，empty) Signal(mutex) Signal(empty) Swait(full，mutex) wait(full) wait(mutex) C进程 Ssignal(mutex,full) signal(mutex) signal(full)

97 Var mutex，empty，full: semaphore:=1，n，0； buffer:array[0，…，n-1] of item；
　in out: integer:=0，0； begin parbegin

98 produce an item in nextp； Swait(empty,mutex)； buffer(in):=nextp；
producer: begin 　　　 repeat produce an item in nextp； 　　　　Swait(empty,mutex)； 　　　　buffer(in):=nextp； 　　　　in:=(in+1)mod n； 　　　　Ssignal(mutex,full)； 　　　 until false； 　　 end … …

99 Ssignal(mutex，empty)； consumer the item in nextc； until false； end
begin 　　 repeat 　　　 Swait(full，mutex)； 　　　 Nextc:=buffer(out)； 　　　 Out:=(out+1) mod n； 　　　 Ssignal(mutex，empty)； 　　　 consumer the item in nextc； 　　 until false； 　 end parend end

100 先建立一个管程,并命名ProceducerConsumer, 简称PC。其中包括两个过程：
　　 3．利用管程解决生产者—消费者问题 先建立一个管程,并命名ProceducerConsumer, 简称PC。其中包括两个过程： 　　(1) put(item)过程。生产者利用该过程将自己生产的产品投放到缓冲池中，并用整型变量count来表示在缓冲池中已有的产品数目，当count≥n时，表示缓冲池已满，生产者须等待。 　　(2) get(item)过程。消费者利用该过程从缓冲池中取出一个产品，当count≤0时，表示缓冲池中已无可取用的产品，消费者应等待。

101 type producer-consumer=monitor Var in,out,count: integer；
PC管程可描述如下： type producer-consumer=monitor Var in,out,count: integer； 　　buffer: array[0, …, n-1] of item； 　　notfull，notempty:condition；

102 procedure entry put(item) begin if count>=n then notfull.wait；
　　　buffer(in):=nextp； 　　　in:=(in+1) mod n； 　　　count:=count+1； if notempty.queue then notempty.signal 　　end

103 procedure entry get(item) begin if count<=0 then notempty.wait；
　　nextc:=buffer(out)； 　　out:=(out+1) mod n； 　　count:=count-1； 　　if notfull.quene then notfull.signal； 　end begin in:=out:=0； count:=0 end

104 P,C进程调用管程： producer: begin repeat produce an item in nextp；
　　　PC.put(item)； 　　until false； 　end consumer: 　　　PC.get(item)； 　　　consume the item in nextc；

105 2.5.2　哲学家 进餐问题 问题描述：五个哲学家共用一个圆桌，圆桌上有五个碗和五只筷子，哲学家交替进行思考和进餐，当哲学家饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。

106 五个筷子对应五个信号量构成信号量数组，其描述如下： Var chopstick: array[0，…，4] of semaphore；
1)进程互斥、同步分析 每个筷子只能由一位哲学家使用，是互斥 2)信号量分析 每个筷子对应一个信号量 1．利用记录型信号量解决哲学家进餐问题 五个筷子对应五个信号量构成信号量数组，其描述如下： Var chopstick: array[0，…，4] of semaphore； 所有信号量均被初始化为1，第i位哲学家的活动可描述为：

107 wait(chopstick[(i+1)mod 5])； eat； signal(chopstick[i])；
　　repeat 　　　　wait(chopstick[i])； 　　　　wait(chopstick[(i+1)mod 5])； 　　　　eat； 　　　　signal(chopstick[i])； 　　　　signal(chopstick[(i+1)mod 5])； 　　　　think； 　　until false； … … …

108 (1) 至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐。
采用记录型信号量易导致问题：产生死锁 解决办法： (1) 至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐。 (2) 仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。

109 思考：若每人拿起左边筷子后再检测右边筷子，若忙则放下左边筷子等待一段时间后再重复这一过程，能否解决这一死锁问题？
　 (3) 规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子，而偶数号哲学家则相反。按此规定，将是1、2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。 思考：若每人拿起左边筷子后再检测右边筷子，若忙则放下左边筷子等待一段时间后再重复这一过程，能否解决这一死锁问题？

110 第i个哲学家思考-进餐过程如下： Var chopsiick array of semaphore:=(1,1,1,1,1)；
　　2．利用AND信号量集解决哲学家进餐问题 第i个哲学家思考-进餐过程如下： Var chopsiick array of semaphore:=(1,1,1,1,1)； processi 　 repeat 　 think； 　 Swait(chopstick[(i+1)mod 5],chopstick[i])； 　 eat； 　 Ssignal(chopstick[(i+1)mod 5]，chopstick[i])； until false；

111 问题描述：多个读者、写者进程要同时访问一个文件或记录。
2.5.3　读者—写者问题 问题描述：多个读者、写者进程要同时访问一个文件或记录。 原则：1)多个读可同时； 2)多个写不能同时； 3)有写不能读，有读不能写； 1）进程互斥、同步分析： 读、写操作是互斥 2）信号量分析： wmutex:进程互斥信号量 rmutex:用于访问readcount公共变量的信号量

112 var rmutex，wmutex: semaphore:=1,1； readcount: integer:=0； begin
1．利用记录型信号量解决读者—写者问题 var rmutex，wmutex: semaphore:=1,1； 　readcount: integer:=0； 　begin 　　parbegin

113 Reader: begin repeat wait(rmutex)； if readcount=0 then wait(wmutex)；
　　　　 readcount:=readcount+1； 　　　　 signal(rmutex)； perform read operation； 　　　 readcount:=readcount-1； 　　　　 if readcount=0 then signal(wmutex)； 　　　 until false； 　 end … …

114 Reader:（若改变两wait语句位置）
begin 　　　 repeat 　　　　 wait(wmutex)； 　　　　 wait(rmutex)； 　　　　 readcount:=readcount+1； 　　　　 signal(rmutex)； perform read operation； 　　　 readcount:=readcount-1； 　　　　 if readcount=0 then signal(wmutex)； 　　　 until false； 　 end … …

115 perform write operation； signal(wmutex)； until false； end parend end
writer: begin 　　repeat 　　　wait(wmutex)； 　　　perform write operation； 　　　signal(wmutex)； 　　until false； 　 end 　parend end

116 Var RN integer； L，mx: semaphore:=RN,1； begin parbegin
2．利用一般信号量集解决读者—写者问题 　1)若最多只允许RN个读者同时读，对应信号量L； 2)对于写、写进程的互斥对应信号量mx； 描述如下： Var RN integer； L，mx: semaphore:=RN,1； begin parbegin

117 perform read operation； Ssignal(L,1)； until false； end
reader: begin 　　repeat 　　　Swait(L,1,1)； 　　　Swait(mx,1,0)； 　　　perform read operation； 　　　Ssignal(L,1)； 　　until false； 　end … …

118 perform write operation； Ssignal(mx,1)； until false； end parend end
writer: begin 　　repeat 　　　Swait(mx,1,1；L,RN,0)； 　　　perform write operation； 　　　Ssignal(mx,1)； 　　until false； 　end parend end

119 2.6 进 程 通 信 用户控制通信过程，传送的信息量少，效率低。信号量机制。 低级通信： 进程通信 高级通信：
2.6 进 程 通 信 用户控制通信过程，传送的信息量少，效率低。信号量机制。 低级通信： 进程通信 共享数据结构 1.共享存储器系统 2.消息传递系统： 3.管道通信系统 共享存储区 直接、间接传递 高级通信： OS控制通信过程，传送的信息量大效高率，通信过程对用户透明。

120 2.6.1 进程通信的类型 1.共享存储器系统 (1)基于共享数据结构的通信方式。
2.6.1　进程通信的类型 1.共享存储器系统 (1)基于共享数据结构的通信方式。 诸进程公用某些数据结构，以实现信息交换。如P—C问题利用有界缓冲区这种数据结构来实现通信。实质是低级通信。 (2) 基于共享存储区的通信方式。 存储器中划出一块共享存储区，诸进程可通过对共享存储区中数据的读或写来实现通信。

121 N Y 进程申请公用存储区 系统是否已有此存储区 分配新存储区 系统将存储区描述符给进程 进程将描述符连入PCB

122 优点：能实现大量数据的传递，隐藏通信细节，使通信过程对用户是透明的。 微内核操作系统中，微内核与服务器之间的通信都采用消息传递机制。
2．消息传递系统 　当前应用最为广泛的一种通信机制。 进程间通信单位：格式化的消息(报文) 。 实现过程：利用OS提供的一组通信原语。 优点：能实现大量数据的传递，隐藏通信细节，使通信过程对用户是透明的。 微内核操作系统中，微内核与服务器之间的通信都采用消息传递机制。 消息传递分为直接通信、间接通信方式两种。

123 读进程读完数据后等待写进程向pipe写数据； (3)pipe两端都有进程才能进行通信。
3．管道通信（最早出现于UNIX系统） 接收进程 (读进程） 发送进程 (写进程) 管道文件 (pipe文件) 字符流 为了协调双方的通信，管道机制必须提供以下三方面的协调能力： (1)互斥：两进程互斥访问pipe。 　(2)同步： 写进程写入一定数据后等待读进程读数据； 读进程读完数据后等待写进程向pipe写数据； 　(3)pipe两端都有进程才能进行通信。

124 2.6.2 消息传递通信的实现方法 1.直接通信方式 源进程直接把消息发送给目标进程。 发送、接收进程都以显式方式提供对方的标识符。
2.6.2　消息传递通信的实现方法 1.直接通信方式 　 源进程直接把消息发送给目标进程。 发送、接收进程都以显式方式提供对方的标识符。 发送原语：Send(Receiver，message)； 接收原语：Receive(Sender，message)； 　　 例如，原语Send(P2，m1) ； 原语Receive(P1，m1) 。 　某些情况下，接收进程可与多个发送进程通信，因此，它不可能事先指定发送进程。对于这样的应用，接收原语可表示为： 　　Receive (id，message)；

125 利用第三方来传递消息，以实现实时、非实时的信息传递。第三方称为信箱。 OS提供的信箱原语：
2．间接通信方式 　利用第三方来传递消息，以实现实时、非实时的信息传递。第三方称为信箱。　　 OS提供的信箱原语： 　 (1)信箱的创建和撤消。 信箱创建原语建立一个新信箱。 需创建的信箱信息：信箱名字、信箱属性(公用、私用或共享)；对于共享信箱，还应给出共享者的名字。 信箱撤消原语撤消信箱。

126 发送原语：Send(mailbox，message)； 接收原语Receive(mailbox，message)；
(2)信箱结构：信箱头，信箱体 (3)消息的发送和接收。 发送原语：Send(mailbox，message)； 　　 接收原语Receive(mailbox，message)； 　信箱可由操作系统创建，也可由用户进程创建，据此，可把信箱分为以下三类。 1) 私用信箱 　由进程自身创建，多进程可向其发信息，但只能由创建者读取信息，有生命周期。 私用信箱采用单向通信链路实现。

127 由进程创建，需指明共享者名字。指定的共享者可从信箱中取属于自己的信息。 3) 公用信箱
2)共享信箱 由进程创建，需指明共享者名字。指定的共享者可从信箱中取属于自己的信息。　 3) 公用信箱 由操作系统创建，提供给系统中的所有核准进程使用。核准进程既可发送消息也可读取自己的消息。 采用双向通信链路的信箱来实现。 通常，公用信箱在系统运行期间始终存在。

128 (1)1对1：1发送1接收，二者通过单向通信链路通信，整个过程不受干扰。
利用信箱通信时发送、接收进程间的关系：　　 (1)1对1：1发送1接收，二者通过单向通信链路通信，整个过程不受干扰。 (2)1对多：1发送多接收，发送进程采用广播方式向多个接收者发送消息。 (3)多对1：多发送1接收，如私有信箱。 (4)多对多关系：如公用信箱。

129 2.6.3 直接消息传递系统实现1．通信链路 显式建立：通信前有发送进程利用“建立连接”原语请求系统显示建立 (主要用于计算机网络)。
2.6.3　直接消息传递系统实现1．通信链路 1)建立 显式建立：通信前有发送进程利用“建立连接”原语请求系统显示建立 (主要用于计算机网络)。 隐式建立：发送进程直接用send原语由系 统自动建立连接(主要用于单机)

130 点—点链路 A.根据链路 中节点数 多点链路 2)分类 单向通信链路 A B B.根据通信 方式 双向通信链路 A B 有容量链路
C.根据链路容量不同 有容量链路 无容量链路

131 单机消息格式比较简单；网络环境下消息格式比较复杂。
2．消息的格式 　单机消息格式比较简单；网络环境下消息格式比较复杂。 消息 消息头 正文 1)源进程名 2)目标进程名 3)消息长度 4)消息类型 6)消息发送日期、时间 5)消息编号

132 进程通信时，发送进程、接收进程，都存在两种可能性状态，即发送(接收)，或者阻塞。二者间可能有以下三种情况：
OS处理消息 定长消息：利于OS操作 变长消息：利于用户 3．进程同步方式 　进程通信时，发送进程、接收进程，都存在两种可能性状态，即发送(接收)，或者阻塞。二者间可能有以下三种情况：

133 两进程平时都处于阻塞状态，直到有消息传递时才被唤醒。 此时进程之间紧密同步，即二者是无容连接。这种同步方式称为汇合。
(1) 二者均阻塞。 两进程平时都处于阻塞状态，直到有消息传递时才被唤醒。 此时进程之间紧密同步，即二者是无容连接。这种同步方式称为汇合。 (2)发送进程不阻塞，接收进程阻塞。 应用最广的同步方式。 发送进程可以尽快地把一个或多个消息发送给多个目标；而接收进程平时则处于阻塞状态，直到发送进程发来消息时才被唤醒。如打印服务。

134 例如，在发送进程和接收进程之间联系着一个消息队列。 发送进程可以连续地向消息队列中发送消息；接收进程也可以连续地从消息队列中取得消息。
(3)发送进程和接收进程均不阻塞。 也较常见。一般二者间为有容连接。 例如，在发送进程和接收进程之间联系着一个消息队列。 发送进程可以连续地向消息队列中发送消息；接收进程也可以连续地从消息队列中取得消息。 只有当消息队列满时，发送进程才会阻塞；只有当消息队列中的消息空时，接收进程才会阻塞。

135 消息缓冲队列通信机制 思考：消息缓冲队列通信机制是直接通信还是间接通信？是有容连接还是无容连接？ 1) 消息缓冲区 消息缓冲区描述如下：
　消息缓冲队列通信机制 思考：消息缓冲队列通信机制是直接通信还是间接通信？是有容连接还是无容连接？ 1) 消息缓冲区 　　消息缓冲区描述如下： 　　type message buffer=record 　　　 sender ；发送者进程标识符 　　　 size； 消息长度 　　　　text； 消息正文 　　　　next； 指向下一个消息缓冲区的指针 　　end

136 在PCB中应增加的数据项可描述如下： type processcontrol block=record mq； 消息队列队首
mutex； 消息队列互斥信号量 　　　 sm； 消息队列资源信号量 end

137 ①根据发送区a中所设置的消息长度a.size来申请一缓冲区i； ②把发送区a中的信息复制到缓冲区i中； ③获得接收进程的内部标识符j；
2．发送原语 1)先在自己的内存空间设置一发送区a 2)把待发送的消息正文、发送进程标识符、 消息长度等信息填入其中 3)然后调用发送原语，把消息发送给目标 (接收)进程。 ①根据发送区a中所设置的消息长度a.size来申请一缓冲区i； ②把发送区a中的信息复制到缓冲区i中； ③获得接收进程的内部标识符j； ④将i挂在j.mq上。

138 procedure send(receiver，a) begin getbuf(a.size,i)；
发送原语可描述如下： 　　procedure send(receiver，a) 　　　begin 　　　　getbuf(a.size,i)；　　 　　　　i.sender:= a.sender； 　　　　i.size:=a.size； 　　　　i.text:=a.text； 　　　　i.next:=0； 　　　　getid(PCB set，receiver.j)； 　　　　wait(j.mutex)； 　　　　insert(j.mq，i)；　　 　　　　signal(j.mutex)； 　　　　signal(j.sm)； 　　end

139 图 2-14　消息缓冲通信

140 2)从自己的消息缓冲队列mq中摘下第一个消息缓冲区i， 3)将其中的数据复制到以b为首址的指定消息接收区内。接收原语描述如下:
3．接收原语 　1)调用接收原语receive(b) 2)从自己的消息缓冲队列mq中摘下第一个消息缓冲区i， 3)将其中的数据复制到以b为首址的指定消息接收区内。接收原语描述如下:

141 procedure receive(b) begin j:= internal name； wait(j.sm)；
　 wait(j.mutex)； 　 remove(j.mq，i)；　 　 signal(j.mutex)； b.sender:=i.sender；　 　 b.size:=i.size； 　 b.text:=i.text； end

142 2.7　线　程 2.7.1　线程的引入 　　在操作系统中再引入线程，是为了减少程序在并发执行时所付出的时空开销，使OS具有更好的并发性。 进程 资源 线程... 线程1 线程2 线程3 线程n

143 传统操作系统:拥有资源的基本单位和独立调度、分派的基本单位都是进程。 引入线程的操作系统:线程作为调度和分派的基本单位。 2) 并发性
2.7.2．线程与进程的比较 1) 调度 　 传统操作系统:拥有资源的基本单位和独立调度、分派的基本单位都是进程。 引入线程的操作系统:线程作为调度和分派的基本单位。 2) 并发性 进程之间可以并发执行; 一个进程中的多个线程之间亦可并发执行。3) 拥有资源 　传统的操作系统:进程是系统中拥有资源的基本单位。线程自己不拥有系统资源可以访问其隶属进程的资源。

144 进程：在创建或撤消进程、进程切换时， 操作系统需要分配内存空间，PCB，保留CPU 当前状态等，所付出的开销大。
4) 系统开销 　进程：在创建或撤消进程、进程切换时， 操作系统需要分配内存空间，PCB，保留CPU 当前状态等，所付出的开销大。 线程：其切换则仅需保存和设置少量寄存 器内容，不涉及存储器管理方面的操作。一 个进程中的多个线程具有相同的地址空间， 在同步和通信的实现方面线程也比进程容易。 新增： 5)独立性 6)支持多处理机系统

145 2.7.3线程的状态和线程控制块 1.线程运行的三个状态：执行、就绪、阻塞 2.线程控制块TCB
1)线程标识符2)寄存器3)线程状态4)优先级 5)线程专有存储区6)信号屏蔽7)堆栈指针 3.多线程OS中的进程属性 1）进程是拥有资源的基本单位 2）多个线程可并发执行 3）进程不是可执行的实体

146 2.8 线程的实现方式 2.8.1线程的实现方式 1．内核支持线程KST
2.8　线程的实现方式 2.8.1线程的实现方式　　 1．内核支持线程KST 　　无论是用户进程中的线程，还是系统进程 中的线程，内核根据该控制块TCB而感知某线 程的存在，并对其加以控制。 这种线程实现方式优点： 　　(1) 在多处理器系统中，内核能够同时调度 同一进程中多个线程并行执行；

147 (2) 如果进程中的一个线程被阻塞了，内核 可以调度该进程中的其它线程运行，也可以运 行其它进程中的线程；
(2) 如果进程中的一个线程被阻塞了，内核 可以调度该进程中的其它线程运行，也可以运 行其它进程中的线程； (3) 内核支持线程具有很小的数据结构和堆 栈，线程的切换比较快，切换开销小； (4) 内核本身也可以采用多线程技术，可以 提高系统的执行速度和效率。 　 缺点：用户的线程切换，需要从用户态转 到内核态进行，其模式切换的开销较大。

148 线程是与内核无关，内核完全不知道用户级线程的存在。
2．用户级线程ULT 　 用户级线程仅存在于用户空间中。 线程是与内核无关，内核完全不知道用户级线程的存在。 优点： 　(1) 线程切换不需要转换到内核空间节省了模式切换的开销。 　(2) 调度算法可以是进程专用的。 　(3) 用户级线程的实现与操作系统平台无关，因此，用户级线程甚至可以在不支持线程机制的操作系统平台上实现。

149 (1) 进程阻塞，进程内的所有线程都会被阻塞。 (2) 多线程应用不能利用多处理机进行并行执行。
缺点： 　(1) 进程阻塞，进程内的所有线程都会被阻塞。 　(2) 多线程应用不能利用多处理机进行并行执行。 3．组合方式 　内核支持多线程的建立、调度和管理，同时，也允许用户应用程序建立、调度和管理用户级线程。

150 2.8.2　线程的实现 　1．内核支持线程的实现 　 系统在创建一个新进程时，便分配一个任务数据区PTDA(Per Task Data Area)，其中包括若干个线程控制块TCB空间，如图2-15所示。TCB中的信息保存在内核空间中。 图 2-15　任务数据区空间

151 内核支持线程的调度和切换与进程的调度和 切换十分相似。
　 内核支持线程，线程的创建、 撤消均与进程 的相类似。 有的系统中为了减少创建和撤消一个线程时的 开销，在撤消一个线程时，并不立即回收该线程 的资源和TCB，当以后再要创建一个新线程时， 便可直接利用已被撤消但仍保持有资源和TCB的 线程作为新线程。 内核支持线程的调度和切换与进程的调度和 切换十分相似。

152 用户级线程是在用户空间实现的，运行在一 个中间系统的上面。 当前有两种方式实现的中间系统，即运行时 系统和内核控制线程。
2．用户级线程的实现 　 用户级线程是在用户空间实现的，运行在一 个中间系统的上面。 当前有两种方式实现的中间系统，即运行时 系统和内核控制线程。 1) 运行时系统(Runtime System) 　　所谓“运行时系统”，即线程库，是用于 管理和控制线程的函数(过程)的集合，包括用 于创建和撤消线程的函数、 线程同步和通信的 函数以及实现线程调度的函数等。 是用户级线程与内核之间的接口。

153 当线程需要系统资源时，是将该要求传 送给运行时系统，由后者通过相应的系统调 用来获得系统资源的。
　　在传统的OS中，进程在切换时必须先由用 户态转为核心态，再由核心来执行切换任务； 而用户级线程在切换时则不需转入核心态， 而是由运行时系统中的线程切换过程来执行 切换任务。 当线程需要系统资源时，是将该要求传 送给运行时系统，由后者通过相应的系统调 用来获得系统资源的。

154 LWP由用户进程调用函数创建，内核识别,可 通过系统调用来获得内核提供的服务。
这种线程实现方式实质上是组合方式。 多个LWP做成一个缓冲池，称为“线程池”。 用户进程中的任一用户线程都可以连接到LWP 池中的任何一个LWP上。

155 内核所看到的总是多个LWP而看不到用户 级线程。 LWP实现了在内核与用户级线程之间的隔 离，从而使用户级线程与内核无关。
内核级线程

156 图 2-16　利用轻型进程作为中间系统

157 内核级线程阻塞，则与之相连接的多个LWP也 将阻塞，进而使连接到LWP上的用户级线程也被阻 塞。
如果在一个进程中含有多个LWP，则当一个 LWP阻塞时，进程中的另一个LWP可继续执行。

158 综合上述两种模型的优点，将多个用户线程映射到多个内核控制线程。
3．用户级线程与内核控制线程的连接 　1) 一对一模型 　　一个内核控制线程一个用户线程。　 　 2)一对多模型 　 一个内核控制线程连多个用户线程。 多个用户线程一般属于一个进程。 优点：线程管理的开销小，效率高。 缺点：一个进程的多个线程无法实现并行。 3) 多对多模型 　 综合上述两种模型的优点，将多个用户线程映射到多个内核控制线程。

159 进程同步补充例题 例1.生产围棋的工人不小心把相等数量的黑子和 白子混装在一个箱子里，现要用自动分拣系统把白子黑子分开，该系统由两个并发执行的进程组成，功能如下： 1)进程A专拣黑子，进程B专拣白子 2)每个进程每次只拣一个子，当一个进程拣子时不允许另一个去拣子。 分析：1)进程关系分析： 互斥 2)信号量： 1个信号量

160 算法实现： begin s:semaphore:=1; process B begin parbegin repeat process A
… wait(s); 拣黑子； signal(s); until false end process B begin repeat … wait(s); 拣白子； signal(s); until false end parend

161 分析： 此时两进程关系为同步，需要两个信号量 算法实现： begin s1,s2：semaphore:=1,0; cobegin
题目改进：若题目改为当一个进程拣了棋子后必须让另一个进程拣一个棋子。 分析： 此时两进程关系为同步，需要两个信号量 算法实现： begin s1,s2：semaphore:=1,0; cobegin

162 process B process A begin begin repeat repeat … … wait(s2); wait(s1);
拣白子； signal(s1); until false end coend process A begin repeat … wait(s1); 拣黑子； signal(s2); until false end

163 run---司机进程信号量 stop---售票员进程信号量 启动车辆 上乘客、关车门 正常行驶 售票 到站停车 开车门、下乘客
例题2：设在公共汽车上，司机何售票员的活动 分别是：司机：启动车辆；正常行车；到站停车； 售票员：上乘客，关车门；售票；开车门，下乘客； 试用P,V操作对其过程进行控制。 问题分析： 1)进程关系分析： 有先后顺序，是同步 2)信号量分析： 两个信号量控制俩进程 run---司机进程信号量 stop---售票员进程信号量 启动车辆 正常行驶 到站停车 上乘客、关车门 售票 开车门、下乘客

164 var driver： stop,run:semaphore； begin stop=1;run=0; repeat Begin
cobegin conductor： begin repeat 上乘客，关车门； signal(run); 售票； wait(stop); 开车门，下乘客； until false end driver： begin repeat wait(run)； 正常行驶; 到站停车； signal(stop); until false end coend

165 例题3：和尚挑水问题：寺庙里有多个小和尚和老和尚，有一个水缸一个水井三个水桶。小和尚从井中打水倒入水缸，只能容纳10桶水，老和尚从水缸中取水喝。水井每次只能入一个水桶，水缸入水、取水也每次只能一个水桶。试用P,V操作描述和尚挑水、饮水的互斥同步过程。

166 多个打水进程互斥，多个取水进程互斥，打水、取水进程同步 2)信号量分析： ①水井、水缸两个互斥信号量：
问题分析： 1)进程关系分析： 多个打水进程互斥，多个取水进程互斥，打水、取水进程同步 2)信号量分析： ①水井、水缸两个互斥信号量： mutex1—水井；mutex2—水缸；初值均为1； ②打水进程信号量： empty(水缸不满时可以打水)初值为10； ③取水进程信号量： full(水缸有水时可以取水)初值为0； ④水桶个数： count(初值为3)

167 var mutex1,mutex2,empty,full, count:semaphore; mutex1:=1; mutex2:=1;
begin parbegin

168 yong monk: begin old monk: begin repeat repeat … … p(empty); p(full);
p(count); p(mutex1); 从水井打水； v(mutex1); p(mutex2); 往缸中放水； v(mutex2); v(full); v(count); until false end old monk: begin repeat … p(full); p(count); p(mutex2); 从水缸中取水； v(mutex2); v(count); v(empty); until false end parend

169 例题4：某超市门口为顾客准备了100辆手推车，每位顾客在进去买东西时取一辆手推车，在买完东西结完账以后再把推车还回去，试用PV操作实现顾客进程的同步互斥关系。
1)进程同步、互斥分析 2)信号量分析

170 Var s:semaphore:=100 begin repeat p(s); 购物； 结账； v(s); until false end

171 例题5：桌子上有一个水果盘，每次可以往里面放一个水果，爸爸专向盘子里放苹果，儿子专等着吃盘子中的苹果，把爸爸、儿子看做两个进程，试用P,V操作实现两进程的并发执行。
1)进程互斥、同步分析 2）信号量分析

172 Var f,s:semaphore; f:=1; s:=0; son: begin begin parbegin repeat
father: repeat p(f); 放苹果； v(s); untilfalse end son: begin repeat p(s); 吃苹果； v(f); untilfalse end parend