Allgemeines
Build-Prozesse
Definition und Kategorisierung
Ein Rechensystem besteht aus Hardware, Systemprogrammen und Anwendungsprogrammen.
Signale und Interrupts
Debugging
Bash-Programmierung
Allgemeines
- [[Bash Trennung von Befehlen]]
- [[Bash Variablen]]
- [[Bash Arrays]]
- [[Bash String-Manipulation]]
Programmstruktur
- [[Bash Schleifen]]
- [[Bash Bedingungen]]
- [[Bash Subroutinen]]
Befehle
- [[read]]
- [[echo]]
Spezielles
- [[Bash Umleitungen]]
Programmstruktur
Prozesserzeugung
Jeder Prozess hat unter anderem einen privaten Stack, Heap, Code und Daten.
Das Betriebssystem sichert (nebenläufigen) Prozessen Konsistenz bzgl. ihrer internen Zustände und der aller genutzten Betriebsmittel (Register, PCB) zu.
Registerinhalte müssen beim Hin- und Herschalten (Kontextwechsel) zwischen Prozessen zwischengespeichert werden.
Eine Compute Farm ist ein Datenparalleles Programmiermodell das wie folgt funktioniert:
- Master - Wartet in Endlosschleife auf requests und erzeugt dynamisch Threads zu deren Verarbeitung
- Worker - Verarbeitet Task durch Abarbeitung des vom Master spezifizierten Code(s)
Prinzip: Abhängigkeiten innerhalb der Worker minimieren
Beispiel
int main(int argc, char **argv) {
for (;;) {
get(&request); // blocking
switch (request) {
case X: pthread_create(... taskX); break;
case Y: pthread_create(... taskY); break;
}
}
}
void *taskX(void *data) {
// ...
}Eine Workcrew ist ein Datenparalleles Programmiermodell, das wie folgt funktioniert:
- Master - Generiert Workerthreads und wartet danach bis diese terminieren
- Worker - Verwenden alle eine gemeinsame, statische Datenquelle
- Gut geeignet für Verfahren mit unveränderlicher Eingabe, z.B. (Datenbank-)Suchmaschine
Beispiel
int main(int argc, char **argv) {
pthread_create(... thread1 ... taskX);
pthread_create(... thread2 ... taskY);
// ...
suspend( ) // wait for all workers to finish
}
}
void *taskX(void *data) { ... } // process taskX
void *taskY(void *data) { ... } // process taskYProgrammiermodelle
Eine Pipeline ist ein Taskparalleles Programmiermodell, bei dem eine große Menge unabhängiger Eingabedaten durch eine Abfolge von stages verarbeitet wird.
- Dieses Modell eignet sich für Schachtelung einer Compute Farm bzw. Workcrew innerhalb von Stages: Multiplexing
- Der maximale Durchsatz ist in jedem Fall auf die Dauer der aufwendigsten stage begrenzt
Beispiel
int main(int argc, char **argv) {
pthread_create(... stage1);
pthread_create(... stage2); /* ... */
}
void *stage1(void *data) {
for ( ; ; ) {
getItem( ); // blocking
... // process stage 1
forwardItem( ); // to next stage
} /* or output */
}
/* ... */
void *stageN(void *data) { ... }Threads, Threadsynchronisation
Das Philosophenproblem (Dijkstra, 1968) ist ein klassisches Gedankenexperiment zur Nebenläufigkeit
Das Problem
- 5 Philosophen speisen mit 5 Gabeln Spaghetti, wobei jeder zum Essen 2 Gabeln braucht.
- Jeder Philosoph kommt zu einem zufälligen Zeitpunkt an seinen Platz, nimmt zwei Gabeln und isst eine zufällig lange Zeit.
Das Szenario veranschaulicht die Phänomene:
- Deadlock - z.B. wenn alle hintereinander die rechte Gabel nehmen
- Starvation - z.B. wenn einer (oder mehr) nie Zugriff bekommen weil andere immer wieder eine Ressource erlangen
- Busy Waiting - z.B. wenn einer (oder mehr) unaufhörlich um Besteck bitten
Ein Deadlock (deutsch Verklemmung) ist die dauerhafte Blockierung von (mindestens 2) Prozessen, die die gemeinsame Ressource nutzen.
Ein Deadlock tritt auf, wenn mindestens zwei Prozesse sich in einem wechselseitigen Wartezustand befinden und dieser Zustand auch durch die Freigabe aller Ressourcen anderer Prozesse nicht aufgegeben werden kann. Einen Deadlock mit nur 2 beteiligten Prozessen nennt man auch Deadly Embrace (tödliche Umarmung).
Siehe auch
Bedingungen
Folgende vier Bedingungen sind notwendig und hinreichend für Deadlocks (Coffman, Elphick & Shoshani, 1971). Das heißt, treffen alle Bedingungen zu, kommt es zwangsläufig zum Deadlock. Trifft mindestens eine Bedingung nicht zu, wird der Deadlock vermieden.
- Serielle Benutzung von Ressourcen (mutual exclusion), z.B.
synchronized-Methoden in Java - Inkrementelles Ressourcen-Erlangen - Während des Wartens auf eine Ressource gibt ein Prozess bereits erlangte Ressourcen nicht frei
- Keine Preemption - Einem Prozess kann eine bereits erlangte Ressource nicht genommen werden
- Wartezyklus - Eine Prozesskette existiert, innerhalb der jeder Prozess die Ressource hält, auf die sein Vorgänger wartet
Vermeidung
- Detection & Recovery - Terminieren einzelner Prozesse in der Abhängigkeitskette durch Präemptiv
- Vorbeugen - Programme so designen, dass es nicht zum Deadlock kommen kann
Starvation durch Priority Inversion kann durch ungünstige Priorisierung auftreten:
- Ein höher-priorisierter Prozess (Task H) kann einen niedriger priorisierten Prozess (Task L) daran hindern eine Ressource freizugeben
- Wird diese von einem Prozess mit noch höherer Priorität (Task A) benötigt, so muss dieser auf beide warten und unter Umständen aushungern.
Ein Resource Allocation Graph (kurz RAG) ist ein Gerichteter Graph, der die Beziehungen von Prozessen und Ressourcen in Verbindung stellt. Er hilft beim Finden von Deadlocks.
Die Knoten
, die Menge aller Prozesse eines Systems , die Menge aller Ressourcen eines Systems
Zusätzlich definieren wir:
- Anforderungskante - gerichtete Kante
wenn ein Prozess die Ressource haben möchte - Zuweisungskante - gerichtete Kante
wenn ein Prozess Zugriff auf die Ressource hat
Beispiele
Grundlegende Fakten
Es gilt:
- Wenn der Graph keinen Zyklus hat, kann es nicht zu einem Deadlock kommen.
- Wenn der Graph einen Zyklus enthält, kommt es darauf an:
- Falls nur eine Instanz je Ressourcen-Typ existiert, kommt es garantiert zu einem Deadlock
- Falls mehrere Instanzen je Ressourcen-Typ existieren, besteht die Möglichkeit eines Deadlocks
Speichermanagement
Hierarchisches Paging ist eine Variante des Paging, bei der der logische Adressraum auf mehrere Page Tables verteilt wird.
Beispiel Zweistufiges Page Table
Angenommen, eine Adresse wären 32 Bit. Diese würde sich dann zusammensetzen aus
- Einer 22-Bit langen Seitennummer
. Da die Page Table zweistufig ist, setzt sich die Seitennummer wiederum zusammen aus - Der 12-Bit langen Seitennummer
- Dem 10-Bit-langen Seitenoffset
- Der 12-Bit langen Seitennummer
- Einem 10-Bit langen Seiten-Offset
| Seitennummer | Seiten-Offset |
| p1 | p2 | d |
| 12 | 10 | 10 |
Invertierte Page Tables sind eine Variante des Paging. Dabei gibt es nicht für jeden Prozess eine eigene Liste sondern eine große für alle. In den Einträgen stehen die Nummern der zugehörigen Pages, sowie die PIDs der Prozesse, denen die Seiten gehören. Dies Verringert den Speicherbedarf, allerdings wird der Suchaufwand erhöht, weshalb oft ein Hashed Page Table vorgeschalten wird.
Hashed Page Tables sind eine Variante des Paging mit Hilfe von Hashing. Diese kommen oft bei großen Adressräumen (> 32 Bit) zum Einsatz.
Die virtuelle Seitennummer (logische) wird dabei in eine Page Table gehashed. In dieser Page Table befinden sich i.A. Listen von Elementen für Seiten, die auf die gleiche Position gehashed wurden.
Zum Auflösen einer virtuellen Seitenadresse, muss diese mit allen Elementen der zugehörigen Liste verglichen werden. Sobald ein Treffer für eine Seite gefunden wurde, wird der zugehörige Frame aus dem Speicher geladen.
Paging beschreibt eine Methode zur Verringerung von externer Fragmentierung.
Funktionsweise
Dabei wird der physikalische Speicher in Blöcke fixer Größe, sogenannte Frames aufgeteilt. Der logische Speicher wird in gleichgroße Pages aufgeteilt. Jede Page wird auf einen Frame abgebildet.
Framegrößen
Die Größe von Frames ist typischerweise eine Zweierpotenz zwischen
und Bytes.
Fragmentierung
Zwar verringert Paging externe Fragmentierung, doch kommt es wegen der fixen Pagegröße zu interner Fragmentierung.
Das Betriebssystem “führt Buch” über alle freien Frames. Meist ist das eine Liste, wo z.B. steht “Zur Page abc gehört Frame 45 xyz”. Dabei hilft ein page table.
Benötigt ein Programm Speicher, so muss das Betriebssystem genug Frames finden.
Siehe auch
Adressschema
Die von der CPU generierten Adressen beinhalten…
- Seitennummer (p) - Dient als Index für die page table und liefert die Basisadresse
- Seiten-Offset (d) - Dient zur Auffindung des Speicherinhalts und wird auf die Basisadresse addiert
Prozessspezifischer Zugriffsschutz
An jeden Frame wird ein Flag, das sogenannte valid-invalid Bit angefügt. Diese Bits stehen hinter den Einträgen der Page Tables der Prozesse
- valid (v) - Zeigt an, dass eine Seite zum logischen Adressraum des Prozesses gehört, dem der Page Table zugeordnet ist
- invalid (i) - Zeigt an, dass eine Seite nicht zum logischen Adressraum gehört und der Prozess, dem die Page Table mit diesem Eintrag zugeordnet ist, folglich nicht auf die Seite zugreifen darf
Paging Hardware
Siehe auch
Segmentierung beschreibt ein Memory-Management Schema, das der User-Sicht auf die Daten entspricht. Ein Programm besteht hier aus einer Ansammlung von Segmenten, wobei jedes Segment einer logischen Einheit entspricht.
Logische Adressen sind hier Zweiertupel: <segment-nummer, offset>
Begriffe
- Segment Table - Enthält Mehrkomponenten-Adressen, jeder Eintrag beinhaltet:
- base - Physikalische Startadresse im RAM
- limit - Segmentlänge
- Segment-table base register (STBR) - zeigt auf die Segment Table
- Segment-table length register (STLR) - gibt die Anzahl der Segmente eines Programms an
Eine Segmentnummer ist legal wenn sie kleiner als der STLR ist.
- Das Betriebssystem speichert zusätzlich zu jedem Eintrag der Segmenttabelle
- Ein Validierungsbit
- Read / Write / Execute Rechte
- Da Segmente in der Länge variieren, muss Speicher dynamisch reserviert werden
Der Least Recently Used (LRU) Algorithmus ist eine Methode des Page Replacement, bei der das victim der Prozess ist, der am längsten nicht mehr genutzt wurde.
Verwandte Themen
Implementierung
Es gibt mehrere Möglichkeiten, den LRU zu implementieren:
Logische Uhr
Jede Seite bekommt einen Zeitstempel der den letzten Zugriffszeitpunkt speichert. Wenn eine Seite ersetzt werden soll, wird die mit dem kleinsten Zeitstempel gewählt.
Hitliste
Ein spezieller Stack, auf dem die Seitennummern in einer doppelt verketteten Liste gespeichert sind. Wenn eine Seite referenziert wird, wird sie an der obersten Position des Stacks positioniert. Vorteile:
- Der Stack ist viel kleiner als die Page Table, das spart Speicherplatz
- Die älteste (bekannte) Seite liegt immer an der untersten Position, der Zeitaufwand der Suche entfällt also
Reference Bit
- Jede Seite bekommt ein Bit, das zunächst auf 0 gesetzt wird
- Wenn die Seite referenziert wird, ändert sich der Wert zu 1
Wir wissen nicht in welcher Abfolge die Seiten referenziert wurden, aber wir haben ein neues Ersetzungsverfahren: Wir ersetzen Pages Reihum, d.h. eine nach der anderen. Wenn aber die Page das Reference Bit 1 hat:
- Setzen wir ihr Reference Bit auf 0
- Belassen wir die Page im Speicher
- Fahren wir mit der nächsten Page entsprechend fort
Zählverfahren
Für jede Seite gibt es einen Zähler, in dem steht, wie oft die Seite referenziert wurde. Ersetzt wird:
- Beim LFU Algorithmus die Seite mit dem kleinsten Zählwert
- Beim MFU Algorithmus die Seite mit dem größten Zählwert
Ein Argument für MFU wäre, dass die Seiten mit dem kleinsten Zählwert möglicherweise gerade erst geladen wurden und die Verwendung noch bevorsteht.
Weil das nachschlagen der Frames hinter Pages oft passiert und langsam ist, werden oft genutzte Pages in einen Assoziativen Cache zwischengespeichert. Dieser Speicher heißt in diesem Zusammenhang auch Translation Look Aside Buffer (TLB). Wird das zugehörige Frame einer Page in diesem Speicher zwischengespeichert, haben wir glück und können schnell den Speicherbereich aufrufen. Falls nicht, haben wir einen TLB miss und müssen wie gewohnt im langsamen Page Table nachschauen.
Schätzung der effektiven Zugriffszeit
Angenommen, wir haben eine Cache-Trefferquote
Reichweite des TLB
Die Kapazität des assoziativen Speichers ist durch den TLB begrenzt:
Idealerweise passt das Working Set eines Prozesses in den assoziativen Speicher, andernfalls lassen sich Page Faults folgendermaßen verhindern:
- Page Size vergrößern (führt zu einer Zunahme an interner Fragmentierung)
- Unterschiedliche Page Sizes zulassen (Prozess-speziefisches Paging, z.B. angepasst für Kernel-Prozesse)