内存使用与分段

一、内存使用

1.逻辑地址

内存作为计算机的基本组成部分，用来存储程序（指令和数据），内存单元按字节编址、寻址，程序装入到内存后，PC 指向程序开始地址，依次取指执行

==即内存使用：将程序放到内存中，PC指向开始地址==

这是main()编译后，entry是入口地址，如果_main相对于_entry的偏移地址是40

现在如果这段程序要运行，那么只要将PC指向 call 40 这条指令所在的地址就好了，执行完call 40之后，会自动跳到地址为40处执行。

但是现在有个问题，_main所在的位置一定是物理地址为40的位置吗？换言之，40表示的是物理地址吗？

学过前面的知识，我们知道肯定不是的，前面放的system模块

call 40这个40指的是相对于_entry的偏移量，程序里面的地址是==相对地址（逻辑地址）==，而==程序真正运行时的地址是绝对地址（物理地址）==，即程序运行时，==根据逻辑地址得到物理地址就是地址的重定位==。

比如_entry这条指令的地址如果存放在物理地址为1000处，那么_main的 地址就应该是1040，所以call 40就要变成call 1040.

2.重定位

==重定位:== ==重定位是指将指令中的逻辑地址转换为内存中实际的物理地址的过程==

重定位方式:

1.编译时重定位 编译时重定位的程序只能放在内存中的固定位置，而编译结束后的内存使用情况不一定,与编译时的相同，因此这种重定位方式有很大的局限性。必须保证装入该程序时，这段程序要使用的地址是可用的。

编译时进行重定位后，装入过程不需要有额外开销，因此效率较高

编译时重定位一般用在可以保证一段程序固定地装入某段内存中的嵌入式系统中

2.载入时重定位（静态重定位） 程序在装入内存时，将指令中的相对地址加上装入的内存段的基址作为绝对地址，载入时重定位的程序一旦载入内存后就不可以再移动位置。不利于程序在内存中的移动（交换，swap）。

3.运行时重定位（动态重定位）(最佳时机） 运行时重定位的程序，装入内存的仍是逻辑地址，在实际访问时进行重定位，即在进程 PCB 中保存程序段的基址，实际访问时进行地址翻译（由基地址与逻辑偏移计算出物理地址），无妨交换

3.交换

为了更好地支持多进程，当内存空闲空间不足时，有选择地将某些进程保存到硬盘上（换出），将腾出的空间交给当前需要运行的进程使用，即将要运行的进程换入到内存
进程1睡眠将进程1换出放入磁盘中，并将要运行的程序换入，当程序1要再次运行的时候，就再次换入，但是每次的基地址可能不一样。所以，一般在运行时重定位。

二、内存分段

在内存的使用方式，以及每个进程中的指令的地址如何对应到实际的内存 实际上，更多时候进程不是作为一个连续的整体装入内存的

而按照程序本身特点，将进程分段管理，满足每个段的需要，建立段表，描述段的信息，包括段号、段基址、段限长，段类别等等 可以单独移动、扩大某个段，只需要维护好段表

进程由多个部分(段)组成，每个段有各自的特点和用途，因为各个段性质的不同，当所有段作为一个整体看待时就会有所不便，比如，代码段是只读的，代码段、数据段不会动态增长，而堆栈段可能要动态增长

假如不分段，在一个程序中执行指令和数据会杂糅在一起并保存在内存中，由于执行指令写到内存后不能被用户修改的，属于只读属性的。而程序中的数据是可读可写的，所以当计算机取址执行时还要判断该对应内存地址下的是指令还是数据，这样就不好判断了。所以我们将指令与数据用地址区间来分开，这样计算机在取址时通过判断地址就可以知道取的是指令还是数据，便于执行程序。所以人们为了计算机方便，就将程序中的具有相同属性的内容放到同一块内存片段。

定位指令(数据):<段号，段内偏移>

重定位的段号有特定的表来记录(LDT，和GDT表一样) CPU每执行一条牵涉到地址的指令都会查一下PCB里面这个进程段表，从而确定物理地址，有一个专门存放该表地址的寄存器LDTR寄存器。

每个进程可以维护一个LDT表作为进程段表 操作系统维护 GDT，每个 LDT 的入口可以作为GDT的一个表项，LDTR寄存器保存当前LDT的地址 进程切换时，切换PCB，包括切换指令序列(CS:IP)与映射表(LDT)

当内存在分段管理时，建立一个进程需要按程序所分的段(编译时确定)建立其段表，即初始化LDT，并将LDT与PCB关联起来，然后在内存中找到一块合适空闲区域装入程序

1.linux0.11下TCB/PCB的实现都是靠一个task_struct结构体

2.这个结构体里面还有一个结构体tss

3.tss里面放的内容可以理解为是当前进程的CPU快照

4.由于进程切换，段寄存器的内容就放在task_struct里的tss了

内存的管理

前面讲了内存的分段，这才是内存管理的起点。接下来，分段和分页结合使用才能真正的管理和使用内存

一、内存分区

分区式存储管理是把内存分为一些大小相等或不等的分区，操作系统占用其中一个分区，其余的分区由应用程序使用，每个应用程序占用一个或几个分区。分区式存储管理虽然可以支持并发，但难以进行内存分区的共享。

专业术语介绍

(1)内碎片与外碎片：

内碎片是占用分区内未被利用的空间，外碎片是占用分区之间难以利用的空闲分区(通常是小空闲分区)。

(2)内存紧缩：将空间分区合并需要移动一个段（复制内容），消耗大量时间，影响操作系统性能

1.固定分区

固定分区：把内存划分为若干个固定大小的连续分区，这种作法只适合于多个相同程序的并发执行(处理多个类型相同的对象)。分区大小也可以不等：有多个小分区、适量的中等分区以及少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。

优点：易于实现，开销小 缺点：内碎片造成浪费；分区总数固定，限制了并发执行的程序数目

2.动态分区

==动态分区就是动态创建分区，在装入程序时按其初始要求分配，或在其执行过程中通过系统调用进行分配或改变分区大小。==

动态分区的分区分配就是寻找某个空闲分区，其大小需大于或等于程序的要求。若是大于需求，则将该分区分割成两个分区，其中一个分区为要求的大小并标记为“占用”，而另一个分区为余下部分并标记为“空闲”。

分区分配的先后次序通常是从内存低端到高端。动态分区的分区释放过程中有一个要注意的问题是，将相邻的空闲分区合并成一个大的空闲分区。 与固定分区相比较：没有内碎片，但它却引入了另一种碎片——外碎片。

==(1)可变分区的管理过程——核心数据结构==

通过已分配分区表和空闲分区表两张表来记录分区使用情况。当有段请求时，空闲分区表将改变 ==(2)可变分区的管理—请求分配== 在上图中，原本内存中已分配了seg1和seg2，空闲分区从地址250k开始，大小为250K，现有一个100k大小的段请求，于是250k-350k被分配给了新请求段seg3，空闲分区还剩下150k

==(3)可变分区的管理—释放内存== 同时由于进程可能被换入换出，所以内存中已分配的空间有可能被释放，因此空闲分区可能存在多段

==(4)可变分区的管理—再次申请==

当存在多个空间分区时，再来一个段提出内存请求，该选谁？所以引入了三个分区分配算法

3.分区分配算法

==(1)最先适配法(nrst-fit)==

按分区在内存的先后次序从头查找，找到符合要求的第一个分区进行分配。该算法的分配和释放的时间性能较好，较大的空闲分区可以被保留在内存高端。但随着低端分区不断划分会产生较多小分区，每次分配时查找时间开销便会增大。

==(2)最佳适配法(best-fit)==

按分区在内存的先后次序从头查找，**找到其大小与要求相差最小的空闲分区进行分配。**从个别来看，外碎片较小；但从整体来看，会形成较多外碎片优点是较大的空闲分区可以被保留。

==(3)最坏适配法(worst- fit)==

按分区在内存的先后次序从头查找，找到最大的空闲分区进行分配。基本不留下小空闲分区，不易形成外碎片。但由于较大的空闲分区不被保留，当对内存需求较大的进程需要运行时，其要求不易被满足。

首先适配快，但其他分区就浪费时间，最佳分配需要遍历内存 因此需要引入分页：解决内存分区导致的内存效率问题

二、内存分页

1.引入分页

引入分页: 解决内存分区导致的内存效率问题

可变分区多次分配以后就会形成内存碎片，当再来一个段请求大于每个单个空间空间时，就需要将内存合并：内存紧缩，内存紧缩需要花费大量时间 解决方法：将每个段分成多页，内存也分成很多页，页是最小分配单位，这样每次分配段空间，最多浪费不超过一页，没有内存碎片

其实也有会部分内存没有使用到，但是注意这种思想，页是一个单位，每次分配的内存都是整数个页，也就是将这些分配出去的页都看成是已经使用的了，所以就没有内存碎片。==所以从内存角度来说这种方式是比较好的，也就是物理内存想要分页，但是用户程序希望是分段。==后面会说到的

每个段在计算物理地址时需要查找段的基址，那么将段分成页后，计算物理地址需要查找页的基址，物理地址=页基址+逻辑地址。

PCB中存在页表保存每个段的页分配信息，为了取分段的页，将内存的页叫作页框 内存分段的有一个段表，分页自然也要有一个页表。有一个专门的寄存器存储页表的地址。

注意页在内存的排布顺序并不是按照地址的顺序递增的，也就是说页0不一定是放在地址零处，这里引入页框，页框是按照内存顺序排列的，并且页框的大小和页是相同的

分析mov [0x2240],%eax

1
2
3
4
5

图片中：  mov [0x2240],%eax  
2240地址表示的实际内存地址是多少？首先看它是那一页的，每一页的大小为
4k，0x2240除以4K得到页号，除以4K也就是右移12位,得到2,即第二页，根据页
号找到具体的页框号，在上图中为3，具体的地址就是3*4K+240=3240，即物理地
址为3240.

2.多级页表

为了提高内存的利用率，内存是分页管理的，并且有一个页表用来存储页号与页框的对应关系。

但是，为了更好的提高内存的利用率，每一页就应该做得足够小，但是每一页都要在页表里面有一项与页框对应，也就是说页数越多页表也就会越大，页表如果很大的话就会对内存造成浪费，因为存放页表的这部分你内存是不能给程序使用的，并且一直存放在该进程的PCB里面

(1)只存放用到的页

只用到0，1，3就存放这三页，如图 若这存放用到的页，但这样的话页表的项就不连续了，找某一页对应的页框就不能直接使用偏移量的形式，较高查找效率是折半查找（因为页号是有顺序的），即便使用折半查找耗费的时间也会比使用偏移量大很多倍。

所以页表的页号必须是连续的。

==(2)多级页表(页目录表+页表)==

==页目录表的每一项对应一个页表，然后再根据页表找到对应的页。== 一个逻辑地址用10bits的页目录号+10bits的页号+12bits的偏移组成

这种思想就类似于书本的目录，目录的地方有一个章目录（页目录表）和节目录（页表)，如果要查找某一节的内容首先找到这一章的地方，然后再查具体的某一节

不仅能节省大量内存，并且保证了章目录和节目录都是连续的，所以可以使用偏移量的形式查找对应的章节

3.快表TLB

多级页表提高了空间效率，但是在时间的效率上非常低。因为每一次访问的时候都要根据章目录找到页目录再找到具体的页。也就是需要访问三次内存，cpu每一条指令执行的时间其实大部分都是浪费在访问内存上 解决方法：在CPU与内存访问之间加一组TLB，==TLB是一组寄存器，用来存放最近使用过的页对应的页框号==

这样如果CPU需要访问某一页首先在TLB里面找，如果TLB里面有就不用访问内存了，因为TLB是寄存器，cpu访问寄存器的速度远大于对内存的访问速度，大大地提升时间性能了。

提升时间性能最主要的因素就是==可以在TLB里面直接找到该页对应的页框号==。

要提升命中率，TLB肯定是越大越好，但是TLB材料很贵，不会做得很大。TLB的大小大概是[64,1024]。

为什么TLB里面存放这么少的项就能实现“近似访存1次”？

因为程序的局部性原理，==程序的局部性原理在用户程序里面多对应的是循环，顺序结构==

总结

为了提高内存的空间性能，提出了多级页表；但是提到空间性能是以浪费时间性能为基础的，因此为了补充损失的时间性能，提出了快表(即TLB)，快表利用的是程序的局部性原理。

Linux虚拟内存

一、虚拟内存的引入

1.基本概念

虚拟内存：

用辅助存储器（一般指磁盘）作为内存的补充。虚拟内存允许进程执行时只将部分程序放入内存，因此程序可以比物理内存大。虚拟内存的大小受计算机寻址机制和可用辅助存储器容量大限制，而不受内存容量的限制。

特征：

①运行进程时只把现在要执行的页/段装入内存，其余页/段放在外存，需要时再利用请求调入页/段功能和置换功能将其调入内存。 ②在逻辑上扩充内存容量 ③访问速度接近于内存，没位(bit)成本接近于外存。

虚拟地址：即逻辑地址，虚拟内存中某个字节的地址，假设该字节在内存中（其实可能位于磁盘，但这对用户是透明的）

虚拟地址空间：分配给某个进程（程序）的虚拟地址范围

实地址：即物理地址, 物理内存中某个字节的地址

驻留集：进程运行时装入内存的部分

工作集：在 t 时刻，进程在过去的N个时间单位内访问的页面集合(活跃页面)

内存管理单元MMU：集成在CPU中，或作为一个协处理器

==功能：分解逻辑地址；逻辑地址到物理地址的转换；查找更新快表TLB；进程切换时清空TLB；发出缺页中断或越界中断；设置和检查页表中各个特征位。==

2.局部性原理

上一篇笔记中提了一点关于局部性原理的特点，这里更详细的介绍。

局部性原理表现在以下两个方面：

==(1)时间局部性==

如果程序中的某条指令一旦执行，不久以后该指令可能再次执行；如果某数据被访问过，不久以后该数据可能再次被访问。

原因:==是由于在程序中存在着大量的循环操作==

==(2)空间局部性==

一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内

原因：==指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式簇聚存储的==。

快表、 页高速缓存以及虚拟内存技术从广义上讲，都是属于高速缓存技术。这个技术所依赖的原理就是局部性原理。局部性原理既适用于程序结构，也适用于数据结构

3.引入

从前面我们了解到：物理内存必须得是分页管理的；对用户来说是分段的。

但是用户程序最终能在内存上面跑，肯定需要某种机制或者转化使得以用户程序的视角看起来内存是分段的，以物理内存的视角看起来又是分页的，这种机制就是虚拟内存

时间局部性是通过将近来使用的指令和数据保存到高速缓存存储器中，并使用高速缓存的层次结构实现。

空间局部性通常是使用较大的高速缓存，并将预取机制集成到高速缓存控制逻辑中实现。虚拟内存技术实际上就是建立了 “内存一外存”的两级存储器的结构，利用局部性原理实现髙速缓存。

虚拟内存是一种和物理内存一样的东西，每一个字节都有对应的地址。但是有一点与物理内存不同，从它的名字就能看出来，“虚拟”：即实际上并不存在，它只是一种机制，是用程序表示的。它的作用就是让上层程序看起来是内存是分段的，而实际上是分页的，如图

用户程序使用了一段内存，首先会在虚拟内存上面找到一段空的内存，然后将用户程序使用的内存映射到这段内存上，然后虚拟内存再将这段内存映射到物理内存上

用户程序使用的逻辑内存经过了两次映射才达到物理内存，第一次映射是段的映射，需要段表；第二次是页的映射，需要页表。

逻辑地址究竟是如何变成物理地址的呢？

==逻辑地址是段号+偏移（CS：IP）组成的，首先根据段号在段表中找到虚拟内存的段基址，然后加上偏移得到虚拟地址（即在虚拟内存上面的地址），格式是：页号+偏移。然后根据页号在页表中找到对应的页框号，再加上偏移得到最后的物理地址。实现了逻辑地址与物理地址的对应。也就是重定位操作。==

二、实现虚拟内存

1.载入内存

内存管理的核心就是内存分配，所以从程序放入内存、使用内存开始

首先为程序分配虚拟内存，将程序中的各段分配到虚拟内存的闲置空间中，然后再将虚拟内存中的各段再分成若干页，映射到物理内存的页框中

2. 分配虚存、 建段表

创建进程使用的是fork()系统调用，从前面可以知道fork()->sys_fork->copy_process

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

在Linux/kernel/fork.c
int copy_process(int nr, long ebp...)
{
	………………
	copy_mem(nr,p); //分配虚拟内存
	………………
}

int copy_mem(int nr, task_struct *p)
{
	unsigned long new_data_base;
	new_data_base = nr*0x4000000;		// nr * 64M
	set_base(p_>ldt[1], new_data_base);		// 代码段 ldt(段表)
	set_base(p->ldt[2], new_data_base);		// 数据段
	………………
}

调用fork()，然后调用sys_fork，进入copy_process后，在copy_process中调用copy_men();

copy_men()函数就是给该进程在虚拟内存上分配内存空间的， 形参 nr：第nr个进程 p：该进程的pcb

1

 new_data_base = nr*0x4000000;		// nr * 64M

给该进程在虚拟内存上分配一块64M的内存块。可以看到第0个进程内存区域就是0 ~ 64M，第一个进程64~128M，依次类推，互不重叠。然后将p的ldt[1]和ldt[2]都指向这块内存

ldt[1]和ldt[2]指的是数据段和代码段，数据段和代码段现在在虚拟内存上分配内存、建立段表完成

3.分配内存、建页表

分配内存、建立页表，还是copy_mem()函数完成的

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

int copy_mem(int nr, task_struct *p)
{
	unsigned long old_data_base;
	old_data_base = get_base(currnet->ldt[2]);
	copy_page_tables(old_data_base, new_data_base, data_limit);
	………………
}

int copy_page_tables(unsigned long from, unsigned long to , long size)
{
	from_dir = (unsigned long *) ((from>>20) & 0xffc);
	to_dir = (unsigned long * )((to>>20) & 0xffc);
	size = (unsigned long)(size + 0x3fffff) >> 22;

	for (; size-->0; from_dir++, to_dir++)
	{
		from_page_table=(0xfffff000 & *from_dir);
		to_page_table = get_free_page();
		*to_dir = ((unsigned long) to_page_table) | 7;
	}
}

简单分析：

1

old_data_base = get_base(currnet->ldt[2]);

得到当前进程的虚拟内存地址赋给old_data_base，再调用copy_page_tables()函数，

参数from和to：都是32为虚拟内存地址 from_dir指向一个父进程的页目录项（章） to_dir指向一个子进程的页目录项（章） 32位虚拟地址格式：

1
2
3

from_dir = (unsigned long *) ((from>>20) & 0xffc);
//from右移22位得到的是页目录号 ffc00000 ->1111 1111 1100 0000 
//这里右移20 并与上0xffc 就是去前10位，

size是页目录项数

1
2
3
4
5
6
7

for (; size-->0; from_dir++, to_dir++)
{
	from_page_table=(0xfffff000 & *from_dir);
	to_page_table = get_free_page();
	//分配一个物理内存页来保存页表,就是在mem_map中找一段没有被用过的内存
	*to_dir = ((unsigned long) to_page_table) | 7;
}

from_dir就是一个指向页目录号的指针，根据这个指针找到每一个页号和对应的页框号,get_free_page()新建一个子进程的页目录表，然后将这个页目录表赋给to_dir,但是to_dir指向的表的内容是空的

get_free_page()函数：得到一段空闲的空间

1
2
3
4
5
6
7
8
9

unsigned long get_free_page(void)
{ register unsigned
long _res asm(“ax”);
_asm_(“std; repne;
scasbnt”
“movl %%edx,%%eaxn”
“D”(mem_map+PAGIG_PA
GES-1));
return _res; }

接下来就是填表,将父进程的页表拷贝到子进程中

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

for (; nr-->0; from_page_table++, to_page_table++)
{
	this_page = *from_page_table;
	this_page &= ~2;		// 设置为只读,父进程子进程共享一个页
	*to_page_table = this_page;
	*from_page_table = this_page;
	this_page -= LOW_MEN;
	this->page >>= 12;
	mem_map[this_page]++; 这一页被共享了，当其中一个释放，还有其他的在使用，因此要+1
}

做完上面三步，内存情况：

4.重定位

通过逻辑地址找到虚拟地址，通过虚拟地址找到物理地址(MMU自动完成)

如：

对父进程指向p=0x300， *p=7，父进程就会在通过重定位找到物理地址，然后将7写入

然后父进程fork()一个子进程，因为公用的是一套页表，并且将页表置位只读，因此子进程指向p=0x300， *p=8时，就会重新申请一段内存，修改页表，然后MMU重新计算，然后执行*p = 8，这样就实现了进程之间的分离。

总结

虚拟内存的实现

• 1.分配段
• 2.建段表
• 3.分配页
• 4.建页表
• 5.重定位

内存换入与换出

为了保证内存在用户程序看起来是分段，而实际是分页的效果，引入了虚拟内存。对于用户来说，虚拟内存是一个完整的内存，用户可以随意使用该内存，假设为4G，对于用户来说就有4G的空间可以使用，但是真正的物理内存远小于4G。为了实现这一差别，引出了内存换入和换出

一、内存换入

1.引出换入

从前面我们知道，在内存中段页同时存在

但是实际情况是虚拟内存的大小一般大于物理内存，我们又不得不实现虚拟内存，所以，用换入换出实现这一差别(建立虚拟内存与物理内存的映射)。

==分段分页的核心是虚拟内存，而要实现虚拟内存，就需要进行内存的换入和换出==

当要访问某一个段的时候，将该段映射到物理内存中，不向相关的数据可以覆盖。

2.请求调页

先用逻辑地址通过查段表计算出虚拟地址时，再由虚拟地址查页表计算物理地址，当用虚拟地址查页表发现该虚拟地址没有映射，即该页没有载入内存时，需要从磁盘中将该页载入物理内存（请求调页）

逻辑地址CS:IP，首先根据CS在段表中找到对应的基址，加上偏移得到虚拟地址：页号+偏移。然后根据页号在页表中找到对应的页框号，加上偏移得到物理地址。

但是如果在页表中找不到对应的页号对应的页框地址，就要从磁盘上将这一页换入了。

换入是利用中断来处理(页错误处理程序)，如果load[addr]的时候，发现addr在页表里面没有对应映射，那么就将中断向量寄存器的某一位置为1，说明有中断产生。然后在中断服务函数里面将addr导入到物理内存中。然后再次执行load[addr]这条语句。

通过虚拟地址查页表找不到映射的情况称作缺页，发现缺页后就要从磁盘中请求调页，这个过程一般比较长，同时需要进入内核，所以在中断中进行。一旦发生缺页，就进入缺页中断，在中断中请求调页。同时建立虚拟内存的该页与物理内存的映射，当请求调页完成时，映射也建立好了 将某页从磁盘换入到内存的，从中断服务函数开始。cpu有专门的中断会就去查找中断号，然后转去执行该中断服务程序。这些东西是在系统初始化的时候就做好了

(1)设置中断号

1
2
3
4
5
6
7

void trap_init(void)
{
	set_trap_gate(14, &page_fault); //设置中断号
}

# define set_trap_gate(n, addr)
	_set_gate(&idt[n], 15, 0, addr);

(2)中断处理page fault

(3)进入中断要push保留现场，然后调用do_no_page(); 当页不存在时，执行该函数

1
2
3

page=get_free_page();
bread_page(page, current->executable->i_dev, nr);
put_page(page, address);

先分配一个空闲页给page，然后将磁盘里面的页读到内存中，调用put_page建立映射，最后再次执行load[addr]

(4)建立映射put_page

二、内存换出

1.引入换出

由于物理内存大小是有限的，在内存换入多次后，物理内存就会满，因此必须换页，才能腾出空间给新换入的页。

换页的核心问题是需要选择一页淘汰，换出到磁盘，选择哪一页？类似于进程调度

2.FIFO算法

即每次缺页的时候就替换掉最开始的那一页（先进先出） 在第一次换D的时候将A换入，但是后面紧跟着又要换入A… 这种算法在这个方面肯定不是最好的算法，因为它没有任何机制保证替换次数尽可能少

3.MIN算法

选最远（不常用的）将使用的页淘汰， 是最优方案 但是，MIN需要知道将来发生的事，在实际中不可行

4.LRU算法

选最近最长一段时间没有使用的页淘汰(最近最少使用)

用过去的历史预测将来，可以通过前面调用的页的顺序来推测未来哪些页是常用的，理论基础就是程序的空间局部性。

实现一：时间戳

用时间戳来记录每页的访问时间 第一次将A放入页框中，并记录当前时间为1；第二次将B放入页框中，并记录当前时间为2；第三次将C放入页框中，并记录当前时间为3；第四次又是访问A页，更新A页访问时间，第五次访问B页，更新B页访问时间；第六次访问D页，不存在，那么就在A、B、C页中选择一个最早使用的也就是数字最小的替换，即C页。

理论上算法可行，但是，每次地址访问都需要修改时间戳， 需维护一个全局时钟， 需找到最小值 … 实现代价较大

1. 这里的关键是维护时机的问题。

2. 如果不缺页，程序应该是直接通过MMU访问物理地址，内核没有机会进行时间戳或者栈的维护。

3. 只有在缺页中断的时候内核才有机会接触处理页换出。

4. 任何在不缺页的时候的数据结构维护都会带来巨大开销

实现二：页码栈

每次选择栈底换出 每次地址访问都需要修改栈(修改10次左右栈指针) … 实现代价仍然较大

5.Clock算法

LRU的近似实现 – 将时间计数变为是和否

实现这一算法：Second Chance Replacement（再给一次机会）

具体思想：每页增加一个引用位( R )，每一次访问该页时，就将该位置为1。当发生缺页时用一个指针查看每一页的引用位，如果是1则将其置为0，如果是0就直接淘汰。

每次访问一页时， 硬件自动设置该位

选择淘汰页： 扫描该位， 是1时清0， 并继续扫描； 是0时淘汰该页

这种方法提高了内存的效率，只要维护R位（在PCB中）

但是，如果缺页很少，可能会出现所以的R为1（在实际中，缺页的情况不会很多；如果缺页很多了，说明内存太小了或者算法不行）

当发生缺页时，指针转一圈之后将所有的页的引用位都置为0，没找到能替换的，继续转，这时候发现最开始的页引用位为0，将其换出，指针后移

然后又一段时间没有发生缺页，所有页的引用位都为1，当发生缺页之后，又会将这一轮最开始的页换出，然后指针后移，一段时间之后发生缺页，又会将这一轮最开始的页换出，这不就直接退化为FIFO了吗？

原因：记录了太长的历史信息

解决：==定时清除R位==

再加一个指针用来清除每一页的引用位（这个指针的移动速度要快），可以放在时钟中断里面，定时清除

三、帧frame

现在置换策略有了，但是还有一个问题：给进程分配多少个页框(帧frame)?

如果分配多，请求调页导致的内存高效利用就没有用。而且内存就那么大，如果每一个进程分配很多的话，跑的进程数量就少了。

如果分配的少，系统内进程增多，每个进程的缺页率增大，当缺页率大到一定程度，进程就会总等待调页完成，导致cpu利用率降低，这一现象为颠簸(thrashing)

所以，先给进程分配一定数量的页框，如果增加页框能增加cpu利用率，就缓慢增加，如果导致cpu利用率减少，就降低页框分配。当然实际情况下每个进程对应的页框数量肯定是得动态调整的。

总结

内存的换入与换出大致过程：