存储器管理

因为我们的可执行程序需要 load 到内存之后才能够进行执行, 而每个程序(进程) 都在同一块物理内存上进行分配内存地址, 就会产生分配与管理方面的问题, 所以需要通过一些规则为程序进行分配内存空间.

内存分配与管理方式

在60-80年代的时候, 由于硬件条件, 软件条件多个方面的限制, 操作系统都停留在只允许一个或少许的程序运行, 于是需要管理的内存空间就不是很复杂, 只需要对内存进行连续的分配即可, 所以最初时期采用连续分配的方式

连续分配存储管理方式

单一连续分配

在单道程序环境下, 内存的管理方式是分为 系统区 和 用户区, 由于只有单个应用程序, 所以可以直接进行分配, 而不会产生内存分配的冲突.

区分用户区和系统区主要就是为了提高系统的健壮性 和 安全性 当然也可以不进行用户区和系统区的区分, 因为单道程序下的单用户场景下, 不会存在其他用户的干扰, 即使应用程序出现破坏现象也不会很严重.

固定分区分配

在后续发展过程中, 为了实现多个应用程序一同执行, 出现了 多道处理程序系统, 由此为了能够在内存中装入多个程序, 于是将整个内存分为几个固定大小的分区, 每次要调入程序执行时, 如果有空闲块就装入对应的块儿中进行运行.

两个问题:

1. 块儿的大小如何确定?
   1. 分区大小相等: 缺乏灵活性, 程序太小时, 会造成大量的内存浪费, 当程序太大时, 会导致一个分区装不下的情况, 导致无法装配运行
   2. 分区大小不等, 增加了灵活性, 分配为大小不等的几个块,
2. 内存分配
   1. 将内存块儿进行排序, 并且通过一张内存分配表, 内部记录起始地址, 大小, 以及使用状况
   2. 当进行分配时, 根据排序进行检索出一个未使用的最佳的块儿进行分配, 否则拒绝分配

分区大小固定后, 必定会导致内存浪费, 但是某些用于控制多个相同对象的控制系统中, 程序是已经编好的, 也是可以使用的

动态分区分配(可变分区分配)

动态分配就是根据进程的需要,动态地为之分配内存空间, 实现动态分配, 需要使用到 数据结构, 分区分配算法 , 分区的分配和回收 等操作

可以这样理解, 我们想要实现动态的分配内存, 主要做的就是内存的分配和回收工作, 肯定需要通过数据结构来表示空闲分区, 而具体选择什么样的分区进行分配 则需要考虑分配算法了 (程序 = 数据结构 + 算法)

首先是数据结构, 因为后续的所有操作, 都是针对于这些数据结构进行的, 想一下如果是我们进行设计, 需要怎么表示呢?

第一种方式: 使用一张表(二位数组)来表示空闲的内存块

第二种方式: 使用双向链表将空闲内存块通过前向指针和后向指针链接.在分区的头部 设置一些用于控制分区分配的信息, 当然为了检索方便, 也会在尾部进行重复设置分配状态以及分区大小

有了数据结构, 我们就需要算法去操作, 查找合适的分区进行分配, 既然是找无非就是索引 和 顺序搜索, 而对于内存块儿的查找也正存在这两种方式:

1. 基于顺序搜索的动态分配算法\

   1. 首次适应算法
      1. 每次都从低地址(首部)开始查找, 找到能满足要求的空闲分区, 将分区进行划分, 多余的部分留在空闲链中, 如果从链首到链尾都未能找到就失败返回
      2. 每次都从低地址开始, 不断被划分, 造成很小的内存难以利用, 形成碎片
      3. 但是为大对象的分配预留了高地址的空间
      4. 每次从头查找会增加一定的查找时间消耗
   2. 循环首次适应算法
      1. 不再是每次从低地址开始查找, 而是从上一次分配的末尾位置开始查找
      2. 减少了查找的时间开销, 但是可能会造成大对象分配的问题
   3. 最佳适应算法
      1. 将空闲链进行排序, 每次找最佳的, 避免大材小用
      2. 虽然总体上看是最好的, 但是每次都会找最小的满足需求的, 这样就会让每次划分后剩余的内存空间都是最小的, 导致内存碎片的产生
   4. 最坏适应算法
      1. 与最佳适应算法正好相反, 每次找最大的
      2. 这对中小型作业较为友好

         我们想一下基于顺序的匹配方法有什么缺点吗 ? 当然, 顺序搜寻匹配 时间复杂度是 O(N) 的, 所以当数据量达到一定量后, 势必会造成性能上的损耗, 所以我们可以使用 索引的方式进行实现

2. 基于索引的动态分配算法

   1. 快速适应算法
   2. 伙伴系统
   3. 哈希算法

      其中的快速适应算法和哈希算法都是为每一类的内存块都设置一个空闲链表, 然后通过一张索引表来记录类别 和 头节点的地址, 当需要分配时, 就从索引表中获取头节点, 然后继续分配,, 注意该算法下, 是不会对内存块进行切割的

有了算法和数据结构之后, 我们知道怎么找到合适的内存块进行分配了, 那么就需要进行 内存的分配 与 回收操作

1. 分配, 如果找到了合适的内存块, 就将其首地址返回, 否则失败返回
2. 回收, 根据回收区的首址在空闲链表上找到插入点, 根据4种不同情况(与前后空闲块的关系)进行合并 与 链接

对换

想一下, 我们在连续分配存储管理方式下, 如果找不到合适的内存块是会直接返回失败, 即应用程序无法加载到内存中, 自然也就无法运行, 如果说在内存中加载的应用程序由于阻塞, 导致了cpu闲置, 而此时外存中又存在一批应用程序因为内存问题无法运行, 显然这样的硬件利用率是很低的. 所以为了提高内存的利用率, 提高系统的吞吐率, 让有机会运行的进程能够运行 提出了 对换技术

在具有对换功能的 OS 中, 磁盘一般被划为两个区, 一个文件区, 一个交换区(例如 Linux 中的交换区就为 /swap)

对换技术对换的类型可以分为两种:

1. 整体对换: 即将整个进程对换, 这也称为 CPU的中级调度
2. 部分对换: 以进程中的一个 分页 / 分段 进行对换

关于对换区中内存的分配问题:
首先, 进程在对换区中驻留的时间是不会太长的, 并且对换区的操作频率也是很高的, 所以我们更想要的是提高换入和换出的速度, 所以对换区采用连续分配的方式, 所以就类似于我们采用连续方式在内存中分配内存块一般. 采用动态分区 中的 首次适应算法, 循环首次适应算法, 最佳适应算法. 对内存的分配操作以及回收操作也是一致的.

进程的换入与换出

什么情况下需要进行换入和换出操作呢? —— 肯定是当我们的系统执行某个操作时, 发现内存不足, 就会进行对换操作, 对换操作是通过一个对换进程来实现的.

进程换出

1. 选择可换出的进程: 内存中, 首先找到阻塞状态 or 睡眠状态的, 如果有多个, 就优先选择优先级较低的, 如果所有阻塞的 和 睡眠的进程都被调出 内存仍然不够的话, 就会选择优先级低的就绪进程换出 (注意: 共享的数据段和程序段不能被换出)
2. 换出操作: 首先在交换区分配空间, 分配成功则启动磁盘传送到交换区中, 并修改 PCB 中的进程状态 , 如果此时还有可以换出的进程, 则继续执行换出进程, 直到没有阻塞进程为止.

进程换入

对换进程会定时执行换入操作, 首先查看PCB集合中所有进程的状态, 找到 “就绪 且 换出” 的进程, 如果存在多个这种进程, 就选择换出时间最久的(2s以上), 为其申请空间, 申请失败则掉调用进程换出腾出足够的空间后再进行换入操作.

成功对换后, 如果还有可以换入的进程, 则继续进行换入换出过程, 直到外存中没有 “就绪 且 换出” 的进程, 或者已经没有足够的内存来支持换入内存操作, 此时才停止进程的换入

由于交换一个进程需要很多的时间, 因此, 对于提高处理机的利用率而言, 并不是一个非常有效的解决方法, 目前较多的解决方案是, 在处理机正常运行时, 不开启对换程序, 而是当发现很多进程在运行时经常发生缺页异常 且 显现出内存紧张的情况, 才启动对换程序, 将一部分进程调至外存, 如果发现所有进程的缺页率都已经明显减少, 系统的吞吐量已经下降就可以暂停运行对换程序

分页存储管理方式

早先的连续分配存储的分配方式会导致很多内存碎片的产生, 虽然可以通过”紧凑”(移动内存块, 并且数据使用执行时动态链接的方式)来拼接内存碎片形成较大的内存空间, 但是这无疑是一笔较大的开销, 所以为了充分的利用内存空间, 就有了离散的将一个进程放入不邻接的内存块中

将内存分块, 进程分页, 分别进行编号 #1页 #2页….. , #1块, #2块……
然后分配时就可以进行离散的分配, 每一页对应到每一块内存上, 如:

当进程需要访问某一个数据时, 就会计算出在第几页上, 以及在该页上的偏移量, 然后查找对应的物理块, 显然我们还需要构建一张 页 与 内存块对应的表, 用于定位物理内存位置

因为在进程执行过程中, 需要对程序和数据进行地址变换, 这是一个很频繁的过程, 所以这个过程我们就需要使用硬件来实现, 通过一个页表寄存器 PTR(page table register)存放页表相关的一些信息, 寄存器是最接近CPU运行频率的存储方式, 但是成本也很高, 一个程序通过页表来表示, 可能会有几千上万个页, 如果都通过寄存器存放的话, 成本太高, 显然是不可能的, 所以页表实际上仍然是存放在内存中的, 页表寄存器中只存放 页表的起始地址, 以及页表的长度, 每个进程都有自己对应的页表, 所以当调用不同进程时, 也会为页表寄存器存储不同进程的信息.

虽然页表存放在了内存中, 但是访问过程中, 需要先在内存中页表中定位物理块, 然后再次访问对应的内存块获取实际的数据/指令, 这样就会有两次访问内存, 已经是很慢.

为了提高速度, 再次增加了一个寄存器 —- “联想寄存器” / 快表, 每次查找时先从快表中查找, 如果找到就直接进行对应物理地址的访问, 如果未找到, 就只有通过 2 次访问内存的方式获取, 获取后会先存入 快表 中, 然后才返回给上层, 如果存入时快表满了, 则会淘汰已被认为不在需要的页表项

当然快表也是具有成本问题的, 所以一个快表一般只能存储 16 - 512 个页表项

一个概念: 访问内存的有效时间

就是从进程发出指定逻辑地址的访问请求, 经过地址变换, 到内存中找到对应的实际物理地址单元, 并 取出数据所花费的时间.

二级和多级页表

首先页表是连续的, 按照 32 位系统的逻辑地址是 4GB, 如果每页的单位是 4kb, 那么一个进程就需要 1GB / 1KB = 1M 的页表项, 而一个页表项占一个字节, 则一个进程就需要 1MB 的连续空间来存储页表, 那显然是不可能的, 所以可以采用两种方式进行解决 :

1. 采用离散分配
2. 只将需要使用的部分表项调入内存中

   看解决方法, 与最初解决内存分配问题的一摸一样, 把连续变为离散, 用表存储离散区域, 把暂时不需要的留再磁盘, 而不加载入内存

其实就类似于 hash表 套一个 hash表 一样, 对页表项进行分页, 每次逻辑地址就是 最外层的页表项(第几页) + 页内偏移就找到了对应的页表项, 从而获得对应的物理地址.

多级页表也是类似, 继续进行分页, 好比将书进行分章节, 分栏目, 分小节, 最后才能找到对应的位置一样.

反置页表

由于现代的计算机的逻辑地址可以很大(寻址的位数), 那么每个进程都需要创建页表项, 并且使用连续的内存空间, 就很难进行分配, 如果我们将页表项进行反置 (原来的页表项 key: 页号, value: 物理内存块儿号 转变成 key: 物理内存块儿, value: 标识进程的页), 那么就无需为每个进程都创建页表了, 每个线程在进行地址转换的时候, 都顺序遍历整个反置页表就可以获得在内存中进程页面的物理位置.

该方法虽然避免了为每个进程都建立页表, 但是每次进行地址转换都通过顺序遍历查找, 就会很慢!!

其次, 如果遍历完成之后, 没有发现对应的页, 就需要从磁盘中进行读取, 而磁盘中的数据并没有划分页面, 所以需要额外为程序建立一张页表(表示 页面号 与 磁盘物理位置的映射关系).

这里的顺序遍历我们是否根据之前的改进思路改成通过索引来实现呢? 通过hash实现, 由此就需要考虑 hash表的大小以及hash冲突问题的解决方式了……

到此， 我们先梳理下演变的流程

最初的操作系统属于是单道程序系统，每次只能运行一个程序，内存中也只需要load应用程序进程的数据、代码到内存中即可，所以采用单一连续分配，找到分配起始点，直接load即可

后来演变为多道程序系统，但是此时的硬件能力也不足以支撑太多的应用程序运行，少量几个进程的运行，我们可以直接将内存划分为几个分区，同时只允许分区个数个进程 load 到内存中运行，所以采用固定分区分配

固定分区又会导致系统缺失灵活性，不能满足多样性的用户程序要求，此时发展为动态分区分配的方式，根据不同的算法，对内存进行划分

但是划分过程中会导致内存碎片的产生，浪费存储空间（内存本身就并非是廉价的），所以为了提高内存的利用率，我们又从原来的顺序分配改变为离散的分配 ——- 分页存储管理方式

上述的一个演变流程，都是为了提升内存的利用率，而下面的分段存储方式则是为了满足程序员们在编程和使用上提供比便利

分段存储管理方式

真正运行在计算机中的其实是机器代码 —- 二进制代码，人们提供了助记符（比如：ADD = 001010101 （随便写的，只是个例子）），由此形成了汇编，所以汇编可以说是接近于机器码了，而对于一个汇编程序，整个程序可以分为：分段

为什么要使用分段存储管理方式呢？

有了分段机制，会对不同段间实现隔离！跨越段间的访问将会进行权限检查，这实现了隔离保护。并且分段后的地址是虚拟地址，到物理地址的转换是：段基地址+段内偏移地址（未开启分页情况），那么程序员可以不用再费劲的考虑使用那些物理地址，地址都可以从头开始

想一下，如果采用分段机制，那么我们在访问不同段的数据时，只需要使用段内偏移地址即可，会自动定位到每个段的基址+偏移地址 的位置，而且每个段中的数据都从 0 开始编址，这样写代码时，程序能十分的直观，更具有可读性

具体的实现，通过给每个段标号，通过一张表记录每个段对应到内存中的初始位置以及段长

通过图可见，每个段其实都是可以离散的分布到内存中的不同分区中的。

与分页相似，段信息也可以通过寄存器存储相关信息来实现快速查找，同样的，段寄存器中只存放 段表始址 和 段表长度，如同分页一般，每次需要访问一个数据（段号 + 段内偏移），步骤：

1. 都需要通过段表寄存器获取到段表始址以及长度，判断段号是否合法，
2. 然后找到对应的段始址，再通过段始址 + 基址去访问对应的物理内存

同样的，需要经历两次内存访问，这显然是降低了计算即的速度，所以类似于解决基于页表的2次读取内存的方法，即添加一个寄存器（联想存储器，也称为快表），用于存表中的部分最近访问的段信息

分页和分段的区别

从分段和分页的方式来看，俩者的差别其实不大，形式上很相似，但是他们在概念上完全是不同的

1. 页是信息的物理单位，采用分页存储管理方式是为了实现离散分配方式，以消减内存的外零头（也叫内存碎片），是为了提高内存的利用率，这仅仅只是系统管理上的需要，可以说是系统的行为，对用户不可见。而分段式存储中，段是信息的逻辑单位，通常包含一组意义相对完整的信息，其目的是更好的满足用户的需求
2. 页的大小固定且由系统决定，在采用分页存储管理方式的系统中，在硬件结构上，就把用户程序的逻辑地址划分为页号和页内地址两部分，也就是说是直接由硬件实现的。而段的长度是不固定的，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分
3. 分页的用户程序地址空间是一维的，分页完全是系统行为，即在分页系统中，应用程序的地址是属于单一的线性地址空间，程序员只同需要利用一个记忆符即可表示一个地址，而分段式用户的行为，用户程序的地址空间是二维的，程序员需要一个地址时，需要给出段名 + 段内地址

分段式 的 相对于分页式的有一个更加方便的地方，就是程序信息的共享

当然，段式存储管理方式还有其余的优势，例如：便于实现，分段可共享，易于保护，可动态链接等一系列优点

段页式存储管理方式

到此，我们知道 页存储管理方式能够帮助系统更好的分配内存，减少内存碎片，提高内存利用率。段式存储管理方式呢，更有利于用户使用（程序员）。各有各的优势，我们能不能将两者进行各取所长，然后形成一种组合方案呢？ 那就到了重点：段页式存储管理方式

实现原理也是比较简单的，首先将用户程序分为若干个段，然后段内通过若干个页来进行分配信息

每次获取指令或数据需要信息： 段号 - 段内页号 - 页内地址
现在假设我们需要获取一条指令或者数据，整个流程应该是这样的：

1. 通过段号，在内存中找到段表中对应的条目，获取到页表始址
2. 通过页号获取到页表中对应的条目，并获取到对应的物理地址
3. 通过获得的地址从内存中获取

由此可见，每次都需要经过三次内存的读取，降低了两倍的内存访问速度，为了进行优化，我们采用之前处理段式 or 页式 时都是增加一个快表 来进行优化

这样每次查找前，先去快表中查找，如果查找到直接访问内存对应位置即可，否则仍然是走三次内存访问！