当前位置： 首页 > article >正文

进程同步之信号量机制

article 2025/1/15 15:55:02

信号量机制

信号量机制是一种用于进程同步和互斥的基本工具，特别是在并发编程中，广泛用于控制对共享资源的访问，避免数据竞争和死锁等问题。信号量机制由荷兰计算机科学家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;  // 阻塞进程的线程ID
    struct 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();  // 获取当前进程的线程ID
    new_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;  // 请求资源，信号量值减1
    if (S->value < 0) {
        block(S->L);  // 资源不足，进程被阻塞
    }
}

// signal原语
void signal(semaphore *S) {
    S->value = S->value + 1;  // 释放资源，信号量值加1
    if (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是否都大于等于1
    if (S_1.value >= 1 && S_2.value >= 1 && ... && S_n.value >= 1) {
        // 如果所有资源都可用，则将每个资源的value值减1
        for (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加1
    for (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;  // 阻塞进程的线程ID
    struct 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();  // 获取当前进程的线程ID
    new_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值减1
        S_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;  // 阻塞进程的线程ID
    struct 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();  // 获取当前进程的线程ID
    new_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博客


http://www.kler.cn/a/503787.html

相关文章：

  • Grails应用http.server.requests指标数据采集问题排查及解决
  • rknn环境搭建之docker篇
  • 【Rust自学】12.6. 使用TDD(测试驱动开发)开发库功能
  • 二级C语言 2025/1/14
  • NLP三大特征抽取器：CNN、RNN与Transformer全面解析
  • java项目之智慧农贸信息化管理平台(ssm+mybatis+mysql)
  • OJ12:160. 相交链表
  • LangGraph 教程：初学者综合指南（1）
  • Android string.xml中特殊字符转义
  • 项目概述、开发环境搭建（day01）
  • 【Flink】Flink内存管理
  • Word中设计好标题样式后不显示
  • Postman如何Mock Api
  • 解决pycharm中动态/静态出图的设置问题
  • 数据结构------树
  • AWS设计和实现无人机图形显示和控制系统
  • 机器学习（1）：线性回归概念
  • 记录一次FFmpeg的安装过程
  • rtthread学习笔记系列(1) -- 宏
  • k8s故障 ImagePullBackOff状态排错
  • vLLM私有化部署大语言模型LLM
  • 清华大学AutoDroid-V2，软件测试行业将如何发展
  • CMD批处理命令入门（6）——常用的特殊字符
  • android studio根据包名获取当前安装包信息
  • java基础概念55-不可变集合
  • springcloud负载均衡原理