操作系统原理学习笔记(八)-经典进程同步问题

操作系统原理学习笔记目录

生产者-消费者问题

利用记录型信号量解决生产者-消费者问题:
假定在生产者与消费者之间的公用缓冲池有n个缓冲区,
可利用互斥信号量mutex实现诸进程对缓冲区的互斥使用,
利用信号量empty与full分别表示空缓冲区与满缓冲区的数量。
又假定这些生产者和消费者等效,只要缓冲池未满,生产者可将消息送入缓冲池。只要缓冲池未空,消费者可从缓冲池取走消息。

生产者消费者描述如下:

int in=0, out=0;
item buffer[n];
semaphore mutex=1, empty=n, full=0;
void producer() {
	do {
		producer an item nextp;
		...
		wait(empty);
		wait(mutex);
		buffer[in] = nextp;
		in = (in+1) % n;
		signal(mutex);
		signal(full);
	}while(true);
}
void consumer() {
	do {
		wait(full);
		wait(mutex);
		nextc = buffer[out];
		out = (out+1) % n;
		signal(mutex);
		signal(empty);
		consumer the item in nextc;
		...
	}while(true);
}
void main() {
	cobegin
		producer();
		consumer();
	coend
}

注意:
每个程序中的wait(mutex)与signal(mutex)需要成对出现,
对资源信号量signal和full的wait和signal操作,也需要成对出现(在不同的程序中出现)。
wait操作的顺序不能颠倒,应先对资源信号量进行wait操作,再对互斥信号量进行wait操作,否则可能出现进程死锁。

利用AND信号量解决生产者-消费者问题:
将AND信号量替换纪录型信号量即可:
用Swait(empty, mutex)代替wait(empty)和wait(mutex),
用Ssignal(mutex, full)代替signal(mutex)和signal(full),
用Swait(full, mutex)代替wait(full)和wait(mutex),
用Ssignal(mutex, empty)代替signal(mutex)和signal(empty)。

int in=0, out=0;
item buffer[n];
semaphore mutex=1, empty=n, full=0;
void producer() {
	do {
		producer an item nextp;
		...
		Swait(empty, mutex);
		buffer[in] = nextp;
		in = (in+1) % n;
		Ssignal(mutex, full);
	}while(true);
}
void consumer() {
	do {
		Swait(full, mutex);
		nextc = buffer[out];
		out = (out+1) % n;
		Ssignal(mutex, empty);
		consumer the item in nextc;
		...
	}while(true);
}

利用管程解决生产者-消费者问题:
在利用管程方法解决生产者-消费者问题时,首先为它们建立一个管程,并命名为producerconsumer(PC)
书上写procducerconsumer,但是后面代码没有c,大概率是这里打错了。

包括两个过程:
put(x)过程:将产品投入缓冲池,用count表示缓冲池已有产品数,当count≥N时,缓冲池已满,生产者等待。
get(x)过程:从缓冲池取出产品。用count表示缓冲池已有产品数,当count≤0时,缓冲池已空,消费者等待。
对于条件变量notfull与notempty,分别有过程cwait与csignal对它们操作:
cwait(condition):管程被占用,其他进程调用该管程时,被阻塞,并挂在条件condition的队列上。
csignal(condition):唤醒cwait执行后阻塞在条件condition队列的进程,如果不止一个,则选择一个,如果队列为空,则略过。

PC管程的描述如下:

Monitor producerconsumer{
	item buffer[N];
	int in, out;
	condition notfull, notempty;
	int count;
	public:
	void put(item x) {
		if(count >= N) cwait(notfull);
		buffer[in] = x;
		in = (in+1) % N;
		count++;
		csignal(notempty);
	}
	void get(item x) {
		if(count <= 0) cwait(notempty);
		x = buffer[out];
		out = (out+1) % N;
		count--;
		csignal(notfull);
	}
	{
		in = 0;
		out = 0;
		count = 0;
	}
}PC;

利用管程解决生产者-消费者问题可描述为:

罢工了,这代码我写了又不看,照搬太累了,
这段代码在第68页,书名在目录页面有写,目录页在文章顶部。
如果没有书,评论一下我拍照发出来。

哲学家进餐问题

哲学家进餐问题(The Dinning Philosophers Problem)是由Dijkstra提出的典型同步问题。
问题描述:五名哲学家坐在五把椅子上共用一张圆桌,圆桌上有五个碗和五支筷子,哲学家在饥饿时停下思考,拿去左右手最近的两支筷子,拿到两支筷子后才进餐,进餐后才继续思考。

利用记录型信号量解决哲学家进餐问题:
分析可知,筷子是临界资源,为了实现对筷子的互斥使用,可以用一个信号量表示一支筷子,由五个信号量构成信号量数组,描述如下:
semaphore chopstick[5] = {1, 1, 1, 1, 1};
所有信号量被初始化成1,第i名哲学家的活动可描述为:

69页代码

容易看出,如果五名哲学家同时伸手拿走左手边的筷子,那么就会出现死锁,这种情况可如此避免:
1.最多允许四名哲学家拿筷子,这样至少会有一名可以获得筷子。
2.左右两支筷子都在时才可拿筷子(类似AND信号量)。
3.奇数号先取左手的筷子,再取右手的筷子,偶数号则相反(筷子必须按顺序拿,没筷子则阻塞等待)。

利用AND信号量机制解决哲学家进餐问题:
即上面讲的第二种方法,描述如下:

70页代码

读者-写者问题

读者-写者问题(Reader-Writer Problem)描述:
一个数据文件可被多个进程共享,将读文件的进程称为“reader进程”,将写文件的进程称为“writer进程”。
允许多个进程同时读取一个数据文件(因为互不影响),但在writer写数据时,不允许reader与其它writer操作。
该问题的核心在于保证一个writer进程必须与其他进程访问共享对象的同步,常被用来测试新同步原语。

利用记录型信号量解决读者-写者问题:
设置一个互斥信号量wmutex,再设置一个整型变量readcount表示reader参与的数量,
只要有一个reader正在读,即readcount>0时,writer不允许执行,
仅当readcount=0时,reader才需执行wait(wmutex),操作成功才可读数据。
当readcount执行-1操作变为0后,才需执行signal(wmutex),允许writer写程序。
因为readcount可能被多个reader同时访问,也属于临界资源,因此也需要一个互斥信号量rmutex。

读者-写者问题可描述为:

71页代码

利用信号量集机制解决读者-写者问题:
这里的问题有了新的限制,最多允许RN个读者同时读。为此,又引入了信号量L,并赋予初值为RN。
通过wait(L, 1, 1)操作来控制读者的数目,每当有一个读者进入时,就要执行wait(L, 1, 1)操作,使L减1,有RN个读者进入读后,L减为0,禁止其他reader进入。

描述如下:

72页代码

其中,sWait(mx, 1, 0)语句起着开关作用。无writer进程时,mx=1,reader可执行,
但一旦writer进入写操作,mx=0,reader进程无法执行。
Swait(mx, 1, 1, L, RN, 0)语句表示无writer进程(mx=1),且无reader进程在读操作(L=RN),writer才能进入临界区操作。

You may also like...

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注