CSCI3150 L14 锁的实现

课程：CSCI3150 Introduction to Operating Systems · 2022未核 本讲：L14 锁的实现，第 1 部分 / 共 2 部分 · 原件 L14-锁与条件变量-2022未核.pptx（本地课件） · PDF页码副本（本地课件） p.1–19 定位：从失败的普通标志位推导硬件原子操作，再比较自旋与睡眠。 前后：前接 线程API；后接 条件变量。

逐页伴读

p.1–3依次是讲题、课程位置与Part I标题。

p.4–6：锁状态与临界区

p.4 Ensure that any critical section executes as if it were a single atomic instruction.

An example: the canonical update of a shared variable

Add some code around the critical section

课件程序与接口（p.4，原页片段）

balance = balance + 1;

课件程序与接口（p.4，原页片段）

1    lock_t mutex; // some globally-allocated lock ‘mutex’
2    …
3    lock(&mutex);
4    balance = balance + 1;
5    unlock(&mutex);

p.5 Lock variable holds the state of the lock.

available (or unlocked or free)

No thread holds the lock.

acquired (or locked or held)

Exactly one thread holds the lock and presumably is in a critical section.

p.6 lock()

Try to acquire the lock.

If no other thread holds the lock, the thread will acquire the lock.

Enter the critical section.

This thread is said to be the owner of the lock.

Other threads are prevented from entering the critical section while the first thread that holds the lock is in there.

原例用lock和unlock包住 balance=balance+1。锁有free与held两种逻辑状态；一个线程成功取得后成为owner，其余遵守相同锁协议的线程不能同时进入。锁的意义是把一串访问作为整体保护，不是让这串机器指令物理上融合成一条。

p.7–9：三个评价标准分别回答三个问题

p.7 The name that the POSIX library uses for a lock.

Used to provide mutual exclusion between threads.

We may be using different locks to protect different variables  Increase concurrency (a more fine-grained approach).

课件程序与接口（p.7，原页片段）

1   pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
2
3   Pthread_mutex_lock(&lock); // wrapper for pthread_mutex_lock()
4   balance = balance + 1;
5   Pthread_mutex_unlock(&lock);

p.8 Efficient locks provided mutual exclusion at low cost.

Building a lock need some help from the hardware and the OS.

p.9 Mutual exclusion

Does the lock work, preventing multiple threads from entering a critical section?

Fairness

Does each thread contending for the lock get a fair shot at acquiring it once it is free? (Starvation)

Performance

The time overheads added by using the lock

pthread mutex提供互斥；不同互不相关的数据用不同锁可增加并发，但关联的不变量不能随意拆开保护。构造锁要问：是否确实只有一个线程进入（正确性），等待者是否可能饿死（公平性），获取、竞争与释放代价多大（性能）。正确不自动推出公平或快。

p.10–12：关中断和普通flag各在哪里失败

p.10 Disable Interrupts for critical sections

One of the earliest solutions used to provide mutual exclusion

Invented for single-processor systems.

Problem:

Require too much trust in applications

Greedy (or malicious) program could monopolize the processor.

Do not work on multiprocessors

Code that masks or unmasks interrupts be executed slowly by modern CPUs

课件程序与接口（p.10，原页片段）

void lock() {
     DisableInterrupts();
 }
 void unlock() {
     EnableInterrupts();
 }

p.11 First attempt: Using a flag denoting whether the lock is held or not.

The code below has problems.

课件程序与接口（p.11，原页片段）

typedef struct __lock_t { int flag; } lock_t;

 void init(lock_t *mutex) {
    // 0  lock is available, 1  held
    mutex->flag = 0;
 }

 void lock(lock_t *mutex) {
    while (mutex->flag == 1)  // TEST the flag
        ;  // spin-wait (do nothing)
    mutex->flag = 1;  // now SET it !
 }

 void unlock(lock_t *mutex) {
    mutex->flag = 0;
 }

p.12 Problem 1: No Mutual Exclusion (assume flag=0 to begin)

Problem 2: Spin-waiting wastes time waiting for another thread

So, we need an atomic instruction supported by Hardware!

test-and-set instruction, also known as atomic exchange

课件程序与接口（p.12，原页片段）

call lock()
while (flag == 1)
interrupt: switch to Thread 2

课件程序与接口（p.12，原页片段）

call lock()
while (flag == 1)
flag = 1;
interrupt: switch to Thread 1

课件程序与接口（p.12，原页片段）

flag = 1; // set flag to 1 (too!)

关闭本CPU中断在早期单处理器内核场景可防某些抢占，但不能停止另一CPU访问共享数据，也不能给普通应用任意长期关中断的权力。

课件错误实现是 while(flag==1) ; flag=1;。题设flag初值0；T1检查为0后切换，T2也检查为0，T2写1并进入，随后T1写1也进入。即使每次单独读写flag都不可分割，检查与占有之间仍有缝隙。这就是需要原子read-modify-write的原因。该教学交错之外，真实语言内存模型也要求使用合适原子或同步原语。

p.13–15：TestAndSet把检查和占有合成一个动作

p.13 An instruction to support the creation of simple locks

return(testing) old value pointed to by the ptr.

Simultaneously update(setting) said value to new.

This sequence of operations is performed atomically.

课件程序与接口（p.13，原页片段）

int TestAndSet(int *ptr, int new) {
    int old = *ptr; // fetch old value at ptr
    *ptr = new; // store ‘new’ into ptr
    return old; // return the old value
 }

p.14 Note: To work correctly on a single processor, it requires a preemptive scheduler.

课件程序与接口（p.14，原页片段）

typedef struct __lock_t {
    int flag;
 } lock_t;

 void init(lock_t *lock) {
    // 0 indicates that lock is available,
    // 1 that it is held
    lock->flag = 0;
 }

 void lock(lock_t *lock) {
    while (TestAndSet(&lock->flag, 1) == 1)
        ;   // spin-wait
 }

 void unlock(lock_t *lock) {
    lock->flag = 0;
 }

p.15 Correctness: yes

The spin lock only allows a single thread to enter the critical section.

Fairness: no

Spin locks don’t provide any fairness guarantees.

Indeed, a thread spinning may spin forever.

Performance:

In a single CPU, performance overheads can be quire painful.

If the number of threads roughly equals the number of CPUs, spin locks work reasonably well.

课件定义TestAndSet原子地读取旧值、写入new并返回旧值。以下是原机制的精简表达，不是可用普通C赋值实现原子性的保证：

lock:   while TestAndSet(flag,1) == 1: retry
unlock: flag = 0

初值0时，第一个操作返回0且写1，所以获锁；后来的操作返回1，继续等待。释放后某个竞争者再次读到旧0获锁。单CPU需允许调度到持有者，否则等待者永远自旋而持有者无法解锁。该锁无FIFO保证，一个线程可能多次被别人抢先。

补充：为什么测试并设置必须是一个硬件动作。 按p.13的约定，TestAndSet同时返回旧值并写1。初始flag=0时，即使T1/T2几乎同时调用，硬件也使它们具有某种先后：排第一者读旧0并写1，第二者读到的是已经变成1的值。胜者进入的理由是“我拿到旧0”，不是“现在flag为1”，因为失败者此刻看见的flag同样为1。

真实语言实现还须用满足同步要求的原子操作及获取/释放顺序，使临界区数据对后续持锁者可见。仅仅用一个名字叫TestAndSet的普通C函数包住读取和写入，不会让它获得硬件原子性。

p.16–17：yield只退到ready，不等于睡到解锁

p.16 Hardware-based spin locks are simple and they work.

In some cases, these solutions can be quite inefficient.

Any time a thread gets caught spinning, it wastes an entire time slice doing nothing but checking a value.

p.17 When you are going to spin, give up the CPU to another thread.

OS system call moves the caller from the running state to the ready state.

The cost of a context switch can be substantial and the starvation problem still exists.

课件程序与接口（p.17，原页片段）

void init() {
     flag = 0;
 }

 void lock() {
     while (TestAndSet(&flag, 1) == 1)
         yield(); // give up the CPU
 }

 void unlock() {
     flag = 0;
 }

自旋占用CPU重复检查。失败后yield使线程从running回到ready，调度器可能运行持有者，也可能很快又选到竞争者，因此减少某些忙等却增加上下文切换，仍不能保证公平。把yield误认成“已经排队等待特定锁释放”会误判程序行为。

p.18–19：等待队列与两阶段锁

p.18 Queue to keep track of which threads are waiting to enter the lock.

park()

Put a calling thread to sleep

unpark(threadID)

Wake a particular thread as designated by threadID.

p.19 A two-phase lock realizes that spinning can be useful if the lock is about to be released.

First phase

The lock spins for a while, hoping that it can acquire the lock.

If the lock is not acquired during the first spin phase, a second phase is entered,

Second phase

The caller is put to sleep.

The caller is only woken up when the lock becomes free later.

park让当前线程睡眠，unpark唤醒指定线程；锁维护队列，释放者找到等待者。补充实现注意：检查锁、入队和睡眠必须协调，不能让unpark发生在尚未park的空档而丢失唤醒。

两阶段锁先短暂自旋，预计持有者很快释放时省去睡眠切换；超过阈值再睡眠。选择与临界区长度、CPU数量和调度情况有关，不是固定“自旋总快”或“睡眠总快”。

补充：把丢失唤醒的空档画成四步。 T1 发现锁忙，决定睡眠；T2 释放锁并通知 T1；T1 此时尚未真正进入睡眠；T1 接着睡下。如果通知不被记住、又没有协调入队与睡眠，锁已经空闲，却可能再没有线程负责叫醒 T1。这是“等待条件已满足但等待者睡过去”的问题，不是互斥失败。

解决要求是协议上的：等待者准备睡眠与释放者的通知之间必须有正确的交接，或通知能以许可/令牌形式可靠保留。仅仅把“检查锁”那一行做成原子指令，不能自动使后续入队和睡眠也成为不可分割的整体。本页只列 park/unpark 的用途，没有给出一套可以直接照抄的完整实现；下一部分条件变量把释放互斥锁和进入等待作为一个协调操作，正好回应这一缺口。

本讲核心考点

• [C] 对普通flag构造两个线程同时进入的反例。
• [C] 追踪TestAndSet返回旧值与写入新值。
• [C] 按正确性、公平性、性能评价自旋锁。
• [C] 区分yield回ready、park睡眠与两阶段等待。

附录

本份没有需要移至附录的长推导；计算过程已在对应页正文写全。

来源与证据

• 原件：L14-锁与条件变量-2022未核.pptx（本地课件）；PDF副本（本地课件） p.1–19。本文页码均为 PDF 页号。

• 考试证据：读了 课程大纲-2026T1.pdf、教学计划-2026T1.pdf、T08-期中参考-2025T2-题目-解答.pdf、T07-多级反馈队列-2025T2.pdf（p.13–15内嵌历史试题）；未识别用途的 PDF：无

• 2026-10-13 内容补全：保留原页顺序与版本，补入对应页的程序、接口、字段、条件和演算；原程序片段保留课件行号、拼写与省略处，不能据此视为经过编译的完整软件。本文已有运行记录属于其标注日期，本次未重新运行课程容器或提交作业。