作業系統-信号量

信号量

信号量機制是一種功能較強的機制，可用于解決互斥和同步的問題，它隻能被兩個标準的原語wait(S)和signal(S)通路，也可以記為“P操作”和“V操作”。

原語：指完成某種功能且不被分割，不被中斷執行的操作序列，通常可由硬體來實作。例如TestAndSet和Swap指令就是通過硬體實作的原子操作。原語功能的不被中斷執行特性在單處理機上可由屏蔽中斷方法來實作。

1、整型資訊量

整型信号量被定義為一個表示資源數量的整型量S，wait和signal操作可描述為

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

wait操作中，隻要信号量S<=0，就會不斷地測試。是以，該機制并未遵循“讓權等待”，而是使程序處于忙等狀态。

2、記錄型信号量

記錄型信号是不存在“忙等”現象的程序同步機制。 除需要一個用于代表資源數目的整型變量外，再層架一個程序連結清單L，用于連接配接所有等待該資源的程序。記錄型信号量可描述為

typedef struct ｛
	int value；
	struct process *L;
}semaphore;
           

相應的wait(S)和signal(S)的操作如下:

void wait(semaphore S) {
	S.value--;
	if(S.value < 0) {
		将這個程序P插入等待連結清單隊列S.L;
		block(P);//阻塞程序P
	}
}
void signal(semaphore S) {
	S.value++;
	if(S.value <= 0) {
		将等待連結清單隊列S.L中的一個阻塞程序P移除;
		wakeup(P);//喚醒程序P
	}
}
           

利用記錄型信号量實作同步（先執行x，再執行y）

semaphore S.value = 0;    //初始化信号量
P1() {
	x;    //語句x
	V(S); //告訴程序P2，語句x已經完成
}
P2() {
	P(S); //檢查語句x是否運作完成
	y;    //檢查無誤，運作y語句
}
           

利用記錄型信号量實作互斥

semaphore S.value = 1;
P1() {
	P(S); //準備開始通路臨界資源，加鎖
	程序P1的臨界區
	V(S); //通路結束，解鎖
}
P2() {
	P(S); //準備開始通路臨界資源，加鎖
	程序P2的臨界區
	V(S); //通路結束，解鎖
}
           

利用記錄型信号量實作前驅關系

實作算法如下：

semaphore a.value = 0;
semaphore b.value = 0;
semaphore c.value = 0;
semaphore d.value = 0;
semaphore e.value = 0;
semaphore f.value = 0;
semaphore g.value = 0;
S1(){
	...;
	V(a);V(b);
}
S2(){
	P(a)
	...;
	V(c);V(d);
}
S3(){
	P(b);
	...;
	V(g);
}
S4(){
	P(c);
	...;
	V(e);
}
S5(){
	P(d);
	...;
	V(f);
}
S6(){
	P(e);
	P(f);
	P(g);
	...;
}
           

3、AND型信号量

由信号量實作前驅關系可得，有時需要滿足多個程序之間的同步關系，此時引入AND型信号量就比較友善了。

AND型信号量可描述為

Swait(S1,S2,……Sn) {
	while(true) {
		if(S!.value >=1 && …… && Sn >= 1) {
			for(int i = 1; i <= n; i++) Si.value--;
			break;		
		}
		else {
			找到第一個Si.value < 1,将P程序放進Si的等待連結清單隊列
		}
	}
}
Ssignal(S1,S2,……Sn){
	while(true) {
		for(int i = 1; i <= n; i++) {
			Si++;
			将Si的等待連結清單隊列中某一個程序喚醒，然後把臨界資源配置設定給它
		}
	}
}
           

重點掌握記錄型信号量