第三章进程管理5报告.ppt

复习 进程间的制约关系有哪两种？ 什么是进程互斥？什么是进程同步？ 什么是私用信号量？什么是公用信号量？各用于何处？ 解决进程互斥和同步问题的步骤是什么？ 第三章 进程管理 习题课 生产者----消费者问题 把并发进程同步和互斥问题一般化，得到一个抽象的模型，即生产者——消费者问题 生产者：释放某一类资源的进程 消费者：使用某一类资源的进程 问题描述：若干个进程通过有限的共享缓冲区交换数据，其中生产者进程不断写入，消费者进程不断读出，共享缓冲区共有n个，任一时刻只能有一个进程对整个共享缓冲区进行操作 生产者----消费者问题 分析： 1）同步问题：生产者想写入时，缓冲区中至少有一个时空的，消费者想读出时，缓冲区中至少有一个是满的 互斥问题：任一时刻只能有一个进程可以对缓冲区操作 用P、V原语实现生产者----消费者问题 解：1）设私用信号量avail表示缓冲区中的空单元数，full表示缓冲区中的满单元数；公用信号量mutex表示整个缓冲区是否在使用 2）设初始值avail=n，full=0，mutex=1 3）描述 生产者----消费者问题 注意:P操作顺序很重要：先检查是否有资源可用，再检查是否互斥；V操作顺序无所谓 用P、V原语实现哲学家问题 例1：5个哲学家在圆桌前进餐，两个人之间各放一根筷子。哲学家或者思考或者分别取左右手边的筷子进餐。请用P、V原语描述每个哲学家的进餐过程。 用P、V原语实现哲学家问题 解：1）设公用信号量s[i]表示是否能取到第i个筷子（i=0,1,2,3,4 ） 2）设初始值，s[i]=1 （i=0,1,2,3,4 ） 3）描述第i个哲学家Pi： 用P、V原语实现哲学家问题(完整) 解：1）设公用信号量mutex表示哲学家是否能同时取到2个筷子，s[i]表示是否能取到第I个筷子（i=0,1,2,3,4 ） 2）设初始值mutex=1，s[i]=1 （i=0,1,2,3,4 ） 3）描述第i个哲学家Pi： 用P、V原语实现同步 例2 设公共汽车上，司机和售票员的活动如下。在汽车不断到站停车、行驶过程中，这两个活动有什么同步关系？用P、V原语实现他们的同步。 用P、V原语实现同步 1）设close为进程P1的私有信号量，表示售票员是否关门，stop为进程P2的私有信号量，表示车辆是否停止到站。 2）设初始值close=1，stop=0，表示车正在运行。 3）描述： 例3 设有一个作业由四个进程组成，这四个进程在运行时必须按图所示的顺序，用P、V原语操作表达四个进程的同步关系。 解：1）设同步（私有）信号量 s12，s13，s24，s34分别用于T1与T2，T1与T3，T2与T4，T3与T4之间进行同步 2）设初始值s12=0，s13=0，s24=0，s34=0 3）PV原语描述： 用P、V原语实现进程同步和互斥 例4：某寺庙，有小、老和尚若干。寺庙有一水缸，可容10桶水，由小和尚提水入缸、取水出缸供老和尚饮用，每次入水、取水仅为1桶，且不可同时进行。水取自同一井中，口窄，每次只能容一个桶取水。水桶总数为3个。用P、V原语给出取水入水的算法描述 用P、V原语实现进程同步和互斥 解：1）设公用信号量mutex1，mutex2分别控制井和缸的互斥，count表示空闲的水桶数；私用信号量empty表示缸中还可以入几桶水，full表示缸中已入几桶水 2）设初始值mutex1=1，mutex2=1，empty=10，full=0，count=3 3）描述 用P、V原语实现进程同步和互斥 入水： L1:P(empty) P(count) P(mutex1) 从井中取水 V(mutex1) P(mutex2) 送水入缸 V(mutex2) V(count) V(full) Goto L1 取水： L2:P(full) P(count) P(mutex2) 从缸中取水 V(mutex2) V(count) V(empty) Goto L2 用P、V原语实现进程同步和互斥 例5：某车站售票厅有20个窗口，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在厅外等待。若把购票者看做一个进程，请用P，V操作管理这些进程，要求如下： (1)在主函数中给出信号量的定义和初值。 (2)给出一个购票者进程的算法 (3)给出当购票者最多不超过n(设n20)个时，信号量可能的变化范围。 用P、V原语实现