Second Attempt

We had problems in the first attempt because the global variables Buf_A and Buf_B are not protected. A very natural and perhaps a little naive way to protect these variables is to surround their accesses with a mutex lock. In the following, the message exchange part is divided into two stages. The first stage has two involved parties making their messages available. In doing so, a binary semaphore Mutex is used so that there is no more than one thread can access the global variables Buf_A and Buf_B. After both threads made their messages available, the second stage starts. The second stage is exactly identical to the first one, except that now the threads take the message from the other's buffer variable. So, the global variables are protected. Is this protection good enough?

Unfortunately, it is still incorrect. The use of semaphore Mutex prevents two threads in group A from accessing Buf_A at the same time. However, this protection is inadequate. Once A and B complete the first stage of message exchange and signal each other, the values of semaphores A and B are both 1s. Consequently, we cannot be sure if (1) A and B will continue with the second stage of message exchange, (2) another pair of threads will start their first stage, or (3) one of the current pair will continue and exchange a message with a newcomer in the other group. The last two can cause race conditions.

The following execution sequence shows a race condition of (3). Right after thread A1 and thread B make their message available (i.e., stage 1), A2 starts its first stage and executes Signal(B) and Wait(A). Then, B enters its second stage and executes Signal(A) and Wait(B). This may release A2 rather than A1. As a result, A2's message overwrites A1's and we have a race condition. Moreover, B exchanges message with A2 rather than A1, which is incorrect.

Lesson Learned

  • Improper protection is no better than no protection, because we have an illusion that data are well-protected.
  • We frequently forget that protection is done by a critical section, which cannot be subdivided. Thus, protecting each shared variable separately may be insufficient if the use of that variable is part of a long execution sequence. Protect the whole execution rather than each individual variable.
  • As a result, protecting "Here is my card" (i.e., first stage) and "May I have yours" (i.e., second stage) separately is unwise.