第三章
存储管理
转自：http://59.67.71.237:8080/ls/web/study/content/chapter3.htm
存储管理是操作系统的重要组成部分，它负责计算机系统内存空间的管理。其目的是充分利用内存空间，为多道程序并发执行提供存储基础，并尽可能地方便用户使用。
3.1存储管理的目的
采用多道程序设计技术，就要在内存中同时存放多道程序，这就要求存储管理解决以下四个重要问题，以达到尽可能方便用户使用和充分利用内存以提高内存利用率的目的。
一、内存空间的分配和回收
二、内存空间的共享与存储保护
三、地址映射（地址重定位）
四、内存扩充
3.2单用户连续存储管理
这是一种最简单的存储管理方式，系统是将整个内存除了给操作系统划分出一块空间外，其余部分的空间都分配给一个作业使用。个人机可采用此种管理方法，它不适宜多道程序设计系统。
可以采用静态重定位方式完成地址映射；处理器在执行指令时，要检查其绝对地址是否属于规定范围内的地址，如果属于，则按此地址访问，否则将产生“地址越界”中断。
某些系统还采用对换技术（Swapping）让多个进程轮流进入内存，这种技术多用于分时系统，随着进程调度，将内存中的进程暂时移到外存，而把外存中某一进程换进内存。
3.3固定分区存储管理
其基本思想是将内存划分成若干固定大小的分区，每个分区中最多只能装入一个作业。当作业申请内存时，系统按一定的算法为其选择一个适当的分区，并装入内存运行。由于分区大小是事先固定的，因而可容纳作业的大小受到限制，而且当用户作业的地址空间小于分区的存储空间时，造成存储空间浪费。
一、空间的分配与回收
系统设置一张“分区分配表”来描述各分区的使用情况，登记的内容应包括：分区号、起始地址、长度和占用标志。其中占用标志为“0”时，表示目前该分区空闲；否则登记占用作业名（或作业号）。有了“分区分配表”，空间分配与回收工作是比较简单的。
二、地址转换和存储保护
固定分区管理可以采用静态重定位方式进行地址映射。
为了实现存储保护，处理器设置了一对“下限寄存器”和“上限寄存器”。当一个已经被装入主存储器的作业能够得到处理器运行时，进程调度应记录当前运行作业所在的分区号，且把该分区的下限地址和上限地址分别送入下限寄存器和上限寄存器中。处理器执行该作业的指令时必须核对其要访问的绝对地址是否越界。
三、多作业队列的固定分区管理
为避免小作业被分配到大的分区中造成空间的浪费，可采用多作业队列的方法。即系统按分区数设置多个作业队列，将作业按其大小排到不同的队列中，一个队列对应某一个分区，以提高内存利用率。
3.4可变分区
可变分区存储管理不是预先将内存划分分区，而是在作业装入内存时建立分区，使分区的大小正好与作业要求的存储空间相等。这种处理方式使内存分配有较大的灵活性，也提高了内存利用率。但是随着对内存不断地分配、释放操作会引起存储碎片的产生。
一、空间的分配与回收
采用可变分区存储管理，系统中的分区个数与分区的大小都在不断地变化，系统利用“空闲区表”来管理内存中的空闲分区，其中登记空闲区的起始地址、长度和状态。当有作业要进入内存时，在“空闲区表”中查找状态为“未分配”且长度大于或等于作业的空闲分区分配给作业，并做适当调整；当一个作业运行完成时，应将该作业占用的空间作为空闲区归还给系统。
可以采用首先适应算法、最佳（优）适应算法和最坏适应算法三种分配策略之一进行内存分配。
二、地址转换和存储保护
可变分区存储管理一般采用动态重定位的方式，为实现地址重定位和存储保护，系统设置相应的硬件：基址/限长寄存器（或上界/下界寄存器）、加法器、比较线路等。
基址寄存器用来存放程序在内存的起始地址，限长寄存器用来存放程序的长度。处理机在执行时，用程序中的相对地址加上基址寄存器中的基地址，形成一个绝对地址，并将相对地址与限长寄存器进行计算比较，检查是否发生地址越界。
三、存储碎片与程序的移动
所谓碎片是指内存中出现的一些零散的小空闲区域。由于碎片都很小，无法再利用。如果内存中碎片很多，将会造成严重的存储资源浪费。解决碎片的方法是移动所有的占用区域，使所有的空闲区合并成一片连续区域，这一技术称为移动技术（紧凑技术）。移动技术除了可解决碎片问题还使内存中的作业进行扩充。显然，移动带来系统开销加大，并且当一个作业如果正与外设进行I/O时，该作业是无法移动的。
3.5页式存储管理
3.5.1基本原理
1．等分内存
页式存储管理将内存空间划分成等长的若干区域，每个区域的大小一般取2的整数幂，称为一个物理页面有时称为块。内存的所有物理页面从0开始编号，称作物理页号。
2．逻辑地址
系统将程序的逻辑空间按照同样大小也划分成若干页面，称为逻辑页面也称为页。程序的各个逻辑页面从0开始依次编号，称作逻辑页号或相对页号。每个页面内从0开始编址，称为页内地址。程序中的逻辑地址由两部分组成：
|
逻辑地址 |
页号p |
页内地址 |
3．内存分配
系统可用一张“位示图”来登记内存中各块的分配情况，存储分配时以页面（块）为单位，并按程序的页数多少进行分配。相邻的页面在内存中不一定相邻，即分配给程序的内存块之间不一定连续。
对程序地址空间的分页是系统自动进行的，即对用户是透明的。由于页面尺寸为2的整数次幂，故相对地址中的高位部分即为页号，低位部分为页内地址。
3.5.2实现原理
1．页表
系统为每个进程建立一张页表，用于记录进程逻辑页面与内存物理页面之间的对应关系。地址空间有多少页，该页表里就登记多少行，且按逻辑页的顺序排列，形如：
|
逻辑页号 |
主存块号 |
|
0 |
B0 |
|
1 |
B1 |
|
2 |
B2 |
|
3 |
B3 |
2．地址映射过程
页式存储管理采用动态重定位，即在程序的执行过程中完成地址转换。处理器每执行一条指令，就将指令中的逻辑地址（p,d）取来从中得到逻辑页号(p)，硬件机构按此页号查页表，得到内存的块号B’，便形成绝对地址（B’,d）,处理器即按此地址访问主存。
3．页面的共享与保护
当多个不同进程中需要有相同页面信息时，可以在主存中只保留一个副本，只要让这些进程各自的有关项中指向内存同一块号即可。同时在页表中设置相应的“存取权限”，对不同进程的访问权限进行各种必要的限制。
3.6段式存储管理
3．6．1基本原理
1．逻辑地址空间
程序按逻辑上有完整意义的段来划分，称为逻辑段。例如主程序、子程序、数据等都可各成一段。将一个程序的所有逻辑段从0开始编号，称为段号。每一个逻辑段都是从0开始编址，称为段内地址。
2．逻辑地址
程序中的逻辑地址由段号和段内地址（s,d）两部分组成。
3．内存分配
系统不进行预先划分，而是以段为单位进行内存分配，为每一个逻辑段分配一个连续的内存区（物理段）。逻辑上连续的段在内存不一定连续存放。
3．6．2实现方法
1．段表
系统为每个进程建立一张段表，用于记录进程的逻辑段与内存物理段之间的对应关系，至少应包括逻辑段号、物理段首地址和该段长度三项内容。
2．建立空闲区表
系统中设立一张内存空闲区表，记录内存中空闲区域情况，用于段的分配和回收内存。
3．地址映射过程
段式存储管理采用动态重定位，处理器每执行一条指令，就将指令中的逻辑地址（s,d）取来从中得到逻辑段号(s)，硬件机构按此段号查段表，得到该段在内存的首地址S’，
该段在内存的首地址S’加上段内地址d，便形成绝对地址（S’+d），处理器即按此地址访问主存。
3．6．3段页式存储管理
页式存储管理的特征是等分内存，解决了碎片问题；段式存储管理的特征是逻辑分段，便于实现共享。为了保持页式和段式上的优点，结合两种存储管理方案，形成了段页式存储管理。
段页式存储管理的基本思想是：把内存划分为大小相等的页面；将程序按其逻辑关系划分为若干段；再按照页面的大小，把每一段划分成若干页面。程序的逻辑地址由三部分组成，形式如下：
|
逻辑地址 |
段号s |
页号p |
页内地址d |
内存是以页为基本单位分配给每个程序的，在逻辑上相邻的页面内存不一定相邻。
系统为每个进程建立一张段表，为进程的每一段各建立一张页表。地址转换过程，要经过查段表、页表后才能得到最终的物理地址。
3.7虚拟存储管理
前面介绍的各种存储管理方案有一点是共同的，即当一个参与并发执行的进程运行时，其整个程序都在内存，存在的缺点是：若一个进程的尺寸比内存可用空间大，则该进程无法运行；而实际上由于局部特性，一个进程在运行的任一阶段只使用所占存储空间的一部分，因此未用到的内存区域就被浪费。
虚拟存储管理是当进程要求运行时，不是将它的全部信息装入内存，而是将其一部分先装入内存，另一部分暂时留在外存（通常是磁盘）。进程在运行过程中，如果要访问的信息不在内存时，发中断由操作系统将它们调入内存，以保证进程的正常运行。
虚拟存储管理分为页式虚拟存储管理、段式虚拟存储管理和段页式虚拟存储管理。
3.7.1页式虚拟存储管理
一、基本原理
基本思想是，在进程开始执行之前，不是装入全部页面，而是只装入一个或几个页面，然后根据进程执行的需要，动态地装入其他页面。
页表中将增加若干项：标志位（又称驻留位），指示该页是否装入内存；外存地址给出该页在外存（磁盘）的地址。
地址映射时当从页表标志位得知此页不在内存时，发缺页中断。此时暂停进程执行，CPU转去执行缺页中断处理程序，负责把所需的页从外存调入到内存某空闲块中，并把物理页号填入页表、更改标志位，然后再返回继续执行被中断的进程。
二、页面淘汰
当内存已无空闲块而又发生缺页中断时，必须在内存中选择一页面将其淘汰并写回到外存，然后再换进新的页面，这一过程称为页面调度，选择被淘汰页面的算法称作页面调度算法。如果页面淘汰算法不合理，可能产生刚被淘汰出去的一页，又要访问它，因而又要把它调入，如此反复，使系统的页面调入调出工作非常频繁从而降低系统效率，这种现象称为“颠簸”或“抖动”。
常用的页面调度算法有：先进先出调度算法（FIFO）、最近最少使用调度算法（LRU）和最近最不经常使用调度算法（LFU）。
注意，对于单用户连续、固定分区、可变分区存储管理是不能实现虚拟存储管理的，因为它们的共同点是，在对作业进行内存分配时是将整个作业全部、连续地放入内存。