虚拟化
- 为什么需要OS
下面为之前记录的
虚拟化
多级反馈队列
之前的调度方法的前提是：知道某一个任务执行的时间，这显然不符合现实，为此提出了MLFQ方法。
策略：
- 有很多队列，从上到下优先级递减。
- 开始时，所有的任务都放到最高优先级队列中，优先级高的先执行，相等的轮着执行。
- 若在一个时间片内完成了任务，则优先级不变，否则优先级降低。
这样设计的初衷是：尽可能将对于响应时间要求比较高的任务放到，优先级高的队列当中，例如键盘鼠标的输入等交互操作，而计算密集型的任务的优先级降低。但这样也存在问题，例如：
- 若有许多的交互操作的话，会导致低优先级的任务执行的时间会减少，解决方式是：每经过一段时间，就将所有的任务都放到优先级最高的队列当中。
- 可能会有恶意的程序，在每个时间片之前主动放弃
CPU，去执行类似I/O的操作，从而达到优先级不会降低的目的。这样该程序就可以绝大多数时间都占用CPU，甚至达到99%这样的占有率，解决方式是：优先级降低的策略改成：在每一层队列当中执行的时间达到一个确定的值，则优先级降低。
调度：比例份额
策略：
- 通过随机数：首先为每一个进程发彩票，例如：
A分到了100，B分到了50，C分到了200，每隔一段时间（例如隔一个时间片）计算0~350的随机数，分到谁就执行谁。（这里若先降序再找，可以保证，查找的次数不变） - 通过步长：彩票越多的步长越短（步长通过很大数除以彩票数获取）。执行方式：
- 每一次找
cnt最短的执行，执行完后cnt += 步长，若出现cnt相等的情况，则随机执行。
- 每一次找
随机数的策略，若执行时间较短的话，可能会出现两个彩票数相等的任务执行的结果是一个在前一个在后，但我们希望权重相等的任务的完成时间应尽可能的接近，因此说明通过随机数，期望是我们想要的，但若随机的次数较少，则结果可能不尽如意。
步长的策略，相比于随机数，需要维护很多cnt的值，而且若几个任务执行的过程中，来了一个新的任务，cnt不好确定。
由于最重要的：一开始如何确定每个任务的彩票的，的问题不好解决，因此这种策略应用不是很广泛。
抽象：地址空间
对于内存的使用：以前的程序比较简单，不需要多个进程共享内存。
0---------------------------------max
操作系统 当前程序
0---------------------------------max
后来人们希望能共享机器，也就是共享内存。
0-----------------------------------------------------max
操作系统 程序1 空闲 程序2 程序3 ...
0-----------------------------------------------------max
当运行到某一个程序，就需要保存其他程序的数据状态等，这些数据若是放到磁盘的话，store和load比较耗时，所以也都放到内存当中。（若内存空间不够该怎么办呢？）
每一个程序所分配到的内存：
0----------------------------------------------------16kb
代码，数据 堆 → → → ← ← ← 堆
0----------------------------------------------------16kb
每一个程序开始的地址看似是0，这都是虚拟地址，需要操作系统在硬件的支持下，进行地址的映射。
共享内存很重要的一点就是隔离，一个程序的失败或者错误不会对其他的程序有影响，甚至对操作系统有影响，不能随便访问到其他地址空间的值。
虚拟化内存的三个目标：
- 透明
- 高效（虚拟化的过程不能耗费太多时间，即相比于不虚拟化，直接使用物理地址）。要保证这一点就需要硬件的支持（类似
TLB）。 - 保护（也就是上面提到的隔离）
插叙：内存操作API
介绍了动态分配内存，类似malloc、free等。mmap？
机制：地址转换
为了实现前面提到的隔离，需要两个寄存器（只有一个，所以在进行进程的切换时，需要保存这些值），用于记录开始和结尾，若访问的内存地址超过了该范围，就触发异常。
操作系统再分配内存时，需要找到未使用的地址空间，所以需要一个列表来记录这些空间。
要实现这些功能需要硬件支持很多的功能，P105。
简单的实现虚拟内存的过程（目前的前提是每个进程的所占的空间相等，就比如上面的16kb，且空间并不会超过物理内存）：
创建：找到空闲的内存空间。
销毁：释放这些内存。
上下文切换：将需要记录的状态保存起来。
异常处理：当遇到什么情况时，执行什么代码。
大概流程应该就是这样：正在执行某个进程的某一行代码，这一行需要访问2kb位置的数据，再去看一下记录开始和结尾的寄存器，如果ed - st大于2就执行即可，否则异常处理。因此这一章也叫作地址转换。
但是这种方式也存在问题:
- 因为每一个进程所分配的内存都是固定的，且栈和堆的空间在两头，向中间扩大，若该进程使用的栈空间和堆空间很小的话就会造成中间空间的浪费，这种浪费也叫作内存碎片。因此还是需要更好的方式。
- 若内存中空闲的内存不连续，但是总和是够一个进程运行所用的空间，但这种简单的策略还是不能处理这种情况。
分段
代码、数据部分，栈部分，堆部分都有一个单独的st和ed。但是好像这样的话，各个部分内部还是会有浪费的情况？
分段存在的问题：
- 上下文切换时，需要存比之前更多的信息（不过这个应该还好）。
- 分的段多了以后，会有很多外部的内存碎片，尽管有很多分配的算法，但本质问题还是没有解决。
还有就是原文中最后这一段没看懂。😥
第二个问题也许更重要，分段还是不足以支持更一般化的稀疏地址空间。例如，如果有一个很大但是稀疏的堆，都在一个逻辑段中，整个堆仍然必须完整地加载到内存中。换言之，如果使用地址空间的方式不能很好地匹配底层分段的设计目标，分段就不能很好地工作。因此我们需要找到新的解决方案。你准备好了吗？
空闲空间管理
malloc返回的地址再往前有一块小内存，存储了一些必要的信息，比如分配的内存的大小，所以在free的时候只需要传入地址就能释放内存，size = (p - sizeof(size_head))->size。
列表可以是一个链表，每一个结点存储了空闲内存的起始位置以及大小。空闲列表的过程：
- 当需要动态分配内存时，就从列表中找一个满足条件（找这个的过程就有很多的算法，目标是优化查询的速度，或许还有减少外部碎片？使用复杂的算法来换取时间）的空闲空间，将该部分一分为二，第一部分来使用，第二部分还是在空闲列表中，当然前提是有第二部分，若恰好用完那么也就没有了。
- 当需要释放内存是，将所占用的内存空间加到空闲列表当中，同时向前向后检查是否可以合并，那这也就是说明这种策略中空闲列表是根据下标有序的。
分页：介绍
一个简单的例子：
前提：每一段都是固定的大小，本例中为
16个字节。将
64字节的空间存到128字节的物理内存当中，也就是需要将4份分配到8份。对于64字节需要6位来表示，，高两位用于表示，选择四个中的哪一个内存块，低四位用于表示偏移量。在虚拟地址映射到物理地址过程中，表示物理地址的位数必须大于等于 7，因此需要将高两位映射到高三位，偏移量还是用四位表示。
操作系统通过虚拟页号（VPN，也就是上面例子的前两位）检索页表，找到该位置的查找页表项（PTE），以便找到物理页号（帧号）。PTE中也有很多内容：
- 保护位：表明该页是否可以读、写或者执行
- 存在为：表明该页是在内存还是在磁盘，通过放到磁盘来完成小内存处理大数据的问题。
- 脏位：
- 参考位：记录该页是否被访问，来确实该页是否受欢迎。
目前分页很大也很慢：
- 大：对于
32位的寻址空间，假设每一页的大小是4kb，那么高20位用于选择哪一个内存块，低12位表示偏移量，假设每一个页表项为4字节用于转换物理地址以及存有用的信息，例如上面提到的很多位，。 - 慢：映射过程还需要通过页表项。
相比于分段，没有外部碎片，因为每一段都是固定大小，但存在着慢或者大的问题。
分页：快速地址转换（TLB）
增加缓存，例如：计算100的物理地址，先去看看缓存中是否存在，若不存在就和之前一样通过查找页表项，去查找物理地址，同时放入到缓存当中，以便以后使用，直观来看页越大，缓存的命中率越高，但是缓存是不能太大的，太大就会慢，受光速和物理的影响。
当缓存满了时，来一个新的地址映射，就需要去除一个一个映射，这就需要选择一种策略来确定去除哪一项，比如LRU最近最少，但LRU在极端情况下也会有问题，例如：缓存的长度为n，但是我循环遍历长度为n + 1的某种数据，这样就会导致次次缓存不命中。
分页：较小的表
超越物理内存：机制
还是一样，计算100的物理地址，缓存中存在的话那皆大欢喜，若不存在的话相比于之前直接查找页表项，还多了一种可能，就是想找的页不在内存当中，这就需要将磁盘中存储的页load到内存当中，load的前提是内存中还有位置，但加入没有空间了，就需要寻找一种策略将目前内存中存在的页置换到磁盘当中。
超越物理内存：策略
介绍了多种置换算法，最优，先进先出，LRU，时钟算法。