Different CPU Scheuling Algorithms

1. First-Come, First-Served (FCFS) Scheduling

• Ready queue is a FIFO queue

• Example Process Burst Time

P1 24

P2 3

P3 3

• Arrival order: P1 , P2 , P3

– The Gantt Chart for the schedule is:

– Waiting time for P1 = 0; P2 = 24; P3 = 27

• Average waiting time: (0 + 24 + 27)/3 = 17

• Arrival Order: P2 , P3 , P1 .

– The Gantt chart for the schedule is:

– Waiting time for P1 = 6; P2 = 0; P3 = 3

• Average waiting time: (6 + 0 + 3)/3 = 3

• Much better than previous case.

• Convoy effect: I/O-bound (short CPU-bursts) wait for CPU-bound (long CPU-bursts)

• Non-preemptive

2. Shortest Job First (SJF) Scheduling

• Each process knows the length of its next CPU burst

– Use these lengths to schedule the process with the shortest time.

• Two schemes:

– Non-preemptive – once CPU given to the process it cannot be preempted until completes its CPU burst.

– Preemptive – if a new process arrives with CPU burst length less than remaining time of current executing process, preempt.

• Shortest-Remaining-Time-First (SRTF).

• SJF is optimal – gives minimum average

waiting time for a given set of processes.

Example of Non-Preemptive SJF

Example of Preemptive SJF

3. Round Robin (RR)

• Each process gets a small unit of CPU time (time quantum), usually 10-100 milliseconds. After this time has elapsed, the process is preempted and added to the end of the ready queue.

• If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once. No process waits more than (n-1)q time units.

• Performance

– q large Þ FIFO

- q small Þ q must be large

Example: RR with Time Quantum = 20

4. Multilevel Queue Scheduling

• Ready queue is partitioned into separate queues

– According to process properties and scheduling needs

– Foreground (interactive) and background (batch)

• Processes are permanently assigned to one queue

• Each queue has its own scheduling algorithm,
foreground – RR, background – FCFS

• Scheduling must be done between the queues.

– Fixed priority scheduling; i.e., serve all from higher-priority then from lower-priority. Possibility of starvation.

– Time slice – each queue gets a certain amount of CPU time which it can schedule amongst its processes; eg., 80% to foreground in RR 20% to background in FCFS

5. Multiple-Processor Scheduling

• Homogeneous processors within a multiprocessor

– Separate vs. common ready queue

– Load sharing

• Symmetric Multiprocessing (SMP) – each processor makes its own scheduling decisions

– Access and update a common data structure

– Must ensure two processors do not choose the same process

• Asymmetric multiprocessing – only the master process accesses the system data structures

6. Real-Time Scheduling

• Hard real-time systems – required to complete a critical task within a guaranteed amount of time

– A process is submitted with a statement of the amount of time in which it needs to complete or perform I/O. The scheduler uses the statement to admit (and guarantee) or reject the process

– Resource reservation – requires the scheduler knows exactly how long each type of OS functions takes to perform

– Hard real-time systems are composed of special-purpose SW running on HW dedicated to their critical process, and lack the full functionality of modern computers and OS

• Soft real-time computing – requires that critical processes receive priority over less fortunate ones.

– Ex. Multimedia, high-speed interactive graphics…

• Related scheduling issues for soft real-time computing

– Priority scheduling – real-time processes have the highest priority

• The priority of real-time process must not degrade over time

– Small dispatch latency

• May be long because many OS wait either for a system call to complete or for an I/O block to take place before a context switch

• Preemption point

• Make the entire kernel preemptible (ex. Solaris 2)