信号量

   操作系统 / 基础 17 分钟读完 (大约2579个字)0次访问

信号量

一、是什么？

信号量本质上是一个计数器，用于控制多进程/线程对共享资源的访问。

  • 在进入一个关键代码段之前，必须先获取一个信号量
  • 一旦该关键代码段完成了，必须释放之前获取的信号量

信号量即可以用于同步（如生产者-消费者），也可以用于互斥（二元信号量）。

二、为什么？

信号量的主要目的是为了在保护共享资源的情况下，对进程/线程进行同步协调。

在并发环境下，需要对共享资源进行保护时，可以考虑用信号量。

三、怎么用？

信号量本身是表示可用资源数量，所以它的取值是一个非负整数。

信号量，除了它的初始化以外，只有2种操作可用：

  • P(S)：如果S的值大于零，就给它减1；如果它的值为零，就挂起该进程
  • V(S)：如果有其他进程因等待S而被挂起，就让它恢复运行；否则就给它加1

并且，需满足以下条件：

  • P(S) 和 V(S) 必须都是不可分割的原子操作

它的功能定义就类似这样：

1
2
3
4
5
6
P (S) {
    while (S <= 0) {
        // process block wait
    }
    S--;
}
1
2
3
4
5
6
7
V (S) {
    if (S has wait process) {
        signal wait process
    } else {
        S++;
    }
}

注：P(S) 和 V(S) 都是原子操作，这里的定义只用于表示它们里面做了什么事。

有了信号量，就能够控制对共享资源的访问了，举个简单的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
semaphore S = 1;

void producer() {
    int item;
    item = produce_item();
    inert_item(item);
    V(S); /* 通知消费者，已放入数据 */
}

void consumer() {
    P(S); /* 消费者必须在此等待生产者放入数据 */
    int item;
    item = remove_item();
    consume_item(item);
}

P(S) 用于等待信号量的可用资源，没有可用资源时，进程将陷入沉睡。

V(S) 用于唤醒在信号量 S 上等待的进程。

另外，P(S) 和 V(S)，也可以用 wait(S) 和 signal(S) 来表示。

四、数据结构？

一般来说，信号量的结构定义可以是这样：

1
2
3
4
typedef struct {
    int value;
    struct process *wait_list;
} semaphore;

其中，value 表示信号量可用资源数量，wait_list 表示在此信号量上等待的进程列表。

对应的 P(S) 和 V(S) 操作定义如下：

1
2
3
4
5
6
7
wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        add this process to S->wait_list;
        block();
    }
}
1
2
3
4
5
6
7
signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        remove a process P from S->wait_list;
        wakeup(P);
    }
}

其中 操作 block() 挂起调用它的进程，操作 wakeup(P) 重新启动阻塞进程 P 的执行。

在这种实现中，信号量的值可以是负数，这和经典的信号量定义是不一样的：

  • 大于0时，表示可用资源数量
  • 等于0时，表示无可用资源，并且没有进程在等待
  • 小于0时，表示无可用资源，但是有进程在等待，其绝对值表示等待的进程数量

这种实现方式在实际的操作系统中比较常见。

五、如何保证原子性？

信号量的操作必须是原子的，否则还是会出现并发问题。

  • 信号量，本身也是一个临界资源，所以可以采用临界区互斥的方式实现原子性

临界区互斥的实现方式有：

  • 单处理器中，采用暂时屏蔽中断的方式，等操作完信号量后再打开
  • 多处理器中，采用硬件指令（TestAndSet 或 Swap）来给信号量加互斥锁访问

比如说，在 linux 系统中，信号量定义是这样的：

1
2
3
4
5
struct semaphore {
    raw_spinlock_t lock;        /* 自旋锁 */
    unsigned int count;         /* 信号量值 */
    struct list_head wait_list; /* 进程等待链表 */
};

在信号量结构中，会带有一个锁变量 lock。

每当对信号量操作时，都需要先对这个 lock 进行互斥加锁，然后才能操作。

比如，P(S) 的实现（在 linux 中是 down()）如下：

1
2
3
4
5
6
7
8
9
10
void down(struct semaphore *sem)
{
    unsigned long flags;
    raw_spin_lock_irqsave(&sem->lock, flags);      /* 自旋等待信号量的锁变量 */
    if (likely(sem->count > 0))
        sem->count--;
    else
        __down(sem);                               /* 如果信号量小于等于0，进入等待队列 */
    raw_spin_unlock_irqrestore(&sem->lock, flags); /* 释放信号量的锁 */
}

这实现代码写得很清晰了：

  • 操作前，首先获取信号量的锁变量，这里是用的自旋锁获取
  • 加锁成功后，再判断信号量的可用资源数
  • 如果可用资源数大于0，则直接减一；否则进入信号量的等待队列
  • 操作完成后，释放信号量的锁

至于  raw_spin_lock_irqsave 自旋锁是如何实现的，实际上就是由更底层的硬件指令来完成的。

比如 TestAndSet 或 Swap 等指令，TestAndSet 指令就类似于这样：

1
2
3
4
5
/* 进入临界区 */
void enter_region(int *lock)
{
    while (TestAndSet(lock));      /* 自旋加互斥锁 */
}

另外，还有一个问题，进入等待队列时都做了啥？具体看一下源码：

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
33
34
35
36
37
38
39
40
static inline int __sched __down_common(struct semaphore *sem, long state, long timeout)
{
    /* 为当前进程创建waiter对象 */
    struct task_struct *task = current;
    struct semaphore_waiter waiter;

    /* 添加到信号量的等待队列 */
    list_add_tail(&waiter.list, &sem->wait_list);
    waiter.task = task;
    waiter.up = false;
 
    for (;;) {
        if (signal_pending_state(state, task))
            goto interrupted;
        if (unlikely(timeout <= 0))
            goto timed_out;
        __set_task_state(task, state);

        /* 在切换到其他进程前，释放信号量的锁 */
        raw_spin_unlock_irq(&sem->lock);

        /* 调度切换进程 */
        timeout = schedule_timeout(timeout);

        /* 重新获取信号量的锁 */
        raw_spin_lock_irq(&sem->lock);

        /* 被V(S)操作唤醒了 */
        if (waiter.up)
            return 0;
    }
 
 timed_out:
    list_del(&waiter.list);
    return -ETIME;
 
 interrupted:
    list_del(&waiter.list);
    return -EINTR;
}

从这里可以看到，进程如果在调用 P(S) 时拿不到资源，就会做几件事：

  • 把当前进程添加到信号量的等待队列
  • 释放信号量的锁，因为当前进程要睡眠了，如果不释放，别的进程就拿不到了
  • 调度切换到其他进程，实际上并没有真正睡眠，而是等待了一段时间

过一段时间后，等待进程再次调度执行时，又会做几件事：

  • 重新获取信号量的锁，不管对信号量做什么，即使只是验证它的值，也要先获取锁
  • 检查自己是不是被别人用 V(S) 唤醒了
  • 如果没有被唤醒，则进入下一轮等待

就这样，一直重复等待，直到拿到信号量的可用资源为止。

总结

信号量是什么？

  • 信号量本质上是一个计数器，用于控制多进程/线程对共享资源的访问
    • 在进入一个关键代码段之前，必须先获取一个信号量
    • 一旦该关键代码段完成了，必须释放之前获取的信号量
  • 信号量即可以用于同步（如生产者-消费者），也可以用于互斥（二元信号量）

为什么要用信号量？

  • 信号量的主要目的是为了在保护共享资源的情况下，对进程/线程进行同步协调
  • 在并发环境下，需要对共享资源进行保护时，可以考虑用信号量

信号量怎么用？

  • 信号量本身是表示可用资源数量，所以它的取值是一个非负整数
  • 信号量，除了它的初始化以外，只有2种操作可用：
    • P(S)：如果S的值大于零，就给它减1；如果它的值为零，就挂起该进程
    • V(S)：如果有其他进程因等待S而被挂起，就让它恢复运行；否则就给它加1
  • P(S) 和 V(S) 必须都是不可分割的原子操作
  • P(S) 和 V(S) 操作，也可以用 wait(S) 和 signal(S) 来表示

信号量的数据结构？

  • 在这种实现中，信号量的值可以是负数，这和经典的信号量定义是不一样的：
    • 大于0时，表示可用资源数量
    • 等于0时，表示无可用资源，并且没有进程在等待
    • 小于0时，表示无可用资源，但是有进程在等待，其绝对值表示等待的进程数量
  • 信号量实现比较灵活，但是正数始终表示可用资源数

信号量的原子性保证？

  • 信号量，本身也是一个临界资源，所以可以采用临界区互斥的方式实现原子性
    • 单处理器中，采用暂时屏蔽中断的方式，等操作完信号量后再打开
    • 多处理器中，采用硬件指令（TestAndSet 或 Swap）来给信号量加互斥锁访问
  • 在 linux 系统中，信号量采用的是锁变量法来互斥访问信号量
    • 信号量结构中自带有一个锁变量
    • 使用自旋锁来给锁变量加锁
    • 自旋锁底层实际上是用的硬件指令实现
  • 进入等待队列时都做了什么？以 linux 系统为例：
    • 把当前进程添加到信号量的等待队列
    • 释放信号量的锁，因为当前进程要睡眠了，如果不释放，别的进程就拿不到了
    • 调度切换到其他进程，实际上并没有真正睡眠，而是等待了一段时间
  • 一段时间后，进程再次被调度执行时：
    • 重新获取信号量的锁，不管对信号量做什么，即使只是验证它的值，也要先获取锁
    • 检查自己是不是被别人用 V(S) 唤醒了
    • 如果没有被唤醒，则进入下一轮等待

信号量

http://example.com/operating_system/basic/semaphore/

作者

jiaduo

发布于

2022-04-09

更新于

2023-07-16

许可协议

 

目录

×