操作系统期末复习.ppt

逻辑地址转化物理地址过程逻辑地址以十六进制数给出逻辑地址以十六进制数给出1.1.根据页大小划分逻辑地址为页号和页内地址根据页大小划分逻辑地址为页号和页内地址根据页大小划分逻辑地址为页号和页内地址根据页大小划分逻辑地址为页号和页内地址2.2.以页号查页表，得到对应内存块号以页号查页表，得到对应内存块号以页号查页表，得到对应内存块号以页号查页表，得到对应内存块号3.3.物理地址页号拼接位移量物理地址页号拼接位移量物理地址页号拼接位移量物理地址页号拼接位移量逻辑地址以十进制数给出逻辑地址以十进制数给出1.1.页号虚地址页号虚地址页号虚地址页号虚地址/页大小页大小页大小页大小 位移量虚地址位移量虚地址位移量虚地址位移量虚地址 mod mod mod mod 页大小页大小页大小页大小2.2.以页号查页表，得到对应内存块号以页号查页表，得到对应内存块号以页号查页表，得到对应内存块号以页号查页表，得到对应内存块号3.3.物理地址块号物理地址块号物理地址块号物理地址块号页大小位移量页大小位移量页大小位移量页大小位移量例1某某某某虚虚虚虚拟拟拟拟存存存存储储储储器器器器的的的的用用用用户户户户编编编编程程程程空空空空间间间间共共共共32323232个个个个页页页页面面面面，每每每每页页页页为为为为1KB1KB1KB1KB，内内内内存存存存为为为为16KB16KB16KB16KB。假假假假定定定定某某某某时时时时刻刻刻刻一一一一用用用用户户户户页页页页表中已调入内存的页面对应的物理块号如下表：表中已调入内存的页面对应的物理块号如下表：表中已调入内存的页面对应的物理块号如下表：表中已调入内存的页面对应的物理块号如下表：页号页号物理块号物理块号0 05 51 110102 24 43 37 7则逻辑地址则逻辑地址0A5C0A5C（H H）所对应的物理地址为）所对应的物理地址为 ：_例10A5CH0A5CH0000,1010,0101,1100 B0000,1010,0101,1100 B页号为页号为2 2，对应块号为，对应块号为4 4，物理地址：物理地址：00010001，0010,0101,11000010,0101,1100即：即：125CH125CH页号页号物理块物理块号号0 05 51 110102 24 43 37 7例2设设页页面面大大小小为为1K1K字字节节，作作业业的的0 0、1 1、2 2页页分分别别存存放放在在第第2 2、3 3、8 8块块中中。求求逻逻辑辑地地址址25002500对应的物理地址？对应的物理地址？则则 逻逻 辑辑 地地 址址 25002500的的 页页 号号 为为2 2（2500/1024=22500/1024=2）页页内内地地址址为为452 452（2500 2500%1024%1024452452）。）。查页表可知第查页表可知第2 2页对应的物理块号为页对应的物理块号为8 8。将将块块号号8 8与与页页内内地地址址452452拼拼接接（8 81024102445245286448644）得到物理地址为）得到物理地址为86448644。练习题1.1.1.1.一一一一分分分分页页页页存存存存储储储储管管管管理理理理系系系系统统统统中中中中逻逻逻逻辑辑辑辑地地地地址址址址长长长长度度度度为为为为16161616位位位位，页页页页面面面面大大大大小小小小为为为为1KB1KB1KB1KB字字字字节节节节，现现现现有有有有一一一一逻逻逻逻辑辑辑辑地地地地址址址址为为为为0A6FH 0A6FH 0A6FH 0A6FH，且且且且第第第第0 0 0 0、1 1 1 1、2 2 2 2、3 3 3 3、页页页页依依依依次次次次存存存存放放放放在在在在物物物物理理理理块块块块3 3 3 3、7 7 7 7、11111111、10101010中中中中。逻逻逻逻辑地址辑地址辑地址辑地址0A6FH0A6FH0A6FH0A6FH对应的物理地址是多少？对应的物理地址是多少？对应的物理地址是多少？对应的物理地址是多少？逻辑地址逻辑地址逻辑地址逻辑地址0A6FH0A6FH0A6FH0A6FH的二进制表示如下：的二进制表示如下：的二进制表示如下：的二进制表示如下：页号页号页号页号 页内地址页内地址页内地址页内地址0000000000000000，10 1010 1010 1010 10，0110011001100110，1111 1111 1111 1111 由由由由此此此此可可可可知知知知逻逻逻逻辑辑辑辑地地地地址址址址0A6FH0A6FH0A6FH0A6FH的的的的页页页页号号号号为为为为2 2 2 2，该该该该页页页页存存存存放放放放在在在在第第第第11111111号号号号物物物物理块中，用十六进制表示块号为理块中，用十六进制表示块号为理块中，用十六进制表示块号为理块中，用十六进制表示块号为B B B B，所所所所以以以以物物物物理理理理地地地地址址址址为为为为：0010001000100010，1110111011101110，0110011001100110，1111 1111 1111 1111，即即即即2E6FH2E6FH2E6FH2E6FH。练习题2.2.2.2.有有有有一一一一系系系系统统统统采采采采用用用用页页页页式式式式存存存存储储储储管管管管理理理理，有有有有一一一一作作作作业业业业大大大大小小小小是是是是8KB8KB8KB8KB，页页页页大大大大小小小小为为为为2KB2KB2KB2KB，依依依依次次次次装装装装入入入入内内内内存存存存的的的的第第第第7 7 7 7、9 9 9 9、A A A A、5 5 5 5块块块块，试试试试将将将将虚虚虚虚地地地地址址址址0AFEH0AFEH0AFEH0AFEH，1ADDH1ADDH1ADDH1ADDH转转转转换换换换成成成成内存地址。内存地址。内存地址。内存地址。虚地址虚地址0AFEH0000 1010 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对于逻辑地址0A5CH0A5CH=0000 1010 0101 1100 页号2，对应物理块1物理地址为0000 0110 0101 1100 即065CH 对于逻辑地址07EFH0A5CH=0000 0111 1110 1111 页号1，对应物理块3物理地址为0000 1111 1110 1111 即0FEFH 对于逻辑地址3000Pint(3000/1024)2W3000 mod 1024952 查页表第2页在第1块，所以物理地址为1976。对于逻辑地址5012 Pint(5012/1024)4W5012 mod 1024916因页号超过页表长度，该逻辑地址非法。习题解答3 3 3 3 有有有有一一一一系系系系统统统统采采采采用用用用页页页页式式式式存存存存储储储储管管管管理理理理，有有有有一一一一作作作作业业业业大大大大小小小小是是是是8KB8KB8KB8KB，页页页页大大大大小小小小为为为为2KB2KB2KB2KB，依依依依次次次次装装装装入入入入内内内内存存存存的的的的第第第第7 7 7 7、9 9 9 9、10101010、5 5 5 5块块块块，试试试试将将将将虚虚虚虚地地地地址址址址7145714571457145，3412341234123412转转转转换换换换成成成成内存地址。内存地址。内存地址。内存地址。虚地址虚地址 3412P3412 2048 1W 3412 mod 2048 1364MR=9*2048+1364=19796虚地址虚地址3412的内存地址的内存地址是：是：19796 虚地址虚地址虚地址虚地址 7145 7145 7145 7145 P P P P7145 7145 7145 7145 2048 2048 2048 2048 3 3 3 3 W W W W7145 mod 20487145 mod 20487145 mod 20487145 mod 2048 1001100110011001 MR=5*2048+1001MR=5*2048+1001MR=5*2048+1001MR=5*2048+1001=11241=11241=11241=11241 虚地址虚地址虚地址虚地址7145714571457145的内存地址是：的内存地址是：的内存地址是：的内存地址是：112411124111241112414.5.2 分段系统的基本原理地址变换机构地址变换过程：地址变换过程：地址变换过程：地址变换过程：1.1.进进进进行行行行地地地地扯扯扯扯变变变变换换换换时时时时，系系系系统统统统将将将将逻逻逻逻辑辑辑辑地地地地址址址址中中中中的的的的段段段段号号号号S S S S与与与与段段段段表表表表长长长长度度度度进进进进行行行行比比比比较较较较，若若若若段段段段号号号号超超超超过过过过了了了了段段段段表表表表长长长长度度度度则则则则产生产生产生产生越界中断；越界中断；越界中断；越界中断；2.2.否否否否则则则则根根根根据据据据段段段段表表表表始始始始址址址址和和和和段段段段号号号号计计计计算算算算出出出出该该该该段段段段对对对对应应应应段段段段表表表表项的位置，从中读出该段在内存的起始地址，项的位置，从中读出该段在内存的起始地址，项的位置，从中读出该段在内存的起始地址，项的位置，从中读出该段在内存的起始地址，3.3.然然然然后后后后再再再再检检检检查查查查段段段段内内内内地地地地址址址址是是是是否否否否超超超超过过过过该该该该段段段段的的的的段段段段长长长长，若若若若超过则同样发出超过则同样发出超过则同样发出超过则同样发出越界中断信号越界中断信号越界中断信号越界中断信号；4.4.若若若若未未未未越越越越界界界界，则则则则将将将将该该该该段段段段的的的的起起起起始始始始地地地地址址址址与与与与段段段段内内内内位位位位移移移移相相相相加，从而得到了要访问的物理地址。加，从而得到了要访问的物理地址。加，从而得到了要访问的物理地址。加，从而得到了要访问的物理地址。分段地址变换例设设作作业业分分为为3 3段段，0 0、1 1、2 2段段长长度度分分别别为为1K1K、800800、600600，分分别别存存放放在在内内存存6K6K、4K4K、8K8K开开始始的的内内存存区区域域。逻逻辑辑地地址址（2 2，100100）的的段段号号为为2 2，段段内内位位移移为为100100。其其物物理理地地址址是是多多少？少？查段表可知第查段表可知第2 2段在内存的起始地址段在内存的起始地址8K8K。将将起起始始地地址址与与段段内内位位移移相相加加，8K8K10010082928292，物理地址为，物理地址为82928292。例子：例子：给定段表如下，求下列对应的内存物理地址。给定段表如下，求下列对应的内存物理地址。1 1、0,430 20,430 2、3,400 33,400 3、1,1 41,1 4、2,5002,500段号段号段号段号段首址段首址段首址段首址段长段长段长段长0 0 0 02192192192196006006006001 1 1 12300230023002300141414142 2 2 2909090901001001001003 3 3 31327132713271327580580580580在一个段式存储管理系统中，其段表如左表所示，求右表逻辑地址对应的物理地址。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，段长为590，故逻辑地址3,400是合法地址。逻辑地址3,400对应的物理地址为13504001750。5.6.1 磁盘的结构和性能5.6.1 磁盘的结构和性能二、磁盘的类型二、磁盘的类型二、磁盘的类型二、磁盘的类型 硬盘和软盘、单片盘和多片盘、固定磁头和活动磁头。硬盘和软盘、单片盘和多片盘、固定磁头和活动磁头。硬盘和软盘、单片盘和多片盘、固定磁头和活动磁头。硬盘和软盘、单片盘和多片盘、固定磁头和活动磁头。1.1.1.1.固定头磁盘：固定头磁盘：固定头磁盘：固定头磁盘：每个磁道上有一个磁头，并行读写，速度快每个磁道上有一个磁头，并行读写，速度快每个磁道上有一个磁头，并行读写，速度快每个磁道上有一个磁头，并行读写，速度快2.2.2.2.移动头磁盘：移动头磁盘：移动头磁盘：移动头磁盘：每个盘面仅有一个磁头，要读写数据需要移动磁头每个盘面仅有一个磁头，要读写数据需要移动磁头每个盘面仅有一个磁头，要读写数据需要移动磁头每个盘面仅有一个磁头，要读写数据需要移动磁头寻道。结构简单、寻道。结构简单、寻道。结构简单、寻道。结构简单、I/OI/OI/OI/O速度慢速度慢速度慢速度慢 。温彻斯特磁盘简称温盘，是一种可移动磁头固定盘温彻斯特磁盘简称温盘，是一种可移动磁头固定盘温彻斯特磁盘简称温盘，是一种可移动磁头固定盘温彻斯特磁盘简称温盘，是一种可移动磁头固定盘片的磁盘存储器，它是目前应用最广，最有代表性片的磁盘存储器，它是目前应用最广，最有代表性片的磁盘存储器，它是目前应用最广，最有代表性片的磁盘存储器，它是目前应用最广，最有代表性的硬磁盘存储器。的硬磁盘存储器。的硬磁盘存储器。的硬磁盘存储器。5.6.1 磁盘的结构和性能三、磁盘访问时间：三、磁盘访问时间：三、磁盘访问时间：三、磁盘访问时间：1.1.1.1.寻道时间：寻道时间：寻道时间：寻道时间：TS=m*n+STS=m*n+STS=m*n+STS=m*n+Sm m m m：常量，：常量，：常量，：常量，n n n n：磁道数，：磁道数，：磁道数，：磁道数，s s s s：磁盘启动时间。：磁盘启动时间。：磁盘启动时间。：磁盘启动时间。2.2.2.2.旋转延时间旋转延时间旋转延时间旋转延时间TrTrTrTr：指定扇区旋转到磁头下所需时间。指定扇区旋转到磁头下所需时间。指定扇区旋转到磁头下所需时间。指定扇区旋转到磁头下所需时间。设每秒设每秒设每秒设每秒r r r r转，则转，则转，则转，则TrTrTrTr1/2r1/2r1/2r1/2r（均值）（均值）（均值）（均值）3.3.3.3.数据传输时间数据传输时间数据传输时间数据传输时间TtTtTtTtb/rNb/rNb/rNb/rNb b b b：读写字节数：读写字节数：读写字节数：读写字节数N N N N：每道上的字节数：每道上的字节数：每道上的字节数：每道上的字节数访问时间：访问时间：访问时间：访问时间：Ta=Ts+Tr+TtTa=Ts+Tr+TtTa=Ts+Tr+TtTa=Ts+Tr+Tt可见，由于特定磁盘，只有集中放数据，集中读写可见，由于特定磁盘，只有集中放数据，集中读写可见，由于特定磁盘，只有集中放数据，集中读写可见，由于特定磁盘，只有集中放数据，集中读写（读写字节多）才能更好提高传输效率。（读写字节多）才能更好提高传输效率。（读写字节多）才能更好提高传输效率。（读写字节多）才能更好提高传输效率。5.6.2 磁盘的调度算法 磁盘是典型的共享设备。在用户处理的信息量越来越磁盘是典型的共享设备。在用户处理的信息量越来越磁盘是典型的共享设备。在用户处理的信息量越来越磁盘是典型的共享设备。在用户处理的信息量越来越大的情况下，对磁盘等共享设备的访问也越来越频繁，大的情况下，对磁盘等共享设备的访问也越来越频繁，大的情况下，对磁盘等共享设备的访问也越来越频繁，大的情况下，对磁盘等共享设备的访问也越来越频繁，因而访问调度是否得当直接影响到系统的效率。因而访问调度是否得当直接影响到系统的效率。因而访问调度是否得当直接影响到系统的效率。因而访问调度是否得当直接影响到系统的效率。磁盘调度的目标：减少寻道时间磁盘调度的目标：减少寻道时间磁盘调度的目标：减少寻道时间磁盘调度的目标：减少寻道时间有如下五种磁盘调度算法：有如下五种磁盘调度算法：有如下五种磁盘调度算法：有如下五种磁盘调度算法：一、一、一、一、FCFSFCFSFCFSFCFS（Fisrt Come First SecondFisrt Come First SecondFisrt Come First SecondFisrt Come First Second）二、二、二、二、SSTFSSTFSSTFSSTF（最短寻道优先）（最短寻道优先）（最短寻道优先）（最短寻道优先）三、扫描算法。三、扫描算法。三、扫描算法。三、扫描算法。四、循环扫描四、循环扫描四、循环扫描四、循环扫描CSCANCSCANCSCANCSCAN 五、五、五、五、N N N NStepStepStepStepSCANSCANSCANSCAN和和和和FSCANFSCANFSCANFSCAN算法。算法。算法。算法。图 5-23 FCFS调度算法1.先来先服务FCFS(First-Come,First Served)n仅用于请仅用于请求磁盘求磁盘I/OI/O的进的进程数目较程数目较少的场合。少的场合。图 5-24 SSTF调度算法 2.最短寻道时间优先SSTF(Shortest Seek Time First)n n要求访问的磁道与当要求访问的磁道与当要求访问的磁道与当要求访问的磁道与当前磁头距离最近，使前磁头距离最近，使前磁头距离最近，使前磁头距离最近，使每次的寻道时间最短每次的寻道时间最短每次的寻道时间最短每次的寻道时间最短vSSTFSSTFSSTFSSTF算算算算法法法法虽虽虽虽然然然然能能能能获获获获得得得得较较较较好好好好的的的的寻寻寻寻道道道道性性性性能能能能，却却却却可可可可能能能能导致某个进程发生导致某个进程发生导致某个进程发生导致某个进程发生“饥饿饥饿饥饿饥饿”(Starvation)(Starvation)(Starvation)(Starvation)现象。现象。现象。现象。vScanScanScanScan算法该算法不仅考虑到欲访问的磁道与当算法该算法不仅考虑到欲访问的磁道与当算法该算法不仅考虑到欲访问的磁道与当算法该算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑磁头当前的移动方前磁道间的距离，更优先考虑磁头当前的移动方前磁道间的距离，更优先考虑磁头当前的移动方前磁道间的距离，更优先考虑磁头当前的移动方向。向。向。向。v其原理是访问的下一个对象应是同方向的，且其原理是访问的下一个对象应是同方向的，且其原理是访问的下一个对象应是同方向的，且其原理是访问的下一个对象应是同方向的，且又距离最近的。一般自里向外访问，直至再无更又距离最近的。一般自里向外访问，直至再无更又距离最近的。一般自里向外访问，直至再无更又距离最近的。一般自里向外访问，直至再无更外的磁道需要访问，才将磁臂换向自外向里，往外的磁道需要访问，才将磁臂换向自外向里，往外的磁道需要访问，才将磁臂换向自外向里，往外的磁道需要访问，才将磁臂换向自外向里，往返反复。这种算法又称为返反复。这种算法又称为返反复。这种算法又称为返反复。这种算法又称为“电梯算法电梯算法电梯算法电梯算法”3.扫描(SCAN)算法SCAN调度算法100道开始，增加方向道开始，增加方向被访问下一个磁道被访问下一个磁道移动距离移动距离1505016010184249094583255339163811820平均寻道长度：平均寻道长度：27.8CscanCscanCscanCscan算法规定磁头单项移动，进行循环扫描。一算法规定磁头单项移动，进行循环扫描。一算法规定磁头单项移动，进行循环扫描。一算法规定磁头单项移动，进行循环扫描。一个方向读完，不是象个方向读完，不是象个方向读完，不是象个方向读完，不是象SCANSCANSCANSCAN那样回头，而是循环。那样回头，而是循环。那样回头，而是循环。那样回头，而是循环。n n访问时间：访问时间：访问时间：访问时间：2T2T2T2TT+SmaxT+SmaxT+SmaxT+Smaxn nT T T T是从外向里或从里向外单向是从外向里或从里向外单向是从外向里或从里向外单向是从外向里或从里向外单向扫描完要访问的磁道扫描完要访问的磁道扫描完要访问的磁道扫描完要访问的磁道的寻道时间的寻道时间的寻道时间的寻道时间。n n而而而而SmaxSmaxSmaxSmax是将磁头从最外面被访问的磁道是将磁头从最外面被访问的磁道是将磁头从最外面被访问的磁道是将磁头从最外面被访问的磁道直接移到直接移到直接移到直接移到最最最最里面欲访问的磁道的寻道时间。里面欲访问的磁道的寻道时间。里面欲访问的磁道的寻道时间。里面欲访问的磁道的寻道时间。4.循环扫描(CSCAN)算法CSCAN调度算法100道开始，增加方向道开始，增加方向被访问的下一个磁道被访问的下一个磁道移动距离移动距离15050160101842418166382039155165839032平均寻道长度：平均寻道长度：27.5若某磁盘共有200个柱面，其编号为0199，假设已完成96号柱面的访问请求，还有若干个请求者在等待服务，它们依次要访问的柱面号为：175，52，157，36，159、106，l08，72，分别用先来先服务调度算法、最短寻道时间调度算法、电梯调度算法和单向扫描调度算法（向序号增加的方向移动）来确定实际服务的次序，并计算上述两种算法下移动臂需移动的距离。(1)先来先服务调度算法：实际服务的次序：96175521573615910610872 移动臂需移动的距离为：(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-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 最佳置换算法和先进先出算法二、二、二、二、FIFOFIFOFIFOFIFO淘汰淘汰淘汰淘汰最先进入内存的页面最先进入内存的页面最先进入内存的页面最先进入内存的页面，即选择在内存中驻留时间，即选择在内存中驻留时间，即选择在内存中驻留时间，即选择在内存中驻留时间最久的页面予以淘汰。最久的页面予以淘汰。最久的页面予以淘汰。最久的页面予以淘汰。出发点：最早调入主存中的页面不再使用的可能性越出发点：最早调入主存中的页面不再使用的可能性越出发点：最早调入主存中的页面不再使用的可能性越出发点：最早调入主存中的页面不再使用的可能性越大，应该最先淘汰。算法简单对具有按线性顺序访问大，应该最先淘汰。算法简单对具有按线性顺序访问大，应该最先淘汰。算法简单对具有按线性顺序访问大，应该最先淘汰。算法简单对具有按线性顺序访问的程序比较合适，而对其它情况效率不高的程序比较合适，而对其它情况效率不高的程序比较合适，而对其它情况效率不高的程序比较合适，而对其它情况效率不高4.8.1 最佳置换算法和先进先出算法进程进程进程进程P P P P执行时的页面走向为：执行时的页面走向为：执行时的页面走向为：执行时的页面走向为：1,2,3,4,1,1,2,3,4,1,1,2,3,4,1,1,2,3,4,1,2,5,1,2,3,4,52,5,1,2,3,4,52,5,1,2,3,4,52,5,1,2,3,4,5；如果在内存中分配如果在内存中分配如果在内存中分配如果在内存中分配3 3 3 3个页面，则缺页情况如下：个页面，则缺页情况如下：个页面，则缺页情况如下：个页面，则缺页情况如下：12121212次访问中有缺页次访问中有缺页次访问中有缺页次访问中有缺页9 9 9 9次；次；次；次；如果在内存中分配如果在内存中分配4 4个页面，则缺页情况如下：个页面，则缺页情况如下：1212次访问中有缺页次访问中有缺页1010次；次；BeladyBelady现象的原因：现象的原因：FIFOFIFO算法的置换特征与进算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。面并不是进程不会访问的。习题1 1 1 1某进程执行时的页面走向为某进程执行时的页面走向为某进程执行时的页面走向为某进程执行时的页面走向为1 2 3 4 1 2 5 1 2 1 2 3 4 1 2 5 1 2 1 2 3 4 1 2 5 1 2 1 2 3 4 1 2 5 1 2 3 4 53 4 53 4 53 4 5，分别画出其分配物理块为，分别画出其分配物理块为，分别画出其分配物理块为，分别画出其分配物理块为3 3 3 3的最佳置换算的最佳置换算的最佳置换算的最佳置换算法的置换图。法的置换图。法的置换图。法的置换图。2 2 2 2某进程执行时的页面走向为某进程执行时的页面走向为某进程执行时的页面走向为某进程执行时的页面走向为1 2 3 4 1 2 5 1 2 1 2 3 4 1 2 5 1 2 1 2 3 4 1 2 5 1 2 1 2 3 4 1 2 5 1 2 3 4 53 4 53 4 53 4 5，分别画出其分配物理块为，分别画出其分配物理块为，分别画出其分配物理块为，分别画出其分配物理块为3 3 3 3和和和和4 4 4 4的的的的FIFOFIFOFIFOFIFO算算算算法的置换图。法的置换图。法的置换图。法的置换图。3 3 3 3在请求分页管理系统中，一个作业要依次访问在请求分页管理系统中，一个作业要依次访问在请求分页管理系统中，一个作业要依次访问在请求分页管理系统中，一个作业要依次访问如下页面：如下页面：如下页面：如下页面：3 4 2 1 4 3 1 4 3 1 4 53 4 2 1 4 3 1 4 3 1 4 53 4 2 1 4 3 1 4 3 1 4 53 4 2 1 4 3 1 4 3 1 4 5，采用，采用，采用，采用LRULRULRULRU置换算法求出访问过程中发生的缺页中断的次数置换算法求出访问过程中发生的缺页中断的次数置换算法求出访问过程中发生的缺页中断的次数置换算法求出访问过程中发生的缺页中断的次数及缺页率。设分给作业的存储块数为及缺页率。设分给作业的存储块数为及缺页率。设分给作业的存储块数为及缺页率。设分给作业的存储块数为3.3.3.3.4 4 4 4在请求分页管理系统中，一个作业要依次访问在请求分页管理系统中，一个作业要依次访问在请求分页管理系统中，一个作业要依次访问在请求分页管理系统中，一个作业要依次访问如下页面：如下页面：如下页面：如下页面：2 3 2 1 5 2 4 5 3 2 5 22 3 2 1 5 2 4 5 3 2 5 22 3 2 1 5 2 4 5 3 2 5 22 3 2 1 5 2 4 5 3 2 5 2，设分给，设分给，设分给，设分给作业的存储块数为作业的存储块数为作业的存储块数为作业的存储块数为3 3 3 3。若用最佳置换算法，先进。若用最佳置换算法，先进。若用最佳置换算法，先进。若用最佳置换算法，先进先出，先出，先出，先出，LRULRULRULRU置换算法求出访问过程中发生的缺页置换算法求出访问过程中发生的缺页置换算法求出访问过程中发生的缺页置换算法求出访问过程中发生的缺页次数及缺页率。次数及缺页率。次数及缺页率。次数及缺页率。请求分页存储管理方式中，假定系统为某进程分配了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%请求分页存储管理方式中，假设分配给某进程的页框数为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 Dijkstra E.W E.W 于于19681968年提出的银行家算法：年提出的银行家算法：该该算算法法需需要要检检查查申申请请者者对对资资源源的的最最大大需需求求量量，如如果果系系统统现现存存的的各各类类资资源源可可以以满满足足申申请请者者的的请请求求，就满足申请者的请求。就满足申请者的请求。这这样样申申请请者者就就可可很很快快完完成成其其计计算算，然然后后释释放放它它占占用用的的资资源源，从从而而保保证证了了系系统统中中的的所所有有进进程程都都能能完完成，所以可避免死锁的发生。成，所以可避免死锁的发生。3.6.2 避免死锁3.6.3利用银行家算法避免死锁 1 1数据结构数据结构可利用资源向量可利用资源向量availableavailable 其初值是系统中该类资源的最大可用数目，其值将其初值是系统中该类资源的最大可用数目，其值将随着该类资源的分配与回收而动态改变。随着该类资源的分配与回收而动态改变。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个；个；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个，方能完成任务。个，方能完成任务。有：有：needi,j=maxi,jneedi,j=maxi,jallocationi,jallocationi,jrequestrequesti i进程进程i i请求资源数请求资源数3.6.3利用银行家算法避免死锁 2 2银行家算法银行家算法 reqi=needierrorreqiNeedi,j,出出错处理。错处理。否则，转向下一步。否则，转向下一步。若若RequestijAvailablei,j出出错处理。错处理。否则否则,转向下一步。转向下一步。N NN NN NY YY Y3.6.3利用银行家算法避免死锁 avail=avail-reqialloci=alloci+reqineedi=needi-reqifinishi=.F.needi=workwork=work+allocifinishi=.T.系统试着把资源分给进程系统试着把资源分给进程Pi，并修改下列数值。，并修改下列数值。Availj=Availj-Reqi j;Alloi,jAlloi,j+Reqij;Needi,j=Needi,jReqij;执行安全性算法执行安全性算法,检查这次资源分配后，系统检查这次资源分配后，系统是否处于安全状态是否处于安全状态.如果安全，则正式将资源分配给如果安全，则正式将资源分配给Pi，否则恢复原，否则恢复原来的资源分配状态，然进程来的资源分配状态，然进程Pi等待。等待。安全性算法1.1.设置两个工作向量设置两个工作向量设置一个临时向量设置一个临时向量workwork：表示系统可提供给进程：表示系统可提供给进程继续运行的资源的集合。安全性算法刚开始执行继续运行的资源的集合。安全性算法刚开始执行时，时，work:work:AvailableAvailable。设置一个数组设置一个数组finishifinishi：表示进程：表示进程i i能否顺序完能否顺序完成。当成。当finishifinishiTrueTrue，表示进程，表示进程PiPi可以获得可以获得其所需的全部资源，而顺利执行完成。其所需的全部资源，而顺利执行完成。安全性算法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=True;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 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 Available A B C