What is the difference between mutex and critical section?

Question

Please explain from Linux, Windows perspectives?

I am programming in C#, would these two terms make a difference. Please post as much as you can, with examples and such....

Thanks

Leakey

Answer 1

For Windows, critical sections are lighter-weight than mutexes.

Mutexes can be shared between processes, but always result in a system call to the kernel which has some overhead.

Critical sections can only be used within one process, but have the advantage that they only switch to kernel mode in the case of contention - Uncontended acquires, which should be the common case, are incredibly fast. In the case of contention, they enter the kernel to wait on some synchronization primitive (like an event or semaphore).

I wrote a quick sample app that compares the time between the two of them. On my system for 1,000,000 uncontended acquires and releases, a mutex takes over one second. A critical section takes ~50 ms for 1,000,000 acquires.

Here's the test code, I ran this and got similar results if mutex is first or second, so we aren't seeing any other effects.

HANDLE mutex = CreateMutex(NULL, FALSE, NULL);
CRITICAL_SECTION critSec;
InitializeCriticalSection(&critSec);

LARGE_INTEGER freq;
QueryPerformanceFrequency(&freq);
LARGE_INTEGER start, end;

// Force code into memory, so we don't see any effects of paging.
EnterCriticalSection(&critSec);
LeaveCriticalSection(&critSec);
QueryPerformanceCounter(&start);
for (int i = 0; i < 1000000; i++)
{
    EnterCriticalSection(&critSec);
    LeaveCriticalSection(&critSec);
}

QueryPerformanceCounter(&end);

int totalTimeCS = (int)((end.QuadPart - start.QuadPart) * 1000 / freq.QuadPart);

// Force code into memory, so we don't see any effects of paging.
WaitForSingleObject(mutex, INFINITE);
ReleaseMutex(mutex);

QueryPerformanceCounter(&start);
for (int i = 0; i < 1000000; i++)
{
    WaitForSingleObject(mutex, INFINITE);
    ReleaseMutex(mutex);
}

QueryPerformanceCounter(&end);

int totalTime = (int)((end.QuadPart - start.QuadPart) * 1000 / freq.QuadPart);

printf("Mutex: %d CritSec: %d\n", totalTime, totalTimeCS);

Disappointed

Not sure if this relates or not (since I haven't compiled and tried your code), but I've found that calling WaitForSingleObject with INFINITE results in poor performance. Passing it a timeout value of 1 then looping while checking it's return has made a huge difference in the performance of some of my code. This is mostly in the context of waiting for an external process handle, however... Not a mutex. YMMV. I'd be interested in seeing how mutex performs with that modification. The resulting time difference from this test seems bigger than should be expected. – Rudbeckia

@TroyHoward aren't you basically just spin locking at that point? – Precatory

The reasons for this distinction are probaly mainly historical. It is not hard to implement locking that is as fast as CriticalSection in the uncontended case (few atomic instructions, no syscalls), yet works across processes (with a piece of shared memory). See e.g. Linux futexes. – Reside

@TroyHoward try forcing your CPU to run at 100% all the time and see if INFINITE works better. The power strategy can take as long as 40ms on my machine (Dell XPS-8700) to crawl back up to full speed after it decides to slow down, which it may not do if you sleep or wait for only a millisecond. – Lotetgaronne

I'm not sure I understand what's being demonstrated here. Generally, entering a critical section requires acquring some kind of semaphore. Are you saying that behind the scenes, the O/S has an efficient way of implementing this critical section behavior without requiring mutexes? – Chibcha

Answer 2

From a theoretical perspective, a critical section is a piece of code that must not be run by multiple threads at once because the code accesses shared resources.

A mutex is an algorithm (and sometimes the name of a data structure) that is used to protect critical sections.

Semaphores and Monitors are common implementations of a mutex.

In practice there are many mutex implementation availiable in windows. They mainly differ as consequence of their implementation by their level of locking, their scopes, their costs, and their performance under different levels of contention. See CLR Inside Out - Using concurrency for scalability for an chart of the costs of different mutex implementations.

Availiable synchronization primitives.

• Monitor
• Mutex
• Semaphore
• ReaderWriterLock
• ReaderWriterLockSlim
• Interlocked

The lock(object) statement is implemented using a Monitor - see MSDN for reference.

In the last years much research is done on non-blocking synchronization. The goal is to implement algorithms in a lock-free or wait-free way. In such algorithms a process helps other processes to finish their work so that the process can finally finish its work. In consequence a process can finish its work even when other processes, that tried to perform some work, hang. Usinig locks, they would not release their locks and prevent other processes from continuing.

Manifestation

Seeing the accepted answer, I was thinking maybe I remembered the concept of critical sections wrong, till I saw that Theoretical Perspective you wrote. :) – Engagement

Practical lock free programming is like Shangri La, except it exists. Keir Fraser's paper (PDF) explores this rather interestingly (going back to 2004). And we're still struggling with it in 2012. We suck. – Pearlpearla

Answer 3

In addition to the other answers, the following details are specific to critical sections on windows:

• in the absence of contention, acquiring a critical section is as simple as an InterlockedCompareExchange operation
• the critical section structure holds room for a mutex. It is initially unallocated
• if there is contention between threads for a critical section, the mutex will be allocated and used. The performance of the critical section will degrade to that of the mutex
• if you anticipate high contention, you can allocate the critical section specifying a spin count.
• if there is contention on a critical section with a spin count, the thread attempting to acquire the critical section will spin (busy-wait) for that many processor cycles. This can result in better performance than sleeping, as the number of cycles to perform a context switch to another thread can be much higher than the number of cycles taken by the owning thread to release the mutex
• if the spin count expires, the mutex will be allocated
• when the owning thread releases the critical section, it is required to check if the mutex is allocated, if it is then it will set the mutex to release a waiting thread

In linux, I think that they have a "spin lock" that serves a similar purpose to the critical section with a spin count.

Inquiring

Unfortunately a Window critical section involves doing a CAS operation in kernel mode, which is massively more expensive than the actual interlocked operation. Also, Windows critical sections can have spin counts associated with them. – Soprano

That is definitly not true. CAS can be done with cmpxchg in user mode. – Disappointed

I thought the default spin count was zero if you called InitializeCriticalSection - you have to call InitializeCriticalSectionAndSpinCount if you want a spin count applied. Do you have a reference for that? – Inquiring

Answer 4

Critical Section and Mutex are not Operating system specific, their concepts of multithreading/multiprocessing.

Critical Section Is a piece of code that must only run by it self at any given time (for example, there are 5 threads running simultaneously and a function called "critical_section_function" which updates a array... you don't want all 5 threads updating the array at once. So when the program is running critical_section_function(), none of the other threads must run their critical_section_function.

mutex* Mutex is a way of implementing the critical section code (think of it like a token... the thread must have possession of it to run the critical_section_code)

Discreet

Also, mutexes can be shared across processes. – Amphibrach

Answer 5

A mutex is an object that a thread can acquire, preventing other threads from acquiring it. It is advisory, not mandatory; a thread can use the resource the mutex represents without acquiring it.

A critical section is a length of code that is guaranteed by the operating system to not be interupted. In pseudo-code, it would be like:

StartCriticalSection();
    DoSomethingImportant();
    DoSomeOtherImportantThing();
EndCriticalSection();

Magnetron

I think the poster was talking about user mode synchronization primitives, like a win32 Critical section object, which just provides mutual exclusion. I don't know about Linux, but Windows kernel has critical regions which behave like you describe - non-interruptable. – Disappointed

I don't know why you got downvoted. There's the concept of a critical section, which you've described correctly, which is different from the Windows kernel object called a CriticalSection, which is a type of mutex. I believe the OP was asking about the latter definition. – Hope

At least I got confused by the language agnostic tag. But in any case this is what we get for Microsoft naming their implementation the same as their base class. Bad coding practice! – Amitie

Well, he asked for as much detail as possible, and specifically said Windows and Linux so sounds like concepts are good. +1 -- didn't understand the -1 either :/ – Krongold

Answer 6

The 'fast' Windows equal of critical selection in Linux would be a futex, which stands for fast user space mutex. The difference between a futex and a mutex is that with a futex, the kernel only becomes involved when arbitration is required, so you save the overhead of talking to the kernel each time the atomic counter is modified. That .. can save a significant amount of time negotiating locks in some applications.

A futex can also be shared amongst processes, using the means you would employ to share a mutex.

Unfortunately, futexes can be very tricky to implement (PDF). (2018 update, they aren't nearly as scary as they were in 2009).

Beyond that, its pretty much the same across both platforms. You're making atomic, token driven updates to a shared structure in a manner that (hopefully) does not cause starvation. What remains is simply the method of accomplishing that.

Pearlpearla

Answer 7

Just to add my 2 cents, critical Sections are defined as a structure and operations on them are performed in user-mode context.

ntdll!_RTL_CRITICAL_SECTION
   +0x000 DebugInfo        : Ptr32 _RTL_CRITICAL_SECTION_DEBUG
   +0x004 LockCount        : Int4B
   +0x008 RecursionCount   : Int4B
   +0x00c OwningThread     : Ptr32 Void
   +0x010 LockSemaphore    : Ptr32 Void
   +0x014 SpinCount        : Uint4B

Whereas mutex are kernel objects (ExMutantObjectType) created in the Windows object directory. Mutex operations are mostly implemented in kernel-mode. For instance, when creating a Mutex, you end up calling nt!NtCreateMutant in kernel.

Motherwell

What happens when a program that initializes and uses a Mutex object, crashes? Does the Mutex object gets automatically deallocated? No, I would say. Right? – Abstriction

Kernel objects have a reference count. Closing a handle to an object decrements the reference count and when it reaches 0 the object is freed. When a process crashes, all of its handles are automatically closed, so a mutex that only that process has a handle to would be automatically deallocated. – Disappointed

And this is the reason why Critical Section objects are process bound, on the other hand mutexes can be shared across processes. – Savannasavannah

Answer 8

In Windows, a critical section is local to your process. A mutex can be shared/accessed across processes. Basically, critical sections are much cheaper. Can't comment on Linux specifically, but on some systems they're just aliases for the same thing.

Soprano

Answer 9

Great answer from Michael. I've added a third test for the mutex class introduced in C++11. The result is somewhat interesting, and still supports his original endorsement of CRITICAL_SECTION objects for single processes.

mutex m;
HANDLE mutex = CreateMutex(NULL, FALSE, NULL);
CRITICAL_SECTION critSec;
InitializeCriticalSection(&critSec);

LARGE_INTEGER freq;
QueryPerformanceFrequency(&freq);
LARGE_INTEGER start, end;

// Force code into memory, so we don't see any effects of paging.
EnterCriticalSection(&critSec);
LeaveCriticalSection(&critSec);
QueryPerformanceCounter(&start);
for (int i = 0; i < 1000000; i++)
{
    EnterCriticalSection(&critSec);
    LeaveCriticalSection(&critSec);
}

QueryPerformanceCounter(&end);

int totalTimeCS = (int)((end.QuadPart - start.QuadPart) * 1000 / freq.QuadPart);

// Force code into memory, so we don't see any effects of paging.
WaitForSingleObject(mutex, INFINITE);
ReleaseMutex(mutex);

QueryPerformanceCounter(&start);
for (int i = 0; i < 1000000; i++)
{
    WaitForSingleObject(mutex, INFINITE);
    ReleaseMutex(mutex);
}

QueryPerformanceCounter(&end);

int totalTime = (int)((end.QuadPart - start.QuadPart) * 1000 / freq.QuadPart);

// Force code into memory, so we don't see any effects of paging.
m.lock();
m.unlock();

QueryPerformanceCounter(&start);
for (int i = 0; i < 1000000; i++)
{
    m.lock();
    m.unlock();
}

QueryPerformanceCounter(&end);

int totalTimeM = (int)((end.QuadPart - start.QuadPart) * 1000 / freq.QuadPart);


printf("C++ Mutex: %d Mutex: %d CritSec: %d\n", totalTimeM, totalTime, totalTimeCS);

My results were 217, 473, and 19 (note that my ratio of times for the last two is roughly comparable to Michael's, but my machine is at least four years younger than his, so you can see evidence of increased speed between 2009 and 2013, when the XPS-8700 came out). The new mutex class is twice as fast as the Windows mutex, but still less than a tenth the speed of the Windows CRITICAL_SECTION object. Note that I only tested the non-recursive mutex. CRITICAL_SECTION objects are recursive (one thread can enter them repeatedly, provided it leaves the same number of times).

Lotetgaronne

Answer 10

I found the explanations stating that critical sections protect a code section from being entered by multiple threads quite misleading. There is no point in protecting code, as code is read only and can't be modified by multiple threads. What one usually wants is to protect data from being modified by multiple threads, leading to incoherent state. Commonly a mutex (or critical section, fulfilling the same purpose) should be associated with some piece of data. Each code section accessing this data should aquire the mutex/critical section and release when it's finished accessing the data. This may be considerably more fine grained than just locking out threads from entering a function. Also, from my experience, locking functions by some synchronisation is much more prone for errors, in particular dead locks. A good article covering that topic can be found here: https://www.bogotobogo.com/cplusplus/multithreaded4_cplusplus11B.php

So, in summary (recursive) mutexes and critical sections basically fulfill the same purpose, which is rather not protecting code, but protecting data instead.

Critical sections may be implemented more efficiently than plain kernel mutexes. The example given in the first answer is a bit misleading, because it does not depict what the synchronisation primitive is designed for: synchronize access to sth. from multiple threads. The example just measures the trivial case, when the critical section/mutex is never owned by another thread. While critical sections could be more efficient if, for instance, two threads access data in short, interlocked periods, they could prove less efficient if we got lots of threads accessing the same piece of data. Each thread would spinlock until giving up and waiting for the semaphore, part of the implementation of the critical section. Such a case should also be considered when measuring execution times.

Burr

Answer 11

A C functions is called reentrant if it uses its actual parameters only.

Reentrant functions can be called by multiple threads at the same time.

Example of reentrant function:

int reentrant_function (int a, int b)
{
   int c;

   c = a + b;

   return c;
}

Example of non reentrant function:

int result;

void non_reentrant_function (int a, int b)
{
   int c;

   c = a + b;

   result = c;

}

The C standard library strtok() is not reentrant and can't be used by 2 or more threads at the same time.

Some platform SDK's comes with the reentrant version of strtok() called strtok_r();

Gulfweed

To my untrained eye, this does not appear to answer the question about mutex and critical section. If you add some explanation for how this relates to the question, then it'll attract more upvotes and remain open. Otherwise, it'll probably be removed as not being an answer to this question. – Emarginate