第四章 存储器管理

2020/5/25,1,学院:计算机与信息技术学院教师:刘贤梅,第四章存储器管理,2020/5/25,2,内容概述,4.1存储器的层次结构4.2程序的装入和链接4.3连续分配方式4.4基本分页存储管理方式4.5基本分段存储管理方式4.6虚拟存储器的基本概念4.7请求分页存储管理方式4.8页面置换算法4.9请求分段存储管理方式,2020/5/25,3,4.1存储器的层次结构,多级存储器结构,寄存器,高速缓存,主存,磁盘缓存,磁盘,可移动存储介质,辅存,主存,CPU寄存器,图4-1计算机系统存储层次示意,2020/5/25,4,内容概述,4.1存储器的层次结构4.2程序的装入和链接4.3连续分配方式4.4基本分页存储管理方式4.5基本分段存储管理方式4.6虚拟存储器的基本概念4.7请求分页存储管理方式4.8页面置换算法4.9请求分段存储管理方式,2020/5/25,5,4.2程序的装入和链接,图4-2对用户程序的处理步骤,多道程序环境下，程序要运行必须为之创建进程，而创建进程的第一件事就是分配内存。源程序要运行通常经过编译(compile)链接(link)装入(load)等几个步骤。,2020/5/25,6,(1)编译。由编译程序将用户源代码编译成若干个目标模块。(2)链接。由链接程序将编译后形成的目标模块以及它们所需要的库函数,链接在一起,形成一个装入模块。(3)装入。由装入程序将装入模块装入主存的过程。,2020/5/25,7,4.2程序的装入和链接,4.2.1程序的装入1.绝对装入方式2.可重定位装入方式3.动态运行时装入方式4.2.2程序的链接1.静态链接2.装入时动态链接3.运行时动态链接,2020/5/25,8,1.绝对装入方式(适合“单道”)在编译时,如果知道程序将驻留在内存的什么位置,则编译程序产生绝对地址的目标代码。装入模块被装入内存后,由于程序中的逻辑地址与实际内存地址完全相同,故不需对程序和数据的地址进行修改。程序中所使用的绝对地址,既可在编译或汇编时给出，也可由程序员直接赋予。但在由程序员直接给出绝对地址时，不仅要求程序员熟悉内存的使用情况,而且一旦程序或数据被修改后，可能要改变程序中的所有地址。因此，通常是宁可在程序中采用符号地址，然后在编译或汇编时，再将这些符号地址转换为绝对地址。,2020/5/25,9,2020/5/25,10,2.可重定位装入方式(可用于“多道”)-静态重定位在多道程序环境下，不可能预知目标模块放在内存中的地址，因此绝对装入方式不适合在多道环境下使用。程序中目标模块的地址通常从0开始，其他地址都是相对于0计算。把在装入时对目标程序中指令和数据的修改过程称为重定位，又因为地址变换通常是在装入时一次完成的，以后不再改变，故称为静态重定位。静态重定位特点：简单、不能在内存中移动、要求连续。,重定位的实质是地址变换，将作业地址空间中的逻辑地址变换为主存空间中的物理地址。,2020/5/25,11,图4-3作业装入内存时的情况,12500,2020/5/25,12,如何将程序在内存中从10000移动到20000？,22500,2020/5/25,13,3.动态运行时装入方式(可用于“多道”)可重定位方式不允许程序运行时在内存中移动位置。装入程序，在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是相对地址，依靠硬件支持进行地址转换。重定位寄存器的支持。动态重定位特点：在内存中可移动。,2020/5/25,14,4.2程序的装入和链接,4.2.1程序的装入1.绝对装入方式2.可重定位装入方式3.动态运行时装入方式4.2.2程序的链接1.静态链接2.装入时动态链接3.运行时动态链接,2020/5/25,15,4.2.2程序的链接,1.静态链接方式在程序运行前，先将各目标模块及所需的库函数链接成一个完整的装入模块，以后不再拆开。在将这几个目标模块装配成一个装入模块时，须解决以下两个问题：(1)对相对地址进行修改(2)变换外部调用符号,2020/5/25,16,图4-4程序链接示意图,2020/5/25,17,2.装入时动态链接将用户的源程序编译后所得的一组目标模块在装入内存时采用边装入边链接的方式。优点:(1)便于目标模块的修改和更新(2)便于实现对目标模块的共享,2020/5/25,18,3.运行时动态链接应用程序在每次运行的模块可能不相同，出错模块不一定什么时候运行。运行时动态链接方式将对某些模块的链接推迟到执行时才去做，即在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。,2020/5/25,19,2020/5/25,20,内容概述,4.1存储器的层次结构4.2程序的装入和链接4.3连续分配方式4.4基本分页存储管理方式4.5基本分段存储管理方式4.6虚拟存储器的基本概念4.7请求分页存储管理方式4.8页面置换算法4.9请求分段存储管理方式,2020/5/25,21,4.3连续分配方式,4.3.1单一连续分配4.3.2固定分区分配4.3.3动态分区分配4.3.4可重定位分区分配4.3.5对换(Swapping),2020/5/25,22,4.3.1单一连续分配,为一个用户程序分配一个连续的内存空间用于单用户、单任务的操作系统中。把内存分为系统区和用户区两部分，系统区仅提供给OS使用，通常是放在内存的低址部分；用户区是指除系统区以外的全部内存空间，提供给用户使用。特点(1)简单易行，系统开销小。(2)资源利用率低(一次只能装入一个作业)。,2020/5/25,23,图单一连续分配,2020/5/25,24,4.3连续分配方式,4.3.1单一连续分配4.3.2固定分区分配4.3.3动态分区分配4.3.4可重定位分区分配4.3.5对换(Swapping),2020/5/25,25,4.3.2固定分区分配,最简单的可运行多道程序的存储管理方式将内存用户空间划分为若干个固定大小的区域，每个分区中只装入一道作业。1.划分分区的方法(1)分区大小相等分区太大，浪费；分区太小，不够用。(2)分区大小不等根据程序大小决定所使用的分区，大班在大教室、小班在小教室。,2020/5/25,26,图4-5固定分区使用表,2.内存分配按分区使用表进行分配，依分区大小排序。,2020/5/25,27,固定分区分配,2020/5/25,28,3.特点,(1)一个作业只能装入一个分区，一个分区只能装入一个作业，当分区大小不能满足作业的要求时,该作业暂时不能装入。(2)通过对“分区使用表”的改写，来实现主存的分配与回收。作业在执行时，不会改变存储区域，所以采用静态地址重定位方式。此方法易于实现，系统开销小。(3)当分区较大作业较小时，仍然浪费许多主存空间，很难避免内部碎片。并且分区总数固定，限制了并发执行的作业数目。,2020/5/25,29,4.3连续分配方式,4.3.1单一连续分配4.3.2固定分区分配4.3.3动态分区分配4.3.4可重定位分区分配4.3.5对换(Swapping),2020/5/25,30,动态分区分配内存使用情况示意图,4.3.3动态分区分配,动态地从可用内存中划分出一个分区,2020/5/25,31,1.分区分配中的数据结构空闲分区表:记录每个空闲分区的情况。,2020/5/25,32,图4-6空闲链结构,1.分区分配中的数据结构空闲分区链实现对空闲分区的分配和链接。,2020/5/25,33,2.分区分配算法(1)首次适应算法FF算法描述空闲分区链以地址递增顺序链接，分配时从链首开始查找，找到一个大小可满足的空闲分区,划出一块给请求者。优点(1)分配算法简单；(2)优先利用低址部分，保留了高址的大空闲区，为大作业装入提供条件。缺点(1)每次从链首开始，增加了查找开销；(2)留下许多难以利用的”碎片”(外碎片),2020/5/25,34,2.分区分配算法(2)循环首次适应算法算法描述空闲分区链以地址递增顺序链接，链表为循环链表；每次分配时从上一次找到空闲分区的下一个空闲区开始。优点使空闲分区分布均匀，减少查找空闲分区开销。缺点会缺乏大的空闲分区。,2020/5/25,35,2.分区分配算法(3)最佳适应算法算法描述每次分配时，把能满足要求、又是最小的分区分配给作业；空闲分区链以大小递增顺序链接，从头开始，第一次找到满足要求的空闲分区，必然是最优的，避免了“大材小用”。特点(1)解决了大作业的分配问题；(2)每次总是最小的,容易产生不可利用的空闲区(“小碎片”)。,2020/5/25,36,3.分区分配操作,1)分配内存,图4-7内存分配流程,2020/5/25,37,图4-8内存回收时的情况,2)回收内存从空闲链表区找到相应的插入点，有以下几种情况：回收区与插入点的前一个空闲分区相邻接回收区与插入点的后一个空闲分区相邻接回收区同时与插入点的前、后两个分区相邻接回收区不与任何空闲区邻接,2020/5/25,38,图动态分区分配方式中释放一个分区的流程,2020/5/25,39,4.特点,分区的长度不是预先固定的，而是按作业的实际需求来划分的。分区的个数也不是预先确定的，而是由装入的作业数决定的。分区的大小由作业的大小来定，提高了主存的使用效率。在主存分配过程中，会产生许多“外碎片”。“外碎片”是指小的无法使用的主存空间，使主存空间仍有一定的浪费。,2020/5/25,40,4.3连续分配方式,4.3.1单一连续分配4.3.2固定分区分配4.3.3动态分区分配4.3.4可重定位分区分配4.3.5对换(Swapping),2020/5/25,41,4.3.4可重定位分区分配,图4-9紧凑的示意,1.可重定位的引入连续分配存在的问题：必须有足够大的连续空间才能分配。“拼接”或“紧凑”的引入。紧凑之后，必须对程序或数据进行重定位。,2020/5/25,42,图4-10可重定位示意图,2.可重定位的实现作业装入内存后的所有地址仍是相对地址，将相对地址转换成物理地址的工作在指令执行时进行。地址变换过程是在程序执行期间，随着每条指令和数据的访问而自动进行的。真正访问地址=相对地址+重定位寄存器中地址。需要有硬件地址变换机构的支持。,2020/5/25,43,3.可重定位分区分配算法,图4-11可分区分配算法流程图,2020/5/25,44,4.3连续分配方式,4.3.1单一连续分配4.3.2固定分区分配4.3.3动态分区分配4.3.4可重定位分区分配4.3.5对换(Swapping),2020/5/25,45,4.3.5对换,1.对换的引入对换：指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存。对换是提高内存利用率的有效措施。如果对换是以整个进程为单位，称为“整体对换”或“进程对换”；如果对换是以“页”或“段”为单位进行的，则称为“页面对换”或“分段对换”，又统称为“部分对换”，这种对换方法是实现请求分页及请求分段式存储器的基础，其目的是为了支持虚拟存储系统。,2020/5/25,46,2.对换空间的管理在具有对换功能的OS中,通常把外存分为文件区和对换区文件区管理的主要目标是提高文件存储空间的利用率,采取离散分配方式。外存中对换区主要存放从内存中换出的进程,对换空间管理的主要目标是提高进程换入和换出的速度。为了能对对换区中的空闲盘块进行管理,在系统中应配置相应的数据结构,以记录外存的使用情况。其形式与内存在动态分区分配方式中所用数据结构相似,即同样可以用空闲分区表或空闲分区链。在空闲分区表中的每个表目中应包含两项,即对换区的首址及其大小,它们的单位是盘块号和盘块数对换区的分配采用连续分配方式,分配算法可以是首次适应算法、循环首次适应算法或最佳适应算法。,2020/5/25,47,3.进程的换出与换入(1)进程的换出选出被换出的进程选择原则:先“阻塞”或“睡眠”的进程,后“就绪”优先级低的进程在内存最长的进程的进程换出最近最久未使用进程进程换出过程系统首先选择处于“阻塞”状态且优先级最低的进程作为换出进程,然后启动盘块,将该进程的程序和数据传送到磁盘的对换区上。若传送过程未出现错误,便可回收该进程所占用的内存空间,并对该进程的进程控制块做相应的修改。,2020/5/25,48,3.进程的换出与换入(2)进程的换入系统应定时地查看所有进程的状态,从中找出(PCB集合中)“就绪”状态且已换出的进程,将其中换出时间(换出到磁盘上)最久的进程作为换入进程,申请内存,若成功将之换入,否则在换出某些进程,腾出足够内存,在换入。,2020/5/25,49,内容概述,4.1存储器的层次结构4.2程序的装入和链接4.3连续分配方式4.4基本分页存储管理方式4.5基本分段存储管理方式4.6虚拟存储器的基本概念4.7请求分页存储管理方式4.8页面置换算法4.9请求分段存储管理方式,2020/5/25,50,离散分配方式思想：,连续分配方式要求为一个进程分配连续的内存空间(整体装入)，形成许多“碎片”而浪费，“紧凑”操作会付出相当大的代价。如果允许一个进程直接分散地装入到许多不相邻接的分区中，称为离散分配方式。离散分配方式有分页存储管理方式、分段存储管理方式和段页存储管理方式。,2020/5/25,51,4.4.1页面与页表4.4.2地址变换机构4.4.3两级和多级页表,4.4基本分页存储管理方式,2020/5/25,52,4.4.1页面与页表,1.页面页面：将一个进程的逻辑地址空间分成若干个大小相等的片称为页面或页。物理块：把内存空间分成与页面相同大小的若干个存储块,称为物理块或页框。页内碎片：在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块而形成了不可利用的碎片。页面大小：2的幂，512B8KB,2020/5/25,53,2.地址结构,分页地址包括页号和页内地址，其地址结构如下:,31,12,11,0,对某特定机器,其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得:,2020/5/25,54,例：系统页面大小为1KB，逻辑地址为2170B，求页号与页内地址。页号P=INT2170/1024=2页内地址d=2170mod1024=122B第0页01023第1页10242047第2页20482170,2020/5/25,55,图4-11页表的作用,3.页表为每个进程建立一张页面映像表，简称页表。作用：是实现从页号到物理块号的地址映射。存取控制字段：对该存储块中的内容加以保护。,2020/5/25,56,4.4.1页面与页表4.4.2地址变换机构4.4.3两级和多级页表,4.4基本分页存储管理方式,2020/5/25,57,4.4.2地址变换机构,1.基本地址变换机构用于实现从逻辑地址到物理地址的转换，将逻辑地址中的页号转换为内存中的物理块号。页表大多驻留在内存中，在系统中设置页表寄存器，在其中存放页表在内存中的始址和页表的长度。进程未执行时，页表的始址和页表长度存放在本进程的PCB中，当调度程序调度到某进程时，才将这两个数据装入页表寄存器。,2020/5/25,58,图4-13分页系统的地址变换机构,以页号查页表，得到对应页装入内存的块号。内存地址物理块号页大小页内地址,b,w,2020/5/25,59,2.具有快表的地址变换机构由于页表是存放在内存中，因此每次CPU存取一个数据要两次访问内存，即，查页表时要作一次访问内存的工作，然后是访问程序要求访问的内存，这样，存取速度降低一倍，将会影响整个系统的使用效率。为提高地址变换速度，在地址变换机构中增设一个具有并行查寻能力的高速缓冲寄存器，又称为“联想寄存器”或“快表”，用以存放当前访问的那些页表项，价格贵。快表通常可存放16-512个表项，命中率可达90以上。,2020/5/25,60,图4-14具有快表的地址变换机构,2020/5/25,61,4.4.1页面与页表4.4.2地址变换机构4.4.3两级和多级页表,4.4基本分页存储管理方式,2020/5/25,62,4.4.3两级和多级页表,现代的大多数计算机系统，都支持非常大的逻辑地址空间(232264)。在这样的环境下，页表就变得非常大,要占用相当大的内存空间。例如，对于一个具有32位逻辑地址空间的分页系统，若规定页面大小为4KB即212B，则在每个进程页表中的页表项可达1M(220)个之多。每个页表项占用4个字节(32bit)，故每个进程仅仅其页表就要占用4MB的内存空间，而且还要求是连续的。,31,12,11,0,220=1M,2020/5/25,63,可以采用两个方法来解决这一问题：采用离散分配方式来解决难以找到一块连续的大内存空间的问题。只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。,2020/5/25,64,1.两级页表可利用将页表分页，并离散地将各个页面分别存放在不同的物理块中，同样要为离散分配的页表再建立一张页表，称为外层页表(OuterPageTable),每个页表项中记录了页表页面的物理块号。,210=1024,210=1024,212=4KB,2020/5/25,65,图4-15两级页表结构,两级页表结构,每个物理块为4KB,恰好放一个1页页表(1024个项,每项4B),共需1024个这样的块,2020/5/25,66,图4-16具有两级页表的地址变换机构,2020/5/25,67,2.多级页表对于32位的机器,采用两级页表结构是合适的;但对于64位的机器,如果页面大小仍采用4KB即212B,那么还剩下52位,假定仍按物理块的大小(210位)来划分页表,则将余下的42位用于外层页号。此时在外层页表中可能有4096G个页表项,要占用16384GB的连续内存空间。必须采用多级页表,将外层页表再进行分页,也是将各分页离散地装入到不相邻接的物理块中,再利用第2级的外层页表来映射它们之间的关系对于64位的计算机,如果要求它能支持264(=1844744TB)规模的物理存储空间,则即使是采用三级页表结构也是难以办到的;而在当前的实际应用中也无此必要,2020/5/25,68,具有64位地址的分页存储管理,242=4096G,210=1024,212=4KB,63,2020/5/25,69,内容概述,4.1存储器的层次结构4.2程序的装入和链接4.3连续分配方式4.4基本分页存储管理方式4.5基本分段存储管理方式4.6虚拟存储器的基本概念4.7请求分页存储管理方式4.8页面置换算法4.9请求分段存储管理方式,2020/5/25,70,4.5基本分段存储管理方式,4.5.1分段存储管理方式的引入4.5.2分段系统的基本原理4.5.3信息共享4.5.4段页式存储管理方式,2020/5/25,71,4.5.1分段存储管理方式的引入,分段存储管理的主要目的是为了满足用户在编程和使用上的要求。方便编程(这是主要的因素)用户作业通常按逻辑关系分若干个段如LOAD1,A|;信息共享程序与数据的共享是以信息的逻辑单位为基础信息保护动态增长动态链接,2020/5/25,72,4.5基本分段存储管理方式,4.5.1分段存储管理方式的引入4.5.2分段系统的基本原理4.5.3信息共享4.5.4段页式存储管理方式,2020/5/25,73,4.5.2分段系统的基本原理,1.分段作业的地址空间被分成若干个段,每个段定义了一组逻辑信息。分段地址中的地址具有如下结构,3116150,2020/5/25,74,2.段表为每个分段分配一个连续的分区，而进程中的各个段可以离散地移入内存中的不同的分区中。系统为每个进程建立一张段映射表，简称为“段表”。每个段在段表中占一个表项，其中记录了该段在内存中的起始地址(又称为“基址”)和段的长度。实现从逻辑段到物理内存区的映射。,2020/5/25,75,图4-17利用段表实现地址映射,2020/5/25,76,图4-18分段系统的地址变换过程,3.地址变换机构,2020/5/25,77,4.分页和分段的主要区别页是信息的物理单位，是为了消减内存的外零头，提高内存的利用率；段是信息的逻辑单位，分段的目的是为了更好地满足用户的需要。页的大小固定，且由系统自动决定；段的大小不固定，决定于用户所编写的程序。分页的作业地址空间是一维的；分段的作业地址空间是二维的。,2020/5/25,78,4.5基本分段存储管理方式,4.5.1分段存储管理方式的引入4.5.2分段系统的基本原理4.5.3信息共享4.5.4段页式存储管理方式,2020/5/25,79,4.5.3信息共享,分段存储的一个优点是易于实现段的共享，即允许若干个进程共享一个或多个分段。分页系统中虽然也能实现程序和数据的共享，但远不如分段系统方便。可重入代码又称为“纯代码”是一种允许多个进程同时访问的代码。可重入代码是一种不允许任何进程对它进行修改的代码。(1)程序在执行时可能改变的部分,拷贝到该局部数据区。(2)程序执行时,只对该数据区(属于该进程私有)中的内容进行修改,而不去改变共享的代码。,2020/5/25,80,图4-19分页系统中共享editor的示意图,2020/5/25,81,图4-19分段系统中共享editor的示意图,2020/5/25,82,4.5基本分段存储管理方式,4.5.1分段存储管理方式的引入4.5.2分段系统的基本原理4.5.3信息共享4.5.4段页式存储管理方式,2020/5/25,83,4.5.4段页式存储管理方式,1.基本原理是分段和分页原理的结合。将用户程序分成若干个段，并为每一段赋予一个段名，再把每一段分成若干个页，把主存分成与页大小相同的块，每段分配与其页数相同的主存块，主存块可以连续，也可以不连续。段页式管理中，逻辑地址由段号、段内页号及页内地址三部分所组成。,2020/5/25,84,图4-21段页式地址结构,2020/5/25,85,图4-22利用段表和页表实现地址映射,2020/5/25,86,2.地址变换过程,图4-23段页式系统中的地址变换机构,2020/5/25,87,内容概述,4.1存储器的层次结构4.2程序的装入和链接4.3连续分配方式4.4基本分页存储管理方式4.5基本分段存储管理方式4.6虚拟存储器的基本概念4.7请求分页存储管理方式4.8页面置换算法4.9请求分段存储管理方式,2020/5/25,88,4.6虚拟存储器的基本概念,4.6.1虚拟存储器的引入4.6.2虚拟存储器的实现方法4.6.3虚拟存储器的特征,2020/5/25,89,4.6.1虚拟存储器的引入,1.作业装入内存时可能会出现如下问题(1)作业太大，因无足够内存而不能装入，无法运行。(2)无足够内存满足大量作业运行的要求。只能将少量作业装入内存让它们先运行，而将大量作业留在外存上等待。解决方法:(1)增加内存容量(从物理上增加内存容量)，成本加大。(2)逻辑上扩充内存容量，即采用虚拟存储技术。,2020/5/25,90,2.虚拟存储器定义虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其逻辑容量由外存容量所决定。其运行速度接近于内存速度，而每位的成本却又接近于外存。虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于大、中、小型机器和微型机中。,2020/5/25,91,4.6虚拟存储器的基本概念,4.6.1虚拟存储器的引入4.6.2虚拟存储器的实现方法4.6.3虚拟存储器的特征,2020/5/25,92,4.6.2虚拟存储器的实现方法,1.请求分页系统在分页系统的基础上增加了请求调页功能和页面置换功能。(1)硬件支持请求分页的页表机制，它是在纯分页的页表机制上增加若干项而形成的，作为请求分页的数据结构；缺页中断机构，即每当用户程序要访问的页面尚未调入内存时便产生一缺页中断，以请求OS将所缺的页调入内存；地址变换机构，它同样是在纯分页地址变换机构的基础上发展形成的(2)实现请求分页的软件用于实现请求调页的软件和实现页面置换的软件。,2020/5/25,93,2.请求分段系统在分段系统的基础上,增加了请求调段及分段置换功能。(1)硬件支持请求分段的段表机制缺段中断机构地址变换机构(2)软件支持用于实现请求调段的软件和实现分段置换的软件。,2020/5/25,94,4.6虚拟存储器的基本概念,4.6.1虚拟存储器的引入4.6.2虚拟存储器的实现方法4.6.3虚拟存储器的特征,2020/5/25,95,4.6.3虚拟存储器的特征,1.离散性离散性是指在主存分配时采用离散分配方式。2.多次性一个作业被分成多次调入内存运行3.对换性允许在作业的运行过程中进行换进、换出4.虚拟性能够从逻辑上扩充内存容量,使用户所看到的内存容量远大于实际内存容量。,2020/5/25,96,内容概述,4.1存储器的层次结构4.2程序的装入和链接4.3连续分配方式4.4基本分页存储管理方式4.5基本分段存储管理方式4.6虚拟存储器的基本概念4.7请求分页存储管理方式4.8页面置换算法4.9请求分段存储管理方式,2020/5/25,97,4.7请求分页存储管理方式,4.7.1请求分页中的硬件支持4.7.2内存分配策略和分配算法4.7.3调页策略,2020/5/25,98,4.7.1请求分页中的硬件支持,1.页表机制它是在分页存储管理系统上增加了请求调页功能、页面置换功能所形成的分页式虚拟存储管理系统。每个页表(增加了四个字段),如下:状态位P用于指示该页是否已调入内存访问字段A用于记录本页在一段时间内被访问的次数,或记录本页在最近多长时间未被访问修改位M表示该页在调入内存后是否被修改过外存地址该页在外存上的地址,通常是物理块号,2020/5/25,99,3.地址变换机构,图4-24请求分页中的地址变换过程,2020/5/25,100,4.7请求分页存储管理方式,4.7.1请求分页中的硬件支持4.7.2内存分配策略和分配算法4.7.3调页策略,2020/5/25,101,4.7.2内存分配策略和分配算法,1.最小物理块数的确定是指能保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时,进程将无法运行进程应获得的最少物理块数与计算机的硬件结构有关,取决于指令的格式、功能和寻址方式对于某些简单的机器,若是单地址指令且采用直接寻址方式,则所需的最少物理块数为2。其中,一块是用于存放指令的页面,另一块则是用于存放数据的页面如果该机器允许间接寻址时,则至少要求有三个物理块对于某些功能较强的机器,其指令长度可能是两个或多于两个字节,因而其指令本身有可能跨两个页面,且源地址和目标地址所涉及的区域也都可能跨两个页面,可能至少需要6个物理块,2020/5/25,102,2.物理块的分配策略在请求分页系统中,可采取两种内存分配策略,即固定和可变分配策略。在进行置换时,也可采取两种策略,即全局置换和局部置换。于是可组合出以下三种适用的策略固定分配局部置换为每个进程分配固定页数的内存空间,在整个运行期间不再改变。分配页数少,会频繁缺页中断;分配页数多,浪费资源,内存中运行作业少。可变分配局部置换为每个进程分配一定量的内存空间。若运行中频繁缺页中断,则再增加若干物理块,直至缺页率减少到适当值为止。反之,若缺页率很低,则减少物理块可变分配全局置换先为每个进程分配一定量物理块,OS有一个空闲物理块队列,某进程缺页时从空闲队列取块装页,当空闲队列为空后,OS再调出某一进程的页,置换,2020/5/25,103,3.物理块分配算法(1)平均分配算法这是将系统中所有可供分配的物理块,平均分配给各个进程例如,当系统中有100个物理块,有5个进程在运行时,每个进程可分得20个物理块。这种方式貌似公平,但实际上是不公平的,因为它未考虑到各进程本身的大小。如有一个进程其大小为200页,只分配给它20个块,这样,它必然会有很高的缺页率;而另一个进程只有10页,却有10个物理块闲置未用,2020/5/25,104,(2)按比例分配算法这是根据进程的大小按比例分配物理块的算法。如果系统中共有n个进程,每个进程的页面数为Si,则系统中各进程页面数的总和为:又假定系统中可用的物理块总数为m,则每个进程所能分到的物理块数为bi,将有:b应该取整,它必须大于最小物理块数。,2020/5/25,105,(3)考虑优先权的分配算法在实际应用中,为了照顾到重要的、紧迫的作业能尽快地完成,应为它分配较多的内存空间通常采取的方法是把内存中可供分配的所有物理块分成两部分:一部分按比例分配给各进程;另一部分则根据各进程的优先权,适当地增加其相应份额后,分配给各进程在有的系统中,如重要的实时控制系统,则可能是完全按优先权来为各进程分配其物理块的,2020/5/25,106,4.7请求分页存储管理方式,4.7.1请求分页中的硬件支持4.7.2内存分配策略和分配算法4.7.3调页策略,2020/5/25,107,4.7.3调页策略,1.何时调入页面(1)预调页策略采用一种以预测为基础的预调页策略,将那些预计在不久之后便会被访问的页面预先调入内存,在连续分配时,一次调入若干相邻的页。这样方法从表面上看起来很好,但系统无法预计系统中作业的运行情况,难以实现,成功率50%。(2)请求调页策略当进程在运行中需要访问某部分程序和数据时,若发现其所在的页面不在内存,便提出请求,由OS将其所需页面调入内存目前的虚拟存储中大多采用此种策略,2020/5/25,108,2.从何处调入页面在请求分页系统中的外存分为两部分:用于存放文件的文件区和用于存放对换页面的对换区。对换区的磁盘I/O速度比文件区的高每当发生缺页请求时,系统应从何处将缺页调入内存,可分成如下三种情况(1)系统拥有足够的对换区空间,这时可以全部从对换区调入所需页面,以提高调页速度。在进程运行前,文件由文件区-对换区。(2)系统缺少足够的对换区空间,这时凡是不会被修改的文件,都直接从文件区调入。凡是会被修改的文件,都直接从对换区调入。(3)UNIX方式。开始时,由于与进程有关的文件都放在文件区,故凡是未运行过的页面,都应从文件区调入。换出到对换区,以后再调入就从对换区调入。,2020/5/25,109,3.页面调入过程每当程序所要访问的页面未在内存时,便向CPU发出一缺页中断,中断处理程序首先保留CPU环境,分析中断原因后,转入缺页中断处理程序。该程序通过查找页表,得到该页在外存的物理块后,如果此时内存能容纳新页,则启动磁盘I/O将所缺之页调入内存,然后修改页表。如果内存已满,则须先按照某种置换算法从内存中选出一页准备换出。如果该页未被修改过,可不必将该页写回磁盘;但如果此页已被修改,则必须将它写回磁盘,然后再把所缺的页调入内存,并修改页表中的相应表项,置其存在位为“1”,并将此页表项写入快表中。在缺页调入内存后,利用修改后的页表,去形成所要访问数据的物理地址,再去访问内存数据。整个页面的调入过程对用户是透明的。,2020/5/25,110,内容概述,4.1存储器的层次结构4.2程序的装入和链接4.3连续分配方式4.4基本分页存储管理方式4.5基本分段存储管理方式4.6虚拟存储器的基本概念4.7请求分页存储管理方式4.8页面置换算法4.9请求分段存储管理方式,2020/5/25,111,抖动:在虚拟存储中,页面在内存与外存之间被频繁地调入调出,以至于调度页面所需的时间比进程实际运行的时间还多,此时系统效率急剧下降,甚至导致系统崩溃。这种现象称为抖动。抖动产生的最根本原因是置换算法在当时的环境下不合理,分配给进程的物理页面数量太少。,2020/5/25,112,4.8页面置换算法,4.8.1最佳置换算法和先进先出置换算法4.8.2最近最久未使用(LRU)置换算法4.8.3CLOCK置换算法4.8.4其它置换算法,2020/5/25,113,4.8.1最佳置换算法和先进先出置换算法,1.最佳(Optimal)置换算法最佳置换算法是由Belady于1966年提出的一种理论上的算法其所选择的被淘汰页面,将是以后永不使用的,或许是在(未来)最长时间内不再被访问的页面采用最佳置换算法,通常可保证获得最低的缺页率,2020/5/25,114,图4-25利用最佳页面置换算法时的置换图,假定系统为某进程分配了三个物理块,并考虑有以下的页面号引用串:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1进程运行时,先将7,0,1三个页面装入内存。以后,当进程要访问页面2时,将会产生缺页中断。此时OS根据最佳置换算法,将选择页面7予以淘汰,0,0,1,0,1,0,3,2,7,7,7,2,4,3,2,0,3,2,0,1,2,0,1,7,缺页次数:9次(算前3个),缺页率:9/20=45%,2020/5/25,115,2.先进先出(FIFO)页面置换算法,先进入内存的页,先退出内存。实质上是淘汰在内存驻留时间最长的页。其理由是:最早调入内存的页,不再被使用的可能性比近期调入内存的大。实现:内存中页面按先后次序链接成一个队列,并设置一个指针,称为替换指针,使它总是指向最老的页面。特点:这种算法简单,实现容易;貌似公平,实际上不公平,不切实际,有些页面经常被访问,可能先被淘汰。,2020/5/25,116,图4-26利用FIFO置换算法时的置换图,0,0,1,0,1,3,1,2,7,7,7,2,3,0,2,3,0,4,2,0,4,2,3,4,2,3,0,1,3,0,1,2,0,1,2,7,0,2,7,0,1,7,缺页次数:15次(算前3个),缺页率:15/20=75%,2020/5/25,117,4.8页面置换算法,4.8.1最佳置换算法和先进先出置换算法4.8.2最近最久未使用(LRU)置换算法4.8.3CLOCK置换算法4.8.4其它置换算法,2020/5/25,118,4.8.2最近最久未使用(LRU)置换算法,这种算法的基本思想是,如果某一页被访问了,那么它很可能马上又被访问;反之,如果某一页很长时间没有被访问,那么最近也不太可能会被访问。这种算法考虑了程序设计的局部性原理。实质:当需要置换一页时,选择在最近一段时间最久未使用的页面予以淘汰。这种算法需要对每一页的使用情况跟踪记录,系统开销较大。,1.LRU(LeastRecentlyUsed)置换算法的描述,2020/5/25,119,图4-27LRU页面置换算法,0,0,1,0,1,0,3,2,7,7,7,2,0,3,4,0,2,4,3,2,4,3,2,0,3,2,1,0,2,1,0,7,1,缺页次数:12次(算前3个),缺页率:12/20=60%,2020/5/25,120,2.LRU置换算法的硬件支持(1)寄存器为了记录某进程在内存中各页的使用情况,须为每个在内存中的页面配置一个移位寄存器,可表示为R=Rn-1Rn-2Rn-3R2R1R0,2020/5/25,121,t0,t1,t2,访问1,t3,2020/5/25,122,图4-28某进程具有8个页面时的LRU访问情况,当进程访问某页时,将相应寄存器的Rn-1位置成1,每隔一定时间把寄存器右移一位。,2020/5/25,123,图4-29用栈保存当前使用页面时栈的变化情况,(2)栈最近访问的页在栈顶,最早访问的页在栈底,4,4,7,4,7,0,4,0,7,4,0,7,1,4,7,1,0,4,7,0,1,4,7,0,1,2,4,7,0,2,1,4,7,0,1,2,7,0,1,2,6,2020/5/25,124,4.8页面置换算法,4.8.1最佳置换算法和先进先出置换算法4.8.2最近最久未使用(LRU)置换算法4.8.3CLOCK置换算法4.8.4其它置换算法,2020/5/25,125,4.8.3Clock置换算法,1.简单的Clock置换算法引入:LRU算法有较多的硬件支持,成本高当采用简单的Clock算法时,只需为每页设置一位访问位,再将内存中的所有页面都通过链接指针链接成一个循环队列当某页被访问时,其访问位被置1置换算法在选择一页淘汰时,只需检查页的访问位由于该算法是循环地检查各页面的访问情况,故称为Clock算法,又称为最近未用算法NRU(NotRecentlyUsed),2020/5/25,126,图4-30简单Clock置换算法的流程和示例,2020/5/25,127,2.改进型Clock置换算法由访问位A和修改位M可以组合成下面四种类型的页面1类(A=0,M=0):表示该页最近既未被访问,又未被修改,是最佳淘汰页2类(A=0,M=1):表示该页最近未被访问,但已被修改,并不是很好的淘汰页3类(A=1,M=0):最近已被访问,但未被修改,该页有可能再被访问4类(A=1,M=1):最近已被访问且被修改,该页可能再被访问,2020/5/25,128,其执行过程可分成以下三步(1)从指针所指示的当前位置开始,扫描循环队列,寻找A=0且M=0的第一类页面,将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A(2)如果第一步失败,即查找一周后未遇到第一类页面,则开始第二轮扫描,寻找A=0且M=1的第二类页面,将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间,将所有扫描过的页面的访问位都置0(3)如果第二步也失败,亦即未找到第二类页面,则将指针返回到开始的位置,并将所有的访问位复0。然后重复第一步,如果仍失败,必要时再重复第二步,此时就一定能找到被淘汰的页,2020/5/25,129,改进型Clock置换算法-示例,2020/5/25,130,4.8页面置换算法,4.8.1最佳置换算法和先进先出置换算法4.8.2最近最久未使用(LRU)置换算法4.8.3CLOCK置换算法4.8.4其它置换算法,2020/5/25,131,1.最少使用(LFU:LeastFrequentlyUsed)置换算法为内存中的每个页面设置一个移位寄存器,用来记录该页面被访问的频率该算法选择在最近使用最少的页面作为淘汰页这种算法并