1. 请求分页存储管理方式

请求分页系统是建立在基本分页基础上的，为了能支持虚拟存储器功能，而增加了请求调页功能和页面置换功能。

相应地，每次调入和换出的基本单位都是长度固定的页面。因此，请求分页便称为目前最常用的一种实现虚拟存储器的方式。

1.1 请求分页中的硬件支持

为了实现请求分页，系统必须提供一定的硬件支持。计算机系统除了要求一定容量的内存和外存外，还需要有请求页表机制、缺页中断机制以及地址变换机构。

1.1.1 请求页表机制

在请求分页系统中需要的主要数据结构是请求页表，其基本作仍然是将用户地址空间中的逻辑地址映射为内存空间中的物理地址。

为了满足页面换进换出的需要，在请求页表中又增加了四个字段。

• 状态位（存在位）P：用于指示该页是否已调入内存

• 访问字段A：用于记录本页在一段时间内被访问的次数

• 修改位M：标识该页在调入内存后是否被修改过

• 外存地址：用于指出该页在外存上的地址

1.1.2 缺页中断机构

在请求分页系统中，每当所要访问的页面不在内存时，便产生一缺页中断，请求OS将所缺之页调入内存。

缺页中断是一种特殊的中断，它与一般的中断相比有着明显的区别，主要表现在两个方面：

• 在指令执行期间产生和处理中断信号
• 一条指令在执行期间可能产生多次缺页中断

1.1.3 地址变换机构

如图展示请求分页系统中的地址变换过程

2. 页面置换算法

2.1 介绍

在进程运行过程中，若其所要访问的页面不在内存，而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送到磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法（Page-Replacement Algorithm）。

不适当的算法可能会导致进程发生“抖动”（Thrashing），即刚被换出的页很快又要被访问，需要将它重新调入，此时又需要再选一页调出，而此刚被换出的页很快又要被访问，又需将它调入，因此我们称该进程发生了“抖动”。

2.2 最佳（Optimal）置换算法

介绍：

最佳置换算法是一种较为极端，理想化的算法，它具有最好的性能，但实际上是无法实现的。通常以其为标准，来衡量其它算法的优劣。

原理：

其所选择的被淘汰页面将是以后永不使用的，或许是在最长（未来）时间内不再被访问的页面。

特点：

• 可保证获得最低的缺页率

• 因人们无法预知一个进程在内存的若干个页面中，究竟哪个是未来最长时间内不再被访问的，故该算法无法实现

2.3 先进先出页面置换算法（FIFO）

原理：

总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入的页面按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总指向最老的页面。

特点：

通常与进程实际运行的规律不相适应，因为有些页面会经常被访问，如全局变量、常用函数等，故可能是性能最差的算法，实际应用极少。

2.4 最近最久未使用置换算法（LRU，Least Recently Used）

原理：

该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t。当需淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。

特点：

• 该算法是根据页面调入内存后的使用情况做出决策的

• 要求系统有较多的支持硬件，为了了解一个进程在内存中的各个页面各有多少时间未被进程访问，以及如何快速地知道哪一页是最近最久未使用的页面，须有寄存器和栈两类硬件之一的支持。

2.5 最少使用置换算法（LFU， Least Frequently Used）

原理：

该算法为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。每次访问某页时，便将该移位寄存器的最高位置1，再每隔一定时间（例如100ms）右移一次。LFU置换算法的页面访问图与上面的LRU置换算法的访问图完全相同。

或者说，利用一套硬件既可实现LRU算法，又可实现LFU算法。

特点：

这种算法并不能真正反映出页面的使用情况，因为在每一时间间隔内，只是用寄存器的一位来记录页的使用情况。因此，在该时间间隔内，对某页访问一次和访问100次效果等效。

2.6 简单的Clock置换算法

介绍：

LRU算法需要较多硬件支持，成本较高，实际应用中，大多采用LRU的近似算法。Clock算法就是用得较多的一种LRU近似算法。

原理：

当利用简单的Clock置换算法时，只需为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。

当某页被访问时，其访问位被置1。置换算法在选择一页淘汰时，只需检查页的访问位。如果是0，选择该页换出；若为1，则重新将它置0，暂不换出，给予该页第二次驻留内存的机会，

再按照FIFO算法检查下一个页面。当检查到队列中的最后一个页面，若其访问为仍为1，则再返回到队首去检查第一个页面。

特点：

该算法是循环地检查各页面的使用情况，故称为Clock算法

因该算法只有一位访问位，只能用其表示该页是否已经使用过，而置换是将未使用过的页面换出去，故该算法又称为最近未用算法或者NRU（Not Recently Used）算法。

2.7 页面缓冲算法（PBA，Page Buffering Algorithm）

内存分配策略上采用了可变分配和局部置换方式，系统为每个进程分配一定数目的物理块，系统自己保留一部分空闲物理块。

为了能显著地降低页面换进、换出地频率，在内存中设置了如下两个链表：

• 空闲页面链表

实际上该链表是一个空闲物理块链表，是系统掌握地空闲物理块，用于分配给频繁发生缺页的进程，已降低该进程的缺页率。

当进程需要读入一个页面时，便可利用空闲物理链表中的第一个物理块来装入该页；

当有一个未被修改的页要换出时，实际上并不将它换出到外存，而是把它们所在的物理块挂在空闲链表的末尾。

• 修改页面链表

该链表是由已修改的页面所形成的链表。设置该链表的目的是为了减少已修改页面换出的次数。

当进程需要将一个已修改的页面换出时，系统并不立即把它换出到外存上，而是将它所在的物理块挂在修改页面链表的末尾。

• PBA算法特点：

1. 显著地降低了页面换进、换出的频率，使磁盘I/O的操作次数大为减少，减少了页面换进、换出的开销。
2. 正是由于换入换出的开销大幅度减小，才能使其采用一种较简单的置换策略，如先进先出（FIFO）算法，它并不需要特殊硬件的支持，实现起来非常简单。

参考：《计算机操作系统》（第四版，汤小凤）

看教材枯燥，码字记录提神，根据计算机操作系统（第四版，汤小凤）个人整理，仅作学习记录 :)

请求分页系统是建立在基本分页基础上的，为了能支持虚拟存储器功能，而增加了请求调页功能和页面置换功能。相应地，每次调入和换出的基本单位都是长度固定的页面，这使得请求分页系统在实现上要比请求分段系统简单（后者在换进和换出时是可变长度的段）。因此，请求分页便成为目前最常用的一种实现虚拟存储器的方式。

请求分页中的硬件支持

为了实现请求分页，系统必须提供一定的硬件支持。计算机系统除了要求一定容量的内存和外存外，还需要有请求页表机制、缺页中断机构以及地址变换机构。

1．请求页表机制

在请求分页系统中需要的主要数据结构是请求页表，其基本作用仍然是将用户地址空间中的逻辑地址映射为内存空间中的物理地址。为了满足页面换进换出的需要，在请求页表中又增加了四个字段。这样，在请求分页系统中的每个页表应含以下诸项：

• (1）状态位（存在位） P ：由于在请求分页系统中，只将应用程序的一部分调入内存，还有一部分仍在外存磁盘上，故须在页表中增加一个存在位字段。由于该字段仅有一位，故又称位字。它用于指示该页是否已调入内存，供程序访问时参考。
• (2）访问字段 A ：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，提供给置换算法（程序）在选择换出页面时参考。
• (3）修改位 M ：标识该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本，因此，在置换该页时，若未被修改，就不需再将该页写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的副本始终是最新的。简而言之， M 位供置换页面时参考。
• (4）外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考。

2．缺页中断机构

在请求分页系统中，每当所要访问的页面不在内存时，便产生一缺页中断，请求 OS 将所缺之页调入内存。缺页中断作为中断，它们同样需要经历诸如保护 CPU 环境、分析中断原因、转入缺页中断处理程序进行处理，以及在中断处理完成后再恢复 CPU 环境等几个步骤。但缺页中断又是一种特殊的中断，它与一般的中断相比有着明显的区别，主要表现在下面两个方面：

• (1）在指令执行期间产生和处理中断信号。通常， CPU 都是在一条指令执行完后，才检查是否有中断请求到达。若有，便去响应，否则，继续执行下一条指令。然而，缺页中断是在指令执行期间，若发现所要访问的指令或数据不在内存时，便立即产生和处理缺页中断信号，以便能及时将所缺之页面调入内存。
• (2）一条指令在执行期间可能产生多次缺页中断。在图5-1中示出了一个例子。如在执行一条指令 copy A to B 时，可能要产生6次缺页中断，其中指令本身跨了两个页面， A 和 B 又分别各是一个数据块，也都跨了两个页面。基于这些特征，系统中的硬件机构应能保存多次中断时的状态，并保证最后能返回到中断前产生缺页中断的指令处继续执行。
  

3．地址变换机构

请求分页系统中的地址变换机构是在分页系统地址变换机构的基础上，为实现虚拟存储器，再增加了某些功能所形成的，如产生和处理缺页中断，以及从内存中换出一页的功能等等。下图示出了请求分页系统中的地址变换过程。

在进行地址变换时，首先检索快表，试图从中找出所要访问的页。若找到，便修改页表项中的访问位，供置换算法选换出页面时参考。对于写指令，还须将修改位置成“1”,表示该页在调入内存后已被修改。然后利用页表项中给出的物理块号和页内地址形成物理地址。地址变换过程到此结束。
如果在快表中未找到该页的页表项，则应到内存中去查找页表，再从找到的页表项中的状态位 P 来了解该页是否已调入内存。若该页已调入内存，这时应将该页的页表项写入快表。当快表已满时，则应先调出按某种算法所确定的页的页表项，然后再写入该页的页表项；若该页尚未调入内存，这时应产生缺页中断，请求 OS 从外存把该页调入内存。

请求分页中的内存分配

在为进程分配内存时，将涉及到三个问题：

• 第一，为保证进程能正常运行，所需要的最小物理块数的确定；
• 第二，在为每个进程分配物理块时，应采取什么样的分配策略，即所分配的物理块是固定的，还是可变的；
• 第三，为不同进程所分配的物理块数，是采取平均分配算法，还是根据进程的大小按比例分配。

1．最小物理块数的确定

一个显而易见的事实是，随着为每个进程所分配的物理块的减少，将使进程在执行中的缺页率上升，从而会降低进程的执行速度。为使进程能有效地工作，应为它分配一定数目的物理块，但这并不是最小物理块数的概念。
最小物理块数是指能保证进程正常运行所需的最小物理块数，当系统为进程分配的物理块数少于此值时，进程将无法运行。至于进程应获得的最少物理块数，与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。对于某些简单的机器，若是单地址指令，且采用直接寻址方式，则所需的最少物理块数为2。其中，一块是用于存放指令的页面，另一块则是用于存放数据的页面。如果该机器允许间接寻址，则至少要求有三个物理块。对于某些功能较强的机器，其指令长度可能是两个或多于两个字节，因而其指令本身有可能跨两个页面，且源地址和目标地址所涉及的区域也都可能跨两个页面。正如前面所介绍的在缺页中断机构中要发生6次中断的情况一样，对于这种机器，至少要为每个进程分配6个物理块，以装入6个页面。

2．内存分配策略

在请求分页系统中，可采取两种内存分配策略，即固定和可变分配策略。在进行置换时，也可采取两种策略，即全局置换和局部置换。于是可组合出以下三种适用的策略。

• 1）固定分配局部置换（ Fixed Allocation , Local Replacement )
  所谓固定分配，是指为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。所谓局部置换，是指如果进程在运行中发现缺页，则只能从分配给该进程的 n 个页面中选出一页换出，然后再调入一页，以保证分配给该进程的内存空间不变。采用该策略时，为每个进程分配多少物理块是根据进程类型（交互型或批处理型等）或根据程序员、程序管理员的建议来确定的。实现这种策略的困难在于：应为每个进程分配多少个物理块难以确定。若太少，会频繁地出现缺页中断，降低了系统的吞吐量。若太多，又必然使内存中驻留的进程数目减少，进而可能造成 CPU 空闲或其它资源空闲的情况，而且在实现进程对换时，会花费更多的时间。
• 2）可变分配全局置换（ Variable Allocation , Global Replacement )
  所谓可变分配，是指先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。所谓全局置换，是指如果进程在运行中发现缺页，则将 os 所保留的空闲物理块（一般组织为一个空闲物理块队列）取出一块分配给该进程，或者以所有进程的全部物理块为标的，选择一块换出，然后将所缺之页调入。这样，分配给该进程的内存空间就随之增加。可变分配全局置换这可能是最易于实现的一种物理块分配和置换策略，已用于若干个 os 中。在采用这种策略时，凡产生缺页（中断）的进程，都将获得新的物理块，仅当空闲物理块队列中的物理块用完时， os 才能从内存中选择一页调出。被选择调出的页可能是系统中任何一个进程中的页，因此这个被选中的进程拥有的物理块会减少，这将导致其缺页率增加。
• 3）可变分配局部置换（ Variable Allocation , Local Replacement )
  该策略同样是基于进程的类型或根据程序员的要求，为每个进程分配一定数目的物理块，但当某进程发现缺页时，只允许从该进程在内存的页面中选择一页换出，这样就不会影响其它进程的运行。如果进程在运行中频繁地发生缺页中断，则系统须再为该进程分配若干附加的物理块，直至该进程的缺页率减少到适当程度为止。反之，若一个进程在运行过程中的缺页率特别低，则此时可适当减少分配给该进程的物理块数，但不应引起其缺页率的明显增加。

3．物理块分配算法

在采用固定分配策略时，如何将系统中可供分配的所有物理块分配给各个进程，可采用下述几种算法；

• (1）平均分配算法，即将系统中所有可供分配的物理块平均分配给各个进程。例如，当系统中有100个物理块，有5个进程在运行时，每个进程可分得20个物理块。这种方式貌似公平，但由于未考虑到各进程本身的大小，会造成实际上的不公平。假设系统平均分配给每个进程20个物理块，这样，一个进程只有10页，闲置了10个物理块，而另外一个进程有200页，也仅被分配了20块，显然，后者必然会有很高的缺页率。
• (2）按比例分配算法，即根据进程的大小按比例分配物理块。如果系统中共有 n 个进程，每个进程的页面数为 S_i，则系统中各进程页面数的总和为：
  $S={\sum }_{i=1}^n{S}_i$
  又假定系统中可用的物理块号总数为m，则每个进程所能分到的物理块号为b_i可由下式计算：
  $bi=\frac{Si}{S}\times m$
  这里， b_i 应该取整，它必须大于最小物理块数。
• (3）考虑优先权的分配算法。在实际应用中，为了照顾到重要的、紧迫的作业能尽快地完成，应为它分配较多的内存空间。通常采取的方法是把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权进行分配，为高优先进程适当地增加其相应份额。在有的系统中，如重要的实时控制系统，则可能是完全按优先权为各进程分配其物理块的。

页面调入策略

为使进程能够正常运行，必须事先将要执行的那部分程序和数据所在的页面调入内存。现在的问题是：

• (1）系统应在何时调入所需页面；
• (2）系统应从何处调入这些页面；
• (3）是如何进行调入的。

1．何时调入页面

为了确定系统将进程运行时所缺的页面调入内存的时间，可采取预调页策略或请求调页策略，现分述如下。

(1）预调页策略。

如果进程的许多页是存放在外存的一个连续区域中，一次调入若干个相邻的页会比一次调入一页更高效些。但如果调入的一批页面中的大多数都未被访问， 则又是低效的。于是便考虑采用一种以预测为基础的预调页策略，将那些预计在不久之后会被访问的页面预先调入内存。如果预测较准确，那么这种策略显然是很有吸引力的。但遗憾的是，目前预调页的成功率仅约50%。
但预调页策略又因其特有的长处取得了很好的效果。首先可用于在第一次将进程调入内存时，此时可将程序员指出的那些页先调入内存。其次是，在采用工作集的系统中，每个进程都具有一张表，表中记求有运行时的工作集，每当程序被调度运行时，将工作集中的所有页调入内存。

(2）请求调页策略。

当进程在运行中需要访问某部分程序和数据时，若发现其所在的页面不在内存，便即提出请求，由 OS 将其所需页面调入内存。由请求调页策略所确定调入的页是一定会被访问的，再加之请求调页策略比较易于实现，故在目前的虚拟存储器中，大多来用此策略。但这种策略每次仅调入一页，故须花费较大的系统开销，增加了磁盘 I / O 的启动频率。

2．从何处调入页面

将请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。通常，由于对换区是采用连续分配方式，而文件区是采用离散分配方式，所以对换区的数据存取（磁盘 I / O ）速度比文件区的高。这样，每当发生缺页请求时，系统应从何处将缺页调入内存，可分成如下三种情况进行：
(1）系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度。为此，在进程运行前，便须将与该进程有关的文件从文件区拷贝到对换区。
(2）系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改，则不必再将它们重写到磁盘（换出），以后再调入时，仍从文件区直接调入。但对于那些可能被修改的部分，在将它们换出时便须调到对换区，以后需要时再从对换区调入。
(3) UNIX 方式。由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时应从对换区调入。由于 UNIX 系统允许页面共享，因此，某进程所请求的页面有可能已被其它进程调入内存，此时也就无需再从对换区调入。

3．页面调入过程

每当程序所要访问的页面未在内存时（存在位为“0”)，便向 CPU 发出一缺页中断，中断处理程序首先保留 CPU 环境，分析中断原因后转入缺页中断处理程序。该程序通过查找页表得到该页在外存的物理块后，如果此时内存能容纳新页，则启动磁盘I/O，将所缺之页调入内存，然后修改页表。如果内存已满，则须先按照某种置换算法，从内存中选出一页准备换出；如果该页未被修改过（修改位为“0”)，可不必将该页写回磁盘；但如果此页已被修改（修改位为“1”)，则必须将它写回磁盘，然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。在缺页调入内存后，利用修改后的页表形成所要访问数据的物理地址，再去访问内存数据。整个页面的调入过程对用户是透明的。

4．缺页率

假设一个进程的逻辑空间为 n 页，系统为其分配的内存物理块数为 m ( m ≤ n )。如果在进程的运行过程中，访问页面成功（即所访问页面在内存中）的次数为 S ，访问页面失败（即所访问页面不在内存中，需要从外存调入）的次数为 F ，则该进程总的页面访问次数为 A = S + F ，那么该进程在其运行过程中的缺页率即为
$f=\frac{F}{A}$
通常，缺页率受到以下几个因素的影响：

• (1）页面大小。页面划分较大，则缺页率较低；反之，缺页率较高。
• (2）进程所分配物理块的数目。所分配的物理块数目越多，缺页率越低；反之则越高。
• (3）页面置换算法。算法的优劣决定了进程执行过程中缺页中断的次数，因此缺页率是衡量页面置换算法的重要指标。
• (4）程序固有特性。程序本身的编制方法对缺页中断次数有影响，根据程序执行的局部性原理，程序编制的局部化程度越高，相应执行时的缺页程度越低。

事实上，在缺页中断处理时，当由于空间不足，需要置换部分页面到外存时，选择被置换页面还需要考虑到置换的代价，如页面是否被修改过。没有修改过的页面可以直接放弃，而修改过的页面则必须进行保存，所以处理这两种情况时的时间也是不同的。假设被置换的页面被修改的概率是 β，其缺页中断处理时间为t_a，被置换页面没有被修改的缺页中断时间为 t_b，那么，缺页中断处理时间的计算公式为
$t=\beta \times ta+(1-\beta )\times tb$

请求分页中的硬件支持
1.页表机制
●基本作用:地址转换
●增加页表字段，供程序在换入换出时参考

状态位P:用于指示该页是否已调入内存
访问字段A:记录本页在一段时间内被访问的次数
修改位M:该页在调入内存后是否被修改过
外存地址：指示该页在外存上的地址（物理块号）
2.缺页中断机构:
●缺页中断与其他中断的不同:
(1)在指令执行期间产生和处理中断信号
(2)一条指令在执行期间可能产生多次缺页中断

3.地址变换机构

内存分配策略和分配算法
1.最小物理块数的确定:
●保证进程正常运行所需的最小物理块数;
●与硬件结构有关，取决于指令的格式、功能和寻址方式。
2.物理块的分配策略:
●两种内存分配策略:
■固定分配:为进程分配的物理块数固定不变。
■可变分配:先为每个进程分配一定 数目的物理块，若发生缺页中断，再增加物理块数。
●两种置换策略:
■局部置换:只能将自己的某个内存页换出。
■全局置换：可将系统中任一进程的内存页换出。
●组合出以下三种适用策略:
■(1) 固定分配局部置换
■(2) 可变分配全局置换
■(3)可变分配局部置换
3.物理块分配算法:
●(1)平均分配算法
●(2)按比例分配算法:根据进程大小按比例分
配（Si/s）*m (m:物理块总数，S:各进程页面总数)
●(3)考虑优先权的分配算法:一-部分按比例分配;另一部分为优先权高的进程增加分配份额
调页策略
1.调入页面的时机:
●预调页策略:进程首次调入内存时，由程序员指出应该先调入哪些页。
●请求调页策略:进程运行中发生缺页时，提出请求，由OS将其所需页面调入内存。
2.确定从何处调入页面:
请求分页系统将外存分为两部分:
文件区(离散分配)、 对换区(连续分配)
●发生缺页请求时，有以下三种情况:
系统拥有足够的对换区空间
系统缺少足够的对换区空间
UNIX方式
3.页面调入过程:
①若发生缺页，便向CPU发出缺页中断
②中断处理程序保存CPU环境，转中断处理程序
③该程序查找页表，得到该页在外存中的块号
④若内存未满，启动磁盘I/O调入页面;若内存已满，先置换再调入
⑤修改页表项内容，并写入快表。