Chapter 6 - Lecture

First-Come, First-Served (FCFS) Scheduling
􀂄 Ready queue is FIFO: process served in order of arrival at the queue

Shortest-Job-First (SJF) Scheduling
􀂄 CPU is assigned to the process with the smallest next CPU burst, use FCFS to break ties
􀂄 SJF is optimal: give the minimum average waiting time for a given set of processes.
􀂄 Two schemes:
􀀩 Nonpreemptive: once the CPU is given to a process, the process cannot be preempted until it finishes its CPU burst.
􀀩 Preemptive: if a new process arrives with next CPU burst shorter than the remaining time of the current executing process, preempt the current executing process.
􀀗 Also called Shortest-Remaining-Time-First (SRTF).

Priority Scheduling
􀂄 A priority number (integer) is associated with each process
􀂄 The CPU is allocated to the process with the highest priority (smallest integer ≡ highest priority). FCFS used to break ties
􀀩 Preemptive: preempt the CPU if the priority of the newly arrived process is higher than the priority of the currently running process
􀀩 Nonpreemptive: allow the currently running process to complete its CPU burst
􀂄 SJF is a priority scheduling where priority number is the predicted next CPU burst time.
􀂄 Problem: Starvation – low-priority processes may never execute.
􀀩 Solution: Aging –gradually increase the priority of the processes as time progresses.

Round Robin (RR) Scheduling
􀂄 Designed for time-sharing systems
􀂄 The algorithm:
􀀩 Each process gets a small unit of CPU time (time quantum or time slice), usually 10-100 milliseconds.
􀀩 After the time quantum has elapsed, the process is preempted and added to the end of the ready queue (an FIFO queue).
􀀩 Essentially FCFS scheduling with preemption
􀂄 If there are n processes in the ready queue and the time quantum is
q, then response time is no more than (n-1)q
􀀩 Smaller q 􀃎 smaller response time, but more context switches
􀂄 Performance of RR depends on size of time quantum
􀀩 q large: same as FCFS
􀀩 q small: each of the n processes has the impression that it has its own
processor running at 1/n the speed of the real processor
􀀗 q must be large with respect to context switch time, otherwise overhead is too high.

Multilevel Queue Scheduling
􀂄 Ready queue is partitioned into separate queues; each process is permanently assigned to one queue based on some property of the process (e.g., process type)
􀀩 E.g., separate queues for foreground (interactive) processes and background (batch) processes
􀂄 Each queue has its own scheduling algorithm
􀀩 E.g., foreground – RR, background – FCFS
􀂄 Scheduling must be done between the queues.
􀀩 Fixed priority preemptive scheduling
􀀗 E.g., foreground queue has absolute priority over background queue
􀀗 Possibility of starvation.
􀀩 Time slice between the queues: each queue gets a certain amount of CPU time
􀀗 E.g., 80% CPU time to foreground in RR, 20% to background in FCFS