Docs by JrHimself

外观

经典进程的同步问题 ​

生产者 - 消费者问题 ​

一组生产者向一组消费者提供产品，它们共享一个有界缓冲区，生产者向其中投放产品，消费者从中取得产品。它是许多相互合作进程的抽象，如输入进程与计算进程；计算进程与打印进程等。

设有界缓冲区的长度为 n（n>0），一群生产者进程 p1,p2,...,pm，一群消费者进程 c1,c2,…,cm。

  • 同步关系：
    • 当缓冲池放满产品时生产者必须等待。
    • 当缓冲池空时，消费者进程必须等待。
  • 互斥关系：
    • 两组进程中的每个进程必须互斥的使用缓冲区。

根据同步关系，可以定义信号量 empty = n 和 full = 0 表示空闲缓冲区的数量和有产品的缓冲区数量 。当 empty = 0 时，表示缓冲区全满，不能继续生产；当 full = 0 表示缓冲区全空，消费者不能工作。

根据互斥关系定义其互斥锁。这个例子的临界资源就是有界缓冲区，所以设计完之后还要考虑一下各种情况下会不会可能出现死锁。

c
Semaphore mutex = 1, empty = n, full = 0;
// int in = 0, out = 0;
// item buffer[n];
void producer() {
	while (1) {
		生产一个产品 m; // item nextp;
		wait(empty);
		wait(mutex);
		将 m 放入缓冲区; // buffer[in] = nextp;
		in = (in + 1) % n;
		signal(mutex);
		signal(full);
	}
}

void consumer() {
	while (1) {
		wait(full);
		wait(mutex);
		将 m 取出缓冲区; // nextc = buffer[out];
		out = (out + 1) % n;
		signal(mutex);
		signal(empty);
		消费产品 m; // ...
	}
}

如果交换两个 wait 或者两个 signal，可能会产生死锁。

比如当生产者的两个 wait 调换顺序，若缓冲区此时已满，则 empty = 0，full = n，生产者进程和消费者进程同时、分别拿到 wait(mutex) 和 wait(full) ，然后生产者进程等待 empty 信号量被 signal，消费者进程等待 mutex 被 signal，结果就是导致死锁。

又比如消费者的两个 wait 调换顺序，若缓冲区为空也会导致死锁。

要解决可以用 AND 信号量集机制，就是把两个 wait、两个 signal 换成 Swait、Ssignal 一次拿到。

哲学家进餐问题 ​

有五个哲学家，他们的生活方式是交替地进行思考和进餐。他们共用一张圆桌，分别坐在五张椅子上。在圆桌上有五个碗和五支筷子，平时一个哲学家进行思考，饥饿时便试图取用其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐。进餐毕，放下筷子又继续思考。

抽象过程：

c
void philisopher(int i) {
	while (1) {
		wait(chopstick[i]);         // 左边筷子
		wait(chopstick[(i+1)%5]);   // 右边筷子
		eat();
		signal(chopstick[i]);       // 左边筷子
		signal(chopstick[(i+1)%5]); // 右边筷子
		think();
	}
}
  • 互斥关系：筷子！

很容易发现，一旦并发让五位哲学家活过来，他们就会一起拿走左手边的筷子。而右手边的筷子在另一位哲学家手中——死锁了。

解决方法：

  • 一个是使用 AND 信号量集机制，仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐；

  • 考虑到只要有一个人让出自己的左手筷子，就一定会有一个哲学家拿到所有筷子、不会导致死锁，所以可以至多只允许有 4 位哲学家同时拿左边的筷子；

    c
    Semaphore limit = 4;
void philisopher(int i) {
	while (1) {
		wait(limit);                // 只有 limit > 0 才可以用餐
		wait(chopstick[i]);         // 左边筷子
		wait(chopstick[(i+1)%5]);   // 右边筷子
		eat();
		signal(chopstick[i]);       // 左边筷子
		signal(chopstick[(i+1)%5]); // 右边筷子
		signal(limit);
		think();
	}
}

  • 又或者更有秩序且更高效一些，让奇偶交替先拿左或右手边筷子，这样就把筷子分成了两组来竞争，避免了死锁。

读者 - 写者问题 ​

有两组并发进程：读者进程（只读），写者进程（只写）共享一个文件（资源）对象。读、写规则如下：

  • 允许多个“读者”同时执行读操作。
  • 任一“写者”访问文件时，不允许其他“读者”或“写者”工作。

由于多个读进程可以同时操作，那就不能对单个读进程进行上锁或者解锁，这样就不能让多个读者同时读了。可以用一个 read_count 变量记录当前正在访问文件的读者个数。

  • 当无读者访问时，read_count = 0，这时候的读者应该对 wmutex 做 p 操作阻止写进程进入；
  • 当同时访问的读者依次全部读完了，read_count = 0，这时候读者应该对 wmutex 做 v 操作允许写进程进入。

所以在读进程中刚进入和刚离开的时候都应该做判断。对多个读进程，修改 read_count 是互斥的，所以还需要有一个互斥信号量 rmutex。

c
Semaphore rmutex=1, wmutex=1;
int read_count = 0;
void reader() {
	while(1) {
		wait(rmutex); 
		if(read_count == 0)
			wait(wmutex); // 第一位读者阻止写者
		read_count++;
		signal(rmutex);
		
		读数据集；
		
		wait(rmutex); 
		read_count--; 
		if(read_count == 0)
			signal(wmutex); // 第末位读者允许写者进
		signal(rmutex);
	}
}

void writer() {
	while(1) {
		wait(wmutex);
		写数据集;
		signal(wmutex);
	}
}

这样做对于写进程很不公平，因为无论读写进程谁先到，只要当前还在读，读进程就可以不断进行。为了避免这种情况，可以要求读者修改 read_count 之前先和写进程竞争一个互斥锁。

也可以用信号量集机制解决读写问题。

image.png

image.png