进程同步与互斥习题

文章目录

进程同步与互斥习题

进程同步与互斥概念

互斥: 源于资源共享。对于硬件和软件临界资源,多个进程必须互斥的对它进行访问。即任一时刻只能有一个进程对其访问。

同步:源于进程间的合作。为了实现进程同步,在系统中设置专门的同步系统来协调诸进程间的运行

取值范围

用某信号量来实现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;

进程同步与互斥习题

上一篇:备忘录模式


下一篇:C++多线程编程第十二讲--windows临界区、其他各种mutex互斥量