Efficient Round Robin Scheduling Algorithm with Dynamic Time

I.J. Education and Management Engineering, 2015, 2, 10-19

Published Online June 2015 in MECS (afb467dba76e58fafbb00314)

DOI: 10.5815/ijeme.2015.02.02

Available online at afb467dba76e58fafbb00314/ijeme

Efficient Round Robin Scheduling Algorithm with Dynamic Time

Slice

Lipika Datta a

a Computer Science and Engineering Department, College of Engineering and Management Kolaghat, K.T.P.P.

Township, Purba Medinipur, W.B., PIN: 721171, India

Abstract

Round Robin (RR) scheduling algorithm is the widely used scheduling algorithm in multitasking. It ensures fairness and starvation free execution of processes. Choosing the time quantum in RR algorithm is very crucial as small time slice results in large number of context switches and large time quantum increases the response time. To overcome these problems of RR scheduling, instead of static time slice dynamic time slice can be used to get optimal performance. The objective of this paper is to modify RR algorithm by adjusting time slices of different rounds depending on the remaining CPU bursts of currently running processes and considering their waiting times un til that round in respect of the other processes’ waiting times. Experimental analysis reveals that the proposed algorithm produces better average turnaround time, average waiting time and fewer number of context switches than existing algorithms.

Index Terms: Operating System, Scheduling, Round Robin Algorithm, Dynamic Time Slice, Context switch, Turnaround time, Average Waiting time.

? 2015 Published by MECS Publisher. Selection and/or peer review under responsibility of the Research Association of Modern Education and Computer Science.

1.Introduction

Modern operating systems support multitasking environment in which processes run in a concurrent manner. In a single-processor system, only one process can run in the CPU at a time. Others processes in the ready queue must wait until the CPU becomes free. The operating system must decide through the scheduler the order of execution of the processes in ready state. The objective of multiprogramming is to have some process running at all times to maximize CPU utilization. Scheduling is a fundamental operating-system function. Almost all computer resources are scheduled before using. The CPU is, of course, one of the primary computer resources. Thus, its scheduling is central to operating-system design. CPU scheduling determines which processes run when there are multiple run-able processes. CPU scheduling is important because it can have a * Corresponding author.

E-mail address: lipika.datta@cemk.ac.in

Efficient Round Robin Scheduling Algorithm with Dynamic Time Slice 11 big effect on resource utilization and the overall performance of the system. In general we want to optimize the behaviour of the system.

The goals of scheduling may be categorized as user based scheduling goals and system based scheduling goals [1]. User based goals are the criteria that benefit the user. Some User-based scheduling goals are:

?Turnaround Time: The time elapsed between the submission of a job and its termination is called the turnaround time.

t r = wt + x

where t r is turnaround time of a process

wt is waiting time of the process in the ready queue.

x is the execution time of the process.

The scheduling algorithm should be designed such that turnaround time is minimized.

?Waiting Time: The time spent by the process in the ready queue is the waiting time. The scheduling algorithm should be designed such that waiting time is less.

?Response Time: It is the time interval between the time of submission of a process and the first response given by the process to the user. The scheduling algorithm should be designed such that the response time is within an acceptable range.

?Predictability: The algorithm should take care that a process does not take too long in processing as compared to the predictable behaviour of the process.

?Deadlines: The scheduling algorithm should be designed such that real-time processes will execute within their deadlines.

Some system-based scheduling goals are:

?Throughput: Throughput is the number of processes completed in a unit time. The scheduling algorithm should be designed in such a way that throughput in a system is maximized.

?CPU Utilization: It is the percentage of time that the CPU is busy in executing a process. The fundamental goal of scheduling is to keep the processor busy all the time.

?Fairness: All processes in the system should be treated in the same way unless there is some preference or priority for a specific process. In that case also processes with lower priority should not be ignored to avoid starvation.

?Context Switch: Context switching is the procedure of storing the state of an active process and restoring the state of another process for the CPU when it has to start executing the later process. Context switch is total overhead to the system and leads to wastage of CPU time. The scheduling algorithm should be designed such that the context switch is minimized.

So we can conclude that a good scheduling algorithm for real time and time sharing system must possess following characteristics:

?Minimum context switches.

?Maximum CPU utilization.

?Maximum throughput.

?Minimum turnaround time.

?Minimum waiting time.

?Minimum response time.

In this paper a new version of Round Robin scheduling algorithm is introduced which calculates the time slice of each pass of the RR scheduling algorithm considering the remaining CPU burst times of the currently

12Efficient Round Robin Scheduling Algorithm with Dynamic Time Slice

executing processes. In each pass, the precedence factor for each process is also calculated. Precedence fac …… 此处隐藏：17352字，全部文档内容请下载后查看。喜欢就下载吧 ……