四章节存储器管理ppt课件

1、第四章 存 储 器 管 理 第四章第四章 存储器管理存储器管理 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 对用户程序的处置步骤 库链接程

2、序装入模块装入程序编译程序产生的目标模块第一步第二步第三步内存第四章 存 储 器 管 理 4.1.1 程序的装入程序的装入1. 绝对装入方式绝对装入方式(单道系统中单道系统中) 程序中所运用的绝对地址，既可在编译或汇编时给出， 也可由程序员直接赋予。 通常是在编译或汇编时，再将这些符号地址转换为绝对地址。 第四章 存 储 器 管 理 2. 可重定位装入方式可重定位装入方式(Relocation Loading Mode) 图 4-2 作业装入内存时的情况 LOAD 1,2500365LOAD 1,2500365100001100012500150005000250010000作业地址空间内存空

3、间第四章 存 储 器 管 理 3. 动态运转时装入方式动态运转时装入方式(Denamle Run-time Loading) 动态运转时的装入程序，在把装入模块装入内存后，并不立刻把装入模块中的相对地址转换为绝对地址， 而是把这种地址转换推迟到程序真正要执行时才进展。 因此， 装入内存后的一切地址都仍是相对地址。 第四章 存 储 器 管 理 4.1.2 程序的链接程序的链接 1. 静态链接方式静态链接方式(Static Linking) 图 4-3 程序链接表示图 模块 ACALL B；Return；0L1模块 BCALL C；Return；0M1模块 CReturn；0N10模块 AJSR“

4、L”Return；L1模块 BJSR“LM”Return；LLM1LMLMN1模块 CReturn；(a) 目标模块(b) 装入模块第四章 存 储 器 管 理 在将这几个目的模块装配成一个装入模块时，须处理以下两个问题： (1) 对相对地址进展修正。 (2) 变换外部调用符号。 第四章 存 储 器 管 理 2. 装入时动态链接装入时动态链接(Loadtime Dynamic Linking) 目的模块是边装入内存边链接的。目的模块是边装入内存边链接的。优点：优点：便于修正和更新。便于修正和更新。 目的模块是分开存放的目的模块是分开存放的(2) 便于实现对目的模块的共享。便于实现对目的模块的共享

5、。一个目的模块可链接到几个运用模块一个目的模块可链接到几个运用模块 第四章 存 储 器 管 理 3. 运转时动态链接运转时动态链接(Run-time Dynamic Linking) 在执行过程中，当发现一个被调用模块尚未装入内存时，再装入内存， 把它链接到调用者模块上。未被用到的目的模块，都不会被调入内存和被链接到装入模块上，如：错误处置用的目的模块 优点：加快程序的装入过程，可节省大量的内存空间。第四章 存 储 器 管 理 4.2 延续分配方式延续分配方式4.2.1 单一延续分配单一延续分配 单用户、单义务单用户、单义务把内存分为系统区和用户区两部分把内存分为系统区和用户区两部分系统区仅提

6、供应系统区仅提供应OS运用，通常是放在内存的低址部分；运用，通常是放在内存的低址部分；用户区是指除系统区以外的全部内存空间，用户区是指除系统区以外的全部内存空间， 提供应用户运提供应用户运用。用。 第四章 存 储 器 管 理 4.2.2 固定分区分配固定分区分配 1. 划分分区的方法划分分区的方法 分区大小相等。分区大小相等。程序太小时浪费内存，程序太大时能够缺乏以装入。程序太小时浪费内存，程序太大时能够缺乏以装入。 (2) 分区大小不等。分区大小不等。 多个较小的分区，适量的中等分区，少量大分区多个较小的分区，适量的中等分区，少量大分区第四章 存 储 器 管 理 2. 内存分配内存分配 图

7、4-4 固定分区运用表 第四章 存 储 器 管 理 4.2.3 动态分区分配动态分区分配 1. 分区分配中的数据构造分区分配中的数据构造 空闲分区表。空闲分区表。 表目：序号，始址表目：序号，始址大小大小(2) 空闲分区链。空闲分区链。 图 4-5 空闲链构造 前向指针N20N个字节可用后向指针N20第四章 存 储 器 管 理 2. 分区分配算法分区分配算法 初次顺应算法初次顺应算法FF。以地址递增的次序链接空闲分区以地址递增的次序链接空闲分区分配内存时，从链首顺序查找，找到为止，假设找不到那么分配分配内存时，从链首顺序查找，找到为止，假设找不到那么分配失败失败优点：优先利用低址，从而保管高址

8、的大空间优点：优先利用低址，从而保管高址的大空间缺陷：低址不断利用，留下碎片；添加查找开销缺陷：低址不断利用，留下碎片；添加查找开销 (2) 循环初次顺应算法，该算法是由初次顺应算法演化而成的。循环初次顺应算法，该算法是由初次顺应算法演化而成的。由初次顺应算法演化而来，只是从上次找到的空闲分区的下一个由初次顺应算法演化而来，只是从上次找到的空闲分区的下一个开场查找开场查找采用循环查找的方式采用循环查找的方式优点：空闲分区的分布得更均匀；缺陷：会缺乏大空闲分区；优点：空闲分区的分布得更均匀；缺陷：会缺乏大空闲分区；(3) 最正确顺应算法。最正确顺应算法。 找到满足要求，又是最小的空闲分区找到满足

9、要求，又是最小的空闲分区从小到大构成一空闲分区链从小到大构成一空闲分区链但切割剩余部分是最小的但切割剩余部分是最小的第四章 存 储 器 管 理 3. 分区分配操作分区分配操作 1) 分配内存 从头开始查表检索完否？m.sizeu.size?m.sizeu.sizesize?从该分区中划出u.size大小的分区将该分区分配给请求者修改有关数据结构返回返回继续检索下一个表项将该分区从链中移出YNNYYN图 4-6 内存分配流程第四章 存 储 器 管 理 2) 回收内存四种情况 图 4-7 内存回收时的情况 第四章 存 储 器 管 理 4.2.4 可重定位分区分配可重定位分区分配 1. 动态重定位的

10、引入要求延续空间，挪动后的程序须重定位动态重定位的引入要求延续空间，挪动后的程序须重定位 图 4-8 紧凑的表示 操作系统用户程序1用户程序310 KB30 KB用户程序614 KB用户程序926 KB操作系统用户程序1用户程序3用户程序6用户程序980 KB(a) 紧凑前(b) 紧凑后第四章 存 储 器 管 理 2. 动态重定位的实现动态重定位的实现 动态装入方式中，内存中的作业仍是相对地址，在程动态装入方式中，内存中的作业仍是相对地址，在程序执行时，才转换为绝对地址序执行时，才转换为绝对地址 为加快转换速度，增设重定位存放器，用于存放起始为加快转换速度，增设重定位存放器，用于存放起始地址地

11、址 在小分区在小分区“拼凑时，不需对程序作任何修正拼凑时，不需对程序作任何修正第四章 存 储 器 管 理 2. 动态重定位的实现动态重定位的实现 图 4-9 动态重定位表示图 LOAD1,25003650100250050002500相对地址10000重定位寄存器LOAD1,250036510000101001250015000作业J处理机一侧 存储器一侧主存第四章 存 储 器 管 理 3. 动态重定位分区分配算法动态重定位分区分配算法 图 4-10 动态分区分配算法流程图 恳求分配u.size分区检索空闲分区链(表)找到大于u.size的可用区否?按动态分区方式进展分配修正有关的数据构造前往

12、分区号及首址空闲分区总和u.size?进展紧凑形成延续空闲区修正有关的数据构造否是无法分配前往否第四章 存 储 器 管 理 4.2.5 对换对换(Swapping) 1. 对换的引入对换的引入 所谓“对换， 是指把内存中暂时不能运转的进程或数据，调出到外存上，再把已具备运转条件的进程或数据，调入内存。对换是提高内存利用率的有效措施。 第四章 存 储 器 管 理 2. 对换空间的管理对换空间的管理在外存中设一对换区，用于存放换出的进程在外存中设一对换区，用于存放换出的进程进程在对换区中驻留是短暂的，对换是频繁的，故采用延续分配方式，进程在对换区中驻留是短暂的，对换是频繁的，故采用延续分配方式，以

13、提高速度以提高速度对换区的分配同样可以用空闲分区表或空闲分区链。在空闲分区表中对换区的分配同样可以用空闲分区表或空闲分区链。在空闲分区表中的每个表目中应包含两项，的每个表目中应包含两项， 即对换区的首址及其大小，它们的单位是即对换区的首址及其大小，它们的单位是盘块号和盘块数。盘块号和盘块数。 第四章 存 储 器 管 理 3. 进程的换出与换入进程的换出与换入 (1) 进程的换出。进程的换出。 1、系统首先选择处于阻塞形状且优先级最低的进程作为换、系统首先选择处于阻塞形状且优先级最低的进程作为换出进程，出进程，2、将该进程的程序和数据传送到磁盘的对换区上。、将该进程的程序和数据传送到磁盘的对换区

14、上。3、假设传送过程未出现错误，便可回收该进程所占用的内、假设传送过程未出现错误，便可回收该进程所占用的内存空间，并对该进程的存空间，并对该进程的PCB做相应的修正。做相应的修正。 第四章 存 储 器 管 理 (2) 进程的换入。进程的换入。 将换出时间将换出时间(换出到磁盘上换出到磁盘上)最久的进程作为换入进程，将最久的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。之换入，直至已无可换入的进程或无可换出的进程为止。 第四章 存 储 器 管 理 4.3 根本分页存储管理方式根本分页存储管理方式 4.3.1 页面与页表页面与页表 1. 页面 1) 页面和物理块页面或页：将

15、进程的逻辑地址空间分成假设干个大小相等的片，并为各页从0开场加以编号。(物理)块或页框(frame)：把内存空间分成与页面一样大小的假设干个存储块，加以编号。在为进程分配内存时，以块为单位将进程中的假设干个页分别装入到多个可以不相邻接的物理块中。“页内碎片：由于进程的最后一页经常装不满一块而构成了不可利用的碎片。 第四章 存 储 器 管 理 2) 页面大小页面大小页面假设太小：页面假设太小：内存碎片减小内存碎片减小但会导致进程的页表过长，占用更多的内存；但会导致进程的页表过长，占用更多的内存；还会降低页面换进换出的效率。还会降低页面换进换出的效率。假设页面较大：假设页面较大：虽然可以减少页表的

16、长度，提高页面换进换出的速度，虽然可以减少页表的长度，提高页面换进换出的速度，但却又会使页内碎片增大。但却又会使页内碎片增大。适宜的页面大小：适宜的页面大小：应是应是2的幂，通常为的幂，通常为512 B8 KB。 第四章 存 储 器 管 理 2. 地址构造地址构造 分页地址中的地址构造如下：分页地址中的地址构造如下： 页号P位移量W3112110 对某特定机器，其地址构造是一定的。假设给定一个逻辑地址空间中的地址为A(2170)，页面的大小为L(1024)，那么页号P(2)和页内地址d(122)可按下式求得： MODLAdLAINTP第四章 存 储 器 管 理 3. 页表每个进程一个页表，将页

17、号转换为块号页表每个进程一个页表，将页号转换为块号 图 4-11 页表的作用 用户程序0 页1 页2 页3 页4 页5 页n 页页表页号块号02132638495内存012345678910第四章 存 储 器 管 理 4.3.2 地址变换机构地址变换机构 1. 根本的地址变换机构始址和长度是平常放在根本的地址变换机构始址和长度是平常放在PCB中，运转时调入存放器中，运转时调入存放器 图 4-12 分页系统的地址变换机构 页表寄存器页表始址页表长度页号(3)页内地址逻辑地址L越界中断1块号b页表页号012物理地址3第四章 存 储 器 管 理 2. 具有快表的地址变换机构具有快表的地址变换机构(一

18、次访存一次访存) 图 4-13 具有快表的地址变换机构 页表寄存器页表始址页表长度页号页内地址逻辑地址L越界中断块号b页表页号页号输入寄存器块号bb快表d物理地址第四章 存 储 器 管 理 快表也叫“联想存放器，IBM系统中也称“TLB CPU给出有效地址，先查快表，假设找到那么直接读物理块，假设没找到那么找内存中的页表，并把表项送到快表中，假设快表满那么找不再需求的页表项换出。第四章 存 储 器 管 理 4.3.3 两级和多级页表两级和多级页表 普通计算机系统逻辑地址空间普通计算机系统逻辑地址空间(232264)，页表就变得非常大，要占很大，页表就变得非常大，要占很大内存空间。内存空间。如，

19、一个如，一个32位逻辑地址空间的分页系统，页面大小为位逻辑地址空间的分页系统，页面大小为4 KB即即212 B，那么，那么每个进程页表中的页表项可达每个进程页表中的页表项可达1兆个。每个页表项占一个字节，兆个。每个页表项占一个字节， 其页表就其页表就要占用要占用1MB的内存空间，而且还要求是延续的。的内存空间，而且还要求是延续的。 可以采用这样两个方法来处理这一问题：可以采用这样两个方法来处理这一问题： 采用离散分配方式来处理难以找到一块延续的大内存空间的问题：采用离散分配方式来处理难以找到一块延续的大内存空间的问题： 只将当前需求的部分页表项调入内存，只将当前需求的部分页表项调入内存， 其他

20、的页表项仍驻留在磁盘上，其他的页表项仍驻留在磁盘上，需求时再调入。需求时再调入。 第四章 存 储 器 管 理 1. 两级页表两级页表(Two-Level Page Table) 逻辑地址构造可描画如下：逻辑地址构造可描画如下： 第四章 存 储 器 管 理 图 4-14 两级页表构造 101110780121742n第0页页表1460121023第1页页表114115011023外部页表012345671141151468第n页页存空间第四章 存 储 器 管 理 图 4-15 具有两级页表的地址变换机构 外部页号P1P2外部页内地址页内地址d逻辑地址外部页表寄存器外部页

21、表db页表页表物理地址第四章 存 储 器 管 理 两级页表采用离散分配空间的方法，但并没有减少页两级页表采用离散分配空间的方法，但并没有减少页表所占空间。表所占空间。 故采用只将当前需求的页表调入内存，以后再根据需故采用只将当前需求的页表调入内存，以后再根据需求陆续调入。求陆续调入。 在外层页表中增设一个形状位在外层页表中增设一个形状位S，假设为，假设为0表示页表不表示页表不在内存，假设为在内存，假设为1表示在内存。表示在内存。第四章 存 储 器 管 理 2. 多级页表 对于64位的机器，假设页面大小仍采用4 KB，此时在外层页表中能够有4096 G个页表项， 要占用16384 GB的延续内存

22、空间。 必需采用多级页表，将外层页表再进展分页。 对于64位的计算机，假设要求它能支持2(=1844744 TB)规模的物理存储空间，那么即使是采用三级页表构造也是难以办到的；而在当前的实践运用中也无此必要。第四章 存 储 器 管 理 4.4 根本分段存储管理方式根本分段存储管理方式 4.4.1 分段存储管理方式的引入分段存储管理方式的引入 引入分段存储管理方式， 主要是为了满足用户和程序员的下述一系列需求： 1) 方便编程 按逻辑关系分段 2) 信息共享 以段为逻辑单位，便于共享，如函数 3) 信息维护 4) 动态增长 便于段数据段的增长 5) 动态链接 目的程序段动态链接第四章 存 储 器

23、 管 理 4.4.2 分段系统的根本原理分段系统的根本原理 1. 分段分段 分段地址中的地址具有如下构造：分段地址中的地址具有如下构造： 段号段内地址31 16 15 0按主程序，子程序，数据，栈等分段按主程序，子程序，数据，栈等分段每段从每段从0开场编号，段长不定开场编号，段长不定第四章 存 储 器 管 理 为每一个段分配一个延续分区为每一个段分配一个延续分区 各个段离散地放在内存中不同的分区中各个段离散地放在内存中不同的分区中 建立一段表，用于从逻辑段到物理内存区的映建立一段表，用于从逻辑段到物理内存区的映射射 段表中的表项存放段的基址和段的长度段表中的表项存放段的基址和段的长度 段表通常

24、放在内存中段表通常放在内存中2. 段表段表 第四章 存 储 器 管 理 图 4-16 利用段表实现地址映射 作业空间(MAIN)0030K(X)1020K(D)2015K(S)3010K30K20K15K10K40K80K120K150K段长基址段号(MAIN)030K(X)120K(D)215K(S)310K040K80K120K150K段表内存空间0123第四章 存 储 器 管 理 控制寄存器段表始址段表长度2100段号S越界1 K段长600段号01236 K4 K5002008 K9200基址位移量W82928K82928692主存物理地址有效地址图 4-17 分段系统的地址变换过程 3

25、. 地址变换机构 第四章 存 储 器 管 理 4. 分页和分段的主要区别分页和分段的主要区别 (1) 页是信息的物理单位，分页是为实现离散分配方式，分页仅仅是由于系统管理的需求而不是用户的需求。段那么是信息的逻辑单位，它含有一组其意义相对完好的信息。 分段的目的是为了能更好地满足用户的需求。 第四章 存 储 器 管 理 (2) 页的大小固定且由系统决议，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的；而段的长度却不固定，通常由编译程序在对源程序进展编译时，根据信息的性质来划分。 (3) 分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址

26、； 而分段的作业地址空间那么是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。 第四章 存 储 器 管 理 4.4.3 信息共享信息共享 ed 1ed 2ed 40data 1data 10进程12122606170页表ed 1ed 2ed 40data 1data 10进程22122607180ed 1ed 2ed 40data 1data 10data 1data 10主存021226061707180页表图 4-18 分页系统中共享editor的表示图第四章 存 储 器 管 理 图 4-19 分段系统中共享editor的表示图 editor进程1data 1进程2edit

27、ordata 2段表段长基址16080402401608040380editordata 1data 280240280380420第四章 存 储 器 管 理 4.4.4 段页式存储管理方式段页式存储管理方式 1. 根本原理根本原理 图 4-20 作业地址空间和地址构造 04K8K12K15K16K子程序段04K8K数据段04K8K10K12K(a)段号(S)段内页号(P)段内地址(W)(b)主程序段第四章 存 储 器 管 理 图 4-21 利用段表和页表实现地址映射 段号 状态页表大小页表始址0111213041页号 状态存储块#0111213041操作系统主存页表段表段表大小 段表始址段表

28、寄存器第四章 存 储 器 管 理 2. 地址变换过程地址变换过程 图 4-22 段页式系统中的地址变换机构 段表寄存器段表始址段表长度段号S页号P段超长段表0123页内地址页表0123b块号 b块内地址页表始址页表长度第四章 存 储 器 管 理 4.5 虚拟存储器的根本概念虚拟存储器的根本概念 4.5.1 虚拟存储器的引入虚拟存储器的引入 1. 常规存储器管理方式的特征常规存储器管理方式的特征 一次性。一次性。(全部装入，但浪费空间全部装入，但浪费空间) (2) 驻留性。驻留性。 长期驻留，直到终了长期驻留，直到终了第四章 存 储 器 管 理 2. 部分性原理部分性原理 早在1968年， De

29、nning.P就曾指出： (1) 程序执行时，除了少部分的转移和过程调用指令外， 在大多数情况下仍是顺序执行的。 (2) 过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域， 但经研讨看出，过程调用的深度在大多数情况下都不超越5。 (3) 程序中存在许多循环构造，这些虽然只由少数指令构成， 但是它们将多次执行。 (4) 程序中还包括许多对数据构造的处置， 如对数组进展操作， 它们往往都局限于很小的范围内。 第四章 存 储 器 管 理 局限性又表如今下述两个方面： (1) 时间局限性。某条指令或数据一旦执行或访问，那么不久以后该指令能够再次执行或访问。典型缘由：是由于在程序中存在着大量的循

30、环操作。 (2) 空间局限性。一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即访问能够集中在一定范围内典型情况：程序的顺序执行。 第四章 存 储 器 管 理 3. 虚拟存储器定义虚拟存储器定义 所谓虚拟存储器，所谓虚拟存储器， 是指具有恳求调入功能和置换功能，是指具有恳求调入功能和置换功能， 能从逻辑上对内存容量加以扩展的一种存储器系统。能从逻辑上对内存容量加以扩展的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决议，其运转速其逻辑容量由内存容量和外存容量之和所决议，其运转速度接近于内存速度，而每位的本钱接近于外存。度接近于内存速度，而每位的本钱接近于外存。虚拟存储

31、技术是一种性能非常优越的存储器管理技术，故虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地运用于大、被广泛地运用于大、 中、中、 小型机器和微型机中。小型机器和微型机中。 第四章 存 储 器 管 理 4.5.2 虚拟存储器的实现方法虚拟存储器的实现方法 1. 分页恳求系统分页恳求系统 1硬件支持。硬件支持。 恳求分页的页表机制，它是在纯分页的页表机制上恳求分页的页表机制，它是在纯分页的页表机制上添加假设干项而构成的，作为恳求分页的数据构造；添加假设干项而构成的，作为恳求分页的数据构造； 缺页中断机构，即要访问的页面尚未调入内存时缺页中断机构，即要访问的页面尚未调入内存时 便产生一缺页

32、中断，以恳求便产生一缺页中断，以恳求OS将所缺的页调入内存；将所缺的页调入内存； 地址变换机构。地址变换机构。(添加了产生和处置缺页中断和换添加了产生和处置缺页中断和换出功能出功能) 第四章 存 储 器 管 理 4.5.3 虚拟存储器的特征虚拟存储器的特征 多次性作业分多次调入内存多次性作业分多次调入内存 对换性允许换入换出对换性允许换入换出虚拟性虚拟性 从逻辑上扩展内存容量从逻辑上扩展内存容量第四章 存 储 器 管 理 4.6 恳求分页存储管理方式恳求分页存储管理方式 4.6.1 恳求分页中的硬件支持恳求分页中的硬件支持 1. 页表机制页表机制 页号 物理块号 状态位P 访问字段A 修改位M

33、外存地址 访问字段访问字段A：被访问的次数或多长时间没被访问。：被访问的次数或多长时间没被访问。第四章 存 储 器 管 理 2. 缺页中断机构缺页中断机构 图 4-23 涉及6次缺页中断的指令 页面B：A：654321指令copy ATO B缺页中断与其他中断的区别：缺页中断与其他中断的区别：1、在指令执行期间产生和、在指令执行期间产生和处置中断信号。处置中断信号。2、一条指令在执行期间能、一条指令在执行期间能够产生多次缺页中断。右够产生多次缺页中断。右图图6次次第四章 存 储 器 管 理 3. 地址变换机构地址变换机构 缺页中断处理保留CPU现场从外存中找到缺页内存满否？选择一页换出该页被修

34、改否？将该页写回外存OS命令CPU从外存读缺页启动I/O硬件将一页从外存换入内存修改页表否是是否页表项在快表中？CPU检索快表访问页表否页在内存？修改访问位和修改位形成物理地址地址变换结束否页号页表长度?开始程序请求访问一页产生缺页中断请求调页修改快表是越界中断是是图 4-24 恳求分页中的地址变换过程 第四章 存 储 器 管 理 4.6.2 内存分配战略和分配算法内存分配战略和分配算法 1. 最小物理块数确实定最小物理块数确实定 是指能保证进程正常运转所需的最小物理块数。少于此值时，进程将无法运转。最少物理块数与计算机的硬件构造有关，取决于指令格式、 功能和寻址方式。单地址指令且采用直接寻址

35、方式，那么所需的最少物理块数为2，指令+数据。间接寻址，那么至少要求有三个物理块。指令长度能够跨页源地址和目的地址所涉及的区域也都能够跨两个页面。第四章 存 储 器 管 理 2. 物理块的分配战略物理块的分配战略 在恳求分页系统中，可采取两种内存分配战略，即固定和可变分配战略。在进展置换时， 也可采取两种战略，即全局置换和部分置换。于是可组合出以下三种适用的战略。1) 固定分配部分置换(固定块数，不够换出，块数太多太少都不好)2) 可变分配全局置换 (先分几块，不够再从系统空闲块中分，空闲块用完，再从全局选换出的块)3) 可变分配部分置换(先分几块，从部分换，缺页率高时增块，反之减块) 第四章

36、 存 储 器 管 理 3. 物理块分配算法物理块分配算法 1) 平均分配算法 这是将系统中一切可供分配的物理块，平均分配给各个进程。 例如，当系统中有100个物理块，有5个进程在运转时，每个进程可分得20个物理块。未思索到各进程本身的大小。如有一个进程其大小为200页，只分配给它20个块，这样，它必然会有很高的缺页率；而另一个进程只需10页，却有10个物理块闲置未用。 第四章 存 储 器 管 理 2) 按比例分配算法按比例分配算法 根据进程的大小按比例分配物理块的算法。假设系统根据进程的大小按比例分配物理块的算法。假设系统中共有中共有n个进程，每个进程的页面数为个进程，每个进程的页面数为Si，

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

38、那么按优先权分。有的系统中，如重要的实时控制系统，那么能够是完全按有的系统中，如重要的实时控制系统，那么能够是完全按优先权分。优先权分。 第四章 存 储 器 管 理 4.6.3 调页战略调页战略 1. 何时调入页面何时调入页面 预调页战略预调页战略预测不久会被访问的页预先调入预测不久会被访问的页预先调入(胜利率只需胜利率只需50% ) ，每次调入多页，减少开销，普通用于初次调入每次调入多页，减少开销，普通用于初次调入2) 恳求调页战略恳求调页战略 发现不在内存再调入。每次调入一页，开销大发现不在内存再调入。每次调入一页，开销大第四章 存 储 器 管 理 2. 从何处调入页面从何处调入页面 在恳

39、求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。对换区是采用延续分配方式，而文件区是采用离散分配方式，故对换区的磁盘I/O速度比文件区的高。缺页时，应从何处将所缺页调入，可分成如下三种情况： (1) 系统拥有足够的对换区空间，可全部从对换区调入所需页面，以提高伐页速度。在进程运转前，便须将与该进程有关的文件，从文件区拷贝到对换区。 第四章 存 储 器 管 理 (2) 系统短少足够的对换区空间，凡不会被修正的文件，都直接从文件区调入；换出这些页面时不用换出，以后再调入时，仍从文件区直接调入。能够被修正的文件，换出时须调到对换区，以后需求时，再从对换区调入。 (3)

40、UNIX方式。由于与进程有关的文件都放在文件区，故凡是未运转过的页面，都应从文件区调入。曾经运转过被换出到对换区，因此在下次调入时，应从对换区调入。由于UNIX系统允许页面共享，某进程所恳求的页面有能够已被其它进程调入内存，就无须再从对换区调入。 第四章 存 储 器 管 理 3. 页面调入过程所要页面未在内存时，向CPU发出一缺页中断，中断处置程序首先保管CPU环境，分析中断缘由后， 转入缺页中断处置程序。该程序经过查找页表，得到该页在外存的块后，假设此时内存有空，那么启动磁盘I/O将所缺之页调入内存，然后修正页表。假设内存已满，那么须先按照某种置换算法从内存中选出一页预备换出；假设该页未被修

41、正正，不用写回磁盘；但假设此页已被修正， 那么必需将它写回磁盘，然后再把所缺的页调入内存， 并修正页表中的相应表项，置其存在位为“1，并将此页表项写入快表中。在缺页调入内存后，利用修正后的页表， 去构成所要访问数据的物理地址，再去访问内存数据。 第四章 存 储 器 管 理 4.7 页面置换算法页面置换算法 4.7.1 最正确置换算法和先进先出置换算法最正确置换算法和先进先出置换算法 1. 最正确最正确(Optimal)置换算法置换算法 其所选择的被淘汰页面，将是以后永不运用的，其所选择的被淘汰页面，将是以后永不运用的， 或许或许是在最长是在最长(未来未来)时间内不再被访问的页面。时间内不再被访

42、问的页面。采用最正确置换算法，通常可保证获得最低的缺页率。采用最正确置换算法，通常可保证获得最低的缺页率。 第四章 存 储 器 管 理 假定系统为某进程分配了三个物理块， 并思索有以下的页面号援用串：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予以淘汰。 引用率70770170122010320304243230321201201770101页框(物理块）203图 4-25 利用最正确页面置换算法时的置换图 第四章 存

43、储 器 管 理 2. 先进先出先进先出(FIFO)页面置换算法页面置换算法 引用率70770170122010323104430230321013201770201页框2304204230230127127011图 4-26 利用FIFO置换算法时的置换图 第四章 存 储 器 管 理 4.7.2 最近最久未运用最近最久未运用(LRU)置换算法置换算法 1. LRU(Least Recently Used)置换算法的描画置换算法的描画 图 4-27 LRU页面置换算法 引用率70770170122010320304403230321132201710701页框402432032102第四章 存

44、储 器 管 理 2. LRU置换算法的硬件支持置换算法的硬件支持 1) 存放器存放器 为了记录某进程在内存中各页的运用情况，须为每个为了记录某进程在内存中各页的运用情况，须为每个在内存中的页面配置一个移位存放器，可表示为在内存中的页面配置一个移位存放器，可表示为 R=Rn-1Rn-2Rn-3 R2R1R0定时将存放器右移一位，定时将存放器右移一位，n位整数最小的为最近最久位整数最小的为最近最久未运用的页面，某页被访问那么将未运用的页面，某页被访问那么将Rn-1置置1下例中，下例中，3页最久未被访问页最久未被访问第四章 存 储 器 管 理 图 4-28 某进程具有8个页面时的LRU访问情况 第四

45、章 存 储 器 管 理 2) 栈栈 图 4-29 用栈保管当前运用页面时栈的变化情况 4474707407047170410174010741210742120741210742621076栈底就是最近最久未用的页号栈底就是最近最久未用的页号第四章 存 储 器 管 理 4.7.3 Clock置换算法置换算法 1. 简单的简单的Clock置换算法置换算法 图 4-30 简单Clock置换算法的流程和例如 入口查寻指针前进一步，指向下一个表目页面访问位 0?选择该页面淘汰是返回置页面访问位“ 0”否块号页号访问位指针0124034215650711替换指针按按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)： 最近已被访问， 但未被修正， 该页有能够再被访问。 4类(A=1, M=1): 最近已被访问且被修正， 该页能够再被访问。 第四章 存 储 器 管 理 其

47、执行过程可分成以下三步： (1) 从指针所指示的当前位置开场， 扫描循环队列， 寻觅第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改动访问位A。 (2) 假设第一步失败，那么开场第二轮扫描，寻觅第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将一切扫描过的页面的访问位都置0。 (3) 反复第一步，假设仍失败，必要时再反复第二步，此时就一定能找到被淘汰的页。 第四章 存 储 器 管 理 4.7.4 其它置换算法其它置换算法 最少运用最少运用(LFU： Least Frequently Used)置换算法置换算法2. 页面缓冲算法页面缓冲算法(PBA： Page Bufferi