操作系统期末复习学习课程

1、例1页号页号物理块号物理块号0 05 51 110102 24 43 37 7则逻辑地址则逻辑地址0A5C0A5C（H H）所对应的物理地址为）所对应的物理地址为 ：_第1页/共80页第一页，编辑于星期日：十七点 二十三分。例10A5CH0A5CH0000,100000,1010,0101,1100 B10,0101,1100 B页号为页号为2 2，对应块号为，对应块号为4 4，物理地址：物理地址：00010001，000010,0101,110010,0101,1100即：即：125CH125CH页号页号物理块物理块号号0 05 51 110102 24 43 37 7第2页/共80页第二页

2、，编辑于星期日：十七点 二十三分。例2第3页/共80页第三页，编辑于星期日：十七点 二十三分。练习题。第4页/共80页第四页，编辑于星期日：十七点 二十三分。练习题虚地址虚地址0AFEH0000 1010 1111 1110P1 W010 1111 1110PA00100 1010 1111 1110 4AFEH虚地址虚地址1ADDH0001 1010 1101 1101P3 W010 1101 1101PA0010 1010 1101 1101 2ADDH第5页/共80页第五页，编辑于星期日：十七点 二十三分。 若在一分页存储管理系统中，某作业的页表如右所示。已知页面大小为1024字节，试将

3、逻辑地址0A5CH，07EFH，3000，5012转化为相应的物理地址。页号页号块号块号0 02 21 13 32 21 13 36 6第6页/共80页第六页，编辑于星期日：十七点 二十三分。 对于逻辑地址0A5CH 0A5CH=0000 1010 0101 1100 页号2，对应物理块1 物理地址为0000 0110 0101 1100 即065CH 对于逻辑地址07EFH 0A5CH=0000 0111 1110 1111 页号1，对应物理块3 物理地址为0000 1111 1110 1111 即0FEFH 对于逻辑地址3000 Pint(3000/1024)2 W3000 mod 102

4、4952 查页表第2页在第1块，所以物理地址为1976。 对于逻辑地址5012 Pint(5012/1024)4 W5012 mod 1024916 因页号超过页表长度，该逻辑地址非法。 第7页/共80页第七页，编辑于星期日：十七点 二十三分。习题解答虚地址 3412P3412 2048 1W 3412 mod 2048 1364MR=9*2048+1364=19796虚地址3412的内存地址是：19796第8页/共80页第八页，编辑于星期日：十七点 二十三分。第9页/共80页第九页，编辑于星期日：十七点 二十三分。第10页/共80页第十页，编辑于星期日：十七点 二十三分。分段地址变换例第11

5、页/共80页第十一页，编辑于星期日：十七点 二十三分。第12页/共80页第十二页，编辑于星期日：十七点 二十三分。 在一个段式存储管理系统中，其段表如左表所示，求右表逻辑地址对应的物理地址。第13页/共80页第十三页，编辑于星期日：十七点 二十三分。 1.(1)由于第0段的内存始址为210，段长为500，故逻辑地址0,430是合法地址。逻辑地址0,430对应的物理地址为210430640 。 (2)由于第1段的内存始址为2350，段长为20，故逻辑地址1,10是合法地址。逻辑地址1,10对应的物理地址为2350+10=2360 。 (3)由于第2段起始地址为100，段长为90，所给逻辑地址2,

6、500非法。 (4)由于第3段的内存始址为1350，段长为590，故逻辑地址3,400是合法地址。逻辑地址3,400对应的物理地址。 第14页/共80页第十四页，编辑于星期日：十七点 二十三分。第15页/共80页第十五页，编辑于星期日：十七点 二十三分。第16页/共80页第十六页，编辑于星期日：十七点 二十三分。 第17页/共80页第十七页，编辑于星期日：十七点 二十三分。第18页/共80页第十八页，编辑于星期日：十七点 二十三分。图 5-23 FCFS调度算法1. 1. 先来先服务先来先服务FCFS(First-Come, First Served)FCFS(Fir

7、st-Come, First Served)n仅用于请仅用于请求磁盘求磁盘I/OI/O的进的进程数目较程数目较少的场合。少的场合。第19页/共80页第十九页，编辑于星期日：十七点 二十三分。图 5-24 SSTF调度算法 2. 2. 最短寻道时间优先最短寻道时间优先SSTF(Shortest Seek Time First)SSTF(Shortest Seek Time First)第20页/共80页第二十页，编辑于星期日：十七点 二十三分。3. 3. 扫描扫描(SCAN)(SCAN)算法算法第21页/共80页第二十一页，编辑于星期日：十七点 二十三分。SCAN调度算法100道开始，增加方向道

8、开始，增加方向被访问下一个磁道被访问下一个磁道移动距离移动距离1505016010184249094583255339163811820平均寻道长度：平均寻道长度：27.8第22页/共80页第二十二页，编辑于星期日：十七点 二十三分。4. 4. 循环扫描循环扫描(CSCAN)(CSCAN)算法算法第23页/共80页第二十三页，编辑于星期日：十七点 二十三分。CSCAN调度算法100道开始，增加方向道开始，增加方向被访问的下一个磁道被访问的下一个磁道移动距离移动距离15050160101842418166382039155165839032平均寻道长度：平均寻道长度：27.5第24页/共80页第

9、二十四页，编辑于星期日：十七点 二十三分。 若某磁盘共有200个柱面，其编号为0199，假设已完成96号柱面的访问请求，还有若干个请求者在等待服务，它们依次要访问的柱面号为：175，52，157，36，159、106，l08，72，分别用先来先服务调度算法、最短寻道时间调度算法、电梯调度算法和单向扫描调度算法（向序号增加的方向移动）来确定实际服务的次序，并计算上述两种算法下移动臂需移动的距离。第25页/共80页第二十五页，编辑于星期日：十七点 二十三分。(1)先来先服务调度算法： 实际服务的次序： 96175521573615910610872 移动臂需移动的距离为： (175-96)+(17

10、5-52)+(157-52)+(157-36)+(159-36)+(159-106)+(108-106)+(108-72)=642 移动臂需移动642柱面的距离。 (2)最短寻找时间优先调度算法： 实际服务的次序：96106108725236157159175 移动臂需移动的距离为： (106-96)+(108-l06)+(108-72)+(72-52)+(52-36)+(157-36)+(159-l57)+(175-159)=223 移动臂需移动223个柱面的距离。 第26页/共80页第二十六页，编辑于星期日：十七点 二十三分。 (1)电梯调度算法： 实际服务的次序：961061081571

11、59175725236 (106-96)+(108-l06)+(157-108)+(159-l57)+(175-159)+(175-72)+(72-52)+(52-36)=218 移动臂需移动218个柱面的距离。 (2)单向扫描调度算法： 实际服务的次序：96106108157159175365272 (106-96)+(108-l06)+(157-108)+(159-l57)+(175-159)+(175-36)+(52-36)+(72-52)=254 除了移动臂由里向外返回所用的时间外，还需移动254个柱面的距离。 第27页/共80页第二十七页，编辑于星期日：十七点 二十三分。引用率707

12、70170122010323104430230321013201770201页框230420423023012712701第28页/共80页第二十八页，编辑于星期日：十七点 二十三分。FIFO123412512345页 0123412555344页 112341222533页 21234111255缺 页xxxxxxxxX第29页/共80页第二十九页，编辑于星期日：十七点 二十三分。如果在内存中分配如果在内存中分配4 4个页面，则缺页情况如下：个页面，则缺页情况如下：1212次访问中有缺页次访问中有缺页1010次；次；FIFO123412512345页 0123444512345页 11233

13、3451234页 21222345123页 3111234512缺 页xxxxxxxxxxBeladyBelady现象的现象的原因原因：FIFOFIFO算法的算法的置换特征置换特征与进程与进程访问内存的动态特征访问内存的动态特征是是矛盾矛盾的，即被置换的页面并的，即被置换的页面并不是进程不会访问的。不是进程不会访问的。第30页/共80页第三十页，编辑于星期日：十七点 二十三分。习题第31页/共80页第三十一页，编辑于星期日：十七点 二十三分。第32页/共80页第三十二页，编辑于星期日：十七点 二十三分。习题第33页/共80页第三十三页，编辑于星期日：十七点 二十三分。习题第34页/共80页第三

14、十四页，编辑于星期日：十七点 二十三分。习题第35页/共80页第三十五页，编辑于星期日：十七点 二十三分。第36页/共80页第三十六页，编辑于星期日：十七点 二十三分。第37页/共80页第三十七页，编辑于星期日：十七点 二十三分。 请求分页存储管理方式中，假定系统为某进程分配了4个页框，页面的引用顺序为：6、1、2、0、3、0、4、2、3、0、3、2、6、0，采用FIFO置换算法产生多少次页面置换？缺页率是多少？(2)(2)页面置换次数为页面置换次数为3 3次次 (3)(3)缺页率为：缺页率为：7/14=50% 7/14=50% 第38页/共80页第三十八页，编辑于星期日：十七点 二十三分。

15、请求分页存储管理方式中，假设分配给某进程的页框数为3，若程序的页面引用顺序为：0、2、3、4、1、2、5、0、2、3、2、5，采用最佳置换算法产生多少次页面置换？缺页率是多少？(2)(2)页面置换次数为页面置换次数为4 4次次 (3)(3)缺页率为：缺页率为：7/12=58% 7/12=58% 第39页/共80页第三十九页，编辑于星期日：十七点 二十三分。二、银行家算法二、银行家算法 避免死锁算法中最有代表性的算法是避免死锁算法中最有代表性的算法是Dijkstra Dijkstra E.W E.W 于于19681968年提出的银行家算法：年提出的银行家算法： 该算法需要检查申请者对资源的最大需

16、求量，如果该算法需要检查申请者对资源的最大需求量，如果系统现存的各类资源可以满足申请者的请求，就满系统现存的各类资源可以满足申请者的请求，就满足申请者的请求。足申请者的请求。 这样申请者就可很快完成其计算，然后释放它占这样申请者就可很快完成其计算，然后释放它占用的资源，从而保证了系统中的所有进程都能完用的资源，从而保证了系统中的所有进程都能完成，所以可避免死锁的发生。成，所以可避免死锁的发生。第40页/共80页第四十页，编辑于星期日：十七点 二十三分。 1 1数据结构数据结构 可利用资源向量可利用资源向量availableavailable 其初值是系统中该类资源的最大可用数目，其值其初值是系

17、统中该类资源的最大可用数目，其值将随着该类资源的分配与回收而动态改变。将随着该类资源的分配与回收而动态改变。 availablej=k: availablej=k: 系统现有系统现有RjRj类资源类资源k k个；个； 最大需求矩阵最大需求矩阵MaxMax 是一个是一个n nm m的矩阵，定义了系统中的的矩阵，定义了系统中的n n个进程中个进程中的每一个进程对的每一个进程对m m类资源的最大需求量。类资源的最大需求量。 maxi,j=k: maxi,j=k: 进程进程i i需要需要RjRj的最大数的最大数k k个；个；第41页/共80页第四十一页，编辑于星期日：十七点 二十三分。 分配矩阵分配矩

18、阵AllocationAllocation 是一个是一个n nm m的矩阵，定义了系统中每一类资源的数量。的矩阵，定义了系统中每一类资源的数量。allocationi,j=k: allocationi,j=k: 进程进程i i已得到已得到RjRj类资源类资源k k个；个； 需求矩阵需求矩阵NeedNeed 是一个是一个n nm m的矩阵，用以表示每一个进程尚需的各类资源数。的矩阵，用以表示每一个进程尚需的各类资源数。 needi,j=k:needi,j=k:进程进程i i还需还需RjRj类资源类资源k k个，方能完成任务。个，方能完成任务。 有：有：needi,j= maxi,jneedi,j

19、= maxi,jallocationi,jallocationi,j requestrequesti i进程进程i i请求资源数请求资源数第42页/共80页第四十二页，编辑于星期日：十七点 二十三分。 2 2银行家算法银行家算法 reqi=needierrorreqiNeedi,j,出错处理。出错处理。否则，转向下一步。否则，转向下一步。 若若RequestijAvailablei,j出错出错处理。处理。否则否则,转向下一步。转向下一步。N NN NN NY YY Y第43页/共80页第四十三页，编辑于星期日：十七点 二十三分。avail=avail-reqialloci=alloci+req

20、ineedi=needi-reqifinishi=.F.needi=workwork=work+allocifinishi=.T. 系统试着把资源分给进程系统试着把资源分给进程Pi，并修改下列数值。，并修改下列数值。Availj=Availj-Reqi j ;Alloi,jAlloi,j+ Reqij;Needi,j= Needi,jReqij ; 执行安全性算法执行安全性算法,检查这次资源分配后，系统是否处于检查这次资源分配后，系统是否处于安全状态安全状态.如果安全，则正式将资源分配给如果安全，则正式将资源分配给Pi，否则恢复原来的资源分，否则恢复原来的资源分配状态，然进程配状态，然进程Pi

21、等待。等待。第44页/共80页第四十四页，编辑于星期日：十七点 二十三分。安全性算法安全性算法1.1.设置两个工作向量设置两个工作向量设置一个临时向量设置一个临时向量workwork：表示系统可提供给进程继续运行的资源的集合。安：表示系统可提供给进程继续运行的资源的集合。安全性算法刚开始执行时，全性算法刚开始执行时，work:work:AvailableAvailable。设置一个数组设置一个数组finishifinishi：表示进程：表示进程i i能否顺序完成。当能否顺序完成。当finishifinishiTrueTrue，表示进程表示进程PiPi可以获得其所需的全部资源，而顺利执行完成。可

22、以获得其所需的全部资源，而顺利执行完成。第45页/共80页第四十五页，编辑于星期日：十七点 二十三分。安全性算法安全性算法2.2. 从进程集合中找到一个能满足下述条件的进程：从进程集合中找到一个能满足下述条件的进程：A Finishi= false; A Finishi= false; B B Needi,j workjNeedi,j workj；若找到，执行若找到，执行3 3步骤，否则执行步骤，否则执行4 4步骤步骤3.3. 进程进程PiPi获得资源，可顺利执行直至完成，然后释放获得资源，可顺利执行直至完成，然后释放它的全部资源。执行：它的全部资源。执行：Workj=workj+Alloca

23、tioni,j;Workj=workj+Allocationi,j;Finishi=True;Finishi=True;Goto 2Goto 24.4. 如果所有进程的如果所有进程的Finishi=true,Finishi=true,则系统处于安全则系统处于安全状态，否则处于不安全状态。状态，否则处于不安全状态。第46页/共80页第四十六页，编辑于星期日：十七点 二十三分。4 4实例实例 Max A B C Allocation A B C Need A B C Available A B C p0 7 5 3 0 1 0 7 4 3 3 3 2 p1 3 2 2 2 0 0 1 2 2 p2

24、 9 0 2 3 0 2 6 0 0 p3 2 2 2 2 1 1 0 1 1 p4 4 3 3 0 0 2 4 3 1T0时刻的资源分配表时刻的资源分配表5 3 27 4 37 4 57 5 510 5 7WORK第47页/共80页第四十七页，编辑于星期日：十七点 二十三分。4 4实例实例Work A B CNeed A B C Alloc A B CWork+alloc A B C Finish p1 3 3 2 1 2 2 2 0 0 5 3 2 true p3 5 3 2 0 1 1 2 1 1 7 4 3 true p4 7 4 3 4 3 1 0 0 2 7 4 5 true p2

25、 7 4 5 6 0 0 3 0 2 10 4 7 true p0 10 4 7 7 4 3 0 1 0 10 5 7 trueT0时刻的安全序列时刻的安全序列第48页/共80页第四十八页，编辑于星期日：十七点 二十三分。4 4实例实例 Max A B C Allocation A B C Need A B C Available A B C p0 7 5 3 0 1 0 7 4 3 (2 3 0) p1 3 2 2 (3 0 2) (0 2 0) p2 9 0 2 3 0 2 6 0 0 p3 2 2 2 2 1 1 0 1 1 p4 4 3 3 0 0 2 4 3 15 3 27 4 37

26、 4 57 5 510 5 7P1申请资源申请资源(1,0,2)时安全性检查时安全性检查(安全安全)WORK第49页/共80页第四十九页，编辑于星期日：十七点 二十三分。4 4实例实例Work A B CNeed A B C Alloc A B CWork+alloc A B C Finish p1 2 3 0 0 2 0 3 0 2 5 3 2 true p3 5 3 2 0 1 1 2 1 1 7 4 3 true p4 7 4 3 4 3 1 0 0 2 7 4 5 true p0 7 4 5 7 4 3 0 1 0 7 5 5 true p2 7 5 5 6 0 0 3 0 2 10

27、5 7 trueP1申请资源申请资源(1,0,2)时安全性检查时安全性检查(安全安全)第50页/共80页第五十页，编辑于星期日：十七点 二十三分。4 4实例实例 若此时若此时P4P4请求资源，请求资源，RequestRequest4 4（3 3，3 3，0 0），系统按），系统按照银行家算法进行检查：照银行家算法进行检查： RequestRequest4 4（3 3，3 3，0 0） Need Available Available（2 2，3 3，0 0）故故P P4 4需要等待需要等待 若此时若此时P0P0请求资源，请求资源，RequestRequest0 0（0 0，2 2，0 0），系

28、统），系统按照银行家算法进行检查：按照银行家算法进行检查： RequestRequest0 0（0 0，2 2，0 0） Need Need4 4（7 7，4 4，3 3），）， RequestRequest0 0（0 0，2 2，0 0） Available Available（2 2，3 3，0 0）故系统暂定能为故系统暂定能为P P0 0分配资源，修改有关数据。分配资源，修改有关数据。第51页/共80页第五十一页，编辑于星期日：十七点 二十三分。4 4实例实例 Allocation A B C Need A B C Available A B C p0 0 3 0 7 2 3 2 1 0

29、 p1 3 0 2 0 2 0 p2 3 0 2 6 0 0 p3 2 1 1 0 1 1 p4 0 0 2 4 3 1为为P0分配（分配（0，2，0）后的情况（不安全）后的情况（不安全）第52页/共80页第五十二页，编辑于星期日：十七点 二十三分。3.33.3调度算法调度算法是一个资源分配问题是一个资源分配问题 1.FCFS1.FCFS非剥夺式的调度算法。非剥夺式的调度算法。以以等待时间等待时间为主要的调度指标为主要的调度指标总是选择就绪队列的队首作业运行总是选择就绪队列的队首作业运行是一种最简单的调度算法，既可用于作业调度，也可用于进程调度是一种最简单的调度算法，既可用于作业调度，也可用于

30、进程调度优点优点: :实现简单，容易实现实现简单，容易实现缺点缺点: :没考虑进程的优先级没考虑进程的优先级 第53页/共80页第五十三页，编辑于星期日：十七点 二十三分。 例例:FCFS:FCFS算法算法第54页/共80页第五十四页，编辑于星期日：十七点 二十三分。3.33.3调度算法调度算法是一个资源分配问题是一个资源分配问题 剥夺或非剥夺式的调度算法。剥夺或非剥夺式的调度算法。以要求服务时间为主要的调度指标以要求服务时间为主要的调度指标总是选择执行时间最短的作业运行；进程运行时间不易确定，通总是选择执行时间最短的作业运行；进程运行时间不易确定，通常采用近似估算方法。常采用近似估算方法。第

31、55页/共80页第五十五页，编辑于星期日：十七点 二十三分。第56页/共80页第五十六页，编辑于星期日：十七点 二十三分。3.33.3调度算法调度算法是一个资源分配问题是一个资源分配问题 优点：有效地降低作业的优点：有效地降低作业的平均等待时间平均等待时间，缩短平，缩短平均周转时间和平均带权周转时间（从而提高了系均周转时间和平均带权周转时间（从而提高了系统吞吐量）统吞吐量）缺点：缺点：不利于长作业，会出现饿死现象。不利于长作业，会出现饿死现象。未考虑紧迫程度，不能保证紧迫性作业未考虑紧迫程度，不能保证紧迫性作业(进进程程)会被及时处理。会被及时处理。该算法不一定能真正做到短作业优先调度。作业该

32、算法不一定能真正做到短作业优先调度。作业(进程进程)的长短只是根据用户所估计的近似值。的长短只是根据用户所估计的近似值。第57页/共80页第五十七页，编辑于星期日：十七点 二十三分。FCFSFCFS与与SJFSJF调度算法调度算法1.FCFS1.FCFS算法算法vFCFSFCFS以以等待时间为调度指标等待时间为调度指标，优先考虑等待时间最，优先考虑等待时间最长的作业（进程），不利于短作业（进程）。长的作业（进程），不利于短作业（进程）。vFCFSFCFS利于利于CPUCPU繁忙型的作业而不利于繁忙型的作业而不利于I/OI/O繁忙型作业繁忙型作业v算法简单，效率低。算法简单，效率低。2.SJF2

33、.SJF算法算法v以以服务时间为调度指标服务时间为调度指标，有利于短作业（进程），不，有利于短作业（进程），不利于长作业（进程）利于长作业（进程）v有效降低了作业（进程）的有效降低了作业（进程）的平均等待时间平均等待时间，提高，提高系统吞吐量。系统吞吐量。第58页/共80页第五十八页，编辑于星期日：十七点 二十三分。第59页/共80页第五十九页，编辑于星期日：十七点 二十三分。优先权算法举例优先权算法举例 有有5 5个任务（个任务（A A、B B、C C、D D、E E）几乎同时到达，）几乎同时到达，估计他们运行时间分别为估计他们运行时间分别为(10(10、6 6、2 2、4 4、8)8)分分钟。其优先数（由外部设定）分别为钟。其优先数（由外部设定）分别为3 3、5 5、2 2、1 1和和4 4，其中，其中5 5设为最高优先级。对于优先级调度算设为最高优先级。对于优先级调度算法，计算其平均进程周转时间。法，计算其平均进程周转时间。带权周带权周转时间转时间周转周转 时间时间完成完成 时间时间 0 0开始开始时间时间 4 4 2 2 6 6 10 10运行运行 时间时