操作系统入门——OSTEP读书笔记（虚拟化）
最近在学习性能优化相关的内容时，发现很多的性能指标（如/proc中的进程线程信息）、api实现机制（如mmap()底层实现方式）、改进方式等都与操作系统底层的实现密不可分，回想起工作以来就没有用过操作系统相关的知识了，正好从头复习一下。拜读了
虚拟化、并发和持久性
为了让计算机易于使用，比如多个程序并行执行（最简单的例子，同时运行用户界面和后台运算程序），操作系统需要为运行的程序提供一个假象：每个程序都单独占用着计算机的CPU和内存。这就是虚拟化技术。虚拟化又分为两个部分，CPU虚拟化和内存虚拟化。
而多程序运行，或是说程序进程内多个线程的执行，都会因为一些操作系统对运行程序提供切换支持时导致的一系列数据问题，这时就需要并发技术提供临界区的互斥手段。
另一方面，DRAM这种以易失方式储存数据非常不可靠，因此操作系统还需要在硬盘中持久化重要数据。管理这些储存数据的文件系统就是持久化的重要部分。
CPU虚拟化
操作系统需要提供正在同时运行许多程序的表象，但是实际上的CPU也只有一个，为了表现出这样的细节，就需要进程切换以及调度，操作系统将运行中的程序抽象为进程（Process），进程也作为操作系统用于调度程序的数据结构。
进程调度
这里为了便于理解，引入一个重要指标：周转时间，并且周转时间 = 完成时间-到达事件
在进行一个最简单的假设：
1．每一个工作运行相同的时间。
2．所有的工作同时到达。
3．一旦开始，每个工作保持运行直到完成。
4．所有的工作只是用 CPU（即它们不执行 IO 操作）。
5．每个工作的运行时间是已知的。
FIFO(First In First Out)
最简单的情况下，达到时间都为0，因此周转时间=完成时间
假设有三个任务 A:100 B:10 C:10(冒号后为他们需要的执行时间)
周转时间为(100 + 110 + 120)/3 = 110
SJF(Shortest Job First)
如果在全部任务都是同时到达的情况下，确实是最优解。但如果放宽条件2：B，C在10s才到达，在非抢占式系统中，要等到A执行完成才可以执行BC，这时周转时间=(100+(100-10)+(120-10))/3 = 103.33
STCF(Shortest Time-to-Compelte First)
引入抢占机制。每当新工作进入系统时，它就会确定剩余工作和新工作中，谁的剩余时间最少，然后调度该工作。
上述例子(10 + 20 + 120)/3 = 50。
更符合实际的程序运行情况，再引入一个新的指标：响应时间 = 首次运行 - 到达时间（如何构建对响应时间敏感的程序， 如果一个用户界面程序在提交很久后才得到运行，那么显然使用者的会体验非常糟糕）
轮转(Round-Robin)
在一个时间片内运行一个工作，然后切换到运行队列的下一个任务，而不是运行一个任务直到结束。如果响应时间是唯一指标，在合适的时间片定义下，RR是非常好的调度程序。但是对于周转时间来说，RR又是最糟糕的策略。
多级反馈队列 (Multiple Level Feedback Queue)
MLFQ中有许多拥有不同优先级的独立队列，每个队列有不同的优先级。任何时刻一个工作职能存在于一个队列中。队列中的多个工作使用轮转调度。
MLFQ根据观察到的行为调整其优先级。如果一个工作不断放弃CPU去等待键盘输入，这是交互型进程的可能行为，MLFQ因此会让他保持高优先级。相反如果一个工作长时间的占用CPU，MLFQ会降低其优先级。
MLFQ优化的规则
- 如果A的优先级 > B的优先级，运行A
- 如果A的优先级 = B的优先级，轮转运行A和B
- 工作进入系统时，放在最高优先级（最上层队列）
- 一旦工作用完了在某一层中的时间配额（无论中间主动放弃了多少次CPU）,就降低优先级（移入低一级队列）。
- 经过一段时间S，就将系统中所有工作重新加入最高优先级队列
受限执行
操作系统需要有效的运行程序，同时保留对CPU的控制权，否则任何一个程序都有可能获取控制权然后肆意修改用户的重要数据。现代操作系统将系统分为两种状态用户态和内核态，一些重要的API，仅在内核态可以调用。在某些情况下，运行中的用户程序会通过陷阱（可以是某些异常状态，或者是固定的时钟中断）陷入内核态，并将CPU控制权限交回给操作系统。
操作系统通过这样的形式保证程序可以在一定限制下执行，并且最大限度的保证程序运行时不受过多影响。
内存虚拟化
内存虚拟化也是操作系统提供给程序的一种假象，每个运行在操作系统上的程序都会感觉自己有一段非常大的，连续的内存空间用于存放他的代码和数据。操作系统通过虚拟化技术，为程序提供了虚拟地址空间，并在使用的时候，把对虚拟地址的调用转换为对物理地址的调用。
地址转换
通过硬件支持，使用基址寄存器和界限寄存器进行虚拟地址与物理地址之间的转换。
分段
普通的基址寄存器映射有可能造成堆栈之间的空闲空间。使用分段技术，在MMU（内存管理单元）中通过给每个逻辑段一对基址限界寄存器。通过一定位数表示对某个段的引用，剩下的位数可以表示段的偏移量，通过找到指定的段，结合两个寄存器内的数据将虚拟地址转换为物理地址。
但是分段这种方式也有问题：
- 由于段大小不同，可能会导致内存被分为大小不同的空间，导致满足内存分配会很难，造成外部的内存碎片。
- 如果有一个段用于表示一个很大但是很稀疏的堆，整个堆仍然需要完整地加载到内存中。
分页
分页概念在操作系统中十分重要。将内存空间分割成固定长度的分片，这就是分页。物理内存可以也视作一个固定大小的槽，数据在内存中的页，和物理页帧中移动。
页表
为了记录地址空间的每个虚拟页放在物理内存中的位置，操作系统通常为每个进程保存一个数据结构，这既是页表。页表可以为地址空间中的每个虚拟页面保存地址转换需要的数据。
在一个简单的地址转换过程中，虚拟地址可以表示为两个部分，虚拟页面号（virtual page number, VPN）和偏移量，通过页表中保存着的VPN和物理页帧的映射信息，找到对应的物理页帧，加上偏移量即可完成地址转换。
那么页表应该保存在哪里呢？内存中？可是由于每一个页都会有对应的页表项，而每一个进程都会有其对应的页表，这些用于储存页表的空间会非常大。比如一个32位的地址空间，页大小为4kb，需要20位的VPN和12位的偏移量（2^12）。20位的VPN意味着操作系统必须为每个进程管理2^20个地址转换。如果每个页表项需要4个字节，那么每个进程的页表就需要4M内存。
段页混合
通过将分页分段结合，减少页表的内存开销。仅仅为每个逻辑分段提供页表，比如为代码段、堆段、栈段各提供一个页表。
多级页表
将页表的结构改变为类似树的方式。将页表分为页大小的单元，如果一个单元内所有的页表项PTE无效，就完全不分配该页的页表。在这里新增了一个代表页目录的结构，页目录可以知道目标的页表在哪个页里。如果分页太小，页表树形结构的深度可能会超过两级。
TLB（旁路转换缓冲器）
由于页表也是保存在内存中的，一次内存访问就需要先去查找内存中的页表，之后才能得到地址在物理内存中的实际位置，这无疑是将访问开销翻倍。
这里引入了TLB，通过高速硬件做一个页表的缓存。
一个页表可能是这样的结构：
VPN | PFN | 其他位
TLB命中后，可以直接得到虚拟地址对应的物理地址，而不需要访问内存；如果未命中，则将这次访问的VPN和PFN存到TLB中。
SWAP
如果内存空间还是不能满足内存分配，操作系统会通过SWAP将内存内的数据置换到磁盘中，减少内存空间的压力。为了表示页被换出的状态，需要在页表中增加一位用于表示该页是否存在于内存中。