第二部分虚拟化的整理。
进程的地址空间
代码，数据，堆栈（它们都可以用指针访问），动态链接库，运行时分配的内存。
分为若干“段”，每一段是可访问（R/W/EXE）的内存。pmap+进程号查看进程地址空间（pmap()是基于procfs中的maps实现的：cat /proc/[pid]/maps）。
相关系统调用：
mmap()：文件→内存（创建）；munmap()：抹去；mprotect()：修改权限
gcc a.c是动态链接；gcc -static a.c -o a.out是静态链接（慢&大）。(gdb) starti, 执行第一条指令时进程的地址空间并没有libc，只有加载器的代码。(gdb) info inferiors(gdb) !+instruction
进程地址空间高位有三个“宝藏“：[vvar], [vdso], [vsyscall]。(man 7 vdso)
让内核和进程共享数据(内核可写，进程只读)
vvar: 内核和进程共享的数据
vdso: 系统调用代码实现
vsyscall: 普通系统调用的封装
只用int指令系统调用慢。SYSCALL —— Fast System Call。(man 2 syscall)
系统调用发生时，进程要和操作系统同步一次?（syscall/共享内存?）
游戏外挂（修改进程地址空间）
实现虚拟存储：分页机制
L0 amgame: 向显存的地址写入数据
需要一个函数f: [0,M)→[0,M)，把VA翻译成PA；f由操作系统控制。
以页面为单位映射(页面之间任意映射，页面内offset确定: VA+100→PA+100)！
e.g. 地址空间32GB，x86页面4KiB。本质上要将220个数字映射到另外220个数字。①Hash table：reversed page table。②使用radix tree(x86)。
x86用的三层的radix tree(PD+PT+Page)，32bit = 10bit+10bit(4KB/sizeof(int)=1KB)+12bit(offset)。
x86-64: PML4(PDPT+PD+PT+Page)
mmap()实际上只是更新了操作系统内部”一张表“，并没有真正给进程分配页面，直到进程执行遇到缺页（此时执行流进入OS，OS查”表“发现已经”映射“过了）。缺页时OS会得到缺页地址(%cr2)
访问合法，分配一页（匿名内存，直接返回；文件，read把文件读到内存）
非法，发送信号（SIGSEGV）
Memory-Mapping File一致性问题，msync(2)
链接与加载
大文件→小文件；C语言眼里只有内存&指针，不同的“解读”即各种类型。
Static
编译后不能直接执行：指令中rip相对寻址的offset为00 00 00 00，链接时才把符号的位置填入offset。使用readelf，发现都是把符号的地址减4填入offset？实际上相对rip寻址时movl off(%rip),%edi，由于rip指向的其实是该指令8b 3d 00 00 00 00 00末尾（也即下条指令的头部），所以off实际上是指令末尾到符号头部的偏移，所以将符号地址减4，符号地址就被填入正确位置（3d后面）。
__attribute__((constructors)), __attribute__((destructors))
就是解析ELF头，把Program Header mmap()到内存。静态链接的程序从ELF Entry执行。
Dynamic
每个程序都static link，浪费空间。最好整个OS只有一个libc副本(libc.so)。(gdb)starti，执行的指令并不是程序第一条指令，而是ld-…….so
实现动态加载：
纯粹加载代码？编译成PIC（引用代码/跳转全部是PC相对寻址），直接把代码mmap()到进程地址空间就行了
除了代码，还要有附带的数据？（还是PC相对寻址：数据相对于对应的代码offset确定）
允许访问其他动态链接库导出的符号(code/data)？重填？(还是相当于静态链接)。为动态符号创建表，查表！编译成call *table[foo]。于是只有这张表要拷贝
Ques: main要调用libc中的printf；printf要调用libfoo中的foo
1. libld加载libfoo
2. libld加载libc：libc对foo的调用被编译成call *libc.tab[FOO]；libld调用_dl_runtime_resolver解析符号，装入libc.tab[FOO]
3.libld完成main的初始化：a.out对printf的调用被编译成call *a.out.tab[PRINTF]; libld解析printf地址，填入a.out.tab[PRINTF]
ELF动态链接与加载
GOT(global offset table)：库函数有，可执行文件也有。（GOT[0]：.dynamic节地址；GOT[1]：link map；GOT[2]：_dl_runtime_resolver地址；……）
But 会有许多符号，实际只可能引用很少的。
Lazy Symbol Resolution: call printf@plt, jmp *a.out.GOT[PRINTF]。第一次查表，会把表中printf@plt的地址替换成真实地址，以后就可以直接jmp到reslove成功的printf地址
虚拟化：处理器调度
下次中断后应该让哪个进程在处理器上运行？
处理器调度
n个任务，分别要t1,……,tn时间完成。任务一旦开始就要结束，按什么顺序执行最好？
Shortest Job First(SJF)，最小化平均完成时间（等待时间↓）。
任务可在任何时间到达？cost = 完成时间-到达时间(上一情况下所有Jobs的到达时间相同)，need to minimize average cost.
Shortest Time-to-Completion First(STCF)：减少等待任务！让剩余执行时间最少的任务执行→新来的short job会抢占当前job！
以上其实是历史遗留问题(批处理时代)
单处理器分时调度（1）
中断(机制)：进程不在独占处理器直到完成，OS代码可定时强制执行
处理器调度(策略)：系统中有很多进程等待执行，OS代码执行调度策略选择一个process；中断返回机制运行Context
基本假设：进程是while(1) do_sth，执行时使用CPU，等待I/O返回时不使用CPU；处理器以固定频率被中断；随时可能有new process被创建或old process退出
Round-Robin:
当前Ti，中断后试图切换到下一个T(i+1)mod n；如果下一个正在等待I/O返回，继续再下一个。（所有thread都不要CPU，调用idle线程执行(likeos->run)）。
中断之间的进程执行称为“时间片”
引入优先级 UNIX niceness
-20(最坏)~19(最好)：越nice，越被不nice的人抢占；nice相差10(1)，CPU获得相差约10(1.25)倍./a.out &后台运行a.outps查看进程号renice -n val pid修改nice值top指令查看CPU使用情况taskset -cp cpuid pid：将进程绑定到某个CPU上
多级反馈调度(MLFQ)
假设有交互进程(vi, vscode……)&计算进程(gcc, ld……)，后者在处理器空闲时才执行，通过观测进程行为(时间片全部用于计算?)确定是哪一种
设计多个Round-Robin队列(每个队列对应一个优先级)
Complete Fair Scheduling(CFS)：
精确记录每个进程运行时间，补偿时间最短的进程
fork()子进程会继承父进程的vruntime
睡眠唤醒的进程获得系统最小的vruntime(防止唤醒后长时占用CPU)
通过调整时钟实现优先级(nice的进程始终跑得快，所以相同的物理时间下其vruntime就较大)
用红黑树(有序集合!)维护vruntime，每个进程指向一个node。
整数溢出问题？用time_delta判断大小。
单处理器分时调度（2）
线程不是while(1)的循环；线程/进程不是纯粹的计算或（长时间）I/O：等待mutex_lock, 信号量，非常短暂的I/O。
producer(‘(‘)→consumer(‘)’)→while(1)，Round-Robin会严重不公平(while(1)几乎占据了所有时间)！
优先级翻转：高优先级进程和低优先级进程持有同一把mutex_lock→低优先级进程进程执行完一个时间片后仍未unlock→高优先级进程等待互斥锁，无法执行→中等优先级进程进程几乎占据整个CPU(直到其vruntime达到低优先级进程vruntime才会停止)ps ax| grep watchdog：最高优先级进程，检查系统
解决： 优先级继承/优先级提升；持有mutex的进程/线程会继承block在该mutex上的最高优先级（即上例中低优先级进程会继续执行直到unlock）；但对于条件变量不总是work┭┮﹏┭┮；对优先级翻转做预警！
多处理器调度
每隔一段时间，负载低的CPU可以从负载高的CPU中偷一些线程。But 策略？？
实际情况1：多用户，多任务，用户的公平性很难保证→Linux Control Groups(man 7 cgroups)
实际情况2：BIG.LITTLE/能耗，处理器的计算能力不同→均分workloads会让小核任务饥饿
实际情况3：Non-Uniform Memory Access，“共享内存”假象！(CPU缓存互联(慢)，所以会有“分配1/2的处理器资源，反而加速”)