《操作系统第八章.ppt》由会员分享，可在线阅读，更多相关《操作系统第八章.ppt（71页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、虚拟内存虚拟内存第第 8 章章1虚拟存储器管理技术虚拟存储器管理技术 固定分区、动态分区、简单分页和简单分段的存储器固定分区、动态分区、简单分页和简单分段的存储器管理方式，有一个共同的特点，即要求将一个作业全管理方式，有一个共同的特点，即要求将一个作业全部装入内存才能运行。如果有的部装入内存才能运行。如果有的作业很大，其所要求作业很大，其所要求的内存空间超过了内存总容量的内存空间超过了内存总容量，作业就不能全部被装，作业就不能全部被装入内存，致使该作业无法运行；有时大量作业要求运入内存，致使该作业无法运行；有时大量作业要求运行，但由于内存容量不足以容纳所有这些作业，只能行，但由于内存容量不足以
2、容纳所有这些作业，只能将少数作业装入内存让它们先运行，而将其它大量的将少数作业装入内存让它们先运行，而将其它大量的作业留在外存上等待。作业留在外存上等待。显而易见的一种解决方法，是从物理上增加内存容量，显而易见的一种解决方法，是从物理上增加内存容量，但这往往会受到机器自身的限制，而且增加了系统成但这往往会受到机器自身的限制，而且增加了系统成本。本。另一种方法是另一种方法是从逻辑上扩充内存容量，这正是虚拟存从逻辑上扩充内存容量，这正是虚拟存储技术所要解决的主要问题储技术所要解决的主要问题。2内存分区技术的关键突破内存分区技术的关键突破进程对内存访问的逻辑地址在运行时动态地进程对内存访问的逻辑地址
3、在运行时动态地被转换为物理地址，从而保证进程可以占据被转换为物理地址，从而保证进程可以占据内存的不同区域（地址重定位机制）。内存的不同区域（地址重定位机制）。一个进程可以划分成许多块，在运行时，这一个进程可以划分成许多块，在运行时，这些块不需要连续地位于主存中些块不需要连续地位于主存中（分页或分（分页或分段机制）。段机制）。一个进程在执行的过程中，不需要所有的块一个进程在执行的过程中，不需要所有的块都在内存中（虚拟内存机制）。都在内存中（虚拟内存机制）。3引入虚拟内存机制之后进程的执行引入虚拟内存机制之后进程的执行首先，操作系统仅读取程序开始处的一些块。首先，操作系统仅读取程序开始处的一些块。
4、常驻集常驻集(Resident set)进程执行中任何时候都进程执行中任何时候都在主存的部分在主存的部分当处理器需要访问一个不在主存中的块时，系统将当处理器需要访问一个不在主存中的块时，系统将产生一个内存访问故障中断（缺页中断）。产生一个内存访问故障中断（缺页中断）。操作系统将该进程置为阻塞状态，并取得控制权。操作系统将该进程置为阻塞状态，并取得控制权。操作系统需要将该进程块取进内存操作系统需要将该进程块取进内存产生一个磁盘产生一个磁盘 I/O读请求读请求执行执行I/O操作期间，操作系统可选择另一个进程操作期间，操作系统可选择另一个进程来运行来运行当当I/O操作完成后，则产生一个操作完成后，则
5、产生一个I/O中断，控制权中断，控制权又交回操作系统，操作系统将之前被阻塞的进程又交回操作系统，操作系统将之前被阻塞的进程置为就绪状态置为就绪状态4虚拟存储技术的优点虚拟存储技术的优点内存中可以容纳更多的进程内存中可以容纳更多的进程每个进程只有一部分的数据块读入内存，其每个进程只有一部分的数据块读入内存，其他数据块仍保存在磁盘上他数据块仍保存在磁盘上内存可以容纳更多的进程，并发性得到更大内存可以容纳更多的进程，并发性得到更大的提高，从而也使得处理器得到了更有效的的提高，从而也使得处理器得到了更有效的利用利用进程可以比主存的全部空间还大进程可以比主存的全部空间还大实存实存(Real memory
6、)：内存：内存虚存虚存(Virtual memory)：磁盘的存储空间：磁盘的存储空间5虚拟存储器的基本概念虚拟存储器的基本概念 1 1局部性原理局部性原理(principle of locality)虚拟存储器系统实现的理论基础：程序执行的局部性规律。虚拟存储器系统实现的理论基础：程序执行的局部性规律。早早在在19681968年年P PDenningDenning就就指指出出过过，程程序序在在执执行行时时将将呈呈现现出出局局部部性性规规律律，即即在在一一段段时时间间内内，程程序序的的执执行行仅仅局局限限于于某某个个部部分分；相应地，它所访问的存储空间也局限于某个区域内。相应地，它所访问的存储
7、空间也局限于某个区域内。出现局部性规律的原因：出现局部性规律的原因：程程序序在在执执行行时时，除除了了少少部部分分的的转转移移和和过过程程调调用用指指令令外外，大大多数仍是顺序执行的。多数仍是顺序执行的。子子程程序序调调用用将将会会使使程程序序的的执执行行由由一一部部分分内内存存区区域域转转至至另另一一部部分分区区域域。但但在在大大多多数数情情况况下下，过过程程调调用用的的深深度度都都不不超超过过5 5。程序中存在许多循环结构，循环体中的指令被多次执行。程序中存在许多循环结构，循环体中的指令被多次执行。程程序序中中还还包包括括许许多多对对数数据据结结构构的的处处理理，如如对对连连续续的的存存储
8、储空空间间数组的访问，往往局限于很小的范围内。数组的访问，往往局限于很小的范围内。6局部性原理局部性原理时间局限性时间局限性：如果程序中的某条指令一旦执行，：如果程序中的某条指令一旦执行，则不久的将来该指令可能再次被执行；如果某个则不久的将来该指令可能再次被执行；如果某个存储单元被访问，则不久以后该存储单元可能再存储单元被访问，则不久以后该存储单元可能再次被访问。产生时间局限性的典型原因是在程序次被访问。产生时间局限性的典型原因是在程序中存在着大量的循环操作。中存在着大量的循环操作。空间局限性空间局限性：一旦程序访问了某个存储单元，则：一旦程序访问了某个存储单元，则在不久的将来，其附近的存储单
9、元也最有可能被在不久的将来，其附近的存储单元也最有可能被访问。访问。即程序在一段时间内所访问的地址，可能即程序在一段时间内所访问的地址，可能集中在一定的范围内，其典型原因是程序是顺序集中在一定的范围内，其典型原因是程序是顺序执行的。执行的。局部性原理确保了虚拟存储机制的可行性。但利局部性原理确保了虚拟存储机制的可行性。但利用局部性原理的同时，要避免系统出现用局部性原理的同时，要避免系统出现抖动现象抖动现象（thrashing），即处理器大部分时间都用于交），即处理器大部分时间都用于交换块，而不是执行指令。换块，而不是执行指令。72.虚拟存储器实现的软硬件支撑虚拟存储器实现的软硬件支撑硬件支撑硬
10、件支撑有相当容量的辅存（磁盘）以存放所有并发作业的地址有相当容量的辅存（磁盘）以存放所有并发作业的地址空间空间有一定容量的内存来存放运行作业的部分程序有一定容量的内存来存放运行作业的部分程序有支持分页或分段的硬件有支持分页或分段的硬件请求分页系统和请求分段系统请求分页系统和请求分段系统动态地址转换机构动态地址转换机构软件支撑软件支撑操作系统能提供页或段在主存和辅存之间有效交换的管操作系统能提供页或段在主存和辅存之间有效交换的管理模块理模块读取策略、放置策略、替换策略、驻留集管理、清除策略等读取策略、放置策略、替换策略、驻留集管理、清除策略等83.虚拟存储器的特征虚拟存储器的特征离散性离散性：指
11、在内存分配时采用离散的分配方式，它是虚指在内存分配时采用离散的分配方式，它是虚拟存储器的最基本的特征。拟存储器的最基本的特征。多次性：多次性：指一个作业被分成多次调入内存运行，即在作指一个作业被分成多次调入内存运行，即在作业运行时没有必要将其全部装入，只须将当前要运行的业运行时没有必要将其全部装入，只须将当前要运行的那部分程序和数据装入内存即可。多次性是虚拟存储器那部分程序和数据装入内存即可。多次性是虚拟存储器最重要的特征。最重要的特征。对换性：对换性：指允许在作业的运行过程中在内存和外存的对指允许在作业的运行过程中在内存和外存的对换区之间换进、换出。换区之间换进、换出。虚拟性：虚拟性：指能够
12、从逻辑上扩充内存容量，使用户所看到指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。的内存容量远大于实际内存容量。9请求分页存储管理系统请求分页存储管理系统请求分页请求分页存储管理系统是存储管理系统是在纯分页系统的在纯分页系统的基础上，增加了请求调页功能、页面置换基础上，增加了请求调页功能、页面置换功能所形成的页式虚拟存储系统功能所形成的页式虚拟存储系统，它是目，它是目前常用的一种虚拟存储器的方式。前常用的一种虚拟存储器的方式。它允许只装入若干页它允许只装入若干页(而非全部页而非全部页)的用户的用户程序和数据，便可启动运行。以后，再通程序和数据，便可启动运行。以后，再通过调
13、页功能及页面置换功能，陆续地把即过调页功能及页面置换功能，陆续地把即将要运行的页面调入内存，同时把暂不运将要运行的页面调入内存，同时把暂不运行的页面换出到外存上，置换时以页面为行的页面换出到外存上，置换时以页面为单位。单位。10为为了了能能实实现现请请求求调调页页和和置置换换功功能能，系系统统必必须须提提供供必必要要的的硬件支持：硬件支持：扩扩充的充的页页表机制和缺表机制和缺页页中断机构。中断机构。（1 1）请求分页的页表机制请求分页的页表机制 它它是是在在纯纯分分页页的的页页表表机机制制上上形形成成的的，由由于于只只将将应应用用程程序序的的一一部部分分调调入入内内存存，还还有有一一部部分分仍
14、仍在在磁磁盘盘上上，故故需需在在页页表表中中再再增增加加若若干干项项，供供程程序序(数数据据)在在换换进进、换换出出时参考。在请求分页系统中的每个页表项如图所示。时参考。在请求分页系统中的每个页表项如图所示。1.请求分页中的硬件支持请求分页中的硬件支持 页号页号 物理块号物理块号 状态位状态位P 访问字段访问字段A 修改位修改位M 外存地址外存地址11其中各字段说明如下：其中各字段说明如下：状态位（中断位状态位（中断位P P）：用于指示该页是否已调入内存，供程用于指示该页是否已调入内存，供程序访问时参考。序访问时参考。访问字段访问字段A A：用于记录本页在一段时间内被访问的次数，或用于记录本页
15、在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面最近已有多长时间未被访问，提供给置换算法选择换出页面时参考。时参考。修改位修改位M M：表示该页在调入内存后是否被修改过。由于内存表示该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本，因此，若未被修改，中的每一页都在外存上保留一份副本，因此，若未被修改，在置换该页时就不需将该页写回到外存上，以减少系统的开在置换该页时就不需将该页写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写到外销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新
16、副本。存上，以保证外存中所保留的始终是最新副本。外存外存(辅辅存存)地址地址：用于指出：用于指出该页该页在外存上的地址，通常是物在外存上的地址，通常是物理理块块号，供号，供调调入入该页时该页时使用使用 12(2)(2)缺页中断机构缺页中断机构 在在请请求求分分页页系系统统中中，每每当当所所要要访访问问的的页页面面不不在在内内存存时时，便便要要产产生生缺缺页页中中断断，请请求求OSOS将将所所缺缺页页调调入入内内存存。与一般中断的主要区别在于：与一般中断的主要区别在于：缺缺页页中中断断在在指指令令执执行行期期间间产产生生和和处处理理中中断断信信号号，而而一般中断在一条指令执行完后检查和处理中断信
17、号。一般中断在一条指令执行完后检查和处理中断信号。缺缺页页中中断断返返回回到到该该指指令令的的开开始始重重新新执执行行该该指指令令，而而一般中断返回到该指令的下一条指令执行。一般中断返回到该指令的下一条指令执行。一条指令在执行期间，可能产生多次缺页中断。一条指令在执行期间，可能产生多次缺页中断。13保存该进程页表保存该进程页表的起始地址的起始地址(3)(3)地址变换机构地址变换机构14请求分页存储管理系统带来的新问题请求分页存储管理系统带来的新问题每个进程都有一个页表，页表保存在哪里？每个进程都有一个页表，页表保存在哪里？一个一个2GB(231)的进程，如果页大小为的进程，如果页大小为512B
18、(29)，则需要的页表项为，则需要的页表项为222页表占据了大量的空间，应该保存在虚存上，可使页表占据了大量的空间，应该保存在虚存上，可使用多级页表结构用多级页表结构每个虚存访问会引起两次物理内存访问，导致每个虚存访问会引起两次物理内存访问，导致存储器访问时间加倍存储器访问时间加倍第一次取相应的页表项第一次取相应的页表项第二次取需要数据第二次取需要数据可使用快表机制来解决可使用快表机制来解决1532位地址的两级页表结构位地址的两级页表结构1617快表（快表（Translation Lookaside Buffer，TLB）为为了了提提高高地地址址变变换换的的速速度度，增增设设了了一一个个具具有
19、有按按内内容容查查找找、并并行行查查询询功功能能的的特特殊殊的的高高速速缓缓冲冲存存储储器器，称称为为 “快快表表”，或或称称为为“关关联联存存储储器器(TLB,TLB,转转换换后后备备缓缓冲冲器器)”)”，用用以以存存放放当当前前访访问问的的那那些页表项，每个页表项包括页号和相应的块号（页号不能省略）。些页表项，每个页表项包括页号和相应的块号（页号不能省略）。引入快表之后的存储访问修改如下：引入快表之后的存储访问修改如下：处理器首先将逻辑地址中的页号与处理器首先将逻辑地址中的页号与TLB中的各页表项中的各页表项的页号进行比的页号进行比较较如果有相同的如果有相同的(TLB命中命中)，则直接从则
20、直接从TLB的输出寄存器输出相应的输出寄存器输出相应的块号的块号如果没有找到如果没有找到(TLB不命中不命中)，则访问内存从该进程的页表中查找，则访问内存从该进程的页表中查找检查该页是否在内存中检查该页是否在内存中(检查检查P位位)如果不在，则发生缺页中断如果不在，则发生缺页中断页访问之后，同时要将该页的页表项读入页访问之后，同时要将该页的页表项读入TLB181920P239 P239 图图8.88.8 缺页中断处理缺页中断处理 是 否 否 是 是 否 产生缺页中产生缺页中 否 是 断请求调页断请求调页 否否 是 开始（程序请求访问一页开始（程序请求访问一页)越界中断越界中断CPU检索快表检索
21、快表页页表表项项是是否否在在快快表表中中？访问页表访问页表页是否在内存中？页是否在内存中？修改快表修改快表修改访问位和修改位修改访问位和修改位形成物理地址形成物理地址 地址变换地址变换结束结束保留保留CPU现场现场 从外存中找到缺页从外存中找到缺页 页页号号页页表表长长度度？内存满否？内存满否？选择一页换出选择一页换出 该页是否被修改？该页是否被修改？将该页写回外存将该页写回外存 将一页从外存换入内存将一页从外存换入内存 修改页表修改页表 CPU从外存读缺页从外存读缺页 启动启动I/O硬件硬件 21快表访问示例快表访问示例假设检索快表的时间假设检索快表的时间T TTLBTLB为为2020nsn
22、s，访问内存的访问内存的时间时间T TM M为为100100nsns，TLBTLB的命中率的命中率p p为为90%90%。计算。计算CPUCPU存取内存一个数据的平均时间。存取内存一个数据的平均时间。解：解：1）快表命中时）快表命中时CPU存取内存一个数据的时间为存取内存一个数据的时间为T1检检索索快快表表时时间间访访问问内内存存数数据据时时间间=T TTLBTLB+T TM M=20100120ns。2）当快表不命中时）当快表不命中时CPU存取内存一个数据的时间为存取内存一个数据的时间为T2检检索索快快表表时时间间检检索索内内存存中中的的页页表表时时间间访访问问内内存数据时间存数据时间=T
23、TTLBTLB+T TM M+T TM M 20100100220ns。3)CPU3)CPU存取内存一个数据的平均时间为存取内存一个数据的平均时间为 T=T1*T=T1*命中率命中率+T2*T2*（1 1命中率）命中率）=T1*P+T2*(1-P)=T1*P+T2*(1-P)=120*0.9+220*0.1=130ns120*0.9+220*0.1=130ns。22存储器存储器Cache23页大小页大小页越小，内部碎片的总页越小，内部碎片的总量越少量越少页越小，每个进程所需页越小，每个进程所需的页数增加，则需要更的页数增加，则需要更大的页表大的页表内存和辅存之间以页为内存和辅存之间以页为单位进
24、行数据交换，从单位进行数据交换，从辅存的角度来看，希望辅存的角度来看，希望页比较大，从而实现更页比较大，从而实现更有效的数据块传送有效的数据块传送24例题例题 例例11某某虚虚拟拟存存储储器器的的用用户户编编程程空空间间共共3232个个页页面面，每每页页1 1KBKB，主主存存为为1616KBKB。假假定定某某时时刻刻用用户户页页表表中中已已调调入入主主存存的的页页面面的的虚虚拟拟页页号号和和物物理理页页表表对对照照表表为为表表一一，则则下下表表中中与与虚虚拟拟地地址址相相对对应应的的物物理理地地址址为为表表二二（如如果果主主存存找找不不到到，即即为为该该页页失失效效）。虚虚拟拟存存储储的的功
25、功能能是是由由C C完完成成的的。在在虚虚拟拟存存储储系系统统中中，采采用用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 25供选择的答案：供选择的答案：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：高
26、速辅助存贮器高速辅助存贮器 高速光盘存贮器高速光盘存贮器 快速通道快速通道 高速缓冲存贮器高速缓冲存贮器E E：连接编辑连接编辑 虚地址分配虚地址分配 动态地址映射动态地址映射 动态连接动态连接答案：答案：A B C D E 26解解：每每页页大大小小 1 1KBKB，用用1616进进制制表表示示为为400400H H，由由虚虚地地址址通通过过直接映象的地址转换成物理地址步骤如下：直接映象的地址转换成物理地址步骤如下：将虚地址分离成页号将虚地址分离成页号p p和页内地址和页内地址d d：页页号号p p（虚虚地地址址页页大大小小）取取整整（0 0A5CH/400HA5CH/400H）取取整整2
27、2(0 0A5CH=000010 0101011011)A5CH=000010 0101011011)页页内内地地址址d d虚虚地地址址页页号号pp每每页页大大小小0 0A5C(H)A5C(H)2400(H)2400(H)25C(H)(0101011011)25C(H)(0101011011)根据页号查页表，由页号根据页号查页表，由页号 p p2 2查页表得物理页号为查页表得物理页号为4 4将将物物理理页页号号和和页页内内地地址址构构成成物物理理地地址址物物理理页页号号页页大大小页内地址小页内地址4400(4400(H)H)25C(H)25C(H)125C(H)125C(H)(000100 0
28、101011011)(000100 0101011011)同理虚拟地址同理虚拟地址1 1A5CHA5CH分离成页号分离成页号P P6 6和页内位移和页内位移1515CH.CH.查页表知该页不在内存，页失效产生缺页中断调入内存。查页表知该页不在内存，页失效产生缺页中断调入内存。278.1.3 请求分段存储管理请求分段存储管理在在简简单单分分段段系系统统的的基基础础上上实实现现的的虚虚拟拟存存储储器器，是是以分段为单位进行换入、换出的。以分段为单位进行换入、换出的。在在程程序序运运行行之之前前只只要要先先调调入入若若干干个个分分段段（不不必必调调入所有的分段），便可启动运行。入所有的分段），便可启
29、动运行。当当所所访访问问的的段段不不在在内内存存时时可可请请求求OSOS将将所所缺缺的的段段调调入内存。入内存。为为实实现现请请求求分分段段存存储储管管理理方方式式，同同样样需需要要一一定定的的硬硬件件支支持持和和相相应应的的软软件件，有有段段表表机机制制、缺缺段段中中断断机构以及地址变换机构。机构以及地址变换机构。281 1段表机制段表机制 在在请请求求分分段段式式管管理理中中在在段段表表中中增增加加若若干干项项，以以供供程程序序在调进、调出时参考。请求分段的段表项如下：在调进、调出时参考。请求分段的段表项如下：存取方式：用于标识本分段的存取属性是只执行、只读，还是允存取方式：用于标识本分段
30、的存取属性是只执行、只读，还是允许读写。许读写。访问字段访问字段A A：用于记录该段被访问的频繁程度。用于记录该段被访问的频繁程度。修改位修改位M M：用于表示该段进入内存后，是否已被修改过。用于表示该段进入内存后，是否已被修改过。存在位存在位P P：说明本段是否已调入内存。说明本段是否已调入内存。增补位：用于表示本段在运行过程中，是否进行过动态增长。增补位：用于表示本段在运行过程中，是否进行过动态增长。外存起址：指示本段在外存中的起始地址，即起始盘块号。外存起址：指示本段在外存中的起始地址，即起始盘块号。段段 段段 段的段的 存取存取 访问访问 修改修改 存在存在 增补增补 外存外存名名 长
31、长 基址基址 方式方式 字段字段A A 位位M M 位位P P 位位 起址起址292.2.缺段中断机构缺段中断机构在请求分段系统中，采用的是请求调段策略。在请求分段系统中，采用的是请求调段策略。类同缺页中断机构，当进程所要访问的段未调类同缺页中断机构，当进程所要访问的段未调入内存时，便由缺段中断机构在硬件指令中间入内存时，便由缺段中断机构在硬件指令中间产生一缺段中断信号，由缺段中断处理程序将产生一缺段中断信号，由缺段中断处理程序将所需的段调入内存。所需的段调入内存。与缺页中断机构不同的是由于各段长不同，置与缺页中断机构不同的是由于各段长不同，置换时对内存的管理采用换时对内存的管理采用动态分区管
32、理动态分区管理。30段表起始地址段表起始地址3 3 地址变换机构地址变换机构318.1.4 段页式存储管理段页式存储管理 分分页页和和分分段段存存储储管管理理方方式式都都各各有有其其优优缺缺点点。如如果果对对两两种种存存储储管管理理方方式式“各各取取所所长长”后后，则则可可以以形形成成一一种新的存储管理方式的系统种新的存储管理方式的系统段页式系统。段页式系统。它它以以分分页页的的方方式式管管理理内内存存，具具有有分分页页系系统统能能有有效效地地提提高高内内存存利利用用率率的的优优点点；又又以以分分段段的的方方式式管管理理用用户户的的逻逻辑辑地地址址空空间间，具具有有分分段段系系统统能能很很好好
33、地地满满足足用用户户需要的长处需要的长处，显然是一种比较有效的存储管理方式。，显然是一种比较有效的存储管理方式。Q：它它有有没没有有碎碎片片问问题题？如如果果有有的的话话，是是内内部部还还是是外外部碎片？部碎片？321 1基本原理基本原理 将将内内存存空空间间划划分分成成大大小小相相同同的的若若干干个个块块，将将用用户户程程序序先先按按逻逻辑辑完完整整性性分分为为若若干干个个段段，并并为为每每个个段段赋赋予予一一个个段段名名，再再把把每每个个段段划划分分成成若若干干个个与与块块大大小小相相同同的的页页，将将这这些些页页离散装入不相离散装入不相邻邻接的接的块块中。中。如如下下图图：一一个个作作业
34、业有有四四个个段段，页页面面大大小小为为4 4K K，四四个个段段的的页页面面数数分分别别为为4 4、2 2、2 2、2 2，总总页页面面数数为为1010页页，此此时时每每一一页页都都属于属于逻辑逻辑上完整的一个段。上完整的一个段。段段页页式式系系统统中中的的地地址址结结构构由由段段号号、段段内内页页号号和和页页内内地地址址三部分三部分组组成。成。在在段段页页式式系系统统中中，为为了了实实现现从从逻逻辑辑地地址址到到物物理理地地址址的的变变换换，系系统统中中必必需需同同时时配配置置段段表表和和页页表表。由由于于将将段段中中的的页页进进行行离离散散地地分分配配，段段表表中中的的内内容容不不再再是
35、是段段的的内内存存始始址址和和段段长长，而是，而是页页表始址和表始址和页页表表长长度。度。段号（段号（S）段内页号（段内页号（P）页内地址（页内地址（W）33段页式系统的作业地址空间段页式系统的作业地址空间 34利用段表和页表实现地址映射利用段表和页表实现地址映射段号状态 页表大小 页表始址01112130段 表段表大小段表始址页号状态 存储块号01112130 页 表页号状态 存储块号0111 页 表35页表的基址页表的基址2 2 地址变换机构地址变换机构36地址变换过程地址变换过程1.1.系系统统将将逻逻辑辑地地址址截截成成段段号号S S、段段内内页页号号P P与与页页内内地地址址W W，
36、先先用用段段号号S S与与段段长长TLTL（存存在在段段表表寄寄存存器器中中）进进行行比比较较。若若 STLSTL，表表示示段段号号太太大大，访访问问越越界界，于于是是产产生生越越界界中断信号；中断信号；2.2.若若S STLTL，表表示示未未越越界界，于于是是利利用用段段表表始始址址（存存在在段段表表寄寄存存器器中中）和和段段号号求求出出该该段段对对应应的的段段表表项项在在段段表表中中的的位置，从中得到位置，从中得到该该段的段的页页表始址；表始址；3.3.利利用用逻逻辑辑地地址址中中的的段段内内页页号号P P来来获获得得对对应应页页的的页页表表项项在在页页表表中中位位置置，判判断断状状态态P
37、 P位位，若若P P位位为为0 0表表示示该该页页不不在在内内存中，存中，产产生缺生缺页页中断；中断；4.4.若若P P位位为为1 1，则则从从中中读读出出该该页页所所在在的的物物理理块块号号b b，再再用用块块号号b b和和页页内地址内地址W W拼成物理地址。拼成物理地址。37Q Q：段段页页式式系系统统中中，为为了了获获得得一一条条指指令令或或数数据据，需需要要访访问几次内存？问几次内存？需访问三次内存：需访问三次内存：第一次访问内存中的段表，从中取得页表始址；第一次访问内存中的段表，从中取得页表始址；第第二二次次访访问问内内存存中中的的页页表表，从从中中取取出出该该页页所所在在的的物物理
38、理块块号号，并将该块号与页内地址一起形成指令或数据的物理地址；并将该块号与页内地址一起形成指令或数据的物理地址；第三次访问才是真正根据所得的物理地址取出指令或数据。第三次访问才是真正根据所得的物理地址取出指令或数据。如何提高速度？如何提高速度？在在地地址址变变换换机机构构中中增增设设一一高高速速缓缓冲冲寄寄存存器器（如如TLBTLB），记记录录最最近近访访问问过过的的地地址址信信息息。每每次次访访问问它它时时，都都同同时时利利用用段段号号和和页页号去检索高速缓存。号去检索高速缓存。388.2 操作系统软件操作系统软件是否使用虚拟内存技术？是否使用虚拟内存技术？使用分页、分段还是段页式？使用分页
39、、分段还是段页式？采用何种算法来进行存储管理？采用何种算法来进行存储管理？所有算法的核心都是尽可能使缺页频率最小所有算法的核心都是尽可能使缺页频率最小读取策略读取策略放置策略放置策略替换策略替换策略驻留集管理驻留集管理清除策略清除策略39取策略取策略(Fetch Policy)确定何时将一页取入内存。确定何时将一页取入内存。请求式页面调度请求式页面调度(Demand paging)：当需要访当需要访问该页中的一个单元时才将其读入内存。问该页中的一个单元时才将其读入内存。当进程第一次启动时，将发生大量的缺页当进程第一次启动时，将发生大量的缺页预约式页面调度预约式页面调度(Prepaging)：将
40、那些预计在不将那些预计在不久的将来会被访问的程序或数据所在的页面，预久的将来会被访问的程序或数据所在的页面，预先调入内存。先调入内存。由于预测的准确率不高（由于预测的准确率不高（50%50%），所以这种策略），所以这种策略主要用于进程的首次调入。主要用于进程的首次调入。40放置策略放置策略(Placement Policy)确定一个进程块到底放在内存的哪个位确定一个进程块到底放在内存的哪个位置。置。分段系统需要考虑（最佳适配、首次适配、分段系统需要考虑（最佳适配、首次适配、邻近适配、最差适配）邻近适配、最差适配）分页或段页式系统中不需要考虑，因为在内分页或段页式系统中不需要考虑，因为在内存中的
41、每一块大小都是相同的，只要放置在存中的每一块大小都是相同的，只要放置在空闲块即可空闲块即可41替换策略替换策略(Replacement Policy)读取一个新页时，应该替换内存中的哪一页读取一个新页时，应该替换内存中的哪一页?在进程运行过程中，如果发生缺页，此时内在进程运行过程中，如果发生缺页，此时内存中又无空闲块时，为了保证进程能正常运存中又无空闲块时，为了保证进程能正常运行，就必须从内存中调出一页到磁盘。行，就必须从内存中调出一页到磁盘。页面置换算法的性能指标：页面置换算法的性能指标：缺页率（缺页率（page fault rate）=“缺页次数缺页次数/内存访问次数内存访问次数”(比率比
42、率)从理论上讲，应将那些以后不再被访问的页从理论上讲，应将那些以后不再被访问的页面换出，或把那些在较长时间内不会再被访面换出，或把那些在较长时间内不会再被访问的页面换出。问的页面换出。基于以前的行为去预测以后的访问行为。基于以前的行为去预测以后的访问行为。42基本的替换算法基本的替换算法1.最佳最佳(Optimal policy,OPT)选择那些永不使用的，或者是在最长选择那些永不使用的，或者是在最长时间内不再被访问的页面置换出去时间内不再被访问的页面置换出去。它是一种理想化的算法，性能最好，它是一种理想化的算法，性能最好，但在实际上难于实现。但在实际上难于实现。要确定哪一个页面是未来最长时间
43、内要确定哪一个页面是未来最长时间内不再被访问的，目前来说是很难估计的，不再被访问的，目前来说是很难估计的，所以该算法通常用来评价其它算法的性所以该算法通常用来评价其它算法的性能。能。43最佳（最佳（OPTOPT）置换算法置换算法例：假定系统为某进程分配了三个物理块，并考虑例：假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：有以下的页面号引用串：7 7，0 0，l l，2 2，0 0，3 3，0 0，4 4，2 2，3 3，0 0，3 3，2 2，l l，2 2，0 0，l l，7 7，0 0，1 1。如下如下图图所示，所示，进程运行时先将进程运行时先将7 7，0 0，1 1三个页
44、面装入内三个页面装入内存。当进程访问页面存。当进程访问页面2 2时，产生缺页中断，此时时，产生缺页中断，此时OSOS根据最佳置换算法，页面根据最佳置换算法，页面7 7将在第将在第1818次才被访问，次才被访问，是三页中最久不被访问的页面，所以被淘汰。接是三页中最久不被访问的页面，所以被淘汰。接着访问页面着访问页面0 0时，发现已在内存中，而不会产生缺时，发现已在内存中，而不会产生缺页中断，以此类推。页中断，以此类推。从从图可以看出，采用最佳置图可以看出，采用最佳置换算法，只发生了换算法，只发生了6 6次页面置换，次页面置换，9 9次缺页中断。次缺页中断。44利用最佳（利用最佳（OPTOPT）置
45、换算法的置换图置换算法的置换图452.先进先出（先进先出（FIFO）置换算法置换算法实用的置换算法实用的置换算法,关键是如何以过去页面走向来预测将关键是如何以过去页面走向来预测将来的页面走向，以达到最佳置换算法。来的页面走向，以达到最佳置换算法。FIFOFIFO算法认为最先进入内存的页面，其不再使用的可算法认为最先进入内存的页面，其不再使用的可能性比最近调入的页面要大。所以该算法总是淘汰最能性比最近调入的页面要大。所以该算法总是淘汰最先进入内存的页面，即先进入内存的页面，即选择在内存中驻留时间最久的选择在内存中驻留时间最久的页面予以淘汰页面予以淘汰。算法实现简单，只须把一个进程已调入内存的页面
46、，算法实现简单，只须把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个循环替换指按先后次序链接成一个队列，并设置一个循环替换指针即可。针即可。是一种最直观的算法，但性能最差，有是一种最直观的算法，但性能最差，有BeladyBelady异常现异常现象象。46利用利用FIFOFIFO置换算法的置换表置换算法的置换表(设置一个循环替换指针设置一个循环替换指针)发生了发生了12次页面替换，共次页面替换，共15次缺页次缺页47Belady 现象采用采用FIFOFIFO算法时，如果对一个进程未分配它所要算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现求的全部页面，有时就会出现分配
47、的页面数增多，分配的页面数增多，缺页率反而提高的异常现象缺页率反而提高的异常现象。对页面访问序列对页面访问序列A B C D A B E A B C D E A B C D A B E A B C D E，分分配配3 3块物理块时，缺页次数为块物理块时，缺页次数为9 9次；分配次；分配4 4块物理块块物理块时，缺页次数反而为时，缺页次数反而为1010次。次。原因在于刚换出去的页马上又被访问到。原因在于刚换出去的页马上又被访问到。483.最近最久未使用置换算法最近最久未使用置换算法 （Least Recently Used，LRU）该算法是该算法是选择最近最久未使用的页面予以淘汰选择最近最久未使
48、用的页面予以淘汰，这，这是局部性原理的合理近似，性能接近最佳算法。是局部性原理的合理近似，性能接近最佳算法。但由于需要记录页面使用时间的先后关系，硬件开但由于需要记录页面使用时间的先后关系，硬件开销太大。销太大。系统在每个页面设置一个访问字段，用以记录这个系统在每个页面设置一个访问字段，用以记录这个页面自上次被访问以来所经历的时间页面自上次被访问以来所经历的时间T，当要淘汰当要淘汰一个页面时，选择一个页面时，选择T最大的页面。但在实现时需要最大的页面。但在实现时需要硬件的支持（寄存器或栈）。硬件的支持（寄存器或栈）。49利用利用LRULRU置换算法的置换表置换算法的置换表504.Clock置换
49、算法置换算法最近未用算法最近未用算法NRU（Not Recently Used）ClockClock置置换换算算法法是是一一种种LRULRU的的近近似似算算法法。该该算算法法为为每每个个页页面面设设置置一一位位访访问问位位，将将内内存存中中的的所所有有页页面面都都通通过过链链接接指指针针链链成成一一个个循循环环队队列列，并并设设置置一一个个循循环环替替换换指指针针，指指向向当当前前被被置换页所在块。置换页所在块。当当页页第第一一次次读读入入内内存存时时，其其访访问问位位为为1 1；当当某某页页被被访访问问时时，其访问位置其访问位置1 1。在在选选择择一一页页淘淘汰汰时时，沿沿循循环环替替换换指
50、指针针检检查查页页面面，如如其其访访问问位位是是“0”“0”，就就选选择择该该页页换换出出；若若为为“1”“1”，则则重重新新置置为为“0”“0”，暂暂不不换换出出该该页页，在在循循环环队队列列中中检检查查下下一一个个页页面面，直直到到访访问问位位为为“0”“0”的的页页面面为为止止。由由于于该该算算法法只只有有一一位位访访问问位位，只只能能用用它它表表示示该该页页是是否否已已经经使使用用过过，而而置置换换时时是是将将未未使使用用过过的的页页面面换换出出去去，所所以以把把该该算算法法称称为为最最近近未未用用算算法法NRCNRC（NotNot Recently Used Recently Use