Betriebssysteme: Aufgaben, Fragen und Antworten
Geschwurbel von Daniel Schwamm (12.09.1994 bis 23.09.1994)
Stoffsammlung
Der Stapelbetrieb - wie sieht der aus?
Beim Stapelbetrieb werden auf Platte befindliche Aufträge vom Betriebssystem
(BS) der Reihe nach (also sequenziell und nie parallel) abgearbeitet. Die
Abarbeitung erfolgt in den Stufen Kompilierung, Programmlauf, Druckausgabe.
Alle Objekte, mit denen das BS hantiert, werden in einer Objekt-Liste
verwaltet; dazu gehören Daten, Geräte und der Arbeitsspeicher. Die
Objekt-Liste enthält Angaben über den Programmnamen, seine Position
auf der Platte und seine Länge. Dateien werden von der Platte geholt,
kompiliert, auf Platte geschrieben, in die Objektliste aufgenommen und dann
ausgeführt. Neu erzeugte Objekte müssen in die Liste aufgenommen
werden, eine Löschung aus der Liste bedeutet immer auch eine physikalische
Löschung.
Skizzieren Sie den Ablauf eines Stapelbetriebs in
Pascal-Pseudocode! Folgende Dienste stehen Ihnen dabei zur Verfügung:
trage-objekt-in-objektliste,
lösche-objekt-aus-objektliste,
suche-object-in-objektliste,
schreibe-auf-platte,
schreibe-auf-drucker,
belege-arbeitsspeicher,
gib-arbeitsspeicher-frei,
lade-objekt-in-arbeitsspeicher.
Antwort:
FUNCTION main: fehler
WHILE Auftrag vorhanden DO
starte:
Kennung=lies_Benutzerkennung;
// Benutzerkennung prüfen
IF NOT Benutzerzugelassen(Kennung)
THEN GOTO starte;
initialisiere:
initialisiere_druckprotokoll;
lade_compiler:
prog="compiler";
dat="programm";
suche-objekt-in-objektliste(prog);
// Fehlerbehandlung
belege-arbeitsspeicher(prog);
// BS weiss Länge über Objekt-Liste
lade-objekt-in-arbeitsspeicher(prog);
compile_and_bind(dat);
// Übersetzen und Binden von "programm"
schreibe_auf_platte("ausführbares-prg");
trage-objekt-in-objektliste("ausführbares-programm");
gib-arbeitsspeicher-frei;
lade_programm:
prog="ausführbares-programm";
dat="daten";
suche-objekt-in-objektliste(prog);
// Fehlerbehandlung
belege-arbeitsspeicher(prog);
lade-objekt-in-arbeitsspeicher(prog);
starte_prg(prog);
// verarbeite "daten" mittels "ausführbares-programm"
schreibe-auf-drucker("druck-daten")
gib-arbeitsspeicher-frei(prog);
lösche-objekt-aus-objektliste(prog);
rechne-systemleistung-ab;
schliesse-druckprotokoll;
END;
END.
Was versteht man unter einem mehrstufigen Scheduling, wie
es MINIX verwendet? Welche Gefahr ist damit verbunden und mit welcher
Strategie kann man dieser Gefahr entgegenwirken?
Die Prozesse werden in verschiedene Klassen verschiedener Priorität
aufgeteilt. Höchste Priorität haben Ausgabe-Tasks, dann folgen
Dienstprozesse (Server) und dann Benutzerprozesse (Clients). Jede
Prioritätsklasse wird mit einer eigenen Queue verwaltet. Es gilt,
dass jeweils die höheren Prioritäten vor den niedrigeren
Prioritäten abgearbeitet werden. Damit ist die Gefahr verbunden, dass
einige Prozesse nie zum Zug kommen, v.a. dann, wenn ein Anwenderprozess
nicht korrekt terminiert. MINIX verwendet hier die Round Robin-Strategie,
die jedem Prozess ein bestimmtes Zeitquantum zuordnet.
Welche Zustände nehmen MINIX-Prozessoren ein (Zustandsdiagramm)?
laufend
Blockieren (Ein-/Ausgabe) Zuteilen Abgeben (Scheduler-Zwang)
blockiert bereit
Eingabe wird verfügbar
Schreiben Sie eine Scheduling-Prozedur "pic_proc()" in C,
die in MINIX den jeweils nächsten Task auswählt. Die Queues
werden über zwei Tabellen verwaltet: rdy_head[queue] zeigt auf den Anfang,
rdy_tail[queue] auf das Ende von "queue", wobei "queue" "TASK_Q", "SERVER_Q"
oder "USER_Q" sein kann. Ein "NIL_PROC"-Wert bedeutet Schlangenende. "proc_ptr"
muss auf den Prozesskontrollblock zeigen; der
"IDLE"-Prozessblock für "cur_proc=IDLE" wird durch "addr(HARDWARE)"
angegeben. "bill_ptr" zeigt auf den, der die CPU-Zeit zu zahlen hat (nur
Prozess >= LOW_USER). "prev_proc" muss vermerkt werden, damit bei
einem Interrupt (Alarm-Signal) während der Prozedur die Register richtig
gesetzt werden.
Globale Variablen in MINIX: cur_proc, prev_proc, realtime
Drei Verteiler-Schlangen : NQ (anzahl), TASK_Q, SERVER_Q, USER_Q
void pic_proc() {
int queue;
// Wähle aktuell-wichtigste Scheduling-Queue aus
if(rdy_head[TASK_Q]!=NIL_PROC)
queue=TASK_Q;
else if(rdy_head[SERVER_Q]!=NIL_PROC)
queue=SERVER_Q;
else queue=USER_Q;
// Vorgänger merken, falls jetzt Interrupt kommt
prev_proc=cur_proc;
// neuer Prozess vorhanden?
if(rdy_head[queue]!=NIL_PROC) {
// aktuelle Prozessnummer bestimmen
cur_proc=rdy_head[queue]->nr;
// Verweis auf Prozesskontrollblock
proc_ptr=rdy_head[queue];
// muss User zahlen?
if(cur_proc>=LOW_USER)
bill_ptr=proc_ptr;
}
else {
cur_proc=IDLE;
proc_ptr=proc_addr(HARDWARE);
bill_ptr=proc_ptr;
};
};
Blockierte Prozesse werden nach ihrer Reaktivierung am Ende
seiner Queue eingereiht. Ein terminierter oder blockierter Prozess dagegen
wird aus seiner Queue entnommen. Schreiben Sie die Prozeduren "ready" und
"unready"! In der Queue zeigt "next_ready" auf nächsten Eintrag.
struct proc {
p_pid, user_time, p_alarm (Zeit, bis nächster Alarm in Ticks),
p_messbuf (Nachrichtenspeicher), p_sp (Stack-Pointer),
p_reg[NR_REGS]
} proc[NR_PROGS];
void ready(proc) {
lock(); // blockiere Interrupts
// wähle Queue-Klasse aus!
if(proc->nr<0)
queue=TASK_Q;
else if(proc->nr<höchster systemprozess)
queue=SERVER_Q;
else queue=USER_Q;
// wenn Queue leer ist,
// dann trage proc am Anfang ein, sonst am Ende
if(rdy_head[queue]==NIL_PROC)
rdy_head[queue]=proc;
else rdy_tail[queue]->next_ready=proc;
rdy_tail[queue]=proc;
proc->next_ready=nil;
restore(); // Interrupts freigeben
};
void unready(proc) {
// entferne proc aus Queue und terminiere bzw. reaktiviere proc
lock();
if(proc.nr<0) queue=TASK_Q;
else if(proc.n<höchster systemprozess) queue=SERVER_Q;
else queue=USER_Q;
// hole Schlangenkopf
qp=rdy_head[queue];
// Schlange leer, dann Ende!
if(qp==NIL_PROC)
restore & return;
// stimmt Kopf mit Anforderung überein,
// dann Köpfe die Schlange und aktiviere Prozess
if(qp==proc) {
rdy_head[queue]=qp->next_ready;
if(proc==proc_ptr)
pick_proc();
}
else {
// suche gewünschten Prozess in Queue
while(qp->next_ready!=proc) {
qp=qp->next_ready;
// Schlangenende erreicht ohne Prozess zu finden
if(qp==PROC_NIL)
restore & return;
};
// proc aus Queue entfernen, qp evtl. zum Ende machen
qp->next_ready=qp->next_ready->next_ready;
if(qp->next_ready==NIL_PROC)
rdy_tail[queue]=qp;
};
restore(); // Interrupts freigeben
};
Die Round-Robin-Strategie benachteiligt interaktive
Prozesse. Warum? Wie liesse sich dem entgegenwirken?
Bei der Round-Robin-Strategie bekommt jeder Prozess ein
festes Zeitquantum zugewiesen (i.d.R. ca. 100 ms), das jeder Prozess voll
ausschöpfen kann. Interaktive Prozesse benötigen aber oft die
Prozessorzeit nicht, weil sie auf Benutzereingaben warten müssen - wenn
diese dann erfolgen, können sie u.U. nicht gleich reagieren, da sie nicht
vorne in der Queue stehen. Dem könnte man entgegenwirken, indem man die
verbrauchte CPU-Zeit in den Scheduling-Tabellen pro Task vermerken würde.
Der Queue-Header würde dann jeweils auf dem Task mit der niedrigsten
CPU-Zeit stehen.
Andere Alternative: Beim Apriori-Scheduling bekommen n User pro
Prozess 1/n CPU-Zeit zugewiesen. Die Anspruchszeit ist Anmeldezeit/n.
Der Prozess mit der jeweils höchsten Anspruchszeit steht vorne in der Schlange.
Welche drei Nachrichtendienste stellt MINIX dem User zur
Verfügung? Was versteht man dabei unter dem Rendezvous-Konzept?
MINIX stellt die Nachrichtendienste "send(dest, msg)", "receive(src, msg)" und
"sendrec(dest, msg)" zur Verfügung. Der letzte Dienst erwartet eine Rückantwort
auf die Message. Das Rendezvous-Konzept besagt, dass ein Server auf die vom Client
kommende Anforderung warten muss, ansonsten wird der Client so lange
blockiert, bis die Sendung doch ohne Pufferung geschehen kann, d.h. bis der
Server "receive()" aufruft.
Sendungen werden in MINIX über die Anti-Deadlock-Funktion "sys_call()" aufgerufen,
was wiederum "mini_send()" oder "mini_receive()" zur Folge hat. Wie wird demnach
eine Anforderung an einen Server abgesetzt? Wie wird das Ergebnis geliefert? Zeigen
Sie die Funktionen "sys_call()"!
struct message {
m_source,
m_type,
union {
Messagetypen 1-6
} m_u
};
void sys_call(int fkt, int caller, int src_dest, message *msg) {
if(fkt & SEND) {
n=mini_send(caller, src_dest, msg); // SEND or BOTH
if(n!=OK)
return;
};
if(fkt & RECEIVE)
n=mini_rec(caller, src_dest, msg); // RECEIVE or BOTH
};
Bedeutung von "mini_rec(caller, src_dest, mptr)": Signalisiert,
dass Caller Botschaft empfangen will. Holt Nachrichten aus Schlange und
entblockiert über "unready()" Sender. Falls keine Nachricht vorhanden ist,
blockiert sich der Prozess mit "ready()" und setzt Flags auf RECEIVING.
Die Funktion "sys_call()" wird über ein Assemblerprogramm aufgerufen,
welches durch einen Software-Interrupt (Trap) aktiviert wird. Bei Aufruf
von "send()" bzw. "sendrec()" des Clients ist "msg" ein Pointer auf den
Ausgabepuffer. Ein Server-Prozess nimmt den Aufruf entgegen und wird
gegenüber dem Kern zum Client, indem er denjenigen SW-Interrupt aktiviert,
der Sendungen losschickt oder diese zu empfangen erlaubt, indem er "sys_call()"
aktiviert. Beim Empfang wird "msg" schliesslich zum Pointer auf den
Empfangspuffer, aus dem der Client dann das Ergebnis entnehmen kann.
Wie gross ist die CPU-Effizienz bei Round-Robin in
den Fällen (1) Q=Unendlich, (2) Q>T, (3) S<Q<T, (4) Q=S und (5) Q
fast Null, wobei Q=Quantum, S=Prozessumschaltung und T=Laufzeit bis
Blockierung?
Im Fall (1) hat jeder Prozess die CPU so lange, bis er
terminiert, d.h., bei Blockierung behält er die CPU bei (Business Waiting):
Die Effizienz wächst mit steigender Prozessanzahl gegen null. Auch
im Fall (b) wird das Zeitquantum grösser gemacht, als es den
Anforderungen entspricht, wodurch CPU-Zeit verschwendet wird. Der Fall (3)
scheint ein geeignetes Quantum zu beinhalten, wird hier doch jedem Prozess
nicht zu viel Zeit, aber auch nicht zu wenig zugeordnet. Fall (4): Hier
wird für die Verwaltung der Prozesse ebenso viel Zeit benötigt, wie
für deren aktive Arbeit, woraus eine maximale Effizienz von 50% folgt. Im
Fall (5) wiederum strebt die Effizienz gegen null, da der Grossteil der
CPU für unverhältnismässig viele Aktionen zur Prozessumschaltung
verschwendet wird.
Implementieren Sie die Funktionen "Send(caller, mb)" und
"receive(caller, mb) für den Botschaftsaustausch. Die Botschaften
liegen in Mailboxen, welche durch die Semaphore "mutex" geschützt werden.
Jede Mailbox, die aus n Speicherblöcken besteht, führt die Variablen
"full" und "empty" (belegte und freie Speicherblöcke-Anzahl). Jeder
Prozess i bekommt eine Semaphore "s[i]" zugewiesen. Für Prozesse, die
auf eine volle bzw. leere Mailbox schreiben bzw. lesen wollen, existieren pro
Mailbox zwei Warteschlangen. Folgende Funktionen sind definiert: insert(queue,
caller), remove(queue, caller), empty(queue), insert_message(mailbox) und
remove_message(mailbox).
empty=zählt Sender pro Mailbox; am Anfang=n.
full=wenn >0, dann mindestens eine Nachricht in Mailbox; am Anfang=0.
void SEND(caller, mb) { // Sende Message in Mailbox mb
P(mutex); // blockiere für andere Zugriff auf mb
// wenn mb voll, dann lege Botschaft in Schlange ab
if(mb.empty==0) {
insert(mb.send-queue, caller);
V(mutex); // gib mb frei
P(s[caller]); // blockiere Sendeprozess (bis Rendezvous)
P(mutex); // blockiere für andere Zugriff auf mb
};
insert_message(mb); // Nachricht von Schlange in Mailbox
mb.empty--; // ein Speicherblock weniger frei
mb.full++; // ein Speicherblock mehr belegt
// Wenn die Empfangs-Queue nicht leer ist, leere sie!
if(!empty(mb.receive-queue))
V(s[remove(mb.receive-queue)]); // entblockiere Sender
V(mutex); // gib mb frei
};
void RECEIVE(caller, mb) { // empfange Message aus Mailbox mb
P(mutex); // blockiere für andere zugriff auf mb
// wenn mb leer, dann lege Queue-Platz an und warte auf msg!
if(mb.full==0) {
insert(mb.receive-queue, caller);
V(mutex); // entblockiere mb
P(s[caller]); // blockiere Empfangsprozess
P(mutex);
};
remove_message(mb);
mb.empty++;
mb.full--;
// wenn Sendedaten vorhanden in Queue, schaufle sie in mb!
if(!empty(mb.send-queue))
V(s(remove(mb.send-queue)]); // gib fremden Empfänger frei
V(mutex);
};
Was versteht man unter einem Watch-Dog?
Eine Funktion, die nach einer bestimmten Zeit durch ein
Alarm-Ereignis aktiviert wird. Initiiert wird das Alarm-Ereignis durch einen
Prozess, der sich dadurch selbst verzögern kann. Beispiel: Ein BS-Task
kann das Disketten-Laufwerk nicht sofort im vollen Umfang benutzen, sondern
muss einen Watch-Dog aktivieren, der den Task so lange blockiert, bis das
Laufwerk seine volle Umdrehungsgeschwindigkeit erreicht hat.
Implementieren Sie einen Watch-Dog für das
Disketten-Laufwerk (Prozessnummer=floppy): Solange der Motor nicht voll
dreht, soll der BS-Task, der es nutzen will, eine bestimmte Zeit warten
müssen. Mögliche Nachrichten an den Clock-Task sind "mess.type",
"mess.clock_proc_nr", "mess.delta_ticks" und "mess.func_to_call". Die Alarmzeit wird
im Prozessblock unter dem Feld "alarm" angegeben. Globale Variable sind
"watch_dog[Prozessoranzahl]", "realtime" und "next_alarm", Nachrichtentypen
sind "set_alarm" und "motor_running".
void message_to_clock(ticks, function) {
// fülle Message-Felder
mess.type=set_alarm;
mess.clock_proc_nr=floppy;
mess.delta_ticks=ticks;
mess.func_to_call=func;
// versende Nachricht an Clock-Task, erwarte Antwort!
sendrec(clock, &mess);
};
void send_message() { // Funktion, die nach ticks aktiviert wird
mess.type=motor_running;
send(floppy, &mess);
};
void set_alarm(ticks, function) {
// hole Messagedaten
proc_nr=mess.clock_proc_nr;
delta_ticks=mess.delta_ticks;
function=mess.func_to_call;
// setzte im Prozesskontrollblock Alarmzeit
rp=proc_addr(proc_nr);
rp->alarm=realtime+deltaticks;
// weise dem Prozess für den Alarmfall seine Watch-Dog-Funktion zu
watch_dog[proc_nr]=function;
// bestimme den frühsten Alarmzeitpunkt unter allen Prozessen
next_alarm=maxint;
for(proc_nr=0; proc_nr<maximale Prozessanzahl; proc_nr++) {
rp=proc_addr(proc_nr);
if(rp->alarm!=0 && rp->alarm<next_alarm)
next_alarm=rp->alarm;
};
};
Behandlungsroutine (wird pro neuer "realtime" durchlaufen!):
if(next_alarm<=realtime) {
// Bestimmung next-alarm nötig, da alter next-alarm-Prozess
// evtl. inzwischen terminiert ist!
next_alarm=maxint;
for(proc_nr=0; proc_nr<maximale Prozessanzahl; proc_nr++) {
rp=proc_addr(proc_nr);
if(rp->alarm!=0)
if(rp->alarm<=realtime) {
(*watch_dog[proc_nr])(); // starte Func
rp->alarm=0;
}
else if(rp->alarm<next_alarm)
next_alarm=rp->alarm;
};
};
Zwei Prozesse P1 und P2 greifen (1) nacheinander und (2)
gleichzeitig auf die durch Semaphore geschützte Ressourcen S1 und S2 zu.
Geben Sie die dafür nötigen Programmabschnitte an!
Im Fall (1) müssen beide Prozesse zuerst Ressource S1
blockieren und wieder freigeben und danach Ressource S2. Dies geschieht durch:
P(S1) ... V(S1) ... P(S2) ... V(S2). Im Fall (2) müssen sich die Prozesse
das Zugriffsrecht auf beide Ressourcen sichern, die sie danach in beliebiger
Reihenfolge wieder freigeben können. Dies geschieht durch: P(S1); P(S2)
... V(S2); V(S1); Im Fall (2) muss die Blockierung in fester Reihenfolge
erfolgen, da sonst die Gefahr eines Deadlocks besteht.
Geben Sie einen Prozess-Betriebsmittel-Graph für
die vorherige Aufgabe an! Ab welcher Zuteilung welchen Betriebsmittels kann
der Deadlock erkannt werden?
R1 P1
P2 R2
Wenn man die zukünftigen Anforderungen der Ressourcen
kennt, dann lässt sich ein Deadlock bereits bei der Zuteilung von R2
an P2 erkennen. Es gilt: Maximale Gesamtanforderung g=[[1 1][1 1]] (=>P1 und
P2 belegen beide S1 und S2), belegte Ressourcen b=[[1 0][0 0]] (=>P1 hat S1
belegt), verbleibende Anforderung a=[[0 1][1 1]] (=>P1 wird noch S2 belegen,
P2 noch S1 und S2 belegen) und verfügbare Ressourcen v=[1 1] (=>es gibt
die Ressourcen S1 und S2 genau einmal). Daraus folgt: f=v-b=[0 1] (=>S1 ist
belegt, S2 frei). Wird nun S2 an P2 geben, dann gilt: f=[0 0], d.h. die
verbleibenden Anforderungen von P1 (a1=[0 1]) und P2 (a2=[1 0]) lassen sich
nicht mehr erfüllen, da sie grösser als f sind.
Wenn man die zukünftigen Anforderungen nach Ressourcen kennt,
wann besteht dann noch die Gefahr von Deadlocks? Geben Sie einen
Algorithmus zur Erkennung solcher Deadlocks an. Es sei:
v(r)=Gesamtressourcenzahl, g(p, r)=Gesamtanforderung, b(p, r)=Belegte
Einheiten, und a(p, r)=Gewünschte Einheiten, wobei p Element aus Prozessen
und r Element aus Ressourcen ist.
Wenn die Reihenfolge der Allokation nicht fest vorgeschrieben
ist, so kann es bei bekannten Anforderungen zu Deadlocks kommen. Diese lassen
sich durch folgenden Algorithmus erkennen:
int deadlockbedroht(P, r, v, b, a) {
for(alle p Element P) {
// bestimme frei-verfügbare Ressourcen für den Prozess p
f=v(r);
for(alle pp Element P)
f=f-b(pp,r);
// genügen diese Ressourcen dem Prozess p
if(a(p,r)<=f)
P=P-{p}; // okay, nimm p aus der Menge
};
return (P==leere Menge)?FALSE:TRUE;
};
Stellen Sie fest, ob die Prozesse P1-P4
deadlockgefährdet sind, wenn (1) P1 eine Einheit von R1 zugeteilt
wird, oder (2) P2 eine Einheit von R1 zugeteilt wird! Gegeben ist: v=[5 4 3],
g=[[3 2 1][3 1 1][3 1 3][2 2 0] und b=[[0 1 0][0 1 1][1 1 1][1 1 0]].
Zunächst einmal lassen sich die noch gewünschten Einheiten bestimmen:
a=g-b=[[3 1 1][3 0 0][2 0 2][1 1 0]]
Betrachten wir Fall (1): R1 wird P1 zugewiesen
=> a1=a1-1*P1=[2 1 1], b1=b1+1*P1=[1 1 0] => a und b verändert!
=> f=v-Summe(bi)=[5 4 3]-[1+0+1+1 1+1+1+1 0+1+1+0]=[2 0 1]
=> ist f>=a1 <=> [2 0 1]>=[2 1 1]? Nein, daher Deadlockgefahr!
Betrachten wir Fall (2): R1 wird P2 zugewiesen
=> a2=[2 0 0], b2=[1 1 1]
=> f=[5 4 3]-[3 4 2]=[2 0 1] // identisch mit oben (immer!)
=> f>=a2 <=> [2 0 1]>=[2 0 0]? Ja, Allokation okay!
=> P2-Ressourcen werden frei: f=f+b2=[2 0 1]+[1 1 1]=[3 1 2]
=> nun kann P1 befriedigt werden, da [3 1 2]>=[3 1 2] => f=[3 2 2]
=> das genügt für P4 => f=[4 3 3]
=> das genügt für P3 => f=[5 4 3]
Eine Freispeicherliste hat folgende Blöcke: 10k, 4 k,
20k, 18k, 7k, 9k, 12k und 15k. Welche Blöcke werden bei der
Übertragung von 12k, 10k und 9k unter Anwendung von (1) "first fit" und
(2) "best fit" belegt?
Die (1) First-Fit-Strategie suchten den ersten passenden Block
aus und allokiert ihn für die Anforderung. Daraus ergibt sich: Die
Blöcke 20k, 10k und 18k werden allokiert. Die (2) Best-Fit-Strategie sucht
den am Besten passenden Block zur Allokation aus. Daraus ergibt sich: Die Blöcke
12k, 10k und 9k werden belegt.
Was versteht man unter Speicherpartitionierung und welche
Vorteile ergeben sich dadurch?
Häufig werden Speicheranforderungen in der Reihenfolge
ihres Eintreffens bearbeitet. Dadurch geht es oft nicht fair zu, weil der Erste
u.U. alles für sich beanspruchen kann und der Nächste überhaupt
nichts mehr bekommt. Durch Speicherpartitionierung kann man dies verhindern:
Hier kann jeder Prozess nur einen bestimmten Speicherbereich allokieren
und nicht mehr.
Wenn zwei Prozesse Daten austauschen, können sie dabei
auf einen gemeinsamen Pufferpool zurückgreifen, wobei der lesende
Prozess den Speicher für den schreibenden Prozess jeweils als
frei markiert. Überlegen Sie sich eine passende Puffer-Struktur
(Memory-Block fester Grösse) und eine Puffer-Pool-Struktur (jeder
Pool verwaltet viele Puffer), wenn die knappe Ressource Speicher über
Semaphore verwaltet wird!
struct buffer {
char *mem_block; // Startadresse des Puffers
int poolid; // gehört zu welchem Pool?
buffer *next; // Zeiger auf nächsten Puffer oder NULL
};
struct bpool {
int bpsize; // Anzahl der möglichen Puffer
buffer *bpnext; // Zeiger auf nächsten Puffer-Pool
int bpsem; // Semaphore zum Zählen der Freipuffer
};
bpool bptab[5];
Wie wird der Semaphore verwendet für die Verwaltung
der Puffer-Pools?
Es wird nach folgendem Algorithmus verfahren:
WENN Prozess Speicher benötig DANN
Zähler um eins erniedrigen;
WENN Zähler<0 DANN
Prozess blockieren;
Prozess in Warteschlange eintragen;
WENN Prozess Speicher freigibt DANN
WENN Zähler<0 DANN
Prozess aus Warteschlange herausnehmen;
Zähler um eins erhöhen;
Wenn der Semaphore-Zähler kleiner Null ist, dann gibt die
negative Zahl an, wie viele Prozesse darauf warten, dass der
Speicherbereich mit V(Semaphore) entblockiert wird.
Unter Betrachtung der vorherigen Ergebnisse: Schreiben Sie
die Funktionen "buffer *getbuf(int poolid)", "void freebuf(buffer *buf)" und
"int mkpool(int bufsize, int numbufs)", woebei "mkpool" die Pool-ID
zurückgibt und MINIX folgende Funktionen bereitstellt: "char
*getmem(unsigned nbytes" und "void freemem(char *base, unsigned nbytes)"!
int mkpool(int bufsize, int numbufs) {
mask=lock; // Interrupts sperren
if(!ok(bufsize, numbufs, nbpool) // Rahmenbedingungen prüfen
return -1;
poolid=nbpool++; // nbpool global, initiiert mit 0
// Speicher für Buffer-Pool-Element allokieren
buf=(buffer *)getmem(numbufs*sizeof(buffer));
// Speicher für Puffer allokieren
char* chunks=getmem(numbufs*BUFFERSIZE);
bptab[poolid].bpnext=buf;
bptab[poolid].bpsize=numbufs;
bptab[poolid].bpsem=numbufs; // Semaphore-Grösse=alle Freiblöcke
// weise jedem Puffer-Element seine Inhalte zu
while(numbufs>0) {
buf->poolid=poolid;
buf->mem_block=chunks;
if(numbufs>1)
buf->next=buf+1; // funktioniert durch Zeigerarithmetik
else buf->next=NULL;
buf++; // entspricht: buf=buf->next
chunks+=BUFFERSIZE; // neue Startadresse für Puffer
numbufs--;
};
restore(mask); // Interrupts zulassen
return poolid;
};
buffer *getbuf(int poolid) {
mask=lock; // Interrupts sperren
P(bptab[poolid].bpsem); // kritischen Bereich sichern
buf=bptab[poolid].bpnext; // nächster freier Speicherblock
bptab[poolid].bpnext=buf->next;
restore(mask); // Interrupts entsperren
return buf;
};
void freebuf(buffer *buf) {
mask=lock;
buf->next=bptab[buf->poolid].bpnext;
bptab[buf->poolid].bpnext=buf; // Speicherblock wieder freigeben
V(bptab[buf->poolid].bpsem); // kritischen Bereich freigeben
restore(mask);
};
Was versteht man unter der Arbeitsmenge (Workingset)?
Was ist über seine Grösse zu sagen?
Die Arbeitsmenge Wp(t, r) des Prozesses P zum Zeitpunkt t ist
die Menge der Seiten, die im Zeitintervall (t-r, t)=[t-r+1 t-1] referiert
wurden, wobei r ein fixer Zeitraum ist. Es gilt: Die Wahrscheinlichkeit,
dass die nächste referierte Seite zu Wp(t, r) gehört, ist
grösser, als dass sie nicht dazugehört. Die
Grösse wp(t, r) der Arbeitsmenge Wp(t, r) hängt also davon ab,
wie häufig auf gleiche Seiten zugegriffen wird. Als Mittelwert setzten wir
wp(r).
Was versteht man unter Seitenfehler-Wahrscheinlichkeit
Delta-p(r)? Wie lässt sie sich bestimmen?
Delta-p(r) gibt an, mit welcher Wahrscheinlichkeit eine
referierte Seite nicht zur Arbeitsmenge Wp(t, r) gehört. Wir können
diese Grösse durch die Seitenfehlerrate mp(r) bestimmen, die das
Verhältnis von Seitenfehlern und Speicherzugriffen wiedergibt.
Zeigen Sie, dass gilt: w(h)<=w(h+1), wobei
h=maximale Grösse des Workingsets, dass also die
durchschnittliche Grösse des Arbeitsbereichs im Laufe der Zeit stets
grösser wird oder gleichgross bleibt!
Die Grösse des Workingsets Wp(t, r) hängt davon
ab, wie häufig verschiedene Seiten referenziert werden. Da in einem
wachsenden Zeitraum die Häufigkeit für die Referenzierung einer
bestimmten Seite, die noch nicht im Workingset ist, wodurch ein Seitenfehler
entsteht, nur zunehmen oder gleich bleiben kann, ändert sich auch die
mittlere Grösse eines Workingsets in der gleichen Weise. Es gilt
daher für Seitenwechselrate mp(r)=m(h): w(h+1)=w(h)+m(h).
Welcher Zusammenhang besteht zwischen der
durchschnittlichen Grösse des Workingsets w(h) und der mittleren
Seitenfehlerrate m(h)?
Wie wir bereits in der vorherigen Aufgabe erkannt haben, nimmt
der Workingset im Zeitablauf monoton zu, da er um die Seiten erweitert wird,
die bei ihrer Referenzierung Seitenfehler ausgelöst haben. Daher gilt:
w(h+1)=w(h)+m(h)!
Zeichen Sie ein Diagramm, welches w(h) in Abhängigkeit
von h angibt (ein Programm habe dazu n Seiten)! Wie kann daraus die
mittlere Seitenfehlerrate abgelesen werden?
Zunächst gilt m(h)=0 für n>=h, d.h. nachdem alle
Seiten einmal referenziert wurden, kommt es zu keinen Seitenfehlern mehr. Da
die Zahl der Seitenfehler bei wachsender Arbeitsmenge abnimmt, wächst die
w(h)-Funktion aufgrund der Gleichung w(h+1)=w(h)+m(h) nicht linear, sondern
abnehmend wachsend. Die mittlere Seitenfehlerrate entspricht dann gerade der
Steigung der Kurve.
w(h)
n
h
==> m(h)=Steigung=y/x=(w(hj)-w(hi))/(hj-hi)
Gegeben sei ein Programm mit den Seiten S={1,2,...10}.
Geben Sie für die Seitenreferenzfolge F={3,4,3,6,1,6,5,4,8,2,7,9,3,2,1}
die folgenden Grössen an: W(7,5), W(5,7), w(3) und m(3)! Dabei
sei ein Referenzzähler auf jeder Seite, der, wenn er kleiner Null ist,
signalisiert, dass die Seite nicht mehr im Workingset ist.
Arbeitsmenge W(t, r) bedeutet: Menge der Seiten, die vom
Zeitpunkt t-r an bis zum Zeitpunkt t referenziert wurden. Das ergibt in unserem
Fall: W(7,5)=(2 7)=[3 6]={3,6,1,5} und W(5,7)=(0 5)=[1 4]={3,4,6,1}.
Mittlere Grösse der Arbeitsmenge w(h) bedeutet, wie viele Seiten im
Schnitt im Zeitraum h allokiert sind, und m(h) gibt die durchschnittliche
Fehlerrate in diesem Zeitraum an. Der Workingset wird bei diesem Beispiel
abgebaut, wenn eine Seite doppelt vorkommt! In unserem Fall gilt (für
h=3):
3 3 4 4 3 1 1 6 5 4 8 2 7 9 3
4 3 3 6 6 6 5 4 8 2 7 9 3 2
6 1 5 4 8 2 7 9 3 2 1
m(h):1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 ==> w(3)=1+3*2+11*3/15=40/15=2.666
==> m(3)=13/15=0.9
Was ist die wesentliche Motivation beim Multiprogramming?
Die CPU besser auszulasten. Das lohnt sich v.a., wenn viele
Prozesse öfter durch Ein- und Ausgabeoperationen blockiert sind, z.B.
durch das Einladen einer referenzierten Seite, und ein Scheduler dadurch einem
anderen Task leicht die CPU für die Dauer der Blockierung zuweisen
könnte.
Der Multiprogramming-Grad sei n, den Teil p seiner Zeit
verbringt jeder Prozess mit Warten. Wie hoch ist die durchschnittliche
Auslastung der CPU?
Wenn p die Wahrscheinlichkeit für das Warten eines
Prozesses ist, so ist p^n die Wahrscheinlichkeit dafür, dass alle
Prozesse warten. 1-p^n gibt dann folgerichtig die Wahrscheinlichkeit dafür
an, dass mindestens ein Prozess aktiv ist, dass also die CPU
belegt ist. Dem entspricht die durchschnittliche Auslastung der CPU.
Unter Berücksichtigung der vorherigen Ergebnisse: p sei
0.8 bzw. 0.2, der Hauptspeicher umfasst 1 MB, jeder Prozess
benötigt 200 kB. Stellen Sie die CPU-Auslastung grafisch in
Abhängigkeit von der Prozessanzahl n dar!
p
p=0.2
p=0.8
n
p\n | 1 2 3 4 5
----------------------------------
.8 | .2 .36 .48 .59 .67 <==> 1-p^n
.2 | .8 .89 .99 ...
Hinter obiger Grafik stecken zwei Ergebnisse, nämlich: Je
höher die Wahrscheinlichkeit dafür ist, dass ein Prozess
wartet, desto eher wird die CPU nicht ausgelastet. Je kleiner die
Prozesszahl, desto eher wird die CPU nicht ausgelastet. man erkennt
dadurch, dass sich der Durchsatz steigern lässt, wenn man den
Hauptspeicher erhöht, weil dann mehr Prozesse gleichzeitig im Speicher
stehen, die weniger Seitenfehler verursachen (was jeweils zum Einladen der
Seite eine Blockierung zur Folge hätte). Bei 1 MB sind nur 1 MB/200 kB=5
Prozesse im Speicher haltbar, bei 2 MB wären es bereits 10 Prozesse,
wodurch sich die Auslastung bei p=0.8 von 0.67 auf 0.89 erhöht!
Erläutern Sie den Zugriff eines Benutzerprozesses auf
ein Gerät (z.B. einen Drucker)! Beschreiben Sie dabei das
Zusammenspiel von Dateisystem, Treiber-Task, Controller und Gerät!
Schema des Zusammenspiels:
User <-> 1.Dateisystem <-> 2.Treiber-Task <-> 3.Controller <-> Gerät
-
Der Zugriff auf die Spezialdatei als Benutzerpuffer
für das Gerät erfolgt wie auf eine normale Datei, zumindest bei
MINIX. Bei TOS wäre dagegen ein Spezialbefehl wie "send_to_midi()"
nötig. Die Gerätedatei von MINIX für den Drucker ist "/dev/lp" ,
die geöffnet werden muss, um einen File-Descriptor "fd" zu erhalten,
über den die Druckdaten mit "write(fd, buffer, ...)" geschrieben werden
können. Fehlermeldungen müssen abgefangen werden.
HW-unabhängiger Teil.
-
Die Aufrufe des Treibers müssen in Nachrichten
umgesetzt werden, die das Gerät (genauer: der Controller) versteht
(hw-abhängiger Teil). Die Grundfunktionalität jeden Treibers
umfasst die Befehle OPEN, WRITE, IOCTL und CLOSE (gilt sogar für ein
CD-ROM-Treiber!), über die die Controller-Register beschrieben werden. Der
Treiber legt Daten in Caches ab, sodass z.T. der Controller nicht
bemüht werden muss. Wird der Controller aktiviert, dann legt sich der
Treiber schlafen, bis der Kernel in weckt.
-
Der Controller führt die Befehle des Treibers aus.
Falls er DMA beherrscht, schaufelt er die Daten aus seinem internen Puffer
selbst über den Systembus in den Speicher, ansonsten erledigt dies die CPU.
Durch einen Interrupt signalisiert der Controller, dass die
Übertragung abgeschlossen ist. Dies löst eine
Unterbrechungsbehandlung aus, bei der der Kernel den schlafenden Treiber
entblockiert.
Was ist eine Spezialdatei in MINIX (im Zusammenhang mit
Treibern)?
Eine Spezialdatei ist ein Gerät, welches über einen
Gerätetreiber genauso wie eine normale Datei angesprochen werden kann,
also die Befehle read, write, open und ioctl versteht. Realisiert werden solche
Dateien in MINIX über das Kommando "mknod"; sie stehen dann i.d.R. in
"/devs", und sind durch ein Mode-Flag als Spezialdatei ausgewiesen.
Implementiert sind sie als Ewigschleifen, die Nachrichten entgegennehmen und
über "switch()" und dem Nachrichtentypen die gewünschte Prozedur
ausführen (die den Controller des Gerätes in hw-spezifischer Weise
steuert). Das Ergebnis wird verpackt und als Nachricht zurückgesendet.
Spezialdateien sind in MINIX immer entweder zeichenorientiert oder blockorientiert.
Welche Register muss ein Controller (für den Maustreiber) besitzen?
Aus Sicht des BS müssen die Register DAR (Datenregister)
und CSR (Control-/Statusregister) existieren. Über das DAR können
Controller-Daten gesetzt bzw. gelesen werden. Im CSR können Flags zum Lesen
(RXINT) bzw. Schreiben (TXINT) gesetzt werden; hier können auch Interrupts
gesperrt/zugelassen werden. Aus HW-Sicht werden tatsächlich aber noch mehr
Register benötigt.
Erläutern Sie den Begriff des Interrupts! Wir wird
ein Interrupt von der HW behandelt?
Ein Interrupt ist eine kurzzeitige Unterbrechung der
Abarbeitung des aktuellen Programms. Er kann über SW als auch über
HW ausgelöst worden sein. Als Ursachen für einen Interrupt sind
denkbar: Seitenfehler, Alarmfunktion oder Fertig-Meldungen von Geräten.
Interrupts können verschiedene Prioritäten zugewiesen sein, wodurch
ein Interrupt einen Interrupt niedrigerer Priorität unterbrechen kann.
Generell müssen Interrupts, bevor sie wirksam werden können, explizit
erlaubt werden (in MINIX werden sie durch ein "mask=lock;" gesperrt und durch
ein "restore(mask);" wieder freigegeben). Die HW behandelt Interrupts, indem
sie in die für sie in Tabellen zugewiesenen Routinen hineinspringt. Vorher
jedoch legen sie die aktuellen Registerwerte und das Prozessor-Status-Wort in
das Interrupt-Stack-Frame ab, damit sie transparent abgearbeitet werden
können. Erzeugt wird der Interrupt vom Controller, indem das Status-Flag
"IRQ" (Interrupt-Request) gesetzt wird. Die Quittierung erscheint als "IACK"
(Interrupt-Acknowledgement) im Statusregister.
Wenn die Maus bewegt wird, erzeugt der Controller eine Folge
von Zeichen, die den Status des Mausknopfs und die absoluten Koordinaten der
Maus beschreiben. Die Zeichen umfassen jeweils 8 bit und haben die folgende
Bedeutung: 5=Mausknopfstatus, 4=x-Koordinate (High-Byte), 3=x-Koordinate (Low-Byte),
2=y-Koordinate (High-Byte) und 1=y-Koordinate (Low-Byte). Geben Sie eine
Interrupt-Routine an, die diese Folge in eine geeignete Datenstruktur
umsetzt!
So wie das erste Zeichen eintrifft, wird die Interrupt-Routine
aufgerufen, die aktiv bleibt, bis die Folge der 5 Bytes eingelesen ist. Um den
Interrupt zu Initialisieren, muss jedoch zuvor das Status-Flag RXINT
gesetzt werden.
n=5;
while(
(stat=MOUSE->CSR & IRQ) && // Interruptrequest ist aktiv
(stat & RXRDY) // Receive-Ready-Interrupt
) {
code=MOUSE->DAR; // hole Datenregister
switch(n) {
catch 5: mouseb=code; break;
catch 4: mousex=code; break;
catch 3: mousex=(mousex<<8)+code; break;
catch 2: mousey=code; break;
catch 1: mousey=(mousey<<8)+code; break;
};
n--;
};
Welche Einträge enthält eine Leseanfrage des
Benutzers, der die Mausposition erfahren will, an einen Maustreiber?
Die Anfrage muss die folgenden Einträge enthalten:
Die Operation READ, die Gerätenummer DEVICE (plus Untergerätenummer,
z.B. um anzugeben, welches Floppylaufwerk gemeint ist), die Nummer des rufenden
Prozesses, damit der Treiber weiss, wohin er die Antwort senden soll,
eventuell die Position, an die in der Spezialdatei gesprungen werden soll (bei
Floppies sinnvoll, nicht aber bei Maustreibern) und ein Zeiger auf den
Datenpuffer, in den die Antwort abgelegt werden kann.
Wie läuft die Leseprozedur eines Maustreibers
schematisch ab, die obige Anfrage erfüllen könnte?
Zunächst muss sich die Routine den anfragenden
Prozess merken, der so lange blockiert ist. Dann ruft sie je nach Anfrage
eine Teilfunktion von sich auf (kann z.B. über "switch()" geschehen). Die
gewünschte Teilfunktion könnte in unserem Fall z.B. "do_read" sein.
Als Ergebnis erhält der Treiber eine Fehler- bzw. Erfolgsmeldung
zurück. Daraufhin kann er eine Nachricht erzeugen und diese an den
gemerkten Prozess senden, der dadurch entblockiert wird.
void mouse_task() { // bei Systemhochfahren zu aktivieren!
initialize();
while(TRUE) {
receive(ANY, &msg); // beachte jeden Caller
caller=msg.m_source; // merke anfragenden Prozess
switch(msg.m_type) {
case READ: r=do_read(); break;
default: r=ERROR; break;
};
msg.m_type=TASK_REPLY; // erzeuge Antwortnachricht
msg.REP_Status=r; // RESPONSE erfolgreich?
send(caller, &msg); // sende Antwort
};
};
Nennen Sie eine Lösung des Leser-Schreiber-Problems! Implementieren Sie sie
mithilfe von Semaphoren!
Der anfragende Leser wird nur so lange SOFORT zugelassen (und
ansonsten verzögert), wie kein Schreiber ANGEMELDET ist. Ein Schreiber
wird erst aktiv, wenn alle Leser fertig sind; er hat dann exklusiven Zugriff.
Wenn ein Schreiber abschliesst, werden zuerst alle LESER wieder für
einen Zugriff berechtigt, während Schreiber sich nur anmelden
können.
Drei Semaphore nötig: empty, full, mutex.
Erzeuger: Verbraucher:
P(empty); P(full);
P(mutex); P(mutex);
fill_buffer(); clr_buffer();
V(mutex); V(mutex);
V(full); V(empty);
Skizzieren Sie das Zusammenspiel von Client und
Verzeichnis-Server, wenn es einen zentralen Verzeichnisdienst gibt, der
Adressen auf den nächsten Pfad-Server zurück gibt, usw. Benennen Sie die
Nachrichten, die zwischen einem C und den S anfallen, wenn der C auf die Datei
"/a/b/c" zugreifen will!
Server1
Client Server2
Server3
Nachrichten: (1) REQUEST: a/b/c; (2) REPLY: Vz a ist auf S2;
(3) REQUEST: b/c; (4) REPLY: Vz b ist auf S3; (5) REQUEST: c; (6) REPLY:
Server3 und Inode von Datei c.
Überlegen Sie sich die Nachrichteninhalte, und
implementieren Sie obigen Verzeichnis-Server und eine
Anfrage-Client-Prozedur!
Eine Anfrage-Nachricht besteht v.a. aus m.path, dem gesuchten
Pfad. Die Antwortnachricht muss drei Felder führen: m.inode (falls
die Datei gefunden wurde), m.host (Adresse des zuständigen Verzeichnis-Servers) und
m.status (falls Fehler auftreten).
void directory_task() {
initialize();
while(TRUE) {
receive(ANY, &m);
caller=m.m_source;
// schlage Pfad im Server nach mithilfe der (zu setzenden)
// Argumente path, inode, host, r(ückgabewert)
if(r==NODE)
m.inode=inode;
else if(r=HOST)
m.host=host;
else r=ERROR;
m.status=r;
m.path=path;
send(caller, &m);
};
};
void client_ask_task() { // path=akt. Pfad, host=akt. Vz-Server
while(TRUE) {
m.path=path;
send(host, &m);
receive(host, &m);
if(m.status==NODE)
return;
else if(m.status==HOST) {
host=m.host;
path=m.path;
}
else Error-Handling;
};
};
Welche Bedingungen führen zusammen zu Deadlocks?
Vier Bedingungen, die alle erfüllt sein müssen: (1)
Gegenseitiger Ausschluss (nicht gleichzeitig im kritischen Abschnitt); (2)
Nichtentziehbarkeit der Ressource; (3) Geschlossene Kette; (4) Warten auf neue
Ressource.
Welche vier Arten von Unterbrechungen gibt es?
Signale, SW-Interrupts, HW-Interrupts, Nachrichten. [?]
Welche Arten von Semaphore kennen Sie?
Mutex-Semaphore: nur 0/1. Normale Semaphore: 0-n. Können
inkrementiert oder dekrementiert werden (über Verlassen(S) und
Passieren(S)). [?]
Warum ist in MINIX die gesetzte ERROR-Variable immer negativ?
ERROR wird i.d.R. als Rückgabewert von Prozeduren
geliefert, z.B. bedeutet -104=EOF (End Of File). Die Fehlernummer ist generell
negativ, damit sie von Erfolgs-Meldungen unterschieden werden kann, denn "read()"
kann u.U. auch einen Null-Wert liefern, ohne dass ein Fehler dabei auftrat.
Welche Aufgabe übernimmt in MINIX das Assembler-Programm "mpx88.s"?
Diese Datei wird ständig von MINIX-Programm benutzt. Ihre
Aufgabe ist es u.a. bei jedem Interrupt angesprungen zu werden, um mit "save()"
den Maschinenstatus von "cur_proc" zu retten. Danach ruft es über den
Interruptvektor, den sie vom Controller bekommt, die Interruptroutine auf.
Mögliche Interrupts sind z.B. tty_int, lpr_int, disk_int, wini_int
(Festplatten-Interrupt) und clock_int. Aktiv wird mpx88.s auch bei "s_call()",
dass immer aufgerufen wird, wenn ein Prozess eine Nachricht versenden
oder empfangen will (auch jeder System Call ist in MINIX ein
Nachrichtenaufruf!) Nach Beendigung der Interruptroutine wird durch "restart()"
das "cur_proc" wieder angestossen.
Beschreiben Sie kurz, wie in UNIX Dateien auf Platte abgelegt werden!
Verzeichnisse sind in UNIX gewöhnliche Dateien. Sie
enthalten die Namen, der im Verzeichnis enthaltenen Dateien, plus einen Vermerk
auf die Position ihrer Inodes auf Platte. Jeder Datei ist eine Inode zugewiesen,
der ihre Attribute enthält ode , wenn es sich um Gerätedateien
handelt, ihre Major- und Minor-Nummern. 10 Felder der Inode verweisen auf
Plattenblöcke, in denen die Dateiinhalte stehen. 3 Felder der Inode
verweisen auf jeweils einen Baumknoten. Der erste Baumknoten führt die
Verweise auf 128 weitere Dateiblöcke. Der zweite Knoten führt 128
Verweise auf Knoten, die jeweils wieder 128 Dateiblöcke adressieren. Der
dritte Knoten schliesslich zeigt auf 128 Knoten, die jeweils auf 128 Knoten
zeigen, die jeweils auf 128 Dateiblöcke zeigen.
Warum können virtuelle Adressen nicht direkt auf den
Speicherbus gelegt werden?
Virtuelle Adressen können viel grösser sein
als der physikalische Speicher. daher müssen sie mithilfe der Memory
Management Unit erst in physikalische Adressen umgerechnet werden
(Seitenadresse + Offset). Damit dies nicht jedes Mal geschehen muss, kann
sich die MMU 32 Einträge merken (Assoziativ-Speicher), weiss bei
einer ankommenden Adresse also sofort die zugehörige physikalische
Adresse.
Berechnen Sie die optimale Seitengrösse P,
wenn die durchschnittliche Prozessgrösse S ist!
Man muss davon ausgehen, dass ein Programm der
Grösse S S/P benötigt, wofür S/P*(Bytes pro
Tabelleneintrag) Bytes benötigt werden. Zusätzlich ist zu erwarten,
dass im Schnitt der letzte Block nur zur Hälfte mit Daten
gefüllt ist. Daraus ergibt sich ein Gesamt-Overhead von:
(S/P)*(Bytes pro Tabelleneintrag)+P/2
Diesen Overhead gilt es zu minimieren, weshalb wir die erste
Ableitung bilden, sie gleich Null setzen und nach P auflösen:
0=-S*(Bytes pro Tabelleneintrag)/P^2+1/2
P=Wurzel(S*(Bytes pro Tabelleneintrag)*2).
Beschreiben Sie kurz, wie der Druckerspooler von 4.3 BSD arbeitet!
Der User gibt "lpr x.txt" in die Shell ein. "lpr" kopiert die
Datei "x.txt" in das Verzeichnis "/usr/spool/lpd". Der dortige Dateiname
enthält Auskunft darüber, wann die Datei auszudrucken ist (d.h. alle
früheren Dateien werden vor ihr ausgedruckt). Zusätzlich wurde eine
Steuerdatei erzeugt, in der z.B. angegeben ist, auf welchem Drucker ausgedruckt
werden soll. "lpr" benachrichtigt den Drucker-Dämon "lpd", dass ein
Auftrag vorliegt (sofern der Dämon dies nicht ohnehin periodisch
prüft) und terminiert. "lpd" erzeugt über "fork()" ein Child, welches
die Datei ausliest und ausdruckt, während der Vater-Dämon wieder auf
Lauschposten geht.
Nennen Sie ein paar Besonderheiten, die beim
LRU-Seitenersetzung in Bezug auf Caches zu beachten ist!
Die Seitenersetzungsperformance lässt sich durch
doppelt verkettete Listen verbessern, da dann bei Löschen-Operationen eine
lokale Betrachtung der Liste genügt (sie muss nicht immer von vorne
aufgerollt werden). Statt einzelner Blöcke sollten Blockpakete, Buckets,
verwaltet werden. Die verwalteten Puffer sollten ein Dirty-Bit besitzen: Es ist
gesetzt, wenn der zugehörige Bucket durch eine Operation verändert
wurde. Für die LRU-Strategie bedeutet dies, dass der Cache-Puffer
gespeichert werden muss und umzusortieren ist. Gesondert behandelt werden
müssen Inodes und der Superblock (enthält Bit-Vektoren der
Inode-Verteilung auf der Platte), die zwar ständig benutzt werden, deren
Cache aber write-through sein sollte, d.h. bei jeder Änderung sofort
physikalisch gespeichert wird, damit es bei Systemausfall nicht zu
Inkonsistenzen kommt.
Schreiben Sie eine Formel auf, die bei einem (1)
sequenziellen System und (2) einem parallelen System die
Ausfallwahrscheinlichkeit 1-P(A) wiedergibt, wenn von den Komponenten A1,
... An ausgegangen werden kann!
Sequenzielle System fallen aus, wenn eine Komponente ausfällt, parallele Systeme nur,
wenn alle Komponenten ausfallen. Daher gilt:
(1) Verfügbarkeit P(A) =P(A1 UND ... UND An)
=1-P(NICHT A1 ODER ... ODER NICHT An)
(2) Verfügbarkeit P(A) =P(A1 ODER ... ODER An)
=1-P(NICHT A1 UND ... UND NICHT An)
Welchen Vorteil bringt die Anwendung der LRU-Strategie bei
der Verwaltung von internen Server-Tabellen?
Wenn eine Client-Workstation abstürzt, aber noch eine
geöffnete Datei vom Server verwalten lässt, so wird dieser
Eintrag schon bald von alleine durch einen aktuelleren Eintrag ausgetauscht, da
er nicht mehr benutzt wird.