第四章 - 存储管理

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,4,章 存储管理,本章内容提要,地址空间与重定位,分区管理技术,分页技术,分段技术,虚拟存储概念,请求分页技术,内存块分配和抖动问题,段式虚拟存储器,Linux,中的存储管理技术,4.1,地址空间与重定位,内存,（,Main Memory,或,Primary Memory,或,Real Memory,）也称主存，是指,CPU,能直接存取指令和数据的存储器。,内存在计算机系统中的地位,4.1.1,用户程序的地址空间,1,存储器的层次,2,用户程序的地址空间,主要处理阶段,编辑 编译 连接 装入 运行,有关概念,装入程序,其功能是将程序模块放入内存，并进行重定位。它通常与连接程序一起使用。,相对地址或逻辑地址,绝对地址或物理地址,程序装入内存的方式, 绝对装入方式, 可重定位装入方式, 动态运行时装入方式,4.1.2,重定位概念,逻辑地址空间,（简称,地址空间）,由程序中逻辑地址组成的地址范围,内存空间,（也称,物理空间,或,绝对空间）,由内存中一系列存储单元所限定的地址范围,重定位,程序和数据装入内存时，需对目标程序中的地址进行修改。这种把逻辑地址转变为内存物理地址的过程称作重定位,重定位方式,静态重定位,动态重定位,1,静态重定位,目标程序装入内存时进行地址变换,程序装入内存时的情况,静态重定位示意图,优点,:,无需增加硬件地址转换机构,主要缺点,:,位置“钉死”；不便共享,2,动态重定位,程序执行期间进行重定位,动态重定位示意图,主要优点：,位置可变，不必连续,；易于共享,主要缺点,：需要附加硬件支持 ；软件算法比较复杂,4.1.3,对换技术,对换两个进程示意图,早期的对换技术用于单用户系统,主要优点,：,利用外存来解决内存不足的问题,主要缺点 ：效率很低 ；不能保证充分利用内存,在多道程序环境中也采用对换技术,4.2,分区管理技术,4.2.1,分区法,分区分配是为支持多道程序运行而设计的一种最简单的存储管理方式。,1,固定分区法,分区,个数,固定不变，各个分区的,大小,固定不变，不同分区的大小可以不同,系统建立一张分区说明表。每个分区对应表中的一项。各表项包含每个分区的起始地址、分区大小以及状态（是否正被使用）。,分区的申请和释放,固定分区法,固定分区管理示意图,分区说明表,优点：,管理方式简单，所需操作系统软件和处理开销都小,缺点,：内存空间利用率不高，碎片严重；,活动进程数目受限；,无法预知所需内存大小,2,动态分区法, 分区的分配,各个分区是在相应进程要进入,内存时才建立的，使其大小恰,好适应进程的大小,MVT,的内存分配和进程调度情况,操作系统内部设置一个 内存登记表,动态分区法,数据结构,常用的数据结构形式有以下两种 ：,空闲分区表,空闲分区链,使用链指针把所有的空闲分区链接成一条链,分配算法,最先适应算法（,First-fit,）,空闲表是按,地址,排列的（即空闲块地址小的，在表中的序号也小）。,最佳适应算法（,Best-fit,）,空闲表是以空闲分区的,大小,为序、按增量形式排列的，即小块在前，大块在后。,循环适应算法（,Next-fit,）,最先适应算法的变种。它不从空闲表的开头查找，而从上次找到的可用分区的下一个空闲分区开始查找，从中选择满足大小要求的第一个空闲分区。,最坏适应算法（,Worst-fit,）,空闲表是以空闲块的大小为序，且大块在前、小块在后。, 硬件支持,通常用,一对寄存器,分别表示用户进程在内存空间的上界地址值和下界地址值。,这对寄存器是所有用户进程,共用,的, 碎片,“碎片”或“零头”：,内存中这种容量太小、无法利用的小分区,内部碎片：,在一个分区内部出现的碎片（即被浪费的空间），如固定分区法会产生内部碎片。,外部碎片：,在所有分区之外新增的碎片, 分区分配的优缺点,主要优点：,有利于多道程序设计，所需硬件支持很少，管理算法简单，易于实现。,主要缺点：,碎片问题严重，内存利用率低，不利于大作业运行，作业大小受内存总量限制。,4.2.2,可重定位分区分配,紧缩（或拼凑）,移动某些已分配区的内容，使所有进程的分区紧挨在一起，而把空闲区留在另一端。,可重定位分区法,动态重定位经常是用,硬件实现的。硬件支,持包括一对寄存器,紧缩时机,释放所占分区时,分配进程分区时,可重定位分区的紧缩示意图,动态重定位的实现过程,动态重定位经常用硬件实现,硬件支持,基址寄存器,限长寄存器,动态重定位的实现过程,可重定位分区法的优缺点,优点：,可以消除碎片，能够分配更多的分区，有助于多道程序设计，提高内存的利用率。,缺点：,紧缩花费了大量,CPU,时间,当进程大于整个空闲区时，仍要浪费一定的内存,进程的存储区内可能放有从未使用的信息,进程之间无法对信息共享,4.3,分页技术,4.3.1,分页的基本概念,分页存储管理的基本方法,逻辑空间分页,若干大小相等的页面,内存空间分块,又称,内存块,或,页框，,由,硬件,（系统）确定,逻辑地址表示,分页技术的地址结构示意图,给定的逻辑地址是,A,，页面的大小为,L,，则页号,p,和页内地址,d,可按下式求得,p,= INT(,A,/,L,) ,d,=,A,MOD,L,式中，,INT,是向下整除的函数，,MOD,是取余函数。,分页存储管理的基本概念,内存分配原则,以块为单位,每个页面对应一个内存块,内存块可不连续,分页存储管理系统示意图,设立页表,系统为每个进程设立一张页面映像表，简称,页表,实现从页号到物理块号的地址映射,建立,内存块表,整个系统有一个内存块表。每个内存块在内存块表中占一项，表明该块当前空闲还是已分出去了。,4.3.2,分页系统中的地址映射,分页系统的地址转换机构,每个进程平均有半个页面的内部碎片,4.3.3,页的共享和保护,页面共享,共享的方法是使这些相关进程的逻辑空间中的页指向相同的内存块（该块中放有共享程序或数据）,在分页系统中实现页的共享比较困难,2.,页面保护,（,1,）利用页表本身进行保护,（,2,）设置存取控制位,（,3,）设置合法标志,4.3.4,页表的构造,1,多级页表,大多数现代计算机系统都支持非常大的逻辑地址空间，如,2,32,2,64,。在这种情况下，只用一级页表会使页表变得非常大。,一种方法是利用两级页表，即把页表本身也分页。,两级页表地址结构示意图,两级页表结构示意图,多级页表,两级页表结构的地址转换,多级页表,散列页表构成及地址转换过程,2,散列页表（,Hashed Page Table,）,以页号作为参数形成散列值。散列表中每一项有一个链表，它把有相同散列值的元素链接起来。每个链表元素由三部分组成：, 页号, 对应的内存块号, 指向链表中下一个元素的指针,3,倒置页表,它是按内存块号排序的，每个内存块占有一个表项。每个表项包括存放在该内存块中页面的虚拟页号和拥有该页面的进程标识符。,倒置页表构成及地址转换过程,4.4,分段技术,4.4.1,分段的基本概念,分段地址空间,1,分段,段是一组逻辑信息的集合。,每段都有自己的名字、长度。,段号,2,程序的地址结构,逻辑地址要用两个成分来表示：,段号,s,和段内地址,d,进程的逻辑地址空间是,二维,的,分段技术地址结构示意图,3,段表和段表地址寄存器,系统为每个进程建立一个段映射表，简称“,段表,”。每个段在段表中占有一项，段表项中包含段号、段长和段起始地址（又称“基址”）等。,系统还要建立一个,段表地址寄存器,。它有两部分,：,该段表在内存的起始地址,该段表的长度。,4,分页和分段的主要区别,页是信息的物理单位,段是信息的逻辑单位,页的大小是由系统确定的,段的长度因段而异,分页的进程地址空间是一维的,分段的进程地址空间是二维的,分页系统很难实现过程和数据的分离,分段系统却可以很容易实现这些功能,4.4.2,分段系统中的地址映射,分段地址转换过程,4.4.3,段的共享和保护,1,段的共享,共享是在段一级实现的，任何共享信息可以单独成为一段。,也可以只共享部分程序。,分段系统中段的共享,2,段的保护,段的,保护措施,包括以下三种：,存取控制,段表本身可起保护作用,表项中设置该段的长度限制,段长,段表地址寄存器中有段表长度的信息,保护环,4.5,虚拟存储管理,4.5.1,虚拟存储器的概念,进程在执行之前要全部装入内存，这种限制是不合理的。,程序中往往含有不会被执行的代码,分配的内存空间会大于它们的实际需要,一个程序的某些选项和特性可能很少使用,程序的执行过程也显示出,局部性,按需分别调入内存会带来两点好处：,用户编制程序时不必考虑内存容量的限制,在一定容量的内存中就可同时装入更多的进程,虚拟存储器（,Virtual Memory,）,用户能作为可编址内存对待的虚拟存储空间，它使用户逻辑存储器 与物理存储器分离，是操作系统给用户提供的一个比真实内存空间大得多的地址空间。,实现虚拟存储技术的,物质基础,二级存储器结构,动态地址转换机构（,DAT,）,虚拟存储器实质上是把用户地址空间和实际的存储空间区分开来。,它主要受到两方面的限制：,指令中表示地址的字长,外存的容量,虚拟存储器的概念,4.5.2,虚拟存储器的特征,虚拟扩充,部分装入,离散分配,多次对换,4.6,请求分页技术,4.6.1,请求分页的基本思想,是在单纯分页技术基础上发展起来的,二者的根本区别在于请求分页提供虚拟存储器。,其基本思想是：,当一个进程的部分页面在内存时就可调度它运行；在运行过程中若用到的页面尚未在内存，则把它们动态换入内存。,如果地址转换机构遇到一个具有,N,状态的页表项时，便产生一个缺页中断,4.6.2,硬件支持及缺页处理,1,页表机制,页表项不仅要包含该页在内存的基址，还要含有下列信息：,页表的每一项增加一个,状态位,，用来指示该页面是否在内存中。,页表项中还要记载该页面在外存的地址（又称文件地址）,在页表中还要增加一些位，用于记录该页的使用情况,页表项,通常包含下列信息,：,典型的页表表项示意图,2,缺页中断机构,指令执行步骤与,缺页中断处理过程,3,页面置换过程,页面置换流程示例,主要包括以下,4,个步骤：, 找出所需页面在磁盘上的位置 。, 找出一个空闲内存块 。, 把所需页面读入内存块（刚刚得到的空闲块），修改页表和存储块表。, 重新启动该用户进程。,实现请求分页必须解决内存块的分配算法和页面置换算法两个主要问题。,4,具有快表的地址转换机构,在内存中放置页表也带来存取速度下降的矛盾。,快表,（或,Translation,Lookaside,Buffer, TLB,）：,专用的、高速小容量的联想存储器,快表每项包括键号和值两部分,程序局部化,：一个程序在一段时间内总是相对集中在一个有限地址空间的某个区域中执行。,利用快表实现地址转换,4.6.3,页面置换算法,1,有效存取时间和页面走向, 有效存取时间,缺页率,p,：,表示缺页中断的概率（,0,p,1,）,等于缺页次数与全部访问内存次数之比,有效存取时间可表示为：,有效存取时间,= (1-,p,)ma +,p,缺页处理时间,缺页中断处理所花费的时间主要有以下三部分：, 处理缺页中断的时间。, 调入该页的时间。, 重新启动该进程的时间。,将页面从盘上读到内存所花费的时间包括：,磁盘,寻道时间,（即磁头从当前磁道移至指定磁道所用的时间）,旋转延迟时间,（即磁头从当前位置落到指定扇区开头所用的时间）,数据传输时间,典型磁盘的旋转延迟时间约为,8 ms,，寻道时间约为,15 ms,，传输时间是,1 ms,。, 页面走向,抖动,频繁地更换页面,以致系统的大部分时间花费在页面的调度和传输上,。,尽量避免系统“抖动”,存储访问序列也叫,页面走向,对于给定的页面大小，仅考虑其页号，不关心完整的地址。,如果当前对页面,p,进行了访问，那么，马上又对该页访问就不会缺页。这样连续出现的同一页号就简化为一个页号。,如下地址序列（用十进制数表示）：,0100,，,0432,，,0101,，,0612,，,0102,，,0103,，,0104,，,0101,，,0611,，,0102,，,0103,，,0104,，,0101,，,0610,，,0102,，,0103,，,0104,，,0101,，,0609,，,0102,，,0105,若每页,100,个字节，则页面走向简化为：,1,，,4,，,1,，,6,，,1,，,6,，,1,，,6,，,1,，,6,，,1,一般来说，随着可用块数的增加，缺页数将减少。,缺页量与内存块数关系图,统一采用下述页面走向,：,7,，,0,，,1,，,2,，,0,，,3,，,0,，,4,，,2,，,3,，,0,，,3,，,2,，,1,，,2,，,0,，,1,，,7,，,0,，,1,并且假定每个作业只有三个内存块可供使用。,页面走向,2,常用的页面置换算法, 先进先出法,总是淘汰在内存中停留时间最长（年龄最老）的一页，即先进入内存的页，先被换出。,FIFO,页面置换序列,总共有,15,次缺页,优点：容易理解，方便程序设计。,缺点：,性能并不很好，效率不高；,存在,Belady,异常现象，即缺页率随内存块增加而增加。, 最佳置换法,最佳置换算法（,Optimal Replacement, OPT,）其实质是：为调入新页面而必须预先淘汰某个老页面时，所选择的老页面应在将来不被使用，或者是在最远的将来才被访问。,保证有最小缺页率,OPT,算法在实现上有困难,最佳页面置换序列,仅出现,9,次缺页中断, 最近最少使用置换法,以“,最近的过去,”作为“不久将来”的近似,把最近最长一段时间里不曾使用的页面淘汰掉,实质是：当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以淘汰。,最近最少使用算法页面置换序列,产生,12,次缺页,LRU,算法需要实际硬件的支持。实现时的问题是：怎样确定最后访问以来所经历时间的顺,序。有以下两种可行的办法：,计数器,栈,利用栈记录目前访问最多的页面示例, 最近未使用置换法,最近未使用（,Not Recently Used,，,NRU,）算法是,LRU,算法的近似方法,是,不是,将淘汰指针指向,下一个存储块,淘汰此页,引用位,是,1,吗？,淘汰此页,返回,NUR,算法流程示例,4.7,内存块分配和抖动问题,4.7.1,内存块分配,1,最少内存块数,分给每个进程的,最少内存块数,是指保证进程正常运行所需的最少内存块数，它是由指令集结构决定的。,2,内存块的分配,固定分配策略,分配给进程的内存块数是固定的，且在最初装入时（即进程创建时）确定块数。,可变分配策略,允许分给进程的内存块数随进程的活动而改变。,3.,页面置换范围,全局置换,允许一个进程从全体存储块的集合中选取淘汰块，尽管该块当前分配给其他进程，还是能强行占用。,局部置换,是每个进程只能从分给它的一组内存块中选择淘汰块。,局部置换可与固定分配策略相结合,局部置换可与可变分配策略相结合,全局置换只能与可变分配策略相结合,内存块的分配,4,分配算法,（,1,）等分法,内存块按进程平分,（,2,）比例法,设进程,p,i,的地址空间大小为,s,i,，则总地址空间为,S,=,s,i,若可用块的总数是,m,，则分给进程,p,i,的块数是,a,i,m,.,s,i,/,S,（,3,）优先权法,给高优先级进程分配较多内存,4.7.2,抖动问题,整个系统的页面替换非常频繁，以致大部分机器时间都用在来回进行的页面调度上，只有一小部分时间用于进程的实际运算。这种局面称为,系统“抖动,（,Thrashing,）”。,1,产生抖动的原因,内存 不足,多道程序度高,CPU,的利用率太低,CPU,利用率与多道程序度之间的关系,2,防止抖动的方法,采用局部置换策略,利用工作集策略防止抖动,挂起某些进程,采用缺页频度法（,Page Fault Frequency, PFF,）,缺页频度的上限和下限,4.7.3,工作集,测试表明，虚拟存储系统的有效操作依赖于程序中访问的局部化程度。,1.,局部性模型,时间局部化,是指一旦某条指令或数据被访问过，它往往很快又被再次访问。,空间局部化,是指一旦某个位置被访问过，它附近的位置也可能很快要用到。,2.,工作集模型,工作集，就是一个进程在某一小段时间,内访问页面的集合。,工作集模型,工作集依赖于程序的行为，并且其大小与,的取值有关。,每个进程的工作集大小为,WSS,i,，那么,工作集,D,就是系统中全部（,n,个）进程对内存块的总请求量。,如果请求值,D,大于可用内存块的总量,m,(,D,m,),，将出现抖动。,4.8,段式虚拟存储器,4.8.1,基本工作过程,一个进程的所有分段的副本都保存在外存上。当它运行时，先把当前需要的一段或几段装入内存，其他段仅在调用时才装入。,当所访问的段不在内存时，便产生缺段中断,各段表项中要增加一位，以表明该段的存在状态。,还要增加另外一些控制位,如：,修改位,保护位,共享位,4.8.2,动态链接和链接中断处理,1,动态链接,仅当用到某个分段时才对它进行链接，从而避免不必要的链接。,间接编址,间接字,链接故障指示位,直接编址与间接编址示意图,2,链接中断处理,段的动态链接示意图,程序,MAIN,中有一条指令,LOAD* 1,，,3|100,4.9,段页式结合系统,段页式存储管理的基本原理,段页式系统的地址转换过程,段页式系统的地址转换机构,4.10 Linux,系统的存储管理技术,Linux,系统采用了,请求分页,存储管理技术和,对换技,4.10.1,对换,1,对换空间的分配,对换设备,是块设备，如经过构造的硬盘,对换文件就是普通文件，但它们所占的磁盘空间必须是,连续,的,通常，将对换分区类型设置为,Linux Swap,核心要为每个换出内存的进程建立对换文件,2,进程对换,对换守护进程,kswapd,的任务就是保证系统中有足够的空闲内存页。,对换,直接,在对换设备和用户的内存空间之间进行，不通过缓冲机制。,对换工作仅需局部进行。只需把,该进程占用的全部内存空间,复制到所分配的对换空间中，而不管未分配内存的那一部分虚拟空间。,4.10.2,请求分页技术,1,Linux,的多级页表结构,进程的虚拟存储空间,Linux,进程的虚拟存储空间,Linux,系统采用三级页表的方式,对于,i386,来说，,CPU,只支持两级模型。,Linux,的多级页表结构,地址映射步骤,2,内存页的分配与释放,分配内存页组,释放一个页面组,Linux,系统采用位图和链表两种方法来管理内存页,位图可以记录内存单元的使用情况,链表可以记录已分配的内存单元和空闲的内存单元,空闲内存的组织示意图,Bye!,下一章,(NEXT),：,第,5,章,-,文 件 系 统,=,