Simulation Of Scheduling Algorithms

Simulation Of Scheduling Algorithms Abstract- In this term paper we have discuss simulation of scheduling algorithm. We have discuss various type of scheduling algorithm such as robin round, first comes first served, shortest job first, and etc. We also discuss its advantages and disadvantages. In this term paper we take some c programme based on this scheduling algorithm to understand properly. We also include some graphical representatiion of each scheduling. From which we can differentiate between each algorithm. Keywords- In this term paper we use some keyword Round Robin(RR), First Come First Serve (FCFS), Shortest Job First(SJF), Process Control Block (PCB), Shortest Time Remaining (SRT). INTRODUCTION Scheduling is a fundamental operating-system function. Whenever the CPU becomes idle, the operating system must select one of the processes in the ready queue to be executed. The selection process is carried out by the short-term scheduler. The scheduler selects from among the processes in memory that are ready to execute, and allocates the CPU to one of them. All processes in the ready queue are lined up waiting for a chance to run on the CPU. The records are generally the PCBs (Process Control Block) of the processes. Another important component involved in the CPU scheduling function is the dispatcher. The dispatcher is the module that gives control of the CPU to the processes selected by the short-term scheduler. This function involves: à ¢Ã¢â€š ¬Ã‚ ¢ Switching context à ¢Ã¢â€š ¬Ã‚ ¢ Jumping to the proper location in the user program to restart that program. Our goal is to simulate the process scheduling algorithms to get a more accurate evaluation on how choice of a particular scheduling algorithm can effect CPU utilization and how a scheduler decides when processors should be assigned, and to which processes. Different CPU scheduling algorithms have different properties and may favour one class of processes over another. We have programmed a model of the computer system and implemented scheduling algorithms using Software data structures which represent the major components of the system which we have discussed in this section. 2. PROPOSAL When system has a choice of processes to execute, it must have a strategy -called a Process Scheduling Policy-for deciding which process to run at a given time .A scheduling policy should attempt to satisfy certain performance criteria, such as maximizing: à ¢Ã¢â€š ¬Ã‚ ¢ Throughput à ¢Ã¢â€š ¬Ã‚ ¢ Latency à ¢Ã¢â€š ¬Ã‚ ¢ Preventing Indefinite postponement of Process à ¢Ã¢â€š ¬Ã‚ ¢ Maximizing Process Utilization It is the job of the scheduler or dispatcher to assign a processor to the selected process. In our project various Process Scheduling Algorithms that determine at runtime which process runs next .These algorithms decide when and for how long each process runs; they make choices about à ¢Ã¢â€š ¬Ã‚ ¢ Preemptibility à ¢Ã¢â€š ¬Ã‚ ¢ Priorities à ¢Ã¢â€š ¬Ã‚ ¢ Running time à ¢Ã¢â€š ¬Ã‚ ¢ Time-to-Completion à ¢Ã¢â€š ¬Ã‚ ¢ Fairness We will be simulating these Scheduling Algorithms and comparing them against various parameters mentioned above. BACKGROUND What is Process :-A process is the locus of control of a procedure in execution that is manifested by the existence of a data structure called Process Control Block. Each process has its own address space, which typically consists of Text region, Data region and Stack region. The Text region stores the code that the processor executes. The Data region stores the variables and dynamically allocated memory that the process uses during execution. The Stack region stores instructions and local variables for active procedure calls. The contents of the Stack grow as the process issues nested procedure calls and shrink as procedures return. 4.WHAT IS PROCESSOR SCHEDULING? -When a system as a choice of processes to execute, it must have a strategy for deciding which process to run at a given time. This strategy is known as Processor Scheduling Policy. Different process scheduling algorithms have different properties and may favor one class of processes over another. In choosing which algorithm to use in a particular situation, we compare the following characteristics to compare the algorithms. CPU Utilization -We want to keep the CPU as busy as possible. It ranges from 0 to 100%. In real systems it ranges from 40% to 90%. For the purpose of this simulation we have assumed that CPU utilization is 100%. Throughput -The work done by the CPU is directly proportional to the CPU utilization. The number of processes completed per unit time, called throughput, is the measure of work done by the CPU. Algorithms should try to maximize the throughput. Turnaround time- The time interval from submission of job to the completion of job is termed as the turnaround time. It includes waiting time of the process and the service time of the process. Waiting time -The amount of time process spent waiting in the ready queue is termed as Waiting time. Any algorithm does not affect the service time of the process but does affect the waiting time of the process. Waiting time should be kept to the minimum. Response time The time interval from the submission of the process to the ready queue until the process receives the first response is known as Response time. Response time should always be kept minimum. Besides the above features, a scheduling algorithm must also have the following properties: à ¢Ã¢â€š ¬Ã‚ ¢ Fairness à ¢Ã¢â€š ¬Ã‚ ¢ Predictability à ¢Ã¢â€š ¬Ã‚ ¢ Scalability 5. SIMULATION- In our simulation the ready queue has been programmed to serve the processes in the First in First out, Round Robin, Shortest Process first, Highest Response Ration Next and also Shortest Remaining time. The simulator has a variable representing a clock; as this variables value is increased, the simulator modifies the system state to reflect the activities of the devices, the processes, and the scheduler. Our system has a function called Process Ready which checks which processes are ready to enter the system depending on the current clock. Preemption is performed based on the current clock. If the next process in the ready queue should get the CPU the current process is pushed into the queue and the next process, based on how the priority of the processes is calculated in ready queue, is taken and given the CPU time. We call this in real systems as context switch .We will be providing this overhead a simple variable which we fill add to a process when it is preempted. The scheduler is an abstract class in which we have defined the basic components which are needed by the scheduler like ready queue .FIFO, RR, SPF, SRT and HRRN are the classes which extend this scheduler class and implement the ready queue based on specific scheduler. The data that we are using to drive the simulation is generated using a random-number generator. The generator is programmed to generate processes, CPU-burst times, Arrivals and Finish time. The process PCB in our simulation consists of following attributes: Process Id Process ServiceTime Process ArrivalTime Process FinishTime Process ResponseTime The same set of processes is feed into the scheduling algorithm to evaluate the algorithms effect on the processes and CPU. These are initialized for all the processes that we randomly generate .Once the process gets the CPU its service time gets updated and if the simulation performs a context switch which preempts the current running process and puts it at the back of the ready queue i.e. we save the PCB of the process. After this the first process in the ready queue is given the block .In the end the system outputs the Arrival Time, Service Time, Turn around Time, Waiting Time and Response Time for each process executed by the system. The output formats, the input and the Analysis using this simulation model are shown in the sections that follow: A simple Class Diagrame :- 6. SCHEDULING ALGORITHM A scheduling algorithm is the method by which threads, processes or data flows are given access to system resources (e.g. processor time, communications bandwidth). This is usually done to load balance a system effectively or achieve a target quality of service. The need for a scheduling algorithm arises from the requirement for most modern systems to perform multitasking (execute more than one process at a time) and multiplexing (transmit multiple flows simultaneously) Type of Scheduling algorithm Scheduling algorithm :- First Come First Serve (FCFS) Round Robin Shortest Job First Shortest Remaining Time Highest Response Ratio Next (HRRN) Fixed priority pre-emptive scheduling FIRST COME FIRST SERVE (FCFS) :- CPU scheduling deals with the problem of deciding which of the processes in the ready queue is to be allocated the CPU. There are many different CPU scheduling algorithms. By far the simplest CPU-scheduling algorithm is the first-come, first-served (FCFS) scheduling algorithm. With this scheme, the process that requests the CPU first is allocated the CPU first. The implementation of the FCFS policy is easily managed with a FIFO queue. When a process enters the ready queue, its PCB is linked onto the tail of the queue. When the CPU is free, it is allocated to the process at the head of the queue. The running process is then removed from the queue. The code for FCFS scheduling is simple to write and understand. The average waiting time under the FCFS policy, however, is often quite long. C- programming for this scheduling algorithm is given below. I only present the main part of the programme. /* Programme for FCFS*/ #include #include //Library for clearing the screen using namespace std; int cont, ctr; class FCFS{ //Class used for the simulation public: //public elements of the class void input(); void gantt(); protected: //protected elements of the class float wt, bt, arr, bt2; float awt; }; int main(){ //main function FCFS IT2B; cout cin>>ctr; if(ctr>=3ctr system(cls); IT2B.input(); //invocation }else{ cout cout cin>>cont; system(cls); main(); } return 0; } void FCFS::input() //input() function of class FCFS { wt=0; bt2=0; cout for(arr=1;arr cout>bt; cout bt2=bt+bt2; wt=bt2+wt; } awt=(wt-bt2)/ctr; cout cout cin>>cont; } /*void FCFS::gantt() { */ Limitations: In FCFS, average waiting time is quite longer. If we have a processor bound job (generally with longer service time) and other I/O bound jobs. And if, processor bound job is allocated the processor time, then it will hold the CPU. As a result, other I/O bound jobs will keep waiting in the ready queue and the I/O devices will remain idle. Like in the test cases we observed, process P3 despite having a very short service time had to wait for long till all the processes ahead of it ran to completion. Average Turn around Time: 12 Average Waiting Time: 7.2 Average Response Time: 7.2 6.2. ROUND ROBIN The round-robin (RR) scheduling algorithm is designed especially for time-sharing systems. It is similar to FCFS scheduling, but preemption is added to switch between processes. A small unit of time, called a time quantum or time slice, is defined. A time quantum is generally from 10 to 100 milliseconds. The ready queue is treated as a circular queue. The CPU scheduler goes around the ready queue, allocating the CPU to each process for a time interval of up to l time quantum. To implement RR scheduling, we keep the ready queue as a FIFO queue of processes. New processes are added to the tail of the ready queue. The CPU scheduler picks the first process from the ready queue, sets a timer to interrupt after l time quantum, and dispatches the process . C- programming for this scheduling algorithm is given below. I only present the main part of the programme. /* Programme for ROUND ROBIN*/ for(i=0;j { if(r[i]>0sp>=a[i]) { f=true; if(r[i] time=r[i]; else time=q; //schedule the process t[i]+=time,r[i]=time,order.push_back(i+1); if(r[i]==0) j++; for(k=0;k if(r[k]!=0k!=ia[k] if(!(a[k] w[k]+=sp+time-a[k],t[i]+=sp+timea[k]; else w[k]+=time,t[k]+=time; sp+=time; continue; } if(i==n-1) { if(!f) { int it; int diff=0; for(it=0;it if(sp { if(diff==0) diff=a[it]-sp; else if(diff>a[it]-sp) diff=a[it]sp; } sp+=diff; } f=false; } } OUTPUT:- Advantages:-Round Robin algorithm exhibits fairness. All the processes are treated equally and are given equal processor time. As compared to FCFS, the average waiting time is considerably reduced in Round Robin algorithm. Limitations: The performance of the system implementing Round Robin mainly depends upon the value of the quantum. If we set the quantum to very high value, then it will proceed as the FCFS. As a result the system performance will be sluggish. If we keep the quantum value low, more overhead will be produced because of frequent context switch .Round Robin with low quantum is generally suitable for the interactive system. However, to determine the optimal quantum time is a tedious task 6.3.SHORTEST JOB FIRST A different approach to CPU scheduling is the shortest-job-first (SJF) scheduling algorithm. This algorithm associates with each process the length of the processs next CPU burst. When the CPU is available, it is assigned to the process that has the smallest next CPU burst. If the next CPU bursts of two processes are the same, FCFS scheduling is used to break the tie. Note that a more appropriate term for this scheduling method would be the shortest-next-CPU-burst algorithm, because scheduling depends on the length of the next CPU burst of a process, rather than its total length. The SJF algorithm is a special case of the general priority scheduling algorithm. A priority is associated with each process, and the CPU is allocated to the process with the highest priority. Equal-priority processes are scheduled in FCFS order. An SJF algorithm is simply a priority algorithm where the priority (p) is the inverse of the (predicted) next CPU burst. The larger the CPU burst, the lower the pri ority, and vice versa. C- programming for this scheduling algorithm is given below. I only present the main part of the programme. /* Programme for SJF*/ #include #include #include void main() { char p[10][5],temp[5]; int tot=0,wt[10],pt[10],i,j,n,temp1; float avg=0; clrscr(); printf(enter no of processes:); scanf(%d,n); for(i=0;i { printf(enter process%d name:n,i+1); scanf(%s,p[i]); printf(enter process time); scanf(%d,pt[i]); } for(i=0;i { for(j=i+1;j { if(pt[i]>pt[j]) { temp1=pt[i]; pt[i]=pt[j]; pt[j]=temp1; strcpy(temp,p[i]); strcpy(p[i],p[j]); strcpy(p[j],temp); } } } wt[0]=0; for(i=1;i { wt[i]=wt[i-1]+et[i-1]; tot=tot+wt[i]; } avg=(float)tot/n; printf(p_namet P_timet w_timen); for(i=0;i printf(%st%dt%dn,p[i],et[i],wt[i]); printf(total waiting time=%dn avg waiting time=%f,tot,avg); getch(); } Output : Advantages: Shorter processes are given preference. If the ready queue contains Processor bound processes and some I/O bound processes, then the I/O bound will be given more preference. As a result the system throughput increases. Average waiting time of the processes decreases. Like in the test case, the process P3 waited for only 6 seconds compared to 10 seconds in RR and 16 seconds in FCFS. 6.4 .SHORTEST REMAINING TIME (SRT) This is the preemptive algorithm which acts on the principles of SPF. It gives preference to the processes with the smaller service time. If a process is using the process and in the mean time a new process arrives whose service time is less than the currently running, then it preempts the currently running process and gives processor control to the new process. This algorithm is no longer useful in todays operating systems. Advantages: It offers the minimum waiting time for the processes. Like the process P3, waited for 6 seconds before getting the processor time. Though this waiting time is equal to that in SPF. But being a preemptive algorithm, SRT scores over SPF by providing even lesser waiting time than the former. Average Turn around Time: 11 Average Waiting Time: 6.4 Average Response Time: 6 6.5 HIGHEST RESPONSE RATIO NEXT This algorithm corrects some of the weakness of the SPF. The SPF algorithm is biased towards the processes with short service time. This keeps the longer processes waiting in the ready queue for the longer time, despite of arriving in the ready queue before the short jobs. It is a non-preemptive scheduling algorithm in which the priority is the function of not only the service time but also of the time spent by the process waiting in the ready queue. Once the process obtains the control of the processor, it completes to completion. The priority is calculated by the formula Priority = (Waiting Time + Service Time)/Service Time In this algorithm too, short processes receive preference. But longer processes that have been waiting in the ready queue are also given the favorable treatment. 7.GRAPHICAL REPRESENTATION Turnaround Time Comparison Waiting time comparison Responce time comparison 8.CONCLUSION From the analysis of the algorithms, we have come up with the conclusion that RR has the best average response time and being the preemptive algorithm, it exhibits fairness. But however, performance of the RR algorithm depends heavily on the size of the quantum. On the one extreme is the time quantum is very large, RR algorithm is same as FCFS policy. But if the time quantum is fairly small, the RR will exhibit fairness but a considerable overhead gets added to the turnaround time due frequent context switch. This fact becomes clear from the RR average turnaround time reading is highest as compared to other algorithms. Hence we observed if majority of the processes are less then the time quantum, the RR will give better response time. Further, SPF has the least average turnaround time and average waiting time as compared to other algorithms. This shows that SPF is provably optimal, in that it gives the minimum average time in the set of processes by moving the short process before a long one. The waiting time of short process decreases more than the waiting time of the long process. Consequently the waiting time decreases. But this algorithm can only be used for systems which are interactive and thereby is biased to short processes and unfavorable to longer ones which may lead to indefinite postponement of longer processes. HRRN has approximately same average turnaround, waiting and response time. It overcomes the limitation of the SPF by giving favorable treatment to the processes waiting for a longer time, and thereby prevents indefinite postponement. SRT exhibits approximately same average response time, waiting time and turnaround time, and may seem to be an effective algorithm for interactive processes if the tasks performed before issuing I/O are short in duration. However, SRT determines priority based on the run time to completion, not the run time to I/O. Some interactive processes such as shell executes for the life time of the session, which would place the shell at the lowest priority level.