昆明理工大学付湘琼操作系统存储器管理课件.ppt

《昆明理工大学付湘琼操作系统存储器管理课件.ppt》由会员分享，可在线阅读，更多相关《昆明理工大学付湘琼操作系统存储器管理课件.ppt（76页珍藏版）》请在三一文库上搜索。

1、计算机操作系统 第四章存储器管理,1,昆明理工大学付湘琼操作系统存储器管理,4.1 存储器管理的若干概念 存储器 地址变换 虚拟存储器,一存储器 1存储器,存储器,主存 （内部存储器，磁芯存 储器）,辅存 （外存）磁盘、磁鼓、 磁带、 软盘,主存,系统区 （OS标准子程序）,用户区 （用户程序、数据）,2主存储器的物理组织，多级存储器,高速 缓存,主存,外存,3存储器管理的功能： (1) 主存空间分配和保护：主存储器中允许同时容纳各种软件和多个用户程序时，必须解决主存空间如何分配以及各存储区内的信息如何保护等问题。对不同的存储管理方式，采用的主存空间分配策略是不同的。为了保护区域内信息不被破坏

2、，必须实现存储保护。存储保护的工作必须由硬件和软件配合来实现。 (2)主存空间的重定位 配合硬件做好地址转换工作，把一组逻辑地址空间转换成绝对地址空间，以保证处理器的正确执行。,(3)主存空间的共享 在多道程序设计的系统中，同时进入主存储器执行的作业可能要调用同的程序。例如，调用编译程序进行编译，把这个编译程序存放在某个区域中，各作业要调用时就访问这个区域，因此这个区域就是共享的。同样也可实现公共数据的公享。 (4) 主存空间的扩充 提供虚拟存储器，使用户编制程序时不必考虑主存储器的实际容量，使计算机系统似乎有一个比实际主存储器容量大得多的主存空间。,二地址变换 1.存储空间 地址空间一个目标

3、程序所限定的地址范围 逻辑地址（相对地址）当对源程序进行编译时，编译后一个目标程序所限定的地址范围称为该作业的逻辑地址空间。 物理地址（绝对地址）主存中一系列存储 物理单元。 地址空间是逻辑地址的集合。存储空间是物理地址的集合。一个是虚的概念，一个是实的物体。,2.重定位 当一个地址装入与其地址空间不一致的存储空间中，就得要地址变换。也就是说将虚地址映射为内存地址，把这种作法叫做地址重定位 (1)静态地址重定位 在装入一个作业时，把作业中的指令地址全部转换为绝对地址（地址转换工作是在作业执行前集中一次完成的）在作业执行过程中就无须再进行地址转换工作。,静态地址重定位优点 它的主要优点是，无需增

4、加硬件地址变换机构，因而可在一般计算机上实现。 静态地址重定位缺点 主要缺点有：要求给每个作业分配一个连续的存储空间，且在作业的整个执行期间不能再移动，因而也就不能实现重新分配主存。用户必须事先确定所需的存储量，若所需的存储量超过可用存储空间时，用户必须考虑覆盖结构。用户之间难以共享主存中的同一程序副本。,2动态地址重定位： 动态地址重地位是在程序执行过程中，在cpu访问内存之前,将要访问的程序或数据地址转换成内存地址. 动态重定位依靠硬件地址变换机构完成。,+,1500,0,100,500,虚拟空间,内存空间,VR,BR,.,地址重定位机构需要一个或多个基地址寄存器BR和一个或多个程序虚地址

5、寄存器VR。指令或数据的内存地址MA与虚地址的关系为：MA=(BR)+(VR) 其中，(x)表示寄存器x中的内容,最简单的办法是利用一个重定位寄存器。该寄存器的值由调度程序根据作业分配到的存储空间的起始地址来设定。在具有这种地址变换机构的计算机系统中，当作业执行时，不是根据CPU给出的逻辑地址去访问主存，而是将逻辑地址与重定位寄存器中的内容相加后得到的地址作为访问主存的地址。,动态重定位的主要优点有： 用户作业不要求分配连续的存储空间。用户作业在执行过程中，可以动态申请存储空间和在主存中移动。有利于程序段的共享。 动态重定位的主要缺点有： 需要附加的硬件支持。实现存储管理的软件算法比较复杂。,

6、三.虚拟存储器 什么是虚拟存储器？ 虚拟存储器是一种存储管理技术，用以完成用小的内存实现在大的虚拟空间中程序的运行工作。 为了给大作业用户提供方便,使它们摆脱对主存和辅存的分配和管理问题,由操作系统把多级存储器统一管理起来,实现自动覆盖。既一个大作业在执行时, 其一部分地址空间在主存,另一部分在辅存,当访问的信息不在主存时.因此,从效果来看,这样的系统,好象用户提供了存储容量比实际主存大得多的存储器,人们称这个为虚拟存储器。之所以称它为虚拟存储器,因为这样的存储器实际上并不存在而只是系统增加自动覆盖功能，给用户造成的一种幻觉,仿佛它有一个很大的主存供它使用。这是虚拟存储器的最初概念。,这种想法

7、的核心,实质上也就是把作业的地址空间和实际主存的存储空间似为两个不同的概念.一个计算机系统算题人员提供了一个多大的地址空间,它就所在这个地址空间编制程序,而完全用不着考虑实际主存的大小.换句话说, 虚拟存储器就是一个地址空间.一个虚存储器的最大容量是由计算机的地址结构确定的.若CPU给出的有效地址长度为18位,可以寻址范围为:0-256k;若地址的长度为为20位,则寻址范围为:1024k. 实际虚拟存储器其一是要相当容量的辅存,足以存放所有并列作业的地址空间.其二是要有一定的主存,因为处理机上运行的作业,必须有一定的信息在主存中.其三是地址变换机构.,4.2 分区存储管理 4.2.1 分区管理

8、基本原理 1.固定分区法 固定分区把主存分成若干个固定大小的存储区。,OS,20K,28K,60K,124K,256K,进程A（6K）,进程B（25K）,进程C（36K）,2.动态分区法 因为固定分区主存利用率不高，使用起来不灵活，所以出现了可变分区的管理技术。 动态分区原则：存储空间的划分是在装作业时进行的。从可用的自由存储空间内，划出一个大小正好等于作业大小的存储区，并分配给这一作业。,OS,进程A,进程B,进程C,进程D,OS,进程A,进程B,进程C,OS,进程A,进程B,OS,进程A,进程E（50K）,进程F（16K）,进入内存,进程B（16K）,进程D（124K）,完成,内存分配变化

9、过程,4.2.2分区的分配与回收 固定式分区和可变式分区的存储管理算法有如下三种： 最佳适应算法(Best Fit) （1）含义 最佳适应算法就是为一作业选择分区时总是寻找其大小最接近于作业所要求的存储空间。换句话说，把作业放入这样的分区后剩下的部分最小。 （2）优点 这种算法的优点是：如果存储空间中具有正好是所要求大小的空闲区，则必然被选中；如果不存在这样的空闲区，也只对比要求稍大的空闲区划分，而绝不会去划分一个更大的空闲区。 （3）实现方法 为了加快查找速度，应将空闲区按其大小递增的顺序排列，组织成一空闲区链。,最坏适应算法（Worst Fit） (1）含义 它在为作业选择存储空间时，总是

10、寻找最大的空闲区。 （2）实现方法 空闲区应按其大小递减的顺序排列。分配时只看链头空闲区是否满足要求，决定是否分配。,首次适应算法(First Fit) （1）含义 最佳适应和最坏适应算法各有利弊。首次适应算法是对它们进行折衷考虑后设计出来的。 （2）实现方法 将空闲区按其在存储空间中的起始地址递增的顺序排列。为作业分配存储空间时，从空闲区链的始端开始查找，选则第一个满足要求的空闲区。,（1）分区分配的主要步骤有： 从未分配表中找到一个足以容纳该作业的可用空闲区；如这个空闲区比所要求的大，则将它分成两部分：一部分成为已分配的分区，剩下部分仍为空闲区； 修改两张表的有关信息，并回送一个所分配分区

11、的序号或该区的首址。,要求Xk大小分区,取分区说明表第一项,状态位置正在使用,取下一表项,无法分配,该分区空闲？,分区长度Xk?,表结束？,返回分区号,否,否,否,是,是,是,固定分区分配算法,最佳分配算法例子,系统回收一个分区的主要步骤有： 检查回收分区是否与空闲区邻接，如邻接则加以合并，使之成为一个连续的大空闲区。修改两张说明表。,可重定位分区存储管理,含义 采用动态分配的可变分区管理，即分配时可以将主存重的空闲区拼接后再分配。 由于可变式分区存储管理是根据作业的需求量划分分区的，因此消除了固定式分区分配造成的内零头。但是，由于作业的多次请求和释放，主存中经常可能出现大量的不能充分利用的小

12、空闲区。,采用拼接技术，把零头集中起来形成一个大的空闲区。实现方法是移动某些已分配区中的信息，移动够分配为止或者使所有的作业位于存储器的一端，把空闲区全部留在另一端，,空闲区拼接的时机选择 进行拼接的时机可选则为 （1）当有作业完成释放分区时，就立即拼接。这样的拼接是比较频繁的，要花费较多的处理机时间。 （2）当某一作业请求分配存储空间时，若当时主存没有足够大的空闲区，但所有空闲区的总和可以满足该作业的要求，此时进行拼接。这样的拼接可节省处理机时间。,分配算法流程,45 页式管理 4.5.1页式管理的基本原理 在分区存储管理中，都要求把一个作业的地址空间装入到连续的存储空间内，不是存在内零头，

13、就是存在外零头或为解决外零头花费时间进行“拼接”。如果我们能取消作业对连续性的要求，必然会进一步提高主存的利用率，又无需为移动信息付出代价。分页管理就是在这个指导思想下设计出来的。,1. 分页技术的实现原理 等分主存： 把主存的存储空间划分成大小相等的片，称为存储块，或称为页架（Page Frame） 用户逻辑地址空间的分页： 把用户的逻辑地址空间（虚地址空间）划分成若干个与存储块大小相等的片，称之为页面或页（Page）。并给各页从零开始依次编以连续的页号0，1，2，。 逻辑地址的表示： 用户的逻辑地址一般是从基地址“0”开始连续编址，即是相对地址。在分页系统中，每个虚拟地址（相对地址）用一个

14、数对（p,d）来表示。其中p是页号，d是该虚拟地址在页面号为p的页中的相对地址，称为页内地址（位移量）。 主存分配原则： 系统以存储块为单位把主存分给作业或进程，并且分给一个作业的各存储块不一定是相邻和连续的。,页表 在分页系统中，作业的一页可以分配到主存空间中任何一个可用的存储块。但是，系统怎么知道作业的哪一页分配到哪一存储块内？为此，系统建立了一张页面映象表，简称页表。用一张页表来描述每页的页号与所在块的块号的映射。,为了便于管理和保护，系统为每个装入主存的作业建立一张相应的页表，它的起始地址及大小保存在该作业的PCB中。一旦这个作业被调度执行，把它的页表始址及大小装入特定的页表寄存器中。

15、,4.5.2 简单分页管理 在作业或进程开始执行之前，把该作业或进程的程序段和数据全部装入主存的各个空闲块中，并通过页表和硬件地址变换机构实现虚拟地址到主存物理地址的地址映射。 1主存的分配与回收 所需的表格 为了实现分页存储管理，在软件方面应建立如下表格，并由操作系统实施管理。 (1）页表（PMT）。每个作业一张表，用于该作业的地址变换，该作业有多少页面就有多少表目。 （2）存储分块表（MBT）。整个系统一张表。该表中每一表目对应一个存储块，记录了该块的状态：已分配或空闲。,2.分配算法 当进程或作业要求分配主存块时，首先检查是否有足够的空闲块，如果没有，则本次无法分配。如果有则首先分配设置

16、页表，将分到的主存快号添入页表中。,3.地址变换 地址变换过程 （1）当调度一个作业执行时，首先将页表始址及大小装入页表寄存器。 （2）作业执行过程中CPU产生的每一个逻辑地址，由硬件地址变换机构自动将其分成两部分：一部分为页号，另一部分是页内位移量。 （3）这个页号先与页表寄存器中的当前页表大小进行比较。如果页号太大，表示访问越界，系统产生相应的中断。如果页访问是合法的，则由页表始址和页号计算出所对应的物理块号； （4）取出其存取控制字段，作存取控制验证，若合法则将物理块号与逻辑地址中的位移量拼接，形成最终访问的物理地址。否则，产生相应访问非法中断。,地址变换例子 例如，设一个3页长的进程具

17、有页号0、1、2,分到的主存快号为2、3、8。假设页的大小为1K,指令LOAD 1,2500的虚地址为100。下面我们以该例子来说明地址变换过程。,（1）指令地址100转换 由虚地址100可知，指令LOAD 1,2500在第0页的100单元中。由于第0页在主存的第二块中，因此，该指令在主存的地址为2048+100=2148。 （2）指令地址2500转换 当CPU执行到第2148单元的指令时，地址变换机构首先将2500转换为页号与页内地址两部分，即P=2,W=452。由页表，可知第二页所对应的主存快为8。将块号8与页内地址452相连，得到待访问的主存物理地址为8644。,4. 超高速缓存 联想存

18、储器 为了提高地址变换速度，且不增加太多的硬件投资，通过在地址变换机构中增设一组数量不多的寄存器，把它作为超高速缓冲寄存器来使用，存放当前访问的那些页的页号和块号。 地址转换过程 （1）当运行进程要访问逻辑地址v时，硬件自动将逻辑地址v截成页号p和页内地址d。 （2）地址转换机构首先以页号p和高速缓冲器中各表目相比较。 （3）若该页不在高速缓冲器中，则访问存储器中的页表。如果相符，则它送出相应的块号与页内地址一起形成物理地址，并按此地址访主存。,超高速缓存（找到）,超高速缓存（未找到）,4.5.3 请求分页管理 请求分页存储管理是在简单分页管理基础上发展起来的。请求页式管理在作业或进程开始执行

19、之前，只把当前需要的一部分页面装入主存，其它部分在作业执行过程中需要时，再从辅存上调入主存,1.页表的扩充 页表增加信息 通常页表表目应增加如下信息： （1）中断位：表示该页是否在主存。中断位为0表示该页在主存；为1表示不在主存。 （2）修改位：该位为0时，表示该页面中的数据未被修改过。该位为1时，表示该页面中的信息已被修改过。 （3）访问位：表示该页面在最近期间是否被访问过。该位为0时，表示该页面未被访问过。为1时，表示该页面最近被访问过。该位主要用于页面置换策略中。 （4）辅存地址：指出该页面在辅存上的存放地址。 扩充后的页表如图所示：,2.地址变换 请求分页的地址变换初始过程十分类似于简

20、单分页系统的地址变换，其全部工作：存储空间的分配，页面的置换等都是在指令执行过程中完成的，更准确地说，是在CPU访问内存的过程中完成的。,3.缺页中断处理 当中断位为1时，表示该页不在主存，则必须确定它在辅存中的存放地址。并把它从辅存中调入主存。缺页中断的处理过程如图：,4. 提取页面策略 这是一个何时把页面装入主存的问题。 两种策略 （1）请求式提取:仅当需要时才提取页面的策略； （2）预先调页:把事先提取页面的策略。任何预先调页策略都是以预测为基础的。如果能装入合适的不久要访问的页面，则可减少缺页中断。在很长一段时间内（甚至本次运行）都不被存取，这样的预先调页是失败的。因为预先调页的成功率

21、约为50，因此，大多数系统采用纯请求式提取页面策略。,4.5.4请求页式管理中的置换算法 （页式淘汰算法） 1.先进先出（FIFO）算法 FIFO：总是淘汰最先进入主存储器的那一页。 FIFO算法容易实现，但是它所依据的理由不是普遍成立的。哪些在内存中驻留很久的页，往往是被经常访问的页，结果这些常用的页都被淘汰调，而可能又需要立即调回内存。 采用FIFO算法还会产生一种奇怪现象，直观上，分配给的作业的实页越多，进程执行时发生的缺页中断率就越小，但对FIFO算法这个结论并不是绝对的。在某些情况下，当分配的页面多反而导致更多的缺页中断，这种现象称为FIFO异常现象或称Belady现象。 创建进程式

22、时往往只向内存装入了第0页。,当需要淘汰某一页时，选择在最近一段时间里最久没有被使用过的页淘汰。 A.近似算法(LFU)：当需要淘汰时，应淘汰被访问次数最少的页。一种简单的方法是为每一页设置一个计数器，每当访问一页时，就把该页对应的计数器加一，隔一个周期T，把左右计数器清0。当发生缺页中断时，选择计数值最小的页，可把它淘汰，同时把所有计数器清0。,1.最近最久未使用页面置换算法（LRU）,B.最近没有使用的页面淘汰算法NUR 需要淘汰某一页时，从那些最近一个时期内未被访问的页中任选一页淘汰。 实现方法：在页内增设一个访问位，当这一页被访问时，硬件把它置成“1”，而没有被访问过的页，访问位为“0

23、”。因此，在产生缺页中断时，可从那些访问位为0的页中选一页进行淘汰。,抖动和工作集 1. 局部性概念 局部性含义 (1)时间局部性：是指某个位置最近被访问了，那么往往很快又要被再次访问。 (2)空间局部性：是指一旦某个位置被访问了，那么它附近的位置也将被访问。 2. 抖动(或称颠簸) 抖动： 如果一个进程花费多于执行时间的时间来完成页面替换工作，我们称该进程是颠簸的。,4.5.5 存储保护 一种是地址越界保护，另一种存取控制保护。 地址越界保护可由地址变换机构中的控制寄存器的值页表长度和所要访问的虚地址通过比较完成。 存取控制保护是通过页表控制对内存信息的操作方式提供保护。它的实现则是在页表增

24、加相应的保护位即可。,页式管理的优缺点,优点 (1) 由于它不要求作业或进程的程序段和数据在主存中连续存放，从而有效的解决了碎片问题。(2) 请求分页管理提供了虚拟存储器。提高了主存的利用率，更加有利于多道程序的运行和方便用户，特别是大作业用户。 缺点 （1）要求有相应的硬件支持。（2）为处理缺页中断，增加了处理机时间的开销。（3）为防止系统抖动所采取的各种措施会增加系统的复杂性。（4）每个作业或进程的最后一页内总有一部分空间得不到利用。,4.6 段式与段页式管理 1.作业的逻辑地址空间：分段情况下要求每个作业的地址空间按照程序的自然逻辑关系分成若干段，每个段有自己的段名。,作业A,0,2K,

25、0,0.5k,0,300,0,200,2. 段式存储管理的地址结构,a:虚拟地址,b:段表,段表每个作业一个，这个段表实施段保护，提供虚存。 存取方式读/写、只读、执行。,段表长度 起始地址,段表地址寄存器,3.段地址变换,4.段的共享与保护 段的共享是比较容易实现的，只要用户使用相同的段名，在新的段表中填入已在主存中的段的起始地址，并置以适当的读写控制权，就可做到共享一个逻辑上完整的段的信息。,段的共享,分段存储管理系统的保护可采用如下几种措施: (1)在段表中设置一个段长值，以指明该段的长度。当存储访问时，段地址的位移量与段长相比较，如超过段长，便发出越界中断信号。 (2) 建立存取控制,

26、在段表的每个表目中，还增加存取方式项。 (3) 采用存储保护键。 在一个段式存储管理系统中，通过在段表中施加段长、存取控制、设置存储保护键等，可提供一个多级的存储保护体系。,分段与分页的区别与联系 分段与分页的区别 （1）分页的作业地址空间是单一的线性地址空间，而分段作业的地址空间是二维的。 （2）页是信息的物理单位，大小固定。段是信息的逻辑单位，其长度不定。 （3）分页管理是单段式虚拟存储系统，而分段存储管理实现多段式虚拟存储系统。,段式管理的主要优点 （1）便于程序模块化处理和便于处理变换的数据结构。（2）便于动态连接。（3）便于共享分段。（4）可以实现虚拟存储器，使作业的地址空间不受主存

27、容量的限制。 段式管理的主要缺点 （1）和分页管理一样，处理机要为地址变换花费时间；要为表格提供附加的存储空间；这使操作系统复杂化。（2）为满足分段的动态增长和减少外零头，要采用拼接手段。（3）分段的最大尺寸受到主存可用空间的限制。,4.6.4 段页式管理的基本思想 分段结构具有逻辑上清晰的优点，但它的一个致命弱点是每个段必须占据主存储器的连续区域，于是，要装入一个分段时可能要移动已在主存储器中的信息，为了克服这个缺点，可兼用分段和分页的方法，构成段页式存储管理。 每个作业仍按逻辑分段，但对每一段不是按单一的连续整体存放到存储器中，而是把每个段再分成若干个页面，每一段不必占据连续的主存空间，可

28、把它按页存放在不连续的主存块中。,4.6.5 段页式管理的实现原理 1虚地址的构成 一个进程中所包含的具有独立逻辑功能的程序和数据仍被划分为段，并有各自的段号S。把段划成若干个页，和页式系统一样。,段号,页号,页内地址,2 段表和页表 在段页式系统中,每个分段又被分成若干个固定大小的页面，那么每个段又必须建立一张页表把段中的虚页变换成内存中的实际页面。显然，与页式管理时相同，页表中也要有相应的实现缺页中断处理和页面保护等功能表项。 每个段有一个页表，段表中应有专项指出该段所对应页表的页表始址和页表长度。,段表、页表、段表地址寄存器。为了进行地址转换，系统为每个作业建立一个段表，并且要为该作业段

29、表中的每一个段建立一个页表。系统中有一个段表地址寄存器来指出作业的段表起始地址和段表长度。,3.动态地址变换过程 关键问题仍是如何将二维虚地址映射成一维实地址，为了实现动态地址变换。 段页式系统必须为每个作业建立一张段表，段表表目中的地址部分指出该段的页表在主存的始址。 为每个段建立一张页表，每个表目指示该页所在主存的页面号。 每个作业有一个段表地址寄存器，指示它的段表所在位置和段表长度。 设置快速联想寄存器，存放当前最常用的段号S，页号P和对应的内存页面与其它控制用栏目。, 查找方法:如果所访问的段或页在快速联想寄存器中，则系统不再访问内存中的段表、页表。把快速联想寄存器中的值与页内相对地址

30、D拼接起来得到内存地址。若快速联想寄存器中没有，才去通过段表、页表进行内存地址查找。,慢速地址转换过程,若运行进程访问虚地址v=(s,p,d)，在没有联想寄存器的情况下，地址变换过程如下： （1）由段表控制寄存器确定段表在主存中的位置。 （2）将虚地址中的段号和控制寄存器中的段表大小比较，以确保其访问的有效性。 （3）硬件地址转换机构根据虚地址中的段号S，得到欲访问段在该作业的段表中的表目。并验证存取权限，然后，检查分段存在标识(判状态位)，如果访问的段在主存，则通过段表找到该段的页表存放地址，再根据虚地址中的页号P查页表，找到该页所对应的内存块号与虚地址中的页内地址d相加形成物理地址；若访问

31、的分段不在主存，则由硬件产生缺段中断。操作系统对缺页中断响应后，必须重新构造其页表，并装入一页或多个所需的页面。,段页式地址转换需要访问主存次数 要是段表和页表全在主存的话，那么，要得到访问主存的物理地址，就需要访问主存两次。一次是访问段表，以段号为索引找到页表所在位置。另一次是访问页表，以页号为索引找到该页所在的存储块号。然后，把存储块号和虚地址中的位移量相加形成所需要访问的主存单元物理地址。,段页式存储管理的优缺点 优点 （1）它提供了大量的虚拟存储空间。 （2）能有效地利用主存，为组织多道程序运行提供了方便。 缺点 （1）增加了硬件成本、系统的复杂性和管理上的开消。 （2）存在着系统发生抖动的危险。 （3）存在着内碎片。 （4）还有各种表格要占用主存空间。 段页式存储管理技术对当前的大、中型计算机系统来说，算是最通用、最灵活的一种方案。,本章小结,小结,小结,外存、内 存统一管 理的虚存,