Scheduling Algorithm

An Algorithm used by the Scheduler

Name	Property	Scheduling criterion	Pros	Cons
FCFS	Intrinsically non-preemptive; could accommodate preemption at time of I/O completion events	Arrival time (intrinsic property)	Fair; no starvation	High variance in response time; convoy effect
SJF	Intrinsically non-preemptive; could accommodate preemption at time of new job arrival and/or I/O completion events	Expected execution time of jobs (intrinsic property)	Preference for short jobs; provably optimal for response time; low variance in response times	Potential for starvation; bias against long running computations
Priority	Could be either non-preemptive or preemptive	Priority assigned to jobs (extrinsic property)	Highly flexible since priority is not an intrinsic property; its assignment to jobs could be chosen commensurate with the needs of the scheduling environment	Potential for starvation (ameliorated by dynamically increasing priority in proportion to waiting time)
SRTF	Similar to SJF but uses preemption	Expected remaining execution time of jobs (intrinsic)	Similar to SJF	Similar to SJF
Round robin	Preemptive allowing equal share of the processor for all jobs	Time quantum (extrinsic)	Equal opportunity for all jobs	Overhead for context switching among jobs

Preemptive

Algorithm that forcible takes the Processor away from the current scheduled Process in response to an external event (e.g. I/O completion Interrupt, timer interrupt)

Shortest Remaining Time First

Round Robin

Priority

Round Robin

• Round Robin is a Preemptive Scheduling Algorithm
• Requires a timer interrupt
• When a processes starts, it is given a time quantum (time slice) which limits the continuous CPU time it may use
• When a process is dispatched, the timer is set to interrupt at the end of the remaining time quantum
• If a processes uses up its remaining time quantum
  • The process is interrupted
  • The scheduler is called to put the process at the end of the ready list
  • The process’ remaining time quantum is reset
• If an interrupt other that the timer occurs, the process’ remaining time quantum is reduced by the amount of time it has used prior to the interrupt

Link to original

Nonpreemptive

An algorithm that allows the current scheduled process on the CPU to voluntarily reliquish the processor (either by terminating or making an I/O system call)

Intrinsic

First Come First Serve

Shortest Job First

Extrinsic

Priority

Transclude of Linux#linux-scheduler