操作系统——经典进程同步问题

生产者、消费者问题

1、互斥关系:生产者进程和消费者进程对缓冲池的访问互斥。

2、同步关系:缓冲池未满生产者才能向其中放入产品;缓冲池非空消费者才能从其中取出产品。

1. 利用记录型信号量解决

semaphore mutex = 1, empty = n, full = 0; // 分别代表对缓冲池互斥访问,缓冲池中空缓冲区数量和满缓冲区数量
cobegin
	producer() {
		while(true){
			生产一个产品
			Swait(empty, mutex);
			向缓冲池放入一个产品
			Ssignal(mutex, full);
		}
	}
	consumer() {
		while(true){
			Swait(full, mutex);
			从缓冲池取走一个产品
			Ssignal(mutex, empty);
			消费一个产品
		}
	}
coend

2. 利用AND信号量解决

semaphore mutex = 1, empty = n, full = 0;// 分别代表对缓冲池互斥访问,缓冲池中空缓冲区数量和满缓冲区数量
cobegin
	producer() {
		while(true){
			生产一个产品
			wait(empty);
			wait(mutex);
			向缓冲池放入一个产品
			signal(mutex);
			signal(full);
		}
	}
	consumer() {
		while(true){
			wait(full);
			wait(mutex);
			从缓冲池取走一个产品
			signal(mutex);
			signal(empty);
			消费一个产品
		}
	}
coend

哲学家进餐问题

只有互斥关系,没有同步关系

三种解决方式

  1. 至多只允许4个人同时拿起左边的筷子,确保至少一个人能够吃上饭;
  2. 只有左右两边的筷子都能使用时,才允许拿起筷子进餐;
  3. 奇数号哲学家先拿左边的筷子再拿右边的筷子,偶数号哲学家先拿右边的筷子再拿左边的筷子;

至多4人同时拿起左边筷子

semaphore chopstick = {1, 1, 1, 1, 1}; // 每根筷子对应一个互斥信号量
semaphore count = 4; // 至多4人同时拿起左边筷子
cobegin
	Pi() {
		while(true) {
			思考
			wait(count); // 同时拿起左边筷子的人不能超过4个
			wait(chopstick[i]); // 拿起左边的筷子
			wait(chopstick[(i+1)%5]); //拿起右边的筷子
			吃饭
			signal(chopstick[(i+1)%5]);
			signal(chopstick[i);
			signal(count);
		}
	}
coend

只有左右两边的筷子都能使用时,才允许拿起筷子进餐

semaphore chopstick = {1, 1, 1, 1, 1}; // 每根筷子对应一个互斥信号量
cobegin
	Pi() {
		while(true){
			思考
			Swait(chopstick[i], chopstick[(i+1)%5]);
			吃饭
			Ssignal( chopstick[(i+1)%5], chopstick[i]);
		}
	}
coend

奇数号哲学家先拿左边的筷子再拿右边的筷子,偶数号哲学家操作相反

semaphore chopstick = {1, 1, 1, 1, 1}; // 每根筷子对应一个互斥信号量
cobegin
	Pi() {
		while(true){
			思考
			if (i % 2 == 1) { // 奇数号科学家先左后右
				wait(chopstick[i]);
				wait(chopstick[(i+1)%5];
				吃饭
				signal(chopstick[(i+1)%5];
				signal(chopstick[i]);
			}
			else {// 奇数号科学家先右后左
				wait(chopstick[(i+1)%5];
				wait(chopstick[i]);
				吃饭
				signal(chopstick[i]);
				signal(chopstick[(i+1)%5];
			}
		}
	}
coend

读者、写者问题

互斥关系:读写互斥、写者互斥

我们还需要一个rcount整形变量记录读者的数量用来维持读写互斥,为实现对其互斥访问,还需要一个互斥信号量。

记录型信号量思路

int rcount = 0; // 记录读者数量
semaphore rmutex = 1, wmutex = 1; // 对rcount互斥访问信号量,写者互斥信号量
cobegin
	Reader() {
		while(true){
				wait(rmutex);
				if (rcount == 0) {
					wait(wmutex);
				}
				rcount += 1;
				signal(rmutex);
				读操作
				wait(rmutex);
				rcount -= 1;
				if (rcount == 0) {
					signal(wmutex);
				}
				signal(rmutex);
		}
	}
	Writer() {
		while(true){
			wait(wmutex);
			写操作
			signal(wmutex);
		}
	}
coend

信号量集解决至多只允许RN个读者在读

引入一个新的信号量L,初始值为RN,每当有读者进入时通过wait(L,1,1)让L减1,有RN个读者进入时,L为0,无法进入。

int RN;
semaphore L = RN, mx = 1; // L记录还能进入得读者数量,mx实现读写互斥和写者间互斥
cobegin
	Reader(){
		while(true){
			Swait(L, 1, 1); // L减一
			Swait(mx, 1, 0); // 开关,mx为1时可以读,mx为0代表在写
			读操作
			Ssignal(L,1);
		}
	}
	Writer(){
		while(true){
			Swait(mx, 1, 1; L, RN, 0); // 只有无写者操作进行(mx=1)以及没有读者操作进行(L=RN)时才能进行写操作
			写操作
			Ssignal(mx, 1);
		}
	}
coend
三种特殊的信号量集
  1. Swait(S,d,d),只有一个信号量S,每次只允许申请d个资源,资源数少于d个时不予分配;
  2. Swait(S,1,1),S>1时,相当于一般的记录型信号量;S=1时,相当于互斥信号量;
  3. Swait(S,1,0),相当于一个开关,S>=1时允许多个进程(读者)进入临界区;S=0时,阻止任何进程进入临界区;
上一篇:2022届秋招Java后端高频知识点汇总③--多线程


下一篇:僵尸进程与孤儿进程详解