Lösungsvorschlag Operating Systems FS06

Aus VISki
Wechseln zu: Navigation, Suche

Aufgabe 1

A)

Die Readyliste ist der Pool der Threads, die bereit zum dispatch, sprich zur Ausführung sind

B)

  • Möglichkeit 1: Create
  • Möglichkeit 2: Ein Yield von einem aktiven Prozess
  • Möglichkeit 3: Rückkehr aus den Zuständen Waiting Res, Waiting Cond
  • Möglichkeit 4: Time Quantuum erschöpft (Preemption)

C)

  • Möglichkeit 1: Dispatch vom Scheduler
  • Möglichkeit 2: Terminate durch externe Forderung


Ich beziehe mich bei meiner Lösung direkt auf Seite 330 von [1]

Aufgabe 2

Szenario 1: Der niederprioritäre Thread besitzt eine lange Laufzeit und gibt die Kontrolle über den Prozessor nicht ab. Zudem verwendet er keine Ressourcen die auch der höherpriorisierte Thread verwenden wird. Sobald der höherpriorisierte Thread zum System hinzukommt ist er blockiert. Jedoch kann ein Scheduler mit Preemption den niederprioritären Thread beenden und dem höherpriorisierten Thread die Kontrolle übergeben.

Szenario 2: Der niederprioritäre Thread blockiert eine Ressource (bspw. hat ein File mit Schreibrechten geöffnet) auf die der höherpriorisierte Thread wartet. Durch Preemption lässt sich das Problem nicht lösen. (Es ginge jedoch mit Priority-Inheritance: indem nämlich der niederprioritäre Prozess die Priority des höherpriorisierte Threads erbt und seine Arbeit am File beendet und dann wieder zum höherpriorisierten Thread gewechselt wird.)

Aufgabe 3

Beim Booten durchläuft man den I-Node Bereich auf der Festplatte. Man startet mit einer "leeren" Belegungsbitmap, und markiert dann für jeden I-Node alle referenzierten Blöcke. Dabei muss man auch die indirekten Verweise im I-Node verfolgen.


Anmerkung: Im UFS scheinen die freien Blöcke bereits in einer I-Node vorhanden zu sein, die man dann einfach traversieren könnte. Siehe S 113 in [2].

Anmerkung zu Anmerkung: Aber genau diese Bitmap ist ja defekt und soll repariert werden? --The p 15:28, 27. Jun 2007 (CEST)

Anmerkung zur Anmerkung zur Anmerkung: Du hast recht, habe den Klammerkommentar überlesen. --Shial 15:35, 27. Jun 2007 (CEST)

Anmerkung zur Anmerkung zur Anmerkung: Das ist doch keine Bitmap

Aufgabe 4

Statt einer tatsächlichen Kopie erstellt man nur einen Link auf die bereits vorhandene zu kopierende Datei. Zudem setzt man bei der Datei ein Flag, dass anzeigt, dass diese Datei zur Zeit verlinkt und von wo aus. Werden nun an einer der "beiden" Dateien Änderungen vorgenommen, so wird das tatsächliche Kopieren erst jetzt ausgeführt und das Flag entfernt. (Dies lässt sich noch optimieren, indem man die Datei unterteilt und nur angibt welche Teile geändert wurden, so kann man noch weiterhin auf "gemeinsame" Teile verlinken anstatt zu kopieren.)

A           Datei A zu kopieren nach B.       
A'(B)       Bei der Datei ein Flag setzen
B -> A'(B)  Link von A nach B setzen
B    A      Beim Ändern einer der beiden Dateien, effektives Kopieren ausführen und Flag entfernen.

Aufgabe 5

Der Realtime Thread darf keine Pointer von markierten auf unmarkierte Objekte erstellen. Es tritt sonst die Problematik auf, die auf Seite 227 von [3] beschrieben wird.

Aufgabe 6

Das beschriebene Vorgehen kann zur Folge haben, dass ein niedrig priorisierter Prozess den kritischen Abschnitt nie ganz abarbeiten kann, wenn er jeweils vor dem Ende des kritischen Abschnittes preempted wird und ein Prozess höherer Priorität anschliessend in den kritischen Abschnitt eintritt. In diesem Fall erhält der niedriger priorisierte Prozess zwar Rechenzeit, aber die ausgeführten Aktionen werden jeweils sofort wieder rückgängig gemacht.

Aufgabe 7

Der VM Monitor des Hosts muss den beiden Gastbetriebssystemen eine gewisse Menge an realem Arbeitsspeicher vorgaukeln. Die beiden Gastbetriebssysteme werden im allgemeinen selten allen, den für sie realerscheinenden, Arbeitsspeicher besetzen. Der Monitor muss also dafür sorgen, dass er nur die vom Gastbetriebssystem tatsälich verwendeten Speicherbereiche auf dem Host alloziert. Die dem Gast zugeteilten Arbeitsspeicherbereiche müssen dann via einer Translation-Table, die vom VM Monitor verwaltet wird, auf den Speicher des Hosts abgebildet werden.

Ich denke es ist auch nötig dass den Betriebssystemen Pagetables vorgegaukelt werden die Sie umschalten können. Das heisst die Befehle die das Gastbetriebssystem für das Umschalten der Pagetable ausführt müssen abgefangen werden.

Aufgabe 8

Q hat Recht. Ob der Aufruf von x.f() zusätzliche Unterstützung zur Laufzeit benötigt, hängt davon ab, ob die Methode f "virtual" ist oder nicht. Nicht-virtual-Methoden sind fix in der Codeklasse (im Module-Heap) codiert und können darum ohne Laufzeitunterstützung aufgerufen werden. Die Adresse von Virtual Methoden kann erst zur Laufzeit bestimmt werden (wegen Überladung, Stichwort "Dynamic Binding"..?). Dies geschieht mit Hilfe von Methodentabellen, welche in den Deskriptoren der Objekte enthalten sind.

TODO: genauere Erklärung der Methodentabellen..

Aufgabe 9

Bin nicht sicher, aber vielleicht:

- Reference Counting: denn da sind in den Dateien selber gespeichert, wie viele Refenezen auf diese zeigen. Somit kann man das Problem des garbage collection in teilprobleme spalten, und somit distributed ausführen. Wenn clients ausloggen ists auch nicht schlimm, da dann niemand auf ihre Objekte zugreifen können und somit müssen ihre Referenzzähler nie modifiziert werden

Aufgabe 10

a) TLB, Festplattencache, L1/L2 Cache "used by the operating system", Caching in verteilten Systemen.

b) Auf der Idee, dass in letzter Zeit verwendete Objekte in kurzer Zeit wieder verwendet werden (temporal locality).

Zum anderen auf der Idee, dass wenn eine Stelle im Speicher (lesend oder schreibend) benutzt wird, dass kurz darauf auch benachbarte Stellen benutzt werden (spatial locality).

Aufgabe 11

Der monolithische Kern benötigt einen Mechanismus der das hinzuladen von kompilierten Gerätetreibern ermöglicht. Insbesondere muss der Kern dafür sorgen, dass die Gerätetreiber im Kernelmode laufen und ein "standardisiertes" (jedenfalls im voraus bekanntes) Kernelinterface auf Hardware und Speicher (Stichwort: Direct Mapping von Geräten in den Speicher) verwenden können.

Aufgabe 12

A)

i) Lesen

Beim Lesezugriff auf ein File muss Schreibzugriff für andere Prozesse auf dieses File gelockt werden. Ansonsten könnten inkonsistente Daten gelesen werden


ii) Schreiben

Lesen wie Schreiben muss für andere Prozesse gelockt werden. Würden Prozesse lesen wärend dem Schreibvorgang würden inkonsistente Daten gelesen, würden sie schreiben hätte das invalide Daten zur Folge. Sind im Directory noch Metadaten der Files gespeichert, müsste man auch dieses vor Lese- und Schreibzugriffen schützen.


iii) Löschen

Es muss Lese und Schreibzugriff auf das Directory in dem das File lieg, und auf das File selbst verboten werden. Das Directory wird gelockt damit keine inkonsistenten Directory-Informationen gelesen werden und das Directory-File nicht durch parallele Schreibzugriffe invalidiert wird. Das File muss aus den selben Gründen wie beim Schreiben vor fremdem Zugriff geschützt werden


B)

Deadlock Gefahr: Ein File wird gelöscht, wärend ein oder mehrere Prozesse auf Zugriff darauf warten. Lösung: Es wird ein modifizierter "Pulse" auf die wartenden Prozesse ausgeführt, die den Prozessen mitteilt dass das File nicht mehr existiert. Alternativ könnte auch das File mit einem "gelöscht" Flag markiert werden, auf das die anderen Prozesse reagieren können.

Aufgabe 13

A) Eine erweiterte Partition enthält wiederum einen PBR (einen Extended PBR aka EPBR oder EBR) und kann weitere Partitionen enthalten. Er wurde eingeführt, da ohne erweiterte Partionen nur 4 Partitionen pro Festplatten möglich wären (für Details siehe Slide 38 BS07cAll.pdf)

B) Der Code im MBR durchsucht standardmässig nur die primären Partitionen. Stattdessen könnte er zusätzlich auch die verkettete Liste der erweiterten Partitionen traversieren. Jede erweiterte Partition besitzt einen EPBR, wo Platz für einen Boot loader, ein bootable Flag etc. vorhanden ist.

Aufgabe 14

A)

mark_sweep()
  for R in Roots
    mark(R)
  sweep()
  if free_pool is empty
    abort "Memory exhausted"
mark(N)
 if mark_bit(N) == unmarked
   mark_bit(N) = marked
   for M in Children(N)
     mark(*M)
free(N)
  add N to free_pool
sweep()
  N = Heap_bottom
  while H < Heap_top
    if mark_bit(N) == unmarked
      free(N)
    else mark_bit(N) = unmarked
    N = N + size(N)

B) Ich würde sagen das hängt von der "Form" des Objektbaumes ab und kann nicht vorhergesagt werden. Die Rekursive Funktion kann sehr wenig Speicher brauchen (Baum sehr breit und nicht tief) aber auch sehr viel (sehr tiefer Baum).

C) todo

Aufgabe 15

Eine Möglichkeit wäre wohl dies über die Hauptspeicherwaltung zu erledigen (Slide 193 BS07AllC.pdf). Bei der Prozesserstellung wird nun jedem Schwergewichtsprozess denselben Codeblock mit Programmmodulen zugewiesen, indem der Virtual Memory Manager in der Arbeitsspeicher Page Table jedem Prozess die Adressen (wo sich im Speicherbild die Programmmodule befinden) zur selben realen Adresse verlinkt.

Speicherbilder der beiden Prozessen
Prozess 1        Realer Speicher          Prozess 2

OS                                           OS
Stack                                       Stack
  |                                         Stack
  |                                          
Stack                                        Heap
                                             Heap
Heap                                         Heap
  |                                         Programm-
  |          - - - ->Progr.- <-------------   module
  |        -         module                  OS
  |     ---
Heap  --
Pro-
gramm-
module
 OS

Aufgabe 16

Man kann hier das gleiche Problem wie im Midterm 07, Frage 6a anführen:

Man betrachte einen Netzwerktreiber der empfangene Daten von der Netzwerkkarte per Interrup in einen Software Puffer schreibt. Wärend diesem Schreibprozess muss der eigene Interrupt ausmaskiert werden, damit der Schreibprozess nicht durch neue Daten unterbrochen wird (geschachtelte Interrupts).