第4章+存储管理.ppt

1、第4章 存储管理,目录,41 存储管理的目的和功能 42 存储分配 4. 3 重定位 44 实存管理技术 45 虚存管理技术,存储器是计算机系统的重要资源之一。计算机系统的存储器可以分成两类：主存储器（简称主存或内存）和辅助存储器（简称辅存或外存）。计算机的中央处理器可以直接从主存中存取指令和数据，主存容量的大小是计算机系统的一个重要性能指标。,41 存储管理的目的和功能,主存空间分为两部分：系统区和用户区。系统区用来存放操作系统与硬件的接口信息（例如，新旧处理机状态字、定时时间、外围设备的工作情况等）、操作系统的管理信息（例如，进程的PCB）和程序、标准子程序等。其余的存储空间都属于用户区，

2、用来存放用户的程序和数据。存储管理就是对主存空间的用户区进行管理，其目的和功能如下： (1) 对主存空间进行分配和管理 (2)提高主存的利用率 (3) “扩充”主存容量 (4) 实现地址的变换,42 存储分配,所谓存储分配就是要解决多道作业之间划分主存空间的问题。通常将存储器分为两级，即主存和辅存。因此，存储分配要确定在什么时候把哪些信息放在哪一级存储器上，而这些对用户来讲都是“透明”的（即不需要用户知道）。系统中有一个存储分配程序，它依照一定的算法实现内存分配。,常用的主存分配有三种方式 : 静态分配 直接方式 动态分配,直接方式 直接方式是早期的计算机所使用的一种方式。当时多道程序技术还没

3、有出现，存储器的可用空间一般是给定的。那时程序员在编程序时或编译程序对源程序进行编译时，使用实际的存储器地址，这种分配方式使用户与计算机内存直接打交道，系统资源在某一时刻为一个用户所独占。,静态分配 静态分配是在装入程序把一个或一组目标模块进行链接装入内存时就确定它们在主存的相对位置。作业一旦进入主存后，在运行过程中就不能在主存空间中“搬家”（或移动）。,动态分配 作业在存储空间的位置也是装入时确定的，但在作业运行的过程中，允许它在存储空间中“搬家”（也称为允许浮动或移动），而且也允许作业临时申请附加的存储空间。 目前绝大多数计算机系统采用动态或静态存储分配策略，这是由于计算机硬件和程序设计技

4、术的发展等方面的原因。,4. 3 重定位,在多道程序环境中，各用户作业独立编程，单独编译，它们装入系统的时间也不同，因此，只有在装入时才确定存储分配问题，而在编译时是不需要考虑的，即采用动态分配或静态分配方式。为了实现这两种分配策略，则必须把逻辑地址与物理地址分开，对逻辑地址采用地址重定位技术。,名字空间 当用户在使用汇编语言或高级语言编写程序时，是通过符号名来访问子程序和数据的。我们把程序中符号名的集合称为“符号名空间”或“名空间”。符号名空间是用户所编写的源程序所限定的空间，源程序存在的地址范围称之为名字空间。,地址空间 汇编语言源程序经过汇编，或者高级语言源程序经过编译所得到的目标程序是

5、以“0”作为参考（或相对）地址的程序。这个相对地址的目标程序是由多个目标模块由链接程序链接而成的一个具有统一地址的装配模块，以便最后装入内存运行。我们把目标模块中的地址称为逻辑地址，而把逻辑地址的集合称为地址空间。地址空间是一个目标程序所限定的地址范围。,存储空间 主存中一系列存储信息的物理单元的集合称为存储空间。单元编号称为物理地址或绝对地址。一个计算机系统的存储空间的大小是由主存实际容量决定的。所以说：地址空间是逻辑地址的集合，存储空间是物理地址的集合，前者是“虚”的概念；后者是“实”的物体。,一个编译好的程序存在于它自己的地址空间中，当它要被运行时才装入到存储空间。程序的名字空间、地址空

6、间、和存储空间是三个很重要的概念，理解他们对于理解下面的重定位很有帮助。,地址重定位 一个编译好的程序要在计算机上运行时，首先应将其指令和数据装入主存的某个区域或某几个区域，也就是说要进行存储分配。一般情况下，作业分配到的存储空间和它的地址空间是不一致的。当一个作业分配到的存储空间和它的地址空间不一致时，引起对有关地址部分的调整过程称之为“地址重定位”。或也称为“地址变换”，它是将一个作业在地址空间中使用的逻辑地址变换成主存中的物理地址的过程（有的也称为“地址映射”）。,假设用户作业的逻辑地址空间从0到600字节，其中在第100字节处有一条“装入”指令，该指令要求从第500字节处取出操作数12

7、345，并装入第1号寄存器中。如果存储管理为该作业分配的主存区域是从1000字节开始，那么，逻辑地址第100字节的指令被放在主存中的对应位置是1100字节的位置，逻辑地址第500字节中的数据就被放在主存的1500字节处。见下图（a）所示。如果不修改上述“装入”指令中的操作数地址500，则处理器执行该指令时将从主存的500字节中去取操作数，这显然是错误的。于是，应把程序中所有逻辑地址都转换成物理地址。上述装入指令中的操作数地址也相应改为1500字节。这样，在执行指令时便可从1500字节处准确地取出操作数12345。由此看来，重定位是必不可少的处理过程。,重定位类型 重定位（地址变换）在什么时候进

8、行？用什么方法实现？这就是我们在此要讨论的问题。按照重定位的时间，可以将重定位分为静态重定位和动态重定位两种类型。 静态重定位 动态重定位,静态重定位 在装入一个作业时，把作业中的指令地址和数据地址全部转换成绝对地址。由于地址转换工作是在作业开始执行前集中一次完成的，所以在作业执行过程中就无需再进行地址转换工作，这种地址转换方式称“静态重定位”。,在上图（b）中，仍假设用户作业的逻辑地址空间从0到600字节，其中在第100字节处有一条装入指令：LOAD 1,500”，该指令要求从第500字节处取出操作数12345，然后装入第1号寄存器中。如果存储管理为该作业分配的主存区域是从1000字节开始，

9、那么，逻辑地址第100字节的指令被放在主存中的对应位置是1100字节的位置，逻辑地址第500字节中的数据就被放在主存的1500字节处。于是，采用静态重定位时，应把程序中所有逻辑地址都转换成绝对地址。上述装入指令中的操作数地址也应改为1500字节。这样，在执行指令时便可从1500字节处准确地取到操作数12345。,静态重定位是由专门的重定位装入程序完成的，因此，它是由软件来实现的，无需专门的硬件地址变换机构的支持，因而可在一般的机器上实现。但是也存在着明显的缺点，由于静态重定位是在装入程序将作业装入主存时就完成了地址变换，则一个程序经过静态重定位而被装入内存后，就不能在内存中移动，而且要求程序在

10、内存中是连续的存放，还要求程序本身是可以重定位的。,动态重定位 动态重定位是指在程序执行过程中，当访问指令或数据时才进行的地址变换方式。动态重定位可使地址空间中的信息不加任何修改就装入内存，在执行指令时才对相应的地址进行调整。它的实现需要专门的硬件重定位寄存器的支持才能完成。下图给出了动态重定位的示意图。,由此可见，动态重定位是在指令执行过程中动态进行的，这样做可以带来两点好处： (1) 目标程序装入内存时无需作任何修改，所以，在程序装入内存之后再移动也不会影响其正确运行（因为这时只需修改重定位寄存器中的值即可），这就便于用拼接的办法来紧缩内存以解决存储器的碎片问题，使主存的使用更加灵活、有效

11、。 (2) 一个程序由若干个相对独立的目标模块组成时，每个目标模块各装入一个存储区域，这些存储区域可以是不相邻接的，只要各个模块有自己对应的重定位寄存器就可以了。 动态重定位的缺点是“必须有相应的硬件支持，实现存储管理的软件算法也比静态重定位复杂。,44 实存管理技术,441 单一连续分区分配方式 442 分区式分配 443 覆盖与交换 444 分页存储管理,441 单一连续分区分配方式,这是一种最简单的存储管理方式，在早期的单道批处理系统的小型机中常使用这种管理方案。采用这种管理方案时，内存被分成两个区域，一个是系统区域，仅供操作系统使用，通常设置在内存的低段；另一个是用户区，它是除系统区以

12、外的全部内存区域，这部分区域是提供给用户使用的区域，任何时刻主存储器中最多只有一个作业。所以，单一连续区存储管理只适用于单用户的情况。,441 单一连续分区分配方式,此系统的特点是： 记住存储器的状态容易，不是全部空闲就是全部已分配； 当作业被调度时就获得全部空间； 全部主存空间都分配给一个作业； 作业运行完后，全部主存空间又恢复成空闲。（以上所指的全部主存空间是全部用户区空间）,特点：任一时刻内存只有一道作业，该作业连续存放于内存中。 管理方法,内存空间安排,操作系统,用户程序,a,a+1,n,越界检查机构：用户程序每访问一次主存，越界检查机构将访问的地址与界地址寄存器中的值比较。若越界，则

13、终止其执行。,界地址寄存器,主存,Aa,cpu,true,false,地址A,终止程序运行,计算机的状态分为：CPU管理方式和用户管理方式两种，我们把CPU管理方式叫做计算机在管态下工作；用户管理方式叫做计算机在目态下工作。如果计算机在目态下工作，对内存访问时硬件均进行校验，以保证保护区不被访问，如果出现这种访问则产生中断，控制权交给操作系统；在管态下，操作系统能访问整个存储空间。仅当控制权交给操作系统时，CPU才由目态变为管态。因此说，目态是用户工作方式，而管态是管理工作方式。,单一连续区分配算法简单，操作系统也比较小，因而了解使用这样的系统很容易，不需要很多经验。但这种管理方案太简单以至于

14、使得： (1) 存储器没有得到充分利用，往往是浪费了一部分或大部分。因为，作业的大小与存储器的可用空间的大小不一定一致。而且是作业的全部信息都装入主存，有的信息从未使用过也白白占用了主存空间。 (2)处理机的利用率较低，因为是单道处理，一旦一个作业提出I/O请求则 CPU空闲。 (3) 作业的周转时间长，当一个大作业装入系统运行后，新进入系统的小作业也必须等待大作业运行完成后才能装入运行。 (4) 缺乏灵活性，要求作业的地址空间小于等于主存可用空间，否则此作业不采用覆盖技术（虚拟存储技术）就无法运行。,442 分区式分配,分区式分配是能满足多道程序设计的最简单的存储管理技术，它允许几个作业共享

15、主存空间，这几个作业被装入不同的分区中，每个分区可用来装入一个作业。 分区式分配又分为：固定式分区、可变式分区、可重定位分区和多重分区四种管理方案。,1. 固定式分区,实现原理 固定式分区是在处理作业之前存储器就已经被划分成为若干个分区，每个分区的大小可以相同，也可以不同。但是，一旦划分好分区后，主存储器中的分区的个数就固定了，且每个分区的大小也固定不变。,硬件支持 采用这种存储管理方案只需很少一点专用硬件-存储保护机构，以防止某一个作业干扰或破坏操作系统和其他作业。有两种实现方法：其一，使用两个界限寄存器框住正在使用的内存区域，但是这样做很麻烦，每当重新分配处理机时都得修改界限寄存器的内容。

16、其二，为每个分区配上一个单独的保护锁，程序状态字中有一把钥匙，根据锁和钥匙相匹配的方法来实现存储保护。,软件算法 这种分区方式一般将内存的用户区分成大小不等（也可以分成大小相等）的分区，以适应不同大小的作业的需要。系统中有一张分区说明表简称为分区表，每个表目记录一个分区的大小、起始地址和分区的状态，当系统为某个作业分配主存空间时，根据所需要的内存容量，在分区表中找到一个足够大的空闲分区分配给它，然后将此作业装入内存。如果找不到足够大的空闲分区则这个作业暂时无法分配内存空间，系统将调度另一个作业。,可变式分区 实现原理 可变式分区是指在作业执行之前并不建立分区，分区的建立是在处理作业的过程中进行

17、的，而且分区的大小可以按作业或进程对内存的需求而改变。在系统初启时除了操作系统中常驻内存的部分以外，给用户只提供一个空闲分区，即整个用户区。当作业装入主存时，从空闲区中划分出一块连续的区域分配给该作业，该区域就变成了已分配区域，也就建立了一个分区。若还有作业要求运行，则继续将空闲区依次分配给各个作业，即在内存中建立了若干个与作业大小相等的分区了 。,为了实现这种管理方案，使用已分配区状态表和空闲区表来记录内存的使用情况 。 表4-3已分配区状态表 区号 大小（k）位置 状态 1 8 312 已分配 2 32 320 已分配 3空白 4 120 384 已分配 5空白,表4-4空闲区表 空闲区

18、大小(k) 位置 状态 1 32 352 可用 2 520 504 可用 3空白 4空白 空表目,从上述两个表中可以看出，系统已经为三个作业分配了主存空间，内存被划分为三个分区，如下图（a）所示。现又有作业4（大小为24k）、作业5（大小为128k）和作业6（大小为256k）欲加入多道运行，在空闲区表中找到能容纳这三个作业的空闲区进行分配。分配后的主存分区情况如下图（b）所示。又过了一段时间作业2与作业3运行结束，主存的分区情况又发生了变化，如下图（c）所示。,可变式分区分配与回收算法比较简单，分配时，首先找到一个足够大的空闲区，即在空闲区中找到一个足以容纳该作业的可用空闲区，如果这个空闲区比

19、所要求的大的较多，则将其分为两部分，一部分分给作业，另一部分仍为空闲区，然后修改已分配区状态表和空闲区表，回收时，须检查回收分区是否邻接空闲区，如邻接空闲区则要进行合并，使之成为一个较大的空闲区。然后也相应地修改已分配分区状态表和空闲区表。,回收分区邻接空闲区的情况有三种： 回收分区R与上面的空闲区F1邻接，如下图（a）所示，这时应将回收分区与上面的空闲区合并成一个空闲区，原空闲区F1的始址不变，只改变其大小。 回收分区R与下面的空闲区F2相邻接，如下图（b）所示，这时也应该将其合并成为一个较大的空闲区，但原空闲区的始址和大小都要改变。 回收分区R的上、下都邻接着空闲区F1和F2，此时应该撤销

20、下面的空闲区F2，只保留上面的那个空闲区F1，其始址不变，它的大小等于原上面的空闲区F1与回收分区R和下面的空闲区F2三者之和，如下图（c）所示。,若回收分区的上、下都无空闲区邻接，这时，应该在空闲区表或空闲区链中增加一个登记表目，表明又增加一个空闲区。 上面所提到的用表格记录存储器使用状态的方法具有如下的缺点： 检查回收分区是否邻接着空闲区比较麻烦，因为要查遍整个未分配分区表。 已分配分区表和未分配分区表中的表目数取决于某一时刻分区个数和空闲区的个数，因而表目数是不固定的，且每个分区的大小也是变化的。但是必须有足够多的空表目，用以登记新装入主存的作业占用的分区和作业撤离后的空闲区。,可变式分

21、区的管理算法 首次适应算法 首次适应算法也叫作最先适应算法。这种算法在每次分配分区时，操作系统顺序查找空闲区表，把最先能够满足要求的空闲区进行分割，这个空闲区的一部分分配给作业，另一部分仍为空闲区。 可把空闲区按照地址顺序从小到大登记在空闲区表中。于是，在分配时总是尽量利用低地址部分的空闲区，而使高地址部分有较大的空闲区，有利于大作业的装入。,最佳适应算法 最佳适应算法总是按作业要求选择一个能满足作业要求的最小空闲区，这个最小空闲区应该是所有空闲区中最合适的一个，这样就保证不会去分割一个更大的区域，使大的作业比较容易得到满足。通常在实现这种算法时，可按空闲区从小到大顺序登记在空闲区表或空闲区链

22、中，分配时，顺序查找空闲区表或空闲区链，由于查找时每次总是从最小的一个空闲区开始，所以，当能够找到第一个满足作业要求的空闲区时，则一定是所有能满足作业要求的空闲区中的最小的（也是最合适的）一个空闲分区。,最坏适应算法 最坏适应分配算法总是挑选一个最大的空闲区分割一部分给作业使用，这样使剩余部分空闲区不致于太小，则就可以被再利用而分配给其他作业，这种分配算法对中小型作业是有利的。 实现最坏分配算法时，空闲区表或空闲区链中的空闲区可以按照从大到小的顺序排列，排在空闲区表或链中的第一个空闲区总是最大的。同样，当作业归还分区时也必须把空闲区表或空闲区链调整成按照空闲区的从大到小的顺序排列的形式，比较麻

23、烦。,硬件支持 采用可变分区方式进行存储管理时，一般采用动态重定位方式装入作业。因此，要有硬件的地址转换机构作支持。通常硬件设置两个专用的控制寄存器：一个是基址寄存器；另一个是限长寄存器。基址寄存器用来存放作业所占分区的起始地址，限长寄存器用来存放作业所占分区的长度。,3. 可重定位分区分配,（1）实现原理 例如，有一个作业需要20K字节的分区，内存空闲区的总数是22 K字节，但不连续，所以按照前面的分配算法就不能给这个作业分配主存空间。解决的方法是移动所有已分配区的内容，使原来不连续的若干个小的空闲区合并成为一个较大的空闲区。我们把这个过程称为“紧缩”。 下图给出了内存紧缩前后的情况以及给作

24、业7分配256K字节的内存空间后，内存的分区情况 。,把作业4从内存中的352K处移至320K，作业4分区中与指令相关的所有地址部分中的有效地址均减去32K。这种程序在内存中移动所进行的与位置有关的地址调整过程称之为“重定位或浮动”。实现方法之一是采用类似于重定位装入程序的软件来实现，但是这种方法所花费的处理机时间太多，而且限制较大。第二种方法是采用动态重定位技术即重定位寄存器来完成。当一个作业在存储器中移动时，只改变重定位寄存器中的内容即可。,注意：作业4在“地址空间”中什么都没变，程序也不知道它的实际物理存储位置。分区虽然从352K移到了320K，但是，作业4的每一条指令都不用变化，仍然和

25、在352K分区时一样。由于这种重定位的地址调整是在每条指令执行时自动完成的，所以称之为“动态重定位”。,软件算法 软件算法与可变式分区管理算法基本相同。下图给出了分配算法的流程图 。,总之，可重定位分区管理算法消除了存储器的碎片，因此，存储器的利用率提高了，但是这是以牺牲处理机的效率为代价而换来的。 那么，什么时候进行拼接呢？一是当某个作业运行完毕离开系统时，该作业的分区被回收后，如果它不与空闲区相邻接，则立即进行拼接。于是在存储空间中总是只有一个空闲区，因而不存在分散零头的问题。这样做，空闲区的管理以及给作业分配分区都特别方便，但是拼接的频率较高，花费的时间较多。 第二是当作业找不到足够大的

26、空闲区时再拼接。一个作业申请存储空间得不到满足时，而所有的空闲区的总和又足够该作业所需要的大小时进行拼接，这样做，降低了拼接的频率，节省了处理机时间，但是空闲区的管理不如前一种方法简单。,4. 多重分区分配,在分区式存储管理方法中采用可重定位方法需要拼接，拼接是比较费时间的。既想利用存储器的零头而又不想费时间，则可采用的另一种分区分配方案是多重分区分配。 因为一个程序往往是由若干个相对独立的程序段和数据段所组成（主程序和子程序等），程序段在逻辑上是连续的，但在主存中却无须连续，这种给作业分配一个以上的分区的方法叫多重分区分配。既然作业可以被分配在多个分区中，当然作业临时申请附加的区段也就容易实

27、现。,5. 分区的保护措施,对于以上四种分区管理方法都需要进行分区的保护，通常采用的分区的保护措施主要有两种，一种方法是使用界限寄存器，另一种方法是使用存储保护键。有的系统二者兼用。例如，下图表示使用界限寄存器的方法来进行分区保护，其中，下界寄存器与基址寄存器起重定位作用。多个分区的作业的保护就必须设置多个界限寄存器。,下图是采用存储保护键的方法实现分区保护。,综上所述，分区式分配的优点可以归纳如下： （1）由于内存被分成多个分区，所以允许多道程序同时共享主存空间，这就更有效地利用了处理机和I/O设备，使系统的吞吐率和周转时间都得到了相应地提高。 （2）相对于以后要介绍的几种管理技术，分区式分

28、配所需要的表格较少，表格占用的空间也少，算法简单。 （3）实现分区保护的手段也简单。 （4）多重分区管理便于实现对子程序、数据的共享。,缺点也可以归纳如下： （1）与后面要介绍的管理方法相比，分区式管理方法主存的利用率仍不是很高，除了可重定位分区分配方法以外，都存在着严重的零头问题。 （2）分区式管理方法不能实现对主存的扩充，因此，作业的大小受主存可用空间的限制。 （3） 要求一个作业在运行前全部信息都要装入主存，有些信息在本次运行时并不需要，它也白白占用了主存空间。 （4） 可重定位分区分配方法所允许采用的拼接技术在拼接时也浪费处理机的大量时间。 （5）除了多重分区外，几个作业之间不能共享存

29、入主存中的信息。,443 覆盖与交换,1.覆盖（overlap） 因内存小于作业的程序空间而引入覆盖，将用户空间划分成一个固定区和多个覆盖区。主程序放固定区，依次调用的子程序则放在同一个覆盖区。操作系统提供覆盖系统调用函数，由用户编程序时考虑调用。,什么叫覆盖 所谓覆盖是指一个作业的若干程序段或几个作业的某些部分共享某一段主存空间。覆盖管理是由系统实施，用户只需提供一个明确的覆盖结构。我们称之为自动覆盖技术。 本节研究两个问题: （1）作业内部的覆盖处理 （2）作业之间的覆盖处理,固定区(4k),覆盖区(6k),覆盖区(10k),A(4k),E(10k),D(6k),C(4k),B(6k),F

30、(8k),（2）作业之间的覆盖处理 在多道程序系统中作业之间也可以采取覆盖技术以达到“扩充”存储空间的目的。通常在作业之间采用最小覆盖算法。 假设系统中有4个作业，内存共有14个存储块，并设每个存储块的大小相等，作业1装入了主存的始端，占6个存储块。作业2装入了内存的末端，占9个存储块。作业3装入了存储器的末端，占6个存储块。作业4被安排在存储器的始端，占3个存储块。结果作业4与作业3的全部信息都存于主存，而作业1和作业2仅保留一部分信息，其余的信息被覆盖掉了，详见下图（b）。,系统实现最小覆盖算法时，分别建立两张表：覆盖次数表和占用者表，如图4-18（a）所示。下图(b)为主存使用情况表。

31、所谓最小覆盖算法是为调度到的作业i在内存中寻找适当的位置，使得被作业i再次覆盖的所有块的覆盖次数总和为最小。为此，此算法必须计算作业i被安放在不同位置时覆盖次数总和，并加以比较，选择总和最小的那几块来存放作业i。由于这些位置将被再次覆盖，所以给每一个被覆盖的存储块增加覆盖次数。,2. 交换,多道程序环境或分时系统中，同时执行好几个作业或进程。但是，这些同时存在于内存中的作业或进程，有的处于执行状态或就绪状态，而有的则处于等待状态。一般来说，等待时间比较长。例如从外存软磁盘读一块数据到内存有时要花0.1秒到1秒左右的时间。如果让这些等待中的进程继续驻留在内存，将会造成存储空间的浪费。因此，应该把

32、处于等待状态的进程换出内存。,基本思想：将处于等待状态(等I/O)或就绪(等CPU)状态的进程从主存换出到辅存，把将要执行的进程移入主存。 I/O缓冲区对于交换的影响。 申请空间的系统调用，用于动态申请空间。 交换要花费较长的时间。,广义地说，交换实质是先将内存某部分的程序或数据写入外存交换区，再从外存交换区中调入指定的程序或数据到内存中来，并让其执行的一种内存扩充技术。与覆盖技术相比，交换不要求程序员给出程序段之间的覆盖结构。而且，覆盖可以在一个作业内部进行，交换主要是在进程或作业之间进行。交换的原则是在任一时刻，在主存中只保留一个用户作业或进程，当它运行一段时间后，系统将它调到辅存，然后又

33、调入另一个作业到主存运行。,444 分页存储管理,不连续空间分配 特点：作业(进程)分成页面，内存也划分成页面，将作业(进程)页面不连续地分布到内存页面。 一、空间安排 用户进程空间(地址)叫逻辑空间(地址); 内存空间(地址)叫物理空间(地址); 用相同长度为单位对逻辑空间等分出的每 个区域叫页，对物理空间等分出的区域叫 页帧，对外存交换区等分出的每个区域叫 块。,分配：初始时，所有页帧都在空闲队列中，当用户进程被创建时，系统按需要量从空闲队列获得相应量的页帧。 回收：当进程结束时，系统回收它的所有物理页帧入空闲队列。 二、动态地址转换机构 因页式方法中逻辑地址与物理地址之间失去自然联系，故

34、要通过页表，并由硬件动态地址转换机构将逻辑地址映射成物理地址才能正确访存。,(一)页表 页表放在系统空间的页表区，存放逻辑页与物理页帧的对应关系。PCB表中有指针指向页表。,(二)地址结构 逻辑地址 = p(页号) d(页内位移) 物理地址 = f(页帧号) d(页内位移) p = 线性逻辑地址 / 页面大小； d = 线性逻辑地址 p页面大小。,(三)页面大小的考虑 将页面大小取成2的k次幂(k是正整数),获取p和d的除法或乘法只要通过位移实现。 页面大小为2的k次幂的地址转换原理如下：,P d,页表始地,f,f d,n k-10,+,页表,(四)联想存储器 CPU有一个用于页号页帧号转换的

35、联想存储器。将页表存入联想存储器的地址，其转换原理如下：,P d,n k-10,f d,n k-10,P2,f2,P1,f1,.,.,P,f,.,.,Pm,fm,关键字 值,地址转换的一般过程： (联想存储器可以看成是页表的cache),软件算法 为了实现这种管理方案，操作系统必须建立和管理三种表格：作业表（JT）、存储分块表（MBT）和页面映象表（PT）。,分页存储管理的优缺点 分页存储管理的优点如下： 分页存储管理解决了存储器的零头问题，可以同时为更多的作业提供主存空间，更有利于进行多道程序设计，提高了主存的利用率以及处理机的效率。,缺点： （1）动态地址变换机构增加了计算机的成本，降低了

36、处理机的速度。 （2）必须占用一些存储空间来存放各种表格，建立表格、管理表格也要花费一定的时间。 （3）分块之间的零头消除了，但是出现了块内零头，也叫做页面间隙。因为作业不一定是页的大小的整数倍，每个作业的最后一页往往是不满的。例如，某作业的地址空间为3.1K，如果页的大小为1K，则这个作业将被分成4个页面，而最后一页装入内存某块中时，只占了0.1K,浪费了0.9K。 （4）要求运行的作业的信息全部装入主存，如果可用空间存储块不能满足该作业的要求，则该作业不能运行。实际上，每次运行只是作业的一部分信息，有些信息从不使用也白白占用存储空间。 （5）作业的地址空间受主存容量的限制。,45 虚存管理

37、技术,451 请求页式存储管理 452 分段存储管理 453 段页式管理,451 请求页式存储管理,页式虚存管理 一、页表项结构:,合法位：置该位表示该页在内存。 修改位：置该位表示该页被修改过，在释放或淘 汰时应写回外存。 页类型：零页时，表示该页在分配物理页帧时应 清0页帧空间;回写swap区页时，表示回 写swap区。 保护码：R,W,E保护说明。 外存块号：该页所在外存的块号。 页 帧 号：当在合法位置上时，代表该页所在内 存的页帧号。,不装入作业的全部地址空间的条件下，能否也能运行这个作业呢？回答是肯定的。因为作业在运行期间多数程序只使用其全部地址空间中的一小部分，理由如下： （1）

38、用户编写的出错处理程序，仅当数据和计算中出现错误时才会用到； （2）程序中某些任选部分是彼此互斥的，并非每次运行都用得到； （3）许多表格占用固定数量的地址空间，而事实上只用到其中的一小部分，如汇编程序建立了一个能处理1000个字符的符号表，在某次具体运行时，仅用到其中的100个符号，则表的90%未用到。它们也跟着装入了主存，白白占用了主存空间； （4）许多子程序在运行过程中通常是彼此排斥的，如，输入、计算、输出等。,下面讨论两个关键问题： （1）当作业的地址空间没有全部装入主存中时，如果作业要访问的地址空间的某个区域不在主存中时，系统应该如何处理？ （2）如何决定哪些页面应该在主存中，哪些页

39、面放在外存上？,软件算法 （1）缺页中断的处理,让我们来讨论以下4个问题： 该页在主存吗？ 有空闲存储块吗？ 发生缺页中断的次数？ 存储块的状态？,页面置换算法（淘汰算法） 随机淘汰算法（Random Glongram） 在系统设计人员认为无法确定哪些页被访问的概率较低时，随机地选择某个页面并将其换出将是一种明智的做法。 先进先出淘汰算法（FIFO First In First Out） 先进先出淘汰算法总是选择作业在主存中驻留时间最长的（最老的）一页淘汰，即先进入主存的页就先退出主存。其理论依据是：可能最早调进主存的页，其不再使用的可能性比最近调入主存的页要大。这好比某商场货架上摆满了各种货

40、物，又来了一种新的商品要摆上货架，但货架上已经没有位置了，需要选择一种货物拿下货架，按照先进先出淘汰算法就应该把在货架上摆放时间最长的货物拿下来（商场卖货是从货架上拿下来卖给顾客，然后再往货架上摆上同类货物），而不管其是否畅销。,最近最久未用页面淘汰算法（LRU Least Recently Used） 最近最久未用页面淘汰算法总是选择长时间未被访问的页面进行淘汰。其理论依据是根据一个作业在执行过程中过去的页面踪迹来推测其未来行为。它认为过去一段时间内不曾被访问的页面在最近的将来也可能不会再被访问。仍然以某商场为例，商场货架上摆满了各种货物，又有一种新货物要上货架，当选择某种货物淘汰时，应该选

41、择在货架上灰尘落得最多的那种货物，因为，这种货物长时间没有卖出去了。相当于长时间未被访问的页。实现这种淘汰算法是周期性地对“引用位”进行检查并记录一个页面自上次访问后所经历的时间，淘汰时选择时间最长的页。但是要想完全实现这种算法是一件十分困难的事情。因为要找出最近最久未被使用的页面的话，就必须对每一个页面都设置有关的访问记录项，而且每一次访问又都必须更新这些记录。这显然要花费巨大的系统开销 。,请求页式存储管理的优缺点 综上所述，请求页式存储管理具有分页式存储管理的优点： (1) 由于它不要求作业或进程的程序段和数据在内存中连续存放，从而有效地解决了碎片问题。 (2) 请求页式存储管理提供了内

42、存和外存统一管理的虚存管理方式，使用户可以利用的存储空间大大增加。这既提高了主存的利用率，又有利于组织多道程序执行。,其主要缺点是： (1) 要求有相应的硬件支持。例如地址变换机构，缺页中断的产生和选择淘汰页面等都要求有相应的硬件支持。这增加了系统的成本。 (2) 请求页式管理的淘汰页面的算法选择不当，可能产生抖动现象。 (3) 理论上这种管理算法消除了存储器的碎片，但每个作业或进程的最后一页总有一部分空间得不到充分利用。如果页面较多，则这一部分的浪费仍然是很严重的。,452 分段存储管理,段式管理 页式管理：对用户而言不自然,段式管理的特点：按作业的自然段将其逻辑空间分成若干段，作业以段为单

43、位分配内存。 一、空间安排 用户作业逻辑空间为二维空间，由若干自然段组成。 逻辑地址：段号段内偏移，记做S,d。编译及装配时把所有地址记成(s,d)的形式。 物理内存空间管理：与多道可变划分法一样，系统以段为单位分配物理内存。,主程序,子程序1,子程序2,栈,数据,逻辑空间,子程序2,主程序,栈,数据,OS,子程序1,物理空间,二、动态地址转换,保护码,段长,本段内存始地址,段表：由如下格式的段表项组成，作业每段由一个段表项表示。,段表放于系统空间，进程PCB表中存有段表始地址、段表长度。 段表始地址寄存器、段表长度寄存器。,段号,保护码,段长,段内存始址,.,.,.,.,保护码,段长,段内存

44、始址,.,.,.,S,d,段表始址,段表长度,+,+,PA,越界,地址转换过程,LA,联想存储器,三、共享,若共享的段引用自身的某个地址，则各进程必须用同一段号来共享这一段。,（1）SQRT（A，Y） （2）IF X0 THEN GOTO （SQRT，L） （3） （4） （5）(SQRT，L)： （6） ,GOTO （SQRT，L）,4.5.3 段页式管理,特点：将作业分成若干段，每段用页式管理实现内存分配。,一、空间安排,对于用户而言，段页式管理与段式相同，用户逻辑地址只涉及段号与段内位移。 对于物理内存管理而言，它与页式系统相同。 系统内的逻辑地址：段号 段内位移 - 段号页号页内位移。

45、记做：S,P,d,作业空间的内部表示,主程序 子程序 数据,保护码 长度 页表始地,OS,段表,页表,主存,作业,段表+页表,动态地址变换,段号,页号,保护码,页帧号,.,.,.,.,S,p,d,段表始址,段表长度,+,越界,+,f,f d,段表,页表,段表,主程序 子程序 数据,作业1,主程序 子程序 数据,作业2,段表,页表,OS,主存,“放” 连续存放： 单道连续划分； 多道连续固定划分； 多道连续可变划分。 不连续存放： 页式存储； 段式存储； 段页式存储。,虚存 目的：提供用户进程一个巨大的虚拟存储空间。 手段：利用外存(磁盘)实现此虚空间。 虚存的基本思想 系统为进程提供一个比物理内存大得多的虚拟存储空间，逻辑空间大小不在物理内存大小的限制。 逻辑空间的容量由系统的有