46

OS (Fach) / Aufgabe 3: Prozesskoordination und -kommunikation (Lektion)

Diese Lektion wurde von Frankybu erstellt.

Lektion lernen

zurück  |  weiter 1 / 1

• Welche Informationen über die Ressourcennutzung von Programmen benötigt ein System zur Laufzeit, um Deadlockvermeidung (deadlock avoidance) zu implementieren? (2 pt) Which information about resource usage of processes do you need in an operating system at runtime for implementing deadlock avoidance? (A) Aktuelle Zuordnung von Ressourcen zu Prozessen (0,5 P),(B) verfügbare Mittel (0,5 P) und(C) am wichtigsten: Die maximale Ressourcennutzung jedes Prozesses muss im Voraus               bekannt sein.(1 P)(a) current allocation of resources to processes (0.5 P),(b) available resources (0.5 P), and(c) most importantly: maximum resource usage of each process needs to be knownin advance. (1 P)
• Nennen Sie die zwei grundlegenden Arten des Wartens in Synchronisationsprimitiven. Warum ist auf einem Einprozessorsystem nur eine davon sinnvoll, und welche ist dies? (2 pt) State the two fundamental forms of waiting within synchronization primitives. Why does only one of them make sense on a single-processor system, and which one is that? Beschäftigtes Warten (0,5 P) und Schlaf + aufwachen (oder blockieren) (0,5 P).Nur Schlaf / Aufwachen macht Sinn auf einem Einzelprozessorsystem. Während dem beschäftigten  warten kann der Sperrhalter keine Fortschritte machen, um das Schloss zu lösen, weil der Thread während dem warten die einzelne CPU einnimmt. Also ist die Zeit die, man mit beschäftigtem warten verbringt verschwendet. (1 P)Busy waiting (0.5 P) and sleep + wakeup (or blocking) (0.5 P).Only sleep/wakeup makes sense on a single-processor system. While busy waiting,the lock holder cannot make progress towards releasing the lock because the waitingthread occupies the single CPU. Thus, this time spent busy waiting is wasted. (1 P)
• Betrachten Sie den Pseudocode für Interprozesskommunikation (IPC) in Listing 1. Klassifizieren Sie die hier eingesetzte IPC möglichst präzise nach den Begriffen der Vorlesung. (2 pt) Consider the pseudocode for interprocess communication (IPC) in Listing 1. Describe the IPC mechanism used here as specific as possible using the classification terms from the lecture. char ∗ msg = ” He l lo World ! ” ; mqd t mq = mq open ( ”my message queue ” , O NONBLOCK | O CREAT | ORDWR ) ; mq setattr (mq, maxmsg=32 /∗ queue capaci ty ∗/ , msgsize =512); mq send (mq, msg, s t r l en (msg ) , 0 ) ; Listing 1 Indirekt (0,5 P) Meldung übergeben (0,5 P) (a.k.a. indirektes Messaging), die in einem nonblocking verwendet wird/ Asynchron (0,5 P) Mode, mit beschränkten Puffern (0,5 P).Indirect (0.5 P) message passing (0.5 P) (a.k.a. indirect messaging), used in a nonblocking/ asynchronous (0.5 P) fashion, with bounded buffers (0.5 P).
• Betrachten Sie das in Abbildung 1 dargestellte System und die zukünftigen Systemaufrufe der drei Prozesse in Listing 2. Befindet sich das System in einem sicheren Zustand (safe state)? Begründen Sie Ihre Antwort. (3 pt) Consider the system depicted in Figure 1 and the three processes’ future system calls in Listing 2. Is the system in a safe state? Explain why. SIEHE ABBILDUNG IN AUFGABE 3 e) VOM 3.3.2016!!!!!!!!!!!!!!!!!!!! Ja, das System befindet sich in einem sicheren Zustand (1 P), da alle Prozesse bis zur Fertigstellung laufen können(0,5 P) in der Reihenfolge P3 (0,5 P) (Freisetzungen R2), P1 (0,5 P) (R2 erhält dann R1 Und R2) und schließlich P2 (0,5 P) (erhält und gibt dann beide Ressourcen frei).Yes, the system is in a safe state (1 P) because all processes can run to completion(0.5 P) in the order P3 (0.5 P) (releases R2), P1 (0.5 P) (acquires R2 then releases R1and R2), and finally P2 (0.5 P) (acquires and then releases both resources).
• Nennen Sie die zwei grundsätzlichen Kommunikationsmodelle der Interprozesskommunikation. Hinweis: Gefragt sind nicht die verschiedenen Designparameter, sondern die grundlegenden Modelle. (1 pt) Enumerate the two fundamental models of interprocess communication (IPC). Note: We do not ask for the various design parameters, but for the fundamental models. • gemeinsamer Speicher (0,5 P)• Nachrichtenübergabe (0,5 P)• shared memory (0.5 P)• message passing (0.5 P)
• Welches Kommunikationsmodell können die Threads eines Prozesses immer implizit nutzen? Erläutern Sie warum. (2 pt) Which is the IPC model that threads of a process can always use implicitly? Explain why. Threads können immer Shared Memory (1 P) für die Kommunikation innerhalb eines Prozesses verwenden.Als Teil des gleichen Prozesses, laufen sie im gleichen virtuellen Adressraumund damit teilen sie implizit alle virtuellen Speicher die sichtbar für sie sind. (1 P)Wir erwarten, dass du mehr formale Begriffe verwendest und genauer bist als nur "ThreadsTeilen den Speicher ". Weiterhin solltest du zwischen Laufzeit / Bibliothek Konstrukten unterscheiden können wie der heap und die OS-vorgesehene gemeinsame virtuelle AS.Threads can always use shared memory (1 P) for communication within a process.Being part of the same process, they are running in the same vrtual address spaceand thus they implicitly share all virtual memory visible to them. (1 P)We expect you to use more formal notions and be more precise than just ”threadsshare the memory”. Further, you should be able to discern between runtime/libraryconstructs such as the heap and the OS-provided common virtual AS.
• Was wird benötigt, um in einem System gleichzeitig nicht-blockierendes Senden und nicht-blockierendes Empfangen für die Interprozess-Kommunikation zu unterstützen? Erklären Sie, warum. Nennen Sie einen hierbei zu wählenden Design-Parameter und erläutern Sie, warum dieser kritisch ist. (3 pt) What is required to support both non-blocking send and non-blocking receive in interprocess communication? Explain why. State one of the design parameters that is introduced thereby. Explain why you need to choose that parameter carefully. Die Unterstützung sowohl des nicht blockierenden Sende- als auch des Empfangs erfordert das Puffern (Warteschlangen). (0,5 P)Meldungen müssen in einem Puffer gespeichert werden, da zwischen dem nicht blockierenden senden und dem entsprechenden Empfangsvorgang eine beliebige Zeitspanne liegt. Wir können die anfängliche Kopie der Nachricht (im Absender AS) nicht annehmen, um verfügbar zu sein in der Empfangszeit, weil der Absender es zerstören kann, sobald die nicht blockierende Sendeoperation gelingt. (1 P)Ein zusätzlicher Helper-Thread ist in diesem Szenario ist keine gültige Lösung!Die Warteschlange führt den Parameter der Pufferkapazität ein, der vorsichtig gewählt werden muss. (0,5 P)Mit einer gewählten beschränkten Kapazität muss ein Absender warten, sobald alle Puffer besetzt sind, wodurch das Nicht-Blocking-Senden zu einer Sperr-Sendeoperation herabgestuft wird. Mit unbegrenzter Kapazität für nicht ausgelieferte Nachrichten, wird der Absender nie warten müssen.Der Pufferraum kann den Betrag des verfügbaren Speichers übersteigen. (1 P) (Sie könnendieses Problem lindern, indem der Sender oder der Empfänger Pufferplatz zur Verfügung stellt)Ein weiterer Entwurfsparameter ist der Ort der Puffer (0,5 P)Nachrichtenpuffer können sich befinden inEmpfänger AS: Wenn die Anzahl der Clients steigt, kann sich die Anzahl der Nachrichten an diese Empfänger erhöhen, so dass ein immer größerer Empfangsbereich erforderlich ist. Wenn der Empfang Bereich ist nicht groß genug ist, werden viele IPCs entweder versagen und wiederholt werden (verdoppeln dieIPC Overhead) oder den Absender blockieren , wodurch das unerwünschte asynchrone senden in ein synchrones wechselt.Kernel: Schädliche oder gefälschte Threads könnten den Kernel mit Nachrichten überschwemmen, also müssen wir das Ausmaß der Puffergröße mit ähnlich begrenzen wie bei den empfängerbasierten Puffern. Kernbasierte Puffer können Chancen bieten für Denial-of-Service-Angriffe, wenn sie nicht richtig implementiert sind.Absender AS: Der Absender hat sowieso die Nachricht gesendet. Wenn wir denursprünglichen Nachrichtenspeicher als Nachrichtenpuffer benutzen, muss die Anwendung benachrichtigt werden sobald die Nachricht vom Empfänger verbraucht wurde, damit der Speicher freigegeben oder wiederverwendet werden kann.Alternativ können wir die Nachricht auch in einen separaten Sendepuffer kopieren.Ein asynchrones Senden kann die Nachricht nicht sofort liefern. Dieser Ansatzwürde es der Anwendung erlauben, den ursprünglichen Nachrichtenspeicher zu überschreiben mit den Kosten für eine (zusätzliche) Kopie der Nachricht.Sender-basierte Pufferung sind ausgewogen, da nur die sendenden Prozesse für ihre Kommunikationsanforderungen bezahlen; Anwendungen, die selten mit anderen Threads kommunizieren werdenaufgrund unzureichender Pufferplätze niemals blockieren. (1 P)Supporting both non-blocking send and receive requires buffering (queueing). (0.5 P)Messages have to be stored in a buffer because an arbitrary amount of time couldpass between the non-blocking send and the corresponding receive operation. Wecannot assume the initial copy of the message (in the sender’s AS) to be available atreceive time because the sender may destroy it once the non-blocking send operationsucceeds. (1 P)An additional helper thread is not a valid solution in this scenario!Queueing introduces the parameter of buffer capacity, which needs to be chosencarefully. (0.5 P)With a chosen bounded capacity, a sender has to wait once all buffers are occupied,thereby degrading the non-blocking send to a blocking send operation. Withunbounded capacity for undelivered messages, the sender will never have to wait.Buffer space may exceed the amount of available memory, though. (1 P) (You mayalleviate this issue by having the sender or the receiver provide buffer space)Another design parameter is the location of buffers (0.5 P)Message buffers can be located inreceiver AS: If the number of clients rises, the number of messages sent to thisreceiver might increase, thus requiring an ever larger receive area. If the receivearea is not large enough, many IPCs will either fail and be repeated (doubling theIPC overhead) or block the sender, turning the asynchronous send undesirablyinto a synchronous one.kernel: Malicious or bogus threads might flood the kernel with messages, thus wewould need to impose limits on the message buffer size with consequences similarto the receiver-based buffers. Kernel-based buffers can provide opportunitiesfor denial-of-service attacks if not implemented properly.sender AS: The sender has stored the to-be-sent message anyways. If we use theoriginal message memory as message buffer, the application needs to be notifiedonce the message has been consumed by the receiver so that the memory canbe released or reused.Alternatively, we might copy the message to a separate sent-message buffer iffan asynchronous send cannot deliver the message instantaneously. This approachwould allow the application to overwrite the original message memory atthe cost of requiring an (additional) copy of the message.Sender-based buffering scales well, as only the sending processes pay for theircommunication requirements; applications that seldom communicate with otherthreads will never block due to insufficient buffer space. (1 P)
• Nennen Sie drei Nachteile von einfachen Spinlocks bzw. Semaphoren und erläutern Sie jeweils, wie der jeweils andere Mechanismus diesen Nachteil behebt. (3 pt) Give three disadvantages of simple spinlocks and/or semaphores. Explain how the respective other mechanism improves on the problem • Spinlocks bieten keine beschränkte Wartezeit, weil das beschäftigte Warten keine Reihenfolge garantiert, in der Threads das Schloss erwerben können. (0,5 P)Starke Semaphoren wecken Threads in der Reihenfolge auf, in der sie diese angerufen haben, und damit begrenzte Wartezeit erreichen(0,5 P) (Ticket Spinlocks sind auch ok.)• Semaphoren erfordern einen Systemaufruf, auch wenn der Thread sofort ablaufen         könnte(0,5P)Spinlocks hingegen können im Userpace komplett implementiert werdenund brauchen keine syscalls, Sie sind sehr effizient für kurze Wartezeiten. (0,5 P)• Spinlocks verschwenden Ressourcen während dem beschäftigten warten, wenn die Wartezeit lang ist. Kein anderer Thread kann nützliche Arbeit an der CPU leisten, wo ein Thread beschäftigt wartet. (0,5 P)Im Gegensatz dazu blockieren Semaphoren Wartethreads und stellen damit sofort die CPU zur Verfügung für andere Threads . (0,5 P)• Nicht-Fragen: Semaphoren können mehrere Threads zählen und zulassen. Aber dasist für kritische Abschnitte nicht geeignet. Alle praktischen Architekturen mit MultiprozessorImplementierungen bieten eine Form der atomaren Read-Modify-Write-Operation.Spinlocks, die atomare Operationen erfordern, sind kein Nachteil (weiter benötigen Siediese auch für die Implementierung von Semaphoren auf einem Multiprozessorsystem).• Spinlocks do not provide bounded waiting because busy waiting does not guaranteean order in which threads acquire the lock. (0.5 P)Strong semaphores wake up threads in the order they called wait, and therebyprovide bounded waiting. (0.5 P) (Ticket spinlocks are also ok.)• Semaphores require a system call even when the thread may proceed immediately.(0.5 P)Spinlocks on the other hand can be implemented completely in userspace anddo not require syscalls. They are very efficient for short wait times. (0.5 P)• Spinlocks waste resources in busy waiting when the wait time is long. No otherthread can do useful work on the CPU where a thread is busy waiting. (0.5 P)In contrast, semaphores block waiting threads and thereby make the CPU availablefor other threads immediately. (0.5 P)• Non-issues: Semaphores can count and admit several threads. However, thatis not viable for critical sections. All practical architectures with multiprocessorimplementations offer some form of atomic read-modify-write operation. Thus,spinlocks requiring atomic operations is not a disadvantage (Further, you needthem for implementing semaphores on a multiprocessor system as well).
• Betrachten Sie das Code-Beispiel in Listing 2. Jeweils ein Thread führt die Funktion thread1() bzw. thread2() aus. Consider the code example in Listing 2. Each of the functions thread1() and thread2() is executing in its own thread. Listing 2 int l , m; void thread1 ( ) { void thread2 ( ) { int key ; int key ; do { do { X1 : wait (m) ; key = 1 ; key = 1 ; Y1 : while ( key ) swap(& l , &key ) ; X2 : while ( key ) swap(& l , &key ) ; Y2 : wait (m) ; l o n g a c t i v i t y ( ) ; // takes 5ms s h o r t a c t i v i t y ( ) ; // takes 1ms X3 : l = 0 ; Y3 : s igna l (m) ; X4 : s igna l (m) ; Y4 : l = 0 ; } while ( 1 ) ; } while ( 1 ) ; } } Wie heissen die Synchronisationsmechanismen, die in Listing 2 zum Einsatz kommen? (2 pt) How do we call the synchronization primitives used in Listing 2? Bei X1/X4 und Y2/Y3: Semaphore (oder Mutex) (1 P)Bei X2/X3 und Y1/Y4: Spinlock (1 P) (atomic operations (0.5 P) )
• Betrachten Sie das Code-Beispiel in Listing 2. Jeweils ein Thread führt die Funktion thread1() bzw. thread2() aus. Consider the code example in Listing 2. Each of the functions thread1() and thread2() is executing in its own thread. Listing 2 int l , m; void thread1 ( ) { void thread2 ( ) { int key ; int key ; do { do { X1 : wait (m) ; key = 1 ; key = 1 ; Y1 : while ( key ) swap(& l , &key ) ; X2 : while ( key ) swap(& l , &key ) ; Y2 : wait (m) ; l o n g a c t i v i t y ( ) ; // takes 5ms s h o r t a c t i v i t y ( ) ; // takes 1ms X3 : l = 0 ; Y3 : s igna l (m) ; X4 : s igna l (m) ; Y4 : l = 0 ; } while ( 1 ) ; } while ( 1 ) ; } } Welche Eigenschaft muss die Funktion swap in den Zeilen X2 und Y1 haben, damit der Synchronisationsmechanismus korrekt funktioniert? Welches Kriterium für eine Losung des Problems kritischer Abschnitte wird dadurch gewährleistet? (2 pt) Which property of the function swap does a correct implementation of the synchronization primitive require? Which of the criteria for a solution to the critical-section problem is thereby guaranteed? Swap muss atomar sein (1 P), wodurch ein gegenseitiger Ausschluss (1 P) für den Spinlock gewährleistet wird.swap must be atomic (1 P) , thereby guaranteeing mutual exclusion (1 P) for the spinlock.
• Anzeige
• Betrachten Sie das Code-Beispiel in Listing 2. Jeweils ein Thread führt die Funktion thread1() bzw. thread2() aus. Consider the code example in Listing 2. Each of the functions thread1() and thread2() is executing in its own thread. Listing 2 int l , m; void thread1 ( ) { void thread2 ( ) { int key ; int key ; do { do { X1 : wait (m) ; key = 1 ; key = 1 ; Y1 : while ( key ) swap(& l , &key ) ; X2 : while ( key ) swap(& l , &key ) ; Y2 : wait (m) ; l o n g a c t i v i t y ( ) ; // takes 5ms s h o r t a c t i v i t y ( ) ; // takes 1ms X3 : l = 0 ; Y3 : s igna l (m) ; X4 : s igna l (m) ; Y4 : l = 0 ; } while ( 1 ) ; } while ( 1 ) ; } } Welcher unerwünschte Systemzustand kann in diesem Szenario auftreten? Illustrieren Sie diesen Zustand mit einer geeigneten graphischen Repräsentation aus der Vorlesung. Verwenden Sie als Beschriftungen die Bezeichner aus Listing 2. (3 pt) Which undesired system state could arise in this scenario? Illustrate that state using an appropriate graphical representation from the lecture. Use the identifiers from Listing 2 as labels. Undesired system state: Illustration: Deadlock (1 P) ; Vertices of RAG (1 P) ; Edges of RAG (1 P) T1 ------> L ------> T2   ^                          /    \                        /     \                     /       \                 /             m    <  
• Betrachten Sie das Code-Beispiel in Listing 2. Jeweils ein Thread führt die Funktion thread1() bzw. thread2() aus. Consider the code example in Listing 2. Each of the functions thread1() and thread2() is executing in its own thread. Listing 2 int l , m; void thread1 ( ) { void thread2 ( ) { int key ; int key ; do { do { X1 : wait (m) ; key = 1 ; key = 1 ; Y1 : while ( key ) swap(& l , &key ) ; X2 : while ( key ) swap(& l , &key ) ; Y2 : wait (m) ; l o n g a c t i v i t y ( ) ; // takes 5ms s h o r t a c t i v i t y ( ) ; // takes 1ms X3 : l = 0 ; Y3 : s igna l (m) ; X4 : s igna l (m) ; Y4 : l = 0 ; } while ( 1 ) ; } while ( 1 ) ; } } Wie konnten Sie das Problem durch Ändern der mit Labels markierten Zeilen (X1- 4 und Y1-4) in Listing 2 lösen? Entfernen Sie keinen Code. Welchem allgemeinen Konzept zur Lösung dieses Problems entspricht Ihr Vorgehen? Nennen Sie sowohl das Konzept als auch die übergeordnete Kategorie. (3 pt) How could you solve this problem by modifying the lines with labels (X1-4 and Y1-4) in Listing 2? Do not remove code. To which concept for solving this problem does your modification relate to? Name both the concept and the more general category. Austauschlinien Y1 und Y2 und Y3 und Y4 (1 P). Diese Änderung implementiert Ressourcen(1 P), die eine Technik für Deadlock-Prävention (1 P) sind.Exchange lines Y1 and Y2, and Y3 and Y4 (1 P) . This modification implements resourceordering (1 P) , which is one technique for deadlock prevention (1 P) .
• Betrachten Sie das Code-Beispiel in Listing 2. Jeweils ein Thread führt die Funktion thread1() bzw. thread2() aus. Consider the code example in Listing 2. Each of the functions thread1() and thread2() is executing in its own thread. Listing 2 int l , m; void thread1 ( ) { void thread2 ( ) { int key ; int key ; do { do { X1 : wait (m) ; key = 1 ; key = 1 ; Y1 : while ( key ) swap(& l , &key ) ; X2 : while ( key ) swap(& l , &key ) ; Y2 : wait (m) ; l o n g a c t i v i t y ( ) ; // takes 5ms s h o r t a c t i v i t y ( ) ; // takes 1ms X3 : l = 0 ; Y3 : s igna l (m) ; X4 : s igna l (m) ; Y4 : l = 0 ; } while ( 1 ) ; } while ( 1 ) ; } } Im Code-Beispiel in Listing 2 schützen offenbar zwei Synchronisationsmechanismen einen kritischen Abschnitt. Im hier beschriebenen Szenario ist einer davon unnötig. Welchen der beiden Mechanismen würden Sie auf einem Einprozessorsystem bevorzugen? Erläutern Sie warum. (2 pt) In the example in Listing 2 apparently two synchronization primitives protect one critical section. In the scenario we describe here, one of them is unnecessary. Explain why you would prefer one of them over the other on a uniprocessor system. Wir bevorzugen den Semaphor über dem Spinlock (0,5 P), da er nicht beschäftigt wartet(0,5 P). Stattdessen blockiert das Semaphor den Wartethread, so dass andere ThreadFortschritte machen können. Bei einem Uniprozessorsystem kann der Lockholder-Thread keinen  Fortschritt und Freigabe der Sperre machen, während ein anderer Thread beschäftigt ist und auf den Spinlock wartet (1 P).We prefer the semaphore over the spinlock (0.5 P) , as it does not use busy wait(0.5 P) . Instead, the semaphore blocks the waiting thread, so that other threadscan make progress. On a uniprocessor system, the lockholder thread cannot makeprogress and release the lock while another thread is busy-waiting for the spinlock(1 P) .
• Nennen und erläutern Sie kurz die drei notwendigen Bedingungen für eine gültige Lösung des Problems kritischer Abschnitte. (3 pt) Name and briefly explain the three requirements for a valid solution of the critical section problem. • Gegenseitiger Ausschluss: Nur ein Thread kann zu einem Zeitpunkt in einem kritischen Abschnitt sein.• Fortschritt:   - Wenn kein Prozess in einem kritischen Abschnitt ist, wird einer der Prozesse die                      versuchen einzusteigen, eventuell einzusteigen.   - Prozesse, die nicht versuchen, einen kritischen Abschnitt zu betreten, behindern keine Prozesse die versuchen, es zu betreten.• Begrenztes Warten: Sobald ein Thread beginnt, einen kritischen Abschnitt einzugeben, gibt      es eine begrenzung der Anzahl an Zeiten, in denen andere Threads hereinkommen.• Mutual exclusion: only one thread can be in a critical section at a time.• Progress:   – If no process is in a critical section, one of the processes trying to enter it will eventually g         get in.   – Processes that are not trying to enter a critical section do not hinder processes      that try to enter it from getting in.• Bounded waiting: once a thread starts trying to enter a critical section, there is  a bound on the number of times other threads get in.
• Erklären Sie warum es auf Multiprozessor-Systemen im Allgemeinen nicht ausreicht, Unterbrechungen zu deaktivieren um das Problem kritischer Abschnitte zu lösen. Welche Anforderung an eine gültige Lösung wird nicht erfüllt? (2 pt) Explain why disabling interrupts does not generally suffice to solve the critical section problem on multiprocessor systems. Which requirement for a valid solution is not satisfied? • Bei Multiprozessorsystemen ist das Deaktivieren des Interrupts eines Prozessors nicht ausreichend zwischen ihnen bei dem betreten von kritischen Abschnitten zum synchronisieren und gegenseitigem Ausschluss (1P) . So wie Threads echt parallel laufen(auf verschiedenen Kernen),  können Threads zu jeder Zeit gleichzeitig in einem kritischen Abschnitt sein (mit Interrupts aber etwas behindert ). (1P)• On multiprocessor systems, disabling interrupts of a processor is not sufficientto synchronize and provide mutual exclusion (1P) between them in entering criticalsections. As threads are running truely in parallel (on different cores), atany time, threads can be in a critical section at the same time (with interruptsdisabled though). (1P)
• Ein Spinlock kann wie folgt auf Basis einer atomaren swap-Instruktion implementiert sein. A spinlock might be implemented based on an atomic swap instruction as follows. 1 int volatile spinlock; 2 3 void lock(int volatile * spinlock) { 4 int key = 1; 5 6 while ( *spinlock != 0 ) ; 7 while( key ) 8 Swap(spinlock, &key); 9 } 10 11 void unlock(int volatile * spinlock) { *spinlock = 0; } a) Erklaren Sie knapp, warum die Variable spinlock als volatile deklariert ist. (1 pt) Explain briefly why the variable spinlock is declared volatile. b) Unter welchem Umstanden performt diese Spinlock-Implementierung schlecht wenn mehrere Threads folgenden Code ausfuhren? (2 pt) Under which circumstances does this spinlock implementation exhibit poor performance if multiple threads run the following code? void thread() { while (1) { lock(&spinlock); // c r i t i c a l sec tion unlock(&spinlock); // remainder sec tion } } c) Erklaren Sie welche einfache Änderung im Code das beschriebene Performanz- Problem löst, und warum. (2 pt) Explain briefly, which minor change in the code solves the illustrated performance issue, and why.  a)Es ist impulsiv, mit dem laufenden Code den aktuellen Wert aus dem Speicher zu holen            (was zwischen gespeichert werden kann) bei jedem Lesen.• It is volatile to make the running code fetch the current value from memory (whichmight be cached) on every read. (1P) b)Falls alle Kerne eines Multi-Core Caches auf dem gemeinsamen Speicher reserviert sind(0,5P) und der Spinlock von einem Thread gehalten wird(auf einem Kern) und mehr als ein weiterer Thread (läuft auf anderen Kernen) versucht, das Schloss (0.5P) zu erwerben,  können kontinuierlich Cache-Line-Invalidierungen verursacht werden. (1P)• In case all cores of a multi-core have dedicated caches on the shared memory(0.5P) and the spinlock is held by one thread (running on one core) and more thanone more thread (running on other cores) try to acquire the lock (0.5P), continuouscache-line invalidations can be caused. (1P)c)1 int volatile spinlock = 0; /∗ i n i t i a l i z e to f r e e ∗/23 void lock(int volatile * spinlock) {4         int key = 1; /∗ occupied s ta te ∗/56         while (key) { /∗ while lock i s held ∗/7                 while ( *spinlock != 0 ) ; /∗ while lock i s held ∗/89                 Swap(spinlock, &key); /∗ t ry to acquire lock ∗/10         }11 }1213 void unlock(int volatile * spinlock) {14         *spinlock = 0; /∗ release lock ∗/15 }Situation revisited: falls der Spinlock von einem Thread gehalten wird (läuft auf einemKern) und mehr als ein weiterer Thread (läuft auf andere Kerne) versucht, das Schloss zu erwerben.• Um das Leistungsproblem zu beheben: tauschen Sie die while-Loops aus. (1P)• Das Problem ist jetzt nicht mehr vorhanden.- Wenn diese Threads versuchen, die Sperre zu erwerben, sind sie in erster Linie beim               beschäftigten warten. Da die Threads nur den Spinlock-Wert lesen, entsteht so weit kein         Performance-Problem.- Wenn der aktuelle Thread die Sperre freigibt, indem der Spinlock wieder einsetzt,  können andere Threads  parallel vorran gehen. Ein Thread wird  Das Schloss erwerben, und die anderen gehen zurück zu beschäftigtem warten. (1P)• Situation revisited: in case the spinlock is held by one thread (running on onecore) and more than one more thread (running on other cores) try to acquire thelock.• To fix the performance problem: exchange the while-loops. (1P)• Problem is gone now– When these thread try to acquire the lock, in the first place, they are busywaiting. As the threads only read the spinlock value, no performance issuearise so far.– When the current thread releases the lock by re-setting spinlock, again the   other threads may step forward truely in parallel. One thread will acquire   the lock, and the others will fall back to busy waiting. (1P)
• Erweitern Sie die in der vorherigen Teilaufgabe gegebenen lock- und unlock-Funktionen, so dass sie im Kontext des folgenden Beispiels alle drei notwendigen Bedingungen aus Teilaufgabe (a) erfüllen. (3 pt) Extend the lock and unlock functions given in the previous sub-task, such that they fullfil all three necessary conditions of sub-task (a) in the context of the following example. int is_waiting(thread_id_t i); int set_waiting(thread_id_t i, int wait_state); thread_id_t get_next_waiting(thread_id_t i); void thread(thread_id_t id) { while (1) { lock(&spinlock, id); // c r i t i c a l sec tion unlock(&spinlock, id); // remainder sec tion } } void lock(int volatile * spinlock, int id) { int key = 1; set_waiting(id, 1); set_waiting(id, 0); } void unlock(int volatile * spinlock, int id) { thread_id_t next = get_next_waiting(id); if (next == id) } 1 void lock(int volatile * spinlock, int id) {2          int key = 1;34          set_waiting(id, 1);56          while (is_waiting(id) && key) {7                while ( is_waiting(id) && *spinlock != 0 ) {};89                Swap(spinlock, &key);10         }1112         set_waiting(id, 0);13 }1415 void unlock(int volatile * spinlock, int id) {16         thread_id_t next = get_next_waiting(id);1718        if (next == id) {19              spinlock = 0;20        } else {21              set_waiting(next, 0);22        }23 }
• Was sind die 4 notwendigen Bedingungen für einen Deadlock? (2 pt) What are the 4 necessary conditions for a deadlock? Die Frage kommt öfters vor!!! • Gegenseitiger Ausschluss (+ 0,5P)• Halten und warten (+ 0,5P)• Keine Vorbeugung (+ 0,5P)• Kreiswarte (+ 0,5P)• Mutual exclusion (+0.5P)• Hold and wait (+0.5P)• No preemption (+0.5P)• Circular wait (+0.5P)
• Nennen und erläutern Sie kurz die drei notwendigen Bedingungen für eine gültige Lösung des Problems kritischer Abschnitte. ( 3 pt) Enumerate and briefly explain the three requirements for a valid solution of the critical section problem. Ist schon mehrmals als Frage vorgekommen!!!!!!! (A) Gegenseitiger Ausschluss: Nur ein Thread kann in der CS zu einem Zeitpunkt sein. (Darf nicht mehr sein als 1! Wenn Sie nur die Anzahl der Threads einschränken, die das CS  in einer gegebenen Zeit erreichen können, könnte man am Ende mit mehreren Threads in der CS zur gleichen Zeit enden)(B) Fortschritt:• Wenn kein Prozess in der CS ist, wird einer der Prozesse, die versuchen rein zu kommen, schließlich reinkommen.• Prozesse, die nicht eingehen wollen, behindern nicht die Prozesse, die versuchen   hereinzukommen.Wenn kein Prozess in seiner kritischen Sektion ausgeführt wird und es mehrere ausgeführte Prozesse gibt die die kritische Sektion betreten wollen, dann werden nur die übrigen Prozesse die nicht ausgeführt werden zum Entscheiden gebracht welcher Prozess die kritische Sektion als nächstes betritt.Diese Selektion kann nicht unendlich hinausgeschoben werden.Wenn eine Gefahr versucht die kritische Sektion zu betreten ist da ein Bound auf die Anzahl wie viel andere Gefahren betreten können.Ein bound muss auf der Basis existieren von der Anzahl wie oft es anderen Prozessen erlaubt ist die kritische Sektion zu betreten. Nachdem ein Prozess ein Anfrage gestartet hat die die kritische Sektion zu betreten und bevor die Anfrage akzteptiert wurde.0,5pt für jede Vorstellung, 0,5pt für jede korrekte und passende Erklärung.(a) Mutual exclusion: Only one thread can be in the CS at a time. (must not be morethan 1! If you only limit the number of threads that can enter the CS at anygiven time, you may end up with several threads in the CS at the same 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.If no process is executing in its critical section and there exist some processesthat wish to enter their critical sections, then only those processes that are notexecuting in their remainder sections can participate in deciding which will enterits critical section next, and this selection cannot be postponed indefinitely.(c) Bounded waiting: Once a thread starts trying to enter the critical section, there isa bound on the number of times other threads get in. A bound must exist on thenumber of times that other processes are allowed to enter the critical sectionsafter a process has made a request to enter its critical section and before thatrequest is granted.0.5pt for each notion, 0.5pt for each correct and matching explanaton.
• Gegeben ist ein System mit 2 Threads, die 3 Semaphoren zum Schutz kritischer Abschnitte verwenden. Thread i führe jeweils die Funktion thread i() aus Listing 2 (auf der nächsten Seite) aus. In dem System gibt es keine weitere Aktivität. Geben Sie für jede der Bedingungen für Deadlocks an, ob diese beim Zugriff auf die Semaphoren in diesem System erfüllt ist und begründen Sie jeweils Ihre Antwort. (5 pt) Given a system with 2 threads that use 3 semaphores to protect critical sections. Each thread i executes function thread i() in Listing 2 (on the following page) respectively. There is no other activity in the system. For each condition for deadlocks, state whether it is fulfilled or not regarding the use of semaphores in this system, and explain your answer. Konnen Deadlocks in diesem System auftreten? Begr ¨ unden Sie Ihre Antwort. ¨ Can deadlocks occur in this system? Explain. • Gegenseitiger Ausschluss: Ja (+ 0,5p), kritische Abschnitte sind exklusiv; Die semaphoren        werden Verwendet, um sie zu schützen. (+ 0,5P)• Halten und warten: Ja (+ 0.5P), kritische Abschnitte sind verschachtelt / threads warten aufSemaphoren, um sie als Schlösser zu erwerben, nachdem sie auf andere Semaphoren gewartet haben. (+ 0,5P)• Keine Vorbeugung: Ja (+ 0.5P), Threads hinterlassen kritische Abschnitte nur freiwillig / nein  eine neben den beteiligten threats kann die Semaphoren (+ 0,5P) signalisieren.• Zirkuläres warten: Nein (+ 0,5P); Die Reihenfolge der Ressourcenzuteilung wartet auf Semaphoren.Es führt nicht zu Zyklen in der RAG / es ist eine Ressourcenbestellungspolitik vorhanden/ Beide Threads warten auf Semaphoren in der Reihenfolge S2, S3. (+ 0,5P)Deadlocks können in diesem System nicht auftreten (+ 0,5P), weil eine der notwendigen Bedingungen für einen Deadlock nicht erfüllt ist(+ 0.5P).• Mutual exclusion: Yes (+0.5p), critical sections are exclusive; the semaphores areused to protect them. (+0.5P)• Hold and wait: Yes (+0.5P), critical sections are nested / threads wait() onsemaphores to acquire them as locks after they have wait()ed on other semaphores.(+0.5P)• No preemption: Yes (+0.5P), threads leave critical sections only voluntarily / noone besides the involved threads can signal the semaphores (+0.5P).• Circular wait. No (+0.5P); the order of resource allocation (wait()s on semaphores)does not lead to cycles in the RAG / there is a resource ordering policy in place/ both threads wait() on semaphores in the order S2, S3. (+0.5P)Deadlocks cannot occur in this system (+0.5P) because one of the necessary conditionsfor a deadlock is not fulfilled (+0.5P).                                            Listing 2:Semaphore S1 , S2 , S3 ;vo id thread 1 ( )                    void thread 2 ( ){                                             {       wait ( S1 ) ;                             wait ( S3 ) ;       wait ( S3 ) ;                             wait ( S2 ) ;       signal ( S1 ) ;                          signal ( S3 ) ;       wait ( S2 ) ;                              //X //X      signal ( S3 ) ;                            signal ( S2 ) ;      signal ( S2 ) ;}                                             }
• Zeichnen Sie den Ressource Allocation Graph (RAG) für die Threads aus Listing 2 mit den Semaphoren als Ressourcen, zu dem Zeitpunkt, an dem die Threads an den mit X markierten Stellen in Ihrer Ausführung unterbrochen wurden. (3 pt) Draw the Resource Allocation Graph (RAG) for the threads from Listing 2 with the semaphores as resources, at the moment the threads have been interrupted at the position marked with an X.                     S1                       T1--> S2--> T2               ^                 \                     S3
• Welche Hardware-Mechanismen werden typischerweise auf Einprozessorsystemen zur Implementierung von Synchronisation im Betriebssystem verwendet, welche auf Mehrprozessorsystemen? (1 pt) Which hardware mechanisms are typically used on single-processor systems to implement synchronization in the operating system? Which mechanisms are used on multi-processor systems? • Uniprozessor: Deaktivieren von Interrupts (+ 0,5P).• Multiprozessor: Atomanweisungen / Interprozessor-Interrupts   (+ 0,5P, eins ist ausreichend)• Uniprocessor: Disabling interrupts (+0.5P).• Multiprocessor: Atomic instructions / inter-processor interrupts (+0.5P, one is  sufficient)
• Warum greift testAndSet auf den Hauptspeicher und nicht auf ein weiteres Register zu? Begründen sie Ihre Antwort mit einem Szenario, wofür testAndSet typischerweise eingesetzt wird. (1 pt) Why does testAndSet access main memory and not another register instead? Explain using a scenario where testAndSet is typically used. Der Registersatz ist privat für einen Thread und CPU-local (+ 0.5P). TestAndSet wird typischerweise Verwendet für die Synchronisation zwischen mehreren CPUs, also muss es über Threads und über CPUs sichtbar sein(+ 0.5P).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).
• Welche Abstraktion wird vom Betriebssystem für das Multiplexen von CPUs bereitgestellt? (0.5 pt) What abstraction does the operating system supply for multiplexing CPUs? Das Betriebssystem abstrahiert CPUs mit Prozessen und Threads (0,5 P). EntwederProzess oder Thread genügt.The operating system abstracts CPUs with processes and threads (0.5 P). Eitherprocess or thread is sufficient.
• Was versteht man unter der Trap Instruktion? Ist diese privilegiert? (1.5 pt) What is the trap instruction? Is is privileged? Der Trap-Befehl schaltet den Prozessor auf den privilegierten Modus (0,5 P) und fährt mit der Ausführung an einem vom Betriebssystem definierten Standort fort. Es wird verwendet, um System calls zu implementieren (0,5 P) und ist somit nicht privilegiert (0,5 P).The trap instruction switches the processor to privileged mode (0.5 P) and continuesexecution at an operating system defined location. It is used to implement systemcalls (0.5 P) and is thus not privileged (0.5 P).
• Nennen Sie eine Betriebssystemfunktion für die üblicherweise kein Eintritt in den Kern notwendig ist. Begründen Sie Ihre Antwort. (1.5 pt) Give an operating system function that typically does not require entering the kernel. Explain your answer. malloc (0,5 P). Der Heap-Allokator wird in der Regel in einer User-Space-Bibliothek implementiert und ruft nur in den Kernel, wenn dem heap der Speicher ausgeht (1 P) .Ein weiteres Beispiel: GetTickCount. Empfangen der Anzahl der Zeichen seit dem dasSystem billig und schnell sein muss. Der Kernel bildet daher eine Seite mit deraktuellen Tickzahl an einem bekannten Ort in jeden Prozess.Andere Antworten werden akzeptiert, wenn sie richtig erklärt werden.malloc (0.5 P). The heap allocator is usually implemented in a user-space library andonly calls into the kernel if the heap ran out of memory (1 P).Another example: GetTickCount. Receiving the number of ticks since the start of thesystem must be cheap and quick. The kernel therefore maps a page containing thecurrent tick count at a known location into each process.Other answers are accepted if properly explained.
• Was sind race conditions? Wie können diese vermieden werden? (2 pt) Explain the term race condition. How can race conditions be avoided? Frage kommt öfters vor!!!!!!!!!!!!!! Gleichzeitiger Zugriff auf gemeinsame Daten durch verschiedene Threads (0,5 P) kann zu falschen Ergebnissen führen. (0,5 P)Alternativ: Berechnete Ergebnisse hängen von der gleichzeitig abgeschlossenen Ausführungsreihenfolge der laufenden Threads oder Prozesse ab. (1 P)Das Schützen kritischer Abschnitte (0,5 P) mit Synchronisationsmechanismen (0,5 P) vermeidet race conditions.Concurrent access to shared data by different threads (0.5 P) can lead to wrongresults. (0.5 P)Alternatively: Computed results depend on the execution order of involved concurrentlyrunning threads or processes. (1 P)Protecting critical sections (0.5 P) with synchronization mechanisms (0.5 P) avoidsrace conditions.
• Wie implementiert man typischerweise Synchronisation auf einem Einprozessorsystem? Nennen Sie zwei Beschränkungen bzw. Nachteile dieses Ansatzes. (2 pt) How do we typically implement synchronization on a single-processor system? State two limitations and disadvantages of that approach. Bei einem Einzelprozessorsystem ist die Deaktivierung von Interrupts ausreichend, um gegenseitig einen Ausschluss zu erreichen. (1 P)Dieser Ansatz hat mehrere Nachteile:• Wir können den Benutzerraum nicht erlauben, Interrupts zu deaktivieren, was diese Technik      zum Kernel einschränkt. (0,5 P) (Alternativ: Wenn wir den Benutzerraum erlauben würden, Interrupts zu deaktivieren, kann das Betriebssystem Prozesse nicht mehr verhindern.)• Während die CPU einen kritischen Abschnitt mit behinderten Interrupts deaktiviert, könnten I / O-Geräte und andere CPUs versuchen, dies über Interrupts dem Betriebssystem zu signalisieren. Diese Unterbrechungen werden verzögert sein und möglicherweise verloren gehen. (0,5 P)• Alternativ akzeptieren wir auch: Das Deaktivieren von Interrupts bietet keinen gegenseitigen   Ausschluss auf Multiprozessorsystemen. (0,5 P)On a single-processor system, disabling interrupts is sufficient to achieve mutualexclusion. (1 P)That approach has several downsides:• We cannot allow user-space to disable interrupts, which restricts this techniqueto the kernel. (0.5 P) (Alternative: If we would allow user-space to disable interrupts,the OS cannot prevent processes anymore.)• While the CPU is executing a critical section with interrupts disabled, I/O devicesand other CPUs might try to signal the OS via interrupts. These interrupts willbe delayed and can potentially be lost. (0.5 P)• Alternatively, we also accept: Disabling interrupts does not provide mutual exclusionon multiprocessor systems. (0.5 P)
• Was ist Verklemmungsverhinderung? (1 pt) What is deadlock prevention? Negieren Sie mindestens einen der erforderlichen Deadlock-Bedingungen: Entwerfen Sie Ihr System in einer Weise so dass eine (oder mehrere) der Bedingungen nicht auftreten können. (1 P)Negate at least one of the required deadlock conditions: Design your system in a waythat one (or multiple) of the conditions cannot occur. (1 P)
• Gegeben ist ein System, das nicht-blockierende (d.h. asynchrone) Interprozesskommunikation (IPC) unterstützt. Warum muss eine korrekte Implementierung dieses Systems das Erzeuger-Verbraucher-Problem (producer-consumer-problem) lösen? Welche Designentscheidung für IPC würde die der Konstruktion des Systems zugrundeliegende Synchronisationsaufgabe vereinfachen? (3 pt) Assume a system that supports non-blocking (i.e., asynchronous) inter-process communication (IPC). Explain why a correct implementation of this system must solve the producer-consumer problem. Which design choice for IPC would simplify the synchronization task involved in building this IPC system? Nachrichten müssen in einem buffer gespeichert werden, weil eine willkürliche Anzahl bestehen kann die zwischen dem nicht blockenden gesendeten und der dazugehörigen receive Operation vorhanden ist. Wir können nicht annhemen das die Initiale kopie der Nachricht ( im der Sender AS) zu der zeit vorhanden ist, weil der Sender die nicht blockierende Nachricht sendet wenn die Operation gelingt. Operationen auf diesem Buffer müssen Synchronisiert sein.(1P) Wenn wir aussuchen eine bestimmte Anzahl an Speicher auf dem Message buffer zu reservieren, muss der Sender warten bis alle buffer besetzt sind, damit die nicht blockierte Sendung erniedrigt wird um eine blockierte Sendungsoperation auszuführen. Folglich werden die Empfangsgeräte die die Nachricht einer voll besetzten Buffer konsumiert haben die Aufgabe haben die pontentiel wartenden Sender aufzuwecken. Dieses Szenario ist das producer - Consumer Problem.(1P) Wenn wir es aussuchen die Buffer unendlich wachsen zu lassen, könne es darin resultieren das der ganze Speicher vom Nachrichten Buffer konsumiert wird (schlechte idee), deswegen müssen die Sender niemals darauf warten das die Nachricht gepostet wird. Deswegen muss das Kommunikationssystem das komplette producer-consumer Problem nicht lösen. (1P) ( Du kannst das Problem der unlimiterten nutzung des Speichers lindern, indem du den Sender oder dem Empfangsgerät mehr Buffer Platz haben lässt)Messages have to be stored in a buffer because an arbitrary amount of time couldpass between the non-blocking send and the corresponding receive operation. Wecannot assume the initial copy of the message (in the sender’s AS) to be available atreceive time because the sender may destroy it once the non-blocking send operationsucceeds. Operations on these buffers have to be synchronized. (1 P)If we choose to reserve a limited amount of memory for message buffers (boundedbuffers), a sender has to wait once all buffers are occupied, thereby degrading thenon-blocking send to a blocking send operation. Consequently, receivers that consumea message from a fully occupied buffer have to wakeup potential waitingsenders. This scenario is the producer-consumer problem. (1 P)6If we choose to let buffers grow indefinitely, which may result in all memory beingconsumed by message buffers (i.e., a bad idea), senders will never have to wait whenposting a message. Thus, the communication system would not need to solve thecomplete producer-consumer problem. (1 P) (You may alleviate the issue of unlimitedmemory use by having the sender or the receiver provide buffer space).
• Anzeige
• Was müssen Sie bei der Verklemmungsverhinderung beim Entwurf eines Systems beachten? Welche Vorkehrungen müssen Sie zur Laufzeit treffen? Erläutern Sie Ihre Antwort anhand einer konkreten Technik. (2 pt) What is required when designing a system if you use deadlock prevention? What provisions are necessary at runtime? Give your answer using an actual technique as example. Deadlock-Prävention muss in ein System oder eine Anwendung von ihr integriert werden,durch seinen Entwickler zur Entwurfszeit. Es bestimmt, wie Ressourcen zugewiesen werden können und hat somit Einfluss auf die Programmstruktur. (0,5 P)Zum Beispiel muss bei der Ressourcenbestellung ein Entwickler sicherstellen, dass der Kontrollfluss immer die Ressourcenhierarchie würdigt und nie eine Ressource mit einer niedrigerenPriorität als die, die bereits gehaltenen wird, fordert.(1 P)Allerdings verlangt die Deadlock-Prävention keine Rückmeldung zur Laufzeit. (0,5 P)Deadlock prevention needs to be incorporated into a system or application by itsdeveloper at design time. It determines how resources can be allocated and thus hasan influence on program structure. (0.5 P)For example, with resource ordering a developer has to ensure that control flow alwayshonors the resource hierarchy and never requests a resource with a lowerpriority than those already held. (1 P)However, deadlock prevention does not demand for any provisions at run time. (0.5 P)
• Was ist Verklemmungsvermeidung? (1 pt) What is deadlock avoidance? Entscheide, ob das System bei jeder Ressourcenanforderung im sicheren Zustand bleibt und den angeforderten Thread blockiert , wenn nicht. (1 P)Decide if system stays in safe state on every resource request and block the requestingthread if not. (1 P)
• Was müssen Sie bei Verklemmungsvermeidung beim Entwurf eines Systems beachten? Welche Vorkehrungen müssen Sie zur Laufzeit treffen? Erläutern Sie Ihre Antwort anhand einer konkreten Technik. (2 pt) What is required when designing a system if you use deadlock avoidance? What provisions are necessary at runtime? Give your answer using an actual technique as example. Deadlock-Vermeidung dagegen erfordert keine Änderungen an der Programmstrukturneben einem Upfront Anspruch der Ressourcen, die es verwendet. (0,5 P)Aber ein Deadlock-Vermeidungs-Algorithmus zur Laufzeit führt umfangreiche Buchhaltungvon aktiven Ressourcenansprüchen. (0,5 P)Bei Ressourcenzuweisungsgraphen fügt das System beispielsweise bei Beginn eines Prozesses Schadenkanten hinzu; Es macht Kanten in Anforderungskanten und dann in Zuordnungskanten, wenn eine Ressource angefordert und schließlich gewährt wird. (1 P)Deadlock avoidance, in contrast, does not require changes to program structure besidesan upfront claim of the resources it is going to use. (0.5 P)At runtime, though, a deadlock avoidance algorithm performs extensive bookkeepingof active resource claims. (0.5 P)With resource-allocation graphs, for example, the system adds claim edges whenstarting a process; it turns claim edges into request edges and then into assignmentedges, when a resource is requested and granted eventually. (1 P)
• Welche der notwendigen Bedingungen für eine gültige Lösung des Problems kritischer Abschnitte werden von einfachen Spinlocks erfüllt, welche nicht? Erläutern Sie jeweils warum. Welcher andere Synchronisationsmechanismus erfüllt alle diese Bedingungen? (5 pt) Which of the requirements for a valid solution of the critical section problem do simple spinlocks fulfill, which not? For each requirement explain why / why not. State another synchronization mechanism that does fulfill all of these requirements. Einfache Spinlocks stellen gegenseitigen Ausschluss zur verfügung. (0.5P) Sie sind darin Implementiert, das sie atomische Anweisungen befolgen die sicher stellen das nur ein Kandidaten prozess den spinlock abrufen kann um den state as free anschließend zu besetzt zu wechseln. (1P) Einfache Spinlocks erfüllen die Fortschritt Kriterie. (0,5P) Ein Prozess kann den Spinlock ganz alleine erwerben. Prozesse der restlichen Sektion greifen niemals auf die Spinlock variable zu und damit kann sie andere Prozesse die versuchen die kritische Sektion zu betreten nicht dabei stören. (1P) Einfache Spinlocks erfüllen nicht das boundete warten (0.5P), weil die atomische Operation die dafür benutzt werden für das beschäftigte warten, garantieren nicht eine Reihenfolge in welche die Gefahren den lock bekommen. (1P) Starke Semaphores ( ticket locks) erfüllen alle Anforderungen für eine gültige Lösung des kritischen Sektions Probelms.(0.5P)Simple spinlocks provide mutual exclusion (0.5 P). They are implemented usingatomic instructions that ensure that only one candidate process will retrieve the spinlock’sstate as free and subsequently change it to occupied. (1 P)Simple spinlocks do fulfill the progress criteria (0.5 P). A process can acquire thespinlock all by itself. Processes in their remainder section never access the spinlockvariable and thus cannot interfere with another process trying to enter the criticalsection. (1 P)Simple spinlocks do not fulfill bounded waiting (0.5 P) because the atomic operationsused for busy waiting do not guarantee an order in which threads acquire thelock. (1 P)Strong semaphores (and e.g., ticket locks) do fulfill all requirements for a valid solutionof the critical section problem. (0.5 P)
• Erklären Sie Direct Communication und Indirect Communication im Kontext von Prozesskommunikation. (2 pt) Explain direct and indirect communication in the context of Process Communication. Direkte Kommunikation:• Prozesse müssen sich explizit benennen: Senden (P, Nachricht), Empfangen (P) (+ 0.5P)• Links werden automatisch aufgebaut, genau ein Link ist genau zugeordnet mit genaueinem Paar kommunizierender Prozesse. (+ 0,5P)Indirekte Kommunikation:• Nachrichten werden an Postfächer gerichtet und empfangen. (+ 0,5P)• Link nur hergestellt, wenn Prozesse eine gemeinsame Mailbox teilen. Ein Link kann Mit vielen Prozessen verknüpft sein. (+ 0,5P)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)
• Exklären Sie knapp was Critical Sections sind. (0.5 pt) Explain briefly what critical sections are. Abschnitte von Programmen, in denen gleichzeitige Aktivitäten oder Threads auf freigegebene Daten zugreifen. (0,5P) Sections of programs where concurrent activities or threads access shared data.(0.5P)
• Betrachten Sie das folgende Code-Beispiel. Nehmen Sie an, dass zwei Producer und ein Consumer in einem System existieren. Sonst gibt es keine weitere Aktivität in diesem System. Das System hat einen präemptiven Scheduler. a) Liegt in dem Code eine Race-Condition vor? Wenn ja, nennen Sie die fehlerhaften Zeilen im Code. b) Beschreiben Sie einen Ablauf, der dazu führt, dass der Consumer ein ungültiges Item aus dem Puffer nimmt. Have a look at the following code sample. Assume that two producers and one consumer exist in a system. There is no other activity in this system. The system schedules pre-emptively. a) Does a race condition exist in this code? If yes, refer to the incorrect lines in the code. b) Describe a flow of execution that leads to the consumer remove an invalid item from the buffer. a) Ja. Die beiden Produzenten können in den Zeilen 8 und 9 auf die Variable zugreifen (+ 1P)b)• Produzent 1 (P1) und Produzent 2 (P2) führen Zeile 8 in beliebiger Reihenfolge durch. (Die zweite gültige Element überschreibt das erste gültige Element im ersten Element des Puffers.) (+ 0.5P)• P1 führt zuerst die Zeile 9 aus. (Eine Pufferfüllung von 1 wird signalisiert.) (+ 0,5P)• P2 führt Zeile 9 als zweites aus. (Eine falsche Füllgröße von 2 wird signalisiert.) (+ 0,5P)• Der Konsument (C) nimmt beim zweiten Mal einen ungültigen Eintrag aus dem Puffer 16 ein. (+ 0,5P) a) Yes. The two producers may race in accessing the variable in in lines 8 and 9. (+1P)b)• Producer 1 (P1) and Producer 2 (P2) execute line 8 in any order. (the second validitem overwrites the first valid item in the first element of the buffer.) (+0.5P)• P1 executes line 9 first. (a buffer fill size of 1 is signaled.) (+0.5P)• P2 executes line 9 second. (an incorrect fill size of 2 is signaled.) (+0.5P)• Consumer (C) takes an invalid item from the buffer the second time it hits line16. (+0.5P)
• Beschreiben Sie das Producer-Consumer-Problem. (2 pt) Describe the producer-consumer problem. - Mindestens ein Herrsteller stellt Daten her das mindestens von einem Konsumierer konsumiert wird. Gleichzeitiger Zugang zu geteilten Daten kann zu Daten inkonsistenz führen. (+1P) - Um Daten konsistenz zu behalten braucht es einen mechanismus um die ordentliche Ausführung der kooperativen Prozesse sicherzustellen. (+1P) - Es muss kein rennen stattfinden im Datenzugriff. (0.5P) - Wenn ein Bounded Buffer benutzt wird, überfüllt der Hersteller den Buffer nicht und der konsumierer unterfüllt ihn nicht. (+0.5P)• 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)
• Wie können Sie das Problem aus der vorherigen Teilaufgabe mit genau einem weiteren Semaphore lösen? (1.5 pt) How can you solve the problem in the previous task by adding exactly one semaphore? • Neues Semaphor Semaphore sem3 = sem_init (1); (+ 0,5P)• wait (sem3); Zwischen den Zeilen 7 und 8 (oder zwischen den Zeilen 6 und 7) und dem signal(sem3);Zwischen den Zeilen 9 und 10 (oder zwischen den Zeilen 10 und 11). (1P)• New semaphore Semaphore sem3 = sem_init(1); (+0.5P)• wait(sem3); between lines 7 and 8 (or between lines 6 and 7) and signal(sem3);between lines 9 and 10 (or between lines 10 and 11). (1P)
• Erklären Sie knapp, wann sich ein System im Kontext von Ressourcenzuteilung in einem unsicheren Zustand befindet? (1 pt) Explain briefly: when is a system considered in an unsafe state in the context of ressource allocation? Ein System befindet sich in einem unsicheren Zustand, wenn es keinen Schedule gibt, so dass das Maximum an Ressourcenanforderungen aller Prozesse erfüllt werden kann. (+ 1P)A system is in an unsafe state, if there exists no schedule such that the maximalresource requests of all processes can be satisfied. (+1P)
• Erklären sie jeweils knapp Deadlock Prevention und Deadlock Avoidance. (2 pt) Briefly explain deadlock prevention and deadlock avoidance. • Deadlock-Prävention: Negieren Sie mindestens einen der erforderlichen Deadlock-Bedingungen (+ 1P)• Deadlock Vermeidung: Entscheiden Sie, ob das System in sicherem Zustand bei jeder Ressourcenanfrage bleibt (+ 1P)• Deadlock Prevention: Negate at least one of the required deadlock conditions(+1P)• Deadlock Avoidance: Decide if system stays in safe state on every resourcerequest (+1P)
• Tragen Sie in der folgenden Tabelle jeweils die Oktalzahl ein, die das jeweilige Zugriffsrecht/Spezielle Flag repräsentiert. (3 pt) In the following table, enter the octal representation of the respective access right/special flag. SGID       2Write       2Execute  1Sticky     1Read      4SUID      4
• Sie sollen die Zugriffsrechte für ein geteiltes Verzeichnis work einer Arbeitsgruppe project festlegen. Alle Gruppenmitglieder sollen in work Dateien auflisten, lesen, schreiben und anlegen können, ansonsten soll aber niemand Zugriff auf das Verzeichnis haben. Die korrekten Rechte sollen auch automatisch für neu angelegte Dateien gesetzt werden. Geben Sie in Oktalnotation die Werte für die Zugriffsrechte und Benutzermaske sowie je eine kurze Erklärung an! (2 pt) You need to set access rights for a shared directory work for your work group project. Allow all group members to list, read, write and create files, while disallowing access from everyone else. Access rights to newly created files should be set correctly automatically. In octal notation, provide the values for the access rights and user mask as well as a short explanation. chmod 2070 arbeitenUmask 007Setze rwx für die Gruppe und die SGID, um Gruppeneigentum auf neu erstellte Dateien und Verzeichnisse zu erben.  Besitzer können optional auch rwx haben. User mask 007 gibt rwx für neue Dateien an Besitzer und Gruppe, 707 gibt rwx nur zur Gruppe.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.
• Unter welchen Umstanden ist eine Free-List eine bessere Datenstruktur als eine Bitmap, um freie Blocke eines Dateisystems zu verwalten? (1 pt) Under what circumstances is a free list a better choice than a bitmap for tracking free blocks in a file system? • Freien Platz zu finden ist in der Regel schneller.- Wenn Sie große freie Chunks schnell finden müssen, können Sie die freie Liste nach Größe sortieren.• Wenn Sie nur wenige große Zuweisungen haben, benötigen Sie weniger Platz.• 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.
• In C/Unix kann man Datahandle offener Dateien an Funktionen übergeben. Nehmen Sie an, Sie schreiben eine Funktion, die ein offenes Datahandle als Argument übergeben bekommt. Ist es einfach möglich, den Dateinamen der zu öffenenden Datei zu bestimmen? Wie bzw. Warum? (2 pt) In C/Unix you can pass file handles of open files to functions. Assume you are writing a function that receives an open file handle as an argument. Is it easily possible to find out the file name of the open file? How or Why? Ein Dateizugriff stellt eine offene Datei im Betriebssystem dar. Es assoziiert eine Nummer mit einem Datei Descritor, der ein Inode-, Offset-Paar enthält. Der Pfad und Dateiname der geöffneten Datei kann nicht direkt abgeleitet werden. Das Wissen über die Inode hilft auch nicht, es kann verschiedene Dateien geben, die durch die selbe Inode (harte Verbindungen) dargestellt werden.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).
• Erklaren Sie für die folgenden Daten, wo/wie diese in einem Unix Dateisystem gespeichert werden! (4 pt) Explain where/how the following data is stored in a Unix file system! Der Dateiname wird als Verzeichniseintrag dargestelltDer Name des enthaltenden Verzeichnisses kann zweideutig sein und wird nur implizitdurch die Verzeichnisstruktur gespeichert. Dateien können in mehreren Verzeichnissen gespeichert werden (Harte Verbindungen).Die Dateigröße wird im Inode gespeichert.Die Anzahl der symbolischen Links wird überhaupt nicht gespeichert und kann nur durch Suche im gesamten Verzeichnisbaum erhalten werden.The file name is represented as directory entryThe 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.

zurück  |  weiter 1 / 1