Can Race Condition Happen In Semaphore?

Question

Note: My question is still un-answered as the only answer has critical logic flaws and wrong assumptions.

Given the following code (From my digital text book):

Why there is no race condition?

For example in:

sem_wait(&barber_ready) and sem_post(&barber_ready) as we could end updating barber_ready at the same time once +1 and once -1.

This case is probably OK as it is well thought for a book. But generally, it is very dangerous to use several mutexes (or semaphores) for a single operation. The risk is high to have a dead lock in some condition. I would recommend to use a condition variable instead. — prapin, Jul 19 '21 at 20:37
This is the whole big thing about semaphores (as well as other synchronization primitives) - they do not suffer from race conditions when lock/unlock operations are executed on them, even when it happens at exactly the same time. For if they behaved any differently, they would be useless. — SergeyA, Jul 19 '21 at 20:40

score 1 · Accepted Answer · answered Jul 19 '21 at 20:36

1

From the man page on sem_wait:

sem_wait() decrements (locks) the semaphore pointed to by sem. If the semaphore's value is greater than zero, then the decrement proceeds, and the function returns, immediately. If the semaphore currently has the value zero, then the call blocks until either it becomes possible to perform the decrement (i.e., the semaphore value rises above zero), or a signal handler interrupts the call.

Importantly - sem-wait is an atomic function - meaning that it decrements the semaphore's value atomically, avoiding a race condition with sem_post.

So, either sem_post is called before sem_wait and sem_wait returns immediately, or sem_wait is called first and the function blocks until sem_post increments the semaphore's value.

answered Jul 19 '21 at 20:36

Daniel Kleinstein

5,262
1
22
39

But from what I read atomic means it does its job in one command, atomic doesn't mean it won't race condition with others... – Jul 19 '21 at 22:50
Atomic means: "means that there will be no context switch during it - nothing can affect the execution of atomic command." you seem to misunderstand my question. I am not talking about context switch but 2 different threads (each with its own cpu core) This has nothing to do with atomic. – Jul 19 '21 at 22:55
1

Makes no difference. If the synchro fails to operate as a semaphore when run on multiple cores, it is not a semaphore. – Martin James Jul 20 '21 at 02:08
@John I think you misunderstand the word "atomic" - it **does** mean that it won't race condition with others. It's (usually) implemented on top of hardware primitives that prevent two threads from executing the same logic simultaneously. This answer goes into more details - https://stackoverflow.com/questions/15054086/what-does-atomic-mean-in-programming/15054186. – Daniel Kleinstein Jul 20 '21 at 06:18
@DanielKleinstein you are wrong, even if we suppose atomic means what you said`sem-wait` is atomic so other `sem-wait`'s can execute, this has nothing to do with my question as I am referring to a race condition between `sem-wait` and `sem-post` not 2 `sem-wait`'s. – Jul 20 '21 at 22:02
Plus, the answer on the post you linked doesn't mention anything about 2 threads running same code but it mentions: ""An operation acting on shared memory is atomic if it completes in a single step relative to other threads." IDK where you brought this wrong information from – Jul 20 '21 at 22:05
@John Maybe seeing concrete implementations of semaphores will help you understand - have a look [here](https://android.googlesource.com/platform/external/pthreads/+/216eb8153b2455d1e15f8fbf84d4413ddcc40adc/sem_wait.c#124) and [here](https://android.googlesource.com/platform/external/pthreads/+/216eb8153b2455d1e15f8fbf84d4413ddcc40adc/sem_post.c#83) - you can see that both `sem_wait` and `sem_post` access the same underlying mutex in the semaphore - and this access is atomic. This atomic access is what prevents race conditions, because - – Daniel Kleinstein Jul 21 '21 at 11:23
if you have two threads each trying to access the mutex **simultaneously**, one will necessarily complete before the other, and so the semaphore's state is still consistent in each thread. – Daniel Kleinstein Jul 21 '21 at 11:25
If this is still unclear and you still think there's a race condition - can you write down what exactly the race condition is? – Daniel Kleinstein Jul 21 '21 at 11:25
It's clear now thanks, but again this is not related to atomic at all. Atomic means the same command can't be interrupted. Atomic doesn't mean 2 threads can't run same code. – Jul 22 '21 at 11:11

score 0 · Answer 2 · edited Dec 20 '21 at 14:28

now assume that the barber method starts running first:
it'll check if there are any customer is ready it'll find that there is no any customer is ready yet, so it will wait.
now the customer method will run and it'll check the free chairs, and upon to you comment that free_chairs will be initialized to N, so it'll not wait, and then we will increment the customer_ready by one and wake it up (customer_ready), and then we will continue and check if the barber_ready not zero but unfortunately it's zero so we will wait.
and now the schedular will choose the barber method, and the customer_ready we already wake it up when we were on customer method and increment it by one so the value of customer_ready will be zero now and we'll return from wait and continue in the method. now we will post free chairs(for the next iteration) and post barber_ready to one.
now we'll come back to the customer method and we stop on line 13 so we already increment it by line 7, and we will get_hair cut so we finish.
and if you want to try for another iteration, by coming back to the barber method we'll again find that customer_ready is zero again and retry the same scenario.
if you want to trail on another scenario by starting with the customer, starting with line 11 you'll not wait because the number of free chairs is N, so continue, incrementing customer_ready by line 12, and then by (line 13), we'll wait for barber_ready to increment. so coming back to the barber, you'll find the customer_ready is already incremented by line 12, so continue, incrementing free chairs and then incrementing the barber_ready, when we come back to the customer we'll return from waiting(line 13) because we already increment it by line 7 and continue.
these are the two scenarios, and we find why there's no racing here.

Can Race Condition Happen In Semaphore?

2 Answers2