操作系统期末复习.

逻辑地址转化物理地址过程•逻辑地址以十六进制数给出1.根据页大小划分逻辑地址为页号和页内地址2.以页号查页表，得到对应内存块号3.物理地址＝页号拼接位移量•逻辑地址以十进制数给出1.页号＝虚地址/页大小位移量＝虚地址mod页大小2.以页号查页表，得到对应内存块号3.物理地址＝块号×页大小＋位移量例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•对于逻辑地址0A5CH•0A5CH=0000101001011100页号2，对应物理块1•物理地址为0000011001011100即065CH•对于逻辑地址07EFH•0A5CH=0000011111101111页号1，对应物理块3•物理地址为0000111111101111即0FEFH•对于逻辑地址3000•P＝int(3000/1024)＝2•W＝3000mod1024＝952•查页表第2页在第1块，所以物理地址为1976。•对于逻辑地址5012•P＝int(5012/1024)＝4•W＝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分段系统的基本原理－地址变换机构地址变换过程：1.进行地扯变换时，系统将逻辑地址中的段号S与段表长度进行比较，若段号超过了段表长度则产生越界中断；2.否则根据段表始址和段号计算出该段对应段表项的位置，从中读出该段在内存的起始地址，3.然后再检查段内地址是否超过该段的段长，若超过则同样发出越界中断信号；4.若未越界，则将该段的起始地址与段内位移相加，从而得到了要访问的物理地址。段表始址段表长度＋段号（2)100段表寄存器逻辑地址越界中断1k6k6004k5008k2009200段长基址段表段号01238292物理地址分段系统地址变换机构＋分段地址变换例•设作业分为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那样回头，而是循环。访问时间：2TT+SmaxT是从外向里或从里向外单向扫描完要访问的磁道的寻道时间。而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–淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。–出发点：最早调入主存中的页面不再使用的可能性越大，应该最先淘汰。算法简单对具有按线性顺序访问的程序比较合适，而对其它情况效率不高引用率70770170122010323104430230321013201770201页框2304204230230127127014.8.1最佳置换算法和先进先出算法进程P执行时的页面走向为：1,2,3,4,1,2,5,1,2,3,4,5；如果在内存中分配3个页面，则缺页情况如下：12次访问中有缺页9次；FIFO123412512345页0123412555344页112341222533页21234111255缺页xxxxxxx√√xX√如果在内存中分配4个页面，则缺页情况如下：12次访问中有缺页10次；FIFO123412512345页0123444512345页112333451234页21222345123页3111234512缺页xxxx√√xxxxxx٭Belady现象的原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。习题1．某进程执行时的页面走向为123412512345，分别画出其分配物理块为3的最佳置换算法的置换图。2．某进程执行时的页面走向为123412512345，分别画出其分配物