操作系统原理与实践教程第二版第5章：存储管理.ppt

《操作系统原理与实践教程第二版第5章：存储管理.ppt》由会员分享，可在线阅读，更多相关《操作系统原理与实践教程第二版第5章：存储管理.ppt（99页珍藏版）》请在三一办公上搜索。

1、第5章 存 储 管 理,5.1 存储管理的概念5.2 连续内存分配5.3 内存不足时的管理5.4 分页存储管理5.5 分段存储管理5.6 段页式存储管理5.7 虚拟存储器5.8 请求分页存储管理技术,5.1 存储管理的概念,为了解决CPU和存储器之间速度上的不匹配，在现代计算机系统中，存储系统通常采用层次结构，存储层次可粗略分为三级：最高层为CPU寄存器，中间为主存，最底层是辅存。根据具体功能还可以细分为寄存器、高速缓存、主存储器、磁盘缓存、辅存储设备(固定磁盘、可移动存储介质)5层。,5.1 存储管理的概念,操作系统的存储管理负责对存储器空间的分配、回收以及提供存储层次间数据移动的管理机制。

2、例如主存与磁盘缓存、高速缓存与主存间的数据移动等。,5.1.1 多级存储结构,1.寄存器 寄存器是中央处理器的组成部份。寄存器访问速度最快，完全能与CPU协调工作，价格昂贵，容量不大。寄存器可用来暂存指令、数据和地址。寄存器的长度一般以字(word)为单位。寄存器可以加速对存储器的访问速度，用途包括：(1)暂存执行算术及逻辑运算的数据；(2)用于寻址，存于寄存器内的地址可用来指向内存的某个位置；(3)用来读写数据到计算机的外围设备。,5.1.1 多级存储结构,2.主存储器 主存储器(简称内存或主存)是用于保存当前进程运行时的程序和数据。CPU能直接随机存取内存中的数据和程序，CPU的控制部件从

3、内存中读取数据并将它们装入到寄存器中，或者从寄存器存入到内存。CPU与外围设备交换信息一般也借助于主存储地址空间。内存以字节为基本存储单位，每个存储单元分配一个唯一的地址，称为内存地址。主存储器的访问速度远低于CPU执行指令的速度，为缓和这一矛盾，在计算机系统中引入了寄存器和高速缓存。,5.1.1 多级存储结构,3.高速缓存 高速缓存介于中央处理器和主存储器之间的高速小容量存储器，其容量大于寄存器而小于主存储器，访问速度要快于主存储器而低于寄存器。工作原理为：根据程序局部性原理，正在使用的主存储器某一单元邻近的那些单元将被访问的可能性很大。由于高速缓存的速度越高价格也越贵，因此目前的计算机系统

4、中多设置两级或多级高速缓存。两级缓存比一级缓存速度慢，但容量更大，主要用做一级缓存和内存之间数据临时交换的地方。缓存中存放的都是CPU频繁访问的数据，所以缓存越大处理器效率就越高，同时由于缓存的物理结构比内存复杂很多，所以其成本也很高。,5.1.1 多级存储结构,4.磁盘缓存磁盘缓存是操作系统为磁盘输入输出而在普通物理内存中分配的一块内存区域。由于目前磁盘的I/O速度远低于主存的访问速度，因此根据程序局部性原理，将频繁访问的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数，提高访问速度。磁盘缓存分为读缓存和写缓存。,5.1.2 程序的运行过程,在多道程序环境下，要使程序运行，必

5、须先为之创建进程。而创建进程的第一件事，便是将程序和数据装入内存。如何将一个用户源程序变为一个可在内存中执行的程序，简单的说，要经过编辑、编译、链接、装入和运行等几个阶段。,5.1.2 程序的运行过程,1.编辑阶段在编辑阶段，用户使用某种编辑软件把程序代码输入到计算机中，并以文件的形式保存到指定的磁盘上，形成用户的源程序文件，即源文件。2.编译阶段计算机只能识别二进制语言，所以源程序文件不能直接在计算机上运行，必须经过编译软件的编译，形成相应的二进制目标代码后才能被计算机识别。通常，用户程序的执行需要经过编译阶段，由初始的文本文件(file1.c)变成CPU可以识别的一系列二进制代码文件(fi

6、le1.o)。,5.1.2 程序的运行过程,3.链接阶段 将编译或汇编后得到的一组目标模块以及它们所需的库函数装配成一个完整的装入模块的过程就是程序的链接阶段。根据链接时间的不同，链接可分为三种：(1)静态链接。在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块，以后不再拆开。(2)装入时动态链接。用户源程序编译后得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式，即在装入一个目标模块时，若发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存。(3)运行时动态链接。对某些目标模块的链接，是在程序执行中需要该模块时，才对它进行链接。运

7、行时动态链接是装入时动态链接方式的一种改进，即在执行过程中，当发现一个被调用模块尚未装入内存时，立即由系统去找到该模块并将之装入内存，把它链接到调用模块上。,5.1.2 程序的运行过程,4.装入阶段 CPU在运行程序时，首先要把用户程序装入内存。为了保证程序的正确执行，程序在装入内存时要进行重新定位，即将程序和数据捆绑到内存地址，以便CPU能够正确寻址。通常，程序装入内存的方式有以下3种：(1)绝对装入方式。在程序编译时如果就知道进程在内存中的驻留地址，那么就可以生成绝对地址。装入模块可以把用户程序装入到指定的位置，这时程序中用到的所有地址都是内存中的绝对地址。(2)可重定位装入方式。在多道程

8、序环境下，程序编译链接后的目标模块起始地址通常是从0开始的，程序中的其它地址也都是相对于起始地址计算的。此时采用可重定位装入方式，根据内存的当前情况，将目标模块装入到内存的适当位置。(3)动态运行时装入方式。动态运行时的装入程序把目标模块装入内存后，并不立即把目标模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是相对地址。为使地址转换不影响指令的执行速度，这种方式需要一个重定位寄存器的支持。,5.1.2 程序的运行过程,5.运行阶段在运行阶段，进程调度程序按照某种策略选中用户程序，给其分配CPU使之运行，完成用户提交的任务。运行完毕

9、后，系统释放其占有的内存空间。,5.1.3 存储管理的任务和功能,存储管理的主要任务是：(1)支持多道程序的并发执行，使多道程序能共享存储资源，在互不干扰的环境中并发执行。(2)方便用户，使用户减少甚至摆脱对存储器的管理，使用户从存储器的分配、保护和共享等繁琐事物中解脱出来。(3)提高存储器的利用率和系统吞吐量。(4)从逻辑上扩充内存空间，支持大程序能在小的内存空间运行或允许更多的进程并发执行。,5.1.3 存储管理的任务和功能,现代操作系统的存储管理应具有以下功能：1.存储空间的分配和回收为每道程序分配内存空间，使它们“各得其所”；尽量提高存储器的利用率，以减少不可用的存储空间(“碎片”)；

10、允许正在运行的程序申请附加内存空间，以适应程序或数据动态增长的需要。为了合理有效地利用内存，在设计内存分配和回收方法时，必须考虑和确定以下几种策略和数据结构：(1)分配结构。(2)放置策略。(3)交换策略。(4)调入策略。(5)回收策略。,5.1.3 存储管理的任务和功能,2.地址转换 在将用户程序部分或全部地装入内存空间时，要实现逻辑地址到物理地址的映射。这种把逻辑地址转换为物理地址的过程称作重定位或地址映射，实现地址重定位或地址映射的方法有两种：静态地址重定位和动态地址重定位。(1)静态地址重定位静态地址重定位是指在用户程序执行之前完成地址映射工作，即把程序的逻辑地址都转换为实际的内存物理

11、地址。静态地址重定位的地址变换只是在装入时一次完成，而在程序运行期间不再变化。静态地址重定位的优点是不需要硬件支持，实现存储管理的软件算法简单。静态重定位的缺点如下：1)要求给每个作业分配一个连续的存储空间，并且在作业执行期间不能再移动，从而也就不能实现重新分配内存。2)静态地址重定位必须占用连续的内存空间，这就难以做到程序和数据的共享。3)用户必须事先确定所需的存储量，若所需的存储量超过可用存储空间时，用户必须考虑覆盖结构。,5.1.3 存储管理的任务和功能,(2)动态地址重定位动态地址重定位是指在程序执行过程中，CPU在访问内存之前，将要访问的程序或数据地址转换为内存地址。地址重定位机构需

12、要一个(或多个)基地址寄存器BR和一个(或多个)程序逻辑地址寄存器VR。指令或数据的内存地址MA与逻辑地址的关系为：MA=(BR)+(VR),5.1.3 存储管理的任务和功能,(2)动态地址重定位动态地址重定位具体过程如下：1)初始化基地址寄存器BR，逻辑地址寄存器VR。2)将程序段装入内存，且将其占用的内存区首地址送到BR中。例如，在图5-4中，(BR)=4000。3)在程序执行过程中，将所要访问的逻辑地址送入VR中，例如，在图5-4中执行LOAD 1,400语句时，将所要访问的逻辑地址400放入VR中。4)地址变换机构把VR和BR的内容相加，得到实际访问的物理地址。,5.1.3 存储管理的

13、任务和功能,(2)动态地址重定位动态地址重定位的主要优点有：1)可以对内存进行非连续分配。2)用户作业在执行过程中，可以动态申请存储空间和在主存中移动。动态地址重定位提供了实现虚拟存储器的基础。3)有利于程序段的共享。动态地址重定位的主要缺点有：1)需要附加的硬件支持。在进行逻辑地址与物理地址映射时，需要依靠硬件地址变换机构才能完成。2)实现存储管理的软件算法比较复杂。,5.1.3 存储管理的任务和功能,3.主存空间的共享主存储器空间的共享是为了提高主存空间的利用率，有两方面的含义：(1)共享主存储器资源。采用多道程序设计技术使若干个程序同时进入主存储器，各自占用一定数量的存储空间，共同使用一

14、个主存储器。(2)共享主存储器的某些区域。若干个作业有共同的程序段或数据时，可将这些共同的程序段或数据存放在某个存储区域，各作业执行时都可访问它们。4.主存空间的保护主存储器中不仅有系统程序，而且还有若干道用户程序。为了避免主存中的多道程序相互干扰，必须对主存中的程序和数据进行保护。通常由硬件提供保护功能，软件配合实现。一般来说，一个程序执行时可能有下列三种情况：(l)对属于自己主存区域中的信息既可读又可写；(2)对公共区域中允许共享的信息或获得可使用的其他用户的信息，可读而不准修改；(3)对未获得授权使用的信息，既不可读又不可写。,5.1.3 存储管理的任务和功能,5.主存储空间的扩充主存储

15、空间扩充的任务是从逻辑上来扩充内存容量，在计算机硬件的支撑下，通过软硬件协作，可把磁盘等辅助存储器作为主存储器的扩充部分来使用，使用户认为系统拥有的内存空间远比其实际空间大。其原理是根据程序执行时表现的局部性特征，即程序在执行过程中的一个较短时间内，所执行的指令地址或操作数地址分别局限于一定的存储区域中。这样，存储管理系统就把进程中那些不经常被访问的程序段和数据放入外存中，待需要访问时再将它们调入内存。系统必须具有下述功能：(1)调入功能。在程序执行之前，没有必要全部装入内存，允许仅装入一部分程序和数据即可启动运行，运行时一旦发现运行所需程序或数据不在内存时，通过请求调入功能，将所需部分调入内

16、存。(2)置换功能。当内存中没有足够空间装入所需调入的部分时，系统能通过置换功能将内存中一部分暂时不用的内容调至外存。,5.1.3 存储管理的任务和功能,6.对换对换的主要任务是实现在内存和外存之间的全部或部分进程的对换，即将内存中处于阻塞状态的进程调换到外存上，而将外存上处于就绪状态的进程换入内存。对换的目的主要是为了提高内存利用率，提高系统的吞吐量。,5.1.4 存储管理方式,其主要目的有两个：一是提高存储器的利用率，这样由固定式分区存储分配方式演变为分页式存储管理方式。二是提高系统吞吐量，更好地满足用户需要，由此，产生了分段式存储管理方式和虚拟存储器。,5.1.4 存储管理方式,1.连续

17、分配方式。连续分配是指为一个系统或用户程序分配一个连续的内存空间。(1)单一连续分配方式。该方式把内存分为系统区和用户区两部分，系统区仅供操作系统使用，用户区中仅驻留一道程序，整个用户区为一用户独占。单一连续分配仅适用于单用户、单任务操作系统，不适用于多道程序环境。(2)分区式分配方式。它把内存划分为若干个大小不等的区域，除操作系统占用一个区域之外，其余区域由多道环境下的各并发进程共享。分区式分配要求将一个用户程序分配到一个连续的内存空间中，因此可能产生多个不可利用的零头(也称“碎片”)。按照分区的时机，分区管理可以分为固定分区、动态分区和可重定位分区。固定分区式。这种方法把内存区域划分为若干

18、个固定大小的区域，以连续存储各个进程的程序和数据。动态分区式。又称为可变分区，是在作业的处理过程中，根据程序的大小，动态地对内存进行划分，因此各分区的大小是不定的，分区数目也是可变的。动态分区方式较之固定分区方式，改变了即使是小作业也要占据大分区的内存浪费现象，显著地提高了存储器的利用率。可重定位分区。可重定位分区分配与动态分区分配基本相同，差别仅在于前者增加了拼接功能。在可重定位分区分配中，若系统中存在满足作业空间要求的空闲分区，则按照与动态分区分配相同的方式分配内存；若系统中找不到满足作业要求的空闲分区，且系统中空闲分区容量总和大于作业要求，则进行拼接。,5.1.4 存储管理方式,2.离散

19、分配方式连续分配方式相对简单，但带来严重的碎片问题，导致内存利用率低。为解决该问题，操作系统引入离散分配方式。它将用户程序离散地分配到内存的多个不相邻接的区域中。离散分配方式有以下三种：(1)分页存储管理。在该方式中，用户程序的地址空间被划分成若干个固定大小的区域，称为“页”，相应地，内存空间也以“页”大小为单位被划分为若干个物理块，这样，可将用户程序的任一页放入内存的任一块中，实现离散分配。分页存储管理方式下，内存中的碎片大小不会超过一页。(2)分段存储管理方式。为了满足用户的需要，更好地实现共享和保护，现代操作系统引入分段存储技术。它把用户程序的地址空间按内容或过程关系分成若干个大小不等的

20、段。在进行存储分配时，以段为单位，这些段在内存中可以不相邻接，故也实现了离散分配。(3)段页式存储管理。段页式存储管理集成了分页和分段两种存储管理方式的优点，既提高了存储器的利用率，又能满足用户要求，更好地实现共享和保护，是目前用得较多的一种存储管理方式。,5.1.4 存储管理方式,3.虚拟存储系统为了满足用户对内存的需求，进一步提高内存利用率，现代操作系统引入虚拟存储管理方式。它能使一个大的用户程序在较小的内存空间内运行，实现在逻辑上扩充物理内存的容量。虚拟存储系统有以下三种：(1)请求分页系统。它是在分页系统的基础上，增加请求调页功能、页面置换功能形成的页式虚拟存储系统。它允许只装入若干页

21、的用户程序和数据，便可启动运行，以后再通过调页功能及页面置换功能，陆续地把即将要运行的页面调入内存，同时把暂不运行的页面换出到外存上，置换时以页面为单位。(2)请求分段系统。它是在分段系统的基础上，增加请求调段功能、分段置换功能形成的段式虚拟存储系统。它允许只装入若干段的用户程序和数据，便可启动运行，以后再通过调段功能和置换功能将暂不运行的段调出，同时调入即将运行的段，置换时以段为单位。(3)请求段页式系统。它是在段页式系统的基础上，增加请求调页和页面置换功能形成的段页式虚拟存储系统。它是目前最好的，也是最为流行的一种存储管理方式。,5.2 连续内存分配,连续分配方式是指为一个系统程序或用户程

22、序分配一个连续的内存空间，这种分配方式曾被广泛应用于早期(20世纪6070年代)的操作系统中。它有两种方式：单一连续分配和分区式分配方式。,5.2.1 单一连续分配,单一连续分配是一种简单的存储分配方案，主要用于单用户单任务操作系统。它把内存分为两个区域：系统区和用户区。系统区是操作系统专用区，不允许用户程序直接访问，一般在内存低地址部分，剩余的内存区域为用户区。应用程序装入到用户区，可使用用户区全部空间。优点是方法简单，只需要很少的软件和硬件支持，易于实现。缺点是它仅适用于单道程序，内存中只能装入一道作业，对要求内存空间少的程序，造成内存浪费。而且它采用静态分配，即作业一旦进入内存，就要等到

23、它执行结束后才能释放内存，程序全部装入后，很少使用的程序部分也占用内存。因而，不能使处理器和内存得到充分利用。,5.2.2 固定分区分配,固定分区分配把内存分为一些大小相等或不等的区域，一旦划分结束，则在整个执行过程中每个分区的长度和内存的总分区个数将保持不变。1.划分分区的方法(1)分区大小相等。所有的内存分区大小相等。这只适合于多个相同程序的并发执行，适用于一些控制多个同类对象的环境。但是对于程序规模差异较大的多道环境不太适合，比如大于分区大小的进程无法装入，而且小进程也会占用一个分区，造成内存碎片(即无法被利用的空闲存储空间)太大。(2)分区大小不等。为了克服分区大小相等而缺乏灵活性的缺

24、点，可把内存区划分成含有多个小分区，适量的中等分区，少量的大分区。根据程序的大小，分配当前空闲的、适当大小的分区，这样可以有效地改善前一种方法的缺陷。,5.2.2 固定分区分配,2.内存分配与回收为了便于内存的管理和控制，通常将内存分区根据其大小进行排队，并为之建立一张分区说明表，表中包含各分区的区号、大小、起始地址及状态(是否为空闲)等信息。内存的分配释放、存储保护以及地址变换等都通过分区说明表进行。,5.2.2 固定分区分配,2.内存分配与回收固定分区分配算法流程。当用户程序要装入内存时，由内存分配程序检索分区说明表，从表中找出一个能满足要求的空闲分区分配给该程序，然后修改分区说明表中相应

25、表项的状态信息；若找不到满足其大小要求的空闲分区，则拒绝为该程序分配内存。固定分区的回收比较简单，当程序执行完毕不再需要内存资源时，释放程序占用的内存分区空间，管理程序只需将对应分区的状态信息设置为未分配即可。由于作业的大小并不一定与某个分区大小相等，因此，在绝大多数已分配的分区中，都有一部分存储空间被浪费掉，由此可见，采用固定分区分配存储管理方法，内存不能得到充分利用。,5.2.3 动态分区分配,动态分区分配又称为可变分区分配，是根据作业运行的实际需要，动态地为之分配内存空间。动态分区法并不预先设置分区的数目和大小，而是在作业装入内存时，根据作业的大小动态建立分区，使分区大小正好满足作业的需

26、要。系统中分区的大小是可变的，分区的数目也是可变的。动态分区改变了固定分区中那种即使是小作业也要占据大分区的内存浪费现象，从而提高内存的利用率。,5.2.3 动态分区分配,1.动态分区分配中的数据结构(1)空闲分区表。在空闲分区表中，内存中的每个空闲分区占用一个表项，每个表项包含分区号、分区起始地址、分区大小以及状态等信息。采用空闲分区表结构，管理过程比较简单，但表的大小难以确定，而且空闲分区表要占用一部分内存。(2)空闲分区链。空闲分区链使用链表指针将内存中的空闲分区链接起来，它利用每个内存空闲区的头几个单元存放本空闲区的大小及下个空闲区的起始地址，从而把所有的空闲区链接起来。然后，系统再设

27、置一个空闲链首指针让其指向第一个空闲区，这样，管理程序就可以通过链首指针查到所有的空闲区。采用空闲分区链法管理空闲区，查找时要比空闲分区表困难，但由于空闲分区链指针是利用空闲区自身的单元，所以不必占用额外的内存区。无论是采用空闲分区表方式还是空闲分区链方式，空闲分区表或空闲分区链中的各项都要按照一定的规则排列以利于查找和回收。,5.2.3 动态分区分配,2.动态分区分配算法 动态分区分配主要解决2个问题：(1)按照作业要求的内存大小，从空闲分区表(链)中寻找出合适的空闲区分配给作业，如果这个空闲分区的容量比作业申请的空间容量要大，则将该分区一分为二，一部分分配给作业，剩下的一部分仍然留在空闲分

28、区表(链)中；(2)分配空闲区之后，更新空闲分区表(链)。,5.2.3 动态分区分配,(1)最先适应算法最先适应算法又称首次适应算法，该算法要求空闲分区表或空闲分区链按起始地址递增的次序排列。在进行内存分配时，从空闲分区表(链)首开始顺序查找，一旦找到大于或等于所要求内存长度的分区，则结束查找。然后，该算法从该分区中划出所要求的内存长度分配给请求者，余下的空闲分区仍留在空闲分区表(链)中，同时修改其相应的表(链)项。该算法的特点是优先利用内存低地址部分的空闲分区，从而保留高地址部分的大空闲区，但由于低地址部分不断被划分，致使低地址端留下许多难以利用的小空闲分区，而每次查找又都是从低地址部分开始

29、，增加了查找可用空闲分区的开销。,5.2.3 动态分区分配,(2)循环首次适应算法循环首次适应算法又称下次适应算法，它是由首次适应算法演变而来的。在为作业分配内存空间时，不再每次从空闲分区表(链)首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直到找到第一个能满足其大小要求的空闲分区为止。然后，再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍然留在空闲分区表(链)中。该算法的特点是使存储空间的利用更加均衡，不致于使小的空闲分区集中在存储器的一端，减少了查找空闲分区的开销。但这会导致缺乏大的空闲分区。,5.2.3 动态分区分配,(3)最佳适应算法最佳适应算法

30、要求空闲分区按容量大小递增的次序排列。当用户作业申请一个空闲区时，存储管理程序从空闲分区表(链)首开始顺序查找，当找到第一个满足要求的空闲区时，停止查找。按这种方式为作业分配内存，就能把既满足作业要求又与作业大小最接近的空闲分区分配给作业。如果空闲分区大于作业的大小，则与最先适应算法相同，将减去作业请求长度后的剩余空闲区仍然留在空闲分区表(链)中。最佳适应算法的特点是尽可能为作业选择大小一致的空闲分区，从而保留大的空闲分区。但空闲分区一般不可能正好和作业申请的内存空间大小相等，因而将其分割成两部分时，往往使剩下的空闲分区非常小，从而在存储器中留下许多难以利用的小空闲分区。,5.2.3 动态分区

31、分配,(4)最坏适应算法最坏适应算法要求空闲分区按其大小递减的顺序组成空闲分区表(链)。当用户作业申请一个空闲区时，先检查空闲分区表(链)的第一个空闲分区的大小是否大于或等于所要求的内存长度，若空闲分区表(链)的第一项长度小于所要求的大小，则分配失败，否则从该空闲分区中划出与作业大小相等的一块内存空间分配给作业，余下的空闲分区仍然留在空闲分区表(链)中。最坏适应算法的特点是总是挑选满足作业要求的最大分区分配给作业，这样使分给作业后剩下的空闲分区也比较大，能装下其它作业。但由于最大的空闲分区总是因首先分配而划分，当有大作业到来时，其存储空间的申请往往得不到满足。,5.2.3 动态分区分配,(1)

32、查找速度。从查找速度上看，最先适应算法具有最佳性能，尽管最佳适应算法或最坏适应算法看上去都能很快地找到一个最适合的或最大的空闲区。(2)释放速度。从回收区释放速度来看，最先适应算法是最佳的，因为使用最先适应算法时，无论被释放区是否与空闲区相邻，都不用改变该区在空闲分区表(链)的位置，只需修改其大小和起始地址即可。(3)利用率。最先适应算法优先利用内存低地址部分的空闲分区，从而保证高地址有较大的空闲区来满足内存需求较大的作业。虽然最佳适应算法找到的空闲区是最佳的，但空闲分区一般不可能正好和作业申请的内存空间大小相等，因而将其分割成两部分时，往往使剩下的空闲分区非常小，从而在存储器中留下许多难以利

33、用的小空闲分区。最坏适应算法是基于减少内存碎片这一出发点的，它选择最大的空闲区来满足用户要求，使分配后的剩余部分仍能进行再分配。,5.2.3 动态分区分配,3.动态分区分配 在内存分配中，系统利用某种分配算法，为作业从空闲分区表(链)中找到所需大小的分区。设作业请求的分区大小为u.size，表中每个空闲分区的大小可表示为m.size。若size(size是预先设定的不可再切割的剩余分区的大小)，表明空闲区多余部分太小不可再切割，将整个分区分配给作业；否则(即多余部分大于size)，从该分区中按请求大小划出一块内存空间分配给作业，余下的部分仍留在空闲分区链(表)中。然后，将分配区的首地址返回给调

34、用者。,5.2.3 动态分区分配,3.动态分区回收当进程运行结束释放内存时，系统要回收已经使用完毕的空闲区，并将其插入空闲分区表(链)。在将回收的空闲区插入空闲分区表(链)时，要考虑剩余空闲区的合并问题，即把不连续的零散空闲区集中起来，此时可能出现以下四种情况之一：,5.2.3 动态分区分配,3.动态分区回收1)回收区的上下两相邻分区都是空闲区，如图5-9(a)所示。此时应将三个空闲区合并。新空闲区的起始地址为上空闲区的起始地址，大小为三个空闲区之和。空闲区合并之后，取消空闲分区表(链)中下空闲区的表目或链指针，并修改上空闲区的对应项。2)回收区的上相邻区是空闲区,如图5-9(b)所示。此时应

35、将回收区与上空闲区合并为一个空闲区，其起始地址为上空闲区的起始地址，大小为上空闲区与回收区之和。合并之后，修改上空闲区对应的空闲分区表的表目或空闲分区链指针。3)回收区的下相邻区是空闲区，如图5-9(c)所示。此时应将回收区与下空闲区合并，并将回收区的起始地址作为合并后的起始地址，合并区的长度为回收区与下空闲区之和。合并之后，修改空闲分区表(或链)中相应的表目或链指针。4)回收区的上下两相邻区都不是空闲区，如图5-9(d)所示，则将回收区作为一个新的空闲区插入空闲分区表(链)中。,5.2.4 可重定位分区分配,在连续内存分配中，必须把一个系统程序或用户作业装入一个连续的内存空间。虽然动态分区比

36、固定分区的内存利用率高，但由于各个进程申请和释放内存空间的结果，在内存中经常会出现大量的分散的小空闲区。如果系统中有若干个小分区，其总容量大于要装入的作业，但由于它们不相邻接，致使作业不能装入内存。,5.2.4 可重定位分区分配,1.碎片和拼接技术 内存中容量太小、无法利用的小分区称作“碎片”或“零头”。根据碎片出现的位置，可以分为内部碎片和外部碎片两种。在一个分区内部出现的碎片(即被浪费的空间)称作内部碎片，如固定分区法就会产生内部碎片；在所有分区之外新增的碎片称作外部碎片，如在动态分区法实施过程中出现的越来越多的小空闲块就是外部碎片，由于它们太小，无法装入一个进程，因而被浪费掉。,5.2.

37、4 可重定位分区分配,1.碎片和拼接技术通过移动把多个分散的小分区拼接成一个大分区的方法称为拼接技术。在拼接过程中，进程需要在内存中移动，因此拼接的实现需要动态重定位技术的支持。利用拼接技术消除碎片，需要对分区中的大量信息进行移动，这一工作要耗费大量的CPU时间。为了减少信息移动的数量，可以根据拼接时需要移动进程的大小和个数，来确定空闲区究竟应该放在何处，即确定是应该放在内存的低地址端、中间、还是高地址端。拼接技术的实现还存在一个拼接时机的问题，这个问题有两种解决方案：第一种方案是在某个分区回收时立即进行拼接，这样在内存中总是只有一个连续的空闲区，但该实现方案因拼接频率过高而使系统开销加大；第

38、二种方案是当找不到足够大的空闲分区且空闲分区的总容量可以满足作业要求时进行拼接，该实现方案拼接的频率比上一种方案要小的多，但空闲分区的管理稍微复杂一些。,5.2.4 可重定位分区分配,2.可重定位分区分配技术 可重定位分区分配算法与动态分区分配算法基本相同，差别仅在于前者增加了拼接功能。在可重定位分区分配算法中，若系统中存在满足作业空间要求的空闲分区，则按照与动态分区分配相同的方式分配内存；若系统中找不到满足作业要求的空闲分区，且系统中空闲分区容量总和大于作业要求，则进行拼接。可重定位分区分配技术可以消除碎片，能够分配更多的分区，有助于多道程序设计及提高内存利用率，但由于拼接技术复杂，并且需要

39、花费大量CPU时间。目前解决外部碎片问题很少采用拼接技术，而是采用非连续内存分配技术，即允许物理空间为非连续的，这样只要有物理内存就可以分配给进程。这种方案有两种实现技术：分页和分段，也可以将两者结合起来使用。,5.3 内存不足时的管理,当出现内存不够用时，操作系统可以采取覆盖、交换、拼接的方法来解决这个问题。5.3.1 覆盖 程序运行时并不需要把它的全部指令和数据都装入内存。在单CPU系统中，每一时刻只能执行一条指令。因此，可以按照逻辑功能把程序划分为若干个相对独立的程序段，按照程序的逻辑结构让那些不会同时执行的程序段共享同一块内存区。通常，这些程序段都被保存在外存中，当有关程序段的先头程序

40、段执行结束后，再把后续程序段调入内存中，并覆盖前面的程序段。这种方式让用户感觉内存扩大了，从而达到逻辑上扩充内存的目的。,5.3 内存不足时的管理,5.3.2 交换 交换是指把内存中暂不能运行的进程，或暂时不用的程序和数据换出到外存上，以便腾出足够的内存空间，把已具备运行条件的进程或进程所需要的程序和数据，换入内存，并让其执行的一种内存扩充技术。如果交换是以整个进程为单位，称之为“整体交换”或“进程交换”，这种交换广泛应用于分时系统中；如果交换是以“页”或“段”为单位，则分别称之为“页面交换”或“分段交换”，又称为“部分交换”，这种交换方法是实现请求分页及请求分段式虚拟存储器的基础。与覆盖技术

41、相比，交换不要求程序员给出程序段之间的覆盖结构。而且，交换主要是在进程或作业之间进行，而覆盖则主要在同一个作业或进程内部进行。另外，覆盖技术只能覆盖那些与覆盖程序段无关的程序段。,5.3 内存不足时的管理,2.交换的实现 为了实现进程交换，系统必须能实现下述三方面功能：(1)交换空间的管理。(2)进程的换出。(3)进程的换入。交换技术大多用在小型机或微机系统中，这些系统大部分采用固定分区或动态分区方式管理内存。,5.4 分页存储管理,离散分配方式允许将一个进程直接分散地装入到许多不相邻接的分区中。它既不需要移动内存中的原有信息，又解决了外部碎片问题，从而提高内存利用率。如果离散分配的基本单位是

42、页，则称为分页存储管理方式；如果离散分配的基本单位是段，则称为分段存储管理方式。本节讨论的分页存储管理要求把每个作业全部装入内存后方能运行，不具备页面交换功能，因此不具有支持实现虚拟存储器的功能。,5.4.1 分页存储管理的基本原理,1.页面和物理块 在分页存储管理方式中，为了将一个进程分散地装入到许多不相邻接的内存分区中，系统会把用户程序的地址空间划分成若干个大小相等的区域，每个区域称作一个页面或页。每个页都有一个编号，叫做页号。页号一般从0开始，如0，1，2，等。类似地，也把内存空间划分成若干和页大小相同的物理块，这些物理块叫“帧”(frame)或内存块。同样，每个物理块也有一个编号，块号

43、也是从0开始依次顺序排列。在分页系统中，为进程分配内存时，以块为单位将进程中的若干页分别装入多个可以不相邻接的块中。由于进程的最后一页经常装不满一块，而形成不可利用的碎片，称为“页内碎片”。,5.4.1 分页存储管理的基本原理,2.地址结构 在分页系统中，每个逻辑地址分为两个部分：页号(p)和页内偏移(或称页内地址)(w)。通常，如果逻辑地址空间为2m，页的大小为2n单元，那么逻辑地址的高mn位表示页号，而低n位表示页内偏移。地址长度为32位，其中09位为页内地址，每页的大小为1KB(210)，1031位为页号，地址空间最多可有4M(222)页。,5.4.1 分页存储管理的基本原理,2.地址结

44、构如果给定的逻辑地址是A，页面大小为L，则页号p和页内地址w可以按下式计算得到：p=INTA/L，w=A MOD L其中，INT是向下整除的函数，MOD是取余函数。例如，假设系统的页面大小为1KB，A=5960，则p=INT(5960/1024)=5，w=5960MOD 1024=840。,5.4.1 分页存储管理的基本原理,3.页表系统为每个进程建立一张页面映射表，简称页表，每个页在页表中占一个页表项，其中记录了该页在内存中对应的物理块号。进程执行时，首先按照逻辑地址中的页号查找页表中对应的项，找到该页在内存中的物理块号。页表的作用就是实现页号到物理块号的地址映射。,5.4.1 分页存储管理

45、的基本原理,4.碎片问题 采用分页技术不会产生外部碎片，每一物理块都可以分配给进程页面。不过，分页技术可能产生页内碎片。由于分页系统的内存分配是以物理块为单位进行的，如果进程所要求的内存不是页的整数倍，那么最后一个物理块就可能用不完，从而导致页内碎片。例如，如果页的大小为2048B，一个大小为56596B的进程需要27个页和1300B。为了使该进程能够执行，系统需要给该进程分配28个物理块，这样就会产生2048-1300=748 B的页内碎片。在最坏的情况下，一个需要n页再加上1 B的进程，就需要给它分配n+1个物理块。这样就几乎产生了一个物理块的页内碎片。,5.4.2 地址映射,系统通过地址

46、变换机构来实现用户地址空间中的逻辑地址到内存空间中的物理地址的映射。由于页内地址和物理地址是一一对应的，因此，地址变换机构的任务实际上只是将逻辑地址中的页号转换为内存中的物理块号。在分页系统中，利用页表来实现用户程序地址和内存物理地址的转换。,5.4.2 地址映射,1.基本的地址映射,5.4.2 地址映射,2.具有快表的地址映射 在地址变换机构中增设一个具有并行查询能力的特殊高速缓冲寄存器，又称为“高速联想存储器”，或称为“快表”。在快表中，保存那些当前执行进程中最常访问的页表项。,5.4.3 页表的结构,现代计算机系统都支持非常大的逻辑地址空间(232 264)。在这种情况下，页表会变得非常

47、大，要占用相当大的内存空间。可以采用下述两个方法来解决这一问题：(1)采用离散分配方式来解决难以找到一块连续大内存空间的问题；(2)只将当前需要的部分页表项调入内存，其余页表项保存在磁盘，需要时再调入。,5.4.3 页表的结构,1.两级页表 p1是用来访问外层页表的索引，外层页表的每一项是相应内层页表的起始地址，而p2则是外层页表的页偏移，是访问内层页表的索引，其中的表项是相应页面在内存中的物理块号。利用外层页号p1检索外层页表，从中找到相应的内层页表的基址p2，再利用p2作为该内层页表的索引，找到该页面在内存的块号，用该块号和页内地址d拼接形成访问该块内存的物理地址。,5.4.3 页表的结构

48、,1.两级页表,两级页表结构,两级页表结构的地址转换,5.4.3 页表的结构,2.多级页表 对于32位机器，采用两级页表结构是合适的。对于64位的逻辑地址，两级分页方案就不再适合了。因此必须采用多级页表，将外层页表再进行分页。对于64位计算机，它支持的物理存储空间规模达264B(=1 844 744 TB)，如此大的存储空间规模，即使是采用三级页表结构也难以解决寻找连续的大内存空间保存页表的问题。而在当前的实际应用中，如此大的存储空间也无此需要。因此，近两年推出的64位操作系统中，把可直接寻址的存储器空间减少为45位长度(即245)左右，这样就可以采用三级页表结构来实现分页存储管理。,5.4.

49、4 页面的共享,分页技术实现了内存离散分配，解决了外部碎片问题，提高了内存的利用率。分页技术的另一个优点是可以在一定程度上实现程序代码的共享。,5.5 分段存储管理,固定分区分配、动态分区分配以及分页存储管理方式，主要目的都是为了解决内存碎片问题，提高内存利用率。但是，这些存储管理方式很少考虑用户在编程和使用上的需要，譬如：方便用户编程、更好地实现信息共享和保护。为了解决这一问题，现代操作系统引入了分段存储技术。,5.5.1 分段存储管理方式的引入,1.方便编程 2.信息共享 3.信息保护,5.5.2 分段存储管理的基本原理,1.分段 在分段存储管理方式中，程序按内容或过程(函数)关系划分为若

50、干个段，每个段定义一组逻辑信息，都有自己的名字。在段式管理方式下，进程的地址空间设计为二维结构，包括段号s与段内地址w。在页式管理中，被划分的页号按照顺序编号递增排列，属于一维空间，而段式管理中的段号与段号之间没有顺序关系。另外，段的划分也不像页的划分那样具有相同的页长，段的长度是不固定的。每个段定义一组逻辑上完整的程序或数据。每个段是一个首地址为零、连续的一维线性空间。根据需要，段长可以动态增长。对段式地址空间的访问包括两个部分：段名和段内地址。,5.5.2 分段存储管理的基本原理,2.段表 在系统中为每个进程建立一张段映射表，简称段表。每个段在表中占有一个表项，其中记录该段在内存中的起始地