1、 第七第七章章 主存管理主存管理（一）（一） 主存的共享方式主存的共享方式（二）（二） 主存管理的功能主存管理的功能（三）（三） 分区存储管理技术分区存储管理技术（四）（四） 页式存储管理技术页式存储管理技术（五）（五） 段式及段页式存储管理技术段式及段页式存储管理技术2计算机系统存储结构计算机系统存储结构外存(secondary storage)DOS核心命令处理程序内存(primary storage)快速缓存(cache)寄存器(register)内存管理的目的内存管理的目的n操作系统的操作系统的“方便方便”性性n便于用户装入程序，无须了解底层细节便于用户装入程序，无须了解底层细节n可实
2、现动态的存储空间伸缩，适应不同程序的需要可实现动态的存储空间伸缩，适应不同程序的需要n操作系统的操作系统的“合理合理”性性n合理分配内存空间，保证多道程序的顺利运行合理分配内存空间，保证多道程序的顺利运行n合理保护内存空间，防止各种可能的破坏泄漏合理保护内存空间，防止各种可能的破坏泄漏n操作系统的操作系统的“有效性有效性”n有效保持内存空间的可用性，防止对资源的浪费有效保持内存空间的可用性，防止对资源的浪费n有效实现有效实现“小空间大容量小空间大容量”，提高计算机的适应性，提高计算机的适应性n有效配合有效配合CPUCPU的调度过程，实现系统运行的稳定的调度过程，实现系统运行的稳定（一）（一）
3、主存的共享方式主存的共享方式n内存储器（简称内存、主存、物理存储器）内存储器（简称内存、主存、物理存储器） 处理机处理机能直接能直接访问的存储器。用来存放系统访问的存储器。用来存放系统和用户的程序和数据，其特点是和用户的程序和数据，其特点是存取速度快存取速度快，断断电信息丢失电信息丢失。主存的共享方式包含三种：主存的共享方式包含三种：n 大小不等的区域大小不等的区域 分区存储管理分区存储管理 分段存储管理分段存储管理n 大小相等的片大小相等的片 页式存储管理页式存储管理n 两者结合两者结合 段页式存储管理段页式存储管理（二）主存管理的功能（二）主存管理的功能一一. . 几个概念几个概念1 1、
4、物理、物理地址（绝对地址地址（绝对地址、实、实地址）：地址）：把把内存分成若干个大小相等的存储单元，内存分成若干个大小相等的存储单元，每个单元给一个编号，这个编号称为内每个单元给一个编号，这个编号称为内存地址，是计算机主存单元的真实地址。存地址，是计算机主存单元的真实地址。存储单元占存储单元占8位，称作字节（位，称作字节（byte）。）。2. 2. 物理地址空间：物理地址空间：物理物理地址的集合称为物理地址空间（地址的集合称为物理地址空间（主主存地址空间存地址空间），它是一个一维的线性空），它是一个一维的线性空间。间。3. 3. 逻辑地址（相对地址、虚地址）逻辑地址（相对地址、虚地址）: :用
5、户编程序时所用的地址。基本单用户编程序时所用的地址。基本单位可与内存的基本单位相同，也可位可与内存的基本单位相同，也可以不相同。以不相同。4. 4. 逻辑地址空间（作业地址空间、逻辑地址空间（作业地址空间、虚地址空间）虚地址空间）: :用户的程序地址的集合称为逻辑地用户的程序地址的集合称为逻辑地址空间，它的编址总是从址空间，它的编址总是从0开始的。开始的。作业地址空间作业地址空间01n-1二二. . 主存管理的功能主存管理的功能1. 地址映射地址映射将程序地址空间中使用的逻辑地址变换成主存中的地址的过程。将程序地址空间中使用的逻辑地址变换成主存中的地址的过程。2. 主存分配主存分配 按照一定的
6、算法把某一空闲的主存区分配给作业或进程。按照一定的算法把某一空闲的主存区分配给作业或进程。3. 存储保护存储保护 保证用户程序保证用户程序(或进程映象或进程映象)在各自的存储区域内操作，互不干扰。在各自的存储区域内操作，互不干扰。4. 主存扩充（提供虚拟存储技术）主存扩充（提供虚拟存储技术）向用户提供一种不受物理存储器大小和结构限制的用户编程时使用的向用户提供一种不受物理存储器大小和结构限制的用户编程时使用的存储器。即使在用户程序比主存容量还要大的情况下，程序也能正确存储器。即使在用户程序比主存容量还要大的情况下，程序也能正确运行。运行。1. 1. 主存功能主存功能地址映射地址映射主存空间01
7、m-1作业1地址空间01n-1作业 i 地址空间01k-1 （1）为什么要进行地址映射）为什么要进行地址映射 作业的相应进程在处理机上运行时，所要访问的指令作业的相应进程在处理机上运行时，所要访问的指令和数据的物理地址和作业地址空间中的地址是不同的和数据的物理地址和作业地址空间中的地址是不同的。mov r1,500123mov r1,50012301005005990 1000110015001599256k-1作业地址空间作业地址空间存储空间存储空间将将500号单号单元处的数元处的数据据123送到送到寄存器寄存器r1中中（2）地址映射的定义）地址映射的定义将程序地址空间中使用的逻辑地址变换成
8、主存中的地址的将程序地址空间中使用的逻辑地址变换成主存中的地址的过程称为地址映射。有时也称为地址重定位。过程称为地址映射。有时也称为地址重定位。 （3 3）地址映射的方式）地址映射的方式编程或编译时确定地址映射关系编程或编译时确定地址映射关系静态地址映射静态地址映射动态地址映射动态地址映射静态地理映射定义：静态地理映射定义： 在在作业装入过程中作业装入过程中随即进行的地址变换方式称为随即进行的地址变换方式称为静态重定位或静态重定位或静态地址映射静态地址映射。mov r1,500123mov r1,500+m12301005005990mm+100256k-1作业地址空间作业地址空间存储空间存储
9、空间m+500重定位重定位装入程序装入程序n动态地址映射定义：动态地址映射定义： 在在程序运行时程序运行时确定地址映射关系。在程序执行期间，随着确定地址映射关系。在程序执行期间，随着每条指令和数据的访问自动地连续地进行地址映射。每条指令和数据的访问自动地连续地进行地址映射。mov r1,5001230100500599作业地址空间0 mov r1 , 500 1231000256k-1存储空间110015001600重定位寄存器 1000500逻辑地址+静态地址映射与动态地址映射的区别静态地址映射与动态地址映射的区别静态地址映射静态地址映射动态地址映射动态地址映射在作业装入过程中进行地址映射在
10、作业装入过程中进行地址映射 需软件变换机构重定位装入程序需软件变换机构重定位装入程序 需硬件地址变换机构重定位装入需硬件地址变换机构重定位装入程序程序 需花费较多需花费较多CPU时间时间 地址变换快地址变换快不灵活不灵活 灵活灵活构造构造分配用的数据结构分配用的数据结构 主存主存资源信息资源信息块（块（M_RIB）、空闲区队列等等）、空闲区队列等等 制定分配策略制定分配策略 2 2、主存功能、主存功能主存分配主存分配 实施主存分配与回收实施主存分配与回收 主存扩充也就是主存扩充也就是提供虚拟存储器提供虚拟存储器 1）问题的提出）问题的提出3、主存扩充、主存扩充 n物理存储器容量是有限的，用户程
11、序的大小，可能比内存物理存储器容量是有限的，用户程序的大小，可能比内存容量小，也可能比内存容量大，有时候要大得多。容量小，也可能比内存容量大，有时候要大得多。n在在主存容量十分紧张主存容量十分紧张的情况下，的情况下，如何如何让让用户使用计算机不受主存容量的限制？用户使用计算机不受主存容量的限制？2 2）解决问题的思路）解决问题的思路 装入部分程序地址空间，它还能正确地执行？装入部分程序地址空间，它还能正确地执行？3 3）实现方法）实现方法 程序的全部代码和数据存放在辅存中；程序的全部代码和数据存放在辅存中； 将程序当前执行所涉及的那部分程序代码放入主将程序当前执行所涉及的那部分程序代码放入主存
12、中；存中； 程序执行时，当所需信息不在主存，由操作系统程序执行时，当所需信息不在主存，由操作系统和硬件相配合来完成主存从辅存中调入信息，程和硬件相配合来完成主存从辅存中调入信息，程序继续执行。序继续执行。 4. 4. 什么是虚拟存储器什么是虚拟存储器 n由操作系统和硬件相配合来完成主存和辅存之间的信由操作系统和硬件相配合来完成主存和辅存之间的信息的动态调度。这样的计算机系统好像为用户提供了息的动态调度。这样的计算机系统好像为用户提供了一个其存储容量比实际主存大得多的存储器一个其存储容量比实际主存大得多的存储器（虚拟存虚拟存储器储器）。5. 5. 虚拟存储器的核心虚拟存储器的核心 逻辑地址与物理
13、地址分开逻辑地址与物理地址分开 主存空间与地址空间分开主存空间与地址空间分开 提供地址变换机构提供地址变换机构 6. 6. 实现虚拟存储器的物质基础实现虚拟存储器的物质基础 有相当容量的辅存有相当容量的辅存 足以存放多用户的作业的地址空间足以存放多用户的作业的地址空间 有一定容量的主存有一定容量的主存 存放运行进程的当前信息存放运行进程的当前信息 地址变换机构地址变换机构4 4、存储保护、存储保护1 1）什么是存储保护）什么是存储保护在多道程序设计的环境下，系统中有系统程序和多个用户程序同在多道程序设计的环境下，系统中有系统程序和多个用户程序同时存在，时存在，如何保证用户程序不破坏系统程序，用
14、户程序之间不相如何保证用户程序不破坏系统程序，用户程序之间不相互干扰？互干扰？主存储器按区分配给各用户程序使用。为了互不影响，由硬主存储器按区分配给各用户程序使用。为了互不影响，由硬件件(软件配合软件配合)保证每道程序只能在给定的存储区域内活动，这种保证每道程序只能在给定的存储区域内活动，这种措施叫做存储保护。措施叫做存储保护。2 2）存储保护方法）存储保护方法 通常的存储保护方法通常的存储保护方法 界地址保护界地址保护和和存储键保护（不介绍）存储键保护（不介绍）n (1) 上、下界防护上、下界防护 mov r1 , 500 123020KB256KB 1存储空间存储空间24KB下界寄存器下界
15、寄存器 20KB上界寄存器上界寄存器 24KB下界寄存器：下界寄存器：存放程序装入存放程序装入内存后的开始地址内存后的开始地址上界寄存器：上界寄存器：存放程序装入存放程序装入内存后的末地址内存后的末地址判别式：判别式：下界寄存器下界寄存器 物理地址物理地址 上界寄存器上界寄存器n (2) 基地址、限长防护基地址、限长防护 mov r1 , 500 123020KB256KB 1存储空间存储空间24KB基址寄存器基址寄存器 20KB限长寄存器限长寄存器 4KB基址寄存器基址寄存器=下界寄存器下界寄存器 （首地址）首地址）限长寄存器：存放程序长度限长寄存器：存放程序长度基址基址+限长限长=上界寄存
16、器上界寄存器 （末地址）（末地址）判别式：判别式：基址寄存器基址寄存器物理地址基物理地址基址址+限长寄存器限长寄存器23作业作业w 第第7章章 第第2题题（三）（三） 分区存储管理分区存储管理分区存储管理分为：分区存储管理分为：1. 固定分区固定分区2. 动态分区（可变分区）动态分区（可变分区）25 固定分区固定分区固定分区一一. . 动态分区分配动态分区分配1. 1. 什么是动态分区分配什么是动态分区分配 在处理作业的过程中，建立分区，依用户请求的大小分在处理作业的过程中，建立分区，依用户请求的大小分配分区。配分区。 思想：分区的大小、数量和位置随内存中进程的大小思想：分区的大小、数量和位置
17、随内存中进程的大小和数量动态变化（根据作业的实际需要在装入内存时和数量动态变化（根据作业的实际需要在装入内存时动态地分配连续的内存空间）。动态地分配连续的内存空间）。 (1) 动态分区的分配过程动态分区的分配过程 20KB 0 os 作业作业1 作业作业2 作业作业3 作业作业4 52KB66KB130KB230KB256KB 1主存主存20KB 0 os 作业作业1 作业作业2 作业作业3 52KB66KB130KB256KB 1主存主存20KB 0 os 作业作业1 52KB256KB 1主存 0 os 256KB 1主存主存20KB20KB 0 os 作业作业1 作业作业2 52KB66
18、KB256KB 1主存主存作业作业1申请申请 32KB作业作业2申请申请 14KB作业作业3申请申请 64KB作业作业4申请申请 100KB作业作业5申请申请 50KB (2) 动态分区的回收过程动态分区的回收过程 20KB 0 os 作业作业1 作业作业2 作业作业3 作业作业4 52KB66KB130KB230KB256KB1主存20KB 0 os 作业作业1 作业作业3 作业作业4 52KB66KB130KB230KB256KB1主存作业2完成作业4完成20KB 0 os 作业作业1 作业作业3 52KB66KB130KB230KB256KB1主存292、分区分配机构、分区分配机构 1)
19、 主存资源信息块主存资源信息块 在动态分区方法中，描在动态分区方法中，描述主存资源的数据结构述主存资源的数据结构是主存资源信息块是主存资源信息块等待队列指针等待队列指针空闲区队列指针空闲区队列指针主存分配程序入口指针主存分配程序入口指针2) 分区描述器和空闲队列分区描述器和空闲队列 主存中的每一个分区都有相应的分区描主存中的每一个分区都有相应的分区描述器（述器（pd）说明分区的特征信息。）说明分区的特征信息。nflag： 为为 0空闲区空闲区; 为为 1已分配区已分配区 nsize： 分区大小分区大小 nnext：空闲区：空闲区自由主存队列中的勾自由主存队列中的勾链字链字;已分配区已分配区此项
20、为零此项为零m_ribpd分配标志分配标志flag分区大小分区大小size勾链字勾链字next30n自由主存队列自由主存队列 (或空闲区队列或空闲区队列) 结构结构n在主存分配中，主要讨论空闲区描述器和空闲区队列。下面是在t时刻的主存分布、空闲区描述器的内容和空闲区队列结构。 020KB os 作业1 作业3 作业4 52KB66KB130KB230KB256KB1主存 52KBm-rib 0 14KB 230KB 0 26KB 空闲区队列结构空闲区表的组织有两种方法：空闲区表的组织有两种方法：1、按空闲区大小的升序（降序）组织；、按空闲区大小的升序（降序）组织；2、按空闲区首址升序（降序）组
21、织。、按空闲区首址升序（降序）组织。3 3、分区的分配与放置策略、分区的分配与放置策略1 1）分区分配）分区分配 用户请求分配一个主存块用户请求分配一个主存块 分区分配程序在分区分配程序在自由主存队列自由主存队列中找一个满足中找一个满足用户需要的空闲块用户需要的空闲块 若找到，则返回所分配区域的首址，否则，若找到，则返回所分配区域的首址，否则， 告之不能满足要求。告之不能满足要求。2 2）放置策略）放置策略选择空闲区的策略，称为放置策略。选择空闲区的策略，称为放置策略。 空闲区表的组织有两种方法：空闲区表的组织有两种方法：1、按空闲区大小的升序（降序）组织；、按空闲区大小的升序（降序）组织；2
22、、按空闲区首址升序（降序）组织。、按空闲区首址升序（降序）组织。 根据空闲区表组织的方法的不同，有不同的放置根据空闲区表组织的方法的不同，有不同的放置策略：策略：首次适应首次适应算法、算法、最佳适应最佳适应算法和算法和最坏适应最坏适应算法三种。算法三种。33 1 1）首次适应算法）首次适应算法空闲区按起始空闲区按起始地址递增地址递增的顺序排列，将作业放到的顺序排列，将作业放到最最先先找到的空闲分区。找到的空闲分区。34 2）最佳适应算法最佳适应算法 空闲区按空闲区按由小到大由小到大的顺序排列，将作业放到满足要的顺序排列，将作业放到满足要求的求的最小最小的空闲分区。的空闲分区。 35 3）最坏适
23、应算法最坏适应算法空闲区按空闲区按由大到小由大到小的顺序排列，将作业放到满足要的顺序排列，将作业放到满足要求的求的最大最大的空闲分区。的空闲分区。几种放置策略的比较几种放置策略的比较例如：某时刻系统中有三个空闲区，其大小和首址为：(35KB，100KB)、(12KB，156KB)、(28KB，200KB)有一作业系列： (JOB1，12KB)、(JOB2，30KB)、(JOB3，28KB)用首次适应算法、最佳适应算法和最坏适应算法来处理该作业序列，看哪种算法合适？注：注：设分配时从空闲区的高地址分设分配时从空闲区的高地址分割，以保持剩余空闲区的起始地割，以保持剩余空闲区的起始地址不变。址不变。
24、 os在使用在使用在使用在使用在使用在使用在使用在使用12KB28KB0KB100KB35KB156KB200KB228KB- -135KB156KB首次适应算法首次适应算法12KB200KB28KBNULL100KB作业作业1（12KB）放到首址）放到首址100KB的空闲区的空闲区23KB156KB12KB200KB28KBNULL100KB作业作业2（30KB）不能分配）不能分配作业作业3（28KB）放到首址）放到首址200KB的空闲区的空闲区12KB200KB最佳适应算法最佳适应算法28KB100KB35KBNULL156KB作业作业1（12KB）放到首址）放到首址156KB的空闲区的空
25、闲区28KB100KB35KBNULL200KB作业作业2（30KB）放到首址）放到首址100KB的空闲区的空闲区作业作业3（28KB）放到首址）放到首址200KB的空闲区的空闲区5KB200KB28KBNULL100KB35KB200KB最坏适应算法最坏适应算法28KB156KB12KBNULL100KB作业作业1（12KB）放到首址）放到首址100KB的空闲区的空闲区作业作业2（30KB）不能继续分配）不能继续分配作业作业3（28KB）放到首址）放到首址200KB的空闲区的空闲区28KB100KB23KB156KB12KBNULL200KB四、碎片问题及拼接技术四、碎片问题及拼接技术1.
26、1. 什么是碎片问题什么是碎片问题在已分配区之间存在着的一些没有被充分利用在已分配区之间存在着的一些没有被充分利用的空闲区。的空闲区。如何解决碎片问题？如何解决碎片问题？ 2. 2. 拼接技术拼接技术所谓拼接技术是指移动存储器中某些已分配区所谓拼接技术是指移动存储器中某些已分配区中的信息，使本来分散的空闲区连成一个大的中的信息，使本来分散的空闲区连成一个大的空闲区。空闲区。41OS400KBJOB1(100KB)JOB2(200KB)0300KBJOB6(100KB)800KB700KB900KBJOB5(100KB)JOB4(100KB)JOB7(100KB)600KB1000KB1024K
27、BOS400KBJOB2(200KB)0300KBJOB6(100KB)800KB700KB900KBJOB5(100KB)JOB4(100KB)JOB7(100KB)600KB1000KB空闲(24KB)1024KB空闲(100KB)OS400KBJOB2(200KB)0300KB800KB700KB900KBJOB5(100KB)JOB7(100KB)600KB1000KB空闲(24KB)1024KB空闲(100KB)空闲(100KB)空闲(100KB)有一大小为200K的作业需要运行!空闲(24KB)分区管理的优缺点分区管理的优缺点优点：优点：n实现了多道程序实现了多道程序共享主存共享主
28、存。n实现分区管理的实现分区管理的系统设计相对简单系统设计相对简单，不需要更多的，不需要更多的系系统软硬件开销统软硬件开销。n实现实现存储保护存储保护的手段的手段也比较简单也比较简单。缺点：缺点：n主存利用不够充分主存利用不够充分。系统中总有一部分存储空间得不。系统中总有一部分存储空间得不到利用，这部分被浪费的空间叫到利用，这部分被浪费的空间叫碎片碎片。n没有实现主存的扩充问题没有实现主存的扩充问题。 当作业的地址空间大于当作业的地址空间大于存储空间时，作业无法运行。也即作业的地址空间受存储空间时，作业无法运行。也即作业的地址空间受实际存储空间限制。实际存储空间限制。（四）（四） 页式存储管理
29、页式存储管理一一. . 问题的提出问题的提出分区存储管理的主要问题是分区存储管理的主要问题是碎片碎片问题。问题。在采用分区存储管理的系统中，会形成一些非在采用分区存储管理的系统中，会形成一些非常小的分区，最终这些非常小的分区不能被系常小的分区，最终这些非常小的分区不能被系统中的任何用户（程序）利用而浪费。统中的任何用户（程序）利用而浪费。造成这样问题的主要原因是用户程序装入内存造成这样问题的主要原因是用户程序装入内存时是整体装入的，为解决这个问题，提出了分时是整体装入的，为解决这个问题，提出了分页存储管理技术。页存储管理技术。二二. . 页式系统的基本概念页式系统的基本概念1. 1. 页面页面
30、程序的地址空间被等分成大小相等的片，称为页面，又程序的地址空间被等分成大小相等的片，称为页面，又称为称为虚页虚页。2. 2. 主存块主存块主存被等分成大小相等的片，称为主存块，又称为主存被等分成大小相等的片，称为主存块，又称为实页实页。n 作业页面与主存块的关系作业页面与主存块的关系 02KB4KB254KB256KB102KB4KB6KB0页1页2页3页主存作业地址空间页表页表地址映射地址映射3. 3. 页表页表（1）什么是页表）什么是页表为了实现从地址空间到物理主存的映象，系统建立的记录页与内为了实现从地址空间到物理主存的映象，系统建立的记录页与内存块之间对应关系的地址变换的机构称为页面映
31、像表，简称页表。存块之间对应关系的地址变换的机构称为页面映像表，简称页表。 包括用户程序空间的页面与内存块的对应关系、页面的存储保护包括用户程序空间的页面与内存块的对应关系、页面的存储保护和存取控制方面的信息。和存取控制方面的信息。01KB01KB2KB3KB1主存作业2地址空间2KB3KB4KB5KB6KB7KB8KB9KB10KB101KB2KB1作业1地址空间01KB1作业3地址空间0516页号块号02140827作业1页表作业2页表作业3页表osos三三. . 页式地址变换页式地址变换1. 1. 虚地址结构虚地址结构虚地址是用户程序中的逻辑地址，它包括虚地址是用户程序中的逻辑地址，它包
32、括页号页号和和页内地页内地址址（页内位移）。（页内位移）。区分页号和页内地址的依椐是区分页号和页内地址的依椐是页的大小页的大小，页内地址占虚，页内地址占虚地址的低位部分，页号占虚地址的高位部分。地址的低位部分，页号占虚地址的高位部分。【例例】设虚地址长度为设虚地址长度为16位，页面大小为位，页面大小为1KB：页号页号 页内地址（位移量）页内地址（位移量） P W 15 10 9 049如何方便将逻辑地址线性分割求出页号如何方便将逻辑地址线性分割求出页号P和页内位移和页内位移W：v逻辑地址以十进制数给出逻辑地址以十进制数给出：页号页号P=逻辑地址逻辑地址 % 页大小页大小页内位移页内位移W=逻辑
33、地址逻辑地址 mod 页大小页大小v逻辑地址以十六进制、八进制、二进制的形式给出：逻辑地址以十六进制、八进制、二进制的形式给出：将逻辑地址转换成二进制；将逻辑地址转换成二进制；按页的大小分离出页号按页的大小分离出页号P P和位移量和位移量W W（低位部分是位移（低位部分是位移量，高位部分是页号）；量，高位部分是页号）；50【例例】：有一系统采用页式存储管理，有一作业大小：有一系统采用页式存储管理，有一作业大小是是8KB8KB，页大小为，页大小为2KB2KB。解：解：求虚地址求虚地址 34123412P P3412 3412 2048 2048 1 1W W 3412 mod 2048 3412
34、 mod 2048 13641364求求虚地址虚地址 71457145：P P7145 7145 2048 2048 3 3W W7145 mod 2048 7145 mod 2048 1001100151【例例】：有一系统采用页式存储管理，有一作业大小是：有一系统采用页式存储管理，有一作业大小是8KB8KB，页大小为页大小为2KB2KB。虚地址虚地址0AFEH0AFEH：00000000 1 1010 1111 1110010 1111 1110P P1 W1 W010 1111 1110010 1111 1110虚地址虚地址1ADDH1ADDH：0001 10001 1010 1101 1
35、101010 1101 1101P P3 W3 W010 1101 1101010 1101 1101例例1 页面大小是页面大小是1KB，虚地址是，虚地址是3BADH例例2 页面大小是页面大小是2KB，虚地址是，虚地址是3BADH532、地址变换、地址变换根据逻辑地址求物理地址的步骤：根据逻辑地址求物理地址的步骤：1）将逻辑地址）将逻辑地址线性分割线性分割求出页号求出页号P和页内位移和页内位移W：2）根据页号查页表）根据页号查页表得块号得块号B；3）物理地址物理地址=块号块号B页大小页大小+页内位移页内位移W54页表始址寄存器mov r1 ,250012301KB2KB3KB1作业2地址空间+
36、021427页表 0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 015 10 9 0页号页内位移W250001KB主存2KB3KB4KB5KB6KB7KB8KB9KB10KB1ososmov r1 , 2500123第1页块号块内位移W 15 10 9 00 0 0 1 1 10 1 1 1 0 0 0 1 0 071024+452=762055【例例】：有一系统采用页式存储管：有一系统采用页式存储管理，有一作业大小是理，有一作业大小是8KB8KB，页大，页大小为小为2KB2KB，依次装入内存的第，依次装入内存的第7 7、9 9、1010、5 5块，试将虚地址块，试将虚地址714
37、57145，34123412转换成内存地址。转换成内存地址。解：解：求虚地址求虚地址 34123412P P3412 3412 2048 2048 1 1W W 3412 mod 2048 3412 mod 2048 13641364MR=9MR=9* *2048+1364=197962048+1364=19796求虚地址求虚地址 71457145：P P7145 7145 2048 2048 3 3W W7145 mod 2048 7145 mod 2048 10011001MR=5MR=5* *2048+1001=112412048+1001=1124156【例例】：有一系统采用页式存储管
38、：有一系统采用页式存储管理，有一作业大小是理，有一作业大小是8KB8KB，页大，页大小为小为2KB2KB，依次装入内存的第，依次装入内存的第7 7、9 9、A A、5 5块，试将虚地址块，试将虚地址0AFEH0AFEH，1ADDH1ADDH转换成内存地址。转换成内存地址。解：解：求虚地址求虚地址0AFEH0AFEH的物理地址：的物理地址：00000000 1 1010 1111 1110010 1111 1110P P1 W1 W010 1111 1110010 1111 1110MRMR01000100 1 1010010 1111 11101111 11104AFEH4AFEH求虚地址求虚
39、地址1ADDH1ADDH的物理地址：的物理地址：0001 10001 1010 1101 1101010 1101 1101P P3 W3 W010 1101 1101010 1101 1101MRMR0010 10010 1010010 1101 11011101 11012ADDH2ADDH57课堂练习：课堂练习： 1、某作业、某作业J的逻辑空间为的逻辑空间为4页，每页页，每页2048B，已知该，已知该作业作业J的页表如下：的页表如下：页号：页号：0 1 2 3块号：块号：2 4 6 8 求：逻辑地址为求：逻辑地址为0A65H的物理地址。的物理地址。2、某作业有、某作业有4个页面，分别装入
40、主存的个页面，分别装入主存的3、4、6、8块中，设页面尺寸为块中，设页面尺寸为1024B（1）、写出该作业的页表；）、写出该作业的页表；（2）、求）、求mov 2100,3100指令中两个操作数的物指令中两个操作数的物理地址。理地址。四四. . 请调策略请调策略1、请调策略定义：、请调策略定义： 在页式系统中，允许一个作业程序只装入部分页在页式系统中，允许一个作业程序只装入部分页面即可投入运行，需要信息时动态调入，这种装面即可投入运行，需要信息时动态调入，这种装入信息的策略称为请调策略。入信息的策略称为请调策略。 (1) (1) 怎样发现所访问的页面在不在主存？怎样发现所访问的页面在不在主存？
41、 (2) (2) 当发现所需访问的页面不在主存时如何处理当发现所需访问的页面不在主存时如何处理? ?2. 2. 扩充页表功能扩充页表功能 中断位中断位 i i标识该页是否在主存标识该页是否在主存若若i=1，表示此页不在主存，表示此页不在主存若若i=0，表示该页在主存，表示该页在主存 辅存地址辅存地址该页面在辅存的位置该页面在辅存的位置页号页号主存块号主存块号 中断位中断位 辅存地址辅存地址n 3. 缺页处理过程缺页处理过程 （举例说明）（举例说明）n 01KB主存2KB3KB4KB5KB6KB7KB8KB9KB10KB102142作业2页表osos作业2第1页作业2第0页3页号 辅存地址 中断
42、位 块号 0011地址地址地址地址01KB2KB4KB1作业2地址空间mov r1,2120add r1,3410006251 006802 3KB作业2的主存块数为 m2=3，页面大小为1KB。 当程序执行 “mov r1，2120”时 CPU产生的虚地址为2120 分页机构得 p=2，w=72 查页表。该页中断位i=1， 则发生缺页中断缺页中断 01KB2KB4KB1作业2地址空间mov r1,2120add r1,3410006251 006802 3KB 如主存中有空白块，且如主存中有空白块，且n m 则直接调入则直接调入 如主存中无空白块，或如主存中无空白块，或n m ，则需淘汰该作
43、业在则需淘汰该作业在主存中的一页主存中的一页（其中其中n 代表作业已分配到的主存块数，代表作业已分配到的主存块数， m 为内存为作业准备的物理块数为内存为作业准备的物理块数）。）。n缺页处理流程缺页处理流程 启动要处理的指令启动要处理的指令给出虚地址给出虚地址 得到页号得到页号该页在主存该页在主存?有空闲块有空闲块? 缺页中断缺页中断执行完该指令执行完该指令 准备执行下条指令准备执行下条指令选一页淘汰选一页淘汰 从外存读入所需的页从外存读入所需的页 调整存储分配表和页表调整存储分配表和页表 重新启动被中断的指令重新启动被中断的指令 调整存储分配表和页表调整存储分配表和页表要重写入要重写入?该页
44、写入外存该页写入外存YNNY硬件硬件软件软件YN4. 4. 淘汰策略淘汰策略1. 1. 什么是淘汰策略什么是淘汰策略用来选择淘汰哪一页的规则就叫做置换策略，用来选择淘汰哪一页的规则就叫做置换策略，或称淘汰算法。或称淘汰算法。常用算法：常用算法：1 1、最优算法最优算法OPT:(OPT:(optimal page-replacement optimal page-replacement algorithm)algorithm)置换在最长时间内不会使用的页置换在最长时间内不会使用的页) )2 2、先进先出算法先进先出算法FIFOFIFO：淘汰先调入内存的页淘汰先调入内存的页3 3、最近最少使用淘汰
45、算法最近最少使用淘汰算法LRULRU：淘汰未被访问的页中时淘汰未被访问的页中时间最长的页间最长的页;(Least Recently Used);(Least Recently Used) 使用使用缺页中断率缺页中断率f衡量页面淘汰算法的优劣：衡量页面淘汰算法的优劣： ffa （a是总的页面访问次数，是总的页面访问次数，f是缺页中断次数）是缺页中断次数） 2. 2. 扩充页表的功能扩充页表的功能页表应增加相应的内容，反映该页是否在内存，在外存页表应增加相应的内容，反映该页是否在内存，在外存的位置，在内存的时间的长短等。的位置，在内存的时间的长短等。n 引用位：引用位：0 0 表示最近没有进程访问
46、表示最近没有进程访问 1 1 表示最近有进程访问表示最近有进程访问n 改变位：改变位：0 0 该页调入内存后没有修改该页调入内存后没有修改 1 1 该页调入内存后修改过该页调入内存后修改过页号 主存块号中断位辅存地址 改变位改变位引用位引用位3. 3. 颠簸颠簸n颠簸颠簸(thrashing)，又称为，又称为“抖动抖动”。简单地说，导致系统效率急剧下降的主存和辅简单地说，导致系统效率急剧下降的主存和辅存之间的频繁页面置换现像称为存之间的频繁页面置换现像称为“抖动抖动”。 OPT原理（难实现）：原理（难实现）：当要调入一新页而必须先当要调入一新页而必须先淘汰一旧页时，所淘汰的那一页应是以后不再淘
47、汰一旧页时，所淘汰的那一页应是以后不再要用的，或者是在最长的时间以后才会用到的要用的，或者是在最长的时间以后才会用到的那页。那页。 缺页率缺页率假定程序假定程序p共有共有n页，系统分配页，系统分配m块，有块，有1mn 若程序若程序p在运行中在运行中:成功的访问次数：成功的访问次数： s 不成功的访问次数：不成功的访问次数： f 则缺页中断率：则缺页中断率： f=f/ (s+ f)*100% f=f (r，m，p) 4. 页面置换算法页面置换算法OPT算法算法例：假设系统为某进程分配了例：假设系统为某进程分配了3个物理块，并考虑有个物理块，并考虑有以下的访问串：以下的访问串：7，0，1，2，0，
48、3，0，4，2，3，0，3，2，1，2，0，1，7，0，1，求缺页率。，求缺页率。 7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1缺页率缺页率f=(9/20)*100%=45% (2) 先进先出淘汰算法先进先出淘汰算法(FIFO算法算法) 1) 什么是先进先出淘汰算法什么是先进先出淘汰算法 原理：总是选择在主存中居留时间最长原理：总是选择在主存中居留时间最长(即最老即最老)的一的一页淘汰。页淘汰。 2) 先进先出淘汰算法的实现方法先进先出淘汰算法的实现方法 建立一个页面进入主存的建立一个页面进入主存的先后次序表先后次序表； 建立一个替换指针，指向最早进入主存的页
49、面；建立一个替换指针，指向最早进入主存的页面； 当需要置换一页时，选择当需要置换一页时，选择替换指向的那一页，然替换指向的那一页，然 后调整替换指针的内容。后调整替换指针的内容。69【例例】某进程的页面访问序列：某进程的页面访问序列：1、2、3、4、1、2、5、1、2、3、4、5，指出在驻留集大小分别为，指出在驻留集大小分别为3和和4时，时，使用使用FIFO置换算法的缺页率，结果说明了什么？置换算法的缺页率，结果说明了什么？（设驻留集（设驻留集M表示分给该作业的内存块数）表示分给该作业的内存块数）解：解：FIFO M3 f fa91275% M4 f101283% 70123412512345
50、t11111111222222223333334444455555512512341251345t1114334522244511332334432455122232234151112采用采用FIFO算法算法 (3) 最久未使用淘汰算法最久未使用淘汰算法(LRU算法算法) 总是选择最长时间未被使用的那一页淘汰。总是选择最长时间未被使用的那一页淘汰。 LRU算法的实现方法算法的实现方法 用引用位考察页面的使用情况用引用位考察页面的使用情况； 当访问页面时，将引用位置当访问页面时，将引用位置1，并记时，并记时； 当要淘汰一页时，选择时间最长的一页淘汰当要淘汰一页时，选择时间最长的一页淘汰。 要精确
