1. Was ist ein Prozess? (Wie unterscheidet er sich von einem Thread?
! !
Ein Prozess ist ein Programm in Ausfhrung. Ein Prozess hat einen eigenen Adressraum: Text - der Programmcode! Data - die Daten! Stack - temporre daten! (Ein Thread hingegen hat zwar einen eigenen Programm-Counter und Stack, allerdings eine gemeinsame Umgebung mit dem Prozess zu dem er gehrt: Adressraum, offene Dateien, )!
2. Wie werden Prozesse erzeugt?
Der Ursprungsprozess (Proc 0) namens Init wird von Hand erzeugt. !
1. Neue Prozesse sind Kindprozesse und werden per fork() erstellt. Kindprozesse sind eine logische Kopie des Vaters. Gleich sind also:! Adressraum (Text, Daten, Stack)! Offene Dateien ! Umgebungsvariablen ! Pipes! !
2. Ausfhren eines anderen Programms durch das Kind per: exec() (eigentlich: execve()) ! Austausch des Adressraums des Kindes ! Starten des angegebenen Programms !
3.
! Unterscheidbar sind Kind und Vater an der Prozess-ID, d.h. nur daran dass fork() unterschiedliche Ints gibt: 0 beim Kind, ProzessID vom kind beim Vater! !
main() {! int pid;! pid = fork();! if (pid == 0) {! ... Kind ...! } else {! ... Vater ...! }! }!
Wie unterscheiden sich Vater- und Kindprozess voneinander? / Woher wei das Kind, das es ein Kind ist?
4. Wie werden mehrere Prozesse in einer Einprozessormaschine verwaltet?
Es braucht einen Scheduler um quasi-Parallelitt zu simulieren! Der Scheduler Teilt Prozessor fr gewisse Zeitfenster zu! Es gibt eine Liste der lauffhigen Prozesse: Die Run-Queue! Und eine Liste der wartenden Prozesse: Die Sleep-Queue! Gewartet wird hier auf sogenannten Waitingchannels auf bestimmte Ereignisse, die den Prozess wieder lauffhig machen!
5. Was ist Parallelitt, was Nebenlufigkeit?
Paralelitt ! Die Anweisungen zweier Prozesse werden parallel bearbeitet, wenn die Anweisungen unabhngig voneinander zur gleichen Zeit ausgefhrt werden.! parallele Bearbeitung nur auf Multiprozessorsystemen!
Nebenlugkeit! Zwei Prozesse heien nebenlug, wenn ihre Anweisungen unabhngig voneinander abgearbeitet werden. Dabei spielt es keine Rolle, ob die Anweisungen zeitlich durchmischt oder auch echt gleichzeitg bearbeitet werden.!
6. Wie geht Round-Robin, wie kann man darin Prioritten simulieren"?
! !
Funktionsweise ! Run-Queue wird der Reihe nach abgearbeitet! Darf die CPU nur fr eine bestimmte Zeit behalten ! Dann wird er wieder hinten eingereiht in der Run-Queue ! Prioritten-Simulation! Unterschiedlich lange Zeitscheiben ! Mehrfaches Einhngen in die Run-Queue !
7. Woher wei ein Prozess, dass seine Zeitscheibe vorbei ist?
Nach Ablauf der Zeitscheibe (x Clock ticks) ndet ein Interrupt statt. !
8. Trap vs. Interrupt
Trap: Ein Trap ist eine Unterbrechung des Prozesses aus prozessinternen Grnden, normalerweise um einen Systemaufruf (also eine Betriebssystemfunktion wie bspw. das Lesen einer Datei) zu starten. Aber auch: Divison durch 0, Zugriff auf illegale Adresse (fhrt in der Regel zu Programmabbruch), Pagefault!
Der Systemzustand wird gespeichert! die Kernelanfrage wird ausgefhrt! das Ergebnis wird an den Prozess vermittelt! Systemzustand und Kontext wird wiederhergestellt, Prozess luft weiter!
Interrupt: Ein Interrupt ist eine prozessexterne Unterbrechung des Prozesses, z.B. um ein Hardwaresignal zu verarbeiten oder um einen anderen Prozess zum Zuge kommen zu lassen.!
9. Welche Scheduling-Strategie empfiehlst du mir? Was wird bei UNIXSystemen genutzt?
In Unix! I. Abgabe der CPU nach Ablauf der Zeitscheibe ! A. Einstellbare Basisprioritt! B. CPU-Nutzung in jngster Zeit wird einbezogen ! 1. Laufzeit wird auf Konto aufgeschlagen !
2. Konto wird mit der Zeit wieder reduziert um langlebige Prozesse nicht zu benachteiligen ! II. Abgabe der CPU bei Warten auf Ereignis ! A. Ereignis auf das gewartet wird bestimmt Prioritt! B. Betriebsmittel sollen u.U. mglichst schnell wieder freigegeben werden!
Kleinerer Wert = hhere Prioritt !
10. Was ist Paging und warum macht man das? Wann tritt ein Pagefault auf und was passiert dann?
Intention ! Die Beschrnktheit des tatschlich vorhandenen physischen Speicher durch einen virtuellen Speicher kompensieren; einen greren Adressraum zur Verfgung stellen. !
Funktionsweise ! Hauptspeicher wird in Kacheln (Page Frames) fester Gre eingeteilt! Prozessadressrume in Seiten (Pages) gleicher Gre eingeteilt ! letzte Seite muss nicht voll sein: Interne Fragmentierung ! Adressumsetzung ber Page-Tabelle (Untersttzt durch Hardware: Memory Management Unit (MMU))! Bendet sich eine Adresse auf einer Seite, die nicht im physikalischen Speicher liegt, kommt es zu einem sogenannten Page-Fault ! Betriebssystem ldt dann die entsprechende Seite aus dem Hintergrundspeicher (i.d.R. die Festplatte) in den Hauptspeicher (dazu wird ein Trap ausgelst)!
11. Was gibt es fr Verdrngungsalgorithmen beim Paging und wie funktionieren sie etwa?
Ziel! Zukunftsprognosen darber welche Pages im Hauptspeicher bleiben sollten anhand der Devise: Was bisher galt, wird sich demnchst nicht wesentlich ndern (Entspricht dem Lokalittsprinzip von Prozessen)!
! ! !
Methodenkategorien ! Verdrngung nach Bedarf! Durch Pagefault getriggert ! Bereitstellung einer Freispeicherreserve (macht Pagefault schneller behandelbar)! Verdrngung, sobald Minimalreserve unterschritten! Methoden im einzelnen ! First in First out (FIFO)! Entfernt lteste Seiten zuerst! Problem: Wenig brauchbar, da z.B. Daten-/Stack-Pages immer wieder gebraucht werden !
Least-Frequently-Used (LFU)! Je seltener benutzt, desto wahrscheinlicher das unwichtig ! Problem: Zu aufwendig da Zugriffszhle gefhrt werden muss, der selbst Speicherzugriffe
erzeugt.!
Auerdem: Annahme oft nicht stimmig: Pages die vor langer Zeit hug benutzt wurden,
bleiben im Hauptspeicher und frisch geladene Seiten werden entfernt!
Umsetzbarkeit: Nur mit Hardwareuntersttzung und einem Veralterungskonzept (Aging)!
Least-Recently-Used (LRU)! Je lnger nicht genutzt, desto wahrscheinlicher das es unwichtig wird ! Entfernt Seiten auf die am lngsten nicht zugegriffen wurde ! Bewertung: Lokalittsprinzip i.d.R. gut erfasst. Gute Approximation an Optimum, aber:! Erfordert Erfassung der Zugriffszeiten (weitere Speicherzugriffe)! Ohne Spezialhardware zu aufwendig (solche Hardware ist selten)! Neues Ziel also: Approximation von LRU!
Not-Recently-Used (NRU)! Beim Zugriff Referenzbit (R) setzen (Hardwareuntersttzung / weitere Optimierung ntig)! Alterungsprozess: Zurcksetzen des R Bits (z.B. periodisch)! Verdrngung: Seite auswhlen, deren R-Bit nicht gesetzt ist !
Clock-Hand-Algorithmus [Wird in Unix genutzt]! Variante von NRU, die Freispeicherreserve aufbaut ! Nicht gekoppelt an Page-Faults! Zyklisch untersuchender Urzeiger geht ber der Frames im Hauptspeicher ! Ist das R-Bit 0 raus, sonst zurcksetzen und weitersuchen ! Erweiterung: Two-Handed-Clock: Zweiter Zeiger mit festem Abstand: Erster zeiger
setzt R-Bits zurck, zweiter wirft raus, falls noch nicht wieder referenziert !
12. Was ist Segmentierung und warum macht man das?
(enthlt Zeug aus der Wikipedia)!
! !
Adressraum soll "logisch" gegliedert werden: Text-, Data-, Stack-Segmente! Schutz dieser Bereiche (z.B.: Daten knnen nicht als Code interpretiert werden)! Abbildung des virtuellen Adressraums auf den realen Speicher! Textsegment bleibt unverndert, Stack & Datensegment knnen sich verndern!
malloc() fordert zusammenhngenden Speicher an. Intern knnen 3 Strategien unterschieden werden:! First Fit (Am Anfang der Freispeicherliste viele kleine Blcke, Suche Zeitaufwndig)! Next Fit (erst schnell, dann schnelles zerhacken groer Blcke)! Beste Fit (Gut aber Zeitaufwndig, Auerdem: viele extrem kleine Blcke)! Wie kleinere Blcke wieder verschmelzen?! Buddy Algorithmus:! Alle Blcke Gre 2^k !
Segmentierung hat das Problem der externen Fragmentierung!
13. Welche Probleme entstehen bei Nebenlufigkeit, wenn bspw. zwei Threads die Variable i inkrementieren mchten und was verursacht dies? Wie heit dieses Problem genau? Wie kann man dies mit Semaphoren lsen?
! ! !
Beide threads werden (in C) den befehl i++ aufrufen. auf maschinenebene wird der befehl jedoch auf 3 befehle aufgespalten. ! 1. das Lesen der variable i, ! 2. das Hinzuaddieren von 1 ! 3. das Speichern des neuen Werts der Variablen i ! Nun kann es passieren, das der erste Tread den Wert von i liest und danach die Zeitscheibe abgeben muss. Nun kommt der zweite Thread, liest i, erhht den Wert um eins und schreibt den neuen Wert. Dann kommt der erste Thread wieder dran und erhht den alten Wert von i um eins und berschriebt die nderung von dem zweiten Thread.! Was realisiert werden muss ist ein gegenseitiger Ausschlu:! Sema s(1);!
! thread 1&2:! !
s.P();! i++;! s.V();!
dadurch kann nur ein Thread den kritischen Abschnitt betreten!
14. (Was bedeuten die Begriffe: Verhungern, Verklemmung (Deadlock), "After-you-after-you"-Problem?)
! ! ! !
Verhungern (Scheduling):! Ein Thread oder Prozess verhungert wenn er vom Scheduler aus welchen Grnden auch immer dauerhaft nicht die bentigten Betriebsmittel zugeteilt bekommt um seine Aufgabe zu erledigen. !
Verklemmung (Scheduling):! Zusammenfassung ! Zwei oder mehr Prozesse warten auf Betriebsmittel, die nur der/die andere(n) Wartende(n) freigeben kann/knnen! Grnde ! Kombination von Randbedingungen muss vorliegen ! Betriebsmittel werden exklusiv von einem Prozess belegt ! Jeder beteiligte Prozess hat bereits solche Belegungen und wartet auf weitere ! Belegte Betriebsmittel knnen nicht zwangsentzogen werden (geschachtelte kritische Abschnitte) !
After-You-After-You-Problem (Nebenlugkeit):! Schlechte Implementierungen fr gegenseitigen Ausschluss erzeugen dieses Problem: Beide Prozesse knnen durch raceConditions nicht arbeiten, weil sie immer dem anderen Prozess oder Thread den vortritt lassen wollen um gemeinsamen Zugriff auf einen kritischen Abschnitt zu vermeiden.!
15. Wie lst du das Producer-Consumer Problem mit Semaphore? (unbegrenzerter Puffer)1
"
! Sem s(0); ! ! ! ! ! ! ! !
//locked!
//Producer ! erzeugen();! s.V();! !
//s++!
//Consumer! s.P();! ! ! verbrauchen();!
//s--!
16. Wenn der Buffer zum Erzeugen eine Gre von 3 hat, wie lst du das mit Semaphoren?
Sem s1(0); ! Sem s2(3); ! //Producer ! s2.P() !! erzeugen();! s1.V() !! ! ! //locked! //unlocked!
! !
// - auf 2, bleibt unlocked ! // ++ auf 1, wird unlocked !
//Consumer! s1.P(); ! ! verbrauchen();! s2.V();!! !
// - auf 0, wird locked ! // + auf 3, bleibt unlocked !
17. Was ist synchrone und asynchrone Kommunikation? Was passiert bei der asynchronen mit den gesendeten Daten?
! ! ! !
Einordnung ! Unterschieden von: Synchronisation / Kommunikation von (Prozessen/) Threads ber gemeinsame Variablen oder Objekte (Schlossvariablen, Semaphore, Monitoren), da dies einen gemeinsamen Adressraum voraussetzt, der nicht immer gegeben ist. !
Gegenbeispiele: UNIX-Prozesse (statt Threads) ohne Shared Memory, Verteilte System /
Rechnernetze ! Benutzung in der Interprozesskommunikation ! durch send(Prozess2, Nachricht) und receive(Prozess1, Puffer) ist gegenseitiger Ausschluss implizit, einseitige Synchronisation implizit. !
Nachrichtenaustausch kann auch auf gemeinsamen Variablen simuliert werden ! Kommunikationskanal = gemeinsamer Speicherbereich !
Senden einer Nachricht = Schreiben einer Variable! Empfangen einer Nachricht = Lesen einer Variable ! Wenn man das so macht, ist Schutz des gemeinsamen Speicherbereichs erforderlich: Locks,
Monitore, etc. !
Bedeutung in Rechnernetzen !
Synchrone Kommunikation! send()/recive() sind blockierend! Sender / Empfnger warten aufeinander ! Setzt wissen ber Empfangsbereitschaft voraus; in verteilten Systemen nicht ohne weiteres
bekannt !
Verklemmungsgefhrdet wenn nicht aufeinander abgestimmt !
! ! ! !
Asynchrone Kommunikation! send() nicht blockierend ! receive() i.d.R. schon ! Senden vor Empfangsbereitschaft mglich. Erfordert Puffern im Kommunikationskanal ! Gefahr: Pufferberlauf; Alternative: send() wirft bei berlauf Fehler; receive() bei leeren Puffer !
Synchrone Kommunikation durch asynchrone Operationen! Obwohl technisch anders mglich, warten auf Empfangsbesttigung einbauen ! Asynchrone Kommunikation durch synchrone Operationen! Pufferprozess einfhren! Modellierung mit Semaphoren ! Asynchrone Kommunikation !
Sema s1(0);!
! !
! !
Prozess1 ... send(Nachricht); s1.V():
Prozess2! ...! s1.P():! receive(Nachricht);!
Synchrone Kommunikation (annhernd) ! Sema s1(0);! Sema s2(0);!
Prozess1! ! ...! ! ! send(Nachricht);! s1.V():! ! s2.P();! !
! ! ! ! !
! ! ! ! !
Prozess2 ! ! s1.P();! receive(Nachricht);! s2.V();!
!
17. Was wird in Unix-Systemen benutzt? Wohin gehren Sockets?
(Unnamed) Pipes: Unidirektional (mssen den selben Vaterprozess haben) ! Named Pipes: Bidirektional!
Sockets: Biderektional, nicht nur sequentielle Bytestrme, auch ber Systemgrenzen hinweg,
untersttzt unterschiedliche Kommunikationsformen: !
Bidirektionale Pipe (TCP) "Telefongesprch"! Bytestrom ! sequentielle bertragung! zuverlssig! verbindungsorientiert ! Datagram-Socket (UDP) "Brief-/Paketzustellung"! Nachrichten (Pakete)! beliebige Reihenfolge! u.U. unzuverlssig (Verluste, Duplikate) ! verbindungslos !
! !
