《操作系统期末大题.ppt》由会员分享，可在线阅读，更多相关《操作系统期末大题.ppt（36页珍藏版）》请在三一办公上搜索。
1、一 同步与互斥问题,分析题意，确定同步、互斥或同步与互斥问题。设信号量，给出信号量表示的含义（公用，私用）和初始值。描述算法，注意死锁问题。,把一个长度为n的有界缓冲区(n0)与一群生产者进程P1，P2，Pm和一群消费者进程C1，C2，Ck联系起来,3.6.4 生产者消费者问题,设生产者进程和消费者进程是互相等效的，其中，各生产者进程使用的过程deposit(data)和各消费者使用的过程remove(data)可描述如下：1.首先生产者消费者问题是一个同步问题。即生产者和消费者之间满足如下条件：1)消费者想接收数据时，有界缓冲区中至少有一个单元是满的 2)生产者想发送数据时，有界缓冲区中至少
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(
3、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、；,解,以上解法会出现死锁，为防止死锁发生可采取的措施：最多允许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号
5、筷子被拿,无死锁哲学家就餐问题 解2,Philosopheri：Beginif i mod 2=0then 思考；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 调度算法,思想：按作业和就绪进程来到的次序进行调度。这种算法优先考虑在系统中等待时间最长的作业，而不管它要求运行时间的长短。优点：算法
6、简单，公平，容易实现缺点：对于短作业或短进程，等待时间长,作业调度算法FCFS（First come first serve）,4.4 调度算法,作业调度算法FCFS,下面是4个作业在系统中从提交、运行的信息。,平均周转时间：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 调度算法,思想：比较作业缓冲区中的作业预计的运行时间，选择预计时间最短的作业进入运行状态。优点：算法简单，可得到最大系统吞吐率，效率高。缺点：主要问题是对长作业不利，如果系统不断地接收短作业，就会使长作业长
7、时间等待。,短作业优先算法SJF（shortest job first）,4.4 调度算法,短作业优先算法SJF,平均周转时间：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+作业等待时间/预计执行时间思想：当需要从就绪队列中选择进程投入运行时，先计算每个进程的响应比，选择响应比最高的进程运行优点：短作业响应比高，执行时间短；长作业响应比随着等待时间增加而提高，不会过长等待。既照顾了短作
8、业、也考虑到了长作业。缺点：每次调度前计算响应比增加了系统开销。,最高响应比优先HRN（highest response-ratio next）,4.4 调度算法,平均周转时间：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）计算逻辑地址多次计算直到找到数据、指令为止。,逻辑空间上的地址为：页号+页内地址，页内的地址空间是连续的，页
9、之间不必连续。,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=
10、8644,四 页面置换,根据引用页面序列画出页面置换图给出被置换页面序列，调入内存页面序列计算缺页次数，缺页率，命中率,5.4.4 请求页式管理的置换算法,先进先出算法(FIFO-First Input First Output）,先进入内存的页面先淘汰。优点：实现简单。缺点：常用的页会被淘汰。,缺页率15/20=75%,Belady现象：分配给一个进程的页面增加，反而出现缺页增加的现象,5.4.4 请求页式管理的置换算法,缺页率为9/12=75%,缺页率=10/12=83.3%,原因是没有考虑页的执行顺序,5.4.4 请求页式管理的置换算法,最优淘汰算法（OPT-Optimal replac
11、ement algorithm）：是理想算法。系统预测作业将要访问的页面。淘汰预测不被访问或长时间后才被访问中的页面。,缺页率9/20=45%,几乎无法实现!,5.4.4 请求页式管理的置换算法,最近最久未使用页面淘汰法（LRU-Least Recently Used）：淘汰最近一段时间最久没访问的页面。缺点：每页设访问记录，每次更新，系统开销大。,缺页率12/20=60%,五 死锁避免,先验证系统初始状态的安全性，找出安全序列。根据申请资源情况，结合剩余资源检查申请合理性。验证分配后系统安全性，给出安全序列，否则不能分配资源给相应进程。,银行家算法实例,假定系统有四个进程P1,P2,P3,P
12、4,三种类型的资源R1,R2,R3,数量分别为9，3，6，在T0时刻的资源分配情况如下：,验证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,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
13、/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，按照银行家算法检查：Request21/0/1=Need21/0/2Request21/0/1=Available21/1/2假定可以分配，修改Available,Allocation,Need,进行安全性检查,验证P2分配资源后的安全性,存在运行序列：P2,P1,P3,P4,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/
14、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，按照银行家算法检查：Request11/0/1 Available10/1/1条件不满足，不能分配，让P1等待。,P1请求资源1，0，1,P3请求资源0，0，1,现在P3请求资源0/0/1，按照银行家算法检查：Request30/0/1=Need31/0/3Request30/0/1=Available30/1/1假定可以分配，修改Available,Allocation,Need,进行安全性检查,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不能分配本次资源，回退。,P2请求资源1，0，1,现在P2请求资源1/0/1，按照银行家算法检查：Request21/0/1=Need21/0/2Request21/0/1=Available21/1/2假定可以分配，修改Available,Allocation,Need,
