第4章存储管理

第4章存储管理

在计算机系统中，内存是关键资源，对内存如何处理在很大程度上将影响整个系统的性能。存储管理目前仍是人们研究操作系统的中心问题之一，甚至操作系统的命名也往往取决于存储管理的策略。学习目标1、掌握：动态分区法，分页的概念和地址映射，分段的概念；请求分页存储管理技术，常用页面置换算法。

2、理解：重定位、固定分区法，碎片和抖动。3、了解：存储器层次；用户程序地址空间；程序的装入方式。本章要点●连续分配存储管理方式

●段式存储管理

●页式存储管理

●虚拟页式存储管理

第4章基本存储管理4.1地址空间与重定位内存（MainMemory或PrimaryMemory或RealMemory）也称主存，是指CPU能直接存取指令和数据的存储器。内存在计算机系统中的地位4.1.1用户程序的地址空间1．存储器的层次2．用户程序的地址空间■主要处理阶段

编辑编译连接装入运行■有关概念●装入程序——其功能是将程序模块放入内存，并进行重定位。●相对地址或逻辑地址

●绝对地址或物理地址2．用户程序的地址空间■程序装入内存的方式

①绝对装入方式②可重定位装入方式③动态运行时装入方式4.1.2重定位概念逻辑地址空间（简称地址空间）

由程序中逻辑地址组成的地址范围。内存空间（也称物理空间或绝对空间）由内存中一系列存储单元所限定的地址范围。重定位程序和数据装入内存时，需对目标程序中的地址进行修改。这种把逻辑地址转变为内存物理地址的过程称作重定位。重定位方式(1)

静态重定位(2)动态重定位1．静态重定位：目标程序装入内存时进行地址变换程序装入内存时的情况

静态重定位示意图

1．静态重定位

目标程序装入内存时进行地址变换。▲优点：无需增加硬件地址转换机构。●主要缺点：位置“钉死”；不便共享。2．动态重定位：程序执行期间进行重定位●主要优点：位置可变，不必连续；易于共享。▲主要缺点：需要附加硬件支持。4.1.3对换技术对换两个进程示意图

4.1.3对换技术早期的对换技术用于单用户系统。

●主要优点：利用外存来解决内存不足的问题。

▲主要缺点：效率很低；不能保证充分利用内存。在多道程序环境中也采用对换技术！4.2分区管理技术4.2.1分区法分区分配是为支持多道程序运行而设计的一种最简单的存储管理方式。1．固定分区法分区个数固定不变，各个分区的大小固定不变，不同分区的大小可以不同。系统建立一张分区说明表。每个分区对应表中的一项。各表项包含每个分区的起始地址、分区大小以及状态（是否正被使用）。▲分区的申请和释放

（1）单一分区存储管理

单一分区存储管理的系统，任何时刻只有一个用户程序驻留内存。因此内存为两个部分。☆供操作系统使用的系统区;☆供用户程序使用的用户区。

(2)用户区分为“使用区”和“空闲区”两部分。使用区是用户作业程序真正占用的连续存储区域；空闲区是分配给了用户、但未被用户使用的区域，称为“内部碎片”。

单一分区存储管理系统的特点：(1)总是把一个连续的用户区分配给一个用户使用。

(3)这种系统只适用于单用户的情况。单一分区存储管理系统的特点：(4)进入内存的作业，独享系统中的所有资源，包括内存中的整个用户区。(5)由于整个用户区都分配给了一个用户，因此作业程序进入用户区后，没有移动的必要。所以采用这种存储管理策略，对用户程序实行静态重定位。单一分区存储管理系统的存储保护

实行静态重定位，不能阻止用户有意无意地通过不恰当的指令闯入操作系统所占用的存储区域。

在单一分区存储管理中，为有效阻止用户程序指令中的地址闯入操作系统所占用的区域，在CPU中会设置一个用于存储保护的专用寄存器——“界限寄存器”。

界限寄存器：存放内存用户区的起始地址。CPU在用户态下工作时，对内存的每一次访问，都要将所访问的地址与界限寄存器中的内容进行比较。一旦发现所访问的地址小于界限寄存器中的地址，产生“地址越界”中断，阻止这次访问的进行。(1)每次只能有一个作业进入内存，故不适用于多道程序设计，整个系统的工作效率不高，资源利用率低下；单一分区存储管理的缺点：(2)只要作业比用户区小，那么在用户区里就会形成碎片，如果用户作业很小，那么这种浪费是巨大的；(3)若用户作业的相对地址空间比用户区大，那么该作业就无法投入运行，因为大作业无法在小内存上运行。（2）固定分区存储管理

系统初启时将内存划分成n个分区（尺寸大小可以不等），系统运行过程中，分区的个数及尺寸保持不变，每个分区里只装入一个作业运行。这就是“固定分区”存储管理。对作业的组织

系统可以为每个分区设置一个后备作业队列，形成多队列的管理方式：对作业的组织

对作业的组织

也可采用多个分区只设置一个后备作业队列的办法。在固定分区存储管理中，每个分区只允许装入一个作业，作业在运行期间不会移动。因此，这时应该对程序实行静态重定位。在固定分区存储管理中，要防止用户程序对操作系统形成的侵扰，也要防止用户程序与用户程序之间形成的侵扰。因此必须在CPU中设置一对专用的寄存器，用于实现存储保护。固定分区管理的地址映射和存储保护

两个专用寄存器起名为“基址寄存器”和“界限寄存器”。调度程序调度某个作业运行时，就把该作业所在分区的起始地址装入基址寄存器，把分区长度装入界限寄存器。

固定分区存储管理的特点：它是最简单的、具有“多道”色彩的存储管理方案。

作业程序将一次性地全部被装入到分配给它的连续分区里。(3)实行静态重定位，在分区内的程序不能随意移动，否则运行就会出错。(4)每个分区都有可能产生内部碎片，引起内存资源的浪费。(5)如果到达作业的尺寸比任何一个分区的长度都大，那么它就无法运行。固定分区管理示意图

分区说明表

分区的管理动态分区存储管理的基本思想

动态分区存储管理的基本思想是：作业要求装入内存时，若内存有足够的连续存储空间供使用，那就依作业相对地址空间的大小，划分出一个分区分配给它。2．动态分区法图（a）表明后备作业队列里，作业A需要内存15KB，作业B需要20KB，作业C需要10KB，等等。图（b）表示系统初启时的情形，整个系统里没有作业运行，用户区空闲。图（c）表示作业A装入内存时，为它划分了尺寸为15KB的分区。用户区被分成两个分区，一个是已分配的，一个是空闲区。图（d）表示作业B装入内存时，为它划分了尺寸为20KB的分区，此时的用户区被分成了三个分区；图（e）表示作业C装入内存时，为它划分了一个尺寸为10KB的分区，此时的用户区被分成了四个分区。⑴动态分区的分配随着作业对存储区域的不断申请与释放，发展趋势是：分区的数目会逐渐增加，有的分区尺寸在逐渐减小，甚至有可能出现内存里有空闲区、但每个都满足不了作业程序的要求而无法分配出去的情形。在存储管理中，把那些无法满足作业存储请求的空闲区称为“外部碎片”。动态分区存储管理模式引发了许多新的问题。只有解决这些问题，动态分区存储管理才能付之以实现。实行动态分区存储管理必须解决的问题：

(1)采用地址动态重定位技术，使程序能在内存中移动，为空闲区的合并提供保证。(2)

记住各个分区的使用情况，当一个分区被释放时，能方便地判定它的前、后分区是否为空闲区。若是空闲区，就进行合并，形成一个大的空闲区。

(3)给出分区分配算法。●动态分区的优点

管理方式简单，所需操作系统软件和处理开销都小。▲动态分区的缺点

①内存空间利用率不高，碎片严重；②活动进程数目受限；③无法预知所需内存大小。动态分区法举例动态分区法举例（2）数据结构常用的数据结构形式有以下两种：

①空闲分区表⑵数据结构②空闲分区链：使用链指针把所有的空闲分区链接成一条链。（3）动态分区管理中空闲区的合并

内存中一个分区被释放时，与它前后相邻接的分区会有四种关系，如图所示。约定：位于一个分区左边的分区，称为它的“后邻接”分区，位于一个分区右边的分区，称为它的“前邻接”分区。（3）动态分区管理中空闲区的合并

图(a)表示释放区的前、后邻接分区都是使用区，不存在合并问题。此时释放区形成一个新空闲区，该空闲区的起址就是该释放区的起址，长度就是该释放区的长度。

图(b)表示释放区的前邻接分区是空闲区，后邻接分区是使用区，释放区应和前邻接的空闲区合并成新的空闲区，它的起址是该释放区的起址，长度是这两个合并分区的长度之和。

图(c)表示释放区的前邻接分区是使用区，后邻接分区是空闲区，释放区应和后邻接的空闲区合并成为新的空闲区，它的起址是原前邻接空闲区的起址，长度是这两个合并分区的长度之和。

图(d)表示释放区的前、后邻接分区都是空闲区，释放区应该和这两个邻接的空闲区合并成新的空闲区，它的起址是原后邻接空闲区的起址，长度是这三个合并分区的长度之和。（4）分配算法①最先适应算法（First-fit）空闲表是按地址排列的（即空闲块地址小的，在表中的序号也小）。②最佳适应算法（Best-fit）空闲表是以空闲分区的大小为序、按增量形式排列的，即小块在前，大块在后。（4）分配算法③循环适应算法（Next-fit）最先适应算法的变种。它不从空闲表的开头查找，而从上次找到的可用分区的下一个空闲分区开始查找，从中选择满足大小要求的第一个空闲分区。④最坏适应算法（Worst-fit）空闲表是以空闲块的大小为序，且大块在前、小块在后。

（5）硬件支持通常用一对寄存器分别表示用户进程在内存空间的上界地址值和下界地址值。这对寄存器是所有用户进程共用的。（6）碎片“碎片”或“零头”：内存中这种容量太小、无法利用的小分区。内部碎片：在一个分区内部出现的碎片（即被浪费的空间），如固定分区法会产生内部碎片。外部碎片：在所有分区之外新增的碎片。（7）总结分区分配的优缺点

●主要优点：有利于多道程序设计，所需硬件支持很少，管理算法简单，易于实现。

▲主要缺点：碎片问题严重，内存利用率低，不利于大作业运行，作业大小受内存总量限制。作业一次性地全部装入到内存中；固定分区实行指令地址的静态重定位；动态分区实行指令地址的动态重定位；

4.2.2可重定位分区分配■紧缩（或拼凑）——移动某些已分配区的内容，使所有进程的分区紧挨在一起，而把空闲区留在另一端。■可重定位分区法动态重定位经常是用硬件实现的。紧缩时机 ●释放所占分区时 ●分配进程分区时

动态重定位分区分配算法

址可重定位分区分配中的进程移动■动态重定位的实现过程动态重定位经常用硬件实现硬件支持

基址寄存器（下界地址值）限长寄存器（上界地址值=下界+长度）■动态重定位的实现过程■可重定位分区法的优缺点●优点

可以消除碎片，能够分配更多的分区，有助于多道程序设计，提高内存的利用率。▲缺点

◎紧缩花费了大量CPU时间；

◎当进程大于整个空闲区时，仍要浪费一定的内存；

◎进程的存储区内可能放有从未使用的信息；

◎进程之间无法对信息共享。4.3分页技术4.3.1分页的基本概念■分页存储管理的基本方法

①逻辑空间分页——若干大小相等的页面。②内存空间分块——又称内存块或页框，由硬件（系统）确定。③逻辑地址表示。

④内存分配原则

⑤设立页表

⑥建立内存块表4.3.1分页的基本概念分页技术的地址结构示意图

▲给定的逻辑地址是A，页面的大小为L，则页号p和页内地址d可按下式求得：

p=INT(A/L),

d=AMODL式中，INT是向下整除的函数，MOD是取余函数。

④内存分配原则

▲以块为单位；▲每个页面对应一个内存块；▲分配的内存块可不连续。分页存储管理系统示意图

⑤设立页表——系统为每个进程设立一张页面映像表，简称页表

●实现从页号到物理块号的地址映射⑥建立内存块表整个系统有一个内存块表。每个内存块在内存块表中占一项，表明该块当前空闲还是已分出去了。内存页帧使用情况图(a)内存块表图(b)4.3.2分页系统中的地址映射分页系统的地址转换机构▲每个进程平均有半个页面的内部碎片。4.3.3页的共享和保护页面共享共享的方法是使这些相关进程的逻辑空间中的页指向相同的内存块（该块中放有共享程序或数据）

★在分页系统中实现页的共享比较困难！2.页面保护（1）利用页表本身进行保护；（2）设置存取控制位；（3）设置合法标志。4.3.4页表的构造1．多级页表

大多数现代计算机系统都支持非常大的逻辑地址空间，如232～264。在这种情况下，只用一级页表会使页表变得非常大。一种方法是利用两级页表，即把页表本身也分页。

两级页表地址结构示意图两级页表结构示意图

两级页表结构的地址转换2．散列页表（HashedPageTable）以页号作为参数形成散列值。散列表中每一项有一个链表，它把有相同散列值的元素链接起来。每个链表元素由三部分组成：①页号；②对应的内存块号；③指向链表中下一个元素的指针。散列页表构成及地址转换过程

2．散列页表（HashedPageTable）3．倒置页表它是按内存块号排序的，每个内存块占有一个表项。每个表项包括存放在该内存块中页面的虚拟页号和拥有该页面的进程标识符。倒置页表构成及地址转换过程

4.4分段技术4.4.1分段的基本概念分段地址空间1．分段▲段是一组逻辑信息的集合。▲每段都有自己的名字、长度和▲段号。2．程序的地址结构逻辑地址要用两个成分来表示：

段号：s和段内地址：d进程的逻辑地址空间是二维的。分段技术地址结构示意图

4.4.1分段的基本概念3．段表和段表地址寄存器系统为每个进程建立一个段映射表，简称“段表”。每个段在段表中占有一项，段表项中包含段号、段长和段起始地址（又称“基址”）等。系统还要建立一个段表地址寄存器。有两部分：●该段表在内存的起始地址

●该段表的长度。4.4.1分段的基本概念4．分页和分段的主要区别①页是信息的物理单位；

段是信息的逻辑单位。②页的大小是由系统确定的；

段的长度因段而异。③分页的进程地址空间是一维的；

分段的进程地址空间是二维的。④分页系统很难实现过程和数据的分离；

分段系统却可以很容易实现这些功能。4.4.2分段系统中的地址映射分段地址转换过程

分段地址转换过程

4.4.3段的共享和保护1．段的共享共享是在段一级实现的，任何共享信息可以单独成为一段。也可以只共享部分程序。2．段的保护段的保护措施包括以下三种：①存取控制②段表本身可起保护作用

●表项中设置该段的长度限制；

●段表地址寄存器中有段表长度的信息；③保护环2．段的保护段的保护措施包括以下三种：③保护环一个程序可以访问驻留在相同环或较低特权环中的数据。一个程序可以调用驻留在相同环或较高特权环中的服务。环保护机构

4.5虚拟存储管理4.5.1虚拟存储器的概念▲进程在执行之前要全部装入内存，这种限制是不合理的。

①程序中往往含有不会被执行的代码；②分配的内存空间会大于它们的实际需要；③一个程序的某些选项和特性可能很少使用。程序的执行过程也显示出局部性。按需分别调入内存会带来两点好处：①用户编制程序时不必考虑内存容量的限制；②在一定容量的内存中就可同时装入更多的进程。虚拟存储器（VirtualMemory）

●用户能作为可编址内存对待的虚拟存储空间，它使用户逻辑存储器与物理存储器分离，是操作系统给用户提供的一个比真实内存空间大得多的地址空间。实现虚拟存储技术的物质基础

●二级存储器结构；

●动态地址转换机构（DAT）。虚拟存储器实质上是把用户地址空间和实际的存储空间区分开来。它主要受到两方面的限制

①指令中表示地址的字长②外存的容量。4.5.2虚拟存储器的特征①虚拟扩充；②部分装入；③离散分配；④多次对换。

4.6请求分页技术4.6.1请求分页的基本思想是在单纯分页技术基础上发展起来的。二者的根本区别在于请求分页提供虚拟存储器。★基本思想：当一个进程的部分页面在内存时就可调度它运行；在运行过程中若用到的页面尚未在内存，则把它们动态换入内存。▲如果地址转换机构遇到一个具有“N”状态的页表项时，便产生一个缺页中断。4.6.2硬件支持及缺页处理1．页表机制★页表项不仅要包含该页在内存的基址，还含有下列信息：

①每一项增加一个状态位，指示该页面是否在内存中。②还要记载该页面在外存的地址（又称文件地址）。③在页表中还要增加一些位，记录该页的使用情况。页表项通常包含下列信息：典型的页表表项示意图

页号物理块号状态位P访问字段A修改位M外存地址2．缺页中断机构指令执行步骤与缺页中断处理过程

3．页面置换过程

▲实现请求分页必须解决内存块的分配算法和页面置换算法两个主要问题。主要包括以下4个步骤：①找出所需页面在磁盘上的位置。②找出一个空闲内存块。③把所需页面读入内存块（刚刚得到的空闲块），修改页表和存储块表。④重新启动该用户进程。页面置换流程示例

4．具有快表的地址转换机构在内存中放置页表也带来存取速度下降的矛盾。快表（或TranslationLookasideBuffer,TLB）：专用的、高速小容量的联想存储器。快表每项包括键号和值两部分。程序局部化：一个程序在一段时间内总是相对集中在一个有限地址空间的某个区域中执行。

4．具有快表的地址转换机构请求分页中的地址变换过程

4.6.3页面置换算法1．有效存取时间和页面走向⑴有效存取时间缺页率p：表示缺页中断的概率（0≤p≤1）

等于缺页次数与全部访问内存次数之比有效存取时间可表示为：

有效存取时间=(1-p)×ma+p×缺页处理时间▲缺页中断处理所花费的时间主要有以下三部分：①处理缺页中断的时间。②调入该页的时间。③重新启动该进程的时间。▲将页面从盘上读到内存所花费的时间包括：

●磁盘寻道时间（即磁头从当前磁道移至指定磁道所用的时间）

●旋转延迟时间（即磁头从当前位置落到指定扇区开头所用的时间）

●数据传输时间典型磁盘的旋转延迟时间约为8ms，寻道时间约为15ms，传输时间是1ms。⑵页面走向抖动频繁地更换页面,以致系统的大部分时间花费在页面的调度和传输上。

尽量避免系统“抖动”。存储访问序列也叫页面走向

①对于给定的页面大小，仅考虑其页号，不关心完整的地址。②如果当前对页面p进行了访问，那么，马上又对该页访问就不会缺页。这样连续出现的同一页号就简化为一个页号。⑵页面走向存储访问序列也叫页面走向▲如下地址序列（用十进制数表示）：

0100，0432，0101，0612，0102，0103，0104，0101，0611，0102，0103，0104，0101，0610，0102，0103，0104，0101，0609，0102，0105

若每页100个字节，则页面走向简化为：1，4，1，6，1，6，1，6，1，6，1一般，随着可用块数的增加，缺页数将减少。缺页量与内存块数关系图▲统一采用下述页面走向：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1并且，假定每个作业只有三个内存块可供使用。2．常用的页面置换算法⑴先进先出总是淘汰在内存中停留时间最长（年龄最老）的一页，即先进入内存的页，先被换出。FIFO页面置换序列

▲总共有15次缺页！2．常用的页面置换算法⑴先进先出●优点：容易理解，方便程序设计。▲缺点：性能并不很好，效率不高；存在Belady异常现象，即缺页率随内存块增加而增加。⑵最佳置换法最佳置换算法（OptimalReplacement,OPT）其实质是：为调入新页面而必须预先淘汰某个老页面时，所选择的老页面应在将来不被使用，或者是在最远的将来才被访问。▲保证有最小缺页率！

▲OPT算法在实现上有困难！最佳页面置换序列仅出现9次缺页中断！

⑶最近最少使用置换法以“最近的过去”作为“不久将来”的近似，把最近最长一段时间里不曾使用的页面淘汰掉。实质是：当需要置换一页时，选择在最近一段时间里最久没有使用过的页面予以淘汰。最近最少使用算法页面置换序列

▲产生12次缺页！LRU算法需要实际硬件的支持。实现时的问题是：怎样确定最后访问以来所经历时间的顺序。有以下两种可行的办法：①计数器②栈。利用栈记录目前访问最多的页面示例

⑷最近未使用置换法最近未使用（NotRecentlyUsed，NRU）算法是LRU算法的近似方法。

不(5)Clock置换算法(6)改进型Clock置换算法

由访问位A和修改位M可以组合成下面四种类型的页面：1类(A=0,M=0):表示该页最近既未被访问，又未被修改，是最佳淘汰页。2类(A=0,M=1):表示该页最近未被访问，但已被修改，并不是很好的淘汰页。3类(A=1,M=0)：最近已被访问，但未被修改，该页有可能再被访问。4类(A=1,M=1):最近已被访问且被修改，该页可能再被访问。(6)改进型Clock置换算法

由访问位A和修改位M可以组合成下面四种类型的页面,其执行过程可分成以下三步：(1)从当前位置开始扫描循环队列，寻找A=0且M=0的页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。(2)如果查找一周后未遇到第一类页面，则开始第二轮扫描，寻找A=0且M=1的页面，将遇到的第一个这类页面作为淘汰页。将所有扫描过的页面的访问位都置0。(3)如果第二步也失败，则将指针返回到开始的位置，并将所有的访问位复0。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。4.7内存块分配和抖动问题4.7.1内存块分配

1．最少内存块数分给每个进程的最少内存块数是指保证进程正常运行所需的最少内存块数，它是由指令集结构决定的。2．内存块的分配

①固定分配策略分配给进程的内存块数是固定的，且在最初装入时（即进程创建时）确定块数。②可变分配策略允许分给进程的内存块数随进程的活动而改变。3.页面置换范围

●全局置换允许一个进程从全体存储块的集合中选取淘汰块，尽管该块当前分配给其他进程，还是能强行占用。●局部置换是每个进程只能从分给它的一组内存块中选择淘汰块。■局部置换可与固定分配策略相结合；■局部置换可与可变分配策略相结合；

■全局置换只能与可变分配策略相结合。

4．分配算法（1）等分法——内存块按进程平分。

（2）比例法设进程pi的地址空间大小为si，则总地址空间为：

S=∑si若可用块的总数是m，则分给进程pi的块数是：

ai

≈m.si

/S（3）优先权法——给高优先级进程分配较多内存。

4.7.2抖动问题■整个系统的页面替换非常频繁，以致大部分机器时间都用在来回进行的页面调度上，只有一小部分时间用于进程的实际运算。这种局面称为系统“抖动（Thrashing）”。1．产生抖动的原因▲内存不足；▲多道程序度高；▲CPU的利用率太低。

CPU利用率与多道程序度之间的关系2．防止抖动的方法

①采用局部置换策略②利用工作集策略防止抖动③挂起某些进程④采用缺页频度法（PageFaultFrequency,PFF）缺页频度的上限和下限

4.8段式虚拟存储器4.8.1基本工作过程

▲一个进程的所有分段的副本都保存在外存上。当它运行时，先把当前需要的一段或几段装入内存，其他段仅在调用时才装入。

▲当所访问的段不在内存时，便产生缺段中断各段表项中要增加一位，以表明该段的存在状态。还要增加另外一些控制位，如：

▲修改位；▲保护位；▲共享位缺段中断机构--请求分段系统中的中断处理过程

4.8.2动态链接和链接中断处理1．动态链接仅当用到某个分段时才对它进行链接，从而避免不必要的链接。间接编址间接字链接故障指示位

4.8.2动态链接和链接中断处理直接编址与间接编址示意图

2．链接中断处理段的动态链接示意图

程序MAIN中有一条指令LOAD*1，3|100

方式功能单一连续区分区式页式段式段页式固定动态适用环境单道多道多道多道多道虚拟空间一维一维一维二维二维重定位方式静态静态动态动态动态动态分配方式连续连续非连续非连续非连续释放全部分区淘汰算法淘汰算法淘汰算法保护界限寄存器界限寄存器对页表段表、段长段表、段长、页表内存扩充覆盖与交换覆盖与交换虚存虚存虚存共享不能不能较难方便方便硬件支持保护保护地址变换机构、保护地址变换机构、保护地址变换机构、保护4.9工作集

测试表明，虚拟存储系统的有效操作依赖于程序中访问的局部化程度。

1.局部性模型时间局部化是指一旦某条指令或数据被访问过，它往往很快又被再次访问。空间局部化是指一旦某个位置被访问过，它附近的位置也可能很快要用到。4.9工作集2.工作集模型工作集，就是一个进程在某一小段时间内访问页面的集合。工作集模型

▲工作集依赖于程序的行为，并且其大小与的取值有关。每个进程的工作集大小为WSSi，那么D就是系统中全部（n个）进程对内存块的总请求量。▲如果请求值D大于可用内存块的总量m(D＞m)，将出现抖动。

伙伴系统是对固定分区和可变分区两种存储管理“扬长避短”后，提出的一种折中方案。

伙伴系统中，可用内存分区的大小为： 2K，L≤K≤U其中：2L表示分配的最小分区的尺寸；2U表示分配的最大分区的尺寸。伙伴系统

C(64KB)64KBA(128KB)128KBB(256KB)512KBA(128KB)B(256KB)512KBA(128KB)128KB256KB512KB1MBC(64KB)64KBA(128KB)B(256KB)D(256KB)C(64KB)64KBA(128KB)256KBD(256KB)256KB256KBC(64KB)64KB128KB256KBD(256KB)256KBC(64KB)64KBE(128KB)256KBD(256KB)256KBE(128KB)128KB256KBD(256KB)256KB512KBD(256KB)256KB1MB1MB初启：A请求100KB：B请求240KB：C请求64KB：D请求256KB：B释放256KB：A释放128KB：E请求128KB：C释放64KB：E释放