c - 信号量的标准原子操作

Question

我是自学C，这是一道关于信号量的练习题:

Recall that a counting semaphore S is an integer variable that can only be accused via two standard atomic operations, P (probe) and V (signal), as shown in the figure:

/*The probe or wait operation */

P(S) {
    while(S <= 0); // do nothing
    S--;
}

/*The signal operation */

V(S) {
    S++;
}

The value of a counting semaphore can range over an unrestricted domain of integers (that is, the semaphore can hold an arbitrary value) whereas the value of a binary semaphore can only be 0 or 1. Show how counting semaphores can be implemented using only binary semaphores, and ordinary (that is, preemptible) machine instructions and data structures.

Provide the pseudocode for the P and V operations.

我在网上找到了一个相关的答案:

struct semaphore {                                                        
    int value;                                                            
    queue L; // l list of processes                                       
}                                                                         

wait(S) {                                                                 

    if(s.value > 0){                                                      
        s.value = s.value - 1;                                            
    } else {                                                              
        add this process to S.L;                                          
        block;                                                            
    }                                                                     
}                                                                         

signal(S){                                                                

    if(S.L != EMPTY) {                                                    
        remove a process P from S.L;                                      
        wakeup(P);                                                        
    } else {                                                              
        s.value = s.value + 1;                                            
    }                                                                     
} 

但老实说，我不知道它要做什么。如果有人可以解释答案，或者用伪代码演示如何回答这个问题，我将不胜感激。

Answer 1

Show how counting semaphores can be implemented using only binary semaphores, and ordinary (that is, preemptible) machine instructions and data structures.

二进制信号量与互斥体非常相似(存在一些显着差异，但出于这个问题的目的，假设它们是等价的)，因此您可以使用具有计数器和二进制信号量。二进制信号量用于同步对计数器的访问。

可以通过获取二进制信号量(即等待信号量)、递增计数器然后向二进制信号量发送信号(释放锁)来实现信号发送。

等待是通过反复获取锁(等待二进制信号量)，检测计数器是否大于0，释放锁来实现的。如果计数器确实大于 0，则意味着我们排到了一个位置，因此我们将计数器递减并返回。请注意，这必须是原子的:我们不能释放二进制信号量然后递减计数器，因为这会打开一个时间窗口，另一个线程可能会错误地看到相同的东西并同时获得我们在行中的位置.因此，二进制信号量用于自动测试计数器并递减它(如果它大于 0)。

假设二进制信号量的类型为 bin_sem_t。这是一些说明这一点的代码。数据结构如下:

/* A semaphore implemented with a binary semaphore */
struct semaphore {
    bin_sem_t sem; /* Controls concurrent access to the counter */
    int counter;
};

信令:

void sem_signal(struct semaphore *semaphore) {
    /* We use the binary semaphore to atomically increment the counter */
    wait(semaphore->sem);
    semaphore->counter++;
    signal(semaphore);
}

等待:

void sem_wait(struct semaphore *semaphore) {
    int acquired = 0;
    /* Here we use the binary semaphore to atomically test and
     * decrement the counter
     */
    while (!acquired) {
        wait(semaphore->sem);
        if (semaphore->counter > 0) {
            semaphore->counter--;
            acquired = 1;
        }
        signal(semaphore->sem);
    }
}

一些重要的注意事项:

• 代码假定有一个初始化函数正确地将计数器设置为 0 并在任何调用 sem_signal() 或 sem_wait() 之前初始化二进制信号量> 发生。
• 如问题所述，此实现使用普通机器指令。请注意，它会一直循环，直到有一个“排队的地方”。这就像有一个烦人的旅伴反复问“我们到了吗？”。一点都不好。这称为轮询，它很糟糕，因为它会浪费 CPU 周期。请记住，在现实世界中，信号量并不是这样实现的；相反，只有当信号量为空时，进程才会进入休眠状态并变为可运行状态。

老实说，我不认为你在网上找到的答案是正确的，它似乎在计数器或进程队列上没有任何形式的同步。因此，它未能解决实现同步原语时的核心问题之一:显然，它们必须是线程安全的!

这看起来也不对:

The value of a counting semaphore can range over an unrestricted domain of integers (that is, the semaphore can hold an arbitrary value) [...]

首先，通用信号量通常不能有负值，它总是大于等于0。其次，计数器的值有一个明显的上限；计算机没有无限的内存。在 Linux 中，信号量可以容纳的最大值在 semaphore.h 中定义为 SEM_VALUE_MAX。

所以请小心这些在线教程，它们中的大多数要么不准确，要么缺乏细节，要么完全错误。你应该从一本好书中学习。我通常喜欢推荐 UNIX 环境中的高级编程，虽然它不是专门针对线程的，但它涵盖了很深入的同步原语。