内存管理
3周完成5个大作业，我笑死了，哈哈哈哈哈。
内存基础知识
内存可以存放数据。程序执行前需要先放到内存中才能被CPU处理——缓和CPU与硬盘之间的速度矛盾。
内存中有一个一个的小房间，每个小房间就是一个存储单元。
编址方式：
- 按字节编址：每个存储单元大小为1字节，即8个比特位。
- 按字编址：如果机器字长为16位，则每个存储单元大小为1字，即16个比特位。
内存地址从零开始，每个地址对应一个存储单元。
数量单位
- 1K = $2^{10}$Byte
- 1M = $2^{20}$Byte
- 1G = $2^{30}$Byte
内存管理
管些什么：
- 如何记录哪些区域已经被分配了，哪些还空闲？
- 新开启一个进程，应该放在哪里？
- 运行结束后，如何将进程占用的内存空间回收？
- 操作系统负责内存空间的分配与回收。
- 操作系统需要提供某种技术从逻辑上对内存空间进行扩充。
- 操作系统需要提供地址转换功能，负责程序的逻辑地址与物理地址的转换。
- 内存保护
三种地址转换方式：
- 绝对装入：编译时产生绝对地址。
- 可重定位装入：装入时将逻辑地址转化为物理地址。
- 动态运行时装入：运行时将逻辑地址转化为物理地址，需设置重定位寄存器。
内存保护：
- 方法一：在CPU中设置一对上、下限寄存器，存放进程的上、下限地址。进程调度指令要访问某个地址时，CPU检查是否越界。
- 方法二：采用重地址寄存器(基址寄存器)和界地址寄存器(限长寄存器)进行越界检查。
进程的内存映像
宏定义：在编译时被编译器替换，实际并不会在内存中被实际分配空间。
内存连续分配管理方式
连续分配：指为用户进程分配的必须是一个连续的内存空间。
单一连续分配
在单一连续分配方式中，内存被分为系统区和用户区。
- 系统区：通常位于内存低地址部分，用于存放操作系统相关数据。
- 用户区：用于存放用户进程相关数据。内存中只能有一道用户程序，用户程序独占整个用户空间。
优点：
- 实现简单，无外部碎片。
缺点：
- 只能用于单用户，单任务的操作系统。
- 有内部碎片，存储器利用率很低。
固定分区分配
为了能在内存中装入多道程序，且这些程序之间又互不打扰。将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业。
分区方式：
- 分区大小相等：缺乏灵活性，但是适合用于用一台计算机控制多个相同程序的场合。
- 分区大小不等：增加了灵活性，满足不同大小的进程需求。
分区说明表
用于实现各个分区的分配与回收。每个表项对应一个分区，通常按分区大小排列。每个表象包括：大小、起始地址、状态
用户程序装入内存时，由操作系统根据用户程序大小检索该表，从中找到合适的分区，并分配给程序。
优点：实现简单，无外部碎片
缺点：
- 用户程序很大时，所有分区都无法满足
- 会产生内部碎片
动态分区分配
动态分区分配又称可变分区分配。这种分配方式不会预先划分内存分区，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区大小正好适合进程的需要。因此系统分区的大小和目的是可变的。
数据结构
空闲分区表：每个空闲分区对应一个表项。表项中包含分区号、分区大小、分区起始地址等信息。
空闲分区链：每个分区的起始部分和末尾部分分别设置前向指针和后向指针，起始部分处还可以记录分区大小等信息。
分配算法
动态分区分配算法
首次适应算法
算法思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区
如何实现：空闲分区以地址递增的次序排序。每次分配内存时顺序查找空闲分区链，找到大小能满足的要求的第一个空闲分区。
最佳适应算法
算法思想：优先使用更小的空闲区。
如何实现：空闲分区按照容量递增次序链接。每次分配内存时顺序查找空闲分区链，找到大小能满足要求的第一个空闲分区。
缺点：每次都用最小的分区进行分配，会留下越来越多、很小的内存块。因此这种方法会产生很多外部碎片。
最坏适应算法
算法思想：优先使用大的空闲区。
如何实现：空闲分区按照容量递减次序排列，每次分配内存时顺序查找空闲分区链，找到大小能满足的第一个空闲分区。
缺点：较大的连续空闲区被迅速用完，如果之后有大进程到达，就没有内存分区可用了。
邻近适应算法
算法思想：首次适应算法每次从链头开始查找。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置来检索，就能解决上述问题。
如何实现：空闲分区以地址递增的顺序排列(可以排成循环链表)。每次分配内存时从上次查找结束的位置来时查找空闲分区链。找到大小能满足要求的第一个空闲分区。
优点：算法开销小
缺点：高地址的大分区也会被用完。
分区回收
如果回收后空闲分区相邻，必须进行合并。
动态分区分配没有内部碎片，但是有外部碎片。
内部碎片：分配给某进程的内存区域中，如果有些部分没有用上。
外部碎片：内存中某些空闲分区由于太小而难以利用。
如果内存中空闲空间的总和本来可以满足某些进程的要求，但由于进程需要的是一整块连续的内存空间，因此这些碎片不能满足进程的需求。
可以通过紧凑(拼凑)技术来解决外部碎片。
分页存储
连续分配：为用户进程分配的必须是一个连续的内存空间。
非连续分配：为用户进程分配的可以是一些分散的内存空间。
基本分页存储管理
将内存空间分为一个个大小相等的分区(比如：每个分区4KB)，每个分区就是一个”页框”(页框 /页帧/内存块/物理块/物理页面)。每个页框有一个编号，即页框号，页框号从0开始。
将进程的逻辑地址空间也分为与页框大小相等的一个个部分，每个部分称为一个页或页面。每个页面也有一个编号，即”页号”，页号也是从0开始。
操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系。
每个页面不需要连续存放，可以放到不相邻的各个页框中。
页表
为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表。
假设某系统物理内存大小为4GB，页面大小为4KB，则每个页表项至少应该为多少字节。
内存块大小 = 页面大小 = 4KB = $2^{12}$B
- 4GB的内存总共会被划分为$2^{32}/ 2^{12} = 2^{20}$ 个内存块。
- 内存块号的范围应该是0 ~ $2^{20}$ - 1
- 内存块号至少要用20bit来表示
- 至少要3B来表示块号(3 * 8 = 24 bit)
由于页表项在内存中连续存放，因此页号可以是隐含的，不占存储空间。
因此存储整个页表需要3*(n+1)B
逻辑地址与物理地址的转换
要访问逻辑地址A，则：
- 确定逻辑地址A 对应的页号P
- 找到P页号在内存中的起始地址，需要查询页表
- 确定逻辑地址A的页内偏移量W
逻辑地址A对应的物理地址= P号页面在内存中的起始地址+页内偏移量W。
逻辑地址结构(页框大小为2的幂)
分页存储管理的逻辑地址结构如下所示：
如果有K位标识页内偏移量，说明该系统中一个页面的大小为$2^k$个内存单元。
如果有M位表示页号，说明系统中一个进程最多允许$2^M$个页面。
基本地址变换机构
- 计算页号P和页内偏移量W
- P = A/L
- W = A%L
- 比较页号P和页表长度M，P>=M时，会产生越界中断。
- 页表中页号P对应的页表地址 = 页表起始地址F + 页号P * 页表项长度。取出页表项内容b，即为页框号。
- 计算E = b*L + W, 访问得到的物理地址E
具有块表的地址变换机构
快表
快表，又称联想寄存器(TLB, translation lookaside buffer)，是一种访问速度比内存块很多的高速缓存(TLB不是内存！)，用来存放最近访问的页表项的副本，可以加速地址变换的速度。于此对应，内存中的页表常称为慢表。
过程：
- CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。
- 如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存单元。因此若快表命中，则访问某个逻辑地址仅需一次访存即可。
- 如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接成物理地址。最后，访问该物理地址对应的内存单元。因此，若快表未命中，则访问某个逻辑地址需要两次访存。
原理：
- 时间局部性
- 空间局部性
两级页表
单级页表存在的问题：
- 当某程序所占内存非常大时，其页表项也就非常多，可能需要占据很多页框。但是由于页表项必须要连续存储，就丧失了分页存储的优势。
- 很多时候，进程在一段事件内只需要访问几个页面就可以正常运行了。因此没有必要让整个页表都常驻内存。
解决方法：
将长长的页表进行分组，使每个页框刚好可以放入一个分组。再为离散分配的页表再建立一张页表，称为页目录表、外层页表、顶层页表。
再给页表项中增加一个标志位，用于表示该页面是否已经调入内存，用于解决问题2：
若想访问的内面不在内存中，则产生缺页中断(内中断)，然后将目标页面从外存调入内存。
注意：
若采用多级页表机制，则各级页表的大小不能超过一个页面。
两级页表的访存次数分析。
- 第一次访存：访问页目录表
- 第二次访存：访问二级页表
- 第三次访存：访问目标内存单元。
n级页表访问n+1次，无快表。
分段存储
进程的地址空间，按照程序自身的逻辑关系划分为若干个段， 每个段都有一个段名，每段从0开始编址。
分段系统的逻辑地址结构由段号和段内地址所组成：
段号的位数决定了每个进程最多可以分几个段
段内地址位数决定了每个段的最大长度是多少
段表
为每个进程建立一张段映射表，简称段表。用于从物理内存中找到各个逻辑段的存放位置。
- 每个段对应一个段表项，其中记录了该段在内存中的起始位置(基址)和段的长度。
- 各个段表项的长度是相同的。
分页分段对比
页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。
段是信息的逻辑单位。分段主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式的给出段名。
分页的用户进程地址空间是一维的，程序员只需要给出一个记忆符即可表示一个地址。
分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。
分段比分页更容易实现信息的共享和保护。
不能修改的代码称为纯代码或可重入代码，这样的代码是可以共享的。可修改的代码是不能共享的。(比如，有一个代码段中有很多变量，各进程并发地同时访问可能造成数据不一致)。
段页式管理方式
分页存储 vs 分段存储
段页管理方式
段页式管理的逻辑地址结构
- 段号的位数决定了每个进程最多可以分几个段
- 页号的位数决定了每个段最大有多少页
- 页内偏移量决定了页面大小、内存块大小是多少
段表、页表
每个段对应一个段表项，每个段表项由段号、页表长度、页表存放块号(页表起始地址)组成。每个段表项长度相等，段号是隐含的。
查找过程
段页存储需要访存三次：
- 访问段表
- 访问页表
- 访问目标内存单元
虚拟内存
传统存储管理方式：很多暂时用不到的数据也会长期占用内存，导致内存利用率不高
传统存储管理缺点：
- 一次性：作业必须一次性全部装入内存后才能开始运行。
- 驻留性：一旦作业被装入内存，就会一直驻留在内存中，直至作业运行结束。事实上，在一个时间段内，只需要访问作业的一小部分数据即可正常运行，这就导致了内存中会驻留大量的、暂时用不到的数据。
局部性原理
时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行；如果某个数据被访问过，不久之后该数据很有可能被再次访问。
空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。
虚拟内存的定义和特征
基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。
在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。
在操作系统的管理下，在用户看来似乎有一个比实际内存大的多的内存，这就是虚拟内存。
特征：
- 多次性：无需在作业运行时一次性 全部装入内存，而是允许被分成多次调入内存。
- 对换性：在作业运行时无需一直常驻内存，而是允许在作业运行过程中，将作业换入、换出。
- 虚拟性：从逻辑上扩充了内存的容量，使用户看到的内存容量，远大于实际的容量。
如何实现虚拟内存技术
虚拟内存的实现需要建立在离散分配的内存管理方式基础上。
- 基本分页存储管理->请求分页存储管理
- 基本分段存储管理->请求分段存储管理
- 基本段页式存储管理->请求段页式存储管理
新增功能：
- 请求调页功能：访问信息不存在时，由操作系统负责将所需信息从外存调入内存。
- 页面置换功能：内存空间不足时，由操作系统负责将内存中暂时用不到的信息换出到外存。
页表机制
基本分页存储管理页表：
请求分页存储管理方式的页表：
状态位：
- 表示是否已经调入内存
访问字段：
- 记录该页最近被访问过几次，或记录上次被访问的时间，供置换算法选择换出页面时参考。
修改位：
- 页面调入内存后是否被修改过。
外存地址：
- 页面在外存中的存放位置。
缺页中断机构
在请求分页系统中，每当要访问的页面不存在时，便产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断。
- 内存中有空闲块：则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项。
- 内存中没有空闲块：则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存。未修改过的页面不用写回外存。
缺页中断是因为当前执行的指令想要访问的目标地址未调入内存而产生的，因此属于内中断。
一条指令在执行期间，可能产生多次缺页中断。(如copy A to B， 即将逻辑地址A中的数据复制到逻辑地址B，而A、B属于不同的页面，则有可能产生两次中断。)
- 找到对应页表项之后，若对应页面未调入内存，则产生缺页中断，之后由操作系统的缺页中断处理程序进行处理。
- 只有执行写指令，才需要修改修改位。并且一般只需修改快表中的修改位，只有要将快表项删除时才需要写回内存中的慢表。这样可以减少访存次数。
- 和普通的中断处理一样，缺页中断处理依旧需要保留CPU现场。
- 页面调入内存后，需要修改慢表，同时也需要将表项复制到快表。
页面置换算法
页面的换入、换出需要磁盘IO，会有较大的开销、因此好的页面置换算法应该追求更少的缺页率。
最佳置换算法(OPT)
每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。
从当前访问的页面向后寻找，最后一个出现的页号就是要淘汰的页面。
整个过程中，缺页中断发生9次，页面置换发生了6次。
缺页率 = 9 / 20 = 45%。
最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面的访问序列。因此，最佳置换算法是无法实现的。
先进先出置换算法(FIFO)
每次选择淘汰的页面是最早进入内存的页面。
实现方法：把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头的页面即可。队列的最大长度取决于系统为进程分配了多少个内存块。
例1：系统为进程分配了3个进程块。
3号页面进入队列最早的，所以淘汰3号页面。
例2：系统为进程分配了4个内存块。
Belady异常——当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。
只有FIFO算法会产生Belady异常。另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因此先进入的页面也有可能最经常访问。因此算法性能差。
最近最久未使用置换算法(LRU)
每次淘汰的页面是最近最久未使用的页面。
实现方法：赋予每个页面对应的页表项中，用访问字段记录该页面上次被访问以来所经历的时间t。当需要淘汰一个页面时，选择现有页面中t值最大的，即最久未访问的页面。
从当前页号开始向前检查，最后一个出现的页号就是要淘汰的页面。
该算法的实现需要专门的硬件支持，虽然算法性能好，但是实现困难，开销大。
时钟置换算法(CLOCK)
又称CLOCK算法、或最近未用算法(NRU)。
简单的Clock算法
为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页面被访问时，其访问位设置为1。当需要淘汰一个页面时，只需要检查页的访问位。
- 如果是0，就选择该页换出；
- 如果是1，则将他置为0，暂不换出，继续检查下一个页面。
若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进程第二轮扫描。
改进型的时钟置换算法
简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。
因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/O操作。这就是改进型的时钟置换算法的思想。修改为=0，表示页面没有被修改过；修改位为1，表示页面被修改过。
算法规则：
- 第一轮：从当前位置开始扫描到第一个(0, 0)的帧用于替换。本轮扫描不修改任何标志位。
- 第一优先级：最近没访问，且没修改的页面。
- 第二轮：若第一轮扫描失败，则重新扫描，查找第一个(0, 1)的帧用于替换。本轮将所有扫描过的帧访问位设为0。
- 第二优先级：最近没访问，但修改过的页面。
- 第三轮：若第二轮扫描失败，则重新扫描，查找第一个(0, 0)的帧用于替换。本轮扫描不修改任何标志位。
- 第三优先级：最近访问过，但没修改过。
- 第四轮：若第三轮扫描失败，则重新扫描，查找第一个(0, 1)的帧用于替换。
- 第四优先级：最近访问过，也修改过。
改进型CLOCK置换算法选择一个淘汰页面最多会进行四轮扫描。
