Cigarette smokers problem

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

SYMPTOMS

Motivation for the problem is an operating system that organizes independent processes that are waiting for allocation of resources ( also called sleep ). Is the operating system a resource available that would allow a single process to continue, the process should be informed (also called wake ). Processes for which no resources are currently available to be left in a waiting state.

Symbolic description

The problem is described pictorially by a tobacconist and three smokers who sit at a table together. To smoke the smoker will need the following things: tobacco, cigarette paper and matches. Each of the chain smoker has an infinite supply of exactly one resource: Smoking A has infinite amount of tobacco, smoking b infinitely cigarette paper and smoke C infinitely many matches. The tobacco merchant has all three ingredients infinitely more stock.

If the table is empty, the tobacconist selects two of the three ingredients from random and places it on the table. One of the smokers can now with its matching third ingredient rotate and smoke a cigarette. As the smoke always want to smoke, the corresponding smoker takes on the ingredients and starts to smoke. The seller can now again accidentally put the ingredients on the table. The currently supplied smoking could right ingredients for him but only take from the table when he smoked his cigarette end. Are the random ingredients for another smoking suitable, it can take them and smoke from the table. The tobacconist always sets new material on the table when it is empty. Otherwise, it must wait.

Technical Description

Technically, the problem can be described by multiple threads and semaphores. The tobacconist corresponds to three different threads TA, TB and TC, the wait table empty each have a common semaphore ( the free table displays ), share resources and then inform the appropriate smoking thread.

Examples which may be called a pseudo - code for thread TA:

Tischleer.warten () tabak.freigeben () papier.freigeben () Patil provided two additional conditions as limitations on to show that the semaphore as a solution to some of the problems are not sufficient. He demanded, first, that the tobacconist his behavior never changes and, second, that no semaphores and related fields are allowed semaphores. With this restriction, the pseudo - code is illegal and the problem even unsolvable. David Parnas found, however, that the second constraint is inappropriate, because that would be many problems unsolvable.

Leaving out of consideration the second constraint, the problem is to find an appropriate program code for the smokers. The obvious solution that smokers wait for the individual ingredients and taking them can lead to a deadlock. Has the Smoking A with matches following program code

Tabak.warten () papier.warten () tischleer.freigeben () and the corresponding other smoking code with the appropriate ingredients, then it can happen that the seller puts tobacco and paper on the table and smoking A takes the tobacco, while smoking his before B comes and takes the paper. Both smokers would now infinitely long wait each other out to get the other ingredient, because they do not come to indicate that the table is free.

Solution

David Parnas introduced a solution without conditional semaphores. Allen Downey uses conditional branches for a slightly more readable solution. It is based on three additional threads that accept the assignment of the ingredients. Each of the threads waiting for another of the three ingredients. The three threads are synchronized using Boolean variables and a mutex so that each thread know if someone else has already started the assignment. The program code for the thread that is waiting on tobacco could look like this:

Tabak.warten () mutex.warten ()     if paper already taken:        paper already taken = false        raucherMitStreichholz.freigeben ()     else if matchstick already taken:        streichholz already taken = false        raucherMitPapier.freigeben ()     else        tobacco already taken = true mutex.freigeben () Is the paper already taken Variable true, know this thread is that the waiting thread on paper is already over. So lay paper and tobacco on the table and this thread allows the smoker with match to take the ingredients and smoke. Its code looks like this:

RaucherMitStreichholz.warten () cigarette rotate () tischfrei.freigeben () smoking ( ) Simplified solution

A further simplification of the problem that the tobacco dealer smokers informed directly, making the solution very simple: you define an array of binary semaphores (A), with one semaphore per smoker. The seller is also associated with a semaphore: v.

The pseudo - code for the seller is:

While true {      down (V);      Choose two smokers from randomly, the third is smoking Smoking k k can now smoke      up (A [k ]); } The pseudo - code for smoking i is:

While true {      down (A [i]);      Turn a cigarette      up (V);      Smoke the cigarette } literature

• Andrew S. Tanenbaum: Modern Operating Systems. 2nd edition. Prentice- Hall, Upper Saddle River ( NJ), 2001, ISBN 0-13-031358-0 Modern operating systems. 2nd edition. Pearson Education, Inc., Munich 2002, ISBN 3-8273-7019-1