• 【操作系统笔记】南京大学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. 编译器其实就是对于状态机的生成和优化
      extern int g; // 全局变量，其他程序可能使用，不可优化
void foo(int x){
	g++;
	asm volatile("nop"::"r"(x));
	// __sync_synchronize();// 这个barrier将不可优化
	g++;
}
// 即使两个g++中间代码不可优化，但使用-O2仍然可以优化

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
    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;
void threadx(){
	while(locked != UNLOCK);// 有锁则自旋
	locked = LOCK;
	// 临界区
	locked = UNLOCK;
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 状态机中包含两个线程的栈帧和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）
      int xchg(volatile int *addr, int newval){
	int result;
	asm volatile("lock xchg %0, %1" : 
		: "=r" (val), "+m" (*addr) : "m" (*ptr) , "0" (val)
	);
	return result;
}
// 自旋锁
int locked = 0;
void lock() {
	while(xchg(&locked, 1));
}
void unlock(){
	xchg(&locked, 0);
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14
      • 15
    5. 代码是两个 层面的东西，一个层面是人所理解的业务逻辑，另一个是机器层面。真正理解代码需要对于两个层面都深入了解
    6. 原子指令模型
      • 之前的所有store写操作都会写入到内存中
      • 所有的内存访问都不能越过原子指令
    7. 原子指令的实现
      • 通过一个bit表示总线资源的锁，访问内存需要先获得总线的锁
    8. x86中的L1缓存是连接在一起的，为了实现缓存的一致性
    9. 常见原子操作的本质
      • load
      • exec(处理器的寄存器的运算)
      • store
    10. risc-v的原子操作：先运算出结果放到缓存中，当需要同步到内存时，先打标记，再判断标记是否存在，存在时再写入内存，然后删除标记
      // CAS锁（compare and swap）的实现机制
int cas(int addr, int cmp_val, int new_val){
	int old_val = *addr;// 读取标记
	if(old_val == cmp_val){// 标记等于自己的之前打的，则写入
		*addr = new_val;
		return 0;
	}else{
		return 1;
	}
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
    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赋值给b
int a=10, b;
asm ("movl %1, %%eax;   /* NOTICE: 下面会说明此处用%%eax引用寄存器eax的原因
      movl %%eax, %0;"
      :"=r"(b)          // 输出参数 %0
      :"r"(a)           // 输入参数 %1
      :"%eax"           // 可能用的寄存器
    );   

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
      • 14

    同步

    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);

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
    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);


      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
      • 12
      • 13
    3. 让一个人集中管理叉子，放弃信号量
      • 非集中式的管理共享资源，会导致分布式的自同步，每个线程都想试一下
    // master/follower 生产者/消费者模型

void Tphilosopher(int id) {// 哲学家线程
	send_request(id, EAT);// 给服务员的队列发一个消息，请求吃
	P(allowed[id]);// 等待服务员许可
	philosopher_eat();// 就餐
	send_request(id, DONE);// 给服务员的队列发一个消息，吃完了
}

// 集中调度器：可以维护公平性（让长时间不占叉子的线程，下次分配时等一等）
void Twaiter(){// 服务员线程
	while(1){
		(id, status) = receive_request();
		if(status == EAT){...}
		if(status == NONE){...}
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    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
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    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 bomb
      fork(){
	fork | fork &// fork管道给fork
}; fork

      • 1
      • 2
      • 3
    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 callDescription
    int fork()创建一个进程，并返回子进程的PID
    int exit(int status)终止当前进程，状态报告为等待
    int wait(int *status)等待子进程退出，退出状态为status，并且返回子进程PID
    int kill(int pid)终止进程PID，返回0或-1（错误）
    int getpid()返回当前进程的PID
    int 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个字符，并返回n
    int read(int fd, char *buf, int n)从文件描述符指定的文件中读取n个字符写入到bufffer，返回读入的字节数，如果在文件末尾则返回0
    int 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)删除一个文件
    1. 读xv6的手册，可以作为操作系统的实践教学
    2. 工具比什么都重要
    3. vscode的执行需要配置命令脚本，也可以在terimal中输入
    4. gdb的源代码对照的按行调试
      • set pegination off
      • layout src
    5. 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是一个一直增长的整数，如果出现溢出，会导致溢出进程从极大变成极小。
      //比较相对大小
bool less(u64 a, u64 b){
	return (i64)(a-b) < 0;
}

      • 1
      • 2
      • 3
      • 4
      • 问题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. 原子执行的宏
      #define atomic \
	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

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
    3. 在每个代码模块都进行assert判断
      #ifdef AGGRESSIVE_CHECK
	assert(conditionJudge());
#endif
// 示例
#include
#define FLAG 1
int main(int argc,char *argv[]){
#ifdef FLAG
printf("hello world");// 如果FLAG不进行宏定义为1就不会打印
#endif
}

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
      • 11
    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. 定义指定字节数量的字符
      struct BPB{
	u8 BS_jmpBoot[3];// 3个字节
	u16 BS_byte[8];// 16个字节
	...
	u8 padding[100];
};
// 健壮性检查
#ifdef ASSERT_CHECK
assert(sizeof(struct BPB) == 119);
#endif

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
      • 7
      • 8
      • 9
      • 10
    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;

      • 1
      • 2
      • 3
      • 4
      • 5
      • 6
    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. 待定引用
  • 相关阅读:
    C/C++数据结构——最优屏障（栈）
    常量左值引用作为形参来接收右值引用实参所带来的问题
    浅淡 C++ 与 C++ 入门
    K8S集群中Node节点资源不足导致Pod无法运行的故障排查思路
    yml语法学习 SpringBoot配置文件自动装配 yml文件有提示读取配置文件
    MyBatis
    将LZO形式的文件放入HDFS中并压缩，LZO文件必须创建索引才支持切片
    使用docker部署flask接口服务 一
    spice Link过程分析
    Flink之Watermark策略代码模板
  • 原文地址：https://blog.csdn.net/qq_43840665/article/details/130496047