Scheduler.md (4177B)
1 # Scheduler 2 3 **Source:** CS 6200 4 5 **Chapter:** P1L2 6 7 **Definition:** An operating system scheduler controls access to the CPU by giving processes execution time. 8 9 ## High Level Scheduling 10 11 If there is currently a process running the OS must preempt (interrupt and save context) the process that is currently running once its CPU time is up. The scheduler will then schedule one of the ready processes to start, and decide how long it can run for. The OS will then dispatch the process to a CPU for it to start executing. 12 13 ## Scheduler Optimization 14 15 If the scheduler runs frequently, it will both result in more cache misses, and spend more cycles on scheduling. This is because the scheduler takes ~the same amount of time to run regardless of timeslice (the amount of time allocated to a scheduled process). 16 17 ## Process 18 19 Assuming there is some number of tasks in the ready queue, the scheduler will read some number of the tasks from the ready queue and schedule one to run on the CPU. 20 21 ## Dispatching Options 22 23 ### FCFS 24 25 The choice to dispatch tasks immediately is simple and often referred to as FCFS (first come first serve) scheduling. 26 27 Pros 28 29 - Minimizes computation performed by scheduler 30 - Easy to reason about 31 - Both from development side and usage side 32 33 ### SJF 34 35 SJF (shortest job first) assigns the simplest tasks first. 36 37 #### Pros 38 39 - Maximizes throughput 40 41 #### Cons 42 43 - Maximally bad to clear the entire queue assuming all tasks in the queue at t=0 (throughput) 44 45 #### Example 46 47 Tasks: 48 49 T1 = 1s 50 T2 = 10s 51 T3 = 1s 52 53 All tasks arrive at t = 0 54 55 Schedule: 56 57 0-1 T1 58 1-2 T3 59 2-12 T2 60 61 Throughput: 3/12 = 0.25 tasks / second 62 63 Average completion time: (1 + 2 + 12) / 3 = 5 seconds 64 65 Average wait time: (0 + 1 + 2) / 3 = 1 second 66 67 ### Complex Tasks First 68 69 The goal of assigning complex tasks first is to maximize resource utilization where resources may be CPU, interrupt devices, memory, and anything else that may be utilized. 70 71 #### Pros 72 73 - Maximizes resource utilization 74 - Tries to minimize total execution time 75 76 ### Round Robin Scheduling 77 78 When running tasks that have the same priority, it is popular to perform round robin scheduling. With this approach, we perform what amounts to FCFS scheduling, but tasks may yield to each other (like when they perform I/O operations) which then places them at the end of the queue. 79 80 ### Priority Scheduling 81 82 Frequently tasks will be assigned priorities based on how important their execution is. As such, priority scheduling is frequently applied on top of other scheduling techniques to ensure higher priority tasks are scheduled before lower priority tasks. 83 84 #### Priority Aging 85 86 Priority queues can suffer from task starvation where lower priority tasks may not get scheduled. One mitigation for this issue is priority aging where tasks increase in priority the longer they are not scheduled. 87 88 #### Priority Inversion 89 90 Priority inversion occurs when a lower priority task completes prior to a higher priority task. This can happen when a lower priority task acquires a lock, gets preempted, and the higher priority task then tries to acquire the same lock. Since it can't it will get preempted by the lower priority task again, and if the lower priority task holds the lock until it completes it will finish execution prior to the higher priority task. 91 92 A common technique to help with this problem is to temporarily boost the priority of the mutex owner when a higher priority task tries to acquire the lock held by the lower priority task. 93 94 ## Preemption Options 95 96 Preemptive scheduling can be applied to any scheduling option. 97 98 An issue with preemptive scheduling is it can impose costly context switches, especially if one is trying to strictly adhere to something like complex tasks first. 99 100 ### Run-to-completion 101 102 Run-to-completion is a preemption option where the scheduler never preempts a running task. 103 104 #### Pros 105 106 - Simple 107 108 #### Cons 109 110 - Hanging tasks can cause halting 111 112 ## Runtime Estimation 113 114 Estimating the execution time for a task is difficult because there are many factors that dictate execution time. As such, we frequently use heuristics to create these estimates. 115 116 ## Links 117 118 - [Timeslice](Timeslice.md)