操作系统—信号量和管程 & 经典同步问题

背景

信号量

• 信号量（semaphore），抽象数据类型

  ➢ 一个整形（$sem$），具有两个原子操作

  ➢ $P()$：$sem$ 减 $1$，如果 $sem<0$，等待，否则继续

  ➢ $V()$：$sem$ 加 $1$，如果 $sem\le 0$，唤醒一个等待的 $P$

• 信号量类似铁路

  ➢ 初始化 $2$ 个资源控制信号灯

  gif

  

  进入临界区的进程执行 $P()$ 操作，当临界区已经有 $2$ 个进程时，信号量不够，变为红灯，再来的进程只能等待，直到某一个进程离开了临界区，变为绿灯，此时进程执行 $V()$ 操作，将等待的进程唤醒，进入临界区。

• Dijkstra在20世纪60年代提出

  ➢ P：Prolaag（荷兰语简称“Probeer te Verlagen”，或尝试减少）

  ➢ V：Verhoog（荷兰语增加）

• 在早期的操作系统主要是同步原语

  ➢ 例如，原Unix

  ➢ 现在很少用（但是还是非常重要在计算机科学中研究）

信号量的特性

• 信号量是整数

• 信号量是被保护的变量

  ➢ 初始化完成后，唯一改变一个信号量的值的办法是通过 $P()$ 和 $V()$

  ➢ 操作必须是原子

• $P()$ 能够阻塞，$V()$ 不会阻塞

• 我们假定信号量是 “公平的”

  ➢ 没有线程被阻塞在 $P()$ 仍然堵塞如果 $V()$ 被无限频繁调用（在同一个信号量）

  ➢ 在实践中，FIFO经常被使用，也就是先进先出

自旋锁（Spinlock）能否是FIFO类型？

不能。

信号量的实现

• 两个类型信号量

  ➢ 二进制信号量：可以是 $0$ 或 $1$

  ➢ 一般/计数信号量：可取任何非负值

  ➢ 两者相互表现（给定一个可以实现另一个）

• 信号量可以用在 $2$ 个方面

  ➢ 互斥

  ➢ 条件同步（调度约束：一个线程等待另一个线程的事情发生）

信号量使用

• 用二进制信号量实现的互斥

  

  mutex = new Semaphore(1);mutex->P();...Critical Section;...mutex->V();

• 用二进制信号量实现的调度约束

  

  condition = new Semaphore(0);// Thread A...condition->P(); // 等待线程B某一些指令完成之后再继续运行，在此阻塞...// Thread B...condition->V(); // 信号量增加唤醒线程A...

生产者-消费者问题

• 一个线程等待另一个线程处理事情

  ➢ 比如生产东西或消费东西（生产者消费者模式）

  ➢ 互斥（锁机制）是不够的

• 例如：有界缓冲区的生产者-消费者问题

  ➢ 一个或者多个生产者产生数据将数据放在一个缓冲区里

  ➢ 单个消费者每次从缓冲区取出数据

  ➢ 在任何一个时间只有一个生产者或消费者可以访问该缓冲区

  

• 正确性要求

  ➢ 在任何一个时间只能有一个线程操作缓冲区（互斥）

  ➢ 当缓冲区为空时，消费者必须等待生产者（调度/同步约束）

  ➢ 当缓存区满，生产者必须等待消费者（调度/同步约束）

• 每个约束用一个单独的信号量

  ➢ 二进制信号量互斥

  ➢ 一般信号量fullBuffers

  ➢ 一般信号了emptyBuffers

  class BoundedBuffer {mutex = new Semaphore(1);fullBuffers = new Semaphore(0);  // 说明缓冲区初始为空 emptyBuffers = new Semaphore(n); // 当前生产者可以往buffer中存入n个数据(size)}// 生产者 添加数据BoundedBuffer::Deposit(c){emptyBuffers->P();mutex->P();Add c to the buffer;mutex->V();fullBuffers->V();}// 消费者 取出数据BoundedBuffer::Remove(c){fullBuffers->P();mutex->P();Remove c from buffer; mutex->V();emptyBuffers->V();}

  P、V操作的顺序有影响吗？

信号量实现

• 使用硬件原语

  ➢ 禁用中断

  ➢ 原子指令（test-and-set）

• 类似锁

  ➢ 例如：“禁用中断”

  

  class Semaphore {int sem;WaitQueue q;}Semaphore::P() {--sem;if (sem < 0) {Add this thread t to q;block(p);}}Semaphore::V() {++sem;if (sem <= 0) {Remove a thread t from q;wakeup(t);}}

• 信号量的双用途

  ➢ 互斥和条件同步

  ➢ 但等待条件是独立的互斥

• 读/开发代码比较困难

  ➢ 程序员必须非常精通信号量

• 容易出错

  ➢ 使用的信号量已经被另一个线程占用

  ➢ 忘记释放信号量

• 不能够处理死锁问题

管程

• 目的：分离互斥和条件同步的关注

• 什么是管程（Moniter）

  ➢ 一个锁：指定临界区

  ➢ 0或者多个条件变量：等待，通知信号量用于管程并发访问共享数据

• 一般方法

  ➢ 收集在对象 / 模块中的相关共享数据

  ➢ 定义方法来访问共享数据

  

• $Lock$

  ➢ Lock::Acquire()：等待直到锁可用，然后抢占锁

  ➢ Lock::Release()：释放锁，唤醒等待者如果有

• $ConditionVariable$（条件变量）

  ➢ 允许等待状态进入临界区

  ​ √ 允许处于等待(睡眠)的线程进入临界区

  ​ √ 某个时刻原子释放锁进入睡眠

• $Wait()operation$

  ➢ 释放锁，睡眠，重新获得锁放回

• $Signal()operation(orbroadcast()operation)$

  ➢ 唤醒等待者（或者所有等待者），如果有

• 实现

  ➢ 需要维持每个条件队列

  ➢ 线程等待的条件等待signal()

  

  class Condition {int numWaiting = 0;WaitQueue q;}Condition::Wait(lock) {numWaiting++;Add this thread t to q;release(lock);schedule(); // need mutexrequire(lock);}Condition::Signal() {if (numWaiting > 0) {Remove a thread t from q;wakeup(t); // need mutexnumWaiting--;}}

• 管程解决生产者-消费者问题

  

  class BoundedBuffer {    ...Lock lock;int count = 0; // buffer为空Condition notFull, notEmpty;};BoundedBuffer::Deposit(c) {lock->Acquire(); // 管程的定义:只有一个线程能够进入管程while (count == n)notFull.Wait(&lock); // 释放前面的锁Add c to the buffer;count++;notEmpty.Signal();lock->Release();}BoundedBuffer::Remove(c) {lock->Acquire();while (count == 0)notEmpty.Wait(&lock);Remove c from buffer;count--;notFull.Signal();lock->Release();}

• 管程条件变量的释放处理方式

  

  ---

  

总结

• 开发 / 调试并行程序很难

  ➢ 非确定性的交叉指令

• 同步结构

  ➢ 锁：互斥

  ➢ 条件变量：有条件的同步

  ➢ 其他原语：信号量

• 怎么样有效地使用这些结构

  ➢ 制定并遵循严格的程序设计风格 / 策略

经典同步问题

读者-写者问题

• 动机

  ➢ 共享数据的访问

• 两种类型的使用者

  ➢ 读者（不修改数据）

  ➢ 写者（读取和修改数据）

• 问题的约束

  ➢ 允许同一时间有多个读者，但在任何时候只有一个写者

  ➢ 当没有写者时，读者才能访问数据

  ➢ 当没有读者和写者时，写者才能访问数据

  ➢ 在任何时候只能有一个线程可以操作共享变量

• 多个并发进程的数据集共享

  ➢ 读者：只读数据集；他们不执行任何更新

  ➢ 写者：可以读取和写入

• 共享数据

  ➢ 数据集

  ➢ 信号量 $CountMutex$ 初始化为 $1$

  ➢ 信号量 $WriteMutex$ 初始化为 $1$

  ➢ 整数 $Rcount$ 初始化为 $0$（当前读者个数）

读者优先设计

只要有一个读者处于活动状态， 后来的读者都会被接纳。如果读者源源不断的出现，那么写者使用处于阻塞状态。

信号量实现

// Writersem_wait(WriteMutex);write;sem_post(WriteMutex);// Readersem_wait(CountMutex);if (Rcount == 0)sem_wait(WriteMutex); // 确保后续不会有写者进入++Rcount;read;--Rcount;if(Rcount == 0)sem_post(WriteMutex); // 全部读者全部离开才能唤醒写者sem_post(CountMutex);

写者优先设计

一旦写者就绪，那么写者会尽可能的执行写操作。如果写者源源不断的出现的话，那么读者就始终处于阻塞状态。

信号量实现

// WriterDatabase::Write() {Wait until readers/writers;write database;check out - wake up waiting readers/writers;}// ReaderDatabase::Read() {Wait until no writers;read database;check out - wake up waiting writers;}

管程实现

// 全局变量AR = 0; // # of active readersAW = 0; // # of active writersWR = 0; // # of waiting readersWW = 0; // # of waiting writersCondition okToRead;Condition okToWrite;Lock lock;

// ReaderPublic Database::Read() {// Wait until no writers;StartRead();read database;// check out - wake up waiting writers;DoneRead();}Private Database::StartRead() {lock.Acquire();while ((AW + WW) > 0) { // 关注等待的Writer，体现出写者优先WR++;okToRead.wait(&lock);WR--;}AR++;lock.Release();}Private Database::DoneRead() {lock.Acquire();AR--;if (AR == 0 && WW > 0) { // 只有读者全部没有了，才需要唤醒okToWrite.signal();}lock.Release();}

// WriterPublic Database::Write() {// Wait until no readers/writers;StartWrite();write database;// check out - wake up waiting readers/writers;DoneWrite();}Private Database::StartWrite(){lock.Acquire();while ((AW + AR) > 0) {WW++;okToWrite.wait(&lock);WW--;}AW++;lock.Release();}Private Database::DoneWrite() {lock.Acquire();AW--;if (WW > 0) {okToWrite.signal();}else if (WR > 0) {okToRead.broadcast(); // 唤醒所有reader }lock.Release();}

哲学家就餐问题

多线程面试题——哲学家就餐问题（Java）

• 共享数据

  ➢ Bowl of rice（data set）

  ➢ Semaphone fork[5] initialized to 1

• 直观的思考

  

  对于1个哲学家没问题，但如果5个人同时拿起左边叉子，大家都准备拿起右边叉子时，出现死锁。

• 稍改进后的方案

  

  问题在于，可能循环：大家同时拿起左边叉子，又同时放下，如此循环。

• 等待时间随机变化的方案

  

  由于时间随机，存在很多不确定性，并不完美。

• 简单的互斥访问方案

  

  虽然解决了死锁问题，但还是存在缺点：

  ➢ 它把就餐（而不是叉子）看成是必须互斥访问的临界资源，因此会造成（叉子）资源的浪费；

  ➢ 从理论上说，如果有 $5$ 把叉子，应允许 $2$ 个不相邻的哲学家同时就餐。

• 正确的解决方案

  ➢ 思路1：哲学家自己怎么来解决这个问题？

  ​ √ 指导原则：要么不拿，要么就拿两把叉子。

  

  ➢ 思路2：计算机怎么解决这个问题？

  ​ √ 指导原则：不能浪费CPU时间；进程间相互通信。

  

  ➢ 思路3：怎么样来编写程序？

  ① 必须有数据结构，来描述每个哲学家当前状态；

  ② 该状态是一个临界资源，对它的访问应该互斥地进行；

  ③ 一个哲学家吃饱后，可能要唤醒邻居，存在同步关系。

  // 1.必须有一个数据结构，来描述每个哲学家的当前状态；#define N 5   // 哲学家个数#define LEFT i// 第i个哲学家的左邻居#define RIGHT (i + 1) % N   // 第i个哲学家的右邻居#define THINKING 0// 思考状态#define HUNGRY   1 // 饥饿状态#define EATING   2 // 进餐状态int state[N];// 记录每个人的状态// 2.该状态是一个临界资源，对它的访问应该互斥地进行semaphore mutex;// 互斥信号量，初值1// 3.一个哲学家吃饱后，可能要唤醒邻居，存在着同步关系semaphore s[N];// 同步信号量，初值0// 函数philosopher的定义void philosopher(int i) // i的取值：0~N-1{    while (TRUE) // 封闭式循环    { think();// S1：思考中... take_forks(i);// S2-S4：拿到两把叉子或被阻塞 eat();// S5：吃面条中... put_forks(i);// S6-S7：把两把叉子放回原处    }}// 函数take_forks的定义// 功能：要么拿到两把叉子，要么被阻塞起来。void take_forks(int i)// i的取值：0到N-1{P(mutex);// 进入临界区state[i] = HUNGRY;// 我饿了！test_take_left_right_forks(i);// 试图拿两把叉子V(mutex);// 退出临界区P(s[i]);// 没有叉子便阻塞}// 函数test_take_left_right_forks的定义void test_take_left_right_forks(int i)// i取0到N-1{if (state[i] == HUNGRY &&// i：我自己，or其他人state[LEFT] != EATING &&state[RIGHT] != EATING){state[i] = EATING;// 两把叉子到手V(s[i]);// 通知第i人可以吃饭了（通知自己）}}// 函数put_forks的定义// 功能：把两把叉子放回原处，并在需要的时候唤醒左右邻居。void put_forks(int i)// i的取值：0到N-1{P(mutex);// 进入临界区state[i] = THINKING;// 交出两把叉子test_take_left_right_forks(LEFT);// 看左邻居能否进餐test_take_left_right_forks(RIGHT);// 看右邻居能否进餐V(mutex);// 退出临界区}

  think()，eat()是否需要进一步实现？如需要？如何实现？

  eat()不需要进一步实现，eat()对应的就是临界区。

  think()需要把初始时的state置为THINKING，且需要pv操作。

• 总结

  很多同步互斥问题都有难度，在本次课程的两个实现中，我们的方法流程如下：

  ① 一般人怎么解决这个问题，写出伪代码；

  ② 伪代码化为程序流程；

  ③ 设定状态变量，保证互斥或同步，使用信号量和管程等哪种手段；

  ④ 逐步细化方式，完成整个处理过程。一般来讲，申请资源、释放资源都是匹配的。

整理自 【清华大学】 操作系统