主存管理 第6章 主存管理

主存管理——主要内容 主存管理概述 主存管理的功能 分区存储管理 页式存储管理 段式及段页式存储管理 1

主存管理——主存管理概述 主存管理概述

1. 主存共享方式 (1) 大小不等的区域 (2) 大小相等的区域 (3) 二者结合 主存管理——主存管理概述 ① 分区存储管理 1. 主存共享方式 (1) 大小不等的区域 ① 分区存储管理 ② 段式存储管理 (2) 大小相等的区域 页式存储管理 (3) 二者结合 段页式存储管理 2

2. 程序的逻辑组织 (1) 一维地址结构 主存管理——主存管理概述 一个程序是一个连续、线性的地 址结构； 确定线性地址空间中的指令地址 2. 程序的逻辑组织 (1) 一维地址结构 一个程序是一个连续、线性的地 址结构； 确定线性地址空间中的指令地址 或操作数地址只需要一个信息。 1 n-1  程序地址空间 一维地址结构 3

(2) 二维地址结构 主存管理——主存管理概述 一个程序由若干个分段组成，每个分段是一个连续的地址区； 确定线性地址空间中的指令地址或操作数地址需要两个信息，一是该信息所在的分段，另一个是该信息在段内的偏移量。 code_addr 4KB1 代码分段 data_addr 3KB1 数据分段 stack_addr 2KB1 栈段 1  程序地址空间——二维地址结构 4

主存管理——主存管理功能 主存管理功能

1. 几个概念 (1) 物理地址 (绝对地址、实地址) (2) 主存空间 (3) 逻辑地址 (相对地址、虚地址) (4) 程序地址空间 主存管理——主存管理功能 1. 几个概念 (1) 物理地址 (绝对地址、实地址) 物理地址是计算机主存单元的真实地址，又称为绝对地 址或实地址。 (2) 主存空间 物理地址的集合所对应的空间组成了主存空间。 (3) 逻辑地址 (相对地址、虚地址) 用户的程序地址 (指令地址或操作数地址)均为逻辑地址。 (4) 程序地址空间 用户程序所有的逻辑地址集合对应的空间。 5

(5) 程序地址空间与主存空间 主存管理——主存管理功能 1 1 n-1 程序1地址空间  m-1 主存空间 k-1 程序 i 地址空间 1 n-1 程序 i 地址空间 k-1  主存空间 1 m-1 程序地址空间与主存空间示意图 6

主存管理——主存管理功能 2. 主存管理功能 实现逻辑地址到物理主存地址的映射 主存分配 存储保护 主存扩充 7

3. 地址映射 (1) 什么是地址映射 主存管理——主存管理功能 址的过程，称为地址映射。 3. 地址映射 (1) 什么是地址映射 将程序地址空间中使用的逻辑地址变换成主存中的物理地 址的过程，称为地址映射。 mov r1,[500] 123 100 500 599 程序地址空间 1000 1100 1500 1599 256k-1 存储空间 程序地址空间装入主存 8

(2) 地址映射的时机和类别 主存管理——主存管理功能 ① 编程或编译时确定地址映射关系 在程序编写或程序编译时确定虚、实地址之间的对应关系，结果 是一 个不能浮动的程序模块。 ② 在程序装入时确定地址映射关系 在程序装入过程中随即进行的地址变换方式称为静态地址映射。 mov r1,[500] mov r1,[500+m] 100 500 599 m m+100 256k-1 程序地址空间 存储空间 m+500 重定位 装入程序 123 静态地址重定位示意图 9

地进行地址映射，这种地址变换方式称为动态地址映射。 主存管理——主存管理功能 ③ 在程序运行时确定地址映射关系 在程序执行期间，随着每条指令和数据的访问自动地连续 地进行地址映射，这种地址变换方式称为动态地址映射。 重定位寄存器 1000 500 逻辑地址 + mov r1 , [500] 256k-1 存储空间 1100 1500 1600 123 mov r1,[500] 100 599 程序地址空间 动态地址重定位示意图 10

4. 主存分配 (1) 构造分配用的数据结构 主存管理——主存管理功能 ④ 静态地址映射与动态地址映射的区别 静态地址映射 动态地址映射 静态地址映射 动态地址映射 在程序装入过程中 在程序执行期间 进行地址映射 进行地址映射 需软件 需硬件地址变换机构 (重定位装入程序) ( 重定位寄存器) 需花费较多CPU时间 地址变换快 不灵活 灵活 4. 主存分配 (1) 构造分配用的数据结构 主存资源信息块：等待队列；空闲区队列；主存分配程序 11

(2) 制定策略 (3) 实施主存分配与回收 主存管理——主存管理功能 ① 分配策略 —— 在众多个请求者中选择一个请求者的原则 ② 放置策略 —— 在可用资源中，选择一个空闲区的原则 ③ 调入策略 —— 决定信息装入主存的时机 预调策略：预先将信息调入主存 请调策略：当需要信息时，将信息调入主存 ④ 淘汰策略 —— 在主存中没有可用的空闲区 (对某一程序而言)时，决定哪些信息从主存中移走，即确定淘汰已占用的内存区的原则。 (3) 实施主存分配与回收 12

5. 主存扩充 (1) 可行性 (2) 实现方法 (3) 虚拟存储器 主存管理——主存管理功能 局部性特征 5. 主存扩充 (1) 可行性 (2) 实现方法 程序的全部代码和数据存放在辅存中； 将程序当前执行所涉及的那部分程序代码放入主存中； 程序执行时，当所需信息不在主存，由操作系统和硬件相 配合来完成主存从辅存中调入信息，程序继续执行。 (3) 虚拟存储器 局部性特征 13

主存管理——主存管理功能 ① 什么是虚拟存储器 ② 虚拟存储器的核心 ③ 实现虚拟存储器的物质基础 由操作系统和硬件相配合来完成主存和辅存之间的信息的动态调度。 这样的计算机系统好像为用户提供了一个其存储容量比实际主存大得 多的存储器，这个存储器称为虚拟存储器。 ② 虚拟存储器的核心 逻辑地址与物理地址分开 存储空间与虚地址空间分开 提供地址变换机构 ③ 实现虚拟存储器的物质基础 有相当容量的辅存： 足以存放应用程序的虚地址空间 有一定容量的主存： 存放进入主存的多进程的信息 地址变换机构 14

6. 存储保护 (1) 什么是存储保护 (2) 实现方法 主存管理——主存管理功能 为了互不影响，必须由硬件 (软件配合)保证各用户程序只 6. 存储保护 (1) 什么是存储保护 在多用户环境中，主存储器按区分配给各用户程序使用。 为了互不影响，必须由硬件 (软件配合)保证各用户程序只 能在给定的存储区域内活动，这种措施叫做存储保护。 (2) 实现方法 界地址保护 存储键保护 15

主存管理——主存管理功能 界地址保护 ① 上下界防护 如何设置上下界寄存器内容 ？ 如何判断是否越界 ？ 允许访问； 否则发生越界中断 例：程序大小为4KB，主存首址为20KB。 mov r1 , [500] 123 20KB 256KB1 存储空间 24KB 如何设置上下界寄存器内容 ？ 如何判断是否越界 ？ 若 20KB≤D＜24KB 允许访问； 否则发生越界中断 下界寄存器 20KB 上界寄存器 24KB 界限寄存器保护示意图 16

主存管理——主存管理功能 ② 基地址、限长防护 如何设置基址、限长寄存器内容 ？ 如何判断是否越界 ？ 若 逻辑地址 ＜ 4KB 允许访问； 例：程序大小为4KB，主存首址为20KB。 mov r1 , [500] 123 20KB 256KB1 存储空间 24KB 如何设置基址、限长寄存器内容 ？ 如何判断是否越界 ？ 若 逻辑地址 ＜ 4KB 允许访问； 否则发生越界中断 基址寄存器 20KB 限长寄存器 4KB 界限寄存器保护示意图 17

主存管理——分区存储管理 分区存储管理

1. 动态分区分配 (1) 什么是动态分区分配 (2) 动态分区的分配、回收过程 主存管理——分区存储管理 分区。 ① 动态分区的分配过程 1. 动态分区分配 (1) 什么是动态分区分配 在处理程序的过程中，建立分区，依用户请求的大小分配 分区。 (2) 动态分区的分配、回收过程 ① 动态分区的分配过程 18

主存管理——分区存储管理 os os os os os 256KB1 主存 20KB 20KB 52KB 256KB1 主存 20KB 256KB1 主存 20KB os 20KB 52KB 256KB1 主存 os 程序1 20KB 52KB 66KB 256KB1 主存 os 程序1 程序2 20KB 52KB 66KB 130KB 256KB1 主存 os 程序1 程序2 程序3 20KB 52KB 66KB 130KB 230KB 256KB1 主存 os 程序1 程序2 程序3 程序4 程序1申请 32KB 程序2申请 14KB 程序3申请 64KB 程序4申请 100KB 程序5申请 50KB 动态分区分配示意图 19

主存管理——分区存储管理 ② 动态分区的回收过程 os os os 20KB 52KB 66KB 130KB 230KB 256KB1 52KB 66KB 130KB 230KB 256KB1 主存 程序1 程序2 程序3 程序4 os 20KB 52KB 66KB 130KB 230KB 256KB1 主存 程序1 程序3 程序4 os 20KB 52KB 66KB 130KB 230KB 256KB1 主存 os 程序1 程序3 程序2 完成 程序4 完成 动态分区分配中的存储区的释放 20

(3) 分区分配数据结构 主存管理——分区存储管理 ① 主存资源信息块 (M_RIB) ② 分区描述器 (PD) 等待队列头指针 空闲区队列头指针 主存分配程序入口地址 M_RIB 分配标志 flag 大小 size 勾链字 next PD flag： 为 0 —— 空闲区 为 1 —— 已分配区 size： 分区大小 next：空闲区——自由主存队列中的勾链字 已分配区——此项为零 21

主存管理——分区存储管理 ③ 空闲区队列结构 os m-rib 20KB 52KB 程序1 52KB 14KB 26KB 230KB 52KB 66KB 130KB 230KB 256KB1 主存 os 程序1 程序3 程序4 52KB m-rib 空闲区队列 230KB 14KB 26KB  动态分区的空闲区队列结构 22

2. 分区的分配与回收 (1) 分区分配思路 主存管理——分区存储管理 ① 寻找空闲块 依申请者所要求的主存区的大小，分区分配程序在自由主 2. 分区的分配与回收 (1) 分区分配思路 ① 寻找空闲块 依申请者所要求的主存区的大小，分区分配程序在自由主 存队列中找一个满足用户需要的空闲块； ② 若找到了所需的空闲区，有两种情况 ⅰ 空闲区与要求的大小相等，将该空闲区分配并从队列中 摘除； ⅱ 空闲区大于所要求的的大小，将空闲区分为两部分：一 部分成为已分配区，建立已分配区的描述器；剩下部分 仍为空闲区。返回所分配区域的首址； ③ 否则，告之不能满足要求。 23

建立一个新的空闲区，并加入到空闲区队列中。 主存管理——分区存储管理 (2) 分区回收思路 ① 检查释放分区 (即为回收分区)在主存中的邻接情况 若上、下邻接空闲区，则合并，成为一个连续的空闲区 ② 若回收分区不与任何空闲区相邻接 建立一个新的空闲区，并加入到空闲区队列中。 24

3. 放置策略 (1) 什么是放置策略 主存管理——分区存储管理 选择空闲区的策略，称为放置策略。 常用的放置策略—— 3. 放置策略 (1) 什么是放置策略 选择空闲区的策略，称为放置策略。 常用的放置策略—— 首次匹配 (首次适应算法) 最佳匹配 (最佳适应算法) 最坏匹配 (最坏适应算法) 25

(2) 首次适应算法 ① 什么是首次适应算法 主存管理——分区存储管理 首次适应算法是将输入的程序放置到主存里第一个足够装 入它的地址最低的空闲区中。 在使用 30KB 5KB 46KB 0KB 20KB 100KB 160KB 210KB 256KB-1 主存 os 程序A 18KB ② 空闲区队列结构 空闲区地址由低到高排序 ③ 首次适应算法的特点 尽可能地利用存储器中低地 址的空闲区，而尽量保 存高地址的空闲区。 三种放置策略的图解 首次适应算法 26

(3) 最佳适应算法 主存管理——分区存储管理 ① 什么是最佳适应算法 最佳适应算法是将输入的程序放置到主存中与它所需大小 最接近的空闲区中。 在使用 30KB 5KB 46KB 0KB 20KB 100KB 160KB 210KB 256KB-1 主存 os ② 空闲区队列结构 空闲区大小由小到大排序 ③ 最佳适应算法的特点 尽可能地利用存储器中小的 空闲区，而尽量保存大的空 闲区。 程序A 18KB 三种放置策略的图解 最佳适应算法 27

(4) 最坏适应算法 主存管理——分区存储管理 ① 什么是最坏适应算法 最坏适应算法是将输入的程序放置到主存中与它所需大小 差距最大的空闲区中。 在使用 30KB 5KB 46KB 0KB 20KB 100KB 160KB 210KB 256KB-1 主存 os ② 空闲区队列结构 空闲区大小由大到小排序 ③ 最坏适应算法的特点 尽可能地利用存储器中大 的空闲区。 程序A 18KB 三种放置策略的图解 最坏适应算法 28

(5) 三种放置策略的讨论 主存管理——分区存储管理 ① 题例 程序A要求18KB；程序B要求25KB；程序C要求30KB。 用首次适应算法、最佳适应算法、最坏适应算法来处理程 序序列，看哪种算法合适。 29

② 首次适应算法、最佳适应算法、最坏适应算法的队列结构 主存管理——分区存储管理 ② 首次适应算法、最佳适应算法、最坏适应算法的队列结构 (a) 首次适应算法的空闲区队列 20KB 30KB 100KB 160KB 5KB 210KB 46KB  (b) 最佳适应算法的空闲区队列 (c) 最坏适应算法的空闲区队列 在使用 30KB 5KB 46KB 0KB 20KB 100KB 160KB 210KB 256KB-1 主存 os 主存分布示意图 30

主存管理——分区存储管理 ⅰ 首次适应算法 程序A要求18KB 程序B要求25KB 程序C要求30KB 首次适应算法对该作业序列是不合适的 在使用 30KB 5KB 46KB 0KB 20KB 100KB 160KB 210KB 256KB-1 主存 os (a) 首次适应算法的空闲区队列 20KB 30KB 100KB 160KB 5KB 210KB 46KB  程序A要求18KB 程序B要求25KB 程序C要求30KB 首次适应算法对该作业序列是不合适的 主存分布示意图 31

主存管理——分区存储管理 ⅱ 最佳适应算法 程序A要求18KB 程序B要求25KB 程序C要求30KB 最佳适应算法对该程序序列是合适的 5KB 100KB 20KB 30KB 210KB 46KB  在使用 30KB 5KB 46KB 0KB 20KB 100KB 160KB 210KB 256KB-1 主存 os 程序A要求18KB 程序B要求25KB 程序C要求30KB 最佳适应算法对该程序序列是合适的 主存分布示意图 32

主存管理——分区存储管理 ⅲ 最坏适应算法 程序A要求18KB 程序B要求25KB 程序C要求30KB 最坏适应算法对该程序序列是不合适的 os 在使用 30KB 5KB 46KB 0KB 20KB 100KB 160KB 210KB 256KB-1 主存 (c) 最坏适应算法的空闲区队列 210KB 46KB 20KB 30KB 100KB 160KB 5KB  程序A要求18KB 程序B要求25KB 程序C要求30KB 最坏适应算法对该程序序列是不合适的 主存分布示意图 33

4. 碎片问题及拼接技术 (1) 什么是碎片问题 在已分配区之间存在着的一些没有被充分利用的空闲区。 (2) 什么是拼接技术 主存管理——分区存储管理 4. 碎片问题及拼接技术 (1) 什么是碎片问题 在已分配区之间存在着的一些没有被充分利用的空闲区。 如何解决碎片问题？ 20KB 54KB 58KB 135KB 254KB 256KB1 主存 138KB 程序2 os 程序3 程序１ 拼接前 20KB 54KB 131KB 247KB 256KB1 主存 os 程序１ 程序2 程序3 拼接后 (2) 什么是拼接技术 所谓拼接技术是指移动存储器中某些已分配区中的信息，使本来分散的空闲区连成一个大的 空闲区。 分区分配中的存储区拼接 34

主存管理——页式存储管理 页式存储管理

1. 页式系统的基本概念 (1) 页面 (3) 页面与主存块的关系 主存管理——页式存储管理 成大小相等的片，称为页 面，又称为虚页。 1. 页式系统的基本概念 (1) 页面 程序的地址空间被等分 成大小相等的片，称为页 面，又称为虚页。 (2) 主存块 主存被等分成大小相等的 片，称为主存块，又称为 实页。 (3) 页面与主存块的关系 2KB 4KB 254KB 256KB1 6KB 0页 1页 2页 3页 主存 程序地址空间 等分主存和虚地址空间 35

(4) 页表 主存管理——页式存储管理 ① 什么是页表 为了实现从地址空间到物理主存的映象，系统建立的记 录页与内存块之间对应关系的地址变换的机构称为页面 映像表，简称页表。 ② 页表的组成 ⅰ 高速缓冲存储器 ： 地址变换速度快，但成本较高 ⅱ 主存区域 ：地址变换速度比硬件慢，成本较低 36

(5) 分页映像存储的例 主存管理——页式存储管理 os 1KB 2KB 3KB1 主存 程序2地址空间 3KB 4KB 5KB 6KB 1KB 2KB 3KB1 主存 程序2地址空间 3KB 4KB 5KB 6KB 7KB 8KB 9KB 10KB1 2KB1 程序1地址空间 1KB1 程序3地址空间 5 1 6 页号 块号 2 4 8 7 程序1页表 程序2页表 程序3页表 os 分页映像存储 37

2. 页式地址变换 (1) 页表 (2) 虚地址结构 主存管理——页式存储管理 记录页与块之间对应关系的地址变换的机构。 2. 页式地址变换 (1) 页表 记录页与块之间对应关系的地址变换的机构。 (2) 虚地址结构 当CPU给出的虚地址长度为16位，页面大小为1KB时， 在分页系统中地址结构的格式如下： mov r1 , [2500] 123 1KB 2KB 3KB1 程序2地址空间 p w 15 10 9 0 页号P 页内位移W 虚地址结构 38

(3) 页式地址变换 主存管理——页式存储管理 ① 页式地址变换的例 程序2地址空间中，设100号单元处有如下指令： mov r1,[2500]。当这条指令执行时，如何进行正确的地址 变换。 mov r1 , [2500] 123 1KB 2KB 3KB1 程序2地址空间 2500 → 2×1024 + 452 p=2 w=452 0000100111000100 000010 0111000100 39

主存管理——页式存储管理 ② 页式地址变换过程 os 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 0 页号P 页内位移W 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 0 15 10 9 0 页号P 页内位移W 2500 1KB 主存 2KB 3KB 4KB 5KB 6KB 7KB 8KB 9KB 10KB1 os mov r1 , [2500] 123 第1页 mov r1 , [2500] 123 1KB 2KB 3KB1 程序2地址空间 页表始址寄存器 + 页号P 页内位移W 15 10 9 0 0 0 0 1 1 1 0 1 1 1 0 0 0 1 0 0 7×1024+452 =7620 2 1 4 7 页表 页式地址变换过程 40

ⅱ 由分页机构自动地把逻辑地址分为两部分，得到页号p 和页内相对位移w (p =2， w =452)； 主存管理——页式存储管理 ③ 页式地址变换步骤 ⅰ CPU给出操作数地址 (为2500) ； ⅱ 由分页机构自动地把逻辑地址分为两部分，得到页号p 和页内相对位移w (p =2， w =452)； ⅲ 根据页表始址寄存器指示的页表始地址，以页号为索 引，找到第2页所对应的块号 (为7) ； ⅳ 将块号b和页内位移量w拼接在一起，就形成了访问主 存的物理地址 (71024+452=7620) 41

(4) 采用联想存储器加快查表速度 主存管理——页式存储管理 ① 什么是联想存储器 高速、小容量半导体存储部件，又称缓冲存储器。 ② 快表 在缓冲存储器中存放正在运行的进程当前用到的页号和对 应的块号，又称为快表。 42

主存管理——页式存储管理 ③ 利用快表进行地址映射 a P w 仅在联想映像不匹配时进行 + 联想存储器 页号 首 先 选 择 p b b w 首 先 选 择 联想存储器 所有页表在主存中 物理地址 p b ┇ a+p 联想寄存器和主存页表相结合的分页地址变换 43

3. 请调页面的机制 (1) 两种页式系统 (2) 扩充页表功能 主存管理——页式存储管理 3. 请调页面的机制 (1) 两种页式系统 ① 简单页式系统：装入一个程序的全部页面才能投入运行。 ② 请求页式系统： 装入一个程序的部分页面即可投入运行。 请求页式系统需解决的问题 (2) 扩充页表功能 页号 主存块号 中断位 辅存地址 中断位i ： 标识该页是否在主存 若i=1，表示此页不在主存；若i=0，表示该页在主存 辅存地址 ：该页面在辅存的位置 44

(3) 缺页处理 主存管理——页式存储管理 ① 程序2在请求分页系统中的存储映像 1KB 主存 2KB 3KB 4KB 5KB 6KB 1KB 主存 2KB 3KB 4KB 5KB 6KB 7KB 8KB 9KB 10KB1 2 1 4 程序2页表 os 程序2 第 1页 程序2 第 0页 3 页号 辅存地址 中断位 块号 地址 1KB 2KB 4KB1 程序2地址空间 mov r1,[2120] add r1,[3410] 006251 006802 3KB 程序2在请求分页系统中的存储映像 45

主存管理——页式存储管理 ② 缺页处理的例 程序2的主存块数为 m2=3，讨论程序执行 “mov r1，[2120］”指令时的情况。 CPU产生的虚地址为2120 分页机构得 p=2，w=72 查页表。该页中断位i=1 发生缺页中断 ！ 1KB 2KB 4KB1 程序2地址空间 mov r1,[2120] add r1,[3410] 006251 006802 3KB 如主存中有空白块，且nm 则直接调入 如主存中无空白块，或n  m ，则需淘汰 该程序在主存中的一页 46

主存管理——页式存储管理 ③ 缺页处理过程图示 启动要处理的指令 给出虚地址 准备执行下条指令 得到页号 执行完该指令 该页在主存? 硬件 有空闲块? 缺页中断 执行完该指令 准备执行下条指令 选一页淘汰 从外存读入所需的页 调整存储分配表和页表 重新启动被中断的指令 要重写入? 该页写入外存 Y N 硬件 软件 指令执行步骤和缺页中断处理过程 47

4. 淘汰机制与策略 (1) 什么是淘汰策略 (2) 扩充页表功能 主存管理——页式存储管理 4. 淘汰机制与策略 (1) 什么是淘汰策略 用来选择淘汰哪一页的规则叫做置换策略，或称淘汰算法。 如何决定淘汰哪一页？ (2) 扩充页表功能 页 号 主存块号 中断位 辅存地址 引用位 改变位 ① 引用位 —— 标识该页最近是否被访问 为“0”—— 该页没有被访问；为“1”—— 该页已被访问 ② 改变位 —— 表示该页是否被修改 为“0”—— 该页未被修改；为“1”—— 该页已被修改 48

(3) 颠簸 (4) 缺 页中断率 主存管理——页式存储管理 颠簸(thrashing)，又称为“抖动”。 简单地说，导致系统效率急剧下降的主存和辅存之间的 频繁页面置换现像称为“抖动”。 (4) 缺 页中断率 假定程序p共有n页，系统分配m块，有 1≤m≤n； 若程序p在运行中：成功的访问次数为s，不成功的访 问次数为f； 缺页中断率： f′=f/ (s+ f) f′= f (r，m，p)； r：置换算法；m：系统分配的块数； p：程序特征 49

(5) 常用的置换算法 主存管理——页式存储管理 ① 最佳算法(OPT算法) 当要调入一新页而必须先淘汰一旧页时，所淘汰的那一页 应是以后不再要用的，或者是在最长的时间以后才会用到 的那页。 50

总是选择在主存中居留时间最长 (即最早进入主存)的一 页淘汰。 ⅱ 先进先出淘汰算法的实现 建立一个页面进入主存的先后次序表； 主存管理——页式存储管理 ② 先进先出淘汰算法(FIFO算法) ⅰ 什么是先进先出淘汰算法 总是选择在主存中居留时间最长 (即最早进入主存)的一 页淘汰。 ⅱ 先进先出淘汰算法的实现 建立一个页面进入主存的先后次序表； 建立一个替换指针，指向最早进入主存的页面； 当需要置换一页时，选择替换指向的那一页，然后调 整替换指针的内容。 51

主存管理——页式存储管理 ⅲ 页号表 页号表记录页面进入 主存的先后次序： 2451 置换第2页 将第2页改为6 替换指针指向第4页 指向最老的一页 页号 2 4 5 1 6 当要调入第6页时： 置换第2页 将第2页改为6 替换指针指向第4页 先进先出淘汰算法图例 52

主存管理——页式存储管理 ⅳ 在存储分块表中建立次序表 在存储分块表中记录页面进 入主存的先后次序： 4512 如何处理 ? 7 1 2 3 4 5 6  替换指针 块号 页号 指针 ⅳ 在存储分块表中建立次序表 在存储分块表中记录页面进 入主存的先后次序： 4512 当要调入第6页时： 如何处理 ? 512  6 7 1 2 3 4 5 6  替换指针 块号 页号 指针 先进先出淘汰算法存储块构造 53

当要淘汰一页时，选择时间最长的一页淘汰。 要精确实现很困难 硬件方法：采用计数器 软件方法：采用页号栈 主存管理——页式存储管理 ③ 最久未使用淘汰算法(LRU算法) ⅰ 什么是最久未使用淘汰算法 总是选择最长时间未被使用的那一页淘汰。 ⅱ 最久未使用淘汰算法的实现 用引用位考察页面的使用情况； 当访问页面时，将引用位置1，并记时； 当要淘汰一页时，选择时间最长的一页淘汰。 要精确实现很困难 硬件方法：采用计数器 软件方法：采用页号栈 54

主存管理——页式存储管理 ⅲ 软件方法：采用页号栈 页面访问轨迹：451 2 5 6 4 5 1 2 4 1 2 5 1 2 5 访问第5页 访问第6页 淘汰第4页 访问4、5、1、2页后栈的内容 访问第5页后，调整栈的内容 访问第6页后，栈的内容 用页号栈记录最近访问的页 55

主存管理——页式存储管理 ④ LRU近似淘汰算法 ⅰ 流程图 入口 读出替换指针指向的块号 移动指针指向下一个存储块 置引用位为0 引用位为0 ? 选择该页淘汰，记录该页的页号、块号 将该页所在的块号送到替换指针 返回 置引用位为0 Y N LRU近似算法流程图 56

主存管理——页式存储管理 ⅱ LRU近似淘汰算法举例 当要调入第6页时，如何处理 ? 块号 页号 引用位 指针 块号 页号 引用位 指针 1 7 1 2 3 4 5 6 替换指针 块号 页号 引用位 指针 7 1 2 3 4 5 6 替换指针 块号 页号 引用位 指针 LRU近似算法举例 当要调入第6页时，如何处理 ? 57

主存管理——段页式存储管理 段页式存储管理

1. 段式地址空间 (1) 什么是段 (2) 程序地址空间 主存管理——段页式存储管理 1. 段式地址空间 (1) 什么是段 分段是程序中自然划分的一组逻辑意义完整的信息集合。 分段的例：代码分段、数据分段、栈段页。 (2) 程序地址空间 由若干个逻辑分段组成，每个分段有自己的名字，对于一个分段而 言，它是一个连续的地址区。 code_addr 4KB1 代码分段 data_addr 3KB1 数据分段 stack_addr 2KB1 栈段 具有段式地址结构的程序地址空间 58

2. 段式地址变换 (3) 段式地址结构 主存管理——段页式存储管理 段式地址步骤 取出程序地址(s，w)； 用s检索段表； L B s w B+w 第S段 段号 段内位移 段号 长度 基址 2. 段式地址变换 段式地址步骤 取出程序地址(s，w)； 用s检索段表； 如w＜0或w≥L则主存越界； (B＋w)即为所需主存 地址 段式地址变换构 59

3. 页式系统与段式系统的区别 (1) 用户地址空间的区别 (2) 分段和页面的区别 主存管理——段页式存储管理 3. 页式系统与段式系统的区别 (1) 用户地址空间的区别 ① 页式系统中用户地址空间： 一维地址空间 ② 段式系统中用户地址空间： 二维地址空间 (2) 分段和页面的区别 分段 页面 信息的逻辑划分 信息的物理划分 段长是可变的 页的大小是固定的 用户可见 用户不可见 w字段的溢出将 w字段的溢出自动加 产生越界中断 入到页号中 60

4. 段页式系统 (1) 段页式地址结构的程序地址空间 主存管理——段页式存储管理 划分页面，就形成了段页式存储管理。 4. 段页式系统 在段式存储管理中结合分页存储管理技术，在一个分段内 划分页面，就形成了段页式存储管理。 (1) 段页式地址结构的程序地址空间 code_addr 4KB1 代码分段 data_addr 3KB1 数据分段 stack_addr 2KB1 栈段 段页式地址结构 61

(2) 段页式系统中段表、页表与主存的关系 主存管理——段页式存储管理 1 n 段号 页表长度 页表始址 2 3 ┆ 页号 块号 其他 1 n 段号 页表长度 页表始址 2 3 ┆ 页号 块号 其他 0段页表 主存 段表  1段页表 段页式管理中的段表、页表和主存的关系 62

主存管理——小结 第6章 主存管理 小结

主存管理——小结 基本概念 虚、实分离 地址映射 虚存 存储保护 逻辑地址 作业地址空间 物理地址 存储空间 定义 逻辑地址 作业地址空间 物理地址 存储空间 地址映射 定义 类型——静态地址重定位 定义 实现 动态地址重定位 定义 实现 虚存 存储保护 界地址保护的实现方法 62

主存管理——小结 分区存储管理 分区分配中的数据结构 放置策略 分区的缺点及解决 空闲区队列结构 首次适应算法、最佳适应算法、最坏适应算法 的定义、特点 三种放置策略的讨论 分区的缺点及解决 碎片与拼接 63

主存管理——小结 页式存储管理 页式地址变换 请调策略 淘汰策略 页表 虚地址结构 页式地址变换过程 扩充页表功能 —— 中断位 辅存地址 页表 虚地址结构 页式地址变换过程 请调策略 扩充页表功能 —— 中断位 辅存地址 缺页处理 淘汰策略 扩充页表功能 —— 引用位 改变位 抖动 置换算法 定义 先进先出淘汰算法、最久未使用淘汰算法 64

主存管理——小结 段页式存储管理 段式系统的二维地址结构 段页式系统中段表、页表与主存的关系 65