Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Overview
Consider an interesting and challenging synchronization problem, the campaign mailer’s problem. Suppose that
a campaign mailing requires three items: an envelope, a campaign flyer and a stamp. There are three volunteers,
each of whom has only one of these items with infinite supply. There is an agent who has an infinite supply of
all three items. To put together a mailing, the volunteer who has an envelope must have the other two items, a
campaign flyer and a stamp. (You can figure out what happens with the volunteers who start with campaign
flyers and stamps, respectively.) The agent and volunteers share a table. The agent randomly generates two items
and notifies the volunteer who needs these two items. Once they are taken from the table, the agent supplies
another two. On the other hand, each volunteer waits for the agent’s notification. Once notified, the volunteer
picks up the items, puts together a mailing, takes the mailing to the mailbox, and goes back to the table waiting
for his next items. The problem is to come up with an algorithm for the volunteers using semaphores as
synchronization primitives.
Now, all jokes aside, this is an actual problem related to computer science. The agent represents an operating
system that allocates resources, while the volunteers represent applications that need resources. The problem is
to make sure that if resources are available that would allow one or more applications to proceed, those
applications should be awakened. Conversely, we want to avoid waking an application if it cannot proceed.
A restriction of the problem is that you are not allowed to modify the agent code. (Indeed, if the agent represents
an operating system it makes sense to assume that you don’t want to modify it every time a new application comes
along.) The agent uses these binary semaphores and actually consists of three concurrent threads (one of which
is given below.) Each waits on agentSem. Each time it’s signaled, one agent thread wakes up and provides
items by signaling two other semaphores.
Semaphore agentSem = 1;
Semaphore envelope = 0;
Semaphore flyer = 0;
Semaphore stamp = 0;
while (true)
{
Wait(agentSem);
Signal(envelope);
Signal(flyer);
}
(One thing you will need to change when you implement this is to make the three agent threads sleep for a random
period of time – up to 200 milliseconds – before beginning to wait on agentSem. This will hopefully mix things
up and make this more interesting.)
Page 2 of 7
This becomes a hard problem because you can show that the natural solution leads to deadlock. To get around
this, propose the use of three additional “pusher” threads that respond to the signals from the agents, keep track
of the available items and signal the appropriate volunteer. We first need three Boolean variables to indicate
whether or not an item is on the table, three new semaphores to signal the volunteers, and a semaphore for
preserving mutual exclusion (as given below.)
Boolean isEnvelope = false;
Boolean isFlyer = false;
Boolean isStamp = false;
Semaphore envelopeSem = 0;
Semaphore flyerSem = 0;
Semaphore stampSem = 0;
Semaphore mutex = 1
Pseudo code for one of the pushers (the one who wakes up when there’s an envelope on the table) appears below.
If this pusher finds flyer, it knows that the flyer pusher has already run, so it can signal the volunteer with stamps.
Similarly, if it finds stamps, the volunteer with flyers is signaled. Finally, if this is the first pusher to run, it cannot
signal any volunteer, so sets isEnvelope.
while (true)
{
wait(envelope);
wait(mutex);
if (isFlyer)
{
isFlyer = false;
signal(stampSem);
}
else
if (isStamp)
{
isStamp = false;
signal(flyerSem);
}
else
isEnvelope = true;
signal(mutex);
}
Page 3 of 7
The other pushers are similar. Since they do all the work, the volunteer code is trivial. Pseudo code for the
volunteer with an envelope appears below; the others are similar. As above simulate the putting together a mailer
and taking the mailing to the mailbox by having the thread sleep for a short period of time (up to 50 milliseconds
for both the putting together a mailer and taking the mailing to the mailbox).