# Address Translation, Caching ## Virtualization Resources 通常计算机的硬件只有一套，CPU、内存、硬盘以及其它设备，而不同的进程/线程需要分享这些硬件，因此操作系统需要提供这些设备的**复用 （Multiplex）**功能。 本节讨论操作系统如何支持内存复用（Memory Sharing），从而让系统内的各个进程/线程按既定方式运行，互不影响。在这个过程中，我们将了解到操作系统的更多方面： * Protection * Multi-programming * Isolation * Memory resource management * I/O efficiency * Sharing * Inter-process communication * Debugging * Demand paging #### Single and Multithreaded Processes 如下图所示，线程是进程的活动单元，每个进程中可以有多个线程并发执行，因此线程也是进程的并发单元，线程之间共享 code、data 和 files，但每个线程拥有各自的 registers 和 stack 数据。 ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZbdmK1UK9Vegu5oCv0%2F-LZbQkPlIX54VFPK3doM%2FScreen%20Shot%202019-02-26%20at%209.32.50%20AM.jpg?alt=media\&token=fcce046c-8bd0-4859-9c80-6688b812ef79) 因此在内存复用的过程中，我们需要考虑到三个重要因素： * Controlled overlap：线程之间只共享允许共享的部分。 * Translation：将 virtual address 转化成 physical address，前者给处理器使用，后者给物理内存使用，中间的这层 indirection layer 可以提供两个功能： * 防止不同进程的内存空间重叠 * 让所有程序都貌似独占所有内存空间 * Protection：防止其它进程访问本进程的私有内存空间，包括用户进程访问用户进程、用户进程访问系统进程等。 假设系统中有一个进程 A 正在运行，如下图所示： ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZbdmK1UK9Vegu5oCv0%2F-LZbTj8SJn8wOI4rGZ6V%2FScreen%20Shot%202019-02-26%20at%209.45.55%20AM.jpg?alt=media\&token=6f048ea3-b92c-4d6c-81c1-7ce000393750) 图左边是进程视角，该进程认为自己拥有整块内存；图中间是 indirection layer，负责将进程的虚拟内存地址转化成物理内存地址；图右边是进程 A 实际使用的物理内存空间。这时候，具有相同程序的进程 B 启动，同样地，经过 indirection layer，进程 B 实际使用的是另一块物理内存地址，如下图所示： ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZbdmK1UK9Vegu5oCv0%2F-LZbUZzKmDpAUtLExJjl%2FScreen%20Shot%202019-02-26%20at%209.49.36%20AM.jpg?alt=media\&token=fcaeeae0-83f5-4fc0-a768-20a0b8934847) ## Translation & Protection 抛开任何已有的内存复用方案，假设我们从程序的编译到执行的过程来思考如何做内存复用，如下图所示： ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZbdmK1UK9Vegu5oCv0%2F-LZbW8MnhribubE7T8E9%2FScreen%20Shot%202019-02-26%20at%209.56.22%20AM.jpg?alt=media\&token=96f4023b-56e6-4fed-84d0-0454ea783fa1) 一个程序从代码到运行时，期间主要有以下 3 个阶段： * 编译阶段（compile time）：即 gcc 的工作 * 加载阶段（load time）：即 ld 的工作 * 执行阶段（execution time/runtime）：dynamic libs，一些 library 已经载入到内存中，因此这些 library 中 routine 的地址将在运行时才被确定。 而最终进程所使用的物理内存地址可以在这个过程中的任意阶段被绑定，这取决于硬件和操作系统。 ### Uni-Programming 当系统中始终只有一个进程运行时，我们可以将整块内存直接给它： ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZbdmK1UK9Vegu5oCv0%2F-LZbZ0t5w5FN7S_SUelf%2FScreen%20Shot%202019-02-26%20at%2010.09.02%20AM.jpg?alt=media\&token=93e4f80c-2636-4a1a-adcc-89c3cdb1e27d) ### Multi-Programming #### Base\&Limit 当系统中有多个（假设 2 个）进程运行时，怎么办？使用 loader/linker 在加载程序的时候调整其访问的内存地址： ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZbdmK1UK9Vegu5oCv0%2F-LZbZl5ccYUGvGz8Q08B%2FScreen%20Shot%202019-02-26%20at%2010.12.15%20AM.jpg?alt=media\&token=2656bd7b-bb26-43eb-87be-2dbef79c970f) 但这种方式无法为进程之间提供内存保护，容易导致进程，甚至操作系统崩溃。我们可以想到一个最简单直接的解决方案，为每个进程（在 PCB 中）记录一个 BaseAddr 和 LimitAddr，每次进程访问内存时，检查目标内存地址是否处于这个范围内，若不在则抛错。操作系统负责控制和管理所有进程的 BaseAddr 与 LimitAddr，用户进程不被允许访问这些信息。 #### Address Translation 将 Base/Limit 方案抽象一层，我们就可以得到一个更加泛化的方案，即 Address Translation： ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZbdmK1UK9Vegu5oCv0%2F-LZbdD4ILapiMrdOt_D7%2FScreen%20Shot%202019-02-26%20at%2010.31.43%20AM.jpg?alt=media\&token=c04f59dc-72ce-4ea6-b52e-15794f9a8d11) 中间的 Memory Management Unit（MMU），负责将虚拟内存转化为物理内存，我们可以在这层抽象中加上 Translation Protection 的逻辑。将进程细化成 Code、Data、Heap 和 Stack，就可以得到更细致的示意图： ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZbdmK1UK9Vegu5oCv0%2F-LZbe7rGeE9r6A_xhYNb%2FScreen%20Shot%202019-02-26%20at%2010.35.44%20AM.jpg?alt=media\&token=85afdf7b-24a3-4793-9aea-15659ade3351) #### Simple Base and Bounds (CRAY-1) 在每个虚拟内存访问经过 MMU 时，统一作一次 Base 大小的位移，然后利用 Limit 来控制可访问的范围大小，如下图所示： ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZbdmK1UK9Vegu5oCv0%2F-LZbfGGm2nL1-N0QZkHW%2FScreen%20Shot%202019-02-26%20at%2010.40.40%20AM.jpg?alt=media\&token=742ec08d-87bd-4937-ac8e-301c4d7ebe9f) 这种方式使得每个程序都认为自己拥有从 0 开始的整块内存资源。而对于操作系统来说，每个进程都将获取连续的、整块的内存空间，同时当进程被放入另一个内存区域时，不需要重新为进程重新分配地址。 但 Base\&Bounds 方案也有它的缺陷，如： *碎片化问题（Fragmentation）* 由于不同的进程大小不同，随着不同的进程陆续进出，内存空间将出现碎片化问题，如下图所示： ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZbdmK1UK9Vegu5oCv0%2F-LZbgX3VAFWinXe-mWjy%2FScreen%20Shot%202019-02-26%20at%2010.46.11%20AM.jpg?alt=media\&token=45093db0-eea8-4fdb-b29d-b316aa1f94c0) *稀疏地址空间问题（Missing Support for Sparse Address Space）* 比如 Stack 和 Heap 会生长 *进程间共享问题（Inter-process Sharing）* * 共享 code segments * 进程间共享内存空间 * 可以通过一定方式的重叠来做，但很蹩脚 #### Multi-Segment 基于 B\&B 方案面临的问题，设计者又提出可以将进程进一步拆分成不同的 segments，如 Code、Data、Stack 等等。每个 segment 都给定 Base 和 Bound，可以被分配到物理内存的任意位置，如下图所示： ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZbdmK1UK9Vegu5oCv0%2F-LZblvCxKIXHlrKmd_s1%2FScreen%20Shot%202019-02-26%20at%2011.09.44%20AM.jpg?alt=media\&token=174a50ad-c2f5-4274-8611-fc1fb4787269) 实现如下图所示： ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZhD7LFzETdo126NVrv%2F-LZgstxoKf_x6f03ofC-%2FScreen%20Shot%202019-02-27%20at%2010.58.19%20AM.jpg?alt=media\&token=b0c150f1-361d-48cd-8e94-251a1453b323) 每个程序运行时，系统内部会维护一个 segment map，后者记录着每个 segment 的 base 和 limit，以及一些元数据，当程序运行时，其虚拟内存的前几位确定 segment 的位置，后几位表示基于 base 之上的 offset，同时验证是否在允许访问的范围内。最后一个 bit 表示这个 segment 是否正在使用中。系统为不同的程序维护不同的 segment map，从而为不同进程提供保护和共享功能，如下图所示： ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZhD7LFzETdo126NVrv%2F-LZh1lA10wDqDZjqlWx7%2FScreen%20Shot%202019-02-27%20at%2011.41.25%20AM.jpg?alt=media\&token=85e24c5a-5a6b-41c2-8606-3c25dce3c03d) 如果所有进程无法都放进内存中怎么办? 只能靠 swapping，为给新的进程腾退空间，操作系统需要选择性地移动一些已经在内存中的进程到硬盘上，但这种做法使得上下文切换（Context-Switch）的成本大大提高。能否有一种方案能够只将每个进程中最活跃的部分数据读入内存中，既能增加同时处于内存中的进程数量，又能够减小上下文切换的成本？ Multi-Segment 方案的缺点总结： * 必须将大小不同的 segment 放入物理内存中，可能需要复杂的位置调整策略才能将更多的进程放入内存中 * swapping 的成本大 * External/Internal Fragmentation #### Paging 基本想法就是把物理内存进一步划分成更小的（通常为 1-16KB）大小相同的块，成为 pages，使用 bitmap 来记录每个 page 的状态（allocated/free）。这时候，相应地，操作系统需要为每个进程维护一个 page map/table，里面记录着每个 page 的位置，以及相关权限控制信息（V - valid， R - read， W - write），如下图所示： ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZhD7LFzETdo126NVrv%2F-LZh9JINM_kdG3XEN_ea%2FScreen%20Shot%202019-02-27%20at%2012.14.25%20PM.jpg?alt=media\&token=0e1e1c0f-d9b2-463e-b05f-0a9ab51e0801) 假设系统内存有 256 byte，那么每个内存地址的长度为 8 位，假设每个 page 大小为 4 byte，一个进程的虚拟内存、page table 以及物理内存分布如下图所示： ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZhD7LFzETdo126NVrv%2F-LZhAme1FoN-ktAu9fu6%2FScreen%20Shot%202019-02-27%20at%2012.20.52%20PM.jpg?alt=media\&token=ca6a4452-dad4-4288-8a7d-cc2bd7e5b7d9) 想要共享内存，让两个进程的 page table 的部分 entry 指向相同的 page 即可，利用权限控制信息来决定保护策略，如下图所示： ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZhD7LFzETdo126NVrv%2F-LZhBKUiZK-X-hQETyNb%2FScreen%20Shot%202019-02-27%20at%2012.23.14%20PM.jpg?alt=media\&token=2245e6ed-e5da-43d3-8699-d01ba1609a67) 典型的 Linux 32-bit 内存区域分布如下图所示： ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZhD7LFzETdo126NVrv%2F-LZhCCu1P6zJRUCTVQV2%2FScreen%20Shot%202019-02-27%20at%2012.27.06%20PM.jpg?alt=media\&token=f2a10b0b-5f4c-40da-9c46-10b391387451) 对应到 paging 策略，一个典型的进程内存区域分布如下图所示： ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZhD7LFzETdo126NVrv%2F-LZhCP1Cr3boa1mXd9Wl%2FScreen%20Shot%202019-02-27%20at%2012.27.55%20PM.jpg?alt=media\&token=0567c6d5-8aee-4b70-8ea8-e29024a6b2a5) 在 paging 策略下，上下文切换只需要修改 page table pointer 和 limit，注意与 multi-segment 不同，这里只需要以 page 为单位进行置换，使得系统不必整块整块地在内存与硬盘之间交换数据。 paging 策略的 Pros & Cons: * Pros * simple memory allocation * easy to share * Cons * address space 是稀疏的，32 位系统，假设 page 大小为 1KB，则每个 page table 的大小为 2 million #### Multi-level Translation *Two-level Paging* 将 page table 从链状组织成两层的树状结构： ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZhTwXqOTthy8w6pbIt%2F-LZhUxUVK-ptSZq-ftuc%2FScreen%20Shot%202019-02-27%20at%201.48.54%20PM.jpg?alt=media\&token=63c52ea4-cdaa-40b7-be16-b63ce2bd1837) 示例如下： ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZhTwXqOTthy8w6pbIt%2F-LZhV97XpEEUzxVpPMCh%2FScreen%20Shot%202019-02-27%20at%201.49.51%20PM.jpg?alt=media\&token=14cc41ee-e5d3-4572-bc1d-b38fe201ed87) * Pros * 与 Simple Page Table 相比，存放在内存中的 pageTable 很小，节省存储资源，同时可以利用 demand paging 的方式来按需获取次级索引 * 在 context-switch 的时候，只需要修改 pageTablePointer，而不需要修改整个 pageTable *Segments + Pages* 类似地，也可以考虑结合 segment model 与 paging，如下图所示： ![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZhTwXqOTthy8w6pbIt%2F-LZhVbeyG6Ql1-A_4moG%2FScreen%20Shot%202019-02-27%20at%201.51.51%20PM.jpg?alt=media\&token=287b74bb-2b40-49e3-9235-9a1bce6e5fe2) Multi-level Translation 的内存分享与 paging 类似，不再赘述。Multi-level Translation 的 Pros & Cons 分析如下： * Pros * 只需要为所需的 page table entries 分配内存空间即可 * 内存分配、分享、保护都比较简单，另外可以在 segment 或者 page 粒度上分享 * Cons * 读取成本变高，需要先通过一次或多次读取 page table，才能访问到最终的数据 ### How is translation accomplished * Hardware Tree Traversal * 对每个虚拟地址，在硬件上遍历 page table * 如果发现 PTE (page table entry) 不合法，则触发 "Page Fault"，Fault handler 来触发后续的 page 获取操作 * Pros：速度快 * Cons：在硬件上，不灵活 * Software Tree Traversal * 在软件上完成上述遍历 * Pros：灵活 * Cons：慢 ### Dual-Mode Operation 操作系统为了保证进程不能修改自己的 translation table，提供了双模操作，及 Kernel mode 和 User mode，所有相关操作只能在 Kernel mode 中执行。 #### 创建用户进程 步骤如下： 1. 分配并初始化 address-space control block 2. 将程序从硬盘中读入内存 3. 分配并初始化 translation table 4. 执行程序 * set machine registers * set hardware pointer to translation table * set processor status word for user mode * Jump to start of program #### 切换进程 * save/restore registers * save/restore PSL (hardware pointer to translation table)