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 Sätze)
c)* Tragen Sie im Folgenden die richtigen Namen der Hypervisor ein und beschriften Sie deren Aufbau:
Name: Name:

Dateisystem:
Blockgröße:
Weitere Mechanismen:
Begründung: 1.
2. 3. 4. 5.
d)* Sie sollen ein Speichersystem für Videos (also große Dateien) aufsetzen. Es werden folgende Anforderungen an das System gestellt:
1. Speichern sehr großer Datenmengen
2. Hohe Performanz
3. Absichern gegen Ausfall einer Festplatte (Gesamtanzahl der Festplatten beliebig) 4. Verhindern inkonsistenter Zustände, z.B. bei Stromausfällen
5. Open-Source-Dateisystem
Wählen Sie ein Dateisystem und, falls nötig, darüber hinausgehende Mechanismen, um die Anforderungen zu er- füllen. Beschreiben Sie wie jede der Anforderungen durch Ihre Konfiguration erfüllt wird (1 Satz pro Anforderung), gehen Sie darüberhinaus auf die Bedeutung und Wahl der Blockgröße für 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 ausgeführt 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 dafür 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 können Informationen über die CPU sowie die physische und virtuelle Adresslänge 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 0–11 werden für den Offset innerhalb einer Page verwendet.
Die Bits 12–47 werden für vierstufiges Paging verwendet.
Die restlichen Bits 48–63 werden nicht verwendet und werden deswegen im Folgenden ignoriert.
Bei einer physischen Adresse werden alle Bits, welche nicht für den Frame-Offset verwendet werden, für die Frame-Nummer verwendet.
Es gilt: Frame-Size = Page-Size.
a)* Wie viele Bits der physischen Adresse werden für 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 für 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 für die folgenden Teilaufgaben.
e) Übersetzen 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 hierfür wie folgt vor:
1. Übersetzen Sie p0 in binäre Notation.
2. Übersetzen 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 Binärdarstellung deutlich mit einem senkrechten Strich.
Zweiter Vordruck. Streichen Sie deutlich durch, was nicht gewertet werden soll.

f) Übersetzen Sie die folgende virtuelle Adresse v1 in eine physische Adresse p1. v1 = 0x2A70000FAAA
Gehen Sie hierfür wie folgt vor:
1. Übersetzen Sie v1 in binäre Notation.
2. Übersetzen 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 Binärdarstellung 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 höchste 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 Blockgröße von 4096 Bytes (4 KiB) und einer Gesamtspeichergröße von 6553 Bytes (64 KiB) aus.
1 2 3 4 5 6 7 8
Zeichnen Sie die gesamte Belegung des Speichers nach der Ausführung jedes Statements aus dem obige Pseudocode auf. Kennzeichnen Sie belegte Blöcke mit dem Buchstaben der Belegung, lassen Sie unbelegt Blöcke frei. Trennen Sie Blöcke 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. Gäste betreten das Gebäude 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 Gäste das Gebäude entweder über die Treppe und den Haupteingang, oder alternativ einen Hinterausgang, der die Treppe umgeht.
Folgendes Petrinetz modelliert das gegebene Szenario:
auf Treppe aufwärts
Ausgabeb. betreten
im Ausgabebereich
Ausgabebere verlassen
Gebäude betreten
vor Mensa
im Essbereic
Gebäude verlassen
auf Treppe abwärts
Essbereich verlassen
Gebäude durch Hinterausgang verlassen
Gegeben sei zudem Folgendes:
• Es dürfen maximal 1500 Personen im Gebäude sein.
• Der Ausgabebereich fasst maximal 100 Personen.
• Die Kapazität der Treppe ist abhängig 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 Kapazität nicht überschreiten, sind möglich (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 Kapazitätsbegrenzungen der Stellen!
a)* Verhindern Sie durch Einführen einer Zählstelle, dass sich zu viele Personen im gesamten Gebäude aufhalten. Ist die Kapazität des Gebäudes erreicht, so müssen Gäste vor dem Gebäude warten.
b)* Verhindern Sie, dass zu viele Gäste im Ausgabebereich sind. Ist dieser voll, so müssen Gäste auf der Treppe warten.

c)* Setzen Sie die Kapazität der Treppe um. Ist die Treppe voll, so müssen eingehende Gäste vor dem Gebäude warten, ausgehende Gäste können das Gebäude nur über 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 für Nudelgerichte ist für uns von besonderem Interesse. Gerichte sind unterteilt in Nudeln und Sauce, beide werden getrennt ausgegeben. Gäste nehmen sich immer Nudeln und Sauce. Der Aufbau sieht wie folgt aus:
—————
|Nudeln| Sauce|
—————
Gäste–> <--Gäste Um den Durchsatz zu erhöhen, beschließt der Betreiber, das Anstehen von beiden Seiten zu ermöglichen. Zwei Gäste (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 nächste Gast rutscht nach. Gäste können sich auch Sauce nehmen, wenn sie vor den Nudeln stehen, und umgekehrt. Sie müssen hierfür also nicht Platz tauschen. Für Sauce und Nudeln gibt es je einen Löffel für die Entnahme. Ein Gast gibt einen Löffel erst frei, wenn er den jeweils anderen Löffel allokieren kann. Sobald ein Gast den zweiten Löffel allokiert hat, gibt er den vorherigen frei. Leider präferieren einige Gäste, die Sauce vor den Nudeln in die Schale zu schöpfen. d)* Beschreiben Sie, wie es zu einem Deadlock kommen kann. e) Der Folgende Pseudocode beschreibt einen Fall des Szenarios. Die Abläufe GastVonLinks und GastVonRechts laufen echt parallel. Fügen Sie Maßnahmen 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 außer Kraft setzen können, um Deadlocks von vornherein zu verhindern. Nennen Sie die Bedingung, die Sie außer Kraft setzen, explizit. g)* Gegeben sei folgender Erreichbarkeitsgraph. Eine Belegung beschreibt jeweils die Stellen (s1, s2, s3). t3 1,0,1 t1 0,1,0 t2 0,0,0 Skizzieren Sie ein zu dem Erreichbarkeitsgraphen zugehöriges Petrinetz mit der Anfangsbelegung (1,0,1). Beschrif- ten Sie alle Stellen und Transitionen. h)* Skizzieren Sie ein Petrinetz, welches beide der folgenden Eigenschaften erfüllt: • Deadlockfrei • Nicht lebendig Sie müssen die Eigenschaften nicht beweisen. Aufgabe4 Scheduling(20Punkte) a)* Die Programmiersprache Go bietet zur Realisierung von Nebenläufigkeit das Konzept der sogenannten Goroutinen. Hierbei handelt es sich um eine besonders leichtgewichtige Variante von User-Level-Threads. Die Verwaltung dieser Goroutinen übernimmt 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 Prioritäten (höher ist besser) der Goroutinen sind dynamisch: • Bei Vollendung einer Zeiteinheit Rechenzeit wird die Priorität um 1 verringert. • Bei Vollendung dreier zusammenhängender Zeiteinheiten Wartezeit wird die Priorität um 2 erhöht. Da die Prioritäten von der Laufzeitumgebung selbst verwaltet werden, zählen 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 hierfür sei vernachlässigbar klein (0 Zeiteinheiten). Der Kernelscheduler des Betriebssystems arbeitet nach der präemptiven 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 eingefügt. Das Kernel-Level-Scheduling benötige stets eine Zeiteinheit, ein Kontextwechsel dauere eine weitere Zeiteinheit. Für 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: Thread Ankunftszeit Benötigte Rechenzeit Startpriorität PA,U1 3 5 4 PA,U2 3 2 2 PA,U3 5 3 3 PB,K1 0 4 PC,K1 9 4 PC,K2 14 2 Vernachlässigen Sie den initialen Kontextwechsel, sprich der erste Prozess beginne zum Zeitpunkt 0 direkt mit der Ausführung. Markieren Sie Wartezeiten mit einem - und Rechenzeiten mit einem x. Sie können sich die Prioritäten in den Freizeilen notieren, dies wird jedoch nicht bewertet. Es zählen ausschließlich die markierten Warte- und Rechenzeiten! Nutzen Sie den zweiten Vordruck, falls Sie Fehler im ersten Vordruck korrigieren möchten. Streichen Sie deutlich durch, was nicht gewertet werden soll (sonst keine Wertung möglich)! 0 5 10 15 20 25 30 35 PA,U1 PA,U2 PA,U3 PB,K1 PC,K1 PC,K2 S./D. 0 5 10 15 20 25 30 35 PA,U1 PA,U2 PA,U3 PB,K1 PC,K1 PC,K2 S./D. b)* Nennen Sie drei wesentlich unterschiedliche Attribute, die im Prozesskontext gespeichert werden. c)* Für welche Art von Systemen wird die Rate-Monotonic Scheduling Strategie verwendet? Beschreiben Sie außerdem die Idee und Besonderheit dieser Strategie. d)* Nennen Sie drei Optimierungsziele von Schedulingstrategien. Die Strategien selbst müssen nicht genannt werden. Aufgabe5 MultipleChoice(9Punkte) Kreuzen Sie richtige Antworten an × Kreuze können durch vollständiges Ausfüllen gestrichen werden ⌅ Gestrichene Antworten können durch nebenstehende Markierung erneut angekreuzt werden ×⌅ Es müssen alle Antworten pro Teilaufgabe korrekt angekreuzt sein. Es ist mindestens eine Antwort korrekt. a) Ein Semaphor besitzt folgende Objekte: Maximalwert Warteschlange Zählvariable Minimalwert b) Kleines Kopfrechnen mit Binär- und Dezimalpräfixen. 8193 MiB sind 8 GiB 1 KiB sind 1000 Byte 10 MB sind 0,0001 TB 1024 GiB sind 1 TiB c) Ein Prozess im Zustand rechnend kann in welche anderen Prozesszustände überführt werden? Rechenwillig Verklemmt Wartend Beendet d) Was gilt unter Linux als eine Datei? Socket Drucker Textdatei Binärdatei Named Pipe Verzeichnis e) 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 lösen? 4 1 3 2 f) Welche Ressourcen teilen sich i.d.R. die einzelnen Threads eines Prozesses? Eingehende Signale Den Program Counter Offene Filedeskriptoren Das Codesegment Das Datensegment Den Inhalt der Register Den Stack Den Heap Den Adressraum g) Kleines Kopfrechnen mit verschiedenen Zahlenbasen. 0b10001 = 0x11 26 = 0b1000000 68 = 0x44 0x00100 = 160 h) 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 Prozessadressräumen. kann maximal so groß sein wie der verfügbare Arbeitsspeicher. i) Der Bankiersalgorithmus... benötigt Information über die Betriebsmittelanforderungen vor Prozessbeginn. setzt eine der Deadlockbedingungen außer Kraft. ist eine Methode zur Deadlock-Vermeidung (Deadlock Avoidance). verbietet Ressourcenbelegungen, die zu Deadlocks führen können.

Related Posts