信号量在生产者-消费者及其变形问题中的应用.pdfVIP

172 福 建 电 脑 信号量在生产者一消费者及其变形问题中的应用 李 洁．张瑜慧 (宿迁学院 计算机科学系 江苏 宿迁 223800) 【摘 要】：生产者一消费者问题是操作系统中进程同步互斥的经典lq题。在其之上的变形问题在实际 应用中非常广泛，用信号量机制描述此类问题 ，并给 出相应的解决方法。 【关键词】：同步；互斥；信号量；PV操作；生产者一消费者 1．信号量机制和 PV操作含义 个物理资源而互相制约。例如系统中只有一台打印机． 1965年 ．荷兰学者 Dijkstra提 出了利用信号量机 有两个进程都要使用 ，则只能是一个进程用完打印机 制解决进程 同步问题 ．信号量正式成为有效 的进程 同 之后 ，另一个进程才能使川 。否则 ．若两个进程 同时刚 步工具．现在信号量机制被广泛的用于单处理机和多 一 台打印机 ．则结果交织在一起 ．无法保证结果的正确 处理机系统 以及计算机网络中 信号量是一个确定 的 性 。这种互斥关系不同于同步关系 ．它们的运行不具有 二元组(S，T)，其 中T是个初始状态为空的等待 队列 ，S 时间次序的特征 ．谁先 向系统提 出申请 ．谁就先 占有资 是一个具有非负初值的整型变量 当S10时．表示系 源执行 。 统 中某类可用资源的数 目，当S0时．其绝对值表示等 3．信号量机制在进程 同步互斥 中的应用 待使用某类资源的进程的个数 信号量 S的值只能由 3．1解决步骤 定义在信号量上的P原语和 v原语来改变 用信号量机制描述进程同步互斥基本步骤为 ： P原语操作的动作是 ： (1)分析进程问的同步互斥关系 ；根据实际问题分 (1)S减 l； 析包含的进程间的关系 ，是 同步还是互斥 ．还是兼有 ． (2)若 S减 l后仍大于或等于零 ．则进程继续执行 ； 分别列出进程的制约关系 (3)若S减 1后小于零 ，则该进程被阻塞后进入与 (2)设相应同步互斥信号量 ．并说明含义和设定初 该信号相对应的队列 中．然后转进程调度。 值 ：根据分析出的进程 同步互斥关系 ，分别设定相应的 v原语操作的动作是 ： 信号量 ．同步信号量和互斥信号量分别是哪些．各 自的 (1)S加 1； 含义是什么．初值是多少 (2)若相加结果大于零 ，则进程继续执行 ： (3)用 P、V操作来描述进程的活动 根据进程相应 (3)若相加结果小于或等于零 。则从该信号的等待 程序算法或流程控制 ．用 P、V操作和设定的信号量机 队列中唤醒一等待进程 ．然后再返回原进程继续执行 制来描述各进程的活动 或转进程调度 3．2信号量机制描述生产者一消费者问题 通常，P操作意味着请求一个资源 ．V操作意味着 生产者与消费者问题是经典的同步问题 ．其 中包 释放一个资源。在一定条件下，P操作代表挂起进程操 括了同步与互斥 ．很多进程之问的联系问题都是在此 作 ．而 v操作代表唤醒被挂起进程的操作 Pv操作对 问题上进行演变和扩展 ．因此是操作系统课程中的核 于每一个进程来说 ．都只能进行一次 ．而且必须成对使 心算法 生产者与消费者问题捕述如下 ：生产者进程 州 ．在 PV原语执行期问不允许有中断的发生 P1、P2、…、Pm，消费者进程 C1、C2、…、Cn共享一个长 2．进程同步互斥含义 度为 k的有界缓冲区(k0)．生产者 向其中存放产品， 同步指两个或多个进程为 了合作完成 同一任务 ． 消费者从其中取得产品．要求 ：生产者不应覆盖一个满 在执行速度或某个确定的时序点上必须相互协调 ．即 的缓冲区：消费者不应使用一个空的缓冲