第四章 存储器管理

本章要点（1/4） 目标：了解简单存储器的管理方式和它们的实现方法。 重定位的基本概念 重定位的实质是什么，如何实现重定位？ 为什么要引入重定位？ 静态重定位适用于何种场合，它有何优缺点？ 动态重定位是为了解决什么问题而引入的？ 在连续分配方式、分页系统和分段系统中，分别是如何实现动态重定位的？

本章要点（2/4） 动态分区分配方式 什么是动态内存分配？ 在动态内存分配中如何提高内存利用率？ 造成动态分区分配方式内存浪费的主要原因是什么，它可以通过什么办法加以解决？ 动态分区分配算法可采用哪两种数据结构来描述分区的情况？可采用哪些算法来进行内存的分配和回收？ 在采用不同的分配算法时，系统是如何组织空闲分区表或空闲分区链的，它们又是如何进行分区的分配和回收的。

本章要点（3/4） 分页和分段存储管理方式 是在什么推动力的作用下，使内存管理由动态分区分配方式发展为分页存储管理方式？ 分页系统是如何将地址空间中的作业划分为若干个页，它又是如何进行内存分配的？ 掌握分页系统逻辑地址的结构。 为了进行逻辑地址到物理地址的转换，分页系统必须为每个作业配置什么样的数据结构并提供哪些硬件支持？ 为什么引入快表可加快分页系统存取指令和数据的速度？

本章要点（4/4） 分页和分段存储管理方式 由分页发展为分段，并进一步发展为段页式存储管理方式的主要推动力是什么？ 分段和段页式系统是如何管理作业的地址空间和内存空间的，它们的地址变换是如何完成的？ 试将分页系统与分段系统加以比较。 为什么分段系统比分页系统更容易实现信息的共享和保护？

本章内容 4.1 存储器的层次结构 4.2 程序的装入和链接 4.3 连续分配存储管理方式 4.4 对换（Swapping） 4.1 存储器的层次结构 4.2 程序的装入和链接 4.3 连续分配存储管理方式 4.4 对换（Swapping） 4.5 分页存储管理方式 4.6 分段存储管理方式

4.1 存储器的层次结构 7

4.1.1 多层结构的存储器系统 1、存储器的多层结构 理想存储器 速度快，能跟上处理机的速度 容量大 价格便宜 图4-1 计算机系统 4.1.1 多层结构的存储器系统 理想存储器 速度快，能跟上处理机的速度 容量大 价格便宜 1、存储器的多层结构 图4-1 计算机系统 存储层次示意 CPU寄存器 寄存器 高速缓存 主存储器 磁盘缓存 固定磁盘 可移动存储介质 可执行存储器 主存 速度 价格 存储容量 辅存

2、可执行存储器

4.1.2 主存储器与寄存器 1、主存储器 2、寄存器 主存储器：也称内存、主存或可执行存储器 寄存器 4.1.2 主存储器与寄存器 1、主存储器 主存储器：也称内存、主存或可执行存储器 CPU的控制部件只能从主存储器中取得指令和数据； CPU与外围设备交换的信息一般依托于主存储器地址空间。 寄存器 访问速度最快，完全能与CPU协调工作； 容量小、价格昂贵； 寄存器的长度一般以字（word）为单位。 2、寄存器

4.1.3 高速缓存和磁盘缓存 1、高速缓存 2、磁盘缓存 高速缓存： 磁盘缓存 容量大于寄存器，但比内存小，访问速度快于主存储器 4.1.3 高速缓存和磁盘缓存 1、高速缓存 高速缓存： 容量大于寄存器，但比内存小，访问速度快于主存储器 根据程序执行局部性原理，将主存中一些经常访问的信息存放在高速缓存中，减少访问主存储器的次数，提高程序执行速度。 磁盘缓存 存放外部存储器中频繁使用的一部分磁盘数据和信息 利用主存中的存储空间，来暂存从磁盘中读出的信息 2、磁盘缓存

4.2 程序的装入和链接

程序在成为进程前的准备工作 编辑→编译→链接→装入→运行 图4-2 对用户程序的处理步骤 编译 链接 装入 Compiler Linker Loder 图4-2 对用户程序的处理步骤

4.2.1 程序的装入 在可执行文件装入时需要解决可执行文件中地址（指令和数据）和内存地址的对应。由操作系统中的装入程序loader来完成。 4.2.1 程序的装入 在可执行文件装入时需要解决可执行文件中地址（指令和数据）和内存地址的对应。由操作系统中的装入程序loader来完成。 装入模块的三种装入方式： 绝对装入方式 可重定位装入方式 动态运行时装入方式

1、绝对装入方式(Absolute Loading Mode) 在可执行文件中记录内存地址，装入时不再作地址重 定位，直接定位在上述(即文件中记录的地址)内存地址。 绝对地址的产生： （1）由编译器完成； （2）由程序员编程完成。 对编译器而言，编程用符号地址，在编译或汇编时再 将符号地址转换为绝对地址。 优点：装入过程简单。 缺点：过于依赖于硬件结构，不适于多道程序系统

1、绝对装入方式(Absolute Loading Mode) 绝对地址 内存地址 1024 1024 JUMP 1424 1424 装入程序 1424 LOAD 2224 2224 2224 绝对装入模块

2、可重定位装入方式(Relocation Loading Mode) 由装入程序根据内存当时的实际使用情况，将装入模块装入到内存的适当地方。 重定位：在装入时对目标程序中的指令和数据地址的修改过程。 静态重定位：地址变换只是在装入时一次完成，以后不再改变。 缺点：一个程序通常需要占用连续的内存空间，程序装入内存后不能移动。不易实现共享。

2、可重定位装入方式(Relocation Loading Mode) 图 4-3 作业装入内存时的情况

3、动态运行时装入方式(Dynamic Run-time Loading) 在把装入模块装入内存后，并不立即把装入模块中的逻辑地址转换为物理地址，而是把这种地址转换工作推迟到程序真正执行时才进行。因此，装入内存后的所有地址都是逻辑地址。 优点： OS可以将一个程序分散存放于不连续的内存空间，可以移动程序，有利用实现共享。 能够支持程序执行中产生的地址引用，如指针变量（而不仅是生成可执行文件时的地址引用）。 缺点： 需要硬件支持（重定位寄存器），OS实现较复杂。

4.2.2 程序的链接 链接程序的功能： 是将经过编译或汇编后所得到的一组目标模块以及它们所需要的库函数，装配成一个完整的装入模块。 链接方式： 静态链接(static-linking) 装入时动态链接(Run-time dynamic-linking) 运行时动态链接(load-time)

1、静态链接方式(Static Linking) 静态链接：是在程序运行之前，先将各目标模块及它们所需的库函数链接成一个完整的装入模块，以后不再拆开的链接方式。 变换外部调用符号 对相对地址进行修改 图 4-4 程序链接示意图

2、装入时动态链接(Load-time Dynamic Linking) 用户源程序经编译后所得到的目标模块，是在装入内存时，采用边装入边链接的链接方式。 优点：便于软件版本的修改和更新 便于实现目标模块共享

3、运行时动态链接(Run-time Dynamic Linking) 在运行时，若发现一个被调用模块尚未装入内存，由OS去找到该模块，将它装入内存，并把它链接到调用者模块上。通常被链接的共享代码称为动态链接库(DLL)或共享库(shared library)。 优点： 共享：多个进程可以共用一个DLL，节省内存。 部分装入：一个进程可以将多种操作分散在不同的DLL中实现，而只将当前操作相应的DLL装入内存。 便于局部代码修改：即便于代码升级和代码重用； 便于运行环境适应：调用不同的DLL，就可以适应多种使用环境和提供不同功能。如：不同的显示卡只需厂商为其提供特定的DLL，而OS和应用程序不必修改。 缺点：链接开销、管理开销

4.3 连续分配存储管理方式

4.3 连续分配方式 连续分配方式： 指为一个系统或用户程序分配一个连续的内存空间。 单一连续分配 固定分区分配 动态分区分配 动态重定位分配

4.3.1 单一连续分配 单一连续分配方式：内存中仅驻留一道程序，整个内存区为一用户独占。 内存分为两个区域：系统区，用户区。 系统区仅供OS使用，通常位于内存的低端 用户区仅供用户使用，其中只能存放一道作业。 最简单，适用于单用户、单任务的OS。 优点：易于管理。 缺点：对要求内存空间少的程序，造成内存浪费；程序全部装入，很少使用的程序部分也占用内存

4.3.2 固定分区分配 又称定长分区或静态分区模式，是满足多道程序设计需要的最简单的存储管理技术 基本思想： 实现： 4.3.2 固定分区分配 又称定长分区或静态分区模式，是满足多道程序设计需要的最简单的存储管理技术 基本思想： 给进入主存的用户作业划分一块连续存储区域，把作业装入该连续存储区域，若有多个作业装入主存，则它们可并发执行。 实现： 系统启动时，系统操作员根据作业情况静态地把可分配的主存储器空间（用户空间）分割成若干个连续的区域，每个区域的位置固定，大小可相同也可不同，每个分区在任何时刻最多只装入一道程序执行

1、划分分区的方法 把内存划分为若干个固定大小的连续分区。 分区的划分方法： 分区大小相等：只适合于多个相同程序的并发执行（处理多个类型相同的对象）。 分区大小不等：多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区。 固定分区(大小相同) 固定分区(多种大小)

2、内存分配 内存分区使用表 作业调度方式 为了便于内存分配，通常将分区按大小进行排队，并为之建立一张分区使用表。 分区使用表包括：每个分区的起始地址、大小及状态 作业调度方式 当有一用户程序要装入时，由内存分配程序检索分区使用表，从中找出一个能满足要求的尚未分配的分区，分配给该程序，并将该表项中的状态置为“已分配”。 若未找到大小足够的分区，则拒绝为该用户程序分配内存。

3、固定分区分配评价 特点：适用于多道程序系统和分时系统 问题：可能存在内碎片和外碎片。 缺点： 支持多个程序并发执行 难以进行内存分区的共享。 比较适合已知程序（作业）大小和出现频率的情形 问题：可能存在内碎片和外碎片。 内碎片：占用分区之内未被利用的空间 外碎片：占用分区之间难以利用的空闲分区（通常是小空闲分区）。 缺点： 实际系统运行时，往往无法预知分区大小（太大，等同于“单用户分区模式”） 主存空间利用率仍然较低 无法适应动态扩充主存 分区数目预先确定，限制了多道运行程序的数量

图 4-5 固定分区使用表 ~ ~ (a) 分区说明表 (b) 存储空间分配情况 操作系统 20K 分区号 起始地址 长度 占用标志 1 未分配 2 32K 已分配 3 64K 4 128K 32K 作业A 64K 作业B 128K ~ ~ (a) 分区说明表 256K (b) 存储空间分配情况 图 4-5 固定分区使用表

4.3.3 动态分区分配 动态分区分配 又称变长分区模式 4.3.3 动态分区分配 动态分区分配 又称变长分区模式 基本思想：按作业的大小划分分区，但划分的时间、大小和位置均动态确定，系统在作业装入主存执行之前并不建立分区。存储空间的划分是在装作业时进行的。从可用的自由存储空间内，划出一个大小正好等于作业大小的存储区，并分配给这一作业。

1、分区分配中的数据结构 空闲分区表：用于记录每个空闲分区的情况。每个空闲分区占 一个表目，表目中包括分区序号、分区始址及分区的大小等数据项。 空闲分区链：用于实现对空闲分区的分配和链接。 前向指针 N个字节可用 后向指针 N+2 0（分配标识） 图 4-7 空闲链结构

2、动态分区分配算法 动态分区分配算法：为把一个新作业装入内存，须按照一定的分配算法，从空闲分区表或空闲分区链中，选出一分区分配给该作业。

3、分区分配操作 (1) 分配内存 图 4-8 内存分配流程

3、分区分配操作 (2) 回收内存（四种情况） 图 4-9 内存回收时的情况 1 F1 X B F1 B 2 A X F2 A F2 3 (2) 回收内存（四种情况） 1 F1 X B F1 B 2 A X F2 A F2 3 F1 X F2 F1 4 A X B A FX B 图 4-9 内存回收时的情况

F1 X B 1 F2 A X 2 A X B FX 4 图 4-10 内存回收流程

4.3.4 基于顺序搜索的动态分区分配算法 常用分配算法： 首次适应（FF）算法 循环首次适应（NF）算法 最佳适应（BF）算法 4.3.4 基于顺序搜索的动态分区分配算法 常用分配算法： 首次适应（FF）算法 循环首次适应（NF）算法 最佳适应（BF）算法 最坏适应（WF）算法 适用范围： 不太大的系统 系统中通常只设有一个空闲分区链

阴影部分表示已占用块，空白部分表示空闲块 申请40K内存 1、首次适应算法 （first fit, FF） 0KB 100KB 180KB 190KB 280KB 330KB 390KB 410KB 512KB 要求：空闲分区链以地址递增的次序链接 算法：从链首开始顺序搜索，直至找到一个大小能满足要求的空闲分区，从该分区中划出一块能放下作业的空间给请求者，剩下的空闲分区仍留在空闲链中。若未找到大小大于作业要求的大小，则分配失败。 缺点：低地址不断被划分，留下许多难以利用的、很小的空闲分区；因为每次查找都是从低地址开始，从而增加可用空闲分区查找的开销。

阴影部分表示已占用块，空白部分表示空闲块 申请40K内存 2、循环首次适应算法 （next fit, NF） 0KB 100KB 180KB 190KB 280KB 330KB 390KB 410KB 512KB 查找指针位置 该算法是由首次适应算法演变而成的。 算法：不从链首开始查找，从上次找到的空闲分区的下一空闲分区开始查找 要求：设置查找指针，指示下一次起始查询的空闲分区 采用循环查找方式 优点：减少了查找空闲分区的开销 缺点：缺乏大的空闲分区

阴影部分表示已占用块，空白部分表示空闲块 3、最佳适应算法 （best fit, BF） 阴影部分表示已占用块，空白部分表示空闲块 申请40K内存 0KB 100KB 180KB 190KB 280KB 330KB 390KB 410KB 512KB 要求：将空闲分区按容量从小到大形成空闲分区链。 算法：将能满足要求、又是最小的空闲分区分配给作业 缺点：留下许多难以利用的小空闲区

阴影部分表示已占用块，空白部分表示空闲块 4、最坏适应算法 （worst fit, WF） 阴影部分表示已占用块，空白部分表示空闲块 申请40K内存 0KB 100KB 180KB 190KB 280KB 330KB 390KB 410KB 512KB 要求：将空闲分区按容量从大到小形成空闲分区链。 算法：查找时只要看第一个分区能否满足作业要求 优点：产生碎片的几率最小；对中、小作业有利；查找效率很高 缺点：会使存储器中缺乏大的空闲分区

基于顺序搜索的动态分区分配算法的评价 引自操作系统概念第9版P363 Simulations have shown that both first fit and best fit are better than worst fit in terms of decreasing time and storage utilization. Neither first fit nor best fit is clearly better than the other in terms of storage utilization, but first fit is generally faster.

例： 采用动态分区分配方式管理内存，内存空间为640K，高端40K为系统区。当前用户内存区空闲。对下列的请求序列：作业1申请130K、作业2申请60K、作业3申请100K、作业2释放60K、作业4申请200K、作业3释放100K、作业1释放130K、作业5申请140K、作业6申请60K、作业7申请50K、作业6释放60K。画图表示出最佳适应算法进行内存分配和回收后内存的实际情况 作业1 作业5 130K 140K 作业2 190K 作业3 290K 作业4 空闲 490K 作业6 550K 作业7 600K 系统区 640K

4.3.5 基于索引搜索的动态分区分配算法 常用分配算法： 快速适应（QF）算法 伙伴系统 哈希算法 适用范围： 大、中型系统

1、快速适应（quick fit）算法（分类搜索法） 要求：将空闲分区根据容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，同时在内存中设立一张管理索引表，该表每个表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。 算法：根据进程长度，寻找能容纳它的最小空闲区链表，并取下第一块进行分配。 优点：查找效率高；既能保留大的分区，也不会产生内存碎片。 缺点：分区归还主存时算法复杂，系统开销较大；分配空闲分区时是以进程为单位，一个分区只属于一个进程，存在一定的浪费，且空闲分区划分越细，浪费越严重。

2、伙伴系统（buddy system） 伙伴系统：内存分区的大小为2k字节，l<=k<=m，其中：2l表示分配的最小分区的大小，而2m表示分配的最大分区的大小，通常2m是整个可分配内存的大小。空闲分区按分区的大小进行分类，对具有相同大小的所有空闲分区单独设立一个空闲分区双向链表，不同大小的空闲分区形成了k个空闲分区链表。 一个大小为2k，地址为x的内存块，其伙伴块的地址为buddyk(x)

2、伙伴系统（buddy system） 伙伴系统的分配算法： 伙伴系统的回收： 当有一个进程申请K字节时，首先计算一个i值，使2i-1<n<=2i，然后在空闲分区大小为2i的空闲分区链表中查找：若找到，则把该空闲分区分配给进程；否则，表明长度为2i的空闲分区已经耗尽，则在分区大小为2i+1的空闲分区链表中寻找，若存在2i+1的空闲分区，则把该空闲分区分为相等的两个分区，其中一个分区用于分配，另一个则加入分区大小为2i的空闲分区链表中。若不存在2i+1的空闲分区，则查找2i+2的空闲分区…… 伙伴系统的回收： 当一个进程释放内存时，回收过程需要查找该分区的伙伴是否也空闲，如果空闲，则与伙伴合并起来形成一个大分区。一次回收也可能要进行多次合并。

2、伙伴系统（buddy system） 伙伴系统分配举例： 假设内存的大小最初为256 KB，内核请求21KB的内存。 伙伴系统分配图

3、哈希（Hash）算法 分类搜索算法与伙伴系统算法的缺点：选择合适空闲链表的开销比较大，时间性能受影响。 哈希算法：利用哈希快速查找的优点，以及空闲分区在可利用空间表中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，表的每一个表项记录了一个对应的空闲分区链表表头指针。当进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，即得到在哈希表中的位置，从而得到相应的空闲分区链表，实现最佳分配策略。

4.3.6 可重定位分区分配 1、紧凑 引入紧凑的原因 紧凑 图 4-11 紧凑的示意 4.3.6 可重定位分区分配 1、紧凑 引入紧凑的原因 连续式分配中，总量大于作业大小的多个小分区不能容纳作业。 紧凑 通过作业移动将原来分散的小分区拼接成一个大分区。 作业的移动需重定位。 图 4-11 紧凑的示意

2、动态重定位 什么是动态运行时装入方式？ 动态重定位：地址变换过程是在程序执行期间，随着对每条指令或数据的访问自动进行的。 动态重定位需要硬件地址变换机构的支持。

2、动态重定位 图 4-12 动态重定位示意图 重定位寄存器 load 1,2500 365 相对地址 10000 load 1,2500 load 1,2500 365 2500 10000 10100 100 12500 2500 + 15000 5000 作业J 处理机一侧 存储器一侧 图 4-12 动态重定位示意图

3、动态重定位分区分配算法 图 4-11 动态分区分配算法流程图

4.4 对换（Swapping）

4.4.1 多道程序环境下的对换技术 1、对换的引入 2、对换的类型 4.4.1 多道程序环境下的对换技术 1、对换的引入 对换：是指把内存中暂不能运行的进程，或暂时不用的程序和数据换出到外存上，以腾出足够的内存空间，把已具备运行条件的进程，或进程所需要的程序和数据换入内存。 整体对换（进程对换）：以整个进程为单位 进行对换，广泛用于分时系统中，用于解决内存紧张问题，提高内存利用率。 部分对换 （页面对换或分段对换）：以“页”或“段”为单位进行对换。是实现请求分页和请求分段式存储管理的基础，目的是为了支持虚拟存储系统。 2、对换的类型

4.4.2 对换空间的管理 1、对换空间管理的主要目标 对换空间的管理：把外存空间分为文件区和对换区 文件区：存放文件 4.4.2 对换空间的管理 1、对换空间管理的主要目标 对换空间的管理：把外存空间分为文件区和对换区 文件区：存放文件 管理目标：提高文件存储空间的利用率 →采用离散分配方式 对换区：存放从内存中换出的进程 管理目标：提高进程换入、换出的速度 →管理策略采用连续分配方式，较少考虑外存中的碎片问题。

2、对换区空闲盘块管理中的数据结构 3、对换空间的分配与回收 数据结构：对对换区的空闲盘进行管理。 空闲分区表：盘块号、盘块数 空闲分区链 对换空间的分配与回收：与动态分区方式时的内存分配与回收方法雷同。 分配算法：FF、NF、BF、WF等 回收操作：4种情况 3、对换空间的分配与回收

4.4.3 进程的换出与换入 1、进程的换出 选择被换出进程： 换出过程： 因素：处于阻塞状态，且优先级最低；考虑在内存驻留时间。 4.4.3 进程的换出与换入 1、进程的换出 选择被换出进程： 因素：处于阻塞状态，且优先级最低；考虑在内存驻留时间。 换出过程： 对进程换出时只能换出非共享的程序和数据段。 先申请对换空间； 启动磁盘，并将换出进程的程序和数据传送到磁盘的对换区； 若传送过程无错误，则回收对换进程所占用的内存空间，并修改对换进程的PCB； 若内存中还有换出的进程，则继续执行换出过程，直至无阻塞进程为止。

2、进程的换入 查看可换入的进程 选择换入进程 申请内存 查看PCB Set：“就绪”、已换出 换出时间、优先级 申请成功：直接将进程从外存调入内存 申请失败：先换出内存中的某些进程，再将进程调入

4.5 分页存储管理方式

离散分配方式：将一个进程直接分散地分配到许多不相邻的分区中。 离散分配三种方式： 基本思想： 允许作业存放在若干个不相邻的分区中，既可免去移动内存信息而产生的工作量，又可充分利用主存空间，尽量减少主存碎片。 离散分配方式：将一个进程直接分散地分配到许多不相邻的分区中。 离散分配三种方式： 分页存储管理（考虑存储器利用率） 分段存储管理（考虑用户要求） 段页式存储管理(考虑存储器利用率和用户要求) 分页存储管理方式：在分页存储管理方式中，如果不具备页面对换功能，则是基本分页存储管理方式，或称为纯分页存储管理方式。 不具有支持实现虚拟存储器的功能 要求把每个作业全部装入内存后方能运行

4.5.1 页面与页表 1、页面和物理块 页面：将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面(page)或页。 页框：把内存空间分成与页面相同大小的若干个存储块，称为（物理）块或页框( frame) 内存的分配以块为单位，并允许将一个进程的若干页分别装入到多个不相邻的物理块中。 页内碎片的形成。

1、页面和物理块 页面大小 结论：页面的大小应选择得适中，且页面大小应是2的幂，通常为1KB~8 KB。 1）页面小： 优点：使内存碎片减小，从而减少了内存碎片的总空间， 有利于提高内存利用率； 缺点：使每个进程占用较多的页面，从而导致进程的页表过长，占用大量内存；还会降低页面换进换出的效率。 2）页面大： 优点：可以减少页表的长度，提高页面换进换出的速度， 缺点：会使页内碎片增大 结论：页面的大小应选择得适中，且页面大小应是2的幂，通常为1KB~8 KB。

2、地址结构 分页地址结构：页号+页内地址 一页的大小为2的整数次幂 地址的高位部分为页号 低位部分为页内地址 页面大小为：212=4KB 空间最多允许有1M页： 220=1M 32位地址

2、地址结构 页号P和页内地址d的求法 设A — 逻辑地址空间中的地址 L — 页面大小 则 页号P = INT [ A / L ] 页内地址d = [A] MOD L 例 ：A = 2170 B L = 1 KB P = INT [ A / L ] = INT [ 2170/1024 ] = 2 d = [ A ] MOD L = [ 2170 ] MOD 1024 =122

3、页表 页表由中存放着块号，通常还包括一存取控制字段。 作用：实现从页号到物理块号的地址映射 系统为每个进程建立的一张页面映射表。 图 4-14 页表的作用

4.5.2 地址变换机构 1、基本的地址变换机构 任务：实现从逻辑地址到物理地址的转换 通过设置页表寄存器实现，其中： 利用页面映射表，实现将逻辑地址中页号，转换为内存中的物理块号。 1、基本的地址变换机构 通过设置页表寄存器实现，其中： 对于较小系统，页表的功能可以由一组专门的寄存器来实现，一个页表项用一个寄存器，具有很高的访问速度。但寄存器成本较高。 现代计算机页表都很长，因此页表驻留在内存中。只在系统中配置一个页表寄存器(PTR)，用于存放运行进程的页表始址和页表长度。

1、基本的地址变换机构 N ① ② ③ 页表始址+页号*页表项长度 图 4-15 分页系统的地址变换机构

例：某分页系统，主存容量为64K，页面大小为1K，对一个4页大的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块中。将十进制的逻辑地址3500转换为物理地址的地址转换图 逻辑地址3500： 1.页号=3500/1K=3 2.页内地址=3500 MOD 1024=428， 3.查页表找到对应得物理块为7，物理地址=7*1K+428=7596

2、具有快表的地址变换机构 问题的提出：由于页表是存放在内存中的，这使CPU每次要存取一个数据时，都要两次访问内存。使计算机的处理速度降低近1/2。 “联想存储器“或“快表”：为了提高地址的变换速度，在地址变换机构中，增设的一个具有并行查寻能力的特殊高速缓冲存储器。 快表作用：存放当前访问的那些页表项。 快表效果：取决于对快表的访问命中率。 快表的大小：通常存放16-512个页表项。

2、具有快表的地址变换机构 ② ① ③ ④ 图 4-16 具有快表的地址变换机构

4.5.3 访问内存的有效时间 内存的有效访问时间(EAT)：从进程发出指定逻辑地址的访问请求，经过地址变换，到内存中找到对应的实际物理地址单元并取出数据，所需花费的总时间。 假定访问一次内存的时间为t，λ为查找快表所需要的时间，a为快表的命中率，则： 基本分页存储管理方式中：EAT=2t 引入快表的分页存储管理方式中： EAT=a × λ+(t+ λ)(1-a)+t=2t+ λ-t × a

例：在一个引入了快表的分页存储系统中，页表放在内存中，多数活动页表项都可以存在快表中。假定一次内存访问时间是100ns，查找快表的时间为20ns，若快表的命中率是85％，则访问内存的有效时间为多少？若快表的命中率为50％，那么访问内存的有效时间为多少？ 解：当快表的命中率为85％时，有效存取时间为： EAT=0.85×20＋(100+20)×(1－0.85) ＋ 100＝135ns 当快表的命中率为50％时，有效存取时间为： EAT=0. 5×20＋(100+20)×(1－0.5) ＋ 100＝170ns

4.5.4 两级和多级页表 现代大多数计算机系统，都支持非常大的逻辑地址空间，页表非常大，要占用相当大的内存空间。 4.5.4 两级和多级页表 现代大多数计算机系统，都支持非常大的逻辑地址空间，页表非常大，要占用相当大的内存空间。 例如32位的逻辑地址空间的分页系统，规定页面大小为4KB（占12位），则在每个进程页表中的页表项可达1M（20位）个，占4MB（每个页表项占4B）的内存空间，而且要求连续存放。 一般采用下面两个方法来解决这一问题。 1）对页表所需的存储空间，采用离散的分配方式； 2）只将当前需要的部分页表项调入内存，其余的表项仍驻留在磁盘上，需要时再调入。

1、两级页表(Two-Level Page Table) 方法：针对难以找到大的连续内存空间以存放页表的问题，采用将页表进行分页的办法，使每个页面的大小与内存物理块的大小相同，并进行编号。 实现了离散地将每个页表的页面分别放在不同的物理块中的目的。 外层页表（Outer Page Table）：为离散分配的页表页面建立的一张页表，该页表的每个页表项中记录了页表页面的物理块号。 图 4-17 两级页表逻辑地址结构

1、两级页表(Two-Level Page Table) 第0页页表 1 1 4 1011 1 2 6 1 1078 … 2 … 3 2 1023 4 第1页页表 … 5 114 1 115 6 n 2 1742 7 … … … 外部页表 1023 114 第n页页表 115 1468 1 … 2 1468 … … 1023 … 图 4-18 两级页表结构

1、两级页表(Two-Level Page Table) 具有两级页表的地址变换机构图

2、多级页表 对于32机器采用两级页表结构是合适的，但对于64位机器需采用三级、四级页表结构。

4.5.5 反置页表 1、反置页表的引入 反置页表的引入：现代计算机系统，进程的逻辑地址空间很大，为减少页表占用的内存空间，所以引入了反置页表。 反置页表：为每个物理块设置一个页表项，内容包括页号和页号隶属进程的标识符，并将它们按物理块的编号排序。

2、地址变换 根据进程标识符和页号检索反置页表 反置页表地址变换示意图 检索到匹配的页表项，则该页表项的序号i与页内地址就直接拼接成物理地址。 未检索到，则表明此页未装入内存。 反置页表地址变换示意图

例：某分页系统，主存容量为64K，页面大小为1K，对一个4页大的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块中。将十进制的逻辑地址1023、2500、4500转换为物理地址。

例：某系统有224字节的内存，固定分区的大小为216字节，1）进程表中的每个表项至少要用多少位来记录分配给进程的分区？2）界限寄存器必须要有多少位？ 答：1）224字节/ 216字节= 28字节，因此需要8位来存储28个分区中的一个。 2）固定分区的大小为216字节，故最大合法地址是216-1，二进制中216-1是16位，所以界限寄存器有16位。

例：在某简单分页系统中，有224字节的物理内存，256页的逻辑地址空间，且页的大小为210字节，问逻辑地址有多少位？ 答：逻辑地址空间包括了256=28个大小为 210字节的页，总的逻辑地址空间是 210×28=218字节，因此需要18位的地址来表示218字节地址空间。

例：某系统的用户空间共有32个页面，每页1KB，主存16KB。试问： 1）逻辑地址的有效位是多少？ 2）物理地址需要多少位？ 3）假定某时刻系统为用户的第0，1，2，3页分别分配的物理块号为5，10，4，7，试将虚地址0A5CH和093CH变换为物理地址。 答：1）逻辑地址空间包括了32=25个大小为 210字节的页，总的逻辑地址空间是 25×210=215字节，因此需要15位的地址来表示215字节地址空间。 2）物理地址=主存16KB=214，因此物理地址需要14位。 3）0A5CH=000101001011100B，前5位为逻辑地址中的页号，为00010B=2，即该地址的物理块号为4，表示为5位的二进制为00100B，因此0A5CH的物理地址是001001001011100，即125CH。同样的方法求得，093CH对应的物理地址是113CH。

4.6 分段存储管理方式

4.6.1 分段存储管理方式的引入 引入分段存储管理方式， 主要是为了满足用户和程序员的下述一系列需要： 方便编程 信息共享 信息保护 动态增长 动态链接

4.6.2 分段系统的基本原理 1、分段 用户程序划分 逻辑地址 4.6.2 分段系统的基本原理 1、分段 用户程序划分 按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名，且有一个段号。段号从0开始，每一段也从0开始编址，段内地址是连续的； 整个程序的地址空间分成多个段，各段长度不等； 分段方式已得到编译程序的支持，根据源程序自动产生段。 逻辑地址 31 16 15 0 段号 段内地址 16位 16位

1、分段 内存划分 内存空间被动态的划分为若干个长度不相同的区域，称为物理段，每个物理段由起始地址和长度确定。 内存分配 以段为单位分配内存，每一个段在内存中占据连续空间（内存随机分割，需要多少分配多少），但各段之间可以不连续存放。

2、段表 为每个进程建立一张段映射表（段表） 每个段在段表中占有一表项 表项记录了该段在内存中的起始地址（基址）和段的长度 段表实现了从逻辑段到物理内存区的映射 段表按段号从小到大的顺序排列，并包含该进程的全部段

2、段表 图 4-19 利用段表实现地址映射

3、地址变换机构 ① TL ④ ② ③ 图 4-20 分段系统的地址变换过程

4.6.3 信息共享 分段系统的共享 分页和分段系统的共享区别 可重入代码 允许若干个进程共享一个或多个段 4.6.3 信息共享 分段系统的共享 允许若干个进程共享一个或多个段 分页和分段系统的共享区别 在分段系统中比分页系统中更容易实现共享。 可重入代码 是一种允许多个进程同时访问的代码（只读不写）。

图 4-21 分页系统中共享editor的示意图

图 4-22 分段系统中共享editor的示意图

分段优缺点 优点 缺点 便于处理变化的数据结构 便于共享 提供了虚拟存储功能 提供了动态连接的便利 便于控制存取访问 要产生外部碎片，为存储紧缩付出处理机的代价 分段的最大尺寸受到主存大小的限制 在外存中管理可变尺寸的分段比较困难 与分页一样，提高了硬件成本

课堂练习 段号 段长 内存起始地址 660 219 1 14 3330 2 100 90 3 580 1237 4 96 1952 计算[0,430], [1,10], [2,500], [3,400], [4,20], [5,100]的内存地址 [0,430]：219+430=649 [1,10]：3330+10=3340 [2,500]：段内地址越界 [3,400]：1237+400=1637 [4,20]：1952+20=1972 [5,100]：段号越界

分页和分段的主要区别

4、分页和分段的主要区别

4.6.4 段页式存储管理方式 产生背景：结合页式段式优点，克服二者的缺点 基本思想 将用户程序按内容或过程（函数）关系分为若干个段 4.6.4 段页式存储管理方式 产生背景：结合页式段式优点，克服二者的缺点 基本思想 将用户程序按内容或过程（函数）关系分为若干个段 把每个段分成大小相等的若干个页 把主存分为与页大小相等的物理块 为每个用户程序创建一张段表，存放段表起始地址和段表长度 为每个段创建一张页表 地址结构：由段号、 段内页号、页内地址组成。

1、基本原理 基本思想 内存划分：按页式存储管理方案 内存分配：以页为单位进行分配

1、基本原理 图 4-23 作业地址空间和地址结构

图 4-24 利用段表和页表实现地址映射

2、地址变换过程 地址变换过程 以段号为索引在段表中找到该段对应的页表始址 以页号为索引找到该页对应的物理块号 物理块号和页内地址构成物理地址 需要3次访存

2、地址变换过程 ① ④ ② ③ 图 4-25 段页式系统中的地址变换机构

3、段页式存储优缺点 优点 缺点 1）与分页和分段一样，提供了虚拟存储器的功能； 2）以物理块为单位分配主存，无紧缩问题，没有页外碎片 3）便于处理变化的数据结构，段可动态增长； 4）便于共享； 5）提供了动态连接的便利； 6）便于控制存取访问。 缺点 增加了硬件成本；增加了软件复杂性和管理开销；同分页系统一样仍然存在页内碎片。