OS04.1-4.3存储管理-2014-2015-2

1、操作系统操作系统Operating Systems笫四章笫四章 存储器管理存储器管理笫四章笫四章 存储器管理存储器管理4.1 存储器的层次结构存储器的层次结构 4.2 程序的装入和链接程序的装入和链接4.3连续分配存储管理方式连续分配存储管理方式4.4对换对换4.5分页存储管理方式分页存储管理方式4.6分段存储管理方式分段存储管理方式图图4-1 计算机系统存储层次示意计算机系统存储层次示意 寄存器高速缓存主存磁盘缓存磁盘可移动存储介质CPU寄存器主存辅存制造成本趋高制造成本趋高访问速度趋慢访问速度趋慢4.1 存储器的层次结构存储器的层次结构 CPUWord TransferFastFastes

2、tFastLessfastSlowSlowBlock TransferCacheMain MemoryFigure 1.16 Cache and Main Memory(a) Single cache(b) Three-level cache organizationCPULevel 1(L1) cacheLevel 2(L2) cacheLevel 3(L3) cacheMainMemory高速缓存（高速缓存（Cache） 介于寄存器和存储器之间介于寄存器和存储器之间的存储器的存储器 容量远大于寄存器容量远大于寄存器 访问速度快于主存储器访问速度快于主存储器 主要用于备份主存中较常主要用于备

3、份主存中较常用的数据用的数据 以减少处理机对主存储以减少处理机对主存储器的访问次数。器的访问次数。磁盘缓存磁盘缓存 缓和两者之间在速度上的不匹配缓和两者之间在速度上的不匹配 磁盘的磁盘的I/O速度远低于对主存的访问速度速度远低于对主存的访问速度 用于暂时存放频繁使用的一部分磁盘数据和信息用于暂时存放频繁使用的一部分磁盘数据和信息 以减少访问磁盘的次数。以减少访问磁盘的次数。 磁盘缓存与高速缓存磁盘缓存与高速缓存 磁盘缓存并不是一种实际存在的存储器磁盘缓存并不是一种实际存在的存储器 利用主存中的部分存储空间暂时存放从磁盘中读出利用主存中的部分存储空间暂时存放从磁盘中读出(或或写入写入)的信息的信

4、息主存储器管理功能主存储器管理功能 存储分配和回收存储分配和回收 分配和回收算法及相应的数据结构分配和回收算法及相应的数据结构 地址变换和重定位地址变换和重定位 存储共享和保护存储共享和保护 存储器扩充存储器扩充 交换交换 虚拟存储的请求调入和预调入虚拟存储的请求调入和预调入物理地址空间物理地址空间 把内存分成若干个大小相等的存储单元把内存分成若干个大小相等的存储单元 存储单元占存储单元占8位，称作字节（位，称作字节（byte） 每个单元给一个编号每个单元给一个编号 这个编号称为内存地址这个编号称为内存地址物理地址、绝对地址、实地址物理地址、绝对地址、实地址 物理地址空间：物理地址空间： 物理

5、地址的集合称为物理地址空间（主存地址空间）物理地址的集合称为物理地址空间（主存地址空间）1000逻辑地址空间逻辑地址空间 逻辑地址空间逻辑地址空间 生成的目标程序占据一定的地址空生成的目标程序占据一定的地址空间，称为程序的逻辑地址空间（简间，称为程序的逻辑地址空间（简称逻辑空间）。称逻辑空间）。 每个目标程序都是以每个目标程序都是以0为基址顺序为基址顺序进行编址的进行编址的 在逻辑空间中每条指令的地址和指令在逻辑空间中每条指令的地址和指令中要访问的操作数地址统称为逻辑地中要访问的操作数地址统称为逻辑地址。址。Load A 500 34560100500逻辑地址空间逻辑地址空间gcc -o te

6、st test.c 逻辑地址和物理地址逻辑地址和物理地址When running a user program, the CPU deals with logical addresses.The memory controller sees a stream of physical addresses.The memory management unit (MMU) does the conversion.CPUMMUVirtualAddressesPhysicalAddresses4.2 程序的装入和链接程序的装入和链接 链接链接动态动态重定重定位位静态静态重定重定位位源程序源程序模块模块1

7、 1源程序源程序模块模块2 2源程序源程序模块模块n n目标目标模块模块1 1目标目标模块模块2 2目标目标模块模块n n目标代码目标代码( (装入模装入模块块)()(辅存辅存) )编译编译装入装入执行执行程序名字空间程序名字空间逻辑地址空间逻辑地址空间物理地址空间物理地址空间可执行可执行二进代二进代码码( (主存主存) )库代码库代码可执行可执行二进代二进代码码( (主存主存) ) 0 0m-1m-10 00 0Typical programming stepstest1.c, test2.cgcc c test1.c;gcc c test2.c; test1.o, test2.ogcc o

8、 test test1.o test2.o lmylib -lmtest./testC sourceC sourcecompilercompilerobjectmoduleobjectmodulelinkerOther objectmodulesSystemlibraryLoad moduleloadermemoryimagemylib,Compile timeLoad timeRun timeDynamicallyLoadedSystem library4.2.1 程序的装入程序的装入 绝对装入方式（绝对装入方式（ Absolute Loading Mode） 可重定位装入方式（可重定位装入

9、方式（ Relocation Loading Mode） 动态运行时装入方式（动态运行时装入方式（ Dynamic Run-time Loading）1. 1. 绝对装入方式绝对装入方式 程序中的逻辑地址与实际内存地址完全相同程序中的逻辑地址与实际内存地址完全相同。 只能将目标模块装入内存中事先指定的位置。只能将目标模块装入内存中事先指定的位置。绝对装入方式只适用于单道程序环境。绝对装入方式只适用于单道程序环境。Load A 500Load A 500 3456 34560 01001005 50000逻辑地址空间逻辑地址空间Load A 500Load A 500 3456 34560 01

10、001005 50000物理地址空间物理地址空间2. 2. 可重定位装入方式可重定位装入方式 根据内存的当前情况，将装入模块装入到内存的适当位置根据内存的当前情况，将装入模块装入到内存的适当位置 又称又称静态重定位静态重定位：地址变换在装入时一次完成：地址变换在装入时一次完成LOAD 1,2500365LOAD 1,2500365100001100012500150005000250010000作 业 地 址 空 间内 存 空 间LOAD 1,12500可重定位装入方式特点可重定位装入方式特点 可用于多道程序环境可用于多道程序环境 可将装入模块装入到内存中任何允许的位置可将装入模块装入到内存中

11、任何允许的位置 不允许程序运行时在内存中移动位置。不允许程序运行时在内存中移动位置。 在运行过程中它在内存中的位置可能经常要改变在运行过程中它在内存中的位置可能经常要改变 此时就应采用动态运行时装入的方式此时就应采用动态运行时装入的方式 Load A, 2500 36502500逻辑地址空间逻辑地址空间Load A, 3651000012500物理地址空间物理地址空间1250020000Load A,22500365225003. 3. 动态运行时装入方式动态运行时装入方式 在把装入模块装入内存后，并不立即把装入模块中的相对在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址地

12、址转换为绝对地址 把这种地址转换推迟到程序真正要执行时才进行。把这种地址转换推迟到程序真正要执行时才进行。 装入内存后的所有地址都仍是相对地址。装入内存后的所有地址都仍是相对地址。 地址变换发生在程序执行过程中！地址变换发生在程序执行过程中！ 动态重定位动态重定位程序的链接程序的链接 静态链接方式（静态链接方式（ Static Linking） 装入时动态链接装入时动态链接（ Load-time Dynamic Linking） 运行时动态链接（运行时动态链接（ Run-time Dynamic Linking）程序的链接程序的链接 静态链接静态链接 在程序运行之前，先将各目标模块及它们所需的

13、库函数在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的，链接成一个完整的装配装配模块，以后不再拆开。模块，以后不再拆开。 修改相对地址；修改相对地址； 变换外部调用符号；变换外部调用符号； Module ACALL BReturnLength LModule BCALL CReturnLength MModule CReturnLength N0L-1Module AJSR “L”ReturnModule BJSR “L+M”ReturnModule CReturnLL+M-1L+ML+M+N-1Object ModulesLoad Module0L-10M-10N-1装入前

14、装入前链接修链接修改地址改地址静态链接静态链接装入时动态链接装入时动态链接 在装入内存时，边装入边链接。在装入内存时，边装入边链接。Module ACALL BReturnLength LModule BCALL CReturnLength MModule CReturnLength N0L-1Module AJSR “L”ReturnModule BJSR “L+M”ReturnModule CReturnLL+M-1L+ML+M+N-1Object Modules0L-10M-10N-1装入时装入时链接修链接修改地址改地址外存外存内存内存装入时动态链接优点装入时动态链接优点 便于修改和更新

15、便于修改和更新 静态链接静态链接若更新某个模块，则需重新链接全部应用程序模块若更新某个模块，则需重新链接全部应用程序模块 gcc -o test test1.o test2.o 便于实现对目标模块的共享便于实现对目标模块的共享 静态静态链接链接每个模块都包含有其目标模块的拷贝每个模块都包含有其目标模块的拷贝 装入时动态链接装入时动态链接易将一个目标模块链接到几个应用模块中易将一个目标模块链接到几个应用模块中gcc -o test3 test4.o test2.o运行时动态链接运行时动态链接 运行时动态链接运行时动态链接 将对某些模块的将对某些模块的链接推迟链接推迟到程序执行时才进行链接到程序执

16、行时才进行链接 在在执行过程中执行过程中，当发现一个被调用模块尚未装入内存，当发现一个被调用模块尚未装入内存时，立即由时，立即由OSOS去找到该模块并将之去找到该模块并将之装入内存装入内存， 把它把它链链接到调用者模块上接到调用者模块上运行时运行时动态链接特点动态链接特点 可加快程序的装入可加快程序的装入过程，可过程，可节省大量的内存空间节省大量的内存空间应用程序应用程序在每次运行的模块可能不相同在每次运行的模块可能不相同凡凡在执行过程中未被用到的目标模块，都不会被调入在执行过程中未被用到的目标模块，都不会被调入内存和被链接到内存和被链接到装入模块装入模块上上4.3连续分配方式连续分配方式 单

17、一连续分配单一连续分配 固定分区分配固定分区分配 动态分区分配动态分区分配 伙伴系统伙伴系统 动态重定位分区分配动态重定位分区分配4.3.14.3.1单一连续分配单一连续分配 只能用于单用户、单任务的操作系统中。只能用于单用户、单任务的操作系统中。 如：如：MS-DOSMS-DOS 把内存分为系统区和用户区两部分把内存分为系统区和用户区两部分 系统区系统区仅提供给仅提供给OSOS使用使用通常是放在内存的低址部分通常是放在内存的低址部分 用户区用户区是指除系统区以外的全部内存空间，提供给用户使是指除系统区以外的全部内存空间，提供给用户使用。用。4.3.24.3.2固定分区分配固定分区分配 多道程

18、序的存储管理多道程序的存储管理 主存空间被划分成主存空间被划分成固定大小固定大小的分区，每个分区只装入一个作业，的分区，每个分区只装入一个作业， 若多个分区中都装有作业，则它们可以并发执行。若多个分区中都装有作业，则它们可以并发执行。1 1划分分区的方法划分分区的方法(1)(1)分区大小相等。分区大小相等。缺点是缺乏灵活性。缺点是缺乏灵活性。 太大：浪费太大：浪费 太小：不太小：不够用够用 内部碎片内部碎片 由于被装入的数据块小于分区由于被装入的数据块小于分区大小，从而导致分区内部有空大小，从而导致分区内部有空间浪费。间浪费。2M1 1划分分区的方法划分分区的方法(2)(2)分区分区大小不等。

19、大小不等。划分为多个大、中、小搭配划分为多个大、中、小搭配的分区的分区 根据程序大小决定所使用根据程序大小决定所使用的分区的分区 2M2 2内存分配内存分配 通常将分区按大小进行排队，并为之建立一张分区使用表通常将分区按大小进行排队，并为之建立一张分区使用表操作系统作业A作业B作业C24 KB32 KB64 KB128 KB256 KB分区号大小/KB起址/KB状态11220已分配23232已分配36464已分配4128128未分配(b) 存储空间分配情况(a) 分区说明表问题：并发进程数受分区个数的制约！问题：并发进程数受分区个数的制约！出现：有内存却不能运行程序或大进程无法运行！出现：有内

20、存却不能运行程序或大进程无法运行！4.3.34.3.3动态分区分配动态分区分配 动态分区分配是根据进程的实际需要，动态地为之分配内动态分区分配是根据进程的实际需要，动态地为之分配内存空间。存空间。动态分区动态分区外部碎片：在所有分区外的存储空间变成越来越多的碎片。外部碎片：在所有分区外的存储空间变成越来越多的碎片。动态分区分配动态分区分配 优点优点： 便于动态申请内存便于动态申请内存 碎片碎片问题问题( (外部碎片外部碎片) ) 要求连续的内存空间要求连续的内存空间 经过一段时间的分配回收后，内存中存在很多很小的经过一段时间的分配回收后，内存中存在很多很小的空闲块空闲块。它们。它们每一个都每一

21、个都很小很小，不足以满足分配要求；，不足以满足分配要求；但其总和满足分配要求。这些空闲块被但其总和满足分配要求。这些空闲块被称为称为碎片。碎片。 造成存储资源的造成存储资源的浪费浪费1 1分区分配中的数据结构分区分配中的数据结构(1)(1)空闲分区表。空闲分区表。设置一张空闲分区表，用于记录每个空闲分区的情况。设置一张空闲分区表，用于记录每个空闲分区的情况。每个空闲分区占一个表目：包括分区序号、分区始址及每个空闲分区占一个表目：包括分区序号、分区始址及分区的大小等数据项。分区的大小等数据项。(2)(2)空闲分区链。空闲分区链。前向指针0N 个字节可用后向指针0N +2N +23 3分区分配操作

22、分区分配操作1) 1) 分配内存分配内存从头开始查表检索完否？m.size u.size?m.size u.sizesize?从该分区中划出u.size 大小的分区将该分区分配给请求者修改有关数据结构返回返回继续检索下一个表项将该分区从链中移出YNNYYN动态分区回收算法（动态分区回收算法（1） 只需修改其前一分区只需修改其前一分区F1F1的大小的大小 X F2 X F2 变为变为 F1 F1 F1 F1X X回收前回收前X X回收回收后后B B大小大小首址首址20K20K 20K 20K20K20K40K40K60K60K大小大小首址首址40K40K 2 20K0K空闲区表空闲区表空闲区表空

23、闲区表动态分区回收算法（动态分区回收算法（2） 用回收区的首址作为新空闲区的首址，大小为两者之和用回收区的首址作为新空闲区的首址，大小为两者之和 F1 X F F1 X F F1 F1变为变为 F2 F2X X回收前回收前X X回收回收后后X X大小大小首址首址20K20K 60K 60K40K40K60K60K大小大小首址首址40K40K 40K 40K空闲区表空闲区表空闲区表空闲区表动态分区回收算法（动态分区回收算法（3） 使用使用F1F1的表项和的表项和F1F1的首址，取消的首址，取消F2F2的表项的表项 变为变为F1F1 F1 F1 F2 F2X X回收前回收前X X回收回收后后X X

24、60K60K20K20K40K40K大小大小首址首址20K20K 20K 20K20K20K 6 60K0K大小大小首址首址60K60K 2 20K0K空闲区表空闲区表空闲区表空闲区表动态分区回收算法动态分区回收算法（4 4） 回收区既不与回收区既不与F1邻接，又不与邻接，又不与F2邻接。邻接。 这时应为回收区单独建立一新表项，填写回收区的首址和这时应为回收区单独建立一新表项，填写回收区的首址和大小，并根据其首址插入到空闲链（表）中的适当位置。大小，并根据其首址插入到空闲链（表）中的适当位置。 F1 X F2 F1 X F2 F1 F2 F1 F2 变为变为X XX X回收前回收前X X回收回

25、收后后大小大小首址首址空闲区表空闲区表 40K40K60K60K大小大小首址首址空闲区表空闲区表20K20K 40K 40K 动态分区分配算法动态分区分配算法 基于顺序式搜索的动态分区分配算法基于顺序式搜索的动态分区分配算法 基于索引搜索的动态分区分配算法基于索引搜索的动态分区分配算法4.3.4基于顺序式搜索的动态分区分配算法基于顺序式搜索的动态分区分配算法 首次适应算法首次适应算法(First(First Fit)Fit) 循环首次适应算法循环首次适应算法(next fit)(next fit) 最佳适应算法最佳适应算法(best fit)(best fit) 最坏适应算法最坏适应算法(wo

26、rst fit)(worst fit)首次适应算法首次适应算法(FF)(FF) 要求要求空闲分区链空闲分区链以地址递增的次序链接。以地址递增的次序链接。首次适应算法首次适应算法(first fit)(first fit) 该算法倾向于优先利用内存中该算法倾向于优先利用内存中低址部分低址部分的空闲分区，从而的空闲分区，从而保留了高址部分的大空闲区。保留了高址部分的大空闲区。 为以后到达的大作业分配大的内存空间创造了条件。为以后到达的大作业分配大的内存空间创造了条件。 缺点缺点 低址部分不断被划分，会留下许多难以利用的、低址部分不断被划分，会留下许多难以利用的、很小很小的空闲分区的空闲分区 每次查

27、找又都是从低址部分开始，这无疑会增加每次查找又都是从低址部分开始，这无疑会增加查找查找可用空闲分区时的可用空闲分区时的开销开销。 循环首次适应算法循环首次适应算法(next fit)(next fit) 该算法是由首次适应算法演变而成的。该算法是由首次适应算法演变而成的。 在分配内存空间时在分配内存空间时 不再是每次都从链首开始查找，不再是每次都从链首开始查找， 是从上次找到的空闲分区的是从上次找到的空闲分区的下一个空闲分区下一个空闲分区开始查找开始查找 直至找到一个能满足要求的空闲分区直至找到一个能满足要求的空闲分区 从中划出一块与请求大小相等的内存空间分配给作业从中划出一块与请求大小相等的

28、内存空间分配给作业 应设置一应设置一起始查寻指针起始查寻指针，用于指示下一次起始查寻的空闲，用于指示下一次起始查寻的空闲分区，并采用循环查找方式分区，并采用循环查找方式循环首次适应算法循环首次适应算法(next fit)(next fit) 使内存中的空闲分区分布得更均匀使内存中的空闲分区分布得更均匀 减少了查找空闲分区时的开销减少了查找空闲分区时的开销 会缺乏大的空闲分区。会缺乏大的空闲分区。 最佳适应算法最佳适应算法(best fit)(best fit) 把能满足要求、又是最小的空闲分区分配给作业把能满足要求、又是最小的空闲分区分配给作业 将所有的空闲分区按其容量以从小到大的顺序形成一空

29、将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。闲分区链。 在存储器中会留下许多难以利用的小空闲区。在存储器中会留下许多难以利用的小空闲区。 最坏适应算法最坏适应算法(worst fit)(worst fit) 优点优点 可使剩下的空闲区不至于太小，产生碎片的几率最小可使剩下的空闲区不至于太小，产生碎片的几率最小 对中、小作业有利，查找效率很高。对中、小作业有利，查找效率很高。 缺点：它会使存储器中缺乏大的空闲分区。缺点：它会使存储器中缺乏大的空闲分区。练习练习 在动态分区分配存储管理下，按地址排列的内存空闲区为：在动态分区分配存储管理下，按地址排列的内存空闲区为：10K 、4K 、

30、20K 、18K 、7K 、9K 、12K 和和15K 。 对于下列的连续存储区的请求：对于下列的连续存储区的请求： 12K 、10K 、9K， 试问：使用首次适应算法、最佳适应算法、最坏适应算法和试问：使用首次适应算法、最佳适应算法、最坏适应算法和循环首次适应算法循环首次适应算法，哪个空闲区被使用？，哪个空闲区被使用？首次适应分配算法首次适应分配算法要求空闲区按要求空闲区按首址递增首址递增的次序组织空闲区表（队列）的次序组织空闲区表（队列） 。顺序查找未分配区表或链表，直到找第一能满足长度要顺序查找未分配区表或链表，直到找第一能满足长度要求的空闲区为止，分割此分区。求的空闲区为止，分割此分区

31、。 按地址排列的内存空闲区为：按地址排列的内存空闲区为： 10KB、4KB、20KB、18KB、7KB、9KB、12KB、15KB 请求序列：请求序列：12KB; 10KB ; 9KB : 8KB 9KB最佳适应分配算法最佳适应分配算法 要求按要求按空闲区大小空闲区大小从小到大的次序组成空闲区表从小到大的次序组成空闲区表挑选一个能满足用户要求的最小分区。挑选一个能满足用户要求的最小分区。 按地址排列的内存空闲区为：按地址排列的内存空闲区为： 10KB、4KB、20KB、18KB、7KB、9KB、12KB、15KB按按空闲区大小空闲区大小: : 4KB 7KB 9KB 10KB 12KB 15K

32、B 18KB 20KB请求序列：请求序列：12KB; 10KB ; 9KB : 最坏适应分配算法最坏适应分配算法要求空闲区要求空闲区按大小递减按大小递减的顺序组织空闲区表的顺序组织空闲区表扫描整个未分配区链表，挑选一个最大的空闲区分割扫描整个未分配区链表，挑选一个最大的空闲区分割 按地址排列的内存空闲区为：按地址排列的内存空闲区为： 10KB、4KB、20KB、18KB、7KB、9KB、12KB、15KB按按空闲区大小空闲区大小: :20KB 18KB 15KB12KB 10KB 9KB 7KB 4KB请求序列：请求序列：12KB; 10KB ; 9KB : 8KB8KB6KB循环首次适应算法

33、循环首次适应算法要求空闲区按要求空闲区按首址递增首址递增的次序组织空闲区表（队列）的次序组织空闲区表（队列） 。从未分配区的上次扫描结束处顺序查找。从未分配区的上次扫描结束处顺序查找。按地址排列的内存空闲区为：按地址排列的内存空闲区为： 10KB、4KB、20KB、18KB、7KB、9KB、12KB、15KB请求序列：请求序列：12KB; 10KB ; 9KB : 8KB8KB 对如图所示的内存分配情况对如图所示的内存分配情况(其中，其中，阴影部分表示已占用块，空白部分阴影部分表示已占用块，空白部分表示空闲块表示空闲块)，若要申请一块，若要申请一块40KB的内存，对于最佳适应算法，给出的内存，

34、对于最佳适应算法，给出分配区域的首地址分配区域的首地址_。A.100KBB.190KBC.330KBD.410KB102K60K90K80K0KB100KB180KB190KB280KB330KB390KB410KB512KBC问题问题思考思考 假设使用固定分区的内存管理方案，分区大小为假设使用固定分区的内存管理方案，分区大小为216字节，字节，内存总大小为内存总大小为224字节。系统维护着一张进程表，为每个常字节。系统维护着一张进程表，为每个常驻进程保存指向一个分区的指针，这个指针需要多少位？驻进程保存指向一个分区的指针，这个指针需要多少位？ 分区数：分区数： 224/216 = 284.3

35、.54.3.5基于索引搜索的动态分区分配算法基于索引搜索的动态分区分配算法 快速适应算法快速适应算法(quick fit)(quick fit) 伙伴系统伙伴系统 哈希算法哈希算法伙伴系统伙伴系统 固定分区和动态分区方式的折衷固定分区和动态分区方式的折衷 分区大小均为分区大小均为2 2的的K K次幂次幂，L LK KM M。 2L = 分配的最小分区大小分配的最小分区大小 2M = 分配的最大分区大小，通常是整个可分配的内存大小分配的最大分区大小，通常是整个可分配的内存大小 伙伴通过对大块的物理主存划分而获得伙伴通过对大块的物理主存划分而获得 每次都对半划分每次都对半划分2M 2M-1 n 2

36、M 2M-1 2M-1 伙伴原理伙伴原理 两个伙伴的大小必须相同两个伙伴的大小必须相同 无论已分配分区或空闲分区其大小均为无论已分配分区或空闲分区其大小均为2的的k次幂。次幂。2M 2M-2 n 2M-12M-2 2M-2 伙伴原理伙伴原理 直到产生大于或等于直到产生大于或等于n的最小块的最小块2M 2M-2 2M-2 空闲分区双向链表空闲分区双向链表 在系统运行过程中，因不断划分，可形成若干个不连续空在系统运行过程中，因不断划分，可形成若干个不连续空闲分区。闲分区。 对每一类具有相同大小的空闲分区，单独设立一个空对每一类具有相同大小的空闲分区，单独设立一个空闲分区双向链表。闲分区双向链表。0

37、 k-12L2k-12k2M0 k0 k 当需要为进程分配一个长度为当需要为进程分配一个长度为n的存储空间时，的存储空间时，1. 计算一个计算一个 i 值，使值，使 2i1 n 2i，2. 在空闲分区大小为在空闲分区大小为2i的空闲分区链表中查找。的空闲分区链表中查找。3. 若找到，把该空闲分区分配给进程。若找到，把该空闲分区分配给进程。4. 否则，表明长度为否则，表明长度为2i的空闲分区已经耗尽，的空闲分区已经耗尽，在分区大小为在分区大小为2i1的空闲分区链表中寻找。的空闲分区链表中寻找。5. 若存在若存在2i1的一个空闲分区，的一个空闲分区，把该空闲分区分为相等的两个分区，把该空闲分区分为

38、相等的两个分区，这两个分区称为一对伙伴，其中的一个分区用于分配，而这两个分区称为一对伙伴，其中的一个分区用于分配，而把另一个加入分区大小为把另一个加入分区大小为2i的空闲分区链表中的空闲分区链表中2i2i+12i+26. 若大小为若大小为2i1的空闲分区也不存在，则需要查找大小为的空闲分区也不存在，则需要查找大小为2i2的空闲分区，的空闲分区，7. 若找到则对其进行两次分割：若找到则对其进行两次分割： 第一次，将其分割为大小为第一次，将其分割为大小为2i1的两个分区的两个分区一个用于分配一个用于分配一个加入到大小为一个加入到大小为2i1的空闲分区链表中；的空闲分区链表中； 第二次，将第一次用于分配的空闲区分割为：第二次，将第一次用于分配的空闲区分割为：一个用于分配，一个用于分配，一个加入到大小为一个加入到大小为2i的空闲分区链表中。的空闲分区链表中。8. 若仍然找不到，则继续查找大小为若仍然找不到，则继续查