操作系统期末复习

1、逻辑地址转化物理地址过程,逻辑地址以十六进制数给出 根据页大小划分逻辑地址为页号和页内地址 以页号查页表，得到对应内存块号 物理地址页号拼接位移量 逻辑地址以十进制数给出 页号虚地址/页大小 位移量虚地址 mod 页大小 以页号查页表，得到对应内存块号 物理地址块号页大小位移量,例1,某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面对应的物理块号如下表：,则逻辑地址0A5C（H）所对应的物理地址为 ：_,例1,0A5CH0000,1010,0101,1100 B 页号为2，对应块号为4， 物理地址：0001，0010,0101,110

2、0 即：125CH,例2,设页面大小为1K字节，作业的0、1、2页分别存放在第2、3、8块中。求逻辑地址2500对应的物理地址？ 则逻辑地址2500的页号为2（2500/1024=2）页内地址为452 （2500 %1024452）。 查页表可知第2页对应的物理块号为8。 将块号8与页内地址452拼接（810244528644）得到物理地址为8644。,练习题,1.一分页存储管理系统中逻辑地址长度为16位，页面大小为1KB字节，现有一逻辑地址为0A6FH ，且第0、1、2、3、页依次存放在物理块3、7、11、10中。逻辑地址0A6FH对应的物理地址是多少？ 逻辑地址0A6FH的二进制表示如下：

3、 页号 页内地址 0000，10 10，0110，1111 由此可知逻辑地址0A6FH的页号为2，该页存放在第11号物理块中，用十六进制表示块号为B， 所以物理地址为： 0010，1110，0110，1111 ，即2E6FH。,练习题,2.有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、A、5块，试将虚地址0AFEH，1ADDH转换成内存地址。,虚地址0AFEH 0000 1010 1111 1110 P1 W010 1111 1110 PA00100 1010 1111 1110 4AFEH,虚地址1ADDH 0001 1010 1101 1101 P

4、3 W010 1101 1101 PA0010 1010 1101 1101 2ADDH,若在一分页存储管理系统中，某作业的页表如右所示。已知页面大小为1024字节，试将逻辑地址0A5CH，07EFH，3000，5012转化为相应的物理地址。,对于逻辑地址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(

5、3000/1024)2 W3000 mod 1024952 查页表第2页在第1块，所以物理地址为1976。 对于逻辑地址5012 Pint(5012/1024)4 W5012 mod 1024916 因页号超过页表长度，该逻辑地址非法。,习题解答,3 有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将虚地址7145，3412转换成内存地址。,虚地址 3412 P3412 2048 1 W 3412 mod 2048 1364 MR=9*2048+1364=19796 虚地址3412的内存地址 是：19796,虚地址 7145 P7145 2

6、048 3 W7145 mod 2048 1001 MR=5*2048+1001 =11241 虚地址7145的内存地址是：11241,4.5.2 分段系统的基本原理地址变换机构,地址变换过程： 进行地扯变换时，系统将逻辑地址中的段号S与段表长度进行比较，若段号超过了段表长度则产生越界中断； 否则根据段表始址和段号计算出该段对应段表项的位置，从中读出该段在内存的起始地址， 然后再检查段内地址是否超过该段的段长，若超过则同样发出越界中断信号； 若未越界，则将该段的起始地址与段内位移相加，从而得到了要访问的物理地址。,分段地址变换例,设作业分为3段，0、1、2段长度分别为1K、800、600，分别

7、存放在内存6K、4K、8K开始的内存区域。逻辑地址（2，100）的段号为2，段内位移为100。其物理地址是多少？ 查段表可知第2段在内存的起始地址8K。 将起始地址与段内位移相加，8K1008292，物理地址为8292。,例子： 给定段表如下，求下列对应的内存物理地址。 1、0,430 2、3,400 3、1,1 4、 2,500,在一个段式存储管理系统中，其段表如左表所示，求右表逻辑地址对应的物理地址。,1.(1)由于第0段的内存始址为210，段长为500，故逻辑地址0,430是合法地址。逻辑地址0,430对应的物理地址为210430640 。 (2)由于第1段的内存始址为2350，段长为2

8、0，故逻辑地址1,10是合法地址。逻辑地址1,10对应的物理地址为2350+10=2360 。 (3)由于第2段起始地址为100，段长为90，所给逻辑地址2,500非法。 (4)由于第3段的内存始址为1350，段长为590，故逻辑地址3,400是合法地址。逻辑地址3,400对应的物理地址。,5.6.1 磁盘的结构和性能,5.6.1 磁盘的结构和性能,二、磁盘的类型 硬盘和软盘、单片盘和多片盘、固定磁头和活动磁头。 1.固定头磁盘： 每个磁道上有一个磁头，并行读写，速度快 2.移动头磁盘： 每个盘面仅有一个磁头，要读写数据需要移动磁头寻道。结构简单、I/O速度慢 。 温

9、彻斯特磁盘简称温盘，是一种可移动磁头固定盘片的磁盘存储器，它是目前应用最广，最有代表性的硬磁盘存储器。,5.6.1 磁盘的结构和性能,三、磁盘访问时间： 1.寻道时间：TS=m*n+S m：常量，n：磁道数，s：磁盘启动时间。 2.旋转延时间Tr： 指定扇区旋转到磁头下所需时间。 设每秒r转，则Tr1/2r（均值） 3.数据传输时间Ttb/rN b：读写字节数 N：每道上的字节数 访问时间：Ta=Ts+Tr+Tt 可见，由于特定磁盘，只有集中放数据，集中读写（读写字节多）才能更好提高传输效率。,5.6.2 磁盘的调度算法,磁盘是典型的共享设备。在用户处理的信息量越来越大的情况下，对磁盘等共享设

10、备的访问也越来越频繁，因而访问调度是否得当直接影响到系统的效率。 磁盘调度的目标：减少寻道时间 有如下五种磁盘调度算法： 一、FCFS（Fisrt Come First Second） 二、SSTF（最短寻道优先） 三、扫描算法。 四、循环扫描CSCAN 五、NStepSCAN和FSCAN算法。,图 5-23 FCFS调度算法,1. 先来先服务FCFS(First-Come, First Served),仅用于请求磁盘I/O的进程数目较少的场合。,图 5-24 SSTF调度算法,2. 最短寻道时间优先SSTF(Shortest Seek Time First),要求访问的磁道与当前磁头距离最近

11、，使每次的寻道时间最短,SSTF算法虽然能获得较好的寻道性能，却可能导致某个进程发生“饥饿”(Starvation)现象。 Scan算法该算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑磁头当前的移动方向。 其原理是访问的下一个对象应是同方向的，且又距离最近的。一般自里向外访问，直至再无更外的磁道需要访问，才将磁臂换向自外向里，往返反复。这种算法又称为“电梯算法”,3. 扫描(SCAN)算法,SCAN调度算法,Cscan算法规定磁头单项移动，进行循环扫描。一个方向读完，不是象SCAN那样回头，而是循环。 访问时间：2TT+Smax T是从外向里或从里向外单向扫描完要访问的磁道的寻道时间

12、。 而Smax是将磁头从最外面被访问的磁道直接移到最里面欲访问的磁道的寻道时间。,4. 循环扫描(CSCAN)算法,CSCAN调度算法,若某磁盘共有200个柱面，其编号为0199，假设已完成96号柱面的访问请求，还有若干个请求者在等待服务，它们依次要访问的柱面号为：175，52，157，36，159、106，l08，72，分别用先来先服务调度算法、最短寻道时间调度算法、电梯调度算法和单向扫描调度算法（向序号增加的方向移动）来确定实际服务的次序，并计算上述两种算法下移动臂需移动的距离。,(1)先来先服务调度算法： 实际服务的次序： 96175521573615910610872 移动臂需移动的距

13、离为： (175-96)+(175-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个柱面的距离。,(1)电梯调度算法： 实际服务的次序：96106108157159175725236 (106

14、-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个柱面的距离。,4.8.1 最佳置换算法和先进先出算法,二、FIFO 淘汰最先进入内存的页面，即选择在内存中驻留时间最久的

15、页面予以淘汰。 出发点：最早调入主存中的页面不再使用的可能性越大，应该最先淘汰。算法简单对具有按线性顺序访问的程序比较合适，而对其它情况效率不高,4.8.1 最佳置换算法和先进先出算法,进程P执行时的页面走向为：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5； 如果在内存中分配3个页面，则缺页情况如下：12次访问中有缺页9次；,如果在内存中分配4个页面，则缺页情况如下：12次访问中有缺页10次；,Belady现象的原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。,习题,1某进程执行时的页面走向为1 2 3 4 1 2 5

16、1 2 3 4 5，分别画出其分配物理块为3的最佳置换算法的置换图。 2某进程执行时的页面走向为1 2 3 4 1 2 5 1 2 3 4 5，分别画出其分配物理块为3和4的FIFO算法的置换图。 3在请求分页管理系统中，一个作业要依次访问如下页面：3 4 2 1 4 3 1 4 3 1 4 5，采用LRU置换算法求出访问过程中发生的缺页中断的次数及缺页率。设分给作业的存储块数为3.,4在请求分页管理系统中，一个作业要依次访问如下页面：2 3 2 1 5 2 4 5 3 2 5 2，设分给作业的存储块数为3。若用最佳置换算法，先进先出，LRU置换算法求出访问过程中发生的缺页次数及缺页率。,习题

17、,1某进程执行时的页面走向为1 2 3 4 1 2 5 1 2 3 4 5，分别画出其分配物理块为3的最佳置换算法的置换图。,习题,2某进程执行时的页面走向为1 2 3 4 1 2 5 1 2 3 4 5，分别画出其分配物理块为3和4的FIFO算法的置换图。,习题,3在请求分页管理系统中，一个作业要依次访问如下页面：3 4 2 1 4 3 1 4 3 1 4 5，采用LRU置换算法求出访问过程中发生的缺页中断的次数及缺页率。设分给作业的存储块数为3.,4在请求分页管理系统中，一个作业要依次访问如下页面：2 3 2 1 5 2 4 5 3 2 5 2，设分给作业的存储块数为3。若用最佳置换算法，

18、先进先出，LRU置换算法求出访问过程中发生的缺页次数及缺页率。,请求分页存储管理方式中，假定系统为某进程分配了4个页框，页面的引用顺序为：6、1、2、0、3、0、4、2、3、0、3、2、6、0，采用FIFO置换算法产生多少次页面置换？缺页率是多少？,(2)页面置换次数为3次 (3)缺页率为：7/14=50%,请求分页存储管理方式中，假设分配给某进程的页框数为3，若程序的页面引用顺序为：0、2、3、4、1、2、5、0、2、3、2、5，采用最佳置换算法产生多少次页面置换？缺页率是多少？,(2)页面置换次数为4次 (3)缺页率为：7/12=58%,二、银行家算法 避免死锁算法中最有代表性的算法是Di

19、jkstra E.W 于1968年提出的银行家算法： 该算法需要检查申请者对资源的最大需求量，如果系统现存的各类资源可以满足申请者的请求，就满足申请者的请求。 这样申请者就可很快完成其计算，然后释放它占用的资源，从而保证了系统中的所有进程都能完成，所以可避免死锁的发生。,3.6.2 避免死锁,3.6.3利用银行家算法避免死锁,1数据结构 可利用资源向量available 其初值是系统中该类资源的最大可用数目，其值将随着该类资源的分配与回收而动态改变。 availablej=k: 系统现有Rj类资源k个； 最大需求矩阵Max 是一个nm的矩阵，定义了系统中的n个进程中的每一个进程对m类资源的最大

20、需求量。 maxi,j=k: 进程i需要Rj的最大数k个；,3.6.3利用银行家算法避免死锁,分配矩阵Allocation 是一个nm的矩阵，定义了系统中每一类资源的数量。allocationi,j=k: 进程i已得到Rj类资源k个； 需求矩阵Need 是一个nm的矩阵，用以表示每一个进程尚需的各类资源数。 needi,j=k:进程i还需Rj类资源k个，方能完成任务。 有：needi,j= maxi,jallocationi,j requesti进程i请求资源数,3.6.3利用银行家算法避免死锁,2银行家算法,当进程Pi 向系统提出申请类资源请求时，系统按下列步骤检查： 若RequestijN

21、eedi,j,出错处理。 否则，转向下一步。 若RequestijAvailablei,j出错处理。 否则,转向下一步。,N,N,N,Y,Y,3.6.3利用银行家算法避免死锁, 系统试着把资源分给进程Pi，并修改下列数值。 Availj=Availj-Reqi j ; Alloi,jAlloi,j+ Reqij; Needi,j= Needi,jReqij ; 执行安全性算法,检查这次资源分配后，系统是否处于安全状态. 如果安全，则正式将资源分配给Pi，否则恢复原来的资源分配状态，然进程Pi等待。,安全性算法,设置两个工作向量 设置一个临时向量work：表示系统可提供给进程继续运行的资源的集合

22、。安全性算法刚开始执行时，work:Available。 设置一个数组finishi：表示进程i能否顺序完成。当finishiTrue，表示进程Pi可以获得其所需的全部资源，而顺利执行完成。,安全性算法,从进程集合中找到一个能满足下述条件的进程： A Finishi= false; B Needi,j workj； 若找到，执行3步骤，否则执行4步骤 进程Pi获得资源，可顺利执行直至完成，然后释放它的全部资源。执行： Workj=workj+Allocationi,j; Finishi=True; Goto 2 如果所有进程的Finishi=true,则系统处于安全状态，否则处于不安全状态。,

23、4实例,T0时刻的资源分配表,5 3 2,7 4 3,7 4 5,7 5 5,10 5 7,WORK,4实例,T0时刻的安全序列,4实例,5 3 2,7 4 3,7 4 5,7 5 5,10 5 7,P1申请资源(1,0,2)时安全性检查(安全),WORK,4实例,P1申请资源(1,0,2)时安全性检查(安全),4实例,若此时P4请求资源，Request4（3，3，0），系统按照银行家算法进行检查： Request4（3，3，0） Available（2，3，0） 故P4需要等待 若此时P0请求资源，Request0（0，2，0），系统按照银行家算法进行检查： Request0（0，2，0）

24、Need4（7，4，3）， Request0（0，2，0） Available（2，3，0） 故系统暂定能为P0分配资源，修改有关数据。,4实例,为P0分配（0，2，0）后的情况（不安全）,3.3调度算法是一个资源分配问题,1.FCFS 非剥夺式的调度算法。 以等待时间为主要的调度指标 总是选择就绪队列的队首作业运行 是一种最简单的调度算法，既可用于作业调度，也可用于进程调度 优点:实现简单，容易实现 缺点:没考虑进程的优先级,3.3.1先来先服务和短作业（进程）优先调度算法,例:FCFS算法,3.3调度算法是一个资源分配问题,剥夺或非剥夺式的调度算法。 以要求服务时间为主要的调度指标 总是选择执行时间最短的作业运行；进程运行时间不易确定，通常采用近似估算方法。,2.短作业进程优先调度算法：SJ(P)F,3.3调度算法是一个资源分配问题,优点：有效地降低作业的平均等待时间，缩短平均周转时间和平均带权周转时间（从而提高了系统吞吐量） 缺点： 不利于长作业，会出现饿死现象。 未考虑紧迫程度，不能保证紧迫性作业(进程)会被及时处理。 该算法不一定能真正做到短作业优先调度。作业(进程)的长短只是根据用户所估计的近似值。,2.短作业进程优先调度算法：SJ(P)F,FCFS与SJF调度算法,1.FCFS算法 FCFS以等待时间为调度指标，优先考虑等待时间最长的作业