How to decide which process to run at which time? (scheduling problem)
Scheduler: Part of the OS that makes the scheduling decision (uses a scheduling algorithm)
Processing environments: Batch processing, Interactive/Multiprogramming, Real time processing e.g. robotics, self driving car
Evaluating scheduling algorithms: Criteria is different for different environments, but these are common among all
- Fairness: All processes/users get a fair share of CPU time, no hogging or starvation
- Utilisation: Maximise utilisation of all parts of the computing system
Scheduling policies
- Non-preemptive (cooperative): A process stays scheduled until it blocks (IO) or it voluntarily gives up CPU time
- Preemptive: OS gives the process a fixed amount of time to run, after which it picks another process if available

Overall Process

Scheduler is triggered (OS takes over)
If context switch is needed: context of current process is saved, and placed on blocked/ready queue
Scheduling algorithm picks a suitable process to run
Setup context for the new process, then let it run

Batch Processing

No user interaction required, no need to be responsive
Generally used in environments like supercomputers, where users submit programs to be executed
Mostly uses non-preemptive scheduling (easier to understand and implement)
Evaluation Criteria
- Turnaround time: Total time taken from when job is submitted to when it is finished (compute time + waiting time)
- Throughput: Number of tasks finished per unit time
- CPU utilisation: % of time that CPU is working on a task

FCFS First-Come-First-Serve (non-preemptive)
- There is a FIFO queue, when processes become ready, they are enqueued. Remove from the front of the queue when we want to schedule something
- Guaranteed no starvation: Number of tasks in front of a task is always decreasing, and it will eventually get its chance (given no infinite execution)
- Non optimal average waiting time: long tasks increase other tasks waiting time
- Convoy effect: CPU bound task causes IO to be idle, IO bound tasks cause CPU to be idle
SJF Shortest Job First (non-preemptive)
- Select task with smallest total CPU time
- Total CPU time for tasks needs to be known in advance
  - Can be inferred by length of previous CPU bound phases
  - Exponential average: $predicted_{n + 1} = α actual_{n} + (1 - α) predicted_{n}$ , where $α$ is a weight placed on history
- Guarantees minimised average waiting time
- Starvation: long tasks can be blocked if short tasks keep coming
SRT Shortest Remaining Time (preemptive)
- When tasks arrive, switch to the task with the shortest remaining time

Active user interacting with system
Needs to be responsive: low and consistent response time
Preemptive scheduling algorithms ensure good response time
- Scheduler needs to run periodically
Evaluation Criteria
- Response time: Time between request and system’s response
- Predictability: Variation in response time
Periodic Scheduler
- Using timer interrupt: an interurupt that happens periodically (based on hardware clock). Scheduler is invoked in the timer interrupt handler
- Interval of Timer Interrupt ITI: How long between interrupts, usually 1-10ms
- Time Quantum: Amount of time that we let a process run, can be constant or variable. Must be multiple of ITI, commonly 5-100ms

RR Round Robin

Tasks are stored in a FIFO queue
Let the first task in the queue run until: Time quantum elapsed, or task gives up CPU voluntarily, or task blocks
Then, the task is placed at the end of the queue
Blocked tasks are moved to another queue to wait for their requested resource; When blocked task is ready, it is placed at the end of the queue
Analysis
- Guarantees response time: for $n$ tasks and quantum $q$ , time before a task gets CPU is max $(n - 1) q$
- Timer interrupt needed: for scheduler to check on quantum expiry
- Time quantum choice
  - Big quantum → better CPU utilisation but long wait time
  - Small quantum → bigger overhead context switching, shorter wait time

Priority Scheduling

Assign a priority value to all tasks, select the task with highest priority
Preemptive version: higher priority process can preempt current process
Non-preemptive version: new tasks have to wait for next round of scheduling
Analysis
- Low priority processes can starve (worse in preemtive version). Can be solved by decreasing priority of currently running process after every time quantum
- Hard to guarantee or control the exact amount of CPU time given to a process using priority
- Priority inversion: Tasks A, B, C with decreasing priority. C runs first, locking a resource needed by A. B preempts C, A preempts B. B continues to run because it is higher priority than C, preventing A from running even though it has higher priority

MLFQ Multi-Level Feedback Queue

New job → highest priority
Job fully utilising time quantum → priority reduced
Job gives up/blocks before finishing time quantum → no priority change
One queue for each priority
Higher priority tasks run first, equal priority tasks run in RR
Analysis
- IO bound tasks don’t fully use a time quantum, remaining high priority → fast response time
- CPU bound tasks end up at lowest priority, but are only interrupted by short IO bound tasks, shortening time taken to complete tasks

Lottery Scheduling

Give out lottery tickets to processes for various system resources (one process can be given multiple)
When a scheduling decision is needed, a lottery ticket is randomly chosen, and the winner is granted the resource
In the long run, a process holding $x %$ of tickets can use the resource $x %$ of the time
Analysis
- Responsive: a newly created process can participate in the next lottery
- Good control: A process can distribute tickets to its children; Important processes can be given more tickets; Can achieve different proportion of usage per resource per task with a different of tickets for each resource