CS计算机代考程序代写 ER Betriebssysteme (BS)

Betriebssysteme (BS)
Probeklausur
https://ess.cs.tu-dortmund.de/DE/Teaching/SS2019/BS/
Horst Schirmeier
horst.schirmeier@tu-dortmund.de
https://ess.cs.tu-dortmund.de/~hsc
AG Eingebettete Systemsoftware mit Material von Olaf Spinczyk, Informatik 12, TU Dortmund Universität Osnabrück

Ablauf
Probeklausur
Eigenständiges Bearbeiten/Lösen der Aufgaben (30-40 Minuten) Besprechung der Aufgaben
Auswertung
Weitere Hinweise zur Vorbereitung
●
– – – –
●
wenn noch Zeit übrig ist:
Fortsetzung der Vorlesung „Systemsicherheit“
Probeklausur Betriebssysteme 01.07.2019
2

Probeklausur
… in (fast) allen Belangen realistisch:
Art der Aufgaben
Auswahl aus dem gesamten Inhalt der Veranstaltung Betriebssystemgrundlagen und UNIX-Systemprogrammierung in C Vorlesungen und Übungen sind relevant
●
– – –
●
–
●
– – –
●
Die Klausur wird nicht eingesammelt. Probeklausur Betriebssysteme 01.07.2019
Umfang
kürzer als das „Original“: 45 statt 60 Punkte
Durchführung idealerweise wie bei der richtigen Klausur
keine Hilfsmittel (keine Spickzettel, Bücher, …) bitte still arbeiten
jeder für sich
3

1 – Prozesse und Scheduling
a) Prozesserzeugung – Was wird ausgegeben?
●
43 43
43 43
int counter;
void *erledigeArbeit(void *param) {
counter++;
printf(“%d\n”, counter);
return NULL;
}
int main(void) {
counter = 42;
}
pthread_t id;
pthread_create(&id,
NULL,
erledigeArbeit,
NULL);
pthread_join(id, NULL);
erledigeArbeit(NULL);
return 0;
43 44
43 44
Probeklausur Betriebssysteme 01.07.2019
4
int counter;
void *erledigeArbeit(void *param) {
counter++;
printf(“%d\n”, counter);
return NULL;
}
int main(void) {
}
counter = 42;
if (fork() == 0) {
erledigeArbeit(NULL);
} else {
erledigeArbeit(NULL);
}
return 0;

1 – Prozesse und Scheduling
a) Prozesserzeugung
Wieso ist die Ausgabe unterschiedlich?
● pthread_create()
●
–
● fork()
– Erzeugt neuen Prozess
– Kopiert Adressraum
→ eigene Version von Data, BSS, Heap und Stack
– Erzeugt neuen Thread
– Legt eigenen Stack an
– Teilt sich Data, BSS und Heap
Jeder hat
Jeder hat
sein eigenes „counter“
sein eigenes „counter“
Probeklausur Betriebssysteme 01.07.2019
5
Beide teilen sich
Beide teilen sich
ein „counter“
ein „counter“

1 – Prozesse und Scheduling
b) Prozesse
1) Was geschieht mit den Kindprozessen, wenn der Elternprozess
terminiert?
(engl. „orphan processes“)
Ein UNIX-Prozess wird zum Waisenkind, wenn sein Elternprozess terminiert.
Was passiert mit der Prozesshierarchie?
●
–
●
●
init (PID 1)
init (PID 1)
getty tty0 login bash
exit!
firefox
firefox
6
init (PID 1) adoptiert alle verwaisten Prozesse. init (PID 1) adoptiert alle verwaisten Prozesse.
So bleibt die Prozesshierarchie intakt.
So bleibt die Prozesshierarchie intakt.
Probeklausur Betriebssysteme 01.07.2019

1 – Prozesse und Scheduling
b) Prozesse
2) Was ist der copy-on-write-Mechanismus? Wo kommt er im Kontext von Prozessen zum Einsatz?
●
–
●
– –
●
–
–
–
Copy-on-write
Zwei (oder mehr) Entitäten arbeiten auf demselbem Datum Erst bei einem schreibendem Zugriff werden Kopien erstellt
Einsatz im Kontext von Prozessen
Verwendung bei fork()
Erlaubt schnelles Erzeugen von Prozessen
Beide (Vater- und Kindprozess) arbeiten zunächst auf demselben BSS-, Daten-, und Heap-Segment – bis einer der beiden etwas verändert.
Probeklausur Betriebssysteme 01.07.2019
7

1 – Prozesse und Scheduling
c) Scheduling
X X
X X
●
●
●
● ●
Im Gegensatz zu Round Robin wird bei Virtual Round Robin die restliche Zeitscheibe berücksichtigt. Die bekommt aber nicht der nächste Prozess, sondern der, der sie „übriggelassen“ hat.
SRTF: Wie bei Shortest Process Next (SPN) können CPU-lastige Prozesse verhungern.
Round Robin ignoriert die restliche Zeitscheibe bei E/A-lastigen Prozessen, die vorzeitig die CPU abgeben.
Präemption ist gerade der Mechanismus, der einem Prozess die CPU entzieht.
Bei einem Mix kommt es bei FCFS z.B. zum „Konvoi-Effekt“, hoher Antwortzeit, und niedrigem E/A-Durchsatz.
●
Probeklausur Betriebssysteme 01.07.2019
8

2 – Synchronisation und Verklemmung
a) Erzeuger-Verbraucher-Problem
Die Funktionen producer() und consumer() in folgendem Pseudocode- Abschnitt werden potentiell gleichzeitig ausgeführt, wobei producer() Elemente erzeugt und consumer() diese verbraucht. Synchronisieren Sie die beiden Funktionen mittels einseitiger Synchronisation und beachten Sie dabei, dass die Warteschlange zwar beliebig viele Elemente aufnehmen kann, die Operationen enqueue() und dequeue() aber selbst kritisch sind und nicht gleichzeitig ausgeführt werden dürfen. Der consumer() soll nur Elemente aus der Warteschlange entfernen, wenn diese nicht leer ist!
Legen Sie dazu geeignet benannte Semaphore an, initialisieren Sie diese, undsetzenSieandenfreienStellenSemaphor-Operationen(P,Vbzw. wait, signal) ein (z.B. P(MeinSemaphor)). (P(), V(), produce_element(), consume_element(), enqueue() und dequeue() können als gegeben angesehen werden und müssen nicht implementiert werden!)
●
Probeklausur Betriebssysteme 01.07.2019
9

Semaphore, die Anzahl der
Semaphore, die Anzahl der
Elemente zählt:
Elemente zählt:
zähler = 0
zähler = 0
2 – Synchronisation und Verklemmung
Namen und Initialwerte der Semaphore:
„Operationen enqueue() und dequeue() […] nicht gleichzeitig ausgeführt werden dürfen“
„consumer() soll nur Elemente aus der Warteschlange entfernen, wenn diese nicht leer ist“
●
producer() {
while (1) {
Element e = produce_element(); P(mutex)
enqueue(e);
V(mutex)
V(zähler)
}}
}}
10
Probeklausur Betriebssysteme 01.07.2019
consumer() {
while (1) {
gegenseitiger Ausschluss /
gegenseitiger Ausschluss /
P(zähler)
P(mutex)
Element e = dequeue(); V(mutex)
consume_element(e);
mutual exclusion:
mutual exclusion:
Semaphore mutex = 1 Semaphore mutex = 1
Signalisierung

2 – Synchronisation und Verklemmung
Namen und Initialwerte der Semaphore:
„Operationen enqueue() und dequeue() […] nicht gleichzeitig ausgeführt werden dürfen“
„consumer() soll nur Elemente aus der Warteschlange entfernen, wenn diese nicht leer ist“
●
producer() {
while (1) {
Element e = produce_element(); P(mutex)
enqueue(e);
V(zähler)
V(mutex)
}}
FALSCH!
FALSCH!
Deadlock möglich.
Deadlock möglich.
consumer() {
while (1) {
gegenseitiger Ausschluss /
gegenseitiger Ausschluss /
P(mutex)
P(zähler)
Element e = dequeue(); V(mutex) consume_element(e);
mutual exclusion:
mutual exclusion:
Semaphore mutex = 1 Semaphore mutex = 1
Semaphore, die Anzahl der
Semaphore, die Anzahl der
Elemente zählt:
Elemente zählt:
zähler = 0
zähler = 0
}}
11
Probeklausur Betriebssysteme 01.07.2019

2 – Synchronisation und Verklemmung
b) Erläutern Sie, was man unter sogenannten Race Conditions versteht und wie man diese verhindern kann.
Race Conditions entstehen, wenn mehrere Prozesse auf die selben Daten zugreifen und mindestens ein Prozess diese manipuliert.
●
–
Probeklausur Betriebssysteme 01.07.2019
12

2 – Synchronisation und Verklemmung
c) Nennen und erläutern Sie zwei Bedingungen, die notwendig sind, damit eine Verklemmung auftreten kann.
1) Exklusive Belegung von Betriebsmitteln („mutual exclusion“)
Die umstrittenen Betriebsmittel sind nur unteilbar nutzbar. 2) Nachforderung von Betriebsmitteln („hold and wait“)
Die umstrittenen Betriebsmittel sind nur schrittweise belegbar. 3) Kein Entzug von Betriebsmitteln („no preemption“)
Die umstrittenen Betriebsmittel sind nicht rückforderbar. 4) Zirkuläres Warten („circular wait“)
Es existiert eine geschlossene Kette wechselseitig wartender Prozesse.
●
●
●
●
●
Probeklausur Betriebssysteme 01.07.2019
13

2 – Synchronisation und Verklemmung
d) Nennen Sie eine Möglichkeit zur Verklemmungsvorbeugung (deadlock prevention)
indirekte Methoden entkräften eine der Bedingungen 1–3
nicht-blockierende Verfahren verwenden
Betriebsmittelanforderungen unteilbar (atomar) auslegen
Betriebsmittelentzug durch Virtualisierung ermöglichen – virtuellerSpeicher,virtuelleGeräte,virtuelleProzessoren
direkte Methoden entkräften Bedingung 4
lineare/totale Ordnung von Betriebsmittelklassen einführen:
– Betriebsmittel Bi ist nur dann erfolgreich vor Bj belegbar, wenn i linear vor j angeordnet ist (d.h. i < j). ● – ● – ● ● ● Probeklausur Betriebssysteme 01.07.2019 14 3 – Speicherverwaltung + virt. Speicher a) Adressabbildung ● Probeklausur Betriebssysteme 01.07.2019 15 Vorlesungsfolien: 08 - Speicherverwaltung Seitenadressierung (paging) Einteilung des logischen Adressraums in gleichgroße Seiten, die an beliebigen Stellen im physikalischen Adressraum liegen können Lösung des Fragmentierungsproblems keine Kompaktifizierung mehr nötig Vereinfacht Speicherbelegung und Ein-/Auslagerungen ● – – – logischer Adressraum physikalischer Adressraum ROM Seiten (pages) Kacheln (frames) RAM Probeklausur Betriebssysteme 01.07.2019 16 Vorlesungsfolien: 08 - Speicherverwaltung MMU mit Seiten-Kacheltabelle Tabelle setzt Seiten in Kacheln um SKT Basisregister + ● logische Adresse 00002 12a Seiten-Kacheltabelle Startadr. ffe0 fxxx ... 00000 00000 00001 00002 00003 00004 ffe0f 12a Probeklausur Betriebssysteme 01.07.2019 17 physikalische Adresse 3 – Speicherverwaltung + virt. Speicher ● a) Adressabbildung 4000 + AB1 4AB1 5000 + 1B7 51B7 Probeklausur Betriebssysteme 01.07.2019 18 3 – Speicherverwaltung + virt. Speicher b) LRU (Seitenersetzung) ● Referenzfolge 3 1 2 4 2 1 5 3 2 Kachel 1 3 Kachel 2 Kachel 3 Kontrollzustände Kachel 1 0 Kachel 2 Kachel 3 Probeklausur Betriebssysteme 01.07.2019 19 3 – Speicherverwaltung + virt. Speicher b) LRU (Seitenersetzung) ● Referenzfolge 3 1 2 4 2 1 5 3 2 Kachel 1 3 3 3 4 4 4 5 5 5 Kachel 2 1 1 1 1 1 1 1 2 Kachel 3 2 2 2 2 2 3 3 Kontrollzustände Kachel 1 0 1 2 0 1 2 0 1 2 Kachel 2 0 1 2 3 0 1 2 0 Kachel 3 0 1 0 1 2 0 1 Probeklausur Betriebssysteme 01.07.2019 20 4 - Ein-/Ausgabe und Dateisysteme Gegeben sei ein Plattenspeicher mit 16 Spuren. Der jeweilige I/O-Scheduler bekommt immer wieder Leseaufträge für eine bestimmte Spur. Die Leseaufträge in L1 sind dem I/O- Scheduler bereits bekannt. Nach einem bearbeiteten Auftrag erhält er die Aufträge in L2. Nach weiteren drei (d.h. nach insgesamt vier) bearbeiteten Aufträgen erhält er die Aufträge in L3. Zu Beginn befindet sich der Schreib-/Lesekopf über Spur 0. L1={4,7,11,3} L2={2,13,1} L3={15,5,6} ● Probeklausur Betriebssysteme 01.07.2019 21 4 - Ein-/Ausgabe und Dateisysteme L1={4,7,11,3} L2={2,13,1} L3={15,5,6} Sofort bekannt Nach 1 Ops Nach 4 Ops bekannt bekannt ● Bitte tragen Sie hier die Reihenfolge der gelesenen Spuren für einen I/O-Scheduler, der nach der First In First Out (FIFO)- Strategie arbeitet, ein: First In – First Out sagt aus „die Aufträge werden in der Reihenfolge abgearbeitet, in der sie hereinkommen“ → L1, L2, L3 einfach aneinanderhängen! 4 7 11 3 2 13 1 15 5 6 Probeklausur Betriebssysteme 01.07.2019 22 4 - Ein-/Ausgabe und Dateisysteme b) Nennen Sie je einen Vorteil und einen Nachteil der kontinuierlichen Datenspeicherung Vorteile: Zugriff auf alle Blöcke mit minimaler Positionierzeit des Schwenkarms Schneller direkter Zugriff auf bestimmter Dateiposition Einfach zu implementieren, daher Einsatz bei nicht-beschreibbaren Medien (CD, DVD, etc.) Finden des freien Platzes auf der Festplatte (Menge aufeinanderfolgender und freier Plattenblöcke) Fragmentierungsproblem (Verschnitt: nicht nutzbare Plattenblöcke; siehe auch Speicherverwaltung) ● – – ● ● ● ● Nachteile: ● ● ● ● Größe bei neuen Dateien oft nicht im Voraus bekannt Erweitern ist problematisch Umkopieren, falls kein freier angrenzender Block mehr verfügbar Probeklausur Betriebssysteme 01.07.2019 23 4 - Ein-/Ausgabe und Dateisysteme ● c) Indizierte Speicherung direkt 0 direkt 1 direkt 9 einfach indirekt zweifach indirekt dreifach indirekt Inode Datenblöcke Probeklausur Betriebssysteme 01.07.2019 24 ... 4 - Ein-/Ausgabe und Dateisysteme c) Indizierte Speicherung 1. Nennen Sie beispielhaft ein Dateisystem, bei dem Dateien in der dargestellten Weise abgelegt werden. UNIX-, und Linux-Dateisysteme, wie z.B. ext2, ext3, ext4 ● – Probeklausur Betriebssysteme 01.07.2019 25 4 - Ein-/Ausgabe und Dateisysteme c) Indizierte Speicherung 2. Ein hypothetisches Dateisystem verwendet Inodes wie oben dargestellt, nur ohne Dreifach-Indirektion. Wie lässt sich die maximale Dateigröße für dieses Dateisystem berechnen, wenn die Blockgröße 1024 Bytes beträgt und für die Speicherung eines Blockverweises 4 Bytes benötigt werden. Hinweis: Es ist nicht erforderlich die Zahl auszurechnen. Beschreiben Sie den Rechenweg Schritt für Schritt oder geben Sie eine Formel an. ● – Probeklausur Betriebssysteme 01.07.2019 26 4 - Ein-/Ausgabe und Dateisysteme B: Maximale Anzahl der Blöcke BG: Blockgröße D: Maximale Dateigröße (gesucht) I: Anzahl der Verweise in indirekten Blöcken I=BG/4=1024/4 ● ● ● ● Jeder Blockverweis ist 4 Byte groß Jeder Blockverweis ist 4 Byte groß Direkte Einfache Direkte Indirektion Verweise Indirektion Verweise Einfache Zweifache Indirektion Indirektion D=BG∗B=BG∗(10+I+I∗I) =1024 Bytes∗(10+256+256∗256) =67381248Bytes=65802KiBytes=ca.64,3MiB Probeklausur Betriebssysteme 01.07.2019 27 Zweifache 4 - Ein-/Ausgabe und Dateisysteme c) Indizierte Speicherung 3) Nennen Sie einen Vorteil und einen Nachteil der indizierten Speicherung im Vergleich zur kontinuierlichen Speicherung. ● – ● – – ● Vorteil: Auch große Dateien lassen sich so addressieren. Nachteil: Bei großen Dateien müssen mehrere Blöcke gelesen werden. Probeklausur Betriebssysteme 01.07.2019 28 Auswertung Bitte schnell einmal die Punkte zusammenzählen ... Notenspiegel: Punkte Note 38,5–45 1 33,5–38 2 28–33 3 22,5–27,5 4 0–22 5 ● ● Probeklausur Betriebssysteme 01.07.2019 29 Weitere Hinweise zur Vorbereitung Inhalt der Folien lernen Klassifizieren: Was muss ich lernen? Was muss ich begreifen? Übungsaufgaben verstehen, C und UNIX „können“ ● – ● ● ● ergänzend Literatur zur Lehrveranstaltung heranziehen Rechnerübung nutzen – ● – – Am besten die Aufgaben noch einmal lösen Optionale Zusatzaufgaben bearbeiten ASSESS-System bleibt mindestens bis zur zweiten Klausur offen bei Fragen zur Korrektur melden Probeklausur Betriebssysteme 01.07.2019 30 Empfohlene Literatur [1] A. Silberschatz et al. Operating System Concepts. Wiley, 2004. ISBN 978-0471694663 [2] A. Tanenbaum: Modern Operating Systems (2nd ed.). Prentice Hall, 2001. ISBN 0-13-031358-0 [3] B. W. Kernighan, D. M. Ritchie. The C Programming Language. Prentice-Hall, 1988. ISBN 0-13-110362-8 (paperback) 0-13-110370-9 (hardback) [4] R. Stevens, Advanced Programming in the UNIX Environment, Addison-Wesley, 2005. ISBN 978-0201433074 Viel Erfolg bei der Klausur! Probeklausur Betriebssysteme 01.07.2019 31