前言
以下内容源自计算机操作系统（第四版）
关于操作系统，
CSDN有很多的优秀博客。
在这里，
本文摘取其他博客内容，
并附上相关链接，
如有侵权，
联系删除，
仅供学习交流使用
推荐
第四章 存储器管理
4.1 存储器的层次结构
4.1.1 多层结构的存储器系统
1.存储器的多层结构。
存储层次至少应具有三级：最高层为 CPU 寄存器，中间为主存，最底层是辅存。还可以根据具体的功能分工细划为寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等 6 层。在存储层次中越往上，存储介质的访问速度越快，价格也越高，相对存储容量也越小。
寄存器、高速缓存、主存储器和磁盘缓存均属于操作系统存储管理的管辖范畴，掉电后它们存储的信息不再存在。固定磁盘和可移动存储介质属于设备管理的管辖范畴，它们存储的信息将被长期保存。
2.可执行存储器。
寄存器和主存储器又被称为可执行存储器。
4.1.2主存储器与寄存器
1.主存储器
主存储器简称内存或主存。由于主存储器的访问速度远低于 CPU 执行指令的速度，为缓和这一矛盾，在计算机系统中引入了寄存器和高速缓存。
2.寄存器
寄存器具有与处理机相同的速度。主要用于存放处理机运行时的数据。如用寄存器存放操作数，或用作地址寄存器加快地址转换速度等。
4.1.3 高速缓存和磁盘缓存
1.高速缓存
高速缓存是介于寄存器和存储器之间的存储器，主要用于备份主存中较常用的数据。其容量远大于寄存器，而比内存约小两到三个数量级左右。
根据程序执行的局部性原理(即程序在执行时将呈现出局部性规律，在一较短的时间内，程序的执行仅局限于某个部分)，将主存中一些经常访问的信息存放在高速缓存中。当 CPU 访问一组特定信息时，首先检查它是否在高速缓存中，在则直接取出使用，否则再从主存中读取。
2.磁盘缓存
由于目前磁盘的 I/O 速度远低于对主存的访问速度，因此将频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数。但磁盘缓存与高速缓存不同，它本身并不是一种实际存在的存储介质，而是利用主存中的部分存储空间暂存从磁盘中读出(或写入)的信息。
4.2 程序的装入和链接
用户程序要在系统中运行，必须先将它装入内存，然后再将其转变为一个可以执行的程序，通常都要经过以下几个步骤：
1）编译，由编译程序将用户源代码编译成若干个目标模块。
2）链接，由链接程序将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成一个完整的装入模块。
3）装入，由装入程序将装入模块装入内存。
4.2.1 程序的装入
1.绝对装入方式
仅能运行单道程序时可以采用该种方式。装入模块被装入内存后，程序中的逻辑地址与实际内存地址完全相同。
2.可重定位装入方式
采用可重定位装入方式，根据内存的当前情况，将装入模块装入到内存的适当位置。值得注意的是，在采用可重定位装入程序将装入模块装入内存后，会使装入模块中的所有逻辑地址与实际装入内存的物理地址不同。通常是把在装入时对目标程序中指令和数据地址的修改过程称为重定位。又因为地址变换通常是在装入时一次完成的，以后不再改变，故称为静态重定位。
3.动态运行时装入方式
动态运行时的装入程序在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是相对地址。为使地址转换不影响指令的执行速度，这种方式需要一个重定位寄存器的支持。
4.2.2 程序的链接
1.静态链接方式
在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块，以后不再拆开。在将这几个目标模块装配成一个装入模块时，须解决以下两个问题：
1）对相对地址进行修改。这是因为在由编译程序所产生的所有目标模块中，使用的都是相对地址，其起始地址都为 0，每个模块中的地址都是相对于起始地址计算的。
2）变换外部调用符号。将每个模块中所用的外部调用符号也都变换为相对地址。
这种先进行链接所形成的一个完整的装入模块，又称为可执行文件。
2.装入时动态链接
指用户源程序经编译后所得的目标模块，在装入内存时采用边装入边链接的链接方式。这样便于装入前修改和更新，以及实现对目标模块的共享。
3.运行时动态链接
将对某些模块的链接推迟到程序执行时才进行链接，亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由 OS 去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。
4.3 连续分配存储管理方式
为了能将用户程序装入内存，必须为它分配一定大小的内存空间。
4.3.1 单一连续分配
只能用于单道程序环境下，整个内存的用户空间由一个程序独占。
4.3.2 固定分区分配
将内存用户空间划分为若干个固定大小的区域，在每个分区中只装入一道作业。
1.划分分区的方法
分区大小相等、分区大小不等。
2.内存分配
通常将分区按大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态(是否已分配)。当有一用户程序要装入时，由内存分配程序检索该表，从中找出一个能满足要求的、尚未分配的分区，将之分配给该程序，然后将该表项中的状态置为“已分配”。
4.3.3 动态分区分配
又称可变分区分配。
1.动态分区分配中的数据结构
常用的数据结构有以下两种形式：
空闲分区表，表目：分区号、分区大小、分区始址、状态。
空闲分区链，在每个分区的起始部分设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针；在分区尾部则设置一后向指针，以及前后都重复设置状态位和分区大小表目。通过前、后向链接指针，可将所有的空闲分区链接成一个双向链。
2.动态分区分配算法
顺序式搜索算法、索引式搜索算法。
3.分区分配操作
1）分配内存：
系统应利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。设请求的分区大小为 u.size，表中每个空闲分区的大小可表示为 m.size。若 m.size-u.size≤size(size 是事先规定的不再切割的剩余分区的大小)，说明多余部分太小，可不再切割，将整个分区分配给请求者；否则(即多余部分超过 size)，从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区链(表)中。然后，将分配区的首址返回给调用者。
2）回收内存：
当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点，此时可能出现以下四种情况之一：
①回收区与插入点的前一个空闲分区相邻接，此时应将回收区与插入点的前一分区合并。
②回收分区与插入点的后一空闲分区相邻接，此时也可将两分区合并。
③回收区同时与插入点的前、后两个分区邻接，此时将三个分区合并。
④回收区既不与前一个邻接，又不与后一个邻接，这时应为回收区单独建立一新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。
4.3.4 基于顺序搜索的动态分区分配算法
顺序搜索，是指依次搜索空闲分区链上的空闲分区，去寻找一个其大小能满足要求的分区。
碎片：内存空间不断被划分，会留下许多难以利用的、很小的空闲分区。
1.首次适应（first fit，FF）算法
要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止，缺点是低址部分会不断被划分，形成碎片。
2.循环首次适应（next fit，NF）算法
在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找。实现可通过设置一起始查寻指针，用于指示下一次起始查寻的空闲分区，并采用循环查找方式。缺点缺乏大的空闲分区。
3.最佳适应（best fit，BF）算法
总是把能满足要求、又是最小的空闲分区分配给作业，为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。缺点产生许多碎片。
4.最坏适应（worst fit，WF）算法
在扫描整个空闲分区表或链表时，总是挑选一个最大的空闲区，分割一部分空间给作业使用。要求将所有的空闲分区按其容量以从大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求即可。缺点缺乏大的空闲分区。
4.3.5 基于索引搜索的动态分区分配算法
1.快速适应算法
又称为分类搜索法。是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，同时在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。
该算法仅需要根据进程的长度，寻找到能容纳它的最小空闲区链表，并取下第一块进行分配即可。在分配过程中，不会对任何分区产生分割。
2.伙伴系统
规定，无论已分配分区或空闲分区，其大小均为 2 的 k 次幂（k 为整数，l≤k≤m）。通常 2^m是整个可分配内存的大小。
对于每一类具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。
当需要为进程分配一个长度为 n 的存储空间时，首先计算一个 i 值，使 2^(i-1) < n ≤ 2^i，然后在空闲分区大小为 2^i 的空闲分区链表中查找。若找到则直接分配。否则，则在分区大小为 2^(i+1) 的空闲分区链表中寻找。若存在 2^(i+1) 的一个空闲分区，则把该空闲分区分为相等的两个分区，这两个分区称为一对伙伴，其中的一个分区用于分配，而把另一个加入分区大小为 2^i 的空闲分区链表中。若仍然找不到，依次类推去寻找更高1次幂的分区。
与一次分配可能要进行多次分割一样，一次回收也可能要进行多次合并，如回收大小为 2i的空闲分区时，若事先已存在回收块所对应的2i伙伴块的空闲分区时，则应将其与伙伴分区合并为大小为2(i+1)的空闲分区，若事先已存在新合并空闲块对应的2(i+1)伙伴块的空闲分区时，依次类推合并。
对于一个大小为2^k，地址为x的内存块，其伙伴块的地址则用buddy k (x)表示，其通式为：
if(x MOD 2^(k+1) == 0) { buddy k (x) = x + 2^k; } else if(x MOD 2^(k+1) == 2^k) { buddy k (x) = x - 2^k; }
3.哈希算法
构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表表头指针。
4.3.6 动态可重定位分区分配
1.紧凑
在连续分配方式中，必须把一个系统或用户程序装入一连续的内存空间。当一台计算机运行了一段时间后，它的内存空间将会被分割成许多小的分区，而缺乏大的空闲分区。
通过移动内存中作业的位置，以把原来多个分散的小分区拼接成一个大分区的方法，称为“拼接”或“紧凑”。由于经过紧凑后的某些用户程序在内存中的位置发生了变化。为此，在每次“紧凑”后，都必须对移动了的程序或数据进行重定位。
2.动态重定位
在动态运行时装入的方式中，作业装入内存后的所有地址都仍然是相对(逻辑)地址，将相对地址转换为物理地址的工作，被推迟到程序指令要真正执行时进行。
地址变换过程是在程序执行期间，随着对每条指令或数据的访问借助重定位寄存器自动进行的，故称为动态重定位。当系统对内存进行了“紧凑”而使若干程序从内存的某处移至另一处时，不需对程序做任何修改，只要用该程序在内存的新起始地址，去置换原来的起始地址即可。
3.动态重定位分区分配算法
动态重定位分区分配算法与动态分区分配算法基本上相同，差别仅在于：在这种分配算法中，增加了紧凑的功能。
4.4 对换
4.4.1 多道程序环境下的对换技术
1.对换的引入
所谓“对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据调入内存。
2.对换的类型
1）整体对换。
处理机中级调度实际上就是存储器的对换功能。其目的用于解决内存紧张问题。由于中级调度是以进程为单位的，故又称之为“进程对换”或“整体对换”。
2）页面(分段)对换。
以进程的一个“页面”或“分段”为单位进行的，分别称为“页面对换”、“分段对换”，又统称为“部分对换”。
在此，我们只介绍进程对换，而分页或分段对换将放在虚拟存储器中介绍。
4.4.2 对换空间的管理
1.对对换空间管理的主要目标
在具有对换功能的 OS 中，通常把外存分为文件区和对换区。
1）对文件区管理的主要目标。
是提高文件存储空间的利用率，为此，对文件区采取离散分配方式。
2）对对换区管理的主要目标。
对换操作较频繁。故是提高进程换入和换出的速度。为此，采取的是连续分配方式，较少考虑外存中的碎片问题。
2.对换空间空闲盘块管理中的数据结构
与动态分区分配方式中的数据结构相似，即空闲分区表或空闲分区链。在每个表目中包含两项：对换区的首址及其大小，分表用盘块号和盘块数表示。
3.对换空间的分配与回收
与动态分区分配方式中内存分配与回收方法雷同。
4.4.3 进程的换出与换入
1.,进程的换出
换出过程：
1）选择被换出的进程。首先选择处于阻塞或睡眠状态的进程，如果有多个，则选择优先级最低的进程。在有的系统除了考虑优先级，还需考虑进程在内存的驻留时间。如果系统中已无阻塞进程且内存仍不足时，则选择优先级最低的就绪进程换出。
2）进程换出过程。只能换出非共享的程序和数据段，对于共享的只要还有进程需要，就不能换出。在进行换出时，①需要申请对换空间。②若申请成功，就启动磁盘，将该进程的程序和数据传送到磁盘的对换区上。③若传送成功，便可回收该进程所占的内存空间，并对该进程的PCB和内存分配表等进行相应的修改，若还有可换出进程，则继续换出，直至内存中再无阻塞进程为止。
2.进程的换入
定时执行换入操作。找出“就绪”状态但已换出的进程，将其中换出时间最久的进程作为换入进程，为它申请内存。若申请成功则调入，若失败则需先将内存中的某些进程换出，再将进程换入。直到外存中再无“就绪且换出”状态的进程为止，或者已无足够的内存来换入进程时，对换进程停止换入。
4.5 分页存储管理方式
基于允许将一个进程直接分散地装入到许多不相邻接的分区中，则无须再进行“紧凑” 的思想而产生了离散分配方式。分为以下三种：
1）分页存储管理方式：将用户程序的地址空间分为若干个固定大小的区域，称为“页”或者“页面”。也将内存空间分为若干个物理块或页框，页和框的大小相同。
2）分段存储管理方式：把用户程序的地址空间分为若干个大小不同的段。分配以段为单位。
3）段页式存储管理方式：是分页和分段两种存储方式相结合的产物。
4.5.1 分页存储管理的基本方法
1.页面和物理块
1）页面：将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号。相应地，也把内存的物理空间分成若干个块，并为各块加以编号。在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”。
2）页面大小：页面的大小应选择适中，且页面大小应是 2 的幂，通常为 1 KB～8 KB。
2.地址结构
逻辑地址的地址结构如下：
含有两部分：前一部分为页号 P，后一部分为位移量 W(或称为页内地址)。图中的地址长度为 32 位，其中 0～11 位为页内地址，即每页的大小为 4 KB；12～31 位为页号，即地址空间最多允许有 1 M 页。可见系统中允许的最大进程为4kb * 2^20 = 4GB。
对于某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为 A，页面的大小为 L，则页号 P 和页内地址 d 可按下式求得：
其中，INT 是整除函数，MOD 是取余函数。例如，其系统的页面大小为 1 KB，设 A = 2170 B，则由上式可以求得 P = 2，d = 122。
3.页表
为保证进程的正确运行，即能在内存中找到每个页面所对应的物理块。为此，系统又为每个进程建立了一张页面映像表，简称页表。在进程地址空间内的所有页，依次在页表中有一页表项，其中记录了相应页在内存中对应的物理块号。可见，页表的作用是实现从页号到物理块号的地址映射。
4.5.2 地址变换机构
实现从逻辑地址到物理地址的转换。由于页内地址和物理地址是一一对应的(例如，对于页面大小是 1 KB 的页内地址是 0～1023，其相应的物理块内的地址也是 0～1023，无须再进行转换)，因此，地址变换机构的任务实际上只是将逻辑地址中的页号，转换为内存中的物理块号。又因为页面映射表的作用就是用于实现从页号到物理块号的变换，因此，地址变换任务是借助于页表来完成的。
1.基本的地址变换机构
页表大多驻留在内存中。在系统中只设置一个页表寄存器 PTR，在其中存放页表在内存的始址和页表的长度。平时，进程未执行时，页表的始址和页表长度存放在本进程的 PCB 中。当调度程序调度到某进程时，才将这两个数据装入页表寄存器中。因此，在单处理机环境下，虽然系统中可以运行多个进程，但只需一个页表寄存器。
当进程要访问某个逻辑地址中的数据时，分页地址变换机构会自动地将有效地址(相对地址)分为页号和页内地址两部分，再以页号为索引去检索页表。查找操作由硬件执行。在执行检索之前，先将页号与页表长度进行比较，如果页号大于或等于页表长度，则表示本次所访问的地址已超越进程的地址空间。于是，这一错误将被系统发现并产生一地址越界中断。若未出现越界错误，则将页表始址与页号和页表项长度的乘积相加，便得到该表项在页表中的位置，于是可从中得到该页的物理块号，将之装入物理地址寄存器中。与此同时，再将有效地址寄存器中的页内地址送入物理地址寄存器的块内地址字段中。这样便完成了从逻辑地址到物理地址的变换。
