北方工业大学 操作系统 操作系统期末复习.ppt

《北方工业大学 操作系统 操作系统期末复习.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、操作系统期末复习MadebyTzh第一部分：大题本部分为课上老师所讲的几道大题，作为大题而言命中率应该蛮高的吧，它们包括：资源分配图硬盘调度页面置换算法PB操作物理地址替换1.资源分配图会看、会画会判断死锁P1P2r1r2会看、会画P1P23个资源2个资源P1进程P1进程请求资源进程拥有资源P1拥有2个r1资源并请求1个r2P2拥有1个r1资源和1个r2资源并请求1个r1r1r2判断死锁P1P2P1需要1个r2P2需要1个r1R1剩余0个资源R2剩余1个资源P2的需求无法满足，但P1可以得到满足

2、P1P2P2需要1个r1R1剩余2个资源R2剩余1个资源P1顺利执行，释放占用所有资源P2需求得到满足，顺利执行P1P2R1剩余3个资源R2剩余2个资源在这种情况下不会死锁那么，什么情况下会产生死锁呢P1P2P1需要2个r2P2需要1个r1R1剩余0个资源R2剩余1个资源此时，P1、P2的需求都无法得到满足，死锁2.磁盘调度想象，从磁盘圆心处向外画一条直线作为我们下图的X轴，把磁盘的磁道序号标在上面。题目是这样出的条件：欲访问的磁道号：100、55、58、39、18、90、160、150磁头当前

3、位置：100问题：磁头移动磁道数和平均寻道长度1.先来先服务算法100、55、58、39、18、90、160、150我们从起始位置开始，按顺序扫描，设磁头移动磁道数为m，初始为0100、55、58、39、18、90、160、150磁头移动到55，m+=(100-55),m=45100、55、58、39、18、90、160、150磁头移动到58，m+=(58-55),m=48100、55、58、39、18、90、160、150磁头移动到39，m+=(58-39),m=67注意：磁头移动的是距离而不

4、是位移，所以不可能为负数，因此一定是大减小以此类推，直到全部扫描完当然，如果是答题，我们直接列式子即可m=(100-55)+(58-55)+(58-39)+…..=结果平均寻道长度=m/nn为磁道号个数2.最短寻道时间优先算法为了节约时间，这次我们不再按照顺序来扫描磁盘了18、39、55、58、90、100、150、160还是那些磁道，不过这次我们提前排好序，起始位置依然100接着我们看，在需要跑的磁道中，离100最近的磁道是哪个这也是我们之所以要排序的原因，在这种情况下只有100相邻的两个磁道

5、可能是我们的选择我们发现，相比150,磁道90离100更近，所以我们先去9018、39、55、58、90、100、150、160m+=(100-90)m=10同样，相比于100,58距离90更近，我们选择5818、39、55、58、90、100、150、160m+=(90-58)m=42以此类推，知道将所有磁道跑完当然，跑过的磁道我们不会跑第二遍我猜你可能会问:这真的是最短的寻道时间吗？当然，答案肯定是不一定，计算机只能看到下一步的情况，但它不可能像围棋高手一样总览全局，至于真正的最短，那就是我

6、们程序员写的算法才能够实现了，在操作系统中不会这么复杂3.扫描算法（电梯算法）没错，就像是电梯一样，直上直下，一条道走到黑，撞了南墙再回头18、39、55、58、90、100、150、160同样的，我们把磁道号排好序，初始位置100然后，我们按照序号增加的方向依次寻道18、39、55、58、90、100、150、16018、39、55、58、90、100、150、160咚！撞墙了，这时可以回头了，但注意寻过道的磁道不需要再走一遍18、39、55、58、90、100、150、160所以我们直接跳到

7、9018、39、55、58、90、100、150、16018、39、55、58、90、100、150、160分页存储求物理地址指令：Load1,2500指令的逻辑地址是100，页长1k，求指令的物理地址1.求页号逻辑地址/页长，商为页号，余数为偏移量2.查表3.物理地址=物理块号*页长+偏移量页号物理块号041827取了两次地址，第一次根据逻辑地址找到物理地址，第二次取物理地址页面置换算法如果给的是逻辑地址需要求出页号页号=逻辑地址/页长（要的是商）先进先出（FIFO）将页号依次排好方法一开始是

8、依次装入物理块，全都有缺页中断方法如果物理块满了，判断哪个页面存在时间最长就替换方法是向左划线判断哪条最长，同时缺页中断方法如果下一个页面物理块已经有了，就不用写了，也没有缺页中断最近最久未使用（LRU）方法往前数第三个来替换（有几个物理块找几个），但不算重复的，有重复的还要往前找要计算的东西缺页次数：每一次页面替换和页面装入（画的对勾数）被置换的页号顺序：被替换走的页号按顺序排列缺页率=缺页次数/页面总数生产者—消费者问题他们又是互斥关系，又是相互协作关系，也是同步关系解法P操作，也可以是wa