操作系统2002--存储管理(1).ppt

基本概念单个分区的存储管理多个分区的存储管理分页式存储管理分段式存储管理虚拟存储管理,存储管理,一、基本概念,内存储器（简称内存、主存、物理存储器）处理机能直接访问的存储器。用来存放系统和用户的程序和数据，其特点是存取速度快，存储方式是以新换旧，断电信息丢失。外存储器（简称外存、辅助存储器）处理机不能直接访问的存储器。用来存放用户的各种信息，存取速度相对内存而言要慢得多，但它可用来长期保存用户信息。在文件系统中介绍。,存储器分类,指导思想：利用辅存（如磁盘、磁带等）提供的大容量存储空间，存放准备运行的程序和数据，当需要时或主存空间允许时，随时将它们读入主存储器。,信息的二级存储,CPU,主存,辅存磁盘磁带,存储器的层次结构,通用寄存器,高速缓存,主存,硬盘,大容量存储器,存储容量增大,单位容量的价格增加,存储管理,内存的物理组织,物理地址：把内存分成若干个大小相等的存储单元，每个单元给一个编号，这个编号称为内存地址（物理地址、绝对地址、实地址），存储单元占8位，称作字节（byte）。物理地址空间：物理地址的集合称为物理地址空间（主存地址空间），它是一个一维的线性空间。,程序的逻辑结构,程序地址：用户编程序时所用的地址（或称逻辑地址、虚地址），基本单位可与内存的基本单位相同，也可以不相同。程序地址空间（逻辑地址空间、虚地址空间）:用户的程序地址的集合称为逻辑地址空间，它的编址总是从0开始的，可以是一维线性空间，也可以是多维空间。,存储管理的功能,主存空间的分配和回收：一个有效的存储分配机制，应在用户提出需求时提供快速响应，为之分配相应的的存储空间；在用户作业不再需要它时，及时回收，以供其它用户使用,地址转换：存储管理必须能够配合硬件完成用户程序中所使用的逻辑地址到程序实际执行时所使用的物理地址之间的转换工作，以保证处理器的正确执行。,主存空间的扩充：借助虚拟存储技术或其它交换技术，达到在逻辑上扩充主存容量，亦即为用户提供主存物理空间大得多的地址空间，以至使得用户感觉他的作业是在这样一个大的存储器中运行。,主存空间的共享和保护：共享主存指的是多个作业共同使用主存中的某个区域，以提高主存利用率。主存的保护指的是确保多道程序都能在各自分配到的主存区域内工作，互不干扰，防止一道程序破坏其它作业的信息，特别要防止破坏系统程序。,重定位,绝对地址：主存中每个物理存储单元的编号称为“绝对地址”或“物理地址”，它们可以被存储控制部件所识别。逻辑地址：源程序经编译后得到的目标程序总是以0为起始地址，其它地址都是以此顺序安排下来，都是相对于0这个起始地址的，这种地址称为“逻辑地址”。名空间：我们把再一个用高级语言编写得源程序中由程序员建立得符号名字空间称为“名空间”。,地址空间：把源程序经编译后得到的目标程序所限定的地址范围称为这个程序的“地址空间”。存储空间：主存中一系列物理单元的集合称为存储空间。显然，地址空间是逻辑地址的集合，存储空间是绝对地址或物理地址的集合，一个是逻辑的概念，一个是物理的实体。,重定位：一个作业的逻辑地址向物理地址的转换，称为重定位（也称为地址映射）。编程或编译时确定地址映射关系：编程时确定虚实地址的关系是指在用机器指令编程时，程序员直接按物理内存地址编程，这种程序在系统中是不能做任何移动的，否则就会出错。静态重定位：地址变换过程发生在程序装入时，且由重定位装入程序完成。采用这种重定位方式时，系统的存储分配只能采用静态分配策略。动态重定位：地址变换过程发生在程序执行过程中访问每条指令和数据时连续进行，且由硬件重定位机构来实现。采用这种重定位方式时，系统的存储分配可以采用动态分配策略。,LOAD1,500,12345,LOAD1,5500,12345,0,100,500,700,0,5000,5100,5500,5700,静态重定位,动态重定位,在装入作业时，不进行地址转换，而是直接把作业装入到分配的主存区域中。在作业执行过程中，每当执行一条指令时，都由硬件的地址转换机构将指令中的逻辑地址转换成物理地址，地址转换工作是在作业执行时完成的。,存储保护,在多道程序设计的环境下，系统中有系统程序和多个用户程序同时存在，如何保证用户程序不破坏系统程序，用户程序之间不相互干扰？这就是存储保护所要解决的问题常用的存储保护有两种：上、下界寄存器保护基址、限长寄存器保护,上下界寄存器保护,下界寄存器存放程序装入内存后的开始地址（首址）上界寄存器存放程序装入内存后的末地址判别式：下界寄存器物理地址上界寄存器,例题：有一程序装入内存的首地址是500，末地址是1500，访问内存的逻辑地址是500、345、1000。下界寄存器：500上界寄存器：1500逻辑地址装入内存的首地物理地址,1、5005001000500100015002、34550084550084515003、1000500150050015001500,二、一个分区的存储管理,采用静态分配和静态重定位方式。,OS常住部分,用户程序,空闲区,fence,覆盖,所谓覆盖是指一个作业的若干程序段（或数据段）间或几个作业的某些部分间共享某主存空间。覆盖技术要求程序员提供一个清楚的覆盖结构，即程序员要把一个程序划分成不同的程序段，并规定好它们的执行和覆盖的次序。操作系统则根据程序员提供的覆盖结构，完成程序段之间的覆盖。,A（20k）,C（30k）,F（30k）,程序结构,B（50k）,D（20k）,E（40k）,0,20k,50k,70k,90k,100k,A,B,C,D,E,F,0,20k,20k,70k,70k,100k,20k,50k,50k,70k,50k,90k,程序的覆盖结构,交换,交换方式是由操作系统把那些在内存中处于等待状态的进程换出内存，而把那些处于就绪状态的进程换入内存,操作系统,用户区,进程P1,进程P2,换出,换入,三、多个分区的存储管理,固定分区,固定分区管理方式是预先把可分配的主存空间分割成若干个连续区域，每个区域的大小可以相同，也可以不同。一旦分好，则每个分区的大小固定，不再变化，且分区的个数也不再改变。,固定分区可变分区可重定位分区,作业1,作业2,作业3,操作系统,分区1,分区2,分区3,CPU,当前运行作业所在分区,2,b,c,上限寄存器,下限寄存器,a,b,c,d,OS常住部分,J1,J2,J3,0,32k,48k,16k,80k,144k,256k,32k,64k,112k,固定分区顺序分配的算法流程,是,查看分区表的第I个表目,已分配？,分区长度xk,I为分区表最后一个表目,置表目中状态位为1,装入作业J,无法分配，作业J等待,是,作业J申请xk主存,否,是,否,I=0,I=I+1,否,地址转换：可采用静态重定位方式,存储保护措施：,CPU,下界,上界,内存,寻址错,寻址错,地址,是,是,否,否,采用固定分区方式的问题：主存利用率不高。改进的方法：划分分区时按分区的大小顺序排列。根据经常出现的作业的大小和频率划分分区。按作业对主存的需求量排成多个作业。,可变分区,所谓可变分区是指，系统并不预先划分几个固定分区。分区的建立是在作业的处理过程中进行的，其大小随作业的主存需求量而决定。在这种管理方式下，系统中任一时刻分区的大小及个数，都是不固定而可改变的。,可变分区管理的数据结构,操作系统,J1,J3,400k,0,1000k,2000k,2300k,2560k,已分配区表,空闲区表,分区的分配算法,最优适应算法：将空闲分区按其存储空间的大小，从小到大顺序组成链。每次查找从链首开始，第一个满足要求的空闲分区将被分配最坏适应算法：空闲分区按其空间大小，从大到小组成链。每次查找从链首开始，第一个满足要求的空闲分区将被分配最先适应算法：空闲分区按其在存储空间中的地址，以递增顺序组成链。每次查找从链首开始，第一个满足要求的空闲分区将被分配下次适应算法：是最先适应算法的一种改进。空闲分区的链接顺序同最先适应算法，但它是一个循环链。每次为存储请求查找合适的空闲分区时，总是从上次查找结束的地方开始。,空闲分区1,空闲分区2,free,空闲分区n,按分区的大小从小到大链接,空闲分区1,空闲分区2,free,空闲分区n,按分区的大小从大到小链接,最优适应算法,最坏适应算法,空闲分区1,空闲分区2,free,空闲分区n,按分区的地址从低到高链接,空闲分区1,空闲分区2,free,空闲分区n,按分区的地址从低到高链接,最先适应算法,下次适应算法,分区的回收,a回收区下面邻接空闲区,b回收区上面邻接空闲区,c回收区上、下邻接空闲区,d回收区不邻接任何空闲区,回收区,使用区,空闲区,地址转换：一般可采用动态重定位方式，基址寄存器的内容加上逻辑地址（相对地址）就可得到绝对地址（物理地址）。,存储保护：将逻辑地址（相对地址）与限长寄存器的内容进行比较，如逻辑地址（相对地址）大于限长寄存器的值，表明地址越界。,例题：在可变分区管理中，有那些分区分配算法？各有何优缺点？最优适应算法空闲分区按空间大小的顺序从小到大链接在一起。系统在查找空闲分区时，总是从最小的一个开始。其实质是，在系统中寻找与要求大小最接近的空闲分区。优点：如果存在有在正好满足所要求大小的空闲分区，则必然被选中，或者只对比要求稍大的空闲分区进行划分，而绝不会划分一个更大的空闲分区。缺点：寻找一个较大空闲区时花费的时间较多；回收时把回收的空闲区插入到链中合适的位置较为费时；系统中，小的空闲区较多。最坏适应算法空闲分区按空间大小的顺序从大到小链接在一起。系统在查找空闲分区时，总是从最大的一个开始。优点：克服了最优适应算法留下许多小的碎片的不足缺点：保留大的空闲区的可能性减小了，而且分区的回收也和最优适应算法一样复杂。,最先适应算法空闲分区按其在内存中位置的顺序从低地址到高地址链接在一起，即每个后继空闲区的起始地址总是比前面的大。系统在查找空闲分区时，按照空闲区的链的顺序，依次查询，直到找到第一个满足要求的空闲区为止。其实质是，尽可能利用存储器的低地址部分，尽量保存高地址部分的空闲区。优点：当需要一个较大的分区时，容易得到满足。缺点：在回收一个分区时，需要花费较多的时间查找链表，以确定插入位置。下次适应算法空闲分区按其在内存中位置的顺序从低地址到高地址链接在一起，与最先适应算法不同的是，每次查找都是从上次查找结束的位置开始。其实质是，空闲分区可以比较均匀的分布在内存中。缺点：寻找一个较大空闲区时花费的时间较多；回收时把回收的空闲区插入到链中合适的位置较为费时。,例题：对下图所示的分区分配情况（其中，阴影部分表示已占用分区，空白部分表示空闲分区），若要申请一块40KB的分区：,对于最优适应分配算法得到的空闲分区的首地址是：A、110KBB、190BKC、330BKD、410BK若要使被分配得到的空闲分区的首地址最大，则应采取的分配策略是：A、最先适应分配算法B、最优适应分配算法C、最坏适应分配算法D、单一连续区的分配算法,100KB,0KB,100KB,80KB,10KB,90KB,50KB,60KB,100KB,180KB,190KB,280KB,330KB,390KB,20KB,101KB,410KB,511KB,60KB,FREE,80KB,90KB,101KB,最优适应分配算法得到的空闲分区的首地址为330KB,申请一块40KB的分区,可见，只有采用最坏分配算法时，得到的首地址最大，为410KB。答案为C。,采用多重分区的管理方法能够实现主存的共享。所谓多重分区技术指的是系统中设置了多对（一般不超过34对）界地址寄存器，并且在为每个作业分配主存时，可按界地址寄存器对的个数分配多个不相邻接的空闲分区。,在共享主存空间时，每个作业即可访问自己所在的分区，也可访问公共区域。但应注意，对公共区域的访问是受限的。一般地说，使用共享信息（即访问公共区域）只能采用“读”或“执行”的方式。,可重定位分区,为了消除外部零头，进一步提高主存的利用率，定时的（或在主存空间紧张时）把主存中的作业“搬家”，集中在主存的一端，另一端就将产生一个较大的空闲区。这种技术称为存储器的“紧缩”（或称移动）。采用了紧缩技术的多个分区的管理方法就是可重定位分区管理方法。,采用紧缩（移动）技术时应注意的问题：1、移动会增加系统的开销2、移动是有条件的,采用移动技术时应尽量减少移动的作业数和信息量。,一种可行的方法：改变作业装入主存的方式,当作业J1完成后，它所占的分区成为空闲区，这样，主存中就有两个空闲区。若有新作业J5进入系统，要求的内存容量大于任何一个空闲区，但不超过两个空闲区之和。此时需移动作业，以将两个空闲区合并为一个较大的空闲区。,四、页式存储管理,1、问题的提出,分区存储管理的主要问题是碎片问题。在采用分区存储管理的系统中，会形成一些非常小的分区，最终这些非常小的分区不能被系统中的任何用户（程序）利用而浪费。造成这样问题的主要原因是用户程序装入内存时是整体装入的，为解决这个问题，提出了分页存储管理技术。,2、基本原理,所谓分页，就是把主存存储空间按大小一定的块划分，称为物理块、或页框（pageframe），同时，按同样的尺寸去划分作业的地址空间，形成一个个相等的页面，称为逻辑页或虚页。为了便于利用硬件进行地址的转换工作，页面大小通常是2的幂次方，分页的过程对用户是透明的。,0,1,2,3,4,5,6,0,1,2,3,4,5,6,作业的地址空间,页表,主存中的物理块,分页存储管理的基本做法：,（1）等分主存：把主存划分成相同大小的存储块，成为块（或称为页架）。对特定计算机，块的大小通常是固定不变的。,（2）用户逻辑地址的分页：把用户的逻辑地址空间（虚拟地址空间）划分成若干个与块大小相同的部分（称为页），并依次编号。,（3）逻辑地址表示：一般从基地址“0”开始编址（相对地址）。每个相对地址用一对数字（p,d）表示，其中p是页号，d是页内位移。,如用A表示相对地址，页面大小为L，则,（4）主存分配原则：系统以块为单位把主存分给作业或进程（它们不一定是相邻和连续的）。,（5）页表：系统为每个进程设立一个页面映象表（简称页表），使页和块建立的一一对应的关系。,页表应包括如下信息：,页号块号：指页面装入系统的第几号块状态：表示该页是否在主存中（以IBM4300为例：断开、连接、可寻址）另外还可能有的其它信息：修改位（修改过否）、访问位（有几个进程访问）、引用位（最近被引用过否）、外存地址等。,（6）分页系统中的地址结构：通常将地址域分成两部分，一部分表示地址所在的页号，另一部分表示页内地址。至于它们各占几位，则主要取决于页的大小。,（7）页面尺寸应是2的幂：目的在于不经运算即可得到p和d。,例子：假定页的大小为1KB，指令的地址域长度为16位，则逻辑地址4101的页号、页内地址可以这样来确定：,逻辑地址,的机内表示形式为：,00,01,00,01,1514,1312,1110,98,76,54,32,10,00,00,00,01,可立即得到页号为4，页内地址为5,两级和多级页表：现代大多数计算机系统，都支持非常大的逻辑地址空间。在这样的环境下，页表就会变得非常大，本身就要占用非常大的内存空间。,页面大小的选择：页面大小一般是由机器的地址结构所决定的，亦即由硬件决定的。页面的大小通常在,之间，即在512字节到4KB之间。目前常见的几种计算机中所选用的页面大小如下所示：,解决的办法：1、对页表所需的内存空间，采用离散的分配办法；2、只将当前需要的部分表项调入内存。,两级页表的逻辑地址结构：,两级页表结构：,具有两级页表的地址变换机构,对于具有更大存储容量的计算机系统，可能需要采用同样的原理建立更多级的页表,3、存储空间的分配和回收,对于存储空间的管理，最简单的办法是建立一张“位示图”，其中每一位对应一个物理块，用1和0分别表示对应的物理块已占用或空闲。另外再增加一个字节记录当前系统中空闲块的总数。假定主存有256个物理块，则可用字长为32位的8个字作为位示图：,在进行物理块的分配时，可按下述公式计算物理块的块号：,块号=字号字长+位号,在进行物理块的回收时，假定被回收的物理块的块号为i，则在位示图中的对应位置为：,字号=i/字长位号=imod字长,4、地址转换,将得到的逻辑地址分成两个部分：页号和页内地址；根据页号查找页表，得到对应的物理块号；根据得到的物理块号和页内地址，计算出实际的物理地址（绝对地址）,例题：,在采用页式存储管理的系统中，某作业J的逻辑地址空间为4页（每页2048字节），且已知该作业的页面映像表如下图。试借助地址变换图（即要求画出地址变换图）求出有效逻辑地址4865所对应的物理地址。,控制寄存器,4865-2，764物理地址：6204876413057,需要考虑的问题：,1、页表放在哪里？多数的系统是在系统表格区专门开辟一个集中的页表空间。在建立页表之前先向系统请求分配页表空间。2、对系统性能有何不利影响？由于CPU存取一次数据至少要访问两次内存（间接寻址对内存的访问多于两次），因此计算机存取内存信息的时间至少比原来多了一倍。,地址变换过程为：,在CPU给出地址变换机构后，由地址变换机构自动地将页号p送入快表，并将此页号与快表中的所有页号同时进行比较。若其中由与此相匹配的页号，则