Scheduling Algorithms - aryanjoshi0823/5143-Operating-System GitHub Wiki

CPU Scheduling Algorithms

1. Shortest Job Next

Description

This algorithm schedules the process with the shortest execution time first, reducing waiting and turnaround time. Processes are sorted by burst time in ascending order.

  • Processes are sorted by burst time.
  • Shorter processes execute first, freeing the CPU sooner for others.

Algorithmic Steps

  1. Collect the burst times for all processes.
  2. Sort the processes in ascending order of burst time.
  3. Select the process with the shortest burst time from the ready queue.
  4. Assign the CPU to the process and execute it until completion.
  5. Remove the process from the queue after execution.
  6. Repeat steps 3–5 for all remaining processes.

Example

  • The first 2 processes execute as they come, but then the 5th process gets to go since it’s the shortest among all others.
  • The turnaround time and waiting time is calculated. It’s visible that as an improvement over FCFS, we get reduced average waiting time as well as reduced average turnaround time.
  • This algorithm is especially useful in cases where there are multiple incoming processes and their burst time is known in advance.

2. Shortest Remaining Time First (SRTF)

Description

This is the preemptive version of SJF. The process with the shortest remaining burst time is executed, but it can be preempted by a newly arrived process with a shorter burst time.

Algorithmic Steps

  1. Maintain a ready queue with all available processes.
  2. Select the process with the shortest remaining burst time from the ready queue.
  3. Assign the CPU to the selected process.
  4. If a new process arrives with a shorter remaining burst time than the running process, preempt the current process.
  5. Update the remaining burst time for the preempted process and reinsert it into the queue.
  6. Continue execution of the new process until:
    • Its remaining burst time becomes zero, or
    • Another process with a shorter burst time arrives.
  7. Repeat steps 2–6 until all processes are completed.

Example

  • Here, the first process starts first and then the second process executes for 1 unit of time. It is then preempted by the arrival of the third process that has a lower service time. This goes on until the ready queue is empty and all processes are done executing.
  • A process begins execution but is interrupted if another process with shorter burst time arrives.
  • This method balances execution efficiency but may cause frequent context switches.

3. Priority-Based Scheduling

Description

Processes are executed based on priority, with higher-priority processes executed first. If two processes have the same priority, they are executed in FCFS order.

Algorithmic Steps

  1. Assign a priority to each process.
  2. Sort the ready queue by priority in descending order.
  3. Select the process with the highest priority.
  4. Assign the CPU to the selected process and execute it until:
    • Completion (non-preemptive), or
    • A higher-priority process arrives (preemptive).
  5. Remove the process from the queue after execution.
  6. Repeat steps 3–5 for all remaining processes.

Example

  • Here, different priorities are assigned to the incoming processes. The lower the number, the higher the priority. The 1st process to be executed is the second one, since it has higher priority than the first process. Then the fourth process gets its turn. This is known as Priority Scheduling. The calculated times may not be the lowest but it helps to prioritise important processes over others.
  • Processes are assigned priorities.
  • Lower-priority processes may face delays.

4. Round Robin Scheduling

Description

A preemptive scheduling algorithm where each process gets a fixed time slice (quantum) for execution. After the time slice, the next process in the queue executes. This continues in a cyclic manner until all processes are complete.

Algorithmic Steps

  1. Maintain a ready queue with all available processes.
  2. Define a fixed time quantum (e.g., 5 ms).
  3. Select the first process in the queue.
  4. Assign the CPU to the process and execute it for the duration of the time quantum or until completion.
  5. If the process is not completed within the quantum, preempt it and move it to the end of the queue.
  6. If the process is completed, remove it from the queue.
  7. Repeat steps 3–6 until the queue is empty.

Example

  • Let’s take a quantum time of 4 units. The first process will execute and get completed. After a gap of 1 unit, the second process executes for 4 units. Then the third one executes since it has also arrived in the ready queue. After 4 units, the fourth process executes. This process keeps going until all processes are done.
  • Each process executes for a quantum time.
  • Context switching occurs between processes.

5. Multi-Level Queue Scheduling

Description

Processes are divided into multiple queues based on criteria like priority or process type (e.g., system, interactive, batch). Each queue uses a different scheduling algorithm.

Algorithmic Steps

  1. Divide processes into multiple queues based on predefined criteria (e.g., system, interactive, batch).
  2. Assign a scheduling algorithm to each queue (e.g., FCFS for system tasks, Round Robin for interactive tasks).
  3. Set a priority for each queue (e.g., system > interactive > batch).
  4. Schedule processes as follows:
    • Execute processes in the highest-priority queue until it is empty.
    • Move to the next lower-priority queue and repeat.
  5. Apply the scheduling algorithm of the respective queue when executing its processes.
  6. Repeat until all processes in all queues are completed.

Example

  • System processes use FCFS.
  • Interactive processes use Round Robin.

6. Multi-Level Feedback Queue Scheduling

Description

This is an enhancement of the Multi-Level Queue Scheduling algorithm. Processes can move between queues based on their behavior. The algorithm adjusts the priority of a process depending on its CPU bursts and how long it waits.

Algorithmic Steps

  1. Create multiple queues with different priority levels.
  2. Define rules for moving processes between queues based on their behavior:
    • Promote processes waiting too long in lower-priority queues to avoid starvation.
    • Demote processes exceeding their CPU burst time in higher-priority queues.
  3. Start with the highest-priority queue:
    • Use a scheduling algorithm (e.g., Round Robin) to select and execute processes.
  4. Move to the next lower-priority queue only when higher-priority queues are empty.
  5. Continuously monitor and adjust the position of processes in the queues based on their execution and waiting times.
  6. Repeat until all processes are completed.

Example

  • Processes are initially placed in the highest priority queue and may be moved to lower-priority queues if they use too much CPU time.
  • Processes that wait too long can be promoted to a higher-priority queue.

7. Completely Fair Scheduler (CFS)

Description

CFS is a modern scheduling algorithm used in Linux. It aims to allocate CPU time fairly by ensuring that each process gets a fair share of the CPU. It does this by maintaining a virtual runtime (vruntime) for each process, which is the time that the process has been running. The process with the least virtual runtime is scheduled next.

Algorithmic Steps

  1. Initialize vruntime for Tasks:

    • Assign each task a vruntime based on its priority.
    • New tasks start with a vruntime slightly below the current minimum.

  2. Task Selection:

    • Organize all tasks in a red-black tree sorted by their vruntime.
    • Pick the task with the smallest vruntime (root of the tree).

  3. Execute the Task:

    • Run the task for a time slice determined by system granularity.
    • Adjust the task’s vruntime by the formula: 
      vruntime += elapsed time * (weight of highest-priority task / weight of current task)

  4. Update and Rebalance Tree:

    • After the time slice expires or the task voluntarily yields, update its vruntime.
    • Reinsert the task into the red-black tree at its new vruntime position.

  5. Handle New Tasks:

    • Insert new tasks into the red-black tree with a vruntime slightly less than the current minimum vruntime.
    • This ensures they are scheduled promptly.

  6. Preemptions:

    • If a new task has a smaller vruntime than the currently running task, preempt the running task and switch to the new one.

  7. Repeat:

    • Continuously repeat the above steps to ensure fair CPU distribution.

Example

  • Processes are executed in proportion to their weight (priority).
  • The process with the lowest vruntime is chosen for execution next.