We learn from the previous attempt that protecting individual access to shared variables is risky, because a thread may come in and ruin a message before the previous message exchange completes. So, let us expand the critical section so that it covers the complete message exchange section.
In the program below, semaphore Aready (resp., Bready) is used to establish a mutual exclusion so that there is no more than one thread in group A (resp., B) can exchange message with a thread in group B (resp., A). Their initial values are 1. Semaphore Adone (resp., Bdone) is used to inform a B (resp., A) that a message is available. Under this scheme, a thread A waits for semaphore Aready. Once thread A is in, it is the only thread in group A that can exchange a message with a thread in group B. Therefore, thread A moves its message into shared variable Buf_A and executes Signal(Adone) to inform threads in group B that a message from a thread in group A is available. Then, thread A waits using Wait(Bdone) until a thread in group B signals it to indicate the availability of a message. Once a signal arrives, thread A retrieves the message from Buf_B. Then, it executes Signal(Aready) to indicate the completion of a message exchange so that the next thread in group A can come in. The logic for a thread in group B is similar.
Does this attempt work? No, it does not, even though it looks quite correct. Suppose threads A and B both successfully deposit their messages and reach the second wait (resp., Wait(Bdone) and Wait(Adone)). At this point, semaphores Adone and Bdone are both 1's. Assume A passes through Wait(Bdone), takes the message from Buf_B, executes Signal(Aready) to indicate the completion of a message exchange of A, and then loops back. See the execution sequence below for the details. If this A or another A is lucky enough to pass through Wait(Aready) and deposits a new message into Buf_A before B can retrieve the previous one, we lose a message and a race condition occurs!
Lesson Learned
|
|
|
|