操作系统原理——虚拟内存

之前学过的知识慢慢捡起来，为实习面试准备基础知识！

虚拟内存的一些概念

局部性原理

时间局部性:如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行;如果某个数据被访问过，不久之后该数据很可能再次被访问。(因为程序中存在大量的循环)

空间局部性:一日程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。(因为很多数据在内存中都是连续存放的，并且程序的指令也是顺序地在内存中存放的)

高速缓冲思想

将近期会频繁访问到的数据放到更高速的存储器中，暂时用不到的数据放在更低速存储器中。

虚拟内存

基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。
在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。
若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。
在操作系统的管理下，进程的可用内存大小比实际内存大小要大得多,但这个“内存大小”不是真实存在的，是通过OS和硬件MMU模拟出来的，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存。

特征

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

几种地址

1. 虚拟地址：虚拟内存中某字节的地址，仿佛该字节存在内存中，其实可能位于磁盘，但这对用户透明
2. 虚拟地址空间：分配给某程序的虚拟地址范围。
3. 实地址：物理内存中的某字节地址
4. 驻留集：进程运行时装入内存的部分
5. 工作集：实际进程访问到的物理块，驻留集 >工作集

分页

页表

将程序的逻辑地址空间划分为固定大小的页(page)，而物理内存划分为同样大小的页框(page frame)。程序加载时，可将任意一页放人内存中任意一个页框，这些页框不必连续，从而实现了离散分配。该方法需要CPU的硬件支持，来实现逻辑地址和物理地址之间的映射。

在系统每次访问虚存页时，都要在内存的所有页表中寻找该页的页框，这是一个很费时间的工作。但是，人们发现，系统一旦访问了某一个页，那么系统就会在一段时间内稳定地工作在这个页上。所以，为了提高访问页表的速度，系统还配备了一组正好能容纳一个页表的硬件寄存器，这样当系统再访问虚存时，就首先到这组硬件寄存器中去访问，系统速度就快多了。这组存放当前页表的寄存器叫做快表。工作过程如下图：

缺页中断

在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放入就绪队列。

若该页面在内存期间被修改过，要将其写回外存。

缺页中断是因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此属于内中断。一条指令在执行期间，可能产生多次缺页中断。

多级页表

两极页表:32-bit机器上，每个进程地址空间为(2^32^)B,页长4KB，则页表最长将到达(2^20^)1M个项。若每个页表项占4B，则存放这张表将需要连续的4MB连续内存。而且每个进程的页表都可能这么大。

于是我们可以将这张长页表划分为多个“页表页”（也就是将这张长页表拆开，然后再搞一张页表，这个页表存的是这张长页表被拆开之后各个片段的编号（地址））,这样可以使得页表页也离散地、尽量地占用内存，甚至仅部分装入内存

在寻址的过程中，根据p1找到根页表页，根页表中的值再拿去查询内存中的块号（帧号），查到了之后就得到了真正存储想要数值的页表，然后根据页内偏移定位数值。

Linux系统使用了三级页表结构：页目录（Page Directory，PGD）、中间页目录（Page Middle Directory，PMD）、页表（Page Table，PTE）

页面置换算法

页面的换入、换出需要磁盘I/O，会有较大的开销，因此算法追求更少的缺页率。

OPT算法(最佳置换)

淘汰那些永不再使用或者下次访问距当前时间最长的页面

最佳，但不可实现，用于衡量其它置换算法性能

LRU算法(最近最久未使用算法)

淘汰在最近一段时间内最近未使用的一页。

实现: 可为每页添加“上次访问时间戳”，空间开销大。以过去预测将来，最近使用过的页可能很快被再次使用，很久未用的页可能不会被立即使用

FIFO算法(先入先出算法)

淘汰驻留内存时间最久的一页。

实现：将页面按调入内存的时间先后排成一个队列,每次将淘汰队首页，性能差

Belady异常现象：通常,帧越多则缺页次数越少，但FIFO算法中，有时，帧越多反而缺页率越高

简单时钟算法

为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出;如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描)

时钟算法改进

简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。
因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/O操作。这就是改进型的时钟置换算法的思想。修改位=0，表示页面没有被修改过;修改位=1，表示页面被修改过。

为方便讨论，用（访问位，修改位）的形式表示各页面状态。如（1，1）表示一个页面近期被访问过，且被修改过。

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

抖动

刚刚换出的页面马上又换入主存，刚刚换入的页面马上又换出主存，这种频繁的页面调度行为称为抖动或颠簸。

原因

抖动发生的主要原因是，进程频繁访问的页面数目高于可用的物理页帧数目，即分配给进程的物理块不够。所有进程工作集的帧需求总量 > 内存帧数

解决方案

抖动时，挂起 一 些进程，释放它们的帧

预防抖动

1. 在调度程序中引入工作集算法：当各进程的内存驻 留集足够大时，才调入新作业。
2. L=S 准则：调整并发度，使得 产生缺页的平均时间 ( 即缺页中断之间的平均时间 ) 等于处理一次缺页中断的平均时间 ，此时 CPU 利用率最高。
3. 50%准则：磁盘利用率50%时，CPU利用率最高。
4. 采用局部置换：只在本进程的内存范围内置换。
5. 当系统并发度较高时，挂起若干进程 （如优先级最低的、最年轻的、发生缺页的、占空间最少的、占空间最多的、剩余运行时间最长的进程