计算信号量的用例

Question

需要说明的是:我主要是嵌入式内容,即它是C和微控制器中的某种实时内核; 但实际上这个问题应该与平台无关.

我读过Michael Barr的好文章:Mutexes和Semaphores Demystified,以及StackOverflow上的相关答案.我清楚地理解二进制信号量是什么,以及互斥量是什么.那很棒.

但说实话,我从来不知道,仍然无法理解,所谓的计数信号量(即最大计数> 1的信号量)是为了什么.在什么情况下我应该使用它？

很久以前,在我读过迈克尔·巴尔的上述文章之前,我已经说过" 你可以使用它,就像有一定数量的床的酒店房间一样.床的数量是最大的数量.信号量,就像那个房间的一些按键 ".

这可能听起来很不错,但实际上我的编程练习中从来没有这种情况(并且无法想象),迈克尔巴尔说这种方法是错误的,他似乎是对的.

然后,在我读完这篇文章后,我认为它可能会在我拥有某种FIFO缓冲区时使用.假设缓冲区的容量是10个元素,我们有两个任务:A(生产者)和B(消费者).然后:

• 信号量的最大计数应设置为10;
• 当A想要将数据放入缓冲区时,它signal就是信号量.
• 当B想要从缓冲区获取数据时,它wait就是信号量.

好吧,但它不起作用:

• 如果A试图将新数据放入FIFO,但没有空间怎么办？如何等待这个地方:它应该signal在放入新数据之前调用(signal然后应该能够等到最大计数<最大计数)？如果是这样,信号量将在数据实际放入FIFO之前发出信号,这是错误的.
• 信号量不足以实现正确的同步:FIFO本身也需要同步.然后,它产生经典的TOCTTOU问题:信号量已经发信号或等待时有一段时间,但FIFO尚未修改.

那么,我什么时候应该使用那个野兽,计数信号量呢？

Answer 1

"经典"的例子确实是生产者 - 消费者队列.

无界队列需要一个信号量(计算队列条目)和受互斥锁保护的线程安全队列(或等效的无锁线程安全队列).信号量初始化为零.生产者锁定互斥锁,将对象推入队列,解锁互斥锁并发信号通知信号量.消费者等待信号量,锁定互斥锁,弹出对象并解锁互斥锁.

有界队列需要两个信号量(一个'count'来计算条目,另一个'available'来计算可用空间),以及一个受互斥锁保护的线程安全队列(或等效的无锁线程安全队列) .'count'初始化为零,并且'可用'为空队列中空闲空间的数量.生产者等待"可用",锁定互斥锁,将对象推入队列,解锁互斥锁并发出"计数"信号.消费者等待"计数",锁定互斥锁,弹出对象,解锁互斥锁并发出"可用"信号.

这是信号量的经典用法,并且永远存在,(好吧,自Dijkstra以来,无论如何:).它已被尝试了数十亿次,并且适用于任何数量的生产者/消费者.

没有TOCTTOU问题,没有角落情况,没有比赛.

"互斥"功能可能由另一个信号量提供,初始化为1.这允许"两个信号量"无界,"三个信号量"有界实现.

Answer 2

我认为它可能会在我拥有某种FIFO缓冲区时使用.假设缓冲区的容量是10个元素,我们有两个任务:A(生产者)和B(消费者).然后:

• 信号量的最大计数应设置为10;
• 当A想要将数据放入缓冲区时,它会向信号量发出信号.
• 当B想要从缓冲区获取数据时,它会等待信号量.

这不是信号量在生产者 - 消费者场景中使用的方式.标准解决方案是使用两个计数信号量,一个用于空插槽(初始化为可用插槽的数量),另一个用于填充插槽(初始化为0).

生产者尝试分配空槽以放入项目,因此它们从wait分配给空槽的信号量开始.消费者试图"分配"(获取)已填充的插槽,因此他们从wait分配给已填充插槽的信号量开始.

在完成他们的工作之后,他们都发信号通知另一个信号量,因为他们分别将空位从空白变为填充,从填充变为空.

标准解决方案:

semaphore mutex  = 1;
semaphore filled = 0;
semaphore empty  = SIZE;

producer() {
    while ( true) {
        item = produceItem();
        wait(empty);

        wait(mutex);
        putItemIntoBuffer( item);
        signal(mutex);

        signal(filled);
    }
}

consumer() {
    while ( true) {
        wait( filled);

        wait( mutex);
        item = removeItemFromBuffer();
        signal( mutex);

        signal( empty);
        consumeItem( item);
    }
}

我认为计算信号量在这种情况下很有用.

另一个,也许更简单的例子可能是使用计数信号量来避免在Dining哲学家场景中出现死锁.由于只有当所有哲学家同时坐下并挑选他们的(比如说)左叉时才能发生僵局,因此可以避免死锁,因为他们不允许所有人同时进入餐厅.这可以通过计数信号量(enter)初始化为少于哲学家的数量来实现.

一个哲学家的协议然后成为:

wait( enter)

wait( left_fork)
wait( right_fork)
eat()
signal( left_fork)
signal( right_fork)

signal( enter)

这确保了所有哲学家不能同时进入餐厅.