OS--第三章 徐宗元.ppt

1、第三章 存储管理 (Memory Management),存储器是计算机系统的重要组成部分，所以存储器的管理是操作系统最主要的功能之一。当程序的指令和数据当以文件的形式存放在磁盘上时，是不能被CPU访问的，只有当被调入内存（RAM）里才能被CPU直接访问，程序才能够被执行。虽然目前的RAM芯片的集成度在不断地提高，从原来的几百到现在的几百兆甚至上千兆，价格也在不断地降低，但是软件系统需要的内存容量也在不断地增加，所以内存的容量仍然是计算机硬件中最关键的、且又是最紧张的“瓶颈”资源。如何对存储器进行有效的管理，不仅直接影响到它的利用率，而且还对系统的性能有重大影响。存储管理的主要对象是内存。,教

2、学要求,熟悉存储管理目的和功能，掌握地址重定位的概念。 熟悉单一连续分配、固定分区分配、动态分区分配实现原理；掌握可变分区分配的数据结构和分配回收算法，熟悉可变分区零头和拼接技术 。 熟练掌握分页存储管理原理，熟练掌握分页存储管理基本的地址变换机构和具有快表的地址变换机构。 掌握分段存储管理原理和分段地址变换机构，掌握分页和分段比较，熟悉分页和分段的共享，掌握段页式存储管理原理和地址变换机构。,教学要求-1,掌握虚拟存储器的理论基础和定义，熟悉虚拟存储器实现方式和特征。 掌握请求分页的页表机制、缺页中断机构和地址变换机构，熟悉页面的分配和置换策略、页面的分配的算法。 熟练掌握最佳置换算法、先进

3、先出（FIFO）置换算法、最近最久未使用置换算法LRU，熟悉Clock置换算法和页面缓冲算法；熟悉有效访问时间计算，了解工作集概念。 掌握请求分段的段表机制、缺段中断机构和地址变换机构，熟悉分段的共享和保护。,存储管理目录,31 存储管理概述 311存储层次结构 312存储管理的功能 313 地址重定位 32 存储器的连续分配 321单一连续分配 322固定分区分配 323可变（动态）分区分配 33存储器的离散分配 331纯分页存储管理 332 分段存储管理 333 段页式存储管理,存储管理目录-1,34虚拟存储器管理技术 341虚拟存储器的基本概念 342请求分页存储管理 343请求分段存储

4、管理 35 Windows2000内存的管理 351Intel x86/Pentium系列CPU对内存管理的硬件支持机制 352 Windows2000地址空间的划分 353 Windows2000用户空间内存分配和使用 354页面调度策略 355物理内存管理 35. 6 Windows 2000高速缓冲管理,存储管理目录-2,36 实验与习题 361实验一：在Windows2000下评价内存和缓存使用 362 实验2：Windows 2000 内存管理API函数的使用 363 选择题 364 问答题,31 存储管理概述,311存储层次结构 存储器是处理器处理的信息的来源与归宿，占据着重要地位

5、。但任何一种存储设备都无法在速度与容量两个方面同时满足用户的需求。为解决速度和容量之间的矛盾，冯诺依曼计算机系统中，采用了三级或更多级的存储器来组成存储层次结构，高一级为CPU寄存器和高速缓存器，中间是主存(可执行的存储器)，最低一级为辅存。通过采用特殊的存储技术，主存与辅存两级可以进一步优化成多级。在存储层次结构中，高层的存储器往往是速度很快、但成本高使容量有限，而接近底部的存储器容量很大、成本低，相对访问速度则慢。各种存储设备组成存储层次结构，如图51所示。,存储层次结构图,存储层次结构-1,存储器的功能是保存数据，存储器的发展方向是高速、大容量和小体积。 内存在访问速度方面的发展：DRA

6、M、SDRAM、SRAM等； 硬盘技术在大容量方面的发展：接口标准、存储密度等； 存储组织是指在存储技术和CPU寻址技术许可的范围内组织合理的存储结构。 其依据是访问速度匹配关系、容量要求和价格。 “寄存器-内存-外存”结构 “寄存器-缓存-内存-外存”结构； 微机中的存储层次组织： 访问速度越慢，容量越大，价格越便宜； 最佳状态应是各层次的存储器都处于均衡的繁忙状态（如：缓存命中率正好使主存读写保持繁忙）；,存储层次结构图-1,存储层次结构图-2,存储层次结构图-3,312存储管理的功能,操作系统为了有效地管理计算机的内存资源，应该具备以下四大功能：内存分配、内存保护、地址映射、内存扩充。

7、11.内存分配 内存分配的主要任务是：为每一道程序分配内存空间，使它们“各得其所”；当程序撤消时，则收回它占用的内存空间。分配时注意提高存储器的利用率。 2地址映射 目标程序所访问的地址是逻辑地址集合的地址空间，而内存空间是内存中物理地址的集合，在多道程序环境下，这两者是不一致的，因此，存储管理必须提供地址映射功能，用于把程序地址空间中的逻辑地址转换为内存空间中对应的物理地址。,存储管理的功能-1,2。存储保护 内存保护的任务是确保每道程序都在自己的内存空间运行，互不干扰。保护系统程序区不被用户侵犯（有意或无意的），不允许用户程序读写不属于自己地址空间的数据（系统区地址空间，其他用户程序的地址

8、空间）。 3。提高主存储器的利用率 减少不可用的存储空间（称为“零头），允许多道程序动态共享主存。 4。内存扩充 内存扩充的任务是从逻辑上来扩充内存容量，使用户认为系统所拥有的内存空间远比其实际的内存空间（硬件RAM）大的多。,313 地址重定位,1。名字空间、地址空间和存储空间 在源程序中，是通过符号名来访问子程序和数据的，我们把程序中符号名的集合称为“名字空间”。汇编语言源程序经过汇编，或者高级语言源程序经过编译，得到的目标程序是以“0”作为参考地址的模块。然后多个目标模块由连接程序连接成一个具有统一地址的装配模块，以便最后装入内存中执行。我们把目标模块中的地址称为相对地址（或称为“逻辑地

9、址”），而把相对地址的集合称为“相对地址空间/逻辑地址空间”或简称为“地址空间”。,名字空间、地址空间和存储空间-1,装配模块虽然具有统一的地址空间，但是仍是以“0”作为参考地址，即是浮动的。要把它装入内存执行，就要确定装入内存的实际物理地址，并修改程序中与地址有关的代码，这一过程称为地址重定位。 地址空间的程序和数据经过地址重定位处理后，就变成了可由CPU直接执行的绝对地址程序。我们把这一地址集合称为“绝对地址空间”或“存储空间”。程序的名字空间、地址空间和存储空间之间的关系如图所示。,名字空间、地址空间和存储空间-2,逻辑地址、物理地址和地址映射,2。地址重定位,地址重定位完成把相对地址转

10、换成内存中的绝对地址，这个过程称为地址映射（map）。按照重定位的时机，可分为静态重定位和动态重定位。 静态重定位 静态重定位是在程序执行之前进行重定位。它根据装配模块将要装入的内存起始地址，直接修改装配模块中的有关使用地址的指令。 在图中以“0”作为参考地址的装配模块，要装入以10000为起始地址的存储空间。显然在装入程序之前，程序必须做一些修改才能正确运行。,地址重定位-1,例如：LOAD 1，2500 这条指令是把相对地址为2500的存储单元的内容365装入1号累加器。而这时内容为365的存储单元的实际物理地址为12500（起始地址10000+相对地址2500），所以LOAD 1，250

11、0 这条指令中的直接地址码要作相应的修改，即改为LOAD 1，12500。,地址重定位-2,地址重定位-3,为了支持静态重定位，连接程序在生成统一地址空间和装配模块时，还应产生一个重定位项表，该表的每一项重定位项是在程序中需要修改地址的位置，操作系统的装入程序要把装入模块和重定位项表一起装入内存。程序装入内存中的起始地址称为重定位因子，由装配模块的实际装入起始地址得到重定位因子，然后取重定位项，把重定位项表示地址的内容进行修改，即把重定位项表示地址的内容加上重定位因子，从而完成指令代码的修改。当完成重定位后，就可以启动程序执行。 静态重定位虽然有无须硬件支持的优点，但是也存在明显的缺点：一是程

12、序重定位以后就不能在内存中移动；二是要求程序的存储空间是连续的，不能把程序存储到若干个不连续的区域中。,地址重定位-4,说明：重定位表中列出所有修改的位置。如：重定位表的150表示相对地址150处的内容为相对地址(即100为从0起头的相对位置)。在装入时，要依据重定位后的起头位置(2000)修改相对地址。 重定位修改：重定位表中的150-绝对地址2150(=2000+150) 内容修改：内容100变成2100(=100+2000)。,动态重定位,动态重定位是指在程序执行过程中进行地址重定位，即在每次访问内存单元前才进行地址变换。动态重定位可使装配模块不加任何修改就装入内存，但是它需要硬件重定位

13、寄存器的支持。下图给出了动态重定位的示意图。 程序的目标模块在装入内存时，与地址有关的指令都无须进行修改，如在图3-4中LOAD 1，2500这条指令中仍保持相对地址2500。当该指令被操作系统取到中央处理器指令寄存器上执行时，操作系统首先把该模块装入的实际起始地址减去目标模块的相对基地址（图3-4中该模块的基地址为0），然后将其差值10000装入重定位寄存器。,动态重定位的示意图,动态重定位-1,当CPU执行该指令时，地址变换硬件逻辑自动将指令中的逻辑地址2500与重定位寄存器中的值相加，再根据和值作为内存的绝对地址去访问该单元的数据，读入的数据送到寄存器1。完成地址变换硬件是属于存储管理部

14、件 MMU，目前它已集成到中央处理器CPU中。 由此可见，动态重定位是在指令执行过程中动态进行，它由硬件完成，这样可以带来两个好处：目标程序装入内存时无需任何修改，所以装入之后再移动也不会影响其正确运行，这便于存储器用紧缩来解决存储器的碎片问题。一个程序由若干个相对独立的目标模块组成时，每个目标模块各装入一个存储区域，这些存储区域可以不相领接，只要各个模块有自己对应的重定位寄存器就可以了。,3.链接,静态链接(static-linking)是在生成可执行文件时进行的。在目标模块中记录符号地址(symbolic address)，而在可执行文件中改写为指令直接使用的数字地址。,有一个程序P（如图

15、所示），它既可以被其它程序调用（通过用符号定义的入口点如P, e, d），也可以调用别的程序模块。前一种情况称为内部定义符号，后者称为外部调用符号。一个源程序经编译或汇编后生成的可重定位目标模块必须明显地给出这些内部符号和外部符号，以供连接装入程序使用。 每个可重定位目标段相关联的除重定位表（又称重定位词典）或指示字外，还应有一张内部定义符号表和外部调用符号表。,链接例-1,链接例-2,CALL SUB1,ADD TIME,内部定义符号：P, e, d。外部调用符号：SUB1, TIME。,P,e,d,内部定义符号表,符号名,地址,Ped,SUB1TIME,Pe,CALL*,ADD*,d,.,

16、外部调用符号表,重定位词典,.,.,代码和数据区,链接例-3,动态链接,动态链接(dynamic-linking)在装入或运行时进行链接。通常被链接的共享代码称为动态链接库(DLL, Dynamic-Link Library)或共享库(shared library)。 优点：共享：多个进程可以共用一个DLL，节省内存，减少文件交换。 部分装入：一个进程可以将多种操作分散在不同的DLL中实现，而只将当前操作相应的DLL装入内存。 便于局部代码修改：即便于代码升级和代码重用；只要函数的接口参数（输入和输出）不变，则修改函数及其DLL，无需对可执行文件重新编译或链接。 便于运行环境适应：调用不同的D

17、LL，就可以适应多种使用环境和提供不同功能。如：不同的显示卡只需厂商为其提供特定的DLL，而OS和应用程序不必修改。 缺点：链接开销：增加了程序执行时的链接开销； 管理开销：程序由多个文件组成，增加管理复杂度。,32 存储器的连续分配,321单一连续分配 这是一种最简单的存储管理方式，但只能用于单用户、单任务的操作系统，如在8位和16位微机上CP/M和MS-DOS操作系统。它将内存分为两个区： 系统区：仅供操作系统使用，通常设置在内存的低段； 用户区：指除系统区以外的全部内存空间，提供给用户使用。 这种存储分配方式由于用在单用户、单任务的操作系统中。,单一连续分配-1,单一连续区存储管理,32

18、2固定分区(Fixed Partitioning)分配,分区存储管理是能够满足多道程序运行的最简单的存储器管理方案，其基本思想是将内存划分成若干个连续的区域，称为分区。每个分区只能储存一个程序，而且程序也只能在它所驻留的分区中运行。分区存储管理根据分区个数及分区大小的可变性分为固定式分区和可变式分区两种。 固定分区是在作业装入之前，内存就被划分成若干个分区。划分工作可以由系统管理员完成，也可以由操作系统实现。然而一旦划分完成，在系统运行期间不再重新划分，即分区的个数不可变，分区的大小不可变，所以，固定式分区又称为静态分区。 这种分区方式一般将内存的用户区域划分成大小不等的分区，以适应不同大小的

19、作业的需要。系统有一张分区说明表，每个表目说明一个分区的大小、起始地址和是否已分配的使用标志。分区说明表和内存分配图如下所示。,固定分区分配-1,区号 大小 起址 标志 1 16KB20K已分配 2 32KB36K已分配 3 64KB68K已分配 4 124KB 132K 未分配 (a) 分区说明表 固定式分区实现技术简单 ，但是内存的利用率不高， 适用于作业的大小和多少事 先都比较清楚的系统中。它 用于60年代的IBM-360的MFT 操作系统中。,固定分区分配-2,由于每个分区的大小是固定的，所以每个提出运行的作业必须说明所需的最大内存容量。在调度作业时，存储管理程序根据作业所需的内存容量

20、，在分区说明表中找出一个足够大的空闲分区分配给它，然后用重定位装入程序将此作业装入。如果找不到，则通知作业调度模块，选择另外一个作业。图3-6（b）说明了某一时刻，作业A、B、C分别被分配到1，2，3三个分区中，第四个分区尚未分配，操作系统则永久占据内存低地址区20KB的空间。当一个作业结束时，系统又调用存储管理程序查到分区说明表，把所占分区的使用标志修改为未分配状态即可。,固定分区分配-3,采用这种技术，虽然可以使多个作业共驻内存，但是一个作业的大小不可能正好等于某个分区的大小，所以每个被分配的分区总有一部分被浪费，我们把这部分被浪费的存储区称为内零头或内碎片。有时这种分配方式浪费相当严重，

21、如图3-6（b）中第3分区未分配的部分还有8KB，加上第4分区的124KB共计132KB，而且这132KB的内存空间在物理上是一个连续的区域，这时如果有一个大小为130KB的作业申请内存，却被拒绝，因为分区的大小是预先划分好的，分区说明表中指出只有第4分区未分配（大小为124K），且不能改变分区的大小。,Multiprogramming with Fixed Partitions,Fixed memory partitions separate input queues for each partition single input queue,323可变（动态） (Dynamic Parti

22、tioning)分区分配,1. 可变分区概述 可变分区是指在作业装入内存时，从可用的内存中划出一块连续的区域分配给它，且分区大小正好等于该作业的大小。可变分区中分区的大小和分区的个数都是可变的，而且是根据作业的大小和多少动态地划分，因此又称为动态分区。这种存储管理技术是固定式分区的改进，既可以获得较大的灵活性，又能提高内存的利用率。 系统初始化后，内存被划分成两块，一块用于常驻的操作系统，另一块则是完整的空闲区（用户区）。对于调入的若干个作业，划分几个大小不等的分区给它们，随着作业的调入和撤除，相应的分区被划分和释放，原来整块的存储区形成空闲区和已分配区相间的局面。图3-7（c）给出了可变式分

23、区的示例，512KB内存中除20KB操作系统外，装入作业2、3、4、6四个，有空闲区1、2、3三个。,可变式分区数据结构图表,序号P大小起址状态 132k20k空闲 256k260k空闲 3 116k396k空闲 4空表目 5空表目 （a）空闲分区表,返回,可变分区概述-1,可变式分区的分配和释放的基本思想是：在分配时，首先找到一个足够大的空闲分区，即这个空闲区的大小比作业要求的要大，系统则将这个空闲分区分成两部分：一部分成为已分配的分区，剩余的部分仍作为空闲区。在回收撤除作业所占领的分区时，要检查回收的分区是否与前后空闲的分区相领接，若是，则加以合并，使之成为一个连续的大空间。,Exampl

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

25、cement Algorithm),(1)最佳适应算法BF（Best Fit）：它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按大小从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区，但造成许多小的空闲区。 (2)首次适应算法FF（First Fit）：从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区，在低址空间造

26、成许多小的空闲区，在高地址空间保留大的空闲区。,可变分区分配算法-1,(3)循环首次适应算法NF(Next Fit)：该算法是首次适应算法的变种，它把空闲分区表（空闲区链）中的空闲分区按地址递增构成一个循环链。在分配内存空间时，不再每次从表头（链首）开始查找，而是从上次找到的空闲区的下一个空闲区开始查找，直到找到第一个能满足要求的的空闲区为止，并从中划出一块与请求大小相等的内存空间分配给作业。该算法能使内存中的空闲区分布得比较均匀。 (4)最坏适应法：从所有未分配的分区中挑选最大的且大于和等于作业大小的分区分给要求的作业；空闲分区按大小由大到小排序。该算法使小的空闲区减少，但造成大的空闲区不够

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

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

29、闲区合并，修改F2分区的表目，把回收区的起址作为新空闲区的起址，大小为两个分区之和。 (4)当回收区与插入点的前、后两个分区（F1和F2）都相领接时（如图3-9（d），合并三个分区，用F1表目的起址作为新空闲区的起址，修改其大小为三块分区之和，最后取消F2的表目。 图3-7（c）内存分配图中作业3、2、4、6分别回收时相当于图3-9（a）、（b）、（c）、（d）内存回收时的情况。,可变分区回收算法 -2,可变分区回收算法 -3,对于前图所示的可变式分区内存分配图，下列四种情况分别如下图所示：,可变分区回收算法 -4,作业3回收前后 序号P大小起址状态 132k20k空闲 256k260k空闲

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

31、号P大小起址状态 132k20k空闲 256k260k空闲 3 116k396k空闲 4空表目 5空表目 （a）空闲分区表 序号P 大小 起址 状态 1 32k 20k 空闲 2 152k 164k 空闲 3 116k 396k 空闲 4 空表目 5 空表目 空闲分区表,可变分区回收算法 -7,作业6回收前后 序号P大小起址状态 132k20k空闲 256k260k空闲 3 116k396k空闲 4空表目 5空表目 （a）空闲分区表 序号P 大小 起址 状态 1 32k 20k 空闲 2 252k 260k 空闲 3 空表目 4 空表目 5 空表目 空闲分区表,作业6（80k）,空闲区4（11

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

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

34、“碎片”，为了减少碎片提高存储器的利用率而引入了离散分配方式,它将一个用户的程序划分成若干个大小相等的页再离散地分配到内存的多个不相邻的区域中。,331纯分页(Paging)存储管理,1分页存储管理原理 分页存储管理是将一个进程的地址空间划分成若干个大小相等的片，称为页面或页，相应地，将内存空间划分成与页相同大小的若干个块，称为（物理）块或页框。在为进程分配内存时，将进程中的若干页离散地装入不相邻接的物理块中。由于页面的大小一般取2的幂次个字节，通常在512B到4KB之间，所以内存空间划分后不存在“外碎片”。由于每块物理块可离散地分配给进程的一页，这样不断地分配，直到剩余的物理块数不能满足一个

35、进程的要求为止。而对每个进程只有最后一页经常装不满一块，平均产生半页“页内碎片”。由此可知，分页存储管理解决了“碎片”问题，提高了存储器的利用率。纯分页存储管理是指一个进程的所有页全部装入内存的物理块中才能运行。,分页存储管理原理-1,分页系统的地址结构如图3-11所示，它由两部分组成：前一部分为页号P；后一部分为页内位移量W，即页内地址。图中的地址长度为16位，其中09位为页内地址（每页的大小为1KB），1015位为页号，所以允许地址空间的大小最多为64个页。,2页表,在将进程的每一页离散地分配到内存的各个物理块中后，系统为了保证进程的正确运行，即能在内存中找到该进程每个页面所对应的物理块，

36、系统需为每页配一个重定位寄存器，由于重定位寄存器是硬件，在页面数很多时实现困难。为此，系统在内存为每个进程建立了一张页面映射表，简称页表（如图3-12所示）。每个页在页表中占一个表项，记录该页在内存中对应的物理块号（页号可以省略）。进程在执行时，通过查找页表，就可以找到每页所对应的物理块号。可见，页表的作用是实现从页号到物理块号的地址映射。,页表 -1,3地址变换机构,地址变换机构的基本任务是利用硬件实现查页表把用户程序中的逻辑地址变换成内存中的物理地址。为了实现地址变换功能，在系统中设置页表寄存器，用来存放页表的始址和页表的长度。在进程未执行时，每个进程对应的页表的始址和长度存放在进程的PC

37、B中，当该进程被调度时，就将它们装入页表寄存器。在进行地址变换时，系统将逻辑地址截成页号和页内地址二部分，将页号与页表长度进行比较，如果页号大于等于页表寄存器中的页表长度，则访问越界，产生越界中断。如未出现越界，则根据页表寄存器中的页表始址和页号计算出该页在页表项中的位置，查页表得到该页的物理块号，将物理块号与逻辑地址中页内地址二者拼接成物理地址，这样便完成了从逻辑地址到物理地址的变换。,地址变换机构-1,图3-13说明了分页系统的地址变换机构，地址变换机构是由硬件完成，包括自动地查内存的页表。图中举例说明CPU指令寄存器在执行Load 1,2500指令时，地址变换机构自动地完成了逻辑地址25

38、00到物理地址5572的变换，将地址为5572内存的数据读入，送入寄存器1。完成从逻辑地址到物理地址的变换的地址变换机构又称为存储管理部件MMU，它由硬件完成，并由于超大规模集成电路的发展，MMU已集成到CPU集成块中。,地址变换机构图,分页存储管理逻辑地址到物理地址地址变换的计算,假设页长为1KB(1024字节)，逻辑地址为2500(十进制)。利用页表把逻辑地址变换成物理地址计算步骤如下： (1)将虚地址分离成页号P和页内地址d： 页号P（逻辑地址页大小）取整（2500/1024）取整2 页内地址d逻辑地址 mod 页大小=2500 mod 1024=452 (2)根据页号查页表，由页表项读

39、出块号： 由页号 P2查页表得块号为5 (3)块号和页内地址构成物理地址： 物理地址块号页大小页内地址= 5*1024+452 =5572,分页存储管理逻辑地址到物理地址地址变换的计算-1,十六进制逻辑地址09C4H 1KB 1024 400H C00H09C4H800H页 号2 2KB 2048 800H 页内地址逻辑地址 该页头地址 3KB 3072 C00H 09C4H800H1C4H 4KB 4096 1000H查页表 页 号2 块号5 5KB 5120 1400H 物理地址该块头地址 +页内地址 6KB 6144 1800H = 1400H + 1C4H = 15C4H,地址变换机构

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

41、不能省略）。在快表的输入寄存器输入页号后，输入页号与快表中的各页表项中的页号同时比较，如有相同，快表的输出寄存器输出相应的块号，如都不相同，快表的输出寄存器不输出。快表存取速度快，但由于成本的原因，快表不可能做得很大，大程序的页表项不可能全部放在快表中。为此，把各进程的页表仍放在内存的系统区中，而系统增加的快表用以存放正在运行进程的、当前常用的部分页面的页号和相应的块号。,快表-1,此时地址变换过程为：CPU给出逻辑地址并将逻辑地址截成页号和页内地址二部分后，地址变换机构先将页号送入快表的输入寄存器，确定所需要的页是否在快表中。若是，则直接读出该页所对应的物理块号，与逻辑地址中页内地址二者拼接

42、成物理地址；若在快表中未找到对应的页表项，则需再访问内存中的页表，找到后，把从页表中读出的页表项存入快表中的一个寄存器单元中，以取代一个旧的页表项，同时将此物理块号与逻辑地址中页内地址二者拼接成物理地址，并访问主存。图3-14说明了具有快表的地址变换机构。 由于成本的原因，快表不可能做得很大，通常只能存放16512个页表项。例如，在Intel80486中有32个。这对中、小型作业来说，已可能把全部页表项放入快表中；但对于大型作业来说，则只能将一部分页表放入快表中。,快表-2,由于对程序和数据的访问往往带有局限性，所以快表的命中率可以达到80%99%。例如，假设检索联想存储器的时间T(联想)为2

43、0ns，访问内存的时间T(内存)为100ns，访问联想存储器的的命中率p为90%。 当快表命中时CPU存取内存一个数据的时间为 T1检索快表时间访问内存数据时间=T(快表)+T(内存) 20100120ns。 当快表不命中时CPU存取内存一个数据的时间为 T2检索快表时间检索内存中的页表时间访问内存数据时间=T(快表)+T(内存) +T(内存)20100100220ns。 则CPU存取内存一个数据的平均时间为 T = T1*命中率+T2*（1命中率）= T1*+T2*(1-)= 120*0.9+220*0.1 = 130ns。访问时间增加为(T- T(内存)T(内存)=(130-100) 10

44、0=30%。如果不引入快表，其访问将延长一倍（达200ns）。,具有快表的地址变换机构图,332 分段(Segmentation)存储管理,1分段存储管理的引入 从固定分区到可变分区，进而又发展到分页系统的原因都是为了提高内存的利用率，然而分段存储管理的引入，是为了满足用户需要。 分页存储管理时的进程地址空间结构都是线性的，这要求对各段源程序编译成目标程序后还要静态链接，例如图3-15把四个源程序段编译后的目标程序段：主程序段main（15KB）、子程序段X（5KB）、数据段D（6KB）、堆栈段S（7KB）按线性空间的一维地址顺序排列起来，再分成8页，每页为4KB。,分段存储管理的引入-1,分

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

46、译后都是从零开始编址的一段连续的地址空间，段的长度由相应逻辑信息组的长度决定，因而各段长度是不等的。分段系统的地址结构如图3-16所示，逻辑地址由段号和段内地址两部分组成。在该地址结构中，允许一个作业最多有64 K个段，每个段的最大长度为64 KB。图3-17中一个作业有四个段：主程序段MAIN、15KB长、段号为0，子程序段X、5KB长、段号为1，数据段D、6KB长、段号为2，堆栈段S、7KB长、段号为3。,3段表,在分段式存储管理系统中，为每个段分配一个连续的分区，而进程中的各个段可以离散地分配到内存中不同的分区中。类同分页式存储管理，在分段式存储管理系统中为每个进程建立一张段映射表，简称

47、为“段表”。每个段在表中占有一表项，在其中记录了该段在内存中的起始地址（又称为“基址”）和段的长度，在图3-17中，上述作业的四个段分别分配到内存中起始地址为40K、120K、160K、200K四个不同的分区中。进程在执行中，通过查段表来找到每个段所对应的内存区。可见，段表实现了从逻辑段到物理内存区的映射。,内存空间 0 40k： 80k： 120k： 150k：,段表的作用图,4地址变换机构,为了实现从逻辑地址到物理地址的变换功能，系统中设置了段表寄存器，用于存放段表始址和段表长度。在进行地址变换时，系统将逻辑地址截成段号S与段内地址d，将逻辑地址中的段号S与段表长度TL进行比较。若 STL

48、，表示段号太大，访问越界，于是产生越界中断信号；若未越界，则根据段表的始址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存中的起始地址，然后再检查段内地址d是否超过该段的段长SL。若超过，即dSL，同样发出越界中断信号；若未越界，则将该段的基址与段内地址d相加，得要访问的内存物理地址。图3-18给出了分段系统的地址变换过程。,地址变换机构图,段号 段长SL 基址,地址变换机构图-1,地址变换机构图(地址映射及存储保护机制),Segmentation Hardware,5共享,段是信息的逻辑单位,因此分段系统的一个突出的优点是易于实现段的共享。即允许若干个进程共享一个或多个段，而且对

49、段的保护也十分简单。在分页系统中，虽然也能实现程序和数据的共享，但远不如分段系统来得方便。分段系统中，每个进程的段表中设置一个段表项。图是分段系统中共享 editor编辑程序的示意图。 在实现段共享时，需要用到可重入代码(Reentrant Code)又称为“纯代码”(Pure Code)。它是一种允许多个进程同时访问的代码，是一种不允许任何进程对其进行修改的代码。但在每个进程中，配以局部数据区，将在执行中可能改变的部分，拷贝到该数据区，这样，程序在执行时，只对该数据区(属于该进程私有)中的内容进行修改，而不去改变共享的代码，这时的可共享代码即成为可重入代码。,共享-1,段 表,6分页和分段的

50、主要区别,分页和分段的主要区别-1,333 段页式存储管理,分页和分段存储管理方式都各有其优缺点。如果对两种存储管理方式“各取所长”后，则可以形成一种新的存储管理方式的系统段页式系统。它以分页的方式管理内存，具有分页系统能有效地提高内存利用率的优点；又以分段的方式管理用户的逻辑地址空间，具有分段系统能很好地满足用户需要的长处，显然是一种比较有效的存储管理方式。,1基本原理,段页式系统的基本原理是将内存空间划分成相同大小相同的若干个块，将用户程序先按逻辑完整性分为若干个段，并为每个段赋予一个段名，再把每个段划分成若干个与块大小相同的页，将进程中的若干页离散装入不相邻接的块中。图3-20中示出了一

51、个作业地址空间结构，该作业有四个段，页面大小为4K，四个段的页面数分别为4、2、2、2，总页面数为10页，此时每一页都属于逻辑上完整的一个段。在段页式系统中，其地址结构由段号、段内页号和页内地址三部分组成，作业地址空间的结构如图3-21所示。,基本原理-1,在段页式系统中，为了实现从逻辑地址到物理地址的变换，系统中必需同时配置段表和页表。由于将段中的页进行离散地分配，段表中的内容不再是段的内存始址和段长，而是页表始址和页表长度。下图说明了利用段表和页表进行地址映射的过程。,段页式系统的作业地址空间,段表、页表的作用,2地址变换过程,在段页式系统中，有一个段表寄存器，存放段表始址和段长TL。在进

52、行地址变换时，系统将逻辑地址截成段号S、段内页号P与页内地址W，先用段号S与段长TL进行比较。若 STL，表示段号太大，访问越界，于是产生越界中断信号；若STL，表示未越界，于是利用段表始址和段号求出该段对应的段表项在段表中的位置，从中得到该段的页表始址，并利用逻辑地址中的段内页号P来获得对应页的页表项在页表中位置，从中读出该页所在的物理块号b，再用块号 b和页内地址W拼成物理地址。图3-23说明了段页式系统中的地址变换机构 。,地址变换过程-1,在段页式系统中，为了获得一条指令或数据，需三次访问内存：第一次访问内存中的段表，从中取得页表始址；第二次访问内存中的页表，从中取出该页所在的物理块号

53、，并将该块号与页内地址一起形成指令或数据的物理地址；第三次访问才是真正根据所得的物理地址取出指令或数据。显然，这使访问内存的次数增加了近两倍。为了提高执行的速度，在地址变换机构中增设一高速缓冲寄存器。每次访问它时，都同时利用段号和页号去检索高速缓存。,段页式系统的地址变换机构图,34虚拟存储器管理技术,前面所介绍的各种存储器管理方式，有一个共同的特点，即要求将一个作业全部装入内存才能运行。如果有的作业很大，其所要求的内存空间超过了内存总容量，作业就不能全部被装入内存，致使该作业无法运行；有时大量作业要求运行，但由于内存容量不足以容纳所有这些作业，只能将少数作业装入内存让它们先运行，而将其它大量

54、的作业留在外存上等待。显而易见的一种解决方法，是从物理上增加内存容量，但这往往会受到机器自身的限制，而且无疑要增加系统成本，因此这种方法是受到一定限制的；另一种方法是从逻辑上扩充内存容量，这正是虚拟存储技术所要解决的主要问题。,341虚拟存储器的基本概念,1局部性原理(principle of locality) 实际上有许多作业在每次运行时，并非用到其全部程序，那么是否可以仅把作业的一部分装入内存就能运行呢？回答是可以的，我们先来研究虚拟存储器系统实现的理论基础：程序执行的局部性规律。 早在1968年PDenning就指出过，程序在执行时将呈现出局部性规律，即在一段时间内，程序的执行仅局限于

55、某个部分；相应地，它所访问的存储空间也局限于某个区域内。,局部性原理-1,那么程序为什么会出现局部性规律呢？原因可以归结为以下几点： 程序在执行时，除了少部分的转移和过程调用指令外，大多数仍是顺序执行的。 子程序调用将会使程序的执行由一部分内存区域转至另一部分区域。但在大多数情况下，过程调用的深度都不超过5。 程序中存在许多循环结构，循环体中的指令被多次执行。 程序中还包括许多对数据结构的处理，如对连续的存储空间数组的访问，往往局限于很小的范围内。,局部性原理- 2,所以局限性表现为： 时间局限性：如果程序中的某条指令一旦执行，则不久的将来该指令可能再次被执行；如果某个存储单元被访问，则不久以

56、后该存储单元可能再次被访问。产生时间局限性的典型原因是在程序中存在着大量的循环操作。 空间局限性：一旦程序访问了某个存储单元，则在不久的将来，其附近的存储单元也最有可能被访问。 即程序在一段时间内所访问的地址，可能集中在一定的范围内，其典型原因是程序是顺序执行的。,2。虚拟存储器的定义,根据局部性原理，一个作业在运行之前，没有必要把全部作业装入内存，而仅将那些当前要运行的那部分页面或段，先装入内存便可启动运行，其余部分暂时留在磁盘上。程序在运行时如果它所要访问的页（段）已调入内存，便可继续执行下去；但如果程序所要访问的页（段）尚未调入内存（称为缺页或缺段），此时程序应利用操作系统所提供的请求调

57、页（段）功能，将它们调入内存，以使进程能继续执行下去。如果此时内存已满，无法再装入新的页（段），则还须再利用页（段）的置换功能，将内存中暂时不用的页（段）调出至磁盘上，腾出足够的内存空间后，再将所要访问的页（段）调入内存，使程序继续执行下去。这样，便可使一个大的用户程序在较小的内存空间中运行；也可使内存中同时装入更多的进程并发执行。从用户角度看，该系统所具有的内存容量，将比实际内存容量大得多，人们把这样的存储器称为虚拟存储器。,虚拟存储器的定义-1,虚拟存储器是采用请求调入和置换功能，将内存和外存统一管理，达到把作业的一部分装入内存便可运行，给用户提供的一个比内存容量大的一维的逻辑地址空间。

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

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