Tema 3 · Parte 2:共享内存的通信与同步 —— 信号量

Comunicación y sincronización con memoria compartida. Parte 2. Semáforos
逐句对照版 · 讲义 51 页一页不省 · 一句西语 → 一句中文 → 考点解释 · 每页附原页截图
怎么用这份讲义

一、信号量:定义与语义

p.1–p.6
p.1

Portada · 封面

▸ 原页截图 p.1原讲义第 1 页

Sistemas Concurrentes y de Tiempo Real

并发与实时系统(课程名,缩写 SCTR)。

Grado en Ingeniería Telemática

远程通信工程本科(你的专业名,答题写课程归属时会用到)。

Tema 3: Comunicación y sincronización con memoria compartida. Parte 2. Semáforos

主题 3:基于共享内存的通信与同步。第 2 部分:Semáforos。

注意标题里的介词是 con memoria compartida(「用共享内存」),不是 en。这是本课程最容易写错的标题介词,答题开头抄标题时别抄成 en memoria compartida。
记忆钩子:Parte 1 是站着等(espera activa,忙等),Parte 2 换装备——拿号等(semáforo,信号量)。同一个 Tema 3,两种武器😎
p.2

Índice de contenidos · 目录

▸ 原页截图 p.2原讲义第 2 页

Índice de contenidos

目录 / 内容索引。

• Semáforos

• 信号量(定义 + POSIX 函数)。

• Exclusión mutua

• 互斥(用信号量当锁)。

• El problema del productor/consumidor

• 生产者 / 消费者问题。

• El problema de los filósofos

• 哲学家就餐问题。

• Lectores/escritores

• 读者 / 写者问题。

这五行就是本章的答题骨架:1 个工具(信号量)+ 4 个经典问题。Parte 1 只做了「互斥 + 生产者消费者」的忙等版;Parte 2 要把四个问题全部用信号量重做一遍。期末大题八成从后四个里抽。
别把 lectores/escritores 读成「读/写文件」——西语里 lectores = 读者线程,escritores = 写者线程,它们访问的是 BD(base de datos,数据库)这个共享资源。
记忆钩子:「一器四题」——信号量是那把万能钥匙,四个问题就是四把锁🔑
p.3

Definición de Semáforo · 信号量的定义

▸ 原页截图 p.3原讲义第 3 页

Un semáforo es un mecanismo de sincronización.

信号量是一种同步机制(mecanismo de sincronización)。

Internamente almacena un número natural, que representa el número de permisos aún disponibles para acceder a un recurso compartido.

它内部保存一个自然数,表示「还有多少个许可(permisos)可以用来访问某个共享资源」。

El semáforo se llama general, si puede tomar valores superiores a uno,

如果它的取值可以大于 1,就叫通用信号量(semáforo general)。

o binario, si solo toma los valores 0, 1.

如果只取 0 和 1 两个值,就叫二元信号量(semáforo binario)。

这是名词解释题的标准答案,一个字都别改:Un semáforo es un mecanismo de sincronización que almacena internamente un número natural que representa el número de permisos disponibles para acceder a un recurso compartido; puede ser general (>1) o binario (0,1).
陷阱:「permisos」不是「计数器」。老师刻意用 permisos(许可)这个词,因为它的语义是「还能放几个人进去」。初值 = 1 → 只放 1 个进 → 天然互斥;初值 = N → 放 N 个进。答题时写 número de permisos 比写 contador 更贴讲义。
记忆钩子:信号量 = 停车场的剩余车位牌。牌子写 3,就还能进 3 辆车;写 0,就得在门口等。写了 1 的车位牌 = 二元信号量 = 单人间😏
p.4

Definición · wait 与 post(原子性)

▸ 原页截图 p.4原讲义第 4 页

Sobre un semáforo s, pueden realizarse dos operaciones principales.

对一个信号量 s,可以执行两个主要操作。

Los nombres de las operaciones varían en diferentes plataformas, pero conceptualmente son las mismas

这两个操作的名字在不同平台上不一样,但概念上完全相同。

wait(): Decrementa el número de permisos

wait():减少许可数(申请一个许可)。

Disminuye el valor de s si es superior a 0.

如果 s 的值 大于 0,就把 s 减 1。

post(): Aumenta el número de permisos

post():增加许可数(归还一个许可)。

Incrementa el valor de s.

把 s 的值加 1。

Por definición, wait y post se ejecutan de forma atómica, es decir, su ejecución paralela nunca produce valores inconsistentes para el semáforo.

按定义,wait 和 post 都是原子(atómica)执行的——也就是说,它们并行执行也绝不会让信号量的值变得不一致。

「atómica」这半句是本章的命门。老师用 por definición(按定义)开头,就是在告诉你:原子性是信号量的前提,不是实现细节。所以后面所有用信号量写的程序,都不需要再给 wait/post 加锁——它自己就是锁。答题被问「¿Por qué no hace falta proteger las operaciones sobre el semáforo?」→ 答:porque wait y post son atómicas por definición。
别把 atómica 理解成「快」。原子 = 不可分割、不被交错,跟速度无关。就算它执行得很慢,中间也不会插进别的线程。
记忆钩子:wait = 取号(拿走一个许可),post = 还号(放回一个许可)。取号和还号都是「一瞬间完成」,别人看不到你手里的半张号票🎫
p.5

Definición · 谁会挂起

▸ 原页截图 p.5原讲义第 5 页

La operación wait() suspende a la hebra que la ejecuta si el semáforo vale 0.

如果信号量等于 0,执行 wait() 的线程会被挂起(suspendida / bloqueada)。

La hebra espera hasta que alguna otra hebra realiza un post sobre el mismo semáforo

这个线程会一直等,直到别的线程对同一个信号量执行 post。

La operación post() nunca suspende.

post() 永远不会挂起。

Si hay alguna hebra suspendida en el semáforo, la despierta.

如果有线程正挂在这个信号量上,就唤醒其中一个。

En caso contrario, aumenta el número de permisos.

否则(没有人在等),就把许可数加 1。

这页就是wait/post 的完整语义表,考试最爱出成「填状态」题。背成两句话:wait:值 > 0 → 减 1 并继续;值 = 0 → 挂起等人叫。post:有人等 → 叫醒一个(值不变);没人等 → 值加 1。
最大的误区:post 在「有人等」的时候不会把值加 1,而是直接把许可「递」给等待者(专业说法:se lo pasa directamente)。所以「post 一定让值 +1」是错的!这是判断题的高频坑。
记忆钩子:post 是「叫号机」——有人排队就直接叫下一位(号票不留在柜台上);没人排队才把号票放回盒子📢
p.6

Ejercicio de traza · 五个线程交错,初值 0

▸ 原页截图 p.6(插图页)原讲义第 6 页插图

Hebra 1 …… sem_wait

线程 1:先干点别的,然后执行一次 sem_wait。

Hebra 2 …… sem_post

线程 2:先干点别的,然后执行一次 sem_post。

Hebra 3 …… sem_post

线程 3:先干点别的,然后执行一次 sem_post。

Hebra 4 …… sem_wait

线程 4:先干点别的,然后执行一次 sem_wait。

Hebra 5 …… sem_wait

线程 5:先干点别的,然后执行一次 sem_wait。

Orden de ejecución · Semaforo. Valor inicial-> 0 · ¿Cómo sería la ejecución?

执行次序(自定)· 信号量初值 = 0 · 「执行过程会是怎样的?」——这是一道让你自己排顺序做轨迹的课堂练习。

总共
3 次 wait、2 次 post,初值 0。
一眼看出
wait 比 post 多 1 → 结束时必然有线程被永久阻塞。

轨迹 A(顺序 1→2→3→4→5,教科书式):

步动作s结果
1H1 wait0s 为 0 → H1 阻塞,进入等待队列
2H2 post0有人等 → 唤醒 H1,值仍为 0(许可直接递过去)
3H3 post1没人等 → 值加 1
4H4 wait0值 > 0 → 减 1,H4 通过
5H5 wait0值 = 0 → H5 永久阻塞

轨迹 B(顺序 2→3→1→4→5,post 先跑):

步动作s结果
1H2 post1没人等 → 值加 1
2H3 post2没人等 → 值加 1
3H1 wait1通过
4H4 wait0通过
5H5 wait0值 = 0 → H5 永久阻塞
考点:这类题不是让你求唯一答案,而是让你证明「结果依赖执行次序」。标准答法分三步:① 数一数 wait 与 post 各几次;② 按某个次序画轨迹表;③ 下结论:Al haber más wait que post, al menos una hebra quedará bloqueada; el número exacto depende del orden de ejecución.
陷阱:不要因为轨迹 A 里「H1 被唤醒后值还是 0」就以为算错了。post 遇到等待者 = 直接移交,值不变(p.5 的原话)。这一点错了,整张表都会错。
记忆钩子:wait 是借钱,post 是还钱。借 3 次还 2 次,最后永远有 1 个人在等钱😭 至于等的是谁?看谁手慢。

二、POSIX 信号量函数

p.7–p.11
p.7

sem_init · 初始化

▸ 原页截图 p.7原讲义第 7 页

int sem_init (sem_t *sem, int pshared, unsigned int value)

原型:int sem_init(sem_t *sem, int pshared, unsigned int value)——三个参数:信号量指针、共享标志、初值。

sem_init Inicializa el semáforo apuntado por sem.

sem_init 初始化 sem 所指向的那个信号量。

El valor inicial del semáforo toma el valor value.

信号量的初值就等于参数 value。

El argumento pshared indica si es local al proceso actual (pshared es cero) o si es compartido entre procesos (diferente de 0).

pshared 说明它是当前进程内私有(pshared = 0),还是在多个进程之间共享(pshared ≠ 0)。

Éxito -> sem_init devuelve 0.

成功 → 返回 0。

Fallo -> devuelve -1

失败 → 返回 -1。

// 线程之间用(本课程 99% 的场景)
sem_t sem;
sem_init(&sem, 0, 1);   // 进程私有 + 初值 1 → 二元信号量

// 进程之间用(要放在共享内存里)
sem_init(&sem, 1, 1);   // pshared ≠ 0 → 跨进程共享
三个参数必须按顺序记牢:① 地址 &sem ② pshared ③ value。写代码题里 sem_init(&sem, 0, 1) 这一行出现频率最高——0 表示线程间、1 表示初值(互斥锁),这两个数字写反是新手最常见的一血。
陷阱:pshared = 0 是「不共享」,≠ 0 才是「共享」。中文语感容易反着记!记住:0 = 只在自家用。
记忆钩子:sem_init(&sem, 0, 1) 读成「零跨进程,一个车位」——自家停车场,只停一辆车🚗
p.8

sem_destroy · 销毁与 EBUSY

▸ 原页截图 p.8原讲义第 8 页

int sem_destroy (sem_t * sem)

原型:int sem_destroy(sem_t *sem)——销毁信号量。

Operación para destruir el semáforo

这是销毁信号量的操作(释放它占用的资源)。

Si existen hebras esperando en el semáforo la operación devuelve EBUSY

如果还有线程正阻塞在这个信号量上,该操作返回 EBUSY(device or resource busy,资源忙)。

这一页只考一个词:EBUSY。问「¿Qué devuelve sem_destroy si hay hebras esperando?」→ 答 EBUSY,理由是「no se puede destruir un semáforo que todavía tiene hebras bloqueadas」。这也解释了为什么必须先 pthread_join 再 sem_destroy。
陷阱:EBUSY 是错误码(errno 值),不是布尔值,也不是 -1。写代码题里如果看到 sem_destroy 在 pthread_join 之前,那一定是错序——先等人全部结束,再销毁。
记忆钩子:EBUSY = 「里面还有人,不许拆房」。等最后一个人出来,才能拆🏚️
p.9

sem_post · 释放 / 唤醒

▸ 原页截图 p.9原讲义第 9 页

int sem_post (sem_t * sem)

原型:int sem_post(sem_t *sem)——对应抽象的 post()。

Función que incrementa el valor del semáforo.

这个函数把信号量的值加 1。

Si otras hebras están esperando en el semáforo una de ellas se despertará

如果有别的线程正在这个信号量上等,其中一个会被唤醒。

这句和第 p.5 页是同一件事的两面:有等待者 → 唤醒一个(值不变);无等待者 → 值 +1。选择题常把「incrementa siempre」当正确选项来骗你,看清 si … una de ellas se despertará 这个条件句。
还要注意:只唤醒「一个」,不是全部(una de ellas)。想让 N 个线程都过去,就得 post N 次。这点在生产者—消费者里非常关键。
记忆钩子:post 像食堂阿姨喊「下一位!」——只喊一个人,不会全场起立🍚
p.10

sem_wait / sem_trywait · 申请

▸ 原页截图 p.10原讲义第 10 页

int sem_wait (sem_t * sem)

原型:int sem_wait(sem_t *sem)——会阻塞的申请。

int sem_trywait (sem_t * sem)

原型:int sem_trywait(sem_t *sem)——不阻塞的申请(try = 试一试)。

Funciones que decrementan el valor del semáforo en 1.

这两个函数都把信号量的值减 1。

Si el valor del semáforo es 0 la hebra se bloquea y espera a que el semáforo sea incrementado por otra hebra.

如果信号量已经是 0,线程就阻塞,等别的线程把它加上去。

En el caso de sem_trywait la hebra no se bloqueará

而 sem_trywait 的情况下,线程不会阻塞——申请不到就立刻返回失败(EAGAIN)。

sem_wait
值为 0 → 睡着等(让出 CPU),被 post 叫醒
sem_trywait
值为 0 → 立刻返回失败,继续干别的
考点就是这一对的反差:wait = bloqueante(会阻塞),trywait = no bloqueante(非阻塞)。这是「轮询 vs 阻塞」的接口级体现,也可以用来实现「拿不到锁就先去做别的事」。
陷阱:sem_trywait 失败时不会把值减成负数,信号量永远 ≥ 0(POSIX 实现)。别把它想成「减到 -1 表示有 1 个线程在等」——那是某些教材里 Dijkstra 原始信号量的记法,考试按老师的 POSIX 版本答。
记忆钩子:try = 试一下,不行就走;wait = 死等。一个是「扫码付款」,一个是「排队到天亮」😴
p.11

sem_getvalue · 读值(有坑)

▸ 原页截图 p.11原讲义第 11 页

int sem_getvalue (sem_t * sem, int * sval)

原型:int sem_getvalue(sem_t *sem, int *sval)——读当前值。

Devuelve en sval el valor del semáforo

把信号量的值写到 sval 指向的整数里。

¡Cuidado! El valor puede haber cambiado cuando termine getvalue.

小心!等 getvalue 返回的时候,那个值可能已经变了。

这一行 ¡Cuidado! 就是考点本体:sem_getvalue 读到的值只是「一瞬间的快照」,不能拿它做判断依据。为什么?因为读完之后、你据此行动之前,别的线程可能已经 post/wait 过了(这和 Parte 1 的 TOCTOU 是同一个病根)。标准答法:El valor devuelto es una instantánea; puede haber cambiado al terminar la llamada, por lo que no debe usarse para tomar decisiones de sincronización.
陷阱:绝对不要写 while (sem_getvalue(&s,&v), v==0) {} 这种「查值再决定」的代码——那等于把已经淘汰的忙等待又请回来了,而且还引入了竞态。
记忆钩子:getvalue 像看油表——你低头看一眼的瞬间是半箱,抬头时可能已经被人开走了🚗💨 只适合调试打日志,不适合做决策。

三、互斥:把信号量当锁用

p.12–p.16
p.12

Exclusión Mutua · 骨架与 R1

▸ 原页截图 p.12原讲义第 12 页

while (1){ //Preprotocolo1 SC1 //Postprotocolo1 }

线程 1 的死循环骨架:前协议(申请)→ 临界区 SC1(要保护的动作)→ 后协议(释放)。线程 2 完全对称。

R1: en cada momento hay a lo sumo una hebra ejecutando su sección crítica

R1:任何时刻,最多只有一个线程在执行它的临界区。

Preprotocolo
进门之前:申请许可(wait)
Postprotocolo
出门之后:归还许可(post)
R1 的原文关键词是 «a lo sumo»(至多),不是 «exactamente una»。「至多一个」包含 0 个——没有线程想进临界区时,里面当然是空的,这并不违反 R1。答题时漏掉「a lo sumo」会被扣分。
原文代码块里多出了几行孤立的 }(PDF 排版残留),这是讲义本身的笔误。这里按原样保留说明,但你自己写作业时不要抄这些多余的右花括号。
记忆钩子:临界区 = 厕所单间。前协议是「敲门 / 锁门」,后协议是「开门出来」。最多一个人在里面,也可以没人🚽
p.13

Exclusión Mutua · 两个线程的实现

▸ 原页截图 p.13原讲义第 13 页

void *P1 (void *id) { while (1){ sem_wait(&s) SC1 sem_post(&s); } }

线程 P1:循环里 wait → 临界区 → post。P2 结构相同,只是临界区换成 SC2。

sem_init(&sem, 0, 1); // semáforo binario

初始化:sem_init(&sem, 0, 1),注释明确写着「二元信号量」——初值 1 就是那把「唯一的钥匙」。

Cuando una hebra entra en su sección crítica cierra el semáforo y así impide que la otra hebra entre.

当一个线程进入临界区时,它把信号量「关上」(1 → 0),这样就挡住了另一个线程。

Cuando la hebra sale de su sección crítica abre el semáforo para permitir que la otra hebra ejecute su SC si quiere hacerlo.

当它离开临界区时,把信号量「打开」(0 → 1),让另一个线程如果愿意的话可以进去执行它的 SC。

void *P1 (void *id) {
  while (1){
    sem_wait(&s);   // ← 原文此处缺分号,讲义笔误
    SC1
    sem_post(&s);
  }
}
void *P2 (void *id) {
  while (1){
    sem_wait(&s);   // ← 原文此处缺分号,讲义笔误
    SC2
    sem_post(&s);
  }
}
sem_init(&sem, 0, 1);   // semáforo binario
这一页是全章最该背下来的 8 行代码:wait → SC → post。「关上 / 打开」这个比喻考试可以直接用:al entrar cierra el semáforo (1→0) y al salir lo abre (0→1)。
原页有两处笔误,抄作业时要改:① 两个 sem_wait(&s) 后面缺分号;② 代码里用的是 &s,而初始化写的是 &sem——变量名不一致,编译会报 undeclared identifier。统一成 sem 即可。
记忆钩子:wait 关门、post 开门。谁进门谁锁门,谁出门谁开锁——这是「自己锁的自己开」的礼貌🔐
p.14

Ejemplo · main(三个线程)

▸ 原页截图 p.14原讲义第 14 页

#include <pthread.h> #include <semaphore.h> #include <stdio.h> #include <stdlib.h> #include <sys/types.h> #include <unistd.h>

六个头文件:线程、信号量、输入输出、随机数、系统类型、sleep。

void *Acceso(void *);

线程函数原型声明(参数是 void*,返回也是 void*,这是 pthread 的固定签名)。

// Definición de la variable semaforo · sem_t sem;

定义信号量变量:sem_t sem;——全局定义,三个线程共享同一个。

int main() { pthread_t thread1, thread2, thread3; int id0=0; int id1=1; int id2=2; }

主函数里建三个线程句柄,并给每个线程准备一个独立的 id 变量(0、1、2)。

// inicializamos semaforo a 1 · sem_init(&sem, 0, 1);

把信号量初始化为 1——保证一开始就有一个人能进。

pthread_create(&thread1, NULL, &Acceso, &id0); … &id1 … &id2

创建三个线程,都执行同一个函数 Acceso,但各自传入不同的 id 地址。

pthread_join(thread1, NULL); pthread_join(thread2, NULL); pthread_join(thread3, NULL); return 0;

主线程等三个线程结束(虽然它们是死循环,实际永远等不到),最后返回 0。

这段 main 是所有 pthread 代码题的标准模板,四步记住:① 定义句柄 ② sem_init ③ pthread_create ④ pthread_join。答题被问「¿Cómo se crean las hebras?」时,直接默写这四行。
陷阱:int id0=0; int id1=1; int id2=2; 必须是三个分开的变量。如果写成数组再传 &id[i] 在循环里,所有线程可能拿到同一个地址(Parte 1 踩过的坑)。讲义这里分开写,正是为了避开这个问题。
记忆钩子:sem_init 必须在 pthread_create 之前——先备好钥匙,再叫人来开门,顺序反了就全乱套🔑
p.15

Ejemplo · 线程函数 Acceso

▸ 原页截图 p.15原讲义第 15 页

void *Acceso(void *id) { int i,k=0, time; while (1) { … } }

线程函数:进入死循环,循环里就是「临界区 + 非临界区」的组合。

sem_wait(&sem);

进临界区之前申请许可(拿锁)。

// estamos un tiempo en la seccion critica (< 30 seconds)

注释:我们在临界区里待一段时间(不到 30 秒)。

time = (int) ((double) rand() / RAND_MAX * 2);

用 rand() 生成 0 或 1 秒的随机睡眠时间(RAND_MAX 归一化后乘 2)。

printf("Thread %d entra y duerme %d segundos...\n", *((int*) id), time); sleep(time);

打印「线程 X 进入并睡 Y 秒」,然后在临界区里 sleep——故意拉长临界区,好让冲突暴露出来。

printf("Thread %d sale de la sección critica\n", *((int*) id)); sem_post(&sem);

打印「线程 X 离开临界区」,然后 post 释放。

printf("Thread %d hace algo fuera de la seccion critica\n", *((int*) id)); for (i=0;i<1000000;i++) {k=k+1;k=k-1;}

出了临界区再打印一句,然后跑一个耗时但无意义的空循环(模拟非临界区的计算)。

Esto se realiza en exclusión mutua

(页边标注)「这一段是互斥执行的」——指的是 sleep + 两条 printf 那一段。

这段代码的作用是实验验证 R1:因为 sleep 在临界区内,如果互斥正确,屏幕上就绝不会出现两个「entra」夹着一个「sale」;一旦发生,就是 R1 被破坏。实验报告的标准结论句:Las trazas muestran que nunca hay dos hebras dentro de la sección crítica a la vez, por lo que se cumple R1.
陷阱:*((int*) id) 是把 void* 先转成 int*,再解引用。少一层括号就会编译错误。另外 sleep() 的参数是秒,不是毫秒。
记忆钩子:sleep 放在临界区里 = 故意把厕所门锁着玩手机📱 正是这种「占着不放」才让并发错误一眼可见。
p.16

Generalización · R1' 与 M 个许可

▸ 原页截图 p.16原讲义第 16 页

Exclusión Mutua: Generalización

互斥的推广(从「只许 1 个」推广到「只许 M 个」)。

R1’: en cada momento hay a lo sumo M<N hebras ejecutando su sección crítica

R1':任何时刻,最多 M 个(M < N)线程在执行临界区(N 是线程总数)。

sem_init(&sem, 0, M);

初始化时把初值写成 M——通用信号量,一次发 M 张许可。

初值同时能进几个信号量类型典型用途
11binario互斥锁(R1)
M最多 Mgeneral限流(R1'):M 个数据库连接、M 个车位
考点:R1 是 R1' 在 M = 1 时的特例。如果考试问「¿Cómo se pasa de exclusión mutua a control de aforo?」→ 答:basta cambiar el valor inicial del semáforo de 1 a M。代码一行都不用改,只有 sem_init 的第三个参数变。
陷阱:M 必须严格小于 N。如果 M = N,所有线程都能同时进,那就不再是「控制」了,等于没加信号量。这个 M<N 是 R1' 成立的前提,答题别漏。
记忆钩子:初值 = 车位数。写 1 是单人间,写 4 是四人宿舍,写 N 就是大马路——那就没人管了🅿️

四、生产者—消费者问题

p.17–p.25
p.17

Planteamiento · 三条性质 C1 / C2 / R1

▸ 原页截图 p.17(插图页)原讲义第 17 页插图

buffer · productor · consumidor

三个核心词:缓冲区、生产者(往里放数据)、消费者(从里取数据)。

Recurso compartido · hebras

图注:buffer 是共享资源(被动实体),productor / consumidor 是线程(主动实体)。

Propiedades

需要满足的性质(这一页就是全题的评分表)。

C1: El productor no puede almacenar en el buffer, si está lleno

C1:缓冲区满了,生产者就不能再存。

C2: El consumidor no puede extraer del buffer, si está vacío

C2:缓冲区空了,消费者就不能再取。

R1: El buffer siempre se utiliza en exclusión mutua

R1:缓冲区永远要在互斥下使用。

C1 / C2 = sincronización
「什么时候能做」——靠条件信号量控制先后
R1 = exclusión mutua
「能不能同时做」——靠一把锁保护 buffer
这三条是本章最重要的答题清单,写任何生产者—消费者代码前先默念:C1 满不放、C2 空不取、R1 缓冲区互斥。而且必须能区分:C1/C2 属于同步(sincronización),R1 属于互斥(exclusión mutua)——这是老师最爱考的概念分辨题。
陷阱:很多同学以为「生产者—消费者就是一个互斥问题」。错!它既有同步(C1/C2)又有互斥(R1),两者缺一不可。只加 mutex 会崩(越界 / 取空),只加条件信号量会读到脏数据。
记忆钩子:buffer = 冰箱。冰箱满了别硬塞(C1),冰箱空了别硬拿(C2),开冰箱门时只能一个人伸手(R1)🧊
p.18

Pseudocódigo · 先写目标,再想信号量

▸ 原页截图 p.18原讲义第 18 页

void productor (arg) { while (1){ produce(dato) //esperar si el buffer está lleno //almacenar dato en el buffer //indicar que el buffer no está vacío } }

生产者循环四步:造数据 → 若满则等 → 存进 buffer → 通知「不空了」。

void consumidor(arg) { while (1){ //esperar si el buffer está vacío //extraer dato del buffer //indicar que el buffer no está lleno consume(dato); } }

消费者循环四步:若空则等 → 从 buffer 取出 → 通知「不满了」→ 消费数据。

int buffer[N]

共享数组,容量 N——这是决定「满 / 空」的物理边界。

C1: El productor no puede almacenar en el buffer, si está lleno

再强调一次 C1:满了就不能存。

Necesitamos un semáforo que valga 0 cuando el buffer está lleno

所以我们需要一个信号量,当 buffer 满时它正好等于 0。

这句「Necesitamos un semáforo que valga 0 cuando…」是老师的解题方法论,比代码本身更值钱:先确定「什么状态下要挡住谁」,再让信号量在该状态下恰好为 0。答题写设计思路时照抄这个句式,阅卷老师一眼就知道你懂。
注意这页还没有任何信号量代码,全是注释形式的「待办」。别急着背代码——老师是故意先让你把「四步流程」刻进脑子,下一才填 wait/post。
记忆钩子:满 → 生产者被拦;空 → 消费者被拦。信号量就是那个「拦人的保安」,满员时把生产者挡在门外💂
p.19

Paso 1 · hayEspacio(只管 C1)

▸ 原页截图 p.19原讲义第 19 页

void Productor (arg) { while (1){ produce(dato) sem_wait(&hayEspacio); //almacenar dato en el buffer //indicar que el buffer no está vacío } }

生产者:造完数据后 wait(hayEspacio)——有位置才继续往下走。

void consumidor (arg) { while (1){ //esperar si el buffer está vacío //extraer dato del buffer sem_post(&hayEspacio); consume(dato); } }

消费者:取完数据后 post(hayEspacio)——「我腾出一个位置了」。

sem_init(&hayEspacio, 0, N);

初始化:初值 = N(容量),因为一开始 buffer 全空,有 N 个空位。

C1: El productor no puede almacenar en el buffer, si está lleno

对应性质 C1。

Necesitamos un semáforo que valga 0 cuando el buffer está lleno

设计依据:buffer 满 ⇔ hayEspacio = 0。

Inicialmente el buffer está vacío

初始条件:buffer 是空的 → 所以空位数 = N。

signal 名
hayEspacio = 「有空间」的信号量
语义
值 = 当前还能存几个数据
考点:hayEspacio 的初值必须是 N,不能是 0。为什么?因为「buffer 一开始是空的」⇒ 有 N 个空位 ⇒ 允许生产者连续存 N 次。初值写 0 会导致生产者一启动就永久阻塞——这是改错题的经典错误。
陷阱:这一页只解决了一半。此时消费者还没有 hayDatos 保护,buffer 空的时候它会直接往下取,读到垃圾数据(C2 未满足)。老师是故意分两步讲,下一才补全。
记忆钩子:hayEspacio 是「空座位牌」。餐厅刚开门,N 个座位都是空的,牌子写 N;客人坐下就减 1🍽️
p.20

Paso 1.5 · 提出 C2(代码还没改)

▸ 原页截图 p.20原讲义第 20 页

C2: El consumidor no puede leer del buffer, si está vacío

C2:buffer 空时,消费者不能读。(注意这页把 p.18 的 extraer 写成了 leer,意思一样。)

Necesitamos un semáforo que valga 0 cuando el buffer está vacío

需要一个信号量,当 buffer 空时它正好为 0。

Inicialmente el buffer está vacío

初始状态:buffer 是空的(所以这个新信号量的初值应该是 0)。

void Productor (arg) { … sem_wait(&hayEspacio); … }

生产者代码与上一页完全相同,没有变化。

void consumidor (arg) { … sem_post(&hayEspacio); consume(dato); }

消费者代码也与上一页完全相同。

这一页是纯「提出问题」页:只写 C2 和设计需求,不改代码。考试如果只给你这一页的代码让你补全,你要加的就是 hayDatos。判断依据一句话:«Necesitamos un semáforo que valga 0 cuando el buffer está vacío» ⇒ su valor inicial es 0, y el productor hará post sobre él tras almacenar.
陷阱:别以为老师忘改代码了。教学递进就是这样:p.19 先解决 C1,p.20 指出 C2 还缺,p.21 才把两个信号量合体。你复习时若只背最终版,就答不出「为什么需要第二个信号量」这种过程题。
记忆钩子:「满看空位牌,空看数据牌」。现在手里只有空位牌,还缺一张「有货」的牌子🏷️
p.21

Paso 2 · 双信号量 hayEspacio + hayDatos

▸ 原页截图 p.21原讲义第 21 页

sem_init(&hayEspacio,0,N);

空位数信号量,初值 N(容量)。

sem_init(&hayDatos ,0,0);

数据数信号量,初值 0(一开始没有数据)。

C2: El consumidor no puede leer del buffer, si está vacío

C2 重申。

Necesitamos un semáforo que valga 0 cuando el buffer está vacío

设计依据:buffer 空 ⇔ hayDatos = 0。

Inicialmente no hay datos

初始条件:没有数据 → hayDatos 从 0 开始。

Productor: produce(dato) · sem_wait(&hayEspacio); · //almacenar · sem_post(&hayDatos);

生产者:等空位 → 存 → 举手说「有数据了」(post hayDatos)。

consumidor: sem_wait(&hayDatos); · //extraer · sem_post(&hayEspacio); · consume(dato);

消费者:等数据 → 取 → 举手说「空出一格」(post hayEspacio)→ 再消费。

wait 谁post 谁含义
ProductorhayEspaciohayDatos消耗一个空位,产出一个数据
ConsumidorhayDatoshayEspacio消耗一个数据,归还一个空位
这张交叉表是本章最该背的东西:生产者 wait 空位 / post 数据;消费者 wait 数据 / post 空位。两边完全镜像,谁 wait 的就由对方 post——这就是「同步」的本质:我等的条件,必须由你来满足。答题时画这张表,比写十行代码更清楚。
陷阱:初值千万别都写 0 或都写 N。hayEspacio = N(开局全空)、hayDatos = 0(开局没货)——这两个数由「初始物理状态」唯一决定,写反了程序一启动就死。
记忆钩子:两个信号量像乒乓:生产者打「有货」给你,你打「有空位」还他。球不能停,停了就死锁🏓
p.22

Paso 3 · 加上 mutex,凑齐三件套

▸ 原页截图 p.22原讲义第 22 页

R1: El buffer se utiliza en exclusión mutua

R1:缓冲区必须互斥使用。

Necesitamos un semáforo para la exclusión mutua de buffer

所以要再加一个专门负责「锁」的信号量。

Inicialmente el buffer está libre

初始时缓冲区是空闲的 → mutex 初值 1。

// 生产者
void Productor (arg) {
  while (1){
    produce(dato)
    sem_wait(&hayEspacio);   // ① 等空位(条件)
    sem_wait(&mutex);        // ② 再拿锁(互斥)
    //almacenar dato en el buffer
    sem_post(&mutex);        // ③ 先放锁
    sem_post(&hayDatos);     // ④ 再喊「有货了」
  }
}
// 消费者
void consumidor (arg) {
  while (1){
    sem_wait(&hayDatos);     // ① 等数据(条件)
    sem_wait(&mutex);        // ② 再拿锁
    //extraer dato del buffer
    sem_post(&mutex);        // ③ 先放锁
    sem_post(&hayEspacio);   // ④ 再喊「有空位了」
    consume(dato);
  }
}
sem_init(&hayEspacio, 0, N);   // 开局 N 个空位
sem_init(&hayDatos , 0, 0);   // 开局 0 个数据
sem_init(&mutex    , 0, 1);   // 锁是开的
信号量管什么初值谁 wait谁 post
hayEspacio还有几个空位(C1)NProductorConsumidor
hayDatos还有几个数据(C2)0ConsumidorProductor
mutex谁能动 buffer(R1)1两边都 wait两边都 post
考题形态:给你一段缺 mutex 的生产者—消费者,问「会不会出错」。答案:会——两个生产者可能同时写同一个 i,或读写交错导致数据丢失/覆盖。补法就是这张表的第三行:进出临界区各包一层 mutex。注意 mutex 的 wait 只包住「存取 buffer」那几行,不要包住 produce() / consume(),否则并发度白送。
顺序铁律(p.25 会用它杀你一遍):进门先条件、后锁;出门先锁、后条件。
即 wait(条件) → wait(mutex) → … → post(mutex) → post(条件)。反过来写就是死锁,见下一页。
记忆钩子:「先排队拿号,再进柜台;出柜台先还钥匙,再喊下一位」。谁把顺序倒过来,谁就把门反锁了🔐
p.23

main 与全局变量 · 环形缓冲区

▸ 原页截图 p.23原讲义第 23 页
int main () {
  pthread_t th1, th2;
  pthread_attr_t attr;
  // Inicializamos semaforos
  sem_init(&Hay_espacio, 0, MAXT);
  sem_init(&Hay_Datos , 0, 0);
  sem_init(&mutex     , 0, 1);
  pthread_attr_init(&attr);
  pthread_create(&th1, &attr, Productor , NULL);
  pthread_create(&th2, &attr, Consumidor, NULL);
  pthread_join(th1, NULL);
  pthread_join(th2, NULL);
  printf("Fin\n");
  return 0;
}

El buffer se utiliza de forma circular

缓冲区按环形方式使用(写到末尾就绕回头)。

#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
//Variable global
#define MAXT 100
long Buffer[MAXT];
// semaforo para controlar que el buffer
//no esta lleno
sem_t Hay_espacio;
// semaforo para controlar que el buffer
//no esta vacio
sem_t Hay_Datos;
// semaforo para controlar el acceso
//al buffer en exclusion mutua
sem_t mutex;
讲义笔误(只标注、不改写):本页起名字变成 Hay_espacio / Hay_Datos(大写 H),而 p.21–p.22 写的是 hayEspacio / hayDatos。C 语言大小写敏感,照抄两页混用会直接编译不过。考试若手写代码,全文统一一种写法即可,但要在旁边说明「与讲义命名差异仅为大小写」。
三个全局信号量为什么必须是全局?因为主线程 sem_init 之后,生产者/消费者两个线程都要看到同一块内存。若定义在 main 内部再传指针,也可以,但讲义选了最简单的全局写法。
常考填空:sem_init(&Hay_espacio, 0, MAXT) 里的第三个参数为什么是 MAXT?答:初值 = 开局可用资源数 = 整个 buffer 都是空的,所以有 MAXT 个空位。同理 Hay_Datos 初值 0(还没生产过)。这一句话能拿满「解释初值含义」的分。
p.24

完整代码 · Productor / Consumidor

▸ 原页截图 p.24原讲义第 24 页
void *Productor(void *argg ){
  int i=0;
  // Suponemos un dato cualquiera.
  // Lo iremos incrementando
  int dato=0;
  while (1) {
    // Comprobamos que se puede producir
    sem_wait(&Hay_espacio);
    // Acceso en exclusion mutua
    sem_wait(&mutex);
    Buffer[i]=dato;
    dato=(dato+1) % 10000;
    i=(i+1)%MAXT;
    sem_post(&mutex);
    // Avisamos de que hay datos
    sem_post(&Hay_Datos);
  }
}
void *Consumidor(void *argg ){
  int i=0;
  int dato=0;
  while (1) {
    // Comprobamos que hay datos
    sem_wait(&Hay_Datos);
    // Acceso en excluision mutua
    sem_wait(&mutex);
    dato=Buffer[i];
    i=(i+1)%MAXT;
    sem_post(&mutex);
    // Avisamos de que hay datos
    sem_post(&Hay_espacio);
    printf("Dato Consumido =%d\n",dato);
  }
}

dato=(dato+1) % 10000;

生产的数据只是「0,1,2,… 循环」的假数据,取模防止溢出。

i=(i+1)%MAXT;

下标环形推进:走到 99 之后回到 0,不越界。

两处讲义笔误(只标注、不改写):
① 消费者那句注释写的是 // Avisamos de que hay datos,但它下一行 sem_post(&Hay_espacio) 通告的其实是「空出一个位置」,正确注释应为 hay espacio——这是典型复制粘贴残留。
② excluision 拼写错误,正确是 exclusión(西语)/ exclusion(代码注释)。
答题时注释写对,别把错误一起抄上去扣分。
考点:为什么两个线程各自有一个 i?因为生产者和消费者是各自独立地按环形顺序推进的游标,不是共享变量。它们能对上,靠的是「生产一个 → 消费一个」的计数信号量同步,而不是共享下标。这句话答出来,说明你真懂了。
另:既然 i 是各线程私有,Buffer[i] 的读写为什么还要 mutex?因为两块不同的私有 i 可能指向同一个槽,且 buffer 元素本身是共享的。
打印语句 printf 放在 sem_post(&Hay_espacio) 之后、临界区之外,是故意的:慢速 I/O 不该占着锁,否则并发度暴跌。这是「临界区尽量短」的教科书示范。
记忆钩子:「锁只管仓库门,不管流水线」。produce / consume / printf 都在门外干,只有存取那一行为什么要进门🏃
p.25

⚠️ 死锁:preprotocolo 顺序颠倒

▸ 原页截图 p.25原讲义第 25 页
Productor
  ……..
  while (1){
    produce(dato)
    sem_wait(&mutex);      // ✗ 先拿锁
    sem_wait(&hayEspacio)   // ✗ 再等条件
    buffer[i] = dato;
    i = (i+1) % N;
    ….
  }
Consumidor
  ………
  while (1){
    sem_wait(&mutex);      // ✗ 先拿锁
    sem_wait(&hayDatos);    // ✗ 再等条件
    dato = buffer[i];
    i = (i+1) % N;
    …….
  }
步谁动作mutexhayDatos结果
0—初始状态10buffer 空
1consumidorwait(mutex)00消费者拿到锁
2consumidorwait(hayDatos)00没数据 → 阻塞,且握着锁不放
3productorwait(mutex)00锁被占 → 阻塞
4—谁都动不了00DEADLOCK 💀
原文页脚警告:「Cuidado con intercambiar las instrucciones del preprotocolo」——小心把前置协议里的两条指令互换顺序。这张图就是互换后的后果:消费者占着 mutex 等 hayDatos,生产者等 mutex 才能生产 hayDatos,互相等对方、谁也不放 → 死锁。
缓冲区满时是镜像版本:生产者占着 mutex 等 hayEspacio,消费者等 mutex 才能腾出空位 → 同样死锁。
这是本章最容易被考的大题,标准答法三段式:
① 现象:preprotocolo 写成 wait(mutex) 在前、wait(条件量) 在后。
② 推演:线程 A 拿到 mutex 后,因为条件不满足(没数据 / 没空位)阻塞;阻塞时并不释放 mutex;线程 B 需要的正是 mutex,于是永远等不到;而 A 等的条件只能由 B 满足 → 循环等待 → deadlock。
③ 结论:必须先 wait 条件信号量、后 wait mutex;退出时先 post mutex、后 post 条件信号量。口诀:「条件在外,锁在内」。
为什么「后 post 条件量」也对?因为如果你还握着锁就 post(hayDatos),被唤醒的消费者会立刻去抢 mutex,抢不到又阻塞一次(叫 thrashing / 无谓唤醒)。先放锁再唤醒,被唤醒者一步到位。这不是死锁,但是性能坑。
记忆钩子:「拿着钥匙去排队,队永远不动」——钥匙(mutex)要在进门那一刻才掏,不是排队前就攥手里🔑

五、哲学家就餐问题 · p.26–p.32

p.26

问题定义:5 个哲学家,两件事

▸ 原页截图 p.26原讲义第 26 页

N = 5 hebras filósofos dedican su vida a dos únicas tareas:

N = 5 个哲学家的线程,一生只干两件事:

pensar, la mayor parte del tiempo

思考——大部分时间都在干这个。

comer, de vez en cuando

吃饭——偶尔来一次。

void Filosofo() {
  while (true){
    //pensar
    //comer
  }
}
这个模型是并发课程的万能替身:凡是「N 个进程 + 有限资源 + 每个进程要同时抓两把」的问题,都能套它。考试常问:「哲学家问题抽象掉了现实中的什么?」答:抽象掉具体业务,只留下资源竞争的结构——这样讨论死锁、饥饿、互斥才干净。
记忆钩子:「想得多,吃得少,抢得凶」——哲学家就是你的 CPU 线程,吃饭就是进临界区🍝
p.27

场景设定:圆桌 · 无限食物 · 两把叉子

▸ 原页截图 p.27原讲义第 27 页

La tarea «pensar» representa la actividad que cada hebra puede hacer sin necesidad de sincronizarse ni comunicarse con los demás.

「思考」代表无需同步、无需通信的独立活动——不碰共享资源,所以随便跑。

Sin embargo, para «comer» los filósofos tienen que ponerse de acuerdo:

但「吃饭」就必须协商——因为要抢共享的叉子。

En el comedor hay una mesa en la que cada filósofo tiene su puesto.

餐厅里一张圆桌,每人有固定座位。

En el centro de la mesa hay una cantidad ilimitada de comida

桌子中央有无限量的食物(所以食物不是瓶颈,叉子才是)。

Adyacentes al plato que corresponde a cada filósofo, hay dos tenedores que el filósofo necesita para poder comer

每个盘子两侧各有一把叉子,必须两把都有才能吃。

设定背后的用意
圆桌(mesa circular)第 5 人的右手边绕回第 1 人 → 形成环,这是死锁的必要条件
食物无限(comida ilimitada)排除「食物不够」这个干扰因素,只让叉子成为唯一资源
每人两把叉子每人要同时持有两个资源 → 才会出现「各拿一把、互相等」
图注 Platón / Descartes只是漫画人名,别当成变量名(考试写代码不用出现)
注意「无限食物」这个设定不是废话。它把问题纯化成「只有叉子是稀缺资源」,这样分析死锁时不用考虑生产者—消费者的缓冲区满/空。答题时点出这一句,说明你读懂了建模意图。
本题最容易踩的坑:把「思考」也加锁。思考不访问共享资源,加锁纯属自找麻烦,还会把并发度砍成 1。凡是「不需要同步的活动」,就别碰信号量。
p.28

建模:一把叉子 = 一个二元信号量

▸ 原页截图 p.28原讲义第 28 页

Los tenedores son los recursos del sistema que las hebras deben utilizar en exclusión mutua

叉子就是系统的资源,线程之间必须互斥使用。

(no puede haber dos filósofos utilizando simultáneamente el tenedor que comparten)

(共享同一把叉子的两个哲学家,不能同时用它。)

Así que de forma natural cada tenedor puede representarse con un semáforo con comportamiento binario:

所以每把叉子很自然地用一个二元信号量表示:

Si está abierto (1), el tenedor correspondiente está libre

值为 1(开着)→ 叉子空闲,可以拿。

Si está cerrado (0), el tenedor está siendo utilizado.

值为 0(关着)→ 叉子正被占用,要等。

术语要对上:这里说的「abierto / cerrado」就是二元信号量的 1 / 0,等价于「libre / ocupado」。考试问「如何用信号量为一把叉子建模」,标准答:二元信号量,初值 1;拿叉子 = sem_wait,放叉子 = sem_post。三句话说完,别绕。
为什么不用整型变量 + 忙等?因为 wait/post 是原子的,而且阻塞时不烧 CPU。这就是 Tema 3 前半段(espera activa)到后半段(semáforos)的进化逻辑——考试爱出这种「对比两种方案」的题。
p.29

代码 ①:头文件与叉子初始化

▸ 原页截图 p.29原讲义第 29 页
#include <pthread.h>
#include <stdio.h>
#include <semaphore.h>
#define MAXF 5
//Semaforos
sem_t ten[MAXF];
int main () {
  pthread_t th[5];
  pthread_attr_t attr;
  int i, id[5];
  for (i=0; i<MAXF; i++) {
    sem_init(&ten[i], 0, 1);
  }

#define MAXF 5

叉子总数(= 哲学家数)= 5。

sem_t ten[MAXF];

信号量数组:一把叉子一个元素,下标 0–4。

sem_init(&ten[i],0,1);

每把叉子都初始化成 1(空闲)——这就是「五个二元信号量」。

注意 sem_t ten[MAXF] 是数组,不是单个信号量。这是本题与生产者—消费者的结构差异:资源有 N 份同类实例时用数组,下标就是资源编号(这里是叉子编号)。考试若问「为什么用数组」,答:资源可枚举、每个实例独立互斥。
记忆钩子:叉子数组 = 一排挂钩,ten[i] 就是第 i 号挂钩上有没有叉子🍴
p.30

代码 ②:创建 5 个哲学家线程

▸ 原页截图 p.30原讲义第 30 页
  pthread_attr_init(&attr);
  for (i=0; i<MAXF; i++) {
    id[i]=i;
    pthread_create(&th[i], &attr, HebraF, &id[i]);
  }
  pthread_join(th[1], NULL);   // ← 讲义只 join 了第 1 个
  return 0;
}

id[i]=i;

给每个线程一个编号,必须用数组存——不能直接用循环变量 i 的地址。

pthread_create(&th[i],&attr,HebraF,&id[i]);

创建线程,把编号地址当参数传进去。

两处经典陷阱,讲义都踩了或差点踩:
① pthread_join(th[1],NULL) 只等了一个线程,其余 4 个没 join。正确写法应循环 for(i=0;i<MAXF;i++) pthread_join(th[i],NULL);。这是讲义笔误,抄作业要改。
② 若写成 pthread_create(..., &i)(直接传循环变量地址),5 个线程可能读到同一个最终值 5 → 越界。所以必须先存进 id[i],再传 &id[i]。
「为什么传 &id[i] 而不是 &i」是必考小陷阱。标准答:循环变量 i 在循环结束后还会变,所有线程共享同一块地址;传到线程里的指针必须在整个线程生命周期内保持稳定。所以为每个线程准备独立存储。
线程函数签名必须是 void *HebraF(void *argg),所以参数一律按 void* 传、在函数里再 ((int*)argg) 转回来。这是 POSIX 线程的固定套路,背下来。
p.31

代码 ③:哲学家主循环 · 朴素解法会死锁

▸ 原页截图 p.31原讲义第 31 页
void *HebraF(void *argg ){
  int id;
  id = *((int *) argg);
  while (1) {
    sem_wait(&ten[id]);              // 先拿左边的
    sem_wait(&(ten[(id+1)%5]));      // 再拿右边的
    sleep(2);//come
    sem_post(&(ten[(id+1)%5]));
    sem_post(&ten[id]);
    sleep(5);//piensa
  }
}

id = *((int *) argg);

把 void* 转回 int*,再取值 → 我自己的编号。

sem_wait(&ten[id]);

拿左手叉子(第 id 号)。

sem_wait(&(ten[(id+1)%5]));

拿右手叉子(第 id+1 号;%5 让第 5 人的右手绕回第 0 号 → 环形)。

Esta solución puede bloquear si todos los filósofos intentan comer simultáneamente y cogen su primer tenedor

原文页注:如果 5 个人同时想吃、并且都先拿起了第一把叉子,这个解法会阻塞。

哲学家先拿(左)再拿(右)结果
F0ten[0] ✓ten[1] ✗等 F1 放叉
F1ten[1] ✓ten[2] ✗等 F2 放叉
F2ten[2] ✓ten[3] ✗等 F3 放叉
F3ten[3] ✓ten[4] ✗等 F4 放叉
F4ten[4] ✓ten[0] ✗等 F0 放叉 → 环闭合
全员各持一把各等一把DEADLOCK 💀
这就是死锁四个必要条件的完美标本,答题按四个条件列:
① 互斥:叉子一次只能一人用;
② 占有并等待:拿到左手还等着右手;
③ 不可剥夺:别人不能强行抢走你手里的叉子;
④ 循环等待:F0→F1→F2→F3→F4→F0。
只要破坏任意一个就能解——p.32 破坏的是第 ④ 个(限制同时进场人数)。
别把「死锁」和「饥饿」混了:这里是互相等、永久卡死 = deadlock;而 p.43 的读者—写者里写者一直抢不到 = inanición / starvation(饿死,但系统还在动)。考试名词千万别写反。
记忆钩子:「五个人、五把叉、每人夹住一把、谁都不肯松」——像五个朋友抢火锅里的最后五片肉,一人夹一片,谁也吃不到🥢
p.32

解法:加一个「椅子」信号量,初值 4

▸ 原页截图 p.32原讲义第 32 页
  …………..
  id = *((int *) argg);
  while (1) {
    sem_wait(&sillas);                 // 先抢椅子(最多 4 人进场)
    sem_wait(&ten[id]);
    sem_wait(&(ten[(id+1)%5]));
    sleep(2);//come
    sem_post(&(ten[(id+1)%5]));
    sem_post(&ten[id]);
    sem_post(&sillas);                 // 吃完还椅子
    sleep(5);//piensa
  }
}
sem_init (&sillas, 0, 4);

Por la disposición en la mesa, a lo sumo 2 filósofos pueden comer simultáneamente.

由于圆桌的布局,最多只有 2 个人能同时吃。

Al siguiente le falta como mínimo un tenedor.

因为下一个人(第 3 个想吃的)至少缺一把叉子。

Una forma de evitar el bloqueo es utilizar un semáforo general (sillas) que deje pasar a los cuatro primeros filósofos que quieren comer, bloqueando al quinto, si también quiere comer.

避免死锁的办法:用一个计数信号量 sillas,放前 4 个想吃的人进场,挡住第 5 个(如果他也想吃)。

为什么初值是 4 而不是 5?核心推理:5 个人同时进场 → 每人拿一把 → 环闭合 → 死锁;最多 4 个人在场 → 至少有一把叉子空着 → 总有人能凑齐两把 → 环闭不上 → 不会死锁。这个「N−1」是本题标准答案,背死它。
语义陷阱:sillas 管的是「允许进场的人数」,不是物理椅子。它其实是在破坏循环等待(4 个位置 + 5 个资源,凑不出环)。别答「椅子信号量保护叉子」——它保护的是「同时竞争的人数」。
还有别的解法,考试可能让你举两个:
① 非对称:奇数号先拿左、偶数号先拿右(打破环路方向);
② 一次性拿两把:用一个 mutex 把「拿左+拿右」变成原子操作;
③ 奇偶分组 / try-wait 失败就放回(回退策略)。
讲义选的 ① 号方案(限制进场数),因为它最简单、最省一次系统调用。
记忆钩子:「五个人只给四把椅子」——总有一个站着,站着的人就凑不出环,死锁自然破局🪑

六、读者—写者问题 · p.33–p.50

p.33

问题定义:两种线程抢一个数据库

▸ 原页截图 p.33原讲义第 33 页

El problema de los lectores/escritores representa un modelo de sincronización entre dos tipos de hebras (los lectores y los escritores) que acceden a un recurso compartido, típicamente una base de datos (BD).

读者—写者问题刻画的是两类线程(lector 读者 / escritor 写者)访问同一共享资源的同步模型,典型场景是数据库(BD, base de datos)。

Las hebras de tipo escritor acceden a la BD para actualizarla.

写者访问数据库是为了修改它。

Las hebras de tipo lector leen los registros de la BD.

读者只是读取数据库里的记录。

角色西语干什么能否并行
读者lector只读(read)读者 ↔ 读者:可以(任意多个)
写者escritor修改(update)写者 ↔ 任何人:不行(完全互斥)
一句话概括本题的全部同步规则,考试直接写这句:
«Los escritores acceden en exclusión mutua con cualquier otra hebra; cualquier número de lectores puede acceder simultáneamente.»
(写者与任何线程互斥;任意数量的读者可同时访问。)
把这句话背熟,p.34 和 p.35 两页就都不用再想了。
记忆钩子:「读可以组团,写必须包场」——读者是组团游客,写者是包场装修队📚
p.34

写者的同步条件:独占全场

▸ 原页截图 p.34原讲义第 34 页

Condición de sincronización para los escritores:

写者的同步条件:

Acceden a la BD en exclusión mutua con cualquier otra hebra de tipo lector o escritor

访问数据库时,与任何其他线程(读者或写者)互斥。

图中元素含义箭头规则
l0 … l45 个读者线程(lectores)只有一个能连到 BD
e0 … e23 个写者线程(escritores)只有一个能连到 BD
BD共享数据库(临界资源)同一时刻至多一条连线有效
这张图考的是「谁能和谁同时连」:
写者 e1 在写时,l0–l4 全部不能进、e0/e2 也不能进——注意是「与任何其他线程互斥」,包括其他写者。别只答「写者和读者互斥」,漏掉「写者之间也互斥」要扣分。
术语坑:西语 exclusión mutua 在这里的含义是「排他」,不是「加锁保护一小段代码」。写者整个访问期间都独占 BD,读者则靠「第一个进 / 最后一个出」来间接把门。
p.35

读者的同步条件:可以组团进

▸ 原页截图 p.35原讲义第 35 页

Condición de sincronización para los lectores:

读者的同步条件:

Cualquier número de lectores puede acceder simultáneamente a la BD.

任意数量的读者可以同时访问数据库。

为什么读者能组团?因为只读不写不会破坏数据一致性。这是本题与生产者—消费者的本质区别:生产者—消费者里「缓冲区」每次只能一个人动(所以必须 mutex),而这里「读」本身是可共享的操作。
推论:读者之间不需要互斥,只需要和写者互斥。
高频简答:「为什么读者之间不需要互斥?」标准答:读操作不改变共享资源状态,多个读并发执行的结果与串行执行一致,因此不构成竞争条件(condición de carrera)。关键词 condición de carrera 写上,分数立刻高一档。
记忆钩子:「看书的人互不干扰,装修的人必须清场」——所以门锁只挡写者🚧
p.36

伪代码骨架:四个协议函数

▸ 原页截图 p.36原讲义第 36 页
void Lector ( void id){
  while (1){
    entraLector(id);
    //lector id en la BD
    saleLector(id);
  }
}
Void Escritor (void id) {
  while (1){
    entraEscritor(id);
    //escritor id en la BD
    saleEscritor(id);
  }
}
void main(){
  Se crean NE hebras escritoras
  Se crean NL hebras lectoras
}

Todos los lectores ejecutan los mismos protocolos de entrada y salida

所有读者执行相同的进入 / 离开协议。

Todos los escritores ejecutan los mismos protocolos de entrada y salida

所有写者也执行相同的进入 / 离开协议。

La BD no hace falta modelarla

数据库本身不需要建模——我们只关心「谁能进、几个人能进」。

讲义笔误(只标注、不改写):第二段写成了 Void Escritor,C 语言的 void 全小写。手写代码时写错直接编译失败,别照抄。
「为什么 BD 不用建模?」这是概念题:因为题目只关心访问控制(互斥 / 共享),不关心数据内容。把 BD 当成一个黑盒临界资源,进入协议 + 离开协议才是要写的代码。答题时提到「abstracción del recurso(资源抽象)」加分。
四个函数名是约定俗成的考试标准命名:entraLector / saleLector / entraEscritor / saleEscritor。你答卷上只要写出这四个名字,阅卷人立刻知道你要干什么,比自创名字省事。
p.37

第一版 ①:写者用二元信号量 escribiendo

▸ 原页截图 p.37原讲义第 37 页

La condición de sincronización de los escritores puede modelarse con un semáforo (con comportamiento binario) escribiendo que garantice la exclusión mutua de los escritores en la BD

写者的条件可以用一个二元信号量 escribiendo(「正在写」)来建模,保证写者之间对 BD 的互斥。

sem_init (&escribiendo, 0, 1);

void entraEscritor(int id) {
  sem_wait(&escribiendo);
}
void saleEscritor(int id){
  sem_post(&escribiendo);
}
命名要会解释:escribiendo 是西语「正在写」的副动词。语义上它就是一把 mutex:1 = BD 空闲、0 = 有人正在里面。考卷上写「escribiendo 是一个充当 mutex 的二元信号量」最稳。
这里只解决了「写者 ↔ 写者」互斥。读者还完全没被管——所以下一批页(p.39)才要引入 nLectores + mutex。看讲义时务必分清每一版解决了哪一半问题,这是本章的叙事主线。
id 参数在这两个函数里没用到,因为写者协议对所有写者完全一样,不需要区分是谁。这是「协议与身份无关」的体现,考试不用纠结。
p.38

第一版 ②:写者进入的两种情形

▸ 原页截图 p.38原讲义第 38 页

Cuando un escritor quiere entrar en la BD

当一个写者想进入数据库时:

Si escribiendo = 1, entonces la BD está vacía. En este caso, pone escribiendo a 0, e impide que cualquier otra hebra (lectora o escritora) entre en la BD

若 escribiendo = 1:说明 BD 空着;写者把信号量置 0,于是任何其他线程(读者或写者)都进不来。

Si escribiendo = 0, hay alguien en la BD. En este caso, espera en el semáforo escribiendo, hasta que pueda entrar en solitario.

若 escribiendo = 0:说明有人在里面;写者就在 escribiendo 上等待,直到能独自进去。

观察到的值物理含义wait 的效果(原子地)
escribiendo = 1BD 空闲值变 0,立刻通过 → 关门包场
escribiendo = 0有人在里面(写者或读者群)值不变,线程阻塞排队
这段是「用一句话解释 wait 语义」的标准模板,背下来能套用到任何信号量题:
«Si vale 1, lo pone a 0 y entra; si vale 0, se bloquea hasta que alguien haga post.»
(值为 1 就置 0 进入;值为 0 就阻塞,直到有人 post。)
记忆钩子:「1 是空房,进去就锁门;0 是有人,门口排队」——写者就是这么霸道🏠
p.39

第一版 ③:读者的核心技巧 —— 计数器 + mutex

▸ 原页截图 p.39原讲义第 39 页

La condición de sincronización de los lectores puede modelarse con una variable entera nLectores, que cuenta el número de lectores que hay en la BD,

读者的条件可以用一个整型变量 nLectores 建模——数一数现在有几个人在库里读,

y un semáforo mutex que garantiza el uso en exclusión mutua de nLectores.

再加一个信号量 mutex,保证对 nLectores 这个计数器的互斥修改。

int nLectores = 0;
sem_init(&mutex, 0, 1);

void entraLector(int id) {
  sem_wait(&mutex);        // 保护计数器
  nLectores++;
  if (nLectores==1) sem_wait(&escribiendo);  // 我是第一个 → 关门
  sem_post(&mutex);
}
这是全章最精妙的三行,也是必考代码。核心思想一句话:「第一个进的人负责锁门,最后一个人负责开门」。这样读者群整体表现为一个大的临界区,对写者完全互斥;而读者之间畅通无阻(只有 nLectores++ 那一瞬排队)。考试若让写 entraLector,就这三行加锁 + 一行 if,别多写。
为什么 nLectores 需要 mutex?因为它是共享变量。nLectores++ 在机器层面是「读-改-写」三步,若两个读者同时执行,可能都读到 0、都加 1,最后结果只有 1 → 两个人都以为自己是第一个,就都去 sem_wait(&escribiendo),第二个永远等不到 → 死锁。这就是「计数器的竞争条件」,考试高频。
记忆钩子:「进门签到,第一人锁门,最后一人开门」——签到本必须排队写(mutex)✍️
p.40

第一版 ④:读者进入的四种情形

▸ 原页截图 p.40原讲义第 40 页

Cuando un lector quiere entrar en la BD,

当一个读者想进入数据库时:

si no hay ningún escritor en la BD, entonces escribiendo = 1

情形 A:库里没有写者 → escribiendo = 1。

si es el primer lector que lo intenta, pone nLectores a 1, cierra el semáforo escribiendo y entra

A1:他是第一个读者 → nLectores = 1,关掉 escribiendo(挡住写者),进入。

Hay uno o más lectores en la BD sii escribiendo = 0

等价关系:库里有 ≥1 个读者 ⇔ escribiendo = 0。

en otro caso, incrementa nLectores, y entra

A2:不是第一个 → 只把计数器 +1,直接进入(不碰 escribiendo)。

Si hay un escritor en la BD, entonces escribiendo = 0

情形 B:库里有写者 → escribiendo = 0。

si es el primer lector que lo intenta, pone nLectores a 1, y se bloquea en escribiendo

B1:他是第一个读者 → nLectores = 1,然后阻塞在 escribiendo 上。

si no es el primer lector, se bloquea en mutex

B2:不是第一个 → 因为前一个读者还握着 mutex(它阻塞在 escribiendo 时没放锁),所以这个读者阻塞在 mutex 上。

场景escribiendo第一个读者后续读者
A:无写者1nLectores=1;wait(escribiendo)→0;进入nLectores++;直接进入
B:有写者0nLectores=1;阻塞在 escribiendo(握着 mutex)阻塞在 mutex
B2 这个细节是阅卷人最爱的追问:「第二个读者为什么阻塞在 mutex 而不是 escribiendo?」标准答:第一个读者在持有 mutex 的情况下阻塞在 escribiendo,mutex 还没 post,所以后来者连计数器都改不了,只能堵在 mutex 上。这不是 bug(写者出门后会 post escribiendo,链条自动解开),但确实降低了并发度——这是后续改进的伏笔。
记忆钩子:「第一人卡在门口,后面全堵在签到台」——门没开,签到本也不撒手😅
p.41

第一版 ⑤:saleLector —— 最后一人开门

▸ 原页截图 p.41原讲义第 41 页

Cuando un lector sale de la BD,

当一个读者离开数据库时:

si es el último lector que queda en la BD, decrementa nLectores a 0, libera el semáforo escribiendo (escribiendo = 1) y sale

若他是最后一个读者:计数器减到 0,释放 escribiendo(置 1),离开。

Si despierta a una hebra debe ser necesariamente un escritor

此时被唤醒的线程必然是写者(因为读者群里已经没人了)。

si no es el último lector que lo intenta, simplemente decrementa nLectores, y sale

若不是最后一个:只把计数器 −1,直接离开(不碰 escribiendo)。

void saleLector(void id)  {
  sem_wait(&mutex);          // 保护计数器
  nLectores--;
  if (nLectores==0) sem_post(&escribiendo);  // 我是最后一个 → 开门
  sem_post(&mutex);
}
和 entraLector 完全镜像:进入时 1→变第一个就锁;离开时 0→变最后一个就开。答题时把这两个函数并排写在纸上,中间画个 ⇄,阅卷人一看就知道你掌握了「首尾对称」这个设计模式。
注意顺序:先改计数器、再判 0、再 post,最后才 post mutex。
别把 if (nLectores==0) 写成 if (nLectores==1)!减完之后判断的是「还剩几个」。写错的话门永远不会开,写者被永久饿死。
这里 sem_post(&escribiendo) 在 sem_post(&mutex) 之前,有没有问题?没有——被唤醒的写者只会去抢 escribiendo,它不碰 mutex,所以不会形成交叉等待。这属于「安全但可以更优」的边界,考试不追究。
p.42

第一版 ⑥:写者出门 · 链式唤醒

▸ 原页截图 p.42原讲义第 42 页

Cuando un escritor sale de la BD, libera el semáforo escribiendo

写者离开时,释放 escribiendo。

lo que puede despertar a un escritor,

这可能唤醒另一个写者;

o al primer lector, que espera en la sección crítica.

也可能唤醒第一个读者(它正阻塞在临界区入口)。

En este caso, el lector despertado, hace post() sobre mutex, lo que puede despertar a otro lector, que hace lo mismo, y así sucesivamente.

这种情况下,被唤醒的读者会 post(mutex),这又可能唤醒下一个读者,它再做同样的事……如此链式传递。

void saleEscritor(int id){
  sem_post(&escribiendo);
}
void entraLector(int id) {
  sem_wait(&mutex);
  nLectores++;
  if (nLectores==1) sem_wait(&escribiendo);
  sem_post(&mutex);
}
步谁动作信号量变化结果
1escritorpost(escribiendo)escribiendo: 0→1唤醒 L1(第一个读者)
2L1post(mutex)mutex: 0→1唤醒 L2(堵在 mutex 的)
3L2nLectores++ → post(mutex)mutex 释放唤醒 L3
4L3…Ln重复同样动作—读者群全部进场
这个「链式唤醒 / 多米诺唤醒」是本章最难描述的机制,考试喜欢让你画时序。一句话总结:写者只负责开第一道闸,后面靠读者之间互相 post(mutex) 传递下去。注意:L1 的 sem_wait(&escribiendo) 是在醒来后完成的,它会把 escribiendo 重新置 0,于是读者群再次把门锁上——所以后面来的写者又得等。
记忆钩子:「一个人推倒第一张骨牌,剩下的自己倒」——这排多米诺就是 mutex 的传递链🀄
p.43

第一版的致命缺陷:写者被饿死

▸ 原页截图 p.43原讲义第 43 页

Es fácil ver que con esta solución los lectores pueden hacerse con el control de la BD, impidiendo el acceso de forma indefinida a los escritores.

很容易看出:这个解法里读者可能霸占数据库,让写者无限期进不去。

时刻读者动作nLectoresescribiendo写者状态
t0L0 进入(第一个)10E0 到达,阻塞
t1L1 进入20E0 仍在等
t2L0 离开10不是最后一个 → 不开门
t3L0 又回来重新进入20E0 永远等不到 escribiendo=1
区分两个名词,考试必考:
• deadlock(死锁):所有人都不动,系统永久卡死(p.25 那种)。
• inanición / starvation(饥饿):系统还在跑,但某个线程永远轮不到。
这里是写者饥饿:只要读者流不断,nLectores 永远 ≥1,escribiendo 永远是 0,写者无限期等待。答出这两个词的区别,直接给高分。
这版叫「读者优先(prioridad a los lectores)」解法。它没有破坏正确性(不会数据错乱),只是不公平(injusto)。所以 p.44 的标题不是「修正错误」,而是「公平版本」——措辞别写错。
记忆钩子:「读者像早高峰地铁,一波接一波,写者在站外等到天荒地老」🚇
p.44

第二版:对写者公平(justa para los escritores)

▸ 原页截图 p.44原讲义第 44 页

La idea de esta solución es la siguiente:

这一版的核心思路是:

Aunque haya lectores en la BD, si hay algún escritor esperando, cualquier lector que quiera entrar debe esperar a que entren los escritores que esperan

即使库里已经有读者,只要有写者在排队,新来的读者就必须先等写者进完。

Esta nueva versión se basa en la solución anterior, pero se complica un poco…

新版基于上一版,但稍微复杂一点点……(马上要多一个信号量 leyendo)

版本规则后果
第一版(lectores)读者随到随进,不看有没有写者在等写者 starvation
第二版(justa)有写者在等 → 新读者也得排队写者能进 → 公平
这页是承上启下的概念页,考试常以简答出现:「如何让读者—写者问题对写者公平?」标准答:增加一个信号量(leyendo),让「有写者在等」这个事实对后来的读者可见,从而挡住新读者。下一批页 p.45–p.48 就是这个思路的代码实现。
注意措辞的精确性:这一版不是「让写者优先(prioridad a los escritores)」,而是「不让写者饿死」。真正的写者优先会让读者饿死——那又是另一个极端。讲义用的是公平(justo),很克制。
记忆钩子:「门口挂个牌子:里面有人在等包场,新游客稍等」——这块牌子就是 leyendo🪧
p.45

第二版 ①:写者进场 —— nEscritores + leyendo

▸ 原页截图 p.45原讲义第 45 页

Cuando llega un escritor, incrementa la variable nEscritores.

写者到达时,先把 nEscritores(排队写者数)加一。

Si es el primero, cierra el semáforo leyendo (para bloquear a los lectores que lleguen a continuación)

如果他是第一个写者 → 关掉 leyendo,把随后到达的读者挡在门外。

Si no es el primero, no ejecuta wait de leyendo para no bloquearse.

如果他不是第一个 → 不执行 wait(leyendo),否则会把自己也堵住。

Pero se pueden seguir bloqueando en escribiendo igual que antes

但他们仍然可能像上一版一样阻塞在 escribiendo 上。

A continuación, accede, si es posible, a la BD en exclusión mutua (como en la versión anterior)

接着,如果可能,以互斥方式进入数据库(与上一版相同)。

void entraEscritor(int id) {
  sem_wait(&mutex2);              // 保护 nEscritores
  nEscritores++;
  if (nEscritores == 1) sem_wait(&leyendo);  // 第一个 → 挂「停止入场」牌
  sem_post(&mutex2);
  sem_wait(&escribiendo);         // 真正的互斥进场(可能阻塞)
}
关键设计点:leyendo 是「读者入场闸门」,1 = 允许读者进、0 = 暂停放读者进来。为什么只有第一个写者去关它?因为 wait(leyendo) 只有一个能成功(它会从 1 变 0),后面的人再 wait 就自己把自己堵死了。所以用 nEscritores==1 做「只让第一个人关门」的判断——这和 p.39 读者那边 nLectores==1 的套路完全同构。
注意 sem_wait(&escribiendo) 放在 post(mutex2) 之后、锁外。为什么?因为这里可能长时间阻塞(等库里的人走光),如果握着 mutex2 等,其他写者连 nEscritores 都改不了。这个「计数在锁内,阻塞在锁外」的模式,是本章反复出现的高级技巧。
记忆钩子:「写者来了先举手,第一个去把读者闸门拉下」——后面来的写者只需排队等包场🚩
p.46

第二版 ②:读者进场要多等一道 leyendo

▸ 原页截图 p.46原讲义第 46 页
void entraEscritor(int id) {
  sem_wait(&mutex2);
  nEscritores++;
  if (nEscritores == 1) sem_wait(&leyendo);
  sem_post(&mutex2);
  sem_wait(&escribiendo);
}
void entraLector(int id) {
  sem_wait(&leyendo);          // ★ 新增:先看闸门
  sem_wait(&mutex1);
  nLectores++;
  if (nLectores==1) sem_wait(&escribiendo);
  sem_post(&mutex1);
  sem_post(&leyendo);          // ★ 进完立刻把闸门抬起
}

Un lector que llega, si leyendo está cerrado, espera en leyendo.

读者到达时,如果 leyendo 是关的,就在 leyendo 上等。

Por lo tanto si hay escritores esperando, el lector no entra en la BD.

所以只要有写者在等,读者就进不了数据库——这就是公平性的实现。

新版 entraLector 只比旧版多了两行:进门 wait(leyendo)、出门 post(leyendo)。但别小看它们:wait 是「看有没有写者在等」,post 是「我进完了,后面的人可以看了」。注意 post(leyendo) 在 post(mutex1) 之后——先把计数器保护放开,再放闸门。
讲义没有列出这一版新增信号量的 sem_init。按语义必须补上:sem_init(&leyendo,0,1)(闸门初始开放)、sem_init(&mutex1,0,1)、sem_init(&mutex2,0,1)、sem_init(&escribiendo,0,1),且 nLectores = nEscritores = 0。考试若要求「完整初始化」,这五行必须写出来。
为什么 leyendo 能挡住新读者?因为第一个写者把它置 0 之后就再没 post 回来,直到所有写者走光(p.47)。所以它的值就是一个全局标志:「现在有没有写者在排队」。
p.47

第二版 ③:saleEscritor —— 最后一个写者抬起闸门

▸ 原页截图 p.47原讲义第 47 页

Un escritor que deja la BD decrementa nEscritores.

写者离开时,nEscritores 减一。

Si ya no hay escritores esperando, abre el semáforo leyendo.

如果已经没有写者在等了 → 打开 leyendo(重新放读者进来)。

En cualquier caso, libera la exclusión mutua de la BD

无论哪种情况,都要释放对 BD 的互斥(post(escribiendo))。

void saleEscritor(int id) {
  sem_wait(&mutex2);
  nEscritores--;
  if (nEscritores == 0) sem_post(&leyendo);   // 最后一个写者 → 抬闸门
  sem_post(&mutex2);
  sem_post(&escribiendo);                    // 无论如何都放锁
}
离开时 nEscritores是否 post(leyendo)理由
> 0(还有写者在等/在写)否公平策略:闸门继续关着,读者还得等
= 0(写者全走光)是没人抢了,放读者进场
注意这里的顺序,是考试重点:post(leyendo) 在 post(mutex2) 之前,而 post(escribiendo) 在最后。
为什么 escribiendo 最后放?因为要等「计数器 + 闸门」都处理完,才算真正离开 BD。答题时把这三步按顺序写清楚:「减计数 → 若为 0 抬闸 → 释放互斥」。
记忆钩子:「最后一个写者走人,顺手把读者闸门抬起来」——像商场的卷帘门,最后一个顾客出来才拉下/抬起🛒
p.48

第二版 ④:saleLector 完全不变

▸ 原页截图 p.48原讲义第 48 页

El protocolo de salida para los lectores no cambia.

读者的离开协议不变(和第一版一模一样)。

void saleLector(int id) {
  sem_wait(&mutex1);
  nLectores--;
  if (nLectores==0)  sem_post(&escribiendo);  // 最后一个读者 → 放写者
  sem_post(&mutex1);
}
「为什么 saleLector 不用改?」标准答:公平性是在「进场」处控制的(用 leyendo 挡住新读者),读者「离场」的逻辑与公平性无关——最后一个读者照样要放写者进来。所以只需改 entraLector / entraEscritor / saleEscritor 三个,saleLector 原封不动。
这种「只改三处」的对比题很常见,记住这个数量。
四个函数现在的分工可以画成一张表(考试可以先画表再写代码,思路立刻清楚):
entraLector = leyendo + mutex1 + 首个 wait(escribiendo)
saleLector = mutex1 + 末个 post(escribiendo)
entraEscritor = mutex2 + 首个 wait(leyendo) + wait(escribiendo)
saleEscritor = mutex2 + 末个 post(leyendo) + post(escribiendo)
p.49

第二版的遗留漏洞:post 唤醒了「错的人」

▸ 原页截图 p.49原讲义第 49 页

Supongamos que un lector y el primer escritor están ejecutando simultáneamente sus protocolos de entrada.

假设一个读者和第一个写者同时执行各自的进入协议。

En este caso, como el semáforo leyendo está cerrado, el primer escritor se bloquea en leyendo.

此时 leyendo 已被读者关成 0,所以写者阻塞在 leyendo 上。

Si más lectores quieren ejecutar su protocolo de entrada, también esperan en leyendo.

如果还有更多读者想进,他们也都在 leyendo 上等。

¿cómo aseguramos que cuando el lector sale de su protocolo de entrada despierta al escritor y no a un lector?

问题:怎么保证「读者做完进入协议、执行 post(leyendo)」时,唤醒的是写者而不是另一个读者?

步事件leyendo等待队列(示意)
1L1: wait(leyendo)0—
2E1: wait(leyendo)0E1
3L2: wait(leyendo)0E1, L2
4L1: post(leyendo)1可能唤醒 L2(信号量不保证 FIFO)
5L2 立刻把 leyendo 又置 00E1 继续等 → 写者饥饿
这页是全章最刁的一问,也是最容易被忽略的考点。核心事实:POSIX 信号量不保证公平(no garantizan justicia / FIFO)——post 只是「把值加一并唤醒某个等待者」,唤谁由实现决定。所以 L1 的 post 完全可能唤醒 L2,L2 立刻又关门,写者永远轮不到。
答题关键词:「semáforo no justo」。
注意这是第二版引入的新问题,不是第一版的老问题。第一版的问题是「没人挡读者」;第二版挡了,但挡得不彻底,因为「谁来被唤醒」不受控。所以 p.50 还要再加一个 mutex3——这是本章的第三层递进。
记忆钩子:「你喊了一声『下一位』,结果插队的人先冲进来」——因为信号量不是排队机,是摇号机🎲
p.50

终极版:mutex3 串行化读者进场

▸ 原页截图 p.50原讲义第 50 页
void entraLector(int id) {
  sem_wait(&mutex3);          // ★ 读者进场排队(一次只放一个读者进来办手续)
  sem_wait(&leyendo);
  sem_wait(&mutex1);
  nLectores++;
  if (nLectores==1) sem_wait(&escribiendo);
  sem_post(&mutex1);
  sem_post(&leyendo);
  sem_post(&mutex3);          // ★ 办完手续,放下一个读者
}
void entraEscritor(int id) {
  sem_wait(&mutex2);
  nEscritores++;
  if (nEscritores == 1) sem_wait(&leyendo);
  sem_post(&mutex2);
  sem_wait(&escribiendo);
}

Si utilizamos otro semáforo mutex3 se asegura que si hay un lector ejecutando su protocolo de entrada, el resto de los lectores esperan en mutex3,

再加一个 mutex3,保证当一个读者正在执行进入协议时,其他读者都堵在 mutex3 上,

por lo que cuando el lector ejecuta sem_post(&leyendo) despierta al escritor, si está bloqueado.

于是当这个读者执行 post(leyendo) 时,被唤醒的只可能是写者(如果它在等)。

Este código resuelve el problema, aunque se utilicen semáforos que no sean justos.

这段代码解决了问题,即使底层信号量并不公平。

为什么有效说明
读者被串行化同一时刻最多一个读者在「办进场手续」,其他人都卡在 mutex3
leyendo 的等待者变唯一执行 post(leyendo) 时,只有写者在 leyendo 上等 → 不可能唤醒错人
不依赖公平性即使信号量随机唤醒,也只有一个候选者 → 结果确定
这是本章的终极答案,也是压轴大题。标准答法四步:
① 问题:post(leyendo) 可能唤醒另一个读者,写者继续饿;
② 根因:信号量不保证公平;
③ 对策:加 mutex3,把读者的「进入协议」串行化;
④ 效果:post(leyendo) 时等待者唯一,从而与信号量公平性无关。
最后一句「aunque se utilicen semáforos que no sean justos」是原文的点睛之笔,务必抄上。
加锁顺序不能乱:mutex3 → leyendo → mutex1,释放顺序严格反过来:mutex1 → leyendo → mutex3。这又是一个「嵌套锁必须逆序释放」的实例,写错就死锁。
记忆钩子:「一次只放一个读者进闸机,闸机口就不会有人跟写者抢」——mutex3 就是那道闸机🚪
p.51

本章小结:En resumen…

▸ 原页截图 p.51原讲义第 51 页

Los semáforos son uno de los mecanismos más habituales para sincronización entre procesos y hebras

信号量是进程与线程同步最常用的机制之一。

Prácticamente cada sistema operativo o lenguaje de programación tienen implementaciones de semáforos

几乎每个操作系统、每种编程语言都有信号量的实现。

Son un mecanismo muy versátil y eficiente pero que, al mismo tiempo, hay que utilizar con cuidado para evitar situaciones de fallo

它通用、高效,但同时也必须小心使用,否则会出问题(死锁、饥饿等)。

用信号量能解决本章对应页
互斥(exclusión mutua)p.12–p.16(R1 / R1')
同步 / 条件等待(sincronización)p.17–p.25(C1 / C2)
资源计数(recursos contables)p.21–p.22、p.32(sillas)
读者—写者这类复杂协议p.33–p.50
本章的考试地图(按出现频率排序):
① 生产者—消费者三信号量代码 + 死锁顺序(p.22 / p.25);
② 哲学家 sillas 初值为什么是 4(p.32);
③ 读者—写者 nLectores==1 那三行(p.39);
④ 公平版的 leyendo + mutex3(p.45–p.50);
⑤ 概念辨析:死锁 vs 饥饿、互斥 vs 同步。
把这五块拿下,本章基本满分。
记忆钩子:「信号量是把好刀,能切菜也能切手」——所以每次写 wait 都要问一句:我会不会握着锁等别人?🔪

七、专有名词总表

A–V · 全章 51 页

专有名词速记表(A–V)

按西语字母排序,点页码直接跳回对应页块。最后一列是「一句话记住 / 易错点」——考前只扫这一列也能救急。

西语术语中文页一句话记住 / 易错点
A
adquirir获取(一个许可)p.10wait 成功 = 抢到一个许可;失败 = 去排队
almacenar存放(数据进缓冲区)p.24生产者动作,必须在 mutex 内部做
atomicidad原子性:wait/post 不可被打断p.4「看起来一步完成」——这是信号量能防竞态的根本原因
B
binario (semáforo)二元信号量:取值只有 0 / 1p.3就是「一把锁」,哲学家的一把叉子
bloqueo阻塞:拿不到许可就挂起,不占 CPUp.5和 Parte 1 的「忙等」相对;谁被挂起由实现决定
buffer缓冲区:生产者放、消费者取的中转区p.23容量 N 有限 ⇒ 必须有 hayEspacio
buffer circular环形缓冲区:下标取模回绕p.23本讲义用 % MAXT 实现回绕,别写成无限数组
C
condición de carrera竞态条件:结果取决于执行次序p.17不是「跑得快」,是「顺序不同结果不同」
condiciones de sincronización同步条件:C1 不满不能取、C2 不满不能放p.17这里没有互斥问题,只有「等条件」问题
consumidor消费者:从缓冲区取数据的线程p.17它的 wait 顺序与生产者镜像相反
contador de permisos许可计数器:信号量的本质就是一个整数p.3post 加一、wait 减一;减到负数就排队
D
deadlock / interbloqueo死锁:所有线程都阻塞、等一个永不发生的事件p.25本章王牌考点:握着锁去等条件 = 必死
datos (hay datos)有数据:消费者可以取的条件p.21hayDatos 初值 0,生产者每放一个就 post 一次
E
EBUSY设备忙:sem_destroy 时有线程在等就报这个错p.8销毁信号量前必须确保没人在等
escribiendo「正在写」信号量:写者独占全场的开关p.37写者一进门就 wait 它,读者组团时由第一个人 wait
escritor写者:必须独占访问数据库的线程p.33写者 vs 读者 = 独占 vs 共享
exclusión mutua互斥:同一时刻只允许一个线程进临界区p.12正是 R1;信号量初值 1 就够
F
fallo故障 / 失效情形(死锁、饥饿等)p.51讲义原话:强大但「hay que utilizar con cuidado」
filósofo哲学家:需要两把叉子才能吃饭的线程p.265 个人 5 把叉子,朴素解法必死锁
G
general (semáforo)通用信号量:取值 0…N,用于计数资源p.3二元信号量是它的特例(N=1)
grupo de lectores读者团体:多个读者可同时进场p.35「第一个进、最后一个出」才需要动 escribiendo
H
hayDatos「有数据」信号量:消费者等的条件p.21初值 0;漏了它消费者会读到空缓冲区
hayEspacio「有空位」信号量:生产者等的条件p.19初值 N(缓冲区容量);漏了它生产者会覆盖未读数据
hebra线程(西语教材常用 hebra / hilo)p.14pthread_create 创建的就是 hebra
I
inanición饥饿:某个线程永远轮不到p.43读者不断涌入 ⇒ 写者饿死;解法是对写者公平
inicializar初始化(sem_init 的第二个参数决定进程内/进程间)p.7线程之间用 0,跨进程才用非 0
L
lector读者:只查询、可并发进入的线程p.33读者之间不互斥,这是本题的核心
leyendo「正在读」信号量:公平版的闸门p.45写者进/出各 post 一次;读者进场先 wait 它
M
memoria compartida共享内存:本主题的通信媒介p.1共享带来耦合,耦合带来竞态 ⇒ 才需要同步
mutex互斥锁信号量(初值 1),保护共享变量p.22只保护「几行变量操作」,不要包住 wait 条件
mutex1 / mutex2 / mutex3保护 nLectores / nEscritores / 读者进场顺序p.39mutex3 只在终极版出现(p.50)
N
nEscritores写者计数器(公平版新增)p.45第一个写者关闸门,最后一个写者开闸门
nLectores读者计数器:0 → 1 时抢全场,1 → 0 时还全场p.39加减必须在 mutex1 内部完成
P
permisos许可:信号量里可被领取的「票」p.3没有许可就等——这是信号量语义的一句话版
post释放 / 唤醒:许可 +1,必要时叫醒一个等待者p.9西语教材也写作 V(...);post 永远不会阻塞
postprotocolo后协议:临界区之后 release + 通知的那两行p.24顺序也要对:先放锁,再 post 条件
preprotocolo前协议:进临界区前 wait 的那几行p.25顺序颠倒 = 死锁(本章第一大坑)
productor生产者:向缓冲区写数据的线程p.17先等空位、再拿锁
R
R1互斥性质:任何时刻至多一个线程在临界区p.12信号量初值 1 + wait/post 夹住 = R1
R1'推广的互斥:至多 M 个线程同时进入(M < N)p.16把初值从 1 改成 M 就行,别改代码结构
recurso资源:被共享、需要保护的对象p.3叉子、缓冲区、数据库都是资源
S
semáforo信号量:带许可计数的同步原语p.3一个整数 + 两个原子操作,就这两样
sem_destroy销毁信号量p.8有等待者时返回 EBUSY
sem_getvalue读取当前值p.11读到的值是瞬时快照,不能拿来做判断
sem_init初始化(信号量、共享标志、初值)p.7线程间共享填 0;初值决定语义
sem_postPOSIX 的「V 操作」p.9释放顺序错了照样死锁
sem_trywait非阻塞申请:拿不到立刻返回错误p.10不会挂起,但也不会等——别用它替代 wait
sem_waitPOSIX 的「P 操作」p.10拿不到许可就阻塞,这是「躺平等」
sillas椅子信号量:哲学家解法里限制同时上桌人数p.32初值 4(不是 5!)——破坏「循环等待」
sincronización同步:按条件先后协调,而不是抢独占p.17互斥管「不能同时」,同步管「必须先后」
T
tenedor叉子:哲学家问题的资源,一个二元信号量p.285 把叉子 = sem_t ten[5],初值全 1
traza执行轨迹:逐条列出各线程动作与信号量取值p.6考「会不会死锁」时,答题就靠画这张表
V
V(...) / P(...)经典记号:V = post(释放),P = wait(申请)p.4讲义两种写法混用,考试按题目给的写
valor信号量的值 = 当前剩余许可数p.11负数的含义是「还有几个人在排队」

八、四张必背速记卡

考前 10 分钟只背这一页
R1 · 互斥
至多 1 个线程进临界区。
实现:sem_init(&s,0,1) + wait(s) … post(s) 夹住。
R1' · 推广互斥
至多 M 个线程同时进(M < N)。
实现:初值写 M,代码一个字不改。
C1 · 不满不能取
消费者取之前必须确认「有数据」。
实现:hayDatos,初值 0。
C2 · 满不能放
生产者放之前必须确认「有空位」。
实现:hayEspacio,初值 N。
互斥 vs 同步
互斥:不能同时(抢独占)。
同步:必须先后(等条件)。
生产者—消费者里两者同时存在。
死锁 vs 饥饿
死锁:全都动不了,永远。
饥饿:有人一直在跑,只是某人永远轮不到。
死锁 ⊂ 更严重,饥饿更隐蔽。
hayEspacio vs hayDatos
hayEspacio:生产者等,初值 N。
hayDatos:消费者等,初值 0。
写反了 = 一上来就卡死。
第一版 vs 公平版
第一版:读者优先,写者可能饿死。
公平版:加 nEscritores + leyendo;
终极版再加 mutex3 串行化进场。
preprotocolo 顺序
生产者:wait(hayEspacio) → wait(mutex)。
消费者:wait(hayDatos) → wait(mutex)。
条件在前,锁在后,颠倒就死锁。
postprotocolo 顺序
先 post(mutex),再 post(条件)。
先放锁再喊人,否则被唤醒者也进不来。
哲学家 · sillas 初值
4,不是 5。
5 个人最多 4 个同时上桌 ⇒ 必然有人能拿到两把叉子。
读者—写者 · 三行核心
wait(mutex1) → nLectores++ → if(nLectores==1) wait(escribiendo)。
出门时 ==0 才 post。