15

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.
Alok Save
  • 202,538
  • 53
  • 430
  • 533
P basak
  • 4,874
  • 11
  • 40
  • 63
  • Nope, I learnt about busy waiting and blocking mechanisms for thread synchronization. But i am not sure about what mutex and semaphore does. – P basak Feb 24 '12 at 08:15

6 Answers6

13

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.

Anthony Williams
  • 66,628
  • 14
  • 133
  • 155
  • "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? – P basak Feb 24 '12 at 08:31
  • 2
    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. – Anthony Williams Feb 24 '12 at 08:49
  • You can achieve busy-waiting using pthreads, that's why there are the pthread_spin_{init,destroy,lock,unlock,trylock} functions. – janneb Feb 24 '12 at 08:51
  • 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. – P basak Feb 24 '12 at 08:58
  • @P basak, actually there are quite a few libraries out there that provide built-in spin mutexes e.g. TBB. – Tudor Feb 24 '12 at 10:14
  • 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 Feb 24 '12 at 13:52
  • 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. – Anthony Williams Feb 24 '12 at 13:56
7

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.

fante
  • 2,475
  • 1
  • 16
  • 17
0

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

Necrolis
  • 25,836
  • 3
  • 63
  • 101
  • 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 Feb 24 '12 at 08:22
0
  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

Dipan Mehta
  • 2,110
  • 1
  • 17
  • 31
  • 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 Feb 24 '12 at 08:31
  • @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. – Dipan Mehta Feb 24 '12 at 09:50
0

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.

mouviciel
  • 66,855
  • 13
  • 106
  • 140
-1

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

Danyal Sandeelo
  • 1