C++ - Threads without coordinating mechanism like mutex_Lock

Question

I attended one interview two days back. The interviewed guy was good in C++, but not in multithreading. When he asked me to write a code for multithreading of two threads, where one thread prints 1,3,5,.. and the other prints 2,4,6,.. . But, the output should be 1,2,3,4,5,.... So, I gave the below code(sudo code)

mutex_Lock LOCK;
int  last=2;
int last_Value = 0;

void function_Thread_1()
{
      while(1)
      {
          mutex_Lock(&LOCK);
          if(last == 2)
          {
              cout << ++last_Value << endl;
              last = 1;
          }
          mutex_Unlock(&LOCK);
      }
}

void function_Thread_2()
{
      while(1)
      {
          mutex_Lock(&LOCK);
          if(last == 1)
          {
              cout << ++last_Value << endl;
              last = 2;
          }
          mutex_Unlock(&LOCK);
      }
}

After this, he said "these threads will work correctly even without those locks. Those locks will reduce the efficiency". My point was without the lock there will be a situation where one thread will check for(last == 1 or 2) at the same time the other thread will try to change the value to 2 or 1. So, My conclusion is that it will work without that lock, but that is not a correct/standard way. Now, I want to know who is correct and in which basis?

Answer 1

Without the lock, running the two functions concurrently would be undefined behaviour because there's a data race in the access of last and last_Value Moreover (though not causing UB) the printing would be unpredictable.

With the lock, the program becomes essentially single-threaded, and is probably slower than the naive single-threaded code. But that's just in the nature of the problem (i.e. to produce a serialized sequence of events).

Answer 2

I think the interviewer might have thought about using atomic variables.

Each instantiation and full specialization of the std::atomic template defines an atomic type. Objects of atomic types are the only C++ objects that are free from data races; that is, if one thread writes to an atomic object while another thread reads from it, the behavior is well-defined. In addition, accesses to atomic objects may establish inter-thread synchronization and order non-atomic memory accesses as specified by std::memory_order.

[Source]

By this I mean the only thing you should change is remove the locks and change the lastvariable to std::atomic<int> last = 2; instead of int last = 2;

This should make it safe to access the last variable concurrently.

---

Out of curiosity I have edited your code a bit, and ran it on my Windows machine:

#include <iostream>
#include <atomic>
#include <thread>
#include <Windows.h>

std::atomic<int>    last=2;
std::atomic<int>    last_Value = 0;
std::atomic<bool>   running = true;

void function_Thread_1()
{
      while(running)
      {
          if(last == 2)
          {
              last_Value = last_Value + 1;
              std::cout << last_Value << std::endl;
              last = 1;
          }
      }
}

void function_Thread_2()
{
      while(running)
      {
          if(last == 1)
          {
              last_Value = last_Value + 1;
              std::cout << last_Value << std::endl;
              last = 2;
          }
      }
}

int main() 
{
    std::thread a(function_Thread_1);
    std::thread b(function_Thread_2);

    while(last_Value != 6){}//we want to print 1 to 6

    running = false;//inform threads we are about to stop

    a.join();
    b.join();//join

    while(!GetAsyncKeyState('Q')){}//wait for 'Q' press
    return 0;
}

and the output is always:

1
2
3
4
5
6

Ideone refuses to run this code (compilation errors)..

Edit: But here is a working linux version :) (thanks to soon)

Answer 3

The interviewer doesn't know what he is talking about. Without the locks you get races on both last and last_value. The compiler could for example reorder the assignment to last before the print and increment of last_value, which could lead to the other thread executing on stale data. Furthermore you could get interleaved output, meaning things like two numbers not being seperated by a linebreak.

Another thing, which could go wrong is that the compiler might decide not to reload last and (less importantly) last_value each iteration, since it can't (safely) change between those iterations anyways (since data races are illegal by the C++11 standard and aren't acknowledged in previous standards). This means that the code suggested by the interviewer actually has a good chance of creating infinite loops of doing absoulutely doing nothing.

While it is possible to make that code correct without mutices, that absolutely needs atomic operations with appropriate ordering constraints (release-semantics on the assignment to last and acquire on the load of last inside the if statement).

Of course your solution does lower efficiency due to effectivly serializing the whole execution. However since the runtime is almost completely spent inside the streamout operation, which is almost certainly internally synchronized by the use of locks, your solution doesn't lower the efficiency anymore then it already is. Waiting on the lock in your code might actually be faster then busy waiting for it, depending on the availible resources (the nonlocking version using atomics would absolutely tank when executed on a single core machine)