Lösungsvorschlag Operating Systems FS08

Aus VISki
Wechseln zu: Navigation, Suche


1. Bootstrapping, Partitionierung

a)

Der Bootloader des MBR muss sich an eine andere Stelle im Speicher kopieren und dann an der neuen Stelle weiterlaufen. Erst danach kann der Partition Bootloader an die vorherige Stelle kopiert und dort ausgeführt werden

b) c)

2. Filesysteme

a)

Verkettete freie Abschnitte
+ kein Platzverbrauch
- Fehleranfälligkeit
Bitmap
+ wenig Speicherplatz
- fixer Platzverbrauch, nicht adaptiv
Liste Freie Blöcke
+ adaptiver Platzverbrauch
- freie Segmentlängen unsichtbar

b)

Gegen externe Fragmentierung: Extents

Gegen interne Fragmentierung: Tail Packing

c)

Z.B. NTFS Kompressionsmethode.
Schreiben: man schaut, ob die erste 16 Blöcke des files sich komprimieren lassen. Falls ja, Kompressionsalgorithmus anwenden und auf Disk speichern. Falls nicht, 16 Blöcke normal schreiben. Und so weiter für die restliche Blöcke. Die verschiedene 'runs' werden dann im MFT Record geschrieben.
Lesen: mann schaut im MFT, ob den benötigten 'run' Komprimiert ist oder nicht. Falls ja, dekomprimieren, ansonsten normal lesen.

3. Filesysteme

a)

Ein Verzeichnis ist selber ein File, der auf andere Files verweist.

b)


c)

4. I/O

a) b) c)

5. Heap Verwaltung

a)

- Automatisieren von free-operationen (Entlastung für den Programmierer)

-Memory Leak vermeiden: falls man kein GC hat, bleibt der Speicherplatz alloziert, auch wenn er nicht mehr gebraucht (referenziert) ist. Der Speicher ist dann relativ schnell voll.

b)

Ein Weak-Pointer zeigt auf ein Objekt, das vom GC nicht "geschütz" ist. Also das Objekt wird am nächsten Durchlauf des GC gelöscht.

Ein Weak-Pointer ist ein Pointer, der vom GC nicht zur Markierung benutzt wird. Wird ein Objekt nur noch von Weak-Pointers referenziert, wird es vom GC gelöscht.

Mit Weak-Pointers kann man z.B. Caches implementieren.

c)

6. Laufzeitunterstützung, Heapverwaltung

a)

Mark bit + offset

b)


c)

7. Virtueller Speicher

a)

  • Illusion des unendlich grossen Speichers
  • Prozess hat potenziell den ganzen Speicher zu Verfügung
  • Prozesse voneinander abschirmen
  • Code wiederverwenden (shared libraries)
  • Erleichterter Programmstart: Jeder Prozess kann annehmen, dass sein Stack an der gleichen Adresse startet, usw.

b)

  • Memory-Mapped I/O

c)

Paging

Problem mit sehr viele Prozesse: Granularität zu gross -> Microstack

8. Concurrency

a)

Als Race Condition werden in der Programmierung Konstellationen bezeichnet, in denen das Ergebnis einer Operation vom zeitlichen Verhalten bestimmter Einzeloperationen abhängt. Ein typisches Beispiel ist wenn mehere Prozesse auf einen File schreiben.

b) c)

9. Concurrency

a)

Deadlock: Eine Menge von Prozessen befindet sich in einem Deadlock, wenn jeder dieser Prozesse auf ein Ereignis wartet, das nur ein anderer Prozess aus dieser Menge verursachen kann. Die Prozesse sind blockiert und ändern ihres Zustand nicht.

Starvation: Ahnlich wie Deadlock, nur sind die Prozesse hier *nicht* in einem blockierten Zustand. Starvation passiert wegen unglückliches oder fehlerhaftes Scheduling.

Ein Monitor kann weder deadlock noch starvation verhindern.

b)
i) A, B1, C1, B2, D, C2
ii) A, B1, C1, C2, D, B2
iii) A, B1, C1, B2, C2, D


c)

10. Prozesse

a)

Der Prozess ist eine laufende Instanz eines Programms. Jeder Prozess hat seinen eigenen virtuellen Speicherbereich (Stack und Heap). Interprozesskommunikation läuft über das OS, Rechenzeit wird zwischen de Prozessen durch das OS verteilt.

In einem Prozess können mehere Threads parallel laufen, die sich nun den selben Speicherbereich teilen -> Der Programmierer muss sich selbst um locking Mechanismen kümmern.

b)

Gewisse Instruktionen können nur in Kernel Mode ausgeführt werden.

Changed processor mode:

  • System calls
  • Interrupts
  • Traps
  • Faults

Thread changes:

  • Thread calls yield()
  • Thread gets preemted
  • Thread performs blocking I/O
  • Thread terminates

c)

Monitor verwenden

11. Scheduling

a)

Aging: die Priorität eines seit lange wartenden Prozess wird mit der Zeit erhöht. Das verhindert auch das Priority Inversion Problem.

b)

Scheduling: entweder so

0------3--------8---------12------------17--------------------26
|  P1  |   P4   |    P2    |      P1     |        P3           |
+--------------------------------------------------------------+

oder so

0--------------8---------12------------17--------------------26
|     P1       |    P2    |      P4     |        P3           |
+-------------------------------------------------------------+


c)

+ Fairness: gemäss Priorität werden die Zeitquanten fair verteilt.
+ Vermeidete Starvation: Jeder Prozess hat eine Wahrscheinlichkeit >0%, ausgewählt zu werden.
- Nicht Adaptiv: Fixe Zeitquanten haben das Nachteil, dass die Prozesse relativ "oft" preempted werden. Das overhead könnte bei sehr kurze Threads zu gross sein.
- Zeitverschwendung: I/O lästige Aufträge werden nicht berücksichtigt. Ein Thread könnte ein Zeitquantum erhalten, obwhol er sowieso auf einem I/O auftrag warten muss.
- Implementierung: Da es sehr viele Prioritätsstufen gibt, und ggf. auch sehr viele Threds geben kann, müssen eventuell Millionen Los verteilt werden. Die Verwaltung einer solche Datenstruktur kann sehr aufwändig werden.

12. Betriebssystemearchitekturen, Virtuelle Maschinen

a)

Monolitische Systeme, Geschichtete Systeme, Mikrokerne, Exokerne

b)


c)