操作系统期末复习.pptx

《操作系统期末复习.pptx》由会员分享，可在线阅读，更多相关《操作系统期末复习.pptx（80页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、例1某某某某虚虚虚虚拟拟拟拟存存存存储储储储器器器器的的的的用用用用户户户户编编编编程程程程空空空空间间间间共共共共32323232个个个个页页页页面面面面，每每每每页页页页为为为为1KB1KB1KB1KB，内内内内存存存存为为为为16KB16KB16KB16KB。假假假假定定定定某某某某时时时时刻刻刻刻一一一一用用用用户户户户页页页页表表表表中中中中已已已已调调调调入入入入内内内内存存存存的的的的页页页页面面面面对对对对应应应应的的的的物物物物理理理理块块块块号号号号如下表：如下表：如下表：如下表：页号页号物理块号物理块号0 05 51 110102 24 43 37 7则逻辑地址则逻辑地址

2、0A5C0A5C（H H）所对应的物理地址为）所对应的物理地址为 ：_第1页/共80页例10A5CH0A5CH0000,100000,1010,0101,1100 10,0101,1100 B B页号为页号为2 2，对应块号为，对应块号为4 4，物理地址：物理地址：00010001，000010,0101,110010,0101,1100即：即：125CH125CH页号页号物理块物理块号号0 05 51 110102 24 43 37 7第2页/共80页例2 设设设设页页页页面面面面大大大大小小小小为为为为1K1K1K1K字字字字节节节节，作作作作业业业业的的的的0 0 0 0、1 1 1 1

3、、2 2 2 2页页页页分分分分别别别别存存存存放放放放在在在在第第第第2 2 2 2、3 3 3 3、8 8 8 8块块块块中中中中。求求求求逻逻逻逻辑辑辑辑地址地址地址地址2500250025002500对应的物理地址？对应的物理地址？对应的物理地址？对应的物理地址？则则则则逻逻逻逻辑辑辑辑地地地地址址址址2500250025002500的的的的页页页页号号号号为为为为2 2 2 2（2500/1024=22500/1024=22500/1024=22500/1024=2）页页页页内内内内地地地地址址址址为为为为452 452 452 452（2500 2500 2500 2500%102

4、4%1024%1024%1024452452452452）。）。）。）。查页表可知第查页表可知第查页表可知第查页表可知第2 2 2 2页对应的物理块号为页对应的物理块号为页对应的物理块号为页对应的物理块号为8 8 8 8。将块号将块号将块号将块号8 8 8 8与页内地址与页内地址与页内地址与页内地址452452452452拼接（拼接（拼接（拼接（810248102481024810244524524524528644864486448644）得到物理地址为）得到物理地址为）得到物理地址为）得到物理地址为8644864486448644。第3页/共80页练习题1.1.1.1.一一一一分分分分页页

5、页页存存存存储储储储管管管管理理理理系系系系统统统统中中中中逻逻逻逻辑辑辑辑地地地地址址址址长长长长度度度度为为为为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中。逻辑地址中。逻辑地址中。逻辑地址中。逻辑地

6、址0A6FH0A6FH0A6FH0A6FH对应的物理地址是多少？对应的物理地址是多少？对应的物理地址是多少？对应的物理地址是多少？逻辑地址逻辑地址逻辑地址逻辑地址0A6FH0A6FH0A6FH0A6FH的二进制表示如下：的二进制表示如下：的二进制表示如下：的二进制表示如下：页号页号页号页号 页内地址页内地址页内地址页内地址0000000000000000，10101010 10 10 10 10，0110011001100110，1111 1111 1111 1111 由由由由此此此此可可可可知知知知逻逻逻逻辑辑辑辑地地地地址址址址0A6FH0A6FH0A6FH0A6FH的的的的页页页页号号号

7、号为为为为2 2 2 2，该该该该页页页页存存存存放放放放在在在在第第第第11111111号物理块中，用十六进制表示块号为号物理块中，用十六进制表示块号为号物理块中，用十六进制表示块号为号物理块中，用十六进制表示块号为B B B B，所所所所以以以以物物物物理理理理地地地地址址址址为为为为：0010001000100010，1111111110101010，0110011001100110，1111 1111 1111 1111，即即即即2E6FH2E6FH2E6FH2E6FH。第4页/共80页练习题2.2.2.2.有有有有一一一一系系系系统统统统采采采采用用用用页页页页式式式式存存存存储储储

8、储管管管管理理理理，有有有有一一一一作作作作业业业业大大大大小小小小是是是是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

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

10、7EFH0A5CH=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因页号超过页表长度，该逻辑地址非法。第7页/共80页习题解答3 3 3 3 有有有有一一一一系系系系统统统统采采采采用用用用页页页页式式式式存存存存储储储储管管管管理理理理，有有有有一一一一作作作作业业业业大大大大小小小小是是是是8K

11、B8KB8KB8KB，页页页页大大大大小小小小为为为为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

12、 7145P P P P7145 7145 7145 7145 2048 2048 2048 2048 3 3 3 3W W W W7145 mod 20487145 mod 20487145 mod 20487145 mod 2048 1001100110011001MR=5*2048+1001MR=5*2048+1001MR=5*2048+1001MR=5*2048+1001=11241=11241=11241=11241虚地址虚地址虚地址虚地址7145714571457145的内存地址是：的内存地址是：的内存地址是：的内存地址是：11241112411124111241第8页/共80页地

13、址变换过程：地址变换过程：地址变换过程：地址变换过程：1.1.进进进进行行行行地地地地扯扯扯扯变变变变换换换换时时时时，系系系系统统统统将将将将逻逻逻逻辑辑辑辑地地地地址址址址中中中中的的的的段段段段号号号号S S S S与与与与段段段段表表表表长长长长度度度度进进进进行行行行比比比比较较较较，若若若若段段段段号号号号超超超超过过过过了了了了段段段段表表表表长度则产生长度则产生长度则产生长度则产生越界中断越界中断越界中断越界中断；2.2.否否否否则则则则根根根根据据据据段段段段表表表表始始始始址址址址和和和和段段段段号号号号计计计计算算算算出出出出该该该该段段段段对对对对应应应应段段段段表表表

14、表项项项项的的的的位位位位置置置置，从从从从中中中中读读读读出出出出该该该该段段段段在在在在内内内内存存存存的的的的起起起起始始始始地地地地址址址址，3.3.然然然然后后后后再再再再检检检检查查查查段段段段内内内内地地地地址址址址是是是是否否否否超超超超过过过过该该该该段段段段的的的的段段段段长长长长，若超过则同样发出若超过则同样发出若超过则同样发出若超过则同样发出越界中断越界中断越界中断越界中断信号信号信号信号；4.4.若若若若未未未未越越越越界界界界，则则则则将将将将该该该该段段段段的的的的起起起起始始始始地地地地址址址址与与与与段段段段内内内内位位位位移移移移相加相加相加相加，从而得到了

15、要访问的物理地址。，从而得到了要访问的物理地址。，从而得到了要访问的物理地址。，从而得到了要访问的物理地址。第9页/共80页第10页/共80页分段地址变换例 设设设设作作作作业业业业分分分分为为为为3 3 3 3段段段段，0 0 0 0、1 1 1 1、2 2 2 2段段段段长长长长度度度度分分分分别别别别为为为为1K1K1K1K、800800800800、600600600600，分分分分别别别别存存存存放放放放在在在在内内内内存存存存6K6K6K6K、4K4K4K4K、8K8K8K8K开开开开始始始始的的的的内内内内存存存存区区区区域域域域。逻逻逻逻辑辑辑辑地地地地址址址址（2 2 2 2

16、，100100100100）的的的的段段段段号号号号为为为为2 2 2 2，段段段段内内内内位位位位移移移移为为为为100100100100。其其其其物物物物理理理理地址是多少？地址是多少？地址是多少？地址是多少？查段表可知第查段表可知第查段表可知第查段表可知第2 2 2 2段在内存的起始地址段在内存的起始地址段在内存的起始地址段在内存的起始地址8K8K8K8K。将起始地址与段内位移相加，将起始地址与段内位移相加，将起始地址与段内位移相加，将起始地址与段内位移相加，8K8K8K8K1001001001008292829282928292，物理地址为，物理地址为，物理地址为，物理地址为82928

17、29282928292。第11页/共80页例子：例子：例子：例子：给定段表如下，求下列对应的内存物理地址。给定段表如下，求下列对应的内存物理地址。给定段表如下，求下列对应的内存物理地址。给定段表如下，求下列对应的内存物理地址。1 1 1 1、0,430 20,430 20,430 20,430 2、3,400 33,400 33,400 33,400 3、1,1 41,1 41,1 41,1 4、2,500 2,500 2,500 2,500段号段号段号段号段首址段首址段首址段首址段长段长段长段长0 0 0 02192192192196006006006001 1 1 123002300230

18、02300141414142 2 2 2909090901001001001003 3 3 31327132713271327580580580580第12页/共80页在一个段式存储管理系统中，其段表如左表所示，求右表逻辑地址对应的物理地址。第13页/共80页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,

19、500非法。(4)由于第3段的内存始址为1350，段长为590，故逻辑地址3,400是合法地址。逻辑地址3,400对应的物理地址为13504001750。第14页/共80页第15页/共80页二、磁盘的类型二、磁盘的类型二、磁盘的类型二、磁盘的类型 硬盘和软盘、单片盘和多片盘、固定磁头和活动硬盘和软盘、单片盘和多片盘、固定磁头和活动硬盘和软盘、单片盘和多片盘、固定磁头和活动硬盘和软盘、单片盘和多片盘、固定磁头和活动磁头。磁头。磁头。磁头。1.1.1.1.固定头磁盘：固定头磁盘：固定头磁盘：固定头磁盘：每个磁道上有一个磁头，并行读写，速度快每个磁道上有一个磁头，并行读写，速度快每个磁道上有一个磁头

20、，并行读写，速度快每个磁道上有一个磁头，并行读写，速度快 2.2.2.2.移动头磁盘：移动头磁盘：移动头磁盘：移动头磁盘：每个盘面仅有一个磁头，要读写数据需要移动磁头每个盘面仅有一个磁头，要读写数据需要移动磁头每个盘面仅有一个磁头，要读写数据需要移动磁头每个盘面仅有一个磁头，要读写数据需要移动磁头寻道。结构简单、寻道。结构简单、寻道。结构简单、寻道。结构简单、I/OI/OI/OI/O速度慢速度慢速度慢速度慢 。温彻斯特磁盘简称温盘，是一种可移动磁头固定盘片的磁盘存储器，温彻斯特磁盘简称温盘，是一种可移动磁头固定盘片的磁盘存储器，温彻斯特磁盘简称温盘，是一种可移动磁头固定盘片的磁盘存储器，温彻斯

21、特磁盘简称温盘，是一种可移动磁头固定盘片的磁盘存储器，它是目前应用最广，最有代表性的硬磁盘存储器。它是目前应用最广，最有代表性的硬磁盘存储器。它是目前应用最广，最有代表性的硬磁盘存储器。它是目前应用最广，最有代表性的硬磁盘存储器。第16页/共80页三、磁盘访问时间：三、磁盘访问时间：三、磁盘访问时间：三、磁盘访问时间：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：磁盘启动时间。：磁盘启动时间。：磁盘启动时间。：磁

22、盘启动时间。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：每道上的字节数：每道上的字节数：每道上的字节数：每道上的字节数

23、访问时间：访问时间：访问时间：访问时间：Ta=Ts+Tr+TtTa=Ts+Tr+TtTa=Ts+Tr+TtTa=Ts+Tr+Tt可见，由于特定磁盘，只有集中放数据，集中读写可见，由于特定磁盘，只有集中放数据，集中读写可见，由于特定磁盘，只有集中放数据，集中读写可见，由于特定磁盘，只有集中放数据，集中读写（读写字节多）才能更好提高传输效率。（读写字节多）才能更好提高传输效率。（读写字节多）才能更好提高传输效率。（读写字节多）才能更好提高传输效率。第17页/共80页 磁盘是典型的共享设备。在用户处理的信息量越来磁盘是典型的共享设备。在用户处理的信息量越来磁盘是典型的共享设备。在用户处理的信息量越来

24、磁盘是典型的共享设备。在用户处理的信息量越来越大的情况下，对磁盘等共享设备的访问也越来越越大的情况下，对磁盘等共享设备的访问也越来越越大的情况下，对磁盘等共享设备的访问也越来越越大的情况下，对磁盘等共享设备的访问也越来越频繁，因而访问调度是否得当直接影响到系统的效频繁，因而访问调度是否得当直接影响到系统的效频繁，因而访问调度是否得当直接影响到系统的效频繁，因而访问调度是否得当直接影响到系统的效率。率。率。率。磁盘调度的目标：减少寻道时间磁盘调度的目标：减少寻道时间磁盘调度的目标：减少寻道时间磁盘调度的目标：减少寻道时间有如下五种磁盘调度算法：有如下五种磁盘调度算法：有如下五种磁盘调度算法：有如

25、下五种磁盘调度算法：一、一、一、一、FCFSFCFSFCFSFCFS（Fisrt Come First SecondFisrt Come First SecondFisrt Come First SecondFisrt Come First Second）二、二、二、二、SSTFSSTFSSTFSSTF（最短寻道优先）（最短寻道优先）（最短寻道优先）（最短寻道优先）三、扫描算法。三、扫描算法。三、扫描算法。三、扫描算法。四、循环扫描四、循环扫描四、循环扫描四、循环扫描CSCANCSCANCSCANCSCAN 五、五、五、五、N N N NStepStepStepStepSCANSCANSCAN

26、SCAN和和和和FSCANFSCANFSCANFSCAN算法。算法。算法。算法。第18页/共80页图 5-23 FCFS调度算法1.1.先来先服务先来先服务FCFS(First-Come,First Served)FCFS(First-Come,First Served)n仅用于请仅用于请求磁盘求磁盘I/OI/O的进的进程数目较程数目较少的场合。少的场合。第19页/共80页图 5-24 SSTF调度算法 2.2.最短寻道时间优先最短寻道时间优先SSTF(Shortest Seek Time SSTF(Shortest Seek Time First)First)n n要求访问的磁道与当要求访问

27、的磁道与当要求访问的磁道与当要求访问的磁道与当前磁头距离最近，使前磁头距离最近，使前磁头距离最近，使前磁头距离最近，使每次的寻道时间最短每次的寻道时间最短每次的寻道时间最短每次的寻道时间最短第20页/共80页vSSTFSSTFSSTFSSTF算算算算法法法法虽虽虽虽然然然然能能能能获获获获得得得得较较较较好好好好的的的的寻寻寻寻道道道道性性性性能能能能，却却却却可可可可能能能能导致某个进程发生导致某个进程发生导致某个进程发生导致某个进程发生“饥饿饥饿饥饿饥饿”(Starvation)(Starvation)(Starvation)(Starvation)现象。现象。现象。现象。vScanSca

28、nScanScan算法该算法不仅考虑到欲访问的磁道与当算法该算法不仅考虑到欲访问的磁道与当算法该算法不仅考虑到欲访问的磁道与当算法该算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑磁头当前的移动方前磁道间的距离，更优先考虑磁头当前的移动方前磁道间的距离，更优先考虑磁头当前的移动方前磁道间的距离，更优先考虑磁头当前的移动方向。向。向。向。v其原理是访问的下一个对象应是同方向的，且其原理是访问的下一个对象应是同方向的，且其原理是访问的下一个对象应是同方向的，且其原理是访问的下一个对象应是同方向的，且又距离最近的。一般自里向外访问，直至再无更又距离最近的。一般自里向外访问，直至再无更又距离最

29、近的。一般自里向外访问，直至再无更又距离最近的。一般自里向外访问，直至再无更外的磁道需要访问，才将磁臂换向自外向里，往外的磁道需要访问，才将磁臂换向自外向里，往外的磁道需要访问，才将磁臂换向自外向里，往外的磁道需要访问，才将磁臂换向自外向里，往返反复。这种算法又称为返反复。这种算法又称为返反复。这种算法又称为返反复。这种算法又称为“电梯算法电梯算法电梯算法电梯算法”3.3.扫描扫描(SCAN)(SCAN)算法算法第21页/共80页SCAN调度算法100道开始，增加方向道开始，增加方向被访问下一个磁道被访问下一个磁道移动距离移动距离15050160101842490945832553391638

30、11820平均寻道长度：平均寻道长度：27.8第22页/共80页CscanCscanCscanCscan算法规定磁头单项移动，进行循环扫描。一算法规定磁头单项移动，进行循环扫描。一算法规定磁头单项移动，进行循环扫描。一算法规定磁头单项移动，进行循环扫描。一个方向读完，不是象个方向读完，不是象个方向读完，不是象个方向读完，不是象SCANSCANSCANSCAN那样回头，而是循环。那样回头，而是循环。那样回头，而是循环。那样回头，而是循环。n n访问时间：访问时间：访问时间：访问时间：2T2T2T2TT+SmaxT+SmaxT+SmaxT+Smaxn nT T T T是从外向里或从里向外单向是从外

31、向里或从里向外单向是从外向里或从里向外单向是从外向里或从里向外单向扫描完要访问的磁道扫描完要访问的磁道扫描完要访问的磁道扫描完要访问的磁道的寻道时间的寻道时间的寻道时间的寻道时间。n n而而而而SmaxSmaxSmaxSmax是将磁头从最外面被访问的磁道是将磁头从最外面被访问的磁道是将磁头从最外面被访问的磁道是将磁头从最外面被访问的磁道直接移到直接移到直接移到直接移到最最最最里面欲访问的磁道的寻道时间。里面欲访问的磁道的寻道时间。里面欲访问的磁道的寻道时间。里面欲访问的磁道的寻道时间。4.4.循环扫描循环扫描(CSCAN)(CSCAN)算法算法第23页/共80页CSCAN调度算法100道开始，

32、增加方向道开始，增加方向被访问的下一个磁道被访问的下一个磁道移动距离移动距离15050160101842418166382039155165839032平均寻道长度：平均寻道长度：27.5第24页/共80页若某磁盘共有200个柱面，其编号为0199，假设已完成96号柱面的访问请求，还有若干个请求者在等待服务，它们依次要访问的柱面号为：175，52，157，36，159、106，l08，72，分别用先来先服务调度算法、最短寻道时间调度算法、电梯调度算法和单向扫描调度算法（向序号增加的方向移动）来确定实际服务的次序，并计算上述两种算法下移动臂需移动的距离。第25页/共80页(1)先来先服务调度算法

33、：实际服务的次序：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个柱面的距离。第26页/共80页(1

34、)电梯调度算法：实际服务的次序：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个柱面的距离。第27页/共80页二、二

35、、二、二、FIFOFIFOFIFOFIFO 淘汰淘汰淘汰淘汰最先进入内存的页面最先进入内存的页面最先进入内存的页面最先进入内存的页面，即选择在内存中驻留时，即选择在内存中驻留时，即选择在内存中驻留时，即选择在内存中驻留时间最久的页面予以淘汰。间最久的页面予以淘汰。间最久的页面予以淘汰。间最久的页面予以淘汰。出发点：最早调入主存中的页面不再使用的可能性出发点：最早调入主存中的页面不再使用的可能性出发点：最早调入主存中的页面不再使用的可能性出发点：最早调入主存中的页面不再使用的可能性越大，应该最先淘汰。算法简单对具有按线性顺序越大，应该最先淘汰。算法简单对具有按线性顺序越大，应该最先淘汰。算法简单

36、对具有按线性顺序越大，应该最先淘汰。算法简单对具有按线性顺序访问的程序比较合适，而对其它情况效率不高访问的程序比较合适，而对其它情况效率不高访问的程序比较合适，而对其它情况效率不高访问的程序比较合适，而对其它情况效率不高第28页/共80页进程进程进程进程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

37、 3 3 3个页面，则缺页情况如下：个页面，则缺页情况如下：个页面，则缺页情况如下：个页面，则缺页情况如下：12121212次访问中有缺页次访问中有缺页次访问中有缺页次访问中有缺页9 9 9 9次；次；次；次；第29页/共80页如果在内存中分配如果在内存中分配4 4个页面，则缺页情况如下：个页面，则缺页情况如下：1212次访问中有缺页次访问中有缺页1010次；次；BeladyBelady现象的现象的原因原因：FIFOFIFO算法的算法的置换特征置换特征与进与进程程访问内存的动态特征访问内存的动态特征是是矛盾矛盾的，即被置换的页的，即被置换的页面并不是进程不会访问的。面并不是进程不会访问的。第3

38、0页/共80页习题1 1 1 1某进程执行时的页面走向为某进程执行时的页面走向为某进程执行时的页面走向为某进程执行时的页面走向为1 2 3 4 1 2 5 1 2 3 4 1 2 5 1 2 3 4 1 2 5 1 2 3 4 1 2 5 1 2 3 4 51 2 3 4 51 2 3 4 51 2 3 4 5，分别画出其分配物理块为，分别画出其分配物理块为，分别画出其分配物理块为，分别画出其分配物理块为3 3 3 3的最佳的最佳的最佳的最佳置换算法的置换图。置换算法的置换图。置换算法的置换图。置换算法的置换图。2 2 2 2某进程执行时的页面走向为某进程执行时的页面走向为某进程执行时的页面走

39、向为某进程执行时的页面走向为1 2 3 4 1 2 5 1 2 3 4 1 2 5 1 2 3 4 1 2 5 1 2 3 4 1 2 5 1 2 3 4 51 2 3 4 51 2 3 4 51 2 3 4 5，分别画出其分配物理块为，分别画出其分配物理块为，分别画出其分配物理块为，分别画出其分配物理块为3 3 3 3和和和和4 4 4 4的的的的FIFOFIFOFIFOFIFO算法的置换图。算法的置换图。算法的置换图。算法的置换图。3 3 3 3在请求分页管理系统中，一个作业要依次访在请求分页管理系统中，一个作业要依次访在请求分页管理系统中，一个作业要依次访在请求分页管理系统中，一个作业要

40、依次访问如下页面：问如下页面：问如下页面：问如下页面：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.第

41、31页/共80页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。若用最佳置换算法，。若用最佳置换算法，。若用最佳置换算法，。若用最佳置换算

42、法，先进先出，先进先出，先进先出，先进先出，LRULRULRULRU置换算法求出访问过程中发生置换算法求出访问过程中发生置换算法求出访问过程中发生置换算法求出访问过程中发生的缺页次数及缺页率。的缺页次数及缺页率。的缺页次数及缺页率。的缺页次数及缺页率。第32页/共80页请求分页存储管理方式中，假定系统为某进程分配了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%第38页/共80页请求分页存储

43、管理方式中，假设分配给某进程的页框数为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%第39页/共80页二、银行家算法二、银行家算法 避避 免免 死死 锁锁 算算 法法 中中 最最 有有 代代 表表 性性 的的 算算 法法 是是Dijkstra E.W Dijkstra E.W 于于19681968年提出的银行家算法：年提出的银行家算法：该该算算法法需需要要检检查查申申请请者者对对资资源源的的最最大大需

44、需求求量量，如如果果系系统统现现存存的的各各类类资资源源可可以以满满足足申申请请者者的的请请求，就满足申请者的请求。求，就满足申请者的请求。这这样样申申请请者者就就可可很很快快完完成成其其计计算算，然然后后释释放放它它占占用用的的资资源源，从从而而保保证证了了系系统统中中的的所所有有进进程程都能完成，所以可避免死锁的发生。都能完成，所以可避免死锁的发生。第40页/共80页 1 1数据结构数据结构可利用资源向量可利用资源向量availableavailable 其初值是系统中该类资源的最大可用数目，其值其初值是系统中该类资源的最大可用数目，其值将随着该类资源的分配与回收而动态改变。将随着该类资源

45、的分配与回收而动态改变。availablej=k:availablej=k:系统现有系统现有RjRj类资源类资源k k个；个；最大需求矩阵最大需求矩阵MaxMax 是一个是一个nmnm的矩阵，定义了系统中的的矩阵，定义了系统中的n n个进程中个进程中的每一个进程对的每一个进程对m m类资源的最大需求量。类资源的最大需求量。maxi,j=k:maxi,j=k:进程进程i i需要需要RjRj的最大数的最大数k k个；个；第41页/共80页分配矩阵分配矩阵AllocationAllocation 是一个是一个nmnm的矩阵，定义了系统中每一类资源的数量。的矩阵，定义了系统中每一类资源的数量。allo

46、cationi,j=k:allocationi,j=k:进程进程i i已得到已得到RjRj类资源类资源k k个；个；需求矩阵需求矩阵NeedNeed 是一个是一个nmnm的矩阵，用以表示每一个进程尚需的各类资源数。的矩阵，用以表示每一个进程尚需的各类资源数。needi,j=k:needi,j=k:进程进程i i还需还需RjRj类资源类资源k k个，方能完成任务。个，方能完成任务。有：有：needi,j=maxi,jneedi,j=maxi,jallocationi,jallocationi,jrequestrequesti i进程进程i i请求资源数请求资源数第42页/共80页2 2银行家算法

47、银行家算法 reqi=needierrorreqiNeedi,j,出出错处理。错处理。否则，转向下一步。否则，转向下一步。若若RequestijAvailablei,j出出错处理。错处理。否则否则,转向下一步。转向下一步。N NN NN NY YY Y第43页/共80页avail=avail-reqialloci=alloci+reqineedi=needi-reqifinishi=.F.needi=workwork=work+allocifinishi=.T.系统试着把资源分给进程系统试着把资源分给进程Pi，并修改下列数值。，并修改下列数值。Availj=Availj-Reqi j;Allo

48、i,jAlloi,j+Reqij;Needi,j=Needi,jReqij;执行安全性算法执行安全性算法,检查这次资源分配后，系统检查这次资源分配后，系统是否处于安全状态是否处于安全状态.如果安全，则正式将资源分配给如果安全，则正式将资源分配给Pi，否则恢复原，否则恢复原来的资源分配状态，然进程来的资源分配状态，然进程Pi等待。等待。第44页/共80页安全性算法安全性算法1.1.设置两个工作向量设置两个工作向量设置一个临时向量设置一个临时向量workwork：表示系统可提供给进程继续运行的资源的集合。安：表示系统可提供给进程继续运行的资源的集合。安全性算法刚开始执行时，全性算法刚开始执行时，w

49、ork:work:AvailableAvailable。设置一个数组设置一个数组finishifinishi：表示进程：表示进程i i能否顺序完成。当能否顺序完成。当finishifinishiTrueTrue，表示进程表示进程PiPi可以获得其所需的全部资源，而顺利执行完成。可以获得其所需的全部资源，而顺利执行完成。第45页/共80页安全性算法安全性算法2.2.从进程集合中找到一个能满足下述条件的进程：从进程集合中找到一个能满足下述条件的进程：A Finishi=false;A Finishi=false;B B Needi,j workjNeedi,j workj；若找到，执行若找到，执行

50、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,则系统处于安则系统处于安全状态，否则处于不安全状态。全状态，否则处于不安全状态。第46页/共80页4 4实例实例 Max A B C Alloc