P3L1: Scheduling

Question 1

How does scheduling work? What are the basic steps and datastructures involved in scheduling a thread on the CPU?

What are the overheads associated with scheduling? Do you understand the tradeoffs associated with the frequency of preemption and scheduling/what types of workloads benefit from frequent vs. infrequent intervention of the scheduler (short vs. long timeslices)?

Can you work through a scenario describing some workload mix (few threads, their compute and I/O phases) and for a given scheduling discipline compute various metrics like average time to completion, system throughput, wait time of the tasks…

Do you understand the motivation behind the multi-level feedback queue, why different queues have different timeslices, how do threads move between these queues… Can you contrast this with the O(1) scheduler? Do you understand what were the problems with the O(1) scheduler which led to the CFS?

Thinking about Fedorova’s paper on scheduling for chip multi processors, what’s the goal of the scheduler she’s arguing for? What are some performance counters that can be useful in identifying the workload properties (compute vs. memory bound) and the ability of the scheduler to maximize the system throughput.

Question 2

10. Round Robin Scheduling

Answer 2

Question 3

11. Timesharing and Timeslices

Answer 3

Question 4

What is a cpu bound task?

Answer 4

Just run in the cpu, no I/O

https://stackoverflow.com/questions/868568/what-do-the-terms-cpu-bound-and-i-o-bound-mean

Question 5

What is a i/o bound task?

Answer 5

A task that has i/o operations

Question 6

What is time quantum in linux

Answer 6

• The time quantum value is the maximum CPU time portion assigned to the process in that epoch. When a process has exhausted its time quantum, it is preempted and replaced by another runnable process
• Equivalent to timeslice

https://www.oreilly.com/library/view/understanding-the-linux/0596002130/ch11s02.html

Question 7

18. Linux O(1) Scheduler

Answer 7

Question 8

What is a CPU cycle

Answer 8

A clock cycle, or simply a “cycle,” is a single electronic pulse of a CPU. During each cycle, a CPU can perform a basic operation such as fetching an instruction, accessing memory, or writing data

https://techterms.com/definition/clockcycle

Question 9

What is a CPI

Answer 9

number of cycles needed to complete each instruction

https://techterms.com/definition/clockcycle

Question 10

What is a IPC

Answer 10

Instructions per cycle