Read the following paper excerpts, and answer the questions below.
The total length of your response should not exceed ~500 words. Submit responses via gradescope.
Briefly describe the problem(s) Lozi et al. discovered with the CFS algorithm, and the problem(s) they caused.
McClure et al. describe a variety of load balancing and core allocation policies in Section 3.2. Which combination(s) of these best represents CFS, as Lozi et al. describe it? If no combination fits well, describe the policy CFS implements.
Lozi et al. state that:
Load balancing is an expensive procedure on today’s systems, both computation-wise, because it requires iterating over dozens of runqueues, and communication-wise, because it involves modifying remotely cached data structures, causing extremely expensive cache misses and synchronization. (Section 2.2)
McClure et al.’s results show in Figure 3a that the (i) work stealing and (ii) JBSQ load balancing policies achieve the best performance. Do these results repudiate or agree with Lozi et al.’s statement? If each repudiates the statement, how so? If each agrees with the statement, how does it minimize the expensive overheads?
Design an adversarial workload for each of the following two cases in which:
CFS (after Lozi et al.’s fixes), would have poor tail latency.
Work stealing, as McClure et al. describe, would have poor tail latency.
Importantly, keep the average load constant between your workload(s) and non-adversarial cases that have lower tail latency. In other words, we already know that increasing offered load will result in higher tail latency, and in this homework we want to focus on other effects. If no such adversarial workload exists, explain why not.