本文已收录到：清华大学操作系统课程笔记 专题
计算机体系结构和内存层次
存数据的地方：CPU里的寄存器、内存、外存。
32位机器也就是可以一次性从内存中读写32位（4字节）数据。
详情查询： 
内存层次
通过MMU（Memory Management Unit，内存管理单元）来作为虚拟（逻辑）地址和物理地址之间的枢纽。
- 抽象：逻辑地址空间
- 保护：每个进程只能访问自己的地址空间。
- 共享：访问相同内存
- 虚拟化：每个进程的地址空间编号都是一样的，分配一模一样的地址空间。甚至可以大于物理内存
操作系统内存管理方式
- 重定位：每个地址用一个段地址+偏移得到的。这种对特定机器才有用，不灵活。
- 分段：我们希望一个进程占用的内存空间不一定非要连续。代码段、数据段、堆栈分离。至少分成三块。不过这要求段里的内存空间是连续的，要求还是有点高。
- 分页：将内存分为基本单位。基本单位是连续的。方便后面的页调度，置换。
- 虚拟存储：希望把数据存在硬盘上，目前多数操作系统（例如Linux）使用的方案
地址空间&地址生成
地址空间的定义
首先是物理地址空间：是由地址总线的条数决定的
逻辑地址空间是CPU运行的进程所看到的地址
一个是内存的角度。一个是CPU的角度。
地址生成过程
https://www.bilibili.com/video/BV1xJ411W71v?p=23 11分
Ps：由CPU硬件去实现硬件转换（MMU）——后面要讲的页表功能。转换的表（页表）是由操作系统建立的。
地址检查
连续内存分配
内存碎片（含外碎片和内碎片）
碎片分为两种，外碎片是两块之间的；内碎片是分配给进程区域内没法利用的区域。
外碎片：两块之间小的空闲块。
内碎片：比如说程序需要510字节，但分配内存只能以2的整数幂的形式分配512字节。多出来的2字节就是内部碎片。
动态分区分配
大小可变，地址连续。
操作系统需要做的事是维护一个已分配分区的数据结构，还要知道空闲分区的大小位置等信息。
对于找分区的不同，有以下策略。动态分区的分区策略（排序算法不同）：
- 最先匹配
- 最佳匹配
- 最差匹配（由大到小，第一个就是）
最先匹配（first fit）——碰着那个是哪个
first fit 内存分配算法：
最佳匹配（best fit）——找个最好的位置，大小合适
最差匹配——找最大的空闲分区
碎片整理
碎片紧凑
我们想把他们压缩在一起，这样可以腾出更多连续的区域供分配。但不是你想动就能动的。必须所有进程都支持动态重定位。不允许正在运行的时候搬动，绝对地址程序也不可以。关于具体的做法再议。
问：什么时候可以搬动？
答：进程处于等待状态的时候才可以搬动。
关于开销问题也要考虑不是任意时候想怎么搬动就怎么搬动，要考虑综合的开销。
分区对换（早期内存紧张的时候）
第二种做法是分区对换
https://www.bilibili.com/video/BV1xJ411W71v?p=25 第4分钟
思路：
把处于等待状态的P1放在外存中：
在Linux中swap早期就是为了扩展内存用的。早期内存很紧张。把处于等待状态的进程移动到外存中。
连续内存分配实例：伙伴系统
第一维是空闲块的大小，从小到大排成第一维。
参考信息： 
我们在实现的时候，就实现这两个函数alloc 和 free就行了。
非连续内存分配
改进：连续内存分配很麻烦，例如有时候用户想要一块内存，但内存中恰好没有连续的一块内存给他分配。
其中段式分配的块比较大，页式分配的块比较小。段页式是将段式和页式结合起来的方法（十分重要）
非连续内存分配的目标是提高利用效率。
eg：例如共享函数库
Ps：简单来说段式存储分配的比较大，以段为基本单位。页则更小，分配的时候以页为单位。
段式存储管理（以段为单位分配）
段地址空间
一般来说也很少有跨段访问的情形。
这样在物理空间中就可以不连续了：
段访问机制
逻辑地址由二元组由段号s和段内偏移地址addr表示：
访问的具体过程可以参考视频：https://www.bilibili.com/video/BV1NE411R7dp?t=251.1&p=36
页式存储管理（分成更小的块，以页为单位）
页式存储管理的概念
在32位机器中，4k，4096B是常见的页帧大小。页帧用来描述物理页面，页面用来描述逻辑页面。
逻辑地址到物理地址的转换
- 页表：用于保存转换关系
- MMU（存储管理单元）/TLB（快表）：让地址转换快速的进行
下图S是帧的位数：
举个例子：不管是逻辑地址空间还是物理地址空间计算方法一样
物理地址空间的划分：
逻辑地址空间的划分：
页表
具体查询过程可以看视频：https://www.bilibili.com/video/BV1NE411R7dp?t=387.6&p=37
f左移s位，加上偏移o。
页表负责逻辑页号到物理帧号之间的转换：
页表结构：
修改位：对应的页面中的内容是否修改了。
引用位：在过去一段时间，是否对他有引用，是否访问过。
实例：https://www.bilibili.com/video/BV1NE411R7dp?t=179.3&p=38
性能问题：需要两次访问，获取页表项和访问数据；内存很大的话，页表也非常大。
如何解决？
- 缓存：快表
- 间接访问：切分成子表（多级页表）
快表和多级页表
快表，CPU里面有个关联存储器（TLB）。可以同时的查询多个关联项。虽然在CPU里查找比内存中快得多，但是CPU里的这个快表不能做的太大。
多级页表：通过间接引用将页号分为若干级。上图形成页表树。
查询方式：p1作为第一级页表的偏移找到二级页表的地址；p2作为二级页表项的偏移找到三级页表的地址；从三级页表找到物理内存地址。
Ps：突然想到了数据库里的B+树
可以有效减小页表长度。可以类比查询算法，二叉查找树之类的。
举个例子：
逻辑地址的低10位作为偏移，中间的5位作为第二级页表p2（第二级页表号），高5位作为第一级页表的p1；intel处理器有CR3寄存器，它保存着第一级页表的起始位置。第一级页表的页表项作为第一级页表的起始位置，再加上p2算出来f。
反置页表和页寄存器
提出反置页表的原来是多级页表在大地址空间系统中表现得很繁琐。
针对上面的繁琐问题，页寄存器和反置页表是两个类似的做法。——让页表和物理空间的大小对应起来，而不是逻辑空间。因为逻辑空间的大小大啊
页寄存器的实现
页寄存器中的地址转换
反置页表
Ps：如果vpn不同就表示有冲突，那么就找next。Index就是页帧号。
段页式存储管理（重要）
段式+页式
，所以我们最好将段式和页式结合。
段页式存储管理例子
段页式存储管理中的内存共享
