操作系统第二章（3）

操作系统——进程管理（3）

进程同步

• （大概理解）虽然多进程是并发执行的，但仍然要满足一定的时空规则，即同步规则。
• 同步：直接制约关系。指为完成某种任务建立的多个进程之间，必须有一个次序、先后的制约关系。
• 临界资源：一次仅允许一个进程使用的资源。对临界资源的访问必须是互斥地进行，而访问临界资源的代码称为临界区
• 互斥：间接制约关系。[理解]因为临界资源的限制，所以制约后来者无法立即获得资源，即为互斥。同时要满足四个准则：
  • 空闲让进
  • 忙则等待
  • 有限等待，保证有限时间内进入临界区
  • 让权等待，当无法进入临界区，进程应立即释放CPU

互斥实现办法

通常有软件实现和硬件实现两种

软件实现

1. 单标志法
   • 设置公用变量turn，设turn=1，允许P1进入，设turn=2，允许P2进入
   • 缺点：两个进程必须交替进入。P1退出后，如果P2不打算进，那么将不允许P1进入。

//P1
while(turn!=1)；//等待
//Todo 进临界区
turn =2;//允许P2进入
//Todo 退临界区
	

//P2
while(turn!=2)；//等待
//Todo 进临界区
turn =1;//允许P1进入
//Todo 退临界区
	

2. 双标志法先检查
   • 每一个进程访问临界资源前，先查看临界资源是否正在被访问，查看后进入临界区，改变自身标志
   • 设置数据flag[i]，若第i个元素为flase，说明Pi未进入临界区
   • 缺点：会出现多进程进入同一个临界区。根源：检查和修改并非原子操作
3. 双标志法后检查
   • 先置自己的标志，再检验对方状态，若对方不在则自己进入临界区
   • 数据依旧是flag[i]，同先检查
   • 缺点：会出现双方谦让，标志位都置true，但都没进入临界区的情况。问题根源同先检查法
4. Peterson‘s Algorithm（皮特森算法）
   • 先设置进入标志，再设置turn，同时检查另一个进程的标志，是单标志和后检查法的混用；
   • flag解决临界资源的互斥，turn解决饥饿（以下代码中，两个while句子同一时刻最多成立一条，所以解决了饥饿问题）

//Pi
flag[i]=true;turn=j;//flag[i]=true表示i想进临界区
while(flag[j]&&turn==j);//表示j已在临界区
//Todo 进临界区
flag[i]=false;
/Todo 退临界区

//Pj
flag[j]=true;turn=i;
while(flag[i]&&turn==i);
//Todo 进临界区
flag[j]=false;
/Todo 退临界区

硬件实现

主要有中断屏蔽方法和硬件指令方法

1. 中断屏蔽。当一个进程正在CPU执行临界区代码时，禁止一切中断发生（即关中断）。步骤为①关中断；②临界区；③开中断。缺点：CPU能力被限制，效率降低明显，而且关中断的权力交给用户就很不明智。
2. 硬件指令。TestAndSet指令和Swap指令。
   • TestAndSet指令是原子指令，执行代码时不允许被中断。
   • Swap指令，交换两个字/字节的内容
   • 以下代码中，lock所指内存代表共享布尔变量，*lock=true表示被占用

==TestAndSet==
//读出标志（即return 标志）后，置标志为真
boolean TestAndSet(boolean *lock){
	boolean old;
	old=*lock;
	*lock=true;
	return old;
}
while TestAndSet(&lock);//lock若true，沉浸while里；lock若false，①跳出while循环，②lock置ture。
//Todo 临界区代码
lock=false;
//Todo 普通代码

////硬件保证①②原子同时


==Swap==
Swap(boolean *a,boolean*b){
//简单交换而已，别瞎想
	boolean temp;
	temp=*a;
	*a=*b;
	*b=temp;
}
key=true;
while(key!=false)
	swap(&lock,&key);//lock若true，交换，而且沉浸在while里；lock若false，交换，key变成false，①lock变为true，②跳出while循环。
//Todo 临界区代码
lock=false;
//Todo 普通代码

////硬件保证①②原子同时

• 硬件优点：适合任意数目的进程，不管是单核还是多核CPU；简单、容易验证正确性；可以支持多临界区，只需为每个临界区设立一个布尔变量；
• 硬件缺点：进程进入临界区需要耗费CPU时间，不能让权等待。有些进程出现饥饿现象。

信号量

为了解决互斥和同步的问题，只能被两个标准的原语wait(S)、signal(S)来访问，即P、V操作

整数型资源S

P、V描述如下：

wait(S){
	while(S<=0);//忙等
	S--;	//占，S>=0时才会流转到这一步
}
signal(S){
	S++;	//放
}

记录性信号量

除了一个代表资源数目的整型变量value外，还有一个进程链表L，链接所有等待该资源的进程（即存有记录）

typedef struct{
	int value;
	struct process *L;
}semaphore;

void wait(semaphore S){
	S.value--;
	if(S.value<0){原value为负或零，即缺少资源
		add this process to S.L;
		block(S.L);//此process放弃CPU
	}
}

void signal(semaphore S){
	S.value++;
	if(S.value<=0){//原value为负，即有进程在等待资源
		remove a process P from S.L;
		wakeup(P);//进入就绪队列，等待CPU
	}
}

信号量实现同步

以下代码保证了会按照先P1后P2的顺序执行

Semaphore S=0;
P1(){
	...
	x;
	V(S);//放
	...
}
P2(){
	...
	P(S);//占
	y;
	...
}

信号量实现互斥

以下代码可实现两进程对临界资源的互斥访问

semaphore S=1;
P1(){
	...
	P(S);//占
	x;
	V(S);
	...
}
P2(){
	...
	P(S);
	y;
	V(S);
}

信号量实现前驱关系

拓扑结构如下：

• S1->S2->S4->S6
• S1->S2->S5->S6
• S1->S3->S6

代码如下：

semaphore a1=a2=b1=b2=c=d=e=0;
S1(){
	...;
	V(a1);V(a2);
}
S2(){
	P(a1);
	...;
	V(b1);V(b2);
}
S3(){
	P(a2);
	...;
	V(c);
}
S4(){
	P(b1);
	...;
	V(d);
}
S5(){
	P(b2);
	...;
	V(e);
}
S6(){
	P(c);
	P(d);
	P(e);
	...;
}

管程

• 定义：由一组数据以及定义在这组数据之上的对这组数据的操作组成的软件模块，这组操作能初始化并改变管程中的数据和同步进程。[理解]数据+操作，像java中的抽象类（具有成员变量和方法、构造）

经典同步问题

例1：生产成品的同步问题，操作buffer区的互斥问题

semaphore mutex=1,list1=n,list2=0;
//list1为producer需要消耗的原料集；list2为供consumer使用的成品
producer(){
	while(1){
		produce an item in nextp;
		P(list1);//消耗原料
		P(mutex);
		add nextp to buffer;
		V(mutex);
		V(list2);//产出成品
	}
}
consumer(){
	while(1){
		P(list2);//消耗成品
		P(mutex);
		remove an item from buffer;
		V(mutex);
		V(list1);//付费给producer，等价于为producer购买原料
		consume the item;
	}
}

例2：（dad与daughter的同步）和（mom与son的同步），以及操作plate的互斥问题

• dad如果操作了，mom和son都会静默，而daughter被唤醒，所以是同步问题；
• daughter和son是选择条件执行，他们之间没有同步或互斥问题；
• plate的操作是四人的互斥问题；

semaphore plate=1,apple=0,orange=0;
dad(){
	while(1){
		prepare an apple;
		P(plate);
		put the apple on the plate;
		V(apple);
	}
}
mom(){
	while(1){
		prepate an orange;
		P(plate);
		put the orange on the plate;
		V(orange);
	}
}
son(){
	while(1){
		P(orange);
		take an orange from the plate;
		V(plate);
		eat the orange;
	}
}
daughter(){
	while(1){
		P(apple);
		take an apple from the plate;
		V(plate);
		eat the apple;
	}
}

例3：读与写文件的复杂问题

• 允许多个读进程；
• 只允许一个写进程；
• 写进程时执行前，要退出已有的读进程和写进程；
• 写进程执行完毕前，不允许其他读进程与写进程进入。

==①读进程优先算法==
int count=0;//记录读者数量
semaphore mutex=1;//保护count变量的更新
semaphore rw=1;//访问文件的互斥
writer(){
	while(1){
		P(rw);
		writing;
		V(rw);
	}
}

reader(){
	while(1){
		P(mutex);
		if(count==0)
			P(rw);//第一个读进程来了，锁死rw
		count++;
		V(mutex);
		reading;
		P(mutex);
		count--;
		if(count==0)
			V(rw);//最有一个读进程退出后，解锁rw
		V(mutex);
	}
}

==②读写公平算法==
int count=0;//记录读者数量
semaphore mutex=1;//保护count变量的更新
semaphore rw=1;//访问文件的互斥
# semaphore w=1;//用来实现写优先（相对的）
writer(){
	while(1){
# 		P(w);
		P(rw);
		writing;
		V(rw);
# 		V(w);
	}
}

reader(){
	while(1){
# 		P(w);
		P(mutex);
		if(count==0)
			P(rw);//第一个读进程来了，锁死rw
		count++;
		V(mutex);
# 		V(w);
		reading;
		P(mutex);
		count--;
		if(count==0)
			V(rw);//最后一个读进程退出后，解锁rw
		V(mutex);
	}
}

• 读进程优先算法中，只要有一个读进程活跃，后来的读进程将被允许但写进程将会阻塞，可能导致写进程饿死（此时写进程地位偏低）；
• 读写公平算法中，#部分为新增代码，新来的读/写进程公平竞争资源w。

例4：哲学家抓筷子问题

• 5个哲学家坐在圆桌上，每两人之间摆上一只筷子
• 一左一右的筷子分别拿起（不论次序）
• 拿到全部筷子的可以吃饭，没拿到的饿着
• 哲学家编号0~4，左边筷子编号i，右边筷子编号（i+1）%5

semaphore chopstick[5]={1,1,1,1,1};
semaphore mutex=1;//取筷子的信号量
P[i](){
	do{
		P(mutex);
		P(chopstick[i]);
		P(chopstick[(i+1)%5]);
		V(mutex);//同时抓到左右筷子时才释放mutex
		eat;
		V(chopstick[i]);
		V(chopstick[(i+1)%5]);
		think;
	}while(1);
}

• 如果没有mutex的互斥，可能出现所有人拿着左边筷子然后等不到右边筷子的集体饥饿现象（死锁）；
• 使用mutex的互斥，相当于增加限制条件：当一个哲学家左右两边的筷子都可用时，才允许他抓起筷子

例5：吸烟者与供应者的复杂问题

• 吸一根烟需要3种材料，3个吸烟者各自持有某一种材料（数量无穷多）；
• 供应者每次提供2种材料，其中能凑足3样材料的吸烟者拿到材料，吸掉烟，告知供应者；
• 供应者提供另外2种材料。
• 明显，3个吸烟者的吸烟操作是互斥的

int random;
semaphore offer1=0;//分别指代3种组合
semaphore offer2=0;
semaphore offer3=0;
semaphore finish=0;//抽烟的互斥操作
P0(){
	while(1){
		random=整数随机数%3；
		if(random==0){
			V(offer1);
		}else if(random==1){
			V(offer2);
		}else{
			V(offer3);
		}
		P(finish);//如果材料没被拿走，就会卡在这里，材料拿走了，才会重新random，进而重新offer
	}
}
P1(){//缺offer3的两种材料的吸烟者
	while(1){
		P(offer3);
		已有三种材料，变成烟，抽掉；
		V(finish);
	}
}
P2(){
	while(1){
		P(offer2);
		已有三种材料，变成烟，抽掉；
		V(finish);
	}
}
P3(){
	while(1){
		P(offer1);
		已有三种材料，变成烟，抽掉；
		V(finish);		
	}
}

死锁

• 定义：多个进程因竞争资源而造成的一种僵局，若无外力推动，进程将无法推进。举例：哲学家的筷子问题时，如果五人全都拿起左手的筷子，将无一人取得右手的筷子，陷入江局 ○( ＾皿＾)っHiahiahia…

• 死锁产生原因：

  • 多个进程请求和释放资源不当会引起死锁；例：双方等待对方的资源。
  • 信号量使用不当会引起死锁。例：双方等待对方的消息。

• 形成死锁的4个必要条件，而破坏这些条件就可以打破死锁的江局

  • 互斥条件。
  • 不剥夺条件。对可剥夺资源的竞争是不会引起死锁的。
  • 请求和保持条件。进程已经保持了至少一个资源，还想要别的资源但该资源被占用，而本进程也不愿意放弃已获得的资源。
  • 循环等待条件。存在一条循环等待链，构成了一个死循环的闭环。

• 三种策略：①预防死锁：破坏四个必要条件；②避免死锁：防止系统进入不安全状态，进而避免死锁；③死锁检测：允许死锁产生的时候能够检测死锁并恢复进程的执行。

  • 前两者是事先预防，但预防死锁的条件比较严格，实现起来简单却导致系统的效率低，资源利用率低；
  • 避免死锁的限制条件宽松，但要通过判断是否进入不安全状态，实现较难

	资源分配策略	各种可能模式	主要优点	主要缺点
死锁预防	保守，宁可资源闲置	一次请求所有资源，资源剥夺，资源按序分配	适用于做突发式处理的进程，不必进行剥夺	效率低，进程初始化时间延长，剥夺次数过多，不便灵活申请新资源
死锁避免	是“预防”和“检测”的折中（在运行中判断是否可能死锁）	寻找可能的安全允许顺序	不必进行剥夺	必须知道将来的资源需求，进程不能被长时间阻塞
死锁检测	宽松，只要允许就分配资源	定期检查死锁是否已经发生	不延长进程初始化时间，允许对死锁进行现场处理	通过剥夺解除死锁，造成损失

死锁预防

（1）破坏互斥条件

• 不太可行，有些场合需要保护这种互斥性

（2）破坏不剥夺条件

• 若一个进程请求新资源而得不到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请。从而破坏了不剥夺条件。
• 但实现起来比较复杂，释放资源会造成前一阶段的工作实效，反复申请和释放资源可能增加系统开销。
• 这种方法适用于状态易于保存和恢复的资源，比如CPU的寄存器或内存资源，但不适合于打印机之类的资源。

（3）破坏请求和保持条件

• 采用预先静态分配的方法，进程在运行前一次性申请完它所需要的全部资源，在资源未满足前，不把它投入运行；一旦投入运行后，这些资源都归它所有，也不再提出其他资源请求。
• 实现简单，缺点：资源被严重浪费，有些资源可能仅在开始或结束短暂使用甚至不被使用。导致饥饿现象，等待某些资源的进程迟迟得不到资源。

（4）破坏循环等待条件

• 可采用顺序资源分配法，先把资源编号，规定每个进程必须按照编号递增的顺序请求资源，同类资源一次申请完。进程如果申请到了资源6，之后只能申请编号大于6的资源，不能申请1~6了。
• 缺点：编号必须相对稳定，这就限制了新设备的增加。容易出现作业使用资源的顺序与系统规定顺序不同的请求，造成资源的浪费。同时也给用户编程带来麻烦。

死锁避免

• 在资源动态分配过程中，防止系统进入不安全状态，以避免发生死锁。限制条件较弱。
• 不安全状态：在当前时刻，找不到一个安全序列顺利完成进程的执行。
• 安全序列：按照此序列，可以使各个进程逐一满足资源条件，顺利的执行下去。
• 不安全序列：进程们无法获得资源执行完成，此时便进入了不安全状态。
• 并非所有不安全状态都是死锁状态（因为随着时间推移，可能某些占大量资源的进程被阻塞释放资源也说不定啊hhhh），但极可能进入死锁状态。
• 死锁避免最著名的算法：银行家算法

银行家算法

• 本质：得到一个分配资源的安全序列
• 进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则推迟分配；
• 当进程在执行中继续申请资源时，先测试该进程已占用的资源数与本次申请的资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源，若没有超过则再测试系统现存的资源能否满足该进程尚需的最大资源量，若能满足则按当前的申请量分配资源，否则也要推迟分配。
• 数据描述：
  • 可利用资源矢量Available。Available[j]=K，指系统现有Rj类资源K个；
  • 最大需求矩阵Max，n×m矩阵，n个进程中的每个进程对m类资源的最大需求；
  • 分配矩阵Allocation：与Max结构相同，为当前时刻，各进程已拥有的各资源情况；
  • 需求矩阵Need：与Max结构相同，为当前时刻，各进程还需要的各资源情况，关系：Need=Max-Allocation；

	Max(A B C)	T0时刻 Allocation(A B C)	T0时刻 Need(A B C)	T0时刻 Available(A B C)
P0	7 5 3	0 1 0	7 4 3	3 3 2
P1	3 2 2	2 0 0	1 2 2	-
P2	9 0 2	3 0 2	6 0 0	-
P3	2 2 2	2 1 1	0 1 1	-
P4	4 3 3	0 0 2	4 3 1	-

说明：

• 本例原本Available数组{10,5,7}
• 对比Need各行与Available数组，看出P1和P3可以满足条件，所以安全队列可以从P1开始（也可以从P3开始）；
• 资源给了P1，P1完成执行后，Available数组变成了{5,3,2},
• Need矩阵没了P1行，只剩如下：

	Need
P0	7 4 3
P2	6 0 0
P3	0 1 1
P4	4 3 1

• 此Need矩阵跟Available数组比较，继续消行（比如P3和P4均可）
• 依次类推，得到一组安全序列{P1,P3,P4,P2,P0}，事实上不止唯一答案。

死锁检测和解除

推荐阅读：死锁检测和解除1以及死锁检测和解除2

• 从上文博客2介绍利用资源分配图来判断死锁的方式，简述：
  • R1资源有3份，分给P1两份，分给P2一份，此时P2还向R1申请一份，故R1缺一份；
  • R2资源有两份，分给P2一份，此时P1向R2申请一份，故R2完全有能力继续分配给P1；
  • 一边进程P1申请资源R2一份，另一边R2也有空余资源，两位一拍即合，执行进程P1，执行完成后P1变成孤立点，P1的两条入边和一条出边也消去；
  • 继续考虑P2，发现P1释放了资源后，P2的资源申请也能得到满足，P2也开始执行；
  • 综上，该图是可完全简化的。
• 死锁发生：S状态的资源分配图是不可完全简化的（亦称死锁定理）。
• 检测的时机：①进程请求资源得不到满足时（此时检测系统开销太大）；②定时检测；③系统资源利用率下降时检测；
• 死锁解除方法：
  1. 资源剥夺法：挂起某些死锁进程，并抢占它的资源。需要放置被挂起的进程长时间得不到资源，而处于资源匮乏状态。
  2. 撤销进程法：可按照进程优先级和撤销进程代价的原则，强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。
  3. 进程回退法：让一个或多个进程回退到足以避免死锁的地步，进程回退时自愿放弃资源而不是被剥夺，需要系统保持进程的历史信息，设置还原点。