计算机操作系统存储器管理

计算机操作系统存储器管理内容摘要：

该算法，应设置起始查寻指针，以指示下一次起始的查寻的空闲区，并采用循 环查找方式，即如果最后一个 (链尾 )空闲区的大小仍然 能满足要求，应返回到第一个空 闲区，比较其大小是否满足要求， 找到后应立即调整起始查寻指针。 这种算法能使内存的 空闲区分布地更均匀，减少了查找空闲区的开销，但这会缺乏大的空闲区。 (3) 最佳适应算法。 采用这种算法要求可用分区表或自由链表按照空闲区从小到大的 次序排列。 当用户作业申请一个空闲区时，存储器管理程序就从可用分区表或自由链表的 头部开始查找，当找到第一个满足条件的空闲区时，停止查找，进行存储区的分配。 采用这种算法的优点是从空闲区中挑选一个能满足作业要求的最小分区，避免了 大 材小用。 孤立地看，最佳适应算法似乎是最佳的，事实上这种算法也存在缺 点，那就是 由于空闲区通常 可能正好和作业所要求的大小相等，因而要将其分割成两部分，这往往 使剩下的空闲区非常小而成为 碎片 ，以至几乎无法使用。 随着系统的运行，这种小空 闲区也逐步增多，造成了内存空间的浪费。 故有些系统往往还采用与之相反的分配算法， 即最坏适应法。 •82 第 4 章 存储器管理 •83 (4) 最坏适应法是把一个作业分配到内存中最大的空闲区中。 采用这种算法要求可用 分区表或自由链表按照空闲区从大到小的次序排列。 当用户进程申请一个空闲区时，存储 管理系统分析可用分区表或自由链表中的第一个空闲区是否满足用户的作业要求，若满足 要求，则将第一个空闲区分配给它，否则分配失败。 这种算法看起来是最差的算法，因为它总是将最大的空闲区来满足用户的要求。 但是 经过分析后发现，最坏 适应算法也具有实用价值。 其原因是：在大空闲区中装入作业后， 剩下的空闲区往往也很大而 至于是 碎片 ，于是也能满足以后较大的作业要求。 该算 法对中、小作业的运行是很有利的。 以上介绍的是有关动态分区的分配问题，对应分配的问题就是回收与合并问题。 当用户作业和进程执行结束时，存储管理程序要回收使用完毕的空闲区，并将其插入 到空闲区可用表或自由链表中。 在回收的过程中，需要对回收的空闲区进行合并。 因为如 果 对空闲区进行合并，则会由于每个作业或进程所要求的内存长度 一样而形成大量分 散的较小的空闲区，从而造成大量内存的浪费。 所以需要对小的空闲区要尽可能多地进行 合并，以便形成能够满足作业需求的大的空闲区。 将一个被释放的空闲区插入空闲区可用 分区表或自由链表中时，会出现 4 种合并情况。 (1) 释放区与上下两个空闲区相邻。 在这种情况下，将 3 个空闲区合并为一个空闲区。 新空闲区起始地址为上空闲区的起始地址，大小为 3 个空闲区之和。 同时，修改可用分区 表或自由链中的表项目。 (2) 释放区与上空闲区相邻。 在这种情况下，将释放区与上空闲区合并为一个空闲区， 其起始地 址为上空闲区的起始地址，大小为释放区和上空闲区之和。 同时，修改可用分区 表或自由链表中的表项目。 (3) 释放区与下空闲区相邻。 在这种情况下，将释放区与下空闲区合并为一个空闲区， 其起始地址为释放区的起始地址，大小为释放区和下空闲区之和。 同时，修改可用分区表 或自由链表中的表项目。 (4) 释放区与上下两个空闲区都 相邻。 在这种情况下，释放区作为一个新的空闲可 用区插入到可用分区表或自由链中。 3. 动态分区地址转换 静态重定位和动态重定位技术，都可以用完成分区内存管理的地址转换 ，但是由于动 态分区时，分区的大小 固定，有时因系统内存中有过多的小的空闲区，操作系统会整理 内存空间，将小的空闲区合并而移动内存中的程序和数据。 因此，对动态分区方式应采用 动态重定位装入作业，当作业执行时由硬件地址转换机构完成地址转换。 4. 分区的共享和保护 在分区管理方式中，如果每个作业只能占用一个分区，那么就 允许各道作业存在公 共的共享区域。 这样，当几道作业都要使用某个例行程序时就只好在各自的存储区域内各 放一套了，这种方式显然降低了内存的使用效率。 所以有些计算机系统提 供了多对基址 / 限长寄存器，允许一个作业占用多个分区。 系统可以规定某对基址 /限长寄存器限定的区域 是共享的，用来存放共享的程序和常数。 对共享区的信息也必须规定只能执行或读出，而 能写入，若某作业要想往该共享区域写入信息时，则将遭到系统的拒绝，并产生保护中 •83 •84 计算机操作系统原理教程与实训 断。 因此，几道作业共享的例行程序或数据就可存放在一个共享的分区中，只要让各道作 业的共享存储区域部分有相同的基址 /限长址，就可实现分区共享。 分区管理下采用的保护机制通常有上下界寄存器法、基址寄存器法和保护键法，这些 方法在前面已介绍，这里 作赘述。 5. 分区存储管理的优缺点 优点主要有如下几点。 (1) 实现了多道程序设计，从而提高了系统资源的利用率。 (2) 系统要求的硬件支 少，管理简单，实现容易。 缺点主要如下。 (1) 必须给作业分配一组连续的内存区域。 (2) 碎片 问题严重，内存仍 能得到充分利用。 (3) 内存的扩充只能采用覆盖与交换技术，无法真正实现虚拟存储。 页式存储管理 尽管分区管理从实现方法来看比较简单，但由于该管理方式要求作业占用内存的一组 连续的存储单元，这样会导致整个计算机存储系统出现系列问题。 首先，当连续空闲区 能满足进程的要求时，即使系统中所有空闲区之和大于进程对内存的要求，也仍然 能装 入进程；其次，在动态分区的存储空间中，常常由于存在着一些 足以装入任何作业的小 的分区而浪费掉部分存储资源，这就是所谓的存储器的 碎片 问题。 尽管采用一些技术 可以解决这个问题，但要为移动大量信息花去 少处理机时间，代价较高。 如果我们能取 消作业对其存储区域的连续性要求，必然会进一步提高内存空间的利用率，又无需为移动 信息付出代价。 基于这一指导思想，产生了离散存储管理方式。 如果离散分配的基本单位 是页，则称为分页式存储管理；如果离散分配的基本单位是段，则称为分段存储管理 方式。 页式管理的基本原理 页式存储管理取消了存储分配的连续性，它能够将用户进程分配到 连续的存储单元 中连续执行。 页式存储管理系统中，在系统初始化时把每个作业的地址空间分成一些大小相等的块， 称之为页 (Page)。 所有的页从 0开始依次有一个页号。 页的大小通常在 1KB～ 4KB 范围 内，但是，页的大小总是 2 的整数次幂。 经过页的划分之后，进程的虚拟地址变为页号 P 与页内位移量即页内地址 W 所组成。 如图 中的地址长度为 24 位，其中 0～ 9 位 为页内地 址，从这个地址结构可以知道，页面的大小为 1024 字节 (1K)，其地址空间最多可有 16K 页。 23   10 9   2 1 0 页号 P 图 页内地址 W 分页系统的地址结构 •84 第 4 章 存储器管理 •85 除了把作业或进程的虚拟空间划分为大小相等的页之外，页式管理还把内存空间以与 页相等的大小划分为若干个物理块，这些物理块称为页面 (Page Frame)或页桢、页框。 每个 页面也从 0开始依次编址。 这些块为系统中的任一进程所共享 (除去操作系统区外 )。 分 页管理时，系统以页为单位为用户进程分配页面，每个页面之间可以 再连续，从而取消 了存储分配的连续性。 与分区管理相比，页式管理 方式的优越性主要体现在以下两个方面。 (1) 实现了连续存储到非连续存储的飞跃，为实现虚拟存储打下了基础。 (2) 解决了内存中的 碎片 问题，因为从分配思想上看已 存在 可利用空闲的页 面，尽管每个进程的最后一页 一定占满整个页面。 这部分未占满页面的存储区域称为 页内碎片 ，任意一个 页内碎片 都 会大于整个页面的大小，从而提高了内存的利 用率。 分页存储管理根据作业装入内存的时机 同，一般分为静态页式管理和动态页式管理。 下面将具体介绍这些存储管理方法。 静态页式管理 静态页式管理是指用户作业在开始执行以前，将该作业的程序和数据全部装入到内存 的各个页面中，如果当时页面 (页框、页桢 )数 足，则该作业必须等待，系统再调度另外 的作业。 1. 页式管理中所用的数据结构 1) 页表 页表占用内存的一块固定的存储区，它是在作业装入内存并创建其相应进程时，由操 作系统根据内存的分配情况建立的。 页表中需要两个信息，一个是页号，另一个是页面号， 记录着该进程的每个页分配到内存的哪些页面中。 显然，每个进程至少拥有一张页表， 这 个页表记录了进程的虚拟地址和内存地址的映射关系。 2) 请求表 请求表就是用来确定作业或进程的虚拟地址空间的各页表在内存中的实际对应位置。 当系统有多个作业或进程时，系统必须知道每个作业或进程的页表起始地址和长度，才能 进行内存分配和地址变换。 整个系统设置一张请求表，请求表的内容包括：进程号、请求 页面数、页表始址、页表长度和状态等，如表 42 所示。 3) 存储页面表 为了描述内存空间的分配情况，系统设置一张存储页面表。 存储页面表指出了内存各 页面是否已被分配，以及未被分配的页 面总数。 存储页面表的形式有两种：一种是在内存 中划分出一个固定的区域，该区域中每个单元的每个位表示一个页面的使用状态，若该位 为 1，代表所对应的页面已分配，若该位为 0，代表所对应的页面空闲。 这种存储页面表称 为位示图，如图 所示。 •85 •86 计算机操作系统原理教程与实训 表 4 2 请求表 进 程 号 请求页面数 1 2 3  20 30 21  页 表 始 址 1 024 1 044 页 表 长 度 20 30   状 已分配 已分配 未分配  态 0 0 0 1 2 1 0 0 3 1 1 0 4 0 1 1 0 1 1         27 1 0 1 28 1 1 1 29 0 1 0 30 1 1 1 31 1 0 0 图 位示图 位示图要占用一部分内存空间，一个划分为 2 048 个页面的主存，如内存单元长度为 32 位，则位示图就占据 2 048/32=64 个内存单元。 存储页面表的另一种形式是采用空闲页面链的方法。 在空闲页面链中，队首页面的第 一单元和第二单元分别存放空闲页面的总数和指向下一个空闲页面的指针，其他页面的第 一单元则分别存放指向下一个空闲页面的指针。 空闲页面链的方法由于使用了空闲页面本 身的存储单元来存放空闲页面链的指针，因此 占 据额外的主存空间，是一种较为经济的 存储页面表的组织法。 2. 静态页式管理中的分配与回收 静态页式管理的分配和回收非常方便。 作业或进程分配页面时，首先从请求表中查出 作业或进程所要求的页面数。 然后，由存储页面表检查是否有足够的空闲页面，若没有， 则本次无法分配。 如果有，则分配并设置页表，并填写请求表中的相应表项 (页表始址、 页表长度和状态 )，同时修改存储页面表将分配出去的页面对应的状态设置为分配状态。 页面的回收算法也较为简单，当进程执行完毕时，根据进程页表中登记的页面号，将 这些页 面插入到存储页面表中，使之成为空闲页面。 最后，拆除该进程所对应的页表即可。 3. 页式管理中的地址变换 静态页式管理的另一个关键问题是地址变换。 地址变换机构的基本任务，是利用页表， 把用户程序中的逻辑地址变换为内存的物理地址。 由于页内地址和物理地址是一一对应 的， 需进行变换，因此，地址变换机构的任务，实际上是将页号变换为页面号。 页式管 理中的地址变换过程全部由硬件地址变换机构自动完成，采用的是动态重定位技术。 由于页表驻留在内存的某个固定区域中，而取数据或指令又必须经过页表变换才能 得 到实际的物理地址。 因此，页式管理中取一个数据或指令至少要访问内存两次以上。 一次 访问页表以确定所取数据或指令的物理地址，另一次是根据地址取数据或指令。 这比通常 执行指令的速度下降了一半。 解决这。