第5章(2)虚存管理技术+

1、操作系统讲义之五第五（第五（2）章）章 虚存管理技术虚存管理技术5.1 基本概念基本概念5.2 页式管理页式管理 补充：多级页表补充：多级页表 十六进制地址转换十六进制地址转换 时钟时钟( (Clock)置换算法置换算法5.3 段式管理段式管理5.4 段页式管理段页式管理5.5 局部性原理和抖动问题局部性原理和抖动问题操作系统讲义之五v前面所述的各种管理技术统称为实存管理技术，其特前面所述的各种管理技术统称为实存管理技术，其特点是在作业运行时，必须将整个作业的逻辑地址空间点是在作业运行时，必须将整个作业的逻辑地址空间全部装入主存全部装入主存(除覆盖外除覆盖外)，当作业尺寸大于主存可用空，当作业

2、尺寸大于主存可用空间时，该作业就无法运行。间时，该作业就无法运行。v同实存相对的另一类存储管理技术称为虚存管理技术同实存相对的另一类存储管理技术称为虚存管理技术。同实存管理的主要区别是：同实存管理的主要区别是：不用将整个作业装入主存不用将整个作业装入主存就可以投入运行。就可以投入运行。v引入如下一些概念引入如下一些概念： 1. 虚拟存储器：是指一种实际上并不存在的虚假的存储虚拟存储器：是指一种实际上并不存在的虚假的存储器。器。 2. 虚拟地址：把一个运行进程访问的地址称为虚拟地址。虚拟地址：把一个运行进程访问的地址称为虚拟地址。5.1 基本概念基本概念操作系统讲义之五 3. 实地址：把处理机可

3、直接访问的地址称为实地址。实地址：把处理机可直接访问的地址称为实地址。相应的有：虚地址空间、实地址空间的概念。相应的有：虚地址空间、实地址空间的概念。 问题：问题： v把把虚地址空间和实地址空间分开后，这样虚地址空虚地址空间和实地址空间分开后，这样虚地址空间可以远远大于实地址空间，亦即作业的大小可以间可以远远大于实地址空间，亦即作业的大小可以远远大于主存空间的大小。远远大于主存空间的大小。v另一个相关问题是：作业运行时，其整个虚地址空另一个相关问题是：作业运行时，其整个虚地址空间间(逻辑地址空间逻辑地址空间)是否必须全部装入主存？如果必是否必须全部装入主存？如果必须的话，那么虚地址空间仍然不能

4、大于实地址空间。须的话，那么虚地址空间仍然不能大于实地址空间。操作系统讲义之五v一个程序的某次运行，常有些部分是不用的一个程序的某次运行，常有些部分是不用的(如：无错如：无错误发生时就不会调用出错处理程序误发生时就不会调用出错处理程序)。所以，只让最近。所以，只让最近要用到的那部分程序和数据装入主存，以后用到哪部分要用到的那部分程序和数据装入主存，以后用到哪部分再把哪部分调入，而把不用部分调出再把哪部分调入，而把不用部分调出(暂存外存暂存外存)。v为了完成上述功能，操作系统应负责下面三个方面的任为了完成上述功能，操作系统应负责下面三个方面的任务：务： （1）把哪部分调入主存；）把哪部分调入主存

5、； （2）放在主存什么位置；）放在主存什么位置； （3）主存空间不足时，把哪部分淘汰出去。）主存空间不足时，把哪部分淘汰出去。v本章主要介绍目前广泛使用的三种虚存管理技术：本章主要介绍目前广泛使用的三种虚存管理技术： 页式管理页式管理(静态页式管理和动态页式管理静态页式管理和动态页式管理) 段式管理段式管理 段页式存储管理段页式存储管理操作系统讲义之五5.2 页式管理页式管理 实现原理实现原理 1. 等分主存等分主存 把主存划分成大小相同的存储块，称为页面把主存划分成大小相同的存储块，称为页面(或或块块)，并给各页面从零开始编上序号：，并给各页面从零开始编上序号：0，1，2，。 2. 等分作业

6、的逻辑地址空间等分作业的逻辑地址空间 将程序的逻辑地址空间也划分若干个与页面大小将程序的逻辑地址空间也划分若干个与页面大小相同的块相同的块,称为页。也编上序号称为页。也编上序号0，1，2，。 主存分配原则主存分配原则 系统以系统以页面页面(块块)为单位把主存分给作业，每页对为单位把主存分给作业，每页对应内存中一个页面，这些页面可以是不相临的或应内存中一个页面，这些页面可以是不相临的或连续的。连续的。 操作系统讲义之五 页式存储管理根据进程的页是否一次全部装入页式存储管理根据进程的页是否一次全部装入还是部分装入而分为：还是部分装入而分为：静态页式管理实存管理静态页式管理实存管理动态页式管理虚存管

7、理动态页式管理虚存管理操作系统讲义之五一、静态页式管理一、静态页式管理v基本原理：要求程序执行前，基本原理：要求程序执行前，分配其所需的所分配其所需的所有页面，这些页面可以是不相邻的有页面，这些页面可以是不相邻的。这意味着。这意味着内存中有足够的空闲页面才能执行某个程序。内存中有足够的空闲页面才能执行某个程序。需要需要CPU的硬件支持的硬件支持。 下面图显示静态页式内存使用情况：下面图显示静态页式内存使用情况：操作系统讲义之五静态页式管理主存分配情况静态页式管理主存分配情况FrameNumber0123456789101112131401234567891011121314A.0A.1A.2A

8、.3 01234567891011121314A.0A.1A.2A.3B.0B.1B.2操作系统讲义之五在页式储存管理中，是以页面为单位分给用户使在页式储存管理中，是以页面为单位分给用户使用，为了记录主存的使用情况，系统为用，为了记录主存的使用情况，系统为每个进程每个进程建立一个页表建立一个页表，最简单的页表包括如下信息：，最简单的页表包括如下信息： （1）页号：作业的各页的页号；）页号：作业的各页的页号； （2）块号：指该页装入主存的第几）块号：指该页装入主存的第几 个页面上。个页面上。1. 页表与页表地址寄存器页表与页表地址寄存器操作系统讲义之五页的大小带来的影响页的大小带来的影响页小：页

9、小：内碎片小，页表长，管理复杂，存内碎片小，页表长，管理复杂，存储信息少，可能频繁调页；储信息少，可能频繁调页；页大：页大：页表短，管理开销小，交换时对外页表短，管理开销小，交换时对外存存I/O效率高，但内碎片大，会多浪费内效率高，但内碎片大，会多浪费内存存操作系统讲义之五LOAD 1LOAD 1，11201120 ADD 1ADD 1，241024100 010010010210210001000680268021120112020002000400040006251625124102410300030000 0页页1 1页页2 2页页3 3页页0 010001000200020003000

10、3000页号页号 块号块号0 30 31 91 92 -2 -3 -3 -0 20 2页号页号 块号块号1 41 42 72 70 0100010002000200030003000LOAD 1LOAD 1，11201120 ADD 1ADD 1，24102410310031003102310240004000500050006000600070007000100001000090009000800080002 2块块3 3块块4 4块块5 5块块6 6块块7 7块块8 8块块9 9块块0 0块块1 1块块9120912068026802操作系统操作系统作业作业1 1作业作业2 2页表页表操作

11、系统讲义之五2. 静态页式管理的特点静态页式管理的特点优点：优点： 没有外碎片，每个内碎片不超过页的大小没有外碎片，每个内碎片不超过页的大小 一个程序不必连续存放。一个程序不必连续存放。 由于页的大小相等，内存的分配、回收简单，由于页的大小相等，内存的分配、回收简单，易于管理。易于管理。缺点：缺点：程序要求全部装入内存才能执行。程序要求全部装入内存才能执行。操作系统讲义之五3. 逻辑地址的表示逻辑地址的表示v用户的逻辑地址一般是从基址用户的逻辑地址一般是从基址“0”开始连续开始连续编址。在分页系统中，每个虚地址编址。在分页系统中，每个虚地址(相对地址相对地址)用一个数对用一个数对(p，d)来表

12、示，其中来表示，其中p表示页号，表示页号，d表示页内地址表示页内地址(页内偏移量页内偏移量)。v令令A是一个虚地址，页面大小为是一个虚地址，页面大小为L,则：则： p=INTA/L，d=AmodL 例如：设页面大小例如：设页面大小 L=1000字节字节, A=3456,则则: p=INT3456/1000=3 L=3456mod1000=456 操作系统讲义之五v在内存中的表示：在内存中的表示： 若页面大小为若页面大小为2的幂，逻辑地址转换为页号的幂，逻辑地址转换为页号p和位移量和位移量d就非就非常简单常简单(由地址变换机构自动完成由地址变换机构自动完成)。页号页号页内地址页内地址( (页内偏

13、移量页内偏移量) )p pd d例如：一个页长为例如：一个页长为1 K，拥有，拥有64页的虚拟空间地址结构如图下页的虚拟空间地址结构如图下图所示。图所示。15 10 9 0pd26=64(页页)，页的长度，页的长度= 210=1024(字节字节)=1K操作系统讲义之五举例：举例：采用页式存储管理的系统中，若逻辑地址中的页采用页式存储管理的系统中，若逻辑地址中的页号用号用8位表示，页内地址用位表示，页内地址用16位表示。问：位表示。问：（1）用户程序的最大长度是多少兆字节？）用户程序的最大长度是多少兆字节？（2）主存分块为多少）主存分块为多少K字节？（字节？（KB） 解：逻辑地址中的页号用解：逻

14、辑地址中的页号用8位表示，就是说逻辑地址位表示，就是说逻辑地址中最大页数是中最大页数是28=256(页页)；页内地址用；页内地址用16位表示，即位表示，即一个一个(逻辑逻辑)页大小为页大小为216=65536(字节字节) / 1024=64K。（1）用户程序的最大长度就是）用户程序的最大长度就是256页全部使用的情况页全部使用的情况了，即了，即 256 * 64K=16384K =16384K/1024=16MB。（2）主存分块大小应该和逻辑页大小相同，即页面）主存分块大小应该和逻辑页大小相同，即页面=64KB操作系统讲义之五4. 分页管理中的地址转换分页管理中的地址转换 静态页式管理的另一个

15、关键问题是地址变换。静态页式管理的另一个关键问题是地址变换。即怎样由页号和页内相对地址变换到内存物即怎样由页号和页内相对地址变换到内存物理地址的问题。理地址的问题。在页式管理中，地址变换的在页式管理中，地址变换的速度也是设计地址变换机构时必须考虑的问速度也是设计地址变换机构时必须考虑的问题之一。题之一。v现以上图的指令现以上图的指令 LOAD 1, 1120 为例说明分页为例说明分页管理中的地址变换过程。管理中的地址变换过程。v当当CPU执行执行LOAD1, 1120时，该指令给出的时，该指令给出的虚地址为虚地址为1120，首先由地址变换机构自动将，首先由地址变换机构自动将该地址分为页号该地址

16、分为页号p=1和位移量和位移量d=120，其转换，其转换过程如下图所示：过程如下图所示：操作系统讲义之五页号页号 块号块号0 30 31 91 92 -2 -3 -3 -页表长度页表长度 页表起址页表起址 1 120 1 1209 1209 1209 91000+1201000+120912091206802680231003100LOAD 1,120LOAD 1,120页式管理地址转换示意图页式管理地址转换示意图p pd d控制寄存器控制寄存器内存内存地址越界比较地址越界比较操作系统讲义之五 注：注： 实际的地址转换工作是计算机系统内部采用硬件实际的地址转换工作是计算机系统内部采用硬件机制完

17、成的，即由机制完成的，即由地址转换机构地址转换机构MMU(Memory Management Unit)自动完成的，自动完成的，MMU是内存管是内存管理单元的意思，它是由中央处理器理单元的意思，它是由中央处理器CPU用来管用来管理虚拟存储器、物理存储器的控制线路，同时理虚拟存储器、物理存储器的控制线路，同时也负责虚地址映射到物理地址的映射。也负责虚地址映射到物理地址的映射。操作系统讲义之五1. 虚地址以十进制数给出虚地址以十进制数给出v页号：页号： PINT(虚地址虚地址 / 页大小页大小) 取整数取整数部分部分v位移量：位移量： W虚地址虚地址MOD 页大小页大小 或或 W虚地址虚地址 %

18、页大小页大小 取余数取余数v根据题意产生页表；根据题意产生页表；v以页号查页表，得到对应页装入内存的块号以页号查页表，得到对应页装入内存的块号v计算机公式内存地址块号计算机公式内存地址块号页大小位移量页大小位移量页式地址映射小结页式地址映射小结操作系统讲义之五2. 虚地址虚地址(逻辑地址、相对地址逻辑地址、相对地址)以十六进制以十六进制、八进、八进制、二进制的形式给出制、二进制的形式给出v将虚地址转换成二进制的数；将虚地址转换成二进制的数；v按页的大小分离出按页的大小分离出页号页号和和位移量位移量(高位部分是页高位部分是页号，低位部分是位移量号，低位部分是位移量)；v将低位部分将低位部分位移量

19、直接复制到位移量直接复制到内存地址寄内存地址寄存器存器的低位部分；的低位部分；v根据页号查页表，得到该页装入内存的物理块根据页号查页表，得到该页装入内存的物理块号，号，并将块号转换成二进制数填入地址寄存器并将块号转换成二进制数填入地址寄存器的高位部分的高位部分，从而形成内存地址。从而形成内存地址。操作系统讲义之五十六进制十六进制(参考参考)：0000 = 00001 = 10010 = 20011 = 30100 = 40101 = 50110 = 60111 = 71000 = 8 1001 = 91010 = A1011 = B1100 = C1101 = D1110 = E1111 =

20、F记忆：记忆：210=1K 211=2K 212=4K 213=8K 214=16K 215=32K 216=64K .操作系统讲义之五例例1：有一系统采用页式存储管理，有一作业大小：有一系统采用页式存储管理，有一作业大小是是8KB，页大小为，页大小为2KB，依次装入内存的第，依次装入内存的第7、9、10、5块，试将虚地址块，试将虚地址7145，3412转换成内存地转换成内存地址。址。解答解答: （1）虚地址）虚地址 7145PINT(7145/2048) 3 (对应对应物理块物理块5)W7145 mod 2048 1001MR=5*2048+1001=11241虚地址虚地址7145的内存地址

21、是：的内存地址是：11241操作系统讲义之五（2）虚地址）虚地址 3412 PINT(3412/2048) 1 (对应物对应物理块理块9) W3412mod 2048 1364 MR=9*2048+1364=19796 虚地址虚地址3412的内存地址是：的内存地址是：19796操作系统讲义之五例例2：某虚拟存储器的用户空间共：某虚拟存储器的用户空间共32个页面个页面，每页每页1KB，主存，主存16KB，假设某时刻系统为用，假设某时刻系统为用户的户的0、1、2、3页分配的物理块为页分配的物理块为5、10、4、7，而该用户作业的长度为而该用户作业的长度为6页页，试将十六进，试将十六进制的虚地址制的

22、虚地址0A5C、103C、1A5C转换成物理转换成物理地址。地址。解答：解答： 用户空间用户空间(逻辑地址空间逻辑地址空间)为为32*1KB=32KB，因因 215=32KB，故逻辑地址编码为，故逻辑地址编码为15位，页面位，页面为为1KB(210KB)，所以页号用，所以页号用5位，页内地址位，页内地址用用10位。位。操作系统讲义之五（1） 0A5C 0A5C=000 1010 0101 1100 P=2，W= 10 0101 1100 MR = 001 0010 0101 1100 = 125CH（2） 103C 103C=001 0000 0011 1100 P=4, W=00 0011

23、1100 页号为页号为4，合法，但该页未装入主存，故产生，合法，但该页未装入主存，故产生缺页中断；缺页中断；（3） 1A5C 1A5C=001 1010 0101 1100 P=6，因，因该用户该用户作业的长度为作业的长度为6页页(05)，故产生地址越界中断。，故产生地址越界中断。操作系统讲义之五一道考研题一道考研题 西北工业大学（西北工业大学（20022002）v设有设有8页的逻辑空间，每页有页的逻辑空间，每页有1024字节字节(1KB)，它们被映射到，它们被映射到32块的物理存储区中，那么逻辑地址的有效位是（）位，物理地块的物理存储区中，那么逻辑地址的有效位是（）位，物理地址至少是（）位。

24、址至少是（）位。分析：分析：v逻辑地址有两个部分组成：页号和页内偏移地址。逻辑空间有逻辑地址有两个部分组成：页号和页内偏移地址。逻辑空间有8 （23）页，说明页号需要）页，说明页号需要3位二进制位编码，而每页有位二进制位编码，而每页有1024（210）字节，说明页内偏移地址需要）字节，说明页内偏移地址需要10位二进制位编码，因此位二进制位编码，因此逻辑地址的有效位为逻辑地址的有效位为3+10=13位。位。v因为物理地址与逻辑地址的页面大小相同，而物理存储块为因为物理地址与逻辑地址的页面大小相同，而物理存储块为32（25）占）占5位，所以物理地址至少为位，所以物理地址至少为5+10=15位位内存

25、有内存有32个物理块，物理块大小与逻辑块大小相同，故物理地址个物理块，物理块大小与逻辑块大小相同，故物理地址空间为空间为32*1KB=32KB。因为。因为215=32768B=32768/1024=32KB，故，故物理地址至少为物理地址至少为15位。位。操作系统讲义之五4. 4. 联想寄存器和快表联想寄存器和快表v联想寄存器：可按内容联想寄存器：可按内容并行查找并行查找的快速寄存器。的快速寄存器。比内存贵、容量小。比内存贵、容量小。v引入原因：页表驻留内存，执行访内指令要先引入原因：页表驻留内存，执行访内指令要先到内存查页表，进行地址转换后才能进行访内到内存查页表，进行地址转换后才能进行访内操

26、作，操作，因此执行一条指令至少要访问内存两次因此执行一条指令至少要访问内存两次v为提高速度，将内存页表为提高速度，将内存页表( (也称慢表也称慢表) )中一部分中一部分经常使用页的页号和页面号等内容放在联想寄经常使用页的页号和页面号等内容放在联想寄存器中存器中( (称为快表称为快表) )。操作系统讲义之五具有快表的地址转换：具有快表的地址转换：v每次访问主存时，首先查找每次访问主存时，首先查找快表快表，若找到所需，若找到所需的页，则快速形成物理地址。的页，则快速形成物理地址。v否则从否则从页表页表(慢表慢表)中查找后形成物理地址，同时中查找后形成物理地址，同时把该页写入快表中。如果设计得当，快

27、表的命把该页写入快表中。如果设计得当，快表的命中率可以很高。中率可以很高。操作系统讲义之五具有快表的地址变换机构具有快表的地址变换机构页表寄存器页表寄存器页表始址页表始址页表长度页表长度页号页号页内地址页内地址逻辑地址逻辑地址L L越界中断越界中断块号块号b页表页表页号页号页号页号输输入入寄寄存存器器块号块号bb快表快表d物理地址物理地址操作系统讲义之五这就意味着，在为一个进程分配内存空间时，除了给进程本身这就意味着，在为一个进程分配内存空间时，除了给进程本身分配内存空间外，还需要另外提供分配内存空间外，还需要另外提供4MB的一块连续内存空间存的一块连续内存空间存放对应的页表。因为每个进程都要

28、有自己的页表，这就需要更放对应的页表。因为每个进程都要有自己的页表，这就需要更大存储空间来存放页表。大存储空间来存放页表。5. 两级和多级页表两级和多级页表-补充补充 CPU具有具有32位地址时，使用位地址时，使用232逻辑地址空间的分页系统，规定逻辑地址空间的分页系统，规定页面页面4KB时，时，每个进程页表的表项最多有每个进程页表的表项最多有1M个，即页表最多个，即页表最多有有1M行行（？）（？），若每个页表项占用，若每个页表项占用4个字节，则每个进程需要个字节，则每个进程需要占用占用4MB连续内存空间存放页表连续内存空间存放页表(即需要即需要1024个连续的内存物个连续的内存物理块理块)。

29、 解释：解释：页面大小为页面大小为4KB(212KB)，故页内编址，故页内编址12位，页号编址为位，页号编址为: 32 12 = 20位，位，220=1048576(个个)=1048576/1024=1024K(个个)=1M(个个), 所以所以共有共有1M个页表项。个页表项。每个页表项占每个页表项占4个字节，故：个字节，故：1048576* *4=4194304B=4096KB=4MB操作系统讲义之五 可以采用两种方法来解决页表存放问题：可以采用两种方法来解决页表存放问题： 采用离散分配方式来解决难以找到一块连续的内存空间的采用离散分配方式来解决难以找到一块连续的内存空间的 问题问题; 只将当

30、前需要的部分页表项调入内存，其余的页表项驻留只将当前需要的部分页表项调入内存，其余的页表项驻留 在磁盘上，需要时再调入。在磁盘上，需要时再调入。 采用此方法解决采用此方法解决操作系统讲义之五1）两级页表）两级页表(Two-Level Page Table)两级页表机制的做法是：两级页表机制的做法是：把整个页表进行分页，即将整个页表拆分成一把整个页表进行分页，即将整个页表拆分成一张张小页表张张小页表(称为页表页称为页表页) ,小页表小页表的大小与的大小与页框页框大大小相同小相同，然后再为这些小页表再建一张表，称为，然后再为这些小页表再建一张表，称为外层页表外层页表( (也称也称页目录表页目录表)

31、 )，外层页表存放每个小，外层页表存放每个小页表对应的页表对应的内存物理块号内存物理块号。操作系统讲义之五1011107801217421023第第0页页表页页表1460121023第第 1 页页表页页表114115011023012345671141151468第第1023 页页表页页存空间内存空间两级页表结构两级页表结构一个内存物理块为一个内存物理块为1KB。本例将页表。本例将页表拆分成拆分成1024个小页个小页表。表。页目录表页目录表操作系统讲义之五v由上图可知，在页表的每个表项中存放的是进由上图可知，在页表的每个表项中存放的是进程的某页在内存的物理块号，如第程

32、的某页在内存的物理块号，如第0页存放在第页存放在第1个物理块中，第个物理块中，第1页存放在第页存放在第4个物理块中。而个物理块中。而在在外层页表的每个表项中外层页表的每个表项中，所存放的是某页表，所存放的是某页表分页的首址，如分页的首址，如第第0号小页表号小页表是存放在第是存放在第1011物物理块中，理块中，第第1号小页表号小页表是存放在第是存放在第1078物理块中物理块中等。等。操作系统讲义之五在两级页表时，指令所给出的地址分为三部分：在两级页表时，指令所给出的地址分为三部分：（ 外层页号，外层页内地址，页内地址）外层页号，外层页内地址，页内地址）逻辑地址结构可描述如下逻辑地址结构可描述如下

33、( (上述例子的逻辑地址结构上述例子的逻辑地址结构) )：1）外层页号用）外层页号用10位，位， 210=1024B (将页表拆分为将页表拆分为1024个个 小页小页)2）外层页内地址用）外层页内地址用10位，位， 210=1024B （每个小页表为（每个小页表为1024B）3）页内地址用）页内地址用12位，位， 212=4096B=4KB操作系统讲义之五具有两级页表的地址变换机构具有两级页表的地址变换机构页目录号页目录号页号页号页内地址页内地址p1p2d逻辑地址逻辑地址+外部页表寄存器外部页表寄存器页目录号页目录号+db页表页表物理地址物理地址b二级页表地址变换需三次访问主存二级页表地址变换

34、需三次访问主存：一次访问页目录、一次：一次访问页目录、一次访问页表页、一次访问指令或数据。访问页表页、一次访问指令或数据。操作系统讲义之五虚拟地址虚拟地址二级页表结构及地址映射二级页表结构及地址映射页表地址页表地址.页目录页目录(每进程一个每进程一个)块号块号.页表页表代码或数据代码或数据.内存块内存块+页目录地址页目录地址外层页号外层页号页表位移页表位移页位移页位移操作系统讲义之五2) 多级页表（多级页表（略略） 对于对于32位的机器，采用两级页表结构是合适位的机器，采用两级页表结构是合适的；的； 对于对于64位的机器，如果页面大小仍采用位的机器，如果页面大小仍采用4KB(即即212KB)，

35、那么还剩下那么还剩下52位，位， 假定仍按物假定仍按物理块的大小理块的大小(212位位)来划分页表，则将余下的来划分页表，则将余下的42位位用于页号。此时在页表中可能有用于页号。此时在页表中可能有4096 G个页表个页表项项(242= 4096 G)， 要占用要占用16384 GB的连续内存的连续内存空间。空间。 操作系统讲义之五 必须采用多级页表，将页目录号表表再为页目录必须采用多级页表，将页目录号表表再为页目录号表，也是将各分页离散地装入到不相邻接的号表，也是将各分页离散地装入到不相邻接的物理块中，再利用第物理块中，再利用第2级的外层页表来映射它们级的外层页表来映射它们之间的关系。之间的关

36、系。操作系统讲义之五一道考研题一道考研题 （东南大学（东南大学2001)2001)v判断题：虚拟存储器是一个虚假的地址空间，因而这个地判断题：虚拟存储器是一个虚假的地址空间，因而这个地址空间的大小是没有限制的（址空间的大小是没有限制的（ ）v分析：在虚拟存储器中，用户的地址空间仍然受到地址字分析：在虚拟存储器中，用户的地址空间仍然受到地址字长和外存容量的限制。虚拟存储器的长和外存容量的限制。虚拟存储器的最大容量受地址长度最大容量受地址长度（地址总线位数）决定，一个（地址总线位数）决定，一个拥有拥有32位地址长度的系统位地址长度的系统，其虚拟内存最大为其虚拟内存最大为232字节。当然，一个字节。

37、当然，一个实际的虚拟存储器实际的虚拟存储器的大小还会受到辅助存储器大小的限制。的大小还会受到辅助存储器大小的限制。v答案答案 错错操作系统讲义之五选择题选择题v一个计算机系统的虚拟存储器的最大容量是由（）确定的，一个计算机系统的虚拟存储器的最大容量是由（）确定的，其实际容量是由（其实际容量是由（B）确定的。）确定的。vA、：、： 计算机字长；计算机字长； 内存容量；内存容量； 硬盘容量；硬盘容量； 内存和硬盘容量之和；内存和硬盘容量之和； 计算机的地址结构。计算机的地址结构。v答案：答案： 、操作系统讲义之五v2010考研题考研题：某计算机采用二级页表的分页存储管理方式，：某计算机采用二级页表

38、的分页存储管理方式，按字节编址，页大小为按字节编址，页大小为210字节（字节（1K），页表项大小为），页表项大小为2字节，字节，逻辑地址结构为：逻辑地址结构为： , 逻辑地址逻辑地址空间大小为空间大小为216页，则表示整个逻辑地址空间的页目录表中包页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是含表项的个数至少是 A. 64 B. 128C. 256 D. 512解：逻辑地址空间为解：逻辑地址空间为216页，页表项为页，页表项为2个字节，故页表长度为个字节，故页表长度为 216 2=128KB，一个内存物理块存放，一个内存物理块存放1KB，故，故 128KB/1KB=128，即得页目

39、录表，即得页目录表(外层页表外层页表)至少包含至少包含 128个表项。个表项。 页目录号页目录号 页号页号 页内偏移量页内偏移量操作系统讲义之五6. 6. 信息的共享和保护信息的共享和保护v信息共享：允许进程的地址空间在内存中非连续信息共享：允许进程的地址空间在内存中非连续存放，使得多个进程可共享某些页面。存放，使得多个进程可共享某些页面。但共享代但共享代码页面受限制码页面受限制。为什么？为什么？v信息保护：信息保护：进行地址转换时，检查是否超页进行地址转换时，检查是否超页（逻辑页和（逻辑页和页表控制寄存器中页表长度相比页表控制寄存器中页表长度相比)；在页表中设置存取权限项。在页表中设置存取权

40、限项。操作系统讲义之五7.存储页面表存储页面表 存储页面表是整个系统的一张表，存储页面表存储页面表是整个系统的一张表，存储页面表指出内存各页面是否已被分配出去指出内存各页面是否已被分配出去, 以及未分配以及未分配页面的总数。存储页面表也有两种构成方法。页面的总数。存储页面表也有两种构成方法。（1）位示图）位示图 一种是一种是在内存中划分一块固定区域在内存中划分一块固定区域，每个单元，每个单元的每个比特代表一个页面。如果该页面已被分的每个比特代表一个页面。如果该页面已被分配，则对应比特位置配，则对应比特位置1，否则置，否则置0。这种方法称。这种方法称为位示图法。如下图所示。为位示图法。如下图所示

41、。操作系统讲义之五位示图位示图操作系统讲义之五（2）空闲页面链空闲页面链 存储页面表的另一种构成办法是采用空闲页存储页面表的另一种构成办法是采用空闲页面链的方法。在空闲页面链中，队首页面的第一面链的方法。在空闲页面链中，队首页面的第一个单元和第二个单元分别放入空闲页面总数与指个单元和第二个单元分别放入空闲页面总数与指向下一个空闲页面的指针。其他页面的第一个单向下一个空闲页面的指针。其他页面的第一个单元中则分别放入指向下一个页面的指针。空闲页元中则分别放入指向下一个页面的指针。空闲页面链的方法由于使用了空闲页面本身的单元存放面链的方法由于使用了空闲页面本身的单元存放指针，因此不占据额外的内存空间

42、。指针，因此不占据额外的内存空间。操作系统讲义之五二、二、动态页式管理动态页式管理1. 引入原因引入原因 在静态页式存储管理中，要求把进程地址空间的全在静态页式存储管理中，要求把进程地址空间的全部页都要装入内存才能运行。部页都要装入内存才能运行。而在实际中一个作业而在实际中一个作业的某些部分可能在运行过程中是用不到的，比如：的某些部分可能在运行过程中是用不到的，比如：如果没有错误的发生，错误处理模块就不会被调用。如果没有错误的发生，错误处理模块就不会被调用。因此，在静态页式管理中会将一些不需要的页也装因此，在静态页式管理中会将一些不需要的页也装入内存入内存,而且内存资源不足时而且内存资源不足时

43、,该作业或进程将无法运该作业或进程将无法运行。行。2. 动态页式管理的主要思想动态页式管理的主要思想: 在作业或进程开始运行前，在作业或进程开始运行前，只将被认为是经常被反只将被认为是经常被反复执行和调用的部分装入内存，而其它部分在执行复执行和调用的部分装入内存，而其它部分在执行过程中动态的调入。即：通过交换的技术以小的内过程中动态的调入。即：通过交换的技术以小的内存运行大的作业。存运行大的作业。操作系统讲义之五3. 有两种动态装入方式有两种动态装入方式 (1)(1) 请求页式管理请求页式管理 当发现欲执行的某条指令或数据不在内存时，当发现欲执行的某条指令或数据不在内存时，发生缺页中断，由系统

44、将外存的页面调入内发生缺页中断，由系统将外存的页面调入内存存(软件实现软件实现)。 (2)(2) 预调入方管理预调入方管理 系统对那些在外存中的页进行调入顺序计算，系统对那些在外存中的页进行调入顺序计算，估计出这些页中指令和数据的执行和被访问估计出这些页中指令和数据的执行和被访问的顺序，并按此顺序事先将它们顺序调入和的顺序，并按此顺序事先将它们顺序调入和调出内存。调出内存。 4. 请求页式管理需要解决的问题请求页式管理需要解决的问题操作系统讲义之五 (1) 如何发现页是否在内存如何发现页是否在内存 可以用扩充页表的方法解决，即除了页号、页面号外，再增可以用扩充页表的方法解决，即除了页号、页面号

45、外，再增加该页是否在内存的加该页是否在内存的标志位标志位及该页在及该页在外存的起始地址外存的起始地址。扩充。扩充后的页表如下：后的页表如下：页号页号 页面号页面号 标志位标志位 外存始址外存始址 0 8 0 8 Y 1 20 1 20 Y 2 - 2 - N 3 - 3 - N (2) (2) 如何处理缺页问题如何处理缺页问题 关于某页不在内存时的处理涉及两个问题：关于某页不在内存时的处理涉及两个问题： 采用何种方法把所缺的页调入内存；采用何种方法把所缺的页调入内存； 如果内存没有空闲页面，把调进来的页放在什么地如果内存没有空闲页面，把调进来的页放在什么地 方方( (如何淘汰页的问题如何淘汰页

46、的问题) )。操作系统讲义之五v采用什么策略淘汰页采用什么策略淘汰页(后面详细讲后面详细讲)v如果内存中的某页被淘汰，有两种情况：其一是该页在程序如果内存中的某页被淘汰，有两种情况：其一是该页在程序运行时被修改过；其二是没被修改。如果被修改过，淘汰时运行时被修改过；其二是没被修改。如果被修改过，淘汰时应重新写到外存，若未修改，则不必重新入外存应重新写到外存，若未修改，则不必重新入外存( (因外存已因外存已有副本有副本) )。v问题：如何知道被淘汰的页是否被修改过？问题：如何知道被淘汰的页是否被修改过？ 可在页表中再增加一项，以记录该页是否被修改过。增加可在页表中再增加一项，以记录该页是否被修改

47、过。增加后的页表如下：后的页表如下：页号页号 页面号页面号 标志位标志位 改变位改变位 外存始址外存始址 修改位修改位操作系统讲义之五5. 请求页式管理中的置换算法请求页式管理中的置换算法 置换算法在内存中没有空闲页面时被调用。它的目的是选置换算法在内存中没有空闲页面时被调用。它的目的是选出一个被淘汰的页面。如果内存中有足够的空闲页面存放所出一个被淘汰的页面。如果内存中有足够的空闲页面存放所调入的页，则不必使用置换算法。把内存和外存统一管理的调入的页，则不必使用置换算法。把内存和外存统一管理的真正目的是真正目的是把那些被访问概率非常高的页存放在内存中把那些被访问概率非常高的页存放在内存中。因。

48、因此，置换算法应该置换那些被访问概率最低的页，将它们移此，置换算法应该置换那些被访问概率最低的页，将它们移出内存。比较常用的置换算法有以下几种出内存。比较常用的置换算法有以下几种: (1)(1) 随机淘汰算法随机淘汰算法(RG) 在系统无法确定哪些页被访问的概率较低时，随机地选择某在系统无法确定哪些页被访问的概率较低时，随机地选择某个用户的页面并将其换出。个用户的页面并将其换出。操作系统讲义之五(2) 轮转法轮转法(RR) 循回换出内存可用区内一个可以被换出的页面，循回换出内存可用区内一个可以被换出的页面，无论该页是否刚被换进或以换进很长时间。无论该页是否刚被换进或以换进很长时间。(3) 先进

49、先出先进先出(FIFO) 总是选择在内存中驻留时间最长的一页被换出。总是选择在内存中驻留时间最长的一页被换出。FIFO算法认为先调入内存的页不再被访问的可算法认为先调入内存的页不再被访问的可能性大，因此选择最先调入的换出。事实上，那能性大，因此选择最先调入的换出。事实上，那些在内存中停留时间最长的页往往也是经常被访些在内存中停留时间最长的页往往也是经常被访问的页。问的页。操作系统讲义之五v假设某作业有假设某作业有5个页面，执行时引用的页序列为：个页面，执行时引用的页序列为：0、1、2、3、0、1、4、0、1、2、3、4 共访问共访问12个页面，当系统给该进程个页面，当系统给该进程3个内存块时，

50、个内存块时，FIFO发生发生9次缺页中断：次缺页中断：操作系统讲义之五(4) 最佳算法最佳算法(OPT) 选择以后不再访问的页或经很长时间之后才可能访问的页进选择以后不再访问的页或经很长时间之后才可能访问的页进行淘汰。行淘汰。 例如：例如：如果一个进程对页面的访问序列为：如果一个进程对页面的访问序列为：0、1、2、3、0、1、4、0、1、2、3、4，系统给该进程，系统给该进程3个物理页块，则按照最佳个物理页块，则按照最佳置换算法，会产生置换算法，会产生7次缺页中断，缺页中断率为次缺页中断，缺页中断率为f= 7/12。表示缺页中断，表示缺页中断，表示无缺页中断表示无缺页中断。操作系统讲义之五（5

51、）最近最久未使用的页面置换算法最近最久未使用的页面置换算法(LRU) 该算法的基本思想是该算法的基本思想是: 当需要淘汰某一页时，选择当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页离当前时间最近的一段时间内最久没有使用过的页先淘汰。该算法的主要出发点是，如果某页被访问先淘汰。该算法的主要出发点是，如果某页被访问了，则它可能马上还要被访问。或者反过来说，如了，则它可能马上还要被访问。或者反过来说，如果某页很长时间未被访问，则它在最近一段时间也果某页很长时间未被访问，则它在最近一段时间也不会被访问。不会被访问。 要完全实现要完全实现LRU算法是十分困难的算法是十分困难的。因为

52、要找出最近。因为要找出最近最久未被使用的页面的话，就必须对每一个页面都最久未被使用的页面的话，就必须对每一个页面都设置有关的访问记录项，而且每一次访问都必须更设置有关的访问记录项，而且每一次访问都必须更新这些记录。这显然要花费巨大的系统开销。因此，新这些记录。这显然要花费巨大的系统开销。因此，在实际系统中往往使用在实际系统中往往使用LRU的近似算法。的近似算法。 操作系统讲义之五LRU页面置换算法举例：页面置换算法举例：例如：进程例如：进程P有有5个页，进程访问页的顺序为：个页，进程访问页的顺序为：4，3，2，1，4，3，5，4，3，2，1，5；如果在内存中分配给该进程；如果在内存中分配给该进

53、程3个页面个页面，则缺页情况如下：，则缺页情况如下：页面432143543215页面1432143543215页面243214354321页面34321435432缺页缺页中断次数：缺页中断次数：1010次次缺页率缺页率 = (10/12)= (10/12)* *100%=83.3%100%=83.3%页面淘汰顺序：页面淘汰顺序： 4，3，2，1，5，4，3操作系统讲义之五LRU有两个近似算法有两个近似算法最不经常使用的页面淘汰算法最不经常使用的页面淘汰算法(LFU)1）最不经常使用页面淘汰算法）最不经常使用页面淘汰算法LFU(least frequently used) 该算法在需要淘汰某一

54、页时，首先淘汰到当前该算法在需要淘汰某一页时，首先淘汰到当前时间为止，被访问次数最少的那一页。这只要在时间为止，被访问次数最少的那一页。这只要在页表中给每一页增设一个页表中给每一页增设一个访问计数器访问计数器即可实现。即可实现。每当该页被访问时，访问计数器加每当该页被访问时，访问计数器加1，而发生一，而发生一次缺页中断时，则淘汰计数值最小的那一页，次缺页中断时，则淘汰计数值最小的那一页，并并将所有的计数器清零将所有的计数器清零。最近没使用的页面淘汰算法最近没使用的页面淘汰算法(NUR)操作系统讲义之五2）最近没有使用页面淘汰算法）最近没有使用页面淘汰算法NUR 该算法在需要淘汰某一页时，从那些

55、最近一个该算法在需要淘汰某一页时，从那些最近一个时期内未被访问的页中任选一页淘汰。只要在时期内未被访问的页中任选一页淘汰。只要在页表中增设一个访问位即可实现。当某页被访页表中增设一个访问位即可实现。当某页被访问时，访问位置问时，访问位置1。否则，访问位置。否则，访问位置0。系统周。系统周期性地对所有引用位清零。当需淘汰一页时，期性地对所有引用位清零。当需淘汰一页时，从那些访问位为零的页中选一页进行淘汰。从那些访问位为零的页中选一页进行淘汰。操作系统讲义之五（6）Clock置换算法置换算法(时钟置换算法时钟置换算法)1） 简单的简单的Clock置换算法置换算法 为每页设置一位访问位，为每页设置一

56、位访问位，当当淘汰一个页面时，如果指针指淘汰一个页面时，如果指针指向页面的访问位向页面的访问位R为为0，就将其，就将其淘汰，并把新的页面插入这个淘汰，并把新的页面插入这个位置，指针向前移动一个位置；位置，指针向前移动一个位置； 如果访问位如果访问位R为为1，就清除，就清除R位位(置置0)，并把指针前移一个位，并把指针前移一个位置，直到找到一个置，直到找到一个R位为位为0的页的页面为止。面为止。操作系统讲义之五 由由访问位访问位R和和修改位修改位M可以组合成下面四种类型的页面：可以组合成下面四种类型的页面： 1类类(R=0, M=0): 表示该页最近既未被访问，又未被修改，是表示该页最近既未被访

57、问，又未被修改，是最佳淘汰页。最佳淘汰页。 2类类(R=0, M=1)： 表示该页最近未被访问，但已被修改，并不表示该页最近未被访问，但已被修改，并不是很好的淘汰页。是很好的淘汰页。 3类类(R=1, M=0)： 最近已被访问，但未被修改，该页有可能再最近已被访问，但未被修改，该页有可能再被访问。被访问。 4类类(R=1, M=1): 最近已被访问且被修改，该页可能再被访问。最近已被访问且被修改，该页可能再被访问。 2. 改进型改进型Clock置换算法置换算法 操作系统讲义之五v其执行过程可分成以下三步：其执行过程可分成以下三步： (1) 从指针所指示的当前位置开始，从指针所指示的当前位置开始

58、， 扫描循环队列，扫描循环队列， 寻找寻找R=0且且M=0的的第一类第一类页面，页面， 将所遇到的第一个页面作为所选中将所遇到的第一个页面作为所选中的淘汰页。的淘汰页。 在第一次扫描期间不改变访问位在第一次扫描期间不改变访问位A。 (2) 如果第一步失败，则开始第二轮扫描，寻找如果第一步失败，则开始第二轮扫描，寻找R=0且且M=1的的第二类第二类页面，将所遇到的第一个这类页面作为淘汰页。在第页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，二轮扫描期间，将所有扫描过的页面的访问位将所有扫描过的页面的访问位R都置为都置为0。 (3) 如果第二步也失败，则将指针返回到开始的位置，并将所如

59、果第二步也失败，则将指针返回到开始的位置，并将所有的访问位有的访问位R置为置为0。 然后重复第一步，如果仍失败，必要然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。时再重复第二步，此时就一定能找到被淘汰的页。 操作系统讲义之五6. Belady现象现象(异常现象异常现象)vBelady现象：先进先出算法的一个缺点是它有一种陷阱现象。现象：先进先出算法的一个缺点是它有一种陷阱现象。一般来说，对于任何一作业或进程，如果给它分配的内存页一般来说，对于任何一作业或进程，如果给它分配的内存页面数越接近于它所要求的页面数，则发生缺页的次数会越少。面数越接近于它所要求的页面数，则

60、发生缺页的次数会越少。在极限情况下，这个推论是成立的。因为如果给一个进程分在极限情况下，这个推论是成立的。因为如果给一个进程分配了它所要求的全部页面，则不会发生缺页现象。但是，配了它所要求的全部页面，则不会发生缺页现象。但是，使使用用FIFO算法时，在未给进程或作业分配足够的页面数时，算法时，在未给进程或作业分配足够的页面数时，有时会出现分配的页面数增多，缺页次数反而增加的奇怪现有时会出现分配的页面数增多，缺页次数反而增加的奇怪现象。这种现象称为象。这种现象称为Belady现象。现象。如下图所示。如下图所示。vBelady现象的原因：现象的原因：FIFO算法的置换特征与进程访问内存算法的置换特