Reklama

Synchronization problems in OS

Проблемы синхронизации в ОС

The literature on operating systems contains many interesting problems, which have been widely discussed and analysed with the use of different methods of synchronization. In this section, we consider the three most known issues.

Problem dining philosophers

In 1965 year of Dijkstra formulated and solved the synchronization problem, named problem dining philosophers. Since then, every, who invented another new synchronization primitive, considered it his duty to demonstrate the advantages of the new primitive in the example problem dining philosophers. The problem can be formulated as follows: five philosophers are sitting at a round table, and everyone has a plate with spaghetti. Spaghetti is so slippery, that each philosopher needs two forks, to cope with them. Between every two plates is one fork .

The life of a philosopher consists of alternating periods of eating and thinking. (Of course, this abstraction, even for philosophers, but the other vital processes for our task irrelevant.) When the philosopher is hungry, he tries to get two forks, left and right, in any order. If he managed to get two forks, for some time he eats, then puts the plug back in and keeps thinking. The question is: is it possible to write an algorithm, which models these steps for each philosopher and never gets stuck? (Some believe, the need two forks looks a bit artificially. Possible, we should replace food Italian cuisine Chinese cuisine, spaghetti rice, and fork — relevant sticks.)

 

You can change the program so, so after getting the left fork was checked availability right. If the right fork is unavailable, the philosopher gives left back, waits a while and repeats the whole process. This approach also will not work, though for a different reason. If you're not lucky, all five philosophers can begin the process at the same time, take the left fork, to detect the lack of the right, put your left back on the table, at the same time to take the left fork, and so on to infinity. The situation, in which all the programs continue to run indefinitely, but they can't achieve at least some progress, called process to hang (English music from starvation, literally, "dying from hunger". This

The term applies even in the case, when the problem does not occur in Italian or Chinese restaurant, and on computers).

You might think: "If philosophers will ponder for a randomly selected period of time after an unsuccessful attempt to take the right fork, the probability, all processes will continue to stagnate for at least a hour, small". It's right, and for most applications the retry after some time is not a problem. For example, in LAN Ethernet in the situation, when two computers send packets at the same time, everyone has to wait a randomly specified time and try again — in practice this solution works well. However, in some applications, the preferred is another solution, always working and not dependent on random numbers (for example, in the application for safety in nuclear power plants).

To make improvement, excluding deadlocks and process hangs: to protect the five operators, following the inquiry think, binary semaphore. Then the philosopher will need to perform an operation on a mutex variable Down first, than be pulled to plugs. And after the return of the forks to the place he should perform Up on the variable mutex. From a theoretical point of view the decision is quite suitable. From the practical point of view there are problems with efficiency: at each moment of time can eat spaghetti only one philosopher. But five forks, therefore, it is necessary to solve in each time two philosophers.

Solution, avoids deadlock and allows the maximum possible parallelism for any number of philosophers. Here we use an array state to track the mental state of each philosopher: he either eats, or thinks, or fast (trying to get forks). The philosopher can start eating, only if none of its neighbors are not eating. Neighbors of a philosopher with index i are defined by the macros LEFT and RIGHT (that is, if i = 2, the LEFT=

The problem of readers and writers

The dining philosophers problem is useful for modeling processes, competing for exclusive access to a limited amount of resources, for example, to devices I / o. Another known problem is the problem of readers and writers [78], simulating database access. Consider a database that booking of plane tickets, trying to access a plethora of processes. You can allow simultaneous reading of data from the database, but if the process writes information to the database, the access other processes have to be terminated, even read access. How to program readers and writers?

To avoid this situation, need to slightly change the program: if the writer process is waiting to access the database, new reader process access does not receive, and is queued for writing process. Now the writing process need to wait, while the base will leave already in her reading processes, but no need to skip ahead of the reading processes, came to the base after him. The disadvantage of this solution is to reduce performance, due to reduced competition. In the solution presented, in which writing processes is a higher priority.

The problem of the sleeping Barber

Action another classic problem situation interprocess communication takes place in a Barber shop. In the Barber shop has one Barber, his chair, and n chairs for visitors. If you want to use his services no, the Barber sits in his chair and sleeps .If the hairdresser comes to the client, he must Wake up the Barber. If a customer comes in and sees, that the Barber is busy, he either sits on a chair (if there is a place), or out (if there is no place). It is necessary to program the Barber and visitors, to avoid race condition. In this task, there are many analogues in the sphere of queueing, for example information service, simultaneously manufacturing a limited number of requests, with computerized system waiting for requests.

 

The proposed solution uses three semaphores: customers, waiting for counting visitors (the client, sitting in the Barber's chair, not count — he is no longer waiting); barbers, the number of Barber (0 or 1), idle while waiting for the client, and mutex to implement mutual exclusion. Also, the variable waiting, designed for counting awaiting visitors.

It is a copy of the variable customers. The presence in the program this variable is due to the fact, to read the current value of the semaphore is impossible. In that decision, the visitor, looking in the Barber shop, should count the number of waiting visitors. If visitors less, than chairs, a new visitor remains, otherwise he leaves.

When the Barber comes to work in the morning, he executes the procedure barber, blockerase on the semaphore customers, because the value of the semaphore is equal to 0. Then the Barber goes to sleep, and sleeping, until the first client.

Coming to the hair salon, the visitor completes the customer, requesting access to a mutex to enter the critical region. If after it will have another visitor, he will not be able to do anything, while the first customer does not release the access mutex. Then the visitor checks the availability of the chairs, in case of failure frees the access to the mutex and goes.

If there is a vacant chair, a visitor increases the value of an integer variable waiting. It then performs the procedure up on the semaphore customers, the

The most activates the flow of Barber. At this point, both the visitor and the Barber — active. When a visitor releases access to mutex, Barber captures it, doing some maintenance tasks and starts to cut the customer.

After cutting the visitor exits the procedure and leaves the Barber shop. Unlike previous programs, cycle visitor no, since every visitor cut only once. The cycle of Barber there is, and the Barber tries to find the next visitor. If he succeeds, he cuts the next visitor, otherwise, the Barber goes to sleep.

It is worth noting, what, despite the lack of data problem readers and writers problem the sleeping Barber, both of these problems relate to the problems of interprocess communication, because they require the synchronization of multiple processes.

 

Reklama