1、 第第4章章 存储管理存储管理 本章的主要内容：本章的主要内容：（1 1）地址重定位的引入、概念及方法。）地址重定位的引入、概念及方法。（2 2）对内存进行连续分配存储管理的方法，包括单一连续分配方式）对内存进行连续分配存储管理的方法，包括单一连续分配方式和分区分配方式。和分区分配方式。（3 3）为了有效利用内存而采用的紧凑和交换技术。）为了有效利用内存而采用的紧凑和交换技术。（4 4）对内存进行离散分配存储管理的方法，包括分页存储管理方式、）对内存进行离散分配存储管理的方法，包括分页存储管理方式、分段存储管理方式和段页式存储管理方式。分段存储管理方式和段页式存储管理方式。（5 5）虚拟存储器
2、的概念及请求分页存储管理、请求分段存储管理和）虚拟存储器的概念及请求分页存储管理、请求分段存储管理和请求段页式存储管理的实现。请求段页式存储管理的实现。第第4章章 存储管理存储管理 第第4章章 存储管理存储管理4.1 4.1 程序的链接和装入程序的链接和装入4.2 4.2 存储器及存储管理的基本功能存储器及存储管理的基本功能4.3 4.3 分区式存储管理分区式存储管理4.4 4.4 分页存储管理分页存储管理4.5 4.5 分段存储管理分段存储管理4.6 4.6 段页式存储管理段页式存储管理4.7 4.7 虚拟存储管理虚拟存储管理 源程序转变为可执行程序：首先由编译程序把源程序编译成若源程序转变
3、为可执行程序：首先由编译程序把源程序编译成若干个目标模块，然后由链接程序把所有目标模块和它们需要的库函干个目标模块，然后由链接程序把所有目标模块和它们需要的库函数链接在一起，形成一个完整的可装入模块。可装入模块可以通过数链接在一起，形成一个完整的可装入模块。可装入模块可以通过装入程序装入内存成为可执行程序，当把装入程序装入内存成为可执行程序，当把CPUCPU分配给它时就可以投入分配给它时就可以投入运行。运行。4.1 程序的链接和装入 （1 1）逻辑地址。逻辑地址。（2 2）逻辑地址空间。逻辑地址空间。4.1 程序的链接和装入 （3 3）物理地址。物理地址。（4 4）物理地址空间。物理地址空间。
4、（5 5）虚拟地址空间。虚拟地址空间。4.1 程序的链接和装入 链接程序在将几个目标模块装配成一个装入模块时，需要解链接程序在将几个目标模块装配成一个装入模块时，需要解决以下问题：决以下问题：（1 1）修改模块的相对地址。）修改模块的相对地址。（2 2）转换外部调用符号。）转换外部调用符号。4.1 程序的链接和装入 目标模块链接方式目标模块链接方式（1 1）静态链接。程序运行前把源程序编译成的所有目标模块及所）静态链接。程序运行前把源程序编译成的所有目标模块及所需要的库函数链接成一个统一的装入模块，以后不再分开。需要的库函数链接成一个统一的装入模块，以后不再分开。（2 2）装入时动态链接。目标
5、模块的链接是在模块装入内存时进行）装入时动态链接。目标模块的链接是在模块装入内存时进行的，即在模块装入过程中同时完成所有目标模块的链接。的，即在模块装入过程中同时完成所有目标模块的链接。（3 3）运行时动态链接。先将一个目标模块装入内存且启动运行，）运行时动态链接。先将一个目标模块装入内存且启动运行，在进程运行过程中如果需要调用其他模块，则再将所需模块装入在进程运行过程中如果需要调用其他模块，则再将所需模块装入内存并把它链接到调用模块上，然后进程继续运行。内存并把它链接到调用模块上，然后进程继续运行。4.1 程序的链接和装入 程序装入程序装入 1.1.程序装入程序装入要使装入内存的程序能够运行
6、，系统必须将程序中的逻辑地址转换要使装入内存的程序能够运行，系统必须将程序中的逻辑地址转换为机器能够直接寻址的物理地址。因此，为机器能够直接寻址的物理地址。因此，这种地址转换操作称为地址映射、地址转换这种地址转换操作称为地址映射、地址转换或重定位。或重定位。程序装入是指装入程序根据内存当前的实际使用情况，将装入模程序装入是指装入程序根据内存当前的实际使用情况，将装入模块（程序）装入到内存合适的物理位置。块（程序）装入到内存合适的物理位置。4.1 程序的链接和装入 程序装入分类程序装入分类 静态装入静态装入-（相对地址）（相对地址）（绝对地址）（绝对地址）。运行时动态装入运行时动态装入-4.1
7、程序的链接和装入 2.2.静态重定位静态重定位 指装入程序将程序（装入模块）装入到内存后，指装入程序将程序（装入模块）装入到内存后，一次性地将程序中所有指令中要访问的地址按一次性地将程序中所有指令中要访问的地址按下面的公式全部由相对地址（逻辑地址）转换为绝对地址（物理地下面的公式全部由相对地址（逻辑地址）转换为绝对地址（物理地址），并在程序运行过程中不再改变：址），并在程序运行过程中不再改变：绝对地址相对地址程序存放的内存起始地址绝对地址相对地址程序存放的内存起始地址4.1 程序的链接和装入 静态重定位优点静态重定位优点:简单、容易实现，不需要增加任何硬件设备，可以通过软件全部简单、容易实现，
8、不需要增加任何硬件设备，可以通过软件全部实现。实现。静态重定位缺点静态重定位缺点:（1 1）程序装入内存后，在运行期间不允许该程序在内存中移动，即）程序装入内存后，在运行期间不允许该程序在内存中移动，即无法实现内存重新分配，因此内存的利用率不高。无法实现内存重新分配，因此内存的利用率不高。（2 2）如果内存提供的物理存储空间无法满足当前程序的存储容量，）如果内存提供的物理存储空间无法满足当前程序的存储容量，则必须由用户在程序设计时采用某种方法来解决存储空间不足的问题，则必须由用户在程序设计时采用某种方法来解决存储空间不足的问题，这无疑增加了用户的负担。这无疑增加了用户的负担。（3 3）不利于用
9、户共享存放在内存中的同一个程序。如果几个用户要）不利于用户共享存放在内存中的同一个程序。如果几个用户要使用同一个程序，就必须在各自的内存空间中存放该程序的副本，这使用同一个程序，就必须在各自的内存空间中存放该程序的副本，这浪费了内存资源。浪费了内存资源。4.1 程序的链接和装入 3.3.动态重定位动态重定位 指将装入模块装入内存后，并不立即完成相对地址到绝对指将装入模块装入内存后，并不立即完成相对地址到绝对地址的转换，地址的转换工作是在程序运行过程中进行的，即地址的转换，地址的转换工作是在程序运行过程中进行的，即执行到要访问指令或数据的相对地址时再进行转换。执行到要访问指令或数据的相对地址时再
10、进行转换。地址重定位机构需要一个（或多个）基地址寄存器（也称地址重定位机构需要一个（或多个）基地址寄存器（也称重定位寄存器，重定位寄存器，BRBR）和一个（或多个）程序逻辑地址寄存器）和一个（或多个）程序逻辑地址寄存器（VRVR）。指令或数据在内存中的绝对地址与逻辑地址的关系为：）。指令或数据在内存中的绝对地址与逻辑地址的关系为：绝对地址绝对地址(BR)(BR)(VR)(VR)4.1 程序的链接和装入 动态重定位过程动态重定位过程 装入程序将程序（装入模块）装入到内存，然后将程序装入程序将程序（装入模块）装入到内存，然后将程序所装入的内存区域首地址作为基地址送入所装入的内存区域首地址作为基地址
11、送入BRBR中。在程序运行中。在程序运行过程中，当某条指令访问到一个相对地址时，则将该相对地过程中，当某条指令访问到一个相对地址时，则将该相对地址送入址送入VRVR中；这时，硬件地址转换机构把中；这时，硬件地址转换机构把BRBR和和VRVR中的内容相中的内容相加就形成了要访问的实际物理地址（绝对地址）。加就形成了要访问的实际物理地址（绝对地址）。4.1 程序的链接和装入 动态重定位优点：动态重定位优点：（1 1）指令和数据的物理地址是在程序运行过程中由硬件动态形成的；）指令和数据的物理地址是在程序运行过程中由硬件动态形成的；（2 2）动态重定位的地址转换工作在程序真正执行到该指令时才进行；）动
12、态重定位的地址转换工作在程序真正执行到该指令时才进行；（3 3）动态重定位有利于对程序段进行共享。）动态重定位有利于对程序段进行共享。动态重定位缺点：动态重定位缺点：（1 1）需要硬件支持；（）需要硬件支持；（2 2）实现存储管理的软件算法比较复杂。）实现存储管理的软件算法比较复杂。4.1 程序的链接和装入 4.1 程序的链接和装入 内存管理目标内存管理目标:（1 1）地址保护。一个程序不能访问另一个程序的地址空间。）地址保护。一个程序不能访问另一个程序的地址空间。（2 2）地址无关。用户并不关心程序中使用的是何种地址，此时程序）地址无关。用户并不关心程序中使用的是何种地址，此时程序是在内存还
13、是在外存，这些工作应由内存管理自动完成。是在内存还是在外存，这些工作应由内存管理自动完成。存储管理基本功能：存储管理基本功能：（1 1）内存空间的分配与回收。按程序要求进行内存分配，当程序完）内存空间的分配与回收。按程序要求进行内存分配，当程序完成后适时回收内存。成后适时回收内存。（2 2）实现地址转换。实现程序中的逻辑地址到内存物理地址的转换。）实现地址转换。实现程序中的逻辑地址到内存物理地址的转换。（3 3）内存空间的共享与保护。对内存中的程序和数据实施保护。）内存空间的共享与保护。对内存中的程序和数据实施保护。（4 4）内存空间的扩充。实现内存的逻辑扩充，提供给用户更大的存）内存空间的扩
14、充。实现内存的逻辑扩充，提供给用户更大的存储空间，允许比内存容量还大的程序运行。储空间，允许比内存容量还大的程序运行。4.2 存储器及存储管理的基本功能 （1 1）寄存器。寄存器是）寄存器。寄存器是CPUCPU内部的高速存储单元，主要用于存放程序运行过程内部的高速存储单元，主要用于存放程序运行过程中所使用的各种数据。寄存器的存储容量最小，但存取速度最高。中所使用的各种数据。寄存器的存储容量最小，但存取速度最高。（2 2）高速缓冲存储器。简称高速缓存，其存取速度与）高速缓冲存储器。简称高速缓存，其存取速度与CPUCPU速度相当，非常快，速度相当，非常快，但成本高且容量较小（一般为几但成本高且容量
15、较小（一般为几KBKB到几百到几百KBKB），主要用来存放使用频率较高的），主要用来存放使用频率较高的少量信息。少量信息。（3 3）内部存储器。简称内存，又称主存储器。程序需要装入内存方能运行，因）内部存储器。简称内存，又称主存储器。程序需要装入内存方能运行，因此内存储器一般用来存放用户正在执行的程序及使用到的数据。此内存储器一般用来存放用户正在执行的程序及使用到的数据。CPUCPU可随机存取可随机存取其中的数据。内存的存取速度要比高速缓存慢一点，容量要比高速缓存大得多其中的数据。内存的存取速度要比高速缓存慢一点，容量要比高速缓存大得多（一般为几（一般为几GBGB）。）。（4 4）外部存储器。
16、简称外存，又称辅助存储器。外存不能被）外部存储器。简称外存，又称辅助存储器。外存不能被CPUCPU直接访问，一直接访问，一般用来存放大量的、暂时不用的数据信息。外存的存取速度较低且成本也较低，般用来存放大量的、暂时不用的数据信息。外存的存取速度较低且成本也较低，但容量较大（一般为几十但容量较大（一般为几十GBGB到几百到几百GBGB）。）。4.2 存储器及存储管理的基本功能 4.2 存储器及存储管理的基本功能 虽然用于存储数据与虽然用于存储数据与程序的多种存储设备在存程序的多种存储设备在存取速度、存储容量等属性取速度、存储容量等属性方面都各不相同，但是将方面都各不相同，但是将它们组织在一起后就
17、能发它们组织在一起后就能发挥各自的特长，共同承担挥各自的特长，共同承担存储信息的任务，所以现存储信息的任务，所以现代计算机一般采用多级存代计算机一般采用多级存储器体系。储器体系。多级存储器体系示意多级存储器体系示意 1.1.内存空间的分配与回收内存空间的分配与回收 内存管理的首要任务是当用户需要内存时，系统按照一定内存管理的首要任务是当用户需要内存时，系统按照一定的算法把某一空闲的内存空间分配给用户程序（进程）；不需的算法把某一空闲的内存空间分配给用户程序（进程）；不需要时再及时回收，以供其他用户程序使用。要时再及时回收，以供其他用户程序使用。在多道程序设计环境中，内存分配的功能包括制定分配策
18、在多道程序设计环境中，内存分配的功能包括制定分配策略、构造分配用的数据结构、响应用户程序的内存分配请求和略、构造分配用的数据结构、响应用户程序的内存分配请求和回收用户程序释放的内存区。回收用户程序释放的内存区。4.2 存储器及存储管理的基本功能 设计内存分配与回收算法必须考虑的问题：设计内存分配与回收算法必须考虑的问题：（1 1）数据结构数据结构。登记内存的使用情况，记录可供分配的内存空闲区大。登记内存的使用情况，记录可供分配的内存空闲区大小和起始地址，以供分配和回收内存时使用。小和起始地址，以供分配和回收内存时使用。（2 2）放置策略放置策略。决定内存中放置信息的区域（或位置），即怎样在若。
19、决定内存中放置信息的区域（或位置），即怎样在若干个内存空闲区中选择一个或几个空闲区来放置信息。干个内存空闲区中选择一个或几个空闲区来放置信息。（3 3）调入策略调入策略。确定外存中的程序段和数据段在什么时间、以什么样。确定外存中的程序段和数据段在什么时间、以什么样的控制方式进入内存。的控制方式进入内存。（4 4）淘汰策略淘汰策略。在需要将某个程序段或数据段调入内存却出现内存没。在需要将某个程序段或数据段调入内存却出现内存没有足够空闲区时，由淘汰策略来决定把内存中的哪些程序段和数据段有足够空闲区时，由淘汰策略来决定把内存中的哪些程序段和数据段由内存调出放入到外存，以便为调入的程序段或数据段腾出足
20、够的内由内存调出放入到外存，以便为调入的程序段或数据段腾出足够的内存空间。存空间。4.2 存储器及存储管理的基本功能 2.2.地址转换（地址重定位）地址转换（地址重定位）地址转换有地址转换有3 3种方式：种方式：（1 1）编程或编译时产生绝对地址）编程或编译时产生绝对地址 在程序中采用符号地址，然后由编译程序或汇编程序在对该程序编在程序中采用符号地址，然后由编译程序或汇编程序在对该程序编译或汇编时再将这些符号地址转换为绝对地址。译或汇编时再将这些符号地址转换为绝对地址。（2 2）静态地址转换）静态地址转换 在程序装入内存时完成从逻辑地址到物理地址的转换。在程序装入内存时完成从逻辑地址到物理地址
21、的转换。（3 3）动态地址转换）动态地址转换 在程序运行过程中要访问数据或指令中的地址时由系统硬件完成从在程序运行过程中要访问数据或指令中的地址时由系统硬件完成从逻辑地址到物理地址的转换。逻辑地址到物理地址的转换。4.2 存储器及存储管理的基本功能 1.1.内存空间的共享和保护内存空间的共享和保护 两个或多个进程共享内存中相同区域称为内存的共享。两个或多个进程共享内存中相同区域称为内存的共享。共享分为代码共享和数据共享。共享分为代码共享和数据共享。代码共享代码共享指多个进程运行内存中的同一个代码段。指多个进程运行内存中的同一个代码段。数据共享数据共享用于实现进程通信。用于实现进程通信。存储保护
22、的目的是保护系统程序区不被用户有意或无意地存储保护的目的是保护系统程序区不被用户有意或无意地侵犯，不允许用户程序读写不属于自己地址空间的数据，使内侵犯，不允许用户程序读写不属于自己地址空间的数据，使内存中各道程序只能访问它自己的区域，避免各道程序之间相互存中各道程序只能访问它自己的区域，避免各道程序之间相互干扰，特别是当一道程序发生错误时不至于影响其他程序的运干扰，特别是当一道程序发生错误时不至于影响其他程序的运行。行。4.2 存储器及存储管理的基本功能 存储保护方式存储保护方式（1 1）界地址保护）界地址保护 界地址方式主要是防止地址越界，每个进程（程序）都有自己独界地址方式主要是防止地址越
23、界，每个进程（程序）都有自己独立的进程空间，如果一个进程在运行时所产生的地址在其所属空间之立的进程空间，如果一个进程在运行时所产生的地址在其所属空间之外则发生地址越界。常用的界地址保护有以下两种：外则发生地址越界。常用的界地址保护有以下两种：上下界保护和地址检查机构：主要用于静态地址转换。硬件提供上下界保护和地址检查机构：主要用于静态地址转换。硬件提供一对上下界寄存器来分别存放程序装入内存后的首地址和末地址。一对上下界寄存器来分别存放程序装入内存后的首地址和末地址。4.2 存储器及存储管理的基本功能 基址、限长寄存器和动态地址转换机构。这种机制主要用于动态基址、限长寄存器和动态地址转换机构。这
24、种机制主要用于动态地址转换。在计算机中设置两个专门的寄存器，称为基址和限长寄存地址转换。在计算机中设置两个专门的寄存器，称为基址和限长寄存器，这两种寄存器分别存放运行程序在内存的起始地址及其总长度。器，这两种寄存器分别存放运行程序在内存的起始地址及其总长度。4.2 存储器及存储管理的基本功能 4.2 存储器及存储管理的基本功能（2 2）存储键保护）存储键保护 通过保护键匹配来判断存储访问方式是否合法。对每个内存区域通过保护键匹配来判断存储访问方式是否合法。对每个内存区域指定一个键值和若干禁止的访问方式，在进程中也指定键值；如果访指定一个键值和若干禁止的访问方式，在进程中也指定键值；如果访问时内
25、存区域和进程键值不匹配而且是被禁止的访问方式，则发生操问时内存区域和进程键值不匹配而且是被禁止的访问方式，则发生操作越权错误。作越权错误。2.2.内存空间的扩充内存空间的扩充 实现内存扩充的根本办法是充分利用内存与外存资源，即只将当实现内存扩充的根本办法是充分利用内存与外存资源，即只将当前需要使用的部分程序和数据放入内存，而将暂不使用的程序和数据前需要使用的部分程序和数据放入内存，而将暂不使用的程序和数据存于外存，当需要的时候再交换到内存来。存于外存，当需要的时候再交换到内存来。控制数据在内、外存之间交换的基本方式：控制数据在内、外存之间交换的基本方式：（1 1）用户程序自己控制方式。）用户程
26、序自己控制方式。（2 2）操作系统控制方式：）操作系统控制方式：交换方式：交换方式：请求调入方式：请求调入方式：预调入方式：预调入方式：4.2 存储器及存储管理的基本功能 4.3 分区式存储管理 1.1.实现原理实现原理特点：特点：只适合于单用户单任务操作系统，是一种最简单的存储管理方式。只适合于单用户单任务操作系统，是一种最简单的存储管理方式。方法：方法：将内存空间划分为系统区和用户区两部分（见下图）。系统区仅将内存空间划分为系统区和用户区两部分（见下图）。系统区仅供操作系统使用，通常放在内存的低地址部分，系统区以外的全部内存供操作系统使用，通常放在内存的低地址部分，系统区以外的全部内存空间
27、为用户区，提供给用户使用。用户程序由装入程序从用户区的低地空间为用户区，提供给用户使用。用户程序由装入程序从用户区的低地址开始装入且只能装入一个程序运行。用户区装入一个程序后，内存中址开始装入且只能装入一个程序运行。用户区装入一个程序后，内存中剩余的区域则无法再利用。剩余的区域则无法再利用。4.3 分区式存储管理 单一连续分区存储管理单一连续分区存储管理2.2.分配与回收分配与回收 分配过程是先将待装入内存的程序与用户区进行大分配过程是先将待装入内存的程序与用户区进行大小比较，若程序所需内存空间没有超过用户区的大小，小比较，若程序所需内存空间没有超过用户区的大小，则为它分配内存空间；否则内存分
28、配失败。回收操作则则为它分配内存空间；否则内存分配失败。回收操作则是在用户区的程序运行结束后，将该区域标志置为未分是在用户区的程序运行结束后，将该区域标志置为未分配即可。配即可。单一连续分区存储管理单一连续分区存储管理3.3.地址转换与存储保护地址转换与存储保护（1 1）采用静态重定位方式）采用静态重定位方式 单一连续分区存储管理的地址转换多采用静态重定位，即用户程单一连续分区存储管理的地址转换多采用静态重定位，即用户程序在装入内存时采用静态重定位一次性对所有数据和指令中的逻辑地序在装入内存时采用静态重定位一次性对所有数据和指令中的逻辑地址进行转换。程序执行期间，不允许指令和数据再改变地址，也
29、不允址进行转换。程序执行期间，不允许指令和数据再改变地址，也不允许程序在内存中移动位置。许程序在内存中移动位置。单一连续分区存储管理单一连续分区存储管理（2 2）采用动态重定位方式）采用动态重定位方式 设置一个重定位寄存器并用它来指明内存中系统区和用户区的设置一个重定位寄存器并用它来指明内存中系统区和用户区的地址界限，同时又作为用户区的基地址。用户程序由装入程序装入地址界限，同时又作为用户区的基地址。用户程序由装入程序装入到从界限地址开始的内存区域，但这时并不进行地址转换。地址转到从界限地址开始的内存区域，但这时并不进行地址转换。地址转换要推迟到程序执行过程中执行到某指令中或某个数据的逻辑地址
30、换要推迟到程序执行过程中执行到某指令中或某个数据的逻辑地址时，这时就动态地将这个逻辑地址与重定位寄存器中的值相加得到时，这时就动态地将这个逻辑地址与重定位寄存器中的值相加得到要访问的物理地址。要访问的物理地址。单一连续分区存储管理单一连续分区存储管理4.4.单一连续分区管理的优缺点单一连续分区管理的优缺点优点：优点：管理简单，开销小；管理简单，开销小；安全性高，除了系统区外，用户区中只有一个程序，不存在多个程安全性高，除了系统区外，用户区中只有一个程序，不存在多个程序相互影响的问题；序相互影响的问题；采用静态重定位方式时不需要硬件支持。采用静态重定位方式时不需要硬件支持。缺点：缺点：不支持多用
31、户；不支持多用户；程序的地址空间受用户区空间大小的限制，这是因为程序在运行前程序的地址空间受用户区空间大小的限制，这是因为程序在运行前必须一次性装入内存的连续区域，若程序的地址空间比用户区大则无法必须一次性装入内存的连续区域，若程序的地址空间比用户区大则无法装入；装入；由于一个程序独占系统资源，这样会造成系统资源的严重浪费。由于一个程序独占系统资源，这样会造成系统资源的严重浪费。1.1.实现原理实现原理 将内存系统区之外的用户空间划将内存系统区之外的用户空间划分成若干个固定大小的区域，每个区分成若干个固定大小的区域，每个区域称为一个分区并可装入一个用户程域称为一个分区并可装入一个用户程序运行。
32、分区一旦划分完成，就在系序运行。分区一旦划分完成，就在系统的整个运行期间保持不变。统的整个运行期间保持不变。每个分区允许装入一道程序运行，每个分区允许装入一道程序运行，则系统允许在内存中同时装入多道程则系统允许在内存中同时装入多道程序并发执行。序并发执行。4.3 分区式存储管理 2.2.分区划分分区划分 在固定分区存储管理方式中，分区的数目和每个分区的大小由系在固定分区存储管理方式中，分区的数目和每个分区的大小由系统操作员或操作系统决定。统操作员或操作系统决定。分区划分方式：分区划分方式：（1 1）分区大小相等。优点：管理简单，缺点：缺乏灵活性。）分区大小相等。优点：管理简单，缺点：缺乏灵活性
33、。例如，若程序过小则会造成内存空间浪费，若程序过大则因其无法装例如，若程序过小则会造成内存空间浪费，若程序过大则因其无法装入分区而导致不能运行。入分区而导致不能运行。（2 2）分区大小不等。适量的中分区和较少的大分区。装入程序可以）分区大小不等。适量的中分区和较少的大分区。装入程序可以根据用户程序的大小将它装入到适当的分区。根据用户程序的大小将它装入到适当的分区。固定分区存储管理固定分区存储管理 固定分区存储管理固定分区存储管理3.3.内存空间的分配与回收内存空间的分配与回收（1 1）数据结构：为了有效管理内存中各分区的分配与使用，系统建立了一张）数据结构：为了有效管理内存中各分区的分配与使用
34、，系统建立了一张内存分区分配表，用来记录内存中所划分的分区以及各分区的使用情况。内存分区分配表，用来记录内存中所划分的分区以及各分区的使用情况。分区分配表的内容包括分区号、起始地址、大小和状态；状态栏的值为分区分配表的内容包括分区号、起始地址、大小和状态；状态栏的值为0 0时表示该分区空闲可以装入程序。时表示该分区空闲可以装入程序。固定分区存储管理固定分区存储管理（2 2）内存空间分配）内存空间分配 系统启动后在为程序分配分区之前，根据内存分区的划分在分区系统启动后在为程序分配分区之前，根据内存分区的划分在分区分配表中填入每个分区的起始地址和大小，并且将所有的状态栏均分配表中填入每个分区的起始
35、地址和大小，并且将所有的状态栏均填入填入0 0表示这些分区可用。表示这些分区可用。固定分区存储管理固定分区存储管理 固定分区存储管理固定分区存储管理（3 3）内存空间回收）内存空间回收 当程序运行结束时，根据程序名检索分区分配表，从状态当程序运行结束时，根据程序名检索分区分配表，从状态栏信息可找到该程序所使用的分区，然后将该分区状态栏置为栏信息可找到该程序所使用的分区，然后将该分区状态栏置为0 0，表示该分区已经空闲可以装入新的程序。，表示该分区已经空闲可以装入新的程序。固定分区存储管理固定分区存储管理4.4.地址转换与存储保护地址转换与存储保护固定分区存储管理的地址转换可以采用静态重定位方式
36、：固定分区存储管理的地址转换可以采用静态重定位方式：物理地址逻辑地址分区起始地址物理地址逻辑地址分区起始地址 固定分区存储管理固定分区存储管理存储保护存储保护 方法是在程序运行过程中，每当方法是在程序运行过程中，每当CPUCPU获得物理地址时首获得物理地址时首先与上、下界寄存器的值进行比较，若超出上、下界寄存先与上、下界寄存器的值进行比较，若超出上、下界寄存器的值就发出地址越界中断信号，并由相应的中断处理程器的值就发出地址越界中断信号，并由相应的中断处理程序处理。序处理。固定分区存储管理固定分区存储管理5.5.固定分区分配的优缺点固定分区分配的优缺点优点：优点：通过分区分配表来实现内存分配与回
37、收，而且程序执通过分区分配表来实现内存分配与回收，而且程序执行时采用静态重定位这种方式简单易行，行时采用静态重定位这种方式简单易行，CPUCPU利用率较高。利用率较高。缺点：缺点：程序大小受分区大小的限制，当分区较大而程序较小程序大小受分区大小的限制，当分区较大而程序较小时容易形成内部碎片（一个分区内部浪费的空间称为内部碎片）时容易形成内部碎片（一个分区内部浪费的空间称为内部碎片）而造成内存空间的浪费；而造成内存空间的浪费；由于固定分区分配方式使分区总数固定，这就限制了并发执由于固定分区分配方式使分区总数固定，这就限制了并发执行程序的数量。行程序的数量。1.1.实现原理实现原理在程序装入内存之
38、前并不建立分区，内存分区是在程序运行时根在程序装入内存之前并不建立分区，内存分区是在程序运行时根据程序对内存空间的需要而动态建立的。据程序对内存空间的需要而动态建立的。分区的划分时间、大小及其位置都是动态的。分区的划分时间、大小及其位置都是动态的。2.2.数据结构数据结构包括：包括：已分配分区表、空闲分区表及空闲分区链。已分配分区表、空闲分区表及空闲分区链。已分配分区表已分配分区表用于登记内存空间中已经分配的分区，每个表项记用于登记内存空间中已经分配的分区，每个表项记录一个已分配分区，其内容包括分区号、起始地址、大小和状态。录一个已分配分区，其内容包括分区号、起始地址、大小和状态。空闲分区表空
39、闲分区表则记录内存中所有空闲的分区，每个表项记录一个空则记录内存中所有空闲的分区，每个表项记录一个空闲分区，其内容包括分区号、起始地址、大小和状态。闲分区，其内容包括分区号、起始地址、大小和状态。空闲分区链空闲分区链以系统当前的空闲分区为结点，利用链指针将所有空以系统当前的空闲分区为结点，利用链指针将所有空闲分区结点链接成一个双向循环队列。闲分区结点链接成一个双向循环队列。4.3 分区式存储管理 可变分区存储管理可变分区存储管理已分配分区表已分配分区表空闲分区表空闲分区表分区号分区号起始地址起始地址（KB）大小（大小（KB）状态状态分区号分区号起始地址起始地址（KB）大小（大小（KB）状态状态
40、15020P117020029015P221051550326040P333001000内存及空闲分区链示意内存及空闲分区链示意 固定分区存储管理固定分区存储管理3.3.分配算法分配算法（1 1）首次适应算法）首次适应算法要求要求空闲分区按内存地址递增的次序排列空闲分区按内存地址递增的次序排列在空闲分区链上，每当一个程在空闲分区链上，每当一个程序申请装入内存时，管理程序在空闲分区链上按内存地址递增的顺序从链序申请装入内存时，管理程序在空闲分区链上按内存地址递增的顺序从链首开始查找空闲分区，直到找到一个最先满足此程序要求的空闲分区，并首开始查找空闲分区，直到找到一个最先满足此程序要求的空闲分区，
41、并按此程序的大小从该空闲分区中划出一块连续的内存区域给其使用。按此程序的大小从该空闲分区中划出一块连续的内存区域给其使用。特点：特点：每次都从内存的低地址部分开始查找满足要求的空闲分区。每次都从内存的低地址部分开始查找满足要求的空闲分区。固定分区存储管理固定分区存储管理（2 2）最佳适应算法）最佳适应算法要求要求空闲分区按分区大小递增的次序排列空闲分区按分区大小递增的次序排列在空闲分区链上，当为用户在空闲分区链上，当为用户程序分配内存空闲分区时，则从空闲分区链链首的最小空闲分区开始查找，程序分配内存空闲分区时，则从空闲分区链链首的最小空闲分区开始查找，找到的第一个大小满足程序要求的空闲分区就是
42、最佳空闲分区；该分区能找到的第一个大小满足程序要求的空闲分区就是最佳空闲分区；该分区能满足程序的内存要求，并且在分配后剩余的空闲空间最小。满足程序的内存要求，并且在分配后剩余的空闲空间最小。优点：优点：保留了内存中的大空闲区，当大程序到来时有足够大的空闲区保留了内存中的大空闲区，当大程序到来时有足够大的空闲区可以为其分配。可以为其分配。固定分区存储管理固定分区存储管理（3 3）最差适应算法）最差适应算法要求要求空闲分区按分区大小递减的次序排列空闲分区按分区大小递减的次序排列在空闲分区链上，每一次在空闲分区链上，每一次总是把空闲分区链链首的最大的空闲分区分配给请求的用户程序；若总是把空闲分区链链
43、首的最大的空闲分区分配给请求的用户程序；若该空闲分区小于程序要求的大小则分配失败；若能够满足程序的要求，该空闲分区小于程序要求的大小则分配失败；若能够满足程序的要求，则按程序要求的大小从该空闲分区中划出一块连续区域分配给它。则按程序要求的大小从该空闲分区中划出一块连续区域分配给它。优点：优点：有利于后期再分配。有利于后期再分配。固定分区存储管理固定分区存储管理例例4.1 4.1 有一程序序列：程序有一程序序列：程序A A要求要求18KB18KB，程序，程序B B要求要求25KB25KB，程序，程序C C要求要求30KB30KB，初始内存分配情况如图所示（其中阴影为分配区）。问首次适应，初始内存
44、分配情况如图所示（其中阴影为分配区）。问首次适应算法、最佳适应算法和最差适应算法中哪种能满足该程序序列的分配？算法、最佳适应算法和最差适应算法中哪种能满足该程序序列的分配？固定分区存储管理固定分区存储管理【解答解答】结合系统中初始内存的结合系统中初始内存的分配情况，建立的首次适应算法、分配情况，建立的首次适应算法、最佳适应算法和最差适应算法的最佳适应算法和最差适应算法的空闲区链分别如图：空闲区链分别如图：对于首次适应算法，程序对于首次适应算法，程序A A分配分配30KB30KB的空闲分区，程序的空闲分区，程序B B分配分配46KB46KB的的空闲分区，此后就无法为程序空闲分区，此后就无法为程序
45、C C分配分配合适的空闲分区了。合适的空闲分区了。对于最佳适应算法，程序对于最佳适应算法，程序A A分配分配20KB20KB的空闲分区，程序的空闲分区，程序B B分配分配30KB30KB的空闲分区，程序的空闲分区，程序C C分配分配46KB46KB的空闲分区。的空闲分区。对于最差适应算法，程序对于最差适应算法，程序A A分配分配46KB46KB的空闲分区，程序的空闲分区，程序B B分配分配30KB30KB的空闲分区，的空闲分区，此后就无法为程序此后就无法为程序C C分配合适的空闲分区了。分配合适的空闲分区了。因此，本题最佳适应算法对这个程序序列的内存分配是合适的。因此，本题最佳适应算法对这个程
46、序序列的内存分配是合适的。固定分区存储管理固定分区存储管理4.4.分配与回收分配与回收 系统进行内存分配时采用相应的分配算法来查找系统中是否存在系统进行内存分配时采用相应的分配算法来查找系统中是否存在满足要求的空闲分区；若找到就为程序分配相应的内存空间，并修满足要求的空闲分区；若找到就为程序分配相应的内存空间，并修改相关的数据结构，否则此次分配失败。改相关的数据结构，否则此次分配失败。内存的回收指在程序运行结束后，系统要把该程序释放的内存空内存的回收指在程序运行结束后，系统要把该程序释放的内存空间及时收回以便重新分配给需要的程序。间及时收回以便重新分配给需要的程序。固定分区存储管理固定分区存储
47、管理回收的内存区与内存中的空闲分区在位置上存在回收的内存区与内存中的空闲分区在位置上存在4 4种关系：种关系：（1 1）回收的内存区与上、下两个空闲分区相邻）回收的内存区与上、下两个空闲分区相邻 （2 2）回收的内存区只与上空闲区相邻）回收的内存区只与上空闲区相邻 （3 3）回收的内存区只与下空闲分区相邻）回收的内存区只与下空闲分区相邻 （4 4）回收的内存区上、下都不与空闲分区相邻）回收的内存区上、下都不与空闲分区相邻 固定分区存储管理固定分区存储管理5.5.地址转换与存储保护地址转换与存储保护（1 1）地址转换）地址转换 步骤如下：步骤如下：当程序占用当程序占用CPUCPU时，进程调度程序
48、就把该程序所占分区的起始地时，进程调度程序就把该程序所占分区的起始地址送入基址寄存器，把程序所占分区的大小送入限长寄存器。址送入基址寄存器，把程序所占分区的大小送入限长寄存器。程序执行过程中，每当程序执行过程中，每当CPUCPU执行到涉及地址的指令时都要由地址执行到涉及地址的指令时都要由地址转换机构把程序中的逻辑地址转换成物理地址。转换机构把程序中的逻辑地址转换成物理地址。固定分区存储管理固定分区存储管理（2 2）存储保护）存储保护 基址寄存器和限长寄存器分别记录当前运行程序在内存中所占基址寄存器和限长寄存器分别记录当前运行程序在内存中所占分区的起始地址和结束地址。当分区的起始地址和结束地址。
49、当CPUCPU执行到程序中涉及地址的指令执行到程序中涉及地址的指令时，必须核对转换后的物理地址是否满足条件时，必须核对转换后的物理地址是否满足条件“起始地址起始地址物理地物理地址址结束地址结束地址”，若满足则执行该指令，否则产生地址越界错误停，若满足则执行该指令，否则产生地址越界错误停止该程序的执行。止该程序的执行。固定分区存储管理固定分区存储管理6.6.碎片问题碎片问题 在采用可变分区存储管理方式下，随着分配与回收的不断进行，在采用可变分区存储管理方式下，随着分配与回收的不断进行，内存中会出现很多离散分布且容量很小的空闲小分区，虽然这些空内存中会出现很多离散分布且容量很小的空闲小分区，虽然这
50、些空闲小分区的总容量能够满足程序对内存的要求，但由于一个程序需闲小分区的总容量能够满足程序对内存的要求，但由于一个程序需要装入到一个连续的内存分区，而这些空闲小分区单个又不能满足要装入到一个连续的内存分区，而这些空闲小分区单个又不能满足程序对内存大小的需求，于是这些小的空闲分区就成为内存中无法程序对内存大小的需求，于是这些小的空闲分区就成为内存中无法再利用的资源，称为内存碎片或零头。再利用的资源，称为内存碎片或零头。在可变分区分配中，系统解决外部碎片的思路是通过某种方法，在可变分区分配中，系统解决外部碎片的思路是通过某种方法，将内存中无法利用的小空闲分区合并在一起组成一个较大的空闲分将内存中无
