第一题

  1. 读者写者问题（写者优先）: 1）共享读; 2）互斥写、读写互斥; 3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
var mutex, wmutex, rwmutex:psemaphore;
var readcount:integer;
begin
	seminit(mutex.v,1;wmutex.v,1;rwmutex.v,1);
	readcount:=0;
	cobegin
		procedure reader;
		begin
			P(rwmutex);
			P(mutex);
			if readcount=0 then P(wmutex);
			readcount:=readcount+1;
			V(mutex);
			V(rwmutex);
			read
			P(mutex);
			readcount:=readcount-1;
			if readcount=0 then V(wmutex);
			V(mutex);
		end
		procedure writer;
		begin
			P(rwmutex);
			P(wmutex);
			writing is performing;
			V(wmutex);
			V(rwmutex);
		end
	coend
end

第二题

  1. 寿司店问题。假设一个寿司店有 5 个座位，如果你到达的时候有一个空座位，你可以立刻就坐。但是如果你到达的时候 5 个座位都是满的有人已经就坐，这就意味着这些人都是一起来吃饭的，那么你需要等待所有的人一起离开才能就坐。编写同步原语，实现这个场景的约束。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var mutex,fullmutex:psemaphore;
var seatcount:integer;
begin
	seminit(mutex.v,1;fullmutex.v,1);
	seatcount:=0;
	cobegin
		procedure customer;
		begin
			P(mutex);
			if (seatcount=5) then P(fullmutex);
			seatcount:=seatcount+1;
			V(mutex);
			eat food
			P(mutex);
			seatcount:=seatcount-1;
			if (seatcount=0) then V(fullmutex);
			V(mutex);
		end
	coend
end

第三题

  1. 进门问题。（1）请给出 P、V 操作和信号量的物理意义。（2）一个软件公司有 5 名员工，每人刷卡上班。员工刷卡后需要等待，直到所有员工都刷卡后才能进入公司。为了避免拥挤，公司要求员工一个一个通过大门。所有员工都进入后，最后进入的员工负责关门。请用 P、V 操作实现员工之间的同步关系。

P操作分配资源 —— 如果无法分配则阻塞（wait）

V操作释放资源 —— 如果有等待进程则唤醒（signal）

信号量的物理意义：

  • 互斥
  • 有限并发
  • 进程同步（描述进程执行的前趋/后继关系）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var doormutex,entermutex:psemaphore;
var incount:integer;
begin
	seminit(doormutex.v,1;entermutex.v.0);
	incount:=0;
	cobegin
		procedure employee;
		begin
			P(doormutex);
			incount:=incount+1;
			V(doormutex);
			if (incount=5) 
			begin
				V(entermutex);
				V(entermutex);
				V(entermutex);
				V(entermutex);
				V(entermutex);
			end
			P(entermutex);
		end
	coend
end
  1. 搜索-插入-删除问题。三个线程对一个单链表进行并发的访问，分别进行搜索、插入和删除。搜索线程仅仅读取链表，因此多个搜索线程可以并发。插入线程把数据项插入到链表最后的位置；多个插入线程必须互斥防止同时执行插入操作。但是，一个插入线程可以和多个搜索线程并发执行。最后，删除线程可以从链表中任何一个位置删除数据。一次只能有一个删除线程执行；删除线程之间，删除线程和搜索线程，删除线程和插入线程都不能同时执行。请编写三类线程的同步互斥代码，描述这种三路的分类互斥问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
var searchmutex,insertmutex,deletemutex;
var searchcount;
begin
	seminit(searchmutex.v,1;insertmutex.v,1;deletemutex.v,1);
	searchcount:=0;
	cobegin
		procedure search;
		begin
			P(searchmutex);
			if (searchcount=0) then P(deletemutex);
			searchcount:=searchcount+1;
			V(searchmutex);
			search
			P(searchmutex);
			searchcount:=searchcount-1;
			if (searchcount=0) then V(deletemutex);
			V(searchmutex);
		end
		procedure insert;
		begin
			SP(insertmutex,deletemutex);
			insert
			SV(insertmutex,deletemutex);
		end
		procedure delete;
		begin
			SP(insertmutex,deletemutex);
			delete
			SV(insertmutex,deletemutex);
		end
	coend
end