操作系统笔记整理6——存储器管理（1）

点此链接可跳转到：操作系统笔记整理——目录索引页

参考书籍：《计算机操作系统》第四版 汤小丹等编著

存储器的层次结构

程序的装入和链接

一个用户源程序要变为在内存中可执行的程序，通常要进行以下处理： 编译：由编译程序将用户源程序编译成若干个目标模块 链接：由链接程序将目标模块和相应的库函数链接成装入模块 装入：由装入程序将装入模块装入内存

根据链接时间的不同，程序的链接可分为：静态链接、装入时动态链接和运行时动态链接

可重定位装入方式

事先不知用户 程序在内存的驻留位置，装入程序在装入时根据内存的实际情况把相 对地址（逻辑地址）转换为绝对地址，装入到适当的位置。（在装入 时进行地址转换） 静态重定位

• 当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后 不再转换。
• 一般在装入内存时由软件完成。

动态重定位

• 在程序运行过程中要访问数据时再进行地址变换（即在逐条指令执行时完 成地址映射）。
• 一般为了提高效率，此工作由硬件地址映射机制来完成。 硬件（寄存器）支持，软硬件结合完成。

连续分配存储管理方式

连续分配方式（分区技术）：指为一个用户程序分配一片连续的内存空间 静态分区：作业装入时一次完成，分区大小和边界在运行时不能改变 动态分区：根据作业大小动态地建立分区，分区的大小、数目可变。

• 单一连续分区分配（静态分区技术）：仅用于单用户单任务系统
• 固定分区分配（静态分区技术）：可用于多道系统
• 动态分区分配（动态分区技术）
• 动态可重定位分区分配（动态分区技术）：引入了动态重定位和内存紧凑技术
• 伙伴系统（动态分区技术）

单一连续分区分配

内存管理方法：将内存分为系统区（内存低端，分配给OS用）和用户区（内存高端，分配给用户用）。 采用静态分配方式，即作业一旦进入内存，就要等待它运行结束后才能释放内存 只能用于单用户、单任务的OS中，内存中只装入一道作业运行

一个容量为256KB的内存，操作系统占用32KB，剩下224KB全部分配给用户作业，如果一个作业仅需64KB，那么就有160KB的存储空间被浪费。

固定分区分配方式

最早使用的一种可运行多道程序的存储管理方法 存储管理方法：将内存空间划分为若干个固定大小的分区，除OS占一区外，其余的一个分区装入一道程序。分区的大小可以相等，也可以不等，但事先必须确定，运行时不能改变。即分区的大小及边界在运行时不能改变 系统需建立一张分区说明表，以记录分区号、分区大小、分区的起始地址及状态（已分配或未分配） 当用户程序要装入内存时，通常将分区按大小进行排队，由内存分配程序检索分区说明表，找出一个满足要求的尚未分配的分区分配该程序

动态分区分配方式

存储管理方法：内存不是预先划分好的，作业装入时，根据作业的需求和内存空间的使用情况来决定是否分配。若有足够的空间，则按需要分割一部分分区给该进程；否则令其等待内存空间

动态分区分配中的数据结构

空闲分区表：用来登记系统中的空闲分区（分区号、分区起始地址、分区大小及状态） 空闲分区链： 前、后向链接指针用于把所有的空闲分区链接成一个双向链。当分区被分配出去以后， 前、后向指针无意义。 状态位 0：未分配 状态位 1：已分配

分区分配操作

分配内存 事先规定size是不再切割的剩余分区的大小 设请求的分区大小为u.size，空闲分区的大小为m.size 若m.size-u.size≤size说明多余部分太小，可不再切割，将整个分区分配给请求者 否则，便从该分区中安请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区链（表）中。 回收内存 回收分区上邻接一个空闲分区，合并后首地址为空闲分区的首地址，大小为二者之和 回收分区下邻接一个空闲分区，合并后首地址为回收分区的首地址，大小为二者之和 回收分区上下邻接空闲分区，合并后首地址为上空闲分区的首地址，大小为三者之和 回收分区不邻接空闲分区，这时在空闲分区表中新建一表项，并填写分区大小等信息

动态分区分配方法 基于顺序搜索的动态分区分配算法

按照一定的分配算法从空闲分区表（链）中选出一个满足作业需求的分区分割，一部分分配给作业，剩下的部分仍然留在空闲分区表（链）中，同时修改空闲分区表（链）中相应的信息。

首次适应算法

空闲分区链按地址递增的次序排列 在进行内存分配时，从空闲分区表/链首开始顺序查找，直到找到第一个满足其大小要求的空闲分区为止，然后再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲分区表中

例题 系统中的空闲分区表如下表示，现有三个作业分配申请内存空间100K、30K及7K，给出按首次适应算法的内存分配情况及分配后空闲分区表。 按首次适应算法，申请作业 100k，分配 3 号分区，剩下分区为 20k，起始地址 160K ；申请 作业 30k，分配 1 号分区，剩下分区为 2k，起始地址 50K ；申请作业 7k，分配 2 号分区， 剩下分区为 1k，起始地址 59K。

特点：优先利用内存低地址部分的空闲分区。但由于低地址部分不断被划分，留下许多难以利用的很小的空闲分区（碎片或零头），而每次查找又都是从低地址部分开始，增加了查找可用空闲分区的开销。

循环首次适应算法

与首次适应算法类似，只不过不再每次从空闲分区表/链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直到找到第一个能满足其大小要求的空闲分区为止。

最佳适应算法

空闲分区表/链按容量大小递增的次序排列。在进行内存分配时，从空闲分区表/链首开始顺序查找，直到找到第一个满足其大小要求的空闲分区为止。 注意分配完后要按容量递增的顺序重新排列 特点：最佳适应算法往往使剩下的空闲分区非常小，从而在存储器中留下许多难以利用的小空闲区（碎片）

最坏适应算法

空闲分区表/链按容量大小递减的次序排列。在进行内存分配时，从空闲分区表/链首开始顺序查找，直到找到第一个满足其大小要求的空闲分区为止。 特点：由于最大的空闲分区总是因首先分配而划分，当有大作业到来时，其存储空间的申请往往会得不到满足

基于索引搜索的动态分区分配算法

基于顺序搜索的动态分区分配算法一般只适合于较小的系统，如果系统的分区很多，空闲分区表（链）可能很大（很长），检索速度会比较慢。为了提高搜索空闲分区的速度，大中型系统采用了基于索引搜索的动态分区分配算法

快速适应算法

快速适应算法，又称为分类搜索法，把空闲分区按容量大小进行分类， 经常用到长度的空闲区设立单独的空闲区链表。系统为多个空闲链表设 立一张管理索引表。 在查找时，仅需要根据进程的长度，寻找到能容纳它的最小空闲区链表，取下第一块进行分配即可 该算法在分配时，不会对任何分区产生分割 在分配空闲分区时是以进程为单位，一个分区只属于一个进程，存在一定的浪费。空间换时间。

伙伴系统

伙伴系统是介于固定分区与可变分区之间的动态分区技术 伙伴：在分配存储块时将一个大的存储块分裂成两个大小相等的小块，这两个小块就称为“伙伴” 伙伴系统规定，无论已分配分区或空闲分区，其大小均为 2 的 k 次幂，k 为整数，n ≤ k ≤ m，其中：2n 表示分配的最小分区的大小，2m 表示分配的最大分区的大小，通常2m是整个可分配内存的大小。 内存管理模块保持有多个空闲块链表，空闲块的大小可以为 2，4，8，…，2m 字节。

对于 1M 的内存，空闲块的大小最多有20种不同的取值

内存分配

1. 系统初启时，只有一个最大的空闲块（整个内存）
2. 当一个长度为n的进程申请内存时，就分给它一个大于等于n的最小的2次幂的空闲块
3. 如果2i-1