软件技术存储管理复习课程

第九章

存储管理本章基本内容与要求基本内容存储器层次结构存储管理任务实存储管理虚拟存储管理要求掌握存储管理任务掌握存储管理、实存储管理、虚拟存储管理了解存储器层次结构第一节存储器层次结构

存储管理目的1、充分利用内存，为多道程序并发执行提供存储基础2、尽可能方便用户使用自动装入用户程序用户程序中不必考虑硬件细节3、系统能够解决程序空间比实际内存空间大的问题4、存储保护与安全1.主存空间分配

合理分配，避免冲突；算法得当，提高效率；及时回收，循环利用。2.地址映射目标程序内存地址空间存储空间0x0640k系统区存放操作系统目标程序用户区存放用户作业绝对地址：主存储器以字节为编址单位，容量为n的主存储器中，每个单元有唯一的编号，从0到n-1，这个唯一的编号就是主存储器的绝对地址(物理地址)。绝对地址逻辑地址:在多道程序设计的系统中，操作系统为了方便用户，就允许每个用户都认为自己的作业的程序和数据存放在地址是0开始的连续空间中。这样用户程序中使用的地址就是逻辑地址(相对地址)。相对地址重定位:当用户程序调入内存时，必须把逻辑地址转换成绝对地址，同时包括对程序中与地址有关的指令进行修改，这一过程叫“重定位”或“地址转换”。重定位的方式有两种:静态重定位动态重定位地址转换静态重定位在装入一个程序时，把程序中的指令地址和数据地址全部转换成绝对地址。这种转换工作是在程序开始前集中完成的，在程序执行过程中无需再进行地址转换。所以称为“静态重定位”。使用一对界地址寄存器，分别存放该程序的起始和终止地址.x逻辑地址空间LD上界下界界地址寄存器Dx'L物理地址空间x'=x+D物理地址逻辑地址下界地址D<=x'<L动态重定位在装入一个程序时，不进行地址转换，而是直接把程序装到分配的主存区域中。在程序执行过程中，每当执行一条指令时都由硬件的地址转换机构转换成绝对地址。这种方式的地址转换是在程序执行时动态完成的，所以称为动态重定位。动态重定位由软件（操作系统）和硬件（地址转换机构）相互配合来实现。2.地址映射

程序的起始地址都是从“0”开始的，程序中的其它地址都是相对于起始地址计算的，该地址被称为逻辑地址（或相对地址）。由这些地址所形成的地址范围称为（作业）地址空间。主存单元的编号称为物理地址（或绝对地址）由主存中的一系列单元所限定的地址范围称为存储空间。相对地址到绝对地址的转换，同时程序中与地址有关的指令的修改，这一过程叫做地址重定位。静态重定位在程序装入时进行,由装配程序进行地址转换动态重定位是在程序的执行过程中,当CPU访问指令或数据前，由地址变换机构进行地址变换。3.内存保护

静态重定位系统中：用界地址寄存器判断程序是否在规定的上下界内动态重定位系统中：与存储方式有关保护系统程序区不被用户侵犯。不允许用户程序读写不属于自己地址空间的数据4.内存“扩充”

把内外存联合起来，向用户提供一个容量比实际容量大的多的存储空间。技术：覆盖交换虚拟存储扩充内存方法-覆盖技术A20kBB50kBC20kBF30kBD20kBE40kB共180kBABCFDE020k21k70k71k110k共110kB作业必须满足树状的模块结构要由用户写出覆盖文件ROOTA-(B-F,C-(D,E))扩充内存方法-交换技术以整个作业为单位进行内外存交换（滚进滚出）缺点：移动会增加系统开销。第三节实存储管理单一连续分区(单道环境)固定分区动态分区为调入内存的程序提供一个不小于作业地址空间的存储空间，当存储空间不够时，采用覆盖或交换技术扩充内存1.单一连续分区

在单道环境下，不管是单用户系统还是单道批处理系统，进程（作业）执行时除了系统占用一部分主存外，剩下的主存区域全部归它占用。2.固定分区分配区号容量起始位置状态作业名18k16k占用作业1216k24k占用作业2332k40k空闲456k72k占用作业3操作系统区作业1作业2作业3016k24k40k72k128k内存状态表内存基本原理：预先把可分配的主存储器空间分割成若干个连续区域，每个区域的大小可以相等，也可以不等。固定分区的优缺点优点实现多个作业共享分区的分配和回收算法简单缺点内存利用不充分，因为每个分区中都会有一部分空间被浪费了。操作系统区作业1作业2作业3016k24k40k72k128k内存碎片3.动态分区

主存不是预先划分好的，而是当作业装入时，根据作业的需求和主存空间的使用情况来动态决定是否分配。进程5OS进程9进程10进程2进程5OS进程9进程2进程5OS进程2进程5OS进程8进程2占用块进程5OS进程10进程2空闲块3.动态分区

分区分配空闲分区分配算法分区的回收可重定位的动态分区3.动态分区

分区分配采用分区表（或者分区链表）来实现空闲分区表:表示空闲分区的信息已分区分配表:已使用分区的信息3.动态分区

分区分配3.动态分区

2.空闲分区分配算法

1）首次适应算法（FirstFit）

2）下次适应算法（NextFit）

3）最坏适应算法（WorstFit）

4）最佳适应算法（BestFit）3.动态分区

2.空闲分区分配算法

1）首次适应算法（FirstFit）在分区表中顺序查找，找到够大的空闲区就分配。特点：简单、快速分配缺点:可能形成许多不连续的空闲区，造成许多“碎片”，使主存空间利用率降低。3.动态分区

2.空闲分区分配算法

2）下次适应算法（NextFit）

类似首次适应法，总是从上次查找结束的地方开始，只要找到一个足够大的空白区，就把它划分后分配出去。特点：解决了低地址区会产生很多碎片的问题，使内存中空闲分区分布比较均匀，缺点:大的空闲分区在内存中不易保留。3.动态分区

2.空闲分区分配算法

3）最坏适应算法（WorstFit）总是挑一个最大的空闲区分给作业使用，使剩下的空间不至于太小。适用于请求分配内存大小较均匀的系统要求:空白块自大至小排列3.动态分区

2.空闲分区分配算法

4）最佳适应算法（BestFit）接到内存申请时，在空闲块表中找到一个能满足要求的最小空块进行分配特点：用最小空间满足要求缺点:可能形成一些极小的空闲区，以致无法使用，这也会影响主存利用率。要求:空白块自小至大排列3.动态分区

3.分区的回收

当进程结束或终止时，要进行内存回收。如果回收的分区与其它的分区相邻，则合并成一个较大的分区，修改空闲分区表，并检查是否满足阻塞在内存空间的等待进程的需求。

3.动态分区

4.可重定位的动态分区使用紧凑技术，为了消除外部碎片，进一步提高主存的利用率，定时地（或者在主存空间紧张时）把主存中的作业“搬家”集中在主存的一端，使另一端产生一个大的空闲区，这种技术称为存储器的“紧凑”。紧凑仅仅在动态重定位时才可以用，并且在运行时执行。P1P2P3P4P5P6占用块空闲块P1P2P3P5动态重定位…Load1,1000…0289001001000地址空间…Load1,1000…02890100231012311023+10023存储空间定位寄存器每读一条指令，都要变换一次地址。变换要靠硬件支持.第四节虚拟存储管理1.虚拟存储器的原理2.请求分页存储管理3.请求分段存储管理虚拟存储管理工作原理：首先把作业信息保留在磁盘上，当作业请求装入时，只将其中一部分先装入主存，作业执行中若要访问的信息不在主存中，则再设法将这些信息装入主存。用软件方法扩充内存。逻辑上扩充了内存空间。虚拟地址空间的大小受指令中地址长度的限制和外存储容量的限制；需解决什么时候把哪部分程序装入内存、放在内存什么地方、淘汰策略问题。内存分页1.虚拟存储器的原理——程序局部性原理

在一段时间内一个程序的执行往往呈现出高度的局部性，表现在时间与空间两方面时间局部性：一条指令被执行了，则在不久的将来它可能再被执行空间局部性：若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用2.请求分页存储管理

1).分页管理的基本概念2).地址变换机构3).页面置换算法4).分页存储管理的优缺点饭店房间和内存分页0页1页2页…n页0213263449……用户程序页表页号块号内存块号01234567分页存储管理页:将作业的地址空间划分成一系列大小相等的块，称为页，所有页按顺序编号为0、1、2、·…¨。页内地址:每个页内的内容也都从0开始顺序编号，这个编号称为页内地址。块（页框）:内存空间也划分成与页一样大的块，所有的块从低地址到高地址顺序编号为0、1、2、·…¨。页表:系统为作业建立一个页号与块号的对照表。页表(PMT表)页号与块号的对照表，称为页表。页号块号状态0:该页不在内存1:该页在内存在多道程序设计系统中，进入主存的每个作业都有一张页表，由一个硬件“页表地址寄存器”来记录每个作业的页表所在位置和长度以便作业转换时同时转换页表。分页系统中的逻辑地址页号p页内地址d逻辑地址可用一个数对表示p=INTAL逻辑地址页面大小d=AMODL例:设某系统页面大小位1024字节，若逻辑地址为:2500,则p=INT(2500/1024)=2d=2500MOD1024=452即2500处于第2页,第452位置上2).分页管理中的地址转换访问某个逻辑地址时，分页地址变换机构自动将逻辑地址分为页号和页内地址两部分，再以页号为索引去检索页表。从页表中查到相应页的目录，将该页对应的块号与页内地址合并构成物理地址将页号与页表长进行比较，若页号超过了表长，产生越界中断2).分页管理中的地址转换Load,1,250023285…地址空间…内存块号0181010002500300003110281页号块号状态Lb+页表长页表起始地址页表地址寄存器24528452232858644PMT表pdp'd'地址变换机构8*1024+452=8644绝对地址=块号*页面大小+页内地址作业(要求写出计算过程）：在请求分页系统中，设每页512字节，某时刻系统给用户程序第0、1、2、3页分配的物理块号依次为6、11、3、17，则用户程序中逻辑地址1200经变换后得到的物理地址为

，该地址所在的物理块号为

。分页式虚拟存储器的实现

首先把作业信息作为副本存放在磁盘上，作业执行时，把作业信息的部分页面装入主存储器，作业执行时若所访问的页面已经在主存中，则进行地址转换，得到绝对地址，否则产生“缺页中断”由操作系统把当前所需的页面装入主存。

XXXX7X5XXX34061260K-64K56K-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K28K-32K24K-28K20K-24K16K-20K12K-16K8K-12K4K-8K0K-4K虚地址空间物理地址空间}虚页分页虚拟存储管理缺页中断（PageFault）在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，使作业继续运行下去如果内存中有空闲块，则分配一页，将新调入页装入内存，并修改页表中相应页表项目的状态位及相应的内存块号若此时内存中没有空闲块，则要淘汰某页，若该页在内存期间被修改过，则要将其写回外存3).页面置换算法

当主页中无空闲块时，为了装入一个页面，就必须按某种算法将主存中某个页调出，调入所需装入的页面。这就是页面调度。算法有：先进先出调度算法(FIFO)、最近最少使用调度算法(LRU)最近未使用页面置换算法（NRU）最佳页面置换算法(OPT)

(1)先进先出算法(FIFO)

当需要淘汰一页时，选择在主存中驻留时间最长的那页被淘汰掉。思想:最先进入内存的页面,不再被使用的可能性最大适用于按线性顺序访问的程序

先进先出算法(FIFO)设一用户程序共分5页,分配给它的内存块数为3页面走向P为

432143543215其页面淘汰过程:432143543215432143555211432143335224321444355+++++++++缺页中断9次FIFO页面淘汰算法会产生异常现象，即：当分配给进程的物理页面数增加时，缺页次数反而增加。例如：假设作业共有5个虚页，其页面访问踪迹为：0，1，2，3，0，1，4，0，1，2，3，4。计算当分配3个和4个实页时的缺页中断次数。页面访问踪迹012301401234三个实页的分配与淘汰012301444233

01230111422

01230001449次缺页中断√√√√√√√

√√

页面访问踪迹012301401234四个实页的分配与淘汰012333401234

01222340123

0111234012

00012340110次缺页中断√√√√

√√√√√√(2)最近最少使用算法(LRU)

当需要淘汰一页时，选择在最近一段时间内最久未用的页淘汰掉。UNIX操作系统采用的就是这种算法。方法：设置记时器:在页表的每个入口，设一个“访问时间”区域,当一个页面被访问时，时钟寄存器里的内容被拷贝到这个区域。置换时替换最小时间值的页面。利用堆栈:当页面被访问时，将它从堆栈底部移到顶部。栈顶页面常常是最常用的页面，而底部的就是LRU页。

(3)最近未使用页面置换算法（NRU）

是LRU算法的近似：将内存中的页面组成一循环链表，每一页面对应一访问位，当某页面被访问时，将其访问位自动置“1”。如果指针指向页面的访问位为“0”（代表最近没有被访问），则置换该页；否则，将访问位置为“0”，页面继续留在内存，按照相同规则替换下一页。如果一页经常被用到，则它永远不会被换出。

NRU页面替换过程入口查询指针前进一步,指向下一个表目页面引用位=0?选择该页面淘汰返回置页面访问位=0是否01240342156507108块号页号引用位指针····q第6页请求进入NRU页面替换过程入口查询指针前进一步,指向下一个表目页面引用位=0?选择该页面淘汰返回置页面访问位=0是否01240342156507108块号页号引用位指针····q611第1页请求访问第5页请求进入NRU页面替换过程入口查询指针前进一步,指向下一个表目页面引用位=0?选择该页面淘汰返回置页面访问位=0是否01240342156617118块号页号引用位指针····q0NRU页面替换过程入口查询指针前进一步,指向下一个表目页面引用位=0?选择该页面淘汰返回置页面访问位=0是否01240342156617108块号页号引用位指针····q15引用位周期性清零NRU页面替换过程入口查询指针前进一步,指向下一个表目页面引用位=0?选择该页面淘汰返回置页面访问位=0是否01240342056607108块号页号引用位指针····q5(4)最佳页面置换算法(OPT)

该算法思想是从主存中移出永不再用的页面，至少是选择很远的将来才用的页面淘汰之。其实，这是一个不实用的算法，因为页面走向是不可预知的。所以该算法常用做性能评价的依据。OPT算法具有最低的缺页率。4).分页存储管理的优缺点

优点分页存储管理的优点是不需要移动就可解决碎片问题；提高主存的利用率；可提供大容量的多个虚拟存储器；提高了多道程序运行的程度；对大作业而言，更加方便用户。缺点由于采用了动态地址变换机构，增加了计算机的成本，处理速度降低；对于请求分页系统，为处理页面中断增加了系统开销；在进程的最后一个页框中可能有内部碎片的存在。

从分页到分段第0页第1页第2页第3页第4页第5页第6页第7页第8页第9页内存作业逻辑结构主程序段子程序段数据区段工作区段内存作业逻辑结构主程序段子程序段数据区段工作区段用户希望第0段第1段第2段第3段3.请求分段存储管理分段存储管理中,作业的地址空间被划分为若干个段,每段定义一组逻辑信息,如:主程序段,子程序段,数据段等,规定一个段号,每段地址空间都从0开始.段号s段内地址w逻辑地址可用两部分表示内存分配:以段为单位分配内存，每一个段在内存中占据连续空间（内存随机分割，需要多少分配多少），但各段之间可以不连续存放段表(SMT表)段号段长度起始地址状态0:该段不在内存1:该段在内存

它记录了段号，段的首（地）址和长度之间的关系每一个程序设置一个段表，放在内存属于进程的现场信息分段管理中的地址转换逻辑地址段号s段内地址w…内存01k6144