操作系统,原理,徐宗元OS-第三章课件

第三章

存储管理

(MemoryManagement)存储器是计算机系统的重要组成部分，所以存储器的管理是操作系统最主要的功能之一。程序的指令和数据只有被调入内存（RAM）CPU直接访问，程序才能够被执行。软件系统需要的内存容量在不断地增加，所以内存的容量仍然是计算机硬件中最关键的、且又是最紧张的“瓶颈”资源。如何对存储器进行有效的管理，不仅直接影响到它的利用率，而且还对系统的性能有重大影响。存储管理的主要对象是内存。教学要求熟悉存储管理目的和功能，掌握地址重定位的概念。熟悉单一连续分配、固定分区分配、动态分区分配实现原理；掌握可变分区分配的数据结构和分配回收算法，熟悉可变分区零头和拼接技术。熟练掌握分页存储管理原理，熟练掌握分页存储管理基本的地址变换机构和具有快表的地址变换机构。掌握分段存储管理原理和分段地址变换机构，掌握分页和分段比较，熟悉分页和分段的共享，掌握段页式存储管理原理和地址变换机构。教学要求-1掌握虚拟存储器的理论基础和定义，熟悉虚拟存储器实现方式和特征。掌握请求分页的页表机制、缺页中断机构和地址变换机构，熟悉页面的分配和置换策略、页面的分配的算法。熟练掌握最佳置换算法、先进先出（FIFO）置换算法、最近最久未使用置换算法LRU，熟悉Clock置换算法和页面缓冲算法；熟悉有效访问时间计算，了解工作集概念。掌握请求分段的段表机制、缺段中断机构和地址变换机构，熟悉分段的共享和保护。存储管理目录-13．4虚拟存储器管理技术3．4．1虚拟存储器的基本概念3．4．2请求分页存储管理3．4．3请求分段存储管理3．5Windows2000内存的管理3．5．1Intelx86/Pentium系列CPU对内存管理的硬件支持机制3．5．2Windows2000地址空间的划分3．5．3Windows2000用户空间内存分配和使用3．5．4页面调度策略3．5．5物理内存管理3．5.6Windows2000高速缓冲管理存储管理目录-23．6实验与习题3．6．1实验一：在Windows2000下评价内存和缓存使用3．6．2实验2：Windows2000内存管理API函数的使用3．6．3选择题3．6．4问答题3．1存储管理概述3．1．1存储层次结构

存储器是处理器处理的信息的来源与归宿，占据着重要地位。但任何一种存储设备都无法在速度与容量两个方面同时满足用户的需求。为解决速度和容量之间的矛盾，冯·诺依曼计算机系统中，采用了三级或更多级的存储器来组成存储层次结构，高一级为CPU寄存器和高速缓存器，中间是主存(可执行的存储器)，最低一级为辅存。通过采用特殊的存储技术，主存与辅存两级可以进一步优化成多级。在存储层次结构中，高层的存储器往往是速度很快、但成本高使容量有限，而接近底部的存储器容量很大、成本低，相对访问速度则慢。各种存储设备组成存储层次结构，如图5－1所示。

存储层次结构-1存储器的功能是保存数据，存储器的发展方向是高速、大容量和小体积。内存在访问速度方面的发展：DRAM、SDRAM、SRAM等；硬盘技术在大容量方面的发展：接口标准、存储密度等；存储组织是指在存储技术和CPU寻址技术许可的范围内组织合理的存储结构。其依据是访问速度匹配关系、容量要求和价格。“寄存器-内存-外存”结构“寄存器-缓存-内存-外存”结构；微机中的存储层次组织：访问速度越慢，容量越大，价格越便宜；最佳状态应是各层次的存储器都处于均衡的繁忙状态（如：缓存命中率正好使主存读写保持繁忙）；存储层次结构-1存储器的功能是保存数据，存储器的发展方向是高速、大容量和小体积。内存在访问速度方面的发展：DRAM、SDRAM、SRAM等；硬盘技术在大容量方面的发展：接口标准、存储密度等；存储组织是指在存储技术和CPU寻址技术许可的范围内组织合理的存储结构。其依据是访问速度匹配关系、容量要求和价格。“寄存器-内存-外存”结构“寄存器-缓存-内存-外存”结构；微机中的存储层次组织：访问速度越慢，容量越大，价格越便宜；最佳状态应是各层次的存储器都处于均衡的繁忙状态（如：缓存命中率正好使主存读写保持繁忙）；存储层次结构图-1高速缓存主存外存cpu可访n+k~几百knM~几百Mn百M~nG存储层次结构图-33．1．2存储管理的功能

操作系统为了有效地管理计算机的内存资源，应该具备以下四大功能：内存分配、内存保护、地址映射、内存扩充。1.内存分配内存分配的主要任务是：为每一道程序分配内存空间，使它们“各得其所”；当程序撤消时，则收回它占用的内存空间。分配时注意提高存储器的利用率。2．

地址映射目标程序所访问的地址是逻辑地址集合的地址空间，而内存空间是内存中物理地址的集合，在多道程序环境下，这两者是不一致的，因此，存储管理必须提供地址映射功能，用于把程序地址空间中的逻辑地址转换为内存空间中对应的物理地址。存储管理的功能-13。存储保护内存保护的任务是确保每道程序都在自己的内存空间运行，互不干扰。保护系统程序区不被用户侵犯（有意或无意的），不允许用户程序读写不属于自己地址空间的数据（系统区地址空间，其他用户程序的地址空间）。

4。提高主存储器的利用率减少不可用的存储空间（称为“零头），允许多道程序动态共享主存。5。内存扩充内存扩充的任务是从逻辑上来扩充内存容量，使用户认为系统所拥有的内存空间远比其实际的内存空间（硬件RAM）大的多。名字空间、地址空间和存储空间-1装配模块虽然具有统一的地址空间，但是仍是以“0”作为参考地址，即是浮动的。要把它装入内存执行，就要确定装入内存的实际物理地址，并修改程序中与地址有关的代码，这一过程称为地址重定位。地址空间的程序和数据经过地址重定位处理后，就变成了可由CPU直接执行的绝对地址程序。我们把这一地址集合称为“绝对地址空间”或“存储空间”。程序的名字空间、地址空间和存储空间之间的关系如图所示。P106图3-2程序的名字空间、地址空间和存储空间

符号源程序LoadA,data1相对目标程序（装配模块）LoadA,200绝对目标程序LoadA,55200名字空间地址空间相对地址/逻辑地址空间存储空间绝对地址/物理地址空间汇编/编译连接地址重定位装入逻辑地址、物理地址和地址映射地址映射BA=1000LoadA200

3456

。

。

。1200物理地址空间LoadAdata1data13456源程序LoadA200

34560100200编译连接逻辑地址空间地址重定位-1例如：LOAD1，2500这条指令是把相对地址为2500的存储单元的内容365装入1号累加器。而这时内容为365的存储单元的实际物理地址为12500（起始地址10000+相对地址2500），所以LOAD1，2500这条指令中的直接地址码要作相应的修改，即改为LOAD1，12500。

P106图3-3静态重定位LOAD1，25003650100：2500：2600：LOAD1，1250036510000：10100：12500：12600：程序的地址空间内存的地址空间地址重定位-3为了支持静态重定位，连接程序在生成统一地址空间和装配模块时，还应产生一个重定位项表，该表的每一项――重定位项是在程序中需要修改地址的位置，操作系统的装入程序要把装入模块和重定位项表一起装入内存。程序装入内存中的起始地址称为重定位因子，由装配模块的实际装入起始地址得到重定位因子，然后取重定位项，把重定位项表示地址的内容进行修改，即把重定位项表示地址的内容加上重定位因子，从而完成指令代码的修改。当完成重定位后，就可以启动程序执行。

地址重定位-5动态重定位

动态重定位是指在程序执行过程中进行地址重定位，即在每次访问内存单元前才进行地址变换。动态重定位可使装配模块不加任何修改就装入内存，但是它需要硬件—重定位寄存器的支持。下图给出了动态重定位的示意图。 程序的目标模块在装入内存时，与地址有关的指令都无须进行修改，如在图3-4中LOAD1，2500这条指令中仍保持相对地址2500。当该指令被操作系统取到中央处理器指令寄存器上执行时，操作系统首先把该模块装入的实际起始地址减去目标模块的相对基地址（图3-4中该模块的基地址为0），然后将其差值10000装入重定位寄存器。

3．2存储器的连续分配3．2．1单一连续分配

这是一种最简单的存储管理方式，但只能用于单用户、单任务的操作系统，如在8位和16位微机上CP/M和MS-DOS操作系统。它将内存分为两个区：系统区：仅供操作系统使用，通常设置在内存的低段；用户区：指除系统区以外的全部内存空间，提供给用户使用。这种存储分配方式由于用在单用户、单任务的操作系统中。P108图3-5单一连续分配示例系统区操作系统用户区用户程序

0下限上限基址长度单一连续区存储管理3．2．2分区存储管理方式

分区存储管理是能够满足多道程序运行的最简单的存储器管理方案，其基本思想是将内存划分成若干个连续的区域，称为分区。每个分区只能储存一个程序，而且程序也只能在它所驻留的分区中运行。分区存储管理根据分区个数及分区大小的可变性分为固定式分区和可变式分区两种。1.固定分区(FixedPartitioning)分配方式

固定分区是在作业装入之前，内存就被划分成若干个分区。划分工作可以由系统管理员完成，也可以由操作系统实现。然而一旦划分完成，在系统运行期间不再重新划分，即分区的个数不可变，分区的大小不可变，所以，固定式分区又称为静态分区。

这种分区方式一般将内存的用户区域划分成大小不等的分区，以适应不同大小的作业的需要。系统有一张分区说明表，每个表目说明一个分区的大小、起始地址和是否已分配的使用标志。分区说明表和内存分配图如下所示。

P109图3-6固定分区分配示例区号大小起址 标志 116KB 20K 已分配 2 32KB 36K 已分配 364KB 68K 已分配 4124KB132K未分配 (a)分区说明表固定式分区实现技术简单，但是内存的利用率不高，适用于作业的大小和多少事先都比较清楚的系统中。它用于60年代的IBM-360的MFT操作系统中。0k：

20k：

36k：

68k：

132k：

256k：

内存分配图

操作系统作业A（16k）作业B（26k）作业C（56k）第1分区（16kb）第2分区（32kb）（已分配）第3分区（64kb）（已分配）4分区（124kb）（未分配）

固定分区分配-2由于每个分区的大小是固定的，所以每个提出运行的作业必须说明所需的最大内存容量。在调度作业时，存储管理程序根据作业所需的内存容量，在分区说明表中找出一个足够大的空闲分区分配给它，然后用重定位装入程序将此作业装入。如果找不到，则通知作业调度模块，选择另外一个作业。图3-6（b）说明了某一时刻，作业A、B、C分别被分配到1，2，3三个分区中，第四个分区尚未分配，操作系统则永久占据内存低地址区20KB的空间。当一个作业结束时，系统又调用存储管理程序查到分区说明表，把所占分区的使用标志修改为未分配状态即可。

固定分区分配-3采用这种技术，虽然可以使多个作业共驻内存，但是一个作业的大小不可能正好等于某个分区的大小，所以每个被分配的分区总有一部分被浪费，我们把这部分被浪费的存储区称为内零头或内碎片。有时这种分配方式浪费相当严重，如图3-6（b）中第3分区未分配的部分还有8KB，加上第4分区的124KB共计132KB，而且这132KB的内存空间在物理上是一个连续的区域，这时如果有一个大小为130KB的作业申请内存，却被拒绝，因为分区的大小是预先划分好的，分区说明表中指出只有第4分区未分配（大小为124K），且不能改变分区的大小。MultiprogrammingwithFixedPartitionsFixedmemorypartitionsseparateinputqueuesforeachpartitionsingleinputqueue2．可变（动态）

(DynamicPartitioning)分区分配方式

(1)可变分区概述可变分区是指在作业装入内存时，从可用的内存中划出一块连续的区域分配给它，且分区大小正好等于该作业的大小。可变分区中分区的大小和分区的个数都是可变的，而且是根据作业的大小和多少动态地划分，因此又称为动态分区。这种存储管理技术是固定式分区的改进，既可以获得较大的灵活性，又能提高内存的利用率。可变分区概述-1

系统初始化后，内存被划分成两块，一块用于常驻的操作系统，另一块则是完整的空闲区（用户区）。对于调入的若干个作业，划分几个大小不等的分区给它们，随着作业的调入和撤除，相应的分区被划分和释放，原来整块的存储区形成空闲区和已分配区相间的局面。图3-7（c）给出了可变式分区的示例，512KB内存中除20KB操作系统外，装入作业2、3、4、6四个，有空闲区1、2、3三个。

P110图3-7可变式分区示例

序号P 大小 起址 状态 1 32k 20k 空闲 2 56k 260k 空闲 3116k 396k 空闲 4 — — 空表目 5 — — 空表目 （a）空闲分区表前向指针N+200后向指针N+200N个字可用空闲区（56k）作业6（80k）空闲区（116k）空闲区（32k）作业2（64k）作业3（48k）作业4（96k）操作系统(20K)020K52K116K164K260K316K396K512K返回可变分区概述-2可变式分区的分配和释放的基本思想是：在分配时，首先找到一个足够大的空闲分区，即这个空闲区的大小比作业要求的要大，系统则将这个空闲分区分成两部分：一部分成为已分配的分区，剩余的部分仍作为空闲区。在回收撤除作业所占领的分区时，要检查回收的分区是否与前后空闲的分区相领接，若是，则加以合并，使之成为一个连续的大空间。

ExampleDynamicPartitioningOperating

SystemProcess1320KProcess2Process3224K288K64KOperating

SystemProcess1320KProcess3224K288K64KOperating

SystemProcess1320KProcess3288K64KProcess4128K96KExampleDynamicPartitioning-1Operating

System320KProcess3288K64KProcess4128K96KOperating

SystemProcess3288K64KProcess4128K96KProcess2224k96K动态/可变式分区分配-1(2)可变式分区的数据结构

空闲区表形式空闲分区表为每个尚未分配的分区设置一个表项，包括分区的序号、大小、始址和状态。空闲区链形式为了实现对空闲分区的分配和链接，在每个分区的起始部分，设置一些用于控制分区分配的信息（如分区的大小和状态位），以及用于链接其它分区的前向指针；在分区尾部，则设置了一个后向指针，为了检索方便也设置了控制分区分配的信息。然后，通过前、后向指针将所有的分区链接成一个双向链表。(3)可变分区分配算法

(PartitioningPlacementAlgorithm)(1)最佳适应算法BF（BestFit）：它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按大小从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区，但造成许多小的空闲区。(2)首次适应算法FF（FirstFit）：从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区。可变分区分配算法-1(3)循环首次适应算法NF(NextFit)：该算法是首次适应算法的变种，它把空闲分区表（空闲区链）中的空闲分区按地址递增构成一个循环链。在分配内存空间时，不再每次从表头（链首）开始查找，而是从上次找到的空闲区的下一个空闲区开始查找，直到找到第一个能满足要求的的空闲区为止，并从中划出一块与请求大小相等的内存空间分配给作业。该算法能使内存中的空闲区分布得比较均匀。(4)最坏适应法：从所有未分配的分区中挑选最大的且大于和等于作业大小的分区分给要求的作业；空闲分区按大小由大到小排序。该算法使小的空闲区减少，但造成大的空闲区不够大。例：分配一个16KB分区采用空闲分区表结构和首次适应分配算法

空闲分区表数据结构空闲分区表中的空闲分区要按地址从低到高连续排序，最后一个空闲分区中m_size为0表示以上表目空白。空闲分区表起始地址为coremap分配和释放的基本思想是：在分配时，首先找到一个足够大的空闲分区，即这个空闲区的大小比作业要求的要大，系统则将这个空闲分区分成两部分：一部分成为已分配的分区，剩余的部分仍作为空闲区。在回收撤除作业所占领的分区时，要检查回收的分区是否与前后空闲的分区相领接，若是，则加以合并，使之成为一个连续的大空间。m_addrm_size…..m_addrm_size=0…...m_addrm_sizem_addrm_sizem_addrm_sizem_addrm_sizeCoremapP111图3-8采用首次适应算法的可变分区的分配流程图

申请分配一个u.size大小的分区从头开始查表是否检索完毕？本次无法分配m.size>u.size

m.size-u.size≤size？从该分区中划出u.size大小的分区继续检索下一个表项将该表目以上的所有表目下移一格将该分区分配给申请者修改有关的数据结构

返回YNN（4）可变分区回收算法

当一个作业运行完毕释放内存时，系统根据释放区的首地址，从空闲区说明表中找到相应的插入点，此时可能出现下列四种情况（如图3-9所示，其中F1，F2表示回收区的前、后空闲区）：(1)当回收区既不与F1领接，又不与F2领接时（如图3-9（a）），应为回收区单独建立一项新表目，填写回收区的起址和大小，并根据其起址，插入到空闲区说明表的适当位置。(2)当回收区只与插入点的前一个分区F1相领接时（如图3-9（b）），应将回收区与插入点的前一个分区合并，不再为回收区分配新的表目，而只需修改F1分区表目的大小即可。可变分区回收算法-1(3)当回收区只与插入点的后一个分区F2相领接时（如图3-9（c）），将把两个空闲区合并，修改F2分区的表目，把回收区的起址作为新空闲区的起址，大小为两个分区之和。(4)当回收区与插入点的前、后两个分区（F1和F2）都相领接时（如图3-9（d）），合并三个分区，用F1表目的起址作为新空闲区的起址，修改其大小为三块分区之和，最后取消F2的表目。图3-7（c）内存分配图中作业3、2、4、6分别回收时相当于图3-9（a）、（b）、（c）、（d）内存回收时的情况。

P112图3-9内存回收时的情况

作业Y回收区作业X

F1

F1

回收区作业Y

F2

F1

回收区

F2作业Y

回收区

F2作业X作业Y

A

B

C

D可变分区回收算法-3对于前图所示的可变式分区内存分配图，下列四种情况分别如下图所示：

作业4回收区作业2空闲区1

空闲区1

回收区作业3

空闲区2

回收区空闲区3

回收区

空闲区2作业3作业6

A

B

C

D作业3回收作业2回收作业4回收作业6回收可变分区回收算法-4作业3回收前后序号P 大小 起址 状态 1 32k 20k 空闲 2 56k 260k 空闲 3116k 396k 空闲 4 — — 空表目 5 — — 空表目 （a）空闲分区表序号P大小起址状态 1 32k20k空闲

2

48k116k空闲

3 56k260k空闲 4 116k396k空闲 5 ——空表目 空闲分区表空闲区2（56k）作业6（80k）空闲区3（116k）空闲区1（32k）作业2（64k）作业3（48k）

回收区作业4（96k）操作系统(20K)020K52K116K164K260K316K396K512K空闲区3（56k）作业6（80k）空闲区4（116k）空闲区1（32k）作业2（64k）空闲区2（48k）作业4（96k）操作系统(20K)020K52K116K164K260K316K396K512K回收前

回收后空闲区2（56k）作业6（80k）空闲区3（116k）作业3（48k）作业4（96k）操作系统(20K)020K116K164K260K316K396K512K空闲区2（56k）作业6（80k）空闲区3（116k）空闲区1（32k）作业2（64k）

回收区作业3（48k）

作业4（96k）操作系统(20K)020K52K116K164K260K316K396K512K回收前

回收后可变分区回收算法-5作业2回收前后序号P 大小 起址 状态 1 32k 20k 空闲 2 56k 260k 空闲 3116k 396k 空闲 4 — — 空表目 5 — — 空表目 （a）空闲分区表序号P大小起址状态 1 96k20k空闲 2 56k260k空闲 3 116k396k空闲 4 ——空表目 5 ——空表目 空闲分区表空闲区1（96k）可变分区回收算法-6作业4回收前后序号P 大小 起址 状态 1 32k 20k 空闲 2 56k 260k 空闲 3116k 396k 空闲 4 — — 空表目 5 — — 空表目 （a）空闲分区表序号P大小起址状态 1 32k20k空闲 2 152k164k

空闲 3 116k396k空闲 4 ——空表目 5 ——空表目 空闲分区表空闲区2（56k）作业6（80k）空闲区3（116k）空闲区1（32k）作业2（64k）作业3（48k）

作业4（96k）

回收区操作系统(20K)020K52K116K164K260K316K396K512K空闲区2（152k）作业6（80k）空闲区3（116k）空闲区1（32k）作业2（64k）作业3（48k）操作系统(20K)020K52K116K164K316K396K512K回收前

回收后可变分区回收算法-7作业6回收前后序号P 大小 起址 状态 1 32k 20k 空闲 2 56k 260k 空闲 3116k 396k 空闲 4 — — 空表目 5 — — 空表目 （a）空闲分区表序号P大小起址状态 1 32k20k空闲 2 252k260k空闲

3 ——空表目

4 ——空表目 5 ——空表目 空闲分区表作业6（80k）空闲区4（116k）空闲区2（56k）作业6-80k回收区空闲区3（116k）空闲区1（32k）作业2（64k）作业3（48k）

作业4（96k）操作系统(20K)020K52K116K164K260K316K396K512K空闲区2（252k）空闲区1（32k）作业2（64k）作业3（48k）作业4（96k）操作系统(20K)020K52K116K164K260K512K回收前

回收后可变分区回收算法-8后空闲区

不

D不

A邻

B邻

C前空闲区

不邻不邻表目

加一

//减一后空闲区首址/

/

-size

撤消后空闲区大小/

/

+size

撤消前空闲区首址

/

/

/

/前空闲区大小

/+size/+size+后空闲区大小(5)可变分区零头和拼接技术

可变分区也有零头问题。在系统不断地分配和回收中，必定会出现一些不连续的小的空闲区，称为外零头或外碎片。虽然可能所有零头的总和超过某一个作业的要求，但是由于不连续而无法分配。解决零头的方法是拼接或紧凑（Compaction），即向一个地址方向（例如向低地址端）移动已分配的作业，使那些零散的小空闲区在另一方向连成一片。分区的拼接技术，一方面是要求能够对作业进行重定位，另一方面系统在拼接时要耗费较多的时间。采用拼接技术的可变分区又称可重定位分区。

动态重定位分区分配例

20k28k88k132k182ko.s作业1(8k)(16k)作业3(24k)(24k)作业(20k)作业4(50k)(74k)64k112k256k(a)初始状态20k202ko.s1324作业5(80k)(54k)122k(c)分配作业5之后(b)移动之后(即浮动)20k28k72ko.s1(8k)3(24k)2(20k)4(50k)(134k)52k122k256k作业580k(6)分区的存储保护

分区的存储保护是用户程序只能访问自己的用户分区，不能访问系统分区和其它程序的分区。分区存储保护常用方法是界地址法或界限寄存器。分区的存储保护-1系统设置一对上、下界寄存器，每当选中某个作业运行时，先将它的界地址装入这对寄存器中，作业运行时形成的每一个访问存储器的地址都要同这两个寄存器的内容进行比较，若超过这个指定范围，就产生越界中断。系统也可以设置一对基址、限长寄存器，此时基址寄存器还起着重定位寄存器的作用，运行进程所在分区的始址和大小分别装入基址和限长寄存器。界限寄存器用硬件实现，它是存储管理部件MMU的一部分，采用基址、限长寄存器的地址变换和存储保护的存储管理部件MMU见图3－10所示。

P112图3-10分区的地址变换和存储保护

界限寄存器重定位寄存器(基址)+CPU<内存地址错逻辑地址YN物理地址3．3存储器的离散分配

连续分配会形成许多“碎片”，为了减少碎片提高存储器的利用率而引入了离散分配方式,它将一个用户的程序划分成若干个大小相等的页再离散地分配到内存的多个不相邻的区域中。3．3．1纯分页(Paging)存储管理方式1．分页存储管理原理

分页存储管理是将一个进程的地址空间划分成若干个大小相等的片，称为页面或页，相应地，将内存空间划分成与页相同大小的若干个块，称为（物理）块或页框。在为进程分配内存时，将进程中的若干页离散地装入不相邻接的物理块中。

分页存储管理原理－1由于页面的大小一般取2的幂次个字节，通常在512B到4KB之间，所以内存空间划分后不存在“外碎片”。由于每块物理块可离散地分配给进程的一页，这样不断地分配，直到剩余的物理块数不能满足一个进程的要求为止。而对每个进程只有最后一页经常装不满一块，平均产生半页“页内碎片”。由此可知，分页存储管理解决了“碎片”问题，提高了存储器的利用率。纯分页存储管理是指一个进程的所有页全部装入内存的物理块中才能运行。分页存储管理原理-1分页系统的地址结构如图3-11所示，它由两部分组成：前一部分为页号P；后一部分为页内位移量W，即页内地址。图中的地址长度为16位，其中0～9位为页内地址（每页的大小为1KB），10～15位为页号，所以允许地址空间的大小最多为64个页。

页号P位移量W1510902．页表

在将进程的每一页离散地分配到内存的各个物理块中后，系统为了保证进程的正确运行，即能在内存中找到该进程每个页面所对应的物理块，系统需为每页配一个重定位寄存器，由于重定位寄存器是硬件，在页面数很多时实现困难。为此，系统在内存为每个进程建立了一张页面映射表，简称页表（如图3-12所示）。每个页在页表中占一个表项，记录该页在内存中对应的物理块号（页号可以省略）。进程在执行时，通过查找页表，就可以找到每页所对应的物理块号。可见，页表的作用是实现从页号到物理块号的地址映射。

页表-13．地址变换机构

地址变换机构的基本任务是利用硬件实现查页表把用户程序中的逻辑地址变换成内存中的物理地址。为了实现地址变换功能，在系统中设置页表寄存器，用来存放页表的始址和页表的长度。在进程未执行时，每个进程对应的页表的始址和长度存放在进程的PCB中，当该进程被调度时，就将它们装入页表寄存器。地址变换机构－1

在进行地址变换时，系统将逻辑地址截成页号和页内地址二部分，将页号与页表长度进行比较，如果页号大于等于页表寄存器中的页表长度，则访问越界，产生越界中断。如未出现越界，则根据页表寄存器中的页表始址和页号计算出该页在页表项中的位置，查页表得到该页的物理块号，将物理块号与逻辑地址中页内地址二者拼接成物理地址，这样便完成了从逻辑地址到物理地址的变换。

地址变换机构-2图3-13说明了分页系统的地址变换机构，地址变换机构是由硬件完成，包括自动地查内存的页表。图中举例说明CPU指令寄存器在执行Load1,2500指令时，地址变换机构自动地完成了逻辑地址2500到物理地址5572的变换，将地址为5572内存的数据读入，送入寄存器1。完成从逻辑地址到物理地址的变换的地址变换机构又称为存储管理部件MMU，它由硬件完成，并由于超大规模集成电路的发展，MMU已集成到CPU集成块中。

P114图3-13分页系统的地址变换机构

块号5块内地址452

页号2页内地址452页表始址页表长度﹥

245越界中断页表寄存器CPU指令寄存器LOAD1,2500逻辑地址2500页号块号

012物理地址55725*1024+452每页1KB(1024)地址变换机构图-100001000010000010116-bitLogicalAddress25006-bitpage#10-bitOffset00001001110001000001010111000100

16-bitPhysicalAddress5572分页存储管理逻辑地址到物理地址地址变换的计算假设页长为1KB(1024字节)，逻辑地址为2500(十进制)。利用页表把逻辑地址变换成物理地址计算步骤如下：(1)将虚地址分离成页号P和页内地址d：页号P＝（逻辑地址／页大小）取整＝（2500/1024）取整＝2页内地址d＝逻辑地址mod页大小=2500mod1024=452(2)根据页号查页表，由页表项读出块号：由页号P＝2查页表得块号为5(3)块号和页内地址构成物理地址：物理地址＝块号×页大小＋页内地址=5*1024+452=5572

分页存储管理逻辑地址到物理地址地址变换的计算-1十六进制－－逻辑地址09C4H1KB1024400H∵C00H＞09C4H＞800H

页号22KB2048800H页内地址＝逻辑地址－该页头地址3KB3072C00H＝09C4H－800H＝1C4H4KB40961000H查页表页号2块号55KB51201400H物理地址＝该块头地址+页内地址6KB61441800H

=

1400H+1C4H=15C4H

ThepositionandfunctionoftheMMU4．快表

如果页表存放在内存中，则每次访问内存时，都要先访问内存中的页表，然后根据所形成的物理地址再访问内存。这样CPU存一个数据必须访问两次内存，从而使计算机的处理速度降低了1/2。为了提高地址变换的速度，在地址变换机构中增设了一个具有按内容查找、并行查询功能的特殊的高速缓冲存储器，称为“联想存储器(AssosiativeMemory)”或“快表”，或称为“关联存储器(TLB,TranslationLook-asideBuffer)”，用以存放当前访问的那些页表项，每个页表项包括页号和相应的块号（页号不能省略）。快表-1

在快表的输入寄存器输入页号后，输入页号与快表中的各页表项中的页号同时比较，如有相同，快表的输出寄存器输出相应的块号，如都不相同，快表的输出寄存器不输出。快表存取速度快，但由于成本的原因，快表不可能做得很大，大程序的页表项不可能全部放在快表中。为此，把各进程的页表仍放在内存的系统区中，而系统增加的快表用以存放正在运行进程的、当前常用的部分页面的页号和相应的块号。

P115图3-14具有快表的地址变换机构

012

245越界中断逻辑地址页表寄存器页号块号块号页号快表物理地址页表

页号页内地址页表始址页表长度﹥块号块内地址

输入寄存器021425快表-2

此时地址变换过程为：CPU给出逻辑地址并将逻辑地址截成页号和页内地址二部分后，地址变换机构先将页号送入快表的输入寄存器，确定所需要的页是否在快表中。若是，则直接读出该页所对应的物理块号，与逻辑地址中页内地址二者拼接成物理地址；若在快表中未找到对应的页表项，则需再访问内存中的页表，找到后，把从页表中读出的页表项存入快表中的一个寄存器单元中，以取代一个旧的页表项，同时将此物理块号与逻辑地址中页内地址二者拼接成物理地址，并访问主存。图3-14说明了具有快表的地址变换机构。快表-3

由于成本的原因，快表不可能做得很大，通常只能存放16~512个页表项。例如，在Intel80486中有32个。这对中、小型作业来说，已可能把全部页表项放入快表中；但对于大型作业来说，则只能将一部分页表放入快表中。

由于对程序和数据的访问往往带有局限性，所以快表的命中率可以达到80%～99%。例如，假设检索联想存储器的时间T(联想)为20ns，访问内存的时间T(内存)为100ns，访问联想存储器的的命中率p为90%。快表-4当快表命中时CPU存取内存一个数据的时间为T1＝检索快表时间＋访问内存数据时间=T(快表)+T(内存)＝20＋100＝120ns。当快表不命中时CPU存取内存一个数据的时间为T2＝检索快表时间＋检索内存中的页表时间＋访问内存数据时间=T(快表)+T(内存)+T(内存)＝20＋100＋100＝220ns。则CPU存取内存一个数据的平均时间为

T=T1*命中率+T2*（1－命中率）=T1*ρ+T2*(1-ρ)=120*0.9+220*0.1=130ns。访问时间增加为(T-T(内存))∕T(内存)=(130-100)∕100=30%。如果不引入快表，其访问将延长一倍（达200ns）。

3．3．2分段(Segmentation)存储管理方式1．分段存储管理的引入从固定分区到可变分区，进而又发展到分页系统的原因都是为了提高内存的利用率，然而分段存储管理的引入，是为了满足用户需要。分页存储管理时的进程地址空间结构都是线性的，这要求对各段源程序编译成目标程序后还要静态链接，例如图3-15把四个源程序段编译后的目标程序段：主程序段main（15KB）、子程序段X（5KB）、数据段D（6KB）、堆栈段S（7KB）按线性空间的一维地址顺序排列起来，再分成8页，每页为4KB。P116图3-15

分页系统的作业地址空间分段存储管理的引入-2这时一个页面中可能装有两个不同子程序段的指令代码，例如第3页装有main和X两个不同段的指令代码，如这2段存取方式不同，则这一页的存取方式无法确定。因此，通过页面共享来达到共享一个逻辑上完整的子程序或数据块是不可能的。另外，从减少CPU开销和存储空间浪费的角度来看，静态链接是不合适的。为了为用户提供一个方便灵活的程序设计环境需引入段式存储管理，每个段是一组完整的逻辑信息，分段存储管理有便于编程、便于共享和保护、可动态链接、可动态增长等特点。2．分段系统的基本原理

在分段存储管理方式中，作业的地址空间按逻辑信息完整性被划分为若干个段，每个段都有自己的名字，编译后都是从零开始编址的一段连续的地址空间，段的长度由相应逻辑信息组的长度决定，因而各段长度是不等的。分段系统的地址结构如图3-16所示，逻辑地址由段号和段内地址两部分组成。在该地址结构中，允许一个作业最多有64K个段，每个段的最大长度为64KB。图3-17中一个作业有四个段：主程序段MAIN、15KB长、段号为0，子程序段X、5KB长、段号为1，数据段D、6KB长、段号为2，堆栈段S、7KB长、段号为3。

P116图3-16分段系统的地址结构

段号段内地址31161503．段表

在分段式存储管理系统中，为每个段分配一个连续的分区，而进程中的各个段可以离散地分配到内存中不同的分区中。类同分页式存储管理，在分段式存储管理系统中为每个进程建立一张段映射表，简称为“段表”。每个段在表中占有一表项，在其中记录了该段在内存中的起始地址（又称为“基址”）和段的长度，在图3-17中，上述作业的四个段分别分配到内存中起始地址为40K、120K、160K、200K四个不同的分区中。进程在执行中，通过查段表来找到每个段所对应的内存区。可见，段表实现了从逻辑段到物理内存区的映射。

内存空间040k：80k：120k：150k：P116图3-17利用段表实现地址映射

作业空间

(MAIN）=00段表

15K段号段长基址（X）=10

017K

（D）=2208K3（S）=3010K15K40K7K80K8K120K10K150K（MAIN）=015K（X）=17K（D）=28K

（S）=310K4．地址变换机构

为了实现从逻辑地址到物理地址的变换功能，系统中设置了段表寄存器，用于存放段表始址和段表长度。在进行地址变换时，系统将逻辑地址截成段号S与段内地址d，将逻辑地址中的段号S与段表长度TL进行比较。若S≥TL，表示段号太大，访问越界，于是产生越界中断信号；若未越界，则根据段表的始址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存中的起始地址，然后再检查段内地址d是否超过该段的段长SL。若超过，即d≥SL，同样发出越界中断信号；若未越界，则将该段的基址与段内地址d相加，得要访问的内存物理地址。图3-18给出了分段系统的地址变换过程。

P117图3-18分段系统地址变换机构

段号段长SL基址段表始址段表长度

TL段号S位移量d2100﹥15K40K7K80K8K120K10K50K

物理地址120k+100逻辑地址越界中断段表寄存器0123地址变换机构图-116-bitLogicalAddress4-bitSegment#12-bitOffset0001001011110000ProcessSegmentTable

16-bitPhysicalAddress0010001100010000000000000000+LengthBase地址变换机构图(地址映射及存储保护机制)

Cl

Cb+段号S段内地址d比较比较b+d比较段表快表物理地址段表始址寄存器段表长度寄存器逻辑地址地址越界d>=1地址越界地址越界lbSlbSegmentationHardware5．共享

段是信息的逻辑单位,因此分段系统的一个突出的优点是易于实现段的共享。即允许若干个进程共享一个或多个段，而且对段的保护也十分简单。在分页系统中，虽然也能实现程序和数据的共享，但远不如分段系统来得方便。分段系统中，每个进程的段表中设置一个段表项。图是分段系统中共享editor编辑程序的示意图。共享-1

在实现段共享时，需要用到可重入代码(ReentrantCode)又称为“纯代码”(PureCode)。它是一种允许多个进程同时访问的代码，是一种不允许任何进程对其进行修改的代码。但在每个进程中，配以局部数据区，将在执行中可能改变的部分，拷贝到该数据区，这样，程序在执行时，只对该数据区(属于该进程私有)中的内容进行修改，而不去改变共享的代码，这时的可共享代码即成为可重入代码。P118图3-19分段系统中实现段共享

段表段长基址

1608040240

editor

DATA1

editor

DATA2段长基址1608040380

editorDATA1

DATA2进程1进程2

802402803804206．分页和分段的主要区别

分页和分段的主要区别-1

3．3．3段页式存储管理

分页和分段存储管理方式都各有其优缺点。如果对两种存储管理方式“各取所长”后，则可以形成一种新的存储管理方式的系统——段页式系统。它以分页的方式管理内存，具有分页系统能有效地提高内存利用率的优点；又以分段的方式管理用户的逻辑地址空间，具有分段系统能很好地满足用户需要的长处，显然是一种比较有效的存储管理方式。1．基本原理

段页式系统的基本原理是将内存空间划分成相同大小相同的若干个块，将用户程序先按逻辑完整性分为若干个段，并为每个段赋予一个段名，再把每个段划分成若干个与块大小相同的页，将进程中的若干页离散装入不相邻接的块中。图3-20中示出了一个作业地址空间结构，该作业有四个段，页面大小为4K，四个段的页面数分别为4、2、2、2，总页面数为10页，此时每一页都属于逻辑上完整的一个段。在段页式系统中，其地址结构由段号、段内页号和页内地址三部分组成，作业地址空间的结构如图3-21所示。

基本原理-1

在段页式系统中，为了实现从逻辑地址到物理地址的变换，系统中必需同时配置段表和页表。由于将段中的页进行离散地分配，段表中的内容不再是段的内存始址和段长，而是页表始址和页表长度。下图说明了利用段表和页表进行地址映射的过程。段号（S）段内页号（P）页内地址（W）P119图3-20段页式系统的作业地址空间P119图3-22利用段表和页表实现地址映射段号状态页表大小页表始址01112130段表段表大小段表始址页号状态存储块号01112130

页

表页号状态存储块号0111

页表2．地址变换过程在段页式系统中，有一个段表寄存器，存放段表始址和段长TL。在进行地址变换时，系统将逻辑地址截成段号S、段内页号P与页内地址W，先用段号S与段长TL进行比较。若S≥TL，表示段号太大，访问越界，于是产生越界中断信号；若S＜TL，表示未越界，于是利用段表始址和段号求出该段对应的段表项在段表中的位置，从中得到该段的页表始址，并利用逻辑地址中的段内页号P来获得对应页的页表项在页表中位置，从中读出该页所在的物理块号b，再用块号b和页内地址W拼成物理地址。图3-23说明了段页式系统中的地址变换机构。地址变换过程-1在段页式系统中，为了获得一条指令或数据，需三次访问内存：第一次访问内存中的段表，从中取得页表始址；第二次访问内存中的页表，从中取出该页所在的物理块号，并将该块号与页内地址一起形成指令或数据的物理地址；第三次访问才是真正根据所得的物理地址取出指令或数据。显然，这使访问内存的次数增加了近两倍。为了提高执行的速度，在地址变换机构中增设一高速缓冲寄存器。每次访问它时，都同时利用段号和页号去检索高速缓存。P120图3-23段页式系统的地址变换机构

+

段表0123

页表0123段表始址段表长度

+段号（S）段内页号（P）页内地址（W）﹥块号b

块内地址越界中断段表寄存器CPU逻辑地址物理地址

b页表始址3．4虚拟存储器管理技术前面所介绍的各种存储器管理方式，有一个共同的特点，即要求将一个作业全部装入内存才能运行。如果有的作业很大，其所要求的内存空间超过了内存总容量，作业就不能全部被装入内存，致使该作业无法运行；有时大量作业要求运行，但由于内存容量不足以容纳所有这些作业，只能将少数作业装入内存让它们先运行，而将其它大量的作业留在外存上等待。显而易见的一种解决方法，是从物理上增加内存容量，但这往往会受到机器自身的限制，而且无疑要增加系统成本，因此这种方法是受到一定限制的；另一种方法是从逻辑上扩充内存容量，这正是虚拟存储技术所要解决的主要问题。

3．4．1虚拟存储器的基本概念

1．局部性原理(principleoflocality)实际上有许多作业在每次运行时，并非用到其全部程序，那么是否可以仅把作业的一部分装入内存就能运行呢？回答是可以的，我们先来研究虚拟存储器系统实现的理论基础：程序执行的局部性规律。早在1968年P．Denning就指出过，程序在执行时将呈现出局部性规律，即在一段时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域内。局部性原理-1那么程序为什么会出现局部性规律呢？原因可以归结为以下几点：程序在执行时，除了少部分的转移和过程调用指令外，大多数仍是顺序执行的。子程序调用将会使程序的执行由一部分内存区域转至另一部分区域。但在大多数情况下，过程调用的深度都不超过5。程序中存在许多循环结构，循环体中的指令被多次执行。程序中还包括许多对数据结构的处理，如对连续的存储空间——数组的访问，往往局限于很小的范围内。局部性原理-2

所以局限性表现为：

时间局限性：如果程序中的某条指令一旦执行，则不久的将来该指令可能再次被执行；如果某个存储单元被访问，则不久以后该存储单元可能再次被访问。产生时间局限性的典型原因是在程序中存在着大量的循环操作。空间局限性：一旦程序访问了某个存储单元，则在不久的将来，其附近的存储单元也最有可能被访问。即程序在一段时间内所访问的地址，可能集中在一定的范围内，其典型原因是程序是顺序执行的。2。虚拟存储器的定义

根据局部性原理，一个作业在运行之前，没有必要把全部作业装入内存，而仅将那些当前要运行的那部分页面或段，先装入内存便可启动运行，其余部分暂时留在磁盘上。程序在运行时如果它所要访问的页（段）已调入内存，便可继续执行下去；但如果程序所要访问的页（段）尚未调入内存（称为缺页或缺段），此时程序应利用操作系统所提供的请求调页（段）功能，将它们调入内存，以使进程能继续执行下去。虚拟存储器的定义-1如果此时内存已满，无法再装入新的页（段），则还须再利用页（段）的置换功能，将内存中暂时不用的页（段）调出至磁盘上，腾出足够的内存空间后，再将所要访问的页（段）调入内存，使程序继续执行下去。这样，便可使一个大的用户程序在较小的内存空间中运行；也可使内存中同时装入更多的进程并发执行。从用户角度看，该系统所具有的内存容量，将比实际内存容量大得多，人们把这样的存储器称为虚拟存储器。虚拟存储器的定义-2虚拟存储器是采用请求调入和置换功能，将内存和外存统一管理，达到把作业的一部分装入内存便可运行，给用户提供的一个比内存容量大的一维的逻辑地址空间。外存内存虚拟存储器逻辑地址虚拟存储器的定义-3

虚拟存储器的逻辑容量由内存和外存容量之和、计算机的地址结构二者所决定，其运行速度接近于内存速度，而每位的成本却又接近于外存。实现虚拟存储技术的物质基础是：一是有相当容量的辅助存储器以存放所有并发作业的地址空间；二是有一定容量的内存来存放运行作业的部分程序；三是有动态地址转换机构，实现逻辑地址到物理地址的转换。可见，虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于大、中、小型机器和微型机中。虚拟存储器实现方式请求分页系统：

它是在分页系统的基础上，增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。它允许只装入若干页（而非全部程序）的用户程序和数据，就可以启动运行，以后再通过调页功能和页面置换功能，陆续把将要运行的页面调入内存，同时把暂不运行的页面置换到外存上，置换时以页面为单位。虚拟存储器实现方式-1请求分段系统：它是在分段系统的基础上，增加了请求调段和分段置换功能所形成的段式虚拟存储系统。它允许只装入若干段（而非全部段）的用户程序和数据，就可以启动运行，以后再通过调段功能和置换功能将不运行的段调出，同时调入将要运行的段，置换以段为单位。请求段页式系统：它是在段页式系统的基础上，增加了请求调页和页面置换功能所形成的段页式虚拟存储系统。3。虚拟存储器的特征离散性：指在内存分配时采用离散的分配方式，它是虚拟存储器的最基本的特征。多次性：指一个作业被分成多次调入内存运行，即在作业运行时没有必要将其全部装入，只须将当前要运行的那部分程序和数据装入内存即可。多次性是虚拟存储器最重要的特征。对换性：指允许在作业的运行过程中在内存和外存的对换区之间换进、换出。虚拟性：指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。3．4．2请求分页存储管理

请求分页存储管理方式是在纯分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页式虚拟存储系统，它是目前常用的一种虚拟存储器的方式。它允许只装人若干页(而非全部页)的用户程序和数据，便可启动运行。以后，再通过调页功能及页面置换功能，陆续地把即将要运行的页面调入内存，同时把暂不运行的页面换出到外存上，置换时以页面为单位。

3．4．2请求分页存储管理

1。请求分页中的硬件支持为了能实现请求调页和置换功能，系统必须提供必要的硬件支持：扩充的页表机制和缺页中断机构。

（1）请求分页的页表机制它是在纯分页的页表机制上形成的，由于只将应用程序的一部分调入内存，还有一部分仍在磁盘上，故需在页表中再增加若干项，供程序(数据)在换进、换出时参考。在请求分页系统中的每个页表项如图所示。

页号物理块号状态位P访问字段A修改位M外存地址请求分页中的硬件支持-1其中各字段说明如下：状态位（中断位P）：用于指示该页是否已调入内存，供程序访问时参考。访问字段A：用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面时参考。修改位M：表示该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本，因此，若未被修改，在置换该页时就不需将该页写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。外存(辅存)地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时使用

(2)缺页中断机构在请求分页系统中，每当所要访问的页面不在内存时，便要产生一缺页中断，请求OS将所缺页调入内存。与一般中断的主要区别在于：缺页中断在指令执行期间产生和处理中断信号，而一般中断在一条指令执行完后检查和处理中断信号。缺页中断返回到该指令的开始重新执行该指令，而一般中断返回到该指令的下一条指令执行。一条指令在执行期间，可能产生多次缺页中断。(3)地址变换机构

请求分页系统中的地址变换机构，是在分页系统的地址变换机构的基础上，再为实现虚拟存储器