进程同步之信号量机制

信号量机制

信号量机制是一种用于进程同步和互斥的基本工具，特别是在并发编程中，广泛用于控制对共享资源的访问，避免数据竞争和死锁等问题。信号量机制由荷兰计算机科学家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博客