多线程与并发
多线程思想。内含临界区,信号量,死锁以及读者写者问题。
多线程与并发
临界区
多个进程在访问共享数据的时候,为防止对资源的竞争,我们提出临界区的概念。
临界区这一概念满足,对于任意的两个进程,不能同时进入临界区,即达到一种进程间“互斥”的效果。
具体来说,临界区的设计需要满足:(摘自讲义)
任何两个进程不能同时处于临界区
对 CPU 的速度和数量没有要求
临界区外运行的进程不能阻塞到其他进程
不能让一个进程无限期等待进入临界区
需要被舍弃的做法
锁变量
int lock;
void Process1()
{
while (lock == 1); // (2)
lock = 1; // (5)
// 临界区 // (5)
lock = 0;
// 非临界区
}
void Process2()
{
while (lock == 1); // (3)
lock = 1; // (4)
// 临界区 // (5)
lock = 0; // (1)
// 非临界区
}
错误原因:
Process1
在 lock == 1
判断为False后的瞬间,进行了进程调度;
而此时Process2
从(1)处继续运行,跨过非临界区,判断 lock==1
为 False 后,进入了临界区;
而此时再发生一次进程调度,Process1
也进入了临界区。
严格轮换法
int turn = 0;
void Process1()
{
while (turn == 0);
// 临界区
turn = 0;
// 非临界区
}
void Process2()
{
while (turn == 1);
// 临界区
turn = 1;
// 非临界区
}
舍弃原因:
(1) 自旋锁(用于忙等待的锁),过于浪费资源
(2) 优先级翻转问题:当某个进程的优先级高…
休眠与唤醒
int cnt = 0;
void Process1()
{
while (1)
{
if (cnt == 1) sleep();
// 临界区
cnt = 1;
wakeup(Process2);
// 非临界区
}
}
void Process2()
{
while (1)
{
if(cnt == 0) sleep();
cnt = 0;
wakeup(1);
}
}
存在的问题:
Process1
判断cnt==1
时进入条件结构体,此时发生了一次进程调度;
Process2
此时将cnt
置为0,并且尝试唤醒Process1
,而Process1
此时还没有休眠.
然后Process2
判断cnt==0
为True,进入休眠.
此时再发生一次进程调度,Process1
也进入休眠,
信号量
上述做法均存在一定的问题,而能够解决这个临界区问题的一个很好的概念便是Dijkstra提出的信号量
.
信号量(Semaphore),有时被称为信号灯,是在多线程环境下使用的一种设施,是可以用来保证两个或多个关键代码段不被并发调用。在进入一个关键代码段之前,线程必须获取一个信号量;一旦该关键代码段完成了,那么该线程必须释放信号量。
计数讯号量具备两种操作动作,称为V(signal()
)与P(wait()
)(即部分参考书常称的“PV操作”)。V操作会增加信号标S的数值,P操作会减少它。
计数讯号量具备两种操作动作,称为V(signal())与P(wait())(即部分参考书常称的“PV操作”)。V操作会增加信号标S的数值,P操作会减少它。
运作方式:
- 初始化,给与它一个非负数的整数值。
- 执行P(wait()),信号标S的值将被减少。企图进入临界区段的行程,需要先执行P(wait())。当信号标S减为负值时,行程会被挡住,不能继续;当信号标S不为负值时,行程可以获准进入临界区段。
- 执行V(signal()),信号标S的值会被增加。结束离开临界区段的行程,将会执行V(signal())。当信号标S不为负值时,先前被挡住的其他行程,将可获准进入临界区段。
int sem = 1;
void Process1()
{
while (1)
{
P(sem);
// 临界区
V(sem);
}
}
void Process2()
{
while (1)
{
P(sem);
// 临界区
V(sem);
}
}
互斥量
我们的sem变量满足以下要求:
信号量的初始值是 1,且 P、V 操作在一个线程中成对出现,先有 P,后有 V,两个操作之间是互斥的临界区。
这意味着同时只能有一个进程进入两个 P、V 操作之间。
因此我们对这种特殊的情况进行单独处理,对信号量进行简化,得到“互斥量(mutex)”。
一个互斥量包含两个操作:加锁(lock,对应于 P 操作)和解锁(unlock,对应于 V 操作)。
条件变量
条件变量(condition variable)是与互斥量配合使用的。在互斥量已经加锁的条件下,条件变量的基本操作有三个:
死锁产生的条件:
互斥条件:资源要么分配给了某个进程,要么就是可用的
占有和等待条件:已经得到了某个资源的进程可以再请求新的资源(即一层锁不会导致死锁)
不可抢占条件:已经分配给一个进程的资源不能强制抢占,只能由占有它的进程自己释放
环路等待条件:死锁发生时,进程一定可以形成一个环路,环路中每一个进程都等待着下一个进程占有的资源
经典例子:DiningPhilosophers
https://leetcode-cn.com/problems/the-dining-philosophers/
5 个沉默寡言的哲学家围坐在圆桌前,每人面前一盘意面。叉子放在哲学家之间的桌面上。(5 个哲学家,5 根叉子)
所有的哲学家都只会在思考和进餐两种行为间交替。哲学家只有同时拿到左边和右边的叉子才能吃到面,而同一根叉子在同一时间只能被一个哲学家使用。每个哲学家吃完面后都需要把叉子放回桌面以供其他哲学家吃面。只要条件允许,哲学家可以拿起左边或者右边的叉子,但在没有同时拿到左右叉子时不能进食。
假设面的数量没有限制,哲学家也能随便吃,不需要考虑吃不吃得下。
设计一个进餐规则(并行算法)使得每个哲学家都不会挨饿;也就是说,在没有人知道别人什么时候想吃东西或思考的情况下,每个哲学家都可以在吃饭和思考之间一直交替下去。
哲学家从 0 到 4 按 顺时针 编号。请实现函数 void wantsToEat(philosopher, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork);
philosopher 哲学家的编号。
pickLeftFork 和 pickRightFork 表示拿起左边或右边的叉子。
eat 表示吃面。
putLeftFork 和 putRightFork 表示放下左边或右边的叉子。
由于哲学家不是在吃面就是在想着啥时候吃面,所以思考这个方法没有对应的回调。
给你 5 个线程,每个都代表一个哲学家,请你使用类的同一个对象来模拟这个过程。在最后一次调用结束之前,可能会为同一个哲学家多次调用该函数。
解题思路:
- 使用C++ std::lock实现多锁原子锁定
class DiningPhilosophers {
private:
std::mutex mutexs[5];
public:
DiningPhilosophers() {
}
void wantsToEat(int philosopher,
function<void()> pickLeftFork,
function<void()> pickRightFork,
function<void()> eat,
function<void()> putLeftFork,
function<void()> putRightFork) {
int lhs = philosopher;
int rhs = (philosopher+1)%5;
std::lock(mutexs[lhs], mutexs[rhs]);
std::lock_guard<std::mutex> lock_a(mutexs[lhs], std::adopt_lock);
std::lock_guard<std::mutex> lock_b(mutexs[rhs], std::adopt_lock);
pickLeftFork();
pickRightFork();
eat();
putLeftFork();
putRightFork(); //在临界区内,其实左边右边顺序无关紧要
}
};
- 随意指定一个人和其他人拿筷子的顺序不一样,这样也可以破坏闭环结构。
class DiningPhilosophers { private: std::mutex forks[5]; public: DiningPhilosophers() { } void wantsToEat(int philosopher, function<void()> pickLeftFork, function<void()> pickRightFork, function<void()> eat, function<void()> putLeftFork, function<void()> putRightFork) { if(philosopher == 0){ forks[0].lock(); forks[4].lock(); pickLeftFork(); pickRightFork(); eat(); putRightFork(); putLeftFork(); forks[4].unlock(); forks[0].unlock(); return; } forks[philosopher-1].lock(); forks[philosopher].lock(); pickLeftFork(); pickRightFork(); eat(); putRightFork(); putLeftFork(); forks[philosopher].unlock(); forks[philosopher-1].unlock(); } };
读者写者问题
一个资源,我们可以需要对它进行读写。
读操作是不对资源进行更改的,而写操作对资源进行更改。
这对我们提出了要求:可以多个进程同时读,但是读的过程中不允许写;只能有一个进程对它写入,写的过程不允许任何其他进程同时写或读。
即我们要求:
- 允许多个读者可同时对文件执行读操作
- 只允许一个写者往文件中写信息
- 任一写者在完成写操作之前不允许其他读者或写者工作
- 写者执行写操作前,应让已有的写者和读者全部退出
读者优先的操作模式
semaphore rmutex = 1; // 读进程互斥信号量
semaphore wmutex = 1; // 写进程互斥信号量
int readcount = 0; // 读进程计数
process reader_i() { // 读进程
while(true) {
P(rmutex);
readcount++;
if(readcount == 1)
P(wmutex);
V(rmutex);
{读文件};
P(rmutex);
readcount--;
if(readcount == 0)
V(wmutex);
V(rmutex);
}
}
process writer_i() { // 写进程
while(true) {
P(wmutex);
{写文件};
V(wmutex);
}
}
要点:读者优先,读者可以抢占写者的资源。
参考链接:https://liuwynn.github.io/2018/11/28/%E8%AF%BB%E8%80%85-%E5%86%99%E8%80%85%E9%97%AE%E9%A2%98/