1 软件实现方法

1.1.单标志法

基本思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予.

先举个例子：

看完例子，我们看下面的代码：

int turn = 0;		//表示当前允许进入临界区的进程号
P0进程:						P1进程:
while(turn!=0);		①		while(turn!=1);		⑤		//进入区
critical section;	②		critical section;	⑥		//临界区
turn=l;				③		turn=0;				⑦		//退出区
remainder section;	④		remainder section;	⑧		//剩余区
1
2
3
4
5
6

• turn就表示红包，turn=0就是红包在亲戚那；turn=1就是红包在“我”这。P0表示“亲戚”；P1表示“我”。
• 最初turn=0，若此时P1请求资源，将一直停留在步骤⑤，直到P1的时间片用完，发生调度，切换P0上处理机运行。代码①不会卡住P0，P0可以正常访问临界区，在P0访问临界区期间即时切换回P1，P1依然会卡在⑤。只有P0在退出区将turn=1后，P1才能进入临界区。
• 存在问题：假若turn=1，P0只能等待P1进程结束，若P1一直不进入临界区，那么turn将一直等于1，P0进程就无法进入临界区（违背“空闲让进”）
  

1.2. 双标志先检查法

基本思想： 设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比“flag[0]=ture”意味着0号进程P0现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的志flag[i]设为true，之后开始访问临界区。

举个例子：

看完例子，我们看下面的代码：

bool flag=[2];		//表示进入临界区意愿的数组
flag[0]=FALSE;  	
flag[1]=FALSE;		//刚开始设置为两个进程都不想进入临界区

P0进程：					P1进程：
while(flag[1]); 	1		while(flag[0]);		5	//进入区
flag[0]=TRUE;		2		flag {1]=TRUE;		6	//进入区
critical section;	3		critical section; 	7	//临界区
flag[0]=FALSE;		4		flag [1]=FALSE;		8	//退出区
remainder section;			remainder section;		//剩余区
1
2
3
4
5
6
7
8
9
10

• 若按照①⑤②⑥③⑦….的顺序执行，P0和P1将会同时访问临界区。
  

• 双标志先检查法的主要问题是：违反“忙则等待”原则。
  原因在于，进入区的“检查”和“上锁”两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进进程切换。

1.3. 双标志后检查法

算法思想： 双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到
先“上锁”后“检查” 的方法，来避免上述问题。

与双标志先检查法相比较（红色）：

看完例子，我们看下面的代码：

bool flag=[2];		//表示进入临界区意愿的数组
flag[0]=FALSE;  	
flag[1]=FALSE;		//刚开始设置为两个进程都不想进入临界区

P0进程：					P1进程：
flag[0]=TRUE; 		1		flag {1]=TRUE;		5	//进入区
while(flag[1]);		2		while(flag[0]);		6	//进入区
critical section;	3		critical section; 	7	//临界区
flag[0]=FALSE;		4		flag [1]=FALSE;		8	//退出区
remainder section;			remainder section;		//剩余区
1
2
3
4
5
6
7
8
9
10

• 若按照①⑤②⑥….的顺序执行，P0和P1将都无法进入临界区
  

• 双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待”原则，会因各进程都长期无法访问临界资源而产生“饥饿”现象。两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。

1.4. Peterson’s Algorithm

算法思想：结合双标志法、单标志法的思想。利用flag解决了临界资源的互斥访问，利用turn解决了“饥饿”问题。

再来一个例子：

代码：

bool flag[2];		//表示进入临界区意愿的数组，初始值是FALSE
int turn=0;			//表示优先让那个进程进入临界区

P0进程:						P1进程：
flag[0]=TRUE;turn=1;		flag [1] =TRUE; turn=0;				//进入区
while(flag[1]&&turn==1); 	while (flag[0]&&turn==0) ; 			//进入区
critical section;			critical section;					//临界区
flag[0]=FALSE;				flag[1]=FALSE;						//退出区
remainder section;			remainder section;					//剩余区
1
2
3
4
5
6
7
8
9

• Peterson算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则。
• Peterson算法相较于之前三种软件解决方案来说，是最好的，但依然不够好

2 硬件实现方法

通过硬件支持实现临界段问题的方法称为低级方法，或称元方法。

1. 中断屏蔽方法

   关中断；		//防止其他进程进入其临界区的最简方法是关中断。
   临界区；
   开中断；		//若一个进程关中断后不再开中断，则系统可能会因此终止。
   1
   2
   3

   优点： 简单、高效
   缺点： 不适用于多处理机；只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险）

2. TestAndSet指令（硬件）
   这条指令是原子操作，即执行该代码时不允许被中断。其功能是读出指定标志后把该标志设置为真。

   boolean TestAndSet (boolean *lock) {
   	boolean old;
   	old=*lock;
   	*lock=true;
   	return old;
   }
   1
   2
   3
   4
   5
   6

   while TestAndSet(&1ock);
   进程的临界区代码段；
   lock=false;
   进程的其他代码;
   1
   2
   3
   4

   可以为每个临界资源设置一个共享布尔变量lock,表示资源的两种状态：true表示正被占用，初值为false进程在进入临界区之前，利用TestAndSet检查标志lock,若无进程在临界区，则其值为false,可以进入，关闭临界资源，把lock置为true,使任何进程都不能进入临界区；若有进程在临界区，则循环检查，直到进程退出。

3. Swap指令：交换两个值的内容（硬件）

   Swap(boolean boolean *b){
   	boolean temp;
   	Temp=*a;
   	*a=*b;
   	*b=temp;
   }
   1
   2
   3
   4
   5
   6

   key=true;
   while(key!=false)
   Swap(&lock, &key);
   进程的临界区代码段；
   lock=false;
   进程的其他代码；
   key=true;
   1
   2
   3
   4
   5
   6
   7

   用Swap指令可以简单有效地实现互斥，为每个临界资源设置一个共享布尔变量lock,初值为false；在每个进程中再设置一个局部布尔变量key,用于与lock交换信息。在进入临界区前，先利用Swap指令交换lock与key的内容，然后检查key的状态；有进程在临界区时，重复交换和检查过程，直到进程退出。

硬件方法的优点：适用于任意数目的进程，而不管是单处理机还是多处理机；简单、容易验证其正确性。可以支持进程内有多个临界区，只需为每个临界区设立一个布尔变量。
硬件方法的缺点：进程等待进入临界区时要耗费处理机时间，不能实现让权等待。从等待进程中随机选择一个进入临界区，有的进程可能一直选不上，从而导致“饥饿”现象。

参考资料

《王道：23操作系统考研复习指导》