计算机操作系统课件(第四版)第四五章

1、第四章第四章存储器管理存储器管理 4.1存储器的层次结构存储器的层次结构 4.2程序的装入和链接程序的装入和链接 4.3连续分配存储连续分配存储管理管理方式方式 4.4对换对换 4.5分页存储管理方式分页存储管理方式 4.5分段存储管理方式分段存储管理方式 1 4.1存储器的层次结构存储器的层次结构 4.1.1多级存储器结构多级存储器结构 4.1.2主存储器与寄存器主存储器与寄存器 4.1.3高速缓存和磁盘缓存高速缓存和磁盘缓存 2 4.1.1多级存储器结构多级存储器结构 存储层次至少应有三级：存储层次至少应有三级：CPU寄存器、主存、辅存寄存器、主存、辅存 寄存器寄存器 高速缓存高速缓存 主

2、存主存 磁盘缓存磁盘缓存 磁盘磁盘 可移动存储介质可移动存储介质 CPU寄存器寄存器 主存主存 辅存辅存 图图4-1存储层次示意图存储层次示意图 价格价格 高高 低低 速度速度 快快 慢慢 容量容量 小小 大大 3 4.1.2主存储器与寄存器主存储器与寄存器 1、主存储器、主存储器 主存也称可执行存储器。主存也称可执行存储器。CPU可从其中取指令和数可从其中取指令和数 据，数据能从主存读取并装入到寄存器中，或从寄据，数据能从主存读取并装入到寄存器中，或从寄 存器存入到主存。存器存入到主存。 2、寄存器、寄存器 寄存器访问速度最快。其长度以字为单位。寄存器访问速度最快。其长度以字为单位。 4 4

3、.1.3高速缓存和磁盘缓存高速缓存和磁盘缓存 1、高速缓存（、高速缓存（cache） 容量大于寄存器，访问速度快于内存。容量大于寄存器，访问速度快于内存。 Cache分类：分类： 一级一级cache紧靠内存，速度最高，容量最小。紧靠内存，速度最高，容量最小。 二级二级cache容量稍大，速度也稍低。容量稍大，速度也稍低。 2、磁盘缓存、磁盘缓存 磁盘缓存本身并磁盘缓存本身并不是不是一种实际存储介质。一种实际存储介质。 实质：实质：利用利用主存主存中的存储空间，来暂存从磁盘中中的存储空间，来暂存从磁盘中 读出或写入的信息读出或写入的信息 5 4.2程序的装入和链接程序的装入和链接 从源程序到程序

4、执行从源程序到程序执行 地址空间的概念地址空间的概念 重定位的概念重定位的概念 程序的装入程序的装入 程序的链接程序的链接 6 1、从源程序到程序执行、从源程序到程序执行 编译：编译程序编译：编译程序 l由编译程序（由编译程序（CompilerCompiler）将用户源代码编译）将用户源代码编译 成若干个目标模块。成若干个目标模块。 链接：链接程序链接：链接程序 l由链接程序（由链接程序（LinkerLinker）将编译后形成的一组）将编译后形成的一组 目标模块，以及它们所需要的库函数链接在目标模块，以及它们所需要的库函数链接在 一起，形成装入模块。一起，形成装入模块。 装入：装入程序装入：装

5、入程序 l由装入程序（由装入程序（LoaderLoader）将装入模块复制到内）将装入模块复制到内 存中。存中。 库库 汇编汇编 编译编译 主主 子子1 子子2 目标模块目标模块 链接程序链接程序 装入模块装入模块 库库 主主 子子1 子子2 装入程序装入程序 内存内存 库库 主主 子子1 子子2 7 2、地址空间的概念、地址空间的概念 物理（绝对）地址物理（绝对）地址程序执行程序执行 l每个内存单元的固定顺序地址（编号）。每个内存单元的固定顺序地址（编号）。 l内存内存：由字或字节组成的一维线性地址空间：由字或字节组成的一维线性地址空间 逻辑（相对）地址逻辑（相对）地址装入（汇编编译）装入（

6、汇编编译） l被链接装配（或汇编、编译）后的目标模块被链接装配（或汇编、编译）后的目标模块 所限定的地址的集合；所限定的地址的集合； l相对于某个相对于某个基准量基准量（通常为：（通常为：0）的编址。）的编址。 物理地址物理地址内存内存 00000 00001 00002 . . . 01000 02200 主主 子子1 子子2 主主 子子1 子子2 逻辑地址逻辑地址装入模块装入模块 0000 . . . 1200 主主 子子1 子子2 相对地址相对地址 源程序源程序/单个目标模块单个目标模块 000 500 000 300 000 400 8 重定位重定位 l概念：在装入时对目标程序中指令和

7、数据的概念：在装入时对目标程序中指令和数据的 修改过程称为重定位。修改过程称为重定位。 l即，逻辑地址变换为物理地址的过程。即，逻辑地址变换为物理地址的过程。 重定位的类型重定位的类型 l静态重定位：静态重定位：地址变换是在装入时一次完地址变换是在装入时一次完 成的，以后不再改变。成的，以后不再改变。 l动态重定位：动态重定位：地址变换是在程序指令执行地址变换是在程序指令执行 时进行的。时进行的。 作业地址空间作业地址空间内存空间内存空间 装入装入 365 LOAD 1,2500 5000 2500 0000 1000 365 LOAD 1,2500 15000 12500 10000 110

8、00 3、重定位的概念、重定位的概念 365 LOAD 1,12500 15000 12500 10000 11000 9 BR：重定位寄存器：重定位寄存器 VR:变址寄存器变址寄存器 0 0 10 4、程序的链接、程序的链接 链接链接： l把一个程序相关的一组目标模块和系统调用模块把一个程序相关的一组目标模块和系统调用模块 （库函数）链接形成一个整体（库函数）链接形成一个整体装入模块的过装入模块的过 程。程。 具体工作具体工作： l对相对地址的修改；变换外部调用符号。对相对地址的修改；变换外部调用符号。 链接方式分类链接方式分类： l静态链接静态链接 l装入时动态链接装入时动态链接 l运行时

9、动态链接运行时动态链接 模块模块A CallB; Return; 0 L-1 模块模块B CallC; Return; 0 M-1 模块模块C ; Return; 0 N-1 链接链接 模块模块A JSR”L”; Return; 0 L-1 模块模块B JSR”L+M”; Return; L L+M-1 模块模块C ; Return; L+M L+M+N-1 装入模块装入模块 11 5、程序的装入、程序的装入 含义：含义：就是把链接好的装入模块装入就是把链接好的装入模块装入“内存内存”。 装入方式分类：装入方式分类： l绝对装入绝对装入 l可重定位装入（静态重定位）可重定位装入（静态重定位）

10、l动态运行时装入（动态重定位）动态运行时装入（动态重定位） 提示：提示：通常链接、装入程序是一体的。通常链接、装入程序是一体的。 12 4.3连续分配存储管理方式连续分配存储管理方式 为用户程序分配一个连续的内存空间。曾被广泛应为用户程序分配一个连续的内存空间。曾被广泛应 用，且现在仍被采用。用，且现在仍被采用。 l单一连续分配单一连续分配 l固定分区分配固定分区分配 l动态分区分配动态分区分配 l基于顺序搜索的动态分区分配算法基于顺序搜索的动态分区分配算法 l基于索引搜索的动态分区分配算法基于索引搜索的动态分区分配算法 l动态可重定位分区分配动态可重定位分区分配 13 4.3.1单一连续分配

11、单一连续分配 基本思想基本思想 l把内存分为系统区和用户区，系统区供把内存分为系统区和用户区，系统区供OS使使 用，通常放在低址部分；系统区以外的全部内用，通常放在低址部分；系统区以外的全部内 存空间是用户区。存空间是用户区。 特点特点 l只能用于单用户、单任务的只能用于单用户、单任务的OS中。中。 l软件简单，硬件要求低（无需存储保护）软件简单，硬件要求低（无需存储保护） 实例实例 lCP/M，MS-DOS，RT-11 DOS内存分区内存分区CP/M内存分配内存分配 系统参数区系统参数区 BIOS CCP BDOS 系统区系统区 系统区系统区 14 4.3.2固定分区分配固定分区分配 最简单

12、的一种可运行最简单的一种可运行多道程序多道程序的存储管理方式。的存储管理方式。 1 1、划分分区的方法、划分分区的方法 l分区大小相等分区大小相等： 缺乏灵活性，用于控制多个相同对象的系统缺乏灵活性，用于控制多个相同对象的系统 l分区大小不等：分区大小不等： 多个较小分区、适量中等分区、少量大分区多个较小分区、适量中等分区、少量大分区 2 2、内存分配管理、内存分配管理 l将分区按大小排队将分区按大小排队 l建立分区使用表建立分区使用表起址、大小、状态起址、大小、状态 l程序装入时，由内存分配程序检索分区使用表，程序装入时，由内存分配程序检索分区使用表， 找到符合要求的分区，并进行标记。找到符

13、合要求的分区，并进行标记。 15 系统区系统区 分区分区1 分区分区4 分区分区5 分区分区2 分区分区3 系统区系统区 分区分区1 分区分区4 分区分区5 分区分区2 分区分区3 作业作业1 作业作业2 作业作业3 已使用已使用 已使用已使用 已使用已使用 作业作业1进入，大小进入，大小30K 作业作业2进入，大小进入，大小500K 作业作业3进入，大小进入，大小8K 16 4.3.3、动态分区分配、动态分区分配 根据进程的实际需要，根据进程的实际需要，动态动态的分配内存空间的分配内存空间 1、内存管理方式（数据结构）：、内存管理方式（数据结构）： l空闲分区表空闲分区表序号、起址、大小等项

14、序号、起址、大小等项 l空闲分区链空闲分区链双向链表双向链表 前向指针前向指针 +2 N 0 后向指针后向指针 +2 N 0 N个字节个字节 可用可用 空闲链表结构空闲链表结构 17 2、动态分区分配算法（、动态分区分配算法（4.3.44.3.5） 4.3.4基于顺序搜索的动态分区分配算法基于顺序搜索的动态分区分配算法 l首次适应算法首次适应算法：空闲分区按起址递增次序排列，：空闲分区按起址递增次序排列， 从头开始直至找到第一个满足要求的空闲分区。从头开始直至找到第一个满足要求的空闲分区。 特点：内存低端会留下小的空闲区，高端有大的特点：内存低端会留下小的空闲区，高端有大的 空闲区；空闲区；

15、l循环首次应算法循环首次应算法：从上次分配的位置之后开始查：从上次分配的位置之后开始查 找。找。 特点：使内存的空闲分区均匀，但缺乏大的空闲特点：使内存的空闲分区均匀，但缺乏大的空闲 分区；分区； 18 l最佳适应算法最佳适应算法：空闲分区按大小递增的次序排列，：空闲分区按大小递增的次序排列， 从头开始找到第一个满足要求的空闲分区。从头开始找到第一个满足要求的空闲分区。 缺点：会留下大量小碎片。缺点：会留下大量小碎片。 l最坏适应算法最坏适应算法：空闲分区按大小递减的次序排列，：空闲分区按大小递减的次序排列， 最前面的最大的空闲分区就是找到的分区。最前面的最大的空闲分区就是找到的分区。 优点：

16、分配后剩下的可用空间比较大优点：分配后剩下的可用空间比较大 缺点：一段时间后就不能满足对于较大空闲区的分缺点：一段时间后就不能满足对于较大空闲区的分 配要求。配要求。 19 4.3.5基于索引搜索的动态分区分配算法基于索引搜索的动态分区分配算法 l1、快速适应算法、快速适应算法：空闲分区按容量大小进行分：空闲分区按容量大小进行分 类。对于每一类具有相同容量的所有空闲空间分类。对于每一类具有相同容量的所有空闲空间分 区，单独设立一个空闲分区链表。在内存中设立区，单独设立一个空闲分区链表。在内存中设立 一张管理索引表，每个表项对应一种空闲分区类一张管理索引表，每个表项对应一种空闲分区类 型。型。

17、优点：查找效率高。保留大分区也不会产生碎片优点：查找效率高。保留大分区也不会产生碎片 缺点：分区归还主存时算法复杂。缺点：分区归还主存时算法复杂。 20 2、伙伴系统、伙伴系统：分区（已分配和空闲）大小均为：分区（已分配和空闲）大小均为2的的 k次幂（次幂（1=k=m）,2m 为可分配内存大小。为可分配内存大小。 l对对不连续的空闲分区，按分区大小进行分类。对不连续的空闲分区，按分区大小进行分类。对 具有相同大小的所有空闲分区，单独设立一个空闲具有相同大小的所有空闲分区，单独设立一个空闲 分区双向链表，即会存在分区双向链表，即会存在k个空闲分区链表。个空闲分区链表。 l分配时分配时，设需分配长

18、度为，设需分配长度为n，找，找2i分区链的分区，分区链的分区， 使使2i-1nu.size? m.size-u.sizesize? 划出划出u.size大小的分区大小的分区 修改有关的数据结构修改有关的数据结构 返回返回 将该分区从链表中移出将该分区从链表中移出 继续检索下一个表项继续检索下一个表项 Y Y Y N N N 内存分配流程内存分配流程 24 内存回收时的情况内存回收时的情况 情况情况1：情况情况2：情况情况3： 情况情况4： 25 4.3.6、可重定位分区分配、可重定位分区分配 1、动态重定位的引入、动态重定位的引入 l随着系统接收的作业的增加，内存中连续的大块随着系统接收的作业

19、的增加，内存中连续的大块 分区不复存在，产生了大量的分区不复存在，产生了大量的“碎片碎片”。 l新的作业无法装入到每个新的作业无法装入到每个“碎片碎片”小分区上运行，小分区上运行， 但所有碎片的空间总和可能大于需求。但所有碎片的空间总和可能大于需求。 l通过通过“拼接拼接”或或“紧凑紧凑”来来实现程序的浮动实现程序的浮动 （动态重定位动态重定位）。）。 26 OS区区 Job2 Job4 Job3 Job1 Job5 Job6 Job7 “零头零头” 碎片碎片 OS区区 Job2 Job4 Job3 Job1 Job5 Job6 Job7 OS区区 Job2 Job4 Job3 Job1 Jo

20、b5 Job6 Job7 “零头零头” 碎片碎片 27 2、动态重定位的实现、动态重定位的实现 l必须由硬件地址变换机构支持实现必须由硬件地址变换机构支持实现重定位重定位R l重定位寄存器：存放程序在内存中的起始地址。重定位寄存器：存放程序在内存中的起始地址。 处理机一侧处理机一侧存储器一侧存储器一侧 作业作业J内存内存 365 LOAD 1, 2500 5000 2500 1000 365 LOAD 1, 2500 15000 12500 10000 11000 2500 相对地址相对地址 10000 重定位重定位 寄存器寄存器 0000 28 优缺点分析优缺点分析 l优点：优点：消除了消除

21、了“碎片碎片”，提高了内存利用率，同，提高了内存利用率，同 时提高了系统效率。时提高了系统效率。 l缺点：缺点：需要动态重定位需要动态重定位“硬件硬件”机构支持，增加机构支持，增加 了系统成本，并轻度降低了程序执行速度，了系统成本，并轻度降低了程序执行速度，“紧紧 凑凑”处理增加了系统开销。处理增加了系统开销。 3、可重定位分区分配算法、可重定位分区分配算法 与动态分区分配算法基本相同，但增加了紧凑功能与动态分区分配算法基本相同，但增加了紧凑功能 动态重定位分区分配算法流程动态重定位分区分配算法流程 查找空闲分区链表第一项查找空闲分区链表第一项 找到可用分区？找到可用分区？ 按动态分区方式按动

22、态分区方式 进行分配进行分配 修改有关的修改有关的 数据结构数据结构 返回分区号返回分区号 及首批及首批 进行紧凑进行紧凑 形成连续空闲区形成连续空闲区 YY NN 请求分配请求分配 u.size分区分区 空闲分区和空闲分区和=u.size？ 修改有关的修改有关的 数据结构数据结构 无法分配无法分配 返回返回 29 1、对换的引入、对换的引入 l对换的定义对换的定义P135 l目的：用于解决内存不足的问题；目的：用于解决内存不足的问题； l对换的类型：对换的类型： 整体对换：以进程为单位的对换整体对换：以进程为单位的对换 部分对换：以部分对换：以“页页”或或“段段”为单位的对换为单位的对换 2

23、、对换空间的管理、对换空间的管理 l外存的划分：文件区、对换区外存的划分：文件区、对换区 l管理方式：空闲分区表、空闲分区链管理方式：空闲分区表、空闲分区链 l分配算法：首次适应法、循环首次适应法、分配算法：首次适应法、循环首次适应法、 最佳适应法最佳适应法 4.4、对换、对换（Swapping） 30 3、进程的换出与换入、进程的换出与换入 l进程的换出进程的换出 l选择处于阻塞状态且优先级最低的进程选择处于阻塞状态且优先级最低的进程 l将该进程的程序和数据传送道磁盘的对换区上将该进程的程序和数据传送道磁盘的对换区上 l回收内存空间，修改该进程的回收内存空间，修改该进程的PCB l进程的换入

24、进程的换入 l定时查看进程状态定时查看进程状态 l将处于就绪态的换出时间最久的进程换入内存将处于就绪态的换出时间最久的进程换入内存 31 例如：例如：在分时系统中，一台主机，多台终端，每个在分时系统中，一台主机，多台终端，每个 用户得到的内存有限，因此可利用外存作为补充。用户得到的内存有限，因此可利用外存作为补充。 内存内存 就绪队列就绪队列 时间片到（换出）时间片到（换出） 调调 度度 换入换入 32 4.5基本分页存储管理方式基本分页存储管理方式 连续分配方式的不足，促使人们产生了离散分连续分配方式的不足，促使人们产生了离散分 配的管理思想。从而引入了配的管理思想。从而引入了“分页分页”分

25、配管理的管分配管理的管 理方式。分为：基本分页（纯分页）和支持虚存管理方式。分为：基本分页（纯分页）和支持虚存管 理的请求分页管理。理的请求分页管理。 l页面与页表页面与页表 l地址变换机构地址变换机构 l两级和多级页表两级和多级页表 l基本分页的特点基本分页的特点 33 4.5.1、页面与页表、页面与页表 1、页面、页面 l页面和物理块（页框页面和物理块（页框/架）：顺序编号，页内碎片架）：顺序编号，页内碎片 l页面大小：页面大小：2n Bytes 一般在：一般在：512B 8/32K 2、地址结构、地址结构 逻辑地址逻辑地址物理地址物理地址 页内地址页内地址d物理块号物理块号P 位移量位移

26、量W页号页号P 例如：例如： 位移量（页内地址）位移量（页内地址）W页号页号P 3112110 每页大小为每页大小为4KB，地址空间最多允许有，地址空间最多允许有1M页页 0 1 2 3 4 5 6 7 8 9 11 10 内存内存 第第0页页 第第1页页 第第2页页 第第3页页 第第4页页 第第5页页 第第6页页 用户作业用户作业 0 2K-1 第第2页页 （页长（页长2K） 0 2K-1 4号页架号页架 （页长（页长2K） 34 l页号页号P和页内地址和页内地址d的的计算公式计算公式 PINTA/LINT：整除函数：整除函数 dAMODLMOD：取余函数：取余函数 （A：逻辑地址空间中的地

27、址，：逻辑地址空间中的地址，L：页面大小）：页面大小） l例如：例如：某系统的页面大小为某系统的页面大小为1KB，地址，地址A=2170B， 则求得则求得P=2，d=122 3、页表、页表页面映像表页面映像表 l数据结构：页号、块号、存取控制项数据结构：页号、块号、存取控制项 l页表作用：实现从页号到物理块号的地址映射。页表作用：实现从页号到物理块号的地址映射。 0 1 2 3 4 5 6 7 8 9 11 10 内存内存 第第0页页 第第1页页 第第2页页 第第3页页 第第4页页 第第5页页 第第6页页 用户作业用户作业 块号块号页号页号 105 116 94 53 32 71 20 页表页

28、表 0000,0000,0000,0000,0101 ,0001,0000,0000 第第3页页256字节的物理地址（页大小：字节的物理地址（页大小：4K） 第第0页页 第第1页页 第第2页页 第第3页页 第第4页页 第第5页页 第第6页页 第第0页页 第第1页页 第第2页页 第第3页页 第第4页页 第第5页页 第第6页页 35 4.5.2、地址变换机构、地址变换机构 1、基本的地址变换机构、基本的地址变换机构 l地址变换机构的任务：实现地址映射，即从逻辑地地址变换机构的任务：实现地址映射，即从逻辑地 址到物理地址的变换过程。址到物理地址的变换过程。 l页表存放在内存系统区的一个连续空间中；页

29、表存放在内存系统区的一个连续空间中； lPCB和页表寄存器和页表寄存器PTR中存有页表在内存的首地址中存有页表在内存的首地址 和页表长度；和页表长度； 地址映射过程：（如图）地址映射过程：（如图） l自动的将逻辑地址分为页号和页内地址自动的将逻辑地址分为页号和页内地址 l根据页号查询页表：页表首地址根据页号查询页表：页表首地址+页号页号 表项长度；表项长度； 36 页表始址页表始址页表长度页表长度 页表寄存器页表寄存器 页表页表 块号块号页号页号 53 32 71 20 52018 物理地址物理地址 32018 逻辑地址逻辑地址 越界中断越界中断 l找到该页对应的物理块号，装入物理地址寄存器找

30、到该页对应的物理块号，装入物理地址寄存器 l将页内地址送入物理地址寄存器。将页内地址送入物理地址寄存器。 37 2、具有快表的地址变换机构、具有快表的地址变换机构 l快表（联想寄存器）快表（联想寄存器）具有并行查询能力的高具有并行查询能力的高 速缓冲寄存器速缓冲寄存器 l空间大小：空间大小：几几K到几百到几百K，只含有部分页表项，只含有部分页表项 （16512个）个） l快表与页表同时访问；快表与页表同时访问； l地址映射过程：地址映射过程： l将页号将页号P送入快表，若有此页号，则读出该页对应送入快表，若有此页号，则读出该页对应 的物理块号；若无，则访问页表的物理块号；若无，则访问页表 l将

31、物理块号送入地址寄存器，并将此页表项存入将物理块号送入地址寄存器，并将此页表项存入 快表。若快表已满，则换出一个不再用的页表项快表。若快表已满，则换出一个不再用的页表项 页表始址页表始址页表长度页表长度 页表寄存器页表寄存器 页表页表 块号块号页号页号 53 32 71 20 31250 物理地址物理地址 21250 逻辑地址逻辑地址 越界中断越界中断 快表快表 块号块号页号页号 205 114 53 20 输入寄存器输入寄存器 38 4.5.3、两级和多级页表、两级和多级页表 两级页表两级页表 l解决大页表占用大的连续存储空间的问题；解决大页表占用大的连续存储空间的问题； l将在内存中离散分

32、配的页表再建立一张页表，将在内存中离散分配的页表再建立一张页表， 称为外层页表。称为外层页表。 l逻辑地址：逻辑地址： 外层页号外层页号+外层页内地址外层页内地址+页内地址页内地址 l增设外层页表寄存器，存放外层页表的始址增设外层页表寄存器，存放外层页表的始址 外部页表外部页表 块号块号页号页号 3 2 10781 10110 页表分页页表分页 1122 31 20 2 1 1130 0 1 2 3 112 113 1011 39 外部页表外部页表 外部页表外部页表 寄存器寄存器 物理地址物理地址 外部页号外部页号P1外部页内地址外部页内地址P2 逻辑地址逻辑地址 页内地址页内地址d 页表页表

33、 具有两级页表的地址变换机构具有两级页表的地址变换机构 40 基本分页的特点：基本分页的特点： 优点优点： l存在页内碎片，但碎片相对较小，内存利用率较高存在页内碎片，但碎片相对较小，内存利用率较高 l实现了离散分配，消除了程序浮动；实现了离散分配，消除了程序浮动； 缺点缺点： l需要专门的硬件支持，尤其需要专门的硬件支持，尤其“快表快表”； l内存访问的效率下降。内存访问的效率下降。 41 4.6分段存储管理方式分段存储管理方式 分段管理思想的引入分段管理思想的引入 基本原理基本原理 地址变换地址变换 分段与分页的主要区别分段与分页的主要区别 段页式存储管理方式段页式存储管理方式 42 4.

34、6.1、分段管理思想的引入、分段管理思想的引入 分段存储管理方式主要是为了满足用户和程序员分段存储管理方式主要是为了满足用户和程序员 的下述需要：的下述需要： 方便编程：方便编程：LOAD1,A|; 信息共享：共享的实现以是信息的逻辑单位为基础信息共享：共享的实现以是信息的逻辑单位为基础 信息保护：同样是对逻辑单位进行保护信息保护：同样是对逻辑单位进行保护 动态增长：如数据段动态增长：如数据段 动态链接：运行时调入内存并链接动态链接：运行时调入内存并链接 43 4.6.2、基本原理、基本原理 1、分段、分段 l作业（逻辑地址）空间分段，每个段都有名字：作业（逻辑地址）空间分段，每个段都有名字：

35、 主程序段、子程序段、数据段、栈段等主程序段、子程序段、数据段、栈段等 l逻辑地址：二维地址（段号，段内地址）逻辑地址：二维地址（段号，段内地址） l每个段装入内存中的一个连续的内存空间每个段装入内存中的一个连续的内存空间 2、段表、段表 l段号、段基址、段长度等段号、段基址、段长度等 l每个段在段表中占一个表项每个段在段表中占一个表项 l段表寄存器：存放段表的起址和长度段表寄存器：存放段表的起址和长度 l利用段表实现地址映射利用段表实现地址映射 内存内存 第第0段段 第第1段段 第第2段段 第第3段段 用户作业用户作业 段表段表 基址基址段长段长 150K35K 500K9K 300K20K

36、 100K42K 3 2 1 0 段号段号第第0段段 第第1段段 第第2段段 第第3段段 44 3、基本分段管理的地址变换、基本分段管理的地址变换 l与基本分页管理的变换机构和过程类似。与基本分页管理的变换机构和过程类似。 段表寄存器段表寄存器 l存放段表的起始地址和段表长度；存放段表的起始地址和段表长度； 越界访问控制越界访问控制 l逻辑地址的段号与段表长度比较； l段内地址与段表中保存的段长比较； 45 段表始址段表始址 段表长度（段表长度（4） 段表寄存器段表寄存器 153705物理地址物理地址 段号段号3105 逻辑地址逻辑地址 越界中断越界中断 段表段表 基址基址段长段长 150K3

37、5K 500K9K 300K20K 100K42K 3 2 1 0 段号段号 内存内存 150*1024=153600 153600+105=153705 46 4、分段与分页的主要区别、分段与分页的主要区别 页是信息的物理单位，段是信息的逻辑单位；页是信息的物理单位，段是信息的逻辑单位； 页的大小固定，段的大小动态变化；页的大小固定，段的大小动态变化； 分页系统中的逻辑地址空间是一维的，分段系分页系统中的逻辑地址空间是一维的，分段系 统中的是二维的。统中的是二维的。 47 内存内存 段表段表 基址基址段长段长 240K40K 80K160K 1 0 段号段号 editor 进程进程1 edi

38、tor 进程进程2 基址基址段长段长 380K40K 80K160K 1 0 段号段号 editor 分段系统易实现信息共享：分段系统易实现信息共享： 4.6.3、信息共享、信息共享 48 内存内存 页表页表 editor1 进程进程1 进程进程2 editor2 editor40 editor1 editor2 editor40 editor1 editor2 editor40 0 21 22 60 61 70 71 80 49 例例1：已知某分页系统，主存容量为已知某分页系统，主存容量为64k，页面大小为，页面大小为 1k，对一个，对一个4页大的作业，第页大的作业，第0、1、2、3页被分配

39、到内页被分配到内 存的存的2、4、6、7块中。块中。 求：将十进制的逻辑地址求：将十进制的逻辑地址1023、2500、4500转换成物转换成物 理地址。理地址。 解解:(1)1023/1K，得到页号为，得到页号为0，页内地址，页内地址1023。 又又对应的物理块号为对应的物理块号为2，故物理地址为，故物理地址为2*1k+1023=3071 (2)2500/1K，得到页号为，得到页号为2，页内地址，页内地址452。 又又对应的物理块号为对应的物理块号为6，故物理地址为，故物理地址为6*1k+452=6596 (3)4500/1K，得到页号为，得到页号为4，页内地址，页内地址404。 因为页号不小

40、于页表长度，故产生越界中断。因为页号不小于页表长度，故产生越界中断。 50 例例2：对于如下所示的段表，请将逻辑地址（对于如下所示的段表，请将逻辑地址（0，137），）， （1，4000），（），（2，3600），（），（5，230）转换成物理地）转换成物理地 址。址。 解解:(1)段号段号0段表长，且段表长，且137段长段长10k，故段号、段，故段号、段 内地址全部合法。得物理地址为内地址全部合法。得物理地址为50k+137=51337 解解:(2)段号段号1段长段长3k，因，因 此产生越界中断。此产生越界中断。 解解:(3)段号段号2段表长，且段表长，且3600段长段长5k，故段号、段，故

41、段号、段 内地址全部合法。得物理地址为内地址全部合法。得物理地址为70k+3600=75280 解解:(4)段号段号5段表长，故段号不合法。产生越界中段表长，故段号不合法。产生越界中 断。断。 51 4.6.4、段页式存储管理方式、段页式存储管理方式 基本思想基本思想 l结合分页和分段技术；结合分页和分段技术； l分页：有效提高内存利用率分页：有效提高内存利用率 l分段：很好的满足用户需求分段：很好的满足用户需求 原理原理 l对内存进行分页（物理块对内存进行分页（物理块/页架）；页架）； l对用户作业先分段，各段再分页。对用户作业先分段，各段再分页。 地址结构与地址变换地址结构与地址变换 l段

42、号、段内页号、页内地址三部分段号、段内页号、页内地址三部分 l段表和页表段表和页表 52 主程序段主程序段 数据段数据段 子程序段子程序段 53 段表段表 13 02 11 10 页表始址页表始址页表长度页表长度状态状态段号段号 段表寄存器段表寄存器 页表页表 03 12 11 10 存储块号存储块号状态状态页号页号 页表页表 11 10 存储块号存储块号状态状态页号页号 54 段表寄存器段表寄存器 逻辑地址逻辑地址 段表段表 块号块号块内地址块内地址 物理地址物理地址 越界中断越界中断 页表页表 xxxx2 xxxx1 xxxx0 页表始址页表始址段号段号 2 1 0 存储块号存储块号页号页

43、号 55 段页式存储管理的优缺点段页式存储管理的优缺点 l同时具备分段和分页管理的优点：分散存储，同时具备分段和分页管理的优点：分散存储， 内存利用率较高；便于代码或数据共享，支持内存利用率较高；便于代码或数据共享，支持 动态链接等。动态链接等。 l访问效率下降：一次访问转换成了三次访问。访问效率下降：一次访问转换成了三次访问。 56 第五章第五章虚拟存储器虚拟存储器 5.1虚拟存储器概述虚拟存储器概述 5.2请求分页存储管理方式请求分页存储管理方式 5.3页面置换算法页面置换算法 5.4抖动与工作集抖动与工作集 5.5请求分段存储管理方式请求分段存储管理方式 57 5.1虚拟存储器概述虚拟存

44、储器概述 虚拟存储器的引入虚拟存储器的引入 虚拟存储器的实现方法虚拟存储器的实现方法 虚拟存储器的特征虚拟存储器的特征 58 5.1.1、虚拟存储器的引入、虚拟存储器的引入 1、内存空间的限制、内存空间的限制 l常规存储器管理方式的特点：一次性、驻留性常规存储器管理方式的特点：一次性、驻留性 l情况一：内存空间装不下的大作业无法运行情况一：内存空间装不下的大作业无法运行 l情况二：作业量大时，无法允许更多的作业并发情况二：作业量大时，无法允许更多的作业并发 59 2、局部性原理、局部性原理 l1968年，年，P.Denning l在一较短的时间内，程序的执行仅限于某个部分；在一较短的时间内，程

45、序的执行仅限于某个部分； 它所访问的存储空间也局限于某个区域。它所访问的存储空间也局限于某个区域。 l提出的论点：提出的论点： （1）程序的顺序执行）程序的顺序执行 （2）过程调用深度有限）过程调用深度有限 （3）程序中的循环结构）程序中的循环结构 （4）程序中有许多对数据结构的处理）程序中有许多对数据结构的处理 l局限性还表现在：局限性还表现在： （1）时间局限性）时间局限性 （2）空间局限性）空间局限性 60 3、虚拟存储器的定义、虚拟存储器的定义 l物理上不存在，利用海量外存进行内存物理上不存在，利用海量外存进行内存“空间空间” 扩展。扩展。 l允许作业部分装入，需要时再临时装入所需的部

46、允许作业部分装入，需要时再临时装入所需的部 分。直到作业退出，某些部分也有可能没被装入分。直到作业退出，某些部分也有可能没被装入 过。过。 l定义：定义：虚拟存储器是指具有虚拟存储器是指具有请求调入功能请求调入功能和和置换置换 功能功能，能从，能从逻辑逻辑上对内存容量加以扩充的一种存上对内存容量加以扩充的一种存 储器系统。储器系统。 61 5.1.2、虚拟存储器的实现方法、虚拟存储器的实现方法 必须建立在离散分配的内存管理技术基础上。必须建立在离散分配的内存管理技术基础上。 1、请求分页系统、请求分页系统 l基本分页系统基本分页系统+请求调页功能请求调页功能+页面置换功能页面置换功能 页式虚拟

47、存储系统页式虚拟存储系统 l硬硬/软件支持：请求分页的页表机制、缺页中断机软件支持：请求分页的页表机制、缺页中断机 构、动态地址变换机构。构、动态地址变换机构。 62 2、请求分段系统、请求分段系统 l基本分段系统基本分段系统+请求调段功能请求调段功能+分段置换功能分段置换功能 段式虚拟存储系统段式虚拟存储系统 l硬硬/软件支持：请求分段的段表机制、缺段中断机构、软件支持：请求分段的段表机制、缺段中断机构、 动态地址变换机构。动态地址变换机构。 63 5.1.3、虚拟存储器的特征、虚拟存储器的特征 多次性多次性 l一个作业被分成多次调入内存运行；一个作业被分成多次调入内存运行； 对换性对换性

48、l允许在作业的运行过程中进行换进、换出；允许在作业的运行过程中进行换进、换出； 虚拟性虚拟性 l能从逻辑上扩充内存容量，使用户能从逻辑上扩充内存容量，使用户“看到看到” 的内存容量远大于实际大小。的内存容量远大于实际大小。 l该特征是以上两个特征为基础的。该特征是以上两个特征为基础的。 64 5.2请求分页存储管理方式请求分页存储管理方式 请求分页中的硬件支持请求分页中的硬件支持 内存分配策略和分配算法内存分配策略和分配算法 请求分页策略请求分页策略 65 5.2.1、请求分页中的硬件支持、请求分页中的硬件支持 1、页表机制、页表机制 l用于地址转换；用于地址转换； l增加页表项：增加页表项：

49、 状态位状态位P：用于指示该页是否已调入内存：用于指示该页是否已调入内存 访问字段访问字段A：记录本页在一段时间内被访问的次数：记录本页在一段时间内被访问的次数 修改位修改位M：该页在调入内存后是否被修改过：该页在调入内存后是否被修改过 外存地址外存地址：指示该页在外存上的地址：指示该页在外存上的地址 66 2、缺页中断机构、缺页中断机构 l所要访问的页不在内存时，便引发一次缺页中断所要访问的页不在内存时，便引发一次缺页中断 缺页中断与其他中断的不同：缺页中断与其他中断的不同： l在指令执行期间产生和处理中断信号在指令执行期间产生和处理中断信号 l一条指令在执行期间可能产生多次缺页中断一条指令

50、在执行期间可能产生多次缺页中断 6 5 4 3 2 1 A: B: Copy A to B 指令指令 67 3、地址变换机构、地址变换机构 l情况一：情况一： 首先检索快表，若找到，修改页表项中的访问位，首先检索快表，若找到，修改页表项中的访问位， 然后利用页表项中给出的物理块号和页内地址，然后利用页表项中给出的物理块号和页内地址， 形成物理地址。形成物理地址。 访问字段访问字段A：记录本页在一段时间内是否被访问：记录本页在一段时间内是否被访问 68 地址变换机构地址变换机构 l情况二：情况二： 如果在快表中未找到相应的页表项，检索内存中如果在快表中未找到相应的页表项，检索内存中 的页表，查看

51、页表中的状态位，若该页已经调入的页表，查看页表中的状态位，若该页已经调入 内存，填写快表，当快表满时，应淘汰一个页表内存，填写快表，当快表满时，应淘汰一个页表 项；若该页尚未调入内存，产生缺页中断，请求项；若该页尚未调入内存，产生缺页中断，请求 OS把该页调入。把该页调入。 状态位状态位P：用于指示该页是否已调入内存：用于指示该页是否已调入内存 69 5.2.2、内存分配策略和分配算法、内存分配策略和分配算法 1、最小物理块数的确定、最小物理块数的确定 l保证进程正常运行所需的最少物理块数；保证进程正常运行所需的最少物理块数； l与硬件结构有关，取决于指令的格式、功能和寻与硬件结构有关，取决于

52、指令的格式、功能和寻 址方式。址方式。 2、物理块的分配策略、物理块的分配策略 l（1）固定分配局部置换：）固定分配局部置换：为进程分配的物理块为进程分配的物理块 数在整个运行期间都不再改变。若某个进程发生数在整个运行期间都不再改变。若某个进程发生 缺页，则只能将自己的某个内存页换出。缺页，则只能将自己的某个内存页换出。 70 l（2）可变分配全局置换：）可变分配全局置换：为每个进程分配一定为每个进程分配一定 数目的物理块，当进程发生缺页，若系统中有空数目的物理块，当进程发生缺页，若系统中有空 闲的物理块，则分配一个物理块并装入缺页；页闲的物理块，则分配一个物理块并装入缺页；页 面的置换范围是

53、任一个进程。面的置换范围是任一个进程。 l（3）可变分配局部置换：）可变分配局部置换：为每个进程分配一定为每个进程分配一定 数目的物理块后，若某个进程发生缺页，则只能数目的物理块后，若某个进程发生缺页，则只能 将自己的某个内存页换出。将自己的某个内存页换出。OS根据缺页率进行物根据缺页率进行物 理块分配的调整。理块分配的调整。 71 3、物理块的分配算法、物理块的分配算法 l平均分配算法平均分配算法 l将空闲物理块，平均分配给各个进程。将空闲物理块，平均分配给各个进程。 l按比例分配算法按比例分配算法 l根据进程的大小按比例分配物理块的。根据进程的大小按比例分配物理块的。 l考虑优先权的分配算

54、法考虑优先权的分配算法 l按比例分配给各进程按比例分配给各进程 l优先权高的一次分得的物理块数多。优先权高的一次分得的物理块数多。 72 5.2.3、请求分页策略、请求分页策略 1、调入页面的时机、调入页面的时机 l确定系统将进程运行时所缺的页面调入内存的时机确定系统将进程运行时所缺的页面调入内存的时机 l预调页策略：首次调入内存时预调页策略：首次调入内存时 l请求调页策略：运行中的发生缺页现象时请求调页策略：运行中的发生缺页现象时 2、确定从何处调入页面、确定从何处调入页面 l系统拥有足够的对换区空间系统拥有足够的对换区空间 l系统缺少足够的对换区空间系统缺少足够的对换区空间 lUNIX方式

55、方式 73 3、页面调入过程、页面调入过程 l向向CPU发出缺页中断发出缺页中断 l中断处理程序保存中断处理程序保存CPU环境转中断处理程序环境转中断处理程序 l该程序查找页表，得到该页在外存中的块号。该程序查找页表，得到该页在外存中的块号。 l若内存未满，启动磁盘若内存未满，启动磁盘I/O读入；若内存已满，读入；若内存已满， 先置换，再调入；先置换，再调入； l最后修改页表对应项的内容。最后修改页表对应项的内容。 74 5.3页面置换算法页面置换算法 最佳置换算法（最佳置换算法（OPT） 先进先出（先进先出（FIFO） 最近最久未使用置换算法（最近最久未使用置换算法（LRU） Clock置换

56、算法（置换算法（NRU） 最少使用置换算法（最少使用置换算法（LFU） 页面缓冲置换算法（页面缓冲置换算法（PBA） 当内存中没有可以利用的页架时，根据一定的策略当内存中没有可以利用的页架时，根据一定的策略 从内存中选择一个页面，把它置换到外存，称为页面从内存中选择一个页面，把它置换到外存，称为页面 置换算法。置换算法。 75 5.3.1、最佳置换算法和先进先出置换算法、最佳置换算法和先进先出置换算法 1、最佳置换算法（、最佳置换算法（OPT） 算法描述：算法描述： 选择以后永远（相比之下，最长时间）不会被选择以后永远（相比之下，最长时间）不会被 使用的页淘汰出去。使用的页淘汰出去。 特点：特

57、点： l理论上，性能最佳；理论上，性能最佳； l实际上，无法实现；实际上，无法实现； l通常用该算法来评价其他算法的优劣。通常用该算法来评价其他算法的优劣。 76 例例1：在一个请求分页系统中，假定系统分给一个作：在一个请求分页系统中，假定系统分给一个作 业的业的物理块数为物理块数为3，并且此作业的页面走向为，并且此作业的页面走向为2，3，2， 1，5，2，4，5，3，2，5，2。用。用FIFO、LRU、OPT计计 算缺页次数和缺页率。算缺页次数和缺页率。 分析：分析：如果所访问的页还没有装入内存，将发生一如果所访问的页还没有装入内存，将发生一 次缺页中断。次缺页中断。访问过程中发生缺页中断的

58、次数就是缺页访问过程中发生缺页中断的次数就是缺页 次数。缺页次数除以总的访问次数，就是缺页率。次数。缺页次数除以总的访问次数，就是缺页率。 77 缺页缺页 中断中断 3 2 5 3 2 5 3 2 + 5 3 2 5 3 4 5 3 4 + 5 3 4 5 3 2 + 5 3 2 + 1 3 2 3 2 + 3 2 + 21 352354251232 页面页面 走向走向 使用使用OPT算法：算法： 将来再也不用或最长时间不用的页面将来再也不用或最长时间不用的页面黄色标志黄色标志 缺页次数：缺页次数：6，缺页率：，缺页率：6/12，页面置换，页面置换3次次 78 2、先进先出置换算法（、先进先出

59、置换算法（FIFO） 算法描述算法描述： 总是先淘汰那些最先进入系统，即驻留主存时间最总是先淘汰那些最先进入系统，即驻留主存时间最 长的页。长的页。 特点特点： l实现简单 l与进程实际的运行不相适应 79 缺页缺页 中断中断 3 2 + 2 5 3 + 4 5 3 4 2 3 + 4 2 3 4 2 5 + 4 2 5 + 1 2 5 + 1 3 5 + 1 3 2 3 2 + 3 2 + 21 252354251232 页面页面 走向走向 使用使用FIFO算法算法: 缺页次数：缺页次数：9，缺页率：，缺页率：9/12；页面置换；页面置换6次次 驻留内存最久的页面驻留内存最久的页面黄色标志黄

60、色标志 80 5.3.2最近最久未使用置换算法（最近最久未使用置换算法（LRU） 1、算法描述：、算法描述： 选择在最近一段时间最久未被使用（访问）的选择在最近一段时间最久未被使用（访问）的 页淘汰出去。页淘汰出去。 特点特点： l性能较好性能较好 l实现复杂，需要硬件支持（每页配置一个寄实现复杂，需要硬件支持（每页配置一个寄 存器、栈），增加系统负担。存器、栈），增加系统负担。 81 缺页缺页 中断中断 3 2 2 5 3 2 5 3 + 2 5 3 + 4 5 3 4 5 2 + 4 5 2 1 5 2 + 1 5 2 + 1 3 2 3 2 + 3 2 + 21 252354251232