用信号量机制与PV操作解决进程同步互斥问题的方法.doc

用信号量机制与 pv操作解决进程同步互斥问题的方法宋新丽, 何永强(河南纺织高等专科学校, 河南 郑州 450007)摘要: 根据信号量机制与 pv操作能协调进程并发执行的特点, 提出了分析此类问题的方法, 并给出快速准确解决此类问题的规律。关 键 词: 信号量机制; 进程; 同步; 互斥; pv 操作中图分类号: t p 301文献标识码: b文章编号: 100828385 (2005) 0320009204采用信号量机制与 pv 操作 来 协 调 进 程 的 同步, 一直是操作系统教学中的一个难点问题, 而且 由它引出的一系列问题, 如: 生产者与消费者、读者 与写者、哲学家进餐、理发师等问题都是很典型的进程同步与互斥问题。 这类题型变化多、实例多, 又与 实际生活中的问题有着紧密联系, 笔者就自己在教学工作中积累的经验, 谈一下用信号量机制与 pv操作解决此类问题的方法。程可以申请到相应资源, 继续执行; 若 s 0 时, 其值表示系统中对应可用资源的数目; 当 s= 0 时, 表示系统中对应资源已经都被占用, 并且 没有因该类资源而被阻塞的进程; 当s 0, 则执行v 操作的进程继续执行; 若 s 0, 则从阻塞队列唤醒一个进程, 并将其插入就绪队列, 然后执行 v作的进程继续执行, 如图 2 所示。操通常, p 操作意味着请求一个资源, v 操作意味收稿日期: 2005- 06- 14作者简介: 宋新丽 ( 1979- ) , 女, 河南漯河人, 助教, 主要研究计算机科学理论。着释放一个资源。在一定条件下, p 操作代表挂起进2. 2互斥问题的分析方法进程互斥指对于某个系统资源, 如果一个进程 正在使用, 则另外一个想使用该资源的进程就必须 等待, 而不能使用3 。互斥进程之间体现了对资源的 竞争关系, 他们竞争的资源被称为临界资源, 而进程中访问临界资源的那段代码叫做临界区。 为了实现对临界资源的互斥访问, 应保证诸进程互斥地进入各自的临界区。用 p、v 操作实现进程程操作, 而 v操作代表唤醒被挂起进程的操作。的互斥, 每个进程中用户实现互斥的 p、v操作必须成对出现, 先做 p 操作, 进入临界区, 再做 v 操作,退出临界区。 p、v 操作应分别紧靠临界区的头尾 部, 临界区代码应尽可能短, 且不能有死循环。 互斥信号量的个数有临界资源的类型决定, 有几类临界 资源设几个信号量, 初值一般设为 1, 表示该临界资 源未占用, 且其可用数目为 1。解决进程互斥问题的主要步骤与解决进程同步 问题的步骤相同。图 2v 操作流程2用 p、v 操作原语实现进程的同步3 应用实例分析3. 1同步问题实例分析在某并发系统中, 有一个发送进程 a 、一个接收与互斥2. 1同步问题的分析方法进程同步指两个或多个进程为了合作完成同一 任务, 在执行速度或某个确定的时序点上必须相互协调, 即一个进程依赖于另一个进程发送的消息, 进 程之间体现了一种相互合作的关系2 。当用 p、v 操作实现进程的同步问题时, 合作进 程之间通过信号量进行互发消息, 执行 p 操作测试消息是否到达, 即是否得到合作进程的通知可以执行 该 进 程; 而 执 行 v 操 作 是 向 其 合 作 进 程 发 送 消 息, 通知它进行下一步操作。 通常, 需要收发几条消息就设置几个信号量, 这些同步信号量的初值一般为 0, 有时也可设为一个整数, 这往往与合作进程所 共享资源的可用数目有关。在同步关系的进程中, 对同一个信号量的 p、v 操作不出现在同一个进程中,而是出现在各个合作进程中确定的时序点, 即当一 个生产者进程在完成了前面的生产任务后, 应立即给消费者进程发送一条消息 (执行 v 操作) , 而消费 者进程在消费前要执行对同一信号量的 p 操作。一般来讲, 解决进程同步问题的主要步骤为:(1) 分析清楚题目涉及的进程间的制约关系;(2) 设置信号量 (包括信号量的个数和初值及其进程b、一个环形缓冲区bu f f er、信号量 s1 和 s2。发送进程不断地产生消息并写入缓冲区 bu f f er ,接收进程不断地从缓冲区bu f f er 读取消息。假设 发送进程和接收进程可以并发地执行, 当缓冲区的容量为 n 时, 请使用 p、v操作保证系统的正常工作。发送进程 a 和接收进程 b 的工作流程如图 3 所示。请在图 3 中的空 (1) (4) 处填入正确的内容4 。图 3 发送进程 a 和接收进程 b 工作流程图插入 p (sa )、v (sa )、p (sb )、v (sb ) 5 。从流程图可以看到, 在系统中有多个发送进程 和多个接收进程时, 若对缓冲区读数据的操作先于修改指针 j 操作, 就意味着, 如果有多个进程同时进程,进 程 b为 接 收 进 程, 两 进 程 共 享 缓 冲 区bu f f er。 信息通过该缓冲区进行传送, 其容量为n 。 这意味着进程 a 最多能连续发送 n 次, 当缓冲 区满时则停止发送; 而接受进程 b 也最多能连续接 受 n 次, 当缓冲区为空时, b 就不能接收信息。进程a 与进程 b 的同步关系主要表现在: 进程 a 每发送 一个信息就要通知进程 b 接收, 同时, 进程 b 每接行读操作, 就会出现对同一缓冲区的重复读操作。如: b 1 , b 2 , 假设 n = 10, s2 = 5, j= 2, 则两个读进程可能读到的都是bu f f er 2中的信息。因为, 当b 1受一个信息都要通知进程 a可以再发送一条信息。执行时, 首先执行 p (s2 ) 操作, s2 = s2 -1= 4 0, 则因此, 设置两个信号量 s1 , s2 来协调进程 ab 之间的同步操作。与进程可 读出 bu f f er 2中的信息, 执行到 i 时进程 b 1的时间片用完, 接着执行进程 b 2; 同样, 它也先执行p ( s2 ) 操 作, s2 = s2 - 1 = 3 0, 则 b 2 也 可 读 出在缓冲区为空时, 进程 b 就无法执行, 所以应先对其进行 p (s2 ) 操作 ( 图 3 中的空 3 处) , 并且设s2 初值为 0, 则它将进入阻塞队列。由此我们可以看 到, s1 代表缓冲区的空位数, 其初始值为 n , s2 代表缓冲区已写入的信息数。这样, 写进程开始运行时先执 行 p (s1 ) 操 作。 因 此, 图 3 中 的 空 ( 1) 处 应 填 p ( s1 ) , 当进程 a 写完一条信息时, 负责通知进程 b可以读操作了。所以空 (2) 处应填v (s2 )。相应地, 进程 b 执行完读操作后也要通知进程 a , 所以空 ( 4)处应填 v (s1 )。3. 2带有互斥问题的实例分析若系统中有多个发送进程和接收进程 ( 进程间 的工作流程如图 4 所示) , 其中空 (1) (4) 的内容与 图 3 相同。 发送进程产生消息并顺序地写入环形缓冲区 bu f f er , 接受者进程顺序地从 bu f f er 中 取消息, 且每条消息只能读取一次。为了保证进程间的正常通讯, 增加了信号量 sa 和 sb。bu f f er 2中的信息, 这与题目要求不一 致。 同时, 对于写进程也存在着多个进程同时向一个缓冲区空间重复写数据的可能性, 这就影响了系统的性 能。为保证进程间的正常通信, 我们需要设置一定的信号量, 使读进程和读进程之间互斥操作, 写进程与写进程之间互斥操作。sa 代表写进程之间申请缓冲 区时的互斥信号量, sb 代表读进程之间申请缓冲区 时的互斥信号量。互斥信号量的 p、v 操作应出现在 同一进程中, 且 sa , sb 的初值都为 1。在某个进程中如果同时存在互斥与同步的 p 操作, 则必须先执行 同 步 信 号 量 的 p 操 作, 再 执 行 互 斥 信 号 量 的 p 操操作的顺序没有严格要求5作, 但 v, 故在本题中先执行 p (s1 ) , 后执行 p (sa )。由此, c 处应填 p (sa ) ,f 处应填 v (sa ) , 以保证写操作完成后再把缓冲区 让给其他进程。同理, p (sb ) 应插入 h 处, v (sb ) 应插入 k 处。结语分析同步互斥问题的关键, 一是深刻理解信号 量级 p、v 操作的含义; 二是要牢牢把握以下原则:( 1) 根据题意确定进程个数及进程间的相互关系 (同步或互斥关系)。( 2) 根据进程间的关系确定信号量的类型与个 数, 一般地, 同步信号量个数等于同步关系进程的类型数, 互斥信号量代表临界资源的类型数目, 其初值 一般为 1。( 3) 同步信号量 p、v 操作出现在不同进程中,体现进程间的协作关系; 互斥信号量 p、v 操作出现 在同一进程中, 体现进程间对资源的竞争关系, 且在同一问题中 p 操作和 v 操作必须成对出现。(4) 在同一进程中, 若同时存在着互斥信号量和 同步信号量的 p 操作, 应先执行同步信号量的 p 操4图 4 多个发送和接收进程工作流程图请说明信号量 sa 和 sb 的物理意义, 并在图4 中的空 (5) 和空 (6) 处填入正确的内容。请从图 4 的 (a) ( l) 中选择四个位置正确地作, 再执行互斥信号量的 p 操作, 但对 v操作的顺序没有严格要求6 。5全国计算机技术与软件专业技术资格 ( 水平) 考试办公室. 2004 年下半年考试程序员考试试题 z . 2004.连卫民等. 操作系统原理教程 m . 北京: 中国水 利水电出版社, 2004.参考文献12 3范辉等. 操作系统原理与实训教程 m .6北京: 高等教育出版社, 2004.4全国计算机技术与软件专业技术资格 ( 水平) 考 试办公室. 全国计算机技术与软件专业技术资格 (水平) z . 2004. 责任编辑: 李连举 a ch ieve m utua l exc lus ionin proce ss syn chron iza t ionw ith s igna l m echan ism an d pv o pera t ionso ng x in 2li, he yo ng 2q ia ng(h en a n t ex t ile c ol leg e, z h en g z h ou 450007, c h in a )a bstra c t: b a sed o n th e fac t th a t th e sign a l m ech an ism an d pv op e ra t io n can coo rd in a te th e p ro ce sssyn ch ro n ize t io n , th is