Standard atomic operations of semaphores

Question

I am self-learning C, and this is a practice problem on semaphores:

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.

I found a related answer to this online:

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;                                            
    }                                                                     
} 

But to be honest, I have no idea what it's trying to do. I would really appreciate it someone could explain the answer, or perhaps demonstrate in pseudo-code on how to answer this.

Answer 1

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

A binary semaphore is pretty much like a mutex (there are some remarkable differences, but for the purposes of this problem assume they are equivalent), and as such you can implement a generic semaphore with a data structure that has a counter and a binary semaphore. The binary semaphore is used to synchronize access to the counter.

Signaling can be implemented by acquiring the binary semaphore (i.e. waiting on the semaphore), incrementing the counter and then signaling the binary semaphore (to release the lock).

Waiting is implemented by repeatedly acquiring the lock (waiting on the binary semaphore), testing if the counter is greater than 0, and releasing the lock. If the counter is indeed greater than 0, then it means we got a place in line, so we decrement the counter and return. Note that this must be atomic: we can't release the binary semaphore and decrement the counter afterwards, since that would open up a window of time where another thread could mistakenly see the same thing and acquire our place in the line at the same time. So, the binary semaphore is used to atomically test the counter and decrement it (if it is greater than 0).

Assume a binary semaphore has type bin_sem_t. Here's some code that illustrates this. The data structure is as follows:

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

Signaling:

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

Waiting:

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);
    }
}

Some important notes:

• The code assumes there is an initialization function that properly sets the counter to 0 and initializes the binary semaphore before any of the calls to either sem_signal() or sem_wait() take place.
• This implementation uses ordinary machine instructions, as the question stated. Note that it keeps looping until there is a "place in line". It's like having an annoying travel companion repeatedly asking "Are we there yet?". Not nice at all. This is known as polling, and it's bad because it wastes CPU cycles. Keep in mind that in the real world semaphores are not implemented like this; instead, processes are put to sleep and made runnable only when the semaphore is vacant.

To be honest, I don't think the answer you found online is correct, it doesn't seem to have any form of synchronization on the counter or on the processes queue. So, it fails to address one of the core concerns when implementing synchronization primitives: obviously, they have to be thread-safe!

This doesn't look right either:

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

First of all, a generic semaphore typically can't have negative values, it is always greater than or equal to 0. Second, there is an obvious upper limit on the value of a counter; computers don't have infinite memory. In Linux, the maximum value a semaphore can hold is defined as SEM_VALUE_MAX in semaphore.h.

So please be careful with these online tutorials, most of them are either inaccurate, lack in detail, or are just plain wrong. You should learn from a good book. I usually like to recommend Advanced Programming in the UNIX Environment, although it is not specifically about threads, but it covers synchronization primitives in great depth.