【操作系统笔记】南京大学jyy老师

系列综述：
💞目的：本系列是个人整理为了

操作系统学习

，整理期间苛求每个知识点，平衡理解简易度与深入程度。
🥰来源：材料主要源于

南京大学操作系统jyy老师

课程进行的，每个知识点的修正和深入主要参考各平台大佬的文章，其中也可能含有少量的个人实验自证。
🤭结语：如果有帮到你的地方，就点个赞和关注一下呗，谢谢🎈🎄🌷！！！
🎉相关网址：jyy老师的博客

文章目录

操作系统概述

生存指南

1. linux设计哲学 - Keep it simple, stupid- Everything is a file- All in terimal
2. 学习操作系统的目的 - 你体内的编程力量没有完全觉醒：看到一切东西都可以写出来- 酷的事情和学的数学理论之间的gap连接起来
3. 操作系统定义 - 充分利用软硬件资源，为系统提高服务的程序
4. 两个操作系统的顶会 - OSDI/SOSP
5. 进程地址隔离的原因 - 避免进程指针访问错误，从而导致其他进程程序错误
6. 多道批处理系统 - 进程与OSKernal交替运行，其他进程负责任务处理，kernel负责切换和资源调度
7. 程序的运行就是一个状态机 - 内存和寄存器存储状态- cpu运行的指令改变内存的状态（pc指向的指令的执行）

什么是程序和编译器

1. 状态机和数字电路 - 状态：内存M+寄存器R- 初始状态：RESET- 迁移：组合逻辑电路计算寄存器下一周期的值
2. 数字逻辑电路的步骤 - 定义并初始化所有寄存器- 在一个时钟周期到来时，运行组合逻辑电路- 将结果更新到寄存器中
3. 管道思想 - 将一个程序的输出作为下一个程序的输入
4. 程序本质是一个状态机 - 程序运行在计算机上- 计算机本质是一个数字系统- 数字系统本质是一个状态机
5. C语言的程序也是状态机 - 堆栈表示状态- 语句表示状态迁移的规则- eg：单步调试就是状态机中状态的转换，堆栈存储的是当前的状态
6. 函数调用的状态机思路 - 状态：调用函数会创建对应的栈帧- 执行：函数中指令的执行导致栈帧状态的转换- 函数调用的返回：将该函数的栈帧删除
7. 状态机之间的转换需要通过 指令，指令有两种 - 计算- syscall
8. 状态机可以观测
9. 真正的计算机从业者应该具有读官方手册的能力
10. 编译器其实就是对于状态机的生成和优化externint g;// 全局变量，其他程序可能使用，不可优化voidfoo(int x){ g++;asmvolatile("nop"::"r"(x));// __sync_synchronize();// 这个barrier将不可优化 g++;}// 即使两个g++中间代码不可优化，但使用-O2仍然可以优化
11. 操作系统管理了所有的软硬件资源，具有最高权限
12. 计算机系统不存在玄学，一切都建立在确定的机制上
13. 通过工具去观测程序运行中状态机的状态
14. 程序运行 - 另一个进程执行execve设置初始状态- 状态机执行计算指令和syscall- _exit(exit_group)退出
15. 程序 = 状态机 - 源代码视角：状态转移 = 执行语句- 二进制视角：状态转移 = 执行指令

多处理器编程

1. 并发的基本单位：线程 - 从状态机视角：并发的线程实际是同一个基本状态延申出来的，不同线程间执行的状态流是独立的，通过共享内存进行通信。- 并发程序执行的每一步都是不确定的
2. join含义 - 如果一个进程有三个线程t1、t2、t3，那么当t1.join()时，意味着t1状态转换的指令是while(t2没结束&&t3没结束);，即选择t1执行会进入状态机的死循环，从而等待t2和t3执行完成。
3. 线程是共享内存空间的，即没有逻辑地址空间的独立性，但是有线程栈帧的独立性
4. 在多处理器体系下，指令无法独占处理器执行，即多线程的状态机中的初始状态下下一个状态可能是多分支的
5. 状态机模型 - 单线程- 多线程
6. 线程安全：能够保证多线程的原子性
7. 并发问题的队列解决 - 99%的并发问题可以使用队列这个数据结构进行处理- 将大问题切分成小问题- worker thread去锁保护队列中取任务- 除去不可并行部分，可并行部分可以获得线性的加速
8. 多处理器编程需要放弃对于单线程状态机的旧理解 - 放弃原子性：并发导致了状态机中状态的转换可能出现分支- 放弃顺序性：编译器对于内存访问“evenual consistent”的处理导致共享内存作为线程同步工具的失效- 放弃可见性：现代处理器对于指令的乱序发射的优化，导致程序语义与指令语义的不同
9. 编译器的优化是按照单线程的状态机进行代码的优化 - 结果一致性：无论中间状态的转换，只要状态机最后的状态是一致的即可去除中间状态转换
10. 避免优化：保持C和汇编语义的一致性 - __sync_synchronize();- asm volatile("":::"memory");// 强制写回内存
11. 现代处理器也是一个动态编译器
12. 在处理器中执行的指令是一个DAG有向无环图，这个图是通过逻辑相关性确定的，每次尽可能的多发射指令进行处理
13. 线程内存模型 - x86架构：每个线程有自己的缓存，结果一致性体现在共享内存中 - risc-v架构：每个线程都有自己的内存副本，是一种分布式的架构，不需要保证内存一致性
14. 现代的编译器（处理器的一部分）：是一个动态的数据流分析器

理解并发程序执行

1. 并发程序 = 多个执行流并且共享内存的状态机器
2. 通过状态机视角，去理解程序的执行。包括并发程序。
3. 互斥：两个或多个线程不能同时执行一段代码
4. 并发问题锁int locked = UNLOCK;voidthreadx(){while(locked != UNLOCK);// 有锁则自旋 locked = LOCK;// 临界区 locked = UNLOCK;}- 状态机中包含两个线程的栈帧和pc（程序计数器，即下一条指令地址），以及全局锁变量（共享变量）- 错误并发的状态机模型 - 第一个状态：线程1和线程2都建立了threadx的函数栈帧，pc均指向while指令处- 执行：线程1执行，读locked为UNLOCK，执行完while并pc指向下一条指令- 第二个状态：线程1pc为locked=LOCK指令执行处。线程2pc内容为while指令处- 执行：线程2执行，读locked为UNLOCK，执行完while并pc指向下一条指令- 第二个状态：线程1和线程2的pc均为locked=LOCK指令执行处- 执行：无论线程1或线程2执行，在之后切换线程执行时均会导致两个线程都在临界区中。
5. Pertenson算法（两个线程看似谦让，实则自私） - 任何一个线程想进入临界区，先更改自己的flag，然后将共享变量更改为对方- 查看对方的flag和共享变量，如果对方的置flag为true并且门上名字不是自己则等待，否则进入- 当离开临界区时，置自己的flag为flase
6. 把线程想象成自己和他人，把物理世界的客观物体（旗子…）想象成共享内存。
7. 线程读取（看到）的共享内存状态是一个历史history，而共享内存写入的东西是一个时间点（瞬间完成的）
8. liveness：任何状态出发，总是能在有限步内到达同一个确定的状态
9. 任何程序可以建立状态机转换模型，通过暴力枚举状态机的方式进行程序正确性的证明。
10. 每一个程序的正确性验证，都可以自己写一个model checker程序，将状态空间进行遍历检查
11. 抽象的角度看一个状态机，它就是一个图。通过图论的方式，将所有的业务逻辑编写成图的形式。
12. 系统需要工具进行人机的交互解释

并发控制

1. lock函数返回含义是调用线程获取了独占某个资源的锁
2. 独立瞬时的读写操作导致写前和读后对于状态的未知性 - 读：看一眼就把眼睛闭上，即读只能读到一瞬间的状态，读的是一个history- 写：闭着眼睛改变，即写入只能覆盖，无法知道写入时的状态
3. 问题无法解决就解决问题的假设（提出问题的人）
4. 只使用一个原子变量实现互斥 - 实现读写的瞬间一致性：一个线程写共享变量时，先读后写，且读写瞬间共享变量屏蔽其他线程- 汇编实现：atomic exchange（load+store）intxchg(volatileint*addr,int newval){int result;asmvolatile("lock xchg %0, %1"::"=r"(val),"+m"(*addr):"m"(*ptr),"0"(val));return result;}// 自旋锁int locked =0;voidlock(){while(xchg(&locked,1));}voidunlock(){xchg(&locked,0);}
5. 代码是两个 层面的东西，一个层面是人所理解的业务逻辑，另一个是机器层面。真正理解代码需要对于两个层面都深入了解
6. 原子指令模型 - 之前的所有store写操作都会写入到内存中- 所有的内存访问都不能越过原子指令
7. 原子指令的实现 - 通过一个bit表示总线资源的锁，访问内存需要先获得总线的锁
8. x86中的L1缓存是连接在一起的，为了实现缓存的一致性
9. 常见原子操作的本质 - load- exec(处理器的寄存器的运算)- store
10. risc-v的原子操作：先运算出结果放到缓存中，当需要同步到内存时，先打标记，再判断标记是否存在，存在时再写入内存，然后删除标记// CAS锁（compare and swap）的实现机制intcas(int addr,int cmp_val,int new_val){int old_val =*addr;// 读取标记if(old_val == cmp_val){// 标记等于自己的之前打的，则写入*addr = new_val;return0;}else{return1;}}
11. 自旋锁的缺陷 - lock和unlock执行时是原子的，指令无法乱序- 除了进入临界区的线程，处理器的上的其他线程都在空转- 时间片轮转：获得自旋锁的线程在就绪队列中排队，其他线程获得CPU会空转，实现了100%的资源浪费
12. 性能的评价维度 - 空间复杂度- 时间复杂度- scalability伸缩性：多处理器性能的度量，难以严谨的计算（CPU功耗受温度影响，系统中的其他进程）
13. 自旋锁的特点 - 快的时候很快：锁的争抢比较少，只需要一条原子指令的开销即可获得锁- 慢的时候很慢：多个线程争抢时，只有一个线程获得锁，其他的均会自旋等待。如果持有自旋锁的线程切换或睡眠，会发生100%的cpu资源浪费（一核有难，八核围观）
14. 解决自旋锁慢的问题，C语言只能做到程序的计算，无法掌控资源的切换。资源的切换必须通过系统调用，所以自旋锁通常放到内核并发数据结构中，作为一个系统调用给用户程序使用 - syscall(SYSCALL_lock, &lock);：尝试获取lock，如果失败就立即切换到其他线程- syscall(SYSCALL_unlock, &lock);：释放lock，如果有等待的线程则直接唤醒
15. 吸优去慢（工程上的优化，通常只优化常见的80%或者最短的木桶板） - Fast path：一条原子指令，上锁成功立即返回- Slow path：上锁失败，立即执行系统调用，使进程睡眠，从而减少cpu资源的占用
16. POSIX线程锁的实现 - 待定
17. 有拥堵时，进内核

内联汇编

1. 内联汇编 - %number：是对于输出对象和输入对象的顺序编号asm[volatile](// volatile向gcc声明该汇编代码不需要进行优化（可选）"assembler template"// 汇编模板代码[: output operands ]// 输出对象（可选）[: input operands ]// 输入对象，即按序为汇编指令参数中的%num（可选）[: list of clobbered registers ]// 告诉编译器该寄存器可能会被修改，要在本次内联汇编使用);// 示例：将a赋值给bint a=10, b;asm("movl %1,%%eax;/* NOTICE: 下面会说明此处用%%eax引用寄存器eax的原因 movl %%eax, %0;" :"=r"(b) // 输出参数 %0 :"r"(a) // 输入参数 %1 :"%eax" // 可能用的寄存器 );

同步

1. 定义：两个或两个以上随事件变化的量，在变化过程中保持一定的相对关系
2. 同步电路：所有触发器在边沿同时触发
3. 线程同步：在某个时间点共同达到互相已知的状态，条件不满足其中一方要等待。
4. 99%的实际并发问题都可以使用生产者-消费者进行解决 - 生产者：向队列中添加资源（任务）- 消费者：从队列中取出资源（任务）- 其中对于共享资源的使用需要进行加锁和取消锁
5. 对自己的程序进行压力测试，并编写压力测试的检查程序，保证自己代码的正确性
6. 将互斥锁的自旋变成睡眠，直到某个条件变量被满足时唤醒某些线程 - wait(cv)：条件变量不满足时，直接sleep()- signal(cv)：唤醒一个或多个等待的线程// 万能的条件变量并发模板：可以将任何可并行算法编程并行的mutex_lock(&mutex);while(!condition){wait(&cv,&mutex);}assert(condition);// **********// 互斥锁保证了在此期间条件变量condition总是成立// ***********mutex_unlock(&mutex);// 其他线程可能满足时broadcast(&cv);
7. 多使用assert进行错误提示，可以进行bug定位

哲学家就餐问题

1. 如果所有哲学家都举起同一边的叉子，则所有的哲学家都会进行等待，即发生了死锁
2. 万能并发模板解决哲学家吃饭问题（所有人都均等的使用叉子并不好，没有一个并发的数据结构）mutex_lock(&mutex);while(!(avail[lhs]&& avail[rhs])){// 看左右手的叉子是否都在wait(&cv,&mutex);// 有一个叉子不在，则睡眠}// 将左右手叉子都拿起来avail[lhc]= avail[rhs]=false;mutex_unlock(&mutex);// 释放信号量mutex_lock(&mutex);avail[lhs]=avail[rhs]=true;// 还叉子broadcast(&cv);// 唤醒其他进程mutex_unlock(&mutex);
3. 让一个人集中管理叉子，放弃信号量 - 非集中式的管理共享资源，会导致分布式的自同步，每个线程都想试一下

// master/follower 生产者/消费者模型voidTphilosopher(int id){// 哲学家线程send_request(id, EAT);// 给服务员的队列发一个消息，请求吃P(allowed[id]);// 等待服务员许可philosopher_eat();// 就餐send_request(id, DONE);// 给服务员的队列发一个消息，吃完了}// 集中调度器：可以维护公平性（让长时间不占叉子的线程，下次分配时等一等）voidTwaiter(){// 服务员线程while(1){(id, status)=receive_request();if(status == EAT){...}if(status == NONE){...}}}

1. 在不了解系统的性能瓶颈之前，不要做任何的优化

真实世界的并发编程

高性能计算

1. 计算机任务如何分解 - 计算图要更容易并行化（使用拓扑排序，分解有向无环图）- 生产者-消费者解决一切
2. 问题划分 - 模拟宏观世界：使用有限元模型- 模拟微观世界：使用粒子模型
3. 数据中心：多副本下高可靠、低延迟数据的访问 - Consistency：数据要保持一致性- Availability：服务时刻保持可用- Partition tolerance：容忍机器离线
4. 每个线程做的事情：读取——处理——写回
5. 一个线程一次只能运行一个协程，协程不受操作系统调度。但是每个线程会占用可观的操作系统资源。
6. 解决协程block问题：一个协程等待资源，其他协程也一起等待 - Go同时实现多处理器并行和轻量级并发——goroutine（线程和协程的混合体）- 执行到blockingAPI时（例如read、sleep）。 - 成功：立即返回- 失败：立即yield到另一个需要cpu的goroutine- 根本思想：当协程要做一件阻塞耗时的事情时，先发出资源请求的系统调用然后阻塞自己，yeild到另一个需要cpu资源的协程执行，当系统资源准备完成时，阻塞协程重新进入就绪队列 。这个过程中不会发生线程切换的堆栈资源开销，几乎每时每刻都有cpu和协程在运行，实现了近100%的cpu资源利用
7. 有原子操作可以实现条件变量，有条件变量可以实现任何的并发算法
8. 越底层，越自由，越容易出错，越高效。但是大多数程序稳定性要求要高于性能要求，所以可以使用通用的安全的接口去实现容易发生不安全的行为 - 既然生产者-消费者可以解决绝大部分的并发问题，那提供一个安全高效的API不就可以了？

// go实现生产者和消费者模型
package main
import"fmt"// 并发的共享队列
var stream =make(chan int,10)const n =4// 生产者
func produce(){for i :=0;; i++{
    fmt.Println("produce", i)
    stream <- i// 放一个到共享队列中}}// 消费者
func consume(){for{
    x :=<- stream
    fmt.Println("consume", x)}}

func main(){for i :=0; i < n; i++{
    go produce()}consume()}

1. web前端的并发模型 - 异步事件模型 - 所有事件通过一个线程执行，每个事件执行都是原子的- 全局的事件队列按序返回，其中耗时的API调用会立即返回，满足条件时向队列中增加一个事件- 缺点：多层嵌套，可维护性差。 可以通过流程图进行事件的化重新划分

并发bug和应对

1. 始终假设自己的代码时错误的
2. 需求 = 抽象代码 + 规约(面试加分) - assert断言机制，将代码在运行后仍肯定存在的属性进行内在规约。 - assert(对象之间的关系)，这里的对象通常是局部变量或者全局变量- 异常处理机制
3. 产生死锁的必要条件（必须同时成立） - 互斥：一个资源每次只能被一个进程使用- 请求与保持：一个进程请求资源阻塞时，不是放已获得的资源- 不剥夺：进程已获得的资源不能强行剥夺- 循环等待：若干进程之间形成肉味详解的循环等待资源关系
4. 解决死锁的方法 - AA型死锁：使用防御性编程，if(holding(lk)) painc();- ABBA型死锁：线程按照固定顺序获得锁，消除循环等待条件。给锁编号并检查上锁和解锁的日志
5. 死锁比较容易判断的并发问题，因为死锁会导致系统无发展
6. 数据竞争：不同的线程同时访问同一段内存，且至少有一个是写
7. 并发程序的书写 - 无锁的并发程序很难写对- 用互斥锁保护好共享数据可以实现一切并发程序
8. 并发程序 - 互斥锁（lock/unlock）：保证原子性 - 如果忘记上锁，则违反原子性（一次做完）导致并发出错。例如t1-t2-t3（ABA）- 条件变量（wzait/signal）：保证同步 - 如果忘记同步，则会导致违反执行顺序- 97%的非死锁并发bug都是互斥锁或条件变量
9. 当一个十倍程序员的前提是程序中bug极少，需要始终假设自己代码是错误的
10. 要善于使用动态程序检测工具，例如linux内核中的动态分析软件sanitizers （可以检查数据竞争和非法访问等）
11. 内存越界检查 - Canary机制：牺牲堆栈头尾的一些数据单元作为特殊标记，隔一段时间就检查这些标记，如果被更改，则报错 - msvc中，为初始化的栈为0xcccc（GB2312编码为烫烫）、为初始化的栈为0xcdcd（GB2312编码为屯屯）

操作系统的状态机模型

写一个操作系统

1. 操作系统是程序，程序是状态机，状态机是状态+指令/syscall形成状态流
2. 计算机硬件也是一个状态机，而软硬件之间的桥梁是软硬件工程师的约定（手册）
3. 计算机的启动(legacy BIOS方式)- 开机，发出一个RESET信号，RESET会初始化计算机硬件的开始状态 - pc初始化指向为内存映射的ROM（0xffff0,跳转到固件的jmp指令），ROM存储了厂商提供的固件- 固件：厂商提供的代码，可以将用户数据加载到内存上，如存储介质上的loader加载器- MBR（启动磁盘的第一个512字节的扇区，末尾是55aa），cpu将mbr中启动程序加载到内存的0x7c00开始处
4. 如何理解一个程序，理解程序的状态机变化，即使每执行一条指令状态机的变化

状态机模型的应用

用状态机模型理解物理世界

1. 状态+指令/syscall = 确定的下一个状态
2. 时间旅行：从一个状态回溯到之前的状态，但是之前的状态会进行分支一个拷贝，从而出现一个平行宇宙
3. strace工具可以将程序执行的的每一条指令和syscall按序列出
4. gdb每次停下来都是停止在一个状态上，可以使用s走一条语句，或者使用si走一条指令，查看下一个状态
5. record full 打开gdb的记录模式，使用rsi回溯上一条指令。但是难以回溯syscall执行，可以使用非确定指令的结果记录的方式进行回溯这种执行
6. 初始状态->确定性指令->状态1->非确定性指令->状态2->… - 确定性指令可以通过逆指令执行，实现状态的回溯- 非确定性指令可以通过结果状态的快照，实现状态的回溯
7. 性能优化反问 - 现在性能够用吗- 这个需要进行性能优化吗- 性能优化的收益大吗
8. gdb会在指令间打断点，即入侵程序的指令来形成执行的历史。如何减少程序入侵 - 程序在中断后，内核可以看到程序中断前的状态（profile软件）

操作系统上的进程

1. 操作系统的内核启动：CPUReset->Firmware（ROM固件）->Boot loader ->启动内核kernel start()->创建第一个进程init
2. 操作系统为程序创建的API - 进程（状态机）管理：状态机的创建fork、改变execve、退出exit- 存储（地址空间）管理：mmap虚拟地址空间- 文件（数据对象）管理 - 文件访问管理：open、read、write、close- 目录管理：mkdir、link、unlink
3. 程序就是状态机，所以操作系统在完成启动后，会通过init创建操作系统的第一个进程（也是一个状态机）
4. fork是状态机整体的复制——拷贝父进程状态，通过fork创建的状态与父进程的状态完成一样（内存的字节都一样，但是地址不同），除了fork的返回值——进程的标识编号。 - fork完成后，即存储了多个进程，状态机变成了并发状态机模型
5. 本质：操作系统是状态机的管理者，虚拟化就是多个状态机复用一个物理机
6. fork bombfork(){ fork | fork &// fork管道给fork}; fork
7. 状态机包含了所有进程和计算机软硬件资源的状态。而每个状态机由于指令/syscall执行导致出现新的状态机，这些状态机形成了执行流
8. fork 无情的复制机器：会将进程所有的内存和寄存器复制一份（包括库函数的内部状态）
9. 标准输出stdout - 输出对象是终端，则为line buffer，以’\n’作为缓冲区一次输出标志- 输出对象是pipe/file，则为full buffer， 写满4096B才会将输出一次
10. 程序是状态机，正在执行的程序是正在运行的状态机，fork是创建状态机的副本
11. execve(环境变量)：将状态机重置成某个状态，环境变量是重置状态机的参数
12. 环境变量：应用程序的执行环境，在linux下可以使用env命令查看 - PATH：可执行文件的搜索路径- PWD：当前路径- HOME：home目录- DISPLAY：图形输出- PS1：shell的提示符
13. 所有的进程的创建都需要fork，所有的进程启动都需要一直reset即execve系统调用进行设置环境
14. _exit(int status) - 销毁当前状态机，并允许有一个返回值- 子进程终止会通知父进程
15. exit的几种写法 - exit(0)：会调用atexit，终止当前进程- syscall(SYS_exit, 0) - 执行exit系统调用终止当前线程- 不会调用atexit- _exit(0)：执行exit_group系统调用终止整个进程

系统调用和shell

1. 计算机系统的构建 - 硬件NEMU：从CPUReset开始执行指令- Firmware固件：加载操作系统- 操作系统：状态机的管理者 - 初始化第一个进程- 执行系统调用
2. shell是操作系统内核外面的中间壳，是人机交互的中间层。可以将用户指令翻译称为系统调用的语言
3. 使用man sh读以下shell的手册
4. shell中的管道实质是将命令翻译成一颗语法树，然后再将将叶子节点翻译成系统调用 - 作用：父子进程可以共享管道，因为是一个完整的复制关系
5. 好的shell，如fish（自动补全的shell）、zsh。加入bert模型
6. 任何人机交互的程序都应该使用大语言模型进行重构
7. linux 的工具 - zsh：兼容bash的shell- tmux：shell分屏- strace：追踪系统调用的分析工具
8. 启动一个shell - 打开一个session：内部是很多个进程组process group，fork前后的进程都同属于一个进程- controlling terminal：会建立一张进程关系表，即一个shell- 如果一个信号被terminal产生，则会相应的发送给所有的进程组
9. 看完linux的sh手册man sh
10. 一个功能完整的shell使用的操作系统对象和API - 控制结构 - session- process group- controlling terminal- 文件描述符 - open- close- pipe- dup- read- write- 状态机管理 - fork- execve- exit- wait- signal- kill- setpgid- getpgid

什么是可执行文件

1. 可执行文件的使用通过系统调用execve实现， execve(可执行文件，...)- 前提：execve用于状态机的重置，重置的数据来源于可执行文件- 本质：可执行文件是一个可迁移的数据结构，描述了状态机（寄存器R+内存M）的初始状态，elf加载器将execve中第一个参数指向的文件Reset状态机- 寄存器： - 大部分由ABI决定，操作系统负责设置，如初始的PC- 地址空间 - 二进制文件+ABI共同决定的，如argc和argv的存储
2. 文件可执行的前提 - 具有可执行权限x- 加载器能识别的可执行文件
3. linux的执行方式 - 二进制文件a.out（不赞成）- ELF(Executable Linkable Format)- She-bang
4. GNU binutils查看、生成、修改二进制文件的工具 - 生成可执行文件 - ld(linker)、as(assembler)- ar、ranlib- 分析可执行文件 - objcopy/objdump/readelf- addr2line/size/nm- 可执行文件的运行时状态 - gdb
5. 调试信息 - 将一个assembly(机器)状态映射到C世界状态的函数 - 通过一个Turing Complete的指令集DW_OP_XXX- 可以执行"任意计算"将当前计算状态映射回C- 不完美 - 对现代语言支持有限- 编译器也无法保证调试信息
6. 状态机器的编译 - C的语句状态机通过语句进行转移到下一个C语句状态机- 指令状态机通过指令/syscall进行转移到下一个指令状态机- 汇编器将指令状态机翻译成.o文件（描述指令状态机），链接器将所有的.o文件约束成.out文件。（约束如在一个文件中只存在的声明部分，而在另一个文件中存在的定义部分进行事后链接）- gcc将语句状态机转化成指令状态机，而gdb就是将指令状态机映射回C状态机。汇编程序assembly将指令状态机转换成二进制的数据结构和约束条件
7. 将要链接的未知符号的地址S+A-P=S-(P-A) - P-A就是现在的PC值，就是跳转的目标地址减去现在的PC
8. 面向问题，而不是面向细节

动态链接和加载

1. 可执行文件：描述状态机初始状态的数据结构 - 不同于内存的数据结构，指针都被偏移量所代替- elf定义：/usr/include/elf.h
2. 文件加载器file loader - 解析数据结构 + 复制到内存 + 跳转- 创建进程运行时的初始状态
3. boot loader的作用 - 引导扇区内容：512B MBR + 1024B main argc + kernel（elf）
4. 动态链接的原因：如果每个可执行文件都有所有库函数的拷贝，会极大的浪费内存空间 - 动态链接库版本无关性：调用者遵守基本的约定，与库函数的版本无关- 原因：在程序运行时，找到编译好的库函数进行动态链接，即运行时才进行链接
5. 动态链接库的功能 - load(lib)一个动态链接库- import(sym)一个符号- export(sym)一个符号- dsym(sym)引用一个外部符号
6. 动态链接本质就是查表，先在符号表中的符号地址填入0，动态链接符号后，根据符号表中的符号地址进行间接跳转
7. elf中字符串：将所有的字符串常量存放在常量池，统一的通过“指针”进行访问
8. 符号表GOT和PLT：统一静态与动态链接
9. 符号表GOT（global offset Table） - 作用 ：是Linux ELF文件中用于定位全局变量和函数的一个表
10. PLT（Procedure Linkage Table，过程链接表） - 作用：Linux ELF文件中用于延迟绑定的表，即函数第一次被调用的时候才进行动态绑定- 优点：延迟绑定只绑定被调用的函数，没用过就不进行绑定
11. 如果系统开启了内存布局随机化ASLR，程序每次运行动态链接库的加载位置都是随机的，就很难通过调试工具直接确定函数的地址

Xv6 代码导读

1. UNIX - v6的现代版克隆： - 基本的工具集和shell- 命令执行、管道、重定向- 支持多处理器- 支持RISC-V

2. xv6中基本的系统调用
   System callDescriptionint fork()创建一个进程，并返回子进程的PIDint exit(int status)终止当前进程，状态报告为等待int wait(int *status)等待子进程退出，退出状态为status，并且返回子进程PIDint kill(int pid)终止进程PID，返回0或-1（错误）int getpid()返回当前进程的PIDint sleep(int n)暂停n个时钟周期int exec(char *file, char *argv[])将文件加载到内存执行并用argv初始化环境，只有错误才返回int open(char *file, int flags)打开一个文件，标志为读/写，返回该文件描述符int write(int fd, char *buf, int n)从bufffer到文件描述符指定的文件中写入n个字符，并返回nint read(int fd, char *buf, int n)从文件描述符指定的文件中读取n个字符写入到bufffer，返回读入的字节数，如果在文件末尾则返回0int close(int fd)释放打开文件的文件描述符int dup(int fd)dup函数创建一个新的文件描述符，该新文件描述符和原文件描述符指向相同的文件、管道或者网络连接int pipe(int p[])创建一个管道，在p[0]和p[1]中放置读/写文件描述符。int chdir(char *dir)改变当前文件目录int mkdir(char *dir)创建一个新的文件目录int mknod(char *file, struct stat *st)创建一个设备文件int fstat(int fd, struct stat *st)将打开文件fd的信息放入st中int stat(char *file, struct stat *st)将有关命名文件fd的信息放入st中int link(char *file1, char *file2)为文件file1创建另一个名字file2（软连接）int unlink(char *file)删除一个文件

3. 读xv6的手册，可以作为操作系统的实践教学

4. 工具比什么都重要

5. vscode的执行需要配置命令脚本，也可以在terimal中输入

6. gdb的源代码对照的按行调试 - set pegination off- layout src

7. gdb tui

Xv6 上下文切换

1. 为什么死循环不能使计算机卡死 - 硬件会发生中断切换到内核态执行- 内核态可以切换到另一个进程执行
2. 操作系统的定义 - 每个程序加载到内存后成为进程，进程的执行是一种状态机的改变- 操作系统是状态机的集合- 单cpu上的操作系统具有多个进程，可以通过时分复用进行处理
3. 协程是一种函数对象，可以设置锚点做暂停，然后再该锚点恢复继续运行 - 同步：因为协程本质是函数，调用协程后原来的地方就会被阻塞，协程处理完了才返回结果，这是天然同步的- 并发：遇到阻塞条件时候，把cpu让给别的协程，等条件满足了再通过中断可恢复的特性再继续运行，就实现了并发
4. 通过协程可以在用户态下，实现一个操作系统在用户态的中断。因为协程可以实现用户态下的状态机转换
5. 进程对于持有的内核区代码是不可见的，只能通过系统调用与操作系统进行交互。
6. 文件描述符是进程状态的一部分
7. 中断和系统调用实际将进程的状态进行保存，这是通过寄存器和内存的虚拟化实现的
8. 操作系统的上下文管理和切换 - 系统调用：操作系统开始真正处理系统调用/中断时- 状态机封存：所有进程的状态机都可以封装到操作系统中- 状态机器处理：所有进程的状态机使用数据结构task_struct数组进行管理，操作系统可以通过数据结构访问每一个进程的状态机，并修改- 调度并恢复：操作系统可以通过schedule将一个进程的状态机（寄存器和内存）恢复到CPU
9. 操作系统是状态机的管理者 - 再xv6中$stap控制了状态机的内存访问，内核通过分页映射机制实现了虚拟内存到物理内存的转换- 操作系统持有所有的物理页面（通过$stap和CR3进行任意映射）

处理器调度

1. 时分复用中断机制- 处理器以固定的频率进行中断- 中断/系统调用返回时，可以自由选择进程/线程执行
2. 有很多进程，如wait I/O进程、等待系统调用的进程、可能被中断的进程。那应该选哪个进程调度到处理器上运行- 时间片轮转：保证了公平，但是可能对于交互不好- 优先级调度：使用nice值标识进程的好坏，越好的人越愿意将CPU让给别人（帮助别人总是最先得到？idea），实时操作系统通常是完全的优先级调度- 通常的优先级调度：nice值低的进程得到cpu机会更多，但是所有进程都能得到CPU可以发展- 动态优先级别
3. 动态优先级MLFQ- 系统自动设置优先级- 设置若干严格时分复用的队列，每个优先级对应一个队列- 用完时间片的，将优先级调低。让出时间片，将优先级调高- 问题：每次再时间片快结束时候，就让出CPU。（看起来是好人，实际是坏人）- 可以隔一段时间，进行重置或者执行完全的时间片轮转
4. 现代linux调度器CFS（complete fair scheduling）- 用红黑树维护一个有序集合- 原则： - 公平的保证：谁亏给谁补，操作系统尽可能的让每个进程都获得同样的运行时间- 优先级的保证：每个进程执行相同的1ms，nice值大的会执行10ms，nice值小的会执行5ms。即通过nice作为系数增加的虚拟时间，统一进程在运行时间上的调度策略- 问题1：进程的运行中出现fork，子进程会直接继承父进程的状态。不会减少，因为如果减少，可能一直fork出现饥饿- 问题2：如果出现状态慢了极大，则需要补充10秒，则会导致其他进程卡顿- 问题3：vruntime是一个一直增长的整数，如果出现溢出，会导致溢出进程从极大变成极小。//比较相对大小boolless(u64 a, u64 b){return(i64)(a-b)<0;}- 问题4：低优先级的获得互斥锁，但是运行时间少，所以释放互斥资源就会慢。解决：当阻塞高优先级的进程的时候，优先级提升到和阻塞优先级一样高
5. 调度策略考虑的两个维度- 同等优先级考虑公平性- 不同优先级考虑优先级
6. 一个进程可能与其他进程进行交互，相互合作完成一个事情。- 高优先级：pv操作一直让出cpu，导致获得大的运行权限- CFS：具有运行时间的记账，可以相对的公平
7. 多核心多线程的计算机系统- 无法实现真正的公平，A用户占用一个进程，B用户并行执行占用1000个线程，则A用户可能会饥饿
8. 轻量级虚拟化容器docker，创造操作系统中的操作系统- cgroup以进程组为单位管理资源，解决多用户的cpu分配不平均问题
9. dark silicon时代的困境（基本计算机模型的改变）- 功率和散热无法同时支撑所有的电路工作，总有一部分要停下来- 解决：大小核异构技术，小核功耗小，大核功耗大
10. 调度器随着硬件的异构，发生调度算法的基本假设不断改变。甚至出现CPU hot plug（热插拔）
11. 调度器是一个中央资源向下分配的问题
12. 建模 - 预测 - 决策，每个进程对自己的需求是最清楚的，所以应该每个进程自己提出调度策略
13. 机制是可以做出来的，但是策略是一个做的好的问题。

持久化

极限速通操作系统

1. 数据竞争：多个进程同时访问一个遍历，并且至少一个是写的。
2. 原子执行的宏#defineatomic\for(int __i =(lock(),0); __i <1; __i++,unlock())// 具体执行// 用法：atomic { body }// lock();// i = 0;// check i < 1 -> yes// body// i++// ublock();// check i < 1 ->no, exit loop
3. 在每个代码模块都进行assert判断#ifdefAGGRESSIVE_CHECKassert(conditionJudge());#endif// 示例#include<stdio.h>#defineFLAG1intmain(int argc,char*argv[]){#ifdefFLAGprintf("hello world");// 如果FLAG不进行宏定义为1就不会打印#endif}
4. 使用技巧尽可能的增加assert进行检查，没有使用技巧尽可能的写的简单。炫耀技巧的地方就是最容易错误的地方
5. 对自己的所有代码给最大的不信任
6. 每一个 CPU 核心都会有一个 idle 进程，idle 进程是当系统没有调度 CPU 资源的时候，会进入 idle 进程，而 idle 进程的作用就是不使用 CPU
7. 写代码写两个版本 - 基本代码（在脑袋中清晰）：要求简单明确- 高级代码（写代码要检查）：要求性能- 两个代码在输入和输出上应该是等价的

持久化：1-Bit 数据的存储

1. 牺牲了掉电后的状态丢失，换取使用电路的高速度
2. 磁芯内存写入数据：行选通和列选通，行列的交点的电路最大超过阈值，将交点置为1
3. segmentation fault的以前的含义core dumped（核心已转储）：程序出错，将内存的状态转移到外存
4. 内存和寄存器的状态失去，但是持久存储的数据仍然存储
5. 存储设备通常是按照块进行存储的，一般为4KB
6. 光盘：通过坑进行持久化存储，eg：CD是只读的
7. SSD：通过施加正反向的电压进行电子的转移，而读盘读取电子的状态。容量越大速度越快 - 可能充电多会导致电子无法完全排空，导致出现坏点。- 通过控制器进行地址映射，进行均匀的写，或者屏蔽坏点
8. 因为硬盘的逻辑映射，所以即使磁盘格式化后（不写满），logic block被覆盖，但是physical block仍然可能存储了数据
9. 软件安装包定义了程序运行的初始状态

输入输出设备

1. I/O设备：使计算机能够感知外部状态，对外实施动作。能和CPU交换数据的设备/控制器
2. 设备是交换信息的接口，交换的是状态/命令/数据
3. 串口UART：可进可出的字节流
4. 键盘控制器 - 硬编码到两个I/O port：0x60data，0x64status/command
5. 设备本质是通过设备寄存器的读写，与CPU进行交互
6. 80386：cpu通过一个多路选择器mux与多个设备进行连接
7. 现在架构：cpu连接一个I/O设备（总线），I/O设备连接多个设备插槽，CPU告知I/O设备指令和访问地址，I/O设备负责与具体设备进行交互。所有设备都在cpu的地址空间中，所以cpu可以通过总线访问
8. CPU有一个中断引脚 - 收到某个特定的电信号会触发中断 - 保存5个寄存器（cs、rip、rflags、ss、rsp）- 跳转到中断向量表的对应项进行执行- 系统中的其他设备可以向中断控制器进行连线
9. DMA：一个专门执行memcpy程序的CPU，通常直接将DMA控制器连接到总线和内存上支持几种 - memory->memory- memory->device(register)- device(register)->memory
10. 将单调的工作给一个单独的设备进行处理，如早期GPU只能执行程序到设备图形的映射
11. 图形学：任何n边形都可以分解成n-2个三角形
12. 下一个时代是异构计算的统一化的时代

设备驱动程序

1. 协处理器：用于处理特殊任务的微处理器，如GPU、I/O总线···
2. 将设备进行抽象 - 字节流设备，如terminal、打印机- 块设备，如硬盘
3. linux中将设备抽象为文件 - read：从设备的某个指定的位置读出数据- write：向设备某个指定位置写入数据- ioctl：读取/设置设备状态
4. 设备驱动程序：将程序的通用的系统调用序列通过翻译成对应的设备的驱动程序
5. 设备驱动程序是一种内核代码，一般是厂商，但是是内核数量最大、质量最差的代码
6. 状态机进行的取指令——译码——执行
7. GPU的架构SMT - 所有cpu都有各自的寄存器组，但是共享内存和pc指针。- pc指针的共享可以
8. 磁盘的访问特性 - 以数据块为单位进行访问 - 传输有最小单元，不支持任意的随机访问- 最佳传输模式与设备相关- 大吞吐量：使用DMA进行数据传输- 应用程序不直接访问 - 访问者通常是文件系统- 大量并发的访问
9. 文件系统就是在block I/O API上构建的持久化的数据结构 10.设备驱动的核心是 将read/write/ioctl翻译成设备可以听得懂的语言

文件系统的API

1. 设备在应用程序间共享 - 对于磁盘来说，block不是一个好的抽象
2. 磁盘、所有的应用程序···都是字节序列，可以将磁盘抽象成应用程序可以持有的虚拟磁盘
3. 文件系统：设计目标 - 提供合理的API使多个应用程序可以共享数据- 提供一定的隔离，使错误程序的伤害不能扩大
4. 存储设备（字节序列）的虚拟化 - 磁盘是一个I/O设备，是能读/写的字节序列- 虚拟磁盘是文件，是能读/写的动态字节序列
5. 允许任何目录mount（挂载）一个设备代表的目录树 - linux下的mount工具是mount系统调用的一个封装
6. linux文件的挂载 - 文件是磁盘上的虚拟磁盘，挂载文件是在虚拟磁盘上虚拟出来的虚拟磁盘- 回环设备loopback device：可以将文件映射为虚拟的块设备。这个虚拟的块设备可以被当作一个普通的物理设备来访问。
7. linux下每个文件都是一个虚拟的磁盘 - 硬链接：存储直接访问虚拟磁盘的指针- 软连接： 在文件里面存储一个跳转提示（即使跳转目标不存在），是一个有向图
8. 每个进程的都有一个工作目录，使用pwd进行查看
9. 系统调用open会返回一个文件描述符fd，这个文件描述符会指向虚拟磁盘
10. 系统调用read和write都是从指定文件描述符fd中读或写指定大小的数据块到指定buf中，但是读写完后fd会指向数据末尾
11. fork子进程时，会同时复制父进程的fd。当父子进程同时通过这个fd进行访问虚拟磁盘时，会有一个中间的offset进行记录。防止出现父子进程都从都写出现交替覆盖的情况。
12. 文件系统的两大部分 - 虚拟磁盘（文件） - mmap、read、write、lseek、ftruncate- 虚拟磁盘的命名管理（目录树和链接） - mount、chdir、mkdir、rmdir、unlink、open

FAT和UNIX文件系统

1. 数据结构课程的假设 - 具有随机存取的存储器- 每条指令都是O(1)的
2. 文件系统自底向上的基本实现 - balloc和bfree的实现 - balloc返回一个空闲可用的数据块- 释放一个数据块- 文件（ 块的array）的实现- 目录的实现
3. 文件系统File Allocation Table（FAT） - balloc和bfree的实现： - 每个节点都有各自的指针域： 实现简单，但是每块可能不是 2 k 2^k 2k，单纯的lseek需要遍历整个链表- 将指针域集中存储：指针域具有局部性，并可以放到内存中进行缓存。但是指针域破坏后，出现文件系统损坏。（进行备份可以解决这个问题，这个指针域表称为FAT）- 目录的实现 - 目录 = 32byte定长目录项的集合
4. 定义指定字节数量的字符structBPB{ u8 BS_jmpBoot[3];// 3个字节 u16 BS_byte[8];// 16个字节... u8 padding[100];};// 健壮性检查#ifdefASSERT_CHECKassert(sizeof(structBPB)==119);#endif
5. FAT - 适合小文件，无法随机存取，所以适合大文件- 会维护若干个FAT副本，防止数据破坏
6. 高性能文件系统EX2 - 文件系统的元数据节点中的数据域，使用多级目录进行索引。 - 例如每个块4KB可以存储1024条索引项，小于4KB的文件，一个块就可以直接所有。而大文件如4kB*1024的可以先索引一个索引块，然后用这个索引块进行二级索引文件- 如果出现存储文件元信息的inode破坏，会出现大量文件的丢失

持久数据的可靠性 (RAID; 崩溃一致性; FSCK 和日志)

1. 数据结构的假设 - 内存可靠并且可以接收断电的数据丢失- 持久数据是不能接收丢失的
2. 磁盘冗余阵列RAID（虚拟化的力量） - 拥有多个不太可靠的物理磁盘，而共同组成了一个可靠性高的但容量稍小一些的虚拟磁盘- 容错概率是指数级的增长- 反向虚拟化 - 进程：把一个cpu分时虚拟成多个虚拟的cpu- 虚拟内存：把一份内存通过MMU虚拟成为多个地址空间- 文件：把一个存储设设备虚拟称为多个虚拟磁盘- 镜像分储：增加读，降低写。但是容错 - 将数据分成两个部分，分别存储不同的两块的磁盘- 读效率翻倍：可以用满两个磁盘的带宽进行读- 写效率降低：一份写要分别写入两个磁盘- 交叉合并：扩容扩速但不容错 - 将两个盘内区块交错合并为一个虚拟盘，顺序读写时，可以分别占用两块磁盘的带宽- 底层使用镜像分储，高层使用交替合并。- RAID-4将镜像存储的数据划分为bit位 - A ⊕ A = 0 A\oplus A = 0 A⊕A=0，自身的异或值为零。- 如果有一个bit错误，则让该部分bit数组自己异或自己，即可知道错误位- 通过一块磁盘存储，异或值。如果其中一块磁盘损坏，可以进入recovery模型，进行快速计算和恢复- eg：99块存数据，一块存校验和。读写速度提高99倍，容忍一块磁盘的损坏。但是随机写的性能是一块磁盘的1/2。- RAID-5将校验部分交替存储到每个盘中，提高读取速度
3. 云计算：将多个不可靠的计算机，合并成为一个又大、又快、又可靠的云计算中心
4. 崩溃一致性（Crash Consistency） - 数据的写入要并行或串行执行很多步骤，要进行步骤的安排和算法进行保证数据可靠性
5. 磁盘调度算法导致，磁盘可能会不按照用户代码规定的顺序写入，而是进行乱序写入（先写入离磁头近的）
6. 状态机的历史 - 每一个状态- 起始状态和每次状态转换的指令
7. 历史文件操作的记录：日志 - 当文件操作时，先将操作记录到日志中- 更新数据结构- 崩溃后，进行日志检查，将所有未完整写入的操作重做一遍（每个操作序列做一个操作完成标记）

Xv6文件系统的实现

1. 通常文件系统是以4KB为单位访问的
2. 磁盘的数据结构 - 目录（数据块的索引表）- 文件（虚拟磁盘块集合）- 文件描述符（磁盘中的偏移量）
3. 数据的集中可以更好的利用局部性
4. vscode的使用 - ctrl + p 输入# 要查找的标号名称
5. 理解一个代码最好的方式是看它的执行流程
6. 写一个gdb的脚本，不需要每次调试设置环境
7. 文件系统的缓冲池 - 将要读取的磁盘块加载到内存缓冲区中，然后从缓冲区中对磁盘块的镜像进行读写操作- 当写入的镜像磁盘块时，将该磁盘块置为dirty。可不用立即将磁盘块写入到磁盘中，等待多个磁盘块一起写回- 使用日志保证系统crash后的数据一致性
8. 先写日志，再保证日志落盘，再进行操作

现代存储系统

1. 表格：每一行都是一个对象，每一列都是对象某个属性的抽象
2. SQL描述出“你想做什么”，数据引擎帮你想办法做到
3. 数据库把数据的访问和应用程序的逻辑分离，可以提供原子性
4. SQL的原子性// 可以保证中间操作的原子性BEGIN WORK;INSERT INTO students VALUES(...);INSERT INTO students VALUES(...);INSERT INTO students VALUES(...);COMMIT;
5. 编译优化：将语句编译成等价的更快的机器语言
6. 虚拟磁盘上的数据结构 - 把SQL查询翻译成read，write， lseek，fsync的调用- 并发控制（事务处理）
7. cmu的15445，使用c++17写一个数据块
8. raft - 基本概念 - 一致性：在分布式系统中的多个节点在状态上达成一致，但是现实场景中由于系统崩溃等原因可能难以完成- leader身份：负责处理客户端的交互请求、日志操作等，一般一个分布式系统中只有一个Leader- follower身份：类似选民，完全被动，在探测不到leader存在时，follower在超时时间过后会转化成candidate- candidate身份：候选人身份，可以被选为一个新的leader- term：选举任期- Raft选举的三个规约 - 超过半数投票- 节点只能响应任期号大于或等于自己任期的请求- 同一个任期内只能选举一次- 选举情况：A随机时间最短，将term+1并转换为candidate，然后投自己一票。并行给其他节点发送投票，并等待其他节点的回复。 - 第一种：A收到大部分的投票（都包含自己的一票），则赢得选举成为leader，并立刻告诉其他所有节点- 第二种： 被告知别人已经当选，则会自行切换到选民follower身份- 第三种：所有节点没有获得大部分投票，都转变为候选人，继续发起投票，直到产生leader为止- 优点 - 通过election timeout一定程度上解决了候选人争抢选票导致选举时间过长的问题- Raft比Paxos算法更容易理解，且更容器工程化实现
9. 分布式友好的数据模型key-value - put(k, v)操作：可以将(k, v)直接追加到文件末尾，具有顺序性- get(k, v)操作：需要遍历整个文件，效率差
10. 分层存储，读的多的在上面，读的少的放到下一层

android操作系统

1. 前端应用比较重要的：网络和人机交互
2. 对象使用栈进行存储
3. 如何理解一个技术，需要从解决的问题和执行过程进行理解
4. 多线程与锁：会产生低优先级线程持有资源的锁，而高优先级线程进行等待的情况
5. 后台应用程序通常优先级低于前台的交互程序

课程总结

1. 数理逻辑通过特定逻辑电路构建体系结构，操作系统通过端口控制体系结构

少年，我观你骨骼清奇，颖悟绝伦，必成人中龙凤。不如点赞·收藏·关注一波

参考博客

1. 待定引用
2. 待定引用
3. 待定引用
4. 待定引用
5. 待定引用
6. 待定引用
7. 待定引用
8. 待定引用