跳转至

同步与互斥

同步问题--引出

Note

考纲

  1. 同步与互斥：
  2. 同步与互斥的基本概念；
  3. 同步与互斥的基本方法：软件实现方法；硬件实现方法；
  4. 锁；
  5. 信号量；
  6. 条件变量；
  7. 经典同步问题：生产者-消费者问题；读者-写者问题；哲学家进餐问题

并发进程/线程

在内存中同时存在的若⼲个进程/线程，由操作系统的调度程序采⽤适当的策略将它(们)调度⾄ CPU上运⾏，同时维护他们的状态队列。

  • 多个并发进程/线程从宏观上是同时在运行；
  • 从微观上看，他们的运⾏过程是走走停停；
  • 并发的进程/线程之间是交替执行

并发进程之间的关系：

  • 独立关系 ：并发进程分别在自己的变量集合上运⾏
  • 交互关系 ：并发进程执⾏过程中需要共享或是交换数据 ，交互的并发进程之间⼜存在着竞争和协作的关系

竞争（RACE）：假设有两个进程在临界区会出现交汇，当红色小车先到达后，会在临界区设置⼀个⼩红旗，此时蓝色小车只能处于等待状态（waiting）

1721710284977-72e3afbd-c036-4430-87f6-e9270690c938.png

协作：从图中的规则我们可以看到，主干道通过2辆蓝⾊⼩⻋，红⾊⼩⻋才可以通过

  • 当通过⼀辆蓝⾊⼩⻋，⼩红旗就减⼀；当⼩红旗数量为0时，红⻋可以通过；否则红⻋⼀直处于 等待状态（waiting）
  • 当⼀辆红⻋通过后，这时⼜会设置两个⼩红旗，下⼀辆红⻋处于wating状态

1721710388006-75a5c426-f107-4d5b-a8af-236d5918be88.png

并发的好处以及带来的灾难

好处：

允许同一时间间隔内运行多个应用

并发使得操作系统能够在单个处理器上快速切换不同的任务，或者在多核或多处理器系统上同时执行多个任务。这意味着用户可以在同一时间间隔内启动和运行多个应用程序，比如同时编辑文档、浏览网页和听音乐。这种多任务处理提高了用户的效率和系统的灵活性。

更好的资源利用率

并发可以提高系统的资源利用率。例如，在一个单核CPU上，如果一个任务因为等待I/O操作（如从磁盘读取数据）而暂停，CPU可以在等待期间切换到另一个任务，而不是闲置。这样，CPU和其他资源（如内存、磁盘等）的使用更加高效，减少了资源的浪费

更好的平均响应时间

由于任务可以交替执行，即使某些任务需要较长的处理时间，系统仍然可以快速响应用户的其他请求，例如采用时间片轮转算法。

并发引发的灾难

资源共享‌

在并发环境中，多个线程或进程可能同时访问和修改相同的资源，如内存中的数据结构、文件或其他临界资源（如打印机等）。如果没有适当的同步机制，这种共享可能导致数据的非预期修改，从而引起数据的不一致性和不可预测的行为。

竞争条件（数据不一致性）

‌竞争条件是指多个线程在没有适当同步的情况下，同时尝试读取和修改同一个共享资源，导致最终的资源状态取决于线程执行的精确时序（即运行结果与程序的运行顺序有关）。这种情况下的数据不一致性可能会导致严重的逻辑错误和安全漏洞。

饥饿与死锁
  • 饥饿：‌ 当一个线程长时间得不到所需资源而无法继续执行时，就会发生饥饿。
  • 死锁：‌ 死锁是指两个或多个线程互相等待对方释放资源，从而导致它们都无法继续执行的情况。死锁通常发生在多个线程试图以不同的顺序获取多个锁时。

灾难根源：异步（ Asynchronous means RANDOM! ）

由于并发的进程是异步执行，你无法预测到它们的运行顺序，因此可能会引发竞争条件：多个进程并发操作同⼀个数据，导致执⾏结果依赖于特定的进程执⾏顺序。如下代码

1721712169458-cc36bb49-3202-481d-9b63-d937ae26178a.png

其中T是每个程序的局部变量，⽽x是全局变量。 我们分析⼀下，由于T1和T2在CPU上是交替执⾏的，所以当T1执⾏⼀句，T2执⾏⼀句时，我们会发现最后在T1中x=1，在T2中x=1。本来是卖出了两张票，但是由于异步执⾏，系统只减掉了⼀张票

【2011-32】有两个并发执行的进程P1和P2，共享初值为1的变量x。P1对x加1，P2对x减1。加1和减1操作的指令序列分别如下所示。

P1 // 加1操作
load R1, x // 取x到寄存器R1中
inc R1
store x, R1 // 将R1的内容存入x

P2 // 减1操作
load R2, x // 取x到寄存器R2中
dec R2
store x, R2 // 将R2的内容存入x

两个操作完成后，x的值（ ）。

A. 可能为-1或3

B. 只能为1

C. 可能为0、1或2

D. 可能为-1、0、1或2

答案

本题选C。

为了方便讨论，将每行代码进行编号

load R1, x ① // 取x到寄存器R1中
inc R1 ② // 将R1中的操作数加一
store x, R1 ③ // 将R1的内容存入x
load R2, x ④ // 取x到寄存器R2中
dec R2 ⑤ // 将R2中的操作数减一
store x, R2 ⑥ // 将R2的内容存入x

方法一：枚举所有情况

x为1：例如执行①, ②, ③, ④, ⑤, ⑥，或者执行④, ⑤, ⑥, ①, ②, ③。

x为2：例如执行①, ②, ④, ⑤, ⑥, ③。

x为0：例如执行 ④, ⑤, ①, ②, ③ ⑥。

本题选C。

方法二：排除法

由于P1为加1操作，P2为减1操作，各执行一次，结果在数轴上具有对称性，由共享初值为1的变量x，结果关于1对称，排除D。

由于P1和P2均只执行1次，要得到3需要执行两次P1，得到-1需要执行两次P2，排除A和D。

由于先执行P1后执行P2得到1，正确选项一定包含1，排除A。

由于P1和P2均不是原子操作，排除B。

【2016-30】进程P1和P2均包含并发执行的线程，部分伪代码描述如下所示。

1747052446488-3ff6de18-c4a6-4596-8d66-1453197d3f11.jpeg

下列选项中，需要互斥执行的操作是（ ）。

A. a=1与a=2

B. a=x与b=x

C. x+=1与x+=2

D. x+=1与x+=3

解析

本题选C。

题图

首先需要明确的是，进程（或线程）外的为全局变量，进程（或线程）内的为局部变量，多进程（或线程）并发执行时，全局变量为临界资源，需要互斥访问。

A错误。a=1中的a为Thread1中的局部变量，a=2中的a为Thread2中的局部变量，两者相互独立。

B错误。a=x中的a为Thread3中的局部变量，b=x中的b为Thread4中的局部变量，两者相互独立。

C正确。x+=1在Thread1中执行，x+=2在Thread2中执行，Thread1和Thread2都属于进程P1，Thread1和Thread2并行修改进程P1的全局变量x，需要互斥执行。

D错误。x+=1在Thread1中执行，x+=3在Thread3中执行，Thread1属于进程P1，而Thread3属于进程P2，这两个x分属于不同进程，两者相互独立。

【2018-25】属于同一进程的两个线程thread1和thread2并发执行，共享初值为0的全局变量x。thread1和thread2实现对全局变量x加1的机器级代码描述如下。

// thread1
mov  R1,x   //(x)→R1
inc  R1     //(R1)+1→R1
mov  x,R1   //(R1)→x

// thread2
mov  R2,x   //(x)→R2
inc  R2     //(R2)+1→R2
mov  x,R2   //(R2)→x

在所有可能的指令执行序列中，使 x 的值为 2 的序列个数是（ ）。

A. 1

B. 2

C. 3

D. 4

解析

本题选B。

为了方便分析，每行代码增加编号后如下：

// thread1
mov  R1,x    ① //(x)→R1
inc  R1      ② //(R1)+1→R1
mov  x,R1    ③ //(R1)→x
// thread2
mov  R2,x    ④ //(x)→R2
inc  R2      ⑤ //(R2)+1→R2
mov  x,R2    ⑥ //(R2)→x

两者均是对x进行加1操作，且均执行一次。x的初始值为0，若要使最终x=2。

方案一：执行代码顺序为①②③④⑤⑥，即先执行thread1再执行thread2。

方案二：执行代码顺序为④⑤⑥①②③，即先执行thread2再执行thread1。

同步

由于异步会出现各种各样数据共享的问题，所以我们出现了同步机制。同步(Synchtonization)指的是协调多个并发进程(或线程)的执行，使它们能够安全地共享资源或进行通信。同步的目的是防止竞态条件、数据不一致和死锁等问题，从而确保系统的正确性和稳定性。下面会介绍一些同步工具。

同步与互斥的基本概念

协作进程能与系统内的其他执行进程互相影响。例如同一进程内的线程可以直接共享逻辑地址空间(即代码和数据)，然而由于进/线程具有异步性(各并发执行的进程以各自独立的、不可预知的速度向前推行)，可能导致数据的不一致。本节讨论多种机制，以便确保共享同一逻辑地址空间的协作进程/线程的有序执行，从而维护数据的一致性。

Note

  1. 临界资源：一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备(如摄像头、打印机)都属于临界资源，此外还有许多共享变量、数据、内存缓冲区等都属于临界资源。
  2. 临界区：为了让进程单独使用资源而不受其他进程干扰引入了临界区的概念，临界区就是 进程中访问临界资源的那段程序(即代码段)；我们希望这段代码是互斥（mutualexclusion）的，也就说保证一个进/线程在临界区执行时，其他进/线程应该被阻止进入临界区，说白了，就是这段代码执行过程中，最多只能出现一个进/线程。

1718418456036-208f5075-fd6e-4ce1-8651-6f060add0d2f.png

对临界资源的互斥访问，在逻辑上分为四个部分

1718418456008-95ba760d-3026-4741-9764-1dcfa9c4c174.png什么是互斥关系和同步关系？

这两个概念都涉及多个进程（或线程）在执行时如何相互影响，但它们的根本目的和关系性质是不同的。

互斥关系 (Mutual Exclusion)

  • 核心思想： 竞争。
  • 定义： 指的是多个进程因争夺同一个、临时的、不可共享的资源而产生的制约关系。这个资源被称为“临界资源”，访问资源的代码段被称为“临界区”。互斥保证了在任何时刻，最多只有一个进程能进入临界区访问该资源。
  • 通俗比喻： 公共厕所的单个隔间。这个隔间就是临界资源。一次只能有一个人进去使用。如果有人在里面（占用资源），其他想用的人就必须在外面排队等待。大家的关系是竞争关系，等待的原因是“资源正忙”。
  • 关键词： 共享资源、临界区、竞争、忙则等待。

同步关系 (Synchronization)

  • 核心思想： 协作。
  • 定义： 指的是多个进程为了共同完成一个任务，在执行次序上需要遵循某种先后顺序而产生的制约关系。一个进程的执行需要依赖另一个进程的消息或信号，当其依赖的条件未满足时，它必须等待。
  • 通俗比喻： 工厂流水线上的接力。工人B的任务是给汽车安装轮子，但他必须等待工人A把汽车底盘造好并送到他面前，他才能开始工作。工人A和B不是在竞争“底盘”，而是在协作完成“造车”任务。工人B等待的原因是“任务A还没完成，条件不满足”。
  • 关键词： 任务协作、执行时序、依赖、条件未满足则等待。

为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则：

Note

  • 空闲让进：临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。
  • 忙则等待：即互斥访问，当有进程进入临界区时，其他试图进入临界区的进程必须等待。
  • 有限等待：对请求访问的进程，应保证能在有限时间内进入临界区(保证不会饥饿)。
  • 让权等待（可选）：当进程不能进入临界区时，应立即释放处理机（如主动阻塞），防止进程忙等。

【2020-32】下列准则中，实现临界区互斥机制必须遵循的是（ ）。

Ⅰ. 两个进程不能同时进入临界区

Ⅱ. 允许进程访问空闲的临界资源

Ⅲ. 进程等待进入临界区的时间是有限的

Ⅳ. 不能进入临界区的执行态进程立即放弃CPU

A. 仅Ⅰ、Ⅳ

B. 仅Ⅱ、Ⅲ

C. 仅Ⅰ、Ⅱ、Ⅲ

D. 仅Ⅰ、Ⅲ、Ⅳ

本题选C。

让权等待并非必须实现，例如Peterson算法。

综上，仅Ⅰ、Ⅱ、Ⅲ正确。

实现临界区互斥的基本方法

软件实现方法

1747038427802-372e9fcb-bccf-4c93-abdc-700dd6094cd5.png

Note

如何判断软件实现方法是否遵循上面那四个原则？

  • 判断是否遵循空闲让进
  • 观察是否有可能让表达式1与表达式2同时成立；
  • 观察没有p1的话，P0能否通过循环进入临界区，没有p0的话，P1能否通过循环进入临界区.
  • 判断是否遵循忙则等待
  • 当p0通过while循环，但是没有进入临界区，此时切换P1，看P1能否也通过while循环，若可以，则不符合忙则等待；完了再反向检查一下；
  • 判断是否遵循有限等待
  • 当p1处于临界区，p0卡在进入区一直通过不了while循环，此时新来了一个p1进程后，仍然可以比p0先进入临界区，那么p0则不满足有限等待，有可能会饥饿；
  • 所有的软件实现方法都不遵循让权等待：上图进入区的while(表达式)；含义为如果表达式为真，则会一直执行这个循环，直到因为时间片到期被剥夺处理机或者因为表达式为假，方可跳出循环；该循环的循环体为空语句，这就是所谓的忙等。
  1. 单标志法： 有两个进程，其中一个进程在访问完临界区后会把使用临界区的权限交给另一个进程，也就是说每个进程使用临界区的权限只能被另一个进程赋予
//共享整形变量标志
int turn = 0;
turn = 1; //表示允许进入临界区的是进程P1

/*进程P0*/
while(TRUE){
    //若turn等于本进程编号，准入临界区
    while(turn != 0);
    临界区；
    turn = 1;//允许对方进入临界区
    剩余区；
}

/*进程P1*/
while(TRUE){
    //若turn等于本进程编号，准入临界区
    while(turn != 1);
    临界区；
    turn = 0;//允许对方进入临界区
    剩余区；
}
  • 满足忙则等待
  • 两个进程必须交替进入临界区，如果其中一个进程不再进入临界区，那么另一个进程由于未得到它的授权也永远进不去，这违背了“空闲让进”的原则

  • 另外由于使用while判断语句作为进入去，违背了“让权等待”。

  • 双标志法先检查：设置一个布尔型数组flag[ ],数组中各个元素用来标记各进程想进入临界区的意愿，比如“flag[0] = true”意味着0号进程P0现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[i]设为true，之后访问临界区。

//共享数组,表示两进程是否在临界区；
bool flag[2]; 
flag[0] = flag[1] = FALSE; 

/*进程P0*/
while(TRUE){
    while(flag[1] = TRUE); //检查对方是否在临界区；
    //通过循环说明对方不在临界区，那么P0先设置标志再进入临界区；
    flag[0] = TRUE; 
    临界区；
    flag[0] = FALSE; //表示本进程已退出临界区；
    剩余区；
}

/*进程P1*/
while(TRUE){
    while(flag[0] = TRUE); //检查对方是否在临界区；
    //通过循环说明对方不在临界区，那么P0先设置标志再进入临界区；
    flag[1] = TRUE; 
    临界区；
    flag[1] = FALSE; //表示本进程已退出临界区；
    剩余区；
}

Note

解决了单标志法需要循环进入的缺点，可以连续使用了，但是由于进程的异步性又产生了新的问题。如果P0进程通过了while循环，但是还没有进入临界区，就发生进程切换（例如时间片到期），让P1执行，P1也能通过while循环进入临界区，这样一来这两个进程可以同时进入临界区，违背了“忙则等待”的原则，原因在于进入区的“检查”和“上锁 ”不是一气呵成的，这两个过程之间很可能会发生进程切换。即并发程序不能保证load和store的原子性。

  1. 双标志法后检查：双标志先检查法的改版。前者由于无法一气呵成完成先“检查”后“上锁”的操作，因此导致了两个进程同时进入临界区的问题，为此人们想到了先“上锁”后“检查”的方法来避免该问题。
//共享数组,表示两进程想进入临界区；
bool flag[2]; 
flag[0] = flag[1] = FALSE; 

/*进程P0*/
while(TRUE){
    flag[0] = TRUE;
    while(flag[1] = TRUE); //检查对方是否在临界区；
    临界区；
    flag[0] = FALSE; //表示本进程已退出临界区；
    剩余区；
}

/*进程P1*/
while(TRUE){
    flag[1] = TRUE; 
    while(flag[0] = TRUE); //检查对方是否在临界区；
    临界区；
    flag[1] = FALSE; //表示本进程已退出临界区；
    剩余区；
}

Danger

观察两个while循环中的表达式能否同时成立，考虑到进程P0在置flag[0] = TRUE后发生进程切换，进程P1在置flag[1] = TRUE后无法进入临界区，即使再调度到进程P0，P0也无法进入临界区，这下违背了“空闲让进”和“有限等待”，两个进程都想进又都不谦让，就干脆都别进了。

  1. peterson算法（正确实现）：结合双标志法、单标志法的思想
//共享变量
int turn; //表示该让谁进入临界区；
bool flag[2]; //表示进程是否准备好进入临界区；

/* 进程 P0 */
while(TRUE) {
    flag[0] = TRUE; // 1. 表示本进程希望进入
    turn = 1;       // 2. 将 turn 置为对方编号（礼让 P1）

    while(flag[1] == TRUE && turn == 1); 
    // 如果 P1 想进 (flag[1]为真) 且 现在是 P1 的轮次 (turn为1)，则 P0 等待

    // 临界区
    临界区;

    flag[0] = FALSE; // 3. 表示本进程已退出临界区
    // 剩余区
    剩余区;
}

/* 进程 P1 */
while(TRUE) {
    flag[1] = TRUE; // 1. 表示本进程希望进入
    turn = 0;       // 2. 将 turn 置为对方编号（礼让 P0）

    while(flag[0] == TRUE && turn == 0); 
    // 如果 P0 想进 (flag[0]为真) 且 现在是 P0 的轮次 (turn为0)，则 P1 等待

    // 临界区
    临界区;

    flag[1] = FALSE; // 3. 表示本进程已退出临界区
    // 剩余区
    剩余区;
}
生活化示例

示例：A和B争用包厢的厕所

  • 想进入包厢之前，A/B都首先举起自己的🚩
    • A往厕所门上贴上“B正在使用”的标签
    • B往厕所门上贴上“A正在使用”的标签
  • 然后，如果对方举着🚩，且厕所门上是对方的名字，则等待
    • 否则可以进入厕所
  • 出厕所后，放下自己的🚩(完全不用管门上的标签)


进入临界区(厕所)的情况：

  • 如果只有一个人举🚩，他就可以直接进入
  • 如果两个人同时举🚩，则由厕所门的标签决定谁进
    • 手快🈶️(先贴的标签会被另一个人的标签覆盖)，手慢🈚

该算法遵循空闲让进、忙则等待、有限等待，不遵循让权等待；

  • 空闲让进：假设P0不打算进入临界区，那么flag[0] = FALSE，则P1可以通过while循环进入临界区，不会出现单标志法那种临界区有空，进程却进不去的情况；
  • 忙则等待，如果进程P0、P1都希望进入临界区，那么turn变量发挥作用，先申请的进程先进入临界区，因为双方进程互相礼让，后申请的进程将turn置为先申请进程的编号；
  • 有限等待，假设P0进入临界区，P1也想进入临界区，当P0执行完临界区出来后，会修改flag标志，这样当进程P1上处理机后会通过while循环进入临界区，因此满足；
  • 由于进程即使进不去临界区，也会一直执行while循环空转直到时间片用完，因此不遵循让权等待；
方法 思想 缺点
单标志法 引入共享变量turn，循环检查直到turn = 本进程编号 违背空闲让进和让权等待，只能两个进程交替使用
双标志先检查 引入flag共享数组，先检查对方是否进入临界区 有可能会同时进入临界区，从而违背忙则等待
双标志后检查 引入flag共享数组，先设置自身flag，再检查对方 当两进程都想进入临界区，有可能都进不去，违背有限等待
peterson算法 引入turn和flag数组，进入临界区时检查两个条件 违背让权等待，且只适用于两个进程之间互斥进入临界区

【2010-27】进程P0和P1的共享变量定义及其初值为

boolean flag[2];
int turn = 0;
flag[0] = FALSE; 
flag[1] = FALSE;

若进程P0和P1访问临界资源的类C伪代码实现如下：

void P0() { //进程P0
    while (TRUE) {
        flag[0] = TRUE;
        turn = 1;
        while (flag[1] && (turn = 1));
        临界区;
        flag[0] = FALSE;
    }
}

void P1() { //进程P1
    while (TRUE) {
        flag[1] = TRUE;
        turn = 0;
        while (flag[0] && (turn = 0));
        临界区;
        flag[1] = FALSE;
    }
}

则并发执行进程P0和P1时产生的情形是（ ）。

A. 不能保证进程互斥进入临界区，会出现“饥饿”现象

B. 不能保证进程互斥进入临界区，不会出现“饥饿”现象

C. 能保证进程互斥进入临界区，会出现“饥饿”现象

D. 能保证进程互斥进入临界区，不会出现“饥饿”现象

解析：

本题考察Peterson算法。

算法实现互斥的主要思想在于设置了一个turn变量用于进程间的互相谦让。如果进程P0试图访问临界资源，则flag[0]=true表示P0希望访问。此时如果进程P1还未试图访问临界资源，则flag[1]在进程上一次访问完临界资源退出临界区后已设置为false。所以进程P0在直线循环判断条件时，第一个条件不满足，进程P0可以正常进入临界区，且满足互斥条件。

需要考虑的是两个进程同时试图访问临界资源的情况。注意turn变量的含义：当某进程试图访问时，首先设置自己的flag变量为true，表示希望访问；但又设置turn变量为对方的进程编号，表示谦让。因为在循环判断条件中turn变量不是自己的编号时就循环等待。虽然两个进程会互相谦让一番，但是这不会造成饥饿的局面，因为turn变量会有一个最终值，所以必定有进程可以结束循环进入临界区。

实际情况是，先作出谦让的进程先进入临界区，后作出谦让的进程则需要循环等待。其实这里可以想象为两个人进门，每个人进门前都会和对方客套一句“您走先”。如果进门时没别人，就当和空气说句废话，然后大步登门入室；如果两人同时进门，就互相“谦让”，但各自只客套一次，所以先客套的人请完对方，就等着对方请自己，然后光明正大进门。

Peterson算法遵循空闲让进、忙则等待、有限等待这三个原则，未遵循让权等待原则，暂时无法进入临界区的进程会占用CPU并执行拦截进入临界区的while循环导致忙等。

本题选D。

硬件实现方法

上面所述基于软件的解决方案(如peterson算法)并不保证在现代计算机体系结构上正确工作，下面我们探讨临界区问题的多个解答，这包括内核开发人员和应用程序员采用的硬件和软件API技术。所有这些解答都是基于加锁(locking)为前提的，即通过加锁来保护临界区。首先我们介绍一些简单的硬件指令(许多系统都具有的)，并有效地使用它们来解决临界区问题。另外，许多现代系统提供特殊硬件指令，用于检测和修改字的内容，或者用于原子地交换两个字(作为不可中断的指令)。我们可以采用这些特殊指令相对简单地解决临界区问题。通过硬件支持实现临界段问题的方法称为低级方法，或称元方法。

  1. 中断屏蔽方法

利用“开/关中断指令”实现(与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能出现两个进程同时访问临界区的情况)

进程切换通常是由中断指令或者系统调用触发，对于单处理机环境来说，在进入临界区时(例如修改共享变量)只要禁止中断出现，这样就能确保当前指令流可以有序执行，且不会被抢占。由于不可能执行其他指令，所以临界区不会被同时访问(共享变量不会被意外修改)。这种方法往往为非抢占式内核所采用。

Info

...\ 关中断\ 临界区\ 开中断\ ....

优点：简单、高效

缺点：

  • 首先，这种方法要求我们允许所有调用线程执行特权操作，因此只适用于操作系统内核进程，不适用于用户进程(因为开/关中断指令只能运行在内核态，这组指令如果让用户随意使用会很危险，一个贪婪的程序可能在它开始时就调用lock()（即关中断）,从而独占处理器，更糟的情况是恶意程序调用lock()后，一直死循环)；
  • 只能再 单处理机 环境下使用，在多处理机环境下这种解决方案不可行，如果多个线程运行在不同的CPU上，每个线程都试图进入同一个临界区，关闭中断也没有作用，线程可以运行在其他处理器上，因此能够进入临界区。

相关问答：

  1. 我们提到频繁禁用中断可能会影响系统的时钟。解释为什么会发生这种情况，以及如何将这种影响降至最低。

系统时钟在每次时钟中断时更新。如果中断被禁用，特别是长时间禁用，则系统时钟可能很容易丢失正确的时间。系统时钟也用于调度目的。例如，进程的时间量表示为时钟滴答数。在每个时钟中断时，调度器确定当前正在运行的进程的时间量是否已过期。如果时钟中断被禁用，调度程序将无法准确分配时间量。通过仅在很短的时间内禁用时钟中断，可以将这种影响降至最低。

  1. 请解释： 为什么在单处理器系统上通过禁止中断来实现同步原语的方法不适用于用户级程序 .

如果用户级程序具有禁用中断的能力，那么它可以禁用计时器中断并防止发生上下文切换，从而不让其他进程执行，达到独占处理器的目的。

  1. 请解释 为什么禁止中断不适合在多处理器系统来实现同步原语.

如果多个进程运行在不同的CPU上，每个进程都试图进入一个临界区，即使禁止中断，其他进程依旧能够在其他处理器上进入临界区。

  1. 硬件指令方法

  2. TestAndSet指令：简称TS指令，也有地方称为TestAndSetLock指令，或TSL指令，TSL指令是用硬件来实现的，它的执行是原子的，因此它的执行过程中不允许被中断，只能一气呵成，如果两个TS指令同时执行在不同CPU上，那么它们会按任意次序来顺序执行。

1747056171797-228b5e82-63a3-4a26-859d-5cc767fa2663.png

测试和置位指令

  1. 从内存单元中读取值
  2. 测试该值是否为1（然后返回真或假）
  3. 内存单元值设置为1；

该硬件指令可适用于共享内存的多处理机环境，原理如下

1747056353194-e41b7a1d-e183-4619-88ea-232ec5c7f4ba.png

  • 1718418456582-c615f377-a1a8-4287-a210-8e5982bfa4ca.png\ 测试并设置指令返回lock指向的旧值，同时更新新值，这些代码原子地执行，因为既可以测试旧值又可以设置新值，所以把这条指令叫做“测试并设置”。
  • 如果刚开始lock值是false,则执行TSL后返回的old值也为false,并且给lock上了锁(lock值变为true)，然后while循环条件不满足，可以进入临界区，执行完之后给临界区解锁
  • 如果刚开始lock值是true，则执行TSL后返回的old值也还是true，while循环条件满足，则一直循环，直到当前访问临界区的进程在退出区将lock解锁或者等到时间片耗尽下处理机；

相比于软件实现方法，由于双标志先检查法无法做到先检查后上锁的一气呵成，因进程的异步性会发生许多错误，而TSL指令由于其原子性把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作，则避免了这种错误的发生。

  • Swap指令：有的地方也叫EXchange指令，或简称XCHG指令。swap指令是由硬件实现的，和TSL一样一气呵成，执行过程不允许被中断。

1718418456614-787dce72-ce53-4890-ae43-233e335ae13e.png

逻辑上来看swap和TSL并无太大区别，都是先记录下此时临界区是否已经被上锁(记录在old变量上)，再将上锁标记lock设置为true，最后在检查old，如果old为false则说明之前没有别的进程，对临界区上锁后，跳出while循环进入临界区，执行完相应操作在退出区解锁。

这两种硬件实现的优缺点

  • 优点：实现简单，易验证其正确性，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于任意数目的进程，不管是单处理机还是多处理机环境；可以支持进程内有多个临界区，只需为每个临界区设立一个布尔型变量。
  • 缺点：不满足“让权等待“原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL/Swap指令，从而导致忙等；从等待进程中随机选择一个进入临界区，有的进程可能一直选不上，从而导致”饥饿“现象。

【2016-27】使用TSL (Test and Set Lock) 指令实现进程互斥的伪代码如下所示。

do {
    ...
    while (TSL(&lock));
    critical section;
    lock = FALSE;
    ...
    } while (TRUE);

下列与该实现机制相关的叙述中，正确的是（ ）。

A. 退出临界区的进程负责唤醒阻塞态进程

B. 等待进入临界区的进程不会主动放弃CPU

C. 上述伪代码满足“让权等待”的同步准则

D. while (TSL(\&lock)) 应在关中断状态下执行

解析

本题选B。

TSL 指令是一条硬件指令，通过对锁的测试和设置操作实现互斥。这条指令可以视为一个函数过程，其执行过程是不可分割的，即是一条原语。其中，lock有两种状态：当lock为FALSE时，该资源空闲；当lock为TRUE时，该资源被占用。

A错误。当某进程退出临界区后，lock为FALSE时，该资源空闲，等待进入临界区的进程 while (TSL(&lock)) 轮询后可以进入临界区，此前该等待进入临界区的进程占用CPU，并非处于阻塞态。

B正确。若等待进入临界区的进程处于 while (TSL(&lock)) 轮询中，则不会主动放弃CPU。

C错误。根据选项B的推理，上述伪代码不满足“让权等待”的同步准则。

D错误。把功能塞进了一条指令的执行周期中，而单条指令不会被打断。注意while(TSL(&lock))语句在开中断状态下执行，虽然该程序段中TSL指令是原子指令，但其实它就相当于一条指令，这段程序还有其他指令，因此如果该程序执行过程中关中断，那么无法响应其他中断源的中断请求。开中断后也不会破坏它的原子性，因为如果有中断请求到来，即使该程序在执行TSL语句，那么可以执行到时间片结束之后再响应中断请求，如果整个程序都关中断的话，则可能很久都不会响应。

【2018-32】在下列同步机制中，可以实现让权等待的是（ ）。

A. Peterson方法

B. swap指令

C. 信号量方法

D. TestAndSet指令

解析

本题选C。

互斥锁重点

采用互斥锁保护临界区，一个进程在进入临界区时应得到锁；它在退出临界区时释放锁。函数acquire()获取锁，而函数release()释放锁；

每个互斥锁有一个变量locked，表示锁是否可用。如果锁是可用的，调用acquire()会成功，且锁不可再用。

1718418456758-f2dee094-50c8-49ec-b896-48b2eb484544.png

互斥锁有两种类型

  1. 自旋锁：当进程申请锁失败后，会一直循环申请锁，直到申请成功；
struct Lock{
     int locked;  //表示锁是否可用
}

locked = 0; 表示锁未被占用；

locked = 1；表示锁被占用；

//获取锁
acquire(Lock *lock){
    while(&lock->locked){
        //如果锁被其他进程占用就一直spin 忙等
    }
    lock->locked = 1;
}

//释放锁
release(Lock *lock){
   lock->locked = 0;
}
当进程申请锁失败后会处于什么状态呢？

就绪态/运行态，如果时间片没用完，则处于运行态，一直尝试获取锁；如果时间片用完，则被剥夺处理机，处于就绪态；注意哈，如果将其应用在单处理器上，需要抢占式的调度器(即不断通过时钟中断一个线程，运行其他线程)，否则自旋锁在单CPU上无法使用，因为一个自旋的线程永远不会放弃处理机。

  1. 无忙等待锁：当进程申请锁失败后，会主动阻塞自己，加入阻塞队列，让出处理机，这样就不会忙等了；等待其他进程释放锁之后，将其唤醒加入就绪队列；

1747061097875-a09dc518-466c-4b1a-9cd9-2c626cb66c41.png

struct Lock{
    int locked;  //表示锁是否可用
    waitqueue q; //该锁对应的等待队列
}

//获取锁
acquire(Lock *lock){
    while(&lock->locked){
        //将该进程加入等待队列；
        block the process into q;
    }
    lock->locked = 1;
}

//释放锁
release(Lock *lock){
   lock->locked = 0;
    //从等待队列唤醒一个阻塞进程；
    wake a process from q; 
}

上面的代码实现是有缺陷的，上锁时检查锁是否可用和上锁这之间如果发生进程切换，那么可能会违背忙则等待，让多个进程进入临界区，为此对acquire()或release()的调用必须原子地执行，因此，互斥锁通常采用上面硬件实现方法所述的硬件机制来实现；

  1. 采用中断机制，在获取锁之前关中断；不过该方式只对单处理机系统有效；

  2. 原子操作指令；

  3. 使用TSL指令实现自旋锁

struct Lock{
    int locked; 
}

locked = 0; 表示锁未被占用；

locked = 1；表示锁被占用；

//获取锁
acquire(Lock *lock){
    while(TestAndSet(&lock->locked)){
        // CPU 在此“忙等待”或“自旋”
    }
}

如果锁没有被占用，那么TSL指令读取false并将locked值设置为 1；

  • 即锁被设置为忙，并且需要等待完成；

如果锁处于忙状态，那么TSL指令读取true并将值设置为true；

  • 不改变锁的状态并且需要一直循环；
//释放锁
release(Lock *lock){
   lock->locked = 0 ;
}
  • 使用TSL指令实现无忙等待锁
struct Lock{
    int locked; 
    waitqueue q; //该锁对应的等待队列
}

//获取锁
acquire(Lock *lock){
    while(TestAndSet(&lock->locked)){
        //主动阻塞
        block the process into q;
        schedule();//发起调度
    }
}

//释放锁
release(Lock *lock){
   lock->locked = 0 ;
   wake a process from q; 
}

自旋锁特性总结：

  • 自旋锁具有随机性，不能保证进程按先来后到的顺序使用cpu资源，顺序可能乱
  • 需忙等，进程时间片用完才下处理机，违反“让权等待”
  • 当进程在等待锁时，没有上下文切换(上下文切换需要相当长的时间)，因此在多处理器系统中，若上锁的时间短，则等待代价很低；
  • 常用于多处理器系统，一个核忙等，其他核照常工作，并快速释放临界区
  • 不太适用于单处理机系统，忙等的过程中不可能解锁，因此如果将其应用在单处理器上，需要抢占式的调度器(即不断通过时钟中断一个线程，运行其他线程)，否则自旋锁在单CPU上无法使用，因为一个自旋的线程永远不会放弃处理机。即使有抢占式的调度器，性能开销也特别大，因为其他未持有锁的进程如果被调度的话都会在放弃CPU之前自旋一个时间片，浪费CPU周期。
  • 自旋锁不提供任何公平性保证，实际上，自旋的线程在竞争条件下可能会永远自旋，自旋锁没有公平性，可能会导致饿死。

无忙等待锁特性总结：

  • 由于等待队列的存在，因此可以实现申请锁的进程的先来后到，较为公平
  • 未申请到锁时不需要忙等，但是需要阻塞自己，切换其他进程，因此有一些切换上下文的代价；

【测试题】互斥锁是一种用于解决临界区互斥问题的常用手段，对acquire()获取锁或release()释放锁的调用必须原子地执行，因此，互斥锁通常采用硬件原语（如Test&Set指令或exchange交换指令来实现），对于TSL硬件原语实现的自旋锁与无忙等待锁，以下说法错误的是（）

A ： 使用原子操作指令实现的互斥锁适用于单处理器或共享内存多处理器中任意数量的进程同步。

B ： 自旋锁不能实现让权等待，但是阻塞锁可以

C： 自旋锁可以实现进程对临界区的先进先出（即按申请顺序访问临界区），不会导致进程饥饿

D： 互斥锁可用于多进（线）程之间，但是只能由获取锁的进（线）程对它进行解锁（即释放）；

解析

本题应该选择C选项；

首先，我们先了解一下什么是互斥锁，其实它就是一个普通的变量，可以是bool类型也可以是int类型（用0表示锁释放，1表示已上锁），上面这种实现出来的互斥锁，它是支持多临界区的互斥访问，什么意思呢，如果我们有好多个临界资源需要互斥访问，我们可以对它们分别实现一个互斥锁，即每把锁一个变量即可；注意，这个互斥锁变量，它是位于主存里的共享变量，不是某个进程私有的，否则实现不了一个进程拿到锁，别的进程进不去这种效果，因此我们说使用原子操作指令实现的互斥锁适用于单处理器或共享内存多处理器中任意数量的进程同步，因此A选项正确。

题图

另外，我们要注意拿到锁和释放锁的必须是同一个进程，否则可能会出现A进程拿到锁之后，但是B进程却释放了这把锁，这时候C获取了这把锁，这样就不满足互斥进入临界区这个规则了，因此在拿到锁和释放锁的时候，需要验证一下身份，例如当某个锁是空闲的时候，A拿到了这把锁，这时候可以把A的进程pid记下来，之后释放锁的时候，验证一下pid是否相等，是的话才可以释放锁，这样就可以保证互斥访问临界区了，因此D正确；

BC选项的话，我们可以根据这两把锁的实现方式来看，自旋锁在拿不到锁的时候，并没有及时释放处理机，而是一直循环尝试是否可以获取锁，因此不符合让权等待，而阻塞锁在拿不到锁的时候，就将该进程加入阻塞队列里面，因此，阻塞锁可以实现让权等待，B 选项正确。此外由于自旋锁具有随机性，没有队列这种数据结构保证进程按照先来后到的顺序使用CPU资源，因此顺序可能会乱，另外如果当某个进程离开临界区时有多个进程等待进入临界区，就有可能导致某些进程由于每次临界区空闲的时候没有上处理机，或者轮到上处理机的时候，临界区有锁，从而导致饥饿，因此C选项错误。

扩展一下，以上这种使用原子操作实现的互斥锁还有可能导致死锁的发生，比如某个低优先级进程拿到了锁，在使用这把锁的时候，来了一个高优先级的进程获得处理机，并且它也想进入临界区，这时就发生了死锁。

信号量

我们刚刚讨论的互斥锁通常被认为是最简单的同步工具，接下来我们会介绍一个更鲁莽的工具，它的功能类似与互斥锁，但是它能提供更为高级的方法，以便进程能够进行同步活动。

用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程同步与互斥；

信号量其实就是一个变量(可以是一个整数，也可以是更复杂的记录型变量)，可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为1的信号量。

一对原语：wait(S)原语和signal(S)原语，可以把原语理解为我们自己写的函数，函数名分别为wait和signal，括号里的信号量S是函数调用时传入的一个参数。wait、signal原语常简称为P(荷兰语proberen,测试)、V(verhogen,增加)操作，因此这也常写成P(S)、V(S)。

  1. 整型信号量

用一个整数型的变量作为信号量，用来表示系统中某种资源的数量(与普通整型变量的区别：对信号量的操作只有三种，即初始化、P操作、V操作)；

eg：某计算机系统中有一台打印机…

1718418457201-885154f4-1b5a-4148-9469-88c70ece50a6.png

  1. 记录型信号量

由于之前提出的互斥锁、整型信号量都存在“忙等”的问题，因此人们提出了“记录型信号量”，即用记录型数据结构表示的信号量。这里需要这样修改信号量操作“wait()”和“signal”的定义：当一个进程执行wait()并且发现信号量不为正时，它必须等待，然而该进程不是忙等待而是阻塞自己。阻塞操作将一个进程放到与信号量相关的等待队列中，并且将该进程切换成阻塞状态。然后，控制转到CPU调度程序，以便选择执行另一个进程。

等待信号量S而阻塞的进程，在其他进程执行signal()操作后，应被重新执行。进程的重新执行是通过操作wakeup()来进行的，它将进程从阻塞状态改为就绪状态。随后该进程被添加到就绪队列中等待调度。

为此我们应该这样定义信号量及信号量操作：

1718418457359-5f6a5763-2b72-40a4-9477-68878c2d0769.png

  • 在考研中wait(S)、signal(S)也可以记为P(S)、V(S),这对原语可用于实现系统资源的“申请”与“释放”。
  • 该机制由于调用了block原语将不能进入临界区的进程阻塞从而释放了处理机，因此遵循了“让权等待”这一原则，不会出现“忙等”现象。
  • 注意该种机制实现的信号量可以是负数，，而在具有忙等待的信号量经典定义(即整型信号量)中，信号量的值不能为负值。如果信号量为负值，那么它的绝对值就是等待它的进程数。出现这种现象的原因是在实现wait()操作时互换了递减和测试的顺序。

对signal()操作中S->value <= 0的解释例子

如果 sem= 1，有三个线程进行了 P操作：

  • 第一个线程 P 操作后，sem= 0；
  • 第二个线程 P 操作后，sem = -1；
  • 第三个线程 P 操作后，sem = -2；

这时，第一个线程执行 V 操作后， sem是 -1，因为 sem<= 0，所以要唤醒第二或第三个线程。

  • 考试中出现P(S)、V(S)操作，除非特殊说明，否则默认S为记录型信号量.

扩展：

  • 通过为每个进程控制块PCB的一个链接字段，等待进程的链表可以轻松实现。每个信号量包括一个整数和PCB链表指针。向链表中增加和删除进程以便确保有限等待的一种方法是采用FIFO队列，这里的信号量包括队列的首尾指针。然而一般来说，链表可以使用任何排队策略，信号量的正确使用不依赖于信号量链表的特定排队策略。
  • 重点信号量操作需原子执行。要保证对同一信号量没有两个进程可以同时执行操作wait()和signal()，这是一个临界区问题。(对信号量的访问必须是互斥的原因：信号量S是能够被多个进程共享的变量，多个进程都可以通过wait()和signal()操作对S进行读、写操作) 对于单处理机环境来说，在执行这两种操作时可以简单禁止中断；对于多处理机来说，若采用这种策略那么每个处理器的中断都应该被禁止，否则在不同处理器上不同的运行进程可能会以任意不同方式一起交织执行，然而每个处理器中断的禁止是很困难的，且严重影响性能。因此多处理器系统例如SMP系统应该提供其他加锁技术，如compare_and_swap或自旋锁，以确保wait()和signal()原子执行。

  • 还有一点我们这里并没有完全取消忙等待，我们只是将忙等待从进入区移到临界区，即将忙等待限制在操作wait()和signal()的临界区内，这些区比较短，因此临界区几乎不被占用，忙等待很少发生，而且所需时间极短。

  • 信号量机制实现进程互斥

互斥是不同进程对同一信号量进行P、V操作实现的。

实现步骤：

  • 分析并发进程的关键活动，划定临界区(如对临界资源打印机的访问应放在临界区)
  • 设置互斥信号量mutex初值为1
  • 在进入区P(mutex)——申请资源
  • 在退出区V(mutex)——释放资源

1718418457567-76857a90-d391-4d3b-b0ef-13fe101e6ad8.png

注意：对不同的临界资源设置不同的互斥信号量；P、V操作必须成对出现，缺少P(mutex)操作就不能保证临界资源的互斥访问，缺少V(mutex)会导致资源永不释放，等待进程永远不会被唤醒；因此在互斥问题中，P、V操作要夹紧使用互斥资源的那个行为，中间不能有其他冗余代码。

  1. 信号量机制实现同步

进程同步：要让各并发进程按要求有序地推进。

实现步骤：

  • 分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作(或两句代码)
  • 设置同步信号量S，初始为0；
  • 在“前操作”之后执行V(S);
  • 在“后操作”之前执行P(S);

示例：进程P2中的语句y要使用进程P1中语句x的运行结果，所以只有当语句x执行完成之后语句y才可以执行。

1718418457705-4bf6c8b5-a7e1-4baf-ad11-8d875b176dc9.png

  1. 信号量机制实现前驱关系(多级同步问题)

每一对前驱关系都是一个进程同步问题(需要保证一前一后的操作)，因此

  • 要为每一对前驱关系各设置一个同步信号量
  • 在“前操作”之后对相应的同步信号量执行V操作
  • 在”后操作“之前对相应的同步信号量执行P操作

1718418457728-082c1666-cc0d-49ff-8877-429614411209.png

管程

  1. 引入管程的原因：虽然信号量机制足够好用，例如相比于锁来说允许多个线程同时访问一个临界区，只要count符合条件即可。但是仍存在一些缺点，那就是真正使用起来比较困难，因为当我们需要解决的同步问题越复杂，条件越多，所需要的信号量也就越多，需要更加地谨慎处理信号量之间的处理顺序，否则很容易造成死锁，这点在后面的类似于生产者消费者问题就能看出来。为此便产生了一种新的进程同步工具———管程。管程的特性保证了进程互斥，无须程序员自己实现互斥，从而降低了死锁发生的可能性。同时管程提供了条件变量，可以让程序员灵活地实现进程同步。 1718418457907-2f9cd5ea-f272-4420-8b9a-decbd983e493.png\ 管程优于信号量之处在于，所有的同步机制都被限制在管程内部，因此，不但容易验证同步的正确性，而且易于检查出错误。此外如果一个管程被正确得编写，则所有进程对受保护资源的访问都是正确的；而对于信号量，只有当所有访问资源的进程都被正确地编写时，资源访问才是正确的。

  2. 管程的定义和基本特征

  3. 管程的定义：利用共享数据结构抽象地表示系统中的共享资源，而把对该数据结构实施的操作定义为一组过程。进程对共享资源的申请、释放等操作，都通过这组过程来实现，这组过程还可以根据资源情况，或接受或阻塞进程的访问，确保每次仅有一个进程使用共享资源，这样就可以统一管理对共享资源的所有访问，实现进程互斥。这个代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序，称为管程(monitor)。

  4. 管程实现的一般方法：收集在对象/模块中的相关共享数据；定义方法来访问共享数据。
  5. 管程是一种特殊的软件模块(抽象数据类型）,采用了面向对象的思想封装了线程间的同步控制，即将共享的变量和对于这些共享变量的操作封装起来，形成一个具有一定接口的功能模块，进程可以调用管程来实现进程级别的并发控制，因此管程主要由这些部分组成:
  6. 管程的名称
    • 局部于管程的共享数据结构说明;
    • 对该数据结构进行操作的一组过程(或函数);
    • 对局部于管程的共享数据设置初始值的语句;

补充：管程拥有，入口等待队列，一个锁：控制整个管程代码的互斥访问，0个或多个条件变量：等待/通知信号量用于管理并发访问共享数据，每个条件变量都包含一个自己的等待队列，以及相应的出/入队操作。

1718418457933-de6285d6-294b-4944-8d5a-18e603575ab4.png

注意：在入口等待队列中的线程，都是条件满足情况未知或曾经满足过条件的线程，它们等待管程的新一轮执行，而条件变量的等待队列中的线程必须等到满足该条件后才可以重新回到入口等待队列中去。

(这里结合后面那个用管程解决生产者/消费者问题的while/if语句理解

  • 管程的基本特性：

  • 只有管程内定义的函数才能访问管程内的局部声明的变量和形式参数. 类似地，管程的局部变量只能为局部函数(过程)所访问。

    • 一个进程通过调用管程的一个过程(局部函数)进入管程；
    • 在任何时候，只能有一个进程在管程中执行，调用管程的任何其他进程都被阻塞，以等待管程可用。

  • 管程如何实现互斥与同步：

对管程的实现互斥由编译器负责！在Java中，只要将关键字synchronized加入到方法声明中，Java保证一旦某个线程执行该方法，就不允许其他线程执行该类中的任何其他方法。通过给进程强加规定，管程可用提供一种互斥机制：管程中的数据变量每次只能被一个进程访问到。因此将代表某些临界资源的共享数据结构放在管程中，从而为访问这些资源提供了互斥机制。也可以理解为由等待队列+封装实现互斥。

管程通过使用条件变量提供对同步的支持，这些条件变量包含在管程中，并且只有在管程中才能被访问。有两个函数可以操作条件变量：

x.wait()：当x对应的条件不满足时，正在调用管程的进程调用x.wait()将自己阻塞，即插入到x条件的等待队列中，并释放管程。此时其他进程可以使用该管程。

x.signal():x对应的条件发生了变化，则调用x.signal(),唤醒一个因x条件而阻塞的进程。

1718418458001-304002e1-7a8f-45c3-ac19-561c2594db56.png

  1. 用管程解决生产者消费者问题的实例：

1718418458060-b54abbe1-a3e8-414e-aa8f-b49075a516d1.png

根据管程定义，只有一个线程能进入管程，所以一开始就上锁，在最后才解锁；这里和信号量是不一样的，信号量的互斥是紧紧靠着信号量的，而管程的互斥是在头和尾。注意，这个lock是管程的lock。

王道伪代码：

1718418458198-71eb444d-2e12-4df0-8967-12e125ac0864.png

注意：管程是一个编程语言概念，编译器必须要识别出管程并用某种方式对互斥做出安排。C、Pascal及多数其他语言都没有管程，这里的伪代码只是用来解释原理。

OSTEP：对条件变量使用while（而不是if)

多线程程序在检查条件变量时，使用while循环总是对的。if语句可能会对，这取决于发信号的语义。因此，总是使用while，代码就会符合预期。\ 对条件变量使用while循环，这也解决了假唤醒（spurious wakeup）的情况。某些线程库中，由于实现的细节，有可能出现一个信号唤醒两个线程的情况。再次检查线程的等待条件，假唤醒是另一个原因。

  1. 条件变量重点：

当一个进程进入管程后被阻塞，直到阻塞的原因解除时，在此期间，如果该进程不释放管程，那么其他进程无法进入管程，为此，将阻塞原因定义为条件变量condition.通常一个进程被阻塞的原因可以有多个，因此在管程中设置了多个条件变量。每个条件变量保存了一个等待队列，对条件变量只能进行wait和signal操作。

条件变量与信号量的比较：

  • 相似点：条件变量的wait/signal操作类似于信号量的P/V操作，可以实现进程的阻塞/唤醒。
  • 不同点：
    1. 条件变量是“没有值”的，仅实现了“排队等待”的功能；而信号量是有值的，信号量的值反映了剩余资源数，而在管程中，剩余资源数用共享数据结构记录。
  • 2.条件变量的wait/signal操作与信号量不同，如果在管程中的一个进程发信号，但没有在这个条件变量上等待的任务，则丢弃这个信号。

注意：条件变量不仅存在于管程中，在多线程库中也是普遍存在的。Unix的多线程库Pthread也使用条件变量协调进程的同步。

经典同步问题

生产者—消费者(有界缓冲区)问题

  • 应用场景：在多线程程序中，线程之间通常存在分工。 在一种常见模式中，一些线程是生产者，一些是消费者。 生产者创建某种物品并将其添加到数据结构中; 消费者处理并删除它们。事件驱动的程序就是一个很好的例子。 “事件”是需要程序响应的事件：用户按下一个键或移动鼠标，一个数据块从磁盘到达，一个数据包从网络到达，一个待处理的操作完成。每当事件发生时，生产者线程都会创建一个事件对象并将其添加到事件缓冲区。 同时，消费者线程将事件从缓冲区中取出并处理它们。 在这种情况下，消费者被称为“事件处理程序”。我们需要强制执行几个同步约束才能使此系统正常工作：
  • 在缓冲区中添加或删除项目时，缓冲区处于不一致状态。 因此，线程必须具有对缓冲区的独占访问权限。
  • 如果消费者线程在缓冲区为空时到达，则会阻塞，直到生产者添加新项目为止。

问题描述：系统中有一组生产者进程和一组消费者进程， 生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。(注：这里的“产品”理解为某种数据） 生产者、消费者共享一个初始为空、大小为 n 的缓冲区。

只有缓冲区没满时， 生产者才能把产品放入缓冲区， 否则必须等待。（同步关系）1718418458308-8463c9f5-53d5-4203-a5ac-a90f785b1ef3.png

只有缓冲区不空时， 消费者才能从中取出产品， 否则必须等待。（同步关系） 1718418458851-f38ad71e-ab7c-452e-86a4-33eb40491102.png

缓冲区是临界资源， 各进程必须互斥地访问。

  • 伪代码分析：

1718418458878-c0392e5d-c7a8-433b-b821-1d4ab851958c.png

注意这里必须先对资源信号量进行P操作后，才能对互斥信号量进行P操作，即实现互斥的P操作必须在实现同步的P操作之后。如果将其顺序颠倒，会发生什么呢？假设此时生产者进程已经将缓冲区填满，消费者没有来消耗产品，下一次调度后又是生产者进程运行，先对mutex进行P操作，然后由于empty=0所以被阻塞，调度消费者进程运行，然而由于mutex此时为0，所以消费者进程无法进入临界区，因而也被阻塞。这样双方都等着对方执行然后唤醒自己，然后又都陷入阻塞，从而发生死锁。V操作不会导致这种情况，因此可以调换顺序。

  • 生产者消费者问题解题模板及例题：

生产者–消费者问题的解题步骤(思路)：（参考王道强化课)

  1. 分析有几类进程：根据题意，区分有几类进程，每类进程对应一个函数。若进程是不断重复的可以加一个while(true)循环；
  2. 在函数内部，用中文描述动作；
  3. 添加PV操作，用中文描述里面的操作；
  4. 同步操作：在每一个动作开始之前思考是否需要消耗资源(例如缓冲区的空位或产品), 需要的话P一下，并在产生该资源的地方添加V操作；因为PV操作是成对出现的，所以这种方法可以有效避免漏操作。
  5. 互斥操作：注意对缓冲区的互斥访问，进入缓冲区的前后分别加上PV操作。
  6. 定义信号量：所有的PV操作写完后便可以定义相应的信号量；对于互斥信号量，初值为1；对于同步信号量(前驱后继)，初始值一般为0；其他一般信号量根据题意定义初始值，例如生产者消费者问题中未运行之前缓冲区空位数为N，产品数为0，则可以定义信号量empty = N, full = 0;注意如果根据题意缓冲区的空位为1，则此时只需要一个记录空位的一般信号量即可，这个信号量可以充当互斥信号量；

  7. 检查是否会出现死锁：

  8. 检查连续的P操作是否会出现死锁：这里的连续P操作是指对一般信号量的连续P操作，不包括互斥信号量的P操作，后文默认如此；像这种出现连续P操作的题目，进程所需要的资源个数一般大于1。根据死锁原理，进程获得资源就不会释放，满足请求并保持条件，因此如果两个进程的资源数不够，但是又互相拿着对方所需的资源，那么就会发生死锁。(见题4)。如果有死锁的可能，我们可以在连续的P操作头尾加上互斥锁，使其一气呵成地完成。

  9. 即使不是连续的P操作，也有可能发生死锁：这种情况发生在一个进程既需要多个资源，又需要进行多个操作的情况，因为获得资源和完成操作是交错进行的，既不能一次性获得所有资源，又不能一次性完成所有操作，这时候就容易导致死锁。（参见题目 8）解决办法很简单，把所有申请资源的 P 操作都写在一起，转化为连续的 P 操作，这样就变成了先前所述的第一种情况，用先前所述办法解决即可。
  10. 检查共享缓冲区是否有隐含的死锁：当多个进程共享同一个缓冲区时，就可能会出现其中一个进程推进过快，而导致缓冲区先行被该进程的产品所占满，其他进程无法放入产品的情况。（参见题目 6）\ 比如，进程 A 生产 A，进程 B 生产 B，消费者需要的资源是一个 A 和一个 B，缓冲区空位为 N。现在缓冲区已经放满了 A，消费者已经拥有了 A，还需要 B，但是缓冲区已经满了，进程 B 放不了 B，结果就发生了死锁现象。\ 所以，要想不死锁，就不能让其中一个进程全部占满缓冲区，进程 A 最多只能放 N-1 个 A，多了就肯定死锁；同理，进程 B 最多只能放 N-1 个 B，多了也肯定死锁。\ 这种问题的解决思路一般是将问题转化为两个缓冲区来解决，方法是构造两个虚拟的缓冲区，一个给进程 A 用，一个给进程 B 用，A 缓冲区最大空位为 N-1，B 缓冲区最大空位为 N-1。放产品的时候，需要同时往真实的缓冲区和虚拟缓冲区放。进程先检测真实缓冲区是否有空位；如果有，则再检测自己的虚拟缓冲区是否有空位，如果也有，才能放进真实缓冲区和虚拟缓冲区。
  1. 单生产者、单消费者、单缓冲区、单次取出类问题：

一组生产者进程和一组消费者进程共享一个初始为空、大小为 N 的缓冲区，只有没其他进程使用缓冲区时，其中的一个进程才能访问缓冲区。对于消费者来说，只有缓冲区不空时才能访问缓冲区并读取信息；对于生产者来说，只有缓冲区不满时才能访问缓冲区并写入信息。

代码如上面的伪代码一样；

  1. 双生产者、双消费者、单缓冲区、单次取出类问题：

桌子上有一个盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。只有盘子为空时，爸爸或妈妈才可向盘子中放一个水果;仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出。

semaphore plate = 1;       
//由于盘子的空位只有一个，即这个一般信号量的初值为1，因此可以充当互斥信号量；
semaphore apple = 0;
semaphore orange = 0;

爸爸(){
    while(1){
        P(plate);
        往盘子里放苹果;
        V(apple);
    }
}

妈妈(){
    while(1){
        P(plate);
        往盘子里放橘子;
        V(orange);
    }
}

儿子(){
    while(1){
        P(orange);
        从盘子取出橘子;
        V(plate);
        吃橘子;
    }
}

女儿(){
    while(1){
        P(apple);
        从盘子取出苹果;
        V(plate);
        吃苹果;
    }
}
  1. 双生产者、单消费者、双缓冲区、单次取出类问题

工厂有两个生产车间和一个装配车间，两个车间分别生产 A、B 两种零件，装配车间的任务是把 A、B 两种零件组装成产品。两个生产车间每生产一个零件都要分别把它们送到装配车间的货架 F1 和 F2 上，F1 存放 A，F2 存放 B，F1 和 F2 均只能容纳10个零件。每当能从货架上取到一个 A 和一个 B 后就可以组装成一件产品。整个过程是自动进行的，使用 P、V 操作进行管理，使各车间相互合作、协调工作。

semaphore emptyF1 = 10;
semaphore emptyF2 = 10;
semaphore fullA = 0;
semaphoresemaphore fullB = 0;
semaphore mutexF1 = 1;
semaphore mutexF2 = 1;

A生产车间(){
    while(1){
        生产零件A;
        P(emptyF1);
        P(mutexF1);
        把零件A放到货架F1上;
        V(mutexF1);
        V(fullA);
    }
}

B生产车间(){
    while(1){
        生产零件B;
        P(emptyF2);
        P(mutexF2);
        把零件B放到货架F2上;
        V(mutexF2);
        V(fullB);
    }
}

装配车间(){
    while(1){
        P(fullA);
        P(mutexF1);    //除了对互斥信号量的P操作外没有连续的P操作，不会死锁
        从货架F1上取出零件A;
        V(mutexF1);
        V(emptyF1);
        P(fullB);
        P(mutexF2);
        从货架F2上取出零件B;
        V(mutexF2);
        V(emptyF2);
        零件A和零件B组装产品;
    }
}
  1. 单消费者、单生产者、单缓冲区、连续取出类问题

系统中有多个生产者进程和多个消费者进程，共享一个能存放 1000 件产品的环形缓冲区（初始为空）。当缓冲区未满时，生产者进程可以放入其生产的一件产品，否则等待；当缓冲区未空时，消费者进程可以从缓冲区取走一件产品，否则等待。要求：一个消费者进程从缓冲区连续取出 10 件产品后，其他消费者进程才可以取产品。请使用信号量 P，V（wait()，signal()）操作实现进程间的互斥与同步，要求写出完整的过程，并说明所用信号量的含义和初值。

1718418459150-103af93c-e2e5-4ceb-99c9-3c0ca5238056.png

  1. 既是生产者又是消费者、双缓冲区、单次取出类问题

（信箱辩论问题）有 A、B 两人通过信箱进行辩论，每个人都从自己的信箱中取得对方的问题。将答案和向对方提出的新问题组成一个邮件放入对方的邮箱中。假设 A 的信箱最多放 M 个邮件，B 的信箱最多 放 N 个邮件。初始时 A 的信箱中有 x 个邮件（0 < x < M），B 的信箱中有 y 个（0 < y < N）。辩论者每取出 一个邮件，邮件数减 1。A 和 B 两人的操作过程描述如下：

1718418459340-fb92fb2a-feff-4740-96cd-76016142389b.png

当信箱不为空时，辩论者才能从信箱中取邮件，否则等待。当信箱不满时，辩论者才能将新邮件放入信箱，否则等待。请添加必要的信号量和P、V（或 wait、signal）操作，以实现上述过程的同步。 要求写出完整过程，并说明信号量的含义和初值.

1718418459570-dd7f2c11-16e5-4af0-8b49-970aa7e512ec.png

  1. 双生产者、单消费者、单缓冲区、连续取出类问题

设自行车生产线上有一个箱子，其中有 N 个位置（N ≥ 3），每个位置可存放一个车架或一个车轮，又设有 3 名工人，其活动分别为：

1718418459789-800282f4-384f-44c7-8fe9-29e1b02759dc.png

试分别用信号量与 PV 操作实现三名工人的合作，要求解中不含死锁.

死锁分析：注意，题目 3 是两个生产者进程各自使用自己的缓冲区；而这道题是两个生产者进程共用一个缓冲区，此时就必须要考虑两个进程推进谁快谁慢的问题了，因为如果其中一个进程太快，就会导致缓冲区很快被其中一种产品全部占满，从而发生死锁现象。现在就来考虑下面几种情形：

  • 如果工人 1 速度很快，箱子很快就被车架占满了，工人 2 没法放车轮，工人 3 没法造车，产生死锁；
  • 如果工人 2 速度很快，箱子很快就被车轮占满了，工人 1 没法放车轮，工人 3 没法造车，产生死锁；
  • 如果工人 1 速度很快，箱子很快就被车架占用了，只剩下一个空位，工人 2 放一个车轮，工人 3 只能获取一个车架和一个车轮，没法造车，产生死锁。

解决办法：

对于工人 1，当他发现空位数只剩下两个的时候（即最多只能放N-2个车架），他就不能再放车架了，必须要让工人 2 放车轮；\ 对于工人 2，当他发现空位数只剩下一个的时候（即最多只能放N-1个车轮），他就不能再放车轮了，必须要让工人 1 放车架。\ 所以此时需要再构造两个虚拟的缓冲区，把共享缓冲区问题转化为双缓冲区问题：

semaphore empty = N;         // 箱子内空位数量
semaphore frame = 0;         // 箱子内车架数量
semaphore wheel = 0;         // 箱子内车轮数量
semaphore mutex = 1;         // 互斥访问箱子
semaphore frameMax = N - 2;  // 最多还能放几个车架 (保证至少给车轮留2个空位)
semaphore wheelMax = N - 1;  // 最多还能放几个车轮 (保证至少给车架留1个空位)

工人 1(){
    while(1){
        加工一个车架;
        P(frameMax);         // 检查车架数是否已达上限
        P(empty);            // 检查箱子是否有空位
        P(mutex);            // 获取箱子互斥锁
        车架放入箱中;
        V(mutex);            // 释放箱子互斥锁
        V(frame);            // 增加箱子内车架的数量
    }
}

工人 2(){
    while(1){
        加工一个车轮;
        P(wheelMax);         // 检查车轮数是否已达上限
        P(empty);            // 检查箱子是否有空位
        P(mutex);            // 获取箱子互斥锁
        车轮放入箱中;
        V(mutex);            // 释放箱子互斥锁
        V(wheel);            // 增加箱子内车轮的数量
    }
}

工人 3(){
    while(1){
        // 取车架部分
        P(frame);            // 消耗一个车架信号量
        P(mutex);            // 获取箱子互斥锁
        箱中取出一个车架;
        V(mutex);            // 释放箱子互斥锁
        V(empty);            // 增加一个空位
        V(frameMax);         // 释放一个车架配额，允许工人1继续放车架

        // 取车轮部分
        P(wheel);            // 消耗第一个车轮信号量
        P(wheel);            // 消耗第二个车轮信号量
        P(mutex);            // 获取箱子互斥锁
        箱中取出二个车轮;
        V(mutex);            // 释放箱子互斥锁
        V(empty);            // 增加第一个空位
        V(empty);            // 增加第二个空位
        V(wheelMax);         // 释放第一个车轮配额
        V(wheelMax);         // 释放第二个车轮配额，允许工人2继续放车轮

        组装为一台车;
    }
}
  1. 单生产者、多消费者、单缓冲区、约束取出类问题：

三个进程 P1、P2、P3 互斥使用一个包含 N（N>0）个单元的缓冲区。

P1 每次用 produce() 生成一个正整数并用 put()送入缓冲区某一空单元中；\ P2 每次用 getodd()从该缓冲区中取出一个奇数并用 countodd()统计奇数个数；\ P3 每次用 geteven()从该缓冲区中取出一个偶数并用counteven()统计偶数个数。\ 请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述。

1718418460118-041dc3f3-45fa-4180-a21c-65ef48944ce7.png

  1. 单生产者、单消费者、多类资源需求类问题

某寺庙有小和尚和老和尚若干，有一个水缸，由小和尚提水入缸供老和尚饮用。水缸可以容纳 10 桶水，水取自同一口井中，由于水井口窄，每次只能容纳一个水桶取水。水桶总数为3个。每次入水、取水仅为一桶，且不可同时进行。试给出有关从缸取水、入水的算法描述。

1718418460530-eea8e498-fc2a-4741-8fa4-e5fbcaf2c3fa.png

死锁分析：

  • 同步信号量（代表有多少水、多少空位、多少水桶）用来决定进程能不能做这件事。如果不能做，就在门外等，别占着门。
  • 互斥信号量（代表水井、水缸的使用权）用来保证进程在真正动手做的时候不被打扰。进去做事要快，做完立刻释放。

先 P 同步信号量，后 P 互斥信号量

semaphore tong = 3;         // 物理资源：水桶
semaphore mutex_jing = 1;   // 互斥资源：水井
semaphore mutex_gang = 1;   // 互斥资源：水缸
semaphore gang_full = 0;    // 同步资源：缸里的水量
semaphore gang_empty = 10;  // 同步资源：缸里的剩余空间

小和尚() {
    while(1) {
        P(gang_empty);      // 1. 先确保缸里有空位（同步）
        P(tong);            // 2. 再去拿水桶（资源）

        P(mutex_jing);      // 3. 锁住水井
        到水井打一桶水;
        V(mutex_jing);      // 4. 离开水井

        P(mutex_gang);      // 5. 锁住水缸
        往缸里倒水;
        V(mutex_gang);      // 6. 离开水缸

        V(gang_full);       // 7. 缸里多了一桶水（唤醒可能在等水的老和尚）
        V(tong);            // 8. 归还水桶
    }
}

老和尚() {
    while(1) {
        P(gang_full);       // 1. 先确保缸里有水（同步）
        P(tong);            // 2. 再去拿水桶（资源）

        P(mutex_gang);      // 3. 锁住水缸
        从水缸打一桶水;
        V(mutex_gang);      // 4. 离开水缸

        V(gang_empty);      // 5. 缸里空出一个位置（唤醒可能在等空位的小和尚）
        V(tong);            // 6. 归还水桶

        喝水; 
    }
}

读者—写者问题(重点真题尚未考过)

问题描述：有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程(读进程或写进程)同时访问共享数据时则可能导致数据不一致的错误。因此要求：

  • 允许多个读进程可以同时对文件执行读操作；(注意这里的读者进程与消费者进程不同，读者进程在读数据后并不会改变数据，而消费者则会将当前数据清除)
  • 同一时刻只允许一个写者往文件中写信息；(两个及以上写进程同时共享数据可能会导致数据错误覆盖的问题)
  • 任一写者在完成写操作之前不允许其他任何进程工作；
  • 写者执行写操作之前，应让已有的读者写者全部退出； (读进程与写进程同时共享数据，可能导致读出的数据不一致的问题)
  • 应用场景：适用于并发线程读取和修改数据结构、数据库或文件系统的任何情况。 在写入或修改数据结构时，通常需要禁止其他线程读取，以防止读者线程中断正在进行的修改并读取不一致或无效的数据。与生产者 - 消费者问题一样，解决方案是不对称的。 读者和写者在进入关键部分之前执行不同的代码。 同步约束是：
  • 任何数量的读者可以同时进入关键部分。
  • 写者必须拥有对关键部分的独占访问权。

换句话说，当任何其他线程（读者或者写者）在那里时，写者不能进入临界区；而当写者在那里时，其他线程都不可以进入。

这里的排除模式可以被称为分类互斥（categorical mutual exclusion）。 临界区中的线程不一定排除其他线程，但是在临界区中存在一个类别会排除其他类别。

通用解题模板：读者写者问题，其本质就是连续多个同类进程访问同一个临界资源的问题。

第一个进程开始访问临界资源前，需要对资源加上互斥锁，后面的进程再访问时就不用再对资源加互斥锁了，直到最后一个进程访问完后，发现自己是最后一个进程，就解锁互斥锁。这就像一种情况：第一个人进房间时必须顺手开门，后面进来的人和离开的人就不用开门，直到最后一个人离开房间时才需要顺手关门。

代码的通用模板是“三段式”，如下：

1718418460473-9ec22bc5-58fd-48f5-98ff-e7dafce1ef34.png

  1. 实现方法一：读者优先

基于读者优先策略的方法，只要有一个读者处于活动状态，后来的读者都会被接纳。如果读者源源不断地出现地话，那么写者就始终处于阻塞状态，可能会“饿死”。

1718418460824-5ea5da7e-40b8-4cd4-8fe3-0a073dcf52a3.png

假设每个读者的读操作都耗时较长，读者写者到达的顺序是：读者1---读者2---读者3---写者A---读者 4---写者 B---读者 5，则：

  • 读者 1、读者 2、读者 3 到达，rw加锁，开始读；
  • 写者 A 到达，但是读者还在读，未释放 rw 锁，因此不能写；
  • 读者 4 到达，可以开始读；
  • 写者 B 到达，但是读者还在读，未释放 rw 锁，因此不能写；
  • 读者 5 到达，可以开始读；\ 等到读者们都读完，释放 rw 锁，写者才可以开始写。
  1. 实现方法二：写者优先

所谓写者优先，即：当有读者进程正在执行，写者进程发出申请，这时应该拒绝其他读者进程的请求，等待当前读者进程结束后立即执行写者进程，只有在无写者进程执行的情况下才能够允许读者进程再次执行。

为此在读者进程的基础上，增加信号量read值为1，用来禁止所有的读进程；增加一个写者进程的计数器，初值为0，用于实现写优先；另外自然也要为写者进程的计数器设置一个互斥信号量用来互斥访问；因此，伪代码如下：

1718418460836-b18d6728-c8c4-43f0-bae6-92fde7569358.png

注意，这里 read 的作用，开始有多个读者读数据，它们全部进入读者队列，此时来了一个写者，执行了 P(read) 之后，后续的读者由于阻塞在 read 上，都不能再进入读者队列，而写者到来，则可以全部进入写者队列，因此保证了写者优先。

同时，第一个写者执行了 P(read) 之后，也不能马上开始写，必须等到所有进入读者队列的读者都执行完读操作，通过 V(write) 唤醒写者的写操作。

假设每个读者的读操作都耗时较长，读者写者到达的顺序是：读者1---读者2---读者3---写者A---读者 4---写者 B---读者 5，则：

  • 读者 1、读者 2、读者 3 到达，Write 加锁，开始读；
  • 写者 A 到达，Read 加锁，但是读者还在读，Write 锁仍未释放，因此不能写；
  • 读者 4 到达，Read 锁仍未释放，不能开始读；
  • 写者 B 到达，Write 锁仍未释放，因此不能写；
  • 读者 5 到达，Read 锁仍未释放，不能开始读；
  • 等到读者 1 到 3 都读完，释放 Write 锁，写者 A 才可以开始写，写完后 Write 解锁。由于写者 A 不是最后一个写进程，因此 Read 不解锁；
  • 写者 B 进行写操作，写完后 Write 解锁，由于写者 B 是最后一个写进程，因此 Read 解锁；
  • 读者 4、读者 5 依次进行读操作。
  1. 实现方法三：读写公平法

公平策略：

  • 优先级相同；
  • 写者、读者互斥访问；
  • 只能一个写者访问临界区；
  • 可以有多个读者同时访问临界资源；

为实现读写公平，我们设置一个互斥信号量queue,其作用是让读者和写者进行排队，当有reader进程执行时，queue = 0 ,因此writer进程会进入等待，直到queue变为1；当writer进程执行时同理；因此，我们借助queue实现了读写进程的优先级平等。

1718418461128-4cdf42df-d915-44f4-92c9-1518855acf49.png

看完代码不知你是否有这样的疑问，为什么加了一个信号量 queue，就实现了公平竞争？

对比方案一的读者优先策略，可以发现，读者优先中只要后续有读者到达，读者就可以进入读者队列， 而写者必须等待，直到没有读者到达。

没有读者到达会导致读者队列为空，即 rcount=0，此时写者才可以进入临界区执行写操作。

而这里 queue 的作用就是阻止读者的这种特殊权限（特殊权限是只要读者到达，就可以进入读者队列）。

比如：开始来了一些读者读数据，它们全部进入读者队列，此时来了一个写者，执行 P(queue) 操作，使得后续到来的读者都阻塞在 queue 上，不能进入读者队列，这会使得读者队列逐渐为空，即 rcount 减为 0。

这个写者也不能立马开始写（因为此时读者队列不为空），会阻塞在信号量 rw 上，读者队列中的读者全部读取结束后，最后一个读者进程执行 V(rw)，唤醒刚才的写者，写者则继续开始进行写操作。

假设每个读者的读操作都耗时较长，读者写者到达的顺序是：读者1---读者2---读者3---写者A---读者 4---写者 B---读者 5，则：

  • 读者 1、读者 2、读者 3 到达，rw 加锁，开始读；
  • 写者 A 到达，queue 加锁，但是读者还在读，rw 锁仍未释放，因此不能写；
  • 读者 4 到达，但是读者还在读，queue 和 rw 锁仍未释放，不能开始读；
  • 写者 B 到达，queue 锁和 rw 锁仍未释放，因此不能写；
  • 读者 5 到达，但是读者还在读，queue 和 rw锁仍未释放，不能开始读；
  • 等到读者 1 到 3 都读完，释放 rw 锁，写者 A 才可以开始写；
  • 接下来就是按读者 4、写者 B、读者 5 的顺序依次访问文件。

读者—写者相关拓展习题：

该类问题的特点是：分类互斥即一般来说同类进程不互斥，异类进程互斥的问题便可以考虑是不是类似于读者写者的问题。关键点是设置一个计数器，第一个读者读之前负责上锁，最后一个读者读完后负责解锁。

  1. 有桥如下图所示，车流如箭头所示，桥上不允许两车交汇，但允许同方向多辆车依次通过（即桥上可以有多个同方向的车）。用P、V操作实现交通管理以防止桥上堵塞。

1718418461591-2302f6a7-aeae-411f-aeb8-e97244968bff.png

1718418461680-a64fe44c-368e-4929-a1bb-f562feea0274.png

  1. 更衣室问题：某男⼦⾜球俱乐部，有教练、队员若⼲。每次⾜球训练开始之前，教练、球员都需要先进⼊更⾐室换⾐服，可惜俱乐部只有⼀个更⾐室。教练们脸⽪薄，⽆法接受和别⼈共⽤更⾐室。队员们脸⽪厚，可以和其他队员⼀起使⽤更⾐室。如果队员和教练都要使⽤更⾐室，则应该让教练优先。请使⽤ P、V 操作描述上述过程的互斥与同步，并说明所⽤信号量及初值的含义。\ 【解答】把教练视为写进程，把队员视为读进程，更衣室视为缓冲区，则该题需要实现写进程优先。
  2. 录像厅问题：假设一个录像厅有 0,1,2 三种不同的录像片可由观众选择放映。录像厅的放映规则为：
  3. 任何时刻最多只能放映一种录像片，正在放映的录像片是自动循环放映的。最后一个观众主动离开时结束当前录像片的放映。
  4. 选择当前正在放映录像片的观众可立即进入，允许同时有多位选择同一中录像片的观众同时观看，同时观看的观众数量不受限制。
  5. 等待观看其他录像片的观众按到达顺序排队，当一种新的录像片开始放映时，所有等待观看该录像片的观众可一次进入录像厅同时观看。

1718418462086-b37e7ac9-5320-49c6-bbec-b4df7ce78e69.png

  1. 某公司有3个项目团队，分别是Java团队、C++团队、Python团队，每个团队有多名员工。该公司只有一个会议室可以使用。当会议室空闲时，任何一位员工都可以进人并使用会议室。当会议室有人时，员工需要观察此时是哪些人在使用会议室，如果是自己团队的人在使用会议室，则员工可以直接进人会议室；如果是其他团队的人在使用会议室，则该员工必须等他们离开后才能进人会议室。请使用信号量的PV操作描述上述过程中的同步与互斤关系，并说明所用信号量及初值的含义。
  2. 某杂技团进行走钢丝表演，在钢丝的A、B两端各有若干名演员在等待表演，只要钢丝上无人便允许一名演员从钢丝的一端走到另一端。现要求两端的演员交替地走钢丝并在另一端排队等待走钢丝，从A端的一名演员先开始走。\ 请问：若把一名演员看作一个进程，怎样用PV操作进行控制？请写出正确的算法。
  3. 某饮品店只有一台榨汁机。该饮品店只提供新鲜的橙汁和芒果汁。为了减少洗榨汁机的次数，\ 更快地为顾客提供服务，饮品店规定：如果第一个顾客点的是橙汁，后面所有点橙汁的顾客都优先被服务，而点芒果汁的顾客必须等待，只有所有点橙汁的顾客都拿到橙汁，再没有顾客点橙汁了才开始提供芒果汁。当然这个规定反之亦然。请用PV操作描述点橙汁和芒果汁客人，要求说明信号量的含义及初值。

理发师问题

  • 理发师问题万能模板 ：理发师问题与生产者消费者问题不同，生产者消费者问题是“生产-消费”问题，理发师问题是“服务-被服务”的问题。然而，这两个问题从根本上来说思路是一样的，下面请大家仔细研究这几个模板。

  • 万能模板 1——无等待上限，服务人员可休息

题目：店里有 N 名服务人员，没有顾客时服务人员休息，有顾客时就叫号。顾客到店时，需要先取号，并叫醒一名休息的服务人员（如果有），并等待叫号。

【解题思路】：本题类似于生产者消费者问题，顾客是生产者，生产顾客资源；服务人员是消费者，消费顾客资源。反过来，服务人员是生产者，生产服务人员资源；顾客是消费者，消费服务人员资源。所以可以按生产者消费者的思路来解答。

服务人员叫号后，意味着有一个服务人员前来提供服务，可视为生产了一个服务人员；顾客取号后，意味着多了一名顾客在等待，可视为生产了一名顾客。而取号和叫号类似于放入缓冲区的操作，需要一个互斥锁。

1718418462201-4916c9db-e3cf-4ce9-b141-2b7383829c8d.png

  1. 万能模板 2——有等待上限，服务人员可休息

店里有 N 名服务人员，没有顾客时服务人员休息，有顾客时就叫号。店里有 M 个空位。顾客到店时，需要先检查是否 M 个位置被其他顾客都占用了，若是，则离店；若否，则占用一个位置取号等待，并叫醒一名休息的服务人员（如果有），并等待叫号。

【解题思路】可以先在上题的基础上增加一个变量 waiting，记录当前正在等待的顾客数。当顾客取号后，顾客等待数量加 1,；当服务人员叫号后，顾客等待数量减 1，然后只需在顾客进程加入一个判断，若顾客等待数量超过上限，则直接离店即可，代码如下：

1718418462235-71766036-1320-4b00-b79b-8732b24b5396.png

  1. 万能模板 3——有等待上限，服务人员忙等

店里有 N 名服务人员，没有顾客时服务人员也不可以休息，必须“忙等”，有顾客时就叫号。店里有 M 个空位。顾客到店时，需要先检查是否 M 个位置被其他顾客都占用了，若是，则离店；若否，则占用一个位置取号等待，并叫醒一名休息的服务人员（如果有），并等待叫号。

【解题思路】在没有顾客时，服务人员忙等，不断询问有没有顾客，所以可以在上题基础上，在服务人员进程里加入判断顾客数量的语句。如果有顾客，则按之前的操作进行；如果没有顾客，则直接进行下一轮循环。因此，对顾客资源的 P 操作就不需要了，因为 P 操作会引发阻塞或休息。如下：

1718418462248-ee981255-0dd3-475c-a769-eda3a803d2d0.png

  1. 万能模板 4——座位已满后顾客仍继续等待，服务人员可休息

店里有 N 名服务人员，没有顾客时服务人员休息，有顾客时就叫号。

店里有 M 个空位。顾客到店时，需要先检查是否 M 个位置被其他顾客都占用了，若是，则等待座位空余(即先等空位再等叫号)；若否，则占用一个位置取号等待，并叫醒一名休息的服务人员（如果有），并等待叫号。

【解题思路】把前面的变量waiting变为信号量 empty即可，用来记录店里的空位，这样就可以起到阻塞等待的作用。

1718418462421-b50bdd74-2fbc-4f36-b81e-2a00d14dd2d4.png

小结：

  • 大家在学习这部分内容的时候，只需把模板 1 的思路记下来即可，其余三个都是从第一个模板延伸而来。做题时，先把模板 1 默写出来，然后在此基础之上按题意进行修修补补。另外是不是有人发现了，这些代码跟服务人员的数量是不是没有关系的？因为我们模板的服务人员进程一共有 N 个，一个进程对应一个服务人员（当然也可以一个进程对应 N 个服务人员，需要额外再加一个记录服务人员的信号量），以后做这种题可以直接无视服务人员的数量，这是冗余条件。
  • 以上这些模板都没有满足先来先服务，即不能按照顾客到来的顺序为他们提供服务，这是因为当理发师进程V(server)后，任意一个顾客进程都有可能继续执行。解决方案是采用名为queue的信号量队列，具体操作见此专栏。408一般不会要求先来先服务，这个不用过多了解。

  • 补充练习题：

  • 理发店里有一位理发师、一把理发椅和 n 把供等候理发的顾客坐的椅子。如果没有顾客，理发师便在理发椅上睡觉；当一个顾客到来时，它必须叫醒理发师；如果理发师正在理发时又有顾客来到，那么，如果有空椅子可坐，顾客就坐下来等待，否则就离开理发店。

  • 某银行提供 1 个服务窗口和 10 个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号，若没有空座位，则离开。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：

1718418462542-259da3a8-e3f2-4730-8278-1cd4725ce191.png

请添加必要的信号量和 P、V（或 wait()、signal()）操作，实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。

  1. 某银行提供 1 个服务窗口和 10 个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号; 若没有空座位就站着等待，直到有座位了再坐下来等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：和上题一样。
  2. 有这样一家寿司店，这家店非常上流，有n位寿司师傅为客人提供一对一服务，现场做料理。一位客人到店时，需要先取号，并等待叫号。这家店老板很黑心，没有客人的时候，寿司师傅也不可以睡觉休息，必须“忙等”。 有客人的时候，只要有空闲的寿司师傅，就叫号，让下位客人进店就餐，并由寿司师傅现场做料理。\ 请使用P、V操作描述上述过程的互斤与同步，并说明所用信号量及初值的含义。
  3. 面包店有很多面包，由n名销售人员推销，每名顾客进店后取一个号，并且等待叫号，当一名销售人员空闲时，就叫下一个号，试设计一个使销售人员和顾客同步的算法。
  4. 睡觉助教问题(《操作系统概念》P205)：\ 某大学计算机科学系有一名助教，他在正常的工作时间帮助本科生完成编程任务。助教办公室相当小，只有一张桌子、一把椅子和一台电脑。办公室外面的走廊里有三把椅子，如果他正在帮助一个学生，其它学生可以坐在那里等待。当没有学生在工作时间需要帮助时，助教就坐在桌子旁边打个盹儿。如果学生在办公时间到达，发现助教睡着了，学生必须叫醒助教寻求帮助。如果一个学生来了并且发现他现在正在帮助另一个学生，那么他会坐在走廊里的一把椅子上并等待。如果没有椅子可用，学生稍后会回来。请使用P、\ V操作描述上述过程的互斤与同步，并说明所用信号量及初值的含义。

1718418462736-3969c84a-cb13-45f1-9a4d-d5a0eeda7632.png

哲学家进餐问题

题目描述：一张圆桌上坐着五名哲学家，在每两名哲学家中间放着一根筷子，哲学家们的生活方式只做两件事：思考和进餐。饥饿时哲学家必须同时拿起两只筷子时才能进餐，进餐完毕后，放下筷子，进行思考。如果筷子被紧挨着的一名哲学家使用着，则不能争抢，必须等待，当这名哲学家就餐完毕后，放下筷子，才能使用。

该类题目特点：只有一类进程，要占用多种资源才能运行；

解题思路探究：在哲学家进餐问题中，我们解决死锁的方法有3种：

  1. 限制并发进程数：例如限制同一时间内只能有一个哲学家进餐(虽然通用，但是并发度不高，

示意图：1718418463247-da75aa47-8392-4aea-8da4-6c17fd5b4cb4.png

1718418463169-be8bbbe8-1626-4f8e-b4d1-26d2e71d2fa6.png

  1. 限制申请资源的顺序：奇数号哲学家必须先拿右手边的筷子，偶数号哲学家必须先拿左手的筷子(不通用，不建议使用，了解即可)

示意图：1718418463798-b5554e68-0ba1-4ea3-b078-73a125de2f29.png

1718418463378-33082f26-13b1-4b47-8ce3-b51e533301a3.png

上面的程序，在 P 操作时，根据哲学家的编号不同，拿起左右两边叉子的顺序不同。另外，V 操作不会阻塞的。这样可以避免死锁，并且可以有两个哲学家同时进餐。

  1. 让进程一口气取得所有资源，再开始运行。即仅当一个哲学家左右两边的筷子都可用时才允许哲学家拿筷子。代码见例题1.

其中方法二适用范围很窄，很难迁移到其他的类哲学家进餐问题，而另外两种方法的思想可以迁移到大多数这种类似的问题以解决“死锁”，这里我们采用最后一种思想：破坏“请求并保持”条件，让进程一口气获得所有所需的资源。

通用解题模板：

  • step1: 先定义一把大互斥锁semaphore lock = 1;
  • step2: 定义资源数 ：比如，a 资源有 9 个，b 资源有 8 个，c 资源有 5 个，则：

1718418463493-ce6a661e-43ce-40a7-b724-d8a7b6968dcb.png

  • step3: 默写代码模板：\ 代码思路：
  • 申请资源：
    • 进程先检测目前资源总数满不满足自身的需求。
    • 若满足，则一气呵成地把所需要的资源全部占用。然后开始完成操作
    • 若不满足，则忙别的事，然后进行下一轮检测。
  • 归还资源：
    • 使用完资源后，进程也需要一气呵成地把所需要的资源全部归还。

1718418463777-267d2d54-5323-4795-ad36-dabf17547862.png\ 这种解题思路即：破坏“请求和保持”条件，采⽤“静态分配”的思想，让进程⼀⼝⽓获得所有资源，再开始运⾏（可参见生产者消费者模型的“老和尚喝水、小和尚取水”的问题，那道题在进程开始操作前先连续 P 操作申请资源，全部申请完资源后再执行操作），如果不采用int

变量全部采用信号量来写的话，可以这样写，只不过并发度可能没有上面那种高： 1718418463869-603e8df7-afd0-4ca8-bfb3-d6dcb26b6fc7.png

相关例题：

  1. 经典版哲学家进餐问题

1718418463965-de875697-6c3d-483c-9df7-013935219352.png

  1. 加强版哲学家问题（1）：有 n（n ≥ 3）位哲学家围坐在一张圆桌边，每位哲学家交替地就餐和思考。在圆桌中心有 m（m ≥ 1）个碗，每两位哲学家之间有一根筷子。每位哲学家必须取到一个碗和两侧的筷子后，才能就餐，进餐完毕，将碗和筷子放回原位，并继续思考。 为使尽可能多的哲学家同时就餐，防止出现死锁现象。请使用信号量的 P、V 操作 [wait()、signal() 操作] 描述上述过程中的互斥与同步，并说明所用信号量及初值的含义。

1718418464075-7a9e5031-a22b-4fa9-ae06-f80b55583314.png

  1. 加强版哲学家进餐问题（2）：俗话说，“⼲饭⼈，⼲饭魂，⼲饭⼈吃饭得⽤盆”。⼀荤、⼀素、⼀汤、⼀⽶饭，是每个⼲饭⼈的标配。饭点到了，很多⼲饭⼈奔向⻝堂。每个⼲饭⼈进⼊⻝堂后，需要做这些事：拿⼀个盆打荤菜，再拿⼀个盆打素菜，再拿⼀个盆打汤，再拿⼀个盆打饭，然后找⼀个座位坐下⼲饭，⼲完饭把盆还给⻝堂，然后跑路。现在，食堂⾥共有 N 个盆，M 个座位。请使⽤ P、V 操作描述上述过程的互斥与同步，并说明所⽤信号量及初值的含义。

1718418464297-0b658c50-734b-4aa6-87ef-8c79a4b1b157.png

  1. 老和尚喝水、小和尚取水问题：某寺庙有小和尚和老和尚若干，有一个水缸，由小和尚提水入缸供老和尚饮用。水缸可以容纳 10 桶水，水取自同一口井中，由于水井口窄，每次只能容纳一个水桶取水。水桶总数为3个。每次入水、取水仅为一桶，且不可同时进行。试给出有关取水、入水的算法描述。

这题刚刚在开头已经提到过，在生产者消费者问题那里也已经做过了一遍，那么我首先说明一下为什么又把这道题目放上来。因为大部分生产者消费者的题目的进程都只需要一个资源，但有些生产者消费者的题目需要多类或多个资源，这个时候我们就可以按哲学家问题的角度去看问题，按照这里所给出的模板，代码并发度比之前的要高。所以，这类多资源题目很有必要再放上来分析，这也有助于我们打开思路。

1718418464382-58ee310b-5c0a-4a06-a4da-9982df8f7dae.png

吸烟者问题

问题描述：假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉，但是要卷起并抽掉一支烟，抽烟者需要三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草，第二个拥有纸，第三个拥有胶水。供应者无限地提供三种材料，供应者每次将两种材料放在桌子上，拥有剩下那种材料的卷烟者卷一根烟并抽掉它，并给供应者一个告诉完成信号，供应者就会放另外两种材料在桌上，这种过程一直重复。

1718418464388-243b2ce3-dac6-46f0-81ad-a4238b0a8bc6.png

  • 解题思路：该问题的本质依然是“生产者-消费者”问题，可以用“生产者-消费者”问题的思路去解决,可以看作是“可生产多种产品的单生产者-多消费者问题”
  • 同步关系如图：注意“前V后P”

1718418464492-5c0b91c6-2ade-41d5-8719-2f47c4373714.png

1718418464653-fe294929-2ab1-4c27-9f3a-ab1c7194c206.png

同步问题

  • 同步过程分析：AOV网每一个顶点代表一个任务，每一条有向边代表一个同步关系，对于任意一条边(u,v) ， u 必须在 v之前完成。分析每一个顶点所代表的任务、该顶点的入边（该任务的前置任务）表示的同步关系以及该顶点的出边（该任务的后序任务）表示的同步关系。\ 为了方便，可以先对AOV网进行拓扑排序，按照拓扑排序序列顺序依次对每个任务进行分析。

  • 历年真题

  • 2020年第45题

现有 5 个操作 A、B、C、D 和 E ，操作 C 必须在 A 和 B 完成后执行，操作 E 必须在 C 和 D 完成后执行。请使用信号量的wait()，signal()操作（P、V操作）描述上述操作之间的同步关系，并说明所用信号量和初值。

解答：首先列出前置关系：

任务 前置任务
A 无
B 无
C A,B
D 无
E C,D

然后画出AOV网： 1718418464787-7c58e3a2-a3f6-49f8-8a52-fccadb35c74a.png

进行拓扑排序：A,B,C,D,E

法一：每个任务一个信号量，即每个AOV网中每个顶点构造一个信号量，默认初始为0。

每个操作需要消耗前置操作信号量，生成当前操作信号量。

1718418465088-5740223d-6b53-4da4-90a6-9c944cebdf30.png

法二：即每个AOV网中每条边（表示一个同步关系）构造一个信号量，默认初始为0。

1718418465091-e8f5ae59-bd2d-4f1e-8357-843e594900b8.png

  1. 2022年第46题

某进程的两个线程 T1和 T2 并发执行 A、B、C、D、E 和 F共 6 个操作，其中 T1执行 A、E和F，T2 执行B、C和D。下图表示上述 6 个操作的执行顺序所必须满足的约束：C 在 A和 B完成后执行， D和 E 在 C完成后执行，F 在 E完成后执行，请使用信号量 wait()、signal()操作描述 T1和 T2之间的同步关系，并说明所用信号量的作用及其初值。

1718418465194-53611b5c-f1b2-42c8-9a7e-7e5986ea551b.png

解答：题目已给出了AOV网，下面列出前置关系：

任务 前置任务
A 无
B 无
C A,B
D C
E C
F E

进行拓扑排序：A,B,C,D,E,F\ 法一：每个任务一个信号量，即每个AOV网中每个顶点构造一个信号量，默认初始为0。\ 每个操作需要消耗前置操作信号量，生成当前操作信号量。唯一要注意的是每次 C 操作完成后要增加两个C的信号量，由于 D 和 E 分别要消耗一个 C 的信号量。 1718418465574-b424e264-c1eb-4b65-bee8-9c1b681b71f4.png\ 法二：每个同步关系一个信号量\ 即每个AOV网中每条边（表示一个同步关系）构造一个信号量，默认初始为0。 1718418465604-4fc110d7-a34e-4ddf-9820-5e2d694c8048.png\ 上述同步关系可以进行简化，同一个线程中的同步关系可以不用设置信号量，跨线程执行的只有 C 的前置 A 和 E 的前置 C。只需要删除不跨线程的信号量即可，简化后如下： 1718418465875-f4a2c6dc-2401-481f-9466-e59f4c88abf6.png

考场上时间紧迫，没有优化到最简也是没有关系的。

  • 其他习题：

1.医生为病人看病，需要化验，于是医生开出化验单，病人到化验室化验，化验结果送回医生处供医生诊断。医生看病为一个进程，化验室化验为一个进程，二者并发执行且需要交换信息。\ 请回答下列问题：

(1)用P、V操作管理这些并发进程时，应怎样定义信号量，写出信号量的初值及含义。

(2)根据所定义的信号量，把应执行的PV操作过程写出来，以保证进程能够正确地并发执行。

解答：（1）因为医生看病诊断进程和化验室化验进程之间为同步关系。所以定义两个信号量S1和S2，S1表示有无化验单，S2表示有无化验结果。初始值均为0。本题结构简单就不用画出AOV网和列出前置关系表了。

1718418465944-c1a6893b-6928-4226-9530-eca97adb219f.png