操作系统中的信号量

2020-07-04

概述

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

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

#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操作进行描述，则可如下。

生产者

P(sem-empty)
P(sem-queue)
produce-something()
V(sem-queue)
V(sem-full)

消费者

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代码，一个线程负责计算斐波那契数列（生产），另一个则负责打印（消费）。

#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
...

总结

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

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