操作系统期末复习

1、逻辑地址转化物理地址过程例1页号页号物理块号物理块号0 05 51 110102 24 43 37 7则逻辑地址则逻辑地址0A5C0A5C（H H）所对应的物理地址为）所对应的物理地址为 ：_例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练习题。练习题虚地址虚地址0AFEH0000 10

2、10 1111 1110P1 W010 1111 1110PA00100 1010 1111 1110 4AFEH虚地址虚地址1ADDH0001 1010 1101 1101P3 W010 1101 1101PA0010 1010 1101 1101 2ADDH 若在一分页存储管理系统中，某作业的页表如右所示。已知页面大小为1024字节，试将逻辑地址0A5CH，07EFH，3000，5012转化为相应的物理地址。页号页号块号块号0 02 21 13 32 21 13 36 6 对于逻辑地址0A5CH 0A5CH=0000 1010 0101 1100 页号2，对应物理块1 物理地址为0000

3、0110 0101 1100 即065CH 对于逻辑地址07EFH 0A5CH=0000 0111 1110 1111 页号1，对应物理块3 物理地址为0000 1111 1110 1111 即0FEFH 对于逻辑地址3000 Pint(3000/1024)2 W3000 mod 1024952 查页表第2页在第1块，所以物理地址为1976。 对于逻辑地址5012 Pint(5012/1024)4 W5012 mod 1024916 因页号超过页表长度，该逻辑地址非法。 习题解答虚地址虚地址 3412P3412 2048 1W 3412 mod 2048 1364MR=9*2048+1364=

4、19796虚地址虚地址3412的内存地址的内存地址是：是：197964.5.2 分段系统的基本原理地址变换机构分段地址变换例 在一个段式存储管理系统中，其段表如左表所示，求右表逻辑地址对应的物理地址。 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,500非法。 (4)由于第3段的内存始址为1350

5、，段长为590，故逻辑地址3,400是合法地址。逻辑地址3,400对应的物理地址。 5.6.1 磁盘的结构和性能5.6.1 磁盘的结构和性能5.6.1 磁盘的结构和性能 5.6.2 磁盘的调度算法图 5-23 FCFS调度算法1. 先来先服务FCFS(First-Come, First Served)n仅用于请仅用于请求磁盘求磁盘I/OI/O的进的进程数目较程数目较少的场合。少的场合。图 5-24 SSTF调度算法 2. 最短寻道时间优先SSTF(Shortest Seek Time First)3. 扫描(SCAN)算法SCAN调度算法100道开始，增加方向道开始，

6、增加方向被访问下一个磁道被访问下一个磁道移动距离移动距离1505016010184249094583255339163811820平均寻道长度：平均寻道长度：27.84. 循环扫描(CSCAN)算法CSCAN调度算法100道开始，增加方向道开始，增加方向被访问的下一个磁道被访问的下一个磁道移动距离移动距离15050160101842418166382039155165839032平均寻道长度：平均寻道长度：27.5 若某磁盘共有200个柱面，其编号为0199，假设已完成96号柱面的访问请求，还有若干个请求者在等待服务，它们依次要访问的柱面号为：175，52，157，36，159、106，l08

7、，72，分别用先来先服务调度算法、最短寻道时间调度算法、电梯调度算法和单向扫描调度算法（向序号增加的方向移动）来确定实际服务的次序，并计算上述两种算法下移动臂需移动的距离。(1)先来先服务调度算法： 实际服务的次序： 96175521573615910610872 移动臂需移动的距离为： (175-96)+(175-52)+(157-52)+(157-36)+(159-36)+(159-106)+(108-106)+(108-72)=642 移动臂需移动642柱面的距离。 (2)最短寻找时间优先调度算法： 实际服务的次序：96106108725236157159175 移动臂需移动的距离为：

8、(106-96)+(108-l06)+(108-72)+(72-52)+(52-36)+(157-36)+(159-l57)+(175-159)=223 移动臂需移动223个柱面的距离。 (1)电梯调度算法： 实际服务的次序：96106108157159175725236 (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

9、-108)+(159-l57)+(175-159)+(175-36)+(52-36)+(72-52)=254 除了移动臂由里向外返回所用的时间外，还需移动254个柱面的距离。 4.8.1 最佳置换算法和先进先出算法引用率70770170122010323104430230321013201770201页框2304204230230127127014.8.1 最佳置换算法和先进先出算法FIFO123412512345页 0123412555344页 112341222533页 21234111255缺 页xxxxxxxxX如果在内存中分配如果在内存中分配4 4个页面，则缺页情况如下：个页面，则缺

10、页情况如下：1212次访问中有缺页次访问中有缺页1010次；次；FIFO123412512345页 0123444512345页 112333451234页 21222345123页 3111234512缺 页xxxxxxxxxxBeladyBelady现象的现象的原因原因：FIFOFIFO算法的算法的置换特征置换特征与进与进程程访问内存的动态特征访问内存的动态特征是是矛盾矛盾的，即被置换的页的，即被置换的页面并不是进程不会访问的。面并不是进程不会访问的。习题习题习题习题 请求分页存储管理方式中，假定系统为某进程分配了4个页框，页面的引用顺序为：6、1、2、0、3、0、4、2、3、0、3、2、

11、6、0，采用FIFO置换算法产生多少次页面置换？缺页率是多少？(2)(2)页面置换次数为页面置换次数为3 3次次 (3)(3)缺页率为：缺页率为：7/14=50% 7/14=50% 请求分页存储管理方式中，假设分配给某进程的页框数为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% 二、银行家算法二、银行家算法 避免死锁算法中最有代表性的算法是避免死锁算法中最有代表性的算法是Dijkstra Dijks

12、tra E.W E.W 于于19681968年提出的银行家算法：年提出的银行家算法： 该算法需要检查申请者对资源的最大需求量，如该算法需要检查申请者对资源的最大需求量，如果系统现存的各类资源可以满足申请者的请求，果系统现存的各类资源可以满足申请者的请求，就满足申请者的请求。就满足申请者的请求。 这样申请者就可很快完成其计算，然后释放它占这样申请者就可很快完成其计算，然后释放它占用的资源，从而保证了系统中的所有进程都能完用的资源，从而保证了系统中的所有进程都能完成，所以可避免死锁的发生。成，所以可避免死锁的发生。3.6.2 避免死锁3.6.3利用银行家算法避免死锁 1 1数据结构数据结构 可利用

13、资源向量可利用资源向量availableavailable 其初值是系统中该类资源的最大可用数目，其值将其初值是系统中该类资源的最大可用数目，其值将随着该类资源的分配与回收而动态改变。随着该类资源的分配与回收而动态改变。 availablej=k: availablej=k: 系统现有系统现有RjRj类资源类资源k k个；个； 最大需求矩阵最大需求矩阵MaxMax 是一个是一个n nm m的矩阵，定义了系统中的的矩阵，定义了系统中的n n个进程中的个进程中的每一个进程对每一个进程对m m类资源的最大需求量。类资源的最大需求量。 maxi,j=k: maxi,j=k: 进程进程i i需要需要Rj

14、Rj的最大数的最大数k k个；个；3.6.3利用银行家算法避免死锁 分配矩阵分配矩阵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个，方

15、能完成任务。个，方能完成任务。 有：有：needi,j= maxi,jneedi,j= maxi,jallocationi,jallocationi,j requestrequesti i进程进程i i请求资源数请求资源数3.6.3利用银行家算法避免死锁 2 2银行家算法银行家算法 reqi=needierrorreqiNeedi,j,出错出错处理。处理。否则，转向下一步。否则，转向下一步。 若若RequestijAvailablei,j出错处理。出错处理。否则否则,转向下一步。转向下一步。N NN NN NY YY Y3.6.3利用银行家算法避免死锁 avail=avail-reqiallo

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

17、的资源分配状态，然进程Pi等待。等待。安全性算法1.1.设置两个工作向量设置两个工作向量 设置一个临时向量设置一个临时向量workwork：表示系统可提供给进程：表示系统可提供给进程继续运行的资源的集合。安全性算法刚开始执行继续运行的资源的集合。安全性算法刚开始执行时，时，work:work:AvailableAvailable。 设置一个数组设置一个数组finishifinishi：表示进程：表示进程i i能否顺序完能否顺序完成。当成。当finishifinishiTrueTrue，表示进程，表示进程PiPi可以获得可以获得其所需的全部资源，而顺利执行完成。其所需的全部资源，而顺利执行完成。

18、安全性算法2.2. 从进程集合中找到一个能满足下述条件的进程：从进程集合中找到一个能满足下述条件的进程：A Finishi= false; A Finishi= false; B B Needi,j workjNeedi,j workj；若找到，执行若找到，执行3 3步骤，否则执行步骤，否则执行4 4步骤步骤3.3. 进程进程PiPi获得资源，可顺利执行直至完成，然后释放获得资源，可顺利执行直至完成，然后释放它的全部资源。执行：它的全部资源。执行：Workj=workj+Allocationi,j;Workj=workj+Allocationi,j;Finishi=True;Finishi=T

19、rue;Goto 2Goto 24.4. 如果所有进程的如果所有进程的Finishi=true,Finishi=true,则系统处于安全状则系统处于安全状态，否则处于不安全状态。态，否则处于不安全状态。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 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

20、 57 5 510 5 7WORK4实例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 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时刻的安全序列时刻的安全序列4实例 Max A B C Allocation A B C Need A B C Avai

21、lable 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 4 57 5 510 5 7P1申请资源申请资源(1,0,2)时安全性检查时安全性检查(安全安全)WORK4实例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

22、 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 5 7 trueP1申请资源申请资源(1,0,2)时安全性检查时安全性检查(安全安全)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

23、）故故P P4 4需要等待需要等待 若此时若此时P0P0请求资源，请求资源，RequestRequest0 0（0 0，2 2，0 0），系统按），系统按照银行家算法进行检查：照银行家算法进行检查： 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分配资源，修改有关数据。分配资源，修改有关数据。4实例 Allocation A B C Need A B C A

24、vailable A B C p0 0 3 0 7 2 3 2 1 0 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）后的情况（不安全）后的情况（不安全）3.3调度算法是一个资源分配问题 1.FCFS1.FCFS非剥夺式的调度算法。非剥夺式的调度算法。以以等待时间等待时间为主要的调度指标为主要的调度指标总是选择就绪队列的队首作业运行总是选择就绪队列的队首作业运行是一种最简单的调度算法，既可用于作业调是一种最简单的调度算法，既可用于作业调度，也可用于进程调度度，也可用于进程调度优点优点: :实

25、现简单，容易实现实现简单，容易实现缺点缺点: :没考虑进程的优先级没考虑进程的优先级 例:FCFS算法3.3调度算法是一个资源分配问题 剥夺或非剥夺式的调度算法。剥夺或非剥夺式的调度算法。以要求服务时间为主要的调度指标以要求服务时间为主要的调度指标总是选择执行时间最短的作业运行；进程总是选择执行时间最短的作业运行；进程运行时间不易确定，通常采用近似估算方运行时间不易确定，通常采用近似估算方法。法。3.3调度算法是一个资源分配问题 优点：有效地降低作业的优点：有效地降低作业的平均等待时间平均等待时间，缩短平，缩短平均周转时间和平均带权周转时间（从而提高了系均周转时间和平均带权周转时间（从而提高了

26、系统吞吐量）统吞吐量）缺点：缺点：不利于长作业，会出现饿死现象。不利于长作业，会出现饿死现象。未考虑紧迫程度，不能保证紧迫性作业未考虑紧迫程度，不能保证紧迫性作业(进程进程)会被及时处理。会被及时处理。该算法不一定能真正做到短作业优先调度。作该算法不一定能真正做到短作业优先调度。作业业(进程进程)的长短只是根据用户所估计的近似值的长短只是根据用户所估计的近似值。FCFS与SJF调度算法1.FCFS1.FCFS算法算法vFCFSFCFS以以等待时间为调度指标等待时间为调度指标，优先考虑等待时间最，优先考虑等待时间最长的作业（进程），不利于短作业（进程）。长的作业（进程），不利于短作业（进程）。vFCFSFCFS利于利于CPUCPU繁忙型的作业而不利于繁忙型的作业而不利于I/OI/O繁忙型作业繁忙型作业v算法简单，效率低。算法简单，效率低。2.SJF2.SJF算法算法v以以服务时间为调度