Saturday, August 16, 2014

Mutex tutorial and example

It began while being asked to watch one of Yashwant Kanetkar's slow 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. For more than two and a half years, it ranked highest for anyone who Googled for "mutex tutorial".

And 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
./thread 


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.



Some people have emailed me asking if they could thank me for having given them knowledge. The best way to thank me is by contributing to Open Source. Being a sweetheart if you'd like to give a more personal thank you, then I don't really like the idea of monetary donations, but  maybe a wishlist wouldn't be that bad.





9 comments:

Anonymous said...

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

Navin Ipe 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.

Navin Ipe 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!

Navin Ipe 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.

Navin Ipe 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