第第4 4章章 存储管理存储管理 第第4章章 存储管理存储管理 4.1 概述概述 4.2 分区存储管理方案分区存储管理方案 4.3 页式存储管理页式存储管理 4.4 段式存储管理段式存储管理 4.5 段页式存储管理段页式存储管理 4.6 交换技术与覆盖技术交换技术与覆盖技术 4.7 虚拟存储虚拟存储 4.8 高速缓冲存储器高速缓冲存储器 4.9 内存管理实例分析内存管理实例分析习题习题 第第4 4章章 存储管理存储管理 4.1 概概 述述存储器是计算机系统中的重要组成部分，随着计算机技术的飞速发展和内存价格的降低，现代计算机中的内存也在不断增加，已经达到GB的范围。第第4 4章章 存储管理存储管理 4.1.1 存储体系存储器的功能是保存指令和数据，它的发展方向是高速、大容量和小体积，诸如内存在访问速度方面的发展有DRAM、SDRAM、SRAM等技术；而磁盘技术的发展方向主要在大容量方面，比如接口标准、存储密度等。第第4 4章章 存储管理存储管理 存储组织的功能是在存储技术和CPU寻址技术许可的范围内组织合理的存储结构，其依据是访问速度的匹配关系、容量要求和价格。常见的存储结构有两种：“寄存器内存外存”结构和“寄存器快速缓存内存外存”结构。图4.1所示的是“寄存器快速缓存内存外存”结构。图4.1存储层次结构第第4 4章章 存储管理存储管理 从源程序到程序执行从源程序到程序执行编译：编译程序由编译程序（Compiler）将用户源代码编译成若干个目标模块。链接：链接程序由链接程序（Linker）将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成装入模块。装入：装入程序由装入程序（Loader）将装入模块复制到内存中。库汇编编译主子1子2目标模块链接程序装入模块库主子1子2装入程序内存库主子1子2第第4 4章章 存储管理存储管理 地址空间的概念地址空间的概念物理（绝对）地址程序执行每个内存单元的固定顺序地址（编号）。逻辑（相对）地址装入（汇编编译）被链接装配（或汇编、编译）后的目标模块所限定的地址的集合；相对于某个基准量（通常为：0）的编址。物理地址内存000000000100002.0100001FFF主子1子2主子1子2逻辑地址装入模块000.FFF主子1子2相对地址源程序/单个目标模块0005FF0005FF0003FF第第4 4章章 存储管理存储管理 4.1.2 地址重定位可执行文件的建立过程是：源程序编译目标模块(多个目标模块或程序库)链接可执行文件。当程序执行时由操作系统装入内存而成为进程。对程序员来说，数据的存放地址是由符号决定的，故称为符号名地址，或者称为名地址。第第4 4章章 存储管理存储管理 当程序被装入内存时，程序的逻辑地址被转换成内存的物理地址，称为地址重定位地址重定位。在可执行文件装入时需要解决可执行文件中地址(指令和数据)和内存地址的对应问题。这是由操作系统中的装入程序Loader来完成的，如图4.2所示。图4.2地址重定位第第4 4章章 存储管理存储管理 1绝对装入(absolute loading)在可执行文件中记录内存地址，装入时直接定位于上述内存地址的方式称为绝对装入(或者称为固定地址再定位)。在这种方式下，程序的地址再定位是在执行之前被确定的，也就是在编译、链接时直接制定程序在执行时访问的实际存储器地址。这样，程序的地址空间和内存地址空间是一一对应的。单片机或者单用户系统常采用这种方式。固定地址再定位的优点是装入过程简单；缺点是过于依赖于硬件结构，不适合多道程序系统。第第4 4章章 存储管理存储管理 2可重定位装入(relocatable loading)可重定位装入方式是指在可执行文件中，列出各个需要重定位的地址单元和相对地址值，装入时再根据所定位的内存地址去修改每个重定位地址项，添加相应的偏移量。一个有相对地址空间的程序装入到物理地址空间时，由于两个空间不一致，就需要进行地址变换，或称地地址址映映射，即地址的再定位。射，即地址的再定位。地址再定位有两种方式：静态再定位和动态再定位。第第4 4章章 存储管理存储管理 1)静态再定位静态再定位是指当程序执行时，由由装装入入程程序序运运行行重重定定位位程程序序，根据作业在内存重分配的起始地址，将可执行的目标代码装入到指定内存中。所谓静态，是指地址定位完成后，在程序的执行期间将不会再发生变化。静态再定位是在程序执行之前进行地址再定位的，这一工作通常是由装配程序完成的。静态重定位示意图第第4 4章章 存储管理存储管理 静态地址再定位的优优点点是是：无需硬件地址变化机构支持，容易实现；无需硬件支持，它只要求程序本身是可再定位的；它只对那些要修改的地址部分做出某种标识，再由专门设计的程序来完成。在早期的操作系统中大多数都采用这种方法。静态地址再定位的缺点是缺点是：必须给作业分配一个连续的存储区域，该存储区不能分布在内存的不同区域；在作业的执行期间不能扩充存储空间，也不能在内存中移动，因而不能重新分配内存，不利于内存的有效利用；多个用户很难共享内存中的同一程序，如若共享同一程序，则各用户必须使用自己的副本。第第4 4章章 存储管理存储管理 2)动态再定位动态地址再定位是在程序执行期间，在在每每次次存存储储访访问问之之前前进进行行的的。程序在装入内存时，并不修改程序的逻辑地址值，而是在访问物理内存之前，再实时地将逻辑地址转换成物理地址。在这种情况下，其实现机制要依赖硬件地址变换机构，即通过基地址寄存器BR、变址寄存器VR计算出指令的有效地址，再利用硬件机构实现地址变换，如图4.3所示。第第4 4章章 存储管理存储管理 图4.3动态地址再定位的原理第第4 4章章 存储管理存储管理 从图4.3中可以看出：当程序开始执行时，系统将程序在内存的起始地址送入BR中。执行指令时，系统将逻辑地址与BR中的起始地址相加，从而得到物理地址。动态地址再定位的优优点点是是：程序在执行期间可以换入和换出内存，这样可以缓解内存紧张的矛盾；可以把内存中的碎片集中起来，以充分利用空间；不必给程序分配连续的内存空间，可以较好地利用较小的内存块；若干用户可以共享同一程序。动态地址再定位的缺缺点点：需要附加的硬件支持，而且实现存储管理的软件算法比较复杂。第第4 4章章 存储管理存储管理 3动态运行期装入动态运行期装入(dynamicrun-timeloading)是指在可执行文件中记录虚拟内存地址，在装入和执行时通过硬件地址变换机构完成虚拟地址到实际内存地址的变换。动态运行期装入的优点是：操作系统可以将一个程序分散存放于不连续的内存空间，可以通过移动程序来实现共享；能够支持程序执行中产生的地址引用，如指针变量(而不仅是生成可执行文件时的地址引用)。动态运行期装入的缺点是：需要硬件支持(通常是CPU)，操作系统的实现比较复杂。第第4 4章章 存储管理存储管理 4.1.3 链接 1链接方法常见的链接方法有静态链接和动态链接两种。1)静态链接静态链接(staticlinking)是在生成可执行文件时进行的，即在目标模块中记录被调用模块的名字符号地址(symbolicaddress)，在可执行文件中将该名字改写为指令直接使用的数字地址，如图4.4所示。第第4 4章章 存储管理存储管理 图4.4静态链接第第4 4章章 存储管理存储管理 2)动态链接动态链接(dynamic-linking)是在运行可执行文件时进行的,亦即，执行过程中，当发现一个被调用模块未装入内存时，立即取找到该模块，并链接到调用者模块上。通常被链接的共享代码称为动态链接库(DynamicLinkLibrary，DLL)或共享库(sharedlibrary)。第第4 4章章 存储管理存储管理 动态链接的优点是：(1)共享：多个进程可以共用一个DLL，比较节省内存，从而可以减少文件的交换。(2)部分装入：一个进程可以将多种操作分散在不同的DLL中实现，而只将当前操作的DLL装入内存。(3)便于局部代码修改：即便于代码升级和代码重用；只要函数的接口参数(输入和输出)不变，则修改函数及其DLL时，无需对可执行文件重新编译或链接。(4)便于适应运行环境：调用不同的DLL，就可以适应多种使用环境并提供不同的功能。第第4 4章章 存储管理存储管理 动态链接的缺点是：(1)增加了程序执行时的链接开销。(2)程序由多个文件组成，因此增加了管理复杂度。第第4 4章章 存储管理存储管理 4.1.5 存储管理的任务在现代操作系统中，存储管理的主要任务有以下几个方面。(1)存储分配和回收：是存储管理的主要内容，用来确定其算法和相应的数据结构。(2)地址变换(地址再定位)：可执行文件生成中的链接技术、程序加载时的重定位技术及进程运行时硬件和软件的地址变换技术和机构。第第4 4章章 存储管理存储管理 (3)存储共享和保护：将代码和数据共享，设定对地址空间的访问权限(读、写、执行)。(4)存储器扩充：它涉及存储器的逻辑组织和物理组织，有两种控制方式：如果由应用程序控制，则采用覆盖技术。如果由操作系统控制，则采用交换技术(整个进程空间范围内)或请求调入和预调入(部分进程空间)。第第4 4章章 存储管理存储管理 4.1.6 各种存储管理方案从操作系统的发展历史来看，存储管理主要有以下几个方案：(1)分区存储管理方案：是一种连续存储管理方案，但需要一次性全部装入内存。(2)段式存储管理方案：是一种不连续存储管理方案，段和段之间可以不连续，但需要一次性全部装入内存。(3)页式存储管理方案：是一种不连续存储管理方案，也需要一次性全部装入内存。第第4 4章章 存储管理存储管理 (4)段页式存储管理方案：是一种不连续存储方案，如果采用纯分页和分段思想，需要一次性全部装入内存；如果采用虚拟存储思想，则不需要一次性全部装入内存。(5)交换技术和覆盖技术：是存储扩充的两种技术，其中交换技术的优点是编写程序时不需要特殊的控制，也不会影响程序的结构。(6)虚拟存储管理方案：又分为两种，分别是虚拟页式(请求分页)存储管理和虚拟段式(请求分段)存储管理。第第4 4章章 存储管理存储管理 4.2 分区存储管理方案分区存储管理方案分区存储管理方案的数据结构是分区表或分区链表，主要功能是：(1)可以只记录空闲分区，也可以同时记录空闲和占用分区。(2)分区表中，表项数目随着内存的分配和释放而动态改变，可以规定最大表项数目。(3)分区表可以划分为两个表格：空闲分区表和分配分区表，从而减小每个表格的长度。第第4 4章章 存储管理存储管理 4.2.1 单一连续分区存储管理单一连续分区存储管理把整个内存空间的最低端和最高端作为操作系统区，中间作为用户程序区。在DOS操作系统中就采用了这种方法，如图4.7所示。第第4 4章章 存储管理存储管理 图4.7单一连续分区存储管理的分配方式第第4 4章章 存储管理存储管理 这种存储分配思想将内存分为两个区域：系统区和用户区。应用程序装入到用户区，可使用用户区全部空间。单一连续分区的优点是：简单，适用于单用户、单任务的操作系统(比如CP/M和DOS操作系统)，不需要复杂的硬件支持。单一连续分区的缺点是：一个作业运行时要占用整个内存的地址空间，即使很小的程序也是如此，对内存造成了很大的浪费，内存的利用率很低。第第4 4章章 存储管理存储管理 4.2.2 固定分区分配为了便于管理整个内存，需建立一个表格来登记和管理整个内存。在这个表中登记了每一个分区的大小，起始地址和分配状态，如表4.1和图4.8所示。当有作业装入时，系统便可以搜索这个表，找出一个大小合适的分区分配给它。当程序运行结束时，可以把它所占用的空间再释放回去。地址重定位可以采用静态地址定位或是动态地址定位的方法。第第4 4章章 存储管理存储管理 表4.1 分区状态表分区号大小起始地址分配状态120KB100K已分配240KB120K已分配3100KB160K未分配4200KB260K已分配第第4 4章章 存储管理存储管理 图4.8固定分区的内存分配情况第第4 4章章 存储管理存储管理 为了实现多道程序设计，可以按等待作业的类型设置多个等待队列，也可以把所有的等待作业设置为一个等待队列。如图4.9所示为多道程序情况下固定分区的情况，左边为多个等待队列情况下的固定分区，右边为单个等待队列情况下的固定分区。第第4 4章章 存储管理存储管理 图4.9多道程序情况下的固定分区原理第第4 4章章 存储管理存储管理 固定分区的优点是：与单一连续分配方法相比，固定分区法的内存利用率提高了；可以支持多道程序；实现简单，开销小。固定分区的缺点：必须预先能够估计作业要占用多大的内存空间，有时候这是难以做到的；区内碎片造成浪费；分区总数固定，限制了并发执行的程序数目。第第4 4章章 存储管理存储管理 4.2.3可变分区(动态分区分配) 1空闲存储区表若采用固定分区法，则作业运行时所需内存一般不会刚好等于某一个分区的大小，因此分区内部的“内零头”被白白浪费了；另一方面，固定分区的分区数在系统启动以后不能任意改变，当系统中运行的作业数大于分区数时，就不可避免地会有一些作业分配不到分区，即使所有作业所需存储空间总和小于内存总和也不行。第第4 4章章 存储管理存储管理 可变分区存储管理法并不预先将内存划分成分区，而是等到作业运行需要内存时才向系统申请，从空闲的内存区中挖一块出来，其大小等于作业所需内存的大小，这样就不会产生“内零头”。管理空闲内存区的数据结构可采用链接法和连续线性表格法。每一个空闲分区用一个map结构管理：structmapunsignedm_size;/空闲分区的长度char*m_addr;/空闲分区的起始地址；structmapcoremapN;第第4 4章章 存储管理存储管理 图4.10所示为空闲分区表的初始状态，图4.11为某一时刻空闲分区表的状态。图中，m_size是空闲分区的长度，m_addr是空闲分区的起始地址。各个空闲分区按起始地址由低到高的顺序登记在空闲存储区表中，m_size为0的表项是空白表项，它们集中在表的后部。第第4 4章章 存储管理存储管理 图4.10空闲分区表的初始状态第第4 4章章 存储管理存储管理 图4.11某一时刻空闲分区表的状态第第4 4章章 存储管理存储管理 2分区分配算法寻找某个空闲分区，其大小必须大于或等于程序的要求。若是大于要求，则将该分区分割成两个分区，其中一个分区为要求的大小并标记为“占用”，而另一个分区为余下部分并标记为“空闲”。分区的先后次序通常是从内存低端到高端。选择分区的算法有四种：最先适应算法、最佳适应算法、最差适应算法和循环最先适应算法。第第4 4章章 存储管理存储管理 1)最先适应算法(first-fit)最先适应算法是将所有的空闲分区按照地址递增的顺序排列，然后按照分区的先后次序从头开始查找，符合要求的第一个分区就是要找的分区。该算法的分配和释放的时间性能较好，较大的空闲分区可以被保留在内存高端。第第4 4章章 存储管理存储管理 (1)分配算法：当为作业分配大小为size的空间时，总是从表的低地址部分开始查找，当第一次找到大于等于申请大小的空间时，就按所需要的大小分配空间给作业，若分配后还有剩余空间，就修改原来的m_size和m_addr，以记录余下的零头；如果作业所需要的空间刚好等于该空间的大小，那么该空间的m_size就为0；然后要删除表中的这些空间，即将各个非零的表项上移。程序描述如下：第第4 4章章 存储管理存储管理 int*ffmalloc(mp,size)structmap*mp;unsignedintsize;registerintregint;registerstructmap*bp;/从mp开始，只要size不等于0，逐个地址检查for(bp=mp;bp-m_size;bp+)if(bp-m_size=size)/只要空间足够大structmapunsignedm_size;char*m_addr;；第第4 4章章 存储管理存储管理 regint = bp-m_addr ; /把老的起始地址保存到把老的起始地址保存到a bp-m_addr += size; /起始地址加起始地址加size，把此块一分为二，把此块一分为二 if ( bp-m_size -= size ) = 0 )/如果块大小相同为如果块大小相同为0 do bp+; (bp-1)-m_addr = bp-m_addr ; while ( ( bp-1 )-m_size = bp-m_size ); return(regint ) ; return(0) ;第第4 4章章 存储管理存储管理 (2)释放算法：某一个作业释放以前所分配到的内存就是将该内存区归还给操作系统，使其成为空闲区而可以被其他作业使用。回收时如果释放区与临近的空闲区相连接，要将它们合并成较大的空闲区，否则空闲区将被分割得越来越小，最终导致不能利用。另外，空闲区个数越来越多，也会使得空闲区登记表溢出。第第4 4章章 存储管理存储管理 释放算法分四种情况：仅与前面一个空闲区相连，如图4.12(a)所示。合并前空闲区和释放区以构成一块大的新空闲区，并修改空闲区表项。与前面空闲区和后面空闲区都相连，如图4.12(b)所示。将三块空闲区合并成一块空闲区。第第4 4章章 存储管理存储管理 仅仅与后空闲区相连，如图4.12(c)所示。与后空闲区合并，使后空闲区表项的m_addr为释放区的起始地址，m_size为释放区与后空闲区的长度之和。与前后空闲区都不相连，如图4.12(d)所示。在前、后空闲区表项中间插入一个新的表项，其m_addr为释放区的起始地址，m_size为释放区的长度。第第4 4章章 存储管理存储管理 图4.12释放区与前后空闲区相邻的情况第第4 4章章 存储管理存储管理 程序描述如下：mfree(unsignedsize,char*StartAddr)structmap*bp;char*addr,*taddr;unsignedTmpSize;addr=StartAddr;structmapunsignedm_size;char*m_addr;；第第4 4章章 存储管理存储管理 for(bp=coremap;bp-m_addrm_size!=0;bp+)if(bpcoremap&(bp-1)-m_size=addr)(bp-1)-m_size+=size;/连接前部空闲区if(addr+size=bp-m_addr)/再连接后部空闲区(bp-1)-m_size+=bp-m_size;while(bp-m_size)第第4 4章章 存储管理存储管理 bp+;(bp-1)-m_addr=bp-m_addr;(bp-1)-m_size=bp-m_size;elseif(addr+size=bp-m_addr&bp-m_size)/与后空闲区相连第第4 4章章 存储管理存储管理 bp-m_addr-=size;bp-m_size+=size;elseif(size)do/单独插入空闲分区表,而不与前后相连taddr=bp-m_addr;bp-m_addr=addr;addr=taddr;TmpSize=bp-m_size;第第4 4章章 存储管理存储管理 bp-m_size=size;bp+;while(size=TmpSize);第第4 4章章 存储管理存储管理 最先适应算法的优点：分配简单而且合并相邻的空闲区也比较容易，该算法的实质是尽可能利用存储区低地址的空闲区，而尽量在高地址部分保存较大的空闲区，以便一旦有分配大的空闲区的要求时，容易得到满足。在释放内存分区时，如果有相邻的空闲区就进行合并，使其成为一个较大的空闲区。第第4 4章章 存储管理存储管理 最先适应算法的缺点：由于查找总是从表首开始，前面的空闲区被分割得很小时，能满足分配要求的可能性就较小，查找次数就较多。系统中作业越多，这个问题就越来越严重。针对这个问题，对最先适应法稍加改进，就有了循环最先适应法。会产生碎片，这些碎片散布在存储器的各处，不能集中使用，因而降低了存储器的利用率。第第4 4章章 存储管理存储管理 如图4.13所示是某一个时刻J1、J2、J3、J4四个作业在内存中的分配情况、空闲区表和已分配区表，它们的长度分别是15KB、10KB、12KB、10KB。J5和J6两个新作业的长度分别为5KB和13KB，分配内存后的内存分配情况、空闲区表和已分配区表如图4.14所示。第第4 4章章 存储管理存储管理 图4.13最先适应算法分配前的状态第第4 4章章 存储管理存储管理 图4.14最先适应算法分配后的状态第第4 4章章 存储管理存储管理 2)循环最先适应算法(next-fit，下次适应算法)相对于最先适应算法，下次适应算法按分区的先后次序，从上次分配的分区开始查找，到最后分区时再回到开头，符合要求的第一个分区就是找到的分区。第第4 4章章 存储管理存储管理 循环最先适应算法分配时总是从从起起始始查查找找指指针针所所指指向向的的表表项项开开始始，第一次找到满足要求的空闲区时，就分配所需要的空闲区，然后修改表项，并调整起始查找指针，使其指向队列中被分配的后面的那块空闲区。循环最先适应法的实质是起始查找指针所指的空闲区和其后的空闲区群常为较长时间未被分割过的空闲区，它们已经合并成为大的空闲区的可能性较大，与最先适应算法相比，它在没有增加多少代价的情况下却明显地提高了分配查找的速度。循环最先适应算法的释放算法与最先适应算法的基本相同。第第4 4章章 存储管理存储管理 3)最佳适应算法(best-fit)最佳适应算法的思想是将所有的空闲分区按照其按照其容量递增的顺序排列容量递增的顺序排列，当要求分配一个空白分区时，由小到大进行查找。第第4 4章章 存储管理存储管理 最佳适应算法的空闲存储区管理表的组织方法可以采用顺序结构，也可以采用链接结构。最佳适应算法的优点：由于算法是在所有大于或者等于要求分配长度的空闲区中挑选一个最小的分区，所以分配后所剩余的空白块会最小。平均而言，只要查找一半的表格便能找到最佳适应的空白区。如果有一个空白区的容量正好满足要求，则它必被选中。第第4 4章章 存储管理存储管理 最佳适应算法的缺点：由于空闲区是按大小而不是按地址的顺序排列的，因此释放时，要在整个链表上搜索地址相邻的空闲区，合并后又要插入到合适的位置。空白区一般不可能恰好满足要求，在分配之后的剩余部分通常非常小，以致小到无法使用。其内存分配前的状态如图4.13所示，J5和J6是两个新作业，对它们分配内存后的内存分配情况、空闲区表和已分配区表如图4.15所示。第第4 4章章 存储管理存储管理 4)最坏适应算法(worst-fit)最坏适应算法的思想与最佳适应算法相反，将所有的空白分区按容量递减的顺序排列，最前面的最大的空闲分区就是找到的分区。该算法是取所有空闲区中最大的一块，把剩余的块再变成一个新小一点的空闲区。算法基本不留下小空闲分区，但较大的空闲分区不会被保留。第第4 4章章 存储管理存储管理 最坏适应算法的实现与前面的最佳适应算法类似。最坏适应算法的优点：分配的时候只需查找一次就可以成功，分配的算法很快。最坏适应算法的缺点：最后剩余的分区会越来越小，无法运行大程序。其内存分配前的状态如图4.13所示，J5和J6是两个新作业，对它们分配内存后的内存分配情况、空闲区表和已分配区表如图4.16所示。第第4 4章章 存储管理存储管理 图4.15最佳适应算法分配后的状态第第4 4章章 存储管理存储管理 图4.16最差适应算法分配后的状态第第4 4章章 存储管理存储管理 4.2.4 可再定位式分区(可重定位分区分配)可再定位分区分配即浮动分区分配，是解决碎片碎片问题问题的简单而有效的办法。其基本思想是移动所有被分配了的分区，使之成为一个连续区域，而留下一个较大的空白区。这好像在一个队列中有些人出列以后，指挥员命令队列向前(或向右)靠拢一样。这种过程我们称之为“靠拢”或“紧凑紧凑”，如图4.17所示。第第4 4章章 存储管理存储管理 图4.17可再定位分区分配的靠拢过程第第4 4章章 存储管理存储管理 为解决程序浮动问题，可使用模块装入程序，将程序的装配模块重新装入到指定位置，并从头开始启动执行。但是这种办法有两个缺点：一是要花费较多的处理机时间；二是如果该程序已经执行了一段时间，则不能再从头开始，否则将引起混乱。较好的办法是采用动态再定位技术。第第4 4章章 存储管理存储管理 4.2.5 伙伴系统（伙伴系统（Buddy System）伙伴系统提供了一个在固定大小和可变大小之间折衷的方案。内存被划分成大小为2的整次幂的单元，初始只有一个包含所有内存的单元。当要将内存分配给进程时，分配大于该进程大小的最小2的整次幂单元。例如，一个需50K内存进程要放入大小为64K的内存单元。如果没有这样的内存单元，大于该进程需求的最小可利用空间被分成原来一半大小的“伙伴”单元，继续分割其中一个伙伴单元，直到创建一个大小合适的分配单元位置。当进程释放内存时，如果互成“伙伴”关系的两个单元均被释放，这两个单元就结合成一个两倍大小的单元。图4.18说明了分配和释放内存时，是如何分割和连接分配单元的。给定大小为2n，伙伴系统维持了一个最大长度为2n的空闲数据块，每种大小的单元各有一个（假定内存大小为28，则大小为28到21的分配单元都有可能得到）。由于有一个单独的各种大小空闲块，伙伴系统分配或释放内存效率较高。然而，由于存在内部碎片和外部碎片，所以伙伴系统内存利用率不高。第第4 4章章 存储管理存储管理 图图4.18 伙伴系统伙伴系统第第4 4章章 存储管理存储管理 4.2.6 多重分区多重分区可变分区虽然解决了多道程序运行的情况，但是总是有碎片的问题，而且一个程序总是一定要放在一个分区中。为了解决这个问题，就引入了多重分区的分配方案。所谓多重分区，就是把一个程序放在多个分区中，这样当一个作业在一个分区中装不下时，可以把它装入到另外一个分区，依此类推。采用多重分区分配方案，可以使存储空间的利用率得到提高，但是实现起来比较困难，所以这里不再赘述。第第4 4章章 存储管理存储管理 4.3 页式存储管理页式存储管理 4.3.1 基本原理把作业的虚拟地址空间划分成若干个长度相等的页(pages)，也可以称为“虚页”，每一个程序的虚页都从0开始编号。主存也划分成若干个与虚页长度相等的页框(pageframe)，也称为页面或实页。在静态页式存储管理系统中，作业加载时可以将任意一页放入内存中的任意一个页框，而且这些页框不必连续，从而实现了不连续分配。第第4 4章章 存储管理存储管理 但是要求一个作业在运行前将其所有的虚页全部都装入主存的块中，当然这就要求主存中有足够多的空闲块，否则程序便不能运行。如图4.18所示是分页存储管理的基本原理。第第4 4章章 存储管理存储管理 图4.19分页存储管理的基本原理第第4 4章章 存储管理存储管理 在分页系统中，页的大小往往都是2的整数次幂，因此在分页系统中，地址的结构由两部分构成：P(页号)和D(页内偏移量)，如图4.19所示。页内偏移量的值为02n-1。P=INTA/LD=AmodL注:A为逻辑地址,页面大小为L图4.20页的划分第第4 4章章 存储管理存储管理 对于分页系统来说，程序在虚拟地址空间是连续的，但却要映射到物理内存中不连续的空闲frame中，所以需要系统在内存中开辟一个页表区来建立每一个作业的虚页号到物理内存的frame号之间的映射关系，这个表格就叫做页变换表(pagemanagementtable)，也叫页表。页表中的内容分为三部分：页号、块号和页内偏移量。程序执行的时候，对于每一条访问内存的指令，分页系统的地址变化过程如图4.20所示。第第4 4章章 存储管理存储管理 图4.21分页式存储管理的地址变换过程页表始址页表始址页表长度页表长度页表寄存器页表块号页号5332712052018物理地址32018逻辑地址越界中断第第4 4章章 存储管理存储管理 过程说明：(1)由硬件机构自动将虚拟地址字分成虚页号和页内偏移量两个部分，虚页号送给累加器，它和页表起始地址之和就是所要查找的表项。(2)由页表控制寄存器中的页表起始地址和虚拟地址字中的虚页号查找页表，对应的虚页号的页表地址为：页表起始地址虚页号页表表项长度。(3)将页表中取出的frame号和虚拟地址字中的页内偏移量一起装入到地址寄存器，根据地址寄存器中的地址值来访问内存。第第4 4章章 存储管理存储管理 4.3.2 页式存储管理的地址变换 1页式管理的数据结构页式存储管理系统中，当进程建立时，操作系统为进程中所有的页分配页块。当进程撤消时需收回所有分配给它的物理页块。第第4 4章章 存储管理存储管理 为了完成上述功能，在一个页式存储管理系统中，一般要采用如下的数据结构：(1)进程页表：是逻辑页号(本进程的地址空间)到物理页面号(实际内存空间)的映射。(2)物理页面表(空闲内存页表)：描述物理内存空间的分配使用状况。整个系统有一个物理页面表。其数据结构是位示图(如图4.22所示)和空闲页面链表，用来记录内存中每个页的使用情况和当前空闲页的总数。第第4 4章章 存储管理存储管理 图4.23位示图第第4 4章章 存储管理存储管理 (3)请求表：描述系统内各个进程页表的位置和大小，用于地址转换，也可以结合到各进程的PCB里。整个系统有一个请求表。第第4 4章章 存储管理存储管理 2. 地址变换机构前面已经指出，在页式存储系统中，指令所给出的地址分为两部分：逻辑页号和页内偏移量。CPU中的内存管理单元(MMU)按逻辑页号通过查进程页表得到物理页框号，将物理页框号与页内偏移量相加即可形成物理地址，如图4.23所示。第第4 4章章 存储管理存储管理 程序装入后执行时，应该需要内存管理单元(MemoryManagementUnit，MMU)的支持，根据进程页表进行执行时的动态地址映射和保护。映射的过程如上所述。MMU的位置和功能如图4.24所示。第第4 4章章 存储管理存储管理 图4.24MMU的位置和功能MMU是MemoryManagementUnit的缩写，中文名是存储器管理单元，它是中央处理器（CPU）中用来管理虚拟存储器、物理存储器的控制线路，同时也负责虚拟地址映射为物理地址，以及提供硬件机制的内存访问授权。第第4 4章章 存储管理存储管理 图4.25页式地址变换第第4 4章章 存储管理存储管理 页面变换（页表建立）的过程是：先要得到进程所需要的页数，参照空闲内存页表，看是否有这么多的空闲页，如果有，则将N个页面分配给这个进程，并修改空闲内存页表，将程序一次性全部装入用户区内存，同时建立起这个进程的进程页表，也就是页面变换表。如果没有N个空闲页面，则被拒绝或者排队等待。第第4 4章章 存储管理存储管理 4.3.3 硬件支持从上面的介绍可以看出，每访问一次指令或者数据，至少需要访问两次内存，第一次是查找页表，第二次才是真正访问指令或者数据。为了加快页式存储管理的速度，往往也需要硬件支持，主要是页表基址寄存器、页表长度寄存器和关联存储器等一些寄存器。第第4 4章章 存储管理存储管理 1系统设置一对寄存器(1)页表基址寄存器(PageTableBaseRegister，PTBR)用户程序在执行过程中每次访问内存时(即每次地址映射时)，MMU需要根据当前进程的进程页表基址寄存器值和此次地址映射的逻辑页号，访问当前进程的进程页表(在内存)，得到此次地址映射的物理页号，再根据逻辑地址中页内偏移量得到真正的物理地址。在进程切换时页表基址寄存器的内容才被保存和恢复，其内容是当前进程的进程页表的内存起始地址。页表基址寄存器的工作原理如图4.26所示。第第4 4章章 存储管理存储管理 图4.26进程页表基址寄存器的工作原理第第4 4章章 存储管理存储管理 由图4.24可以看出以下4点：每次进程切换时不用保存和恢复当前新老进程的整个进程页表，只需保存和恢复PTBR。进程页表是由硬件访问的，这意味着进程页表的格式是由硬件规定的。对进程页表的访问是直接存取。用户程序执行时的每次内存访问，都至少访问内存两次，第一次访问进程页表，第二次才是访问此次要访问的页本身，这意味着用户程序的执行时间将增加一倍。第第4 4章章 存储管理存储管理 (2)页表长度寄存器为了实现存储保护，在页表基址寄存器的基础上，还需要一个页表长度寄存器，它用来存放当前进程页表的长度。在每次访问内存之前，先检查所取得指令的地址是否超过了进程页表的长度。如果在范围之内，则正常访问内存；如果在长度范围之外，则拒绝此次访问。第第4 4章章 存储管理存储管理 直接采用上述机构进行地址变换实际上是不可取的。由于页表是驻留在内存中的，为了进行地址变换，对于每一条访问内存的指令，系统至少要访问内存两次，这样程序执行的速度只能是原来的1/2。2关联存储器快表为缩短查找时间，可以将页表装入到关联存储器，按内容查找逻辑页号到物理页号的映射。很多页式系统都有一组关联存储器(TranslationLookasideBuffer，TLB)，用来存放当前运行作业的页表表项，以加速地址变换过程，这种页表称为快表，它是介于内存与寄存器之间的存储机制。内存中的页表有时也称为慢表。利用快表进行地址变换的过程如图4.25所示。第第4 4章章 存储管理存储管理 图4.27利用快表进行地址变换的过程页表页表第第4 4章章 存储管理存储管理 两级和多级页表两级和多级页表两级页表解决大页表占用大的连续存储空间的问题；关于“页表”的分页存放“页表”外层页表(页目录)；逻辑地址：外层页号+外层页内地址+页内地址多级页表10位10位12位第第4 4章章 存储管理存储管理 页框为4K;页目录项(4Byte)用来寻址一个页表；页表项(4Byte)用来指定一个物理内存页面。图中二级目录的寻址空间范围是图中二级目录的寻址空间范围是? 该页目录表寻址的该页目录表寻址的所有页表共可以寻址所有页表共可以寻址1024*1024*4096=4G 内内存空间。存空间。第第4 4章章 存储管理存储管理 4.28地址变换示意图(CPU的寄存器CR3用来确定当前页目录的物理地址)4.29页目录和页表表项结构每个表项由页框地址、访问标志位、脏（已改写）标志位和存在标志位等构成。第第4 4章章 存储管理存储管理 外部页表块号页号321078110110页表分页1122312021113001231121131011第第4 4章章 存储管理存储管理 外部页表外部页表外部页表寄存器寄存器物理地址外部页号P1外部页内地址P2逻辑地址页内地址d页表第第4 4章章 存储管理存储管理 4.3.5 优缺点分页式存储管理的优点：(1)没有外碎片，每个内碎片不超过页的大小。(2)一个程序不必连续存放。(3)便于改变程序占用空间的大小(主要指随着程序运行而动态生成的数据增多，要求地址空间相应增长，通常由系统调用完成而不是操作系统自动完成)。第第4 4章章 存储管理存储管理 分页式存储管理的缺点：(1)程序要全部装入内存。(2)采用动态地址变换机构会增加计算机的成本和降低处理机的速度。(3)各种表格要占用一定的内存空间，而且要花费一定的时间来建立和管理这些表格。(4)存储扩充问题没有得到解决。(5)不易实现共享。(6)不便于动态连接。第第4 4章章 存储管理存储管理 4.4 段式存储管理段式存储管理通常，一个作业是由若干个自然段组成的。因而，用户希望能把自己的作业按照逻辑关系划分为若干个段，每个段都有自己的名字和长度。要访问的逻辑地址是由段名(段号)和段内偏移量(段内地址)决定的，每个段都从0开始编址。这样，用户程序在执行中可用段名和段内地址进行访问。例如，下述的两条指令便是使用的段名和段内地址。第第4 4章章 存储管理存储管理 LOADL，A|(D)STOREI，B|(C)其中，前一条指令的含义是将分段A中D单元内的值读入寄存器L；后一条指令的含义是将寄存器I的内容存入分段B中的C单元内。第第4 4章章 存储管理存储管理 段式存储管理(simplesegmentation)可以实现共享共享。通常，在实现程序和数据的共享时，都是以信息的逻辑单位为基础的，比如共享某个例程和函数。段式存储管理可以实现分段保护分段保护。在多道程序环境下，为了防止其他程序对某程序在内存中的数据有意无意的破坏，必须采取保护措施。段式存储管理可以实现动态链接。段式存储管理使得段可以动态增长。第第4 4章章 存储管理存储管理 4.4.1 基本思想在页式存储管理思想中，作业的地址空间是连续的一维地址空间，程序的各个目标模块都由链接程序装配成一个可执行的程序后装入内存执行。第第4 4章章 存储管理存储管理 我们根据程序的模块结构，把作业地址空间划分为大小不同的一些块，我们把这些大小不同的块叫做段。每个程序段都有一个段名，且有一个段号。段号从0开始，每一段也从0开始编址，段内地址是连续的，通常分为主程序段、子程序段、库函数段和数据段等等。同时在物理内存中，也分成一些和这些块一样大的块。分段的基本原理如图4.26所示。第第4 4章章 存储管理存储管理 图4.26分段的基本原理第第4 4章章 存储管理存储管理 作业在装入的时候是一次性全部装入的，如果不是一次性装入，就叫做请求分段式的管理。将程序的地址空间划分为若干个段(segment)，程序加载时，为每个段分配其所需的一个连续内存分区，而进程中的各个段可以不连续地存放在内存的不同分区中。物理内存的管理采用动态分区的思想，即在为某物理内存的管理采用动态分区的思想，即在为某个段分配物理内存时，可以采用最先适应法、下次适个段分配物理内存时，可以采用最先适应法、下次适应法和最佳适应等方法。应法和最佳适应等方法。第第4 4章章 存储管理存储管理 在收回某个段所占用的空间时，要注意将收回的空间与其相邻的空间合并。分段式存储管理也需要硬件支持，以实现逻辑地址到物理地址的映射。分段式存储管理的基本原理如图4.27所示。第第4 4章章 存储管理存储管理 图4.27分段式存储管理的基本原理第第4 4章章 存储管理存储管理 在分段式存储管理的思想中，程序通过分段(segmentation)划分为多个模块，如代码段、数据段、共享段，其优点是可以分别进行编写和编译；可以针对不同类型的段采取不同的保护；可以以段为单位来进行共享，包括通过动态链接进行代码共享。在分段存储管理系统中，作业地址空间的每一个单元均采用二维地址(S，W)，其中，S为段号，W为段内地址或者偏移量，如图4.28所示。图4.28进程段地址第第4 4章章 存储管理存储管理 4.4.2 分段式管理的数据结构(1)进程段表：也叫段变换表(SMT)，如图4.29所示。它描述组成进程地址空间的各段。它可以是指向系统段表中表项的索引，每段都有段基址(baseaddress)。(2)系统段表：描述系统所有占用的段。(3)空闲段表：描述了内存中所有空闲段，可以结合到系统段表中。内存的分配算法可以采用最先适应法、最佳适应法和最坏适应法。第第4 4章章 存储管理存储管理 图4.29段式地址变换第第4 4章章 存储管理存储管理 4.4.3 分段式管理的地址变换为了实现从逻辑地址到物理地址的变换功能，在系统中设置了段表基址寄存器和段表长度寄存器。在进行地址变换时，系统将逻辑地址中的段号S与段表长度STL进行比较。若SSTL，表示段号太大，则越界访问，产生越界中断；若未越界，则根据段表的起始地址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存的起始地址，然后再检查段内地址D是否超过该段的段长SL。若DSL，同样发出越界中断；若未越界，则将该段的基址D与段内地址相加，即得到要访问的内存物理地址。第第4 4章章 存储管理存储管理 和分页式存储管理系统一样，当段表放在内存中时，分段式每访问一个数据或者指令，都需至少访问内存两次，从而成倍地降低了计算机的速率。解决的办法和分页存储管理的思想类似，即再增设一个关联寄存器，用于保存最近常用的段表项。由于一般情况下段比页大，因而段表项的数目比页表数目少，其所需的关联寄存器也相对较小，可以显著地减少存取数据的时间。第第4 4章章 存储管理存储管理 4.4.4 分段式管理的硬件支持如上面所述，和分页式存储管理的思想类似，也可以设置一对寄存器：段表基址寄存器和段表长度寄存器。段表基址寄存器用于保存正在运行进程的段表的基址，而段表长度寄存器用于保存正在运行进程的段表的长度。第第4 4章章 存储管理存储管理 同样，和分页式存储管理的思想类似，也可以设置联想存储器，它是介于内存与寄存器之间的存储机制，和分页式存储管理系统一样也叫快表。它的用途是保存正在运行进程的段表的子集(部分表项)，其特点是可按内容并行查找。引入快表的作用是为了提高地址映射速度，实现段的共享和段的保护。快表中的项目包括：段号、段基址、段长度、标识(状态)位、访问位和淘汰位。第第4 4章章 存储管理存储管理 4.4.5 分段式管理的优缺点分段式存储管理的优点：没有内碎片，外碎片可以通过内存紧凑来消除；便于改变进程占用空间的大小；便于实现共享和保护，即允许若干个进程共享一个或者多个段，对段进行保护。如图4.30所示是分段系统中共享一个compiler编译器程序的例子。分段式存储管理的缺点：作业需要全部装入内存，不能实现存储扩充。第第4 4章章 存储管理存储管理 图4.30分段系统中共享compilor的示意图第第4 4章章 存储管理存储管理 4.4.6 分页式管理和分段式管理的比较(1)分页是出于系统管理的需要，分段是出于用户应用的需要。(2)页的大小是系统固定的，而段的大小则通常不固定。(3)逻辑地址表示：分页是一维的，各个模块在链接时必须组织在同一个地址空间；而分段是二维的，各个模块在链接时可以把每个段组织成一个地址空间。(4)通常段比页大，因而段表比页表短，可以缩短查找时间，提高访问速度。(5)分段式存储管理可以实现内存共享，而分页式存储管理则不能实现内存共享。但是两者都不能实现存储扩充。分页式管理和分段式管理的比较如图4.31所示。第第4 4章章 存储管理存储管理 图4.31页式管理与段式管理的比较第第4 4章章 存储管理存储管理 4.5 段页式存储管理段页式存储管理 4.4.1 基本思想段页式存储管理是对虚拟页式和虚拟段式存储管理的结合，这种思想结合了二者的优点，克服了二者的缺点。这种思想将用户程序分为若干个段，再把每个段划分成若干个页，并为每一个段赋予一个段名。第第4 4章章 存储管理存储管理 也就是说将用户程序按段式划分，而将物理内存按页式划分，即以页为单位进行分配。换句话来说，段页式管理对用户来讲是按段的逻辑关系进行划分的，而对系统来讲是按页划分每一段的。在段页式存储管理中，其地址结构由段号、段内页号和页内地址三部分组成，如图4.32所示。第第4 4章章 存储管理存储管理 图4.32段页式存储管理的地址结构第第4 4章章 存储管理存储管理 在段页式存储管理中，为了实现从逻辑地址到物理地址的变换，系统中需要同时配置段表和页表。由于允许将一个段中的页进行不连续分配，因而使段表的内容有所变化：它不再是段内起始地址和段长，而是页表起始地址和页表长度。如图4.33所示是段页式存储管理中利用段表和页表进行逻辑地址到物理地址的映射过程。第第4 4章章 存储管理存储管理 图4.33段页式存储管理的地址映射第第4 4章章 存储管理存储管理 4.4.2 段页式存储管理的地址变换如图4.33所示，为了实现段页式存储管理的机制，需要在系统中设置以下几个数据结构：(1)段表：记录每一段的页表起始地址和页表长度。(2)页表：记录每一个段所对应的逻辑页号与内存块号的对应关系，每一段有一个页表，而一个程序可能有多个页表。(3)空闲内存页表：其结构同分页式存储管理，因为空闲内存采用分页式的存储管理。(4)物理内存分配：同分页式存储管理。第第4 4章章 存储管理存储管理 4.4.3 硬件支持在段页式系统中，为了便于实现地址变换，必须配置一个段表基址寄存器(在其中存放段表起始地址)和一个段表长度寄存器(在其中存放段长SL)。进行地址变换时，首先利用段号S，将它与段长SL进行比较。若S0。工作集大小范围：1|W(t,)|min(,n)，其中n是进程的总页面数。第第4 4章章 存储管理存储管理 (3)工作集大小的变化：进程开始执行后，随着访问新页面而逐步建立较稳定的工作集。当内存访问的局部性区域的位置大致稳定时，工作集大小也大致稳定；当局部性区域的位置改变时，工作集快速扩张和收缩过渡到下一个稳定值。工作集大小的变化如图4.39所示。第第4 4章章 存储管理存储管理 图4.39工作集大小的变化第第4 4章章 存储管理存储管理 (4)利用工作集进行常驻集调整的策略：记录一个进程的工作集变化。定期从常驻集中删除不在工作集中的页面。总是让常驻集包含工作集。第第4 4章章 存储管理存储管理 (5)工作集的困难：工作集的过去变化未必能够预示工作集的将来大小或组成页面的变化。记录工作集变化要求开销太大。对工作集窗口大小的取值难以优化，而且通常该值是不断变化的。第第4 4章章 存储管理存储管理 4缺页率算法(Page Fault Frequency，PFF)(1)PFF算法：页面被访问时的处理：每个页面设立使用位(usebit)，在该页被访问时设置usebit=1。缺页时的处理：每次缺页时，由操作系统计算与上次缺页的“虚拟时间”间隔t。缺页时对常驻集的调整：定义一个“虚拟时间”间隔的阈值(threshold)F，依据t和F来修改常驻集。第第4 4章章 存储管理存储管理 (2)和页面缓冲算法(pagebuffering)配合使用，可以获得良好的性能。(3)缺页率算法的主要缺点：当局部性区域的位置改变时，工作集的变化处于过渡阶段，其快速扩张使较多新页面添加到进程的常驻集中。其中较少使用的页面至少还要经过一段F虚拟时间才会被淘汰，因而带来较多不必要的调页开销。第第4 4章章 存储管理存储管理 4. 可变采样间隔算法(Variable-interval Sampled Working Set，VSWS)(1)VSWS算法：使用3个参数：采样间隔时间的下限M，采样间隔时间的上限L，一个采样间隔内允许发生的缺页次数的上限Q。第第4 4章章 存储管理存储管理 常驻集的调整：每个页面设立使用位(userbit)，在每个采样间隔的开始设置各页的userbit=0，而在每个采样间隔的结束只保留userbit=1的页面在常驻集中，其余页面从常驻集中删除。采样间隔划分：每次缺页时，对缺页次数加1。(2)VSWS算法的优点：在局部性区域位置改变时，缺页率上升，通过缩短采样间隔，删除无用页面，可降低常驻集扩张的峰值。第第4 4章章 存储管理存储管理 6虚拟存储中的负载控制负载控制讨论的是操作系统要在内存中驻留多少个并发进程才是较好的。1)改善时间性能的途径降低缺页率：缺页率越低，虚拟存储器的平均访问时间延长得越小。提高外存的访问速度：外存和内存的访问时间比值越大，则达到同样的时间延长比例所要求的缺页率就越低。第第4 4章章 存储管理存储管理 2)负载控制(loadcontrol)策略负载控制策略是：在避免出现抖动的前提下，尽可能提高进程并发水平。(1)基于工作集策略的算法(如PFF,VSWS)：它们隐含负载控制策略，只有那些常驻集足够大的进程才能运行，从而实现对负载的自动和动态控制。第第4 4章章 存储管理存储管理 (2)“L=S判据”策略(Denning,1980)：让缺页的平均间隔时间(是指真实时间而不是虚拟时间)等于对每次缺页的处理时间(即缺页率保持在最佳水平)，这时CPU的利用率达到最大。一种类似的策略称为“50%判据”策略，即让外存交换设备保持50%的利用率，这时CPU也达到最高的利用率。第第4 4章章 存储管理存储管理 (3)基于轮转置换算法的负载控制策略：定义一个轮转计数，描述轮转的速率(即扫描环形页面链的速率)。当轮转计数少于一定的阈值时，表明缺页较少或存在足够的空闲页面。当轮转计数大于阈值时，表明系统的进程并发水平过高，需降低系统负载。第第4 4章章 存储管理存储管理 4.7.4 虚拟段式存储管理 1段表内容为实现虚拟段式存储管理的各项功能和管理需要，在进程段表中添加了如下各项：(1)标志位：如存在位(presentbit)，修改位(modifiedbit/dirtybit)，扩充位(该段是否增加过长度)。(2)访问统计位：如使用位(usebit)。(3)存取权限位：如读R，写W，执行X。(4)外存地址：本段在外存的起始地址。第第4 4章章 存储管理存储管理 2越界中断处理进程在执行过程中，有时需要扩大分段，如数据段的扩充。由于要访问的地址超出原有的段长，所以引发越界中断。操作系统处理中断时，首先判断该段的“扩充位”，如可扩充，则增加段的长度；否则按出错处理。第第4 4章章 存储管理存储管理 3缺段中断处理在请求分段系统中，采用的是请求调段策略。CPU的硬件逻辑要根据段表表项进行地址变换或者产生缺段中断。请求分段存储管理与请求分页存储管理不同之处在于，指令和操作系统一定不会跨越在段边界上。但是，在请求分段系统中，一般会增加存取权限的违法中断和段的越界中断。第第4 4章章 存储管理存储管理 在请求调段时：先检查内存中是否有足够的空闲空间，若有，则装入该段，修改有关数据结构，中断返回；若没有，则检查内存中空闲区的总和是否满足要求，如是，则应采用紧缩技术，再转；否则，淘汰一些段，再转。第第4 4章章 存储管理存储管理 4请求分段系统的内存分配策略1)段的动态链接在程序开始运行时，只将主程序段装配好并调入内存，其他各段的装配是在主程序段的运行过程中逐步完成的。第第4 4章章 存储管理存储管理 2)链接间接字机器指令可采用直接寻址或间接寻址方式。采用间接寻址时，间接地址指示的单元的内容称为间接字，在间接字中，包含了直接地址及附加的状态位。其格式如图4.40所示。图4.40链接间接字格式第第4 4章章 存储管理存储管理 3)链接中断处理链接中断处理的步骤是：(1)根据链接间接字找出要访问段的符号名和段内地址。(2)分配段号，检查该段是否在内存。若不在内存，则从外存调入，并登记段表，修改内存分配表。(3)修改间接字：修改链接标志位为0，并修改直接地址。(4)重新启动被中断的指令执行。第第4 4章章 存储管理存储管理 4.8 高速缓冲存储器高速缓冲存储器 4.8.1 高速缓存的组织由于CPU的指令处理速度与内存中指令的访问速度存在差异(可达到一个数量级的差异，如IntelPentiumPro平均一个时钟周期可执行3条指令，)，因此为提高CPU的利用率，在CPU与内存之间组织了一个高速缓存结构，如图4.41所示。第第4 4章章 存储管理存储管理 图4.41高速缓存的组织结构第第4 4章章 存储管理存储管理 高速缓存由三部分组成：高速缓冲存储器、缓存目录和缓冲控制器。(1)高速缓冲存储器：主要作用是缓存内存中数据。(2)缓冲目录：描述各缓冲存储器块的状态。第第4 4章章 存储管理存储管理 内存地址行号：相应缓存块对应的内存地址(24位)为行号(13位)+列号(5位)+字节数(6位)。3个状态位描述相应缓存块的状态。(3)缓存控制器：负责缓存目录的维护，并利用缓存淘汰算法进行缓存的更新。第第4 4章章 存储管理存储管理 4.8.2 缓存的工作过程 在不同类型的内存操作时，缓存会有不同的工作过程。具体的缓存工作过程如下：(1)CPU读数据：缓存控制器自动查找缓存目录，确定相应内存数据是否在缓存中。第第4 4章章 存储管理存储管理 查找过程： 依据读操作的地址确定查找缓存目录的列号。 比较缓存目录相应列的各区行号与地址行号。 判断有效位是否为0。依据查找结果，有两种可能的操作： 如果在缓存，则从缓存中读数据，并修改访问标志。如果不在缓存，则从内存中读数据，同时该块内容被送到缓存相应列的某块。第第4 4章章 存储管理存储管理 (2)CPU写数据：查找缓存目录，确定相应地址是否在缓存中：如果在缓存，则修改缓存内容，并把缓存目录中相应修改位置1。这时有两种做法： 立即写：在内存与缓存的相应块同时写。 惰性写：数据只写入缓存，不马上写入内存。当该缓存块被淘汰时，才写回内存。 如果不在缓存，则先把内存读入缓存，再在缓存中修改。第第4 4章章 存储管理存储管理 (3)通道向内存写数据：数据被写入内存，缓存控制器同时查找缓存目录，如果有，则修改相应表项的有效位为1。(4)通道从内存读数据：如果在缓存中，则从缓存中读数据到通道。如果不在缓存中，则从内存中读数据到通道，但并不同时送到缓存。第第4 4章章 存储管理存储管理 4.9 内存管理实例分析内存管理实例分析 4.9.1 UNIX S5的内存管理 1对换1)对换设备空间的管理对换设备是块设备，如经过构造的磁盘盘区。核心分配对换空间时是按连续的块为一组进行的。进程使用对换空间是临时性的，这取决于进程调度的方式。第第4 4章章 存储管理存储管理 2)进程的换出和换入如果核心需要内存空间，它就把一个进程换出到对换设备中。这可能是由于下列原因引起的：创建子进程时必须为它分配空间；要增加进程的大小；栈区自然增长变大和核心期望把某些先前换出的进程重新换入内存。第第4 4章章 存储管理存储管理 图4.42对换一个进程空间到对换设备上第第4 4章章 存储管理存储管理 对换程序算法/*换入以前被换出的进程，换出其他进程，以腾出内存空间*/输入：无输出：无loop：for(所有被换出的处于就绪状态的进程)挑选被换出时间最久的进程；if(没有找到这种进程)第第4 4章章 存储管理存储管理 sleep(换入事件)gotoloop；if(在内存中有供进程使用的足够空间)把进程换入内存；gotoloop；/loop2：在修改过的算法中从这里进行循环for(所有在内存、非终止态且未封锁的进程)第第4 4章章 存储管理存储管理 if(有正在睡眠的进程)选择进程，其(优先数驻留内存时间)在数值上最大；else/没有睡眠态进程选择进程，其(驻留内存时间nice值)在数值上最大；if(被选进程没有睡眠或者驻留条件不满足要求)sleep(换出事件)；else换出进程gotoloop；/在修改过的算法中，应gotoloop2第第4 4章章 存储管理存储管理 2请求分页1)数据结构核心提供了4个主要的数据结构用来支持低级的存储管理和请求分页，它们是：页表项、盘块描述字、页框数据表(pageframedatatable)和对换用表。一旦系统生成，核心就为页框数据表分配空间，而为其他结构动态地分配内存页面。页表项包括该页的内存地址，读、写或执行的保护位和下列信息位：有效(valid)位、访问(reference)位、修改(modify)位、复制写(copyonwrite)位和年龄(age)位。第第4 4章章 存储管理存储管理 每一个页表项都与一个盘块描述字联系在一起。盘块描述字对逻辑页面的磁盘副本进行说明，如图4.43所示。第第4 4章章 存储管理存储管理 图4.43页表项和盘块描述字第第4 4章章 存储管理存储管理 页框数据表对整个内存的每个页面进行描述，它是通过页面号进行索引的。每项包含以下内容：(1)页面状态。说明该页面是在对换设备上或者是可执行文件，DMA当前正对该页面操作(从对换设备中读数据)，或者该页面可以重新分配。(2)访问该页面的进程数目。访问计数值等于访问该页的合法页表项目数。它可能不同于共享该页所在分区的进程数(如在fork算法中)。第第4 4章章 存储管理存储管理 (3)逻辑设备(对换或文件系统)和该页所在的盘块号。(4)指向在空闲页面链表上和在页面散列队列中的其他页框数据表项的指针。第第4 4章章 存储管理存储管理 图4.44给出了页表项、盘块描述字、页框数据表项和对换用计数表间的关系。一个进程虚拟地址1493K映射到一个页表项，它指向物理页面794；该页表项的盘块描述字说明了该页存于对换设备1的2743块中。该虚拟页面的对换用计数值为1，说明只有一个页表项指向对话设备上的一个页面。第第4 4章章 存储管理存储管理 图4.44请求分页数据结构间的关系第第4 4章章 存储管理存储管理 2)页面淘汰进程页面淘汰进程(又称页面窃取进程，pagestealerprocess)是一个核心进程，它把不再是进程工作集部分的那些页面换出内存。它是在系统初启时由核心创建的，在系统活动期间它一直存在。内存页面有两种状态：页面“老化”但还不适宜对换；页面适于对换且可用于重新分给其他虚拟页面。第第4 4章章 存储管理存储管理 当页面淘汰进程决定换出一个页面时，它要考虑该页的副本是否在对换设备上。这有三种可能性：(1)如在对换设备上没有该页的副本，则页面淘汰进程把它放在准备换出的队列中，然后继续找其他可以被换出的页，而在逻辑上认为对换已经完成。第第4 4章章 存储管理存储管理 (2)如该页面在对换设备上已有副本，并且内存中的内容未被修改过(页表项的修改位被清)，则核心清除相应页表项的有效位，减少页框数据表项的访问次数，并把该页放到自由链的末尾，供以后分配使用。(3)如该页在对换设备上有副本，但是其内存的内容被修改过，则核心将该页换出，并且释放它刚才占用过的的对换区。第第4 4章章 存储管理存储管理 3)缺页缺页又称页面故障(pagefaults)。系统可出现两类缺页：有效缺页和保护性缺页。第第4 4章章 存储管理存储管理 (1)有效缺页处理。对于进程虚拟地址空间以外的页面和虽在其虚拟地址空间内但当前未在内存的页面，它们的有效位是0，表示缺页。如果一个进程试图存取这样的一个页面，则导致有效缺页，此时核心调用有效缺页处理程序。有效缺页处理程序的算法如下：第第4 4章章 存储管理存储管理 输入：进程出现缺页的地址输出：无按照缺页地址找到分区表、页表项、盘块描述字、封锁分区表；if(地址在虚拟地址空间之外)向进程发信号(段越界)；gotoout；第第4 4章章 存储管理存储管理 if(地址现在是有效的)/进程可能已经在睡眠gotoout；if(页面在自由链盘中)从自由链中移走该页；调整页表项；while(页面内容无效)/先前已经有另外的进程出现过缺页sleep(页面内容有效事件)；第第4 4章章 存储管理存储管理 else/页面不在自由链中给分区指派新页面；把新页面放入散列链，更新页框数据表项；if(页面以前未装入内存且页面“请求清0”)把分到的页面清0；else从对换设备或者执行文件中读取虚拟页面；sleep(I/O完成事件)；第第4 4章章 存储管理存储管理 唤醒诸进程(页面内容有效事件)；置页面有效位；清除页面修改位和年龄位；重新计算进程优先数；out：封锁分区表；第第4 4章章 存储管理存储管理 (2)保护性缺页处理。它是由于进程对有效页面存取的权限不符合规定而引起的。例如，某进程试图对正文段进行改写。导致保护性缺页的另外一个原因是：一个进程想写一个页面，而该页面的复制写位在执行fork期间已经置位。核心必须确定导致保护性缺页的原因是上述哪一种。当发生保护性缺页事件后，硬件向其处理程序提供发生事件的虚拟地址，然后由处理程序进行处理。第第4 4章章 存储管理存储管理 保护性缺页处理程序的算法如下：输入：进程缺页地址输出：无/按地址找到分区表、页表项、盘块描述字、页框数据表、封锁分区表if(页面不在内存)gotoout；if(复制写位未置位)第第4 4章章 存储管理存储管理 gotoout；/实际程序错误发信号if(页框表项访问计数大于1)/与其他进程共享该页分配内存新页面；复制老页面内容到新页面；减少老的页框表项访问计数；更新页表项，使它指向新内存页面；第第4 4章章 存储管理存储管理 else/“淘汰”页面，因为没有进程在用它if(页面副本在对换设备上存在)释放该对换设备的空间，断开页面联系；if(页面在相应散列队列上)从散列队列上移走该页；第第4 4章章 存储管理存储管理 设置修改位；清除页表项中的复制写位；重新计算进程优先数；检查信号；out：封锁分区表；第第4 4章章 存储管理存储管理 4.9.2 Windows 2000/XP的内存管理内存管理器是Windows2000/XP执行程序的一部分，因此它存在于NT操作系统krnl.exe中，在硬件抽象层(HAL)中没有内存管理器的任何部分。内存管理器由下列组件构成：第第4 4章章 存储管理存储管理 (1)一组执行程序系统服务程序，用于虚拟内存的分配、释放和管理，它们中的大多数通过Win32API或内核模式设备驱动程序接口实现。(2)一个转换(translation-not-valid)和访问错误陷阱处理程序，用于解决硬件检测到的内存管理异常事件，并代表一个进程使虚拟页驻留。(3)运行在6个不同内核模式系统线程环境中的几个关键组件：第第4 4章章 存储管理存储管理 工作集管理程序(workingsetmanager)：优先级为16，由平衡集管理程序(内核创建的系统线程)每秒调用一次，或在空闲内存低于某个值时调用，驱动所有的内存管理规则，例如工作集的休整、年龄和已修改页的写入。进程/栈交换程序(process/stackswapper)：优先级为23，执行进程和内核线程的栈换入和换出操作。第第4 4章章 存储管理存储管理 修改页面的写入器(modifiedpagewriter)：优先级为17，把在修改链表上的脏页面写入到正确的调页文件中，当需要减小修改链表的大小时可以唤醒这个线程。映射页面写入器(mappedpagewriter)：优先级为17，把映射文件中的脏页面写入磁盘。第第4 4章章 存储管理存储管理 废弃段线程(deferencesegmentthread)：优先级为18，负责系统高速缓存和页面文件的增加和减少。清零页面线程(zeropagethread)：优先级为0，将空闲链表内的页清零，以便使零页高速缓存能用于满足将来的零页错误。第第4 4章章 存储管理存储管理 1. 虚拟地址空间布局32位Windows2000/XP上的每个用户进程可以占有2GB的私有地址空间(addressspace)，操作系统占有剩下的2GB地址空间。Windows2000/XP高级服务器和Windows2000/XP数据中心服务器支持一个导引选项，允许用户拥有3GB的地址空间。这两个地址空间的布局如图4.45所示。第第4 4章章 存储管理存储管理 图4.45Windows2000/XP系统的虚拟地址空间布局第第4 4章章 存储管理存储管理 (1)用户地址空间分布：在用户态和核心态都可访问的用户存储区为2GB；用户存储区为页交换区，可对换到外存。用户存储区的内容包括：专用进程地址空间：包括用户代码、数据和堆栈。线程环境块(TEB)：包括用户态代码可修改的线程控制信息。第第4 4章章 存储管理存储管理 进程环境块(PEB)：包括用户态代码可修改的进程控制信息。共享用户数据页：包括系统存储区映像，为用户态可访问的系统空间，目的在于避免用户态与核心态的频繁切换，如系统时间。表4.6描述了2GB的Windows2000/XP用户地址空间的详细布局。第第4 4章章 存储管理存储管理 表4.6 Windows 2000/XP用户地址空间的详细布局范围大小功能0X00XFFFF64KB不可访问区域，用来帮助程序员避免不正确的指针引用，访问该范围内的地址将导致访问违例0X100000X7FFEFFFF2GB减少至少192KB进程专用地址空间0X7FFDE0000X7FFDEFFF4KB第一个线程的线程环境块(TEB)，其他TEB在该页之前的页中创建0X7FFDF0000X7FFE0FFF4KB进程环境块(PEB)第第4 4章章 存储管理存储管理 0X7FFE00000X7FFE0FFF4KB共享用户数据页。该只读页面被映射到系统空间中包含系统时间、时钟的计数以及版本号等信息的页面。因有该页的存在，所以可以直接从用户模式读取这些数据而不需在内核模式读取0X7FFF10000X7FFEFFFF60KB不可访问的区域(紧随共享用户数据页的64KB区域之后的区域)0X7FFF00000X7FFFFFFF64KB不可访问区域，用来防止线程传递跨越用户/系统空间边界的缓冲区第第4 4章章 存储管理存储管理 (2)系统地址空间分布：在核心态可访问的系统存储区为2GB。按交换特征，系统存储区可分为以下几个区：固定页面区：永不被换出内存的页面，如HAL特定的数据结构。页交换区：非常驻内存的系统代码和数据，如进程页表和页目录。直接映射区：常驻内存且其寻址由硬件直接变换的页面，访问速度最快，用于存放内核中频繁使用且要求快速响应的代码。第第4 4章章 存储管理存储管理 如表4.7列出了带有2GB系统空间的X86系统的整体布局。X86体系结构在系统空间中有以下组成：系统代码：它包含了用于引导系统的操作系统映像、HAL和设备驱动程序。系统映射视图：它用于映射Win32.sys-Win32子系统可加载内核模式部分以及它使用的内核模式图形驱动程序。第第4 4章章 存储管理存储管理 会话空间(sessionspace)：用于映射与用户会话相关的信息。会话工作集列表描述了驻留和正使用的区域空间部分。 进程页面表(page table) 和页面目录(pagedirectory)：描述虚拟地址映射的结构。超空间(hyperspace)：一个特殊的区域，被用来映射进程工作集列表和为下列操作临时映射物理页面：在自由列表中将页面清零，使其他页面表中的页面表项无效和在进程创建时设置新进程的地址空间。第第4 4章章 存储管理存储管理 系统工作集列表：描述系统工作集的列表数据结构。系统高速缓存(systemcache)：用于映射在系统高速缓存中打开的文件的页面。页交换区(pagedpool)：可调页的系统内存堆。 系统页面表项(Page Table Entries，PTE)：系统PTE的交换区，用于映射系统页面。例如I/O空间，内核堆栈和内存描述列表。第第4 4章章 存储管理存储管理 非页交换区(nonpagedpool)：不可调页的系统内存堆，通常以两部分存在：一部分在系统空间较底端，一部分在系统空间较高端。崩溃转存信息：保留，用来记录有关系统故障状态的信息。HAL使用区域：为HAL相关的结构保留的系统内存。第第4 4章章 存储管理存储管理 表4.7 X86系统的整体布局80000000系统代码(NT操作系统Krnl，HAL)和系统中一些初始的未分页面缓冲池A0000000系统映射图(例如Win32k.sys)或者会话空间A4000000附加的系统PTES(高速缓存可以扩展到这里)C0000000进程页面表和页面目录C0400000超空间和系统工作集列表C0800000未使用不可访问C0C00000系统工作集列表C1000000系统高速缓存E1000000页面池EB000000(MIN)系统PTEFFBE0000崩溃转存信息FFC00000HAL使用第第4 4章章 存储管理存储管理 2. 地址转换机构Windows2000/XP使用二级页表结构转换虚拟地址，一个32位虚拟地址被解释为三个独立的分量，分别是页目录索引、页表索引和字节索引，它们用于找出描述页面映射结构的索引。在二级页表结构中的第一级称为页目录(每个进程有一个页目录)，第二级称为页表。每个页目录或页表有1024(210)个表项，每个表项为4个字节。由于每个页面为4KB，每个进程的地址空间可为4GB(210*210*212)。如图4.46所示为X86系统中32位虚拟地址的构成。第第4 4章章 存储管理存储管理 图4.46X86系统中32位虚拟地址的构成第第4 4章章 存储管理存储管理 页目录索引用于指出虚拟地址的页目录在页表中的位置。页表索引则用来确定页表项在页表中的具体位置，也就是说，页表项包含的虚拟地址被映射到物理地址。字节索引使得在物理页中能够寻找到某个具体的地址。如图4.47所示为这三个值之间的联系和它们从虚拟地址到物理地址的映射过程(其中，KPROCESS是系统核心进程，其块中保存着进程页目录的物理地址)。第第4 4章章 存储管理存储管理 图4.47X86系统中虚拟地址的变换第第4 4章章 存储管理存储管理 下面是虚拟地址变换的基本步骤：(1)内存管理的硬件设备定位当前进程的页目录。(2)页目录索引用于在页目录中指出页目录项(PageDirectoryEntry，PDE)的位置。(3)页表索引用于在页表中指明表项的位置。(4)页表项用于确定页框的位置。(5)当页表项指向了有效的页时，字节索引用于找到物理页内所需数据的地址。第第4 4章章 存储管理存储管理 3. 页面调度策略页面调度策略包括取页策略、置页策略和淘汰策略。(1)取页策略(fetchpolicy)：Windows2000/XP采用按进程需要进行的请求取页和按集群方法进行的提前取页。(2)置页策略：在线性存储结构中，简单地把装入的页放在未分配的物理页面即可。(3)淘汰策略：采用局部FIFO置换算法，即在本进程范围内进行局部置换，利用FIFO算法把驻留时间最长的页面淘汰出去。第第4 4章章 存储管理存储管理 4. 工作集策略Windows2000/XP根据内存负荷和进程缺页情况自动调整工作集：(1)进程创建时，指定一个最小工作集(可用SetProcessWorkingSetSize函数指定)。(2)当内存负荷不太大时，允许进程拥有尽可能多的页面。(3)系统通过自动调整，保证内存中有一定的空闲页面存在。每个进程都以同样的默认的工作集的最大值和最小值开始。这些数值列在表4.8中。第第4 4章章 存储管理存储管理 表4.8 默认的工作集的最大值和最小值内存大小默认的最小工作集大小(页面)默认的最大工作集大小(页面)小(小于19MB)2045中(2032MB)30145大 (Windows 2000/XP Prefessional大 于 32MB,Windows2000/XPServer大于32MB)50345第第4 4章章 存储管理存储管理 4. 页面状态Windows2000/XP的页面有6种状态：有效状态：某进程正在使用该页面。清零状态：空闲且已被清零。空闲状态：空闲但尚未被清零。备用状态：已标记为无效，但可快速回到有效状态。修改状态：已标记为无效，但对该页面内容的修改尚未写入外存，可快速回到有效状态。坏页状态：该页面产生硬件错，不能再用。第第4 4章章 存储管理存储管理 链接举例这里以WindowsNT/2000/XP中的动态链接库为例来进一步对链接加以说明。1)构造动态链接库动态链接库(DLL)是包含函数和数据的模块，它的调用模块可为EXE或DLL，它由调用模块在运行时加载，加载时它被映射到调用进程的地址空间。在VisualC+中有一类工程用于创建DLL，说明如下：第第4 4章章 存储管理存储管理 (1)库程序文件.C相当于给出一组函数定义的源代码。(2)模块定义文件.DEF相当于定义链接选项，也可在源代码中定义，如DLL中函数的引入和引出。第第4 4章章 存储管理存储管理 源文件中的链接选项如下：/Exampleofthedllimportanddllexportclassattributes_declspec(dllimport)inti;_declspec(dllexport)voidfunc();或void_declspec(dllexport)_cdeclFunction1(void);第第4 4章章 存储管理存储管理 (3)编译程序利用.C文件生成目标模块.OBJ。(4)库管理程序利用.DEF文件生成DLL输入库.LIB和输出文件.EXP。(5)链接程序利用.OBJ和.EXP文件生成动态链接库.DLL。(6)动态链接库映射到调用方进程的地址空间中。第第4 4章章 存储管理存储管理 2)构造动态链接库的装入方法(1)装入时动态链接(load-time)：在编程时显式调用某个DLL函数，该DLL函数在可执行文件中称为导入(import)函数。链接时需利用.LIB文件。在可执行文件中为引入的每个DLL建立一个IMAGE_IMPORT_DESCRIPTOR结构，而在装入时由系统根据该DLL映射在进程中的地址改写ImportAddressTable中的各项函数指针。第第4 4章章 存储管理存储管理 Hint是DLL函数在DLL文件中的序号，当DLL文件修改后，就未必指向原先的DLL函数了。在装入时，系统会查找相应的DLL，并把它映射到进程地址空间，获得DLL中各函数的入口地址，定位本进程中对这些函数的引用，如图4.5所示。第第4 4章章 存储管理存储管理 图4.5装入时动态链接的过程第第4 4章章 存储管理存储管理 (2)运行时动态链接(run-time)：在编程时通过LoadLibrary(给出DLL名称，返回装入和链接之后该DLL的句柄)、FreeLibrary、GetProcAddress(其参数包括函数的符号名称，返回该函数的入口指针)等API来使用DLL函数。这时不再需要引入库(importlibrary)。LoadLibrary或LoadLibraryEx把可执行模块映射到调用进程的地址空间并返回模块句柄；GetProcAddress获得DLL中特定函数的指针并返回；FreeLibrary把DLL模块的引用计数减1。当引用计数为0时，拆除DLL模块到进程地址空间的映射。DLL函数的调用过程如图4.6所示。第第4 4章章 存储管理存储管理 图4.6DLL函数的调用过程第第4 4章章 存储管理存储管理 下面是一个运行时动态链接的例子：HINSTANCEhInstLibrary;DWORD(WINAPI*InstallStatusMIF)(char*,char*,char*,char*,char*,char*,char*,BOOL);if(hInstLibrary=LoadLibrary(ismif32.dll)InstallStatusMIF=(DWORD(WINAPI*)(char*,char*,char*,char*,char*,char*,char*,BOOL)GetProcAddress(hInstLibrary,InstallStatusMIF);第第4 4章章 存储管理存储管理 if(InstallStatusMIF)if(InstallStatusMIF(office97,Microsoft操作系统,Office 97, 999.999, ENU, 1234, Completedsuccessfully,TRUE)!=0)FreeLibrary(hInstLibrary);第第4 4章章 存储管理存储管理 4.1.4 存储管理的目的在现代操作系统中，存储管理的主要目的有以下几个方面：(1)使得用户和用户程序不涉及内存物理的细节。(2)为用户程序完成程序的装入。(3)提高内存的利用率，弥补用户对内存容量的需求与内存实际容量之间的差距。(4)解决内存速度与CPU速度不匹配的问题。(5)实现内存共享。第第4 4章章 存储管理存储管理 习习 题题1存储管理的主要功能是什么？2什么是地址重定位？它分为哪几种？各有什么特点？3什么是内碎片和外碎片？各种存储管理方法中可能产生哪些碎片？4什么是“系统抖动”现象？产生抖动的直接原因是什么？可以采用哪几种方法防止抖动？第第4 4章章 存储管理存储管理 4.覆盖和交换的区别是什么？各有什么优缺点？6在内存存储管理系统中，分页存储管理和分段存储管理的主要区别是什么？7用可变式分区分配的存储管理方案中，基于链表的存储分配算法有哪几种？它们的主要思想是什么？8请说明为什么请求分页存储管理可以实现虚拟存储管理？它可以实现存储扩充吗？9什么是动态链接？用何种内存分配方法可以实现这种技术？第第4 4章章 存储管理存储管理 10在页表中，哪些数据结构是为实现请求调页而设置的？哪些数据项是为实现页面置换一页而设置的？11为什么要引入段页式存储管理？说明在段页式存储管理系统中的地址变换过程。12什么是局部性原理？13什么叫工作集？工作集模型的优点是什么？14UNIXSystemV、Windows2000/XP中采用了什么样的存储管理思想？第第4 4章章 存储管理存储管理 14.在一个请求分页存储管理系统中，一个程序的页面走向为4，3，2，1，4，3，5，4，3，2，1，5，采用LRU页面置换算法。设分配给该程序的存储块数为M，当M分别为3和4时，试求出在访问过程中发生缺页中断的次数和缺页率。比较两种结果，从中可得出什么启示？第第4 4章章 存储管理存储管理 16某分段式存储管理中采用如表4.9所示的结构。试回答：(1)给定段号和段内地址，完成段式管理中的地址变换过程。(2)给定0，340，1，10，2，500，3，400的内存地址，其中方括号内的第一元素为段号，第二元素为段内地址。(3)存取主存中的一条指令或者数据至少要访问几次主存？第第4 4章章 存储管理存储管理 表4.9 习题16用表段号段的长度(字节)主存起始地址06602191143300210090358012374961952第第4 4章章 存储管理存储管理 17某系统内存分布如图4.48所示。试回答：(1)当作业1、作业3执行完毕，释放它们所占用的内存后，内存空闲区有什么变化？并说明具体的变化情况。(2)当使用首次适应分配算法和最佳适应分配算法时，画出此时主存的结构。(3)当作业4(要求70KB的内存容量)要进入系统中，该作业在这两种不同的放置策略下各分配在哪一个空闲区中。第第4 4章章 存储管理存储管理 图4.48习题17用图第第4 4章章 存储管理存储管理 18某系统采用页式存储管理，现有J1、J2和J3共3个作业同驻内存。其中，J2有4个页面，被分别装入到内存的第3、4、6、8块中。假定页面和存储块的大小均为1024字节，内存的容量为10KB。(1)写出J2的页面映像表。(2)当J2在CPU上运行时，执行到其地址空间第500号处遇到一条传送指令：MOV2100,3100请用地址变换图计算出MOV指令中两个操作数的物理地址。第第4 4章章 存储管理存储管理 19一台计算机有4个页框，装入时间、上次引用时间和它们的R(读)与M(修改)位见表4.10，请问NRU、FIFO、LRU和第二次机会算法将替换哪一页？表4.10 习题19用表页装入时间/s上次引用时间/sRM012627900123026010212027211316028011第第4 4章章 存储管理存储管理 20在一个请求分页管理的系统中，内存容量为1MB，被划分为256块，每块4KB。现有一个作业，它的页表如表4.11所示。(1)若给定一个逻辑地址为9016，其物理地址是多少？(2)若给定一个逻辑地址为12300，给出其物理地址的计算过程。第第4 4章章 存储管理存储管理 表4.11 习题20用表页号块号状态0240126023203141