PURSUING EXCELLENCE / TOWARD SUCCESS WUCHANG UNIVERSITY OF TECHNOLOGY

Presentation on theme: "PURSUING EXCELLENCE / TOWARD SUCCESS WUCHANG UNIVERSITY OF TECHNOLOGY"— Presentation transcript:

1 PURSUING EXCELLENCE / TOWARD SUCCESS WUCHANG UNIVERSITY OF TECHNOLOGY
武昌理工学院 操作系统原理 第三章 进程管理 我们毕业啦 其实是答辩的标题地方 主讲人 温 静 院系 信息工程学院

2 主要内容 1 程序执行方式 2 进程的基本概念 3 进程控制 4 进程互斥 CONTANTS 5 进程同步 6 进程通信 7 线程

3 程序执行方式 程序的执行方式可分为两类： 顺序执行 并发执行

4 程序的顺序执行 例1. 在处理一个作业时，总是首先输入用户的程序和 数据，然后进行计算，最后将所得的结果打印出来。 在早期的计算机中，输入、计算、打印这三个程序 段的执行只能是一个一个地顺序执行。

5 程序的顺序执行 例2. 对于一个程序段中的多条语句来说，也有一个执行顺序问题，如: S1: b=a+2; S2: c=b-5;
S3: x=c+b; S4: y=x+10; S1 S2 S3 S4

6 程序顺序执行的特征 (1) 顺序性： 处理机的操作必须严格按照程序所规定的顺序执行。 (2) 封闭性：
程序在执行时独占系统的全部资源，因此，机器资源状态的 改变只与执行的程序有关，而与外界环境无关。 (3) 可再现性： 只要初始条件相同，一个程序的多次重复执行，将得到相同 的结果（不论它是从头到尾不停顿地执行，还是“停停走走” 地执行，“可再现”即可再次出现，结果重复出现）。

7 前趋图 前趋图是一个有向无环图，简称DAG。 图中每个结点表示一个程序段、一条语句或一个进 程。
结点之间的有向边表示两个结点之间存在的偏序或 前趋关系 “→”。

8 前趋图的例子 具有6个结点的前趋图: 存在下述前趋关系: S1→S2，S1→S3，S1→S4，S2→S5，S3→S5，S4→S6，S5→S6

9 前趋图的例子 S1 S2 S3 按照前趋图的定义分析，上图不是一个前趋图，因为前趋图是一种有向无环图，而上图中S2→S3，S3→S2，构成了一个环，所以不是前趋图。

10 程序的并发执行 让我们再回到图3-1的例子，对于n个程序的处理， 每个程序都有输入、计算和打印三个步骤：
对作业1的处理: I1, C1, P1 对作业2的处理: I2, C2, P2 … … … 对作业n的处理: In, Cn, Pn

11 程序的并发执行 当系统中存在着大量的操作时,就可以进行并发处理 并发执行时的前趋图: I1 I2 I3 I4 C1 C2 C3 C4 P1

12 程序的并发执行 两类前趋关系： （1）I1→I2→I3→…→In（对输入机的竞争） C1→C2→C3→…→Cn（对CPU的竞争）
P1→P2→P3→…→Pn（对打印机的竞争） 原因是竞争资源 （2）I1→C1→P1 I2→C2→P2 … In→Cn→Pn 原因是程序内部的逻辑关系

13 程序的并发执行 还有一些结点之间是没有“→”相连的。 下标满足i+1，i和i-1关系的结点是可以并发的。
如I3、C2和P1，I4、C3和P2，…，而又因为这些操 作 分别占用不同的物理部件，因此可以达到真正的并 行操作。

14 程序的并发执行 P,Q,R这三个程序段就是并发执行的程序段 程序的并发执行是指:
若干个程序段同时在系统中运行,这些程序段的执行在时 间上是重叠的,一个程序段的执行尚未结束,另一个程序段 的执行已经开始,即使这种重叠是很小的一部分,也称这几 个程序段是并发执行的。 如: P Q R P,Q,R这三个程序段就是并发执行的程序段

15 程序的并发执行 程序并发执行时的特征 (1) 间断性： 多个并发程序共享系统资源，互相制约，因此产生 间断性。 (2) 失去封闭性：
程序之间会产生关联，彼此之间会受到影响，不再 是在一个封闭环境中运行了。 (3) 不可再现性： 程序的运行结果不能再次出现。

16 程序的并发执行 例如：两个并发执行的程序A和B，它们共享一个公共变量n。 A：n=1； B：n=2； print（n）；
① print（n）在n=1与n=2之后执行，则打印结果为2； ② print（n）在n=2与n=1之间执行，则打印结果为2； ③ print（n）在n=2与n=1之后执行，则打印结果为1； 这种现象说明程序并发执行时会发生与时间有关的错误。

17 进程的基本概念

18 进程的基本概念 在多道程序环境下，程序的并发执行破坏了程序的封 闭性和可再现性，使得程序的运行不再处于一个封闭 的环境中，从而导致出现了与时间有关的错误。 但操作系统最重要的特征就是并发，而程序又不能描 述并发，因此需要引入一个新的概念——进程。

19 进程的定义 进程是程序在处理机上的一次执行过程。（强调动态性） 进程是可以和别的计算并发执行的计算。（强调并发性）
进程是程序在一个数据集合上的运行过程，是系统进行资源分 配和调度的一个独立单位。（强调独立性） 进程是一个具有一定功能的程序关于某个数据集合的一次运行 活动。（描述进程的数据结构） 1978年在庐山召开的全国操作系统学术会议上，计算机学者给 出的定义：进程是具有独立功能的程序关于某个数据集合的一 次执行过程，是系统资源分配和调度的基本单位。

20 进程的特征 1. 结构性 进程包含:程序,数据,进程控制块(PCB).
用户编制 程序 数据 加工对象 PCB 描述程序执行状态 数据结构(表格),描述程序执行过程中的动态信息,是进程存在的唯一标志,OS通过PCB管理程序,它是OS唯一能感知的. PCB是进程存在的唯一标志

21 进程的特征 2. 动态性 动态性是进程的最基本特征。 进程的动态性具体体现在两个方面：
进程的运行过程是“执行—暂停—执行”，这个过 程具有动态性； 进程具有一定的生命周期，在其生命期内是一种动 态的特性。

22 进程的特征 3. 并发性 多个进程实体同时存在于内存之中，能在一段时 间内都得到运行。引入进程的目的就是为了使程序能 与其它程序并发执行，以提高资源利用率和系统效率。 4. 独立性 一是独立运行单位（没有引入线程的情况下）； 二是资源分配和调度的单位。 5. 异步性 进程按各自不可预知的速度向前推进。

23 进程与程序的区别 程序是静态的，而进程是动态的。 程序是永久的，而进程是暂时的。 进程和程序并不是一一对应的。
进程在执行过程中，根据需要可以创建其它进程， 而程序不具有这个功能。

24 进程的状态 （不论哪种操作系统，三种基本状态不可少）
1. 就绪状态（Ready）：进程除了CPU之外所有的资源 都得到了满足。（万事具备，只欠CPU），处于就绪 状态的进程可能有多个，通常将它们排成一个队列， 称为就绪队列。 2. 执行状态（Run）：进程正在使用CPU。 3. 阻塞状态（Block/Wait/Sleep）：进程因缺少某种 资源而放弃CPU，根据阻塞原因不同而把处于阻塞状 态的进程排成多个队列。

25 进程的状态 执行 进程调度 等待 事件 时间片完 就绪 阻塞 事件发生 进程的三种基本状态及其转换

26 进程控制块 进程控制块的作用 为了描述和控制进程的执行，系统为每个进程定 义了一个数据结构——进程控制块（PCB）。
它是进程的组成部分之一，是操作系统用来记录 进程状态及相关信息的数据结构。 操作系统通过PCB来了解和掌握进程的状态。 PCB是进程存在的唯一标志。

27 进程控制块 进程控制块中的信息： 标识信息 处理机状态信息 进程调度信息 进程控制信息

28 进程控制块 进程控制块的组织方式常见的有三种： 线性方式：把所有不同状态的进程的PCB组织在 一个线性表中。
索引方式：系统根据所有进程的状态建立几张索 引表。

29 进程控制 进程控制包含控制和管理进程的一些原语： 进程创建原语 进程撤销原语 进程阻塞原语 进程唤醒原语 进程挂起原语 进程激活原语

30 进程创建 进程创建的原因： 用户登录 提交作业 操作系统提供服务 应用请求

31 进程创建 进程的创建过程： 申请空闲PCB。 为新进程分配资源。 初始化新进程的PCB。 将新进程的PCB插入就绪队列。

32 进程撤销 进程撤销的原因： 进程正常结束 进程异常结束 外界干预

33 进程撤销 进程的撤销过程： 根据被撤销进程的标识符，从PCB集合中找到 该进程的PCB，从中读出该进程的状态。
如果该进程的状态为执行，则首先应暂停该进 程的执行，转进程调度程序，在就绪队列中选 择一个新的进程占用CPU运行。 检查该进程是否还有子孙进程，若有则应首先 撤销其所有的子孙进程，以防止它们成为不可 控的进程。 将被撤销进程所拥有的资源，或归还给父进程， 或归还给系统。 系统回收该被撤销进程的PCB，并将之放入 PCB资源池，以便创建新进程时申请使用。

34 进程的阻塞与唤醒 进程阻塞与唤醒的原因： 请求系统服务 启动某种操作 新数据尚未到达 系统进程无新工作可做

35 进程的阻塞与唤醒 进程的阻塞过程： 停止当前进程的执行。 保存该进程的CPU现场信息。 将进程状态改为阻塞，并插入到阻塞队列中。
进程的唤醒过程： 将被唤醒的进程从相应的阻塞队列中移出。 将进程状态由阻塞改为就绪，并将该进程插入到就绪队列。 在某些抢占式系统中，若被唤醒进程的优先级比当前运行进程高时，可能需要设置调度标志。 注意：进程的阻塞和唤醒是一对作用刚好相反的原语。

36 问题 过独木桥： P1 P2 P1（） { 由西向东过独木桥； } P2（） { 由东向西过独木桥； }

37 进程间的间接相互制约关系 这种制约是由于共享资源引起的，若某一进程要求使用某一资源，而该资源正被另一进程使用，并且这一资源不允许两个进程同时使用，那么该进程只有等待已占用资源的进程释放后才能使用。 进程 资源 进程

38 进程互斥的概念 Concept Explanation 进程互斥 进程之间因为竞争资源所导致的间接相互制约关系
当多个进程之间存在互斥关系时，这些进程之间本身没有逻辑关系，而是因为都要使用同一个临界资源而引起的。

39 临界资源 在一段时间内只允许一个进程访问的资源 概念 设备、表格、数据、程序段、变量、队列等 举例 交叉访问，容易产生与时间有关的错误 错误

40 例1 进程共享公共变量 在一个银行系统的两个终端上，分别运行着两个进程P1和P2，它们共享同一账户变量count，进程P1、P2的功能都是从该账户中取款，部分程序段如下： P1： P2： … … M=count； N=count； M=M-200； N=N-300； count=M； count=N； 方式一： P1：M=count；M=M-200；count=M； P2： N=count；N=N-300；count=N； 方式二： P1：M=count； P2： N=count；N=N-300；count=N； P1： M=M-200；count=M； 方式一是正确的；但方式二出现了与时间有关的错误，因为对共享变量count采取了交叉访问。

41 临界区（ Critical Section，CS ）
进程中访问临界资源的那一段代码 临界区 如果能够保证各进程互斥地进入自己的临界区，便可以实现多个进程对临界资源的互斥访问。 如果一个进程正在访问临界资源，我们就说该进程进入了临界区。

42 问题 例1中的进程p1和p2的临界区是什么？ 临界资源count 进程p2的临界区 进程p1的临界区 M=M-200； count=M；
count=N； N=N-300； N=count； 进程p2的临界区 进程p1的临界区 临界资源count

43 访问临界资源的格式 一个访问临界资源的进程描述如下： entry section 进入区: 提出申请,并进行检查
critical section 临界区: 访问临界资源 exit section 退出区: 恢复为未访问标志(访问之前的标志) remainder section 剩余区：进程中的剩余代码

44 访问临界资源应遵循的规则 规则 空闲让进 忙则等待 忙则等待 空闲让进 有限等待 让权等待 让权等待 有限等待
当无进程处于临界区时，可让要求进入临界区的进程进入临界区。 规则 空闲让进 有限等待 让权等待 忙则等待 当已有进程处于临界区时，其他进程则等待。 有限等待 让权等待 不能进入临界区时，应立即释放处理机，进入“等待队列”，以免陷入“忙等”。 进程进入临界区只能停留有限的时间，以免死锁。

45 问题 交通信号灯 信号量 生活中：道路资源少，行人车辆多，如何维持正常交通秩序？
计算机系统中：系统资源少，进程多，如何确保进程间合理地竞争资源？

46 信号量机制的诞生 信 号 量 1965年，由荷兰学者Dijkstra提出的。
一种进程同步工具 引自交通管理中 其基本思想是在多个相互合作的进程之间使用简单的信号来同步 信 号 量 Dijkstra，1930年5月11日~2002年8月6日，荷兰人。 计算机科学家，毕业就职于荷兰Leiden大学，早年钻研物理及数学，而后转为计算学。曾在1972年获得过素有计算机科学界的诺贝尔奖之称的图灵奖。 1965年，由荷兰学者Dijkstra提出的。

47 信号量的定义 Concept 信号量是一种结构体类型的变量 信号量 Structure 包含两个成员： 代表资源数目的整型变量 进程队列

48 信号量定义实例 struct semaphore { struct semaphore S； int value； queue L； }
信号量结构体类型定义 struct semaphore { int value； queue L； } 信号量类型变量定义 struct semaphore S；

49 信号量的取值含义 由于初始状态下，没有任何进程因为请求资源而被阻塞，所以S.L的初始值为空。 代表因为请求资源而被阻塞的进程队列。 整型值
S.value 整型值 S.value的初始值只能取大于等于0的整数。 当S.value<0时，其绝对值代表因为请求资源而被阻塞的进程个数。 当S.value>=0时，代表系统中当前可用的资源数目。 S.L 代表因为请求资源而被阻塞的进程队列。 由于初始状态下，没有任何进程因为请求资源而被阻塞，所以S.L的初始值为空。

50 信号量的三种操作 信号量S 将信号量S初始化为非负数，即系统初 始状态下信号量S所代表的资源的数目。
signal操作使信号量的value加1。如果值小于或等于0，则唤醒一个因请求资源而被阻塞的进程。 wait操作使信号量的value减1。若为负数，则执行wait操作的进程被阻塞，否则进程继续执行。

51 wait(s)：每调用一次，代表申请一个资源 signal(s)：每调用一次，代表释放一个资源
原语 即原子操作，执行时不可中断 原语 wait(s)：每调用一次，代表申请一个资源 wait signal(s)：每调用一次，代表释放一个资源 signal

52 wait原语 流程图 wait（S）原语的程序描述如下： void wait（semphore S） { S.value--；
if（S.value<0） block（S.L）； } 流程图 wait（s） s.value=s.value-1 Y s.value<0？ N 本进程获得一个资源 本进程进入s.L队列，被阻塞 临界区

53 signal原语 signal（S）原语的程序描述如下： 流程图 void signal（semphore S） { S.value++；
if（S.value<=0） wakeup（S.L）； } 流程图 signal（s） s.value=s.value+1 Y s.value<=0？ N 将s.L队列中的第一个进程唤醒

54 3. 将各进程中访问临界资源的临界区CS置于wait（mutex）和signal（mutex）之间
利用信号量机制实现进程互斥 1. 设一个互斥信号量mutex 2. 初始值设为1 3. 将各进程中访问临界资源的临界区CS置于wait（mutex）和signal（mutex）之间

55 例子 两个并发进程对临界资源互斥访问的程序描述如下： void P2（） { while（true） wait（mutex）； CS2；
signal（mutex）； RS2； } 0-1=-1<0 阻塞 转去执行p1 两个并发进程对临界资源互斥访问的程序描述如下： semaphore mutex=1； void P1（） { while（true） wait（mutex）； CS1； signal（mutex）； RS1； } 0+1=1 恢复到初始值 1-1=0>=0 申请成功 中断 void main（） { parbegin p1（）； p2（）； parend } 执行进程p2 -1+1=0<=0 唤醒进程p2 p1执行完毕，转去执行p2

56 互斥信号量的取值范围 对于两个并发进程，互斥信号量的值仅能取 到1，0和-1三个值 表示没有进程进入临界区 表示有一个进程进入临界区
mutex=1 表示没有进程进入临界区 mutex=0 表示有一个进程进入临界区 mutex=-1 表示一个进程进入临界区，另一个进程等待进入 由于mutex为整型变量，所以取值范围为：[-1,1]

57 互斥信号量的取值范围 进一步推广，如果有n个并发进程访问同一个临 界资源，那么mutex的取值范围应为[1-n，1]；
如果n个并发进程访问m个临界资源，则mutex的 取值范围为[m-n，m]。

58 互斥信号量的取值范围 当有100个学生都想要进入自习室时，则mutex的取值范围为 [-40，60]。
semaphore mutex=60； void studenti（） { while（true） {wait（mutex）； 进入自习室； 自习； 离开自习室； signal（mutex）；} } void main（） { parbegin student1（）； student2（）； … studentn（）； parend } 当有100个学生都想要进入自习室时，则mutex的取值范围为 [-40，60]。

59 进程同步 进程之间因为相互合作所导致的直接相互制约关系 就是进程的同步。 同步意味着两个或多个进程之间根据它们一致同意 的协议进行相互作用。
同步的实质是使各合作进程的行为保持某种一致性 或不变关系。 要实现同步，一定存在着必须遵循的同步规则。

60 进程同步的概念 A B 数据 读 进程 存 缓冲区 取 加工 进程A、B必须遵循以下同步规则：

61 用信号量机制实现进程同步 一般同步问题可以分为两类： 保证一组合作进程按逻辑需要所确定的执行次序来 执行；
保证共享缓冲区（或共享数据）的合作进程的同步。

62 合作进程的执行次序 void S2（） {wait（a）； … signal（c）； signal（d）；} void S3（）
{wait（b）； signal（e）；} void S4（） {wait（c）； signal（f）；} void S5（） {wait（d）； signal（g）；} S1 S3 S6 S4 S5 S2 a b c d e f g void S6（） {wait（e）； wait（f）； wait（g）； …} void main（） {parbegin S1（）；S2（）；S3（）；S4（）；S5（）；S6（）； parend} semaphore a，b，c，d，e，f，g； a=0；b=0；c=0；d=0；e=0；f=0；g=0； void S1（） {… signal（a）； signal（b）；}

63 共享缓冲区的合作进程的同步 void B（） semaphore s1，s2； { while（true） s1=1；s2=0；
数据 读 进程 存 缓冲区 取 加工 void B（） { while（true） { wait（s2）； 从缓冲区中取出一个数据； signal（s1）； 加工该数据；} } void main（） { parbegin A（）； B（）； parend } semaphore s1，s2； s1=1；s2=0； void A（） { while（true） { 产生一个数据； wait（s1）； 存入缓冲区中； signal（s2）；} }

64 进程同步与进程互斥的区别与联系 进程的互斥与进程的同步又是有区别的。 进程的互斥是进程之间竞争临界资源的使用权。
进程同步更多强调的是进程之间的合作，而共 享资源只是为了实现合作而使用的一种工具。

65 生产者-消费者问题 生产者：多个产生数据的进程； 消费者：多个从缓冲区取数据的进程。 p1 n-1 c1 p2 c2 …. … … ck
n-1 c1 p2 c2 …. … … ck pm 生产者：多个产生数据的进程； 消费者：多个从缓冲区取数据的进程。

66 生产者-消费者问题 1. 生产者正在往里放数据时，消费者不能取，其它进程也不能放数据（互斥）应设互斥信号量mutex；
2. 假设缓冲区满了，送数据没地方装,应设信号量阻塞放数据，若缓冲区为空，则对消费者阻塞。 一.生产者和消费者的同步关系 禁止生产者向满的缓冲区送产品(数据); 禁止消费者从空的缓冲区取产品(数据). 二. 同步的信号量(灯) 1. empty: 说明空缓冲区的数目, 初值:n; 2. full: 表示满缓冲区的数目, 初值:0. 三. 缓冲区是临界资源,故应设 一 个互斥 信号量(灯)mutex 初值:1 实现对缓冲区的互斥操作.

67 生产者-消费者问题 item B[n]； //定义有界缓冲区B semaphore empty=n； //可用的空缓冲区数
semaphore full =0； //缓冲区内可用的产品数 semaphore mutex=1； //互斥信号量 int in=0； //放入缓冲区指针 int out=0； //取出缓冲区指针 void produceri（） //i=1,2,3, …,m { while（生产未完成） { 生产一件产品nextp； wait（empty）； //检测缓冲区中是否有空位 wait（mutex）； //检测有界缓冲区是否可用 B[in]=nextp； //将产品放入缓冲区中 in=(in+1)%n； //将缓冲区下标后移 signal（mutex）； //释放有界缓冲区 signal（full）；} //释放缓冲区填满一个空位的信号量 }

68 生产者-消费者问题 void consumerj（） //j=1,2,3, …,k { while（还需继续消费）
{ wait（full）； //检测缓冲区中是否有产品 wait（mutex）； //检测有界缓冲区是否可用 nextc=B[out]； //从缓冲区中取出一件产品 out=(out+1)%k； //将缓冲区下标后移 signal（mutex）； //释放有界缓冲区 signal（empty）； //释放取空一个缓冲区的信号量 消费一个产品；} } void main（） { parbegin produceri（）； consumerj（）； parend }

69 生产者-消费者问题 生产者-消费者问题是一个典型的同步与互斥的混合问 题。 在这一问题中应注意：
在每个进程中用于实现互斥的wait（mutex）和 signal（mutex）必须成对地出现，夹在两者之间的 代码段是进程的临界区； 对同步信号量empty和full的wait和signal操作， 同样需要成对地出现，但它们分别处于不同的进程 中； 在每个进程中的多个wait操作的次序不能随便颠倒， 一般来说，用于互斥的wait操作总是在后面执行， 而signal操作的次序则无关紧要。

70 哲学家进餐问题 哲学家只有拿到了左边和右边的筷子才能用餐.
S1 S0 P0 哲学家只有拿到了左边和右边的筷子才能用餐. 设信号量S0, S1, S2, S3, S4分别表示桌上的五支筷子,初始值均为1. S0=1; S1=1; S2=1; S3=1; S4=1. P4 P1 盘 S4 S2 P3 P2 S3

71 philosopher0（）； philosopher1（）；
哲学家进餐问题 semaphore chopstick[5] ; int i； for（ i=0；i<5；i++） chopstick[i]=1； void philosopheri( ) //i=0,1,2,3,4 { while（true） { think； hungry； wait（chopstick[i]）； wait（chopstick[(i+1)%5]）； eat； signal（chopstick[i]）； signal（chopstick[(i+1)%5]）；} } void main（） { parbegin philosopher0（）； philosopher1（）； …； philosopher4（）； parend }

72 哲学家进餐问题 在上述解法中，如果五位哲学家同时拿起左 边（或右边）的筷子，则桌上的五支筷子全 部分完了，当每位哲学家企图再拿起其右边 （或左边）的筷子时，将出现死锁。

73 哲学家进餐问题 为了防止死锁的发生，可以采取以下一些措施： 至多允许四位哲学家同时进餐
奇数号哲学家先取左边的筷子，然后再取右边的筷 子；偶数号哲学家先取右边的筷子，然后再取左边 的筷子。 每位哲学家必须取到左右两边的筷子才能进餐，否 则，一支筷子也不取。

74 进程通信 进程之间互相交换信息的工作称为进程通信。
高级通信机制是指用户可以直接利用操作系统 所提供的一组通信原语高效地传送大量数据的 一种通信方式。

75 进程通信的类型 消息传递通信机制 管道通信机制 共享内存通信机制

76 消息传递通信机制 消息传递通信机制是实现进程通信的常用方式。 这种通信方式既可以实现进程间的信息交换， 也可以实现进程间的同步。
消息传递通信机制可分为直接通信和间接通信 两种类型。

77 直接通信方式 所谓直接通信方式，是指发送进程利用操作系统所提供 的发送原语，直接将消息发送给接收进程，中间不经过 任何第三方媒介。
系统提供两条通信原语，分别用于发送和接收消息。 send（receiver，message）： 表示将消息message发送给接收进程receiver。 receive（sender，message）： 表示接收由发送进程sender发来的信息message。

78 直接通信方式 （1）消息缓冲通信机制中的数据结构 struct message buffer { sender； //消息发送者进程标识符
size； //消息长度 text； //消息正文 next； //指向下一个消息缓冲区的指针 } struct process control block { mq； //消息队列队首指针 mutex； //消息队列互斥信号量 sm； //消息队列资源信号量 }

79 直接通信方式 （2）发送原语 void send（receiver，a）
{ getbuf（a.size，i）； //根据消息长度a.size申请一个消息缓冲区i i.sender=a.sender； //将发送区a中的消息复制到消息缓冲区i中 i.size=a.size； i.text=a.text； i.next=0； //设置消息缓冲区指针域为空 getid（PCB set，receiver.j）；//获得接收进程内部标识符j wait（j.mutex）； //消息队列是临界资源，必须互斥访问 insert（j.mq，i）； //将消息缓冲区i插入消息队列的队尾 signal（j.mutex）； //释放消息队列的互斥信号量 signal（j.sm）； //释放发送一条消息的资源信号量 }

80 直接通信方式 （3）接收原语 void receive（b） { j=internal name； //获得接收进程的内部标识符
wait（j.sm）； //申请一条消息 wait（j.mutex）； //对消息队列采取互斥访问 remove（j.mq，i）； //将消息i从消息队列中移出 signal（j.mutex）； //释放消息队列的互斥信号量 b.sender=i.sender；//将消息缓冲区i中的消息复制到接收区b中 b.size=i.size； b.text=i.text； }

81 直接通信方式 进程A PCB(B) 进程B send(B,a) receive(b) mq mutex sm a sender:A
第一消息缓冲区 b 发送区a sender:A 接收区b size: 5 sender:A size: 5 text: Hello size: 5 text: Hello text:Hello next:0

82 间接通信方式 为了实现异步通信，必须采用间接的通信方式。 进程之间发送或接收消息通过一个共享的数据结 构——信箱（mailbox）进行。
消息可被理解成信件，每个信箱都有唯一的标识符。 当两个以上进程的拥有共享信箱时，它们就能进行 通信。

83 间接通信方式 （1）信箱 可存信件数 已有信件数 可存信件的指针 信件1 信件2 … 信箱头 取信件 信箱结构示意 信箱体

84 间接通信方式 为避免信件的丢失和错误地索取信件，通信时 应遵循如下规则：
① 若发送信件时信箱已满，则应把发送信件的进程 置成“等信箱”状态，直到信箱有空时才被释放。 ② 若取信件时信箱中无信，则应把接收信件的进程 置成“等信件”状态，直到信箱中有信件时才被释 放。

85 间接通信方式 （2）信箱的创建和撤销 （3）消息的发送和接收 struct mailbox
{ int size； //信箱大小，即信箱体中可容纳的信件数 int count； //信箱中现有的信件数 semaphore s1，s2； //s1为等待信箱信号量，s2为等待信件信号量 semaphore mutex； //信箱互斥访问的信号量 mail letter [size]； //信箱体 } （3）消息的发送和接收 send(mailbox，message)； //将一条消息发送到指定信箱 receive(mailbox，message)； //从指定信箱中接收一条消息

86 间接通信方式 （3）消息的发送和接收 void send（B，M） //B为信箱，M为要发送的消息 { int i；
wait（B.s1）； //申请信箱中的一个空信件区 wait（B.mutex）； //申请信箱的互斥信号量 i=B.count+1； //信箱中的信件数加1 B.letter[i]=M； //将信件放入第i个信件区 B.count=i； //设置新的信件数 signal（B.s2）； //释放信箱中又存入了一封信的信号量 signal（B.mutex）； //释放信箱的互斥信号量 }

87 间接通信方式 （3）消息的发送和接收 void receive（B，X） //B为信箱，X为要接收的消息 { int i；
wait（B.s2）； //申请收信件 wait（B.mutex）； //申请信箱的互斥信号量 B.count =B.count-1； //信箱中的信件数减1 X=B.letter[1]； //取信箱中的第一封信 if（B.count！=0） for（i=1；i<=B.count；i++） B.letter[i]=B.letter[i+1]； //信箱中的所有信件前移 signal（B.s1）； //释放信箱中又取走了一封信的信号量 signal（B.mutex）； //释放信箱的互斥信号量 }

88 线程的引入 在进程的并发执行过程中，系统要为之付出较大的开销。 把进程的两项功能“独立分配资源”和“被调度分派执 行”分离开来。
前一项任务仍然由进程来承担，作为系统资源分配和保 护的独立单位，无须频率地切换。 后一项任务交给称作线程的实体来完成，线程作为系统 调度和分派的基本单位，会被频繁地调度和切换。 在这种思想的指导下，产生了线程的概念。

89 线程的组成 线程的组成部分有： （1）线程控制块TCB及线程状态信息；
（2）未运行时所保存的线程上下文，从某种意义上说， 线程可以被看作进程内的一个被独立地操作的程序计数 器； （3）核心栈，在核心态工作时保存参数，在函数调用时 的返回地址，等等； （4）用于存放线程局部变量和用户栈的私有存储区。

90 线程的属性 （1）轻型实体 （2）独立调度和分派的基本单位 （3）可并发执行 （4）共享进程资源

91 小结 程序执行方式 顺序执行、并发执行 进程基本概念 进程特征、状态及状态转换 进程控制 四个进程控制原语 进程互斥
信号量机制、利用信号量解决互斥 进程同步 利用信号量解决同步

92 PURSUING EXCELLENCE / TOWARD SUCCESS WUCHANG UNIVERSITY OF TECHNOLOGY
武昌理工学院 Thank you！ 2015－11－22