操作系统第三章ppt课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第3章 存储器管理,3.1,内存管理概述,（次重点）,3.2 分区存储管理,（次重点）,3.3,页式存储管理,（重点）,3.4,段式存储管理,（非重点）,3.5,段页式存储管理,（自学）,第3章 存储器管理3.1 内存管理概述（次重点）,1,本章需掌握的知识要点,内存管理任务,三种内存管理方式,两类算法（内存分配、页面置换）,三组区别,可,重定位动态分区,基本分页,请求分页,实存 与 虚存,分页 与 分段,连续 与 离散,本章需掌握的知识要点内存管理任务可重定位动态分区实存 与 虚,2,3.1 内存管理概述,1. 存储体系,三级存储器,内存(主存),：,RAM,、ROM,外存(辅存)：,磁盘,、磁带、光盘等,高速缓冲存储器(cache),另有寄存器级,OS负责协调各存储器的使用，OS本身的程序和数据与其他程序一起共享主存，为安全起见，多道程序系统常由OS把内存初始化为系统区和用户区两大部分：,内存,系统区（存放OS程序和数据）,用户区（存放用户程序、数据）,3.1 内存管理概述1. 存储体系三级存储器内存(主存)：,3,2. 存储管理的目的,充分利用内存，为多道程序并发执行提供存储基础,尽可能方便用户使用,自动装入用户程序,用户程序中不必考虑硬件细节,能够解决小内存运行大程序的问题,支持程序在执行时可以动态伸缩,保证内存存取速度快,实现存储保护与安全,实现共享与通信,了解有关资源的使用状况,权衡实现的性能和代价,2. 存储管理的目的充分利用内存，为多道程序并发执行提供存储,4,3. 存储管理的任务,或功能,（1）内存空间的管理、分配与回收,记录内存的使用情况,设置相应的内存分块表（内存分配回收的依据）,内存空间划分问题？,静态或动态，等长或不等长,确定分配算法,考虑连续性与离散性，驻留性与交换性，一次性与多次性，静态方式与动态方式,内存碎片问题及解决办法,确定回收策略,（2）地址转换,（又称地址重定位、地址映射）,指,为了保证CPU执行指令时可正确访问存储单元，需将用户程序中的,逻辑地址,（相对地址，虚地址）,转换为运行时由机器直接寻址的,物理地址,（绝对地址，实地址）的,过程,3. 存储管理的任务或功能（1）内存空间的管理、分配与回收,5,3. 存储管理的任务（续）,根据实施转换的主体和转换时机的不同，重定位具体分为两种：,静态重定位,和,动态重定位,。后者更常用,系统采用动态重定位后，程序在内存,可浮动,（3）内存的共享与保护,进程共用相同内存区可节省空间，便于通信，所共享的代码应为,纯代码,（或者叫,可重入的代码,）,内存保护限定程序只能访问自己所在的内存区，保护了OS和其他程序,常用界限寄存器对法和存取控制字来实现,（4）内存的扩充,常用,覆盖,、,交换,和,虚拟存储,技术等实现对内存的逻辑扩充，以使小内存能够运行大程序,3. 存储管理的任务（续）根据实施转换的主体和转换时机的不同,6,装入,Load 1, 200,3456,1200,物理地址空间,Load 1, data1,data1 3456,源程序,Load 1, 200,3456,0,100,200,编译,连接,逻辑地址空间,BA=1000,1100,系统采用动态重定位，程序装入内存时的示例,（内外存副本一致）,：,装入1200物理地址空间源程序0100200编译逻辑地址空间,7,1000,3456,LOAD 1, 200,0,100,200,300,LOAD 1, 200,3456,逻辑地址空间,1100,1200,1300,物理地址空间,200,VR,+,1000,BR,动态重定位示例：,10003456LOAD 1, 2000100200300L,8,覆盖示意图,主程序(30k),子程序 A(8k),子程序 B(10k),子程序M(20k,),子程序N(25k),子程序X(15k),主程序（30k),覆盖区1(25k),覆盖,区0,(10k),内,存,区,用,户,的,结,构,化,程,序,区,覆盖示意图主程序(30k)子程序 A(8k)子程序 B(10,9,程序的装入和链接,源程序从编辑到运行要经历以下阶段：,编辑, 编译 链接 装入 运行,静态链接、动态链接,绝对地址装入、静态重定位装入、动态重定位装入,程序的装入和链接源程序从编辑到运行要经历以下阶段：,10,存储管理策略分类,存储管理策略,：,实存管理,连续,区,分配,（包括,固定分区,、,可变分区,和,伙伴系统,）,分页（Paging ）,分段（Segmentation ）,虚存管理,请求分页(Demand paging),-,主流技术,请求分段(Demand segmentation),段页式（ segmentation with paging ）,离散分配,存储管理策略分类存储管理策略：离散分配,11,3.2 分区式存储管理,早期的一类,实存,管理技术,系统给每个作业或进程分配一个,连续,的内存分,区,。,单一连续区分配（静态分区技术）,固定分区分配,（,静态分区,技术）,可变分区分配（动态分区技术）,可重定位可变分区分配,（,动态分区,技术）,伙伴系统,（,动态分区,技术）,3.2 分区式存储管理 早期的一类实存管理技术,12,1. 单一连续区存储管理,系统静态地将内存划分为两个区域，一个供操作系统使用，一个供用户使用，且每次只能装入一个作业或进程，主要用于早期单道程序系统和后来的PC操作系统。,特点,是实现简单，但内存利用率低，作业大小受限。,操作系统,用户程序,0xFFF.,0,1. 单一连续区存储管理系统静态地将内存划分为两个区域，一个,13,区号,起始地址,长度(,KB,),状态,1,a,S,1,0,2,b,S,2,1,3,c,S,3,0,系统预先把可分配的内存空间分割成若干个连续区域，每一区域称为分区，每个分区的大小可以相同也可以不同，分区的个数与大小固定不变，每个分区每次只能装一个作业。,OS,0,a,b,c,d,空,job,2,空,内存分块表(MBT),内存,特点,：实现简单，可用于多道程序系统，但内存利用率低，作业大小受限。,2. 固定分区存储管理,单一连续区在多道程序系统中的直接应用,区号起始地址长度(KB)状态1aS102bS213cS30系,14,3. 可变分区存储管理,基本思想,内存划分是在作业或进程进入时动态进行的，分区的个数与大小都不是固定的,作业装入时，根据作业的需求和内存空间的使用情况来决定是否分配,若有足够的空间，则把分配算法选中的那个分区直接分配给该作业，或者从那个选中的分区中割下与该作业申请量等大小的一部分连续空间分给该作业；否则令其等待。,特点,克服了固定分区管理的“,内碎片,”问题，但产生了“,外碎片,”。,怎样解决,碎片问题呢？,改进内存释放算法,在内存中移动程序,变连续分配为离散分配,3. 可变分区存储管理基本思想怎样解决改进内存释放算法,15,4. 可重定位可变分区存储管理,基本思想,相当于引入了动态重定位和,内存紧凑,（紧缩、拼接、紧致、浮动、搬家）,（compaction）技术的可变分区存储管理,问题,实现紧凑所花的代价与换来的提高了内存空间利用率的好处相比是否值？,内存紧凑的开销、频率、条件、时机？,一经紧凑，外碎片是否彻底消失？,特点,消除了,内碎片，提高了内存利用率，便于动态申请内存， 便于共享内存，便于动态链接，但会产生外碎片，而紧凑内存需要花费处理机大量时间，另外，还需要硬件重定位机构支持，作业大小也受内存可用空间的限制。,4. 可重定位可变分区存储管理基本思想,16,可重定位可变分区存储管理（续1）,内存管理用主要数据结构,空闲分区链,（或空闲分区表）,内存分配算法,（顺序查找分配，可能触发,紧凑,程序）,最先适应（First Fit）,下次适应（Next Fit）,最佳适应（Best Fit）,最坏适应（Worst Fit）,内存释放,/回收,算法,（考虑及时,合并相邻空闲区,）,先在空闲分区链中找到插入点，再考虑能否合并相邻空闲区,数据结构怎样组织更有效？,可重定位可变分区存储管理（续1）内存管理用主要数据结构数据结,17,例,3.1,分区存储管理算法题,采用可变分区方式管理内存时，若内存中按地址顺序依次有五个大小依次为,15k、28k、10k、226k和,110k的,空闲区。现有五个作业J,a,、J,b,、J,c,、J,d,和J,e，,它们各需要内存,10k、15k、102k、26k和180k,。问：如果采用最先适应分配算法，能将这五个作业按J,a, J,e,的次序全部装入内存吗？用什么分配算法装入这5个作业可使内存的利用率最高？,例3.1 分区存储管理算法题采用可变分区方式管理内存时，若,18,解答：,按最先适应分配算法，不能将这五个作业按Ja Je的次序全部装入内存。因为内存中前两个原先的空闲分区能依次装入Ja(10k)和J,b,(15k)，第3个10KB的空闲区和刚刚划分出来的两个大小分别为5KB和13KB的空闲区均无法分配，第4个空闲区可以分2次装入作业Jc(102k)和J,d,(26k)，则作业Je(180k)无法装入内存。,用最佳适应分配算法装入这5个作业，可使内存的利用率最高。此时，原先的5个空闲区依次装入了5个作业，它们是：J,b,(15k)，J,d,(26k)，J,a,(10k)，J,e,(180k)和J,c,(102k)。,15k,28k,10k,226k,110k,解答： 按最先适应分配算法，不能将这五个作业按Ja J,19,5. 伙伴系统,（,buddy system,）,介于固定分区与可变分区之间的动态分区技术,伙伴系统可看作固定分区分配和可变分区分配的一种折中方案。,采用伙伴系统时，内存是以,2,的幂次个字节大小的空闲块为分配单位的。,系统初启时，只有,1,个最大的,2,的幂次的空闲块，它就是整个可用的内存空间。当,1,个进程申请内存时，系统就分给它,1,个大于或等于进程所申请尺寸的最小的,2,的幂次的空闲块。,例如，某进程提出的50,KB,的内存请求，将首先被系统向上取整，转化为对1个64,KB,的空闲块的请求。,伙伴系统的内存分配过程,在一开始不能找到合适的空闲块时将把一个最小的比该空闲块大的空闲块,对分成2个“伙伴”,单位，该对分过程可能会继续，直到获得合适的空闲块为止。,伙伴系统的内存释放过程,首先考虑将被释放块与其伙伴单位,合并,成1个大的空闲块，然后继续合并下去，直到不能合并为止。,5. 伙伴系统（buddy system）介于固定分区,20,伙伴系统（续1）,为了实现伙伴系统,，系统要为每一种可能的空闲块维护1个空闲块链表。设系统管理的可用内存空间共为2,N,个字节，则1个伙伴系统最多需要维护,N,个空闲块链表。由于每种尺寸的空闲块都有一个空闲块队列，因此内存的分配与释放可以有效地进行。,Linux维护6个链表,。,伙伴系统的最大缺陷,是不能有效地利用内存，特别是内碎片严重。,例如，1个257,KB,的进程需要占用1个512,KB,的分配单位，其中将产生255,KB,的内碎片。,另外，,每次释放内存时都尽可能地合并伙伴单位的做法也会降低系统性能，因为刚合并好的块可能马上又要对分。一种改进的做法是延迟合并的时机。,伙伴系统（续1）为了实现伙伴系统，系统要为每一种可能的空闲块,21,伙伴系统（续2）,伙伴系统示意图,Action,Memory,Start,1M,A请求150kb,A,256k,512k,B请求100kb,A,B,128k,512k,C请求50kb,A,B,C,64k,512k,释放B,A,C,64k,512k,D请求200kb,A,C,64k,D,256k,E请求60kb,A,C,E,D,256k,释放C,A,64k,E,D,256k,释放A,256k,64k,E,D,256k,释放E,512k,D,256k,释放D,1M,伙伴系统（续2） 伙伴系统示意图ActionMemo,22,3.3 页式存储管理,不用“紧凑”也能消除碎片的一种,离散分配,技术,实分页式存储管理（基本分页）,虚拟页式存储管理（请求分页）,3.3 页式存储管理 不用“紧凑”也能消除碎片,23,3.3.1 实分页存储管理,似当今磁盘空间的管理，我认为在PC上很有发展前途！,基本思想（,特殊的固定分区+离散分配,）,系统自动地等分进程地址空间和内存空间，每一等分单位分别叫页,（page）,和块,（frame，也叫页帧、页框、页架）,，页与块等大小，且都从0开始连续编号。进程运行时，全部页面必须装入内存，但逻辑上连续的各个页所对应的内存块可以不连续。,3.3.1 实分页存储管理 似当今磁盘空间的管,24,2. 相关概念,逻辑地址、页面、页内碎片,分页对用户是透明的。页面是内存的划分使用单位，似磁盘的扇区或簇，也似CPU的时间片。一般，一,页的大小,为2的整数次幂（k/24K16KB），也是个实验统计值，不能太大，也不能太小，,为什么,？进程的,地址空间是一维连续的,，用一个记号即可表示一个逻辑地址，但为重定位方便，系统常,视,逻辑地址,为,两部分组成的，即把地址的高位部分视为页号，低位部分视为页内偏移。进程最后一页中空闲的部分称为,页内碎片,。,0,11,12,31,页号P,页内位移量W,编号01048575,相对地址04095,该地址结构限定的最大地址空间是多少？最大页表呢？,2. 相关概念逻辑地址、页面、页内碎片0111231页号P,25,3. 管理,页表（page,map,table）：,系统为每个进程建立一个页表，页表给出逻辑页号和具体内存块号相应的关系,(虚分页系统中页表表目的内容更多),。页表放在内存，属于进程的现场信息。,页表源于一组动态重定位寄存器，今天的用途主要有两处：记录进程的内存分配情况实现进程运行时的动态重定位。,为了解决要求连续内存空间存放页表的问题,，可用对页表分页并将其各页面离散存放的办法来实现。这就形成了,多级页表,，目前最常用的是2级页表，如Windows 2000和Linux中。这时，原来的页号部分，又被看成是两部分：页目录偏移、页表偏移。,另外，在IBM AS/400和Mac OS中，使用更省内存的,反置页表,页表表目为：Pid、page、valid、point。下面是一个页表示意图。,3. 管理页表（page map table）：,26,.,.,.,0,1,2,3,4,5,6,0,1,2,3,4,5,6,进程的,地址空间,页框,（物理块）,页号,页表,主存中页框（物理块）,.,.,.,.,.,.,.,页表示意图：,.01234560123456进程的页框页号页表主存中页,27,0,31,0/1,0/1,0/1,0/1,0/1,0,1,7,空闲块数,空块管理位示图,(用于外存分配时常叫盘图),使用时需进行字位号到块号的转换：(i,j),b，b=i*w+j。另外，找n个连续的块较慢。,3. 管理（续1）,0310/10/10/10/10/1017空闲块数空,28,3. 管理（续2）,内存的分配,与回收,计算一个作业所需要的总块数N,查位示图，看看是否还有N个空闲块,如果有足够的空闲块，则页表长度设为N，可填入PCB中；申请页表区，把页表始址填入PCB,依次分配N个空闲块，将块号和页号填入页表,修改位示图,3. 管理（续2）内存的分配与回收,29,4. 硬件支持,系统设置一对寄存器：,页表始址寄存器,（用于重定位时查页表）,页表长度寄存器,（用于重定位时内存保护校验，页表目还常有控制位）,联想存储器,（associative memory）,快表,（cache结构，,为提高地址变换速度而引入,，在IBM系统中称,TLB（Translation lookaside buffers）,）,用途：保存正在运行进程的部分页表项，以快速重定位,快表表目内容：页号、内存块号、标识位、淘汰位,快表的特点：可按内容并行查找,快表命中率：已经证明，16个表目可达90%以上。,Intel 80x86/Pentium有32项，SGI MIPS R4000有48项。,下面是快表在地址转换过程中应用的示意图。,4. 硬件支持系统设置一对寄存器：,30,分页地址映射过程示意图,地址越界,p,页表,l,比较,P=1,p,p,.,快表,b,+,页号p 页内地址,d,P,d,页表地址寄存器,页表长度寄存器,逻辑地址,.,.,物理地址,分页地址映射过程示意图地址越界页表 l比较P=1pp.快,31,页目录地址,目录位移,页表位移,页位移,虚拟地址,页表地址,.,.,.,页目录（每进程一个）,块号,.,.,.,页 表,代码或数据,.,.,.,物理页,+,+,二级页表结构及地址映射过程,（未画出快表）,页目录地址目录位移页表位移页位移虚拟地址页表地址.页目录（每,32,5. 实分页存储管理方式小结,优点：,内存利用率高,，解决了碎片问题；,便于管理。,缺点：,不易,实现,共享,（见P93）；,不便于,页面,动态增长,；,进程仍受内存可用空间大小的限制；,所需硬件支持较多。,5. 实分页存储管理方式小结优点：内存利用率高，解决了碎片问,33,3.3.2,虚拟,页式存储管理,1. 基本思想,实分页+对换和请求装入功能,系统等分进程地址空间和内存空间，每一等分单位分别叫页和块，页与块等大小，且都从0开始连续编号。,进程运行时，,只需部分页面在内存,，且逻辑上连续的页所对应的内存块可以不连续。当进程访问的页不在内存时将产生,缺页中断,，由服务程序把所缺页装入内存，此时若内存空间已满，则又需要,对换,进程根据,页面调度算法,淘汰某个内存页面，再装入所缺页面。,3.3.2 虚拟页式存储管理1. 基本思想实分页+对换和请,34,2. 虚拟存储器的概念,实存管理方式的特征,：,一次性；驻留性,；连续性。,虚拟存储器是,为了,逻辑扩充内存，以解决小内存无法运行大程序的问题而,引入,的，是一种以CPU时间和外存空间换取内存空间的技术（是OS中的资源转换技术），也是迄今为止逻辑扩充内存程度最彻底的技术（远强于覆盖和交换技术）。,虚拟存储器是在1961年由英国曼彻斯特大学的Fotheringham提出，并在该校的atlas机器上实现的一种存储技术。从1970年后被广泛应用，今天的OS普遍采用这一技术管理内存,，但我们仍应辨证地看待它,。,虚拟存储器的基本思想,是：,程序、数据、堆栈的大小可以超过内存的大小，OS把程序当前使用的部分保留在内存，而把其它部分保存在磁盘上，并在需要时在内存和磁盘之间动态交换。,虚拟存储器支持多道程序设计技术。,虚存管理方式的特征,：,多次性；对换性；虚拟性,；离散性,2. 虚拟存储器的概念实存管理方式的特征：虚存管理方式的特,35,2. 虚拟存储器的概念（续1）,1968年美国MIT的Denning提出程序局部性原理是对虚拟存储器有力的理论支持。,程序局部性原理,程序在执行时呈现出高度的局部性特征，即在一较短的时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域。程序执行的局部性表现在时间与空间两个方面：,时间局部性,一条指令被执行了，则在不久的将来它可能再被执行,空间局部性,若某一存储单元被访问，则在不久之后，与该存储单元相邻的单元也可能被访问,2. 虚拟存储器的概念（续1） 1,36,2. 虚拟存储器的概念（续2）,虚拟存储器定义,（至今没有统一定义，我认为以下前3种比较重要）,虚假的存储器；,进程能够访问的虚拟地址空间；,具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。,把内存与外存有机的结合起来使用，从而得到一个容量很大的“内存”，这就是虚存,虚拟存储器是把内存与外存这两级存储器并用做一级存储器的结果，是逻辑扩充内存的最佳手段,虚拟存储器的容量,取决于内存与外存的容量之和，但实际最大尺寸取决于系统的地址结构,2. 虚拟存储器的概念（续2）虚拟存储器定义（至今没有统一,37,2. 虚拟存储器的概念（续3）,虚拟存储器,是建立在离散分配的内存管理技术基础上的，它主要有以下,3种实现方法,：,请求分页系统,虚拟分页系统,基本分页系统 + 请求分页功能 + 页面置换功能,硬/软件支持,：请求分页的页表机制、缺页中断机构、动态地址变换机构、对换机制、大容量外存。,请求分段系统虚拟分段系统,基本分段系统 + 请求分段功能 + 分段置换功能；,硬/软件支持：请求分段的段表机制、缺段中断机构、动态地址变换机构、对换机制、大容量外存。,请求段页式系统虚拟段页式系统,请求分页系统 + 请求分段系统,硬/软件支持：页表机制、缺页中断机构、段表机制、缺段中断机构、动态地址变换机构、对换机制、大容量外存。,2. 虚拟存储器的概念（续3） 虚拟,38,虚拟存储器的概念（续4）, 要辨证地看待虚拟存储器管理,问题1：windows98为何常提示“内存不足”？,问题2：当今OS几乎都用虚拟内存技术，有必要吗？,虚拟存储器管理的主要优点,扩充了内存，解决了小内存无法运行大程序的问题，提高了内存的利用率和多道程度,虚拟存储器管理的主要缺点,实现开销大，程序运行比实模式下慢,虚拟存储器的概念（续4） 要辨证地看待虚拟存储器管理,39,3. 虚分页所需的硬件支持,页表机制,（似实分页的，只是扩充了页表目内容）,用于地址转换；,扩充页表项：页号、页架号、状态位、访问字段/位、修改位、外存地址,缺页中断（Page Fault）机构,在地址映射过程中，所访问的页不在内存时，便产生一缺页中断；OS接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，更新页表，完成重定位，使进程继续运行下去。这期间可能调用置换程序。,与常规中断的不同之处：,在指令执行期间产生和处理中断信号；,一条指令在执行期间，可能产生多次缺页中断。,3. 虚分页所需的硬件支持页表机制（似实分页的，只是扩充了,40,3. 虚分页所需的硬件支持（续1）,地址变换机构,（似实分页的，但重定位过程中可能触发缺页中断）,首先检索快表，若找到，修改页表项中的访问位，然后利用页表项中给出的页架号和页内地址，形成物理地址。,如果在快表中未找到相应的页表项，则检索内存中的页表，察看页表项中的状态位，若该页已经调入内存，则形成物理地址，并更新快表，当快表满时，应淘汰一个页表项；若该页尚未调入内存，则,产生缺页中断,，请求OS把该页调入内存，然后再完成重定位。,3. 虚分页所需的硬件支持（续1）地址变换机构（似实分页的，,41,4. 内存分配策略和分配算法,最小物理块（页架）数的确定,保证进程正常运行所需的最少页架数；,与指令的格式、功能和寻址方式有关。,页架的分配策略,固定分配局部置换,：进程占据的内存页架数不变；置换时在该进程所占页架中选则换出对象。系统给各进程分配固定数目的页架时，可考虑,按比例分,、平均分、结合工作集、结合优先权分配等策略。,可变分配全局置换：,初始时先给进程分配一定数目的页架，当进程缺页率较高或较低时，能由OS对其占据的页架数加以调整，置换时在整个内存用户区的页架中选则换出对象。,可变分配局部置换：,可变分配同上，置换时在运行进程所占页架中选则换出对象。,4. 内存分配策略和分配算法最小物理块（页架）数的确定,42,4. 内存分配策略和分配算法（续1）,工作集（Working Set）模型,Denning在1968年研究缺页率与页架数的关系时提出工作集的概念，旨在降低进程的缺页率。,一个进程当前使用的页的集合叫它的,工作集,。更形式化的定义是：对于给定的页面访问序列选取定长的区间，称为工作集窗口，落在工作集窗口中的页面集合称为,工作集。,例如，某访问序列为：,26157775162341234443434441327,| |t,1,| |t,2,则ws(t,1,)=1,2,5,6,7，ws(t,2,)=3,4,4. 内存分配策略和分配算法（续1）工作集（Working,43,尽量保持进程的工作集在内存可以降低进程的缺页率，这种方法叫,工作集模型,。依据是,局部性原理,。借助该模型，可实现可变分配、改进时钟置换算法等。,Windows 2000在系统初始化时，计算进程的最小和最大工作集值，当物理内存大于32MB（server大于64MB）时，进程缺省最小工作集为50页，最大工作集为345页。,尽量保持进程的工作集在内存可以降低进程的缺页率，这种方法叫工,44,4. 内存分配策略和分配算法（续2）,内存分配算法,同基本分页，管理物理页帧/空闲内存块的数据结构也是位示图,5. 调页策略,请求调页策略,（demand paging）,进程运行过程中靠缺页中断程序装入所需访问的不在内存的页面。实现简单，用得广，但费时。,预调页策略,（prepaging）,进程运行之前预先装入一些页面。主要用于进程的首次调入时，并且多涉及工作集模型的实现。,4. 内存分配策略和分配算法（续2）内存分配算法,45,5.,调页策略,（续1）,问题,从何处调入页面？,外存文件区、外存对换区、内存区,（共享页面或Buffer中页面的及时再利用）,页面的调入过程？,先由中断服务程序调内存分配程序,（可能触发对换程序）,获得一内存块，,再查页表，把所缺页从外存调入内存，并修改页表。,这是在重定位过程中实现的，对用户透明。,5. 调页策略（续1）问题,46,6. 页面置换,（淘汰 / 调度）,算法,Page Replacement Algorithms,颠簸（抖动）,在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象称为,颠簸,或,抖动,。例如，一个每隔几条指令就发生一次页面故障的进程称为在颠簸,（因为一条指令的执行只需几纳秒，而每从磁盘上读入一个页面则常需几十毫秒）,。,系统发生颠簸的原因,页面置换算法不合理,分配给进程的物理页面数太少,6. 页面置换（淘汰 / 调度）算法,47,6. 页面置换算法（续1）,最佳（OPTimal）置换算法,淘汰以后不再需要的或最远的将来才会用到的页面,。1966年Belady提出的理想算法，但无法实现，主要用于评价其他置换算法。,先进先出（FIFO）置换算法,选择在内存中驻留时间最长的页并淘汰之,。,它实现简单,：只需把进程在内存的页面按先后次序链成1个队列，并设置1个替换指针，使它总是指向内存中最老的页面。,缺点：,效率不高,，因为它与进程实际的运行规律不相适应，比如常用的全局变量所在的页面或者循环体所在页面都可能被它选为淘汰对象。另外，它,还有Belady异常,现象,（考虑页面访问序列为14，12，5，15的进程分别获得3块内存和4块内存请求装入执行时的缺页情况）,。,6. 页面置换算法（续1）最佳（OPTimal）置换算法,48,6. 页面置换算法（续2）,最近最少使用,（,LRU, Least Recently Used ）,置换算法,选择最后一次访问时间距离当前时间最长的一页并淘汰之。该算法理论上性能好，但实现代价高,（,需硬件支持,，如：为进程每个内存页面设一,计时器,或,寄存器,，或为进程所有内存页面设一,栈/,链表，,P98,）,。,LRU的软件解决方案,（LRU的近似算法）,：,二次机会(SC,Second Chance,）,置换算法,时钟,(Clock),置换算法,最近未使用,（,NRU, Not Recently Used ）,置换算法,6. 页面置换算法（续2）最近最少使用（LRU, Leas,49,6. 页面置换算法（续3）,二次机会,(,SC,Second Chance,）,置换算法,FIFO法的一种改进实现,实现,：,页表目中增设访问位R，初值为0，页面访问时置1。,发生缺页中断需置换时，,OS按照,先进先出,置换算法选择某一页面，检查其,访问位,，如果为0，则淘汰该页，如果为1，则将该位置0，把该页放到内存页面链表的尾端，给它第二次驻留机会，再检查内存页面链上的下一个页面。如果查到链尾还未找到置换对象，则再从链首开始，进行第2趟扫描检查。,优点,：,实现简单，且性能比FIFO好很多；,缺点,：,运行效率低，时间开销大。,6. 页面置换算法（续3）二次机会(SC, Second,50,6. 页面置换算法（续4）,时钟,(Clock),置换算法,SC的一种改进实现,SC算法因为常需把给予二次驻留机会的页面移到链尾而降低效率，若把其所用的内存页面单向链表改为循环链表，则就不必在链中移动页面了。这种改进的SC法就是Clock法。,显然，Clock算法的页面调度性能与SC法一样，但其自身的运行效率比SC法高，因而比SC法更常用。其实，Clock法,从某种角度,也可看作一种LRU近似算法。,6. 页面置换算法（续4）时钟(Clock)置换算法SC算,51,6. 页面置换算法（续5）,最近未使用,（,NRU, Not Recently Used ）,置换算法,选择在最近一段时间内未使用过的一页并淘汰之。,实现,：页表目中增设访问位R，修改位M。启动进程时，R、M置0，随后R被定期清零。根据R、M的值，进程在内存的页面分为4类：00,类、,01,类、 1,0,类、 11类。发生缺页中断需置换时，,OS,从编号最小的非空类中随机选择一页淘汰。,特点,：易实现，性能上也够用。,6. 页面置换算法（续5）最近未使用（NRU, Not R,52,其他置换算法,（仅作一般了解）,最少使用频率,（,LFU, Least Frequently Used ）,置换算法,选择在最近时期使用频率最少的页面淘汰。,页面缓冲置换算法,=,FIFO,+,page-buffer,+,write-delay,该算法用在VAX/VMS中，利用了,延迟写,技术，调度性能也不错，但延迟写都存在安全隐患。Windows2000采用可变分配局部置换策略，也用类似的置换算法。,6. 页面置换算法（续6）,其他置换算法（仅作一般了解）6.,53,例3.2,设某请求分页系统采用固定分配局部置换策略，一进程的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，该进程分得3个页架，初始为空，试计算分别采用FIFO、LRU、OPT置换算法时该进程访问过程中所发生的缺页次数和依次被换出的页面。,解,： FIFO,4 3 2 1 4 3 5 4 3 2 1 5,4 4 4,1,1,1,5,5 5 5,5 5,3,3 3,4,4,4 4 4,2,2 2,2,2,2,3,3 3 3,3,1,1,是否命中,x x x x x x x,x x,所以该进程运行时共发生缺页中断9次，被换出的页面依次是4、3、2、1、4、3。,6. 页面置换算法（续7）,链首oldest,：,链尾newest,：,页架1,页架2,页架3,例3.2 设某请求分页系统采用固定分配局部置换策略，一进程的,54, LRU,4 3 2 1 4 3 5 4 3 2 1 5,栈：,4,3 2 1 4 3 5,4 3,2 1 5,4,3 2 1 4 3 5 4 3 2 1,4 3 2 1 4 3 5 4 3 2,是否命中,x x x x x x x,x x x,所以该进程运行时共发生缺页中断10次，被换出的页面依次是4、3、2、1、5、4、3。,6. 页面置换算法（续8）, LRU 4 3 2 1 4 3 5,55, OPT,4 3 2 1 4 3 5 4 3 2 1 5,页架1,4 4 4 4 4 4 4 4,4,2 2 2,页架2,3 3 3 3 3 3 3 3,3,1 1,页架3,2,1 1,1,5 5 5 5 5 5,是否命中,x x x x,x,x x,所以该进程运行时共发生缺页中断7次，被换出的页面依次是2、1、4、3。,6. 页面置换算法（续9）, OPT 4 3 2 1 4 3,56,例3.3,设某请求分页系统采用固定分配局部置换策略，置换算法为FIFO。一进程在内存中分得m块，初始为空，其页面走向为1，2，3，4，1，2，5，1，2，3，4，5。问：当m=3，m=4时各发生缺页几次？,解,： m=3时，缺页中断9次；,m=4时，缺页中断10次。,注,：,FIFO页面置换算法会产生异常现象（Belady现象），即：当分配给进程的物理页面数增加时，缺页次数不降反增。,其实，上例也是,。,其他置换算法没有此异常。,6. 页面置换算法（续10）,例3.3设某请求分页系统采用固定分配局部置换策略，置换算法为,57,分配给进程的物理页面数,页面本身的大小,程序的编制方法,页面淘汰算法,例子3.4,设某请求分页系统采用固定分配局部置换策略，置换算法为LRU。,进程分得3页架，初始时全空，以下代码占1页，页面大小为128个整数；矩阵A,128X128,在逻辑地址空间中按行存放。,程序编制方法1：,For j:=1 to 128,For i:=1 to 128,Ai,j:=0;,程序编制方法2：,For i:=1 to 128,For j:=1 to 128,Ai,j:=0;,则该进程在两种编程方法下的缺页次数分别为：16385和129。,影响缺页率的主要因素,分配给进程的物理页面数例子3.4设某请求分页系统采用固定分配,58,3.4 段式存储管理,需用“紧凑”才能消除碎片的一种,离散分配,技术，但便于代码共享与增长,实分段式存储管理（基本分段）,虚拟段式存储管理（请求分段）,3.4 段式存储管理需用“紧凑”才能消除碎片的一种离散,59,3.4.1 实分段式存储管理,(基本分段技术),为方便用户编程和克服基本分页存储管理的缺点而引入,1. 基本思想（,可重定位可变分区+离散分配,）,进程地址空间划分,按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名，且有一个段号。段号从0开始，每一段也从0开始编址，段内地址是连续的。,(分段是由用户或,编译器负责,的）,逻辑地址,（,注意,：分段地址空间是,真正二维,的）,段号 段内地址,3.4.1 实分段式存储管理(基本分段技术),60,0,116,N,.,.,.,0,S,工作区段B,主程序段M,.,.,.,.,.,.,0,E,P,子程序段X,0,K,.,.,.,CALL X E,.,.,.,.,.,.,.,.,.,CALL Y F,CALL A 116,.,.,.,.,.,.,0,F,L,子程序段Y,数组A,12345,.,.,.,进程地址空间分段示意图：,0116N.0S工作区段B主程序段M.,61,1.,基本思想（续）,内存空间划分,内存空间以段为单位被动态地划分为若干个长度不相同的区域，称为物理段，每个物理段由起始地址和长度确定，相当于可变分区管理中的一个分区。,内存分配,以段为单位分配内存，每一个段在内存中占据一个连续区域，但同一进程的各段对应的物理段可以不连续。,进程运行时，其各段必须全部装入内存,1. 基本思想（续）内存空间划分,62,2. 管理,段表,记录了进程的每个逻辑段及其物理段的对应关系。,每个进程设置一个段表，放在内存，属于其现场信息。,空闲块管理,空闲块链/表（似可变分区中的）,内存分配算法（,似可变分区中的,）,段号,0,1,2,物理段首址,段长度,58K,20K,100K,110K,260K,140K,2. 管理段表段号012物理段首址段长度58K20K100,63,段表示意图：,B,0,S,A,0,N,Y,0,L,X,0,P,M,0,K,逻辑段号,0,1,2,3,4,进程1的地址空间,1000,3200,5000,6000,8000,P,K,S,L,N,内存,K 3200,P 1500,L 6000,N 8000,S 5000,段长 段始址,0,1,2,3,4,操作系统,.,.,.,.,.,段表,段表示意图：B0SA0NY0LX0PM0K逻辑段号01234,64,3. 硬件支持,系统设置一对寄存器和一个联想存储器：,段表始址寄存器：,用于保存正在运行进程的段表的始址,段表长度寄存器：,用于保存正在运行进程的段表的长度（例如上图的段表长度为5，它与段长及扩充段表目中的存取控制字一起用于分段管理中的存取保护）,联想存储器，即快表,用途：保存正在运行进程的段表的子集（部分表项）,特点：按内容并行查找,快表表目内容：,段号、段始址、段长、标识（状态）位；访问位,快表置换问题？,3. 硬件支持系统设置一对寄存器和一个联想存储器：,65,C,l,C,b,+,段号S 段内地址,d,比较,b + d,段,表,S=,C,l,快表,物理地址,段表始址寄存器,段表长度寄存器,逻辑地址,l,b,.,.,.,S,l,b,地址越界,d=1,分段地址映射及,存储保护,机制,地址越界,比较,+,Cl Cb+段号S 段内地址d比较b + d段表S,66,4. 实分段式存储管理小结,优点：,便于动态申请内存,便于共享,(P103),便于动态链接,管理和使用统一化,缺点：,似可重定位可变分区,，如产生碎片，内存利用率低；紧凑开销大，需硬件支持多，进程受内存可用空间限制等。,思考,：1) 分段与可重定位可变分区的异同？,2),分段与分页的主要不同,？,（PP104105）,自学：分段与分页的结合,段页式存储管理(P109),4. 实分段式存储管理小结优点：便于动态申请内存,67,1. 段表内容,比实分段新增：,特征位（在/不在内存，是否可共享）,存取权限位（读，写，执行允许位）,标志位（是否修改过，能否移动）,扩充位（固定长/可扩充 ）,3.4.2 虚拟段式存储管理,实分段+对换和请求装入功能,1. 段表内容3.4.2 虚拟段式存储管理,68,进程在执行过程中，有时需要扩大分段，如数据段。由于要访问的地址超出原有的段长，所以发越界中断。操作系统处理中断时 ，首先判断该段的“扩充位”，如可扩充，则增加段的长度；否则按出错处理,2. 越界中断处理,进程在执行过程中，有时需要扩大分段，如数据段。由于要访问,69,检查内存中是否有足够的空闲空间,若有，则装入该段，修改有关数据结构，中断返回,若没有，检查内存中空闲区的总和是否满足要求，是则应采用紧缩技术，转 ；否则，淘汰一（些）段，转,3. 缺段中断处理,检查内存中是否有足够的空闲空间3. 缺段中断处理,70,大型程序包含：,若干程序段，若干数据段,一些熟知的事实：,进程的某些程序段在进程运行期间可能根本不用,互斥执行的程序段没有必要同时驻留内存,有些程序段执行一次后不再用到,4. 段的动态链接,大型程序包含：4. 段的动态链接,71,静态链接：为了程序正确执行，必须由连接装配程序把它们连接成一个可运行的目标程序，并在程序运行前都装入内存。,问题,：花费时间，浪费空间,动态链接：,在程序开始运行时，只将主程序段装配好并调入内存，其它各段的装配是在主程序段的运行过程中逐步完成。每当需要调用一个新段时，再将这个新段装配好，并与主程序段链接,实现,：需编译器配合支持。,4. 段的动态链接（续1）,静态链接：为了程序正确执行，必须由连接装配程序把它们连接,72,4. 段的动态链接（续2）,机器指令的两种寻址方式,：直接寻址，间接寻址,LOAD,100,600,直接寻址,100,数据,600,LOAD,100,800,间接寻址,100,间接字,数据,800,链接间接字和链接中断,采用间接寻址时，间接地址指示的单元的内容称为,间接字,，在链接间接字中，包含了直接地址和附加的状态位。格式为：,L,直接地址,L：链接标志位,（ L=0：该段已经建立了链接；L=1：该段尚未链接）,CPU执行间接指令时，硬件能对链接字中链接标志位进行判断。当L=1时，硬件发出,链接中断,，并停止执行该条指令，转去执行中断处理程序。处理完后,（L已被处理程序改为0）,，再重新执行该间接指令；若L=0，则根据间接字中的直接地址去取数据。,4. 段的动态链接（续2）机器指令的两种寻址方式：直接寻址，,73,LOAD 1, A|,编译前,LOAD* 1, 3|100,.,.,100,678,1,3,.,678 7“A|”,.,编译后,链接前,编译器的准备工作,（把对外段的符号访问译成了对本段链接间接字的间接访问）,：,4. 段的动态链接（续3）,LOAD 1, A|,74,3段,LOAD* 1, 3|100,100,678 7“A|,120,0,4,链接后,：,4段, 即A段,120 ：12345,4. 段的动态链接（续4）,3段 12004链接后：4段, 即A段4,75,链接中断处理,根据链接间接字找出要访问段的符号名和段内地址,分配段号，检查该段是否在内存，若不在，则从外存调入，并登记段表，修改内存分配表,修改间接字：修改连接标志位为0，修改直接地址,重新启动被中断的指令执行,由于只有“,纯段,”才可被共享，因此链接间接字应该放在,杂段,中。,请求分段的其他存储管理任务的实现似基本分段和请求分页,。,4. 段的动态链接（续5）,链接中断处理4. 段的动态链接（续5）,76,PP109112：综合练习题三,补充题1（似七.4）,某分页系统中，经快表完成的一次内存访问需100ns，经页表完成的一次内存访问需180ns，要使一次有效的内存访问时间达到120ns，则访问快表的命中率必须是多少？,补充题2,某分页系统中，当进程所访问的页面在内存时，完成一次内存访问需200ns。当所访问的页面不在内存时，则如果内存有空闲页架或者被换出页面未改写过，那么完成一次内存访问需7ms；否则需要15ms。如果页面故障率为5%，要换出的页面中有60%改写过，系统只运行单一进程，CPU在页面交换时是闲置的，那么有效的访问时间是多少？,本章作业,PP109112：综合练习题三本章作业,77,