CPU Scheduling Algorithms PDF

 CPU scheduling is a process used by the operating system to decide which task or program gets to use the CPU at a particular time. Since many programs can run at the same time, the OS needs to manage the CPU’s time so that every program gets a proper chance to run. The purpose of CPU Scheduli...

 CPU scheduling is a process used by the operating system to decide which task or program gets to use the CPU at a particular time. Since many programs can run at the same time, the OS needs to manage the CPU’s time so that every program gets a proper chance to run. The purpose of CPU Scheduling is to make the system more efficient and faster. The main function of CPU scheduling is to ensure that whenever the CPU remains idle, the OS has at least selected one of the processes available in the ready-to-use line. In Multiprogramming, if the long-term scheduler selects multiple I/O binding processes then most of the time, the CPU remains idle. The function of an effective program is to improve resource utilization. Arrival Time: The time at which the process arrives in the ready queue. Completion Time: The time at which the process completes its execution. Burst Time: Time required by a process for CPU execution. Turn Around Time: Time Difference between completion time and arrival time. Turn Around Time = Completion Time – Arrival Time Waiting Time(W.T): Time Difference between turn around time and burst time. Waiting Time = Turn Around Time – Burst Time There are mainly two types of scheduling methods: Preemptive Scheduling: Preemptive scheduling is used when a process switches from running state to ready state or from the waiting state to the ready state. Non-Preemptive Scheduling: Non-Preemptive scheduling is used when a process terminates , or when a process switches from running state to waiting state. FCFS is considered to be the simplest of all operating system scheduling algorithms. First come first serve scheduling algorithm states that the process that requests the CPU first is allocated the CPU first and is implemented by using FIFO queue. Advantages of FCFS Easy to implement First come, first serve method Disadvantages of FCFS FCFS suffers from Convoy effect. The average waiting time is much higher than the other algorithms. FCFS is very simple and easy to implement and hence not much efficient. Shortest job first (SJF) is a scheduling process that selects the waiting process with the smallest execution time to execute next. This scheduling method may or may not be preemptive. Significantly reduces the average waiting time for other processes waiting to be executed. The full form of SJF is Shortest Job First. Advantages of SJF As SJF reduces the average waiting time thus, it is better than the first come first serve scheduling algorithm. SJF is generally used for long term scheduling Disadvantages of SJF One of the demerit SJF has is starvation. Many times it becomes complicated to predict the length of the upcoming CPU request Longest Job First(LJF) scheduling process is just opposite of shortest job first (SJF), as the name suggests this algorithm is based upon the fact that the process with the largest burst time is processed first. Longest Job First is non-preemptive in nature. Advantages of LJF No other task can schedule until the longest job or process executes completely. All the jobs or processes finish at the same time approximately. Disadvantages of LJF Generally, the LJF algorithm gives a very high average waiting time and average turn-around time for a given set of processes. This may lead to convoy effect. Highest Response Ratio Next is a non-preemptive CPU Scheduling algorithm, and it is considered as one of the most optimal scheduling algorithms. The name itself states that we need to find the response ratio of all available processes and select the one with the highest Response Ratio. A process once selected will run till completion.  HRRN is considered as the modification of Shortest Job First to reduce the problem of starvation. In comparison with SJF, during the HRRN scheduling algorithm, the CPU is allotted to the next process which has the highest response ratio and not to the process having less burst time. Response Ratio = (W + S)/S Here, W is the waiting time of the process so far and S is the Burst time of the process.