操作系统原理第3_1~2章_存储管理蒲晓蓉

1、内存内存OS 图图3.1 3.1 进程执行时的寻址进程执行时的寻址当前栈顶当前栈顶进程控制信息进程控制信息程序入口点程序入口点地址值增加地址值增加进程控制块进程控制块程序程序栈栈数据数据访问数据访问数据分支指令分支指令进程映像进程映像 CPUCPU地址管理部件地址管理部件程序指令程序指令物理地址物理地址地址总线地址总线逻辑地址逻辑地址图图3.2 CPU3.2 CPU中的地址管理部件工作示意图中的地址管理部件工作示意图PCB3 数据数据代码代码PCB2 代码代码数据数据PCB1数据数据代码代码 进程进程1进程进程2进程进程3图图3.3 进程之间共享代码和数据进程之间共享代码和数据 8MB8MB8

2、MB8MB8MB操作系统操作系统8MB(a)等长分区等长分区图图3.4 固定分区划分固定分区划分操作系统操作系统8MB2MB8MB4MB12MB20MB(b)异长分区异长分区图图3.4 固定分区划分固定分区划分 (FFA：First Fit Algorithm)(FFA：First Fit Algorithm)(FFA：First Fit Algorithm)图图3.8 利用紧凑技术消除外零头利用紧凑技术消除外零头(a) 紧凑之前紧凑之前24MB10MBOS 8MBP7 16MBP2 10MBP4 10MBP6 10MB20MB10MB(b)紧凑以后紧凑以后64MBOS 8MBP7 16MBP

3、2 10MBP4 10MBP6 10MB(NFA: Next-Fit Algorithm) (NFA: Next-Fit Algorithm)(BFA：Best Fit Algorithm) (BFA：Best Fit Algorithm) (WFA：Worst Fit Algorithm)(WFA：Worst Fit Algorithm)(Buddy System) P1 申请申请100KBP2 申请申请200KBP3 申请申请120KBP4 申请申请300KB系统初始状态系统初始状态P2、P3结束结束P5 申请申请160KBP1执行结束执行结束P5执行结束执行结束P4执行结束执行结束1MB

4、 P1 128KB 256KB 512KB P1 128KB P2 512KB P1 P3 P2 512KB P1 P3 P2 P4 P1 128KB 256KB P4 P1 128KB P5 P4 256KB P5 P4512KB P41MB图图3.9 一个伙伴系统的内存分配与回收过程一个伙伴系统的内存分配与回收过程3.3 程序装入技术程序装入技术 可执行程序的生成步骤可执行程序的生成步骤图图3.10 高级程序处理过程高级程序处理过程源程序源程序目标模块目标模块编译编译库函数库函数装入模块装入模块链接链接编辑编辑执行执行目标模块目标模块内存内存可执行程序的装入可执行程序的装入 ？如何装入待执

5、行的程序及其所需的数据？如何装入待执行的程序及其所需的数据 ？ 何时将程序的逻辑地址转换为物理地址何时将程序的逻辑地址转换为物理地址 3种装入方式：绝对装入、重定位装入和运行种装入方式：绝对装入、重定位装入和运行时动态装入。时动态装入。 绝对装入绝对装入 程序运行之前，按照程序的逻辑地址，程序运行之前，按照程序的逻辑地址，将程序和数据装入内存指定的地方。将程序和数据装入内存指定的地方。 实现简单，无须进行逻辑地址到物理地实现简单，无须进行逻辑地址到物理地址的变换。址的变换。绝对装入绝对装入缺点：缺点： 程序每次必须装入同一内存区；程序每次必须装入同一内存区； 程序员必须事先了解内存的使用情况，

6、根据内程序员必须事先了解内存的使用情况，根据内存情况确定程序的逻辑地址；存情况确定程序的逻辑地址； 程序的修改（增加或删除指令）将引起整个程程序的修改（增加或删除指令）将引起整个程序中指令地址的变动；序中指令地址的变动； 程序中的所有存储引用，例如函数调用或过程程序中的所有存储引用，例如函数调用或过程调用等，在装入之前都必须转换为物理地址，调用等，在装入之前都必须转换为物理地址，这不利于存储共享。这不利于存储共享。重定位装入重定位装入 允许将程序装入与逻辑地址不同的物理允许将程序装入与逻辑地址不同的物理内存空间。即程序可以装入到内存的任内存空间。即程序可以装入到内存的任何位置，其逻辑地址与装入

7、内存后的物何位置，其逻辑地址与装入内存后的物理地址无直接关系。理地址无直接关系。 但是，必须进行地址映射，将逻辑地址但是，必须进行地址映射，将逻辑地址转换为物理地址。转换为物理地址。 静态重定位技术静态重定位技术：地址映射在程序装入：地址映射在程序装入时进行，以后不再更改程序地址。时进行，以后不再更改程序地址。重定位装入重定位装入 有利于程序代码和数据的共享。因为装入程序有利于程序代码和数据的共享。因为装入程序时，可以将其中的某些存储引用的逻辑地址映时，可以将其中的某些存储引用的逻辑地址映射为内存中已有的共享区的物理地址。射为内存中已有的共享区的物理地址。 但是，静态重定位不允许程序在内存中移

8、动。但是，静态重定位不允许程序在内存中移动。这不便于进程交换和紧凑拼接操作，也很难实这不便于进程交换和紧凑拼接操作，也很难实现多道程序环境下，多个程序同时装入内存的现多道程序环境下，多个程序同时装入内存的要求。要求。 故，重定位装入方式只适合于单道程序环境。故，重定位装入方式只适合于单道程序环境。运行时动态装入运行时动态装入 指，程序的地址转换不是在装入时进行，而是指，程序的地址转换不是在装入时进行，而是在程序运行时动态进行。在程序运行时动态进行。 运行时动态装入需要硬件支持，即重定位寄存运行时动态装入需要硬件支持，即重定位寄存器，用于保存程序在内存中的起始地址。器，用于保存程序在内存中的起始

9、地址。 程序被执行时，通过重定位寄存器内的起始物程序被执行时，通过重定位寄存器内的起始物理地址和指令或数据的逻辑地址计算其物理地理地址和指令或数据的逻辑地址计算其物理地址。址。 运行时动态装入有利于多道程序环境下，进程运行时动态装入有利于多道程序环境下，进程的换进的换进/换出及实现紧凑技术。换出及实现紧凑技术。 可执行程序的链接形成可执行程序的链接形成 ？ 目标模块如何链接成装入模块呢目标模块如何链接成装入模块呢 静态链接静态链接 动态链接动态链接：装入时动态链接和运行时动：装入时动态链接和运行时动态链接态链接 静态链接静态链接 指，程序被装入内存之前，必须完全链接成一指，程序被装入内存之前，

10、必须完全链接成一个装入模块，将其中的存储引用全部转换为相个装入模块，将其中的存储引用全部转换为相对地址跳转语句。并将多个目标模块链接成为对地址跳转语句。并将多个目标模块链接成为一个模块，使装入模块中的每一条指令具有相一个模块，使装入模块中的每一条指令具有相对于整个模块的第一条语句的逻辑地址。对于整个模块的第一条语句的逻辑地址。 静态链接生成的装入模块可以采用重定位装入静态链接生成的装入模块可以采用重定位装入或运行时动态装入方式。或运行时动态装入方式。 静态链接需要花费大量的处理机时间。而其中静态链接需要花费大量的处理机时间。而其中的很多模块将不会运行，浪费存储空间和处理的很多模块将不会运行，浪

11、费存储空间和处理机时间。机时间。 链接链接图图3.11 目标模块链接成装入模块目标模块链接成装入模块模块模块1if x 1 thencall mm1elsecall mm2模块模块mm1模块模块mm2(a) 目标模目标模块块模块模块1if x 1 thenelse模块模块mm1模块模块mm2(b) 装入模装入模块块？执行？执行？执行？执行动态链接动态链接 指，不用事先链接所有目标模块形成一指，不用事先链接所有目标模块形成一个完备的装入模块，而是生成一个含有个完备的装入模块，而是生成一个含有未被链接的外部模块引用的装入模块，未被链接的外部模块引用的装入模块，这些外部模块可以在装入时链接，或运这些

12、外部模块可以在装入时链接，或运行时链接。行时链接。装入时动态链接装入时动态链接 指，当系统装入含有未链接的外部模块引用的指，当系统装入含有未链接的外部模块引用的装入模块时，每当遇到一个外部模块引用，则装入模块时，每当遇到一个外部模块引用，则查找相应的目标模块。将其装入内存，并将模查找相应的目标模块。将其装入内存，并将模块内的指令地址转换为相对于整个装入模块起块内的指令地址转换为相对于整个装入模块起始地址的相对地址。始地址的相对地址。 优点：有利于目标模块的更新与升级；有利于优点：有利于目标模块的更新与升级；有利于代码共享；有利于扩充软件的功能，可以将扩代码共享；有利于扩充软件的功能，可以将扩充

13、部分作为动态链接模块。充部分作为动态链接模块。 但是，可能链接一些不会执行的模块，浪费存但是，可能链接一些不会执行的模块，浪费存储空间和处理机时间。储空间和处理机时间。运行时动态链接运行时动态链接 指，外部模块引用直至程序执行时才装入内存，指，外部模块引用直至程序执行时才装入内存，并链接到装入模块中，进行地址转换。并链接到装入模块中，进行地址转换。 可以解决静态链接和装入时动态链接都面临的可以解决静态链接和装入时动态链接都面临的存储空间和处理机时间浪费问题，不需要执行存储空间和处理机时间浪费问题，不需要执行的模块就不会装入内存。的模块就不会装入内存。 广泛用于事务处理系统，如航空售票系统、银广

14、泛用于事务处理系统，如航空售票系统、银行管理系统等。行管理系统等。 操作系统自身的一些特殊处理例程，如错误处操作系统自身的一些特殊处理例程，如错误处理例程，也无需事先全部装入内存。理例程，也无需事先全部装入内存。3.4 简单存储管理技术简单存储管理技术 简单存储简单存储 相对于虚拟存储而言，指为了实现简单，执行相对于虚拟存储而言，指为了实现简单，执行之前，操作系统必须将待执行的程序全部装入之前，操作系统必须将待执行的程序全部装入内存。内存。 然而，现代操作系统大都支持虚拟存储功能，然而，现代操作系统大都支持虚拟存储功能，允许进程装入部分程序即可开始执行，其余部允许进程装入部分程序即可开始执行，

15、其余部分保留在外存。当执行所需的部分不在内存时，分保留在外存。当执行所需的部分不在内存时，中断进程执行，使之阻塞等待，直到相应部分中断进程执行，使之阻塞等待，直到相应部分装入内存。装入内存。？ 程序在内存中如何组织程序在内存中如何组织 连续存储连续存储 : 需要内存中的一块连续的、需要内存中的一块连续的、足够大的分区。足够大的分区。 如果内存中没有足够大的连续空闲分区，如果内存中没有足够大的连续空闲分区，但存在总量足够的独立小分区，即但存在总量足够的独立小分区，即外零外零头头。系统要么拒绝分配空间，要么采用。系统要么拒绝分配空间，要么采用紧凑技术紧凑技术拼接外零头。拼接外零头。 非连续存储非连

16、续存储：允许进程的程序和数据分：允许进程的程序和数据分别装在内存的不同分区中。别装在内存的不同分区中。 必须登记一个进程分到的所有分区的位必须登记一个进程分到的所有分区的位置、大小、使用情况（如是否共享等）置、大小、使用情况（如是否共享等）等信息。等信息。 常用的非连续存储技术：分页存储技术、常用的非连续存储技术：分页存储技术、分段存储技术及其结合。分段存储技术及其结合。图图3.12 内存的连续存储与非连续存储内存的连续存储与非连续存储OS进程进程P基地址基地址(a)连续存储连续存储进程进程P（2）OS进程进程P（1）进程进程P（n）进程的组成进程的组成基地址基地址长度长度P(1)260420

17、0P(2)1240300P(n)6500300(b)非连续存储非连续存储连续存储管理连续存储管理 最简单的存储管理技术最简单的存储管理技术 要求系统配置专门的硬件实现快速地址要求系统配置专门的硬件实现快速地址转换和存储保护。转换和存储保护。 处理机硬件处理机硬件 基址寄存器基址寄存器(Base register) 界限寄存器界限寄存器(Bounds register)连续存储管理连续存储管理 基址寄存器基址寄存器：存放当前执行进程所在分区的物：存放当前执行进程所在分区的物理存储单元的起始地址。理存储单元的起始地址。 界限寄存器界限寄存器：存放当前执行进程所在分区最后：存放当前执行进程所在分区最

18、后一个物理存储单元的地址，限定进程的执行范一个物理存储单元的地址，限定进程的执行范围，保护其他进程不被非法访问。围，保护其他进程不被非法访问。 基址寄存器和界限寄存器被多个进程共享，只基址寄存器和界限寄存器被多个进程共享，只有当前执行进程才使用它们。有当前执行进程才使用它们。 装入时，进程分区的基地址值和分区的最后一装入时，进程分区的基地址值和分区的最后一个物理存储单元的地址值，分别填入该进程个物理存储单元的地址值，分别填入该进程PCB的相应字段中。的相应字段中。 当进程被调度执行时，将当进程被调度执行时，将PCB中对应的进程基中对应的进程基地址值写入基址寄存器中，并将进程获得的内地址值写入基

19、址寄存器中，并将进程获得的内存分区最大地址值，填入界限寄存器中。存分区最大地址值，填入界限寄存器中。 当进程被交换出当进程被交换出/换入内存时，上述两个地址换入内存时，上述两个地址值也会发生改变。值也会发生改变。 地址映射与存储保护地址映射与存储保护 逻辑地址转换成物理地址逻辑地址转换成物理地址 取基址寄存器中的值，加上逻辑地址值，生取基址寄存器中的值，加上逻辑地址值，生成一个物理地址成一个物理地址 地址越界检查地址越界检查 取界限寄存器中的值，与第一步计算的结果取界限寄存器中的值，与第一步计算的结果进行比较。如果生成的物理地址超出了界限范进行比较。如果生成的物理地址超出了界限范围，产生一个中

20、断，报告地址越界。否则，继围，产生一个中断，报告地址越界。否则，继续该指令的执行。续该指令的执行。程序部分程序部分数据部分数据部分内存内存基址寄存器基址寄存器加法器加法器逻辑地址逻辑地址界限寄存器界限寄存器比较器比较器越界中断越界中断物理地址物理地址图图3.13 连续存储管理的地址转换和越界检查连续存储管理的地址转换和越界检查 简单分页存储管理简单分页存储管理 连续存储：存在外零头，浪费存储空间。连续存储：存在外零头，浪费存储空间。“紧凑紧凑”需要系统额外开销。需要系统额外开销。 非连续存储：允许将一个进程的程序和非连续存储：允许将一个进程的程序和数据离散存储在多个独立的分区中，消数据离散存储

21、在多个独立的分区中，消除了外零头。除了外零头。 基本原理基本原理 分页存储管理技术是一种特殊的固定分分页存储管理技术是一种特殊的固定分区方法。区方法。 系统事先将物理内存划分成许多尺寸相系统事先将物理内存划分成许多尺寸相等的等的页框页框 (Page Frame)，并将进程分，并将进程分割成许多大小相同的割成许多大小相同的页面页面 (Page)，页面，页面与页框大小相同。与页框大小相同。 分区分区：进程的逻辑地址空间是连续的、一维的、：进程的逻辑地址空间是连续的、一维的、线性地址，进程的每一条指令和数据的地址相线性地址，进程的每一条指令和数据的地址相对于第一条语句的地址而定。对于第一条语句的地址

22、而定。 分页分页：进程被分割成许多页面。每个页面内的：进程被分割成许多页面。每个页面内的指令和数据是连续的，它们的地址相对于其所指令和数据是连续的，它们的地址相对于其所属页的第一条语句的地址，称为属页的第一条语句的地址，称为页内偏移量页内偏移量。 逻辑地址被分为两部分：逻辑地址被分为两部分：页号页号和和页内偏移量页内偏移量 页号页号页内偏移量页内偏移量15 10 9 0图图3.14 分页管理的逻辑地址表示分页管理的逻辑地址表示 当一个进程被装入物理内存时，系统将当一个进程被装入物理内存时，系统将为该进程的每个页面分配一个独立的页为该进程的每个页面分配一个独立的页框。框。 同一个进程的多个页面不

23、必存放在连续同一个进程的多个页面不必存放在连续的多个页框中。的多个页框中。例如例如 假设内存能提供假设内存能提供16个空闲页框，进程个空闲页框，进程P1被分被分割成割成4个页面，装入内存中的个页面，装入内存中的0号至号至3号页框。号页框。进程进程P2被分割成被分割成3个页面，装入个页面，装入4号至号至6号页号页框。进程框。进程P3被装入被装入7号至号至12号页框，如图号页框，如图3.15(a)所示。所示。 此时，进程此时，进程P4请求分配请求分配5个页框大小的存储空个页框大小的存储空间，但内存只有间，但内存只有3个空闲页框。于是，将暂时个空闲页框。于是，将暂时不运行的不运行的P2交换出内存，如

24、图交换出内存，如图3.15(b)所示。所示。 然后，再将然后，再将P4装入装入4、5、6、13、14号页号页框，如图框，如图3.15(c)所示。所示。 图图3.15 进程装入到离散的页框中进程装入到离散的页框中0123456789101112131415P1.2P1.1P1.0P1.3P2.0P2.1P2.2P3.0P3.1P3.2P3.3P3.4P3.5页框号页框号 内存内存(a) 依次装入依次装入P1、P2、P3P1P2P3空闲空闲0123456789101112131415P1.2P1.1P1.0P1.3P3.0P3.1P3.2P3.3P3.4P3.5页框号页框号 内存内存(b) 换出换

25、出P2P1空闲空闲P3空闲空闲0123456789101112131415P1.2P1.1P1.0P1.3P4.0P4.1P4.2P3.0P3.1P3.2P3.3P3.4P3.5P4.3P4.4页框号页框号 内存内存(c) 装入装入P4P1P4P3空闲空闲P4数据结构：页表数据结构：页表 页表：系统为每个进程建立一张页面映页表：系统为每个进程建立一张页面映射表。射表。 用于记载进程的各页面到物理内存中页用于记载进程的各页面到物理内存中页框的映射信息。框的映射信息。 进程的每个页面依次对应页表中的一个进程的每个页面依次对应页表中的一个表项，其中包含相应页在内存中对应的表项，其中包含相应页在内存中

26、对应的物理页框号和页面存取控制权限等字段。物理页框号和页面存取控制权限等字段。页号页号页框号页框号00112233进程进程P1页表页表页号页号页框号页框号0-1-2-进程进程P2页表页表页号页号页框号页框号071829310411512进程进程P3页表页表页号页号页框号页框号041526313414进程进程P4页表页表图图3.16 进程进程P1、P2、P3、P4的页表的页表数据结构：页框表数据结构：页框表 空闲页框表：登记系统中剩下的空闲页空闲页框表：登记系统中剩下的空闲页框情况框情况图图3.17 空闲页框表空闲页框表151413地址变换地址变换 硬件机制，实现逻辑地址到物理地址的转换硬件机制

27、，实现逻辑地址到物理地址的转换 分页系统中的地址变换过程如下：分页系统中的地址变换过程如下：（1） 根据逻辑地址根据逻辑地址,计算出页号和页内偏移计算出页号和页内偏移量；量；（2） 用页号检索页表，查找指定页面对应用页号检索页表，查找指定页面对应的页框号；的页框号；（3） 根据页框号和页内偏移量，计算出物根据页框号和页内偏移量，计算出物理地址。理地址。页表寄存器页表寄存器 页表寄存器：实现快速地址映射，存储执行进页表寄存器：实现快速地址映射，存储执行进程的页表起始地址。程的页表起始地址。 页表寄存器设置在处理机硬件中。页表寄存器设置在处理机硬件中。 当进程被创建时，其页表起始地址记载于进程当进

28、程被创建时，其页表起始地址记载于进程PCB中。中。 当进程被调度执行时，页表的起始地址将从该当进程被调度执行时，页表的起始地址将从该进程的进程的PCB中取出，并填入页表寄存器中。中取出，并填入页表寄存器中。 进行地址变换时，处理机从页表寄存器中查找进行地址变换时，处理机从页表寄存器中查找页表的地址。页表的地址。页号页号 偏移量偏移量逻辑地址逻辑地址物理地址物理地址页框号页框号 偏移量偏移量页表寄存器页表寄存器页表起始地址页表起始地址内存内存页框号页框号页表页表地址转换地址转换程序程序+偏偏移移量量图图3.18 分页系统的地址变换过程分页系统的地址变换过程页框页框大页表大页表 大逻辑地址空间，页

29、表非常大，需要占大逻辑地址空间，页表非常大，需要占用相当大的内存空间。用相当大的内存空间。 比如，比如，32位逻辑地址空间，假设页面大位逻辑地址空间，假设页面大小为小为4KB（212），则），则4GB（232）的）的逻辑地址空间将被划分成逻辑地址空间将被划分成220个页面。个页面。大页表大页表 若采用一级页表，则其内将包含若采用一级页表，则其内将包含1兆（兆（220）个页表项。若按字节寻址，一个页表项占个页表项。若按字节寻址，一个页表项占4B，则一级页表需要占用则一级页表需要占用4MB（222）内存空间。）内存空间。 不可能将不可能将4MB的页表保存在一个连续区中。的页表保存在一个连续区中。

30、那么，如何处理大页表的存储与检索呢？那么，如何处理大页表的存储与检索呢？ 二级页表二级页表 将一个大页表全部保存在内存中。将一个大页表全部保存在内存中。 首先，将其分割，并离散地存储在内存的多个首先，将其分割，并离散地存储在内存的多个页框中。页框中。 为之建立二级页表，记录被分割的各个页面存为之建立二级页表，记录被分割的各个页面存储在哪些页框中，也称为外层页表（储在哪些页框中，也称为外层页表（Outer Page Table）。）。 对于对于4GB的进程，若采用二级页表，则对应的的进程，若采用二级页表，则对应的二级页表结构如图：二级页表结构如图： 4GB的用户进程的用户进程4MB的一级页表的一

31、级页表4KB的二级页表的二级页表图图3.19 4GB进程的二级页表结构进程的二级页表结构多级页表多级页表 对于某些机器，二级页表也可能非常大。可以对于某些机器，二级页表也可能非常大。可以采用多级页表，对外层页表再进行分页，将各采用多级页表，对外层页表再进行分页，将各个页面离散地存储到不相邻接的物理页框中个页面离散地存储到不相邻接的物理页框中 虽然，对大页表而言，多级页表方法消除了对虽然，对大页表而言，多级页表方法消除了对较大的连续内存空间的需要，但并未解决大页较大的连续内存空间的需要，但并未解决大页表占用较大的内存空间的问题，建立多及页表表占用较大的内存空间的问题，建立多及页表反而会增加额外的

32、存储空间。反而会增加额外的存储空间。大页表大页表 最好的解决办法是采用最好的解决办法是采用虚拟存储技术虚拟存储技术，内存中，内存中仅装入页表的一部分。仅装入页表的一部分。 即只将当前需要的部分页表项装入内存，其余即只将当前需要的部分页表项装入内存，其余页表项驻留在磁盘上，需要时再将它们装入内页表项驻留在磁盘上，需要时再将它们装入内存。存。 若采用多级页表，对于正在运行的进程，必须若采用多级页表，对于正在运行的进程，必须将其外层页表调入内存，而内层页表只需调入将其外层页表调入内存，而内层页表只需调入几页就可以了。几页就可以了。反置页表反置页表(Inverted Page Table) 一般情况下

33、，系统从进程的角度为每个进程建一般情况下，系统从进程的角度为每个进程建立一张页表，页表的表项按页号排序。立一张页表，页表的表项按页号排序。 这种方法可能导致一个大进程的页表太大，占这种方法可能导致一个大进程的页表太大，占据大量的内存空间。据大量的内存空间。 反置页表反置页表：从内存的角度建立页表，整个系统：从内存的角度建立页表，整个系统只有一张页表。页表的表项基于内存中的每一只有一张页表。页表的表项基于内存中的每一个物理页框设置，页表项按页框号的顺序排序。个物理页框设置，页表项按页框号的顺序排序。其中还必须包含页框对应的页号及其隶属进程其中还必须包含页框对应的页号及其隶属进程的标识符等信息。的

34、标识符等信息。 反置页表反置页表 通常，反置页表需要包含成千上万个表项，利通常，反置页表需要包含成千上万个表项，利用进程用进程ID和页号检索其中某一个表项的速度很和页号检索其中某一个表项的速度很慢。慢。 可以根据进程可以根据进程ID和页号构建和页号构建Hash表。表。Hash表表的每一项指向反置页表中的某一项。的每一项指向反置页表中的某一项。 但是，可能会出现多个逻辑地址被映射到一个但是，可能会出现多个逻辑地址被映射到一个Hash表项的情况。需要通过链接指针将多个表项的情况。需要通过链接指针将多个冲突的映射链接起来。冲突的映射链接起来。 一般，冲突的表项一般只有一项，或两项。一般，冲突的表项一

35、般只有一项，或两项。 地址变换地址变换 首先，以进程首先，以进程ID和页号为参数，代入和页号为参数，代入Hash函函数进行计算。数进行计算。 然后，根据计算结果，检索反置页表。若检索然后，根据计算结果，检索反置页表。若检索完整个反置页表都未找到与之匹配的表项，表完整个反置页表都未找到与之匹配的表项，表明此页尚未装入内存。明此页尚未装入内存。 若系统支持虚拟存储技术，则产生请求调页中若系统支持虚拟存储技术，则产生请求调页中断。若系统不支持虚拟存储技术，则表示地址断。若系统不支持虚拟存储技术，则表示地址出错。出错。 当检索到反置页表中的对应表项时，将其中的当检索到反置页表中的对应表项时，将其中的页

36、框号与逻辑地址中的偏移量相加，构成物理页框号与逻辑地址中的偏移量相加，构成物理地址。地址。 物理地址物理地址偏移量偏移量页框号页框号逻辑地址逻辑地址偏移量偏移量页号页号HashHash表表页号页号 进程进程ID指针指针页框号页框号反置页表反置页表图图3.20 利用反置页表进行地址变换利用反置页表进行地址变换 快表快表 分页系统：处理机每次存取指令或数据至少需分页系统：处理机每次存取指令或数据至少需要访问两次物理内存要访问两次物理内存 第一次访问页表，第二次存取指令或数第一次访问页表，第二次存取指令或数据据 为了提高地址变换速度，为进程页表设置一个为了提高地址变换速度，为进程页表设置一个专用的高

37、速缓冲存储器，称为快表、专用的高速缓冲存储器，称为快表、TLB(Translation Lookaside Buffer)，或联，或联想存储器（想存储器（Associative Memory） 快表的工作原理快表的工作原理 快表的工作原理类似于系统中的数据高速缓存快表的工作原理类似于系统中的数据高速缓存(cache)，其中专门保存当前进程最近访问过，其中专门保存当前进程最近访问过的一组页表项。的一组页表项。 根据根据局部性原理局部性原理，在一个很短的时间段内，程，在一个很短的时间段内，程序的执行总是局部于某一个范围。序的执行总是局部于某一个范围。 即，进程最近访问过的页面在不久的将来还可即，进

38、程最近访问过的页面在不久的将来还可能被访问。能被访问。分页系统地址转换分页系统地址转换 通过根据逻辑地址中的页号，查找快表中是否通过根据逻辑地址中的页号，查找快表中是否存在对应的页表项。存在对应的页表项。 若快表中存在该表项，称为命中（若快表中存在该表项，称为命中（hit），取），取出其中的页框号，加上页内偏移量，计算出物出其中的页框号，加上页内偏移量，计算出物理地址。理地址。 若快表中不存在该页表项，称为命中失败，则若快表中不存在该页表项，称为命中失败，则再查找页表，找到逻辑地址中指定页号对应的再查找页表，找到逻辑地址中指定页号对应的页框号。同时，更新快表，将该表项插入快表页框号。同时，更新

39、快表，将该表项插入快表中。并计算物理地址中。并计算物理地址图图3.21 具有快表的分页系统地址变换过程具有快表的分页系统地址变换过程页号页号 偏移量偏移量逻辑地址逻辑地址物理地址物理地址页框号页框号 偏移量偏移量偏偏移移量量内存内存快表快表页框号页框号页表页表页框页框TLB命中命中命中失败命中失败页面与页框大小页面与页框大小 分页系统中，页面分页系统中，页面 = 页框。页框的大小页框。页框的大小由计算机的硬件逻辑定义。通常，页框由计算机的硬件逻辑定义。通常，页框的大小是的大小是2的幂次个字节，且常在的幂次个字节，且常在512B（29）4KB（212）之间，典型的页）之间，典型的页框大小为框大小

40、为1KB。 将页框大小设置为将页框大小设置为2的幂次，可以简化处的幂次，可以简化处理机中地址变换硬件逻辑的设计与实现。理机中地址变换硬件逻辑的设计与实现。页面与页框大小页面与页框大小 影响页面与页框大小的主要因素：页内零头、影响页面与页框大小的主要因素：页内零头、地址转换速度和页面交换效率。地址转换速度和页面交换效率。 较小的页面较小的页面有利于减少内零头，从而有利于提有利于减少内零头，从而有利于提高内存的利用率。然而，高内存的利用率。然而，较小的页面较小的页面也将导致也将导致页表过大，从而降低处理机访问页表时的命中页表过大，从而降低处理机访问页表时的命中率率(Hit Rate)。 块越大，内

41、块越大，内/外存之间的数据交换效率越高。外存之间的数据交换效率越高。因此，对于支持交换技术的系统，因此，对于支持交换技术的系统，较大的页面较大的页面有利于提高页面换进有利于提高页面换进/换出内存的效率。换出内存的效率。对分页存储管理的评价对分页存储管理的评价 彻底消除了外零头彻底消除了外零头,仅存在很少的内零头仅存在很少的内零头, 提高提高了内存利用率。了内存利用率。 分页操作由系统自动进行分页操作由系统自动进行,一个页面不能实现一个页面不能实现某种逻辑功能。用户看到的逻辑地址是一维的，某种逻辑功能。用户看到的逻辑地址是一维的，无法调试执行其中的某个子程序或子函数。无法调试执行其中的某个子程序

42、或子函数。 采用分页技术不易于实现存储共享，也不便于采用分页技术不易于实现存储共享，也不便于程序的动态链接。程序的动态链接。简单分段存储管理简单分段存储管理 基于模块化程序设计时，常常需要将一个大任基于模块化程序设计时，常常需要将一个大任务划分成若干相对独立的子任务，对应于子任务划分成若干相对独立的子任务，对应于子任务编写子程序，称为段务编写子程序，称为段(Segment)。 每个子程序可以独立地编辑、编译、链接和执每个子程序可以独立地编辑、编译、链接和执行。行。 各个子程序由实现的功能决定，长度各不相同。各个子程序由实现的功能决定，长度各不相同。执行时，根据实际需要，将若干子程序链接成执行时

43、，根据实际需要，将若干子程序链接成一个大程序。一个大程序。基本原理基本原理 程序由若干逻辑段组成，每个段有自己的名字程序由若干逻辑段组成，每个段有自己的名字和长度。程序的逻辑地址是由段名（段号）和和长度。程序的逻辑地址是由段名（段号）和段内偏移量决定。每个段的逻辑地址从段内偏移量决定。每个段的逻辑地址从0开始开始编址编址 段号段号段内偏移量段内偏移量15 10 9 0图图3.22 分段管理的逻辑地址表示分段管理的逻辑地址表示 系统采用动态划分技术，将物理内存动系统采用动态划分技术，将物理内存动态地划分成许多尺寸不相等的分区。态地划分成许多尺寸不相等的分区。 当一个进程被装入物理内存时，系统将当

44、一个进程被装入物理内存时，系统将为该进程的每一段独立地分配一个分区。为该进程的每一段独立地分配一个分区。同一进程的多个段不必存放在连续的多同一进程的多个段不必存放在连续的多个分区中。个分区中。分段系统的基本数据结构分段系统的基本数据结构 段表段表 : 每个进程建立一个，用于描述进程的分每个进程建立一个，用于描述进程的分段情况，记载进程的各个段到物理内存中分区段情况，记载进程的各个段到物理内存中分区的映射情况。其中包含段号、段长、段基址以的映射情况。其中包含段号、段长、段基址以及对本段的存取控制权限等信息。及对本段的存取控制权限等信息。 空闲分区表空闲分区表 : 用于记载物理内存中的空闲分区用于

45、记载物理内存中的空闲分区情况情况图图3.23 分段存储示例分段存储示例 P2.1P1.0P1.2P1.1P2.0(a) 分段存储分段存储0500100执行执行存取控制存取控制段基址段基址段长段长段号段号1200800只读只读2200 1000执行执行(b) 进程进程P1的段表的段表0100 1200执行执行存取控制存取控制段基址段基址段长段长段号段号1200600执行执行(c) 进程进程P2的段表的段表地址变换和存储保护地址变换和存储保护 （1） 根据逻辑地址中的段号检索进程段表，根据逻辑地址中的段号检索进程段表，获得指定段对应的段表项；获得指定段对应的段表项；（2） 判断是否地址越界。比较逻

46、辑地址中判断是否地址越界。比较逻辑地址中的段内偏移量与段表项中的段长，若超过段的的段内偏移量与段表项中的段长，若超过段的长度，则产生存储保护中断（该中断将由操作长度，则产生存储保护中断（该中断将由操作系统进行处理）；否则，转（系统进行处理）；否则，转（3）；）；（3）把逻辑地址中的段内偏移量与段表表项中）把逻辑地址中的段内偏移量与段表表项中的段基址相加，从而得到物理地址。的段基址相加，从而得到物理地址。 段表寄存器段表寄存器 段表同样被保存在物理内存中。段表同样被保存在物理内存中。 段表寄存器段表寄存器 ：实现快速地址变换，用来存放实现快速地址变换，用来存放当前执行进程的段表在物理内存中的起始

47、地址。当前执行进程的段表在物理内存中的起始地址。 当创建进程，将进程的程序和数据装入内存时，当创建进程，将进程的程序和数据装入内存时，系统为之建立段表，并将段表的起始地址填入系统为之建立段表，并将段表的起始地址填入进程的进程的PCB中。中。 当进程被调度执行时，取出其当进程被调度执行时，取出其PCB中的段表首中的段表首址，填入段表寄存器中。址，填入段表寄存器中。 图图3.24 分段系统的地址变换过程分段系统的地址变换过程内存内存物理地址物理地址段基址段基址+偏移量偏移量偏偏移移量量段号段号 偏移量偏移量逻辑地址逻辑地址段表寄存器段表寄存器段表起始地址段表起始地址+段表段表段长段长 段基址段基址

48、+越界越界判断判断中断中断越界越界正常正常段段段段分段系统的快表分段系统的快表 在分段系统中，为了访问内存中的一条指令或在分段系统中，为了访问内存中的一条指令或数据，需要两次访问内存：数据，需要两次访问内存： 第一次，访问内存中的段表，获得对应段的起始第一次，访问内存中的段表，获得对应段的起始地址。根据段的起始地址和段内偏移量，计算出物理地址。根据段的起始地址和段内偏移量，计算出物理地址。地址。 第二次，根据物理地址，访问对应存储单元的指第二次，根据物理地址，访问对应存储单元的指令或数据。令或数据。 为了提高处理机的效率，类似分页系统的快表，为了提高处理机的效率，类似分页系统的快表，可以为分段

49、系统增加一个快表，用于保存最近可以为分段系统增加一个快表，用于保存最近使用过的段表项。使用过的段表项。 对分段系统的评价对分段系统的评价 有效消除了内零头，提高了存储利用率。有效消除了内零头，提高了存储利用率。 允许子程序独立编译和修改，而不需要重新编允许子程序独立编译和修改，而不需要重新编译或链接其它相关子程序。译或链接其它相关子程序。 容易实现存储共享。容易实现存储共享。 具有较高的安全保障。具有较高的安全保障。 很容易满足程序段的动态增长需要很容易满足程序段的动态增长需要 。分页与分段技术的比较分页与分段技术的比较 都采用非连续存储，由地址映射实现地址变换。都采用非连续存储，由地址映射实

50、现地址变换。 不同主要表现在：不同主要表现在：（1） 页是信息的物理单位，大小固定。段是信息的页是信息的物理单位，大小固定。段是信息的逻辑单位，各段的长度不固定。每一段都具有一定逻逻辑单位，各段的长度不固定。每一段都具有一定逻辑含义。辑含义。（2） 分页的地址空间是一维的，逻辑地址的划分由分页的地址空间是一维的，逻辑地址的划分由机器硬件实现，对用户透明。分段的地址空间是二维机器硬件实现，对用户透明。分段的地址空间是二维或多维的，程序员知道段名和段内偏移量。或多维的，程序员知道段名和段内偏移量。（3）分页活动源于系统管理物理内存的需要，在系统内）分页活动源于系统管理物理内存的需要，在系统内部进行

51、，由系统实施，用户看不见。分段活动源于用部进行，由系统实施，用户看不见。分段活动源于用户进行模块化程序设计的需要，在系统外部进行，由户进行模块化程序设计的需要，在系统外部进行，由用户实施，用户是知道的。用户实施，用户是知道的。 简单段页式存储管理简单段页式存储管理 基本思想：采用分段方法组织用户程序，采用基本思想：采用分段方法组织用户程序，采用分页方法分配和管理内存。分页方法分配和管理内存。 即，用户程序可以用模块化思想进行设计，一即，用户程序可以用模块化思想进行设计，一个用户序由若干段构成。系统将内存划分成固个用户序由若干段构成。系统将内存划分成固定大小的页框，并将程序的每一段分割成若干定大小的页框，并将程序的每一段分割