Anwenderprogramme laufen im user-Mode, im Systemmodus sind nur previligierte Aufrufe erlaubt,. Systemaufrufe (Syscalls) dienen als Schnittstelle zum BS.
Bsp.: Datei öffnen, Dateiattribute abfragen
Implementiert heutzutage durch Software Interrupts, damals durch feste Adressen
Jeder Syscall hat feste ID, Anwndungsprogramm legt diese ID + Aufrufparameter in bestinteb Registren ab und sendet Interrupt. BS checkt diese Register und führt dann Syscall aus.
strace zeigt die Systemaufrufe an, die ein Aufruf durchführt
strace -c <Aufruf der angezeigt werden soll>
Bei ls werden nur die Dateien die an sich betrachtet, bei ls -la
auch noch die versteckten Dateien.
mult(2, 3) → mult(1, 3) → mult(0, 3)
Register, Rücksprungadresse, Parameter, Ergebnis
nach Prolog des HP als caller
register |
1004 (Rücksprungadresse) |
3 (Parameter) |
2 (Parameter) |
nach Prolog des UP1 als Callee
register |
1004 (Rücksprungadresse) |
nach Prolog von UP1 als Caller
register |
1004 (Rücksprungadresse) |
register |
4004 (Rücksprungadresse) |
3 |
1 |
nach Prolog von UP2 als Callee
register |
1004 |
register |
4004 |
nach Prolog von UP2 als caller
register |
1004 |
register |
4004 |
register |
4004 |
3 |
0 |
nach Prolog von UP3 als Callee
register |
1004 |
register |
4004 |
register |
4004 |
nach epilogue von UP3 als callee
register |
1004 |
register |
4004 |
register |
0 |
nach epilogue von UP2 als caller
register |
1004 |
register |
4004 |
nach epilogue von UP2 als callee
register |
1004 |
register |
3 |
nach epilogue von UP1 als caller
register |
1004 |
nach epilogue von UP1 als callee
register |
6 |
nach epilogue von HP als caller
a) falsch (s.S. 4)
b) wahr (s.S. 5)
c) wahr (s.S. 5)
d) wahr (s.S. 43)
e) falsch (s.S. 9)!!!
a) Multiprogramming, logischer Mehrprogrammbetrieb, also die pseudoparaööeöe/verzahnte Ausführung von Prozessen.
b) Hauptvorteil: Effizienssteigerung
der Prozessor kann einen anderen Prozess bearbeiten, wenn der aktuelle auf z.B. E/A wartet.
c) Multiprocessoring: Echt parallele Ausführung von Prozessen auf verschiedenen Prozessoren
(+) Erhöhung der Rechenleistung ohne Verdopplung der Peripherie
(+) Schneller als Multiprogramming
(-) Komplexer für den Programmierer
(-) Betriebssystem muss entsprechend seine Scheduling-Algorithmen anpassen können
a) sehr hohe Redundanz, hoher Wartungsaufwand, Programmcode wird länger, Rekursion nicht möglich.
b)Aufrufe geschlossener Unterprogramme erfordern Sprünge, Parameterübergabe, Sicherung, Wiederherstellung des Kontexts usw.
c) Call-by-Value: die Wert an sich
Call-by-Reference: Speicheradresse wird übergeben → Referenz/Zeiger
d) Mit dem Sprungbefehr wird die Adresse der aufzurufenden Sequenz in den Programm Counter geschrieben.
e) bei JMP wird „nur“ gesprungen, bei CALL wird zusätzlich die Rücksprungadresse auf den Stack oder ein Register gelegt.
f) Zwei Möglichkeiten:
Adresse | Befehl | Kommentar | Nach der Befehlsausführung | |||||
---|---|---|---|---|---|---|---|---|
PC | RA | SP | R1 | R2 | R3 | |||
- | - | - | 405 | null | null | 23 | 42 | null |
405 | PUSH R1 | Sichern der CPU Register | 406 | null | 0 | 23 | 42 | null |
406 | PUSH R2 | 407 | null | 1 | 23 | 42 | null | |
407 | PUSH p3 | Platz für Ergebniss reservieren (p3=irgendwas) | 408 | null | 2 | 23 | 42 | null |
408 | PUSH p2 | Parameter rückwerts auf den Stack pushen | 409 | null | 3 | 23 | 42 | null |
409 | PUSH p1 | 410 | null | 4 | 23 | 42 | null | |
410 | CALL 770 | Unterprogrammaufruf | 770 | 411 | 4 | 23 | 42 | null |
770 | POP R1 | Parameter holen | 771 | 411 | 3 | p1 | 42 | null |
771 | POP R2 | 772 | 411 | 2 | p1 | p2 | null | |
772 | POP R2 | Stack dekrementieren für ergebniss | 773 | 411 | 1 | p1 | p2 | p3 |
Unterproigramm: Halt, Stop, Jetzt rechne ich | ||||||||
810 | PUSH R3 | Ergebniss auf den Stack pushen | 811 | 411 | 2 | p1 | p2 | p3' |
811 | RET | 411 | null | 2 | p1 | p2 | p3' | |
411 | POP R3 | Ergebniss vom Stack holen | 412 | null | 1 | p1 | p2 | p3' |
412 | POP R2 | Wiederherstellung der CPU Register | 413 | null | 0 | p1 | 42 | p3' |
413 | POP R1 | 414 | null | null | 23 | 42 | p3' |
(ai) Nicht erglaubt: Prozess muss immer erst in den Ready Zustand wechseln, bevor er ausgeführt werden kann.
(aii) Erlaubt: Der Prozess wartet auf dein Ergebnis
(aiii) Nicht erlaubt: Ohne Ausführung kann ekin Ereigniss eintreten, auf das er warten müsste
(bi)
(bii) Ready-Zustand kann eingespart werden, da Prozesse Komplett unterbrechungsfrei abgearbeitet werden. Blocked zustand wird weiterhin benötigt, da manche Prozesse auf E/As warten.
(biii) Es ändert sich gar nichts, da das Model nur einen Prozess beschreibt
(bii)
a) Skript S. 38/39.
b)
c)
a)ready suspend to ready - blocked suspend to blocked: Freie Resourcen auf dem Hauptspeicher → Laden..
ready to ready suspend - blocked to blocked suspend: Der Hauptspeicher ist ausgelastet, Prozesse werden ausgelagert.
blocked suspend to ready suspend - blocked to ready: Das Ergebniss, auf das der Prozess gewartet hat, tritt ein.
b) i) falsch - enter, dispatch, suspend, exit
ii) falsch - Timeout: Die Zeit, die der Prozess zum Rechnen zugewiesen bekommen hat, ist abgelaufen.
iii) wahr
iv) wahr
v) falsch - der Prozesskontrollblock ist Teil des Prozessdeskriptors.
Prozessdeskriptor: Zusätzliche Information zu einem Prozess. Aka Prozess-Image. Siehe S 50 Skript?
a)
i) Wahr
ii) Falsch
iii) Wahr
iv) Flasch. Bei Stack haben wir nur auf den obersten Element Zugriffe.
b) Skript S.47-49.
Prozessidentifikation (PID, PPID, …) wird benötigt um den Prozess referenieren zu können.
Prozesszustandsinformation (Nutzerregister, PC, SP) wird benötigt um einen Prozess nach einer Unterbrechung wieder herzustellen.
Prozesskontrollinformationen (Prozesszustand, Priorität, bisherige Rechenzeit) wird benötigt um den Prozess entsprechend der angewandten Schedulingstrategie korrekt zu Schedulen
c) PCB: enthält die für das Betriebsystem relevanten (kontroll-)Informationen zu einem Prozess.
Prozess-Image: bezeichet die Gesamtheit der physischen Bestandteile eines Prozesses.
a) Moduswechsel: Wechsel zwischen System- und Nutzermodus oder umgekehrt.
b) Programmstatuswort: PSW
c) Kontextswitch: Sicherung und Wiederherstellung des Kontextes von „alten“ und neuem Prozess.
d) Aktualisierung und Sicherung des PCB, als:
Einfügen des PCB in die Warteschlange des Schedulers.
Selektion des nächsten auszuführenden Porzesses.
(Wieder)herstellung des kontextes des neuen Prozesses.
e) Anzahl der (CPU-)Register
f) i) zB Unterbrechungsbehandlungsroutinen, also Vorgänge in der BS-Aufrufe benötigt werden, zB Ausgabe auf den Bildschirm.
ii) Der Scheduler setzt den Status eines Prozesses von running auf ready und wählt einen anderen Prozess zur Azsführung aus.
iii) Beenden eines Prozesses → Unterbrechungsbehandlung und anschließend wechsel zu einem anderen Nutzerprozess.
Frage: Wer schedult den Scheduler?
g) Eher schlechte Idee - Der gewählte Ansatz verfolgt kurzfristige Ziele Änderungen von Anwendungen können auch den Bedarf von mehr Registern rechtfertigen.
Okay für Ampeln die immer nur Rot-Grun-Geld können, aber unfug sobald die Ampel zB auch noch Töne kennen soll.
a) Skript S.43/44.
b) Es gibt Querbezüge: Speicher, E/A-Geräte, Dateien werden für einzelne Prozesse verwaltet.
Es bestehen Querbeziehungen z.B. zwischen I/O-Tabelle und Prozesstabelle.
Ein Prozess benutzt ein Gerät/Kanal und das muss irgendwo vermerkt werden.
c)
Für die Prozesslokalisierung wird das Prozess-Image verwendet. Das besteht aus dem auszuführenden Programm, Nutzerdaten, Stack und PCB, der die Attribute enthält.
a) Wechsel von Benutzer- in Systemmodus
b)
c) Wechsel eines Prozesses, also die vollständige Kontextsicherung des aktuellen und Kontextaktualisierung und wiederherstellung eines neuen Prozesses.
d)
e)
Anzahl der Register
f i)
nur Moduswechsel: Systemaufruf, danach wird zum Prozess zurückgekehrt.
f ii)
nur Kontextwechsel: Prozesswechsel durch Zustandswechsel. Bei manchen Betriebssystemen sind Prozesswechsel keine Systemfunktionen, ein Prozess kann also, wenn er z.B. von running
auf ready
wehcselt, dies ohne Moduswechsel tun.
f iii)
Moduswechsel mit Kontextswitch: aktueller Prozess hat Unterbrechungsbehandlung ausgeführt und kann danach nicht weiter ausgeführt werden. Es wird zu einem neuen Prozess gewechselt.
g)
Schlechte Idee, da hier nur kurzfristig Zeit ….
a) Ansonsten würde die gesamte Anwendung bis zur Beendung der Berechnung blockiert
b)
User-Level | Kernel-Level | Prozess | |
---|---|---|---|
Generierung | Gering kein Aufruf von Systemroutinen. Etwas Verwaltungsaufwand innerhalb der Anwendung | Mittel Man benötigt bereits Systemroutinen, muss aber kein komplettes Porzessimage erstellen | Hoch es muss auf Systemroutinen zugegriffen werden. Zusätlich muss neuer Speicher allokiert werden und ein neuer Prozess erzeugt werden |
Kommunikation und Datenaustausch | einfach und effizient: direkter Zugriff auf den gemeinsamen Speicher. | Same as User-Level. | Interprozesskommunikation, da kein gemeinsamer Speicherbereich vorhanden ist. |
Scheduling | Übernimmt das Anwendungsprogramm. | Betriebssystem. | Betriebssystem. |
Multiprozessingplattform | kein Nutzen. | möglich. | möglich. |
c) zur Berechnung erscheinen Kernel-Level-Threads am Sinnvollsten.
KLT
ULT
Prozess
a)
b)
Es gibt folgende Zustände
Folgende Translationen werden durch Funktionen durchgeführt
start()
→ ready to runyield()
→ ready to runjoin()
→ blockedsleep()
→ blockedwait()
→ blockednotify()
→ ready to runnotifyAll()
→ reasdy to runyield()
: Thread gibt freiwillig seine Rechenzeit ab.sleep()
vs. wait()
: sleep(time)
wartet eine bestimmte Zeit, wird dann wieder automatisch „read to run“. wait()
wartet auf notify()
, notifyAll()
, muss also „außen“ wieder aktiviert werden.a) Es gibt follgete Zustände
Folgende translationen werderen durch funktionen durchgefürt
rund()
-Methode fertig → daedsleep()
beendet → ready to runjoin()
beendet → ready to runb) heute: Kernel-Level-Threads früher: User-Level-Threads, wegen Platformunabhängigkeit. Nicht jedes BS auf dem Java lief hat KLTs angeboten
T: Mittlere Bedienzeit (Zwit, die ein Prozess bis zur Abarbeitung im Zustand running verbringt)
S: Overhead für Prozesswechsel
Q: Größe der Zeitscheibe
P: T/T_{eff} = T / {T+n*S}
n = \ceil T/ Q
b)
* Q > T
n = \ceil T / Q = 1
p = T / {T+S}
⇒ Entartung zu FCFS, da jeder Prozess komplett zu Ende rechnen kann
Q = S « T
p = T / {T+{\ceil T / S} * S = T \ {2*T} = 0,5
* Q \aprox 0 ( Q → 0 )
\lim_{Q → 0} \ceil {T / Q} = \infty
\lim_{n → \infty} T / {T+n*S} = 0
c)
„Trifft ein Prozess zum zeitpunkt t ein, so wird er direkt zum zum zeitpunkt t beachtet“ bedeutet, das er da in die Queu kommt, nicht den anderen unterbricht.
siehe Blatt
Erster Teil, siehe Blatt
d)
Zwei Prozesse: A und B
Betriebsmittel: X, Y und Z
t_{ij}: Zeitdauer, die BM_i von Prozess j benötigt wird
t_j: Dauer fpr Prozess j
kein Deadlock wenn: t_{XA} + t_{YA} + t_{ZA} < t_A und t_{XB} + t_{YB} + t_{ZB} < t_B
kein Deadlock wenn: t_{XA} * t_{XB} + t_{YA} * t_{YB} + t_{ZA} * t_{ZB} < t_{A} * t_{B}
Deadklock immer wenn: t_{XA} + t_{YA} + t_{ZA} > t_A und t_{XB} + t_{YB} + t_{ZB} > t_B
Deadlock immer wenn: siehe Angabe … Fuuu
Alle Aussagen falsch
siehe blatt
a)
Es kann ein deadlock auftreten, da alles synchronices
ist.
b)
T1: a.swapContent(b); T2: b.swapContent(a);
c)
System.identityHashcode(Object);
public void swapContent(Box other) { if(this == other) { // Don't swap the same objects return; } else if(System.identityHashcode(this) < System.identityHashcode(other)) { this.doSwapContent(other); } else { other.doSwapContent(this); } }
b) Mi(Leser(wartend), Leser(lesend), Anzahl Leser, Schreiber(wartend), Schreiber(schreibend))
M0(3,0,2,3,0)
↔
M1(2,1,1,3,0) M3(3,0,0,2,1)
↔
M2(1,2,0,3,0)
c) Der Petrinetz ist nicht fair. Wenn stetig Leseprozesse eintreten, können Schreibeprozesse nie abgearbeitet werden.
Die Lösung wäre, Schreibprozesse höher zu priorisieren.
Algorithmus von Peterson
a) Druckaufträge können verloren gehen.
aktiver Prozess | auseführte Codezeile | Inhalt von W | Wert von next |
---|---|---|---|
p1 | 2 | prt_file1 | 0 |
p2 | 2 | prt_file2 | 0 |
p1 | 3 | prt_file2 | 1 |
p2 | 3 | prt_file2 | 2 |
b) For p1:
a = true //I want y = 1 //You may while (y = 1 && b = true){ //do nothing } W[next] … … a = false
For p2:
b= true y = 0 while (y = 0 && b = true){ //do nothing } W[next] … … b = false
c) busy-waiting: Der Peterson-Ansatz verschwendet CPU Zeit. Ein Prozess, dem der Eintritt in den kritischen Bereich verwährt wurde, muss in seiner Schleife selbst prüfen wann er dran ist.
a) Semaphore ist eine Kontrollkomponente
init(Semaphor, Anfangswert)
- setzt die Zählvariable der Semaphore auf ausgangswert.wait()
, down()
)S–; if(S < 0) { Prozess in warteschlange an stelle -S ; }
signal()
, up()
)S++; if(S⇐ 0) { Setze den am längsten wartenden Prozess auf „rechnend“ ; }
p()
!b) Anzahl der Prozesse, die gleichzeitig in ihre kritische Phase eintreten dürfen. (Anzhal der Prozesse die hintereinader die Prolog operation ausführen können, ohne blokiert zu werden)
c) Bei einer Vertauschung von 3) und 4) in P1 wäre nicht mehr gewährleistet, dass P1 vor Belegung des Semaphors S überprüft, ob Platz >= 0 ist.
Ist dies nicht der Fall, kann P2 nämlich nicht in seinen kritischen Bereich eintreten.
Ist der Semaphor S aber von P1 belegt, dann kann P2 ebenfals nicht in seinen kritischen Bereich eintrten und Platz nicht erhöhen ⇒ Deadlock
d) ka wo das hingehört
P1 1 S=0 P1 2 platz=-1 -> blockiert P2 1 P2 2 s=-1 -> blockiert
init(S, 1) init(platz, 0) init(bestand, 5) P1: wait(S) -> S=0, P1 macht weiter P1: wait(platz) -> platz = -1, P1 wird in die Warteschlange gesetzt P2: wait(bestand) -> bestand = 4, P2 macht weiter P2: wait(S) -> S = -1, P2 auf warteschlange
⇒ Deadlock
i)
init(x, 2) init(y, 0) init(z, 2) P1: 3 P1: 4 P3: 3 P3: 4
Es geht zwar noch ein paar Zeilen weiter, aber es ist ab hier der deadlock sicher. ⇒ Kein Prozess rechnet zu Ende.
ii)
init(x, 3) init(y, 0) init(z, 2) P1: 3 P1: 4 P1: 5 P1: 7 P2: 3 P2: 5 P2: 6 P3: 3 P3: 4 P3: 5 P3: 7 P3: 8
iii)
init(x, 3) init(y, 0) init(z, 2) P1: 3 P1: 4 P2: 3 P2: 5 P2: 6 P1: 5 P1: 7 P3: 3 P3: 4
⇒ Deadlock. Nur P1 und P2 rechnen zu ende
iv)
init(x, 0) init(y, 0) init(z, 3) P3: 3 P3: 4 P3: 5 P3: 7 P3: 8 P2: 3 P2: 5 P2: 6 P1: 3
⇒ Deadlock. Nur P2 und P3 kommen zu einem Ende.
To be scanned
a. Lockmechanismus mit Warteschlange.
Jedem Objekt wird ein Lock zugeordnet. Ein Threat kann nur dann auf eine synchornised-Methode eines Objekts zugreifen, wen dieses verfügbar ist.
Das Lock wird bei Verlasssen der synchronized-Methode wieder freigegeben.
b. wait() und notifyAll().
c. Bei „echten“ Monitoren werden Klassen synchronisiert, in Java Objekte bzw. Methoden dieser Objekte (public variablen können immer noch von außen bösartig verändert werden).
d. Der wesentliche Unterschied besteht im Fehlen von Bedingungs-Variablen, konkret wäre ein Aufruf von wait(Bedingung) nicht möglich.
e.
f. Signal and continue.
War mal Klausuraufgabe
a. wahr
b. falsch
c. falsch
d. falsch
e. falsch
receive(): queue.remove(i); print(); return.message; … wait();
send(): notifyAll();
run(): String message = box.recieve(this.type);
a) Statische Speichergrpartitionierung
b)
a)
Baum following shortly.
b) In den belegten Segmenten entstehen - Freibereiche, da die Prozesse die Segmente nicht voll ausfüllen.
→ interne Fragmentierung
Insgesamt stehen nur noch 320kB Speicher zu verfügung
c) P5 kann nicht mehr geladen werden, da kein 512kB großes Segment zu verfügung Steht (und 356kB nicht ausreichen).
d) Das Buddy-Verfahren kombiniert die Vorteile fester Partitionierung mit den Vorteilen der dynamischen (einfache Adressierung & Flexibilität) insbesondere bei vielen kleinen Anfragen kommt es zu weniger internen Fragmentierung als bei fester Partitionierung.
a) i)
Virtueller Speicher mit 16 „Schubladen“. Durchnumeriert von 0000 zu 1111.
Physischer Speicher mit 8 „Schubladen“. Durchnumeriert von 000 zu 111.
Skizze Folgt.
ii)
Offset: Portion/Byte innerhalb einer Seite
iii) 8196_10 = 0010 0000 0000 0100_L
b) 1 Byte Wortgröße, 12 des 32 Adressbits werden für den Offset benützt.
2^32/2^12 = 2^20 = 1.048.576
→ Daraus ergibt sich die maximale Größe des HS: 4GB
Der physische Speicher ist immer eine Teilmenge des virtuellen Speichers. Ziel ist es ja, den Prozesssen einen linearen Speicher dynamischer Größe zu Verfügung zu stellen.
c) Lösung: Mehrstufige Seitentabelle.
a) i) DS, BS
ii) FS, BS
iii) DS, BS
b) i) First, Next
ii) Best, Worst
iii) Best
iv) First
c) Anzahl der Seitenfehler: 12 Stellen
d) 512kB großer Speicher, 2kB minimaler Segment.
→ 523/2 = 256 → 8 Bits