Muirauqa's Brain

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.
Prozesse
===== Programme und Unterprogramme =====
==== Programm -> Mscgienenprogramm ====
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]


{{:users:skruppy:ext:uni:3:2_1-maschine.jpg?direct&200|}}


Abarbeitung von Machinenprogram:
  - MAR <- PC
  - MBR <- S[MAR]
  - IR <- MBR
  - decode(IR)
  - if not "Sprungebefehl" then
  - _<stelle operanden bereit>
  - _PC <- PC + 1
  - else
  - _PC <- Sprungadresse
  - end

==== Unterprogramme und Prozeduren ====

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

=== Die Befehle CALL & RET ===
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

=== Unterprogrammaufrufe ===
<code>
HP:
  ...
  4000 ...
  ...
  4100 CALL 4500
  4101
  ...

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

Prozedur 2.
  4800 ...
  ...
  4890 RET
</code>

=== Module ===
  * Unterprogramme (Prozeduren, Funktionen)
  * Komponenten eines BS / BS als Ganzes
  * Nuzerprogramme
  * Prozesse

==== Realisierung eines UP-Aufrufs ====
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:

{{:users:skruppy:ext:uni:3:2_3-up_aufruf.jpg?direct&200|}}

<code>
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
</code>

====Rekursive Prozeduraufrufe====

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

===== (3) Prozess =====
^ Name ^ Wie ^ Was ^
| Programm | Statisch  | Code |
| Prozess  | Dynamisch | Programm in Ausführung \\ -> Im Speicher \\ -> Eigener Kontext |

  * Prozess//kontext//: Um Prozess auf dem //selben// Rechner fortzuführen
  * Prozess//image//: 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

==== Fork/Prozesshierachie ====
{{:users:skruppy:ext:uni:3:fork.png?500|}}

Prozess erzeugen
  - PID erzeugen
  - Speicher reservieren
  - PCB erzeugen
  - In Scheduller queues eintragen
  - Sonstige Datenstrukturen erzeugen

==== 2-Zustands Prozessmodell ====
  * Not running
  * running

==== 5-Zustands Prozessmodell ====
  * ready (queue)
  * running
  * blocked (queue)
  * new
  * exit

==== 7-Zustands Prozessmodell ====
  * ready
  * running
  * blocked
  * ready, suspend
  * blocked, suspend
  * new
  * exit

{{:users:skruppy:ext:uni:3:9.png?500|}}


==== Tabellen ====
  * 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
  * Prozess//deskriptor//
    * Prozess//adressraum// / //lokalisierung//
    * PCB


==== PCB ====
  * Prozess//identifikation//
    * PID
    * PPID
    * UID
  * Prozess//zustandsinformationen//
    * Register
    * PSW (Programm Status Word)
  * Prozess//kontrollinformationen//
    * Scheduler Infos
      * ready/blocked/running/...
      * Priorität
      * Erwartete Ereignisse
      * Sonstige Scheduler Atribute
    * Nächste PID (linked list)
    * Signale (IPC)
    * Nachrichten (IPC)
    * Rechte

==== Kontextswitch ====
  - Update PCB des alten Prozesses
  - Alten Prozess in Queue des Schedulers einfügen
  - Scheduler wählt neuen Prozess
  - Wiederherstellen des PCB des neuen Prozesses
==== Modus ====
  * //System//modus / Kernel mode
  * //Nutzer//modus / User mode (Eingeschränkt => Support-Funktion des OS verwenden a.k.a. Syscall)

Aktueller Modus steht in PSW (Programm Status Word)

  - Update des PCB (nicht vollständig)
  - Privilegien Ändern
  - Sprung zu Unterbrechungsroutine

=== Unterbrechung ===
Bei
  * Externe Unterbrechungen (Interrupt) \\ z.B. I/O
  * Interne Unterbrechungen (Exceptions/Traps) \\ z.B. Fehler
  * Unterbrechungsroutine (Interrupt Handler) \\ Eine OS funktion

== Unterbrechungskonflikte ==
Lösung: Prioritäten

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

===== (4) Threads ====
  * 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

^ ^^ 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|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 [[http://docs.oracle.com/javase/1.5.0/docs/api/java/lang/Thread.State.html|Thread.State]].

Advanced shit => Uninteresant:

[[http://en.wikipedia.org/wiki/Flynn's_taxonomy]]
^ ^ //S//ingle //D//ata ^ //M//ultiple //D//ata ^
^ //S//ingle //I//nstruction | **SISD (für ** \\ Alte, normale CPUs | **SIMD** \\ Normale CPUs mit SSE/3Dnow \\ Vektorprozessoren / Arrayprozessoren |
^ //M//ultiple //I//nstruction | **MISD** \\ Fehlertolerante Rechner (Flugzeuge) | **MIMD** \\ Normale Multicore CPUs \\ Rechnerverbunde (Supercomputer) |

===== (5) Scheduling =====
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

==== 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
  * 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

==== Petrinetze ====
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.
==== Lösungen ====
  * Umordnen
===== (7) Prozesskoordination =====
^ ^ Quasi Paralell ^ Parallel ^
^ //Un//abhängige \\ Abläufe | | |
^ Abhängige \\ Abläufe | | Nebenläufigkeit |

Ablaufverhalten:
  * Syncron \\ Vorbestimmt (ähnlich RTOS)
  * Asynchron \\ Ereignisgesteuert (Zufällig)

[[http://phoenix.goucher.edu/~kelliher/cs42/sep27.html|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; }''
==== Probleme ====
=== Erzeuger/Verbraucher ===
{{:users:skruppy:ext:uni:3:petri-ev.png?400|}}
  * 2 Semphore für Speicher//platz// **und** 1 für Speicher//zugriff// = 3 Semaphonre
  * Lösung mit
    * Ringbuffer, wenn
      * 1 Erzeuger
      * 1 Verbraucher
    * Mutex

Erzeuger
<code c>
while(true) {
   el = clreate();
   
   wait(out);
   wait(s);
   
   push(el);
   
   signal(s);
   signal(in);
}
</code>

Verbraucher:
<code c>
while(true) {
   wait(in);
   wait(s);
   
   pop();
   
   signal(s);
   signal(out);
}
</code>

=== Leser/Schreiber ===
  * Es ist darauf zu achten das nicht ein leser/schreiber alle schreiber/leser blokieren kann

=== Philosophen ===
  * Jeder Philosoph könnte sich ein Stäbchen nehmen => Keiner kann essen
  * => Weiterer semaphore der Anzhal esser begrenzt

<code c>
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);
}
</code>
==== Mutex algos ====
=== Algorithmus von Decker ===
  * (-) Nur 2 Prozesse

<code c>
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;
</code>

Nur 2 Prozesse!

=== Algorithmus von Petterson ===
  * (+) Belibige Anzahl an Prozessen

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

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

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

=== Test and Set (int) ===
  * Kein //Bounded Waiting// (scheduller kann ihn immer zurücksetzen).
  * (+) Belibige Anzahl an Prozessen

//Test and Set// ist ein atomarer Maschienenbefehl.

<code c>
bool testAndSet(int * i) {
   if(*i == 0) {
      *i = 1;
      return true;
   }
   else {
      *i = 1;
      return false;
   }
}
</code>

^ In ^ Out ^^
^ ''i'' ^ ''i'' ^ return ^
| 0 | 1 | true |
| 1 | 1 | false |

<code c>
while(testAndSet(i) == false) { nop; }

// <critical section>
//   ...   
// </critical section>

i = 0;
</code>

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

=== Test and Set (bool) ===
  * Kein //Bounded Waiting// (scheduller kann ihn immer zurücksetzen).
  * (+) Belibige Anzahl an Prozessen

//Test and Set// ist ein atomarer Maschienenbefehl.

<code c>
bool testAndSet(bool * lock) {
   bool old = *lock;
   *lock = true;
   return old;
}
</code>

^ In ^ Out ^^
^ ''lock'' ^ ''lock'' ^ return ^
| false | true | false |
| true | true | true |

<code c>
while(testAndSet(lock) == true) { nop; }

// <critical section>
//   ...   
// </critical section>

lock = false;
</code>

=== Semaphor ===
  * 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)

=== Monitor ===
  * 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()''

{{http://upload.wikimedia.org/wikipedia/commons/thumb/d/db/Monitor_%28synchronization%29-SU.png/565px-Monitor_%28synchronization%29-SU.png?300}}

Java-Style

{{http://upload.wikimedia.org/wikipedia/commons/thumb/f/f5/Monitor_%28synchronization%29-Java.png/377px-Monitor_%28synchronization%29-Java.png?200}}

=== Messages ===
^ ^^ Send ^^
^ ::: ^^ Blocking ^ Non Blocking ^
^ Receive ^ Blocking |  Rendezvous  |  Post-Modell  |
^ ::: ^ Non Blocking |  Mit/Ohne Buffer  ||


Adressierung
  * Direkt
    * Empfange von jedem
    * Empfangsfilter (auf Prozesse)
  * Indirekt (Queues)
    * **1:1** ...
    * **n:1** Ports
    * **1:n** Broadcasting
    * **n:m** Mailbox
===== (8) Speicher =====
==== Speicherverwaltung ====
  * Wiederauffinden \\ Wo habe ich was hingemapt / ausgelagert
  * Schutz \\ Kernel/User space
  * Teilen/Aufteilen \\ gleiche ''lib''
  * Logische Organisation \\ clusterung
  * Physische Organisation \\ kopieren beim paging

==== Fragmentierng ====
  * Interne Fragmentierung \\ In einer Partition
  * Externe Fragmentierung \\ Zwischen den Partitionen

==== Speicherpartitionierung ====
  * 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)
=== Normale Buddy Systeme ===
$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!**

{{:users:skruppy:ext:uni:3:speicher-buddy.png?400|}}

=== 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

{{:users:skruppy:ext:uni:3:speicher-vm-tab.png?400|}}

=== Paging (Vorlade) Strategien ===
  * Demand Paging \\ Kein Vorladen
  * Demand **Pre**paging \\ Seitenfehler => Vorladen
  * Look-Ahead-Paging \\ Random bedingung => Vorladen

=== Paging Policies ===
  * 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

== 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 ==
  * Zeiger zeigt auf älterestes Element
  * Use flag
    * Neu: 1
    * Zugriff: 1
    * Zeiger überstreich: 0
  * Zeiger löscht Use Bit 0
== Working Set ==
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

=== 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 ====
  * $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 \]
users/skruppy/ext/uni/3/bs.txt · Zuletzt geändert: 2013/04/17 14:10 von 84.56.31.122