Today Operating System can run multiple processes. But we know that only one process can be executed at the same time. Then to arrange and control the numerous processes in the system and utilize the CPU efficiently, some scheduling algorithm used by CPU.
CPU Scheduling Algorithm primarily used in multiprogramming operating system. To execute a process in the simple system, a process required Input-Output devices, resources and CPU time. If the process is dealing with I/O devices, the CPU will sit idle. To overcome this problem and save time, OS manage the system in this way that if one process is busy with I/O devices, then another process will use CPU for execution of their process. So that management of time will achieve in a right way.
CPU Scheduler: There is many processes in the ready queue to execute their process, scheduler select one of them for execution by CPU. A process should be a proper contrast to I/O bound and CPU bound. I/O required processes require more time for I/O than computation.CPU Bound process requires more time computation.
If all process is CPU bounded than I/O waiting for queues always empty and if all process is I/O delineated than CPU will get free.
We’ll be covering the following topics in this tutorial:
The scheduler has Three Categories
Long Term Scheduler : There are lots of processes in systems that are ready to execute. To execute a process, a process should be in the ready queue. The long-term scheduler selects the job from job pool and loads into ready line. It controls the degree of multiprogramming. It is also known as JOB Scheduler because it manages the jobs.
Short Term Scheduler : When a process becomes a part of the ready queue, now they required CPU for execution.Short term Scheduler select the process from the line and Assign CPU for performance. It is also known as CPU Scheduler because it manages the CPU utilization.
Mid Term Scheduler : Mid-term scheduler removes those processes from main memory and places them in secondary memories, which are not active for some time. Primarily Scheduler is used for swap out or swap in.
Scheduling algorithm can be categorized in two ways
Preemptive Scheduling: If CPU has been allocated to a process; the process will switch to running state to ready state after entering into a new process.
Non-Preemption : A running process cannot be interrupted or released CPU after entering a new process into ready queue.
To understand these scheduling algorithms, let us discuss some terms.
CPU Utilization: CPU utilization refers to use the CPU for maximum time. So that it will not remain free.
Throughput : Throughput is the measure of completing the number of processes per unit time.
Turnaround Time: Time interval from submission of a process to completion of a process. Turnaround time is the sum of periods spent waiting to get into time, waiting time in ready queue, I/O processes or execution time.
Turnaround time = Completion time – Arrival Time
Waiting Time : Waiting time is a sum of time when a process waits for CPU in the ready queue. It may be in continue slot or maybe a non-continue slot.
Waiting time for Process = Completion time – Arrival time – Execution time
Response Time : Time is taken by CPU to response the process.
CPU Burst: The time required by Process for execution.
For example, the below example using RR scheduling, where all processes arrived at time 0.
Process CPU Burst
P1 3
P2 4
P3 2
In above example, we have taken time quantum equal to 1 millisecond. After completion of time quantum, the process preempted, and the new process gets CPU.
Gantt Chart Shown the result as below
Response time for process P1=0, P2=1 ms, P3=2ms
Turnaround time for process P1=7 ms, P2=10, P3=6
Waiting time for P2=9-0-4=5
Preemptive Scheduling
Types of Scheduling Algorithms
1) First Come First Served Scheduling : In this Algorithm, Process that request CPU first, CPU is allocated first to that process .i.e. the algorithm is known as first come, first served. It based on FIFO (First in First Out) queue data structure. When a process entered in the ready queue, its Process Control Block (PCB) is added to end of the Queue. When CPU gets free after a process execution, a new process from the head of the queue is removed and enters in running state.
Let us discuss an example, some process p1, p2, p3, and p4 arrived at time 0, with the CPU burst.
Process CPU Burst
P1 20
P2 4
P3 6
P4 4
Gantt Chart Shown the result as below
Waiting time : Waiting time for process P1=0, P2=20, P3=24 and P4=30. Average Waiting time = (0+20+24+30)/4=18.4.
Example2 . If we Change the execution order of processes, like P4, P3, P2 and P1 then Gantt chart shown the result.
Waiting time : Waiting time for process P1=14, P2=10, P3=4, and P4=0.
Now Average Waiting Time = (0+4+10+14)/4=7
FCFS Scheduling algorithm suffered from Convoy effect. This effect resulted in lower CPU utilization and more waiting time.
In the list of processes, if one significant process gets CPU first, then all small process are waiting for getting the CPU.As a result, average waiting time is more in Example1.But If we talk about Example 2, Average waiting time is less.
FCFS is a non-preemptive algorithm. Once CPU has been allocated to a process, the process keeps the CPU until process itself terminate or any I/O request.
2) Shortest–Job–First Scheduling : SJF is a preemptive and Non-Preemptive algorithm. It based on length of latter’s next CPU burst. If a process acquired CPU and execution is going on, a new process with small CPU burst entered. Then CPU is preempted from current process and will give to further process. If two processes have the same length next CPU burst, FCFS scheduling is used to break the tie. Shortest Next CPUburst is also an appropriate term for SJF algorithm because scheduler examines the length of next CPU burst continuously.
Process CPU Burst
P1 20
P2 4
P3 6
P4 4
In above example, two processes P2, P4 have the same length. Now to break their tie FCFS algorithm is being used by system.P2 will process first and P4 follow it.
Gantt Chart Shown the result as below
Waiting time : Waiting time for process P1=14, P2=0, P3=8 and P4=4. Average Waiting time = (14+0+8+4)/4 = 6.5.
SJF scheduling algorithm is optimal because it gives average waiting time for a set of processes. If FCFS algorithm solves above example then average waiting time will be 18.4.
In SJF, shortest length run first which decrease the waiting time for small CPU burst process but increase the waiting time of lengthy processes, thus average waiting time decrease. SJF algorithm used in long-term scheduling. We can’t determine the length of next CPU burst, i.e., why it not used in short-term CPU scheduling.
Because of next CPU burst, SJF may be either preemptive or non-preemptive. If a new process arrives in the ready queue with greater CPU burst length, then non–preemptive SJF algorithm allow currently process to continue their execution till the termination. If the new process has shorter CPU burst, then preemptive SJF scheduling algorithm preempt the now process and assign the CPU to new process.Preemptive SJF scheduling also is known as Shortest Remaining Time first Scheduling.
Preemptive Scheduling Algorithm example:
Process CPU Burst (millisecond) Arrival Time
P1 10 0
P2 4 2
P3 6 4
P4 2 5
Gantt Chart Shown the result as below
In above example, Process P1 is running after 2 ms P2 enter in the ready queue with CPU Burst length 4.Now P1 is preempted, P2 gets CPU. In mid between of execution P3 and P4 get to enter with CPU burst 6,2.But P2 is not preempted, because of small burst. Don’t think that P4 process has small CPU burst 2, because till p4 entered into ready queue P2 has only one length CPU burst remain. Now p4, p3, and P1 get executed.
3) Priority Scheduling : SJF is a simple priority algorithm, where we are not considering the smallest next CPU burst, scheduler consider the priority of processes. The priority assigned to each process and CPU allocated to highest priority process. Equal priority processes scheduled in FCFS order.
Priority can be discussed regarding Lower and higher priority.Numbers denote it.We can use 0 for lower priority as well as more top priority.There is not a hard and fast rule to assign numbers to preferences.
Now in this example, we are using low numbers to represent higher priority.
Process CPU Burst Priority
P1 10 4
P2 4 1
P3 6 3
P4 5 2
Gantt Chart Shown the result as below
Average waiting time= (0+4+9+15) /4=28/4=7
Average time is 7 milliseconds.
We can compute the priority to a process by measuring internal or external factors. In Internal factors, we calculate priority by measuring time limits, memory requirements, number of open file and ratio of average I/o burst to average CPU burst of a process.In external factors, we consider the importance of process, amount of fund used for computer use and work type, etc.
Priority scheduling can be either preemptive or non-primitive. When a new process arrives in the ready queue with lower priority, then non–preemptive SJF algorithm allow currently process to continue their execution. If the new process has higher priority, then preemptive SJF scheduling algorithms preempt the currently process and assign the CPU to new process.
Priority Scheduling suffers from a starvation problem. The starvation problem leads to indefinite blocking of a process due to low priority. Every time higher priority process acquires CPU, and Low priority process is still waiting in the waiting queue. The aging technique gives us a solution to overcome this starvation problem in this technique; we increased the priority of process that was waiting in the system for a long time.
4) Round Robin Scheduling : Round Robin Scheduling algorithm designed for time-sharing systems. It is similar to FCFS scheduling but adding preemption to switch the processes after a small unit of time. A small unit of time is called a time quantum. A time quantum might be from 10 to 100 millisecond.
How RR algorithm works: Now Ready queue as a FIFO queue. The new process will add to the tail of the ready queue and process is removed from the head of queue.CPU select a process from ready queue, set a timer. After completion of time quantum, the process will be preempted doesn’t matter it is completed or not. IF the process not finished it will add in the tail of the queue and CPU select new process. In this way, the process is going on.
Ready Queue treated as a circular queue.
Process CPU Burst
P1 3
P2 4
P3 2
In above example, we have taken time quantum equal to 1 millisecond. After completion of time quantum, the process preempted, and the new process gets CPU.
Gantt Chart Shown the result as below
If time quantum is very large than RR scheduling algorithm treat as FCFS and if time quantum is small than RR called processor sharing.Processor sharing show to each process that they have their own processor.
The central concept is time switching in RR scheduling. If the context switch time is 10 percent of the time quantum then about 10 percent time will be spent in context switching.
5) Multilevel Queue Scheduling : Multilevel Queue Scheduling based on response–time requirements. Some process required a quick response by the processor; some processes can wait. Processes can be classifieds -Foreground process and background process. Based on memory size, priority and process type ready queue is assigned to processes. Separate queues used for foreground and background processes. Both processes are scheduled by the different scheduling algorithm. Foreground process used RR algorithm, and background process used FCFS algorithm. Lets us discuss an example of Multilevel Queue Scheduling with five queues having a different priority level.
1. System Processes
2. Interactive Processes
3. Interactive Editing processes
4. Batch Processes
5. Student Processes
Each queue has a different level of priority. If an interactive editing process entered in ready queue and Student process was running. Then student process preempted and interactive editing process first execute.
Dinesh Thakur holds an B.C.A, MCDBA, MCSD certifications. Dinesh authors the hugely popular