Loading....
Coupon Accepted Successfully!

 

CPU Scheduling

 

829.pngAlmost all programs have some alternating cycle of CPU number crunching and waiting for I/O of some kind. (Even a simple fetch from memory takes a long time relative to CPU speeds.)


Preemptive Scheduling

834.pngCPU scheduling decisions take place under one of four conditions:

  1. When a process switches from the running state to the waiting state, such as for an I/O request or invocation of the wait( ) system call.
  2. When a process switches from the running state to the ready state, for example in response to an interrupt.
  3. When a process switches from the waiting state to the ready state, say at completion of I/O or a return from wait( ).
  4. When a process terminates.

839.pngIf scheduling takes place only under conditions 1 and 4, the system is said to be non-preemptive, or cooperative. Under these conditions, once a process starts running it keeps running, until it either voluntarily blocks or until it finishes. Otherwise the system is said to be preemptive.


Dispatcher

844.pngThe dispatcher is the module that gives control of the CPU to the process selected by the scheduler. This function involves:

  • Switching context.
  • Switching to user mode.
  • Jumping to the proper location in the newly loaded program.

849.pngThe dispatcher needs to be as fast as possible, as it is run on every context switch. The time consumed by the dispatcher is known as dispatch latency.


Scheduling Algorithms

First Come First Serve (FCFS)

854.pngJobs are executed on first come, first serve basis.

859.pngEasy to understand and implement.

864.pngPoor in performance as average wait time is high.


Wait time of each process is following

Process Wait Time : Service Time - Arrival Time

P0 0 - 0 = 0

P1 5 - 1 = 4

P2 8 - 2 = 6

P3 16 - 3 = 13


Average Wait Time: (0+4+6+13) / 4 = 5.55

 

870.png 

First come first serve

Shortest Job First (SJF)

 

875.pngBest approach to minimize waiting time.

880.pngImpossible to implement

885.pngProcesser should know in advance how much time process will take.


Wait time of each process is following

Process Wait Time :

Service Time - Arrival Time

P0 3 - 0 = 3

P1 0 - 0 = 0

P2 16 - 2 = 14

P3 8 - 3 = 5


Average Wait Time: (3+0+14+5) / 4 = 5.50

890.png 

Shortest Job First


Priority Based Scheduling

895.pngEach process is assigned a priority. Process with highest priority is to be executed first and so on.

900.pngProcesses with same priority are executed on first come first serve basis.

905.pngPriority can be decided based on memory requirements, time requirements or any other resource requirement.


Wait time of each process is following

Process Wait Time :

Service Time - Arrival Time

P0 0 - 0 = 0

P1 3 - 1 = 2

P2 8 - 2 = 6

P3 16 - 3 = 13

Average Wait Time: (0+2+6+13) / 4 = 5.25


Round Robin Scheduling

910.pngEach process is provided a fix time to execute called quantum.

915.pngOnce a process is executed for given time period. Process is preempted and other process executes for given time period.

921.pngContext switching is used to save states of preempted processes.


Wait time of each process is following

Process Wait Time: Service Time - Arrival Time

P0 (0-0) + (12-3) = 9

P1 (3-1) = 2

P2 (6-2) + (15-9) = 10

P3 (9-3) + (18-12) = 12


Average Wait Time: (9+2+10+12) / 4 = 8.25

 

926.png 





Test Your Skills Now!
Take a Quiz now
Reviewer Name