计算机操作系统第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 页面置换算法页面置换算法 4.8 4.8 请求分段存储管理方式请求分段存储管理方式 第四章 存 储 器 管 理 4.1 程序的装入和链接程序的装入和链接 图4-1对用户程序的处理步骤第四章 存 储 器 管 理 4.1.1 程序的装入程序的装入1.绝对装入方式绝对装入方式(Absolute Loading Mode)程序中所使用的绝对地址，既可在编译或汇编时给出，也可由程序员直接赋予。但在由程序员直接给出绝对地址时，不仅要求程序员熟悉内存的使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。因此，通常是宁可在程序中采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址。第四章 存 储 器 管 理 2.可重定位装入方式可重定位装入方式(Relocation Loading Mode)图4-2作业装入内存时的情况第四章 存 储 器 管 理 3.动态运行时装入方式动态运行时装入方式(Denamle Run-time Loading)动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是相对地址。第四章 存 储 器 管 理 4.1.2 程序的链接程序的链接 1.静态链接方式静态链接方式(Static Linking)图4-3程序链接示意图第四章 存 储 器 管 理 在将这几个目标模块装配成一个装入模块时，须解决以下两个问题：(1)对相对地址进行修改。(2)变换外部调用符号。第四章 存 储 器 管 理 2.装入时动态链接装入时动态链接(Loadtime Dynamic Linking)装入时动态链接方式有以下优点：(1)便于修改和更新。(2)(2)便于实现对目标模块的共享。第四章 存 储 器 管 理 3.运行时动态链接运行时动态链接(Run-time Dynamic Linking)近几年流行起来的运行时动态链接方式，是对上述在装入时链接方式的一种改进。这种链接方式是将对某些模块的链接推迟到执行时才执行，亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。第四章 存 储 器 管 理 4.2 连续分配方式连续分配方式4.2.1 单一连续分配单一连续分配 这是最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中。采用这种存储管理方式时，可把内存分为系统区和用户区两部分，系统区仅提供给OS使用，通常是放在内存的低址部分；用户区是指除系统区以外的全部内存空间，提供给用户使用。第四章 存 储 器 管 理 4.2.2 固定分区分配固定分区分配 1.划分分区的方法划分分区的方法(1)分区大小相等，即使所有的内存分区大小相等。(2)(2)分区大小不等。第四章 存 储 器 管 理 2.内存分配内存分配 图4-4固定分区使用表第四章 存 储 器 管 理 4.2.3 动态分区分配动态分区分配 1.分区分配中的数据结构分区分配中的数据结构(1)空闲分区表。(2)(3)(2)空闲分区链。图4-5空闲链结构第四章 存 储 器 管 理 2.分区分配算法分区分配算法(1)首次适应算法FF。(2)(2)循环首次适应算法，该算法是由首次适应算法演变而成的。(3)(3)最佳适应算法。第四章 存 储 器 管 理 3.分区分配操作分区分配操作 1)分配内存图4-6内存分配流程第四章 存 储 器 管 理 2)回收内存图4-7内存回收时的情况第四章 存 储 器 管 理 4.2.4 可重定位分区分配可重定位分区分配 1.动态重定位的引入动态重定位的引入 图4-8紧凑的示意第四章 存 储 器 管 理 2.动态重定位的实现动态重定位的实现 图4-9动态重定位示意图第四章 存 储 器 管 理 3.动态重定位分区分配算法动态重定位分区分配算法 图4-10动态分区分配算法流程图第四章 存 储 器 管 理 4.2.5 对换对换(Swapping)1.对换的引入对换的引入 所谓“对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存。对换是提高内存利用率的有效措施。第四章 存 储 器 管 理 2.对换空间的管理对换空间的管理为了能对对换区中的空闲盘块进行管理，在系统中应配置相应的数据结构，以记录外存的使用情况。其形式与内存在动态分区分配方式中所用数据结构相似，即同样可以用空闲分区表或空闲分区链。在空闲分区表中的每个表目中应包含两项，即对换区的首址及其大小，它们的单位是盘块号和盘块数。第四章 存 储 器 管 理 3.进程的换出与换入进程的换出与换入(1)进程的换出。每当一进程由于创建子进程而需要更多的内存空间，但又无足够的内存空间等情况发生时，系统应将某进程换出。其过程是：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动盘块，将该进程的程序和数据传送到磁盘的对换区上。若传送过程未出现错误，便可回收该进程所占用的内存空间，并对该进程的进程控制块做相应的修改。第四章 存 储 器 管 理(2)进程的换入。系统应定时地查看所有进程的状态，从中找出“就绪”状态但已换出的进程，将其中换出时间(换出到磁盘上)最久的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。第四章 存 储 器 管 理 4.3 基本分页存储管理方式基本分页存储管理方式 4.3.1 页面与页表页面与页表 1.页面页面1)页面和物理块分页存储管理，是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号，从0开始，如第0页、第1页等。相应地，也把内存空间分成与页面相同大小的若干个存储块，称为(物理)块或页框(frame)，也同样为它们加以编号，如0块、1块等等。在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”。第四章 存 储 器 管 理 2)页面大小在分页系统中的页面其大小应适中。页面若太小，一方面虽然可使内存碎片减小，从而减少了内存碎片的总空间，有利于提高内存利用率，但另一方面也会使每个进程占用较多的页面，从而导致进程的页表过长，占用大量内存；此外，还会降低页面换进换出的效率。然而，如果选择的页面较大，虽然可以减少页表的长度，提高页面换进换出的速度，但却又会使页内碎片增大。因此，页面的大小应选择得适中，且页面大小应是2的幂，通常为512B8KB。第四章 存 储 器 管 理 2.地址结构地址结构 分页地址中的地址结构如下：页号P位移量W3112110对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得：第四章 存 储 器 管 理 3.页表页表 图4-11页表的作用第四章 存 储 器 管 理 4.3.2 地址变换机构地址变换机构 1.基本的地址变换机构基本的地址变换机构 图4-12分页系统的地址变换机构第四章 存 储 器 管 理 2.具有快表的地址变换机构具有快表的地址变换机构 图4-13具有快表的地址变换机构第四章 存 储 器 管 理 4.3.3 两级和多级页表两级和多级页表 现代的大多数计算机系统，都支持非常大的逻辑地址空间(232264)。在这样的环境下，页表就变得非常大，要占用相当大的内存空间。例如，对于一个具有32位逻辑地址空间的分页系统，规定页面大小为4KB即212B，则在每个进程页表中的页表项可达1兆个之多。又因为每个页表项占用一个字节，故每个进程仅仅其页表就要占用4KB的内存空间，而且还要求是连续的。可以采用这样两个方法来解决这一问题：采用离散分配方式来解决难以找到一块连续的大内存空间的问题：只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。第四章 存 储 器 管 理 1.两级页表两级页表(Two-Level Page Table)逻辑地址结构可描述如下：第四章 存 储 器 管 理 图4-14两级页表结构第四章 存 储 器 管 理 图4-15具有两级页表的地址变换机构第四章 存 储 器 管 理 2.多级页表多级页表对于32位的机器，采用两级页表结构是合适的；但对于64位的机器，如果页面大小仍采用4KB即212B，那么还剩下52位，假定仍按物理块的大小(212位)来划分页表，则将余下的42位用于外层页号。此时在外层页表中可能有4096G个页表项，要占用16384GB的连续内存空间。必须采用多级页表，将外层页表再进行分页，也是将各分页离散地装入到不相邻接的物理块中，再利用第2级的外层页表来映射它们之间的关系。对于64位的计算机，如果要求它能支持2(=1844744TB)规模的物理存储空间，则即使是采用三级页表结构也是难以办到的；而在当前的实际应用中也无此必要。第四章 存 储 器 管 理 4.4 基本分段存储管理方式基本分段存储管理方式 4.4.1 分段存储管理方式的引入分段存储管理方式的引入 引入分段存储管理方式，主要是为了满足用户和程序员的下述一系列需要：1)方便编程2)信息共享3)信息保护4)动态增长5)动态链接第四章 存 储 器 管 理 4.4.2 分段系统的基本原理分段系统的基本原理 1.分段分段 分段地址中的地址具有如下结构：段号段内地址31161502.段表段表 第四章 存 储 器 管 理 图4-16利用段表实现地址映射第四章 存 储 器 管 理 图4-17分段系统的地址变换过程3.地址变换机构第四章 存 储 器 管 理 4.分页和分段的主要区别分页和分段的主要区别(1)页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率。或者说，分页仅仅是由于系统管理的需要而不是用户的需要。段则是信息的逻辑单位，它含有一组其意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。第四章 存 储 器 管 理(2)页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。(3)分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址；而分段的作业地址空间则是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。第四章 存 储 器 管 理 4.4.3 信息共享信息共享 图4-18分页系统中共享editor的示意图第四章 存 储 器 管 理 图4-19分段系统中共享editor的示意图第四章 存 储 器 管 理 4.4.4 段页式存储管理方式段页式存储管理方式 1.基本原理基本原理 图4-20作业地址空间和地址结构第四章 存 储 器 管 理 图4-21利用段表和页表实现地址映射第四章 存 储 器 管 理 2.地址变换过程地址变换过程 图4-22段页式系统中的地址变换机构第四章 存 储 器 管 理 4.5 虚拟存储器的基本概念虚拟存储器的基本概念 4.5.1 虚拟存储器的引入虚拟存储器的引入 1.常规存储器管理方式的特征常规存储器管理方式的特征(1)一次性。(2)(3)(2)驻留性。第四章 存 储 器 管 理 2.局部性原理局部性原理 早在1968年，Denning.P就曾指出：(1)程序执行时，除了少部分的转移和过程调用指令外，在大多数情况下仍是顺序执行的。(2)过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域，但经研究看出，过程调用的深度在大多数情况下都不超过5。(3)程序中存在许多循环结构，这些虽然只由少数指令构成，但是它们将多次执行。(4)程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往都局限于很小的范围内。第四章 存 储 器 管 理 局限性又表现在下述两个方面：(1)时间局限性。如果程序中的某条指令一旦执行，则不久以后该指令可能再次执行；如果某数据被访问过，则不久以后该数据可能再次被访问。产生时间局限性的典型原因，是由于在程序中存在着大量的循环操作。(2)空间局限性。一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，其典型情况便是程序的顺序执行。第四章 存 储 器 管 理 3.虚拟存储器定义虚拟存储器定义 所谓虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。可见，虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于大、中、小型机器和微型机中。第四章 存 储 器 管 理 4.5.2 虚拟存储器的实现方法虚拟存储器的实现方法 1.分页请求系统分页请求系统(1)硬件支持。请求分页的页表机制，它是在纯分页的页表机制上增加若干项而形成的，作为请求分页的数据结构；缺页中断机构，即每当用户程序要访问的页面尚未调入内存时便产生一缺页中断，以请求OS将所缺的页调入内存；地址变换机构，它同样是在纯分页地址变换机构的基础上发展形成的。(2)实现请求分页的软件。第四章 存 储 器 管 理 4.5.3 虚拟存储器的特征虚拟存储器的特征 1.多次性多次性2.2.对换性对换性3.3.虚拟性虚拟性 第四章 存 储 器 管 理 4.6 请求分页存储管理方式请求分页存储管理方式 4.6.1 请求分页中的硬件支持请求分页中的硬件支持 1.页表机制页表机制 页号物理块号状态位P访问字段A修改位M外存地址第四章 存 储 器 管 理 2.缺页中断机构缺页中断机构 图4-23涉及6次缺页中断的指令第四章 存 储 器 管 理 3.地址变换机构地址变换机构 图4-24请求分页中的地址变换过程第四章 存 储 器 管 理 4.6.2 内存分配策略和分配算法内存分配策略和分配算法 1.最小物理块数的确定最小物理块数的确定 是指能保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时，进程将无法运行。进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。对于某些简单的机器，若是单地址指令且采用直接寻址方式，则所需的最少物理块数为2。其中，一块是用于存放指令的页面，另一块则是用于存放数据的页面。如果该机器允许间接寻址时，则至少要求有三个物理块。对于某些功能较强的机器，其指令长度可能是两个或多于两个字节，因而其指令本身有可能跨两个页面，且源地址和目标地址所涉及的区域也都可能跨两个页面。第四章 存 储 器 管 理 2.物理块的分配策略物理块的分配策略 在请求分页系统中，可采取两种内存分配策略，即固定和可变分配策略。在进行置换时，也可采取两种策略，即全局置换和局部置换。于是可组合出以下三种适用的策略。1)固定分配局部置换(FixedAllocation,LocalReplacement)2)可变分配全局置换(VariableAllocation,GlobalReplacement)3)可变分配局部置换(VariableAllocation,LocalReplacemen第四章 存 储 器 管 理 3.物理块分配算法物理块分配算法 1)平均分配算法这是将系统中所有可供分配的物理块，平均分配给各个进程。例如，当系统中有100个物理块，有5个进程在运行时，每个进程可分得20个物理块。这种方式貌似公平，但实际上是不公平的，因为它未考虑到各进程本身的大小。如有一个进程其大小为200页，只分配给它20个块，这样，它必然会有很高的缺页率；而另一个进程只有10页，却有10个物理块闲置未用。第四章 存 储 器 管 理 2)按比例分配算法这是根据进程的大小按比例分配物理块的算法。如果系统中共有n个进程，每个进程的页面数为Si，则系统中各进程页面数的总和为：又假定系统中可用的物理块总数为m，则每个进程所能分到的物理块数为bi，将有：b应该取整，它必须大于最小物理块数。第四章 存 储 器 管 理 第四章 存 储 器 管 理 4.6.3 调页策略调页策略 1.何时调入页面何时调入页面 1)预调页策略2)2)请求调页策略第四章 存 储 器 管 理 2.从何处调入页面从何处调入页面 在请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。通常，由于对换区是采用连续分配方式，而事件是采用离散分配方式，故对换区的磁盘I/O速度比文件区的高。这样，每当发生缺页请求时，系统应从何处将缺页调入内存，可分成如下三种情况：(1)系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度。为此，在进程运行前，便须将与该进程有关的文件，从文件区拷贝到对换区。第四章 存 储 器 管 理(2)系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出，以后再调入时，仍从文件区直接调入。但对于那些可能被修改的部分，在将它们换出时，便须调到对换区，以后需要时，再从对换区调入。(3)UNIX方式。由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，应从对换区调入。由于UNIX系统允许页面共享，因此，某进程所请求的页面有可能已被其它进程调入内存，此时也就无须再从对换区调入。第四章 存 储 器 管 理 3.页面调入过程页面调入过程每当程序所要访问的页面未在内存时，便向CPU发出一缺页中断，中断处理程序首先保留CPU环境，分析中断原因后，转入缺页中断处理程序。该程序通过查找页表，得到该页在外存的物理块后，如果此时内存能容纳新页，则启动磁盘I/O将所缺之页调入内存，然后修改页表。如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出；如果该页未被修改过，可不必将该页写回磁盘；但如果此页已被修改，则必须将它写回磁盘，然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。在缺页调入内存后，利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。第四章 存 储 器 管 理 4.7 页面置换算法页面置换算法 4.7.1 最佳置换算法和先进先出置换算法最佳置换算法和先进先出置换算法 1.最佳(Optimal)置换算法最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。第四章 存 储 器 管 理 假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1进程运行时，先将7，0，1三个页面装入内存。以后，当进程要访问页面2时，将会产生缺页中断。此时OS根据最佳置换算法，将选择页面7予以淘汰。图4-25利用最佳页面置换算法时的置换图第四章 存 储 器 管 理 2.先进先出先进先出(FIFO)页面置换算法页面置换算法 图4-26利用FIFO置换算法时的置换图第四章 存 储 器 管 理 4.7.2 最近最久未使用最近最久未使用(LRU)置换算法置换算法 1.LRU(Least Recently Used)置换算法的描述置换算法的描述 图4-27LRU页面置换算法第四章 存 储 器 管 理 2.LRU置换算法的硬件支持置换算法的硬件支持 1)寄存器寄存器为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为R=Rn-1Rn-2Rn-3R2R1R0第四章 存 储 器 管 理 图4-28某进程具有8个页面时的LRU访问情况第四章 存 储 器 管 理 2)栈栈 图4-29用栈保存当前使用页面时栈的变化情况第四章 存 储 器 管 理 4.7.3 Clock置换算法置换算法 1.简单的简单的Clock置换算法置换算法 图4-30简单Clock置换算法的流程和示例第四章 存 储 器 管 理 2.改进型改进型Clock置换算法置换算法 由访问位A和修改位M可以组合成下面四种类型的页面：1类(A=0,M=0):表示该页最近既未被访问，又未被修改，是最佳淘汰页。2类(A=0,M=1)：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。3类(A=1,M=0)：最近已被访问，但未被修改，该页有可能再被访问。4类(A=1,M=1):最近已被访问且被修改，该页可能再被访问。第四章 存 储 器 管 理 其执行过程可分成以下三步：(1)从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。(2)如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。(3)如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。第四章 存 储 器 管 理 4.7.4 其它置换算法其它置换算法 1.最少使用(LFU：LeastFrequentlyUsed)置换算法2.2.页面缓冲算法(PBA：PageBufferingAlgorithm)第四章 存 储 器 管 理 4.8 请求分段存储管理方式请求分段存储管理方式 4.8.1 请求分段中的硬件支持请求分段中的硬件支持 1.段表机制段表机制 段名段长段的基址存取方式访问字段A修改位M存在位P增补位外存始址第四章 存 储 器 管 理 在段表项中，除了段名(号)、段长、段在内存中的起始地址外，还增加了以下诸项：(1)存取方式。(2)访问字段A。(3)修改位M。(4)存在位P。(5)增补位。(6)外存始址。第四章 存 储 器 管 理 2.缺段中断机构缺段中断机构 图图 4-31 请求分段系统中的中断处理过程请求分段系统中的中断处理过程第四章 存 储 器 管 理 3.地址变换机构地址变换机构 图4-32请求分段系统的地址变换过程第四章 存 储 器 管 理 4.8.2 分段的共享与保护分段的共享与保护 1.共享段表共享段表 图4-33共享段表项第四章 存 储 器 管 理 2.共享段的分配与回收共享段的分配与回收 1)共享段的分配在为共享段分配内存时，对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，再把共享段调入该区，同时将该区的始址填入请求进程的段表的相应项中，还须在共享段表中增加一表项，填写有关数据，把count置为1；之后，当又有其它进程需要调用该共享段时，由于该共享段已被调入内存，故此时无须再为该段分配内存，而只需在调用进程的段表中，增加一表项，填写该共享段的物理地址；在共享段的段表中，填上调用进程的进程名、存取控制等，再执行count=count+1操作，以表明有两个进程共享该段。第四章 存 储 器 管 理 2)共享段的回收当共享此段的某进程不再需要该段时，应将该段释放，包括撤在该进程段表中共享段所对应的表项，以及执行count=count-1操作。若结果为0，则须由系统回收该共享段的物理内存，以及取消在共享段表中该段所对应的表项，表明此时已没有进程使用该段；否则(减1结果不为0)，则只是取消调用者进程在共享段表中的有关记录。第四章 存 储 器 管 理 3.分段保护分段保护 1)越界检查2)2)存取控制检查(1)只读(2)(2)只执行(3)(3)读/写(4)3)环保护机构(5)一个程序可以访问驻留在相同环或较低特权环中的数据。(6)一个程序可以调用驻留在相同环或较高特权环中的服务。第四章 存 储 器 管 理 图4-34环保护机构