第四章：存储器管理

🌈个人主页：小新_-

🎈个人座右铭：“成功者不是从不失败的人，而是从不放弃的人！”🎈

🎁欢迎各位→点赞👍 + 收藏⭐️ + 留言📝

🏆所属专栏：操作系统 欢迎订阅，持续更新中~~~

✨让小新带着你快乐的学习吧~✨

一、内存的基础知识

（一）什么是内存，有何作用

1、存储单元、内存地址的概念和联系

2、按字节编制vs按字编制

（二）进程运行的基本原理

1、装入的三种方式

2、链接的三种方式

二、内存管理的概念

（一）内存空间的分配与回收

（二）内存空间的扩充

（三）地址转换

（四）存储保护

三、内存空间的扩充

（一）覆盖技术

（二）交换技术

四、分配管理方式

（一）连续分配管理方式

1、连续单一分配

2、固定分区分配

3、动态分区分配

（二）非连续分配管理方式

1、基于分页存储管理

2、基于分段存储管理

3、段页式存储管理

（三）知识补充

1、关于碎片

2、动态分区分配算法

3、具有快表的地址变换机构

五、虚拟存储器

（一）虚拟存储器概述

1、常规存储管理方式的弊端

（1）常规存储器管理方式的特征

（2）局部性原理

（3）虚拟存储器的基本工作情况

2、虚拟存储器的定义和特征

1）定义

2）特征

3、虚拟存储器的实现方法

1）分页请求系统

2）请求分段系统

（二）请求分页管理方式

1、请求分页中的硬件支持（页表机制）

2、缺页中断机构

3、地址变换机构

（三）页面置换算法

（四）页面分配策略、抖动与工作集

1、驻留集

2、页面分配、置换算法

3、调入页面时机

4、从何处调入

5、抖动

6、工作集

一、内存的基础知识

（一）什么是内存，有何作用

1、存储单元、内存地址的概念和联系

内存可存放数据。程序执行前需要先放到内存中才能被CPU处理--缓和CPU与硬盘之间的速度矛盾

【补充】几个常用的数量单位

【指令的工作原理】

2、按字节编制vs按字编制

（二）进程运行的基本原理

1、装入的三种方式

1）绝对装入

2)可重定位装入

3）动态运行装入

2、链接的三种方式

我们在写代码时，会经过编译然后链接成可执行文件，而链接有三种方式

1）静态链接

2）装入时动态链接

3）运行时动态链接

二、内存管理的概念

操作系统作为系统资源的管理者，当然也需要对内存进行管理，要管些什么呢?

（一）内存空间的分配与回收

操作系统负责内存空间的分配与回收

（二）内存空间的扩充

操作系统需要提供某种技术从逻辑上对内存空间进行扩充

游戏 GTA的大小超过 60GB，按理来说这个游戏程序运行之前需要把60GB数据全部放入内存。然而，实际我的电脑内存才4GB，但为什么这个游戏可以顺利运行呢?--虚拟技术(操作系统的虚拟性)

（三）地址转换

操作系统需要提供地址转换功能，负责程序的逻辑地址与物理地址的转换

为了使编程更方便，程序员写程序时应该只需要关注指令、数据的逻辑地址。而逻辑地址到物理地址的转换(这个过程称为地址重定位)应该由操作系统负责，这样就保证了程序员写程序时不需要关注物理内存的实际情况。

（四）存储保护

操作系统需要提供内存保护功能。保证各进程在各自存储空间内运行，互不干扰

【总结】

三、内存空间的扩充

（一）覆盖技术

早期的计算机内存很小，比如 IBM 推出的第一台PC机最大只支持 1MB 大小的内存。因此经常会出现内存大小不够的情况。

后来人们引入了覆盖技术，用来解决“程序大小超过物理内存总和”的问题

我们来看一个列子

必须由程序员声明覆盖结构，操作系统完成自动覆盖。缺点:对用户不透明，增加了用户编程负担。

覆盖技术只用于早期的操作系统中，现在已成为历史

（二）交换技术

交换(对换)技术的设计思想:内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存(进程在内存与磁盘间动态调度)

中级调度(内存调度)，就是要决定将哪个处于挂起状态的进程重新调入内存。

我们需要思考三个问题

1.应该在外存(磁盘)的什么位置保存被换出的进程?

2.什么时候应该交换?

交换通常在许多进程运行且内存吃紧时进行，而系统负荷降低就暂停。例如:在发现许多进程运行时经常发生缺页，就说明内存紧张，此时可以换出一些进程:如果缺页率明显下降，就可以暂停换出。

3.应该换出哪些进程?

可优先换出阻塞进程;可换出优先级低的进程;为了防止优先级低的进程在被调入内存后很快又被换出，有的系统还会考虑进程在内存的驻留时间.(注意:PCB 会常驻内存，不会被换出外存)

【总结】

（三）虚拟存储技术

这一小节的内容比较多，所以在本章的第五节给出详细介绍，这里是为了逻辑的完整性给出标题

四、分配管理方式

（一）连续分配管理方式

1、连续单一分配

在单一连续分配方式中，内存被分为系统区和用户区。

系统区通常位于内存的低地址部分，用于存放操作系统相关数据;

用户区用于存放用户进程相关数据。内存中只能有一道用户程序，用户程序独占整个用户区空间。

优点:实现简单:无外部碎片:可以采用覆盖技术扩充内存;不一定需要采取内存保护(eg:早期的PC操作系统 MS-DOS)。
缺点:只能用于单用户、单任务的操作系统中;有内部碎片（分配给某进程的内存区域中，如果有些部分没有用上，就是“内部碎片’）;存储器利用率极低。

2、固定分区分配

20世纪60年代出现了支持多道程序的系统，为了能在内存中装入多道程序，且这些程序之间又不会相互干扰，于是将整个用户空间划分为若于个固定大小的分区，在每个分区中只装入一道作业，这样就形成了最早的、最简单的一种可运行多道程序的内存管理方式。

固定分区管理方式又分为俩种方式：大小相等和不等，如图所示。

为了便于分配，操作系统需要建立一个数据结构--分区说明表，通常按分区大小排队，各表项包括每个分区的起始地址、大小及状态（是否已分配）如图所示

当某用户程序要装入内存时，由操作系统内核程序根据用户程序大小检索该表，从中找到一个能满足大小的、未分配的分区，将之分配给该程序，然后修改状态为“已分配”
优点:实现简单，无外部碎片。

缺点:a.当用户程序太大时，可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决，但这又会降低性能；b.会产生内部碎片，内存利用率低。

3、动态分区分配

动态分区分配又称为可变分区分配。这种分配方式不会预先划分内存分区，而是在进程装入内存时根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的。(eg:假设某计算机内存大小为64MB，系统区8MB，用户区共56MB..)

1.系统要用什么样的数据结构记录内存的使用情况?

2.当很多个空闲分区都能满足需求时:应该选择哪个分区进行分配?

把一个新作业装入内存时，须按照一定的动态分区分配算法，从空闲分区表(或空闲分区链)中选出一个分区分配给该作业。由于分配算法算法对系统性能有很大的影响，因此人们对它进行了广泛的研究。

这里会有四种动态分区分配算法，详情请看下一回分解。
3.如何进行分区的分配与回收操作?（假设采用的是“空闲分区表”）

当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链（表）中找到相应的插入点，此时可能出现以下四种情况之一：
(1) 回收区与插入点的前一个空闲分区 Fi相邻接，见图-4-9(a)。此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区 Fi的大小。

(2) 回收分区与插入点的后一空闲分区F2相邻接，见图 4-9(b)。此时也可将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。

（3）回收区同时与插入点的前、后两个分区邻接，见图4.9(c)。此时将三个分区合并，他用日的表项和F,的首址，取消F2的表项，大小为三者之和。

(4) 回收区既不与F邻接，又不与,邻接。这时应为回收区单独建立一个新表项填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。图410示出了内存回收时的流程。

（二）非连续分配管理方式

1、基于分页存储管理

1、什么是分页

2、页表

2、基于分段存储管理

1、分段

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

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

2、段表

问题:程序分多个段，各段离散地装入内存，为了保证程序能正常运行，就必须能从物理内存中找到各个逻辑段的存放位置。为此，需为每个进程建立一张段映射表，简称“段表”

1、每个段对应一个段表项，其中记录了该段在内存中的起始位置(又称J“基址”)和段的长度。

2、各个段表项的长度是相同的。例如:某系统按字节寻址，采用分段存2储管理，逻辑地址结构为(段号16位,段内地址16位)，因此用16位即可表示最大段长。物理内存大小为4GB(可用32位表示整个物理内存地址空间)。因此，可以让每个段表项占16+32=48位，即6B。由于段表项长度相同，因此段号可以是隐含的，不占存储空间。若段表存放的起始地址为M，则K号段对应的段表项存放的地址为M+K*6

3、地址变换机构

4、分页和分段的主要区别

1）页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。

段是信息的逻辑单位。分页的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。

2）页的大小固定且由系统决定。段的长度却不固定，决定于用户编写的程序。

3）分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址。分段的用户进程地址空间是二维的，程序员在标识一个地时，既要给出段名，也要给出段内地址。
4）分段比分页更容易实现信息的共享和保护。不能被修改的代码称为纯代码或可重入代码(不属于临界资源)，这样的代码是可以共享的。可修改的代码是不能共享的
访问一个逻辑地址需要几次访存?分页(单级页表):第一次访存--查内存中的页表，第二次访存--访问目标内存单元。总共两次访存分段:第一次访存--查内存中的段表，第二次访存--访问目标内存单元。总共两次访存与分页系统类似，分段系统中也可以引入快表机构，将近期访问过的段表项放到快表中，这样可以少一次访问，加快地址变换速度。

【总结】

3、段页式存储管理

1、分页、分段管理方式中最大的优缺点

分页系统以页面作为内存分配的基术单位，能有效地提高内存利用率，而分段系统以段作为内存分配的基本单位，它能够更好地满足用户多方面的需要。如果能对两种存储管理方式“各取所长”，则可形成一种新的存储器管理方式——段页式存储管理方式。这种新的系统既具有分段系统的便于实现、分段可共享、易于保护、可动态链接等一系列优点，又能像分页系统那样，很好地解决内存的外部碎片问题。

2、分段+分页——段页式管理方式

段页式系统的基本原理是分段和分页原理的结合，即先将用户程序分成若千个段，再把每个段分成若于个页，并为每一个段赋予一个段名。图4-23(a)示出了一个作业地址空间的结构。该作业有三个段：主程序段、子程序段和数据段；页面大小为4KB。在段页式系统中，其地址结构由段号、段内页号及页内地址三部分所组成，如图4-23(b)所示。
在段页式系统中，为了实现从逻辑地址到物理地址的变换，系统中需要同时配置段表和页表。段表的内容与分段系统略有不同，它不再是内存始址和段长，而是页表始址和页表长度。图4-24示出了利用段表和页表进行从用户地址空间到物理（内存）空间的映射。

3、如何实现地址转换

在段页式系统中，为了便于实现地址变换，须配置一个段表寄存器，其中存放段表始址和段长TL。进行地址变换时，首先利用段号S，将它与段长TL进行比较。若S<TL，表示未越界，于是利用段表始址和段号来求出该段所对应的段表项在段表中的位置，从中得到该段的页表始址，并利用逻辑地址中的段内页号P来获得对应页的页表项位置，从中读出该页所在的物理块号b，再利用块号b和页内地址来构成物理地址。图4-25示出了段页式系统中的地址变换机构。
在段页式系统中，为了获得一条指令或数据，须三次访问内存。第一次访问是访问内存中的段表，从中取得页表始址；第二次访问是访问内存中的页表，从中取出该页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理地址；第三次访问才是真正从第二次访问所得的地址中取出指令或数据。
显然，这使访问内存的次数增加了近两倍。为了提高执行速度，在地址变换机构中增设一个高速缓冲寄存器。每次访问它时，都须同时利用段号和页号去检索高速缓存，若找到匹配的表项，便可从中得出相应页的物理块号，用于与页内地址一起形成物理地址；若未找到匹配表项，则仍需第三次访问内存。由于他的基本原理与分页机分段的情况类似，这里不再赘述。

【总结】

（三）知识补充

1、关于碎片

2、动态分区分配算法

1. 首次适应算法（First - Fit）

- 工作方式：当需要为一个进程分配内存时，从空闲分区链（表）的头部开始顺序查找，找到第一个大小能满足该进程需求的空闲分区，然后将此分区分配给进程。如果该空闲分区大小大于进程所需大小，就将其分割，一部分分配给进程，剩余部分仍作为空闲分区留在空闲分区链（表）中。
- 优点：实现简单，分配速度相对较快。倾向于优先利用内存低地址部分，使得高地址部分可能保留较大的空闲分区，对于较大内存需求的进程比较有利。
- 缺点：低地址部分容易产生外部碎片，因为经过多次分配后，低地址区域会有许多小的空闲分区，这些碎片难以利用。而且，由于总是从低地址开始查找，会使低地址部分频繁被分割，造成内存使用不均衡。

2. 循环首次适应算法（Next - Fit）

- 工作方式：该算法是对首次适应算法的改进。在为进程分配内存时，从上次分配结束的空闲分区的下一个分区开始顺序查找，找到第一个合适的空闲分区就进行分配。这样，每次分配都是从上次分配结束的位置开始循环查找空闲分区链（表）。
- 优点：相对首次适应算法，它能使内存空间的利用更加均衡，减少了低地址部分碎片堆积的现象，各个区域的空闲分区都有更多机会被分配。
- 缺点：依然会产生碎片，而且由于其循环查找的特性，可能会把一些大分区分割成小碎片。另外，在某些情况下，可能会出现分割大分区后，后续需要大分区的进程找不到合适分区的情况。

3. 最佳适应算法（Best - Fit）

- 工作方式：在空闲分区链（表）中查找大小与进程所需内存大小最接近的空闲分区进行分配。这个算法的目的是尽量减少内存浪费，使得分配后剩余的空闲分区尽可能小。
- 优点：能够最大程度地减少浪费的空间，剩余的空闲分区相对其他算法而言在大小上更合理，有利于后续小内存需求的分配。
- 缺点：为了找到最合适的空闲分区，需要遍历整个空闲分区链（表），比较每个分区的大小，这会花费较多时间，导致查找效率较低。而且，容易产生许多难以利用的小碎片。

4. 最坏适应算法（Worst - Fit）

- 工作方式：每次都从空闲分区链（表）中选择最大的空闲分区来分配给请求内存的进程。这样做的目的是希望分配后剩余的空闲分区比较大，便于后续的利用。
- 优点：减少了产生小碎片的可能性，因为优先使用大分区，剩余的空闲分区相对较大，容易被后续进程利用。
- 缺点：会导致大的空闲分区很快被分割成小分区，当后续有大进程需要大分区时，可能找不到合适的空闲分区，需要进行内存紧凑等操作来腾出足够的空间。并且，可能会过度分割大分区，造成一定程度的空间浪费。

3、具有快表的地址变换机构

1、什么是快表

快表又称之为联想寄存器（TLB），是一种访问速度比内存块很多的高速缓存（TLB不是内存），用来存放最近访问的页表项的副本，可以加速地址变换的速度。与此对应，内存中的页表常称为慢表。

2、能否把整个页表都放在TLB中？

TLB是一种高速缓存，制作大容量的TLB成本很高。一方面，大容量的高速缓存芯片本身的生产成本高，因为需要更多的晶体管和更复杂的制造工艺来实现较大的存储容量；另一方面，大容量TLB会使CPU芯片面积增大，这不仅增加了芯片制造的成本，还可能会降低CPU的频率，影响整体性能。所以从成本效益的角度考虑，通常不会将整个页表放入TLB中。

3、快表的作用

4、局部性原理

4、俩级页表

五、虚拟存储器

虚拟存储器作为现代操作系统中存储器管理的一项重要技术，实现了内存扩充功能。但该功能并非是从物理上实际地扩大内存的容量，而是从逻辑上实现对内存容量的扩充，让用户所感觉到的内存容量比实际内存容量大得多。于是便可以让比内存空间更大的程序运行，或者让更多的用户程序并发运行。这样既满足了用户的需要，又改善了系统的性能。本章将对虚拟存储的有关概念和技术做较详细的阐述

（一）虚拟存储器概述

前面所介绍的各种存储器管理方式有一个共同的特点，即它们都要求将一个作业全部装入内存后方能运行。于是，出现了下面这样两种情况:
(1)有的作业很大，其所要求的内存空间超过了内存总容量，作业不能全部被装入内存，致使该作业无法运行;
(2)有大量作业要求运行，但由于内存容量不足以容纳所有这些作业，只能将少数作业装入内存让它们先运行，而将其它大量的作业留在外存上等待。
出现上述两种情况的原因都是由于内存容量不够大。一个显而易见的解决方法是从物理上增加内存容量，但这往往会受到机器自身的限制，而且无疑要增加系统成本，因此这种方法是受到一定限制的。另一种方法是从逻辑上扩充内存容量，这正是虚拟存储技术所要解决的主要问题。

1、常规存储管理方式的弊端

（1）常规存储器管理方式的特征

我们把前一章中所介绍的各种存储器管理方式统称为传统存储器管理方式，它们全都具有如下两个共同的特征:
(1)一次性，是指作业必须一次性地全部装入内存后方能开始运行。在传统存储器管理方式中，无一例外地要求先将作业全部装入内存后方能运行。正是这一特征导致了大作业无法在小内存中运行，以及无法进一步提高系统的多道程序度，直接限制了对处理机的利用率和系统的吞吐量的提高。事实上，许多作业在运行时，并非需要用到全部程序和数据，如果一次性地装入其全部程序和数据，显然也是对内存空间的一种浪费。(2)驻留性，是指作业被装入内存后，整个作业都一直驻留在内存中，其中任何部分都不会被换出，直至作业运行结束。尽管运行中的进程会因IO等原因而被阻塞，可能处于长期等待状态，或者有的程序模块在运行过一次后就不再需要(运行)了，它们都仍将驻留在内存中，继续占用宝贵的内存资源。
由此可以看出，上述的一次性及驻留性特征使得许多在程序运行中不用或暂时不用的程序(数据)占据了大量的内存空间，而一些需要运行的作业又无法装入运行，显然，这是在浪费宝贵的内存资源。现在要研究的问题是:一次性及驻留性特征是否是程序在运行时所必需的和不可改变的。

（2）局部性原理

程序运行时存在的局部性现象，很早就已被人发现，但直到1968年，PDenning才真正指出:程序在执行时将呈现出局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分，相应地，它所访问的存储空间也局限于某个区域。他提出了下述几个论点:

(1)程序执行时，除了少部分的转移和过程调用指令外，在大多数情况下是顺序执行的。该论点也在后来许多学者对高级程序设计语言(如FORTRAN语言、PASCAL语言及C语言)规律的研究中被证实。
(2)过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域。但经研究看出过程调用的深度在大多数情况下都不超过5。这就是说，程序将会在一段时间内，都局限在这些过程的范围内运行。

(3)程序中存在许多循环结构，这些结构虽然只由少数指令构成，但是它们将被多次执行。
(4)程序中还包括许多对数据结构的处理，如对数组进行操作，这些处理往往都局限于很小的范围内。

局限性又表现在下述两个方面:

(1)时间局限性。如果程序中的某条指令被执行，则不久以后该指令可能再次执行:如果某数据被访问过，则不久以后该数据可能再次被访问。产生时间局限性的典型原因是在程序中存在着大量的循环操作。
(2)空间局限性。一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址可能集中在一定的范围之内，其典型情况便是程序的顺序执行。

（3）虚拟存储器的基本工作情况

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

2、虚拟存储器的定义和特征

1）定义

当用户看到自己的程序能在系统中正常运行时，他会认为，该系统所具有的内存容量定比自己的程序大，或者说，用户所感觉到的内存容量会比实际内存容量大得多。但用户所看到的大容量只是一种错觉，是虚的，故人们把这样的存储器称为虚拟存储器。综上所述，所谓虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。可见，虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于大、中、小型机器和微型机中。

2）特征

与传统的存储器管理方式比较，虚拟存储器具有以下三个重要特征:

(1)多次性。多次性是相对于传统存储器管理方式的一次性而言的，是指一个作业中的程序和数据无需在作业运行时一次性地全部装入内存，而是允许被分成多次调入内存运行，即只需将当前要运行的那部分程序和数据装入内存即可开始运行。以后每当要运行到尚未调入的那部分程序时，再将它调入。正是由于虚拟存储器的多次性特征，才使它具有从逻辑上扩大内存的功能。无疑，多次性是虚拟存储器最重要的特征，它是任何其它的存储管理方式所不具有的。因此，我们也可以认为虚拟存储器是具有多次性特征的存储器管理系统。

(2)对换性。对换性是相对于传统存储器管理方式的常驻性而言，是指一个作业中的程序和数据，无须在作业运行时一直常驻内存，而是允许在作业的运行过程中进行换进、换出，亦即，在进程运行期间，允许将那些暂不使用的代码和数据从内存调至外存的对换区(换出)，待以后需要时再将它们从外存调至内存(换进)。甚至还允许将暂时不运行的进程调至外存，待它们重又具备运行条件时再调入内存。换进和换出能有效地提高内存利用率可见，虚拟存储器具有对换性特征，也正是由于这一特征，才使得虚拟存储器得以正常运行。试想，如果虚拟存储器不具有换出功能，即不能把那些在存储器中暂时不运行的进程或页面(段)换至外存，不仅不能充分地利用内存，而且还会使在换入时，因无足够的内存空间，而经常以失败告终。
(3)虚拟性。虚拟性是指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。这样，就可以在小的内存中运行大的作业，或者能提高多道程序度。它不仅能有效地改善内存的利用率，还可提高程序执行的并发程度，从而可以增加系统的石吐量。这是虚拟存储器所表现出来的最重要的特征，也是实现虚拟存储器的最重要的目标正是由于它具有这一特征，才使得虚拟存储器目前已成为在大、中、小及微机上最广泛采用的存储器管理方式。
值得说明的是，虚拟性是以多次性和对换性为基础的，或者说，仅当系统允许将作业分多次调入内存，并能将内存中暂时不运行的程序和数据换至盘上时，才有可能实现虚拟存储器；而多次性和对换性显然必须建立在离散分配的基础上。

3、虚拟存储器的实现方法

在虚拟存储器中，允许将一个作业分多次调入内存。如果采用连续分配方式时，要求必须将作业装入一个连续的内存区域中，则必须事先为作业一次性地申请一个足以容纳整个作业的内存空间，以便能将该作业分先后地多次装入内存。这不仅会使相当一部分内存空间都处于暂时或“永久”的空闲状态，造成内存资源的严重浪费，而且无法、也无意义再从逻辑上扩大内存容量。所以，虚拟存储器的实现，都毫无例外地建立在离散分配存储管理方式的基础上。目前，所有的虚拟存储器都是采用下述方式之一实现的。

1）分页请求系统

分页请求系统是在分页系统的基础上增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。它允许用户程序只装入少数页面的程序(及数据)即可启动运行。以后，再通过调页功能及页面置换功能陆续地把即将运行的页面调入内存，同时把暂不运行的页面换出到外存上。置换时以页面为单位。为了能实现请求调页和页面置换功能，系统必须提供必要的硬件支持和实现请求分页的软件。
1)硬件支持
主要的硬件支持有:
(1)请求分页的页表机制。它是在纯分页的页表机制上增加若干项而形成的，作为请求分页的数据结构。
(2)缺页中断机构。每当用户程序要访问的页面尚未调入内存时，便产生一缺页中断以请求 OS 将所缺的页调入内存。
(3)地址变换机构。它同样是在纯分页地址变换机构的基础上发展形成的。2)实现请求分页的软件
这里包括有用于实现请求调页的软件和实现页面置换的软件。它们在硬件的支持下，将程序正在运行时所需的页面(尚未在内存中的)调入内存，再将内存中暂时不用的页面从内存置换到磁盘上。

2）请求分段系统

请求分段系统是在分段系统的基础上，增加了请求调段及分段置换功能后所形成的段式虚拟存储系统。它允许用户程序只要装入少数段(而非所有的段)的程序和数据即可启动运行。以后通过调段功能和段的置换功能将暂不运行的段调出，再调入即将运行的段。置换是以段为单位进行的。为了实现请求分段，系统同样需要必要的硬件和软件支持。

1)硬件支持
主要的硬件支持有:
(1)诸求分段的段表机制。它是在纯分段的段表机制上增加若干项而形成的，作为请求分段的数据结构。
(2)缺页中断机构。每当用户程序要访问的段尚未调入内存时，使产生一缺段中断，以请求 OS 将所缺的段调入内存。
(3)地址变换机构。它同样是在纯分段地址变换机构的基础上发展形成的。
2)软件支持
这里包括有用于实现请求调段的软件和实现段置换的软件。它们在硬件的支持下，先将内存中暂时不用的段从内存置换到磁盘上，再将程序正在运行时所需的段(尚未在内存中的)调入内存。虚拟存储器在实现上是具有一定难度的。相对于请求分段系统，因为请求分页系统换进和换出的基本单位都是固定大小的页面，所以在实现上要容易些。而请求分段系统换进换出的基本单位是段，其长度是可变的，分段的分配类似于动态分区方式，它在内存分配和回收上都比较复杂。

目前，有不少虚拟存储器是建立在段页式系统基础上的，通过增加请求调页和页面置换功能形成了段页式虚拟存储器系统，而且把实现虚拟存储器所需支持的硬件集成在处理器芯片上。例如，早在20世纪80年代中期，Intel80386处理器芯片便已具备了支持段页式虚拟存储器的功能，以后推出的80486、80586以及P2、P3、P4等芯片中，都无一例外地具有支持段页式虚拟存储器的功能。

（二）请求分页管理方式

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

1、请求分页中的硬件支持（页表机制）

为了实现请求分页，系统必须提供一定的硬件支持。计算机系统除了要求一定容量的内存和外存外，还需要有请求页表机制、缺页中断机构以及地址变换机构。
1.请求页表机制
在请求分页系统中需要的主要数据结构是请求页表，其基本作用仍然是将用户地址空间中的逻辑地址映射为内存空间中的物理地址。为了满足页面换进换出的需要，在请求页表中又增加了四个字段。这样，在请求分页系统中的每个页表应含以下诸项:

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

2、缺页中断机构

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

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

（3）

3、地址变换机构

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

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