1、第5章 存储管理第5章 存储管理 5.1 存储管理基本概念 5.2 存储器的分区管理 5.3 简单页式存储管理 5.4 简单段式存储管理 5.5 虚拟存储管理技术 5.6 段页式存储管理技术 5.7 Linux 的存储管理本章学习的目标1 .存储管理基本概念2. 存储器的分区管理3 .简单页式存储管理4. 简单段式存储管理5. 虚拟存储管理技术6. 段页式存储管理技术7 . Linux 的存储管理 严格地说，计算机的存储管理应该包括内存管理和外存管理，由于内存的管理与外存的管理相似，只是二者的用途不同而已，外存主要用于长时间地保存文件，因此，对外存的管理将放在文件管理那一章介绍，本章主要介绍内
2、存管理。5.1存储管理基本概念 5.1.1 物理内存和虚拟内存 5.1.2交换技术和覆盖技术 5.1.3物理内存和虚拟内存 5.1.4 存储管理的基本任务5.1存储管理基本概念 随着计算机有不断发展，计算机的内存也不断增大，但是，运行在计算机中的软件也在不断的增大。因此，一直以来，计算机内存资源都是紧缺资源之一，对计算机内存进行有效的管理，不仅影响内存的使用效率，而且还会影响整个计算机系统的性能，计算机内存管理也就成为操作系统管理的重要组成部分。 为了更好地理解操作系统的存储管理，首先应该了解几个重要概念。包括：物理地址、逻辑地址、物理内存、虚拟内存、交换技术、覆盖技术等。5.1.1物理地址和
3、逻辑地址 通常一个程序是由多个模块构成的，当程序经过编译后，每一个模块的数据或指令就会形成自己相对独立的地址编码，一般都从0地址开始编码，再经过链接装配后，各个模块就会形成统一的地址编码，这个统一的地址就称为该程序的逻辑地址。每个程序的逻辑地址都是从0开始编码的，这个地址空间也称逻辑地址空间，当程序装入内存后， 并不是装入0开始的空间，因为，内存的0号地址一般有特殊的用途，而操作系统本身的进程一般也是占用地址编号比较小的地址空间，一般用户的程序只能装入地址编号比较大的地址空间，这样，当程序装入内存后的实际的地址便称为该程序的物理地址，因此，程序运行时，都要经过地址变换过程，即将逻辑地址转变成物
4、理地址，这个过程也称为地址重定位。 一般而言，逻辑地址是连续的，程序装入内存后的实际地址可能是不连续的，要看采用的是什么内存管理方法。如图4.1，（a）是逻辑地址，是连续的地址空间，(b)物理地址空间，是不连续的。程序在运行过程中，若要访问内存，就应该将逻辑地址转换成物理地址，即地址重定位，地址重定位有两种方法：静态地址重定位和动态地址重定位。5.1.2 交换技术和覆盖技术 交换技术和覆盖技术都是由于内存使用紧张而出现的弥补措施。由于内存始终都是一种重要而紧缺的资源，当内存不够用时，就可以采用交换技术和覆盖技术，将内存中暂时没用的内容交换到硬盘的交换区中，而将外存中要访问的内容装入内存，或采用
5、覆盖技术。以缓解内存资源的不足，也为实现内存的扩充打下了基础。.交换技术：是将内存中暂时没用的内容交换到硬盘的交换区中，而将外存中要访问的内容装入内存的一种技术。交换到硬盘中的内容要在下次要访问时，才将其装入内存。若系统采用的是静态地址重定位技术，则装入内存时须存放原来的位置；若系统采用的动态地址重位技术，则装入内存时可以不必放回原来的位置。由于每次进行内容换入、换出时都须要用去CPU的时间，如果换入、换出太频繁，也会影响系统的性能。实际上，交换技术是一种用CPU的时间来换取内存空间的做法。因此，这种技术在有些场合也不实用，例如，有些实时性要求比较高的应用。 覆盖技术：是指一个程序在时间上不相
6、互重叠模块共同使用同一块内存空间，在运行过程中，这不重叠模块在内存空间的使用上相互覆盖。如图4.2所示，当主程序启动之后输入模块、修改模块和打印模块都没有执行，而系统执行其中的一个模块时，其它模块是不被执行的，这样的结构就可以利用覆盖技术，使得输入模块、修改模块和打印模块共用一块内存空间，当执行输入模块时，就将主程序和输入模块调入内存，当执行修改模块时，就将主程序和修改模块调入内存，它们交替地使用内存空间，以达到提高内存的利用率。覆盖技术和交换技术一样，是一种以时间换取空间的做法，当模块相互覆盖时，用去了不少的CPU时间。另外，这种技术的使用对程序员要求较高，因为，覆盖技术不需系统的特别支持，
7、完全由程序员自己控制，这就要求程序了解程序的结构，这也就加大了编程的困难。因此，在内存资源不是很紧缺时，一般不采用这种技术。 5.1.3 物理内存和虚拟内存 内存有物理内存和虚拟内存两个不同的概念。物理内存是指系统实际的内存空间。通常以字节为单位，即每个单元为一个字节，每个单元都有一个编号，称之为地址，从0开始，其最大地址是由系统决定的，系统的地址线决定了它的最大寻址地址，一般是2的指数幂。例如，一个32位计算机，理论上的内存可以达到232 字节，其最大地址为232-1，但是，一般情况下，实际的物理内存都没有这么大，常见的有32MB、64MB、128MB、256MB、512MB、1GB等。虚拟
8、内存不是真正的内存，通常是将外存的一部分空间作内存使用，即是虚拟的。就是上面提到的理论上的内存，其容量是由系统所支持的地址总线的位数决定的。如上所说，一个32位的计算机，其虚拟内存可以达到232 字节，约4G字节。5.1.4 存储管理的基本任务 简单地说，存储管理的任务就是管理内存的使用，我们对存储管理的目的就是让有限的内存资源充分地发挥作用，提高内存的使用效率。随着操作系统的发展，存储管理的任务也不同。在有操作系统的初期，那时，在内存的程序除操作系统外只有一个用户程序，存储管理的任务比较简单，只要负责对用户使用的内存进行分配与回收。 但是，后来发展到多用户多任务的操作系统时，即在内存中除操作
9、系统外，还有多道程序的时候，存储管理的任务就复杂了。除了要对多道程序使用的内存进行分配与回收外，还要对不同用户的程序进行保护，使它们之间不相互影响及用户之间的信息共享；还要将每个用户的程序中逻辑地址转换成物理地址，这个过程也称地址映射；此外，还要解决内存资源不足问题等等。 在现代的操作系统中，存储管理不仅要解决上述提出的问题，还要方便用户使用内存，提高内存的利用率，于是，出现了分区、分页、分段和段页式等管理方法，还有交换、覆盖和虚拟存储等技术。具体的存储管理的任务可以归纳如下：1内存空间的管理内存空间的管理是存储管理最基本的任务。只有管理好内存空间，才能有效发挥内存的作用，提高内存利用率。内存
10、空间的管理主要有三个方面的内容：（1）内存使用情况的信息管理：要对内存空间进行管理，首先就应用掌握内存的使用状况，即哪些空间已分配，哪些空间空闲。这就要求有一种数据结构来记录内存的状况信息，不同的管理方法，其数据结构也有所区别。（2）内存的分配：在掌握内存的使用情况的前提下，当用户提出内存申请时，操作系统就要根据一定的分配策略对内存进行分配，能满足一定的条件时就进行分配，同时要修改内存状况信息，不能满足一定的条件时就不能将内存分配给用户。不同的分配策略，内存的利用率也不同，在多道程序环境下，内存的分配策略有两种： 静态分配方式：这种分配方式是将用户程序一次性装入，在程序的执行过程中，不能移动位
11、置，也不能申请增加内存使用的容量。这种分配方式简单，但是，内存的利用率不高，也不利于内存信息的共享。 动态分配方式：这种分配方式是用户不必将程序一次性装入内存，而是将程序的主要执行部分装入内存，在程序的执行过程中，可以根据需要动态申请内存空间。这种分配方式中，不仅可以动态申请内存空间，还可以移动位置，程序可以根据需要从一个位置移到另一个位置，内存使用灵活，内存利用率也较高，更重要的是，在多道程序环境下，这种分配方式容易实现信息共享。（3）内存的回收：当用户用完内存后，要及时将其内存回收，以提高内存的利用率。同时也要修改内存状况信息，有的管理方法中还要对相邻的空闲空间进行合并。 2地址的映射从上
12、面的物理地址和逻辑地址的概念中，我们知道每个程序都有自己逻辑地址空间，而且都是从0从始，但是，在多道程序环境下，它们共同使用一维内存空间，只有一个0地址空间， 因此，每个程序装入内存后，都要将其逻辑地址转换为其实际存放的物理地址，这个过程就是操作系统要做的地址映射过程。地址映射需要系统硬件的支持，通常有一个基地址寄存器BA，用来存当前正在执行的进程的内存空间的基地址。一个源程序中，往往定义许多变量，我们在使用变量时，实际上是用它来代表这个变量的地址，我们也称之为符号地址，当源程序经过编译链接后，这些符号地址就会转换为相应的逻辑地址，当该程序被装入内存的某个存储单元开始的地址空间后，才是该程序的
13、实际物理地址。地址映射过程也称为地址重定位，地址重定位一般有两种方式：静态地址重定位和动态地址重定位。 （1）静态地址重定位：静态重定位是在程序执行之前进行地址重定位。这一工作通常是由装配程序完成的，装配程序将程序中的所有逻辑地址都转换成实际的物理地址。例如，程序在执行前装入到内存开始地址为2000H的一段区域，装配程序将该模块中所有访问内存的逻辑地址转换成物理地址，即将逻辑地址+2000H得到物理地址。这种静态地址重定位早期的操作系统常用的地址重定位位方法，它容易实现，无需硬件支持；但是，它也有不少缺点，主要表现在以下几个方面： 程序经地址重定位后就不能再移动了，因而不能重新分配内存，不利于
14、内存的有效利用。 程序在存储空间中只能连续分配，不能分布在内存的不同区域。 若干用户很难共享内存中的同一程序段，如若共享同意程序，则各用户必须使用自己的副本。 （2）动态地址重定位：动态地址重定位在程序装入内存时并没立刻进行地址重定位，而是在程序执行过程中进行地址重定位，它要求系统有硬件的支持，即地址重定位机构，它提供地址重定位寄存器BA，用于存放当前执行程序的物理内存基地址。当CPU执行指令要求访问内存时，地址重定位机构就会将程序中的逻辑地址与地址重定位寄存器BA中的值相加得到相应的物理地址。虽然，动态地址重定位需要硬件的支持，同时也带来许多优点，主要表现在以下几方面： 在执行过程中，用户程
15、序在内存可以移动，也可以将程序中暂时没有用的信息交换到外存中，需要时再将其交换进来，而不需每次进行地址重定位，这有利于内存的充分利用，也为实现虚拟技术奠定了基础。 程序不必连续存放在内存中，可以分散在内存的若干个不同区域。这样，可以让多个用户共享同一个程序段，有利于程序的重用。 3信息的共享与保护 在多道程序环境中，内存中有多道程序，它们各自占用自己的内存空间，在运行过程中是不能相互干扰的，一个程序不能随便访问另一个程序所占用的内存空间，否则，将会影响程序的正常执行，甚至破坏另一个程序，特别是操作系统本身的内存空间更要加以保护，否则将会影响系统的正常运行。信息共享的提出，主要有以下两方面的原因
16、： 一是为了提高内存的利用率。例如，两个程序共同调用一个子模块，如果不能共享，两个程序同时运行时，就要求在内存中有两份该子模块的副本，这样就浪费了内存空间，从而影响内存的利用率，也就影响了系统的性能。信息共享可以通过地址映射来实现。如图4.6所示：将程序A和程序B的逻辑地址空间的子模块都映射到同一个物理内存空间，这样，它们就可以共享同一个子模块，而内存中也只有一个子模块的副本。节省的内存空间的使用，提高了内存的使用效率。 二是为内存中进程之间的通信。我们可以在内存中开辟一块空间，用来实现两个或多个进程之间进行信息的交换，这就要求它们都能访问到这块内存空间。这也是内存信息共享的一种形式。2假脱机
17、技术 通过共享设备来模拟独享设备所采用的操作是假脱机操作，即在联机情况下外部设备设备同时操作。所使用的假脱机技术称之为假脱机技术。4内存的扩充 内存资源始终都计算机系统中最重要的资源之一，且价格比较高。因此，一般的计算机中配置的内存都不会太大，几十兆字节或几百兆字节较多，而这与现代计算机的地址总线决定能访问的逻辑地址空间相比，小得很多，32位的地址总线的计算机的逻辑地址空间就可达到4GB。理论上，实际的物理内存还有很大的增长空间，但是，价格问题，我们不可能在计算机中配置大内存。然而，现代的软件可是越做越大，有些软件要求使用大内存，而现有的内存往往又不能满足它的要求。 5.2 存储器的分区管理
18、5.2.1单一分区管理 5.2.2 固定分区管理 5.2.3 可变分区管理 存储管理方法是随着操作系统的发展而发展的，早期的操作系统主要采用的是分区管理，即将内存空间分为若干块，分别给不同的进程使用。分区管理主要有：单一分区、固定分区和可变分区管理三种，下面分别加以说明。5.2.1 单一分区管理 单一分区管理是操作系统最早的内存管理，当时还处在单道程序环境下，即内存中除了操作系统本身外，只允许有一道用户进程，因此，内存区域可以分成三块，分别是：系统区、用户程序区、空闲区。所有的内存空间除了操作系统占有的空间外，其余的都是给用户的，但是，一般用户进程不会刚好那么大，总是会有空闲的区域。 这部分空
19、间就被浪费了。若用户进程要求的内存大于用户可用空间，则用户进程是无法装入内存运行的。若要让大程序在小的内存空间中运行，则要求程序用覆盖技术和交换技术，这对程序员的要求较高。 单一分区管理的优点就是管理简单、易操作、无须特别的硬件支持；缺点是：它一个单用户单任务的系统，内存利用率低，无内存扩充能力。5.2.2固定分区管理 在多道程序环境下，固定分区是最简单的内存管理方法。它将操作系统占用空间以外的内存，即用户内存空间，分成大小固定的若干块，且这种划分方案一旦确定，在整个系统运行过程中是不会改变的，即分块数目和每块的大小都不会改变。在这样的分区方案中，若系统将用户内存空间分成N个分区，那么，该系统
20、将最多能运行N个用户程序，因为，每个分区只能装入一道作业。1划分方法固定分区的划分方法可以分为两种：分区大小相等和分区大小不等。 （1）分区大小相等：这种分区方案就是将用户内存空间分为大小相等的若干块。这种分法缺乏灵活性。当用户程序小于分区大小时，则会有一部分空间被利用，我们把分区中被程序占用后剩下不可用的空间称为“碎片”；当用户程序大于分区大小时，则该用户程序又无法装入内存而不能运行。因此，这种分区方法在一般的操作系统不被采用，但是，它在一定环境下还是很有用的，例如，在一些工业控制中，用来控制多个相同的对象的特定的系统中，正好要用这种固定分区的方法。（2）分区大小不等：将内存分成大小不等的若
21、干的分区，以适应不同大小的程序的需要，大的程序用大的分区，小的程序用小的分区。这样的分区方法使用更加灵活，效率也更高。2内存管理0KB为了实现固定分区的内存管理，要有相应的数据结构支持，我们可以用一张分区划分使用说明表来描述内存空间的有关特征信息。图片 表中记录每个分区的大小、起始地址、状态等信息，用状态来标记是否已分配。当用户作业提出申请时，存储管理进程就根据作业所需的内存容量当分区说明表中找一块末用的且能满足用户要求的分区给它，并将说明表中的状态位改成已用。当当用户作业提出申请时，若表中找不到能满足用户需求的块，则用户作业不能装入内存，即使内存末使用空间加起来超过该用户作业所需的容量，也不
22、能分配，这时，要给用户报告一个错误信息。分配后的内存情况如图4.7所示，阴影部分为空闲块。当内存中的进程运行完成后，要收回其占用的内存，只要在说明表将其对应的块的状态位改成末用即可。固定分区的内存管理方法简单、易实现，不要特殊的硬件支持，但是，其内存利用率很低，因为，每个用户作业不太可能与分区大小相等，总是会有“碎片”存在，总是会有浪费，也没有内存扩充能力。因此，它只适用于事先知道作业大小的系统。5.2.3 可变分区管理 可变分区管理又称动态分区管理。这种分配方式是根据作业的大小动态地划分分区，使分区的大小正好等于用户作业的大小。因此，各分区的大小是不定，一般大小是不等的，内存中分区的数目也是
23、不定的。开始时，内存中只有操作系统本身，其余的空间都是空闲的。当用户作业提出申请时，内存管理进程就在空闲的区域中分出一块与用户所需的容量一样的分区分配给用户。从而改变了固定分区中每个分区都有“碎片”的现象，大大提高了内存的利用率。可变分区管理与固定分区相比要复杂一些，涉及到的主要问题有：分区管理的数据结构、分区的分配算法和内存分配与回收三个方面。1数据结构 为了实现可变分区管理，就应有相应的数据结构来描述内存特征信息：内存中现有哪些分区，大小分别是多少，每个分区是已分配还是空闲等等。在固定分区我们分析过采用内存说明表的方法来描述内存的使用情况，但是，在可变分区中，分区是动态划分的，分区的数目事
24、先无法确定，随着动态的分配与回收，分区的数目是不断变化的，这样，分区说明表的大小也就无法确定。所以，在可变分区管理中，采用分区说明表的方法已经不适应了，为了更好的管理内存可变分区管理，现在一般采用双向链表来组织内存的空闲块。如图4.8所示：在这双向链表中，每个结点记录一个空闲块的信息，包括空闲的大小、起始地址等。2分配算法可变分区管理中，由于是动态划分内存分区，即在分配过程中来划分。因此，分配算法很重要，它会影响内存分区的划分，进而影响内存的使用效率。常见的分配算法有：（1）首次适应算法首次适应算法是一种比较简单的算法。分配时，从链首开始按顺序查找，查找到第一个能满足用户要求的空间止，然后从该
25、空闲块中划出与用户要求相等的分区分配给用户，余下的小空闲块再插入有序的空闲链表中。 若从链首到链尾都找不到能满足用户要求的空间，则返回用户装入失败的信息。该算法每次分配都是从链首开始，查找满足用户要求空间的时间开销较大，另外，还会使得链首余下的空闲块都是很小而难以再利用的“碎片”，不过会在链尾留下大的空闲块，以便大程序能够运行。（2）循环首次适应算法 该算法与首次适应算法相类似，是首次适应算法演变而来的，不一样的是，首次适应算法在分配时每次都头开始查找，而循环首次适应算法则要查找指针，确定下一次查找的开始位置，查找指针的值为上一次查找位置的下一个空闲块的指针。分配时，如果到最后一个空闲块还查找
26、不到满足用户要求的空闲，则应返回第一个空闲块继续查找。一直这循环。该算法会使得双向链中的空闲块的大小分布比较均匀，可以减少用在查找的时间开销。但是，这样会使得链表中的大空闲不断变少，甚至没有大空闲块，使得大程序无法运行。（3）最佳适应算法 所谓的“最佳”是指这种算法在分配时总是在链表中找一块与用户需求最接近的空闲块来划分。为了实现这种算法，事先要将空闲链表按升序排序。分配时，每一次都从头开始，找到第一个能满足用户需求的空闲块自然就是最接近用户需求的。从每一次的分配来看，这种算法是最佳的，但是，从全局来看，该算法末必就是最佳的，因为它每一次划分时总是余下最小空闲块，这样的空闲块可能再也不能被利用
27、，成为真正意义上的“碎片”。另外，每一次划分完后或回收时都要将空闲块插入有序的链表或重新排序，这也要有一定开销。（4）最坏适应算法 所谓的“最坏”是指这种算法在分配时总是在链中找一块最大的空闲块用来划分。这种算法也要求事先将链表排序，不过是按降序排列。分配时，总是从第一个空闲块中划分出一块满足用户要求的空闲块，因此，速度很快。若第一个空闲块都无法满足用户的需求，则本次分配失败。从局部看，这种算法似乎是最坏的，每次都最大的空闲块拿来划分，但是，从全局来看，也不一定是最坏的，因为，它每次划分完后余下的空闲块都相对比较大，还可以再利用。不过，经过一段时间的分配与回收后，空闲链表中大空闲块将会均匀地变
28、小，会导致大程序无法运行。3分配与回收可变分区的分配与回收要比固定分区复杂一些，下面分别加以说明。（1）内存分配对于某个系统来说，先要确定采用哪一种分配算法。分配时，从空闲链表的某一分配位置开始查找满足用户要求的空闲块，若都没找到，则给用户一个分配失败的信息；若找到，则从该空闲块中划分出用户需求大小的分区分配给用户，同时，修改相应的数据结构。若用户所需的内存大小为u.size，当前空闲内存块大小为m.size，则分配过程如图4.9所示。（2）内存回收对可变分区管理来说，空闲块一般采用链表方式组织，当进程运行完成后，其所占用的空间要释放，并且要将该空闲块插入到链表中，不仅如此，它还要看释放的内存
29、块与其相邻内存块情况进行相应的拼接操作，具体有以下四种情况： 当释放的内存块与其前相邻块B1也是空闲块时，则当前释放的内存块要与相邻的前一内存块B1拼接，形成一块更大的空闲块，这时不须在链表中增加一个节点，只要修改前一空闲块B1的大小即可。如图4.10（a）所示。当释放的内存块与其后相邻块B2也是空闲块时，则当前释放的内存块要与相邻的后一内存块B2拼接，形成一块更大的空闲块，这时必须在链表中增加一个新的节点，其大小为两块大小之和，并删除后一空闲块B2。如图4.10（b）所示。当释放的内存块与其前相邻块B1和后相邻块B2都是空闲块时，则当前释放的内存块要与相邻的B1和B2拼接，形成一块更大的空闲
30、块，这时也不须在链表中增加一个新的节点，只要修改B1的大小为三块大小之和即可。如图4.10（c）所示。当释放的内存块与其前相邻块B1和后相邻块B2都不是空闲块时，则当前释放的内存块单独成为一个空闲块，并形成一个新的节点插入到链表的相应位置。通过以上对可变分区管理的分析，我们可以知道，它和固定分区管理一样都会产生许多“碎片”，但是，可变分区管理在内存回收时会进行拼接，可以减少一些“碎片”。此外，可变分区管理中，还可以通过“紧凑”方法解决，具体的方法就是将内存中所有的用户进程移动，而将所有空闲分区拼接成一个大分区。不过这种方法要占用CPU时间，还要有动态地址重定位机构的支持。最后，我们总结下可变分
31、区管理的优缺点。可变分区管理的优点主要有：（1）支持多道程序设计，从而提高了系统资源的利用率。与固定分区管理相比，内存分配具有更大的灵活性。（2）对硬件要求少，算法简单、易实现。为了支持“紧凑”等技术，可变分区管理的地址变换要有基地址寄存器；在存储保护中，要有限长寄存器的支持。可变分区管理的缺点主要有：（1）内存利用率还不高，要求用户程序装入到内存的连续空间。（2）无法实现内存的扩充。（3）难以实现内存信息的共享。例4.1 物理内存中已有操作系统及用户进程若干，当前还有两块空闲分区F1（80KB）和F2（70KB），如图4,11（a）所示。现有三个作业A（50KB）、B（30KB）和C（70K
32、B）依次请求内存分配。分别写出采用首次适应算法、循环首次适应算法、最佳适应算法、最坏适应算法的内存分配情况。解：首次适应算法：采用首次适应算法时，每一次都从头开始检索，找到第一个能满足要求的空闲块即可，本题中，作业A先请求，于是根据首次适应算法将从F1中划分出50KB后，F1还余下30KB；当作业B请求分配内存时，正好将F1余下30KB分配给它；当作业C请求内存分配时，F2正好分配。分配后如图(b)所示。 循环首次适应算法：采用循环首次适应算法时，下一次检索空闲块是从上一次为上一次检索位置的下一个空闲块。本题中，正好和首次适应算法一样。 最佳适应算法：事先要将空闲链表按升序排序，分配时总是在链表中找一块与用户需求最接近的空闲块来划分。因此，F2在链表的前面，本题中，根据算法作业A是从F2中划出50KB，F2还余下20KB。此时，F2还是排在链表的前面，当分配作业B时，F2空间不够，只
