Aufgabe 5. Prozesse und Threads

Question 1

Nennen und erläutern Sie zwei wesentliche Aufgaben eines I/O Subsystems in einem Betriebssystem. (2 pt) Give and explain two essential tasks of an operating system’s I/O subsystem.

Accepted Answer

(0,5 P) für jede gegebene Aufgabe (maximal zwei) plus (0,5 P) für eine entsprechende Erläuterung. Andere werden akzeptiert, wenn sie plausibel sind.Abstraktion Das I / O-Subsystem sollte eine einheitliche Schnittstelle und Zusammenfassung von den physischen Details der Geräte liefern.Serialisierung In einem System mit asynchroner E / A oder Multiprogrammierung, können mehrere offene E / A-Anfragen gleichzeitig vorhanden sein. Allerdings unterstützen die meisten Geräte nur eine einzelne E / A-Operation zu einem Zeitpunkt. Es ist die Aufgabe des I / O-Subsystems, I / O-Forderungen zu serialisieren.Scheduling In einem System sind oft bestimmte Jobs wichtiger als andere (z.BInteraktive Anwendung vs. Hintergrund Virus Scan). Das I / O-Subsystem solltedies durch die Planung von I / O-Anfragen nach der Priorität der Jobs wiederspiegeln. Sonstiger Punkt:Fairness erreichenFehlerbehandlung Das I / O-Subsystem sollte mit einer Funktionsstörung des Gerätes fertig werden.Die Fehlgeschlagene Festplatte liest oder schreibt durch anmutige Vervollständigung der zugehörigen E / A-Anfragen und meldet den Fehler an den Emittenten.Pufferung Abhängig von der I / O-Schnittstelle kann es sich um die Aufgabe des I / O-Subsystems handeln, zwischen Daten zwischen einem Prozess und einem Gerät zu Puffern, wegen der Geräteübertragungsgröße oder einer semantischen Kopie für asynchrone E / A zu pflegen.(0.5 P) for each given task (two at most) plus (0.5 P) for a corresponding explanation.Other tasks are accepted if they are plausible.Abstraction The I/O subsystem should provide a uniform interface and abstractfrom the physical details of devicesSerialization In a system with asynchronous I/O or multiprogramming, multipleopen I/O requests can exist simultaneously. However, most devices support onlya single I/O operation at a time. It is the I/O subsystem’s task to serialize I/Orequests.Scheduling On a system often certain jobs are more important than others (e.g.,interactive application vs. background virus scan). The I/O subsystem shouldreflect this by scheduling I/O requests according to the jobs’ priority. Other point:achieve fairness.Error Handling The I/O subsystem should cope with device malfunction such asfailed disk reads or writes by gracefully completing associated I/O requestsand report the error to the issuer.Buffering Depending on the I/O interface, it can be the I/O subsystem’s task tobuffer data between a process and a device, because of device transfer sizelimits or to maintain a copy semantic for asynchronous I/O.

Question 2

Erläutern Sie die Unterschiede zwischen Programmed I/O und Interrupt-getriebener I/O. (2 pt) Explain the differences between programmed I/O and interrupt-driven I/O.

Accepted Answer

Bei programmierter I / O gibt die CPU einen Gerätebefehl aus und fragt nach einem Gerätestatus ab. Die CPU kann auch entscheiden, andere Arbeit auszuführen, aber es wird nicht signalisiert wenn das Gerät nach Abschluss der Operation ist. Es muss zu letzt das Statusregister überprüfen. Die Datenübertragung wird jeweils ein Wort sein. (1 P)Bei unterbrechungsgesteuerten E / A muss die CPU kein Gerätestatusregister abfragen.Stattdessen erstellt das Gerät einen Interrupt, wenn der Vorgang beendet ist. Folglich,Die CPU kann während des Wartens auf das Gerät eine andere Arbeit ausführen. Datenübertragung, bedeutet immer noch ein Wort zu einer bestimmten Zeit. (1 P)With programmed I/O the CPU issues a device command and polls on a device statusregister for the completion of the operation. The CPU may also decide to perform otherwork, however, it will not be signaled when the device is ready and ultimately hasto check the status register. Data transfer will be one word at a time. (1 P)With interrupt-driven I/O the CPU does not need to poll on a device status register.Instead, the device raises an interrupt when the operation finishes. Consequently,the CPU can perform other work while waiting for the device. Data transfer, however,still happens one word at a time. (1 P)

Question 3

Durch welche Technik kann der Datendurchsatz von Interrupt-getriebener I/O deutlich erhöht werden? Erläutern Sie kurz, wie diese Technik funktioniert. (2 pt) What technique can noticeably increase the data throughput of interrupt-driven I/O? Briefly explain how this technique works.

Accepted Answer

Direkter Speicherzugriff (DMA) (1 P). Mit DMA ist die CPU damit entlastet, die Daten auf einer Wort-Basis vom Gerät zum Hauptspeicher zu transferieren. Stattdessen schreibt das Gerät direkt (Oder indirekt über den DMA-Controller) in den Hauptspeicher und nur eine einzige Unterbrechung wird ausgelöst, wenn die gesamte Transaktion (z. B. ein Sektor vom Sekundär-Speicher lesen) vervollständigt ist (1 P).Direct memory access (DMA) (1 P). With DMA the CPU is relieved from having to transferdata on a per-word basis from the device to main memory. Instead, the device directly(or indirectly via the DMA controller) writes to main memory and only a singleinterrupt is fired, when the entire transaction (e.g., reading a sector from secondarystorage) completes (1 P).

Question 4

Erläutern Sie, weshalb moderne Speichergeräte in der Regel keine Aussage über die tatsächliche Speicherposition von Daten auf dem physischen Medium erlauben. Wieso ist dies insbesondere bei SSDs der Fall? (2 pt) Explain why modern storage devices usually do not allow conclusions on the actual storage position of data on the physical medium. Why is this particularly true for SSDs?

Accepted Answer

Moderne Geräte verwenden die logische Blockadressierung (LBA), die das Speicherlayout des physikalischen Mediums verdeckt (1 P). Dies erleichtert die Entwicklung einer geräteunabhängigen Driver-Software und ermöglicht es dem Gerät, eine beliebige Zuordnung zwischen Blockadressen physikalische Lagerorten durchzuführen. Während dieses Merkmal seit langem von HDDs verwendet wird, um gebrochene Sektoren zu Schonsektoren zu reparieren, können SSDs transparente Verschleißnivellierungen implementieren und Neu abbauen. Auf diese Weise können SSDs transparent tragende level implementieren (0,5 P) um die Effekte der begrenzten Schreibzahl von NAND-Zellen mindern . Weiterhin ermöglicht eine neue Zuordnung den SSDs, mit vorzeitig gelöschten Sektoren zu arbeiten, was die Schreiblatenz reduziert (0,5 P).Modern devices use logical block addressing (LBA), which hides the storage layout ofthe physical medium (1 P). This eases the development of device independent driversoftware and enables the device to perform an arbitrary mapping between block addressesand physical storage locations. While this feature has long been used onHDDs to remap broken sectors to sectors, SSDs particularly depend on extensiveremapping. This way, SSDs can implement transparent wear leveling (0.5 P) tomitigate the effects of the limited write count of NAND cells. Furthermore, remappingenables SSDs to work with prematurely erased sectors, which reduces write latency(0.5 P).

Question 5

Gegeben ist ein I-Node mit vier Platzen zur direkten Blockadressierung, einem Platz zur einfach-indirekten Blockadressierung und einem Platz zur zweifach-indirekten Blockadressierung. Jeder Block umfasst 512 Bytes, eine Blockadresse 8 Bytes. a) Um welche Art der Dateiblockallokation handelt es sich? (1P) b) Berechnen Sie den nötigen Speicherbedarf in Bytes zur vollständigen Adressierung einer 1 MiB großen Datei. (3P) Consider an i-node with four entries for direct block addressing, one entry for single-indirect block addressing, and one entry for double-indirect block addressing. A block is 512 bytes in size, a block address is 8 bytes long. a) What kind of file block allocation is used? b)Calculate the amount of storage space in bytes required to fully address a 1 MiB file.

Accepted Answer

a) Indexierte Zuordnung (1 P)a) Indexed Allocation (1 P)Um 1 M iB = 220 Bytes zu adressieren, benötigen wir 220 Bytes = 211 Blöcke. 29 bytes Ein einzelner indirekter Block kann 29bytes = 26 Blöcke adressieren. 23 Bytes Wir brauchen also 211 = 25 Einzel-indirekte Blöcke (jeweils 512 Bytes). 26 Weil wir nur einen einzigen indirekten Block im i-Knoten haben, müssen wir die doppelte indirekte Adressierungsebene verwenden. Diese Ebene ist effektiv nur eine Reihe von zusätzlichen 26 Einzel-indirekten Blöcke mit den Kosten eines einzelnen 512-Bytes-Blocks. Die vier direkten Block-Adressen im i-Knoten speichern keinen vollständigen Einzel-indirekten Block, sondern kosten extra 4 * 8 Bytes = 32 Bytes. Darüber hinaus haben wir einen Zeiger auf den Einzel-indirekten und einen Zeiger auf die doppelt-indirekten Block (2 * 8 Bytes = 16 Bytes). Das ergibt eine Raumanforderung von:25 ∗ 512 bytes (1 P) + 512 bytes (1 P) + 48 bytes (1 P)= 214 bytes + 512 bytes + 48 bytes= 16 KiB + 512 bytes + 48 bytes= 16944 bytesb)To address 1 M iB = 220 bytes we need 220 bytes = 211 blocks. 29 bytes A single-indirect block can address 29bytes = 26 blocks. 23 bytes We thus need 211 = 25 single-indirect blocks (512 bytes each). 26 Because we have only a one single-indirect block in the i-node, we have to usethe double-indirect addressing level. This level is effectively only an array of additional26 single-indirect blocks at the cost of a single 512 bytes block. The four directblock addresses in the i-node do not save a full single-indirect block, but cost extra4 ∗ 8 bytes = 32 bytes. Furthermore, we have one pointer to the single-indirect and onepointer to the double-indirect blocks (2 ∗ 8 bytes = 16 bytes). This gives a total spacerequirement of:25 ∗ 512 bytes (1 P) + 512 bytes (1 P) + 48 bytes (1 P)= 214 bytes + 512 bytes + 48 bytes= 16 KiB + 512 bytes + 48 bytes= 16944 bytes

Question 6

Welche UNIX Dateizugriffsrechte wurden in der Vorlesung besprochen und wofür stehen diese bei Dateien und Verzeichnissen? (3 pt) Which UNIX file permissions where discussed in the lecture and what do these permissions stand for when set for files and directories?

Accepted Answer

Dateien: 1 = ausführen (0,5 P) 2 = schreiben (0,5 P) 4 = lesen (0,5 P) Verzeichnisse: 1 = Verzeichnis Öffnen (0,5 P) 2 = Dateien erstellen, löschen, umbenennen (0,5 P) 4 = Listendateien (0,5 P)Files: 1 = execute (0.5 P) 2 = write (0.5 P) 4 = read (0.5 P) Directories: 1 = directoryopen (0.5 P) 2 = create, delete, rename files (0.5 P) 4 = list files (0.5 P)

Question 7

Die meisten Betriebssysteme stellen einen Buffer Cache für Dateisysteme bereit. Beschreiben Sie einen Nachteil dieses Caches und schlagen Sie eine mögliche Losung für dieses Problem vor! (2 pt) Most operating systems provide a buffer cache for file systems. Describe one disadvantage of this cache and propose a possible solution to this problem!

Accepted Answer

Write-behind-policy könnte zu Datenverlusten im Falle eines Systemabsturzes und / oder inkonsistenten Zustand der FS führen(1 P) Lösung: keine Write-behind-policy oder Journaling-Datei-System (1 P)oder FS-Cache-Wiping, wenn nacheinander eine sehr große Datei von Ende zu Ende gelesen wird und erneuter Zugriff nicht statt findet (1 P) Lösung: Umgehen des Puffer-Cache, entweder durch direkte I / O oder Hinweise wie sequentieller Zugriff (1 P)Write-behind policy might lead to data losses in case of system crash and/or inconsistentstate of the FS (1 P) Solution: no write-behind policy or a journaling filesystem (1 P) orFS Cache wiping if sequentially reading a very large file from end to end and notaccessing it again (1 P) Solution: by-passing the buffer cache, either by direct I/O orhints like sequential access (1 P)

Question 8

Nennen und erklären Sie die Unterschiede zwischen, den in der Vorlesung behandelten File Locking Ansätzen! (2 pt) Name and explain the difference between the two file locking approaches presented in the lecture!

Accepted Answer

Obligatorisch: Das Betriebssystem sorgt dafür, dass kein Prozess eine Datei öffnen kannwelche ein anderer Prozess momentan offen hat.(1 P) Beratend: Das Betriebssystem erlaubt den gleichzeitigen Zugriff mehrerer Prozesseauf die gleichen Datei. Bei Bedarf müssen die Prozesse selbst eine korrekte Synchronisation durchführen. (1 P)Mandatory: The operating system ensures that no process can open a file that anotherprocess holds a lock on. (1 P)Advisory: The operating system permits the simultaneous access of multiple processesto the same file. If required, the processes have to perform correct synchronizationon their own. (1 P)

Question 9

Welchen RAID Level würden Sie für ein Datacenter vorschlagen? Es soll sowohl eine bessere Performance als auch eine höhere Zuverlässigkeit als eine einzelne Festplatte bieten. Beachten Sie auch die Kosten. Warum haben Sie den Level gewählt und wie viele Festplatten brauchen Sie mindestens für die Umsetzung? (2 pt) Which RAID level would you suggest for a datacenter? It should provide both higher performance and better reliability than a single hard disk. Keep the costs in mind. Why have you chosen the level and how many disks are at least required?

Accepted Answer

RAID5 benötigt mindestens 3 Festplatten. (1 P) RAID5 bietet höhere Leistung und bessere Zuverlässigkeit ohne die Notwendigkeit einer einzigen Engpassscheibe (RAID4) und niedrigere Kosten verglichen mit RAID01 (4 Platten). (1 P)RAID5, requires at least 3 disks. (1 P) RAID5 provides higher performance and betterreliability without the need of a single bottleneck disk (RAID4) and lower costscompared to RAID01 (4 disks). (1 P)

Question 10

Wir haben in der Vorlesung vier Dateiallokationsstrategien kennengelernt. Nennen Sie diese Strategien. Die Metadaten des Dateisystems wurden beschädigt. Die Dateidaten sollen wiederhergestellt werden. Nehmen Sie an, dass wenigstens der Beginn einer Datei durch eine Dateitypanalyse identifiziert werden kann. Welche Allokationsstrategien sind für dieses Szenario am wenigsten geeignet und warum? (3 pt) We have described four file allocation strategies in the lecture. Name these strategies. The metadata of the file system has been corrupted. The file data should be recovered. Assume that at least the beginning of a file can be determined by a file type analysis. Which of the allocation strategies are least suitable for this scenario? Explain why.

Accepted Answer

(A) Indexierte Zuordnung (0,5 P), (b) Dateizuordnungstabelle (0,5 P), (c) Verkettete Zuweisung (0,5 P) und (d) zusammenhängende Zuordnung. (0,5 P)Indizierte Zuordnung (mit hoher Fragmentierung) und FAT, da die Datei rekonstruiert wirdsind Daten am Anfang nicht ausreichend (im schlimmsten Fall bekommst du nur den ersten Block der Datei). Die Indextabellen sind ebenfalls erforderlich. Das ist bei Verketteter oder zusammenhängender zuordnung nicht der Fall . (1.0 P) Allerdings ist es nicht immer möglich, das genaue Dateigröße direkt durch interne Fragmentierung zu bekommen.(a) Indexed Allocation (0.5 P) , (b) File Allocation Table (0.5 P) , (c) Chained Allocation(0.5 P) , and (d) Contiguous Allocation. (0.5 P)Indexed allocation (with high fragmentation) and FAT, because to reconstruct the filedata the beginning of a file is not sufficient (in the worst case, you only get the firstblock of the file). The index tables are also needed. This is not the case with chainedor contiguous allocation. (1.0 P) However, it is not always possible to get the exactfile size, due to internal fragmentation.

Question 11

Nennen Sie die drei grundlegenden I/O-Techniken. Welche Technik wird für Festplatten und SSDs verwendet und warum? (2 pt) Name the three basic I/O techniques. Which one is used for harddisks and SSDs, and why?

Accepted Answer

Programmierte I / O / Wahl (0,5 P) Interruptgesteuerte I / O (0,5 P) Direkter Speicherzugriff (DMA) (0,5 P) DMA wird typischerweise von SSDs und HDDs verwendet, da es erlaubt, Daten Bei hohem Durchsatz und bei geringer CPU-Auslastung zu übertragen (0,5 P)Programmed I/O / Polling (0.5 P) Interrupt-driven I/O (0.5 P) Direct Memory Access(DMA) (0.5 P) DMA is typically used by SSDs and HDDs, as it allows to transfer dataat high throughput with low CPU utilization.(0.5 P)

Question 12

Für Solid State Disks (SSDs) wurde ein neuer Befehl in die Schnittstellen zu Hintergrundspeichern eingeführt. Wie lautet dieser Befehl und wann sollte ein Dateisystem ihn ausführen? Welche zwei Vorteile bietet dieser Befehl aus Sicht der SSD? (3 pt) For Solid State Disks (SSDs) a new command has been introduced to the background storage interface. What is its name and when is it executed? Name two advantages of this command from the perspective of an SSD!

Accepted Answer

trim (0,5 P) sollte aufgerufen werden, wenn irgendwelche Plattenblöcke freigegeben werden, das heißt, wenn eine Datei gelöscht oder gekürzt wird (0,5 P).Unbenutzte logische Blocks ​​müssen bei einem SSD-Block nicht neu geschrieben werden (vermeidet Schreibvergößerung) (1 P)Unbenutzte logische Blöcke erhöhen den Pool von Ersatz-SSD-Blöcken (0,5 P) nach der MüllSammlung (0,5 P)trim (0.5 P) should be called whenever any disk blocks are freed, that is, when afile is deleted or truncated (0.5 P) .Unused logical blocks do not have to be copied in case of a SSD block re-write (avoidsWrite Amplification) (1 P)Unused logical blocks increase the pool of spare SSD blocks (0.5 P) after garbagecollection (0.5 P)

Question 13

Gegeben ist ein Dateisystem, das die Belegung von Blocken mit einer verketteten Liste im Speicher verwaltet. Der aktuelle Zustand dieser Liste auf der Festplatte sei in Tabelle 1 angegeben. Ein Verzeichnis enthält die Einträge {”foo”:3, ”bar”:7}. Welche Blocke enthalten die Inhalte der Dateien foo und bar? (2 pt) Imagine a file system with linked list allocation in memory. The current state of that list on disk is given below in Table 1. The current directory contains the entries {”foo”:3, ”bar”:7}. Which disk blocks contain the contents of the files foo and bar, respectively? Table 1 Block Link 0 1 1 5 2 3 1 4 -1 5 4 6 7 -1

Accepted Answer

foo: 3, 1, 5, 4 (1 P) bar: 7 (1 P)

Question 14

a)Gegeben ist ein Dateisystem, das die Belegung von Blöcken mit einer verketteten Liste im Speicher verwaltet. Der aktuelle Zustand dieser Liste auf der Festplatte ist in Tabelle 1 angegeben. Ein Verzeichnis enthält die Einträge {”foo”:3, ”bar”:7}. Welche Blöcke enthalten die Inhalte der Dateien foo und bar? (2 pt) Imagine a file system with linked list allocation in memory. The current state of that list on disk is given below in Table 1. The current directory contains the entries {”foo”:3, ”bar”:7}. Which disk blocks contain the contents of the files foo and bar, respectively? Table 1 Block Link 0 1 1 5 2 3 1 4 -1 5 4 6 7 -1 b)Ein weiteres Verzeichnis im oben beschriebenen Dateisystem enthält einen Eintrag ”punkteliste.txt”:0. Was ist daran problematisch? Wie kann der Einsatz eines Buffer Cache zu dieser Situation fuhren? (2 pt) Another directory in the file system described above contains an entry ”punkteliste.txt”:0. What is the issue with that entry? How can the use of a buffer cache lead to that situation?

Accepted Answer

a)foo: 3, 1, 5, 4 (1 P) bar: 7 (1 P)b)Die Datei punkteliste.txt scheint einige der Blöcke der Datei foo zu enthalten, was ein Inkonsistenter Dateisystemzustand ist(1 P).Änderungen am Dateisystem werden zuerst in den Puffer-Cache geschrieben. Anscheinend wurde der Eintrag für Block 0 in der verknüpften Zuordnungsliste im Speicher geändert aber noch nicht auf der Festplatte (1 P).Wenn das System abstürzt (z. B. Stromausfall), bevor alle Änderungen auf die Festplatte geschrieben wurden, kann das Dateisystem in einem inkonsistenten Zustand sein, wenn es während eines Neustartes montiert wird (alternative Antwort).The file punkteliste.txt appears to contain some of the blocks of file foo, which is aninconsistent file system state (1 P) .Modifications to the file system get written to the buffer cache first. Apparently, theentry for block 0 in the linked allocation list has been changed in memory but not yeton disk (1 P) .When the system crashes (e.g., power failure) before all the changes are written backto disk, the file system can be in an inconsistent state when it is mounted during areboot (alternative answer).

Question 15

Welche der folgenden Informationen findet sich üblicherweise (a) in der inode, (b) im Verzeichnis, oder (c) in der Datei? (Pro Zeile ist genau eine Antwort richtig) (2 pt) Which information is typically stored in (a) the inode, (b) the directory, or (c) the file? (In each line, there is exactly one correct answer) Inode/ Verzeichnis/ Datei/ Inode Directory File Dateiname file name Anzahl der Hardlinks number of hard links Magische Zahl für den Dateityp magic number for the file type Zugriffsrechte access rights

Accepted Answer

Inode/ Verzeichnis/ Datei/Inode Directory File X Dateiname file name Anzahl der Hardlinks X number of hard links X Magische Zahl für den Dateityp magic number for the file type Zugriffsrechte X access rights

Question 16

a) In Linux besteht die Oktalnotation der Zugriffsrechte aus 4 Ziffern. Zählen Sie auf, wofür die 4 Ziffern jeweils stehen (nicht welche Werte sie annehmen können). (2 pt) b) Wofür stehen die Werte, die die hinteren drei Ziffern annehmen können, in Bezug auf reguläre Dateien und in Bezug auf Verzeichnisse? (Konzentrieren Sie sich auf die Zweierpotenzen.) a) In Linux, the octal notation for access rights consists of 4 digits. List what these 4 digits stand for (not which values they can hold). b) What do the possible values of the last three digits represent, for both, regular files and for directories? (Focus on the powers of two.)

Accepted Answer

a)• Spezial (0,5P)• Benutzer (0.5P)• Gruppe (0,5P)• Andere (0,5P)• Special (0.5P)• User (0.5P)• Group (0.5P)• Other (0.5P)b) • Dateien: - ausführen (0,5P) - schreiben (0,5P) - lesen (0.5P)• Verzeichnisse: - Verzeichnis eingeben (0.5P) - Dateien erstellen, löschen, umbenennen (0.5P) - Dateien auflisten (0.5P)• Files: – execute (0.5P) – write (0.5P) – read (0.5P)• Directories: – enter directory (0.5P) – create, delete, rename files (0.5P) – list files (0.5P)

Question 17

a) rsnapshot ist eine Anwendung, um über die Zeit mehrere vollständige Abbilder von Verzeichnisstrukturen zum instantanen Zugriff zu erstellen (z.B. in Ordern mit “gestern”, “letzte woche”). Beschreiben Sie einen Vorteil für die Nutzung von Hardlinks gegenüber Softlinks, um dies umzusetzen. (1 pt) b) Welche Strukturen müssen auf Dateisystemebene zusätzlich angelegt werden, um ein neues Abbild anzulegen? Gehen Sie davon aus, dass es keine Änderungen seit dem letztem inkrementellen Abbild gab. (1 pt) Which structures have to be created on file system level to take a new snapshot? Assume that there where no changes since the last incremental backup. a)Let rsnapshot be a filesystem snapshot utility for making it possible to keep multiple backups of directory structures instantly available (e.g., in folders like “yesterday”, “last week”). Explain briefly one advantage of using hardlinks instead of softlinks for implementing this. b)Which structures have to be created on file system level to take a new snapshot? Assume that there where no changes since the last incremental backup.

Accepted Answer

a) • Erste und konsequente Backups können sicher gelöscht / umbenannt werden. . . (1P). . .• First and consequtive backups can be safely deleted/renamed . . . (1P)• . . .b)• So wie harte Links einfach Verzeichniseinträge sind, die einem Namen nur einem Inode zuordnen, muss die Verzeichnisstruktur dupliziert werden. Harte Links sind Dateieinträge zu den Dateien in der vorherigen Sicherung. (1P)b)• As hard links are simply directory entries that map a name to an inode, onlythe directory structure has to be duplicated and file entries are hard links to thefiles in the previous backup. (1P)

Question 18

rsnapshot basiert auf rsync. rsync identifiziert identische Teile zwischen Quell und Zieldatei und versucht nur die modifizierten Teile zu kopieren. Dies basiert auf einer rollenden Prüfsumme. Beschreiben Sie die Eigenschaft einer rollenden Prüfsumme. (1 pt) rsnapshot is based on rsync identifies identical parts between source and destination file, and tries to copy only the modified parts. This is based on a rolling checksum. Describe the property of a rolling checksum.

Accepted Answer

• Die Prüfsumme kann inkrementell berechnet werden. (1P)• The checksum can be incrementally computed. (1P)

Question 19

Welches sind die zwei Ziele von RAID, und durch welche Konzepte werden diese umgesetzt? (2 pt) What are the two goals of RAID, and what are the concepts to implement them?

Accepted Answer

• Verbessern Sie die Leistung (0,5P) und die Zuverlässigkeit (0,5P) von Single Large Expensive Disks (SLED) mit redundanten Arrays von preiswerten / unabhängigen Disks (RAID)• RAID bietet I / O-Parallelität (Striping) (0.5P) und Redundanz (Spiegelung, Parität) (0,5P)• Improve performance (0.5P) and reliability (0.5P) of Single Large Expensive Disks (SLED) using Redundant Arrays of Inexpensive/Independent Disks (RAID)• RAID provides I/O parallelism (striping) (0.5P) and redundancy (mirroring, parity) (0.5P)

Question 20

a) Sie erstellen eine Datei a, einen Hardlink b auf diese Datei und einen symbolischen Link auf a, den Sie c nennen. Was sind die Dateirechte von a, b und c, in rwx Notation, nach allen folgenden Shell-Befehlen? (3 pt) b)Was ändert sich an b und c, wenn a gelöscht wird? (1 pt) a) You create a file a, a hardlink b to this file, and a symbolic link to a, called c. What are the file permissions of a, b, and c in rwx notation, after executing all of the following shell commands? b) How do b and c change when a is deleted?

Accepted Answer

a)chmod 670 achmod 123 bchmod 456 cDatei/File Dateirechte in rwx Notation/File permissions in rwx notation a - - x - w - - w x b - - x - w - - w x c r- - r - x r w - b)• b Linkzähler wird dekrementiert• c Keine Änderung, nur Linkziel verschwindet• b Link counter is decremented• c No change, only link target disappears

Question 21

Was ist anonymer Speicher? Nennen Sie zwei mögliche Quellen. (2 pt) What is anonymous memory? Enumerate two possible sources.

Accepted Answer

Anonymer Speicher ist Speicher, der nicht durch eine Datei unterstützt wird. Z.B. der Haufen oder das Stapelsegment eines Prozesses.Anonymous memory is memory that is not backed by a file. E.g., the heap or thestack segment of a process.

Question 22

Wie wird benannter (nicht-anonymer) Speicher beim Swapping behandelt? (1 pt) How is named (non-anonymous) memory treated when swapping?

Accepted Answer

Beim Austauschen kann der benannte Speicher gelöscht werden, wenn er nicht geändert wurde. Andernfalls wird in die ursprüngliche Datei geschrieben, anstatt in den Swap-Space.When swapping, named memory may be dropped if it has not been modified. Otherwiseit is written back to the original file instead of being written to the swap space.

Question 23

Mit dem Programm fsck konnen unter Unix Dateisystemfehler gefunden und behoben werden. Geben Sie für die folgenden Fehlermeldungen an, was fsck im inkonsistenten Dateisystem gesehen haben könnte um auf den Fehler zu schließen. a) Der Inode Linkzähler ist 1, er sollte 2 sein.(2 pt) b) Der Frei-Bitmap Eintrag fur Block 1234 ist 0 (frei), er sollte 1 sein (belegt). Unix file systems can be checked and fixed with the fsck program. What could fsck have seen to generate the following error messages in an inconsistent file system. a) The inode link count is 1, it should be 2. b) The free-bitmap entry for block 1234 is 0 (free), it should be 1 (allocated).

Accepted Answer

a) Ein zweiter Verzeichniseintrag wurde zu einem Inode mit Linkzählung 1 gefunden.a) A second directory entry has been found to an inode with link count 1.b) Ein Inode-Eintrag zeigt auf einen Block, der nicht zuzuordnen ist.b) An inode entry points to a block which is not marked to be allocated.

Question 24

Wir haben in der Vorlesung drei Dateiallokationsstrategien kennengelernt: (a) Indexed allocation, (b) chained allocation und (c) contiguous allocation. Geben Sie für die folgenden Szenarien an, wie gut die Strategien jeweils geeignet sind und warum. (3 pt) a) Schneller wahlfreier Zugriff auf sehr große Dateien. b) Ausnutzung der Festplattenkapazitat (Speichern möglichst vieler Datei-Bytes). We have described three file allocation strategies in class: (a) Indexed allocation, (b) chained allocation, and (c) contiguous allocation. Describe how well the three strategies perform in each one of the following scenarios. Explain why. a) Fast random access to very large files. b) Utilization of the disk capacity (storage of as many file-bytes as possible). Die Frage kommt mehrmals vor!!!!!!!!!!!

Accepted Answer

a)Contiguous allocation/Zusammenhängende Zuordnung : Am besten, sehr einfache Index-Berechnung ohne indirekteZugriffeIndexed allocation/Indexierte Zuordnung: Sehr gut, einfaches Finden des richtigen Blocks mithilfe des Indizes.Chained allocation/Verkettete Zuordnung: Schlecht, lineares durchsuchen der Kette zum Finden des korrekten Blocks. b)Chained allocation: Sehr gut, keine externe Fragmentierung, kleine Datenstrukturen.Indexed allocation: Sehr gut, keine externe Fragmentierung, minimal großere Daten- ¨strukturen als bei Chained allocation.Contiguous allocation: Schlecht, entweder externe Fragmentierung oder compactionnotig.

Question 25

Was versteht man unter Logical Block Adressing (LBA) zur Adressierung von Festplattensektoren? Nennen Sie einen Vor- und einen Nachteil gegenüber Cylinder Head Sector (CHS) Adressierung. Begründen Sie Ihre Antwort. (2 pt) Explain the term logical block addressing (LBA) to address disk sectors. Give one advantage and one disadvantage compared to cylinder head sector (CHS) addressing. Explain your answer.

Accepted Answer

LBA (Logical Block Addressing) behandelt die gesamte Platte als ein einziges Array von Blöcken (1 P).Dies ist heute die vorherrschende Technik, weil es versteckt Disk-geometrie-Details undvereinfacht damit den Zugriff (0,5 P). Allerdings machtes LBA schwierig für Betriebssysteme Disk-Zugriffe zu optimieren (z. B. um die Suchzeiten zu minimieren), weil die physische Platzierung der Sektoren auf der Platte unbekannt ist(0,5 P).LBA (Logical Block Addressing) treats the whole disk as a single array of blocks (1 P).It is the prevalent technique today, because it hides disk geometry details and thussimplifies access (0.5 P). However, LBA makes is difficult for operating systems tooptimize disk accesses (e.g., to minimize seek times), because the physical placementof sectors on the disk is unknown (0.5 P).

Question 26

Ein Verbund aus vier Festplatten kann für unterschiedliche RAID Level konfiguriert werden. Wie viele Festplatten können in der jeweiligen Konfiguration ausfallen, bevor Daten endgültig verloren gehen? Begründen Sie jeweils Ihre Antwort. (4 pt) An array of four hard disks can be configured for different RAID levels. How many disks can fail in each configuration before data is permanently lost? Explain your answer.

Accepted Answer

RAID 0: 0 (0,5 P), Strippen, keine Redundanz (0,5 P).RAID 1: 3 (0,5 P), Spiegelung, alle Platten enthalten identischen Inhalt (0,5 P).RAID 4: 1 (0,5 P), Daten werden auf 3 Festplatten gespeichert, Paritätsinformationen werden separat Festplatte gespeichert, so ist die Rekonstruktion nur möglich, wenn ein Datenträger ausfällt (0,5 P).RAID 5: 1 (0,5 P), wie RAID 4, aber Paritätsinformationen sind über alle Disks verteilt.RAID 0: 0 (0.5 P), stripping, no redundancy (0.5 P).RAID 1: 3 (0.5 P), mirroring, all disks contain identical contents (0.5 P).RAID 4: 1 (0.5 P), data is stored on 3 disks, parity information is stored on a separatedisk, thus reconstruction is only possible if one disk fails (0.5 P).RAID 5: 1 (0.5 P), same as RAID 4, but parity information is distributed across alldisks (0.5 P).

Question 27

Moderne Betriebssysteme verwenden für SSDs den trim-Befehl. Warum wird dieser Befehl nicht für HDDs verwendet? (1 pt) Modern operating systems use the trim command for SSDs. Why is this command not used for HDDs?

Accepted Answer

Im Gegensatz zu SSDs müssen HDDs keine Daten freigeben und explizit löschen bevorRaum überschrieben oder wiederverwendet werden kann.In contrast to SSDs, HDDs do not require to release and explicitly erase data beforethe space can be overwritten or reused.

Question 28

Nennen Sie vier Metadaten, die das Betriebssystem für eine geöffnete Datei halten muss. Welche der Informationen werden Systemweit nur einmal, welche pro geöffneter Instanz gespeichert? (2 pt) Give four pieces of metadata that the operating system has to store for an open file. Which information is stored once per system and which once per open file instance?

Accepted Answer

Pro System: File-Open-Zähler (0,5 P), Informationen über Cache-Datei-Teile (0,5 P)Pro Instanz: Zugriffsmodus (0,5 P), Dateizeiger (0,5 P)per system: file-open counter (0.5 P), information on cached file parts (0.5 P)per instance: access mode (0.5 P), file pointer (0.5 P)

Question 29

Erläutern Sie Unterschiede in der Implementierung von harten und symbolischen Links. Geben Sie jeweils ein Verwendungsbeispiel an. (3 pt) Explain the implementation differences of hard and soft links. Give a usage example for each.

Accepted Answer

Während harte und weiche Links beide einen dedizierten Verzeichniseintrag erhalten, teilen harte Links der gleichen Datei den gleichen Inode (0,5 P). Das Erstellen eines neuen Hardlinks erhöht nur ein Referenzzähler im Inode (0,5 P). Harte Links können für inkrementelle Backups verwendet werden (0,5 P).Auf der anderen Seite sind Soft Links regelmäßige Dateien (0,5 P), mit einem absoluten oderrelativen Pfad zum Ziel (0,5 P). Ein Verzeichnis kann auf einen anderen Datenträger oder Dateisystem verschoben werden, kann aber noch von der ursprünglichen Position (0,5 P) abgerufen werden.While hard and soft links both get a dedicated directory entry, hard links of thesame file share the same inode (0.5 P). Creating a new hard link only increments areference counter in the inode (0.5 P). Hard links can be used for incremental backups(0.5 P).Soft links, on the other side, are regular files (0.5 P) that contain the absolute orrelative path to the destination (0.5 P). A directory can be moved to another disk orfile system, but can still be accessed from the original location (0.5 P)

Question 30

Betrachten Sie ein System, das an ein sehr schnelles Netzwerk angeschlossen ist. Jedes ankommende Paket löst einen Interrupt aus. Welches Problem kann beim Empfang vieler kleiner Pakete auftreten? (2 pt) Consider a system that is connected to a very fast network. Each arriving packet triggers an interrupt. What problem can arise while receiving many small packets?

Accepted Answer

Die Handhabung eines Interrupts verursacht Overhead. Die CPU muss den aktuellen Ausführungskontext speichern und betritt das Betriebssystem (unter anderem CPU-interne Aktivität). Zusätzlich muss der Kontext der Benutzerebene nach der Bearbeitung des Interrupts wiederhergestellt werden. (1 P)Der Empfang vieler kleiner Pakete kann die CPU überladen, was zu verlust von Paketen führen kann. (1 P)Handling an interrupt causes overhead. The CPU needs to save the current executioncontext and enter the operating system (amongst other CPU-internal activity). Inaddition, the user-level context has to be restored after processing the interrupt. (1 P)The reception of many small packets can overload the CPU which can result in packetsbeing lost. (1 P)

Question 31

Welche alternative I/O-Technik wurde diese Situation verbessern und warum? (1 pt) Which other I/O technique would improve that situation? Why?

Accepted Answer

Das Wählen, da kein Overhead von der Interrupt-Handhabung. (1 P)Polling, because no overhead of interrupt handling. (1 P)

Question 32

Welches ist der Hauptunterschied zwischen Festplatten (HDDs) und Solid State Disks (SDD) in Bezug auf die Zugriffscharakteristik? Was sind die Auswirkungen hiervon für den Entwurf von Dateisystemen? (2 pt) What is the main difference in access characteristics between hard disk drives (HDDs) and solid state disks (SSDs)? What are the implications on file system design?

Accepted Answer

SSDs bieten einen hohen Durchsatz für kleine Anfragen an zufälligen Orten (0,5 P), währendHDDs nur Spitzenbandbreite für sequentielle Lese- / Schreibvorgänge nacheinander erreichen. (0,5 P)(Alternative: SSDs müssen möglicherweise große Blöcke intern neu schreiben, auch wenn die Datensystem nur wenige kleine Sektoren schreibt. (0,5 P))Dateisysteme, die typischerweise darauf abzielen, Dateien auf der Festplatte in Chunks so nah wie möglich zusammen zuzuordnen, um diese idiosyncracy von HDDs zu empfangen. (0,5 P) Das Design-Ziel hat für SSDs das meiste seiner Bedeutung verloren. (0,5 P)SSDs provide high throughput for small requests at random locations (0.5 P) whereasHDDs only achieve peak bandwidth for sequential reads/writes of data placed consecutively.(0.5 P)(Alternative: SSDs may need to rewrite large blocks internally even when the filesystem writes only a few small sectors. (0.5 P) )File systems typically aimed at allocating files on disk in as few chunks located asclosely together as possible to accomodate for that idiosyncracy of HDDs. (0.5 P) ForSSDs, that design goal has lost most of its importance. (0.5 P)

Question 33

) In einem i-node-basierten Dateisystem bietet jeder i-node Platz bis zu fünf LBA- Zeiger auf 4 KiB große Festplatten-Blöcke. Wie muss man diese Block-Zeiger einsetzen um eine maximale Dateigröße von 2 MiB bei minimalem Speicherverbrauch zu unterstützen? I-nodes belegen 512 B, jeder Block-Zeiger ist 8 B lang. (3 pt) Consider an i-node based file system that stores up to five LBA pointers in each inode, each of which refers to a 4-KiB disk block. How do you have to utilize these pointers to support a maximum file size of 2 MiB using a minimum of disk space? Each i-node is 512 B in size, block pointers are 8 B long

Accepted Answer

Direkt referenzierende Blöcke im i-Knoten würden nur Dateien von Größe 5 * 4 KiB = 20 KiB erlauben.So ist eine Indirektion erforderlich: Die Zeiger im i-Knoten beziehen sich auf Plattenblöcke, die selbst blockieren können(0,5 P)Wir können die erforderlichen Indirektionsniveaus auf der Grundlage des maximal erforderlichen Bedarfs der Dateigröße bestimmen, die Länge der Zeiger und die Größe jedes Plattenblocks.Das Dateisystem arbeitet mit Plattenblöcken von 4 KiB Größe. So kann jeder indirekte Block4 KiB = 4096 B = 512 Zeiger speichern. (0,5 P) 64 Bits 8 BEin einzelner indirekter Block kann die benötigten 512 * 4 KiB = 2 M iB adressieren. Mit den anderen vier Zeigern für direkte Blöcke sichert Speicherplatz für kleine Dateien. (1 P)So benötigen wir eine Ebene der Indirektion bei der Adressierung von Dateiblöcken. (0,5 P)Die fünf Blockzeiger im i-Knoten könnten wie folgt verwendet werden: Vier direkte Blöcke(Speicherplatz für kleine Dateien) und einen einzigen indirekten Block. (0,5 P)Directly referencing blocks in the i-node would only allow files of size 5∗4 KiB = 20 KiB.Thus, indirection is required: The pointers in the i-node refer to disk blocks that containdisk blocks themselves. (0.5 P)We can determine the required levels of indirection based on the maximum requiredfile size, the length of pointers, and the size of each disk block.The file system operates with disk blocks of 4 KiB size. Thus, each indirect block canstore 4 KiB = 4096 B = 512 pointers. (0.5 P) 64 bits 8 B A single indirect block can address the required 512 ∗ 4 KiB = 2 M iB. Using the otherfour pointers for direct blocks saves storeage space for small files. (1 P)Thus, we require one level of indirection in addressing file blocks. (0.5 P)The five block pointers in the i-node could be used as follows: Four direct blocks(saving space for small files), and one single-indirect block. (0.5 P)

Question 34

Wie viel Speicherplatz wird in obigem Dateisystem insgesamt benötigt, um eine 8 KiB große Datei abzulegen? Wie viel für eine 20 KiB große Datei? Beschreiben Sie Ihren Rechenweg. Ignorieren Sie Verzeichniseinträge. (2 pt) How much disk space in total is required to store a file of 8 KiB size in the file system discussed above? How much for a 20 KiB file? Describe how you arrived at your solution. Ignore directory entries.

Accepted Answer

Eine 8-KiB-Datei benötigt zwei Datenblöcke (jeweils 4 KiB) und 512 B für den i-Knotenin 2 * 4 KiB + 512 B = 8,5 KiB. (1 P)Eine 20-KiB-Datei benötigt 5 Datenblöcke (20/4 = 5), von denen wir vier direkt an den Blockzeiger verweisen können. Für den fünften Datenblock müssen wir einen indirekten Block zuordnen. Wi benötigen 5 * 4 KiB für Daten +4 KiB für den indirekten Block +512 B für den Inode,Was zu 24,5 KiB erforderlichen Speicherplatz führt. (1 P)An 8 KiB file requires two data blocks (4 KiB each), and 512 B for the i-node, resultingin 2 ∗ 4 KiB + 512 B = 8.5 KiB. (1 P)A 20 KiB file requires 5 data blocks (20/4 = 5), four of which we can refer in directblock pointers. For the fifth data block, we have to allocate an indirect block. Thus,we require 5 ∗ 4 KiB for data +4 KiB for the indirect block +512 B for the inode,resulting in 24.5 KiB required storage space. (1 P)

Question 35

Können harte Links und/oder symbolische Links verschiedene Dateisysteme überspannen? Warum/warum nicht? (2 pt) Can hard links and/or symbolic links span different file systems? Why/why not?

Accepted Answer

Harte Links: nein (0,5 P) Ein Hardlink verweist auf einen Inode (nach Inode-Nummer). Inodessind eine Dateisystem-lokale Entität, so dass Inode-Nummern nur innerhalb eines Dateisystems eindeutig sind. (0,5 P)Symbolische Links: ja. (0,5 P) Symbolische Links verweisen auf einen VFS-Pfad und sind somit nicht verwandt mit dem zugrunde liegenden FS. (0,5 P)Hard links: no. (0.5 P) A hardlink references an inode (by inode number). Inodesare a file system local entity, so inode numbers are unique only within a file system.(0.5 P)Symbolic links: yes. (0.5 P) Symbolic links reference a VFS path and are thus unrelatedto the underlying FS. (0.5 P)

Question 36

Wir haben in der Vorlesung drei Dateiallokationsstrategien kennengelernt: (a) Indexed Allocation, (b) Chained Allocation und (c) Contiguous Allocation. Sortieren Sie die Strategien nach der Reihenfolge ihrer Eignung in den folgenden Szenarien. Begründen Sie für jede Strategie kurz, warum sie sich eignet/nicht eignet.3 pt a) Schnelles Auslesen aufeinanderfolgender Blöcke einer Datei. b)Effiziente Datenspeicherung durch wenig Metadaten. Gehen Sie davon aus, dass der Speicher unfragmentiert ist. We have discussed three file allocation strategies in the lecture: (a) indexed allocation, (b) chained allocation, and (c) contiguous allocation. Order the strategies based on how well they perform in each of the following scenarios. Provide a short explaination why each strategy performs well/bad. a)Fast reading of consecutive blocks of a file. b)Efficient storage of data in terms of few metadata. Assume that the memory is defragmented.

Accepted Answer

a)(A) zusammenhängende Zuordnung: Am besten, da Blöcke einer Datei direkt zusammenhängen. (+ 0,5P)(B) Indizierte Zuordnung: Schlechter, da Blöcke einer Datei nicht direkt zusammenhängen müssen (+ 0,5P)(C) Verkettete Zuordnung: Noch schlechter, da nächste Blockadressen erst berechnet werden nachdem ein aktueller Block geladen wurde. (+ 0,5P)b)(a) Contiguous allocation/ Zusammenhängende Zuordnung: Am besten, da nur eine Anfangsadresse und eine Längeninformation für die Datei gespeichert werden muss. (+0.5P)(b) Chained allocation/Verkettete Zuordnung: kleine Datenstrukturen nur Pointer am Ende von Blöcken. (+0.5P)(c) Indexed allocation/Indizierte Zuordnung: größere Datenstrukturen als bei Chained allocation (IndexStruktur und Block-Pointer). (+0.5P)

Question 37

Welche Metadaten einer Datei sind notwendig, wenn Chained Allocation zur Reservierung von Plattenspeicher verwendet wird? (1 pt) Which metadata of a file are necessary if chained allocation is used to allocate disk space?

Accepted Answer

• Anfangsadresse des ersten Blocks (+0.5P)• Jeweils die Adressen des nächsten Blöcke (+0.5P)

Question 38

Gegenüberstellung von absoluten und relativen Pfadnamen: geben Sie ein Beispiel an, dass absolute Pfadnamen für den Zugriff auf eine Datei weniger Festplattenzugriffe erfordern als relative, und ein weiteres Beispiel für den umgekehrten Fall. Gehen Sie davon aus dies sei ihr Current Working Directory: /home/user1/ (2 pt) Comparison of absolute and relative pathnames: provide an example in which more disc accesses are needed to access a file when using absolute pathnames instead of a relative ones, and provide another example to illustrate the opposite case. Assume the following is your current working directory: /home/user1/

Accepted Answer

Absolute faster than relative path:• /home/user1/somefile ←→ ../../../../home/user1/somefile (+1P)Relative faster than absolute path:• somedir/somefile ←→ /home/user1/somedir/somefile (+1P)

Question 39

Sie haben ein RAID1 aus zwei Festplatten. Die Platten rotieren mit 1200 RPM, bestehen aus Spindeln von je 8 Platten, besitzen 16 Köpfe, haben eine Sektorgröße von 512 Bytes und haben 50 Sektoren auf jeder Spur. Für beide Platten beträgt die durchschnittliche Zeit eine Spur zu fokussieren 10ms und die durchschnittliche Verzögerung um zu einem Sektor auf einer ihrer Spuren zu rotieren 5ms. Gehen Sie davon aus, dass in einer Festplatte zu einer Zeit nur ein Kopf aktiv (lesen oder schreiben) sein kann. a)Geben Sie die maximale Übertragungsrate an mit der Sequenzen von zufällig ausgewählten Sektoren beschrieben werden können. Nehmen Sie an, dass sich jeder Sektor einer zufälligen Sequenz auf einer anderen Spur befindet. (2P) b)Wie würde sich die maximale Übertragungsrate verändern, wenn beide Platten in einem RAID0 angeordnet wären? Begründen Sie Ihre Antwort kurz. 1 pt You have two hard disk drives in a RAID1 setup. The disks spin at 1200 RPM, have spindles of 8 platters, 16 heads, a sector size of 512 bytes and hold 50 sectors per track. The average time to seek a track on each disk is 10ms, and the average delay to rotate to a sector on their tracks is 5ms. Assume that only one head per hard disk drive can be active (reading or writing) at a time. a)Provide the maximum transfer rate at which sequences of randomly selected sectors can be written. Assume that each sector in the random sequence is on a different track. b)How would the maximum transfer rate change if both disks were arranged in a RAID0? Explain your answer briefly.

Accepted Answer

a) • Jede Übertragung schreibt 512 Bytes auf beide Festplatten, was 1 = 1ms dauert.(+ 1P) 1200 U / min * 50 Sektoren 60s• Jede Übertragung beinhaltet eine durchschnittliche Suchzeit von 10ms und eine durchschnittliche Rotationsverzögerung von 5ms. (+ 0,5P)• Deshalb bedienen wir die Sequenzen bei 1 * 512 Bytes = 32.000B / s. (+ 0,5P) 1ms + 10ms + 5msa)• Each transfer writes 512 bytes to both disks, which takes 1 = 1ms(+1P) 1200rpm ∗50sectors 60s • Each transfer involves an average seek time of 10ms and an average rotationaldelay of 5ms. (+0.5P)• Therefore, we service the sequences at 1 ∗ 512 bytes = 32.000B/s. (+0.5P) 1ms+10ms+5msb) • Jede Übertragung schreibt nur 512 Bytes auf eine Festplatte, daher können wir zwei parallel-schreibende bedienen (+ 0,5P)• Deshalb bedienen wir die Sequenzen bei 2 * 32.000B / s = 64.000B / s. (+ 0,5P)b)• Each transfer writes 512 bytes to one disk only, therefore we can service twowrites in parallel. (+0.5P)• Therefore, we service the sequences at 2 ∗ 32.000B/s = 64.000B/s. (+0.5P)

Question 40

Zählen Sie drei verschiedene RAID-Architekturen auf und nennen Sie die Eigenschaften durch welche Redundanz und Performance verbessert werden. Kombinierte Architekturen, wie z.B. RAID 0+1, sind ausgeschlossen. (3 pt) Enumerate three different RAID architectures and name the features by which redundancy and performance are improved. Combined architectures, such as RAID 0+1, are excluded.

Accepted Answer

RAID Redundancy PerformanceRAID Redundanz Performanz RAID0 n / a Block-Level-Striping und nicht synchronisierte Spindeln machen paralleles einlesen und schreiben möglich RAID1 Spiegeln Gespiegelte Blöcke und nicht synchronisierte Spindeln machen nur paralleles Lesen möglich RAID2 Fehler-korrigierender Bit-Level-Striping und synchronisierte Code auf extra Spindeln beschränken sich zwar auf Festplatten ein paralleles lesen / schreiben, aber bieten dafür einen hohen Durchsatz RAID3 Byte-Level-Parität auf Byte-Level-Striping und synchronisierte spindeln Extra parity disk beschränken sich zwar auf paralleles Einlesen / schreiben, bieten aber eine hohe Verarbeitungsmenge RAID4 Block-Level-Parität auf Block-Level-Striping und nicht synchronisierte zusätzlicher Paritäts-disk spindeln bieten paralleles Einlesen RAID5 Verteilte Block-Level- Block-Level-Striping und nicht synchronisierte Parität Spindeln bieten paralleles Einlesen RAID Redundancy PerformanceRAID Redundanz Performanz RAID0 n/a Block-level striping and nonsynchronized spindles offers parallel reads and writesRAID1 Mirroring Mirrored blocks and non synchronized spindles offers parallel reads onlyRAID2 Error-correcting Bit-level striping and synchronized code on extra disks spindles restricts to one parallel read/write, but offers high throughputRAID3 Byte-level parity on Byte-level striping and synchronized extra parity disk spindles restricts to one parallel read/write, but offers high throughputRAID4 Block-level parity on Block-level striping and nonsynchronized extra parity disk spindles offers parallel readsRAID5 Distributed block-level Block-level striping and nonsynchronized parity spindles offers parallel reads

Question 41

Beschreiben Sie die Unterschiede zwischen kurzfristigem (short-term) und langfristigem (long-term) Scheduling. (1 pt) Describe the differences between short-term and long-term scheduling.

Accepted Answer

Der langfristige Scheduler - oder Job Scheduler - wählt aus, welche Prozesse in die fertige Warteschlange gebracht werden sollen. Es wird eher selten aufgerufen, im Zeitrahmen von Sekunden, Minuten oder sogar Stunden. Seine Implementierung und Algorithmen können daher vergleichsweise langsam sein. Der long-term Scheduler steuert den Grad der Multiprogrammierung, der short-term Scheduler - oder CPU Scheduler - wählt aus, welcher Prozess als nächstes ausgeführt werden soll und verschickt die ausgewählten an die verfügbaren CPUs. Der short-term Scheduler wird eher häufig in der Reihenfolge von Millisekunden aufgerufen. Wirkungsgrad seiner Algorithmen und Umsetzung sind daher entscheidend für die Leistung des Betriebssystems.The long-term scheduler – or job scheduler – selects, which processes should bebrought into the ready queue. It is invoked rather infrequently, in time frames of seconds,minutes, or even hours. Its implementation and algorithms may therefore becomparatively slow. The long-term scheduler controls the degree of multiprogrammingThe short-term scheduler – or CPU scheduler – selects which process should be executednext, and dispatches the selected ones among the available CPUs. The shorttermscheduler is invoked rather frequently, in the order of milliseconds. Efficiencyof its algorithms and implementation are therefore crucial for the performance of theoperating system.

Question 42

Diskutieren Sie, warum es schwierig ist, einen Prozess-Scheduler so zu gestalten, dass er gleichzeitig die Anwendung zur Verfügung stehenden CPU-Zyklen und die Antwortzeit der Prozesse optimiert. Geben Sie ein Szenario an, in welchem es zu einem Zielkonflikt des Prozess-Schedulings kommen kann. (2 pt) Discuss why it is difficult to design a process scheduler that simultaneously optimizes both the amount of CPU cycles that are usable in applications and the process response time. Devise a scenario where a conflict of interest may arise for the process scheduler.

Accepted Answer

Um die CPU-Auslastung zu optimieren, kann ein Scheduler danach streben, den Overhead mit Kontextumschaltung zu minimieren. Der Kontextwechsel Overhead könnte abgesenkt werden, in dem man den Kontextwechsel unregelmäßig durchführt. Dies könnte jedoch zu einer Erhöhung der Reaktionszeit für Prozesse führen.To optimize for CPU utilization, a scheduler can strive to minimize the overhead associatedwith context switching. The context switching overhead could be lowered byperforming context switches infrequently. This could, however, result in increasingthe response time for processes.

Question 43

Gegeben sind die untenstehenden fünf Prozesse auf einem Uniprozessorsystem mit den angegebenen Ankunftszeiten (0 = Start), Burst-Zeiten und Prioritaten (1 =höchste Priorität). a) Vervollständigen Sie die untenstehenden Scheduling-Pläne für die Strategien Non-Preemptive Priority, PSJF und RR. Ein Kasten im Zeitplan stellt eine Zeitscheibe dar. (3 pt) b) Berechnen Sie für den obigen Non-Preemptive-Priority-Plan die durchschnittliche Wartezeit. c) Berechnen Sie für den obigen PSJF-Scheduling-Plan die durchschnittliche Turnaround-Zeit. Consider the five processes given below on a uniprocessor system, with given arrival times (0 = start), burst times, and priorities (1 = highest priority). a)Complete the scheduling plans given below, for the policies Non-Preemptive Priority, PSJF, and RR. A box in the scheduling plan represents one time slice. b)Calculate, for the above non-preemptive priority plan, the average waiting time. c)Calculate, for the above PSJF scheduling plan, the average turnaround time.

Accepted Answer

a)Non-Preemptive Priority/Nicht präventive Priorität 2 2 1 1 1 1 1 1 1 1 5 5 5 5 5 4 3 3 3 3PSJF2 2 3 4 3 3 3 5 5 5 5 5 1 1 1 1 1 1 1 1RR2 3 2 1 3 4 5 1 3 5 1 3 5 1 5 1 5 1 1 1b)Process Arrival Time NPP Start Time NPP Waiting Time 1 1.5 2 0.5 2 0 0 0 3 0.5 16 15.5 4 2.4 15 12.6 5 2.6 10 7.4Average Waiting Time = (0.5+0+15.5+12.6+7.4) = 36 = 7.2 5 5c)Process Arrival Time PSJF Finishing Time PSJF Turnaround Time 1 1.5 20 18.5 2 0 2 2 3 0.5 7 6.5 4 2.4 4 1.6 5 2.6 12 9.4Average Turnaround Time = (18.5+2+6.5+1.6+9.4) = 38 = 7.6 5 5

Question 44

Gegeben ist ein Uniprozessorsystem, auf welchem zehn I/O-bound Threads und ein CPU-bound Thread laufen. Die I/O-bound Threads stoßen einmal pro Millisekunde an CPU-Berechungen eine I/O-Operation an, und jede dieser I/O-Operationen benötige 10 Millisekunden zur erfolgreichen Bearbeitung. Die Kosten eines Kontextwechsels betragen ferner 0,1 Millisekunden, und alle Threads seien langlebig. Berechnen Sie den CPU Overhead in Prozent bei Benutzung eines RoundRobin Schedulers in den folgenden Fallen: (a) Eine Zeitscheibe betrage 1 Millisekunde (b) Eine Zeitscheibe betrage 10 Millisekunden (Angaben in Bruchform genügen) (3 pt) Consider a uniprocessor system running ten I/O-bound threads and one CPU-bound thread. Assume that each I/O-bound thread issues an I/O operation once for every millisecond of CPU computing and that each I/O operation takes 10 milliseconds to complete. Also assume that the context switching overhead is 0.1 millisecond and that all threads are long-running. What is the CPU overhead due to context switching in percent when using a round-robin scheduler in the following cases: (a) The time quantum is 1 millisecond (b) The time quantum is 10 milliseconds (Stating results as fractions is sufficient)

Accepted Answer

(A) Die Zeitquantum beträgt 1 Millisekunde: Unabhängig davon, welcher Thread geplant ist,der Scheduler geht für jeden Kontext eine 0.1 Millisekunden Kontextwechsel ein. Dies führt zu einem CPU-Overhead von 100 · 0,1 = 9,1 Prozent. 1.1(B) Das Zeitquantum beträgt 10 Millisekunden: Alle I / O-gebundenen Threads ergeben einen Kontextwechsel nachdem verbrauchen von nur 1 Millisekunde des Zeitquants. Die benötigte Zeit um alle Threads zu durchlaufen, ist also 10 · 1.1 + 10.1 (jeder I / O boundThread läuft für 1 Millisekunde und geht dann einen Kontextwechsel-task ein,während der CPU-gebundene Thread für 10 Millisekunden ausgeführt wird, bevor er einKontextwechsel eingeht). Der CPU-Overhead beträgt also 100 · (11 · 0,1) = 100 · 1,1 = 5,2 Prozent. (10 · 1.1 + 10.1) 21.1(a) The time quantum is 1 millisecond: Irrespective of which thread is scheduled,the scheduler incurs a 0.1 millisecond context switching cost for every contextswitch. This results in a CPU overhead of 100 · 0.1 = 9.1 per cent. 1.1 (b) The time quantum is 10 milliseconds: all I/O-bound threads incur a contextswitch after using up only 1 millisecond of the time quantum. The time requiredto cycle through all the threads is therefore 10 · 1.1 + 10.1 (as each I/Oboundthread executes for 1 millisecond and then incur the context switch task,whereas the CPU-bound thread executes for 10 milliseconds before incurring acontext switch). The CPU overhead is therefore 100 · (11·0.1) = 100 · 1.1 = 5.2 per cent. (10·1.1+10.1) 21.1

OS (Fach) / Aufgabe 5. Prozesse und Threads (Lektion)