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

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

错误原因：

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

运作方式：

  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/

参考资料