四章节存储器管理.ppt

《四章节存储器管理.ppt》由会员分享，可在线阅读，更多相关《四章节存储器管理.ppt（87页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章 存 储 器 管 理 四章节存储器管理 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望第四章 存 储 器 管 理 4.1 程序的装入和链接程序的装入和链接 图4-1对用户程序的处理步骤第四章 存 储 器 管 理 4.1.1 程序的装入程序的装入1.绝对装入方式绝对装入方式(单道系统中单道系统中)程程序序中中所所使使用用的的绝绝对对地地址址，既既可可在在编编译译或或汇汇编编时时给给出出，也可也可由程序员直接赋予。由程序员直接赋予。通通常常是是在在编编译译或或汇

2、汇编编时时，再再将将这这些些符符号号地地址址转转换换为为绝绝对地址。对地址。第四章 存 储 器 管 理 2.可重定位装入方式可重定位装入方式(Relocation Loading Mode)图4-2作业装入内存时的情况第四章 存 储 器 管 理 3.动态运行时装入方式动态运行时装入方式(Denamle Run-time Loading)动动态态运运行行时时的的装装入入程程序序，在在把把装装入入模模块块装装入入内内存存后后，并不立即并不立即把装入模块中的把装入模块中的相对地址转换为绝对地址相对地址转换为绝对地址，而而是是把把这这种种地地址址转转换换推推迟迟到到程程序序真真正正要要执执行行时时才才

3、进进行。行。因此，因此，装入内存后的所有装入内存后的所有地址都仍是地址都仍是相对地址相对地址。第四章 存 储 器 管 理 4.1.2 程序的链接程序的链接 1.静态链接方式静态链接方式(Static Linking)图4-3程序链接示意图第四章 存 储 器 管 理 在在将将这这几几个个目目标标模模块块装装配配成成一一个个装装入入模模块块时时，须须解解决以下两个问题：决以下两个问题：(1)对相对地址进行修改。对相对地址进行修改。(2)变换外部调用符号。变换外部调用符号。第四章 存 储 器 管 理 2.装入时动态链接装入时动态链接(Loadtime Dynamic Linking)目标模块是目标模

4、块是边装入内存边链接边装入内存边链接的。的。优点：优点：(1)便于修改和更新。便于修改和更新。（目标模块是分开存放的）（目标模块是分开存放的）(2)(2)便于实现对目标模块的共享。便于实现对目标模块的共享。(3)（一个目标模块可链接到几个应用模块（一个目标模块可链接到几个应用模块）第四章 存 储 器 管 理 3.运行时动态链接运行时动态链接(Run-time Dynamic Linking)在在执执行行过过程程中中，当当发发现现一一个个被被调调用用模模块块尚尚未未装装入入内内存存时，再装入内存，时，再装入内存，把它链接到调用者模块上。把它链接到调用者模块上。未未被被用用到到的的目目标标模模块块

5、，都都不不会会被被调调入入内内存存和和被被链链接接到到装入模块上，装入模块上，（如：错误处理用的目标模块）（如：错误处理用的目标模块）优点：优点：加快程序的装入过程，可节省大量的内存空间。加快程序的装入过程，可节省大量的内存空间。第四章 存 储 器 管 理 4.2 连续分配方式连续分配方式4.2.1 单一连续分配单一连续分配（单用户、单任务）单用户、单任务）把内存分为把内存分为系统区系统区和和用户区用户区两部分两部分系统区系统区仅提供给仅提供给OS使用，通常是放使用，通常是放在内存的在内存的低址低址部分；部分；用用户户区区是是指指除除系系统统区区以以外外的的全全部部内内存存空空间间，提提供供给

6、给用用户户使使用。用。第四章 存 储 器 管 理 4.2.2 固定分区分配固定分区分配 1.划分分区的方法划分分区的方法(1)分区大小相等。分区大小相等。(2)程序太小时程序太小时浪费内存，浪费内存，程序太大时程序太大时可能不足以装入。可能不足以装入。(3)(2)分区大小不等。分区大小不等。(4)多个较小的分区，适量的中等分区，少量大分区多个较小的分区，适量的中等分区，少量大分区第四章 存 储 器 管 理 2.内存分配内存分配 图4-4固定分区使用表第四章 存 储 器 管 理 4.2.3 动态分区分配动态分区分配 1.分区分配中的数据结构分区分配中的数据结构(1)空闲分区表空闲分区表。表目：序

7、号，始址表目：序号，始址大小大小(2)空闲分区链。空闲分区链。图4-5空闲链结构第四章 存 储 器 管 理 2.分区分配算法分区分配算法(1)首次适应算法首次适应算法FF。以以地址递增地址递增的次序链接空闲分区的次序链接空闲分区分配内存时，从链首顺序查找，找到为止，若找不到则分配失败分配内存时，从链首顺序查找，找到为止，若找不到则分配失败优点：优点：优先利用低址，从而保留高址的大空间优先利用低址，从而保留高址的大空间缺点：缺点：低址不断利用，留下碎片；增加查找开销低址不断利用，留下碎片；增加查找开销(2)循环首次适应算法，该算法是由首次适应算法演变而成的。循环首次适应算法，该算法是由首次适应算

8、法演变而成的。由首次适应算法演变而来，只是从上次找到的空闲分区的下一个开由首次适应算法演变而来，只是从上次找到的空闲分区的下一个开始查找始查找采用循环查找的方式采用循环查找的方式优点：优点：空闲分区的分布得更均匀；空闲分区的分布得更均匀；缺点：缺点：会缺乏大空闲分区；会缺乏大空闲分区；(3)最佳适应算法。最佳适应算法。找到满足要求，又是最小的空闲分区找到满足要求，又是最小的空闲分区从小到大形成一空闲分区链从小到大形成一空闲分区链但切割剩余部分是最小的但切割剩余部分是最小的第四章 存 储 器 管 理 3.分区分配操作分区分配操作 1)分配内存图4-6内存分配流程第四章 存 储 器 管 理 2)回

9、收内存（四种情况）图4-7内存回收时的情况第四章 存 储 器 管 理 4.2.4 可重定位分区分配可重定位分区分配 1.动态重定位的引入动态重定位的引入（要求连续空间，移动后的程序须重定位）图4-8紧凑的示意第四章 存 储 器 管 理 2.动态重定位的实现动态重定位的实现动态装入方式中，内存中的作业仍是相对地址，在程动态装入方式中，内存中的作业仍是相对地址，在程序序执行时执行时，才转换为绝对地址，才转换为绝对地址为加快转换速度，增设重为加快转换速度，增设重定位寄存器定位寄存器，用于存放起始，用于存放起始地址地址在小分区在小分区“拼凑拼凑”时，时，不需对程序作任何修改不需对程序作任何修改第四章

10、存 储 器 管 理 2.动态重定位的实现动态重定位的实现 图4-9动态重定位示意图第四章 存 储 器 管 理 3.动态重定位分区分配算法动态重定位分区分配算法 图4-10动态分区分配算法流程图请求分配u.size分区检索空闲分区链(表)找到大于u.size的可用区否?按动态分区方式进行分配修改有关的数据结构返回分区号及首址空闲分区总和u.size?进行紧凑形成连续空闲区修改有关的数据结构否是无法分配返回否第四章 存 储 器 管 理 4.2.5 对换对换(Swapping)1.对换的引入对换的引入 所所谓谓“对对换换”，是是指指把把内内存存中中暂暂时时不不能能运运行行的的进进程程或或数数据据，调

11、调出出到到外外存存上上，再再把把已已具具备备运运行行条条件件的的进进程程或或数数据据，调入内存。调入内存。对换是对换是提高内存利用率提高内存利用率的有效措施。的有效措施。第四章 存 储 器 管 理 2.对换空间的管理对换空间的管理在外存中设一在外存中设一对换区对换区，用于存放换出的进程，用于存放换出的进程进进程程在在对对换换区区中中驻驻留留是是短短暂暂的的，对对换换是是频频繁繁的的，故故采采用用连连续续分分配配方方式式，以提高速度以提高速度对对换换区区的的分分配配同同样样可可以以用用空空闲闲分分区区表表或或空空闲闲分分区区链链。在在空空闲闲分分区区表表中中的的每每个个表表目目中中应应包包含含两

12、两项项，即即对对换换区区的的首首址址及及其其大大小小，它它们们的的单单位位是是盘块号和盘块数盘块号和盘块数。第四章 存 储 器 管 理 3.进程的换出与换入进程的换出与换入 (1)进程的换出。进程的换出。1、系统首先选择处于、系统首先选择处于阻塞状态且优先级最低阻塞状态且优先级最低的进程作为换出进程，的进程作为换出进程，2、将该进程的程序和数据、将该进程的程序和数据传送到传送到磁盘的对换区上。磁盘的对换区上。3、若若传传送送过过程程未未出出现现错错误误，便便可可回回收收该该进进程程所所占占用用的的内内存存空空间间，并并对对该进程的该进程的PCB做相应的做相应的修改。修改。第四章 存 储 器 管

13、 理 (2)进程的换入。进程的换入。将将换换出出时时间间(换换出出到到磁磁盘盘上上)最最久久的的进进程程作作为为换换入入进进程程，将将之换入，直至已无可换入的进程或无可换之换入，直至已无可换入的进程或无可换出的进程为止。出的进程为止。第四章 存 储 器 管 理 4.3 基本分页存储管理方式基本分页存储管理方式 4.3.1 页面与页表页面与页表 1.页面页面 1)页面和物理块页面和物理块页页面面或或页页：将将进进程程的的逻逻辑辑地地址址空空间间分分成成若若干干个个大大小小相相等等的的片片，并并为为各各页从页从0开始加以编号。开始加以编号。(物物理理)块块或或页页框框(frame)：把把内内存存空

14、空间间分分成成与与页页面面相相同同大大小小的的若若干干个个存储块，加以编号。存储块，加以编号。在在为为进进程程分分配配内内存存时时，以以块块为为单单位位将将进进程程中中的的若若干干个个页页分分别别装装入入到到多多个可以个可以不相邻接不相邻接的的物理块物理块中。中。“页页内内碎碎片片”：由由于于进进程程的的最最后后一一页页经经常常装装不不满满一一块块而而形形成成了了不不可可利利用的碎片。用的碎片。第四章 存 储 器 管 理 2)页面大小页面大小页面若太小页面若太小：内存碎片减小内存碎片减小但会导致进程的但会导致进程的页表过长页表过长，占用更多的内存；，占用更多的内存；还会降低页面换进换出的还会降

15、低页面换进换出的效率效率。若页面较大：若页面较大：虽然可以减少页表的长度，提高页面换进换出的速度，虽然可以减少页表的长度，提高页面换进换出的速度，但却又会使但却又会使页内碎片增大页内碎片增大。合适的页面大小：合适的页面大小：应是应是2的幂，的幂，通常为通常为512 B8 KB。第四章 存 储 器 管 理 2.地址结构地址结构 分页地址中的地址结构如下：分页地址中的地址结构如下：页号P位移量W3112110对对某某特特定定机机器器，其其地地址址结结构构是是一一定定的的。若若给给定定一一个个逻逻辑辑地地址址空空间间中中的的地地址址为为A(2170)，页页面面的的大大小小为为L(1024)，则页号则

16、页号P(2)和页内地址和页内地址d(122)可按下式求得：可按下式求得：第四章 存 储 器 管 理 3.页表页表（每个进程一个页表，将页号转换为块号）（每个进程一个页表，将页号转换为块号）图4-11页表的作用第四章 存 储 器 管 理 4.3.2 地址变换机构地址变换机构 1.基本的地址变换机构基本的地址变换机构（始址和长度是平时放在（始址和长度是平时放在PCB中，运行时调入寄存器）中，运行时调入寄存器）图4-12分页系统的地址变换机构第四章 存 储 器 管 理 2.具有快表的地址变换机构具有快表的地址变换机构(一次访存一次访存)图4-13具有快表的地址变换机构第四章 存 储 器 管 理 快表

17、也叫“联想寄存器”，IBM系统中也称“TLB”CPU给出有效地址，先查快表，若找到则直接读物理块，若没找到则找内存中的页表，并把表项送到快表中，若快表满则找不再需要的页表项换出。第四章 存 储 器 管 理 4.3.3 两级和多级页表两级和多级页表 一一般般计计算算机机系系统统逻逻辑辑地地址址空空间间(232264)，页页表表就就变变得得非非常常大大，要要占占很很大大内内存空间。存空间。如如，一一个个32位位逻逻辑辑地地址址空空间间的的分分页页系系统统，页页面面大大小小为为4 KB即即212 B，则则每每个个进进程程页页表表中中的的页页表表项项可可达达1兆兆个个。每每个个页页表表项项占占一一个个

18、字字节节，其其页页表表就就要要占占用用1MB的的内内存存空间，而且还要求是空间，而且还要求是连续的连续的。可以采用这样两个方法来解决这一问题：可以采用这样两个方法来解决这一问题：采用采用离散分配方式离散分配方式来解决难以找到一块连续的大内存空间的问题：来解决难以找到一块连续的大内存空间的问题：只只将将当当前前需需要要的的部部分分页页表表项项调调入入内内存存，其其余余的的页页表表项项仍仍驻驻留留在在磁磁盘盘上上，需要时再调入。需要时再调入。第四章 存 储 器 管 理 1.两级页表两级页表(Two-Level Page Table)逻辑地址结构可描述如下：逻辑地址结构可描述如下：第四章 存 储 器

19、 管 理 图4-14两级页表结构第四章 存 储 器 管 理 图4-15具有两级页表的地址变换机构第四章 存 储 器 管 理 两级页表采用两级页表采用离散离散分配空间的方法，但分配空间的方法，但并没有减少页并没有减少页表表所占所占空间空间。故采用只将故采用只将当前需要的当前需要的页表调入内存，以后再根据需页表调入内存，以后再根据需要陆续调入。要陆续调入。在外层页表中增设一个状态位在外层页表中增设一个状态位S，若为，若为0表示页表不在表示页表不在内存，若为内存，若为1表示在内存。表示在内存。第四章 存 储 器 管 理 2.多级页表多级页表对对于于64位位的的机机器器，如如果果页页面面大大小小仍仍采

20、采用用4 KB，此此时时在在外外层层页页表表中中可可能能有有4096 G个个页页表表项项，要要占占用用16384 GB的的连连续内存空间。续内存空间。必须采用多级页表，将外层页表再进行分页。必须采用多级页表，将外层页表再进行分页。对对于于64位位的的计计算算机机，如如果果要要求求它它能能支支持持2(=1844744 TB)规规模模的的物物理理存存储储空空间间，则则即即使使是是采采用用三三级级页页表表结结构构也也是是难以办到的；而在当前的实际应用中也无此必要。难以办到的；而在当前的实际应用中也无此必要。第四章 存 储 器 管 理 4.4 基本分段存储管理方式基本分段存储管理方式 4.4.1 分段

21、存储管理方式的引入分段存储管理方式的引入 引引入入分分段段存存储储管管理理方方式式，主主要要是是为为了了满满足足用用户户和和程程序序员员的下述一系列需要：的下述一系列需要：1)方便编程方便编程（按逻辑关系分段）（按逻辑关系分段）2)信息共享信息共享（以段为逻辑单位，便于共享，如函数）（以段为逻辑单位，便于共享，如函数）3)信息保护信息保护 4)动态增长动态增长 （便于段（数据段）的增长）（便于段（数据段）的增长）5)动态链接动态链接（目标程序）段动态链接（目标程序）段动态链接第四章 存 储 器 管 理 4.4.2 分段系统的基本原理分段系统的基本原理 1.分段分段 分段地址中的地址具有如下结构

22、：分段地址中的地址具有如下结构：段号段内地址3116150按主程序，子程序，数据，栈等分段按主程序，子程序，数据，栈等分段每段从每段从0开始编号，段长不定开始编号，段长不定第四章 存 储 器 管 理 为每一个段分配一个连续分区为每一个段分配一个连续分区各个段离散地放在内存中不同的分区中各个段离散地放在内存中不同的分区中建立一段表，用于从建立一段表，用于从逻辑段逻辑段到到物理内存区物理内存区的映的映射射段表中的表项存放段的段表中的表项存放段的基址和段的长度基址和段的长度段表通常放在内存中段表通常放在内存中2.段表段表 第四章 存 储 器 管 理 图4-16利用段表实现地址映射第四章 存 储 器

23、管 理 图4-17分段系统的地址变换过程3.地址变换机构第四章 存 储 器 管 理 4.分页和分段的主要区别分页和分段的主要区别(1)页页是是信信息息的的物物理理单单位位，分分页页是是为为实实现现离离散散分分配配方方式，分页仅仅是由于式，分页仅仅是由于系统管理的需要系统管理的需要而不是用户的需要。而不是用户的需要。段段则则是是信信息息的的逻逻辑辑单单位位，它它含含有有一一组组其其意意义义相相对对完完整整的信息。的信息。分段的目的是为了能更好地满足分段的目的是为了能更好地满足用户的用户的需要需要。第四章 存 储 器 管 理(2)页页的的大大小小固固定定且且由由系系统统决决定定，由由系系统统把把逻

24、逻辑辑地地址址划分为划分为页号和页内地址页号和页内地址两部分，是由机器硬件实现的；两部分，是由机器硬件实现的；而而段段的的长长度度却却不不固固定定，通通常常由由编编译译程程序序在在对对源源程程序序进进行编译时，根据信息的性质来划分。行编译时，根据信息的性质来划分。(3)分分页页的的作作业业地地址址空空间间是是一一维维的的，即即单单一一的的线线性性地地址空间，程序员只需利用一个记忆符，即可表示一个地址；址空间，程序员只需利用一个记忆符，即可表示一个地址；而而分分段段的的作作业业地地址址空空间间则则是是二二维维的的，程程序序员员在在标标识识一一个地址时，个地址时，既需给出段名，又需给出段内地址。既

25、需给出段名，又需给出段内地址。第四章 存 储 器 管 理 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 虚拟存储器的引入

26、虚拟存储器的引入 1.常规存储器管理方式的特征常规存储器管理方式的特征(1)一次性。一次性。(全部装入，但浪费空间全部装入，但浪费空间)(2)驻留性。驻留性。（长期驻留，直到结束）（长期驻留，直到结束）第四章 存 储 器 管 理 2.局部性原理局部性原理 早在早在1968年，年，Denning.P就曾指出：就曾指出：(1)程程序序执执行行时时，除除了了少少部部分分的的转转移移和和过过程程调调用用指指令令外外，在大多数情况下仍是在大多数情况下仍是顺序顺序执行的执行的。(2)过过程程调调用用将将会会使使程程序序的的执执行行轨轨迹迹由由一一部部分分区区域域转转至至另另一一部部分分区区域域，但但经经研

27、研究究看看出出，过过程程调调用用的的深深度度在在大大多多数数情况下都情况下都不超过不超过5。(3)程程序序中中存存在在许许多多循循环环结结构构，这这些些虽虽然然只只由由少少数数指指令令构成，构成，但是它们将多次执行。但是它们将多次执行。(4)程程序序中中还还包包括括许许多多对对数数据据结结构构的的处处理理，如如对对数数组组进行操作，进行操作，它们往往都它们往往都局限于很小局限于很小的的范围内。范围内。第四章 存 储 器 管 理 局限性又表现在下述两个方面：局限性又表现在下述两个方面：(1)时时间间局局限限性性。某某条条指指令令或或数数据据一一旦旦执执行行或或访访问问，则则不久以后不久以后该指令

28、可能该指令可能再次执行再次执行或访问。或访问。典型原因：是由于在程序中存在着大量的典型原因：是由于在程序中存在着大量的循环循环操作。操作。(2)空空间间局局限限性性。一一旦旦程程序序访访问问了了某某个个存存储储单单元元，在在不不久久之之后后，其其附附近近的的存存储储单单元元也也将将被被访访问问，即即访访问问可可能能集中在一定范围内集中在一定范围内典型情况：典型情况：程序的程序的顺序顺序执行。执行。第四章 存 储 器 管 理 3.虚拟存储器定义虚拟存储器定义 所所谓谓虚虚拟拟存存储储器器，是是指指具具有有请请求求调调入入功功能能和和置置换换功功能能，能从能从逻辑上逻辑上对内存容量加以对内存容量加

29、以扩充扩充的一种存储器系统。的一种存储器系统。其其逻逻辑辑容容量量由由内内存存容容量量和和外外存存容容量量之之和和所所决决定定，其其运运行行速速度度接近于内存速度接近于内存速度，而每位的，而每位的成本接近于外存成本接近于外存。虚虚拟拟存存储储技技术术是是一一种种性性能能非非常常优优越越的的存存储储器器管管理理技技术术，故故被广泛地应用于大、被广泛地应用于大、中、中、小型机器和微型机中。小型机器和微型机中。第四章 存 储 器 管 理 4.5.2 虚拟存储器的实现方法虚拟存储器的实现方法 1.分页请求系统分页请求系统（1）硬件支持。）硬件支持。请请求求分分页页的的页页表表机机制制，它它是是在在纯纯

30、分分页页的的页页表表机机制制上上增加若干项增加若干项而形成的，作为请求分页的数据结构；而形成的，作为请求分页的数据结构；缺缺页页中中断断机机构构，即即要要访访问问的的页页面面尚尚未未调调入入内内存存时时 便产生一缺页中断，以请求便产生一缺页中断，以请求OS将所缺的页调入内存；将所缺的页调入内存；地址变换机构地址变换机构。(增加了产生和处理增加了产生和处理缺页中断缺页中断和和换出换出功能功能)第四章 存 储 器 管 理 4.5.3 虚拟存储器的特征虚拟存储器的特征 1.多次性多次性（作业分多次调入内存）（作业分多次调入内存）2.对换性对换性（允许换入换出）（允许换入换出）3.虚拟性虚拟性 （从逻

31、辑上扩充内存容量）（从逻辑上扩充内存容量）第四章 存 储 器 管 理 4.6 请求分页存储管理方式请求分页存储管理方式 4.6.1 请求分页中的硬件支持请求分页中的硬件支持 1.页表机制页表机制 页号物理块号状态位P访问字段A修改位M外存地址访问字段访问字段A：被访问的次数或多长时间没被访问。被访问的次数或多长时间没被访问。第四章 存 储 器 管 理 2.缺页中断机构缺页中断机构 图4-23涉及6次缺页中断的指令缺页中断与其他中断的区别缺页中断与其他中断的区别：1、在指令执行期间产生和、在指令执行期间产生和处理处理中断中断信号。信号。2、一条指令在执行期间可、一条指令在执行期间可能产生多次能产

32、生多次缺页中断缺页中断。（右。（右图图6次）次）第四章 存 储 器 管 理 3.地址变换机构地址变换机构 图4-24请求分页中的地址变换过程第四章 存 储 器 管 理 4.6.2 内存分配策略和分配算法内存分配策略和分配算法 1.最小物理块数的确定最小物理块数的确定 是是指指能能保保证证进进程程正正常常运运行行所所需需的的最最小小物物理理块块数数。少少于于此此值值时时，进程将无法运行。进程将无法运行。最最少少物物理理块块数数与与计计算算机机的的硬硬件件结结构构有有关关，取取决决于于指指令令格格式式、功功能能和和寻址方式。寻址方式。单单地地址址指指令令且且采采用用直直接接寻寻址址方方式式，则则所

33、所需需的的最最少少物物理理块块数数为为2，指指令令+数据。数据。间接寻址间接寻址，则至少要求有三个物理块。指令长度可能，则至少要求有三个物理块。指令长度可能跨页跨页源地址和目标地址所涉及的区域也都可能跨两个页面。源地址和目标地址所涉及的区域也都可能跨两个页面。第四章 存 储 器 管 理 2.物理块的分配策略物理块的分配策略 在在请请求求分分页页系系统统中中，可可采采取取两两种种内内存存分分配配策策略略，即即固固定定和和可可变变分分配配策策略略。在在进进行行置置换换时时，也也可可采采取取两两种种策策略略，即即全全局置换局置换和和局部置换局部置换。于是可组合出以下三种适用的策略。于是可组合出以下三

34、种适用的策略。1)固定分配局部置换固定分配局部置换(固定块数，不够换出，块数太多太少都不好固定块数，不够换出，块数太多太少都不好)2)可变分配全局置换可变分配全局置换(先分几块，不够再从系统空闲块中分，空闲块先分几块，不够再从系统空闲块中分，空闲块用完，再从全局选换出的块用完，再从全局选换出的块)3)可变分配局部置换可变分配局部置换(先分几块，从局部换，缺页率高时增块，反之先分几块，从局部换，缺页率高时增块，反之减块减块)第四章 存 储 器 管 理 3.物理块分配算法物理块分配算法 1)平均分配算法平均分配算法这这是是将将系系统统中中所所有有可可供供分分配配的的物物理理块块，平平均均分分配配给

35、给各各个个进程。进程。例例如如，当当系系统统中中有有100个个物物理理块块，有有5个个进进程程在在运运行行时时，每每个个进进程程可可分分得得20个个物物理理块块。未未考考虑虑到到各各进进程程本本身身的的大大小小。如如有有一一个个进进程程其其大大小小为为200页页，只只分分配配给给它它20个个块块，这这样样，它它必必然然会会有有很很高高的的缺缺页页率率；而而另另一一个个进进程只有程只有10页，却有页，却有10个物个物理块闲置未用。理块闲置未用。第四章 存 储 器 管 理 2)按比例分配算法按比例分配算法根根据据进进程程的的大大小小按按比比例例分分配配物物理理块块的的算算法法。如如果果系系统统中中

36、共共有有n个个进进程程，每每个个进进程程的的页页面面数数为为Si，则则系系统统中中各各进进程程页面数的总和为：页面数的总和为：又又假假定定系系统统中中可可用用的的物物理理块块总总数数为为m，则则每每个个进进程程所所能能分分到的物理块数为到的物理块数为bi，将有：，将有：b应该取整，它必须大于最小物理块数。应该取整，它必须大于最小物理块数。第四章 存 储 器 管 理 3)考虑优先权的分配算法考虑优先权的分配算法为为重要的、紧迫的重要的、紧迫的作业多分配内存空间。作业多分配内存空间。通常把内存中可分配块分成两部分：通常把内存中可分配块分成两部分：一部分一部分按比例按比例地分配给；另一部分则按地分配

37、给；另一部分则按优先权优先权分。分。有有的的系系统统中中，如如重重要要的的实实时时控控制制系系统统，则则可可能能是是完完全全按按优优先权先权分分。第四章 存 储 器 管 理 4.6.3 调页策略调页策略 1.何时何时调入页面调入页面 1)预调页策略预调页策略2)预测不久会被访问的页预先调入预测不久会被访问的页预先调入(成功率只有成功率只有50%)，3)每次调入多页，减少开销，一般用于首次调入每次调入多页，减少开销，一般用于首次调入4)2)请求调页策略请求调页策略5)发现不在内存再调入。每次调入一页，开销大发现不在内存再调入。每次调入一页，开销大第四章 存 储 器 管 理 2.从何处调入页面从何

38、处调入页面 在在请请求求分分页页系系统统中中的的外外存存分分为为两两部部分分：用用于于存存放放文文件件的的文件区文件区和用于存放对换页面的和用于存放对换页面的对换区对换区。对对换换区区是是采采用用连连续续分分配配方方式式，而而文文件件区区是是采采用用离离散散分分配配方方式式，故对换区的磁盘故对换区的磁盘I/O速度速度比文件区的比文件区的高高。缺页时，应从缺页时，应从何处何处将所缺页调入，可分成如下三种情况：将所缺页调入，可分成如下三种情况：(1)系系统统拥拥有有足足够够的的对对换换区区空空间间，可可全全部部从从对对换换区区调调入入所所需需页页面面，以以提提高高调调页页速速度度。在在进进程程运运

39、行行前前，便便须须将将与与该该进进程有关的文件，从文件区拷贝到程有关的文件，从文件区拷贝到对换区对换区。第四章 存 储 器 管 理(2)系系统统缺缺少少足足够够的的对对换换区区空空间间，凡凡不不会会被被修修改改的的文文件件，都都直直接接从从文文件件区区调调入入；换换出出这这些些页页面面时时不不必必换换出出，以以后后再再调调入入时时，仍仍从从文文件件区区直直接接调调入入。可可能能被被修修改改的的文文件件，换换出出时时须须调到调到对换区对换区，以后需要时，再从对换区调入。，以后需要时，再从对换区调入。(3)UNIX方方式式。由由于于与与进进程程有有关关的的文文件件都都放放在在文文件件区区，故故凡凡

40、是是未未运运行行过过的的页页面面，都都应应从从文文件件区区调调入入。曾曾经经运运行行过过被被换换出出到到对对换换区区，因因此此在在下下次次调调入入时时，应应从从对对换换区区调调入入。由由于于UNIX系系统统允允许许页页面面共共享享，某某进进程程所所请请求求的的页页面面有有可可能能已已被被其它进程调入内存，就无须再从对换区调入。其它进程调入内存，就无须再从对换区调入。第四章 存 储 器 管 理 3.页面调入过程页面调入过程所所要要页页面面未未在在内内存存时时，向向CPU发发出出一一缺缺页页中中断断，中中断断处处理理程程序序首首先先保保留留CPU环环境境，分分析析中中断断原原因因后后，转转入入缺缺

41、页页中中断断处处理理程程序序。该该程程序序通通过过查查找找页页表表，得得到到该该页页在在外外存存的的块块后后，若若此此时时内内存存有有空空，则则启启动动磁磁盘盘I/O将将所所缺缺之之页页调调入入内内存存，然然后后修修改改页页表表。若若内内存存已已满满，则则须须先先按按照照某某种种置置换换算算法法从从内内存存中中选选出出一一页页准准备备换换出出；如如果果该该页页未未被被修修改改过过，不不必必写写回回磁磁盘盘；但但如如果果此此页页已已被被修修改改，则则必必须须将将它它写写回回磁磁盘盘，然然后后再再把把所所缺缺的的页页调调入入内内存存，并并修修改改页页表表中中的的相相应应表表项项，置置其其存存在在位

42、位为为“1”，并并将将此此页页表表项项写写入入快快表表中中。在在缺缺页页调调入入内内存存后后，利利用用修修改改后后的的页页表表，去去形形成成所所要要访访问问数数据据的的物物理理地地址址，再再去去访访问问内内存存数据。数据。第四章 存 储 器 管 理 4.7 页面置换算法页面置换算法 4.7.1 最佳置换算法和先进先出置换算法最佳置换算法和先进先出置换算法 1.最佳最佳(Optimal)置换算法置换算法 其其所所选选择择的的被被淘淘汰汰页页面面，将将是是以以后后永永不不使使用用的的，或或许许是在是在最长最长(未来未来)时间内不再被访问时间内不再被访问的页面。的页面。采用最佳置换算法，采用最佳置换

43、算法，通常可保证获得通常可保证获得最低的缺页率最低的缺页率。第四章 存 储 器 管 理 假假定定系系统统为为某某进进程程分分配配了了三三个个物物理理块块，并并考考虑虑有有以以下下的页面号引用串：的页面号引用串：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利用最佳页面置换算法时的置换图第四章 存 储 器 管

44、 理 2.先进先出先进先出(FIFO)页面置换算法页面置换算法 图4-26利用FIFO置换算法时的置换图第四章 存 储 器 管 理 4.7.2 最近最久未使用最近最久未使用(LRU)置换算法置换算法 1.LRU(Least Recently Used)置换算法的描述置换算法的描述 图4-27LRU页面置换算法第四章 存 储 器 管 理 2.LRU置换算法的硬件支持置换算法的硬件支持 1)寄存器寄存器为为了了记记录录某某进进程程在在内内存存中中各各页页的的使使用用情情况况，须须为为每每个个在内存中的页面在内存中的页面配置一个移位寄存器配置一个移位寄存器，可表示为，可表示为 R=Rn-1Rn-2R

45、n-3R2R1R0定时定时将寄存器右移一位，将寄存器右移一位，n位整数最小的为最近最久位整数最小的为最近最久未使用的页面，某页被访问则将未使用的页面，某页被访问则将Rn-1置置1下例中，下例中，3页最久未被访问页最久未被访问第四章 存 储 器 管 理 图4-28某进程具有8个页面时的LRU访问情况第四章 存 储 器 管 理 2)栈栈 图4-29用栈保存当前使用页面时栈的变化情况栈底就是最近最久未用的页号栈底就是最近最久未用的页号第四章 存 储 器 管 理 4.7.3 Clock置换算法置换算法 1.简单的简单的Clock置换算法置换算法 图4-30简单Clock置换算法的流程和示例按按FIFO

46、形成循环队列，形成循环队列，某页被访问时置某页被访问时置1。换页时，若是换页时，若是0则换出；则换出；若是若是1则重新置则重新置0。第四章 存 储 器 管 理 2.改进型改进型Clock置换算法置换算法 由访问位由访问位A和修改位和修改位M可以组合成下面四种类型的页面：可以组合成下面四种类型的页面：1类类(A=0,M=0):表表示示该该页页最最近近既既未未被被访访问问，又又未未被被修修改改，是最佳淘汰页。是最佳淘汰页。2类类(A=0,M=1)：表表示示该该页页最最近近未未被被访访问问，但但已已被被修修改改，并不是很好的淘汰页。并不是很好的淘汰页。3类类(A=1,M=0)：最最近近已已被被访访问

47、问，但但未未被被修修改改，该该页页有有可能再被访问。可能再被访问。4类类(A=1,M=1):最近最近已被访问已被访问且且被修改被修改，该页可能再被该页可能再被访问。访问。第四章 存 储 器 管 理 其执行过程可分成以下三步：其执行过程可分成以下三步：(1)从从指指针针所所指指示示的的当当前前位位置置开开始始，扫扫描描循循环环队队列列，寻寻找找第第一一类类页页面面，将将所所遇遇到到的的第第一一个个页页面面作作为为所所选选中中的的淘淘汰汰页页。在在第一次扫描期间不改变访问位第一次扫描期间不改变访问位A。(2)如如果果第第一一步步失失败败，则则开开始始第第二二轮轮扫扫描描，寻寻找找第第二二类类页页面

48、面，将将所所遇遇到到的的第第一一个个这这类类页页面面作作为为淘淘汰汰页页。在在第第二二轮轮扫扫描描期间，将期间，将所有所有扫描过的页面的扫描过的页面的访问位访问位都都置置0。(3)重重复复第第一一步步，如如果果仍仍失失败败，必必要要时时再再重重复复第第二二步步，此此时就时就一定一定能能找到被淘汰的页。找到被淘汰的页。第四章 存 储 器 管 理 4.7.4 其它置换算法其它置换算法 1.最少使用最少使用(LFU：Least Frequently Used)置换算法置换算法2.页面缓冲算法页面缓冲算法(PBA：Page Buffering Algorithm)第四章 存 储 器 管 理 4.8 请

49、求分段存储管理方式请求分段存储管理方式 4.8.1 请求分段中的硬件支持请求分段中的硬件支持 1.段表机制段表机制 段名段长段的基址存取方式访问字段A修改位M存在位P增补位外存始址增补位：表示本段在运行中，是否做过动态增长增补位：表示本段在运行中，是否做过动态增长第四章 存 储 器 管 理 在在段段表表项项中中，除除了了段段名名(号号)、段段长长、段段在在内内存存中中的的起起始地址外，始地址外，还增加了以下诸项：还增加了以下诸项：(1)存取方式。存取方式。存取属性，如执行，只读，读存取属性，如执行，只读，读/写写(2)访问字段访问字段A。(3)修改位修改位M。(4)存在位存在位P。(5)增补位

50、。增补位。是否做过动态增长；是否做过动态增长；(6)外存始址。外存始址。第四章 存 储 器 管 理 2.缺段中断机构缺段中断机构 图图 4-31 请求分段系统中的中断处理过程请求分段系统中的中断处理过程第四章 存 储 器 管 理 3.地址变换机构地址变换机构 图4-32请求分段系统的地址变换过程第四章 存 储 器 管 理 4.8.2 分段的共享与保护分段的共享与保护 1.共享段表共享段表（系统中配置一共享段表）（系统中配置一共享段表）图4-33共享段表项第四章 存 储 器 管 理 2.共享段的分配与回收共享段的分配与回收 1)共享段的分配共享段的分配在在为为共共享享段段分分配配内内存存时时，第