Tafelübung: Klausurvorbereitungsstunde · Die 1:1-Beziehung zwischen Kontrollfluss und Adressraum ... – Eng kooperierende Threads (deutsch „Fäden“) können sich einen Adressraum

Betriebssysteme

Tafelübung: Klausurvorbereitungsstunde

http://ess.cs.tu-dortmund.de/DE/Teaching/SS2016/BS/

Olaf Spinczyk

[email protected]://ess.cs.tu-dortmund.de/~os

AG Eingebettete SystemsoftwareInformatik 12, TU Dortmund

mailto:[email protected]

19.07.2016 Betriebssysteme: Fragestunde 2

Agenda● Prozesse● Synchronisation● Deadlocks● Speicherverwaltung● Ein-/Ausgabe


Verwendung von fork()... /* includes */int main () { int pid; printf(“Elternpr.: PID %d PPID %d\n”, getpid(), getppid()); pid = fork(); /* Prozess wird dupliziert! Beide laufen an dieser Stelle weiter. */ if (pid > 0) printf(“Im Elternprozess, Kind-PID %d\n”, pid); else if (pid == 0) printf(“Im Kindprozess, PID %d PPID %d\n”, getpid(), getppid()); else printf(“Oh, ein Fehler!\n”); /* mehr dazu in der TÜ */}

... /* includes */int main () { int pid; printf(“Elternpr.: PID %d PPID %d\n”, getpid(), getppid()); pid = fork(); /* Prozess wird dupliziert! Beide laufen an dieser Stelle weiter. */ if (pid > 0) printf(“Im Elternprozess, Kind-PID %d\n”, pid); else if (pid == 0) printf(“Im Kindprozess, PID %d PPID %d\n”, getpid(), getppid()); else printf(“Oh, ein Fehler!\n”); /* mehr dazu in der TÜ */}

olaf@xantos:~> ./forkElternpr.: PID 7553 PPID 4014Im Kindprozess, PID 7554 PPID 7553Im Elternprozess, Kind-PID 7554

olaf@xantos:~> ./forkElternpr.: PID 7553 PPID 4014Im Kindprozess, PID 7554 PPID 7553Im Elternprozess, Kind-PID 7554


Diskussion: Zombies● Bevor der exit status eines terminierten Prozesses mit Hilfe

von wait abgefragt wird, ist er ein „Zombie“.● Die Ressourcen solcher Prozesse können freigegeben werden,

aber die Prozessverwaltung muss sie noch kennen.– Insbesondere der exit status muss gespeichert werden.

olaf@xantos:~> ./wait &olaf@xantos:~> ps PID TTY TIME CMD 4014 pts/4 00:00:00 bash17892 pts/4 00:00:00 wait17895 pts/4 00:00:00 wait <defunct>17897 pts/4 00:00:00 psolaf@xantos:~> Exit Status: 42

olaf@xantos:~> ./wait &olaf@xantos:~> ps PID TTY TIME CMD 4014 pts/4 00:00:00 bash17892 pts/4 00:00:00 wait17895 pts/4 00:00:00 wait <defunct>17897 pts/4 00:00:00 psolaf@xantos:~> Exit Status: 42

Beispielprogrammmit beendetem Kindprozess ohne abgefragten exit Status.

Beispielprogrammmit beendetem Kindprozess ohne abgefragten exit Status.

Zombies werdenvon ps als <defunct>dargestellt.

Zombies werdenvon ps als <defunct>dargestellt.


Leichtgewichtige Prozesse (Threads)● Die 1:1-Beziehung zwischen Kontrollfluss und Adressraum

wird aufgebrochen.– Eng kooperierende Threads (deutsch „Fäden“) können sich einen

Adressraum teilen (code + data + bss + heap, aber nicht stack!).

● Vorteile:– Aufwändige Operationen können in einen leichtgewichtigen

Hilfsprozess ausgelagert werden, während der Elternprozess erneut auf Eingabe reagieren kann.

● Typisches Beispiel: Webserver– Programme, die aus mehreren unabhängigen Kontrollflüssen bestehen,

profitieren unmittelbar von Multiprozessor-Hardware.– Schneller Kontextwechsel, wenn man im selben Adressraum bleibt.– Je nach Scheduler eventuell mehr Rechenzeit.

● Nachteil:– Programmierung ist schwierig: Zugriff auf gemeinsame Daten muss

koordiniert werden.


Vergleich: exec..() fork() pthread_create()● Überlagerung eines Prozesses● Keine gemeinsamen Daten● schwergewichtig

/* TEXT Segment prog1 */

…exec..(“prog2”...);


…exec..(“prog2”...);

DATA , BSS , HEAP

STACK

Prozess A

main thread


Vergleich: exec..() fork() pthread_create()● Überlagerung eines Prozesses● Keine gemeinsamen Daten● schwergewichtig


int main(...)...


int main(...)...

DATA , BSS , HEAP

STACK

Prozess A

main thread


int main(...)...


int main(...)...

DATA , BSS , HEAP

STACK


Vergleich: exec..() fork() pthread_create()● Verzweigung eines Prozesses● Gemeinsame Daten: shared-memory● schwergewichtig

/* TEXT Segment */switch(fork()){

case -1: exit(EXIT_FAILURE);case 0:

... break;case default:

... break;}




... break;}

DATA , BSS , HEAP

STACK

Prozess A

main thread






... break;}




... break;}

DATA , BSS , HEAP

STACK

Prozess A

main thread

DATA , BSS , HEAP

STACK

Prozess B

main thread






... break;}




... break;}

DATA , BSS , HEAP

STACK

Prozess A

main thread

DATA , BSS , HEAP

STACK

Prozess B

main thread

SHARED MEMORY






... break;}




... break;}

DATA , BSS , HEAP

STACK

Prozess A

main thread

DATA , BSS , HEAP

STACK

Prozess B

main thread

SHARED MEMORY

Zugriff muss durchSemaphore

synchronisiert werdenErzeugung

und Anbindung nötig


Vergleich: exec..() fork() pthread_create()● Aufteilung eines Prozesses● Gemeinsame Daten: Data, BSS, Heap, shared-memory● leichtgewichtig

/* TEXT Segment */

int main(void){...

pthread_create(…,&NEWthread,(void*)&thArgs); ...

}

/* TEXT Segment */

int main(void){...

pthread_create(…,&NEWthread,(void*)&thArgs); ...

}

DATA , BSS , HEAP

STACK

Prozess A

main thread



/* TEXT Segment */

int main(void){ void *NEWthread(void *thArgs){... ...

pthread_create(…); ... ... pthread_exit((void*)0);

} }

/* TEXT Segment */



} }

DATA , BSS , HEAP

MainThread STACK

Prozess A

main thread

NEWthread STACK

new thread



/* TEXT Segment */



} }

/* TEXT Segment */



} }

DATA , BSS , HEAP

MainThread STACK

Prozess A

main thread

NEWthread STACK

new thread

Zugriff muss durchMutexe oder Semaphore

synchronisiert werden




Semaphor – komplexere Interaktionen● Beispiel: Das erste Leser/Schreiber-Problem

/* gem. Speicher */Semaphore mutex;Semaphore wrt;int readcount;

/* gem. Speicher */Semaphore mutex;Semaphore wrt;int readcount;

/* Initialisierung */mutex = 1;wrt = 1;readcount = 0;

/* Initialisierung */mutex = 1;wrt = 1;readcount = 0;

/* Schreiber */wait (&wrt);

... schreibe

signal (&wrt);

/* Schreiber */wait (&wrt);

... schreibe

signal (&wrt);

/* Leser */wait(&mutex);readcount++;if (readcount == 1) wait(&wrt);signal(&mutex);

... lese

wait(&mutex);readcount--;if (readcount == 0)

signal(&wrt);signal(&mutex):

/* Leser */wait(&mutex);readcount++;if (readcount == 1) wait(&wrt);signal(&mutex);

... lese

wait(&mutex);readcount--;if (readcount == 0)

signal(&wrt);signal(&mutex):


Naiver Lösungsansatz – falsch!

/* Schlossvariable (Initialwert 0) */typedef unsigned char Lock;

/* Kritischen Abschnitt betreten */void acquire (Lock *lock) { while (*lock); *lock = 1;}

/* Kritischen Abschnitt wieder verlassen */void release (Lock *lock) { *lock = 0;}

/* Schlossvariable (Initialwert 0) */typedef unsigned char Lock;

/* Kritischen Abschnitt betreten */void acquire (Lock *lock) { while (*lock); *lock = 1;}

/* Kritischen Abschnitt wieder verlassen */void release (Lock *lock) { *lock = 0;}


Naiver Lösungsansatz – falsch!

/* Schlossvariable */typedef unsigned char Lock;

/* K.A. betreten */void acquire (Lock *lock) { while (*lock); *lock = 1;}

/* K.A. verlassen */void release (Lock *lock) { *lock = 0;}

/* Schlossvariable */typedef unsigned char Lock;

/* K.A. betreten */void acquire (Lock *lock) { while (*lock); *lock = 1;}

/* K.A. verlassen */void release (Lock *lock) { *lock = 0;}

● acquire soll einen kritischen Abschnitt schützen, ist dabei aber selbst kritisch!– Problematisch ist der Moment nach

dem Verlassen der Warteschleife und vor dem Setzen der Schlossvariablen.

– Bei Verdrängung des laufenden Prozesses in diesem Moment könnte ein anderer Prozess den kritischen Abschnitt frei vorfinden und ebenfalls betreten.

Im weiteren Verlauf könnten (mindestens) zwei Prozesseden eigentlich durch acquire geschützten kritischen Abschnittüberlappt ausführen!

Im weiteren Verlauf könnten (mindestens) zwei Prozesseden eigentlich durch acquire geschützten kritischen Abschnittüberlappt ausführen!


Schloss mit atomaren Operationen● Viele CPUs unterstützen unteilbare (atomare)

Lese-/Modifikations-/Schreibzyklen, mit denen sich Schlossalgorithmen implementieren lassen:

● Motorola 68K: TAS (Test-and-Set)

– Setzt Bit 7 des Zieloperandenund liefert den vorherigenZustand in Condition Code Bits

● Intel x86: XCHG (Exchange)

– Tauscht den Inhalt einesRegisters mit dem einer Variablenim Speicher

● PowerPC: LL/SC (Load Linked/Store Conditional)

● ...

acquire TAS lockBNE acquire

acquire TAS lockBNE acquire

mov ax,1acquire: xchg ax,lock

cmp ax,0jne acquire

mov ax,1acquire: xchg ax,lock

cmp ax,0jne acquire


Semaphor – einfache Interaktionen● “einseitige Synchronisation”

● “betriebsmittelorientierte Synchronisation”

/* gem. Speicher */Semaphore elem;struct list l;struct element e;

/* gem. Speicher */Semaphore elem;struct list l;struct element e;

void producer() { enqueue(&l, &e); signal(&elem);}

void producer() { enqueue(&l, &e); signal(&elem);}

void consumer() { struct element *x; wait(&elem); x = dequeue(&l);}

void consumer() { struct element *x; wait(&elem); x = dequeue(&l);}

sonst wie beimgegenseitigen Ausschluss

/* Initialisierung */elem = 0;/* Initialisierung */elem = 0;

/* gem. Speicher */Semaphore resource;/* gem. Speicher */Semaphore resource;

/* Initialisierung */resource = N; /* N > 1 *//* Initialisierung */resource = N; /* N > 1 */


Agenda● Prozesse● Synchronisation● Deadlocks● Speicherverwaltung


Ursachenforschung ... am Beispiel

Verklemmung möglichVerklemmung möglich

L

R

Verklemmung aufgetretenVerklemmung aufgetreten

L

R

1

2

1

2

Käfer 1 belegt L und benötigt RKäfer 2 belegt R und benötigt LKäfer 1 belegt L und benötigt RKäfer 2 belegt R und benötigt L


Ursachenforschung ... abstrakt

FortschrittProzess K2


Betriebsmittel

LR

Bet

rieb

smit

tel

L R

In diese Bereichekönnen die Prozessenicht hinein!

In diese Bereichekönnen die Prozessenicht hinein!

Verklemmungunvermeidbar

1 2

3

5

64

'1'-'6': mögliche Abläufe: Verklemmung'1'-'6': mögliche Abläufe: Verklemmung


Ursachenforschung ... abstrakt


Betriebsmittel

LR

Bet

rieb

smit

tel

L R

Eine Verklemmung kannin diesem Szenario nichtauftreten.

Eine Verklemmung kannin diesem Szenario nichtauftreten.

1 2 3

5

6

4

'1'-'6': mögliche Abläufe'1'-'6': mögliche AbläufeFortschrittProzess K2


Betriebsmittel ...werden vom Betriebssystem verwaltet und den Prozessen zugänglich gemacht. Man unterscheidet zwei Arten:

● Wiederverwendbare Betriebsmittel– Werden von Prozessen für eine bestimmte Zeit belegt und anschließend

wieder freigegeben.– Beispiele: CPU, Haupt- und Hintergrundspeicher, E/A-Geräte,

Systemdatenstrukturen wie Dateien, Prozesstabelleneinträge, ...

● Konsumierbare Betriebsmittel– Werden im laufenden System erzeugt (produziert) und zerstört

(konsumiert)– Beispiele: Unterbrechungsanforderungen, Signale, Nachrichten, Daten

von Eingabegeräten


Wiederverwendbare Betriebsmittel● Es kommt zu einer Verklemmung, wenn zwei Prozesse ein

wiederwendbares Betriebsmittel belegt haben, dass vom jeweils anderen hinzugefordert wird.

● Beispiel: Ein Rechnersystem hat 200 GByte Hauptspeicher. Zwei Prozesse belegen den Speicher schrittweise. Die Belegung erfolgt blockierend.

Prozess 1

...Belege 80 GByte;...Belege 60 GByte;

Prozess 1


Prozess 2


Prozess 2


Wenn beide Prozesse ihre erste Anforderung ausführen bevorSpeicher nachgefordert wird, ist eine Verklemmung unvermeidbar.Wenn beide Prozesse ihre erste Anforderung ausführen bevorSpeicher nachgefordert wird, ist eine Verklemmung unvermeidbar.


Konsumierbare Betriebsmittel● Es kommt zu einer Verklemmung, wenn zwei Prozesse auf ein

konsumierbares Betriebsmittel warten, das vom jeweils anderen produziert wird.

● Beispiel: Synchronisationssignale werden mit Hilfe der Semaphoroperation wait und signal zwischen zwei Prozessen „verschickt“.

Prozess 1

semaphore s1 = {0, NULL};...wait (&s1);...signal (&s2);

Prozess 1


Prozess 2


Prozess 2


Jeder Prozess wartet auf ein Synchronisationssignal des anderen,das dieser aber nicht senden kann, da er selbst blockiert ist.Jeder Prozess wartet auf ein Synchronisationssignal des anderen,das dieser aber nicht senden kann, da er selbst blockiert ist.


Verklemmung von Prozessen● 1. Variante: Deadlock

– Passives Warten

– Prozesszustand BLOCKED

● 2. Variante: Livelock

– Aktives Warten (busy waiting oder „lazy“ busy waiting)

– Prozesszustand beliebig (auch RUNNING), aber kein Fortschritt

● Deadlocks sind das vergleichsweise geringere Übel, da dieser Zustand eindeutig erkennbar ist und so die Basis zur „Auflösung“ gegeben ist.




Grundlegende Politiken/Strategien● Platzierungsstrategie (placement policy) – obligatorisch

– Woher soll benötigter Speicher genommen werden?● Wo der Verschnitt am kleinsten/größten ist● Egal, weil Verschnitt zweitrangig ist

Und zusätzlich bei Ein-/Auslagerung ...

● Ladestrategie (fetch policy)– Wann sind Speicherinhalte aus dem Hintergrundspeicher in den

Hauptspeicher zu laden?● Auf Anforderung oder im Voraus

● Ersetzungsstrategie (replacement policy)– Welche Speicherinhalte sind ggf. in den Hintergrundspeicher zu

verdrängen, falls der Speicher knapp wird?● Das älteste, am seltensten genutzte● Das am längsten ungenutzte


Segmentierung● Hardwareunterstützung: Abbildung logischer auf

physikalische Adressen

logischer Adressraum physikalischer Adressraum

Das Segment des logischen Adressraums kann an jeder beliebigen Stelleim physikalischen Adressraum liegen. Das Betriebssystem bestimmt, wo ein Segment im physikalischen Adressraum tatsächlich liegen soll.

Das Segment des logischen Adressraums kann an jeder beliebigen Stelleim physikalischen Adressraum liegen. Das Betriebssystem bestimmt, wo ein Segment im physikalischen Adressraum tatsächlich liegen soll.

0

0xfffff

ROM

RAM

+ 0x450000

+ 0x100000

0x100000

0x1fffff

0x450000

0x54ffff


Segmentierung (2)● Realisierung mit Übersetzungstabelle

Segmenttabellen-basisregister

Segmenttabelle

00 4fffffe0 f000

...

02

01

00

LängeStartadr.

+ 00 4a0202logischeAdresse

<

ffe1 3a02physikalischeAdresse

+

Trap: Schutzverletzung

ja


Seitenadressierung (paging)● Einteilung des logischen Adressraums in gleichgroße Seiten,

die an beliebigen Stellen im physikalischen Adressraum liegen können– Lösung des Fragmentierungsproblems– keine Kompaktifizierung mehr nötig– Vereinfacht Speicherbelegung und Ein-/Auslagerungen

logischer Adressraum physikalischer Adressraum

Seiten(pages)

Kacheln(frames)

ROM

RAM


MMU mit Seiten-Kacheltabelle● Tabelle setzt Seiten in Kacheln um

SKT Basisregister

Seiten-Kacheltabelle

00000

Startadr.

+ 12alogischeAdresse

physikalischeAdresse

00002

ffe0 fxxx

00000

00001

00002

0000300004

12affe0f...


Mehrstufige Seitenadressierung● Beispiel: zweifach indirekte Seitenadressierung

● Präsenzbit auch für jeden Eintrag in den höheren Stufen– Tabellen werden aus- und einlagerbar

– Tabelle können bei Zugriff (=Bedarf) erzeugt werden (spart Speicher!)

● Aber: Noch mehr implizite Speicherzugriffe

12a03023logischeAdresse

... ...

...

......

......

302 03


Translation Look-Aside Buffer (TLB)● Schneller Registersatz wird konsultiert bevor auf die SKT

zugegriffen wird:

SKT Basisregister

Seiten-Kacheltabelle

00000

Startadr.

+ 12a logischeAdresse

physikalischeAdresse

00002

ffe0 fxxx

...

00000

00001

00002

0000300004

12affe0f

a0123

bfff4

ffe0f

12345

00004

00028

00002

00032

Translation Look AsideBuffer (TLB)


Translation Look-Aside Buffer (2)● Schneller Zugriff auf Seitenabbildung, falls Information im

voll-assoziativen Speicher des TLB– keine impliziten Speicherzugriffe nötig

● Bei Kontextwechseln muss TLB gelöscht werden (flush)

● Bei Zugriffen auf eine nicht im TLB enthaltene Seite wird die entsprechende Zugriffsinformation in den TLB eingetragen

– Ein alter Eintrag muss zur Ersetzung ausgesucht werden

● TLB Größe– Intel Core i7: 512 Einträge, Seitengröße 4K

– UltraSPARC T2: Daten TLB = 128, Code TLB = 64, Seitengröße 8K

– Größere TLBs bei den üblichen Taktraten zur Zeit nicht möglich


Seitenersetzung● Was tun, wenn keine freie Kachel vorhanden?

● Eine Seite muss verdrängt werden, um Platz für neue Seite zu schaffen!

● Auswahl von Seiten, die nicht geändert wurden (dirty bit in der SKT)

● Verdrängung erfordert Auslagerung, falls Seite geändert wurde

● Vorgang:● Seitenfehler (page fault): Trap in das Betriebssystem

● Auslagern einer Seite, falls keine freie Kachel verfügbar

● Einlagern der benötigten Seite

● Wiederholung des Zugriffs

● Problem● Welche Seite soll ausgewählt werden (das „Opfer“)?


Ersetzungsstrategien● Betrachtung von Ersetzungsstrategien und deren Wirkung auf

Referenzfolgen

● Referenzfolge

● Folge von Seitennummern, die das Speicherzugriffsverhalten eines Prozesses abbildet

● Ermittlung von Referenzfolgen z.B. durch Aufzeichnung der zugegriffenen Adressen

- Reduktion der aufgezeichneten Sequenz auf Seitennummern

- Zusammenfassung von unmittelbar hintereinanderstehenden Zugriffen auf die gleiche Seite

● Beispiel für eine Referenzfolge: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5


Optimale Ersetzungsstrategie● Vorwärtsabstand

● Zeitdauer bis zum nächsten Zugriff auf die entsprechende Seite

● Strategie OPT (oder MIN) ist optimal(bei fester Kachelmenge):minimale Anzahl von Einlagerungen/Ersetzungen (hier 7)

● „Ersetze immer die Seite mit dem größten Vorwärtsabstand!“

Referenzfolge 1 2 3 4 1 2 5 1 2 3 4 5

HauptspeicherKachel 1 1 1 1 1 1 1 1 1 1 3 4 4Kachel 2 2 2 2 2 2 2 2 2 2 2 2Kachel 3 3 4 4 4 5 5 5 5 5 5Kachel 1 4 3 2 1 3 2 1 > > > > >Kachel 2 > 4 3 2 1 3 2 1 > > > >Kachel 3 > > 7 7 6 5 5 4 3 2 1 >

Kontrollzustände(Vorwärtsabstand)


Optimale Ersetzungsstrategie● Implementierung von OPT praktisch unmöglich

● Referenzfolge müsste vorher bekannt sein

● OPT ist nur zum Vergleich von Strategien brauchbar

● Suche nach Strategien, die möglichst nahe an OPT kommen

● z.B. Least Recently Used (LRU)


Least Recently Used (LRU)● Rückwärtsabstand

● Zeitdauer, seit dem letzten Zugriff auf die Seite

● LRU Strategie (10 Einlagerungen)

● „Ersetze die Seite mit dem größten Rückwärtsabstand!“

Referenzfolge 1 2 3 4 1 2 5 1 2 3 4 5

HauptspeicherKachel 1 1 1 1 4 4 4 5 5 5 3 3 3Kachel 2 2 2 2 1 1 1 1 1 1 4 4Kachel 3 3 3 3 2 2 2 2 2 2 5Kachel 1 0 1 2 0 1 2 0 1 2 0 1 2Kachel 2 > 0 1 2 0 1 2 0 1 2 0 1Kachel 3 > > 0 1 2 0 1 2 0 1 2 0

Kontrollzustände(Rückwärts-abstand)


Least Recently Used (LRU)● Vergrößerung des Hauptspeichers (4 Kacheln):

8 Einlagerungen

Referenzfolge 1 2 3 4 1 2 5 1 2 3 4 5

Hauptspeicher

Kachel 1 1 1 1 1 1 1 1 1 1 1 1 5Kachel 2 2 2 2 2 2 2 2 2 2 2 2Kachel 3 3 3 3 3 5 5 5 5 4 4Kachel 4 4 4 4 4 4 4 3 3 3Kachel 1 0 1 2 3 0 1 2 0 1 2 3 0Kachel 2 > 0 1 2 3 0 1 2 0 1 2 3Kachel 3 > > 0 1 2 3 0 1 2 3 0 1Kachel 4 > > > 0 1 2 3 4 5 0 1 2

Kontrollzustände(Rückwärts-abstand)


Least Recently Used (LRU)● Keine Anomalie

● Allgemein gilt: Es gibt eine Klasse von Algorithmen(Stack-Algorithmen), bei denen keine Anomalie auftritt:

- Bei Stack-Algorithmen ist bei k Kacheln zu jedem Zeitpunkt eine Untermenge der Seiten eingelagert, die bei k+1 Kacheln zum gleichen Zeitpunkt eingelagert wären!

- LRU: Es sind immer die letzten k benutzten Seiten eingelagert

- OPT: Es sind die k bereits benutzten Seiten eingelagert, die als nächstes zugegriffen werden

● Problem● Implementierung von LRU nicht ohne Hardwareunterstützung möglich

● Es muss jeder Speicherzugriff berücksichtigt werden


Least Recently Used (LRU)● Naive Idee: Hardwareunterstützung durch Zähler

● CPU besitzt einen Zähler, der bei jedem Speicherzugriff erhöht wird (inkrementiert wird)

● bei jedem Zugriff wird der aktuelle Zählerwert in den jeweiligen Seitendeskriptor geschrieben

● Auswahl der Seite mit dem kleinsten Zählerstand (Suche!)

● Aufwändige Implementierung

● viele zusätzliche Speicherzugriffe

● hoher Speicherplatzbedarf

● Minimum-Suche in der Seitenfehler-Behandlung


Second Chance (Clock)● So wird’s gemacht: Einsatz von Referenzbits

● Referenzbit im Seitendeskriptor wird automatisch durch Hardware gesetzt, wenn die Seite zugegriffen wird

- einfacher zu implementieren

- weniger zusätzliche Speicherzugriffe

- moderne Prozessoren bzw. MMUs unterstützen Referenzbits(z.B. x86: access bit)

● Ziel: Annäherung von LRU● bei einer frisch eingelagerten Seite wird das Referenzbit

zunächst auf 1 gesetzt

● wird eine Opferseite gesucht, so werden die Kacheln reihum inspiziert

- ist das Referenzbit 1, so wird es auf 0 gesetzt (zweite Chance)

- ist das Referenzbit 0, so wird die Seite ersetzt


Second Chance (Clock)● Implementierung mit umlaufendem Zeiger (Clock)

● an der Zeigerposition wird Referenzbit getestet

- falls Referenzbit 1, wird Bit gelöscht

- falls Referenzbit gleich 0, wurde ersetzbare Seite gefunden

- Zeiger wird weitergestellt; falls keine Seite gefunden: Wiederholung

● falls alle Referenzbits auf 1 stehen, wird Second Chance zu FIFO

A 1

B 0

C 1

D 1

E 0F 1

G 1

H 0

I 1

A 1

B 0

C 0

D 0

0EF 1

G 1

H 0

I 1

Referenzbit

Seite wirdersetzt


Second Chance (Clock)● Ablauf bei drei Kacheln (9 Einlagerungen)

Referenzfolge 1 2 3 4 1 2 5 1 2 3 4 5

HauptspeicherKachel 1 1 1 1 4 4 4 5 5 5 5 5 5Kachel 2 2 2 2 1 1 1 1 1 3 3 3Kachel 3 3 3 3 2 2 2 2 2 4 4Kachel 1 1 1 1 1 1 1 1 1 1 0 0 1Kachel 2 0 1 1 0 1 1 0 1 1 1 1 1Kachel 3 0 0 1 0 0 1 0 0 1 0 1 1

Umlaufzeiger 2 3 1 2 3 1 2 2 2 3 1 1

Kontrollzustände(Referenzbits)


Second Chance (Clock)● Vergrößerung des Hauptspeichers (4 Kacheln):

10 Einlagerungen

Referenzfolge 1 2 3 4 1 2 5 1 2 3 4 5

Hauptspeicher

Kachel 1 1 1 1 1 1 1 5 5 5 5 4 4Kachel 2 2 2 2 2 2 2 1 1 1 1 5Kachel 3 3 3 3 3 3 3 2 2 2 2Kachel 4 4 4 4 4 4 4 3 3 3Kachel 1 1 1 1 1 1 1 1 1 1 1 1 1Kachel 2 0 1 1 1 1 1 0 1 1 1 0 1Kachel 3 0 0 1 1 1 1 0 0 1 1 0 0Kachel 4 0 0 0 1 1 1 0 0 0 1 0 0

Umlaufzeiger 2 3 4 1 1 1 2 3 4 1 2 3

Kontrollzustände(Referenzbits)


Second Chance (Clock)● Bei Second Chance kann es auch zur FIFO Anomalie kommen

● Wenn alle Referenzbits gleich 1, wird nach FIFO entschieden

● Im Normalfall kommt man aber LRU nahe

● Erweiterung● Modifikationsbit kann zusätzlich berücksichtigt werden (Dirty Bit)

● Drei Klassen: (0,0), (1,0) und (1,1) mit (Referenzbit, Modifikationsbit)

● Suche nach der niedrigsten Klasse (Einsatz im MacOS)




Geräteklassen● Zeichenorientierte Geräte

– Tastatur, Drucker, Modem, Maus, ...

– Meist rein sequentieller Zugriff, selten wahlfreie Positionierung

● Blockorientierte Geräte

– Festplatte, Diskette, CD-ROM, DVD, Bandlaufwerke, ...

– Meist wahlfreier blockweiser Zugriff (random access)

● Andere Geräte passen weniger leicht in dieses Schema

– Grafikkarten (insbesondere 3D-Beschleunigung)

– Netzwerkkarten (Protokolle, Adressierung, Broadcast/Multicast, Nachrichtenfilterung, ...)

– Zeitgeberbaustein (Einmalige oder periodische Unterbrechungen)– ...


Polling (oder „Programmierte E/A“)... bedeutet aktives Warten auf ein Ein-/Ausgabegerät

/* Zeichen in Kern-Puffer p kopieren */copy_from_user (buffer, p, count);

/* Schleife über alle Zeichen */for (i=0; i<count; i++) {

/* Warte “aktiv” bis Drucker bereit */ while (*printer_status_reg != READY);

/* Ein Zeichen ausgeben */ *printer_data_reg = p[i]; }

return_to_user ();

Pseudo-Code einerBetriebssystem-funktion zum Drucken von Text im Polling-Betrieb.

Pseudo-Code einerBetriebssystem-funktion zum Drucken von Text im Polling-Betrieb.


Unterbrechungsgetriebene E/A... bedeutet, dass die CPU während der Wartezeit einem anderen Prozess zugeteilt werden kann.

Code, der die E/A-Operation initiiert. Unterbrechungsbehandlungsroutine

copy_from_user (buffer, p, count);/* Druckerunterbrechungen erlauben */enable_interrupts ();/* Warte bis Drucker bereit */while (*printer_status_reg != READY);/* Erstes Zeichen ausgeben */*printer_data_reg = p[i++]; scheduler ();return_to_user ();

if (count > 0) { *printer_data_reg = p[i]; count--; i++;}else unblock_user ();acknowledge_interrupt ();return_from_interrupt ();


DMA-getriebene E/A... bedeutet, dass die Software nicht mehr für den Datentransfer zwischen Controller und Hauptspeicher zuständig ist.

– Die CPU wird weiter entlastet.

Code, der die E/A-Operation initiiert. Unterbrechungsbehandlungsroutine

copy_from_user (buffer, p, count);set_up_DMA_controller (p, count); scheduler ();return_to_user ();

acknowledge_interrupt ();unblock_user ();return_from_interrupt ();


UNIX Block Buffer Cache● Pufferspeicher für Plattenblöcke im Hauptspeicher

– Verwaltung mit Algorithmen ähnlich wie bei Kachelverwaltung

– Read ahead: beim sequentiellen Lesen wird auch der Transfer von Folgeblöcken angestoßen

– Lazy write: Block wird nicht sofort auf Platte geschrieben (erlaubt Optimierung der Schreibzugriffe und blockiert den Schreiber nicht)

– Verwaltung freier Blöcke in einer Freiliste

● Kandidaten für Freiliste werden nach LRU Verfahren bestimmt

● Bereits freie aber noch nicht anderweitig benutzte Blöcke können reaktiviert werden (Reclaim)


UNIX Block Buffer Cache (2)● Schreiben erfolgt, wenn

– keine freien Puffer mehr vorhanden sind,

– regelmäßig vom System (fsflush Prozess, update Prozess),

– beim Systemaufruf sync(),

– und nach jedem Schreibaufruf im Modus O_SYNC.

● Adressierung

– Adressierung eines Blocks erfolgt über ein Tupel:(Gerätenummer, Blocknummer)

– Über die Adresse wird ein Hash-wert gebildet, der eine der möglichen Pufferlisten auswählt


Journaled File Systems● Zusätzlich zum Schreiben der Daten und Meta-Daten (z.B.

Inodes) wird ein Protokoll der Änderungen geführt

– Alle Änderungen treten als Teil von Transaktionen auf.

– Beispiele für Transaktionen:

● Erzeugen, löschen, erweitern, verkürzen von Dateien

● Dateiattribute verändern

● Datei umbenennen

– Protokollieren aller Änderungen am Dateisystem zusätzlich in einer Protokolldatei (Log File)

– Beim Bootvorgang wird Protokolldatei mit den aktuellen Änderungen abgeglichen und damit werden Inkonsistenzen vermieden.

Documents

Tafelübung: Klausurvorbereitungsstunde · Die 1:1-Beziehung zwischen Kontrollfluss und Adressraum ... – Eng kooperierende Threads (deutsch „Fäden“) können sich einen Adressraum