信号量的标准原子操作

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，那么这意味着我们有一个位置，所以我们减少计数器和 return。请注意，这必须是原子的：我们不能释放二进制信号量并在之后递减计数器，因为这会打开一个 window 的时间，另一个线程可能会错误地看到相同的东西并获得我们在行中的位置同时。因此，二进制信号量用于自动测试计数器并将其递减（如果它大于 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() 的任何调用发生之前初始化二进制信号量。
如问题所述，此实现使用普通机器指令。请注意，它会一直循环直到出现 "place in line"。就像有一个烦人的旅伴反复询问"Are we there yet?"。一点都不好。这被称为轮询，这很糟糕，因为它浪费了 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中，信号量可以容纳的最大值定义为SEM_VALUE_MAX在semaphore.h.

中

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

信号量的标准原子操作

Standard atomic operations of semaphores

c

semaphore