操作系统PV习题课ppt课件.ppt

操作系统习题讲解进程概念（一）解答：运行进程最多1个，最少0个；就绪进程最多N-1个，最少0个；等待进程最多N个，最少0个；概念：(1)进程、进程的基本状态；单CPU；进程切换瞬间；系统进程、用户进程；(2)死锁（不是“死机”）；进程概念（二）问题：一个转换发生，是否另一个转换一定发生？找出所有的可能。解答：就绪—运行:不一定（系统中仅一个进程）转换条件：被调度程序选中运行—就绪:一定（讨论就绪队列的长度）转换条件：时间片到时,或有更高优先级的进程出现解答：运行—等待:不一定（考虑死锁）转换条件：等待某事件发生等待—就绪:不一定转换条件：等待的事件发生进程概念（四）进程同步和互斥（一）进程同步和互斥（一）（同步）信号量：{实际上也起到互斥作用}S_Empty,T_Empty，{初值为1}S_Full,T_Full;{初值为0}进程同步和互斥（二）信号量：S_Door,{初值为0}S_Stop;{初值为0}问题：推广读写者问题中的消息缓冲处理。消息缓冲区为k个，有m个发送进程，n个接收进程，每个接收进程对发送来的消息都必须取一次TypeBufferType=Recordmsg:MessageType;count:integer;mutex:semaphore;{初值为1}empty:semaphore;{初值为1}full:array[1..n]ofsemaphore；{初值全为0}EndVarmutex:semaphore;{初值为1}s:integer;{初值为0}buff:array[0..k-1]ofBufferType;{k是缓冲区大小；n是接收进程个数}{m是发送进程个数，通过s进行“写互斥”}ProcedureSender_i(i:integer);{i为发送进程的标号}Vars0,j:integer;BeginRepeatP(mutex);s0:=s;s:=(s+1)modk;V(mutex);P(buff[s0].empty)；在buff[s0].msg中写信息；P(buff[s0].mutex)；buff[s0].count:=n;V(buff[s0].mutex);For(j:=1tondo)V(buff[s0].full[j]);Untilfalse;End第二类读者写者问题（写者优先）1）共享读2）互斥写、读写互斥3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）Varmutex:semaphore;{互斥信号量，初值为1}R:semaphore;{对应读者等待队列，初值为0}W:semaphore;{对应写者等待队列，初值为0}{一般变量：}Writing:Boolean;{初值false,有写者正在写}rc:integer;{初值0,共享读的读者数}rq:integer;{初值0,等待队列中读者数}wq:integer;{初值0,等待队列中写者数}BeginP(mutex);If(WritingORwq<>0)ThenBeginrq:=rq+1;V(mutex);P(R);P(mutex);{resume}End;rc:=rc+1;V(mutex);Read();BeginP(mutex);If(WritingORrc>0)ThenBeginwq:=wq+1;V(mutex);P(W);End;ElseBeginWriting:=true;V(mutex);Write();P(mutex);If(wq<>0)ThenBeginwq:=wq-1;V(mutex);V(W);EndElseP(s):s:=s-1;Ifs<0Then将本进程插入相应队列末尾等待；V(s)：s:=s+1;Ifs<=0Then从等待队列队尾取一个进程唤醒，插入就绪队列问题：1）这样定义P、V操作是否有问题？不合理：先进后出；可能“无限等待”2）用这样的P、V操作实现N个进程竞争使用某一共享变量的互斥机制。思路：令等待队列中始终只有一个进程。将“栈”变成“队列”VarS:array[1..n-1]ofsemaphore;{n为进程数目；S[i]初值为i；S[n]到S[1]的作用好象是n层筛子}ProcedurePi;Vari:integer;BeginRepeatPre_Do_it();Fori:=n-1Downto1DoP(S[i]);Do_It_In_Critical_Section;Fori:=1Ton-1DoV(S[i]);Post_Do_it();Untilfalse;End3）对于2）的解法，有无效率更高的方法。如有，试问降低了多少复杂性？上述解法每次都需要做2n次P/V操作，性能低下。采用二叉树的思想，改进如下：ProcedureP1;{P2isthesame}BeginRepeatP