操作系统的内存管理（上）

实现内存的分配，内存的回收等基本内存管理功能。提高内存的利用率和内存访问速度。

内存管理的目标

实现内存的分配，内存的回收等基本内存管理功能。提高内存的利用率和内存访问速度。

存储的层次结构

存储系统是一个具有不同容量，成本和访问时间的存储设备的层次结构。

层次系统中，从高层到低层（L0 ～ L5），较低存储设备速度更慢，容量更大，价格更便宜。

L0 CPU 寄存器，可以在一个时间周期内访问。

L1 芯片内的 L1 高速缓存（SRAM）1～10 个周期内访问 。

L2 芯片外的 L2 高速缓存（SRAM）1～10 个周期内访问 。

L3 主存（DRAM），50 ～100 个周期内 。

L4 本地二级存储，2000 万个周期 。

L5 远程二级存储。

程序的执行遵循局部性原理

程序执行的局部性原理指出，程序在执行时呈现出的局部性规律，即在一段较短的时间内，程序的执行仅局限于某个部分，相应地，它所访问的存空间也局限于某个区域。

论点

1. 程序在执行时，除了少部分转移和过程调用指令外，在大多数的情况下都是顺序执行。

2. 过程调用将会使程序执行轨迹有一部分内存区域转到另外一部分内存区域。但研究表明，在大多数情况下，过程的调用深度不超过 5 。这就是说，程序将会在一段时间内局限在这些过程的范围内运行。

3. 程序中存在很多循环结构，它们虽然由少量指令构成，但多少次执行。

4. 程序中往往包括许多对数据结构的处理。如对数组进行操作，它们往往局限在很小范围内。

表现方式

时间局部性

如果程序中的某个指令一旦被执行，则不久后该指令可能再次被执行。如果某个数据结构被访问，不久后该数据结构可能再次被访问。

空间局部性

一旦程序访问了某个单元，在不久之后，其附近的存储单元也将被访问。

程序的链接和装入

高级语言程序必须经过编译，链接才能成为可执行程序，操作系统需要为程序的执行分配内存空间。链接程序不属于操作系统的构成部分，但是它为操作系统提供了可装入的程序模块。链接程序要解决的问题是将编译后的目标模块装配称一个可执行程序。

根据链接进行的时间和实现方式不同

静态链接

静态链接是在程序运行前，用链接程序将目标模块链接成一个完整的装入模块。

静态链接程序的任务

对逻辑地址进行修改将独立模块的逻辑地址空间链接成一个连续的地址空间。变换外部调用符号每一个模块中的所用的外部调用服务号都变为逻辑地址。

静态链接相对动态链接而言，程序运行速度较快。但是无论程序在本次运行中会不会被执行，都将全部链接到一个可执行文件中，使可执行文件比较大，占用外存空间较大，使存储开销较大。

另位静态链接的方式，程序不够灵活，方便。修改某一个模块会导致整个程序重新链接。

动态链接

动态链接，可以将目标模块的链接推迟到这些模块中函数被调用执行时在进行。即在程序执行时，若发现一个被调用模块未被链接，再把它链接到调用者模块上。

采用动态链接的优点是节省了内存和外存空间，方便程序开发。但由于动态链接是在程序运行过程中从外存将调用模块装入内存并链接到调用者模块上的，这需要运行时间的开销，是程序运行的速度变慢。

程序的装入

将一个用户的源程序变为一个可以在内存中执行的程序，通常要经过编译，链接，装入 3 个阶段。

不同阶段，程序地址有着不同的表现形式。

物理地址 = 有效逻辑地址 + 程序在内存中的起始地址。

源程序中的地址通常是符号表现，如，一个整型的 counter。

编译器将这些符号地址变成可重定位的地址，通常是现对于本模块的开始为止的地址。如，被编译的的模块的起始地址为 0，所有符号转变成相对于 0 开始的逻辑地址。

链接程序把几个目标模块的逻辑的地址转变为相对于整个可以执行程序的起始地址的逻辑地址。每一层地址的变换都是从一个地址空间到另一个地址空间的映射。

绝对装入方式

编译程序事先已知程序在内存的驻留位置，编译时产生物理地址的目标代码，绝对装入程序按照装入模块的物理地址将程序和数据装入内存。

可重定位装入方式

1. 在多道程序系统中，众多用户进程共享内存空间，什么时候空闲，内存的哪一块内存空闲，可以让操作系统在此装入一个新进程是无法预知的。因此，编译器在编译程序时无法形成物理地址。

2. 如果编译器不知道目标程序将驻留在内存中的什么位置，那么编译时就必须生成可重定位的代码，其地址都是逻辑地址，在程序装入内存时，再把这些逻辑地址映射到物理地址。

3. 特点

编译器是目标模块的起始地址从 0 开始程序装入时。

装入程序根据内存的使用情况将装入模块装入某个位置，并对模块进行重定位。

动态运行时装入

1. 进程装入内存后，可能从内存的一个区域移动到另位一个区域，这种情况可能发生在支持虚拟存的系统中。一个进程在被换出之前所在的内存位置与后来被从外存重新调入的内存所在地址不同，这种情况下，地址映射必须延迟到进程执行时再进行，把这种方式成为动态运行时装入。

2. 系统将程序装入内存后，由于进程在内存中的位置可能方式移动，所有此时并不计算物理地址，而是在进程运行访存过程中才进行地址转换，这种方式需要重定位寄存器的支持。

3. 当进程获得 CPU 运行时，系统把该进程在内存的其实地址存入重定位寄存器中，进程在运行过程中访存时，通过重定位寄存器和被访问单元的逻辑地址计算出被访问单元的物理地址。

连续分配存储的管理方式

单一连续分配方式

1. 内存中只有一个用户区，任意时候内存只能装入一道程序，这种分配方式仅适用于单用户，单任务系统。

2. 适用于单用户，单任务操作系统，它内存分为系统区和用户区。系统区仅供操作系统使用，用户区供用户使用。

3. 系统区用于驻留操作系统，用户区用于分配用户进程使用。为了防止用户程序对操作系统的破坏，保证系统的安全，可靠，在操作操作系统应考虑设置存储器保护机制。

在单用户，单任务操作系统中常用的方式是设置一个基址寄存器和一个界限寄存器。

1. 基址寄存器存放物理地址内存中的最小地址。

2. 界限寄存器存放装入用户程序的地址范围。

有些单用户，单任务的操作系统，没有设置存储器的保护机制 。理由如下。

1.节省硬件

2.单任务用户系统中，用户独占机器，对系统的破坏只可能是用户自己造成的，后果也不严重，不会影响其他用户的执行，而且操作系统很容易重装和在此重启。

固定分区分配方式

1. 将内存用户区域划分成若干固定大小的区域，每个区域驻留一道程序。

2. 内存的用户区被划分成几个分区，运行几个进程并发运行。当有一个空闲分区时，可从外存的后备队列中选取一个大小适当的作业装入该分区。当该作业结束时，释放所占用的分区，系统游客从后备作业队列中找到另一个作业调用该分区。

划分内存的方法

固定分区的用户分区数量是固定的，每个分区的大小也是固定的，大小可以相等，也可以不相等。

分区大小相等

在这种设计中，把用户区划分成大小相等的若干分区。

缺点是内存的利用率低

这种设计主要用于一台计算机区控制多个大小相等对象的场合。

分区大小不相等

为了更好的利用内存，可以将用户划分成大小不同，数量固定的若干分区。

为用户进程分配空间时，把大小最接近的空闲分区分配给申请内存的空间进程。使小进程占小分区，大进程占大分区，减少内存浪费。

支持固定分区分配的数据结构

固定分区说明表

1. 必须定义一个记录用户分区大小和使用情况的数据结构

2. 分区编号，分区大小（KB），分区器起始地址（KB），分区状态（已分配/空闲）

固定分区的分配过程

1. 需要为进程分配内存时，操作系统执行内存分配程序，搜索内存分区使用表。

2. 当找到一个大小大于或等于进程需要的内存空间且处于空闲状态的用户分区时候。

3. 将该分区分配个进程，并将该分区的状态修改为“已占用”。

固定分区的回收

1. 当进程运行结束后，系统要回收进程占用分区。

2. 同执行内存会程序完成回收操作。

3. 只需要把回收分区的使用状态改为 “空闲”。

动态分区分配方式

1. 由于固定分区分配将内存空间划分成大小固定的分区，当运行需要的内存空间比分区大的进程时，固定分区无法满足要求。而当运行只需要很小空间的进程，内存空间浪费大，使用固定分区分配内存利用率低，难以提高系统的多道程序度。动态分区分配根据进程的实际需要，为进程分配大小何时的内存区域。系统中用户分区的数量和大小都是动态变化的。

2. 系统动态的对内存进行划分，根据进程需要的空间大小分配内存。内存中分区大小和数量变化的。动态分区方式比固定分区方式显著提高了内存的利用率。

动态分区原理

系统初始只有一个大空闲区，当进程请求空间时，由系统根据进程需要的空间的大小划分出一片空闲分区给进程。系统运行一段时间后，内存的空闲区可能散布在不连续的区域。系统维护一个记录当前空闲分区情况的数据结构，当进程请求内存时，系统从所有空闲区中找到大小何时的空闲区域进行分配。系统中分区的大小和数量都是变化的，空闲区的大小和数量也是变化的。

动态分区中的数据结构

空闲分区表

系统在空闲分区中为每一个空闲分区建立一个表项。每一个表中包括 分区编号，分区大小，分区起始地址。

缺点是设置太多表项会浪费内存空间，设置太少的表项，当空闲分区较多时，无法记录说有空闲分区的情况。在实现时，结构数组大小不容易确认。

空闲分区链

使用空闲分区链可以动态的为每一个分区建立一个结点，每个结点包括分区大小，分区起始地址，指向前一个空闲分区结点的指针，及指向后一个空闲分区的结点的指针。空闲分区链中的每一个结点占用的内存可以动态分配，动态回收。使用空闲分区链可以克服空闲分区表存在的缺陷。

动态分区分配算法

• 首次适应算法 FF（First Fit）

在采用空闲分区链作为结构时，首次适应算法要求空闲分区链已地址递增的顺序链接。

在进程内存分配时时，在链首开始顺序查找，直到找一个能满足进程大小要求的空闲分区为止。然后将按照进程请求的大小，从该分区中划出一块内存分配给请求者，剩余空闲分区仍然保留在空闲链中。

缺点是该算法总是先分配低地址部分的内存空间，容易使低地址部分留下小分区，而高地址部分大空闲较多。当进程请求大内存空间时，找到合适的空闲分区，搜索空闲分区链需要时间的开销比较大。 低地址部分的空闲分区被反复划分，可能留下许多难以利用的很小的分区，这种难以被利用的小空闲区被成为外部碎片或外碎片。分配给进程的分区若大于进程的分区，分区内会存在一部分不被利用的空间，这部分浪费的空间被成为内部碎片或内碎片。

• 循环首次适应算法 NF （Next Fit）

该算法是由首次适应算法演变形成的。在为进程分配空间内存时，不再每次从链首开始查找合适的空闲分区，而是从上次查找的空闲分区的下一个空闲分区开始查找，直到找到第一个满足要求的空闲分区，并从中划出一块于请求大小相等的内存空间分配给进程，为实现算法，应设置一起始查找指针，以指向下一次起始查找的空闲分区，并采用循环查找方式。

优点 空闲分区分布均匀，查找开销小，

缺点 容易使系统缺乏大空闲区。

• 最佳适应算法 BF（Best Fit）

该算法在每次作业分配内存，总把大小于进程所请求空间大小最接近的空闲分区分配个进程，避免了“大材小用”，为为了加速寻找，该算法要求将所有空闲分区安全分区大小递增的顺序形成一个空闲分区链。这样第一次找到的满足要求的空闲分区必然是最接近进程需要的内存空间大小。

优点 避免了 “大材小用”，提高了内存的利用率。

缺点 容易留下难以利用的小空闲区。

动态分区的分配和回收

分配流程

1. 进程申请的内存空间大小为 u.size ,当前结点对应的空闲分区大小为 m.size ，size 是系统规定的一个阀值。

2. 检索空闲分区链，找到满足条件的空闲分区（m.size >= u.size） 。

3. 如果 m.size - u.size <= size，则之间把该分区分配给进程。否则，从 m.size 中划出大小为 u.size 的空间分配给进程。把剩余的大小为 m.size -u.size 的空闲空间作为新的空闲分区。

4. 将分配给进程分区的起始地址返回给内存分配程序的调用者。

5. 修改空闲分区链表。

内存回收

内存回收的任务是释放被占用的内存区域，如果被释放的内存空间与其他空闲分区在地址上相连，还需进行空间合并。

1.释放一块连续的内存区域。 如果被释放的内存区域与其他空闲区域相邻，则合并空闲区域。

空间合并的 3 中情况

1.仅回收区域的前面有相邻的空闲分区（R1）。

把回收区域与 R1 合并成一个空闲分区，把空闲分区链中与 R1 对应的结点的分区起始地址作为新 的空闲分区的起始地址，将该结点的分区大小修改为被回收的空闲分区与 R1 分区的大小之和。

2.仅回收区域的后面有相邻的空闲分区（R2）。

把回收区域与 R2 合并成一个空闲分区，把空闲分区链表与 R2 对应的结点的分区起始地址修改为回收区的起始地址，将该结点的大小修改为 R2 与回收区的大小之和。

3.回收区域的前（R1），后（R2）都有相邻的空闲分区。

回收区与 R1，R2 合并成一个空闲分区，把空闲链中与 R1 对应的结点其实地址作为新的合并后的空闲分区的起始地址，该结点的大小修改为 R1 + R2 + 回收区 三者的大小之和。删除与 R2 分区对应的空闲分区的结点。当然也可以修改分区 R2 的结点，而删除 R1 的结点，还可以为合并的新的空闲分区新建一个结点，同时删除 R1 和 R2 对应的结点。

2.修改空闲分区链。

欢迎大家的留言讨论。按惯例最后分享一首诗给大家。

一架水车在水中旋转。

一颗孤星和月亮一起转动。

我们生活在这夜的海洋上，不知道

这些灯盏是什么。