一些比较经典的, 书上的进程同步问题。
总结的解题思路:
- 画图理解题目
- 判断题目类型
- 分析进程数目, 填写进程模板
- 补充基本代码
- 补充 PV 代码
- 检查调整代码
不同线程之间的同步问题
由于不同线程之间存在异步性, 两个线程的语句执行先后顺序无法确定. 使用信号量机制来实现不同线程之间的同步问题
以此为延申, 如何实现拓扑排序
注意在线程同步中信号量初值为 0, 但是在线程互斥中信号量初值为 1
生产者-消费者问题
分析
共享变量为缓存池里面的产品数 缓冲区满, 生产者必须等待. 缓冲区空, 消费者必须等待 因为缓冲区的数量是临界资源, 只使用一个互斥变量来实现线程互斥如何?
semaphore n = 5;
semaphore mutex=1;
producer (){
do{
wait(mutex);
signal(n);
// produce
signal(mutex);
}while(true);
}
consumer(){
do{
wait(mutex);
wait(n);
// consume
signal(mutex);
}while(true);
}
这个代码存在很严重的问题. 假设只有一个 consumer 进程先启动, 他顺利执行到 consume 操作. 但是此时的缓冲区中还没有商品. 我们对此进行分析一下.
- 如果缓冲区满,生产者是不能生产的,所以生产者进程受到消费者进程的制约;
- 如果缓冲区空,消费者是不能消费的,所以消费者进程受到生产者进程的制约。
所以 P/C 问题不仅仅是线程互斥, 还包含了线程同步, 线程同步仅仅使用一个信号量是不够的. 因此我们需要额外设置两个信号量来实现线程的同步问题. 生产者在乎的是剩余空间 empty. 消费者在乎的是占用空间 full. 生产者在生产商品之前应该 P(empty) , 消费者在消费商品之前应该 P(full).
semaphore mutex = 1;
semaphore empty = n;
semaphore full = 0;
producer(){
do{
wait(empty); // P消耗一个空闲缓冲区
wait(mutex);
// produce
signal(mutex);
signal(full); // V增加一个产品
}while(true);
}
consumer(){
do{
wait(full); // P消耗一个产品, 非缓冲区
wait(mutex);
// consume
signal(mutex);
signal(empty); // V增加一个空闲缓冲区
}while(true);
}
是否可以交换 producer 或者 consumer 中的两个 P 操作呢? 我们交换 producer 里面的两个 P 操作
// producer
wait(mutex);
wait(empty); // P消耗一个空闲缓冲区
假设此时缓冲区为满, empty = 0, full=n; producer 执行 P(mutex), mutex 变为 0, 执行 P(empty), 这个时候会被阻塞. 现在切换回 consumer 进程, 执行 wait(full) 没有问题, 执行 wait(mutex) 会被阻塞. 这样就会出现线程死锁. 因此实现互斥的 P 操作要在实现 同步的 P 操作之后执行 但是 V 操作的执行顺序不会导致线程.
套路
- 分析题目题型: 容器大小固定, 为 P/C 问题
- 分析进程数量: 不同个体对应不同的进程
- 分析每个进程关心的: 消费者只关心 占用空间, 生产者只关心 剩余空间
- 填写进程基本操作
- 补充 PV 代码
哲学家进餐问题
2019 王道考研 操作系统 哔哩哔哩 (゜-゜)つロ 干杯~-bilibili
分析
临界资源: 筷子 对哲学家进行编号, 第 i 位哲学家的活动可以描述为
semaphore chopstick[5]={1,1,1,1,1}; // 筷子的信号量
Pi(){
do{
wait(chopstick[i]);
wait(chopstick[(i+1)%5]); // 对左右筷子互斥访问
////
//eat
////
signal(chopstick[i]);
signal(chopstick[(i+1)%5]); // 释放
////
//think
////
}while(true);
}
但是这样会导致一个问题, 哲学家们可能会同时拿起左边的筷子, 在去拿右边的筷子时会发生阻塞 解决方案
- 最多允许四个哲学家同时拿左边的筷子
- 只有当哲学家左右两边的筷子均可以使用时才允许拿筷子
- 奇数哲学家先拿左边, 再拿右边的筷子. 偶数哲学家相反
方案 1
semaphore chopstick[5]={1,1,1,1,1}; // 筷子的信号量
semaphore r=4; // 只允许4个哲学家进餐
Pi(){
do{
wait(r);
wait(chopstick[i]);
wait(chopstick[(i+1)%5]);
//eat
signal(chopstick[(i+1)%5]);
signal(chopstick[i]);
signal(r);
}while(true);
}
获得信号量 r 的哲学家最多只有 4 个 最少有一个哲学家可以 eat, 使用完之后释放两只筷子, 不会出现死锁和饿死
方案 2
semaphore chopstick[5]={1,1,1,1,1}; // 筷子的信号量
semaphore mutex=1; // 互斥访问变量
Pi(){
do{
wait(mutex);
wait(chopstick[i]);
wait(chopstick[(i+1)%5]); //*
signal(mutex);
// eat
signal(chopstick);
signal(chopstick[(i+1)%5]);
// think
}while(true);
}
使用一个互斥变量实现线程同步, 但是, 这其实也不是一个完美的方案 假如一个哲学家 x 拿起了左右两边的筷子, 他右边的哲学家 y 拿起了他左边的筷子, 想去拿右边的筷子时会发生阻塞, 阻塞在 * 位置. 这个情况下只能等 x 放下了 x 左边的筷子, y 才能继续进行. 不过比较好的是, 这个方案并不会产生死锁的问题
方案 3
semaphore chopstick[5]={1,1,1,1,1};
Pi(){
while(1){
if(i%2!=0){//奇数号哲学家
wait(chopstick[i]);//拿左边的
wait(chopstick[(i+1)%5]);//右边的
}else{//偶数号哲学家
wait(chopstick[(i+1)%5]);//右边的
wait(chopstick[i]);//左边的
}
// eat
signal(chopstick[i]);//释放筷子资源
signal(chopstick[(i+1)%5]);
}
}
读者-写者问题
要求:
- 可以多个读者同时读
- 但是不允许多个写者同时写, 只允许一个写者写
- 不允许在写的时候读, 也不能有新的写者来写
- 写者执行写之前, 不应该有读者或写者在操作
共享数据是文件
分析
两类进程: 读, 写者进程 互斥关系: 1. 读进程-写进程 2. 写进程-写进程
写进程与其他进程都互斥. 首先, 写进程与写进程之间 需要一个信号量 rw, 在写者操作共享文件前后加上 PV 操作 其次, 读进程与写进程也互斥, 因此也需要 PV 操作. 但是如果一个读者在读取共享文件之前进行了 P(rw) 操作, 会导致其他读者无法读取. 怎么解决?
使用一个 count 变量来解决, 记录当前有多少读进程.
假设刚开始 count = 0 , 进行 P(rw) 保证不会有写进程参与进来, 之后 count++, 说明现在有一个读进程.
此时有另外一个读进程参与进来, 由于 count!=0, 那么他就不会进行 P(rw) 操作, 而是直接 count++. 这样我们就解决了读者进程之间的非互斥执行问题
semaphore rw=1; // 对文件的互斥访问
int count = 0; // 记录当前读进程数
reader(){
do{
if(count==0) // 如果当前没有读者
wait(rw);
count++;
// read file
count--;
if(count==0) // 如果当前没有读者
signal(rw);
}while(true);
}
writer(){
do{
wait(rw);
// write file
signal(rw);
}while(true);
}
还存在一个问题 , count 变量是共享变量, 设想这样一种情况, count=0 时, 读者 1 if 判断执行, 刚要执行 P(rw) 时, count 现在还是 0, 与此同时另外一位读者也通过了 if 判断. 那么, 在读者一获得了 rw 权限之后, 读者 2 就会被阻塞. 还需要一个互斥变量来保证一气呵成地操作 count 变量
semaphore rw=1; // 对文件的互斥访问
int count = 0; // 记录当前读进程数
semaphore mutex = 1; // 对count 变量的互斥访问
reader(){
do{
wait(mutex);
if(count==0) // 如果当前没有读者
wait(rw);
count++;
signal(mutex);
// read file
wait(mutex);
count--;
if(count==0) // 如果当前没有读者
signal(rw);
signal(mutex);
}while(true);
}
writer(){
do{
wait(rw);
// write file
signal(rw);
}while(true);
}
套路
写者关心文件是否被占用. 读者团:
- 第一个读者关心文件是否被占有, 未被占有就占用.
- 中间读者只增加读者团人数.
- 最后一个读者释放文件.
设置一个信号量表示资源是否被占有, 使用另外一个信号量表示读者团中读者的数量.
特征: 资源占用, 团体性