#Scheduling  #Operating-System 

CPU Scheduling in Operating Systems

  • Short-term schedular
  • Move processes from: Ready Queue (Ready state)--> Running state
  • CPU scheduling can be of two types
    • Non-Preemptive scheduling
    • Preemptive scheduling
  • Non-Preemptive scheduling
    • Has context switching but no time sharing
    • Once CPU has been allocated to a process, the process keeps the CPU until it releases CPU either by terminating or by switching to wait-state.
    • Starvation, as a process with long burst time may starve less burst time process.
    • Low CPU utilization
  • Preemptive scheduling
    • Has time sharing alongside of context switching
    • CPU is taken away from a process after time quantum expires along with terminating or switching to wait-state.
    • Less Starvation
    • High CPU utilization

Goals of CPU scheduling

  • Maximum CPU utilization
  • Minimum Turnaround time (TAT).
  • Min. Wait-time
  • Min. response time.
  • Max. throughput of system.

Terms

  • Throughput
    • No. of processes completed per unit time.
  • Arrival time (AT)
    • Time when process is arrived at the ready queue.
  • Burst time (BT)
    • The time required by the process for its execution.
  • Turnaround time (TAT)
    • Time taken from first time process enters ready state till it terminates.
    • TAT = CT - AT or TAT = BT + WT
  • Wait time (WT)
    • Time process spends waiting for CPU.
    • WT = TAT – BT
  • Response time
    • Time duration between process getting into ready queue and process getting CPU for the first time.
  • Completion Time (CT)
    • Time when the process gets terminated.

CPU Scheduling Algorithms

  • Who –> Short term scheduler
  • Where –> Ready to Running
  • When –> when the process moves from
    • Run
      • Run –> Termination (process completes, take new)
      • Run –> Wait (on I/O)
      • Run –> Ready (on Quant-time)
    • New –> Ready
      • When high priority is created
    • Wait –> Ready
      • When high priority goes to Ready
  • Convoy Effect
    • It is a situation where many processes, who need to use a resource for a short time, are blocked by one process holding that resource for a long time.
  • Aging
    • Aging is a technique of gradually increasing the priority of processes that wait in the system for a long time.

First Come First Serve (FCFS)

  • Simplest scheduling algorithm that schedules according to arrival times of processes.
  • Criteria
    • Arrival Time(AT)
  • Mode
    • Non-preemptive
  • Cons
    • High WT and Response time
    • High Convoy effect

Shortest Job First (SJF)

  • Process with least BT will be dispatched to CPU first.
  • Criteria
    • Burst Time(BT)
  • Mode
    • Non-preemptive
  • Preemptive SJF
    • Shortest Remaining Time First (SRTF)
  • Pros
    • Min Avg WT and TAT
      • Best among all scheduling algorithms
    • Max throughput
  • Cons
    • Estimation for BT(impossible) for each process in ready queue beforehand,
    • May suffer from convoy effect
    • Process starvation might happen if process with small BT is repeatly arriving and larger BT process is wating forever
  • Estimation for BT
    • Static
      • Process size
      • Process type
    • Dynamic
      • Simple averaging
      • Exponential averaging

Shortest Remaining Time First (SRTF)

  • It is preemptive version of SJF Pros
    • No convey effect

Longest Job First(LJF)

  • Process having longest BT gets scheduled first
  • Preemptive LJF
    • Longest Remaining Time First (SRTF)
  • Criteria
    • Burst Time(BT)
  • Mode
    • Non-premptive

Longest Remaining Time First (SRTF)

  • It is preemptive version of LJF

Round Robin

  • Round Robin is a CPU scheduling algorithm where each process is cyclically assigned a fixed time slot
  • It is type of preemptive version of FCFS
  • It’s one of the most widely used methods in CPU scheduling
  • Criteria
    • AT + time quantum(TQ)
  • Pros
    • Easy to implement
    • No convoy effect
  • Cons
    • Move overhead, if context-switching is high(TQ is small)

Highest Response ratio next(HRRN)

  • HRRN not only favours shorter jobs but also limits the WT of longer jobs
  • Criteria
    • Response ratio(RR) = (W + BT)/BT
      • W: wating time for a process so far
      • BT: Burst time of a procees
  • Mode
    • Non preemptive

Priority Based scheduling

  • Priority is assigned to a process when it is created
  • Criteria
    • AT + Priority
  • Mode
    • Preemptive and Non preemptive
  • Pros
    • Less complex
  • Cons
    • Indefinite wating or Extreme starvation
      • If newly arrived process has high priority then process with low priority will be wating forever
  • Types
    • Static priority
      • No Aging concept
    • Dynamic priority
      • Has Aging concept
  • Extreme starvation can be solved by Aging
    • i.e increase priority based on AT

Multilevel Queue Scheduling (MLQ)

  • Ready queue is divided into multiple queues depending upon priority
    • System process(SP) queue –> CPU process
    • Interactive process(IP) queue –> Foreground process
    • Batch process(BP) queue –> Background process
  • Priority: SP > IP > BP
    • i.e Only after completion SP, IP is executed and then BP
  • Each queue has its own scheduling algorithm
    • E.g: SP -> RR, IP -> RR & BP -> FCFS
  • Inter-queue movement not allowed
  • Cons
    • Low priority process may suffer Starvation Multilevel Queue Scheduling

Multilevel Feedback Queue (MLFQ) Scheduling

  • MLFQ CPU Scheduling is like MLQ Scheduling but in this process can move between the queues.
  • Inter-queue movement is allowed
  • It is more flexible
  • It is the most complex algorithm
  • Can be configured to match a specific system design requirement
  • The parameters of the multilevel feedback queue scheduler are as follows:
    • Scheduling algorithm for every queue
    • No of queues
    • Method to demoted to a lower-priority queue
    • Method to upgraded to a higher-priority queue –> Aging
    • Method to to determine in which queue the process will be pushed