This problem is due to S. S. Patil in 1971. Suppose a cigarette requires three ingredients, tobacco, paper and match. There are three chain smokers. Each of them has only one ingredient with infinite supply. There is an agent who has infinite supply of all three ingredients. To make a cigarette, the smoker has tobacco (resp., paper and match) must have the other two ingredients paper and match (resp., tobacco and match, and tobacco and paper). The agent and smokers share a table. The agent randomly generates two ingredients and notifies the smoker who needs these two ingredients. Once the ingredients are taken from the table, the agent supplies another two. On the other hand, each smoker waits for the agent's notification. Once it is notified, the smoker picks up the ingredients, makes a cigarette, smokes for a while, and goes back to the table waiting for his next ingredients.
Write a program that simulates this system, with three smokers and the agent being simulated by threads.
Let us draw a diagram that details all activities of the agent and a smoker. As usual, we use red squares and green circles for semaphore waits and signals, respectively. The table is a shared object, because the agent puts ingredients on the table and smokers take ingredients from the table. Therefore, some protection is necessary to avoid race condition. Is a mutex lock good enough? A good question. Isn't it? No, a mutex lock simply does not work, because with a lock the owner must unlock the lock which is not the case here. The agent waits for the table to become available, and then puts ingredients on the table. If we use a mutex lock, the agent must unlock the table, and if the agent is a fast runner he may come back and lock the table again to make another set of ingredient before the previous ones are taken. Thus, we have a race condition. Thus, we use a semaphore with which the thread that executes a wait to lock the semaphore and the thread that executes a signal to unlock the semaphore do not have to be the same.
When the table is available, the agent puts ingredient on the table. Of course, the agent knows what ingredients are on the table, and, hence, signals the smoker that needs this set of ingredients. On the other hand, a smoker cannot continue if he has no ingredients. To this end, we need another semaphore to block a smoker. In fact, we need three semaphores, one for each smoker. For example, if the agent puts paper and match on the table, he most inform the smoker who needs paper and match to continue. Therefore, the smoker who needs paper and match must wait on this semaphore.
The meaning of the above diagram is clear. The agent prepares for the ingredients, waits on the table, makes the ingredients available on the table when it becomes available, signals the proper smoker to take the ingredient, and then goes back for another round. For a smoker, he waits for the ingredients he needs, takes them when they are available, informs the agent that the table is free, makes a cigarette and smokes, and goes back for another round.
From the above discussion, we see that the table is not protected with a lock. Instead, it is protected through notification!
Because we have two types of threads, the agent and the smoker, we have two classes Agentthread and Smokerthread. The smoker thread is very simple, while the agent thread receives a name and the number of iterations iter. The number of iterations indicates how many times the agent should provide his ingredients on the table.
#include "ThreadClass.h"
#define NUM_OF_SMOKERS 3 // number of Smoker
class Smokerthread: public Thread
{
public:
Smokerthread(int Number); // constructor
private:
void ThreadFunc();
int No;
};
class Agentthread: public Thread
{
public:
Agentthread(char *ThreadName, int iter); // constructor
private:
void ThreadFunc();
int Iterations;
};
|
| Click here to download this file (smoker.h) |
To avoid initializing semaphores in the main program, we create the three semaphores for blocking smokers individually, and save the pointers in an array of pointer to Semaphore. Therefore, Sem[0], Sem[1], and Sem[2] are used to block the smokers who need paper-match, match-tobacco and tobacco-paper, respectively. More precisely, the smokers that have tobacco, paper and match are named as Smoker(Tobacco), Smoker(Paper) and Smoker(Match), respectively. The semaphores they are waiting for ingredients are PaperMatch, MatchTobacco and TobaccoPaper.
The constructor of Smokerthread takes one integer argument, indicating the smoker number. From this number, a proper name is assigned to the smoker thread. Here, the names of smokers 0, 1 and 2 are Smoker(Tobacco), Smoker(Paper) and Smoker(Match), indicating that these smokers have tobacco, paper and match, respectively.
The activities of a smoker is easy. It waits on semaphore Sem[No] for his ingredients, notifies the agent that the ingredients have been taken and the table is free once the needed ingredients are available, then executes Delay() to simulate smoking for a while, and then goes back for the next round.
The constructor of Agentthread is very simple. It takes the number of iterations and initializes the random number seed. The agent iterates for Iteration number of times. In each iteration, the agent takes some rest (i.e., the call to Delay()), generates a random number in the range of 0 and 2 that represents one of the three different pairs of ingredients, notifies the corresponding smoker that the ingredients are available, waits on the table to be cleared, and goes back for the next ingredients. After Iteration number of iterations, the agent exits.
#include <iostream>
#include <stdlib.h>
#include <time.h>
#include "smoker.h"
#define MATCH_PAPER 0
#define PAPER_TOBACCO 1
#define TOBACCO_MATCH 2
static char *materials[]={ "tobacco", "paper", "match" };
static char *names[] = { "Smoker(Tobacco)", "Smoker(Paper)", "Smoker(Match)"};
static Semaphore PaperMatch("PaperMatch");
static Semaphore MatchTobacco("MatchTobacco");
static Semaphore TobaccoPaper("TobaccoPaper");
static Semaphore *Sem[NUM_OF_SMOKERS] = {&PaperMatch, &MatchTobacco, &TobaccoPaper};
static Semaphore Table("Table", 0); // control the sharing of the table
strstream *Filler(int n)
{
int i;
strstream *Space;
Space = new strstream;
for (i = 0; i < n; i++)
(*Space) << ' ';
(*Space) << '\0';
return Space;
}
Smokerthread::Smokerthread(int Number)
{
No = Number;
ThreadName.seekp(0, ios::beg);
if (Number == 0)
ThreadName << "Smoker(Tobacco)" << '\0';
else if (Number == 1)
ThreadName << "Smoker(Paper)" << '\0';
else
ThreadName << "Smoker(Match)" << '\0';
}
// -------------------------- Smokerthread ---------------------------
void Smokerthread::ThreadFunc()
{
Thread::ThreadFunc();
strstream *Space;
Space = Filler(4); // build leading spaces
while (1) {
Sem[No]->Wait(); // smoker waits for materials
cout << Space->str() << ThreadName.str() << " is smoking" << endl;
Table.Signal(); // take ingredients and release the table
Delay(); // smoking for a while
}
}
Agentthread::Agentthread(char *ThreadName, int iter)
: Thread(ThreadName)
{
Iterations = iter;
srand((unsigned int) time(NULL));
}
// ---------------------------- Agentthread ------------------------------
void Agentthread::ThreadFunc()
{
Thread::ThreadFunc();
int RandomNo;
for (int i = 0; i < Iterations; i++) {
Delay();
RandomNo = rand() % NUM_OF_SMOKERS;
cout << "Agent prepares " << materials[RandomNo] << " and "
<< materials[(RandomNo+1) % NUM_OF_SMOKERS] << endl;
Sem[RandomNo]->Signal(); // randomly provide material to one smoker
Table.Wait(); // waiting for smoker finish smoking
cout << "Agent finishes serving " << names[RandomNo] << endl;
}
cout << "Agent quits." << endl;
Exit();
}
|
| Click here to download this file (smoker.cpp) |
The main program is easy. It creates and runs the agent thread first, followed by the three smokers. Note that the smoker threads never exit. Therefore, the main program only joins with the agent thread. As you can see, all initialization activities of semaphores are moved to the implementation file of class, and none of these activities is visible in the main program.
#include <iostream>
#include <stdlib.h>
#include "smoker.h"
int main(int argc, char *argv[])
{
Smokerthread SmokerTobacco(0); // smoker thread with "tobacco"
Smokerthread SmokerMatch(1); // smoker thread with "match"
Smokerthread SmokerPaper(2); // smoker thread with "paper"
int Iterations;
if (argc != 2) {
cout << "Use " << argv[0] << " #-of-iterations of agent." << endl;
exit(0);
}
Iterations = abs(atoi(argv[1]));
// create the agent thread and fire it up
Agentthread Agent("Agent", Iterations);
Agent.Begin();
// start smoker threads
SmokerTobacco.Begin();
SmokerMatch.Begin();
SmokerPaper.Begin();
// wait for all child threads
Agent.Join();
cout << "Game is over." << endl;
Exit();
return 0;
}
|
| Click here to download this file (smoker-main.cpp) |
The original version of the smokers problem is more sophisticated. Each ingredient is associated with a semaphore. The agent adds two different ingredients on the table, and signals the corresponding semaphores. Each smoker waits for his ingredients to become available. It looks very similar to the solution above. However, it is not and has some complicated issues to be solved. For example, if the agent puts paper and match on the table, and signals semaphores paper and match. Then, the smoker who needs paper and the smoker who needs match may pass their first wait. However, they may wait for their second needed ingredient, and neither of them cannot signal the agent to indicate the table has been cleared (because each of them only gets on ingredient). Hence, we have a deadlock, smokers waiting for the agent for more ingredients and the agent waiting for smoker to clear the table.
This is a very good example of simultaneous wait. More precisely, a smoker who has paper can continue only if the semaphores corresponding to tobacco and match can be decreased by 1. If one of these two semaphores has counter value 0, the smoker waits. This type of semaphores is available on Unix and Linux. It turns out, this type of and synchronization is equivalent to the form we have been using so far. In other word, we can use and synchronization semaphores to implement traditional semaphores (easy), and use traditional semaphores to implement and synchronization semaphores (more involved). Why don't you try it?
|
|
|