第7章-操作系统ppt课件-07主存管理.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,,*,,,,,,,,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,*,,,,,,,,,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,*,,,,,,,,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,宁波大学科技学院计算机系陆静,*,第七章 主存管理,（一） 主存的共享方式,（二） 主存管理的功能,（三） 分区存储管理技术,（四） 页式存储管理技术,（五） 段式及段页式存储管理技术,第七章 主存管理（一） 主存的共享方式,2,计算机系统存储结构,,2计算机系统存储结构,内存管理的目的,操作系统的,“,方便,”,性,便于用户装入程序，无须了解底层细节,可实现动态的存储空间伸缩，适应不同程序的需要,操作系统的,“,合理,”,性,合理分配内存空间，保证多道程序的顺利运行,合理保护内存空间，防止各种可能的破坏泄漏,操作系统的,“,有效性,”,有效保持内存空间的可用性，防止对资源的浪费,有效实现“小空间大容量”，提高计算机的适应性,有效配合,CPU,的调度过程，实现系统运行的稳定,,内存管理的目的操作系统的“方便”性,（一） 主存的共享方式,内存储器（简称内存、主存、物理存储器）,处理机,能直接,访问的存储器。

用来存放系统和用户的程序和数据，其特点是,存取速度快,，,断电信息丢失,一） 主存的共享方式内存储器（简称内存、主存、物理存储器）,主存的共享方式包含三种：,,大小不等的区域,——,,分区存储管理,分段存储管理,,大小相等的片,——,,页式存储管理,,两者结合,——,,段页式存储管理,主存的共享方式包含三种： 大小不等的区域—— 分区存储管理,（二）主存管理的功能,一,.,几个概念,,1,、物理地址（绝对地址、实地址）：,把内存分成若干个大小相等的存储单元，每个单元给一个编号，这个编号称为内存地址，是计算机主存单元的真实地址存储单元占,8,位，称作字节（,byte,）2.,物理地址空间：,物理地址的集合称为物理地址空间（,主存地址空间,），它是一个一维的线性空间二）主存管理的功能一. 几个概念,3.,逻辑地址（相对地址、虚地址）,:,用户编程序时所用的地址基本单位可与内存的基本单位相同，也可以不相同4.,逻辑地址空间（作业地址空间、虚地址空间）,:,用户的程序地址的集合称为逻辑地址空间，它的编址总是从,0,开始的作业地址空间,0,1,n-1,3. 逻辑地址（相对地址、虚地址）:作业地址空间01n-1,二,.,主存管理的功能,1.,地址映射,,将程序地址空间中使用的逻辑地址变换成主存中的地址的过程。

2.,主存分配,,按照一定的算法把某一空闲的主存区分配给作业或进程3.,存储保护,,保证用户程序,(,或进程映象,),在各自的存储区域内操作，互不干扰4.,主存扩充（提供虚拟存储技术）,,向用户提供一种不受物理存储器大小和结构限制的用户编程时使用的存储器即使在用户程序比主存容量还要大的情况下，程序也能正确运行二. 主存管理的功能1. 地址映射,1.,主存功能,——,地址映射,,主存空间,0,1,m-1,,作业,1,地址空间,0,1,n-1,,作业,i,地址空间,0,1,k-1,┆,,┆,1. 主存功能——地址映射主存空间01m-1作业1地址空间0,（,1,）为什么要进行地址映射,,作业的相应进程在处理机上运行时，所要访问的指令和数据的物理地址和作业地址空间中的地址是不同的,mov r,1,,[500],,123,,,mov r,1,,[500],,123,0,100,500,599,0,1000,1100,1500,1599,256k-1,作业地址空间,存储空间,将,500,号单元处的数据,123,送到寄存器,r1,中,（1）为什么要进行地址映射01005005990 10,（,2,）地址映射的定义,,将程序地址空间中使用的逻辑地址变换成主存中的地址的过程称为地址映射。

有时也称为地址重定位3,）地址映射的方式,编程或编译时确定地址映射关系,静态地址映射,动态地址映射,（2）地址映射的定义,静态地理映射定义：,,在,作业装入过程中,随即进行的地址变换方式称为,静态重定位或静态地址映射,mov r,1,,[500],,123,,,mov r,1,,[500+m],,123,0,100,500,599,0,m,m+100,256k-1,作业地址空间,存储空间,m+500,重定位,装入程序,静态地理映射定义： 01005005990mm+100256,,,动态地址映射定义：,在,程序运行时,确定地址映射关系在程序执行期间，随着每条指令和数据的访问自动地连续地进行地址映射mov r,1,,[500],,123,0,100,500,599,作业地址空间,0,,,mov r,1,, [500],,123,1000,256k-1,存储空间,1100,1500,1600,重定位寄存器,,1000,500,逻辑地址,+,0100500599作业地址空间01000256k-1存储空,静态地址映射与动态地址映射的区别,静态地址映射,动态地址映射,在作业装入过程中进行地址映射,在程序执行期间进行地址映射,需软件变换机构重定位装入程序,需硬件地址变换机构重定位装入,程序,需花费较多,CPU,时间,地址变换快,不灵活,灵活,静态地址映射与动态地址映射的区别静态地址映射动态地址映射在作,构造分配用的数据结构,主存资源信息块（,M_RIB,）、空闲区队列等等,制定分配策略,,,2,、主存功能,——,主存分配,实施主存分配与回收,,构造分配用的数据结构 2、主存功能——主存分配实施,主存扩充也就是,提供虚拟存储器,,,1,）问题的提出,3,、主存扩充,,物理存储器容量是有限的，用户程序的大小，可能比内存容量小，也可能比内存容量大，有时候要大得多。

在,主存容量十分紧张,的情况下，,如何,让,用户使用计算机不受主存容量的限制？,主存扩充也就是提供虚拟存储器3、主存扩充 物理存储,2,）解决问题的思路,,,装入部分程序地址空间，它还能正确地执行？,,3,）实现方法,,,,程序的全部代码和数据存放在辅存中；,,,,,将程序当前执行所涉及的那部分程序代码放入主存中；,,,,程序执行时，当所需信息不在主存，由操作系统和硬件相配合来完成主存从辅存中调入信息，程序继续执行2）解决问题的思路,4.,什么是虚拟存储器,,由操作系统和硬件相配合来完成主存和辅存之间的信息的动态调度这样的计算机系统好像为用户提供了一个其存储容量比实际主存大得多的存储器,（,虚拟存储器,）,4. 什么是虚拟存储器 由操作系统和硬件相配合来完成主存和辅,5.,虚拟存储器的核心,,,,逻辑地址与物理地址分开,,,,主存空间与地址空间分开,,,,提供地址变换机构,,,6.,实现虚拟存储器的物质基础,,,,,有相当容量的辅存,,,足以存放多用户的作业的地址空间,,,,,有一定容量的主存,,存放运行进程的当前信息,,,,,地址变换机构,5. 虚拟存储器的核心,4,、存储保护,1,）什么是存储保护,,在多道程序设计的环境下，系统中有系统程序和多个用户程序同时存在，,如何保证用户程序不破坏系统程序，用户程序之间不相互干扰？,,——,主存储器按区分配给各用户程序使用。

为了互不影响，由硬件,(,软件配合,),保证每道程序只能在给定的存储区域内活动，这种措施叫做存储保护2,）存储保护方法,,,通常的存储保护方法,——,,界地址保护,和,存储键保护（不介绍）,4、存储保护1）什么是存储保护,,(1),上、下界防护,,,,mov r,1,, [500],,123,0,20KB,256KB,,1,存储空间,24KB,下界寄存器,,20KB,上界寄存器,,24KB,下界寄存器：,存放程序装入内存后的开始地址,上界寄存器：,存放程序装入内存后的末地址,判别式：,下界寄存器 ≤ 物理地址 ＜ 上界寄存器,(1) 上、下界防护,,(2),基地址、限长防护,,,,mov r,1,, [500],,123,0,20KB,256KB,,1,存储空间,24KB,基址寄存器,,20KB,限长寄存器,,4KB,基址寄存器,=,下界寄存器,,（,首地址）,限长寄存器：存放程序长度,基址,+,限长,=,上界寄存器,,（末地址）,∴判别式：,基址寄存器≤物理地址＜基址,+,限长寄存器,(2) 基地址、限长防护 020KB256KB1存,23,作业,第,7,章,,第,2,题,23作业第7章 第2题,（三） 分区存储管理,分区存储管理分为：,1.,固定分区,2.,动态分区（可变分区）,（三） 分区存储管理分区存储管理分为：,25,,,,,,固定分区,固定分区,25固定分区固定分区,一,.,动态分区分配,,1.,什么是动态分区分配,,,在处理作业的过程中，建立分区，依用户请求的大小分配分区。

思想：分区的大小、数量和位置随内存中进程的大小和数量动态变化（根据作业的实际需要在装入内存时动态地分配连续的内存空间）一. 动态分区分配,,(1),动态分区的分配过程,20KB,,0,,os,,作业,1,,作业,2,,作业,3,,,作业,4,,,52KB,66KB,130KB,230KB,256KB,1,主存,20KB,,0,,os,,作业,1,,作业,2,,作业,3,,,,,52KB,66KB,130KB,256KB,1,主存,20KB,,0,,os,,作业,1,,,,,,,52KB,256KB,1,主存,,0,,os,,,,,,,,256KB,1,主存,20KB,20KB,,0,,os,,作业,1,,作业,2,,,,,52KB,66KB,256KB,1,主存,,作业,1,申请,,32KB,作业,2,申请,,14KB,作业,3,申请,,64KB,作业,4,申请,,100KB,作业,5,申请,,50KB,(1) 动态分区的分配过程 20KB 0 o,,(2),动态分区的回收过程,20KB,,0,,os,,作业,1,,作业,2,,作业,3,,,作业,4,,,52KB,66KB,130KB,230KB,256KB,1,主存,20KB,,0,,os,,作业,1,,,作业,3,,,作业,4,,,52KB,66KB,130KB,230KB,256KB,1,主存,,作业,2,完成,作业,4,完成,20KB,,0,,os,,作业,1,,,作业,3,,,,,52KB,66KB,130KB,230KB,256KB,1,主存,,,(2) 动态分区的回收过程 20KB 0 o,29,2,、分区分配机构,,1),主存资源信息块,在动态分区方法中，描述主存资源的数据结构是主存资源信息块,等待队列指针,空闲区队列指针,主存分配程序入口指针,2),分区描述器和空闲队列,主存中的每一个分区都有相应的分区描,述器（,pd,）说明分区的特征信息。

flag,： 为,0,—,空闲区,;,为,1,—,已分配区,size,： 分区大小,next,：空闲区,—,自由主存队列中的勾链字,;,已分配区,—,此项为零,m_rib,pd,分配标志,flag,分区大小,size,勾链字,next,292、分区分配机构等待队列指针空闲区队列指针主存分配程序入,30,自由主存队列,(,或空闲区队列,),结构,在主存分配中，主要讨论空闲区描述器和空闲区队列下面是在,t,时刻的主存分布、空闲区描述器的内容和空闲区队列结构0,20KB,,os,,作业,1,,,作业,3,,,作业,4,,,52KB,66KB,130KB,230KB,256KB,1,主存,,,,52KB,m-rib,,0,14KB,230KB,,0,26KB,,,空闲区队列结构,空闲区表的组织有两种方法：,,1,、按空闲区大小的升序（降序）组织；,,2,、按空闲区首址升序（降序）组织30自由主存队列 (或空闲区队列) 结构 020KB,3,、分区的分配与放置策略,1,）分区分配,,,•,,用户请求分配一个主存块,,,•,,分区分配程序在,自由主存队列,中找一个满足用户需要的空闲块,,,•,,若找到，则返回所分配区域的首址，否则， 告之不能满足要求。

3、分区的分配与放置策略1）分区分配,2,）放置策略,,选择空闲区的策略，称为放置策略空闲区表的组织有两种方法：,,1,、按空闲区大小的升序（降序）组织；,,2,、按空闲区首址升序（降序）组织根据空闲区表组织的方法的不同，有不同的放置策略：,首次适应,算法、,最佳适应,算法和,最坏适应,算法三种2）放置策略,33,,,,,,,1,）首次适应算法,,空闲区按起始,地址递增,的顺序排列，将作业放到,最先,找到的空闲分区33 1）首次适应算法,34,,,,,,,,2,）,最佳适应算法,,,空闲区按,由小到大,的顺序排列，将作业放到满足要求的,最小,的空闲分区34 2）最佳适应算法,35,,,,,,,,3,）,最坏适应算法,,空闲区按,由大到小,的顺序排列，将作业放到满足要求的,最大,的空闲分区35 3）最坏适应算法,几种放置策略的比较,,例如：某时刻系统中有三个空闲区，其大小和首址为：,(35KB,，,100KB),、,(12KB,，,156KB),、,(28KB,，,200KB),,有一作业系列：,,(JOB1,，,12KB),、,(JOB2,，,30KB),、,(JOB3,，,28KB),,用首次适应算法、最佳适应算法,和最坏适应算法,来处理该作业序列，看哪种算法合适？,注：,设分配时从空闲区的高地址分割，以保持剩余空闲区的起始地址不变。

os,,在使用,在使用,在使用,,在使用,,12K,B,,28K,B,0KB,100KB,,35,KB,156KB,200KB,228KB,-,1,几种放置策略的比较 例如：某时刻系统中有三个空闲区，其大小和,0,35KB,156KB,,首次适应算法,0,12KB,200KB,,0,28KB,NULL,,100KB,作业,1,（,12KB,）放到首址,100KB,的空闲区,0,23KB,156KB,,0,12KB,200KB,,0,28KB,NULL,,100KB,作业,2,（,30KB,）不能分配,作业,3,（,28KB,）放到首址,200KB,的空闲区,035KB156KB首次适应算法012KB200KB028K,0,12KB,200KB,,最佳适应算法,0,28KB,100KB,,0,35KB,NULL,,156KB,作业,1,（,12KB,）放到首址,156KB,的空闲区,0,28KB,100KB,,0,35KB,NULL,,200KB,作业,2,（,30KB,）放到首址,100KB,的空闲区,作业,3,（,28KB,）放到首址,200KB,的空闲区,0,5KB,200KB,,0,28KB,NULL,,100KB,,012KB200KB最佳适应算法028KB100KB035K,0,35KB,200KB,,最坏适应算法,0,28KB,156KB,,0,12KB,NULL,,100KB,作业,1,（,12KB,）放到首址,100KB,的空闲区,作业,2,（,30KB,）不能继续分配,作业,3,（,28KB,）放到首址,200KB,的空闲区,0,28KB,100KB,,0,23KB,156KB,,0,12KB,NULL,,200KB,,,035KB200KB最坏适应算法028KB156KB012K,四、碎片问题及拼接技术,1.,什么是碎片问题,,在已分配区之间存在着的一些没有被充分利用的空闲区。

如何解决碎片问题？,,2.,拼接技术,,所谓拼接技术是指移动存储器中某些已分配区中的信息，使本来分散的空闲区连成一个大的空闲区四、碎片问题及拼接技术1. 什么是碎片问题,41,OS,400KB,JOB1(100KB),JOB2(200KB),0,300KB,JOB6(100KB),800KB,700KB,900KB,JOB5(100KB),JOB4(100KB),JOB7(100KB),600KB,1000KB,1024KB,OS,400KB,JOB2(200KB),0,300KB,JOB6(100KB),800KB,700KB,900KB,JOB5(100KB),JOB4(100KB),JOB7(100KB),600KB,1000KB,空闲,(24KB),1024KB,空闲,(100KB),OS,400KB,JOB2(200KB),0,300KB,800KB,700KB,900KB,JOB5(100KB),JOB7(100KB),600KB,1000KB,空闲,(24KB),1024KB,空闲,(100KB),空闲,(100KB),空闲,(100KB),,,,有一大小为,200K,的作业需要运行,!!!,空闲,(24KB),41OS400KBJOB1(100KB)JOB2(200KB,分区管理的优缺点,优点：,实现了多道程序,共享主存,。

实现分区管理的,系统设计相对简单,，不需要更多的,系统软硬件开销,实现,存储保护,的手段,也比较简单,缺点：,主存利用不够充分,系统中总有一部分存储空间得不到利用，这部分被浪费的空间叫,碎片,没有实现主存的扩充问题, 当作业的地址空间大于存储空间时，作业无法运行也即作业的地址空间受实际存储空间限制分区管理的优缺点优点：,（四） 页式存储管理,一,.,问题的提出,,,分区存储管理的主要问题是,碎片,问题在采用分区存储管理的系统中，会形成一些非常小的分区，最终这些非常小的分区不能被系统中的任何用户（程序）利用而浪费造成这样问题的主要原因是用户程序装入内存时是整体装入的，为解决这个问题，提出了分页存储管理技术四） 页式存储管理一. 问题的提出,二,.,页式系统的基本概念,1.,页面,,程序的地址空间被等分成大小相等的片，称为页面，又称为,虚页,2.,主存块,,主存被等分成大小相等的片，称为主存块，又称为,实页,二. 页式系统的基本概念1. 页面,,作业页面与主存块的关系,,,0,2KB,4KB,254KB,256KB,1,0,2KB,4KB,6KB,0,页,1,页,2,页,3,页,主存,作业地址空间,页表,地址映射,作业页面与主存块的关系 02KB4KB254KB2,3.,页表,（,1,）什么是页表,,为了实现从地址空间到物理主存的映象，系统建立的记录页与内存块之间对应关系的地址变换的机构称为页面映像表，简称页表。

包括用户程序空间的页面与内存块的对应关系、页面的存储保护和存取控制方面的信息3. 页表（1）什么是页表,,,0,1KB,0,1KB,2KB,3KB,1,主存,作业,2,地址空间,2KB,3KB,4KB,5KB,6KB,7KB,8KB,9KB,10KB,1,,0,1KB,2KB,1,作业,1,地址空间,,0,1KB,1,作业,3,地址空间,,0,5,1,6,页号,块号,,0,2,1,4,,0,8,2,7,作业,1,页表,作业,2,页表,作业,3,页表,os,os,01KB01KB2KB3KB1主存作业2地址空间2KB3K,三,.,页式地址变换,,1.,虚地址结构,,虚地址是用户程序中的逻辑地址，它包括,页号,和,页内地址,（页内位移）区分页号和页内地址的依椐是,页的大小,，页内地址占虚地址的低位部分，页号占虚地址的高位部分例,】,设虚地址长度为,16,位，页面大小为,1KB,：,页号 页内地址（位移量）,,P W,15 10 9 0,,三. 页式地址变换,49,,,,,,,,如何方便将逻辑地址线性分割求出页号,P,和页内位移,W,：,逻辑地址以十进制数给出,：,,页号,P=,逻辑地址,%,页大小,页内位移,W=,逻辑地址,mod,页大小,逻辑地址以十六进制、八进制、二进制的形式给出：,将逻辑地址转换成二进制；,按页的大小分离出页号,P,和位移量,W,（低位部分是位移量，高位部分是页号）；,49如何方便将逻辑地址线性分割求出页号P和页内位移W：,50,,,,,,,,,【,例,】,：有一系统采用页式存储管理，有一作业大小是,8KB,，页大小为,2KB,。

解：,求虚地址,3412,P,＝,3412,％,2048,＝,1,W,＝,3412 mod 2048,＝,1364,求,虚地址,7145,：,P,＝,7145,％,2048,＝,3,W,＝,7145 mod 2048,＝,1001,50【例】：有一系统采用页式存储管理，有一作业大小是8KB，,51,,,,,,,,,【,例,】,：有一系统采用页式存储管理，有一作业大小是,8KB,，页大小为,2KB,虚地址,0AFEH,：,0000,,1,010 1111 1110,P,＝,1 W,＝,010 1111 1110,虚地址,1ADDH,：,0001 1,010 1101 1101,P,＝,3 W,＝,010 1101 1101,51【例】：有一系统采用页式存储管理，有一作业大小是8KB，,例,1,页面大小是,1KB,，虚地址是,3BADH,例,2,页面大小是,2KB,，虚地址是,3BADH,例1 页面大小是1KB，虚地址是3BADH,53,,,,,,,,,2,、地址变换,,根据逻辑地址求物理地址的步骤：,1,）将逻辑地址,线性分割,求出页号,P,和页内位移,W,：,2,）根据页号查页表,得块号,B,；,3,）,物理地址,=,块号,B×,页大小,+,页内位移,W,532、地址变换,54,,,,,,,页表始址寄存器,,mov r,1,,,[2500],,,,123,0,1KB,2KB,3KB,1,作业,2,地址空间,,+,,0,2,1,4,2,7,页表,0 0 0 0 1 0 0 1 1 1 0 0 0 1 0 0,15 10 9 0,页号,页内位移,W,2500,,0,1KB,主存,2KB,3KB,4KB,5KB,6KB,7KB,8KB,9KB,10KB,1,os,os,mov r,1 ,,[2500],123,第,1,页,块号,块内位移,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,54页表始址寄存器mov r1 ,01KB2KB3KB1,55,,,,,,,,,【,例,】,：有一系统采用页式存储管理，有一作业大小是,8KB,，页大小为,2KB,，依次装入内存的第,7,、,9,、,10,、,5,块，试将虚地址,7145,，,3412,转换成内存地址。

解：,求虚地址,3412,P,＝,3412,％,2048,＝,1,W,＝,3412 mod 2048,＝,1364,MR=9*2048+1364=19796,求虚地址,7145,：,P,＝,7145,％,2048,＝,3,W,＝,7145 mod 2048,＝,1001,MR=5*2048+1001=11241,55【例】：有一系统采用页式存储管理，有一作业大小是8KB，,56,,,,,,,,,【,例,】,：有一系统采用页式存储管理，有一作业大小是,8KB,，页大小为,2KB,，依次装入内存的第,7,、,9,、,A,、,5,块，试将虚地址,0AFEH,，,1ADDH,转换成内存地址解：,求虚地址,0AFEH,的物理地址：,0000,,1,010 1111 1110,P,＝,1 W,＝,010 1111 1110,MR,＝,0100,,1,010,,1111 1110,＝,4AFEH,求虚地址,1ADDH,的物理地址：,0001 1,010 1101 1101,P,＝,3 W,＝,010 1101 1101,MR,＝,0010 1,010,,1101 1101,＝,2ADDH,56【例】：有一系统采用页式存储管理，有一作业大小是8KB，,57,,,,,,,,,课堂练习：,1,、某作业,J,的逻辑空间为,4,页，每页,2048B,，已知该作业,J,的页表如下：,页号：,0 1 2 3,,块号：,2 4 6 8,,求：逻辑地址为,0A65H,的物理地址。

2,、某作业有,4,个页面，分别装入主存的,3,、,4,、,6,、,8,块中，设页面尺寸为,1024B,（,1,）、写出该作业的页表；,（,2,）、求,mov 2100,3100,指令中两个操作数的物理地址57课堂练习：,四,.,请调策略,1,、请调策略定义：,,在页式系统中，允许一个作业程序只装入部分页面即可投入运行，需要信息时动态调入，这种装入信息的策略称为请调策略1),怎样发现所访问的页面在不在主存？,,,(2),当发现所需访问的页面不在主存时如何处理,?,,四. 请调策略1、请调策略定义：,,2.,扩充页表功能,,,,,,,中断位,i,——,标识该页是否在主存,若,i=1,，表示此页不在主存,若,i=0,，表示该页在主存,,,辅存地址,——,该页面在辅存的位置,,页号,主存块号,中断位,辅存地址,页号主存块号中断位辅存地址,,,3.,缺页处理过程 （举例说明）,,,0,1KB,主存,2KB,3KB,4KB,5KB,6KB,7KB,8KB,9KB,10KB,1,,0,2,1,4,2,作业,2,页表,os,os,作业,2,第,1,页,作业,2,第,0,页,3,页号 辅存地址 中断位 块号,,0,0,1,1,地址,地址,地址,地址,,0,1KB,2KB,4KB,1,作业,2,地址空间,mov r1,[2120],add r1,[3410],006251,,006802,,3KB,3. 缺页处理过程 （举例说明）01KB主存2KB3,,作业,2,的主存块数为,m,2,=3,，页面大小为,1KB,。

当程序执行,“,mov r,1,，,[2120,］,”,时,,,CPU,产生的虚地址为,2120,,分页机构得,p=2,，,w=72,,,查页表该页中断位,i,=1,，,则发生,缺页中断,,0,1KB,2KB,4KB,1,作业,2,地址空间,mov r1,[2120],add r1,[3410],006251,,006802,,3KB,,,如主存中有空白块，且,n,m,则直接调入,,如主存中无空白块，或,n,,,m,，,则需淘汰该作业在主存中的一页,（,其中,n,代表作业已分配到的主存块数，,m,为内存为作业准备的物理块数,）01KB2KB4KB1作业2地址空间mov r1,[212,缺页处理流程,,启动要处理的指令,给出虚地址,,得到页号,,该页在主存,?,,有空闲块,?,,,缺页中断,执行完该指令,,准备执行下条指令,选一页淘汰,,从外存读入所需的页,,调整存储分配表和页表,,重新启动被中断的指令,,调整存储分配表和页表,,要重写入,?,该页写入外存,Y,N,N,Y,硬件,软件,Y,N,缺页处理流程 启动要处理的指令给出虚地址 得到,4.,淘汰策略,1.,什么是淘汰策略,,用来选择淘汰哪一页的规则就叫做置换策略，或称淘汰算法。

常用算法：,1,、,最优算法,OPT:(,optimal page-replacement algorithm),置换在最长时间内不会使用的页,),2,、,先进先出算法,FIFO,：,淘汰先调入内存的页,3,、,最近最少使用淘汰算法,LRU,：,淘汰未被访问的页中时间最长的页,;(Least Recently Used),,使用,缺页中断率,f,’,衡量页面淘汰算法的优劣：,,f,’,＝,f,／,a,（,a,是总的页面访问次数，,f,是缺页中断次数）,4. 淘汰策略1. 什么是淘汰策略,2.,扩充页表的功能,页表应增加相应的内容，反映该页是否在内存，在外存的位置，在内存的时间的长短等引用位：,0,表示最近没有进程访问,,1,表示最近有进程访问,,改变位：,0,该页调入内存后没有修改,,1,该页调入内存后修改过,页号,主存块号,中断位,辅存地址,改变位,引用位,2. 扩充页表的功能页表应增加相应的内容，反映该页是否在内存,3.,颠簸,颠簸,(thrashing),，又称为,“,抖动,”,简单地说，导致系统效率急剧下降的主存和辅存之间的频繁页面置换现像称为,“,抖动,”,3. 颠簸颠簸(thrashing)，又称为“抖动”。

OPT,原理（难实现）：,当要调入一新页而必须先淘汰一旧页时，所淘汰的那一页应是以后不再要用的，或者是在最长的时间以后才会用到的那页缺页率,,假定程序,p,共有,n,页，系统分配,m,块，有,1≤m≤n,若程序,p,在运行中,:,成功的访问次数：,s,,不成功的访问次数：,f,,则缺页中断率：,f′=f/ (s+ f)*100%,f′=f (r,，,m,，,p),,4.,页面置换算法,——OPT,算法,4. 页面置换算法——OPT算法,例：假设系统为某进程分配了,3,个物理块，并考虑有以下的访问串：,7,，,0,，,1,，,2,，,0,，,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%,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,例：假设系统为某进程分配了3个物理块，并考虑有以下的访问串：,,,,(2),先进先出淘汰算法,(FIFO,算法,),1),什么是先进先出淘汰算法,原理：总是选择在主存中居留时间最长,(,即最老,),的一页淘汰。

2),先进先出淘汰算法的实现方法,,,建立一个页面进入主存的,先后次序表,；,,,建立一个替换指针，指向最早进入主存的页面；,, 当需要置换一页时，选择,替换指向的那一页，然,,后调整替换指针的内容69,,,,,,,,,【,例,】,某进程的页面访问序列：,1,、,2,、,3,、,4,、,1,、,2,、,5,、,1,、,2,、,3,、,4,、,5,，指出在驻留集大小分别为,3,和,4,时，使用,FIFO,置换算法的缺页率，结果说明了什么？,（设驻留集,M,表示分给该作业的内存块数）,,解：,FIFO,,,M,＝,3,f,’,＝,,f,／,a,＝,9,／,12,＝,75%,M,＝,4,f,’,＝,10,／,12,≈,83%,,69【例】某进程的页面访问序列：1、2、3、4、1、2、5、,70,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,1,2,3,4,1,2,5,1,2,3,4,5,t,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,3,3,3,3,3,3,4,4,4,4,4,5,5,5,5,5,5,1,2,5,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,1,2,3,4,1,2,5,1,3,4,5,t,1,1,1,4,3,3,4,5,2,2,2,4,4,5,1,1,3,3,2,3,3,4,4,3,2,4,5,5,1,2,2,2,3,2,2,3,4,1,5,1,1,1,2,采用,FIFO,算法,70123412512345t111111112222222,,,(3),最久未使用淘汰算法,(LRU,算法,),总是选择最长时间未被使用的那一页淘汰。

LRU,算法的实现方法,, 用引用位考察页面的使用情况,；,, 当访问页面时，将引用位置,1,，并记时,；,, 当要淘汰一页时，选择时间最长的一页淘汰,要精确实现很困难,硬件方法：采用寄存器（计时法）,软件方法：,采用页号栈,(3) 最久未使用淘汰算法(LRU算法),72,,,,,,,,,【,例,】,某进程的页面访问序列：,1,、,2,、,3,、,4,、,1,、,2,、,5,、,1,、,2,、,3,、,4,、,5,，指出在驻留集大小分别为,3,和,4,时，使用,LRU,置换算法的缺页率，？,（设驻留集,M,表示分给该作业的内存块数）,解：,,LRU,,,,M,＝,3,f,’,＝,,f,／,a,＝,10,／,12,≈,83%,M,＝,4,f,’,＝,,f,／,a,＝,8,／,12,≈,67%,,72【例】某进程的页面访问序列：1、2、3、4、1、2、5、,73,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,1,2,3,4,1,2,5,1,2,3,4,5,t,1,1,1,1,1,1,2,5,2,2,2,2,2,5,1,1,3,3,3,3,3,4,4,4,4,4,5,5,1,2,2,2,3,1,2,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,1,2,3,4,1,2,5,1,3,4,5,t,1,1,1,1,1,1,2,5,2,2,2,2,2,5,1,1,3,3,3,3,3,4,4,4,4,4,5,5,1,2,2,2,3,2,4,4,4,1,5,2,3,1,2,采用,LRU,算法,73123412512345t111111252222251,练习,在分页虚拟存储管理系统中，假设系统为某进程分配了四个主存块（将开始,4,页先装入主存），进程执行时页的引用顺序为：,7,1,2,0,3,0,4,2,3,0,3,2,7,0,1,，求分别采用,OPT,、,FIFO,、,LRU,算法计算产生多少次缺页中断？产生多少次缺页置换？依次淘汰的页是什么？缺页率为多少？,练习 在分页虚拟存储管理系统中，假设系统为某进程分配了四个主,。