-操作系统chapter4存储器管理课件.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.9 4.9 请求分段存储管理方式请求分段存储管理方式 4.1 程序的装入和链接程序的装入和链接 图 4-1 对用户程序的处理步骤 库链接程序装入模

2、块装入程序编译程序产生的目标模块第一步第二步第三步内存4.1.1 程序的装入程序的装入1.绝对装入方式绝对装入方式(Absolute Loading Mode)程序中所使用的程序中所使用的绝对地址绝对地址，既可在编译或汇编时给出，既可在编译或汇编时给出，也可由程序员直接赋予。也可由程序员直接赋予。但在由程序员直接给出绝对地址但在由程序员直接给出绝对地址时，时，不仅要求程序员熟悉内存的使用情况，而且一旦程序不仅要求程序员熟悉内存的使用情况，而且一旦程序或数据被修改后，可能要改变程序中的所有地址。因此，或数据被修改后，可能要改变程序中的所有地址。因此，通常是宁可在程序中采用符号地址，然后在编译或汇

3、编时，通常是宁可在程序中采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址。再将这些符号地址转换为绝对地址。2.可重定位装入方式可重定位装入方式(Relocation Loading Mode)图 4-2 作业装入内存时的情况 LOAD 1,2500365LOAD 1,2500365100001100012500150005000250010000作业地址空间内存空间3.动态运行时装入方式动态运行时装入方式(Denamle Run-time Loading)动态运行时的装入程序，在把装入模块装入内存后，动态运行时的装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转

4、换为绝对地址，而并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因是把这种地址转换推迟到程序真正要执行时才进行。因此，此，装入内存后的所有地址都仍是相对地址。装入内存后的所有地址都仍是相对地址。4.1.2 程序的链接程序的链接 1.静态链接方式静态链接方式(Static Linking)图 4-3 程序链接示意图 模块 ACALL B；Return；0L1模块 BCALL C；Return；0M1模块 CReturn；0N10模块 AJSR“L”Return；L1模块 BJSR“LM”Return；LLM1LMLMN1模块 CReturn；(a)目

5、标模块(b)装入模块 静态链接静态链接将目标模块装配成一个装入模块时，须解将目标模块装配成一个装入模块时，须解决以下两个问题：决以下两个问题：(1)对相对地址进行修改。对相对地址进行修改。(2)变换外部调用符号。变换外部调用符号。2.装入时装入时动态链接动态链接(Loadtime Dynamic Linking)优点：优点：（1）便于修改和更新。便于修改和更新。(2)便于实现对目标模块的共享。便于实现对目标模块的共享。3.运行时动态链接运行时动态链接(Run-time Dynamic Linking)近几年流行起来的运行时动态链接方式，是对上述在装入时链接方式的一种改进。这种链接方式是将对某些

6、模块的链接推迟到执行时才执行，亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。4.2 连续分配方式连续分配方式4.2.1 单一连续分配单一连续分配 这是最简单的一种存储管理方式，但只能用于单用户、这是最简单的一种存储管理方式，但只能用于单用户、单任务的操作系统中。采用这种存储管理方式时，可把内单任务的操作系统中。采用这种存储管理方式时，可把内存分为存分为系统区系统区和和用户区用户区两部分，系统区仅提

7、供给两部分，系统区仅提供给OS使用，使用，通常是放在内存的低址部分；用户区是指除系统区以外的通常是放在内存的低址部分；用户区是指除系统区以外的全部内存空间，全部内存空间，提供给用户使用。提供给用户使用。4.2.2 固定分区分配固定分区分配 1.划分分区的方法划分分区的方法 分区大小相等，即使所有的内存分区大小相等。(2)分区大小不等。2.内存分配内存分配 图 4-5 固定分区使用表 4.2.3 动态分区分配动态分区分配 1.分区分配中的数据结构分区分配中的数据结构 空闲分区表。空闲分区表。(2)空闲分区链。空闲分区链。图图 4-6 空闲链结构空闲链结构 前向指针N20N个字节可用后向指针N20

8、3.分区分配操作分区分配操作 1)分配内存 从头开始查表检索完否？m.sizeu.size?m.sizeu.sizesize?从该分区中划出u.size大小的分区将该分区分配给请求者修改有关数据结构返回返回继续检索下一个表项将该分区从链中移出YNNYYN图 4-7 内存分配流程2)回收内存 图 4-7 内存回收时的情况 4.3.4 可重定位分区分配可重定位分区分配 1.动态重定位的引入动态重定位的引入图 4-8 紧凑的示意 操作系统用户程序1用户程序310 KB30 KB用户程序614 KB用户程序926 KB操作系统用户程序1用户程序3用户程序6用户程序980 KB(a)紧凑前(b)紧凑后2

9、.动态重定位的实现动态重定位的实现 图 4-10 动态重定位示意图 LOAD1,25003650100250050002500相对地址10000重定位寄存器LOAD1,250036510000101001250015000作业J处理机一侧 存储器一侧主存3.动态重定位分区分配算法动态重定位分区分配算法 图 4-11 动态分区分配算法流程图 请求分配u.size分区检索空闲分区链(表)找到大于u.size的可用区否?按动态分区方式进行分配修改有关的数据结构返回分区号及首批空闲分区总和u.size?进行紧凑形成连续空闲区修改有关的数据结构否是无法分配返回否4.3.5 对换对换(Swapping)1

10、.对换的引入对换的引入 所谓所谓“对换对换”，是指把是指把内存中内存中暂时不能运行的进程或暂时不能运行的进程或者暂时不用的程序和数据，调出到者暂时不用的程序和数据，调出到外存外存上，以便腾出足够上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存。对换是提高内存利用率的有效措程序和数据，调入内存。对换是提高内存利用率的有效措施。施。2.对换空间的管理对换空间的管理 为了能对对换区中的空闲盘块进行管理，在系统中应为了能对对换区中的空闲盘块进行管理，在系统中应配置相应的数据结构，以记录外存的使用情况。其形式与配置相

11、应的数据结构，以记录外存的使用情况。其形式与内存在动态分区分配方式中所用数据结构相似，即同样可内存在动态分区分配方式中所用数据结构相似，即同样可以用空闲分区表或空闲分区链。在空闲分区表中的每个表以用空闲分区表或空闲分区链。在空闲分区表中的每个表目中应包含两项，目中应包含两项，即对换区的首址及其大小，它们的单位即对换区的首址及其大小，它们的单位是盘块号和盘块数。是盘块号和盘块数。3.进程的换出与换入进程的换出与换入 (1)进程的换出。进程的换出。每当一进程由于创建子进程而需要更多的内存空间，每当一进程由于创建子进程而需要更多的内存空间，但又无足够的内存空间等情况发生时，系统应将某进程换但又无足够

12、的内存空间等情况发生时，系统应将某进程换出。出。其过程是：系统首先选择处于阻塞状态且优先级最低其过程是：系统首先选择处于阻塞状态且优先级最低的进程作为换出进程，然后启动盘块，将该进程的程序和的进程作为换出进程，然后启动盘块，将该进程的程序和数据传送到磁盘的对换区上。若传送过程未出现错误，便数据传送到磁盘的对换区上。若传送过程未出现错误，便可回收该进程所占用的内存空间，并对该进程的进程控制可回收该进程所占用的内存空间，并对该进程的进程控制块做相应的修改。块做相应的修改。(2)进程的换入。进程的换入。系统应定时地查看所有进程的状态，从中找出系统应定时地查看所有进程的状态，从中找出“就绪就绪”状态但

13、已换出的进程，将其中换出时间状态但已换出的进程，将其中换出时间(换出到磁盘上换出到磁盘上)最最久的进程作为换入进程，将之换入，直至已无可换入的进久的进程作为换入进程，将之换入，直至已无可换入的进程或无可换出的进程为止。程或无可换出的进程为止。4.4 基本分页存储管理方式基本分页存储管理方式 4.4.1 页面与页表页面与页表 1.页面页面 1)页面和物理块页面和物理块 分页存储管理，是将一个进程的逻辑地址空间分成若干个分页存储管理，是将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号，从大小相等的片，称为页面或页，并为各页加以编号，从0开始，开始，如第如第0页、第页、

14、第1页等。相应地，也把内存空间分成与页面相同大页等。相应地，也把内存空间分成与页面相同大小的若干个存储块，称为小的若干个存储块，称为(物理物理)块或页框块或页框(frame)，也同样为也同样为它们加以编号，如它们加以编号，如0块、块、1块等等。在为进程分配内存时，块等等。在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为可利用的碎片，称之为“页内碎片页内碎片”。2)页面大小页面大小 在在分页

15、系统分页系统中的页面其大小应适中。页面若太小，一方中的页面其大小应适中。页面若太小，一方面虽然可使内存碎片减小，从而减少了内存碎片的总空间，面虽然可使内存碎片减小，从而减少了内存碎片的总空间，有利于提高内存利用率，但另一方面也会使每个进程占用较有利于提高内存利用率，但另一方面也会使每个进程占用较多的页面，从而导致进程的多的页面，从而导致进程的页表过长页表过长，占用大量内存；，占用大量内存；此此外，还会降低页面换进换出的效率。然而，如果选择的页面外，还会降低页面换进换出的效率。然而，如果选择的页面较大，虽然可以减少页表的长度，提高页面换进换出的速度，较大，虽然可以减少页表的长度，提高页面换进换出

16、的速度，但却又会使页内碎片增大。因此，页面的大小应选择得适中，但却又会使页内碎片增大。因此，页面的大小应选择得适中，且页面大小应是且页面大小应是2的幂，通常为的幂，通常为512 B8 KB。2.地址结构地址结构 分页地址中的地址结构如下：分页地址中的地址结构如下：页号P位移量W3112110 对某特定机器，其地址结构是一定的。若给定一个逻对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为辑地址空间中的地址为A，页面的大小为，页面的大小为L，则页号，则页号P和页和页内地址内地址d可按下式求得：可按下式求得：MODLAdLAINTP3.页表页表 图 4-11 页表的作用 用户程序0

17、 页1 页2 页3 页4 页5 页n 页页表页号块号02132638495内存0123456789104.4.2 地址变换机构地址变换机构 1.基本的地址变换机构基本的地址变换机构 图 4-12 分页系统的地址变换机构 页表寄存器页表始址页表长度页号(3)页内地址逻辑地址L越界中断1块号b页表页号012物理地址32.具有快表的地址变换机构具有快表的地址变换机构 图 4-13 具有快表的地址变换机构 页表寄存器页表始址页表长度页号页内地址逻辑地址L越界中断块号b页表页号页号输入寄存器块号bb快表d物理地址【例1】考虑一个由8个页面，每页有1024个字节组成的逻辑空间，把它装入到有32个物理块的存

18、储器中，问：（1）逻辑地址需要多少二进制位表示？（2）物理地址需要多少二进制位表示？解:因为页面数为8=23，故需要3位二进制数表示。每页有1024个字节，1024=210，于是页内地址需要10位二进制数表示。32个物理块，需要5位二进制数表示（32=25）。（1）、页的逻辑地址由页号和页内地址组成，所以需要3+10=13位二进制数表示。（2）、页的物理地址由块号和页内地址的拼接，所以需要5+10=15位二进制数表示。例例2、分页存储管理中页表如图。页面大小为、分页存储管理中页表如图。页面大小为1024B，试将逻辑地址试将逻辑地址1011，2148，4000，5012转化为相应转化为相应的物理

19、地址。的物理地址。物理地址页的大小物理地址页的大小L 块号块号f页内地址页内地址d 解：解：设页号为设页号为p，页内位移为，页内位移为d，则：，则：（1）逻辑地址）逻辑地址1011，pINT(1011/1024)0，d1011 mod 10241011。查页表第。查页表第0页对应第页对应第2块，块，物理地址为物理地址为1024 210113059。（2）对于逻辑地址）对于逻辑地址2148，pINT(2148/1024)2，d2148 mod 1024100。查页表第。查页表第2页对应第页对应第1块，块，物理地址为物理地址为10241001124。（3）对于逻辑地址）对于逻辑地址4000，pIN

20、T(4000/1024)3，d4000 mod 1024928。查页表第。查页表第3页对应第页对应第6块，块，物理地址为物理地址为1024 69287072。（4）对于逻辑地址）对于逻辑地址5012，pINT(5012/1024)4，d5012 mod 1024916。因页号超过页表长度，。因页号超过页表长度，该逻辑地址非法。该逻辑地址非法。页号块号021321364.3.3 两级和多级页表两级和多级页表 现代的大多数计算机系统，都支持非常大的逻辑地址空现代的大多数计算机系统，都支持非常大的逻辑地址空间间(232264)。在这样的环境下，页表就变得非常大，要占用相。在这样的环境下，页表就变得非

21、常大，要占用相当大的内存空间。例如，对于一个具有当大的内存空间。例如，对于一个具有32位逻辑地址空间的位逻辑地址空间的分页系统，规定页面大小为分页系统，规定页面大小为4 KB即即212 B，则在每个进程页表，则在每个进程页表中的页表项可达中的页表项可达1兆个之多。又因为每个页表项占用一个字节，兆个之多。又因为每个页表项占用一个字节，故每个进程仅仅其页表就要占用故每个进程仅仅其页表就要占用4 KB的内存空间，而且还要的内存空间，而且还要求是连续的。求是连续的。可以采用这样两个方法来解决这一问题：可以采用这样两个方法来解决这一问题：采采用离散分配方式来解决难以找到一块连续的大内存空间的问用离散分配

22、方式来解决难以找到一块连续的大内存空间的问题：题：只将当前需要的部分页表项调入内存，只将当前需要的部分页表项调入内存，其余的页表项其余的页表项仍驻留在磁盘上，需要时再调入。仍驻留在磁盘上，需要时再调入。1.两级页表两级页表(Two-Level Page Table)逻辑地址结构可描述如下：逻辑地址结构可描述如下：图 4-14 两级页表结构 101110780121742n第0页页表1460121023第1页页表114115011023外部页表012345671141151468第n页页表14680121023内存空间图图 4-15 具有两级页表的地址变换机构具有两级页表的地址变换机构 外部页号

23、P1P2外部页内地址页内地址d逻辑地址外部页表寄存器外部页表db页表页表物理地址 2.多级页表多级页表 对于对于32位的机器，采用两级页表结构是合适的；但对于位的机器，采用两级页表结构是合适的；但对于64位的机器，如果页面大小仍采用位的机器，如果页面大小仍采用4 KB即即212 B，那么还剩，那么还剩下下52位，位，假定仍按物理块的大小假定仍按物理块的大小(212位位)来划分页表，则将来划分页表，则将余下的余下的42位用于外层页号。此时在外层页表中可能有位用于外层页号。此时在外层页表中可能有4096 G个页表项，个页表项，要占用要占用16384 GB的连续内存空间。的连续内存空间。必须采用必须

24、采用多级页表，将外层页表再进行分页，也是将各分页离散地多级页表，将外层页表再进行分页，也是将各分页离散地装入到不相邻接的物理块中，再利用第装入到不相邻接的物理块中，再利用第2级的外层页表来映级的外层页表来映射它们之间的关系。射它们之间的关系。对于对于64位的计算机，如果要求它能支持位的计算机，如果要求它能支持2(=1844744 TB)规模的物理存储空间，则即使是采用三级页表结构也是规模的物理存储空间，则即使是采用三级页表结构也是难以办到的；而在当前的实际应用中也无此必要。难以办到的；而在当前的实际应用中也无此必要。4.4 基本分段存储管理方式基本分段存储管理方式 4.4.1 分段存储管理方式

25、的引入分段存储管理方式的引入 引入分段存储管理方式，引入分段存储管理方式，主要是为了满足用户和程序员主要是为了满足用户和程序员的下述一系列需要：的下述一系列需要：1)方便编程方便编程 2)信息共享信息共享 3)信息保护信息保护 4)动态增长动态增长 5)动态链接动态链接 4.4.2 分段系统的基本原理分段系统的基本原理 1.分段分段 分段地址中的地址具有如下结构：分段地址中的地址具有如下结构：段号段号段内地址段内地址31 16 15 02.段表段表 图 4-17 利用段表实现地址映射 作业空间(MAIN)0030K(X)1020K(D)2015K(S)3010K30K20K15K10K40K8

26、0K120K150K段长基址段号(MAIN)030K(X)120K(D)215K(S)310K040K80K120K150K段表内存空间0123控制寄存器段表始址段表长度2100段号S越界1 K段长600段号01236 K4 K5002008 K9200基址位移量W82928K82928692主存物理地址有效地址图 4-18 分段系统的地址变换过程 3.地址变换机构 4.分页和分段的主要区别分页和分段的主要区别 分段分段分页分页划分单位划分单位逻辑上的段逻辑上的段(大小不固定大小不固定)固定大小的页固定大小的页采用目的采用目的满足用户的要求满足用户的要求满足系统的要求（消满足系统的要求（消除碎

27、片、提高内存利除碎片、提高内存利用率等）用率等）地址空间地址空间二维：程序员给出段号二维：程序员给出段号和段内地址和段内地址程序员给出一维地址：程序员给出一维地址：逻辑地址由系统直接逻辑地址由系统直接划分为划分为2部分部分优点优点4.5.3 信息共享信息共享 ed 1ed 2ed 40data 1data 10进程12122606170页表ed 1ed 2ed 40data 1data 10进程22122607180ed 1ed 2ed 40data 1data 10data 1data 10主存021226061707180页表图 4-19 分页系统中共享editor的示意图图 4-20 分

28、段系统中共享editor的示意图 editor进程1data 1进程2editordata 2段表段长 基址16080402401608040380editordata 1data 2802402803804204.4.4 段页式存储管理方式段页式存储管理方式 1.基本原理基本原理 图 4-20 作业地址空间和地址结构 04K8K12K15K16K子程序段04K8K数据段04K8K10K12K(a)段号(S)段内页号(P)段内地址(W)(b)主程序段图 4-21 利用段表和页表实现地址映射 段号状态页表大小页表始址0111213041页号状态存储块#0111213041操作系统主存页表段表段表

29、大小段表始址段表寄存器2.地址变换过程地址变换过程 图 4-22 段页式系统中的地址变换机构 段表寄存器段表始址段表长度段号S页号P段超长段表0123页内地址页表0123b块号 b块内地址页表始址页表长度4.5 虚拟存储器的基本概念虚拟存储器的基本概念 4.5.1 虚拟存储器的引入虚拟存储器的引入 1.常规存储器管理方式的特征常规存储器管理方式的特征 一次性。(2)驻留性。2.局部性原理局部性原理 早在早在1968年，年，Denning.P就曾指出：就曾指出：(1)程序执行时，程序执行时，除了少部分的转移和过程调用指令除了少部分的转移和过程调用指令外，外，在大多数情况下仍是顺序执行的。在大多数

30、情况下仍是顺序执行的。(2)过程调用将会使程序的执行轨迹由一部分区域转至过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域，另一部分区域，但经研究看出，过程调用的深度在大多数但经研究看出，过程调用的深度在大多数情况下都不超过情况下都不超过5。(3)程序中存在许多循环结构，程序中存在许多循环结构，这些虽然只由少数指这些虽然只由少数指令构成，令构成，但是它们将多次执行。但是它们将多次执行。(4)程序中还包括许多对数据结构的处理，程序中还包括许多对数据结构的处理，如对数组如对数组进行操作，进行操作，它们往往都局限于很小的范围内。它们往往都局限于很小的范围内。局限性又表现在下述两个方面：局限性又

31、表现在下述两个方面：(1)时间局限性。如果程序中的某条指令一旦执行，时间局限性。如果程序中的某条指令一旦执行，则不久以后该指令可能再次执行；如果某数据被访问过，则不久以后该指令可能再次执行；如果某数据被访问过，则不久以后该数据可能再次被访问。产生时间局限性的则不久以后该数据可能再次被访问。产生时间局限性的典型原因，是由于在程序中存在着大量的循环操作。典型原因，是由于在程序中存在着大量的循环操作。(2)空间局限性。一旦程序访问了某个存储单元，在空间局限性。一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的

32、地址，可能集中在一定的范围之内，段时间内所访问的地址，可能集中在一定的范围之内，其典型情况便是程序的顺序执行。其典型情况便是程序的顺序执行。3.虚拟存储器定义虚拟存储器定义 所谓虚拟存储器，所谓虚拟存储器，是指具有请求调入功能和置换功能，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。可见，虚近于内存速度，而每位的成本却又接近于外存。可见，虚拟存储技术是一种性能非常优越的

33、存储器管理技术，故被拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于大、广泛地应用于大、中、中、小型机器和微型机中。小型机器和微型机中。4.5.2 虚拟存储器的实现方法虚拟存储器的实现方法 1.分页请求系统分页请求系统 硬件支持。请求分页的页表机制，它是在纯分页的页表机制上增加若干项而形成的，作为请求分页的数据结构；缺页中断机构，即每当用户程序要访问的页面尚未调入内存时 便产生一缺页中断，以请求OS将所缺的页调入内存；地址变换机构，它同样是在纯分页地址变换机构的基础上发展形成的。(2)实现请求分页的软件。4.5.3 虚拟存储器的特征虚拟存储器的特征 多次性多次性 对换性对换性3、

34、虚拟性虚拟性 4.6 请求分页存储管理方式请求分页存储管理方式 4.6.1 请求分页中的硬件支持请求分页中的硬件支持 1.页表机制页表机制 页号页号 物理块号物理块号 状态位状态位P 访问字段访问字段A 修改位修改位M外存地址外存地址 2.缺页中断机构缺页中断机构 图图 4-23 涉及涉及6次缺页中断的指令次缺页中断的指令 页面B：A：654321指令copy ATO B3.地址变换机构地址变换机构 缺页中断处理保留CPU现场从外存中找到缺页内存满否？选择一页换出该页被修改否？将该页写回外存OS命令CPU从外存读缺页启动I/O硬件将一页从外存换入内存修改页表否是是否页表项在快表中？CPU检索快

35、表访问页表否页在内存？修改访问位和修改位形成物理地址地址变换结束否页号页表长度?开始程序请求访问一页产生缺页中断请求调页修改快表是越界中断是是图 4-24 请求分页中的地址变换过程 4.6.2 内存分配策略和分配算法内存分配策略和分配算法 1.最小物理块数的确定最小物理块数的确定 是指能保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时，进程将无法运行。进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。对于某些简单的机器，若是单地址指令且采用直接寻址方式，则所需的最少物理块数为2。其中，一块是用于存放指令的页面，另一块则是用于存放数据的页面

36、。如果该机器允许间接寻址时，则至少要求有三个物理块。对于某些功能较强的机器，其指令长度可能是两个或多于两个字节，因而其指令本身有可能跨两个页面，且源地址和目标地址所涉及的区域也都可能跨两个页面。2.物理块的分配策略物理块的分配策略 在请求分页系统中，可采取两种内存分配策略，即固定和可变分配策略。在进行置换时，也可采取两种策略，即全局置换和局部置换。于是可组合出以下三种适用的策略。1)固定分配局部置换(Fixed Allocation,Local Replacement)2)可变分配全局置换(Variable Allocation,Global Replacement)3)可变分配局部置换(Va

37、riable Allocation,Local Replacemen 3.物理块分配算法物理块分配算法 1)平均分配算法 这是将系统中所有可供分配的物理块，平均分配给各个进程。例如，当系统中有100个物理块，有5个进程在运行时，每个进程可分得20个物理块。这种方式貌似公平，但实际上是不公平的，因为它未考虑到各进程本身的大小。如有一个进程其大小为200页，只分配给它20个块，这样，它必然会有很高的缺页率；而另一个进程只有10页，却有10个物理块闲置未用。2)按比例分配算法 这是根据进程的大小按比例分配物理块的算法。如果系统中共有n个进程，每个进程的页面数为Si，则系统中各进程页面数的总和为：又假

38、定系统中可用的物理块总数为m，则每个进程所能分到的物理块数为bi，将有：b应该取整，它必须大于最小物理块数。niiSS1mSSbii 3)考虑优先权的分配算法 在实际应用中，为了照顾到重要的、紧迫的作业能尽快地完成，应为它分配较多的内存空间。通常采取的方法是把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。在有的系统中，如重要的实时控制系统，则可能是完全按优先权来为各进程分配其物理块的。4.6.3 调页策略调页策略 1.何时调入页面何时调入页面 预调页策略 2)请求调页策略 2.从何处调入页面从何处调入页面

39、在请求分页系统中的外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。通常，由于对换区是采用连续分配方式，而事件是采用离散分配方式，故对换区的磁盘I/O速度比文件区的高。这样，每当发生缺页请求时，系统应从何处将缺页调入内存，可分成如下三种情况：(1)系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度。为此，在进程运行前，便须将与该进程有关的文件，从文件区拷贝到对换区。(2)系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改而不必再将它们换出，以后再调入时，仍从文件区直接调入。但对于那些可能被修改的部分

40、，在将它们换出时，便须调到对换区，以后需要时，再从对换区调入。(3)UNIX方式。由于与进程有关的文件都放在文件区，故凡是未运行过的页面，都应从文件区调入。而对于曾经运行过但又被换出的页面，由于是被放在对换区，因此在下次调入时，应从对换区调入。由于UNIX系统允许页面共享，因此，某进程所请求的页面有可能已被其它进程调入内存，此时也就无须再从对换区调入。3.页面调入过程页面调入过程 每当程序所要访问的页面未在内存时，便向CPU发出一缺页中断，中断处理程序首先保留CPU环境，分析中断原因后，转入缺页中断处理程序。该程序通过查找页表，得到该页在外存的物理块后，如果此时内存能容纳新页，则启动磁盘I/O

41、将所缺之页调入内存，然后修改页表。如果内存已满，则须先按照某种置换算法从内存中选出一页准备换出；如果该页未被修改过，可不必将该页写回磁盘；但如果此页已被修改，则必须将它写回磁盘，然后再把所缺的页调入内存，并修改页表中的相应表项，置其存在位为“1”，并将此页表项写入快表中。在缺页调入内存后，利用修改后的页表，去形成所要访问数据的物理地址，再去访问内存数据。4.7 页面置换算法页面置换算法 4.7.1 最佳置换算法和先进先出置换算法最佳置换算法和先进先出置换算法 1.最佳(Optimal)置换算法 最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面，将是以后永不使

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 利用最佳页面置换算法时的置换图 2.先进先出先进先出(FIFO)页面置换算法页面置换算法 引用率707

43、70170122010323104430230321013201770201页框2304204230230127127011图 4-26 利用FIFO置换算法时的置换图 4.7.2 最近最久未使用最近最久未使用(LRU)置换算法置换算法 1.LRU(Least Recently Used)置换算法的描述置换算法的描述 图 4-27 LRU页面置换算法 引用率70770170122010320304403230321132201710701页框4024320321022.LRU置换算法的硬件支持置换算法的硬件支持 1)寄存器寄存器 为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置

44、一个移位寄存器，可表示为 R=Rn-1Rn-2Rn-3 R2R1R0 图 4-28 某进程具有8个页面时的LRU访问情况 2)栈栈 图 4-29 用栈保存当前使用页面时栈的变化情况 44747074070471704101740107412107421207412107426210764.7.3 Clock置换算法置换算法 1.简单的简单的Clock置换算法置换算法 图 4-30 简单Clock置换算法的流程和示例 入口查寻指针前进一步，指向下一个表目页面访问位 0?选择该页面淘汰是返回置页面访问位“0”否块号页号访问位指针0124034215650711替换指针2.改进型改进型Clock置换

45、算法置换算法 由访问位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)如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻

46、找A=0且M=1的第二类页面，将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置0。(3)如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复0。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。4.7.4 其它置换算法其它置换算法 最少使用(LFU：Least Frequently Used)置换算法2.页面缓冲算法(PBA：Page Buffering Algorithm)4.8 请求分段存储管理方式请求分段存储管理方式 4.8.1 请求分段中的硬件支持请求分段中的硬件支持 1.段表机制段表机制 段

47、名 段长 段的基址 存取方式 访问字段A 修改位M 存在位P 增补位 外存始址 在段表项中，除了段名(号)、段长、段在内存中的起始地址外，还增加了以下诸项：(1)存取方式。(2)访问字段A。(3)修改位M。(4)存在位P。(5)增补位。(6)外存始址。2.缺段中断机构缺段中断机构 虚段S不在内存阻塞请求进程内存中有合适的空闲区吗？从外存读入段S修改段表及内存空区链唤醒请求进程返回空区容量总和能否满足？空区拼接，以形成一个合适的空区淘汰一个或几个实段，以形成一个合适空区否否是是图图 4-31 请求分段系统中的中断处理过程请求分段系统中的中断处理过程3.地址变换机构地址变换机构 访问sww段长?符

48、合存取方式?段S在主存?修改访问字段,如写访问,置修改位1形成访问主存地址(A)(主存始址)(位移量w)返回分段越界中断处理分段保护中断处理缺段中断处理是是是否否否图 4-32 请求分段系统的地址变换过程4.8.2 分段的共享与保护分段的共享与保护 1.共享段表共享段表 图 4-33 共享段表项 段名段长内存始址状态外存始址共享进程计数count状态进程名进程号段号存取控制共享段表2.共享段的分配与回收共享段的分配与回收 1)共享段的分配 在为共享段分配内存时，对第一个请求使用该共享段的进程，由系统为该共享段分配一物理区，再把共享段调入该区，同时将该区的始址填入请求进程的段表的相应项中，还须在

49、共享段表中增加一表项，填写有关数据，把count置为1；之后，当又有其它进程需要调用该共享段时，由于该共享段已被调入内存，故此时无须再为该段分配内存，而只需在调用进程的段表中，增加一表项，填写该共享段的物理地址；在共享段的段表中，填上调用进程的进程名、存取控制等，再执行count=count+1操作，以表明有两个进程共享该段。2)共享段的回收 当共享此段的某进程不再需要该段时，应将该段释放，包括撤在该进程段表中共享段所对应的表项，以及执行count=count-1操作。若结果为0，则须由系统回收该共享段的物理内存，以及取消在共享段表中该段所对应的表项，表明此时已没有进程使用该段；否则(减1结果不为0)，则只是取消调用者进程在共享段表中的有关记录。3.分段保护分段保护 越界检查 2)存取控制检查 只读(2)只执行(3)读/写 3)环保护机构 一个程序可以访问驻留在相同环或较低特权环中的数据。一个程序可以调用驻留在相同环或较高特权环中的服务。图 4-34 环保护机构 调用返回调用返回环0环1环2(a)程序间的控制传输数据访问环0环1环2(b)数据访问数据访问