操作系统-存储管理

存储器是由内存和外存组成。内存由顺序编址的块组成，每块包含相应的物理单元。CPU要启动相应的输入输出设备后才能使外存与内存交换信息。

1、虚拟存储器

存储管理系统吧进程中那些不经常被访问的程序段和数据放入外存中，待需要访问他们时再将他们调入内存。对于那些一部分数据和程序段在内存而另一部分在外存的进程，可用虚拟存储器来安排地址。有两种方法可以安排这些编译后的的目标代码的地址。一种方法是按照物理存储器中的位置赋予实际物理地址;另一种方法是编译链接程序把用户源程序编译后链接到一个以0地址为始地址的线性或多维虚拟地址空间

将进程中的目标代码、数据等的虚拟地址组成的虚拟空间称为虚拟存储器。。每个进程都有自己的虚拟存储器，且虚拟存储器的容量是由计算机的地址结构和寻址方式确定的。

(1)地址变换：把虚拟地址映射到内存地址。称为地址重定位或地址映射。

(2)静态地址重定位：在虚拟空间执行程序之前完成地址映射工作。不需要硬件支持。但是无法实现虚拟存储器

(3)动态地址重定位：在程序执行过程中，CPU访问内存之前，将要访问的程序或数据地址依靠地址变换机构转换。。可以对内存进行非连续分配。

2、分区存储管理

分区管理是把内存划分成若干个大小不等的区域，除操作系统占用一个区域之外，其余由多道环境下的各并发进程共享。

(1) 固定分区：将内存大小固定地划分成若干个大小不等的区域。一旦划分结束，在整个执行过程中每个分区的长度和内存的总分区个数将保持不变。

(2) 动态分区域法：在作业执行前并不建立分区，分区的建立是在作业的处理过程中进行的，且其大小可随作业或进程对内存的要求而改变，这就改变了固定分区法中那种即使是小作业也要占据大分区的浪费现象，从而提高了内存的利用率。

3、动态分区的分配与回收

主要解决三个问题：

对于请求表中的要求内存长度，从可用表或自由链中寻找合适的空闲区分配程序;

分配空闲区之后，更新可用表或自由链;

进程或作业释放内存资源时，和相邻的空闲区进行链接合并，更新可用表或自由链。

(1) 最先适应法：要求可用表或自由链接按起始地址递增的次序排列。一旦找到大于或等于所要求内存长度的分区，则结束探索。然后，从找到的分区中划出所要求的内存长度分配给用户，并把剩余部分进行合并(如果有相邻空闲区存在)后留在可用表中，但要修改其相应的表项。

(2) 最佳适应算法：要求从小到大的次序组成空闲区可用表或自由链。当用户作业或进程声请一个空闲区时，存储管理程序从表头开始查找，当找到第一个满足要求的空闲区时，停止查找。如果该空闲区大于请求表中的请求长度，则与最先适应法相同，将减去剩余空闲区部分留在可用表中。

(3) 最坏适应算法：要求空闲区按其大小递减的顺序组成空闲区可用表或自由链。

4、动态分区时的回收与拼接

当用户左右或进程执行结束时存储管理程序要收回已使用完毕的空闲区，并将其插入空闲区可用表或自由链，此时会碰到空闲区拼接问题。如果不对空闲区进行拼接，则由于每个作业或进程所要求的内存长度不一样而出现大量分散，较小的空闲区。这就造成了大量的内存浪费。

5、分区存储管理的优缺点

优点如下：

(1) 实现了多个作业或进程对内存的共享，有助于多道程序设计，从而提高了系统的资源利用率。

(2) 该方法要求的硬件支持少，管理算法简单，因而实现容易

缺点如下：

(1) 内存利用率仍然不高。和单一连续分配算法一样，存储器中可能含有从未使用过的信息。而且还存在着严重的碎小空闲区(碎片)不能利用的问题，这进一步影响了内存的利用率。

(2) 作业或进程的大小受分区大小的控制，除非配合采用覆盖和交换技术。

(3) 无法实现各分区间的信息共享。

6、 覆盖与交换技术

是在多道环境下用来扩充内存的两种方法。

(1) 覆盖技术

基于这样一种思想提出的，即一个程序并不需要一开始就把它的全部指令和数据都装入内存后都执行。在单CPU系统中，每一时刻事实上只能执行一条指令。一次不妨把程序划分为若干个功能上相对独立的程序段，按照程序的逻辑结构让那些不会同时执行的程序段共享同一块内存区。通常，这些程序段都被保存在外存中，当有关程序段的先头程序段已经执行结束后，再把后续程序段调入内存覆盖前面的程序段。这使得用户看来，好像内存扩大了，从而达到内存扩充的目的。但是，这要求程序员提供一个清楚的覆盖结构。

(2) 交换技术

多道程序环境或分时系统中，同时执行好几个作业或进程。但是，这些同时存在于内存中的作业或进程，有的处于执行状态或就绪状态，而有的则处于等待状态。一般来说，等待时间较长，如果让这些等待中的进程继续驻留内存，将会造成存储空间的浪费。交换是指先将内存某部分的程序或数据写入外存交换区，再从外存交换区中调入指定的程序或数据到内存中来，并让其执行的一种内存扩充技术。与覆盖技术相比，交换不要求程序员给出程序段之间的覆盖结构。而且交换主要是在进程或作业之间进行，而覆盖主要在同一个作业或进程内进行。

页式管理

分区式管理尽管实现方式较为简单，但存在着严重的碎片问题使得内存的利用率不高，再者，分区式管理时，由于各作业或进程对应于不同的分区以及在分区各作业或进程连续存放，进程的大小仍受分区大小或内存可用空间的限制。而且，分区式管理也不利于程序段和数据的共享。

页式管理正是为了减少碎片以及为了只在内存存放那些反复执行或即将执行的程序段与数据部分，而把那些不经常执行的程序段和数据存放于外存待执行时调入，以提高内存的利用率而提出来的。

基本原理： 首先，各进程的虚拟空间被划分成若干个长度相等的页，页长的划分和内存外存之间的数据传输速度以及内存大小等有关，一般每个页长的大小为1-4K大小，划分之后，进程的虚地址变为页号p与页内地址w所组成。每个页面之间不再连续。实现了内存中碎片的减少，因为任一碎片都会小于一个页面。实现了连续存储到非连续存储的飞跃，为动态存储打好了基础。

1、 静态页面管理

在作业或进程开始执行之前，把该作业或进程的的程序段和数据全部装入内存的各个页面中，并通过页表和硬件地址变换机构实现虚拟地址到内存物理地址的地址映射。

(1)内存页面分配与回收

为要求内存的作业或进程分配足够的页面。系统依靠存储页面表、请求表以及页表来完成内存的分配工作。

a. 页表：页号+页面号组成。在内存中占有一块固定的存储区。页表的大小由进程或作业的长度决定。

b. 请求表：确定作业或进程的虚拟空间的各页在内存中的实际位置。为了完成这个任务，系统必须知道每个作业或进程的页表起始地址和长度，以进行内存分配和地址变换。

c. 存储页面表：指出内存个页面是否已被分配出去，以及未分配页面的总数。存储页面表有两种构成方法，一种是在内存中划分一块固定区域，每个单元的每个比特代表一个页面，如果页面已被分配，则对应比特位置1，否则置0,，这种方法是位视图法。另一种方法是空闲页面链的方法，使用了空闲页面本身的单元存放指针，不占据额外的内存空间。

(2) 分配算法(如下图)

(3) 地址变换

怎样由页号和页内相对地址变换到内存物理地址的问题。首先需要一个装置页表起始地址和页表长度用的控制寄存器。系统把所调度执行的进程页表始地址和长度从请求表中取出置入控制寄存器中。然后由控制寄存器的页表始地址，可以找到页表所在的位置

静态页式管理解决了分区管理时的碎片问题。但是，由于静态页式管理要求进程或作业在执行前全部装入内存，如果可用页面数小于用户要求时，该作业或进程只好等待。而且作业和进程的大小仍受内存可用页面数的限制。

11.3 动态页式管理

请求页式管理的地址变换过程与静态页式管理时相同，也是通过页表查出相应的页面号之后，由页面号和域内相对地址相加而得到实际物理地址。但是，由于请求页式管理只让进程或作业的部分程序和数据驻留在内存中，一次，在执行过程中，不可避免地会出现某些虚页不在内存中的问题。

第一个问题可以用扩充页表的方法解决。即与每个虚页号相对应，除了页面号之外，再增设该页是否在内存的中断位以及该页在外存中的副本起始地址。

关于虚页不在内存时的处理，涉及到两个问题。第一，采用何种方法把所缺的页调入内存;第二，如果内存中没有空闲页面时，把调进来的页面放在什么地方，也就是说，采用什么策略来淘汰已占据内存的页。

(1) 请求页式管理中的置换算法

a. 随机淘汰算法

b. 轮转法和先进先出算法(FIFO)

FiFO和RR算法的内存利用率不高，FIFO的另一个缺点是陷阱现象(belady现象)，有时会出现分配的页面数增多，缺页次数反而增加的奇怪现象。

c.最近最久未使用页面置换算法(LRU)：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。