操作系统内存分配
本文主要参考《计算机操作系统（第四版）》（西安电子科技大学出版社）以及清华大学操作系统公开课（向勇、陈渝），整理操作系统的基本概念，供自己复习查阅。
内存分配
为了能将用户的程序装入内存，必须给其分配一定的内存空间。连续分配就是最直观的一种分配方式。但目前的操作系统普遍采用基于离散分配的分页和分段机制的虚拟内存机制，该方式更为合理高效。
连续分配存储管理
连续分配可以分为四类：单一连续分配、固定分区分配、动态分区分配、动态可重定位分区分配。
单一连续分配
在单道程序环境下，内存分为系统区和用户区。用户区仅装有一个用户程序，即整个内存都被该程序独占。
固定分区分配
即在单一连续分配的基础上，把用户空间划分为若干个固定大小的区域，每个分区可以装入一道作业。这是最早出现的可用于多道程序系统的存储管理方式，这种方式显然会造成较大的内存空间浪费，故现在很少用于通用的OS中。
动态分区分配
动态分区分配又称可变分区分配，即根据进程的需要动态分配内存空间，会涉及到分区分配所用的数据结构、分区分配算法以及分区的分配和回收三个问题。
动态分区分配所用的数据结构
为了实现动态分区分配，通常会使用空闲分区表或空闲分区链记录分区的情况。
动态分区分配算法
分区分配操作的性能直接影响系统的性能，故出现了许多分区分配算法。大体上，分区分配算法可分为两类：顺序式搜索算法和索引式搜索算法。细致划分即：
顺序式搜索算法：
- 首次适应算法
- 循环首次适应算法
- 最佳适应算法
- 最坏适应算法
索引式搜索算法：
- 快速适应算法
- 伙伴系统
- 哈希算法
首次适应算法
以使用空闲分区链为数据结构的分配为例，首次适应（First Fit，FF）算法要求空闲分区链的地址为增序，在分配地址时从链首开始查找，找到第一个大小可满足的空闲分区为止，再按作业大小从该分区分出一块内存，其余部分仍作为空闲区留在空闲链中；整条链内都无法找到满足的分区即分配失败。显然该算法倾向于优先利用低位地址的空闲分区，保留了高位地址的大空闲区，为大作业预留了空间，但同时也会造成低址部分留下大量内存碎片。
循环首次适应算法
为了避免低址存在大量的内存碎片，改进FF得到循环首次适应（Next Fit，NF）算法。使用额外的指针保留上一次找到的空闲分区的下一分区的地址，下次查找时从此地址开始查找，并且采用循环查找方式。
最佳适应算法
所谓最佳适应（Best Fit，BF）算法即总是把能满足要求的、最小的空闲分区分配给作业。看似是每次分配均为最佳，但实际上这样做的后果是：每次分配后剩余的部分也是最小的，即产生许多难以利用的内存碎片。
最坏适应算法
最坏适应（Worst Fit，WF）算法与最佳适应相反，即每次都选取最大的空闲分区，它的优点是使每次产生的碎片不至于过小，对中、小作业比较有利；同时，由于该算法要求空闲分区按从大到小的顺序排序，故其查找效率也比较高（只需查看第一个分区即可）。
快速适应算法
快速适应（Quick Fit，QF）算法又称为分类搜索法，即把具有相同容量的所有空闲分区单独设置一个空闲分区链表，再设立一张管理索引表管理所有分区表。在进行分配时，先根据进程长度从索引表找到能容纳它的最小空闲区大小对应的链表，然后直接取出其中的第一块即可，注意此做法并不分割分区。优点即不产生碎片，查找效率高；但为了有效合并分区，分区归还的算法很复杂，系统开销大。
伙伴系统
伙伴系统（Buddy System）基于QF算法，并规定分区大小必须为2的幂。当需要为进程分配内存时，也是先找到能容纳该进程的、最小的空闲分区。若此时该分区能容纳至少两个该进程，则将该分区分割成两个等大分区，并把其中一个归到上一级空闲分区链，另一个用于分配；若分割后仍能容纳至少两个该进程，则重复此法直到分区大小为能容纳该进程的最小的2的幂。与分配时类似，在回收内存时，若存在与待回收分区相同大小的分区则合并这两个分区，并把合并分区归入下一级分区链，若下一级分区同样存在该情况，则依次合并。由于在回收时需要进行合并操作，其时间性能会比QF稍差；但由于采用索引搜索，它的性能又会优于顺序搜索。在空间性能上，合并操作减少了小空闲分区，提高了空闲分区的使用率，优于QF算法，但比顺序搜索算法差。
哈希算法
当空闲分区分类较细时，索引表项较多，搜索时间开销也会显著增大。哈希算法则利用哈希快速查找的优点，以空闲分区大小为关键字构建哈希表，从而在分区分配时快速得出分区链表表头指针。
可重定位分区分配
可重定位分区分配法与动态分区分配法基本一致，差别仅在于：该方法加入了紧凑（Compact）功能。紧凑即当当前的空闲分区无法满足用户需求时，让当前所有作业都进行移动，使它们相邻接，最后形成一个大空闲分区。紧凑使进程的物理地址发生了改变，也就迫使我们修改程序和数据的地址。而运行时动态链接则可以解决这一性能问题，重定位寄存器的存在使得紧凑操作仅需修改寄存器保存的程序起始地址即可，这就是动态重定位。
离散分配存储管理
连续分配方式都无法避免内存碎片的产生，紧凑可以解决这一问题但开销很大。如果允许一个进程分散装入不同的分区，便能充分利用空间，由此即产生了离散分配方式。根据分配地址空间的基本单位的不同，基本的离散分配方式有分页式和分段式。同时还可以结合两者优点形成段页式，这也是目前应用较广泛的形式。
分页存储管理
该方式把用户程序的地址空间分为若干固定大小的称为“页”的区域，同时把内存空间分为若干物理块，页块大小相同。
页和块
逻辑地址分为若干页并编号，内存的物理地址空间分为若干块并编号。在为进程分配内存时以块为单位，可以把进程的若干页装入不相邻的物理块中，无法装满的块即页内碎片。
在选择页面大小时也要注意。页面过小可以减少内存碎片，但也会使进程占用的页数变多，导致进程页表过长，使页表占用内存变大，降低换入换出效率。而页面过大虽然可以减小页表长度，但又会使页内碎片增大。
地址结构
以32位地址为例，假设地址前20位为页号，剩余部分为页内地址（位移量）。12位的页内地址即每页的大小为\(2^{12}B=4KB\)；20位页号即地址空间最多有\(2^{20}=1M\)页。
对于给定的逻辑空间地址A以及其页面的大小L，均可以计算出对应的页号P以及页内地址d：
\]
页表
为保证离散分配后的进程仍能正常运行，系统还应为每个进程建立一张页面映像表，即页表。页表的作用是实现从页号到物理块号的映射，同时还可以在页表设置一个存取控制字段，对块中内容加以保护。
地址变换机构
地址变换机构的任务即把逻辑地址转换为内存中的物理块号，是借助页表完成的。由于页表可能很大，即页表项数很多，故页表大多驻留在内存中，在系统中设置一页表寄存器（Page Table Register，PTR）存放页表的起始地址和页表长度。进程未执行时，起始地址和页表长度一般位于本进程的PCB中。
快表
由于页表存放在内存中，CPU每次访问数据都要访问两次内存，即-先访问页表获取物理块号，再把其与页内地址拼接成物理地址，再访问物理地址中的数据。显然这会使计算机处理速度下降近一半。为了提高地址变换速度，可以在地址变换机构中增设一个具有并行查询能力的特殊高速缓冲寄存器，即快表（Associative Memory）。快表用于存放那些当前正在访问的页表项。配备快表后，每当需要访问数据时，首先在快表中寻找是否存在相匹配的页号，有则直接读取；否则继续在内存中寻找页号，并将此页表项存入快表。若快表已满，则选取一个被认为是不再需要的快表项并替换。
内存的有效访问时间
从进程发出访问逻辑地址的请求开始，经过地址变换，到在内存中找到对应的实际物理地址单元并取出数据所花费的总时间即内存的有效访问时间（Effective Access Time，EAT）。设访问一次内存的时间为\(t\)，则在引入快表前：\(EAT=2t\)；引入快表后：\(EAT=a\times \lambda+(t+\lambda)(1-a)+t=2t+\lambda-t\times a\)，其中\(\lambda\)为查询快表所需的时间，\(a\)为快表命中率。采用合适的算法保证命中率可使引入快表的CPU访问速度大幅提高。如当\(\lambda={t\over 5}\)时，若命中率能达到90%，则整体访问时间可缩短至\(1.3t\)。
多级页表
现代操作系统大多支持非常大的逻辑地址空间。对于页面大小为4KB的32位逻辑地址，页表项数最高可达1M，这就意味着对应进程的页表就会占用1MB的连续内存。为了解决这一问题，我们可以沿用离散分配的思路，把页表也进行离散分配，并且只把当前需要的页表项调入内存，其余驻留磁盘，这就是多级页表。
以二级页表为例，同样是32为逻辑地址，可以作如下划分：
为了实现，同时在地址变换机构增设一个外层页表寄存器，用于存放外层页表的起始地址。只是多级划分并没有解决页表的内存占用问题，真正解决问题的是配合多级页表实现当前不用的页表驻留磁盘。为此，还应在外层页表中为每一个内层页表增设状态位S，以说明此页表是否在内存上。
分段存储管理
一方面，通常的程序都可以划分为若干段，如主程序段、子程序段、数据段、栈段等，每个段都是一个相对独立的逻辑单位；另一方面，这些段也是实现信息共享、信息保护、动态链接以及信息动态增长的基本单位。显然，分段更符合实际需求，由此也就引入了分段存储管理方式。
分段
在这种管理方式中，作业的地址空间被划分为若干段每个段都具有实际意义，方便起见为段编号，各段从0开始编址且地址空间连续，段长度由相应的逻辑信息组决定，因此各段的长度很可能各不相同。
段表
与分页管理类似，分段管理系统也会为每个分段分配一个连续分区，并为每个进程建立一张段映射表，即段表。段表的作用即建立逻辑段到物理内存区的映射，每个段在表中都有一个表项，用于记录段的起始地址以及段的长度。
地址变换机构
为了实现地址变换，同样也要在系统中设置段表寄存器，用于存放段表起始地址以及段长度。在访问时需要检测是否发生段表越界或段内越界。同样，增设联想存储器保存最近使用的段表项。由于段一般比页大，段表项数目较少，其联想存储器规模也相对较小，存取速度较快。
分段与分页的区别
- 页是信息的物理单位，其对用户是不可见的；段是信息的逻辑单位，为了用户的需要而划分。
- 页的大小固定且由系统决定；段的长度不固定且由用户决定。
- 由于分页是系统行为，页地址空间是线性的，即通过一个逻辑地址就可以计算出对应的物理地址；而分段是用户行为，其地址空间是二维的，即需要提供段号以及段内地址才可以得到实际地址。
段页式存储管理
对两种分配方式各取所长即得到段页式存储管理方式，它既具有分段系统便于实现、分段可共享、易于保护、可动态链接的优点，又能像分页系统一样解决内存外部碎片的问题。
基本原理
段页式存储管理即先把用户程序分为若干段，并为每个段赋予一个段名，再把每个段分为若干页。其地址结构由三部分组成：段号、段内页号、页内地址。为了实现从逻辑地址到物理地址的转换，系统中需同时配置段表和页表。段的内容不再是内存起始地址以及段长，而是页表的起始地址以及页表长度。
地址变换
在段页式系统中，获取系统中配有一段表寄存器，在进行地址变换时，首先判断段号是否越界，未越界则利用段表起始地址以及段号求出该段对应项在段表中的位置，从中得出该段的页表起始地址，再利用逻辑地址中的段内页号获取对应页的页表项所在位置并从中读取物理块号，再利用块号和页内地址计算物理地址。显然，在一次数据或指令访问中，需要访问三次内存。为了提高执行速度，同样可以设置高速缓冲寄存器。