Lösungsvorschlag Betriebssysteme Midterm 2006

Aus VISki
Wechseln zu: Navigation, Suche

Aufgabe 1

  • MBR (inkl. Partit.table mit Windows = aktive Parition) auf roten USB Stick kopieren
  • MBR (inkl. Partit.table mit Linux = aktive Parition) auf blauen USB Stick kopieren
  • im BIOS USB-Boot in Boot-Präferenzen als first-choice

Bem: nicht sehr dynamisch aber einfach; besser, aber komplizierter: Code schreiben, der in der Tabelle den Ort des jeweiligen PBR nachschaut und diesen lädt.

Aufgabe 2

  • 1. FAT in den Hauptspeicher laden
  • 2. Wurzelverzeichnis in den Hauptspeicher laden
  • 3. Jede Datei besuchen (durch die Verzeichnisstruktur gehen), dabei jedes mal den Referenzen in der FAT folgen und für jeden benützten Block in der Bitmap das zugehörige Bit setzen.

Alternative: Oben genannte Strategie funktioniert auf jeden Fall, jedoch sind die freien Blöcke laut Folie 87 verkettet, so dass es reichen würde, dieser linearen Liste zu folgen.

Aufgabe 3

  • "Erweitern" der FAT-Einträge mit einem Wert für die Anzahl Schreibvorgänge auf dem entsprechenden Block.
  • Beim Schreiben neuer Daten wird nun die Anzahl Schreibvorgänge des ersten freien Blocks als "Defaultwert" angenommen. Die Daten werden in den nächsten freien Cluster geschrieben, welcher keine grössere "Anzahl Schreibvorgänge" hat als der Defaultwert.
    • Sind nur grössere Werte vorhanden, wird der Block mit dem Defaultwert überschrieben.

Bem: intelligentere Vorschläge???

Evtl. sowas wie ne next-fit policy? Man weiss immer wo das letzte Mal eingefügt wurde (Zeiger) und man beginnt von dort an das nächste File einzufügen?

Aufgabe 4

  • Stale: Power Failure wärend einem File-Update
  • Inkonsistent: Beispielsweise falsche Grösseninformation im iNode => Power Failure zwischen Grösseninformationsupdate und eigentlicehr Vergrösserung/Verkleinerung des Files.
  • Ganzes FS inkonsistent: Im Superblock steht beispielsweise die Anzahl vorhandener iNodes. Beispielsweise also Power Failure zwischen Anlaegen eines neuen iNodes und Update der Metadaten im Superblock.

Aufgabe 5

a) wie: mit interrupts, unter kontrolle des gerätetreibers für die maus

b) alle anwendungen die benachrichtigt werden wollen haben sich beim interrupt-handler (?) (wahrscheinlich registriert man sich beim gerätetreiber, der dann intterupts/signale broadcastet) registriert, welcher diese dann jeweils per "broadcast" informiert (interrupted)

Aufgabe 6

Voraussetzung: Es treffen keine weiteren Aufträge ein, bis alle abgearbeitet sind.

Die rote Linie beschreibt die Position des Armes / der Köpfe.

Möglichkeit 1: Der Arm bewegt sich zur Zeit von aussen nach innen, d.h. von den Zylindern mit hoher Nummer zu den Zylindern mit tiefer Nummer.

elevator_down.png

Timeline:
1 - 4. Eintreffen der Aufträge für Zylinder 99, 120 (2×), 105 (Reihenfolge egal). Merke: Auftrag 105 trifft ein, nachdem sich der Arm über Zylinder 105 bewegt hat.
5. Zugriff auf Zylinder 103 (vorgegeben).
6. Schreiben in Zylinder 99.
7. Schreiben in Zylinder 105.
8 - 9. Lesen von Zylinder 120 (Sektoren 1 und 5).


Möglichkeit 2: Der Arm bewegt sich zur Zeit von innen nach aussen, d.h. von den Zylindern mit tiefer Nummer zu den Zylindern mit hoher Nummer.

elevator_up.png

Timeline:
1. Eintreffen der Aufträge für Zylinder 99, 120 (2×), 105 (Reihenfolge egal). Hier trifft Auftrag 99 ein, nachdem sich der Arm über den entsprechenden Zylinder bewegt hat.
2. Zugriff auf Zylinder 103 (vorgegeben).
3. Schreiben in Zylinder 105.
4 - 5. Lesen von Zylinder 120 (Sektoren 1 und 5).
6. Schreiben in Zylinder 99.

Aufgabe 7

Die Zwischenwerte werden nur vorübergehend und nur innerhalb der Berechnung benötigt. Daher ist nur die Allokation auf dem Stack sinnvoll.

Aufgabe 8

Kommt auf den verwendeten Garbage Collector an, bei einem GC mit Reference Counting wird eine solche Struktur tatsächlich nie abgeräumt, bei einem (vom root set aus) traversierenden GC (Mark & Sweep o.ä.) wird die Struktur abgeräumt, sobald sie nicht mehr vom root set aus erreicht werden kann.

Alternative Lösung Ich bin ein wenig anderer Meinung. Man besitzt 5 Objekte (1-5 nummeriert) die in einem zyklus zusammenhängen, also 1-2-3-4-5-1-... wir nehmen an, das es einen zeiger auf die 1 gibt vom root-set raus. wenn wir nun die verbindung zwischen 4-5 löschen, dann wird das element 5 und nur das element 5 mit einem Mark&Sweep GC collected. (dies geschieht unter der annahme, das es keine doppelt verkette liste ist die den zyklus auferhält)

Wenn die Verbindung zwischen 4 und 5 entfernt wird, handelt es sich nicht mehr um eine zyklische Struktur. Was dann geschieht, steht in keinem Zusammenhang mit der Aufgabe....
Richtig erkannt, aber aufgabenstellung nicht verstanden: es geht darum zu zeigen, das Objekte in einer zyklischen Struktur eben doch gelöscht werden können und das konstrukt zerstört, ohne den gesamten ring zu kollekten. das die struktur anschliessend in einer linearen liste endet ist das ergebniss, was aber zeigt, das ich trotzdem objekte aus einer ringstruktur löschen kann. (zitat aus aufgabenstellung: "someone claims that objects which are linked in a ring structure will never be collected ...") Die Aufgabenstellung redet also davon, das objekte vor einem GC sicher wären, wenn sie sich ringförmig anordnen. dies ist aber wie gezeigt eben nicht der fall.
Ich weiss nicht was das soll mit dieser alternativen Lösung soll, in der Aufgabenstellung steht dass die Objekte Glieder einer Ringstruktur sind. Mir ist es schleierhaft wie man da reininterpretiren soll dass der Ring aufgelöst werden soll und dann der Garbagekollektor laufen lässt.

Aufgabe 9

Falls auf diese Art ein GC implementiert würde, könnten Prozeduren keine Objekte an ihre Aufrufer zurückgeben (ob direkt via Rückgabewert, oder via globale Variablen, oder via Pointer, die an die Prozedur übergeben wurden). Genauer gesagt würde der Aufrufer dann Pointer auf "Objekte" haben, deren zugehörige Speicherbereiche möglicherweise von anderen Prozeduren unbeabsichtigt überschrieben wird (Stichwort dangling pointer).

Um mit dieser Strategie einen funktionierenden GC zu konstruieren, müsste man sich diejenigen Objekte merken, auf die nach der Abarbeitung der Prozedur noch Pointer bestehen. Diese Pointer können sich in Registern, in globalen Variablen, im Stack oder im Heap befinden.

Aufgabe 10

Unterschiede:

  • Mark & Sweep: Hält eine Liste freier Blöcke aktuell, Aktualisierung bei jedem Sweep vorgang
  • Mark & Lazy Sweep: Verzichtet auf ein solches Vorgehen, für die Allokation neuer Objekte wird eine ausreichend lange Folge von unmarkierten Blocks im Speicher gesucht.

Vergleich:

  • Mark & Sweep: Geringe Allokationszeit, Mehraufwand bei jedem GC Aufruf zum Aktualisieren der Freelist
  • Mark & Lazy Sweep: Längere Allokationszeit, Aufwand die Freelist zu aktualisieren entfällt
Überlegung: Mark & Sweep ist eine Methode der Hauptspeicherverwaltung, dort existiert der Begriff des "Blocks" eigentlich nicht. Auch das Lazy Sweep Verfahren benötigt zur Verwaltung (insb. zur Allokation) Informationen, wo sich freie Speicherbereiche befinden und wie gross sie sind. Ob diese nun selbst verkettet und mit einer Grösseninformation ausgestattet sind, oder ob man dazu eine free list benutzt, ist im Endeffekt egal.