what would happen if you signal() before wait()?

Question

A bakery shop has to provide a stream of muffins for customers. The muffins are made by a baker in the kitchen and placed on a conveyor belt. The conveyor belt carries the muffins to where the customers are waiting to buy them. This scenario has been simulated using two processes: the baker and customer, and a shared conveyor belt implemented as a circular array called conveyor, where each space in the array can hold one muffin. There are two shared general semaphores, empty and full, and a mutex buffer_mutex. In this scenario, there is only multiple bakers and a single customer.

The pseudo-code for the baker is as follows. The baker makes use of an integer variable in for noting the next available space on the conveyor belt.

while(true){
muffin = makeMuffin(); // Create a muffin
wait(empty);
wait(buffer_mutex);
conveyor[in] = muffin; // Put the muffin on the conveyor belt
in = (in + 1) mod n;
signal(buffer_mutex);
signal(full);
}

The pseudo-code for the customer is as follows. The customer makes use of an integer variable out for noting the next location on the conveyor belt that contains a muffin.

while(true){
wait(full);
muffin = conveyor[out]; // Get a muffin from the conveyor belt
conveyor[out] = null;
out = (out + 1) mod n;
signal(empty);
eat(muffin); // Eat the muffin
}

What will happen if the order of semaphores in the customer changes. So, we have in line 2 signal(empty) and in line 6 wait(full).

gnasher729 · Accepted Answer · 2020-03-15 09:13:05Z

I didn't look at your code. What counts is how wait and signal work.

When your code contains a wait(), the line of code after the wait() will be executed after a signal() call. It doesn't matter if the signal() happened before or after the wait.

Now your buffer_mutex has an obvious problem: After the wait(), the next line of code is only executed after the appropriate signal(). But signal() is never executed because your code is waiting for the signal(). You may have confused this with lock / unlock.

What if the buffer was full? Would it matter that signal() came before wait()? — Callum Bell
– Callum Bell, Commented Mar 15, 2020 at 21:46

Mike Robinson · Accepted Answer · 2020-03-16 16:28:16Z

Consider it this way:

signal() does not mean "wake up!" It means: "you should not be sleeping now."

At the instant a signal comes in, the signaled process might or might not be sleeping. If it comes in before the process attempts to wait() it will not actually go to sleep at all.

In this case, you would need a counting semaphore, initially set to zero, another one that is set to the size of the conveyor, and a mutex controlling access to the conveyor itself.

In order to manipulate the conveyor, or to reliably examine its status, you must first obtain and hold the buffer-mutex. You release it as soon as you are done. This maintains the integrity of the shared data structure.
In order to put a muffin on the conveyor, the baker must first obtain (decrement ...) the "size of the conveyor" semaphore. If the conveyor is full (count <= 0), he will be delayed. He then places a muffin (using the mutex), and increments the "number of muffins" semaphore.
To remove a muffin, the customer must first obtain the "number of muffins" semaphore. If the conveyor is empty, he will be delayed. He then removes a muffin (using the mutex), and increments (signals ...) the "size of the conveyor" mutex.

In each case, one party waits on a semaphore that is controlled by the other party, and vice-versa. Meanwhile, everyone who manipulates the conveyor must hold the mutex while doing it.

Stack Exchange Network

what would happen if you signal() before wait()?

2 Answers 2

Hot Network Questions