操作系统原理第七章

1、1/19第七章第七章 内存管理内存管理内存管理的功能内存管理的功能程序的加载和链接程序的加载和链接连续分配方式连续分配方式基本分页分配方式基本分页分配方式基本分段分配方式基本分段分配方式虚拟页式分配虚拟页式分配页面置换算法页面置换算法虚拟段式分配虚拟段式分配段页式分配方式段页式分配方式2/197.1 内存管理的功能内存管理的功能存储管理主要是对主存的管理。不论存储管理主要是对主存的管理。不论何种操作系统的存储管理都必须能够实何种操作系统的存储管理都必须能够实现内存分配、地址变换、存储保护、存现内存分配、地址变换、存储保护、存储共享和存储扩充等功能。储共享和存储扩充等功能。 3/197.1.1

2、内存分配内存分配直接指定方式直接指定方式 ：编写程序时确定地址编写程序时确定地址 静态分配方式静态分配方式 ：程序装入内存时确定地址程序装入内存时确定地址动态分配方式动态分配方式 ：程序执行时确定地址程序执行时确定地址 4/197.1.2 地址变换地址变换地址空间：地址空间：程序编译时还没有装入主存，还不程序编译时还没有装入主存，还不能确定它在主存中的实际位置，所以都是从能确定它在主存中的实际位置，所以都是从开始。相对于位置开始的地址称为逻辑地址，开始。相对于位置开始的地址称为逻辑地址，也称为相对地址。地址空间是指逻辑地址的集也称为相对地址。地址空间是指逻辑地址的集合。合。 存储空间存储空间：

3、一个程序在主存中的实际位置称为一个程序在主存中的实际位置称为物理地址。物理地址的集合就是存储空间。物理地址。物理地址的集合就是存储空间。 5/197.1.2 地址变换地址变换地址转换：地址转换：作业逻辑地址到物理地址的转换，又称作业逻辑地址到物理地址的转换，又称为重定位。为重定位。 目标目标程序程序地址空间地址空间0n目标目标程序程序主存的存储空间主存的存储空间0K+nK图图7.1 一个作业的地址空间和存储空间一个作业的地址空间和存储空间6/197.1.3 存储保护存储保护 地址保护地址保护 ：一个进程不能跳到另一个进程一个进程不能跳到另一个进程地址上去执行。地址上去执行。权限保护：权限保护：

4、对于不同的进程有不同的存取对于不同的进程有不同的存取权限，确保不能越权执行。权限，确保不能越权执行。 7/197.1.4 存储共享存储共享 任何保护机制必须具有一定的灵活性，以任何保护机制必须具有一定的灵活性，以允许多个进程访问主存的同一部分。例如，许允许多个进程访问主存的同一部分。例如，许多进程正在执行同一个程序，则允许每个进程多进程正在执行同一个程序，则允许每个进程访问该程序的同一个副本要比让每个进程有自访问该程序的同一个副本要比让每个进程有自己单独的副本更具优势。合作完成同一个任务己单独的副本更具优势。合作完成同一个任务的进程可能需要共享访问同一个数据结构。因的进程可能需要共享访问同一个

5、数据结构。因此内存管理系统必须允许对内存共享区域进行此内存管理系统必须允许对内存共享区域进行受控访问，而不会损害基本的保护。受控访问，而不会损害基本的保护。 8/197.1.5 存储扩充存储扩充 请求调入功能请求调入功能 ：把程序的一部分装入内存，使把程序的一部分装入内存，使其先运行，在运行的过程中随时请求操作系统其先运行，在运行的过程中随时请求操作系统把需要的部分调入内存。把需要的部分调入内存。 置换功能置换功能 ：把不需要的部分换出主存，以装载把不需要的部分换出主存，以装载需要的部分。需要的部分。9/197.2 程序的加载和链接程序的加载和链接 源模块源模块1目标模块目标模块1源模块源模块

6、2目标模块目标模块2源模块源模块n 目标模块目标模块n 加载模块加载模块（在外存）（在外存） 加载模块加载模块（在内存）（在内存） 编译编译 链接链接 加载加载 运行运行 图图7.2 程序转换程序转换 10/197.2.1 程序的加载程序的加载 绝对装入方式绝对装入方式 :在编译时，如果知道程序将驻留在编译时，如果知道程序将驻留在内存的什么位置，那么，编译程序将产生绝对在内存的什么位置，那么，编译程序将产生绝对地址的目标代码。绝对装入程序按照装入模块中地址的目标代码。绝对装入程序按照装入模块中的地址，将程序和数据装入内存。装入模块被装的地址，将程序和数据装入内存。装入模块被装入内存后，由于程序

7、中的逻辑地址与实际内存中入内存后，由于程序中的逻辑地址与实际内存中的地址完全相同，故不需对程序和数据的地址进的地址完全相同，故不需对程序和数据的地址进行修改。行修改。 11/197.2.1 程序的加载程序的加载可重定位方式可重定位方式 ：0LOAD 1，250036510002500500010000LOAD 1，2500365110001250015000作业地址空间作业地址空间物理地址空间物理地址空间12/197.2.1 程序的加载程序的加载动态运行时装入方式：动态运行时装入方式：在把装入模块装入到在把装入模块装入到内存后，并不立即把装入模块中的相对地址内存后，并不立即把装入模块中的相对地

8、址转换成绝对地址，而是把这种地址转换推迟转换成绝对地址，而是把这种地址转换推迟到程序真正执行时才进行。因此，装入内存到程序真正执行时才进行。因此，装入内存后的所有地址都仍然是相对地址。后的所有地址都仍然是相对地址。 13/197.2.2 程序的链接程序的链接 模块模块A调用调用B；返回返回模块模块B调用调用C；返回返回模块模块C返回返回模块模块B的外部的外部引用引用长度长度L长度长度M长度长度N模块模块AJSR “L”返回返回模块模块BJSR “L+M”返回返回模块模块C返回返回相对地相对地址址0L -1LL+M-1L+ML+M+N-1（a）目标模块目标模块（b）加载模块加载模块14/197.

9、2.2 程序的链接程序的链接链接编辑程序链接编辑程序 ：静态链接静态链接动态链接器动态链接器 ：动态链接动态链接 15/197.3 连续分配方式连续分配方式 连续分配方式指的是为一个用户程序划分连续连续分配方式指的是为一个用户程序划分连续的内存空间，这种分配方式广泛应用于的内存空间，这种分配方式广泛应用于20世纪世纪6070年代，它至今在内存分配方式中还占有一席年代，它至今在内存分配方式中还占有一席之地。我们又可以把连续分配方式进一步分为单一之地。我们又可以把连续分配方式进一步分为单一连续分配、固定分区分配、动态分区分配和可重定连续分配、固定分区分配、动态分区分配和可重定位分区分配四种方式。位

10、分区分配四种方式。 16/197.3.1 单一连续分配单一连续分配 位于位于ROM中操作系中操作系统统用户程序用户程序（a）（b）位于位于RAM中的操作中的操作系统系统ROM中的中的设备驱动设备驱动程序程序用户程序用户程序位于位于RAM中的操作中的操作系统系统（c）用户程序用户程序17/197.3.2 固定分区分配固定分区分配 把内存空间划分为多个分区，这些分区把内存空间划分为多个分区，这些分区的大小在操作系统初始化的时候就确定了，的大小在操作系统初始化的时候就确定了，并且运行时不会改变，这种机制称为固定分并且运行时不会改变，这种机制称为固定分区分配区分配。划分分区的方法：划分分区的方法：分区

11、大小相同分区大小相同 分区大小不同分区大小不同 18/197.3.2 固定分区分配固定分区分配内存管理内存管理 :分区号分区号起始地址起始地址长度长度状态状态进程名进程名内存管理：设置内存分配表内存管理：设置内存分配表内存分配：每个区分配一个进程内存分配：每个区分配一个进程内存回收：简单内存回收：简单缺点：内存利用率不高缺点：内存利用率不高如何记录系统的状况呢？如何记录系统的状况呢？19/197.3.2 固定分区分配固定分区分配分配策略分配策略 分区分区4分区分区3分区分区2分区分区1操作系统操作系统0100K200K400K700K800K多个输入队列多个输入队列分区分区4分区分区3分区分区

12、2分区分区1操作系统操作系统0100K200K400K700K800K单个输入队列单个输入队列（a）有若干独立输入队列的固定式分区有若干独立输入队列的固定式分区（b）只有单个输入队列的固定式分区只有单个输入队列的固定式分区20/197.3.3 动态分区分配动态分区分配 事先不划定分区的大小，根据进程的大小动态事先不划定分区的大小，根据进程的大小动态的为之分配内存空间。的为之分配内存空间。 A操作系统操作系统ABA操作系统操作系统BC操作系统操作系统BCD操作系统操作系统BCD操作系统操作系统CD操作系统操作系统EC（a）（b）（c）（d）（e）（f）（g）内存分配情况随着进程进出内存而变化，阴

13、影表示的区域是未使用的内存内存分配情况随着进程进出内存而变化，阴影表示的区域是未使用的内存操作系统操作系统21/197.3.3 动态分区分配动态分区分配内存管理：内存管理：空闲分区表：在系统中设置一张空闲分区表，记录每空闲分区表：在系统中设置一张空闲分区表，记录每个空闲分区的情况，每个空闲分区占有一个表目。个空闲分区的情况，每个空闲分区占有一个表目。空闲分区链：在每个分区的起始部分，设置一些用于空闲分区链：在每个分区的起始部分，设置一些用于控制分区的信息，以及用于链接各分区所用的前向指控制分区的信息，以及用于链接各分区所用的前向指针；在分区尾部则设置一后向指针，通过前后向链接针；在分区尾部则设

14、置一后向指针，通过前后向链接指针，可以将所有的空闲分区链接成一个双向链。指针，可以将所有的空闲分区链接成一个双向链。22/197.3.3 动态分区分配动态分区分配分配策略分配策略首次适应算法（首次适应算法（First-FitFirst-Fit） 下次适应算法（下次适应算法（Next-FitNext-Fit） 最佳适应算法（最佳适应算法（Best-FitBest-Fit） 最坏适应算法（最坏适应算法（Worst-FitWorst-Fit） 23/197.3.3 动态分区分配动态分区分配空闲区表空闲区表始址始址长度长度标志标志15K23K未分配未分配48K6K未分配未分配60K15K未分配未分配8

15、0K130K0K15K38K48K75K80K210K220K54K60K作业序列：作业序列：P1，3K、P2，20K、P3，10K、P4，100K。24/197.3.4 可重定位分区分配可重定位分区分配 内存紧凑内存紧凑 ：把系统中小的、离散的分区合并成一：把系统中小的、离散的分区合并成一个大的分区的过程。个大的分区的过程。操作系统操作系统用户程序用户程序1用户程序用户程序5用户程序用户程序3用户程序用户程序816K24K30K8K操作系统操作系统用户程序用户程序1用户程序用户程序5用户程序用户程序3用户程序用户程序878K操作系统操作系统用户程序用户程序1用户程序用户程序5用户程序用户程序

16、3用户程序用户程序816K62K（a）初始状态初始状态（b）完全紧凑完全紧凑（c）部分紧凑部分紧凑25/197.3.4 可重定位分区分配可重定位分区分配重定位重定位 ：逻辑地址逻辑地址物理地址物理地址静态重定位静态重定位：在程序被加载到内存之前已经知道了它将在程序被加载到内存之前已经知道了它将要加载到内存的开始地址，这样就可以事先进行地址转要加载到内存的开始地址，这样就可以事先进行地址转换，把相对地址转换成绝对地址。换，把相对地址转换成绝对地址。 动态重定位：作业装入内存后所有的地址仍然是相对地动态重定位：作业装入内存后所有的地址仍然是相对地址，将相对地址转换成绝对地址的过程被推迟到程序指址，

17、将相对地址转换成绝对地址的过程被推迟到程序指令要真正执行时进行。令要真正执行时进行。 26/197.3.4 可重定位分区分配可重定位分区分配LOAD A 200346502001002003001000 +LOAD A 20034650110012001300逻辑地址空间逻辑地址空间物理地址空间物理地址空间重定位寄存器重定位寄存器动态重定位示意图动态重定位示意图相对地址相对地址27/197.3.5 交换和覆盖交换和覆盖 交换交换：把内存中暂时不用的程序和数据换出到外把内存中暂时不用的程序和数据换出到外存上，以释放内存空间，当换到外存的数据再次存上，以释放内存空间，当换到外存的数据再次使用时，再

18、把它们换入内存。使用时，再把它们换入内存。 覆盖：覆盖：是指把程序划分成若干个功能相对独立的是指把程序划分成若干个功能相对独立的程序段，按照其自身的逻辑结构将那些不会同时程序段，按照其自身的逻辑结构将那些不会同时执行的程序段共享同一块内存区域。执行的程序段共享同一块内存区域。 28/197.3.5 交换和覆盖交换和覆盖A（8K）B（8K）C（10K）D（12K）E（4K）F（10K）ABABDACEACF（a）函数调用结构函数调用结构（b）地址分配地址分配图图7.10 程序覆盖程序覆盖29/197.4 基本分页分配方式基本分页分配方式 分区分配方式有很多不足，首先会产分区分配方式有很多不足，首

19、先会产生很多碎片，其次要求一段较大并且连生很多碎片，其次要求一段较大并且连续的空间。续的空间。 针对分区分配的不足，提出针对分区分配的不足，提出把作业离散分配到内存中的思想。把作业离散分配到内存中的思想。30/197.4.1 页面与页表页面与页表 页面页面 ：分页存储管理是将作业的逻辑地址划分分页存储管理是将作业的逻辑地址划分成一系列同等大小的部分，称为成一系列同等大小的部分，称为页页。把可用的。把可用的物理内存也划分成同样大小的连续的部分，称物理内存也划分成同样大小的连续的部分，称之为之为块块或或页框页框。在为进程分配内存空间时，以。在为进程分配内存空间时，以页为单位，每个内存中的块存放一页

20、用户作业。页为单位，每个内存中的块存放一页用户作业。31/197.4.1 页面与页表页面与页表0123456作业的作业的地址空间地址空间内存内存01234567891011121332/197.4.1 页面与页表页面与页表地址结构地址结构 ：页号页号p偏移量偏移量w页号页号p偏移量偏移量w22位位10位位20位位12位位0910310111231（b）页面大小为页面大小为4K（a）页面大小为页面大小为1K33/197.4.1 页面与页表页面与页表页表页表 0123456作业的作业的地址空间地址空间块号块号页号页号页表页表内存内存012345601234567891011121311289541

21、334/197.4.2 地址变换机构地址变换机构 基本地址变换基本地址变换 Load 1, 2500100Load 1, 2500100用户空间用户空间内存空间内存空间35/197.4.2 地址变换机构地址变换机构 基本地址变换基本地址变换 页号页号p页内偏移量页内偏移量w页表始址页表始址页表长度页表长度逻辑地址逻辑地址A越界中断越界中断 +1n0123页表页表页号页号块号块号块号块号块内偏移量块内偏移量图图7.13 页式存储的地址变换机构页式存储的地址变换机构=36/197.4.2 地址变换机构地址变换机构一分页系统，页架的大小为一分页系统，页架的大小为1KB，逻辑地址为逻辑地址为4101（

22、十进制数）页表如下：（十进制数）页表如下： 要求把逻辑地址转换成物理地要求把逻辑地址转换成物理地址。址。012341552039182217请你帮我把逻辑地址请你帮我把逻辑地址3100转换转换为物理地址为物理地址37/197.4.2 地址变换机构地址变换机构快表：快表：介于内存与寄存器之间的存储机制介于内存与寄存器之间的存储机制用来保存正在运行进程的页表的子集用来保存正在运行进程的页表的子集p页表页表地址越界地址越界 l比较比较P=lpp. . .快表快表 b+页号页号p p 页内地址页内地址dPd物理地址物理地址页表地址寄存器页表地址寄存器页表长度寄存器页表长度寄存器逻辑地址逻辑地址38/1

23、97.4.2 地址变换机构地址变换机构多级页表多级页表 0 0111112122121外层页内地址外层页内地址页内位移量页内位移量外层页号外层页号22223131外部页表外部页表第第1页页表页页表页表页表内存内存0120123115116146831115第第n页页表页页表012211614680n311539/197.4.2 地址变换机构地址变换机构外层页号外层页号内层页号内层页号偏移量偏移量0122231PTBR有位，二级地址有位，二级地址有位，页框地址有位，页框地址物理页框号物理页框号偏移量偏移量01231选定的二级页表选定的二级页表一级页表一级页表多级页表多级页表 40/197.4.3

24、 页面大小页面大小 假设平均进程大小是假设平均进程大小是s字节，页面大小是字节，页面大小是p字节，每个字节，每个页表项需要页表项需要e字节。字节。开销开销=es/p + p/2在页面比较小时，第一项（页表大小）大，在页面比在页面比较小时，第一项（页表大小）大，在页面比较大时，第二项（内碎片大小）大。把上边公式两边对较大时，第二项（内碎片大小）大。把上边公式两边对p求求导，我们得到如下方程式：导，我们得到如下方程式：-es/p2 + 1/2=0p=2es对于对于s=128k和每个页表项和每个页表项e=8个字节，最优页面大小为个字节，最优页面大小为1448字节。大部分计算机使用的页面尺寸在字节。大

25、部分计算机使用的页面尺寸在512字节到字节到64K之间。之间。41/197.5 基本分段分配方式基本分段分配方式 引入分段的必要性：引入分段的必要性：逻辑上完整逻辑上完整动态增长动态增长动态链接动态链接信息共享信息共享信息保护信息保护42/197.5.1 段表段表 分段管理逻辑地址结构分段管理逻辑地址结构 段表段表0 0151516163131段号段号段内地址段内地址段号段号012段首址段首址段长度段长度58K20K100K110K260K140K43/197.5.1 段表段表作业空间作业空间（MAIN），），0030K00020K10K15K（X），），1（D），），2（S），），3段表段表

26、30K 40K20K 80K10K 120K15K 150K段长段长 基址基址段号段号0123内存空间内存空间（MAIN），），0（X），），0（D），），0（S），），0040K80K120K150K图图7.17 段表的作用段表的作用44/197.5.2 地址变换机构地址变换机构 段号段号段内地址段内地址段表始址段表始址 段表长度段表长度逻辑地址逻辑地址A=越界中断越界中断 +1K5002006000123基址基址段号段号段长段长用户程序用户程序8292段式存储的地址变换机构段式存储的地址变换机构2100+6K8K92004K45/197.5.3 共享与保护共享与保护 例子：有一个多用户系统

27、，可以容纳例子：有一个多用户系统，可以容纳40个用户，他们个用户，他们都执行一个文本编辑程序，如果文本编辑程序有都执行一个文本编辑程序，如果文本编辑程序有160K的代的代码和码和40K的数据区，则需要：的数据区，则需要：（160+40）*40 =8M 的内存空间，如果的内存空间，如果160K的代码是可的代码是可重入的，则在内存中只保存一个副本就可以了，则需要：重入的，则在内存中只保存一个副本就可以了，则需要：160+40*40=1760K内存空间。内存空间。46/197.5.3 共享与保护共享与保护进程进程1页表页表ed1ed2ed40data1data10ed1ed2ed40data1dat

28、a1021226061702122607180进程进程2页表页表ed1ed2ed40data1data10主存主存editordata1data1data10212260617007180editordata1段长段长16016040基址基址8080380editordata1data14024080420240280380进程进程1进程进程2段表段表（a）分页系统中共享分页系统中共享editor示意图示意图（b）分段系统中共享分段系统中共享editor示意图示意图分页与分段分配方式共享代码段的比较分页与分段分配方式共享代码段的比较47/197.5.3 共享与保护共享与保护分页存储管理和分段存

29、储管理的主要区别如下：分页存储管理和分段存储管理的主要区别如下：页是信息的物理单位，段是信息的逻辑单位；页是信息的物理单位，段是信息的逻辑单位；页的大小是固定的，段的长度是不固定的；页的大小是固定的，段的长度是不固定的；分页的地址空间是一维的，分段的地址空间是二维的；分页的地址空间是一维的，分段的地址空间是二维的；页存在内碎片，段存在外碎片；页存在内碎片，段存在外碎片；48/197.6 虚拟页式分配虚拟页式分配 分页内存分配和分段内存分配方法可以解决分页内存分配和分段内存分配方法可以解决程序在内存中离散存放的问题，但是，这两种方程序在内存中离散存放的问题，但是，这两种方式都要求程序整个装入内存

30、。事实上，很多时候，式都要求程序整个装入内存。事实上，很多时候，程序本身比内存要大得多，那么简单的分页和分程序本身比内存要大得多，那么简单的分页和分段的内存方式就无法解决这个问题了。可以采用段的内存方式就无法解决这个问题了。可以采用虚拟存储器的方法，使用请求分配和置换策略来虚拟存储器的方法，使用请求分配和置换策略来实现存储管理。实现存储管理。49/197.6.1 虚拟存储器虚拟存储器为什么需要虚拟存储器：为什么需要虚拟存储器：程序大于内存程序大于内存程序暂时不执行或运行完是否还要占用内存程序暂时不执行或运行完是否还要占用内存程序的局部性原理程序的局部性原理虚拟存储器的定义虚拟存储器的定义 ：所

31、谓的虚拟存储器是指请所谓的虚拟存储器是指请求调入功能和置换功能，能从逻辑上对内存容求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。量加以扩充的一种存储器系统。 50/197.6.1 虚拟存储器虚拟存储器 虚拟存储器的特点虚拟存储器的特点 ：多次性：一个进程的数据会多次装入内存。多次性：一个进程的数据会多次装入内存。 对换性对换性：允许一个程序在运行过程中从内存换允许一个程序在运行过程中从内存换入和换出。入和换出。 虚拟性：不能改变系统中内存的大小虚拟性：不能改变系统中内存的大小 51/197.6.1 虚拟存储器虚拟存储器虚拟存储器技术需要解决的问题虚拟存储器技术需要解决的问

32、题 ：地址映射地址映射 分配策略分配策略 置换策略置换策略 装载控制装载控制 52/197.6.2 请求分页概念请求分页概念 在进程开始运行之前，不是装入全部页面，在进程开始运行之前，不是装入全部页面，而是装入几个页面，之后根据进程运行的需要，而是装入几个页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面。页面，以便装入新的页面。53/197.6.2 请求分页概念请求分页概念XXXX7X5XXX34061260K-64K56K-60K

33、52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K 8K-12K 4K-8K 0K-4K28K-32K24K-28K20K-24K16K-20K12K-16K 8K-12K 4K-8K 0K-4K虚地址空间虚地址空间物理地址空间物理地址空间 虚页虚页页框页框54/197.6.3 请求分页硬件支持请求分页硬件支持 页表页表 状态位：表明该页是否在内存。状态位：表明该页是否在内存。 访问位：根据访问位来决定淘汰哪页访问位：根据访问位来决定淘汰哪页修改位：查看此页是否在内存中被修改过修改位：查看此

34、页是否在内存中被修改过页号页号物理块号物理块号状态位状态位访问位访问位修改位修改位外存地址外存地址55/197.6.3 请求分页硬件支持请求分页硬件支持缺页中断机构缺页中断机构 ：在请求分页系统中，要访问的页在请求分页系统中，要访问的页不在内存时，便产生了一个缺页中断，请求操作系不在内存时，便产生了一个缺页中断，请求操作系统将该页面调入内存。缺页中断同其它中断一样要统将该页面调入内存。缺页中断同其它中断一样要经历经历CPU环境保护、分析中断原因、转入中断处理环境保护、分析中断原因、转入中断处理程序、恢复程序、恢复CPU环境等步骤。但缺页中断又是一种环境等步骤。但缺页中断又是一种特殊的中断。这种

35、中断在指令执行期间产生和处理特殊的中断。这种中断在指令执行期间产生和处理中断信号。中断信号。 56/197.6.3 请求分页硬件支持请求分页硬件支持地址变换机构地址变换机构 0 1001 00 0 1 1 0 0 10010000010110111.1111.00000125161110 1101 00 0 1 1 0 0 10010状态位状态位页号为页号为5偏移量不变偏移量不变逻辑地址逻辑地址物理地址物理地址57/197.6.4 内存分配策略内存分配策略 内存分配要考虑的问题：内存分配要考虑的问题：分配给一个进程的存储量越小，在任何时候驻留在内存分配给一个进程的存储量越小，在任何时候驻留在内

36、存中的进程数就越多，中的进程数就越多，CPU找到就绪进程的机会就大，从找到就绪进程的机会就大，从而减少了而减少了CPU等待的时间。等待的时间。如果一个进程在内存中的页面数较少，那么，基于局部如果一个进程在内存中的页面数较少，那么，基于局部性原理，它发生缺页的可能性仍然很高。性原理，它发生缺页的可能性仍然很高。给进程分配的物理块超过一定的数目后，由于局部性原给进程分配的物理块超过一定的数目后，由于局部性原理，给该进程分配更多的物理块对该进程的缺页率没有理，给该进程分配更多的物理块对该进程的缺页率没有影响。影响。58/197.6.4 内存分配策略内存分配策略缺页率缺页率缺页率缺页率（a）页尺寸页尺

37、寸（b）分配的物理块数分配的物理块数PNP表示整个进程的大小，表示整个进程的大小，N进程中的总页数进程中的总页数页面大小与物理块数对缺页率的影响页面大小与物理块数对缺页率的影响59/197.6.4 内存分配策略内存分配策略分配策略：分配策略：固定分配策略固定分配策略 可变分配策略可变分配策略 替换策略替换策略局部替换局部替换全局替换全局替换 A0A1A4A3B0B1B2B3B4C1C2局部置换与全局置换局部置换与全局置换A0A1A2A3B0B1B2B3B4C1C267384632974生存时间生存时间（a）置换前置换前（b）局部置换局部置换A0A1A2A3B0B1B2A4B4C1C2（c）全局

38、置换全局置换60/197.6.4 内存分配策略内存分配策略固定分配局部置换固定分配局部置换 可变分配局部置换可变分配局部置换 可变分配全局置换可变分配全局置换 61/197.6.5 内存分配方法内存分配方法 平均分配平均分配 ：所有的空闲物理块按照进程数目平所有的空闲物理块按照进程数目平均分配。均分配。按进程大小比例分配：按进程大小比例分配：考虑优先级的分配算法考虑优先级的分配算法 P= Pini=1bi = PiPm62/197.6.6 缺页处理缺页处理 访问的页在内存访问的页在内存产生缺页中断产生缺页中断内存中有空块内存中有空块从外存调入要访问的页从外存调入要访问的页换出某些暂时不用的页换

39、出某些暂时不用的页运行运行NYNY63/197.7 页面置换算法页面置换算法 当需要的页不在内存时，操作系统必须从内存当需要的页不在内存时，操作系统必须从内存中选择一页并将其移到外存，然后把需要的页调入中选择一页并将其移到外存，然后把需要的页调入内存。在每次缺页时，不同的选择会使系统的效率内存。在每次缺页时，不同的选择会使系统的效率有很大不同。对页面置换算法的研究已经非常深入，有很大不同。对页面置换算法的研究已经非常深入，下面介绍几个重要的算法。这几个算法都是采用下面介绍几个重要的算法。这几个算法都是采用固固定分配局部置换定分配局部置换的内存分配策略。的内存分配策略。64/197.7.1最优页

40、面置换算法最优页面置换算法 当发生缺页时，当前内存中的这几页中，有的页可当发生缺页时，当前内存中的这几页中，有的页可能能以后再也不用以后再也不用了，那么把这个页置换出去是最好了，那么把这个页置换出去是最好的，如果当前内存中的几页都要使用，那么就选择的，如果当前内存中的几页都要使用，那么就选择一个一个最后用到的页最后用到的页并把它置换出去。并把它置换出去。（向后看）（向后看） 65/197.7.1最优页面置换算法最优页面置换算法假定系统为某进程分配了假定系统为某进程分配了三个物理块三个物理块，进程，进程的页面走向如下：的页面走向如下：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0

41、，1，7，0，1现在分配给该作业的现在分配给该作业的三个物理块为空三个物理块为空 ，采用，采用OPT算法，置换过程如何呢？算法，置换过程如何呢？ 66/197.7.1最优页面置换算法最优页面置换算法7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 11 7 0 127 037X X X最佳页面算法（最佳页面算法（OPT）67/197.7.2 先进先出置换算法先进先出置换算法 置换最先进入内存的页置换最先进入内存的页先进先出算法（先进先出算法（FIFO）7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 11 7 0 127 037X X X68

42、/197.7.2 先进先出置换算法先进先出置换算法页面走向页面走向 物理块物理块012301401234000012300014411123011142222301444233缺页缺页YYYYYYYYY页面走向页面走向 物理块物理块0123014012340000000123401111111234012222223401233333401234缺页缺页YYYYYYYYYY69/197.7.3最近最少使用置换算法最近最少使用置换算法 最近最少使用（最近最少使用（LRU）置换算法的思想是当发置换算法的思想是当发生缺页时，系统会选择当前内存页面中没有被使用生缺页时，系统会选择当前内存页面中没有被使

43、用时间最久的那一页，即最少使用的那一页，并将它时间最久的那一页，即最少使用的那一页，并将它置换出去。置换出去。 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 11 7 0 127 037X X X70/197.7.3最近最少使用置换算法最近最少使用置换算法最近最久未用算法（最近最久未用算法（LRU）硬件支持硬件支持 R实页实页R7R6R5R4R3R2R1R0101010010210101100300000100401101011511010110600101011700000111801101101移位寄存器移位寄存器 R = Rn-1Rn-2Rn-3R2R1R0

44、71/197.7.4 用软件模拟用软件模拟LRU算法算法 最不常用（最不常用（NFU）算法：该算法将每个页面与算法：该算法将每个页面与一个软件记数器相联，记数器的初值为一个软件记数器相联，记数器的初值为0。每次时。每次时钟中断时，由操作系统扫描内存中的所有的页面，钟中断时，由操作系统扫描内存中的所有的页面，将每个页面的将每个页面的R位（它的值是位（它的值是0或或1）加到它的记数）加到它的记数器上。实际上这个记数器是试图跟踪各个页面的访器上。实际上这个记数器是试图跟踪各个页面的访问频繁程度。发生页面失效时，计数器最小的页面问频繁程度。发生页面失效时，计数器最小的页面被淘汰。被淘汰。这样做有没有问

45、题呢？这样做有没有问题呢？对对NFU进行一个简单的修改来模拟进行一个简单的修改来模拟LRU。首先，在首先，在R位被加进来之前先将记数器右移一位；位被加进来之前先将记数器右移一位；然后将然后将R位加到记数器的最左端的位。位加到记数器的最左端的位。72/197.7.4 用软件模拟用软件模拟LRU算法算法(a)1 0 1 0 1 11 1 0 0 1 01 1 0 1 0 11 0 0 0 1 00 1 1 0 0 01 0 0 0 0 0 0 00 0 0 0 0 0 0 01 0 0 0 0 0 0 00 0 0 0 0 0 0 01 0 0 0 0 0 0 01 0 0 0 0 0 0 01

46、1 0 0 0 0 0 01 0 0 0 0 0 0 00 1 0 0 0 0 0 00 0 0 0 0 0 0 01 1 0 0 0 0 0 00 1 0 0 0 0 0 01 1 1 0 0 0 0 01 1 0 0 0 0 0 00 0 1 0 0 0 0 01 0 0 0 0 0 0 00 1 1 0 0 0 0 01 0 1 0 0 0 0 01 1 1 1 0 0 0 00 1 1 0 0 0 0 00 0 0 1 0 0 0 00 1 0 0 0 0 0 01 0 1 1 0 0 0 00 1 0 1 0 0 0 00 1 1 1 1 0 0 01 0 1 1 0 0 0 01

47、0 0 0 1 0 0 00 0 1 0 0 0 0 00 1 0 1 1 0 0 00 0 1 0 1 0 0 0页面页面012345页面页面05的的R位，位，时钟嘀嗒时钟嘀嗒0页面页面05的的R位，位，时钟嘀嗒时钟嘀嗒1页面页面05的的R位，位，时钟嘀嗒时钟嘀嗒2页面页面05的的R位，位，时钟嘀嗒时钟嘀嗒3页面页面05的的R位，位，时钟嘀嗒时钟嘀嗒4(b)(c)(d)(e)用软件模拟用软件模拟LRU的老化算法，图中所示是的老化算法，图中所示是6个页面个页面5个时钟嘀嗒的情况个时钟嘀嗒的情况73/197.7.5 时钟算法时钟算法 时钟算法需要给每个物理块增加一个时钟算法需要给每个物理块增加一

48、个附加位附加位，称为称为使用位使用位u。当某一页装入内存，该物理块的使当某一页装入内存，该物理块的使用位设为用位设为1；当该物理块被使用时，它的使用位也；当该物理块被使用时，它的使用位也设为设为1。对于页面置换算法，把用于替换的物理块。对于页面置换算法，把用于替换的物理块集合看作是一个循环缓冲区，并且有一个指针与之集合看作是一个循环缓冲区，并且有一个指针与之关联。当需要进行页面置换时，如果指针所在的页关联。当需要进行页面置换时，如果指针所在的页面面u=0，则将它置换，然后把指针指向下一个物理则将它置换，然后把指针指向下一个物理块。否则，把该块的使用位置为块。否则，把该块的使用位置为0，然后跳过

49、该块，然后跳过该块继续扫描，直到找到一个继续扫描，直到找到一个u=0的物理块。的物理块。 74/197.7.5 时钟算法时钟算法页面页面12使用位使用位=1页面页面2使用位使用位=1页面页面36使用位使用位=0页面页面6使用位使用位=1页面页面23使用位使用位=1页面页面25使用位使用位=1页面页面11使用位使用位=0页面页面8使用位使用位=0页面页面12使用位使用位=0页面页面2使用位使用位=1页面页面9使用位使用位=1页面页面6使用位使用位=0页面页面23使用位使用位=1页面页面25使用位使用位=1页面页面11使用位使用位=0页面页面8使用位使用位=0(a)页面置换前状态页面置换前状态(b

50、)页面置换后状态页面置换后状态0123456775/197.7.6 改进改进Clock算法算法 在在Clock算法的基础上再增加一个附加位修算法的基础上再增加一个附加位修改位改位w。具有具有2个附加位的物理块中的页具有个附加位的物理块中的页具有4种情况：种情况：最近未访问过，也未被修改过（最近未访问过，也未被修改过（u=0，w=0）。）。最近未访问过，但被修改过（最近未访问过，但被修改过（u=0，w=1）。）。最近访问过，但没有被修改过（最近访问过，但没有被修改过（u=1，w=0）。）。最近访问过，也修改过（最近访问过，也修改过（u=1，w=1）。）。76/197.7.6 改进改进Clock算

51、法算法改进型时钟算法如下：改进型时钟算法如下：从指针当前位置开始扫描，在这次扫描过程中对使用位从指针当前位置开始扫描，在这次扫描过程中对使用位的值不做任何修改，找到一个的值不做任何修改，找到一个u=0，w=0的物理块，进的物理块，进行置换。行置换。如果第一步失败，则查找如果第一步失败，则查找u=0，w=1的块，遇到的第一的块，遇到的第一个这样的物理块，则把该块中的页置换出去，同时把扫个这样的物理块，则把该块中的页置换出去，同时把扫描过程中的遇到的描过程中的遇到的u=1的块设为的块设为u=0。如果前两步都失败，在重新执行第一步、第二步，这样如果前两步都失败，在重新执行第一步、第二步，这样一定会找

52、到一个合适的页替换出去。一定会找到一个合适的页替换出去。77/197.7.6 改进改进Clock算法算法块号块号页号页号访问位访问位修改位修改位571120108111改进型改进型Clock置换算法置换算法7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 178/197.7.7 工作集模型工作集模型 一个进程当前正在使用的页面的集合称为它的一个进程当前正在使用的页面的集合称为它的工作集（工作集（Working set）。）。如果在内存中装入的是如果在内存中装入的是整个工作集，进程的运行就不会产生很多缺页。若整个工作集，进程的运行就不会产生很多缺页。若分配给进程的物理块

53、太少，无法容纳下整个工作集，分配给进程的物理块太少，无法容纳下整个工作集，进程的运行会产生大量的缺页。进程的运行会产生大量的缺页。 79/197.7.7 工作集模型工作集模型工作集大小示意图工作集大小示意图瞬变瞬变 稳定稳定 瞬变瞬变瞬变瞬变瞬变瞬变稳定稳定稳定稳定稳定稳定时间时间工作集大小工作集大小每个进程在给定的时间每个进程在给定的时间t都有一个页面的工作集都有一个页面的工作集W（t，），），该工作集被定义为这个进程在时间（该工作集被定义为这个进程在时间（t-，t）中引用的页面的集合。中引用的页面的集合。 80/197.7.7 工作集模型工作集模型工作集模型中的存储器管理策略遵循下面两条规

54、则：工作集模型中的存储器管理策略遵循下面两条规则：每次引用时，会确定当前的工作集，而且只有属于工作每次引用时，会确定当前的工作集，而且只有属于工作集的页面才能留在内存。集的页面才能留在内存。当且仅当进程的整个当前工作集都驻留在内存中时，一当且仅当进程的整个当前工作集都驻留在内存中时，一个进程才可以运行。个进程才可以运行。 81/197.7.7 工作集模型工作集模型Windows 2000 实现了一种页面置换机制，它结合了工实现了一种页面置换机制，它结合了工作集模型和时钟算法。作集模型和时钟算法。这种置换是局部的，系统为每个进程维护了一个当前工作集。系统这种置换是局部的，系统为每个进程维护了一个

55、当前工作集。系统指定了一个最小尺寸工作集和一个最大尺寸工作集。最小尺寸的值指定了一个最小尺寸工作集和一个最大尺寸工作集。最小尺寸的值一般是一般是2050个物理块；最大尺寸的值一般是个物理块；最大尺寸的值一般是45345个物理块。个物理块。每次缺页时，会通过把引用到的页面添加到集合中而增加进程的工每次缺页时，会通过把引用到的页面添加到集合中而增加进程的工作集，直至达到最大值。此时，如果有新的页面请求，必须要从工作集，直至达到最大值。此时，如果有新的页面请求，必须要从工作集中移出一个页面。作集中移出一个页面。从工作集中移出哪个页面，使用了模拟从工作集中移出哪个页面，使用了模拟LRU算法和时钟算法的

56、一个算法和时钟算法的一个变种。每个物理块有一个使用位变种。每个物理块有一个使用位u和一个计数器和一个计数器count。每当访问每当访问到页面时，使用位被硬件置位。当在工作集中寻找一个要移出的页到页面时，使用位被硬件置位。当在工作集中寻找一个要移出的页面时，工作集管理器会扫描工作集中的页面的使用位。每次扫描过面时，工作集管理器会扫描工作集中的页面的使用位。每次扫描过程中，它执行下面的操作：程中，它执行下面的操作：if (u=1) u = 0 ; count =0 ; else count +;在扫描结束时，它会移出在扫描结束时，它会移出count值最大的页面。因此，只要一个页值最大的页面。因此，

57、只要一个页面经常被引用，它的面经常被引用，它的count值将比较小，而不会被移出。值将比较小，而不会被移出。82/197.8 虚拟段式分配虚拟段式分配 虚拟段式分配又称为请求分段，它类似于虚虚拟段式分配又称为请求分段，它类似于虚拟页式分配，在程序装入时，只需调入几个分拟页式分配，在程序装入时，只需调入几个分段而不是所有的分段。随着程序的运行，如果段而不是所有的分段。随着程序的运行，如果需要访问的段不在内存，可以请求操作系统把需要访问的段不在内存，可以请求操作系统把需要的段调入内存。需要的段调入内存。 83/197.8.1 请求分段中的硬件支持请求分段中的硬件支持 段段号号段段长长中断中断位位段

58、基段基址址外存外存地址地址引用引用位位修改修改位位保护保护位位增补增补位位中断位：标识该段在内存还是外存中断位：标识该段在内存还是外存 外存地址：标识该段处于外存的地址外存地址：标识该段处于外存的地址引用位：标识一段被使用的频繁程度引用位：标识一段被使用的频繁程度当一段在内存中被修改，就需要设置该位当一段在内存中被修改，就需要设置该位保护位：记录段的存取控制信息保护位：记录段的存取控制信息 增补位：请求分段管理段表中特有的一项。段的长度是增补位：请求分段管理段表中特有的一项。段的长度是变化的，当一段的长度在内存中改变后，如果被置换出变化的，当一段的长度在内存中改变后，如果被置换出去，原位置可能

59、无法存放。去，原位置可能无法存放。84/197.8.2 地址变换机构地址变换机构 请求分段存储管理的地址变换与纯分段系请求分段存储管理的地址变换与纯分段系统的地址变换基本相同，不同之处是要通过中统的地址变换基本相同，不同之处是要通过中断位来判断一段是否在内存。如果在内存，根断位来判断一段是否在内存。如果在内存，根据段号查找段表中对应的段的起始地址据段号查找段表中对应的段的起始地址段段基址。段基址与段内地址的和即为物理地址。基址。段基址与段内地址的和即为物理地址。如果不在内存，发出一个缺段中断，请求操作如果不在内存，发出一个缺段中断，请求操作系统把段调入内存。系统把段调入内存。 85/197.8

60、.3 缺段中断缺段中断 阻塞请求进程阻塞请求进程虚段虚段s不在内存不在内存在内存中有合在内存中有合适的空闲区吗适的空闲区吗从外存读入段从外存读入段s修改段表及内存空闲区链修改段表及内存空闲区链唤醒请求进程唤醒请求进程内存区空闲容量内存区空闲容量总和能满足吗总和能满足吗空闲区紧凑，以形空闲区紧凑，以形成一个合适的空闲成一个合适的空闲区区淘汰一个或几个内存中的淘汰一个或几个内存中的段，形成一个合适空闲区段，形成一个合适空闲区返回返回请求分段系统中的缺段中断处理过程请求分段系统中的缺段中断处理过程yynn86/197.9 段页式分配方式段页式分配方式 分段和分页都有各自的优势。分页对程序员分段和分页