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.

Answer 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.

Answer 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.

Answer 3

It depends on the type of mutex (its backing implementation), some have busy spinning with back-off, others will just sleep the kernel thread object which will then later be woken when the mutex is updated and some are a hybrid of the two (Valve's Source engine uses the hybrid ones). Its characteristics also depend on when and how often it needs to cross kernel/userspace barriers, as sometimes this can be more costly than just spinning a little longer (see this if you want to get more into the spinning vs sleeping side of things).

Mutexes are generally for single thread entry at a time (though they may support recursive entry by the same thread). Semaphores on the other hand allow only n threads at a time to try acquire it (see this MSDN writeup, or this comparative Intel writeup).

Sleeping a thread generally means it gives up its allocation computation timeslice till its ready to be woken and the OS scheduler gives it another time slice. the best examples you are likely to find would actually be in the linux kernel source (or any other open source OS for that matter).

Answer 4

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?

When a thread attempts to acquire a mutex lock, it is stuck and returns only if the lock is granted to that thread. The lock is recognised by OS, so OS knows that till such a lock is available to give thread - it has nothing else to do. The thread is parked inside OS. It is only the OS who knows that now the thread has ownership it goes back to sleep. In a single CPU system, at that very instance if some other process is on, the mutex lock will return only when thread has both - CPU available as well lock granted!

Note: when you do fwrite or select same thing happens. Since OS knows that respective IO will take time, the thread becomes idle. When data arrives, the thread becomes runnable.

1. Same question as 1, but in this case it is semaphore. 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?

In both cases, there are NO busy wait. If any one would busy wait to kill time till you get lock - you have actually failed the purpose of lock! Consider this, let say we have strictly single CPU case (and a stupid OS). So what happens is, thread 1 attempts to acquire lock, since lock lies with thread B so thread A begins to do busy wait. Hence, CPU is never released from thread A and thread B never gets chance to execute on CPU - in the end both threads are in useless situation. Locks doesn't do anything on thread object. But locking process invariably park the threads

Answer 5

Waiting, sleeping, blocking, all mean the same thing:

1. The thread makes a system call (get a mutex or semaphore, wait for some time, whatever)

2. The OS takes control, run the scheduler, marks the thread as waiting for a resource, updates status of other threads as well, then gives control to a thread that is ready to run. If more than one thread is ready to run, one is selected according to scheduling policy.

3. As soon as the resource is made available (through another system call made by another thread), the scheduler updates the status of the former thread from waiting for a resource to ready to run and the thread is given control as soon as the scheduler policy decides so.

As long as the thread is waiting for a resource, it doesn't consume CPU. There is no polling from its part.

Answer 6

In simple words Mutex is for the stuff when you are concerned with 1 lock....semaphore is for multiple locks.. I will try to send you the samples. I remember i had some assignments related to semaphore and mutex in C.. As far as concept is concerned this is something funny here http://geekswithblogs.net/shahed/archive/2006/06/09/81268.aspx :)

Thanks