《存储管理.PPT》由会员分享，可在线阅读，更多相关《存储管理.PPT（91页珍藏版）》请在金锄头文库上搜索。
1、第3章 存储管理 1第第4 4章章 存储管理存储管理 本章的主要内容如下：n(1)存储管理的目的和四大基本功能。 n(2)实存管理中讲述了固定分区存储管理、可变式分区存储管理、纯分页存储管理三种存储管理方案的实现原理n(3)虚存管理以请求式分页存储管理为重点 n(4)总结各种存储管理方案中存在的碎片和抖动问题及解决方法23.1存储管理的功能n存储管理的主要功能：n内存的分配与回收 n地址重定位n存储保护 n虚拟存储器 存储管理的主要目的：存储管理的主要目的： 一是提高资源一是提高资源 的利用率的利用率 二是方便用户使用主存储器二是方便用户使用主存储器33.1.1内存的分配与回收n内存分配按分配
2、时机的不同，可分为两种方式。n（1）静态存储分配：指内存分配是在作业运行之前各目标模块连接后，把整个作业一次性全部装入内存，并在作业的整个运行过程中，不允许作业再申请其他内存，或在内存中移动位置。也就是说，内存分配是在作业运行前一次性完成的。n（2）动态存储分配：作业要求的基本内存空间是在目标模块装入内存时分配的，但在作业运行过程中，允许作业申请附加的内存空间，或是在内存中移动，即分配工作可以在作业运行前及运行过程中逐步完成。43.1.2地址重定位n1.程序的名空间n2.内存空间（或物理空间）n3逻辑空间n4地址重定位51.程序的字符名空间程序的字符名空间main() int a,b,c;.a
3、=6;b=b+a;.62逻辑空间逻辑空间n源程序经过汇编或编译后，形成目标程序，每个目标程序都是以0为基址顺序进行编址的，原来用符号名访问的单元用具体的数据单元号取代。这样生成的目标程序占据一定的地址空间，称为作业的逻辑地址空间，简称逻辑空间。在逻辑空间中每条指令的地址和指令中要访问的操作数地址统称为逻辑地址。7n物理地址：n 把内存分成若干个大小相等的存储单元，每个单元给一个编号，这个编号称为内存地址（物理地址、绝对地址、实地址），存储单元占8位，称作字节（byte）。n物理地址空间：n 物理地址的集合称为物理地址空间（主存地址空间），它是一个一维的线性空间。3内存空间（或物理空间）内存空间
4、（或物理空间）8作业的名空间、逻辑地址空间和装入后的物理空间作业的名空间、逻辑地址空间和装入后的物理空间9n将程序地址空间中使用的逻辑地址变换成主存中的地址的过程称为地址重定位,有时也称为地址映射。n1)静态地址重定位n2)动态地址重定位地址重定位地址重定位101)静态地址重定位静态地址重定位静态地址重定位是在程序执行之前由操作系统的重定静态地址重定位是在程序执行之前由操作系统的重定位装入程序完成的。位装入程序完成的。11(2)动态地址重定位n 动态重定位是在程序执行时由系统硬件完成从逻辑地址到物理地址的转换的。系统中设置了重定位寄存器。123.1.3存储保护n（1）上、下界存储保护：上、下界
5、保护是一种简单的存储保护技术。系统可为每个作业设置一对上、下界寄存器，分别用来存放当前运行作业在内存空间的上、下边界地址，用它们来限制用户程序的活动范围。 n（2）基址限长存储保护：上、下界保护的一个变种是采用基址限长存储保护。 13界限寄存器的两种存储保护方式界限寄存器的两种存储保护方式143.1.4虚拟存储器n虚拟存储技术的基本思想是把有限的内存空间与大容量的外存统一管理起来，构成一个远大于实际内存的、虚拟的存储器。此时，外存是作为内存的直接延伸，用户并不会感觉到内、外存的区别，即把两级存储器当作一级存储器来看待。一个作业运行时，其全部信息装入虚存，实际上可能只有当前运行的必需一部分信息存
6、入内存，其他则存于外存，当所访问的信息不在内存时，系统自动将其从外存调入内存。 153.2实存管理n3.2.1固定分区存储管理 n3.2.2可变式分区存储管理n3.2.3纯分页存储管理 163.2.1固定分区存储管理n固定分区存储管理是实现多道程序设计的最简单的一种存储管理技术。n其基本思想是，预先把可分配的主存储器空间分割成若干个连续区域，称为一个分区。每个分区的大小可以相同也可以不同，如图所示。但分区大小固定不变，每个分区装一个且只能装一个作业n因为在系统运行期间，分区大小、数目都不变，所以固定式分区也称为静态分区。17n对作业的组织分区分区4分区分区3分区分区2分区分区1操作系统操作系统
7、多个输入队列多个输入队列单个输入队列单个输入队列分区分区4分区分区3分区分区2分区分区1操作系统操作系统700K400K100K018固定式分区内存分配示意图（固定式分区内存分配示意图（a）和（）和（b）固定）固定式分区分配表式分区分配表193.2.2可变式分区存储管理n1空闲分区的组织形式 n2内存的分配与回收 n3常用的分配算法 n4可变式分区的地址重定位 内存的分配：内存不是预先划分好的，而是当内存的分配：内存不是预先划分好的，而是当作业装入时，根据作业的需求和内存空间的使作业装入时，根据作业的需求和内存空间的使用情况来决定是否分配。若有足够的空间，则用情况来决定是否分配。若有足够的空间
8、，则按需要分割与作业相对地址空间同样大小分区按需要分割与作业相对地址空间同样大小分区给该进程；否则令其等待主存空间给该进程；否则令其等待主存空间。20可变式分区内存使用情况示意图可变式分区内存使用情况示意图211空闲分区的组织形式n空闲分区链表的组织是这样的：在每个空闲分区的起始部分开辟出一个单元，存放一个链表指针和该分区的大小，链表指针指向下一个空闲分区。系统中用一个固定单元作为空闲分区链表的链表头指针，指向第一块空闲分区首地址，最后一块空闲分区的链表指针存放链尾标志。如图4.7（a）所示 。22空闲分区链表组织形式空闲分区链表组织形式232内存的分配与回收n当某一个用户作业完成释放所占分区
9、时，系统应进行回收。在可变式分区中，应该检查回收区与内存中前后空闲区是否相邻，若相邻，则应进行合并，形成一个较大的空闲区，并对相应的链表指针进行修改；若不相邻，应将空闲区插入到空闲区链表的适当位置。n243常用的分配算法n（1）首次适应算法 n（2）最佳适应算法 n（3）最差适应算法 25首次适应算法空闲分区链表组织形式首次适应算法空闲分区链表组织形式26最佳适应算法的空闲分区链表组织形式最佳适应算法的空闲分区链表组织形式27最差适应算法的空闲分区链表组织形式最差适应算法的空闲分区链表组织形式28内存使用情况内存使用情况 29用三种适应算法处理同一作业序列用三种适应算法处理同一作业序列304可
10、变式分区的地址重定位n可变式分区的地址重定位可采用静态重定位，也可采用动态重定位。如采用静态重定位，因用户作业进入内存后，程序的逻辑地址实现了重定位，不能在内存中再进行移动，经过一段时间的运行，内存中不能再分配利用的小碎片会越来越多。有时可能会出现这种情况，即当一个作业申请一定数量的内存时，虽然此时空闲区的总和大于新作业的内存要求，但却没有单个的空闲区足以装下该作业。n采用动态重定位的可变式分区管理技术，在执行内存分配时，如无足够大空闲块，应考虑实现紧凑操作。其分配算法如图所示。 31采用动态重定位的可变式分区分配算法采用动态重定位的可变式分区分配算法323.2.3纯分页存储管理n1纯分页存储
11、管理中存储块的分配与回收 n2纯分页存储管理的地址重定位问题n3联想存储器 n4存储保护 33纯分页存储管理示意图纯分页存储管理示意图34n分页的概念n 内存空间分成大小相等的若干块页面，同时把程序逻辑地址也分成与块大小相等的若干页面，当一个用户程序装入内存时，以页面为单位进行分配。页面的大小是为2n ,通常为1KB，2KB，nKB等。1纯分页存储管理中存储块的分配与回收35n通 常 有两 种 记录 空 闲存 储 块的方法：位 图 法和 链 表法。（a）存储块使用情况（b）存储块使用情况的位图表示存储块的位图管理法存储块的位图管理法362纯分页存储管理的地址重定位问题n纯分页存储管理中的地址重
12、定位是非常重要的，要使不连续的、分散的用户程序能正常运行，须采用动态地址重定位。此时，可采用重定位寄存器方式，如分页太多，则重定位寄存器用得太多。通常可在内存中为每个作业开辟一块特定区域，建立起作业的逻辑页与存储块之间的对应表格关系，这种表常称为页面映象表，简称页表。 3738纯分页存储管理地址重定位实现过程纯分页存储管理地址重定位实现过程39n一、页表n 页表是页式存储管理的数据结构，它包括用户程序空间的页面与内存块的对应关系、页面的存储保护和存取控制方面的信息。n 页号 内存块号 存取控制 状态 其它n 在实际的系统中，为了节省存储空间，在页表中可以省去页号这个表目。40n二、虚地址结构(
13、程序字)n 虚地址是用户程序中的逻辑地址，它包括页号和页内地址（页内位移）。n 区分页号和页内地址的依椐是页的大小，页内地址占虚地址的低位部分，页号占虚地址的高位部分。n 假定页面大小1024字节，虚地址共占用2个字节(16位)n 页号 页内地址（位移量）n P Wn 15 10 9 0413联想存储器n从上面介绍的地址变换过程可以看出：如果把页表全部放在内存，那么存取一个数据时，至少要访问二次内存。一次是访问页表，形成实际内存地址；另一次是根据形成的内存地址存取数据。显然，这比通常执行指令的速度要慢得多，使计算机的运行速度几乎降低一半。n应用联想存储器和页表相结合的方式，可有效地提高系统动态
14、地址转换的速度，是一种行之有效的方法。42采用快表和页表相结合的分页地址变换过程示意图采用快表和页表相结合的分页地址变换过程示意图434存储保护n四种保护方式：禁止做任何操作，只能执行，只能读，能读/写，当要访问某页时，先判断该页的存取控制和存储保护信息是否允许。n添加了存取控制信息的页表表目如下图所示： 44Windows NT两级页表地址变换示意图两级页表地址变换示意图45（2）面对大的页表，地址的映射怎样才能比较快地实现？n使用快表：即利用前面我们已介绍的高速缓冲存储器来存放经常使用的页表表目，以提高页表的查询速度。46段式存储管理 基本思想（工作原理） 作业的地址空间被划分为若干个段,
15、每个段定义了一组逻辑信息.系统为每个段分配一个连续的分区,进程中的各个段可以离散地放入内存中不同的分区中.47.0S工作区段工作区段B主程序段主程序段M.0EP子程序段子程序段X0K.CALL X E.CALL Y FCALL A 116.0FL子程序段子程序段Y0116N数组数组A12345.48操作系统操作系统.B0SA0NY0LX0PM0K逻辑段号逻辑段号01234作业作业1的地址空间的地址空间10003200500060008000PKSLN主存主存K 3200P 1500L 6000N 8000S 5000长度长度 段地址段地址01234操作系统操作系统49用户程序划分用户程序划分
16、按程序自身的逻辑关系划分为若干个程序段，每个程序段都有一个段名，且有一个段号。段号从0开始，每一段也从0开始编址，段内地址是连续的。50逻辑地址逻辑地址内存划分 内存空间被动态的划分为若干个长度不相同的区域，这些区域被称为物理段，每个物理段由起始地址和长度确定。段号段内地址51内存分配内存分配 以段为单位分配内存，每一个段在内存中占据连续空间（内存随机分割，需要多少分配多少），但各段之间可以不连续存放。52管理管理段表： 它记录了段号，段的首（地）址和长度之间的关系。 每一个程序设一个段表段号01253硬件支持硬件支持一对寄存器段表始址寄存器： 用于保存正在运行进程的段表的始址。段表长度寄存器
17、： 用于保存正在运行进程的段表的长度（例如上图的段表长度为3）。54ClCb+段号段号S S 段内地址段内地址d比较比较比较比较b + d比较比较段段表表S= Cl快表快表物理地址物理地址段表始址寄存器段表始址寄存器段表长度寄存器段表长度寄存器逻辑地址逻辑地址lb.Slb地址越界地址越界d=1d=1地址映射及存储保护机制地址越界地址越界地址越界地址越界比较比较55优点： 便于动态申请内存 管理和使用统一化 便于共享 便于动态链接缺点：产生碎片56段页式存储管理段页式存储管理产生背景及基本思想 背景：结合了二者优点 克服了二者的缺点57基本思想：基本思想： 用户程序划分：按段式划分（对用户来讲，
18、按段的逻辑关系进行划分；对系统讲，按页划分每一段） 逻辑地址：内存划分：按页式存储管理方案内存分配：以页为单位进行分配58管理管理1 段表：记录了每一段的页表始址和页表长度2 页表：记录了逻辑页号与内存块号的对应关系。（每一段有一个，一个程序可能有多个页表）4 分配：同页式管理593.3虚拟存储器管理n3.3.1虚拟存储器的概念 n3.3.2请求式分页存储管理与动态地址重定位 n3.3.3现代计算机系统改进的动态地址重定位 n3.3.4页面置换算法 n3.3.5请求式分页存储管理性能分析举例 n3.3.6请求式分段存储管理 60 早早在在19681968年年P PDenningDenning就
19、就指指出出过过，程程序序在在执执行行时时将将呈呈现现出出局局部部性性规规律律，即即在在一一段段时时间间内内，程程序序的的执执行行仅仅局局限限于于某某个个部部分分；相相应应地地，它它所所访访问问的的存存储储空空间间也也局局限限于于某某个个区区域域内内。那那么么程程序序为为什什么么会会出出现现局局部部性性规规律律呢呢？原原因因可可以以归归结为以下几点：结为以下几点：程程序序在在执执行行时时，除除了了少少部部分分的的转转移移和和过过程程调调用用指指令令外外，大多数仍是顺序执行的。大多数仍是顺序执行的。子子程程序序调调用用将将会会使使程程序序的的执执行行由由一一部部分分内内存存区区域域转转至至另另一一
20、部部分分区区域域。但但在在大大多多数数情情况况下下，过过程程调调用用的的深深度度都都不不超超过过5 5。程序中存在许多循环结构，循环体中的指令被多次执行。程序中存在许多循环结构，循环体中的指令被多次执行。程程序序中中还还包包括括许许多多对对数数据据结结构构的的处处理理，如如对对连连续续的的存存储储空间空间数组的访问，往往局限于很小的范围内。数组的访问，往往局限于很小的范围内。613.3.1虚拟存储器的概念n局部性原理(principle of locality)：指程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。在一段时间内一个程序的执行往往呈现出高度的
21、局部性，表现在时间与空间两方面:n时间局限性：如果程序中的某条指令一旦执行，则不久的将来该指令可能再次被执行；如果某个存储单元被访问，则不久以后该存储单元可能再次被访问。产生时间局限性的典型原因是在程序中存在着大量的循环操作。n 空间局限性：一旦程序访问了某个存储单元，则在不久的将来，其附近的存储单元也最有可能被访问。 即程序在一段时间内所访问的地址，可能集中在一定的范围内，其典型原因是程序是顺序执行的。62（1）程序中往往会有一些彼此互斥的部分。）程序中往往会有一些彼此互斥的部分。 （2）在一个完整的程序中，会有一些诸如出错处理这样的子程）在一个完整的程序中，会有一些诸如出错处理这样的子程序
22、，在作业正常运行情况下不会执行这些程序，没有必要把它序，在作业正常运行情况下不会执行这些程序，没有必要把它们调入内存。们调入内存。 基于程序局部性原理和上述情况，就没有必要把一个作业一基于程序局部性原理和上述情况，就没有必要把一个作业一次性全部装入内存再开始运行。而是可以把程序当前执行所涉次性全部装入内存再开始运行。而是可以把程序当前执行所涉及的信息放入内存中，其余部分可根据需要临时调入，由操作及的信息放入内存中，其余部分可根据需要临时调入，由操作系统和硬件相配合来完成主存和辅存之间信息的动态调度。系统和硬件相配合来完成主存和辅存之间信息的动态调度。虚拟存储器的定义虚拟存储器的定义 根据局部性
23、原理，一个作业在运行之前，没有必要把全部作根据局部性原理，一个作业在运行之前，没有必要把全部作业装入内存，而仅将那些当前要运行的那部分页面或段，先装业装入内存，而仅将那些当前要运行的那部分页面或段，先装入内存便可启动运行，其余部分暂时留在磁盘上。入内存便可启动运行，其余部分暂时留在磁盘上。633.3.2请求式分页存储管理与动态地址重定位n请求式分页存储管理与纯分页存储管理在内存块的分配与回收，存储保护某方面都十分相似，不同之处在于地址重定位问题。在请求式分页存储管理的地址重定位时，可能会出现所需页面不在主存的情况，此时，系统必须解决以下两个问题：n（1）当程序要访问的某页不在内存时，如何发现这
24、种缺页情况？发现后应如何处理？n（2）当需要把外存上的某个页面调入内存时，此时内存中没有空闲块应怎么办？64所示是请求式分页存储管理的存储映像所示是请求式分页存储管理的存储映像 65n为了帮助操作系统对要置换出内存的页面进行选择，在页表中还可以增加一个引用位，以反映该页最近的使用情况。n一般来说，一个页表的表目通常可包括如下的数据内容：66请求式分页存储管理中的地址重定位和缺页中断处请求式分页存储管理中的地址重定位和缺页中断处理过程如图所示。理过程如图所示。673.3.4页面置换算法n1最优算法（OPT算法）n2先进先出算法（FIFO算法）n3最久未使用页面置换算法（LRU算法）n4LRU近似
25、算法681最优算法（OptimalOptimal算法）n它是一种理想化的算法，性能最好，但在实际上难于实现。即即选选择择那那些些永永不不使使用用的的，或或者者是是在在最最长长时时间间内内不不再再被被访访问问的的页页面面置置换换出出去去。但是要确定哪一个页面是未来最长时间内不再被访问的，目前来说是很难估计的，所以该算法通常用来评价其它算法。n例：例：假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：7，0，l，2，0，3，0，4，2，3，0，3，2，l，2，0，l，7，0，1。如下图所示，进程运行时先将7，0，1三个页面装入内存。当进程访问页面2时，产生缺页中断，此时OS根据最佳置换
26、算法，页面7将在第18次才被访问，是三页中将最久不被访问的页面，所以被淘汰。接着访问页面0时，发现已在内存中，而不会产生缺页中断，以此类推。从图可以看出，采用最佳置换算法，只发生了6次页面置换。692先进先出算法（FIFO算法）n这种算法的基本思想是：总是先淘汰那些驻留在内存时间最长的页面，即先进入内存的页面先被置换掉。理由是：最先进入内存的页面不再被访问的可能性最大。 70先进先出算法存储分块表构造先进先出算法存储分块表构造713最久未使用页面置换算法（LRULeast Recently UsedLeast Recently Used算法）n这种算法的基本思想是，如果某一页被访问了，那么它很
27、可能马上又被访问；反之，如果某一页很长时间没有被访问，那么最近也不太可能会被访问。这种算法考虑了程序设计的局部性原理。其实质是，当需要置换一页时，选择在最近一段时间最久未使用的页面予以淘汰。n实现这种算法可通过周期性地对“引用位”进行检查，并利用它来记录一页面自上次被访问以来所经历的时间t，淘汰时选择t最大的页面。 724LRU近似算法n这种算法，只要在存储分块表（或页表）中设一个“引用位”，当存储分块表中的某一页被访问时，该位由硬件自动置1，并由页面管理软件周期性把所有引用位置0。这样，在一个时间周期T内，某些被访问过的页面其引用位为1，而未被访问过的页面其引用位为0。因此，可根据引用位的状
28、态来判别各页面最近的使用情况。当需要置换一页面时，选择其引用位为0的页，如图4.21所示的算法 。图4.22是这种近似算法的一个例子。 73LRU近似算法近似算法 74LRU近似算法举例近似算法举例753.3.5请求式分页存储管理性能分析举例n1程序设计的质量n2页面的大小n3分配的内存块数n4页面置换算法性能76n【例1】主存块数m=3，置换算法采用FIFO算法，缺页中断次数及缺页率如图4.23所示。n在图4.23中，P行表示页面走向，M行表示在主存中的页面号，其中带有+的表示新调入页面，在M行的各列按调入的顺序排列，带有圆圈的数字表示下一时刻将被淘汰页面，F行表示是否引起缺页中断，带号的表
29、示引起缺页中断。从图4.23可以看出，缺页中断页数为9次，缺页率f=9/12=75%。77FIFO算法性能分析（算法性能分析（m=3）78n【例2】设m=4，仍采用FIFO算法，缺页中断次数及缺页率如图4.24所示。可以算出，在分配给该作业的内存块数增加到4时，缺页中断由图4.23的9次反而增加到了10次，缺页率由75%增加到10/12=83%，这就是FIFO算法的一种异常现象。随着分配的主存块数的增加，缺页中断次数不但没有降低，反而增加了。这与该算法定全不考虑程序的动态特征有关。79FIFO算法性能分析（算法性能分析（m=4）80n【例3】设m=3，采用LRU算法，缺页中断次数及缺页率如图所
30、示。LRU算法性能分析（算法性能分析（m=3）81n【例4】设m=4，其余同例3，则缺页中断次数及缺页率如图所示。 LRU算法性能分析（算法性能分析（m=4）823.3.6请求式分段存储管理n为了能实现虚拟存储，段式逻辑地址空间中的程序段在运行时并不全部装入内存，而是如同请求式分页存储管理，首先调入一个或若干个程序段运行，在运行过程中调用到哪段时，就根据该段长度在内存分配一个连续的分区给它使用。若内存中没有足够大的空闲分区，则考虑进行段的紧凑或将某段或某些段淘汰出去。相应于请求式分页存储管理，这种存储管理技术称为请求式分段存储管理。83分段的逻辑地址空间分段的逻辑地址空间84请求式分段存储管理
31、的地址变换n1程序的逻辑地址结构 n2段表 n3请求式分段动态地址变换过程 n4请求式分段存储管理的优、缺点 851程序的逻辑地址结构n请求式分段存储管理的逻辑地址结构由段号s和段内位移量d组成，如下图所示。862段表n类似于请求式分页存储管理的页表，为了实现动态地址变换和存储保护，系统要为每一个作业建立一张段表。段表中的每一个表目对应着作业地址空间的一个程序段，其一般格式为： 873请求式分段动态地址变换过程请请求求式式分分段段动动态态地地址址 88请求式分段存储管理的地址变换n（1）可提供大容量的虚存 n（2）允许动态增加段的长度 n（3）便于段的动态链接 n（4）便于实现程序段的共享 n
32、（5）便于实现存储保护 893.4碎片与抖动问题n1、碎片问题 n解决碎片问题的比较好的方法是采用分页技术，在纯分页存储管理系统中，因存储区划分成固定大小的块，而用户作业也划分成与块相等的若干页，每个作业调入内存时，除最后一个页面可能有页内碎片出现外，其余页不存在碎片问题，一般来说，平均每个作业可能有半页的内碎片。90n2、抖动现象 n避免抖动现象最根本的方法是控制多道程序的道数，使得每个用户作业都有足够的内存空间可供使用。但作业的个数又不能太少，否则，会影响处理机的利用率。最好是使处理机利用率较高，又不致于使系统发生抖动，这是一个很难解决的问题，牵扯到程序的局部性问题，并需借助于工作集模型。91
