1、第四章 存 储 器 管 理 第四章第四章 存储器管理存储器管理 4.1 存储器的层次结构存储器的层次结构 4.2程序的装入和链接程序的装入和链接 4.3连续分配方式连续分配方式4.4基本分页存储管理方式基本分页存储管理方式4.5基本分段存储管理方式基本分段存储管理方式4.6虚拟存储器的基本概念虚拟存储器的基本概念4.7请求分页存储管理方式请求分页存储管理方式4.8页面置换算法页面置换算法4.9请求分段存储管理方式请求分段存储管理方式 第四章 存 储 器 管 理 4.1 存储器的层次结构存储器的层次结构寄存器高速缓存主存磁盘缓存磁盘可移动存储介质CPU寄存器主存辅存寄存器、高速缓存、主存储器和磁
2、盘缓存均属于操作系统寄存器、高速缓存、主存储器和磁盘缓存均属于操作系统存储管理的管辖范畴，掉电后它们存储的信息不再存在。存储管理的管辖范畴，掉电后它们存储的信息不再存在。在主存中第四章 存 储 器 管 理 存储器管理：存储器管理：指内存的管理，外存管理在文件部分讲述；指内存的管理，外存管理在文件部分讲述； 单道程序系统：单道程序系统：内存被划分成两部分：一部分供内存被划分成两部分：一部分供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,50012341234
8、0 0100100500500600600Mov r1,1500Mov r1,15000 01000100011001100150015001600160012341234作业的地址空间作业的地址空间存储空间存储空间装入程序装入程序第四章 存 储 器 管 理 静态映射优缺点静态映射优缺点优点：不需要硬件的支持，简单易实现，成本低；优点：不需要硬件的支持，简单易实现，成本低；缺点：程序必须占用连续的内存空间；一旦程序装入缺点：程序必须占用连续的内存空间；一旦程序装入后不能移动；后不能移动；主存利用率低；难以做到程序和数据的主存利用率低；难以做到程序和数据的共享。共享。第四章 存 储 器 管 理
9、动态地址映射（重定位）动态地址映射（重定位）动态地址重定位：动态地址重定位：在程序执行的过程中，每次将要访问的指令或数在程序执行的过程中，每次将要访问的指令或数据逻辑地址转换为内存地址。据逻辑地址转换为内存地址。动态映射方法：动态映射方法：装入程序把程序和数据装入程序把程序和数据原样装入原样装入到已分配的存储区到已分配的存储区中，然后把这个存储区的起始地址送入中，然后把这个存储区的起始地址送入重定位寄存器重定位寄存器中。在程序执中。在程序执行时，再将相对地址转换成绝对地址。行时，再将相对地址转换成绝对地址。硬件支持：硬件支持：在动态地址重定位机构中，有一个在动态地址重定位机构中，有一个基地址寄
10、存器基地址寄存器BRBR和一和一个个程序地址寄存器程序地址寄存器VRVR，一个，一个内存地址寄存器内存地址寄存器MRMR。转换过程：转换过程：MR=BR+VRMR=BR+VR第四章 存 储 器 管 理 把程序装入起始地址为把程序装入起始地址为10001000的内存区的内存区123412340 0100100500500599599作业的地址空间作业的地址空间0 01000100011001100150015001599159912341234存储空间存储空间10001000+ +重定位寄存器重定位寄存器逻辑地址逻辑地址VRVR物理地址物理地址MRMRMOV r1MOV r1， 500500 M
11、OV r1MOV r1， 500500 第四章 存 储 器 管 理 动态地址映射的过程动态地址映射的过程程序装入内存后，它所占用的内存区的程序装入内存后，它所占用的内存区的首地址首地址由系统送入由系统送入基地址寄存器基地址寄存器BRBR中。中。在程序执行的过程中，若要访问内存，将访问的逻辑地址在程序执行的过程中，若要访问内存，将访问的逻辑地址送入送入VRVR中。中。 地址转换机构把地址转换机构把VRVR和和BRBR中的内容相加，并将结果送入中的内容相加，并将结果送入MRMR中，中，作为实际访问的地址。作为实际访问的地址。第四章 存 储 器 管 理 动态重定位优缺点动态重定位优缺点优点：优点：1
12、 1）程序占用的内存空间是动态可变的，当程序从）程序占用的内存空间是动态可变的，当程序从某个存储区移到另一个区域时，只需要修改相应的寄存器某个存储区移到另一个区域时，只需要修改相应的寄存器BRBR的内容即可；的内容即可；2 2）一个程序不一定要求占用一个连续的）一个程序不一定要求占用一个连续的内存空间，可以部分地装入程序运行；内存空间，可以部分地装入程序运行；4 4）便于多个进程）便于多个进程共享同一个程序的代码。共享同一个程序的代码。动态地址重定位的代价：动态地址重定位的代价：1 1）需要硬件的支持；）需要硬件的支持；2 2）实现存）实现存储管理的软件算法较为复杂。储管理的软件算法较为复杂。
13、第四章 存 储 器 管 理 4.2 程序的装入和链接程序的装入和链接 （可能产生）可执行程序文件编译链接装入二进制内存映像程序处理步骤：编译-编译程序，负责检查语法错，涉及名空间。输入：源程序； 输出：多个目标模块；链接-链接程序，负责将多个模块相关联，涉及逻辑地址空间。输入：多个目标模块、库函数；输出：装入模块；装入：装入程序，负责内存分配和地址映射，涉及内存空间。输入：装入模块；输出：可执行的二进制内存映像。过程或函数可能分别对应一个模块！库链接程序装入模块装入程序编译程序产生的目标模块第一步第二步第三步内存第四章 存 储 器 管 理 4.1.2 4.1.2 程序的链接程序的链接 1. 1
14、. 静态链接方式静态链接方式(Static Linking) (Static Linking) 图 4-3 程序链接示意图 模块 ACALL B；Return；0L1模块 BCALL C；Return；0M1模块 CReturn；0N10模块 AJSR“L”Return；L1模块 BJSR“LM”Return；LLM1LMLMN1模块 CReturn；(a) 目标模块(b) 装入模块链接前，链接前，每个模每个模块都有块都有各自的各自的相对起相对起始地址始地址0 0链接后，链接后，每个模每个模块使用块使用同一个同一个相对起相对起始地址始地址0 0名空间名空间逻辑地址空间逻辑地址空间在程序运行之前
15、，先将各目标模块及它们所需的库函数，链接成一个完整的装入模块，又称为链接成一个完整的装入模块，又称为可执行文件可执行文件，以后不再拆开。解决：对相对地解决：对相对地址进行修改；变换外部调用符号址进行修改；变换外部调用符号不要求！不要求！第四章 存 储 器 管 理 2. 2. 装入时动态链接装入时动态链接(Load(Loadtime Dynamic Linking) time Dynamic Linking) 基本思想：基本思想：源程序被编译生成的目标模块，是在装入内源程序被编译生成的目标模块，是在装入内存时，边装入边连接。装入程序根据外部模块调用而存时，边装入边连接。装入程序根据外部模块调用而
16、逐个装入和连接。装入时动态链接方式有以下优点逐个装入和连接。装入时动态链接方式有以下优点 便于修改和更新：便于修改和更新：各个模块的修改极易编译和连接；各个模块的修改极易编译和连接； 便于实现对目标模块的共享：便于实现对目标模块的共享：将内存中的一个模块可将内存中的一个模块可以连接到多个程序中。以连接到多个程序中。 要运行的程序都必须在装入时，全部连接调入内存。要运行的程序都必须在装入时，全部连接调入内存。 第四章 存 储 器 管 理 3. 3. 运行时动态链接运行时动态链接(Run-time Dynamic Linking) (Run-time Dynamic Linking) 动态链接方式
17、：动态链接方式：将对某些模块的链接推迟到执行时才实施，将对某些模块的链接推迟到执行时才实施，亦即，在执行过程中，当发现一个被调用模块尚未装亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由入内存时，立即由OSOS去找到该模块并将之装入内存，去找到该模块并将之装入内存，把它链接到调用者模块上。特点如下：把它链接到调用者模块上。特点如下：特点：特点：凡在执行过程中未被用到的目标模块，都不会被调凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。的装入过程，而且可节省
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,25003651000011000125001500050
20、00250010000作业地址空间内存空间又称静态重定位：地址变换在装入时又称静态重定位：地址变换在装入时一次完成，其后不能移动。一次完成，其后不能移动。逻辑地址（相对地址）逻辑地址（相对地址）物理地址物理地址（绝对地（绝对地址）址）LOAD 1,LOAD 1,1250012500第四章 存 储 器 管 理 3. 3. 动态运行时装入方式动态运行时装入方式(Denamle Run-time Loading) (Denamle Run-time Loading) 动态运行时装方式：动态运行时装方式：装入内存后的所有地址都仍是相对地址；装入内存后的所有地址都仍是相对地址；逻辑地址到逻辑地址到物理地
21、址的变换要推迟到程序真正执行时才进行；物理地址的变换要推迟到程序真正执行时才进行；地址变换发生在程序执行过程中（即动态重定位）地址变换发生在程序执行过程中（即动态重定位）。为使地址转换不影响程序执行速度，必须使用硬件支为使地址转换不影响程序执行速度，必须使用硬件支持。持。第四章 存 储 器 管 理 链接和装入的关系（一） 静态链接会形成磁盘上的可执行文件，而装入时动态链接和运行时动态链接不会产生磁盘上的可执行文件。 静态链接产生的可执行文件装入时内存是连续分配的，而地址映射既可采用可重定位装入方式（静态重定位）也可以采用动态运行时装入方式（动态重定位）第四章 存 储 器 管 理 链接和装入间的
22、关系（二） 装入时动态链接方式可以分别给每个装入模块分配一块内存区域，因而装入时各模块不一定连续存放。 装入时的地址映射既可采用可重定位装入方式（静态重定位-链接后运行前一次性修改逻辑地址为物理地址）也可以采用动态运行时装入方式（动态重定位-运行时动态计算出逻辑地址到物理地址的映射）第四章 存 储 器 管 理 链接和装入间的关系（三） 运行时动态链接方式一般情况下后装入的模块和原先已装入的模块是不连续存放的。 运行时动态链接方式的地址变换不可能运行前一次性映射地址，即不可能采用静态重定位方法，而只能使用动态重定位的方法。第四章 存 储 器 管 理 链接和装入间的关系（四） 链接链接装入装入静态
23、链接静态链接装入时动态链接装入时动态链接运行时动态链接运行时动态链接连续或不连续分配连续均可一般不连续静态重定位或动态重定位均可均可动态重定位第四章 存 储 器 管 理 4.2 4.2 连续分配方式连续分配方式4.2.1 4.2.1 单一连续分配单一连续分配 特征：特征：最简单的一种存储管理方最简单的一种存储管理方式，但只能用于单用户、单任务式，但只能用于单用户、单任务的操作系统中；常把内存分为系的操作系统中；常把内存分为系统区和用户区两部分，系统区仅统区和用户区两部分，系统区仅提供给提供给OSOS使用，通常是放在内使用，通常是放在内存的低址部分；用户区是指除系存的低址部分；用户区是指除系统区
24、以外的全部内存空间，统区以外的全部内存空间， 提供提供给用户使用。给用户使用。 OS用户区用户区第四章 存 储 器 管 理 4.2.2 4.2.2 固定分区分配固定分区分配 1. 1. 划分分区的方法划分分区的方法 分区大小相等，分区大小相等， 即使所有的内存分区大小相等。即使所有的内存分区大小相等。缺点：缺缺点：缺乏灵活性，大作业无法运行，小作业浪费空间。乏灵活性，大作业无法运行，小作业浪费空间。 分区大小不等，即划分为小、中、大不等的固定分区。分区大小不等，即划分为小、中、大不等的固定分区。优优点：灵活性好。点：灵活性好。 分配方法：分配方法：将用户空间划分为若干个固定大小的区域，在每个分
25、将用户空间划分为若干个固定大小的区域，在每个分区中装入一道作业；有几个分区，就有几道并发的作业；有区中装入一道作业；有几个分区，就有几道并发的作业；有空闲分区时，可调入一适当大小的作业；最简单的一种多道空闲分区时，可调入一适当大小的作业；最简单的一种多道程序存储管理方法。程序存储管理方法。第四章 存 储 器 管 理 2. 2. 内存分配内存分配 ：为了便于内存分配，将分区按照大小排队，并建立一为了便于内存分配，将分区按照大小排队，并建立一个分区表。如图所示。当为作业分配空间时，分配程序按照此表检个分区表。如图所示。当为作业分配空间时，分配程序按照此表检索以合适分区分配；否则，拒绝分配。索以合适
26、分区分配；否则，拒绝分配。缺点：缺点：空间浪费。空间浪费。图 4-4 固定分区使用表 第四章 存 储 器 管 理 4.2.3 4.2.3 动态分区分配动态分区分配 1. 1. 分区分配中的数据结构分区分配中的数据结构 (1) 空闲分区表。 (2) 空闲分区链。 图 4-5 空闲链结构 前向指针N20N个字节可用后向指针N20分配思想：分配思想：根据进程的实际需要，动态的为进程分配（切分）内根据进程的实际需要，动态的为进程分配（切分）内存空间，及需要多大，分配多大。提高内存的利用率。存空间，及需要多大，分配多大。提高内存的利用率。第四章 存 储 器 管 理 未分配区表用空闲区链表表示：未分配区表
27、用空闲区链表表示：0010k10k270k00730k730k 100k100k100k270k 空闲区链空闲区链head空闲区大小第四章 存 储 器 管 理 2. 2. 分区分配算法分区分配算法 首次适应算法首次适应算法FFFF：空闲分区按地址递增成链表；每次分配从链首空闲分区按地址递增成链表；每次分配从链首依次查找一空间首次满足作业的空闲分区；再从该分区中切出与依次查找一空间首次满足作业的空闲分区；再从该分区中切出与作业等量的空间分之，余者挂到链表中；若找不到满足作业空间作业等量的空间分之，余者挂到链表中；若找不到满足作业空间要求的空闲分区，分配失败。要求的空闲分区，分配失败。优缺点：优缺
28、点：低地址部分将产生多个较小的空闲分区（碎片），增加低地址部分将产生多个较小的空闲分区（碎片），增加分配开销。分配开销。问题：问题：如何从空闲分区表或链表中，选择一分区分配个作业，如何从空闲分区表或链表中，选择一分区分配个作业，常用的算法如下：常用的算法如下：第四章 存 储 器 管 理 2. 2. 分区分配算法分区分配算法 循环首次适应算法：循环首次适应算法：该算法是由首次适应算法演变而成的，区别该算法是由首次适应算法演变而成的，区别仅是从上次已分配分区的下一个分区依次查找首次满足作业的空仅是从上次已分配分区的下一个分区依次查找首次满足作业的空闲分区，并从中划分出作业需要的分区。闲分区，并从中
29、划分出作业需要的分区。实现方法：实现方法：起始循环指针起始循环指针+ +循环空闲分区链表循环空闲分区链表 最佳适应算法：最佳适应算法：空闲链表依照空间大小排列，每次从链首为作业空闲链表依照空间大小排列，每次从链首为作业找一个大小最合适的分区分配。找一个大小最合适的分区分配。缺点：缺点：最佳适应必将产生最小的空闲碎片。最佳适应必将产生最小的空闲碎片。 最坏适应算法最坏适应算法(worst fit)(worst fit)：总是挑选一个最大的空闲区分割给作业总是挑选一个最大的空闲区分割给作业使用，其优点是可使剩下的空闲区不至于太小，产生碎片的几率使用，其优点是可使剩下的空闲区不至于太小，产生碎片的几
30、率最小，对中、小作业有利，同时最坏适应分配算法查找效率很高。最小，对中、小作业有利，同时最坏适应分配算法查找效率很高。第四章 存 储 器 管 理 3. 3. 分区分配操作分区分配操作 1)1)分配内存操作分配内存操作 分配操作如左分配操作如左图所示图所示从头开始查表检索完否？m.sizeu.size?m.sizeu.sizesize?从该分区中划出u.size大小的分区将该分区分配给请求者修改有关数据结构返回返回继续检索下一个表项将该分区从链中移出YNNYYN第四章 存 储 器 管 理 2)2)回收内存操作回收内存操作 回收的分区有回收的分区有4 4种情况：与前、后、前后空分区相邻，如下图所示
31、。种情况：与前、后、前后空分区相邻，如下图所示。图 4-7 内存回收时的情况 第四章 存 储 器 管 理 当回收分区与前后空闲分区均不相邻时，为回收分区建当回收分区与前后空闲分区均不相邻时，为回收分区建立一个空闲分区结点，并插入链表适当位置。立一个空闲分区结点，并插入链表适当位置。回收分区回收分区第四章 存 储 器 管 理 4.2.4 4.2.4 可重定位分区分配可重定位分区分配 1. 1. 动态重定位的引入：动态重定位的引入：动态回收碎片，将小而不可用的空闲分区拼接动态回收碎片，将小而不可用的空闲分区拼接成较大的一个空闲分区。移动作业分区，必然要重定位。成较大的一个空闲分区。移动作业分区，必
32、然要重定位。 图 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,25003651000010100125001500
33、0作业J处理机一侧 存储器一侧主存第四章 存 储 器 管 理 3. 3. 动态重定位分区分配算法：在动态分区算法增加了回收碎片的功能。动态重定位分区分配算法：在动态分区算法增加了回收碎片的功能。图 4-10 动态分区分配算法流程图 请求分配u.size分区检索空闲分区链(表)找到大于u.size的可用区否?按动态分区方式进行分配修改有关的数据结构返回分区号及首批空闲分区总和u.size?进行紧凑形成连续空闲区修改有关的数据结构否是无法分配返回否第四章 存 储 器 管 理 作业4-1 P142 ： 4、5、6第四章 存 储 器 管 理 4.2.5 4.2.5 对换对换(Swapping) (Sw
34、apping) 1. 1. 对换的引入对换的引入 对换定义：对换定义：对换对换是指把内存中暂时不能运行的进程或者暂时不用的程是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据调入内存。备运行条件的进程或进程所需要的程序和数据调入内存。对换目的：对换目的：提高内存的利用率。提高内存的利用率。进程对换：进程对换：如果对换是以整个进程为单位进行的，则称为进程对换或如果对换是以整个进程为单位进行的，则称为进程对换或整体对换；整体对换；页面对换：页面对换：如
35、果对换是以页或段为单位进行的，称为页面对换或分段如果对换是以页或段为单位进行的，称为页面对换或分段对换，统称部分对换。对换，统称部分对换。在实现虚拟存储系统时候，依靠页面或分在实现虚拟存储系统时候，依靠页面或分段对换。段对换。第四章 存 储 器 管 理 2. 2. 对换空间的管理对换空间的管理实现进程对换系统必须具备三个功能：实现进程对换系统必须具备三个功能：对换空间管理、进程的换出和进对换空间管理、进程的换出和进程的换入。首先研究对换空间管理：程的换入。首先研究对换空间管理： 将外存磁盘空间划分为文件区和对换区：将外存磁盘空间划分为文件区和对换区：文件区用于存放文件，管文件区用于存放文件，管
36、理以提高存储空间的利用率为目的；后者用于存储对换的进程，故理以提高存储空间的利用率为目的；后者用于存储对换的进程，故应以提高对换速度为目标。应以提高对换速度为目标。 对换去空间管理：对换去空间管理：建立对换区空闲空间分区表（链）数据结构。建立对换区空闲空间分区表（链）数据结构。其其形式与内存动态分区分配方式中的空闲分区表或空闲分区链。在空形式与内存动态分区分配方式中的空闲分区表或空闲分区链。在空闲分区表中的每个表项中应包含两项，对换区的首址及其大小，它闲分区表中的每个表项中应包含两项，对换区的首址及其大小，它们的单位是盘块号和盘块数。们的单位是盘块号和盘块数。第四章 存 储 器 管 理 2.
37、2. 对换空间的管理对换空间的管理 对换区分配：对换区分配：采用连续分配，雷同内存动态分区方式的分配算法：采用连续分配，雷同内存动态分区方式的分配算法：可用首次适应算法，循环首次适应算法或最佳适应算法。可用首次适应算法，循环首次适应算法或最佳适应算法。 对换区回收：对换区回收：也与内存动态分区回收算法雷同，要考虑回收区与也与内存动态分区回收算法雷同，要考虑回收区与前后地址相邻（磁盘块号）分区的合并。前后地址相邻（磁盘块号）分区的合并。第四章 存 储 器 管 理 3. 3. 进程的换出与换入进程的换出与换入 进程的换出：进程的换出：每当创建一新进程而又无足够的内存空间时，系统每当创建一新进程而又
38、无足够的内存空间时，系统应将某进程换出。应将某进程换出。 换出过程：换出过程：系统首先选择处于阻塞状态且优先级最低的进程作为系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，并将该进程的程序和数据安全传送到磁盘的对换区上；换出进程，并将该进程的程序和数据安全传送到磁盘的对换区上；然后回收该进程所占用的内存空间，并对该进程的进程控制块做然后回收该进程所占用的内存空间，并对该进程的进程控制块做相应的修改（该什么？）。相应的修改（该什么？）。 进程的换入：进程的换入：系统定时找出系统定时找出“静止就绪静止就绪”状态的进程，并将其中状态的进程，并将其中换出时间最久的进程作为换入进程换入，直至已无
39、可换入的进程换出时间最久的进程作为换入进程换入，直至已无可换入的进程 第四章 存 储 器 管 理 4.3 4.3 基本分页存储管理方式基本分页存储管理方式 问题：问题：由于为进程连续分配内存空间，将产生大量碎片；为了利用碎片必由于为进程连续分配内存空间，将产生大量碎片；为了利用碎片必须将其合并，又需要系统开销。须将其合并，又需要系统开销。能否给进程离散（不连续）地分配内能否给进程离散（不连续）地分配内存空间，解决这些问题存空间，解决这些问题？离散分配：离散分配：当前使用最多的内存分配方式是分页管理方式和分段管理方式；当前使用最多的内存分配方式是分页管理方式和分段管理方式；分页是页面为单位进行内
40、存分配，分段方式是以段为单位进行内存分分页是页面为单位进行内存分配，分段方式是以段为单位进行内存分配。配。基本分页（段）存储管理方式：基本分页（段）存储管理方式：如果分页或分段存储管理方式中不具备页如果分页或分段存储管理方式中不具备页面或分段对换功能，将其称之为基本分页或基本分段存储管理方式。面或分段对换功能，将其称之为基本分页或基本分段存储管理方式。第四章 存 储 器 管 理 4.3.1 4.3.1 页面与页表页面与页表 1. 1. 页面与物理块页面与物理块 页面：页面：将一个进程的逻辑地址空间分成若干个大小相等的片，称为页将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各
41、页顺序编号为面或页，并为各页顺序编号为0 0、1 1、2 2、n n。 物理块：物理块：把内存空间分成与页面相同大小的若干个存储块，称为把内存空间分成与页面相同大小的若干个存储块，称为( (物理物理) )块或页框块或页框(frame)(frame)， 也同样为它们加以编号，如也同样为它们加以编号，如0 0块、块、1 1块等等。块等等。 内存分配原理：内存分配原理：在为进程分配内存时，以页面为单位给进程离散分配在为进程分配内存时，以页面为单位给进程离散分配与页面数等量的物理块，并分别装入到相应的物理块中与页面数等量的物理块，并分别装入到相应的物理块中（全部（全部装装入）入） 页内碎片：页内碎片：
42、由于进程的最后一页经常装不满一块而形成了不可利用的由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为碎片，称之为“页内碎片页内碎片”。第四章 存 储 器 管 理 举例：举例：如左图所示，如左图所示，按照基本分页存按照基本分页存储管理方式为进储管理方式为进程分配内存空间。程分配内存空间。设页面大小为设页面大小为1KB1KB第四章 存 储 器 管 理 页面大小设定：页面大小设定：在分页系统中的页面其大小应适中，且页面大小应在分页系统中的页面其大小应适中，且页面大小应是是2 2的幂，通常为的幂，通常为512 B8 KB512 B8 KB。 页面大小利弊：页面大小利弊：若页面太小，若页面太
43、小，内存碎片减小，从而减少了内存碎片内存碎片减小，从而减少了内存碎片的总空间，提高内存利用率；但另一方面也会使每个进程占用较多的总空间，提高内存利用率；但另一方面也会使每个进程占用较多的页面，从而导致进程的页表过长，占用大量内存等；的页面，从而导致进程的页表过长，占用大量内存等；若页面较大，若页面较大，可以减少页表的长度，节省内存，但却又会使页内碎片增大。可以减少页表的长度，节省内存，但却又会使页内碎片增大。第四章 存 储 器 管 理 2、逻辑地址结构页号页号 页内地址页内地址0111231页号页号P页内位移量页内位移量W编号编号01048575相对地址相对地址04095最大页面数： 220=
44、1M个页面大小： 212=4KB逻辑空间： 0232-1一维的，并针对程序员第四章 存 储 器 管 理 逻辑地址空间中的地址为逻辑地址空间中的地址为A A，页面大小为，页面大小为L L，则有：，则有： P=INTA/L d=A MOD L例：A=2170B，L=1KB时，则有P=2，d=122第四章 存 储 器 管 理 3 3、页表、页表分页存储管理方式按照进程页面的多少，为进程离散分分页存储管理方式按照进程页面的多少，为进程离散分配相同数量的物理块，为了记录每一页所分配的物理块，配相同数量的物理块，为了记录每一页所分配的物理块，必须为每个进程建立一个页表必须为每个进程建立一个页表每个进程一个
45、页表，每个页面一个表项；每个进程一个页表，每个页面一个表项；表项：表项：页号页号：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.基本的地址变换机构基本的地址变换机构 ：实现
46、逻辑地址向物理地址的转换。由于页实现逻辑地址向物理地址的转换。由于页内地址与块内地址一一对应，所以地址转换关键是将逻辑地址中内地址与块内地址一一对应，所以地址转换关键是将逻辑地址中的页号转换为内存中的物理块号。的页号转换为内存中的物理块号。2.2.转换机构设施：转换机构设施：页表寄存器：页表寄存器：存放进程页表在内存中的起地址和存放进程页表在内存中的起地址和页表长度（进程不执行时放在页表长度（进程不执行时放在PCBPCB中，执行时调入寄存器中）；中，执行时调入寄存器中）；物理地址寄存器：物理地址寄存器：存放转换后的物理地址（内存地址）；存放转换后的物理地址（内存地址）；3.3.查找表项：查找表
47、项：表项地址表项地址= =页表起始地址页表起始地址+ +页号页号* *表项长度；表项长度；4.4.地址转换过程如下图。地址转换过程如下图。 图 4-12 分页系统的地址变换机构 第四章 存 储 器 管 理 页表寄存器页表始址页表长度页号(3)页内地址逻辑地址L越界中断1块号b页表页号012物理地址3第四章 存 储 器 管 理 例例 说明运行进程的地址变换过程。说明运行进程的地址变换过程。 如下图所示，进程程序地址空间共有如下图所示，进程程序地址空间共有7 7个页，每页的大小个页，每页的大小为为10241024。其对应的主存块在页表中已列出。假定页表在主。其对应的主存块在页表中已列出。假定页表在
48、主存始址为存始址为500500。若该程序从第。若该程序从第0 0页开始运行，且现程序计数页开始运行，且现程序计数器内容为：器内容为：0100程序计数器：程序计数器：逻辑地址逻辑地址第四章 存 储 器 管 理 页表寄存器页表寄存器程序计数器程序计数器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内存地址：内
49、存地址：5 51024+100=52201024+100=5220500+0=500500+0=500第四章 存 储 器 管 理 例：例：有一系统采用页式存储管理，有一作业大小是有一系统采用页式存储管理，有一作业大小是8KB8KB，页，页大小为大小为2KB2KB，依次装入内存的第，依次装入内存的第7 7、9 9、1010、5 5块，试将虚块，试将虚地址地址71457145，34123412转换成内存地址。转换成内存地址。第四章 存 储 器 管 理 虚地址虚地址 71457145P P7145 7145 2048 2048 3 3W W7145 mod 20487145 mod 2048 100
50、11001MR=5MR=5* *2048+1001=112412048+1001=11241虚地址虚地址71457145的内存地址是：的内存地址是：1124111241虚地址虚地址 34123412P P3412 3412 2048 2048 1 1W W3412 mod 20483412 mod 2048 13641364MR=9MR=9* *2048+1364=197962048+1364=19796虚地址虚地址34123412的内存地址是：的内存地址是：1979619796第四章 存 储 器 管 理 2 2、具有快表的地址变换机构、具有快表的地址变换机构问题：问题：两次访问内存两次访问内
