多线程思想。内含临界区,信号量,死锁以及读者写者问题。

1024px-An_illustration_of_the_dining_philosophers_problem

多线程与并发

临界区

多个进程在访问共享数据的时候,为防止对资源的竞争,我们提出临界区的概念。

临界区这一概念满足,对于任意的两个进程,不能同时进入临界区,即达到一种进程间“互斥”的效果。

具体来说,临界区的设计需要满足:(摘自讲义)

  • 任何两个进程不能同时处于临界区

  • 对 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)
    // 非临界区
}

错误原因:

Process1lock == 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操作会减少它。

运作方式:

  1. 初始化,给与它一个非负数的整数值。
  2. 执行P(wait()),信号标S的值将被减少。企图进入临界区段的行程,需要先执行P(wait())。当信号标S减为负值时,行程会被挡住,不能继续;当信号标S不为负值时,行程可以获准进入临界区段。
  3. 执行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)是与互斥量配合使用的。在互斥量已经加锁的条件下,条件变量的基本操作有三个:

  • 将互斥量解锁并进入休眠状态(被唤醒时会重新加锁互斥量)

  • 唤醒一个被休眠的进程

  • 唤醒所有休眠的进程

    死锁

死锁产生的条件:

  • 互斥条件:资源要么分配给了某个进程,要么就是可用的

  • 占有和等待条件:已经得到了某个资源的进程可以再请求新的资源(即一层锁不会导致死锁)

  • 不可抢占条件:已经分配给一个进程的资源不能强制抢占,只能由占有它的进程自己释放

  • 环路等待条件:死锁发生时,进程一定可以形成一个环路,环路中每一个进程都等待着下一个进程占有的资源

image-20210716122611212

经典例子: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();
        }
    };

读者写者问题

一个资源,我们可以需要对它进行读写。

读操作是不对资源进行更改的,而写操作对资源进行更改。

这对我们提出了要求:可以多个进程同时读,但是读的过程中不允许写;只能有一个进程对它写入,写的过程不允许任何其他进程同时写或读。

即我们要求:

  1. 允许多个读者可同时对文件执行读操作
  2. 只允许一个写者往文件中写信息
  3. 任一写者在完成写操作之前不允许其他读者或写者工作
  4. 写者执行写操作前,应让已有的写者和读者全部退出

读者优先的操作模式

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/

参考资料