操作系统（实验班）预习笔记

Last updated on April 28, 2026 12:32 AM

0218

Lab 代码量较大（几千行），需要注意实现 Design Doc
- TacOS：基于 Rust，指令集是 RISCV
- 本地测试点和测评测试点一致
- Design Doc 不用卷字数
五个 lab，两次考试（期中期末）
考勤 5%，Lab 30%，期中 25%，期末 40%
- lab：4% + 6.5% + 6.5% + 6.5% + 6.5%

0220

四个基本概念：线程、地址空间、进程、双模式
CLAB 上部署 docker：
- pull taco 到本地
- 然后 docker save -o tacos.tar，再上传，在 CLAB 上 docker load -l tacos.tar

0225 线程

线程上下文
同步：协调多个线程的运行使得对共享数据做操作的时候可以依照程序员期望的方式执行
锁的两个原子化状态：
- lock.acquire()
- lock.release()
信号量 semaphore：更加 generailized 的锁

0228 文件

POSIX 文件：
- data：二进制字节序列
- metadata：文件的信息
存储层次图：app -> high level I/O（流） -> low level I/O（描述符） -> Syscall -> File System -> I/O driver -> Disk/Flash/DMA
- high-level I/O：不带格式的字节流，以及文件位置
  - fopen, fclose
  - 预定义好的 FILE* 流：stdin, stdout, stderr
  - fseek 操作文件位置，ftell 返回文件位置，rewind 返回到文件开头。
- low-level I/O：
  - open before use：使用文件前必须打开
  - byte-oriented
  - kernel buffered read/write
  - 显式关闭
  - open, close, creat。open 返回的是文件描述符。fopen 等是在 FILE* 数据结构上操作的
    - 因为不能让用户态操作内核数据结构，所以不给指针，只给整数 fd
    - 通过 fileno(FILE*) 可以获取 FILE* 的 fd，通过 fdopen 可以将 fd 转换成 FILE*
  - I/O：read, write，可能有不足值。lseek：重新调整文件位置，移动的是内核里的指针，不是应用层的。
  - kernel buffing：内核会缓冲。进程阻塞，跑其他进程。
fread, fwrite 是操作的 user space 的 buffer。kernel space 还有一个 buffer。low-level 的 API 就没有 user space 的 buffer 了。
FILE* 里面包含的东西：文件描述符，buffer 以及 lock
High-level 的意义：
- User buffer 的意义：减少系统调用次数（陷入内核需要上下文切换，效率低）
- 可以简化内核的实现：内核不需要实现什么读完一行的操作
打开文件表在内核里只维护一份。
一些陷阱：
- 不要在多线程里面 fork，除非你已经 exec 了。
  - fork 出来的新进程只会有一个线程（call fork 的线程）
  - 而且不会做清理（锁，堆）
- 不要混合使用 FILE* 和 fd

0304 IPC

所有皆文件：进程间通信也用统一的 I/O 接口。socket 和 pipe。

PIPE：一个有限的内存中的 buffer。单向，producer 写，consumer 读。如果写的时候满了，阻塞；如果读的时候空的，阻塞。（但其实不一定要阻塞，只是一种方式）不需要显式创建文件

最后一个写描述符关掉后，读就只返回 EOF
最后一个读描述符关掉后，写的话会返回 SIGPIPE

进程间通信需要 syntax 和 semantics。一个协议可以通过状态机形式化表示（比如网络传送的一些字符串和数字，需要特定 translate）

RPC: remote procedure call

client-server 相对的：peer-to-peer。

TCP：两个进程间的双向进程流。一个连接有两个 buffer，独立的。

socket 也是抽象为了 fd，write 是往 output queue 里加东西，read 是从 input queue 取出东西。lseek 不适用。

一些假设：可靠性（TCP），保序（字节流）、像 pipe 一样有什么就读什么（假设已经写过了，像 pipe 一样）

剩下讲的东西都是 ICS 第 11 和 12 章讲的内容。

0306 SYNC 1

PCB：维护进程的状态，status, register state (when not ready), pid, 权限，执行时间，地址空间。

进程的状态：new，ready，running，waiting，terminated

调度就是从几个队列里面决定执行的顺序。没有 running 的进程 PCB 放到比如 I/O queue, ready queue 等等里面。

原则：公平性/实时性/延时优化等。

线程：共享堆、全局变量、代码。每个线程包含一个 TCB（栈，保存的寄存器状态，metadata），以及栈。线程调度伪代码：

Loop {
    RunThread();
    ChooseNextThread();
    SaveStateOfCPU(curTCB);
    LoadStateOfCPU(newTCB);
}

内核中：run_new_thread() -> switch()。

0311 SYNC 2

信号量。

同步的层次：

Programs: Shared Programs
Higher-level API: 锁、信号量、管程、send/recive
硬件层面（不提供锁），提供原子操作：Load/Store, Disable Ints, Test&Set, Compare&Swap

以买牛奶为例说明，只用 load/store 的话是十分繁琐的（还只是两个人的情况）。

0313 SYNC 3

锁的实现

一般硬件层面没有对于锁的实现（过于复杂）

法一：开关中断。

最 naive 的方法：acquire 就关中断，release 就开中断。问题：不能让用户层面做开关中断的操作（恶意代码），而且临界区可能很长很长，并且其他中断也无法进来了。

更好的实现：只在 acquire 和 release 内部关中断：

int value = FREE;

Acquire() {
    disable interrupts; // 进入临界区
    if (value == BUSY) {
        put thread on wait queue;
        go to sleep(); // Enable interrupts?
    } else {
        value = BUSY; // 获取锁
    }
    enable interrupts; // 离开临界区
}

Release() {
    disable interrupts;
    if (anyone on wait queue) {
        take thread off wait queue;
        place on ready queue;
    } else {
        value = FREE;
    }
    enable interrupts;
}

为什么 acquire 一定是临界区？万一两个线程都认为自己拿到了锁。

在 go to sleep() 之后要 enable interrupt。首先显然不能在 go to sleep 之前，不然他可能就永远 sleep 了。交给调度器。上下文切换出去的时候 enable interrupts。相当于你这个过程必须是原子的，不能被 release 在中途打断。

但还是具有问题：
- 不能作为用户态锁的实现（开关中断是特权操作）
- 没法在多核/多处理器上用。
  
  Disabling interrupts on all processors requires messages and would be
  very time consuming

法二：原子读改写 Atomic RMW。

由硬件实现的常见原子读改写操作：

test&set(&address) {
    result = M[address];
    M[address] = 1;
    return result;
}

swap(&address, register) {
    temp = M[address];
    M[address] = register;
    register = temp;
}

compare&swap(&address, reg1, reg2) {
    if (reg1 == M[address]) {
        M[address] = reg2;
        return success;
    } else {
        return failure;
    }
}

一种 naive 的死等实现：
1
2
3
4
5
6
7
int value = 0; Acquire() { while (test&set(value)); // while busy } Release() { value = 0; }
如果 value = 0 的时候 acquire，test&set 会返回 0 并把 value 设置成 1（拿到锁），循环退出。如果 value = 1 的时候 acquire，那么就一直循环，直到有人 release。

优点：
- 能正常接收中断
- 用户态可用
- 可以在多处理器上 work
缺点：
- 循环会消耗 CPU 运算资源
- 可能死锁（如果在等待的线程比持有锁的线程优先级高，那么锁就一直释放不出来）

更好的实现：只让 busy-wait 来原子化检查锁：

int guard = 0; // 小锁
int value = FREE; // 真正的锁

Acquire() {
    while (test&set(guard)); // short busy wait time
    if (value == BUSY) {
        put thread on wait queue;
        go to sleep() & guard = 0; // 要求这一步是原子的
    } else {
        value = BUSY;
        guard = 0;
    }
}

Release() {
    while (test&set(guard));
    if anyone on wait queue {
        take thread off wait queue;
        place on ready queue;
    } else {
        value = FREE;
    }
    guard = 0;
}

其实就很像关中断的那个实现，只不过把开关中断换成了一个 guard 变量。

0331 SYNC 4 读者写者

读者写者

期中必考

课上讲了用管程实现读者写者（写者优先）的一个例子。

约束：

读者只能在没有写者的时候访问数据库
写者只能在没有读者/写者的时候访问数据库
只有一个线程能操作状态变量。

状态变量：

AR, WR, AW, WW
条件变量 okToRead, okToWrite

读者代码：

Reader() {
  // check self into system
  acquire(&lock);
  while ((AW + WW) > 0) {
    // 没有写者，且没有等待的写者（写者优先）
    WR++;
    cond_wait(&okToRead, &lock); // sleep on condvar
    WR--;
  }
  AR++; // now active
  release(&lock);
  
  AccessDataBase(ReadOnly);
  
  acquire(&lock);
  AR--;
  if (AR == 0 && WR > 0) {
    cond_signal(&okToWrite); // wake up a waiting writer
  }
  release(&lock); 
}

写者代码：

Writer() {
  acquire(&lock);
  while ((AW + AR) > 0) {
    // not safe to write
    WW++;
    cond_wait(&okToWrite, &lock);
    WW--;
  }
  AW++;
  release(&lock);
  
  AccessDataBase(readAndWrite);
  
  acquire(&lock);
  AW--;
  if (WW > 0) {
    // 写者优先，优先唤醒写者
    cond_signal(&okToWrite);
  } else if (WR > 0) {
    cond_broadcast(&okToRead); // 这里唤醒**所有**读者，所以要用 broadcast
  }
}

辨析

读者会饥饿吗

会的，因为这个是写者优先，如果一直有写者来那么读者是会一直等待的
如果把读者退出代码的那个 if 删掉呢

也没问题，writer 会睡回去的，但是效率变差了
那把 signal 换成 broadcast 呢

也没问题，只有一个 writer 能写，效率变差而已。
只用一个条件变量 okToContinue 呢

可以，必须用 broadcast，因为无法保证唤醒的是读者还是写者，有可能会永远醒不来。

OSDI 06 The Chubby Lock

0402 Schedule 1

调度的三个 objective：

最小化完成时间
最大化吞吐量
“公平”

四类调度算法：

FCFS：最简单的队列策略，先处理先到的
Round Robin：每个 ready process 最多运行一个固定时间片 quantum $q$ 。如果时间片用完还没结束，就被抢占，并放回 ready queue 队尾。相当于使用了 timer interrupt。核心在于抢占。

但是不考虑任务长短，且上下文开销更大，quantum 太小也不行，平均完成时间不一定优于 FCFS。
Strictly Priority Scheduling：维护多个优先级队列，优先处理高优先级的。

问题：1. 饥饿 2. 优先级逆转，即低优先级持锁，which 高优先级在等待。一般可能需要一些动态优先级设计。
SJF：short jobs first，可以减少平均完成时间，但是难预测这个，而且长任务可能饥饿。
SRTF：short remaining time first，始终运行剩余时间最短的 job。如果一个新 job 到来，并且它的总运行时间小于当前 job 的剩余时间，则立即抢占当前 job。

问题：

RR 一定比 FCFS 更优吗？

不是的，只是能避免短任务长期被卡住，但所有任务时间相同的话 RR 的平均完成时间是劣于 FCFS 的。
RR 的 quantum 时间越小越好吗？举出三个例子：
- $T_1=10,T_2=1$ ， $q=10$ 劣于 $q=1$ ；
- $T_1=1,T_2=1$ ， $q=10$ 和 $q=1$ 一样；
- $T_1=1,T_2=1$ ， $q=1$ 劣于 $q=0.5$ ；
所以都是不一定的

0407 Schedule 2

Adaptive Scheduling

对于 SRTF，有个很关键的问题在于无法预测任务时间，所以可以使用 adaptive scheduling，根据之前观测到的 CPU burst 时间来预计之后的 CPU burst 时间。标准指数平均：

\tau_n = \alpha t_{n-1}+ (1-\alpha)\tau_{n-1}

Lottery Scheduling

给每个任务发 tickets，每个时间片抽一张来调度。

这样可以表达 priority，同时可以避免严格 starvation。

但是如果需要硬实时/low latency 的话不适合，且公平是统计意义上的。

MLFQ

multi-level feedback queue

维护多个队列，每个对应不同优先级。

高优先级队列对应更低 quantum，用于前台/交互性任务
低优先级队列对应更高 quantum，甚至 FCFS，用于后台/CPU bound 的任务
每个队列用自己的调度算法

关键在于 feedback：任务优先级会动态调整。

新任务从最高优先级开始
若其用完了 quantum，说明可能是 CPU-bound，降级
若没用完就阻塞了（例如去 I/O）了，说明可能是 interactive / I/O bound，升级或者保持

其近似 SRTF，但是根据行为推断 CPU burst 时间，近似满足了短 CPU burst 任务优先。

但是，用户可以通过行为欺骗，比如插入大量 printf 来 I/O 显得自己像 interactive task，保持高优先级。

所以说问题很复杂，对于一些 sleep 很久然后 compute 很久的，或者是对 deadline 敏感的，或者必须周期性运行的，当多种现实情况混合起来，调度是很复杂的，光看短 burst 优先是不够的。

多核调度

倾向于在各自核上维护调度数据结构
Affinity Scheduling，CPU 倾向于把调度过的线程重新调度到同一个核上，利用局部性（cache）

自旋锁：

int value = 0;

Acquire() {
  while (test&set(&value)) ;
}

Release() {
  value = 0;
}

这种锁不会让线程休眠，而是在用户态/内核态 busy wait。

如果等待时间短，spinlock 可能更好，比如多核程序的 barrier，这种情况 sleep/wakeup 开销可能反而更大。

Cache ping-pong 问题：多核情况下，每次 test&set 都是写操作，会导致锁变量在多个 core cache 之间来回失效并迁移，所以推荐用 test-and-test-and-set：

Acquire() {
  do {
    while (value);
  } while (test&set(&value));
}

Gang Scheduling：多个线程一起工作时最好一起被调度，感觉这个是显然的。

一般而言，调度的单位是线程。考虑线程/进程切换需要切换的上下文。

实时调度

关心的是能否在 ddl 前完成，而非平均跑得多快。

硬实时：

ddl miss 可能有严重后果
尽可能满足所有 ddl
最好在运行前就判断能否满足
常见算法：EDF (earliest ddl first), RMS (rate-monotonic scheduling), DM (ddl monotonic scheduling)
像 RR 就只能满足公平，但是不保证 ddl

软实时：

ddl miss 可能影响体验
主要是多媒体场景：视频播放，游戏渲染等
Constant Bandwith Server

EDF

所有 active tasks 中，选择 absolute ddl 最近的任务运行。周期性任务的话， $D_i^{t+1} = P_i + D_{i}^{t}$

判断能否满足的条件：

\sum_{i=1}^n \frac{C_i}{D_i}\le 1

饥饿

LCFS 可能饥饿，FCFS 如果遇到不 yield CPU 的后续也会饥饿。RR 一般不太会饥饿，但不一定在吞吐量意义下公平。

Priority Scheduling 会饥饿，高优先级会压制低优先级。更严重的是 priority inversion。

SRTF 和 MLFQ 也可能导致长任务饥饿。

Priority 只是手段，不是目标，所以现在的真实调度器逐渐从严格优先级走向更公平更可控。

O(1) Scheduler

140 个优先级：

0-99：real-time 或者 kernel 任务
100-139：用户任务，由 nice 值影响。

$O(1)$ 指调度操作时间不随任务数量增长，用 bit mask 表示哪些优先级非空。

有两个队列集合：active 和 expired。任务用完时间片后进入 expired，当 active 空了之后和 expired 交换。

有很多 ad-hoc heuristics。

Linux CFS (Completely Fair Scheduler)

跟踪每个线程已经获得的 CPU 时间，每次选择获得 CPU 最少的线程运行。使用红黑树来维护。

Target latency 和 minimum granularity：最小反应时间窗口以及每个任务最少运行的时间。

也支持 proportional share 来调整大家获得的 CPU 时间的权重。

总结

你关心什么	适合选择
CPU throughput	FCFS
平均完成时间	SRTF approximation
I/O throughput	SRTF approximation
CPU time fairness	Linux CFS
等待 CPU 的公平性	Round Robin
meeting deadlines	EDF
favoring important tasks	Priority Scheduling

算法	核心思想	优点	缺点	适合场景
FCFS	先来先服务	简单、吞吐好、切换少	队头阻塞、响应差	batch compute
RR	时间片轮转	waiting-time 公平、响应好	切换开销、平均完成时间不一定好	time-sharing
Priority	高优先级先跑	表达任务重要性	starvation、priority inversion	重要任务优先
SJF/SRTF	短任务/剩余时间最短优先	平均完成时间最优	需要预测未来、不公平	理论基准、近似策略
Lottery	按 ticket 随机调度	比例公平、避免绝对 starvation	短期不稳定	proportional share
MLFQ	多级反馈队列	自动识别 interactive / CPU-bound，近似 SRTF	heuristic、可被欺骗、可能 starvation	通用 OS
EDF	deadline 最近先跑	实时 deadline-aware	需要任务参数，overload 敏感	real-time
Linux O(1)	多优先级队列 + active/expired	调度快，工程高效	heuristic 多，公平模型弱	旧 Linux
Linux CFS	最小 vruntime / 公平 CPU share	原则清晰，公平，交互性自然	非硬实时，复杂度 (O(\log N))	现代通用 Linux

Schedule 3

死锁的四个条件（缺一不可）：

mutual exclusion
hold and wait
no preemption
circular wait

笔记 > 本科课程

#笔记 #本科课程 #OS

操作系统（实验班）预习笔记

https://blog.imyangty.com/note-os/

Author

YangTY

Posted on

December 14, 2025

Licensed under

强化学习紧急预习 Previous

倒腾日记 Next