Multitasking auf dem ST - Scheduling-Algorithmen
Daß die Computer der Atari ST/TT-Reihe mit einer komfortablen Benutzeroberfläche ausgerüstet sind, ist allgemein bekannt. Trotzdem gibt es immer wieder Kritik am fehlenden Multitasking des GEM, der Eigenschaft also, mehrere Programme quasi gleichzeitig ablaufen zu lassen.
Zwar konnte man in diversen Zeitschriften immer wieder von einem geheimnisvollen GEM/XM hören, das angeblich bei Digital Research in Entwicklung sei, und genau diese Fähigkeiten (bei voller Kompatibilität zum ‘normalen’ GEM) haben solle, doch bis heute warten die Atari-Anwender vergeblich auf diesen Leckerbissen.
Einen ersten Lichtblick gab es dann auf der letztjährigen Atari-Messe in Düsseldorf, als man am MAXON-Stand ein Produkt begutachten konnte, das genau diese fehlende Eigenschaft ‘nachliefern’ soll: MULTIGEM.
Für viele Benutzer dürfte es daher interessant sein, ein wenig mehr über die Techniken des Mehrprogrammbetriebs (Multiprogramming) bzw. Multitaskings zu erfahren. Der folgende Artikel soll einen Einblick in die Möglichkeiten der Implementation eines solchen Programms geben, indem ein Themenbereich etwas genauer untersucht wird: Scheduling.
Ich muß die Leser, die jetzt erwarten, eine komplette ‘Bauanleitung’ zu einem Multitasking-GEM quasi frei Haus geliefert zu bekommen, aber gleich enttäuschen: dies würde den Rahmen dieses Artikels bei weitem (!) sprengen; erstens wäre solch ein Programmierprojekt eine recht knifflige Angelegenheit, und zweitens füllt alleine die vorhandene ‘Grundlagenliteratur’ mittlerweile ganze Regale. Es kann sich also nur um eine kleine Einführung (in die Einführung) der Thematik handeln. So weit alles klar? Gut, dann bitte anschnallen und das Rauchen einstellen, es geht los..
Prozesse
Vorab einige Begriffsklärungen: Unter einem Prozeß soll hier ein Programm verstanden werden, das sich (konkurrierend mit anderen Programmen) um die Gunst des Prozessors bewirbt. Auf einer Ein-Prozessor-Maschine wie dem Atari ST kann zu einem bestimmten Zeitpunkt nämlich immer nur ein Programm aktiv sein. Die Aufgabe eines Schedulers besteht nun darin, festzulegen, in welcher Reihenfolge bestimmte Prozesse (d.h. Programme) der CPU zugeteilt werden sollen bzw. welche erst einmal warten müssen. Dementsprechend befindet sich jeder Prozeß in genau einem der folgenden Zustände:
Bereit: Der Prozeß ‘bewirbt’ sich um die Zuteilung der CPU. Im allgemeinen sind ihm alle anderen Betriebsmittel, wie z.B. bestimmte Speicherbereiche oder Peripheriegeräte (Drucker, Festplatte), vom Betriebssystem bereits zugeteilt worden.
Laufend: Der Prozeß ist gerade aktiv, ist also im Besitz der CPU, die diesen ausführt; davon gibt es auf dem Atari wie gesagt höchstens einen.
Blockiert: Das ist i.a. dann der Fall, wenn der Prozeß auf ein bestimmtes Betriebsmittel wartet, wie z.B. auf das Eintreffen eines Interrupt-Signals, das ihm das Ende einer Ein-/Ausgabeoperation (IO) anzeigt.
Beendet: In diesem Fall hat der Prozeß die CPU schon benutzt, und alle seine Berechnungen auch durchgeführt. Außerdem hat er alle vorher in seinem Besitz befindlichen Betriebsmittel zurückgegeben, die jetzt von einem anderen Prozeß benutzt werden können.
Falls der Scheduler nun der Meinung ist, der gerade aktive Prozeß müsse unterbrochen werden, weil ein anderer (wichtigerer) aufgetreten ist, stoppt er kurzerhand den arbeitenden Prozeß und legt alle wichtigen Daten über diesen im sogenannten Prozeßkontrollblock ab. Diesen Kontrollblock kann man als eine Art Pseudo-CPU bezeichnen; d.h. es handelt sich um eine Struktur, in der alle Registerinhalte des Prozessors zum Zeitpunkt der Unterbrechung sowie die Kennziffer (PID) des laufenden Programms, dessen Zustand und die von diesem benutzten Betriebsmittel festgehalten werden. Abbildung 1 zeigt eine mögliche Implementierung dieses Kontrollblocks in Pascal.
Um einen anderen Prozeß ans Ruder (hier: CPU) zu lassen, genügt es also, den zu diesem Prozeß gehörenden Kontrollblock auszuwerten, die CPU-Register mit den alten Werten und den Programmzähler neu zu laden. Obwohl dieses Vorgehen an sich recht trivial ist, kann es dennoch zu einigen Problemen kommen...
Deadlocks
So kann es z.B. passieren, daß verschiedene Prozesse sich (gleichzeitig) um bestimmte Betriebsmittel bewerben, diese aber nur exklusiv an einen Prozeß vergeben werden können. Im allgemeinen werden diese Betriebsmittel über sogenannte Semaphoren verteilt, spezielle Datenstrukturen, die genau festlegen, wieviele Prozesse maximal auf sie zugreifen dürfen. Falls es dann noch weitere Programme gibt, die diese Mittel nutzen wollen, werden sie erst einmal abgewiesen und in eine Warteschlange (Queue) eingereiht, bis das Betriebsmittel wieder zur Verfügung steht. Diese Prozesse gehen also in den Zustand ‘blockiert’ über (s.o.)
Ganz ärgerlich wird es, wenn ein Programm mehrere Betriebsmittel für sich beansprucht, und zwar gerade die, die auch von einem anderen Prozeß angefordert werden. In einer solchen Situation kann es sehr leicht zu einer Prozeßverklemmung (DEADLOCK) kommen, und dann geht oft nichts mehr! Beispiel: Zwei Prozesse A und B benötigen exklusiv zwei Betriebsmittel M1 und M2. Nehmen wir an, daß A bereits im Besitz von M1 und B im Besitz von M2 ist. Wie soll weiterverfahren werden, vor allem dann, wenn es nicht (oder nur schwer) möglich ist, einem Prozeß ein Betriebsmittel wieder zu entziehen?
Zur Entstehung eines solchen Deadlocks sind grundsätzlich die folgenden Bedingungen notwendig:
- Die beteiligten Prozesse (Programme) verlangen einen exklusiven Zugriff auf bestimmte Betriebsmittel.
- Es gibt Prozesse, die schon über einige Betriebsmittel verfügen, aber noch auf weitere warten.
- Es ist dem Betriebssystem nicht möglich, einem Prozeß einmal zugeteilte Betriebsmittel (BMs) wieder wegzunehmen, ohne daß dieser sie benutzt hat.
- Es existiert eine (geschlossene!) Kette von Prozessen, in der jeder Prozeß über gewisse BM verfügt, die vom nächsten Prozeß in dieser Kette benötigt werden.
Um einen Deadlock zu vermeiden, müßte man also mindestens eine der letzten drei Bedingungen durchbrechen, z.B. in dem man einem Prozeß alle BMs entzieht, wenn ihm ein bestimmtes nicht zugesprochen werden konnte.
Type kontrollblock = record data : array[0..7] of Longint; (* CPU-Datenregister ) adres : array[0..6] of Longint; ( Adreßregister ) stack : array[0..1] of Longint; ( Stackpointer ) pc : Longint; ( Programm-Counter ) status, ( Statusregister ) pid, ( Prozeßkennung ) prior : integer; ( Priorität ) time : Longint; ( (Rest-)Laufzeit *) end;
Abb. 1: Ein Prozeßkontrollblock in Pascal
Scheduling-Strategien
Kommen wir aber jetzt zu dem bereits oben angedeuteten Problem der Zuteilung der CPU an ein bestimmtes Programm, d.h. der Frage, in welcher Reihenfolge die vorhandenen Prozesse abgearbeitet werden sollen.
Es sind diesbezüglich eine Reihe von Verfahren entwickelt worden, von denen ich einige hier kurz erläutern und auch durch kleine Pascal-Programme simulieren möchte. Zur Programmentwicklung habe ich Maxon-Pascal benutzt, das sich vor allem durch das Unit-Konzept vorteilhaft von anderen Systemen abhebt; selbstverständlich kann aber auch jeder andere Pascal-Compiler (wie z.B. ST-Pascal) verwendet werden.
Priorität: Klassen: Scheduling:
hoch system jobs SRTF
interaktive RR
"" editing RR
batch SRTF
niedrig student-jobs FCFS
Abb. 5: Klasseneinteilung bei Multi-Level-Queues
First Come First Serve (FCFS)
Eine der einfachsten Möglichkeiten, die eintreffenden Prozesse in eine abzuarbeitende Reihenfolge zu bringen, ist das FCFS-Prinzip. Hierbei werden alle Aufträge einfach in der Reihenfolge ihres Eintreffens bearbeitet. Da die CPU natürlich immer nur einen Prozeß zu einem bestimmten Zeitpunkt bearbeiten kann, werden alle anderen Prozesse, die während dieser Abarbeitungsphase eintreffen, in eine Warteschlange (FIFO-Queue) eingereiht. Sobald dann der aktive Prozeß beendet wird, holt sich der Scheduler den nächsten Prozeß aus dieser Schlange und übergibt ihn der CPU zur Bearbeitung. Zwar ist dieses Verfahren extrem einfach zu implementieren, es besitzt aber auch einen gravierenden Nachteil: eine große Varianz bei der mittleren Turnaround-Zeit. Hierunter versteht man die Zeit von der Abgabe eines Prozesses an die CPU bis zu dessen Fertigstellung. Es ist wichtig zu wissen, daß der Scheduler nur die Zeit beeinflußt, in der die Aufträge in der Warteschlange sind, denn alle anderen Zeitaufwände wie z.B. die Ausführungszeit der CPU oder Zeiten für Ein-/Ausgabeoperationen sind ja stets und unabhängig von der Reihenfolge der Bearbeitung gegeben.
Abbildung 2 soll dieses Problem noch einmal veranschaulichen. Es werden dort drei verschiedene Prozesse (Tasks) in unterschiedlicher Reihenfolge bearbeitet und die mittlere Turnaround-Zeit berechnet.
Shortest Job First (SJF)
Diese Form des Schedulings versucht stets, den Prozeß als nächsten zu starten, der die kürzeste CPU-Anforderung, also die kürzeste Rechenzeit besitzt. Das Problem ist aber, daß dieser Zeitbedarf normalerweise gar nicht bekannt ist (und auch gar nicht bekannt sein kann!).
Hier hilft dann nur einfaches Schätzen: in der Praxis wird diese Schätzung i.d.R. mit Hilfe des exponentiellen Mittels vorgenommen. Dabei geht man von der Annahme aus, daß künftige Prozesse einen ähnlichen Zeitaufwand haben werden wie die bisherigen. Durch das exponentielle Mittel wird dann ein einfacher Durchschnitt berechnet, wobei aber jüngere Werte (d.h. aktuellere) stärker gewichtet werden als ältere. Somit lassen sich etwaige Trends berücksichtigen.
Ein arges Problem darf aber auch hier nicht verschwiegen werden: Da beim SJF ja immer die Prozesse mit der kürzesten Rechenzeit gestartet werden, kann es leicht passieren, daß einige Tasks einfach nicht bedient werden, weil nämlich ständig andere Prozesse mit einer vermeintlich kürzeren Laufzeit eintreffen. Diesen Vorgang bezeichnet man in der Informatik auch als STARVATION, was aussagen soll, daß Prozesse mit einer hohen Laufzeit schlichtweg ‘verhungern’ müssen.
Daß dieses Problem durchaus ernst zu nehmen ist, wurde spätestens im Jahre 1973 deutlich, als beim Massachusetts Institute of Technology (MIT), dem wohl bekanntesten Forschungszentrum der Welt, eine IBM 7094 abgeschaltet wurde: auf ihr fand man einen Prozeß aus dem Jahr 1967, der immer noch darauf wartete, das ihm die CPU zugesprochen würde!!!
Natürlich gibt es kein Problem, das nicht zu meistern wäre. So kann man sich vor einer Starvation beispielsweise recht wirkungsvoll durch das sogenannte AGING (Alterung) schützen: dabei werden nach Ablauf eines bestimmten Zeitintervalls einfach die Prioritäten der noch nicht zum Zuge gekommenen Prozesse erhöht, beim SJF also z.B. die geschätzte Ausführungszeit verkürzt.
Anzumerken bliebe noch, daß sich viele Scheduler dieses Verfahrens bedienen, da SJF die optimale mittlere Turnaround-Zeit liefert (auf den mathematischen Beweis soll hier aber, wenn er auch recht simpel ist, verzichtet werden). In Abbildung 3 kann die Bearbeitungsreihenfolge (am Beispiel von 4 Prozessen) noch einmal nachvollzogen werden.
Shortest Remaining Time First (SRTF)
Die beiden bisher vorgestellten Verfahren zeichneten sich jeweils dadurch aus, daß die zu bearbeitenden Prozesse in eine bestimmte Reihenfolge gebracht wurden, und - wenn das erst mal geschehen war, just in dieser Folge bearbeitet wurden. Daß solch ein Vorgehen jedoch nicht optimal sein kann, wird klar, wenn man sich folgende Situation vorstellt:
Zu einem bestimmten Zeitpunkt gebe es auf einem Computer nur einen einzigen Prozeß (mit einer relativ langen Ausführungszeit). Da kein anderer Prozeß sich um die CPU bewirbt, wird diesem die CPU zugeteilt und das entsprechende Programm gestartet. Während der Abarbeitungsphase treten dann plötzlich andere Prozesse auf, die aber, da die Zentraleinheit beschäftigt ist, erst einmal warten müssen. Denn sowohl FCFS als auch SJF starten einen neuen Prozeß erst dann, wenn der gerade aktive seine Arbeit beendet hat.
Sehr ärgerlich, vor allem, wenn die wartenden Tasks eine wesentlich höhere Priorität besitzen (also eigentlich ‘wichtiger’ sind) als die gerade aktive. Man bräuchte also ein Verfahren, das den gerade aktiven Prozeß unterbricht, wenn ein wichtigerer auftritt.
Beim Shortest Remaining Time First bezieht sich diese Auswahl auf die Restlaufzeit eines Prozesses. Dabei wird das gerade laufende Programm immer dann vom Scheduler unterbrochen, wenn ein neuer Prozeß mit einer kürzeren Laufzeit als die Restlaufzeit der aktiven Task eintrifft. Die so deaktivierten Programme werden dann als quasi neue Prozesse betrachtet, indem ihre Laufzeit auf die noch verbleibende Restzeit gesetzt wird. (Dies setzt natürlich wie beim SJF voraus, daß man eine grobe Vorstellung davon hat, wie lange ein bestimmter Prozeß die CPU benutzt). Die Reaktivierung dieser Prozesse erfolgt dann nach dem bereits oben beschriebenen Shortest-Job-First-Prinzip. Auch dieser Sachverhalt ist zum besseren Verständnis noch einmal in einer Abbildung (4) zusammengefaßt.
Task-Eintreffen: t0: (T1,8), t1: (T2,4), t2: (T3,9),
t3: (T4,5)
==> Bearbeitung in folgender Reihenfolge:
t0: (T1,8)
t1: (T1,7), (T2,4)
t2: (T1,7), (T2,3), (T3,9)
t3: (T1,7), (T2,2), (T3,9), (T4,5)
...
...
Zeitaufwand: (5+10+17+26)74 = 14,5
Abb. 4: Prozeßverarbeitung beim SRTF
Round Robin (RR)
Beim Round-Robin-Verfahren wird die genaue Festlegung der Bearbeitungsreihenfolge und -zeit noch etwas ‘gerechter’ durchgeführt. Hier kommen alle Tasks wie beim FCFS zunächst in eine FIFO-Queue (den letzten beißen die Hunde). Zusätzlich existiert jedoch ein für alle Prozesse fest vorgegebenes Zeitintervall, so daß bei einer Prozeßbearbeitung die folgenden zwei Fälle auftreten können:
- Die (tatsächliche) Rechenzeit einer Task ist kleiner (oder gleich) dem vorgegebenen Intervall. Dann führt das Programm einfach seine Berechnungen durch und deaktiviert sich anschließend selbst. (Der Scheduler startet dann das nächste Programm aus der Warteschlange).
- Der Zeitbedarf eines Programms ist größer als das festgelegte Intervall. In diesem Fall wird die Task nach Ablauf der Zeitscheibe vom Scheduler unterbrochen und wieder hinten in die Schlange eingereiht. Danach wird das nächste Programm aus der Schlange geholt, gestartet, und das ganze Spiel beginnt von neuem.
Die Kunst dieses Verfahrens liegt also eigentlich darin, einen geeigneten Wert für die Zeitscheibe zu finden. Setzt man den Wert zu hoch an, wird aus dem Round-Robin schnell das bekannte First-Come-First-Serve. Setzt man ihn hingegen zu niedrig an, kommt es zu häufigen Prozeßumschaltungen (Context-Switches), was wiederum unnötig viel Zeit kostet, da ja jedesmal der Prozessorstatus im Kontrollblock gesichert und ein neuer geladen werden muß. Es gibt zwar Rechner, die dieses Problem nicht so hart trifft, da sie mit mehreren Registersätzen ausgestattet sind (Beispiel: SPARC der Sun-4: 8 Sätze), nur nützt uns das auf dem Atari natürlich herzlich wenig. Der Vollständigkeit halber sei noch erwähnt, daß die in der Praxis benutzten Scheduling-Algorithmen i.d.R. mit Zeitscheiben von 10-20ms arbeiten.
Multi Level Queues
Eine weitere (und beliebte) Scheduling-Strategie ist die der Multi Level Queues. Es handelt sich hierbei im Prinzip um eine Mischung aus Prioritäten-Scheduling und anderen Algorithmen. Bei diesem Verfahren werden alle auftretenden Tasks in spezielle Klassen eingeteilt. So gibt es etwa Klassen für System-Jobs, Stapelverarbeitung (Batch-Processing), allgemeine User-Jobs oder ähnliches. Jeder Klasse wird dabei eine festgelegte Priorität zugeordnet (vgl. Abbildung 5), so daß bestimmte Prozesse stets Vorrang vor solchen in einer niedrigeren priorisierten Klasse haben. Innerhalb einer solchen Klasse können die Prozesse dann z.B. nach dem gerade beschriebenen Round-Robin-Verfahren der CPU zugeteilt werden.
Dabei ist es wichtig zu betonen, daß die einmal getroffene Prioritätenfestlegung strikt ist. Auf Abbildung 5 bezogen, bedeutet das beispielsweise, daß ‘Studenten-Jobs’ nur dann bearbeitet werden können, wenn alle darüber liegenden Warteschlangen leer sind.
Multi Level Feedback Queues
Das letzte Verfahren, das ich Ihnen vorstellen möchte, geht noch einen etwas anderen Weg: Hier werden werden ähnlich wie beim Round-Robin Zeitscheiben definiert, die die Verarbeitung eines Prozesses auf eine bestimmte Zeit begrenzen. Im Gegensatz zum Round-Robin existiert hier jedoch nicht nur eine solche Schranke, sondern mehrere. Konkret: Man konstruiert sich verschiedene Warteschlangen mit jeweils festgelegter maximaler CPU-Benutzung. Jeder auftretende Prozeß wird dann zunächst in die Schlange mit der kleinsten Bearbeitungszeit eingereiht. Entweder reicht das dort gesetzte Limit zur Bearbeitung des Jobs aus, oder die Task wandert in die nächste Schlange (mit einer großzügiger ausgelegten Zeitspanne) usw.
In der letzten dieser Schlangen könnten die Prozesse dann z.B. nach dem zu Anfang beschriebenen FCFS-Prinzip verwaltet werden; somit ist sichergestellt, daß alle Programme auch tatsächlich komplett bearbeitet werden.
Ran an die Tasten
Nach so viel Theorie wenden wir uns nun den Programm-Listings zu. Bei den Listings 3 und 4 handelt es sich um die eigentlichen Hauptprogramme, die eine Prozeßverarbeitung nach dem Round-Robin- bzw. Multi-Level-Queue-Verfahren simulieren. Aber der Reihe nach: In Listing 1 finden Sie eine Pascal-Unit, die verschiedene Prozeduren zur Erstellung und Verwaltung von Warteschlangen enthält. (ST-Pascal-Benutzer und solche, deren Compiler keine Units unterstützen, müssen diese in das Hauptprogramm mit einbinden). Ich gehe an dieser Stelle davon aus, daß Sie die Arbeitsweise einer solchen Schlange bereits kennen; Einzelheiten zur Funktion der einzelnen Routinen entnehmen Sie bitte dem kommentierten Listing (1).
Die zur Bearbeitung der vorhandenen Prozesse notwendigen Prozeduren wurden ebenfalls in eine eigene Unit ausgelagert (Listing 2). task_state gibt den aktuellen Status eines Prozesses aus, schedule_rr steuert die Abarbeitung der in den Warteschlangen vorhandenen Prozesse nach dem oben beschriebenen Round-Robin-Verfahren. Bei der Funktion work_task handelt es sich um eine spezielle Unterroutine dieses Schedulers, die jeden Prozeß eine bestimmte Zeit arbeiten läßt und ihn danach deaktiviert.
Das Nachvollziehen der Bearbeitungsreihenfolge der beiden Simulationsprogramme sollte Ihnen (aufgrund der oben stehenden, theoretischen Überlegungen) keine Probleme bereiten. Trotzdem noch ein paar Worte zum Ablauf: Nach dem Starten der Programme wird zuerst eine Meldung auf dem Bildschirm ausgegeben, die u.a. anzeigt, um welche Art des Schedulings es sich handelt. Danach wird versucht, die notwendigen Prozeßdaten vom aktuellen Laufwerk einzulesen; diese Daten müssen in einem File of task untergebracht sein, das den Namen tasks.in trägt. Die Komponenten task.pid und task.ankunft werden zur Bearbeitung der Prozesse eigentlich nicht benötigt; sie werden jedoch innerhalb von task_state als Prozeßinformation mit ausgegeben. Das Multi-Level-Queue-Verfahren wurde von mir mit vier verschiedenen Warteschlangen realisiert. Aus diesem Grund sollten Sie darauf achten, als Task-Prioritäten nur die Ziffern von 1 bis 4 zu wählen, da ansonsten ein Einfügen in die entsprechenden Warteschlangen nicht möglich ist. (Die Ziffer 1 steht dabei übrigens für hohe, die 4 für niedrige Priorität...)
Anschließend können Sie einen beliebigen (ganzzahligen, positiven) Wert für die Zeitscheibe(n) eingeben. Danach wird der Scheduler gestartet, der die Verarbeitung der Prozesse steuert. Nach dem Ende der Simulation kommen Sie mit einem ‘Return’ zur aufrufenden Umgebung (z.B. Desktop) zurück.
Abschließend möchte ich noch einige Hinweise zur Entwicklung eines ‘echten’ Multitasking-Kerns geben: Zur Unterbrechung eines laufenden Programmes bietet sich im ST z.B. der Timer-A des MFP an. Diesen Timer könnten Sie mit einem geeigneten Wert für die Zeitscheibe (z.B. 10ms) programmieren, so daß nach Ablauf dieser Frist eine eigene Interrupt-Routine angesprungen wird, die das Umschalten der Prozesse übernimmt (die geretteten Parameter des gestoppten Programms in einen Prozeßkontrollblock packen, einen neuen laden usw.) Um möglichst sauber zu programmieren, sollten Sie dabei zwei Dinge nicht vergessen; erstens sollte bei jedem Verbiegen eines Systemvektors eine XBRA-Struktur angelegt werden (es gibt leider immer noch Programmierer, die sich nicht an dieses Konzept halten!), und zweitens sollten Sie sich bei allen Stack-Manipulationen darüber im klaren sein, welchen Prozessor Sie vor sich haben. Der MC-68030 im Atari-TT packt nämlich einiges mehr an Informationen auf den Stack, so daß man schnell auf falsche Parameter zugreift, wenn man nicht aufpaßt. Der vorhandene Prozessor läßt sich z.B. durch den Cookie-Jar abfragen, und auch die Systemvariable $59E ist in diesem Zusammenhang recht nützlich: sie enthält den Wert NULL , wenn der Prozessor 6 Bytes bei Trap-Aufrufen auf dem Stack ablegt, anderenfalls werden dort 8 Bytes hinterlegt.
Anmerkungen
So, damit ist unsere kleine Einführung in die Scheduling-Strategien erst einmal beendet. Ich hoffe, dem einen oder anderen Leser die Grundtechniken dieser Verfahren zumindest ansatzweise verdeutlicht zu haben. Natürlich können im Rahmen eines solchen Artikels nicht alle Aspekte ausreichend angesprochen werden; insbesondere sei noch einmal darauf hingewiesen, daß die hier vorgestellten Algorithmen hauptsächlich in Ein-Prozessor-Maschinen Verwendung finden. Richtig interessant wird die Sache aber erst dann, wenn man es mit Mehrprozessor-Maschinen wie z.B. der Atari Transputer Workstation (ATW) zu tun hat, von der man in den letzten Monaten leider auch nichts mehr hört; sollten Sie jetzt Blut geleckt haben, kann ich Sie auf die unten angegebene Literatur verweisen...
Doch es müssen ja nicht gleich Transputer oder ein MultiGEM-Projekt sein, auf das Sie sich nun stürzen: Vielleicht implementiert der eine oder andere von Ihnen ja einen ‘kleinen’ Multitasking-Kern in eines seiner eigenen Programme. Es ist doch einfach toll, wenn man wie z.B. in Phoenix umfangreiche Sortierungen vornehmen kann und gleichzeitig neue Daten eingibt, während im Hintergrund exportiert wird und, und, und...
Literatur:
[1] Oberschelp/Vossen, „Rechneraufbau und Rechner Strukturen“, Oldenbourg-Verlag, 3.Auflage 1989
[2] Andrew S. Tanenbaum, „Operating Systems: Design and Implementation“, Prentice-Hall
[3] Franz-Josef Rammig, Skriptum zur „Informatik B“, Universität-GH Paderborn, SS 1990
[4] Rudolf Pichler, „Multitasking zum Selbermachen“, c't Magazin 06/90, Seite 304 ff.
(*
Programm : Extended Standard-Library
Unit : queue.pas
Funktion : Implementation des abstrakten
Datentyps 'Schlange'
Edit : 09.04.91
Autor : Rolf Kotzian, Paderborn
Copyright (c) MAXON Computer 1991
*)
UNIT Queue;
(* Public-Symbols *)
Interface
Type task =
record
pid : integer; (* Prozeßkennung *)
ankunft, (* Ankunftszeit *)
laenge : Longint; (* geschätzte Ausführungszeit *)
prior : integer, (* Priorität *)
end;
Squeue = ^Selem;
Schlange = record
anfang, ende : Squeue;
end;
Selem = record
value : task;
rest : Squeue;
end;
(* Prototyping *)
procedure create_queue (var schlange: Schlange);
function is_empty_queue (schlange: Schlange): boolean;
procedure front (schlange Schlange;
var t: task);
procedure deq_queue (var schlange: Schlange);
procedure enq_queue (var schlange: Schlange,
t: task);
(* Private Symbols *)
Implementation
(* 'create_queue': erzeugt leere Schlange *)
procedure create_queue (var schlange: Schlange);
begin
schlange.ende := Nil;
end; (* create_queue *)
(* 'is empty queue': prüft, ob Schlange leer... *)
function is_empty_queue (schlange: Schlange): boolean;
begin
is_empty_queue = (schlange.ende = Nil);
end; (* is_empty_queue *)
(* 'front' liefert (vorderstes) Element der Schlange... *)
procedure front (schlange Schlange;
var t: task);
var dummy: ^Selem;
begin
if not is_empty_queue (schlange) then
begin
dummy := schlange.anfang;
t.pid := dummy^.value.pid;
t.ankunft := dummy^.value.ankunft;
t.laenge := dummy^.value.laenge;
t.prior := dummy^.value.prior;
end;
end; (* front *)
(* 'deq_queue’: entfernt (vorderstes) Element
der Schlange... *)
procedure deq_queue (schlange: Schlange);
var dummy: ^Selem;
begin
if not is_empty_queue (schlange) then
begin
dummy := schlange.anfang;
schlange.anfang = schlange.anfang^.rest,
if schlange.anfang = Nil then
schlange.ende := Nil;
dispose (dummy);
end;
end; (* deq_queue *)
(* 'enq_queue': hängt neues Element (hinten) an
die Schlange *)
procedure enq_queue (var schlange: Schlange;
t: task);
var dummy : ^Selem;
began
new (dummy);
dummy^.value.pid := t.pid,
dummy^.value.ankunft := t.ankunft,
dummy^.value.laenge := t.laenge,
dummy^.value.prior := t.prior;
dummy^.rest := Nil;
if schlange.ende = Nil then
schlange.anfang := dummy
else schlange.ende^.rest := dummy;
schlange.ende := dummy;
end (* enq_queue *)
Begin
End (* End of Unit 'queue' *)
(*
Programm: Scheduling-Simulator
Unit : tasks.pas
Funktion: Hilfsroutinen zum Task-Handling
Edit : 13.04.91
Autor : Rolf Kotzian, Paderborn
Copyright (c) MAXON Computer 1991
*)
UNIT Tasks;
(* Public Symbols *)
Interface
Uses Queue:
(* Prototyping *)
procedure task_state (t: task);
procedure work_task (var s:Schlange;
var t:task;
time: integer);
procedure schedule_rr (var s:Schlange;
time_slice: integer);
(* Private Symbols *)
Implementation
(* 'task_state': wird bei jedem Aufruf der Task
't' aufgerufen und gibt deren
aktuellen Zustand wie folgt
aus:
- Prozeßkennung (PID)
- Ankunftszeit der Task
- (geschätzte) (Rest-) Laufzeit
- Priorität
*)
procedure task_state (t: task);
begin
Write (t.pid:2, ' ', t.ankunft:8);
Write (' ', t.laenge 8);
Writeln (t.prior:11);
end; (* task_state *)
(* 'work_task': lässt den Prozess 't' genau
'time' Zeiteinheiten arbeiten
und stoppt
diesen anschließend. *)
procedure work_task (var s:Schlange, var t:task;
time: integer);
var i: integer;
begin
task_state (t);
for i := 1 to time do
(* Unsere Task darf jetzt genau 'time'
Zeiteinheiten schuften ! *)
(* Restlaufzeit ermitteln *)
t.laenge := t.laenge - time;
if t.laenge > 0 then
(* Task wieder einreihen *)
enq_queue(s, t);
(* Schlangenkopf entfernen *)
deq_queue (s);
end; (* work_task *)
(* 'schedule_rr': Scheduling-Algorithmus, b.d.
die Prozesse nach dem Round-
Robin Verfahren (RR)
ausgewählt werden... *)
procedure schedule_rr (var s: Schlange;
time_slice: integer);
var t: task;
time: integer;
begin
(* Es wird so lange gearbeitet, bis alle
Prozesse komplett bedient wurden, die
Warteschlange also leer ist *)
while not is_empty_queue(s) do
begin
(* erste Taks aus der Warteschlange holen... *)
front (s,t);
(* reicht das Limit der Zeitscheibe
zur vollständigen Bearbeitung der Task aus ? *)
if t.laenge > time_slice then
(* Nein ! *)
work_task (s, t, time_slice)
else (* Ja, Limit reicht aus ! *)
work_task (s, t, t.laenge);
end;
end; (* schedule_rr *)
Begin
End (* End of Unit 'Tasks' *)
(*
Programm : Scheduling-Simulator
Modul : Round_Robin.pas
Funktion : Prozeßverarbeitung nach dem
Round-Robin Verfahren
Edit : 13.04.91
Autor : Rolf Kotzian, Paderborn
Copyright: (c) MAXON Computer 1991
*)
Program Round_Robin (input, output);
Uses Queue, Tasks;
(* Variablen-Vereinbarungen *)
Var dat : File of task;
t : task;
s : Schlange;
time_slice: integer;
Begin (* Main *)
ClrScr;
Writeln ('Scheduling-Simulator');
Write ('Prozeßverarbeitung nach dem 1);
Writeln ('Round-Robin Verfahren');
Writeln ('by Rolf Kotzian, Paderborn');
Writeln;
Writeln ('(c) 1991 MAXON Computer GmbH');
Writeln; Writeln;
Reset (dat, 'tasks.in');
if IOresult = 0 then
begin
(* leere Warteschlange erzeugen *)
create_queue (s);
while not eof (dat) do
begin
(* Prozeßdaten aus File
lesen und in eine Warte-
schlange einfügen *)
Read (dat, t);
enq_queue (s, t);
end;
end
else
begin
(* leider konnte das File 'tasks in' nicht gelesen werden *)
Writeln ('Kann Daten nicht lesen '');
Halt;
end;
Write ('Wie groß ist die Zeitscheibe? ');
Readln (time_slice); Writeln;
(* Nun wird der Scheduler aufgerufen, der die
Bearbeitung der Tasks steuert *)
Write ('PID: ANKUNFT LÄNGE: ');
Writeln (' PRIORITÄT: ');
Write (' ============================') ;
Writeln (' ==========');
Writeln;
schedule_rr (s, time_slice);
Readln;
End. (* Main *)
(*
Programm : Scheduling-Simulator
Modul : Multi_Level_Queue.pas
Funktion : Prozeßverarbeitung nach dem MLQ-Verfahren
Edit : 14.04.91
Autor : Rolf Kotzian. Paderborn
Copyright (c) MAXON Computer 1991
*)
Program Multi_Level_Queue (input, output);
Uses Queue, Tasks;
(* Variablen-Vereinbarungen *)
Var dat : File of task;
t : task;
s : array[1..4] of Schlange;
time: array[1 .4] of integer;
Begin (* MAIN *)
ClrScr;
Writeln ('Scheduling-Simulator');
Write ('Prozeßverarbeitung nach dem ’);
Writeln ('Multi-Level-Queue Verfahren');
Writeln ('by Rolf Kotzian, Paderborn');
Writeln;
Writeln ('(c) 1991 MAXON Computer GmbH');
Writeln; Writeln;
Reset (dat, 'tasks.in');
if IOResult = 0 then
begin
(* leere Warteschlangen erzeugen *)
create_queue (s[1]);
create_queue (s[2]);
create_queue (s[3]);
create_queue (s[4]);
while not eof (dat) do
begin
(* die Prozessdaten werden aus
dem File gelesen, und in die
entsprechende Warteschlange
(abhängig von der Priorität)
eingereiht... *)
Read (dat, t);
enq_queue (s[t.prior], t);
end;
end
else
begin
(* leider konnte das File 'tasks.in'
nicht gelesen werden... *)
Writeln ('Kann Daten nicht lesen !');
Halt;
end;
(* Nun werden die Zeitscheiben für jede zu
bearbeitende Klasse festgelegt *)
Write ('Zeitscheibe der Klasse 1 ');
Readln (time[1]);
Write ('Zeitscheibe der Klasse 2 '),
Readln (time[2]);
Write ('Zeitscheibe der Klasse 3 ');
Readln (time[3]);
Write ('Zeitscheibe der Klasse 4 ');
Readln (time[4]);
(* Jede Klasse wird wiederum nach dem
Round-Robin Verfahren bearbeitet... *)
Write ('PID: ANKUNFT: LÄNGE: ');
Writeln (' PRIORITÄT ');
Write ('=============================');
Writeln ('===========');
Writeln;
schedule_rr (s[1], time[1]);
schedule_rr (s[2], time[2]);
schedule_rr (s[3], time[3]);
schedule_rr (s[4], time[4]);
Readln;
End. (* MAIN *)
Rolf Kotzian