> For the complete documentation index, see [llms.txt](https://smadi0x86-blog.gitbook.io/smadi0x86-playground/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://smadi0x86-blog.gitbook.io/smadi0x86-playground/architecture/operating-systems/cpu-scheduling.md).
# CPU Scheduling
CPU scheduling is a process which allows one process to use the CPU while the execution of another process is on hold (in waiting state) due to unavailability of any resource like I/O etc... thereby making full use of CPU.
The aim of CPU scheduling is to make the system efficient, fast and fair.
#### We have 2 types of scheduling:
* **Long Term Scheduling:** For example the number of jobs executing at once in the primary memory.
* **Short Term Scheduling:** A small time scale, for example right now we have multiple processes wanting to run on CPU, which ones shall execute first.
## Short Term Scheduling
#### The kernel runs the scheduler at least when:
* A process switches from running to waiting.
* An interrupt occurs.
* A process is created or terminated.
**Non-preemptive system:** The scheduler must wait for one of these events.
**Preemptive system:** The scheduler can interrupt a running process.
## Criteria for comparing scheduling algorithms
* **CPU Utilization:** The percentage of time that the CPU is busy.
* **Throughput:** The number of processes completing in a unit of time.
* **Turnaround time:** The length of time it takes to run a process from initialization to termination, including all the waiting time.
* **Waiting time:** The total amount of time that a process is in the ready queue.
* **Response time:** The time between when a process is ready to run and its next I/O request.
## Scheduling Algorithms
1. **FCFS:** First Come, First Served.
2. **Round Robin:** Use a time slice and preemption to alternate jobs.
3. **SJF:** Shortest Job First.
4. **Shortest Remaining Time First (SRTF):** A Preemptive SJF.
5. **Multilevel Feedback Queues:** Round robin on each priority queue.
### FCFS
* The scheduler executes jobs to completion in arrival order.
* In early FCFS schedulers, the job did not relinquish the CPU even when it was doing I/O.
* We will assume a FCFS scheduler that runs when processes are blocked on I/O, but that is non-preemptive, i.e., the job keeps the CPU until it blocks (say on an I/O device).
**Advantage:** FCFS is simple to implement.
**Disadvantages: A**verage wait time is highly variable as short jobs may wait behind long jobs.
FCFS may lead to poor overlap of I/O and CPU since CPU-bound processes will force I/O bound processes to wait for the CPU, leaving the I/O devices idle.
### Round Robin
* Variants of round robin are used in most time sharing systems.
* Add a timer and use a preemptive policy.
* After each time slice, move the running thread to the back of the queue.
* Selecting a time slice:
* **Too large:** Waiting time suffers, degenerates to FCFS if processes are never preempted.
* **Too small:** Throughput suffers because too much time is spent context switching.
{% hint style="info" %}
Balance these tradeoffs by selecting a time slice where context switching is roughly 1% of the time slice.
{% endhint %}
**Today:**
* **T**ypical time slice is 10-100 ms.
* Context switch time is 0.1-1 ms.
* **Advantage:** It's fair; each job gets an equal shot at the CPU.
* **Disadvantage:** Average waiting time can be bad.
### Shortest Job First
Schedule the job that has the least (expected) amount of work (CPU time) to do until its next I/O request or termination.
**Advantages:**
* Provably optimal with respect to minimizing the average waiting time.
* Works for preemptive and non-preemptive schedulers.
* Preemptive SJF is called SRTF (shortest remaining time first).
**Disadvantages:**
* Impossible to predict the amount of CPU time a job has left.
* Long running CPU bound jobs can starve.
### Multilevel Feedback Queues
Multilevel feedback queues use past behavior to predict the future and assign job priorities.
MLFQ overcomes the prediction problem in SJF.
* If a process is I/O bound in the past, it is also likely to be I/O bound in the future (programs turn out not to be random).
* To exploit this behavior, the scheduler can favor jobs that have used the least amount of CPU time, thus approximating SJF.
* This policy is adaptive because it relies on past behavior and changes in behavior result in changes to scheduling decisions.
#### Adjusting Priorities in MLFQ:
* Job starts in highest priority queue.
* If job's time slices expires, drop its priority one level.
* If job's time slices does not expire (the context switch comes from an I/O request instead), then increase its priority one level, up to the top priority level.
{% hint style="info" %}
CPU bound jobs quickly drop in priority and I/O bound jobs stay at a high priority.
{% endhint %}
### Summary
1. **FCFS:** Not fair, and average waiting time is poor.
2. **Round Robin:** Fair, but average waiting time is poor.
3. **SJF:** Not fair, but average waiting time is minimized assuming we can accurately predict the length of the next CPU burst. Starvation is possible.
4. **Multilevel Queuing:** An implementation (approximation) of SJF.
{% hint style="info" %}
Our modeling assumed that context switches took no time, which is unrealistic.
{% endhint %}
Example #1 (FCFS & RR)
5 Jobs, 100 seconds each, time slice is 1 second and context switch time of 0
1. Using FCFS, each job will complete in 100 seconds and then do a context switch, we can calculate average completion time (100 + 200 + 300 + 400 + 500 / 5 = 300).
2. Now for Round Robin, each job will get executed based on time slice (quantum time) for 1 second and move to the next job.
So if we calculate the completion time for round robin, each job will accomplish 1 second of work every 5 seconds, we can get FCFS completion time and minus it from the other 4 jobs to get the completion time for the first job, as its the first job which executed the time slice. The same applies for job 2 which will be `500 - 3 = 497` etc...
3. Now to calculate the wait time which is the time that the job waits until it gets executed, we can do it by computing `completion time - length (burst time)`
#### Example #2 (FCFS & RR)
5 Jobs of length 50, 40, 30, 20 and 10, time slice 1 second and context switch time of 0 seconds
1. Using FCFS, we first get the first burst time (length) which is 50 then to get the second job burst time we add `50 + 40 = 90` etc...
2. For round robin with a time slice (quantum time) of 1, the first job that will finish is job 5 because it needs to reach only 10 which would take `10 x 5 = 50` completion time, the formula used is `Length x Job number`.
3. Finally, for the waiting time we calculate using same formula which is `completion time - length`
Example #3 (FCFS & RR & SJF)
5 Jobs of length 50, 40, 30, 20 and 10 seconds each, time slice of 1 second and context switch time is 0
1. We calculate FCFS & RR same as Example 1 and 2
2. For SJF, we must pick the shortest Job First, which in this case is Job 5 which is = 10. after that we go to the second shortest job which is job 4 which is equals to `10 + 20 = 30` then to job 3 which is `30 + 30 = 60` etc...
3. Finally, for the waiting time we calculate using same formula which is `completion time - length`
