CPU Scheduling Algorithms

• Operating Systems (CS/CPE 408) : CPU Scheduling

• Non-Preemptive Vs Preemptive Scheduling

Non-Preemptive: Non-preemptive algorithms are designed so that once a process enters the running state(is allowed a process), it is not removed from the processor until it has completed its service time ( or it explicitly yields the processor). 

context_switch() is called only when the process terminates or blocks. 

Preemptive: Preemptive algorithms are driven by the notion of prioritized computation. The process with the highest priority should always be the one currently using the processor. If a process is currently using the processor and a new process with a higher priority enters, the ready list, the process on the processor should be removed and returned to the ready list until it is once again the highest-priority process in the system. 

context_switch() is called even when the process is running usually done via a timer interrupt

• First In First Out (FIFO)

This is a Non-Premptive scheduling algorithm. FIFO strategy assigns priority to processes in the order in which they request the processor.The process that requests the CPU first is allocated the CPU first.When a process comes in, add its PCB to the tail of ready queue. When running process terminates, dequeue the process (PCB) at head of ready queue and run it.

Consider the example with P1=24, P2=3, P3=3

  Gantt Chart for FCFS :  0 - 24 P1 , 25 - 27 P2 , 28 - 30 P3

  Turnaround time for P1 = 24

  Turnaround time for P1 = 24 + 3

  Turnaround time for P1 = 24 + 3 + 3

  Average Turnaround time = (24*3 + 3*2 + 3*1) / 3

  In general we have (n*a + (n-1)*b + ....) / n

  If we want to minimize this, a should be the smallest, followed by b and

  so on.

Comments: While the FIFO algorithm is easy to implement, it ignores the service time request and all other criteria that may influence the performance with respect to turnaround or waiting time.

Problem: One Process can monopolize CPU

Solution: Limit the amount of time a process can run without a context switch. This time is called a time slice.

• Round Robin

Round Robin calls for the distribution of the processing time equitably among all processes requesting the processor.Run process for one time slice, then move to back of queue. Each process gets equal share of the CPU. Most systems use some variant of this.

Problem: Round robin assumes that all processes are equally important; each receives an equal portion of the CPU. This sometimes produces bad results. Consider three processes that start at the same time and each requires three time slices to finish

• Priority Based Scheduling

Run highest-priority processes first, use round-robin among processes of equal priority. Re-insert process in run queue behind all processes of greater or equal priority.

Problem: Priority scheduling may cause low-priority processes to starve

• Shortest Job First

Maintain the Ready queue in order of increasing job lengths. When a job comes in, insert it in the ready queue based on its length. When current process is done, pick the one at the head of the queue and run it.

Problem: SJF minimizes the average wait time because it services small processes before it services large ones. While it minimizes average wiat time, it may penalize processes with high service time requests.

• Multi-Level Feedback Queue

Several queues arranged in some priority order.

Each queue could have a different scheduling discipline/ time quantum.

Lower quanta for higher priorities generally.

Defined by:

# of queues

scheduling algo for each queue

when to upgrade a priority

when to demote

http://www1bpt.bridgeport.edu/sed/projects/cs503/Spring_2001/kode/os/scheduling.htm

• CPU Scheduling Algorithms

http://www.youtube.com/watch?v=QpuFq3-fdhw&feature=related

• CPU Scheduling

http://www.youtube.com/watch?v=5p3bAC-AX84&feature=related