Inhaltsverzeichnis

Prozesse

Programme und Unterprogramme

Programm -> Mscgienenprogramm

Wiederholung:

Abarbeitung von Maschienenbefehlen

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

Unterprogramme und Prozeduren

Problem: Oft gleiche/ähnlche Abläufe

Die Befehle CALL & RET

2 Dinge unterscheiden

Unterprogrammaufrufe

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

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

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

Module

Realisierung eines UP-Aufrufs

Modell-Maschiene

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

Rekursive Prozeduraufrufe

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

(3) Prozess

Name Wie Was
Programm Statisch Code
Prozess Dynamisch Programm in Ausführung
→ Im Speicher
→ Eigener Kontext

Arten (paralleler) Ausführung:

Multiprogramming rechnungen (!) Siehe script S. 30

Fork/Prozesshierachie

Prozess erzeugen

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

2-Zustands Prozessmodell

5-Zustands Prozessmodell

7-Zustands Prozessmodell

Tabellen

PCB

Kontextswitch

  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

Modus

Aktueller Modus steht in PSW (Programm Status Word)

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

Unterbrechung

Bei

Unterbrechungskonflikte

Lösung: Prioritäten

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

(4) Threads

Pro Thread

Zustände

Arten

Threads
1 n
Prozesse 1 Klassisch Normal
m Thread kann Prozess wechseln
z.B. Cloud 		n:1 und 1:m kombiniert
z.B. TRIX

Java-Thread Modell

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

Single Data Multiple Data
Single Instruction SISD (für
Alte, normale CPUs 		SIMD
Normale CPUs mit SSE/3Dnow
Vektorprozessoren / Arrayprozessoren
Multiple Instruction MISD
Fehlertolerante Rechner (Flugzeuge) 		MIMD
Normale Multicore CPUs
Rechnerverbunde (Supercomputer)

(5) Scheduling

Aufgabenverteilung

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

Scheduling Arten

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

Allgemeine Anforderungen

System Arten / Anforderungen

Zeitpunkte

Zeitspannen

Verweildauer = Bedienzeit + Wartezeit

Optimalitätsbeweis von SJF

$n$ Anzahl Jobs
$t_j$ Ausführungszeit eines Jobs
$i_j$ Permutation der Jobs

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} \]

(6) Deadlocks

Prozessfortschrittsdiagramm

Alle 4 Deadlockbedingungen müssen werfüllt sein

Petrinetze

Begriffe

Default

Erreichbarkeitsgraph

deadlock ⇒ partial deadlock

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

Lösungen

(7) Prozesskoordination

Quasi Paralell Parallel
Unabhängige
Abläufe
Abhängige
Abläufe 		Nebenläufigkeit

Ablaufverhalten:

Mutex Bedingunegn:

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

Probleme

Erzeuger/Verbraucher

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);
}

Leser/Schreiber

Philosophen

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);
}

Mutex algos

Algorithmus von Decker

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!

Algorithmus von Petterson

/* 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;

Interrupts disablen

Test and Set (int)

Test and Set ist ein atomarer Maschienenbefehl. 

bool testAndSet(int * i) {
   if(*i == 0) {
      *i = 1;
      return true;
   }
   else {
      *i = 1;
      return false;
   }
}
In Out
i i return
0 1 true
1 1 false 
while(testAndSet(i) == false) { nop; }
 
// <critical section>
//   ...   
// </critical section>
 
i = 0;

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

Test and Set (bool)

Test and Set ist ein atomarer Maschienenbefehl. 

bool testAndSet(bool * lock) {
   bool old = *lock;
   *lock = true;
   return old;
}
In Out
lock lock return
false true false
true true true 
while(testAndSet(lock) == true) { nop; }
 
// <critical section>
//   ...   
// </critical section>
 
lock = false;

Semaphor

Monitor

Java-Style

Messages

Send
Blocking Non Blocking
Receive Blocking Rendezvous Post-Modell
Non Blocking Mit/Ohne Buffer

Adressierung

(8) Speicher

Speicherverwaltung

Fragmentierng

Speicherpartitionierung

Normale Buddy Systeme

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

Entfernen: Rekursiver Merge!

Gewichtete Buddy Systeme

Normal 1:1 Split
Jetzt $2^n$ ⇒ 1:3 split
$3 \cdot 2^n$ ⇒ 1:2 split

VM

HGS HS
Pages/Seiten Frames/Seitenrahmen

Adresstranslation

Seitentabelle

Paging (Vorlade) Strategien

Paging Policies

OPT

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

FIFO
Z E
Fr 1 3 3 4
Fr 2 2 2 2 3
Fr 3 1 1 1 1 2

Zugriff: Nix Ersetzen: Durchdrücken

LRU
Z E
Fr 1 3 2 4
Fr 2 2 2 3 2
Fr 3 1 1 1 1 3

Zugriff: Ganz Hochzeihen Ersetzen: Durchdrücken

Bei: Starker Lokalität

Climb
Z E
Fr 1 3 2 2
Fr 2 2 2 3 3
Fr 3 1 1 1 1 4

Zugriff: Eins Hochbubblen Ersetzen: Unten austauschen

Clock
Working Set

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

Bei: Starker Lokalität

Begriffe

Belady's Anomalie

FIFO: Mehr Seiten ⇒ ggf. mehr page faults

Reference String

Anforderungsreihenfolge der Pages

Distance String

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

Ref. Str. 2 3 1 3 3
1 2 3 1 3 3
2 4 2 3 1 1
3 1 4 2 2 2
4 1 4 4 4
Dist. Str. ? ∞ 4 2 1
Lifetime-Function L(m)

Mittlere Zeit zwischen Seitenfehlern

Stack Algorithmus

Mehr Frames ⇒ Anszahl an Seitenfehlern wird kleiner oder bleibt gleich

Anzhal Seitenfehler aus Distance String

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