Inhaltsverzeichnis

  Aufgabenstellung dieses Beleges  3

1  Entwicklung eines einfachen Simulations-Schedulers  4

1.1  Das Haupt-Programm (Main)  4

1.1.1  Start der Prozesse und des Schedulers  4

1.1.2  Implementierung des Schedulers  5

1.2  Signal ubermittlung  6

1.3  Anlegen eines Z ahlprozesses  6

1.4  Der Scheduling-Algorithmus Round Robin  7

1.4.1  Theorie zum Algorithmus Round Robin  7

1.4.2  Implementierung des Algorithmus Round Robin  7

1.5  Der Scheduling-Algorithmus Lottery Scheduling  8

1.5.1  Theorie zum Algorithmus Lottery Scheduling  8

1.5.2  Implementierung des Algorithmus Lottery Scheduling  9

1.6  Der Scheduling-Algorithmus Priority Scheduling  10

1.6.1  Theorie zum Algorithmus Priority Scheduling  10

1.6.2  Implementierung des Algorithmus Priority Scheduling  10

1.6.3  Berechnungs-Beispiel f ur den Algorithmus Priority Scheduling  12

2  Entwicklung eines Simulators f ur das Dining-Philosophers-Problem  13

2.1  Inhalt des Dining-Philosophers-Problem  13

2.2  Theoretische Herangehensweise an das Dining- Philosophers-Problem  14

2.3  Simulator f ur das Dining-Philosophers-Problem  15

2.3.1  DiningSimulator  15

1

2.4  Aufbau und Arbeitsweise der Prozesse  16

3  Eine L osung des Dining-Philosophers-Problems auf Scheduler-Ebene  18

3.1  Ein zweiter Simulator f ur das Dining-Philosophers-Problem: L osung auf  

  Ebene des Schedulers  18

3.1.1  Das Haupt-Programm (Main) und Anlegen der Prozesse sowie  

  der ben otigten Dateien  18

3.1.2  Die Funktionen file-random und take-file  19

3.1.3  Auswertung der Dateiinhalte und Aufruf des passenden Prozesses  20

A  Quelltext der Datei scheduler.c (zu Kapitel 1)  23

B  Quelltext der Datei dining.c (zu Kapitel 2)  28

C  Quelltext der Datei dining2.c (zu Kapitel 3)  35

D  Aufruf-Beispiele f ur die Simulations-Programme  41

  D.1 Aufruf-Beispiel f ur den Algorithmus Round Robin  41

  D.2 Aufruf-Beispiel f ur den Algorithmus Lottery Scheduling  42

  D.3 Aufruf-Beispiel f ur den Algorithmus Priority Scheduling  44

  Literaturverzeichnis  46

2

  Tabellenverzeichnis  

1.1  Gestartete Prozesse beim Priority-Scheduling  11

1.2  Berechnungsbeispiel f ur den Algorithmus Priority Scheduling  12

2.1  Datei-  

  Anderungen  17

3.1  Aufgerufene Dateien in Abh angigkeit von Zufallszahlen  20

3.2  Reaktionen auf m ogliche Dateiinhalte der drei Dateien  22

3

Aufgabenstellung dieses Beleges

Dieser Beleg besteht aus zwei Teilen, die verschiedene Aspekte eines Betriebssystems simulieren sollen.

Aufgabe des ersten Teils dieses Belegs ist es, einen Scheduler zu entwickeln. Er soll im Benutzermodus und nicht auf Betriebssystemebene laufen. Außerdem sind drei einfache Prozesse zu entwickeln, die lediglich im Halbsekundentakt aufw¨ arts z¨ ahlen und dies ausgeben. Der Scheduler soll daf¨ ur verantwortlich sein, den Prozessen Signale zu schicken, um sie zu starten beziehungsweise zu pausieren. Dabei sollen folgende Scheduling-Algorithmen realisiert werden:

• Round Robin

• Lottery Scheduling und

• Priority Scheduling.

Im zweiten Teil soll das Dining-Philosophers-Problem simuliert werden. Demgem¨ aß soll ein Prozess nur laufen, wenn er zwei nicht-teilbare Ressourcen binden konnte. Auch daf¨ ur soll ein passender Scheduler entwickelt werden.

Im folgenden m¨ ochte ich die Herangehensweise an diese Probleme erl¨ autern. Dabei werde ich bei der Erkl¨ arung des Quellcodes jeweils auf den theoretischen Hintergrund mit eingehen und diesen ebenfalls erkl¨ aren.

4

Kapitel 1

Entwicklung eines einfachen

Simulations-Schedulers

1.1 Das Haupt-Programm (Main)

1.1.1 Start der Prozesse und des Schedulers

Das Hauptprogramm dient dazu, die einzelnen Prozesse zu starten und den Scheduler zu steuern. Daher ist der Scheduler auch im Hauptprogramm implementiert. Zun¨ achst ist es n¨ otig, die einzelnen Variablen anzulegen. Dazu z¨ ahlen die PIDs der einzelnen Prozesse sowie des Schedulers, damit man diese Prozesse sp¨ ater ¨ uber Signale

mit der jeweiligen Prozessnummer ansprechen kann. Die PIDs gen¨ ugen dem einfachen Systemdatentyp pid_t, der in der Headerdatei definiert ist. Neue Prozesse werden mit fork beziehungsweise mit vfork angelegt. Durch vfork ist es m¨ oglich, im Kindprozess wieder neue Prozesse aufzurufen oder Programme auszuf¨ uhren. Dabei wird nicht der gesamte Adressbereich des Elternprozesses zum Kindprozess kopiert. Obwohl ich mich f¨ ur die erweiterte Funktion vfork entschieden habe, w¨ are es in diesem Fall genauso m¨ oglich, fork zu verwenden. Die Funktionen fork und vfork liefern als R¨ uckgabewerte 0 an den Kindprozess, wenn der Prozess richtig aufgerufen wurde beziehungsweise -1 im Fehlerfall sowie die Prozessnummer des Kindprozesses an den Elternprozess.

Der folgende Programm-Abschnitt legt gem¨ aß den oben beschriebenen Algorith-

5

men die 3 Prozesse an, indem er jeweils das Unterprogramm prozess(Nr) aufruft. Zum Schluss wird der Scheduler aufgerufen, seine Implementierung wird weiter unten erkl¨ art (siehe Abschnitt 1.1.2). Es ist m¨ oglich, den Scheduler erst nach dem Anlegen der Prozesse aufzurufen, da die Prozesse sofort nach dem Start schlafen gelegt werden und auf Anweisungen vom Scheduler warten (siehe Abschnitt 1.3).

if((proc1_pid=vfork()) == 0) prozess(1); else if((proc2_pid=vfork()) == 0) prozess(2); else if((proc3_pid=vfork()) == 0) prozess(3);

else if((scheduler_pid=vfork()) == 0) { Implementierung des Schedulers; siehe unten } else printf("Fehler beim Anlegen der Prozesse oder des Schedulers.\n");

Ist es nicht m¨ oglich, einen der Prozesse beziehungsweise den Scheduler aufzurufen, dann wird eine Fehlermeldung ausgegeben.

1.1.2 Implementierung des Schedulers

Zu Beginn werden im Bildschirmprotokoll die PIDs des Schedulers und der Prozesse ausgegeben. Danach folgt eine Auswahlroutine, in der der Benutzer den von ihm gew¨ unschten Scheduling-Algorithmus ausw¨ ahlen kann. Zur Auswahl stehen Round Robin, Lottery Scheduling und Priority Scheduling. Die Funktionsweise der einzelnen Algorithmen wird in den folgenden Abschnitten noch genauer erkl¨ art. Bei einer ung¨ ultigen Eingabe hat der Benutzer die M¨ oglichkeit, nochmals zwischen den 3 Algorithmen zu w¨ ahlen. Bei richtiger Eingabe wird jeweils das f¨ ur den Algorithmus zust¨ andige Unterprogramm aufgerufen. Als Parameter werden den Unterprogrammen roundrobin und lottery_scheduling jeweils die 3 Prozess-PIDs ¨ ubergeben, dem

Unterprogramm priority_scheduling werden zus¨ atzlich zu den PIDs die Priorit¨ aten der Prozesse ¨ ubergeben. Diese wurden vorher im Scheduler ermittelt beziehungsweise festgelegt. Im Beispiel wurde festgelegt, dass der erste Prozess 50% der Zeit laufen soll, Prozess 2 soll zu 30% laufen und Prozess 3 20% der Gesamtzeit. Diese Priorit¨ aten k¨ onnten durchaus auch ge¨ andert oder anderweitig berechnet werden.

6

1.2 Signal¨ ubermittlung

Da es bei allen Scheduling-Algorithmen notwendig ist, Signale zu ¨ ubertragen, m¨ ochte ich zun¨ achst einmal darauf eingehen.

Die Funktion kill, die in der Headerdatei definiert ist, sendet ein Signal an einen Prozess. Sie erwartet die Prozess-PID als Argument. Außerdem kann man noch eine Funktionsnummer ¨ ubergeben. Ich m¨ ochte hier nur die f¨ ur den Scheduler relevanten Funktionsnummern erw¨ ahnen. Mit der Funktionsnummer 17 kann man Prozesse schlafen legen, wogegen die Funktionsnummer 19 Prozesse wieder aufweckt. Den Aufruf der Funktion kill soll folgendes Beispiel verdeutlichen:

kill(proc1_pid, 19); // Prozess aufwecken kill(proc2_pid, 17); // Prozess schlafen legen

1.3 Anlegen eines Z¨ ahlprozesses

Das Anlegen der Z¨ ahlprozesse erledigt das Unterprogramm prozess. Es erwartet eine Nummer, f¨ ur den jeweiligen Prozess, der aufgerufen werden soll. Diese Nummer ist in diesem Fall eine fortlaufende Nummer zur Unterscheidung der Prozesse und ist von der Prozess-PID verschieden. Im Beispiel werden die Prozesse mit den Nummern 1, 2 und 3 aufgerufen.

Im Unterprogramm prozess wird zun¨ achst einmal der neu angelegte Prozess schlafen gelegt. Das geschieht mit der Funktion kill mit der Funktionsnummer 17 f¨ ur das Pausieren eines Prozesses (siehe Abschnitt 1.2). Der Aufruf lautet: kill(self_pid, 17) wobei die Variable self_pid lediglich die PID des Prozesses mit getpid() bestimmt. Erst wenn der Prozess vom Scheduler ein Signal bekommt, arbeitet er weiter. Nun wird der eigentliche Prozess in einer Endlosschleife ausgef¨ uhrt. Dabei wird zun¨ achst usleep(500000) aufgerufen. Die Funktionen sleep und usleep halten den jeweiligen Prozess an, bis die angegebene regul¨ are Zeit verstrichen ist oder bis ein Signal eintrifft. Der Unterschied zwischen sleep und usleep liegt darin, dass sleep die Zeit in Sekunden erwartet und usleep in Mikrosekunden. Die Zeitangabe muss als nat¨ urliche Zahl erfolgen (Typ integer). Da der Prozess jeweils im Halbsekundentakt z¨ ahlen sollte habe ich mich f¨ ur die Funktion usleep entschieden und ihr den Parameter

7

ubergeben (0,5 Sekunden = 500 Millisekunden = 500000 Mikrosekunden). 500000 ¨

Nach der Wartezeit von 0,5 Sekunden wird die Z¨ ahlvariable n um 1 erh¨ oht (zu Beginn betr¨ agt n=0). Jetzt folgt die Konsolenausgabe, die die Prozess-Nummer darstellt, sowie den aktuellen Stand der Z¨ ahlvariable.

All das geschieht st¨ andig in der Endlosschleife, wobei der Prozess nur laufen kann, wenn er vom Scheduler aufgerufen wird.

1.4 Der Scheduling-Algorithmus Round Robin

1.4.1 Theorie zum Algorithmus Round Robin

Beim Algorithmus Round Robin kommt jeder Prozess gleich h¨ aufig dran. Die Reihenfolge, in der die Prozesse arbeiten d¨ urfen, ist genau festgelegt und bei jedem Durchlauf gleich (im Beispiel: Prozess 1 - Prozess 2 - Prozess 3 - Prozess 1 - . . .). Ebenso ist die Zeit, die ein Prozess zur Verf¨ ugung hat, immer die gleiche. Dieser Algorithmus ist der einfachste zur Realisierung eines Schedulers. Jedoch ist er auch nicht sehr effizient, da er keine R¨ ucksicht auf die Priorit¨ at der Prozesse nimmt. Dringlichere Prozesse k¨ onnen nicht schneller abgearbeitet werden als v¨ ollig unwichtige. Daher lassen sich auch keine zeitkritischen Anwendungen realisieren.

1.4.2 Implementierung des Algorithmus Round Robin

Zun¨ achst wird die Variable next_process angelegt, die angibt, welcher Prozess als n¨ achstes laufen soll. Zu Beginn hat next_process den Wert 1, damit als erstes der Prozess 1 laufen kann. Nun wird in einer Endlosschleife jeweils der Wert der Variable next_process abgefragt und in Abh¨ angigkeit davon der jeweilige Zweig aufgerufen (1 bis 3, f¨ ur die 3 Prozesse). Nimmt next_process einen anderen Wert an, so wird eine Fehlermeldung ausgegeben. Diese Abfrage findet in einer switch-Anweisung statt. Jeder der drei Zweige arbeitet folgendermaßen: Zun¨ achst wird der Prozess mit der Funktion kill und der Funktionsnummer 19 aufgeweckt (siehe Abschnitt 1.2). Danach wird der Scheduler f¨ ur eine vorher festgelegte Zeit angehalten. Diese Zeit wird in der Variable run_time gespeichert und der Funktion sleep ¨ ubergeben. Im Beispiel wurde

run_time vorher auf 3 Sekunden gesetzt. Damit l¨ auft der Prozess nun f¨ ur 3 Sekunden.

8

Nun wird der Prozess mit der Funktion kill und der Funktionsnummer 17 pausiert. Jetzt wird der n¨ achste Prozess aufgerufen, das heißt die Variable next_process wird auf den n¨ achsten Prozess, der laufen soll, gesetzt. Beim n¨ achsten Durchlauf der switch- Anweisungwird dann dieser Prozess gestartet.

Folgender sehr einfacher Quellcode f¨ ur den Round Robin-Algorithmus w¨ are auch m¨ oglich:

void roundrobin2(proc1, proc2, proc3) { int run_time = 3; while(0==0) { kill(proc1, 19); sleep(run_time); kill(proc1, 17); kill(proc2, 19); sleep(run_time); kill(proc2, 17); kill(proc3, 19); sleep(run_time); kill(proc3, 17); } }

Dabei k¨ onnte man auf die Variable next_process v¨ ollig verzichten. Auch die switch- Anweisungw¨ urde ¨ uberfl¨ ussig werden. F¨ ur die Reihenfolge Prozess 1 - Prozess 2 - Prozess 3 - Prozess 1 - . . . w¨ are dieser Algorithmus v¨ ollig ausreichend. Der Vorteil der zuerst geschilderten Variante liegt jedoch darin, dass man als Programmierer die Reihenfolge auch ohne großen Aufwand ¨ andern kann. Daf¨ ur braucht man lediglich die Variable next_process auf einen anderen als den logisch folgenden Prozess zu setzen.

1.5 Der Scheduling-Algorithmus Lottery Scheduling

1.5.1 Theorie zum Algorithmus Lottery Scheduling

Beim Lottery Scheduling ist weder die Reihenfolge der Prozess vorher festgelegt noch die H¨ aufigkeit, in der sie aufgerufen werden. Das wird alles erst zur Laufzeit zuf¨ allig

9