Priority Based Round-Robin CPU Scheduling Algorithm with Case Study(Part-9)
Objective
The main objective of this paper is to develop a new approach for round robin CPU scheduling algorithm which improves the performance of CPU in real time operating system. The proposed Priority based Round-Robin CPU Scheduling algorithm is based on the integration of round-robin and priority scheduling algorithm. It retains the advantage of round robin in reducing starvation and also integrates the advantage of priority scheduling. The proposed algorithm also implements the concept of aging by assigning new priorities to the processes. Existing round robin CPU scheduling algorithm cannot be implemented in real time operating system due to their high context switch rates, large waiting time, large response time, large turnaround time and less throughput. The proposed algorithm improves all the drawbacks of round robin C P U scheduling algorithm. The paper also presents the comparative analysis of proposed algorithm with existing round robin scheduling algorithm on the basis of varying time quantum, average waiting time, average turnaround time and number of context switches.
What is Scheduling?
Scheduling is the process by which processes are given access to system resources. The need for a scheduling algorithm arises from the requirement of fast computer systems to perform multitasking (execute more than one process at a time) and multiplexing (transmit multiple flows simultaneously).
Objectives of Scheduling?
- Maximize throughput: A scheduling algorithm should be capable of servicing the maximum number of processes per unit of time.
- Avoid indefinite blocking or starvation: A process should not wait for unbounded time before or while process service.
- Minimize overhead: Overhead causes wastage of resources. But when we use system resources effectively, then overall system performance improves greatly.
A system can accomplish these goals in several ways. The scheduler can prevent indefinite blocking of processes through the concept of aging. The scheduler can increase throughput by favouring processes whose requests can be satisfied quickly, or whose completion cause other processes to run.
Criterias for scheduling
Different CPU algorithms uses different criterias which are as follows:
Context switch: A context switch is process of storing and restoring context (state) of a preempted process, so that execution can be resumed from same point at a later time. Context switching is usually computationally intensive, lead to wastage of time and memory, which in turn increases the overhead of scheduler, so the design of operating system is to optimize only these switches.
Throughput: Throughput is defined as number of processes completed per unit time. Throughput i s slow in round robin scheduling implementation. Context switching and throughput are inversely proportional to each other.
CPU Utilization: This is a measure of how much busy the CPU is. Usually, the goal is to maximize the CPU utilization.
Turnaround Time: The time interval from the time of submission of a process to the time of completion is the turnaround time.Total turnaround time is the sum of the periods spent waiting to get into memory, waiting time in the ready queue, execution time on the CPU and doing I/O.
Waiting Time: Waiting time is the total time a process has been waiting in ready queue.
Response Time: response time is the time from the submission of a request until the first response is produced that means time when the task is submitted until the first response is received. So the response time should be low for best scheduling.
Round-Robin Scheduling Algorithm
- The scheduler maintains a queue of ready processes and a list of blocked and swapped out processes.
- The Process Control Block of newly created process is added to end of ready queue. The Process Control Block of terminating process is removed from the scheduling data structures.
- The scheduler always selects the Process Control Block from the head of the ready queue. This is a disadvantage since all processes are basically given the same priority. Round robin also favors the process with short CPU burst and penalizes long ones.
- When a running process finishes its time slice, it is moved to end of ready queue. A time slice is an amount of time that each process spends on the processor per iteration of the Round Robin algorithm. All processes are executed in a first come first serve manner but are preempted after a time slice. The process will either finish in the time slice given or the process will be returned to the tail of the ready queue and return to the processor at a later time.
Disadvantages of Round Robin Algorithm
- Larger waiting time and Response time
- Context Switches
- Low throughput
With these observations it is found that the existing simple round robin architecture is not suitable for real time systems. So, its drawbacks are eliminated in the modified version of round robin described in the next section.
Priority Based Scheduling Algorithm
The operating system assigns a fixed priority to every process, and the scheduler arranges the processes in the ready queue in order of their priority. Lower priority processes get interrupted by incoming higher priority processes.
Overhead is not minimal, nor is it significant in this case. Waiting time and response time depend on the priority of the process. Higher priority processes have smaller waiting and response times. Deadlines can be easily met by giving higher priority to the earlier deadline processes.
Disadvantage: Starvation of lower priority processes is possible if large no of higher priority processes keep arriving continuously
Proposed algorithm
Allocate CPU to every process in round robin fashion, according to the given priority, for given time quantum (say k units) only for one time.
After completion of first step following steps are performed:
- Processors are arranged in increasing order or their remaining CPU burst time in the ready queue. New priorities are assigned according to the remaining CPU bursts of processes; the process with shortest remaining CPU burst is assigned with highest priority
- The processes are executed according to the new priorities based on the remaining CPU bursts, and each process gets the control of the CPU until they finished their execution.
Case Study
Time quantum is 5ms
According to Traditional Round-Robin algorithm:
Simple Round Robin does not use priority and five processes has been scheduled using simple Round Robin architecture. The time slice of five milliseconds has been used. In round robin algorithm no process is allocated CPU for more than one time slice in a row. If the CPU process exceeds one time slice, the concern process will be preempted and put into the ready queue. The process is preempted after the first time quantum and the CPU is given to the next process which is in the ready queue (process B), similarly schedules all the process and completes the first cycle. In the second cycle same method is used to schedule the processes. The process time slicing in simple Round Robin architecture is shown in Gantt chart.
Total context switches = 13
Average waiting time = 32.200001 ms, and Average Turnaround time = 45.8 ms
According to proposed algorithm:
It consists of the following two rounds —
- Process with the highest priority is executed first for the time equal to given time quantum i.e. 5 ms. The sequence of execution for above case is:
2. This round includes the changing of the process’s priorities according to the remaining CPU Burst Time. The process with least remaining CPU Burst Time is assigned highest priority. The new assigned priorities are as follows:
Gantt chart:
Total no of context switches = 8
Average waiting time = 26.200001 ms
Average Turnaround time = 38.8 ms
Comparison of Results and Discussion
The performance of two algorithms can be compared by considering the number of context switches, average waiting time and average turnaround time. Fig.4 shows the comparison of number of context switches performed in simple round robin and priority based round robin algorithm and can be plotted in MATLAB 7.0. It shows that the proposed algorithm performs better over simple round robin for varying time quantum. We see that priority based round robin has less number of context switches in comparison to simple round robin for same value of time quantum.
Fig.5 shows the comparison of average waiting time in simple round robin and priority based round robin algorithm and can be plotted in MATLAB 7.0. It shows that the proposed algorithm has less average waiting time over simple round robin for varying time quantum.
Fig.6 shows the comparison of average turnaround time in simple round robin and priority based round robin algorithm and can be plotted in MATLAB 7.0. It shows that the proposed algorithm has less average turnaround time over simple round robin for varying time quantum.
Conclusion
We have successfully compared both the algorithm i.e. simple round robin and the proposed one that the proposed one is more efficient because it has less average waiting time, average turnaround time and number of context switches as compared to simple round robin, in turn reducing the operating system overhead and hence dispatch latency. Also, it reduces the problem of starvation as the processes with less remaining CPU burst time are assigned with the higher priorities and are executed first in the second round of algorithm. Performance of time sharing systems can be improved with the proposed algorithm and can also be modified to enhance the performance of real time system.
