操作系统,第3章存储管理

1、第3章 存储管理 v 本章学习目标 v3.1 存储管理概述 v3.2 连续分配存储管理方式 v3.3 页式存储器管理 v3.4 段式存储管理v3.5 段页式存储管理v3.6 虚拟存储器v3.7 请求分页存储管理v3.8 请求分段存储管理本章目标本章目标 v理解与掌握存储管理的功能。v理解与掌握单用户连续、固定分区和可变分区存储管理方式。v理解与掌握页式存储管理方式。v了解段式、段页式存储管理方式。v理解请求页式虚拟存储管理方式。本章学习目标 v本章首先介绍了存储管理的研究对象和目的，明确了存储管理的基本功能和有关的基本概念；然后从实存和虚存两个角度，分别介绍了常用的几种存储管理方案；最后对各种

2、存储管理方案存在的问题，主要是碎片和抖动问题进行了总结。 本章的主要内容如下：v(1)存储管理的目的和四大基本功能。 v(2)实存管理中讲述了固定分区存储管理、可变式分区存储管理、纯分页存储管理三种存储管理方案的实现原理v(3)虚存管理以请求式分页存储管理为重点 v(4)总结各种存储管理方案中存在的碎片和抖动问题及解决方法3.1 存储管理的概述 v3.1.1 存储器的层次结构 v3.1.2 存储管理的功能v3.1.3 地址重定位 多级存储器体系示意图多级存储器体系示意图3.1.1 存储器的层次结构内存空间的分配和保护。内存储器中允许同时容纳各种软件和多个用户程序时，必须解决内存空间如何分配以及

3、各存储区域内的信息如何保护等问题。内存空间的重定位。配合硬件做好地址转换工作，把一组逻辑地址空间转换成绝对地址空间，以保证处理器的正确执行。内存空间的共享。在多道程序设计的系统中，同时进入内存储器执行的作业可能要调用共同的程序。内存空间的扩充。提供虚拟存储器，使用户编制程序时不必考虑内存储器的实际容量，使计算机系统似乎有一个比实际内存储器容量大的多的内存空间。 3.1.2 存储器的功能1程序的装入v（1）绝对装入方式。也称直接分配方式。这种方式指程序在编写程序或编译程序对源程序编译时采用实际存储地址。采用这种方式，必须事先划定作业的可用空间，因此这种绝对装入方式的存储分配，存储空间的利用率不高

4、，对用户使用也不方便。v（2）可重定位方式。也称静态分配方式。在将作业装入内存时才确定它们在内存中的位置。也就是说，存储空间的分配是在作业装入内存时实现的。采用这种装入方式，在一个作业装入时必须分配其要求的全部存储量；如果没有足够的存储空间，就不能装入该作业。此外，作业一旦进入内存后，在整个运行过程中不能在内存中移动，也不能再申请内存空间。这种装入方式实际上就是静态重定位静态重定位。v（3）动态运行时装入方式。 3.1.3 地址重定位2地址重定位基本概念地址重定位基本概念（1）逻辑地址）逻辑地址 一个应用程序经编译后，通常会形成若干个目标程序，这些目标程序再经过连接而形成可装入程序。这些程序的

5、地址都从“0”开始的，程序中的其他地址都是相对于起始地址计算；由这些地址所形成的地址范围称为地址空间，其中的地址称为逻辑地址逻辑地址或相对地址。（2）绝对地址）绝对地址 当用户把作业交给计算机执行时，存储管理就为其分配一个合适的内存空间，这个分配到的内存空间可能是从“A”单元开始的一个连续地址空间，称为“绝对地址”空间，其中的地址称为物理地址或绝对地址。（3）地址重定位）地址重定位 由于逻辑地址经常与分到的内存空间的绝对地址不一致，而且对于每个逻辑地址在内存储器中也没有一个固定的绝对地址与之对应。因此，不能根据逻辑地址直接到内存储器中去存取信息。由于处理器执行指令是按绝对地址进行的，为了保证作

6、业的正确执行，必须根据分配到的内存区域对它的指令和数据进行重定位，即把逻辑地址转换成绝对地址。把逻辑地址转换成绝对地址的工作称为地址转地址转换换或地址重定位地址重定位或地址映射地址映射。 3静态、动态重定位静态、动态重定位 重定位的方式可以有静态定位静态定位和动态定位动态定位两种。（1）静态重定位）静态重定位 静态重定位在装入一个作业时，把作业中的指令地址和数据地址全部转换成绝对地址。由于地址转换工作是在作业执行前集中一次完成的，所以在作业执行过程中就无需进行地址转换工作。这种定位方式称静态重定位静态重定位。 （2）动态重定位）动态重定位 动态重定位是在程序执行过程中，每当访问指令或数据时，将

7、要访问的程序或数据的逻辑地址转换成物理地址。由于重定位过程是在程序执行期间随着指令的执行逐步完成的，故称为动态重定位动态重定位。 150011001250作业地址空间存储地址空间0LOAD 1,25031002505001000LOAD 1,12503图3.3 动态重定位过程重定位寄存器具+逻辑地址作业地址空间存储地址空间0LOAD 1,25031002505001000LOAD 1,125031100125015002501000（b）采用动态重定位时内存空间及地址重定位示意图 （a）采用静态重定位后的内存空间 静态地址重定位和动态地址重定位示意图静态地址重定位和动态地址重定位示意图3.2

8、连续分配存储管理方式 v3.2.1 单用户连续存储管理v3.2.2 固定分区存储管理v3.2.3 可变分区存储管理1. 单用户连续存储管理单用户连续存储管理 单用户连续存储管理方式是一种最简单的存储管理方式，它只能用于单用户、单任务的操作系统中。在这种管理方式下操作系统占了一部分内存空间，其余剩下的内存空间都分配给一个作业使用，即在任何时刻内存储器中最多只有一个作业。 3.2.1 单用户连续存储管理单用户连续存储管理示意图用户区作业队列cb0aOS区用户作业空闲区CPU界限寄存器a作业1 作业2覆盖技术示意图cb0aOS区覆盖区1驻留区用户区D可覆盖的段覆盖区2主程序段DCAB2. 覆盖（覆盖

9、（Overly）技术）技术 所谓覆盖覆盖就是指一个作业中的若干程序段和数据段共享内存的某个区域。其实现的方法是将一个大的作业划分成一系列的覆盖（程序段），每个覆盖是一个相对独立的程序单位，执行时并不要求同时装入内存的覆盖组成一组，并称其为覆盖段，将一个覆盖段分配到同一存储区域。 3.交换（交换（Swapping）技术）技术 交换（对换）技术就是把暂时不用的某个程序或数据部分（或全部）从内存移到外存中去， 以便腾出必要的内存空间；或把指定的程序或数据从外存读到相应的内存中，并将控制权转给它，让其在系统上运行的一种内存扩充技术 。 内存外存交换交换示意图 固定分区存储管理是在作业装入前，内存用户区

10、被划分成若干个大小不等连续区域，每一个连续区称为一个分区，每个分区可以存放一个作业。一旦划分好后，内存储器中分区的个数就固定了。各个分区的大小可以相同，也可以不同，每个分区的大小固定不变，因此，也把固定分区称为静态分区。各分区的使用情况，用“分区分配表”来说明 。3.2.2 固定分区存储管理固定分区存储管理示意图e作业队列b0aOS区CPU上限寄存器d作业1 作业2c3下限寄存器正运行作业分区分区1分区2分区3空闲区d分区号起始地址长度占用标志1aL102bL203cL31分区分配表分区分配表 下限地址绝对地址块号 页内地址p页表始址 页表长度bmnbd物理地址越界中断页号 页内地址逻辑地址p

11、dCPU+3.3.3 快表具有快表地址变换机构示意图快表页号 块号b页表块号 页内地址p页表始址 页表长度页表寄存器bmnbd物理地址越界中断页号 页内地址逻辑地址pd输入寄存器内存 分页式存储管理把内存储器的可分配区域按页面大小分成若干块，分配内存空间按块为单位。可用一张内存分配表来记录已分配的块和尚未分配的块以及当前剩余的空闲块数。由于块的大小是固定的，所以可以用一张“位示图”来构成内存分配表。 3.3.4 分页式存储空间的分配与回收0310/10/1 0/1 0/1 0/10/1 0/1 0/1 0/1 0/1剩余块数0/10/10/10/10/10/1分页存储管理内存分配表 分页存储管

12、理能方便地实现多个作业共享程序和数据。 页的共享可节省内存空间，但实现信息共享必须解决共享信息的保护问题。通常的办法是在页表中增加一些标志，指出该页的信息可读/写、只读、只可执行等等。3.3.5 页的共享与保护第100块第200块内存作业1页表页号标志块号0只执行 1001读/写2002读/写3003只读30作业2页表页号标志块号0只执行 1001读/写2322读/写4243读/写5684只读200共享程序共享数据 目前，大多数计算机系统都支持非常大的逻辑地址空间。在这样的环境下，页表就变得非常大，要占用很大的内存空间。而且页表还要求存放在连续的存储空间中，显然这是不现实的，可以采用以下两种途

13、径解决这一问题。 （1）对页表所需的内存空间，采用离散的分配方式； （2）只将当前需要的部分页表项调入内存，其余的页表项当需要时再调入。 3.3.6 两级和多级页表v两级页表：两级页表：对于支持32位逻辑地址空间的计算机系统可以采用两级页表。就是将页表再分页，形成两级页表，。比如当一个32位系统的页大小为4KB，那么逻辑地址被分为20bit的页号和12bit页内地址。如果采用两级页表结构，对页表进行再分页，使每个页中包含1024个页表项，最多允许有1024个页表分页，或者说，外层页表中的外层页内地址p2为10位，外层页号p1也为10位。v多级页表多级页表：两级页表结构适合32位的机器，但是对于

14、64位机器，两级页表结构就不再合适了。 外层页号外层页内地址页内地址31 2221 1211 0p1p2d两级页表地址结构3.4 段式存储管理 v3.4.1 引入的原因v3.4.2 段式存储管理基本思想v3.4.3 地址变换机构与存储保护3.4.1 引入的原因 在分页存储管理中，用户程序的地址空间是从0开始编址的单一连续的逻辑地址。虽然操作系统可把程序划分成若干个页面，但是页面与源程序无逻辑关系，也就难以实现对源程序以模块为单位进行分配、共享和保护。 在段式存储管理中，段是一组逻辑信息（独立信息段）的集合。在单纯的分页存储管理中，这些信息都混在一起，并统一编址，显然，分页系统并不是编程人员愿意

15、接受的信息组织方式。因此按照信息原有的方式组织数据是必要的，也是支持高级语言必要的。 3.4.2 段式存储管理基本思想 在编制程序时每一段都可独立编制，每一段的逻辑地址都是从“0”开始编址，每段的长度不一定相同，形成了段内地址是连续段内地址是连续的，而段与段之间的地址是不连续段与段之间的地址是不连续的。 当作业被装入内存储器时，以段为单位为作业的每一段分配一个连续的内存区域 ，各段之间也可不必连续 ，分配方法同可变分区方式 。 装入作业时，用一张段表记录该作业每个分段在内存中起始地址和长度 。31 16 15 0段号S段内地址d段式存储管理地址结构段式存储管理原理图作业空间040K120K16

16、0K200K210段长 基址8KB10KB5KB18KB120K160K200K40KS0段号3S1S2S3内存空间S0 18KBS2 10KBS3 5KBS1 8KB段表3.4.3 地址变换机构与存储保护1.地址变换机构地址变换机构段式地址变换过程0段号 段长 基址pp-1段表内存段表始址 段表长度段表寄存器m fsn物理地址越界中断段号 段内地址逻辑地址pdCPU2.共享与保护共享与保护 段是信息的逻辑单位，段式存储管理方式可以方便地实现内存的信息共享，并进行有效的内存保护。 段式存储管理的保护主要有地址越界保护和存取方式控制保护。 段的共享200K400K100K200K内存作业1段表段

17、长标志始址200K 只执行 100K100K 读/写 200K300K 读/写 300K400K只读50K作业2段表段长标志始址200K 只执行 100K200K 读/写 232K320K 读/写 424K100K 读/写 568K400K只读200K共享程序共享数据始址 段长v（1）页是信息的物理单位，分页是由于系统管理的需要。段是信息的逻辑单位，它含有意义相对完整的信息（程序段或数据段等）。分段的目的是为了更好的满足用户的需要；v（2）页的大小是固定并且由系统决定，段的长度不定，取决于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分；v（3）页式在存储管理中的逻辑

18、地址空间是一维的，段的逻辑地址空间是二维的；v（4）页式存储管理的优点是在管理内存空间上，而段式存储管理的优点是在管理逻辑地址空间上。3.段式与页式存储的区别段式与页式存储的区别 3.5 段页式存储管理 v3.5.1 段页式存储管理原理v3.5.2 地址变换3.5.1 段页式存储管理原理段页式存储管理原理 段页式存储管理基本原理是分段和分页相结合。内存采用分页存储管理方式，将内存划分成大小相等的物理块，用户程序的逻辑地址空间采用分段方式，按程序的逻辑关系把地址空间分成若干个逻辑段，每一段不是按单一的连续整体存放到内存中，而是把每段再分成若干个页面，每一段不必占据连续的内存空间，可把它按页存放在

19、不连续的内存块中，每一段中的所有页必须在其所在每一段中的所有页必须在其所在的段内，即段内的页是离散分配的的段内，即段内的页是离散分配的。 段号s段内地址d段页式存储管理逻辑地址格式段内页号p内存段表段表寄存器段表长度 段表始址段号 状态 页表长度 页表始址0123页号 状态0123块号页号 状态0123块号操作系统段页式存储管理的地址映射 3.5.2 地址变换地址变换图3.32 段页式地址变换过程块号 块内地址p0121ss-1页表内存段表始址 段表长度段表寄存器mn物理地址越界中断段号 页号 页内地址逻辑地址CPUspd 页表长度页表始址3.6 虚拟存储器 v3.6.1 局部性原理v3.6.

20、2 虚拟存储器的定义和特征v3.6.3 虚拟存储器的实现方法 早在1968年P.Denning就指出过，程序在执行时将呈现出局部性规律，即在一较短的时间内，程序的执行仅限于某个部分；相应的它所访问的存储空间也局限于某个区域。 局部性表现如下。 （1）时间局部性。如果程序中的某条指令一旦执行，则不久以后该指令可能再次被执行；如果某个存储单元被访问，则不久以后该存储单元可能再次被访问，产生时间局部性的典型原因是在程序中存在大量的循环操作。 （2）空间局部性。一旦程序访问了某个存储单元。则不久以后，其附近的存储单元也将被访问，即是程序在一段时间内访问的地址可能集中在一定范围内，引起空间局部性的典型原

21、因是程序的顺序执行。3.6.1 局部性原理局部性原理3.6.2 虚拟存储器的定义和特征虚拟存储器的定义和特征1.虚拟存储器定义虚拟存储器定义 ：就是指把用户的作业的一部分装入内存便可运行作业的存储系统。其实际上用户看到的大容量只是一种感觉，是虚的，故而称为虚拟存储器。2. 虚拟存储器特征虚拟存储器特征（1）离散性。指在内存分配时采用离散分配方式。（2）多次性。指一个作业运行时分成多次装入内存。（3）对换性。指作业运行过程中在内存和外存的对换区之间换进换出。（4）虚拟性。指能够从逻辑上扩充内存容量，使用户感觉到的存储器容量远远大于实际的内存容量。 3.6.3 虚拟存储器的实现方法虚拟存储器的实现

22、方法（1）请求页式存储管理 请求页式存储管理是在页式存储管理基础上增加了请求调页功能、页面置换功能所形成的页式虚拟存储分配系统。程序启动运行时装入部分用户程序页和数据页，在以后的运行过程中，访问到其他逻辑页时，再陆续将所需的页调入内存中。请求调页和置换时，需要页表机构、缺页中断机构、地址变换机构等硬件支持。（2）请求段式存储管理 请求段式存储管理是在段式存储管理方式的基础上增加了请求调段和分段置换功能而形成的段式虚拟存储管理，只需装入部分程序段和数据段即可启动运行，以后出现缺段时再动态调入。实现请求分段同样需要分段的段表机制、缺段中断机构、地址变换机构等软硬件支持。3.7 请求分页存储管理v3

23、.7.1 页表机制v3.7.2 缺页中断v3.7.3 地址变换v3.7.4 页面分配v3.7.5 页面淘汰算法3.7.1 页表机制页表机制 在请求分页存储管理的方式中，页表仍然是重要的数据结构，其主要作用是实现用户逻辑地址空间中逻辑地址到内存空间中的物理地址的变换。在虚拟存储器中，由于应用程序并没有完全调入内存，所以页表结构根据虚拟存储器的需要增加了若干项，如图所示。其中：（1）状态位P用于该页是否已调入内存，供程序访问时参考；（2）访问字段A用于记录本页在一段时间内被访问的次数，或最近多长时间未被访问，供转换算法选择换出页面时参考；（3）修改位M表示该页在调入内存后是否被修改过。（4）外存地

24、址用于指出该页在外存上的地址，通常是物理块（簇）号，供调入该页时使用。请求分页虚拟存储管理方式的页表结构页号块号状态位P 访问字段A 修改位M外存地址3.7.2 缺页中断缺页中断 在请求分页存储管理中，当所要访问的页不在内存时，便要产生缺页中断，请求操作系统将所缺页调入内存。缺页中断与一般中断不同，区别如下。 （1）缺页中断是在执行一条指令期间时产生的中断，并立即转去处理，而一般中断则是在一条指令执行完毕后，当发现有中断请求时才去响应和处理； （2）缺页中断处理完成后，仍返回到原指令去重新执行，因为那条指令并未执行。而一般中断则是返回到下一条指令去执行，因为上一条指令已经执行完毕了。3.7.3

25、 地址变换地址变换 请求分页系统中进行地址变换时，首先要检测该页面是否在内存，如果该页面在内存中，则地址变换方式与页式存储管理方式相同；如果该页不在内存中，则进行缺页中断处理。进行缺页中断处理时首先判断内存空间是否够用，如果内存没有可用空间，必须进行置换以腾出可用空间。越界中断NNY开始（程序访问第一页）页号页表长度？访问页面Y页是否在内存？调整页表形成物理地址地址变换结束从外存中找到缺页缺页中断处理NY内存满否？淘汰一个页面Y该页是否修改过？N将该页写回内存将缺页调入内存调整页表请求分页存储管理的地址变换过程3.7.4 页面分配页面分配 在为进程分配物理块时，首先考虑的是：保证进程能正常运行

26、所需要的最少物理块数。若系统为某进程分配的物理块数小于此值时进程将无法运行。其次，要考虑的问题是页面的分配和置换策略。在请求分页存储管理中可采用固定和可变两种分配策略。在进程置换时，也可采用全局置换和局部置换两种策略。组合成如下三种策略。 （1）固定分配局部置换策略 （2）可变分配全局置换策略 （3）可变分配局部置换策略3.7.5 页面淘汰算法页面淘汰算法 发生缺页时，就要从外存上把所需要的页面调入到内存。如果当时内存中有空闲块，那么页面的调入问题就解决了；如果当时内存中已经没有空闲块可供分配使用，那么就必须在内存中选择一页，然后把它调出内存，以便为即将调入的页面让出块空间。这就是所谓的“页面

27、淘汰”问题。选择淘汰对象有很多种策略可以采用，比如： 1.先进先出（FIFO）页面淘汰算法 (first in firstout,FIFO) 2. 最近最久未使用页面淘汰算法（Least Recently Used，LRU） 3. 最近最少用页面淘汰算法（Least Frequently Used，LFU） 4. 最佳页面淘汰算法（Optimal，OPT）1最优算法（最优算法（OPT算法）算法）v最理想的页面置换算法是：从内存中移出以后不再使用的页面；如无这样的页面，则选择以后最长时间内不需要访问的页。这就是最优算法的思想。v这种算法本身不是一种实际的方法，因为页面访问的顺序是很难预知的。但是

28、，可把它作为一种评价标准，比较其他实用方法的优劣，所以，最优算法只具有理论上的意义。2先进先出算法（先进先出算法（FIFO算法）算法）v这种算法的基本思想是：总是先淘汰那些驻留在内存时间最长的页面，即先进入内存的页面先被置换掉。理由是：最先进入内存的页面不再被访问的可能性最大。 3最久未使用页面置换算法（最久未使用页面置换算法（LRU算法）算法）v这种算法的基本思想是，如果某一页被访问了，那么它很可能马上又被访问；反之，如果某一页很长时间没有被访问，那么最近也不太可能会被访问。这种算法考虑了程序设计的局部性原理。其实质是，当需要置换一页时，选择在最近一段时间最久未使用的页面予以淘汰。v实现这种

29、算法可通过周期性地对“引用位”进行检查，并利用它来记录一页面自上次被访问以来所经历的时间t，淘汰时选择t最大的页面。 4LRU近似算法近似算法v这种算法，只要在存储分块表（或页表）中设一个“引用位”，当存储分块表中的某一页被访问时，该位由硬件自动置1，并由页面管理软件周期性把所有引用位置0。这样，在一个时间周期T内，某些被访问过的页面其引用位为1，而未被访问过的页面其引用位为0。因此，可根据引用位的状态来判别各页面最近的使用情况。当需要置换一页面时，选择其引用位为0的页，如图4.21所示的算法 。图4.22是这种近似算法的一个例子。 【例题】在请求页式存储管理系统中，设一个作业访问页面的序列为

30、4，3，2，1，4，3，5，4，3，2，1，5，设分配给该作业的存储空间有4块，且最初未装入任何页。试计算FIFO和LRU算法的缺页率。 解： 采用FIFO页面淘汰算法，该作业运行时缺页情况如表所示时刻123456789101112访问页面432143543215内存页面432111543215432221543214333215432444321543缺页+从表中可以看出，缺页中断次数为10；缺页率为f=10/12=83% 采用LRU页面淘汰算法，该作业运行时缺页情况如表所示 时刻123456789101112访问页面432143543215内存页面432143543215432143543214321435432432111543缺页+从表中可以看出，缺页中断次数为8；缺页率为f=8/12=67% v3.8.1请求分段存储管理基本思想 v3.8.2 缺段中断 v3.8.