一般的通用计算机至少将存储器分为CPU寄存器、主存、辅存三个层次，而在较高档的计算机中，还将存储器进一步细分为寄存器、高速缓存、主存储器、固定磁盘、可移动介质等多层次

在存储层次中，层次越高，存储介质的访问速度越快，价格越高，相应的存储容量也越小。

其中寄存器、高速缓存、主存储器、磁盘缓存均属于操作系统存储管理的管辖范畴，掉电后存储信息不再存在

低层的固定磁盘、可移动存储介质则属于设备管理范畴，存储信息将长久保存

主存储器的分配和管理：按用户要求把适当的存储空间分配给相应的作业。一个有效的存储分配机制，应在用户请求时能快速的做出相应，分配相应的存储空间；在用户不使用的时候，应该立即回收，以供其他用户使用。为此应该具有如下三个功能：

记住每个存储区域的状态

实施分配

接收系统或用户释放的存储区域

提高主存储器的利用率：使多道程序能动态地共享主存，最好能共享主存中的信息

扩充主存容量：借助虚拟存储器或其他自动覆盖技术实现

存储保护：确保各道用户作业都在所分配的存储区内操作，互不干扰。

解决存储分配的三种方式

直接指定方式：程序员在编程序时，或编译程序对源程序进行编译时，使用实际存储地址

在多道程序环境下应保证各作业所用地址互不重叠。

缺点：用户使用不便，而且存储空间的利用也不那么有效

静态分配方式：用户编程时，或由编译程序产生的目的程序，均可从其地址空间的零地址开始；当装配程序对其连接装入时才确定他们在主存中的相应位置，从而生成可执行程序。

(1)在一个作业装入时必须分配其要求的全部存储量；

(2)如果没有足够的存储空间，就不能装入该作业；

(3)一旦一个作业进入内存后，在其退出系统之前，它一直占用着分配给它的全部存储空间；

(4) 作业在整个运行过程中不能在内存中“搬家”、也不能再申请存储量。

动态分配方式

(1)作业在存储空间中的位置，也是在其装入时确定的；

(2)在其执行过程中可根据需要申请附加的存储空间；

(3)一个作业已占用的部分存储区域不再需要时，可以要求归还给系统。

即：这种存储分配机制能接受不可预测的分配和释放存储区域的请求，实现个别存储区域的分配和回收；

(4)存储区域的大小是可变的；

(5)允许作业在内存中“搬家”。

编译，由编译程序对用户源程序进行编译，形成若干目标模块

链接，由链接程序将编译后形成的一组目标模块以及他们所需要的库函数链接在一起，形成一个完整的装入模块

装入，由装入程序将装入模块装入内存

绝对装入方式

在编译时事先知道程序将驻留在内存中的位置，则编译程序可直接将程序的符号地址转换为绝对地址，产生使用绝对地址的目标模块，进而链接成使用绝对地址的装入模块。这样装入程序就可以按照装入模块中的地址将程序和数据装入内存，而不需要对模块中的地址部分进行修改。

使用于单道程序环境

可重定位装入方式：

在多道程序的环境下，编译程序通常不直接将符号地址转为绝对地址，而是产生从0开始编址的目标模块，并由链接程序链接成一个从0开始编址的可装入模块。装入模块中的指令和数据的地址是相对于装入模块的首字节而编址的，因此被称为相对地址或逻辑地址，相对地址的集合称为相对地址空间。

将装入模块的指令和数据的相对地址调整为相应内存单元的绝对地址后程序才能正常运行，这个地址转换过程叫重定位。

如果重定位是在装入时，由重定位装入程序一次性完成，则称为静态重定位。而相应的装入方式称为可重定位装入方式。

不允许程序运行时在内存中移动位置

优点：

不需要硬件支持，可以装入有限多道程序

缺点：

一个程序通常需要占用连续的内存空间。程序装入内存后不能移动，不易实现共享

动态运行时装入方式

重定位不在装入时进行，推迟到程序真正执行时进行，这种重定位方式称为动态重定位。相应的装入方式称为动态运行时装入方式

需要硬件支持，如重定位寄存器

优点：

主存使用更加灵活有效

几个作业共享一个程序段的单个副本比较容易

有可能向用户提供一个比主存的存储空间大得多的地址空间，由系统来负责全部的存储管理

缺点：

需要附加硬件支持

实现存储器管理的软件比较复杂

链接是将编译后得到的各个目标模块以及所需要的库函数连接到一起，形成一个完整的装入模块。

链接程序必须将各个目标模块中的相对地址和外部调用符号转换成装入模块的相对地址。

静态链接方式

在程序运行之前，将各目标模块以及它们所需的库函数，链接成一个完整的装入模块，以后不在拆开的方式。

装入动态链接：

链接在装入时进行，即在装入一个目标模块时，若发生一个模块调用事件，则由装入程序找出相应的外部模块，把它装入内存，并把它链接到调用者模块上去。

优点：

便于实现目标模块的修改、更新

可对外层中的目标模块实现共享

运行时动态链接：

链接在运行时进行，即在执行过程中发现一个被调用模块尚未装入内存，立即由OS找出该模块装入内存并链接到调用者模块

优点：

便于实现目标模块的修改、共享、更新

加快程序的装入过程、提高内存利用率

为什么需要：为了能将用户程序装入内存，必须为它分配一定大小的内存空间。

连续分配方式：是指为一个用户程序分配一个连续的内存空间，即程序中代码或数据的逻辑地址相邻，体现在内存分配时物理地址的相邻。

单一连续分配：

最简单的，只适用与单用户、单任务的操作系统。

将内存分为系统区和用户区两部分，系统区仅供OS使用，通常位于内存的低端；而用户区则供用户使用，其中仅能存放一道作业

优点：管理简单、开销小

缺点：内存浪费、资源利用率低

固定分区分配：

固定分区分配在系统初启时，将内存的用户空间划分为若干个区域，这些分区的大小和边界在系统运行期间不再变化，并只允许在每个分区中装入一道作业。【支持多道程序并发设计】

固定分区划分可以分区大小相等，也可以不等

需建立固定分区说明表，指明分配的分区数以及每个分区的大小、起始地址、状态

​​​​​​​

分配过程

当有作业要装入内存时，内存分配程序检索分区说明表，找到一个尚未使用 的满足大小要求的分区分配给该作业，然后修改分区的状态；如果找不到合适的分区就拒绝为该作业分配内存。

优点：

易于实现，开销小

缺点：

内部碎片造成浪费

内部碎片：内存中已经分配给用户但未被利用的区域称为内部碎片

分区总数固定，限制了并发执行的程序数目

存储空间的利用率太低。

动态分区分配：

为了减少存储区域的内部碎片，进一步提高主存的利用率，使存储空间的划分更加适应不同的作业组合，设计了动态分区方案。

每次装入作业时，动态地为作业从可用内存中划分出一个分区，其大小刚好能满足作业的实际需要。因此内存中分区的个数和每个分区的大小随着系统中运行的作业情况而变化。

实现可变分区分配关键点：

分区分配中数据结构

空闲分区表

空闲分区链

分区分配操作：

涉及动态分区的操作有分配内存，回收内存。这些操作都是程序接口中通过系统调用发出的。

分配内存：向操作系统提出一特定存储量的请求。通常，它并不要求这个分配的存储区域限于特定的位置，但是，这个区域必须是连续的

回收内存：进程用于归还一个不再需要的存储区域。当进程运行完毕释放内存时，系统根据回收区首址，从空闲区链中找到相应的插入点。

动态分区分配算法

基于顺序搜索的动态分区分配算法

为了实现动态分区分配，通常是将系统中的空闲分区链接成一个链，所谓顺序搜索是指一次搜索空闲分区链上的空闲分区，去寻找一个其大小能满足要求的分区

首次适应算法【First Fit FF】

空白区按其在存储空间中地址递增【不是大小递增】的顺序连在一起，即每个后继空白区的起始地址总是比前者大。选择第一个满足要求的空白块。倾向优先利用存储空间中低址部分的空白区

优点：算法简单，查找速度快；留在高地址部分大的空白区划分机会少，大作业到来时容易满足

缺点： 存储空间利用率不高【用大空白区适应小作业，留下较小的无法利用的空白区】

小而无用的集中在前端，较大的在尾端，找到合适空白区的速度降低，增加查找开销

在低地址的部分会累计大量的外部碎片

循环首次适应算法【也叫下次适应算法 Next Fit NF】

把存储空间的空白区构成一个循环链。每次为存储请求查找到合适的分区时，总是从上次查找结束的地方开始，只要找到一个足够大的空白区就把他划分后分配出去。

优点:存储空间的利用更加均衡，不至于使小的空白区集中于存储器的一端。

缺点：存储器的另一端也不可能保留大的空白块，当需要获得相当大的空白区时，满足的可能性减小

最佳适应算法（Best Fit)

每次为作业分配时，总是能把满足要求的又是最小的空闲分区分配给作业。为了加速查找，要求所有的空闲分区按照容量从小到大形成空闲分区链，第一次找到的就是最佳

优点：如果存储空间中具有正好是所要求大小的存储空白区，则必然被选中；如果不存在这样的空白区，也只对比要求稍大的空白区进行划分，而绝不会去划分一个更大的空白区。因此，其后遇到大作业到来时，作业要求的存储区域就比较容易得到满足。

缺点：每次分配总是产生最小的空白区，难以利用

回收一个分区时，为了把它插入到空白区链的合适位置也很费时

最坏适应算法（Worst Fit）

为作业选择存储区域时总是寻找最大的空白区

优点：在划分后剩余的空白区也是最大的，因此对之后的分配仍然是有用的

缺点：当有大的作业时，存储空间的申请往往得不到满足

基于索引搜索的动态分区分配算法

快速适应算法（Quik FIt）

将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立了一个空闲分区链表。这样系统中就存在多个空闲分区链表

同时在内存中设立一张管理分区类型并记录该类型空闲分区链表表头的索引表

分配过程：根据进程的长度，寻找到能容纳它的最小的空闲分区链表，并取下第一块进行分配即可

优点：

查找效率高

在进行空闲分区分配时，不会对任何分区产生分割，能保留大的分区满足对大空间的需求。也不会产生内部碎片

缺点

分区归还主存算法复杂，系统开销大

算法在分配空闲分区时以进程为单位，一个分区只属于一个进程，在为一个进程分配的分区中或多或少有浪费，空闲分区划分越细，浪费越严重

伙伴系统（Buddy System)

固定分区限制了内存中作业的道数，并且由于存在内部碎片而降低了内存的利用率；动态分区分配算法复杂，回收分区时需要进行分区合并，系统开销大。

在伙伴系统中，可用内存块的大小为 2k (1≤k≤m)

21表示分配的最小块的尺寸；

2m表示分配的最大块的尺寸，通常是可供分配的整个内存空间的大小。

➢对空闲区按照大小分类，相同大小的分区链接为一个双向空闲链表；最多可形成 k（0 ≤k≤m ）个链表

哈希算法

利用哈希算法快速查找的特点，以及空闲分区在可利用空闲空间表中的分布规律建立哈希函数，构造哈希表，以分区大小为关键字

动态可重定位分区分配

紧凑：将内存中的所有作业进行移动，将原本分散的多个空闲分区移动到同一端拼接成一个大的空闲分区，以装入用户的作业。

可重定位分区分配方式就是在动态分区分配方式的基础上增加紧凑功能，即在找不到足够大的空闲分区而空闲分区的总和却能满足用户需求时进行紧凑

由于紧凑时作业在内存中移动位置，因此需要得到动态重定位技术的支持

动态重定位：地址变换过程是在程序执行期间，随着每条指令或数据的访问自动进行的

将装入模块的指令和数据的相对地址调整为相应内存单元的绝对地址后程序才能正常运行，这个地址转换过程叫重定位。

原理： 需要增设重定位寄存器，用来存放程序在内存中的起始位置。程序执行时真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的

对换：把内存中暂时不能运行的进程或暂时不用的程序和数据换出到外存上，以便腾出足够多的内存空间，再把已具备运行条件的进程或进程所需要的 程序和数据换入；

对换是改善内存利用率的有效措施，可直接提高处理机的利用率和系统吞吐量。从逻辑上扩充内存空间。

对换以整个进程为单位:整体对换或进程对换

处理机的中级调度实际上就是存储器的对换功能，其目的是用来缓解内存紧张和进一步提高内存的利用率和系统的吞吐量

这种对换广泛用于分时系统和多道程序系统

对换是以页、段为单位，称为页面对换、或分段对换、部分对换

是实现虚拟存储器的基础

为了实现进程对换，系统必须实现三方面功能

对换空间的管理

对文件区管理的主要目标是提高存储空间的利用率，然后才是提高对文件的访问速度。因此采用离散分配方式

对对换区主要目的是提高进程换入和换出的速度，然后才是提高文件存储区的利用率。因此采用连续分配方式

进程的换入

系统定时查看所有进程的状态，从中找出就绪但已换出的进程，将他们按照某种次序依次换入，直到无可换入的进程为止。

进程的换出

当有就绪进程要换入但是没有足够空间，选择换出进程，首先选择处于阻塞状态且优先级最低的进程，若找不到，则根据进程的优先级、在外存的驻留时间等因素考虑将某个进程换出

连续分配会形成许多碎片，虽然可通过紧凑方式将许多碎片拼接成可用大块空间，但是会有很大开销。如果允许将一个进程直接分散地装入到许多不相邻接的分区中，便可充分的利用内存空间，不需要再进行紧凑。基于这个思想产生了离散分配方式，根据所分配的地址空间的基本单位不同，又分为

分页存储管理：在该方式中，将用户程序的地址空间分为若干个固定的区域，称为页，也将内存空间分为若干物理块或页框

分段存储管理方式：为了满足用户要求而形成的一种存储管理方式。把用户程序的地址空间分为若干大小不同的段，每段可定义一组相对完整的信息。分配时以段为单位

段页式存储管理方式，两者相结合

离散分配的优点

没有外零头

不受连续空间的限制，每块都能分出去

仅有小于一个页面的内零头

程序大小一般不是页大小的整数倍

页：系统将一个进程的逻辑地址空间分为若干个大小相等的片

页框：将内存空间分成若干个与页面相同大小的块

为了地址映射的方便，页面大小通常为2的幂，若大小为 2k，逻辑地址的长度为n，则0到k-1为页面位移量，k到n-1为页号

页表：在进程运行时，为了能在内存中找到每个页面对应的物理块，系统为每个进程建立了一张页面映射表，称为页表。进程的每个页占页表的一个表项，其中记录了相应页对应的内存块的块号，以及用于分页保护的存取控制信息。

一个进程对应一张页表

进程的每一页对应一个页表项

每个页表项由页号和块号组成

页表记录进程页面和实际存放的内存块之间的对应关系

每一个页表项的长度相等，页号是隐含的

进程在内存中连续存放时，操作系统是如何实现逻辑地址到物理地址的转换？

使用重定位寄存器：存放装入模块的起始位置

真正访问的内存地址是重定位寄存器加相对地址形成的

进程在内存中离散存放时，操作系统是如何实现逻辑地址到物理地址的转换？

页号=逻辑地址 / 页面长度

页内偏移量 = 逻辑地址 % 页面长度

页面在内存的起始位置：操作系统需要用某种数据结构记录进程每个页面的起始位置

基本的地址变换机构

借助进程的页表将逻辑地址转换为物理地址

通常会在系统中设置一个页表寄存器（PTR），存放页表在内存中的起始地址F和页表长度M

进程未执行时，页表的始址和页表长度放在进程控制块PCB中，当进程被调度，操作系统内核会将他们放在页表寄存器中

设页面大小为L，逻辑地址A到物理地址E的变换过程如下：

①计算页号P和页内偏移量W

②判断页号P和页表长度M，若P>=M，则会产生越界中断，否则继续执行。

③页表中的页号P对应的是页表项地址 = 页表起始地址+页号P*页表项长度，取出该表象内容b，即为内存块号

④计算E=b*L + W

练习：

页内偏移量10位->页面大小210B=1KB

A/1024 = 2 ，A % 1024 = 452得到页号2，页内偏移量452

E = 1024 * 8 + 452 = 8192 + 452 = 8644

在分页存储管理的系统中，只要确定了每个页面的大小，逻辑地址结构就确定了，因此页式管理中的地址是一维的

页表存放在内存中，CPU需要两次访存，第一次访存页表，得到指令或数据所在的内存块号，第二次根据物理地址存取指令或数据。

具有快表的地址变换机构

时间局部性原理：如果执行了程序的某条指令，那么不久之后这条指令很可能被再次执行；如果某个数据被访问过，不久后该数据可能被再次访问

空间局部性原理：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也可能被访问。

在基本地址变换机构中，每次要访问一个逻辑地址都需要查询内存中的页表，由于局部性原理，可能连续很多次查到的都是同一个页表项。

快表，又称联想寄存器（TLB），是一种访问速度比内存块快很多的高速缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换的过程，对应内存中的页表称为慢表

快表命中一次访问，未命中两次访存！

EAT：从进程发出指定逻辑地址的访问请求，经过地址变换到在内存中找到对应的实际物理地址单元并取出数据，所要花费的总时间，称为内存的有效访问时间

两级页表【多级】

反置页表（IPT）

现代计算机系统中，通常允许一个进程的逻辑地址空间非常大，因此就需要由许多的页表项，因此会占用大量的内存空间。为了减少页表占用的内存，引入反置页表

一般页表的页表项是按照页号进行排序，页表项中里的内容为物理块号

而反置页表则是为每一个物理块设置一个页表项，并将它们按照物理块的编号排序

思路

不让页表与逻辑地址空间的大小对应

让页表与物理地址空间的大小相对应

反置页表地址转换过程如下:

给出进程标识和页号,用它们去比较IPT,若整个反置页表中未能找到匹配的页表项,说明该页不在主存,产生请求调页中断,请求操作系统调入;否则，该表项的序号便是物理块号,块号加上位移,便形成物理地址。

Hash反置页表

基于Hash映射值查找对应页表项中的帧号

页表项中包含保护位、修改位、访问位、和存在位等标识

用户通常喜欢将自己的作业按照逻辑关系划分为若干段，然后通过段名和段内地址来访问相应的程序或数据，同时希望以以段为单位对程序和数据进行共享和保护，并要求分段能动态增长。

分页存储虽然较好的解决了动态分区的碎片问题，却很难满足用户的上述需求，也不方便支持动态链接技术，因此引入分段式存储管理方式

分段共享

一般实现程序和数据共享时都是以信息的逻辑单位（过程、函数或文件）为基础的。

在分页系统中的每一页都只是存放信息的物理单位，其本身并无完整意义，因而不便于实现信息共享。

段是信息的逻辑单位，可以为共享过程建立一个独立的段，更便于实现程序和数据的共享。

分段保护

对内存中的信息的保护，同样也是对信息的逻辑单位进行保护。

采用分段存储管理，对实现保护，将是更有效和方便。

动态链接。

程序运行时，先将主程序所对应的目标程序装入内存并启动运行，当运行过程中又需要调用某段时，才将该段调入内存并进行链接。

动态增长

在实际使用中，往往有些段，特别是数据段会随着程序的运行不断增大，而这种增长事先并不知晓会增长到多大，采用其它存储管理方式是难以应付的，而分段存储管理却能较好的解决这一问题

与分页最大的区别就是，离散分配时地址空间的基本单位不同

进程中的地址空间：按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名，每段从0开始编址

内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但每段之间可以不相邻

和页式结构类似，分段系统的逻辑机制由段号、段内地址组成

分段系统的作业地址空间是二维的。

为了实现二维地址空间中的逻辑地址到内存空间中的物理地址的转换，系统为每个进程建立了一张段映射表，简称段表。

进程的每个段在段表中占一个表项，其中记录了该段在内存中的起始地址和段的长度以及对分段进行保护的存取控制信息

为了既能像分页系统那样有效的利用内存，又能像分段系统那样满足用户多方面的需要，引入段页式存储管理方式

根据逻辑地址得到段号、页号、页内偏移

根据段号查询，与段表长度比较看是否越界

第一次访存：得到页表长度和存放块号

页号和页表长度比较看是否越界

第二次访存：根据页表存放块号，页号查询页表项，得到内存块号。

内存块号+偏移量得到最终的物理地址

第三次访存：访问目标内存单元

每取一条指令或一个 数据都需要三次访问内存，可在地址变换机构中增设快表，用来存放当前被频繁访问的页面所对应的段号、段内地址和物理块号信息，以减少访问内存的次数，提高指令执行的速度。

分页系统实现程序段的共享较为困难。

分段易于实现段的共享和段的保护。

可重入代码（Reentrant Code, 纯代码）

是一种允许多个进程同时访问的代码（可共享），且是一种不允许任何进程对其进行修改的代码。

分段的共享是通过两个作业段表的相应表目都指向同一物理副本来实现的。

“驻留性”: 作业装入后一直驻留内存直到作业完成。

传统存储方式：

连续分配

非连续分配

页、段、段页

共同特征：

一次性：作业在运行前必须一次性的全部装入内存后方可开始运行。

驻留性：作业装入内存后，便一直驻留在内存内，直至作业运行结束。

一次性和驻留性，使许多在程序运行中不用或暂时不用的程序或数据占据大量的内存空间，使得一些需要运行的作业无法装入运行；而且若一个程序所要求的内存空间超过了内存实际容量，则该程序必定无法装入内存运行。

局部性原理

时间局部性原理：如果执行了程序的某条指令，那么不久之后这条指令很可能被再次执行；如果某个数据被访问过，不久后该数据可能被再次访问。【循环】

空间局部性原理：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也可能被访问。【顺序访问】

基于局部性原理，应用程序在运行之前并不必全部装入内存，仅需将当前要运行的那部分程序和数据装入内存便可启动程序的运行，其余部分仍驻留外存；

当要执行的指令或数据不在内存时，再由OS自动通过请求调入功能将它们调入内存，以使程序能继续运行；

若内存空间不足，可以通过置换功能将暂时不用的程序或数据移到磁盘上，腾出足够的内存空间后，再将要访问的程序或数据调入内存。

这样可以使一个大的用户程序能在较小的内存空间中运行，也可在内存中同时装入更多的进程使它们并发执行。

从用户的角度看，该系统具有的内存容量比实际的内存容量大得多。

虚拟存储器：具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的存储器系统

虚拟内存的最大容量是计算机地址结构确定的

实际容量 = min（内存和外存容量之和，CPU寻址范围）

多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存

对换性：在作业运行时无需一直常驻内存，而是运行在作业运行过程中将作业换入换出

虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量远大于实际的容量。

虚拟性是以多次性和对换性为基础的，或者说仅当系统允许将作业分多次调入内存，并能将内存中暂时不运行的程序和数据换至盘上时，才可能实现虚拟存储器

而多次性和对唤性显然必须建立在离散分配的基础上

虚拟内存的实现必须建立在离散分配的内存管理方式基础上

包括

请求分页存储管理

请求分段存储管理

请求段页式存储管理

和传统的非连续分配存储管理的区别：

在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序【请求调页/段功能】

若内存空间不够，由操作系统将内存中暂时用不到的信息换出外存【页面置换/段置换功能】

在实现过程中，虚拟存储器必须得到一定的硬件支持，如：系统必须具有一定容量的内存和较大容量的外存，必须提供请求分页（段）的页（段）表机制，以及缺页（段）中断机构和地址变换机构；还需要得到实现请求调页（段）软件以及实现页（段）置换的软件支持。

请求分页管理和基本分页存储管理的区别

在程序执行过程中，当所访问的信息不在内存中时，由操作系统负责将所需信息从外存调入内存【增加请求调页功能】

若内存空间不够，由操作系统负责将内存中暂时不用的信息换出到外存【页面置换功能】

页表机制

页表新增字段

当进程需要访问某条指令或某个数据时，硬件地址变换机构将根据逻辑地址中的页号去检索内存中的页表，并根据相应页表项的存在位P来判断指令数据所在的页是否已装入内存

若已调入内存，则可立即从页表项中获取内存块号和页内地址拼接形成指令或数据的物理地址【和基本分页一样】，同时修改页表项中的访问位，对于修改操作还需要对修改位置一

若未调入内存，则产生缺页中断，上述访问缺页的作业将被打断，控制将转向缺页中断处理程序。

缺页中断机构

缺页中断处理程序用来完成页面的调入工作。

若系统中仍有空闲的内存块，只需根据页表项中的外存地址将所确的页装入内存，然后修改页表项中的存在位和内存块号即可

若系统中没有空闲的内存块，需要根据置换算法淘汰内存中的某一页，对已被修改过的淘汰页还需要先将其写入磁盘，再将所缺页调入

缺页中断和普通中断的区别

作为中断，同样需要经历诸如保护CPU环境、分析中断原因、转入缺页中断处理程序进行处理以及恢复CPU环境等几个步骤

但缺页中断又是一种特殊的中断，表现为两个方面

在指令执行期间产生和处理中断信号。通常CPU都是在一条指令执行完后，才检查是否有中断请求到达。若有，便去响应，否则继续执行。然而缺页中断是在指令执行期间，若发现所要访问的指令或数据不在内存时，便立即产生和处理缺页中断信号，以便及时的将所缺页面调入

一条指令在执行期间可能产生多次缺页中断

地址变换机构

请求分页系统中的地址变换机构，是在分页系统地址变换机构的基础上，为了实现虚拟存储器而增加了某些功能而形成的

如产生和处理缺页中断，从内存中换出一页的功能等

请求分页新增步骤

请求调页（查到页表项时进行判断）

页面置换（需要调入页面，但没有空闲内存块时进行）

需要修改请求页表中新增的表项

在为进程分配物理块时涉及三个问题

最小物理块数的确定

最小物理块数：是指能保证进程正常运行所需的最少物理块数。若系统为某进程所分配的物理块数少于此值时，进程将无法运行

物理块的分配策略

两种分配策略：固定分配、可变分配

两种置换策略：全局置换、局部置换

固定分配局部置换

可变分配全局置换

可变分配局部置换

物理块的分配算法

在采用固定分配策略时，可以采取下述方法将系统中可供分配的所有物理块分配给各个进程

平均分配算法

按比例分配算法

考虑优先权的分配算法

需要解决的问题

系统在何时将一个页面装入内存

预调页：一种以预测为基础的预调页策略，将预计在不久后会被访问的 页面，预先调入内存

请求调页：仅当进程执行过程中，通过检查页表发现响应页面不在内存时，才装入该页面

从何处调入页面

在请求分页系统中的外存分为两部分：

用于存放文件的文件区

用于存放对换页面的对换区

通常对换区使用连续分配方式，而文件区使用离散分配方式，故对换器的磁盘IO速度更快

这样每次发生缺页请求时，从何处调入内存有三种情况

页面调入过程

缺页率

➢ 解决：需要调入页面时，选择内存中哪个或哪些物理页面被置换。

➢ 目标：把未来不再使用的或在以后一段时间内较少使用的页面调出。（通常只能在局部性原理指导下依据过去的统计数据进行预测；相反会有“抖动”）

页面的换入、换出需要磁盘的IO，会有较大的开销，因此好的页面置换算法应该追求更少的缺页率。

最佳置换算法（OPT）

每次淘汰的页面是最长时间内不被访问的页面

最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能直到接下来会访问到是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的

先进先出置换算法（FIFO）

每次淘汰的页面是最早进入内存的页面

FIFO算法会产生Belady异常：当为进程分配的物理块数增大时，缺页次数不减反增的异常。算法实现简单，但是与进程实际运行规律不适应，算法性能差

最近最久未使用置换算法（LRU）

每次淘汰的页面是最近最久未使用的页面

LRU算法赋予每个页面一个访问字段，用来记录响应页面自上次被访问以来所经历的时间t，当淘汰一个页面时，应选择所有页面中t值最大的进行淘汰。

LRU算法的实现需要专门的硬件支持，虽然算法性能好，但是实现困难，开销大。实际应用中，采用LRU的近似算法。

需要以下两类硬件的支持：

寄存器：用于记录某进程在内存中各页的使用情况

进程访问物理块时将最高位置一，之后隔一段时间右移一位，最小数值的寄存器所对应的页面就是最近最久未使用的页面

栈：用于保存当前进程使用的各个页面的页面号

当进程访问某页面时，便将该页面号从栈中移出，也如栈顶。这样栈底就是最近最久未使用页面的页面号。

时钟置换算法（CLOCK）

时钟置换算法【CLOCK又被称为最近未用算法NRU】

最多两轮

改进型的时钟置换算法

优先淘汰没有修改的页面，减少IO操作

最多四轮

最少使用LFU置换算法

选择当前时间为止被访问次数最少的页面置换。

实际采取方法

为页面设置移位寄存器。

与LRU的区别：R1=10000000

R2=01110100

LRU----------淘汰R2

LFU----------淘汰R1

缺页率对有效访问时间的影响

有效访问时间是指访问存储器所需时间的平均值

抖动：如果运行进程的大部分时间都用于页面的换入换出，而几乎不能完成任何有效的工作，则称此时进程处于抖动状态，又称颠簸

产生抖动的原因

给进程分配的物理块过少

置换算法选择不当

全局置换使抖动传播

驻留集：请求分页存储管理中给进程分配的内存块的集合

工作集：在某段时间间隔内，进程实际访问页面的集合

驻留集不能小于工作集大小，否则进程运行过程中将频繁换页

越界检查

存取控制检查

环保护机构