Scheduling Algorithms - TarisMajor/5143-OpSystems GitHub Wiki

cpu_scheduling_is_the_basis

Scheduling Algorithms

First-Come, First-Served (FCFS)

First-Come, First-Served (FCFS) is a non-preemptive CPU scheduling algorithm that schedules processes in the order they arrive in the ready queue. The first process to arrive is executed first, and subsequent processes are scheduled in the same order.

Shortest Job Next (SJN)

Shortest Job Next (SJN), also known as Shortest Job First (SJF), is a CPU scheduling algorithm where the process with the smallest execution time is selected to execute next. It minimizes waiting time but requires knowing the execution time of each process, which can be difficult in practice.

Priority Scheduling

Priority Scheduling assigns a priority to each process and executes the process with the highest priority first. If two processes have the same priority, other criteria like arrival time or FCFS may be used to break the tie.

Round Robin (RR)

Round Robin (RR) is a preemptive CPU scheduling algorithm where each process is assigned a fixed time slice or quantum. Once the time slice expires, the process is placed at the back of the ready queue, and the next process is scheduled.

Shortest Remaining Time (SRT)

Shortest Remaining Time (SRT) is a preemptive version of Shortest Job Next (SJN). The process with the smallest remaining execution time is executed next. If a new process arrives with a shorter remaining time, it preempts the current process.

Multi-Level Queue Scheduling

Multi-Level Queue Scheduling divides processes into different queues based on attributes like priority, process type (interactive or batch), or execution time. Each queue can use its own scheduling algorithm, and processes are scheduled based on their queue.

Multi-Level Feedback Queue Scheduling

Multi-Level Feedback Queue Scheduling is an enhancement to Multi-Level Queue Scheduling where processes can move between different queues based on their behavior. This allows the scheduler to dynamically adjust the priority of a process based on its CPU burst and I/O behavior.

Completely Fair Scheduler (CFS)

The Completely Fair Scheduler (CFS) is a CPU scheduling algorithm used in Linux systems. It aims to allocate CPU time fairly to all processes based on their weight, ensuring that each process receives a proportional amount of CPU time relative to its priority.

Sources:

  1. Operating System Concepts by Abraham Silberschatz, Peter B. Galvin, and Greg Gagne
  2. Modern Operating Systems by Andrew S. Tanenbaum and Herbert Bos
  3. Introduction to Operating Systems by H.M. Deitel, Paul J. Deitel, and David R. Choffnes
  4. Operating Systems: Design and Implementation by Andrew S. Tanenbaum
  5. ChatGPT