16 August 2014

Mutex tutorial and example

It began because of being asked to watch one of Yashwant Kanetkar's painfully boring video tutorials at my workplace. He explained every concurrency concept with an example, but for mutexes, he said "I leave it to you as an assignment". *groan*. To add to the difficulty, there weren't any decent tutorials on the internet either.

So one day when a lightbulb lit up in my head, I decided to create my own mutex example.

Here it is

A lot of people run to a lone phone booth (no mobiles) to talk to their loved ones. The first person to catch the door-handle of the booth, is the one who is allowed to use the phone. He has to keep holding on to the handle of the door as long as he uses the phone, otherwise someone else will catch hold of the handle, throw him out and talk to his wife :-) There's no queue system as such. When the person finishes his call, comes out of the booth and leaves the door handle, the next person to get hold of the door handle will be allowed to use the phone.
A thread is : Each person
The mutex is : The door handle
The lock is : The person's hand
The resource is : The phone
Any thread which has to execute some lines of code which should not be modified by other threads at the same time (using the phone to talk to his wife), has to first acquire a lock on a mutex (clutching the door handle of the booth). Only then will a thread be able to run those lines of code (making the phone call).
Once the thread has executed that code, it should release the lock on the mutex so that another thread can acquire a lock on the mutex (other people being able to access the phone booth).

Blue is the protected area of code.
Red is where the locking happens.
Green is where the unlocking happens.

#include <iostream>
#include <thread>
#include <mutex>

std::mutex m;//you can use std::lock_guard if you want to be exception safe 
int i = 0; 
void makeACallFromPhoneBooth() 
    //The other men wait outside 
    m.lock();// one man gets a hold of the phone booth door and locks it. 
      //man happily talks to his wife from now....
      std::cout << i << " Hello Wife" << std::endl;
      i++;//no other thread can access variable i until m.unlock() is called
      //...until now, with no interruption from other men
    m.unlock();//man unlocks the phone booth door 

int main() 
    //This is the main crowd of people uninterested in making a phone call

    //man1 leaves the crowd to go to the phone booth
    std::thread man1(makeACallFromPhoneBooth);
    //Although man2 appears to start second, there's a good chance he might
    //reach the phone booth before man1
    std::thread man2(makeACallFromPhoneBooth);
    //And hey, man3 also joined the race to the booth
    std::thread man3(makeACallFromPhoneBooth);

    man1.join();//man1 finished his phone call and joins the crowd
    man2.join();//man2 finished his phone call and joins the crowd
    man3.join();//man3 finished his phone call and joins the crowd
    return 0;
Compile and run it using  
g++ -std=c++0x -pthread -o thread thread.cpp

Note that apart from explicitly specifying lock() and unlock(), it's also possible to let the variable scope define when the unlocking happens (scoped lock).

Memory fencing
Do you know that while processing instructions, threads recognize that an area of code is protected by a mutex, through the concept of memory fencing.
A memory barrier, also known as a membar, memory fence or fence instruction, is a type of barrier instruction which causes a central processing unit (CPU) or compiler to enforce an ordering constraint on memory operations issued before and after the barrier instruction. This typically means that operations issued prior to the barrier are guaranteed to be performed before operations issued after the barrier.

It's basically some CPU instructions that inform a CPU that a region of code should not be accessed for a while.

Lockless programming
Did you also know that it's possible to design your algorithm in a way that it might use shared memory, and yet not need to use mutexes? Typically, such instructions are processed in such a way that a group of load and store instructions are executed atomically (transactional memory). This is achieved by using hardware intrinsic atomic operations.
An algorithm is lock-free if there's a system-wide progress regardless of scheduling, and an algorithm is wait-free if there's also a per-thread progress.


The fact that you are here means that you use the computer a lot. So please also take some time to understand the real cure for eye strain.  Yes, it matters.


Anonymous said...

Example of pre c++ 2011 mutex would be great.

Nav said...

@Anonymous: I just considered posting a tutorial for the older version, but realized that the whole reason that I initially chose to post a simple example of using mutexes with TBB on StackOverflow.com (http://stackoverflow.com/questions/4989451/mutex-example-tutorial), was so that the explanation and the code would be short and clear. None of the other examples on the internet were concise, mainly because of pthread syntax and CreateMutex syntax which looks messy. Clarity in understanding was the primary focus of the tutorial, and neat syntax is needed for that.

When I realized that most people didn't have access to TBB, I posted the C++0x example.

Modern C++ compilers will easily be able to run the program which I posted, and I strongly recommend that people move toward modern standards. If you still want an older tutorial, then have a good look at how my code has been structured and understand the mutex concept. Then use the pre-C++0x code to create an example similar to mine, and post it online. It'll not only help in your learning, but will help others too. You'll automatically be doing this too: http://nrecursions.blogspot.in/2014/02/contributing-to-open-source-community.html

happyuk said...

Nice example. Suitable for someone like me who needs to start understanding this stuff.

Nav said...

Thank you happyuk. Knowing that it has been useful to you brings happiness to what has been a rather disappointing day for me today. :-) Glad you wrote in.

Anonymous said...

Super job! Needed to get this straight in my head as I'm moving from futures to shared_futures. Wish I could sign in with my Disqus handle (seems friendlier than remaining anonymous)
Hope you have great day!

Nav said...

Glad it helped you, Anonymous! You taught me something in return now. I wasn't familiar with std::shared_future and std::promise. Been quite some time since I used C++.
Yes, Blogger doesn't allow a Disqus handle yet, but there was the option of leaving your name and URL...
Cheers! Keep learning, and enjoy the LOL pages I put up every month whenever you pass by NRecursions!

Jason D said...

Thank you for this simple explanation. My head wasn't wrapping around this concept until now.

Nav said...

You're most welcome Jason. By thanking me, you're just thanking one of the people in this world who contributes to open source. There are thousands of awesome people who share their knowledge and build open source software. The better way to thank us is by you contributing your knowledge to open source and build the internet for greater good. Also encourage others to do so: http://nrecursions.blogspot.in/2014/02/contributing-to-open-source-community.html

anonymous said...

Great article, you have given good explanation to memory fencing and lockless programming

thealoeshop said...

Brilliant article, Nav. Didn't get mutexes until now. Thank you.

Anonymous said...

Six years later... great blog post. Helped me start understanding mutex and how I might use it. Thanks!