内存管理

（一）程序执行过程

1.程序从外存载入内存

用户源代码以程序的形式存放在外存上，需要运行时通过三步将程序载入到内存中：编译、分类组装和载入。

image.png

• 第一步：将用户源代码编译成若干个目标模块
• 第二步：将目标模块及所需的库函数链接在一起形成完整的装入模块
• 第三步：由装入程序将装入模块装入内存运行

1.1 目标模块及所需的库函数的链接有哪些链接方式？

• 静态链接：程序运行前，将各个目标模块及它们所需的库函数链接成一个完整的可执行文件后不再拆开;
• 装入时动态链接：在装入内存时，边装入边链接；
• 运行时动态链接：在程序执行中需要目标模块时才进行链接

1.2 装入内存时有哪些装入方式?

• 绝对装入：适用于单道程序环境，绝对装入程序按照装入模块中的地址将程序和数据装入内存，不需要对程序和数据的地址进行修改。
• 静态重定位：适用于多道程序环境，根据内存的当前情况，将装入模块装入内存的适当位置，地址变换通常在装入时一次完成。一个作业若采用该方式装入内存，必须给它分配要求的全部内存空间，如果没有足够的内存，则不能装入该作业，而且一旦进入内存，整个运行期间不能在内存移动，也不能再申请内存空间。
  image.png

• 动态重定位：如果程序在内存中发生一道，需要采用动态的装入方式。即使把程序装入到内存中，也不立即转换地址，只有程序运行时才进行地址转换。使用这种方式可以将程序分配到一个不连续的存储区中，并且可以动态申请内存。

  
  image.png

2.逻辑地址和物理地址

上面提到，装入内存时的一个重要步骤是进行地址转换。需要进行地址转换的一个原因是，程序编译成若干个目标模块，每个模块都是从0号单位开始编址，这些地址称为逻辑地址；而物理地址是内存中物理单元的集合，它是地址转换的最终地址。因此当装入程序装入内存时，需要通过地址转换将逻辑地址转换成物理地址，这个过程叫做重定位。

（二）扩充内存

如果要同时运行多个程序，需要将这些程序全都装入内存中，但内存空间远远小于外存空间，一次无法载入多个内存大的程序，为了让这些程序都能运行，采用覆盖和交换技术对内存进行扩充。

image.png

1. 覆盖

覆盖技术主要用于一个程序或进程中。
实现原理：将内存划分为1个固定区和若干个覆盖区，把经常活跃的部分放在固定区，其余部分按照调用关系分段，首先把那些将要访问的段放在覆盖区，其他段放在外存中，在需要调用前，再把其调入到覆盖区中，替换覆盖区中原来的段。

image.png

• 优点：打破必须把一个外存的所有信息都装入到内存才能运行的限制；
• 缺点：如果需要调入的段的代码大于内存空间时，仍旧不能运行，此外，能够更新的范围只有覆盖区。

2. 交换

交换技术主要用于不同进程（作业）之间，其基本思想是把内存和外存的进程（作业）对调。
把处于等待态的程序从内存移到辅存，腾出内存空间，把需要竞争CPU运行的程序从辅存移到内存。

image.png

（三）内存空间分配

进程装入内存后，怎样存放才能使内存利用率最高？
有两类分配方法——连续分配和非连续分配。连续分配指的是为一个用户程序分配一个连续的内存空间。非连续分配允许一个程序分散地装入不相邻的内存分区。

1.连续分配

有三种连续分配方式：单一连续分配、固定分区分配和动态分区分配。

• 单一连续分配：将内存分为系统区和用户区，仅用户区被用于进程分配。这种分区方式用于单任务操作系统中，由于每次仅运行一道程序，会产生内部碎片，内存利用率极低。

image.png

• 固定分区分配：可使用两种方式对用户区进行固定分区，一种是大小相等的分区，另一种是大小不等的分区。每个分区只能装入一道作业，当有空闲分区时，才可以从外存的后备作业队列中选择合适大小的作业装入该分区，如此循环。
  image.png

由于被分区，需要建立分区表对其进行说明和管理。有程序要装入内存前，先通过分区表查找合适的分区，如果有合适的分区则装入，如果没有则拒绝。

image.png

优点：相较于单一连续法，可以装入多个进程；
缺点：可能会因为程序过大而无法装入任意一个分区，从而不得不使用覆盖技术；其次，容易产生内部碎片，内存利用率提升空间不大。

• 动态分区分配：不预先划分内存区域，而是在进程装入内存时根据进程大小动态创建分区。
  image.png

动态分区分配需要解决的一个问题是，如何把进程分配到合适的内存中。
（1）首次适应算法：把空闲分区按地址递增顺序链接，分配时顺序查找，找到大小能够满足的第一个分区；
（2）最佳适应算法：把空闲分区按容量递增形成分区链，找到第一个能满足要求的空闲分区；
（3）最坏适应算法：把空闲分区按容量递减形成分区链，找到第一个能满足要求的空闲分区；
（4）邻近适应算法：把空闲分区按地址递增顺序链接，分配时从上次查找结束的位置开始查找；

image.png

2.非连续分配

非连续分配方式下，将内存、程序裁剪成小块（4k），程序按块装入内存。内存被裁剪成小块后，提高灵活性，可以使程序分散地装入不相邻的内存分区。

有两种不同方式可实现非连续分配，根据分区的大小是否固定，分为分页存储管理方式和分段存储管理方式；在分页存储管理方式又根据运行作业时是否把作业的所有页面都装入内存才能运行分为基本分页存储管理方式和请求分页管理方式。

image.png

1. 基本分页存储管理方式

在连续分配管理中，使用固定分区会产生内部碎片，而使用动态分区会产生外部碎片，那么借鉴它们的优点，采用固定分区，将主存空间划分为大小相等的固定的块，而且块很小，同时进程也以块为单位划分，在执行时以块为单位申请内存。

由于进程、主存都划分为块，因此需要在进程、主存和主存物理地址建立对应关系，使用分页存储管理的逻辑地址结构来管理进程地址，在主存中建立页表用于为进程查找其在主存上的物理地址。

image.png

虽然将内存、进程及外存上的程序都分为大小相等的块，但是这些“块”有三个名称。外存上的程序所分成的块仍然称为“块”，进程上的每一块称为“页”，而主存上的块则称为“页框”。

如何使用每一页的逻辑地址和页表来查找其在内存中的物理地址？下图给出了示意图：

image.png

• （1）计算页号P（P=A/L）和页内偏移量W（W=A%L）(L为页面大小)
• （2）比较W与M，判断是否越界
• （3）计算页表中页号P的页表项地址(F+P*M)，取出页表项内容b，即物理块号。
• （4）再用b和W计算出内存的物理地址（E=b*L+W）

这些运算都硬件实现，所以查找速度快。但是存在一个问题，如果进程分页多，那么页表项也就变长，这样页表项占用主存大部分空间，因此引入快表，快表相当于cache，先通过快表查内存地址，若命中则直接返回物理地址，若不命中，则再计算页表项。

image.png

引入快表后，查找速率提高，但是没有解决页表项因为进程分页多而变长的问题，因此引入二级页表。
回想一下我们使用字典查字，首先根据字的大写拼音定位26个字母中的一位（一级查找），找到这个字母后，再在这个字母下方查找这个字的全拼（二级查找）。二级页表的实现原理同查字相同，它实际上是在原有页表结构上再加上一层页表。

image.png

2. 基本分段存储管理方式

分段存储管理是面向程序员提出的，目的是方便其编程、信息保护和共享及动态链接等各方面需求。
进程是根据自然段划分的，例如将一个进程划分为主程序、子程序、栈和一段数据，划分后的段都从0开始编制，进程被划分后自然需要建立逻辑地址结构来管理各个段。同时每个进程都有一张逻辑空间与内存空间映射的段表，示意图如下。

image.png image.png

分段系统的地址变换过程如图，

image.png

3. 段页式存储管理方式

段页式存储管理方式将页式存储管理提供内存利用率的方式和分段管理中对段的共享结合起来。
实现原理：
（1）将作业分段；
（2）每段分页；
（3）内存分块，进程仍以块装入内存中

image.png

由于作业既分段又分页，所以它的逻辑地址分为三部分：

image.png

段页式系统的地址变换如下：

image.png

（四）虚拟内存

虚拟内存的实现，是为了让内存看起来更大。在传统存储管理方式中，作业必须一次性全部装入内存后才能运行，这可能会导致作业太大不能全部装入内存而无法运行，或者只有少数作业能够运行；作用载入后就一直驻留在内存中，直到作业运行结束才会被换出，作业有可能处于长期等待状态，由于无法换出该作业，导致其他进程无法装入内存中。

虚拟内存的理论基础是局部性原理：时间局部性和空间局部性。

• 时间局部性：程序中的某条指令一旦执行，不久后该指令可能再次执行；某数据被访问过，不久后该数据可能再次被访问，这是因为程序中存在大量的循环操作。
• 空间局部性：一旦程序访问了某个存储单元，在不久后，其附近的存储单元也将被访问，这是因为指令通常是顺序存放、顺序执行，数据一般是以向量、数组、表等形式簇聚存储。

根据局部性原理，将程序的一部分装入内存，其余留在外存，就可以执行，执行过程中如果需要调用的信息不再内存，那么由操作系统将存放在外存中的信息调入，把暂时不使用的内容换出到外存上。从用户看来，好像系统内存增大一样，但实际上内存大小不变，这种看起来系统提供了一个比内存更大的存储器，叫做虚拟存储器。

image.png

与非连续分配一样，虚拟内存的实现方式也包括请求分页存储管理、请求分段存储管理和请求段页存储管理。这些实现方式都由页表机构、缺页中断机构和地址变换机构组成。

以请求分页管理为例，了解虚拟存储器的页表机构、缺页中断机构和地址变换机构的工作原理，内存与虚拟内存之间使用哪些算法完成页面置换，页面如何分配

1. 组成

在非连续分配中使用页式存储管理，以页为单位分割进程、内存，因此为进程建立地址结构管理页，在内存中通过页表项建立进程到内存物理地址的映射关系，而快表的引入是为了提高查找效率，压缩页表。

同理，在虚拟内存中使用分页请求管理方式，也需要页表机构、地址变换机构来实现分页请求管理，采用缺页中断机构对页表进行扩展。

1.1页表机构

由于作业并不是一次性全部调入内存，所以页表项不仅要记录页号、物理块，还要记录其他信息，方便调入调出操作。

image.png

1.2 缺页中断机构

在进程执行中需要的信息不在内存中，需要发起缺页中断，请求操作系统把所缺的页调入内存。如果此时内存中有空闲块，则直接调入，如果没有，则淘汰某页再调入。调入调出操作都要对页表项做出相应修改。

1.3 地址变换机构

请求分页的地址变换机构是在分页系统地址变换机构的基础上，增加修改页表、是否发起缺页中断这些功能而形成的。

image.png

2. 页面置换算法

页面可以采用4种方法将页面调入调出。

• 最佳置换
• 先进先出
• 最近最久未使用
• 时钟算法

2.1 最佳置换

将以后永不使用的页面或者未来长时间内不再访问的页面换出。但是这种算法无法预测哪些页面将来不再使用，无法实现，只能作为基准评价其他三种算法。

2.2 先进先出

优先淘汰最早进入内存的页面。这种算法容易高频率进行调入调出操作，因为有些最早进入内存的页面经常使用。

2.3 最近最久未使用

选择淘汰最近最久没有使用过的的页面，如果某个页面在一段时间内没有被访问，那么在最近的将来可能也不会被访问。

2.4 时钟算法

时钟算法通过循环扫描缓冲区来实现。缓冲区内的每个帧添加标识符，用于记录访问记录及修改次数，根据访问记录和修改次数的值来判断是否将该页面调出。

3.页面分配策略

页面分配策略要解决的问题是：给进程分配多少个页框？什么时候调入页面？从哪里调入？

3.1驻留集

每次给进程分配一定数量的页框，把这些页框看作是一个集合，形成驻留集

3.2 调入页面的时机

当发生缺页时，可以采用以下两种方法调入页面

• 预调页策略：根据局部性原理，一次性调入若干个相邻的页。
• 请求调页策略： 进程运行过程中访问的页面不再内存而提出请求，由操作系统将所需页面调入。

3.3 从哪调入页面

• 系统有足够的对调区空间：可以全部从对调区调入所需页面；
• 系统缺少足够的对调区空间：如果某个文件不会被修改，则直接从文件去调入，而对于那些可能会被修改的部分，需要从对换区调入调出；
• UNIX方式：从未运行过的页面都从文件区调入，而运行过的放在对换区。