信號量機制
信號量機制是一種用于進程同步和互斥的基本工具,特別是在并發編程中,廣泛用于控制對共享資源的訪問,避免數據競爭和死鎖等問題。信號量機制由荷蘭計算機科學家Edsger Dijkstra在1965年提出,并在操作系統的進程同步中發揮了重要作用。經歷了整型信號量、 記錄型信號量、AND型信號量和信號量集。
1)整型信號量
Dijkstra最初提出的信號量為表示臨界資源的一個整型量S。S>0時表示有S個資源可用;S<=0表示該資源已被分配完。另外,定義了兩個原語wait(S)和signal(S)用于資源的分配和釋放,這兩個原語的C語言偽代碼如下:
?wait(int &S){while (S<=0);S=S-1;}?signal(int &S){S=S+1;}
wait原語(也叫作P操作)首先通過while循環測試是否S<=0,如果是則繼續等待,否則將S的值減1,資源分配成功,可以進入臨界區訪問。 signal原語(也叫做V操作)只有一條語句,即將S值加1,表示釋放1個資源。
示例:使用整型信號量進行互斥控制
// 信號量 S,初始化為1,表示有1個資源
int S = 1;// wait原語(P操作)
void wait(int *S) {while (*S <= 0); *S = *S - 1;
}// signal原語(V操作)
void signal(int *S) {*S = *S + 1;
}// 臨界區函數
void *p1(void *p) {wait(&S); printf("線程1進入臨界區\n");signal(&S); return NULL;
}void *p2(void *p) {wait(&S); printf("線程2進入臨界區\n");signal(&S); return NULL;
}
解釋:
信號量 S:它是一個整型變量,表示可用的資源數量,初始化為1,表示有一個資源可以分配。
wait 操作(P操作): wait操作會檢查信號量S的值。如果 S小于等于0,表示資源不可用,當前線程將進入等待狀態。如果 S 大于0,表示有資源可用,信號量 S會減1,表示資源已被分配給當前線程,線程可以訪問共享資源。
signal操作(V操作): signal操作會釋放一個資源,信號量 S增加1。如果有等待的線程,它們會根據信號量的值重新獲得資源。
線程 p1和 p2: 這兩個線程都訪問共享資源,每個線程在進入臨界區前都調用 wait(S)請求資源,執行完任務后調用 signal(S) 釋放資源。 由于信號量的控制,線程 p1和 p2 會互斥地訪問共享資源。
2.)記錄型信號量
為了解決整型信號量中的“忙等”問題,即當沒有資源可用時,進程不斷等待而不釋放CPU,可以采用記錄型信號量(semaphore)。在這種信號量機制中,我們引入了阻塞進程隊列來管理等待資源的進程。記錄型信號量由一個結構體組成,包含兩個成員:整型變量value
和進程阻塞隊列L
。value
表示當前可用的資源數量,當value > 0
時,表示有可用資源;當value < 0
時,value
的絕對值表示正在等待資源的進程數量。
此外,L
是一個進程隊列,包含那些因無法獲取資源而被阻塞的進程。當資源可用時,這些被阻塞的進程可以被喚醒,繼續執行。因此,記錄型信號量通過引入阻塞隊列來避免了“忙等”,實現了進程的高效調度。
偽代碼如下:
typedef struct{int value;struct process_control_block *L
}semaphore;
//value>O時,value為資源可用數目
//value<O,|value|為已阻塞進程的數目
//L為阻塞進程隊列首指針wait(int &S){S.value = S.value -1;if (S.value<0) block(S.L);
}
//阻塞到隊尾,
//程序計數器定位在Wait之后signal(int &S){S.value = S.value+1;if(S.value<=0) wake(S.L);//喚醒隊首
}
示例:
#include <stdio.h>
#include <pthread.h>typedef struct process_control_block {pthread_t thread; // 阻塞進程的線程IDstruct process_control_block *next; // 指向下一個進程
} PCB;typedef struct {int value; // 信號量的值,表示資源的數量PCB *L; // 阻塞進程隊列的頭指針
} semaphore;semaphore S = {1, NULL}; // 初始化信號量,資源數量為1// 模擬進程被阻塞
void block(PCB *L) {PCB *new_pcb = (PCB *)malloc(sizeof(PCB));new_pcb->thread = pthread_self(); // 獲取當前進程的線程IDnew_pcb->next = NULL;// 將新進程加入到阻塞隊列的尾部if (L == NULL) {L = new_pcb;} else {PCB *temp = L;while (temp->next != NULL) {temp = temp->next;}temp->next = new_pcb;}// 阻塞進程的代碼邏輯printf("進程 %lu 被阻塞。\n", pthread_self());pthread_exit(NULL); // 當前線程掛起
}// 模擬進程被喚醒
void wake(PCB *L) {if (L != NULL) {PCB *temp = L;L = L->next; // 喚醒隊列中的第一個進程printf("進程 %lu 被喚醒。\n", temp->thread);free(temp); // 釋放喚醒的進程}
}// wait原語
void wait(semaphore *S) {S->value = S->value - 1; // 請求資源,信號量值減1if (S->value < 0) {block(S->L); // 資源不足,進程被阻塞}
}// signal原語
void signal(semaphore *S) {S->value = S->value + 1; // 釋放資源,信號量值加1if (S->value <= 0) {wake(S->L); // 喚醒阻塞隊列中的一個進程}
}// 線程函數
void *process(void *param) {printf("進程 %lu 正在嘗試進入臨界區。\n", pthread_self());wait(&S); // 請求資源printf("進程 %lu 已進入臨界區。\n", pthread_self());signal(&S); // 釋放資源return NULL;
}int main() {pthread_t t1, t2;// 創建兩個線程pthread_create(&t1, NULL, process, NULL);pthread_create(&t2, NULL, process, NULL);// 等待線程結束pthread_join(t1, NULL);pthread_join(t2, NULL);return 0;
}
3)AND型信號量
記錄型信號量一次只能申請一種資源,而當一個進程需要同時獲取多種臨界資源時,若資源申請順序不當,很容易導致死鎖的發生。為了解決這個問題,引入了AND信號量,它允許一次申請多種資源,每種資源申請一個單位。只有當所有申請的資源都滿足要求時,才會全部分配,否則一種資源也不會分配。
AND型信號量通過Swait
和Ssignal
兩個原語進行資源的申請和釋放。Swait
的參數為涉及的n種資源的信號量,分別定義為S_1
到S_n
。在Swait
操作中,首先檢查n種資源的可用數量(即信號量的value
)是否都大于或等于1。如果滿足條件,則將所有信號量的value
值減1,表示資源分配成功;如果不滿足條件,則從S_1
到S_n
中查找第一個value
值小于1的信號量S_i
,并將當前進程阻塞到S_i
的阻塞隊列S_i.L
中。此時,程序的計數器將重新定位到Swait
操作的起點,等待資源滿足條件后繼續執行。
偽代碼如下:
// Swait原語:請求多個資源
void Swait(semaphore S_1, semaphore S_2, ..., semaphore S_n) {// 判斷所有信號量的value是否都大于等于1if (S_1.value >= 1 && S_2.value >= 1 && ... && S_n.value >= 1) {// 如果所有資源都可用,則將每個資源的value值減1for (int i = 1; i <= n; i++) {S_i.value = S_i.value - 1;}} else {// 否則,找到第一個不可用的資源for (int i = 1; i <= n && S_i.value >= 1; i++);// 將進程阻塞到第一個不可用資源的阻塞隊列中block(S_i.L);// 程序計數器重新定位到Swait操作的起點,等待資源可用}
}// Ssignal原語:釋放多個資源
void Ssignal(semaphore S_1, semaphore S_2, ..., semaphore S_n) {// 釋放每個資源并將value加1for (int i = 1; i <= n; i++) {S_i.value = S_i.value + 1;// 如果該資源的value小于等于0,表示有阻塞的進程,需要喚醒if (S_i.value <= 0) {wake(S_i.L);}}
}
示例:
#include <stdio.h>
#include <pthread.h>typedef struct process_control_block {pthread_t thread; // 阻塞進程的線程IDstruct process_control_block *next; // 指向下一個進程
} PCB;typedef struct {int value; // 信號量的值,表示資源的數量PCB *L; // 阻塞進程隊列的頭指針
} semaphore;semaphore S1 = {1, NULL}; // 資源1,初始值為1
semaphore S2 = {1, NULL}; // 資源2,初始值為1
semaphore S3 = {1, NULL}; // 資源3,初始值為1// 模擬進程被阻塞
void block(PCB *L) {PCB *new_pcb = (PCB *)malloc(sizeof(PCB));new_pcb->thread = pthread_self(); // 獲取當前進程的線程IDnew_pcb->next = NULL;// 將新進程加入到阻塞隊列的尾部if (L == NULL) {L = new_pcb;} else {PCB *temp = L;while (temp->next != NULL) {temp = temp->next;}temp->next = new_pcb;}// 阻塞進程的代碼邏輯printf("進程 %lu 被阻塞。\n", pthread_self());pthread_exit(NULL); // 當前線程掛起
}// 模擬進程被喚醒
void wake(PCB *L) {if (L != NULL) {PCB *temp = L;L = L->next; // 喚醒隊列中的第一個進程printf("進程 %lu 被喚醒。\n", temp->thread);free(temp); // 釋放喚醒的進程}
}// Swait原語:請求多個資源
void Swait(semaphore *S_1, semaphore *S_2, semaphore *S_3) {if (S_1->value >= 1 && S_2->value >= 1 && S_3->value >= 1) {// 如果所有資源都可用,則將資源的value值減1S_1->value--;S_2->value--;S_3->value--;printf("資源已分配給進程 %lu。\n", pthread_self());} else {// 否則,找到第一個不可用的資源if (S_1->value < 1) {block(S_1->L); // 阻塞進程} else if (S_2->value < 1) {block(S_2->L);} else if (S_3->value < 1) {block(S_3->L);}}
}// Ssignal原語:釋放多個資源
void Ssignal(semaphore *S_1, semaphore *S_2, semaphore *S_3) {S_1->value++;S_2->value++;S_3->value++;printf("資源已被進程 %lu 釋放。\n", pthread_self());// 喚醒被阻塞的進程wake(S_1->L);wake(S_2->L);wake(S_3->L);
}// 線程函數
void *process(void *param) {printf("進程 %lu 正在嘗試請求資源。\n", pthread_self());Swait(&S1, &S2, &S3); // 請求資源printf("進程 %lu 已進入臨界區。\n", pthread_self());Ssignal(&S1, &S2, &S3); // 釋放資源return NULL;
}int main() {pthread_t t1, t2, t3;// 創建三個線程pthread_create(&t1, NULL, process, NULL);pthread_create(&t2, NULL, process, NULL);pthread_create(&t3, NULL, process, NULL);// 等待線程結束pthread_join(t1, NULL);pthread_join(t2, NULL);pthread_join(t3, NULL);return 0;
}
4)信號量集
當一個進程需要申請多種資源,每種資源需要多個單位,并且當資源的可用數量低于設定的下限時,不應進行資源分配。為便于軟件開發,AND型信號量機制進行了擴展,定義了信號量集。
信號量集的資源申請和釋放操作與AND型信號量相似,但參數的構成有所不同。具體來說,Swait
操作的參數包括n種資源信號量S_i
、每種資源的申請數量d_i
以及資源分配的下限t_i
的序列。在Swait
中,首先判斷每種資源的可用數量(即信號量的value
)是否大于或等于對應的下限t_i
,如果滿足條件,則將每種資源的信號量value
減去相應的d_i
,表示分配成功;如果不滿足條件,則檢查所有資源的可用性,直到發現第一個不滿足條件的信號量S_i
,然后將當前進程阻塞到該信號量S_i
的阻塞隊列S_i.L
中。此時,程序的計數器將重新定位到Swait
操作的起點,等待資源滿足條件后繼續執行。
偽代碼如下:
// Swait原語:請求多個資源,指定每種資源的分配下限和申請數量
void Swait(semaphore S_1, int t_1, int d_1, ..., semaphore S_n, int t_n, int d_n) {// 判斷所有信號量的value是否都大于等于對應的分配下限if (S_1.value >= t_1 && S_2.value >= t_2 && ... && S_n.value >= t_n) {// 如果所有資源都滿足分配條件,則將資源的value值減去對應的申請數量for (int i = 1; i <= n; i++) {S_i.value = S_i.value - d_i;}} else {// 否則,找到第一個不滿足資源要求的信號量for (int i = 1; i <= n && S_i.value >= t_i; i++);// 將進程阻塞到不滿足條件的信號量的阻塞隊列中block(S_i.L);// 程序計數器重新定位到Swait操作的起點,等待資源可用}
}// Ssignal原語:釋放多個資源,指定每種資源的釋放數量
void Ssignal(semaphore S_1, int d_1, ..., semaphore S_n, int d_n) {// 釋放每個資源并將value加上對應的釋放數量for (int i = 1; i <= n; i++) {S_i.value = S_i.value + d_i;// 喚醒阻塞隊列中的進程if (S_i.value <= 0) {wake(S_i.L);}}
}
示例:
#include <stdio.h>
#include <pthread.h>typedef struct process_control_block {pthread_t thread; // 阻塞進程的線程IDstruct process_control_block *next; // 指向下一個進程
} PCB;typedef struct {int value; // 信號量的值,表示資源的數量PCB *L; // 阻塞進程隊列的頭指針
} semaphore;semaphore S1 = {5, NULL}; // 資源1,初始值為5
semaphore S2 = {5, NULL}; // 資源2,初始值為5
semaphore S3 = {5, NULL}; // 資源3,初始值為5// 模擬進程被阻塞
void block(PCB *L) {PCB *new_pcb = (PCB *)malloc(sizeof(PCB));new_pcb->thread = pthread_self(); // 獲取當前進程的線程IDnew_pcb->next = NULL;// 將新進程加入到阻塞隊列的尾部if (L == NULL) {L = new_pcb;} else {PCB *temp = L;while (temp->next != NULL) {temp = temp->next;}temp->next = new_pcb;}// 阻塞進程的代碼邏輯printf("進程 %lu 被阻塞。\n", pthread_self());pthread_exit(NULL); // 當前線程掛起
}// 模擬進程被喚醒
void wake(PCB *L) {if (L != NULL) {PCB *temp = L;L = L->next; // 喚醒隊列中的第一個進程printf("進程 %lu 被喚醒。\n", temp->thread);free(temp); // 釋放喚醒的進程}
}// Swait原語:請求多個資源,指定每種資源的分配下限和申請數量
void Swait(semaphore *S_1, int t_1, int d_1, semaphore *S_2, int t_2, int d_2, semaphore *S_3, int t_3, int d_3) {// 判斷所有信號量的value是否都大于等于對應的分配下限if (S_1->value >= t_1 && S_2->value >= t_2 && S_3->value >= t_3) {// 如果所有資源都滿足分配條件,則將資源的value值減去對應的申請數量S_1->value -= d_1;S_2->value -= d_2;S_3->value -= d_3;printf("資源已分配給進程 %lu。\n", pthread_self());} else {// 否則,找到第一個不滿足資源要求的信號量if (S_1->value < t_1) {block(S_1->L); // 阻塞進程} else if (S_2->value < t_2) {block(S_2->L);} else if (S_3->value < t_3) {block(S_3->L);}}
}// Ssignal原語:釋放多個資源,指定每種資源的釋放數量
void Ssignal(semaphore *S_1, int d_1, semaphore *S_2, int d_2, semaphore *S_3, int d_3) {S_1->value += d_1;S_2->value += d_2;S_3->value += d_3;printf("資源已被進程 %lu 釋放。\n", pthread_self());// 喚醒阻塞隊列中的進程wake(S_1->L);wake(S_2->L);wake(S_3->L);
}// 線程函數
void *process(void *param) {printf("進程 %lu 正在嘗試請求資源。\n", pthread_self());Swait(&S1, 2, 1, &S2, 2, 1, &S3, 2, 1); // 請求資源printf("進程 %lu 已進入臨界區。\n", pthread_self());Ssignal(&S1, 1, &S2, 1, &S3, 1); // 釋放資源return NULL;
}int main() {pthread_t t1, t2, t3;// 創建三個線程pthread_create(&t1, NULL, process, NULL);pthread_create(&t2, NULL, process, NULL);pthread_create(&t3, NULL, process, NULL);// 等待線程結束pthread_join(t1, NULL);pthread_join(t2, NULL);pthread_join(t3, NULL);return 0;
}
信號量機制之蘋果-橘子問題-CSDN博客