0
$\begingroup$

I was going through the book Operating Systems by Galvin. First they explain Semaphores acting like a mutex.

While talking about semaphores as mutex, they mention that the wait operation of semaphores are always atomic in nature.

This is how a simple snippet of wait would look.

wait()
{
    while(s<=0);
    s-=1;
}

where the value of shared variable s is initially 1.

As we know that a thread or process can be context switched anytime irrespective of anything else. So in the above what if a thread1 context switches after line3 and another thread comes in, it would also find the value of s to be 1. So it wouldn't be waiting in the while condition.

Now to tackle the above situation Galvin says that wait is an atomic operation.

What I don't understand here is how can wait be atomic and how the same is implemented internally? The OS also must be using some similar operation to make a function atomic and if we already have that algorithm which is used by OS then why use semaphores at all?

What are the ways in which a system ensures atomicity?

$\endgroup$

1 Answer 1

2
$\begingroup$

A possible implementation is to have the semaphore counter protected by a spinlock, in order to avoid concurrent accesses (a spinlock manages a lightweight critical section). When the value is found positive, it is decremented and that's it. Otherwise, the process is set in a waiting state and control is passed to the scheduler.

A spinlock works by busy waiting, which must be avoided in general. But in this particular case, the critical section being extremely short, the probability of long stalls is negligible. It takes a processor instruction that performs a read-modify-write atomically (needs to be guaranteed by the hardware interacting with memory, even through caches and in the case of memory shared between multiple processors). For instance, the x86 platform supports an InterlockedIncrement instruction.

https://devblogs.microsoft.com/oldnewthing/20130913-00/?p=3243

$\endgroup$
2
  • $\begingroup$ And wouldnt spinlock need to be protected as well? How does that work exactly? $\endgroup$ Jul 30, 2023 at 7:26
  • $\begingroup$ @Himanshuman: I have added a comment on this. $\endgroup$
    – user16034
    Jul 30, 2023 at 7:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.