Betriebssysteme Klausur

Question

Welche Scheduling-Verfahren gibt es?

Answer 1

Priority Scheduling
Round Robin
Multilevel Feedback Queue
Lottery Scheduling
PSJF
FCFS

Answer 2

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“.

Answer 3

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.

Answer 4

Interrupts deaktivieren (nur im Kernel-Space, nur Single-Core)
Spezielle atomare Instruktionen:
Semaphor (wait und signal)
Monitor
Algorithmus von Peterson

Answer 5

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.

Answer 6

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.

Answer 7

RAID 0: Striping. Die Daten werden blockweise abwechselnd auf die Platten verteilt.
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.

Answer 8

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 alle 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.

Answer 9

Sie würden zu viel Speicher benötigen. Es wird eine Seitentabelle pro Prozess benötigt. Die Größe einer einstufigen Seitentabelle berechnet sich folgendermaßen: 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 Seiteneintrags · 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 \text{ GiB} = 4 \cdot 2^{30} \text{ Byte} = 2^{32} \text{ Byte}$, $p = 4096 \text{ Byte}$ und $a = 8$. Daraus folgt eine Seiteneintrags-Größe von 4 Byte und $2^{52} = 4.503.599.627.370.496$ Seiten. Das ergibt eine Seitentabellengröße von $2^{54}$ Byte = 16 PiB (Pebibyte).

Answer 10

Sei $b$ die Größe eines Blocks in Byte, ein Zeiger belege 4 Byte und ein Inode habe (wie bei ext2) zusätzlich 12 direkte Blöcke. Dann berechnet sich die maximale Dateigröße in Byte folgendermaßen: $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 die Blockgröße so herausfinden:

moose@pc08 ~ $ 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
moose@pc08 ~ $ sudo tune2fs -l /dev/sda1 | grep 'Block size'
Block size:               4096

Answer 11

Ich sehe gerade, dass bei rodata wohl das Schlüsselwort const dabei stehen sollte. Statische Variablen können natürlich geändert werden.

Answer 12

Anonymous memory is memory that is not backed by a file. Examples are stack and heap.

Betriebssysteme Klausur

Themen

Begriffe

FAQ

Material

Some Random Facts

Termine und Klausurablauf

Ergebnisse