THIS IS UNOFFICIAL, THERE ARE NO GUARANTEES FOR ANYTHING 5 Programmiersprachenebene Übersetzung (Kompilierer) 4 Assembliersprachenebene Übersetzung (Assemblierer), Bindung (Binder) 3 Maschinenprogrammebene Teilinterpretation (OS) 2 Befehlssatzebene (CISC) Interpretation (Mikroprogramm) 1 Mikroarchitekturebene (RISC) Ausführung 0 digitale Logikebene 0 - 3: Interpretation, System, numerisch 4 - 5: Übersetzung, Anwendung, symbolisch 0 - 2: Firm-/Hardware 3 - 5: Software Speicher: Adressraum: -physisch (0 - 2^n-1): nicht jede Adresse gültig, gibt Lücken -logisch (n - m): pro Prozess, jede Adresse gültig, keine Lücken -virtuell: wie logisch, aber nicht jede Adresse liegt im Hauptspeicher -Exklusion: total private Adressräume für alle Programme -Inklusion: partiell private Adressräume Maschinenprogramme Verwaltung Freispeicher: -Bitkarte: Stücke fester Größe; bei Paging -Lochliste: verschiedene Größen, aber Mindestgröße; bei Segmentierung Speicherzuteilung/Platzierungsstrategien: -best-fit: kleinste ausreichende Lücke: Verschnitt minimieren (Nachteil: externe Fragmentierung) -worst-fit: größte ausreichende Lücke: Suchaufwand minimieren Verschmelzung angrenzender Löcher aufwändig -first-fit: erste ausreichende Lücke: Laufaufwand minimieren -next-fit: wie first, aber ab letzter Fundstelle: Verschnitt ausgleichen mehr Verschnitt (FF mehr als NF) Speicherladestrategie: on demand, anticipatory -Anforderung: Referenzierung, Seitenfehler, Einlagerung, Verbuchung (present bit = 1), Wiederanlauf Speicherersetzungsstrategien: FIFO, LFU, LRU -LRU: aging register, Zeitgeber (periodische Unterbrechung) -zweite Chance: FIFO mit use bit -dritte Chance: dirty bit Dateisysteme: -kontinuierliche Speicherung: Fragmentierung, gut für Echtzeitsysteme -verkettete Speicherung: fehleranfällig, wenn Verzeigerung kaputt; FAT -indizierte Speicherung: feste Anzahl Blöcke im Indexblock -Freispeicherverwaltung durch Bitvektoren Prozesse: Prozesseinplanung: -kurzfristig: bereit, laufend, blockiert -mittelfristig: schwebend bereit, schwebend blockiert -langfristig: erzeugt, gestoppt, beendet Betriebsmittel: -dauerhaft: begrenzt, wiederverwendbar, teilbar/unteilbar (zeitweise exklusiv) (CPU, GPU, RAM, kritischer Abschnitt, Variable) -vorübergehend: unbegrenzt, konsumierbar (Interrupt, Trap, Meldung, Datenstrom) Prozessgewichtsklassen: -feder (User-Threads): im lokalen Benutzeradressraum, Kernel sieht nur einen Kontrollfluss -leicht (Kernel-Threads): teilt sich Benutzeradressraum, Kernel sieht jeden Thread einzeln, vertikale Isolation von OS -schwer ("Prozess"): im eigenen Kernadressraum, horizontale Isolation von anderen Prozessen Prozesswechsel: kein/ein/zwei Adressraumwechsel (feder/leicht/schwer) Kriterien Einplanung: -benutzerorientiert: Antwortzeit, Durchlaufzeit, Termineinhaltung, Vorhersagbarkeit -systemorientiert: Durchsatz, Prozessorauslastung, Gerechtigkeit, Dringlichkeit, Lastausgleich für Betriebsart wichtig: -allgemein: Gerechtigkeit, Lastausgleich -Stapelbetrieb: Durchlaufzeit, Durchsatz, Prozessorauslastung -Dialogbetrieb: Antwortzeit -Echtzeitbetrieb: Termineinhaltung, Vorhersagbarkeit, Dringlichkeit Kriterien Einplanungsalgorithmen: -kooperativ vs präemptiv -deterministisch vs probabilistisch -statisch (off-line) vs dynamisch (on-line) -asymmetrisch vs symmetrisch Einplanungsalgorithmen: -first come first served: CPU intensiv begünstigt; Konvoi-Effekt -round robin: Zeitscheiben, periodische Programmunterbrechungen; Konvoi-Effekt -virtual round robin: Vorzugsliste, variable Zeitscheiben -shortest process next: erwartete Bedienzeit; Verhungern -highest respone ratio next: periodische Umplanung, höhere Wartezeit -> höhere Priorität -shortest remaining time first: spontane Umplanung, wenn laufender Prozess länger dauert als Eintreffender -> Laufender verdrängt -multilevel queue: separate Ready Listen nach Prozesstypen; zwischen Listen statisch (feste Prioritäten, Verhungern) oder dynamisch (Zeitmultiplexen) -multilevel feedback queue: Hierarchie von Ready Listen, unten RR sonst FCFS, Zeitscheibengrößen nehmen nach unten zu; penalization (lange Prozesse nach unten) durch preemption, aging (Prozessse unten finden seltener statt), und anti-aging (nach Bewährungsfrist wieder anheben) Synchronisation: Simultanverarbeitung: -vertikal: Multiplexen -horizontal: Multi Core Synchronisationsarten: -multilateral: Wechselseitiger Ausschluss, bei unteilbaren Betriebsmitteln; Semaphor, Monitor, Schlossvariable (blockierend; pessimistisch, d.h. vermutlich Konkurrenz) atomar, transaktionales Programm/Speicher (nichtblockierend; optimistisch, d.h. vermutlich keine Konkurrenz) -unilateral (logisch/bedingt): Reihenfolgenbildung, bei konsumierbaren Betriebsmitteln; Unterbrechung, Fortsetzung, Verdrängung (unterdrückend) Lebendigkeit: -behinderungsfrei: Prozess beendet in endlicher Anzahl an Schritten -sperrfrei: jeder Schritt lässt nichtsequentielles Programm voranschreiten, systemweiter Fortschritt, aber Aushungerung -wartefrei: Anzahl auszuführender Schritte ist nach oben begrenzt, systemweiter Fortschritt, keine Aushungerung Monitore: -Monitorwarteschlange, Ereigniswarteschlange(n) Monitorarten: -Hansen: blockierende Bedingungsvariablen (Signalnehmer Vorrang, Signalgeber verlässt), alle Signalnehmer signaled -Hoare: blockierende Bedingungsvariablen (Signalnehmer Vorrang, Signalgeber verlässt), ein Signalnehmer fährt fort -Mesa: nichtblockierende Bedingungsvariablen (Signalgeber Vorrang), Signalgeber bleibt, einer oder alle Signalnehmer signaled -Java: wie Mesa, aber nur eine Ereigniswarteschlange für gesamten Monitor Neuauswertung der Wartebedingung toleriert falsche Signalisierungen (alle außer Hoare) Umlaufsperre: wechselseitiger Ausschluss in Software durch Kreiseln -atomares acquire mit test and set (Speicherbus "gesperrt", Cache stark beansprucht), compare and swap (Speicherbus "gesperrt"), Kreiseln mit Ablesen (bei großem Wettstreit immer noch häufig Bussperre), Kreiseln mit Zurückhaltung (Verweilzeit), Kreiseln mit proportionaler Zurückhaltung (angestaute Prozesse zählen, nächster Prozess wird ausgewählt; kein Verhungern) Transaktion: Aktion(sfolge), gelingt/scheitert als Ganzes -Nachteile blockierender Synchronisation: Leistung, Robustheit (im kritischen Abschnitt abstürzen), Interferenz (mit Scheduler), Lebendigkeit (Verhungern/Verklemmung) -Kreiseln mit Bedingung: Schleifendauer bedeutet Nutzarbeit Verklemmung: wechselseitiger Ausschluss, Nachforderung, Unentziehbarkeit, zirkulares Warten -Verklemmungsvorbeugung: mindestens eins von: nichtblockierender Synchronisation, Atomarität, Betriebsmittel virtualisieren für Entzug, Ordnung der Betriebsmittel -Verklemmungsvermeidung: analytische Maßnahme zur Laufzeit, unsicheren Zustand vermeiden durch Betriebsmittelgraph/Bankiersalgorithmus -Verklemmungsnachweis und Erholen: sporadische Suche mit Betriebsmittelgraph, Zyklen werden durchbrochen (Prozesszerstörung oder Betriebsmittelentzug/Zurückrollen)