🎃Thought Seeds

同步与互斥

Jan 03, 20258 min read

临界区：进程中用于访问临界资源的那段代码

实现临界区互斥的基本方法

实现临界区互斥必须遵循的规则：

  1. 空闲让进
  2. 忙则等待
  3. 有限等待
  4. 让权等待：当进程不能进入临界区时，应立即释放处理器，防止进程忙等待。（非必须）

各种同步方法对比

方法硬件/软件空闲让进忙则等待有限等待让权等待
单标志法软件✓
双标志先检查法软件✓
Peterson软件✓✓✓
中断屏蔽方法硬件
TSL(TestAndSet)硬件✓✓✓
Swap硬件✓✓✓
互斥锁硬件✓✓✓
整型信号量✓✓✓
记录型信号量✓✓✓✓

软件实现方法

单标志法

用一个公共变量 turn 标记允许进入临界区的进程编号

缺点

当 turn==1 时，而进程 又没有进入临界区的意愿，那 turn ==1 就会一直成立，其他进程就永远无法访问临界区。

进程p0:
while (turn != 0);
critical section;
turn = 1;//退出临界区后把turn置为另一个进程的编号
remainder section;
进程p1:
while (turn != 1);
critical section;
turn = 0;
remainder section;

双标志先检查法

设置一个布尔型数组 flag[2], 用来标记各个进程想进入临界区的意愿。该算法先检查对方的标志，再设置自己的标志。

优点

不用交替进入，可以连续使用

缺点

和 可能同时进入临界区，因为检查和设置意愿两个操作不是原子操作

进程p0:
while(flag[1]);//当另一个进程想要进入临界区时，先等待
flag[0] = true;
critical section;
flag[0] = false;
remainder section;
进程p1:
while(flag[0]);//当另一个进程想要进入临界区时，先等待
flag[1] = true;
critical section;
flag[1] = false;
remainder section;

双标志后检查法

设置一个布尔型数组 flag[2], 用来标记各个进程想进入临界区的意愿。该算法先设置自己的标志，再检查对方的标志。

缺点

两个进程可能依次设置自己的标志，并依次检查对方的意愿，于是都卡在检查标志部分。两个进程都无法进入临界区，导致“饥饿”现象。

进程p0:
flag[0] = true;
while(flag[1]);
critical section;
flag[0] = false;
remainder section;
进程p1:
flag[1] = true;
while(flag[0]);
critical section;
flag[1] = false;
remainder section;

Peterson 算法

结合了单标志法和 双标志后检查法，用 flag[]解决互斥访问问题，用 turn 解决“饥饿”问题。

进程p0:
flag[0]=true;
turn=1;
while(flag[1] && turn==1);
critical section;
flag[0]=false;
remainder section;
进程p1:
flag[1]=true;
turn=0;
while(flag[0] && turn==0);
critical section;
flag[1]=false;
remainder section;

硬件实现方法

中断屏蔽方法

缺点
  1. 不能进程切换，系统效率很低
  2. 只适用于内核，不适用于用户进程（因为用户进程没有关中断权限）
  3. 不适用于多处理器系统，因为在一个 CPU 上关中断不影响进程在其他 CPU 上访问临界区
关中断；
critical section;
开中断

硬件指令方法

优点
  1. 简单、容易验证其正确性
  2. 适用于任何数目的进程，支持多处理器系统
  3. 支持系统中有多个临界区，只需为每一个临界区设定一个 lock 变量
缺点
  1. 可能导致“饥饿”
TSL(TestAndSet) 指令
//这条指令是原子操作，所以当一个进程释放锁时，仅有一个进程读取到这个lock==false的状态并重新加锁
boolean TestAndSet(boolean *lock){
	boolean old;
	old = *lock;//保存lock的旧值
	*lock = true;//无论之前是否已经加锁，都把lock置为true
	return old;//返回lock的旧值
}
 
while(TestAndSet(&lock));//加锁并检查
critical section;
lock = false;//解锁
remainder section;
Swap 指令
//这条指令是原子操作
Swap(boolean *a,boolean *b){
	boolean temp = *a;
	*a = *b;
	*b = temp;
}
 
boolean old = true;//old是每个进程的局部变量
while(old) Swap(&lock , &old);
critical section;
lock = false;
remainder section;

互斥锁

//acquire和release都是原子操作
acquire(){
	while(!available);//忙等待
	available = false;//加锁
}
 
release(){
	available = true;//释放锁
}

信号量

整型信号量

整型信号量被定义为一个用于表示资源数目的整型量 S。对 S 有初始化、wait 和 signal 三种操作。

缺点

未实现“让权等待”

wait(S){
	while(S<=0);
	S--;
}
 
signal(S){
	S++;
}

记录型信号量

优点

实现了“让权等待”

typedef struct {
	int value;
	struct process *L;链表L用于链接所有等待该资源的进程
}semaphore;
 
void wait(semaphore S){
	S.value--;
	if(S.value<0){
		add the process to S.L;
		block(S.L);//主动阻塞，由此实现了“让权等待”
	}
}
 
void signal(semaphore S){
	S.value++;
	if(S.value<=0){
		remove a process P from S.L;
		wakeup(P);
	}
}

管程

管程的特性保证了进程互斥，所以不需要程序员自己实现 PV 操作，降低了死锁发生的可能性。

管程由四部分组成

  1. 管程的名称
  2. 局部与管程内部的共享数据结构说明
  3. 对该数据结构进行操作的一组过程
  4. 对局部于管程内部的共享数据设置初始值的语句

每次只允许一个进程使用管程，从而实现进程互斥。若多个进程同时调用 take_away ()，give_back ()，则只有某个进程运行完它的调用后，下一进程才能开始运行它调用的过程。

monitor Demo{//定义一个名为Demo的管程
	共享数据结构 S;
 
	init(){
		S=5;//初始化资源数为5
	}
 
	take_away(){//申请资源
		if(S<=0) x.wait();
		对共享数据结构x的一系列处理；
		S--;
		...;
	}
 
	give_back(){//归还资源
		对共享数据结构x的一系列处理；
		S++;
		...;
		if(有进程在等待) x.signal();//唤醒一个阻塞进程
	}
}

Graph View

Backlinks