《操作系统》V习题PPT课件.ppt

操作系统习题讲解操作系统习题讲解一、一、进程概念进程概念二、二、进程同步和互斥进程同步和互斥进进 程程 概概 念（一）念（一）问题：如果系统中有问题：如果系统中有N N个进程，个进程，运行进程最多几个，最少几个？运行进程最多几个，最少几个？就绪进程最多几个，最少几个？就绪进程最多几个，最少几个？等待进程最多几个，最少几个？等待进程最多几个，最少几个？运行运行就绪就绪等待等待解答：解答：运行进程最多运行进程最多1 1个，最少个，最少0 0个；个；就绪进程最多就绪进程最多N-1N-1个，最少个，最少0 0个；个；等待进程最多等待进程最多N N个，最少个，最少0 0个；个；概念：概念：(1)(1)进程、进程的基本状态；进程、进程的基本状态；单单CPUCPU；进程切换瞬间；进程切换瞬间；系统进程、用户进程；系统进程、用户进程；(2)(2)死锁（不是死锁（不是“死机死机”）；）；进进 程程 概概 念（一）念（一）进进 程程 概概 念（二）念（二）问题：问题：进程有无如下状态转换，为什么？进程有无如下状态转换，为什么？（1 1）等待）等待运行运行 （2 2）就绪）就绪等待等待解答：解答：（1 1）不能：等待就绪运行）不能：等待就绪运行 （2 2）不能：就绪运行等待）不能：就绪运行等待问题：问题：一个转换发生，是否另一个转换一一个转换发生，是否另一个转换一定发生？找出所有的可能。定发生？找出所有的可能。解答：解答：就绪就绪运行运行:不一定（系统中仅一个进程）不一定（系统中仅一个进程）转换条件：被调度程序选中转换条件：被调度程序选中 运行运行就绪就绪:一定（讨论就绪队列的长度）一定（讨论就绪队列的长度）转换条件：时间片到时转换条件：时间片到时,或有更高优先级或有更高优先级 的进程出现的进程出现进进 程程 概概 念（三）念（三）解答：解答：运行运行等待等待:不一定（考虑死锁）不一定（考虑死锁）转换条件：等待某事件发生转换条件：等待某事件发生 等待等待就绪就绪:不一定不一定转换条件：等待的事件发生转换条件：等待的事件发生进进 程程 概概 念（三）念（三）进进 程程 概概 念（四）念（四）问题：问题：日常生活中的日常生活中的“进程进程”举例举例解答：解答：两个角度：两个角度：“程序程序-数据数据-运行运行”或或“资源资源-调度调度-运行运行”经典例子：经典例子：“按照菜谱作菜按照菜谱作菜”“”“乐队演乐队演奏奏”或或“向服务员请求服务向服务员请求服务”等等进程同步和互斥（一）进程同步和互斥（一）问题：问题：用用P.VP.V操作解决下图之同步问题操作解决下图之同步问题getgetcopycopyput进程同步和互斥（一）进程同步和互斥（一）一个数据上的操作顺序：一个数据上的操作顺序：get-copy-get-copy-putputGetGet不能向不能向“满满”的的S S中放；中放；CopyCopy不能从不能从“空空”的的S S中取；不能向中取；不能向“满满”的的T T中中放；放；PutPut不能不能“空空”的的T T中取中取（同步）信号量：（同步）信号量：实际上也起到互斥作用实际上也起到互斥作用 S_Empty,T_EmptyS_Empty,T_Empty，初值为初值为11S_Full,T_Full;S_Full,T_Full;初值为初值为00Get:Get:BeginBegin Repeat Repeat P(S_Empty)P(S_Empty)T_get_S();T_get_S();V(S_Full);V(S_Full);Until false;Until false;EndEndCopy:Copy:BeginBegin Repeat Repeat P(S_Full);P(S_Full);P(T_Empty);P(T_Empty);S_copy_T();S_copy_T();V(T_Full);V(T_Full);V(S_Empty);V(S_Empty);Until false;Until false;EndEndPut:Put:Begin Begin Repeat Repeat P(T_Full);P(T_Full);T_put_G();T_put_G();V(T_Empty);V(T_Empty);Until false;Until false;EndEnd进程同步和互斥（二）进程同步和互斥（二）问题：用问题：用P.VP.V操作解决下面问题操作解决下面问题司机进程：司机进程：REPEAT启动车辆启动车辆正常驾驶正常驾驶到站停车到站停车UNTIL 售票员进程：售票员进程：REPEAT关门关门售票售票开门开门UNTIL 信号量：信号量：S_Door,S_Door,初值为初值为00S_Stop;S_Stop;初值为初值为00司机进程：司机进程：BeginBegin Repeat Repeat P(S_Door);P(S_Door);启动；启动；驾驶；驾驶；停车；停车；V(S_Stop);V(S_Stop);Until false;Until false;EndEnd乘务员进程乘务员进程:Begin Begin Repeat Repeat 关门；关门；V(S_Door);V(S_Door);售票；售票；P(S_Stop);P(S_Stop);开门；开门；Until false;Until false;EndEnd同步要求：先关门，后开车；同步要求：先关门，后开车；先停车，后开门先停车，后开门问题：问题：推广读写者问题中的消息缓冲处理。消推广读写者问题中的消息缓冲处理。消息缓冲区为息缓冲区为k k个，有个，有m m个发送进程，个发送进程，n n个接个接收进程，每个接收进程对发送来的消息收进程，每个接收进程对发送来的消息都必须取一次都必须取一次 进程同步和互斥（三）进程同步和互斥（三）THANK YOUSUCCESS2024/2/29 周四15可编辑Type BufferType=RecordType BufferType=Recordmsg:MessageType;msg:MessageType;count:integer;count:integer;mutex:semaphore;mutex:semaphore;初值为初值为11empty:semaphore;empty:semaphore;初值为初值为11full:array 1.n of semaphorefull:array 1.n of semaphore；初值全为初值全为00EndEndVar Var mutex:semaphore;mutex:semaphore;初值为初值为11s:integer;s:integer;初值为初值为00buff:array 0.k-1 of BufferType;buff:array 0.k-1 of BufferType;k k是缓冲区大小；是缓冲区大小；n n是接收进程个数是接收进程个数 m m是发送进程个数，通过是发送进程个数，通过 s s 进行进行“写互斥写互斥”Procedure Procedure Sender_i(i:integer);Sender_i(i:integer);i i 为发送进程的标号为发送进程的标号 VarVars0,j:integer;s0,j:integer;Begin Begin Repeat Repeat P(mutex);P(mutex);s0:=s;s0:=s;s:=(s+1)mod k;s:=(s+1)mod k;V(mutex);V(mutex);P(buffs0.empty)P(buffs0.empty)；在在buffs0.msgbuffs0.msg中写信息；中写信息；P(buffs0.mutex)P(buffs0.mutex)；buffs0.count:=n;buffs0.count:=n;V(buffs0.mutex);V(buffs0.mutex);For(j:=1 to n do)For(j:=1 to n do)V(buffs0.fullj);V(buffs0.fullj);Until false;Until false;EndEndProcedure Recvr(i:integer);Procedure Recvr(i:integer);i i 为接收进程的标号为接收进程的标号 VarVarj:integer;j:integer;Begin Begin j:=0;j:=0;Repeat Repeat P(buffj.fulli);P(buffj.fulli);从从buffj.msgbuffj.msg中读信息；中读信息；P(buffj.mutex)P(buffj.mutex)；buffj.count:=buffj.count:=buffj.count-1;buffj.count-1;If(buffj.count=0)If(buffj.count=0)Then V(buffj.empty)Then V(buffj.empty)；V(buffj.mutex);V(buffj.mutex);j:=(j+1)mod k j:=(j+1)mod kUntil false;Until false;EndEnd第二类读者写者问题（写者优先）第二类读者写者问题（写者优先）1 1）共享读）共享读2 2）互斥写、读写互斥）互斥写、读写互斥3 3）写者优先于读者（一旦有写者，则后续）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）读者必须等待，唤醒时优先考虑写者）进程同步和互斥（四）进程同步和互斥（四）Var Var mutex:semaphore;mutex:semaphore;互斥信号量，初值为互斥信号量，初值为11 R:semaphore;R:semaphore;对应读者等待队列，初值为对应读者等待队列，初值为00 W:semaphore;W:semaphore;对应写者等待队列，初值为对应写者等待队列，初值为00 一般变量：一般变量：Writing:Boolean;Writing:Boolean;初值初值false,false,有写者正在写有写者正在写 rc rc:integer;:integer;初值初值0,0,共享读的读者数共享读的读者数 rq rq:integer;:integer;初值初值0,0,等待队列中读者数等待队列中读者数 wq wq:integer;:integer;初值初值0,0,等待队列中写者数等待队列中写者数 Begin Begin P(mutex);P(mutex);If(Writing OR wq0)If(Writing OR wq0)Then BeginThen Beginrq:=rq+1;rq:=rq+1;V(mutex);V(mutex);P(R);P(R);P(mutex);P(mutex);resumeresume End;End;rc:=rc+1;rc:=rc+1;V(mutex);V(mutex);Read();Read();P(mutex);P(mutex);rc:=rc-1;rc:=rc-1;If(rc=0 AND wq0)If(rc=0 AND wq0)Then Begin Then Begin wq:=wq-1;wq:=wq-1;Writing:=true;Writing:=true;V(mutex);V(mutex);V(W);V(W);End;End;Else V(mutex)Else V(mutex);EndEnd读者进程(a)检测是否有写者并处理(b)Inc(rc)(c)Read()(d)Dec(rc)(e)处理写者等待队列Begin Begin P(mutex);P(mutex);If(Writing OR rc0)If(Writing OR rc0)Then BeginThen Beginwq:=wq+1;wq:=wq+1;V(mutex);V(mutex);P(W);P(W);End;End;Else BeginElse BeginWriting:=true;Writing:=true;V(mutex);V(mutex);Write();Write();P(mutex);P(mutex);If(wq0)If(wq0)Then BeginThen Beginwq:=wq-1;wq:=wq-1;V(mutex);V(mutex);V(W);V(W);End EndElse Else If(rq0)If(rq0)Then BeginThen BeginWriting:=false;Writing:=false;While(rq0)While(rq0)Begin Beginrq:=rq-1;rq:=rq-1;V(R)V(R);End End End EndElse BeginElse BeginWriting:=false;Writing:=false;V(mutex);V(mutex);End EndEndEnd写者进程(a)(a)检测是否有进程正在读写检测是否有进程正在读写 (b)Writing(T);Write();Writing(F)(b)Writing(T);Write();Writing(F)(c)(c)处理写者等待队列处理写者等待队列;处理处理ReaderReader等待队列等待队列P(s):P(s):s:=s-1;s:=s-1;If s0 If s0 Then Then 将本进程插入相应队列将本进程插入相应队列末尾末尾等待；等待；V(s)V(s)：s:=s+1;s:=s+1;If s=0 If s=0 Then Then 从等待队列从等待队列队尾队尾取一个进程唤醒，取一个进程唤醒，插入就绪队列插入就绪队列进程同步和互斥（五）进程同步和互斥（五）对对 P/V P/V 操作定义作以下修改操作定义作以下修改问题：问题：1 1）这样定义）这样定义P P、V V操作是否有问题？操作是否有问题？不合理：先进后出；可能不合理：先进后出；可能“无限等待无限等待”2 2）用这样的）用这样的P P、V V操作实现操作实现N N个进程竞争使个进程竞争使用某一共享变量的互斥机制。用某一共享变量的互斥机制。思路：令等待队列中始终只有一个进程。思路：令等待队列中始终只有一个进程。将将 “栈栈”变成变成 “队列队列”Var S:array 1.n-1 of semaphore;Var S:array 1.n-1 of semaphore;n n为进程数目；为进程数目；SiSi初值为初值为i i；SnSn到到S1S1的作用好象是的作用好象是 n n 层筛子层筛子 Procedure Pi;Procedure Pi;Var i:integer;Var i:integer;BeginBeginRepeatRepeat Pre_Do_it();Pre_Do_it();For i:=n-1 Downto 1 Do For i:=n-1 Downto 1 Do P(Si);P(Si);Do_It_In_Critical_Section;Do_It_In_Critical_Section;For i:=1 To n-1 Do For i:=1 To n-1 Do V(Si);V(Si);Post_Do_it();Post_Do_it();Until false;Until false;EndEnd3 3）对于）对于2 2）的解法，有无效率更高的方法。）的解法，有无效率更高的方法。如有，试问降低了多少复杂性？如有，试问降低了多少复杂性？上述解法每次都需要做上述解法每次都需要做2 2n n次次P/VP/V操作，操作，性能低下。采用二叉树的思想，改进如下：性能低下。采用二叉树的思想，改进如下：S1.4P1.4S1S2S3让信号量处于不同的层次上，每个信号量至多让信号量处于不同的层次上，每个信号量至多控制两个进程（对两个进程进行同步）控制两个进程（对两个进程进行同步）P1P2P3P4Procedure P1;Procedure P1;P2 is the sameP2 is the same Begin Begin Repeat Repeat P(S1);P(S1);P(S3);P(S3);Do_It();Do_It();V(S3);V(S3);V(S1);V(S1);Until false;Until false;End;End;Procedure P3;Procedure P3;P4 is the sameP4 is the same Begin Begin Repeat Repeat P(S2);P(S2);P(S3);P(S3);Do_It();Do_It();V(S3);V(S3);V(S2);V(S2);Until false;Until false;End;End;不妨设有不妨设有4 4个进程个进程P1.P4P1.P4，Var S1,S2,S3:semaphore;Var S1,S2,S3:semaphore;初值为初值为11假设共有假设共有2 2N N个进程争用临界区；个进程争用临界区；时间复杂性：时间复杂性：2 2N N vsvsN N；空间复杂性：空间复杂性：2 2N N vs 2vs 2N N1 1理发师问题理发师问题 理发店里有一位理发师理发店里有一位理发师,一把理发椅一把理发椅和和N N把供等候理发的顾客坐的椅子把供等候理发的顾客坐的椅子.如如果没有顾客果没有顾客,则理发师便在理发椅上则理发师便在理发椅上睡觉睡觉.当一个顾客到来时当一个顾客到来时,他必须先唤他必须先唤醒理发师醒理发师.如果顾客到来时理发师正如果顾客到来时理发师正在理发，则如果有空椅子，可坐下来在理发，则如果有空椅子，可坐下来等；否则离开。等；否则离开。进程同步和互斥（六）进程同步和互斥（六）顾客进程顾客进程 i:i:P(Sn);P(Sn);门外观望门外观望 P(mutex);P(mutex);进门；进门；V(mutex);V(mutex);V(S);V(S);等候；等候；理发；理发；V(Sn)V(Sn)P(mutex);P(mutex);出门；出门；V(mutex);V(mutex);VarVarSn:Sn:semaphore;semaphore;位子数目，初值为位子数目，初值为nnS:S:semaphore;semaphore;理发师睡觉，初值为理发师睡觉，初值为11 mutex:mutex:semaphore;semaphore;初值为初值为11理发师进程理发师进程 ：RepeatRepeat P(S);P(S);P(mutex);P(mutex);叫人理发；叫人理发；V(mutex);V(mutex);理发；理发；Until false;Until false;用用P.VP.V操作来实现操作来实现ReceiveReceive原语原语:ReceiveReceive（S S，M M）Begin Begin 根据根据S S找发送进程，找发送进程，如果没找到出错返回如果没找到出错返回;申请缓冲区消息申请缓冲区消息P P（s-ms-m）；）；P(m-mutex);P(m-mutex);将载有消息的缓冲区从消息链中取出将载有消息的缓冲区从消息链中取出;V(m-mutex);V(m-mutex);把消息从把消息从M M处处copycopy到到receiverreceiver的信息空间的信息空间;P(b-mutex);P(b-mutex);是缓冲区为空；是缓冲区为空；V(b-mutex);V(b-mutex);V(s-b);V(s-b);EndEnd其中其中s-bs-b初值初值:n;s-m:n;s-m初值初值:0:0THANK YOUSUCCESS2024/2/29 周四30可编辑