[SOLVED] CS algorithm ER Aufgabe1 GenerischeFragen(20Punkte)

Aufgabe1 GenerischeFragen(20Punkte)
a)* Ein Betriebssystem unterscheidet (mindestens) zwei Betriebsmodi. Welche sind dies? Nennen Sie zwei
Unterschiede?
Modi:
1. 2.
Unterschiede:
b)* Was ist ein Livelock? (max. 3 Satze)
c)* Tragen Sie im Folgenden die richtigen Namen der Hypervisor ein und beschriften Sie deren Aufbau:
Name: Name:

Dateisystem:
Blockgroe:
Weitere Mechanismen:
Begrundung: 1.
2. 3. 4. 5.
d)* Sie sollen ein Speichersystem fur Videos (also groe Dateien) aufsetzen. Es werden folgende Anforderungen an das System gestellt:
1. Speichern sehr groer Datenmengen
2. Hohe Performanz
3. Absichern gegen Ausfall einer Festplatte (Gesamtanzahl der Festplatten beliebig) 4. Verhindern inkonsistenter Zustande, z.B. bei Stromausfallen
5. Open-Source-Dateisystem
Wahlen Sie ein Dateisystem und, falls notig, daruber hinausgehende Mechanismen, um die Anforderungen zu er- fullen. Beschreiben Sie wie jede der Anforderungen durch Ihre Konfiguration erfullt wird (1 Satz pro Anforderung), gehen Sie daruberhinaus auf die Bedeutung und Wahl der Blockgroe fur die angegebene Situation ein.

e)* Wie lange kann ein auf dem Stack allozierter Speicher sicher genutzt werden?
Im Folgenden sehen Sie ein Programmkonstrukt, das ein Passwort einlesen soll.
1 #include
2 #include
3
4 int main(void) {
5 char *password = calloc(1024, 1);
6 scanf(%1023s, password);
7 // password wird lesend ausgewertet
8 free(password);
9}
f)* Beschreiben Sie ein Problem, welches sich durch obige Konstruktion bei Abfrage von sensiblen Daten ergeben kann. Das Programm soll auf einem Unix-System mit mehreren Nutzern ausgefuhrt werden.
g) Was sollte man dagegen unternehmen? (Kein Code erforderlich.)
h)* Deklarieren Sie in C folgendes Konstrukt: Ein 11-stelliges Array von Pointern auf Arrays die wiederum auf Arrays zeigen, welche void-Pointer beinhalten. Der Bezeichner dafur ist triple_pagetable.

Aufgabe2 Speicherverwaltung(21Punkte)
Um unter Linux die Page-Size in Bytes zu erhalten, kann das Kommando getconf PAGE_SIZE genutzt werden. Mittels cat /proc/cpuinfo konnen Informationen uber die CPU sowie die physische und virtuelle Adresslange ausgelesen werden.
Beispiel:
$ getconf PAGE_SIZE 4096
$ cat / proc / cpuinfo
[]
model name : Intel (R) Core(TM) i7=8650U CPU @ 1.90GHz
[]
address sizes : 39 bits physical , 48 bits virtual
[]
Auf Linux-x86-64 ist eine virtuelle Adresse wie folgt aufgebaut:
63 48 47 39 38
9 Bit
30 29
21 20 12 11
9 Bit
0
9 Bit
9 Bit
12 Bit
Abbildung 2.1: Aufbau einer virtuellen Adresse auf Linux-x86-64
Die Bits 011 werden fur den Offset innerhalb einer Page verwendet.
Die Bits 1247 werden fur vierstufiges Paging verwendet.
Die restlichen Bits 4863 werden nicht verwendet und werden deswegen im Folgenden ignoriert.
Bei einer physischen Adresse werden alle Bits, welche nicht fur den Frame-Offset verwendet werden, fur die Frame-Nummer verwendet.
Es gilt: Frame-Size = Page-Size.
a)* Wie viele Bits der physischen Adresse werden fur den Frame-Offset verwendet?
Unused
Page-
Table Level 1
Page-
Table Level 2
Page-
Table Level 3
Page-
Table Level 4
Page-Oset
b) Wie viele Bits der physischen Adresse werden fur die Frame-Nummer verwendet?
c) In wie viele Frames wird der physische Speicher eingeteilt?
d) Wie viele Pages kann Linux mit diesem Verfahren adressieren?

0x1FF
0xFFF
0x42
0x0
p0 = 0x 42D9B
p0 = 0b ________ ________ ________ ________ ________
v0 = 0b ________ ________ ________ ________ ________ ________ v0 = 0x
p0 = 0x 42D9B
p0 = 0b ________ ________ ________ ________ ________
v0 = 0b ________ ________ ________ ________ ________ ________ v0 = 0x
0x000
0x001
0x002
0x003
0x004
0x005
0x006
0x007
0x008
0x009
0x00A
0x00B
0x00C
0x00D 0x011
0x00E 0x012
0x00F 0x013
0x010 0x014
0x099 0x005 0x1FC
0x09A 0x006 0x1FD
0x09B 0x007 0x1FE
0x09C 0x008 0x1FF
0x000 0x00C
0x001 0x00D
0x002 0x00E
0x003 0x00F
0x005 0x000
0x006 0x001
0x007 0x002
0x008 0x003
Abbildung 2.2: Vierstufige Page-Table
Abbildung 2.2 zeigt nun eine Momentaufnahme der Page-Table eines Prozesses. Nutzen Sie diese Momentaufnah- me fur die folgenden Teilaufgaben.
e) Ubersetzen Sie die folgende physische Adresse p0 in eine virtuelle Adresse v0 und geben Sie diese in hexadezi- maler Notation an.
p0 = 0x 42D9B
Gehen Sie hierfur wie folgt vor:
1. Ubersetzen Sie p0 in binare Notation.
2. Ubersetzen Sie p0 mittels Abbildung 2.2 in eine virtuelle Adresse. 3. Geben Sie v0 in hexadezimaler Notation an.
Trennen Sie die einzelnen Teile der virtuellen und physischen Adresse in ihrer Binardarstellung deutlich mit einem senkrechten Strich.
Zweiter Vordruck. Streichen Sie deutlich durch, was nicht gewertet werden soll.

f) Ubersetzen Sie die folgende virtuelle Adresse v1 in eine physische Adresse p1. v1 = 0x2A70000FAAA
Gehen Sie hierfur wie folgt vor:
1. Ubersetzen Sie v1 in binare Notation.
2. Ubersetzen Sie v1 mittels Abbildung 2.2 in eine physische Adresse.
3. Geben Sie p1 an. Falls ein Pagefault auftritt, schreiben Sie Pagefault statt der physischen Adresse und umkreisen Sie in Abbildung 2.2 den problematischen Bereich.
Trennen Sie die einzelnen Teile der virtuellen und physischen Adresse in ihrer Binardarstellung deutlich mit einem senkrechten Strich.
v1 = 0x 2A70000FAAA
v1 = 0b ________ ________ ________ ________ ________ ________ p1 =
Zweiter Vordruck. Streichen Sie deutlich durch, was nicht gewertet werden soll.
v1 = 0x 2A70000FAAA
v1 = 0b ________ ________ ________ ________ ________ ________ p1 =
g) Gegeben sei die physische Adresse p = 0x D19B.
Wie lautet die hochste physische Adresse des Frames, auf das p zeigt, in Hexadezimaldarstellung?

h) Gegeben sei der Buddy-Allocator-Algorithmus gema Vorlesung, sowie der Pseudocode des folgenden Pr gramms. Gehen Sie von einer Blockgroe von 4096 Bytes (4 KiB) und einer Gesamtspeichergroe von 6553 Bytes (64 KiB) aus.
1 2 3 4 5 6 7 8
Zeichnen Sie die gesamte Belegung des Speichers nach der Ausfuhrung jedes Statements aus dem obige Pseudocode auf. Kennzeichnen Sie belegte Blocke mit dem Buchstaben der Belegung, lassen Sie unbelegt Blocke frei. Trennen Sie Blocke mittels senkrechter Striche.
Geben Sie bei jeder von ihnen verwendeten Vorlage an, welche Zeile des Pseudocodes sie abbildet.
Zeilennummer:
0123456789101112131415 4K4K4K4K4K 4K4K4K4K4K4K4K4K4K4K4K
Zeilennummer:
0123456789101112131415 4K4K4K4K4K 4K4K4K4K4K4K4K4K4K4K4K
Zeilennummer:
0123456789101112131415 4K4K4K4K4K 4K4K4K4K4K4K4K4K4K4K4K
Zeilennummer:
0123456789101112131415 4K4K4K4K4K 4K4K4K4K4K4K4K4K4K4K4K
Zeilennummer:
0123456789101112131415 4K4K4K4K4K 4K4K4K4K4K4K4K4K4K4K4K
Zeilennummer:
0123456789101112131415 4K4K4K4K4K 4K4K4K4K4K4K4K4K4K4K4K
Zeilennummer:
0123456789101112131415 4K4K4K4K4K 4K4K4K4K4K4K4K4K4K4K4K
Zeilennummer:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 4K4K4K4K4K 4K4K4K4K4K4K4K4K4K4K4K
Zeilennummer:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 4K4K4K4K4K 4K4K4K4K4K4K4K4K4K4K4K
Zeilennummer:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 4K4K4K4K4K 4K4K4K4K4K4K4K4K4K4K4K
Zeilennummer:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 4K4K4K4K4K 4K4K4K4K4K4K4K4K4K4K4K
Zeilennummer:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 4K4K4K4K4K 4K4K4K4K4K4K4K4K4K4K4K
Zeilennummer:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 4K4K4K4K4K 4K4K4K4K4K4K4K4K4K4K4K
Zeilennummer:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 4K4K4K4K4K 4K4K4K4K4K4K4K4K4K4K4K
A = allocate (12123); B = allocate (14242); C = allocate (8193);
free (B);
D = allocate (42);
free (C); free (A); free (D);

Aufgabe3 Synchronisierung(20Punkte)
Im Folgenden betrachten wir eine vereinfachte Version einer Mensa. Gaste betreten das Gebaude durch den Haupteingang, gehen eine Treppe hinauf und begeben sich in den Ausgabebereich. Von dort bewegen sie sich in den Essbereich. Nach dem Verzehr der Mahlzeit verlassen Gaste das Gebaude entweder uber die Treppe und den Haupteingang, oder alternativ einen Hinterausgang, der die Treppe umgeht.
Folgendes Petrinetz modelliert das gegebene Szenario:
auf Treppe aufwarts
Ausgabeb. betreten
im Ausgabebereich
Ausgabebere verlassen
Gebaude betreten
vor Mensa
im Essbereic
Gebaude verlassen
auf Treppe abwarts
Essbereich verlassen
Gebaude durch Hinterausgang verlassen
Gegeben sei zudem Folgendes:
Es durfen maximal 1500 Personen im Gebaude sein.
Der Ausgabebereich fasst maximal 100 Personen.
Die Kapazitat der Treppe ist abhangig von der Gangrichtung. Beim Heruntergehen (Richtung Ausgang) braucht eine Person doppelt so viel Platz, wie wenn sie die Treppe hinaufgeht.
Die Treppe fasst maximal 50 heraufgehende Personen.
Die Treppe fasst demnach maximal 25 herabgehende Personen.
Alle Kombinationen, die die Kapazitat nicht uberschreiten, sind moglich (z.B. 24 herab, 2 herauf).
Bearbeiten Sie Teilaufgabe a), b) und c) durch Erweiterung des obigen Netzes. Verwenden Sie in Teilauf- gabe a), b) und c) keine Kapazitatsbegrenzungen der Stellen!
a)* Verhindern Sie durch Einfuhren einer Zahlstelle, dass sich zu viele Personen im gesamten Gebaude aufhalten. Ist die Kapazitat des Gebaudes erreicht, so mussen Gaste vor dem Gebaude warten.
b)* Verhindern Sie, dass zu viele Gaste im Ausgabebereich sind. Ist dieser voll, so mussen Gaste auf der Treppe warten.

c)* Setzen Sie die Kapazitat der Treppe um. Ist die Treppe voll, so mussen eingehende Gaste vor dem Gebaude warten, ausgehende Gaste konnen das Gebaude nur uber den Hinterausgang verlassen.

// Globale Deklarationen
// Programmablauf
GastVonLinks{








GastVonRechts{

}}







In unserem vereinfachten Mensamodell stellt der Ausgabebereich (Selbstbedienung) ein Bottleneck dar. Wir wollen eine der Ausgaben im Detail betrachten. Die Ausgabe fur Nudelgerichte ist fur uns von besonderem Interesse. Gerichte sind unterteilt in Nudeln und Sauce, beide werden getrennt ausgegeben. Gaste nehmen sich immer Nudeln und Sauce. Der Aufbau sieht wie folgt aus:

|Nudeln| Sauce|

Gaste> <–GasteUm den Durchsatz zu erhohen, beschliet der Betreiber, das Anstehen von beiden Seiten zu ermoglichen. Zwei Gaste (je einer von links und rechts) platzieren ihr Tablett vor Nudeln oder Sauce und nehmen sich nacheinander beides. Nachdem sie sich Nudeln und Sauce genommen haben, verlassen sie die Ausgabe nach hinten, der nachste Gast rutscht nach. Gaste konnen sich auch Sauce nehmen, wenn sie vor den Nudeln stehen, und umgekehrt. Sie mussen hierfur also nicht Platz tauschen.Fur Sauce und Nudeln gibt es je einen Loffel fur die Entnahme. Ein Gast gibt einen Loffel erst frei, wenn er den jeweils anderen Loffel allokieren kann. Sobald ein Gast den zweiten Loffel allokiert hat, gibt er den vorherigen frei.Leider praferieren einige Gaste, die Sauce vor den Nudeln in die Schale zu schopfen. d)* Beschreiben Sie, wie es zu einem Deadlock kommen kann.e) Der Folgende Pseudocode beschreibt einen Fall des Szenarios. Die Ablaufe GastVonLinks undGastVonRechts laufen echt parallel. Fugen Sie Manahmen zur Synchronisierung (Mutexes, Semaphoren) ein, um Deadlocks zu verhindern. Die Parallelisierung muss nicht erhalten bleiben.f) Beschreiben Sie, wie Sie im obigen Szenario eine der vier Deadlockbedingungen auer Kraft setzen konnen, um Deadlocks von vornherein zu verhindern. Nennen Sie die Bedingung, die Sie auer Kraft setzen, explizit.g)* Gegeben sei folgender Erreichbarkeitsgraph. Eine Belegung beschreibt jeweils die Stellen (s1, s2, s3).t31,0,1 t1 0,1,0 t2 0,0,0Skizzieren Sie ein zu dem Erreichbarkeitsgraphen zugehoriges Petrinetz mit der Anfangsbelegung (1,0,1). Beschrif- ten Sie alle Stellen und Transitionen. h)* Skizzieren Sie ein Petrinetz, welches beide der folgenden Eigenschaften erfullt: Deadlockfrei Nicht lebendigSie mussen die Eigenschaften nicht beweisen.Aufgabe4 Scheduling(20Punkte)a)* Die Programmiersprache Go bietet zur Realisierung von Nebenlaufigkeit das Konzept der sogenannten Goroutinen. Hierbei handelt es sich um eine besonders leichtgewichtige Variante von User-Level-Threads. Die Verwaltung dieser Goroutinen ubernimmt die Laufzeitumgebung, die jedes kompilierte Go-Programm mitbringt.Der Prozess PA bestehe aus den drei Goroutinen U1, U2 und U3, die mittels Priority-Scheduling auf einen Kernel- Level-Thread abgebildet werden. Die Prioritaten (hoher ist besser) der Goroutinen sind dynamisch: Bei Vollendung einer Zeiteinheit Rechenzeit wird die Prioritat um 1 verringert. Bei Vollendung dreier zusammenhangender Zeiteinheiten Wartezeit wird die Prioritat um 2 erhoht.Da die Prioritaten von der Laufzeitumgebung selbst verwaltet werden, zahlen hierbei nur die Zeiteinheiten als War- tezeit, in denen die CPU dem Programm PA zugewiesen war. Der User-Level-Scheduler wird zu jedem Zeitschritt aktiv, der Aufwand hierfur sei vernachlassigbar klein (0 Zeiteinheiten).Der Kernelscheduler des Betriebssystems arbeitet nach der praemptiven Round-Robin-Strategie mit einem Zeitquantum von drei Zeiteinheiten. Stehen hierbei mehrere Prozesse zur Auswahl, so wird die CPU dem Prozess mit der kleineren ID zugewiesen. Neu eintreffende Kernel-Level-Threads bekommen die CPU sofort und werden an dieser Position in die Reihenfolge eingefugt. Das Kernel-Level-Scheduling benotige stets eine Zeiteinheit, ein Kontextwechsel dauere eine weitere Zeiteinheit.Fur die drei Prozesse PA (mit seinen Goroutinen U{1,2,3}), PB (mit seinem Kernel-Level-Thread K1) und PC (mit seinen Kernel-Level-Threads K{1,2}) gelten folgende Werte: ThreadAnkunftszeit Benotigte RechenzeitStartprioritatPA,U13 54PA,U23 22PA,U35 33PB,K10 4PC,K19 4PC,K214 2 Vernachlassigen Sie den initialen Kontextwechsel, sprich der erste Prozess beginne zum Zeitpunkt 0 direkt mit der Ausfuhrung.Markieren Sie Wartezeiten mit einem – und Rechenzeiten mit einem x.Sie konnen sich die Prioritaten in den Freizeilen notieren, dies wird jedoch nicht bewertet.Es zahlen ausschlielich die markierten Warte- und Rechenzeiten! Nutzen Sie den zweiten Vordruck, falls Sie Fehler im ersten Vordruck korrigieren mochten. Streichen Sie deutlich durch, was nicht gewertet werden soll (sonst keine Wertung moglich)!0 5 10 15 20 25 30 35 PA,U1PA,U2 PA,U3PB,K1 PC,K1 PC,K2 S./D.0 5 10 15 20 25 30 35PA,U1 PA,U2 PA,U3PB,K1 PC,K1 PC,K2 S./D.b)* Nennen Sie drei wesentlich unterschiedliche Attribute, die im Prozesskontext gespeichert werden.c)* Fur welche Art von Systemen wird die Rate-Monotonic Scheduling Strategie verwendet? Beschreiben Sie auerdem die Idee und Besonderheit dieser Strategie.d)* Nennen Sie drei Optimierungsziele von Schedulingstrategien. Die Strategien selbst mussen nicht genannt werden.Aufgabe5 MultipleChoice(9Punkte)Kreuzen Sie richtige Antworten an Kreuze konnen durch vollstandiges Ausfullen gestrichen werden Gestrichene Antworten konnen durch nebenstehende Markierung erneut angekreuzt werden Es mussen alle Antworten pro Teilaufgabe korrekt angekreuzt sein. Es ist mindestens eine Antwort korrekt.a) Ein Semaphor besitzt folgende Objekte: MaximalwertWarteschlange Zahlvariable Minimalwertb) Kleines Kopfrechnen mit Binar- und Dezimalprafixen. 8193 MiB sind 8 GiB1 KiB sind 1000 Byte 10 MB sind 0,0001 TB 1024 GiB sind 1 TiBc) Ein Prozess im Zustand rechnend kann in welche anderen Prozesszustande uberfuhrt werden? RechenwilligVerklemmt Wartend Beendetd) Was gilt unter Linux als eine Datei? SocketDrucker Textdatei Binardatei Named Pipe Verzeichnise) In der Vorlesung haben Sie das sogenannte Producer-Consumer-Problem kennengelernt. Wie viele Sema- phore brauchen Sie mindestens, um das Producer-Consumer-Problem ohne Deadlocks zu losen?4 1 3 2 f) Welche Ressourcen teilen sich i.d.R. die einzelnen Threads eines Prozesses? Eingehende SignaleDen Program Counter Offene Filedeskriptoren Das CodesegmentDas Datensegment Den Inhalt der Register Den StackDen HeapDen Adressraumg) Kleines Kopfrechnen mit verschiedenen Zahlenbasen. 0b10001 = 0x1126 = 0b1000000 68 = 0x44 0x00100 = 160h) Ein Prozessadressraum in einem mit Paging verwalteten Speichersystem… dient unter anderem dem Schutz unterschiedlicher Prozesse voreinander.wird in Seiten eingeteilt.ist immer disjunkt von allen anderen Prozessadressraumen. kann maximal so gro sein wie der verfugbare Arbeitsspeicher.i) Der Bankiersalgorithmus…benotigt Information uber die Betriebsmittelanforderungen vor Prozessbeginn. setzt eine der Deadlockbedingungen auer Kraft.ist eine Methode zur Deadlock-Vermeidung (Deadlock Avoidance).verbietet Ressourcenbelegungen, die zu Deadlocks fuhren konnen.