第4章 存储管理

存储管理是操作系统的重要组成部分，它负责管理计算机系统的重要资源主存储器。由于任何程序、数据必须占用主存空间后才能执行，因此存储管理直接影响系统的性能。

第四章

存储管理基本概念连续分配方式分页存储管理方式分段存储管理方式4123段页式存储管理方式54.1基本概念一、重定位1、逻辑地址为了使用户不过问存储分配，通常采用相对于某个基准量(通常用0)的相对地址编程。相对地址常用于程序编写和编译过程中。2、逻辑空间：一个程序的相对地址的集合组成了该程序的逻辑空间。3、物理地址：为区分存储器中不同的存储单元，需对其进行统一编号,这些编号称为物理地址。物理地址是主存的真实地址–––绝对地址4、物理地址空间：指主存中物理单元的集合，是程序真正运行的空间，其大小取决于主存的实际容量。LoadAdata1data13456源程序LoadA20034560100200逻辑地址空间LoadA12003456

。。1200物理地址空间BA=1000编译连接地址映射图逻辑地址空间与物理地址空间5、重定位把逻辑地址空间中使用的逻辑地址变换成内存空间中的物理地址的过程。按地址变换时间和所采用技术的不同可分为：静态重定位动态重定位静态重定位

当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换（一般在装入内存时由软件完成），直到该程序完成退出内存为止。

例：在用户程序的1000号单元处有一条指令LOAD1，2500，该指令的功能是将2500单元中的整数365取至寄存器1中。

图4-3作业装入内存中的情况在装入时对目标程序中的指令和数据地址的修改过程称为重定位。又因为地址交换只是在装入时一次完成，以后不再改变，故称为静态重定位。1,12500动态重定位

程序执行时真正要访问的地址图4-10动态重定位示意图二、存储管理的目的和功能1、在多个用户间分配主存－主存分配(1)分配策略(计算)放置策略–––

决定放的位置调入策略–––

装入时机(什么时刻调入)淘汰策略(2)数据结构：队、表2、地址映射：映射逻辑地址为存储地址3、扩充逻辑存区－主存扩充(这里指的扩充并非指硬件设备上的扩充，而是用存储管理软件来实现逻辑上的扩充－即所谓的虚拟存贮技术)（1）覆盖：（2）交换：P129-130（3）虚拟存储器（利用辅存）：P141-143

系统统一管理内外存，程序在运行时，一部分在内存，一部分在外存，从效果上看，好象为用户提供了一个比实际内存器大得多的运行空间，我们称之为虚拟存储器。附：虚拟存储器4、对主存中信息提供保护－存储保护越界保护－范围存储键保护－存储权限虚拟内存用硬盘空间模拟内存存储器分配地址的转换信息的保护程序员编写程序→内存中程序逻辑地址（从0开始）→物理地址

分区法页式段式段页式存储管理多个进程共享存储器，分配、释放存储器进程需要的存储空间是变化的调进或调出进程移动进程功能常用方法分配地址转换保护防止一个进程的存储空间被其它的进程破坏软件和硬件结合的保护措施4.2连续分配方式

连续分配方式：是指为一个用户程序分配一个连续的内存空间。具体的分为四种方式：单一连续分配固定分区分配动态分区分配动态重定位分区分配对于内存一般是被分为两个区域：系统区：存放关于操作系统的文件，处于内存的低址部分。用户区：存放用户的程序或文件，除系统区的剩余内存空间注意：内存分配通常是指对于用户区这一部分内存空间的分配。一、单一连续分配

方法：把内存空间分成两个连续的区域,一个为系统区,供OS使用;另一个为用户区,供用户程序运行。

缺点：内存利用率很低适用于单用户单任务系统中操作系统用户程序0aa+1n内存空间安排二、固定分区分配

方法：在这种方式中，内存的用户区被划分为若干个固定大小的区域，在每个分区中只装入一个作业，这样，在内存中就可以存放多个用户的作业，因而也就允许有多道作业在系统中同时运行。OS4k6k12kOS4k6k12k...7k3k4k5k...3k4k1k2k...5k6k...7k10k11k8k多队列法单队列法优缺点优点：简单易行，特别是对作业大小已知的专用系统，这种方法较为实用。缺点：内存利用率低，产生碎片。OS12k4k3K内部碎片OS4k6k12k作业长度：5K、8K、12K外部碎片一、可变分区分配方法：系统不预先建立分区，分区的建立是在作业处理时进行，这样做的目的是使分区的大小正好满足用户作业的需要，分区的大小及个数都是不固定的。说明：内存分配：动态分配内存回收：当某一块归还后，前后空间合并，修改内存空闲块表1.分区分配中的数据结构分区分配表空闲分区链2.分区分配操作分配内存3.分配算法按空闲块链接的方式不同，可以有以下四种算法：首次适应法下次适应法（循环首次适应法）最佳适应法最坏适应法1)首次适应法：空闲区排列：地址递增的顺序查找：从头查找，直至找到可以容纳该作业的空白块，从中划分作业所需大小空间，剩下的仍保留在链表中。否则，分配失败。特点：优先利用低地址空间，将在高地址部分为后来的大作业保留空间。缺点：查找效率低，低地址部分不断被划分，会形成外部碎片。2)循环首次适应法空闲区排列：地址递增的顺序查找：从上次查找结束的下一个位置开始查找，直至找到可以容纳该作业的空白块，从中划分作业所需大小空间，剩下的仍保留在链表中。否则，分配失败。（循环查找）特点：均匀利用空间，查找开销小。缺点：可能缺少大的空闲分区3)最佳适应算法空闲区排列：容量（或长度）递增的顺序查找：从头查找，即从最小的分区开始查找。特点：用最小空间满足要求，较大的空闲区被保留，有利于满足长作业的要求。缺点：查找效率低，需要调整划分后分区的顺序；会形成外部碎片。4)最坏适应算法空闲区排列：容量（或长度）递减的顺序查找：从头查找，即从最大的分区开始查找。特点：优先利用大分区，查找效率高。不容易形成碎片缺点：容易缺乏大分区，需要调整划分后分区的顺序。例：设系统空闲分区链表为指针7k3k10k8k20k5kabcdef020351005002000用户先后申请7.5k，4k，试用以上四种分配算法，求出分配块。首次适应法:c,a3k3k2.5k8k20k5kabcdef下次适应法:c,d7k3k2.5k4k20k5kabcdef3k5k7k8k10k20kbfadce最佳适应算法:首先从小到大排序3k5k7k0.5k10k20kbfadce3k5k7k0.5k10k20kbfadce再排序从小到大分配块为d,f

内存回收①回收区与插入点的前一个空闲分区F1相邻接②回收区与插入点的后一个空闲分区F2相邻接③回收区与插入点的前后两个空闲分区F1、F2相邻接20K10K260K40K30K30K

50K10K260K40K80K180K

50K10K180K120K120K60K

未分配给用户程序的分区但难以被利用的内存空间总结：固定分区分配特点：分区大小固定不变；分配时较简单，根据当前空闲分区的大小情况分配；缺点：分配时缺乏灵活性，易产生内部碎片。动态分区分配特点：分区大小不固定；分配时较复杂，需要设置一定的数据结构如空闲分区表或空闲分区链；可根据作业大小情况来分配；缺点：易产生部碎片。余留在系统中没有被分配出去并且也不能利用的小的存储空间二、可重定位分区分配可重定位分区分配法是利用分区的“拼接”或“紧凑”技术解决“零头”。动态重定位分区分配方式=“紧凑”技术+重定位+动态分区分配方式可重定位分区的优缺点优点：解决了可变分区分配所引入的“外零头”问题。消除内存碎片，提高内存利用率。缺点：提高硬件成本，紧凑时花费CPU时间。内存保护界限寄存器上下界寄存器基址、限长寄存器保护键为每个分区分配一个单独的保护键，为每个进程分配一个相应的保护键，两者匹配时可访问分区式存储管理的优缺点优点：便于动态申请内存

缺点：碎片问题(外碎片)，内存利用率不高，受实际内存容量限制对换对换：把内存中暂时不能运行的进程或暂时不用的程序数据调出到外存上，一边腾出足够的内存空间，再把一具备运行条件的进程或进程所需的程序和数据调入内存。以进程为单位的对换，称为整体对换。以页或段为单位的对换，称为部分对换。对换空间是外存的一部分，采取连续分配方式管理4.3基本分页存储管理方式引入前面学过的几种存储管理方式，有一个共同的特点：程序集中地分配到一块地址连续的存储空间中，形成了所谓“存储器零头”问题。为解决这一问题，引入页式管理方式。一、页式管理1.方法将一个进程的逻辑地址空间分成若干个大小相等的片，称为页面或页，并为各页加以编号。把内存空间分成与页面相同大小的若干个存储块，称为(物理)块或页框(frame)，也进行编号。在为进程分配内存时，将进程中的若干个页分别装入到多个可以不相邻的物理块中。页式存储管理是离散分配方式页面大小页面的大小一般是2的幂。页面大小一般为512B~8KB，太大则页内碎片大，太小则页表太长，占较大内存2.逻辑地址结构

分页地址结构如下：页面大小=212作业的最大逻辑页数：220P=逻辑地址/页面大小（整除）W=逻辑地址MOD页面大小页号P位移量W3112110在计算机内具体实现时，需解决以下两个问题：（1）作业的一页究竟分配到内存的哪一个存储块中？（2）作业的逻辑地址为连续的，采用这种办法分配时，所分配到的物理地址不一定连续，如何保证作业的正常运行？3.页表页表记录用户进程的逻辑页面与内存物理块之间的对应关系，实现逻辑页号到物理块号的地址映射。图页表的作用地址变换Y图分页系统的地址变换机构N(页数)执行指令或取数据时至少需访问内存两次页表始址+页号×页表项长度例如指令LOAD1,2500地址变换过程如下：

若页表全部放在主存，则要取一个数据(一条指令)至少要访问二次主存，第一次是访问页表，确定所取数据(或指令)的物理地址，第二次是根据该地址取数(或指令)。将作业中最常用的页、块号置入高速缓存，提高查表速度。访问主存＝访页表＋访主存存放页表部分内容的快速存储器称为联想存储器，联想存储器中存放的部分页表称为“快表”。联想存储器一般由8～16个单元组成，它们用来存放正在运行进程的当前最常用的页号和相应的块号，并具有并行查寻能力。快表(联想存储器)具有快表的地址变换机构图具有快表的地址变换机构查联想表－物理地址(访问一次主存)查页表－物理地址(访问二次主存)

有效地址同时进行这个联想存贮器的查表速度可以做到比一般存储器的速度快一个数量级。存储空间管理1)页表：系统为每个进程建立一个页表，页表给出逻辑页号和具体内存块号相应的关系,页表放在内存，属于进程的现场信息2)请求表3)空块管理——位示图4)内存的分配与回收0310/10/10/10/10/1017……空闲块数……空块管理——位示图字号位号内存的分配与回收计算一个作业所需要的总块数N查位示图，看看是否还有N个空闲块如果有足够的空闲块，则页表长度设为N，可填入PCB中；申请页表区，把页表始址填入PCB依次分配N个空闲块，将块号和页号填入页表修改位示图共享和保护共享以页为单位，只需把要共享的页表项加入进程的页表即可保护越界保护

-页表长度寄存器操作访问保护

-在页表项中增设存储保护域基本分页存储管理方式的特点：要求在程序运行前一次性地将整个程序装入内存，但作业在内存中可以不连续分页存储管理器方式的优缺点：优点：由于这种内存分配方式不要求程序或进程的程序段和数据在内存中连续存放，消除了外部碎片，从而能在一定程度提高内存的利用率，又有利于组织多道程序执行。缺点：易产生页内碎片。

在一分页存储管理系统中，某作业J的逻辑地址空间为4页（页面大小为2048字节），且第0、1、2、3页依次存放在物理块2、4、6、7中，现有逻辑地址为4865和10020，将它们转换成物理地址，并画出该系统的地址变换图。习题4.5基本分段存储管理方式引入分段存储管理的引入,主要是满足用户(程序员)编程和使用上的要求。(P136)1）方便编程

2）分段共享

3）分段保护

4）动态链接

5）动态增长一、基本段式管理方式将作业的地址空间划分为若干个段，每个段定义一组逻辑信息,都有自己的名字,且都是首地址为零、连续的一维线性空间。系统以段为单位分配主存，每一段分配连续的分区。同一进程所包含的各段不要求连续.分配方式：离散分配装入方式：在作业运行前一次性地将整个作业装入内存...0S工作区段[B]主程序段[M]......0EP子程序段[X]0K...CALL[X][E].........CALL[Y][F]CALL[A]116......0FL子程序段[Y]0116N数组[A]12345...分段系统中的地址具有如下结构：

段号段内地址3116150整个作业的地址空间是二维结构，由段号（名）和段内地址组成。每段长度不超过216，每个作业不超过216段。地址变换段表

它记录了每个段的首地址和长度，借助段表可实现从逻辑段到物理内存区的映射。

段表常驻内存段号012段首址段长度58K20K100K110K260K140K段表.....B0SA0NY0LX0PM0K逻辑段号01234作业的地址空间10003200500060008000PKSLN主存K3200P1500L6000N8000S5000长度段首址01234操作系统分段管理中作业与段表、存储空间的关系有效地址越界段号S位移量W地址变换机构段表长度段表始址段表寄存器8Ｋ82928692主存＋92002008K5004K6006K1K段号段长基址0123>＋物理地址访问数据时，需两次访问内存：1、访问内存中的段表2、访问数据所在的物理单元解决方法：在地址变换机构中加入快表1）将逻辑地址中的段号S与段表长度TL进行比较，若S≥TL，则产生越界中断信号；2）若未越界，则将段表始址与段号和段表项长度的乘积相加，得到段表项的物理地址；3）检查段内地址d是否超过该段的段长SL，若超过，发出越界中断信号；4）若未越界，则将该段的基址d与段内地址相加，得到实际的物理地址。

4.5段页式存储管理方式

一、产生背景：

结合了段式与页式二者优点 克服了二者的缺点二、基本思想用户程序划分：按段式划分（对用户来讲，按段的逻辑关系进行划分；对系统讲，按页划分每一段）逻辑地址：内存划分：按页式存储管理方案内存分配：以页为单位进行分配段号段内地址页号页内地址三、管理1.段表：记录了每一段的页表始址和页表长度2.页表：记录了逻辑页号与内存块号的对应关系（每一段有一个，一个程序可能有多个页表）3.空块管理：同页式管理4.分配：同页式管理四、地址空间作业地址空间五、地址变换每次访问数据需3次访问内存：访问内存中的段表访问内存中的页表访问数据所在的物理单元解决办法：在地址变换机构中加入快表4.6虚拟存储器的基本概念引入虚拟存储器的原因较大的作业无法一次性装入内存大量作业要求运行时，没有足够的内存解决办法从逻辑上扩充内存容量常规存储器的特征一次性驻留性虚拟存储器实现的理论基础局部性原理时间局限性空间局限性虚拟存储器的定义指具有调入功能和置换功能，能从逻辑上扩充内存容量的一种存储器系统。其逻辑容量由内外存容量之和决定实现方法请求分页系统分段请求系统请求段页式系统虚拟存储器的特征多次性对换性虚拟性4.7请求分页存储管理

请求式分页也称虚拟页式存储管理.与纯分页存储管理不同，请求式分页管理系统在进程开始运行之前，不是装入全部页面，而是装入一个或零个页面，之后根据进程运行的需要，动态装入其它页面；当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面。一、需要解决的问题系统需要解决下面三个问题：系统如何获知进程当前所需页面不在主存。当发现缺页时，如何把所缺页面调入主存。当主存中没有空闲的页框时，为了要接受一个新页，需要把老的一页淘汰出去，根据什么策略选择欲淘汰的页面。页表

实现请求分页技术的硬件支持：页表机制、缺页中断机构、地址变换机构。1.页表机制在基本分页存储管理方式中所采用的页表基础上又增加几项，用来记录程序页面的换入换出情况。除了保留页号、物理块号字段外，又增加了状态位、访问字段、修改位、外存地址四个字段，请求分页系统中的页表结构如下图所示：页号物理块号状态位P访问字段A修改位M外存地址状态位P：

指示该页是否已调入内存，以供程序在运行时参考；访问字段A：记录该页在一段时间内被访问的次数，或记录该页最近有多长时间未被访问，以供系统在换出页面时参考。修改位M：

表示该页在调入内存后是否被修改过。外存地址：指出该页在外存上的地址，通常是物理块号/盘块号。2.缺页中断机构(PageFault)在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，使作业继续运行下去。如果内存中有空闲块，则分配一页，将新调入页装入内存，并修改页表中相应页表项目的驻留位及相应的内存块号。若此时内存中没有空闲块，则要淘汰某页，若该页在内存期间被修改过，则要将其写回外存。3.影响缺页次数的因素(1)分配给进程的物理页面数(2)页面本身的大小(3)程序的编制方法(4)页面淘汰算法4.地址变换查页表时，当存在位指示该页不在主存时，则引起一个缺页中断发生，相应的中断处理程序把控制转向缺页中断子程序。执行此子程序，即把所缺页面装入主存。然后处理机重新执行缺页时打断的指令。这时，就将顺利形成物理地址。5.页面调度策略由于增加了虚拟内存技术，进程的页面有一部分在虚拟存储器上，所以请求分页管理的页面调度策略相较于分页存储管理的策略要复杂得多。1．虚存页面调入策略(P148-149)2．虚存页面分配策略(P147-148)3.页面调入过程保存CPU环境启动中断处理程序查找页表得到需换入页面的外存位置内存是否满从内存中选择一页置换该页是否被修改直接将该页换出需将该页写回磁盘换入外存页面，修改页表发生缺页中断访问该调入内存的页面否是否是二、页面置换算法当要放一页面到全满的主存块时，系统需淘汰一页。用来选取淘汰哪一页的规则，叫置换算法。最佳置换算法先进先出置换算法最近最久未用置换算法近似的LRU算法（NRU算法）

驻留集(工作集)：进程的合法页集合

访问串：进程访问虚空间的地址踪迹。举例：某进程依次依次访问如下地址，0100，0432，0101，0612，0102，0103，…

页式虚存管理以页为基本单位，只需页号即可。设页面大小为100，上述访问串可简化为1，4，1，6，1，1，…2.先进先出(FIFO)页面置换算法系统将最先进入到内存中的页面换出到外存的对换区中，即选择在内存中停留时间最长的的页面予以淘汰。利用FIFO置换算法时的置换图

在早期，人们所编写程序其结构都是比较简单的，大多程序是线性的，很少有循环、嵌套、迭代等这些复杂的结构，因此，先进先出页面置换算法其实是基于程序线性结构的特性而设计出的一种页面置换算法。

这种算法比较容易实现，系统只要将进程在内存中的页面按照进入内存时间的先后顺序排序，并组织成一个队列，另外再设置一个指针，使这个指针总执行最早进入到内存的那个页面。补充：Belady异常现象例：进程P，页面号引用串为:432143543215，最初分物理块数3，后来又追加1个物理块。

43214354321544411155533344422222333144445555113333444452222333311112223.最近最久未使用(LRU)置换算法选择在最近一段时间内最久不用的页面予以淘汰。

LRU页面置换算法优点:

适用于各种类型的程序。缺点:

实现代价很高(时间戳或硬件方法)。LRU置换算法的硬件支持1)寄存器为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为:R=Rn-1Rn-2Rn-3…R2R1R02)栈4.Clock置换算法(近似的LRU算法）优点:

算法简单,易于实现。缺点:

周期T的大小不易确定。5.其它置换算法（P154-155）最少使用(LFU：LeastFrequentlyUsed)置换算法2.页面缓冲算法(PBA：PageBufferingAlgorithm)

页面置换算法实现思想优点缺点最佳置换算法根据最近的将来页面的使用情况理论意义上的较难实现先进先出页面置换算法根据页面进入内存的先后顺序易实现置换顺序与实际页面访问顺序不一致最近最久未使用置换算法根据最近时间内页面的使用情况较好的一种算法需硬件支持Clock置换算法根据上次(很短时间)页面的使用情况最少使用置换算法根据页面被访问的次数情况页面缓冲置换算法采用FIFO置换算法，将需要置换的页面一起置换

在一个请求分页系统中，假定一个程序的页面走向为2，3，2，1，5，2，4，5，3，2，5，2，目前它还没有任何页装入内存，当系统分配给该程序的物理块数为3。试用FIFO和LRU两种页面置换算法分别计算程序访问过程中所发生的缺页次数和缺页率。FIFOLRU缺页次数97缺页率75%58.3%习题4.8、请求分段存储管理基本思想：运行之前装入程序的若干段就可以运行，以后再通过调段功能和置换功能，将暂不运行的段调出，同时调入即将运行的段。置换单位（换入换出的单位）：段；硬件支持：请求分段的段表机制缺段中断机构地址变换机构1.扩充段表

段号，段长，段始址，存取方式，访问字段，修改位，存在位，增补位，辅存地址存在位：表示该页在不主存访问字段：表示该页最近被访问的频繁程度修改位：表示该页内容是否被修改增补位：（固定长/可扩充）2.缺段中断处理检查内存中是否有足够的空闲空间①若有，则装入该段，修改有关数据结构，中