Sign In
Create Account
Follow Us on Twitter
Subscribe on Youtube
1
I have explained critical sections and Mutex locks API in Linux/POSIX in an earlier tutorial
http://forum.codecal...on-locks-c.html
However, it is important to understand how these primitives are implemented internally. Often you are asked in programming interviews (Microsoft is famous for this one) to write your own mutex / semaphore / reader-writer.
Most of the ones I have seen on the internet are filled with OS specific terminologies that many find hard to digest. I will try to make it simpler. A motivational relevant post would be
http://forum.codecal...on-trouble.html
Also the code for this tutorial uses some inline assembly. An excellent beginner series to grasp assembly is
http://forum.codecal...e-part-1-a.html
First, the concept should be clear from the earlier tutorial i.e. WHY you need a lock? If that is answered, it can be assumed that you have a critical section (CS) which is a piece of code that can be executed simultaneously by multiple threads and is modifying at least one shared variable and at least two threads.
Now how can you ensure that while your thread 1 is inside CS, thread 2 does not start executing it until thread 1 is done with it?
The conventional thought is let’s have a global variable, if it is zero we can go into CS while making shared variable 1. This would be considered locked state. Any other thread which tries to go in sees it locked. When free after we are done with CS, we assign the shared variable back to 0 so that it can be locked again.
This seems perfect as long as we can guarantee that the lock test and modify can be executed atomically which means a thread cannot expire while in a state that it has executed test (if lock_variable equals to 0) but not the assignment (assign lock_variable = 1). Unfortunately we have no such guarantee so the above could happen and multiple threads can be executing CS code there by breaking your synchronization.
The core reason is, these “if then assignment” instructions are not atomic unless we find some special way to do that.
The concept behind needs to be understood. One way to implement this as often suggested is by disabling interrupts. What does that has to do with it? Interrupts are high priority OS messages (some times generated by programs too) which come in between a process’s normal execution by the CPU. It is interrupts using which OS ensures that a process only takes it allocated time slice of CPU cycles and no more. So if we find a way to disable interrupts while our process is running through CS, it would always be able to finish without any other thread intervening. But this is not termed a good solution and generally a user space program does not have the authority to disable all / relevant interrupts.
Other than that, there are some pure software based algorithms such as
Dekker's algorithm - Wikipedia, the free encyclopedia
Peterson's algorithm - Wikipedia, the free encyclopedia
which provide a way to obtain lock in user space without any special hardware support. But these are not the most preferred solutions based upon their time complexity which increases significantly as the number of simultaneous threads grow, although they would be portable across machines.
In general each platform provides a basic hardware instruction similar to “test and set”. There is a whole long debate around busy waiting vs. event driven, but I don’t want to complicate things, so let’s just understand that there is an instruction supported by hardware that can ‘test the value of a variable and assign it atomically’. This means that the operation cannot be separated or broken down. Either both (test and set) would execute or none of them would. This would resolve the key problem we have.
On Intel platform there is an assembly instruction called XCHG which takes two parameters, one register and one memory location and swaps them both. So the way we would do this is, initialize the memory variable with 0, register with 1 and exchange. Then test the register value. The variable will always be 1,
Register would contain the previous value of variable. If it was zero, it means lock was available and we have acquired it successfully (since variable is now 1). Then onwards, every other attempt would return register containing 1 which means variable was already locked. When we are done through the critical section, the variable can be assigned 0 again.
Code follows:
#include<iostream>
using namespace std;
int lock_var = 0; // actual lock global variable used to provide synchronization
int value; // variable contain lock value merely to explain current state
void acquire_lock()
{
__asm // Inline assembly is written this way in c
{
mov eax, 1 // EAX is a 32 bit register in which we are assigning 1
xchg eax, lock_var // Exchange eax and lock_var atomically
mov value, eax // merely saving for printing purpose
}
}
void free_lock()
{
__asm
{
mov eax, 0
xchg eax, lock_var // This could have been a single assignment lock_var = 0
mov value, eax // But we are merely using xchg again to see the previous value
}
}
int main()
{
acquire_lock();
if(value == 0) // Value would contain the previous value in lock_var before acquiring lock
cout << "Lock was available so acquired now" << endl;
acquire_lock();
if(value == 1)
cout << "Already locked so cannot acquire until free" << endl;
free_lock();
if(value == 1)
cout << "Freed now (though was locked earlier) and can be acquired" << endl;
acquire_lock();
if(value == 0)
cout << "Lock was available again so acquired now" << endl;
return 0;
}
And the output too
OwnMutex.jpg 38.02K
98 downloads
OwnMutex.jpg 38.02K
98 downloads Inline assembly means mixing assembly code inside c language code. This can simply be done by using blocks.
__asm
{
// statements in assembly
}
The above code is tested using MS Visual Studio 2010. So the assembler would be MASM.
This basic locking primitive can be extended to create other more complex synchronization tools such as semaphores, reader writers etc.
Back to top
