引言：操作系统中的存储器管理； 更新：增加《CSAPP》中的知识点内容

存储器管理

操作系统很重要的一个工作，完成对存储器的控制与管理

存储技术

RAM

RAM（Random Access Memory）随机访问存储器

分为两类：静态与动态

SRAM

SRAM（Static RAM）：静态RAM

所谓静态RAM，我认为静态的意思就是指其实现比较稳定：

结构特点：

​ 其每一位都存放在一个双稳态的存储器单元内（这个存储器单元是由6个晶体管电路来实现的，具体实现无需了解）

这种单元有这样一个特性：

• 无限期的保持在两个不同的电压状态之一（即：不存在中间状态，要么是0，要么是1，任何一点点干扰都会使其偏向一边）

（《CSAPP》中说到SRAM使用了一个倒摆来阐述这个特性）

注意：

1、这里的稳定，会在断电之后失效，所以SRAM会在断电后丢失数据

2、也可以这么理解，只要有电SRAM就会永远保证其值不会发生变化

DRAM

Dynamic RAM：动态RAM

结构特点：其每一位都依靠一个电容来进行存储，每个单元都由一个电容和一个访问晶体管组成，相对于SRAM，DRAM就不是稳定的了：

• DRAM对干扰非常敏感，比如光照就可以让DRAM的电容改变

（基于这个特性，数码照相机中的传感器就是DRAM实现的）

DRAM不稳定，那它怎么去存数据？

​ DRAM不稳定，但是他可以保证在10-100ms的时间内不改变，而CPU的时钟周期是纳秒级别的，所以对于CPU来说，DRAM足够稳定能存储数据了

（可以这么理解，比如使用白纸黑字来记录数据，虽然数据不能永远存在，但对于人来说，已经足够使用了）

SRAM与DRAM的对比

种类	晶体管数/单元	相对访问时间	是否稳定	是否敏感	相对花费	应用
SRAM	6	1x	稳定	不敏感	1000x	高速缓存
DRAM	1	10x	不稳定	敏感	1x	主存，相机传感器

注意到：

• SRAM速度大约是DRAM的10倍，而花费却是其1000倍
• 高速缓存就是SRAM构成的
• 主存就是由DRAM构成的

传统DRAM的结构实现

上面相当于简单介绍了一下DRAM，这里具体介绍一下DRAM的结构

结构：

• DRAM芯片
  • 一个DRAM芯片由d个超单元组成（每个超单元可以传输1字节的信息）
  • 一个超单元由w个DRAM单元组成（每个DRAM单元可以传输1bit信息）
  • 超单元为一个方阵，r行，c列（d = r*c）
  • addr：代表地址线，图中有两根，所以可以指向4位的地址
  • data：代表数据选，图中有8根，所以一次可以传输1字节信息（一个超单元）
  • 内部行缓冲区（下面会举一个例子）
• 内存控制器：两个功能
  1. 可以一次传入或传出w位
  2. 可以给DRAM芯片发送行地址RAS与列地址CAS

如何从DRAM（主存）读取一个数据？

还是这个图，现在我们要从中读取（2,1）位置的数据

CPU传来地址，要读取（2,1）的数据，那么内存控制器地址线传输地址，会先传输行地址2，在传输列地址1（分两次传输）

a）传输行地址2：此时读取行号为2的整行数据，读入到内部行缓冲区

b）传输列地址1：从内部行缓冲区读取列为1的数据，通过数据线返回

（此处使用CSAPP中的图）

为什么要设计DRAM芯片为二维结构？

这里涉及到一个折衷的问题：

• 设计为4*4的结构：地址线使用2根即可，但是要传输行与列，意味着取一个数需要传入两次地址

• 设计为1*16的结构：地址线需要4根，但是读一个数据，一次就可以读取到

内存模块

现在我们已经知道了DRAM芯片的构成，再向上抽象，DRAM芯片是构成内存模块的组成部分：

​ 可以看到此处的内存模块由8个DRAM芯片构成，每次读取数据时，会将相同的行列传到每一个DRAM芯片中，然后每一个DRAM芯片都会返回对应超单元的数据，分别组成数据的不同高度的位

这样，就实现了一次读取64位的数据

内存控制器

此处我们总结一下内存控制器的作用：

1、翻译地址：可以将CPU传来的地址，翻译为DRAM芯片的行与列

2、多播：将行地址与列地址传输到每一个DRAM

3、组合数据返回：将每一个DRAM芯片读出来的数据，组合起来，返回给CPU

ROM

ROM（Read Only Memory）只读存储器

由于历史原因，称为只读存储器，但其实有的类型是可读可写的

分类：

• PROM（Program ROM）：可编程ROM，只能被写一次；（内容原理是每一个单元都是一个熔丝，只能被高电流熔断一次）
• EPROM（Erasable PROM）：可擦写可编程ROM，允许1k次的重复写操作；（其实现原理是EPROM有一个石英窗口，允许紫外线进入，当紫外线照射到存储单元时，对应位置就变为0）
• EEPROM（Electrically EPROM）：电子可擦除ROM（直接在印制的电路卡上编程，可达10w次重写操作）
• Flash Memory：闪存，其实现基于EEPROM（固态硬盘就是闪存的一种实现）

从CPU到主存

CPU是如何读取一个数据到寄存器的呢？

例如命令

movq A, %rax
-- 此处的A代表一个地址，这种寻址方式也叫直接寻址

要知道这个问题，我们先得大致了解CPU的指令是如何传递到主存的，如图：

结构：

• CPU芯片内部有对外的总线接口
• 系统总线：连接IO桥与CPU
• 内存总线：连接IO桥与主存

作用：IO桥负责将系统总线的电子信号转换为内存总线的电子信号

movq A, %rax
-- 此处的A代表一个地址，这种寻址方式也叫直接寻址（movq的q代表读取一个64位的数据）

此命令在执行中，就分为三个过程

1. CPU总线接口将A通过系统总线——IO桥（完成电子信号转换）——内存总线传递到主存
2. 内存控制器将地址翻译为DRAM地址，取数据，传回
3. 总线接口读出数据，放入CPU寄存器中

磁盘（机械硬盘）

磁盘的结构

要了解清楚几个概念：盘片、盘面、磁道、柱面、扇区

---

一个机械硬盘内部的主要结构有：主轴、磁头、盘片

间隙用来作为扇区与扇区之间的分隔符

盘片会绕着主轴进行旋转，磁头可以在最内圈到最外圈之间摆动（这是机械运动，所以磁盘的读取速度十分缓慢）

机械硬盘内部是真空密封的，打开就不能使用了，为什么？

“读写头在磁盘表面一层薄薄的气垫上飞翔”，这个厚度很薄，即使很小的一粒灰尘，对于磁头来说都相当于摩天大楼，会发生读写头碰撞(head crash)

有以下转换公式：

1盘片 = 2 盘面 = 2*k 磁道 = 2*K*n 扇区 = 2*K*n*512 字节

• 一个盘片的两面都刷油磁性介质，都可以存储数据
• 磁道是一个圈（图中画的密度很均匀，但其实实际上不是均匀的）
• 柱面就是很多个盘片相同的磁道组成的一个面

一个磁盘可以存储的数据大小公式：

磁盘容量 = 每扇区字节数 * 每磁道扇区数 * 每盘面磁道数 * 2 * 盘片数

其中每磁道扇区数也可以换为每盘面柱面数，这两个值是相同的

磁盘格式化

一个新的磁盘是不能使用的，我们需要首先进行格式化

格式化主要做的内容有：

• 用标识扇区的信息填写扇区之间的间隙
• 标识出有故障的柱面并且不使用
• 每个区要预留一组柱面作为备用

如果你使用Linux挂载过磁盘，那么其中一步就是格式化磁盘，换成可以使用的文件格式。

磁盘如何存储数据

磁盘的数据存放在了扇区内（一般一个扇区512字节）

对于一个文件来说（磁盘通过这样的方式尽可能的优化查询时间）

先会存放在一个扇区内，如果不够，就存放在同一个磁道内，如果还不够，就存放在同一个柱面内，如果还不够，就放在相邻的磁道内

磁盘如何查找数据

磁盘查找数据主要分为三个部分：

• 寻道时间（磁头摆动到对应磁道的时间）
• 旋转时间（磁盘旋转到期望扇区所需的时间，最坏的情况就得转一圈）
• 传送时间（读取一个扇区所需要的时间）

首先磁盘需要定位到对应磁道（此时磁臂会进行摆动），定位后要找到期望的扇区（磁盘疯狂旋转，会转到文件的开始位置），然后磁头开始读取对应位置的数据。

磁盘调度算法

考虑的就是使得平均寻道时间最短

例如：假定磁盘有 200 个磁道，当前有 9 个访问者（进程）先后提出 I/O 操作，需要访问的磁道分别为：55，58，39，18，90，160，150，38，184；又假定当前磁头位置为 100

先来先服务 / 先进先出

优点：公平

缺点：未考虑优化寻道，有大量进程访问者竞争一个磁盘，则这种算法的性能接近于随机调度

最短寻道时间优先（SSTF）

选择使磁头臂从当前位置开始移动距离最短的 I/O 访问者

缺点：每次选择距离最短者同时，忽略了可能由于不断的有新的 I/O 请求进程加入到队列中，且与当前磁头位置较近，会使得原请求队列中的距离远的访问者总也得不到调度，产生所谓 “饥饿” 现象

扫描算法 SCAN

考虑了两个方面的问题：

• 方向
• 与当前磁道号距离最短

作先由内向外运动，再由外向内运动，或反之。
这样就避免了饥饿现象。

由于这种算法使得磁臂移动规律颇似电梯的运动，因而也称为电梯算法。

缺点：

会导致某些请求会被延迟读写

循环扫描算法 CSCAN

为了减少这种延迟，**规定磁头单向读 / 写运动 (如只由内向外)，完成读写后立即返到最小 / 大磁道号的位置 (构成循环)**，再进行扫描。即 CSCAN 算法

磁盘控制器

磁盘的结构确实很复杂，但是磁盘设计厂商为我们做了一层抽象，以便于我们使用逻辑磁盘块

磁盘控制器：维护着逻辑块号与实际磁盘扇区的映射关系

如果OS要执行一个IO操作，读取磁盘的一个数据，那么OS就会发过来一个逻辑块号，然后磁盘控制器将其翻译为一个（盘面， 磁道， 扇区）的三元组

然后磁盘就会去对应位置读取数据，然后将其复制到OS内核的一个小的缓冲区中，然后OS再去缓冲区读取数据

固态硬盘

一种基于闪存存储技术的存储介质

固态硬盘的结构如下：

• 闪存翻译层（作用类似于磁盘控制器）
• 一个或多个闪存芯片
  • 一个闪存芯片由B个块组成
    • 一个块由P个页组成（一页大小约为512字节，类似于扇区）

固态硬盘的特点：

• 数据的读写是以页为单位读写的，如果要写一页，需要擦除该页所属的块
• 随机读要比随机写快

为什么写操作慢？

1. 写操作执行之前，需要擦除对应块的所有页的数据，才能进行写入
2. 如果要更改一页的部分数据，需要将这一页所属块的所有数据复制到一个新块后，才能对页进行修改

但即使这么复杂，也比磁盘要快很多，这也是固态硬盘贵和重要的原因

存储器的层次结构

如图：

• 其中主存储器与寄存器也被称为可执行寄存器
  • 对于可执行寄存器的访问：通过指令load与store
  • 对于辅存中的信息的访问：通过I/O中断机制
• 高速缓存和磁盘缓存是用来缓和主存与寄存器、辅存和主存之间速度差异过大的不匹配的问题的，都利用了局部性原理
• 寄存器与主存属于OS管理的部分，而辅存的管理属于设备管理

存储管理的目的

1. 主存的分配和管理

   当用户需要内存时，系统为之分配相应的存储空间；不需要时，及时回收，以供其它用户使用。

2. 提高主存储器的利用率

   不仅能使多道程序动态地共享主存，提高主存利用率，最好还能共享主存中某个区域的信息

3. “扩充”主存容量

   为用户提供比主存物理空间大得多的地址空间，以至使用户感觉他的作业是在这样一个大的存储器中运行

4. 存储保护

   确保多道程序都在各自分配到存储区域内操作，互不干扰，防止一道程序破坏其它作业或系统文件的信息。

程序的装入和链接

#include<stdio.h>
int main(){
    printf("hello world!");
    return 0;
}

从编写一个hello world的c程序，到运行它，中间存在这些过程：

1. 编译
2. 链接
3. 装入

程序的编译

编译之前，其实还有一步预编译的过程，在这个过程中，会识别#include<stdio.h>，告诉预处理器读取系统头文件stdio.h的内容，并将它直接插入到程序的文本中，结果就得到了另一个C程序，这个c程序以.i作为文件的扩展名

然后就开始进行编译过程，会将这个.i的程序翻译成.s的程序，这个程序是一个汇编语言程序，汇编器（例如as汇编器）会将这个.s文件翻译成真正的机器语言文件，结果产生一个.o文件，这个文件是一个二进制文件

程序的链接

此时我们有一个.o文件，注意我们的程序调用了printf函数，这个函数我们并没有实现，而是C编译器提供的标准C库的一个函数，这个函数存在于printf.o的单独预编译好了的目标文件中，我们必须将它与我们的程序进行合并

根据链接时间的不同，程序链接分成三种：

1. 静态链接
2. 装入时动态链接
3. 运行时动态链接

静态链接

一种事先链接方式，即在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装入模块(执行文件)，以后不再拆开

需要克服两个问题：

• 对相对地址进行修改
  • 各个地址都是从0开始计算的，假设有A、B、C三个模块，他们的长度分别为L、M、N，A调用了B，B调用了C，此时我们需要把B中的相对地址加L，C中的相对地址加L+M
• 变换外部调用符号
  • 把B的起始地址变为L，C的起始地址变为L+M（原本都是0）

静态链接后的文件就是可执行文件

存在问题：

1. 不便于对目标模块的修改和更新（如要更新其中一个模块，需要打开装入模块）
2. 无法实现对目标模块的共享

装入时动态链接

将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式。

优点：

1. 便于对目标模块的修改和更新，各个模块分开存放
2. 可以实现对目标模块的共享

存在问题：
由于程序运行所有可能用的目标模块在装入时均全部链接在一起，所以将会把一些不会运行的目标模块也链接进去。如程序中的错误处理模块。

运行时动态链接

对某些模块的链接推迟到程序执行时才进行链接。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上

程序的装入

由装入程序将装入模块装入内存中

装入方式有以下几种：

1. 绝对装入方式
2. 可重定位装入方式
3. 动态运行时的装入方式

绝对装入方式

这是一种早期的方式，早期的计算机很小，程序员可以直接操作绝对地址，程序编译后直接就是绝对地址（不需要进行逻辑地址与绝对地址的转换）

缺点：

• 只适用于单道程序环境
• 需要程序员熟悉内存
• 程序的地址都是绝对地址，修改麻烦，一个的改动可能会让全部地址都得改动

可重定位的装入方式

在多道程序环境下，目标模块中的其它地址都是相对于0编址。

应根据内存的当前情况，将装入模块装入到内存的适当位置。

通常是把在装入时对目标程序中指令和数据的修改过程称为重定位

例如，有一条指令load ax ,[2500]，将会把2500处的内容读取到ax寄存器中，此时的位置相对于0编址的，在程序被装入主存后，地址是从10000开始的，重定位就是此时将程序中的所有地址进行转换，将逻辑地址转换为绝对地址

物理地址 = 基地址 + 相对地址

注意：

• 地址转换在装入时一次完成，不再允许程序再次更改位置

动态运行时装入方式

实际情况中程序在运行过程中它在内存中的位置可能经常要改变，重定位就不能满足我们的要求

动态运行时装入方式：装入后并不立即将地址进行映射，而是将地址转换推迟到程序真正要执行的时刻

因此， 装入内存后的所有地址都仍是相对地址

注意：

• 需要重定位寄存器的支持

连续分配存储管理方式

连续分配存储方式：早期的一种分配方式，为每一个用户程序分配一段连续的内存空间（程序中代码或数据逻辑地址相邻，分配的物理地址也相邻）

连续分配方式可以分为四类：

• 单一连续分配
• 固定分区分配
• 动态分区分配
• 动态可重定位分区分配

单一连续分配

用于单用户、单任务的OS中。

核心：

• 将内存分为系统区（占内存低地址端）和用户区（占内存高地址端）
• 采用静态重定位分配方式
• 由装入程序检查其绝对地址是否越界，即可达到保护系统的目的。

特点：

• 简单
• 只需要小量软硬件支持

缺点：

• 内存空间浪费大，各类资源利用率也不高
• 程序运行受主存容量限制
• 不支持多道

固定分区分配

分区分配方式：将内存分成若干个分区（大小相等/不相等），除OS占一区外，其余的每一个分区容纳一个用户程序

分为两种：

• 固定分区存储管理
• 动态分区存储管理

固定分区存储管理方式：

将内存空间划分为若干个固定大小的分区，除OS占一区外，其余的一个分区装入一道程序。

注意：分区的大小可以相等，也可以不等，但事先必须确定，在运行时不能改变。

特点：

• 分区大小及边界在运行时不能改变
• 需要建立一张分区说明表或使用表（区号、大小、起止、状态）

过程：

当某个用户程序要被装入时

1. 内存分配程序检索分区说明表
2. 若找到满足要求的分区即分配分区，修改说明表状态，否则拒绝
3. 当程序运行完毕，释放对应分区，同时修改说明表状态

特点：

• 管理简单
• 作业的大小并不一定与某个分区大小相等，从而使一部分存储空间被浪费，利用率低

例如：

动态分区分配方式

在作业进入内存时，根据作业的大小动态地建立分区，并使分区的大小正好适应作业的需要。

因此系统中分区的大小是可变的，分区的数目也是可变的。

特点：

• 管理简单
• 利用率有所提高

核心：

• 空闲分区表
• 空闲分区链
• 分区分配算法（专门一节来讨论）
  • 首次适应算法
  • 循环首次适应算法
  • 最佳适应算法
  • 最坏适应算法
• 分配与回收操作

空闲分区表

登记系统中的空闲分区

分区号	大小KB	起始地址KB	状态
1	50	85	空闲
2	32	155	空闲
3	70	275	空闲

空闲分区链

​ 用链头指针将系统中的空闲分区链接起来，构成空闲分区链。

​ 每个空闲分区的起始部分存放相应的控制信息(如大小,指向下一空闲分区的指针等).

分区分配算法

见后一节

分配回收操作

分配操作：按不同的算法有不同的分配操作

​ 核心步骤：m.szie - u.size <= size

​ m.size空闲分区大小，u.size请求的分区大小，size事先规定的不再切割的大小

​ 如果这个判断为true，则说明剩下的区域太小，干脆全部分配给该请求

回收操作：

系统根据回收分区的大小及首地址，在空闲分区表中检查是否有邻接的空闲分区，如有，则合成为一个大的空闲分区，然后修改有关的分区状态信息。

有四种情况：

哪种回收情况，回收后，空闲分区数目要减少一个？

第三种情况

可重定位分区分配方式

零头（碎片）：内存中无法被利用的存储空间

分为两类：

• 内零头（内部碎片）：分配给作业的存储空间中未被利用的部分。如固定分区中存在的碎片。
• 外零头（外部碎片）：系统中无法利用的小的空闲分区。如动态分区中存在的碎片

为了消除零头，目前主要有两种办法：

• 拼接（也叫紧凑或紧缩技术）
• 离散分配方式

拼接

时机：

• 分区回收时
• 当找不到足够大的空闲分区且总空闲分区容量可以满足作业要求时

功能：将内存中所有作业移到内存一端（作业在内存中的位置发生了变化，这就必须对其地址加以修改或变换即称为重定位），使本来分散的多个小空闲分区连成一个大的空闲区

动态分区分配方式 + 拼接

特点：

• 可以充分利用存储区中的“零头/碎片”，提高主存的利用率
• 但若 “零头/碎片”大多，则拼接频率过高会使系统开销加大。

离散分配方式

​ 使用分页式存储管理方式

分区分配算法（基于顺序搜索）

首次自适应算法

空闲分区（链）按地址递增的次序排列。

在进行内存分配时,从空闲分区表/链首开始顺序查找,直到找到第一个满足其大小要求的空闲分区为止。

然后再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲分区表（链）中。

例题：

​ 系统中的空闲分区表如下，现有三个作业分配申请内存空间100K、30K及7K。给出按首次适应算法的内存分配情况及分配后空闲分区表

区号	大小	起址
1	32k	20k
2	8k	52k
3	120k	60k
4	331k	180k

解：

​ 由首次自适应算法可知，100k被分配到了分区3，30k被分配到了分区1，1k被分配到分区2，空闲分区表如下：

​ 大小要减去分配的大小，起止要加上分配走的大小

区号	大小	起址
1	2k	50k
2	1k	59k
3	20k	160k
4	331k	380k

特点：

• 优先利用内存低地址部分的空闲分区,从而保留了高地址部分的大空闲区。

• 但由于低地址部分不断被划分,致使低地址端留下许多难以利用的很小的空闲分区(碎片或零头),而每次查找又都是从低地址部分开始,这无疑增加了查找可用空闲分区的开销。

循环首次适应算法

又称为下次适应算法

与首次适应算法的区别是：

​ 不再每次从空闲分区表/链首开始查找,而是从上次找到的空闲分区的下一个空闲分区开始查找

例题：（还是这个题）

​ 系统中的空闲分区表如下，现有三个作业分配申请内存空间100K、30K及7K。给出按循环适应算法的内存分配情况及分配后空闲分区表

区号	大小	起址
1	32k	20k
2	8k	52k
3	120k	60k
4	331k	180k

解：

​ 区别在于从上次分配后的区号开始查找：

区号	大小	起址
1	25k	27k
2	8k	52k
3	20k	160k
4	301k	210k

特点：

• 使存储空间的利用更加均衡，不致使小的空闲区集中在存储区的一端
• 但这会导致缺乏大的空闲分区。

最佳适应算法

与首次适应算法区别在于：

​ 空闲分区表/链按容量大小递增的次序排列。（注意：每次还是从链首开始查找）

例题：（还是这个题）

​ 系统中的空闲分区表如下，现有三个作业分配申请内存空间100K、30K及7K。给出按最佳适应算法的内存分配情况及分配后空闲分区表

区号	大小	起址
1	32k	20k
2	8k	52k
3	120k	60k
4	331k	180k

解：

​ 区别在于要按容量大小排序：排序后

区号	大小	起址
1	8k	52k
2	32k	20k
3	120k	60k
4	331k	180k

​ 分配：

区号	大小	起址
1	1k	59k
2	2k	50k
3	20k	160k
4	331k	180k

特点：

• 若存在与作业大小一致的空闲分区,则它必然被选中
• 若不存在与作业大小一致的空闲分区，则只划分比作业稍大的空闲分区，从而保留了大的空闲分区
• 但空闲区一般不可能正好和它申请的内存空间大小一样,因而将其分割成两部分时,往往使剩下的空闲区非常小,从而在存储器中留下许多难以利用的小空闲区（碎片或零头）。

最坏适应算法

与最佳适应算法区别在于：

​ 空闲分区表/链按容量大小递减的次序排列。（注意：每次还是从链首开始查找）

例题：（还是这个题）

​ 系统中的空闲分区表如下，现有三个作业分配申请内存空间100K、30K及7K。给出按最佳适应算法的内存分配情况及分配后空闲分区表

区号	大小	起址
1	32k	20k
2	8k	52k
3	120k	60k
4	331k	180k

解：

​ 区别在于要按容量大小递减排序：排序后

区号	大小	起址
1	331k	180k
2	120k	60k
3	32k	20k
4	8k	52k

​ 分配后：

区号	大小	起址
1	194k	317k
2	120k	60k
3	32k	20k
4	8k	52k

特点：

• 总是挑选满足作业要求的最大的分区分配给作业。
• 这样使分给作业后剩下的空闲分区也较大，可装下其它作业。
• 但由于最大的空闲分区总是因首先分配而划分，当有大作业到来时，其存储空间的申请往往会得不到满足。

分区的存储保护

存储保护：

​ 为了防止一个作业有意或无意地破坏操作系统或其它作业

保护方法：

• 界限寄存器方法
  • 上下界寄存器方法
  • 基址、限长寄存器方法
• 存储保护键方法

界限寄存器方法

存储保护键方法

​ 给每个存储块分配一个单独的保护键，它相当于一把锁。进入系统的每个作业也赋予一个保护键，它相当于一把钥匙。当作业运行时，检查钥匙和锁是否匹配，如果不匹配，则系统发出保护性中断信号，停止作业运行

对换（交换 Swapping）

​ 将暂时不用的某个进程及数据（首先是处于阻塞状态优先级最低的）部分（或全部）从内存移到到外存（备份区或对换区，采用连续分配的动态存储管理方式）中去，让出内存空间，同时将某个需要的进程调入到内存中，让其运行。

交换的类型：

• 整体对换（其实就是处理器调度中的中程调度，也叫进程对换）
• 部分对换（以“页”或“段”为单位进行内外存调度）

为了实现进程对换，OS必须实现：

• 对换空间的管理
• 进程的换入
• 进程的换出

对换空间的管理

OS把外存分为：

• 文件区
  • 文件区主要用来长期存放文件，采用离散分配方式
• 对换区
  • 对换区用于存放从内存换出的进程，短暂存储，为了提高换入换出速度，使用连续分配方式

进程的换入与换出

换出：

• 时机：一进程创建子进程，无足够内存
• 过程：
  1. 选择处于阻塞状态且优先级最低的进程
  2. 启动磁盘，将该进程的程序和数据传送到磁盘的对换区
  3. 回收该进程所占用的内存空间，修改PCB

换入：

• 过程：
  1. 系统定时地查看所有进程的状态，从中找出“就绪”状态但已换出的进程。**(静止就绪)**
  2. 选择换出时间最久进程
  3. 将其换入

分页存储管理方式

在第五节，我们知道，连续分配存储方式虽然简单，但是会产生很多碎片，使用拼接技术代价极高，所以我们可以使用离散分配的方式

• 分页式存储管理（主流）
• 分段式存储管理
• 段页式存储管理

在分页存储管理方式中，如不具备页面对换功能，不支持虚拟存储器功能，

则在调度作业运行时，必须将它的所有页面一次调入内存，且在运行过程中页必须一直驻留内存。

若内存没有足够的块，则作业等待，

这种存储管理方式称为纯分页或基本分页存储管理方式

基本思想

• 将用户进程的逻辑地址空间划分为若干个大小相等的区域，称为页，从0开始编号
• 内存空间也分成若干个与页大小相等的区域，称为块（页框），从0开始编号

在为进程分配内存时，以块为单位,将进程中若干页装入到多个不相邻的块中，最后一页常装不满一块而出现页内碎片。

如：作业9KB，页面大小2KB，划分5个页，最后一页只有1KB。

注意：需要CPU的硬件支持——地址变换机构

核心内容

地址结构

逻辑地址：页号 + 位移量（页内地址）

• 页号的大小决定地址空间有多少页，例如页号有20bit，那么就允许有2^20即1M页
• 位移量决定每页的大小，例如页内地址有12bit，那么每页就有2^12即4KB

物理地址：块号 + 块内位移

• 块号说明内存有多少块
• 块内位移与逻辑地址的页内地址相等

例如：页面大小为1K；用户作业的逻辑地址为：1027(十进制)；

​ 那么它可以这么表示（1,3） 1027 - 1024 =3

有如下公式：

逻辑地址A
页面大小L
页号P
页内地址d

P = INT [A / L]
d = [ A ] MOD L

例题：设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页2048B，内存总共有8个存储块，试问逻辑地址至少应为多少位？内存空间有多大？

解：

​ 逻辑地址空间最大为16页，即2^4，那么页号就占4bit

​ 每页2048B，即2KB，那么页内位移与块内位移就是11bit

​ 内存有八个存储块，块号就有2^3，那么块号就有3bit

​ 所以解得：逻辑地址有15bit，内存空间有8*2KB，即16Kb

页面大小

由地址结构（逻辑）决定(页内位移的位数)

如果页面较小：

• 页面数多，页表长
• 页面换进换出效率低下

如果页面较大：

• 增加页面碎片，不利于内存利用率

所以页面大小通常为2的幂次

页表

• 记录了页面在内存中对应的块号
• 页表一般放在内存中
• 页表的基址及长度由页表寄存器（[页表始地+页表长度]）给出
  • 未执行时存放在PCB中
• 访问一个字节的数据/指令需访问内存2次(页表一次,内存一次),所以出现内存访问速度降低的问题

地址变换机构

能将用户地址空间中的逻辑地址变换为内存空间中的物理地址

分为：

• 基本的地址变换机构
• 具有快表（TLB）的地址变换机构

基本的地址变换机构

例1： 若在一分页存储管理系统中，某作业的页表如表所示，已知页面大小为1024B，试将逻辑地址1011，2148，5012转化为相应的物理地址？画出其地址转换图。

页号	块号
0	2
1	3
2	1
3	6

解： 由页号共四页可知，页号占2bit，页内地址为10bit

​ 块号有第6页，说明页号至少为3bit，块内地址10bit

​ 1011 = 0011 1111 0011，可以得出页号为0，页内地址为11 1111 0011

​ 查表，可知页号0对应块号2，所以物理地址为 0 1011 1111 0011（0BF3H）

​ 2148同理，5012越界，产生越界中断

具有快表（TLB）的地址变换机构

为提高地址变换速度，加了TLB

• 一种特殊告诉缓存存储器
• 内容为页表的一部分
• CPU产生的逻辑地址页首先在快表中查询，若找到就找出对应物理块；否则再按原有结构寻找

信息共享

分页存储管理，虽然解决了零头问题，但是不利于页面共享

若共享数据与不共享数据划在同一块中，则：有些不共享的数据也被共享，不易保密。

实现数据共享的最好方法——段式存储管理

信息保护

页式存储管理系统提供了两种方式：

• 地址越界保护：页号<页表长度（页表寄存器）
• 在页表中设置保护位：定义操作权限：只读，读写，执行等

分段存储管理方式

为了满足用户的一系列需求：

• 方便编程
  • 按逻辑关系分为若干个段，每个段从0编址，并有名字和长度，访问的逻辑地址由段名和段内偏移量决定
• 信息共享
  • 共享是以信息为逻辑单位，页是存储信息的物理单位，段却是信息的逻辑单位
• 信息保护
• 动态链接：动态链接以段为单位。
• 动态增长

基本思想

空间划分：

​ 将用户作业的逻辑地址空间划分成若干个大小不等的段（由用户根据逻辑信息的相对完整来划分）。

​ 各段有段名（常用段号代替），首地址为0。

内存分配：

​ 在为作业分配内存时，以段为单位，分配一段连续的物理地址空间；段间不必连续。

注意：

1. 整个作业的逻辑地址空间是二维的，其逻辑地址由段号和段内地址组成；物理地址空间是一维的
2. 需要CPU的硬件支持（地址变换机构）

段表

• 记录了（段号，段长，基址）
• 段表记录了段与内存位置对应关系
• 保存在内存中
• 有段表寄存器（段表始址 + 段表长度）
• 访问一个数据也需要访问2次内存

例：采用段式存储管理的系统中，若地址用24位表示，其中8位表示段号，则允许段的最大长度是___

24-8=16 段的最大长度2^16

注意：

• 在分段存储管理中，要检查两次越界
  1. 检查段号是否越界
  2. 检查段内地址是否越界

例如：段表为

段号	内存起始地址	段长
0	210	500
1	2350	20
2	100	90
3	1350	590

有下表：

0	430
2	120

求表中逻辑地址对应的物理地址

解：由0查段表，得到内存起始地址为210，段长为500，430<500，所以物理地址为430+210=640

​ 由2查段表，得到内存起始地址为100，段长为90，由于90<120，所以段内地址越界

优缺点

优点：

1. 便于程序模块化处理；段的保护容易
2. 便于处理动态的数据结构；可增、减分段长度
3. 便于动态链接。每一分段是一组有意义的信息或具有独立功能的程序段
4. 便于共享分段。

缺点：

1. 和分页管理一样，处理机要为地址变换花费时间，要为段表提供附加的存储空间，这使操作系统复杂化
2. 为满足分段的动态增长和减少外零头，要采用拼接手段
3. 产生碎片(外部碎片)。

分段和分页的主要区别

	页式存储管理	段式存储管理
目的	实现非连续分配, 解决碎片问题(页内碎片)	更好满足用户需要
信息单位	页（物理单位）	段（逻辑单位）
大小	固定（由系统定）	不定（由用户程序定）
内存分配单位	页	段
作业地址空间	一维	二维
优点	有效解决了碎片问题 有效提高内存的利用率	更好地实现数据共享与保护 段长可动态增长 便于动态链接

着重注意：

• 页信息的物理单位，段是信息的逻辑单位
• 作业地址空间，分页是一维，分段是二维

后来结合段式与页式，有了段页式存储管理方式：

• 将内存等分为块，程序按逻辑模块分为若干段
• 只会产生内零头

虚拟存储器

程序想要运行就得全部装入内存中去，

• 但是有的程序很大，所需的内存空间大于内存总容量；

• 有大量作业运行，但内存不够所有作业

此时提出了虚拟存储器

虚拟存储器的最大容量由计算机的地址结构决定

常规存储器管理方式的特征

1. 一次性：作业在运行前需一次性地全部装入内存。将导致上述两问题。
2. 驻留性：作业装入内存后，便一直驻留内存，直至作业运行结束。

局部性原理

一较短时间内，程序的执行仅限于某个部分，相应地，它所访问的存储空间也局限于某个区域

分为：

• 时间局部性：刚被访问的数据可能不久后被再次访问
• 空间局部性：访问后的存储单元的附加很可能被访问

所以，此后没有必要将程序全部装入内存中去，而是如果要访问的页不在内存才去将该页调入内存

虚拟存储器：是指仅把作业的一部分装入内存便可运行作业的存储管理系统，它具有请求页(段)调入功能和页（段）置换功能，能从逻辑上对内存容量进行扩充，其逻辑容量由外存容量和内存容量之和决定，其运行速度接近于内存，成本接近于外存

请求分页（段）存储管理方式

在分页（段）方式上，增加了

• 请求调页（段）功能：访问的页面不存在时要求将页面调入内存
• 页面（分段）置换功能：将当前不需要运行的页面换入外存，需要用的换入内存

特征

1. 多次性（最基本）：虚拟存储器最重要的特征。指一个作业被分成多次调入内存运行。
2. 对换性：允许在作业运行过程中进行换进、换出。换进、换出可提高内存利用率。
3. 虚拟性（最本质）：从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量

虚拟性以多次性和对换性为基础，而多次性和对换性又是离散分配为基础

实现

	分页请求系统	分段请求系统
基本单位	页	段
长度	固定	可变
分配方式	固定分配	动态
复杂性	简单	较复杂

页表机制

页号	块号	状态位	访问字段	修改位	外存地址

新增加：

• 状态位：表示该页是否调入内存
• 访问字段：记录本页最近一段时间内的访问次数
• 修改位：表示调入内存后是否被修改
• 外存地址：指出外存上的地址

缺页中断机制

当访问的页不在内存时（通过判断状态位），就产生缺页中断

缺页中断与一般中断的区别：

1. 在指令执行期间产生和处理中断信号。缺页中断要立即处理
2. 一条指令在执行期间，可能产生多次缺页中断。

地址变换机构

例题： 某虚拟存储器的用户空间共有32个页面，每页1KB，主存16KB。假定某时刻系统为用户的第0、1、2、3页分别分配的物理块号为5、10、4、7，试将虚拟地址0A5C变换为物理地址。

解：32个页面 >> 页号为2^5 >> 页号占5bit

​ 每页1kb>>页内地址与块内地址为>>10bit

0A5C转换为二进制为000 1010 0101 1100，页号为2，查出块号为4，即0100

结果为0010010 0101 1100 = 125C

请求分页页面置换算法

用来选择换出页面的算法

页面置换算法的优劣直接影响到系统的效率，若选择不合适，可能会出现抖动现象

抖动：

​ 刚被淘汰出内存的页面，过后不久又要访问它，需要再次将其调入，而该页调入内存后不入又再次被淘汰出内存，然后又要访问它，如此反复

最佳置换算法（OPT）

选择永远不再需要的页面或最长时间以后才需要访问的页面予以淘汰

是一种理论算法，不可实现，这种方法用来衡量其他算法的质量

例如：假定系统为某进程分配了3个物理块，进程运行时的页面走向为 1,2,3,4,1,2,5,1,2,3,4,5，开始时3个物理块均为空，计算采用最佳置换页面淘汰算法时的缺页率？

页面走向	1	2	3	4	1	2	5	1	2	3	4	5
物理块1	1	1	1	1	1	1	1	1	1	3	3	3
物理块2		2	2	2	2	2	2	2	2	2	4	4
物理块3			3	4	4	4	5	5	5	5	5	5
缺页	缺	缺	缺	缺	H	H	缺	H	H	缺	缺	H

解：如表格所示，缺页率为7/12（H代表命中）

先进先出置换算法（FIFO）

最先进来的页面最先换出去

还是这个题：

例如：假定系统为某进程分配了3个物理块，进程运行时的页面走向为 1,2,3,4,1,2,5,1,2,3,4,5，开始时3个物理块均为空，计算采用最佳置换页面淘汰算法时的缺页率？

页面走向	1	2	3	4	1	2	5	1	2	3	4	5
物理块1	1	1	1*	4	4	4*	5			5	5*
物理块2		2	2	2*	1	1	1*			3	3
物理块3			3	3	3*	2	2			2*	4
缺页	缺	缺	缺	缺	缺	缺	缺			缺	缺

解：如表格所示，缺页率为9/12

假如本题我们再给一个物理内存块，结果是：

页面走向	1	2	3	4	1	2	5	1	2	3	4	5
物理块1	1	1	1	1*			5	5	5	5*	4	4
物理块2		2	2	2			2*	1	1	1	1*	5
物理块3			3	3			3	3*	2	2	2	2*
物理块4				4			4	4	4*	3	3	3
缺页	缺	缺	缺	缺			缺	缺	缺	缺	缺	缺

10/12，多给了一块内存块，缺页率还增加了！这就是Belady异常

Belady现象是指：采用FIFO算法时，如果对—个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。

最近最久未使用算法（LRU）

least recently used：选择最近没有使用的页面进行淘汰（依据局部性原理）

需要硬件的支持：

• 栈：栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号
• 寄存器：寄存器每一位代表一个页，置为1代表刚被访问，每隔一段时间（100ms）将寄存器右移一位

还是此题：

例如：假定系统为某进程分配了3个物理块，进程运行时的页面走向为 1,2,3,4,1,2,5,1,2,3,4,5，开始时3个物理块均为空，计算采用最佳置换页面淘汰算法时的缺页率？

页面走向	1	2	3	4	1	2	5	1	2	3	4	5
物理块1	1	1	1*	4	4	4*	5	5	5*	3	3	3
物理块2		2	2	2*	1	1	1*	1	1	1*	4	4
物理块3			3	3	3*	2	2	2*	2	2	2*	5
缺页	缺	缺	缺	缺	缺	缺	缺	H	H	缺	缺	缺

解：如表格所示，缺页率为10/12

淘汰算法的性能评价

缺页率：f = 缺页次数 / 总次数

命中率：H = 命中次数 / 总次数

抖动问题：导致系统效率急剧下降的主辅存之间的频繁的页面置换现象称为抖动

影响缺页中断率的因素

• 页面大小：页面大一点有助于缺页率降低，但是会使浪费增大
• 分配给作业的主存：主存越大，减少却也次数（任何程序在局部性放入主存时都有一个临界值的要求，这个主存要求的临界值被称为工作集）

总结

“内零头”：是指分配给作业的存储空间中未被利用的部分。
“外零头”：是指系统中无法利用的小存储块。

• 固定分区分配：产生“内零头”
• 可变分区分配：产生“外零头”
• 页式虚拟存储器：产生“内零头”
• 段式虚拟存储器：产生“外零头”
• 段页式：产生“内零头”