页数：58页文件大小：363.0 KB来源： 计算机操作系统ppt课件
本课件讲解进程同步，先区分互斥与同步两类制约关系，说明临界区与同步机制四条准则，继而展开整型、记录型与 AND 信号量及管程机制，最后用信号量求解生产者消费者、哲学家进餐、读者写者等经典同步问题。
第二章 进程管理：本页为《计算机操作系统》课件封面，标注课程名称与英文名称 Operating Systems，并列出 WINDOWS、UNIX、LINUX 等常见操作系统类型。
2.3进程同步
进程的同步与互斥
生产者-消费者问题描述：生产者-消费者问题。
生产者-消费者问题的程序描述
生产者-消费者问题producer:repeat…produce an item in nextp;…while counter=n do no-op;buffer[in]:=nextp;in:=(in+1) mod n;counter:=counter+1;until falseconsumer:repeatwhile counter=0 do no-op;nextc:=buffer[out];out:=(out+1) mod n;counter:=counter-1;consumer the item in nextc;until false
counter变量的机器指令分解
生产者-消费者问题counter:=counter+1：register1:=counter；register1:=register1+1；counter:=register1；counter:=counter-1：register2:=counter；register2:=register2-1；counter:=register2
并发执行导致结果不可再现
生产者-消费者问题生产者进程://counter初始值=5 ⑥counter:=register2；;程序的执行已经失去了再现性。解决此问题的关键是应把变量counter作为临界资源处理，令生产者进程和消费者进程互斥地访问变量counter。5register15register2465counter46
临界区的概念
临界区 把在每个进程中访问临界资源的那段代码称为临界区
临界区的进入与退出：临界区。
同步机制应遵循的规则：同步机制应遵循的规则1.空闲让进。2.忙则等待。3.有限等待。4.让权等待。
2.3.2信号量机制
2.3.2信号量机制1整型信号量 定义为一个用于表示资源数目的整型量S
记录型信号量
wait与signal操作原语
申请一个单位资源：procedurewait(S)var S：semaphore；beginS.value:=S.value-1；if S.value<0 thenblock(S.L)；end释放一个单位资源：procedure signal(S)var S: semaphore；BeginS.value:=S.value+1；if S.value<=0 thenwakeup(S.L)；end
信号量的物理意义
多临界资源互斥引发的死锁：上述的进程互斥问题，是针对各进程之间只共享一个临界资源而言的。process A:process B:wait(Dmutex)；wait(Emutex)；wait(Emutex)；wait(Dmutex)；若进程A和B按下述次序交替执行wait操作：process A: wait(Dmutex)；于是Dmutex=0process B: wait(Emutex)；于是Emutex=0process A: wait(Emutex)；于是Emutex=-1 A阻塞process B: wait(Dmutex)；于是Dmutex=-1 B阻塞。
3AND同步机制的基本思想
3AND同步机制的基本思想 采取原子操作方式 要么把它所请求的资源全部分配到进程 要么一个也不分配 可避免上述死锁情况的发生 在wait操作中，增加了一个“AND”条件 AND同步，或称为同时wait操作
Swait操作的定义
Swait(S1，S2，…，Sn)if S1>=1 and…and Sn>=1 thenfori:=1 to n doSi:=Si-1；endforelse当发现第一个Si<1就把该进程放入等待队列，并将其指令计数器置于Swait操作的开始位置endif
Ssignal操作的定义
Ssignal(S1，S2，…，Sn)fori:=1tondoSi:=Si+1；RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueue.endfor
信号量实现进程互斥
2.3.3信号量的应用利用信号量实现进程互斥Varmutex:semaphore=1;beginparbeginprocess1:beginrepeatwait(mutex);critical section；signal(mutex);remainder section;until false;endprocess 2: beginrepeatwait(mutex);critical section;signal(mutex);remainder section；until false;Endparendmutex10NULL-1
2.3.4管程机制
管程的定义
管程的示意图：管程的示意图conditionc1wait(c1)…conditioncnwait(cn)局部数据条件变量过程/函数1过程/函数k出口初始化代码入口管程等待调用过程的进程队列管程等待区…。
管程的条件变量
x.wait操作
x.signal操作
管程的主要特性
管程与进程的区别
管程与进程的区别（续）
2.4经典进程的同步问题
信号量解决生产者消费者问题
单生产者单消费者共享单缓冲：①一个生产者、一个消费者共享一个缓冲区的解int B;semaphore empty;
单缓冲同步的伪代码解
一个生产者、一个消费者共享一个缓冲区cobeginprocess producer(){ process consumer(){while(true){ while(true) {produce( );P(empty);append( ) to B;V(full);} }} }coendEmptyfull空1不满00满1无缓冲区-1空-1P(full);V(empty);consume( );take( ) from B
多生产者多消费者环形缓冲：②一组生产者，一组消费者，公用n个环形缓冲区。
记录型信号量解生产者-消费者
利用记录型信号量解决生产者—消费者问题Varbuffer:array［0,…, n-1］of item;in，out:integer:=0,0;
生产者-消费者问题的解
生产者/消费者、共享多个缓冲区的解parbeginProceducer_i:beginrepeat…produce an itemnextp;…wait(empty);wait(mutex);buffer(in) :=nextp;in:=(in+1) mod n;signal(mutex);signal(full);until false;endparendConsumer_j:beginrepeatwait(full);wait(mutex);nextc:=buffer(out);out:=(out+1) mod n;signal(mutex);signal(empty)；consumer the item in nextc;until false;endparendend
并发解法中的永远等待问题
永远等待cobeginprocessproducer_i(){while(true){produce();P(mutex);P(empty);append to B[in];in=(in+1)%k;V(mutex);V(full);}}coendprocessconsumer_j(){while(true){P(full);P(mutex);take( ) from B[out];out=(out+1)%k;V(mutex);V(empty);consume( );}}emptyfull0kMutex=1Mutex=0-1
信号量及P、V操作讨论
哲学家进餐问题：有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘子，每两人之间放一把筷子。每个哲学家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必须获得两只筷子，且每人只能直接从自己左边或右边去取筷子。
哲学家进餐问题的解决思路
记录型信号量解哲学家进餐
用记录型信号量解决哲学家进餐问题
哲学家进餐解法的分析
哲学家进餐解法的问题
避免哲学家进餐死锁的办法
AND信号量解哲学家进餐
利用AND信号量机制解决哲学家进餐问题Var chopsiick array of semaphore:=(1,1,1,1,1)；processirepeatthink；Swait(chopstick[(i+1)mod 5]，chopstick[i])；eat；Ssignal(chopstick[(i+1)mod 5]，chopstick[i])；until false
读者-写者问题
读者-写者问题的解决思路
读者-写者问题的Readcount
读者-写者问题解法（一）
parbeginReader: beginrepeatwait(rmutex)；if readcount=0 thenwait(wmutex)；Readcount:=Readcount+1；signal(rmutex)；perform read operation；wait(rmutex)；readcount:=readcount-1；if readcount=0 thensignal(wmutex)；//最后一个读者离开时通知写者signal(rmutex)；untilfalse；endparendwriter: beginrepeatwait(wmutex)；perform write operation；signal(wmutex)；until false；End
读者-写者问题解法（二）
parbeginReader: beginrepeatwait(rmutex)；if readcount=0 thenwait(wmutex)；Readcount:=Readcount+1；signal(rmutex)；perform read operation；wait(rmutex)；readcount:=readcount-1；if readcount=0 thensignal(wmutex)；//最后一个读者离开时通知写者signal(rmutex)；untilfalse；endparendwriter: beginrepeatwait(wmutex)；perform write operation；signal(wmutex)；until false；End
读者-写者问题解法（三）
parbeginReader: beginrepeatwait(rmutex)；if readcount=0 thenwait(wmutex)；Readcount:=Readcount+1；signal(rmutex)；perform read operation；wait(rmutex)；readcount:=readcount-1；if readcount=0 thensignal(wmutex)；//最后一个读者离开时通知写者signal(rmutex)；untilfalse；endparendwriter: beginrepeatwait(wmutex)；perform write operation；signal(wmutex)；until false；End
苹果桔子问题：桌上有一只盘子，每次只能放入一只水果；爸爸专向盘子中放苹果，妈妈专向盘子中放桔子；一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子里的苹果。
苹果桔子问题的解决思路
苹果桔子问题的信号量设置
分析 设置3个信号量 empty表示盘子能放的水果数目，初值为1 full_o表示盘子里有无桔子，初值为0
苹果桔子问题：爸爸与儿子进程
process fatherbeginL1:削一个苹果；P(empty);放苹果;V(full_a);goto L1;end;process motherbeginL2:剥一个桔子；P(empty);放桔子；V(full_o);goto L2;end;process daughterbeginL4:P(full_a);取苹果；V(empty);吃苹果；gotoL4;end;process sonbeginL3: P(full_o);取桔子；V(empty);吃桔子；gotoL3;end
苹果桔子问题的扩展
问题 可以放n个水果？ empty表示盘子能放的水果数目，初值为n full_o表示盘子里有无桔子，初值为0 full_a表示盘子里有无苹果，初值为0
苹果桔子问题的改进解法
process fatherbeginL1:削一个苹果；P(empty);P(mutex);放苹果;V(mutex);V(full_a);goto L1;end;process daughterbeginL4:P(full_a);P(mutex);取苹果；V(mutex);V(empty);吃苹果；gotoL4;end
苹果桔子问题：妈妈与女儿进程
process motherBeginL2:剥一个桔子；P(empty);P(mutex);放桔子；V(mutex);V(full_o);goto L2;end;process sonbeginL3:P(full_o);P(mutex);取桔子；V(mutex);V(empty);吃桔子；gotoL3;end
作业：作业。
下载地址：{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}