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

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