Situation where mutexes are necessary?

Question

Can someone help me out with example of a situation in which absence of mutexes "definetely" leads to incorrect result.

I need this so that I could test my mutex implementation.

-- Neeraj

Answer 1

You definitely need a mutex (or similar mechanism) when there is a need from mutual exclusion.

Answer 2

Make a program that has a fork() in it. Then, make both the child process and the parent process read a number from the same file, increment it and then write it back to the file. Do this 100 times in each process.

Answer 3

The classic case is the ATM shared by husband and wife. One makes a deposit, the other a withdrawal in different threads. If the critical section isn't guarded appropriately by a mutex it's possible for each of them to see inconsistent results.

If a "definite situation" is required, have the husband make a deposit and then sleep for sufficient time so the wife can make a withdrawal. The husband's result will overwrite the wife's, and the the account balance isn't ACID anymore.

Answer 4

I think not, because the scheduler as implemented in current OSes is not deterministic from an application's point of view. However, if you start a lot of threads and test the code several times, the probability of a clash should be high enough.

Answer 5

Consider any correct code that uses mutexes for synchronization. By removing the locking, you will introduce new (possibly incorrect) behaviors (executions) to the program. However, the new code will still contain all of the old behaviors, therefore there will always be at least one execution that will yield a correct result. Hence, what you're asking for is impossible.

Answer 6

Here is the kind of test I used in my mutex implementation test suite:

// global:
enum { HUGE_VAL = 50000 }
Mutex mutex;
int variable;

// main thread
mutex.lock();
thread.run();
for(int i = 0; i < HUGE_VAL; ++i)
    ++variable;
assert(variable == HUGE_VAL);
mutex.unlock();
thread.join();
assert(variable == -HUGE_VAL);

// parallel thread
mutex.lock();
variable = -HUGE_VAL;
mutex.unlock();

Of course, adapt HUGE_VAL as you feel it, because a mutex is used to protect from concurrent acces. Therefore, to test it, you need to create concurrency, and the faster the machine, the huger HUGE_VAL should be...

Answer 7

Are you just testing that it locks correctly? If so maybe something like this? Two threads

#Global Variables
int counter = 1
int factorial = 1


#Critical Section
counter++
Delay for some amount of time
factorial *= counter
#End Critical Section

If your Mutex works then the end result should be 6. Otherwise it will be 9. Edit or 3 I suppose as the *= is not atomic but not 6 anyway.

Answer 8

You can simulate the famous "bank transfer" scenario used to illustrate database transactions. We have accounts A and B and need to transfer 200 bucks from A to B.

C++ - like pseudocode (not tested)

 int accountA = 200;
 int accountB = 0;

 void transfer( int& from, int& to, int amount )
 {
     //mutex acquisition should be here
     if( from < amount ) {
         printf( "error" );
         // mutex release should be here
         return;
     }
     from -= amount;
     Sleep( 5000 ); //wait idle for 5 seconds
     to += amount;
     // mutex release should be here
 }

 void display( const int& account1, const int& account2 )
 {
     //mutex acquisition should be here
     Sleep( 3000 ); //wait 3 seconds
     printf( "%d", account1 );
     printf( %d", account2 );
     // mutex release should be here
 }

now spawn two threads and execute transfer( accountA, accountB, 200 ); on one and display( accountA, accountB ); on another starting at the same moment of time.

On a system without load the program will show that money have disappeared "in the middle of transfer" - the accounts are read in the middle of "transaction" (the problem there's no transaction here), so there's no isolation. With mutexes you would see the final state - "after the transfer".