概述
信号量是并发编程中的基本概念,由荷兰计算机科学家Dijkstra发明。简单来说,它是一种变量,用于控制多个进程对公共资源的访问。
其中,允许计数任意资源的信号量称为计数信号量,而将值限制为0和1的信号量称为二进制信号量,也就是锁。
POSIX实现
POSIX系统中的信号量采用P/V机制。P/V来自荷兰语缩写,简单来说,P就是减少(如减1),V就是增加(如加1)。
在POSIX中,P就是wait
,V就是post
,含义如下。
wait
:将信号量减1,若结果为负,将其置为阻塞态;post
:将信号量加1,若结果为正,将其置为就绪态;
其中POSIX信号量又分为匿名的和具名的,这里只考虑匿名信号量。
macOS兼容POSIX匿名信号量
由于macOS并没有完全实现标准POSIX信号量,可以使用macOS自带GCP信号量,二者之间可以做一些简单兼容。
如下是匿名信号量的兼容宏定义。
c#ifdef __APPLE__
#include <dispatch/dispatch.h>
typedef dispatch_semaphore_t sem_t;
#define sem_init(sem_p, x, val) *sem_p = dispatch_semaphore_create(val)
#define sem_post(sem_p) dispatch_semaphore_signal(*sem_p)
#define sem_wait(sem_p) dispatch_semaphore_wait(*sem_p, DISPATCH_TIME_FOREVER)
#define sem_destroy(sem_p) dispatch_release(*sem_p)
#else
#include <semaphore.h>
#endif
生产者与消费者
多进程资源竞争问题里面,最经典的是生产者消费者问题。
给定一个长度为n的队列,同时有多个生产者负责生产东西并放到队列里,并且同时也有多个消费者负责消费队列里的东西。
记信号量sem-empty
初始值为n,信号量sem-full
初始值为0,队列信号量sem-queue
初始值为1(锁)。
采用P/V操作进行描述,则可如下。
生产者
lispP(sem-empty) P(sem-queue) produce-something() V(sem-queue) V(sem-full)
消费者
lispP(sem-full) P(sem-queue) consume-something() V(sem-queue) V(sem-empty)
简化的🌰子
考虑我们只有一个生产者和一个消费者,且队列的长度只有一,则队列退化为普通变量。
于是这就成为两进程交替执行的问题。
进程1
lispP(sem-1) do-something() V(sem-2)
进程2
lispP(sem-2) do-something() V(sem-1)
比如说下面这段C代码,一个线程负责计算斐波那契数列(生产),另一个则负责打印(消费)。
c#define MAX 94
static unsigned long long fib_x = 0;
static sem_t mutex_fib;
static sem_t mutex_print;
void *fib()
{
sem_post(&mutex_print);
unsigned long long fib_1 = 1, fib_2 = 1;
for (size_t i = 1; i < MAX; i++)
{
sem_wait(&mutex_fib);
fib_x = i <= 2 ? 1 : fib_1 + fib_2;
fib_1 = fib_2;
fib_2 = fib_x;
sem_post(&mutex_print);
}
return NULL;
}
void *print()
{
for (size_t i = 0; i < MAX; i++)
{
sem_wait(&mutex_print);
printf("fib(%zu) = %llu\n", i + 1, fib_x);
sem_post(&mutex_fib);
}
return NULL;
}
提示:由于unsigned long long
在AMD64系统上最长64位限制,这里只求到第94个斐波那契数。求斐波那契数时采用了动态规划的思想,自底向上求解,时间复杂度O(n)
,空间复杂度O(1)
。
代码中,sem_wait
就是P操作,sem_post
就是V操作。
信号量mutex_print
和mutex_fib
初始值都是0。在fib
线程开始执行时,主动将mutex_print
加1,迫使print
率先执行。之后二者将形成生产/消费关系,交替执行。
执行结果如下所示。
fib(1) = 0
fib(2) = 1
fib(3) = 1
fib(4) = 2
fib(5) = 3
fib(6) = 5
fib(7) = 8
fib(8) = 13
fib(9) = 21
fib(10) = 34
fib(11) = 55
fib(12) = 89
...
总结
信号量是并发编程的基础,用于控制进程对公共资源的访问。
尽管信号量在不同的系统中的使用方式可能不同,但是基本思想都是一致的。
评论
发表评论