经典进程同步问题小结.ppt

1 生产者－消费者问题 2 哲学家就餐问题 3 读者-写者问题 4 睡眠理发师问题 1 经典问题：生产者－消费者问题 问题描述 一个有限空间的共享缓冲区，负责存放货物 生产者向缓冲区中放物品，缓冲区满则不能放 消费者从缓冲区中拿物品，缓冲区空则不能拿 生产者－消费者问题分析 互斥关系分析 任何时刻，只能有一个进程在缓冲区中操作 引入互斥信号量（二元信号量） 信号量为0，表明已有进程进入临界区； 同步关系分析 对于“生产者”而言，缓冲区满则应等待 引入同步信号量“empty”，为0表示缓冲区满 对于“消费者”而言，缓冲区空则应等待 引入同步信号量“full”，为0表示缓冲区空 2 经典问题：哲学家就餐问题 问题描述 五个哲学家坐在圆桌前，每人一份炒饭 每个哲学家两侧各有一支筷子 哲学家处于吃饭和思考两种状态 哲学家就餐问题的信号量解法 互斥关系分析 筷子：同一时刻只能有一个哲学家拿起筷子 同步关系分析 就餐：只有获得两个筷子后才能进餐 特殊情况考虑 死锁：如果每个哲学家都拿起一只筷子，都饿死 并行程度：五只筷子允许两人同时进餐 3 经典问题：读者-写者问题 问题描述 写者向数据区放数据，读者从数据区获取数据 多个读者可同时读取数据 多个写者不能同时写数据 读者和写者的控制策略变化多端 利用记录型信号量解决读者-写者问题 利用信号量集机制解决读者-写者问题  4 经典问题：睡眠理发师问题 问题描述 一把理发椅，N把等待座位 理发师为理发椅上的顾客理发，没有顾客就在理发椅上睡觉 有一个顾客时需要叫醒理发师 多个顾客时需要在等待座位上等候 睡眠理发师问题的信号量解法 互斥关系分析 理发椅上只能有一位顾客 等待座位是有限缓冲区 同步关系分析 只要存在顾客，理发师就不能睡觉 信号量设计 互斥信号量：实现对“等待顾客数”的互斥 同步信号量1：理发师“睡眠”和“工作”的同步 同步信号量2：等待顾客与等待座位的同步 * * 进程通信 进程通信 1. 利用记录型信号量解决生产者—消费者问题 假定在生产者和消费者之间的公用缓冲池中，具有n个缓冲区，这时可利用互斥信号量mutex实现诸进程对缓冲池的互斥使用；利用信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。对生产者—消费者问题可描述如下： Var mutex, empty, full:semaphore∶=1,n,0; buffer:array［0, …, n-1］ of item; in, out: integer∶=0, 0; begin parbegin proceducer:begin repeat … producer an item nextp; … wait(empty); wait(mutex); buffer(in)∶=nextp; in∶=(in+1) mod n; signal(mutex); signal(full); until false; end consumer:begin repeat wait(full); wait(mutex); nextc∶ =buffer(out); out∶ =(out+1) mod n; signal(mutex); signal(empty); consumer the item in nextc; until false; end parend end 2. 利用AND信号量解决生产者—消费者问题 var mutex, empty, full:semaphore∶ =1, n, 0; buffer:array［0, …, n-1］ of item; in out:integer∶ =0, 0; begin parbegin