Muirauqa's Brain

Wiederholung:

Abarbeitung von Maschienenbefehlen

• Speicher: lineares Array von Information Einheiten
  • Speicherzelle: kleinste adressierbare Speichereinheit
  • Speicherkapazität: m*n^n = 1byte*2^32 = 4GB
    • n = Länge der Adresse
    • m = Länge/Breite einer Speicherzelle

• CPU
  • Datenprozessor [von Datenbuss]
    • MBR = Memory Buffer Register [von
    • IR = Instruction Register
  • Befehlsprozessor [zu Adressbus]
    • PC = Programmcounter (n)
    • MAR = Memory Adress Register (n) [von PC]

Abarbeitung von Machinenprogram:

1. MAR ← PC
2. MBR ← S[MAR]
3. IR ← MBR
4. decode(IR)
5. if not „Sprungebefehl“ then
6. _<stelle operanden bereit>
7. _PC ← PC + 1
8. else
9. _PC ← Sprungadresse
10. end

Problem: Oft gleiche/ähnlche Abläufe

• Offene Unterprogramme (Strg + C & Strg + V)
  • Fehleranfällig
  • Mühsam
  • Höchstens bei x^2, |x|, …
• Gesclossene Unterprogramme (Prozedur)
  • Programmstück wird über Anfangsadresse angesprungen (Addresse der speicherzelle, mit der es beginnt)
    • Anouncement (A → B)
    • Invocation (A → B dann B → A)
      Kommunikation erfolgt wie:
      • Stack
        • Zugriff von oben, oberste Adresse ist 0, unterste 2^(n-1)
      • Spezielle Register

2 Dinge unterscheiden

• Sprungbefehl JMP
  COMMAND JMP addr
  BEGIN
  _ PC ← addr
  END
• Prozeduraufruf
  Sprung wie oben + Sicherung des Rücksprungs
  • Stack
    • COMMAND CALL addr
      BEGIN
      _ PUSH(PC + 1)
      PC ← addr
      END
    • COMMAND RET
      BEGIN
      _ PC ← POP
      END
  • Register
    • COMMAND CALL addr
      BEGIN
      _ RA ← PC + 1
      _ PC ← addr
      END
    • COMMAND RET
      BEGIN
      _ PC ← RA
      END

HP:
  ...
  4000 ...
  ...
  4100 CALL 4500
  4101
  ...

Prozedur 1:
  4500 ...
  ...
  4600 CALL 4800
  4601 ...
  ...
  4650 CALL 4800
  4651 ...
  ...
  4700 RET

Prozedur 2.
  4800 ...
  ...
  4890 RET

• Unterprogramme (Prozeduren, Funktionen)
• Komponenten eines BS / BS als Ganzes
• Nuzerprogramme
• Prozesse

Modell-Maschiene

• PC
• SP
• 16 Register (R0 bis R15; R15 vorbelegt)
  • R12 Ablageadresse des ersten Parameters
  • R13 Basisadresse des lokalen Datenraums des Unterprograms

Stack baut sich auf:

HP:
  4000 ...
  ...
  40?? PUSH pn
  ...
  4098 PUSH p2
  4099 PUSH p1
  4100 CALL 4500
  4101 POP p1
  4102 POP p2
  ...
  41?? POP pn
  
Prozedur:
  4500 PUSH // Alle Register R14 to R0 auf Stack
  4501 MOVE 64+SP, R12 //p1 in R12
  4502 MOVE SP, R13
  ...  <up>
  ???? MOVE R13, SP
       POP R
       RET

PROCEDURE fak(k:INT) RETURNS INT
BEGIN
  IF k=0 THEN RETURN 1
  ELSE RETURN k*fak(k-1)
END
  

• Prozesskontext: Um Prozess auf dem selben Rechner fortzuführen
• Prozessimage: Um Prozess auf anderem Rechner zu starten

Arten (paralleler) Ausführung:

• Uniprogramming: Nacheinander (auch keine Unterbrechung bei warten auf I/O)
• Multiprogramming: pseudo-parallel
• Multiprocessoring: echt-parallel

Multiprogramming rechnungen (!) Siehe script S. 30

Prozess erzeugen

1. PID erzeugen
2. Speicher reservieren
3. PCB erzeugen
4. In Scheduller queues eintragen
5. Sonstige Datenstrukturen erzeugen

• Not running
• running

• ready (queue)
• running
• blocked (queue)
• new
• exit

• ready
• running
• blocked
• ready, suspend
• blocked, suspend
• new
• exit

• Seiten/Speicher Tabellen
  • Freier Hauptspeicher
  • Freier Virtueller Speicher
  • Prozess → Virtueller Speicher
  • Virtueller Speicher → Hauptspeicher
  • Schutzatribute
• I/O Tabellen
  • Geräte Status
  • Geräte Zuordnung
  • mmap
• Datei Tabellen
• Prozess Tabellen
  • PCB

• Prozesslokalisierung
• Prozessdeskriptor
  • Prozessadressraum / lokalisierung
  • PCB

• Prozessidentifikation
  • PID
  • PPID
  • UID
• Prozesszustandsinformationen
  • Register
  • PSW (Programm Status Word)
• Prozesskontrollinformationen
  • Scheduler Infos
    • ready/blocked/running/…
    • Priorität
    • Erwartete Ereignisse
    • Sonstige Scheduler Atribute
  • Nächste PID (linked list)
  • Signale (IPC)
  • Nachrichten (IPC)
  • Rechte

1. Update PCB des alten Prozesses
2. Alten Prozess in Queue des Schedulers einfügen
3. Scheduler wählt neuen Prozess
4. Wiederherstellen des PCB des neuen Prozesses

• Systemmodus / Kernel mode
• Nutzermodus / User mode (Eingeschränkt ⇒ Support-Funktion des OS verwenden a.k.a. Syscall)

Aktueller Modus steht in PSW (Programm Status Word)

1. Update des PCB (nicht vollständig)
2. Privilegien Ändern
3. Sprung zu Unterbrechungsroutine

Bei

• Externe Unterbrechungen (Interrupt)
  z.B. I/O
• Interne Unterbrechungen (Exceptions/Traps)
  z.B. Fehler
• Unterbrechungsroutine (Interrupt Handler)
  Eine OS funktion

Lösung: Prioritäten

IPL (Interrupt Priority Level) Teil des PSW (Programm Status Word)

• Prozess
  Eigentümer/Verwalter von Resourcen
• Thread / lightweight process
  Aufgabe abarbeiten

Pro Thread

• TCB
• User Stack
• Kernel Stack

Zustände

• Ready
• Running
• Blocked
• (alles andere sinnlos

Arten

• ULT (User level threads)
  • (+) Keine speziellen Rechte
  • (+) Eigener angepasster Scheduler
  • (+) Keine OS anforderungen
  • (-) Einer blokiert ⇒ Alle blokiert
  • (-) Nutzt nur einen Kern
• KLT (Kernel level threads)
  • (+) Einer blokiert ⇒ Anderer running
  • (+) Nutzt alle Kerne
  • (-) Moduswechsel für Threadwechsel nötig
• Kombiniert

http://www.uml-diagrams.org/examples/java-6-thread-state-machine-diagram-example.html|Perfektes Diagramm (Zu beachten ist, das objekte noch eine lock- und wait-pool haben. Ein Thread ist BLOCKED wenn es im lock-pool eines objekts ist, indem es eine syncronizes pasage betreten will. Ein Thread ist *WAITING wenn es im wait-pool eines Objekts ist, indem es wait() in einem syncronized block aufgerufen hat (s. Monitor weiter unten).

Doku des Thread.State.

Advanced shit ⇒ Uninteresant:

http://en.wikipedia.org/wiki/Flynn's_taxonomy

Aufgabenverteilung

• Scheduler
  Algorithmus der nächsten Prozess bestimmt
• Displatcher
  Programm was context switcht

3 Zustands Prozessmodell ⇒ Short Term Scheduling 5 Zustands Prozessmodell ⇒ Medium Term Scheduling 7 Zustands Prozessmodell ⇒ Long Term Scheduling

Scheduling Arten

• Nicht preemptiv (freiwillige kontrollabgabe möglich, z.B. bei warten auf I/O)
  • FIFO/FCFS (First Come First Served)
    • (+) Fair
    • (+) Einfach
  • SJF/SPN (Shortest Process Next)
    • (+) Optimale mittlere Verweildauer
    • (*) Vorsehung der Ausführungszeit?
    • (-) Verhungern
• Preemptiv
  • SRT/SRPT (Shortest Remaining Processing Time)
    • (+) Theoretisch Optimal
    • (-) Verhungern
    • (!) (Neue) Kürzere Prozesse unterbrechen den laufenden
  • RR (Round Robin) / Zeitscheibenverfahren
    • (+) Kein Verhungern
    • (+) Einfach
    • (*) Mittlere Verweildauer ist OK
  • PS (Priority Scheduling)
    • (?) Der beschreibung nach eher nicht preemptiv????
  • Multilevel Feedback Queueing
    • Freiwillige abgabe ⇒ gleiche FIFO queue
    • Timeout abgabe ⇒ nächst niedrigere FIFO queue
    • Niedrigste queue: RR

Mittlere Verweildauer:
FCFS > RR > SRPT/SJF (best)

Allgemeine Anforderungen

• Fair
• Policy Enforcement (keine Ausnahmen)
• Balance (System auslasten)
• Datensicherheit
• Skalierbarket
• Effizienz (CPU auslasten)

System Arten / Anforderungen

• Batch
  • Durchsatz
  • Verweildauer
  • Prozessorauslastung
• Interaktiv
  • Antwortzeit
  • Verhältnismäsigkeit
  • Interaktion (Viele nutzer)
• Echtzeit
  • Sollzeitpunkte
  • Vorhersagbarkeit

Zeitpunkte

• Ankunftszeit (erstes ready)
• Beendigungszeit (erstes done)
• Startzeit (erstes running)

Zeitspannen

• Verweildauer (erstes ready - done)
• Bedienzeit (im zustand running)
• Wartezeit (nicht im zustand running)
• Normalisierte Verweildauer = Verweildauer / Bedienzeit (1 = gut, >1 schlechter)

Verweildauer = Bedienzeit + Wartezeit

• Antwortzeit (alternativ: Reaktionszeit auf Ereignisse)
• Remote
  Antwortzeit > Verweildauer
• Lokal
  Antwortzeit = Verweildauer

• 1 Queue
• Queue pro Priorität
• Queue pro Priorität

Mittlere Verweildauer bei der Reihenfolge $t_{i_1}, t_{i_2}, \dots, t_{i_n}$ (← das ist doch keine Reihenfolge (?)) ist: \[ \frac{1}{n} (t_{i_1} + (t_{i_1} + t_{i_2}) + \cdots + (t_{i_1} + t_{i_2} + \cdots + t_{i_n})) = \frac{1}{n} \sum^n_{k=1}\sum^k_{j=1}t_{i_j} = \frac{1}{n} \sum^n_{k=1}(n-k+1)t_{i_k} \]

Das ist offensichtlich minimal wenn \[ n \cdot t_{i_1} + (n-1) \cdot t_{i_2} + \cdots + 2 \cdot t_{i_{n-1}} + 1 \cdot t_{i_{n-1}} = min \]

die ist schon wieder offensichtlich minimal wenn gilt: \[ t_{i_1} < t_{i_2} < \cdots < t_{i_{n-1}} < t_{i_n} \]

Prozessfortschrittsdiagramm

• unsicherer Bereich
• unmöglicher Bereich

Alle 4 Deadlockbedingungen müssen werfüllt sein

• Indirekte Methoden
  • Mutal Exclusion
    • Prozesse >= 2
    • Exklusive resourcen >= 2
  • Hold and Wait
    • Mindestens 1 Resource besitzen
    • weitere anfordern
  • No Preemption (Resource kann nicht zwangsentzogen werden)
• Direkte Methoden
  • Circular wait

Begriffe

• Stellen
• Marken
• Kapazität
• Transitionen
  • Aktiv
  • Gefeuert
• Eingangskanten
• Ausgangskanten
• Gewicht

Default

• Kantengewicht: 1
• Stellenkapazität: \infty

Erreichbarkeitsgraph

• Verklemmungsfrei
  Alles zyklisch
• Partial deadlock/Teilweise Verklemung
  Nicht alles erreichbar
• deadlock/Verklemmung
  Keine Nachfolger

deadlock ⇒ partial deadlock

Achtung: Werden mehere Marken eingesamelt, so werden dennoch nur eine (default) abgegeben.

• Umordnen

Ablaufverhalten:

• Syncron
  Vorbestimmt (ähnlich RTOS)
• Asynchron
  Ereignisgesteuert (Zufällig)

Mutex Bedingunegn:

• Mutual exclusion
  • Nur 1 Prozess im kritischen Bereich
• Progress
  • Nur die Kandidaten entscheiden unter sich
  • (Unbeeinflusst von Prozessen die nicht rein wollen)
• Bounded Waiting
  • Jeder der will darf
  • In endlicher Zeit
  • ⇒ Wer im Kritischen bereich ist muss da wieder raus (dar z.B. nicht drinn sterben)

Busy waiting: while(not condition) { nop; }

• 2 Semphore für Speicherplatz und 1 für Speicherzugriff = 3 Semaphonre
• Lösung mit
  • Ringbuffer, wenn
    • 1 Erzeuger
    • 1 Verbraucher
  • Mutex

Erzeuger

while(true) {
   el = clreate();
 
   wait(out);
   wait(s);
 
   push(el);
 
   signal(s);
   signal(in);
}

Verbraucher:

while(true) {
   wait(in);
   wait(s);
 
   pop();
 
   signal(s);
   signal(out);
}

• Es ist darauf zu achten das nicht ein leser/schreiber alle schreiber/leser blokieren kann

• Jeder Philosoph könnte sich ein Stäbchen nehmen ⇒ Keiner kann essen
• ⇒ Weiterer semaphore der Anzhal esser begrenzt

while(true) {
   wait(esser);
   wait(stäbchen[i]);
   wait(stäbchen[(i+1) % n]);
 
   essen();
 
   signal(stäbchen[(i+1) % n]);
   signal(stäbchen[i]);
   signal(esser);
}

• (-) Nur 2 Prozesse

flag[0] = true;             // Ich will
while (flag[1] == true) {   // Solange der andere will oder tut
   if (turn ≠ 0) {          // und ich bin nicht dran
      flag[0] = false;      // ziehe mein "will" zurück, bis ich wieder dran bin
      while (turn ≠ 0) {    // (so kann der andre aus der Äuseren Schleife raus)
        // busy wait
      }
      flag[0] = true;
   }
}
 
// <critical section>
//   ...   
// </critical section>
 
turn    = 1;
flag[0] = false;

Nur 2 Prozesse!

• (+) Belibige Anzahl an Prozessen

/* claim the resource */
flags[i] = BUSY;
 
/* give away the turn */
turn = j ;
/* wait while the other process is using the resource *and* has the turn */
while ((flags[j] == BUSY) && (turn != i )) {
}
 
// <critical section>
//   ...   
// </critical section>
 
/* release the resource */
flags[i] = FREE;

• http://en.wikipedia.org/wiki/Peterson's_algorithm
• http://www.cs.wvu.edu/~jdm/classes/cs550/notes/tech/mutex/Peterson.html

• (-) Nicht für echte Paralelität
• (-) Im Userland unmöglich
• (+) Belibige Anzahl an Prozessen

• Kein Bounded Waiting (scheduller kann ihn immer zurücksetzen).
• (+) Belibige Anzahl an Prozessen

Test and Set ist ein atomarer Maschienenbefehl.

bool testAndSet(int * i) {
   if(*i == 0) {
      *i = 1;
      return true;
   }
   else {
      *i = 1;
      return false;
   }
}

while(testAndSet(i) == false) { nop; }
 
// <critical section>
//   ...   
// </critical section>
 
i = 0;

http://en.wikipedia.org/wiki/Test-and-set

• Kein Bounded Waiting (scheduller kann ihn immer zurücksetzen).
• (+) Belibige Anzahl an Prozessen

Test and Set ist ein atomarer Maschienenbefehl.

bool testAndSet(bool * lock) {
   bool old = *lock;
   *lock = true;
   return old;
}

while(testAndSet(lock) == true) { nop; }
 
// <critical section>
//   ...   
// </critical section>
 
lock = false;

• Warteschlange ⇒ Fair & kein busy waiting
• signal() dekrementiert auch unter 0
• wait(S = 0) ⇒ wait!
• Trick: init() mit 0 ⇒ Man kann auf etwas warten lasesen (syncronisation)

• Bedingungen (nicht nur i > 0)
• Monitorprozeduren
  • wait() Aufruf ⇒ Ein anderer Thread darf in den selbe Monitor
• Lokale Daten
  • Nur über Monitor Prozedur zugreifbar
• cwait()
• csignal()

Java-Style

Adressierung

• Direkt
  • Empfange von jedem
  • Empfangsfilter (auf Prozesse)
• Indirekt (Queues)
  • 1:1 …
  • n:1 Ports
  • 1:n Broadcasting
  • n:m Mailbox

• Wiederauffinden
  Wo habe ich was hingemapt / ausgelagert
• Schutz
  Kernel/User space
• Teilen/Aufteilen
  gleiche lib
• Logische Organisation
  clusterung
• Physische Organisation
  kopieren beim paging

• Interne Fragmentierung
  In einer Partition
• Externe Fragmentierung
  Zwischen den Partitionen

• Feste Partitionierung (interne Fragmentierung)
  • gleich große Partitionen
  • unterschiedlich große Partitionen
• Dynamische Partitionierung (externe Fragmentierung)
  • Best-Fit
    Finde Platz im gesamten Speicher
  • First-Fit
    Finde Platz von Anfang an
  • Next-Fit
    finde Platz ab letztem Treffer
• Buddy Systeme (interne & externe Fragmentierung)
• Gewichtete Buddy systeme (interne & externe Fragmentierung)

$2^L \le 2^K \le 2^U \le 2^N$

• N (fix): gesamter Speicher
• U (fix): größter Block
• K: Variable Block Größe
• L (fix): kleinster Block

Entfernen: Rekursiver Merge!

Seitentabelle

• Demand Paging
  Kein Vorladen
• Demand Prepaging
  Seitenfehler ⇒ Vorladen
• Look-Ahead-Paging
  Random bedingung ⇒ Vorladen

• Resident Set Management Policy
  Frame muss drinn bleiben
• Fetch Policy
  Frame Vorlade Strategie
• Placement Policy
  Irrelevant
• Replacement Policy
  • OPT
  • FIFO
  • LIFO
  • LRU
  • LFU
    Zugriffe seit …
    • laden der Seite
    • Zeit
    • letztem Seitenfehler
  • Climb
  • Clock
  • Working Set

Vorwärtsabstand: Löschen was am längsten nicht mehr gebraucht wird

Zugriff: Nix Ersetzen: Durchdrücken

Zugriff: Ganz Hochzeihen Ersetzen: Durchdrücken

Bei: Starker Lokalität

Zugriff: Eins Hochbubblen Ersetzen: Unten austauschen

• Zeiger zeigt auf älterestes Element
• Use flag
  • Neu: 1
  • Zugriff: 1
  • Zeiger überstreich: 0
• Zeiger löscht Use Bit 0

W(t, h) = Menge der h letzten referenzierten Seiten, seit einschließlich t w(t, h) = | W(t, h) |

• h fix
• Jeder Prozess hat w(t, h) Pagages
• Ersetze was nicht in Workin set, sonst: Prozess auslagern

Bei: Starker Lokalität

FIFO: Mehr Seiten ⇒ ggf. mehr page faults

Anforderungsreihenfolge der Pages

Von wo eine zugegriffene Page hochgezogen wird (1-Indexiert)

Mittlere Zeit zwischen Seitenfehlern

Mehr Frames ⇒ Anszahl an Seitenfehlern wird kleiner oder bleibt gleich

• $C_k$ Anzahl an $k$ Elementen in Distance String
• $F_m$ Anzahl an Seitenfehlern

\[ F_m = \sum^n_{k=m+1} C_k + C_\infty \]