下载掌阅APP，畅读海量书库
立即打开
3.5 存储管理
存储管理是指对存储器资源的管理，主要是指内存并涉及外存的管理。内存是指处理机可以直接存取指令和数据的存储器。它是现代操作系统进行操作的中心，是计算机系统中的一种重要资源。在计算机的发展历程中，不管是单道程序系统，还是多道程序系统，内存利用始终是一个重要环节。在计算机工作时，程序处理的典型过程是首先CPU通过程序计数器中的值从内存中取得相应的指令，指令被译码后根据要求可能会从存储器中再取得操作数。对操作数处理完成后，操作结果又会存储到存储器中。在这个过程中，操作系统需要保证程序执行中按照适当的顺序从正确的存储器单元中存取指令或者数据，也就是说有效管理存储器的存储空间，根据地址实现上述任务。
在单道程序阶段，人们就已经意识到存储资源的不足，并开始研究用覆盖技术来解决程序长度超过内存可用空间时程序的运行问题。在多道程序出现以后，这种要求就更为突出，而且又提出存储器的分配（即共享）的问题。由于多道程序共享内存，这就产生内存保护功能的问题。因为用户程序或非常驻系统程序是随机、动态地纳入系统，所以必须改变以前那种按绝对地址编写程序的概念。因此产生地址转换或地址再定位的问题。由于用户程序的规模在成百上千倍地增长，这就要求内存管理能够提供内存扩充功能，即利用单位价格更为便宜的外存来模拟为内存，让用户透明使用。这就是内存管理的虚拟功能。
综上所述，存储管理包括以下4方面的内容：
（1）存储器资源的组织和分配，存储的共享和各种分配算法。
（2）地址的再定位，各种地址变换机构，逻辑地址与物理地址的对应关系及维护。
（3）存储保护。
（4）存储器的扩充，虚拟存储器及其各种调度算法等。
在我们用汇编语言或高级语言编写程序时，总是通过符号名来访问某一单元。我们把程序中由符号名组成的空间称为名空间。源程序经过汇编或编译并再经过链接编辑程序所装配形成的程序，通常是以0为基址进行顺序编址。或者是把程序分成若干部分，每部分以0为基址。这样的地址表示形式称为相对地址，也称为逻辑地址或虚地址。把该程序逻辑地址组成的集合称为程序的逻辑地址空间（简称地址空间）。而在存储器中每个具体存储单元都有不同的编号，每个编号就是一个物理地址，整个程序在内存中存储后所占用的物理地址的集合形成程序的物理地址空间（简称存储空间）。
当一个逻辑地址空间的程序装入到物理地址空间时，由于两个空间不一致，需要进行地址映射，即地址的重定位。地址重定位有两种方式：静态重定位和动态重定位。
静态重定位是在程序装入内存，开始执行前进行地址重定位。静态重定位工作通常是由装配程序完成的。静态地址重定位的优点是容易实现，无需硬件支持，它只要求程序本身是可重定位的，即对那些要修改的地址部分具有某种标识，地址重定位由专门设计的程序来完成。在早期的操作系统中大多数都采用这种方法。其主要缺点是程序经地址重定位后就不能移动了，因而不能重新分配内存，不利于内存的有效利用。
动态地址重定位是在程序执行期间，在每次存储访问前进行的。在这种情况下，通常通过基地址寄存器、变址寄存器计算出指令的有效地址，再利用硬件机构实现地址映射，这样的硬件设备称为存储管理单元MMU（Memory-Management Unit）。通常采用的办法是利用一个重定位寄存器，对每一个有效地址都要加上重定位寄存器中的内容，以形成绝对地址。动态地址重定位的优点是程序在内存中的搬移不会对程序的正确执行造成影响，使内存得以被充分利用，其缺点是需要附加的硬件支持，实现存储管理的软件算法比较复杂。
单一连续分配是一种简单的存储分配方案，主要用于单用户单任务操作系统。它把内存分为两个区域：系统区和用户区。系统区是操作系统专用区，不允许用户程序直接访问，一般在内存低地址部分，剩余的其他内存区域为用户区。应用程序装入到用户区，可使用用户区全部空间。
单一连续分配方案的优点是方法简单，易于实现。缺点是它仅适用于单道程序，对要求内存空间少的程序，造成内存浪费。因程序全部装入，所以很少使用的程序部分也占用内存。因而，不能使处理机和内存得到充分利用。
固定式分区分配是把内存分为一些大小相等或不等的分区，每个应用进程占用一个或几个分区。操作系统占用其中一个分区。根据不同的内存容量划分策略有两类情况：一是分区大小相等，这只适合于多个相同程序的并发执行，适用于一些控制多个同类对象的环境，处理多个类型相同的对象，各对象由一道存在于一个分区的进程控制，但是对于程序规模差异较大的多道环境不太适合，比如大于分区大小的进程无法装入，而且小进程也会占用一个分区，造成内存碎片（即无法被利用的空闲存储空间）太大。
二是分区大小不等，多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区，这样可以有效地改善前一种方法的缺陷。
固定式分区分配的优点是适用于多道程序系统和分时系统，支持多个程序并发执行。问题是可能存在内碎片和外碎片。所谓内碎片是指占用分区之内未被利用的空间；外碎片是指占用分区之间难以利用的空闲分区（通常是小空闲分区）。内碎片将造成浪费。分区总数固定也限制了并发执行的程序数目。
固定式分区分配可使用分区表或分区链表的数据结构，记录分区的大小和使用情况，以便对内存进行分配和回收的管理。还可以和覆盖、交换技术配合使用，以提高内存的利用率。
覆盖技术的基本思想是将内存的同一区域按照使用的先后顺序，分配给几个不同进程或一个进程的几个程序段或数据段，即允许进程运行时，可以不用把它的所有程序段都调入内存，当进程处理需要某程序段时将它装入到原来已经占用的某分区中，原来存储在这个分区中的程序就被“覆盖”了。
采用覆盖技术后，进程可以分为常驻内存部分和覆盖部分，常驻内存部分是指进程处理过程中始终需要的程序段，而覆盖部分是进程处理过程中动态调入内存的程序段。这样，当进程要求运行时，系统根据其覆盖结构，给它分配一段存储空间，其大小等于常驻部分和覆盖区之和。覆盖区长度由相应覆盖段中最大程序段的长度确定。处理过程是先把常驻内存部分调入，然后将需要的可覆盖程序段由辅存调入，随着进程执行，再将其他存放在辅存的覆盖部分陆续调入。
我们看到，采用覆盖技术后，就可以用小于进程申请大小的内存空间来满足一个进程的处理空间，有效地利用内存。
所谓对换，就是把内存中暂时无法运行的进程或者暂时不需要的程序、数据写入辅存，并将具备运行条件的进程或者需要的程序、数据从辅存读入内存。采用对换技术可以很好地提高内存的利用率和CPU的处理效率。
为了改善固定分区分配给系统带来的内存碎片太大、空间浪费严重的缺陷，提出了动态分区分配，也称为可变式分区分配的策略，即根据进程的实际需求动态地划分内存的分区方法。它是在进程装入和处理过程中建立分区，并要使分区的容量能正好适应进程的大小。而整个内存分区数目随着进程数目的变化而动态改变，各个分区的大小随着各个进程的大小各有不同，所以称之为动态分区分配。
在动态分区分配中，各个空闲分区通过指针形成链，称为空闲分区链，它是系统动态分区分配所需要的一种重要数据结构。按分区分配算法，寻找某个空闲分区，其大小需大于或等于程序的要求。若是大于要求，则将该分区分割成两个分区，其中一个分区为要求的大小并标记为“占用”，而另一个分区为余下部分并标记为“空闲”。分区的先后次序通常是从内存低端到高端。当需要时，将相邻的空闲分区合并成一个空闲分区。根据空闲分区链和分区说明表实现分区分配。
动态分区分配算法有以下几种。
·最先匹配法（first-fit）。空闲分区链以地址递增的顺序链接，分配时从链首开始查找，找到第一个大小可以满足的分区为止，从其中划分出所需空间分配给申请的进程，剩余部分仍旧作为一个分区保留在空闲分区链的适当位置中，否则给出无法分配的提示。
·下次匹配法（next-fit）。为了改变首次适应算法每次从链首开始查寻造成的缺陷，可以增加一个起始查寻指针，指向下一次开始查寻时的起始分区，在查寻过程中，该指针向后移动，当移动到最后一个空闲分区后，重新回到链首。找到适当分区后，按首次适应算法的划分分区方式进行。这种方法可以使内存区分配比较平均，减少查寻次数，分配和释放的时间性能较好，但较大的空闲分区不易保留，造成缺少大空闲分区，使得大进程无法进入。
·最佳匹配法（best-fit）。空闲分区链按照分区容量递增的方式形成，分配时从链首开始查找，这样找到的第一个大小可以满足的分区肯定是与进程申请空间大小最接近，甚至是完全吻合的分区，而且平均查找次数为分区数的一半，也就是说，它是“最佳适应”的。但这种方法所造成的剩余分区又肯定是相对最小的，通常难以利用，甚至我们可以说，每次分配一个分区都会造成一个无法再利用的“碎片”，而这些“碎片”的总容量可能是比较大的。
·最坏匹配法（worst-fit）。空闲分区链按照分区容量递减的方式形成，分配时从链首开始，若链首分区大小不满足，则可以肯定不存在能够满足要求的分区；否则对链首分区进行划分，剩余空间成为“碎片”的可能性肯定是最小的。所以说，最差适应算法具有查找速度快，分区碎片少的优点，但又会产生缺少大分区的缺点。
在分区分配方案中，地址映射都遵循“物理地址=分区始地址+逻辑地址”，固定分区分配与动态分区分配的分区始地址都来自于硬件“基址寄存器”，动态重定位分区分配的分区起始地址来自于“重定位寄存器”。内存保护由“基址寄存器”和“限长寄存器”共同实现，也可以用一对下限寄存器和上限寄存器来实现，一旦超过限长，则发出越界中断信号。
分区分配方案的主要优点可归纳如下：
·多道程序下的内存共享，改善了系统吞吐量，在内存利用率方面，从固定式分区到动态分区，再到动态重定位分区依次提高。
·为实现分区分配所使用的数据结构占用的存储容量相对较少，算法也相对简单。
·实现存储保护的措施比较简单。
分区分配的主要缺点有：
·内存仍不能充分利用，除了动态重定位式分区法外，都存在着严重的碎片问题。
·不能实现对内存的扩充，因此进程的大小受到内存可用空间的限制。
·与单一连续分配一样，要求一个进程在执行前必须全部装入内存，因此在内存中可能包含不会被使用的信息。
· “紧凑”提高了内存利用率，但是进程移动所产生的额外开销增加了CPU的负担。
·几个并行进程之间不能共享存入内存的单一信息副本（如公用子程序、数据段等）。
页式存储管理是通过引入进程的逻辑地址，把进程地址空间与实际存储位置分离，从而增加存储管理的灵活性。
我们把逻辑地址空间划分为一些相等的片，这些片称为页或页面。同样，物理地址空间也被划分为同样大小的片，称为块。这样用户程序进入内存时，就可以将一页对应存入到一个块中。这些块不必连续。对整个程序来说，只有可能在最后一块存在碎片（称为页内碎片），而且碎片大小不会超过一块，所以内存利用率可以大大提高。
页面（或块）的大小由系统硬件地址结构规定，通常是2的幂，例如1KB、2KB、4KB等。这样的规定可以使地址映射容易实现。页面不能过大，也不能过小。过小会造成页面过多，页表过长，页表又会占用较大的内存空间，而且在虚拟存储中增加了页面换入换出次数，增加了系统开销。过大又会造成页内碎片太大，内存利用率不高。
综上所述，分页存储管理便于多道程序设计，提高了内存的利用率，而不必像动态分区分配那样执行紧凑操作。但分页存储管理仍然存在如下严重缺点：
·采用动态地址映射会增加计算机成本和降低处理机的速度。
·各种表格要占用一定容量的内存空间，而且还要花费一部分处理机时间来建立和管理这些表格。
·虽然消除了大量碎片，但每个作业的最后一页一般都有不能充分利用的空白区。例如，假定页面大小为4KB，如果某一作业需要9KB内存，则应该为它分配3个物理存储块，最后一块的3KB空间被浪费了。如果减少页面大小，使页面大小为2KB，则对于需要9KB内存的作业应分配5个存储块，其中有1KB的内存被浪费了。减少页面大小，可以减少内存的浪费，但页表的长度又增加了，这也是一个矛盾。
·存储扩充问题仍未得到解决。当没有足够空间能装下整个作业地址空间时，该作业还是无法运行。
分段存储管理和页式存储管理一样是通过引入进程的逻辑地址，把进程地址空间与实际存储位置分离，从而增加存储管理的灵活性。页式管理是把内存视为一维线性空间；而段式管理是把内存视为二维空间，与进程逻辑相一致。
将程序的地址空间划分为若干个段（Segment），程序加载时，分配其所需的所有段（内存分区），这些段不必连续。物理内存的管理采用动态分区。
一个用户作业的程序按其逻辑结构可划分为若干段，例如主程序段、子程序段、数据段、堆栈段等。这些段中的每一段在逻辑上都是完整的，因此每一段都是一组逻辑信息，有自己的名字，且都有一段连续的地址空间。这样的分段组织便于实现段共享和保护，便于实现动态链接和数据动态增长。
在分段式存储管理中，段名用段号代替，段地址从0开始编址，因为各段的逻辑信息内容不同，所以段长度不同。
当一个用户程序装入内存时，系统为每个段分配一个连续的内存区域，而各个段之间可以离散存放。
为了获得分段管理在逻辑上及分页管理在存储空间方面的优点，可以采用段页结合的方法。这一技术的基本思想是：用分段的方法来分配和管理虚存；用分页的方法来分配和管理实存。在段页式存储管理系统中，每一段不再占有连续的实存空间，而被划分为若干个页面。详细内容可参看有关文献。
现在我们讨论的重点转向存储扩充的问题及与此问题有关的虚拟存储器的概念。请求分页技术可以实现主存的扩充，它为每个用户提供一个虚拟存储器，它的地址空间远比主存的空间大。我们把作业空间、地址空间划分的页称为虚页。相应地把主存称为实存，把实存中的块称为实页。
分页存储管理系统根据请求装入所需页面的方法，称为请求分页存储管理。
由于在多道程序环境下，程序执行时呈现出如下的局部性特征：
·时间局部性。一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内；具体表现为程序中大量的循环结构和各种数据结构，使某段程序一旦执行，很快又会被再次执行，某数据结构被访问后，可能在短时间内再次被访问。
·空间局部性。当前指令和邻近的几条指令，当前访问的数据和邻近的数据都集中在一个较小区域内。
程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域的特性称为局部性原理。
由于程序存在局部性原理，我们就可以将当前必需的一部分程序存在于内存中，就可以开始执行，随着向前推进，再将所需的其他内容调入。但是在调入时，可能出现内存不够的情况，这样就要采用对换等技术。在请求分页管理中，对换的对象是页。
页面置换算法的功能是需要调入页面时，选择内存中哪个物理页面被置换。目标是在局部性原理指导下依据过去的统计数据进行预测，把未来不再使用的或短期内较少使用的页面调出。对必须常驻内存的操作系统的关键部分或时间关键（time-critical）的应用进程，采用页面锁定技术，在页表中加上锁定标志位。下面是常用的页面置换算法。
（1）先进先出算法FIFO（First In First Out）。算法的基本思想是，总是先淘汰那些驻留在内存时间最长的页面，即先进入内存的页面先被淘汰。因为最早调入内存的页面不再被访问的可能性最大，这种算法实现起来比较简单。
先进先出算法实现简单，但是与进程实际运行的规律不适应，一般缺页率较高，置换的次数较多，这种置换增加了系统开销。
（2）最优页面置换算法OPR（Optimal Page Replacement）。最优页面置换算法的思想是选择以后最远将来才会用到甚至是以后再不会用到的页面予以置换。采用这种算法，可以保证只发生最少页面置换次数。因为这是依据进程将来的执行情况来决定置换对象的，而实际的操作系统不可能具有预知“未来”的能力，所以说这种算法无法由计算机实现，但它可以作为衡量某种置换算法性能的一个参考标准。
（3）最近最久未用置换算法LRU（Least Recently Used）。该算法的基本思想是依据局部性原理，如果某一页被访问了，那么它很可能马上又被访问；反之，如果某一页很久没被访问，那么最近也不会再被访问。所以这种算法的实质是当需要置换一页时，选择在最近一段时间最久未用的页予以淘汰。
LRU算法能够比较普遍地适用于各种类型的程序，但是实现起来比较困难。因为要对先前的访问历史时时加以记录和更新，如果这种连续的修改完全由软件来做，则系统开销太大，如果由硬件完成，会增加计算机成本。因此，在实际应用中得到推广的是一种简单而又有效的LRU近似算法。