What does mutex and semaphore actually do?

Question

I want some clarification regarding mutex and semaphore.
My question is,

1. What mutex actually do when a thread tries to enter a region locked by a mutex, a. it waits for the lock to be released? or b. it goes to sleep until the lock is released. In that case how it is wake up again when the lock is released?
2. Same question as 1, but in this case it is semaphore.
3. Can you give me some code regarding busy waiting in pthread in C, and also a case where thread goes to sleep instead of waiting? does sleep mean it is blocked or sleeping is another kind of busy waiting?
4. i want to know some programs where this situations are covered, for example some c source codes where busy waiting, blocking etc are implemented.

Solution 1

When a thread tries to acquire a lock on a mutex, if that mutex is already held then typically it will use a call to the OS kernel to indicate that it is waiting, and then when the thread that currently holds the lock unlocks the mutex then it will make a call to the OS kernel to wake one of the waiting threads.

The same applies to a semaphore, except it only blocks if the count is decremented below zero, and threads are only woken when the count is increased back above zero.

A busy wait is where you don't block or sleep when waiting for something, but repeatedly poll in a loop, so the processor is always busy, but not doing anything useful.

To truly achieve a busy wait, you need an atomic variable, but POSIX threads does not provide such a thing, so you cannot truly write a busy wait in pthreads. The closest you can get is to lock a mutex, read a flag, unlock the mutex, loop if the flag was not set. This repeatedly locks and unlocks the mutex, but does not wait for the data to be ready. In this situation you should use a condition variable instead.

Typically, you say a thread is sleeping if it has called something like usleep to suspend its own execution for a specified period of time. This is as opposed to to blocking, where it is waiting for a specific signal which will be provided by another thread.

Solution 2

Please take a look at: https://stackoverflow.com/a/24582076/3163691

Yes, both mutex and semaphore are synchronizing kernel objects which when a thread tries to acquire one of them, this thread is put to sleep if that object is already owned by other thread.

As you already guessed, this sleeping is a crucial feature because it allows other threads to do more useful work than just 'looping/polling'.

The sleeping of one of these threads ends when the thread who owns the object release it.

[OS Scheduler doesn't give any execution slice to sleeping threads].

Contrast it with a lock & spinlock where a thread is in a 'looping/busy-waiting' state wasting precious CPU time doing almost nothing. Therefore, spinlocks should be avoided in User code. Use a critical section, mutex or semaphore instead!.

As you can see from the above link, both objects are different and should be used in the right context which fits best.

Think of a mutex as a lock which allows just one thread to own it. And that it has many safe attributes (ownership, termination notification, recursion, etc.).

And, think of a semaphore as a lock which allows just a specified number of threads to own it. However, it doesn't have the many useful attributes of a mutex.

Hope this helps.

Comments

[Alok Save]

Semaphore can also be used for a single lock.

[P basak]

Hi I am particularly interested about posix threads implementation in linux C. So, from a posix viewpoint what mutex and semaphore actually does? For example if i write a code in C where some shared data is locked with mutex, when other threads come to access, will it wait? or just blocked releasing its resources? and what will happen in case of semaphore. if the thread is blocking then how spinning and busy waiting is implemented in posix C? Are the condition variables the only way?

[P basak]

Hi, okay then you mean if there is some spinning needed, I have to explicitly implement that busy waiting, i.e. with some variables or condition variables right? I mean mutex and semaphore does not allow threads to wait, right? for example if a semaphore is initialized with 5, then when it is 5, other threads will just be put into sleep by the OS until the semaphore is decreased from 5, and then threads will be waken up by the OS, am I right?

[P basak]

"then it will make a call to the OS kernel to wake one of the waiting threads." then it means threads are actually puts to sleep when waiting for mutex unlock or semaphore value decreased? they are not kept waiting in background for a specific amount of time?

[Anthony Williams]

How it is handled is an implementation detail of the OS, but yes a waiting thread does not typically consume any CPU. It is added to a list of waiting threads by the OS, and only woken when signalled by the mutex being unlocked.

[janneb]

You can achieve busy-waiting using pthreads, that's why there are the pthread_spin_{init,destroy,lock,unlock,trylock} functions.

[P basak]

well I somehow understood. I needed to know the concept of busy waiting in pthread. Now it looks that programmers need to implement busy waiting or spinning on their own. Then it is upto them whether they want to consume cpu resources by introducing busy waiting or not.

[Dipan Mehta]

@Pbasak once the thread gains access of mutex (or if semaphore condition is met), the thread is now runnable - there could be many runnable threads in a system so that depends on other aspects of OS scheduling. Mutex acquisition by itself doesn't control other threads in the system - but your number is now in active queue.

[Tudor]

@P basak, actually there are quite a few libraries out there that provide built-in spin mutexes e.g. TBB.

[Anthony Williams]

The pthread_spin_xxx do not actually guarantee that they perform a busy wait, just that the thread "shall not return from the pthread_spin_lock call" until the lock has been acquired. The intention is clear (it is called a "spin lock"), but it is still a matter of Quality of Implementation.

[Anthony Williams]

Just for completeness: many platforms that offer pthreads also provide atomic operations and spin locks either as a native extension, or through the addition of third-party libraries. The circumstances under which you really want a busy wait are quite specialized though.