Smoking problem

from Wikipedia, the free encyclopedia

The smoking problem is a problem of process synchronization and was formulated by Suhas S. Patil in 1971. It describes a certain behavior of activities running in parallel, which are forced to use certain resources together, and asks the question of possibilities of coordination in order to enable a smooth process.

Problem Description

The motivation for the problem is an operating system that organizes independent processes that wait for resources to be allocated (also called sleep ). If the operating system has a resource that would allow a process to continue, the process should be informed (also called waking up ). Processes for which no resources are currently available should be left in the waiting state.

Pictorial description

The problem is pictorially described by a tobacconist and three smokers sitting together at a table. In order to smoke, smokers need the following things: tobacco , cigarette paper and matches . Each of the chain smokers has an infinite supply of exactly one resource: smoker A has an infinite amount of tobacco, smoker B an infinite amount of cigarette paper and smoker C an infinite number of matches. The tobacco merchant has an infinite supply of all three ingredients.

If the table is empty, the tobacconist chooses two of the three ingredients at random and places them on the table. One of the smokers can now roll a cigarette and smoke with his matching third ingredient. Since the smokers always want to smoke, the corresponding smoker picks up the ingredients and starts smoking. The seller can now randomly place ingredients on the table again. However, the smoker who has just been delivered could only take the right ingredients from the table when he has finished smoking his cigarette. If the random ingredients are suitable for another smoker, he can take them from the table and smoke. The tobacco merchant always puts new material on the table when it is empty. Otherwise he'll have to wait.

technical description

Technically, the problem can be described by several threads and semaphores . The tobacco merchant corresponds to three different threads TA , TB and TC , each waiting for a common semaphore tischleer(indicating the free table), releasing the resources and then informing the appropriate smoking thread.

A pseudo program code for thread TA is mentioned as an example : 

tischleer.warten()
tabak.freigeben()
papier.freigeben()

Patil set two more constraints as constraints to show that semaphores are not sufficient as a solution to some problems. He demanded, first, that the tobacco merchant never changes his behavior and, second, that no conditional semaphores and fields of semaphores are allowed. With this restriction, the pseudo-program code is invalid and the problem is even unsolvable. However, David Parnas found that the second limitation was inappropriate because it would make many problems unsolvable.

If one ignores the second restriction, the problem is to find a suitable program code for the smokers. The obvious solution, that smokers wait for the individual ingredients and take them, can lead to a deadlock . Does smoker A with matches have the following program code 

tabak.warten()
papier.warten()
tischleer.freigeben()

and the other smokers corresponding code with the appropriate ingredients, then it can happen that the seller puts tobacco and paper on the table and smoker A takes the tobacco while smoker B precedes him and takes the paper. Both smokers would now wait indefinitely for each other to get the other ingredient, because they couldn't get around to indicating that the table was free.

solution

David Parnas presented a solution without conditional semaphores. Allen Downey uses conditional branches for a slightly more readable solution. It is based on three additional threads that handle the ingredient assignment. Each of the threads waits for a different one of the three ingredients. The three threads are synchronized via Boolean variables and a mutex so that each thread knows whether another has already started the assignment. The code for the thread waiting for tobacco could look like this: 

tabak.warten()
mutex.warten()
   if papierSchonGenommen:
      papierSchonGenommen = false
      raucherMitStreichholz.freigeben()
   else if streichholzSchonGenommen:
      streichholzSchonGenommen = false
      raucherMitPapier.freigeben()
   else
      tabakSchonGenommen = true
mutex.freigeben()

If the variable is papierSchonGenommentrue, this thread knows that the thread waiting for paper has already run. So there were paper and tobacco on the table and this thread allows the smoker with a match to take the ingredients and smoke. Its program code then looks like this: 

raucherMitStreichholz.warten()
zigaretteDrehen()
tischfrei.freigeben()
rauchen()

Simplified solution

Another simplification of the problem that the tobacco merchant informs the smoker directly makes the solution very simple: An array of binary semaphores ( A ) is defined, with one semaphore for each smoker. A semaphore is also assigned to the seller: v .

The pseudo program code for the seller is: 

while true {
    down(v);
    Wähle zwei Raucher zufällig aus, der dritte wird Raucher k. Raucher k kann nun rauchen
    up(A[k]);
}

The pseudo-program code for smoker i is: 

while true {
    down(A[i]);
    Drehe eine Zigarette
    up(v);
    Rauche die Zigarette
}

See also

literature