08 07 2022 E TS

Page 1

Advanced Operating Systems - Part A, July 8th, 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 Completely Fair Scheduling algorithm Question 2.2 (Points 5) Describe the deadlock problem and provide a schematic overview of the possible solutions Question 2.3 (Points 3) Describe the goals and operating principles of the log-structured file system Question 2.4 (Points 2) Describe the main methods used by Linux for device discovery Exercise 3 — Scheduling (Points 7) Question 3.1 (Points 7) Given task set in the following table, • draw the Gantt diagram of the schedule obtained by applying the Highest Response Ratio Next (HRRN) • fill the last column in table according to the above scheduling algorithm • consider a preemptive variant of HRRN where response ratios and scheduling decisions are taken at each time step t with the following additional rule: For a running task Ti, the waiting time Wi at time t is t − Ai when the first preemption would occur? Which task preempts which one? Justify the answer Solution 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 3 3 Task Arrival time ( Ai) Completion time ( Ci) Turnaround time ( Zi) T1 0 5 5 T2 1 4 14 T3 2 3 9 T4 2 2 5 T5 4 1 4 For the preemptive HRRN the first preemption occurs at time t=4, T4 preempts T1; in fact: • time t = 0: The first task to start is T1 because it is the only one ready at time t=0. • time t = 1: T2 arrives and: – RR1(t=1) = (1+5)/5 = 1.2 – RR2(t=1)…