离散分配式存储管理

赵刚

【摘 要】该文提出了一种不连续分配内存的方式——分页式存储管理，并且讨论了它的基本思想和地址转换，最后提出了该存储管理的缺点。

【关键词】分页式存储管理；物理地址；逻辑地址；地址重定位；页表；快表

【Abstract】This paper proposes a way to allocate memory discrete - page memory management， and discusses its basic ideas and address translation. Finally， the shortcomings of the storage management.

【Key words】Page memory management；Physical address；Logical address；The relocation；Page table；Fast table

存储管理是操作系统五大功能之一，是操作系统的重要课题。在存储管理中，连续分配方式会产生许多“碎片”，而这些“碎片”空间很小，无法容纳相关作业。通常通过“紧凑”方法，移动程序可以将许多“碎片”拼接成可用的大块空间，但是通过“紧凑”方法，移动程序增加了系统的开销。如果允许将作业直接分散地装入到许多不相邻、不连续的分区中，则无须再进行“紧凑”。基于这一思想而产生了离散分配方式，分页式存储管理就是其中的一种。

1. 分页式存储管理的基本思想

物理地址是内存储器中的实际有效地址，逻辑地址用是户程序中使用的地址，也就是访内指令给出的地址叫逻辑地址。

1.1 分页存储管理允许把一个作业存放到若干不相邻、不连续的分区中，这样既可免去移动信息所造成的系统开销，又可尽量减少内存产生碎片，其基本思想是：

（1）把物理地址空间分成大小相等的许多分区，每个分区称为“块”或“帧”，每个块有一个编号，从“0”开始编号，块是存储分配的单元；

（2）按块的大小把逻辑地址空间分成许多“页”，从“0”开始编号；

（3）逻辑地址形式： 作业的逻辑地址与一个数对（页号，页内位移）一一对应；

（4）采用分页式存储管理，作业一次性全部装入内存，作业进入内存时其连续的页面可以装入内存中不相邻、不连续的块中，只要内存有空闲块，作业的某一页可以放到内存任一空闲块。

1.2 例如：用户作业A的大小为3KB，内存块的大小为1KB，当作业提交给系统后被分成了3页，如图1（a）所示，根据图1（c）页表（页与块的对应关系），作业A被装进了内存不相邻、不连续块中，如图1（b）所示。

2. 页面的大小

在分页存储管理中的页面的大小要适中。页面如果太小，虽然可以使内存碎片减小，减少了内存碎片的总空间，有利于提高内存利用率，但也会使每个作业占用较多的页面，从而导致作业的页表过长，占用大量内存，此外，还会降低页面换进换出的效率；页面如果较大，虽然可以减少页表的长度，提高页面换进换出的速度，但却又会使页内碎片增大，降低内存利用率（分页存储管理的实现见图1）。

3. 分页式存储管理的地址转换

3.1 页表与快表。

（1）分页系统中，将作业的各个页面离散地存储在内存不连续的物理块中，系统应能保证进程的正确运行，即能在内存中找到每个页面所对应的物理块。为此，系统为每个作业建立了一张页面映像表，简称页表。配置了页表后，作业执行时，通过查找页表，找到每页在内存中的物理块号。页表的作用是实现从页号到物理块号的地址映射。

（2）由于页表是存放在内存中，CPU在每存取一个数据时，都要两次访问内存。第一次是访问内存中的页表，从中找到指定页的物理块号，再将块号与页内位移拼接，以形成物理地址。第二次访问内存时，才是从第一次所得地址中获得所需数据（或向此地址中写入数据）。因此，采用这种方式将降低CPU访问速度，增加了系统在存储上的开销。为了提高地址变换速度，可在地址变换机构中增设一个具有并行查寻能力的特殊高速缓冲寄存器，又称为“联想寄存器”（Associative Memory），或称为“快表”，地址变换过程是：在CPU给出有效地址后，由地址变换机构自动地将页号送入高速缓冲寄存器，并将此页号与高速缓存中的所有页号进行比较，若其中有与此相匹配的页号，便表示所要访问的页表项在快表中。于是，可直接从快表中读出该页所对应的物理块号，并送到物理地址寄存器中。如在块表中未找到对应的页表项，则还须再访问内存中的页表，找到后，把从页表项中读出的物理块号送地址寄存器，同时，再将此页表项存入快表的一个寄存器单元中，重新修改快表。

3.2 地址重定位。

地址重定位指把目标程序中的逻辑地址转换成主存空间的物理地址，分页式存储管理采用的是动态重定位，程序在执行时过程中动态完成地址重定位，需要硬件的支持，地址转换过程如下：

（1）作业的逻辑地址转换成页号，页内位移两部分，页号=逻辑地址/块尺寸，页内位移=逻辑地址%块尺寸（“/”是整除运算符，“%”是求余运算符）；

（2）以页号为索引去检索页表，在执行检索之前，先将页号与页表长度进行比较，如果页号大于或等于页表长度，表示本次所访问的地址已超越作业的地址空间，系统将产生一个地址越界中断，如果没有出现越界错误，通过查找页表，找到页号对应的块号；

（3）块号*块尺寸+页内位移得到物理地址，这样完成从逻辑地址到物理地址的变换。

3.3 举例分析。

3.3.1 分页系统中内存被划分成4块，每块4KB，某作业的逻辑地址空间共划分成4个页面，当前页与块对应关系表（页表）如表1所示，试求出对应于下列逻辑地址的物理地址：（a）4100（b）8300。（见表1）

3.3.2 解：（a）逻辑地址4100对应的页号是：4100/4096=1 ，对应的页内位移是：4100%4096=4，用1去查页表，知道第1页现在存放在内存的第1块，第1块的起始地址为4096（4KB），因此，逻辑地址4100所对应的物理地址是：4096+4=4100；

（b）虚拟地址8300对应的页号是：8300/4096=2，对应的页内位移是：8300%4096=108，用2去查页表，知道第2页现在存放在内存的第6块，第6块的起始地址为6×4K=24576，因此，逻辑地址8300所对应的物理地址是24576+108=24684。

4. 分页式存储管理的缺点

（1）分页式存储管理中，作业的最后一页大小可能与内存块大小不吻合，会产生内部碎片，浪费内存空间；

（2）分页式存储管理中，作业需要一次性全部装入内存，当作业尺寸大于内存剩余空间时，作业无法进入内存运行，因此，分页式存储管理不具备虚拟存储技术。

参考文献

[1] 宗大华， 宗涛， 陈吉人. 操作系统[M].3版.北京： 人民邮电出版社， 2011： 57～66.

[2] 张尧学， 史美林.计算机操作系统教程[M]. 北京： 清华大学出版社， 1993.

[文章编号]1619-2737（2015）07-29-027