os CH8 内存管理
CH8 内存管理
8.1 background
CPU只能直接访问内存（memory）以及一系列内置的寄存器（无法直接访问磁盘），想要执行指令的时候，一定需要先把指令从磁盘移到内存中； 依旧分层结构
- 大部分计算机进行执行命令的时候是经过如下的步骤：“Repeatedly perform fetch-decode-execute cycles”
- 地址的概念：
也就是，实际进程运行的时候的虚拟地址转化为实际的物理地址来进行memory的寻址
限长寄存器设定了最长的长度，并且限制不让其去访问别的进程的空间
- 整个程序的生命周期：首先编译生成.o文件，然后和别的文件进行链接，最终装载生成可执行文件进行运行。
- 内存管理单元（MMU）：这是一种硬件设备，通过使用页表等结构实现物理地址和逻辑地址的转换：这里引入了relocate register（重定位寄存器）的概念，每一次转换的时候直接将虚拟地址的值加上重定位寄存器中的值实现地址转换，如图所示
- dynamic load（动态装载）：初始的静态载入会一开始将程序相关的内容全部装入memory，但是动态装载的思想就是用到哪个部分再加载相应的部分即可。
- dynamic linking（动态链接）：会将库函数全部加载到一个shared memory中，然后在我程序的相应位置会打上一个stub；执行到这个的时候，会跳转到相应的地方来执行这个指令，不同的进程带着自己私有的参数，跳转到完全相同的虚拟地址去执行完全相同的代码
8.2 swapping（交换技术）
这里指的交换技术，指的是内存和磁盘之间的一种交换技术：让一个进程读到memory，运行一段时间，再将其存回磁盘中。相关的基础概念介绍如下：
这里我们讨论的基本是整进程的换入和换出；正常情况下，禁止交换，当空闲内存低于某一个阈值时，启用交换换出；当空闲内存增加一定数量时，停止换出。
需要注意的是，一般移动系统是不支持交换的，具体细节如下：
8.3 continuous allocation（连续分配）
接下来介绍的都是一些内存分配的策略
8.3.1 单一连续分配
依旧采用前面介绍的MMU base limit register；用户空间会全部给一个大进程
8.3.2 多分区分配
分区式管理的基本思想是将内存划分成若干个连续区域，称为分区。每个分区只能存放一个进程。 1. Fixed Partitioning（固定分区）在装入前，各个进程需要提供需要的空间大小，然后首先划分固定的大小，然后装入程序，适用于多道程序分配（这个地方会带来内部碎片） 2. Dynamic Partitions（动态分区）按需分配：进程需要多少空间，就给其分配多少空间；操作系统需要维护如下的信息： allocated partitions （已分配的分区） free partitions (hole) （空闲的分区） 自然地想到，当空闲的空间很大的时候，需要一个算法来帮助选择某一个特定的内存需要哪一个分区；以下是三种算法
；为了帮助理解，以下是三个例子
优先利用低地址空间，将完整的高地址空间留给大进程 缺点：低地址不断被分割，产生大量的外部碎片；同时每次都必须从低地址从头开始寻找，效率不高。 
优先选择空闲分区满足大小的最小的空间；缺点是依然会留下越来越小、越来越难以利用的外部碎片，并且效率其实也不高
和best-fit恰恰相反，每次选择空闲分区满足大小最大的空间这样就会避免产生大量的外部碎片，但是大空间会被快速使用掉，这样之后真正的大进程到来的时候就可能没空间了
最后一种算法综合了前面算法的优缺点：所谓的next-fit
主要是改进了first-fit，使用一个指针，指向上次查找分配结束的位置；然后从上次的结尾开始向后找，这样的效率较高。 缺点：头指针之前的大量空间无法被利用 综合来看，总结如下：
一般来说：First-fit and best-fit better than worst-fit in terms of speed and storage utilization
介绍一下内部碎片和外部碎片
内部碎片是分配给进程空间内实际没有被使用的空间，外部碎片是因为memory中一段空间太小无法被分配给进程的空间
一些减少外部碎片的方法：可以通过移动已经使用的进程和空闲空间中代价较小的到一端，相当于把空闲的区域拼凑了起来，这样就可以利用之前外部碎片的空间。
8.4 Paging(分页，页式管理)
基本思想是，首先将整个主存分成若干个小的单元，然后以这个为单位，将空间分配给各个进程
这里注意区分概念：逻辑地址的block叫做page，物理地址的block叫做frame；它们二者是一一对应的，n个page就需要去在物理地址找到n个frame，二者的大小是相等的
以及page table:page table列出了进程的逻辑页与其在主存中的物理帧间的对应关系;其本质上也是一种动态重定位的技术。 我们可以知道，其不会产生外部碎片（因为每个frame都可以被分配出去）但是如果frame内部没填满，内部碎片依然存在。 
简单看，逻辑就这样；在这样的机制下，虚拟地址被分为两个部分：页号以及页内偏移（offset） 也就是说，根据虚拟地址计算出对应的物理地址的公式应当是physical_address = page_number * page_size + offset
8.4.2 Address Translation Scheme
对于逻辑地址的拆分：
8.4.3 Page table implementation
操作系统需要为每一个进程建立一个页表，并且将其保存在主存中
PTBR指向页表的基地址，PRLR标明页表的长度。因此，每次存取都需要访问内存两次；首先访问页表，得到物理地址；然后访问物理地址，得到真正的数据。
为了避免（减小）第一次访问的时间，可以通过引入TLB来解决；在os这门课中，associative memory与其功能类似
recall一下整个过程：首先去TLB里面找，找到就好，要是没找到，那么就需要去memory中找，并且找到之后还要：1. 在TLB中存入新的项 2. 去读取内容
当TLB读满之后，采用一些策略换出老的项。
因此，自然地引入有效访问时间（Effective Access Time)的计算方法
（和体系结构类似）
页表使用一个valid位来限定；根据PRLR限定的一个进程的逻辑地址空间，只要在这个范围内就是v，否则就是i。
页的共享：需要记忆的是：如果使用shared code，那么对应的虚拟地址必须都相同；private code就不需要
e.g.对于复用的ed段代码，对于不同的进程进行复用共享
8.4.4 Structure of the Page Table(页表的结构)
为了优化存储页表的空间，有很多不同的页表种类。 1. Hierarchical Paging（分级页表）其实你就理解为图书馆内找书的过程：首先确认楼层，然后确认阅览室，最后确定书架，这样去查找的效率显然会更高。（一般地，适用于32位的系统） 2. Hashed Page Tables（哈希页表） 适用于32位以上的系统（64位系统），其具体的操作流程如下：
首先使用hash函数对于虚拟页号算出一个值，然后针对算出的hash值，在链表中进行比对，找到完全符合的项。 3. inverted page tables（倒置页表）内存中，对于倒置页表有一个这样的布局：
怎么理解这个东西呢？相当于，之前我是以进程为单位，每一个进程记录自己对应的虚拟地址和哪些物理地址建立映射；而这里是直接对于每一个物理页，记录自己对应的虚拟地址和进程号，并且对于这里维护的这个表：
回忆一下这个题：
答案是B，这里需要注意的是二级页表中，所有的页表项需要能被放在同一个页里面，所以有页号位数最多是log2(512)=9
页表项中包含的内容：页表框（物理地址和逻辑地址的映射），以及有效位等等
8.5 segmentation（分段式管理）
在分段式管理中，所有的逻辑地址中的内容是由一个个“段”组成的，这里段我理解是一些有相同功能的数据集合，比如main memory段 data段 stack等等；用户不需要知道它们具体的位置，只需要给他们各自“名字”就可以使用
所以，维护一个段表，来记录各个段在物理内存中对应什么地址即可
对于使用段的方式，其地址方式也是段号+偏移量；然后会有一个段表记录对应关系； 然后寻址的时候，是使用基址+限长的方式；首先使用段号找到对应的段的基地址；然后，查看是否在限长范围内，如果是的话取出，不然返回fault。 
段式存储的保护位，有有效位（v），读写执行保护位等等，一个具体的例子：
8.5.2 Segmentation with Paging 段页式管理
一些习题：
答案：DDBA
在计算虚拟地址映射的时候，要注意区分什么时候是缺页中断（现在还没有建立当前页的映射）和什么是越界中断（当前的虚拟页号超过了总的空间）