10 07 2023 E TS

Page 1

Advanced Operating Systems - Part A, July 10th, 2023 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) Address the following 3 sub-questions related to concurrency in the Linux kernel. Please USE CAPITAL LETTERS and respect the space allocated to each sub-question. Solution 1. Queued spinlocks. Linux queued spinlocks ( qspinlock) are an extension of traditional cache-aware MCS locks. Describe concretely the additional field that characterizes this extension and the rationale. A: The additional field is the ’pending’ field. It is used to account for contention over the spinlock. If there is only one locker and one waiter, the MCS structure is not used but instead, the waiter spins the waiter spins over the ’locked’ field. Only after a third thread enters the critical section then MCS must be used to avoid the cache ping-pong effect. The pointer to the last element in the MCS queue is stored in the ’tail’ field of the qspinlock structure. 2. Memory consistency. Assuming x is initialised to 0, describe the conditions under which the following multi-threaded program could end printing 0: 1 // Thread 1 // Thread 2 2 x = 1; while(done == 0) { /* loop */ } 3 done = 1; print(x); A: This might happen on a partially store ordered machine (e.g. ARM) where the order of stores is not preserved (unless memory barriers are used). 3. CPU scaling. Complete the following chart with the (approximate) behavior of power consumption and number of transistors per CPU as observed in the last 20 years and discuss its implications. Use just…