第三章 存 储 器 管 理 第三章第三章 存储管理存储管理1第三章 存 储 器 管 理 第三章第三章 存储管理存储管理 3.13.1 存储器管理概述存储器管理概述3.2 3.2 连续分配方式连续分配方式 3.3 3.3 基本分页存储管理方式基本分页存储管理方式 3.4 3.4 基本分段存储管理方式基本分段存储管理方式 3.5 3.5 虚拟存储器的基本概念虚拟存储器的基本概念 3.6 3.6 请求分页存储管理方式请求分页存储管理方式 3.7 3.7 页面置换算法页面置换算法 3.8 3.8 请求分段存储管理方式请求分段存储管理方式 2第三章 存 储 器 管 理 3.1 存储器管理概述存储器管理概述 3.1.1 存储器管理的主要任务存储器管理的主要任务 3.1.2 存储器管理的主要功能存储器管理的主要功能 3.1.3 程序的装入与链接程序的装入与链接 3.1.4 存储管理方式存储管理方式 3第三章 存 储 器 管 理 图图3.1 存储层次结构存储层次结构协调使用这些存储器正是协调使用这些存储器正是OS提要做的工作之一提要做的工作之一4第三章 存 储 器 管 理 3.1.1 存储器管理的主要任务存储器管理的主要任务 1.尽可能方便用户尽可能方便用户2.提高主存储器的使用效率提高主存储器的使用效率3.使主存储器在成本、速度和规模之间获使主存储器在成本、速度和规模之间获得较好的权衡。得较好的权衡。 5第三章 存 储 器 管 理 3.1.2 存储器管理的主要功能存储器管理的主要功能 1主存空间的分配和回收主存空间的分配和回收 2地址转换地址转换 3主存空间的共享与保护主存空间的共享与保护 4主存空间的扩充主存空间的扩充 6第三章 存 储 器 管 理 3.1.3 程序的装入与链接程序的装入与链接 1源程序的执行过程源程序的执行过程 2程序的链接程序的链接 3程序的装入程序的装入 7第三章 存 储 器 管 理 1源程序的执行过程源程序的执行过程 l通常要经过编译、链接和装入几个步骤通常要经过编译、链接和装入几个步骤: （1）编编译译。由由编编译译程程序序将将用用户户源源代代码码编编译译成成若若干个目标模块。干个目标模块。（2）链链接接。由由链链接接程程序序将将编编译译后后形形成成的的目目标标模模块块以以及及它它们们所所需需要要的的库库函函数数，链链接接在在一一起起，形成一个装入模块。形成一个装入模块。（3）装装入入。由由装装入入程程序序将将装装入入模模块块装装入入主主存存的的过程。过程。8第三章 存 储 器 管 理 图图3.2 一个可执行目标程序的生命周期一个可执行目标程序的生命周期9第三章 存 储 器 管 理 2程序的链接程序的链接 链接程序的功能是将一组目标模块以及它们所需要链接程序的功能是将一组目标模块以及它们所需要的库函数，装配成一个完整的装入模块。的库函数，装配成一个完整的装入模块。实现链接的方法有三种实现链接的方法有三种静态链接静态链接：事先进行链接，以后不再拆开的链接方式：事先进行链接，以后不再拆开的链接方式 装入时动态链接装入时动态链接：用户源程序经编译后所得到的目标模：用户源程序经编译后所得到的目标模块，是在装入主存时，边装入边链接的。块，是在装入主存时，边装入边链接的。 运行时动态链接运行时动态链接：可将某些目标模块的链接，推迟到执：可将某些目标模块的链接，推迟到执行时才进行。在执行过程中，当发现一个被调用模块尚行时才进行。在执行过程中，当发现一个被调用模块尚未装入内存时，立即由未装入内存时，立即由OS去找到该模块并将之装入内存，去找到该模块并将之装入内存， 把它链接到调用者模块上。把它链接到调用者模块上。 10第三章 存 储 器 管 理 3程序的装入程序的装入程序的装入就是把程序装入内存空间。采用三种方式程序的装入就是把程序装入内存空间。采用三种方式 （1）绝对装入绝对装入方式：方式：根据根据装入装入模块中的地址模块中的地址，将程，将程序和数据装入主存序和数据装入主存(程序地址与主存地址相同）。程序地址与主存地址相同）。（2）可重定位可重定位方式方式 ：根据主存根据主存当前的实际使用情况，当前的实际使用情况，将装入模块装入到主存适当的地方。将装入模块装入到主存适当的地方。11第三章 存 储 器 管 理 2. 可重定位装入方式可重定位装入方式重定位：重定位：在装入时对目标程序中指令和数据地址的修改过程在装入时对目标程序中指令和数据地址的修改过程12第三章 存 储 器 管 理 3程序的装入程序的装入静态重定位：静态重定位：地址变换在装入时一次完成的，以地址变换在装入时一次完成的，以后不再改变。后不再改变。静态重定位装入方式可将程度装入到内存中任何静态重定位装入方式可将程度装入到内存中任何位置，但不允许程序运行时在内存移动位置。然位置，但不允许程序运行时在内存移动位置。然而，实际上在运行过程中它在内存中的位置可能而，实际上在运行过程中它在内存中的位置可能经常要改变。经常要改变。（3）动态运行时装入动态运行时装入方式：在把装入模块装入主存方式：在把装入模块装入主存后，并不立即把装入模块中的相对地址转换为绝后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序要真正对地址，而是把这种地址转换推迟到程序要真正执行时才进行。执行时才进行。13第三章 存 储 器 管 理 3.动态装入动态装入（动态重定位）（动态重定位）过程过程: 1.所有子程序以可重定位格式驻留在盘上所有子程序以可重定位格式驻留在盘上 2.主程序执行前只装入主程序不装入子程序主程序执行前只装入主程序不装入子程序 3.当主程序要调用一个子程序或者一个子程当主程序要调用一个子程序或者一个子程序要调用另一个子程序时。序要调用另一个子程序时。主程序首先检查子程序是否已被装入；主程序首先检查子程序是否已被装入；如未装入如未装入,调用可重定位连接装入程序来装入希调用可重定位连接装入程序来装入希望调用的子程序并更新相应表格；望调用的子程序并更新相应表格；将控制传递给新装入的例程。将控制传递给新装入的例程。14第三章 存 储 器 管 理 动态装入的好处动态装入的好处:(1)节省内存空间，提高内存空间利用率节省内存空间，提高内存空间利用率(2)加快程序的装入过程加快程序的装入过程(3)便于修改和更新便于修改和更新(4)便于实现对目标模块的共享便于实现对目标模块的共享15第三章 存 储 器 管 理 3程序的装入程序的装入相对相对(逻辑逻辑)地址地址:目标目标程序中程序中指令和数据的地址（相指令和数据的地址（相对装入模块的起址，一般为对装入模块的起址，一般为0）绝对绝对(物理物理)地址地址:指令和数据装入指令和数据装入内存后内存后所在的单元所在的单元地址地址(取决于程序将在内存中的起址取决于程序将在内存中的起址)。重定位：重定位：是指对目标程序中指令和数据地址的修改过是指对目标程序中指令和数据地址的修改过程程(将逻辑地址转换为物理地址将逻辑地址转换为物理地址) 。静态重定位静态重定位:当当程序装入内存时程序装入内存时一次性完成对指令地一次性完成对指令地址的转换。址的转换。动态重定位：动态重定位：地址转换过程地址转换过程在指令执行时才进行。在指令执行时才进行。16第三章 存 储 器 管 理 3.1.4 存储管理方式存储管理方式单用户连续存储管理方式单用户连续存储管理方式 固定分区存储管理方式固定分区存储管理方式 可变分区存储管理方式可变分区存储管理方式 页式存储管理方式页式存储管理方式 段式存储管理方式段式存储管理方式 段页式存储管理方式段页式存储管理方式 虚拟存储管理方式虚拟存储管理方式17第三章 存 储 器 管 理 3.2 连续分配方式连续分配方式3.2.1 单一连续分配单一连续分配采用这种存储管理方式时，可把内存分为系统区和采用这种存储管理方式时，可把内存分为系统区和用户区两部分，系统区仅提供给用户区两部分，系统区仅提供给OS使用。使用。 主存中仅驻留一道程序，整个用户区为一用户独占。主存中仅驻留一道程序，整个用户区为一用户独占。当用户作业空间大于用户区时该作业不能装入当用户作业空间大于用户区时该作业不能装入.这是最简单的一种存储管理方式，但只能用于单用这是最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中。户、单任务的操作系统中。18第三章 存 储 器 管 理 3.2 连续分配方式连续分配方式3.2.2 固定分区分配固定分区分配固定分区式分配是将内存用户空间划分为固定分区式分配是将内存用户空间划分为若干个固定大小的区域，在每个分区中只若干个固定大小的区域，在每个分区中只装入一道作业。装入一道作业。它是一种最简单的可运行多道程序的存储它是一种最简单的可运行多道程序的存储管理方式。管理方式。19第三章 存 储 器 管 理 3.2 连续分配方式连续分配方式3.2.2 固定分区分配固定分区分配1. 划分分区的方法划分分区的方法 (1)分区大小相等，分区大小相等， 即使所有的内存分区大即使所有的内存分区大小相等。小相等。 (2) 分区大小不等。分区大小不等。 20第三章 存 储 器 管 理 2. 内存分配内存分配 固定分区使用表固定分区使用表 优点：易于实现，开销小。优点：易于实现，开销小。缺点：内缺点：内碎片碎片造成浪费；造成浪费； 分区总数固定，限制了并发执行的程序数目。分区总数固定，限制了并发执行的程序数目。21第三章 存 储 器 管 理 3.2.3 动态分区分配动态分区分配是根据进程的实际需要，动态分区分配是根据进程的实际需要，动态为之分配内存空间。动态为之分配内存空间。分区分配中的数据结构分区分配中的数据结构 为实现动态分区分配，系统中必须配置相应为实现动态分区分配，系统中必须配置相应的数据结构，用来描述空闲分区和已分配分的数据结构，用来描述空闲分区和已分配分区的情况。通常采用以下两种形式：区的情况。通常采用以下两种形式：22第三章 存 储 器 管 理 (1)空闲分区表。空闲分区表。 (2) 空闲分区链。空闲分区链。 图 3-5 空闲链结构 23第三章 存 储 器 管 理 2. 分区分配算法分区分配算法(1)首次适应算法首次适应算法FF空闲区链：空闲区链：首址递增首址递增排列；排列；申请：申请：按分区的先后次序，从头查找，找到符合按分区的先后次序，从头查找，找到符合 要求的第一个分区。要求的第一个分区。优点：尽量使用低地址空间，优点：尽量使用低地址空间， 高地址空间保持大的空闲区域。高地址空间保持大的空闲区域。缺点：随着低地址分区不断划分而产生较多小分区（内缺点：随着低地址分区不断划分而产生较多小分区（内存碎片），每次分配时查找时间开销会增大。存碎片），每次分配时查找时间开销会增大。24第三章 存 储 器 管 理 2. 分区分配算法分区分配算法(2) 循环首次适应算法循环首次适应算法空闲区链：空闲区链：首址递增首址递增排列；排列；申请：从申请：从上次分配的分区起查找上次分配的分区起查找（到最后分区时（到最后分区时再回到开头），再回到开头），找到符合要求的第一个分区找到符合要求的第一个分区，应设置一个查询指针。应设置一个查询指针。特点：空闲分区分布均匀；特点：空闲分区分布均匀； 大的空闲分区不易保留；大的空闲分区不易保留； 查找时间开销会减小。查找时间开销会减小。25第三章 存 储 器 管 理 2. 分区分配算法分区分配算法(3) 最佳适应算法最佳适应算法空闲区链：分区空闲区链：分区容量递增容量递增排列；排列；申请：申请：找到符合要求的第一个分区找到符合要求的第一个分区。特点：碎片较小，但从整体来看，会形成较多的特点：碎片较小，但从整体来看，会形成较多的碎片。碎片。26第三章 存 储 器 管 理 2. 分区分配算法分区分配算法(4) 最坏适应算法最坏适应算法空闲区链：分区空闲区链：分区容量递减容量递减排列；排列；申请：找到符合要求的第一个分区。申请：找到符合要求的第一个分区。特点：大的空闲分区不易保留。特点：大的空闲分区不易保留。27第三章 存 储 器 管 理 三种分配算法的比较三种分配算法的比较从搜索速度和回收过程上看：从搜索速度和回收过程上看：最先适应算法最先适应算法具有最佳性能；具有最佳性能；从空间利用上看：从空间利用上看：最先适应算法最先适应算法比比最最佳佳适应算法适应算法好，好，最最佳佳适适应算法应算法比比最坏适应算法最坏适应算法要好；要好；最最佳佳适应算法适应算法找到的空闲区是找到的空闲区是最佳的，但在某些情况下，不一定能提高主存的利用率。最佳的，但在某些情况下，不一定能提高主存的利用率。最先适应算法最先适应算法的另一个优点是尽可能地利用了低地址空间，的另一个优点是尽可能地利用了低地址空间，从而保证高地址有较大的空闲区来放置较大的作业。从而保证高地址有较大的空闲区来放置较大的作业。最坏适应算法最坏适应算法由于过多的分割大的空闲区，当遇到较大作业由于过多的分割大的空闲区，当遇到较大作业申请时，无法满足其申请的可能性较大，该算法对中、小作申请时，无法满足其申请的可能性较大，该算法对中、小作业比较有利。业比较有利。因此，在实际系统中最先适应算法法用得最多因此，在实际系统中最先适应算法法用得最多. 28第三章 存 储 器 管 理 3. 分区分配操作分区分配操作 1) 分配内存分配内存 内内存存分分配配流流程程29第三章 存 储 器 管 理 2) 回收内存回收内存 图 3-7 内存回收时的情况 当进程运行完毕释放内存时，系统根据回收区的首址，当进程运行完毕释放内存时，系统根据回收区的首址，从空闲表中找到相应的插入点。从空闲表中找到相应的插入点。30第三章 存 储 器 管 理 3.2.4 可重定位分区分配可重定位分区分配 1. 动态重定位的引入动态重定位的引入 图 3-8 紧凑的示意 32第三章 存 储 器 管 理 2重定位（地址转换）重定位（地址转换） 采采用用动动态态重重定定位位方方式式装装入入作作业业。它它需需要要设设置置硬硬件件地地址址转转换换机构：基址寄存器和限长寄存器。地址转换步骤如下：机构：基址寄存器和限长寄存器。地址转换步骤如下： 当当作作业业占占用用处处理理器器时时，进进程程调调度度把把该该作作业业的的起起始始地地址址送入送入基址寄存器基址寄存器，把作业的，把作业的最大地址最大地址送入送入限长寄存器限长寄存器。 处处理理器器每每执执行行一一条条指指令令，都都要要由由硬硬件件的的地地址址转转换换机机构构把把逻辑地址转换成物理地址逻辑地址转换成物理地址。 当当取取出出一一条条指指令令后后，把把该该指指令令中中的的逻逻辑辑地地址址与与基基址址寄寄存存器器内内容容相相加加得得到到物物理理地地址址，该该物物理理地地址址必必须须满满足足：物物理地址理地址=限长寄存器的值限长寄存器的值 基址寄存器和限长寄存器总是存放当前占用处理器的作业基址寄存器和限长寄存器总是存放当前占用处理器的作业所占分区的始址和末址。所占分区的始址和末址。33第三章 存 储 器 管 理 所有连续模式地址映射过程所有连续模式地址映射过程/保护保护34第三章 存 储 器 管 理 2. 动态重定位的实现动态重定位的实现 图 3-9 动态重定位示意图 35第三章 存 储 器 管 理 4 . 管理特点管理特点 1.分分区区的的长长度度不不是是预预先先固固定定的的，而而是是按按作作业业的的实实际际需需求求来来划划分分的的。分分区区的的个个数数也也不不是是预预先先确定的，而是由装入的作业数决定的。确定的，而是由装入的作业数决定的。2.分分区区的的大大小小由由作作业业的的大大小小来来定定，提提高高了了主主存存的使用效率。的使用效率。3.在在主主存存分分配配过过程程中中，会会产产生生许许多多主主存存“碎碎片片”。主主存存“碎碎片片”是是指指小小的的无无法法使使用用的的主主存存空间。使主存空间仍有一定的浪费。空间。使主存空间仍有一定的浪费。36第三章 存 储 器 管 理 3.2.4 采用技术采用技术 为了提高主存空间的利用率，可以采用为了提高主存空间的利用率，可以采用移动技术移动技术和和对换技术对换技术，来合并空闲区，来合并空闲区，满足作业的要求；或把暂时不运行的作满足作业的要求；或把暂时不运行的作业从主存中对换到外存上，运行紧迫的业从主存中对换到外存上，运行紧迫的作业，然后再把对换到外存上的作业调作业，然后再把对换到外存上的作业调入主存。入主存。 1移动技术移动技术 2对换技术对换技术 37第三章 存 储 器 管 理 1移动移动(紧缩紧缩)技术技术 将主存中的所有作业进行移动，使它们相邻接。这样，将主存中的所有作业进行移动，使它们相邻接。这样，原来分散的多个小分区便拼接成一个大分区，从而就原来分散的多个小分区便拼接成一个大分区，从而就可以把作业装入该区。可以把作业装入该区。这种通过移动，把多个分散的小分区拼接成大分区的这种通过移动，把多个分散的小分区拼接成大分区的方法被称为方法被称为“拼接拼接”或或“紧凑紧凑”，改变作业在主存中，改变作业在主存中位置的工作称为位置的工作称为“移动移动”。移动会增加系统开销（操作系统所占有的系统资源和移动会增加系统开销（操作系统所占有的系统资源和所需要的处理器的时间称为所需要的处理器的时间称为“系统开销系统开销”）。）。移动是有条件的：当作业不与外围设备交换信息时，移动是有条件的：当作业不与外围设备交换信息时，可以移动，否则不能移动。可以移动，否则不能移动。 38第三章 存 储 器 管 理 2. 对换对换1） 对换的引入对换的引入所谓所谓“对换对换”， 是指把内存中暂时不能是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存。对换所需要的程序和数据，调入内存。对换是提高内存利用率的有效措施。是提高内存利用率的有效措施。 39第三章 存 储 器 管 理 2. 对换对换交换的基本单位为交换的基本单位为整个进程的地址空间整个进程的地址空间。覆盖的基本单位为一个程序的几个代码覆盖的基本单位为一个程序的几个代码段或数据段。段或数据段。 优点：增加并发运行的程序数目，优点：增加并发运行的程序数目，并且给用户提供适当的响应时间；编写并且给用户提供适当的响应时间；编写程序时不影响程序结构。程序时不影响程序结构。 缺点：对换入和换出的控制增加处缺点：对换入和换出的控制增加处理机开销；理机开销；40第三章 存 储 器 管 理 2. 对换2） 对换空间的管理对换空间的管理把外存分为把外存分为文件区文件区和和对换区对换区。对换区用来。对换区用来存放从内存换出的进程。主要目标是提高存放从内存换出的进程。主要目标是提高进程换入和换出的速度。进程换入和换出的速度。为了能对对换区中的空闲盘块进行管理，为了能对对换区中的空闲盘块进行管理，在系统中应配置相应的数据结构，以记录在系统中应配置相应的数据结构，以记录外存的使用情况。其形式可以用空闲分区外存的使用情况。其形式可以用空闲分区表或空闲分区链。表或空闲分区链。41第三章 存 储 器 管 理 2. 对换对换3） 进程的换出与换入进程的换出与换入(1) 进程的换出。进程的换出。 l当创建子进程而需要更多的内存空间，但又无当创建子进程而需要更多的内存空间，但又无足够的内存空间时，系统应将某进程换出。足够的内存空间时，系统应将某进程换出。(2) 进程的换入。进程的换入。 l系统应定时地查看所有进程的状态，从中找出系统应定时地查看所有进程的状态，从中找出“就绪就绪”状态但已换出的进程，将其中换出时状态但已换出的进程，将其中换出时间最久的进程作为换入进程，将之换入。间最久的进程作为换入进程，将之换入。42第三章 存 储 器 管 理 小结基本概念：基本概念：相对相对(逻辑逻辑)地址、绝对地址、绝对(物理物理)地址、重定位地址、重定位 、静态重定位、动态重定位、静态重定位、动态重定位、移动（紧缩）、对换技术。移动（紧缩）、对换技术。连续分配方式：程序与数据占据连续的存连续分配方式：程序与数据占据连续的存储单元。储单元。分配算法：最先适应、循环适应、最佳适分配算法：最先适应、循环适应、最佳适应、最坏适应及其优缺点。应、最坏适应及其优缺点。43第三章 存 储 器 管 理 作业作业重定位、动态重定位重定位、动态重定位最先适应、最佳适应、最坏适应算法及最先适应、最佳适应、最坏适应算法及其优缺点。其优缺点。44