文章目录
进程同步与互斥习题
进程同步与互斥概念
互斥： 源于资源共享。对于硬件和软件临界资源，多个进程必须互斥的对它进行访问。即任一时刻只能有一个进程对其访问。
同步：源于进程间的合作。为了实现进程同步，在系统中设置专门的同步系统来协调诸进程间的运行
取值范围
用某信号量来实现n个进程的互斥时，信号量的取值范围：1-n到1
设有N个进程共享一个程序段，而每次最多允许M个进程进入该程序段（N>M），则所采用的信号量的取值范围为m-n到m
n如果系统中有n个进程，则就绪队列中进程的个数最多有n-1
进程同步与互斥问题
题目一：汽车行驶
题目：
在一个只允许单向行驶的十字路口，分别有 若干由东向西，由南向北的车辆在等待通过十字路口。为了安全，每次只允许一辆车通过（东－>西或南－>北）。当有车辆通过时其它车辆等待，当无车辆在十字路口行驶时则允许一辆车进入（东－>西或南－>北）。请用P、V操作实现能安全行驶的自动管理系统。（西电2001）
分析:
一个资源：十字路口
两个进程：由东向西、由南向北
为资源设置一个互斥信号量s ，初值为1
semaphore s=1;
east_to_west:begin
P(s);
通过十字路口
V(s);
end;
south_to_north:begin
P(s);
通过十字路口
V(s);
end;
题目二：取材料问题
题目：
有一个材料保管员，负责管理纸和笔。另有A、B两组学生，A组学生每人有纸，B组学生每人都有笔，任何一个学生只要能得到另一种材料就可以写信。有一个可以放一张纸或一支笔的小盒，当小盒中为空时，保管员可以任意放入一张纸或一支笔。当小盒中有材料时，允许一个学生从中取出自己所需的材料，当学生取走材料后，允许保管员再存放一件材料。请用P、V操作描述该算法。
分析：
设置互斥信号 mutex，初值为1
设置同步信号paper，pen， 初值为0
semaphore mutex=1;//互斥信号量，表示对小盒操作的互斥访问
semaphore paper=0,pen=0;//同步信号量
保管员:begin
P(mutex);
放入材料；
if(材料==笔)
V(pen);
if(材料==纸)
V(paper);
end;
A组:begin
P(pen);
取走笔;
V(s);
end;
B组:begin
P(paper);
取走纸;
V(s);
end;
题目三：小桥过人问题
题目：
一座小桥（最多能承重两个人），横跨东西两岸，东侧桥段和西侧桥段任意时刻只允许一人通过，桥中间一处宽敞，允许两人通过或者休息。请用P、V操作描述东西两岸过桥的算法。
分析：
信号量 初值 含义 EW 2 允许从东到西的人数 WE 2 允许从西到东的人数 east 1 是否允许在东段桥上 west 1 是否允许在西段桥上
eastTowest：begin
P(EW);
P(WE);
P(east);
从东岸经东段桥，走到桥*；
V(east);
通过桥*或者休息；
P(west);
经西段桥，从桥*到西岸；
V(west);
V(WE);
V(EW);
end;
westToeast：begin
P(EW);
P(WE);
P(west);
从西岸经西段桥，走到桥*；
V(west);
通过桥*或者休息；
P(east);
经东段桥，从桥*到东岸；
V(east);
V(WE);
V(EW);
end;
题目四：阅览室登记问题
题目：
有一阅览室，共有100个座位。读者进入时必须先在一张登记表上登记，该表为每一座位列一表目，包括座号和读者姓名。读者离开时要消掉登记内容。试用P／v操作描述读者进程的同步结构。
semaphore mutex=1;//互斥信号量
semaphore full=100;//资源信号量
int[n]table;
reader:begin
P(full);
P(mutex);
register(table);
v(mutex);
read;
P(mutex);
delete_name(table);
V(mutex);
V(full);
end;
题目五：流水线问题
题目：
某流水线有4个并发工序P1、P2、P3、P4，他们执行情况如下：
P1先执行；P1结束后，P2，P3同时开始执行，P2，P3都结束后，P1才能继续下一次执行，同时P4开始执行。试用PV操作实现他们之间的同步。
分析：
SA12,SB12,SA13,SB13,SB24,SB34：Semophore
SA12:=SA13:=1;
SB12:=SB13:=SB24:=SB34:=0;