Fourth Attempt

The critical sections in the third attempt are not good enough because they cannot block threads in the same group from rushing in and overwriting the existing message before it is taken. So, we might force a thread in group A (resp., group B) to wait until a thread in group B (resp., group A) completes its task. The following is an attempt that is similar to the previous one, except that when a thread in a group completes its task, it signals the other group. Hopefully, this would overcome the problem in the previous attempt.

Unfortunately, this attempt does not work either! In the following execution sequence, right after thread A1 deposits its message into Buf_A and informs B with Signal(Adone), B retrieves the message, and signals semaphore Bready to indicate the completion of B. After this signal completes, semaphore Bready is 1. However, thread A2 may be faster than thread A1 does. As a result, thread A2 passes through Wait(Bready), sets its message into Buf_A, executes Signal(Adone) followed by Wait(Bdone). Since semaphore Bdone was signaled by thread B, its value is 1. Therefore, thread A2 passes through Wait(Bdone) and retrieves the message that is supposed to be retrieved by thread A1. Therefore, we have a race condition!

Lesson Learned

  • Mutual exclusion is important! If the lock for mutual exclusion is not released by its owner, race condition may occur.
  • In the above, the lock, actually a binary semaphore, Bready (resp., Aready) is acquired by a thread in group A (resp., group B) and released by a thread in group B (resp., group A). This is a very risky programming practice if mutual exclusion is the central concern.
  • In the case, a pure mutex lock is more natural than a binary semaphore.