Aufgabe 2: Prozesse und Threads/Ablaufplanung

Question 1

Ist es sinnvoll, auf einem System mit nur einer CPU mehrere Threads zu verwenden? Begründen Sie Ihre Antwort. (1 pt) Does it make sense to use multiple threads on a computer with only one CPU? Explain your answer.

Accepted Answer

Ja, das macht Sinn. (0,5 P) Threads neigen dazu, von Zeit zu Zeit für I / O zu blockieren. In diesem Fall kann das Betriebssystem einfach zu einem anderen fertigen Thread wechseln, wenn mehrere Threads verwendet werden. Mehrere Threads führen zu einer höheren CPU-Nutzung. (0,5 P)Yes, it makes sense. (0.5 P) Threads tend to block for I/O from time to time. In thatcase, the operating system can just switch to another ready thread if multiple threadsare used. Multiple threads thus result in a higher CPU utilization. (0.5 P)

Question 2

Gegeben seien fünf Prozesse auf einem Einprozessorsystem mit den angegebenen Ankunftszeiten (0 = Start), Burst-Zeiten und Prioritaten (hohe Werte werden bevor- zugt). Vervollstandigen Sie die untenstehenden Ablaufpläne für die Strategie ¨ Preemptive Shortest Job First (PSJF)" sowie die Strategie "Preemptive Strict Priority (PSP)". Ein Kasten im Zeitplan stellt eine Zeiteinheit dar. (4 pt) Consider five processes on a uniprocessor system, with given arrival times (0 = start), burst times, and priorities (high values are favored). Complete the scheduling plans given below for the policy Preemptive Shortest Job First (PSJF) and the policy Preemptive Strict Priority (PSP). A box in the scheduling plan represents one unit of time. Process Arrival Time Burst Time Priority 1 4 1 1 2 0 7 3 3 2 4 2 4 5 3 5 5 6 6 4

Accepted Answer

Preemptive Shortest Job First (PSJF)2 2 3 3 1 3 3 4 4 4 2 2 2 2 2 5 5 5 5 5 5Preemptive Strict Priority (PSP)2 2 2 2 2 4 4 4 5 5 5 5 5 5 2 2 3 3 3 3 1-0.5 P for each incorrect scheduling decision

Question 3

Berechnen Sie für den obigen PSJF-Ablaufplan die Turnaround-Zeit aller Prozesse. (2.5 pt) For the above PSJF scheduling plan, calculate the turnaround time of each process.

Accepted Answer

The turnaround time for each process can be calculated as ttournaround = tf inish−tarrivalProcess Finish time Arrival time Turnaround time 1 5 4 1 2 15 0 15 3 7 2 5 4 10 5 5 5 21 6 15

Question 4

Berechnen Sie für den obigen PSP-Ablaufplan die Wartezeit aller Prozesse. (2.5 pt) For the above PSP scheduling plan, calculate the waiting time of each process.

Accepted Answer

The waiting time for each process can be calculated as twait = tf inish − tarrival − tburstProcess Finish time Arrival time Burst time Waiting time 1 21 4 1 16 2 16 0 7 9 3 20 2 4 14 4 8 5 3 0 5 14 6 6 2

Question 5

Betrachten Sie einen Drucker, der ununterbrochen neue Aufträge von vielen Nutzern erhält. Immer wenn ein Auftrag fertig bearbeitet ist, verwendet der Drucker ¨ folgenden Scheduling-Algorithmus, um den nächsten Auftrag zum Drucken auszuwählen: Zunächst werden alle Aufträge aufsteigend nach Ihrer Seitenzahl sortiert. Anschließend wird der Auftrag mit der geringsten Seitenzahl ausgeführt. ¨ Ist der beschriebene Scheduling-Algorithmus in diesem Szenario eine gute Wahl? Begründen Sie Ihre Antwort. (2 pt) Consider a printer which continuously receives print jobs from many users. Whenever the printer has finished printing a job, it uses the following scheduling algorithm to select the next job for execution: First, it sorts all queued print jobs in ascending order of their page count. Then, it prints the job containing the smallest number of pages. Is the scheduling algorithm described above a good choice in the above scenario? Explain your answer.

Accepted Answer

Der Algorithmus ist eine schlechte Wahl. (1 P) Da neue Jobs kontinuierlich ankommen, gibt es eine gute Chance, dass es immer Arbeitsplätze mit einer kleinen Anzahl von Seiten in der Schlange gibt. Große Arbeitsplätze können daher aussterben. (1 P) In der Vergangenheit war dies ein großes Problem mit den zentralen SCC-Druckern. Mittlerweile hat der SCC Anpassungen in seiner Planung vorgenommen, die das Problem etwas lindern.The algorithm is a bad choice. (1 P) Since new jobs arrive continuously, there is agood chance that there will always be jobs containing a small number of pages inthe queue. Large jobs can therefore starve. (1 P) Back in the days, this used to be ahuge problem with the central SCC printers. By now, the SCC has made adjustmentsto its scheduling which alleviate the problem somewhat.

Question 6

Gegeben sind vier Prozesse auf einem Einprozessorsystem mit den angegebenen Ankunftszeiten (0 = Start), Burst-Zeiten und Prioritäten (hohe Werte werden ¨ bevorzugt). Vervollständigen Sie die untenstehenden Ablaufpläne für die Strategie Preemptive Shortest Job First (PSJF) sowie die Strategie Non-Preemptive Static Priority (NPSP). Ein Kasten im Zeitplan stellt eine Zeiteinheit dar. (4 pt) Consider four processes on a uniprocessor system, with given arrival times (0 = start), burst times and priorities (high values are favored). Complete the scheduling plans given below for the policy preemptive shortest job first (PSJF) and the policy nonpreemptive static priority (NPSP). A box in the scheduling plan represents one unit of time. Process Arrival Time Burst-Time Priority 1 2.5 1 3 2 3.5 3 4 3 0 6 2 4 1.5 3 1 5 8 5 5

Accepted Answer

Preemptive Shortest Job First (PSJF)3 3 4 1 4 4 2 2 2 3 3 3 3 5 5 5 5 5Non-Preemptive Static Priority (NPSP)3 3 3 3 3 3 2 2 2 5 5 5 5 5 1 4 4 4-0.5 P for each incorrect scheduling decision

Question 7

Berechnen Sie für den obigen PSJF-Ablaufplan die Antwortzeit aller Prozesse. (2 pt) For the above PSJF scheduling plan, calculate the response time of each process.

Accepted Answer

Die Wartezeit für jeden Prozess kann als twait = tarrival - tstart berechnet werden.The waiting time for each process can be calculated as twait = tarrival − tstart Process Arrival time Start time Response time 1 2.5 3 0.5 2 3.5 6 2.5 3 0 0 0 4 1.5 2 0.5 5 8 13 5

Question 8

Welches Problem tritt im Zusammenhang mit Static Priority Scheduling häufig auf? Welcher Mechanismus wird üblicherweise eingesetzt, um dieses Problem zu lösen? Beschreiben Sie das Problem und die Lösung jeweils kurz. (2 pt) Which problem frequently occurs in conjunction with static priority scheduling? What mechanism can be used to solve that problem? Briefly describe both the problem and the solution.

Accepted Answer

Verhungern(0,5 P) ist ein häufiges Problem bei der statischen Prioritätsplanung: Prozesse mit niedriger Priorität können niemals ausgeführt werden, wenn es eine Reihe von Prozessen mit hoher Priorität im System gibt. (0,5 P) Eine Lösung für dieses Problem ist das heranreifen, (0,5 P), d.h. die Priorität der wartenden Prozesse im Laufe der Zeit zu erhöhen. (0,5 P)Alternative Lösung: Prioritätsinversion (0,5 P) ist, wenn ein Prozess mit hoher Priorität auf einen anderen Prozess mit einer niedrigeren Priorität wartet. Das Verfahren mit hoher Priorität hat effektiv den Standpunkt der niedrigen Priorität während der Wartezeit. (0,5 P) Eine Lösung ist die Prioritätsspende oder Prioritätsvererbung: (0,5 P) Der Prozess, auf den gewartet wird, gibt die "wartender Prozess"- Priorität während der Wartezeit ab. (0,5 P)Starvation (0.5 P) is a frequent problem with static priority scheduling: Low priorityprocesses may never execute if there is a number of high-priority processes in thesystem. (0.5 P) A solution to this problem is aging, (0.5 P) i.e. increasing the priorityof waiting processes as time progresses. (0.5 P)Alternative solution: Priority inversion (0.5 P) is when a high-priority process waitsfor another process with a lower priority. The high-priority process effectively has thelower-priority process’ priority during the wait time. (0.5 P) A solution is Prioritydonation or Priority inheritance: (0.5 P) The process being waited for is given thewaiting process’ priority during the wait time. (0.5 P)

Question 9

Beschreiben Sie kurz den Unterschied zwischen einem Prozess und einem Thread im Kontext der Vorlesung. (1 pt) Briefly describe the difference between a process and a thread in the context of the lecture.

Accepted Answer

Ein Prozess besteht aus einem Adressraum (0,5 P) und allen Threads, die darin ausgeführtwerden. (0,5 P) Ein Thread ist somit Bestandteil eines Prozesses.(Eine andere potenzielle Antwort: Ein Prozess ist immer eine Scheduling Entity des Betriebssystems (0,5 P)Das Thread-Modell bestimmt, ob Threads OS-Entitäten sind. (0,5 P))A process consists of an address space (0.5 P) and all threads executing inside thataddress space. (0.5 P) A thread is thus a component of a process.(Another potential answer: A process is always a scheduling entity of the OS. (0.5 P)The thread model determines whether threads are OS entities. (0.5 P) )

Question 10

Gegeben sind fünf Prozesse auf einem Einprozessorsystem mit den angegebenen Ankunftszeiten (0 = Start) und Burst-Zeiten. Vervollständigen Sie die untenstehenden Scheduling-Plane für die Strategie PSJF sowie die Strategie RR für die Zeitscheibenlänge 3 Zeiteinheiten. Ein Kasten im Zeitplan stellt eine Zeiteinheit dar. (4 pt) Consider five processes on a uniprocessor system, with given arrival times (0 = start) and burst times. Complete the scheduling plans given below, for the policy PSJF and the policy RR for a timeslice length of 3 units of time. A box in the scheduling plan represents one unit of time. Process Arrival Time Burst-Time 1 1.5 3 2 0 4 3 3 5 4 2.5 2 5 5 7

Accepted Answer

PSJF2 2 2 2 4 4 1 1 1 3 3 3 3 3 5 5 5 5 5 5 5RR (timeslice length 3) – if you first requeue the running process at the end of the timeslice2 2 2 1 1 1 4 4 2 3 3 3 5 5 5 3 3 5 5 5 5RR (timeslice length 3) – if you first enqueue newly arrived processes at the end ofthe time slice2 2 2 1 1 1 4 4 3 3 3 2 5 5 5 3 3 5 5 5 5We accept both versions.-0.5 P for each incorrect scheduling decision-1 P for idle time after finished processes

Question 11

Berechnen Sie für den obigen PSJF-Scheduling-Plan die Wartezeit aller Prozesse. (2.5 pt) For the above PSJF scheduling plan, calculate the waiting time of each process.

Accepted Answer

The waiting time for each process can be calculated as twait = tfinish − tarrival − tburstProcess Finish time Arrival time Burst time Waiting time 1 9 1.5 3 4.5 2 4 0 4 0 3 14 3 5 6 4 6 2.5 2 1.5 5 21 5 7 9

Question 12

Berechnen Sie für den obigen RR-Scheduling-Plan die Tournaround-Zeit aller Prozesse. (2.5 pt) For the above RR scheduling plan, calculate the tournaround time of each process.

Accepted Answer

The turnaround time for each process can be calculated as ttournaround = tfinish−tarrival Process Finish time Arrival time Turnaround time 1 6 1.5 4.5 2 9 / 12 0 9 / 12 3 17 3 14 4 8 2.5 5.5 5 21 5 16(Zum ersten Anfordern des laufenden Prozesses / erstmalig neu eingegangene Prozesseam Ende der Zeitscheibe. Wir akzeptieren beide Versionen, wenn die Lösung im Einklang steht mit der Frage 2b.)(for first requeueing the running process / first enqueueing newly arrived processesat the end of the time slice. We accept both versions if the solution is consistent withquestion 2b.)

Question 13

Wie verhält sich ein RR-Scheduler im Fall einer unendlich langen Zeitscheibe? (1 pt) How does a RR-Scheduler behave in case of an infinite timeslice length?

Accepted Answer

Round-Robin wählt Prozesse in der Reihenfolge, in der sie ankommen, und für eine unendliche Zeitlückenlänge, beendet er keine Prozesse, bis sie fertig sind. Also verhält ein Round-Robin-Scheduler mit einer unendlichen Zeitscheiben-Länge sich genau wie ein First-come-first-served (FCFS) Scheduler.(Entweder benennen oder beschreiben FCFS ist ausreichend)Round-Robin selects processes in the order they arrive, and, for an infinite timeslicelength, does not preempt processes until they finish. Hence, a Round-Robin-schedulerwith an infinite timeslice length behaves exactly like a first-come-first-served (FCFS)scheduler.(either naming or describing FCFS is sufficient)

Question 14

Erklären Sie, warum ein RR-Scheduler keine gute Wahl für ein Batch-System ist, auf dem ausschließlich langlebige Prozesse laufen. (2 pt) Explain why a RR-scheduler is not a good choice for a batch-system executing only long-running processes.

Accepted Answer

Round-Robin-Scheduler betonen Interaktivität durch ständiges Umschalten zwischenLauffähigen Prozessen. In einem Batch-System ist jedoch keine Interaktivität erforderlich. (1 P)Darüber hinaus wird ein Round-Robin-Scheduler überall viele Kontext-wechsel verursachenwährend der Lebensdauer jedes Prozesses, wobei andere Scheduler wie FCFS oder SFJ Prozesse nur nach Fertigstellung wechseln. Da Kontextwechsel in einem realistischen System nicht kostenfrei sind, wird ein Round-Robin-Scheduler wahrscheinlich viel mehr Overhead als FCFS / SJF verursachen. (1 P)Round-robin schedulers emphasize interactivity by constantly switching betweenrunnable processes. In a batch system, however, interactivity is not required. (1 P)In addition, a round-robin scheduler will cause many context switches throughoutthe lifetime of each process, while other schedulers like FCFS or SFJ switch processesonly on completion. Since context switches are not free in a realistic system,a round-robin scheduler will likely cause much more overhead than FCFS/SJF. (1 P)

Question 15

Berechnen Sie für den obigen RR-Scheduling-Plan die Tournaround-Zeit aller Prozesse. (2.5 pt) For the above RR scheduling plan, calculate the tournaround time of each process

Accepted Answer

The turnaround time for each process can be calculated as ttournaround = tfinish−tarrival Process Finish time Arrival time Turnaround time 1 6 1.5 4.5 2 9 / 12 0 9 / 12 3 17 3 14 4 8 2.5 5.5 5 21 5 16(Zum ersten Anfordern des laufenden Prozesses / erstmalig neu eingegangene Prozesseam Ende der Zeitspanne. Wir akzeptieren beide Versionen, wenn die Lösung im Einklang steht mit Frage 2b.)(for first requeueing the running process / first enqueueing newly arrived processesat the end of the time slice. We accept both versions if the solution is consistent withquestion 2b.)

Question 16

Berechnen Sie für den obigen NPSP-Ablaufplan die Tournaround-Zeit aller Prozesse. (2 pt) For the above NPSP scheduling plan, calculate the tournaround time of each process.

Accepted Answer

The turnaround time for each process can be calculated as ttournaround = tfinish−tarrivalProcess Finish time Arrival time Turnaround time 1 15 2.5 12.5 2 9 3.5 5.5 3 6 0 6 4 18 1.5 16.5 5 14 8 6

Question 17

Nennen Sie vier in der Vorlesung besprochene Bestandteile eines Prozesskontrollblocks. (1 pt) Name four elements of a Process Control Block discussed in the lecture

Accepted Answer

• Prozesszustand• Prozesskennung• Programm zähler• CPU-Register• CPU-Scheduling-Informationen• Speicherverwaltungsinformationen• Liste der geöffneten Dateien• ...-0.5P für jeden falschen, fehlenden Eintrag• Process state• Process identifier• Program counter• CPU registers• CPU scheduling information• Memory-management information• List of open files• ...-0.5P fur jeden falschen, fehlenden Eintrag

Question 18

Erklären Sie kurz, wann der Kontrollblock eines Prozesses ausschließlich gültige Informationen enthält und wann nicht. (1 pt) Explain briefly when the control block of a process contains entirely valid information and when it does not.

Accepted Answer

• Wenn ein Prozess nicht ausgeführt wird, enthält seine Platine nur gültige Informationen.(0,5P)• Wenn ein Prozess ausgeführt wird, kann seine PCB ungültige Informationen enthalten, z.B.CPU-Register (0,5P)• 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)

Question 19

Nennen Sie die drei Prozesstypen, beschreiben Sie deren typische Reaktionsfreudigkeit und Gebundenheit (E/A, CPU). (3 pt) Name the three process types and describe their typical responsiveness and boundness (I/O, CPU).

Accepted Answer

Typ Gebundenheit ReaktionsfreudigkeitType Boundness ResponsivenessInteractive IO-bound Highly responsive to com - Sehr angenehm für Komfort Process fort users (low variance) Benutzer (geringe Varianz)Batch processes CPU-bound No need to be responsive -Keine Notwendigkeit zu reagieren (no user interaction) (Keine Benutzerinteraktion) Real-time IO-bound or Requirements/contraints -Anforderungen /Kontraktionen processes CPU-bound on responsiveness (bound auf Reaktionsfähigkeit(gebundene variance) to achive QoS Varianz), um QoS zu erreichen • -0.5P fur jeden falschen, fehlenden Eintrag

Question 20

Gegeben sind die 5 untenstehenden Prozesse auf einem Uniprozessorsystem mit den angegebenen Ankunftszeiten (Start-Zeit = 1.0) und Burst-Zeiten. Vervollständigen Sie den untenstehenden Ablaufplan für die Strategie ¨ Virtual Round Robin (VRR). Ein Kasten im Zeitplan entspricht einer Zeitscheibe. Beachten Sie: Der Prozess P5 blockiert nach der Halfte des Bursts (nach einer ¨ halben Zeitscheibe) und ist nach einer Dauer von 2.0 Zeitscheiben wieder bereit. 3 pt Consider the 5 processes given below on a uniprocessor system, with the given arrival times (start time = 1.0) and burst times. Complete the schedule given below according to the policy Virtual Round Robin (VRR). A box in the schedule represents one time slice/quantum. Attention: the process P5 blocks after half its burst (after half a time slice) and is ready again after a duration of 2.0 time slices. Prozess Ankunft-Zeit Burst-Zeit Process Arrival time Burst time P1 1.9 7.0 P2 1.0 4.0 P3 5.9 1.0 P4 5.8 6.0 P5 6.1 1.0

Accepted Answer

• Die erste Spalte nennt die Zeitspanne.• Die zweite Spalte enthält den Zeitplan. Jede Zelle zeigt den laufenden Prozess dieser Zeitspanne an. Die verbleibende Zeit des Prozesses platzt in Parenthese, nach nach dem die aktuelle Zeitspanne gegeben ist.• Die dritte Spalte enthält den Status der fertigen Warteschlange, wenn die Terminierungsentscheidung für diese Zeitspanne gewählt wurde.• Die vierte Spalte ist analog für die Zusatzwarteschlange.• The first column numbers the time slices.• The second column holds the schedule. Each cell indicates the process runningin that time slice. In parentheses the remaining time of the process’ burst afterthe current time slice is given.• The third column holds the state of the ready queue when the scheduling decisionis taken for that time slice.• The fourth column is analogous for the auxiliary queue. Zeit Ablaufplan Ready Queue Auxiliary QueueTime Schedule Ready queue Auxiliary queue 1 2 2 2 1 1 2 3 2 2 1 4 1 1 2 5 2 2 1 6 1 1 4 3 2 7 4 4 3 2 5 1 8 3 3 2 5 1 4 9 2 2 5 1 4 10 5 5 1 4 11 1 1 4 12 4 4 1 13 5 1 4 5 14 1 1 4 15 4 4 1• -0.5P fur jeden falschen, fehlenden Eintrag ¨• Wenn der komplette Schedule teilweise korrekt ist, ein Fehler erfolgte und erdavon ausgehend plausibel ausgefullt wurde, gibt es Folgefehler.Den 2ten Teil der Aufgabe bitte nachschauen, 18.3.2013 Aufgabe 2 d)!!!!!!!!!!!!!!!!!!!!!

Question 21

Beschreiben Sie knapp die Fairness-Strategie nach welcher der Linux Completely Fair Scheduler versucht, immer wenn er aufgerufen wird, die Interaktivitat von Prozessen zu gewährleisten? (2 pt) Explain briefly according to which fairness strategy the Linux Completely Fair Scheduler tries to provide interactivity of processes each time it is invoked?

Accepted Answer

• Auf Aufruf, wie viel Zeit auch immer vergangen ist, um eine faire Terminierung zu etablieren, muss der Prozess einen proportionalen Anteil der CPU über seine gesamte Lebensdauer gehabt haben. Wenn ein Prozess nicht seinen Anteil während dieser Zeit bekommt, hat es ungerechter Weise gewartet, und wird als nächstes ausgeführt werden. (1P)• Dieses Verhalten fördert die Interaktivität von I / O-gebundenen Prozessen, als CPU- gebunden Prozesse haben eine generell niedrigere Priorität. (1P)• 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)

Question 22

Nennen Sie vier verschiedene Metriken/Kriterien, welche zur Beurteilung eines Scheduling-Verfahrens herangezogen werden können. (2 pt) Name four different metrics/criteria that can be used to estimate the quality of a scheduling policy.

Accepted Answer

• Prozessorauslastung• Anwendungsdurchsatz• Seitenwechsel • Wartezeit• Reaktionszeit• ... Processor utilization• Application Throughput• Turnaround time• Waiting time• Response time• ...

Question 23

Diskutieren Sie Vor- und Nachteile einer langen gegenüber einer kurzen Zeit Spannenlänge. (2 pt) Discuss pros and cons of long versus short time slice lengths.

Accepted Answer

Je länger ein Zeitlimit ist, desto weniger Kontextwechsel pro Zeiteinheit sind erforderlich. So wie Kontext-Switches einen bestimmten Overhead erfordern (Eingabe des Kernels, Auswahl eines neuen Prozesses, wechseln der Adressäume, wenn nötig, etc.), kann die Verringerung der Anzahl der Kontext-Schalter helfen, den Durchsatz zu verbessern. Allerdings wirken sich auch zu lange Zeitspannen negativ auf die Reaktionsfähigkeit des Systems aus: Jeder Prozess wird eine relativ lange Zeit lang ausgeführt, bis es beendet wird, und folglich bereite Prozesse müssen länger warten, bis sie wieder laufen dürfen.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.

Question 24

Gegeben seien ein Lottery-Scheduler auf einem Uniprozessorsystem mit der Prozessliste {P1, P2, P3}. P1 habe 2 Tickets, P2 habe 5 Tickets, P3 habe 1 Ticket. Alle Prozesse sind permanent lauffähig. Vervollständigen Sie den untenstehenden Plan (10 Kreuze). Die erste Zeile (TIME) ¨ gibt die Zeit an. Eingeplant wird jeweils beim Wechsel der Zeiteinheit. Um die Lotterie deterministisch zu gestalten, enthält die zweite Zeile (LOTTERY) das vorgegebene Lotterie-Ergebnis zum jeweiligen Anfang der Zeiteinheit. (3 pt) Consider a lottery scheduler on a uniprocessor system with process list {P1, P2, P3}. P1 has 2 lottery tickets, P2 has 5 lottery tickets, and P3 has 1 ticket. Complete the scheduling plan given below (10 crosses). The first row (TIME) states the time. Scheduling occurs at time unit changes. In order to ensure deterministic results, the second row (LOTTERY) contains a pre-defined lottery result for each time unit start. TIME 0 1 2 3 4 5 6 7 8 9 LOTTERY 4 5 0 0 1 3 2 4 1 6 P1 P2 P3

Accepted Answer

TIME 0 1 2 3 4 5 6 7 8 9LOTTERY 4 5 0 0 1 3 2 4 1 6P1 X XX XP2 X X X X X XP3

Question 25

Lottery-Scheduling kann insofern als fair bezeichnet werden, weil es im Durschnitt zu jedem Prozess proportional zu den Tickets Zeit zuteilt. Nehmen Sie an, Sie möchten auf einem Prozessor eine im Hintergrund ablaufende Kernel-Kompilierung (Prozess P4) gleichzeitig mit einer Videokonferenzanwendung (Prozess P5) ausführen lassen. P4 habe permanenten Rechenbedarf, während P5 nie die volle Zeitscheibenallokation ausnutzt. Bleibt Lottery-Scheduling fair, wenn Sie den beiden Prozessen dieselbe Anzahl Tickets zuteilen? Warum/Warum nicht? (2 pt) Lottery scheduling can be termed fair insofar, as it will allocate, on average, processing time to each process in proportion to its respective number of tickets. Suppose you want to execute, on a single processor, a kernel compilation job in background (process P4) together with a video conferencing application (P5). P4 requires the processor at any time, while P5 never eats up its time slice completely. Will Lottery Scheduling stay fair (according to previous definition) if you allocate the same number of tickets to both P4 and P5? Why / why not?

Accepted Answer

Nein. Während bei beiden Prozessen im Durchschnitt die gleiche Anzahl von Lotterien gewonnen werden, wird P5 nur einen Bruchteil der Bearbeitungszeit von P4 benötigen.No. While both processes will win the same number of lotteries on average, P3 willreceive only a fraction of the processing time of P4.

Question 26

Erklären Sie kurz das Scheduling-Verfahren: Multi-Level Feedback Queue (MLFB) mit variablen Zeitscheibenlängen. (3 pt) Briefly explain the scheduling policy: Multi-Level Feedback Queue (MLFB) with variable time slices. Erklären Sie kurz, ob MLFB ein geeignetes Verfahren in den folgenden Fällen ist: Briefly discuss whether MLFB is a good scheduler in the following cases: In einem System, in welchem die Kosten für Kontextwechsel hoch sind. In a system where context switching costs are high. In einem System, in welchem Aushungern (Starvation) vermieden werden sollte. In a system where starvation should be avoided.

Accepted Answer

MLFB: Mehrfache Warteschlangen mit individuellen Prioritäten und Zeitscheiben. Typischerweise je niedriger prio, desto größer die Zeitspanne. Interaktive Prozesse haben High-Prio und kleine Zeitspannen.CPU-gebundene Prozesse, die alle CPU-Zeit verbrauchen, gehen zu einer niedrigeren Prioritäts-Warteschlange mit höherer Zeitscheibe.MLFB ist eine gute Wahl, wenn die Kontextwechselkosten hoch sind, wie es nur benötigt wird bei häufigem Wechsel mit kurzen Aufträgen aber vermeidet Schaltkontexte mit langerfristigenjobs.In MLFB können viele kurzfristige Aufträge die Arbeitsplätze mit niedrigerer Priorität verhungern lassen. Das kann aber auch vermieden werden, indem man Prozesse bewegt, die zu lange in einer der höhere-Priorität-Warteschlangen gewartet haben.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.

Question 27

Gegeben sind fünf Prozesse auf einem Einprozessorsystem mit den angegebenen Ankunftszeiten (0 = Start) und Burst-Zeiten. Vervollständigen Sie die untenstehenden Ablaufpläne für die Strategie Shortest Job First (SJF) sowie die Strategie Round-Robin (RR). Ein Kasten im Zeitplan stellt eine Zeiteinheit dar. (4 pt) Consider five processes on a uniprocessor system, with given arrival times (0 = start) and burst times. Complete the scheduling plans given below for the policy Shortest Job First (SJF) and the policy Round-Robin (RR). A box in the scheduling plan represents one unit of time. Process Arrival Time Burst-Time 1 2.5 5 2 7.5 3 3 1.5 6 4 4.5 1 5 0 3

Accepted Answer

Shortest Job First (SJF)5 5 5 1 1 1 1 1 4 2 2 2 3 3 3 3 3 3Round-Robin (RR)5 5 3 5 1 3 4 1 3 2 1 3 2 1 3 2 1 3-0.5 P for each incorrect scheduling decision

Question 28

Berechnen Sie für den obigen SJF-Ablaufplan die Wartezeit aller Prozesse. (2 pt) For the above SJF scheduling plan, calculate the waiting time of each process.

Accepted Answer

The waiting time for each process can be calculated as twait = tfinish − tarrival − tburstProcess Finish time Arrival time Burst time Waiting time 1 8 2.5 5 0.5 2 12 7.5 3 1.5 3 18 1.5 6 10.5 4 9 4.5 1 3.5 5 3 0 3 0

Question 29

Berechnen Sie für den obigen RR-Ablaufplan die Tournaround-Zeit aller Prozesse. (2 pt) For the above RR scheduling plan, calculate the tournaround time of each process.

Accepted Answer

The turnaround time for each process can be calculated as ttournaround = tfinish−tarrivalProcess Finish time Arrival time Turnaround time 1 17 2.5 14.5 2 1 6 7.5 8.5 3 18 1.5 16.5 4 7 4.5 2.5 5 4 0 4

Question 30

Was versteht man unter kooperativem Scheduling? Geben Sie je einen Vor- und Nachteil von kooperativem Scheduling an. (2 pt) What is cooperative scheduling? Give an advantage and a disadvantage of cooperative scheduling.

Accepted Answer

Kooperative Terminierung bedeutet, dass das Betriebssystem nicht zwangsweise vorsätzlichThreads laufen lässt(0,5 P). Stattdessen müssen Threads die CPU freiwillig abgeben zum Beispiel durch Blockierung für I / O oder explizit durch Aufruf von yield() (0,5 P).Der Hauptnachteil der kooperativen Planung ist, das unkooperative oder fehlerhafteThreads die CPU beschlagnahmen können; Das OS hat keine Möglichkeit, solche Threads unter Kontrolle zu bringen(0,5 P).Die Vorteile der kooperativen Terminierung beinhalten einen reduzierten scheduling overhead seit Threads die CPU zu einer Zeit aufgeben können, die für sie bequem ist (z. B. wenn sie für I / O sowieso blockieren muss) und eine einfachere Scheduler-Implementierung, da eskeine Notwendigkeit gibt, preemption zu implementieren. (0,5 P)Cooperative scheduling means that the operating system does not forcibly preemptrunning threads (0.5 P). Instead, threads must relinquish the CPU voluntarily, forexample by blocking for I/O or calling yield() explicitly (0.5 P).The main disadvantage of cooperative scheduling is that uncooperative or malfunctioningthreads can hog the CPU; the OS has no way of bringing such threads undercontrol (0.5 P).Advantages of cooperative scheduling include a reduced scheduling overhead sincethreads can relinquish the CPU at a time that is convenient for them (e.g., when theymust block for I/O anyway) and a simpler scheduler implementation since there isno need to implement preemption. (0.5 P)

Question 31

Nennen Sie die drei in der Vorlesung vorgestellten Threadmodelle und geben Sie für jedes Modell an, wo (Kernel-/User space) Schedulingentscheidungen getroffen werden. (3 pt) Name the three threading models discussed in the lecture. For each model, also state where (kernel-/user space) scheduling decisions are calculated.

Accepted Answer

Threading model Scheduling decisions in...One-to-one (1x1) Kernel spaceMany-to-one (Mx1) User spaceMany-to-many (MxN) Kernel and user space0.5 P for each field in the table

Question 32

Gegeben sind vier Prozesse auf einem Einprozessorsystem mit den angegebenen Ankunftszeiten (0 = Start) und Burst-Zeiten. Vervollständigen Sie die untenstehenden Scheduling-Plane für die Strategie FCFS sowie die Strategie RR für die Zeitscheibenlänge 1 Zeiteinheit. Ein Kasten im Zeitplan stellt eine Zeiteinheit dar. ¨ 3 pt Consider four processes on a uniprocessor system, with given arrival times (0 = start) and burst times. Complete the scheduling plans given below, for the policy FCFS and the policy RR for a timeslice length of 1 units of time. A box in the scheduling plan represents one unit of time Process Arrival Time Burst-Time 1 2.5 4 2 1.5 7 3 0 4 4 6.5 5

Accepted Answer

FCFS3 3 3 3 2 2 2 2 2 2 2 1 1 1 1 4 4 4 4 4 RR3 3 2 3 1 2 3 1 2 4 1 2 4 1 2 4 2 4 2 4 -0.5 P for each incorrect scheduling decision

Question 33

Berechnen Sie für den obigen FCFS-Scheduling-Plan die Wartezeit aller Prozesse. (1.5 pt) For the above FCFS scheduling plan, calculate the waiting time of each process.

Accepted Answer

The waiting time for each process can be calculated as twait = tf inish − tarrival − tburstProcess Finish time Arrival time Burst time Waiting time 1 15 2.5 4 8.5 2 11 1.5 7 2.5 3 4 0 4 0 4 20 6.5 5 8.5

Question 34

Berechnen Sie für den obigen RR-Scheduling-Plan die Tournaround-Zeit aller Prozesse. (1.5 pt) For the above RR scheduling plan, calculate the tournaround time of each process.

Accepted Answer

The turnaround time for each process can be calculated as ttournaround = tfinish−tarrivalProcess Finish time Arrival time Turnaround time 1 14 2.5 11.5 2 19 1.5 17.5 3 7 0 7 4 20 6.5 13.5

Question 35

Erklären Sie, warum ein FCFS-Scheduler eine schlechte Wahl für Desktopsysteme ist. (1 pt) Explain why a FCFS-scheduler is a bad choice for desktop systems.

Accepted Answer

FCFS beendet nicht laufende Prozesse und bietet daher keine gute Interaktivität,was für Desktop-Systeme wichtig ist. Wenn zum Beispiel ein einzelner Prozessauf der CPU für einen längeren Zeitraum läuft, dann werden andere Prozesse, einschließlich der Desktopumgebung, nie versendet.FCFS does not preempt running processes and therefore does not provide good interactivity,which is important for desktop systems. If, for example, a single processruns on the CPU for an extended period of time, other processes, including the desktopenvironment, are never dispatched.

Question 36

Betrachten Sie einen Webserver mit einem CPU-Kern, der viele Anfragen von mehreren entfernten Clients verarbeiten muss. Ist SJF in diesem Szenario ein geeignetes Schedulingverfahren? Schlagen sie gegebenenfalls ein anderes Schedulingverfahren vor! Begründen Sie Ihre Antworten! (2 pt) Consider a web server with a single CPU core, which must process many requests from multiple remote clients. Is SJF an appropriate scheduling strategy in this scenario? If not, propose a more appropriate scheduling strategy! Justify your answers!

Accepted Answer

SJF ist nicht angemessen. (0,5 P) Im obigen Szenario entsprechen Arbeitsplätze individuell denKundenwünschen. Um den kürzesten Job zuerst einzuplanen, ist die Joblänge (d.h. die Zeit,die erforderlich ist, um jede Anfrage zu bearbeiten) muss im Voraus bekannt sein. Das ist für einen typischen Webserver nicht der Fall, wie den Inhalt jeder Anfrage und damit die Menge an Arbeit die erforderlich ist, um jede Anfrage zu verarbeiten, sind in der Regel im Vorraus unbekannt. Deswegen kannSJF im obigen Szenario nicht angewendet werden. Darüber hinaus, auch wenn die Job-Länge im Vorraus bekannt ist, wäre SJF immer noch nicht angemessen, da die Kunden in der Regel eine Mischung aus kurzen und langen Wünschen haben. Da SJF kurze Anfragen priorisiert, würden lange Anfragen wahrscheinlich verhungern. (0,5 P)FCFS ist eine angemessenere Strategie, (0,5 P), da es die geringste turnaround time besitzt, vorausgesetzt, dass Joblängen im Voraus nicht bekannt sind und garantiert ist das sie nicht Verhungern(0,5 P)(Eine Rechtfertigung pro Antwort ist ausreichend. Wir akzeptieren auch andere Terminierungsstrategien als FCFS, wenn dies angemessen gerechtfertigt ist.)SJF is not appropriate. (0.5 P) In the above scenario, jobs correspond to individualclient requests. In order to schedule the shortest job first, the job length (i.e., the timerequired to process each request) must be known in advance. This is not the casefor a typical web server, as the contents of each request, and hence the amount ofwork required to process each request, are typically unknown in advance. Therefore,SJF cannot be applied in the above scenario. In addition, even if the job lengths areknown in advance, SJF would still not be appropriate, since clients will typicallysend a mixture of short and long requests. Since SJF prioritizes short requests, longrequests would likely starve. (0.5 P)FCFS is a more appropriate strategy, (0.5 P) since it achieves the lowest possibleturnaround times given that job lengths are not known in advance and is guaranteedto be starvation-free. (0.5 P)(One justification per answer is sufficient. We accept scheduling strategies other thanFCFS if justified appropriately.)

Question 37

Erklären Sie den Begriff Zombie im Kontext von Prozessen. Geben Sie insbesondere an, wie ein Zombie entsteht und wie man ihn entfernt. (1.5 pt) Erklären Sie den Begriff Orphan im Kontext von Prozessen. (0.5 pt) Explain the term zombie in the context of processes. State specifically how it is created and how to get rid of it. Explain the term orphan in the context of processes.

Accepted Answer

• Zombie: Stoß eines (Kind-) Prozesses in der Prozesstabelle, nach dem (Kind-) Prozessbeendet ist(+ 0,5P)• Übergeordnete Prozesse müssen den Exit-Status ihrer beendeten untergeordneten Prozesse sammeln mit der Wartezeit oder Wartezeit Syscalls, um Zombies loszuwerden. (Anmerkung: Zombies existieren aus genau diesem Grund, um ein Kind zu beenden 'Exit-Status.) (+ 1P)• Ein Prozess, dessen (ursprünglicher) Elternprozess gestorben ist (+ 0,5P), wobei das Kind verwaist zurückgelassen wird.• Zombie: Stub of a (child) process in the process table after the (child) process hasterminated. (+0.5P)• Parent processes need to collect the exit status of their terminated child processesusing the wait or waitpid syscalls to get rid of zombies. (Note: Zombies existfor precisely that reason, to keep a child process’ exit status.) (+1P)• A process whose (original) parent process has died (+0.5P), whereby the child isleft orphaned.

Question 38

Nennen Sie ein Threading-Modell, welches das Debugging von Anwendungen begünstigt, und eines, welches es erschwert. Begründen Sie Ihre Antworten. (2 pt) Name a threading model which favors application debugging and one that complicates it. Explain your answers.

Accepted Answer

• Gefälligkeiten: Eins-zu-eins (+ 0,5P). Ein Debugger kann mit einem einzigen User-Level Thread interagieren ohne Interferenz mit gleichzeitigen Threads (der gleichen Anwendung).(+ 0,5P)• Kompliziert: viele-zu-eins (+ 0,5P). Wenn ein Debugger mit einem User-Level Thread interagiert, stört es stark mit gleichzeitigen Threads (der gleichen Anwendung),z.B. Wenn ein Thread angehalten wird, müssen auch andere Threads angehalten werden. (+ 0,5P)• 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)

Question 39

Erklären Sie knapp die Rollenverteilung zwischen CPU-Scheduler und Dispatcher. (1 pt) Explain briefly the separation of concerns between CPU scheduler and dispatcher.

Accepted Answer

• CPU Scheduler: Policy welcher Prozess als nächstes läuft. (+0.5P)• Dispatcher: Mechanismus der den tatsächlichen Prozesswechsel durchführt. (+0.5P)

Question 40

Gegeben sind die 3 untenstehenden Prozesse auf einem Uniprozessorsystem mit den angegebenen Ankunftszeiten (Start-Zeit = 1.0) und Burst-Zeiten. Vervollständigen Sie die untenstehenden Ablaufpläne für die Strategien Round Robin (RR) und Shortest-Job-First (SJF). Ein Kasten im Zeitplan entspricht einer Zeitscheibe. Hinweise: Rechts neben den Ablaufplänen ist etwas Platz für Notizen. Zum Zeitpunkt 11 sind alle Prozesse beendet. (2 pt) Consider the 3 processes given below on a uniprocessor system, with the given arrival times (start time = 1.0) and burst times. Complete the schedules given below according to the policies Round Robin (RR) and Shortest Job First (SJF). A box in the schedule represents one time slice/quantum. Notes: right next to the schedules is some free space for notes. All processes are finished at time 11. Prozess Ankunft-Zeit Burst-Zeit Process Arrival time Burst time P1 1.9 5.0 P2 1.0 4.0 P3 2.6 1.0

Accepted Answer

Zeit Ablaufplan RR Ablaufplan SJFTime Schedule RR Schedule SJF 1 2 2 2 1 2 3 2 2 4 3 2 5 1 3 6 2 1 7 1 1 8 2 1 9 1 1 10 1 1• RR correct (+1P)• SJF correct (+1P)Zweiter Teil der Aufgabe bitte in Klausur 13.09.2013 In Aufgabe 2 d) nachschauen!!!!!!!!

Question 41

Welche Art von Prozessen wird von Virtual Round Robin gegenüber Robin Robin gefördert? Begründen Sie ihre Antwort knapp. (1 pt) Which kind of process is supported by Virtual Round Robin in contrast to Robin Robin? Explain your answer briefly.

Accepted Answer

• I / O-gebundene Prozesse werden über CPU-gebundene Prozesse priorisiert. (+ 0,5P)• Wenn eine E / A abgeschlossen ist, wird der gesperrte Prozess in eine Hilfswarteschlange verschoben, welche Vorrang vor der bereiten Hauptwarteschlange hat. (+ 0,5P)• 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)

Question 42

Nennen und beschreiben Sie 4 in der Vorlesung besprochene Kriterien, die ein Scheduler optimieren kann. (2 pt) Name and describe 4 criteria which a scheduler can optimize, which have been discussed in the lecture.

Accepted Answer

Throughput Anzahl der Prozesse, pro Zeiteinheit (+ 0,5P)Turnaround time Zeit von der Vorlage bis zur Fertigstellung (+ 0,5P)Response time Zeit von Anforderung bis zur ersten Antwort (+ 0,5P)CPU utilization hält die CPU so beschäftigt wie möglich (+ 0,5P)Waiting time Zeit, die jeder Prozess wartet in der bereiten Warteschlange (+ 0,5P)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)

Question 43

Betrachten Sie das Code-Beispiel in Listing 2. Stellen Sie sich ein System vor, in dem zwei Threads parallel die Funktion worker thread() ausführen. Consider the code example in Listing 2. Imagine a system where two threads simultaneously execute the function worker thread(). 1 int data [ SIZE ] ; // SIZE be defined above , i t s ac tual value does not matter 2 int pos = 0 ; 3 4 void worker thread ( void ) 5 { 6 while ( pos < SIZE ) { 7 int entry = get data from somewhere ( ) ; 8 data [ pos ] = entry ; // en ter new entry 9 pos++; 10 } 11 } Beschreiben Sie einen Ablauf, in dem ein Thread auf Speicher jenseits der Grenzen des Arrays zugreift. (2 pt) Describe a flow of execution in which one thread accesses memory beyond the bounds of the array.

Accepted Answer

Pos ist SIZE-1 (0,5pt); Beide Threads treten in den Loop-Körper ein (0,5pt); Thread 1 betritt einen Eintrag, erhöht sich auf SIZE (0,5pt); Thread 2 greift auf Daten [SIZE] zu, jenseits am Ende des Arrays (0.5pt). Jede Beschreibung, die zum gewünschten Zugang jenseits des Arrays führt, ist mit 2 Punkten markiert. Ziehen Sie Punkte für übermäßig umfangreiche Beschreibungen ab, wenneine Folge von Schritten gegeben ist, die nicht zum gewünschten Ergebnis beitragen.pos is SIZE-1 (0.5pt); both threads entered the loop body (0.5pt); thread 1 enters anentry, increases pos to SIZE (0.5pt); thread 2 accesses data[SIZE] which is beyond theend of the array (0.5pt). Every description that leads to the required access beyondthe array is marked 2 pts. Subtract points for overly extensive descriptions, when asequence of steps is given that do not contribute to the desired outcome.

Question 44

Betrachten Sie das Code-Beispiel in Listing 2. Stellen Sie sich ein System vor, in dem zwei Threads parallel die Funktion worker thread() ausführen. Consider the code example in Listing 2. Imagine a system where two threads simultaneously execute the function worker thread(). 1 int data [ SIZE ] ; // SIZE be defined above , i t s ac tual value does not matter 2 int pos = 0 ; 3 4 void worker thread ( void ) 5 { 6 while ( pos < SIZE ) { 7 int entry = get data from somewhere ( ) ; 8 data [ pos ] = entry ; // en ter new entry 9 pos++; 10 } 11 } Beschreiben Sie einen Ablauf, der zum Verlust eines Datums fuhrt. (2 pt) Describe a flow of execution that leads to a data entry being lost.

Accepted Answer

Beide Threats führen den Loop-Körper parallel (0,5pt) aus; Pos ist bei irgendeinem willkürlichen Wert;Sowohl T1 als auch T2 geben einen Eintrag (0,5pt) ein, wobei der gleiche Wert für pos und damit an den gleichen Ort eingetragen wird(0,5pt); Infolgedessen überschreibt ein Thread den gerade geschriebenen Wert des anderen Threads (0,5pt). Jede Beschreibung, die zum Datenverlust führt, ist mit 2 Punkten gekennzeichnet.Ziehen Sie Punkte für übermäßig umfangreiche Beschreibungen ab, wenn eine Folge von Schritten gegeben ist, die nicht zum gewünschten Ergebnis beitragen.Both threads execute the loop body in parallel (0.5pt); pos is at some arbitrary value;both T1 and T2 enter an entry (0.5pt), using the same value for pos and thus atthe same place (0.5pt); as a result, one thread overwrites the value just written bythe other thread (0.5pt). Every description that leads to data loss is marked 2 pts.Subtract points for overly extensive descriptions, when a sequence of steps is giventhat do not contribute to the desired outcome.

Question 45

Betrachten Sie das Code-Beispiel in Listing 2. Stellen Sie sich ein System vor, in dem zwei Threads parallel die Funktion worker thread() ausfuhren. Consider the code example in Listing 2. Imagine a system where two threads simultaneously execute the function worker thread(). 1 int data [ SIZE ] ; // SIZE be defined above , i t s ac tual value does not matter 2 int pos = 0 ; 3 4 void worker thread ( void ) 5 { 6 while ( pos < SIZE ) { 7 int entry = get data from somewhere ( ) ; 8 data [ pos ] = entry ; // en ter new entry 9 pos++; 10 } 11 } Wie nennt man ein solches Fehlverhalten von Software? Warum treten solche Fehler manchmal auf, manchmal nicht? (1 pt) How do we call such errors in software? For what reason do they sometimes occur, sometimes not?

Accepted Answer

Race Bedingungen (0,5pt); Ihr Vorkommen hängt vom Zeitpunkt der Ausführung der Threads ab, der variiert (0,5pt).Race conditions (0.5pt); their occurrence depends on the timing of the execution of threads, which is varying (0.5pt).

Question 46

Betrachten Sie das Code-Beispiel in Listing 2. Stellen Sie sich ein System vor, in dem zwei Threads parallel die Funktion worker thread() ausfuhren. Consider the code example in Listing 2. Imagine a system where two threads simultaneously execute the function worker thread(). 1 int data [ SIZE ] ; // SIZE be defined above , i t s ac tual value does not matter 2 int pos = 0 ; 3 4 void worker thread ( void ) 5 { 6 while ( pos < SIZE ) { 7 int entry = get data from somewhere ( ) ; 8 data [ pos ] = entry ; // en ter new entry 9 pos++; 10 } 11 } Was verstehen wir unter kritischen Abschnitten im Kontext von Betriebssystemen? Beschreiben Sie den Begriff kurz. (1 pt) What are critical sections in the context of operating systems? Briefly explain that term.

Accepted Answer

Abschnitte von Programmen, in denen gleichzeitige Aktivitäten oder Threads (0.5pt) den Zugriff auf Daten teilt(0,5pt).Sections of programs where concurrent activities or threads (0.5pt) access shared data (0.5pt).

Question 47

Betrachten Sie das Code-Beispiel in Listing 2. Stellen Sie sich ein System vor, in dem zwei Threads parallel die Funktion worker thread() ausfuhren. Consider the code example in Listing 2. Imagine a system where two threads simultaneously execute the function worker thread(). 1 int data [ SIZE ] ; // SIZE be defined above , i t s ac tual value does not matter 2 int pos = 0 ; 3 4 void worker thread ( void ) 5 { 6 while ( pos < SIZE ) { 7 int entry = get data from somewhere ( ) ; 8 data [ pos ] = entry ; // en ter new entry 9 pos++; 10 } 11 } Enthält der Code im Listing 2 (auf der vorherigen Seite) kritische Abschnitte? Falls ja, geben Sie die Zeilennummern des Codes in den kritischen Abschnitten an. (2 pt) Does the code in Listing 2 contain critical sections? If yes, give the line numbers of the code comprising critical sections.

Accepted Answer

Ja, tut es(0,5pt). Zeile 6, 8, 9 (0,5pt für jede korrekte Linie; -0.5pt für jede falscheLinie)Yes, it does (0.5pt). Lines 6, 8, 9 (0.5pt for each correct line; -0.5pt for each wrongline)

Question 48

Betrachten Sie das Code-Beispiel in Listing 2. Stellen Sie sich ein System vor, in dem zwei Threads parallel die Funktion worker thread() ausfuhren. Consider the code example in Listing 2. Imagine a system where two threads simultaneously execute the function worker thread(). 1 int data [ SIZE ] ; // SIZE be defined above , i t s ac tual value does not matter 2 int pos = 0 ; 3 4 void worker thread ( void ) 5 { 6 while ( pos < SIZE ) { 7 int entry = get data from somewhere ( ) ; 8 data [ pos ] = entry ; // en ter new entry 9 pos++; 10 } 11 } Enthält der Code im Listing 2 (auf der vorherigen Seite) kritische Abschnitte? Falls ¨ ja, geben Sie die Zeilennummern des Codes in den kritischen Abschnitten an. (2 pt) Does the code in Listing 2 contain critical sections? If yes, give the line numbers of the code comprising critical sections.

Accepted Answer

Ja, tut es(0,5pt). Zeile 6, 8, 9 (0,5pt für jede korrekte Linie; -0.5pt für jede falsche Linie)Yes, it does (0.5pt). Lines 6, 8, 9 (0.5pt for each correct line; -0.5pt for each wrong line)

Question 49

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.

Accepted Answer

(A) Gegenseitiger Ausschluss: Nur ein Thread kann in der CS zu einem Zeitpunkt sein.(B) Fortschritt: • Wenn kein Prozess in der CS ist, wird einer der Prozesse, die versuchen reinzukommen schließlich reinkommen. • Prozesse, die nicht eingehen wollen, behindern nicht die Prozesse, die versuchen hereinzukommen.(C) Begrenztes Warten: Sobald ein Thread beginnt, den kritischen Abschnitt zu betreten, Ist dort eine Bindung an die Anzahl der Eingänge von anderen Threads.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.(b) Progress: • If no process is in the CS one of the processes trying to enter will eventually get in. • Processes that are not trying to enter do not hinder processes that try to enter from getting in.(c) Bounded waiting: Once a thread starts trying to enter the critical section, there is a bound on the number of times other threads get in.(d) 0.5pt for each notion, 0.5pt for each correct and matching explanaton.

Question 50

Nennen Sie einen Mechanismus, mit dem man einen Mutex für ein Multiprozessorsystem implementieren kann. Ist dieser nur im Betriebssystem-Kern oder auch im User-Space nutzbar? Begründen Sie kurz, warum. (1 pt) Give a mechanism that can be used to implement a mutex for a multiprocessor system. Can this mechanism be used only in the OS kernel or in user-space as well? Briefly state why.

Accepted Answer

• Spinlocks / atomare Anweisungen und beschäftigtes Warten. Kann im Kernelraum verwendet werden und im Benutzerraum, da atomare Anweisungen häufig nicht privilegiert sind. 0,5pt für den Mechanismus, 0,5pt für eine korrekte Erklärung.• Spinlocks/atomic instructions and busy waiting. Can be used in kernel-spaceand user-space, because atomic instructions are commonly non-privileged.0.5pt for the mechanism, 0.5pt for a correct explanation.

OS (Subject) / Aufgabe 2: Prozesse und Threads/Ablaufplanung (Lesson)