第八章虚拟内存浙江工业大学课件.ppt

1、1虚拟内存虚拟内存第第 8 章章2虚拟存储器管理技术虚拟存储器管理技术 固定分区、动态分区、简单分页和简单分段的存储器固定分区、动态分区、简单分页和简单分段的存储器管理方式，有一个共同的特点，即要求将一个作业全管理方式，有一个共同的特点，即要求将一个作业全部装入内存才能运行。如果有的部装入内存才能运行。如果有的作业很大，其所要求作业很大，其所要求的内存空间超过了内存总容量的内存空间超过了内存总容量，作业就不能全部被装，作业就不能全部被装入内存，致使该作业无法运行；有时大量作业要求运入内存，致使该作业无法运行；有时大量作业要求运行，但由于内存容量不足以容纳所有这些作业，只能行，但由于内存容量不足

2、以容纳所有这些作业，只能将少数作业装入内存让它们先运行，而将其它大量的将少数作业装入内存让它们先运行，而将其它大量的作业留在外存上等待。作业留在外存上等待。显而易见的一种解决方法，是从物理上增加内存容量，显而易见的一种解决方法，是从物理上增加内存容量，但这往往会受到机器自身的限制，而且增加了系统成但这往往会受到机器自身的限制，而且增加了系统成本。本。另一种方法是另一种方法是从逻辑上扩充内存容量，这正是虚拟存从逻辑上扩充内存容量，这正是虚拟存储技术所要解决的主要问题储技术所要解决的主要问题。 3分页和分段对内存分区技术的关键突破分页和分段对内存分区技术的关键突破进程对内存访问的逻辑地址在运行时动

3、态地进程对内存访问的逻辑地址在运行时动态地被转换为物理地址，从而保证进程可以占据被转换为物理地址，从而保证进程可以占据内存的不同区域（地址重定位机制）。内存的不同区域（地址重定位机制）。一个进程可以划分成许多块，在运行时，这一个进程可以划分成许多块，在运行时，这些块不需要连续地位于主存中些块不需要连续地位于主存中 （分页或分（分页或分段机制）。段机制）。一个进程在执行的过程中，不需要所有的块一个进程在执行的过程中，不需要所有的块都在内存中（虚拟内存机制）。都在内存中（虚拟内存机制）。4引入虚拟内存机制之后进程的执行引入虚拟内存机制之后进程的执行首先，操作系统仅读取程序开始处的一些块。首先，操作

4、系统仅读取程序开始处的一些块。常驻集常驻集 (Resident set) 进程执行中任何时候进程执行中任何时候都在主存的部分都在主存的部分当处理器需要访问一个不在主存中的块时，系统将当处理器需要访问一个不在主存中的块时，系统将产生一个内存访问故障中断（缺页中断）。产生一个内存访问故障中断（缺页中断）。操作系统将该进程置为阻塞状态，并取得控制权。操作系统将该进程置为阻塞状态，并取得控制权。操作系统需要将该进程块取进内存操作系统需要将该进程块取进内存产生一个磁盘产生一个磁盘 I/O读请求读请求执行执行I/O操作期间，操作系统可选择另一个进程操作期间，操作系统可选择另一个进程来运行来运行当当I/O操

5、作完成后，则产生一个操作完成后，则产生一个I/O中断，控制中断，控制权又交回操作系统，操作系统将之前被阻塞的进权又交回操作系统，操作系统将之前被阻塞的进程置为就绪状态程置为就绪状态5虚拟存储技术的优点虚拟存储技术的优点内存中可以容纳更多的进程内存中可以容纳更多的进程每个进程只有一部分的程序块或数据块装入每个进程只有一部分的程序块或数据块装入内存，其他块仍保存在磁盘上内存，其他块仍保存在磁盘上内存可以容纳更多的进程，并发性得到更大内存可以容纳更多的进程，并发性得到更大的提高，从而也使得处理器得到了更有效的的提高，从而也使得处理器得到了更有效的利用利用进程可以比主存的全部空间还大进程可以比主存的全

6、部空间还大实存实存 (Real memory)：内存：内存虚存虚存 (Virtual memory)：磁盘的存储空间：磁盘的存储空间6虚拟存储器的基本概念虚拟存储器的基本概念 1 1局部性原理局部性原理( (principle of locality) )虚拟存储器系统实现的理论基础：程序执行的局部性规律。虚拟存储器系统实现的理论基础：程序执行的局部性规律。早在早在19681968年年P PDenningDenning就指出过，就指出过，程序在执行时将呈现出局部程序在执行时将呈现出局部性规律性规律，即在一段时间内，程序的执行仅局限于某个部分；相，即在一段时间内，程序的执行仅局限于某个部分；相应

7、地，它所访问的存储空间也局限于某个区域内。应地，它所访问的存储空间也局限于某个区域内。出现局部性规律的原因：出现局部性规律的原因：程序在执行时，除了少部分的转移和过程调用指令外，大多程序在执行时，除了少部分的转移和过程调用指令外，大多数仍是顺序执行的。数仍是顺序执行的。子程序调用将会使程序的执行由一部分内存区域转至另一部子程序调用将会使程序的执行由一部分内存区域转至另一部分区域。但在大多数情况下，过程调用的深度都不超过分区域。但在大多数情况下，过程调用的深度都不超过5 5。程序中存在许多循环结构，循环体中的指令被多次执行。程序中存在许多循环结构，循环体中的指令被多次执行。程序中还包括许多对数据

8、结构的处理，如对连续的存储空程序中还包括许多对数据结构的处理，如对连续的存储空间间数组的访问，往往局限于很小的范围内。数组的访问，往往局限于很小的范围内。7局部性原理局部性原理时间局限性时间局限性：如果程序中的某条指令一旦执行，：如果程序中的某条指令一旦执行，则不久的将来该指令可能再次被执行；如果某个则不久的将来该指令可能再次被执行；如果某个存储单元被访问，则不久以后该存储单元可能再存储单元被访问，则不久以后该存储单元可能再次被访问。产生时间局限性的典型原因是在程序次被访问。产生时间局限性的典型原因是在程序中存在着大量的循环操作。中存在着大量的循环操作。空间局限性空间局限性：一旦程序访问了某个

9、存储单元，则：一旦程序访问了某个存储单元，则在不久的将来，其附近的存储单元也最有可能被在不久的将来，其附近的存储单元也最有可能被访问。访问。 即程序在一段时间内所访问的地址，可能即程序在一段时间内所访问的地址，可能集中在一定的范围内，其典型原因是程序是顺序集中在一定的范围内，其典型原因是程序是顺序执行的。执行的。局部性原理确保了虚拟存储机制的可行性。但利局部性原理确保了虚拟存储机制的可行性。但利用局部性原理的同时，要避免系统出现用局部性原理的同时，要避免系统出现抖动现象抖动现象（thrashing），即处理器大部分时间都用于交），即处理器大部分时间都用于交换块，而不是执行指令。换块，而不是执行

10、指令。82. 虚拟存储器实现的软硬件支撑虚拟存储器实现的软硬件支撑硬件支撑硬件支撑有相当容量的辅存（磁盘）以存放所有并发作业的地址有相当容量的辅存（磁盘）以存放所有并发作业的地址空间空间有一定容量的内存来存放运行作业的部分程序有一定容量的内存来存放运行作业的部分程序有支持分页或分段的硬件有支持分页或分段的硬件请求分页系统和请求分段系统请求分页系统和请求分段系统动态地址转换机构动态地址转换机构软件支撑软件支撑操作系统能提供页或段在主存和辅存之间有效交换的管操作系统能提供页或段在主存和辅存之间有效交换的管理模块理模块读取策略、放置策略、替换策略、驻留集管理、清除策略等读取策略、放置策略、替换策略、

11、驻留集管理、清除策略等93. 虚拟存储器的特征虚拟存储器的特征离散性离散性：指在内存分配时采用离散的分配方式，它是虚指在内存分配时采用离散的分配方式，它是虚拟存储器的最基本的特征。拟存储器的最基本的特征。多次性：多次性：指一个作业被分成多次调入内存运行，即在作指一个作业被分成多次调入内存运行，即在作业运行时没有必要将其全部装入，只须将当前要运行的业运行时没有必要将其全部装入，只须将当前要运行的那部分程序和数据装入内存即可。多次性是虚拟存储器那部分程序和数据装入内存即可。多次性是虚拟存储器最重要的特征。最重要的特征。对换性：对换性：指允许在作业的运行过程中在内存和外存的对指允许在作业的运行过程中

12、在内存和外存的对换区之间换进、换出。换区之间换进、换出。虚拟性：虚拟性：指能够从逻辑上扩充内存容量，使用户所看到指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。的内存容量远大于实际内存容量。10请求分页存储管理系统请求分页存储管理系统请求分页请求分页存储管理系统是存储管理系统是在纯分页系统的基础在纯分页系统的基础上，增加了上，增加了请求调页功能请求调页功能、页面置换功能页面置换功能所形所形成的页式虚拟存储系统成的页式虚拟存储系统，它是目前常用的一种，它是目前常用的一种虚拟存储器的方式。虚拟存储器的方式。它允许只装人若干页它允许只装人若干页( (而非全部页而非全部页) )的

13、用户程序的用户程序和数据，便可启动运行。以后，再通过调页功和数据，便可启动运行。以后，再通过调页功能及页面置换功能，陆续地把即将要运行的页能及页面置换功能，陆续地把即将要运行的页面调入内存，同时把暂不运行的页面换出到外面调入内存，同时把暂不运行的页面换出到外存上，置换时以页面为单位。存上，置换时以页面为单位。 11 遇到要访问的页面不在内存中，遇到要访问的页面不在内存中，如何发现如何发现和和处理处理这种情况？这种情况？这是请求分页存储这是请求分页存储管理要解决的两个管理要解决的两个基本问题基本问题12为了能实现请求调页和置换功能，系统必须提供必要的为了能实现请求调页和置换功能，系统必须提供必要

14、的硬件支持：扩充的页表机制和缺页中断机构。硬件支持：扩充的页表机制和缺页中断机构。 （1 1）请求分页的页表机制请求分页的页表机制 它是在纯分页的页表机制上形成的，由于只将应用它是在纯分页的页表机制上形成的，由于只将应用程序的一部分调入内存，还有一部分仍在磁盘上，故程序的一部分调入内存，还有一部分仍在磁盘上，故需在页表中再增加若干项，供程序需在页表中再增加若干项，供程序( (数据数据) )在换进、换在换进、换出时参考。在请求分页系统中的每个页表项如图所示。出时参考。在请求分页系统中的每个页表项如图所示。1. 请求分页中的硬件支持请求分页中的硬件支持 页号页号 物理块号物理块号 状态位状态位P

15、访问字段访问字段A 修改位修改位M 外存地址外存地址13其中各字段说明如下：其中各字段说明如下：状态位（中断位状态位（中断位P P）：用于指示该页是否已调入内存，供程用于指示该页是否已调入内存，供程序访问时参考。序访问时参考。访问字段访问字段A A：用于记录本页在一段时间内被访问的次数，或用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页最近已有多长时间未被访问，提供给置换算法选择换出页面时参考。面时参考。修改位修改位M M：表示该页在调入内存后是否被修改过。由于内存表示该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本，因此，若未被

16、修改，中的每一页都在外存上保留一份副本，因此，若未被修改，在置换该页时就不需将该页写回到外存上，以减少系统的在置换该页时就不需将该页写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写开销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。到外存上，以保证外存中所保留的始终是最新副本。外存外存( (辅辅存存) )地址地址：用于指出该页在外存上的地址，通常是：用于指出该页在外存上的地址，通常是物理块号，供调入该页时使用物理块号，供调入该页时使用 14151413121110 9 8 7 6 5 4 3 2 1000000000000

17、0000111100001011000000000000011110010001110100110101 00010000000000100110000000000100110在在/不在内存不在内存页表页表虚地址虚地址8196（0 x2004）物理地址物理地址24580MOVE REG,819615MOVE REG,32760虚页虚页70000000000000000111100001011000000000000011110010001110100110101151413121110 9 8 7 6 5 4 3 2 1 00 1 1 1 1 1 1 1 1 1 1 1 1 0 0 03276

18、0-0 x7FF816(2)(2)缺页中断机构缺页中断机构 在请求分页系统中，每当所要访问的页面不在内存时，在请求分页系统中，每当所要访问的页面不在内存时，便要产生缺页中断，请求便要产生缺页中断，请求OSOS将所缺页调入内存。将所缺页调入内存。OS访问访问捕获页错误捕获页错误页在备用存储上页在备用存储上17缺页中断与一般中断的主要区别在于：缺页中断与一般中断的主要区别在于：缺页中断在指令执行期间产生和处理中断信号，而一缺页中断在指令执行期间产生和处理中断信号，而一般中断在一条指令执行完后检查和处理中断信号。般中断在一条指令执行完后检查和处理中断信号。缺页中断返回到该指令的开始重新执行该指令，而

19、一缺页中断返回到该指令的开始重新执行该指令，而一般中断返回到该指令的下一条指令执行。般中断返回到该指令的下一条指令执行。一条指令在执行期间，可能产生多次缺页中断。一条指令在执行期间，可能产生多次缺页中断。18保存该进程页表保存该进程页表的起始地址的起始地址(3)(3)地址变换机构地址变换机构19请求分页存储管理系统带来的新问题请求分页存储管理系统带来的新问题每个进程都有一个页表，页表保存在哪里？每个进程都有一个页表，页表保存在哪里？一个一个4GB (232 )的进程的进程,如果页大小为如果页大小为4KB(212 ) ，则需要的页表项为则需要的页表项为220页表占据了大量的空间，应该保存在虚存上

20、，可使页表占据了大量的空间，应该保存在虚存上，可使用多级页表结构用多级页表结构每个虚存访问会引起两次物理内存访问，导致每个虚存访问会引起两次物理内存访问，导致存储器访问时间加倍存储器访问时间加倍第一次取相应的页表项第一次取相应的页表项第二次取需要数据第二次取需要数据可使用快表机制来解决可使用快表机制来解决2032位地址的两级页表结构位地址的两级页表结构211011107817421461141151468 01141468外部页表外部页表第第0页页表页页表第第1页页表页页表第第1023页页表页页表01023某页表某页表分页的分页的始址始址进程的某页进程的某页在内存中的在内存中的物理块号物理块号

21、01023以以32位的逻辑地址空间的系统为例，页面大小为位的逻辑地址空间的系统为例，页面大小为4 KB010230102322通过通过P1可以找可以找到对应页表分到对应页表分页在内存中的页在内存中的起始地址起始地址通过通过P2可以找到可以找到对应页表项，从对应页表项，从而找到该页在内而找到该页在内存中的起始地址存中的起始地址23 举例：假设虚拟地址为举例：假设虚拟地址为32位，每页为位，每页为4KB，采用二级页表结构，如图。，采用二级页表结构，如图。 逻辑地址逻辑地址0 x00403004（十进制）所对（十进制）所对应的物理地址是什么？应的物理地址是什么？0 x00403004：0000000

22、001 0000000011 0 P1 P2 页内地址页内地址d4206596/4k=102741027/1024=13 P1=1 P2=3 d=4外层页号外层页号P1外层页内地址外层页内地址P2页内地址页内地址d3122 2112 11024快表（快表（Translation Lookaside Buffer，TLB）为了提高地址变换的速度，增设了一个具有为了提高地址变换的速度，增设了一个具有按内容查找、并行按内容查找、并行查询查询功能的特殊的高速缓冲存储器，称为功能的特殊的高速缓冲存储器，称为 “ “快表快表”，或称为，或称为“关联存储器关联存储器( (TLB, TLB, 转换后备缓冲器转

23、换后备缓冲器)”)”，用以存放当前访问的用以存放当前访问的那些页表项，每个页表项包括页号和相应的块号（页号不能省那些页表项，每个页表项包括页号和相应的块号（页号不能省略）。略）。引入快表之后的存储访问修改如下：引入快表之后的存储访问修改如下：处理器首先将逻辑地址中的页号与处理器首先将逻辑地址中的页号与TLB中的各页表项中的各页表项的页号进行的页号进行比较比较如果有相同的如果有相同的 (TLB命中命中)， 则直接从则直接从TLB的输出寄存器输出相应的输出寄存器输出相应的块号的块号如果没有找到如果没有找到(TLB不命中不命中) ，则访问内存从该进程的页表中查找，则访问内存从该进程的页表中查找检查该

24、页是否在内存中检查该页是否在内存中(检查检查P位位) 如果不在，则发生缺页中断如果不在，则发生缺页中断页访问之后，同时要将该页的页表项读入页访问之后，同时要将该页的页表项读入TLB252627P249 P249 图图8.88.8 缺页中断处理缺页中断处理 是 否 否 是 是 否 产生缺页中产生缺页中 否 是 断请求调页断请求调页 否否 是 开始（程序请求访问一页开始（程序请求访问一页)越界中断越界中断CPU检索快表检索快表页表项是否在快表中？页表项是否在快表中？访问页表访问页表页是否在内存中？页是否在内存中？修改快表修改快表修改访问位和修改位修改访问位和修改位形成物理地址形成物理地址 地址变换

25、地址变换结束结束保留保留CPU现场现场 从外存中找到缺从外存中找到缺页页 页号页号页表长页表长度？度？ 内存满否？内存满否？选择一页换出选择一页换出 该页是否被修改？该页是否被修改？ 将该页写回外存将该页写回外存 将一页从外存换入内存将一页从外存换入内存 修改页表修改页表 CPU从外存读缺页从外存读缺页 启动启动I/O硬件硬件 28分页和分页和TLB的操作的操作29快表访问示例快表访问示例假设检索快表的时间假设检索快表的时间T TTLBTLB为为2020nsns，访问内存的访问内存的时间时间T TM M为为100100nsns，TLBTLB的命中率的命中率p p为为90%90%。计算。计算CP

26、UCPU存取内存一个数据的平均时间。存取内存一个数据的平均时间。解：解：1）快表命中时）快表命中时CPU存取内存一个数据的时间为存取内存一个数据的时间为T1检索快表时间访问内存数据时间检索快表时间访问内存数据时间=T TTLBTLB+T TM M =20100120ns。2）当快表不命中时）当快表不命中时CPU存取内存一个数据的时间为存取内存一个数据的时间为T2检索快表时间检索内存中的页表时间访问内检索快表时间检索内存中的页表时间访问内存数据时间存数据时间= T TTLBTLB+T TM M +T TM M 20100100220ns。3)CPU3)CPU存取内存一个数据的平均时间为存取内存一

27、个数据的平均时间为 T = T1T = T1* *命中率命中率+ +T2T2* *（1 1命中率）命中率）= = T1T1* *P+T2P+T2* *(1-P)= (1-P)= 120120* *0.9+2200.9+220* *0.1=130ns0.1=130ns。30存储器存储器Cache虚存必须与内存高速缓存进行交互虚存必须与内存高速缓存进行交互31页大小页大小页越小，内部碎片的总页越小，内部碎片的总量越少量越少页越小，每个进程所需页越小，每个进程所需的页数增加，则需要更的页数增加，则需要更大的页表大的页表内存和辅存之间以页为内存和辅存之间以页为单位进行数据交换，从单位进行数据交换，从辅

28、存的角度来看，希望辅存的角度来看，希望页比较大，从而实现更页比较大，从而实现更有效的数据块传送有效的数据块传送32例题例题 例例11某虚拟存储器的用户编程空间共某虚拟存储器的用户编程空间共3232个页面，每页个页面，每页1 1KBKB，主存主存为为1616KBKB。假定某时刻用户页表中已调入主存的页面的虚拟页号假定某时刻用户页表中已调入主存的页面的虚拟页号和物理页表对照表为表一，则下表中与虚拟地址相对应的物理和物理页表对照表为表一，则下表中与虚拟地址相对应的物理地址为表二（如果主存找不到，即为该页失效）。虚拟存储的地址为表二（如果主存找不到，即为该页失效）。虚拟存储的功能是由功能是由C C完成

29、的。在虚拟存储系统中，采用完成的。在虚拟存储系统中，采用D D提高提高E E的速度。的速度。 表一表一 虚页号虚页号 物理页号物理页号 0 5 0 5 1 10 1 10 2 4 2 4 8 7 8 7 表二表二 虚地址虚地址 物理地址物理地址 0 0A5CA5C（H H） A A 1A5C 1A5C（H H） B B 33供选择的答案：供选择的答案：A A，B B： 页失效页失效 1 1E5CE5C（H H） 2A5C 2A5C（H H） 165C 165C（H H） 125C 125C（H H） 1A5C 1A5C（H H）C C： 硬件硬件 软件软件 软、硬件结合软、硬件结合D D： 高

30、速辅助存贮器高速辅助存贮器 高速光盘存贮器高速光盘存贮器 快速通道快速通道 高速缓冲存贮器高速缓冲存贮器E E： 连接编辑连接编辑 虚地址分配虚地址分配 动态地址映射动态地址映射 动态连接动态连接答案：答案：A B C D E 34解：每页大小解：每页大小 1 1KBKB，用用1616进制表示为进制表示为400400H H，由虚地址通过由虚地址通过直接映象的地址转换成物理地址步骤如下：直接映象的地址转换成物理地址步骤如下：将虚地址分离成页号将虚地址分离成页号p p和页内地址和页内地址d d：页号页号p p（虚地址页大小）取整（虚地址页大小）取整（0 0A5CH/400HA5CH/400H）取整

31、取整2 2( (0 0A5CH=00011)A5CH=00011)页内地址页内地址d d虚地址页号虚地址页号p p每页大小每页大小0 0A5C(H)A5C(H)2 2400(H)400(H)25C(H)(0101011011)25C(H)(0101011011)根据页号查页表，由页号根据页号查页表，由页号 p p2 2查页表得物理页号为查页表得物理页号为4 4将物理页号和页内地址构成物理地址物理页号页大将物理页号和页内地址构成物理地址物理页号页大小页内地址小页内地址4 4400(400(H)H)25C(H)25C(H)125C(H)125C(H) (000100 0101011011) (00

32、0100 0101011011)同理虚拟地址同理虚拟地址1 1A5CHA5CH分离成页号分离成页号P P6 6和页内位移和页内位移1515CH.CH.查页表知该页不在内存，页失效产生缺页中断调入内存。查页表知该页不在内存，页失效产生缺页中断调入内存。358.1.3 请求分段存储管理请求分段存储管理在简单分段系统的基础上实现的虚拟存储器，是在简单分段系统的基础上实现的虚拟存储器，是以分段为单位进行换入、换出的。以分段为单位进行换入、换出的。在程序运行之前只要先调入若干个分段（不必调在程序运行之前只要先调入若干个分段（不必调入所有的分段），便可启动运行。入所有的分段），便可启动运行。当所访问的段不

33、在内存时可请求当所访问的段不在内存时可请求OSOS将所缺的段调将所缺的段调入内存。入内存。为实现请求分段存储管理方式，同样需要一定的为实现请求分段存储管理方式，同样需要一定的硬件支持和相应的软件，有段表机制、缺段中断硬件支持和相应的软件，有段表机制、缺段中断机构以及地址变换机构。机构以及地址变换机构。368.1.3 请求分段存储管理请求分段存储管理 这是在分段系统的基础上，增加了请这是在分段系统的基础上，增加了请求调段及分段置换功能后，所形成的段式求调段及分段置换功能后，所形成的段式虚拟存储系统。虚拟存储系统。 为了实现请求分段，系统要提供硬件支持：为了实现请求分段，系统要提供硬件支持： (1

34、) (1) 请求分段的段表机制。请求分段的段表机制。 (2) (2) 缺段中断机构。缺段中断机构。 (3) (3) 地址变换机构。地址变换机构。 同样地，请求调段和段的置换功能的同样地，请求调段和段的置换功能的实现也需要得到实现也需要得到OS的支持。的支持。 371 1段表机制段表机制 在请求分段式管理中在段表中增加若干项，以供程序在请求分段式管理中在段表中增加若干项，以供程序在调进、调出时参考。请求分段的段表项如下：在调进、调出时参考。请求分段的段表项如下：存取方式：用于标识本分段的存取属性是只执行、只读，还是允存取方式：用于标识本分段的存取属性是只执行、只读，还是允许读写。许读写。访问字段

35、访问字段A A：用于记录该段被访问的频繁程度。用于记录该段被访问的频繁程度。修改位修改位M M：用于表示该段进入内存后，是否已被修改过。用于表示该段进入内存后，是否已被修改过。存在位存在位P P：说明本段是否已调入内存。说明本段是否已调入内存。增补位：用于表示本段在运行过程中，是否进行过动态增长。增补位：用于表示本段在运行过程中，是否进行过动态增长。外存起址：指示本段在外存中的起始地址，即起始盘块号。外存起址：指示本段在外存中的起始地址，即起始盘块号。段段 段段 段的段的 存取存取 访问访问 修改修改 存在存在 增补增补 外存外存名名 长长 基址基址 方式方式 字段字段A A 位位M M 位位

36、P P 位位 起址起址382.2.缺段中断机构缺段中断机构在请求分段系统中，采用的是请求调段策略。在请求分段系统中，采用的是请求调段策略。类同缺页中断机构，当进程所要访问的段未调入内类同缺页中断机构，当进程所要访问的段未调入内存时，便由缺段中断机构在硬件指令中间产生一缺存时，便由缺段中断机构在硬件指令中间产生一缺段中断信号，由缺段中断处理程序将所需的段调入段中断信号，由缺段中断处理程序将所需的段调入内存。内存。与缺页中断机构不同的是由于各段长不同，置换时与缺页中断机构不同的是由于各段长不同，置换时对内存的管理采用对内存的管理采用可变分区管理可变分区管理。39段表起始地址段表起始地址3 3 地址

37、变换机构地址变换机构408.1.4 段页式存储管理段页式存储管理 分页和分段存储管理方式都各有其优缺点。如果对分页和分段存储管理方式都各有其优缺点。如果对两种存储管理方式两种存储管理方式“各取所长各取所长”后，则可以形成一后，则可以形成一种新的存储管理方式的系统种新的存储管理方式的系统段页式系统。段页式系统。它以分页的方式管理内存，具有分页系统能有效地它以分页的方式管理内存，具有分页系统能有效地提高内存利用率的优点；又以分段的方式管理用户提高内存利用率的优点；又以分段的方式管理用户的逻辑的逻辑地址空间，地址空间，具有分段系统能很好地满足用户具有分段系统能很好地满足用户需要的长处需要的长处，显然

38、是一种比较有效的存储管理方式。，显然是一种比较有效的存储管理方式。Q：它有没有碎片问题？如果有的话，是内部还是外：它有没有碎片问题？如果有的话，是内部还是外部碎片？部碎片？411 1基本原理基本原理 将内存空间划分成大小相同的若干个块，将用户程序先按逻将内存空间划分成大小相同的若干个块，将用户程序先按逻辑完整性分为若干个段辑完整性分为若干个段，并为每个段赋予一个段名，并为每个段赋予一个段名，再把每再把每个段划分成若干个与块大小相同的页个段划分成若干个与块大小相同的页，将这些页离散装入不，将这些页离散装入不相邻接的块中。相邻接的块中。 假定页面大小为假定页面大小为4K。一作业分成三段。一作业分成

39、三段。 第一段第一段7k，占有，占有2页；页； 第二段第二段4k，占，占1页；页； 第三段第三段3k，占，占1页。页。 8k0104k004k04k0页内零头页内零头42段页式系统的地址结构段页式系统的地址结构段号段号段内地址段内地址页号页号页内地址页内地址 段页式存储管理中，地址结构是几维的？段页式存储管理中，地址结构是几维的？二维的二维的431 1基本原理基本原理 将内存空间划分成大小相同的若干个块，将用户程序先将内存空间划分成大小相同的若干个块，将用户程序先按逻辑完整性分为若干个段按逻辑完整性分为若干个段，并为每个段赋予一个段名，并为每个段赋予一个段名，再把每个段划分成若干个与块大小相同

40、的页再把每个段划分成若干个与块大小相同的页，将这些页，将这些页离散装入不相邻接的块中。离散装入不相邻接的块中。如下图：一个作业有四个段，页面大小为如下图：一个作业有四个段，页面大小为4 4K K，四个段的页四个段的页面数分别为面数分别为4 4、2 2、2 2、2 2，总页面数为，总页面数为1010页，此时每一页都页，此时每一页都属于逻辑上完整的一个段。属于逻辑上完整的一个段。段页式系统中的地址结构由段号、段内页号和页内地址段页式系统中的地址结构由段号、段内页号和页内地址三部分组成。三部分组成。在段页式系统中，为了实现从逻辑地址到物理地址的变在段页式系统中，为了实现从逻辑地址到物理地址的变换，系

41、统中必需同时配置段表和页表。由于将段中的页换，系统中必需同时配置段表和页表。由于将段中的页进行离散地分配，进行离散地分配，段表中的内容不再是段的内存始址和段表中的内容不再是段的内存始址和段长，而是页表始址和页表长度。段长，而是页表始址和页表长度。段号（段号（S）段内页号（段内页号（P）页内地址（页内地址（W）44段页式系统的作业地址空间段页式系统的作业地址空间 45 在段页式系统中，为了实现从逻辑地址到物在段页式系统中，为了实现从逻辑地址到物理地址的变换，系统中必需同时配置段表和页表。理地址的变换，系统中必需同时配置段表和页表。由于将段中的页进行离散地分配，由于将段中的页进行离散地分配，段表中

42、的内容段表中的内容不再是段的内存始址和段长，而是页表始址和页不再是段的内存始址和段长，而是页表始址和页表长度。表长度。46利用段表和页表实现地址映射利用段表和页表实现地址映射段号 状态 页表大小页表始址01112130段 表段表大小段表始址段 表 寄 存 器页号状态 存储块号01112130 页 表页号 状态存储块号0111 操作系统 主存页 表47页表的基址页表的基址2 2 地址变换机构地址变换机构48地址变换过程地址变换过程系统将逻辑地址截成段号系统将逻辑地址截成段号S S、段内页号段内页号P P与页内地址与页内地址W W，先用段号先用段号S S与段长与段长TLTL（存在段表寄存器中）进行

43、比较。（存在段表寄存器中）进行比较。若若 STLSTL，表示段号太大，访问越界，于是产生越界表示段号太大，访问越界，于是产生越界中断信号；中断信号；若若S STLTL，表示未越界，于是利用段表始址（存在段表表示未越界，于是利用段表始址（存在段表寄存器中）和段号求出该段对应的段表项在段表中的寄存器中）和段号求出该段对应的段表项在段表中的位置，从中得到该段的页表始址；位置，从中得到该段的页表始址；利用逻辑地址中的段内页号利用逻辑地址中的段内页号P P来获得对应页的页表项在来获得对应页的页表项在页表中位置，判断状态页表中位置，判断状态P P位，若位，若P P位为位为0 0表示该页不在内表示该页不在内

44、存中，产生缺页中断；存中，产生缺页中断；若若P P位为位为1 1，则从中读出该页所在的物理块号，则从中读出该页所在的物理块号b b，再用块再用块号号 b b和页内地址和页内地址W W拼成物理地址。拼成物理地址。49Q Q：段页式系统中，为了获得一条指令或数据，需要访：段页式系统中，为了获得一条指令或数据，需要访问几次内存？问几次内存？需访问三次内存：需访问三次内存：第一次访问内存中的段表，从中取得页表始址；第一次访问内存中的段表，从中取得页表始址；第二次访问内存中的页表，从中取出该页所在的物理块号，第二次访问内存中的页表，从中取出该页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理

45、地址；并将该块号与页内地址一起形成指令或数据的物理地址；第三次访问才是真正根据所得的物理地址取出指令或数据。第三次访问才是真正根据所得的物理地址取出指令或数据。如何提高速度？如何提高速度？在地址变换机构中增设一高速缓冲寄存器（如在地址变换机构中增设一高速缓冲寄存器（如TLBTLB），记录最），记录最近访问过的地址信息。每次访问它时，都同时利用段号和页近访问过的地址信息。每次访问它时，都同时利用段号和页号去检索高速缓存。号去检索高速缓存。508.2 操作系统软件操作系统软件是否使用虚拟内存技术？是否使用虚拟内存技术？使用分页、分段还是段页式？使用分页、分段还是段页式？采用何种算法来进行存储管理？

46、采用何种算法来进行存储管理？所有算法的核心都是尽可能使缺页频率最小所有算法的核心都是尽可能使缺页频率最小读取策略读取策略放置策略放置策略替换策略替换策略驻留集管理驻留集管理清除策略清除策略51读取策略读取策略(Fetch Policy)确定何时将一页取入内存。确定何时将一页取入内存。请求式页面调度请求式页面调度 (Demand paging) ：当需要访当需要访问该页中的一个单元时才将其读入内存。问该页中的一个单元时才将其读入内存。当进程第一次启动时，将发生大量的缺页当进程第一次启动时，将发生大量的缺页预约式页面调度预约式页面调度(Prepaging)：将那些预计在不将那些预计在不久的将来会被

47、访问的程序或数据所在的页面，预久的将来会被访问的程序或数据所在的页面，预先调入内存。先调入内存。由于预测的准确率不高（由于预测的准确率不高（50%50%），所以这种策略），所以这种策略主要用于进程的首次调入。主要用于进程的首次调入。52放置策略放置策略 (Placement Policy )确定一个进程块到底放在内存的哪个位确定一个进程块到底放在内存的哪个位置。置。分段系统需要考虑（最佳适配、首次适配、分段系统需要考虑（最佳适配、首次适配、邻近适配、最差适配）邻近适配、最差适配）分页或段页式系统中不需要考虑，因为在内分页或段页式系统中不需要考虑，因为在内存中的每一块大小都是相同的，只要放置在存

48、中的每一块大小都是相同的，只要放置在空闲块即可空闲块即可53替换策略替换策略(Replacement Policy )读取一个新页时，应该替换内存中的哪一页读取一个新页时，应该替换内存中的哪一页?在进程运行过程中，如果发生缺页，此时内在进程运行过程中，如果发生缺页，此时内存中又无空闲块时，为了保证进程能正常运存中又无空闲块时，为了保证进程能正常运行，就必须从内存中调出一页到磁盘。行，就必须从内存中调出一页到磁盘。页面置换算法的性能指标：页面置换算法的性能指标：缺页率（缺页率（ page fault rate ）=“缺页次数缺页次数 / 内存访问次数内存访问次数” (比比率率)从理论上讲，应将那

49、些以后不再被访问的页从理论上讲，应将那些以后不再被访问的页面换出，或把那些在较长时间内不会再被访面换出，或把那些在较长时间内不会再被访问的页面换出。问的页面换出。基于以前的行为去预测以后的访问行为。基于以前的行为去预测以后的访问行为。54基本的替换算法基本的替换算法1. 最佳最佳 (Optimal policy,OPT)最佳置换算法是由最佳置换算法是由Relady在在1966年提出的，年提出的，这种算法选择的被淘汰页面，将是这种算法选择的被淘汰页面，将是永不使用永不使用的的，或在，或在最长时间内不再被访问最长时间内不再被访问的页面。的页面。它是一种理想化的算法，性能最好，但在实它是一种理想化的

50、算法，性能最好，但在实际上难于实现。际上难于实现。要确定哪一个页面是未来最长时间内不再被要确定哪一个页面是未来最长时间内不再被访问的，目前来说是很难估计的，所以该算访问的，目前来说是很难估计的，所以该算法通常用来评价其它算法的性能。法通常用来评价其它算法的性能。55 假定系统为某进程分配了三个物理块，假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串。并考虑有以下的页面号引用串。 1 2 3 4 5 6 7 8 9 1011121314151617181920217 0 1 2 0 3 0 4 2 3 0 3122 0 1 1 7101720717034238 91002145023