(6)--第6章 基本存储管理操作系统原理.ppt

本章目录 6.1 存储管理的基本功能 6.2 分区存储管理 6.3 内存扩充技术 6.4 分页存储管理 6.5 分段存储管理 6.6 段页式存储管理6.1 存储管理的基本功能 6.1.1 存储系统的基本概念 6.1.2 存储管理的基本功能 6.1.1 存储系统的基本概念在计算机系统中，存储是有层次的。需要指出的是存储管理模块是针对内存的管理技术。6.1.1 存储系统的基本概念通常，内存被划分为系统区和用户区两部分。系统区：用于加载操作系统常驻内存部分（内核）；用户区：除系统区以外的全部内存空间，供当前正在执行的用户程序使用。在多道程序环境中，操作系统的存储管理模块需要对内存的用户区进行细分，以加载多个用户程序。1.物理地址和逻辑地址(1)物理地址和物理地址空间内存单元的地址称为物理地址，也称为绝对地址。物理地址反映了数据在内存的实际存放位置。物理地址的集合称为物理地址空间，也称为绝对地址空间、存储空间。在单道程序环境中，一个程序总是被装入内存用户区的起始空间去执行，即程序装入内存的物理地址范围是可以预知的。因此，程序员在编写程序时，可以使用物理地址指明要访问的数据或执行的指令在内存的位置。然而在多道程序环境中，程序员事先并不知道程序会被装入内存的哪个区域执行，因此编程时就无法使用物理地址了。1.物理地址和逻辑地址(2)逻辑地址和逻辑地址空间 在多道程序环境中，装入模块被加载到内存的位置是不确定的，因此编译链接环节无法将名地址转换成内存物理地址，便对目标模块从0 开始为其编址，并顺序分配给所有的名地址单元。1.物理地址和逻辑地址(2)逻辑地址和逻辑地址空间我们把这种与物理地址无关的访问地址称为逻辑地址或相对地址。逻辑地址的集合称为逻辑地址空间或相对地址空间。在多道程序环境中，编译程序产生的所有目标模块都是从0 地址开始编址的。当用链接程序将各个模块连接成一个完整的装入模块时，链接程序顺次按各个模块的逻辑地址构成统一的从0 开始编址的逻辑地址。2.地址重定位地址重定位负责把用户程序中的逻辑地址转换为内存中的物理地址。地址重定位又称为地址变换、地址映射。根据地址重定位的时机不同，地址重定位又分为：静态地址重定位动态地址重定位。(1)静态地址重定位静态地址重定位发生在程序被装入内存的过程中，在程序运行之前就完成了地址重定位。物理地址=装入内存的起始地址+逻辑地址(1)静态地址重定位优点：静态地址重定位不需要硬件支持。缺点：用户程序只能装入内存的一个连续存储区域上，不能装入多个离散区域。用户程序地址重定位后不允许在内存中移动。(2)动态地址重定位动态地址重定位发生在程序运行过程中，即当执行到某条指令且该指令需要进行内存访问时，再将逻辑地址转换为相应的物理地址。使用重定位寄存器存放正在执行的用户进程在内存的起始地址。物理地址=重定位寄存器的值+逻辑地址(2)动态地址重定位优点：支持程序执行过程在内存中移动。当程序在内存发生移动时，只需修改重定位寄存器为新的内存起始地址，就可以实现正确的地址重定位。支持程序在内存中离散存储。用每个离散部分的内存起始地址重置重定位寄存器，就可以实现正确的地址重定位。缺点：与静态地址重定位相比，动态地址重定位需要附加硬件支持（重定位寄存器），增加了机器成本。3.程序的装入方式程序经过编译、链接生成装入模块。系统在将一个装入模块装入内存时，根据是否需要地址重定位及采用的地址重定位方式，有以下三种程序装入方式：绝对装入方式可重定位装入方式动态运行时装入方式(1)绝对装入方式绝对装入方式是在单道程序设计技术阶段，操作系统采用的一种程序装入方式。在此方式下，装入模块使用的是物理地址，系统就按照此物理地址，将代码和数据装入内存的对应存储区，无须进行地址重定位。(2)可重定位装入方式可重定位装入方式是在多道程序设计技术阶段，操作系统采用的一种程序装入方式。在此方式下，装入模块使用的是逻辑地址，系统在将其装入内存的过程中，完成了逻辑地址到物理地址的重定位。此方式采用的是静态地址重定位，因此程序装入内存后不允许移动。(3)动态运行时装入方式动态运行时装入方式是在多道程序设计技术阶段，操作系统采用的一种程序装入方式。在此方式下，装入模块使用的是逻辑地址，系统在将其装入内存时未进行地址重定位，而是在此后的程序执行过程中，完成了逻辑地址到物理地址的重定位。此方式采用动态地址重定位，支持程序在内存中离散加载和装入内存后进行移动。6.1.2存储管理的基本功能存储管理的目标是合理有效地组织存储空间管理，进行内存的分配和回收，以支持多个进程并发执行，同时提高内存空间的利用率并方便用户使用。因此，存储管理应具有以下基本功能：内存的分配和回收。地址重定位。内存的共享与保护。内存的扩充。6.1.2存储管理的基本功能内存的分配与回收内存的分配和回收是存储管理的主要功能之一。存储管理要为每一个并发执行的进程分配内存，并在进程执行结束后及时回收该进程占用的内存。为此，需要设计合理有效的数据结构及内存分配和回收策略。6.1.2存储管理的基本功能地址重定位在多道程序环境中，用户程序的装入模块使用的是逻辑地址，而处理机是按物理地址访问内存的。为了保证程序的正确执行，存储管理需要把程序地址空间的逻辑地址变换成内存空间的物理地址，即具备地址重定位功能。6.1.2存储管理的基本功能内存的共享与保护在多道程序环境中，不同用户进程存在共享系统程序、用户程序或数据段的情况。为了提高内存空间利用率，存储管理模块不会为每个进程分别存储一个副本，而是在内存中提供一个共享副本。当然，除访问共享区外，存储管理要对各个存储区的信息进行保护，约束各个进程只能在自己的存储区执行，以防相互干扰和破坏。常见的内存保护方法有上下界保护法、保护键法、界限寄存器与CPU 的用户态或核心态工作方式相结合的保护方法。6.1.2存储管理的基本功能内存的扩充内存的容量是有限的。为了满足大作业和多个并发进程共存于内存的需求，存储管理需要通过软件方法在有限的内存空间运行比内存容量大得多的作业，从而让用户感觉到内存空间变大了。这种软件方法称为内存扩充技术，其本质仅是逻辑上的扩充。早期的覆盖技术和交换技术、现代操作系统普遍采用的虚拟内存技术都属于内存扩充技术。6.2 分区存储管理 6.2.1 固定分区存储管理 6.2.2 动态分区存储管理 6.2.3 动态重定位分区存储管理 连续分配存储管理连续分配存储管理方式是指为一个用户程序分配一个连续的内存空间。单一连续分配存储管理：内存的用户区仅装入一个程序，整个用户区被一个程序独占，因此该方式不支持多道程序环境。分区存储管理：将内存的用户区划分成多个区域，每个区域称为一个分区，每个分区允许装入至多一个用户程序，以实现内存同时存储多个运行程序的目的。分区存储管理又分为：固定分区存储管理动态分区存储管理动态重定位分区存储管理6.2.1 固定分区存储管理固定分区存储管理是满足多道程序设计要求的最简单的一种分区存储管理方案，曾用于IBM OS360 大型机的MFT 操作系统中。固定分区存储管理是指系统在初始化时，把用户区划分成若干固定大小的区域，在每个分区中可装入一个程序。分区一旦划分好，在系统运行期间就不能再重新划分。“固定”的含义：分区的数目和每个分区的大小是固定的。两种固定分区的划分方式：分区大小相等、分区大小不等。1.固定分区的划分方式(1)分区大小相等，如图6-4(a)所示。缺点：缺乏灵活性。若程序小于分区容量，则内部碎片严重，内存利用率低下。若程序大于分区容量，则无法装入到分区中，致使该程序无法运行。注：把内存中这种无法被利用的空间称为碎片；若碎片出现在分区内部，则称为内碎片1.固定分区的划分方式(2)分区大小不等，如图6-4(b)所示。系统将内存固定划分成多个较小分区、适量中等分区及少量大分区，并根据程序的大小选择适当的分区。小于8MB 的分区可以容纳更小的程序，减少了内碎片的数量；大于8MB 的大程序也有机会找到一个大分区运行。2.内存分配及采用的数据结构分区说明表：用于记录每个分区的大小、起始地址和状态等信息。操作系统利用分区说明表，完成内存的分配和回收工作。分区存储管理的优缺点优点：与单一连续分配方式相比，固定分区存储管理的内存利用率高，且支持多道程序设计，缺点：分区的数目在系统生成阶段已经确定，限制了系统并发进程的数目；分区大小固定不变，内碎片数量较多，导致内存空间的浪费。6.2.2 动态分区存储管理分区不是固定划分好的，而是根据进程的实际需要动态地划分。动态分区存储管理也称为可变分区存储管理。系统初始化后，除操作系统常驻内存部分之外，内存的用户区只有一个空闲分区。随后，分配程序根据进程的实际需求依次划分出分区，供进程使用。1.采用的数据结构分区说明表：描述内存的分区情况。空闲分区表或空闲分区链：描述内存中的空闲分区情况。空闲分区表：在系统中设置一张顺序表，用于记录每个空闲分区的情况，每个空闲分区对应一个表项，表项中包括空闲分区的起始地址和分区大小等数据项。空闲分区链：在系统中设置一个链表，每个结点对应一个空闲分区的信息，如空闲分区的起始地址和分区大小等。2.分区的分配和回收(1)分配分区首先，按照一定的算法，在空闲分区表或空闲分区链中从表头或链首开始，查找一个能够满足要求的空闲分区。若找到，则根据进程的实际大小，将该空闲分区划分成两部分，一部分交由进程装入，一部分形成新的空闲分区，然后更新分区说明表和空闲分区表（或链）。若找不到满足要求的空闲分区，则此次内存分配失败。2.分区的分配和回收(2)回收分区当进程运行完毕系统回收其占有的分区时，需要考虑回收分区是否与空闲分区邻接，若有邻接，则应加以合并。3动态分区分配算法顺序搜索分配算法空闲分区表的表头或链首开始依次搜索，直到找到第一个满足要求的分区或直到最后也未找到。分为首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法，区别主要在于各个空闲分区在空闲分区表或空闲分区链中排列的先后顺序不同。分区数目很多时，顺序搜索分配算法的效率会降低。索引搜索分配算法在大、中型操作系统中通常会采用索引搜索分配算法，如伙伴系统。(1)首次适应算法该算法按照地址递增的顺序组织空闲分区。优点：倾向于优先利用内存中低地址部分的空闲分区，将高地址部分的大空闲区保留下来满足大作业的使用要求。缺点：低地址部分不断被划分，致使留下许多难以利用的小空闲分区。每次查找又都是从低地址部分开始，增加查找可用空闲分区的开销。(2)循环首次适应算法循环首次适应算法是由首次适应算法变化而来的。为了避免低地址部分小空闲分区不断增加，在为进程分配内存空间时，不再是每次从表头或链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找。实现上，要设置一个起始检索指针，用于指示下一次开始检索的位置。优点：该算法能使内存中的空闲分区分布得更均匀，从而减少了查找可用空闲分区的开销。缺点：缺乏大的空闲分区。(3)最佳适应算法该算法将所有空闲分区按照分区大小依次递增的顺序进行组织，这样找到的满足要求的空闲分区，必然是“最优”的，即把能满足要求且又是最小的空闲分区分配给进程，避免“大材小用”。优点：较大的空闲分区可以被保留下来，交给大作业使用。缺点：内存中留下许多难以利用的小空闲区（称为外碎片），影响了内存分配的速度。(4)最坏适应算法该算法将所有空闲分区按照分区大小依次递减的顺序组织。这样，每次分配时，从表头或链首找到最大的空闲分区，按进程大小对空闲分区进行分配。优点：基本上留不下小的空闲分区，不易形成碎片。缺点：大的空闲分区被划分分配，当再有大作业时，系统往往不能满足要求。若一个8MB的进程提出了分配请求，下图给出了最佳适应算法、首次适应算法、循环首次适应算法和最坏适应算法的分配结果。(5)伙伴系统系统规定分区的大小均为2k（k为整数）.系统初始化后，整个用户区就是一个大的空闲分区。在系统运行过程中，由于不断地划分分区，将会形成若干不连续的空闲分区。将这些空闲分区按分区大小进行分类，对于同一长度类型的所有空闲分区，单独建立一个空闲分区表（链）。这样，系统中产生了k 个空闲分区表（链）。注：以建立空闲分区链为例讲解下面内容。(5)伙伴系统分区分配首先根据进程长度n，计算分区长度值i（满足2i-1n2i）。然后在分区大小为i 的空闲分区链中查找；若该空闲分区链不为空，则把该空闲分区链的第一个空闲分区分配给进程；否则，在分区大小为2i+1的空闲分区链中查找。若存在分区大小为2i+1 的一个空闲分区，则把该空闲分区分为大小相等的两个分区，这两个分区称为一对伙伴，其中一个分区用于分配，另一个分区链接到分区大小为2i的空闲分区链中。若分区大小为2i+1的空闲分区也不存在，则继续查找分区大小为2i+2 的空闲分区；若找到，则对其进行两次划分：第一次将其划分为分区大小为2i+1的两个分区，一个分区用于分配，另一个分区链接到分区大小为2i+1的空闲分区链中；第二次将第一次用于分配的空闲分区划分为分区大小2i 的两个分区，一个分区用于分配，另一个分区链接到分区大小为2i 的空闲分区链中，以此类推。(5)伙伴系统分区回收若已存在分区大小为2i 的空闲分区且和回收分区相邻，说明它们互为伙伴，则将其和伙伴合并为分区大小为2i+1的空闲分区。若该分区大小为2i+1的空闲分区也存在伙伴，则继续合并为分区大小为2i+2的空闲分区，以此类推。若回收分区时不存在伙伴，则新建一个结点，链接到对应长度的空闲分区链的末尾。(5)伙伴系统优点：伙伴系统分配分区和回收分区所花费的时间取决于查找空闲分区位置、分区划分和合并空闲分区所花费的时间。因此，索引搜索分配算法的分配效率比顺序搜索分配算法要高。缺点：伙伴系统的分区大小必须是2m，所以采用索引搜索分配算法时，其碎片问题比顺序搜索分配算法略严重，空间利用率较低。6.2.3 动态重定位分区存储管理考虑如下情况：系统的内存有若干小的空闲分区，其容量之和大于要装入进程的长度，但任何一个空闲分区都小于进程的长度。例如，图6-10(a)中，如果现在有一个大小为48MB的进程申请装入内存，由于无法为该进程分配一个连续的空闲分区，此种情况下，动态分区存储管理分配失败，该进程无法装入。6.2.3 动态重定位分区存储管理为了解决这一问题，可以对内存采用紧凑技术。紧凑是指移动内存中原来的进程，将分散的多个空闲分区拼接成一个大的空闲分区，如图6-10(b)所示。由于用户进程在内存中可能发生移动，因此必须配合动态地址重定位方法。这种采用紧凑技术的动态分区分配方式称为动态重定位分区存储管理。动态重定位分区分配算法动态重定位分区与动态分区存储管理的分配算法基本上相同，差别仅在于：前者增加了紧凑功能，即在找不到足够大的空闲分区来满足用户需求时，实施紧凑技术。6.3 内存扩充技术 6.3.1 覆盖技术 6.3.2 交换技术 在基本存储管理系统中，当并发运行的多个进程的长度之和大于内存可用空间时，多道程序设计的实现就会遇到很大的困难。内存扩充技术就是借助大容量的辅存在逻辑上实现内存的扩充，以解决内存容量不足的问题。介绍两种虚拟内存出现之前的内存扩充技术。6.3.1覆盖技术用于早期的单用户系统。覆盖技术：将一个程序按照逻辑结构划分成若干程序段。将不同时执行的程序段组成一个覆盖段小组。一个覆盖段小组的多个程序段可装入同一块内存区域，这个内存区域称为覆盖区。6.3.1覆盖技术图6-12(a)中，整个程序全部装入需要160KB 内存。采用覆盖技术，除main 函数必须占用10KB 的内存空间外，模块A 和模块B 可以共用一个30KB 大小的存储区，模块C、D、E 可以共用一个40KB 大小的存储区。因此，覆盖区的分配情况如图6-12(b)所示。这样，只要分配80KB 的内存空间，该程序就能够运行。6.3.1覆盖技术覆盖对用户是不透明的。为了提高覆盖的效果，用户在编写程序时就要精心安排好程序的覆盖结构，并用覆盖描述语言描述覆盖段小组。覆盖描述语言可以写入独立的覆盖描述文件中，并和目标程序一起提交给系统，也可附加在源文件中一起编译。6.3.2交换技术1.交换技术的概念交换技术是指把内存中暂时不能运行的进程或者暂时不用的代码和数据调到外存上，腾出足够的内存空间把已具备运行条件的进程或进程所需要的程序和数据从外存调入内存。交换技术与覆盖技术相比：交换技术不要求用户给出程序段之间的覆盖结构。交换技术主要在程序或进程之间进行。覆盖技术主要发生在同一个程序或进程内部。而且覆盖技术只能覆盖那些与覆盖程序段无关的程序段。交换技术最早用于单一连续分配系统解决多道程序运行的问题，后来加以发展用于分区存储管理。6.3.2交换技术图6-13为某系统实施交换技术的过程。作业1先被装入内存运行；当作业1时间片用完或因等待某一事件产生阻塞时，系统发生调度，把作业1 换到外存，作业2被装入内存运行；接下来，待作业2时间片用完或因等待某一事件产生阻塞时，系统把作业2的部分内容换到外存，调入作业3运行；之后，作业3时间片用完或因等待某一事件产生阻塞时，系统又把作业3的部分内容换到外存，再次将作业1装入内存运行；当作业1运行完毕时，系统把作业3的换出部分重新装入运行；待作业3运行完毕后，系统把作业2 的换出部分重新运行，直至作业2 运行完毕。这样借助交换技术，有限的内存空间装入运行了更多的作业。因此，交换技术是提高内存利用率的有效措施。6.3.2交换技术2.交换技术的类型整体交换。以整个进程为单位在内存和外存之间进行交换，其目的是减轻内存负荷，广泛用于多道程序系统。处理机中级调度的核心就是交换技术。部分交换。以进程的一部分为单位，如一个页或一个段，在内存和外存之间进行交换。部分交换是第7 章将要介绍的请求分页存储管理和请求分段存储管理的基础，其目的是支持虚拟存储器。6.3.2交换技术3.交换空间的管理为了便于管理，系统把外存分为文件区和对换区两部分。前者用于存放文件，后者用于存放从内存换出的进程。交换空间管理的主要目标是提高进程换入和换出的速度，采用的是连续分配方式。与动态分区分配方式类似，系统中也需要设置相应的数据结构，以记录外存的使用情况。6.4 分页存储管理 6.4.1 工作原理 6.4.2 地址变换 6.4.3 两级页表、多级页表和反置页表 6.4.4 分页存储管理的特点 分区存储管理会形成很多碎片，导致内存空间利用率下降。解决这个问题通常有两种办法：采用动态重定位分区存储管理，但要增加很多额外开销；采用离散分配方式，即系统为一个进程分配的未必是连续的内存区域，以提高内存空间利用率。如果离散分配的基本单位是页分页存储管理；如果离散分配的基本单位是段分段存储管理。6.4.1工作原理为了便于离散分配，分页存储管理把内存空间划分为若干大小相等的物理块，又称为页框。为了将程序装入内存，系统先将程序的逻辑地址空间按物理块的大小划分为若干大小相等的页，又称为页面。然后查看内存是否有足够的空闲物理块；若有，系统则以物理块为单位进行分配，为每一个页面分配一个空闲的物理块，当然分配的物理块未必连续；若没有，则此次分配失败。所以，分页存储管理要求一个程序的所有页面必须全部装入内存才可以运行，但可以不连续存放。6.4.1工作原理1.物理块和页面内存空间分块：将内存空间划分成若干大小相等的物理块，系统为每个物理块从0 开始顺序编号，该编号称为物理块号。逻辑空间分页：按照物理块的大小，系统将装入模块的逻辑地址空间也划分成若干大小相等的片，这个片称为页面或页。同样，将页面依次编号，编号从0 开始。当然，最后一页可能出现页内碎片。页或物理块的大小由计算机的地址结构决定，通常为2 的幂次方。6.4.1工作原理2.页表系统为每个进程创建一个数据结构，用于记录页与分配的物理块的对应关系，这个数据结构称为页表。页表的作用是实现从页号到物理块号的地址映射。6.4.1工作原理3.逻辑地址结构用户程序的逻辑地址空间是从0 开始依次编址组成的一维地址空间。分页后，每个逻辑地址又可以表示为“页号，页内地址”的形式，这种表示称为页式地址。给定一个逻辑地址A，若页面大小为L，则页号P和页内地址w 可由下面的公式求得：其中，INT 是取整函数，MOD 是取余函数。6.4.1工作原理例如，若页面大小为1KB，则逻辑地址1502在分页后处于1 号页内，页内地址为478，图6-15 给出了逻辑地址为1502 的分页情况。6.4.1工作原理实现上，页面大小一般选为2的幂次方，此时利用计算机系统本身的二进制地址结构，可以很方便地将逻辑地址转换为页内地址。例如，某系统逻辑地址长度为20位，分页的页面大小为4KB；从图6-16 中可以看出，分页后二进制逻辑地址的低12位地址A0A11为页内地址、高8位地址A12A19为页号。显然，逻辑地址空间最多容纳28=256个页面。6.4.1工作原理4.内存空间管理操作系统专门设置了一个数据结构记录内存的使用情况，包括物理块的总数、哪些物理块已经分配、哪些物理块还未分配等信息，这个数据结构称为内存块表。整个系统设置一个内存块表，每个物理块在表中占一个表项，记录该物理块的使用状态；若已分配，还需记录分配给哪个进程。内存块表有多种实现方法。位图、顺序栈或链接栈6.4.2地址变换1.基本地址变换机构进程在运行期间，经常需要做从逻辑地址到物理地址的地址变换。所以系统通常将页表驻留在内存中。页表寄存器：用于存放页表在内存的始址和页表的长度。某进程没有执行时，页表的始址和页表长度存放在该进程的PCB 中。当调度程序调度到该进程时，系统再将这两个数据装入页表寄存器。6.4.2地址变换基本地址变换机构地址变换过程将逻辑地址分成页号P和页内地址w两部分。将页号P 与页表寄存器存放的页表长度进行比较。若页号大于或等于页表长度，则表示本次访问的地址超出了进程地址空间，系统产生越界中断。若页号小于页表长度，则根据页表寄存器存放的页表始址，在内存中找到页表，查得该页号对应的物理块号将物理块号送入物理地址寄存器的高位部分；同时将页内地址w直接送入物理地址寄存器的块内地址字段。这样就得到了二进制物理地址，完成了从逻辑地址到物理地址的变换。6.4.2地址变换基本地址变换机构整个地址变换过程由硬件自动完成。可以看出，页表实际上是动态重定位技术的一种延伸。6.4.2地址变换基本地址变换机构由于页表存放在内存，所以每当CPU 执行读写内存的指令时都需要访问内存两次：第一次访问内存是读取页表，进行地址变换，获得物理地址；第二次是根据物理地址去内存访问所需要的数据。这导致读写内存的指令处理速度降低了近一半。分页存储管理采用离散分配方式提高内存空间利用率是以降低内存访问指令执行效率为代价的，这个代价是高昂的。具有快表的地址变换机构6.4.2地址变换2.具有快表的地址变换机构为了提高地址变换速度，系统在地址变换机构中增设一个高速联想存储器，又称为联想存储器，构成一张快表。快表用于存放当前访问最频繁的页表项。在具有快表的地址变换机构中，先在快表中查找是否有页号P对应的页表项。若该页号在快表中能找到，则可直接得到对应的物理块号形成物理地址。若该页号在快表中找不到，则再到内存中访问页表。6.4.2地址变换具有快表的地址变换机构有统计数据表明，从快表中找到所需页表项的概率可达90%以上。这样，因增加地址变换机构而造成的速度损失可减少到10%以下。6.4.3两级页表、多级页表和反置页表问题：页表很大，有可能一个物理块已经装不下页表。例如，某分页系统具有32 位逻辑地址空间，若页面大小为4KB，则进程的页表项最多可以有220个；假设每个页表项为4B，则该进程的页表大小为4MB，显然一个物理块已经装不下。解决方法：采用离散方式存储页表，即对页表进行分页，加载到多个物理块来存储，这种方法就是本节介绍的两级页表或多级页表。只将当前需要的部分页表项调入内存，其余的页表项放在外存，当有需要时再调入内存，这种方法需要借助第7 章的虚拟存储技术来实现。6.4.3两级页表、多级页表和反置页表1.两级页表系统对页表进行分页，并将页表的各个分页存放在不同的物理块中。系统为离散存放的页表再建立一张页表，由此形成了两级页表。外层页表：记录页表的每个分页在内存的存放情况，实现原始页表的离散存放内层页表：原始页表的各个分页。利用两级页表，实现从进程的逻辑地址到内存物理地址的变换。6.4.3两级页表、多级页表和反置页表两级页表的逻辑地址结构及地址变换过程如图6-20所示。以32位逻辑地址空间为例，若页面大小为4KB，则32位逻辑地址结构表达如下：低12位二进制地址：页内地址，高10位二进制地址：外层页号，中间10位二进制地址：外层页内地址。6.4.3两级页表、多级页表和反置页表实现上增设一个外层页表寄存器，用于存放外层页表的始址。由地址变换结构将逻辑地址分页，即逻辑地址变为（P1,P2,d）的形式。先用外层页表寄存器找到外层页表，在外层页表中查找P1对应的物理块，找到内层页表；然后在内层页表中查找P2对应的物理块，找到逻辑页对应的物理块号；最后根据该物理块号和页内地址d 装配成要访问的内存物理地址。6.4.3两级页表、多级页表和反置页表显然，采用两级页表后，访问内存的一条指令在执行时需要访问内存三次，更有必要采用具有快表的地址变换机构。6.4.3两级页表、多级页表和反置页表2.多级页表对于32 位的计算机，采用两级页表结构是合适的。但对于64 位的计算机，采用两级页表仍然不能解决问题。在实际应用中，人们发现对于64位的计算机，即使采用三级页表结构也是不行的。解决的方法有下面两种：近两年推出的64 位操作系统把可直接寻址的存储器空间减少为45位，由此可利用三级页表结构实现分页存储管理；采用反置页表。6.4.3两级页表、多级页表和反置页表3.反置页表常规页表：按页号进行排序，页表项中的内容是物理块号。反置页表：按物理块号排序，页表项中的内容是该物理块装入的页号P及所属进程的标识符pid。整个系统只有一个页表，每个物理块在表中有唯一对应的表项。6.4.3两级页表、多级页表和反置页表利用反置页表进行地址变换的过程：地址变换机构分页后，每个逻辑地址由进程标识符pid、页号P和页内地址w三部分组成；根据进程标识符pid和页号P在反置页表中检索。若找到与之匹配的表项，则该表项的序号i就是该逻辑页对应的物理块号；将物理块号i 与页内地址w 组合形成访问内存的物理地址；若搜索整个反置页表也没有找到相匹配的页表项，则表示发生非法地址访问，即该页目前尚未调入内存。6.4.4分页存储管理的特点分页存储管理在现代操作系统中被广泛应用。优点：实现了离散存储，减少了内碎片，提高了内存利用率。缺点：仍然存在页内碎片；不方便进行信息共享；不支持动态增长；当内存中没有足够空间装下整个程序时，程序仍然无法运行。6.5 分段存储管理 6.5.1 段的引入 6.5.2 工作原理 6.5.3 地址变换 6.5.4 分段存储管理和分页存储管理的区别 6.5.1 段的引入分页存储管理无法满足用户在编程和使用上的需要，主要表现在以下几点。(1)不方便编程。通常，用户把编写的程序按照逻辑关系划分成若干部分，如主函数、子函数、全局变量和数据集等。每个部分都是相对独立的逻辑单位，且长度不确定。因此，无法以页为单位组织每个部分。(2)不便于信息共享。对程序和数据的共享是以信息的逻辑单位为基础的，如共享某个函数。而页只是存放信息的物理单位，并无完整的意义，因而不便于实现页的信息共享。(3)不便于信息保护。为了防止其他程序对某程序和数据的破坏，必须采取某些保护措施，对内存中的信息保护更适合以信息的逻辑单位开展。6.5.1 段的引入(4)不允许动态增长。分页存储管理采用的是首地址从0 开始的一维线性地址空间。在实际应用中，程序的某些部分特别是数据部分，在使用过程中会不断增长。而一维线性地址空间难以应付动态增长带来的地址冲突。(5)不便于动态链接。动态链接是指在作业运行时，实现目标模块的链接。显然，用一维线性地址形式无法处理链接时的地址冲突。为了满足用户在编程和使用上的要求，迫切需要一个信息的逻辑单位。该逻辑单位允许长度不相等，为支持其动态增长和动态链接，每个逻辑单位都是从0 开始独立编址。这个信息的逻辑单位称为段。6.5.2 工作原理1.分段作业的地址空间被划分成若干段，每个段都是一组有意义的逻辑信息集合。例如，一个程序由主程序段main、子程序段list和数据段data 等组成。每个段都是从0 开始编址，各段的长度并不要求相等。根据需要，段也可以动态增长。为了区分，每个段都有自己的名字。为了方便管理，系统为每个段规定一个段号。一般规定每个作业的段号从0开始顺序编号，如0 段，1 段，2 段，。6.5.2 工作原理程序分段后，逻辑地址由两部分组成：段号s（或段名）和段内地址d。如指令“LOAD A,1|;”的含义是将1 段中160 单元的值读出，给寄存器A 赋值。在分段存储管理中，作业的逻辑地址空间是二维的。6.5.2 工作原理2.内存空间管理以段为单位申请内存空间。系统根据段的长度，为每个段分配一块连续的内存区域；但在内存中，段与段之间未必连续。为了给段分配内存空间，需要了解内存分区的情况、空闲分区的大小和位置。因此，内存空间的管理采用和动态分区存储管理相同的空闲分区管理方法。即把内存的各个空闲分区组织成空闲分区表或空闲分区链。6.5.2 工作原理3.段表系统为每个进程建立一个段表，用来记录每个逻辑段在内存的存放始址和相关信息。每个段对应一个段表项，包含段号、段长、基址等信息。段表实现了从逻辑段到物理内存的映射。6.5.3 地址变换段表寄存器：用于存放段表在内存的始址和段表长度。地址变换过程：首先将逻辑地址中的段号s 与段表长度进行比较。如果段号s 大于或等于段表长度，表示没有该段，访问越界，产生越界中断。若段号未越界，则根据段表始址和段号，访问该段的段表项。将段表中记录的该段始址与段内地址相加，得到要访问的内存的物理地址。6.5.3 地址变换当段表放在内存时，每访问内存一个数据，需要访问内存两次，从而成倍地降低了计算机的工作速率。解决方法：增设一个联想存储器，用于保存最近常用的段表项。6.5.4 段和页的区别页是信息的物理单位。而段是信息的逻辑单位，它含有一组有意义的相对完整的信息。分页是系统管理的需要而不是用户的需要。分段是为了能更好地满足用户的需要。页的大小是固定的，由系统决定，即系统中只能有一种大小的页面。而段的长度是不固定的，取决于用户所编写的程序。分页的逻辑地址空间是一维的，而分段的逻辑地址空间是二维的。6.6 段页式存储管理 6.6.1 工作原理 6.6.2 地址变换 分段存储管理，虽然段与段之间可以离散存储，但同一个段必须连续存储，即要为每个段找一个连续的存储区，若找不到连续的存储区，则分配失败。因此，问题：一个段是否可以离散存储？将分页存储管理和分段存储管理结合起来段页式存储管理。6.6.1 工作原理将用户程序按照逻辑关系划分成若干段，每段都是从0 开始编址，所以逻辑地址空间和分段存储管理相同，都是二维的逻辑地址空间，其逻辑地址形式为（段号，段内地址）。在内存空间管理上，采用和分页存储管理相同的处理方法，将内存划分为若干大小相等的物理块，以物理块为单位进行内存空间的分配。当某个进程申请装入内存执行时，在为每个段分配内存空间时，首先将该段划分成若干页，为每个页分配一个空闲的物理块，同时为该段建立一个页表来记录段中每一个页与物理块的对应关系。为记录所有段的整体存储情况，系统为每个进程再设立一个段表来记录每个段的页表信息，包含页表长度和页表在内存的存储位置。图6-23 给出了段页式存储管理下段表和页表的映射关系图。6.6.2 地址变换段页式存储管理的地址变换过程如图6-24 所示。6.6.2 地址变换首先，由地址变换机构根据页的大小，将段内地址w转换为页号P和页内地址d。然后，将段号s与段表长度进行比较。若段号s大于或等于段表长度，则产生越界中断。若段号s不越界，则通过段表寄存器的段表始址找到该段在内存的段表，从段表中查得该段对应的页表存放地址和页表长度。将段内页号P 与该段对应的页表长度进行比较。若段内页号P大于或等于页表长度，则产生一个越界中断。若段内页号P小于页表长度，则通过页表始址找到该段的页表，查得页号P对应的块号b。再利用块号b和页内地址d组合，形成物理地址。在段页式存储管理下，访问内存的一条指令或一个数据，需要访问内存三次。第一次是访问内存中的段表，从中取得页表始址；第二次是访问内存中的页表，从中取得该页所在的物理块号，并将该物理块号与页内地址组合，形成物理地址；第三次是根据物理地址，访问内存的指令或数据。这使得访问内存的次数增加了近两倍。为了提高执行速度，与分页存储管理和分段存储管理类似，在地址变换机构中有必要增设一个高速联想存储器，构建一张快表。小结存储管理是操作系统的一个重要内容，管理的是内存空间。在虚拟存储技术出现之前，基本存储管理分为连续分配存储管理和离散分配存储管理。前者包括单一连续存储管理、固定分区存储管理、动态分区存储管理和动态重定位分区存储管理；后者则有分页、分段和段页式三种存储管理方式。