一、存储器的层次结构
对于通用计算机而言，存储层次至少应具有三级：最高层为 CPU 寄存器，中间为主存，最底层是辅存。
在较高档的计算机中，还可以根据具体的功能分工细划为寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等 6 层。
在存储层次中越往上，存储介质的访问速度越快，价格也越高，相对存储容量也越小。其中，寄存器、高速缓存、主存储器和磁盘缓存均属于操作系统存储管理的管辖范畴，掉电后它们存储的信息不再存在。固定磁盘和可移动存储介质属于设备管理的管辖范畴，它们存储的信息将被长期保存。
主存储器(简称内存或主存)是计算机系统中一个主要部件，用于保存进程运行时的程序和数据，也称可执行存储器。通常，处理机都是从主存储器中取得指令和数据的，并将其所取得的指令放入指令寄存器中，而将其所读取的数据装入到数据寄存器中；或者放置，将寄存器中的数据存入到主存储器中。早期的内存时由磁芯做成的，其容量一般为数十 KB 到数百 KB。随着 VLSI 的发展，现在的内存已由 VLSI 构成，其容量，即使是微机系统，也在数十 MB到数 GB，而且容量还在不断增加，而嵌入式计算机系统一般仅有几十 KB 到几 MB。CPU与外围设备交换的信息一般也依托于主存储器的地址空间。由于主存储器访问速度远低于 CPU 执行指令的速度，为缓和这一矛盾，在计算机系统中引入了寄存器和高速缓存。
寄存器具有与处理机相同的速度，故对寄存器的访问速度最快，完全能与 CPU 协调工作，但价格却十分昂贵，因此容量不可能做得很大。在早期的计算机中，寄存器的数目仅为几个，主要用于存放处理机运行时的数据，以加速存储器的访问速度，如使用寄存器存放操作数，或用作地址寄存器加快地址转换速度等。随着 VLSI 的发展，寄存器的成本也在迅速降低，对于当前的微机系统和大
中型机，可能有几十个甚至上百个，而寄存器的字长一般是32位或64位；而在小型的嵌入式计算机系统中，寄存器的数目一般仅有几个到几十个，而且寄存器的字长通常只有 8 位。
高速缓存是现代计算机结构中的一个重要部件，它是介于寄存器和存储器之间的存储器，主要用于备份主存中较常用的数据，以减少处理机对主存储器的访问次数，这样可大幅度地提高程序执行速度。高速缓存容量大于或远大于寄存器，而比内存约小两到三个数量级左右，从几十 KB 到几 MB，访问速度快于主存储器。根据程序执行的局部性原理(即程序在执行时将呈现出局部性规律，在一较短的时间内，程序的执行仅局限于某个部分)，将主存中一些经常访问的信息存放在高速缓存中，减少访问主存储器的次数，可大幅度提高程序执行速度。通常，进程的程序和数据是存放在主存储器中，每当使用时，被临时复制到一个速度较快的高速缓存中。当 CPU 访问一组特定信息时，首先检查它是否在高速缓存中，如果已存在，可直接从中取出使用，以避免访问主存，否则，再从主存中读出信息。如大多数计算机有指令高速缓存，用来暂存下一条欲执行的指令，如果没有指令高速缓存，CPU 将会空等若干个周期，直到下一条指令从主存中取出。由于高速缓存的速度越高价格也越贵，故有的计算机系统中设置了两级或多级高速缓存。紧靠内存的一级高速缓存的速度最高，而容量最小，二级高速缓存的容量稍大，速度也稍低。
二、程序的装入和链接
用户程序要在系统中运行，必须先将它装入内存，然后再将其转变为一个可以执行的程序，通常都要经过下面几个步骤：
- 编译，由编译程序对用户源程序进行编译，形成若干个目标模块。
- 链接，由链接程序将编译后形成的一组目标模块以及它们所需要的库函数链接在一起，形成一个完成的装入模块。
- 装入，由装入程序将装入模块装入内存。
1.无需进行链接的单个目标模块的装入
（1）绝对装入方式
当计算机系统很小，且仅能运行单道程序时，完全有可能知道程序将驻留在内存的什么位置。此时可以采用绝对装入方式。用户程序经编译后，将产生绝对地址（即物理地址）的目标代码。例如，事先已知用户程序(进程)驻留在从 R 处开始的位置，则编译程序所产生的目标模块(即装入模块)，便可从 R 处开始向上扩展。绝对装入程序按照装入模块中的地址，将程序和数据装入内存。装入模块被装入内存后，由于程序中的逻辑地址与实际内存地址完全相同，故不须对程序和数据的地址进行修改。
程序中所使用的绝对地址，既可在编译或汇编时给出，也可由程序员直接赋予。但在由程序员直接给出绝对地址时，不仅要求程序员熟悉内存的使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。因此，通常是宁可在程序中采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址。
（2）可重定位装入方式
绝对装入方式只能将目标模块装入到内存中事先指定的位置，这只适用于单道程序环境。而在多道程序环境下，编译程序不可能预知所编译的目标模块应放在内存的何处，因此，对于用户程序编译所形成的若干个目标模块，它们的起始地址通常是从 0 开始的，程序中的其它地址也都是相对于起始地址计算的。此时，不可能再用绝对装入方式，而应采用可重定位装入方式，它可根据内存的当前情况，将装入模块装入到内存的适当位置。
值得注意的是，在采用可重定位装入程序将装入模块装入内存后，会使装入模块中的所有逻辑地址与实际装入内存的物理地址不同。
例如，在用户程序的 1000 号单元处有一条指令 LOAD 1，2500，该指令的功能是将 2500 单元中的整数 365 取至寄存器 1。但若将该用户程序装入到内存的 10000～15000号单元而不进行地址变换，则在执行 11000 号单元中的指令时，它将仍从 2500 号单元中把数据取至寄存器 1 而导致数据错误。
而正确的方法应该是将取数指令中的地址 2500 修改成 12500，即把指令中的相对地址 2500 与本程序在内存中的起始地址 10000 相加，才得到正确的物理地址 12500。除了数据地址应修改外，指令地址也须做同样的修改，即将指令的相对地址 1000 与起始地址 10000 相加，得到绝对地址 11000。通常是把在装入时对目标程序中指令和数据的修改过程称为重定位。又因为地址变换通常是在装入时一次完成的，以后不再改变，故称为静态重定位。
（3）动态运行时的装入方式
可重定位装入方式可将装入模块装入到内存中任何允许的位置，故可用于多道程序环境；但这种方式并不允许程序运行时在内存中移动位置。因为，程序在内存中的移动，意味着它的物理位置发生了变化，这时必须对程序和数据的地址(是绝对地址)进行修改后方能运行。然而，实际情况是，在运行过程中它在内存中的位置可能经常要改变，例如，在具有对换功能的系统中，一个进程可能被多次换出，又多次被换入，每次换入后的位置通常是不同的。在这种情况下，就应采用动态运行时装入的方式。
动态运行时的装入程序在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是相对地址。为使地址转换不影响指令的执行速度，这种方式需要一个重定位寄存器的支持。
2.链接
源程序经过编译后，可得到一组目标模块。链接程序的功能是将这组目标模块以及它们所需要的库函数装配成一个完成的装入模块。在对目标模块进行链接时，根据进行链接的时间不同，可把链接分成三种。
- 静态链接。在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块，以后不再拆开。我们把这种事先进行链接的方式称为静态链接方式。
- 装入时动态链接。这是指将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式。即在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存，还要修改目标模块中的相对地址。
- 运行时动态链接。这是指对某些目标模块的链接，是在程序执行中需要该(目标)模块时，才对它进行的链接。
（1）静态链接方式
通过一个例子来说明在实现静态链接时应解决的一些问题。在图 (a) 中示出了经过编译后所得到的三个目标模块 A、B、C，它们的长度分别为 L、M 和 N。在模块 A 中有一条语句 CALL B，用于调用模块 B。在模块 B 中有一条语句 CALL C，用于调用模块 C。B 和C 都属于外部调用符号，在将这几个目标模块装配成一个装入模块时，须解决以下两个问题：
- 对相对地址进行修改。在由编译程序所产生的所有目标模块中，使用的都是相对地址，其起始地址都为 0，每个模块中的地址都是相对于起始地址计算的。在链接成一个装入模块后，原模块 B 和 C 在装入模块的起始地址不再是 0，而分别是 L 和 L+M，所以此时须修改模块 B 和 C 中的相对地址，即把原 B 中的所有相对地址都加上 L，把原 C 中的所有相对地址都加上 L+M。
- 变换外部调用符号。将每个模块中所用的外部调用符号也都变换为相对地址，如把B 的起始地址变换为 L，把 C 的起始地址变换为 L+M，如图 (b) 所示。这种先进行链接所形成的一个完整的装入模块，又称为可执行文件。通常都不再拆开它，要运行时可直接将它装入内存。这种事先进行链接，以后不再拆开的链接方式，称为静态链接方式。
（2）装入时动态链接
用户源程序经编译后所得的目标模块，是在装入内存时边装入边链接的，即在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存，还要按照上图所示的方式来修改目标模块中的相对地址。
装入时动态链接方式有以下优点：
- 便于修改和更新。对于经静态链接装配在一起的装入模块，如果要修改或更新其中的某个目标模块，则要求重新打开装入模块。这不仅是低效的，而且有时是不可能的。若采用动态链接方式，由于各目标模块是分开存放的，所以要修改或更新各目标模块是件非常容易的事。
- 便于实现对目标模块的共享。在采用静态链接方式时，每个应用模块都必须含有其目标模块的拷贝，无法实现对目标模块的共享。但采用装入时动态链接方式，OS 则很容易将一个目标模块链接到几个应用模块上，实现多个应用程序对该模块的共享。
（3）运行时动态链接
在许多情况下，应用程序在运行时，每次要运行的模块可能是不相同的。但由于事先无法知道本次要运行哪些模块，故只能是将所有可能要运行到的模块都全部装入内存，并在装入时全部链接在一起。显然这是低效的，因为往往会有些目标模块根本就不运行。比较典型的例子是作为错误处理用的目标模块，如果程序在整个运行过程中都不出现错误，则显然就不会用到该模块。
近几年流行起来的运行时动态链接方式，是对上述在装入时链接方式的一种改进。这种链接方式是将对某些模块的链接推迟到程序执行时才进行链接，亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由 OS 去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。
三、连续分配存储管理方式
为了能将用户程序装入内存，必须为它分配一定大小的内存空间。连续分配方式是最早出现的一种存储器分配方式，曾被广泛应用于上世纪 60~80 年代的 OS 中，该分配方式为一个用户程序分配一个连续的内存空间，即程序中代码或数据的逻辑地址相邻，体现在内存空间分配时物理地址的相邻。
连续分配方式可分为四类：单一连续分配、固定分区分配、动态分区分配以及动态可重定位分区分配。
1.单一连续分配
在单道程序环境下，当时的存储器管理方式是把内存分为系统区和用户区，系统区仅提供给 OS 使用，它通常是放在内存的低址部分。而用户区是指除系统区以外的全部内存空间，且用户区仅装有一道用户程序，即整个内存的用户空间由该程序独占。这样的存储器分配方式被称为单一连续分配方式。
2.固定分区分配
在多道程序系统中，为了能在内存中装入多道程序，且这些程序之间又不会发生相互干扰，于是将整个用户空间划分为若干个固定大小的区域，在每个分区中只装入一道作业，这样就形成了最早的、也是最简单的一种可运行多道程序的分区式存储管理方式。如果在内存中有四个用户分区，便允许四个程序并发运行。当有一空闲分区时，便可以再从外存的后备作业队列中选择一个适当大小的作业，装入该分区。当该作业结束时，又可再从后备作业队列中找出另一作业调入该分区。
（1）划分分区的方法
可用下面的两种方法将内存的用户空间划分为若干个固定大小的分区：
- 分区大小相等（指所有的内存分区大小相等）。其缺点是缺乏灵活性，即当程序太小时，会造成内存空间的浪费；当程序太大时，一个分区又不足以装入该程序，致使该程序无法运行。尽管如此，这种划分方式仍被用于利用一台计算机去控制多个相同对象的场合，因为这些对象所需的内存空间是大小相等的。例如，炉温群控系统，就是利用一台计算机去控制多台相同的冶炼炉。
- 分区大小不等。为了增加存储器分配的灵活性，应将存储器分区划分为若干个大小不等的分区。最好能对常在该系统中运行的作业大小进行调查，根据用户的需要来划分。通常，可把内存区划分成含有多个较小的分区、适量的中等分区以及少量的大分区，这样，便可根据程序的大小，为之分配适当的分区。
（2）内存分配
为了便于内存分配，通常将分区按大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态(是否已分配)，见图 (a) 所示。当有一用户程序要装入时，由内存分配程序检索该表，从中找出一个能满足要求的、尚未分配的分区，将之分配给该程序，然后将该表项中的状态置为“已分配”；若未找到大小足够的分区，则拒绝为该用户程序分配内存。存储空间分配情况如图 (b) 所示。
固定分区分配，是最早的多道程序的存储管理方式。由于每个分区的大小固定，必然会造成存储空间的浪费，因而现在已很少将它用于通用的计算机系统中。但在某些用于控制多个相同对象的控制系统中，由于每个对象的控制程大小相同，是事先编好的，其所需的数据也是一定的，故仍采用固定分区式存储管理方式。
3.动态分区分配
动态分区分配又称为可变分区分配，它是根据进程的实际需要，动态地为之分配内存空间。
在实现可变分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配与回收操作这样三个问题。
（1）动态分区分配中的数据结构
为了实现分区分配，系统中必须配置相应的数据结构，用来描述空闲分区和已分配分区的情况，为分配提供依据。常用的数据结构有以下两种形式：
- 空闲分区表。在系统中设置一张空闲分区表，用于记录每个空闲分区的情况。每个空闲分区占一个表目，表目中包括分区序号、分区始址及分区的大小等数据项。
- 空闲分区链。为了实现对空闲分区的分配和链接，在每个分区的起始部分，设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针；在分区尾部则设置一后向指针，通过前、后向链接指针，可将所有的空闲分区链接成一个双向链。为了检索方便，在分区尾部重复设置状态位和分区大小表目。当分区被分配出去以后，把状态位由“0”改为“1”，此时，前、后向指针已无意义。
（2）动态分区分配算法
为把一个新作业装入内存，须按照一定的分配算法，从空闲分区表或空闲分区链中选出一分区分配给该作业。
动态分区分配算法分为基于顺序搜索的动态分区分配算法和基于索引搜索的动态分区分配算法：
基于顺序搜索的动态分区分配算法是指一次搜索空闲分区链上的空闲分区，去寻找一个其大小能满足要求的分区。
基于索引搜索的动态分区分配算法是指当系统很大时，系统中的内存分区可能会很多，相应的空闲分区链就可能很长，这时候采用顺序搜索分区法可能会很慢。为了提高搜索空闲分区的速度，在大、中型系统中往往会采用基于索引搜索的动态分区分配算法。
- 基于顺序搜索的动态分区分配算法：首次适应、循环首次适应、最佳适应和最坏适应算法
- 基于索引搜索的动态分区分配算法：快速适应、伙伴系统和哈希算法
（3）分区的分配与回收操作
- 分配内存.系统应利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。设请求的分区大小为 u.size，表中每个空闲分区的大小可表示为 m.size。若 m.size-u.size≤size(size 是事先规定的不再切割的剩余分区的大小)，说明多余部分太小，可不再切割，将整个分区分配给请求者；否则(即多余部分超过 size)，从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区链(表)中。然后，将分配区的首址返回给调用者。
- 当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点，此时可能出现以下四种情况之一：① 回收区与插入点的前一个空闲分区 F1 相邻接。此时应将回收区与插入点的前一分区合并，不必为回收分区分配新表项，而只需修改其前一分区 F1 的大小。② 回收分区与插入点的后一空闲分区 F 2 相邻接。此时也可将两分区合并，形成新的空闲分区，但用回收区的首址作为新空闲区的首址，大小为两者之和。③ 回收区同时与插入点的前、后两个分区邻接。此时将三个分区合并，使用 F 1 的表项和 F1 的首址，取消 F2 的表项，大小为三者之和。④ 回收区既不与 F1 邻接，又不与 F2 邻接。这时应为回收区单独建立一新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。
4.动态可重定位分区分配
在连续分配方式中，必须把一个系统或用户程序装入一连续的内存空间。如果在系统中只有若干个小的分区，即使它们容量的总和大于要装入的程序，但由于这些分区不相邻接，也无法把该程序装入内存。例如，在内存中现有四个互不邻接的小分区，它们的容量分别为 10 KB、30 KB、14 KB 和 26 KB，其总容量是 80 KB。但如果现在有一作业到达，要求获得 40 KB 的内存空间，由于必须为它分配一连续空间，故此作业无法装入。这种不能被利用的小分区称为“零头”或“碎片”。
若想把作业装入，可采用的一种方法是：将内存中的所有作业进行移动，使它们全都相邻接，这样，即可把原来分散的多个小分区拼接成一个大分区，这时就可把作业装入该区。这种通过移动内存中作业的位置，以把原来多个分散的小分区拼接成一个大分区的方法，称为“拼接”或“紧凑”。由于经过紧凑后的某些用户程序在内存中的位置发生了变化，此时若不对程序和数据的地址加以修改(变换)，则程序必将无法执行。为此，在每次“紧凑”后，都必须对移动了的程序或数据进行重定位。
在动态运行时装入的方式中，作业装入内存后的所有地址都仍然是相对地址，将相对地址转换为物理地址的工作，被推迟到程序指令要真正执行时进行。为使地址的转换不会影响到指令的执行速度，必须有硬件地址变换机构的支持，即须在系统中增设一个重定位寄存器，用它来存放程序(数据)在内存中的起始地址。程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。地址变换过程是在程序执行期间，随着对每条指令或数据的访问自动进行的，故称为动态重定位。当系统对内存进行了“紧凑”而使若干程序从内存的某处移至另一处时，不需对程序做任何修改，只要用该程序在内存的新起始地址，去置换原来的起始地址即可。
动态重定位分区分配算法与动态分区分配算法基本上相同，差别仅在于：在这种分配算法中，增加了紧凑的功能，通常，在找不到足够大的空闲分区来满足用户需求时进行紧凑。
四、对换
对换技术也称为交换技术。最早是因为当时计算机的内存都非常小，为了使该系统能分时运行多个用户程序而引入了对换技术。系统把所有的用户作业都存放在磁盘上，每次只能调用一个作业进入内存，当该作业的一个时间片用完时，将它调至外存的后备队列上等待，在从后备队列上将另一个作业调入内存。这就是最早出现的分时系统中所用的对换技术。
要实现内、外存之间的交换，系统中必须有一台 I/O 速度较高的外存，而且其容量也必须足够大，能容纳正在分时运行的所有用户作业，目前最常使用的是大容量磁盘存储器。
1.多道程序环境下的对换技术
（1）对换的引入
在多道程序环境下，一方面，在内存中的某些进程由于某事件尚未发生而被阻塞运行，但它却占用了大量的内存空间，甚至有时可能出现在内存中所有进程都被阻塞，而无可运行之进程，迫使 CPU 停止下来等待的情况；另一方面，却又有着许多作业在外存上等待，因无内存而不能进入内存运行的情况。显然这对系统资源是一种严重的浪费，且使系统吞吐量下降。为了解决这一问题，在系统中又增设了对换(也称交换)设施。所谓“对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据调入内存。对换是提高内存利用率的有效措施，它可以直接提高处理机的利用率和系统的吞吐量。
在早期的 UNIX 系统中已引入了对换功能，该功能一直保留至今，各个 UNIX 版本实现对换功能的方法也大体上是一样的，即在系统中设置一个对换进程，由它将内存中暂时不能运行的进程调出到磁盘的对换区；同样也由该进程将磁盘上已具备运行条件的进程调入内存。在 Windows OS 中也具有对换功能。如果一个新进程在装入内存时发现内存不足，可以将已在内存中的老进程调至磁盘，腾出内存空间。由于对换技术的确能有效地改善内存的利用率，故现在已被广泛地应用于 OS 中。
（2）对换的类型
在每次对换时，都是将一定数量的程序或数据换入或换出内存。根据每次对换时所对换的数量，可将对换分为下面两类：
- 整体对换。 如果对换是以整个进程为单位的，便称之为“整体对换”或“进程对换”。这种对换被广泛地应用于分时系统中，其目的是用来解决内存紧张问题，并可进一步提高内存的利用率。
- 如果对换是以“页”或“段”为单位进行的，则分别称之为“页面对换”或“分段对换”，又统称为“部分对换”。
2.对换空间的管理
在具有对换功能的 OS 中，通常把外存分为文件区和对换区。前者用于存放文件，后者用于存放从内存换出的进程。由于通常的文件都是较长久地驻留在外存上，故对文件区管理的主要目标，是提高文件存储空间的利用率，为此，对文件区采取离散分配方式。然而，进程在对换区中驻留的时间是短暂的，对换操作又较频繁，故对对换空间管理的主要目标，是提高进程换入和换出的速度。为此，采取的是连续分配方式，较少考虑外存中的碎片问题。
为了能对对换区中的空闲盘块进行管理，在系统中应配置相应的数据结构，以记录外存的使用情况。其形式与内存在动态分区分配方式中所用数据结构相似，即同样可以用空闲分区表或空闲分区链。在空闲分区表中的每个表目中应包含两项，即对换区的首址及其大小，分别用盘块号和盘块数表示。
由于对换分区的分配是采用连续分配方式，因而对换空间的分配与回收，与动态分区方式时的内存分配与回收方法雷同。其分配算法可以是首次适应算法、循环首次适应算法或最佳适应算法。
3.进程的换入和换出
（1）进程的换入
进程的换出。每当一进程由于创建子进程而需要更多的内存空间，但又无足够的内存空间等情况发生时，系统应将某进程换出。其过程是：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动磁盘，将该进程的程序和数据传送到磁盘的对换区上。若传送过程未出现错误，便可回收该进程所占用的内存空间，并对该进程的进程控制块做相应的修改。
（2）进程的换出
进程的换入。系统应定时地查看所有进程的状态，从中找出“就绪”状态但已换出的进程，将其中换出时间最久(换出到磁盘上)的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。
五、离散存储管理方式的三种实现
连续分配方式会形成许多“碎片”，虽然可通过“紧凑”方法将许多碎片拼接成可用的大块空间，但须为之付出很大开销。如果允许将一个进程直接分散地装入到许多不相邻接的分区中，便可充分地利用内存空间，而无须再进行“紧凑”。基于这一思想而产生了离散分配方式。根据在离散分配时所分配地址空间的基本单位的不同，又可将离散分配分为下面三种：
- 分页存储管理方式。在该方式中，将用户程序的地址空间分为若干个固定大小的区域，称为“页”或“页面”。典型的页面大小为 1KB。相应地，也将内存空间分为若干个物理块或页框（frame），页和块的大小相同，这样可将用户程序的任一页放入任一物理块中，实现了离散分配。
- 分段存储管理方式。这是为了满足用户要求而形成的一种存储管理方式。它把用户程序的地址空间分为若干个大小不同的段，每段可定义一组相对完整的信息。在存储器分配时，以段为单位，这些段在内存中可以不相邻接，所以也同样实现了离散分配。
- 段页式存储管理方式。这是分页和分段两种存储管理方式相结合的产物。它同时具有两者的优点，是目前应用较广泛的一种存储管理方式。
六、分页存储管理方式
1.分页存储管理的基本方法
（1）页面和物理块
- 页面。分页存储管理是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号，从 0 开始，如第 0 页、第 1 页等。相应地，也把内存空间分成与页面相同大小的若干个存储块，称为(物理)块或页框(frame)，也同样为它们加以编号，如 0 # 块、1 # 块等等。在为进程分配内存时，以块为单位，将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”。
- 页面大小。在分页系统中的页面其大小应适中。页面若太小，一方面虽然可使内存碎片减小，从而减少了内存碎片的总空间，有利于提高内存利用率，但另一方面也会使每个进程占用较
多的页面，从而导致进程的页表过长，占用大量内存；此外，还会降低页面换进换出的效率。然而，如果选择的页面较大，虽然可以减少页表的长度，提高页面换进换出的速度，但却又会使页内碎片增大。因此，页面的大小应选择适中，且页面大小应是 2 的幂，通常为 1 KB～8 KB。
（2）地址结构
分页地址中的地址结构含有两部分：前一部分为页号 P，后一部分为位移量 W(或称为页内地址)，地址长度为 32 位，其中 0～11 位为页内地址，即每页的大小为 4 KB；12～31 位为页号，地址空间最多允许有 1 M 页。
（3）页表
在分页系统中，允许将进程的各个页离散地存储在内存的任一物理块中，为保证进程仍然能够正确地运行，即能在内存中找到每个页面所对应的物理块。为此，系统又为每个进程建立了一张页面映像表，简称页表。在进程地址空间内的所有页(0～n)，依次在页表中有一页表项，其中记录了相应页在内存中对应的物理块号。在配置了页表后，进程执行时，通过查找该表，即可找到每页在内存中的物理块号。可见，页表的作用是实现从页号到物理块号的地址映射。
即使在简单的分页系统中，也常在页表的表项中设置一存取控制字段，用于对该存储块中的内容加以保护。当存取控制字段仅有一位时，可用来规定该存储块中的内容是允许读/写，还是只读；若存取控制字段为二位，则可规定为读/写、只读和只执行等存取方式。如果有一进程试图去写一个只允许读的存储块时，将引起操作系统的一次中断。如果要利用分页系统去实现虚拟存储器，则还须增设一数据项。
2.地址变换机构
为了能将用户地址空间中的逻辑地址变换为内存空间中的物理地址，在系统中必须设置地址变换机构。该机构的基本任务是实现从逻辑地址到物理地址的转换。
由于页内地址和物理地址是一一对应的(例如，对于页面大小是 1 KB 的页内地址是 0～1023，其相应的物理块内的地址也是 0～1023，无须再进行转换)，因此，地址变换机构的任务实际上只是将逻辑地址中的页号，转换为内存中的物理块号。又因为页面映射表的作用就是用于实现从页号到物理块号的变换，因此，地址变换任务是借助于页表来完成的。
（1）基本的地址转换机构
页表的功能可以由一组专门的寄存器来实现。一个页表项用一个寄存器。由于寄存器具有较高的访问速度，因而有利于提高地址变换的速度；但由于寄存器成本较高，且大多数现代计算机的页表又可能很大，使页表项的总数可达几千甚至几十万个，显然这些页表项不可能都用寄存器来实现，因此，页表大多驻留在内存中。在系统中只设置一个页表寄存器 PTR(Page-Table Register)，在其中存放页表在内存的始址和页表的长度。平时，进程未执行时，页表的始址和页表长度存放在本进程的 PCB 中。当调度程序调度到某进程时，才将这两个数据装入页表寄存器中。因此，在单处理机环境下，虽然系统中可以运行多个进程，但只需一个页表寄存器。
当进程要访问某个逻辑地址中的数据时，分页地址变换机构会自动地将有效地址(相对地址)分为页号和页内地址两部分，再以页号为索引去检索页表。查找操作由硬件执行。在执行检索之前，先将页号与页表长度进行比较，如果页号大于或等于页表长度，则表示本次所访问的地址已超越进程的地址空间。于是，这一错误将被系统发现并产生一地址越界中断。若未出现越界错误，则将页表始址与页号和页表项长度的乘积相加，便得到该表项在页表中的位置，于是可从中得到该页的物理块号，将之装入物理地址寄存器中。与此同时，再将有效地址寄存器中的页内地址送入物理地址寄存器的块内地址字段中。这样便完成了从逻辑地址到物理地址的变换。
（2）具有快表的地址变换机构
由于页表是存放在内存中的，这使 CPU 在每存取一个数据时，都要两次访问内存。第一次是访问内存中的页表，从中找到指定页的物理块号，再将块号与页内偏移量 W 拼接，以形成物理地址。第二次访问内存时，才是从第一次所得地址中获得所需数据(或向此地址中写入数据)。因此，采用这种方式将使计算机的处理速度降低近 1/2。可见，以此高昂代价来换取存储器空间利用率的提高，是得不偿失的。
为了提高地址变换速度，可在地址变换机构中增设一个具有并行查寻能力的特殊高速缓冲寄存器，又称为“联想寄存器”(Associative Memory)，或称为“快表”，在 IBM 系统中又取名为 TLB(Translation Lookaside Buffer)，用以存放当前访问的那些页表项。此时的地址变换过程是：在 CPU 给出有效地址后，由地址变换机构自动地将页号 P 送入高速缓冲寄存器，并将此页号与高速缓存中的所有页号进行比较，若其中有与此相匹配的页号，便表示所要访问的页表项在快表中。于是，可直接从快表中读出该页所对应的物理块号，并送到物理地址寄存器中。如在块表中未找到对应的页表项，则还须再访问内存中的页表，找到后，把从页表项中读出的物理块号送地址寄存器；同时，再将此页表项存入快表的一个寄存器单元中，亦即，重新修改快表。但如果联想寄存器已满，则 OS 必须找到一个老的且已被认为不再需要的页表项，将它换出。
由于成本的关系，快表不可能做得很大，通常只存放 16～512 个页表项，这对中、小型作业来说，已有可能把全部页表项放在快表中，但对于大型作业，则只能将其一部分页表项放入其中。由于对程序和数据的访问往往带有局限性，因此，据统计，从快表中能找到所需页表项的机率可达 90%以上。这样，由于增加了地址变换机构而造成的速度损失，可减少到 10%以下，达到了可接受的程度。
3.两级和多级页表
现代的大多数计算机系统，都支持非常大的逻辑地址空间(2^32 B ～2^64 B )。在这样的环境下，页表就变得非常大，要占用相当大的内存空间。例如，对于一个具有 32 位逻辑地址空间的分页系统，规定页面大小为 4 KB 即 2^12 B，则在每个进程页表中的页表项可达 1 MB 之多。又因为每个页表项占用一个字节，故每个进程仅仅其页表就要占用 1 MB 的内存空间，而且还要求是连续的。显然这是不现实的。
可以采用下述两个方法来解决这一问题：(1) 对于页表所需的内存空间，可采用离散分配方式来解决难以找到一块连续的大内存空间的问题；(2) 只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。
（1）两级页表
针对难以找到大的连续的内存空间来存放页表的问题，可利用将页表进行分页的方法，使每个页面的大小与内存物理块的大小相同， 并为它们进行编号，即依次为 0# 页、1# 页，...，n# 页，然后离散地将各个页面分别存放在不同的物理块中。同样，也要为离散分配的页表再建立一张页表，称为外层页表(Outer Page Table)，在每个页表项中记录了页表页面的物理块号。
仍以前面的 32 位逻辑地址空间为例来说明。当页面大小为 4 KB 时(12 位)，若采用一级页表结构，应具有 20 位的页号，即页表项应有 1 兆个；在采用两级页表结构时，再对页表进行分页，使每页中包含 2^10 (即 1024)个页表项，最多允许有 2^10 个页表分页；或者说，外层页表中的外层页内地址 P2 为 10 位，外层页号 P1 也为 10 位。此时的逻辑地址结构可描述如下：
由图可以看出，在页表的每个表项中存放的是进程的某页在内存中的物理块号，如第0 # 页存放在 1 # 物理块中；1 # 页存放在 4 # 物理块中。而在外层页表的每个页表项中，所存放的是某页表分页的首址，如第 0 # 页表是存放在第 1011 # 物理块中。我们可以利用外层页表和页表这两级页表，来实现从进程的逻辑地址到内存中物理地址间的变换。
为了地址变换实现上的方便起见，在地址变换机构中同样需要增设一个外层页表寄存器，用于存放外层页表的始址，并利用逻辑地址中的外层页号，作为外层页表的索引，从中找到指定页表分页的始址，再利用 P 2 作为指定页表分页的索引，找到指定的页表项，其中即含有该页在内存的物理块号，用该块号和页内地址 d 即可构成访问的内存物理地址。
上述对页表施行离散分配的方法，虽然解决了对大页表无需大片存储空间的问题，但并未解决用较少的内存空间去存放大页表的问题。换言之，只用离散分配空间的办法并未减少页表所占用的内存空间。解决方法是把当前需要的一批页表项调入内存，以后再根据需要陆续调入。在采用两级页表结构的情况下，对于正在运行的进程，必须将其外层页表调入内存，而对页表则只需调入一页或几页。为了表征某页的页表是否已经调入内存，还应在外层页表项中增设一个状态位 S，其值若为 0，表示该页表分页尚未调入内存；否则，说明其分页已在内存中。进程运行时，地址变换机构根据逻辑地址中的 P 1 ，去查找外层页表；若所找到的页表项中的状态位为 0，则产生一中断信号，请求 OS 将该页表分页调入内存。
（2）多级页表
对于 32 位的机器，采用两级页表结构是合适的；但对于 64 位的机器，采用两级页表是否仍可适用的问题，须做以下简单分析。如果页面大小仍采用 4 KB 即 2 12 B，那么还剩下 52 位，假定仍按物理块的大小(2 12 位)来划分页表，则将余下的 42 位用于外层页号。此时在外层页表中可能有 4096 G 个页表项，要占用 16 384 GB 的连续内存空间。这样的结果显然是不能令人接受的，因此必须采用多级页表，将外层页表再进行分页，也就是将各分页离散地装入到不相邻接的物理块中，再利用第 2 级的外层页表来映射它们之间的关系。
对于 64 位的计算机，如果要求它能支持 2 64 B(= 1 844 744 TB)规模的物理存储空间，则即使是采用三级页表结构也是难以办到的；而在当前的实际应用中也无此必要。故在近两年推出的 64 位 OS 中，把可直接寻址的存储器空间减少为 45 位长度(即 2 45 )左右，这样便可利用三级页表结构来实现分页存储管理。
七、分段存储管理方式
存储管理方式随着 OS 的发展也在不断地发展。
当 OS 由单道向多道发展时，存储管理方式便由单一连续分配发展为固定分区分配。
为了能更好地适应不同大小的用户程序要求，存储管理方式又从固定分配，发展到动态分区分配。
为了能更好地提高内存的利用率，进而又从连续分配方式发展到离散分配方式--分页存储管理方式。
如果说推动存储管理方式发展的主要动力是提高内存利用率，那么，引入分段存储管理方式的目的，则主要是为了满足用户(程序员)在编程和使用上多方面的要求，其中有些要求是其它几种存储管理方式所难以满足的。因此，这种存储管理方式已成为当今所有存储管理方式的基础。许多高级语言和 C 语言的编译程序也都支持分段存储管理方式。
1.分段管理方式的引入
为什么要引入分段存储管理方式，：
- 一方面是由于通常的程序都可分为若干个段，如主程序段、子程序段 A、子程序段 B、... 、数据段以及栈段等，每个段大多是一个相对独立的逻辑单位
- 另一方面，实现和满足信息共享、信息保护、动态链接以及信息的动态增长等需要，也都是以段为基本单位的。更具体地说，分段存储管理方式更能符合用户和程序员的多方面需要。
（1）方便编程
通常，用户把自己的作业按照逻辑关系划分为若干个段，每个段都是从 0 开始编址，并有自己的名字和长度。
因此，程序员们都迫切地需要访问的逻辑地址是由段名(段号)和段内偏移量(段内地址)决定的，这不仅可以方便程序员编程，也可以使程序非常直观，更具可读性。
例如，下述的两条指令便是使用段名和段内地址：LOAD 1，[A] |〈D〉；STORE 1，[B] |〈C〉；其中，前一条指令的含义是将分段 A 中 D 单元内的值读入寄存器 1；后一条指令的含义是将寄存器 1 的内容存入 B 分段的 C 单元中。
（2）信息共享
在实现对程序和数据的共享时，是以信息的逻辑单位为基础的。
比如，共享某个过程、函数或文件。分页系统中的“页”只是存放信息的物理单位(块)，并无完整的逻辑意义，不便于实现共享，因为一个可共享的过程往往可能需要占用数十个页面；
然而段可以是信息的逻辑单位。因此，可以为该被共享过程建立一个独立的段，这就大大简化了共享的实现。为了实现段的共享，希望存储管理能与用户程序分段的组织方式相适应。
分段系统的一个突出优点，是易于实现段的共享，即允许若干个进程共享一个或多个分段，且对段的保护也十分简单易行。在分页系统中，虽然也能实现程序和数据的共享，但远不如分段系统来得方便。我们通过一个例子来说明这个问题。
例如，有一个多用户系统，可同时接纳 40 个用户，他们都执行一个文本编辑程序(Text Editor)。如果文本编辑程序有 160 KB 的代码和另外 40 KB 的数据区，则总共需有 8 MB 的内存空间来支持 40 个用户。如果 160 KB 的代码是可重入的(Reentrant)，则无论是在分页系统还是在分段系统中，该代码都能被共享，在内存中只需保留一份文本编辑程序的副本，此时所需的内存空间仅为1760 KB(40×40+160)，而不是 8000 KB。假定每个页面的大小为 4 KB，那么，160 KB 的代码将占用 40 个页面，数据区占 10 个页面。为实现代码的共享，应在每个进程的页表中都建立 40 个页表项，它们的物理块号都是 21 # ～60 # 。在每个进程的页表中，还须为自己的数据区建立页表项，它们的物理块号分别是 61 # ～70 # 、71 # ～80 # 、81 # ～90 # ，…，等等。
在分段系统中，由于是以段为基本单位的，不管该段有多大，都只需为该段设置一个段表项，因此使实现共享则容易得多。仍以共享 editor 为例，此时只需在（每个）进程 1 和进程 2 的段表中，为文本编辑程序设置一个段表项，让段表项中的基址（80）指向 editor 程序在内存中的其实地址即可。
可重入代码(Reentrant Code)又称为“纯代码”(Pure Code)，是一种允许多个进程同时访问的代码。为使各个进程所执行的代码完全相同，绝对不允许可重入代码在执行中有任何改变。因此，可重入代码是一种不允许任何进程对它进行修改的代码。但事实上，大多数代码在执行时都可能有些改变，例如，用于控制程序执行次数的变量以及指针、信号量及数组等。为此，在每个进程中，都必须配以局部数据区，把在执行中可能改变的部分拷贝到该数据区，这样，程序在执行时，只需对该数据区(属于该进程私有)中的内容进行修改，并不去改变共享的代码，这时的可共享代码即成为可重入码。
（3）信息保护
信息保护同样是对信息的逻辑单位为基础的，而且经常是以一个过程、函数或文件为基本单位进行保护的。
例如，假设希望函数 A 仅允许进程执行，而不允许读，更不允许写，那么，我们只须在包含了函数 A 的这个段上标上只执行标志即可。但是在分页系统中，函数 A 可能要占用若干个页面，而且其中的第一个和最后一个页面还会装有其他程序段的数据，它们可能有不同的保护属性，如可以允许进程读写，这样就很难对这些页面实施统一的保护，因此，分段管理方式能更有效和方便地实现对信息的保护功能。
（4）动态增长
在实际应用中，往往存在着一些段，特别是数据段，在使用过程中，由于数据量的不断增加，而使数据段动态增长，相应地它所需要的存储空间也会动态增长。
对于数据段究竟会增长到多大，事先又很难确切地知道。对此，很难采取预先多分配的方式进行解决。
前述的其它几种存储管理方式，都难以应付这种动态增长的情况，而分段存储管理方式却能较好地解决这一问题。
（5）动态链接
在之前对内存的介绍中，为了提高内存的利用率，系统只将真正要运行的目标程序装入内存，也就是说，动态链接在作业运行之前，并不是把所有的目标程序段都链接起来。
当程序要运行时，首先将主程序和它立即需要用到的目标程序装入内存，即启动运行。而在程序运行过程中，当需要调用某个目标程序时，才将该段（目标程序）调入内存并进行链接。
可见，动态链接要求的是以目标程序（即段）作为链接的基本单位。因此，分段存储管理方式非常适合于动态链接。
2.分段系统的基本原理
（1）分段
在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。例如，有主程序段 MAIN、子程序段 X、数据段 D 及栈段 S 等。每个段都有自己的名字。为了实现简单起见，通常可用一个段号来代替段名，每个段都从 0开始编址，并采用一段连续的地址空间。段的长度由相应的逻辑信息组的长度决定，因而各段长度不等。整个作业的地址空间由于是分成多个段，因而是二维的，亦即，其逻辑地址由段号(段名)和段内地址所组成。分段地址中的地址具有如下结构：
在该地址结构中，允许一个作业最长有 64 K 个段，每个段的最大长度为 64 KB。
分段方式已得到许多编译程序的支持，编译程序能自动地根据源程序的情况而产生若干个段。例如，Pascal 编译程序可以为全局变量、用于存储相应参数及返回地址的过程调用栈、每个过程或函数的代码部分、每个过程或函数的局部变量等等，分别建立各自的段。类似地，Fortran 编译程序可以为公共块(Common block)建立单独的段，也可以为数组分配一个单独的段。装入程序将装入所有这些段，并为每个段赋予一个段号。
（2）段表
在前面所介绍的动态分区分配方式中，系统为整个进程分配一个连续的内存空间。而在分段式存储管理系统中，则是为每个分段分配一个连续的分区，而进程中的各个段可以离散地移入内存中不同的分区中。为使程序能正常运行，亦即，能从物理内存中找出每个逻辑段所对应的位置，应像分页系统那样，在系统中为每个进程建立一张段映射表，简称“段表”。每个段在表中占有一个表项，其中记录了该段在内存中的起始地址(又称为“基址”)和段的长度。段表可以存放在一组寄存器中，这样有利于提高地址转换速度，但更常见的是将段表放在内存中。
在配置了段表后，执行中的进程可通过查找段表找到每个段所对应的内存区。可见，段表是用于实现从逻辑段到物理内存区的映射。
（3）地址变换机构
为了实现从进程的逻辑地址到物理地址的变换功能，在系统中设置了段表寄存器，用于存放段表始址和段表长度 TL。在进行地址变换时，系统将逻辑地址中的段号与段表长度 TL 进行比较。若 S>TL，表示段号太大，是访问越界，于是产生越界中断信号；若未越界，则根据段表的始址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存的起始地址，然后，再检查段内地址 d 是否超过该段的段长 SL。若超过，即 d>SL，同样发出越界中断信号；若未越界，则将该段的基址 d 与段内地址相加，即可得到要访问的内存物理地址。
像分页系统一样，当段表放在内存中时，每要访问一个数据，都须访问两次内存，从而极大地降低了计算机的速率。解决的方法也和分页系统类似，再增设一个联想存储器，用于保存最近常用的段表项。由于一般情况是段比页大，因而段表项的数目比页表项的数目少，其所需的联想存储器也相对较小，便可以显著地减少存取数据的时间，比起没有地址变换的常规存储器的存取速度来仅慢约 10%～15%。
（4）分页和分段的主要区别
由上所述不难看出，分页和分段系统有许多相似之处。比如，两者都采用离散分配方式，且都要通过地址映射机构来实现地址变换。但在概念上两者完全不同，主要表现在下述三个方面
- 页是信息的物理单位，采用分页存储管理方式是为实现离散分配方式，以消减内存的外零头，提高内存的利用率。或者说，分页仅仅是由于系统管理的需要，完全是系统的行为，而对用户是不可见的。而分段存储管理方式中的段则是信息的逻辑单位，它通常包含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。
- 页的大小固定且由系统决定。在采用分页存储管理方式的系统中，在硬件结构上，就把用户程序的逻辑地址划分为页号和页内地址两部分，也就是说是由机器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。
- 分页的用户程序地址空间是一维的。分页完全是系统的行为，故在分页系统中，用户程序的地址是属于单一的线性地址空间，程序员只需利用一个记忆符即可表示一个地址。而分段是用户的行为，故在分段系统中，用户程序的地址空间是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。
八、段页式存储管理方式
分页系统以页面作为内存分配的基本单位，能有效地提高内存利用率，而分段系统以段作为内存分配的基本单位，能很好地满足用户需要。
如果能对两种存储管理方式“各取所长”，则可以将两者结合成一种新的存储管理方式系统。这种新系统既具有分段系统的便于实现、分段可共享、易于保护、可动态链接等一系列优点，又能像分页系统那样很好地解决内存的外部碎片问题，以及可为各个分段离散地分配内存等问题。把这种结合起来形成的新系统称为“段页式系统”。
1.基本原理
段页式系统的基本原理，是分段和分页原理的结合，即先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名。
例如，作业有三个段：主程序段、子程序段和数据段；页面大小为 4 KB。在段页式系统中，其地址结构由段号、段内页号及页内地址三部分所组成，
在段页式系统中，为了实现从逻辑地址到物理地址的变换，系统中需要同时配置段表和页表。段表的内容与分段系统略有不同，它不再是内存始址和段长，而是页表始址和页表长度。
2.地址变换过程
在段页式系统中，为了便于实现地址变换，须配置一个段表寄存器，其中存放段表始址和段表长 TL。进行地址变换时，首先利用段号 S，将它与段表长 TL 进行比较。若 S<TL，表示未越界，于是利用段表始址和段号来求出该段所对应的段表项在段表中的位置，从中得到该段的页表始址，并利用逻辑地址中的段内页号 P 来获得对应页的页表项位置，从中读出该页所在的物理块号 b，再利用块号 b 和页内地址来构成物理地址。
在段页式系统中，为了获得一条指令或数据，须三次访问内存。第一次访问是访问内存中的段表，从中取得页表始址；第二次访问是访问内存中的页表，从中取出该页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理地址；第三次访问才是真正从第二次访问所得的地址中，取出指令或数据。
显然，这使访问内存的次数增加了近两倍。为了提高执行速度，在地址变换机构中增设一个高速缓冲寄存器。每次访问它时，都须同时利用段号和页号去检索高速缓存，若找到匹配的表项，便可从中得到相应页的物理块号，用来与页内地址一起形成物理地址；若未找到匹配表项，则仍须再三次访问内存。