(三)内存管理[os]

3.1.基础知识

内存是用于存放数据的硬件。程序执行前需要先放到内存中才能被CPU处理。

相对地址和绝对地址

编译时产生的指令只关心“相对地址”，实际放入内存中时再想办法根据起始位置得到“绝对地址”。
Eg: 编译时只需确定变量x存放的相对地址是100（也就是说相对于进程在内存中的起始地址而言的地址）。CPU 想要找到x在内存中的实际存放位置，只需要用进程的起始地址+100即可。

相对地址又称逻辑地址，绝对地址又称物理地址。

写程序到程序运行

3.2.内存管理

操作系统对内存进行管理，那么要管理哪些内容呢？

内存空间的分配和回收
操作系统需要提供某种技术从逻辑上对内存空间进行扩充。
操作系统需要提供地址转换功能，负责程序的逻辑地址与物理地址的转换

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

内存保护可采取两种方法:

方法一:在CPU中设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令要访问某个地址时，CPU检查是否越界。

方法二:采用重定位寄存器（又称基址寄存器）和界地址寄存器（又称限长寄存器）进行越界检查。重定位寄存器中存放的是进程的起始物理地址。界地址寄存器中存放的是进程的最大逻辑地址。

3.3.覆盖和交换

1.覆盖技术

覆盖技术的思想 : 将程序分为多个段（多个模块）。常用的段常驻内存，不常用的段在需要时调入内存。
内存中分为一个“固定区”和若干个“覆盖区”。需要常驻内存的段放在“固定区”中，调入后就不再调出（除非运行结束)不常用的段放在“覆盖区”，需要用到时调入内存，用不到时调出内存。

必须由程序员声明覆盖结构，操作系统完成自动覆盖。**缺点:对用户不透明，增加了用户编程负担。**覆盖技术只用于早期的操作系统中，现在已成为历史。

2.交换技术

交换（对换）技术的设计思想: 内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存（进程在内存与磁盘间动态调度）。之前讲的中级调度（内存调度）就是为这个服务的。

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

具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区两部分。文件区主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式;对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区。由于对换的速度直接影响到系统的整体速度，因此对换区空间的管理主要追求换入换出速度，因此通常对换区采用连续分配方式（学过文件管理章节后即可理解）。总之，对换区的I/O速度比文件区的更快。

2.什么时候应该交换?

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

3.应该换出哪些进程?

可优先换出阻塞进程;可换出优先级低的进程;为了防止优先级低的进程在被调入内存后很快又被换出，有的系统还会考虑进程在内存的驻留时间…

(注意:PCB会常驻内存，不会被换出外存)

3.4.连续分配管理方式

连续分配：指为用户进程分配的必须是一个连续的内存空间。

1.单一连续分配

在单一连续分配方式中，内存被分为系统区和用户区。系统区通常位于内存的低地址部分，用于存放操作系统相关数据;用户区用于存放用户进程相关数据。
内存中只能有一道用户程序，用户程序独占整个用户区空间。
优点: 实现简单 ;无外部碎片;可以采用覆盖技术扩充内存;不一定需要采取内存保护（eg:早期的 PC操作系统MS-DOS)。
缺点:只能用于单用户、单任务的操作系统中;有内部碎片;存储器利用率极低。

2.固定分区分配

3.动态分区分配

动态分区分配又称为可变分区分配。这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的。

使用这种方式的话，我们需要考虑以下三个问题。

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

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

使用动态分区算法，这个将在下一小节进行详细介绍。

如何进行分区的分配与回收操作?

如何分配 -----------> 使用动态分区算法之后，修改数据结构即可。

如何回收-------------------------------> 牢记一点即可，==会把相邻的空闲区域合并为一个==。

4.内部碎片和外部碎片

动态分区分配没有内部碎片，但是有外部碎片。
内部碎片，分配给某进程的内存区域中，如果有些部分没有用上。
外部碎片，是指内存中的某些空闲分区由于太小而难以利用。
如果内存中空闲空间的总和本来可以满足某进程的要求，但由于进程需要的是一整块连续的内存空间，因此这些进程“碎片”不能满足进程的需求。可以通过紧凑（(拼凑，Compaction)技术来解决外部碎片。

3.5.动态分区分配算法

动态分区分配算法:在动态分区分配方式中，当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配?

1.首次适应算法

算法思想: 每次都从低地址开始查找，找到第一个能满足大小的空闲分区。
如何实现:空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链(或空闲分区表），找到大小能满足要求的第一个空闲分区。

2.最佳适应算法

算法思想:由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即，优先使用更小的空闲区。
如何实现:空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。

3.最大适应算法

又称最坏适应算法(Largest Fit)
算法思想:为了解决最佳适应算法的问题――即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。
如何实现:空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表），找到大小能满足要求的第一个空闲分区。

4.临近适应算法

算法思想: 首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。

如何实现: 空闲分区以地址递增的顺序排列(可排成一个循环链表）。每次分配内存时从上次查找结束的位置开始查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

5.四种算法对比

3.6.基本分页存储管理

连续分配:为用户进程分配的必须是一个连续的内存空间。

非连续分配:为用户进程分配的可以是一些分散的内存空间。

基本分页存储管理的思想――把内存分为一个个相等的小分区,再按照分区大小把进程拆分成一个个小部分。

将内存空间分为一个个大小相等的分区（比如:每个分区4KB），每个分区就是一个“页框”，或称“页帧”、“内存块”、“物理块”。每个页框有一个编号，即“页框号”(或者“内存块号”、“页帧号”、“物理块号”)页框号从0开始。

将用户进程的地址空间也分为与页框大小相等的一个个区域，称为“页”或“页面”。

每个页面也有一个编号，即“页号”，页号也是从0开始。
(注:进程的最后一个页面可能没有一个页框那么大。因此，页框不能太大，否则可能产生过大的内部碎片)

操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系。

各个页面不必连续存放，也不必按先后顺序来，可以放到不相邻的各个页框中。

思考：将进程地址空间分页之后，操作系统该如何实现逻辑地址到物理地址的转换?

要算出逻辑地址对应的页号
要知道该页号对应页面在内存中的起始地址
要算出逻辑地址在页面内的“偏移量”
物理地址 = 页面始址＋页内偏移量

如何计算:

页号=逻辑地址/页面长度(取除法的整数部分)
页内偏移量 = 逻辑地址%页面长度（取除法的余数部分)
页面在内存中的起始位置:操作系统需要用某种数据结构记录进程各个页面的起始位置。

举例:

页号=80 / 50= 1
页内偏移量=80 % 50 = 30
1号页在内存中存放的起始位置450

思考: 如何知道该页号对应页面在内存中的起始地址?

操作系统为每一个进程创建一个页表?

如何理解每个页表项的长度是相同的，页号是“隐含的”？

3.7.基本地址变换机构

基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。
通常会在系统中设置一个页表寄存器(PTR），存放页表在内存中的起始地址F和页表长度M。进程未执行时，页表的始址和页表长度放在进程控制块(PCB）中，当进程被调度时，操作系统内核会把它们放到页表寄存器中。

执行流程

页表项长度，页表长度，页面大小

页表长度是指这个页表中总共有几个页表项，即总共有多少页。页面大小是指一个页面占多大的存储空间。页表项长度是指每个页表项占多大的存储空间。

通过下面这个例子来理解页表项长度。

Eg:假设某系统物理内存大小为4GB，页面大小为4KB，内存总共会被分为2^32/ 2¹²⁼²20个内存块，因此内存块号的范围应该是0~2^20 - 1。因此至少要20个二进制位才能表示这么多的内存块号，因此至少要3个字节才够(每个字节8个二进制位，3个字节共24个二进制位)。每个块号用三个字节来表示。

3.8.具有快表的地址变换机构

1.局部性原理

时间局部性:如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行;如果某个数据被访问过，不久之后该数据很可能再次被访问。(因为程序中存在大量的循环)
空间局部性:一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。(因为很多数据在内存中都是连续存放的)

上小节介绍的基本地址变换机构中，每次要访问一个逻辑地址，都需要查询内存中的页表。由于局部性原理，可能连续很多次查到的都是同一个页表项。既然如此，能否利用这个特性减少访问页表的次数呢?

2.快表

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

执行流程

3.9.两级页表

两级页表的出现主要是为了解决单级页表的问题。那么单级页表有什么问题呢？

问题一:页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框。
问题二:没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面。

1.解决问题一

我们可以回想以下当初是如何解决进程必须连续的问题？

我们可以把页表放在不同的页框中，再用一个表来记录各个各个子页表所在位置，我们把这个表叫做页目录表（外层页表，顶级页表）。

2.解决问题二

3. 其他细节

若采用多级页表机制，则各级页表的大小不能超过一个页面
两级页表的访存次数分析（假设没有快表机构）

第一次访存:访问内存中的页目录表
第二次访存:访问内存中的二级页表
第三次访存:访问目标内存单元

==N级页表访问一个逻辑地址需要N+1次访问内存。==

3.10.基本分段存储管理方式

1.分段

进程的地址空间:按照程序自身的逻辑关系划分为若干个段，每个段都有一个段名（在低级语言中，程序员使用段名来编程)，每段从0开始编址。
内存分配规则 : 以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻。

分段系统的逻辑地址结构由段号（段名）和段内地址（段内偏移量）所组成。

段号的位数决定了每个进程最多可以分几个段。

段内地址位数决定了每个段的最大长度是多少。

2.段表

3.段内寻址

4.分段，分页对比

页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。
段是信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。
页的大小固定且由系统决定。段的长度却不固定，决定于用户编写的程序。
分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址。
分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。
分段比分页更容易实现信息的共享和保护。

3.11.段页式管理方式

1.分页，分段的优缺点

既然两者都有优缺点，那么可不可以把他们结合起来呢？答案当然是可以的。如下图所示。

2.段页式管理的逻辑结构

段号的位数决定了每个进程最多可以分几个段

页号位数决定了每个段最大有多少页

页内偏移量决定了页面大小、内存块大小是多少

3.段内寻址

3.12.虚拟内存 ⭐

虚拟内存的起因

使用硬盘/磁盘使更多的程序在有限的内存中运行
理想的存储器 : 更大更快更便宜和非易失性的存储区

实际的存储器

早期的解决技术

如果是程序太大，超过了内存的容量，可以采用手动的覆盖(overlay)技术，只把需要的指令和数据保存在内存当中：
如果是程序太多，超过了内存的容量，可以采用自动的交换(swapping)技术，把暂时不能执行的程序送到外存中：
如果想要在有限容量的内存中，以更小的页粒度为单位装入更多更大的程序，可以采用自动的虚拟存储技术。

覆盖技术

对编程语言, 程序员有一定的要求

交换技术

UNIX操作系统提供的方法

目标

多道程序在内存中时，让正在运行的程序或需要运行的程序获得更多的内存资源。

方法：

可将暂时不能运行的程序送到外存，从而获得空闲内存空间。
操作系统把一个进程的整个地址空间的内容保存到外存中（换出swap out),而将外存中的某个进程的地址空
间读入到内存中（换入swap in)。换入换出内容的大小为整个程序的地址空间。

存在的问题

交换时机的确定：何时需要发生交换？只当内存空间不够或有不够的危险时换出：
交换区的大小：必须足够大以存放所有用户进程的所有内存映像的拷贝；

必须能对这些内存映像进行直接存取;
程序换入时的重定位：换出后再换入的内存位置一定要在原来的位置上吗？最好采用动态地址映射的方法。

覆盖与交换的比较

覆盖只能发生在那些相互之间没有调用关系的程序模块之间，因此程序员必须给出程序内的各个模块之间的逻辑覆盖结构。
交换技术是以在内存中的程序大小为单位来进行的，它不需要程序员给出各个模块之间的逻辑覆盖结构。换言之，交换发生在内存中程序与管理程序或操作系统之间，而覆盖则发生在运行程序的内部。

传统存储管理方式的特征和缺点

一次性: 作业必须一次性全部装入内存后才能开始运行。这会造成两个问题:
1. 作业很大时，不能全部装入内存，导致大作业无法运行;
2. 当大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发度下降。
驻留性: 一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。事实上，在一个时间段内，只需要访问作业的一小部分数据即可正常运行，这就导致了内存中会驻留大量的、暂时用不到的数据，浪费了宝贵的内存资源。

虚拟内存技术⭐

覆盖技术以及交换技术都存在一定的问题, 出现了虚存技术

目标

象覆盖技术那样，不是把程序的所有内容都放在内存中，因而能够运行比当前的空闲内存空间还要大的程序。但做得更好，由操作系统自动来完成，无须程序员的干涉：
象交换技术那样，能够实现进程在内存与外存之间的交换，因而获得更多的空闲内存空间。但做得更好，只对进程的部分内容在内存和外存之间进行交换。

MMU : MMU是Memory Management Unit的缩写，中文名是内存管理单元，有时称作分页内存管理单元（英语：paged memory management unit，缩写为PMMU）。它是一种负责处理中央处理器（CPU）的内存访问请求的计算机硬件。它的功能包括虚拟地址到物理地址的转换（即虚拟内存管理）、内存保护、中央处理器高速缓存的控制，在较为简单的计算机体系结构中，负责总线的仲裁以及存储体切换（bank switching，尤其是在8位的系统上）。

程序的局部性原理

时间局部性: 一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内；
空间局部性：当前指令和邻近的几条指令，当前访问的数据和邻近的几个数据都集中在一个较小区域内。

程序的局部性原理表明，从理论上来说，虚拟存储技术是能够实现的，而且在实现了以后应该是能够取得一个满意的效果的。

基本特征

大的用户空间：通过把物理内存与外存相结合，提供给用户的虚拟内存空间通常大于实际的物理内存，即实现了这

两者的分离。如32位的虚拟地址理论上可以访问4GB,而可能计算机上仅有256M的物理内存，但硬盘容量大于4GB。
部分交换：与交换技术相比较，虚拟存储的调入和调出是对部分虚拟地址空间进行的 => 每次交换都是整块交换
不连续性：物理内存分配的不连续，虚拟地址空间使用的不连续 , 由于操作系统会把一些代码交换出去, 因此会造成物理内存分配不连续

基本思路

基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。

在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。

若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。

在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存。

比如下面的代码 , 执行速度应该是 写法一更快

注意数组在内存中的存储方式

虚拟页式内存管理

页表表项

下面的几个bit 对于页面的置换十分必要

驻留位：表示该页是在内存还是在外存。
- 如果该位等于1，表示该页位于内存当中，即该页表项是有效的，可以使用：
- 如果该位等于0，表示该页当前还在外存当中，如果访问该页表项，将导致缺页中断：
保护位：表示允许对该页做何种类型的访问，如只读、可读写、可执行等：
修改位：表明此页在内存中是否被修改过。当系统回收该物理页面时 , 根据此位来决定是否把它的内容写回外存;
如果修改位是0 , 表明没有对这个页做写操作, 那么说明这个页的数据与在硬盘中的数据是一样的 , 这个时候就不需要做写回 , 如果这个时候需要把这个页去掉, 直接进行释放即可
- 通过对修改位的使用可以有效的提高置换功能的效率
访问位：如果该页面被访问过（包括读操作或写操作），则设置此位 , 用于页面置换算法。
- 如果最近被访问过, 那么置为 1

注意点

虚拟内存的最大容量是由计算机的地址结构（ CPU寻址范围）确定的

虚拟内存的实际容量= min(内存和外存容量之和，CPU寻址范围)

如: 某计算机地址结构为32位，按字节编址，内存大小为512MB，外存大小为2GB.

则虚拟内存的最大容量为2^32B= 4GB 。虚拟内存的实际容量=min (2^32B,512MB+2GB)= 2GB+512MB

虚拟内存三个主要特征

多次性:无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。
对换性:在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出。
虚拟性:从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。

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

虚拟内存的性能

3.13.请求分页管理方式

1.页表机制

与基本分页管理相比，请求分页管理中，为了实现“请求调页”，

操作系统需要知道每个页面是否已经调入内存;
如果还没调入，那么也需要知道该页面在外存中存放的位置。
当内存空间不够时，要实现“页面置换”，操作系统需要通过某些指标来决定到底换出哪个页面;
有的页面没有被修改过，就不用再浪费时间写回外存。有的页面修改过，就需要将外存中的旧数据覆盖，因此，操作系统也需要记录各个页面是否被修改的信息。

因此页表会增加四个字段来上面的信息。

2.缺页中断机制

假设此时要访问逻辑地址 = (页号，页内偏移量）= (0，1024)

在请求分页系统中，**每当要访问的页面不在内存时，便产生一个缺页中断，**然后由操作系统的缺页中断处理程序处理中断。

此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。

如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项。

如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存。

缺页中断是因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此属于内中断

一条指令在执行期间，可能产生多次缺页中断。(如: copy AtoB，即将逻辑地址A中的数据复制到逻辑地址B，而A、B属于不同的页面，则有可能产生两次中断)

3.地址变换

4.后备存储backing store

在何处保存未被映射的页？

能够简单地识别在二级存储器中的页
交换空间（磁盘或者文件）：特殊格式，用于存储未被映射的页面

概念：后备存储

一个虚拟地址空间的页面可以被映射到一个文件（在二级存储中)中的某个位置
代码段：映射到可执行二进制文件
动态加载的共享库程序段：映射到动态调用的库文件
其它段：可能被映射到交换文件(swap file)

补充知识点

只有“写指令”才需要修改“修改位”。并且，一般来说只需修改快表中的数据，只有要将快表项删除时才需要写回内存中的慢表。这样可以减少访存次数。
和普通的中断处理一样，缺页中断处理依然需要保留CPU现场。
需要用某种“页面置换算法”来决定一个换出页面（下节内容)
换入/换出页面都需要启动慢速的I/o操作，可见，如果换入/换出太频繁，会有很大的开销。
页面调入内存后，需要修改慢表，同时也需要将表项复制到快表中。

3.14.页面置换算法⭐

3.2_3_页面置换算法_哔哩哔哩_bilibili

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

1.最佳置换算法 =>无法实现

最佳置换算法（OPT，Optimal): 每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。

最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。

操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。

只有当内存块全部占满并且出现了缺页中断才会发生页面置换

2.先进先出置换算法-FIFO

先进先出置换算法（FIFO): 每次选择淘汰的页面是最早进入内存的页面

实现方法:把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面即可。队列的最大长度取决于系统为进程分配了多少个内存块。

那么当我们增加了内存块的个数 :

可以发现虽然我们增加了内存块的个数, 缺页中断的发生次数反而增加了 , 这就是 Belady 异常

Belady异常：当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。

只有FIFO算法会产生Belady异常。另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问。因此，算法性能差。

3.最近最久未使用算法-LRU

最近最久未使用置换算法（LRU，least recently used): 每次淘汰的页面是最近最久未使用的页面。

实现方法:赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t。

当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面。

4.时钟置换算法-NRU

最佳置换算法性能最好，但无法实现;先进先出置换算法实现简单，但算法性能差;最近最久未使用置换算法性能好，是最接近OPT算法性能的，但是实现起来需要专门的硬件支持，算法开销大。

时钟置换算法是一种性能和开销较均衡的算法，又称CLOCK算法，或最近未用算法(NRU，NotRecently Used)

简单的CLOCK 算法实现方法:

为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。

当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。

如果是0，就选择该页换出;
如果是1，则将它置为0，暂不换出，继续检查下一个页面，

若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描)

5.改进型的时钟置换算法

简单的时钟置换算法仅考虑到一个页面最近是否被访问过。

事实上，==如果被淘汰的页面没有被修改过，就不需要执行I/o操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。==
因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。

在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/o操作。这就是改进型的时钟置换算法的思想。修改位=0，表示页面没有被修改过;修改位=1，表示页面被修改过。
为方便讨论，用==（访问位，修改位）==的形式表示各页面状态。

如（1，1)表示一个页面近期被访问过，且被修改过。

算法规则: 将所有可能被置换的页面排成一个循环队列
第一轮:从当前位置开始扫描到第一个（0，0）的帧用于替换。本轮扫描不修改任何标志位
第二轮:若第一轮扫描失败，则重新扫描，查找第一个（0，1）的帧用于替换。本轮将所有扫描过的帧访问位设为0
第三轮:若第二轮扫描失败，则重新扫描，查找第一个(0，0）的帧用于替换。本轮扫描不修改任何标志位
第四轮:若第三轮扫描失败，则重新扫描，查找第一个（0，1）的帧用于替换。
由于第二轮已将所有帧的访问位设为0，因此经过第三轮、第四轮扫描一定会有一个帧被选中，因此改进型CLOCK置换算法选择一个淘汰页面最多会进行四轮扫描

第一优先级：最近没访问，且没修改的页面
第二优先级：最近没访问，但修改过的页面
第三优先级：最近访问过，但没修改的页面
第四优先级：最近访问过，且修改过的页面

6.五种算法对比

3.15.页面分配策略

1.页面分配，置换策略

驻留集:指请求分页存储管理中给进程分配的物理块的集合。

在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。

若驻留集太小，会导致缺页频繁，系统要花大量的时间来处理缺页，实际上用于进程推进的时间很少。
驻留集太大，又会导致多道程序并发度下降，资源利用率降低。所以应该选择一个合适的驻留集大小。

固定分配:操作系统为每个进程分配一组固定数目的物理块，在进程运行期间大小不变。即，驻留集大小不变。

可变分配:先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。即，驻留集大小可变

局部置换:发生缺页时只能选进程自己的物理块进行置换。

全局置换:可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。

下面来分别介绍这几种方式。

固定分配局部置换:系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面。这种策略的缺点是:很难在刚开始就确定应为每个进程分配多少个物理块才算合理。(采用这种策略的系统可以根据进程大小、优先级、或是根据程序员给出的参数来确定为一个进程分配的内存块数)
可变分配全局置换:刚开始会为每个进程分配一定数量的物理块。操作系统会保持一个空闲物理块队列。当某进程发生缺页时，从空闲物理块中取出一块分配给该进程;若已无空闲物理块，则可选择一个未锁定的页面换出外存，再将该物理块分配给缺页的进程。采用这种策略时，只要某进程发生缺页都将获的物理块，仅当空闲物理块用完时，系统才选择一个未锁定的页面调出。被选择调出的页可能是进程中任意一个进程的页，因此被选中的这个进程物理块会减少，缺页率会增加。
可变分配局部置换：刚开始会为每个进程分配一定数量的物理块，当某进程发生缺页时，只允许从该进程自己的物理块中选出一个换出外存。如果进程在运行中频繁地缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋势适当，反之，如果进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块。

可变分配全局置换:只要缺页就给分配新物理块
可变分配局部置换:要根据发生缺页的频率来动态地增加或减少进程的物理块

2.何时调入页面

预调页策略: 根据局部性原理（主要是空间局部性），一次调入若干个相邻的页面可能比一次调入一个页面更高效。但如果提前调入的页面中大多数都没被访问过，则又是低效的。因此可以预测不久之后可能访问到的页面，将它们预先调入内存，但目前预测成功率只有50%左右。故这种策略主要用于进程的首次调入，由程序员指出应该先调入哪些部分。它是运行前调入。
请求调页策略: 进程在运行期间发现缺页时才将所缺页面调入内存。由这种策略调入的页面一定会被访问到，但由于每次只能调入一页，而每次调页都要磁盘l/o操作，因此I/o开销较大。它是运行时调入。