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

Last updated on January 15, 2026 11:30 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 wait queue;
    } else {
        value = FREE;
    }
    guard = 0;
}

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

管程

信号量的问题：把约束和互斥一起进行了处理。

管程（monitor）：将约束和互斥进行解耦。一把锁以及若干条件变量。某些语言（Java）天生支持管程。

条件变量：a queue of threads waiting for something inside a critical section（注意信号量是不支持在临界区内 wait 的）

操作：

Wait(&lock)：自动释放锁然后睡眠，返回之前重新获取锁。
Signal()：唤醒其中一个等待中的线程（如果有）
Broadcase()：唤醒所有等待中的线程。

例子：

lock buf_lock;
condition buf_CV;
queue queue;

Producer(item) {
    acquire(&buf_lock);
    enqueue(&queue, item);
    cond_signal(&buf_CV); // signal any waiters
    release(&buf_lock);
}

Consumer() {
    acquire(&buf_lock);
    while (isEmpty(&queue)) {
        cond_wait(&buf_CV, &buf_lock); // if empty, sleep
    }
    item = dequeue(&queue);
    release(&buf_lock);
    return item;
}

为什么要用 while 而不是 if？因为大多数 OS 使用 Mesa 调度而不是 Hoare 调度，虽然后者更“符合语义”，但也更难以实现。

0318 SYNC 4 读者写者

期中必考

笔记 > 本科课程

#本科课程 #笔记 #OS

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

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

Author

YangTY

Posted on

December 14, 2025

Licensed under

强化学习紧急预习 Previous

倒腾日记 Next