• Martin Thoma
  • Home
  • Categories
  • Tags
  • Archives
  • Support me

Betriebssysteme Klausur

Contents

  • Betriebssysteme Klausur
    • Themen
    • Begriffe
    • FAQ
    • Material
    • Some Random Facts
    • Termine und Klausurablauf
    • Ergebnisse
Dieser Artikel beschäftigt sich mit der Vorlesungen des Moduls „Betriebssysteme“ am KIT. Er dient als Prüfungsvorbereitung. Ich habe die Vorlesungen bei Prof. Dr. Bellosa und später bei Prof. Dr. Beigl gehört.

Wenn ich im Folgenden eine Seitenzahl angebe, dann ist damit "Operating System Concepts" von Silberschatz gemeint (ISBN 0-471-69466-5):

Themen

  • Process Coordination:
    • Shared Memory
    • Critical-Section Problem: Peterson's Solution, Synchronisation
    • Deadlock, Starvation
  • Process Management
    • Process Sheduling
    • Process States: new, ready, running, waiting, terminated
    • Process Control Block: Folie 6/65 slide_proc_management
  • Memory Management
    • Globale / lokale Seitenersetzungsstrategie
    • Equal allocation
    • Slab allocator

Begriffe

Folgende Begriffe muss man kennen und erklären können:

  • Critical Section und Race Condition
  • Semaphor: counting Semaphores, binary Semaphores und Mutex Locks → Antwort auf S. 200f
  • Dining-Philosophers Problem → Antwort auf S. 207f
  • Deadlock, Starvation
  • Safe State

FAQ

  • Wie funktionieren Bitmasken und insbesondere ~, &, |?
  • Nenne ein reales Beispiel, bei dem eine Race-Condition auftreten könnte.
  • Welche Probleme hat Contiguous Allocation? → Antwort
Welche Scheduling-Verfahren gibt es?
  • Priority Scheduling
  • Round Robin
  • Multilevel Feedback Queue
  • Lottery Scheduling
  • PSJF
  • FCFS
What is the difference between Page and Frame?
In a paging system, programs and data stored on disk are divided into equal, fixed sized blocks called pages, and main memory is divided into blocks of the same size called frames. Exactly one page can fit in one frame. Physical memory is divided into parts called „frame“ and logical memory is divided into parts called „page“.
Quelle: wiki.answers.com
Nennen und erläutern Sie die drei notwendigen Bedingungen für eine gültige Lösung des Problems kritischer Abschnitte.
  • Mutual exclusion: Only one thread can be in the CS at a time.
  • Progress:
    • If no thread is in the CS one of the threads trying to enter will eventually get in
    • Threads that are not trying to enter do not hinder processes that try to enter from getting in
  • Bounded waiting: Once a thread starts trying to enter the critical section, there is a bound on the number of times other threads get in.
Wie kann man das Problem kritischer Abschnitte lösen?
  • Interrupts deaktivieren (nur im Kernel-Space, nur Single-Core)
  • Spezielle atomare Instruktionen:
    • Test-and-set
    • Compare-and-swap
    • Fetch-and-add
    • swap
  • Semaphor (wait und signal)
  • Monitor
  • Algorithmus von Peterson
Nennen und erklären Sie die ver notwendigen Bedingungen für Deadlocks.
  • Mutual exclusion: Eine Ressource kann nicht gleichzeitig von mehreren Prozessen benutzt werden
  • Hold and wait: Ein Prozess, der bereits mindestens eine Ressource hält, wartet auf mindestens eine andere Ressource
  • No preemption: Zugeteilte Ressourcen können einem Prozess nicht wieder entzogen werden. Er muss diese selbst freigeben.
  • Circular wait: Es gibt eine Menge von Prozessen $\{P_0, P_1, \dots, P_n\}$, wobei $P_0$ auf eine Ressource wartet, die $P_1$ hält, $P_1$ auf eine Ressource wartet, die $P_2$ hält, ..., $P_n$ auf eine Ressource wartet, die $P_0$ hält.
Was kann man in Bezug auf das Deadlock-Problem machen?
  • Prevention
  • Avoidance
  • Detection:
    • Prozess abschießen
    • Rollback
  • Vogel-Strauß-Algorithmus: Der User wird sich schon drum kümmern, z.B. indem er einen Prozess abschießt (kill -9) oder indem er den PC vom Strom nimmt.
Erklären Sie Raid 0 - 5.
  • Raid 0: Striping. Platten werden "aneinandergehängt".
  • Raid 1: Mirroring. Daten werden auf mehrere Platten gespiegelt.
  • Raid 2: Fehlerkorrigierender Hamming-code.
  • Raid 3: Byteweise Parität.
  • Raid 4: Blockweise Parität.
  • Raid 5: Blockweise, verteilte Parität.
Warum verwenden wir Seitentabellen? Könnte man nicht einfach im Hauptspeicher je zwei Datenwörter kombinieren, wobei das erste die Metainformationen (z.B. Zugriffsrechte, Prozess-ID) und das zweite die Daten enthält?
Prinzipiell wollen wir in einer x86-Architektur, dass sich die Hardware um das Paging kümmert. Bei MIPS sieht das wohl anders aus (Quelle). Wenn man sich für jedes Datenwort ein Datenwort mit Metainformationen merken würde, hätte man sehr viel Overhead. Diese Informationen hat man bei Paging auf IA-32 nur jede 4096 Byte! (Allgemein ist Overhead übrigens eine Begründung, die häufig stimmt.) Falls man es wirklich genau wissen will, sollte man wohl die IA-32 Architectures Software Developer’s Manuals lesen. Das sind ja nur 3044 Seiten.
Einstufige Seitentabellen sind deutlich einfacher zu verstehen und zu implementieren. Warum verwendet man sie nicht auf 64 Bit Systemen?
Sie würden zu viel Speicher benötigen. Es wird eine Seitentabelle pro Prozess benötigt. Die Größe einer einstufigen Seitentabelle berechnet sich wie folgt: Sei $m$ die Größe des Hauptspeichers in Byte, $p$ die Größe einer Seite in Byte und $a$ die Anzahl der zusätzlichen Bit pro Seite (Access Control bits, validity. Siehe StackExchange). Dann gilt: Größe der Seitentabelle = Größe eines Seiteneintrages · Anzahl der Seiten $= \lceil \frac{\log_2(\frac{m}{p}) + a}{8}\rceil \text{Byte} \cdot \frac{2^{64} \text{ Byte}}{p \text{ Byte}}$ Typischerweise gilt: $m = 4 GB = 4 \cdot 2^{30} \text{ Byte} = 2^{32} \text{ Byte}$, $p = 4096 \text{ Byte}$ und $a = 8$. Daraus folgt eine Seitengröße von 4 Byte und 4.503.599.627.370.496 Seiten. Das ergibt eine Seitentabellengröße von 16 Petabyte.
Wenn man nur Segmentierung nutzt, wie kommt man dann von der logischen Adresse auf die physische?
Segmentation: Logical to linear address
Segmentation: Logical to linear address (source)
Wie ist ein Inode aufgebaut?
Struktur eines Inodes
Struktur eines Inodes
Wie groß kann eine Datei maximal werden, wenn man Inodes mit jeweils einem indirekten, doppelt indirektem und dreifach indirektem Block hat?
Sei $b$ die Größe eines Blocks in Byte und ein Zeiger belege 4 Byte. Dann berechnet sich die maximale Dateigröße in Byte wie folgt: $12 \cdot b + \frac{b}{4} \cdot b+ \frac{\frac{b}{4} \cdot b}{4} \cdot b + \frac{\frac{\frac{b}{4} \cdot b}{4} \cdot b}{4} \cdot b = 12 \cdot b + \frac{b^2}{4} + \frac{b^3}{16} + \frac{b^4}{64}$ Bei einer Blockgröße von 1024 Byte sind das 17,25 GB (Rechnung), bei einer Blockgröße von 4096 Byte sogar 4,40 TB (Rechnung)! Wenn ihr Linux habt, könnt ihr diese Werte so herausfinden:
[email protected] ~ $ df
Filesystem     1K-blocks     Used Available Use% Mounted on
/dev/sda1      303869280 16418288 272015268   6% /
udev             1889040        4   1889036   1% /dev
tmpfs             758712      988    757724   1% /run
none                5120        0      5120   0% /run/lock
none             1896772      772   1896000   1% /run/shm
none              102400        8    102392   1% /run/user
[email protected] ~ $ sudo tune2fs -l /dev/sda1 | grep 'Block size'
Block size:               4096
Depict the common memory layout of a process. Give an example of the data that is stored in each section.
Common process memory layout
Common process memory layout
Ich sehe gerade, dass bei rodata wohl das Schlüsselwort const mit dabei stehen sollte. Statische Variablen können natürlich geändert werden.
What is anonymous memory?
Anonymous memory is memory, that is not backed by a file. Examples are stack and heap.

Material

Material zum Üben (also alte Klausuren) gibts wie immer entweder online oder bei der Fachschaft.

Die Lösungen zu den Klausuren sind Passwortgeschützt, aber wenn ihr euch einmal über VPN einloggt, stehen ganz unten auf der Seite die Zugangsdaten.

Das Skript / die Folien sind im VAB.

Folgende Wiki-Artikel und manpages sollte man sich durchlesen:

  • Unix-Dateirechte und chmod sowie mein Artikel.

Als Buch kann ich neben dem Silberschatz folgendes Empfehlen: LPIC-1 - Vorbereitung auf die Prüfung des Linux Professinal Institute. ISBN 978-3-937514-81-9

Some Random Facts

  • subl $16, %esp allokiert 16 Byte auf dem Stack.

Termine und Klausurablauf

Datum: 18.03.2012 um 14:00 Uhr.
Ort: ich bin im 30.21 Gerthsen (Hörsaalverteilung)
Dauer: 60 Minuten
Punkte: 60
Benuspunkte: Abhängig von den Punkten im Übungsschein:

  • 110 - 129 Punkte: 1 Bonuspunkt
  • 130 - 149 Punkte: 2 Bonuspunkte
  • 150 - 169 Punkte: 3 Bonuspunkte
  • 170 - x Punkte: 4 Bonuspunkte

Quelle
Nicht vergessen: Studentenausweis
Einsicht: 09.04.2013 (war seit spätestens 13.02.2013 bekannt)
Ort der Einsicht: 07.07 (Vincenz-Priessnitz-Str. 1, 2.OG, links), Raum 215
Zeit der Einsicht: Je nach Matrikelnummer unterschiedlich.

Ergebnisse

Hängen noch nicht aus (Stand: 15.03.2013) Hängen nun aus (Stand: 08.04.2013) und sind im VAB

Ergebnisse der OS-Klausur vom WS 2012 / 2013
Ergebnisse der OS-Klausur vom WS 2012 / 2013

Published

Mär 2, 2013
by Martin Thoma

Category

German posts

Tags

  • Klausur 34

Contact

  • Martin Thoma - A blog about Code, the Web and Cyberculture
  • E-mail subscription
  • RSS-Feed
  • Privacy/Datenschutzerklärung
  • Impressum
  • Powered by Pelican. Theme: Elegant by Talha Mansoor