未央的技术岛

操作系统中的信号量

概述

信号量是并发编程中的基本概念,由荷兰计算机科学家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信号量,二者之间可以做一些简单兼容。

如下是匿名信号量的兼容宏定义。

1
2
3
4
5
6
7
8
9
10
11
12
13
#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操作进行描述,则可如下。

生产者

1
2
3
4
5
P(sem-empty)
P(sem-queue)
produce-something()
V(sem-queue)
V(sem-full)

消费者

1
2
3
4
5
P(sem-full)
P(sem-queue)
consume-something()
V(sem-queue)
V(sem-empty)

简化的🌰子

考虑我们只有一个生产者和一个消费者,且队列的长度只有一,则队列退化为普通变量。

于是这就成为两进程交替执行的问题。

进程1

1
2
3
P(sem-1)
do-something()
V(sem-2)

进程2

1
2
3
P(sem-2)
do-something()
V(sem-1)

比如说下面这段C代码,一个线程负责计算斐波那契数列(生产),另一个则负责打印(消费)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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_printmutex_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
...

总结

信号量是并发编程的基础,用于控制进程对公共资源的访问。

尽管信号量在不同的系统中的使用方式可能不同,但是基本思想都是一致的。