存储器管理的主要对象是内存，由于对外存的管理与对内存的管理相类似，只是它们的用途不同，即外存主要用来存放文件。

存储器的层次结构

　　对于通用计算机而言，存储层次至少应具有三级：最高层为CPU寄存器，中间为主存，最底层是辅存。可以细划为寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等6 层。由于进程可以在很少的时钟周期内使用一条load或store指令对可执行存储器进行访问，速度快；但对辅存的访问则需要通过I/O设备来实现，因此，访问中将涉及到中断、设备驱动程序以及物理设备的运行，速度慢。操作系统的存储管理，负责对可执行存储器的分配、回收以及提供在存储层次间数据移动的管理机制。

• 寄存器：访问速度最快，完全能与CPU协调工作，存器的长度一般以字(word)为单位。寄存器用于加速存储器的访问速度，如用寄存器存放操作数，或用作地址寄存器加快地址转换速度等。 
• 高速缓存：根据程序执行的局部性原理(即程序在执行时将呈现出局部性规律，在一较短的时间内，程序的执行仅局限于某个部分)，将主存中一些经常访问的信息存放在高速缓存中，减少访问主存储器的次数，可大幅度提高程序执行速度。如果没有指令高速缓存，CPU 将会空等若干个周期，直到下一条指令从主存中取出，故有的计算机系统中设置了两级或多级高速缓存。
• 主存储器：CPU的控制部件只能从主存储器中取得指令和数据，数据能够从主存储器读取并将它们装入到寄存器中，或者从寄存器存入到主存储器。CPU 与外围设备交换的信息一般也通过主存储器。由于主存储器的访问速度远低于CPU执行指令的速度，为缓和这一矛盾，在计算机系统中引入了寄存器和高速缓存。
• 磁盘缓存：由于磁盘的I/O速度远低于对主存的访问速度，因此将频繁使用的一部分磁盘数据和信息暂时存放在磁盘缓存中，可减少访问磁盘的次数。磁盘缓存利用主存中的存储空间，来暂存从磁盘中读出(或写入)的信息。

程序的装入与链接

　　首先是要编译，其次是链接，形成一个完整的装入模块(Load Module)，最后是装入，由装入程序(Loader)将装入模块装入内存。

 程序的装入

• 绝对装入方式：在编译时，如果知道程序将驻留在内存的什么位置，那么，编译程序将产生绝对地址的目标代码。绝对装入程序按照装入模块中的地址，将程序和数据装入内存。装入模块被装入内存后，由于程序中的逻辑地址与实际内存地址完全相同，故不须对程序和数据的地址进行修改。只适合于单道程序环境。
• 可重定位装入方式：在多道程序环境下，所得到的目标模块的起始地址通常是从0 开始的，程序中的其它地址也都是相对于起始地址计算的。通常是把在装入时对目标程序中指令和数据的修改过程称为重定位。又因为地址变换通常是在装入时一次完成的，以后不再改变，故称为静态重定位。不允许程序运行时在内存中移动位置。
• 动态运行时装入方式：动态运行时的装入程序在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是相对地址。为使地址转换不影响指令的执行速度，这种方式需要一个重定位寄存器的支持。

程序的链接

　　需要解决两个问题，相对地址问题和变换外部调用符号问题。

• 静态链接：在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块，以后不再拆开。
• 装入时动态链接：指将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式。优点是便于修改和更新，便于实现目标模块的共享。
• 运行时动态链接：指对某些目标模块的链接，是在程序执行中需要该(目标)模块时，才对它进行的链接。在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。

连续分配方式

 　　连续分配方式是指一个用户程序分配一个连续的内存空间。连续分配方式分为单一连续分配、固定分区分配、动态分区分配以及动态重定位分区分配四种方式。

• 单一连续分配方式：把内存分为系统区和用户区两部分，系统区仅提供给OS使用，通常是放在内存的低址部分；用户区是指除系统区以外的全部内存空间，提供给用户使用。只能用于单用户、单任务的操作系统。
• 固定分区分配：将内存用户空间划分为若干个固定大小的区域，在每个分区中只装入一道作业。会维护一个分区使用表。是最简单的一种可运行多道程序的存储管理方式。分区划分有大小相等划分和大大小不等划分两种。缺点是由于每个分区的大小固定，必然会造成存储空间的浪费。

• 动态分区分配：根据进程的实际需要，动态地为之分配内存空间。涉及到分区分配中所用的数据结构、分区分配算法和分区的分配与回收三个问题。

　　数据结构有空闲分区表（表项分区号、分区起始地址，分区大小等）和空闲分区链（如下图，在分区的起始部分，设置一些用于控制分区分配的信息和前向指针；在分区尾部则设置后向指针。注意当分区被分配出去以后，把状态位由“0”改为“1”，此时前、后向指针已无意义。）

 　　分区分配算法有以下5种：

1. 1. 首次适应算法：要求空闲分区链以地址递增的次序链接。在分配内存时，从链首顺序查找，直至找到第一个能满足要求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。若没有找到则此次内存分配失败。其缺点是低址部分不断被划分，会留下许多碎片，而每次查找又都是从低址部分开始，会增加查找时的开销。
   2. 循环首次适应算法：该算法是由首次适应算法演变而成，每次从上次找到的空闲分区的下一个空闲分区开始查找。应设置一起始查寻指针，用于指示下一次起始查寻的空闲分区，并采用循环查找方式，可从尾回到首部。找到后，应调整起始查寻指针。该算法能使内存中的空闲分区分布得更均匀，从而减少了查找空闲分区时的开销。
   3. 最佳适应算法：要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。所谓“最佳”是指每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。为了加速寻找，缺点会留下许多碎片。
   4. 最坏适应分配算法：要求将所有的空闲分区按其容量以从大到小的顺序形成一空闲分区链。扫描整个空闲分区表或链表，总是挑选一个最大的空闲区分割给作业使用，其优点是可使剩下的空闲区不至于太小，产生碎片的几率最小，对中、小作业有利。缺点是它会使存储器中缺乏大的空闲分区。
   5. 快速适应算法：又称为分类搜索法，是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，同时在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。

　　  分区分配与回收

　　分配：设请求的分区大小为u.size，表中每个空闲分区的大小可表示为m.size，size是事先规定的不再切割的剩余分区的大小。若m.size-u.size≤size，说明多余部分太小，可不再切割，将整个分区分配给请求者；否则(即多余部分超过size)，从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区链(表)中。然后，将分配区的首址返回给调用者。

 　　回收：当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点。会有如下4种情况。

1. 回收区与插入点的前一个空闲分区F1相邻接。此时将两分区合并，修改其前一分区F1的大小为两者之和。
2. 回收分区与插入点的后一空闲分区F2相邻接。此时将两分区合并，用回收区的首址作为新空闲区的首址，大小为两者之和。
3. 回收区同时与插入点的前、后两个分区邻接。此时将三个分区合并，使用F1的表项和F1的首址，取消F2的表项，大小为三者之和。
4. 回收区既不与F3邻接，又不与F4邻接。这时应为回收区单独建立一新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。

　　伙伴系统方式是结合固定分区分配和动态分区分配的一种折衷方案。伙伴系统规定，无论已分配分区或空闲分区，其大小均为2 的k 次幂，k 为整数，l≤k≤m，其中：2的1次幂 表示分配的最小分区的大小，2的m次幂 表示分配的最大分区的大小。

　　哈希算法就是利用哈希快速查找的优点，以及空闲分区在可利用空间表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表表头指针。

•  动态重定位分区分配：在连续分配方式中，如果在系统中只有若干个小的分区，即使它们容量的总和大于要装入的程序，但由于这些分区不相邻接，也无法把该程序装入内存。可采用的一种方法是将内存中的所有作业进行移动，使它们全都相邻接，“紧凑”起来。由于经过紧凑后的某些用户程序在内存中的位置发生了变化，此时若不对程序和数据的地址加以修改(变换)，则程序必将无法执行。为此，在每次“紧凑”后，都必须对移动了的程序或数据进行重定位。将相对地址转换为物理地址的工作，被推迟到程序指令要真正执行时进行。须在系统中增设一个重定位寄存器，用它来存放程序(数据)在内存中的起始地址。程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。动态重定位分区分配算法与动态分区分配算法基本上相同，差别仅在于，在这种分配算法中，增加了紧凑的功能，通常，在找不到足够大的空闲分区来满足用户需求时进行紧凑。

 、

　　连续分配方式开销太大，如何实现离散分配方式呢？就有了分页和分段。

基本分页存储管理

　　在分页存储管理方式中，如果不具备页面对换功能，则称为基本的分页存储管理方式，或称为纯分页存储管理方式，它不具有支持实现虚拟存储器的功能，它要求把每个作业全部装入内存后方能运行。

　 分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号，如第0 页、第1 页等。相应地，也把内存空间分成与页面相同大小的若干个存储块，称为(物理)块或页框，也同样为它们加以编号，如0#块、1#块等等。在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”。简单说就是一页对应一个物理块，一个物理块内有固定大小的字节，其大小等于页面大小。页面大小应该适中，太小可使得碎片减小，提高了内存利用率，但是页表过长，占用大量内存，降低了换入换出的速度；太大，减小了页表长度，提高了换入换出的速度，但是碎片增大。页面大小一般选择2的幂。

　　分页地址结构如下：图中的地址长度为32 位，其中0～11 位为页内地址，即每页的大小为4 KB；12～31 位为页号，地址空间最多允许有1 M页。对于某特定机器，其地址结构是一定的。

 　　设逻辑空间地址A，页面大小为L，则页号P和页内地址d可以由如下公式确定：

 　　如何将逻辑上的页与物理上的块一一对应呢，这就需要系统为每个进程建立了一张页面映像表，简称页表。也常在页表的表项中设置一存取控制字段，用于对该存储块中的内容加以保护。

　　有了这个映射表（也就是页表），那么就需要有一个地址变换机构来完成从逻辑地址到物理地址的转换。由于页面大小和物理块大小是相同的，所以页内地址和物理块内地址是对应好的，地址转换机构就只需要借助页表将页号转为物理号即可。页表大多驻留在内存中，在系统中只设置一个页表寄存器PTR，在其中存放页表在内存的始址和页表的长度。平时，进程未执行时，页表的始址和页表长度存放在本进程的PCB 中。当调度程序调度到某进程时，才将这两个数据装入页表寄存器中。因此，在单处理机环境下，虽然系统中可以运行多个进程，但只需一个页表寄存器。　　

　　由于页表是存放在内存中的，这使CPU在每存取一个数据时，都要两次访问内存。第一次是访问内存中的页表，从中找到指定页的物理块号，再将块号与页内偏移量W 拼接，以形成物理地址。第二次访问内存时，才是从第一次所得地址中获得所需数据(或向此地址中写入数据)。为了提高地址变换速度，可在地址变换机构中增设一个具有并行查寻能力的特殊高速缓冲寄存器，又称为“联想寄存器”，或称为“快表”。在CPU给出有效地址后，由地址变换机构自动地将页号P送入高速缓冲寄存器，并将此页号与高速缓存中的所有页号进行比较，若其中有与此相匹配的页号，便表示所要访问的页表项在快表中。于是，可直接从快表中读出该页所对应的物理块号，并送到物理地址寄存器中。如在块表中未找到对应的页表项，则还须再访问内存中的页表，找到后，把从页表项中读出的物理块号送地址寄存器；同时，再将此页表项存入快表的一个寄存器单元中，亦即，重新修改快表。但如果联想寄存器已满，则OS必须找到一个老的且已被认为不再需要的页表项，将它换出。简单说快表就是用于记忆之前访问过的页号的一个高速缓存，方便下次直接使用，快表实时更新，且当缓存区满时按照一定规则替换一些。

 　　现在有一个问题就是页表也需要在内存中存储呀，那么如果页表太长采用连续分配方式肯定不行。解决方法有二，一是用相同的方法对页表进行离散分配存储，这就出现了两级页表和多级页表，这种方式并没有减少页表存储空间，只是将存储分散了；二是只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入，这就是请求调页。

　　两级页表：对于要求连续的内存空间来存放页表的问题，可利用将页表进行分页，并离散地将各个页面分别存放在不同的物理块中的办法来加以解决，同样也要为离散分配的页表再建立一张页表，称为外层页表，在每个页表项中记录了页表页面的物理块号。当外层页表还是过长时，可以对外层页表在分页，形成多级页表。

基本分段存储管理

　　在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。例如，有主程序段MAIN、子程序段X、数据段D 及栈段S等。每个段都有自己的名字，通常可用一个段号来代替段名，每个段都从0开始编址，并采用一段连续的逻辑地址空间。段的长度由相应的逻辑信息组的长度决定，因而各段长度不等。整个作业的地址空间由于是分成多个段，因而是二维的，亦即，其逻辑地址由段号(段名)和段内地址所组成。

　　引入分段的需求是：

• 方便编程。希望要访问的逻辑地址是由段名(段号)和段内偏移量(段内地址)决定的；
• 信息共享。在实现对程序和数据的共享时，是以信息的逻辑单位为基础的，而段是信息的逻辑单位；
• 信息保护。信息保护同样是对信息的逻辑单位进行保护；
• 动态增长。往往有些段，特别是数据段，在使用过程中会不断地增长，而事先又无法确切地知道数据段会增长到多大；
• 动态链接。要运行时，先将主程序所对应的目标程序装入内存并启动运行，当运行过程中又需要调用某段时，才将该段(目标程序)调入内存并进行链接。可见，动态链接也要求以段作为管理的单位。

　　在该地址结构中，允许一个作业最长有64 K个段，每个段的最大长度为64 KB。

　　和分页管理一样，分段管理也需要段表、地址变换机构、快表等。

　　系统为每个分段分配一个连续的分区（类似于分页中每页对应一个连续的物理块），而进程中的各个段可以离散地移入内存中不同的分区中。为使程序能正常运行，亦即，能从物理内存中找出每个逻辑段所对应的位置，应像分页系统那样，在系统中为每个进程建立一张段映射表，简称“段表”。每个段在表中占有一个表项，其中记录了该段在内存中的起始地址(又称为“基址”)和段的长度。段表可以存放在一组寄存器中，这样有利于提高地址转换速度，但更常见的是将段表放在内存中。

　　信息共享

　　分段存储管理允许若干个进程共享一个或多个分段，且对段的保护也十分简单易行。在分页系统中，虽然也能实现程序和数据的共享，但远不如分段系统来得方便。

　　例如，有一个多用户系统，他们都执行一个文本编辑程序。

　　分页 vs. 分段

• 页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率，或者说，分页仅仅是由于系统管理的需要而不是用户的需要。段则是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。
• 页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。
• 分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址；而分段的作业地址空间则是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。

段页式存储管理方式

　　段页式系统的基本原理，是分段和分页原理的结合，即先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名。

　　在段页式系统中，为了获得一条指令或数据，须三次访问内存。第一次访问是访问内存中的段表，从中取得页表始址；第二次访问是访问内存中的页表，从中取出该页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理地址；第三次访问才是真正从第二次访问所得的地址中，取出指令或数据。为了提高执行速度，在地址变换机构中增设一个高速缓冲寄存器，每次访问它时，都须同时利用段号和页号去检索高速缓存。

虚拟存储器

　当作业太多或者作业数太多，内存容量无法满足时，可以从逻辑上扩充内存容量，这正是虚拟存储器所要解决的主要问题。所谓虚拟存储器，是指具有请求调入功能和置换功能，利用外存，从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。虚拟存储器具有多次性、对换性和虚拟性三大主要特征。

　　程序局部性原理：程序在执行时将呈现出局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域。时间局限性。如果程序中的某条指令一旦执行，则不久以后该指令可能再次执行；如果某数据被访问过，则不久以后该数据可能再次被访问。产生时间局限性的典型原因是由于在程序中存在着大量的循环操作。空间局限性。一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，其典型情况便是程序的顺序执行。

　　基于局部性原理，应用程序在运行之前，没有必要全部装入内存，仅须将那些当前要运行的少数页面或段先装入内存便可运行，其余部分暂留在盘上。程序在运行时，如果它所要访问的页(段)已调入内存，便可继续执行下去；但如果程序所要访问的页(段)尚未调入内存(称为缺页或缺段)，此时程序应利用OS所提供的请求调页(段)功能，将它们调入内存，以使进程能继续执行下去。如果此时内存已满，无法再装入新的页(段)，则还须再利用页(段)的置换功能，将内存中暂时不用的页(段)调至盘上，腾出足够的内存空间后，再将要访问的页(段)调入内存，使程序继续执行下去。

　　虚拟存储器的实现

　　分页系统的基础上，增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。主要的硬件支持有：① 请求分页的页表机制，它是在纯分页的页表机制上增加若干项而形成的，作为请求分页的数据结构；② 缺页中断机构，即每当用户程序要访问的页面尚未调入内存时，便产生一缺页中断，以请求OS将所缺的页调入内存；③ 地址变换机构，它同样是在纯分页地址变换机构的基础上发展形成的。实现请求分页的软件：包括有用于实现请求调页的软件和实现页面置换的软件。

　　在分段系统的基础上，增加了请求调段及分段置换功能后所形成的段式虚拟存储系统。主要的硬件支持有：(1) 请求分段的段表机制，这是在纯分段的段表机制基础上增加若干项而形成的；(2) 缺段中断机构，每当用户程序所要访问的段尚未调入内存时，产生一个缺段中断，请求OS将所缺的段调入内存；(3) 地址变换机构。与请求调页相似，实现请求调段和段的置换功能也须得到相应的软件支持。

请求分页存储管理

　请求分页系统是建立在基本分页基础上的，为了能支持虚拟存储器功能而增加了请求调页功能和页面置换功能。需要有页表机制、缺页中断机构、地址变换机构以及请求调页和置换功能的软件。

　　页表机制，页表项如下：

• 状态位P：用于指示该页是否已调入内存，供程序访问时参考。
• 访问字段A：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供选择换出页面时参考。
• 修改位M：表示该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本，因此，若未被修改，在置换该页时就不需再将该页写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。简言之，M位供置换页面时参考。
• 外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考

　　缺页中断在请求分页系统中，每当所要访问的页面不在内存时，便产生一缺页中断，请求OS将所缺之页调入内存。缺页中断作为中断，它们同样需要经历诸如保护CPU环境、分析中断原因、转入缺页中断处理程序进行处理、恢复CPU环境等几个步骤。缺页中断与一般中断区别：在指令执行期间产生和处理中断信号、一条指令在执行期间，可能产生多次缺页中断。

　　地址转换机构：

　　内存分配策略和分配算法

　　在请求调页存储管理系统中为进程分配内存时，将涉及到三个问题：第一，最小物理块数的确定；第二，物理块的分配策略；第三，物理块的分配算法。

　最小物理块数，是指能保证进程正常运行所需的最小物理块数。对于某些简单的机器，若是单地址指令且采用直接寻址方式，则所需的最少物理块数为2。其中，一块是用于存放指令的页

面，另一块则是用于存放数据的页面。

　　物理块的分配策略在请求分页系统中，可采取两种策略，即固定和可变分配策略。在进行置换时，也可采取两种策略，即全局置换和局部置换。有了如下组合：

　　固定分配局部置换，指基于进程的类型(交互型或批处理型等)，或根据程序员、程序管理员的建议，为每个进程分配固定数目的物理块，在整个运行期间都不再改变。采用该策略时，如果进程在运行中发现缺页，则只能从该进程在内存的n 个页面中选出一个页换出，然后再调入一页，以保证分配给该进程的内存空间不变。

　　可变分配全局置换，先为系统中的每个进程分配一定数目的物理块，而OS自身也保持一个空闲物理块队列。当某进程发现缺页时，由系统从空闲物理块队列中取出一个物理块分配给该进程，并将欲调入的(缺)页装入其中。这样，凡产生缺页(中断)的进程，都将获得新的物理块。仅当空闲物理块队列中的物理块用完时，OS才能从内存中选择一页调出，该页可能是系统中任一进程的页。

　　可变分配局部置换，这同样是基于进程的类型或根据程序员的要求，为每个进程分配一定数目的物理块，但当最初某进程发现缺页时，只允许从该进程在内存的页面中选出一页换出，这样就不会影响其它进程的运行。如果进程在运行中频繁地发生缺页中断，则系统须再为该进程分配若干附加的物理块，直至该进程的缺页率减少到适当程度为止；反之，若一个进程在运行过程中的缺页率特别低，则此时可适当减少分配给该进程的物理块数。

　　物理块的分配算法，如何将系统中可供分配的所有物理块分配给各个进程，可采用下述几种算法：平均分配算法、 按比例分配算法、考虑优先权的分配算法。

　　调页策略

　　调度时机：预调页策略、请求调页策略。

　　从何处调入：在请求分页系统中的外存分为两部分，用于存放文件的文件区和用于存放对换页面的对换区。通常，由于对换区是采用连续分配方式，而文件区是采用离散分配方式，故对换区的磁盘I/O 速度比文件区的高。

　　页面置换算法

　　那么选择哪一或者哪些页面置换出去呢？

　　最佳置换算法：其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。但这是一种理想算法，由于人们目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用该算法去评价其它算法。

　　先进先出(FIFO)页面置换算法：该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。

　　最近最久未使用(LRU，Least Recently Used)置换算法：选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t 值最大的，即最近最久未使用的页面予以淘汰。为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为R = Rn-1Rn-2Rn-3 … R2R1R0。当进程访问某物理块时，要将相应寄存器的Rn－1 位置成1。此时，定时信号将每隔一定时间(例如100 ms)将寄存器右移一位。

 　　可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号。

 　　Clock置换算法：LRU 算法是较好的一种算法，但由于它要求有较多的硬件支持，故在实际应用中，大多采用LRU的近似算法，Clock算法就是用得较多的一种LRU近似算法。当采用简单Clock算法时，只需为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位被置1。置换算法在选择一页淘汰时，只需检查页的访问位。如果是0，就选择该页换出；若为1，则重新将它置0，暂不换出，而给该页第二次驻留内存的机会，再按照FIFO 算法检查下一个页面。当检查到队列中的最后一个页面时，若其访问位仍为1，则再返回到队首去检查第一个页面。

　　在将一个页面换出时，如果该页已被修改过，便须将该页重新写回到磁盘上；但如果该页未被修改过，则不必将它拷回磁盘。在改进型Clock算法中，除须考虑页面的使用情况外，还须再增加一个因素，即置换代价。由访问位A和修改位M可以组合成下面四种类型的页面：

 　　改进型clock算法步骤：

1. 从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。
2. 如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。
3. 如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。

　　最少使用(LFU：Least Frequently Used)置换算法：在采用最少使用置换算法时，应为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。

　　页面缓冲算法(PBA：Page Buffering Algorithm)：它采用了前述的可变分配和局部置换方式，置换算法采用的是FIFO。该算法规定将一个被淘汰的页放入两个链表中的一个，即如果页面未被修改，就将它直接放入空闲链表中；否则，便放入已修改页面的链表中。当需要读入一个页面时，便可利用空闲物理块链表中的第一个物理块来装入该页。当有一个未被修改的页要换出时，实际上并不将它换出内存，而是把该未被修改的页所在的物理块挂在自由页链表的末尾。类似地，在置换一个已修改的页面时，也将其所在的物理块挂在修改页面链表的末尾。

请求分段存储管理

 　　请求分段管理所需的硬件支持有段表机制、缺段中断机构，以及地址变换机构。

• 存取方式：用于标识本分段的存取属性是只执行、只读，还是允许读/写。
• 访问字段A：其含义与请求分页的相应字段相同，用于记录该段被访问的频繁程度。
• 修改位M：用于表示该页在进入内存后是否已被修改过，供置换页面时参考。
• 存在位P：指示本段是否已调入内存，供程序访问时参考。
• 增补位：这是请求分段式管理中所特有的字段，用于表示本段在运行过程中是否做过动态增长。
• 外存始址：指示本段在外存中的起始地址，即起始盘块号。

 缺段中断机构

 　　地址转换机构

 　　分段共享

　　为了实现分段共享，可在系统中配置一张共享段表，所有各共享段都在共享段表中占有一表项。表项中记录了共享段的段号、段长、内存始址、存在位等信息，并记录了共享此分段的每个进程的情况。

　　共享段的分配：在为共享段分配内存时，对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，再把共享段调入该区，同时将该区的始址填入请求进程的段表的相应项中，还须在共享段表中增加一表项，填写有关数据，把count 置为1；之后，当又有其它进程需要调用该共享段时，由于该共享段已被调入内存，故此时无须再为该段分配内存，而只需在调用进程的段表中增加一表项，填写该共享段的物理地址；在共享段的段表中，填上调用进程的进程名、存取控制等，再执行count :=count+1 操作，以表明有两个进程共享该段。

　　共享段的回收：当共享此段的某进程不再需要该段时，应将该段释放，包括撤消在该进程段表中共享段所对应的表项，以及执行count :=count-1 操作。若结果为0，则须由系统回收该共享段的物理内存，以及取消在共享段表中该段所对应的表项，表明此时已没有进程使用该段；否则(减1 结果不为0)，只是取消调用者进程在共享段表中的有关记录。

　　分段保护

　　在分段系统中，由于每个分段在逻辑上是独立的，因而比较容易实现信息保护。目前，常采用以下几种措施来确保信息的安全：越界检查、存取控制检查、环保护机构。

　　环保护机构规定：低编号的环具有高优先权。OS核心处于0 环内；某些重要的实用程序和操作系统服务占居中间环；而一般的应用程序则被安排在外环上。

　　在环系统中，程序的访问和调用应遵循以下规则：

• 一个程序可以访问驻留在相同环或较低特权环中的数据。
• 一个程序可以调用驻留在相同环或较高特权环中的服务。

参考

　　《计算机操作系统》第三版 汤小丹