操作系统期末复习

逻辑地址转化物理地址过程逻辑地址以十六进制数给出根据页大小划分逻辑地址为页号和页内地址以页号查页表，得到对应内存块号物理地址＝页号拼接位移量逻辑地址以十进制数给出页号＝虚地址/页大小位移量＝虚地址mod页大小以页号查页表，得到对应内存块号物理地址＝块号×页大小＋位移量例1某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面对应的物理块号如下表：页号物理块号051102437则逻辑地址0A5C（H）所对应的物理地址为：_____例10A5CH＝0000,1010,0101,1100B页号为2，对应块号为4，物理地址：0001，0010,0101,1100即：125CH页号物理块号051102437例2设页面大小为1K字节，作业的0、1、2页分别存放在第2、3、8块中。求逻辑地址2500对应的物理地址？则逻辑地址2500的页号为2（2500/1024=2）页内地址为452（2500%1024＝452）。查页表可知第2页对应的物理块号为8。将块号8与页内地址452拼接（8×1024＋452＝8644）得到物理地址为8644。练习题1.一分页存储管理系统中逻辑地址长度为16位，页面大小为1KB字节，现有一逻辑地址为0A6FH，且第0、1、2、3、页依次存放在物理块3、7、11、10中。逻辑地址0A6FH对应的物理地址是多少？逻辑地址0A6FH的二进制表示如下：页号页内地址0000，1010，0110，1111由此可知逻辑地址0A6FH的页号为2，该页存放在第11号物理块中，用十六进制表示块号为B，所以物理地址为：0010，1110，0110，1111，即2E6FH。练习题2.有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、A、5块，试将虚地址0AFEH，1ADDH转换成内存地址。虚地址0AFEH0000101011111110P＝1W＝01011111110PA＝00100101011111110＝4AFEH虚地址1ADDH0001101011011101P＝3W＝01011011101PA＝0010101011011101

＝2ADDH若在一分页存储管理系统中，某作业的页表如右所示。已知页面大小为1024字节，试将逻辑地址0A5CH，07EFH，3000，5012转化为相应的物理地址。页号块号02132136对于逻辑地址0A5CH0A5CH=0000101001011100页号2，对应物理块1物理地址为0000011001011100即065CH对于逻辑地址07EFH0A5CH=0000011111101111页号1，对应物理块3物理地址为0000111111101111即0FEFH对于逻辑地址3000P＝int(3000/1024)＝2W＝3000mod1024＝952查页表第2页在第1块，所以物理地址为1976。对于逻辑地址5012P＝int(5012/1024)＝4W＝5012mod1024＝916因页号超过页表长度，该逻辑地址非法。习题解答3有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将虚地址7145，3412转换成内存地址。虚地址3412P＝3412％2048＝1W＝3412mod2048＝1364MR=9*2048+1364=19796虚地址3412的内存地址是：19796虚地址7145P＝7145％2048＝3W＝7145mod2048＝1001MR=5*2048+1001=11241虚地址7145的内存地址是：112414.5.2分段系统的基本原理－地址变换机构地址变换过程：进行地扯变换时，系统将逻辑地址中的段号S与段表长度进行比较，若段号超过了段表长度则产生越界中断；否则根据段表始址和段号计算出该段对应段表项的位置，从中读出该段在内存的起始地址，然后再检查段内地址是否超过该段的段长，若超过则同样发出越界中断信号；若未越界，则将该段的起始地址与段内位移相加，从而得到了要访问的物理地址。分段地址变换例设作业分为3段，0、1、2段长度分别为1K、800、600，分别存放在内存6K、4K、8K开始的内存区域。逻辑地址（2，100）的段号为2，段内位移为100。其物理地址是多少？查段表可知第2段在内存的起始地址8K。将起始地址与段内位移相加，8K＋100＝8292，物理地址为8292。例子：给定段表如下，求下列对应的内存物理地址。1、[0,430]2、[3,400]3、[1,1]4、[2,500]段号段首址段长0219600123001429010031327580在一个段式存储管理系统中，其段表如左表所示，求右表逻辑地址对应的物理地址。1.(1)由于第0段的内存始址为210，段长为500，故逻辑地址[0,430]是合法地址。逻辑地址[0,430]对应的物理地址为210＋430＝640。(2)由于第1段的内存始址为2350，段长为20，故逻辑地址[1,10]是合法地址。逻辑地址[1,10]对应的物理地址为2350+10=2360。(3)由于第2段起始地址为100，段长为90，所给逻辑地址[2,500]非法。(4)由于第3段的内存始址为1350，段长为590，故逻辑地址[3,400]是合法地址。逻辑地址[3,400]对应的物理地址为1350＋400＝1750。5.6.1磁盘的结构和性能5.6.1磁盘的结构和性能二、磁盘的类型硬盘和软盘、单片盘和多片盘、固定磁头和活动磁头。1.固定头磁盘：每个磁道上有一个磁头，并行读写，速度快2.移动头磁盘：每个盘面仅有一个磁头，要读写数据需要移动磁头—寻道。结构简单、I/O速度慢。温彻斯特磁盘简称温盘，是一种可移动磁头固定盘片的磁盘存储器，它是目前应用最广，最有代表性的硬磁盘存储器。5.6.1磁盘的结构和性能三、磁盘访问时间：1.寻道时间：TS=m*n+Sm：常量，n：磁道数，s：磁盘启动时间。2.旋转延时间Tr：指定扇区旋转到磁头下所需时间。设每秒r转，则Tr＝1/2r（均值）3.数据传输时间Tt＝b/rNb：读写字节数N：每道上的字节数访问时间：Ta=Ts+Tr+Tt可见，由于特定磁盘，只有集中放数据，集中读写（读写字节多）才能更好提高传输效率。

5.6.2磁盘的调度算法磁盘是典型的共享设备。在用户处理的信息量越来越大的情况下，对磁盘等共享设备的访问也越来越频繁，因而访问调度是否得当直接影响到系统的效率。磁盘调度的目标：减少寻道时间有如下五种磁盘调度算法：一、FCFS（FisrtComeFirstSecond）二、SSTF（最短寻道优先）三、扫描算法。四、循环扫描CSCAN五、N—Step—SCAN和FSCAN算法。图5-23FCFS调度算法1.先来先服务FCFS(First-Come,FirstServed)仅用于请求磁盘I/O的进程数目较少的场合。图5-24SSTF调度算法2.最短寻道时间优先SSTF(ShortestSeekTimeFirst)要求访问的磁道与当前磁头距离最近，使每次的寻道时间最短SSTF算法虽然能获得较好的寻道性能，却可能导致某个进程发生“饥饿”(Starvation)现象。Scan算法该算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑磁头当前的移动方向。其原理是访问的下一个对象应是同方向的，且又距离最近的。一般自里向外访问，直至再无更外的磁道需要访问，才将磁臂换向自外向里，往返反复。这种算法又称为“电梯算法”3.扫描(SCAN)算法SCAN调度算法100道开始，增加方向被访问下一个磁道移动距离1505016010184249094583255339163811820平均寻道长度：27.8Cscan算法规定磁头单项移动，进行循环扫描。一个方向读完，不是象SCAN那样回头，而是循环。访问时间：2TT+SmaxT是从外向里或从里向外单向扫描完要访问的磁道的寻道时间。而Smax是将磁头从最外面被访问的磁道直接移到最里面欲访问的磁道的寻道时间。4.循环扫描(CSCAN)算法CSCAN调度算法100道开始，增加方向被访问的下一个磁道移动距离15050160101842418166382039155165839032平均寻道长度：27.5若某磁盘共有200个柱面，其编号为0～199，假设已完成96号柱面的访问请求，还有若干个请求者在等待服务，它们依次要访问的柱面号为：175，52，157，36，159、106，l08，72，分别用先来先服务调度算法、最短寻道时间调度算法、电梯调度算法和单向扫描调度算法（向序号增加的方向移动）来确定实际服务的次序，并计算上述两种算法下移动臂需移动的距离。(1)先来先服务调度算法：实际服务的次序：96→175→52→157→36→159→106→108→72移动臂需移动的距离为：(175-96)+(175-52)+(157-52)+(157-36)+(159-36)+(159-106)+(108-106)+(108-72)=642移动臂需移动642柱面的距离。(2)最短寻找时间优先调度算法：实际服务的次序：96→106→108→72→52→36→157→159→175移动臂需移动的距离为：(106-96)+(108-l06)+(108-72)+(72-52)+(52-36)+(157-36)+(159-l57)+(175-159)=223移动臂需移动223个柱面的距离。(1)电梯调度算法：实际服务的次序：96→106→108→157→159→175→72→52→36(106-96)+(108-l06)+(157-108)+(159-l57)+(175-159)+(175-72)+(72-52)+(52-36)=218移动臂需移动218个柱面的距离。(2)单向扫描调度算法：实际服务的次序：96→106→108→157→159→175→36→52→72(106-96)+(108-l06)+(157-108)+(159-l57)+(175-159)+(175-36)+(52-36)+(72-52)=254除了移动臂由里向外返回所用的时间外，还需移动254个柱面的距离。4.8.1最佳置换算法和先进先出算法二、FIFO淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。出发点：最早调入主存中的页面不再使用的可能性越大，应该最先淘汰。算法简单对具有按线性顺序访问的程序比较合适，而对其它情况效率不高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．某进程执行时的页面走向为123412512345，分别画出其分配物理块为3的最佳置换算法的置换图。2．某进程执行时的页面走向为123412512345，分别画出其分配物理块为3和4的FIFO算法的置换图。3．在请求分页管理系统中，一个作业要依次访问如下页面：342143143145，采用LRU置换算法求出访问过程中发生的缺页中断的次数及缺页率。设分给作业的存储块数为3.4．在请求分页管理系统中，一个作业要依次访问如下页面：232152453252，设分给作业的存储块数为3。若用最佳置换算法，先进先出，LRU置换算法求出访问过程中发生的缺页次数及缺页率。习题1．某进程执行时的页面走向为123412512345，分别画出其分配物理块为3的最佳置换算法的置换图。习题2．某进程执行时的页面走向为123412512345，分别画出其分配物理块为3和4的FIFO算法的置换图。习题3．在请求分页管理系统中，一个作业要依次访问如下页面：342143143145，采用LRU置换算法求出访问过程中发生的缺页中断的次数及缺页率。设分给作业的存储块数为3.4．在请求分页管理系统中，一个作业要依次访问如下页面：232152453252，设分给作业的存储块数为3。若用最佳置换算法，先进先出，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%二、银行家算法

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

1．数据结构可利用资源向量available其初值是系统中该类资源的最大可用数目，其值将随着该类资源的分配与回收而动态改变。available[j]=k:系统现有Rj类资源k个；最大需求矩阵Max是一个n×m的矩阵，定义了系统中的n个进程中的每一个进程对m类资源的最大需求量。max[i,j]=k:进程i需要Rj的最大数k个；3.6.3利用银行家算法避免死锁分配矩阵Allocation是一个n×m的矩阵，定义了系统中每一类资源的数量。allocation[i,j]=k:进程i已得到Rj类资源k个；需求矩阵Need是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。need[i,j]=k:进程i还需Rj类资源k个，方能完成任务。有：need[i,j]=max[i,j]－allocation[i,j]requesti 进程i请求资源数3.6.3利用银行家算法避免死锁2．银行家算法reqi<=needierrorreqi<=availiblock当进程Pi向系统提出申请类资源请求时，系统按下列步骤检查：①若Requesti[j]>Need[i,j],出错处理。否则，转向下一步。②若Requesti[j]>Available[i,j]出错处理。否则,转向下一步。NNNYY3.6.3利用银行家算法避免死锁avail=avail-reqialloci=alloci+reqineedi=needi-reqifinish[i]=.F.needi<=workwork=work+allocifinish[i]=.T.③系统试着把资源分给进程Pi，并修改下列数值。Avail[j]=Avail[j]-Reqi[j];Allo[i,j]＝Allo[i,j]+Reqi[j];Need[i,j]=Need[i,j]－Reqi[j];④执行安全性算法,检查这次资源分配后，系统是否处于安全状态.如果安全，则正式将资源分配给Pi，否则恢复原来的资源分配状态，然进程Pi等待。安全性算法设置两个工作向量设置一个临时向量work：表示系统可提供给进程继续运行的资源的集合。安全性算法刚开始执行时，work:＝Available。设置一个数组finish[i]：表示进程i能否顺序完成。当finish[i]＝True，表示进程Pi可以获得其所需的全部资源，而顺利执行完成。安全性算法从进程集合中找到一个能满足下述条件的进程：AFinish[i]=false;BNeed[i,j]≤work[j]；若找到，执行3步骤，否则执行4步骤进程Pi获得资源，可顺利执行直至完成，然后释放它的全部资源。执行：Work[j]=work[j]+Allocation[i,j];Finish[i]=True;Goto2如果所有进程的Finish[i]=true,则系统处于安全状态，否则处于不安全状态。4实例MaxABC

AllocationABC

NeedABC

AvailableABCp0753

010

743

332p1322

200

122p2902

302

600p3222

211

011p4433

002

431T0时刻的资源分配表5327437457551057WORK4实例WorkABCNeedABC

AllocABCWork+allocABCFinishp1

332122

200532truep3

532011

211743truep4

743431

002745truep2

745600

3021047truep0

1047743

0101057trueT0时刻的安全序列4实例MaxABC

AllocationABC

NeedABC

AvailableABCp0753

010

743(230)p1322(302)(020)p2902

302

600p3222

211

011p4433

002

4315327437457551057P1申请资源(1,0,2)时安全性检查(安全)WORK4实例WorkABCNeedABC

AllocABCWork+allocABCFinishp1

230

020

302532truep3

532011

211743truep4

743

431

002745truep0

745

743

010755truep2

755

600

3021057trueP1申请资源(1,0,2)时安全性检查(安全)4实例若此时P4请求资源，Request4（3，3，0），系统按照银行家算法进行检查：Request4（3，3，0）<Need4（4，3，1），Request4（3，3，0）>Available（2，3，0）故P4需要等待若此时P0请求资源，Request0（0，2，0），系统按照银行家算法进行检查：Request0（0，2，0）<Need4（7，4，3），Request0（0，2，0）<Available（2，3，0）故系统暂定能为P0分配资源，修改有关数据。4实例AllocationABCNeedABCAvailableABCp0030723210p1302020p2302600p3211011p4002431为P0分配（0，2，0）后的情况（不安全）3.3调度算法——是一个资源分配问题1.FCFS非剥夺式的调度算法。以等待时间为主要的调度指标总是选择就绪队列的队首作业运行是一种最简单的调度算法，既可用于作业调度，也可用于进程调度优点:实现简单，容易实现缺点:没考虑进程的优先级3.3.1先来先服务和短作业（进程）优先调度算法

例:FCFS算法进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C21101102100100D31001022021991.993.3调度算法——是一个资源分配问题剥夺或非剥夺式的调度算法。以要求服务时间为主要的调度指标总是选择执行时间最短的作业运行；进程运行时间不易确定，通常采用近似估算方法。2.短作业进程优先调度算法：SJ(P)F3.3调度算法——是一个资源分配问题优点：有效地降低作业的平均等待时间，缩短平均周转时间和平均带权周转时间（从而提高了系统吞吐量）缺点：不利于长作业，会出现饿死现象。未考虑紧迫程度，不能保证紧迫性作业(进程)会被及时处理。该算法不一定能真正做到短作业优先调度。作业(进程)的长短只是根据用户所估计的近似值。2.短作业进程优先调度算法：SJ(P)FFCFS