Standard atomic semaphore operations
I'm self learning C and this is a practice problem on semaphores:
Recall that the counting semaphore S is an integer variable that can only be blamed 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 counting semaphore value can vary within an unlimited range of integers (i.e. the semaphore can have an arbitrary value), while the binary semaphore value can only be 0 or 1. Show how semaphore counting can be implemented using only binary semaphores and regular (i.e., proactive) machine instructions and data structures.
Provide pseudocode for the P and V operations.
I found the answer to this question on the internet:
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 he is trying to do. I would really appreciate if someone can explain the answer, or perhaps demonstrate in pseudocode how to answer this.
source to share
Show how semaphore counting can be implemented using only binary semaphores and conventional (i.e. preemptive) 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 it is assumed that they are equivalent), and as such you can implement a generic semaphore with a data structure that has a counter and a binary semaphore. A binary semaphore is used to synchronize counter access.
Signaling can be implemented by receiving a binary semaphore (i.e. waiting on a semaphore), incrementing the counter, and then signaling the binary semaphore (to release the lock).
Waiting is implemented by acquiring a lock multiple times (waiting on a binary semaphore), testing if the counter is greater than 0, and releasing the lock. If the counter is indeed greater than 0, then we got a place in the queue, so we decrement the counter and return. Note that this must be atomic: we cannot deallocate the binary semaphore and decrement the counter afterwards, as this will open a window of time where another thread might mistakenly see the same thing and get space in the line at the same time.Thus, a binary semaphore used to atomically test the counter and decrement it (if it is greater than 0).
Suppose the binary semaphore is of type bin_sem_t
. Here's some code that illustrates this. The data structure looks like this:
/* 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);
}
Expectation:
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 correctly sets the counter to 0 and initializes the binary semaphore before any of the calls to
sem_signal()
or occurssem_wait()
. - This implementation uses normal machine instructions as pointed out in this question. Note that it continues to loop until "space in line" appears. It's like an annoying travel companion who keeps asking, "Are we still there?" Nothing good. This is called polling, which is bad because it takes up CPU cycles. Keep in mind that in the real world, semaphores are not implemented like this: instead, processes are put to sleep and only executed when the semaphore is empty.
To be honest, I don't think the answer you found online is correct, it doesn't seem to have any form of on-counter or process queue synchronization. Thus, it cannot solve one of the main problems when implementing synchronization primitives: it is obvious that they must be thread safe!
It doesn't look like this either:
The value of the counting semaphore can vary within an unlimited range of integers (ie, the semaphore can have an arbitrary value) [...]
First of all, a common semaphore usually cannot have negative values, it is always greater than or equal to 0. Second, there is an obvious upper limit on the counter value; computers don't have infinite memory. On Linux, the maximum value a semaphore can store is defined as SEM_VALUE_MAX
in semaphore.h
.
So please be careful with these online tutorials, most of them are either inaccurate, inaccurate, or just plain wrong. You must learn from a good book. I usually like to recommend advanced programming in the UNIX environment, although this is not only about threads, but also covers synchronization primitives at a great depth.
source to share