操作系统原理课件

1、第二章 存 储 管 理 1第二章第二章 存储管理存储管理 2.1 2.1 存储管理基础存储管理基础 2.2 2.2 基本存储管理方法基本存储管理方法 2.3 2.3 可变分区存储管理方法可变分区存储管理方法 2.4 2.4 内存扩充技术内存扩充技术 2.5 2.5 纯分页的存储管理纯分页的存储管理 2.6 2.6 请求分页系统请求分页系统 2.7 2.7 段式存储管理段式存储管理 2.8 2.8 段页式存储管理段页式存储管理 2.9 Linux2.9 Linux存储管理存储管理第二章 存 储 管 理 2存储器可分为：内存储器和外存储器；存储器可分为：内存储器和外存储器；内存储器：可以被内存储器

2、：可以被CPU直接访问。直接访问。外存储器：不可以被外存储器：不可以被CPU直接访问，外存与直接访问，外存与CPU之之间只能够在输入输出控制系统的管理下，进行信息间只能够在输入输出控制系统的管理下，进行信息交换。交换。第二章 存 储 管 理 32.1 2.1 存储管理基础存储管理基础 库链接程序装入模块装入程序编译程序产生的目标模块第一步第二步第三步内存2.1.1 2.1.1 虚拟地址与物理地址虚拟地址与物理地址第二章 存 储 管 理 4内存储器是由一个个存储单元组成，一个存储单元可存放内存储器是由一个个存储单元组成，一个存储单元可存放若干个二进制的位（若干个二进制的位（bit），），8个二进

3、制位被称为一个字节个二进制位被称为一个字节（Byte）。）。内存中的存储单元按一定顺序进行编号，每个单元所对应内存中的存储单元按一定顺序进行编号，每个单元所对应的编号，称为该单元的单元地址。的编号，称为该单元的单元地址。物理地址物理地址（绝对地址，实地址）：内存中存储单元的地址。（绝对地址，实地址）：内存中存储单元的地址。物理地址可直接寻址。物理地址可直接寻址。逻辑地址逻辑地址（相对地址，虚地址）：用户的程序经过汇编或（相对地址，虚地址）：用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式。编译后形成目标代码，目标代码通常采用相对地址的形式。其首地址为其首地址为0 0，其余

4、指令中的地址都相对于首地址来编，其余指令中的地址都相对于首地址来编址。址。不能用逻辑地址在内存中读取信息。不能用逻辑地址在内存中读取信息。第二章 存 储 管 理 5第二章 存 储 管 理 6地址重定位地址重定位 地址重定位（地址映射）地址重定位（地址映射）：将用户程序中的逻辑地址：将用户程序中的逻辑地址转换为运行时由机器直接寻址的物理地址。转换为运行时由机器直接寻址的物理地址。 当程序装入内存时当程序装入内存时, , 操作系统要为该程序分配一个合操作系统要为该程序分配一个合适的内存空间，由于适的内存空间，由于程序的逻辑地址与分配到内存物程序的逻辑地址与分配到内存物理地址不一致理地址不一致, ,

5、 而而CPUCPU执行指令时，是按物理地址进行执行指令时，是按物理地址进行的，所以要进行地址转换。的，所以要进行地址转换。第二章 存 储 管 理 72.1.2 地址定位方式地址定位方式1. 固定定位方式固定定位方式 由程序员在编写程序时或由编译连接程序对源程序进由程序员在编写程序时或由编译连接程序对源程序进行编译连接时，直接指定程序在执行时访问的实际存储器行编译连接时，直接指定程序在执行时访问的实际存储器地址的方式称为固定定位方式。此种定位方式一般只适合地址的方式称为固定定位方式。此种定位方式一般只适合于单板机或单用户系统。在多道程序环境下，应保证各个于单板机或单用户系统。在多道程序环境下，应

6、保证各个作业的地址互不重叠，这就比较困难了。作业的地址互不重叠，这就比较困难了。第二章 存 储 管 理 8第二章 存 储 管 理 92. 静态重定位方式静态重定位方式 源程序经编译和连接后生成目标代码中的地址是以源程序经编译和连接后生成目标代码中的地址是以0为起始地址的相对地址。为起始地址的相对地址。 当需要执行时，由装入程序运行重定位程序模块，当需要执行时，由装入程序运行重定位程序模块，根据作业在本次分配到的内存起始地址，将可执行目标根据作业在本次分配到的内存起始地址，将可执行目标代码装到指定内存地址中，代码装到指定内存地址中，并修改所有有关地址部分的并修改所有有关地址部分的值值。 修改的方

7、式是对每一个逻辑地址的值加上内存区首修改的方式是对每一个逻辑地址的值加上内存区首地址（或称基地址）值。地址（或称基地址）值。第二章 存 储 管 理 10第二章 存 储 管 理 11静态重定位的特点静态重定位的特点（1 1）静态重定位是在程序运行之前完成地址重定位工作的；静态重定位是在程序运行之前完成地址重定位工作的；（2 2）静态重定位由软件实现，无须硬件提供支持；静态重定位由软件实现，无须硬件提供支持；（3 3）实行静态重定位时，地址重定位工作是在程序装入时被实行静态重定位时，地址重定位工作是在程序装入时被一次集中完成的；一次集中完成的；（4 4）绝对地址空间里的目标程序与原相对地址空间里的

8、目标绝对地址空间里的目标程序与原相对地址空间里的目标程序面目已不相同，因为前者进行了地址调整；程序面目已不相同，因为前者进行了地址调整；（5 5）实施静态重定位后，若用户程序在内存中做了移动，那实施静态重定位后，若用户程序在内存中做了移动，那么程序指令中的地址就不再反映所在的存储位置了，除非么程序指令中的地址就不再反映所在的存储位置了，除非重新进行地址重定位。重新进行地址重定位。第二章 存 储 管 理 123. 动态重定位方式动态重定位方式 采用动态重定位方式，将程序在装入内存时，不必修采用动态重定位方式，将程序在装入内存时，不必修改程序的逻辑地址值，程序执行期间在访问内存之前，改程序的逻辑地

9、址值，程序执行期间在访问内存之前，再实时地将逻辑地址变换成物理地址。动态重定位要靠再实时地将逻辑地址变换成物理地址。动态重定位要靠硬件地址变换机构实现。硬件地址变换机构实现。 当程序开始执行时，系统将程序在内存的起始地址送当程序开始执行时，系统将程序在内存的起始地址送入地址变换机构中的入地址变换机构中的基地址寄存器基地址寄存器BR中。中。 在执行指令时，若涉及到逻辑地址，则先将该地址送在执行指令时，若涉及到逻辑地址，则先将该地址送入入虚拟地址寄存器虚拟地址寄存器 VR，再将，再将BR 和和 VR 中的值相加后送中的值相加后送入地址寄存器入地址寄存器 MR，并按，并按 MR 中的值访问内存。中的

10、值访问内存。（MR）=（BR）+（VR）第二章 存 储 管 理 13第二章 存 储 管 理 142.2 2.2 基本存储管理方法基本存储管理方法2.2.1 单一连续分区存储管理单一连续分区存储管理 基本思想基本思想：内存分为两个区域：系统区，用户区。：内存分为两个区域：系统区，用户区。应用程序装入到用户区，可使用用户区全部空间。应用程序装入到用户区，可使用用户区全部空间。 最简单，适用于单用户、单任务的最简单，适用于单用户、单任务的OS；单用户系单用户系统在一段时间内，只有一个进程在内存。统在一段时间内，只有一个进程在内存。第二章 存 储 管 理 15特点特点（1）系统总是把整个用户区分配给一

11、个用户使用。系统总是把整个用户区分配给一个用户使用。（2）实际上，内存用户区又被分为实际上，内存用户区又被分为“使用区使用区”和和“空闲区空闲区”两部分。两部分。在操作系统中，把分配给用户、但又未使用的区域称为在操作系统中，把分配给用户、但又未使用的区域称为“内部碎片内部碎片”。（3）由于任何时刻内存的用户区中只有一个作业运行，因由于任何时刻内存的用户区中只有一个作业运行，因此这种系统只使用于单用户的情况。此这种系统只使用于单用户的情况。（4）进入内存的作业，独享系统中的所有资源，包括内存进入内存的作业，独享系统中的所有资源，包括内存中的整个用户区。中的整个用户区。第二章 存 储 管 理 16

12、特点特点（5）由于整个用户区都分配给了一个用户使用，因此作业由于整个用户区都分配给了一个用户使用，因此作业进入用户区后，没有移动的必要。采用这种存储分配策进入用户区后，没有移动的必要。采用这种存储分配策略时，将对用户程序实行略时，将对用户程序实行静态重定位静态重定位。（6）实行静态重定位，并不能阻止用户有意无意地通过不实行静态重定位，并不能阻止用户有意无意地通过不恰当地指令闯入操作系统所占用的存储区域，如何阻止恰当地指令闯入操作系统所占用的存储区域，如何阻止对操作系统的侵扰，就是所谓的对操作系统的侵扰，就是所谓的“存储保护存储保护”问题。问题。用于存储保护的专用寄存器用于存储保护的专用寄存器“

13、界限寄存器界限寄存器”第二章 存 储 管 理 17 存储保护过程存储保护过程：在：在用户态用户态下，对内存的每一次访问，都下，对内存的每一次访问，都要要在硬件的控制在硬件的控制下，与界限寄存器中的内容进行比较。下，与界限寄存器中的内容进行比较。一旦发现该访问的地址小于界限寄存器中的地址，就会一旦发现该访问的地址小于界限寄存器中的地址，就会产生产生“地址越界地址越界”中断，阻止这次访问的进行。中断，阻止这次访问的进行。 优点优点：易于管理，便于用户的了解和使用。：易于管理，便于用户的了解和使用。 缺点缺点： 由于每次只能有一个作业进入内存，故它不适用于多由于每次只能有一个作业进入内存，故它不适用

14、于多道程序设计，整个系统的工作效率不高，资源利用率道程序设计，整个系统的工作效率不高，资源利用率底下。底下。 只要作业比用户区小，那么在用户区里就会形成碎片，只要作业比用户区小，那么在用户区里就会形成碎片，造成内存储器资源的浪费。造成内存储器资源的浪费。 若用户作业的相对地址空间比用户区大，那么该作业若用户作业的相对地址空间比用户区大，那么该作业就无法运行。就无法运行。第二章 存 储 管 理 182.2.2 固定分区存储管理固定分区存储管理 把内存区把内存区固定固定地划分为若干个大小相等（和不等）的地划分为若干个大小相等（和不等）的连续分区。连续分区。每个分区装一个且只能装每个分区装一个且只能

15、装一个一个作业，分区作业，分区的划分原则一般由系统操作员或操作系统决定，分区的划分原则一般由系统操作员或操作系统决定，分区一旦划分结束，在整个执行过程中每个分区的一旦划分结束，在整个执行过程中每个分区的长度长度和和内存的总分区内存的总分区个数个数将将保持不变保持不变。 分区大小相等分区大小相等：只适合于多个相同程序的并发执行：只适合于多个相同程序的并发执行（处理多个类型相同的对象）。（处理多个类型相同的对象）。 分区大小不等：分区大小不等：多个小分区、适量的中等分区、少量多个小分区、适量的中等分区、少量的大分区。根据程序的大小，分配当前空闲的、适当的大分区。根据程序的大小，分配当前空闲的、适当

16、大小的分区。大小的分区。第二章 存 储 管 理 198 M8 M8 M8 M8 MOperating SystemOperating System8 M12 M8 M8 M6 M4 M2 M第二章 存 储 管 理 20内存分配内存分配 为了便于内存分配，通常将分区按大小进行排队，为了便于内存分配，通常将分区按大小进行排队，并为之建立一张分区说明表，其中各表项包括每个分区并为之建立一张分区说明表，其中各表项包括每个分区的起始地址、大小及状态（是否已分配）。的起始地址、大小及状态（是否已分配）。 当有一用户程序要装入时，由内存分配程序检索该当有一用户程序要装入时，由内存分配程序检索该表，从中找出一

17、个能满足要求的、尚未分配的分区，将表，从中找出一个能满足要求的、尚未分配的分区，将之分配给该应用程序，然后将该表项中的状态置为之分配给该应用程序，然后将该表项中的状态置为“已已分配分配”；若未找到大小足够的分区，则拒绝为该用户程；若未找到大小足够的分区，则拒绝为该用户程序分配内存。序分配内存。第二章 存 储 管 理 21第二章 存 储 管 理 22地址重定位与存储保护地址重定位与存储保护 固定分区存储管理中，每个分区只允许装入一个作业，固定分区存储管理中，每个分区只允许装入一个作业，作业在运行期间没有必要移动自己的位置，因此，应作业在运行期间没有必要移动自己的位置，因此，应该对程序实行该对程序

18、实行静态重定位静态重定位。 在固定分区存储管理中，不仅要防止用户程序对操作在固定分区存储管理中，不仅要防止用户程序对操作系统形成的侵扰，也要防止用户程序与用户程序之间系统形成的侵扰，也要防止用户程序与用户程序之间形成侵扰。因此必须在形成侵扰。因此必须在CPU中设置一对专用的寄存器，中设置一对专用的寄存器，用于存储保护。将两个专用寄存器分别起名为用于存储保护。将两个专用寄存器分别起名为“下下界界寄存器寄存器”和和“上界寄存器上界寄存器”第二章 存 储 管 理 23存储保护过程存储保护过程 当进程调度程序调度某个作业进程运行时，就把该作当进程调度程序调度某个作业进程运行时，就把该作业所在分区的低边

19、界地址装入到低界限寄存器，高边业所在分区的低边界地址装入到低界限寄存器，高边界地址装入到高界限寄存器。作业运行时，对内存的界地址装入到高界限寄存器。作业运行时，对内存的每一次访问，都要每一次访问，都要在硬件的控制在硬件的控制下，与两个界限寄存下，与两个界限寄存器中的内容进行比较。一旦发现该访问的地址小于界器中的内容进行比较。一旦发现该访问的地址小于界限寄存器中的地址，就会产生限寄存器中的地址，就会产生“地址越界地址越界”中断，阻中断，阻止这次访问的进行。止这次访问的进行。第二章 存 储 管 理 24固定分区存储管理的特点固定分区存储管理的特点 （1）它是最简单的、具有）它是最简单的、具有“多道

20、多道”色彩的存储管理方色彩的存储管理方案。案。 （2）当把一个分区分配给某个作业时，该作业的程序）当把一个分区分配给某个作业时，该作业的程序将一次性的全部被装入到分配给它的连续分区里。将一次性的全部被装入到分配给它的连续分区里。第二章 存 储 管 理 25 优点：易于实现，开销小。优点：易于实现，开销小。 缺点：缺点： 内碎片造成浪费（小作业不能有效地利用分区空间。内碎片造成浪费（小作业不能有效地利用分区空间。 分区总数在系统生成时确定（固定），限制了并发分区总数在系统生成时确定（固定），限制了并发执行的程序数目。执行的程序数目。 如果到达作业的尺寸比任何一个分区的长度都大，如果到达作业的尺寸

21、比任何一个分区的长度都大，那么它就无法得到运行。那么它就无法得到运行。固定分区方式的评价固定分区方式的评价第二章 存 储 管 理 262.3 2.3 可变分区存储管理可变分区存储管理 基本思想：基本思想： 内存不是预先划分好的，而是当作业装入内存不是预先划分好的，而是当作业装入时，根据作业的需求和内存空间的使用情况来决定是时，根据作业的需求和内存空间的使用情况来决定是否分配。否分配。 若有足够的空间，则按需要分割一部分分区给该进若有足够的空间，则按需要分割一部分分区给该进程程 否则令其等待主存空间否则令其等待主存空间 优点优点：没有内碎片。：没有内碎片。 缺点缺点：有外碎片。：有外碎片。第二章

22、 存 储 管 理 27外部碎片问题外部碎片问题操作系统操作系统20KB0256KB作业作业A(16KB)A(16KB)空闲区空闲区(236KB)空闲区空闲区(220KB)作业作业B(100KB)B(100KB)空闲区空闲区(120KB)(120KB)作业作业C(70KB)C(70KB)空闲区空闲区(50KB)(50KB)空闲区空闲区(100KB)(100KB)作业作业D(75KB)D(75KB)空闲区空闲区(25KB)(25KB)第二章 存 储 管 理 282.3.1 空闲存储区表空闲存储区表 管理空闲内存区的数据结构可采用链接法和连续线性表管理空闲内存区的数据结构可采用链接法和连续线性表格法

23、。下面举一个连续线性表格管理空闲内存的方法，格法。下面举一个连续线性表格管理空闲内存的方法，如采用链接法，就需要在表项中增加一个指向下一个空如采用链接法，就需要在表项中增加一个指向下一个空闲区的指针。闲区的指针。每一个空闲分区用一个每一个空闲分区用一个map结构管理：结构管理：struct map unsigned m_size; /空闲分区的长度空闲分区的长度 char *m_addr; /空闲分区的起始地址空闲分区的起始地址 ;struct map coremapN;各个空闲分区按起始地址由低到高顺次登记在空闲存储区各个空闲分区按起始地址由低到高顺次登记在空闲存储区表中，表中，m_size

24、为为0的表项是空白表项，它们集中在表的的表项是空白表项，它们集中在表的后部后部第二章 存 储 管 理 29l在系统初始阶段，在系统初始阶段，拥有一块很大的内拥有一块很大的内存空白区，这时空存空白区，这时空闲存储区表闲存储区表coremapcoremap中只需有一项登记中只需有一项登记该空闲区。该空闲区。l其余的其余的coremapcoremap表表项为空白项，即项为空白项，即m_sizem_size皆为零。皆为零。第二章 存 储 管 理 30l以后随着很多作以后随着很多作业的不断申请内存业的不断申请内存和释放内存，整个和释放内存，整个存储空间将出现许存储空间将出现许多大小不等的区域，多大小不等

25、的区域，l存储区表和实际存储区表和实际的内存空间就可能的内存空间就可能变成如图所示的情变成如图所示的情况。况。第二章 存 储 管 理 312.3.2 首次适应算法首次适应算法 1. 分配算法分配算法。u采用首次适应法为作业分配大小为采用首次适应法为作业分配大小为size的内存空间时，的内存空间时，总是从表的起始端的低地址部分开始查找。总是从表的起始端的低地址部分开始查找。u当第一次找到大于或等于申请大小的空闲区时，就按当第一次找到大于或等于申请大小的空闲区时，就按所需大小分配给作业。所需大小分配给作业。u如果分配后原空闲区还有剩余空间，就修改原存储区如果分配后原空闲区还有剩余空间，就修改原存储

26、区表项的表项的 m_size 和和 m_addr，使它记录余下的，使它记录余下的“零头零头”。u如果作业所需空间正好等于该空闲区大小，那么该空如果作业所需空间正好等于该空闲区大小，那么该空闲区表项的闲区表项的m_size就成为就成为0。u接下来要删除表中这个接下来要删除表中这个“空洞空洞”，即将随后的各非零，即将随后的各非零表项依次上移一个位置表项依次上移一个位置第二章 存 储 管 理 32char *malloc(mp,size)struct map *mp;unsigned size; register char *a; register struct map *bp; for (bp =

27、 mp; bp-m_size; bp+) if(bp-m_size = size) a = bp-m_addr; bp-m_addr += size; if(bp-m_size -= size) = 0) do bp+; (bp-1)-m_addr = bp-m_addr; while(bp-1)-m_size = bp-m_size); return(a); return(0);第二章 存 储 管 理 332. 回收算法回收算法 l当某一作业释放以前所分配到的内存时，就要将该内当某一作业释放以前所分配到的内存时，就要将该内存区归还给系统，使其成为空闲区而可被其他作业使存区归还给系统，使其成为

28、空闲区而可被其他作业使用。用。l释放区与原空闲区相邻情况可归纳为如图所示的释放区与原空闲区相邻情况可归纳为如图所示的4种情种情况。况。第二章 存 储 管 理 34u 仅与前空闲区相连仅与前空闲区相连：合并前空闲区和释放区构成一：合并前空闲区和释放区构成一块大的新空闲区，并修改空闲区表项。该空闲区的块大的新空闲区，并修改空闲区表项。该空闲区的m_addr不变，仍为原前空闲区的首地址，修改表项的不变，仍为原前空闲区的首地址，修改表项的长度域长度域m_size为原为原m_size 与释放区长度之和。与释放区长度之和。u 与前空闲区和后空闲区都相连与前空闲区和后空闲区都相连：将三块空闲区合并：将三块空

29、闲区合并成一块空闲区。修改空闲区表中前空闲区表项，其起成一块空闲区。修改空闲区表中前空闲区表项，其起始地址始地址m_addr仍为原前空闲区起始地址，其大小仍为原前空闲区起始地址，其大小m_size等于三个空闲区长度之和，这块大的空闲区由等于三个空闲区长度之和，这块大的空闲区由前空闲区表项登记。接下来还要在空闲区表中删除后前空闲区表项登记。接下来还要在空闲区表中删除后项，方法是将后项以下的非空白表项顺次上移一个位项，方法是将后项以下的非空白表项顺次上移一个位置。置。第二章 存 储 管 理 35u 仅与后空闲区相连仅与后空闲区相连：与后空闲区合并，使后空闲区：与后空闲区合并，使后空闲区表项的表项的

30、m_addr为释放区的起始地址，为释放区的起始地址，m_size为释放区为释放区与后空闲区的长度之和。与后空闲区的长度之和。u 与前、后空闲区皆不相连与前、后空闲区皆不相连：在前、后空闲区表项中：在前、后空闲区表项中间插入一个新的表项，其间插入一个新的表项，其 m_addr为释放区的起始地址，为释放区的起始地址，m_size为释放区的长度。为此，先要将后项及以下表为释放区的长度。为此，先要将后项及以下表项都下移一个位置项都下移一个位置第二章 存 储 管 理 36u若采用首次适应法，则其分配算法简单且合并若采用首次适应法，则其分配算法简单且合并相邻空闲区也很容易。相邻空闲区也很容易。u该算法的实

31、质是尽可能利用存储区低地址部分该算法的实质是尽可能利用存储区低地址部分的空闲区，而尽量在高地址部分保存较大的空的空闲区，而尽量在高地址部分保存较大的空闲区，以便一旦有分配大的空闲区的要求时，闲区，以便一旦有分配大的空闲区的要求时，容易得到满足。容易得到满足。u其缺点是由于查找总是从表首开始，前面的空其缺点是由于查找总是从表首开始，前面的空闲区往往被分割得很小，能满足分配要求的可闲区往往被分割得很小，能满足分配要求的可能性较小，查找次数就较多。系统中作业越多，能性较小，查找次数就较多。系统中作业越多，这个问题就越严重。这个问题就越严重。第二章 存 储 管 理 372.3.3 循环首次适应算法循环

32、首次适应算法u把空闲表设计成顺序结构或链接结构的循环队列，把空闲表设计成顺序结构或链接结构的循环队列，各空闲区仍按地址从低到高的次序登记在空闲区的各空闲区仍按地址从低到高的次序登记在空闲区的管理队列中。管理队列中。u同时需要设置一个起始查找指针，指向循环队列中同时需要设置一个起始查找指针，指向循环队列中的一个空闲区表项。的一个空闲区表项。u循环首次适应法分配时总是从起始查找指针所指的循环首次适应法分配时总是从起始查找指针所指的表项开始查找。表项开始查找。u第一次找到满足要求的空闲区时，就分配所需大小第一次找到满足要求的空闲区时，就分配所需大小的空闲区，修改表项，并调整起始查找指针，使其的空闲区

33、，修改表项，并调整起始查找指针，使其指向队列中被分配的后面的那块空闲区。指向队列中被分配的后面的那块空闲区。u下次分配时就从新指向的那块空闲区开始查找。下次分配时就从新指向的那块空闲区开始查找。第二章 存 储 管 理 382.3.3 循环首次适应算法循环首次适应算法u循环首次适应法的实质是起始查找指针所指的空闲循环首次适应法的实质是起始查找指针所指的空闲区和其后的空闲区群常为较长时间未被分割过的空区和其后的空闲区群常为较长时间未被分割过的空闲区，它们已合并成为大的空闲区可能性较大。闲区，它们已合并成为大的空闲区可能性较大。u比起首次适应法来，在没有增加多少代价的情况下比起首次适应法来，在没有增

34、加多少代价的情况下却明显地提高了分配查找的速度。释放算法基本同却明显地提高了分配查找的速度。释放算法基本同首次适应法一样。首次适应法一样。u首次适应法和循环首次适应法不仅可用于内存的分首次适应法和循环首次适应法不仅可用于内存的分配和释放，也可用于进程图像交换的辅存空间的分配和释放，也可用于进程图像交换的辅存空间的分配和释放，其管理空闲区的数据结构也相同。配和释放，其管理空闲区的数据结构也相同。第二章 存 储 管 理 392.3.4 最佳适应算法最佳适应算法u所谓最佳适应算法就是在所有大于或等于要求分配所谓最佳适应算法就是在所有大于或等于要求分配长度的空闲分区中挑选一个最小的分区，在分割后，长度

35、的空闲分区中挑选一个最小的分区，在分割后，所余下的剩余存储区最小或等于零。所余下的剩余存储区最小或等于零。u因此，该算法的空闲区利用率高，较大的空闲区被因此，该算法的空闲区利用率高，较大的空闲区被保存下来。保存下来。u空闲存储区管理表的组织方法可以采用顺序结构，空闲存储区管理表的组织方法可以采用顺序结构，也可采用链接结构。也可采用链接结构。u如采用顺序结构，空闲分区按地址由小到大的顺序如采用顺序结构，空闲分区按地址由小到大的顺序登记在表中，分配时需要搜索所有的空闲分区，以登记在表中，分配时需要搜索所有的空闲分区，以在其中挑出一个满足分配大小的最小的分区。此种在其中挑出一个满足分配大小的最小的分

36、区。此种管理结构的释放算法可用顺序结构的首次适应法。管理结构的释放算法可用顺序结构的首次适应法。第二章 存 储 管 理 402.3.4 最佳适应算法最佳适应算法u当采用链接结构时，空闲区也可按由小到大的非递减次当采用链接结构时，空闲区也可按由小到大的非递减次序排列。序排列。u分配时总是从最小的第一项开始，这样第一次找到的满分配时总是从最小的第一项开始，这样第一次找到的满足条件的空闲区必定是最合适的。足条件的空闲区必定是最合适的。u平均而言，只要搜索一半数目的空闲区表项就能找到最平均而言，只要搜索一半数目的空闲区表项就能找到最佳配合的空闲区，但寻找较大空闲区比较费时。佳配合的空闲区，但寻找较大空

37、闲区比较费时。u采用按存储区大小排序的链接表会降低释放算法的效率。采用按存储区大小排序的链接表会降低释放算法的效率。u由于空闲区是按大小而不是按地址序号排序的，因此释由于空闲区是按大小而不是按地址序号排序的，因此释放回收空闲区时要在整个链表上寻找地址相邻的前、后放回收空闲区时要在整个链表上寻找地址相邻的前、后空闲区，合并后又要插入到合适的位置，因此释放算法空闲区，合并后又要插入到合适的位置，因此释放算法比前两种算法耗时得多。比前两种算法耗时得多。第二章 存 储 管 理 412.3.5 最差适应算法最差适应算法u最差适应法所分割的空闲存储区是所有空闲分区中最差适应法所分割的空闲存储区是所有空闲分

38、区中的最大的一块。的最大的一块。u在实施最差适应法时，空闲区管理表项一般以在实施最差适应法时，空闲区管理表项一般以m_size由大到小的次序组织成一个链接表，因此查由大到小的次序组织成一个链接表，因此查找分割的总是最大的第一个空闲存储区。找分割的总是最大的第一个空闲存储区。u实现最差适应法时的空闲存储区表的组织方法一般实现最差适应法时的空闲存储区表的组织方法一般都是采用按空闲块由大到小排序的链接表。采用按都是采用按空闲块由大到小排序的链接表。采用按存储区大小顺序排列的链接表的形式虽然释放一个存储区大小顺序排列的链接表的形式虽然释放一个空闲块时速度较慢，但分配效率是一切算法中最高空闲块时速度较慢

39、，但分配效率是一切算法中最高的一种。的一种。第二章 存 储 管 理 42可变分区存储管理的特点可变分区存储管理的特点u（1）作业一次性的全部装入到一个连续的存）作业一次性的全部装入到一个连续的存储分区中。储分区中。u（2）分区是按照作业对存储的需求划分的，）分区是按照作业对存储的需求划分的，因此在可变分区管理中，不会出现内部碎片这因此在可变分区管理中，不会出现内部碎片这样的存储浪费。样的存储浪费。u（3）为了确保作业能够在内存中移动，要由）为了确保作业能够在内存中移动，要由硬件支持，实行指令地址的动态重定位。硬件支持，实行指令地址的动态重定位。第二章 存 储 管 理 43可变分区存储管理的缺点

40、可变分区存储管理的缺点u（1）仍然没有解决小内存运行大作业的问题。）仍然没有解决小内存运行大作业的问题。u（2）虽然避免了内部碎片造成的存储浪费，但）虽然避免了内部碎片造成的存储浪费，但有可能出现极小的分区暂时分配不出去的情形，有可能出现极小的分区暂时分配不出去的情形，引起外部碎片。引起外部碎片。u（3）为了形成大的分区，可变分区存储管理通）为了形成大的分区，可变分区存储管理通过移动程序来达到分区合并的目的，然而程序的过移动程序来达到分区合并的目的，然而程序的移动是很花费时间的，增加了系统在这方面的开移动是很花费时间的，增加了系统在这方面的开销。销。第二章 存 储 管 理 442.3.6 多重

41、分区多重分区u可变分区存储管理算法是按作业对存储的需求分配可变分区存储管理算法是按作业对存储的需求分配存储区的，因而消除了固定分区内部的剩余碎片，存储区的，因而消除了固定分区内部的剩余碎片，但随着存储区的分配和释放过程的进行，在各个被但随着存储区的分配和释放过程的进行，在各个被分配出去的分区之间会存在很多的空闲区，这就是分配出去的分区之间会存在很多的空闲区，这就是“外部碎片外部碎片”。u有时，当一个作业要装入运行，但分配不到一个够有时，当一个作业要装入运行，但分配不到一个够用的空闲分区，尽管这时内存中所有外部碎片的总用的空闲分区，尽管这时内存中所有外部碎片的总和远大于作业所申请的空间。和远大于

42、作业所申请的空间。u如采用如采用“紧凑紧凑”技术重新安排内存中各个作业的位技术重新安排内存中各个作业的位置，以使零碎的空闲区集中起来，这是一个极其耗置，以使零碎的空闲区集中起来，这是一个极其耗时的过程，一般很少采用这种策略。时的过程，一般很少采用这种策略。第二章 存 储 管 理 45请求分配请求分配u.size分分区区检索空闲分区链（表）检索空闲分区链（表）找到大于找到大于u.size的可的可用区否用区否按动态分区方按动态分区方式进行分配式进行分配修改有关的数修改有关的数据结构据结构返回分返回分区号及区号及首地址首地址空闲分空闲分区总和区总和=u.size进行紧凑形成进行紧凑形成连续空闲区连续

43、空闲区修改有关的数修改有关的数据结构据结构无法分配无法分配返回返回否否否否是是是是第二章 存 储 管 理 462.3.6 多重分区多重分区u有些系统采用多重分区技术，在作业的运行过程中有些系统采用多重分区技术，在作业的运行过程中可以申请附加的分区，以装入一个或多个子程序。可以申请附加的分区，以装入一个或多个子程序。新申请的空闲分区也无需与作业的现有分区相邻接。新申请的空闲分区也无需与作业的现有分区相邻接。u采用多重分区技术可以提高外部碎片的利用率，也采用多重分区技术可以提高外部碎片的利用率，也便于多个作业共享分区的代码和数据，这只要在共便于多个作业共享分区的代码和数据，这只要在共享的作业中包含

44、某个共享的分区即可。享的作业中包含某个共享的分区即可。u多重分区系统应当采用动态重定位技术，但存储管多重分区系统应当采用动态重定位技术，但存储管理的复杂性也增加了。为了实现存储保护，在多重理的复杂性也增加了。为了实现存储保护，在多重分区系统中要设置多对界地址寄存器，以使现运行分区系统中要设置多对界地址寄存器，以使现运行作业对每一个分区的访问都不会越界。作业对每一个分区的访问都不会越界。第二章 存 储 管 理 472.4 2.4 内存扩充技术内存扩充技术u在基本的存储管理系统中，当一个作业的程序地址空在基本的存储管理系统中，当一个作业的程序地址空间大于内存可用空间时，该作业就不能装入运行；间大于

45、内存可用空间时，该作业就不能装入运行；u当并发运行作业的程序地址空间总和大于内存可用空当并发运行作业的程序地址空间总和大于内存可用空间时，多道程序设计的实现就会碰到很大的困难。间时，多道程序设计的实现就会碰到很大的困难。u内存扩充技术就是借助大容量的辅存在逻辑上实现内内存扩充技术就是借助大容量的辅存在逻辑上实现内存的扩充，以解决内存容量不足的问题。存的扩充，以解决内存容量不足的问题。第二章 存 储 管 理 482.4.1 覆盖覆盖(overlay) 引入：引入：其目标是在较小的可用内存中其目标是在较小的可用内存中运行较大的程序运行较大的程序。 原理：原理：覆盖技术就是将一个大程序按程序的逻辑结

46、构划分成覆盖技术就是将一个大程序按程序的逻辑结构划分成若干个程序（或数据）段，并将不会同时执行，从而就不必若干个程序（或数据）段，并将不会同时执行，从而就不必同时装入内存的程序段分在一组内，该组称为同时装入内存的程序段分在一组内，该组称为覆盖段覆盖段。这个。这个覆盖段可分配到同一个称为覆盖段可分配到同一个称为覆盖区覆盖区的存储区域的存储区域。 将程序的将程序的必要部分必要部分（常用功能）的代码和数据常驻内存；（常用功能）的代码和数据常驻内存； 可选部分可选部分（不常用功能）在其他程序模块中实现，平时存（不常用功能）在其他程序模块中实现，平时存放在外存中（覆盖文件），在需要用到时才装入到内存；放

47、在外存中（覆盖文件），在需要用到时才装入到内存； 不存在调用关系的模块不必同时装入到内存，从而可以相不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖。互覆盖。( (即即不同时用的模块可共用一个分区不同时用的模块可共用一个分区) )第二章 存 储 管 理 49A20KB50KC30KF30KD20KE40KResident20KOverlay 050KOverlay 140KTotal: 190KTotal: 110K注：另一种覆盖方法：注：另一种覆盖方法：(100K)(100K)A(20K)A(20K)占一个分区：占一个分区：20K20K；B(50K)B(50K)、D(20K)D(20

48、K)和和E(40K)E(40K)共用一个分区：共用一个分区：50K50K；F(30K)F(30K)和和C(30K)C(30K)共用一个分区：共用一个分区：30K30K；第二章 存 储 管 理 50 缺点：缺点： 对用户不透明，增加了用户负担。对用户不透明，增加了用户负担。编程时必须划编程时必须划分程序模块和确定程序模块之间的覆盖关系，增分程序模块和确定程序模块之间的覆盖关系，增加编程复杂度。加编程复杂度。 从外存装入覆盖文件，以时间延长来换取空间节从外存装入覆盖文件，以时间延长来换取空间节省。省。 覆盖不需要任何来自操作系统的特殊支持，由用覆盖不需要任何来自操作系统的特殊支持，由用户程序自己控

49、制户程序自己控制 所以，覆盖通常限于用在微机和其他内存容量所以，覆盖通常限于用在微机和其他内存容量有限的或缺乏对更先进技术的硬件支持的系统中有限的或缺乏对更先进技术的硬件支持的系统中第二章 存 储 管 理 512.4.2 交换交换(swapping)u引入引入：让单一连续分区存储管理能具有：让单一连续分区存储管理能具有“多道多道”的效果。的效果。u中心思想中心思想：将作业信息都存放在辅存上，根据单一连续分区：将作业信息都存放在辅存上，根据单一连续分区存储管理的分配策略，每次只让其中一个进入内存投入运行，存储管理的分配策略，每次只让其中一个进入内存投入运行，当运行中提出输入输出请求或分配的时间片

50、用完时，就把这当运行中提出输入输出请求或分配的时间片用完时，就把这个程序从内存储器个程序从内存储器“换出换出”到辅存，把辅存里的另一个作业到辅存，把辅存里的另一个作业“换入换入”内存运行。这样从宏观上看，系统中同时就有几个内存运行。这样从宏观上看，系统中同时就有几个作业处在运行之中。作业处在运行之中。u为了减少在主存和辅存间传输的数据量，可以只将原作业的为了减少在主存和辅存间传输的数据量，可以只将原作业的一部分保存到辅存中去，只要释放的主存空间刚好够装入下一部分保存到辅存中去，只要释放的主存空间刚好够装入下一个运行作业就行。在以后的适当时间，作业移出的部分可一个运行作业就行。在以后的适当时间，

51、作业移出的部分可装入到原来的存储区中继续运行下去。这种技术称之为装入到原来的存储区中继续运行下去。这种技术称之为交换交换技术技术，也叫，也叫“滚进滚出滚进滚出”第二章 存 储 管 理 52第二章 存 储 管 理 53 优点优点： 增加并发运行的程序数目，并且给用户提供适当增加并发运行的程序数目，并且给用户提供适当的响应时间；的响应时间； 编写程序时不影响程序结构编写程序时不影响程序结构 缺点缺点： 对换入和换出的控制增加处理机开销；程序整个对换入和换出的控制增加处理机开销；程序整个地址空间都进行传送，地址空间都进行传送， 没有考虑执行过程中地址访问的统计特性。没有考虑执行过程中地址访问的统计特

52、性。交换技术的优缺点交换技术的优缺点第二章 存 储 管 理 54交换与覆盖的比较交换与覆盖的比较u与覆盖技术相比，交换技术不要求用户给出程与覆盖技术相比，交换技术不要求用户给出程序段之间的逻辑覆盖结构。序段之间的逻辑覆盖结构。u交换发生在进程或作业之间，而覆盖发生在同交换发生在进程或作业之间，而覆盖发生在同一进程或作业内。一进程或作业内。u覆盖只能覆盖那些与覆盖段无关的程序段。覆盖只能覆盖那些与覆盖段无关的程序段。第二章 存 储 管 理 552.4.3 虚拟存储器虚拟存储器u在现代的计算机系统中，一个作业即使不全部装入主在现代的计算机系统中，一个作业即使不全部装入主存，也同样能正确运行，因为：

53、存，也同样能正确运行，因为：u 在一个程序中一般都有相当数量的出错处理子程序，在一个程序中一般都有相当数量的出错处理子程序，在正常的运行过程中很少执行到这些程序；在正常的运行过程中很少执行到这些程序；u 程序中一般都含有类似程序中一般都含有类似then和和else的彼此互斥的部分，的彼此互斥的部分，在程序的一次执行中往往只选择其中的一条路径执行；在程序的一次执行中往往只选择其中的一条路径执行；u 程序中的初始化部分一般只执行一次，初始化工作程序中的初始化部分一般只执行一次，初始化工作完成后，这些代码就没有存放在主存中的必要；完成后，这些代码就没有存放在主存中的必要；第二章 存 储 管 理 56

54、2.4.3 虚拟存储器虚拟存储器u 从运行的时间角度来分析，在一段时间内，作业一从运行的时间角度来分析，在一段时间内，作业一般不会执行到所有程序段的指令和存取绝大部分数据，般不会执行到所有程序段的指令和存取绝大部分数据，它往往相对集中地访问某些区域中的指令和数据，这它往往相对集中地访问某些区域中的指令和数据，这就是程序运行的就是程序运行的“局部性原理局部性原理”。u在主存中可只装入最近经常要访问的某些区域的指令在主存中可只装入最近经常要访问的某些区域的指令和数据，剩余部分就暂时不必装入，等到以后要访问和数据，剩余部分就暂时不必装入，等到以后要访问到它们时再调入内存。到它们时再调入内存。u如果主

55、存较紧张，必要时可将已不大访问的信息调出如果主存较紧张，必要时可将已不大访问的信息调出内存，再执行调入操作。这样，程序运行时所需要的内存，再执行调入操作。这样，程序运行时所需要的实际内存就可以远小于程序的虚拟地址空间。实际内存就可以远小于程序的虚拟地址空间。第二章 存 储 管 理 57u由于作业的指令和数据可以存放在外存中，用户的程由于作业的指令和数据可以存放在外存中，用户的程序就不受实际内存大小的限制，好像计算机系统向用序就不受实际内存大小的限制，好像计算机系统向用户系统提供了容量极大的户系统提供了容量极大的“主存主存”，而这个大容量的，而这个大容量的“主存主存”是靠存储管理的软件和硬件通过

56、大容量的辅是靠存储管理的软件和硬件通过大容量的辅存作为后援存储器扩充而获得的，是程序设计员感觉存作为后援存储器扩充而获得的，是程序设计员感觉到的，而实际上并不存在的存储器，故称到的，而实际上并不存在的存储器，故称虚拟存储器虚拟存储器。u采用虚拟存储器技术究竟可运行多大的程序呢？当然采用虚拟存储器技术究竟可运行多大的程序呢？当然也不能无限大，它受到以下两个条件的限制。也不能无限大，它受到以下两个条件的限制。第二章 存 储 管 理 58u 指令地址字长的限制指令地址字长的限制。地址字长决定了程序所能访问。地址字长决定了程序所能访问的虚拟地址空间的大小，如对于的虚拟地址空间的大小，如对于32位字长的

57、地址字可构位字长的地址字可构成成4GB的虚拟地址空间。的虚拟地址空间。u 存放程序指令和数据的外存储器的大小存放程序指令和数据的外存储器的大小，这种外存叫，这种外存叫做交换设备，存放程序指令和数据的外存区域称为做交换设备，存放程序指令和数据的外存区域称为交换交换区区。u采用虚拟存储管理策略，在作业运行时就要由地址映像采用虚拟存储管理策略，在作业运行时就要由地址映像机构将程序的逻辑地址转换成内存的物理地址。此外，机构将程序的逻辑地址转换成内存的物理地址。此外，还要决定将虚拟地址空间中的哪一部分装入主存，装入还要决定将虚拟地址空间中的哪一部分装入主存，装入主存的位置以及当主存中的空闲区不够时将哪一

58、部分空主存的位置以及当主存中的空闲区不够时将哪一部分空间的内容调至交换区中。这些都是虚拟存储管理中要解间的内容调至交换区中。这些都是虚拟存储管理中要解决的新的技术问题。决的新的技术问题。第二章 存 储 管 理 592.5 2.5 纯分页的存储管理纯分页的存储管理 可变分区存储管理：连续分配存储空间。可变分区存储管理：连续分配存储空间。分页式存储管理：打破了分页式存储管理：打破了“连续连续”的禁锢，把的禁锢，把对存储的管理大大推进了一步。对存储的管理大大推进了一步。分页式存储管理是将固定分区方法与动态重定分页式存储管理是将固定分区方法与动态重定位技术结合在一起的一种存储管理方案，它需位技术结合在

59、一起的一种存储管理方案，它需要硬件的支持。要硬件的支持。第二章 存 储 管 理 602.5.1 分页存储管理的基本思想分页存储管理的基本思想u作业的虚拟地址空间划分成若干长度相等的页作业的虚拟地址空间划分成若干长度相等的页（page），也称虚页，每一个作业的虚页都从），也称虚页，每一个作业的虚页都从 0 开开始编号。始编号。u主存也划分成若干与虚页长度相等的页架主存也划分成若干与虚页长度相等的页架（frame），也称页框或实页，主存的页架也从），也称页框或实页，主存的页架也从 0开始编号。开始编号。u程序装入时，每一个虚页装到主存中的一个页架程序装入时，每一个虚页装到主存中的一个页架中，这些页

60、架可以是不连续的中，这些页架可以是不连续的。需要需要CPUCPU的硬件支的硬件支持持。第二章 存 储 管 理 61例：第二章 存 储 管 理 62 把用户程序按逻辑页划分成大小相等的部把用户程序按逻辑页划分成大小相等的部分，称为页。从分，称为页。从0 0开始编制页号，页内地址是开始编制页号，页内地址是相对于相对于0 0编址编址逻辑地址逻辑地址页号页号 页内地址页内地址用户程序划分用户程序划分例：页的大小为例：页的大小为4K4K相对地址相对地址51885188，对应数对（，对应数对（1 1，10921092）；）；相对地址相对地址92009200，对应数对（，对应数对（2 2，10081008）