What is the difference between lock, mutex and semaphore?

Question

I've heard these words related to concurrent programming, but what's the difference between lock, mutex and semaphore?

Cordi

ans;https://mcmap.net/q/15500/-difference-between-binary-semaphore-and-mutex – Lamere

The best explanation I have ever seen: crystal.uta.edu/~ylei/cse6324/data/semaphore.pdf – Turbofan

Possible duplicate of Difference between binary semaphore and mutex – Tenorrhaphy

Answer 1

A lock allows only one thread to enter the part that's locked and the lock is not shared with any other processes.

A mutex is the same as a lock but it can be system wide (shared by multiple processes).

A semaphore does the same as a mutex but allows x number of threads to enter, this can be used for example to limit the number of cpu, io or ram intensive tasks running at the same time.

For a more detailed post about the differences between mutex and semaphore read here.

You also have read/write locks that allows either unlimited number of readers or 1 writer at any given time.

The descriptions are from a .NET perspective and might not be 100% accurate for all OS/Languages.

Corroboration

@mertinan i can't say i ever heard about it, but this is what wikipedia says "Latch (database), (a relatively short-lived) lock on a system data-structure like an index" – Corroboration

Monitor allows to wait for a certain condition (e.g. when lock is released), "monitors". – Faught

@DzmitryLazerka while that is true its not the entire truth, the Enter method doesn't just monitor it also takes a lock, also if you look at the TryEnter methods they don't wait.. – Corroboration

@Petoj Right, there are many nuances (the same in Java). I'm just stating the difference between monitor and lock. Monitors has feature to wait until lock is released. – Faught

Monitor also have PulseOne and PulseAll (C#), and there is SemaphoreSlim (lightweight version) which has AwaitAsync :-) – Arturo

A semaphore is not the same as a mutex. They are used very differently and also have different properties (namely regarding ownership). See for example barrgroup.com/Embedded-Systems/How-To/RTOS-Mutex-Semaphore for details – Melioration

@Melioration feel free to edit my answer if you feel that it is misleading or incorrect. – Corroboration

I always thought that locks and mutexes were the same exact thing. By system-wide you mean that mutexes are handled by the operating system and can be used for sharing resources across processes while simple locks can be implemented without OS calls? Does this mean that when someone say mutex they are always referencing the OS handled one? Also a simple explanation of how monitors and semaphores work would also be pretty good for this question. – Decapitate

@Decapitate i have no idea how they are handled i only use them not implement them and my view is from a .net and windows standpoint.. so i can't guarantee that they work the same way in different OS'es or languages. – Corroboration

Stupid question, but how does a semaphore allow X number of threads to enter? – Sisson

@Kapil in a windows environment they can, msdn.microsoft.com/en-us/library/windows/desktop/… You can use a mutex object to protect a shared resource from simultaneous access by multiple threads or processes. – Corroboration

For a clearer distinction between mutex and semaphore, in nanoquack's link, The key paragraph is "The correct use of a semaphore is for signaling from one task to another. A mutex is meant to be taken and released, always in that order, by each task that uses the shared resource it protects. By contrast, tasks that use semaphores either signal or wait—not both." – Endoenzyme

@Endoenzyme Well that makes sense, what i never have understood is when do i want a semaphore to count to more than 1 (binary), the only idea i can come up with is if you have multiple mutexes, you could use the semaphore to wait but once you get the signal you would have to try all mutexes anyway? – Corroboration

I was surprised that the answer which is wrong is the most upvoted one.. please remove your answer for other people not to confuse about mutex and semaphore. – Victorious

@david the answer might get the semaphore part wrong, but the rest is not wrong? Seems overkill to remove it? Why not flag it as incorrect or even better edit it and make it correct? This is a community without community help this place would not exist! – Corroboration

@Corroboration Agree we shouldn't remove the answer. Do you plan on editing the part about the semaphore? I can go ahead and try to edit it if you don't plan on it. – Trimerous

@Trimerous I have no idea how to use a semaphore correctly, so please go ahead and edit to your hearts content! – Corroboration

If only one thread can use a lock, what is the difference in behavior if the lock was not present? – Complexion

@Complexion If you use a lock only one thread can run the locked code at a time. If you don't use a lock multiple threads can run the code at the same time. If you for example modify a data structure from multiple threads at the same time it could result in undefined behavior (corrupt data, crash, security issues, hard to recreate bugs, reading stale data and so on). – Corroboration

@Corroboration my question was in the context of the answer which says there's a difference between locks and mutates. Though looking at this again, I think it seems to draw a line between threads and processes, which I suppose is a technically a distinction though I'm not sure I agree. I think the distinction is only the case for a specific set of primitives offered by a specific OS or programming language versus being a general definition of a lock. – Complexion

@Complexion the definitions i have written are from a .net context so yes they might not be 100% correct in all environments, in case you think something is wrong please use the suggest edit function and i will happily accept the change! – Corroboration

Often, a mutex is a type of lock, so I was confused that there being a distinction. Now that you've mentioned the context, it makes sense and your previous comment helped me understand that you were drawing a distinction between threads and processes. If there's an edit suggestion - maybe mentioning that your definitions are from the context of .NET. – Complexion

I think the confusion comes from the question itself. It asks for "lock, mutex and semaphore?". But the term Lock is used (only?) in .NET and is just syntactic sugar for Monitor. So a better question would be "monitor, mutex and semaphore?". mutex and semaphore are low level operations offered by an operating system. A Monitor is an object offered by a framework like .NET for C#. It can only be "entered" by one thread within your app. How to define a monitor will vary by framework. The irony: the .NET Monitor.Enter/Exit aka .Net Lock is not really what a textbook would describe as Monitor. – Boleslaw

Answer 2

There are a lot of misconceptions regarding these words.

This is from a previous post (https://mcmap.net/q/15503/-difference-between-mutex-semaphore-amp-spin-locks) which fits superb here:

1) Critical Section= User object used for allowing the execution of just one active thread from many others within one process. The other non selected threads (@ acquiring this object) are put to sleep.

[No interprocess capability, very primitive object].

2) Mutex Semaphore (aka Mutex)= Kernel object used for allowing the execution of just one active thread from many others, among different processes. The other non selected threads (@ acquiring this object) are put to sleep. This object supports thread ownership, thread termination notification, recursion (multiple 'acquire' calls from same thread) and 'priority inversion avoidance'.

[Interprocess capability, very safe to use, a kind of 'high level' synchronization object].

3) Counting Semaphore (aka Semaphore)= Kernel object used for allowing the execution of a group of active threads from many others. The other non selected threads (@ acquiring this object) are put to sleep.

[Interprocess capability however not very safe to use because it lacks following 'mutex' attributes: thread termination notification, recursion?, 'priority inversion avoidance'?, etc].

4) And now, talking about 'spinlocks', first some definitions:

Critical Region= A region of memory shared by 2 or more processes.

Lock= A variable whose value allows or denies the entrance to a 'critical region'. (It could be implemented as a simple 'boolean flag').

Busy waiting= Continuosly testing of a variable until some value appears.

Finally:

Spin-lock (aka Spinlock)= A lock which uses busy waiting. (The acquiring of the lock is made by xchg or similar atomic operations).

[No thread sleeping, mostly used at kernel level only. Ineffcient for User level code].

As a last comment, I am not sure but I can bet you some big bucks that the above first 3 synchronizing objects (#1, #2 and #3) make use of this simple beast (#4) as part of their implementation.

Have a good day!.

References:

-Real-Time Concepts for Embedded Systems by Qing Li with Caroline Yao (CMP Books).

-Modern Operating Systems (3rd) by Andrew Tanenbaum (Pearson Education International).

-Programming Applications for Microsoft Windows (4th) by Jeffrey Richter (Microsoft Programming Series).

Also, you can take a look at look at: https://mcmap.net/q/15504/-what-does-mutex-and-semaphore-actually-do

Apex

Actually critical section is not a kernel object, thus more lightweight and incapable of synchronizing across processes. – Gospel

@ Vladislavs Burakovs: You are right! Forgive my redaction. I'll fix it for the sake of coherence. – Apex

For a clearer distinction between mutex and semaphore, as nanoquack mentions elsewhere, see barrgroup.com/Embedded-Systems/How-To/RTOS-Mutex-Semaphore - The key paragraph is "The correct use of a semaphore is for signaling from one task to another. A mutex is meant to be taken and released, always in that order, by each task that uses the shared resource it protects. By contrast, tasks that use semaphores either signal or wait—not both." – Endoenzyme

Re conjecture other lock mechanisms build on [inefficient] spinlock: unlikely; AFAIK only need some atomic operations plus sleep queues. Even where spinlock is needed inside kernel, modern solutions minimize its impact as described in Wikipedia - Spinlock - Alternatives - ".. use a hybrid approach called "adaptive mutex". The idea is to use a spinlock when trying to access a resource locked by a currently-running thread, but to sleep if the thread is not currently running. (The latter is always the case on single-processor systems.)" – Endoenzyme

@ToolmakerSteve, I dare you to provide a 'solution' without a 'spinlock' for the problem of 'collisions' at trying to 'insert' a thread ID to a 'sleep queue'. Anyway, the Wikipedia text concludes that a spinlock is used at the implementation!!!. – Apex

@fante, The Wikipedia text does not say nor imply that spinlock is used as part of these other concurrency mechanisms. [Unfortunately, it is silent on that topic - it doesn't clarify when spinlock is used;] Nor was I saying that spinlock is never needed. I conjectured that it isn't needed, to implement either mutex nor semaphore - however this answer clarifies that spinlock is part of an efficient "hybrid" implementation of mutex on multi-core CPUs; so I was wrong. [I presume one should never spinlock in app code, call kernel funcs.] – Endoenzyme

@Apex ... I mean, in app code, call some existing kernel function that has the low-level knowledge to decide whether to spinlock or not. E.g. as far as app code is concerned, it is a lock, a mutex, a semaphore, or use interchange instructions. If circumstances are right to spinlock for a brief while, to see if another cpu core releases a mutex or semaphore, then let kernel do so. – Endoenzyme

A "critical section" in general is actually the piece of code that accesses a shared resource and must do so in an atomic manner. Now there are also "critical section objects" in Windows which are light weight mutexes that can be used only in the same process. They allow more efficient implementation of critical sections then mutex objects, because no kernel transition happens unless there is contention. – Chloride

Answer 3

Most problems can be solved using (i) just locks, (ii) just semaphores, ..., or (iii) a combination of both! As you may have discovered, they're very similar: both prevent race conditions, both have acquire()/release() operations, both cause zero or more threads to become blocked/suspended... Really, the crucial difference lies solely on how they lock and unlock.

• A lock (or mutex) has two states (0 or 1). It can be either unlocked or locked. They're often used to ensure only one thread enters a critical section at a time.
• A semaphore has many states (0, 1, 2, ...). It can be locked (state 0) or unlocked (states 1, 2, 3, ...). One or more semaphores are often used together to ensure that only one thread enters a critical section precisely when the number of units of some resource has/hasn't reached a particular value (either via counting down to that value or counting up to that value).

For both locks/semaphores, trying to call acquire() while the primitive is in state 0 causes the invoking thread to be suspended. For locks - attempts to acquire the lock is in state 1 are successful. For semaphores - attempts to acquire the lock in states {1, 2, 3, ...} are successful.

For locks in state state 0, if same thread that had previously called acquire(), now calls release, then the release is successful. If a different thread tried this -- it is down to the implementation/library as to what happens (usually the attempt ignored or an error is thrown). For semaphores in state 0, any thread can call release and it will be successful (regardless of which thread previous used acquire to put the semaphore in state 0).

From the preceding discussion, we can see that locks have a notion of an owner (the sole thread that can call release is the owner), whereas semaphores do not have an owner (any thread can call release on a semaphore).

---

What causes a lot of confusion is that, in practice they are many variations of this high-level definition.

Important variations to consider:

• What should the acquire()/release() be called? -- [Varies massively]
• Does your lock/semaphore use a "queue" or a "set" to remember the threads waiting?
• Can your lock/semaphore be shared with threads of other processes?
• Is your lock "reentrant"? -- [Usually yes].
• Is your lock "blocking/non-blocking"? -- [Normally non-blocking are used as blocking locks (aka spin-locks) cause busy waiting].
• How do you ensure the operations are "atomic"?

These depends on your book / lecturer / language / library / environment.
Here's a quick tour noting how some languages answer these details.

---

C, C++ (pthreads)

• A mutex is implemented via pthread_mutex_t. By default, they can't be shared with any other processes (PTHREAD_PROCESS_PRIVATE), however mutex's have an attribute called pshared. When set, so the mutex is shared between processes (PTHREAD_PROCESS_SHARED).
• A lock is the same thing as a mutex.
• A semaphore is implemented via sem_t. Similar to mutexes, semaphores can be shared between threasds of many processes or kept private to the threads of one single process. This depends on the pshared argument provided to sem_init.

python (threading.py)

• A lock (threading.RLock) is mostly the same as C/C++ pthread_mutex_ts. Both are both reentrant. This means they may only be unlocked by the same thread that locked it. It is the case that sem_t semaphores, threading.Semaphore semaphores and theading.Lock locks are not reentrant -- for it is the case any thread can perform unlock the lock / down the semaphore.
• A mutex is the same as a lock (the term is not used often in python).
• A semaphore (threading.Semaphore) is mostly the same as sem_t. Although with sem_t, a queue of thread ids is used to remember the order in which threads became blocked when attempting to lock it while it is locked. When a thread unlocks a semaphore, the first thread in the queue (if there is one) is chosen to be the new owner. The thread identifier is taken off the queue and the semaphore becomes locked again. However, with threading.Semaphore, a set is used instead of a queue, so the order in which threads became blocked is not stored -- any thread in the set may be chosen to be the next owner.

Java (java.util.concurrent)

• A lock (java.util.concurrent.ReentrantLock) is mostly the same as C/C++ pthread_mutex_t's, and Python's threading.RLock in that it also implements a reentrant lock. Sharing locks between processes is harder in Java because of the JVM acting as an intermediary. If a thread tries to unlock a lock it doesn't own, an IllegalMonitorStateException is thrown.
• A mutex is the same as a lock (the term is not used often in Java).
• A semaphore (java.util.concurrent.Semaphore) is mostly the same as sem_t and threading.Semaphore. The constructor for Java semaphores accept a fairness boolean parameter that control whether to use a set (false) or a queue (true) for storing the waiting threads.

---

In theory, semaphores are often discussed, but in practice, semaphores aren't used so much. A semaphore only hold the state of one integer, so often it's rather inflexible and many are needed at once -- causing difficulty in understanding code. Also, the fact that any thread can release a semaphore is sometimes undesired. More object-oriented / higher-level synchronization primitives / abstractions such as "condition variables" and "monitors" are used instead.

Rotenone

Definitively the most thorough answer. It would be helpful to have examples. For example can a semaphore lock customer master file for reading shared, or lock everyone out for nightly updates? Can a semaphore lock a customer number for exclusive update, or lock customer number for shared reading? etc. Or should applications create their own semaphore file and not use system semaphores? – Volumeter

"the fact that any thread can release a semaphore is sometimes undesired" The fact that a different thread will decrement a semaphore is the defining characteristic of a semaphore. It's what distinguishes a semaphore from a mutex/lock. – Bravado

A mutex is the same as a lock (the term is not used often in Java) - That's the point that tons of articles did not explain well – Partition

Answer 4

Take a look at Multithreading Tutorial by John Kopplin.

In the section Synchronization Between Threads, he explain the differences among event, lock, mutex, semaphore, waitable timer

A mutex can be owned by only one thread at a time, enabling threads to coordinate mutually exclusive access to a shared resource

Critical section objects provide synchronization similar to that provided by mutex objects, except that critical section objects can be used only by the threads of a single process

Another difference between a mutex and a critical section is that if the critical section object is currently owned by another thread, EnterCriticalSection() waits indefinitely for ownership whereas WaitForSingleObject(), which is used with a mutex, allows you to specify a timeout

A semaphore maintains a count between zero and some maximum value, limiting the number of threads that are simultaneously accessing a shared resource.

Algo

Answer 5

I will try to cover it with examples:

Lock: One example where you would use lock would be a shared dictionary into which items (that must have unique keys) are added.
The lock would ensure that one thread does not enter the mechanism of code that is checking for item being in dictionary while another thread (that is in the critical section) already has passed this check and is adding the item. If another thread tries to enter a locked code, it will wait (be blocked) until the object is released.

private static readonly Object obj = new Object();

lock (obj) //after object is locked no thread can come in and insert item into dictionary on a different thread right before other thread passed the check...
{
    if (!sharedDict.ContainsKey(key))
    {
        sharedDict.Add(item);
    }
}

Semaphore: Let's say you have a pool of connections, then an single thread might reserve one element in the pool by waiting for the semaphore to get a connection. It then uses the connection and when work is done releases the connection by releasing the semaphore.

Code example that I love is one of bouncer given by @Patric - here it goes:

using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;

namespace TheNightclub
{
    public class Program
    {
        public static Semaphore Bouncer { get; set; }

        public static void Main(string[] args)
        {
            // Create the semaphore with 3 slots, where 3 are available.
            Bouncer = new Semaphore(3, 3);

            // Open the nightclub.
            OpenNightclub();
        }

        public static void OpenNightclub()
        {
            for (int i = 1; i <= 50; i++)
            {
                // Let each guest enter on an own thread.
                Thread thread = new Thread(new ParameterizedThreadStart(Guest));
                thread.Start(i);
            }
        }

        public static void Guest(object args)
        {
            // Wait to enter the nightclub (a semaphore to be released).
            Console.WriteLine("Guest {0} is waiting to entering nightclub.", args);
            Bouncer.WaitOne();          

            // Do some dancing.
            Console.WriteLine("Guest {0} is doing some dancing.", args);
            Thread.Sleep(500);

            // Let one guest out (release one semaphore).
            Console.WriteLine("Guest {0} is leaving the nightclub.", args);
            Bouncer.Release(1);
        }
    }
}

Mutex It is pretty much Semaphore(1,1) and often used globally (application wide otherwise arguably lock is more appropriate). One would use global Mutex when deleting node from a globally accessible list (last thing you want another thread to do something while you are deleting the node). When you acquire Mutex if different thread tries to acquire the same Mutex it will be put to sleep till SAME thread that acquired the Mutex releases it.

Good example on creating global mutex is by @deepee

class SingleGlobalInstance : IDisposable
{
    public bool hasHandle = false;
    Mutex mutex;

    private void InitMutex()
    {
        string appGuid = ((GuidAttribute)Assembly.GetExecutingAssembly().GetCustomAttributes(typeof(GuidAttribute), false).GetValue(0)).Value.ToString();
        string mutexId = string.Format("Global\\{{{0}}}", appGuid);
        mutex = new Mutex(false, mutexId);

        var allowEveryoneRule = new MutexAccessRule(new SecurityIdentifier(WellKnownSidType.WorldSid, null), MutexRights.FullControl, AccessControlType.Allow);
        var securitySettings = new MutexSecurity();
        securitySettings.AddAccessRule(allowEveryoneRule);
        mutex.SetAccessControl(securitySettings);
    }

    public SingleGlobalInstance(int timeOut)
    {
        InitMutex();
        try
        {
            if(timeOut < 0)
                hasHandle = mutex.WaitOne(Timeout.Infinite, false);
            else
                hasHandle = mutex.WaitOne(timeOut, false);

            if (hasHandle == false)
                throw new TimeoutException("Timeout waiting for exclusive access on SingleInstance");
        }
        catch (AbandonedMutexException)
        {
            hasHandle = true;
        }
    }


    public void Dispose()
    {
        if (mutex != null)
        {
            if (hasHandle)
                mutex.ReleaseMutex();
            mutex.Dispose();
        }
    }
}

then use like:

using (new SingleGlobalInstance(1000)) //1000ms timeout on global lock
{
    //Only 1 of these runs at a time
    GlobalNodeList.Remove(node)
}

Hope this saves you some time.

Tonsorial

Answer 6

Wikipedia has a great section on the differences between Semaphores and Mutexes:

A mutex is essentially the same thing as a binary semaphore and sometimes uses the same basic implementation. The differences between them are:

Mutexes have a concept of an owner, which is the process that locked the mutex. Only the process that locked the mutex can unlock it. In contrast, a semaphore has no concept of an owner. Any process can unlock a semaphore.

Unlike semaphores, mutexes provide priority inversion safety. Since the mutex knows its current owner, it is possible to promote the priority of the owner whenever a higher-priority task starts waiting on the mutex.

Mutexes also provide deletion safety, where the process holding the mutex cannot be accidentally deleted. Semaphores do not provide this.

Galway

Answer 7

My understanding is that a mutex is only for use within a single process, but across its many threads, whereas a semaphore may be used across multiple processes, and across their corresponding sets of threads.

Also, a mutex is binary (it's either locked or unlocked), whereas a semaphore has a notion of counting, or a queue of more than one lock and unlock requests.

Could someone verify my explanation? I'm speaking in the context of Linux, specifically Red Hat Enterprise Linux (RHEL) version 6, which uses kernel 2.6.32.

Darlington

Now this might be different in different operating systems but in windows a Mutex can be used by multiple processes at least the .net Mutex object.. – Corroboration

stackoverflow.com/questions/9389730/… "Threads within the same process or within other processes can share mutexes." so no a mutex must not be process specific. – Corroboration

Answer 8

Using C programming on a Linux variant as a base case for examples.

Lock:

• Usually a very simple construct binary in operation either locked or unlocked

• No concept of thread ownership, priority, sequencing etc.

• Usually a spin lock where the thread continuously checks for the locks availability.

• Usually relies on atomic operations e.g. Test-and-set, compare-and-swap, fetch-and-add etc.

• Usually requires hardware support for atomic operation.

File Locks:

• Usually used to coordinate access to a file via multiple processes.

• Multiple processes can hold the read lock however when any single process holds the write lock no other process is allowed to acquire a read or write lock.

• Example : flock, fcntl etc..

Mutex:

• Mutex function calls usually work in kernel space and result in system calls.

• It uses the concept of ownership. Only the thread that currently holds the mutex can unlock it.

• Mutex is not recursive (Exception: PTHREAD_MUTEX_RECURSIVE).

• Usually used in Association with Condition Variables and passed as arguments to e.g. pthread_cond_signal, pthread_cond_wait etc.

• Some UNIX systems allow mutex to be used by multiple processes although this may not be enforced on all systems.

Semaphore:

• This is a kernel maintained integer whose values is not allowed to fall below zero.

• It can be used to synchronize processes.

• The value of the semaphore may be set to a value greater than 1 in which case the value usually indicates the number of resources available.

• A semaphore whose value is restricted to 1 and 0 is referred to as a binary semaphore.

Tiphani

Answer 9

lock, mutex, semaphore

It is a general vision. Details are depended on real language realisation

lock - thread synchronization tool. When thread get a lock it becomes a single thread which is able to execute a block of code. All others thread are blocked. Only thread which owns the lock can unlock it

mutex - mutual exclusion lock. It is a kind of lock. On some languages it is inter-process mechanism, on some languages it is a synonym of lock. For example Java uses lock in synchronised and java.util.concurrent.locks.Lock

semaphore - allows a number of threads to access a shared resource. You can find that mutex also can be implemented by semaphore. It is a standalone object which manage an access to shared resource. You can find that any thread can signal and unblock. Also it is used for signalling

[iOS lock, mutex, semaphore]

Aberration

Answer 10

Supporting ownership, maximum number of processes share lock and the maximum number of allowed processes/threads in critical section are three major factors that determine the name/type of the concurrent object with general name of lock. Since the value of these factors are binary (have two states), we can summarize them in a 3*8 truth-like table.

• X (Supports Ownership?): no(0) / yes(1)
• Y (#sharing processes): > 1 (∞) / 1
• Z (#processes/threads in CA): > 1 (∞) / 1

---

  X   Y   Z          Name
 --- --- --- ------------------------
  0   ∞   ∞   Semaphore              
  0   ∞   1   Binary Semaphore       
  0   1   ∞   SemaphoreSlim          
  0   1   1   Binary SemaphoreSlim(?)
  1   ∞   ∞   Recursive-Mutex(?)     
  1   ∞   1   Mutex                  
  1   1   ∞   N/A(?)                 
  1   1   1   Lock/Monitor           

Feel free to edit or expand this table, I've posted it as an ascii table to be editable:)

Dignity