Literatur über Betriebssysteme enthält eine Vielzahl von interessanten Probleme, die breit diskutiert und analysiert mit der Anwendung der verschiedenen Methoden synchronisieren. In diesem Abschnitt betrachten wir die drei am meisten bekannte Probleme.

Das Problem Abendessen Philosophen

In 1965 Jahr Dijkstra formuliert und beschlossen, das Problem der Synchronisierung, genannt Sie ein Problem Abendessen Philosophen. Seitdem jeder, wer erfand ein weiteres neues Objekt synchronisieren, hielt es für seine Pflicht, zu demonstrieren, die Vorteile der neuen Einheit am Beispiel des Problems Abendessen Philosophen. Das Problem kann wie folgt formuliert werden: fünf Philosophen sitzen an einem Runden Tisch, und jeder hat einen Teller mit Spaghetti. Spaghetti so rutschig, dass jeder Philosoph müssen zwei Gabeln, um mit Ihnen fertig. Zwischen jeweils zwei Teller liegt eine Gabel .

Das Leben des Philosophen besteht aus abwechselnden Phasen der Aufnahme der Nahrung und nachdenken. (Natürlich, diese Abstraktion, auch in Bezug auf die Philosophen, aber die anderen Prozesse des Lebens für die Aufgabe irrelevant.) Wenn der Philosoph hungrig, er versucht, zwei Gabeln, Links und rechts, in beliebiger Reihenfolge. Wenn es ihm gelang, sich mit zwei Gabeln, er eine Weile isst, dann legt die Gabel zurück und weiter nachdenken. Die Frage ist wie folgt: kann ich schreiben-Algorithmus, die modelliert diese Schritte für jeden Philosophen und nie stecken? (Jemand glaubt, dass die Notwendigkeit, zwei Gabeln sieht etwas künstlich. Vielleicht, sollten wir ersetzen die italienische Lebensmittel Spezialitäten der chinesischen Küche, Spaghetti — Reis, und die Stecker mit den entsprechenden Stäbchen.)

 

Sie können ändern Sie das Programm so, um nach Erhalt der linken Stecker überprüft die Verfügbarkeit der rechten. Wenn die Rechte Stecker ist nicht verfügbar, der Philosoph gibt die linke zurück, wartet eine Weile und wiederholt den gesamten Prozess. Dieser Ansatz wird auch nicht funktionieren, obwohl Sie aus einem anderen Grund. Wenn Sie nicht das Glück haben, alle fünf Philosophen können beginnen, den Prozess der gleichzeitig, nehmen Sie die linke Stecker, entdecken Sie das fehlen von rechten, setzen Sie die linke wieder auf den Tisch, gleichzeitig nehmen die linke Stecker, und so weiter bis ins unendliche. Die Situation, in dem alle Programme weiterhin so lange wie Sie wollen, aber nicht erreichen können, obwohl jeder Fortschritt, heißt hängenden Prozess (Englisch starvation, wörtlich: «das sterben vor Hunger». Diese

Der Begriff gilt auch in dem Fall, wenn ein Problem Auftritt, nicht in der italienischen oder chinesischen Restaurant, und auf den Computern).

Sie können denken: «Wenn die Philosophen werden, darüber nachzudenken, für einige zufällig ausgewählte Zeitdauer nach dem gescheiterten Versuch, nehmen Sie mit der rechten Stecker, die Wahrscheinlichkeit, dass alle Prozesse werden weiterhin stagnieren, zumindest innerhalb einer Stunde, klein». Das ist richtig, und für die meisten Anwendungen eine Wiederholung der versuche nach einiger Zeit ist das kein Problem. Zum Beispiel, in ein Ethernet-LAN in der Situation, wenn zwei Computer senden Pakete gleichzeitig, jeder muss warten, bis zufällig eine VORGEGEBENE Zeit und versuchen Sie es erneut — in der Praxis ist diese Lösung gut funktioniert. Allerdings ist in einigen Anwendungen ist die bevorzugte eine andere Lösung, läuft immer und unabhängig von den Zufallszahlen (zum Beispiel, in der Anwendung für Sicherheit in Kernkraftwerken).

Sie mit Verbesserung, frei von Deadlocks und hängt Prozess: schützen Sie die fünf Betreiber, der Antrag think, binären einer Semaphore. Dann Philosoph, muss der Vorgang ab auf der mutex-Variable vor, als die Strecke zu Stecker. Und nach der Rückkehr Stecker auf Platz sollte er die Operation Up auf der mutex-Variable. Aus theoretischer Sicht ist die Entscheidung durchaus geeignet. Aus der Sicht der Praxis Probleme mit der Effizienz: zu jedem Zeitpunkt kann ein Spaghetti nur ein Philosoph. Aber fünf Gabeln, deshalb müssen Sie zulassen, dass es in jeder Zeit, die beiden Philosophen.

Lösung, schließt Deadlocks und ermöglicht die maximal mögliche Parallelität für eine beliebige Anzahl von Philosophen. Hier wird ein array von state-Tracking-seelischen Zustand der einzelnen Philosophen: entweder er isst, oder denkt, oder Fasten (Sie versuchen die Stecker). Der Philosoph kann beginnen, nur, wenn keiner seiner Nachbarn nicht isst. Die Nachbarn des Philosophen mit der Nummer i definiert Makros LEFT und RIGHT (das heißt, wenn i = 2, dann LEFT=

Das Problem der Leser und Schriftsteller

Das Problem Abendessen Philosophen nützlich für die Modellierung der Prozesse, die Kämpfer für den exklusiven Zugriff auf eine begrenzte Anzahl von Ressourcen, Z. B. I / O-Geräten. Eine andere bekannte Aufgabe ist es, das Problem der Leser und Schriftsteller [78], der Simulator Zugriff auf die Datenbank. Stellen Sie sich vor, die Datenbank der Buchung von Flugtickets, der versucht, Sie auf eine Vielzahl von Prozessen. Sie können zulassen, dass die gleichzeitige Auslesen der Daten aus der Datenbank, aber wenn der Prozess speichert die Informationen in der Datenbank, der Zugriff der übrigen Prozesse beendet werden soll, auch lese. Wie man Leser und Schriftsteller?

Um diese Situation zu vermeiden, brauchen Sie ein wenig Programm ändern: wenn der schreibende Prozess wartet Zugriff auf die Datenbank, neue liest Prozess Zugriff erhält, und wird in der Linie für einen Prozess. Jetzt пишущему Prozess muss warten, während die Basis verlassen sich bereits in Ihr lesenden Prozesse, aber Sie müssen nicht nach vorne zu springen lesenden Prozesse, die Datenbank nach ihm. Der Nachteil dieser Lösung besteht in der Reduzierung der Leistung, durch die Reduzierung der Konkurrenz. In der Projektmappe, in dem schreibenden Prozesse wird eine höhere Priorität.

Das Problem schlafenden Barbier

Die Aktion noch einer der klassischen Problemsituation Interprozesskommunikation spielt in Friseur. Beim Friseur gibt es eine Pardes, seinen Stuhl, und N und Stühle für die Besucher. Wenn der Wunsch, seine Dienste nicht, Pardes sitzt in seinem Sessel und schläft .Wenn der Friseur kommt der Kunde, er muss aufwachen Barbier. Wenn ein Kunde kommt und sieht, dass Pardes beschäftigt, entweder er setzt sich auf den Stuhl (wenn es einen Ort), entweder raus (wenn der Platz nicht da). Programmieren Sie ein Barbier und Besucher so, um zu vermeiden, Wettlaufsituation. Bei dieser Aufgabe gibt es viele Kollegen, die im Bereich der Warteschlangentheorie, zum Beispiel Informations-Dienst, verarbeitende gleichzeitig eine begrenzte Anzahl von Abfragen, mit dem EDV-System Standby-Abfragen.

 

In der vorgeschlagenen Lösung werden drei Semaphore: customers, für die Berechnung der wartenden Besucher (der Kunde, sitzt in einem Stuhl Barbier, nicht berücksichtigt wird er schon nicht erwartet); barbers, die Anzahl der брадобреев (0 oder 1), im Leerlauf warten auf Kunden, und mutex für die Umsetzung der gegenseitigen Ausschluss. Auch wird die Variable waiting, entwickelt, um zu zählen, warten auf die Besucher.

Es ist eine Kopie der Variable customers. Präsenz im Programm dieser Variablen ist die Tatsache zurückführen, was Lesen Sie den aktuellen Wert der Semaphore unmöglich. In diesem Urteil der Besucher, заглядывающий zum Friseur, sollte zählen die Anzahl der ausstehenden Besucher. Wenn Besucher weniger, als Stühle, neue Besucher bleibt, sonst ist er raus.

Wenn Pardes kommt morgen an die Arbeit, er führt das Verfahren barber, блокируясь auf der Semaphore customers, da der Wert der Semaphore noch 0. Dann Pardes schläft, und schläft, bis der kommt, der erste Kunde.

Kommt zum Friseur, der Besucher führt das Verfahren customer, anfordern von Zugriff auf mutex für die Anmeldung in den kritischen Bereich. Wenn nach ihm wird noch ein Besucher., er ist nicht in der Lage, etwas zu tun, während die ersten Besucher nicht befreien, die Zugriff auf die mutex -. Dann wird der Besucher überprüft, ob die freien Stühle, im Falle des Scheiterns befreit Zugriff auf die mutex-und raus.

Wenn der freie Stuhl haben, der Besucher erhöht den Wert der int-Variablen waiting. Dann führt er die Prozedur up auf der Semaphore customers, Themen

Die Aktivierung der Thread Barbier. In diesem Moment beide — Besucher und Pardes — aktiv. Wenn der Besucher befreit Zugriff auf die mutex -, Pardes erfasst, macht einige Systemprogramme Operation und beginnt zu schneiden Kunden.

Nach Abschluss der Haarschnitt der Besucher kommt aus dem Verfahren und verlässt Friseur. Im Gegensatz zu früheren Programmen, Zyklus der Besucher nicht, da jeder Besucher nur einmal schneiden. Der Zyklus der Barbier gibt es, und Pardes versucht, die nächsten Besucher. Wenn ihm das gelingt, er mäht den nächsten Besucher, andernfalls Pardes schläft.

Es ist erwähnenswert, was, trotz des Fehlens der übertragung der Daten in das Problem der Leser und Autoren und das Problem der schlafenden Barbier, beide diese Probleme beziehen sich auf die Probleme der Interprozesskommunikation, da fordern die Synchronisation mehrerer Prozesse.