OS：6-管程与信号量PV操作

第6章并发程序设计

6.1 并发进程

6.1.1 顺序程序设计

一个进程在处理器上的执行顺序是严格按顺序的
不但指一个程序模块内部，也指两个程序模块之间

特点：

程序执行的顺序性
程序环境的封闭性
执行结果的确定性
计算过程的可再现性

6.1.2 进程的并发性

程序的并发性指一组进程的执行在时间上是重叠的
- 宏观上，一个时间段中几个进程都在同一个处理器上
- 微观上，任一时刻仅有一个进程在处理器上运行
并发进程的分类
- 无关的：满足Bernstein条件
- 交互的：一个进程的执行可能影响其他并发进程的结果
Bernstein条件
- R(pi)={ai1,ai2,ai3,..,ain}，进程pi在执行期间引用的变量集
- W(pi)={bi1,bi2,bi3,...,bin}，进程pi在执行期间改变的变量集
- (R(p1)∩W(p2)) ∪ (R(p1)∩W(p2)) ∪ (W(p1)∩W(p2)) = 空集
交互的并发进程——与时间有关的错误
- 结果不唯一
- 永远等待

6.1.3 进程的交互：竞争与协作

竞争关系：两个进程要访问同一资源
- 带来两个问题：死锁和饥饿
- 解决：互斥
  - 若干进程要使用同一共享资源时，任何时刻最多允许一个进程去使用
协作关系：某些进程为了完成同一任务需要分工协作，合作的每一个进程不知道互相的进度，当合作进程中的一个到达协作点时，在尚未得到其伙伴进程发来的消息或信号之前应阻塞自己
- 解决：同步
  - 一个进程的执行依赖于另一个协作进程的信号，当一个进程没有得到来自于另一个进程的消息或信号则需等待

6.2 临界区管理

6.2.1 互斥与临界区

并发进程中
- 共享变量有关的程序段——临界区
- 共享变量代表的资源——临界资源
临界区调度原则
- 一次至多一个进程进入临界区
- 如果已有进程在临界区，其他试图进入的进程需要等待
- 进入临界区的进程应该在有限时间内退出

6.2.2 Peterson算法

尝试1：可能两个进程都进去
尝试2：可能两个进程都进不去
Peterson算法

6.2.3 实现临界区管理的硬件设施

关中断

测试并建立指令

bool TS(bool &x) {
	if(x) {
		x=false;
		return true;
	}else
		return false;
}

//TS指令实现进程互斥
bool s=true;
cobegin
process Pi( ) { //i=1,2,...,n
	while(!TS(s)); //上锁
	{临界区};
	s=true; //开锁
}
coend

对换指令

void SWAP(bool &a, bool &b) {
    bool temp=a;
    a=b;
    b=temp;
}

//对换指令实现进程互斥
bool lock=false;
cobegin
Process Pi( ){ //i=1,2,...,n
	bool keyi=true;
	do {
		SWAP(keyi,lock);
    }while(keyi); //上锁
    {临界区};
	SWAP(keyi,lock); //开锁
}
coend

6.3 信号量与PV操作

6.3.1 信号量与PV操作

struct semaphore
{ int count; QueueType queue; }
void P(semaphore s); // also named wait
{
	s.count - -;
	if (s.count < 0) 
    { place this process in s.queue; block this process }
};
void V(semaphore s); // also named signal
{
	s.count ++;
	if (s.count <= 0)
	{ remove a process from s.queue; convert it to ready state; }
};

count>0，代表可使用的资源数
count<0，绝对值表示等待进程数

6.3.2 经典互斥问题

飞机票问题

方案1：性能差

方案2：性能较好

哲学家就餐问题

初步尝试：存在死锁！

一些解决方案：

至多允许四个哲学家同时取叉子 (C. A. R. Hoare方案)

奇数号先取左手边的叉子，偶数号先取右手边的叉子

每个哲学家取到手边的两把叉子才吃，否则一把叉子也不取 (第五版教材, Page 188, AND型信号量)

解法1：至多允许四个哲学家同时取叉子
解法2：奇数号先取左手边的叉子，偶数号先取右手边的叉子

6.3.3 经典同步问题

生产者-消费者问题

一个生产者，一个消费者，一个缓冲单元
一个生产者，一个消费者，多个缓冲单元
多个生产者，多个消费者，多个缓冲单元

苹果-桔子问题

6.3.4 其他习题

读写者问题

读者优先
读写公平
- 新增信号量S，写者进程有机会进队列等，会阻断两波读者，等前一波读者读完了就可以写
写者优先

睡眠理发师问题

理发店理有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子

如果没有顾客，理发师便在理发椅上睡觉

一个顾客到来时，它必须叫醒理发师

如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开

农夫猎人问题

有一个铁笼子，每次只能放入一个动物。猎手向笼中放入老虎，农夫向笼中放入羊；动物园等待取笼中的老虎，饭店等待取笼中的羊

其实就苹果桔子问题

银行业务问题

某大型银行办理人民币储蓄业务，由n个储蓄员负责。每个顾客进入银行后先至取号机取一个号，并且在等待区找到空沙发坐下等着叫号。取号机给出的号码依次递增，并假定有足够多的空沙发容纳顾客。当一个储蓄员空闲下来，就叫下一个号

其实就是生产消费问题，(n,n,inf)

注意到这里多了个server_count，按照生产消费者的代码是不应该有的，为什么呢？如果没有的话，从customer角度，拍了号就结束了，P(server_count)代表了一个被叫号、服务的过程

缓冲区管理

有n个进程将字符逐个读入到一个容量为80的缓冲区中(n>1)，当缓冲区满后，由输出进程Q负责一次性取走这80个字符。这种过程循环往复，请用信号量和P、V操作写出n个读入进程(P1， P2，…Pn)和输出进程Q能正确工作的动作序列

本质上也是生产者消费者问题的变式

售票问题

汽车司机与售票员之间必须协同工作，一方面只有售票员把车门关好了司机才能开车，因此，售票员关好门应通知司机开车，然后售票员进行售票。另一方面，只有当汽车已经停下，售票员才能开门上下客，故司机停车后应该通知售票员。假定某辆公共汽车上有一名司机与两名售票员，汽车当前正在始发站停车上客，试用信号量与P、V操作写出他们的同步算法

吸烟者问题

一个经典同步问题：吸烟者问题(patil，1971)。三个吸烟者在一个房间内，还有一个香烟供应者。为了制造并抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴，供应者有丰富货物提供。三个吸烟者中，第一个有自己的烟草，第二个有自己的纸和第三个有自己的火柴。供应者随机地将两样东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再把两样东西放在桌子上，唤醒另一个吸烟者

这道题思路比较巧，用了一个逆向思维，信号量代表的不是缺什么，而是唤醒已经有什么的人

6.4 管程

6.4.1 管程和条件变量

管程是由局部于自己的若干公共变量及其说明和所有访问这些公共变量的过程所组成的软件模块

为什么要引入管程
- 把分散在各进程中的临界区集中起来进行管理
- 防止进程有意或无意的违法同步操作
- 便于用高级语言来书写程序
条件变量：是出现在管程内的一种数据结构，且只有在管程中才能被访问，它对管程内的所有过程是全局的，只能通过两个原语操作来控制它
- wait( )-阻塞调用进程并释放管程，直到另一个进程在该条件变量上执行signal( )
- signal( )-如果存在其他进程由于对条件变量执行wait( ) 被阻塞，便释放之；如果没有进程在等待，那么，信号不被保存、
  - 使用signal释放等待进程时，可能出现两个进程同时停留在管程内
  - 霍尔(Hoare, 1974)采用：执行signal的进程等待，直到被释放进程退出管程或等待另一个条件变量

type 管程名=monitor {
	局部变量说明；
	条件变量说明；
	初始化语句；
	define 管程内定义的，管程外可调用的过程或函数名列表；
	use 管程外定义的，管程内将调用的过程或函数名列表；
	过程名/函数名(形式参数表) {
		<过程/函数体>;
	}
	…
	过程名/函数名(形式参数表) {
		<过程/函数体>;
	}
}

6.4.2 管程的实现

霍尔方法使用P和V操作原语来实现对管程中过程的互斥调用，及实现对共享资源互斥使用的管理
不要求signal操作是过程体的最后一个操作，且 wait和signal操作可被设计成可以中断的过程

数据结构

mutex
- 对每个管程，使用用于管程中过程互斥调用的信号量 mutex (初值为1)
- 进程调用管程中的任何过程时，应执行P(mutex)；进程退出管程时，需要判断是否有进程在next信号量等待，如果有(即next_count>0)，则通过V(next)唤醒一个发出signal的进程，否则应执行V(mutex)开放管程，以便让其他调用者进入
- 为了使进程在等待资源期间，其他进程能进入管程，故在 wait操作中也必须执行V(mutex)，否则会妨碍其他进程进入管程，导致无法释放资源
next和next-count
- 对每个管程，引入信号量next(初值为0)，凡发出signal操作的进程应该用P(next)阻塞自己，直到被释放进程退出管程或产生其他等待条件
- 进程在退出管程的过程前，须检查是否有别的进程在信号量next上等待，若有，则用V(next)唤醒它。next-count(初值为0)，用来记录在next上等待的进程个数
x-sem和x-count
- 引入信号量x-sem(初值为0)，申请资源得不到满足时，执行P(x-sem)阻塞。由于释放资源时，需要知道是否有别的进程在等待资源，用计数器x-count(初值为0)记录等待资源的进程数
- 执行signal操作时，应让等待资源的诸进程中的某个进程立即恢复运行，而不让其他进程抢先进入管程，这可以用 V(x-sem)来实现

使用??-count的原因在于：信号量规定，只允许使用P、V原语操作访问信号量，不能直接对信号量的整型值做读写操作，也不能直接对信号量的队列做其他任何操作

管程操作

6.4.3 解决互斥问题

读写者问题

哲学家就餐问题

其他解法

TYPE dining = monitor{
	semaphore f[5]}; // 叉子
	semaphore room; // 房间
	int f_count[5],room_count,rc=0;
	bool f_use[5]={false};
	InterfaceModule IM;
	USE enter,leave,wait,signal;
	DEFINE give,smoke;
	procedure pickup(int i){ // i = 0,1,2,3,4
		enter(IM);
		if(rc==4) wait(room,room_count,IM);
		rc++;
		if(f_use[i]) wait(f[i],f_count[i],IM);
		f_use[i]=true;
		if(f_use[(i+1)%5]) wait(f[(i+1)%5],f_count[(i+1)%5],IM);
		f_use[(i+1)%5]=true;
		leave(IM);
	}
	procedure putdown(int i){ // i = 0,1,2,3,4
		enter(IM);
		f_use[i]=f_use[(i+1)%5]=false;
		signal(f[i],f_count[i],IM);
		signal(f[(i+1)%5],f_count[(i+1)%5],IM);
		rc--;
		signal(room,room_count,IM);
		leave(IM);
	}
}
cobegin
	process philosopher_i(){ // i = 0,1,2,3,4
		while(1){
			pickup(i);
			// 吃
			putdown(i);
		}
	}
coend

睡眠理发师问题

理发店理有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子

如果没有顾客，理发师便在理发椅上睡觉

一个顾客到来时，它必须叫醒理发师

如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开

TYPE barbershop = monitor{
	semaphore barber,customer;
	int barber_count,customer_count;
	int chair=N,cc=0,bc=0;//cc=等待顾客，bc=可用理发师
	InterfaceModule IM;
	USE enter,leave,wait,signal;
	DEFINE give,smoke;
	procedure barber(){
		enter(IM);
		if(cc==0) wait(customer,customer_count,IM); // 如果没人来，睡觉
		cc--;
		leave(IM);
	}
	procedure barber_next(){
		enter(IM);
		signal(barber,barber_count,IM); // 送客，唤醒等待的客户
		leave(IM);
	}
	procedure customer(){
		enter(IM);
		if(cc<chair){
			cc++;
			if(cc<=bc){
				signal(customer,customer_count,IM); // 客人来了，有睡觉的赶紧给爷起
			}else{
				wait(barber,barber_count,IM); // 在椅子上等
			}
		}// 没椅子，溜了
		leave(IM);
	}
}
cobegin
	process barber_i(){ // i = 0,1,2,3,..
		barbershop.bc++;
		while(1){
			barbershop.barber();
			// 理发
			barbershop.barber_next();
		}
	}
	process customer_i(){ // i = 0,1,2,3,...
		while(1){
			barbershop.customer();
			// 理发
		}
	}	
coend

生产消费者的一个变式

6.4.4 解决同步问题

生产者-消费者问题

苹果桔子问题

6.4.5 其他经典问题

吸烟者问题

TYPE smoke = monitor{
	semaphore s[3]={0,0,0};
	semaphore g=1;
	int s_count[3]={0,0,0},g_count;
	bool sc[3]={false};
	InterfaceModule IM;
	USE enter,leave,wait,signal;
	DEFINE give,smoke;
	procedure give(){
		enter(IM);
		wait(g,g_count,IM);
		// 随机取i,j
		if((i==0&&j==1)||(j==0&&i==1)){
			signal(s[2],s_count[2],IM);
		}else if((i==0&&j==2)||(j==0&&i==2)){
			signal(s[1],s_count[1],IM);
		}else if((i==2&&j==1)||(j==2&&i==1)){
			signal(s[0],s_count[0],IM);
		}
		leave(IM);
	}
	procedure smoke(int i){
		enter(IM);
		if(!sc[i]) 
			wait(s[i],s_count[i],IM);
		sc[i] = false;
		// 抽烟
		signal(g,g_count,IM);
		leave(IM);
	}
}
cobegin
	process giver(){
		while(1)
			give();
	}
	process smoker_i(){ // i = 0,1,2
		while(1)
			smoke(i);
	}
coend

生产线装配问题

设儿童小汔车生产线上有一只大的储存柜，其中有N 个槽（N为5的倍数且其值≥5），每个槽可存放1个车架或1个车轮；设有3组生产工人，其活动如下，试用管程实现这三组工人的生产合作工作

将N个槽口分为两部分：N/5和4N/5，分别装车架和车轮

车架 box1[N/5];

车轮 box2[4*N/5] ;

TYPE pipeline = monitor{
	semaphore S1,S2,S3,S4;
	int S1_count,S2_count,S3_count,S4_count;
	int c1,c2;
	InterfaceModule IM;
	USE enter,leave,wait,signal;
	DEFINE put1,put2,take;
	procedure put1(){
		enter(IM);
		if(c1==N/5)	wait(S1,S1_count,IM);
		// 生产车架并放入
		c1++;
		signal(S3,S3_count,IM);
		leave(IM);
	}
	procedure put2(){
		enter(IM);
		if(c2==4N/5)	wait(S2,S2_count,IM);
		// 生产车轮并放入
		c2++;
		if(c2%4==0)	signal(S4,S4_count,IM);
		leave(IM);
	}
	procedure take(){
		enter(IM);
		if(c1==0)	wait(S3,S3_count,IM);
		// 取一个车架
		c1--;
		if(c2<4)	wait(S4,S4_count,IM);	
		// 取四个车轮
		c2-=4;
		signal(S1, S1_count, IM);
		signal(S2, S2_count, IM);
		leave(IM);
	}	
}
cobegin
	略
coend

6.5 进程通信

消息传递提供了这些功能，最典型的消息传递原语

send 发送消息的原语
receive 接收消息的原语

6.5.1 直接通信

对称直接寻址，发送进程和接收进程必须命名对方以便通信，原语send() 和 receive()定义如下：
- send(P, messsage) 发送消息到进程P
- receive(Q, message) 接收来自进程Q的消息
非对称直接寻址，只要发送者命名接收者，而接收者不需要命名发送者，send()和 receive()定义如下：
- send(P, messsage) 发送消息到进程P
- receive(id, message) 接收来自任何进程的消息，变量 id置成与其通信的进程名称
消息格式

6.5.2 间接通信

消息不是直接从发送者发送到接收者，而是发送到由临时保存这些消息的队列组成的一个共享数据结构，这些队列通常成为信箱(mailbox)

一个进程给合适的信箱发送消息，另一进程从信箱中获得消息

间接通信的send()和receive()定义如下：

send(A,message)：把一封信件(消息)传送到信箱A
- 如果指定的信箱未满，则将信件送入信箱中由指针所指示的位置，并释放等待该信箱中信件的等待者；否则，发送信件者被置成等待信箱状态
receive(A,message)：从信箱A接收一封信件(消息)
- 接收信件：如果指定信箱中有信，则取出一封信件，并释放等待信箱的等待者，否则，接收信件者被置成等待信箱中信件的状态

（注：R为出，W为入）

应用：求解生产者消费者问题

6.5.3 消息缓冲通信

注意在复制过程中系统会将接收进程名换成发送进程名，以便接收者识别

6.6 死锁

6.6.1 死锁产生

进程推进顺序不当
PV操作不当
资源分配不当

若系统中有m个资源被n个进程共享，每个进程都要求Ｋ个资源，而m < n·K时，即资源数小于进程所要求的总数时，如果分配不得当就可能引起死锁（这句话表述不太对）

当 m≤n 时，每个进程最多请求 1 个这类资源时，系统一定不会发生死锁。当 m>n 时，如果 m/n 不整除，每个进程最多可以请求”商+1”个这类资源，否则为”商”个资源，使系统一定不会发生死锁

可以这么理解，只要有一个进程可以满足了，那么它就能执行完成并释放它占有的资源，其他进程也可以接着被满足
对临时性资源使用不加限制

进程P1等待进程P3的信件S3来到后再向进程P2发送信件S1；P2又要等待P1的信件S1来到后再向P3发送信件S2；而P3也要等待P2的信件S2来到后才能发出信件S3。这种情况下形成了循环等待，产生死锁

6.6.2 死锁防止

系统形成死锁的四个必要条件

互斥条件(mutual exclusion)：系统中存在临界资源，进程应互斥地使用这些资源
占有和等待条件(hold and wait)：进程请求资源得不到满足而等进程请求资源得不到满足而等待时，不释放已占有的资源
不剥夺条件(no preemption)：已被占用的资源只能由属主释放，不允许被其它进程剥夺
循环等待条件(circular wait)：存在循环等待链，其中，每个进程都在链中等待下一个进程所持有的资源，造成这组进程永远等待

死锁防止的一些方法：

破坏第一个条件：
- 使资源可同时访问而不是互斥使用
- 但是有的资源不允许
破坏第二个条件：
- 静态分配，进程在执行中不再申请资源，就不会出现占有某些资源再等待另一些资源的情况
- 降低资源利用率
破坏第三个条件：
- 采用剥夺式调度方法
- 当进程在申请资源未获准许的情况下,如主动释放资源(一种剥夺式),然后才去等待。
破坏第四个条件

层次分配策略（破坏条件2、4）

资源被分成多个层次

当进程得到某一层的一个资源后，它只能再申请较高层次的资源
当进程要释放某层的一个资源时，必须先释放占有的较高层次的资源
当进程得到某一层的一个资源后，它想申请该层的另一个资源时，必须先释放该层中的已占资源

例如，将资源排序，r1,r2……,rm ，规定如果进程不得在占用资源ri(1≤i≤m)后再申请 rj(j<i)

6.6.3 死锁避免

银行家算法

注意一个解题格式

6.6.4 死锁检测和解除

本质上还是归结于银行家算法

OS：6-管程与信号量PV操作

第6章 并发程序设计

6.1 并发进程

6.1.1 顺序程序设计

6.1.2 进程的并发性

6.1.3 进程的交互：竞争与协作

6.2 临界区管理

6.2.1 互斥与临界区

6.2.2 Peterson算法

6.2.3 实现临界区管理的硬件设施

6.3 信号量与PV操作

6.3.1 信号量与PV操作

6.3.2 经典互斥问题

飞机票问题

哲学家就餐问题

6.3.3 经典同步问题

生产者-消费者问题

苹果-桔子问题

6.3.4 其他习题

读写者问题

睡眠理发师问题

农夫猎人问题

银行业务问题

缓冲区管理

售票问题

吸烟者问题

6.4 管程

6.4.1 管程和条件变量

6.4.2 管程的实现

数据结构

管程操作

6.4.3 解决互斥问题

读写者问题

哲学家就餐问题

睡眠理发师问题

6.4.4 解决同步问题

生产者-消费者问题

苹果桔子问题

6.4.5 其他经典问题

吸烟者问题

生产线装配问题

6.5 进程通信

6.5.1 直接通信

6.5.2 间接通信

6.5.3 消息缓冲通信

6.6 死锁

6.6.1 死锁产生

6.6.2 死锁防止

6.6.3 死锁避免

6.6.4 死锁检测和解除

第6章并发程序设计