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
  1. 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.
  2. 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.
  3. 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.