操作系统导论笔记1:虚拟化
操作系统导论第一部分:虚拟化。
CPU虚拟化
进程
进程：一个正在运行的程序。
fork() 创建新进程
wait() 等待子进程执行完毕
exec() 让子进程执行与父进程不同的程序
受限直接执行
硬件提供不同的执行模式：用户模式、内核模式
陷阱指令：调入内核并将特权升级为内核模式，执行操作，完成后操作系统调用一个特殊的从陷阱返回指令，回到用户模式。
内核通过启动时设置陷阱表，来实现os内运行代码的控制。
时钟中断：时钟设备每隔几毫秒产生一次中断，中断产生时运行中断处理程序，使操作系统重新获取cpu的控制权。
进程调度介绍
T周转时间 = T完成时间 - T到达时间
T响应时间 = T首次运行 - T到达时间
先进先出（FIFO）
最短任务优先（SJF）
最短完成时间优先（STJF）：SJF添加抢占，每当新工作进入系统，会确定剩余工作和新工作谁的剩余时间最少，然后调度该工作。
轮转（RR）：时间片长度必须是时钟中断周期的倍数；正在运行的作业在IO期间不会使用CPU。
如果愿意不公平，可以运行较短的工作直到完成，但是要以响应时间为代价；重视公平性，则响应时间会较短，但会以周转时间为代价。
多级反馈队列（MLFQ）
- 如果A的优先级>B的优先级，运行A（不运行B）。
- 如果A的优先级=的优先级，轮转运行A和B。
- 工作进入系统时，放在最高优先级（最上层队列）。如果不知道工作是短工作还是长工作，那么就在开始的时候假设其是短工作，并赋予最高优先级，如果确实是短工作，则会很快执行完毕，否则会被慢慢移入低优先级队列，这是该工作也会被认为是长工作了。
- 一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次CPU），就降低其优先级（移入低一级队列）。防止程序在时间片运行完之前调用IO主动释放CPU
- 经过一段时间S，就将系统中所有工作重新加入最高优先级队列。防止程序被饿死，程序从cpu密集型变为交互型保证调度程序会正确对待它。
比例份额
彩票调度：随机算法（智能概率上实现比例）
步长调度：可以每个调度周期做到完全正确，但需要全局状态（调度执行过程中如果有新进程加入无法处理）
比例份额没有作为CPU调度程序被广泛使用，因为不能很好适合IO，且票数分配问题没有确定的解决方式。
多处理器调度
时间局部性：当一个数据被访问后，它很可能在不久的将来被再次访问。
空间局部性：当程序访问地址为X的数据时，很可能会紧接着访问X周围的数据。
单队列多处理器调度（SQMS）
简单复用但处理器调度基本架构，多CPU共用一个队列。需要锁来保持原子性会带来较大的开销；缓存亲和性差，进程从CPU1到2运行的过程，会导致需要重新构造缓存。
多队列多处理器调度（MQMS）
包含多个调度队列，每个队列可使用不同的调度规则。具有较好的扩展性，队列随着CPU增加而增加，锁和缓存争用开销小；工作保持在固定的CPU上，缓存亲和性较好。
负载不均可以通过迁移来处理（工作窃取：工作量较少的队列不定期偷看其他目标队列，从工作量较多的队列窃取一个或多个工作，来实现负载均衡）
内存虚拟化
抽象地址空间
一个进程的地址空间包含运行的程序和所有内存状态。
栈stack：保存当前函数调用信息，分配空间给局部变量，传递参数和函数返回值。
堆heap：管理动态分配的、用户管理的内存。
内存操作API
对于C程序
栈内存：申请和释放操作编译器隐式管理。
堆内存：申请和释放操作有程序员显示完成。
malloc 分配内存
free 释放内存
地址转换
地址转换：硬件对每次内存访问进行处理（即指令获取、数据读取或写入），将指令中的虚拟地址转换为数据实际存储的物理地址。
动态重定位：每个CPU需要两个硬件寄存器，基址寄存器（地址转换）和界限寄存器（判断内存地址是否异常）。
MMU：内存管理单元。
分段
MMU中引入不止一个基址和界限寄存器，而是给地址空间内每个逻辑段一对。典型的三个不同的逻辑段：代码、栈和堆。
地址开头几位可以用来标识不同的段，剩余位表示段内偏移。
引入标志位是否正向增长，堆正向增长（由低到高），栈反向增长（由高到低）。堆和栈增长方向不同是为了最大化利用内存空间。
引入保护位（只能读取或执行），实现代码共享。
内存紧凑成本很高（因为拷贝段式内存密集型，占用大量处理器时间），更简单的做法是空闲列表管理算法。
空闲空间管理
空闲列表：在堆上管理空闲空间的数据结构。
最优匹配/最差匹配：遍历整个空闲列表，找到和请求大小一样或更大的空闲快，返回这组候选者中最小/大的一块。（需要全遍历，性能差）
首次匹配：找到第一个足够大的块。（会让空闲列表开头有很多小块）
下次匹配：多维护一个指针。指向上次查询结束位置。
分离空闲列表：如果某个应用程序经常申请一种（或几种大小的内存空间），那就用一个独立的列表，只管理这样大小的对象。其他大小的请求都交给更通用的的内存分配程序。
二分伙伴分配程序：但有一个内存分配请求时，空闲空间被递归的一分为二，直到刚好可以满足请求的大小（再一分为二就无法满足）。（块释放时，检查伙伴是否空闲，如果空间就合二为一，并向上递归）
分页
分页：将进程的地址空间分割成固定大小的单元，每个单元称为一页。
页表：主要作用是为地址空间的每个虚拟页面保存地址转换，从而让我们知道每个页在屋里内存中的位置。页表是每个进程一个的数据结构。页表存在内存里，也可以交换到磁盘上。
虚拟页面号（VPN）+页内偏移量 => 转换为真正的物理地址
页表项（PTE）
有效位：指示特定地址转换是否有效。
保护位：表示页是否可以可以读取、写入或执行。
存在位：表示该页实在物理存储器还是磁盘上。
脏位：表示页面被带入内存后是否被修改过。
参考位（访问位）：用于追踪页是否被访问，确定哪些页很受欢迎，应该保留在内存中。
分页：快速地址转换
在转换虚拟地址时，分页逻辑上需要一次额外的内存访问，这会导致变慢。
地址转换缓存（TLB）：通过引入TLB缓存来解决，地址转换带来的额外内存访问。
TLB上下文切换：在TLB中添加进程标识符，避免每次上下文切换需要清空TLB。
分页：多级页表
解决页表太大，占用内存太多。
将页表分成页大小的单元，如果整页页表项无效，就完全不分配该页的页表。通过页目录（PDE）来追踪，以此构成了二级页表。
有效位：若有效，该目录项指向的页表至少有一项是有效的。<
虚拟地址（页目录索引 + 页表索引 + 偏移量） => 转换为真正的物理地址>
在二级的基础上再次构造出多级页表。
TLB未命中时，会带来更多次的内存加载。
超越物理内存
交换空间：在硬盘上开辟一部分空间用于物理页的移入和移出。
页错误：访问不在物理内存中的页。
页表项（PTE）的某些位存储硬盘地址，当不在内存中可以找到硬盘的数据。
虚拟地址转换流程：
硬件从虚拟地址获得VPN（页目录索引+页表索引），检查TLB是否匹配。
如果TLB未命中，则硬件在内存中查找页表（使用页表基址寄存器），使用VPN查找该页的页表项（PTE）作为索引。
如果页有效且在物理内存中，硬件从PTE获取PFN（页帧号），将其插入TLB，并重试该指令。
如果不在物理内存中，操作系统用PTE中的位获取存储硬盘地址，执行IO将页读取到内存中。IO完成时，操作系统更新页表将此页标记为已存在，更新页表项（PTE）的PFN字段，并重试该指令。
页错误处理流程：
第一种：该页存在且有效，简单的从PTE获取PFN即可。
第二种：页不在物理内存。页错误处理程序需运行。
第三种：访问的是无效页，由于程序运行错误，操作系统陷阱处理程序运行，可能会杀死非法进程。
超越物理内存：策略
LRU策略：替换最近最少使用的页面。
近似LRU：每当页被引用（读或写）时，硬件将使用位置为1。但是硬件不会清除该位（即将其设置为0），这由操作系统负责。时钟算法（时钟指针开始时指向某个特定的页，当必须进行页替换时，操作系统检查当前指向的页P的使用位时1还是0。如果是1，则意味着页面P最近被使用，因此不适合替换。然后P的使用位置位0，时钟指针递增到下一页（P+1）。该算法一直持续找到一个使用位为0的页。近似LRU可以降低全扫描带来的性能开销。
考虑脏页：如果页已被修改而变脏，则踢出它就必须写回磁盘，这很昂贵。因此一些系统更倾向于踢出干净页。
预取：操作系统会猜测一个页面即将被使用，从而提前载入。
聚集（分组）写入：操作系统收集一些待完成写入，并以更高效的写入方式写入硬盘（硬盘执行单次大的写操作，比许多小的写操作更有效）