信号量的标准原子操作

Question

我是自学C,这是信号量的练习题:

回想一下,计数信号量S是一个整数变量,只能通过两个标准原子操作P(探测)和V(信号)来控制,如图所示:

/*The probe or wait operation */

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

/*The signal operation */

V(S) {
    S++;
}

计数信号量的值可以超过不受限制的整数域(即,信号量可以包含任意值),而二进制信号量的值只能是0或1.显示如何仅使用二进制来实现计数信号量信号量和普通(即可抢占)机器指令和数据结构.

为P和V操作提供伪代码.

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

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

展示如何仅使用二进制信号量和普通(即可抢占的)机器指令和数据结构来实现计数信号量.

二进制信号量非常像互斥体(存在一些显着的差异,但出于这个问题的目的,假设它们是等价的),因此您可以实现具有计数器和二进制信号量的数据结构的通用信号量.二进制信号量用于同步对计数器的访问.

信令可以通过获取二进制信号量(即等待信号量),递增计数器然后发信号通知二进制信号量(释放锁定)来实现.

通过重复获取锁(等待二进制信号量),测试计数器是否大于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周期.请记住,在现实世界中,信号量不是这样实现的; 相反,只有当信号量空缺时,进程才会进入休眠状态并且可以运行.

说实话,我不认为你在网上找到的答案是正确的,它似乎没有在柜台或进程队列上进行任何形式的同步.因此,在实现同步原语时,它无法解决其中一个核心问题:显然,它们必须是线程安全的!

这看起来也不正确:

计数信号量的值可以超过不受限制的整数域(也就是说,信号量可以保持任意值)[...]

首先,通用信号量通常不能具有负值,它总是大于或等于0.其次,计数器的值有一个明显的上限; 电脑没有无限的记忆.在Linux中,信号量可以容纳的最大值被定义为SEM_VALUE_MAX在semaphore.h.

所以请注意这些在线教程,其中大部分都是不准确的,缺乏细节,或者只是完全错误.你应该从一本好书中学习.我通常喜欢在UNIX环境中推荐高级编程,虽然它不是专门针对线程的,但是它深入介绍了同步原语.