/* * Dispatcher.java (Entity Per CPU. Works on FCFS within priority levels) * * Written by : Nitin Motgi (nmotgi@cs.ucf.edu) * * This file provides mechanism to manage jobs when they are queue to * run on the CPU. This simulates the state machine of the Jobs as they * move from Ready to Running, Running to Input-Output and from Input- * Output to Ready again. Finite State machine moves the Jobs back * forth from one state to another with just a state indicator. * The important functins used are ComputeIOBurst and ComputeCPUBurst. * * ASSUMPTION : No Overhead involved in switching the Job from one * state to the other. * * Portions copyright (c) 2001 to School of Electrical Engineering and * Computer science, UCF. * * Use and distribution of this source code are strictly governed by * terms and condition of the author. * * $Id : Dispatcher.java, v1.0 2/02/2001. $ * * Revision History. * 1. Created Basic Method, $Id: v1.0.0 02/02/2001. * 2. Added Documentation, $Id: v1.0.1 02/02/2001. * 3. Added Job addition capabilities $Id: v1.1.0 02/02/2001. * 4. State machine handlers added $Id: v2.0.0 02/04/2001. * 5. Documentation was modified $Id: v2.0.1 02/04/2001. * 6. UpdateDispatcher() Added, $Id: v2.1.1 02/04/2001. * 7. ComputeCPUBurst() Added, $Id: v2.2.1 02/05/2001. * 8. ComputeIOBurst() Added, $Id: v2.3.1 02/05/2001. * 9. Final Variable Name Check, $Id: v2.3.2 02/05/2001. * 10.Final Documentation Check, $Id: v2.3.3 02/05/2001. * 11.Final Functionality Check, $Id: v2.3.4 02/05/2001. * */ /* Include some of the library file(s).*/ import java.util.*; import java.lang.*; /* Start of Dispatcher Class.*/ public class Dispatcher{ Vector DispatcherQueue; /* Stores Job to be scheduled.*/ public int nDispID; /* Dispatcher ID.*/ int nNumberOfJobs; /* Keeps track of number of Jobs.*/ int nCompletedJobs; /* Keeps track of number of completed jobs.*/ long lWaitTime; /* This is the characteristics of the queue which is used by the Short-Term scheuler to place the jobs.*/ long lIdealTime; /* Keeps track of for how much time the Processor was ideal.*/ long lCPUBusyTime; /* This is for statistical data for what percentage of time was this processor busy as compared to processing of of jobs in all the processor.*/ int nCurrentRunningJob; /* This pointer points to the current executing job.*/ final int MAX_DISPATCHER_JOBS = 100; /************************************************************************** * Constructor. */ Dispatcher(int nDispID){ lWaitTime = 0; lIdealTime = 0; lCPUBusyTime = 0; nCurrentRunningJob = -1; /* Initially set to zero.*/ nNumberOfJobs = 0; nCompletedJobs = 0; this.nDispID = nDispID; DispatcherQueue = new Vector(); }/* End of Constructor.*/ /************************************************************************** * Returns no of jobs completed in the system. */ int GetJobCompleteCount(){ return nCompletedJobs; }/* End of GetJobCompleteCount.*/ /************************************************************************** * Returns Ideal Time of the Processor. */ long GetIdealTime(){ return lIdealTime; }/* End of GetIdealTime.*/ /************************************************************************** * Adding Job to the Queue of the dispatcher. This will return the status * indicating whether the Job was added or not by returning TRUE for job * added and FALSE for not added. The calling routine can make a decision * based on the return value of this. If the Job is not added, the state * of the dispatcher is not changed in any sense. But, when added a counter * indicating the Number of Jobs in the queue is incremented and wait time * is adjusted. */ boolean AddJobToQueue(ProcessControlBlock PCB){ /* Check if the current job addition to the dispatcher will exceed the dispatcher queue limit.*/ if(nNumberOfJobs+1 > MAX_DISPATCHER_JOBS){ /* Return FALSE indicating failure to add the Job.*/ return false; } /* Can add the job to the queue.*/ AddJobFCFS(PCB); /* Increment count.*/ nNumberOfJobs++; return true; }/* End of AddJobToQueue.*/ /************************************************************************* * Adds Job to the Queue, such that jobs are in FCFS within priority * levels. Once, the Job is placed in the queue, it will be removed * only when it is finished and then moved into the Finished Pool of * the dispatcher. */ void AddJobFCFS(ProcessControlBlock PCB){ long lNewJobArrivalTime = PCB.GetArrivalTime(); int nNewJobPriority = PCB.GetPriority(); int nIndex; ProcessControlBlock tempPCB; /* For all the Jobs in the Queue check this.*/ int nInsIndex=0; for(nIndex=0; nIndex < nNumberOfJobs; nIndex++){ tempPCB = (ProcessControlBlock)(DispatcherQueue.elementAt(nIndex)); if((nNewJobPriority == tempPCB.GetPriority() && lNewJobArrivalTime < tempPCB.GetArrivalTime())) break; /* This is the location where this Job has to be added.*/ }/* End For.*/ /* Insert New Job at the location pointed by nIndex.*/ DispatcherQueue.insertElementAt(PCB,nIndex); }/* End of AddJobFCFS.*/ /************************************************************************ * Compute Wait time of Jobs in the queue. It uses the interface provided * by PCB to retrieve this information. */ void ComputeWaitTime(){ ProcessControlBlock PCB; lWaitTime = 0; /* For all the Jobs in the Queue compute Wait times.*/ for(int nIndex=0; nIndex < nNumberOfJobs; nIndex++){ PCB = (ProcessControlBlock)DispatcherQueue.elementAt(nIndex); if(PCB.GetState() == PCB.STATE_IO || PCB.GetState() == PCB.STATE_READY || PCB.GetState() == PCB.STATE_CPU) lWaitTime+=PCB.GetCurrentExecTime(); }/* End of For.*/ }/* End of ComputeWaitTime.*/ /************************************************************************ * Returns the Wait time of the Dispatcher. */ long GiveWaitTime(){ ComputeWaitTime(); return lWaitTime; }/* End of GiveWaitTime.*/ /************************************************************************ * This function basically is the "HEART" of the dispatcher as, this * basically change the state of the jobs as when called during every * 100th of a second by the centralised controlled simulator. The * events in this are triggered by the logical time called "R Current * System Time" RCST. */ boolean UpdateDispatcher(long lRCST){ int nJobIndex; if(nNumberOfJobs == nCompletedJobs){ lIdealTime++; return false; } /* When there are no Jobs in the Queue, the nCurrentRunningJob is set to -1 and Number of Jobs in the queue is zero, we increment the ideal counter and exit.*/ if(nCurrentRunningJob == -1 && nNumberOfJobs == 0){ lIdealTime++; return true; }/* End if.*/ /* When nCurrentRunningJob is -1 and there are jobs in the queue, then we have to find a victim and put him to run on the CPU.*/ if(nCurrentRunningJob == -1 && nNumberOfJobs > 0){ nJobIndex = GetJobToRun(); /* Will give only those jobs which are in running state. Will also set nCurrentRunningJob.*/ if(nJobIndex != -1){ /* Start the Job Move the Job From Ready to Running.*/ ReadyToCPU(nJobIndex,lRCST); }else{ /* All Jobs in the CPU are in IO.*/ lIdealTime++; CheckIOToReady(lRCST); return true; }/* End if.*/ }/* End if.*/ /* Check if the Job is currently running on the CPU.*/ ProcessControlBlock PCB = (ProcessControlBlock)DispatcherQueue.elementAt(nCurrentRunningJob); if(PCB.GetCST() == lRCST){ nJobIndex = GetJobToRun(); if(nJobIndex != -1){ /* Move the Job from CPU to IO state.*/ CPUToIO(nCurrentRunningJob,lRCST); ReadyToCPU(nJobIndex,lRCST); }else{ CPUToIO(nCurrentRunningJob,lRCST); lIdealTime++; nCurrentRunningJob = -1; }/* End if.*/ } CheckIOToReady(lRCST); return true; }/* End of UpdateDispatcher.*/ /************************************************************************* * Checks whether are any jobs which can be moved into IO. */ void CheckIOToReady(long lRCST){ ProcessControlBlock PCB; /* Check all the Jobs other than current running.*/ for(int nJobIndex=0; nJobIndex < nNumberOfJobs; nJobIndex++){ PCB = (ProcessControlBlock)DispatcherQueue.elementAt(nJobIndex); if(PCB.GetState() == PCB.STATE_IO && lRCST == PCB.GetCST()){ IOToReady(nJobIndex,lRCST); }/* End if.*/ }/* End of For.*/ }/* End of CheckIOToReady.*/ /************************************************************************* * Move the Job State from Ready To CPU (i.e. Execution). Good Job which * was selected to run is passed as parameter to this funtion. Update * PCB Structure to reflect new changes. */ void ReadyToCPU(int nIndex,long lRCST){ ProcessControlBlock PCB = (ProcessControlBlock)DispatcherQueue.elementAt(nIndex); /* Compute the Wait time of the Job as it is moving from ready to to CPU.*/ long lWaitTime = lRCST - PCB.GetCST(); if(PCB.bDispFlag == false){ TimeFormat Time = new TimeFormat(); System.out.println("Job " + PCB.thisJob.nJobID + " commenced running on " + " processor " + nDispID + " at " + Time.formatTime(lRCST) + " wait time " + Time.formatTime(lWaitTime)); PCB.SetFirstWaitTime(lWaitTime); PCB.bDispFlag = true; } PCB.SetWaitTime(lWaitTime); /* generally computes the Burst whether it is CPU or I/O. it just computes the burst.*/ long lCPUBurst = ComputeCPUBurst(nIndex); /* Change state of Job to CPU.*/ PCB.SetState(PCB.STATE_CPU); PCB.SetCPUBurst(lCPUBurst); PCB.SetEOT(lCPUBurst); PCB.SetCurrentExecTime(lCPUBurst); PCB.SetCST(lRCST); /* Change the pointer to point to the current job as the running job in the system.*/ nCurrentRunningJob = nIndex; }/* End of ReadyToCPU.*/ /*********************************************************************** * Changes the state of the job from CPU to IO. The burst is computed * such that it will end with CPU burst. */ void CPUToIO(int nIndex, long lRCST){ if(nIndex == -1) return; ProcessControlBlock PCB = (ProcessControlBlock)DispatcherQueue.elementAt(nIndex); PCB.SetState(PCB.STATE_IO); long lIOBurst = ComputeIOBurst(nIndex); if(lIOBurst != 0){ PCB.SetIOBurst(lIOBurst); PCB.SetEOT(lIOBurst); PCB.SetCurrentExecTime(lIOBurst); PCB.SetCST(lRCST); }else{ long lTotal = PCB.GetTotalExecTime(); float rCPU = (float)((PCB.GetCPUBurst()/(float)lTotal)*100); float rIO = (float)((PCB.GetIOBurst()/(float)lTotal)*100); float rWait = (float)((PCB.GetWaitTime()/(float)lTotal)*100); TimeFormat Time = new TimeFormat(); System.out.println("Job " + PCB.thisJob.nJobID + " completed running at "+ Time.formatTime(lRCST) + ", actual run time " + Time.formatTime(PCB.GetTotalExecTime()) + ","+ Time.formatPercent(rCPU) +"% CPU, "+ Time.formatPercent(rIO) +"% I/O, "+ Time.formatPercent(rWait)+"% waiting."); PCB.SetState(PCB.STATE_COMP); nCompletedJobs++; }/* End if.*/ }/* End of CPUToIO.*/ /*********************************************************************** * Changes the state of the Job from IO to Ready. */ void IOToReady(int nIndex,long lRCST){ ProcessControlBlock PCB = (ProcessControlBlock)DispatcherQueue.elementAt(nIndex); //System.out.println("Job " + PCB.thisJob.nJobID +" IOToReady " + " current time :" // + lRCST); PCB.SetState(PCB.STATE_READY); PCB.SetEOT(-1); PCB.SetCST(lRCST); }/* End of IOToReady.*/ /*********************************************************************** * Gets the New Job to be run. It will select the Jobs with lowest * arrival time and with in priority levels. */ int GetJobToRun(){ ProcessControlBlock PCB; for(int nJobIndex=nNumberOfJobs-1; nJobIndex >=0; nJobIndex--){ PCB = (ProcessControlBlock)DispatcherQueue.elementAt(nJobIndex); if(PCB.GetState() == PCB.STATE_READY){ if(PCB.GetCurrentExecTime() > 0){ return nJobIndex; }/* End if.*/ }/* End if.*/ }/* End of For.*/ return -1; }/* End of GetJobToRun.*/ /*********************************************************************** * ComputeCPUBurst. */ long ComputeCPUBurst(int nIndex){ ProcessControlBlock PCB = (ProcessControlBlock)DispatcherQueue.elementAt(nIndex); double rCPUBurst; long lCPUBurst; rCPUBurst = java.lang.Math.random(); lCPUBurst = (long)((rCPUBurst * 3990) + 10); if(lCPUBurst > PCB.GetCurrentExecTime()) lCPUBurst = PCB.GetCurrentExecTime(); return lCPUBurst; }/* End of ComputeCPUBurst.*/ /*********************************************************************** * ComputeIOBurst. */ long ComputeIOBurst(int nIndex){ ProcessControlBlock PCB = (ProcessControlBlock)DispatcherQueue.elementAt(nIndex); double rIOBurst; long lIOBurst; rIOBurst = java.lang.Math.random(); lIOBurst = (long)((rIOBurst * 3990) + 10); if(lIOBurst > PCB.GetCurrentExecTime()-1) lIOBurst = PCB.GetCurrentExecTime()-1; if(lIOBurst == -1) lIOBurst = 0; return lIOBurst; }/* End of ComputeIOBurst.*/ /********************************************************************* * Get Total First Wait Time of the Job. */ long GetTotalFirstWaitTime(){ long lTotalFirstWaitTime=0; for(int nIndex=0; nIndex < nNumberOfJobs; nIndex++){ ProcessControlBlock PCB = (ProcessControlBlock)DispatcherQueue.elementAt(nIndex); lTotalFirstWaitTime+=PCB.GetFirstWaitTime(); }/* End for.*/ return lTotalFirstWaitTime; }/* End of GetTotalFirstWaitTime.*/ /******************************************************************** * Get Information of Priority Jobs in this dispatcher. */ PriorityInfo GetPriorityInformation(int nPriority){ int nPrJobCount=0; long lPrJobWaitTime=0; long lPrCPUTime=0; long lPrTotalTime=0; double rPrCPUUtil=0.0; double rPrIOUtil=0.0; double rPrWaitUtil=0.0; PriorityInfo PrInfo = new PriorityInfo(); for(int nIndex=0; nIndex < nNumberOfJobs; nIndex++){ ProcessControlBlock PCB = (ProcessControlBlock)DispatcherQueue.elementAt(nIndex); if(PCB.thisJob.nPriority == nPriority){ nPrJobCount++; lPrJobWaitTime+=PCB.GetWaitTime(); lPrCPUTime+=PCB.GetCPUBurst(); lPrTotalTime+=PCB.GetTotalExecTime(); rPrCPUUtil+=(PCB.GetCPUBurst()/(double)PCB.GetTotalExecTime()*100); rPrIOUtil+=(PCB.GetIOBurst()/(double)PCB.GetTotalExecTime()*100); rPrWaitUtil+=(PCB.GetWaitTime()/(double)PCB.GetTotalExecTime()*100); }/* End if.*/ }/* End for.*/ PrInfo.nJobCount = nPrJobCount; PrInfo.lJobWaitTime = lPrJobWaitTime; PrInfo.lCPUTime = lPrCPUTime; PrInfo.rCPUUtil = rPrCPUUtil; PrInfo.rIOUtil = rPrIOUtil; PrInfo.rWaitUtil = rPrWaitUtil; PrInfo.lTotalTime = lPrTotalTime; return PrInfo; }/* End GetPriorityInformation.*/ }/* End of Dispatcher.*/