《操作系统》教学课件-项目三-存储器管理

操作系统工程三共分为八个任务操作系统工程三共分为八个任务1工程三存储器管理一二三四存储器管理概述单一连续分配管理方式分区存储管理方式覆盖技术与对换技术五六七八分页存储管理方式分段存储管理方式虚拟存储管理方式Windows操作系统的存储管理工程三存储器管理一二三四存储器管理概述单一连续分配管理2一、存储体系二、存储器管理的主要功能具体内容存储器管理概述一三、地址变换四、各种存储管理方式一、存储体系二、存储器管理的主要功能具体内容存储器管理概述一3

一、存储体系为解决速度和容量之间的矛盾，各种存储设备组成了一个存储体系，如以下图所示。在此存储体系中，包含了少量的速度快、昂贵的高速缓存Cache，中等速度、中等价格的内存RAM，以及容量大、速度慢的磁盘。高速缓存内存外存数据存取速度快存储容量小数据存取速度中等存储容量中等数据存取速度慢存储容量大一、存储体系为解决速度和容量之间的4

二、存储器管理的主要功能1.内存的分配与回收内存空间的分配是指采用一定的数据结构，按照一定的算法为每一道程序分配内存空间，并记录内存空间的使用情况和作业的分配情况。内存空间的回收是指当一个作业运行结束后，必须归还所占用的内存空间，即在记录内存空间使用情况的数据结构中进行修改，并且把记录作业分配情况的数据结构删除。2.地址变换在多道程序环境下，程序的逻辑地址与分配到主存的物理地址是不一致的，而CPU执行指令时是按物理地址进行的，所以要进行地址转换，即将逻辑地址转换为物理地址。3.内存共享所谓内存共享是指两个或多个进程共用内存中相同的区域，这样不仅能使多道程序动态地共享内存，提高内存的利用率，而且还能共享内存中某个区域的信息。二、存储器管理的主要功能1.内存的分配与回收5

4.内存的保护的目的在于为多个进程共享内存提供保障，使内存中的各道程序只能访问它自己的区域，防止各道程序间相互干扰。特别是当一道程序发生错误时，不至于影响其他进程的运行，更要防止破坏系统程序。5.内存的扩充用户在编制程序时，不应该受到内存容量的限制，所以要采用一定的技术来“扩充〞内存的容量，使用户得到比实际内存容量大得多的内存空间。具体实现是在硬件支持下，软件、硬件相互合作，将内存和外存结合起来统一使用。通常是借助虚拟存储技术。4.内存的保护的目的在于为多个进程共享内6

三、地址变换1.逻辑地址用户源程序经过编译后的每个目标模块都以0为基地址顺序编址，这种地址称为逻辑地址，也称为相对地址。2.物理地址在多道程序环境下，程序的逻辑地址与分配到主存的物理地址是不一致的，而CPU执行指令时是按物理地址进行的，所以要进行地址转换，即将逻辑地址转换为物理地址。在多道程序环境下，程序的逻辑地址与分配到内存的物理地址是不一致的，而CPU执行指令时是按物理地址进行的，所以要进行地址变换，即将逻辑地址转换为物理地址〔也称为地址映射或地址重定位〕。三、地址变换1.逻辑地址用户源程序经过编译73.地址变换用户源程序经过编译后的每个目标模块都以0为基地址顺序编址，这种地址称为逻辑地址，也称为相对地址。当用户程序被装入内存时，一次性实现逻辑地址到物理地址的变换，以后不再改变。一般是在装入内存时由重定位装入程序完成。在程序执行过程中需要访问数据时再进行地址变换，即逐条指令执行时完成地址变换。通常情况下，为了提高效率，此工作由硬件地址映射机制来完成。〔1〕静态重定位〔2〕动态重定位与静态重定位相比，动态重定位的优点是显而易见的，因此现代计算机系统中主要采用动态重定位方法。3.地址变换用户源程序经过编译后的每个目标模块都以8对内存的存储管理方式，根据是否把作业全部装入，全部装入后是否分配到一个连续的存储区域，可以分为以下图所示的几种管理方式。存储管理方式部分装入分页式虚拟存储管理段页式虚拟存储管理分段式虚拟存储管理全部装入连续分配单一连续分配分页存储管理分段存储管理段页式存储管理离散分配分区分配固定分区存储管理可变分区存储管理

四、各种存储管理方式对内存的存储管理方式，根据是否把作业全部装入，全部装9一、根本原理二、内存空间的分配具体内容单一连续分配管理方式二三、地址变换与存储保护一、根本原理二、内存空间的分配具体内容单一连续分配管理方式二10采用单用户存储管理方式具有以下特点：一、根本原理在单用户连续存储管理方式下，内存中仅驻留一道程序，整个用户区被一用户独占.在这种管理方式下，存储器利用率极低，仅能用于单用户单任务的操作系统，不能用于多用户系统和单用户多任务系统中。管理简单。它把内存分为两个区，用户区一次只能装入一个完整的作业，且占用一个连续的存储空间。它需要很少的软硬件支持，且便于用户了解和使用。资源利用率低。不管用户区有多大，它一次只能装入一个作业，这样造成了存储空间的浪费，使系统整体资源利用率不高。在内存中的作业不必考虑移动的问题，并且内存的回收不需要任何操作。这种分配方式不支持虚拟存储器的实现。采用单用户存储管理方式具有以下特点：一、根本11

二、内存空间的分配在单一连续分配存储管理方式下，任何时刻内存中最多只有一个作业，适合于单道运行的计算机系统。采用这种存储管理方式时，内存分为两个分区：1.系统区系统区是仅提供给操作系统使用的内存区，通常驻留在内存的低地址局部。用户区是指除系统区以外的内存空间，提供给用户使用。2.用户区等待装入内存的作业排成一个作业队列，当内存中无作业或一个作业执行结束，允许作业队列中的一个作业装入内存。其分配过程是：首先，从作业队列中取出队首作业；判断作业的大小是否大于用户区的大小，假设大于那么作业不能装入，否那么可以把作业装入用户区。它一次只能装入一个作业。二、内存空间的分配在单一连续分配存储管理方式12

三、地址变换与存储保护1.地址变换采用单一连续分配管理方式时，处理器设置两个存放器：界限存放器和基地址存放器。界限存放器用来存放内存用户区的长度，基地址存放器用来存放用户区的起始地址。一般情况下，这两个存放器的内容是不变的，只有当操作系统占有的存储区域改变时才会改变。处理器≥+主存界限寄存器基地址寄存器逻辑地址物理地址否是地址越界长度基址其转换过程如以下图所示。三、地址变换与存储保护1.地址变换采用单一13

2.存储保护单用户连续存储管理方式下，处理器在执行指令时，通过比较逻辑地址和界限存放器的值，来控制产生“地址越界〞中断信号，以到达存储保护的目的。在硬件方面，常见的几种单用户操作系统中，如CP/M，MS-DOS及RT-11等，都未设置存储器保护设施。主要原因在于：内存由用户独占，不可能存在受其他用户程序干扰的问题；用户程序也很容易通过系统的再启动而重新装入内存。可能出现的破坏行为也只是由用户程序自己去破坏操作系统，其后果并不严重，只是影响该用户程序的运行；2.存储保护单用户连续存储管理方式下，处14一、固定分区存储管理方式二、可变分区存储管理方式具体内容分区存储管理方式三三、紧凑技术一、固定分区存储管理方式二、可变分区存储管理方式具体内容分区15

一、固定分区存储管理方式1.根本原理固定分区是指系统预先把内存中的用户区划分成假设干个固定大小的连续区域。每一个区域称为一个分区，每个分区可以装入一个作业，一个作业也只能装入一个分区中，这样就可以装入多个作业，使它们并发执行。2.分区分配表在固定分区存储管理方式下，为了记录各个分区的使用情况，方便内存空间的分配与回收操作，通常要为分区建立一张表，如以下图所示。分区的划分方式有以下两种：〔1〕分区大小相等〔2〕分区大小不等一、固定分区存储管理方式1.根本原理固定分16区号大小起始地址状态18KB16KBJ1216KB24KB0332KB40KBJ2464KB72KB0…………固定分区分配表因为在作业装入之前，主存中的分区大小和个数已经确定，也就是说分区分配表的记录个数是确定的。所以，分区分配表一般采用顺序存储方式，即用数组存储。内存空间016KB24KB40KB72KB136KB操作系统区作业J1作业J2区号大小起始地址状态18KB16KBJ1216KB24KB0173.地址变换由于固定分区方式是预先把内存划分成假设干个区，每个分区只能放一个作业，因此作业在执行过程中不会改变分区的个数和大小。所以，地址转换采用静态重定位方式，即在作业被装入内存时，一次性地完成地址变换。地址转换过程是：CPU获得的逻辑地址首先与下限存放器的值相加，产生物理地址；然后与上限存放器的值比较：假设大于上限存放器的值，产生“地址越界〞中断信号，由相应的中断处理程序处理；假设不大于上限存放器的值，那么该物理地址就是合法地址，它对应于内存中的一个存储单元。3.地址变换由于固定分区方式是预先把内存划分成假设18例1：在某系统中采用固定分区分配管理方式，内存分区情况如左图所示。现有大小为1KB，9KB，33KB，121KB的多个作业要求进入内存，试画出它们进入内存后的空间分配情况，并说明内存浪费有多大？解析：采用固定分区存储管理方式，作业进入系统后的分配情况如右图所示，内存浪费512KB-20KB-(1KB+9KB+33KB+121KB)=328KB。例1：在某系统中采用固定分区分配管理方式，内存分区情19

二、可变分区存储管理方式可变分区是指系统不预先划分固定区域，而是在作业装入时根据作业的实际需要动态地划分内存空间。1.根本原理系统在作业装入内存执行之前并不建立分区，当要装入一个作业时，根据作业需要的内存量查看内存中是否有足够的空间：假设有，那么按需要量分割一个分区分配给该作业；假设无，那么令该作业等待内存空间。由于分区的大小是按作业的实际需要量来定的，且分区的个数也是随机的，所以可以克服固定分区方式中的内存空间的浪费，有利于多道程序设计，实现了多个作业对内存的共享，进一步提高了内存资源利用率。二、可变分区存储管理方式可变分区是指系统不预20随着作业的装入、撤离，内存空间被分成许多个分区。当一个新的作业要求装入时，必须找一个足够大的空闲区，如果找到的空闲区大于作业需要量，那么作业装入后又把原来的空闲区分成两局部，一局部被作业占用了，而另一局部又分成为一个较小的空闲区。当一个作业运行结束撤离时，它归还的区域如果与其他空闲区相邻，那么可合成一个较大的空闲区，如以下图所示。随着作业的装入、撤离，内存空间被分成许多个分区。当一212.采用的数据结构在可变分区存储管理方式中，内存中分区的数目和大小随作业的执行而不断改变。为了实现分区分配，系统中必须配置相应的数据结构，用来记录内存的使用情况，包括空闲分区的情况和已用分区的情况。为此，系统设置了两个表，即已用分区表和空闲分区表。〔1〕已用分区表记录当前已经分配给用户作业的内存分区，包括分区序号、分区大小、起始地址和状态。〔2〕空闲分区表记录当前内存中空闲分区的情况，包括空闲分区序号、分区大小、起始地址和状态。因为已用分区表和空闲分区表中记录的个数是随着内存的分配与回收而变化的，所以这两个表一般采用链表的形式存储，链表中的数据域记录相关的信息。2.采用的数据结构在可变分区存储管理方式中，内存中223.分区分配算法〔1〕首次适应算法〔FF〕首次适应算法也叫最先适应算法，要求空闲分区表中的记录按地址递增的顺序排列。每次分配时，总是顺序查找空闲分区表，找到第一个能满足长度要求的空闲分区。分割这个空闲分区，一局部分配给作业，另一局部仍为空闲分区。优点：优先利用内存中低址局部的空闲分区，在高址局部的空闲区很少被利用，从而保存了高址局部的大空闲区，为以后到达大作业分配大的内存空间创造了条件。缺点：低址局部不断被划分，致使留下许多难以利用的很小的空闲分区，即内存“碎片〞。而每次查找又都是从低址局部开始，这无疑增加了查找可用空闲分区的开销。3.分区分配算法〔1〕首次适应算法〔FF〕首次适应23〔2〕循环首次适应算法该算法要求空闲分区表的记录仍然按地址递增的顺序排列。每次分配时，是从上次分配的空闲区的下一条记录开始顺序查找空闲分区表，最后一条记录不能满足要求时，再从第1条记录开始比较，找到第一个能满足作业长度要求的空闲分区，分割这个空闲分区，装入作业。否那么作业不能装入。

优点：能使内存中的空闲分区分布得更均匀，减少查找空闲分区的开销。缺点：缺乏大的空闲分区。〔2〕循环首次适应算法该算法要求空闲分区表的记录仍然24〔3〕最正确适应算法〔BF〕最正确适应算法也叫最优适应算法，要求把空闲分区按长度递增次序登记在空闲分区表中。每次分配时，可以从所有的空闲分区中挑选一个能满足作业要求的最小空闲区进行分配。这样可以保证不去分割一个更大的空闲区，使装入大作业时比较容易得到满足。

优点：解决了大作业的分配问题。缺点：容易产生内存碎片，如果找出的分区正好满足要求，那么是最适宜的了；如果比所要求的略大，那么分割后使剩下的空闲区就很小，以致无法使用。另外，按这种方法，在回收一个分区时也必须对分配表或链表重新排列，这样就增加了系统开销。〔3〕最正确适应算法〔BF〕最正确适应算法也叫最优适25〔4〕最差适应算法〔WF〕最差适应算法也叫最坏适应算法，要求把空闲区按长度递减的次序登记在空闲分区表中。每次分配时，总是挑选一个最大的空闲区，分割一局部给作业使用，使剩下的局部不至于太小而成为内存碎片。

优点：不会产生过多的碎片。缺点：影响大作业的分配。另外，由于收回内存时要按长度递减的顺序插入到空闲分区表中，因而增加了系统开销。〔4〕最差适应算法〔WF〕最差适应算法也叫最坏适应算26首次适应算法的另一个优点是尽可能地利用了低地址空间，从而保证高地址有较大的空闲区来放置较大的作业。最差适应算法由于过多地分割大的空闲区，当遇到较大作业申请时，很可能无法满足其申请，该算法对中、小作业比较有利。因此，在实际系统中，首次适应算法用得最多。从搜索速度和回收过程上看，首次适应算法具有最正确性能；在空间利用上，首次适应算法比最正确适应算法好，最正确适应算法又比最差适应算法好；最正确适应算法找到的空闲区是最正确的，但在某些情况下，不一定能提高内存的利用率。比较与总结首次适应算法的另一个优点是尽可能地利用了低地址空间，274.分区的回收〔1〕回收的分区前后没有相邻的空闲分区当一个作业运行结束后，在已用分区表中找到该作业，根据该作业所占内存的始址和大小，去修改空闲分区表相应的记录。其修改情况分为四种在空闲分区表中要增加一条记录，该记录的始址和大小即为回收分区的始址和大小。〔2〕回收分区的前面有相邻的空闲区在空闲分区表中找到这个空闲分区〔查找的方法是比较空闲分区的始址＋空闲分区的大小与回收分区的始址是否相等〕，修改这个空闲分区的大小，即加上回收分区的大小，始址不变。4.分区的回收〔1〕回收的分区前后没有相邻的空闲分区28〔3〕回收分区的后面有相邻的空闲区在空闲分区表中找到这个空闲分区〔查找的方法是回收分区的始址＋回收分区的大小与空闲分区的始址比较是否相等〕，修改这个空闲分区的始址和大小。始址为回收分区的始址，大小为回收分区的大小与空闲分区的大小之和。〔4〕回收分区的前后都有相邻的空闲区在空闲分区表中找到这两个空闲分区，修改前面相邻的空闲区的大小，其始址不变。大小改为相邻两个空闲分区和回收分区的大小之和，然后从空闲分区表中删除后一个相邻空闲分区的记录。〔3〕回收分区的后面有相邻的空闲区在空闲分区表中找到29例1：内存有两个空闲区F1，F2，如图1所示。F1为220KB，F2为120KB，另外依次有J1，J2，J3三个作业请求加载运行，它们的内存需求量分别是40KB，160KB，100KB，试比较首次适应算法、最正确适应算法和最差适应算法的性能。解析：在首次适应算法和最差适应算法中可以给所有作业分配空间，在最正确适应算法中，还有作业J3不能分配，如图2所示。

图1

图2例1：内存有两个空闲区F1，F2，如图1所示。F1为304.地址变换与存储保护〔1〕地址变换可变分区存储管理方式一般采用动态重定位方式装入作业。地址转换过程如下：①当作业占用处理器时，进程调度把该作业所占分区的起始地址送入基址存放器，把作业所占分区的最大地址送入限长存放器。③当取出一条指令后，把该指令中的逻辑地址与基址存放器内容相加得到物理地址，该物理地址必须满足：物理地址<=限长存放器的值。此时允许指令访问内存单元的地址，否那么产生“地址越界〞中断，不允许访问。②作业执行过程中，处理器每执行一条指令，都要由硬件的地址转换机构把逻辑地址转换成物理地址。4.地址变换与存储保护〔1〕地址变换可变分区存储管31〔2〕存储保护系统设置了一对存放器，称为“基址存放器〞和“限长存放器〞，用它记录当前在CPU中运行作业在内存中所占分区的始址和末址。当处理器执行该作业的指令时必须核对表达式“始址<=绝对地址<=末址〞是否成立。假设成立，就执行该指令，否那么就产生“地址越界〞中断信号，停止执行该指令。运行的作业在让出处理器时，调度程序选择另一个可运行的作业，同时修改当前运行作业的分区号和基址存放器、限长存放器的内容，以保证处理器能控制作业在所在的分区内正常运行。〔2〕存储保护系统设置了一对存放器，称为“基址存放器32

三、紧凑技术为了解决碎片问题，可采用的一种方法是，将内存中的所有作业进行移动，使它们相邻接。这样原来分散的多个内存碎片便拼接成了一个大的空闲分区，从而可以把作业装入运行。这种通过移动把多个分散的小分区拼接成大分区的方法，称为“紧凑〞或“拼接〞〔也称为“合并〞、“移动〞〕。在移动时，虽可聚集内存的空闲区，但也增加了系统的开销。此外，移动是有条件的，当作业不与外围设备交换信息时，可以移动，否那么不能移动。由于经过移动后的用户程序在内存中的位置发生了变化，假设不对程序和数据的地址进行相应修改〔变换〕，程序将无法执行。三、紧凑技术为了解决碎片问题，可采用的一种方33一、覆盖技术二、对换技术具体内容覆盖技术与对换技术四一、覆盖技术二、对换技术具体内容覆盖技术与对换技术四34覆盖的根本原理可以从下面的例子来描述。所谓覆盖，是指同一内存区可以被不同的程序段重复使用。们把可以相互覆盖的程序段叫做覆盖，而把可共享的主存区叫做覆盖区。为此，我们把程序执行时并不要求同时装入内存的覆盖组成一组，叫覆盖段，并分配同一个内存区。这样，覆盖段与覆盖区一一对应。主程序A（20K）子程序D（30K）子程序E（20K）子程序B（50K）子程序F（40K）子程序C（30K）作业J常驻部分A（20K）覆盖区0（50K）覆盖区1（40K）EDBAFC程序逻辑关系使用覆盖技术后的覆盖结构A〔20K〕＋B〔50K〕＋C〔30K〕＋D〔30K〕＋E〔20K〕＋F〔40K〕＝190KA〔20K〕＋B〔50K〕＋F〔40K〕＝110K该作业要求的内存空间：使用覆盖技术后所需要的内存空间：

一、覆盖技术覆盖的根本原理可以从下面的例子来描述。所谓覆35覆盖技术的关键是提供正确的覆盖结构。通常，一个作业的覆盖结构要求编程人员事先给出，对于一个规模较大或比较复杂的程序来说是难以分析和建立它的覆盖结构的。因此，通常覆盖技术主要用于系统程序的内存管理上。覆盖技术的主要特点是打破了必须将一个作业的全部信息装入内存后才能运行的限制，在一定程度上解决了小内存运行大作业的矛盾。覆盖技术的关键是提供正确的覆盖结构。通常，一个作业的36

二、对换技术所谓“对换〞，是指把内存中暂时不能运行的进程，或暂时不用的程序和数据，换出到外存上，把已具备运行条件的进程，或进程所需要的程序或数据，换入到内存的技术，对换技术现在已被广泛应用于操作系统中。它的主要特点是打破了一个程序一旦进入内存便一直运行到结束的限制。对换有两种方式：〔1〕整体对换〔2〕局部对换如果对换是以整个进程为单位，便称之为“整体对换〞或“进程对换〞，这种对换被广泛应用于分时系统中，其目的是用以解决内存紧张问题，并可进一步提高内存的利用率。如果对换是以“页〞或“段〞为单位进行的，那么分别称之为“页面对换〞或“分段对换〞，又统称为“局部对换〞，这种对换方法是实现请求分页或请求分段式存储管理的根底，其目的是为了支持虚拟存储系统。二、对换技术所谓“对换〞，是指把内存中暂时不37一、根本原理二、页表具体内容分页存储管理方式五三、地址变换四、对页式存储管理的改进一、根本原理二、页表具体内容分页存储管理方式五三、地址变换四38一、根本原理1.内存空间划分页式存储管理将内存空间划分成等长的假设干个区域，称为物理块或页框。内存的所有物理块从0开始编号，称作物理块号；每个物理块内亦从0开始依次编址，称为块内地址。2.作业空间划分系统将用户作业地址空间按照物理块大小划分成假设干个区域，称为页面或页。各个页面从0开始依次编号，称作逻辑页号；每个页面内从0开始编址，称为页内地址。因此逻辑地址由页号和页内地址两局部组成，如以下图所示。一、根本原理1.内存空间划分页式存储管理将393.内存分配在分配存储空间时，总是以块为单位，按照作业的页数分配物理块。分配的物理块可以连续也可以不连续。由于作业的最后一页经常装不满一块而形成不可利用的碎片，称为“页内碎片〞。4.页面大小在确定页面大小时，假设选择的页面较小，一方面可使内存碎片小，并减少了内存碎片的总空间，有利于提高内存的利用率。但另一方面，也会使每个进程要求较多的页面，从而导致页表过长，占用大量内存空间，此外，还会降低页面换进换出的效率。假设选择的页面较大，虽然可以减少页表长度，提高换进换出效率，但却又会使页内碎片增大。

因此，页面的大小要适中。通常，页面的大小是2的整数次幂，且常在29～213，即512B～8KB。3.内存分配在分配存储空间时，总是以块为单位，按照40

二、页表系统为每个作业建立了一张页面映射表，简称页表。页表的一般格式如下表所示。页表给出逻辑地址中的页号与内存块号的对应关系。在配置了页表后，当作业执行时，通过查找页表，可找到每页在内存中的物理块号。可见，页表的作用是实现从页号到块号的地址映射。页号块号0215……从用户角度看，用户使用的依然是一维的逻辑空间，与使用分区管理没有什么两样。页的划分完全是一种系统硬件行为。页划分后，作业的逻辑地址变为页号和页内地址。二、页表系统为每个作业建立了一张页面映射表，41

三、地址变换为了能将用户地址空间中的逻辑地址变换为内存空间中的物理地址，在系统中必须设置地址变换机构。该机构的根本任务是实现逻辑地址到物理地址的转换。由于页内地址和物理块内地址是一一对应的，因此，地址转换机构的任务实际上只是将逻辑地址中的页号转换为内存中的物理块号。由逻辑地址计算出页号和页内地址的计算方法如下：页号=逻辑地址/页长〔商〕页内地址=逻辑地址mod页长〔余数〕由块号计算物理地址的计算方法为：物理地址=块号×块长+块内地址其中，块长等于页长，块内地址等于页内地址。三、地址变换为了能将用户地址空间中的逻辑地址42分页式地址变换过程如以下图所示，假设页面大小为1KB。块号块内地址6266B否页表始址页表长度2122页号页内地址页表寄存器+02152639页号块号6122越界

主存2170B物理地址逻辑地址≤是CPU分页式地址变换过程如以下图所示，假设页面大小为1KB43例1：在一个分页式存储管理系统中，页面大小为1KB，假定页号0，1，2，3分别对应3，4，9，7块，现有一逻辑地址〔页号为2，页内地址为20〕，试计算相应的物理地址。解析：从逻辑地址中取出页号2，从页表中取出该页的块号9，因页内地址为20，所以块内地址也是20。

根据物理地址的计算公式可得：物理地址=块号×块长＋块内地址=9×1024＋20=9236例1：在一个分页式存储管理系统中，页面大小为1KB，44四、对页式存储管理的改进为了提高处理速度，可以采用快表和两级页表的方法对页式存储管理进行改进。1.快表为了提高地址转换速度，可以在地址转换机构中增设一个具有并行查询能力的特殊高速缓冲存放器，用来存放页表的一局部。我们把存放在高速缓冲存放器中的页表叫做快表，快表的结构和页表一样。这个高速缓冲存放器又叫做联想存放器。采用快表的地址转换过程是：在CPU给出逻辑地址后，由地址转换机构自动地将页号送入高速缓冲存储器，与快表中的所有页号进行比较。假设快表中有要处理的页号，那么从快表中取出所对应的块号；假设快表中无要处理的页号，再访问内存，到页表中查找，把物理块号送地址存放器，并把此表项存入快表的一个存储单元中。四、对页式存储管理的改进为了提高处理速度，可45具有快表的地址转换如以下图所示。是否页表始址页表长度2122逻辑地址页表寄存器+02152639页号块号6122越界联想寄存器152639页号块号页表快表

主存21706266物理地址≤CPU具有快表的地址转换如以下图所示。是否页表始址462.两级页表现代计算机已普遍使用32或64位虚拟地址，可以支持232～264容量的逻辑地址空间，采用页式存储管理时，页表会相当的大。假设每页大小4KB，那么需要1M个页表项，每个页表项占4B，页表需要占用内存4MB。系统存放页表是需要连续的内存空间的，而找到较大的连续内存空间存放页表是比较困难的。为此，可采用将页表再进行分页的方法，使每个页面的大小与内存物理块的大小相同，并为它们进行编号，即依次为0页，1页，…，n页。可以离散地将各个页面分别放在不同的物理块中，同样要为离散分配的页表再建立一张页表，称为外层页表，在每个页表项中记录了页表页面的物理块号，把要使用的页表项调入内存，其余页表项仍在外存，需要时再调入。2.两级页表现代计算机已普遍使用32或64位虚拟地47一、根本原理二、段表具体内容分段存储管理方式六三、地址变换四、分页和分段的主要区别五、段页式存储管理方式一、根本原理二、段表具体内容分段存储管理方式六三、地址变换四48分段存储管理方式的引入，那么主要是为了满足以下一系列的要求。1.便于询问用户在编程时，一般会把自己的作业按照逻辑关系划分为假设干个段，可以通过每段的名字和长度来访问。2.分段共享程序和数据的共享是以信息的逻辑单位为根底的，而段恰好是信息的逻辑单位，因此可知，为了实现段的共享也希望存储管理按段加以组织。3.分段保护信息保护同样是对具有相对完整意义的逻辑单位进行保护，采用按段来组织的方式，对于实现保护功能将更有效和方便。4.动态链接作业要运行前先将主程序对应的目标程序装入内存并启动运行，当运行过程中又需要调用某段时，再将该段〔目标程序〕调入内存并进行链接。分段存储管理方式的引入，那么主要是为了满足以下一系列49一、根本原理1.内存空间划分内存空间被动态地划分为假设干个长度不相等的区域，称为物理段。每个物理段在内存中有一个起始地址，称为段始址。每个物理段内从0开始依次编址，称为段内地址。2.作业空间划分作业的地址空间按逻辑上有完整意义的段来划分，称为逻辑段，简称为段。段的长度由相应的逻辑信息组的长度决定，因而各段长度不等。每个段都有自己的名字。将一个用户作业的所有逻辑段从“0〞开始编号，称为段号。每个段都从“0〞开始编址，称为段内地址。因此，逻辑地址由段号和段内地址两局部组成，如以下图所示。一、根本原理1.内存空间划分内存空间被动态503.内存分配系统以段为单位进行内存分配，为每一个段分配一个连续的内存空间〔物理段〕，逻辑上连续的段在内存中不一定连续存放。3.内存分配系统以段为单位进行内存分配，为每一个段51

二、段表为了使程序能够正常执行，即能从内存中找到每个逻辑段所存储的位置，系统为每个进程建立了一张段映射表，简称“段表〞。例1：一个作业有主程序段MAIN、子程序段X、数据段D和椎栈段S等，在内存的映射情况如图3-17所示。二、段表为了使程序能够正常执行，即能从内存中52

三、地址变换在分段存储管理方式中，根据段表来进行地址转换。为了提高地址的转换速度，可以把段表存放在存放器中，称为段表存放器。段表存放器用来存放段表的始址和段表长度，可以实现作业逻辑地址到物理地址的转换。地址转换过程如以下图所示。是01KB6K1800B4K2600B8K3300B10K段表始址段表长度2100段号段内地址段表寄存器+段号段长段始址段内地址≥段长越界段始址+段内地址段表CPU主存逻辑地址物理地址8292≤≥地址越界否三、地址变换在分段存储管理方式中，根据段表来53例1：某个采用分段存储管理的系统为装入内存的一个作业建立了段表，如下表所示。段号内存起始址段长02219660B13300140B290100B31237580B43959960B〔1〕给出段式地址转换过程；〔2〕计算该作业访问逻辑地址〔0，432〕，〔1，10〕，〔2，500〕，〔3，400〕，〔5，450〕时的物理地址。例1：某个采用分段存储管理的系统为装入内存的一个作业54解析：〔1〕段式地址的转换过程如以下图所示。是段表始址段表长度段号段内地址逻辑地址段表寄存器+段号段长段始址段内地址≥段长否段始址+段内地址CPU主存物理地址0660B22191140B33002100B903580B12374960B3959地址越界≤≥越界段表〔2〕根据地址转换图可知，该作业访问的逻辑地址〔0，432〕，〔1，10〕，〔2，500〕，〔3，400〕，〔5，450〕对应的物理地址如下表所示。逻辑地址物理地址0，43226511，1033102，500段内地址越界3，40016375，450段号越界解析：〔1〕段式地址的转换过程如以下图所示。是段表始址55

四、分页和分段的主要区别分页和分段有许多相似之处，因而容易混淆，但是在概念上两者完全不同，主要表现为：〔1〕页是信息的物理单位，分页仅仅是为了系统管理内存的方便而进行的，而不是用户的需要；而段是信息的逻辑单位，它含有一组具有相对完整意义的信息，是出于用户的需要。〔3〕从用户角度看，分页的作业地址空间是一维的；而分段的作业地址空间是二维的。〔2〕页的大小是固定的，由系统决定；而段的大小是不固定的，由用户作业本身决定。四、分页和分段的主要区别分页和分段有许多相似56

五、段页式存储管理方式1.根本原理段页式存储管理方式的根本原理是段式和页式系统工作原理的组合，即先把用户程序分成假设干个段，并为每个段赋予一个段名，每段可以独立地从“0〞编址，再把每个段划分成大小相等的假设干个页，把内存分成与页大小相同的块。每段分配与其页数相同的内存块，内存块可以连续，也可以不连续。在段页式存储管理中，作业的逻辑地址由段号、段内页号和页内地址组成，如以下图所示。段号段内页号页内地址五、段页式存储管理方式1.根本原理段页式存572.地址变换段页式存储管理的地址转换如以下图所示。是否段表始址段表长度段表寄存器+物理地址越界010004130005260003321006段号页表始址页长段表段号页号页内地址逻辑地址块号块内地址CPU主存越界≤≤段号<段表长度页号>页长页表页号块号否是2.地址变换段页式存储管理的地址转换如以下图所示。583.特点在段页式存储管理方式中，执行一条指令需要3次访问内存。第一次访问段表，从中得到页表的位置，第二次访问页表，得出该页所对应的物理块号，第三次按照得到的物理地址访问内存。段页式存储管理方式既具有段式系统便于实现、分段共享、易于保护、动态链接等一系列优点，又能像页式系统那样很好地解决了内存碎片问题，并为各个分段离散地分配内存。这种管理方式的缺乏是管理信息〔如段表和页表〕需要占用较多的存储空间。3.特点在段页式存储管理方式中，执行一条指令需要359一、根本原理二、分页虚拟存储管理具体内容虚拟存储管理方式七一、根本原理二、分页虚拟存储管理具体内容虚拟存储管理方式七60一、根本原理1.局部性原理在一较短时间内，程序的执行仅局限于某个局部。相应地，它所访问的存储空间也局限于某个区域，即表现在时间和空间两方面。〔1〕时间局部性如果程序中的某条指令被执行后，那么它可能很快会再次被执行；如果某个数据被访问，那么不久以后它可能再次被访问。产生时间局部性的典型原因是在程序中存在着大量的循环操作。〔2〕空间局部性一旦程序访问了某个存储单元，那么与该存储单元相邻的单元可能会很快被访问。其典型情况便是程序的顺序执行。一、根本原理1.局部性原理在一较短时间内，612.虚拟存储器的定义虚拟存储器是指仅把作业的一局部装入内存便可运行作业的存储器系统。具体地说，所谓虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。实际上，用户所看到的大容量只是一种感觉，是虚的，故而得名虚拟存储器。虚拟存储器的容量也不是无限大的，它的最大容量一方面受限于系统中的地址长度，另一方面还受限于系统中所配置的外存容量。虚拟存储器的运行速度接近于内存速度，而其本钱却又接近于外存。可见，虚拟存储技术是一种性能非常优越的存储器管理技术，故被广泛地应用于各类计算机中。2.虚拟存储器的定义虚拟存储器是指仅把作业的一局部623.虚拟存储器的特点采用虚拟存储器具有以下特点：〔1〕离散性：离散性是指在内存分配时采用离散分配方式，这是虚拟存储器的根底。〔2〕屡次性：屡次性是指一个作业被分成屡次调入内存运行。〔3〕对换性：对换性是指允许在作业的运行过程中换进、换出。〔4〕虚拟性：虚拟性是指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。这是虚拟存储器所表现出来的最重要的特征，也是实现虚拟存储器的最重要目标。3.虚拟存储器的特点采用虚拟存储器具有以下特点：634.虚拟存储器的实现方法实现虚拟存储器需要有一定的物质根底。〔1〕要有相当数量的外存，足以存放多个用户程序。〔2〕要有一定容量的内存，因为在处理器上运行的程序必须有一局部信息存放在内存中〔3〕址变换机构，以动态实现逻辑地址到物理地址的变换。常用的虚拟存储器实现方案有分页虚拟存储管理方式、分段虚拟存储管理方式、段页式虚拟存储管理方式。4.虚拟存储器的实现方法实现虚拟存储器需要有一定的64

二、分页虚拟存储管理方式1.根本原理分页式虚拟存储管理方式是在分页系统的根底上，增加了请求调页功能、页面置换功能所形成的虚拟存储器系统。分页虚拟存储管理采用的数据结构和分页存储管理根本相似，主要的数据结构仍然是页表。请求分页系统中的页表结构如下表所示。2.页表页号块号状态位访问字段修改位外存地址在进程装入内存时，并不是装入全部页面，而是装入假设干页，之后根据进程运行的需要，动态装入其他页面；当内存空间已满，而又需要装入新的页面时，那么根据某种算法淘汰某个页面，以便腾出空间，装入新的页面。二、分页虚拟存储管理方式1.根本原理分页式65其中各字段含义如下：〔1〕页号与块号：其定义同分页存储管理，是进行地址变换所必须的。〔2〕状态位〔存在位〕：用于指示该页是否已调入内存，供程序访问时参考。〔3〕访问字段：用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面时参考。〔4〕修改位：表示该页在调入内存后是否被修改正。〔5〕外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时使用。其中各字段含义如下：〔1〕页号与块号：其定义663.缺页中断和地址变换缺页中断作为中断，它同样需要经历诸如保护CPU环境、分析中断原因、转入缺页中断处理程序进行处理、恢复CPU环境等几个步骤。缺页中断的处理过程如以下图所示。操作系统…访问i页…i0j找内存空闲块调入i页j块i页页表作业磁盘i页内存1．查页表6．重新执行2．i页不在主存缺页中断3．到磁盘第j块调第i页5．修改页表，填入块号k4．装入内存第k块3.缺页中断和地址变换缺页中断作为中断，它同样需要经67缺页中断是一种特殊的中断，它与一般的中断相比，有着明显的区别，主要表现为：〔1〕产生中断的时间不一样〔2〕产生中断的次数不一样一般中断是在执行完一条指令后，检查中断请求，产生中断。假设有，便去响应；否那么，继续执行下一条指令。然而，缺页中断是在指令执行期间，发现所要访问的指令或数据不在内存时产生和处理的，即缺页中断是在指令执行过程中产生中断请求。一般中断在执行一条指令后只产生一次中断，而缺页中断在一条指令执行期间就可以产生屡次中断。缺页中断是一种特殊的中断，它与一般的中断相比，有着明684.页面置换算法从理论上讲，应将那些以后不再会访问的页面换出，或把那些在较长时间内不会再访问的页面调出。常用的页面置换算法有以下几种。〔1〕最正确置换算法〔Optimal，OPT〕最正确置换算法是一种理想化的算法。要求从内存中淘汰以后永远不使用的页，假设无这样的页，那么淘汰在最长时间内不再被访问的页。但是人们无法预知一个进程在内存的假设干个页面，哪一个页面是未来最长时间不再被访问的，因此这种算法是无法实现的，只能作为其他置换算法的衡量标准。〔2〕先进先出置换算法〔First-InFirst-Out，FIFO〕该算法是淘汰最早进入内存的那个页面。先进先出置换算法的缺乏是它所依据的理由不是普遍成立的。那些在内存中驻留很久的页，往往是被经常访问的页，如、常用子程序、循环等。4.页面置换算法从理论上讲，应将那些以后不再会访问的69〔3〕最近最久未使用置换算法〔LeastRecentlyUsed，LRU〕该算法选择在最近一段时间内最久没有使用过的页，把它淘汰掉。它依据的是程序局部性原理，即如果某页被访问，它可能马上还要被访问；相反，如果某页长时间未被访问，它可能最近也不会被访问。〔3〕最近最久未使用置换算法〔LeastRecently70一、内存管理二、内存查看和虚拟内存设置具体内容Windows操作系统的存储管理八一、内存管理二、内存查看和虚拟内存设置具体内容Windows71

一、内存管理在WindowsXP/2000中，内存管理是由虚拟存储管理器负责的。WindowsXP/2000利用请求式页面调度算法及簇方式将页面装入内存。每当进程所要访问的页面不在内存时，便产生一次缺页中断，虚拟存储管理器将引发中断的页面及后续的少量页面装入内存。因为局部性原理，程序〔尤其是大型程序〕往往在一段时间内仅在连续的一块地址空间上运行，装入后续少量页面可减少缺页中断的次数。当产生缺页中断时，虚拟存储管理器还必须确定将调入的虚拟页面放在物理内存中的位置。确定最正确位置的算法称为“置换算法〞。如果发生缺页中断时物理内存已满，置换算法还要决定将哪个虚拟页面从物理内存中换出，为新的页面腾出空间。在单处理器系统中，WindowsXP/2000采用类似于最近最久未使用置换算法〔LRU〕。

一、内存管理在WindowsXP/200072

二、内存查看和虚拟内存设置WindowsXP/2000中，可以通过任务管理器查看系统内存的使用情况。启动“Windows任务管理器〞，选择“性能〞选项卡，其中显示了CPU和内存〔包括物理内存和核心内存〕的使用情况，如以下图所示。二、内存查看和虚拟内存设置WindowsX73要想更改分页文件的位置或大小配置参数，可按以下步骤进行：〔1〕右键单击桌面上的“我的电脑〞图标，从弹出的快捷菜单中选择“属性〞，翻开“系统属性〞对话框

〔2〕在“系统属性〞对话框中选择“高级〞选项卡，然后单击“性能〞区中的“设置〞按钮，翻开“性能选项〞对话框，并选择“高级〞选项卡〔3〕在“虚拟内存〞区单击“更改〞按钮，翻开“虚拟内存〞对话框。在该对话框中，更改系统驱动器页面文件的初始大小和最大值，调整其他驱动器现有分页文件的初始大小和最大值，还可以为没有分页文件的驱动器添加分页文件。〔4〕依次单击“确定〞按钮，关闭各对话框，设置生效。要想更改分页文件的位置或大小配置参数，可按以下步骤进74操作系统工程三共分为八个任务操作系统工程三共分为八个任务75工程三存储器管理一二三四存储器管理概述单一连续分配管理方式分区存储管理方式覆盖技术与对换技术五六七八分页存储管理方式分段存储管理方式虚拟存储管理方式Windows操作系统的存储管理工程三存储器管理一二三四存储器管理概述单一连续分配管理76一、存储体系二、存储器管理的主要功能具体内容存储器管理概述一三、地址变换四、各种存储管理方式一、存储体系二、存储器管理的主要功能具体内容存储器管理概述一77

一、存储体系为解决速度和容量之间的矛盾，各种存储设备组成了一个存储体系，如以下图所示。在此存储体系中，包含了少量的速度快、昂贵的高速缓存Cache，中等速度、中等价格的内存RAM，以及容量大、速度慢的磁盘。高速缓存内存外存数据存取速度快存储容量小数据存取速度中等存储容量中等数据存取速度慢存储容量大一、存储体系为解决速度和容量之间的78

二、存储器管理的主要功能1.内存的分配与回收内存空间的分配是指采用一定的数据结构，按照一定的算法为每一道程序分配内存空间，并记录内存空间的使用情况和作业的分配情况。内存空间的回收是指当一个作业运行结束后，必须归还所占用的内存空间，即在记录内存空间使用情况的数据结构中进行修改，并且把记录作业分配情况的数据结构删除。2.地址变换在多道程序环境下，程序的逻辑地址与分配到主存的物理地址是不一致的，而CPU执行指令时是按物理地址进行的，所以要进行地址转换，即将逻辑地址转换为物理地址。3.内存共享所谓内存共享是指两个或多个进程共用内存中相同的区域，这样不仅能使多道程序动态地共享内存，提高内存的利用率，而且还能共享内存中某个区域的信息。二、存储器管理的主要功能1.内存的分配与回收79

4.内存的保护的目的在于为多个进程共享内存提供保障，使内存中的各道程序只能访问它自己的区域，防止各道程序间相互干扰。特别是当一道程序发生错误时，不至于影响其他进程的运行，更要防止破坏系统程序。5.内存的扩充用户在编制程序时，不应该受到内存容量的限制，所以要采用一定的技术来“扩充〞内存的容量，使用户得到比实际内存容量大得多的内存空间。具体实现是在硬件支持下，软件、硬件相互合作，将内存和外存结合起来统一使用。通常是借助虚拟存储技术。4.内存的保护的目的在于为多个进程共享内80

三、地址变换1.逻辑地址用户源程序经过编译后的每个目标模块都以0为基地址顺序编址，这种地址称为逻辑地址，也称为相对地址。2.物理地址在多道程序环境下，程序的逻辑地址与分配到主存的物理地址是不一致的，而CPU执行指令时是按物理地址进行的，所以要进行地址转换，即将逻辑地址转换为物理地址。在多道程序环境下，程序的逻辑地址与分配到内存的物理地址是不一致的，而CPU执行指令时是按物理地址进行的，所以要进行地址变换，即将逻辑地址转换为物理地址〔也称为地址映射或地址重定位〕。三、地址变换1.逻辑地址用户源程序经过编译813.地址变换用户源程序经过编译后的每个目标模块都以0为基地址顺序编址，这种地址称为逻辑地址，也称为相对地址。当用户程序被装入内存时，一次性实现逻辑地址到物理地址的变换，以后不再改变。一般是在装入内存时由重定位装入程序完成。在程序执行过程中需要访问数据时再进行地址变换，即逐条指令执行时完成地址变换。通常情况下，为了提高效率，此工作由硬件地址映射机制来完成。〔1〕静态重定位〔2〕动态重定位与静态重定位相比，动态重定位的优点是显而易见的，因此现代计算机系统中主要采用动态重定位方法。3.地址变换用户源程序经过编译后的每个目标模块都以82对内存的存储管理方式，根据是否把作业全部装入，全部装入后是否分配到一个连续的存储区域，可以分为以下图所示的几种管理方式。存储管理方式部分装入分页式虚拟存储管理段页式虚拟存储管理分段式虚拟存储管理全部装入连续分配单一连续分配分页存储管理分段存储管理段页式存储管理离散分配分区分配固定分区存储管理可变分区存储管理

四、各种存储管理方式对内存的存储管理方式，根据是否把作业全部装入，全部装83一、根本原理二、内存空间的分配具体内容单一连续分配管理方式二三、地址变换与存储保护一、根本原理二、内存空间的分配具体内容单一连续分配管理方式二84采用单用户存储管理方式具有以下特点：一、根本原理在单用户连续存储管理方式下，内存中仅驻留一道程序，整个用户区被一用户独占.在这种管理方式下，存储器利用率极低，仅能用于单用户单任务的操作系统，不能用于多用户系统和单用户多任务系统中。管理简单。它把内存分为两个区，用户区一次只能装入一个完整的作业，且占用一个连续的存储空间。它需要很少的软硬件支持，且便于用户了解和使用。资源利用率低。不管用户区有多大，它一次只能装入一个作业，这样造成了存储空间的浪费，使系统整体资源利用率不高。在内存中的作业不必考虑移动的问题，并且内存的回收不需要任何操作。这种分配方式不支持虚拟存储器的实现。采用单用户存储管理方式具有以下特点：一、根本85

二、内存空间的分配在单一连续分配存储管理方式下，任何时刻内存中最多只有一个作业，适合于单道运行的计算机系统。采用这种存储管理方式时，内存分为两个分区：1.系统区系统区是仅提供给操作系统使用的内存区，通常驻留在内存的低地址局部。用户区是指除系统区以外的内存空间，提供给用户使用。2.用户区等待装入内存的作业排成一个作业队列，当内存中无作业或一个作业执行结束，允许作业队列中的一个作业装入内存。其分配过程是：首先，从作业队列中取出队首作业；判断作业的大小是否大于用户区的大小，假设大于那么作业不能装入，否那么可以把作业装入用户区。它一次只能装入一个作业。二、内存空间的分配在单一连续分配存储管理方式86

三、地址变换与存储保护1.地址变换采用单一连续分配管理方式时，处理器设置两个存放器：界限存放器和基地址存放器。界限存放器用来存放内存用户区的长度，基地址存放器用来存放用户区的起始地址。一般情况下，这两个存放器的内容是不变的，只有当操作系统占有的存储区域改变时才会改变。处理器≥+主存界限寄存器基地址寄存器逻辑地址物理地址否是地址越界长度基址其转换过程如以下图所示。三、地址变换与存储保护1.地址变换采用单一87

2.存储保护单用户连续存储管理方式下，处理器在执行指令时，通过比较逻辑地址和界限存放器的值，来控制产生“地址越界〞中断信号，以到达存储保护的目的。在硬件方面，常见的几种单用户操作系统中，如CP/M，MS-DOS及RT-11等，都未设置存储器保护设施。主要原因在于：内存由用户独占，不可能存在受其他用户程序干扰的问题；用户程序也很容易通过系统的再启动而重新装入内存。可能出现的破坏行为也只是由用户程序自己去破坏操作系统，其后果并不严重，只是影响该用户程序的运行；2.存储保护单用户连续存储管理方式下，处88一、固定分区存储管理方式二、可变分区存储管理方式具体内容分区存储管理方式三三、紧凑技术一、固定分区存储管理方式二、可变分区存储管理方式具体内容分区89

一、固定分区存储管理方式1.根本原理固定分区是指系统预先把内存中的用户区划分成假设干个固定大小的连续区域。每一个区域称为一个分区，每个分区可以装入一个作业，一个作业也只能装入一个分区中，这样就可以装入多个作业，使它们并发执行。2.分区分配表在固定分区存储管理方式下，为了记录各个分区的使用情况，方便内存空间的分配与回收操作，通常要为分区建立一张表，如以下图所示。分区的划分方式有以下两种：〔1〕分区大小相等〔2〕分区大小不等一、固定分区存储管理方式1.根本原理固定分90区号大小起始地址状态18KB16KBJ1216KB24KB0332KB40KBJ2464KB72KB0…………固定分区分配表因为在作业装入之前，主存中的分区大小和个数已经确定，也就是说分区分配表的记录个数是确定的。所以，分区分配表一般采用顺序存储方式，即用数组存储。内存空间016KB24KB40KB72KB136KB操作系统区作业J1作业J2区号大小起始地址状态18KB16KBJ1216KB24KB0913.地址变换由于固定分区方式是预先把内存划分成假设干个区，每个分区只能放一个作业，因此作业在执行过程中不会改变分区的个数和大小。所以，地址转换采用静态重定位方式，即在作业被装入内存时，一次性地完成地址变换。地址转换过程是：CPU获得的逻辑地址首先与下限存放器的值相加，产生物理地址；然后与上限存放器的值比较：假设大于上限存放器的值，产生“地址越界〞中断信号，由相应的中断处理程序处理；假设不大于上限存放器的值，那么该物理地址就是合法地址，它对应于内存中的一个存储单元。3.地址变换由于固定分区方式是预先把内存划分成假设92例1：在某系统中采用固定分区分配管理方式，内存分区情况如左图所示。现有大小为1KB，9KB，33KB，121KB的多个作业要求进入内存，试画出它们进入内存后的空间分配情况，并说明内存浪费有多大？解析：采用固定分区存储管理方式，作业进入系统后的分配情况如右图所示，内存浪费512KB-20KB-(1KB+9KB+33KB+121KB)=328KB。例1：在某系统中采用固定分区分配管理方式，内存分区情93

二、可变分区存储管理方式可变分区是指系统不预先划分固定区域，而是在作业装入时根据作业的实际需要动态地划分内存空间。1.根本原理系统在作业装入内存执行之前并不建立分区，当要装入一个作业时，根据作业需要的内存量查看内存中是否有足够的空间：假设有，那么按需要量分割一个分区分配给该作业；假设无，那么令该作业等待内存空间。由于分区的大小是按作业的实际需要量来定的，且分区的个数也是随机的，所以可以克服固定分区方式中的内存空间的浪费，有利于多道程序设计，实现了多个作业对内存的共享，进一步提高了内存资源利用率。二、可变分区存储管理方式可变分区是指系统不预94随着作业的装入、撤离，内存空间被分成许多个分区。当一个新的作业要求装入时，必须找一个足够大的空闲区，如果找到的空闲区大于作业需要量，那么作业装入后又把原来的空闲区分成两局部，一局部被作业占用了，而另一局部又分成为一个较小的空闲区。当一个作业运行结束撤离时，它归还的区域如果与其他空闲区相邻，那么可合成一个较大的空闲区，如以下图所示。随着作业的装入、撤离，内存空间被分成许多个分区。当一952.采用的数据结构在可变分区存储管理方式中，内存中分区的数目和大小随作业的执行而不断改变。为了实现分区分配，系统中必须配置相应的数据结构，用来记录内存的使用情况，包括空闲分区的情况和已用分区的情况。为此，系统设置了两个表，即已用分区表和空闲分区表。〔1〕已用分区表记录当前已经分配给用户作业的内存分区，包括分区序号、分区大小、起始地址和状态。〔2〕空闲分区表记录当前内存中空闲分区的情况，包括空闲分区序号、分区大小、起始地址和状态。因为已用分区表和空闲分区表中记录的个数是随着内存的分配与回收而变化的，所以这两个表一般采用链表的形式存储，链表中的数据域记录相关的信息。2.采用的数据结构在可变分区存储管理方式中，内存中963.分区分配算法〔1〕首次适应算法〔FF〕首次适应算法也叫最先适应算法，要求空闲分区表中的记录按地址递增的顺序排列。每次分配时，总是顺序查找空闲分区表，找到第一个能满足长度要求的空闲分区。分割这个空闲分区，一局部分配给作业，另一局部仍为空闲分区。优点：优先利用内存中低址局部的空闲分区，在高址局部的空闲区很少被利用，从而保存了高址局部的大空闲区，为以后到达大作业分配大的内存空间创造了条件。缺点：低址局部不断被划分，致使留下许多难以利用的很小的空闲分区，即内存“碎片〞。而每次查找又都是从低址局部开始，这无疑增加了查找可用空闲分区的开销。3.分区分配算法〔1〕首次适应算法〔FF〕首次适应97〔2〕循环首次适应算法该算法要求空闲分区表的记录仍然按地址递增的顺序排列。每次分配时，是从上次分配的空闲区的下一条记录开始顺序查找空闲分区表，最后一条记录不能满足要求时，再从第1条记录开始比较，找到第一个能满足作业长度要求的空闲分区，分割这个空闲分区，装入作业。否那么作业不能装入。

优点：能使内存中的空闲分区分布得更均匀，减少查找空闲分区的开销。缺点：缺乏大的空闲分区。〔2〕循环首次适应算法该算法要求空闲分区表的记录仍然98〔3〕最正确适应算法〔BF〕最正确适应算法也叫最优适应算法，要求把空闲分区按长度递增次序登记在空闲分区表中。每次分配时，可以从所有的空闲分区中挑选一个能满足作业要求的最小空闲区进行分配。这样可以保证不去分割一个更大的空闲区，使装入大作业时比较容易得到满足。

优点：解决了大作业的分配问题。缺点：容易产生内存碎片，如果找出的分区正好满足要求，那么是最适宜的了；如果比所要求的略大，那么分割后使剩下的空闲区就很小，以致无法使用。另外，按这种方法，在回收一个分区时也必须对分配表或链表重新排列，这样就增加了系统开销。〔3〕最正确适应算法〔BF〕最正确适应算法也叫最优适99〔4〕最差适应算法〔WF〕最差适应算法也叫最坏适应算法，要求把空闲区按长度递减的次序登记在空闲分区表中。每次分配时，总是挑选一个最大的空闲区，分割一局部给作业使用，使剩下的局部不至于太小而成为内存碎片。

优点：不会产生过多的碎片。缺点：影响大作业的分配。另外，由于收回内存时要按长度递减的顺序插入到空闲分区表中，因而增加了系统开销。〔4〕最差适应算法〔WF〕最差适应算法也叫最坏适应算100首次适应算法的另一个优点是尽可能地利用了低地址空间，从而保证高地址有较大的空闲区来放置较大的作业。最差适应算法由于过多地分割大的空闲区，当遇到较大作业申请时，很可能无法满足其申请，该算法对中、小作业比较有利。因此，在实际系统中，首次适应算法用得最多。从搜索速度和回收过程上看，首次适应算法具有最正确性能；在空间利用上，首次适应算法比最正确适应算法好，最正确适应算法又比最差适应算法好；最正确适应算法找到的空闲区是最正确的，但在某些情况下，不一定能提高内存的利用率。比较与总结首次适应算法的另一个优点是尽可能地利用了低地址空间，1014.分区的回收〔1〕回收的分区前后没有相邻的空闲分区当一个作业运行结束后，在已用分区表中找到该作业，根据该作业所占内存的始址和大小，去修改空闲分区表相应的记录。其修改情况分为四种在空闲分区表中要增加一条记录，该记录的始址和大小即为回收分区的始址和大小。〔2〕回收分区的前面有相邻的空闲区在空闲分区表中找到这个空闲分区〔查找的方法是比较空闲分区的始址＋空闲分区的大小与回收分区的始址是否相等〕，修改这个空闲分区的大小，即加上回收分区的大小，始址不变。4.分区的回收〔1〕回收的分区前后没有相邻的空闲分区102〔3〕回收分区的后面有相邻的空闲区在空闲分区表中找到这个空闲分区〔查找的方法是回收分区的始址＋回收分区的大小与空闲分区的始址比较是否相等〕，修改这个空闲分区的始址和大小。始址为回收分区的始址，大小为回收分区的大小与空闲分区的大小之和。〔4〕回收分区的前后都有相邻的空闲区在空闲分区表中找到这两个空闲分区，修改前面相邻的空闲区的大小，其始址不变。大小改为相邻两个空闲分区和回收分区的大小之和，然后从空闲分区表中删除后一个相邻空闲分区的记录。〔3〕回收分区的后面有相邻的空闲区在空闲分区表中找到103例1：内存有两个空闲区F1，F2，如图1所示。F1为220KB，F2为120KB，另外依次有J1，J2，J3三个作业请求加载运行，它们的内存需求量分别是40KB，160KB，100KB，试比较首次适应算法、最正确适应算法和最差适应算法的性能。解析：在首次适应算法和最差适应算法中可以给所有作业分配空间，在最正确适应算法中，还有作业J3不能分配，如图2所示。

图1

图2例1：内存有两个空闲区F1，F2，如图1所示。F1为1044.地址变换与存储保护〔1〕地址变换可变分区存储管理方式一般采用动态重定位方式装入作业。地址转换过程如下：①当作业占用处理器时，进程调度把该作业所占分区的起始地址送入基址存放器，把作业所占分区的最大地址送入限长存放器。③当取出一条指令后，把该指令中的逻辑地址与基址存放器内容相加得到物理地址，该物理地址必须满足：物理地址<=限长存放器的值。此时允许指令访问内存单元的地址，否那么产生“地址越界〞中断，不允许访问。②作业执行过程中，处理器每执行一条指令，都要由硬件的地址转换机构把逻辑地址转换成物理地址。4.地址变换与存储保护〔1〕地址变换可变分区存储管105〔2〕存储保护系统设置了一对存放器，称为“基址存放器〞和“限长存放器〞，用它记录当前在CPU中运行作业在内存中所占分区的始址和末址。当处理器执行该作业的指令时必须核对表达式“始址<=绝对地址<=末址〞是否成立。假设成立，就执行该指令，否那么就产生“地址越界〞中断信号，停止执行该指令。运行的作业在让出处理器时，调度程序选择另一个可运行的作业，同时修改当前运行作业的分区号和基址存放器、限长存放器的内容，以保证处理器能控制作业在所在的分区内正常运行。〔2〕存储保护系统设置了一对存放器，称为“基址存放器106

三、紧凑技术为了解决碎片问题，可采用的一种方法是，将内存中的所有作业进行