Semaphores(信号量)

October 16, 2018
编程
操作系统, 同步

Semaphores是一种同步机制（Concurrency Mechanisms），它用来协调各个进程访问公共资源。其基本思想如下所述：

两个或多个进程通过一个信号量进行协调，当一个进程需要某个资源时，它需要申请并等待一个信号，如果信号没有来临则等待。

General Semaphores #

general semaphore的一种实现。

struct semahpore {
    int count;
    queueType queue;
};
void semWait(semaphore a)
{
    s.count--;
    if (s.count < 0) {
        /* place this process in s.queue. */
        /* block this process. */
    }
}
void semSignal(semaphore a)
{
    s.count++;
    if(s.count <= 0) {
        /* remove a process from s.queue. */
        /* place process p on ready list. */
    }
}

  • count的含义

    • 大于0时：指示当前可以加进来的进程数。
    • 小于等于0时：绝对值指示当前想加入还未加入的进程数。

  • 队列里存储的就是等待加入的进程。

Binary Semaphore # 

struct binary_semaphore {
    enum {zero, one} value;
    queueType queue;
};
// B: Binary
void semWaitB(binary_semaphore s)
{
    if (s.value == one)
        s.value = zero;
    else {
        /* place this process in s.queue. */
        /* block this process. */
    }
}
void semSignalB(semaphore s)
{
    if (s.queue is empty())
        s.value = one;
    else {
        /* remove a process P from s.queue. */
        /* place process P on ready list. */
    }
}

优缺点 #

  • 比较难编程，当需要同时使用多个semaphore的时候，需要仔细安排semaphore调用顺序等，否则容易出现死锁。

例子：

/* program producersonsumer */
	semaphore n = 0, s = 1;
	void producer()
    {
        while (true) {
            produce();
            semWait(s);
            append();
            semSignal(s);
            semSignal(n);
        }
    }
	void consumer()
    {
        while(true) {
            semWait(n);
            semWait(s);
            take();
            semSignal(s);
            consume();
        }
	}
	void main()
    {
        parbegin (producer, consumer);
    }
  • 这里 semaphore n 用于防止consumer消耗空buffer，s用于buffer的mutual exclusion。
  • 如果buffer为空，且consumer的 semWait(n); 与 semWait(s); 互换，则第一个semWait能成功进入，但会在第二semWait被阻塞。
  • 这时由于，buffer被consumer占用，producer无法生产新的product加入buffer， semWait(s);将被一直阻塞，产生死锁。
Calendar November 29, 2020