《实存储管理技术》PPT课件.ppt

第7章实存储管理技术,引言71存储管理的基本概念72连续分配存储管理方式73离散分配存储管理方式,引言,存储器是一种最重要的计算机资源，内存管理一直是操作系统最主要的功能之一。早期的存储器价格比较昂贵，内存容量有限。尽管现在个人计算机的存储容量已经是60年代早期最大的计算机IBM7094的存储容量的数百倍以上，但是程序的大小也是原来的数百倍以上，正如Parkinson定律所说：“存储器有多大，程序就会有多大”。因此，内存容量一直是计算机硬件资源中最关键而又最紧张的“瓶颈”资源。特别是在多道程序设计技术出现以后，对存储管理提出了更高的要求。一方面要使内存得到充分、有效的利用；另一方面又要为用户提供安全、方便的使用环境。这是操作系统必须解决的问题。存储器管理技术可分为两大类：实存储器管理和虚拟存储器管理。本章研究常用的实存储管理技术，第八章研究虚拟存储管理技术。,71存储管理的基本概念,存储管理的主要对象是内存。对存储器管理不当，不但直接影响到存储器的利用率，而且会对系统性能产生严重影响。本节介绍存储管理需要解决的问题，存储管理方式等。,711存储管理要解决的问题,存储分配：这是存储管理要研究的主要内容，也是本章讨论的重点。在本章中将研究各种内存分配算法，以及每种算法所要求的数据结构。地址映射：研究各种地址变换机构，以及静态和动态重定位方法。存储保护：研究如何确保每道程序都在自己的内存空间运行，互不干扰；研究如何保护各程序区中信息不被破坏和偷窃。内存扩充：内存扩充研究的是如何从逻辑上扩充内存，而不是从物理上扩充内存。为了实现内存的逻辑扩充，我们采用虚拟存储管理技术，这将在第八章进行讨论。,712存储管理的分类,连续分配方式：连续分配方式是指系统为一个用户程序分配一个连续的存储空间。这种分配方式曾被广泛应用于6070年代的操作系统中，今天仍有它的一席之地。连续分配主要有两种：单一连续分配方式：这种存储管理方式把内存划分成系统区和用户区两个分区，用户区仅被一个用户所独占。例如MS-DOS就是采用的单一连续分区管理方式。分区式分配方式：这种存储分配方式适用于多道程序的存储管理，可以分为固定分区式和可变分区式。固定分区式是将内存的用户区预先划分成若干个固定大小的区域，每个区域中驻留一道程序。可变分区式是根据用户程序的大小，动态地对内存进行划分，所以每个分区的大小不是固定的，分区数目也不是固定的。可变分区式显著地提高了存储器的利用率。,712存储管理的分类,离散分配方式：为了进一步提高内存的利用率，提高进程的并发粒度，引入了离散分配方式。它将一个用户进程离散地分配到内存中多个互不邻接的区域。离散分配方式有以下三种：分页存储管理方式：在这种存储管理方式中，用户地址被划分成若干大小相等的区域，称为页或页面；而内存空间也相应地划分成若干个物理块，页和块的大小相等。这样，就可以将用户程序离散地分配到内存中的任意一块中，从而实现内存的离散分配，这时内存中的碎片不会超过一页。,712存储管理的分类,分段存储管理方式：这种管理方式是从逻辑关系考虑，把用户地址空间分成若干个大小不等的段，每段可以定义一个相对完整的逻辑信息。在进行内存分配时，以段为单位，段与段之间在内存中可以不相邻接，实现离散分配。段页式存储管理方式：这是分页和分段存储管理方式的结合，即将用户程序分成若干个段，再把每一段分成若干个页，相应地将内存空间划分成若干物理块，页和块的大小相等，将页装入块中。这种存储管理方式不但提高了内存的利用率，而且又能满足用户的要求。,712存储管理的分类,虚拟存储管理系统：为了进一步提高内存的利用率，实现从逻辑上扩充内存的功能，引入了虚拟存储管理系统，虚拟存储管理系统有三种：请求分页系统：请求分页系统是在分页系统的基础上，增加了请求调页功能和页面置换功能所形成的分页式虚拟存储系统。它只把用户程序的部分页面（而非全部页）装入内存，就可以启动运行，以后再通过请求调页功能和页面置换功能，陆续把将要运行的页面调入内存，同时把暂不运行的页面置换到外存上，置换时以页面为单位。,712存储管理的分类,请求分段系统：请求分段系统是在分段系统的基础上，增加了请求调段功能和分段置换功能所形成的分段式虚拟存储系统。它只把用户程序的部分段（而非全部段）装入内存，就可以启动运行，以后再通过请求调段功能和置换功能将不运行的段调出，同时调入将要运行的段，置换时以段为单位。请求段页系统：请求段页系统是在段页式系统的基础上，增加了请求调页功能和页面置换功能所形成的段页式虚拟存储系统。,713地址重定位,地址空间和存储空间：名字空间：程序中由符号名组成的空间称为“名字空间”。相对地址：也称逻辑地址或虚地址。源程序经过汇编或编译后再经过链接装配，加工形成程序的装配模块形式，它是以“0”为基址顺序进行编址的。相对地址空间：相对地址的集合称为相对地址空间，或简称为地址空间。绝对地址：相对地址经地址重定位机构转换到内存中的地址，称为绝对地址，或称物理地址。绝对地址空间：相对地址空间通过地址重定位机构转换到绝对地址空间，绝对地址空间也叫物理地址空间，或称为存储空间。,713地址重定位,名字空间、地址空间和存储空间的关系如下图所示：,713地址重定位,地址重定位：一个逻辑地址空间的程序装入到物理地址空间时，由于两个空间不一致，就需要进行地址变换，或称地址映射，即地址重定位。地址重定位有两种方式：静态重定位和动态重定位。静态重定位：静态重定位是在程序执行之前进行重定位。它根据装配模块将要装入的内存起始地址，直接修改装配模块中的有关地址的指令，这一工作通常是由装配程序完成的。,713地址重定位,静态重定位示意图：静态重定位如下图所示：,713地址重定位,静态重定位示例：如上图所示，以“0”为参考地址的装配模块，要装入以2000为起始地址的存储空间。为使程序装入后能正确运行，程序在装入之前，必须对有关地址的指令进行一些修改。例如：程序中LOAD1，450这条指令是把相对地址为450的存储单元的内容3500装入1号累加器，而这时内容为3500的存储单元的实际物理地址为2450（起始地址2000+相对地址450），所以LOAD1，450这条指令中的直接地址码要作相应的修改，即改为LOAD1，2450。,713地址重定位,静态重定位的优点：静态重定位的优点是容易实现，无须硬件的支持，它只要求程序本身是可重定位的，即对那些要修改的地址部分具有某种标识。静态重定位的缺点：（1）程序在地址重定位后就不能在内存中移动了，因而不能重新分配内存，不利于内存的有效利用。（2）要求程序的存储空间必须是连续的，不能分布在内存的不同区域。（3）不利于内存的共享，若干用户如若共享同一程序，则各用户必须使用自己的副本。,713地址重定位,动态重定位：动态重定位是在程序执行期间，在每次存储访问之前进行的。动态重定位需要硬件的支持，这个硬件就是重定位寄存器。重定位寄存器的内容是程序装入内存区的起始地址减去目标模块的相对基地址。重定位时，对每一个有效地址都要加上重定位寄存器中的内容，以形成存储空间的地址，即绝对地址。,713地址重定位,动态重定位示意图：动态重定位如下图所示：,713地址重定位,动态重定位示例：程序的目标模块在装入内存时，与地址有关的指令都无需进行修改，如地址空间中的指令LOAD1，450在装入后仍保持相对地址450。当该模块被操作系统调度到处理器上执行时，操作系统首先把该模块装入的起始地址减去目标模块的相对基地址，然后将其差值装入重定位寄存器。当处理器取一条访问内存的指令时，地址变换硬件机构自动将指令中的相对地址与重定位寄存器中的内容相加，把所得结果作为内存的绝对地址去访问该单元的数据。此外还应增设一个界限寄存器，用于防止程序使用的地址超过程序的界限。,713地址重定位,动态重定位的优点：（1）在程序的执行过程中，用户程序在内存中可以移动，因而可以重新分配内存，有利于内存的充分利用。（2）程序不必连续存放在内存中，可以分散在内存的若干个不同区域，这只需增加几对基址限长寄存器，每对寄存器对应一个区域。（3）若干用户可以共享同一程序。动态重定位的缺点：动态重定位的缺点是需要附加硬件支持，实现存储管理的软件算法比较复杂。,72连续分配存储管理方式,连续分区存储管理方式广泛应用于6070年代的操作系统中，至今仍占有一席之地。本节主要讲述单一连续分配、固定分区分配和可变分区分配等方案。,用户区,721单一连续分配方式,在早期的计算机及某些小型、微型计算机系统中，没有采用多道程序设计技术，采用的是单用户、单任务的操作系统（如MS-DOS、CP/M等），使用计算机的用户占用了全部计算机资源。这时的存储管理方案采用的是单一连续分配方案。,系统区,分区方法：在这一存储管理方案中，内存分为两个区域，如右图所示：系统区：这一区域仅供操作系统使用，通常驻留在内存的低段。用户区：除系统区之外的全部内存空间，提供给用户使用。,721单一连续分配方式,存储保护：对于单一连续分配方式，为了实现存储保护，防止操作系统受到有意或无意的破坏，需要设置界限寄存器。如果CPU处于用户态工作方式，则对于每一次访问，需检查其逻辑地址是否大于界限寄存器的值，如果大于界限寄存器的值，则表示已经越界，出现了用户程序对操作系统区域的访问，便产生中断，并将控制转给操作系统。如果CPU处于核心态工作方式，此时可以访问操作系统区域。单一连续分配方式的优点：方法简单，易于实现。单一连续分配方式的缺点：仅适用于单道程序，不能使处理器和内存得到充分利用。,722固定分区存储管理方式,固定分区分配方式是最早使用的一种能应用于多道程序设计的存储管理方式，其基本思想是在系统生成时就将内存按一定规则划分成若干个分区，每个分区的大小可以不等，但事先必须固定，在系统运行过程中不能改变。在每一个分区内装入一个进程，这样，把内存划分成几个分区，便允许几道作业并发执行。当有空闲分区时，可从外存的后备队列中，选择一个适当大小的作业装入该分区。,722固定分区存储管理方式,分区划分方法：分区大小相等：把内存等分成若干份，所有分区的大小都是相等的。这种分区方法不适宜于程序大小不等的情况。当程序太小时，会造成内存空间的浪费；而当程序太大时，可能由于分区太小而无法装入。尽管这种分区方法存在着很多缺点，但在一些地方仍被采用，主要用于利用一台计算机控制多个相同对象的场合。例如，炉温控制系统是利用一台计算机去控制多台相同的冶炼炉。分区大小不等：为了克服分区大小相等分配方法的缺点，可以根据一定的规则，在内存中划分成多个大小不等的分区，为小的程序分配小分区，中等程序分配中等分区，大程序分配大分区。,722固定分区存储管理方式,数据结构：在固定分区分配方式下，操作系统的存储分配模块和存储回收模块都要用到内存分区情况的说明信息，以及这些存储区的使用状况信息。为此，系统中设置了一张分区说明表，包含三项信息：大小：指该分区的大小；始址：指该分区在内存中的起始位置；状态：表明该分区是否已被使用。内存分配：当有一用户程序需要装入时，由内存分配程序检索分区说明表，按照一定的算法找出一个能够满足要求的、尚未使用的分区分配给该程序，同时修改分区说明表中该分区表项中的状态。如果找不到大小足够的分区，则拒绝为该用户程序分配内存，如下图所示：,722固定分区存储管理方式,分区说明表,722固定分区存储管理方式,固定分区的优缺点：优点：简单，所需硬件支持只是一对界地址寄存器，软件算法也很简单。缺点：存在较多的内零头，内存利用率不高。,723可变分区存储管理方式,可变分区是指内存事先并没有划分成分区，而是在作业进入内存时，操作系统按照作业的大小从内存中划分出一个分区分配给作业使用。分区的大小和分区的个数都是可变的，是根据作业的大小和数量动态地划分。在实现可变分区存储管理方式时，必须解决下述四个问题：分区分配中所使用的数据结构；分区的分配算法；分区的回收操作；存储保护问题。,723可变分区存储管理方式,数据结构：可变分区存储管理中各功能模块要用的数据结构可以有以下几种组织方式：分区说明表：这种方法类似于固定分区中的分区说明表结构，已使用分区和空闲分区都集中在一个表中，但这种表存在两个缺点：由于分区数量是不断变化的，所以表的长度不好确定，造成表格管理上的困难。如果给该表预留的空间不够，则无法登记各分区的情况。如果预留的空间过大，又会造成浪费。在为作业分配内存时，由于整个表的长度增加了，为查找一块合适的空闲分区，所需扫描的表目增加，查找速度变慢。,723可变分区存储管理方式,空闲分区表FBT和已使用分区表UBT：分别设置两个表格，一个是空闲分区表FBT，另一个是已使用分区表UBT，分别用来登记系统中的空闲分区和已使用分区。这样可以减少存储分配和释放时查找表格的长度，提高查找速度。下表是这两种表格的示意图。,723可变分区存储管理方式,空闲分区链：上述表格的语言表示一般可用数组。但对空闲分区的管理中，通常广泛使用链表把所有的空闲分区链接在一起，构成一个空闲分区链。具体做法是：在每一分区的起始部分设置一前向指针；在分区尾部设置一后向指针通过前后向指针把所有的空闲分区链接成一个双向链。为了检索空闲分区方便起见，在分区尾部重复设置状态位和分区大小表目，当分区分配出去以后，把状态位由“0”改为“1”，空闲分区链如下图所示：,723可变分区存储管理方式,723可变分区存储管理方式,分区分配算法：在可变分区存储管理方式中，需按照一定的分配算法，分配空闲区给作业，目前常用的方法有以下四种：最先适应分配算法：这种算法按分区序号从空闲分区表的第一个表目开始查找该表，把最先找到的大于或等于作业大小的空闲分区分给要求的作业。然后，再按照作业的大小，从该分区中划出一块内存空间分配给作业，余下的空闲分区仍留在空闲分区表中。如果查找到分区表的最后仍没有找到大于或等于该作业的空闲区，则此次分配失败。优点：优先利用内存中低址部分的空闲分区，而高址部分的空闲分区很少被利用，从而保留了高址部分的大空闲区。为以后到达的大作业分配大的内存空间创造了条件。缺点：低址部分不断被划分，致使留下许多难以利用的、很小的空闲分区。,723可变分区存储管理方式,循环最先适应分配算法：这种算法是由最先适应分配算法经过改进而形成的。在为作业分配内存时，不再每次从空闲分区表的第一个表项开始查找，而是从上次找到的空闲区的下一个空闲区开始查找，直至找到第一个能满足要求的空闲区为止，并从中划分出一块与请求大小相等的内存空间分配给作业。为实现该算法，应设置一起始查找指针，以指示下一次开始查找的空闲分区，并采用循环查找方式。即如果最后一个空闲分区的大小仍不能满足要求，则返回到第一个空闲分区进行查找。优点：内存中的空闲区分布得更均匀，减少查找空闲分区的开销。缺点：系统中缺乏大的空闲分区，对大作业不利。,723可变分区存储管理方式,最佳适应分配算法：该算法从所有未分配的分区中挑选一个最接近作业大小且大于或等于作业的空闲分区分配给作业，目的是使每次分配后剩余的碎片最小。为了查找到大小最合适的空闲分区，需要查遍整个空闲分区表，从而增加了查找时间。因此，为了加快查找速度，要求将所有的空闲分区，按从小到大递增的顺序进行排序。这样，第一次找到的满足要求的空闲分区，必然是最佳的。缺点：每次分配之后形成的剩余部分，却是一些小的碎片，不能被别的作业利用。因此，该算法的内存利用率是不高的。,723可变分区存储管理方式,最坏适应分配算法：该算法从所有未分配的分区中挑选一个最大的空闲分区分配给作业，目的是使分配后剩余的空闲分区足够大，可以被别的作业使用。为了查找到最大的空闲分区，需要查遍整个空闲分区表，从而增加了查找时间。因此，为了加快查找速度，要求将所有的空闲分区按从大到小递减的顺序进行排序。这样，第一次找到的空闲分区，必然是最大的。优点：最坏适应分配算法在分配后剩余的空闲分区可能比较大，仍能满足一般作业的要求，可供以后使用。从而最大程度地减少系统中不可利用的碎片。缺点：这种算法使系统中的各空闲分区比较均匀地减小，工作一段时间以后，就不能满足对较大空闲分区的分配要求。,723可变分区存储管理方式,分区的回收：当一个作业运行完毕释放内存时，系统根据回收区的首地址，在空闲分区表中找到相应的插入点，此时可能出现下述四种情况之一。（其中F1、F2表示回收区前后的空闲区）：,723可变分区存储管理方式,回收区既不与F1相邻，也不与F2相邻（如上图(a)所示），应为回收区建立一项新表目，填写回收区的始址和大小，并根据其起址和大小，插入到空闲分区表的适当位置；回收区只与插入点的前一个空闲分区F1相邻时（如上图(b)所示），此时将两个分区合并为一个新的空闲分区，不再为回收区分配新表项，只需修改F1的大小，新回收区的大小为F1与回收区的大小之和；回收区只与插入点的后一个分区F2相邻时（如上图(c)所示），此时将两个分区合并为一个新的空闲分区，修改F2表目的内容，以回收区的始址作为新空闲区的始址，以回收区与F2的大小之和作为新空闲区的大小。,723可变分区存储管理方式,回收区与插入点的前、后两个分区F1和F2都相邻时（如上图(d)所示），此时以F1的表目作为新空闲区的表目，F1的始址作为新空闲区的始址，以F1、回收区、F2的大小之和作为新空闲区的大小，删除F2表目。,723可变分区存储管理方式,存储保护：为了防止一个作业有意或无意地破坏操作系统或别的作业，应对分区采取保护措施。可变分区存储管理方式的存储保护一般采用两种方法：界地址法：系统设置一对上、下界寄存器，当选中某个作业运行时，将作业的界地址装入这对寄存器中，作业运行时所形成的每一个访问存储器的地址都要同这两个寄存器的内容进行比较，若超过寄存器中的界限，则产生越界中断。如下图(a)所示，作业所在分区是120KB180KB，作业装入时，将其上界地址寄存器置为120KB，下界地址寄存器置为180KB。作业访问一个存储器地址D时，要把地址D与上、下界寄存器的内容进行比较，如果满足120KBD180KB,则访问是合法的，如果超出这一范围，则产生越界中断。,723可变分区存储管理方式,也可以使用一对基址、限长寄存器，原理也是相同的，此时基址寄存器还起着重定位寄存器的作用。如下图(b)所示，把基址寄存器置为120KB，限长寄存器置为60KB。作业访问一个存储器地址D时，把D减去基址寄存器的内容，再与限长寄存器的内容进行比较，如果超出限长，则产生越界中断。,723可变分区存储管理方式,保护键法：系统为每一个存储块都设置了一个单独的保护键，它相当于一把锁。而在作业的程序状态字中设置一个保护键字段，对不同的作业赋予不同的代码，它相当于一把钥匙。当运行作业要访问某个存储器地址时，先要把程序的保护键字段与存储块的保护键进行比较。如果相符，可以进行读写操作；如果不相符，则访问被禁止或只允许进行读操作。当一个作业运行中产生非法访问时，系统将产生保护性中断。可见，保护键法还提供了一种数据共享的方式。,723可变分区存储管理方式,存储器的紧缩和程序的浮动：可变分区存储管理中，由于各作业动态地请求和释放内存分区的结果，会造成内存中存在大量小的，离散分布的碎片。为了解决碎片问题，可以有两种解决方案：解决方案1：把作业分成几部分装入到不同的分区中去，也就是不把一个作业作为一个连续的整体存放在内存中。显然，这种方法可以改变碎片问题，但也带来了程序管理和执行上的复杂性。解决方案2：把内存中的小碎片集中起来，形成一个较大的分区，使之可以装入较大的作业。要进行存储器的紧缩，就要将内存中的程序进行移动。为了解决这个问题，应采用动态重定位技术。一个作业在内存中移动后，只需改变重定位寄存器的内容即可。,723可变分区存储管理方式,程序浮动示意图：,723可变分区存储管理方式,上图（a）表示了内存的分配情况。此时，作业5（400K）需要装入，但系统中已无足够大的空闲分区装入作业5。此时进行程序的浮动，把作业集中到内存的一端，在另一端形成了454KB的空闲分区（如上图（b）所示），作业5便可装入了（如上图（c）所示）。,73离散分配存储管理方式,上一节我们讨论了连续分配存储技术，但使用这种分配技术会造成较多的碎片，降低了内存的利用率。尽管使用存储器的紧缩技术可以把零散的空闲分区集中成较大的分区，提高了内存的利用率。然而，这种内存利用率的提高是以牺牲处理器时间为代价的，使得这一方法并不可取。因此，应打破连续存储的限制，把作业离散地装入存储器中。根据离散分配时所用基本单位的不同，可把离散分配方式分为三种：,73离散分配存储管理方式,分页存储管理：在该方式中，用户程序的地址空间被划分成若干固定大小的区域，称为页。而将存储空间也划分成相应大小的区域，称为物理块。这样，可以将用户程序的任一页放入存储空间的任一物理块中，从而实现了离散存储。分段存储管理：分页存储管理是从提高内存利用率的角度出发而形成的，它没有考虑用户的要求。分段存储管理是为满足用户要求而形成的一种存储管理方式。在这种存储管理方式中，作业的地址空间按照程序的逻辑关系被划分成若干个大小不等的段，每个段定义了一组完整的逻辑信息。在进行存储分配时，以段为单位，这些段在内存中可以不互相邻接，从而实现了离散存储。,73离散分配存储管理方式,段页式存储管理：这是分页和分段存储管理相结合而形成的一种存储管理方式。它综合分页式和分段存储管理的优点，既提高了内存的利用率，又满足了用户的要求，是目前使用较多的一种存储管理方式。,731分页存储管理方式,分页存储管理的基本概念：页面和物理块：在分页存储管理方式中，将一个进程的逻辑地址等分成若干区域，称为页面或页，并给各页从零开始依次编以连续的页号0，1，2，。相应地，将存储空间划分成与页大小相等的若干个存储块，称为（物理）块或页架，并给各块从零开始依次编以连续的块号0，1，2，。由于进程的最后一页经常装不满一块，形成不可利用的碎片，称为“页内碎片”。逻辑地址的表示：进程的逻辑地址一般是从基地址“0”开始连续编址的。在分页系统中，每个逻辑地址用一个数对（p，d）来表示，其中p是页号，d是页内地址。若给定一个逻辑地址A，页面大小为L，则：,731分页存储管理方式,其中INT是向下取整的函数，MOD是取余函数。例如，逻辑地址A是4856B，页面大小L为1024B，根据上式，可得p=4，d=760，表示为（4，760）。,731分页存储管理方式,分页系统中的地址结构：分页系统的地址场分为两部分：一部分表示该地址的页号p，另一部分表示页内地址d，其格式如下图所示。至于页号和页内地址场各占几位，主要取决于页的大小。如页的大小为1KB，则页内地址部分应占10位，即09位，页的大小为2KB时，页内地址部分应占11位，即010位。,731分页存储管理方式,内存分配原则：在分页存储管理中，系统以物理块为单位把内存分给进程，并且分给一个进程的各个物理块不一定是相邻和连续的。进程的一个页面装入系统分给的某个物理块中，所以页面和物理块对应。一个进程的相邻的连续的几个页面，可被装入内存的任意几个物理块中，从而实现了离散存储，如下图所示。,731分页存储管理方式,分页存储管理系统示意图:,0,1,0,1,2,3,作业3,0,1,2,3,4,块号,页号,0,3,1,4,存储空间,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,0,0,1,6,2,9,3,10,0,2,1,5,2,7,3,12,4,14,物理地址空间,逻辑地址空间,页面映射表,作业1,作业2,731分页存储管理方式,页表：系统将进程的每一页离散地分配到内存的多个物理块中，应能保证进程的正确运行，即在内存中能够找到每一页对应的物理块。为此，系统为每一个进程建立了一个页面映射表（PMT表），简称页表，如上图所示。页表至少应包含以下信息：页号：进程各页的序号。物理块号：对应页装入内存的物理块号。每个页在页表中占一个表项，记录该页在内存中的物理块号。进程运行时，通过查找页表，就可以找到每一页在内存中的物理块号。可见，页表的作用是实现从页号到物理块号的地址映射。,731分页存储管理方式,页面大小的选择：在分页系统中页面的大小是由机器的地址结构所决定的，亦即由硬件决定。对于某一种机器只能采用一种大小的页面。页面大小的选择应遵循如下两条原则：若选择的页面较小，可以使内存碎片减小，从而减少了内存碎片的总空间，有利于提高内存的利用率；但另一方面，也会使每个进程的页面数增多，从而导致页表过长，占用大量内存；此外，还会降低页面置换的效率。若选择的页面过大，虽然可以减少页表长度，提高置换效率，但却又会使页内碎片增大。因此，页面的大小应选择的适中，常在29213之间，即在512B8KB之间。,731分页存储管理方式,页面的大小不但应该选择适中，而且应该是2的幂。这是因为在分页系统中，须将逻辑地址转换成页号p和页内地址d才能进行访问。而将逻辑地址转换成页号p和页内地址d须使用除法。而如果每访问一个内存单元都要做一次除法运算，将使系统效率大大下降。而如果页的大小是2的幂，把一个逻辑地址转换成页号p和页内地址d就十分简单了。只要根据页的大小是2的几次幂，就把地址场从第几位截开成两部分，高位部分代表的数表示页号p，低位部分代表的数表示页内地址d。,731分页存储管理方式,【例7-1】：在一分页系统中，页的大小为2KB，试计算逻辑地址2A3CH的页号和页内地址。解：逻辑地址2A3CH=0010101000111100B，其地址场结构如下所示：,页面大小2K=211，所以从第11位（图中虚线处）把地址分成两部分，高位部分为5H，低位部分为23CH，故p=5H，d=23CH。所以，2A3CH（5H，23CH），即2A3CH。,731分页存储管理方式,分页系统中的地址转换：地址转换机构的基本任务是完成逻辑地址到物理地址的转换。由于页内地址和块内地址是一一对应的，所以无须转换。因此，地址转换的任务，只是将逻辑地址中的页号，转换为内存中的物理块号。根据系统中硬件结构的不同，可以有三种地址转换方式：,731分页存储管理方式,直接映象的页地址转换：地址变换机构的地址映象硬件自动按页面大小把逻辑地址截成两部分，页号和页内地址（p，d），在执行检索之前，先将页号与页表长度进行比较，如果页号大于或等于页表长度，则表示此次访问的地址已超出进程的地址空间，于是，这一错误将被系统发现并产生一次地址越界中断。如果没有出现越界中断，加法器将页表始址与页号和页表项长度的乘积相加，得到该页在页表中的表目位置，于是可以得到该面在内存中的物理块号p。然后地址映象硬件又将物理块号p与页内地址拼出实际的内存绝对地址，实现了地址映象。直接映象的页地址转换如下图所示：,731分页存储管理方式,块号,页号,页表,p,p,物理地址,块号p,块内地址d,逻辑地址,页号p,页内地址d,页表寄存器,页表始址,页表长度,+,越界中断,731分页存储管理方式,直接映象地址转换的硬件实现并不复杂，但它对系统的效能却有很不利的影响。主要问题是处理器要两次访问内存才能存取到所需数据，第一次查页表以找出对应的物理块号，第二次才能真正访问所需数据。由此可见，处理器执行指令的速度，降低为原来的二分之一。,731分页存储管理方式,相关映象的页地址转换：为了提高页地址转换速度，在地址变换机构中增设一种硬件联想存储器，或称“快表”。把所有页表放在联想存储器中，因为联想存储器的数据存取速度比一般存储器高一个数量级。当进程访问一个逻辑地址时，该地址被硬件截成两部分：页号p和页内地址d。这时硬件以页号p对联想存储器中页表的各表目同时进行比较，查找出相应的物理块号，与页内地址d拼成绝对地址，然后按此地址访问内存。其地址转换过程如下图所示。,731分页存储管理方式,731分页存储管理方式,在相关映象的地址转换中，页表是放在高速的联想存储器中，而不是放在普通的内存中，其访问数据的速度基本上接近原来速度（约降低10%）。并且相关页表是各表目同时进行比较，所以不用加法器相加的方法来查找所需表目。但由于整个系统的页表所占空间很大，需要很多联想存储器。而联想存储器价格比较昂贵，因此成本很高，不很实用。,731分页存储管理方式,直接映象与相关映象相结合的页地址转换：该方法是直接映象与相关映象相结合而形成的。由于联想存储器价格很贵，页表全部使用联想存储器来存放很不经济。于是把各进程的页表仍然存放在内存的系统区内。此外，系统还使用联想存储器（存放16512个页表项），其中存放着正在运行的进程的当前最常用的部分页面的页号和它的相应物理块号。当运行进程要访问一个逻辑地址时，硬件将逻辑地址截成页号p和页内地址d。地址转换机构首先以页号p和联想存储器中各表目同时进行比较，以便确定该页是否在联想存储器中。若在其中，则联想存储器即送出相应的物理块号p与页内地址一起拼接成绝对地址，并按此地址访问内存。,731分页存储管理方式,与此同时要将该页的页号及对应的物理块号一起送入联想存储器的空闲表目中。如无空表目，通常把最先装入的页的有关信息淘汰出去，以供装入新页的有关信息。实际上直接映象与相关映象同时进行，当相关映象成功后，自动停止直接映象工作。直接映象与相关映象相结合的地址转换机构如下图所示:,731分页存储管理方式,块号,页号,块号,物理地址,块号p,块内地址d,快表,页表,页号,逻辑地址,页号p,页内地址d,页表寄存器,页表始址,页表长度,越界中断,+,731分页存储管理方式,由于对程序和数据的访问往往带有局限性，所以快表的命中率可以达到80%90%。例如，检索联想存储器的时间为20ns，访问内存的时间为100ns，访问联想存储器的命中率为85%，则处理器存取一个数据的平均时间为T=0.85(100+20)+0.15(20+100+100)=135ns所以访问时间只增加了35%。如果不引入联想存储器，其访问时间将增加到200ns。,731分页存储管理方式,两级和多级页表：在现代计算机系统中，逻辑地址空间都有32位到64位。在采用分页存储管理方式时，页表要占用相当大的内存空间。例如，对于一个有32位逻辑地址空间的分页系统，如果页面大小为4KB，即212B，则页面数可有220个，即1M个，若每个页表项占用4个字节，则每个进程仅页表就要占用4MB的内存空间，而且还要求是连续的，显然这是不现实的。为此，可以采用二级页表甚至多级页表的方法来解决这一问题。,731分页存储管理方式,二级页表：把页表分成若干页，并为它们进行编号。可以离散地将各个页面存放在不同的物理块中，为了管理这些页表，需再建立一张页表，称为外层页表，也就是页表的索引表。在外层页表中的每个页表项中记录了页表页面的物理块号。二级页表逻辑地址结构如下图所示：,31,22,21,12,11,0,p1,P2,d,外层页号,外层页内地址,页内地址,731分页存储管理方式,二级页表系统结构如下图所示：,731分页存储管理方式,外层页表的每个表项中，存放的是某页表分页的首址；而在页表的每个表项中存放的是某页在内存中的物理块号。可以利用外层页表和页表，来实现从进程的逻辑地址到内存中物理地址间的变换。为了实现地址变换，在地址机构中需要设置一个外层页表寄存器，用于存放外层页表的始址，并利用逻辑地址中的外层页号作为外层页表的索引，从而找到指定页表分页的首址，再利用外层页内地址作为指定分页的索引，找到指定的页表项，从中找到该页在内存中的物理块号，用该块号和页内地址d即可构成访问内存的物理地址。二级页表时的地址变换机构如下图所示：,731分页存储管理方式,731分页存储管理方式,多级页表：对于32位的机器，采用二级页表结构是合适的。但对于64位的机器，使用二级页表仍然存在着页表占用内存空间过大的问题，原因如下：如果页面大小仍采用4KB（212B），则还剩下52位，假定仍按物理块的大小（210位）来划分页表，此时，把余下的42位用于外层页号，这样，外层页表中最多可能有4T（242）个页表项，要占用16TB的连续内存空间，这是不可能接受的；即使按220位来划分页表，外层页表中仍有4G（232）个页表项，要占用16GB的连续内存空间，这也是不能接受的。因此，在64位机器中，必须采用多级页表，将外层页表再进行分页，然后将各个分页离散地分配到不相邻接的物理块中，再利用第二级的页表来映射它们之间的关系。,732分段存储管理方式,前面介绍的各种存储管理方案中，为用户提供的是一个一维的线性地址空间，这对于模块化的程序设计和变化的数据结构的处理，对于进程之间某些子程序块或数据块的共享等问题，都存在着较大的困难。因此，程序员希望能够按照程序模块来划分段，并以段为单位分配内存。每个段都有自己的名字，可以根据段名来访问相应的程序段或数据段。分页存储管理是从系统的角度出发，主要目的是为了提高内存利用率。而分段存储管理是为满足用户的要求而设计的。,732分段存储管理方式,分段存储管理的基本概念：进程的逻辑地址空间：在分段存储管理方式中，进程的地址空间按照程序自身的逻辑关系分成若干段，每一段在逻辑上都是完整的。例如，有主程序段MAIN、子程序段X、数据段D及堆栈段S等。每个段有自己的段名，故分段存储情况下，进程的逻辑地址空间是二维的。每一个逻辑地址都由段名和段内地址两部分组成。为了实现简单起见，通常用一个段号来代替段名，每个段都从“0”开始编址，并采用一段连续的地址空间，段的长度由相应的逻辑信息组的长度所决定。,732分段存储管理方式,分段系统的地址结构：进程的逻辑地址要用两部分（s，w）来描述，假定某机器指令地址部分长为32位，如果规定左边8位表示段号，而右边24位表示段内地址。这样的地址结构限定了一个进程最多可有256段，最大的段长为16MB。分段系统中的地址结构如下所示：,732分段存储管理方式,内存分配原则：分段存储管理的内存分配以段为单位，每一段分配一块连续的内存分区，一个进程的各段所分到的内存分区不要求是相邻连续的分区。,732分段存储管理方式,段表和段表地址寄存器：在分段系统中，系统为每一个进程建立一个段映象表（简称段表），以实现动态地址转换。段表中应包含的基本信息有段号、段的长度、段在内存中的起始地址。在配置了段表后，执行中的进程可通过查找段表，找到每个段所对应的内存区域。可见，段表实现了从逻辑段到物理内存区域的映射。分段存储管理系统如下图所示：,732分段存储管理方式,732分段存储管理方式,分段存储管理的地址转换：段地址转换与分页系统的页地址转换基本相同，如下图所示：,732分段存储管理方式,类似分页存储管理中的情况，处理器要访问一个数据，也需两次访问内存，使处理器访问指令的速度降为原来的二分之一。为了提高地址转换速度，可以采用联想存储器技术。,732分段存储管理方式,分段存储管理的共享：如下图所示，进程1和进程2要共享Brush段，则在每个进程的段表中，设置一个Brush段即可。,732分段存储管理方式,分段存储管理的优缺点：优点：方便编程；便于动态增长；便于共享；便于动态链接；便于分段保护。,732分段存储管理方式,缺点：要为存储器的紧缩付出处理器机时的代价；为管理各段，要设立段表，为此，要提供附加的存储空间；在外存上管理可变长度的段比较困难；段的最大长度受到内存大小的限制；与分页一样，提高了硬件成本,733段页式存储管理,分页存储管理和分段存储管理，它们各有其优缺点。分页系统能有效地提高内存利用率，但却不能很好地满足用户的需要，给共享和保护带来了一定的困难。分段系统能够很好地满足用户的需要，但要为存储器的紧缩付出处理器机时的代价。为了获得分段管理在逻辑上以及分页管理在存储空间方面的优点，可以把两者结合起来，形成一种新的存储管理方式段页式存储管理技术。这一技术的基本思想是：用分段方法来分配和管理虚存；用分页方法来分配和管理实存。,733段页式存储管理,段页式存储管理的基本概念：进程的逻辑地址空间：在段页式存储管理方式中，先把进程的地址空间按照程序自身的逻辑关系分成若干段，每一段在逻辑上都是完整的，每个段有自己的段名。再把每个段划分成若干个页。段页式存储管理的逻辑地址划分如下图所示：,733段页式存储管理,分段系统的地址结构：进程的逻辑地址被划分成三部分：段号、页号和页内地址。表示为（s,p,d）。所以段页式系统中的地址结构如下所示：,假定某机器指令地址部分长为32位，如果规定011位表示页内地址，1221位表示段内页号，2231位表示段号。这样的地址结构限定了一个进程最多可有1024段，每段最多可有1024页，页的大小为4KB。,733段页式存储管理,内存分配原则：段页式存储管理的内存分配以页为单位，而不是以段为单位。内存分配方法与分页式存储管理方式相似。,733段页式存储管理,段表和页表：在段页式系统中，系统为每一个进程建立一个段映象表（简称段表），为每一段建立一个页映象表（简称页表），以实现动态地址转换。在配置了段表和页表后，执行中的进程可通过查找段表和页表，找到相应的内存区域。过程如下图所示：,733段页式存储管理,733段页式存储管理,段页式存储管理的地址转换：在段页式存储管理中，若运行进程访问逻辑地址v=（s，p，d），在没有联想存储器的情况下，地址转换过程如下：系统中须配置一段表寄存器，在其中放置段表始址和段长TL。地址转换硬件首先利用段号s，将它与段长TL进行比较。若sTL，则表示未越界，便可以利用段表始址和段号来求出该段对应的段表项在段表中的位置，得到该段的页表始址，再利用页表始址和段内页号获得该页对应的物理块号，再用块号与页内地址形成物理地址。地址转换过程如下图所示：,733段页式存储管理,733段页式存储管理,不难看出，从逻辑地址到物理地址的转换过程中，要三次访问内存，第一次是访问段表，第二次是访问页表，第三次才是访问内存物理地址。这就是说，当访问内存中的一条指令或一个数据时，到少要三次访问内存，这将使程序的执行速度大大降低。因此，可以使用联想存储器来加快查表速度。,733段页式存储管理,段页式存储管理的优缺点：优点：与分页和分段式存储管理一样，提供了虚拟存储器的功能；因为存储分配是以物理块为单位，所以没有存储器紧缩问题，也没有页外碎片的存在；便于处理变化的数据结构，段可以动态增长；便于共享，只要在所有需要共享的进程的段表中，有相应表目指向该共享段在内存中的页表地址；便于动态链接；便于存取控制。,733段页式存储管理,段页式存储管理的优缺点：缺点：增加了硬件成本，因为需要更多的硬件支持；增加了软件复杂性和管理开销；存在着页内碎片，而且比分页式存储管理更为严重。,