PV操作专讲

第 3 章 进程的同步与通信 1 第 3 章 进程的同步与通信 3.13.13.13.1 基本点、重点和难点 在多道程序系统中，程序的执行失去了封闭性和再现性，程序的运行具有不确定性， 这是我们所不希望看到的。如果多道程序系统中程序的执行不加控制，程序的每次执行就 可能得到不同的结果。如何使多道程序的执行的结果具有再现性和确定性？这就需要通过 进程间的同步和互斥来实现，将原来无序的、不确定的程序的执行转换为有序的、确定的 执行。 解决同步和互斥问题最常用的方法就是信号量的方法，通过在程序中使用 P、V 操作 达到同步和互斥的目的。在使用信号量和 P、V 操作时，很多学生觉得无从下手，感到困 惑。这主要是因为他们对进程的本质理解还不够深入、对多道程序设计的原理还不够清楚、 对信号量的含义还不够明白造成的。但这部分内容又是各类考试的必考点。 本章有很多经典问题，其解题的方法和 答案 八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案 在很多资料上都可以见到。但这些解题的 结果是专家们长期精炼而成的，初学者在开始时不可能得到这样的结果。对于初学者而言， 迫切想知道的已不单是解题的结果，而是问题解决的思考和分析过程。为此，本章中对一 些问题的解答给出了详细的分析过程。 3.1.13.1.13.1.13.1.1 进程的同步和互斥的概念 1. 同步(Synchronization) 相互合作的进程需要在某些点上协调，先到达某点的进程需要等待后到达的进程，进 程间的这种协调关系叫同步。 2. 互斥(Mutex) 互斥是一种特殊的同步方式。当多个进程需要使用相同的资源，而此资源在任一时刻 却只能供一个进程使用，获得资源的进程可以继续执行，没有获得资源的进程必须等待。 进程间的这种相互排斥关系叫互斥。 3. 临界资源与临界区(Critical(Critical(Critical(Critical ResourceResourceResourceResource andandandand CriticalCriticalCriticalCritical Section)Section)Section)Section) 临界资源是一次只允许一个进程使用的资源。 临界区是在进程中操作临界资源的程序段。 3.1.2锁操作法实现互斥 1111．基本思想 实现互斥的基本思想是使多个进程不能同时进入临界区。给每个临界资源分配一个 锁：锁打开时，进程进入临界区，将锁关闭，开始操作临界资源，离开临界区时，将锁打 第 3 章 进程的同步与通信 2 开；锁关闭时，需要进入临界区的进程要等待。 2222．操作锁的步骤 (1) 确定临界资源； (2) 确定临界区； (3) 确定锁个数； (4) 设置锁操作。 3.1.33.1.33.1.33.1.3 信号量与 P、V操作 1. 信号量的引入       1965年，荷兰学者 Dijkstra 提出的信号量机制是一种卓有成效的进程同步工具。在长 期且广泛的应用中，信号量机制得到了很大的发展：它从整型信号量经记录型信号量，进 而发展为“信号量集”机制。现在的信号量机制已被广泛的应用于单处理机、多处理机系 统和计算机网络中。 2.2.2.2. 信号量(Semaphore)(Semaphore)(Semaphore)(Semaphore) 设 S为信号量，可以将 S 看成一个信号灯，但 S 能比信号灯 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 达更丰富的含义。 (1) 当 S>0 时，是绿灯，进程看到绿灯可以通过。S 值越大，通过进程的能力越大， 供进程使用的相关资源越多。S值反映了可供进程使用的相关资源的数量。 (2) 当 S<=0 时，是红灯，进程看到红灯需要等待。此时|S|表示等待 S 信号的进程的个 数。 3333．信号量的操作 最初由 Dijkstra 把整型信号量定义为一个整型量，除初始化外，仅能通过两个标准的 原子操作 Wait(S)和 Signal(S)来访问，其它方法都不能操作信号量。这两个操作很长时间以 来，一直被分别称为 P、V 操作，因为希腊语的 Wait词头为 P，Signal的词头为 V。 对信号量的操作定义如下： (1) P(S)或 Wait(S)：是等待信号的操作，是查看信号的操作，是看灯操作。若为绿灯， 进程继续前进；若为红灯，进程必须等待。在该操作中，进行 S=S-1，操作使 S的值向负 方向转化，即操作使信号灯 S 向红的方向转化。 (2) V(S)或 Signal(S)：是发送信号的操作。在该操作中，进行 S=S+1, 操作使 S的值向 正方向转化，即操作使信号灯 S向绿的方向转化。 4． P(S)、V(S)的实现 (1) 整型信号量 P(S)： while s<=0 do no-op S：=S-1； V(S)：S：=S+1； (2) 记录型信号量 在整型信号量机制中的 wait 操作，只要是信号量 S<=0，就会不断地测试。因此，该 机制并未遵循“让权等待”的准则，而是该进程处于“忙等”的状态。记录型信号量机制 则是一种不存在“忙等”问题的进程同步机制。但在采取了“让权等待”的策略后，又会 第 3 章 进程的同步与通信 3 出现多个进程等待访问同一临界资源的问题。为此，在信号量机制中，除了需要一个用于 代表资源数目的整型变量 value 外，还应增加一个进程链表 L，用于链接或记录上述的所 有因此信号量而等待的进程。记录型信号量是由于它采用了纪录型的数据结构而得名的。 它所包含的上述两个数据项可描述为： type semaphore=record value:integer; L:list of process; End 相应地，wait(s)和 singal(s)操作可描述为： Procedure wait(s) var s:semaphore; Begin S.value:=S.value-1; If S.value<0 then Begin Insert(*, S....L)； Block(*)； End End Procedure signal (s) var S:semaphore; Begin S.value:=S.value+1; If S.value<=0 then Begin N=remove(S....L) ; Wakeup(N); End End 每次的 wait 操作，意味着进程请求一个单位的资源，因此描述为 S.value:=S.value-1； 当 S.value<0 时，表示资源已分配完毕，进程需要等待而进入阻塞状态。为了便于唤醒， 在当前进程需要进入阻塞状态前，将当前进程号插入到信号量链表 S.L 中，进程调用 block 原语，进行自我阻塞，放弃处理机。因为只有在 S.value<0 时进程才进入阻塞状态，所以 当 S.value<0 时，S.value 的绝对值表示在该信号量阻塞进程链表中进程的数目。 每次 signal操作，表示执行进程释放一个单位资源，故 S.value:=S.value+1 操作表示资 源数目加 1。若加 1 后仍是 S.value<=0,则表示在该信号量链表中，仍有等待该资源的进程 被阻塞，故还应从该信号量链表中移出一个进程，调用 wakeup 原语将该进程唤醒。 第 3 章 进程的同步与通信 4 3.1.4 信号量实现进程的同步与互斥 1111.... 利用信号量实现互斥 当信号量用于互斥时，信号量 mutex的含义是进程是否可以操作临界资源，进程是否 可以进入临界区。mutex>0 时，进程可以操作临界资源，可以进入临界区，否则 mutex<=0 时进程必须等待。为了使多个进程能互斥地访问某临界资源，只需为该临界资源设置互斥 信号量 mutex。如果每次只允许一个进程操作临界资源，其初值为 1；如果最多允许 k 个 进程使用某个资源，信号量的初值为 k。然后将各进程的临界区 CS 置于 wait(mutex)和 signal(mutex)操作之间即可。这样，每个欲访问该临界资源的进程，在进入临界区之前， 都要对 mutex 执行 wait 操作。若该资源此刻未被访问，本次 wait 操作成功，进程便可进 入自己的临界区，这时若有其他的进程欲进入自己的临界区，进程执行 wait操作必然阻塞， 从而保证了该临界资源被互斥访问。当访问临界资源的进程退出临界区后，进程对 mutex 执行 signal 操作，释放该临界资源。 要注意的是，在利用信号量机制实现进程互斥时，wait(mutex)和 signal(mutex)必须成 对出现。缺少 wait(mutex)将会导致系统混乱，不能保证对临界资源的互斥访问；而缺少 signal(mutex)将会使临界资源永远不被释放，从而使等待该资源而阻塞的进程永远不能被 唤醒。 2.2.2.2. 利用信号量实现同步 当信号量用于互斥时，信号量 S的含义是某事件是否发生，某条件是否满足。 下面看一下如何用信号量来描述程序或语句之间的前趋关系。 设有两个并发执行的进程 P1 和 P2。P1 中有语句 S1；P2 中有语句 S2。如果我们希望 执行 S1 后再执行 S2。为实现这种前趋关系，我们只需使进程 P1 和 P2 共享一个公用信号 量 S，并赋予其初值为 0，将 signal(s)操作放在 S1 后面；而在 S2 语句前面插入 wait(s)操 作，即： 在进程 P1 中，S1；signal(s) 在进程 P2 中，wait(s)；S2 S的含义是 S1 语句是否执行：S1 执行后，信号量 S>0；，S1 没有执行时，信号量 S<=0。 初始状态 S1 语句没有执行，因此 S<=0。因为 S1 执行后 S 应变成大于 0 的值，所以 S 应 被初始化为 0。这样，若 P2 先执行必定阻塞自己，只有在进程 P1 执行完 S1；signal(s)后， 使 S增为 1 时，P2 进程才能执行语句 S2。 同样，可以利用信号量，按下图语句间的前趋关系，写出一个可并发执行的程序。 详细描述如下： 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; 第 3 章 进程的同步与通信 5 begin wait(c);S4;signal(f);end; begin wait(d);S5;signal(g);end; begin wait(e);wait(f);wait(g);S6;end; parend end 图 4.1 进程前趋关系图 3. 解决同步和互斥问题的步骤 (1) 确定并发和顺序操作 哪些操作是并发的？哪些操作是顺序的？这是解决同步和互斥问题时首先要确定的。 并发操作可以用多个进程实现，同步和互斥就发生在这多个进程之间。多个进程操作同一 临界资源就是进程间的互斥问题，多个进程要按一定的顺序进行操作就是进程间的同步问 题。 (2) 确定互斥和同步的规则 分析具体问题，确定同步和互斥的基本方式，确定能够进行正确操作的条件，在这些 条件中隐含着同步和互斥的规则。 (3) 确定同步、互斥的操作 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 按操作的步骤，写出每个进程操作的流程 (4) 确定信号量的个数和含义 根据同步和互斥规则以及操作流程确定信号量的个数，确定信号量代表的含义，只有 确切地知道信号量所代表的含义，设置这个信号量才有意义。 (5) 确定信号量的初值 同步信号量的初值则要根据进程的初始状态确定，具体问题要具体分析，没有统一的 方法。 (6) 确定 P、V 操作的位置 S1 S3 S5 S6 S2 S4 第 3 章 进程的同步与通信 6 根据同步和互斥规则和每个进程的操作流程就可以确定 P、V 操作的位置。 需要说明的是无论是互斥问题还是同步问题，只要是需要进程进入阻塞状态，就必须 想到在什么时候将进程唤醒。 初学者开始时可以按上述步骤解决同步和互斥问题，熟练后，就可以不局限于这些规 则，灵活应用。这好象学骑自行车一样，开始时需要左看右看，掌握了基本要领，熟练操 作以后就可以随心所欲。 以上讲述的只是一般的求解规则，虽然有一定的可操作性，但在实际应用中还是要针 对具体情况，多做多想，领悟出其中的原理和窍门。 4. 同步和互斥的经典问题 (1) 生产者和消费者问题（PCP:Producer-Consumer Problem）。例如，消息缓冲通信的 管理。 (2) 读者和写者问题（RWP:Reader-Writer Problem）。例如，共享文件的读写问题。 (3) 哲学家进餐问题（DPP:Dining Philosopher Problem）。例如，进程对多类资源的竞 争使用。 3.2 例题解析 例 3.2.13.2.13.2.13.2.1 多道程序系统程序的执行失去了封闭性和再现性，因此多道程序的执行不需 要这些特性，这种说法是否正确 ？ 解 这种说法不正确。可以想象，如果一个程序在多道程序系统中，在相同的输入的 情况下，多次执行所得结果是不同的，有谁还敢使用这个程序？因此，多道程序的执行也 需要封闭性和再现性，只不过单道程序系统的封闭性和再现性是先天固有的，多道程序系 统的程序执行要想获得封闭性和再现性，需通过程序员的精心设计才能得到。所使用的方 法就是同步和互斥的方法。 例 3.2.3.2.3.2.3.2.2222 多个进程对信号量 S 进行了 5次 P操作，2 次 V 操作后，现在信号量的值是 -3，与信号量 S 相关的处于阻塞状态的进程有几个？信号量的初值是多少？ 解 (1)因为 S的当前值是-3，因此因为 S处于阻塞状态的进程有 3 个； (2)因为每进行一次 P(S)操作，S 的值都减 1，每执行 1 次 V 操作 S 的值加 1，故信号 量的初值为-3+5-2=0; 例 3.2.3.2.3.2.3.2.3333 如下锁的实现方法存在什么缺点？如何改进？ LOCK(X) UNLOCK(X) { { do while X=1 ; X=0; X=1 第 3 章 进程的同步与通信 7 } } 解 存在的缺点是：当锁是关闭时，采用的是循环等待的方法，这样的等待还是要占 用处理机的时间，应该采用阻塞等待的方法。 改进的锁实现如下： LOCK(X) UNLOCK(X) { { if X.value=1 if not empty(X.L) { insert( *, X.L); { P=remove(X.L); Block (*) Wakeup(P) } } else X.Value=1 else X.Value=0 } } 这里 X....value 是锁的值，X....L 是存放由于锁 X 而阻塞的进程的队列。insert( *, X.L) 将当前进程的进程号插入到 X....L，remove(X.L)是从 X....L中移出一个进程号。 例 3.2.3.2.3.2.3.2.4444 使用多个进程计算 Y=F1(X)+F2 (X). 解 (1) 确定并发和顺序操作 在这个问题中，F1(X)和 F2 (X)的计算是可以并行处理的，因此 F1(X)和 F2 (X)可以分 别出现在两个进程中。 (2) 确定互斥或同步的规则 在 F1(X)+F2 (X)中，必须在 F1(X)和 F2(X)计算完毕，才能进行加法运算，因此本问题 是同步问题。 (3) 同步的操作流程 〈进程 main〉 创立进程 p1 来计算 F1(X)； 创立进程 p2 来计算 F2(X)； F1(X)计算是否完成？没有，等待；① F2(X)计算是否完成？没有，等待；② 进行加法运算。 〈进程 p1〉 y1= F1(X)； 设置 F1(X)计算完成标志； ③ 〈进程 p2〉 y1= F2(X)； 设置 F2(X)计算完成标志。 ④ 第 3 章 进程的同步与通信 8 (4) 确定信号量的个数和含义 根据同步规则以及操作流程确定信号量的个数是 2 个，S1 和 S2： S1 含义是 F1(X)计算是否完成； S2 含义是 F2(X)计算是否完成。 (5) 确定信号量的初值 S1=0； S2=0。 (6) 确定 P、V 操作的位置 上面①处是一个 P 操作，P(S1)； 上面②处是一个 P 操作，P(S2)； 上面③处是一个 V 操作，V(S1)； 上面④处是一个 V 操作，V(S2)。 解法 1111 Main ( ) Public y, y1, y2,. P1, P2 Semaphore S1,S2 { S1=0; S2=0; P1=Creat(N-F1, F1,x,……); P2=Creat(N-F2, F2, x,……); P(S1); P(S2); y=y1+y2; } Procedure F1(x) { y1= 计算 1; V(S1)； } Procedure F2(x) { y2=计算 2; V(S2) } 解法 2222 第 3 章 进程的同步与通信 9 Main ( ) Public y, y1, y2,. P1,x Semaphore S1 { input(x); S1=0; P1=Creat(N-F1, F1,x,……); Y2=F2(x); P(S1); y=y1+y2; } Procedure F1(x) { y1= 计算 1; V(S1) } 采用 2个进程和 1 个信号量来实现 Y=F1(X)+F2 (X)的时候，采用的方法是父进程创立 子进程，F1(X)在子进程中计算，F2 (X)在父进程中计算，因此 F1(X)和 F2(X)计算仍然是 并发进行的。S1 信号量的含义为 F1(X)是否完成。改进的方法比原来的方法节约一个进程 和一个信号量，但并发操作的程度并没有降低。 例 3.2.53.2.53.2.53.2.5 生产者—消费者问题演变。 情况 1111 一个 buffer，一个生产者，一个消费者，生产者只生产一个东西，消费者只 进行一次消费，即：生产者只进行一次 putdata操作，消费者只进行一次 getdata 操作。 解 这是一个同步问题，生产者和消费者分别是 2个并发的进程。 （1）操作规则 如果 buffer 为空，则消费者只能等待。 （2）操作流程 <生产者> { putdata； 设置 Buffer 有数据标志 V(S) } <消费者> { 判断 buffer 是否有产品，没有则等待； getdata； } 第 3 章 进程的同步与通信 10 (3) 信号量 设置 1 个信号量 full，full表示 buffer 是否有数据，初值为 0。 (4) P、V 操作实现 var full:semaphore:=0; buffer: array [1] of item; begin parbegin producer: begin putdata； V(full); end consumer: begin P(full); getdata; end parend end 情况 2222 一个 buffer，一个生产者，一个消费者，生产者不断地进行 putdata 操作，消 费者不断地进行 getdata 操作，即：生产者不断地生产，消费者不断地消费 (1) 操作规则 只有 buffer为空时才能进行 putdata操作；只有 buffer有数据时才能进行 putdata 操作。 (2) 操作流程 <生产者> { repeat 判断 buffer 是否为空，不空则等待； putdata ； 设置 buffer 有数据的标志； until false } <消费者> { repeat 判断 buffer 是否有数据，没有数据则等待； getdata； 第 3 章 进程的同步与通信 11 设置 buffer 为空标志； until false } (3) 信号量 设置 2 个信号量 full和 empty。 full表示 buffer 是否有数据。因为进程在初始状态时，buffer 中没有数据，故初值为 0， 变化范围-1~1。 empty 表示 buffer是否为空。因为进程在初始状态时，buffer 为空，故初值为 0 初值为 1，变化范围-1~1。 (4) P、V 操作实现 var full:semaphore:=0; emptyl:semaphore:=1; buffer: array [1] of item; begin parbegin producer： begin repeat P(empty)； putdata； V(full); until false end consumer： begin repeat P(full)； getdata； V(empty)； until false. end parend end 情况 3333 一个 buffer，多个生产者，多个消费者，多个生产者和消费者都在不断地存 取 buffer，即生产者不断地进行 putdata操作，消费者不断地进行 getdata 操作。 (1) 操作规则 只有 buffer为空时才能进行 putdata操作；只有 buffer有数据时才能进行 putdata 操作。 这时 buffer 变成了临界资源，不允许多个进程同时操作 buffer，即不允许多个消费者 第 3 章 进程的同步与通信 12 同时进行 gedata，不允许多个生产者同时进行 putdata操作。 (2) 操作流程 <生产者> { repeat 判断 buffer 是否为空，不则等待； 是否可操作 buffer； putdata； 设置 buffer 可操作标志； 设置 buffer 有数据的标志； until false } <消费者> { repeat 判断 buffer 是否有数据，没有则等待； 是否可操作 buffer； getdata ； 设置 buffer 可操作标志； 设置 buffer 为空标志； until false } (3) 信号量 设置 3 个信号量 full、empty 和 B-M。 full表示 buffer 是否有数据，初值为 0； empty 表示 buffer 是否为空，初值为 1； B-M 表示 buffer是否可操作，初值为 1。 由于 buffer 只有一个，full和 empty 可以保证对 buffer 的正确操作，故 B-M 是多余的， 可以省略。 (4) P、V 操作实现 <生产者> <消费者> { { repeat repeat P(empty)； P(full)； P(B-M)； P(B-M)； putdata； getdata； V(B-M)； V(B-M)； 第 3 章 进程的同步与通信 13 V(full)； V(empty)； until false. until false } } 情况 4444 多个生产者，多个消费者，N 个 buffer，多次循环存取 buffer，即，即多个生 产者不断地进行 putdata操作，多个消费者不断地进行 getdata 操作。 (1) 操作规则 只有 buffer有空间才能进行 putdata操作； 只有 buffer 有数据才能进行 putdata操作； 这时 buffer 变成了临界资源，不允许多个消费者和生产者同时对同一个 buffer 进行 gedata 和 putdata操作。 (2) 操作流程 <生产者> { repeat 判断 buffer 是否有空间，没有则等待； 是否可操作 buffer； putdata； 设置 buffer 可操作标志； 设置 buffer 有数据的标志； until false } <消费者> { repeat 判断 buffer是否有数据，没有则等待； 是否可操作 buffer； getdata； 设置 buffer可操作标志； 设置 buffer有空间标志； until false } (3) 信号量 full表示 buffer 是否有数据，初值为 0; empty 表示 buffer 是否为空，初值为 N； B-M 表示 buffer是否可操作，初值为 1。 (4) P、V 操作实现 <生产者> <消费者> 第 3 章 进程的同步与通信 14 { { repeat repeat P(empty)； P(full)； P(B-M)； P(B-M)； putdata； getdata； V(B-M)； V(B-M)； V(full)； V(empty)； until false until false } } (5) 改进的 P、V 操作实现 在上述的实现中，putdata 和 getdata 操作都在临界区中，因此多个进程对多个 buffer 的操作是不能并发进行的，进程间并行操作的程度很低。实际上只要保证多个进程同时操 作不同 buffer就可以实现对整个 buffer的并行操作。因此，只要保证为不同的进程分配不 同 buffer，putdata 和 getdata 操作是可以同时进行。这样互斥不是发生在对 buffer 的存取操 作上，而是发生在对 buffer 的分配上，这个时间与存取 buffer 的时间相比是较短的，因此 减少了进程处于临界区的时间。这里引入２个函数: getE_buffer()，返回值是空的 buffer 号； getD_buffer()，返回值是有数据的 buffer 号。 getE_buffer()和 getD_buffer()通过将 buffer转换成循环队列的方法来实现对 buffer的 分配。buffer 设有 Pbuff，Pdata 两个指针，分别指向空闲 buffer 和有数据 buffer 的头，每 进行一次 getE_buffer()和 getD_buffer()，Pbuff 和 Pdata 两个指针分别向后移动一个位置。 GetE_buffer( ) {c=Pbuff Pbuff=(Pbuff+1)MOD N; Return( c) } getD_data( ) {c=Pdata; Pdata=(pdata+1)MOD N; Return(c) } 改进的程序描述如下： var mutex.empty,full:semaphore:=1,n,0; buffer: array [0,…,n-1] of item; Pbuff，Pdata: integer:=0,0; begin parbegin 第 3 章 进程的同步与通信 15 producer: begin repeat ┇ P(empty); P(B_M); in:=getE_buffer(); V(B_M) putdata(in); V(full); until false; end consumer:begin repeat P(full); P(B_M); out:=getD_buffer(); V(B_M); Getdata(out); V(empty); until false end parend end 例 3.2.63.2.63.2.63.2.6 设公共汽车上，司机和售票员的活动分别为：司机的活动为启动车辆，正常 行车，到站停车；售票员的活动为关车门，售票，开车门。试问： (1) 在汽车不断地到站、停车、行驶过程中，司机和售票员的活动是同步关系还是互 斥关系？ (2) 用信号量和 P、V 操作实现他们间的协调操作。 解 (1) 确定并发和顺序操作 在这个问题中，司机与售票员间是并行操作的，司机和售票员本身的操作是顺序进行 的。因此司机是一个进程，售票员是一个进程，它们之间是同步关系。 (2) 确定同步的规则 根据一般常识，司机和售票员在车上的操作规则如下： 1) 售票员操作的规则是只有司机停车后，售票员才能开门让乘客上下车； 2) 司机操作的规则是只有售票员关门后，司机才能启动开始行驶汽车。 可见，售票员关车门后，要向司机发开车信号，司机接到开车信号后才能启动车辆。 第 3 章 进程的同步与通信 16 在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开车门，让乘客上 下车。因此司机启动车辆的动作必须与售票员的动作取得同步；售票员开车门的动作也必 须同司机停车取得同步。 （3）进程的操作流程 <售票员进程> do while T 关车门； 设立车门已关标志; 售票； 是否停车？没停则等待; 开车门； 上下乘客； enddo <司机进程> do while T 是否关门？没关则等待; 启动车辆； 正常行车； 到站停车； 设立车停标志; enddo (4) 确定信号量的个数和含义 根据同步规则以及操作流程确定信号量的个数是 2 个，S1 和 S2。 S1 的含义是否关门； S2 的含义是否停车。 (5) 确定信号量的初值 S1=0； S2=1。 (6) 确定 P、V 操作的位置 司机操作中，是否关门？没关则等待，这是一个 P操作，P(S1)； 司机操作中，设立停车标志，这是一个 V 操作，V(S2)； 售票员操作中，是否停车？没停则等待，这是一个 P 操作，P(S2)； 售票员操作中，设立关门标志，这是一个 V 操作，V(S1)。 (7) P、V 操作实现 int S1=0; int S2=1; main() 第 3 章 进程的同步与通信 17 { cobegin driver(); busman(); coend } driver() { do while T { P(S1)； 启动车辆； 正常行车； 到站停车； V(S2)； } } busserver () { do while T { 关车门； V(S1)； 售票； P(S2)； 开车门； 上下乘客； } } 例 3.2.73.2.73.2.73.2.7 在 OS 中引入管程的目的是什么？ 解 在 OS 中引入管程的目的是为了更简便、更可靠地解决进程之间的同步、互斥问题。 在未引入管程之间，进程间的同步、互斥问题是由程序员处理的。例如，在临界区的 前后插入 P、V 操作。但是，由程序员处理同步、互斥问题有可能引入种种人为的错误。 管程主要是管理对共享数据的操作和使用，即把对共享数据互斥使用的控制这一任务从程 序员身上，交由编译程序去处理，这样既方便了编程，又不会产生人为的同步、互斥上的 错误。 例 3.2.83.2.83.2.83.2.8 说明管程中条件变量的含义及作用。 解 管程中的条件变量（类型为 Condition）是供调用管程中外部过程的进程执行 Wait 和 Signal操作将自己挂起和解挂的变量。可通过与信号量的比较来认识条件变量： (1)信号量要赋初值而条件变量不赋初值，它只是一个队首指针； (2)在信号量上执行 P操作的进程不一定会被阻塞，而在条件变量上执行 Wait操作的 第 3 章 进程的同步与通信 18 进程肯定被挂起； (3)在信号量上的 V 操作将导致信号量值加 1，若增加后的值小于等于 0，则要唤醒在 信号量上等待的进程，但唤醒者不受什么影响；而在条件变量上的 Signal操作却有两种处 理方式：P 等待，直到 Q 离开管程，或等待另一条件；Q 等待，直到 P 离开管程，或等待 另一条件。P、Q 是两个进程。 例 3.2.9 如果信号量Ｓ的初值是５，现在信号量的值是 -５，那么系统中的相关 进程至少执行了几个Ｐ(S)操作？ 与信号量S相关的处于阻塞状态的进程有几个？如果要 使信号量 S 的值大于 0，应该进行怎样的操作？ 解 (1)因为每执行一次 P 操作 S的值减 1，5-（-5）=10，在这期间有可能有进程执行 V 操作，使 S的值加 1，所以至少执行了 10 次 P(S)； (2) 5 个； (3) 6 个 V(S) 或 5 个以上。 例 3.2.3.2.3.2.3.2.10101010 如下图所示，有多个 PUT 操作同时向 BUFF1 放数据，有一个 MOVE 操作不断 地将 BUFF1 的数据移到 Buff2，有多个 GET 操作不断地从 Buff2 中将数据取走。BUFF1 的 容量为 m，BUFF2 的容量是 n, PUT、 MOVE、 GET 每次操作一个数据，在操作的过程中要 保证数据不丢失。试用Ｐ、Ｖ原语协调 PUT、 MOVE 的操作，并说明每个信号量的含义和 初值。 图 4.2 进程操作图 解 (1) 确定并发的操作 本问题是把 2 个消费者和生产者问题综合在一起。多个 PUT 操作与一个 MOVE 操作 并发进行，多个 GET 操作与一个 MOVE 操作并发进行。因此本题涉及三类进程：PUT 类 进程，有多个；GET 类进程，有多个；MOVE 类进程，有 1个。 (2) 操作规则 1) 只有 buff1有空间才能进行 PUT 操作； 2) 只有 buff1有数据，buff2有空间才能进行 MOVE 操作； 3) 只有 buff2有数据才能进行 GET 操作； 4) 不允许多个进程同时操作 buff1； GETPUT Buff1 Buff2 MOVE 第 3 章 进程的同步与通信 19 5) 不允许多个进程同时操作 buff2。 (3) 操作流程 { repeat 判断 buff1 是否有空间，没有则等待； 是否可操作 buff1； PUT； 设置 buff1 可操作标志； 设置 buff1 有数据的标志； until false } { repeat 判断 buff1 是否有数据，没有则等待； 判断 buff2 是否有空间，没有则等待； 是否可操作 buff1； 是否可操作 buff2； MOVE； 设置 buff1 可操作标志； 设置 buff2 可操作标志； 设置 buff1 有空间标志； 设置 buff2 有数据标志； until false } { repeat 判断 buff2 是否有数据，没有则等待； 是否可操作 buff2； GET； 设置 buff1 可操作标志； 设置 buff1 有空间标志； until false } 第 3 章 进程的同步与通信 20 (4) 信号量 设置 6 个信号量 full1、empty1、B-M1、full2、empty2、B-M2，它们的含义和初值如 下： 1) full1 表示 buff1 是否有数据，初值为 0； 2) empty1 表示 buff1 有空间，初值为 m； 3) B-M1 表示 buff1是否可操作，初值为 1； 4) Full2表示 buff2是否有数据，初值为 0； 5) Empty2 表示 buff2有空间，初值为 n； 6) B-M2 表示 buff2是否可操作，初值为 1； (5) P、V 操作实现 { repeat P(empty1)； /*判断 buff1是否有空间，没有则等待 */ P(B-M1)； /*是否可操作 buff1*/ PUT； V(B-M1)； /*设置 buff1可操作标志 */ V(full1)； /*设置 buff1 有数据的标志 */ until false } { repeat P(full1)； /*判断 buff1是否有数据，没有则等待*/ P(empty2)； /*判断 buff2 是否有空间，没有则等待*/ P(B-M1)； /*是否可操作 buff1 */ P(B-M2)； /*是否可操作 buff2 */ MOVE； V(B-M1)； /*设置 buff1可操作标志*/ V(B-M2)； /*设置 buff2可操作标志*/ V(empty1)； /*设置 buff1有空间标志*/ V(full2)； /*设置 buff2 有数据标志*/ until false } { 第 3 章 进程的同步与通信 21 repeat P(empty2)； /*判断 buff2 是否有空间，没有则等待 */ P(B-M2)； /*是否可操作 buff2*/ GET； V(B-M2)； /*设置 buff2可操作标志 */ V(full2)； /*设置 buff2 有数据的标志 */ until false } 例 3.2.3.2.3.2.3.2.11111111 一售票厅只能容纳 300人，当少于 300人时，可以进入；否则，需在外等候。 若将每一个购票者作为一个进程，请用 P、V 操作编程，并写出信号量的初值。 解 〈购票者进程〉 { ┋ P(S)； 进入售票厅； 购票； 退出售票厅； V(S)； } 信号量的初值 S=300 例 3333....2222....12121212 设 A、B 为两个并发进程，它们共享一个临界资源，其执行临界区的算法 框图如下图所示。试判断该算法是否有错？请说明理由。如果有错，请改正。S1、S1 的初 值为 0，CSA、CSB为临界区。 A 进程 B进程 图 4.3 进程操作图 分析 咋一看， 好像是 A 进程开始未执行 P操作，便直接进入临界区，以为问题出在 这里。从图中可分析出 A、B两进程的执行思路：A 进程对临界资源操作结束后，将其释 放给 B 进程，而 B 进程对临界资源操作结束后，将释放给进程 A。系统初启时，S1、S2 CSA V(S1) P(S2) P(S1) CSB V(S2) 第 3 章 进程的同步与通信 22 初值为 0，则 B 执行 P(S1)被阻塞，而 A 进程可直接访问临界资源。故 A、B 两个并发进 程不可能同时操作临界资源，该算法是可以保证互斥的。按本题的要求，两个进程对临界 资源的操作是没有先后顺序的，但是，在上面的实现中，只有 A 进程先操作完临界资源后， B 进程才能操作。 解 该算法有错。 若 A 进程永不要求访问临界资源，则不会执行 V(S1)，意味着 B进程的申请永远得不 到操作临界资源的机会；同理，若 B 进程不要求访问临界资源，则不会执行 V(S2)，意味 着 A 进程下次也得不到操作临界资源的机会。所以问题在于本应进行互斥控制而使用的却 是同步控制。实现改正： 设置信号 mutex mutex:=1; cobegin AAAA进程： Begin repeat P(mutex); CSA; V(mutex); until false End BBBB进程： Begin repeat P(mutex); CSB; V(mutex); until false End Coend 例 3.2.3.2.3.2.3.2.11113333 何谓纯代码，它有什么用途？ 解 纯代码是可以为多个进程共享的程序段，代码不因程序的执行而改变，又称为可 重入码。并不是所有的程序段都能被多个进程共享，如果多个进程共享不可重入的代码， 就可能会出现错误。纯代码的主要用途就是让多个进程共享它。 例 3.2.3.2.3.2.3.2.11114444 某高校计算机系开设网络课并安排上机实习，假设机房共有 2m 台机器，有 2n 名学生选该课，规定： 第 3 章 进程的同步与通信 23 (1)每两个学生组成一组，各占一台机器，协同完成上机实习； (2)只有凑够两个学生，并且此时机房有空闲机器，门卫才允许该组学生进入机房； (3)上机实习由一名教师检查，检查完毕，一组学生才可以离开机房。 试用 P、V 操作模拟上机实习过程。 解 (1) 确定并发和顺序操作 在这个问题中，学生(student)、检查教师(teacher)和门卫(gategard)是并行操作的，因此, 有多个学生(student)进程、一个检查教师(teacher)进程和一个门卫(gategard)进程。 (2) 确定互斥和同步的规则 gateguard：只有凑够两个学生，并且此时机房有空闲机器时，门卫才分配计算机给 学生，允许该组学生进入机房； student：只有门卫分配完计算机后，学生才能进入机房上机操作。只有老师检查完 毕才能离开。 Teacher：只有老师检查完学生的实习，才准许学生离开。 (3) 每个进程的操作流程 >>> 设立有学生到达标志，通知 gateguard 进程； 学生是否可进入？ 上机实习； 设立实习完成标志，通知教师； 教师是否可检查，等待教师检查完毕； 学生释放一台计算机资源； >>> repeat 是否有学生１实习完成？ 是否有学生２实习完成？ （是否有一组学生实习完成） 检查学生实习结果； 检查完成，允许学生 1 离开； 检查完成，允许学生 2 离开； until false >>> repeat 等待学生 1 到达; 等待学生 2 到达; 是否有可用的计算机 1; 是否有可用的计算机 2; 分配计算机； 第 3 章 进程的同步与通信 24 设置学生 1 可进入标志; 设置学生 2 可进入标志; until false (4) 确定信号量的个数和含义 student：是否有学生; computer：是否有可用的计算机； enter：学生是否可以进入机房； finish：是否有学生完成实习； test： 老师是否检查完一组学生。 (5) 确定信号量的初值 在初始状态，各信号量的初值如下： student=0 学生没有到达; compute=2m 有 2m个可用的计算机； enter=0 不允许学生进入机房，因为需要得到门卫允许； finish=0 没有学生实习完成； test=0 老师没有检查学生。 (6) 确定 P、V 操作的位置 >>> 设立有学生到达标志，通知 gateguard 进程 =>V(student) 学生是否可进入？=> P(enter) 上机实习； 设立实习完成标志，通知教师 => V(finish) 教师是否可检查，等待教师检查完毕 => P(test(i)) 学生释放一台计算机资源 => V(computer) >>> repeat 是否有学生１实习完成？=>P(student) 是否有学生２实习完成？=>P(student) （是否有一组学生实习完成） 检查学生实习结果； 检查完成，允许学生 1离开 => V(test(i)) 检查完成，允许学生 2离开 => V(test(i)) until false >>> repeat 等待学生 1 到达 =>P(student) 等待学生 2 到达 =>P(student) 是否有可用的计算机 1 => P(computer) 第 3 章 进程的同步与通信 25 是否有可用的计算机 2 => P(computer) 分配计算机； 设置学生 1 可进入标志 => V(enter) 设置学生 2 可进入标志 => V(enter) until false (7) P、V 操作实现 程序如下： student:=0; computer:=2m; enter:=0; finish:=0; test(i):=0; parbegin Student i:::: Begin V(student); /*表示有学生到达，通知 gateguard 进程 */ P(enter); /*学生是否可进入*/ 上机实习； V(finish); /*实习结束，通知教师,有需要检查的学生*/ P(test(i)); /*等待教师检查完毕*/ V(computer); /*释放计算机资源} End; .... Teacher::::Begin repeat P(finish); /*是否有需要检查的学生，等待实习完成*/ P(finish); /*是否有需要检查的学生，等待实习完成*/ 选出可检查的第 i组学生； 检查第 i组学生实习结果； V(test(i)); /*检查完成*/ V(test(i)); /*检查完成*/ until false End; Gategard::::Begin repeat. P(student); /*等待学生到达*/ P(student); /*等待另一学生到达*/ 第 3 章 进程的同步与通信 26 P(computer); /*是否有可用的计算机*/ P(computer); /*是否有可用的计算机*/ 分配计算机； V(enter); /*设置学生 1 可进入标志*/ V(enter); /*设置学生 2 可进入标志*/ untile false End; Parend; 在 student进程中，如果在一个学生到达后，立即向 gateguard 进程发信号，在 gateguard 进程为其分配计算机后，该学生才被允许进入机房，因此避免了让该学生争夺计算机的使 用权和死锁的发生。 例 3.2.3.2.3.2.3.2.11115555 针对如下所示的优先图解答下列问题： 图 4.4 进程优先图 （1）仅使用并发语句能否将其转换成正确的程序？如果能则写出相应程序，如果不 能则说明为什么？ （2）若可以使用信号量机构，该优先图将如何转换成正确的程序？ 解 (1) 如果仅用并发语句不能将其转换成程序。 因为 S5 有２个前趋，S4 有２个前趋，S6 有２个前趋。 (2) 使用信号量机构，就可以将其转换成程序。 Var a, b, c, d, e, f, g, h: Semaphores; {初值均为 0