Process scheduling

Long Term Scheduling: putting new processes in the ready queue Short Term Scheduling: which process in the ready queue must be executed next

Short-term scheduling algorithms focuses on minimizing/maximizing on the following criteria:

  • CPU utilization: percentage of time the CPU is actively executing things (and not waiting for I/O or context switching). When every process waits $p$ of its time on I/O and there are $n$ processes the CPU utilization is $1 - p^n$ (maximize).
  • Turnaround time: time process enter ready queue until it terminates, average turnaround time is the average turnaround for all processes (maximize).
  • Throughput: number of processes executed completely in a time unit (maximize).
  • Waiting time: time that a process waits in ready queue (minimize).
  • Response time: time it takes for a problem to respond to input (minimize).

Starvation: when a process waits too long before using the CPU

Scheduling algorithms #

Preemptive scheduling algorithms allow the scheduler to interrupt process and allocate the CPU to another process. Processes with a higher-priority can preempt lower-priority processes. Non-preemptive: processes are run until they are complete.

Are often displayed in a Gannt Chart.

Non-preemptive scheduling algorithms:

  • First Come First Served (FCFS): executes processes in the order they arrive
  • Shortest Job First (SJF): chooses the next process with the minimal execution time, this minimizes the average turnaround time.
  • Shortest Job First with Aging: prevents starvation of longer jobs by giving priority to age, e.g. $\text{priority} = 1 / \text{execution} + 0.1 \times \text{waiting time}$.

Preemptive scheduling algorithms:

  • Shortest Remaining Time First: preemptive version of SJF: when a new process enters the queue, the current process is swapped out if its remaining time is longer than the execution time of the new process.
  • Round Robin (RR): assigns each process to execute for one quantum, does not consider priority. Optimal quantum has to be chosen to balance between context switching overhead and minimizing response time.

Process categories #

  • Real-time processes: have upper limit on responsive time, generally industrial applications
  • Interactive processes: requires input from user and provides output to user
  • Batch processes: no interaction with users, output in files

Multi-queue scheduling: defines multiple priority levels and uses round robin for each level. If the queue from a level is empty the next queue is used and so on. Can be used with feedback: the OS heuristically determines priority of processes, processes are moved between queues based on their behavior.

Lottery scheduling: uses probability to decide which processes is executed next

Real-time scheduling: for real-time systems, achieved by dividing the program into multiple short processes that can be executed in short time intervals