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

 用信号量机制与 PV 操作 解决进程同步互斥问题的方法 宋新丽, 何永强 (河南纺织高等专科学校, 河南 郑州 450007) 摘 要: 根据信号量机制与 PV 操作能协调进程并发执行的特点, 提出了分析此类问题的方法, 并给出快 速准确解决此类问题的规律。 关 键 词: 信号量机制; 进程; 同步; 互斥; PV 操作 中图分类号: T P 301 文献标识码: B 文章编号: 100828385 (2005) 0320009204 采用信号量机制与 PV 操作 来 协 调 进 程 的 同 步, 一直是《操作系统》教学中的一个难点问题, 而且 由它引出的一系列问题, 如: 生产者与消费者、读者 与写者、哲学家进餐、理发师等问题都是很典型的进 程同步与互斥问题。 这类题型变化多、实例多, 又与 实际生活中的问题有着紧密联系, 笔者就自己在教 学工作中积累的经验, 谈一下用信号量机制与 PV 操作解决此类问题的方法。 程可以申请到相应资源, 继续执行; 若 S 0, 表示已 没有资源可用, 请求者必须等待其他进程释放该类 资源之后才能继续运行, 则置该进程为阻塞状态, 并 将其插入阻塞队列, 如图 1 所示。 信号量机制与 PV 操作 1 1. 1 信号量机制 信 号量是一个确定的二元组 (S, Q ) , 其中 S 是 一个具有非负初值的整形变量, 且 S 的值只能由定 义在信号量上的 P 操作原语和 V 操作原语来改变, 而 Q 是个初始状态为空的队列, 即信号量表示某类 资源实体与进程队列有关的整形变量1 。 通常, S 用来表示系统中资源的使用情况。 当 S 0 时, 其值表示系统中对应可用资源的数目; 当 S= 0 时, 表示系统中对应资源已经都被占用, 并且 没有因该类资源而被阻塞的进程; 当S 0 时, 其绝 对值表示因该类资源而被阻塞的进程数目。 1. 2 P、V 操作 P (S) : 执行一次 P 操作意味着请求分配一个单 位资源, 因此 S 的值减 1, S∶= S- 1。若 S≥0, 其值 代表了可利用资源的数目, 则表示执行 P 操作的进 图 1 p 操作流程 V (S ) : 执行一个 V 操作意味着释放一个单位 资源, 因此 S 的值加 1, S∶= S+ 1。若 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。 解决进程互斥问题的主要步骤与解决进程同步 问题的步骤相同。 图 2 v 操作流程 2 用 P、V 操作原语实现进程的同步 3 应用实例分析 3. 1 同步问题实例分析 在某并发系统中, 有一个发送进程 A 、一个接收 与互斥 2. 1 同步问题的分析方法 进程同步指两个或多个进程为了合作完成同一 任务, 在执行速度或某个确定的时序点上必须相互 协调, 即一个进程依赖于另一个进程发送的消息, 进 程之间体现了一种相互合作的关系2 。 当用 P、V 操作实现进程的同步问题时, 合作进 程之间通过信号量进行互发消息, 执行 P 操作测试 消息是否到达, 即是否得到合作进程的通知可以执 行 该 进 程; 而 执 行 V 操 作 是 向 其 合 作 进 程 发 送 消 息, 通知它进行下一步操作。 通常, 需要收发几条消 息就设置几个信号量, 这些同步信号量的初值一般 为 0, 有时也可设为一个整数, 这往往与合作进程所 共享资源的可用数目有