第三章：存储管理¶

存储器的体系结构¶

读取过程——应该是逐级的

3.1 单道程序存储管理¶

内存分为两个区域：系统区和用户区。【软件区分的】

每次把一个应用程序装入到用户区运行，由它和操作系统来共享内存。当它运行结束后，操作系统再装入一个新的程序把它覆盖。

优点：简单

缺点：

• 每次只能运行一个程序
• 内存资源的使用效率不高——程序较小时，会浪费大量的内存空间
• OS的保护——应用程序的bug会破坏OS
• 地址空间有限——即为物理内存的大小

3.2 分区存储管理¶

• 内存分为两大区域：系统区、用户区。

• 又把用户区划分为若干分区（partition），一个进程占用一个分区。

固定分区¶

各个用户分区的个数、位置和大小一经确定，就固定不变。

• 分区方法：多个小分区，适量中等分区，少量大分区

• 数据结构：内存分配表

• 内存分配：进入输入队列；按照最先匹配，最佳匹配算法分配

• 内存回收：简单啊

缺点：

• 内碎片：进程所占用分区之内未被利用的空间
• 不够灵活
• 不能预测分区代价

可变分区¶

• 初始时，操作系统会占用内存的一部分，剩余空间为一个完整的大空闲区
• 当一个程序要求装入内存运行时，系统从这个空闲区中划一块分配给它
• 当程序完成后释放所占用的存储区
• 随着一系列的内存分配和回收，原来的一整块大空闲区就形成若干占用区和空闲区相间的布局。

缺点：

• 内碎片减少
• 外碎片增多，即各个占用分区之间难以利用的空闲分区增多；
  • 使得内存的分配、回收和管理更为复杂。

可变分区的实现¶

内存管理的数据结构¶

分区链表

记录：

• 分区的状态（占用或空闲）
• 起始地址
• 长度
• ...

内存的分配算法¶

遍历，满足条件，分割

内存的回收方法¶

将相邻的几个空闲分区合并为一个大的空闲分区

碎片问题的解决¶

实例¶

假设堆空间的大小是固定的（一整块内存），请问如何来实现堆空间的管理？

动态申请固定大小的数据结构或缓冲区，如64B、9KB、64KB、256KB、400KB等；

使用malloc/free函数动态申请和释放任意大小的堆空间。

内存中的程序执行¶

进程的地址空间（？）

/* 全局变量，固定地址，其他源文件可见 */
int global_static;
/* 静态全局变量，固定地址，但只在本文件中可见 */
static int file_static;
/* 函数参数：位于栈帧当中，动态创建，动态释放 */
int foo(int auto_param) // 代码
{
  /* 静态局部变量，固定地址，只在本函数中可见 */
  static int func_static;
  /* 普通局部变量，位于栈帧当中，只在本函数可见 */
  int auto_i, auto_a[10];
  /* 动态申请的内存空间，位于堆当中 */
  double *auto_d = malloc(sizeof(double)*5);
  return auto_i;
}

内存空间：

• header（符号表？）——里头到底有什么？

• text section（代码段）

• data section（静态变量）
• other sections（堆栈）

3.2.6 地址映射¶

物理地址：可以直接寻址

逻辑地址：相对地址，相对首地址来编址

地址映射：逻辑地址转换为物理地址

• 静态地址映射（静态重定位）：装入内存时，修改指令代码

• 动态地址映射（动态重定位）：程序运行过程中，需要访问内存时进行地址转换（即在逐条执行指令时完成转换）。由硬件地址映射机制完成。

3.2.7 存储保护¶

防止

• 操作系统免受用户程序的破坏：

• 一个用户程序去访问其他用户程序的内存分区

物理限制：

• 增加一个限长寄存器，记录分区长度

3.3 页式和段式存储管理¶

3.3.1 页式存储管理¶

物理页面/页框（page frame）：物理内存划分为许多个固定大小的内存块 逻辑页面，或简称页面（page）：把逻辑地址空间划分为大小相同的块

页面大小为2n，一般在512字节到64K字节之间

一个进程需要的 n 个逻辑页面可以存储在不连续的 n 个物理页面中

页表：数据结构，逻辑页号 → 物理页号

但是，页表在内存中，不可能为了去取一条指令而花费一次读内存的时间；

所以必须要用硬件加速！

物理页面表：位示图 ~ 空闲物理 page frame 的链表；同时维护总共空闲页数

内存的分配与回收：trivial

地址映射：高位就是页号，低位就是页内偏移量；

页表的具体实现：PCB中设置 PTBR(base), PTLR(length）存储指针， ；都存在内核空间的内存中【1次寄存器+2次内存】

加速【主要是内存访问】：TLB，存储一个类似map的东西，TLB miss 的时候才去内存找

缺点：每个进程都要维护一张页表；必须把程序全部装入内存

3.3.2 段式存储管理¶

存储保护：

• 代码段——只读、可执行
• 数据段——可读写、需写回磁盘
• 栈——运行期间数据

如何跨进程的共享？

对程序的每个逻辑单元（代码、数据和栈等），设立一个完全独立的地址空间，称为“段”。

每个段的内部是一维的线性连续地址，大小可不同；

对于物理内存来说，采用可变分区（动态分区）的管理方法；

当一个程序需要装入内存时，以段为单位进行分配，把每一个段装入到一个内存分区【之前的分区方法】当中，这些内存分区不必是连续的。

用户空间地址：二维，段号+段内偏移

段表：每个进程都有，它给出了每一个段和它所对应的内存分区之间的映射关系【起始地址、长度】→ 寄存器【STBR，STLR】

3.3.3 段页式存储管理¶

先把程序划分为段【内存划分】，然后在段内分页【内存存储】。

1. 段表：页表起始地址 & 段长
2. 页表：逻辑页面号与物理页面号之间的对应关系。【每一段有一个】

3.4 虚拟存储技术¶

内存不够用的情况，把内存扔到磁盘里面

局部性原理——

只装入部分页面

增页、页面置换

页表项，增加一个驻留位：是否在内存中；一个访问位 ：是否被访问过：用于页面置换算法

缺页中断不能加 PC，刚才的指令根本没有执行完成

淘汰页面的算法¶

最优页面置换：选择未来等待时间最长的

最近最久未用：选择最近最久未使用的那个页面

最近最少使用：选择访问次数最少的那个页面

先进先出置换：选择驻留时间最长的页面

时钟页面置换算法：基本思路（FIFO + 跳过已访问过的页面）

3.4.4 工作集模型¶

证明、定量分析程序的局部性原理

工作集¶

工作集：一个进程当前正在使用的逻辑页面集合，可以用一个二元组 \(W(t,\Delta)\) 来表示， \(t\) 是当前的执行时刻，\(\Delta\) 定长的窗口

工作集大小变化：【快速扩张-快速收缩-稳定期】* 每一个局部性区间

进程固有性质

驻留集¶

实际在内存中的逻辑页面集合

取决于物理页面数目和页面置换算法。

一般我们希望缺一点， |驻留集| < |工作集|

3.4.5 虚拟页式的设计问题¶

1. 页面的分配策略

固定分配：驻留集大小固定

可变分配：调整驻留集的大小，可以根据缺页率等等调整

1. 页表结构

多级页表

反置页表：根据物理块来维护下标

Windows 的存储管理¶

每个进程的虚拟地址空间大小为 32 位，4G

低 2G 是用户空间，用于存放进程自身的代码和数据

高 2G 是内核空间，虚拟页式存储管理，页面大小为 4 KB

二级页表进行映射

页面置换算法：努力去维持一定量的空页表；算法平时会定期向着各个进程索取页面

Linux 的存储管理¶

虚拟页式存储

四级页表结构