OS存储器管理(一)

存储器的层次：

分为寄存器、主存（内存）和 辅存（外存）三个层次。

主存：高速缓冲存储器、主存储器、磁盘缓冲存储器，

         主存又称为可执行存储器；

辅存：固定磁盘存储器、可移动的外部存储器；

         其可长期保存数据，但不能被处理器直接访问。

此处针对的是在OS层面上对主存（内存）的管理。

内(主)存储器管理的主要功能：① 逻辑地址到物理地址的转换     ② 内存（主存）空间的分配与回收     ③ 内存信息（数据）的共享与保护     ④ 内存的逻辑扩充（虚拟存储器的实现）

一个用户程序在运行之前需要经历若干步骤，为了执行，程序应被调入内存并放在进程内：

在这些步骤中，地址可能有不同的表示形式：

符号（源程序中），可重定位的地址（目标模块），绝对地址（内存映像）

逻辑地址：目标代码的相对编址。由CPU生成，也称为虚拟地址

物理地址：内存存储单元的编址，内存单元的实际地址

逻辑地址空间：目标代码用逻辑地址编址对应的区域

内存存储空间：内存若干存储单元用物理地址编址对应的区域

重定位：逻辑地址转换为物理地址的操作（过程）

接下来，将指令与数据捆绑到内存地址，可以在以下步骤的任何一步中执行：

编译时：MS-DOS的COM格式程序

加载时：编译器生成可重定位代码

执行时：进程在执行时可以从一个内存段移到另一内存段，那么捆绑必须延迟到执行时才进行。

运行时从虚拟地址映射到物理地址的硬件设备称为内存管理单元(MMU)

用户进程所生成的地址在送交内存之前，都将加上重定位寄存器的值。

用户程序处理的是逻辑地址，它不会看到真实的物理地址。

原理图如下：

例如：

重定位的方式：

静态重定位：目标代码装入内存时，一次性进行逻辑地址到物理地址的地址转换。

动态重定位：目标代码装入内存时，先不进行地址转换（即原代码装入），在执行时,再实施地址转换。

内存分配的方式：连续分配和非连续分配

内存通常分为两个区域：

一个用于驻留操作系统，常与中断向量一起放在低内存

另一个用于用户进程，常放在高内存。

一、连续分配

四种方式：

①单一连续区分配

②固定分区分配

③可变（动态）分区分配

④可重定位分区分配

①单分区分配方法（Single-partition allocation）

重定位寄存器方案用来保护用户进程之间，用户进程与操作系统之间不会相互修改代码与数据

重定位寄存器包含了最小的物理地址；界限寄存器包含了逻辑地址的范围，每个逻辑地址必须小于界限寄存器

②固定分区分配

* 算法思想

内存可用区划分成若干个大小固定的存区，每个存区分别装入一道作业的代码（数据）。

* 算法实现

建立分区说明表，记录各分区大小、地址及分配情况

例如：

分配：查分区说明表，找到一个足够大的空闲分区分配之；

回收：将回收分区对应的分区说明表状态改为“空闲”。

优点：内存可同时装入多道作业代码，算法实现简单；

缺点：存在浪费（分区一次性全部分配出去）；会产生内部碎片。

③动态存储分配问题

算法思想：事先不划分分区，待作业需要分配内存时，再按需分配划分分区（分区的大小及个数不固定）。

数据结构:

空闲分区表或空闲分区链表  ---->   记录空闲分区的大小、地址等

空闲分区链表状况：

分配：查空闲分区链表，找到第一个足够大的分区，将其一分为二分配之；

分配策略（算法）：首次适应算法，循环首次适应算法，最佳适应算法，最差适应算法

回收：先将回收分区与相邻空闲分区合并再修改空闲分区链表。

回收算法：前邻接合并，后邻接合并，前、后邻接合并，不邻接处理

* 优、缺点

按需分配，可解决浪费问题； 分配算法复杂，会产生外部碎片；

邻接合并系统开销大。

* 碎片问题

碎片:可变分区分配过程中形成的若干个非常小的无法再利用的小分区，形成外部碎片

碎片分为外部碎片和内部碎片。

处理碎片的方法：

1.紧缩（compaction，拼接）：用来降低外部碎片移动内存内容，以便所有空闲空间合并成一整块。

如果重定位是动态的，是在运行时进行的，那么就能采用紧缩

2.另一种可能解决外部碎片问题的方法是允许物理地址空间为非连续，这样只要有物理内存就可为进程分配：分页或分段

④可重定位分区分配

* 算法思想

在可变分区分配算法的基础上，采用动态重定位方式装入程序（数据）。当无足够大的分区供分配时，若总的空闲存储容量够用，则将各分区中的内容向内存一端移动（紧凑），使另一端形成一个大的空闲分区，然后再分配。

例：前例若要为作业10分配120k的存储空间，因无足够大分区（总空闲容量290k），则先进行合并处理：

内存的离散分配方式见下篇。