CSCI3150 L14 条件变量

课程：CSCI3150 Introduction to Operating Systems · 2022未核 本讲：L14 条件变量，第 2 部分 / 共 2 部分 · 原件 L14-锁与条件变量-2022未核.pptx（本地课件） · PDF页码副本（本地课件） p.20–52 定位：用共享谓词记住事实，用条件变量让尚不能继续的线程睡眠等待。 前后：前接 锁实现；后接 L15 信号量。

逐页伴读

p.20为Part II标题。

p.21–23：互斥之外，还需要先后关系

p.21 There are many cases where a thread wishes to check whether a condition is true before continuing its execution.

Example:

A parent thread might wish to check whether a child thread has completed.

This is often called a join().

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

1   void *child(void *arg) {
2       printf("child\n");
3       // XXX how to indicate we are done?
4       return NULL;
5   }
6
7   int main(int argc, char *argv[]) {
8       printf("parent: begin\n");
9       pthread_t c;
10      Pthread_create(&c, NULL, child, NULL); // create child
11      // XXX how to wait for child?
12      printf("parent: end\n");
13      return 0;
14  }

p.23 Parent waiting fore child: Spin-based Approach

p.23 This is hugely inefficient as the parent spins and wastes CPU time.

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

1   volatile int done = 0;
2
3   void *child(void *arg) {
4       printf("child\n");
5       done = 1;
6       return NULL;
7   }
8
9   int main(int argc, char *argv[]) {
10      printf("parent: begin\n");
11      pthread_t c;
12      Pthread_create(&c, NULL, child, NULL); // create child
13      while (done == 0)
14          ; // spin
15      printf("parent: end\n");
16      return 0;
17  }

原例希望输出严格为 parent: begin、child、parent: end。仅创建child不足以保证最后一行等到它完成；父线程不断轮询done会浪费CPU，普通 volatile也不能代替同步。需要一份持久状态done和等待机制。

p.24–26：wait的三个环节缺一不可

p.24 Condition variables are useful when some kind of signaling must take place between threads.

pthread_cond_wait:

Put the calling thread to sleep on a queue.

Wait for some other thread to signal it.

pthread_cond_signal:

Unblock at least one of the threads that are blocked on the condition variable

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

int pthread_cond_wait(pthread_cond_t *cond,
                       pthread_mutex_t *mutex);
int pthread_cond_signal(pthread_cond_t *cond);

p.25 A thread calling wait routine:

The wait call releases the lock when putting said caller to sleep.

Before returning after being woken, the wait call re-acquires the lock.

A thread calling signal routine:

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

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t init = PTHREAD_COND_INITIALIZER;

pthread_mutex_lock(&lock);
while (initialized == 0)
    pthread_cond_wait(&init, &lock);
pthread_mutex_unlock(&lock);

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

pthread_mutex_lock(&lock);
initialized = 1;
pthread_cond_signal(&init);
pthread_mutex_unlock(&lock);

p.26 The waiting thread re-checks the condition in a while loop, instead of a simple if statement.

Without rechecking, the waiting thread will continue thinking that the condition has changed even though it has not (the condition can be changed before an awakened thread returns from pthread_cond_wait()).

pthread_cond_wait(&c,&m) 在持锁调用时，原子地释放m并进入等待；醒来后先重新取得m才返回。它不是“抱着锁睡觉”。调用方应在 while(!predicate) 内wait，返回后重新检查谓词，因为其他线程可能先拿走资源，也可能发生无需对应signal的唤醒。

signal只是通知等待者有机会重新检查，既不转移mutex所有权，也不存储一个永久事件。

p.27–29：done使两种执行顺序都成立

p.27 Parent waiting for Child: Use a condition variable

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

1   int done = 0;
2   pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
3   pthread_cond_t c = PTHREAD_COND_INITIALIZER;
4
5   void thr_exit() {
6       Pthread_mutex_lock(&m);
7       done = 1;
8       Pthread_cond_signal(&c);
9       Pthread_mutex_unlock(&m);
10  }
11
12  void *child(void *arg) {
13      printf("child\n");
14      thr_exit();
15      return NULL;
16  }
17
18  void thr_join() {
19      Pthread_mutex_lock(&m);
20      while (done == 0)
21          Pthread_cond_wait(&c, &m);
22      Pthread_mutex_unlock(&m);
23  }
24

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

(cont.)
25  int main(int argc, char *argv[]) {
26      printf("parent: begin\n");
27      pthread_t p;
28      Pthread_create(&p, NULL, child, NULL);
29      thr_join();
30      printf("parent: end\n");
31      return 0;
32  }

p.29 Parent:

Create the child thread and continues running itself.

Call into thr_join() to wait for the child thread to complete.

Acquire the lock

Check if the child is done

Put itself to sleep by calling wait()

Release the lock

Child:

Print the message “child”

Call thr_exit() to wake the parent thread

Grab the lock

Set the state variable done

Signal the parent thus waking it.

原代码child在锁m内设置done=1并signal；parent在同一锁内循环检查done，若为0则wait。若parent先来，它释放锁睡眠，child可以取得锁更新并唤醒。若child先完成，done已是1，parent根本不wait。两条路径都形成目标打印顺序。

p.29把“睡眠、释放锁”列为两行只是说明；真正接口要保证它们与通知者的同步不可出现丢失通知的间隙。

补充：done是事实，signal只是提醒。 可以把done理解为一块由锁保护的告示牌，写上“孩子已完成”后会一直保留；signal只是提醒当前等待者再看牌。若没人正在等，提醒可以消失，但事实仍在，所以后来到达的parent看见done=1就不必睡。

正确顺序的要点不在于“signal一定要让谁马上跑”，而在于parent持锁检查done与释放锁进入等待之间不能让child插入一个无法被观察到的完成。cond_wait把释放与等待协调起来；返回前又拿回锁，保证重新读取谓词时和修改者遵守同一协议。拿着锁普通sleep则会阻止child写done；先手工解锁再普通sleep则可能错过完成，两个看似相近的替代都不成立。

补充：课件的 thr_join 等到哪一步？ child 的实际顺序是 printf → thr_exit → return NULL。thr_exit 内又是 lock → done=1 → signal → unlock。parent 的 thr_join 可以在 child 解锁后就取得 m、看见 done=1 并返回；此时 child 可能还没有从 thr_exit 返回，更没有执行最后的 return NULL。

这已经足以保证课件要求的三行打印顺序，因为 child 的打印发生在 done=1 之前；但它不是 pthread_join 的完整替代，也不负责回收 joinable 线程资源。这里 done 的确切含义应读作“课件指定的工作点已经到达”。若主线程还需要确认 child 整个函数已结束、或随后要销毁 child 仍可能使用的资源，就需要真正的线程结束与回收协议。不能只因为自定义函数名字叫 join，就给它附加代码没有实现的保证。

p.30–31：有通知没状态、有状态没锁都不够

p.30 Imagine the case where the child runs immediately.

The child will signal, but there is no thread asleep on the condition.

When the parent runs, it will call wait and be stuck.

No thread will ever wake it.

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

1   void thr_exit() {
2       Pthread_mutex_lock(&m);
3       Pthread_cond_signal(&c);
4       Pthread_mutex_unlock(&m);
5   }
6
7   void thr_join() {
8       Pthread_mutex_lock(&m);
9       Pthread_cond_wait(&c, &m);
10      Pthread_mutex_unlock(&m);
11  }

p.30 thr_exit() and thr_join() without variable done

p.31 The issue here is a subtle race condition.

The parent calls thr_join().

The parent checks the value of done.

It will see that it is 0 and try to go to sleep.

Just before it calls wait to go to sleep, the parent is interrupted and the child runs.

The child changes the state variable done to 1 and signals.

But no thread is waiting and thus no thread is woken.

When the parent runs again, it sleeps forever.

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

1   void thr_exit() {
2       done = 1;
3       Pthread_cond_signal(&c);
4   }
5
6   void thr_join() {
7       if (done == 0)
8           Pthread_cond_wait(&c);
9   }

删done后，child先signal但当时无人等待，parent后来的wait会永久睡下。删mutex后，即便保留done，也可能parent读0→切到child写1并signal→parent才开始wait，仍错过通知。共享谓词、保护它的锁、wait原子释放入队一起才封住这条缝隙。

p.32–34：有界缓冲区的两个谓词

p.32 The Producer / Consumer (Bound Buffer) Problem

p.32 Producer

Produce data items

Wish to place data items in a buffer

Consumer

Grab data items out of the buffer consume them in some way

Example: Multi-threaded web server

A producer puts HTTP requests in to a work queue

Consumer threads take requests out of this queue and process them

p.33 A bounded buffer is used when you pipe the output of one program into another.

Example: grep foo file.txt | wc –l

The grep process is the producer.

The wc process is the consumer.

Between them is an in-kernel bounded buffer.

Bounded buffer is Shared resource  Synchronized access is required.

p.34 Only put data into the buffer when count is zero.

i.e., when the buffer is empty.

Only get data from the buffer when count is one.

i.e., when the buffer is full.

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

1   int buffer;
2   int count = 0;  // initially, empty
3
4   void put(int value) {
5       assert(count == 0);
6       count = 1;
7       buffer = value;
8   }
9
10  int get() {
11      assert(count == 1);
12      count = 0;
13      return buffer;
14  }

管道 grep foo file.txt | wc -l 可视为生产者把字节写入内核缓冲，消费者取出。单槽原例有buffer与count，put要求count=0并置1，get要求count=1并置0。这些assert只是检查前提，不负责等前提成立，也不阻止并发。

p.35–37：一个CV加if为什么不可靠

p.35 Producer puts an integer into the shared buffer loops number of times.

Consumer gets the data out of that shared buffer.

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

1   void *producer(void *arg) {
2       int i;
3       int loops = (int) arg;
4       for (i = 0; i < loops; i++) {
5           put(i);
6       }
7   }
8
9   void *consumer(void *arg) {
10      int i;
11      while (1) {
12          int tmp = get();
13          printf("%d\n", tmp);
14      }
15  }

p.36 Producer/Consumer: Single CV and If Statement

p.36 A single condition variable cond and associated lock mutex

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

1   cond_t cond;
2   mutex_t mutex;
3
4   void *producer(void *arg) {
5       int i;
6       for (i = 0; i < loops; i++) {
7           Pthread_mutex_lock(&mutex);         // p1
8           if (count == 1)                 // p2
9               Pthread_cond_wait(&cond, &mutex);   // p3
10          put(i);                     // p4
11          Pthread_cond_signal(&cond);         // p5
12          Pthread_mutex_unlock(&mutex);       // p6
13      }
14  }
15
16  void *consumer(void *arg) {
17      int i;
18      for (i = 0; i < loops; i++) {
19          Pthread_mutex_lock(&mutex);         // c1

p.37 p1-p3: A producer waits for the buffer to be empty.

c1-c3: A consumer waits for the buffer to be full.

With just a single producer and a single consumer, the code works.

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

20          if (count == 0)                 // c2
21             Pthread_cond_wait(&cond, &mutex);    // c3
22          int tmp = get();                // c4
23          Pthread_cond_signal(&cond);         // c5
24          Pthread_mutex_unlock(&mutex);       // c6
25          printf("%d\n", tmp);
26      }
27  }

p.37 If we have more than one of producer and consumer?

原版本producer在满时wait、put后signal；consumer在空时wait、get后signal，都在mutex内。但等待只用if，醒来后直接操作。课件说单生产者单消费者情况下可工作，是其忽略虚假唤醒的教学模型；通用pthread代码仍应用while。

p.38–39：醒来的消费者被另一个抢先

图p.38的完整关键轨迹是：C1发现空并睡→P放入一项count=1、唤醒C1→P下一轮见满睡→C2先得锁取走，count=0，并通知P→C1终于返回wait，却跳过检查执行get，断言失败。被唤醒只代表ready，不代表立即运行。

旧PDF的p.38注释与p.39采用不一致的兼容图片；已回查原始PPTX正文层。p.39真正解释的是Mesa与Hoare语义：Mesa下被唤醒者不保证立即运行，期间缓冲可被C2改变，故醒来必须重查；Hoare语义提供被唤醒者立即运行的更强保证。课件以Mesa作为常见系统模型，不能把signal理解成直接移交CPU与条件。

表（p.38）：if 版本逐行状态。 R=运行，Q=就绪，S=睡眠；c1/p1 是加锁，c2/p2 检查，c3/p3 等待，c4/p4 取/放，c5/p5 通知，c6/p6 解锁。每行状态是该步之后；这些符号对应前面的完整程序。

最后一行在转换页底部排版溢出，已以原 PPTX 正文层补齐。C1 的错误是没重新检查 count，不是 C2“偷走了本应预留给 C1 的物品”：signal 从未预留物品。

p.40–41：改while能防错误消费，但还可能全睡

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

1   cond_t cond;
2   mutex_t mutex;
3
4   void *producer(void *arg) {
5       int i;
6       for (i = 0; i < loops; i++) {
7           Pthread_mutex_lock(&mutex);         // p1
8           while (count == 1)          // p2
9               Pthread_cond_wait(&cond, &mutex);   // p3
10          put(i);                     // p4
11          Pthread_cond_signal(&cond);         // p5
12          Pthread_mutex_unlock(&mutex);       // p6
13      }
14  }
15

p.41 A simple rule to remember with condition variables is to always use while loops.

However, this code still has a bug (next page).

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

(Cont.)
16  void *consumer(void *arg) {
17      int i;
18      for (i = 0; i < loops; i++) {
19          Pthread_mutex_lock(&mutex);         // c1
20          while (count == 0)          // c2
21              Pthread_cond_wait(&cond, &mutex);   // c3
22          int tmp = get();                // c4
23          Pthread_cond_signal(&cond);         // c5
24          Pthread_mutex_unlock(&mutex);       // c6
25          printf("%d\n", tmp);
26      }
27  }

while使C1在重新得锁后再次见count=0，于是继续睡，修复了越过谓词的问题。但producer和consumer都在同一个cond队列，signal不知道该叫哪一类线程。修好安全性并不代表确保前进。

p.42–43：唤醒同类导致没人能改变条件

p.43 A consumer should not wake other consumers, only producers, and vice-versa.

p.43 Thread Trace: Broken Solution (Version 2) (Cont.)

图中C1、C2均因空睡眠；P放一项并唤醒C1，随后因满睡眠。C1消费后应叫醒P，却可能signal到C2；C1下轮见空也睡；C2醒来重查仍空再睡。此刻count=0、P仍睡在“满”的旧等待中、两消费者也睡，所有人停止推进。循环检查没错，错在唤醒目标。

表（p.42–43）：while 加单一 CV 的完整失败轨迹。 沿用 R/Q/S 和程序行号；C1 与 C2 在同一 cond 上等待，所以消费后可能唤醒同类。

p.42 最后一行同样从原 PPTX 正文层恢复。P 的等待条件现在已满足，却没有收到合适通知；这正说明谓词的真假与线程是否已被唤醒是两件事。

p.44–45：两个CV分别等待两种状态

p.44 Use two condition variables and while

Producer threads wait on the condition empty, and signals fill.

Consumer threads wait on fill and signal empty.

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

1   cond_t empty, fill;
2   mutex_t mutex;
3
4   void *producer(void *arg) {
5       int i;
6       for (i = 0; i < loops; i++) {
7           Pthread_mutex_lock(&mutex);
8           while (count == 1)
9               Pthread_cond_wait(&empty, &mutex);
10          put(i);
11          Pthread_cond_signal(&fill);
12          Pthread_mutex_unlock(&mutex);
13      }
14  }
15

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

(Cont.)
16  void *consumer(void *arg) {
17      int i;
18      for (i = 0; i < loops; i++) {
19          Pthread_mutex_lock(&mutex);
20          while (count == 0)
21              Pthread_cond_wait(&fill, &mutex);
22          int tmp = get();
23          Pthread_cond_signal(&empty);
24          Pthread_mutex_unlock(&mutex);
25          printf("%d\n", tmp);
26      }
27  }

producer在empty上等待“不是满”，放入后signal fill；consumer在fill上等待“不是空”，取出后signal empty。两类等待共用同一mutex保护count与buffer。注意变量名empty表示一类等待通知，不是一个自动维护count的计数器。

补充：在原代码上逐行检查“谁现在持有 mutex”。 producer 到第 8 行检查 count 时持锁；若 count==1，wait 在进入等待时释放锁，否则消费者永远拿不到锁去取走数据。被唤醒后，wait 返回之前又取得同一把锁，所以第 8 行重新检查与第 10 行 put 之间不会被遵守协议的另一个修改者插入。consumer 一侧完全对称，检查的是 count==0。

signal 只是让某个等待者有机会继续竞争，并不把 mutex 直接送给它，也不替它预订缓冲区。producer 执行 signal 后仍持锁，直到 unlock；被叫醒的 consumer 之后还要重新拿锁、重新检查。while、mutex、分开的 empty/fill 各有职责：重新检查当前事实、保护检查到修改的区间、通知正确类别的等待者。少了任意一项，都不能用另外两项的名字替它担保。接口核验：pthread_cond_wait

p.46–48：多槽环形队列仍守同一不变量

p.46 More concurrency and efficiency  Add more buffer slots.

Allow concurrent production or consuming to take place.

Reduce context switches.

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

1   int buffer[MAX];
2   int fill = 0;
3   int use = 0;
4   int count = 0;
5
6   void put(int value) {
7       buffer[fill] = value;
8       fill = (fill + 1) % MAX;
9       count++;
10  }
11
12  int get() {
13      int tmp = buffer[use];
14      use = (use + 1) % MAX;
15      count--;
16      return tmp;
17  }

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

1   cond_t empty, full;
2   mutex_t mutex;
3
4   void *producer(void *arg) {
5       int i;
6       for (i = 0; i < loops; i++) {
7           Pthread_mutex_lock(&mutex);         // p1
8           while (count == MAX)            // p2
9               Pthread_cond_wait(&empty, &mutex);  // p3
10          put(i);                     // p4
11          Pthread_cond_signal(&full);         // p5
12          Pthread_mutex_unlock(&mutex);       // p6
13      }
14  }
15
16  void *consumer(void *arg) {
17      int i;
18      for (i = 0; i < loops; i++) {
19          Pthread_mutex_lock(&mutex);         // c1
20          while (count == 0)          // c2
21              Pthread_cond_wait(&full, &mutex);   // c3
22          int tmp = get();                // c4

p.48 p2: A producer only sleeps if all buffers are currently filled.

c2: A consumer only sleeps if all buffers are currently empty.

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

(Cont.)
23          Pthread_cond_signal(&empty);        // c5
24          Pthread_mutex_unlock(&mutex);       // c6
25          printf("%d\n", tmp);
26      }
27  }

课件最终put使用 buffer[fill]=value; fill=(fill+1)%MAX; count++;，get对应读取use位置、递增use并count--。producer仅在count==MAX等待，consumer仅在count==0等待；始终保持 $0\le count\le MAX$。

补充完整演算：MAX=3，初始fill=use=count=0；put10→(1,0,1)，put20→(2,0,2)，get得到10→(2,1,1)，put30→(0,1,2)，put40→(1,1,3)。此时fill==use却是满；初始二者也相等却是空，必须用count或等价状态区分。缓冲扩大允许生产消费阶段更灵活交错，但被同一mutex保护的单次put/get仍互斥。

p.49–51：不同等待者的条件不一样时用broadcast

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

1   // how many bytes of the heap are free?
2   int bytesLeft = MAX_HEAP_SIZE;
3
4   // need lock and condition too
5   cond_t c;
6   mutex_t m;
7
8   void *
9   allocate(int size) {
10      Pthread_mutex_lock(&m);
11      while (bytesLeft < size)
12          Pthread_cond_wait(&c, &m);
13      void *ptr = ...;        // get mem from heap
14      bytesLeft -= size;
15      Pthread_mutex_unlock(&m);
16      return ptr;
17  }
18
19  void free(void *ptr, int size) {
20      Pthread_mutex_lock(&m);
21      bytesLeft += size;
22      Pthread_cond_signal(&c);    // whom to signal??
23      Pthread_mutex_unlock(&m);
24  }

p.51 Solution (Suggested by Lampson and Redell)

Replace pthread_cond_signal() with pthread_cond_broadcast()

pthread_cond_broadcast()

Wake up all waiting threads.

Cost: too many threads might be woken.

Threads that shouldn’t be awake will simply wake up, re-check the condition, and then go back to sleep.

原题：空闲0 B，Ta要100 B、Tb要10 B，两者都睡；Tc释放50 B。若signal只唤醒Ta，它重查50<100再睡，而能继续的Tb仍睡。broadcast让所有等待者争锁重查：Ta仍等，Tb可扣10，剩40 B。

广播不把50 B同时承诺给所有线程，因为每个分配仍在锁内检查并扣减。代价是无资格者也被唤醒，产生额外调度。

补充：让有限生产者结束后，消费者也能退出。 原无限循环示例强调等待条件。若生产者终将停止，消费者除了“有数据”还需知道“以后不会再有数据”。可增加受同一mutex保护的关闭状态：缓冲为空且仍可能有生产者时等待；有数据时继续消费；缓冲为空且已关闭时结束。最后一个生产者更新关闭事实后通知可能仍在等的消费者。

不能仅由主线程destroy条件变量来“把大家叫醒”，销毁不是通知；也不能只signal一个消费者就假设所有等待者都会退出。如果多个消费者都等在空缓冲上，完成关闭时应让它们都有机会重查退出条件。此处给出生命周期推理，不把它冒充原课件已经提供的完整停机代码。

p.52：把三件事各归其位

mutex保护共享状态的原子更新；谓词记录“现在能否继续”；CV提供睡眠与通知。做题先写谓词与不变量，再安排while、wait和通知对象，不从机械背诵signal位置开始。

本讲核心考点

• [C] 说明wait原子释放锁、入队、醒来重新加锁的语义。
• [C] 分别构造无done、无锁、if、单CV四种失败轨迹。
• [C] 用双CV和while解释有界缓冲区正确性。
• [C] 跟踪环形fill/use/count，区分空和满。
• [C] 解出100 B与10 B等待者在释放50 B后的唤醒选择。

附录

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

来源与证据

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

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

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