计算机操作系统第5章.ppt

第5章存储管理,5.1存储管理的功能5.2分区存储管理5.3覆盖与交换技术5.4页式管理5.5段式与段页式管理5.6局部性原理和抖动问题本章小结习题,5.1.1多级存储器结构,对于通用计算机系统而言，存储层次至少应具有三级：最高层为CPU寄存器，中间层为主存，最底层为辅存。在较高档的计算机中，可以根据具体功能分工细分为：寄存器、高速缓存、主存、磁盘缓存、固定磁盘、可移动存储介质等6层。如图5-1所示。,存储层次中，越往上，访问速度越快，价格也越高，相对存储容量也越小。其中寄存器、高速缓存、主存、磁盘缓存均属于操作系统存储管理的管辖范畴，掉电后它们存储的信息不再存在。固定磁盘、可移动存储介质属于操作系统设备管理的管辖范畴，它们存储的信息被长期保存。,5.1.2主存储器与寄存器,1.主存储器,主存储器(简称内存或主存)用于保存进程的程序和数据，也称为可执行存储器，在微机系统和大中型机中，其容量可能为几十MB到数GB，而且容量还在不断增加，在嵌入式计算机系统中，其容量一般为几十KB到几MB。CPU的控制部件只能从主存中取得指令和数据。CPU与外围设备交换的信息一般也依托于主存地址空间。由于主存的访问速度远低于CPU执行指令的速度，为缓解这一矛盾，在计算机系统中引入了寄存器和高速缓存。,2.寄存器,寄存器访问速度最快，完全能与CPU协调工作，但价格却十分昂贵，因此容量不可能做得很大。寄存器的长度一般以字为单位。寄存器的数目，对于微型计算机和大中型机，可能有几十个甚至上百个；而嵌入式计算机系统一般仅有几个到几十个。寄存器用于加速存储器的访问速度，如用寄存器存放操作数，或用作地址寄存器加快地址转换速度等。,5.1.3高速缓存和磁盘缓存,1.高速缓存,高速缓存(Cache)是存在于主存与CPU之间的一级存储器，由静态存储芯片(SRAM)组成，容量比较小但速度比主存高得多，接近于CPU的速度。其容量大于或远大于寄存器，而比主存约小2到3个数量级，从几十KB到几MB。根据程序执行的局部性原理，将主存中一些经常访问的信息存放在高速缓存中，减少访问主存的次数，可以大幅度提高程序执行的速度。由于高速缓存的速度越快价格也越高，故有的计算机系统中设置了两级或多级高速缓存。一级高速缓存速度最高而容量最小，二级高速缓存容量稍大，速度也稍低。,2.磁盘缓存,磁盘缓存是操作系统为磁盘输入输出而在普通物理内存中分配的一块内存区域。由于磁盘的I/O速度远低于主存的访问速度，因此将频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中(即利用主存中的存储空间，来暂存从磁盘中读出或写入的数据和信息)，可减少访问磁盘的次数。在读硬盘数据时，系统先检查请求指令，看看所要的数据是否在缓存中，如果在的话就由缓存送出相应的数据，这个过程称为命中。这样系统就不必访问硬盘中的数据，由于主存的速度比磁介质快很多，因此也就加快了数据传输的速度。在写入硬盘数据时也在缓存中找，如果找到就由缓存将数据写入磁盘中。,虚拟存储器虚拟存储器是存储管理的核心概念。实验证明，在一个进程的执行过程中，其大部分程序和数据并不经常被访问。这样，存储管理系统把进程中那些不经常被访问的程序段和数据放入外存中，待需要访问它们时再将它们调入内存。那么，对于那些一部分数据和程序段在内存而另一部分在外存的进程，怎样安排它们的地址呢？通常由用户编写的源程序，首先要由编译程序编译成CPU可执行的目标代码。然后，链接程序把一个进程的不同程序段链接起来以完成所要求的功能。显然，对于不同的程序段，应具有不同的地址。,将进程中的目标代码、数据等的虚拟地址组成的虚拟空间称为虚拟存储器(virtualstore或virtualmemory)。虚拟存储器不考虑物理存储器的大小和信息存放的实际位置，只规定每个进程中互相关连信息的相对位置。与实际物理存储器数量有限，且被所有进程共享不一样，每个进程都拥有自己的虚拟存储器，且虚拟存储器的容量是由计算机的地址结构和寻址方式确定的。直接寻址时，如果CPU的有效地址长度为16位，则其寻址范围为0到64K。用户编制程序时使用的地址称为虚地址或逻辑地址，其对应的存储空间称为虚存空间或逻辑地址空间；而计算机物理内存的访问地址则称为实地址或物理地址，其对应的存储空间称为物理存储空间或主存空间。程序进行虚地址到实地址转换的过程称为地址重定位。,图中，编译和链接主要是语言系统的设计问题，而虚拟存储器到物理存储器的变换是操作系统必须解决的问题。要实现这个变换，必须要有相应的硬件支持，并使这些硬件能够完成统一管理内存和外存之间数据和程序段自动交换的虚拟存储器功能。即，由于每个进程都拥有自己的虚存，且每个虚存的大小不受实际物理存储器的限制，因此，系统不可能提供足够大的内存来存放所有进程的内容。内存中只能存放那些经常被访问的程序和数据段等。这就需要有相当大的外部存储器，以存储那些不经常被访问或在某一段时间内不会被访问的信息。待到进程执行过程中需要这些信息时，再从外存中自动调入主存。,地址变换与物理存储器,虚拟内存是计算机系统内存管理的一种技术。它使得应用程序认为它拥有连续的可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。目前，大多数操作系统都使用了虚拟内存，如Windows家族的“虚拟内存”；Linux的“交换空间”等。虚拟内存别称虚拟存储器（VirtualMemory）。电脑中所运行的程序均需经由内存执行，若执行的程序占用内存很大或很多，则会导致内存消耗殆尽。为解决该问题，Windows中运用了虚拟内存技术，即匀出一部分硬盘空间来充当内存使用。当内存耗尽时，电脑就会自动调用硬盘来充当内存，以缓解内存的紧张。,1.外存（如磁盘）上存放的程序和数据（）。A、可由CPU直接访问B、必须在CPU访问之前移入内存C、是必须由文件系统管理的D、必须由进程调度程序管理2.当程序经过编译或者汇编以后，形成了一种由机器指令组成的集合，被称为（）。A、源程序B、目标程序C、可执行程序D、非执行程序3.可由CPU调用执行的程序所对应的地址空间为（）。A、符号名空间B、虚拟地址空间C、相对地址空间D、物理地址空间4.存储管理的目的是（）。A、方便用户B、提高内存利用率C、方便用户和提高内存利用率D、增加内存实际容量,（）1、动态存储分配时，要靠硬件地址变换机构实现重定位。（）2、虚拟存储器实际上是一种设计技巧，使主存物理容量得到扩大。（）3、利用对换技术扩充内存时，设计时必须考虑的问题是：如何减少信息交换量，降低交换所用的时间。（）4、虚拟存储方式下，程序员编写程序时，不必考虑主存的容量，但系统的吞吐量在很大程度上依赖于主存储器的容量。（）5、虚拟存储空间实际上就是辅存空间。虚拟存储空间不是一个实际存在的存储空间，是操作系统对逻辑内存的扩充（）6、在虚拟存储系统中，操作系统为用户提供了巨大的存储空间。因此，用户地址空间的大小可以不受任何限制。,5.1.2地址变换内存地址的集合称为内存空间或物理地址空间。内存中，每一个存储单元都与相应的称为内存地址的编号相对应。显然，内存空间是一维线性空间。虚存的一维线性空间或多维线性空间变换到内存的唯一的一维物理线性空间所涉及的两个问题：第一个问题是虚拟空间的划分问题。虚拟空间的划分使得编译链接程序可以把不同的程序模块(它们可能是用不同的高级语言编写的)，链接到一个统一的虚拟空间中去。虚拟空间的划分与计算机系统结构有关。VAX-11型机中的虚拟空间就是划分为进程空间和系统空间两大部分，而进程空间又更进一步划分为程序区和控制区。VAX-11的虚拟空间容量为232单元，其中程序区占230单元，用来存放用户程序，程序段以零为基址动态地向高地址方向增长，最大可达230-1号单元。控制区也占230个单元，存放各种方式和状态下的堆栈结构及数据等，其虚拟地址由231-1号地址开始由高向低地址方向增长。系统空间占231个单元，用来存放操作系统程序。,图5.2VAX-11机虚拟空间的划分,第二个问题是把虚拟空间中已链接和划分好的内容装入内存，并将虚拟地址映射为内存地址的问题，称之为地址重定位或地址映射。地址映射就是要建立虚拟地址与内存地址的关系。实现地址重定位或地址映射的方法有两种：静态地址重定位和动态地址重定位。静态地址重定位(staticaddressrelocation)是在虚拟空间程序执行之前由装配程序完成地址映射工作。对于虚拟空间内的指令或数据来说，静态地址重定位只完成一个首地址不同的连续地址变换。它要求所有待执行的程序必须在执行之前完成它们之间的链接，否则将无法得到正确的内存地址和内存空间。优点是不需要硬件支持。缺点1：使用静态重定位方法进行地址变换无法实现虚拟存储器。缺点2：必须占用连续的内存空间，这就难以做到程序和数据的共享。动态地址重定位(dynamicaddressrelocation)是在程序执行过程中，在CPU访问内存之前，将要访问的程序或数据地址转换成内存地址。动态重定位依靠硬件地址变换机构完成。,地址重定位机构需要一个(或多个)基地址寄存器BR和一个(或多个)程序虚拟地址寄存器VR。指令或数据的内存地址MA与虚拟地址的关系为：MA=(BR)+(VR)这里，(BR)与(VR)分别表示寄存器BR与VR中的内容。动态重定位过程可参看图5.3。,图5.3动态地址重定位,动态重定位的具体过程：设置基地址寄存器BR，虚拟地址寄存器VR。将程序段装入内存，且将其占用的内存区首地址送BR中。例如，在图5.3中，(BR)=1000。在程序执行过程中，将所要访问的虚拟地址送入VR中，例如在图5.3中执行LOADA500语句时，将所要访问的虚拟地址500放入VR中。地址变换机构把VR和BR的内容相加，得到实际访问的物理地址。动态重定位的主要优点有：可以对内存进行非连续分配。显然，对于同一进程的各分散程序段，只要把各程序段在内存中的首地址统一存放在不同的BR中，则可以由地址变换机构变换得到正确的内存地址。动态重定位提供了实现虚拟存储器的基础。因为动态重定位不要求在作业执行前为所有程序分配内存，也就是说，可以部分地、动态地分配内存。从而，可以在动态重定位的基础上，在执行期间采用请求方式为那些不在内存中的程序段分配内存，以达到内存扩充的目的。有利于程序段的共享。,1.把逻辑地址转变为内存的物理地址的过程称做()。A、编译B、连接C、运行D、重定位2.经过（），目标程序可以不经过任何改动而装入物理内存单元。A、静态重定位B、动态重定位C、编译或汇编D、存储扩充3.存储分配解决多道作业1划分问题。为了实现静态和动态存储分配，需采用地址重定位，即把2变成3，静态重定位由4实现，动态重定位由5实现。供选择的答案：1：A、地址空间B、符号名空间C、主存空间D、虚存空间2、3：A、页面地址B、段地址C、逻辑地址D、物理地址E、外存地址F、设备地址4、5：A、硬件地址变换机构B、执行程序C、汇编程序D、连接装入程序E、调试程序F、编译程序G、解释程序,5.1.3内外存数据传输的控制要实现内存扩充，在程序执行过程中，内存和外存之间必须经常地交换数据。也就是说，把那些即将执行的程序和数据段调入内存，而把那些处于等待状态的程序和数据段调出内存。那么，按什么样的方式来控制内存和外存之间的数据流动呢?最基本的控制办法有两种。一种是用户程序自己控制，另一种是操作系统控制。用户程序自己控制内外存之间的数据交换的例子是覆盖(overlay)。覆盖技术要求用户清楚地了解程序的结构，并指定各程序段调入内存的先后次序。覆盖是一种早期的主存扩充技术。使用覆盖技术，用户负担很大，且程序段的最大长度仍受内存容量限制。因此，覆盖技术不能实现虚拟存储器。操作系统控制方式又可进一步分为两种。一种是交换(swapping)方式，另一种是请求调入(ondemand)方式和预调入(onprefetch)方式。,交换方式由操作系统把那些在内存中处于等待状态的进程换出内存，而把那些等待事件已经发生、处于就绪态的进程换入内存。请求调入方式是在程序执行时，如果所要访问的程序段或数据段不在内存中，则操作系统自动地从外存将有关的程序段和数据段调入内存的一种操作系统控制方式。而预调入则是由操作系统预测在不远的将来会访问到的那些程序段和数据段部分，并在它们被访问之前系统选择适当的时机将它们调入内存的一种数据流控制方式。由于交换方式一般不进行部分交换，即每次交换都交换那些除去常驻内存部分后的整个进程，而且，即使能完成部分交换，也不是按照执行的需要而交换程序段，只是把受资源限制、暂时不能执行的程序段换出内存。因此，虽然交换方式也能完成内存扩充任务，但它仍未实现那种所谓自动覆盖、内存和外存统一管理、进程大小不受内存容量限制的虚拟存储器。只有请求调入方式和预调入方式可以实现进程大小不受内存容量限制的虚拟存储器。,5.1.4内存的分配与回收内存的分配与回收是内存管理的主要功能之一。无论采用哪一种管理和控制方式，能否把外存中的数据和程序调入内存，取决于能否在内存中为它们安排合适的位置。因此，存储管理模块要为每一个并发执行的进程分配内存空间。另外，当进程执行结束之后，存储管理模块又要及时回收该进程所占用的内存资源，以便给其他进程分配空间。为了有效合理地利用内存，设计内存的分配和回收方法时，必须考虑和确定以下几种策略和数据结构：(1)分配结构：登记内存使用情况，供分配程序使用的表格与链表。例如内存空闲区表、空闲区队列等。(2)放置策略：确定调入内存的程序和数据在内存中的位置。这是一种选择内存空闲区的策略。(3)交换策略：在需要将某个程序段和数据调入内存时，如果内存中没有足够的空闲区，由交换策略来确定把内存中的哪些程序段和数据段调出内存，以便腾出足够的空间。(4)调入策略：外存中的程序段和数据段什么时间按什么样的控制方式进入内存。调入策略与5.1.3节中所述内外存数据流动控制方式有关。(5)回收策略：回收策略包括二点，一是回收的时机，二是对所回收的内存空闲区和已存在的内存空闲区的调整。,5.1.5内存信息的共享与保护内存信息的共享与保护也是内存管理的重要功能之一。在多道程序设计环境下，内存中的许多用户或系统程序和数据段可供不同的用户进程共享。这种资源共享将会提高内存的利用率。但是，反过来说，除了被允许共享的部分之外，又要限制各进程只在自己的存储区活动，各进程不能对别的进程的程序和数据段产生干扰和破坏，因此须对内存中的程序和数据段采取保护措施。常用的内存信息保护方法有硬件法、软件法和软硬件结合三种：(1)上下界保护法是一种常用的硬件保护法。上下界存储保护技术要求为每个进程设置一对上下界寄存器。上下界寄存器中装有被保护程序和数据段的起始地址和终止地址。在程序执行过程中，在对内存进行访问操作时首先进行访址合法性检查，即检查经过重定位后的内存地址是否在上、下界寄存器所规定的范围之内。若在规定的范围之内，则访问是合法的；否则是非法的，并产生访址越界中断。,图5.4上、下界寄存器保护法,(2)保护键法也是一种常用的存储保护法。保护键法为每一个被保护存储块分配一个单独的保护键。在程序状态字中则设置相应的保护键开关字段，对不同的进程赋予不同的开关代码和与被保护的存储块中的保护键匹配。保护键可设置成对读写同时保护的或只对读，写进行单项保护的。例如，图5.5中的保护键0，就是对2K到4K的存储区进行读写同时保护的，而保护键2则只对4K到6K的存储区进行写保护。如果开关字与保护键匹配或存储块未受到保护，则访问该存储块是允许的，否则将产生访问出错中断。,图5.5保护键保护法,(3)界限寄存器与CPU的用户态或核心态工作方式相结合的保护方式。在这种保护模式下，用户态进程只能访问那些在界限寄存器所规定范围内的内存部分，而核心态进程则可以访问整个内存地址空间。UNIX系统就是采用的这种内存保护方式。,5.2分区存储管理分区管理是把内存划分成若干个大小不等的区域，除操作系统占用一个区域之外，其余由多道环境下的各并发进程共享。分区管理是满足多道程序设计的一种最简单的存储管理方法。5.2.1分区管理基本原理分区管理的基本原理是给每一个内存中的进程划分一块适当大小的存储区，以连续存储各进程的程序和数据，使各进程得以并发执行。按分区的时机，分区管理可以分为固定分区、动态分区以及动态重定位分区等方法。,5.3连续分配方式,是指一个用户程序分配一个连续的内存空间。又称分区管理方式。分区是指内存中的一个连续区域。,分区管理方式曾被广泛应用于20世纪6070年代的OS中，至今仍在内存分配方式中占一席之地。,分区分配方式可分为：固定分区分配动态分区分配动态重定位分区分配等。,最简单的可运行多道程序的存储器管理方式。,将内存划分为若干个固定大小的区域（分区），每个分区中装入一道作业，允许几道作业并发运行。当有空闲分区时，便可从后备队列中选择一个作业装入该分区。,1.划分分区的方法,分区大小相等分区大小不等更合理,5.3.1固定分区分配,2.内存分配,为了便于内存分配，通常将分区按大小排队，建立一张分区使用表。表项：分区起始地址、大小、状态（是否已分配），如图4-1。,图4-1分区分配表,100K132K196K324K452K,图4-2内存分配情况,当有一用户程序要装入时，由内存分配程序检索该表，从中找出一个能满足要求的、尚未分配的分区，将之分配给该程序，然后将该表项中的状态置为“已分配”；若找不到大小足够的分区，则拒绝为该用户程序分配内存。,3.固定分区方式的缺点,大程序可能无法装入；主存空间利用率不高作业往往不可能恰好填满分区；作业动态扩充主存困难；各分区作业要共享程序和数据也难实现；限制了多道运行的程序数。,5.3.2动态分区分配,1分区分配中的数据结构,可以有两种形式：空闲分区表、空闲分区链,1)空闲分区表,动态分区分配是根据进程的实际需要，动态地为之分配内存空间。在实现时，涉及到3个问题：数据结构、分配算法、分配及回收操作。,每个空闲分区占一个表目，表目包括：分区号、分区始址、分区大小等,空闲区,作业A,228K,作业B,800K,作业C,1000K,作业D,1300K,空闲区,空闲区,2)空闲分区链,优点：自身不占用存储空间。缺点：比空闲分区表管理复杂。,2分区分配算法,空闲分区表按地址递增排序。分配时从表首开始顺序查找，直至找到一个大小能满足要求的空闲分区；然后按作业大小划出一块内存空间分配给请求者，余下的空闲分区仍留在表中。,由首次适应算法演变而成。为进程分配内存时，不再是每次从表首开始查找，而是从上次扫描结束处开始顺序查找，直至找到一个大小能满足要求的空闲分区，从中划出一块与请求大小相等的分区分配给作业。为实现该算法，应设置一起始查找指针。,每次分配时，总是将能满足要求的最小分区分配给请求者。将空闲分区按其容量从小到大顺序排列，分配时从表首开始顺序查找加快查找。,首次适应算法,循环首次适应算法,最佳适应算法,最坏适应算法,举例说明,将空闲分区按其容量从大到小顺序排列，分配时从表首开始顺序查找。,在可变分区存储管理下，按地址排列的内存空闲区为：100KB、500KB、200KB、300KB和600KB。现有若干用户程序，其所需内存依次分别为212KB、417KB、112KB和426KB，分别用首次适应算法、最佳适应算法、最坏适应算法，将它们装入到内存的哪些空闲分区？哪个算法能最有效利用内存？,解：采用首次适应算法，空闲分区表为：,2分区分配算法,采用首次适应算法程序请求空闲区新空闲区,212KB,500KB,288KB,417KB,600KB,183KB,112KB,288KB,176KB,426KB，无法装入内存,采用最佳适应算法，空闲分区表为：,212KB,300KB,88KB,417KB,500KB,83KB,112KB,200KB,88KB,程序请求空闲区剩余空闲区,426KB,600KB,74KB,最坏适应算法，空闲分区表为：,212KB,600KB,388KB,417KB,500KB,83KB,112KB,388KB,276KB,426KB，无法装入内存,程序请求空闲区剩余空闲区,4.几种分配算法的比较由于回收后的空闲区要插入可用表或自由链中，而且可用表或自由链是按照一定顺序排列的，所以，除了搜索查找速度与所找到的空闲区是否最佳，释放空闲区的速度也对系统开销产生影响。搜索速度：最先适应算法最佳。尽管最佳适应算法或最坏适应算法看上去能很快找到一个最适合的或最大的空闲区，但后两种算法都要求首先把不同大小的空闲区按其大小进行排队，这实际上是对所有空闲区进行一次搜索。回收过程：最先适应算法最佳。因为使用最先适应算法回收某一空闲区时，无论被释放区是否与空闲区相邻，都不用改变该区在可用表或自由链中的位置，只需修改其大小或起始地址。而最佳适应算法和最坏适应算法都必须重新调整该区的位置。最先适应算法尽可能地利用低地址空间，从而保证高地址有较大的空闲区来放置要求内存较多的进程或作业。最佳适应法找到的空闲区最佳，用最佳适应法找到的空闲区或者是正好等于用户请求的大小或者是能满足用户要求的最小空闲区。尽管最佳适应法能选出最适合用户要求的可用空闲区，但这样做在某些情况下并不一定能提高内存的利用率。最坏适应算法正是基于不留下碎片空闲区这一出发点的。它选择最大的空闲区来满足用户要求，以期分配后的剩余部分仍能进行再分配。,3分区分配操作,1）分配内存,当某空闲分区满足m.sizeu.size时，执行如下操作：当m.size-u.sizesize时，将整个分区分配给请求者；否则，按作业大小划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲分区表（链）中。将分配区的首地址返回给调用者。,分配内存过程如图5-7所示。,图中假设：请求分区大小u.size；分区大小为m.size；不再切割的剩余分区大小为size。,2）回收内存,根据回收区的首地址，在空闲分区表（链）找到插入点，此时可能出现4种情况之一（假设空闲分区表按地址从低到高顺序排列）：,回收区与插入点的前一个空闲分区F1相邻接：将回收区与前一区合并，不必增加新表项，只需修改F1的大小为两者之和。,图5-8,回收区与高地址F2分区邻接：此时将回收分区与该分区合并，回收区的首地址为新分区的首地址，大小为两者之和。,回收区与前后分区F1和F2都邻接：将此3个分区合并，F1（前邻接区）的首地址为新分区的首址，大小为三者之和，取消F2表项。,回收区与任何空闲区都不邻接：在插入点建立一个新表项，填写回收区的首地址和大小。插入到空闲区表的适当位置（后移插入点后的各个表项）,3.动态重定位分区分配算法,与动态分区分配算法基本相同，只是增加了紧凑功能。当找不到满足请求的空闲区，但空闲区总和大于等于请求数时，进行紧凑操作。,图5-11动态分区分配算法流程图,1.分区管理要求对每一个作业都分配（）的内存单元。A、地址连续B、若干地址不连续C、若干连续的帧D、若干不连续的帧2.固定分区中各分区的大小是（）。A、相同的B、相同或者不同，但预先固定C、根据作业要求确定D、随作业个数而定3.（）存储管理支持多道程序设计，算法简单，但存储碎片多。A、段式B、页式C、固定分区D、段页式,3.可变分区管理方式按作业需求量分配主存分区，所以（）。A、分区的长度是固定的B、分区的个数是确定的C、分区的长度和个数都是确定的D、分区的长度不是预先固定的，分区的个数也不是确定的4.可变分区存储管理采用的地址转换公式是（）。A、绝对地址=界限寄存器值+逻辑地址B、绝对地址=下限寄存器值+逻辑地址C、绝对地址=基址寄存器值+逻辑地址D、绝对地址=块号块长+页内地址,5.3.5对换,1.对换的引入阻塞进程占用大量内存外存中的等待作业因无内存不能调入运行,资源浪费,对换把内存中暂时不能运行的进程或进程所需要的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具有运行条件的进程或进程所需要的程序和数据，调入内存。,整体对换(进程对换),对换以整个进程为单位广泛应用于分时系统中,部分对换,对换以“页”为单位页面对换对换以“段”为单位分段对换,虚存,本节介绍进程对换，部分对换将在虚拟存储器中介绍。,要实现进程对换，需实现三方面功能：,2.对换空间的管理,把外存分为：文件区和对换区,文件区,存放文件管理主要目标：提高文件存储空间利用率为此，采用离散分配方式,对换区,存放换出的进程管理主要目标：提高进程换入和换出的速度为此，采用连续分配方式,对换空间的管理进程的换出进程的换入,数据结构：对换区的空闲盘块管理的数据结构与动态分区分配方式采用的数据结构相似空闲区表或空闲区链。空闲分区表中应包含两个表项：对换区的首址及其大小，它们的单位是盘块号和盘块数。分配算法：对换区的分配与回收，与动态分区分配雷同，其分配算法可以是首次适应、循环首次适应或最佳适应分配算法。,3.进程的换出与换入,进程的换出,当一进程由于创建子进程而需要更多的内存空间，但无足够的内存空间等情况发生时，系统应将某个进程换出。,选择处于阻塞状态且优先级别最低的进程作为换出进程；启动磁盘，将该进程的程序和数据传送到磁盘的对换区上；若传送过程未出现错误，回收该进程所占用的内存空间，并对该进程的PCB做相应的修改。,进程的换入,系统应定时查看所有进程的状态，从中找出“就绪”状态但已换出的进程，将其中换出时间最久的进程换入，直至已无可换入的进程或无可换出的进程为止。,换出过程：,4.分区存储管理的主要优缺点分区存储管理的主要优点实现了多个作业或进程对内存的共享，有助于多道程序设计，从而提高了系统的资源利用率。该方法要求的硬件支持少，管理算法简单，因而实现容易。主要缺点有内存利用率仍然不高。和单一连续分配算法一样，存储器中可能含有从未用过的信息。而且，还存在着严重的碎小空闲区(碎片)不能利用的问题，这更进一步影响了内存的利用率。作业或进程的大小受分区大小控制，除非配合采用覆盖和交换技术。无法实现各分区间的信息共享。,5.3覆盖与交换技术5.3.1覆盖技术覆盖技术的基本思想：一个程序并不需要一开始就把它的全部指令和数据都装入内存后再执行。单CPU系统中，每一时刻事实上只能执行一条指令。可以把程序划分为若干个功能上相对独立的程序段，按照程序的逻辑结构让那些不会同时执行的程序段共享同一块内存区。通常，这些程序段都被保存在外存中，当有关程序段的先头程序段已经执行结束后，再把后续程序段调入内存覆盖前面的程序段。这使得用户看来，好像内存扩大了，从而达到了内存扩充的目的。覆盖技术要求程序员提供一个清楚的覆盖结构。即程序员必须完成把一个程序划分成不同的程序段，并规定好它们的执行和覆盖顺序的工作。,一般来说，一个程序究竟可以划分为多少段，以及让其中的哪些程序共享哪一内存区只有程序员清楚。这要求程序员既要清楚地了解程序所属进程的虚拟空间及各程序段所在虚拟空间的位置，又要求程序员懂得系统和内存的内部结构与地址划分，因此，程序员负担较重。例如，设某进程的程序正文段由A，B，C，D，E和F等6个程序段组成。它们之间的调用关系如图5.13(a)所示，程序段A调用程序段B和C，程序段B又调用程序段F，程序段C调用程序段D和E。由图5.13(a)可以看出，程序段B不会调用C，程序段C也不会调用B。因此，程序段B和C无需同时驻留在内存，它们可以共享同一内存区。同理，程序段D、E、F也可共享同一内存区。其覆盖结构如图5.13(b)所示。,图5.13覆盖示例在图5.13(b)中，整个程序正文段被分为两个部分。一个是常驻内存部分，该部分与所有的被调用程序段有关，因而不能被覆盖。这一部分称为根程序。图5.13(b)中，程序段A是根程序。另一部分是覆盖部分，图中被分为两个覆盖区。其中，一个覆盖区由程序段B，C共享。其大小为B，C中所要求容量大者。另一个覆盖区为程序段F，D，E共享。两个覆盖区的大小分别为50K与40K。这样，虽然该进程正文段所要求的内存空间是A(20K)+B(50K)+F(30K)+C(30K)+D(20K)+E(40K)=190K，但由于采用了覆盖技术，只需110K的内存空间即可开始执行。,5.3.2交换技术多道程序环境或分时系统中，同时执行好几个作业或进程。但是，这些同时存在于内存中的作业或进程，有的处于执行状态或就绪状态，而有的则处于等待状态。一般来说，等待时间比较长。例如从外存软磁盘读一块数据到内存有时要花0.1秒到1秒左右的时间。如果让这些等待中的进程继续驻留内存，将会造成存储空间的浪费。因此，应该把处于等待状态的进程换出内存。实现上述目标的方法很多，其中比较常用的方法之一就是交换。广义地说，交换是指先将内存某部分的程序或数据写入外存交换区，再从外存交换区中调入指定的程序或数据到内存中来，并让其执行的一种内存扩充技术。与覆盖技术相比，交换不要求程序员给出程序段之间的覆盖结构。而且，交换主要是在进程或作业之间进行，而覆盖则主要在同一个作业或进程内进行。另外，覆盖只能覆盖那些与覆盖程序段无关的程序段。,5.3.2交换技术交换进程由换出和换入两个过程组成。其中换出(swapout)过程把内存中的数据和程序换到外存交换区，而换入(swapin)过程把外存交换区中的数据和程序换到内存分区中。换出过程和换入过程都要完成与外存设备管理进程通信的任务。由交换进程发送给设备进程的消息m中应包含分区的分区号i、该分区的基址basei、长度sizei和方向及外存交换区中分区起始地址。交换进程和设备管理进程通过设备缓冲队列进行通信。交换技术大多用在小型机或微机系统中。这样的系统大部分采用固定的或动态分区方式管理内存。,在换出过程SWAPOUT(i)中，除了前5行描述所需要的控制信息之外，backupstorbasei是用来记录被换出数据和程序的起始地址以便换入时使用的。而send指令则驱动设备做相应的数据读写操作。,与SWAPOUT过程相同，可以写出SWAPIN过程：,5.4.1页面和页表,1页面,1）页面和物理块,最后一个页不满，称为页内碎片。,2）页面的大小,应是2的幂。通常为512B8KB,商用计算机的页面大小在512B64KB之间，以往的典型值为1KB，而现在更常见的页面大小为4KB和8KB。,将逻辑地址空间分成若干大小相等的片，称为页面或页(page)。页号从0开始。内存空间分成与页大小相同的若干存储块，称为块或页框(frame)。也从0开始编号。,连续分配方式会形成“碎片”“紧凑”须付出很大开销,产生了离散分配方式,不宜过小，也不宜过大,2地址结构,分页的逻辑地址结构如下：,位移量d也称页内地址。图中的地址长度为32位，每页大小为4KB，地址空间最多220（1M）个页。对于特定的机器，其地址结构是一定的。,若逻辑地址为A,页面大小为L,则页号P和页内地址d可按下式求得：,P=int(A/L)d=AmodL,举例说明,页面大小为4KB，逻辑地址为7800及5F86H，分别求它们的页号和页内偏移。,3.页表,系统为每个进程建立一张页表，记录了相应页在内存中对应的物理块号，实现从页号到物理块号的地址映射。,5.4.2地址变换机构,页表驻留在内存中，设置一个页表寄存器存放页表在内存中的始址。地址转换的原理如图4-12所示。,1.基本的地址转换机构,图5-13分页系统的地址变换机构,举例说明请看下页的例题,页表始址页表长度,页号P页内地址W,+,越界中断,页表寄存器,逻辑地址,b0b1b2b3,页号块号b,b2W,页表,物理地址,0123,物理地址=bL+W(L为页的长度),例题,2在采用页式存储管理的系统中，某作业的逻辑地址空间为4页(每页4096字节)，且已知该作业的页表如下表。试求出逻辑地址14688所对应的物理地址。,页表,页号P=INT(14688/4096)=3页内偏移d=14688%4096=2400(960H)由页号3查页表，得块号为9物理地址=94096+2400=39264(9960H),对于十六进制，由块号9与页内偏移960可“合成”物理地址9960H。问：若左边页表中的9改为30，则对应的物理地址是多少？,例题：某分页系统的逻辑地址为16位，其中高6位为页号，低10位为页内地址。请问：这样的地址结构一页有多少字节？逻辑地址可有多少页？一个作业最大的使用空间是多少？逻辑地址2318，4096，850对应的页号、页内地址分别是多少？,（1）由于低10位为页内地址，寻址能力为210=1024，于是一页有1024个字节（或1KB）。共有页面26=64。所以一个作业最大的使用空间是641024=64KB。（2）分页系统中每页都一样大（1KB），所以用逻辑地址除以页面大小，商为页号，余数为页内地址。于是：逻辑地址2318，页号为2，页内地址为270；逻辑地址4096，页号为4，页内地址为0；逻辑地址850，页号为0，页内地址为850。,2具有快表的地址转换机构,由分页系统的地址转换可知，每存取一个数据，要访问2次内存，计算机处理速度降低近1/2。为提高地址转换速度，在MMU中增设一个具有并行查寻能力的特殊高速缓冲寄存器，称为联想寄存器(AssociativeMemory)，或称快表。在IBM系统中称TLB(TranslationLookasideBuffer)，用于存放当前访问的那些页表项。此时的地址变换过程是：,MMU将页号送入高速缓存，将此页号与高速缓存中所有页号比较，若有匹配的页号，则将其对应的块号送物理地址寄存器中；若在快表中未找到对应的页表项，则还需访问内存中的页表，找到后，把从页表项中读出的块号送物理地址寄存器；同时，再将此页表项存入快表的一个寄存器单元中，亦即修改快表。如果快表已满，则OS必须淘汰一个老的页表项。,5.4.3两级和多级页表,现在大多数计算机系统，都支持非常大的逻辑地址空间（232264）。,考虑具有32位逻辑地址空间的分页系统：,若页面大小为4KB（即212B），则每个进程页表中的页表项可达1兆个，因每个页表项占用4个字节，故每个进程仅仅页表就要占用4MB的内存空间，而且还要求是连续的。显然这是不现实的。,解决此问题的办法有：,采用离散分配方式来解决难于找到一块连续的大内存空间的问题；办法：两级和多级页表,只将当前需要的部分页表项调入内存，其余的页表项驻留在磁盘上，需要时再调入。,1两级页表,采用离散方式来解决难于找到一块连续的大内存空间的问题，解决的办法是：,将页表分页将各个页面离散地存放在不同的物理块中为离散分配的页表再建立一张页表，称为外层（外部）页表,【例5-1】以32位逻辑地址空间为例，当页面大小为4KB（12位）时，采用两级页表结构时，再对页表分页，使每个页中包含210（1024）个页表项，则最多需要1024个页存放页表，即外部页表中页号P1为10位，外部页表中的外部页内地址P2也是10位。此时逻辑地址结构如下：,x86系统中，外层页号称为页目录索引，外层页内地址称为页表索引，它们合称“虚页号”WindowsNT中的虚地址结构,两级页表结构示意图,(页目录),每个进程一个页目录，每个页目录中索引项最多1024个,一个进程最多有1024个页表,一个页表映射的内存空间为4MB,【说明】本页注释是对上页的逻辑地址结构而言的。,图5-14两级页表结构,为地址变换方便，需设置一个外层页表寄存器。两级页表地址变换机构如图5-15所示(图中假设页的大小为4KB)。,在下一页举例说明,Pentium系列CPU(保护模式下)页式不分段地址转换过程,页目录1024个表项,每个页表1024个表项,图5-16Pentium系列CPU(保护模式下)页式不分段地址转换过程,返回,WindowsNT地址变换过程举例,设逻辑地址(虚地址)为00C02008H，则页目录索引号(外层页号)为3，页表索引号(外层页内地址)为2，页位移(页内地址)为8。地址变换过程如下图所示：,图5-17WindowsNT地址转换过程示例,1.在页式存储管理系统中，整个系统的页表个数是（）个。A、1B、2C、3D、和装入主存的作业个数相同2.碎片是指（）。A、存储分配完后所剩的空闲区B、没有被使用的存储区C、不能被使用的存储区D、未被使用，而又暂时不能使用的存储区3.碎片现象的存在使得（）。A、内存空间利用率降低B、内存空间利用率提高C、内存空间利用率得以改善D、内存空间利用率不影响,5.5.1分段存储管理方式的引入,主要是为了满足用户和程序员的下述需要：,方便编程,通常用户把自己的程序按逻辑关系分为若干个段，每段都从0开始编址，并有自己的名字和长度。因此，希望要访问的逻辑地址是由段名(段号)和段内偏移量(段内地址)决定的。,信息共享,在实现对程序和数据的共享时，是以信息的逻辑单位为基础的，比如，共享某个例程和函数。分页系统中的“页”只是存放信息的物理单位（块），并无完整的意义，不便于实现共享；而段却是信息的逻辑单位。,信息保护,信息保护同样是对信息的逻辑单位进行保护，因此，分段管理能更有效地实现信息保护功能。,动态增长,在实际应用中，往往有些段，特别是数据段，在使用过程中会不断增长，而事先又无法确切地知道数据段会增长到多大。前述的其它几种存储管理方式，都难以应付这种动态增长的情况，而分段存储管理方式却能较好地解决这一问题,动态连接,动态链接是指在作业运行之前，并不把几个目标程序链接起来。要运行时，先将主程序所对应的目标程序装入内存并启动运行，当运行过程中需要调用某段时，才将该段（目标程序）调入内存并进行链接。可见，动态链接也要求以段作为管理的单位。,5.5.2分段系统的基本原理,1分段,(1)作业地址空间划分成若干段，每段定义了一组逻辑信息。如,主程序段MAIN；子程序段X数据段D；栈段S,(2)每个段都有名字。为实现简单，常用段号代替段名（段号从0开始）；(3)每个段内都从0开始编址，并采用一段连续的地址空间。由于分多个段，所以地址是二维的，亦即逻辑地址由段号S和段内地址W组成。具体结构举例如下：,该地址结构中允许作业最多有4K(212)个段，每段最大长度为1MB(220)。,教材上段号为16bit，段内地址16bit，故最多有64K个段,PDP-11（PDP-11为迪吉多电脑(DigitalEquipmentCorp.)于1970到1980年代，所销售的一系列16位电脑）的段式逻辑地址结构：,段号（3位）段内偏移（13位）,Pentium系列CPU(保护模式下)段式不分页的逻辑地址,段号（12位）段内偏移（20位）,2段表,每个段占一个连续内存空间，各个段之间不要求连续（可以在不同的分区中）但和连续分配不同不同之处是什么？故需要利用段表来进行地址变换（动态重定位）段表结构：段长，基址。,每访问一个数据，要访问两次内存，速度减慢1/2。但段表存于联想存储器中时，比没有地址变换的常规存储器存取速度仅减慢10%15%。,图5-21分段系统的地址变换过程,3地址变换机构,5.5.3信息共享,分页系统中的信息共享,分段系统的一个突出优点，是易于实现段的共享，即允许若干个进程共享一个或几个段，且对段的保护也十分简单易行。分页系统虽然也能实现程序和数据的共享，但远不如分段系统方便。,【例】有一个多用户系统，可同时接纳40个用户，他们都执行一个文本编辑程序(TextEditor)。如果文本编辑程序有160KB的代码和40KB的数据区，则共需8MB内存来支持40个用户。如果160KB的代码是可重入的(Reentrant)，则无论是在分页系统还是在分段系统中，该代码都能被共享，在内存中只需保留一份文本编辑程序的副本，此时所需的内存空间仅为1760KB(4040+160)，而不是8000KB。,假定每个页面大小为4KB，那么160KB的代码将占40个页面，数据区占10个页面，为实现代码共享，应在每个进程的页表中都建立40个页表项，它们的物理块号都是21#60#，在每个进程的页表中，还需为自己的数据区建立页表项，它们的物理块号分别是61#70#、71#80#、81#90#，等等。图5-25是分页系统中共享editor的示意图。(见下页),图5-25分页系统中共享editor的示意图,共享的editor是可重入代码，又称为“纯代码”，是一种允许多个进程同时访问的代码。可重入代码在执行中不允许有任何改变。,5.5.4段页式存储管理方式,分页系统能有效地提高内存利用率分段系统能很好地满足用户的需要,取长补短段页式存储管理,1基本原理,先将用户程序分成若干段，再把每段分成若干页。,逻辑地址由3部分组成：段号、段内页号、页内地址。如下所示：,利用段表和页表实现地址映射，如下页的图5-27所示。,图5-27利用段表和页表实现地址映射,2地址变换过程,访问3次内存：第一次，段表；第二次，页表；第三次，取出指令或数据。,图5-28段页式系统的地址变换机构,需配置一个段表寄存器，其中存放段表始址、段表长度。原理见图5-28。,Pentium系列CPU(保护模式下)段页式地址转换过程,页目录1024个表项,每个页表1024个表项,图5-29Pentium系列CPU(保护模式下)段页式地址转换过程,返回,（）1、页式存储管理系统不利于共享和保护。（）2、页式存储管理中，为了提高内存的利用效率，允许同时使用不同大小的页面。（）3、页式存储管理中，一个作业可以占用不连续的内存空间，而段式存储管理中，一个作业则是占用连续的内存空间。4、（）存储管理方式提供一维地址结构。A、固定分区B、分段C、分页D、分段和段页式5、分段管理提供（）维的地址结构。分页管理提供()的维地址结构A、1B、2C、3D、46、（）实现了两种存储方式的优势互补。A、请求分页管理B、可变式分区管理C、段式管理D、段页式管理,7、段页式存储管理汲取了页式管理和段式管理的长处，其实现原理结合了页式和段式管理的基本思想，即（）。A、用分段方法来分配和管理物理存储空间，用分页方法来管理用户地址空间。B、用分段方法来分配和管理用户地址空间，用分页方法来管理物理存储空间。C、用分段方法来分配和管理主存空间，用分页方法来管理辅存空间。D、用分段方法来分配和管理辅存空间，用分页方法来管理主存空间。8、段页存储管理中，系统中（）。A、每个作业一个段表，一个页表B、每个作业的每个段一个段表一个页表C、每个作业一个页表，每个段一个段表D、每个作业一个段表，每个段一个页表9、在段页式管理中，每取一次数据，要访问（）次内存。A、1B、2C、3D、4,5.7请求分页存储管理方式,5.7.1请求分页中的硬件支持,1页表机制,每个页表表项如下所示：,页号和外存地址一般不是页表的一部分,状态位P：指示该页是否已调入内存访问位A：记录本页在一段时间内被访问的次数修改位M：表示该页被调入内存后是否被修改过外存地址：指出该页在外存的地址，通常是磁盘物理块号。操作系统在处理页面失效时需要把信息保存操作系统内部的软件表格中。硬件不