CSCI3150 L15 信号量

课程：CSCI3150 Introduction to Operating Systems · 2022未核 本讲：L15 信号量，第 1 部分 / 共 2 部分 · 原件 L15-信号量与常见并发问题-2022未核.pptx（本地课件） · PDF页码副本（本地课件） p.1–30 定位：用许可数量同时表达互斥与资源等待，检查初始化值和获取次序。 前后：前接 条件变量；后接 并发故障。

逐页伴读

p.1–3为讲题、课程位置和Part I标题。

p.4–6：许可可以被记住

p.4 An object with an integer value

We can manipulate with two routines; sem_wait() and sem_post().

Initialization

Declare a semaphore s and initialize it to the value 1

The second argument, 0, indicates that the semaphore is shared between threads in the same process.

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

#include <semaphore.h>
 sem_t s;
 sem_init(&s, 0, 1); // initialize s to the value 1

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

sem_wait()

When sem_wait()is called,
Decrement the value of semaphore s by one
If the value of the semaphore
0 or higher, return right away;
otherwise (lower than 0), the caller will be suspended  and wait for a subsequent post.
When negative, the value of the semaphore is equal to the number of waiting threads.

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

1  int sem_wait(sem_t *s) {
2   decrement the value of semaphore s by one
3       wait if value of semaphore s is negative
4  }

p.6 sem_post()

Simply increments the value of the semaphore.

If there is a thread waiting to be woken, wakes one of them up.

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

1  int sem_post(sem_t *s) {
2       increment the value of semaphore s by one
3       if there are one or more threads waiting, wake one
4  }

sem_init(&s,0,1) 的0表示进程内线程共享，1是初始许可数。wait取得许可，许可不足时阻塞；post归还或发布许可并可能唤醒一个等待者。与条件变量signal不同，先post再wait也能消费保存下来的许可。

课件前半用“先减，负则睡”的抽象：值为-2表示两个等待者，严格说等待人数是负值的绝对值。不能据此假定每个平台读取出的信号量值一定为负；本讲末尾还会给非负计数实现。wait/post内部的检查、计数和排队必须有原子性，不能用两句无保护普通整数运算替代。

p.7–9：作为锁时，初值为什么是1

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

1   sem_t m;
2   sem_init(&m, 0, X); // initialize semaphore to X; what should X be?
3
4   sem_wait(&m);
5   //critical section here
6   sem_post(&m);

p.8 Thread Trace: Single Thread Using A Semaphore

原题 sem_init(&m,0,X); sem_wait(&m); critical; sem_post(&m); 要互斥，X应为1。0会使第一个线程就等待，2会允许两个线程进入。

单线程轨迹1→wait→0→临界区→post→1。双线程图：T0取得后值0；T1 wait减到-1并睡；T0 post到0唤醒T1；T1原来的wait随后返回并进入，不能再次扣一次许可；T1 post恢复1。负值是当前采用的教学计数约定。

表（p.8）：课件完整字段与状态。 下表保留原页术语和数值；读写轨迹的同一格按原页由上到下排列，空格以“—”表示。

表（p.9）：课件完整字段与状态。 下表保留原页术语和数值；读写轨迹的同一格按原页由上到下排列，空格以“—”表示。

p.10–12：作为一次完成事件时，初值是0

p.10 What should X be?

The value of semaphore should be set to is 0.

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

1   sem_t s;
2
3   void *
4   child(void *arg) {
5       printf("child\n");
6       sem_post(&s); // signal here: child is done
7       return NULL;
8   }
9
10   int
11   main(int argc, char *argv[]) {
12      sem_init(&s, 0, X); // what should X be?
13      printf("parent: begin\n");
14      pthread_t c;
15      pthread_create(c, NULL, child, NULL);
16      sem_wait(&s); // wait here for child
17  printf("parent: end\n");
18      return 0;
19   }

p.11 Thread Trace: Parent Waiting For Child (Case 1)

p.11 The parent call sem_wait() before the child has called sem_post().

p.12 Thread Trace: Parent Waiting For Child (Case 2)

p.12 The child runs to completion before the parent call sem_wait().

原例要保证parent begin→child→parent end，child打印后post，parent创建后wait，X取0。parent先wait则0→-1睡，child post到0唤醒；child先post则0→1，parent后来wait扣到0立即返回。两种顺序都不会丢失完成事件。

p.10的 pthread_create(c,...) 缺少接收线程标识所需的 &c，照抄前应校正。这里是一次性事件示范；多个等待者、重复轮次和资源回收还需明确协议。

表（p.11）：课件完整字段与状态。 下表保留原页术语和数值；读写轨迹的同一格按原页由上到下排列，空格以“—”表示。

表（p.12）：课件完整字段与状态。 下表保留原页术语和数值；读写轨迹的同一格按原页由上到下排列，空格以“—”表示。

补充：post 保存一次许可，但不替代完整的线程结束等待。 child 在 sem_post(&s) 后还有 return NULL。parent 的 wait 成功，证明打印 child 和发布许可已经发生；不能证明 child 已经执行最后的返回，更不能据此假设 joinable 线程资源自动被回收。若把例子改成长期运行程序，应对成功创建的线程安排真正的 join 或其他合法回收方式。

这一份许可也只能让一次成功 wait 通过。若两个 parent 各等一次、child 只 post 一次，就会有一个等待者继续等；若一轮开始前误留了一份旧许可，新一轮 parent 可能过早通过。初值 0 的含义是“尚未发生本轮完成事件”，所以重复使用时必须先设计轮次与发布次数，不能只靠变量名把它当作广播条件。

p.13–15：空槽和满槽计数不能保护索引

p.13 The Producer/Consumer (Bounded-Buffer) Problem

p.13 Producer: put() interface

Wait for a buffer to become empty in order to put data into it.

Consumer: get() interface

Wait for a buffer to become filled before using it.

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

1   int buffer[MAX];
2   int fill = 0;
3   int use = 0;
4
5   void put(int value) {
6       buffer[fill] = value;   // line f1
7       fill = (fill + 1) % MAX;    // line f2
8   }
9
10  int get() {
11      int tmp = buffer[use];  // line g1
12      use = (use + 1) % MAX;  // line g2
13      return tmp;
14  }

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

1    sem_t empty;
2    sem_t full;
3
4    void *producer(void *arg) {
5       int i;
6       for (i = 0; i < loops; i++) {
7           sem_wait(&empty);   // line P1
8           put(i);             // line P2
9           sem_post(&full);        // line P3
10      }
11   }
12
13   void *consumer(void *arg) {
14      int i, tmp = 0;
15      while (tmp != -1) {
16          sem_wait(&full);        // line C1
17          tmp = get();        // line C2
18          sem_post(&empty);   // line C3
19          printf("%d\n", tmp);
20      }
  }
  …

p.14 First Attempt: Adding the Full and Empty Conditions

p.15 Imagine that MAX is greater than 1 .

If there are multiple producers, race condition can happen at line f1.

It means that the old data there is overwritten.

We’ve forgotten here is mutual exclusion.

The filling of a buffer and incrementing of the index into the buffer is a critical section.

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

int main(int argc, char *argv[]) {
      // …
      sem_init(&empty, 0, MAX);     // MAX buffers are empty to begin with…
      sem_init(&full, 0, 0);    // … and 0 are full
      // …
  }

p.15 First Attempt: Adding the Full and Empty Conditions (Cont.)

原环形队列put写buffer[fill]并令fill取模前进；get同样维护use。初始empty=MAX、full=0；producer先wait(empty)、put、post(full)，consumer相反。

当MAX>1且有多个producer时，两个线程可各取得一个空槽许可，却同时读到相同fill，于是覆盖同一位置。计数确保总容量约束，不确保修改fill、use和槽位时互斥；还需初值1的mutex。

p.16–18：拿着mutex等资源会锁死帮助者

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

1   sem_t empty;
2   sem_t full;
3   sem_t mutex;
4
5   void *producer(void *arg) {
6       int i;
7       for (i = 0; i < loops; i++) {
8           sem_wait(&mutex);   // line p0 (NEW LINE)
9           sem_wait(&empty);   // line p1
10          put(i);             // line p2
11          sem_post(&full);        // line p3
12          sem_post(&mutex);   // line p4 (NEW LINE)
13      }
14  }
15
(Cont.)

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

(Cont.)
16  void *consumer(void *arg) {
17      int i;
18      for (i = 0; i < loops; i++) {
19          sem_wait(&mutex);   // line c0 (NEW LINE)
20          sem_wait(&full);        // line c1
        int tmp = get();        // line c2
22          sem_post(&empty);   // line c3
23          sem_post(&mutex);   // line c4 (NEW LINE)
24          printf("%d\n", tmp);
25      }
26  }

p.18 Imagine two thread: one producer and one consumer.

The consumer acquire the mutex (line c0).

The consumer calls sem_wait() on the full semaphore (line c1).

The consumer is blocked and yield the CPU.

The consumer still holds the mutex!

The producer calls sem_wait() on the binary mutex semaphore (line p0).

The producer is now stuck waiting too – A classic deadlock.

错误版本consumer先wait(mutex)再wait(full)。初始队列空，consumer持mutex睡在full；producer想取得mutex才能put和post(full)，也睡下。一个等数据，一个等被前者占有的锁，形成死锁。这不是把信号量初值随便调大能修的。

p.19–20：先预留资源，再短暂保护共享结构

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

1   sem_t empty;
2   sem_t full;
3   sem_t mutex;
4
5   void *producer(void *arg) {
6       int i;
7   for (i = 0; i < loops; i++) {
8           sem_wait(&empty);   // line p1
9           sem_wait(&mutex);   // line p1.5 (MOVED MUTEX HERE…)
10          put(i);             // line p2
11          sem_post(&mutex);   // line p2.5 (… AND HERE)
12          sem_post(&full);        // line p3
13      }
14   }
15
(Cont.)

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

(Cont.)
16   void *consumer(void *arg) {
17      int i;
18      for (i = 0; i < loops; i++) {
19          sem_wait(&full);        // line c1
20          sem_wait(&mutex);   // line c1.5 (MOVED MUTEX HERE…)
21          int tmp = get();        // line c2
22          sem_post(&mutex);   // line c2.5 (… AND HERE)
        sem_post(&empty);   // line c3
        printf(“%d\n”, tmp);
    }
 }

 int main(int argc, char *argv[]) {
    // …
    sem_init(&empty, 0, MAX); // MAX buffers are empty to begin with …
    sem_init(&full, 0, 0);    // ... and 0 are full
    sem_init(&mutex, 0, 1);   // mutex=1 because it is a lock
    // …
 }

正确顺序producer为 wait(empty) → wait(mutex) → put → post(mutex) → post(full)；consumer为 wait(full) → wait(mutex) → get → post(mutex) → post(empty)。初值分别MAX、0、1。这样等待“有槽/有数据”时不占用修改结构的锁。

补充轨迹：容量2初始(E,F)=(2,0)。producer预留后(1,0)，插入并发布后(1,1)；consumer预留后(1,0)，取出归还后(2,0)。中途E+F可小于2，因为许可正被线程预留，不能把静止时E+F=MAX错当成每条语句后都成立的不变量。

补充：许可是预留权利，不等于缓冲区已经完成改变。 用E表示尚未预留的空槽许可、F表示可领取的数据许可、P表示生产者已经预留但尚未发布的槽位、C表示消费者已经领取但尚未归还的槽位。在正确容量协议中，E+F+P+C=MAX；这比只写E+F=MAX更准确地覆盖中间状态。

容量2、初始E=2。生产者wait(empty)后E=1、P=1；它尚未写入，所以F仍0。写好并post(full)后P=0、F=1。消费者wait(full)后F=0、C=1；直到取完并post(empty)，C才归0、E回2。这里E/F均指非负的可用许可数，不能直接代入用负数表示等待者的教学计数模型或任意时刻读到的实现内部值。P/C是解释用逻辑记账量，不要求实现再放两个信号量。

如果线程预留许可后因错误直接返回，既没完成操作也没归还许可，容量就会永久少一份。错误路径必须明确“预留了什么、是否已提交、应归还给谁”，不能无条件把所有信号量post一遍，那会凭空造许可。

p.21–23：读者组共同占有写锁

p.21 Imagine a number of concurrent list operations, including inserts and simple lookups.

insert:

Change the state of the list

A traditional critical section makes sense.

lookup:

Simply read the data structure.

As long as we can guarantee that no insert is on-going, we can allow many lookups to proceed concurrently.

p.21 This special type of lock is known as a reader-writer lock.

p.22 Only a single writer can acquire the lock.

Once a reader has acquired a read lock,

More readers will be allowed to acquire the read lock too.

A writer will have to wait until all readers are finished.

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

typedef struct _rwlock_t {
    sem_t lock;     // binary semaphore (basic lock)
    sem_t writelock;    // used to allow ONE writer or MANY readers
    int readers;    // count of readers reading in critical section
 } rwlock_t;

 void rwlock_init(rwlock_t *rw) {
    rw->readers = 0;
    sem_init(&rw->lock, 0, 1);
    sem_init(&rw->writelock, 0, 1);
 }

 void rwlock_acquire_readlock(rwlock_t *rw) {
    sem_wait(&rw->lock);
    …

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

rw->readers++;
    if (rw->readers == 1)
        sem_wait(&rw->writelock); // first reader acquires writelock
    sem_post(&rw->lock);
 }

 void rwlock_release_readlock(rwlock_t *rw) {
    sem_wait(&rw->lock);
    rw->readers--;
    if (rw->readers == 0)
        sem_post(&rw->writelock); // last reader releases writelock
    sem_post(&rw->lock);
 }

 void rwlock_acquire_writelock(rwlock_t *rw) {
    sem_wait(&rw->writelock);
 }

 void rwlock_release_writelock(rwlock_t *rw) {
    sem_post(&rw->writelock);
 }

读写锁允许多个只读者并行，写者必须独占。课件有保护readers计数的lock，及隔离写者的writelock，二者初值1。第一个reader把计数0→1并取得writelock，后续reader只增加计数；最后一个reader把1→0时释放writelock。writer直接取得writelock。

补充轨迹：R1进入读者数1占写锁，R2进入数2；R1退出数1仍不放写锁，R2退出数0才放。writer必须等两人结束。计数锁不能覆盖整个读操作，否则多读者也被串行化，失去设计目的。

补充：跟踪第一位与最后一位读者，而不是每位都抢写锁。 第一位读者把组内人数从 0 改到 1 时，为整个读者组取得排斥写者的许可；第二位读者只把 1 改到 2，不应再次等待那一份已被本组占有的许可。若每位读者都等待同一份二元许可，读者也只能逐个进入，失去并发阅读的目的。

退出时先看人数变化：从 2 到 1 说明还有一位读者使用数据，不能释放写锁；从 1 到 0 才由最后离开的读者释放。负责取得和释放的人可以不同，因为这里用的是信号量表达读者组的协议，不能不加判断地换成要求持有者释放的 mutex。保护人数的锁则只用于让人数更新和“是否第一/最后”的判断可靠，不能让它承担整个读操作的互斥。该协议解释安全性，并未单凭人数计数解决持续新读者到来时的写者饥饿。

p.24–26：公平问题与哲学家模型

p.24 The reader-writer locks have fairness problem.

It would be relatively easy for reader to starve writer.

How to prevent more readers from entering the lock once a writer is waiting?

p.25 Assume there are five “philosophers” sitting around a table.

Between each pair of philosophers is a single fork (five total).

The philosophers each have times where they think, and don’t need any forks, and times where they eat.

In order to eat, a philosopher needs two forks, both the one on their left and the one on their right.

The contention for these forks.

p.26 Key challenge

There is no deadlock.

No philosopher starves and never gets to eat.

Concurrency is high.

Philosopher p wishes to refer to the for on their left  call left(p).

Philosopher p wishes to refer to the for on their right  call right(p).

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

while (1) {
    think();
    getforks();
    eat();
    putforks();
}

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

// helper functions
int left(int p) { return p; }

int right(int p) {
    return (p + 1) % 5;
}

读者持续加入可让readers永远不归零，writer饿死；能互斥并不等于公平。随后五哲学家图把共享资源换成五把叉，每人需左右两把才可吃。课件编号left(p)=p、right(p)=(p+1)%5，目标同时包括无死锁、不饿死与合理并行度。

p.27–28：统一左先右后形成环，反转一人打破环

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

We need some semaphore, one for each fork: sem_t forks[5].

Deadlock occur!
If each philosopher happens to grab the fork on their left before any philosopher can grab the fork on their right.
Each will be stuck holding one fork and waiting for another, forever.

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

void getforks() {
    sem_wait(forks[left(p)]);
    sem_wait(forks[right(p)]);
 }

 void putforks() {
    sem_post(forks[left(p)]);
    sem_post(forks[right(p)]);
 }

p.27 The getforks() and putforks() Routines (Broken Solution)

p.28 Change how forks are acquired.

Let’s assume that philosopher 4 acquire the forks in a different order.

There is no situation where each philosopher grabs one fork and is stuck waiting for another. The cycle of waiting is broken.

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

void getforks() {
    if (p == 4) {
        sem_wait(forks[right(p)]);
        sem_wait(forks[left(p)]);
    } else {
        sem_wait(forks[left(p)]);
        sem_wait(forks[right(p)]);
    }
 }

原错误顺序所有人先wait左再wait右。若P0–P4各拿f0–f4，就分别等f1、f2、f3、f4、f0，五人均无法前进。让P4改为先f0再f4，其余仍按较小叉号先拿，等价于统一按叉号升序获取，循环等待被破坏。

这证明排除了该获取协议的死锁，并不单独证明调度和信号量实现下没有饥饿。示例调用在真实C中还应传信号量地址 &forks[index]。

p.29–30：用mutex和CV构造非负许可计数

p.29 Build our own version of semaphores called Zemaphores

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

typedef struct __Zem_t {
    int value;
    pthread_cond_t cond;
    pthread_mutex_t lock;
 } Zem_t;

 // only one thread can call this
 void Zem_init(Zem_t *s, int value) {
    s->value = value;
    Cond_init(&s->cond);
    Mutex_init(&s->lock);
 }

 void Zem_wait(Zem_t *s) {
    Mutex_lock(&s->lock);
    while (s->value <= 0)
    Cond_wait(&s->cond, &s->lock);
    s->value--;
    Mutex_unlock(&s->lock);
 }
 …

p.30 Zemaphore does not maintain the invariant for the value of the semaphore.

The value should never be lower than zero.

This behavior is easier to implement and matches the current Linux implementation.

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

void Zem_post(Zem_t *s) {
    Mutex_lock(&s->lock);
    s->value++;
    Cond_signal(&s->cond);
    Mutex_unlock(&s->lock);
 }

Zem_wait持锁循环等待value>0，之后才value--；Zem_post持锁value++并signal。这样value从不为负，等待人数由CV队列另存。它与前面的负值抽象表示方式不同，但都可表达取得许可和等待。

关键不是照着名称互相替换，而是保持：计数有锁保护；检查用while；wait原子释放锁；post先更新持久计数再通知。课件关于某Linux实现的描述是历史说明，不作为当前内核版本核验结果。

本讲核心考点

• [C] 区分互斥初值1、一次事件初值0、资源数初值N。
• [C] 完整推演先wait或先post的两种完成事件轨迹。
• [C] 解释生产消费为何需要empty、full和mutex三者，并修正获取顺序。
• [C] 追踪首读者/末读者协议及写者饥饿。
• [C] 构造哲学家环并说明反转一人的获取顺序为何破环。

附录

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

来源与证据

• 原件：L15-信号量与常见并发问题-2022未核.pptx（本地课件）；PDF副本（本地课件） p.1–30。本文页码均为 PDF 页号。

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

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