【操作系统】第十章——信号量与管程

• 采用的是基于硬件支持的原子操作来完成进程互斥与同步
  

1、什么是信号量

为了使临界区中可以有多个线程&＃xff0c;引入信号量来实现这种机制

2、如何实现信号量

• 信号量是一种抽象的数据类型&＃xff1a;包含一个整形数sem&＃xff0c;以及对应的两个操作

P( ): sem 减一&＃xff0c;如果sem <0,则等待&＃xff0c;反之则继续执行【类似于加锁】

V( ):sem 加一&＃xff0c;如果sem <&＃61; 0&＃xff0c;唤醒一个等待的P【类似于解锁】

• 案例分析&＃xff1a;铁路信号灯&＃xff0c;允许两辆火车在指定路段

3、信号量的使用&＃xff1a;

• 信号量用一个有符号数表示
• 如果只能唤醒一个进程&＃xff0c;我们一般采取FIFO的形式&＃xff0c;先来先唤醒【公平】
• 信号量是被保护的变量&＃xff0c;只能由两个原子操作P、V来修改它的值【P减一阻塞、V加一恢复】
• 信号量一般分为两类&＃xff1a;

&＃xff08;1&＃xff09;二进制信号量&＃xff1a;取值为0或1【适用于一个进程访问临界区】

&＃xff08;2&＃xff09;一般/计数信号量&＃xff1a;取值为非负值【适用于临界区里面有多个进程】

• 信号量的这两种类型也说明了一个事情&＃xff1a;

信号量不仅可以实现进程/线程的互斥&＃xff0c;同时可以实现他们的同步功能

4、通过一个案例来说明信号量如何解决问题&＃xff1a;

&＃xff08;1&＃xff09;案例一&＃xff1a;利用二进制信号量实现互斥

//初始化信号量[mutex代表互斥锁]
mutex &＃61; new Semaphore(1);
//P操作
mutex -> P();
//临界区代码
Critical Section;
//V操作
mutex -> V();


&＃xff08;2&＃xff09;案例二&＃xff1a;利用二进制信号量实现同步【当一个进程/线程执行到某一位置才能轮到另一个进程/线程执行】

信号量初值为0&＃xff0c;所以当线程A执行到P操作的时候就会被挂起&＃xff0c;直至线程B执行完V操作&＃xff0c;线程A才能执行剩余的部分

&＃xff08;3&＃xff09;案例三&＃xff1a;利用计数信号量实现生产者与消费者【包含同步与互斥】

• 一个或多个生产者产生数据&＃xff0c;将数据放在缓冲区中
• 单个消费者每次从缓冲区取出数据
• 在任何一个时间只有一个生产者或消费者可以访问缓冲区【一个线程等待另一个线程处理事情】

• 正确性要求&＃xff1a;【对同步和互斥的一些约束】

&＃xff08;1&＃xff09;在任何一个时间只能有一个线程操作缓冲区&＃xff08;互斥&＃xff09;

&＃xff08;2&＃xff09;当缓冲区为空&＃xff0c;消费者必须等待生产者&＃xff08;同步约束&＃xff09;

&＃xff08;3&＃xff09;当缓存区满时&＃xff0c;生产者必须等待消费者&＃xff08;同步约束&＃xff09;

• 那么我们应该如何设置生产者与消费者的信号量&＃xff1f;

我们知道实现临界区互斥需要一个二进制信号量&＃xff0c;又因为分为缓冲区和缓存区&＃xff08;一个记录是否有产品、一个记录是否有空间&＃xff09;&＃xff0c;所以还需要两个信号量

&＃xff08;1&＃xff09;二进制信号量实现互斥

&＃xff08;2&＃xff09;计数信号量 fullBuffers 对应剩余产品的个数

&＃xff08;2&＃xff09;计数信号量 **emptyBuffers **对应剩余空间大小【这两个计数信号量是互补的】

• 代码实现&＃xff1a;【为了看起来更直观、方便对比&＃xff0c;用图片来表示】

• 代码分析&＃xff1a;

&＃xff08;1&＃xff09;Class BoundedBuffer类实现信号量初始化&＃xff1a;

互斥信号量初始为1&＃xff0c;当第一个线程访问缓冲区时其他线程就要等待&＃xff1b;

fullBudders 信号量初始为 0&＃xff0c;代表空间内还没有产品&＃xff1b;

emptyBuffers 信号量初始为 n&＃xff0c;代表空间的大小为 n&＃xff0c;此时剩余的空间也为 n

&＃xff08;2&＃xff09;BoundeBuffer::Deposit(c)代表生产者线程&＃xff1a;

减少一个空间 >> 临界区加锁 >> 生产产品 >> 临界区解锁 >> 产品个数增加

&＃xff08;3&＃xff09;BoundedBuffer::Remove(c)代表消费者线程&＃xff1a;

产品个数减少 >> 临界区加锁 >> 消耗产品 >> 临界区解锁 >> 增加一个空间

• 如果交换信号量操作的顺序是否会产生影响&＃xff1a;【相邻的操作】

&＃xff08;1&＃xff09;V操作交换顺序没有问题&＃xff0c;因为只是起到通知的作用【例如&＃xff1a;消费者的末尾两次V操作】

&＃xff08;2&＃xff09;但是V操作交换顺序可能会出现问题&＃xff0c;此处以生产者开头两次V操作为例

当没有剩余空间时&＃xff0c;生产者执行 mutex -> P()导致消费者无法访问临界区&＃xff0c;接着执行emptyBuffers -> P(),因为此时已经没有空间了&＃xff0c;执行完该操作生产者处于挂起状态&＃xff0c;消费者也无法执行。

所以就导致出现了死锁现象。

5、在操作系统中&＃xff0c;这个等究竟是怎么实现的呢&＃xff1f;【信号量实现细节】

• 首先&＃xff0c;需要一个整型变量记录加减的一个值
• 如果产生等操作&＃xff0c;就将这个线程或进程添加到等待队列中&＃xff0c;也就涉及两个操作

&＃xff08;1&＃xff09;P操作去执行等

执行P操作&＃xff0c;信号量sem减一 >> 如果信号量现在小于零&＃xff0c;说明有进程在访问临界区&＃xff0c;需要将当前进程添加到等待队列 >> 通过block让进程睡眠

&＃xff08;2&＃xff09;V操作不再等

执行V操作&＃xff0c;信号量sem加一 >> 如果信号量现在还会小于等于零&＃xff0c;说明等待队列中有进程&＃xff0c;我们就根据调度算法取出一个进程 >> 再将其唤醒

• 信号量机制既有好处、也有缺点&＃xff1a;

&＃xff08;1&＃xff09;通过信号量机制&＃xff0c;我们实现了互斥与同步

&＃xff08;2&＃xff09;但是不容易读代码&＃xff0c;而且如果PV操作循序不当可能会出现错误&＃xff0c;甚至死锁

&＃xff08;3&＃xff09;接下来我们引入管程的概念

6、什么是管程&＃xff1f;

• 是包含一系列共享变量以及对这些共享变量的操作函数的模块或组合
• 需要对临界区的锁
• 需要0或多个条件变量
• 管程与信号量的层次是不同的&＃xff1a;信号量面向操作系统、管程面向编程语言

7、使用管程的大致流程&＃xff1a;

• 形成了一个等待队列&＃xff0c;当获得锁之后就可以进入管程中
• 流程概述&＃xff1a;

进程获得锁进入临界区&＃xff0c;访问共享数据&＃xff0c;里面设置了一些条件变量&＃xff0c;通过wait和signal函数实现互斥与同步&＃xff0c;执行到某一位置释放锁&＃xff0c;后续进程可以获得锁

• 重点在于锁和条件变量的实现&＃xff1a;

&＃xff08;1&＃xff09;Lock锁的实现&＃xff1a;【与信号量那块类似】

Lock::Acquire() - 等待直到锁可用&＃xff0c;然后抢占锁

Lock::Release() - 释放锁&＃xff0c;唤醒等待着【如果存在等待着&＃xff0c;否则不进行操作】

&＃xff08;2&＃xff09;条件变量的实现&＃xff1a;【主要涉及两个操作&＃xff1a;】

Wait() 释放锁&＃xff0c;进程睡眠&＃xff0c;在重新获得锁后返回

Singal() 如果存在等待着&＃xff0c;则唤醒等待着

• 具体的代码实现&＃xff1a;
  

&＃xff08;1&＃xff09;Class Condition初始化条件变量&＃xff1a;numWaiting 处于等待的线程个数&＃xff0c;q 代表等待队列

&＃xff08;2&＃xff09;Wait操作&＃xff1a;增加等待线程的个数&＃xff0c;将当前线程添加到等待队列中&＃xff0c;释放锁 >> 获得锁

&＃xff08;3&＃xff09;Singal操作&＃xff1a;如果等待队列中存在线程&＃xff0c;就将该线程从队列汇总取出&＃xff0c;唤醒&＃xff0c;更新等待队列中元素的个数&＃xff0c;否则步进行任何处理

8、利用管程解决生产者与消费者问题&＃xff1a;

count 代表产品个数&＃xff0c;notFull 代表剩余空间&＃xff0c;notEmpty 代表产品个数【这样好理解】

在这里同时说明了一件事情&＃xff1a;Wait 操作为什么先释放锁后获得锁&＃xff1f;

wait操作是为了让当前线程去睡眠&＃xff0c;由于管程为了实现互斥只允许一个进程访问&＃xff0c;如果那个线程睡眠了&＃xff0c;但是没有释放锁&＃xff0c;则其他线程会一直处于等待状态

9、当执行Singal操作之后&＃xff0c;是否立刻去执行唤醒的线程&＃xff1f;

汉森和霍尔分别给出了自己的方案&＃xff1a;

&＃xff08;1&＃xff09;汉森的方案

当前线程执行 signal 后&＃xff0c;不会立刻执行唤醒的线程&＃xff0c;只有当前线程 release&＃xff08;释放&＃xff09;之后才会去选择一个唤醒的线程去执行&＃xff0c;操作简单

&＃xff08;2&＃xff09;霍尔的方案

当前线程执行 signal 后&＃xff0c;就会进入到睡眠状态&＃xff0c;立刻执行一个唤醒的线程&＃xff0c;只有当这个新线程release之后&＃xff0c;原线程才会继续执行 signal&＃xff0c;操作复杂。

9、总结图示&＃xff1a;

$ 读者写者问题

&＃x1f499; 1、什么是读者写者问题&＃xff1f;

• 有一个共享数据&＃xff0c;有读操作和写操作去访问这个数据
• 读者 >> 不修改数据、写着 >> 读取并修改数据
• 根据读者写者操作的不同&＃xff0c;需要满足以下几点要求&＃xff1a;

&＃xff08;1&＃xff09;读写互斥、写写互斥、读读共享

&＃xff08;2&＃xff09;在任何时间只允许一个线程操作共享变量

• 读者优先&＃xff1a;如果当前有读线程在执行&＃xff0c;有一个写线程在等待&＃xff0c;新来的读线程会跳过这个写线程先执行
• 共享数据包括以下几部分&＃xff1a;数据集、信号量CountMutex、WriteMutex、整数Rcount

&＃x1f499; 2、如何利用信号量实现读者写者问题&＃xff1f;【读者优先】

&＃xff08;1&＃xff09;无论是读线程还是写线程&＃xff0c;都与写线程互斥&＃xff0c;所以执行读、写操作时都会先判断是否有写线程在访问数据

&＃xff08;2&＃xff09;因为读写是互斥的&＃xff0c;在读者线程到来的时候先判断是否存在写线程&＃xff0c;如果不存在就要去判断是否存在写线程。

可以正常执行就将读线程的个数加一&＃xff0c;执行完读操作之后就会将读线程的个数减一&＃xff0c;如果此时读线程的个数已经变为零了&＃xff0c;那么就把访问数据的权限交给写线程

&＃xff08;3&＃xff09;对于读者线程之间&＃xff0c;读线程个数Count信号量是共享的&＃xff0c;所以在修改它的时候应该是互斥的&＃xff0c;通过CountMutex信号量完成互斥

&＃x1f499; 3、什么是读者优先、什么是写者优先&＃xff1f;

• 基于读者优先策略的方法&＃xff0c;只要有一个读者处于活动状态&＃xff0c;后来 的读者都会被接纳。如果读者源源不断地出现的话&＃xff0c;那么写者就 始终处于阻塞状态。
• 基于写者优先策略的方法&＃xff1a;一旦写者就绪&＃xff0c;那么写者会尽可能快地 执行写操作。如果写者源源不断地出现的话&＃xff0c;那么读者就始终处于 阻塞状态。

&＃x1f499; 4、如何利用管程实现读者写者问题&＃xff1f;【写者优先】

&＃xff08;1&＃xff09;先用伪代码说明读、写两个方法&＃xff1a;

• Read操作&＃xff1a;

  因为是读者优先&＃xff0c;所以先要等到等待队列中没有写线程之后&＃xff0c;才能去执行读线程

  读取数据

  当执行完全部读线程之后&＃xff0c;判断等待队列中是否有新产生的写线程&＃xff0c;如果有则当前读进程负责唤醒写线程

• Write操作&＃xff1a;

  需要先判断是否有正在执行的读线程或写线程&＃xff0c;管程处于空闲才能获得锁&＃xff0c;去执行当前的写进线程

  写数据

  当执行完本次写线程之后&＃xff0c;先判断是否有等待的写线程&＃xff0c;如果有则先唤醒写线程&＃xff0c;没有则唤醒全部的读线程

&＃xff08;2&＃xff09;定义需要的变量

Lock lock 【锁】

AR >> 正在执行的读线程、WR >> 正在执行的写线程

WR >> 等待队列中读线程的个数、WW >> 等待队列中写线程的个数

Condition okToRead >> 已经准备好执行读操作、Condition okToWrite >> 已经准备好执行写操作

&＃xff08;3&＃xff09;具体的代码实现&＃xff1a;

• 我们需要考虑两个方面&＃xff1a;等这个状态如何实现、以及执行完相关的操作后&＃xff0c;如果进行接下来的处理
• Read操作&＃xff1a;

读操作分为三个部分&＃xff1a;StartRead、read database、DoneRead

StartRead:

先判断是否有正在执行或处于等待队列中的写线程 >> 有&＃xff0c;则将等待的读线程个数加一并阻塞&＃xff0c;阻塞结束后WR减一&＃xff0c;没有则将执行的读线程个数加一。【因为管程只允许一个函数进入&＃xff0c;所以对于Start和Done内部开始要加上锁实现互斥】

read database: 读取数据

DoneRead:

执行完读线程之后&＃xff0c;先将执行的读线程个数减一 >> 判断是否已经没有正在执行的读线程了&＃xff0c;如果有则不进行处理&＃xff0c;如果没有就去考虑是否存在处于等待状态的写线程&＃xff0c;如果有就唤醒一个等待的写线程&＃xff0c;否则不进行处理

• Write操作&＃xff1a;

同样也是分为 StartWrite、write database、DoneWrite 三部分

StartWrite:

先判断是否有正在执行的线程&＃xff0c;如果有则更新等待的写线程个数并阻塞当前线程&＃xff0c;被唤醒之后更新WW&＃xff0c;并执行当前线程&＃xff1b;

如果没有&＃xff0c;就更新正在执行的写线程个数&＃xff0c;去执行当前的写线程

**write database: **修改数据

DoneWrite:

恢复正在执行的写线程个数&＃xff0c;如果存在等待的写线程&＃xff0c;就去唤醒一个等待的写线程&＃xff1b;否则唤醒全部的读线程。

signal 唤醒一个、broadcase 唤醒全部

$ 哲学家就餐问题

&＃x1f4d6; 1、什么是哲学家就餐问题&＃xff1f;

• 涉及的共享变量&＃xff1a;

  fork[5] 初始化为1&＃xff0c;代表五个叉子

  take_fork(i) 代表第i个哲学家去拿叉子

  put_fork(i) 代表第i个哲学家去放叉子

  访问临界资源互斥&＃xff0c;PV操作 P(fork[i])、V(fork[i])

book: 2、几种存在问题的实现方式&＃xff1a;

• 方案一&＃xff1a;如果五个哲学家同时去拿一侧的叉子&＃xff0c;就会陷入死锁的情况【既不愿意放弃现有资源&＃xff0c;又不能获得新资源继续执行】

#define N 5 //哲学家个数
void philosopher(int i) // i 代表哲学家的编号
while(TRUE){
think(); //哲学家思考
take_fork(i); //去拿左边的叉子
taek_fork((i &＃43; 1) % N); //去拿右边的叉子
eat(); //哲学家进餐
put_fork(i); //放下左边的叉子
put_fork((i &＃43; 1) % N); //放下右边的叉子
}


• 方案二&＃xff1a;等待时间是确定的&＃xff0c;只是重复的进行方案一的情况

#define N 5
void philosopher(int i)
while(1)
{
take_fork(i);
if(fork((i &＃43; 1) % N)){ //拿到左手的叉子之后&＃xff0c;判断右手的叉子是否还在
take_fork((i &＃43; 1) % N); //右侧叉子还在就拿起
break;
}else{
put_fork(i); //右侧叉子不存在&＃xff0c;就放下左手的叉子
wait_some_time(); //等待一会儿再继续去执行
}
}


• 方案三&＃xff1a;可行&＃xff0c;但是等待时间是随机的&＃xff0c;可能会出现部分哲学家饥饿现象【某些哲学家已经食用了好几次了&＃xff0c;然而部分哲学家仍处于等待状态】

#define N 5 //哲学家个数
void philosopher(int i) // i 为哲学家编号
while(1) //去拿两把叉子
{
take_fork(i); //去拿左边的叉子
if(fork((i &＃43; 1) % N)){ //判断右侧叉子是否存在
take_fork((i &＃43; 1) % N); //去拿右边的叉子
break; //已经拿到两把叉子
}else{ //右边的叉子不存在
put_fork(i); //放下左边的叉子
wait_random_time(); //等待随机长时间
}
}


• 方案四&＃xff1a;对于整个进餐过程通过信号量互斥&＃xff0c;导致同一时刻只能允许一个哲学家进餐

semaphore mutex //互斥信号量。初始化为1
void philosopher(int i) //哲学家编号
while(TRUE){
think(); //哲学家在思考
P(mutex); //进入临界区
take_fork(i); //去拿左边的叉子
take_fork((i &＃43; 1) % N); //去拿右边的叉子
eat(); //哲学家进餐
put_fork(i); //放下左边的叉子
put_fork((i &＃43; 1) % N); //放下右边的叉子
V(mutex); //退出临界区
}


book: 3、通过哲学家分析&＃xff0c;什么时候应该去拿叉子&＃xff0c;什么时候不应该去拿叉子&＃xff1f;

• 原则&＃xff1a;要么不拿&＃xff0c;要么就拿两把叉子
• 整体流程如下&＃xff1a;

• 计算机如何去实现这个方案&＃xff1a;【要满足不能浪费CPU时间、进程间能相互通信】

• 编写程序需要定义那些变量或信号量&＃xff1f;

&＃xff08;1&＃xff09;需要有一个数据结构来描述哲学家们的当前状态

&＃xff08;2&＃xff09;哲学家的状态属于临界资源&＃xff0c;应该实现访问进程互斥

semaphore mutex; //互斥信号量&＃xff0c;初值1

&＃xff08;3&＃xff09;一个哲学家进餐结束后&＃xff0c;有义务去唤醒左右满足进餐条件的哲学家&＃xff0c;应该实现进程同步

semaphore s[N] //同步信号量&＃xff0c;初值0

book: 4、哲学家进餐问题代码实现&＃xff1a;【针对不同的功能封装成具体的一个函数】

&＃xff08;1&＃xff09;函数philosopher的定义【整个流程】

void philosopher(int i) //i代表哲学家编号
{
while(TRUE) //假设为一直进餐、思考、饥饿
{
think(); //思考中
take_forks(i); //拿到两把叉子或被阻塞
eat(); //进餐
put_forks(i); //把两把叉子放回原处
}
}


&＃xff08;2&＃xff09;函数take_forks的定义【要么拿到两把叉子&＃xff0c;要么阻塞】

void take_forks(int i)
{
P(mutex); //进入临界区
state[i] &＃61; HUNGRY; //第i个哲学家饿了
test_take_left_right_forks(i); //试图拿两把叉子
V(mutex); //退出临界区
P(s[i]); //没有叉子便阻塞
}


&＃xff08;3&＃xff09;函数test_take_left_right_forks的定义【具体去拿叉子的方法】

void test_take_left_right_forks(int i)
{
if(state[i] &＃61;&＃61; HUNGRY && state[LEFT] !&＃61; EATING && state[RIGHT] !&＃61; EATING) //自己饿了&＃xff0c;左右哲学家没在进餐状态
{
state[i] &＃61; EATING; //两把叉子到手
V(s[i]); //通过第i个哲学家进餐
}
}


&＃xff08;4&＃xff09;函数put_forks的定义【把两把叉子放回原处&＃xff0c;并在需要的时候唤醒左右的要想进食的哲学家】

void put_forks(int i)
{
state[i] &＃61; THINKING; //交出两把叉子
test_take_left_right_forks(LEFT); //查看左邻居能否进餐
test_take_left_right_forks(RIGHT); // 查看右邻居能否进餐
}


&＃xff08;5&＃xff09;函数think的定义【就是将哲学家的状态置为THINKING】

void think(int i){
P(mutex); //对于状态的访问是互斥的
state[i] &＃61; THINKING;
V(mutex);
}


&＃xff08;6&＃xff09;函数eat的定义【就是进餐这个动作&＃xff0c;没有什么需要完成的内部结构】