Cpu Scheduling Algorithms – Operating System

  • August 8, 2021
  • Aashish Mishra

Basic Terminologies

  • Burst Time / Execution Time.
  • Waiting Time
  • Arrival Time
  • Exit Time
  • Turnaround Time
  • Turnaround Time = Exit Time – Arrival Time = Burst Time + Waiting Time
  • Waiting Time = Turnaround Time – Burst Time
  • Response Time : Time between a process enters ready queue and get scheduled on the CPU for the first time.

Criteria for CPU Scheduling Algorithm

  1.  Average Waiting Time (Minimum)
  2. Average Response Time (Minimum)
  3. CPU utilization (Maximum)
  4. Throughput:- No. of process executed per unit time. (Maximum)
  5. Average Turnaround Time (Minimum)

First Come First Serve (FCFS)

>> It is Simplest Scheduling Algorithm, it assign CPU to the process which arrives first.

>> It is easy to understand and can easily be implemented using Queue Data Structure.

>> It is always non-pre-emptive in nature and usually poor in performance as the avg. waiting time is higher.

 

Convey Effect : 

   

Smaller Process may have to wait for long time for bigger process to release CPU. It is called Convey Effect. This Process can be resolved by Using Shortest job first Algorithm.

 

Shortest job first

  • This is also known as Shortest job Next.
  • This can be both non-preemptive or preemptive scheduling algorithm.
  • Preemptive SJF is also known as Shortest Remaining Time First (SRTF).
  • Best Approach to minimize the waiting time.
  • Easy to implement in interactive systems where required CPU time is not known.
  • The Processor should know in advance how much time process will take.
  • Process with longer burst time will suffer from Starvation.

Non-Preemptive

Preemptive

 

Priority Scheduling

  • There is priority number is assigned to each process.
  • In some systems, the lower the number the higher the priority. While, in others, the higher the number, the higher will be the priority.
  • There are two type of priority scheduling algorithm exist. One is Preemptive Priority while other is Non-preemptive Priority Scheduling.

Non-preemptive Priority Scheduling

  • The process are scheduled according to the priority number assigned to them. Once the process gets scheduled, it will run till the completion.
  • Generally, the lower the priority number, the higher is the priority of the process.
  • Jobs will be assigned to the  CPU according to their priority, process with higher priority will be assigned first.
  • If two jobs have similar priority number assigned to them, the one with the least arrival time will be executed first.

Preemptive Priority Scheduling

  • If a process with higher priority than the process currently being executed arrives the CPU is preempted and given to the higher priority process.
  • The waiting time for the process having the highest priority will always be zero.
  • It is more expansive and difficult to implement. Also a lot of time is wasted in switching.

Round Robin Scheduling

  • A preemptive scheduling designed for time sharing system.
  • The ready Queue is treated as a circular queue.
  • A small execution time interval is defined as the time quantum or time slice.

 

Process Scheduling – Operating System