第三章进程管理

第三章进程管理内容摘要：

P1 和 P2 间的同步 取用 P 2 计算结果计算 f u n c 1 ( x )进程 P2 算完 f u n c 2 ( y )计算 f u n c 2 ( y )置计算完标志终止进程 P1进程 P2YN第三章 进程管理 2. 进程间的互斥 图 资源互斥使用例 进程 A① 请求资源 R② 释放资源 R进程 B② 请求资源 R④ 释放资源 RR使用 R（阻塞）唤醒分配拒绝第三章 进程管理 又如 ， 设有两个进程 P P2， 它们共享同一变量 count, P P2 P1： R1∶ =count。 P2: R2∶ =count。 R1∶ =R1+1。 R2∶ =R2+1。 count∶ =R1。 count∶ =R2。 其中， R1 和 R2 是处理机的两个通用寄存器。 第三章 进程管理 它们可以按各自独立的速度前进 ， 所以运行的顺序也 P1: R1∶ =count。 P2: R2∶ =count。 P1: R1∶ =R1+1。 count∶ =R1。 P2: R2∶ =R2+1。 count∶ =R2。 第三章 进程管理 3. (1) 当有若干进程要求进入它们的临界区时 ， 应在有限时间内使一进程进入临界区。 换句话说 ， 它们不应相互等待而致使谁都不能进入。 (2) 每次最多有一个进程处于临界区内。 (3) 进程在临界区内逗留应在有限时间范围内。 第三章 进程管理 这种方法使用了一个物理实体 ， 称为锁 ， 用 W来表示。 锁有两种状态： W=0 表示锁已打开； W=1 表示锁被关闭。 加锁原语用 LOCK (W)表示 ， 测试 W， 若 W=1， 表示资源正在使用 ， 继续反复测试； 若 W=0， 置 W=1(加锁 )。 加锁原语用 LOCK (W)表示 ， L: if W=1 then go to L else W∶ [KG*8]= 1。 开锁原语用 UNLOCK (W)表示 ， W∶ =0； 第三章 进程管理 于是，两个进程 P1， P2使用如下程序实施进程的互斥： 进程 P1 进程 P2 LOCK (W) LOCK (W) S1 S2 UNLOCK (W) UNLOCK (W) 其中 S1和 S2分别为进程 P1 和 P2 的临界区。 第三章 进程管理 在有些系统中 ， 上述的加锁 、 开锁操作可用机器硬件指令完成。 例如 IBM/370 中就有一条称为 “ 测试并置位 ”指令 TS。 该指令的功能是按第二操作域指出的地址从主存中取出一个字节 ， 其最高位 (最左边的位 )为 0 时 ， 置条件码为 0；否则置条件码为 1， 并将该字节的所有位均置 1。 于是加锁原语 LOCK (W)可用指令 TS W BNZ * 4 第三章 进程管理 来代替 ， 其中 BNZ表示不等于 0 转移 ， * 4 表示本指令地址减 4(BNZ本身是 4 字节指令 )。 即当 W不为 0 时转移到上一条指令 TS继续测试 ， 否则停止测试 ， 进入临界区。 请注意 ， 测试 W和置 W=1 是在一个指令周期内完成的。 开锁原语 UNLOCK (W) MVI W， X′00′ 来完成， MVI将一个全 0 的字节送入 W中。 第三章 进程管理 信号量和 P、 V操作 1. 信号量及 P、 V操作 信号量或信号灯 ， 是交通管理中的一种常用设备。 交通管理人员利用信号灯的颜色 (红 、 绿 )实现交通管理。 在操作系统中 ， 信号量是表示资源的实体 ， 是一个与队列有关的整型变量 ， 其值仅能由 P、 V操作来改变。 操作系统利用信号量对进程和资源进行控制和管理。 根据用途不同 ， 分为公用信号量和私用信号量。 公用信号量通常用于实现进程之间的互斥 ，初值为 1， 它所联系的一组并发进程均可对其实施 P、 V操作；私用信号量一般用于实现进程间的同步 ， 初值为 0 或为某个正整数 n， 仅允许拥有它的进程对其实施 P操作。 第三章 进程管理 P、 V操作是定义在信号量 S上的两个操作 ， 其定义如下： P(S)： ① S∶ =S1。 ② 若 S≥0， 则调用 P(S) ③ 若 S0， 则调用 P(S)的进程被阻塞 ， 并把它插入到等 待信号量 S的阻塞队列中。 V(S)： ① S∶ =S+1。 ② 若 S0， 则调用 V(S) ③ 若 S≤0， 从等待信号量 S的阻塞队列中唤醒头一个进程 ， 然后调用 V(S)的进程继续运行。 第三章 进程管理 P、 V操作可表示为如下两个过程： Procedure P(Var S:Semaphore)。 begin S∶ =S1。 if S0 then W(S) end。 {P} Procedure V(Var S:Semaphore)。 begin S∶ =S+1。 if S≤0 then R(S) end。 {V} 第三章 进程管理 2. 利用信号量实现进程的互斥 利用信号量可以方便地解决临界区问题。 设 S为两进程互斥的公用信号量 ， 初值赋予 1， 表明该临界资源未被占用。 只需把临界区的程序段置于 P(S)和 V(S)之间 ， 即可实现两进程的互斥。 例如进程 P1 和进程 P2 按如下安排 ， 即可实现互斥： 进程 P1 进程 P2 P(S) P(S) S1 S2 V(S) V(S) 第三章 进程管理 例 1 前面例子中的公用变量 count, 也是一个临界资源。 两个并发进程对 count的操作必须互斥地执行。 对此 ， 可写出如下程序： begin count: integer。 S:semaphore。 count∶ =0。 S∶ =1。 cobegin process p1 R1: register。 begin P(S)。 第三章 进程管理 R1∶ =count。 R1∶ =R1+1。 count∶ =R1。 V(S) end。 process P2 R2: register。 begin P(S)。 R2∶ =count。 R2∶ =R2+1。 count∶ =R2。 V(S) end。 coend。 end。 第三章 进程管理 例 2 设一民航航班售票系统有 n个售票处。 每个售票处通过终端访问系统中的公用数据区 ， 假定公共数据区中一些单元 xk(k=1, 2, …)分别存放 月 日 次航班的现存票数。 设P1， P2， …， Pn表示各售票处的处理进程 ， R1, R2, …, Rn表示各进程执行时所用的工作单元。 用信号量实现进程间互斥的程序如下： begin S: Semaphore。 S∶ =1 cobegin 第三章 进程管理 Process P i(i=1, 2, …, n) begin 按旅客订票要求找到 xk。 P(S) Ri∶ =xk。 if Ri≥1 then begin Ri∶ =Ri1。 xk∶ =R1。 V(S) end else begin V(S)。 输出 “ 票已售完 ” end end。 coend。 end。 第三章 进程管理 3. 利用信号量实现进程间的同步 一般来说， 信号量初值为 0， 两个进程之间的同步模型如下： 进程 P1 进程 P2 L1： P(S) L2： V(S) 第三章 进程管理 例 1 用信号量实现司机和售票员的同步。 设 S1和 S2分别为司机和售票员的私用信号量 ， 初值均为 0， 则司机和售票员的同步过程描述如下： 第三章 进程管理 例 2 设进程 A、 B是两个相互合作的进程 ， 共用一个缓冲区。 进程 A负责从卡片输入机读入卡片送到缓冲区 ， 进程 B取走缓冲区中的卡片信息进行加工处理。 进程 A在完成将卡片送入缓冲区后 ， 给进程 B发一信号。 进程 B收到信号后 ， 取走卡片信息进行加工处理。 反之 ， 进程 B取走卡片信息后 ， 给进程 A发一信号 ， 进程 A再将卡片信息读入缓冲区。 为此 ， 我们利用两个私用信号量 S1和 S2， 其初值均为 0， 信号量 S1表示缓冲区是否有卡片信息 ， 信号量 S2表示缓冲区信息是否被取走。 利用 P、 V操作实施进程 A、 B 第三章 进程管理 第三章 进程管理 4. 生产者 — 消费者问题 (ProducerConsumer Problems) 图 生产者 — 消费者问题 123456…0n 1n2C1C2C3C K…P1P2P3P m…RP第三章 进程管理 了实现上述两组进程互斥地进入临界区 ， 我们设置两个 (1) 公用信号量 S， 初值为 1， 表示没有进程进入临界区 ， (2) 私用信号量 S0， 用以表示产品数目 ， 初值为 0 (3) 私用信号量 Sn， 用以表示可用缓冲区数 ， 初值为 n。 生产者 — 消费者进程描述如下： 第三章 进程管理 第三章 进程管理 生产者和消费者可按如下方式并发执行： begin B: array［ 0n1］ of integer。 P, R: integer。 S, S n, S 0: semaphore。 p∶ =R∶ =0 S∶ =1。 S n∶ =n。 S 0∶ =0。 cobegin process producer i(i=1, 2, ……, m) begin L1: produce a product。 P(S n)。