OS Klausuraufgaben Flashcards
(176 cards)
1
Q
trap ist eine privilegierte Instruktion. Ja oder Nein?
A
Nein
2
Q
Auf Einprozessorsystemen ist zu jedem Zeitpunkt h¨ochstens einProzess im Zustand ”rechnend“(“running”). Ja oder Nein?
A
Ja
3
Q
Paging verhindert internen Verschnitt innerhalb einer Seitenkachel. Ja oder Nein?
A
Nein
4
Q
Durch Verwendung von ASIDs entf¨allt die Notwendigkeitden TLB beim Adressraumwechsel vollst¨andig invalidieren zum¨ussen. Ja oder Nein?
A
Ja
5
Q
RAID 0 mit mindestens 2 Platten erlaubt nach dem Totalausfalleiner Platte eine vollst¨andige Wiederherstellung aller Daten. Ja oder Nein?
A
Nein
6
Q
Erkl¨aren Sie die Begriffe ”Systemaufruf“ ”Exception“ und ”Interrupt“. Gehen Sieinsbesondere darauf ein wann und von wem das jeweilige Ereignis ausgel¨ost wird.
A
Systemaufruf: Wird von einem Userlevel-Programm get¨atigt um vom Kernelbereitgestellte Dienste aufzurufen (z.B. ¨ Offnen einer Datei Erstelleneines neuen Prozesses . . . ) Exception: Von der Hardware ausgel¨ost falls bei der Ausf¨uhrung einer Instruktionein Fehler auftrat (z.B. Division durch 0 ung¨ultiger Speicherzugriff. . . ) Interrupt: Ausgel¨ost von Hardwarekomponenten die damit ein bestimmtesEreignis signalisieren (z.B. anliegende Daten Ende eines Zeitintervalls. . . )
7
Q
Erl¨autern Sie die beiden Hauptprobleme die mit virtuell indizierten virtuell getaggtenCaches auftreten k¨onnen.
A
Mehrdeutigkeiten (ambiguity): Eine virtuelle Adresse wird zu verschiedenen Zeitpunktenoder in verschiedenen Adressr¨aumen (0.5 P) auf unterschiedliche physischeAdressen abgebildet. Ohne Invalidierung der entsprechenden Cachezeilenk¨onnte der Cache ”veraltete“ Daten enthalten (0.5 P) . Bedeutungsgleichheit (alias): Verschiedene virtuelle Adressen werden auf die gleichephysische Adresse abgebildet. Dadurch kann es zu Inkonsistenzen kommen(1 P) .
8
Q
Angenommen Sie sollten einen mehrf¨adigen (multithreaded) Webserver entwickelnbei dem ein Thread Anfragen von Clients entgegennimmt und diese unter einerMenge von Arbeiter-Threads verteilt. Jeder Arbeiter-Thread bearbeitet seine Anfrageindem er die ben¨otigten Daten mittels eines blockierenden Systemaufrufsvon der Festplatte liest und dann an den Client zur¨ uckschickt. Welches der dreiaus der Vorlesung bekannten Threading-Modelle w¨urden Sie in diesem Szenariobevorzugen? Begr¨unden Sie Ihre Antwort.
A
One-to-One (1 P) . Bei Many-to-One w¨urde ein blockierender Systemaufruf eines Threadsdie gesamte Anwendung blockieren (1 P) . Many-to-Many ist auch denkbar aber eigentlichnur sinnvoll wenn der Kernel die Userlevel-Threads ¨uber Blockierungen benachrichtigenkann (etwa via Scheduler Activations).
9
Q
Z¨ahlen Sie zwei Vorteile von Lottery Scheduling gegen¨uber priorit¨atsbasierten Ans¨atzenauf.
A
Verhungern wird verhindert: Solange jeder Prozess mindestens ein Ticket hatkommt er irgendwann zur Ausf¨uhrung (1 P) . Ticketweitergabe erlaubt eine genauere Abrechnung von Rechenzeit: Ein Clientprozesskann Tickets an einen Serverprozess weitergeben sodass dieser Rechenzeitdes Clients (statt eigener Rechenzeit) ”verbraucht“ (1 P) . Beim Lottery Scheduling wirken sich Lastver¨anderungen (Hinzunahme oder Entfernenvon Prozessen) gleichm¨aßig und proportional zum jeweiligen Ticketbesitzder noch laufenden Prozesse aus (graceful degradation) (1 P) .
10
Q
Nennen und erkl¨aren Sie die vier notwendigen Bedingungen f ¨ur Deadlocks.
A
Mutual exclusion (aka exclusiveness): Eine Ressource kann nicht gleichzeitig vonmehreren Prozessen benutzt werden (0.5 P) . Hold and wait: Ein Prozess der bereits mindestens eine Ressource h¨alt wartet aufmindestens eine andere Ressource (0.5 P) . No preemption: Zugeteilte Ressourcen k¨onnen einem Prozess nicht wieder entzogenwerden er muss diese selbst freigeben (0.5 P) . Circular wait: Es gibt einen Menge von Prozessen fP0; P1; : : : ; P0g wobei P0 auf eineRessource wartet die P1 h¨alt P1 auf eine Ressource wartet die P2 h¨alt usw.und Pn auf eine Ressource wartet die P0 h¨alt (0.5 P) .
11
Q
F¨uhrt ein unsicherer Zustand immer zu einem Deadlock? Warum oder warumnicht?
A
Nein (0.5 P) da ein Prozess nicht notwendigerweise das Maximum anRessourcen anfordert / ggf. eine abwechselnde Ausf¨uhrung erfolgreich ist (0.5 P) .
12
Q
Diskutieren Sie die Vor- und Nachteile von Deadlock-Vermeidung (avoidance) gegen¨uber Deadlock-Erkennung (detection).
A
Deadlock avoidance:+ Es wird sichergestellt dass keine Deadlocks auftreten (0.5 P) .+ Deadlocks m¨ussen nicht behoben werden (0.5 P) .– ¨ Uberpr¨ufung bei jeder Ressourcenzuteilung n¨otig (0.5 P) .– Maximalbedarf an Ressourcen pro Prozess muss vorab bekannt sein (0.5 P) .– Ggf. unn¨otige Verz¨ogerung von Ressourcenanforderungen (0.5 P) .
13
Q
Wozu dient ein TLB?
A
Ein TLB beschleunigt die ¨ Ubersetzung von virtuellen in physische Adressen(1 P) .
14
Q
Bestimmen Sie die effektive Speicherzugriffszeit unter der Annahme dass ein TLBLookup10 ns und ein Speicherzugriff 200 ns dauert und dass der TLB eine durchschnittlicheTrefferrate von 50% hat. Nehmen Sie an dass das System keine weiterenCaches außer dem TLB besitzt.
A
Grundformel: 0.5 * Hit + 0.5 * Miss (0.5 P)Hit: 10 ns + 200 ns = 210 ns (1 P)Miss: 10 ns + 200 ns + 200 ns + 200 ns = 610 ns (1 P)Richtiges Ergebnis (ggf. als Folgefehler): 410 ns (0.5 P)
15
Q
Welche Zugriffsrechte haben Besitzer Gruppe und andere an der Datei exam.texauf einem Unix-Dateisystem nachdem untenstehendes Kommando erfolgreich ausgef¨uhrt wurde?chmod 640 exam.tex
A
Besitzer: r w – (lesen und schreiben) (1 P)Gruppe: r – – (lesen) (0.5 P)Andere: – – – (keine Rechte) (0.5 P)
16
Q
Welche Eintr¨age m¨ussen die Metadaten einer Datei mindestens enthalten wenn”contiguous allocation“ zur Reservierung von Plattenbl¨ocken verwendet wird?
A
Anfangsadresse (0.5 P) und Gr¨oße (0.5 P) .
17
Q
Was ist ein ”einfach indirekter Block“ und wozu wird er ben¨otigt?
A
Ein ”einfach indirekter Block“ ist ein Plattenblock der Zeiger auf (bzw.Adressen von) weiteren Plattenbl¨ocken enth¨alt (0.5 P) . Er wird verwendet um Dateienverwalten zu k¨onnen die mehr Bl¨ocke belegen als eine Inode direkt referenzierenkann (0.5 P) .
18
Q
Angenommen Sie erstellen einen symbolischen Link s zu einer existierenden Dateig. Wie ¨andert sich dadurch der Linkz¨ahler in der Inode von g? Was passiert mit swenn g gel¨oscht wird?
A
Der Linkz¨ahler ¨andert sich durch symbolische Links nicht (1 P) .Nach dem L¨oschen von g zeigt der Link ins Leere bleibt aber unver¨andert bestehen(1 P) .
19
Q
Gegeben seien Plattenanfragen f ¨ur die Zylinder 1; 17; 23; 40; 42; 50; 70; 105. Der Schreib-/Lesekopf befindet sich momentan auf Zylinder 45. Geben Sie an in welcher Reihenfolgedie einzelnen Zylinder angesteuert werden wenn als PlattenschedulingstrategieSSTF verwendet wird.
A
(45) 42 40 50 70 105 23 17 1 (2 P)
20
Q
Was ist das Hauptproblem das bei Verwendung von SSTF auftreten kann?
A
Anfragen nach Zylindern ”am Rand“ k¨onnen verhungern falls st¨andig Anfragennach Zylindern ”in der Mitte“ vorliegen (1 P) .
21
Q
Erkl¨aren Sie die RAID-Level RAID1 und RAID5.
A
RAID1: Mirroring. Daten werden auf mehrere Platten gespiegelt (1 P) .RAID5: Block-Level-Parit¨at (0.5 P) mit verteilten Parit¨atsbl¨ocken (0.5 P) .
22
Q
Die CPU-Instruktion die Interrupts ausschaltet ist privilegiert. Richtig oder falsch?
A
richtig
23
Q
Beim One-to-One-Modell teilen sich alle Threads in einemAdressraum den selben Stack. Richtig oder falsch?
A
falsch
24
Q
Das Hauptproblem von physisch indizierten (physically indexed)Caches ist das Auftreten von Mehrdeutigkeiten. Richtig oder falsch?
A
falsch
25
Interrupts werden vom Betriebssystem ausgel¨ost wenn ein Benutzerprogrammeine unzul¨assige Instruktion ausgef¨uhrt hat. Richtig oder falsch?
falsch
26
Erl¨autern Sie kurz die Unterschiede zwischen einem System mit monolithischemKern und einem mikrokernbasierten System. Nennen Sie einen Nachteil einesmikrokernbasierten Systems gegen¨uber einem System mit monolithischem Kern.
Monolith: Gesamte Funktionalit¨at (einschl. Treiber) in einem einzelnen Binary d.h.keine “harte” Isolation zwischen Komponenten. (1 P) Mikrokern: Nur kleine privilegierte Code-Basis alle Dienste/Treiber laufen isoliertund unprivilegiert Kommunikation ¨uber Nachrichten. (1 P)Nachteile eines Mikrokerns: Geringere Performance durch mehr Kommunikationsoverhead (1 P) . Hoher Aufwand bei Portierung von Monolith (0.5 P) aber insgesamt max. (1 P)f¨ur Nachteil.
27
Nennen Sie zwei M¨oglichkeiten wie bei einem Systemaufruf Parameter an den Betriebssystemkern¨ubergeben werden k¨onnen.
¨ Uber Register Auf dem Stack ¨ Uber einen dedizierten Speicherbereich dessen Anfangsadresse in einem Register¨ubergeben wird
28
Er¨ortern Sie Vor- und Nachteile des Many-to-One-Modells gegen¨uber dem One-to-One-Modell.
+ Schnelles Threadmanagement (0.5 P)+ UL-Scheduling (0.5 P)+ Leicht portierbar auf 1:1 oder M:N (0.5 P)- Profitiert nicht von Mehrprozessor-Systemen (0.5 P)- Blockierender Systemaufruf eines Threads blockiert alle anderen Threads derAnwendung. (0.5 P)- Profiling/Debugging schwierig (0.5 P)
29
In einem Mehrprozessor-System kann man entweder eine gemeinsame Ready-Queue f ¨ur alle Prozessoren oder eine lokale Ready-Queue pro Prozessor verwenden.Diskutieren Sie die Vor- und Nachteile der beiden M¨oglichkeiten.
Zentral:+ Gleichm¨aßige Auslastung aller Prozessoren (1 P)- Queue wird zum Flaschenhals (1 P)Pro CPU:+ “Automatische” Prozessor-Affinit¨at (1 P)- Load-Balancing n¨otig (1 P)
30
Bei x86-Prozessoren enth¨alt das sogenannte CR3-Register die Basisadresse der¨außeren Seitentabelle (das sog. page directory). Wird vom Betriebssystem eine neueAdresse in dieses Register geladen so invalidiert die Hardware automatisch denTLB. Warum?
Weil der TLB sonst die (Virt ! Phys) Abbildungen des “alten” Adressraumszur¨uckliefern w¨urde (und somit der Prozess im “neuen” Adressraum auf falsche Datenzugreifen w¨urde). (2 P)(Formaler: Der TLB kann als virtuell indexierter virtuell getaggter Cache betrachtetwerden. Wird er beim Adressraumwechsel nicht invalidiert treten Mehrdeutigkeiten(Ambiguities) auf.)
31
Durch welche ¨Anderung am TLB k¨onnte diese Invalidierung vermieden werden?
Unterst¨utzung von ASIDs (address space identifier)
32
Erkl¨aren Sie die Begriffe demand paging und pre-paging. Bei welchem Verfahren istmit mehr “verschwendetem” Speicher zu rechnen? Warum kann dieses Verfahrendennoch von Vorteil sein?
Demand paging: Seiten werden bei Bedarf also erst beim Auftreten eines Seitenfehlerseingelagert. (0.5 P) Pre-paging: Seiten werden “auf Verdacht” eingelagert in der Hoffnung dass sie zueinem sp¨ateren Zeitpunkt ben¨otigt werden. (0.5 P)Pre-paging verschwendet potentiell mehr Speicher (0.5 P) (da Seiten eingelagert werdenk¨onnen die gar nicht gebraucht werden). Dennoch kann pre-paging von Vorteilsein da dadurch die Zahl der auftretenden Seitenfehler reduziert und somit die Leistungverbessert werden kann (1.5 P) . Effizienterer Datentransfer von der Festplatte:(1 P) falls als einziger Vorteil genannt (0.5 P) Bonus falls zus¨atzlich zur reduziertenPF-Rate.
33
Durch welche Technik k¨onnen die mit dem fork()-Systemaufruf verbundenen Kosten(in Form von Rechenzeit) deutlich gesenkt werden?
copy-on-write (1 P)
34
Erl¨autern Sie den Unterschied zwischen mandatory und advisory file locking.
Mandatory: Das Betriebssystem stellt sicher dass kein Prozess eine Datei ¨offnenkann auf die bereits ein anderer Prozess ein Lock h¨alt. (1 P) Advisory: Das Betriebssystem erlaubt den gleichzeitigen Zugriff von mehreren Prozessenauf eine Datei die Prozesse m¨ussen sich ggf. selbst um korrekte Synchronisationk¨ummern. (1 P)
35
Erkl¨aren Sie den Unterschied zwischen einem Hardlink und einem symbolischenLink.
Hardlink: Ein (weiterer) Name f¨ur eine Datei d.h. ein Verzeichniseintrag der eine(schon vorhandene) Inode referenziert. (1 P) Symlink: Eine spezielle Datei vom Typ “Link” die den Namen der Zieldatei enth¨alt.(1 P)
36
Moderne Dateisysteme erlauben es in der Regel dass Dateien aus beliebig aufder Festplatte verteilten Bl¨ocken bestehen k¨onnen. Warum kann es dennoch vonVorteil sein Bl¨ocke f ¨ur eine Datei m¨oglichst “am St¨uck” zu allozieren?
Mechanische Festplatten erlauben vergleichsweise hohe Transferraten wenn Bl¨ockesequentiell (also auf derselben Spur) gelesen werden. Die Latenz f¨ur wahlfreie Zugriffeist dem gegen¨uber aber relativ hoch da in diesem Fall der Schreib-/Lesekopf erstpositioniert werden muss (seek time). (1 P) Unter Annahme der Lokalit¨atseigenschaft (sequentieller Zugriff oder wahlfreie Zugriffe auf dieselbe Spur) (0.5 P) k¨onnen daher zeitaufwendige Positionierungen des Schreib-/Lesekopfes vermieden werden. (0.5 P)
37
Nennen Sie zwei Beispiele f ¨ur zeichenorientierte Ger¨ate (character devices).
Z.B. Tastatur (0.5 P) und Maus (0.5 P) .
38
Wof ¨ur steht das Akronym DMA? Erkl¨aren Sie kurz wie DMA funktioniert und wozuman es verwendet.
Direct Memory Access (0.5 P) Das Betriebssystem programmiert den DMA-Controller (0.5 P) der die Daten vom Ger¨at in den Hauptspeicher ¨ubertr¨agt (oder umgekehrt). (0.5 P) . Das Ende des Kopiervorgangs wird durch einen Interrupt signalisiert. (0.5 P) DMA erlaubt den Datentransfer zwischen Hauptspeicher und einem E/A-Ger¨at ohne die CPU zu belasten. (1 P)
39
Wohin zeigt der Frame Pointer?
Fixed address for the stack frame. E.g. Between arguments and local variablesor between return address and arguments (1P). To the frame + explanation what a frame is (1P). To the beginning of the frame (1P). To the frame without further explanation (0P).
40
Wof ¨ur stehen die folgenden Akronyme?APICKSP
APIC Advanced Programmable Interrupt ControllerKSP Kernel Stack Pointer
41
Bei Nutzung des Many-to-One–Faden-Modells ist es nichtm¨oglich Rechen- und E/A-Operationen zu ¨uberlappen. Richtig oder falsch?
falsch
42
Der TLB ist f ¨ur gew¨ohnlich ein physisch indizierter virtuellgetaggter Cache. Richtig oder falsch?
falsch
43
Ruft man unter Linux fork() in einem Prozess auf deraus mehreren One-to-One–F¨aden besteht so werden allezugeh¨origen F¨aden dupliziert. Richtig oder falsch?
falsch
44
In Monitoren k¨onnen Verklemmungen auftreten. Richtig oder falsch?
richtig
45
Bei hinreichend langen Zeitscheiben ist Round-Robin ¨aquivalentzu First-Come-First-Served. Richtig oder falsch?b
richtig
46
Speicherplatz der als interne Fragmentierung bezeichnet wirddarf nicht in der Frei-Liste sein wohingegen der Speicherplatzder als externe Fragmentierung bezeichnet wird in der Frei-Liste auftauchen muss. Richtig oder falsch?
richtig
47
Was spricht daf ¨ur einen dedizierten Kern-Stapel pro Prozess zu benutzen? GebenSie ein konkretes Beispiel an!
Improved kernel protection: (1P) prevents information leaks from kernel to userspace (+1P) or ensures that stack is of sufficient size for kernel operations (+1P) or handling of userstack pagefaults need a separate kernel-stack anyway (+1P) or prevents effects of malicious manipulation of user-stack-pointer (+1P)
48
Bei einem Funktionsaufruf sichert die aufrufende Funktion selbst den aktuellenCPU-Kontext auf dem Anwendungsstapel. Wer sichert den aktuellen CPU-Kontextbei Auftritt einer Unterbrechung?
CPU sichert IP(/SP) (+0.5P) Interrupthandler u.U. den Rest der durch Interrupt-Service-Routine ¨uberschriebenwird (+0.5P)
49
Im Gegensatz zu Linux Kern-Modulen sind Mikrokern-Dienste voreinander gesch¨ utzt.Wie ist dieser Schutz implementiert (zwei Aspekte)?
Every Service runs as a user process (1P) and within its own address space (1P). If you cannot name it you cannot touchit.
50
Betriebssysteme laufen normalerweise im Kern-Modus was ihnen erm¨oglicht dengesamten CPU-Instruktionssatz zu verwenden. Virtuelle Maschinen (VMs) laufenallerdings im User-Mode. Z¨ahlen Sie drei Techniken auf die benutzt werden k¨onnenum VMs die Ausf¨uhrung privilegierter Instruktionen zu erm¨oglichen.
Paravirtualization (1P) Binary Translation (1P) Trap-and-emulate (1P)
51
Nehmen Sie an Sie haben ein System welches einen Kreis im Ressourcen-Allokations-Graphen enth¨alt. Befindet sich das System zwingend in einem Deadlock?Begr¨unden Sie Ihre Antwort.
No (+1P) There could be multiple resources of a kind which might prevent a deadlock (+1P)
52
Nehmen Sie an Sie haben eine Verklemmung erkannt. Nennen Sie zwei M¨oglichkeitendiese Verklemmung aufzul¨osen.
Some possibilities are: Process termination Rollback (+ resource preemtion)/resource preemption Add resources
53
Was ist der Unterschied zwischen Verklemmungsverhinderung und Verklemmungsvermeidung?Geben Sie jeweils ein Beispiel an.
Deadlock Prevention/Verhinderung: Negate at least one of the required deadlockconditions (+0.5P) e.g. using resource ordering (+0.5P)Deadlock Avoidance/Vermeidung: Decide if system stays in safe state on everyresource request (+0.5P) e.g. the Banker’s algorithm (+0.5P)
54
Geben Sie ein konkretes Szenario an in dem ein System ein einziges Semaphorenthalten k¨onnte auf dem ein Faden nur signal- und ein anderer Faden nur wait-Operationen ausf¨ uhrt.
Reader-Writer synchronization of an unbounded shared buffer (e.g. the readeris faster than the writer) Pipeline synchronization One-way communication/signal
55
Warum tauscht die atomare swap-Instruktion welche zur Implementierung vonSpin-Locks verwendet werden kann den Inhalt eines Registers mit dem einer Speicherstellestatt zwei Registerinhalte zu vertauschen?
Each thread has it’s own private register set so swapping between registers isinvisible to other threads (1P) Registers are CPU-local resources (0.5P)
56
Erkl¨aren Sie warum man das Kritischer-Abschnitt-Problem auf Multiprozessor-Systemen nicht durch das Maskieren von Unterbrechungen l¨osen kann.
Disabling interrupts only affects a single CPU/core threads on other CPUs canstill interfere (0.5P) Disabling interrupts on all CPUs cannot be done atomically (0.5P)
57
Ein Prozessor hat einen 32-Bit-Adressraum und kombiniert Segmentierung undKachelverwaltung (wie IA-32 erst Segmentierung dann Kachelverwaltung). DieSeitengr¨oße betr¨agt 4 KiB. Visualisieren Sie was in der MMU passiert wenn einBenutzerprozess auf Speicher zugreift und weder Segmentierungs- noch Seitenfehlerauftreten. Gehen Sie davon aus dass eine einstufige Seitentabelle genutztwird.
Aufteilung der Adresse f¨ur Segmentierung (+1P) Vergleich des Offsets mit der L¨ange des Segments (+1P) Addition der Basis-Adresse des Segments (+1P) Resultierende Adresse f¨ur Paging aufteilen (+0.5P) Aufl¨osen VPN -\> PPN anhand der Pagetable (+0.5P) Protection bits im Pagetable-Eintrag mit Zugriff abgleichen (+1P)
58
Ist es sinnvoll Kachelverwaltung vor Segmentierung einzusetzen? Begr¨unden SieIhre Antwort.
No. Loses advantage of page tables (large virtual address spaces patched togetherfrom non-contiguous memory) while keeping the overhead of the two level scheme.In addition segment tables are small so building them from pages doesn’t buy youanything (and may lose because of internal fragmentation).
59
Beurteilen Sie Stapel Textsegment und Halde danach wie gut Ihrer Meinung nachbei diesen die LRU Seitenersetzungsstrategie in einer Kachelverwaltung funktioniert.Erkl¨aren Sie f ¨ur jedes Segment wie Sie zu der Einsch¨atzung kommen.
Stack best it is used in a LIFO fashion and is dense Code is second it is linear with loops and generally follows certain execution patterns Heap is last it tends to be used in a more random access fashion than e.g. stacks Different orderings may also be ok depending on your justification.
60
Ben¨otigt eine virtuelle Speicherverwaltung die Equal Allocation implementiert eineglobale oder eine lokale Seitenersetzungsstrategie? Begr¨unden Sie Ihre Antwort.
A local page replacement policy to keep the allocated shares equal.
61
In Linux hat die Oktalnotation der Zugriffsrechte 4 Ziffern. Erkl¨aren Sie wof¨ur die 4 Ziffern jeweils stehen (nicht welche Werte sie annehmen k¨onnen).
Je +0.5P f¨ur Spezialattribute Userrechte Gruppenrechte Rechte f¨ur alle.
62
Welche Zugriffsrechte werden ¨ ublicherweise f ¨ur das Verzeichnis /tmp/ gesetzt inwelchem unter Linux tempor¨are Daten abgelegt werden k¨onnen? Erkl¨aren Siewarum genau diese Rechte gesetzt werden.
1777 (+1P) Sticky bit (restricted deletion flag): Users may only remove or rename files theyown not those of others (despite the directory’s permissions) (+1P)
63
Erkl¨aren Sie warum ein RAID-5-Verbund Lesezugriffe generieren k¨onnte obwohldas Betriebssystem ausschließlich schreibend auf den Verbund zugreift.
Old data (0.5P) and Old checksum (0.5P) are needed for fast recomputation of new checksum
64
Der CPU-Befehlssatz wird generell in privilegierte und nicht privilegierte Instruktionenunterteilt. Woher weiß die CPU (IA-32) ob sie zu einer bestimmten Zeit eineprivilegierte Instruktion ausf¨uhren darf?
Current Privilege Level (CPL) Register in the CPU (”Ring”)
65
Nennen Sie 2 privilegierte IA-32 Instruktionen und erkl¨aren Sie jeweils warumdiese privilegiert sein m¨ussen.
CLI/STI - IRQ off/on - e.g. Timer triggers via interrupt if user could disableinterrupts she could interfere with scheduling PUSHF/POPF - Push/Pop Flags - e.g. to set CPL if user could set CPL she couldget kernel-mode privileges.
66
Wie bemerkt das Betriebssystem dass ein nicht privilegierter Prozess versucht hateine privilegierte Instruktion auszuf¨uhren?
The CPU generates an exception in that case.
67
Wof ¨ur stehen die folgenden Abk¨urzungen im Kontext der Betriebssysteme-Vorlesung?ASIDPFN
ASID Address Space IDentifierPFN Page/Physical Frame Number
68
Bei Nutzung des Many-to-One–Faden-Modells ist es nichtm¨oglich Rechen- und E/A-Operationen zu ¨uberlappen wennnur synchrone E/A-Primitiven benutzt werden. Richtig oder falsch?
richtig
69
Hauptprozessor-Einplanungsalgorithmen in General-PurposeBetriebssystemen tendieren dazu denjenigen Auftr¨agen hohePriorit¨aten zuzuordnen welche den Hauptprozessor am wenigstenbenutzen. Richtig oder falsch?
richtig
70
Ruft man unter Linux fork() in einem Prozess auf deraus mehreren Many-to-One–F¨aden besteht so werden allezugeh¨origen F¨aden dupliziert. Richtig oder falsch?
richtig
71
Wird Copy-on-Write bei der Prozessduplikation mittels fork() benutzt hat dies Geschwindigkeitsvorteile f ¨ur das Kind ohneGeschwindigkeitseinbußen f ¨ur den Vaterprozess zu bringen. Richtig oder falsch?
falsch
72
Beim One-to-One-Modell teilen sich alle Threads in einemAdressraum den selben Heap. Richtig oder falsch?
richtig
73
Erkl¨aren Sie den Begriff Zombie im Kontext von Prozessen. Geben Sie insbesonderean wie ein Zombie entsteht und wie man ihn entfernt.
Zombie: Stub of a child process in the process table after it has terminated. The parent needs to collect the exit status of the terminated processes with thewait or waitpid syscalls to get rid of zombies. (Note: Zombies exist for preciselythat reason—to keep a child process’s exit status.)
74
Nennen und erl¨autern Sie kurz die drei notwendigen Bedingungen f ¨ur eine g¨ ultigeL¨osung des Problems kritischer Abschnitte.
(a) Mutual exclusion: Only one thread can be in cs at a time.(b) Progress: If no process is in the CS one of the processes trying to enter will eventuallyget in. Processes that are not trying to enter do not hinder processes that try toenter from getting in.(c) Bounded waiting: Once a thread starts trying to enter the critical section thereis a bound on the number of times other threads get in.
75
Nennen Sie die zwei grunds¨atzlichen Kommunikations-Modelle der Interprozess-Kommunikation (Hinweis: Gefragt sind nicht die verschiedenen Design-Parametersondern die grundlegenden Modelle). Welche der beiden Modelle werden von POSIX (und damit von den meisten Unix- Systemen) angeboten?
shared memory (0.5 pt) (used in the example) message passing (0.5 pt) POSIX: both (0.5 pt)
76
Das Beispiel aus Listing 1 implementiert einen Spinlock mittels atomarem Vertauschen(swap). Nennen Sie eine weitere atomare nicht priviligierte Instruktiondie zur Synchronisation verwendet werden kann (ihre Bezeichnung nichtAssembler-Befehl) und beschreiben Sie kurz ihre Funktion.
We expect one of test and set: Test a memory word and set its value fetch and add: Fetch a memory word and add a value in memory. compare and swap: Compare content of a memory word and set it to a newvalue.
77
Erkl¨aren Sie warum es auf Einprozessorsystemen nicht sinnvoll ist Spinlocksdaf ¨ur zu benutzen kritische Abschnitte im Betriebssystemkern zu sch¨ utzen.
Spinlocks are not reasonable for single-processor systems because the conditionthat would release a process from the spinlock could be obtained only by executinga different process that eventually releases the lock not by spinning inthe process waiting to acquire the lock. The time spent spinning would be lost unnecessarily. 0.5 Bonus: If the spinning process does never relinquish the processor otherprocesses do not get the opportunity to establish the condition required for thefirst process to make progress.
78
Wie w¨urden Sie (als Alternative zu Spinlocks) kritische Abschnitte auf einem Einprozessorsystemimplementieren? Welche Eigenschaft f ¨uhrt dazu dass diese L¨osung nur im Betriebssystemkern verwendbar ist und warum darf man diese Beschr¨ankung nicht aufheben? Wie k¨onnen Benutzerprogramme dennoch Synchronisationsprimitive verwenden?
We may disable interrupts during critical sections. (1 pt) Enabling or disabling interrupts is a privileged operation and user-level applicationsrun unprivileged (in contrast to the kernel). (0.5 pt) We cannot allow user-space programs to disable interrupts because this wouldallow to hog the CPU and to avoid preemption. (0.5 pt) The OS kernel offers synchronization primitives to user-level via the system callinterface. (1 pt)
79
Nehmen Sie an ihr Rechner besitzt einen TLB mit fester Seitengr¨oße. Welche Eigenschaftdes TLB limitiert die physische Speichergr¨oße welche ihr System nutzenkann?
The number of bits in the physical page number as it is stored in the TLB.
80
Woher kennt der Kernel die Basisadresse der ¨außeren Seitentabelle (page directory)in IA-32 Systemen?
%cr3 (Control Register 3)
81
Wie viele Seitentabellen existieren jeweils im Falle von Invertierten Seitentabellenund im Falle von einstufigen Vorw¨arts-Seitentabellen im Betriebssystem? Begr¨undenSie jeweils kurz wie Sie auf die Anzahl kommen.
inverted pagetables: 1 (table of all physical pages) forward pagetables: one for every process (mapping of each processes’ virtualpages to system’s physical pages)
82
Diskutieren Sie die folgende Aussage: Puffer ¨ uberl¨aufe welche zur Ausf¨uhrung vonbeliebigem Code f ¨uhren k¨onnen nicht mehr auftreten wenn man die Richtungumkehrt in welche der Stack w¨achst.
Classical stack overflow: Return address is stored on the stack. The stack grows downward. There is no check for accessing/writing data beyond the bounds of the buffer.Stack grows upward: Buffer can theoretically overflow ”downwards” (e.g. through neg. index). Buffer may have been allocated in old stackframe and passed through a pointer(then the problem is just passed to the previous stackframe). It does make programming errors that lead to buffer overflow attacks harder orimpossible to exploit but does not prevent them.
83
Wird in einem UNIX-artigen Dateisystem der Dateiname im Verzeichnis oder inder inode gespeichert? Welches Funktionsmerkmal des Dateisystems macht dieseDesignentscheinung sinnvoller als die andere?
The filename is stored in the directory. Otherwise hard-links with different nameswould be impossible.
84
Erkl¨aren Sie warum ein harter Link unter Unix nicht verschiedene Dateisysteme¨uberspannen kann w¨ahrend ein symbolischer Link dies kann.
A hardlink references an inode (by inode number). Inodes are a file system local entityso inode numbers are unique only within a file system. Symbolic links referencea VFS path and are thus unrelated to the underlying FS.
85
Erkl¨aren Sie wie Caching sowohl die Latenz als auch die Bandbreite eines Systemsverbessern kann. Geben Sie jeweils ein Beispiel an.
Latency: Access data that has been accessed before or access data that hasbeen prefetched before it was needed. Bandwidth: Prefetch from I/O devices while they are idle or batch transfers tominimize seeking delays.
86
Beschreiben Sie die Methode in RAID 5 welche es erm¨oglicht Daten redundant zuspeichern ohne ein Replikat f ¨ur jeden Block der Platten zu speichern. Beschreibensie insbesondere was wie und wo gespeichert wird und wie die Daten bei Ausfalleiner Platte wiederhergestellt werden k¨onnen.
Note: n data drives require n+1 RAID5 drives (0pt). XOR all blocks with the same address and store the result on the n+1st drive(parity block). Revolve the location of the parity block in such a way that they are evenly distributedamong all drives. When a disk fails its contents can be restored by XORing the other drives.
87
Wie viele Lese- und Schreibzugriffe auf die Datenplatten sind notwendig wenn einByte auf ein RAID 5 Array geschrieben wird? Gehen Sie davon aus dass keineCaches benutzt werden. Erkl¨aren Sie Ihre Antwort!
2 reads (old data old parity)2 writes (new data new parity)Note: You do not have to read from all data drives to calculate the new parity block.
88
Warum wird ein RAID 5 System oft einem RAID 4 System vorgezogen?
Using RAID4 every data write implies a write to the very same parity disk. WhenRAID5 is used the parity read and write load is distributed among all drives.
89
Was tut der folgende Assmbler-Befehl auf einer IA-32 Architektur? Wof ¨ur wird ersemantisch benutzt?subl 16 %esp
Subtract 16 bytes from stack pointer. Semantically this is an allocation of 16 byteson the stack.
90
Erkl¨aren Sie den Begriff: preemption.
Forcefully take away a recource from a process.
91
open und close sind priviligierte CPU Instruktionen. Richtig oder falsch?
falsch
92
Die MMU muss bei jedem Load/Store Zugriff eines User LevelProzesses Virtuelle Addressen in Physische Addressen ¨ ubersetzen. Richtig oder falsch?
richtig
93
Wenn wir schnellen g¨ unstigen großen kompakten energieeffizientenund nicht-fl ¨uchtigen Speicher h¨atten br¨auchten wirkeine Cache-Hierarchy. richtig oder falsch?
richtig
94
Belady’s Anomalie kann auftreten wenn die LRU Seitenersetzungsstrategiegenutzt wird. richtig oder falsch?
falsch
95
Nennen Sie vier verschiedene Metriken/Kriterien welche zur Beurteilung einesScheduling-Verfahrens herangezogen werden k¨onnen.
Processor utilization Application Throughput Turnaround time Waiting time Response time ...
96
Diskutieren Sie Vor- und Nachteile einer langen gegen¨uber einer kurzen Zeitscheibenl¨ange.
The longer a timeslice is the fewer context switches per time-unit are required. Ascontext switches require a certain overhead (entering the kernel selecting a newprocess to run switching address spaces if necessary etc.) reducing the number ofcontext switches can help to improve the throughput. However making time slices toolong will negatively affect the responsiveness of the system: Each process will run fora relatively long time until it will be preempted and consequently ready processeshave to wait longer until they are allowed to run again.
97
Erkl¨aren Sie kurz das Scheduling-Verfahren: Multi-Level Feedback Queue (MLFB)mit variablen Zeitscheibenl¨angen.Erkl¨aren Sie kurz ob MLFB ein geeignetes Verfahren in den folgenden F¨allen ist:In einem System in welchem die Kosten f ¨ur Kontextwechsel hoch sind.In einem System in welchem Aushungern (Starvation) vermieden werden sollte.
MLFB: Multiple queues with individual priorities and time slice. Typically the lowerthe prio the larger the timeslice. Interactive processes have high-prio and small timeslice.CPU-bound processes that eat up all CPU time go to a lower-priority queue withhigher time slice.MLFB is a good choice when context switching costs are high as it only requiresfrequent switches with short jobs but avoids switching contexts with long-runningjobs.In MLFB many short-running jobs may starve lower-priority jobs. However this canbe avoided by moving processes that have been waiting too long into higher-priorityqueues.
98
Welche Hardware-Mechanismen werden typischerweise auf Einprozessorsystemenzur Implementierung von Synchronisation im Betriebssystem verwendet welcheauf Mehrprozessorsystemen?
Uniprocessor: Disabling interrupts (+0.5P). Multiprocessor: Atomic instructions / inter-processor interrupts (+0.5P one issufficient)
99
Warum greift testAndSet auf den Hauptspeicher und nicht auf ein weiteres Registerzu? Begr¨unden sie Ihre Antwort mit einem Szenario wof¨ur testAndSet typischerweiseeingesetzt wird.
The register set is private to a thread and CPU-local (+0.5P). testAndSet is typicallyused for synchronization between several CPUs thus it needs to be visible acrossthreads and across CPUs (+0.5P).
100
Welche Arten von Fragmentierung wurden in der Vorlesung vorgestellt?
Internal fragmentation (+0.5P) and external fragmentation (+0.5P).
101
Welches Ereignis geschieht beim ersten Zugriff eines Prozesses auf seinen Stackwenn das Betriebssystem on-demand paging verwendet? Wie reagiert das Betriebssystem darauf damit der Prozess anschliessend weiterl ¨auft?
The CPU/MMU generates a pagefault (+0.5P). The operating system then assigns physical memory / a physical page for the page just accessed (+0.5P) updates the pagetable of the process setting the valid bit of the faulting page(+0.5P) and continues the execution of the process by restarting the faulting instruction.(+0.5P)
102
Was ist anonymer Speicher? Nennen Sie zwei m¨ogliche Quellen.
Anonymous memory is memory that is not backed by a file. E.g. the heap or thestack segment of a process.
103
Wie wird benannter (nicht-anonymer) Speicher beim Swapping behandelt?
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
104
Mit dem Programm fsck k¨onnen unter Unix Dateisystemfehler gefunden und behobenwerden. Geben Sie f ¨ur die folgenden Fehlermeldungen an was fsck iminkonsistenten Dateisystem gesehen haben k¨onnte um auf den Fehler zu schließen.Der Inode Linkz¨ahler ist 1 er sollte 2 sein.Der Frei-Bitmap Eintrag f ¨ur Block 1234 ist 0 (frei) er sollte 1 sein (belegt).
A second directory entry has been found to an inode with link count 1.An inode entry points to a block which is not marked to be allocated.
105
Wir haben in der Vorlesung drei Dateiallokationsstrategien kennengelernt:(a) Indexed allocation (b) chained allocation und (c) contiguous allocation. GebenSie f ¨ur die folgenden Szenarien an wie gut die Strategien jeweils geeignet sind undwarum.Schneller wahlfreier Zugriff auf sehr große Dateien.Ausnutzung der Festplattenkapazit¨at (Speichern m¨oglichst vieler Datei-Bytes).
Contiguous allocation: Am besten sehr einfache Index-Berechnung ohne indirekteZugriffeIndexed allocation: Sehr gut einfaches Finden des richtigen Blocks mithilfe desIndizes.Chained allocation: Schlecht lineares durchsuchen der Kette zum Finden des korrektenBlocks. Chained allocation: Sehr gut keine externe Fragmentierung kleine Datenstrukturen. Indexed allocation: Sehr gut keine externe Fragmentierung minimal gr¨oßere Datenstrukturen als bei Chained allocation. Contiguous allocation: Schlecht entweder externe Fragmentierung oder compaction n¨otig.
106
Beim Lottery Scheduling ist garantiert dass jeder teilnehmendeFaden nach endlicher Wartezeit eine CPU-Zeitscheibe zugeteiltbekommt. richtig oder falsch?
Richtig
107
Ausnahmen werden vom Betriebssystem ausgel¨ost wenn einBenutzerprogramm eine unzul¨assige Instruktion ausgef¨uhrthat. richtig oder falsch?
falsch
108
Beim Ausf¨uhren vieler I/O-Operationen in kurzer Zeit l¨asst sichdurch Einsatz von Polling anstelle von Interrupts ein h¨ohererDurchsatz erreichen. richtig oder falsch?
richtig
109
Wird ausschließlich Paging mit fester Seitengr¨oße verwendetum virtuellen Speicher zu implementieren kann im physischenAdressraum externe Fragmentierung auftreten. richtig oder falsch
falsch
110
malloc ist ein Systemaufruf mit dem Prozesse Speicher vom Betriebssystemanfordern k¨onnen. richtig oder falsch?
falsch
111
Im Kernadressraum gibt es keine Seitenfehler. richtig oder falsch?
falsch
112
Das Hauptproblem von physisch indizierten (physically indexed)Caches ist das Auftreten von Mehrdeutigkeiten. richtig oder falsch?
falsch
113
Was verstehen wir unter kritischen Abschnitten im Kontext von Betriebssystemen?Beschreiben Sie den Begriff kurz.
Sections of programs where concurrent activities or threads (0.5pt) access shareddata (0.5pt).
114
Nennen Sie einen Mechanismus mit dem man einen Mutex f ¨ur ein Multiprozessorsystemimplementieren kann. Ist dieser nur im Betriebssystem-Kern oder auchim User-Space nutzbar? Begr¨unden Sie kurz warum.
Spinlocks/atomic instructions and busy waiting. Can be used in kernel-spaceand user-space because atomic instructions are commonly non-privileged. Disabling interrupts. Can only be used in kernel because it is a privileged instruction.
115
Sie sollen die Zugriffsrechte f ¨ur ein geteiltes Verzeichnis work einer Arbeitsgruppe project festlegen. Alle Gruppenmitglieder sollen in work Dateien auflisten lesenschreiben und anlegen k¨onnen ansonsten soll aber niemand Zugriff auf das Verzeichnishaben. Die korrekten Rechte sollen auch automatisch f ¨ur neu angelegteDateien gesetzt werden.Geben Sie in Oktalnotation die Werte f ¨ur die Zugriffsrechte und Benutzermaskesowie je eine kurze Erkl¨arung an!
chmod 2070 workumask 007Set rwx for group and the SGID to inherit group ownership to newly created files anddirectories. Owner may optionally also have rwx. User mask 007 gives rwx for newfiles to owner and group 707 gives rwx only to group.
116
Unter welchen Umst¨anden ist eine Free-List eine bessere Datenstruktur als eineBitmap um freie Bl¨ocke eines Dateisystems zu verwalten?
Finding free space is generally faster. – If you need to find large free chunks quickly you may sort free list by size. If you have few large allocations you need less space.
117
In C/Unix kann man Dateihandles offener Dateien an Funktionen ¨ubergeben.Nehmen Sie an Sie schreiben eine Funktion die ein offenes Dateihandle als Argument¨ubergeben bekommt. Ist es einfach m¨oglich den Dateinamen der offenenDatei zu bestimmen? Wie bzw. Warum?
A file handle represents an open file in the OS. It associates a number with a filedescritor that contains an inode offset pair. The path and file name of the open filecan not be inferred directly through the handle. Knowing the inode does not helpeither there may be different files represented by the same inode (hard links).
118
Erkl¨aren Sie f ¨ur die folgenden Daten wo/wie diese in einem Unix Dateisystemgespeichert werden!The file nameThe name of containing directoryThe file sizeThe number of symbolic links
The file name is represented as directory entry The name of containing directory may be ambiguous and is only implicitly storedthrough the directory structure. Files may be stored in multiple directories(hard links). The file size is stored in the inode. The number of symbolic links is not stored at all and can only be obtained throughsearching the entire directory tree.
119
Wie kann in einem System mit virtuellem Speicher und Demand Paging die Anzahlvon Seitenfehlern durch das Hinzuf¨ugen von Pre-Paging reduziert werden?
Pre-paging can reduce the number of page faults by transfering pages from disk toRAM before a process accesses them. (1pt)
120
Ist es m¨oglich dass es durch Pre-Paging zu mehr Seitenfehlern kommt? Wenn jawie? Wenn nicht was verhindert dies?
Yes pre-paging may also increase the number of page faults as it is highly speculative.It may lead to the eviction of used pages although the pre-loaded pages are notneeded. (1pt)
121
Erkl¨aren Sie kurz was man unter interner und externer Fragmentierung versteht.Geben Sie jeweils ein Beispiel an wo diese auftreten k¨onnen.
Internal: Allocated memory may be slightly larger than requested memory (becauseof alignment requirements); the unused fragement is inside the allocated partition.(1pt)Example: Allocation with page granularity in an address space (0.5pt)External: Total memory space exists to satisfy a request but it is not contiguous.(1pt)Example: Heap (0.5pt)
122
In der Vorlesung wurde eine Methode zur Reduktion von externer Fragmentierungvorgestellt. Um welches Verfahren handelt es sich? Eignet sich dieses Verfahrenum externe Fragmentierung im virtuellen Adressraum eines laufenden Prozesseszu verringern? Begr¨unden Sie Ihre Antwort!
The method is called Compaction. (0.5pt)The technique is not suitable because it invalidates memory references in the runningprocess. (0.5pt) Alternative: The technique is (only) suitable in managed execution environments. (0.5pt)
123
Bei Copy-On-Write werden die gleichen physischen Seiten (z.B. von Programmbibliotheken)in die Adressr¨aume mehrerer Prozesse eingeblendet. Um die Speicherisolationzwischen den Prozessen zu gew¨ahrleisten wird bei Schreibvorg¨angen aufdiese Seiten durch das Betriebssystem eine private Kopie angelegt. Wie erkenntdas Betriebssystem solche Schreibvorg¨ange?
The pages are mapped read-only. (0.5pt)On write operations the CPU triggers a page fault and thereby invokes the operatingsystem. (0.5pt)
124
F¨ur welche Speicherbereiche ist es typischerweise n¨otig das Caching durch denProzessor zu unterbinden?
Buffers that are modified via DMA require that caching is disabled. Otherwisethe processor might read stale data. (1pt)Alternative: Areas that map device registers. (1pt)
125
Beschreiben Sie die Unterschiede zwischen kurzfristigem (short-term) und langfristigem(long-term) Scheduling.
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 secondsminutes 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.
126
Diskutieren Sie warum es schwierig ist einen Prozess-Scheduler so zu gestaltendass er gleichzeitig die f ¨ur Anwendung zur Verf ¨ugung stehenden CPU-Zyklen unddie Antwortzeit der Prozesse optimiert. Geben Sie ein Szenario an in welchem eszu einem Zielkonflikt des Prozess-Schedulings kommen kann.
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.
127
Nennen Sie zwei plattform-unabh¨angige ganzzahlige Datentypen aus stdint.h undgeben Sie f ¨ur beide die gr¨oßte darstellbare Zahl an.
uint8 t 0xFF int16 t 0x7FFF ...
128
Beschreiben Sie knapp den Unterschied zwischen Multiprogramming und Multitasking.(Gehen Sie von einem Uniprozessorsystem aus.)
With multiprogramming the operating system switches between jobs/processesat OS-specific program conditions e.g. when the currently running job/processis waiting for I/O. (0.5P) With multitasking the operating system can switch between jobs/processes independentof any program conditions/design. (0.5P) When switching at a highrate interactivity of the jobs/processes is fostered.
129
DMA bietet immer eine geringere Latenz als unterbrechungsgetriebeneE/A. richtig oder falsch?
falsch
130
Nach der write-back-Strategie werden ver¨anderte Daten imCache nur in Folge eines write misses zur¨uckgeschrieben. richtig oder falsch?
falsch
131
Ringf¨ormige Zwischenspeicher l¨osen das Erzeuger-Verbraucher-Problem zwischen E/A-Ger¨aten und Anwendungen. richtig oder falsch?
falsch
132
Wenn das SUID-Bit eines Verzeichnisses gesetzt ist k¨onnen Programmeinnerhalb des Verzeichnisses nur vom Besitzer des Verzeichnisses ausgef¨uhrt werden. richtig oder falsch?
falsch
133
Unter Unix enth¨alt nur der Eintrag in der system-weiten Tabellege¨offneter Dateien die aktuelle Position des Zugriffs (seek position)einer ge¨offneten Datei. Daher st¨oren sich geforkte Prozessegegenseitig wenn sie gleichzeitig auf einer Datei ¨uber demselbenglobalen Eintrag arbeiten. richtig oder falsch
richtig
134
Auf C99-konformen Systemen entspricht die L¨ange (in Bytes)eines Zeigers (z.B. unsigned integer \*) nicht immer der des unsigned integer-Datentypens. richtig oder falsch?
richtig
135
Nennen Sie vier in der Vorlesung besprochene Bestandteile eines Prozesskontrollblocks.
Process state Process identifier Program counter CPU registers CPU scheduling information Memory-management information List of open files ...
136
Erkl¨aren Sie kurz wann der Kontrollblock eines Prozesses ausschließlich g¨ ultigeInformationen enth¨alt und wann nicht.
When a process is not in execution its PCB contains valid information only.(0.5P) When a process is in execution its PCB may contain invalid information e.g.CPU registers. (0.5P)
137
Beschreiben Sie knapp die Fairness-Strategie nach welcher der Linux Completely Fair Scheduler versucht immer wenn er aufgerufen wird die Interaktivit¨at vonProzessen zu gew¨ahrleisten?
On invocation whatever time has passed to establish fair scheduling eachprocess must have had a proportional share of the CPU over its entire lifetime. Ifa process did not get its share during this time it has unfairly waited and is tobe executed next. (1P) This behaviour fosters interactiveness of I/O-bound processes as CPU-boundprocesses have a generally lower priority. (1P)
138
Erkl¨aren Sie knapp was man unter Kompaktierung im Zusammenhang mit externer Fragmentierung versteht und unter welcher Bedingung Kompaktierunganwendbar ist.
Reduce external fragmentation by compaction. Shuffle memory contents to placeall free memory together in one large block. (0.5P) Compaction is possible only if relocation is dynamic (i.e. the memory referencesmust remain valid when moving a program from one region to another) and isdone at execution time. (0.5P)
139
Beschreiben Sie die n¨otigen Schritte um einen Seitenfehler im Addressraum einerAnwendung zu behandeln (typischerweise 6 inkl. Reaktivierung).
valid!? free space find and allocate ! freien speicher freiräumen ! content in frame laden ! page table ! restart!
140
Was sind Aliase im Zusammenhang mit virtuell-indizierten Daten-Caches? WelcheBedingung muss ein Betriebssystem erf ¨ ullen damit diese im Daten-Cache auftretenk¨onnen?
Alias: different virtual addresses point to the same physical memory location.(0.5P) The operating system must allow to map a physical memory location to morethan one virtual memory location: shared memory (0.5P)
141
In Linux besteht die Oktalnotation der Zugriffsrechte aus 4 Ziffern. Z¨ahlen Sie aufwof¨ur die 4 Ziffern jeweils stehen (nicht welche Werte sie annehmen k¨onnen). Wof ¨ur stehen die Werte die die hinteren drei Ziffern annehmen k¨onnen in Bezug auf regul¨are Dateien und in Bezug auf Verzeichnisse? (Konzentrieren Sie sich auf die Zweierpotenzen.)
Special (0.5P) User (0.5P) Group (0.5P) Other (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)
142
Welches sind die zwei Ziele von RAID und durch welche Konzepte werden dieseumgesetzt?
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)
143
Nennen Sie die drei in der Vorlesung besprochenen Zeitpunkte an denen bei derVerarbeitung eines Programms dessen Programmtext und Programmvariablen anSpeicheradressen gebunden werden.
Compile time (Übersetzungszeit) (+0.5P) Load time (Ladezeit) (+0.5P) Execution time (Ausführungszeit) (+0.5P)
144
Wie kann die CPU erkennen dass ein nicht privilegierter Prozess versucht eine privilegierteInstruktion aufzurufen? Wie wird das Betriebssystem darüber benachrichtigt?
The CPU has mode flag (i.e. user mode). Now privileged instructions are prohibitedto be executed. (+0.5P) The CPU generates an exception which invokes an operating system handlerimmediately. (+0.5P)
145
Beschreiben Sie knapp die Unterschiede in der Struktur von Systemen auf Basisvon monolitischen und Mikro-Kernen. In welcher Art von Systemen liegt prinzipiellein größerer Overhead durch IPC vor? Begründen Sie Ihre Antwort kurz
micro kernel: user-space (hosting applications and “as many as possible partsof the kernel”) kernel-space (hosting the “kernel essentials”) (+1P) Micro kernels impose larger IPC overhead as kernel-internal communication imposesswitches between user- and kernel-mode. (+0.5P)
146
Beschreiben Sie knapp den Unterschied zwischen Virtualisierung und Para-Virtualisierung.Welche Auswirkungen hat dies für das Gast-OS?
Either one of the following (+1P) Using virtualization guest operating systems are provided with (virtual but)identical copies of the underlying hardware. Therefore the guests do not haveto be modified. Using para-virtualization guest operating systems are not provided with fullyidenticalcopies of the underlying hardware. Therefore the guests have to be“aware of their virtualization” and be modified.
147
In SMPs müssen Caches durch geeignete Protokolle synchronisiertwerden. richtig oder falsch?
richtig
148
RAID 0+1 bietet hörere Ausfallsicherheit als RAID 1+0. richtig oder falsch?
falsch
149
In RAID2 und RAID3 sollte die Rotation der Platten synchronisiertsein um möglichst hohe Performanz zu bieten. richtig oder falsch?
richtig
150
Bei Nutzung des One-to-One-Threading-Modells kann das BetriebssystemI/O-Operationen nicht überlappen falls es Prozessennur eine synchrone I/O-API bietet. richtig oder falsch?
falsch
151
Bei IPC mittels synchronem Message Passings blockiert einsend-Aufruf solange bis der Empfänger die receive-Operationabgeschlossen hat. richtig oder falsch?
richtig
152
Der TLB kann nicht in Hardware implementiert werden. richtig oder falsch?
falsch
153
Erklären Sie den Begriff Orphan im Kontext von Prozessen.
A process whose (original) parent process has died (+0.5P) whereby the child isleft orphaned.
154
Nennen Sie ein Threading-Modell welches das Debugging von Anwendungen begünstigtund eines welches es erschwert. Begründen Sie Ihre Antworten.
Favors: one-to-one (+0.5P). A debugger can interact with a single User-LevelThread without interfering with concurrent threads (of the same application).(+0.5P) Complicates: many-to-one (+0.5P). When a debugger interacts with a User-LevelThread it interferes strongly with concurrent threads (of the same application)e.g. if one thread is halted any other threads have to be halted too. (+0.5P)
155
Explären Sie knapp die Rollenverteilung zwischen CPU-Scheduler und Dispatcher.
CPU Scheduler: Policy welcher Prozess als nächstes läuft. (+0.5P) Dispatcher: Mechanismus der den tatsächlichen Prozesswechsel durchführt. (+0.5P)
156
Welche Art von Prozessen wird von Virtual Round Robin gegenüber Robin Robin gefördert? Begründen Sie ihre Antwort knapp.
I/O-bound processes are priotized over CPU-bound processes. (+0.5P) When an I/O has completed the blocked process is moved to an auxiliary queuewhich gets preference over the main ready queue. (+0.5P)
157
Nennen und beschreiben Sie 4 in der Vorlesung besprochene Kriterien die einScheduler optimieren kann.
Throughput # of processes that complete per time unit (+0.5P) Turnaround time time from submission to completion (+0.5P) Response time time from request to first response (+0.5P) CPU utilization keep the CPU as busy as possible (+0.5P) Waiting time time each process waits in ready queue (+0.5P)
158
Erklären Sie Direct Communication und Indirect Communication im Kontextvon Prozesskommunikation.
Direct communication: Processes must name each other explicitly: send(P message) receive(P) (+0.5P) Links are established automatically exactly one link is associated with exactlyone pair of communicating processes. (+0.5P)Indirect communication: Messages are directed to and received from mailboxes. (+0.5P) Link established only if processes share a common mailbox. A link may be associatedwith many processes. (+0.5P)
159
Beschreiben Sie das Producer-Consumer-Problem.
At least one producer produces data that is consumed by at least one consumer.Concurrent access to shared data may result in data inconsistency. (+1P) Maintaining data consistency requires mechanisms to ensure the orderly executionof cooperating processes. (+1P)– There must be no race conditions in data accesses. (+0.5P)– If a bounded buffer is used the producer does not overflow the buffer consumerdoes not underflow the buffer. (+0.5P)
160
Exklären Sie knapp was Critical Sections sind.
Sections of programs where concurrent activities or threads access shared data.(0.5P)
161
Erklären Sie knapp wann sich ein System im Kontext von Ressourcenzuteilung ineinem unsicheren Zustand befindet?
A system is in an unsafe state if there exists no schedule such that the maximalresource requests of all processes can be satisfied. (+1P)
162
Wie ist der Single Buffer Speed Up definiert? Geben Sie die Formel und die Bedeutung
der verwendeten Variablen an.
163
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?
chmod 670 a
chmod 123 b
chmod 456 c
Was ¨andert sich an b und c, wenn a gel¨oscht wird?
164
165
166
Nehmen Sie an, dass ein Betriebssystem die drei Taskzust¨ande ”rechnend“ (“running”),
”bereit“ (“ready”) und ”blockiert“ (“blocked”) unterst ¨ utzt. Stellen Sie grafisch
dar, zwischen welchen Zust¨anden ¨ Uberg¨ange m¨oglich sind und geben Sie jeweils
an, von welchen Ereignissen diese ¨ Uberg¨ange ausgel¨ost werden.
167
Skizzieren Sie einen gebr¨auchlichen Aufbau des virtuellen Adressraums eines Prozesses.
168
169
Zählen Sie drei verschiedene RAID-Architekturen auf und nennen Sie die Eigenschaften
durch welche Redundanz und Performanz verbessert werden.
Kombinierte Architekturen, wie z.B. RAID 0+1, sind ausgeschlossen.
170
Wir haben in der Vorlesung die Adressr¨aume von Prozessen in 6 Sektionen aufgeteilt.
Wie haben wir diese benannt? Geben Sie jeweils ein Beispiel f ¨ur Daten an, die in
den Sektionen gespeichert werden.
171
172
Erkl¨aren Sie, wie bei der Verwendung von Segmentierung eine logische Adresse auf
eine physische Adresse umgesetzt wird (Bild + Erkl¨arung).
Logische Adresse wird aufgeteilt in Segmentnummer s und Offset/Displacement
d. (0.5 P)
Die Segmentnummer dient als Index in die Segmenttabelle, dort wird der Segmentdeskriptor
(base und limit) an der entsprechenden Stelle geladen. (0.5 P)
limit wird mit dem Offset verglichen. Ist der Offset gr¨oßer, so ist der Zugriff
ung¨ultig, da die resultierende Adresse außerhalb des Segments liegen w¨urde.
In diesem Fall wird eine Ausnahme ausgel¨ost. (0.5 P)
Ist der Offset kleiner als das limit, so ist der Zugriff g¨ultig, und die Basisadresse
wird zum Offset d addiert. Das Resultat ist die physische Adresse, die an den
Speichercontroller weitergegeben werden kann. (0.5 P)
173
Wie ist die Effective Access Time (EAT) definiert? Geben Sie die Formel an und
erkl¨aren Sie die Parameter.
174
Schreiben Sie ein C-Code-Fragment, welches einen neuen Kind-Prozess erstellt.
Das Kind soll sich sofort mit dem Statuswort 1 beenden. Der Vater-Prozess soll die
Prozess ID des Kindes und sein Statuswort auf die Standardausgabe ausgeben. Sie
m¨ussen keine Fehler behandeln.
Erinnerung: Die Signatur von wait ist: pid\_t wait(int \*status);
175
Nennen Sie die drei Prozesstypen, beschreiben Sie deren typische Reaktionsfreudigkeit
und Gebundenheit (E/A, CPU).
176
Implementieren Sie die wait()-Operation eines blockierenden Semaphors in Pseudocode.
Die Funktion block() kann benutzt werden, um den aktuellen Prozess zu
blockieren und den Scheduler aufzurufen. Die globale Variable cur\_process bezeichnet
den aktuell laufenden Prozess. Der Datentyp List stellt die Operationen
append(elem) und remove() zur Verf ¨ugung, die dazu verwendet werden k¨onnen,
ein Element an die Liste anzuh¨angen bzw. das erste von dieser zu entfernen und
zur¨uckzugeben.
Sie brauchen nicht sicherzustellen, dass der Code atomar ausgef¨uhrt wird!
