Scheduling

• What is Scheduling?  

  • Deciding which tasks to process, for how long, and in what order is achieved through scheduling algorithms 
  • A CPU is responsible for processing tasks as fast as possible 
  • Different algorithms are used to prioritise and process tasks that need CPU time 
  • The algorithms have different uses, benefits and drawbacks. 
• Scheduling categories 

  • Preemptive: allocates the CPU for time-limited slots 
  • Non-preemptive: allocates the CPU to tasks for unlimited time slots 
• Preemptive Scheduling 

  • Allocates the CPU for a specific time quantum to a process 
  • Allows interruption of processes currently being handled 
  • It can result in low-priority processes being neglected if high-priority processes arrive frequently 
  • Example algorithms include Round Robin and Shortest Remaining Time First  
• Non-Preemptive Scheduling 

  • Once the CPU is allocated to a process, the process holds it until it completes its burst time or switches to a 'waiting' state 
  • A process cannot be interrupted unless it completes or its burst time is reached 
  • If a process with a long burst time is running, shorter processes will be neglected 
  • Example algorithms include First Come First Serve and Shortest Job First 
• Scheduling Algorithms:

  • Round Robin
  • First-Come-First-Served (FCFS) 
  • Multi-Level Feedback Queue (MLFQ) 
  • Shortest job first (SJF) 
  • Shortest remaining time first (SRTF) 
• Round robin (RR) 

  • RR is a pre-emptive algorithm, equally distributing processor time amongst all processes 
  • Each process is given a time quantum to execute 
  • Processes that are ready to be worked on get queued 
  • If a process hasn’t been completed by the end of its time quantum, it will be moved to the back of the queue 

  
• First-Come-First-Served (FCFS) 

  • FCFS is non-preemptive, prioritising processes that arrive at the queue first 
  • The process currently being worked on will block all other processes until it is complete 
  • All new tasks join the back of the queue 

  
• Multi-Level Feedback Queue (MLFQ) 

  • MLFQ is a pre-emptive priority algorithm where shorter and more critical tasks are processed first 
  • Multiple queues are used so that tasks of equal size are grouped together 
  • All processes will join the highest priority queue but will trickle down to lower priority queues if they exceed the time quantum

  
• Shortest job first (SJF) 

  • SJF is non-preemptive, where all processes are continuously sorted by burst time from shortest to longest 
  • When new processes arrive on the queue, they are prioritised based on their burst time in the next cycle 
  • Shorter jobs are placed at the front of the priority queue 
  • Longer jobs have lower priority, so they are placed at the back 

  
• Shortest remaining time first (SRTF) 

  • SRTF is a preemptive version of SJF, where processes with the shortest remaining time are higher priority 
  • Time quantum is set, and if a task doesn’t complete in time, it will be re-queued for further processing 
  • Before the next cycle starts, all processes are inspected and ordered by the shortest remaining time to complete

  
• Shortest remaining time image

  
• Comparison of Scheduling Algorithms