第四章 存储管理 (一 )
主要内容,
4.1、简介
4.2、内存管理
4.3、虚拟存储技术
4.4、辅存管理
4.5、高速缓存管理
4.1、简介
现代计算机的体系结构是以存储器为中心。
存储器的体系结构：同寄存器、高速缓存、主存和辅存等多层体系结构。
本章主要介绍内存分配与管理的原理和策略、辅存信息的组织和管理方法、高速缓存结构和操作方式等内容，以进一步认识和掌握操作系统的存储器管理原理和方法，提高计算机系统的利用率。
4.2、内存管理
1、内存管理简介
2、存储管理功能
3、地址重定位
4、存储管理方法
1、内存管理简介在单道程序系统中：主存划分成两部分，
一部分供操作系统使用，一部分供当前正在执行的程序使用。
多道程序系统中：存储器的“用户”部分必须进一步地细分，以适应多个进程的要求。
Windows2000内存管理器位于 Ntoskrnl.exe文件中。
在硬件抽象层（ HAL）中没有内存管理器的任何部分。
内存管理器由以下几个部分组成：
1）、一组执行程序系统服务程序，用于虚拟内存的分想、释放和管理，它们中的大多数通过 Win32API或核心态的设备驱动程序接口形式出现。
2）、一个转换无效和访问错误陷阱处理程序，
用于解决硬件检测到的内存管理异常事件，并代表一个进程的虚拟页驻留。
3）、运行在 6个不同内核模式系统线程的环境中的几个关键组件。
2、存储管理功能
一、存储管理的体系统结构
主存的功能：存放内核和用户程序的指令和数据，每一项信息都存放在主存的特定位置上。
信息在主存是按“位”存放的。
为了能对信息进行访问，要对这些位置进行编号，这些编号称为“地址”。
计算机的三级存储结构：
辅存
内存
高速缓存二、主存储器管理功能
1）、主存分配：可以使多个程序同时驻留在主存中，以提高处理器的利用率。
2）、地址转换和重定位：即能运行与机器无关的代码
3）、存储保护和主存共享：研究如何保护各存储区中信息不被破坏和偷窃。
4）、存储扩充：运行的程序应不受主存大小的限制，理想情况下应能运行任意大小的程序。
3、地址重定位
重定位：处于主存中的程序，一旦被换出，下次换出时，不一定装在同一区域中，因此为了保证作业的正确执行，必须根据分配给作业的主存空间对作业中指令和数据的存放地址进行重定位，即要把逻辑地址转换成绝对地址。
一、逻辑组织
1）、计算机中存储数据的方式：计算机系统中的主存总是被组织成线性的或一维的地址空间，此空间由一系列字节或字组成，辅存在物理层上也是按类似方式组织的。
2）、程序存在的方式：模块、及某种机制
逻辑地址：用户程序中使用的地址被为逻辑地址，由逻辑地址对应的存储空间称逻辑地址空间。
二、物理组织
1）、计算机存储器至少被组织成两级称作主存和辅存
2）、物理地址：程序和数据存放在存储器上位置相应的地址
3）、由物理地址对应的存储空间
在主存和辅助之间移动信息是系统的责任，这个任务是存储器管理的本质所在。
三、保护
每个进程都应该受到保护,以免其他进程有意或无意的干涉，因此，必须在运行时检查一个进程产生的所有存储访问，以确保它们只访问了分配给进程的存储空间。
采用的方法：通常，用户进程不能访问操作系统的任何部分，不论是程序还是数据。再者，
一个进程中的程序通常不能分支到另一个进程中的指令。如果没有特别的安排，一个进程中的程序不能访问另一个进程的数据区。处理器必须能够在执行时取消这样的指令。
四、共享
任何保护机制必须具有一定的灵活性，
以允许多个进程访问主存的同一部分。
例：如果许多进程正执行同一个程序，
则允许每个进程访问进程的同一个副本要优于让它们有自已单独的副本。在同一个任务上合作的进程可能需要共享访问同一个数据结构。存储器管理系统必须允许对存储器共享区域的受控访问，
并且不能损害本质上的保护。
五、静态重定位
方法：在装入一个作业时，把作业中的指令地址和数据地址全部转换成绝对地址。转换工作是在作业执行前集中一次完成，所以在作业执行过程中就无需再进行地址转换。
注：采用这种方式时，由于装入主存储器的作业信息已经都是用绝对地址指示，
故作业执行过程中是不能移动位置的。
六、动态重定位
方法：是指程序的重定位时机不是在程序执行前进行，而是在程序执行过程中才进行地址转换。更确切的说是在每次访问主存单元前才进行地址转换。
注：采用动态重定位时，由于装入的作业仍保持原来的逻辑地址，所以，必要时可改变它在主存中的再存放区域。
当作业被移到一个新区域时，只要改变定位寄存器的值，使定位寄存器的内容变为新区域的起始地址。这样，在作业执行时，硬件的地址转换机构按照新区域的起始地址与逻辑地址相加，转换成新区域的绝对地址，使作业仍可正确执行。
4、存储管理方法
存储器管理最基本的操作是由处理器把程序装入主存执行。
单用户系统中：内存被分为两个区域，
即系统区和用户区。
多道程序并发执行的系统中：虚拟存储器方案。（分段和分页）
一、固定分区
1）、分区大小：
大小相等的分区：碎片较多
大小不等的分区：碎片相对较小
缺点：都容易产生内部碎片
内部碎片：由于装入的数据块小于分区从而使得分区内部有空间浪费的现象。
2）、放置算法
即选择那个空闲分区给新作业。
对于大小相等的分区：不重要
对于大小不等的分区：把每个进程指定到适应它的最小分区。在这种情况下，
每个分区都需要一个调度队列，用于保存为这个分区换出等待的进程。这种方法优点是可以使一个分区内部浪费的空间（内部碎片）最少。
改进算法：给所有的进程提供一个队列，
当需要把一个进程装入主存时，选择可以保存该进程的最小的分区。如果所有的分区都已占据，则必须进行交换决策。
一般首先考虑换出占据了能保存这个新到进程的最小分区的进程，也可以考虑一些诸如优先权的其他因素，或者选择换出阻塞的进程。
二、动态分区
对于动态分区，分区长度和数目是可变的，当一个进程被装入主存时，正好给它分配所需要的存储空间。
外部碎片：在动态分区的作用下，导致在存储器中出现了许多空闲区。随着时间的推移，存储器中产生了越来越多的碎片，它的利用率也随着下降。
拼接：克服外部碎片的一种技术。即操作系统不时地移动进程，使得它们变得连续，并且使所有自空间连成一片。但压缩是一个非常费时的过程，并且浪费了处理器的时间同时，也意味了程序需要动态重定位。
内碎片和外碎片：
内碎片是占用分区内未被利用的空间，
外碎片是点用分区之间难以利用的空闲分区。
分区式存储管理常采用的一项技术就是内存紧缩，即将各个占用分区向内存的一端移动，然后将各个空闲分区合并成为一个空闲分区。
常用的几种分区分配算法：
1）、首先适配法：
2）、下次适配法：
3）、最佳适配法：
4）、最坏适配法：
三、分页
分页的产生：在分区中提到了主存可以划分成大小相等的许多区，每个区称为一块。与此对应，每个作业也被分成同样大小的作业块。进程中被称作页的块就可以指定存放到存储器的可用块中。
页：是一个相对于逻辑空间的概念是对程序 (作业 )的一种划分。
块：是一个相对物理空间的概念是对主存划分的一种，通常也叫帧。
在使用上页的大小必须和块的大小相对应页式存储管理
页式存储管理就是把主存储器分成大小相等的许多区，每个区称为一块。与此对应，编制程序的逻辑地址也要分成页，
页的大小与块的大小相等。
页式存储管理的逻辑地址由两部分组成：
页号和页内地址。
地址结构确定了主存储器的分块大小，
也就决定了页面的大小。
页和块的用法：
空闲块的管理：操作系统通过列表来维护。存储在磁盘上的作业由几个页组成。
当装入这个作业时，操作系统查找几个空闲块，
并将作业的页装入这几个块中。
操作系统为每个作业维护一个页表。页表给出了该作业的每一页对应的帧位置。
在程序中，每个逻辑地址包括一个页和在该页中的偏移量。
在简单分区的情况下，逻辑地址是一个指令相对于程序的开始处的位置，处理器把它转换成一个物理地址。在分页中，逻辑／物理地址的转换仍然由处理器硬件完成，那么处理器必须知道如何访问当前作业的页表。给出一个逻辑地址（页号＋偏移量），处理器使用页表产生一个物理地址（块号＋偏移量）。
简单分页和固定分区的比较：
相同点：把内存分成多个等份
不同点：它们不同之处在于，对于分页，
分区相当小,一个作业可以占据多个分区，并且这些分区不需要是连续的。
页大小的规定
为了使分页更加方便，可以规定页的大小以及块的大小必须是 2的幂。
原因：
首先是因为逻辑地址方案对程序员、汇编程序和编译器是透明的，程序的每个逻辑地址（页＋偏移量）与它的相对地址是一致的。
其次是因为硬件实现运行时动态地址转换的功能相对比较容易。
例：考虑一个 n+m位的地址，左边的 n位是页号，右边的 m位是偏移量。按定义可以用页号和偏移量表。那么地址转换的步骤如下：
（１）、提取页号，即逻辑地址左边的 n位。
（２）、以这个页号为索引，查找该作业页表中的相应块号Ｋ。
（３）、该块的起始地址为 kＸ２ m，被访问字节的物理地址是这个数加上偏移量。物理地址不需要计算，它可以通过简单地把偏移量添加在块号后面来构造。
简单分页的总结：
主存被分成许多大小相等且很小的帧，每个作业被划分成同样的大小的页；较小的作业需要较少的块，较大的作业需要较多的块；当一个作业被装入时，它的所有页都被装入到可用的块中，
并且建立一个页表。
空闲页表：管理空闲块作业页表：对作业所占块进行登记四、分段
分段：用户按照自已的意愿把一个作业分成若干个段，如程序段和数据段。
段的地址：段内是连续的，从“０”开始
段与段之间的地址不是连续的。
逻辑地址的组成：段号和段内地址；
当地址结构确定后，那么允许作业的最多段数及每段的最大长度也就确定了。
（但并不要求所有程序的所有段都具有相同的长度）
与动态分区的不同,
在分段方案中，一个程序可以占据多个分区，并且这些分区不要求是连续的。
分段消除了内部碎片，但是和动态分区一样，它会的生外部碎片。但是一个作业被分成许多小块，因此外部碎片是很小。
对于使用覆盖方案或使用虚存的情况下，动态分区与分段这两种方法相同和分页的比较：
分页对程序员来讲是不可见的，
分段是通常是可见的，并且作为组织程序和数据的一种方便手段提供程序员。
典型地，程序员或编译器把程序和数据指定到不同的段。基于模块化程序设计的目的，程序或数据可能进一步分成多个段。（这种方法最不方便之处：是程序员必须知道段长度的最大限度）。
大小不等的分段方式的处理办法
结果：逻辑地址和物理地址不再有简单的对应关系。
段表：每个进程都有一个段表，主存的自由块组织到一个列表中。每个段表必须给出相应的段在主存中的起始地址，还必须提供段的长度，以确保不会使用无效地址。当一个作业进入运行状态时，它的段表地址被装入到一个特殊的寄存器，该寄存器由存储器管理硬件使用。
分段管理方式的地址转换的步骤如下：
（１）、提取段号，即逻辑地址左边的段号 n位。
（２）、以这个段号为索引，查找该作业段表中该段的起始物理地址。
（３）、将逻辑地址中的偏移量与段长进行比较，
如果偏移量大于该长度，则该地址无效。
（４）、物理地址为该段的起始地址加上偏移量的和。
简单分段小结：
一个作业被划分成许多段，段的大小不需要相等；当一个作业被调入时，它的所有段都被装入到存储器的可用区域中，
并建立一个段表。
4.3、虚拟存储技术
０、虚拟存储引入的技术支持
1、虚拟存储概念
2、存储管理策略
3,windows 2000虚存管理策略
4,windows 2000内存管理
０、虚拟存储引入的技术支持
１）、分页和分段管理的二个特点：
进程中所有存储访问都是逻辑地址，并可在运行过程中动态转换成物理地址。
进程可以可以划分成许多块，在执行过程中，通过页表和段表进行地址转换，不需要连续的主存空间。
２）、而且进程的执行往往有局部性。一个进程可以被部分换入或换出主存，进程仍能正常执行。
３）、虚拟存储技术：用户编制程序时可以不必考虑主存储器的实际容量，允许用户的逻辑地址空间大于主存的绝对地址空间。对用户来说，好像计算机系统具有一个容量很大的主存。
1、虚拟存储概念
一、局部性和虚拟存储器
二、分页虚拟存储管理
三、分段虚拟存储管理
四、分段和分页组合
五、保护和共享一、局部性和虚拟存储器
１）、问题的提出：
对于一个由很长程序和许多数据组成的大进程，
在任何一段很短的时间内，执行可能会局限在很小的一段程序中，并且可能仅仅会访问一个或两二个数据数组。这样，如果在程序被挂起或被换出前仅仅使用了一部分进程块，那么为该进程装入太多的块显然会带来大量的浪费。
２）、情况分析
在任何时刻，任何一个进程只有一部分块位于存储器中，当程序转移或访问到不在主存中的某一块时，就会引发一个信息，告诉操作系统想要取进的块；此外，未用到的块不需要换入／换出存储器，也可节省一些时间。同时，也可以在存储器中保留更多的进程，提高并发度和资源的利用率。
3）、局部性原理
局部性原理定义：描述了一个进程中程序和数据引用的簇聚性倾向。因此，假设在很短的时间内仅需要进程的一部分块是否合理的，同时，
还可以对在不远的将来可能会需要的块进行明智的猜测，从而避免系统抖动。
为了使虚存实用有效，需要考虑两方面的因素：
（ 1）、必须有对所采用的分页或分段方案进行硬件支持。
（ 2）、操作系统必须有管理页或段在主存和辅存之间移动的软件。
二、分页虚拟存储管理
1）、简单分页的解决方案
简单分页的体系结构：
页表：有四个方面的含义（如图 4-10aP134
P表示对应的页当前是否在主存中。（如果该页在主存中，则这个页表项还包括该页的帧号。）
M是修改位，表示相应页的内容从上一次装入主存中到现在是否已经改变。如果没有改变，则不需要把它当前占据的帧的页写出。
其他控制位：如页的保护和共享等。
帧号：如该页在主存中，则记录了对应的帧号。
简单分页存在的缺陷：
在大多数系统中，每个进程都有一个页表。但是如果某个进程占据大量的虚存空间，如某个进程有接近 231=2GB的虚存空间，如果使用的页的大小是 29=512B，
这意味着此进程需要有 222个页表项，显然用于放置页表的存储空间是无法接受的。
对于大进程使用的解决方法：
大多数虚拟存储器方案都必须在虚存中保存页表，而不是在实存中。也就是说，
页表也和别的页一样都服从页面调度。
当一个进程正在运行时，它的页表至少有一部分必须在主存中，这一部分包括正在运行的页的页表项。
这里注意二点：页表放在虚存中；
对页表的也可以使用局部调度页号 偏移量
P M 其他控制位 长度 段基虚地址页表项 分页段号 偏移量 分段虚地址段表项段号 页号 偏移量虚地址
P M 其他控制位 帧号
P M 其他控制位 帧号
P M 其他控制位 长度 段基页表项页表项分段和分页相结合
pentium处理器的处理方案
在 pentium处理器中使用的两级方案组织大型页表。在这类方案中有一个页目录，每一项指向一个页表，通常一个页表的最大长度被限制成等于一页。 P134图 4-11给出了这种方案地址转换的步骤。
虚地址的前几位用于检索根页表，查找关于用户页表的页的页表项。如果该页不在主存中，
则发生一次缺页中断。如果该页在主存中，则用虚地址中接下的几位检索用户页表，查找 该虚地址引用的页的页表项。 索引检索技术的引用三、分段虚拟存储管理
在这种方式中，允许程序员把存储器看成由多个地址空间段组成，段的大小是不相等的，并且是动态的。存储器访问是以段号和偏移量的地址形式组成的。
分段比非段式地址空间具有的优点：
1）、简化不断增长的数据结构的处理
2）允许程序独立地改变或重新编译，而不要求整个程序集合重新链接和重新加载。
3）、有助于进程间的共享。
4）、有助于保护。
四、分段和分页组合
1）、各自的优点：
分页：对程序员是透明的，它消除了外部碎片，
因而可以更有效地使用主存。此外，由于移进和移出主存的块是固定、大小相等的，就有可能开发出更高级的存储管理算法。
分段是对程序员是可见的，包括处理不断增长的数据结构的能力以及支持共享和保护能力。
为了把它们二者的优点结合起来，一些系统配备了处理器硬件和操作系统软件，以提供这些能力。
2）这种组合方式的实现：
用户的地址空间根据程序员的判断划分成许多段。每个段依次划分成许多固定大小的页，页的长度等于主存的帧大小。
图 4-10c中给出了虚拟地址、段表和页表的结构。
从程序员角度看：逻辑地址仍然由段号和段偏移量组成；
从系统的角度看，段偏移量看作是指定段中的一个页号和页内偏移量。
五、保护和共享
保护和共享的需要解决的问题：
分段有助于实现保护与共享策略。由于每个段表项包括一个长度和一个基地址，因而程序不会不经意地访问超出该段的主存单元。为实现共享，一个段可能在多个进程的段表中被引用。
当然在分页系统中也可以得到同样的机制。但是，对于程序页结构和数据对程序员不可见的情况，共享和保护要求的说明比较难。
2）、解决方案：
一种常用的方案是 使用环状保护结构 。
在这个方案中，编号小的内环比编号大的外环具有更大的特权。环状系统的基本原理如下：
程序可以只访问驻留在同一个环或更低特权环中的数据。
程序可以调用驻留在相同或更高特权环中的服务。
2、存储管理策略
一、取策略和放置策略
二、替换策略
三、驻留集管理一、取策略和放置策略
取策略：确定一个页何时取入主存。
请求式页面调度：只有当访问到某页中的一个单元时才将该页取入主存。
预约式页面调度：取进的页并不是缺页故障请求的页。
这是大部分操作启动缓慢的原因
具体实施方法：
当进程第一次启动时可以采用预约式页面调度策略，在这种情况下，程序员必须以某种方式指定想要的页；当发生缺页时也可以采用预约式页面调度策略，
由于这个过程对程序员是不可见的，因而它显得更可取一些。但不要把预约式页面调和交换混淆。当一个进程被换出主存并且被置于挂起状丰收时，它的所有驻留页都被移出。当该进程被唤醒时，
所有在主存中的页都返回主存。
小结：
放置策略决定一个进程块驻留在实存中的什么地方。在分段系统中，常用的放置策略有：最佳适配、首次适配等。
这些策略近乎于作业调度所采用的方式二、替换策略
替换策略用于处理在必须取进一个新页时，应该选择替换主存中的哪一页。
这这涉及相关的问题：
1）、给每个进程分配多少页帧。
2）、考虑替换的页的集合是否局限在那些产生缺页或所有页帧都在主存中的进程。
3）、在考虑的页集合中，选择替换出哪一个页。
替换策略决定当前在主存中的哪个页将被替换。所有策略的目标都是移出最近最不可能访问的页。
由于局部性原理，最近的访问历史和最近将要访问的模式间有很大的相关性。因此大多数策略都基于过去的行为预测预测将来的行为。
一些用于选择替换页的基本策略
1）、最佳策略 (OPT)
替换对象,选择替换下次访问距当前时间最长的那些页。
性能总评,该策略导致最少数目的缺页，但是由于它要求操作系统必须知道将来的事件，显然这是不可能实现。因此仅能将其作为一种标准，用于测量其它策略的性能。
2 3 2 1 5 2 4 5 3 2 5 3
内存帧 1 2 2 2 2 2 2 4 4 4 2 2 2
内存帧 2 3 3 3 3 3 3 3 3 3 3 3
内存帧 3 1 5 5 5 5 5 5 5 5
缺页记录 F F F F F F
缺页率 = 6
实例演示：
2）、最近最少使用策略替换（ LRU ）
替换对象,此种策略主要替换主存中上次使用距当前最远的缺页。
性能分析,根据局部性原理，这也是最近最不可能访问到的页。实际上，最近最少使用策略的性能接近于最佳策略。
具体实施,该方法的实现比较困难，一种实现方法是给每一页添加一个最后一次访问的时间标签，并且必须在每次访问存储器时，不论访问的是指令还是数据，都执行这种操作。即使有支持这种方案的硬件，开销仍然是非常大的。
2 3 2 1 5 2 4 5 3 2 5 3
内存帧 1 2|0 2|1 2|0 2|1 2|2 2|0 2|1 2|2 3|0 3|1 3|2 3|0
内存帧 2 3|0 3|1 3|2 5|0 5|1 5|2 5|0 5|1 5|2 5|0 5|1
内存帧 3 1|0 1|1 1|2 4|0 4|1 4|2 2|0 2|1 2|2
缺页记录 F F F F F F F
缺页率 = 7
实例演示：
3）、先进先出策略 (FIFO)
替换对象,这种选择方法是替换驻留在主存中时间最长的页。
具体实施,在这种策略中，把分配给进程的页帧看作是一个循环缓冲区，按循环方式移动页。它所需要的只是一个指针，
这个指针在该进程的页帧中循环。
性能分析,这是一种实现起来最简单的页替换策略。
2 3 2 1 5 2 4 5 3 2 5 3
内存帧 1 2|0 2|1 2|2 2|3 5|0 5|1 5|2 5|3 3|0 3|1 3|2 3|3
内存帧 2 3|0 3|1 3|2 3|3 2|0 2|1 2|2 2|3 2|4 5|0 5|1
内存帧 3 1|0 1|1 1|2 4|0 4|1 4|2 4|3 4|4 4|5
缺页记录 F F F F F F F F
缺页率 = 8
实例演示：
4）、时钟策略 (clock)
A,替换对象,主要替换那些指针指向使用位为 0的帧中的页面。
B,具体实施：
（ 1）、给每一帧关联一个使用位。
（ 2）、当某一页首次装入主存中的某一帧时，
该帧的使用位置 1；当该页随后被访问到时，
它的使用位被置为 1。
（ 3）、对于页替换算法，用替换的候选帧集合被看作是一个循环缓冲区，并且有一个指针与之相关联。 当一个页被替换时，该指针被设置成指向缓冲区中的下一帧。
（ 4）、当替换一页时，操作系统扫描缓冲区，
以查找使用位被置 0的一帧，每当遇到一个使用位为 1的帧时，操作系统将该位重新置为 0，
则指针滑向下一个帧；
（ 5）、如果在空虚过程开始时，缓冲区所有帧的使用位均为 0，则选择替换遇到的第一个帧；
（ 6）、如果所有帧的使用位均为 1，则指针在缓冲区中完整地循环一周，把所有使用位都置为 0，并且停留在最初的位置上，替换该帧的页。
性能分析,使用此种策略对系统的开销一样较大，
当使用位是 0时，时钟算法就退化成先进先出。
2 3 2 1 5 2 4 5 3 2 5 3
2· 2· 2· 2 > 2 2· 2· > 2 3· 3· > 3 3·
> 3· 3 > 3 5 > 5 4· 4 > 4 2· 2 > 2
> > 1· 1 1 > 1 5 5 > 5 5 5
F F F F F F F F
缺页率 =
实例演示：
2 3 2 1 5 2 4 5 3 2 5 3
内存帧 1
2· 2· 2· 2 > 2 2· 2 > 2 3· 3 > 3 3·
内存帧 2
> 3· 3 > 3 5· 5 > 5 5· 5 > 5 5· 5
内存帧 3
> > 1· 1 > 1 4· 4 > 4 2· 2 > 2
缺页记录 F F F F F F
F
三、驻留集管理
1)、给进程分配主存需要考虑的因素：
分配一个进程的存储量越小，在任何时候驻留在主存中的 进程数 就越多。
如果一个进程在主存中的页数比较少，尽管有局部性原理 缺页率 仍然相对较高。
超过一定的大小后，由于局部性原理，给特定的进程分配更多的主存空间对该进程的缺页率没有明显的影响。
、
2）常用的二种策略
固定分配策略：
为一个进程在主存中分配固定数目的帧用于执行时使用。这个数目是在最初加载时决定，可以根据进程的类型或者基于程序员或系统管理员的指导来确定。对于固定分配策略，一旦进程的执行过程中发生缺页，该进程的一页必须被它所需要的页替换。
可变分配策略：
允许分配给一个进程的页帧在该进程的生命周期时不断地发生变化。理论上，
如果一个进程的缺页率一直比较高，则在该进程中局部性原理表现得比较弱，
应该为它额外分配一些页帧以减小缺页率；而如果一个进程的缺页率特别低，
则从局部性的角度看该进程的表现非常好，可以在不会明显增加缺页率的前提下减少分配给它的页帧。
3）替换策略的作用范围
可以分为全局和局部两类，
局部替换策略仅仅在产生这次缺页的进程的驻留页中选择。
全局替换策略把主存中所有未被锁定的页都作为替换的候选页，而不管它们分别属于哪一个进程。
4）、驻留集管理局部替换 全局替换固定分配 一个进程的帧数是固定的 不可能可变分配?从分配给该进程的帧中选择被替换的页分配给一个进程的帧数可以不时地变化，
用于保存该进程的工作集
从分配给该进程的帧中选择被替换的页从主存中的所有可用帧中选择被替换的页；这导致进程驻留集的大小不断变化
3,windows 2000虚存管理策略
前言,Windows2000中每个用户进程看到的是一个独立的 32位地址空间，每个进程允许 4G的存储空间。一部分存储空间默认为操作系统保留，因而每个用户空间增加到 3GB，只留下 1GB用作所有进程共享的系统空间。
32位的地址空间：
其大小为,232即
4GB
3,windows 2000虚存管理策略
前言,Windows2000中每个用户进程看到的是一个独立的 32位地址空间，每个进程允许 4G的存储空间。一部分存储空间默认为操作系统保留，因而每个用户空间增加到 3GB，只留下 1GB用作所有进程共享的系统空间。
32位的地址空间：
其大小为,232即
4GB
一,windows2000虚地址映射
1)、虚拟存储空间的分配：
理论上,Windows 2000使用独立的 32位地址空间，每个进程允许 4GB的存储空间。
实际上：一部分存储空间为操作系统保留，因而每个用户实际上有 2GB的可用虚拟地址空间。
Windows 2000有一个选项，可以允许用户空间增加到 3GB，只留下 1GB用作系统空间。
3,windows 2000驻留集管理策略
前言,Windows2000中每个用户进程看到的是一个独立的 32位地址空间，每个进程允许 4G的存储空间。一部分存储空间默认为操作系统保留，因而每个用户空间增加到 3GB，只留下 1GB用作所有进程共享的系统空间。
32位的地址空间：
其大小为,232即
4GB
一,windows2000虚地址映射
1)、虚拟存储空间的分配：
理论上,Windows 2000使用独立的 32位地址空间，每个进程允许 4GB的存储空间。
实际上：一部分存储空间为操作系统保留，因而每个用户实际上有 2GB的可用虚拟地址空间。
Windows 2000有一个选项，可以允许用户空间增加到 3GB，只留下 1GB用作系统空间。
2）、虚拟地址的空间的组成：
0~0X0FFFF：留出来用于帮助程序员捕获空指针赋值。
0X010000~0X7FFEFFF:可以使用的用户地址空间。这个空间划分成页，可以装入主存。
0X7FFF0000~0XFFFFFFF：用户不能访问的保护页。
0X80000000~0XFFFFFFFF：系统地址空间。
二,windows2000页面调度
1)、页面的状态划分：
每一页可以处于以下三个状态：
可用：当前没有被进程使用
保留：虚存管理程序为一个进程保留一组连续的页，但是在被使用之前都没有算在该进程的存储器分配额中。
提交：虚存管理程序在它的页面调度文件中为这类页留出空间。
注：当一个进程创建后，原则上它可以使用整个用户空间。这个空间划分 成固定大小的页，
每个页都可以被取进主存。
2）、页面调度的总准则：
区分保留的存储空间和调拔（可分配）的存储空间。因为减少了为某一特定的进程留出的磁盘空间总量，保持该磁盘空间对其它的进程使用是自由的；允许一个进程或线程声明在需要时可以迅速分配的存储量。
Windows2000使用的驻留集管理方案是可变分配、局部范围的。当一个进程第一次激活时，
给它分配一定数目页、帧作为其工作集。当一个进程访问不在存储器中的某页时。该进程的一个驻留页被换出，这个新页被取进。
3)、页面调度的方法
活动进程的工作集可以使用下面通用性的约束进行调整：
当主存空间很充裕时，虚存管理程序允许活动进程的驻留增长。
当主存空间很称少时，虚存管理程序通过把最近很少使用的页移出活动进程的驻留集，从页减少那些驻留集的大小，
为系统回收主存空间。
主要内容,
4.1、简介
4.2、内存管理
4.3、虚拟存储技术
4.4、辅存管理
4.5、高速缓存管理
4.1、简介
现代计算机的体系结构是以存储器为中心。
存储器的体系结构：同寄存器、高速缓存、主存和辅存等多层体系结构。
本章主要介绍内存分配与管理的原理和策略、辅存信息的组织和管理方法、高速缓存结构和操作方式等内容，以进一步认识和掌握操作系统的存储器管理原理和方法，提高计算机系统的利用率。
4.2、内存管理
1、内存管理简介
2、存储管理功能
3、地址重定位
4、存储管理方法
1、内存管理简介在单道程序系统中：主存划分成两部分，
一部分供操作系统使用，一部分供当前正在执行的程序使用。
多道程序系统中：存储器的“用户”部分必须进一步地细分，以适应多个进程的要求。
Windows2000内存管理器位于 Ntoskrnl.exe文件中。
在硬件抽象层（ HAL）中没有内存管理器的任何部分。
内存管理器由以下几个部分组成：
1）、一组执行程序系统服务程序，用于虚拟内存的分想、释放和管理，它们中的大多数通过 Win32API或核心态的设备驱动程序接口形式出现。
2）、一个转换无效和访问错误陷阱处理程序，
用于解决硬件检测到的内存管理异常事件，并代表一个进程的虚拟页驻留。
3）、运行在 6个不同内核模式系统线程的环境中的几个关键组件。
2、存储管理功能
一、存储管理的体系统结构
主存的功能：存放内核和用户程序的指令和数据，每一项信息都存放在主存的特定位置上。
信息在主存是按“位”存放的。
为了能对信息进行访问，要对这些位置进行编号，这些编号称为“地址”。
计算机的三级存储结构：
辅存
内存
高速缓存二、主存储器管理功能
1）、主存分配：可以使多个程序同时驻留在主存中，以提高处理器的利用率。
2）、地址转换和重定位：即能运行与机器无关的代码
3）、存储保护和主存共享：研究如何保护各存储区中信息不被破坏和偷窃。
4）、存储扩充：运行的程序应不受主存大小的限制，理想情况下应能运行任意大小的程序。
3、地址重定位
重定位：处于主存中的程序，一旦被换出，下次换出时，不一定装在同一区域中，因此为了保证作业的正确执行，必须根据分配给作业的主存空间对作业中指令和数据的存放地址进行重定位，即要把逻辑地址转换成绝对地址。
一、逻辑组织
1）、计算机中存储数据的方式：计算机系统中的主存总是被组织成线性的或一维的地址空间，此空间由一系列字节或字组成，辅存在物理层上也是按类似方式组织的。
2）、程序存在的方式：模块、及某种机制
逻辑地址：用户程序中使用的地址被为逻辑地址，由逻辑地址对应的存储空间称逻辑地址空间。
二、物理组织
1）、计算机存储器至少被组织成两级称作主存和辅存
2）、物理地址：程序和数据存放在存储器上位置相应的地址
3）、由物理地址对应的存储空间
在主存和辅助之间移动信息是系统的责任，这个任务是存储器管理的本质所在。
三、保护
每个进程都应该受到保护,以免其他进程有意或无意的干涉，因此，必须在运行时检查一个进程产生的所有存储访问，以确保它们只访问了分配给进程的存储空间。
采用的方法：通常，用户进程不能访问操作系统的任何部分，不论是程序还是数据。再者，
一个进程中的程序通常不能分支到另一个进程中的指令。如果没有特别的安排，一个进程中的程序不能访问另一个进程的数据区。处理器必须能够在执行时取消这样的指令。
四、共享
任何保护机制必须具有一定的灵活性，
以允许多个进程访问主存的同一部分。
例：如果许多进程正执行同一个程序，
则允许每个进程访问进程的同一个副本要优于让它们有自已单独的副本。在同一个任务上合作的进程可能需要共享访问同一个数据结构。存储器管理系统必须允许对存储器共享区域的受控访问，
并且不能损害本质上的保护。
五、静态重定位
方法：在装入一个作业时，把作业中的指令地址和数据地址全部转换成绝对地址。转换工作是在作业执行前集中一次完成，所以在作业执行过程中就无需再进行地址转换。
注：采用这种方式时，由于装入主存储器的作业信息已经都是用绝对地址指示，
故作业执行过程中是不能移动位置的。
六、动态重定位
方法：是指程序的重定位时机不是在程序执行前进行，而是在程序执行过程中才进行地址转换。更确切的说是在每次访问主存单元前才进行地址转换。
注：采用动态重定位时，由于装入的作业仍保持原来的逻辑地址，所以，必要时可改变它在主存中的再存放区域。
当作业被移到一个新区域时，只要改变定位寄存器的值，使定位寄存器的内容变为新区域的起始地址。这样，在作业执行时，硬件的地址转换机构按照新区域的起始地址与逻辑地址相加，转换成新区域的绝对地址，使作业仍可正确执行。
4、存储管理方法
存储器管理最基本的操作是由处理器把程序装入主存执行。
单用户系统中：内存被分为两个区域，
即系统区和用户区。
多道程序并发执行的系统中：虚拟存储器方案。（分段和分页）
一、固定分区
1）、分区大小：
大小相等的分区：碎片较多
大小不等的分区：碎片相对较小
缺点：都容易产生内部碎片
内部碎片：由于装入的数据块小于分区从而使得分区内部有空间浪费的现象。
2）、放置算法
即选择那个空闲分区给新作业。
对于大小相等的分区：不重要
对于大小不等的分区：把每个进程指定到适应它的最小分区。在这种情况下，
每个分区都需要一个调度队列，用于保存为这个分区换出等待的进程。这种方法优点是可以使一个分区内部浪费的空间（内部碎片）最少。
改进算法：给所有的进程提供一个队列，
当需要把一个进程装入主存时，选择可以保存该进程的最小的分区。如果所有的分区都已占据，则必须进行交换决策。
一般首先考虑换出占据了能保存这个新到进程的最小分区的进程，也可以考虑一些诸如优先权的其他因素，或者选择换出阻塞的进程。
二、动态分区
对于动态分区，分区长度和数目是可变的，当一个进程被装入主存时，正好给它分配所需要的存储空间。
外部碎片：在动态分区的作用下，导致在存储器中出现了许多空闲区。随着时间的推移，存储器中产生了越来越多的碎片，它的利用率也随着下降。
拼接：克服外部碎片的一种技术。即操作系统不时地移动进程，使得它们变得连续，并且使所有自空间连成一片。但压缩是一个非常费时的过程，并且浪费了处理器的时间同时，也意味了程序需要动态重定位。
内碎片和外碎片：
内碎片是占用分区内未被利用的空间，
外碎片是点用分区之间难以利用的空闲分区。
分区式存储管理常采用的一项技术就是内存紧缩，即将各个占用分区向内存的一端移动，然后将各个空闲分区合并成为一个空闲分区。
常用的几种分区分配算法：
1）、首先适配法：
2）、下次适配法：
3）、最佳适配法：
4）、最坏适配法：
三、分页
分页的产生：在分区中提到了主存可以划分成大小相等的许多区，每个区称为一块。与此对应，每个作业也被分成同样大小的作业块。进程中被称作页的块就可以指定存放到存储器的可用块中。
页：是一个相对于逻辑空间的概念是对程序 (作业 )的一种划分。
块：是一个相对物理空间的概念是对主存划分的一种，通常也叫帧。
在使用上页的大小必须和块的大小相对应页式存储管理
页式存储管理就是把主存储器分成大小相等的许多区，每个区称为一块。与此对应，编制程序的逻辑地址也要分成页，
页的大小与块的大小相等。
页式存储管理的逻辑地址由两部分组成：
页号和页内地址。
地址结构确定了主存储器的分块大小，
也就决定了页面的大小。
页和块的用法：
空闲块的管理：操作系统通过列表来维护。存储在磁盘上的作业由几个页组成。
当装入这个作业时，操作系统查找几个空闲块，
并将作业的页装入这几个块中。
操作系统为每个作业维护一个页表。页表给出了该作业的每一页对应的帧位置。
在程序中，每个逻辑地址包括一个页和在该页中的偏移量。
在简单分区的情况下，逻辑地址是一个指令相对于程序的开始处的位置，处理器把它转换成一个物理地址。在分页中，逻辑／物理地址的转换仍然由处理器硬件完成，那么处理器必须知道如何访问当前作业的页表。给出一个逻辑地址（页号＋偏移量），处理器使用页表产生一个物理地址（块号＋偏移量）。
简单分页和固定分区的比较：
相同点：把内存分成多个等份
不同点：它们不同之处在于，对于分页，
分区相当小,一个作业可以占据多个分区，并且这些分区不需要是连续的。
页大小的规定
为了使分页更加方便，可以规定页的大小以及块的大小必须是 2的幂。
原因：
首先是因为逻辑地址方案对程序员、汇编程序和编译器是透明的，程序的每个逻辑地址（页＋偏移量）与它的相对地址是一致的。
其次是因为硬件实现运行时动态地址转换的功能相对比较容易。
例：考虑一个 n+m位的地址，左边的 n位是页号，右边的 m位是偏移量。按定义可以用页号和偏移量表。那么地址转换的步骤如下：
（１）、提取页号，即逻辑地址左边的 n位。
（２）、以这个页号为索引，查找该作业页表中的相应块号Ｋ。
（３）、该块的起始地址为 kＸ２ m，被访问字节的物理地址是这个数加上偏移量。物理地址不需要计算，它可以通过简单地把偏移量添加在块号后面来构造。
简单分页的总结：
主存被分成许多大小相等且很小的帧，每个作业被划分成同样的大小的页；较小的作业需要较少的块，较大的作业需要较多的块；当一个作业被装入时，它的所有页都被装入到可用的块中，
并且建立一个页表。
空闲页表：管理空闲块作业页表：对作业所占块进行登记四、分段
分段：用户按照自已的意愿把一个作业分成若干个段，如程序段和数据段。
段的地址：段内是连续的，从“０”开始
段与段之间的地址不是连续的。
逻辑地址的组成：段号和段内地址；
当地址结构确定后，那么允许作业的最多段数及每段的最大长度也就确定了。
（但并不要求所有程序的所有段都具有相同的长度）
与动态分区的不同,
在分段方案中，一个程序可以占据多个分区，并且这些分区不要求是连续的。
分段消除了内部碎片，但是和动态分区一样，它会的生外部碎片。但是一个作业被分成许多小块，因此外部碎片是很小。
对于使用覆盖方案或使用虚存的情况下，动态分区与分段这两种方法相同和分页的比较：
分页对程序员来讲是不可见的，
分段是通常是可见的，并且作为组织程序和数据的一种方便手段提供程序员。
典型地，程序员或编译器把程序和数据指定到不同的段。基于模块化程序设计的目的，程序或数据可能进一步分成多个段。（这种方法最不方便之处：是程序员必须知道段长度的最大限度）。
大小不等的分段方式的处理办法
结果：逻辑地址和物理地址不再有简单的对应关系。
段表：每个进程都有一个段表，主存的自由块组织到一个列表中。每个段表必须给出相应的段在主存中的起始地址，还必须提供段的长度，以确保不会使用无效地址。当一个作业进入运行状态时，它的段表地址被装入到一个特殊的寄存器，该寄存器由存储器管理硬件使用。
分段管理方式的地址转换的步骤如下：
（１）、提取段号，即逻辑地址左边的段号 n位。
（２）、以这个段号为索引，查找该作业段表中该段的起始物理地址。
（３）、将逻辑地址中的偏移量与段长进行比较，
如果偏移量大于该长度，则该地址无效。
（４）、物理地址为该段的起始地址加上偏移量的和。
简单分段小结：
一个作业被划分成许多段，段的大小不需要相等；当一个作业被调入时，它的所有段都被装入到存储器的可用区域中，
并建立一个段表。
4.3、虚拟存储技术
０、虚拟存储引入的技术支持
1、虚拟存储概念
2、存储管理策略
3,windows 2000虚存管理策略
4,windows 2000内存管理
０、虚拟存储引入的技术支持
１）、分页和分段管理的二个特点：
进程中所有存储访问都是逻辑地址，并可在运行过程中动态转换成物理地址。
进程可以可以划分成许多块，在执行过程中，通过页表和段表进行地址转换，不需要连续的主存空间。
２）、而且进程的执行往往有局部性。一个进程可以被部分换入或换出主存，进程仍能正常执行。
３）、虚拟存储技术：用户编制程序时可以不必考虑主存储器的实际容量，允许用户的逻辑地址空间大于主存的绝对地址空间。对用户来说，好像计算机系统具有一个容量很大的主存。
1、虚拟存储概念
一、局部性和虚拟存储器
二、分页虚拟存储管理
三、分段虚拟存储管理
四、分段和分页组合
五、保护和共享一、局部性和虚拟存储器
１）、问题的提出：
对于一个由很长程序和许多数据组成的大进程，
在任何一段很短的时间内，执行可能会局限在很小的一段程序中，并且可能仅仅会访问一个或两二个数据数组。这样，如果在程序被挂起或被换出前仅仅使用了一部分进程块，那么为该进程装入太多的块显然会带来大量的浪费。
２）、情况分析
在任何时刻，任何一个进程只有一部分块位于存储器中，当程序转移或访问到不在主存中的某一块时，就会引发一个信息，告诉操作系统想要取进的块；此外，未用到的块不需要换入／换出存储器，也可节省一些时间。同时，也可以在存储器中保留更多的进程，提高并发度和资源的利用率。
3）、局部性原理
局部性原理定义：描述了一个进程中程序和数据引用的簇聚性倾向。因此，假设在很短的时间内仅需要进程的一部分块是否合理的，同时，
还可以对在不远的将来可能会需要的块进行明智的猜测，从而避免系统抖动。
为了使虚存实用有效，需要考虑两方面的因素：
（ 1）、必须有对所采用的分页或分段方案进行硬件支持。
（ 2）、操作系统必须有管理页或段在主存和辅存之间移动的软件。
二、分页虚拟存储管理
1）、简单分页的解决方案
简单分页的体系结构：
页表：有四个方面的含义（如图 4-10aP134
P表示对应的页当前是否在主存中。（如果该页在主存中，则这个页表项还包括该页的帧号。）
M是修改位，表示相应页的内容从上一次装入主存中到现在是否已经改变。如果没有改变，则不需要把它当前占据的帧的页写出。
其他控制位：如页的保护和共享等。
帧号：如该页在主存中，则记录了对应的帧号。
简单分页存在的缺陷：
在大多数系统中，每个进程都有一个页表。但是如果某个进程占据大量的虚存空间，如某个进程有接近 231=2GB的虚存空间，如果使用的页的大小是 29=512B，
这意味着此进程需要有 222个页表项，显然用于放置页表的存储空间是无法接受的。
对于大进程使用的解决方法：
大多数虚拟存储器方案都必须在虚存中保存页表，而不是在实存中。也就是说，
页表也和别的页一样都服从页面调度。
当一个进程正在运行时，它的页表至少有一部分必须在主存中，这一部分包括正在运行的页的页表项。
这里注意二点：页表放在虚存中；
对页表的也可以使用局部调度页号 偏移量
P M 其他控制位 长度 段基虚地址页表项 分页段号 偏移量 分段虚地址段表项段号 页号 偏移量虚地址
P M 其他控制位 帧号
P M 其他控制位 帧号
P M 其他控制位 长度 段基页表项页表项分段和分页相结合
pentium处理器的处理方案
在 pentium处理器中使用的两级方案组织大型页表。在这类方案中有一个页目录，每一项指向一个页表，通常一个页表的最大长度被限制成等于一页。 P134图 4-11给出了这种方案地址转换的步骤。
虚地址的前几位用于检索根页表，查找关于用户页表的页的页表项。如果该页不在主存中，
则发生一次缺页中断。如果该页在主存中，则用虚地址中接下的几位检索用户页表，查找 该虚地址引用的页的页表项。 索引检索技术的引用三、分段虚拟存储管理
在这种方式中，允许程序员把存储器看成由多个地址空间段组成，段的大小是不相等的，并且是动态的。存储器访问是以段号和偏移量的地址形式组成的。
分段比非段式地址空间具有的优点：
1）、简化不断增长的数据结构的处理
2）允许程序独立地改变或重新编译，而不要求整个程序集合重新链接和重新加载。
3）、有助于进程间的共享。
4）、有助于保护。
四、分段和分页组合
1）、各自的优点：
分页：对程序员是透明的，它消除了外部碎片，
因而可以更有效地使用主存。此外，由于移进和移出主存的块是固定、大小相等的，就有可能开发出更高级的存储管理算法。
分段是对程序员是可见的，包括处理不断增长的数据结构的能力以及支持共享和保护能力。
为了把它们二者的优点结合起来，一些系统配备了处理器硬件和操作系统软件，以提供这些能力。
2）这种组合方式的实现：
用户的地址空间根据程序员的判断划分成许多段。每个段依次划分成许多固定大小的页，页的长度等于主存的帧大小。
图 4-10c中给出了虚拟地址、段表和页表的结构。
从程序员角度看：逻辑地址仍然由段号和段偏移量组成；
从系统的角度看，段偏移量看作是指定段中的一个页号和页内偏移量。
五、保护和共享
保护和共享的需要解决的问题：
分段有助于实现保护与共享策略。由于每个段表项包括一个长度和一个基地址，因而程序不会不经意地访问超出该段的主存单元。为实现共享，一个段可能在多个进程的段表中被引用。
当然在分页系统中也可以得到同样的机制。但是，对于程序页结构和数据对程序员不可见的情况，共享和保护要求的说明比较难。
2）、解决方案：
一种常用的方案是 使用环状保护结构 。
在这个方案中，编号小的内环比编号大的外环具有更大的特权。环状系统的基本原理如下：
程序可以只访问驻留在同一个环或更低特权环中的数据。
程序可以调用驻留在相同或更高特权环中的服务。
2、存储管理策略
一、取策略和放置策略
二、替换策略
三、驻留集管理一、取策略和放置策略
取策略：确定一个页何时取入主存。
请求式页面调度：只有当访问到某页中的一个单元时才将该页取入主存。
预约式页面调度：取进的页并不是缺页故障请求的页。
这是大部分操作启动缓慢的原因
具体实施方法：
当进程第一次启动时可以采用预约式页面调度策略，在这种情况下，程序员必须以某种方式指定想要的页；当发生缺页时也可以采用预约式页面调度策略，
由于这个过程对程序员是不可见的，因而它显得更可取一些。但不要把预约式页面调和交换混淆。当一个进程被换出主存并且被置于挂起状丰收时，它的所有驻留页都被移出。当该进程被唤醒时，
所有在主存中的页都返回主存。
小结：
放置策略决定一个进程块驻留在实存中的什么地方。在分段系统中，常用的放置策略有：最佳适配、首次适配等。
这些策略近乎于作业调度所采用的方式二、替换策略
替换策略用于处理在必须取进一个新页时，应该选择替换主存中的哪一页。
这这涉及相关的问题：
1）、给每个进程分配多少页帧。
2）、考虑替换的页的集合是否局限在那些产生缺页或所有页帧都在主存中的进程。
3）、在考虑的页集合中，选择替换出哪一个页。
替换策略决定当前在主存中的哪个页将被替换。所有策略的目标都是移出最近最不可能访问的页。
由于局部性原理，最近的访问历史和最近将要访问的模式间有很大的相关性。因此大多数策略都基于过去的行为预测预测将来的行为。
一些用于选择替换页的基本策略
1）、最佳策略 (OPT)
替换对象,选择替换下次访问距当前时间最长的那些页。
性能总评,该策略导致最少数目的缺页，但是由于它要求操作系统必须知道将来的事件，显然这是不可能实现。因此仅能将其作为一种标准，用于测量其它策略的性能。
2 3 2 1 5 2 4 5 3 2 5 3
内存帧 1 2 2 2 2 2 2 4 4 4 2 2 2
内存帧 2 3 3 3 3 3 3 3 3 3 3 3
内存帧 3 1 5 5 5 5 5 5 5 5
缺页记录 F F F F F F
缺页率 = 6
实例演示：
2）、最近最少使用策略替换（ LRU ）
替换对象,此种策略主要替换主存中上次使用距当前最远的缺页。
性能分析,根据局部性原理，这也是最近最不可能访问到的页。实际上，最近最少使用策略的性能接近于最佳策略。
具体实施,该方法的实现比较困难，一种实现方法是给每一页添加一个最后一次访问的时间标签，并且必须在每次访问存储器时，不论访问的是指令还是数据，都执行这种操作。即使有支持这种方案的硬件，开销仍然是非常大的。
2 3 2 1 5 2 4 5 3 2 5 3
内存帧 1 2|0 2|1 2|0 2|1 2|2 2|0 2|1 2|2 3|0 3|1 3|2 3|0
内存帧 2 3|0 3|1 3|2 5|0 5|1 5|2 5|0 5|1 5|2 5|0 5|1
内存帧 3 1|0 1|1 1|2 4|0 4|1 4|2 2|0 2|1 2|2
缺页记录 F F F F F F F
缺页率 = 7
实例演示：
3）、先进先出策略 (FIFO)
替换对象,这种选择方法是替换驻留在主存中时间最长的页。
具体实施,在这种策略中，把分配给进程的页帧看作是一个循环缓冲区，按循环方式移动页。它所需要的只是一个指针，
这个指针在该进程的页帧中循环。
性能分析,这是一种实现起来最简单的页替换策略。
2 3 2 1 5 2 4 5 3 2 5 3
内存帧 1 2|0 2|1 2|2 2|3 5|0 5|1 5|2 5|3 3|0 3|1 3|2 3|3
内存帧 2 3|0 3|1 3|2 3|3 2|0 2|1 2|2 2|3 2|4 5|0 5|1
内存帧 3 1|0 1|1 1|2 4|0 4|1 4|2 4|3 4|4 4|5
缺页记录 F F F F F F F F
缺页率 = 8
实例演示：
4）、时钟策略 (clock)
A,替换对象,主要替换那些指针指向使用位为 0的帧中的页面。
B,具体实施：
（ 1）、给每一帧关联一个使用位。
（ 2）、当某一页首次装入主存中的某一帧时，
该帧的使用位置 1；当该页随后被访问到时，
它的使用位被置为 1。
（ 3）、对于页替换算法，用替换的候选帧集合被看作是一个循环缓冲区，并且有一个指针与之相关联。 当一个页被替换时，该指针被设置成指向缓冲区中的下一帧。
（ 4）、当替换一页时，操作系统扫描缓冲区，
以查找使用位被置 0的一帧，每当遇到一个使用位为 1的帧时，操作系统将该位重新置为 0，
则指针滑向下一个帧；
（ 5）、如果在空虚过程开始时，缓冲区所有帧的使用位均为 0，则选择替换遇到的第一个帧；
（ 6）、如果所有帧的使用位均为 1，则指针在缓冲区中完整地循环一周，把所有使用位都置为 0，并且停留在最初的位置上，替换该帧的页。
性能分析,使用此种策略对系统的开销一样较大，
当使用位是 0时，时钟算法就退化成先进先出。
2 3 2 1 5 2 4 5 3 2 5 3
2· 2· 2· 2 > 2 2· 2· > 2 3· 3· > 3 3·
> 3· 3 > 3 5 > 5 4· 4 > 4 2· 2 > 2
> > 1· 1 1 > 1 5 5 > 5 5 5
F F F F F F F F
缺页率 =
实例演示：
2 3 2 1 5 2 4 5 3 2 5 3
内存帧 1
2· 2· 2· 2 > 2 2· 2 > 2 3· 3 > 3 3·
内存帧 2
> 3· 3 > 3 5· 5 > 5 5· 5 > 5 5· 5
内存帧 3
> > 1· 1 > 1 4· 4 > 4 2· 2 > 2
缺页记录 F F F F F F
F
三、驻留集管理
1)、给进程分配主存需要考虑的因素：
分配一个进程的存储量越小，在任何时候驻留在主存中的 进程数 就越多。
如果一个进程在主存中的页数比较少，尽管有局部性原理 缺页率 仍然相对较高。
超过一定的大小后，由于局部性原理，给特定的进程分配更多的主存空间对该进程的缺页率没有明显的影响。
、
2）常用的二种策略
固定分配策略：
为一个进程在主存中分配固定数目的帧用于执行时使用。这个数目是在最初加载时决定，可以根据进程的类型或者基于程序员或系统管理员的指导来确定。对于固定分配策略，一旦进程的执行过程中发生缺页，该进程的一页必须被它所需要的页替换。
可变分配策略：
允许分配给一个进程的页帧在该进程的生命周期时不断地发生变化。理论上，
如果一个进程的缺页率一直比较高，则在该进程中局部性原理表现得比较弱，
应该为它额外分配一些页帧以减小缺页率；而如果一个进程的缺页率特别低，
则从局部性的角度看该进程的表现非常好，可以在不会明显增加缺页率的前提下减少分配给它的页帧。
3）替换策略的作用范围
可以分为全局和局部两类，
局部替换策略仅仅在产生这次缺页的进程的驻留页中选择。
全局替换策略把主存中所有未被锁定的页都作为替换的候选页，而不管它们分别属于哪一个进程。
4）、驻留集管理局部替换 全局替换固定分配 一个进程的帧数是固定的 不可能可变分配?从分配给该进程的帧中选择被替换的页分配给一个进程的帧数可以不时地变化，
用于保存该进程的工作集
从分配给该进程的帧中选择被替换的页从主存中的所有可用帧中选择被替换的页；这导致进程驻留集的大小不断变化
3,windows 2000虚存管理策略
前言,Windows2000中每个用户进程看到的是一个独立的 32位地址空间，每个进程允许 4G的存储空间。一部分存储空间默认为操作系统保留，因而每个用户空间增加到 3GB，只留下 1GB用作所有进程共享的系统空间。
32位的地址空间：
其大小为,232即
4GB
3,windows 2000虚存管理策略
前言,Windows2000中每个用户进程看到的是一个独立的 32位地址空间，每个进程允许 4G的存储空间。一部分存储空间默认为操作系统保留，因而每个用户空间增加到 3GB，只留下 1GB用作所有进程共享的系统空间。
32位的地址空间：
其大小为,232即
4GB
一,windows2000虚地址映射
1)、虚拟存储空间的分配：
理论上,Windows 2000使用独立的 32位地址空间，每个进程允许 4GB的存储空间。
实际上：一部分存储空间为操作系统保留，因而每个用户实际上有 2GB的可用虚拟地址空间。
Windows 2000有一个选项，可以允许用户空间增加到 3GB，只留下 1GB用作系统空间。
3,windows 2000驻留集管理策略
前言,Windows2000中每个用户进程看到的是一个独立的 32位地址空间，每个进程允许 4G的存储空间。一部分存储空间默认为操作系统保留，因而每个用户空间增加到 3GB，只留下 1GB用作所有进程共享的系统空间。
32位的地址空间：
其大小为,232即
4GB
一,windows2000虚地址映射
1)、虚拟存储空间的分配：
理论上,Windows 2000使用独立的 32位地址空间，每个进程允许 4GB的存储空间。
实际上：一部分存储空间为操作系统保留，因而每个用户实际上有 2GB的可用虚拟地址空间。
Windows 2000有一个选项，可以允许用户空间增加到 3GB，只留下 1GB用作系统空间。
2）、虚拟地址的空间的组成：
0~0X0FFFF：留出来用于帮助程序员捕获空指针赋值。
0X010000~0X7FFEFFF:可以使用的用户地址空间。这个空间划分成页，可以装入主存。
0X7FFF0000~0XFFFFFFF：用户不能访问的保护页。
0X80000000~0XFFFFFFFF：系统地址空间。
二,windows2000页面调度
1)、页面的状态划分：
每一页可以处于以下三个状态：
可用：当前没有被进程使用
保留：虚存管理程序为一个进程保留一组连续的页，但是在被使用之前都没有算在该进程的存储器分配额中。
提交：虚存管理程序在它的页面调度文件中为这类页留出空间。
注：当一个进程创建后，原则上它可以使用整个用户空间。这个空间划分 成固定大小的页，
每个页都可以被取进主存。
2）、页面调度的总准则：
区分保留的存储空间和调拔（可分配）的存储空间。因为减少了为某一特定的进程留出的磁盘空间总量，保持该磁盘空间对其它的进程使用是自由的；允许一个进程或线程声明在需要时可以迅速分配的存储量。
Windows2000使用的驻留集管理方案是可变分配、局部范围的。当一个进程第一次激活时，
给它分配一定数目页、帧作为其工作集。当一个进程访问不在存储器中的某页时。该进程的一个驻留页被换出，这个新页被取进。
3)、页面调度的方法
活动进程的工作集可以使用下面通用性的约束进行调整：
当主存空间很充裕时，虚存管理程序允许活动进程的驻留增长。
当主存空间很称少时，虚存管理程序通过把最近很少使用的页移出活动进程的驻留集，从页减少那些驻留集的大小，
为系统回收主存空间。
