12 01 2022 E TS

Page 1

Advanced Operating Systems - Part A, January 12th 2022 Exercises and solutions Exam finalization Question 1.1 This is part A of the AOS’s exam and today you are finalising your entire grade. You must express now how you have finalised part B. The answer is mandatory for the entire exam. Exercise 2 — Open and closed questions (Points 15) Question 2.1 (Points 5) Describe the goals, structure and uses of a Mellor-Crummey and Scott (MCS) lock. Question 2.2 (Points 5) Describe the goals and the basic operating principles of the Buddy allocator algorithm. Question 2.3 (Points 3) Describe the purpose, the operating principles and uses of a log-structured FTL Question 2.4 (Points 2) What is the purpose of secure boot? Can you describe the basic working structure? Exercise 3 — Scheduling (Points 7) Question 3.1 (Points 7) Given the following task set: Task Arrival time ( Ai) Completion time ( Ci) T1 0 3 T2 1 10 T3 2 5 T4 3 7 T5 10 2 1. Draw the Gantt diagram of the schedule obtained by applying the Short Job First (SJF) scheduling algorithm (for remote students, you can use a grid of characters with tasks assigned to rows and time ticks assigned to columns; use character ’ .’ when task is not running and an ’ R’ when task is running) 2. Compute the turnaround time Zi for each task i in the schedule. 3. Is the SJF scheduler optimal for the considered set of tasks? Are there any better non-preemptive schedul- ing algorithms? Solution Task Arrival time ( Ai) Completion time ( Ci) Turnaround time ( Zi) T1 0 3 3 T2 1 10 26 T3 2 5 6 T4 3 7 12 T5 10 2 7 The main disadvantage of SJF is the risk of starvation for long tasks. Indeed, in the schedule of this exercise, T2 is activated at time t=2 but it has to wait until t=17 to execute, yielding to all other tasks. If more tasks were…