感谢jyy老师，醍醐灌顶的操作系统课程。

互斥算法

问题的引入

有多个线程需要访问临界区，修改临界区里面的共享内存的内容，如何保证在任一时刻，最多只有一个线程能够进入临界区？首先展示一个错误的做法

pub sum: i32 = 0;
pub lock: bool = false; // 临界区的锁，一开始是开着的

fn t1() {
  // lock
  while lock {} // 如果锁是开着的，那么就等待
  lock = true; // 当前线程拿到了锁

  // 临界区
  sum += 1;

  // unlock
  lock = false; // 释放锁
}         

fn t1() {
  // lock
  while lock {} // 如果锁是开着的，那么就等待
  lock = true; // 当前线程拿到了锁

  // 临界区
  sum += 1;

  // unlock
  lock = false; // 释放锁
}          

fn main() {
  let handle1 = thread::spawn(|| {
    for _ in 0..1000 {
      t1();
    }
  });

  let handle2 = thread::spawn(|| {
    for _ in 0..1000 {
      t2();
    }
  });

  handle1.join().unwrap();
  handle2.join().unwrap();
}

使用状态机法，或是利用 module-checker，都会发现存在一个状态使得两个线程都进入了临界区。简单来讲，就是两个线程都读到了一个释放了的锁，导致两个线程都拿到了锁，进入了临界区

Peterson算法

完全用软件算法解决两个线程的互斥访问问题

定义

每个人（Peterson算法仅限两个线程）：

• 有一个flag，表示自己是否想进入临界区
• 有一个turn，表示轮到自己进入临界区
• 如果两个人都想进入临界区，那么就看turn是谁，谁的turn是1，谁就进入临界区

fn t1() {
  // lock
  🏴‍☠️  // 举起旗帜，表示我要上厕所
  2️⃣  // 在厕所门口贴上对方的名字，表示我到了
  while 🏳️ && 2️⃣ {} // 我想上厕所，但是对面也到了，如果墙上贴的是我的名字，那我先上厕所；对面到了，墙上贴的也是对面的，那等对面上完厕所；如果对面根本没到/上完了，我先上厕所

  // 临界区
  sum += 1; // 上厕所

  // unlock
  put down 🏴‍☠️  // 放下旗帜，我厕所上完了
}         

fn t2() {
  // lock
  🏳️  // 举起旗帜，表示我要上厕所
  1️⃣  // 在厕所门口贴上对方的名字，表示我到了
  while 🏴‍☠️ && 1️⃣ {} // 我想上厕所，但是对面也到了，如果墙上贴的是我的名字，那我先上厕所；如果墙上贴的对面的，那等对面上完厕所

  // 临界区
  sum += 1; // 上厕所

  // unlock
  put down 🏳️  // 放下旗帜，我厕所上完了
}    

核心

谁快谁进，因为谁手慢，谁就会贴上对面的名字，两者在都想进入临界区时，由临界区决定先后顺序（上述例子中的厕所门口的张贴的名字）

原子指令

但是Peterson算法理解难度高，如果交换举起旗帜和张贴名字的顺序，那该算法还正确吗？估计又蒙圈了。而且Peterson算法只适用于两个线程，若是多个线程，又要改写算法，非常麻烦。那么有没有一种更加简洁的方案呢？

互斥问题的本质

互斥问题的本质是：读-写 的原子性问题。在多线程编程中，一个线程读取了一个共享变量，然后对这个变量进行了修改，最后写回这个变量。在上面那个错误的例子中，就是因为一个线程的读-写lock的操作不是原子性的，导致另一个线程在当前线程写锁之前，读到了释放的锁。因此，我们需要保证这个过程的原子性。

硬件支持

于是，为了解决 读-写 的原子性问题，现代CPU提供了原子指令，如x86的lock指令，riscv的lr和sc指令。这些原子指令的实现，保证了 读-写 的原子性，也即保证了在一个线程的读写操作中间，不会被其他线程读取。
那么最开始的错误代码就可以改写为（原子变量的内存序问题这里不再探讨）：

use std::sync::atomic::{AtomicBool, Ordering};
let lock = AtomicBool::new(true);

fn t1() {
  // lock
  while !xchg(lock, false, core::sync::atomic::Ordering::Acquire) {} // xchg作用是交换lock和false的值，返回的是拿到的lock变量的值，就好像你拿一个空锁去交换一个共享的锁，如果真的拿到了锁（lock=true），就可以进入临界区执行，否则就忙等

  // 临界区
  sum += 1;

  // unlock
  lock.store(false, Ordering::Relaxed); // 释放锁
}

fn t2() {
  // lock
  while !xchg(lock, false, core::sync::atomic::Ordering::Acquire) {} // xchg作用是交换lock和false的值，返回的是拿到的lock变量的值，就好像你拿一个空锁去交换一个共享的锁，如果真的拿到了锁（lock=true），就可以进入临界区执行，否则就忙等

  // 临界区
  sum += 1;

  // unlock
  lock.store(false, Ordering::Relaxed); // 释放锁
}

但是其实 xchg 是C语言中的接口函数 atomic_xchg，在rust中可以使用其他的方法

代价是什么

现代CPU的设计都存在核单独享用的L1-Cache，可能到L2-Cache才是共享内存，那么在原子指令的执行中，一个核的执行的原子指令可能改动了某个内存地址的值，但此时别的核的L1-Cache若缓存了相同地址的值，那么这个值就是过时的，这就导致了缓存一致性问题。

Intel-486时代原子指令会给bus总线加锁实现缓存同步，这是一个大锁，显然浪费了其他核的性能。而现代CPU采用了通知机制，当某个核在执行原子指令时，会通知其他核，让其他核的缓存失效，保证了原子指令的原子性

riscv指令的巧妙实现：

• lr: load reserved，表示盯上你了，其他处理器写入/中断都会导致这个标记失效
• sc: store conditional，只有当被盯上了（存在这个标记），才会真正实现写操作

多线程编程中，riscv中的lr和sc原子指令的应用：

1. lr指令：将内存中的值读取到寄存器中，并且标记这个内存位置已经被盯上了
2. 根据读出数据进行某种操作
3. sc指令：将寄存器中的值写回内存，但是只有当这个内存位置没有被其他线程盯上时，才会真正写入，否则跳转回1，重新尝试进行读取写入

自旋锁和互斥锁

自旋锁

• 优点：如果能拿到锁，进入临界区的速度很快
• 缺陷：其他处理器会被阻塞，浪费CPU资源；存在不能被打断的情况，可能会导致死锁
• 使用场景：临界区执行时间短，无阻塞；持有自旋锁的线程不会被中断，禁止执行流中断

互斥锁（系统调用支持）

• 为了解决自旋锁的缺点，本线程想要访问长临界区，如果确实有锁，那么系统调用直接返回，但是此时如果锁被别的线程持有，无法获得锁，那么就把自己占用的CPU让权，让出CPU资源，等待锁被释放；释放锁的时候，会检查有哪些线程等待锁，若有则唤醒之
• 优点：如果拿不到锁，会让出CPU资源
• 缺陷：如果能拿到锁，也因为系统调用的开销，进入临界区的速度会慢一些

Futex（实际运用）:

• 兼顾自旋锁和互斥锁的优点，让大部分情况能拿到锁的情况，只需要通过一条原子指令就可以拿到锁，最快速的进入临界区执行代码
• 用到了操作系统设计/CPU设计中的重要思想：优化大部分情况，忽视小部分情况。当然这里的大小一定是明显的大和小，比如95%和5%，我们优化80%的情况的收益就很高，类比CPU设计中的分支预测

多核处理器调度

多核处理器调度是一个非常复杂，甚至可以说无解的问题，因为它甚至不存在一个绝对的衡量标准，可能在不同的应用场景下，两种调度策略展现出来的结果大相径庭，所以我们讲调度策略，一定需要针对某一个特定的使用场景，并且指定所有的外部非 Kernel 代码所能决定的外部条件(甚至包括用户程序能否向操作系统合理的传递它当前任务的合理优先级)。例如在实时操作系统中，高优先级的任务就是绝对的高优先级；在面向用户的使用场景中，要保证I/O设备的快速响应。多种调度策略甚至不能说孰优孰劣，只能说互有利弊。

1. 目标复杂多样

• 保证I/O设备的快速响应？
• 全局任务的执行时间最快？
• 功耗低？

2. 条件复杂

• 真的可以假设程序是黑盒吗？（调度器真的是操作系统决定的吗）
• 多核之间的数据迁移导致的cache/TLB开销
• 程序中使用锁被调度，导致高优先级任务拿不到低优先级任务的锁（优先级翻转）
• 不同处理器的算力性能不同
• 处理器热插拔？

针对操作系统比赛环境

调度目标

• 存在多个任务，其中包含网络任务和I/O任务，保证总任务的执行时间最短

外部硬件条件

• 四核CPU
• 4GB内存
• 无需考虑功耗
• 无需考虑热插拔

可选的调度策略

CFS（Completely Fair Scheduler）：Linux内核中的调度策略，保证每个任务都能获得公平的CPU时间（vruntime）。并且保证运行时间最长和运行时间最短的任务的 vruntime 差值不会超过 USIZEMAX / 2，这是为了便于比较函数的实现（塞给红黑树的比较）。

但是还需要考虑很多其他的因素，比如：

• I/O外部中断，需要调度那些需要I/O数据的任务
• 如果当前核正要被调度，是执行别的任务，还是执行当前被打断的任务呢，因为继续执行当前任务不需要刷cache/TLB，执行其他任务需要。从执行任务总时间的角度是继续执行当前任务，除非当前任务是因为I/O等待，那我需要衡量I/O等待的时间是否大于刷cache/TLB的时间，如果大于我切换到别的任务才是有收益的，否则甚至可以不切换
• 其他没有想到的可能…