操作系统-内存管理

内存管理的概念

内存空间的分配与回收

为了更好能适应不同大小的程序要求和提高内存的利用率，就需要对内存空间进行分配与回收。

覆盖与交换

覆盖于交换技术是在多道程序环境下用来扩充内存的两种方法。

1. 覆盖技术

   覆盖技术的思想就是将程序分为多个段。常用的段常驻内存，不常用的段在需要时调入内存。

   常驻内存的段放在“固定区”中，调入后就不再调出（除非运行结束），

   不常用的段放在“覆盖区”，需要用到时调入内存，用不到时调出内存。

   缺点：由于必须由程序员声明覆盖结构，操作系统完成自动覆盖。对用户不透明，增加了用户编程负担

2. 交换技术

   交换技术的思想技术当内存空间紧张时，系统将内存某些进程暂时换出外存，把外存中某些以具备运行条件的进程换入内存（类似进程在内存与磁盘间动态调度）。

连续分配管理方式

连续分配是为用户程序分配一个连续的内存空间。

单一连续分配

在单一连续分配方式中，内存被分为系统区和用户区。系统区通常位于内存的低地址部分，存放操作系统相关数据；用户区用于存放用户进程相关数据。

在单一连续分配中，内存只能有一道用户程序，用户程序独占整个用户区空间。

优点：实现简单，无外部虽破；可以采用覆盖技术扩充内存；不一定需要采取内存保护。

缺点：只能用于单用户、单任务的操作系统中；有内部碎片（即分配给某进程的内存区域中，有些没有用上的部分就称内部碎片）；存储器利用率极低。

固定分区分配

固定分区分配就是将整个用户空间划分未若干个固定大小的分区，在每个分区中只装入一道作业。

固定分区分配分为分区大小相等和分区大小不等两种情况。

分区大小相等：会缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合。

分区大小不等：增加了灵活性，可以满足不同大小的进程需求。根据常在系统中运行的作业大小情况进行划分。

优点：

实现简单，无外部碎片。

缺点：

当用户程序太大时，可能所有分区都不能满足需求，需要采用覆盖技术来解决，这回导致性能降低；

会产生内部碎片，内存利用率低。

动态分区分配

动态分区分配又称为可变分区分配。这种分配方式是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。

动态分区没有内部碎片，但有外部碎片。

内部碎片，分配给某进程的内存区域中，如果有些部分没有用上就称没有用上的部分为内部碎片。

外部碎片，是指内存中某些空闲分区由于太小而难以利用，而没有用上的部分就称外部碎片。

可以通过紧凑（拼凑，Compaction）技术来解决外部碎片，紧凑即对内存中进程的位置进行挪位，从而减去外部碎片。

动态分区分配算法

• 首次适应算法

  首次适应算法使每次都从低地址开始查找，找到第一个能满足大小的空间分区。

• 最佳适应算法

  最佳适应算法是由于动态分区分配是一种连续方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证留有大片的连续空间，会优先使用更小的空闲区。

  缺点：每次都选最小的分区进行分配，会留下越来越多难以利用的外部碎片块。

  实现：会让分区的数据结构根据容量递增次序排序，找到满足大小的第一个空闲分区。

• 最坏适应算法

  为了解决最佳适应算法的问题，该算法会优先使用最大的连续空闲区，这样分配后的剩余空间区就不会太小，更方便使用。

  实现：会让分区的数据结构根据容量递减次序排序，找到满足大小的第一个空闲分区。

  缺点：会导致之后有“大进程”到达就没有内存分区可以使用。

• 邻近适应算法

  该算法每次查找都会从上次查找结束的位置开始检索，找到第一个能满足大小的空间分区。

基本分页存储管理

页式存储就是将内存分为一个个大小相等的分区，每个分区就是一个“页框”（也称内存块、物理块）。每个页框有一个编号，即“页框号”（也称内存块号、物理块号），页框号从0开始。

将进程的逻辑地址空间页分为与页框大小相等的一个个部分，每个部分称为一“页”或“页面”。每个页面也有一个编号，即“页号”，也会也是从0开始。

根据内存块数列计算页表项的字节数：

例：假设某系统物理内存大小为4GB，页面大小为4KB，则每个页表项至少应该为多少字节？

由题可得内存块数：
$$
内存块数=\frac{4GB}{4KB}=\frac{2^{32}B}{2^{12}B}=2^{20}块
$$
所以内存块号的地址范围应该是0~$2^{20}-1$

所以内存块号至少要20bit来表示。

换成字节为3B来表示块号。

在页表中页号无需计算，是隐含的（类似于数组）。

基本地址变换机构

基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址。

通常会再系统中设置一个页表寄存器（PTR），存放页表再内存中的起始地址F和页表长度M。

注：页面大小是2的整数幂

页面逻辑地址到物理地址的转变过程如下：

具有快表的地址变换机构

快表，又称联想寄存器（TLB, translation lookaside buffer），是一种访问速度比内存快很多的高速缓存，用来存放最近访问的页表项的副本。

快表的功能和cache差不多，快表会存放最近使用的页表项，然后下次访问若命中就可以直接通过快表获得物理地址，增加了查表的速度。

基于局部性原理，一般快表的命中率可以达到90%以上。

基本地址变换机构和具有快表的地址变换机构的区别

两级页表

为了解决单级页表中：

• 页表必须连续存放，当页表很大时，需要占用很多个连续页框。
• 无需整个页表常驻内存，因为进程在一段时间可能只访问某几个特定的页面。

的问题，就需要使用两级页表。

两级页表实现离散分配就是为页表在建立一张页表，称为页目录表。

若想让页表不常驻内存，可采用虚拟存储技术，在页表项中增加一个标志位，用于表示该页面是否已经调入内存。

使用二级页表需要注意的细节:

• 若采用多级页表机制，则各级页表的大小不能超过一个页面

• 两级页表的访存次数分析（不采用快表）

  第一次访存：访问内存中页目录表。

  第二次访存：访问内存中二级页表。

  第三次访存：访问目标内存单元。

虚拟内存管理

虚拟内存的的定义和特征

虚拟内存是基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。

在执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后执行。

若内存不够，由操作系统负责将内存暂时用不到的信息换出到外存。

在操作系统的管理下，在用户看来似乎有比实际大得多的内存，这就是虚拟内存。

虚拟内存的三个特征：

• 多次性：无需在作业运行时一次性全部装入内存，而是允许被分成多次调入内存。
• 对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出。
• 虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。

由于连续分配方式不方便实现虚拟内存技术，所以会建立在离散分配上实现虚拟内存技术。

与传统的非连续分配存储管理的区别：

在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行。

若内存空间不够，由操作系统负责将内存暂时用不到的信息换出外存。

请求分页管理方式

在请求分页管理系统中，当访问的页面不在内存时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。

此时缺页的进程阻塞，等调页完成后再将其唤醒，放回就绪队列。

如果内存中有空闲块，则为进程分配一个空闲块。

如果内存中没有空闲块，则有页面置换算法选择一个页面淘汰，若该页面再内存期间被修改过，则要写回外存。未经修改无需写回。

页面置换算法

最佳置换算法（OPT）

最佳置换算法时每次选择淘汰的页面将是以后永不使用，或者再最长时间内不再被访问的页面，这样可以保证最低的缺页率。

例：假设有三个内存块，并考虑到有一下页面号引用串（会依次访问这些页面）：

7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

通过最佳置换算法可得：

每当内存块满时换出最长时间不被访问的页面号。

最佳置换算法可以保证最低的缺页率，但实际上，只有再进程执行的过程中才能知道接下来会访问哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的。

先进先出置换算法（FIFO）

每次选择淘汰的页面是最早进入内存的页面。

例：假设系统为某进程分配了三个内存块，并考虑到有以下页面号引用串：

3，2，1，0，3，2，4，3，2，1，0，4

Belady异常：当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。

在所有置换算法中，只有FIFO算法会产生Belady异常。虽然FIFO算法实现简单，但由于算法与进程实际运行时的规律不适应，算法性能较差。

最近最久未使用置换算法（LRU）

每次淘汰的页面是最近最久未使用的页面。

在该算法会为每个页面添加一个访问记录字段，该字段用于记录上次被访问依赖所经历的时间。

例：假设系统为某进程分配了四个内存块，并考虑到有以下页面号引用串：

1，8，1，7，8，2，7，2，1，8，3，8，2，1，3，1，7，1，3，7

在实际做题只需逆向检查此时内存中的页面号最后一个出现的页号就是要淘汰的页面。

该算法的实现需要专门的硬件支持，虽然算法性能好，但是实现困难，开销大。

时钟置换算法（CLOCK）

时钟置换算法又称最近未用算法（NRU），时钟置换算法又分为简单的CLOCK算法和改进的CLOCK算法。

• 简单的CLOCK算法。为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位置为1。若访问位为0，表示最近没被访问过。

  当CLOCK扫描过后会将该页面的访问位置为0，所以第二轮扫描必定会有访问位为0的页面。（简单的CLOCK算法淘汰页面最多会经历两轮扫描）

• 改进型的时钟置换算法。该算法除了考虑一个页面最近有没有被访问过之外，还会考虑该页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面。

  在该算法会为页面增加一位修改位，若修改位为0，表示没有被修改过，为1，表示页面被修改过。假设各页面状态以（访问位，修改位）形式表示。

  ​ 算法规则：将所有可能被置换的页面排成一个循环队列

  ​ 第一轮：从当前位置开始扫描到第一个（0，0）的帧用于替换。本轮扫描不修改任何标志位。

  ​ 第二轮：若第一轮扫描失败，则查找第一个（0，1）的帧用于替换。本轮将所有扫描过的帧访问位设置为0。

  ​ 第三轮：若第二轮扫描失败，则查找第一个（0，0）的帧用于替换。本轮扫描不修改任何标志位。

  ​ 第四轮：若第三轮扫描失败，则查找第一个（0，1）的帧用于替换。

  改进型CLOCK置换算法最多会进行四轮扫描。

页面分配策略

驻留集：指请求分页存储管理中给进程分配的物理块的集合。

采用虚拟存储技术的系统中，驻留集大小一般小于进程的总大小。

置换策略

在请求分页系统中，可采取固定分配和可变分配两种内存分配策略。在进行置换时，可采用全局置换和局部置换两种策略。

固定分配：操作系统位每个进程分配一组固定数目的物理块，在进程运行期间不可改变。即驻留集大小不变。

可变分配：操作系统位每个进程分配一定数目的物理块，在进程运行期间可改变。即驻留集大小可变。

局部置换：发生缺页时只能选进程自己的物理块进行置换。

全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。

可变分配全局置换：只要缺页就给分配新物理块。

可变分配局部置换：要根据缺页的频率来动态地增加或减少进程的物理块。

抖动现象

刚刚换出的页面马上又要换入内/外存，这种频繁的页面调度行为称为抖动，或颠簸。产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数。

工作集

为了减少抖动现象，就提出了工作集的概念。

工作集指在某段时间间隔里，进程实际访问页面的集合。

操作系统会根据“窗口尺寸”来算出工作集。

例：

某进程的页面访问序列如下，窗口尺寸为4，各时刻的工作集为：

工作集大小可能小于窗口尺寸，实际应用中，操作系统可以统计进程的工作集大小，根据工作集大小给进程分配若干内存块。