操作系统期末大题

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,一 同步与互斥问题,分析题意，确定同步、互斥或同步与互斥问题。,设信号量，给出信号量表示的含义（公用，私用）和初始值。,描述算法，注意死锁问题。,把一个长度为,n,的有界缓冲区,(n,0),与一群生产者进程,P,1,，,P,2,，,，,P,m,和一群消费者进程,C,1,，,C,2,，,，,C,k,联系起来,3.6.4,生产者,消费者问题,设生产者进程和消费者进程是,互相等效,的，其中，各生产者进程使用的过程,deposit(data,),和各消费者使用的过程,remove(data,),可描述如下：,1.,首先,生产者,消费者问题是一个,同步问题,。即生产者和消费者之间满足如下条件：,1),消费者想,接收数据,时，有界缓冲区中至少有,一个,单元是,满的,2),生产者想,发送数据,时，有界缓冲区中至少有,一个,单元是,空的,2.,由于有界缓冲区是临界资源，因此，各生产者进程和各消费者进程之间,必须互斥执行,。,3.6.4,生产者,消费者问题,公用信号量,mutex,，保证生产者进程和消费者进程之间的互斥，,表示,可用有界缓冲区的个数，,初值为,1,；,信号量,avail,为生产者进程的私用信号量，,表示,有界缓冲区中的空单元个数，,初值为,n,；,信号量,full,为消费者进程的私用信号量，,表示,有界缓冲区中非空单元个数，,初值为,0,。,从而有：,3.6.4,生产者,消费者问题,deposit(data),：,begin,P(avail),P(mutex),送数据入缓冲区某单元,V(full),V(mutex),End,remove(data),：,begin,P(full),P(mutex),取缓冲区中某单元数据,V(avail),V(mutex),end,3.6.4,生产者,消费者问题,哲学家就餐问题,有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子,每个哲学家的行为是思考，感到饥饿，然后吃通心粉,为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子,设,fork5,为,5,个信号量，初值为均,1,forki,表示,i,号筷子被拿（,i= 0,，,1,，,2,，,3,，,4,）,Philosopheri,：,while (1),思考；,P(forki);,P(fork(i+1) % 5),；,进食；,V(forki);,V(fork(i+1) % 5),；,解,以上解法会出现死锁，为防止死锁发生可采取的措施：,最多允许,4,个哲学家同时坐在桌子周围,仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子,给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之。,分 析,设,fork5,为,5,个信号量,初值为均,1,，,forki,表示,i,号筷子被拿,设信号量,S,，,初值为,4,S,用于封锁第,5,个哲学家,无死锁哲学家就餐问题 解,1,Philosopheri,：,while (1),思考；,P(S),P(forki);,P(fork(i+1) % 5),；,进食；,V(forki);,V(fork(i+1) % 5),；,V(S),设,fork5,为,5,个信号量，初值为均,1,，,forki,表示,i,号筷子被拿,无死锁哲学家就餐问题 解,2,Philosopheri,：,Begin,if i mod 2 = 0,then,思考；,P(forki,);,P(forki+1 mod 5),；,进食；,V(forki,);,V(forki+1mod 5),；,else,思考；,P(forki+1 mod 5);,P(forki,),；,进食；,V(forki+1 mod 5);,V(forki,),；,二 作业调度,画表格计算周转时间和带权周转时间,给出作业（进程）调度序列,计算平均周转时间和平均带权周转时间,4.4,调度算法,思想：,按作业和就绪进程来到的次序进行调度。这种算法优先考虑在系统中等待时间最长的作业，而不管它要求运行时间的长短。,优点：,算法简单，公平，容易实现,缺点：,对于短作业或短进程，等待时间长,作业调度算法,FCFS,（,First come first serve,）,4.4,调度算法,作业调度算法,FCFS,下面是,4,个作业在系统中从提交、运行的信息。,作业,提交,时间,运行时间,开始,时间,完成,时间,周转,时间,带权周转时间,1,8,2,2,8.5,0.5,3,9,0.1,4,9.5,0.2,平均周转时间：,T=1.725,平均带权周转时间,W=6.875,8,10,10.5,10.6,10,10.5,10.6,10.8,2,2,1.6,1.3,1,4,16,6.5,4.4,调度算法,思想：,比较作业缓冲区中的作业预计的运行时间，选择,预计时间最短的作业,进入运行状态。,优点：,算法简单，可得到最大系统吞吐率，效率高。,缺点：,主要问题是对长作业不利，如果系统不断地接收短作业，就会使长作业长时间等待。,短作业优先算法,SJF,（,shortest job first,）,4.4,调度算法,短作业优先算法,SJF,作业,提交,时间,运行时间,开始,时间,完成,时间,周转,时间,带权周转时间,1,8,2,2,8.5,0.5,3,9,0.1,4,9.5,0.2,平均周转时间：,T=1.55,平均带权周转时间,W=5.15,8,10.3,10,10.1,10,10.8,10.1,10.3,2,2.3,1.1,0.8,1,4.6,11,4,4.4,调度算法,响应比,=,响应时间,/,预计执行时间,响应时间,=,等待时间,+,预计执行时间,所以响应比为：,1+,作业等待时间,/,预计执行时间,思想,：当需要从就绪队列中选择进程投入运行时，先计算每个进程的,响应,比，选择,响应,比最高的进程运行,优点,：短作业响应比高，执行时间短；长作业响应比随着等待时间增加而提高，不会过长等待。既照顾了短作业、也考虑到了长作业。,缺点,：每次调度前计算响应比增加了系统开销。,最高响应比优先,HRN,（,highest response-ratio next,）,4.4,调度算法,作业,提交,时间,运行时间,开始,时间,完成,时间,周转,时间,带权周转时间,1,8,2,2,8.5,0.5,3,9,0.1,4,9.5,0.20,平均周转时间：,T=1.625 W=5.675,最高响应比优先,HRN,8,10.1,10,10.6,10,10.6,10.1,10.8,2,2.1,1.1,1.3,1,4.2,11,6.5,三 地址映射,根据公式计算逻辑地址的页号和页内地址,p=,intA,/L d=A mod L,根据页表查找页面号。,页面号乘以页长,，,加上位移量（,d,）,计算逻辑地址,多次计算直到找到数据、指令为止。,逻辑空间,上的,地址,为：页号,+,页内地址，页内的地址空间是连续的，页之间不必连续。,19,9,10,0,页号,p,页内地址,d,如果给定的逻辑地址是,A,，,页面大小是,L,，,则,页 号,p,和,页内地址,d,可以按以下公式求得：,p=,intA,/L d=A mod L,例,：逻辑地址,100,页面大小,1k,5.4.1,页式管理的基本原理,5.4.2,静态页面管理,地址变换：,根据逻辑空间的页号，查找页表对应项找到对应的物理页面号，,页面号乘以页长,，,加上位移量（页内地址）,就是物理地址。每个作业的逻辑地址是连续的，重定位到内存空间后就不一定连续了。,变换过程全部由,硬件,地址变换机构,自动完成,。,5.4.2,静态页面管理,地址变换：,请求表中读出,MOV r1,，,2500,虚地址为,100,8*1024+452=8644,四 页面置换,根据引用页面序列画出页面置换图,给出被置换页面序列，调入内存页面序列,计算缺页次数，缺页率，命中率,5.4.4,请求页式管理的置换算法,先进先出算法,(FIFO- First Input First Output,）,先进入内存的页面先淘汰。,优点,：实现简单。,缺点,：常用的页会被淘汰。,缺页率,15/20=75%,1,2,3,4,1,2,5,1,2,3,4,5,1,1,1,4,4,4,5,5,5,5,5,5,2,2,2,1,1,1,1,1,3,3,3,3,3,3,2,2,2,2,2,4,4,1,2,3,4,1,2,5,1,2,3,4,5,1,1,1,1,1,1,5,5,5,5,4,4,2,2,2,2,2,2,1,1,1,1,5,3,3,3,3,3,3,2,2,2,2,4,4,4,4,4,4,3,3,3,Belady,现象,：分配给一个进程的,页面增加，反而出现缺页增加的现象,5.4.4,请求页式管理的置换算法,缺页率为,9/12=75%,缺页率,=10/12=83.3%,原因是,没有考虑页的执行顺序,5.4.4,请求页式管理的置换算法,最优淘汰算法,（,OPT-Optimal replacement algorithm,）：是理想算法。系统预测作业将要访问的页面。淘汰预测不被访问或长时间后才被访问中的页面。,缺页率,9/20=45%,几乎无法实现,!,5.4.4,请求页式管理的置换算法,最近,最久未使用页面淘汰法,（,LRU - Least Recently Used,）：,淘汰最近一段时间最久没访问的页面。,缺点,：每页设访问记录，每次更新，,系统开销大。,缺页率,12/20=60%,五 死锁避免,先验证系统初始状态的安全性，找出安全序列。,根据申请资源情况，结合剩余资源检查申请合理性。,验证分配后系统安全性，给出安全序列，否则不能分配资源给相应进程。,银行家算法实例,假定系统有四个进程,P1,P2,P3,P4,三种类型的资源,R1,R2,R3,数量分别为,9,，,3,，,6,，在,T0,时刻,的资源分配情况如下：,Process,Max,allocated,Need,Finish,Available,P1,3/2/2,1/0/0,2/2/2,false,1/1/2,P2,6/1/3,5/1/1,1/0/2,false,P3,3/1/4,2/1/1,1/0/3,false,P4,4/2/2,0/0/2,4/2/0,false,验证,T0,时刻的安全性,分析,：,1.,四进程执行状态都是未完成，,Finish=false,2.,找,Pi,，其需要的资源,need=,有效资源,work,3.,当前的,work=1/1/2,，,need P1 P2 P3 P4, (2/2/2),(1/0/2),(1/0/3), (4/2/0) ,4.,找到,P2,满足条件，如果让,P2,运行结束，,验证,T0,时刻的安全性,存在运行序列：,P2,P1,P3,P4,Process,Work,need,allocation,Work-new,Finish,P2,1/1/2,1/0/2,5/1/1,false,P1,2/2/2,1/0/0,false,P3,1/0/3,2/1/1,false,P4,4/2/0,0/0/2,false,0/1/0,0/0/0,6/1/3,true,6/2/3,6/2/3,4/0/1,0/0/0,3/2/2,7/2/3,7/2/3,6/2/0,0/0/0,true,true,true,0/0/0,3/1/4,9/3/4,9/3/4,5/1/4,4/2/2,9/3/6,P2,请求资源,1,，,0,，,1,现在,P2,请求资源,1/0/1,，按照银行家算法检查：,Request,2,1/0/1=Need,2,1/0/2,Request,2,1/0/1=Available,2,1/1/2,假定可以分配，修改,Available, Allocation, Need,Process,Max,allocated,Need,Finish,Available,P1,3/2/2,1/0/0,2/2/2,false,0/1/1,P2,6/1/3,6/1/2,0/0/1,false,P3,3/1/4,2/1/1,1/0/3,false,P4,4/2/2,0/0/2,4/2/0,false,进行安全性检查,验证,P2,分配资源后的安全性,存在运行序列：,P2,P1,P3,P4,Process,Work,need,allocation,Work-new,Finish,P2,0/1/1,0/0/1,6/1/2,false,P1,2/2/2,1/0/0,false,P3,1/0/3,2/1/1,false,P4,4/2/0,0/0/2,false,0/1/0,0/0/0,6/1/3,true,6/2/3,6/2/3,4/0/1,0/0/0,3/2/2,7/2/3,7/2/3,6/2/0,0/0/0,true,true,true,0/0/0,3/1/4,9/3/4,9/3/4,5/1/4,4/2/2,9/3/6,P1,请求资源,1/0/1,，按照银行家算法检查：,Request,1,1/0/1 ,Available,1,0/1/1,条件不满足，不能分配，让,P1,等待。,P1,请求资源,1,，,0,，,1,P3,请求资源,0,，,0,，,1,现在,P3,请求资源,0/0/1,，按照银行家算法检查：,Request,3,0/0/1=Need,3,1/0/3,Request,3,0/0/1=Available,3,0/1/1,假定可以分配，修改,Available, Allocation, Need,Process,Max,allocated,Need,Finish,Available,P1,3/2/2,1/0/0,2/2/2,false,0/1/0,P2,6/1/3,6/1/2,0/0/1,false,P3,3/1/4,2/1/2,1/0/2,false,P4,4/2/2,0/0/2,4/2/0,false,进行安全性检查,P3,分配资源后的安全性,分析,：四进程执行状态都是未完成，,Finish=false,找,Pi,，其需要的资源,need=,当前的,work=0/1/0,进程的,need P1 P2 P3 P4,(2/2/2), 0/0/1), (1/0/2), (4/2/0),找不到满足条件的,Pi,因此资源,P3,不能分配本次资源，回退。,Process,Max,allocated,Need,Finish,Available,P1,3/2/2,1/0/0,2/2/2,false,0/1/1,P2,6/1/3,6/1/2,0/0/1,false,P3,3/1/4,2/1/1,1/0/3,false,P4,4/2/2,0/0/2,4/2/0,false,P2,请求资源,1,，,0,，,1,现在,P2,请求资源,1/0/1,，按照银行家算法检查：,Request,2,1/0/1=Need,2,1/0/2,Request,2,1/0/1=Available,2,1/1/2,假定可以分配，修改,Available, Allocation, Need,Process,Max,allocated,Need,Finish,Available,P1,3/2/2,1/0/0,2/2/2,false,0/1/1,P2,6/1/3,6/1/2,0/0/1,false,P3,3/1/4,2/1/1,1/0/3,false,P4,4/2/2,0/0/2,4/2/0,false,