操作系统第4章

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 请求分段存储管理方式请求分段存储管理方式 存储层次结构存储层次结构外存(secondary storage)DOS核心命令处理程序内存(primary storage)高速缓存(cac

2、he)寄存器(register)速速度度容容量量小小大大底底高高基本概念1.1.定位（存储分配）定位（存储分配）：为具体的程序和数为具体的程序和数据等分配存储单元或存储区工作。据等分配存储单元或存储区工作。2.2.映射：映射：把逻辑地址转换为相应的物理地把逻辑地址转换为相应的物理地址的过程。址的过程。创建进程时，由于创建进程时，由于程序的逻辑地址程序的逻辑地址与分配到内存物理地址不一致与分配到内存物理地址不一致, 而而CPU执行指令时，是按物理地址进执行指令时，是按物理地址进行的，所以要进行地址转换行的，所以要进行地址转换。? ?为何要进行地址映射为何要进行地址映射程序的装入和链接程序的装入和

3、链接 从用户的源程序进入系统到相应程从用户的源程序进入系统到相应程序在机器上运行，所经历的主要处理阶序在机器上运行，所经历的主要处理阶段有段有 ， ， 和和 。运行阶段运行阶段编译阶段编译阶段装入阶段装入阶段链接阶段链接阶段将用户源代码将用户源代码编译成若干个编译成若干个目标模块目标模块将装入模块将装入模块装入内存装入内存将一组目标模块及他将一组目标模块及他们需要的库函数链接们需要的库函数链接在一起形成装入模块在一起形成装入模块要使程序运行，必须为之先建立要使程序运行，必须为之先建立进程进程。创建进。创建进程的第一件事是将程序和数据装入内存。程的第一件事是将程序和数据装入内存。4.1 程序的装

4、入和链接程序的装入和链接库库汇编汇编编译编译主主子子1子子2目标模块目标模块链接程序链接程序装入模块装入模块库库主主子子1子子2装入程序装入程序内存内存库库主主子子1子子2地址空间的概念地址空间的概念l物理（绝对）地址物理（绝对）地址指令在指令在内存中的真实地址，内存中存储单元的内存中的真实地址，内存中存储单元的地址。地址。l逻辑（相对）地址逻辑（相对）地址被链接装配（或汇编、编译）后的目标模块所被链接装配（或汇编、编译）后的目标模块所限定的地址的集合；限定的地址的集合；其首地址为其首地址为0 0，其余指令中的地址都相对于首地，其余指令中的地址都相对于首地址而编址址而编址。物理地址物理地址 内

5、存内存000000000100002.0100001FFF主主子子1子子2主主子子1子子2逻辑地址逻辑地址 装入模块装入模块000.FFF主主子子1子子2相对地址相对地址源程序源程序/单个目标模块单个目标模块0005FF0005FF0005FFGoto L1L1：源程序编译Goto 2目标代码0123名空间地址空间装入Goto a2内存(运行程序)aa1存储空间a2逻辑地址、物理地址和地址映射逻辑地址、物理地址和地址映射4.1.1 程序的装入程序的装入l就是把链接好的装入模块装入就是把链接好的装入模块装入“内存内存”。l装入方式装入方式绝对装入：单道（任务）绝对装入：单道（任务）可重定位装入（

6、静态重定位）可重定位装入（静态重定位）动态运行时装入（动态重定位）动态运行时装入（动态重定位）l提示：通常链接、装入程序是一体的。提示：通常链接、装入程序是一体的。1. 绝对装入方式绝对装入方式u装入模块的地址与内存实际地址完全相同装入模块的地址与内存实际地址完全相同u要求：要求：编译程序直接产生绝对地址，或用户使用绝编译程序直接产生绝对地址，或用户使用绝对地址编程对地址编程用户了解程序在内存中的存放位置用户了解程序在内存中的存放位置用户控制内存使用情况用户控制内存使用情况适合于单道适合于单道程序系统：程序系统：例如例如DOSl装入模块中使用从装入模块中使用从0开始的相对地址开始的相对地址l装

7、入时装入时由系统分配内存空间由系统分配内存空间进行重定位进行重定位 完成映射完成映射-装入模块中相对地址变换为绝对地址装入模块中相对地址变换为绝对地址 指令中的地址也要进行重定位指令中的地址也要进行重定位2. 可重定位装入方式可重定位装入方式装入时的地址变换装入时的地址变换l重定位重定位 概念：将程序装入内存时，修改程序中所有概念：将程序装入内存时，修改程序中所有与地址有关的项。与地址有关的项。 逻辑地址变换为物理地址。逻辑地址变换为物理地址。l可重定位装入：可重定位装入：静态重定位静态重定位，地址变换是在装，地址变换是在装入时一次性完成。入时一次性完成。3. 动态运行时装入方式动态运行时装入

8、方式u采用采用动态重定位动态重定位u装入模块装入内存后，并不立即把装入模块中装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址的相对地址转换为绝对地址u在程序执行时将相对地址转换为绝对地址在程序执行时将相对地址转换为绝对地址u允许程序在内存中移动允许程序在内存中移动4.1.2 程序的链接程序的链接模块模块ACall B;Return;0L-1模块模块BCall C;Return;0M-1模块模块C;Return;0N-1链接链接模块模块ACall B;Return;0L-1模块模块BCall C;Return;LL+M-1模块模块C;Return;L+ML+M+N-1装入模块装入

9、模块l链接：链接：把一个程序相关的一组目标模块和系统调用把一个程序相关的一组目标模块和系统调用模块（库函数）链接形成一个整体模块（库函数）链接形成一个整体装入装入模块的过程。模块的过程。l具体工作：具体工作：对相对地址的修改；变换外部调用符号。对相对地址的修改；变换外部调用符号。l链接方式：链接方式：静态链接静态链接装入时动态链接装入时动态链接运行时动态链接运行时动态链接1、静态链接、静态链接l定义：定义：进程执行前将装入模块装入时，链接所有的进程执行前将装入模块装入时，链接所有的目标模块目标模块先链接后装入先链接后装入l具体工作具体工作对相对地址修改对相对地址修改变换外部调用标号变换外部调用

10、标号l静态链接静态链接 装入模块时完整的包括所有的目标模块 连接后装入模块 ACALL B；Return；0L1模块 BCALL C；Return；0M1模块 CReturn；0N10模块 AJSR“L”Return；L1模块 BJSR“L+M”Return；L+ML+M+N1模块 CReturn；(a) 目标模块(b) 装入模块;LL+M1修改地址修改地址变换外部调用标号：变换外部调用标号：转移到子程序转移到子程序例例1：静态链接：静态链接目标模块目标模块Printf (“OK”)0主模块Void printf() 0库模块Printf (“OK”)Void printf() 01200H装

11、入模块装入模块库主JSR 1200H内存内存装入装入11FFH2. 装入时动态链接装入时动态链接u 装入模块并不包含所有目标模块装入模块并不包含所有目标模块u 由系统装入操作在装入同时找到需要的其由系统装入操作在装入同时找到需要的其他模块，并链接他模块，并链接u 特点：特点： 目标模块目标模块“减肥减肥”， 便于共享。便于共享。便于修改和更新单个目标模块而不需打便于修改和更新单个目标模块而不需打开整个装入模块。开整个装入模块。 例例2：装入时动态链接：装入时动态链接目标模块目标模块主主模模块块库库模模块块装入模块装入模块内存内存装入装入3. 运行时动态链接运行时动态链接 u装入模块不完整，装入

12、时也没有装入所有的模块装入模块不完整，装入时也没有装入所有的模块u运行时根据需要，找到所需模块，装入，链接，再执行运行时根据需要，找到所需模块，装入，链接，再执行需要动态装入的支持需要动态装入的支持u装入后链接装入后链接u特点：特点： 将对某些模块的链接推迟到执行时才执行，节约将对某些模块的链接推迟到执行时才执行，节约内存空间。内存空间。printf( “ OK” );printf( “ OK” );库模块库模块void printf()00void printf()printf( “ OK” );执行执行33600Hcall 33600H内存内存目标模块目标模块装入模块装入模块例例3：运行时

13、动态链接：运行时动态链接主主模模块块4.2 连续分配方式连续分配方式4.2.1 单一连续分配单一连续分配 n内存分为系统区和用户区两部分内存分为系统区和用户区两部分n系统区：仅提供给系统区：仅提供给OS使用使用n用户区：仅允许一个用户程序占据整个用户区。用户区：仅允许一个用户程序占据整个用户区。 系统参数区系统参数区BIOS CCPBDOS系统区系统区系统区系统区单一连续分配的存储保护单一连续分配的存储保护n存贮保护：保护系统区不被用户错误占用存贮保护：保护系统区不被用户错误占用（1）设置界限寄存器：）设置界限寄存器：判别地址是否超界判别地址是否超界（2）把）把CPU工作状态分为工作状态分为“

14、管管”态和态和“目目”态态管态：管态：CPU只访问只访问OS区区目态：只访问用户区目态：只访问用户区4.2.2 固定分区分配固定分区分配 1. 划分分区的方法划分分区的方法 分区大小相等，分区大小相等， 即使所有的内存分区大小即使所有的内存分区大小相等。相等。 (2) 分区大小不等。分区大小不等。 每个分区装入一道作业，同时可装入多每个分区装入一道作业，同时可装入多道作业道作业系统区系统区分区分区 1分区分区 4分区分区 5分区分区 2分区分区 3区号区号/键键大小大小位置位置状态状态18 K512K正使用正使用232 K520K正使用正使用332 K552K未使用未使用4128 K584K未

15、使用未使用5512 K712K正使用正使用系统区系统区作业作业 3分区分区 4作业作业 2作业作业 1分区分区 32. 内存分配内存分配 固定分区使用表固定分区使用表n内存分配性能评价的一类重要指标内存分配性能评价的一类重要指标内零头：内零头：p分配给用户但用户没有使用的空间分配给用户但用户没有使用的空间外零头：外零头：p没有分配但因太小而无法分配的空间没有分配但因太小而无法分配的空间单一连续分配有较大的内零头单一连续分配有较大的内零头分区分配有小于一个分区的内零头分区分配有小于一个分区的内零头 n引入原因引入原因固定分区分配会造成大量的固定分区分配会造成大量的内零头内零头n基本思想基本思想按

16、需分配，仅将进程需要的大小分配出去，按需分配，仅将进程需要的大小分配出去，其余的仍然留在空白内存表里。其余的仍然留在空白内存表里。4.2.3 动态分区分配动态分区分配 （可变分区分配）（可变分区分配）1.动态分区分配中的数据结构动态分区分配中的数据结构 空闲分区表。空闲分区表。 (2) 空闲分区链。空闲分区链。 图图 4-5 空闲链结构空闲链结构 前向指针N20N个字节可用后向指针N202. 分区分配算法分区分配算法 顺序搜索法顺序搜索法首次适应算法首次适应算法FF。 循环首次适应算法。循环首次适应算法。最佳适应算法。最佳适应算法。 最适合自己的分区最适合自己的分区最坏适应算法。每次挑最大的空

17、闲分区。最坏适应算法。每次挑最大的空闲分区。（1）首次适应算法）首次适应算法FF第一次遇到可装入程序的分区就分配的算法第一次遇到可装入程序的分区就分配的算法步骤：步骤：（1）将空白分区按地址）将空白分区按地址递增顺序链接递增顺序链接（2）从）从链首开始查找链首开始查找适合的分区适合的分区（3）从选中的分区中分出所需的大小，其）从选中的分区中分出所需的大小，其余部分仍留在空白分区链表里余部分仍留在空白分区链表里特点：优先分配内存中低地址部分特点：优先分配内存中低地址部分优点：简单优点：简单缺点：在低地址部分会积累大量缺点：在低地址部分会积累大量外零头外零头（2）循环首次适应）循环首次适应l在在F

18、F基础上，均衡利用整个内存空间基础上，均衡利用整个内存空间l实现：实现：将空白区链表首尾相接形成环形，将空白区链表首尾相接形成环形，每次查找从上一次停留的位置开始每次查找从上一次停留的位置开始l特点特点可以均衡利用高址和低址内存可以均衡利用高址和低址内存减慢了外零头形成的速度减慢了外零头形成的速度“饼干越掰越碎饼干越掰越碎”，当需要大分区时，当需要大分区时可能无分区可用可能无分区可用 （3）最佳适应）最佳适应(Best Fit)n选取最适合大小的空白分区选取最适合大小的空白分区空白分区空白分区按分区大小递增排列按分区大小递增排列遇到的第一个可分配空白分区就分配遇到的第一个可分配空白分区就分配n

19、特点：特点：优点：保证总有大分区可分配（排在后面）优点：保证总有大分区可分配（排在后面）缺点：缺点：效率不高，排在前面的分区不断变小，效率不高，排在前面的分区不断变小，能被分出去的概率也就越来越低能被分出去的概率也就越来越低外零头形成速度快外零头形成速度快X（4）最差适应）最差适应(Worst Fit)n选取分区中最大的一个选取分区中最大的一个最不适合的最不适合的空白分区按大小空白分区按大小递减递减排列排列遇到的第一个可分配的空白分区就分配遇到的第一个可分配的空白分区就分配n特点：特点：优点：查找效率显著提高优点：查找效率显著提高缺点：大作业容纳能力会下降缺点：大作业容纳能力会下降二、分类搜索

20、法（快速适应算法）二、分类搜索法（快速适应算法） 将空闲分区按大小进行分类，同类分区设一将空闲分区按大小进行分类，同类分区设一个链表。再设立一个索引表，每一表项对应一个个链表。再设立一个索引表，每一表项对应一个分区类型并记录指向该类分区链表表头的指针。分区类型并记录指向该类分区链表表头的指针。例题例题1： 设某一操作系统采用可变分区的存储管理方设某一操作系统采用可变分区的存储管理方式，用户区内存为式，用户区内存为512KB，空闲块链入空闲块表，空闲块链入空闲块表，分配时截取空闲块的前半部分（小地址部分）。分配时截取空闲块的前半部分（小地址部分）。初始时用户区全部空闲，分别采用首次适应算法初始时

21、用户区全部空闲，分别采用首次适应算法与最佳适应算法求出在执行了如下的申请、释放与最佳适应算法求出在执行了如下的申请、释放操作序列后的内存情况。操作序列后的内存情况。（1）申请）申请300KB （2）申请）申请100KB （3）释放）释放300KB （4）申请）申请150KB （5）申请）申请50KB （6）申请）申请90KB （7）申请）申请80KB首次适应算法：首次适应算法：最佳适应算法：最佳适应算法：从头开始查表检索完否？m.size u.size?m.size u.sizesize?从该分区中划出u.size大小的分区将该分区分配给请求者修改有关数据结构返回返回继续检索下一个表项将该分区

22、从链中移出YNNYYN3. 分区分配操作流程分区分配操作流程为了减少外零头，为了减少外零头，设置常量设置常量size，限制，限制划出小于划出小于size大小的大小的分区分区 2) 回收内存回收内存 图 47 内存回收时的情况 4.2.4 动态可重定位分区分配动态可重定位分区分配OS区区Job2Job4Job3Job1Job5Job6Job7外零头外零头OS区区Job2Job4Job3Job1Job5Job6Job7紧凑紧凑移动后如何实现地址变换？移动后如何实现地址变换？处理机一侧 存储器一侧 作业J 内存365LOAD 1, 2500500025001000365LOAD 1, 2500150

23、001250010000110002500相对地址10000重定位寄存器2. 动态重定位的实现动态重定位的实现 3. 动态重定位分区分配算法动态重定位分区分配算法 请求分配u.size分区检索空闲分区链(表)找到大于 u.size的可用区否?按动态分区方式进行分配修改有关的数据结构返回分区号及首批空闲分区总和 u.size?进行紧凑形成连续空闲区修改有关的数据结构否是无法分配返回否n紧凑时机紧凑时机当存储分配找不到满足作业需求的空间时，当存储分配找不到满足作业需求的空间时，进行紧凑生成一个足够大的分区进行紧凑生成一个足够大的分区当回收区找不到与之相邻的空白区时，启动当回收区找不到与之相邻的空白

24、区时，启动紧凑紧凑4.2.5 对换对换(Swapping) 1. 对换的引入对换的引入 n对换：把内存中暂时不能运行的进程或者暂时不用对换：把内存中暂时不能运行的进程或者暂时不用的程序和数据，挂起以腾出足够的内存空间，再把已的程序和数据，挂起以腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调具备运行条件的进程或进程所需要的程序和数据，调入内存。入内存。n对换是对换是提高内存利用率提高内存利用率的有效措施。的有效措施。 （1）整体对换）整体对换中级调度中级调度（2）页面（分段）对换）页面（分段）对换虚拟存储技术虚拟存储技术2. 对换的类型对换的类型 02. 对换空间的管理

25、对换空间的管理n对换空间只占磁盘一小部分，但是对换操作频率很高对换空间只占磁盘一小部分，但是对换操作频率很高n用空闲分区表或空闲分区链管理外存对换区中的空闲用空闲分区表或空闲分区链管理外存对换区中的空闲盘块。盘块。n 在空闲分区表中的每个表目中应包含两项：对换区在空闲分区表中的每个表目中应包含两项：对换区的首址（盘块号），对换区大小（和盘块数）的首址（盘块号），对换区大小（和盘块数）3. 进程的换出与换入进程的换出与换入 (1) 进程的换出。进程的换出。 (2) 进程的换入。进程的换入。 4.3 基本分页存储管理方式基本分页存储管理方式 4.3.1 页面与页表页面与页表 1. 页面页面 1)

26、页面和物理块页面和物理块 2) 页面大小页面大小01234567891110内存内存第第0页页第第1页页第第2页页第第3页页第第4页页第第5页页第第6页页用户作业用户作业02K-1第第2页页（页长（页长2K）02K-14号页架号页架（块长（块长2K）物理块物理块页内碎片页内碎片01234567891110内存内存第第0页页第第1页页第第2页页第第3页页第第4页页第第5页页第第6页页用户作业用户作业第第0页页第第1页页第第2页页第第3页页第第4页页第第5页页第第6页页01234567891110内存内存第第0页页第第1页页第第2页页第第3页页第第4页页第第5页页第第6页页用户作业用户作业块号块号

27、页号页号1051169453327120页表页表第第0页页第第1页页第第2页页第第3页页第第4页页第第5页页第第6页页2. 页表页表 3. 地址结构地址结构 分页地址中的地址结构如下：分页地址中的地址结构如下： 页号页号P位移量位移量W3112110设每页大小为设每页大小为4KB，内存大小为，内存大小为4G，则地址结构为：，则地址结构为：页号页号P位移量位移量W页号页号P位移量位移量W物理块号物理块号P页内地址页内地址d逻辑地址逻辑地址物理地址物理地址4.3.2 地址变换机构地址变换机构 1. 基本的地址变换机构基本的地址变换机构 图图 4-12 分页系统的地址变换机构分页系统的地址变换机构

28、页表寄存器页表寄存器页表始址页表长度 页号(3) 页内地址 逻辑地址逻辑地址L L越界中断越界中断1块号块号b页表页表页号页号012页内地址页内地址b物理地址物理地址3执行某进程时，将其页表信息执行某进程时，将其页表信息从从PCB中取出放入这里中取出放入这里n页表存于内存中，因此要获得所需数据页表存于内存中，因此要获得所需数据需需访问两次内存访问两次内存。n快表：将当前访问的若干页表项存于一快表：将当前访问的若干页表项存于一个具有并行查询能力的特殊高速缓冲寄个具有并行查询能力的特殊高速缓冲寄存器中，即快表中，以提高访问速度。存器中，即快表中，以提高访问速度。2. 具有快表的地址变换机构具有快表

29、的地址变换机构 图 413 具有快表的地址变换机构 页表寄存器页表始址页表长度页号页内地址逻辑地址L越界中断块号b页表页号页号输入寄存器块号bb快表d物理地址例题例题2： 在某个分页管理系统中，某一个作业有在某个分页管理系统中，某一个作业有4个页面，个页面，被分别装入到主存的第被分别装入到主存的第3，4，6，8页架中，假定页页架中，假定页面和页架大小均为面和页架大小均为1024字节，当作业在字节，当作业在CPU上运行上运行时，执行到其地址空间第时，执行到其地址空间第500号处遇到一条传送命令号处遇到一条传送命令MOV 2100，3100请用地址变换图计算出请用地址变换图计算出MOV指令中两个操

30、作数的物指令中两个操作数的物理地址。理地址。 页面大小为页面大小为10241024字节，用二进制表示为字节，用二进制表示为2 21010： 表示表示0 09 9位为页内地址。位为页内地址。页号页号 逻辑地址逻辑地址21002100页号为页号为2 2，页内位移为，页内位移为5252 逻辑地址逻辑地址31003100页号为页号为3 3，页内位移为，页内位移为2828 转换过程如图转换过程如图3.53.5所示：所示：2100逻辑地址为：逻辑地址为：100000110100物理地址为：物理地址为：11000001101003100逻辑地址为：逻辑地址为：110000011100物理地址为：物理地址为：

31、10000000011100例题例题3： 假定某操作系统存储器采用分页管理，某作业假定某操作系统存储器采用分页管理，某作业在存储器中的页表为：在存储器中的页表为： 假定该作业的代码长度为假定该作业的代码长度为320字，每页长为字，每页长为32字，字，现有逻辑地址（八进制）为：现有逻辑地址（八进制）为：101，204，576，若能，若能翻译成相应的物理地址，则说明翻译过程；若不能翻译成相应的物理地址，则说明翻译过程；若不能翻译，请说明原因。翻译，请说明原因。页号页号0123456789页架页架号号6432000000状态状态1111000000该页不在内存中该页不在内存中 页面大小页面大小32为

32、为25，所以逻辑地址结构中低，所以逻辑地址结构中低5位为页内位移，其余高位为页号。位为页内位移，其余高位为页号。(101)8(001000001)2 页号为页号为2，相应块号为，相应块号为3，物，物理地址为理地址为(011000001)2(301) (204)8(010000100)2 页号为页号为4，状态为，状态为“0”，说，说明此页当时不在内存中，需要产生一次缺页中断，明此页当时不在内存中，需要产生一次缺页中断，按页面更换策略进行页面置换。按页面更换策略进行页面置换。(576)8(101111110)2 页号为页号为11，超出了页表的范，超出了页表的范围，不能翻译成物理地址，须进行越界处理

33、。围，不能翻译成物理地址，须进行越界处理。4.3.3 两级和多级页表两级和多级页表 大多数计算机系统支持很大的逻辑地址空间，页表大多数计算机系统支持很大的逻辑地址空间，页表有可能非常大，以致一个物理块放不下。有可能非常大，以致一个物理块放不下。n做页表的页表，表明该进程需要多少页（块）来做页表的页表，表明该进程需要多少页（块）来放置页表。放置页表。n解决方法：解决方法： 将页表离散的放在内存若干块中；将页表离散的放在内存若干块中； 只将当前需要的部分页表项调入内存，只将当前需要的部分页表项调入内存， 其余页表其余页表项仍驻留在磁盘上，需要时再调入。项仍驻留在磁盘上，需要时再调入。 例：设内存块

34、大小为例：设内存块大小为4K， 现有一个现有一个128MB的程序，则其页表的程序，则其页表 有个页表有个页表项。设每个页表项占据项。设每个页表项占据1字节空间，则页字节空间，则页表的大小为表的大小为 K，在一个内存块中放，在一个内存块中放不下。必须放入不下。必须放入 个内存块。因此必须个内存块。因此必须有一个页表的页表，记录存放页表的这有一个页表的页表，记录存放页表的这些内存块。些内存块。2152581. 两级页表两级页表逻辑地址结构可描述如下：逻辑地址结构可描述如下： 每页大小为每页大小为4KB，存放页表项时，每页中最多，存放页表项时，每页中最多包含包含210个页表项。最多允许有个页表项。最

35、多允许有210个页表分页。个页表分页。图 414 两级页表结构 101110780121742n第0页页表1460121023第1页页表114115011023外部页表012345671141151468第n页页存空间图图 4-15 具有两级页表的地址变换机构具有两级页表的地址变换机构 外部页号P1P2外部页内地址页内地址d逻辑地址外部页表寄存器外部页表db页表页表物理地址 2. 多级页表多级页表 对于对于32位的机器，采用两级页表结构是合适的；但对于位的机器，采用两级页表结构是合适的；但对于64位的机器，必须采用多级页表，将外层页表再进行分页，位的机器，必须采用多级

36、页表，将外层页表再进行分页，也是将各分页离散地装入到不相邻接的物理块中，再利用也是将各分页离散地装入到不相邻接的物理块中，再利用第第2级的外层页表来映射它们之间的关系。级的外层页表来映射它们之间的关系。 内存管理的实现需要三个表内存管理的实现需要三个表作业表（作业表（JT）页映射表（页映射表（PMT）存储分块表（存储分块表（MBT）（1）作业表）作业表JT每个系统一个每个系统一个每个作业一个表项，包含了两方面内每个作业一个表项，包含了两方面内容容该作业的大小和存储位置，即页该作业的大小和存储位置，即页表的存储起始地址。表的存储起始地址。作业表是动态的，随着载入系统的作作业表是动态的，随着载入系

37、统的作业数目的增大而增大，随着作业完成数业数目的增大而增大，随着作业完成数目的增大而减少。目的增大而减少。（2）页表）页表PMT 每个激活的作业都有自己的页映射表每个激活的作业都有自己的页映射表（PMT），该表保存了每一页的主要信），该表保存了每一页的主要信息息页序号和对应的页面存储地址。页序号和对应的页面存储地址。 每个作业一个。每个作业一个。 其始地址从其始地址从JT表得到。表得到。块号块号页号页号1051169453327120页表页表3096 （3）存储分块表（）存储分块表（MBT） ?整个系统一个整个系统一个N：可用的空白块总数：可用的空白块总数Fptr：空白块链表表首指针：空白块链

38、表表首指针 每个空白块记录了下一个空白块的每个空白块记录了下一个空白块的 块号，因此形成了空白块链表块号，因此形成了空白块链表4.4 基本分段存储管理方式基本分段存储管理方式 4.4.1 分段存储管理方式的引入分段存储管理方式的引入 引入分段存储管理方式，引入分段存储管理方式， 主要是为了满足用户和程序员主要是为了满足用户和程序员的下述一系列需要：的下述一系列需要： 1) 方便编程方便编程 2) 信息共享信息共享 3) 信息保护信息保护 4) 动态增长动态增长 5) 动态链接动态链接 l作业（逻辑地址）空间的分段作业（逻辑地址）空间的分段l逻辑地址：二维地址（段号，段内地址）逻辑地址：二维地址

39、（段号，段内地址）l每个段分得一个连续的可变分区每个段分得一个连续的可变分区l段表段表段号、段基地址、段状态等段号、段基地址、段状态等段表寄存器段表寄存器利用段表实现地址映射利用段表实现地址映射基本原理基本原理1. 分段分段 分段地址中的地址具有如下结构：分段地址中的地址具有如下结构： 31 16 15 02. 段表段表 4.4.2 分段系统的基本原理分段系统的基本原理 段号段号段内地址段内地址第0段第1段第2段第3段用户作业用户作业段表段表基址基址段长段长150K35K500K9K300K20K100K42K3210段号段号内存内存第0段第1段第2段第3段地址变换及变换机构l基本分段管理的地

40、址变换基本分段管理的地址变换与基本分页管理的变换机构和过程类似。与基本分页管理的变换机构和过程类似。l段表寄存器段表寄存器存放段表的起始地址和段表长度；存放段表的起始地址和段表长度；l越界访问控制越界访问控制逻辑地址的段号与段表长度比较；逻辑地址的段号与段表长度比较；段内地址与段表中保存的段长比较；段内地址与段表中保存的段长比较；段表始址段表始址段表长度段表长度段表寄存器段表寄存器153705物理地址物理地址段号段号 3105逻辑地址逻辑地址越界中断越界中断段表段表基址基址段长段长150K35K500K9K300K20K100K42K3210段号段号内存1、判断段号是否小于段、判断段号是否小于

41、段表长度，否则越界表长度，否则越界3、判断段内偏移量是否、判断段内偏移量是否小于段长，否则越界小于段长，否则越界2、将段号与段表始址相加，找、将段号与段表始址相加，找到该段相应的段长和基址到该段相应的段长和基址4、将该段的基址与偏移、将该段的基址与偏移量相加得出物理地址量相加得出物理地址分段与分页的主要区别l页是信息的物理单位，段是信息的逻辑页是信息的物理单位，段是信息的逻辑单位；单位；l页的大小固定，段的大小动态变化；页的大小固定，段的大小动态变化；l分页系统中的逻辑地址空间是一维的，分页系统中的逻辑地址空间是一维的，分段系统中的是二维的。分段系统中的是二维的。l分页系统中不易实现分页系统中

42、不易实现“共享共享”和和“动态动态链接链接” ，分段则很容易。，分段则很容易。内存段表基址基址段长段长180K100K300K20K100K42K210段号段号第0段用户1编辑进程第0段用户2编辑进程基址基址段长段长380K30K300K20K100K42K210段号段号第0段4.4.3 信息共享信息共享 对比分页与分段中的信息共享对比分页与分段中的信息共享ed 1ed 2ed 40data 1data 10进程12122606170页表ed 1ed 2ed 40data 1data 10进程22122607180ed 1ed 2ed 40data 1data 10data 1data 10主

43、存021226061707180页表图 418 分页系统中共享editor的示意图图图 4-19 分段系统中共享分段系统中共享editor的示意图的示意图 editor进程1data 1进程2editordata 2段表段长基址16080402401608040380editordata 1data 280240280380420是否存在碎片？是否存在碎片？4.4.4 段页式存储管理方式段页式存储管理方式 1. 基本原理基本原理 图图 4-20 作业地址空间和地址结构作业地址空间和地址结构 04K8K12K15K16K子 程 序 段04K8K数 据 段04K8K10K12K(a )段 号 (S

44、)段 内 页 号 (P)段 内 地 址 (W)(b )主 程 序 段段号(S)段内页号(P)页内地址(W)(b)段页式存储管理方式主程序段数据段子程序段纯分页式存储管理能纯分页式存储管理能否使用动态链接？否使用动态链接？可动态链接可动态链接段表段表13021110页表始址页表始址页表长度页表长度状态状态段号段号段表寄存器页表页表03121110存储块号存储块号状态状态页号页号页表页表1110存储块号存储块号状态状态页号页号段表寄存器逻辑地址段表块号块号块内地址块内地址物理地址越界中断页表xxxx2xxxx1xxxx0页表始址页表始址段号段号1202601800块号块号页号页号1、对比段表、对比

45、段表长度和段号长度和段号2、将段号和始址相、将段号和始址相加，找出页表长度加，找出页表长度和页表始址和页表始址3、对比页表、对比页表长度和页号长度和页号4、将页号和页表、将页号和页表始址相加找出该始址相加找出该页在内存哪一块页在内存哪一块5、根据块号、根据块号和页内地址算和页内地址算出物理地址出物理地址页表长度3564.5 虚拟存储器的基本概念虚拟存储器的基本概念 4.5.1 虚拟存储器的引入虚拟存储器的引入 1. 常规存储器管理方式的特征常规存储器管理方式的特征 一次性。 (2) 驻留性。 2. 局部性原理局部性原理 (1) 程序执行时， 除了少部分的转移和过程调用指令外， 在大多数情况下仍

46、是顺序执行的。 (2) 过程调用将会使程序的执行轨迹由一部分区域转至另一部分区域， 但经研究看出，过程调用的深度在大多数情况下都不超过5。 (3) 程序中存在许多循环结构， 这些虽然只由少数指令构成， 但是它们将多次执行。 (4) 程序中还包括许多对数据结构的处理， 如对数组进行操作， 它们往往都局限于很小的范围内。 局限性表现在下述两个方面： (1) 时间局限性。 (2) 空间局限性。3. 虚拟存储器定义虚拟存储器定义 所谓虚拟存储器，是指具有请求调入功能请求调入功能和置换功能置换功能，能从逻辑上逻辑上对内存容量加以扩充的一种存储器系统。4.5.2 虚拟存储器的实现方法虚拟存储器的实现方法

47、1. 分页请求系统分页请求系统 段式虚拟存储系统页式虚拟存储系统2.请求分段系统请求分段系统4.5.3 虚拟存储器的特征虚拟存储器的特征 多次性多次性 对应一次性，一个作业被分成多次调入内存运行。对换性对换性 允许作业在运行过程中进行换入换出。3. 虚拟性虚拟性 以多次性和对换性为基础，用户看到的逻辑内存大于物理内存容量4.6 请求分页存储管理方式请求分页存储管理方式 4.6.1 请求分页中的硬件支持请求分页中的硬件支持 1. 页表机制页表机制 页号页号 物理块号物理块号 状态位状态位P 访问字段访问字段A 修改位修改位M外存地址外存地址 一段时间内被访问次数一段时间内被访问次数或多久未被访问

48、或多久未被访问该页是否已调入内存该页是否已调入内存在调入内存后是否被修在调入内存后是否被修改过，是则需保存改过，是则需保存在外存的物理块号在外存的物理块号2. 缺页中断机构缺页中断机构 图 423 涉及6次缺页中断的指令 页面B：A：654321指令copy ATO B（2）一条指令在执行期间可能产生多次缺页中断（1）缺页中断是在指令执行期间发现所要访问的数据或指令不在内存时所产生和处理的3. 地址变换机构地址变换机构 缺页中断处理保留CPU现场从外存中找到缺页内存满否？选择一页换出该页被修改否？将该页写回外存OS命令CPU从外存读缺页启动I/O硬件将一页从外存换入内存修改页表否是是否页表项在

49、快表中？CPU检索快表访问页表否页在内存？修改访问位和修改位形成物理地址地址变换结束否页号页表长度?开始程序请求访问一页产生缺页中断请求调页修改快表是越界中断是是图 424 请求分页中的地址变换过程 例：在作业执行中访问第i页时，要完成哪些步骤？ 硬件的地址转换机构查页表，若该页对应标志位为“1”,则按指定的内存块号进行地址转换，得到绝对地址：若该页标志位为“0”,则由硬件发出一个“缺页中断”,表示该页不在内存中；操作系统处理该中断,首先查看内存中是否有空闲块？若有,例如第k块为空闲块，则查到该页在辅助存储器中的位置为磁盘第j块 ；把该页读入内存第k块中 ；在页表中填上该页所占块号k，修改页标

50、志位为“1”；当要访问的页被调入内存后，再重新执行被中断的指令就可找到要访问的内存单元。4.6.2 内存分配策略和分配算法内存分配策略和分配算法 l最小物理块（页架）数的确定最小物理块（页架）数的确定保证进程正常运行所需的最少页架数；保证进程正常运行所需的最少页架数；与指令的格式、功能和寻址方式有关。与指令的格式、功能和寻址方式有关。l物理块的分配策略物理块的分配策略固定分配局部置换：固定分配局部置换：可变分配全部置换：可变分配全部置换：可变分配局部置换：可变分配局部置换：3. 物理块分配算法物理块分配算法 1) 平均分配算法平均分配算法 2) 按比例分配算法按比例分配算法 3) 考虑优先权的

51、分配算法考虑优先权的分配算法 4.6.3 调页策略调页策略 1. 何时调入页面何时调入页面 预调页策略预调页策略 2) 请求调页策略请求调页策略 2. 从何处调入页面从何处调入页面 系统拥有足够的对换区空间，这时可以全部从对换系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度。区调入所需页面，以提高调页速度。 (2) 系统缺少足够的对换区空间。系统缺少足够的对换区空间。(3) UNIX方式。方式。 3. 页面调入过程页面调入过程 4.7 页面置换算法页面置换算法 4.7.1 最佳置换算法和先进先出置换算法最佳置换算法和先进先出置换算法 1. 最佳最佳(Optimal)置

52、换算法置换算法 最佳置换算法是一种理论上的算法。其所选择的最佳置换算法是一种理论上的算法。其所选择的被淘汰页面，将是以后永不使用的，或许是在最长被淘汰页面，将是以后永不使用的，或许是在最长(未未来来)时间内不再被访问的页面。采用最佳置换算法，通时间内不再被访问的页面。采用最佳置换算法，通常可保证获得最低的缺页率。常可保证获得最低的缺页率。 假定系统为某个进程分配了三个物理块，进程的访问顺假定系统为某个进程分配了三个物理块，进程的访问顺序为序为7 7，0 0，1 1，2 2，0 0，3 3，0 0，4 4，2 2，3 3，0 0，3 3，2 2，1 1，2 2OPTOPT置换算法示例：置换算法示

53、例：7，0，1， 2，0，3，0，4，2， 3，0 ，3， 2，1， 27 *7 0 *7 0 1 *2 0 1 *2 0 12 0 3 *2 0 32 4 3 *2 4 32 4 32 0 3 *2 0 32 0 32 1 3 *2 1 3缺页次数缺页次数8 8缺页率缺页率f=8/15=53.33%f=8/15=53.33%2. 先进先出先进先出(FIFO)页面置换算法页面置换算法 总是淘汰最先进入内存的页面。它实现简单总是淘汰最先进入内存的页面。它实现简单，只需把进程中已调入内存的页面，按先后次序链成一个队列，并设置一个所谓的替换指针，使它总是指向内存中最老的页面。7，0，1， 2，0，3

54、，0，4， 2， 3，0 ，3， 2，1， 27 *7 0 *7 0 1 *2 0 1 *2 0 12 3 1 *2 3 0 *4 3 0 *4 2 0 *4 2 3 *0 2 3 *0 2 30 2 30 1 3 *0 1 2 *缺页率缺页率f=12/15=80%缺点：效率不高，缺点：效率不高，4.7.2 最近最久未使用最近最久未使用(LRU)置换算法置换算法 1. 算法描述算法描述 根据页面调入内存后的使用情况，根据页面调入内存后的使用情况，选择内存中最久选择内存中最久未使用的页面被置换。未使用的页面被置换。这是局部性原理的合理近似，这是局部性原理的合理近似，性能接近最佳算法。性能接近最佳

55、算法。7 *7 0 *7 0 1 *2 0 1 *2 0 12 0 3 *2 0 34 0 3 *4 0 2 *4 3 2 *0 3 2 *0 3 20 3 21 3 2 *1 3 2 7，0，1， 2，0，3，0，4， 2， 3，0 ，3， 2，1， 210次，缺页率次，缺页率f=10/15=66.67%LRU的开销是的开销是很大的，必须很大的，必须有硬件的支持有硬件的支持2. LRU置换算法的硬件支持置换算法的硬件支持 1) 寄存器寄存器 为了记录某进程在内存中各页的使用情况，须为每个为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为在内存中的页面配置

56、一个移位寄存器，可表示为 R=Rn1Rn2Rn3 R2R1R0 定时记录是否被访问了定时记录是否被访问了图 428 某进程具有8个页面时的LRU访问情况 每一次访问，在该页首位设每一次访问，在该页首位设1随着时间推移，寄存器中数值随着时间推移，寄存器中数值 往右移，即数值慢慢变小往右移，即数值慢慢变小需要换出页面时，选数需要换出页面时，选数值最小的那个页面换出值最小的那个页面换出2) 栈栈 图 429 用栈保存当前使用页面时栈的变化情况 4474707407047170410174010741210742120741210742621076每当进程访问某页面时，每当进程访问某页面时，便将该页面

57、的页号从栈中便将该页面的页号从栈中移出，将它压入栈顶。移出，将它压入栈顶。栈底则是最近最久未被栈底则是最近最久未被使用的页面的页面号使用的页面的页面号4.7.3 Clock置换算法置换算法 1. 简单的简单的Clock置换算法置换算法 图 430 简单Clock置换算法的流程和示例 入口查寻指针前进一步，指向下一个表目页面访问位 0?选择该页面淘汰是返回置页面访问位“ 0”否块号页号访问位指针0124034215650711替换指针Page9 use=1Page19Use=1Page1Use=0Page45Use=1Page191Use=1Page556Use=0Page13Use=0Page

58、67Use=1Page33Use=1Page222Use=0下一个帧指针n012345678（a）一个页替换前的缓冲区状态Page9 use=1Page19Use=1Page1Use=0Page45Use=0Page191Use=1Page727Use=1Page13Use=0Page67Use=1Page33Use=1Page222Use=0n012345678（b）下一页替换后的缓冲区状态 图4 23 时钟页面替换算法示意1第1页框假设正扫描到这个位置需调入页，要找到下一个访问位为0的页访问位不为0的要清0，再找下一个556页访问位页访问位为为0，可换出，可换出556页被换出，页被换出，7

59、27页换入，页换入，访问位访问位=1例题：例题： 假设采用固定分配策略，进程分得三个页框假设采用固定分配策略，进程分得三个页框,它在执行中按下列次序引用它在执行中按下列次序引用5个独立的页面个独立的页面: 2 3 2 1 5 2 4 5 3 2 5 2。给出。给出clock算法的计算过算法的计算过程和结果。程和结果。 2 3 2 1 5 2 4 5 3 2 5 22. 改进型改进型Clock置换算法置换算法 由访问位由访问位A和修改位和修改位M可以组合成下面四种类型的页面：可以组合成下面四种类型的页面： 1类类(A=0, M=0): 表示该页最近既未被访问，表示该页最近既未被访问， 又未被修改

60、，又未被修改， 是最佳淘汰页。是最佳淘汰页。 2类类(A=0, M=1)： 表示该页最近未被访问，表示该页最近未被访问， 但已被修改，但已被修改， 并不是很好的淘汰页。并不是很好的淘汰页。 3类类(A=1, M=0)： 最近已被访问，最近已被访问， 但未被修改，但未被修改， 该页有该页有可能再被访问。可能再被访问。 4类类(A=1, M=1): 最近已被访问且被修改，最近已被访问且被修改， 该页可能再被该页可能再被访问。访问。 1、第一次扫描寻找、第一次扫描寻找1类类页面，不改变访问位页面，不改变访问位2、找不到第、找不到第1类，则第类，则第二次扫描找第二次扫描找第2类页面类页面 ，并改变访问