1、第四章第四章 存储器管理存储器管理 4.1 存储器的层次结构存储器的层次结构 4.2程序的装入和链接程序的装入和链接 4.3连续分配方式连续分配方式4.4基本分页存储管理方式基本分页存储管理方式4.5基本分段存储管理方式基本分段存储管理方式4.6虚拟存储器的基本概念虚拟存储器的基本概念4.7请求分页存储管理方式请求分页存储管理方式4.8页面置换算法页面置换算法4.9请求分段存储管理方式请求分段存储管理方式 4.1 存储器的层次结构存储器的层次结构寄存器高速缓存主存磁盘缓存磁盘可移动存储介质CPU寄存器主存辅存寄存器、高速缓存、主存储器和磁盘缓存均属于操作系统寄存器、高速缓存、主存储器和磁盘缓存
2、均属于操作系统存储管理存储管理的管辖范的管辖范畴，掉电后它们存储的信息不再存在。畴，掉电后它们存储的信息不再存在。而辅存的使用与管理放在而辅存的使用与管理放在设备和文件管理设备和文件管理中介绍！中介绍！在主存中KBMBGBTB存储器管理：存储器管理：指内存的管理，外存管理在文件部分讲述；指内存的管理，外存管理在文件部分讲述； 单道程序系统：单道程序系统：内存被划分成两部分：一部分供内存被划分成两部分：一部分供OSOS使用，使用，一部分供当前正在执行的程序使用。一部分供当前正在执行的程序使用。多道程序系统：多道程序系统：存储器的存储器的用户部分用户部分必须进一步地细分，以必须进一步地细分，以适应
3、多个进程的要求。细分的任务由操作系统动态实适应多个进程的要求。细分的任务由操作系统动态实现，这就是存储器管理。现，这就是存储器管理。存储器管理的目的：存储器管理的目的：一是方便用户使用，二是提高存储器一是方便用户使用，二是提高存储器的利用率的利用率。 基本概念补充1、存储器管理功能主存的分配和回收：主存的分配和回收：系统应能记住每个存储区的状态；实施存储器的分配；系统应能记住每个存储区的状态；实施存储器的分配；回收系统或用户释放的存储区。回收系统或用户释放的存储区。地址转换或重定位：地址转换或重定位：实现逻辑地址到物理地址的变换，分为静态重定位和动实现逻辑地址到物理地址的变换，分为静态重定位和
4、动态重定位态重定位主存共享与保护：主存共享与保护：使多道程序能使多道程序能动态动态地地共享主存共享主存，最好能共享主存中的信息；，最好能共享主存中的信息；保证进入主存的各道作业都在自己的存储空间内运行，互不干扰。由硬件和保证进入主存的各道作业都在自己的存储空间内运行，互不干扰。由硬件和软件配合完成。软件配合完成。主存扩充：主存扩充：借助于借助于虚拟存储技术虚拟存储技术，为用户提供比主存空间大的地址空间。，为用户提供比主存空间大的地址空间。内存的每个存储单元都有一个编号，这种编号称为内存的每个存储单元都有一个编号，这种编号称为内存地址内存地址（或称为（或称为物理物理地址，绝对地址地址，绝对地址）
5、。）。内存地址的集合称为内存地址的集合称为内存空间（或物理地址空间）。内存空间（或物理地址空间）。例如，我们常说内存例如，我们常说内存为：为：512MB要求用户用内存地址编程是非常困难的，尤其是在多道程序设计的环境中要求用户用内存地址编程是非常困难的，尤其是在多道程序设计的环境中（不知道）。（不知道）。2 2、地址映射、地址映射( (地址重定位地址重定位) ) 用户编程所用的地址称为用户编程所用的地址称为逻辑地址（或程序地址，或虚地址）逻辑地址（或程序地址，或虚地址），由逻由逻辑地址组成的空间称为辑地址组成的空间称为逻辑地址空间（或程序地址空间）逻辑地址空间（或程序地址空间）。我们把用户程序装
6、入内存时，或在程序执行时，对有关指令或数据地我们把用户程序装入内存时，或在程序执行时，对有关指令或数据地址的修改称为址的修改称为从程序地址到内存地址的地址映射，或称为地址重定位。从程序地址到内存地址的地址映射，或称为地址重定位。地址映射地址映射Load A 1200 3456 。 。1200物理地址空间物理地址空间Load A data1data1 3456源程序（名空间）源程序（名空间）Load A 200 34560100200编译编译连接连接逻辑地址空间逻辑地址空间BR=10001100地址映射的方式静态地址映射：静态地址映射：1 1）程序被装入内存时由操作系统的连接装入程序完成）程序被
7、装入内存时由操作系统的连接装入程序完成程序的逻辑地址到内存地址的转换；程序的逻辑地址到内存地址的转换；2 2）地址转换工作是在程序执行）地址转换工作是在程序执行由装入程序集中一次由装入程序集中一次完成。完成。n假定程序装入内存的首地址为假定程序装入内存的首地址为BRBR，程序地址为，程序地址为VRVR，内存，内存地址为地址为MRMR，则地址映射按下式进行：，则地址映射按下式进行：MR=BR+VRMR=BR+VR把程序装入起始地址为把程序装入起始地址为10001000的内存区的内存区Mov r1,500Mov r1,500123412340 0100100500500600600Mov r1,1
8、500Mov r1,15000 01000100011001100150015001600160012341234作业的地址空间作业的地址空间存储空间存储空间装入程序装入程序静态映射优缺点静态映射优缺点优点：不需要硬件的支持，简单易实现，成本低；优点：不需要硬件的支持，简单易实现，成本低；缺点：程序必须占用连续的内存空间；一旦程序装入缺点：程序必须占用连续的内存空间；一旦程序装入后不能移动；后不能移动；主存利用率低；难以做到程序和数据的主存利用率低；难以做到程序和数据的共享。共享。动态地址映射（重定位）动态地址映射（重定位）动态地址重定位：动态地址重定位：在程序执行的过程中，每次将要访问的指令
9、或数在程序执行的过程中，每次将要访问的指令或数据逻辑地址转换为内存地址。据逻辑地址转换为内存地址。动态映射方法：动态映射方法：装入程序把程序和数据装入程序把程序和数据原样装入原样装入到已分配的存储区到已分配的存储区中，然后把这个存储区的起始地址送入中，然后把这个存储区的起始地址送入重定位寄存器重定位寄存器中。在程序执中。在程序执行时，再将相对地址转换成绝对地址。行时，再将相对地址转换成绝对地址。硬件支持：硬件支持：在动态地址重定位机构中，有一个在动态地址重定位机构中，有一个基地址寄存器基地址寄存器BRBR和一和一个个程序地址寄存器程序地址寄存器VRVR，一个，一个内存地址寄存器内存地址寄存器M
10、RMR。转换过程：转换过程：MR=BR+VRMR=BR+VR把程序装入起始地址为把程序装入起始地址为10001000的内存区的内存区123412340 0100100500500599599作业的地址空间作业的地址空间0 01000100011001100150015001599159912341234存储空间存储空间10001000+ +重定位寄存器重定位寄存器逻辑地址逻辑地址VRVR物理地址物理地址MRMRMOV r1MOV r1， 500500 MOV r1MOV r1， 500500 动态地址映射的过程动态地址映射的过程程序装入内存后，它所占用的内存区的程序装入内存后，它所占用的内存区
11、的首地址首地址由系统送入由系统送入基地址寄存器基地址寄存器BRBR中。中。在程序执行的过程中，若要访问内存，将访问的逻辑地址在程序执行的过程中，若要访问内存，将访问的逻辑地址送入送入VRVR中。中。 地址转换机构把地址转换机构把VRVR和和BRBR中的内容相加，并将结果送入中的内容相加，并将结果送入MRMR中，中，作为实际访问的地址。作为实际访问的地址。动态重定位优缺点动态重定位优缺点优点：优点：1 1）程序占用的内存空间是动态可变的，当程序从）程序占用的内存空间是动态可变的，当程序从某个存储区移到另一个区域时，只需要修改相应的寄存器某个存储区移到另一个区域时，只需要修改相应的寄存器BRBR的
12、内容即可；的内容即可；2 2）一个程序不一定要求占用一个连续的）一个程序不一定要求占用一个连续的内存空间，可以部分地装入程序运行；内存空间，可以部分地装入程序运行；4 4）便于多个进程）便于多个进程共享同一个程序的代码。共享同一个程序的代码。动态地址重定位的代价：动态地址重定位的代价：1 1）需要硬件的支持；）需要硬件的支持；2 2）实现存）实现存储管理的软件算法较为复杂。储管理的软件算法较为复杂。4.2 程序的装入和链接程序的装入和链接 （可能产生）可执行程序文件编译链接装入二进制内存映像程序处理步骤：编译-编译程序，负责检查语法错，涉及名空间。输入：源程序； 输出：多个目标模块；链接-链接
13、程序，负责将多个模块相关联，涉及逻辑地址空间。输入：多个目标模块、库函数；输出：装入模块；装入：装入程序，负责内存分配和地址映射，涉及内存空间。输入：装入模块；输出：可执行的二进制内存映像。过程或函数可能分别对应一个模块！库链接程序装入模块装入程序编译程序产生的目标模块第一步第二步第三步内存4.1.2 4.1.2 程序的链接程序的链接 1. 1. 静态链接方式静态链接方式(Static Linking) (Static Linking) 图 4-3 程序链接示意图 模块 ACALL B；Return；0L1模块 BCALL C；Return；0M1模块 CReturn；0N10模块 AJSR“
14、L”Return；L1模块 BJSR“LM”Return；LLM1LMLMN1模块 CReturn；(a) 目标模块(b) 装入模块链接前，链接前，每个模每个模块都有块都有各自的各自的相对起相对起始地址始地址0 0链接后，链接后，每个模每个模块使用块使用同一个同一个相对起相对起始地址始地址0 0名空间名空间逻辑地址空间逻辑地址空间在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装入模块，又称为链接成一个完整的装入模块，又称为可执行文件可执行文件，以后不再拆开。解决：对相对地解决：对相对地址进行修改；变换外部调用符号址进行修改；变换外部调用符号不要求！不要求！2. 2. 装入时
15、动态链接装入时动态链接(Load(Loadtime Dynamic Linking) time Dynamic Linking) 基本思想：基本思想：源程序被编译生成的目标模块，是在装入内存时，边装入边连接。源程序被编译生成的目标模块，是在装入内存时，边装入边连接。装入程序根据外部模块调用而逐个装入和连接。装入时动态链接方式有装入程序根据外部模块调用而逐个装入和连接。装入时动态链接方式有以下优点以下优点便于修改和更新：便于修改和更新：各个模块的修改极易编译和连接；各个模块的修改极易编译和连接；便于实现对目标模块的共享：便于实现对目标模块的共享：将内存中的一个模块可以连接到多个程序将内存中的一个
16、模块可以连接到多个程序中。（中。（已在内存的就不必重复装入已在内存的就不必重复装入）要运行的程序都必须在装入时，全部连接调入内存。要运行的程序都必须在装入时，全部连接调入内存。 3. 3. 运行时动态链接运行时动态链接(Run-time Dynamic Linking) (Run-time Dynamic Linking) 动态链接方式：动态链接方式：将对某些模块的链接推迟到执行时才实施，将对某些模块的链接推迟到执行时才实施，亦即，在执行过程亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由中，当发现一个被调用模块尚未装入内存时，立即由OSOS去找到该模块并去找到该模块并将之装入内
17、存，把它链接到调用者模块上。特点如下：将之装入内存，把它链接到调用者模块上。特点如下：特点：特点：凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。间。 三种链接方式的差别相当于：三种链接方式的差别相当于：静态链接：上车（相当于进入内存）前集合起来静态链接：上车（相当于进入内存）前集合起来装入时链接：上车后集合起来（装入时链接：上车后集合起来（有利于共享已在内存中的部分有利于共享已在内存中的部分
18、）运行时链接：开车后需要时集合起来（运行时链接：开车后需要时集合起来（按需调入按需调入）4.2.1 4.2.1 程序的装入程序的装入1. 1. 绝对装入方式绝对装入方式(Absolute Loading Mode) (Absolute Loading Mode) 程序中所使用的绝对地址，既可在编译或汇编时给出，程序中所使用的绝对地址，既可在编译或汇编时给出， 也可也可由程序员直接赋予；由程序员直接赋予；编译程序生成的目标模块其逻辑地址与要装入内存的物理地编译程序生成的目标模块其逻辑地址与要装入内存的物理地址相同；址相同；缺点：单道程序可用，多道程序环境不能用。缺点：单道程序可用，多道程序环境不
19、能用。 采用绝对地址装入，目前很少使用采用绝对地址装入，目前很少使用2. 2. 可重定位装入方式可重定位装入方式(Relocation Loading Mode) (Relocation Loading Mode) 图 4-2 作业装入内存时的情况 LOAD 1,2500365LOAD 1,2500365100001100012500150005000250010000作业地址空间内存空间又称静态重定位：地址变换在装入时又称静态重定位：地址变换在装入时一次完成，其后不能移动。一次完成，其后不能移动。逻辑地址（相对地址）逻辑地址（相对地址）物理地址物理地址（绝对地（绝对地址）址）LOAD 1,L
20、OAD 1,12500125003. 3. 动态运行时装入方式动态运行时装入方式(Denamle Run-time Loading) (Denamle Run-time Loading) 动态运行时装方式：动态运行时装方式：装入内存后的所有地址都仍是相对地址；装入内存后的所有地址都仍是相对地址；逻辑地址到物理地址的变换要逻辑地址到物理地址的变换要推迟到程序真正执行时才进行；推迟到程序真正执行时才进行；地址变换发生在程序执行过程中（即动态重定位）地址变换发生在程序执行过程中（即动态重定位）。为使地址转换不影为使地址转换不影响程序执行速度，必须使用硬件支持。响程序执行速度，必须使用硬件支持。链接和
21、装入的关系（一）v静态链接会形成磁盘上的可执行文件，而装入时动态链接和运行时动态链接不会产生磁盘上的可执行文件。v静态链接产生的可执行文件装入时内存是连续分配的，而地址映射既可采用可重定位装入方式（静态重定位）也可以采用动态运行时装入方式（动态重定位）链接和装入间的关系（二）v装入时动态链接方式可以分别给每个装入模块分配一块内存区域，因而装入时各模块不一定连续存放。v装入时的地址映射既可采用可重定位装入方式（静态重定位-链接后运行前一次性修改逻辑地址为物理地址）也可以采用动态运行时装入方式（动态重定位-运行时动态计算出逻辑地址到物理地址的映射）链接和装入间的关系（三）v运行时动态链接方式一般情
22、况下后装入的模块和原先已装入的模块是不连续存放的。v运行时动态链接方式的地址变换不可能运行前一次性映射地址，即不可能采用静态重定位方法，而只能使用动态重定位的方法。链接和装入间的关系（四） 链接链接装入装入静态链接静态链接装入时动态链接装入时动态链接运行时动态链接运行时动态链接连续或不连续分配连续均可一般不连续静态重定位或动态重定位均可均可动态重定位链接：考虑格模块如何关联起来装入：考虑装在内存何处，以及如何进行地址变换4.2 4.2 连续分配方式连续分配方式4.2.1 4.2.1 单一连续分配单一连续分配 特征：特征：最简单的一种存储管理方最简单的一种存储管理方式，但只能用于单用户、单任务式
23、，但只能用于单用户、单任务的操作系统中；常把内存分为系的操作系统中；常把内存分为系统区和用户区两部分，系统区仅统区和用户区两部分，系统区仅提供给提供给OSOS使用，通常是放在内使用，通常是放在内存的低址部分；用户区是指除系存的低址部分；用户区是指除系统区以外的全部内存空间，统区以外的全部内存空间， 提供提供给用户使用。给用户使用。 OS用户区用户区4.2.2 4.2.2 固定分区分配固定分区分配 1. 1. 划分分区的方法划分分区的方法 分区大小相等，分区大小相等， 即使所有的内存分区大小相等。即使所有的内存分区大小相等。缺点：缺缺点：缺乏灵活性，大作业无法运行，小作业浪费空间。乏灵活性，大作
24、业无法运行，小作业浪费空间。 分区大小不等，即划分为小、中、大不等的固定分区。分区大小不等，即划分为小、中、大不等的固定分区。优优点：灵活性好。点：灵活性好。 分配方法：分配方法：将用户空间划分为若干个固定大小的区域，在每个分将用户空间划分为若干个固定大小的区域，在每个分区中装入一道作业；有几个分区，就有几道并发的作业；有区中装入一道作业；有几个分区，就有几道并发的作业；有空闲分区时，可调入一适当大小的作业；最简单的一种多道空闲分区时，可调入一适当大小的作业；最简单的一种多道程序存储管理方法。程序存储管理方法。2. 2. 内存分配内存分配 ：为了便于内存分配，将分区按照大小排队，并建立一为了便
25、于内存分配，将分区按照大小排队，并建立一个分区表。如图所示。当为作业分配空间时，分配程序按照此表检个分区表。如图所示。当为作业分配空间时，分配程序按照此表检索以合适分区分配；否则，拒绝分配。索以合适分区分配；否则，拒绝分配。缺点：缺点：空间浪费。空间浪费。图 4-4 固定分区使用表 4.2.3 4.2.3 动态分区分配动态分区分配 1. 1. 分区分配中的数据结构分区分配中的数据结构 (1) 空闲分区表。 (2) 空闲分区链。 图 4-5 空闲链结构 前向指针N20N个字节可用后向指针N20分配思想：分配思想：根据进程的实际需要，动态的为进程分配（切分）内根据进程的实际需要，动态的为进程分配（
26、切分）内存空间，及需要多大，分配多大。提高内存的利用率。存空间，及需要多大，分配多大。提高内存的利用率。未分配区表用空闲区链表表示：未分配区表用空闲区链表表示：0010k10k270k00730k730k100k100k100k270k 空闲区链空闲区链head空闲区大小2. 2. 分区分配算法分区分配算法 首次适应算法首次适应算法FFFF：空闲分区按地址递增成链表空闲分区按地址递增成链表；每次分配从链首；每次分配从链首依次查找一空间首次满足作业的空闲分区；再从该分区中切出与依次查找一空间首次满足作业的空闲分区；再从该分区中切出与作业等量的空间分之，余者挂到链表中；若找不到满足作业空间作业等量
27、的空间分之，余者挂到链表中；若找不到满足作业空间要求的空闲分区，分配失败。要求的空闲分区，分配失败。优缺点：优缺点：低地址部分将产生多个较小的空闲分区（碎片），增加低地址部分将产生多个较小的空闲分区（碎片），增加分配开销。分配开销。问题：问题：如何从空闲分区表或链表中，选择一分区分配个作业，常用的算法如下：如何从空闲分区表或链表中，选择一分区分配个作业，常用的算法如下：循环首次适应算法：循环首次适应算法：该算法是由首次适应算法演变而成的，区别仅是从上次该算法是由首次适应算法演变而成的，区别仅是从上次已分配分区的下一个分区依次查找首次满足作业的空闲分区，并从中划分出作已分配分区的下一个分区依次查
28、找首次满足作业的空闲分区，并从中划分出作业需要的分区。业需要的分区。实现方法：实现方法：起始循环指针起始循环指针+ +循环空闲分区（链）表循环空闲分区（链）表2. 2. 分区分配算法分区分配算法 最佳适应算法：最佳适应算法：空闲链表依照空间大小排列空闲链表依照空间大小排列，每次从链首，每次从链首( (小的在前小的在前) )为作为作业找一个大小最合适的分区分配。业找一个大小最合适的分区分配。缺点：缺点：最佳适应必将产生最小的空闲碎片。最佳适应必将产生最小的空闲碎片。 最坏适应算法最坏适应算法(worst fit)(worst fit)：总是挑选一个最大的空闲区分割给作业使用，其总是挑选一个最大的
29、空闲区分割给作业使用，其优点是可使剩下的空闲区不至于太小，产生碎片的几率最小，优点是可使剩下的空闲区不至于太小，产生碎片的几率最小，对中、小作业有利，同时最坏适应分配算法查找效率很高。对中、小作业有利，同时最坏适应分配算法查找效率很高。3. 3. 分区分配操作分区分配操作 1)1)分配内存操作分配内存操作 分配操作如左分配操作如左图所示图所示从头开始查表检索完否？m.sizeu.size?m.sizeu.sizesize?从该分区中划出u.size大小的分区将该分区分配给请求者修改有关数据结构返回返回继续检索下一个表项将该分区从链中移出YNNYYN2)2)回收内存操作回收内存操作 回收的分区有
30、回收的分区有4 4种情况：与前、后、前后空分区相邻，如下图所示。种情况：与前、后、前后空分区相邻，如下图所示。图 4-7 内存回收时的情况 当回收分区与前后空闲分区均不相邻时，为回收分区建立一个空闲分区结当回收分区与前后空闲分区均不相邻时，为回收分区建立一个空闲分区结点，并插入链表适当位置。点，并插入链表适当位置。回收分区回收分区4.2.4 4.2.4 可重定位分区分配可重定位分区分配 1. 1. 动态重定位的引入：动态重定位的引入：动态回收碎片，将小而不可用的空闲分区拼接动态回收碎片，将小而不可用的空闲分区拼接成较大的一个空闲分区。移动作业分区，必然要重定位。成较大的一个空闲分区。移动作业分
31、区，必然要重定位。 图 4-8 紧凑的示意 操作系统用户程序1用户程序310 KB30 KB用户程序614 KB用户程序926 KB操作系统用户程序1用户程序3用户程序6用户程序980 KB(a) 紧凑前(b) 紧凑后2.2.动态重定位的实现：动态重定位的实现：作业在内存中仍保持逻辑地址，在执行时再实施重定位。作业在内存中仍保持逻辑地址，在执行时再实施重定位。具体过程如下图。具体过程如下图。 图 4-9 动态重定位示意图 LOAD1,25003650100250050002500相对地址10000重定位寄存器LOAD1,250036510000101001250015000作业J处理机一侧 存
32、储器一侧主存3. 3. 动态重定位分区分配算法：在动态分区算法增加了回收碎片的功能。动态重定位分区分配算法：在动态分区算法增加了回收碎片的功能。图 4-10 动态分区分配算法流程图 请求分配u.size分区检索空闲分区链(表)找到大于u.size的可用区否?按动态分区方式进行分配修改有关的数据结构返回分区号及首批空闲分区总和u.size?进行紧凑形成连续空闲区修改有关的数据结构否是无法分配返回否作业4-1v1、在系统中采用可变分区存储管理，操作系统占用低地址部分的126KB，用户区的大小是386KB，若采用空闲分区表管理空闲分区。若分配时从高地址开始，对于下述的作业申请序列：作业1申请80KB
33、；作业2申请56KB；作业3申请120KB；作业1完成；作业3完成；作业4申请156KB；作业5申请80KB。试用首次适应法处理上述作业，并回答下面问题。（1）画出作业1、2、3进入内存后。内存分布情况。（2）画出作业1、3完成后。内存的分布情况。（3）画出作业4、5进入内存后。内存分布的情况。4.5 4.5 基本分页存储管理方式基本分页存储管理方式 问题：问题：由于为进程连续分配内存空间，将产生大量碎片；为了利用碎片必由于为进程连续分配内存空间，将产生大量碎片；为了利用碎片必须将其合并，又需要系统开销。须将其合并，又需要系统开销。能否给进程离散（不连续）地分配内能否给进程离散（不连续）地分配
34、内存空间，解决这些问题存空间，解决这些问题？离散分配：离散分配：当前使用最多的内存分配方式是分页管理方式和分段管理方式；当前使用最多的内存分配方式是分页管理方式和分段管理方式；分页是页面为单位进行内存分配，分段方式是以段为单位进行内存分分页是页面为单位进行内存分配，分段方式是以段为单位进行内存分配。配。基本分页（段）存储管理方式：基本分页（段）存储管理方式：如果分页或分段存储管理方式中不具备页如果分页或分段存储管理方式中不具备页面或分段对换功能，将其称之为基本分页或基本分段存储管理方式。面或分段对换功能，将其称之为基本分页或基本分段存储管理方式。4.3.1 4.3.1 页面与页表页面与页表 1
35、. 1. 页面与物理块页面与物理块 页面：页面：将一个进程的逻辑地址空间分成若干个大小相等的片，称为页将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页顺序编号为面或页，并为各页顺序编号为0 0、1 1、2 2、n n。 物理块：物理块：把内存空间分成与页面相同大小的若干个存储块，称为把内存空间分成与页面相同大小的若干个存储块，称为( (物理物理) )块或页框块或页框(frame)(frame)， 也同样为它们加以编号，如也同样为它们加以编号，如0 0块、块、1 1块等等。块等等。 内存分配原理：内存分配原理：在为进程分配内存时，以页面为单位给进程离散分配在为进程分配内存时
36、，以页面为单位给进程离散分配与页面数等量的物理块，并分别装入到相应的物理块中与页面数等量的物理块，并分别装入到相应的物理块中（全部（全部装装入）入） 页内碎片：页内碎片：由于进程的最后一页经常装不满一块而形成了不可利用的由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为碎片，称之为“页内碎片页内碎片”。举例：举例：如左图所示，如左图所示，按照基本分页存按照基本分页存储管理方式为进储管理方式为进程分配内存空间。程分配内存空间。设页面大小为设页面大小为1KB1KB 页面大小设定：页面大小设定：在分页系统中的页面其大小应适中，且页面大小应在分页系统中的页面其大小应适中，且页面大小应是是2
37、 2的幂，通常为的幂，通常为512 B8 KB512 B8 KB。 页面大小利弊：页面大小利弊：若页面太小，若页面太小，内存碎片减小，从而减少了内存碎片内存碎片减小，从而减少了内存碎片的总空间，提高内存利用率；但另一方面也会使每个进程占用较多的总空间，提高内存利用率；但另一方面也会使每个进程占用较多的页面，从而导致进程的页表过长，占用大量内存等；的页面，从而导致进程的页表过长，占用大量内存等；若页面较大，若页面较大，可以减少页表的长度，节省内存，但却又会使页内碎片增大。可以减少页表的长度，节省内存，但却又会使页内碎片增大。逻辑地址空间中的地址为逻辑地址空间中的地址为A A，页面大小为，页面大小
38、为L L，则有：，则有： P=INTA/L d=A MOD L例：A=2170B，L=1KB时，则有P=2，d=1222、逻辑地址结构页号页号 页内地址页内地址0111231页号页号P页内位移量页内位移量W编号编号01048575相对地址相对地址04095最大页面数： 220=1M个页面大小： 212=4KB逻辑空间： 0232-1一维的，并针对程序员3 3、页表、页表分页存储管理方式按照进程页面的多少，为进程离散分分页存储管理方式按照进程页面的多少，为进程离散分配相同数量的物理块，为了记录每一页所分配的物理块，配相同数量的物理块，为了记录每一页所分配的物理块，必须为每个进程建立一个页表必须为
39、每个进程建立一个页表每个进程一个页表，每个页面一个表项；每个进程一个页表，每个页面一个表项；表项：表项：页号页号：0 0、1 1、2 2、n n；块号块号：离散分配形成；：离散分配形成；存取控制存取控制：读写控制：读写控制 页表示意图页表示意图 图 4-11 页表的作用 用户程序0 页1 页2 页3 页4 页5 页n 页页表页号块号02132638495内存012345678910基本分页系统多进程内存分配示意图基本分页系统多进程内存分配示意图4.3.2 4.3.2 地址变换机构地址变换机构 1.1.基本的地址变换机构基本的地址变换机构 ：实现逻辑地址向物理地址的转换。由于页实现逻辑地址向物理
40、地址的转换。由于页内地址与块内地址一一对应，所以地址转换关键是将逻辑地址中内地址与块内地址一一对应，所以地址转换关键是将逻辑地址中的页号转换为内存中的物理块号。的页号转换为内存中的物理块号。2.2.转换机构设施：转换机构设施：页表寄存器：页表寄存器：存放进程页表在内存中的起地址和存放进程页表在内存中的起地址和页表长度（进程不执行时放在页表长度（进程不执行时放在PCBPCB中，执行时调入寄存器中）；中，执行时调入寄存器中）；物理地址寄存器：物理地址寄存器：存放转换后的物理地址（内存地址）；存放转换后的物理地址（内存地址）；3.3.查找表项：查找表项：表项地址表项地址= =页表起始地址页表起始地址
41、+ +页号页号* *表项长度；表项长度；4.4.地址转换过程如下图。地址转换过程如下图。 图 4-12 分页系统的地址变换机构 例例 说明运行进程的地址变换过程。说明运行进程的地址变换过程。 如下图所示，进程程序地址空间共有如下图所示，进程程序地址空间共有7 7个页，每页的大小为个页，每页的大小为10241024。其对应的。其对应的主存块在页表中已列出。假定页表在主存始址为主存块在页表中已列出。假定页表在主存始址为500500。若该程序从第。若该程序从第0 0页开始页开始运行，且现程序计数器内容为：运行，且现程序计数器内容为：0100程序计数器：程序计数器：逻辑地址逻辑地址页表寄存器页表寄存器
42、程序计数器程序计数器500 7500 70 (0 (页号）页号） 100100（页内地址）（页内地址） + +页表页表5 5（内存块号）（内存块号） 100100（页内地址）（页内地址）1 12 23 34 45 50 01 12 23 34 45 56 65 57 79 91515131310101616500500每页的大小每页的大小为为10241024内存地址：内存地址：5 51024+100=52201024+100=5220500+0=500500+0=500例：例：有一系统采用页式存储管理，有一作业大小是有一系统采用页式存储管理，有一作业大小是8KB8KB，页，页大小为大小为2KB
43、2KB，依次装入内存的第，依次装入内存的第7 7、9 9、1010、5 5块，试将逻块，试将逻辑地址辑地址71457145，34123412转换成内存地址。转换成内存地址。逻辑地址逻辑地址 71457145P P7145 7145 2048 2048 3 3W W7145 mod 20487145 mod 2048 10011001MR=5MR=5* *2048+1001=112412048+1001=11241逻辑逻辑地址地址71457145的内存地址是：的内存地址是：1124111241逻辑地址逻辑地址 34123412P P3412 3412 2048 2048 1 1W W3412 m
44、od 20483412 mod 2048 13641364MR=9MR=9* *2048+1364=197962048+1364=19796逻辑逻辑地址地址34123412的内存地址是：的内存地址是：19796197962 2、具有快表的地址变换机构、具有快表的地址变换机构问题：问题：两次访问内存两次访问内存( (页表，数据页表，数据) )，运行速度下降一半；，运行速度下降一半；解决方法：解决方法：联想存储器，快表，存放当前访问的页表项；联想存储器，快表，存放当前访问的页表项；思路：思路：将已访问的页号的页表项放入快表，方便下次访问，将已访问的页号的页表项放入快表，方便下次访问，提高访问速度，
45、争取一次访问内存；提高访问速度，争取一次访问内存；联想存储器：联想存储器：通常只要设定通常只要设定8 81616个寄存器作为联想存储器，个寄存器作为联想存储器，即可使程序执行速度大大提高。即可使程序执行速度大大提高。 具有快表的地址变换过程示意图具有快表的地址变换过程示意图 图 4-13 具有快表的地址变换机构 页表寄存器页表始址页表长度页号页内地址逻辑地址L越界中断块号b页表页号页号输入寄存器块号bb快表d物理地址4.3.3 4.3.3 两级和多级页表两级和多级页表 问题：问题：现代的大多数计算机系统，都支持非常大的逻辑地址空间现代的大多数计算机系统，都支持非常大的逻辑地址空间(2(2323
46、2226464) )。在这。在这样的环境下，页表就变得非常大，要占用相当大的内存空间。例如，对于一个具样的环境下，页表就变得非常大，要占用相当大的内存空间。例如，对于一个具有有3232位逻辑地址空间的分页系统，规定页面大小为位逻辑地址空间的分页系统，规定页面大小为4 KB4 KB即即2 212 12 B B，则在每个进程页，则在每个进程页表中的页表项可达表中的页表项可达1 1兆个之多，而且还要求是连续的。兆个之多，而且还要求是连续的。解决办法：解决办法： 采用离散分配方式存放页表；采用离散分配方式存放页表； 使用对换方式调入、调出页表。使用对换方式调入、调出页表。 1. 1. 两级页表两级页表
47、(Two-Level Page Table) (Two-Level Page Table) 逻辑地址结构可描述如下：页面大小为逻辑地址结构可描述如下：页面大小为4K4K（1212位），每页包含位），每页包含10241024个页表项（个页表项（P2P2，占，占1010位）；总共有位）；总共有10241024个分页（个分页（P1P1，占，占1010位）位）图 4-14 两级页表结构 101110780121742n第0页页表1460121023第1页页表114115011023外部页表012345671141151468第n页页表14680121023内存空间图 4-15 具有两级页表的地址变换机
48、构 外部页号P1P2外部页内地址页内地址d逻辑地址外部页表寄存器外部页表db页表页表物理地址二级页表地址转换过程示意图二级页表地址转换过程示意图 2. 2. 多级页表多级页表 对于对于3232位的机器，采用两级页表结构是合适的；但对于位的机器，采用两级页表结构是合适的；但对于6464位的机器，位的机器，如果页面大小仍采用如果页面大小仍采用4 KB4 KB即即2 21212 B B，那么还剩下，那么还剩下5252位，位， 假定仍按物理块假定仍按物理块的大小的大小(2(21212位位) )来划分页表，则将余下的来划分页表，则将余下的4242位用于外层页号。此时在外位用于外层页号。此时在外层页表中可
49、能有层页表中可能有4096 G4096 G个页表项，个页表项， 要占用要占用16384 GB16384 GB的连续内存空间。的连续内存空间。 必须采用多级页表，将外层页表再进行分页，也是将各分页离散地装入必须采用多级页表，将外层页表再进行分页，也是将各分页离散地装入到不相邻接的物理块中，再利用第到不相邻接的物理块中，再利用第2 2级的外层页表来映射它们之间的关级的外层页表来映射它们之间的关系。系。 对于对于6464位的计算机，如果要求它能支持位的计算机，如果要求它能支持2 2(=1844744 TB)(=1844744 TB)规模的规模的物理存储空间，则即使是采用三级页表结构也是难以办到的；而
50、在当前物理存储空间，则即使是采用三级页表结构也是难以办到的；而在当前的实际应用中也无此必要。的实际应用中也无此必要。例题一一个由8个页面，每页有1024个字节组成的逻辑空间，把它装入有32个物理块的存储器中，问：(1)逻辑地址需要多少位二进制来表示？(2)绝对地址需要多少位二进制来表示？解：页面数：解：页面数：8=28=23 3 块数：块数：32= 232= 25 5 页面长度：页面长度：1024=21024=21010页号页号 页内地址页内地址页面长度决定了页内地址的长度09，10位；页面数决定了页号的地址长度02，3位；块数决定了块号的地址程度04，5位；块内地址与页内地址的长度相等；故：
