实存储管理技术

第7章实存储管理技术引言7．1存储管理的根本概念7．2连续分配存储管理方式7．3离散分配存储管理方式引言存储器管理技术可分为两大类：实存储器管理和虚拟存储器管理。本章研究常用的实存储管理技术，第八章研究虚拟存储管理技术。7．1存储管理的根本概念存储器层次结构7．1存储管理的根本概念存储管理目的1、充分利用内存，为多道程序并发执行提供存储根底2、尽可能方便用户使用自动装入用户程序用户程序中不必考虑硬件细节3、系统能够解决程序空间比实际内存空间大的问题4、对操作系统及用户信息提供存储保护与平安7．1．1存储管理要解决的问题

存储分配：动态地为不断进进出出的作业分配内存空间

研究各种内存分配算法，以及每种算法所要求的数据结构。地址映射：保证作业运行中能够正确的定位。研究各种地址变换机构，以及静态和动态重定位方法。存储保护：保证作业的进程之间既能互相通信而又不互相干扰研究如何确保每道程序都在自己的内存空间运行，互不干扰；研究如何保护各程序区中信息不被破坏和偷窃。内存扩充：使空间需求量大于用户区内存容量的作业也能够正常运行研究如何从逻辑上扩充内存，而不是从物理上扩充内存。7．1．2存储管理的分类

连续分配方式：连续分配方式是指系统为一个用户程序分配一个连续的存储空间。这种分配方式曾被广泛应用于60

70年代的操作系统中，今天仍有它的一席之地。连续分配主要有两种：单一连续分配方式：这种存储管理方式把内存划分成系统区和用户区两个分区，用户区仅被一个用户所独占。例如MS-DOS就是采用的单一连续分区管理方式。分区式分配方式：这种存储分配方式适用于多道程序的存储管理，可以分为固定分区式和可变分区式。7．1．2存储管理的分类固定分区式：是将内存的用户区预先划分成假设干个固定大小的区域，每个区域中驻留一道程序。可变分区式：是根据用户程序的大小，动态地对内存进行划分，所以每个分区的大小不是固定的，分区数目也不是固定的。可变分区式显著地提高了存储器的利用率。7．1．2存储管理的分类

离散分配方式：为了进一步提高内存的利用率，提高进程的并发粒度，引入了离散分配方式。它将一个用户进程离散地分配到内存中多个互不邻接的区域。离散分配方式有以下三种：分页存储管理方式：在这种存储管理方式中，用户地址空间被划分成假设干大小相等的区域，称为页或页面；而内存空间也相应地划分成假设干个物理块，页和块的大小相等。这样，就可以将用户程序离散地分配到内存中的任意一块中，从而实现内存的离散分配，这时内存中的碎片不会超过一页。7．1．2存储管理的分类

分段存储管理方式：这种管理方式是从逻辑关系考虑，把用户地址空间分成假设干个大小不等的段，每段可以定义一个相对完整的逻辑信息。在进行内存分配时，以段为单位，段与段之间在内存中可以不相邻接，实现离散分配。段页式存储管理方式：这是分页和分段存储管理方式的结合，即将用户程序分成假设干个段，再把每一段分成假设干个页，相应地将内存空间划分成假设干物理块，页和块的大小相等，将页装入块中。这种存储管理方式不但提高了内存的利用率，而且又能满足用户的要求。7．1．2存储管理的分类

虚拟存储管理系统：为了进一步提高内存的利用率，实现从逻辑上扩充内存的功能，引入了虚拟存储管理系统，虚拟存储管理系统有三种：请求分页系统：请求分页系统是在分页系统的根底上，增加了请求调页功能和页面置换功能所形成的分页式虚拟存储系统。它只把用户程序的局部页面〔而非全部页〕装入内存，就可以启动运行，以后再通过请求调页功能和页面置换功能，陆续把将要运行的页面调入内存，同时把暂不运行的页面置换到外存上，置换时以页面为单位。7．1．2存储管理的分类

请求分段系统：请求分段系统是在分段系统的根底上，增加了请求调段功能和分段置换功能所形成的分段式虚拟存储系统。它只把用户程序的局部段〔而非全部段〕装入内存，就可以启动运行，以后再通过请求调段功能和置换功能将不运行的段调出，同时调入将要运行的段，置换时以段为单位。请求段页系统：请求段页系统是在段页式系统的根底上，增加了请求调页功能和页面置换功能所形成的段页式虚拟存储系统。7．1．3地址重定位

地址空间和存储空间：名字空间：程序中由符号名组成的空间称为“名字空间〞。相对地址：也称逻辑地址或虚地址。源程序经过汇编或编译后再经过链接装配，加工形成程序的装配模块形式，它是以“0〞为基址顺序进行编址的。相对地址空间：相对地址的集合称为相对地址空间，或简称为地址空间。绝对地址：相对地址经地址重定位机构转换到内存中的地址，称为绝对地址，或称物理地址。绝对地址空间：相对地址空间通过地址重定位机构转换到绝对地址空间，绝对地址空间也叫物理地址空间，或称为存储空间。7．1．3地址重定位

名字空间、地址空间和存储空间的关系如以下图所示：I/O说明数据说明符号指令相对目标程序绝对目标程序汇编/编译链接地址重定位装入名字空间地址空间存储空间7．1．3地址重定位

地址重定位：一个逻辑地址空间的程序装入到物理地址空间时，由于两个空间不一致，就需要进行地址变换，或称地址映射，即地址重定位。地址重定位有两种方式：静态重定位和动态重定位。静态重定位：静态重定位是在程序执行之前进行重定位。它根据装配模块将要装入的内存起始地址，直接修改装配模块中的有关地址的指令，这一工作通常是由装配程序完成的。7．1．3地址重定位

静态重定位loadA,[2000+450]010002000+4503500256k-12000+6002000+100存贮空间地址空间3500loadA,[450]0450599100从第2000行开始重定位装入程序BA=20007．1．3地址重定位

静态重定位的优点：静态重定位的优点是容易实现，无须硬件的支持，它只要求程序本身是可重定位的，即对那些要修改的地址局部具有某种标识。静态重定位的缺点：〔1〕程序在地址重定位后就不能在内存中移动了，因而不能重新分配内存，不利于内存的有效利用。〔2〕要求程序的存储空间必须是连续的，不能分布在内存的不同区域。〔3〕不利于内存的共享，假设干用户如假设共享同一程序，那么各用户必须使用自己的副本。7．1．3地址重定位

动态重定位：在程序执行过程中进行重定位，由系统硬件完成从逻辑地址到物理地址的转换。

动态重定位需要硬件的支持，这个硬件就是重定位存放器。重定位存放器的内容是程序装入内存区的起始地址减去目标模块的相对基地址。重定位时，对每一个有效地址都要加上重定位存放器中的内容，以形成存储空间的地址，即绝对地址。7．1．3地址重定位

动态重定位示意图：动态重定位如以下图所示：…LOADA,[450]…3500…LOADA,[450]…3500操作系统0：100：450：2000：2100：2450：地址空间存储空间2000重定位寄存器+7．1．3地址重定位

动态重定位例如：程序的目标模块在装入内存时，与地址有关的指令都无需进行修改，如地址空间中的指令LOADA，450在装入后仍保持相对地址450。当该模块被操作系统调度到处理器上执行时，操作系统首先把该模块装入的起始地址减去目标模块的相对基地址，然后将其差值装入重定位存放器。当处理器取一条访问内存的指令时，地址变换硬件机构自动将指令中的相对地址与重定位存放器中的内容相加，把所得结果作为内存的绝对地址去访问该单元的数据。此外还应增设一对界限存放器，用于防止程序使用的地址超过程序的界限。7．1．3地址重定位

动态重定位的优点：〔1〕在程序的执行过程中，用户程序在内存中可以移动，因而可以重新分配内存，有利于内存的充分利用。〔2〕程序不必连续存放在内存中，可以分散在内存的假设干个不同区域，这只需增加几对基址—限长存放器，每对存放器对应一个区域。〔3〕假设干用户可以共享同一程序。动态重定位的缺点：动态重定位的缺点是需要附加硬件支持，实现存储管理的软件算法比较复杂。

7．2连续分配存储管理方式

连续分区存储管理方式广泛应用于60～70年代的操作系统中，至今仍占有一席之地。本节主要讲述单一连续分配、固定分区分配和可变分区分配等方案。

用户区7．2．1单一连续分配方式在早期的计算机及某些小型、微型计算机系统中，没有采用多道程序设计技术，采用的是单用户、单任务的操作系统〔如MS-DOS、CP/M等〕，使用计算机的用户占用了全部计算机资源。这时的存储管理方案采用的是单一连续分配方案。系统区分区方法：在这一存储管理方案中，内存分为两个区域，如右图所示：系统区：这一区域仅供操作系统使用，通常驻留在内存的低段。用户区：除系统区之外的全部内存空间，提供给用户使用。7．2．1单一连续分配方式

存储保护：对于单一连续分配方式，为了实现存储保护，防止操作系统受到有意或无意的破坏，需要设置界限存放器。如果CPU处于用户态工作方式，那么对于每一次访问，需检查其逻辑地址是否大于界限存放器的值，如果大于界限存放器的值，那么表示已经越界，出现了用户程序对操作系统区域的访问，便产生中断，并将控制转给操作系统。如果CPU处于核心态工作方式，此时可以访问操作系统区域。单一连续分配方式的优点：方法简单，易于实现。单一连续分配方式的缺点：仅适用于单道程序，不能使处理器和内存得到充分利用。7．2．1单一连续分配方式操作系统区作业i的程序、数据等界限地址界限寄存器作业2作业1界限地址+逻辑地址装入程序7．2．2固定分区存储管理方式固定分区分配方式是最早使用的一种能应用于多道程序设计的存储管理方式，其根本思想是在系统生成时就将内存按一定规那么划分成假设干个分区，每个分区的大小可以不等，但事先必须固定，在系统运行过程中不能改变。在每一个分区内装入一个进程，这样，把内存划分成几个分区，便允许几道作业并发执行。当有空闲分区时，可从外存的后备队列中，选择一个适当大小的作业装入该分区。7．2．2固定分区存储管理方式分区划分方法：分区大小相等：把内存等分成假设干份，所有分区的大小都是相等的。这种分区方法不适宜于程序大小不等的情况。当程序太小时，会造成内存空间的浪费；而当程序太大时，可能由于分区太小而无法装入。尽管这种分区方法存在着很多缺点，但在一些地方仍被采用，主要用于利用一台计算机控制多个相同对象的场合。例如，炉温控制系统是利用一台计算机去控制多台相同的冶炼炉。分区大小不等：为了克服分区大小相等分配方法的缺点，可以根据一定的规那么，在内存中划分成多个大小不等的分区，为小的程序分配小分区，中等程序分配中等分区，大程序分配大分区。7．2．2固定分区存储管理方式数据结构：在固定分区分配方式下，操作系统的存储分配模块和存储回收模块都要用到内存分区情况的说明信息，以及这些存储区的使用状况信息。为此，系统中设置了一张分区说明表，包含三项信息：大小：指该分区的大小；始址：指该分区在内存中的起始位置；状态：说明该分区是否已被使用。内存分配：当有一用户程序需要装入时，由内存分配程序检索分区说明表，按照一定的算法找出一个能够满足要求的、尚未使用的分区分配给该程序，同时修改分区说明表中该分区表项中的状态。如果找不到大小足够的分区，那么拒绝为该用户程序分配内存，如以下图所示：7．2．2固定分区存储管理方式区号大小始址状态116K30K已分配232K46K已分配332K78K未分配464K110K已分配5128K174K未分配分区说明表作业A（16KB）操作系统作业B（20K）作业C（52K）0：46K：30K：78K：110K：174K：内存空间分配图7．2．2固定分区存储管理方式固定分区的优缺点：优点：简单，所需硬件支持只是一对界地址存放器，软件算法也很简单。缺点：存在较多的内零头，内存利用率不高。7．2．3可变分区存储管理方式可变分区是指内存事先并没有划分成分区，而是在作业进入内存时，操作系统按照作业的大小从内存中划分出一个分区分配给作业使用。分区的大小和分区的个数都是可变的，是根据作业的大小和数量动态地划分。7．2．3可变分区存储管理方式系统生成后，操作系统占用内存的一局部，一般在物理内存的开始处，比方，一个操作系统占20KB，装入系统后占用0～20KB的内存空间，剩下的局部作为一个空闲区，当一个用户程序〔作业、进程〕调入内存时，把这个空闲区的低地址局部的区域分配给它，如下图。7．2．3可变分区存储管理方式当有作业完成后释放所占用的存储区。在系统运行的过程中，系统中形成多个空闲的不连续的存储区，称主空闲。7．2．3可变分区存储管理方式在实现可变分区存储管理方式时，必须解决下述四个问题：分区分配中所使用的数据结构；分区的分配算法；分区的回收操作；存储保护问题。7．2．3可变分区存储管理方式数据结构：可变分区存储管理中各功能模块要用的数据结构可以有以下几种组织方式：分区说明表：这种方法类似于固定分区中的分区说明表结构，已使用分区和空闲分区都集中在一个表中，但这种表存在两个缺点：由于分区数量是不断变化的，所以表的长度不好确定，造成表格管理上的困难。如果给该表预留的空间不够，那么无法登记各分区的情况。如果预留的空间过大，又会造成浪费。在为作业分配内存时，由于整个表的长度增加了，为查找一块适宜的空闲分区，所需扫描的表目增加，查找速度变慢。7．2．3可变分区存储管理方式空闲分区表FBT和已使用分区表UBT：分别设置两个表格，一个是空闲分区表FBT，另一个是已使用分区表UBT，分别用来登记系统中的空闲分区和已使用分区。这样可以减少存储分配和释放时查找表格的长度，提高查找速度。下表是这两种表格的示意图。

已使用分区表UBT空闲分区表FBT区号大小始址状态区号大小始址状态128K30K已分配120K58K空闲248K78K已分配2——空表目3——空表目346K142K空闲416K126K已分配498K252K空闲5——空表目5——空表目664K188K已分配6——空表目7．2．3可变分区存储管理方式空闲分区链：上述表格的语言表示一般可用数组。但对空闲分区的管理中，通常广泛使用链表把所有的空闲分区链接在一起，构成一个空闲分区链。具体做法是：在每一分区的起始局部设置一前向指针；在分区尾部设置一后向指针通过前后向指针把所有的空闲分区链接成一个双向链。为了检索空闲分区方便起见，在分区尾部重复设置状态位和分区大小表目，当分区分配出去以后，把状态位由“0〞改为“1〞，空闲分区链如以下图所示：7．2．3可变分区存储管理方式N个字节可用前向指针后向指针N+2N+2007．2．3可变分区存储管理方式分区分配算法：在可变分区存储管理方式中，需按照一定的分配算法，分配空闲区给作业，目前常用的方法有以下四种：1〕最先适应分配算法2〕循环最先适应分配算法3〕最正确适应分配算法4〕最坏适应分配算法7．2．3可变分区存储管理方式最先适应分配算法：在分区表中顺序查找，找到够大的空闲区就分配。优点：简单、快速分配，优先利用内存中低址局部的空闲分区，而高址局部的空闲分区很少被利用，从而保存了高址局部的大空闲区。为以后到达的大作业分配大的内存空间创造了条件。缺点：可能形成许多不连续的空闲区，造成许多“碎片〞，使主存空间利用率降低。从该空闲区中截取所需大小，修改调整可用表从空闲区表第一表目顺序查找从可用表中移去该表目，调整可用表取下一表项无法分配该空闲区长度≥SIZE？该空闲区长度=SIZE？表目查完？返回分配起始地址否否否是是是7．2．3可变分区存储管理方式循环最先适应分配算法：类似首次适应法，总是从上次查找结束的地方开始，只要找到一个足够大的空白区，就把它划分后分配出去。优点：解决了低地址区会产生很多碎片的问题，使内存中空闲分区分布比较均匀，减少查找空闲分区的开销。缺点：系统中缺乏大的空闲分区，对大作业不利。7．2．3可变分区存储管理方式最正确适应分配算法：从所有未分配的分区中挑选一个最接近作业大小且大于或等于作业的空闲分区分配给作业。特点：用最小空间满足要求缺点：每次分配之后形成的剩余局部，却是一些小的碎片，不能被别的作业利用。因此，该算法的内存利用率是不高的。要求：空闲分区表自小至大排列7．2．3可变分区存储管理方式最坏适应分配算法：总是挑一个最大的空闲区分给作业使用，使剩下的空间不至于太小。优点：最坏适应分配算法在分配后剩余的空闲分区可能比较大，仍能满足一般作业的要求，可供以后使用。从而最大程度地减少系统中不可利用的碎片。缺点：这种算法使系统中的各空闲分区比较均匀地减小，工作一段时间以后，就不能满足对较大空闲分区的分配要求。7．2．3可变分区存储管理方式注意：这四种分配算法的优劣很难区分，要具体情况具体分析。例如：某时刻系统中有三个空闲区其大小和首址为：(35KB，100KB)、(12KB，156KB)、(28KB，200KB)有一作业系列：(JOB1，12KB)、(JOB2，30KB)、(JOB3，28KB)尝试分析哪种分配策略可以满足作业的内存需求〔分别画出空闲存储区链表〕。JOBREQUESTJOB112KBJOB230KJOB328KB7．2．3可变分区存储管理方式分区的回收：当一个作业运行完毕释放内存时，系统根据回收区的首地址，在空闲分区表中找到相应的插入点，此时可能出现下述四种情况之一。〔其中F1、F2表示回收区前后的空闲区〕：回收区回收区F1F2回收区F2回收区F1(a)(b)(c)(d)7．2．3可变分区存储管理方式回收区既不与F1相邻，也不与F2相邻〔如上图(a)所示〕，应为回收区建立一项新表目，填写回收区的始址和大小，并根据其起址和大小，插入到空闲分区表的适当位置；回收区只与插入点的前一个空闲分区F1相邻时〔如上图(b)所示〕，此时将两个分区合并为一个新的空闲分区，不再为回收区分配新表项，只需修改F1的大小，新回收区的大小为F1与回收区的大小之和；回收区只与插入点的后一个分区F2相邻时〔如上图(c)所示〕，此时将两个分区合并为一个新的空闲分区，修改F2表目的内容，以回收区的始址作为新空闲区的始址，以回收区与F2的大小之和作为新空闲区的大小。7．2．3可变分区存储管理方式回收区与插入点的前、后两个分区F1和F2都相邻时〔如上图(d)所示〕，此时以F1的表目作为新空闲区的表目，F1的始址作为新空闲区的始址，以F1、回收区、F2的大小之和作为新空闲区的大小，删除F2表目。7．2．3可变分区存储管理方式存储保护：保护系统程序区不被用户侵犯。不允许用户程序读写不属于自己地址空间的数据可变分区存储管理方式的存储保护一般采用两种方法：界地址法〔1〕系统设置一对上、下界存放器判别式：下界存放器≤物理地址＜上界存放器作业分区0120K180K180K120K上界存放器下界存放器〔a〕作业分区0120K180K120K60K基址寄存器限长寄存器（b）7．2．3可变分区存储管理方式〔2〕一对基址、限长存放器D<60kD——逻辑地址判别式：0≤逻辑地址<限长存放器作业分区0120K180K120K60K基址寄存器限长寄存器（b）7．2．3可变分区存储管理方式保护键法：系统为每一个存储块都设置了一个单独的保护键，它相当于一把锁。而在作业的程序状态字中设置一个保护键字段，对不同的作业赋予不同的代码，它相当于一把钥匙。当运行作业要访问某个存储器地址时，先要把程序的保护键字段与存储块的保护键进行比较。如果相符，可以进行读写操作；如果不相符，那么访问被禁止或只允许进行读操作。当一个作业运行中产生非法访问时，系统将产生保护性中断。可见，保护键法还提供了一种数据共享的方式。7．2．3可变分区存储管理方式存储器的紧缩和程序的浮动：可变分区存储管理中，由于各作业动态地请求和释放内存分区的结果，会造成内存中存在大量小的，离散分布的碎片。为了解决碎片问题，可以有两种解决方案：解决方案1：把作业分成几局部装入到不同的分区中去，也就是不把一个作业作为一个连续的整体存放在内存中。显然，这种方法可以改变碎片问题，但也带来了程序管理和执行上的复杂性。解决方案2：把内存中的小碎片集中起来，形成一个较大的分区，使之可以装入较大的作业。要进行存储器的紧缩，就要将内存中的程序进行移动。为了解决这个问题，应采用动态重定位技术。一个作业在内存中移动后，只需改变重定位存放器的内容即可。7．2．3可变分区存储管理方式程序浮动示意图：作业5(400K)作业4(350K)作业3(108K)作业2(30K)作业1（8K）操作系统030K38K78K108K260K368K718K1024K(a)作业4(350K)作业3(108K)作业2(30K)作业1（8K）操作系统(b)作业4(350K)作业3(108K)作业2(30K)作业1（8K）操作系统(c)7．2．3可变分区存储管理方式上图〔a〕表示了内存的分配情况。此时，作业5〔400K〕需要装入，但系统中已无足够大的空闲分区装入作业5。此时进行程序的浮动，把作业集中到内存的一端，在另一端形成了454KB的空闲分区〔如上图〔b〕所示〕，作业5便可装入了〔如上图〔c〕所示〕。7．3离散分配存储管理方式连续分配存储技术，容易产生内存碎片，可以通过紧缩技术，移动内存中的作业来解决，但是以花费CPU时间为代价。为解决这一问题，把作业放在主存中不连续的区域里〔离散分配存储管理〕，可以有效解决碎片问题，把作业离散地装入存储器中。7．3离散分配存储管理方式分页存储管理：在该方式中，用户程序的地址空间被划分成假设干固定大小的区域，称为页。而将存储空间也划分成相应大小的区域，称为物理块。这样，可以将用户程序的任一页放入存储空间的任一物理块中，从而实现了离散存储。分段存储管理：分页存储管理是从提高内存利用率的角度出发而形成的，它没有考虑用户的要求。分段存储管理是为满足用户要求而形成的一种存储管理方式。在这种存储管理方式中，作业的地址空间按照程序的逻辑关系被划分成假设干个大小不等的段，每个段定义了一组完整的逻辑信息。在进行存储分配时，以段为单位，这些段在内存中可以不互相邻接，从而实现了离散存储。7．3离散分配存储管理方式段页式存储管理：这是分页和分段存储管理相结合而形成的一种存储管理方式。它综合分页式和分段存储管理的优点，既提高了内存的利用率，又满足了用户的要求，是目前使用较多的一种存储管理方式。7．3．1分页存储管理方式分页存储管理的根本概念：页面和物理块：在分页存储管理方式中，将一个进程的逻辑地址等分成假设干区域，称为页面或页，并给各页从零开始依次编以连续的页号0，1，2，…。相应地，将存储空间划分成与页大小相等的假设干个存储块，称为〔物理〕块或页架，并给各块从零开始依次编以连续的块号0，1，2，…。由于进程的最后一页经常装不满一块，形成不可利用的碎片，称为“页内碎片〞。7．3．1分页存储管理方式逻辑地址的表示：进程的逻辑地址一般是从基地址“0〞开始连续编址的。在分页系统中，每个逻辑地址用一个数对〔p，d〕来表示，其中p是页号，d是页内地址。假设给定一个逻辑地址A，页面大小为L，那么：页号页内地址7．3．1分页存储管理方式例如，逻辑地址A是4856B，页面大小L为1024B，根据上式，可得p=4，d=760，表示为〔4，760〕。7．3．1分页存储管理方式分页系统中的地址结构：分页系统的地址场分为两局部：一局部表示该地址的页号p，另一局部表示页内地址d，其格式如以下图所示。至于页号和页内地址场各占几位，主要取决于页的大小，一般，一页的大小为2的整数次幂。如页的大小为1KB，那么页内地址局部应占10位，即0～9位，页的大小为2KB时，页内地址局部应占11位，即0～10位。页号p页内地址d31111007．3．1分页存储管理方式内存分配原那么：在分页存储管理中，系统以物理块为单位把内存分给进程，并且分给一个进程的各个物理块不一定是相邻和连续的。进程的一个页面装入系统分给的某个物理块中，所以页面和物理块对应。一个进程的相邻的连续的几个页面，可被装入内存的任意几个物理块中，从而实现了离散存储，如以下图所示。7．3．1分页存储管理方式分页存储管理系统示意图:010123作业301234块号页号0314存储空间01234567891011121314001629310021527312414物理地址空间逻辑地址空间页面映射表作业1作业27．3．1分页存储管理方式页表：系统为每一个进程建立了一个页面映射表〔PMT表〕，简称页表，页表至少应包含以下信息：页号：进程各页的序号。物理块号：对应页装入内存的物理块号。页表放在内存，属于进程的现场信息每个页在页表中占一个表项，记录该页在内存中的物理块号。页表作用：实现从页号到物理块号的地址映射。7．3．1分页存储管理方式页面大小的选择：在分页系统中页面的大小是由机器的地址结构所决定的，亦即由硬件决定。对于某一种机器只能采用一种大小的页面。页面大小的选择应遵循如下两条原那么：选择的页面大小适中页面假设太小，有利于提高内存利用率，但也会导致进程的页表过长，占用大量内存。页面较大，虽然可以减少页表的长度，但却又会使页内碎片增大。常在29～213之间，即在512B～8KB之间。页面的大小为2的整数次幂〔转换方便〕7．3．1分页存储管理方式【例7-1】：在一分页系统中，页的大小为2KB，试计算逻辑地址2A3CH的页号和页内地址。解：逻辑地址，其地址场结构如下所示：15141312111098765432100010101000111100页面大小2K=211，所以从第11位〔图中虚线处〕把地址分成两局部，高位局部为5H，低位局部为23CH，故p=5H，d=23CH。所以，2A3CH→〔5H，23CH〕，即2A3CH。7．3．1分页存储管理方式分页系统中的地址转换：地址转换机构的根本任务是完成逻辑地址到物理地址的转换。由于页内地址和块内地址是一一对应的，所以无须转换。因此，地址转换的任务，只是将逻辑地址中的页号，转换为内存中的物理块号。根据系统中硬件结构的不同，可以有三种地址转换方式7．3．1分页存储管理方式直接映象的页地址转换：页表是硬件地址转换的依据页表的功能可以由一组专门的存放器来实现。但由于存放器本钱较高，因此，页表大多驻留在内存中。在系统中只设置一个页表存放器PTR，在其中存放页表在内存的始址和页表的长度。平时，进程未执行时，页表的始址和页表长度存放在本进程的PCB中。当调度程序调度到某进程时，才将这两个数据装入页表存放器中。7．3．1分页存储管理方式地址转换过程：地址变换机构的地址映象硬件自动按页面大小把逻辑地址截成两局部，页号和页内地址〔p，d〕， 在执行检索之前，先将页号与页表长度进行比较，如果页号大于或等于页表长度，那么系统产生一次地址越界中断。 加法器将页表始址与页号和页表项长度的乘积相加，得到该页在页表中的表目位置，于是可以得到该页在内存中的物理块号p’。然后地址映象硬件又将物理块号p’与页内地址拼出实际的内存绝对地址，实现了地址映象。物理地址=块号*页长+页内地址7．3．1分页存储管理方式块号页号页表pp’物理地址块号p’块内地址d逻辑地址页号p页内地址d页表存放器页表始址页表长度+>越界中断7．3．1分页存储管理方式例：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将逻辑地址3412转换成内存地址。7．3．1分页存储管理方式虚地址3412P＝3412/2048＝1d＝3412%2048

＝1364MR=9*2048+1364=19796虚地址3412的内存地址是：197967．3．1分页存储管理方式直接映象地址转换的硬件实现并不复杂，但它对系统的效能却有很不利的影响。主要问题是处理器要两次访问内存才能存取到所需数据，第一次查页表以找出对应的物理块号，第二次才能真正访问所需数据。由此可见，处理器执行指令的速度，降低为原来的二分之一。

7．3．1分页存储管理方式相关映象的页地址转换：为了提高页地址转换速度，在地址变换机构中增设一种硬件——联想存储器，或称“快表〞。把所有页表放在联想存储器中，因为联想存储器的数据存取速度比一般存储器高一个数量级。当进程访问一个逻辑地址时，该地址被硬件截成两局部：页号p和页内地址d。这时硬件以页号p对联想存储器中页表的各表目同时进行比较，查找出相应的物理块号，与页内地址d拼成绝对地址，然后按此地址访问内存。其地址转换过程如以下图所示。7．3．1分页存储管理方式块号快表页号PP’物理地址块号p’块内地址d逻辑地址页号p页内地址d7．3．1分页存储管理方式在相关映象的地址转换中，页表是放在高速的联想存储器中，而不是放在普通的内存中，其访问数据的速度根本上接近原来速度〔约降低10%〕。并且相关页表是各表目同时进行比较，所以不用加法器相加的方法来查找所需表目。但由于整个系统的页表所占空间很大，需要很多联想存储器。而联想存储器价格比较昂贵，因此本钱很高，不很实用。7．3．1分页存储管理方式直接映象与相关映象相结合的页地址转换：该方法是直接映象与相关映象相结合而形成的。由于联想存储器价格很贵，页表全部使用联想存储器来存放很不经济。于是把各进程的页表仍然存放在内存的系统区内。此外，系统还使用联想存储器〔存放16～512个页表项〕，其中存放着正在运行的进程的当前最常用的局部页面的页号和它的相应物理块号。7．3．1分页存储管理方式地址转换过程： 当进程访问一页时，系统将页号与快表中的所有项进行并行比较。假设访问的页在快表中，即可立即进行地址转换。如在快表中未找到对应的页表项，那么还须再访问内存中的页表，找到后，再与页内位移相拼接，得到访问主存的物理地址；同时，再将此页表项存入快表的一个空闲表目中。:7．3．1分页存储管理方式块号页号块号物理地址块号p’块内地址d快表PP’页表页号PP’逻辑地址页号p页内地址d页表存放器页表始址页表长度>越界中断+7．3．1分页存储管理方式配置快表的效果取决于对联想存储器访问的命中率，命中率是通过快表实现内存访问的比率。

例如，检索联想存储器的时间为20ns，访问内存的时间为100ns，访问联想存储器的命中率为85%，那么处理器存取一个数据的平均时间为T=0.85×(100+20)+0.15×(20+100+100)=135ns所以访问时间只增加了35%。如果不引入联想存储器，其访问时间将增加到200ns。7．3．1分页存储管理方式两级和多级页表：在现代计算机系统中，逻辑地址空间都有32位到64位。在采用分页存储管理方式时，页表要占用相当大的内存空间。例如，对于一个有32位逻辑地址空间的分页系统，如果页面大小为4KB，即212B，那么页面数可有220个，即1M个，假设每个页表项占用4个字节，那么每个进程仅页表就要占用4MB的内存空间，而且还要求是连续的，显然这是不现实的。为此，可以采用二级页表甚至多级页表的方法来解决这一问题。7．3．1分页存储管理方式二级页表：把页表分成假设干页，并为它们进行编号。可以离散地将各个页面存放在不同的物理块中，为了管理这些页表，需再建立一张页表，称为外层页表，也就是页表的索引表。在外层页表中的每个页表项中记录了页表页面的物理块号。二级页表逻辑地址结构如以下图所示：31222112110p1P2d外层页号外层页内地址页内地址7．3．1分页存储管理方式二级页表系统结构如以下图所示：4810::260012n外部页表35::0110230页页表1256::260011023n页页表::0123451256存储空间7．3．1分页存储管理方式地址变换：在地址机构中需要设置一个外层页表存放器，用于存放外层页表的始址，并利用逻辑地址中的外层页号作为外层页表的索引，从而找到指定页表分页的首址，再利用外层页内地址作为指定分页的索引，找到指定的页表项，从中找到该页在内存中的物理块号，用该块号和页内地址d即可构成访问内存的物理地址。二级页表时的地址变换机构如以下图所示：7．3．1分页存储管理方式逻辑地址外层页号p1外层页内地址p2页内地址d外层页表寄存器外层页表页表物理地址页内地址物理块号++7．3．1分页存储管理方式多级页表：对于32位的机器，采用二级页表结构是适宜的。但对于64位的机器，使用二级页表仍然存在着页表占用内存空间过大的问题，原因如下：如果页面大小仍采用4KB〔212B〕，那么还剩下52位，假定仍按物理块的大小〔210位〕来划分页表，此时，把余下的42位用于外层页号，这样，外层页表中最多可能有4T〔242〕个页表项，要占用16TB的连续内存空间，这是不可能接受的；即使按220位来划分页表，外层页表中仍有4G〔232〕个页表项，要占用16GB的连续内存空间，这也是不能接受的。因此，在64位机器中，必须采用多级页表，将外层页表再进行分页，然后将各个分页离散地分配到不相邻接的物理块中，再利用第二级的页表来映射它们之间的关系。7．3．2分段存储管理方式 在分页存储系统中，作业的地址空间是一维线性的，这破坏了程序内部的逻辑结构,造成共享、保护的困难。引入分段存储管理方式，主要是为了满足用户和程序员的下述需要：

1)方便编程2)信息共享

3)信息保护4)动态增长

5)动态链接7．3．2分段存储管理方式分段存储管理的根本概念：进程的逻辑地址空间：在分段存储管理方式中，进程的地址空间按照程序自身的逻辑关系分成假设干段，每一段在逻辑上都是完整的。例如，有主程序段MAIN、子程序段X、数据段D及堆栈段S等。每个段有自己的段名，故分段存储情况下，进程的逻辑地址空间是二维的。每一个逻辑地址都由段名和段内地址两局部组成。为了实现简单起见，通常用一个段号来代替段名，每个段都从“0〞开始编址，并采用一段连续的地址空间，段的长度由相应的逻辑信息组的长度所决定。7．3．2分段存储管理方式分段系统的地址结构：进程的逻辑地址要用两局部〔s，w〕来描述，假定某机器指令地址局部长为32位，如果规定左边8位表示段号，而右边24位表示段内地址。这样的地址结构限定了一个进程最多可有256段，最大的段长为16MB。分段系统中的地址结构如下所示：3124230段内地址w段号s7．3．2分段存储管理方式内存分配原那么：分段存储管理的内存分配以段为单位，每一段分配一块连续的内存分区，一个进程的各段所分到的内存分区不要求是相邻连续的分区。7．3．2分段存储管理方式段表和段表地址存放器：在分段系统中，系统为每一个进程建立一个段映象表〔简称段表〕，以实现动态地址转换。段表中应包含的根本信息有段号、段的长度、段在内存中的起始地址。在配置了段表后，执行中的进程可通过查找段表，找到每个段所对应的内存区域。可见，段表实现了从逻辑段到物理内存区域的映射。分段存储管理系统如以下图所示：7．3．2分段存储管理方式存储空间030K90K150K200K（MAIN）=020K（X）=18K（D）=212K（S）=310K基址段长段号20K030K段表8K190K12K2150K10K3200K作业空间10K0（S）=312K08K0（D）=2（X）=120K0（MAIN）=07．3．2分段存储管理方式分段存储管理的地址转换：段地址转换与分页系统的页地址转换根本相同，如以下图所示：越界中断段内地址w段号s逻辑地址25125段表段表寄存器段表始址段表长度基址段长段号20K030K8K190K12K2150K10K3200K150K+5125物理地址++>7．3．2分段存储管理方式类似分页存储管理中的情况，处理器要访问一个数据，也需两次访问内存，使处理器访问指令的速度降为原来的二分之一。为了提高地址转换速度，可以采用联想存储器技术。7．3．2分段存储管理方式分段存储管理的共享：如以下图所示，进程1和进程2要共享Brush段，那么在每个进程的段表中，设置一个Brush段即可。进程1BrushData1进程2BrushData2段表段长基址150500100200150500803506505004303503002000Data1Data2Brush7．3．2分段存储管理方式分段存储管理的优缺点：优点：方便编程；便于动态增长；便于共享；便于动态链接；便于分段保护。7．3．2分段存储管理方式缺点：要为存储器的紧缩付出处理器机时的代价；为管理各段，要设立段表，为此，要提供附加的存储空间；在外存上管理可变长度的段比较困难；段的最大长度受到内存大小的限制；与分页一样，提高了硬件本钱7．3．2分段存储管理方式什么是内碎片？什么是外碎片？产生的原因是什么？固定分区存储分配技术，由于用户作业占据的内存空间不可能刚好等于某个分区的大小，所以，在已分配的分区中，通常都有一局部未被进程占用而浪费的内存空间，这一局部空间称作为存储器的“内碎片〞或“内零头〞。在可变分区管理中，由于作业频繁地调入和调出，会使系统中产生一些小的无法使用的空闲区，这些空闲区称为“外碎片〞。固定分区产生内碎片，可变分区产生外碎片。分页管理产生内碎片，分段管理产生外碎片7．3．2分段存储管理方式分页和分段的主要区别(1)页是信息的物理单位，段那么是信息的逻辑单位(2)页的大小固定且由系统决定，而段的长度却不固定(3)分页的作业地址空间是一维的，即单一的线性地址空间，分段的作业地址空间那么是二维的