第9讲 存储器管理(2)⚓

1. 非连续分配存储管理⚓

使用连续存储管理技术时，进程在内存中必须连续存放，使进程受到可用连续内存容量的限制。非连续分配技术：运行时将一个进程的程序和数据离散存储在多个独立的分配单位中。包括：页式，段式，段页式。

(1) 页式

将物理内存划分为固定大小的块，称为页 page，操作系统将进程的逻辑地址空间划分为同样大小的页。以页为单位实现内存的分配和回收，通过页表实现逻辑地址到物理地址的转换。

按照是否支持虚拟内存，分为实存页式存储管理和虚拟页式存储管理。实存页式存储管理应用场景主要是嵌入式系统，现代通用操作系统一般采用虚拟页式存储管理。

(2) 段式

将程序和数据划分为逻辑上独立的段 segment，每个段代表一个功能单元，如代码段、数据段、堆栈段等。不同的段在物理内存中不需要连续。该技术已经过时。

(3) 段页式

段页式 Segmentation with Paging ，结合分段和分页两种技术。

分段：按程序逻辑（如代码、数据、堆栈等）划分内存，每段独立管理。

分页：将每个段进一步划分为固定大小的页，物理内存按页分配。

现代处理器中，采用段页式的架构主要是 x86。其他主流架构，包括 ARM, RISC-V, MIPS，通常采用纯分页管理。

2. 实存页式存储管理⚓

也称为简单分页。进程加载时，以页为单位进行分配，并按进程的页数多少来分配。逻辑上相邻的页，物理上不一定相邻。

逻辑页号和物理页号都是从0开始编址，页内地址相对于0编址。页的划分是由系统自动完成的，对用户透明。

为区分程序逻辑地址空间的页，物理内存的页通常称为页框(page frame)。

进程页表：在逻辑页与物理页框之间建立起对应关系，实现逻辑页号(本进程的地址空间)到物理页框号(实际内存空间)的映射关系。页表位于内存中。

物理页框表：描述物理内存空间的分配使用状况，数据结构为位图或空闲页面链表。

请求表：描述系统内各个进程页表的位置和大小，用于地址转换，也可以结合到各进程的PCB里。

页表寄存器(Page-Table Register，PTR)中存有页表在内存的首地址和页表长度(即页数)。

地址转换：

1. 逻辑地址=逻辑页号+页内偏移。地址化成二进制之后可以直接看出“逻辑页号+页内偏移”。
2. 判断是否越界中断。
3. 物理地址=物理页框号+页内偏移。

内存管理单元 MMU(Memory Management Unit)，管理硬件页表寄存器、分解逻辑地址、访问页表、管理快表 TLB。

一般而言，采用分页存储管理使，CPU 访问内存需访问两次：访问页表、访问内存中的内容。为提高速度，增设一个具有并行查询能力的特殊 Cache，称为 TLB(Translation Lookaside Buffer)，用以存放当前访问的那些页表项。

具有快表的地址转换：

1. 根据逻辑地址中的页号，查找快表 TLB 中是否存在对应的页表项。
2. 若快表中存在该表项，称为命中，取出其中的页框号，加上页内偏移量，计算出物理地址。
3. 若快表中不存在该页表项，称为缺失。再查找页表，找到逻辑地址中指定页号对应的页框号，同时更新快表，将该表项插入快表中，并计算物理地址。

基于实存的页式存储管理：

(1) 优点：

1. 没有外碎片，每个内碎片不超过页大小。
2. 一个程序不必连续存放。
3. 便于改变程序占用空间的大小，即随着程序运行而动态生成的数据增多，地址空间可相应增长。

(2) 缺点：

1. 作业虽然不占据连续的存储区，但每次仍要求一次全部进入内存。因此，如果作业很大，其存储需求大于内存，存在小内存不能运行大作业的问题。
2. 存在内碎片。
3. 难于实现共享。

3. 虚拟页式存储管理⚓

虚拟存储器：在具有层次结构存储体系的计算机系统中，采用自动实现部分装入和部分交换功能，为用户提供一个独立于物理内存容量的、可寻址的“存储器”。

进程虚拟地址空间的大小由处理机的地址结构所决定，与主存大小并无直接关系。虚拟存储器以辅助存储器作为后备存储器。

工作原理：以大容量的辅助存储器做后备存储器。把进程保存在后备存储器上，当要求装入时，只将其中一部分先装入主存，另一部分暂时存放在后备存储器上，要用到那些不在主存中的信息时再装到主存中。进程不全部装入主存的情况下也能够正确执行，这由存储器的局部性原理保证。

优点：

1. 大程序：可在较小的可用内存中执行较大的用户程序。
2. 大的用户地址空间：提供给用户可用的虚拟内存空间可以大于物理内存或实存(real memory)。
3. 并发：可在内存中容纳更多程序并发执行。

缺页中断：程序执行过程中，如果需执行的指令或访问的数据尚未在内存，由处理器通知操作系统执行缺页中断处理程序，将相应的页调入到内存，然后继续执行程序。

虚拟页式存储管理是在实存页式存储管理的基础上，增加调页和页面置换功能。需要在进程页表中添加若干项：

1. 标志位：存在位 present bit、修改位 modified bit。
2. 访问统计：在近期内被访问的次数，或最近一次访问到现在的时间间隔。
3. 外存地址。

MMU：

1. 管理硬件页表寄存器。
2. 分解虚拟地址。
3. 访问页表。
4. 管理快表 TLB。
5. 设置和检查页表中各个特征位。
6. 发出缺页中断，并将控制权交给内核存储管理处理。

页面置换算法⚓

(1) 最优页面置换算法 OPT

选择未来不再使用的或在离当前最远时间才使用的页面被置换。这是一种理想情况，实际执行中无法预知，因此无法实现，但可用作性能评价的依据。

(2) 最近未使用页面置换算法 NRU

随机地从编号最小的非空类中挑选一个页面淘汰之。

(3) 先进先出页面置换算法 FIFO

选择最老的页面，可以通过链表来表示各页的装入时间先后。

缺点：性能较差，较早调入的页往往是经常被访问的页，在 FIFO 算法下可能被反复调入调出。存在 Belady 异常：如果对一个进程未分配它所要求的全部页，有时会出现分配的页框数增多，缺页率反而提高的异常现象。

(4) 第二次机会页面置换算法

对 FIFO 的改进，检查最老页面的 R 位，如果为1（表示最近被访问过），清除该位，并将该页放到链表的末尾。继续检查下一个页面直到找到一个访问位为0的页面进行置换。

(5) 时钟页面置换算法 Clock

逻辑上与第二次机会页面置换算法等价。

(6) 最近最少使用页面置换算法 LRU

选择最久未使用的页面被置换。是局部性原理的合理近似，性能接近最佳算法。但由于需要记录页面使用时间的先后关系，硬件开销较大。

硬件结构实现1：硬件有一个计数器 C(足够长，例如64位)，每条指令执行后自动增1。每个页表项有一个能够容纳计数器值的域。每次访问内存后，当前 C 值被复制到被访问页面的页表项中。页表项的计数值最小的页面就是最近最少使用的。

硬件结构实现2：对于有 n 个页框的机器，LRU 硬件可以维护一个 \(n\times n\) 矩阵，初值为0。访问页框 k 时，先把 k 行的位都置1，再把k列的位都清0。任何时刻，二进制值最小的行就是最近最少使用的。

(7) 最不常用页面置换算法 NFU

将每个页面与一个软件计数器相关联，每次时钟中断时，将页表项的 R 位加到计数器上。发生页面失效时，计数器值最小的页面被置换。

(8) 老化算法 aging

对 NFU 算法的改进。在 R 位被加进之前先将计数器右移一位，然后将 R 位加到计数器的最左端。发生页面失效时，计数器值最小的页面被置换。

工作集(working set)：一个进程当前正在使用的页面的集合。用二元函数 \(W(k, t)\) 表示在时刻 t 所有最近 k 次内存访问所用过的页面。

进程开始执行后，随着访问新页面逐步建立较稳定的工作集。当内存访问的局部性区域的位置大致稳定时，工作集大小也大致稳定；局部性区域的位置改变时，工作集快速扩张和收缩过渡到下一个稳定值。

工作集的一种近似：用二元函数 \(W(k,\tau)\) 表示工作集， \(t\) 为当前时刻， \(\tau\) 是一个虚拟时间段，称为窗口大小(window size)，工作集是 \([t-\tau,t]\) 时间段内所访问的页面的集合。

采用工作集策略的困难在于操作系统要经常监视活动进程的行为和进程缺页中断率的情况，会增加系统的开销。

页面置换算法小结：

实存页式 VS. 虚拟页式：

Comments