【操作系统（一）】虚拟内存

本文内容总结于《操作系统概念》 Peter Baer Galvin . Greg Gagne 著&＃xff0c; 郑扣根 译
这本书讲的很详细&＃xff0c;翻译的也很好&＃xff0c;非常的全面&＃xff0c;拿来用来学习操作系统足矣。
在未来的 2-3 月内&＃xff0c;我将以此书为向导&＃xff0c;以内核源码为依托&＃xff0c;对操作系统刨根问底。

本系列文章与我的内核源码与Android系列分析与解读 系列文章相辅相成。感兴趣的人可以多翻阅。

操作系统简述这个文档只是对操作系统的简单的总结。

• 使用虚拟内存&＃xff0c;每个进程都有属于自己的虚拟地址空间&＃xff0c;显著优点就是程序可以比物理内存大。同时将用户看到的逻辑地址和物理内存分开。允许程序员不受内存存储的限制。也允许进程间共享文件和地址空间&＃xff0c;还为创建进程提供了有效机制。

1. 背景

很多情况下不需要将程序都加载到物理内存。

优点&＃xff1a;

• 程序不再受物理内存空间限制。
• 每个用户程序使用更少的物理内存&＃xff0c;更多的程序可以同时执行&＃xff0c;CPU使用率也相应增加&＃xff0c;响应时间和周转时间并不增加。
• 载入或交换每个用户程序到内存所需的IO会更少&＃xff0c;用户程序会运行更快。

虚拟内存将用户逻辑内存和物理内存分开&＃xff0c;需要内存管理单元MMU将逻辑页映射到内存的物理页帧。

虚拟内存也允许文件和内存通过共享页而为两个或多个进程所共享。

• 通过共享对象映射到虚拟地址空间&＃xff0c;系统库可为多个进程所共享。
• 虚拟内存允许进程共享。&＃xff08;通过共享内存&＃xff09;
• 虚拟内存允许在系统调用fork&＃xff08;&＃xff09;创建进程期间共享页&＃xff0c;从而加快进程创建。

2. 按需调页&＃xff08;demand paging&＃xff09;

当需要执行进程时&＃xff0c;将所需要的页从磁盘交换至内存&＃xff0c;使用懒惰交换&＃xff08;lazy swapper&＃xff09;。将所需要的页通过调页程序加载至内存。

**首先需要区分哪些页在内存&＃xff0c;哪些在磁盘。**页表的有效位和无效位&＃xff08;valid-invalid&＃xff09;可以用于这一目的。当该位设置为有效时&＃xff0c;该值表示相关的页既合法且也在内存中。当该位设置为无效&＃xff08;也就是&＃xff0c;不在进程的逻辑地址空间内&＃xff09;&＃xff0c;或者有效但是在磁盘上。对于调入内存的页&＃xff0c;其页表条目的设置和平常一样&＃xff1b;但是对于不在内存的页&＃xff0c;其页表条目设置为无效&＃xff0c;或包含该页在磁盘的地址。

**对标记为无效的访问会产生页错误陷阱&＃xff08;page-fault trap&＃xff09;。**分页硬件&＃xff0c;在通过页表转换地址时&＃xff0c;将发现已设置了无效位&＃xff0c;会陷入操作系统。这种陷阱是由于操作系统未能将所需的页调入内存引起的。处理这种页错误的程序比较简单。

1. 检查进程的内部页表&＃xff08;通常与PCB一起保存&＃xff09;&＃xff0c;以确定该引用是合法还是非法的地址访问。
2. 如果引用非法&＃xff0c;那么终止进程。如果引用有效但是尚未调入页面&＃xff0c;那么现在应调入
3. 找到一个空闲帧&＃xff08;从空闲帧链表中选一个&＃xff09;。
4. 调度一个磁盘操作&＃xff0c;以便将所需要的页调入刚分配的帧。
5. 当磁盘读操作完成后&＃xff0c;修改进程的内部表和页表&＃xff0c;以表示该页已在内存中。
6. 重现开始因陷阱而中断的指令。进程现在能访问所需的页&＃xff0c;就好像它似乎总在内存中。

按需调页的性能&＃xff1a;

页的错误率为&＃xff1a;P&＃xff08;0~1&＃xff09;
有效访问时间&＃xff1a; &＃61; &＃xff08;1-p&＃xff09; * ma &＃43; p x 页错误时间。

ma 指 内存访问时间。

其中页错误时间为8ms&＃xff0c; 性能降低不超过10%&＃xff0c; p <0.0000025

2. 写时复制&＃xff08;copy on write&＃xff09;

写时拷贝技术&＃xff0c;最先看到这个名词时是在看fork技术的时候。讲的时由于fork子进程创建为父进程的复制品&＃xff0c;但是子进程在创建之后通常会马上执行系统调用exec(), 所以这种复制进程地址空间没有必要。
写时复制允许父子进程共享页面&＃xff0c;这些页面被标记为写时复制页&＃xff0c;即如果任何一个进程需要对页进行写操作&＃xff0c;那么就创建一个共享页的副本。

3.页面置换

页置换&＃xff1a; page replacement &＃xff08;当页面过度分配时&＃xff0c;会产生没有空闲帧&＃xff0c;所有内存都在使用&＃xff0c;此时可以终止进程&＃xff0c;也可以交换出一个进程。更常用的方法是页置换。&＃xff09;

为了实现按需调页&＃xff0c;必须解决两个问题&＃xff1a; 帧分配算法&＃xff08;frame-allocation algorithm&＃xff09;和页置换算法&＃xff08;page-replacement algorithm&＃xff09;。 这里重点说页置换算法。

指标&＃xff1a; 最小的页错误率&＃xff01;&＃xff01;&＃xff01;&＃xff01;

1. FIFO &＃xff1a; 性能并不总是很好&＃xff01;

Belady异常&＃xff1a; 帧数越多页错误率反而越高。。。。页错误率可能会随着分配的帧数的增加而增加&＃xff0c;原期望为增加内存会改善其性能。

2. 最优置换算法&＃xff08;OPT optimal page-replacement algorithm&＃xff09;

置换出最长时间不会使用的页&＃xff01;

弱点&＃xff1a; 难以实现。常用来比较&＃xff01;

3. LRU页置换&＃xff08;Least-recently-used algorithm&＃xff09;

• 最近最少使用算法。可使用1. 计数器实现&＃xff08;记录时间戳&＃xff09; 2. 栈
• 注意&＃xff0c;如果只有标准TLB寄存器而没有其他硬件支持&＃xff0c;这两种LRU实现都是不可能的。每次内存引用都必须更新始终域或栈。如果对每次引用都采用中断&＃xff0c;以允许软件更新这些数据结构&＃xff0c;那么它就会使内存引用慢至少10倍&＃xff0c;进而使用户进程慢10倍。几乎没有系统可以忍受如此程度的内存管理开销。

4. 近似LRU页置换

   1. 附加引用位算法
      内存页表中的页保留8位的字节。从高位开始置位&＃xff0c;将其他位向右移动&＃xff0c;并抛弃最低位。所以这8位移位寄存器包含着该页在最近8个时间周期内的使用情况。值为11000100的移位寄存器的页要比值为01110111的页更为最近使用。具有最小值的页为LRU页&＃xff0c;可以被置换。
   2. 二次机会算法
      基本算法是FIFO置换算法。当选择一个页时&＃xff0c;引用位为0&＃xff0c;则直接置换此页&＃xff0c;否则给其第二次机会&＃xff0c;并选择下一个FIFO页。当一个页获得第二次机会时&＃xff0c;其引用位清零&＃xff0c;其到达时间设为当前时间。
   3. 增强型二次机会算法
      通过将引用位和修改位作为一个有序对来考虑&＃xff0c;可以改进二次机会算法。每个页有以下四种可能类型。
      1. &＃xff08;0&＃xff0c; 0&＃xff09;最近没有使用也没有修改----用于置换的最佳页
      2. &＃xff08;0&＃xff0c; 1&＃xff09;最近没有使用&＃xff0c;但修改过----不是很好&＃xff0c;因为在置换之前需要将页写出到磁盘。
      3. &＃xff08;1&＃xff0c; 0&＃xff09;最近使用&＃xff0c;但没修改----他很有可能再次被使用
      4. &＃xff08;1, 1&＃xff09;最近使用&＃xff0c;并修改----很有可能再次被使用&＃xff0c;在置换之前需要将页写出到磁盘。

这种方法与简单时钟算法的主要差别是&＃xff0c;给那些已经修改过的页以更高的级别。从而降低了所需 I/O 的数量。

5. 基于计数的页置换算法

   1. 最不经常使用页置换算法&＃xff08;least frequently used &＃xff08;LFU&＃xff09;page-replacement algorithm&＃xff09;&＃xff0c;要求置换计数最小的页。可能有很多页在开始时大量使用&＃xff0c;之后不再使用&＃xff0c;可以定期地将次数寄存器右移一位&＃xff0c;以形成指数衰减的平均使用次数。
   2. 最常使用页置换算法&＃xff08;most frequently used (MFU&＃xff09; page-replacement algorithm), 具有最小次数的页可能刚刚调进来&＃xff0c;且还没有使用。

这两种算法都不常用&＃xff0c;很费时&＃xff0c;不能很好地接近OPT置换算法。