OS Summary 5 - 物理内存管理:连续内存分配
内容概述
计算机体系结构由 CPU、内存、I/O 设备、总线组成。
CPU 中包括：
- ALU、控制逻辑
- 寄存器
- 高速缓存：加快读写速度
- 存储管理单元 (MMU)
内存的特点：
- 最小访问单位是字节 (8 bit )
- 一次可以读 / 写 4 字节 (32 位)，有地址对其问题
内存可以分为如下层次：
- CPU 中：
- L1 缓存
- L2 缓存
- 这些缓存都是由硬件 (MMU) 来控制的，软件看不到
- 高速缓存未命中：( 这之下由操作系统软件来控制)
- 内存
- 缺页
- 外存 ( 虚拟内存 )
操作系统的内存管理
OS 内存管理的特点：
- 每个字节有自己的物理地址
- 分为内存和外存
- 每个进程有自己用的内存片，它们自己的地址之间是可以重叠的
- MMU：将逻辑 ( 虚拟 ) 地址空间转换为物理地址空间
OS 内存管理的目标：
- 抽象：逻辑地址空间
- 保护：独立地址空间
- 共享：访问相同内存
- 虚拟化：更大的地址空间
操作系统采用的内存管理方式：
- 重定位 (relocation)：段地址 + 偏移
- 分段 (segmentation)：程序的逻辑结构不需要连成一片，而是分成代码、数据、堆栈 3 块，每一块的空间就减少了；但每段的内容是连续的
- 分页 (paging)：把内存分成最基本的单位
- 虚拟存储 (virtual memory)：目前多数系统 ( 如 Linux ) 采用的是按需页式虚拟存储
内存管理方式的实现是高度依赖硬件的：
- 与计算机存储架构紧密耦合
- MMU (内存管理单元)：处理 CPU 存储访问请求的硬件
静态地址重定位：即在程序装入内存的过程中完成，是指在程序开始运行前，程序中的各个地址有关的项均已完成重定位，地址变换通常是在装入时一次完成的，以后不再改变，故成为静态重定位。
优点：无需硬件支持
缺点：1）程序重定位之后就不能在内存中搬动了；2）要求程序的存储空间是连续的，不能把程序放在若干个不连续的区域中。
动态地址重定位：不是在程序执行之前而是在程序执行过程中进行地址重定位。更确切的说，是在每次访问内存单元前才进行地址变换。动态重定位可使装配模块不加任何修改而装入内存，但是它需要硬件一定位寄存器的支持。
优点：1）目标模块装入内存时无需任何修改，因而装入之后再搬迁也不会影响其正确执行，这对于存储器紧缩、解决碎片问题是极其有利的；2）一个程序由若干个相对独立的目标模块组成时，每个目标模块各装入一个存储区域，这些存储区域可以不是顺序相邻的，只要各个模块有自己对应的定位寄存器就行。
缺点：需要硬件支持。
地址空间和地址生成
一般来说，地址空间至少有 3 种：
- 物理地址空间：硬件支持的地址空间
- 起始地址 0
- 到 MAXsys
- 线性地址空间：CPU 看到的地址
- 起始地址 0
- 大小取决于地址线的宽度
- 逻辑地址空间：在 CPU 中运行的进程看到的地址
- 起始地址 0
- 到 MAXprog
- 也就是用户程序可见的地址
逻辑地址的生成需要经过如下几个过程：
- 高级语言程序：写出函数
- 编译：对源代码进行编译，称为汇编源代码，此时仍然用符号来指代函数
- 汇编：汇编成二进制代码，用具体地址来替代符号了，但是有一些函数还没有找到
- 链接：加入函数库，找到库函数的地址
- 重定位：程序加载时进行，视程序实际位置改变符号地址
一般来说，生成地址有几个时机：
- 编译时（优点：简单）
- 假设起始地址已知
- 但如果起始地址改变，就必须重新编译
- 功能手机一般会有这种情况
- 加载时
- 如果加载时起始位置未知，编译器需生成可重定位的代码 ( relocation code )
- 加载时，生成绝对地址
- 执行时（优点：灵活）
- 执行时代码可移动
- 需地址转换（映射）硬件支持（一般是虚拟存储）
连续内存分配
一般分配给一个进程的地址空间是连续的，因此需要进行有效的内存分配。需求是，给进程分配一块不小于制定大小的连续的物理内存区域。定义碎片是过小的不能被利用的空闲内存，分为 2 类：
- 外部碎片：分配单元之间的未被使用内存
- 内部碎片：分配单元内部的未被使用内存（一般是否有内碎片取决于分配单元大小是否要取整）
我们在 uCore 中进行的是动态内存分配，需要满足如下要求：
- 当程序被加载执行时，分配一个进程指定大小可变的分区（块）
- 分区的地址是连续的
一般来说，操作系统需要维护至少 2 个数据结构，里面存储的内容是：
- 所有进程的已分配分区
- 空闲分区 ( Empty-blocks )
常见的几种连续内存分配策略包括：
- 最先匹配 (First-fit)
- 最佳匹配 (Best-fit)
- 最差匹配 (worst-fit)
总的来说，这些匹配方式各有优劣，至于到底是什么优劣，与使用场景关系很大。
三种不同的分类策略
最先匹配 (First Fit Allocation) 策略
思路：需要分配 n 个字节时，使用第一个可用的空间比 n 打的空闲块
原理和实现：
- 空闲分区列表按地址顺序排序
- 分配时搜索第一个合适的分区
- 释放分区时，检查是否可与邻近的空闲分区合并
优点：
- 简单
- 在搞地质空间有大块的空闲分区
缺点
- 容易产生外部碎片
- 分配大块时较慢
最佳匹配 (Best Fit Allocation) 策略
思路：分配 n 字节内存时，查找并使用不小于 n 的最小空闲分区
原理和实现：
- 空闲分区列表按照大小排序
- 分配时，查找一个合适的分区
- 释放时，查找并合并邻近的空闲分区（如果找到）
优点：
- 大部分分配的尺寸较小时，效果很好
- 可避免大的空闲分区被拆分
- 可减少外部碎片的大小
- 相对简单
缺点：
- 外部碎片较多
- 释放分区较慢
- 容易产生很多无用的小碎片
最差匹配 (Worst Fit Allocation) 策略
思路：分配 n 字节时，使用尺寸不小于 n 的最大空闲分区
原理和实现：
- 空闲分区列表由大到小排序
- 分配时，选最大的分区
- 释放时检查是否可与邻近的空闲分区合并，进行可能的合并，并调整空闲分区列表顺序
优点：
- 中等大小的分配较多时，效果最好
- 避免出现太多的小碎片
缺点：
- 释放分区较慢
- 外部碎片较多
- 容易破坏打的空闲分区，因此难以分配大的分区
碎片整理
上述方法都会产生外碎片。（但是不会产生内碎片，因为是按需分配的）如果碎片太多，就有可能出现，即使空余内存总数足够大，也无法分配出一块连续内存的情况。为此就需要进行碎片整理。碎片整理的定义是通过调整进程占用的分区位置来减少或避免分区碎片。一般有两种碎片整理的方法
- 紧凑（compaction）通过移动分配给进程的内存分区，以合并外部碎片
- 进行碎片紧凑的条件：所有的应用程序可动态重定位
- 需要在应用程序等待时进行移动
- 需要考虑开销
- 分区对换（Swapping in/out）：通过抢占并回收处于等待状态进程的分区，以增大可用内存空间
- 这就让更多进程能够在内存里交替运行
- 需要解决的问题：交换哪个（些）进程？
- swap分区在linux中是耳熟能详的，在早期很有用，但代价很大，因为外存的速度远远慢于内存
- 有了虚拟页式存储之后，纯粹的分区对换的意义就不大了
伙伴系统
伙伴系统（Buddy System）是一种连续存储分配的办法，它解决了分配位置和碎片的问题。
假定整个可分配的分区大小为2u，伙伴系统的分配和释放过程如下：
- 分配过程：
- 需要的分区大小为2u−1<s≤2u时，把整个块分配给该进程
- 若s≤2i−1−1，则将大小为2i的当前空闲分区划分成两个大小为2i−1−1的空闲分区
- 重复划分过程，直到2i−1<s≤2i，并把一个空闲分区分配给该进程
- 释放过程：
- 将进程占用的块释放
- 查看它能否与相邻的空闲块合并（注意边界条件）
- 如果能合并，则不断合并到不能再合并为止
由分析可知，内碎片的大小最多是2i−1−1，没有外碎片。
伙伴系统的具体实现
数据结构：
- 空闲块按大小和起始地址组织成二维数组（或者说一维数组+一维链表）
- 第一维：大小；第二维：地址
- 初始状态：只有一个大小为2u的空闲块
分配过程：
- 由小到大 在空闲块数组中找最小的可用空闲块（只要有合适的空闲块，就不切分大块，这是隐含的一个原则吧）
- 如果块太大，则对可用空闲块进行二等分，直到得到合适大小的块
释放过程：
- 把释放的块放入空闲块数组
- 合并满足合并条件的空闲块，合并条件是：
- 大小相同，均为2i
- 地址相邻
- 相邻两块的低地址必须是2^(i+1)的倍数
练习
选择填空题
操作系统中可采用的内存管理方式包括()
- 重定位(relocation)
- 分段(segmentation
- 分页(paging)
- 段页式（segmentation+paging）
都有。虽然我还是很难想象重定位是内存管理方式，这难道不是进程的管理方式么，虽然能够把进程在内存中搬移大概是上述几种分配策略的前提……
在启动页机制的情况下，在CPU运行的用户进程访问的地址空间是()
- 物理地址空间
- 逻辑地址空间
- 外设地址空间
- 都不是
用户进程访问的内存地址是虚拟地址。虚拟地址加上对应的段选择子构成逻辑地址。逻辑地址经过分段翻译成线性地址。线性地址经过分页翻译成物理地址。（但是，即使没有启动页机制，用户进程访问的地址空间也应该是逻辑地址空间吧）
连续内存分配的算法中，会产生外碎片的是()
- 最先匹配算法
- 最差匹配算法
- 最佳匹配算法
- 都不会
三种算法都会有外碎片，而没有内碎片。相比之下，分页不会有外碎片，只会有内碎片。伙伴系统是可能会产生外碎片的，当然也有内碎片。
在使能分页机制的情况下，更合适的外碎片整理方法是()
- 紧凑(compaction)
- 分区对换(Swapping in/out)
- 都不是
分页方式不会有外碎片。虽然很对，但这道题完全毫无意义。
描述伙伴系统(Buddy System)特征正确的是()
- 多个小空闲空间可合并为大的空闲空间
- 会产生外碎片
- 会产生内碎片
- 都不对
小空闲空间在满足一定条件时可以合并。因为是一个不断二分的过程，所以外碎片是可能会产生的。因为是分配2的幂大小的内存，所以内碎片也是有的。
简答题
操作系统中存储管理的目标是什么？
- 抽象
- 保护
- 共享
- 虚拟化
描述编译、汇编、链接和加载的过程是什么？
- 编译：将程序源代码转换为汇编代码
- 汇编：将汇编代码转为二进制的机器码
- 链接：将多个二进制的机器码结合成一个可执行环境
- 加载：将程序从外存中加载到内存中
什么是内碎片、外碎片？
内碎片是指分配给任务的内存大小比任务所要求的大小所多出来的内存。外碎片指分配给任务的内存之间无法利用的内存。当然，一块内存是否为外碎片取决于需要分配的内存的大小。
最先匹配会越用越慢吗？请说明理由（可来源于猜想或具体的实验）？
最先匹配总是先找低地址空间的内存，到后期低地址空间都是大量小的不连续的内存空间，每次都要扫描低地址空间后到达高地质空间才能得到可用的内存。所以大概是会越用越慢的。
最差匹配的外碎片会比最优适配算法少吗？请说明理由（可来源于猜想或具体的实验）
应该会的。因为每次都找到最大的内存块进行分割，因此分割剩下的内存块也很大，往往还可以再装下一个程序。
理解0:最优匹配，1:最差匹配，2:最先匹配，3:buddy systemm算法中分区释放后的合并处理过程？ (optional)
它们的处理方式都是查看边上是否也有空闲块，如果有，则合并空闲块，然后将空闲块管理数据插入链表中。如果能进行合并，都需要连续合并。当然，伙伴系统的合并过程需要判断是否满足条件。
对换和紧凑都是碎片整理技术，它们的主要区别是什么？为什么在早期的操作系统中采用对换技术？
区别是，紧凑是在内存中搬动进程占用的内存位置，以合并出大块的空闲块；对换是把内存中的进程搬到外存中，以空出更多的内存空闲块。采用对换的原因是，处理简单。不过代价也比较高，因为外存比较慢。
伙伴系统的空闲块如何组织？
按照内存的大小由一系列链表组织。类似于哈希表，将相同大小的内存区域首地址连接起来。（因为一般来说，内存要按首地址大小排列，链表的插入删除比较简单啊）
伙伴系统的内存分配流程？
当向内核请求分配(2i−1，2i]数目的页块时，按照2i大小的块来请求处理。如果对应的块链表中没有空闲页块，则在更大的页块链表中找空闲块，并将大块进行切分，直到得到满足要求的块。如果切出了多余的块，伙伴系统会将这些块插入到对应的空闲页块链表中。
伙伴系统的内存回收流程？
当释放多页的块时，内核首先计算出该内存块的伙伴的地址。内核将满足以下条件的三个块称为伙伴：
- 两个块具有相同的大小，记作b。
- 它们的物理地址是连续的。
- 第一块的第一个页的物理地址是2∗(2b)的倍数。
如果找到了该内存块的伙伴，确保该伙伴的所有页都是空闲的，以便进行合并。内存继续检查合并后页块的“伙伴”并检查是否可以合并，依次类推。
（所以才叫伙伴系统，了解了）