/* * Scheduler.java (Implements Short Term Scheduler) * * Written by : Nitin Motgi (nmotgi@cs.ucf.edu) * * This simulates the Real time Short Term Scheduler. The simulation * is completely based on moving the events on logical time scale. * The program moves on logical time scale and every increment in the * logical time unit, it checks the integrity of the whole system. * The check including Checking the Job Pool, Scheduler Queue, * All the dispatchers queue also. Basically during every tick all * the jobs in the system at looked at. The increments in this logical * clock basically represent 10 milliseconds. * * 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 : Scheduler.java, v1.0 2/02/2001. $ * * Revision History. * 1. Created Basic Method, $Id: v1.0.0 2/02/2001. * 2. Added Documentation, $Id: v1.0.1 2/02/2001. * 3. Added CreateJobPool(), $Id: v1.1.1 2/02/2001. * (Jobs are created based on the specs for the simulation. The * runs till all the jobs provided for the system have completed * execution.) * 4. Added CheckJobPool(), $Id: v2.0.0 2/03/2001. * (Every logical time, a check is made in the job pool to check * whether there are any jobs whose arrival time matches the * current time. If yes, then move the Job to Scheduler.) * 5. Added CheckSchedulerPool(), $Id: v3.0.0 2/04/2001. * (Moves Job from Scheduler to dispatcher, puts in the right * order in the dispatcher i.e FCFS within priorities.) * 6. Added Integrity Checks on $Id: v3.1.0 2/04/2001. * command line. * 7. Modified Documentation $Id: v3.1.1 2/04/2001. * 8. Final Variable Name Check, $Id: v3.1.2 2/06/2001. * 9. Final Documentation Check, $Id: v3.1.3 2/06/2001. * 10. Final Functionality Check, $Id: v3.1.4 2/06/2001. * */ /* Include some of library files.*/ import java.lang.*; import java.util.*; /* Start of Class.*/ public class Scheduler{ static Vector JobPool; /* All the Jobs Generated are stored here.*/ static Vector SchedulerQueue; /* Scheduler Jobs which are SJF with in priority levels.*/ /************************************************************************* * Is the Start of Scheduler, a multiprocessor environment Job Scheduling * simulation. */ public static void main(String[] szArgs){ int nNoOfProcessor; /* No of Processors in the System.*/ int nNoOfJobs; /* Number of Jobs that will be in the system.*/ int nArrivalTimeInMin; /* Uniform Distribution over this arrival time.*/ long lGLC; /* Global Logical Counter, basically represent the logical time for simulation.*/ /* Make the command line integrity Check.*/ if(szArgs.length < 3){ System.out.println("* ERROR : Invalid command line."); PrintError(); return; }/* End if.*/ /* Process command line.*/ nNoOfProcessor = Integer.parseInt(szArgs[0]); nNoOfJobs = Integer.parseInt(szArgs[1]); nArrivalTimeInMin = Integer.parseInt(szArgs[2]); /************** PERFORM INTEGRITY CHECK ON ENTERED DATA ****************/ if(nNoOfProcessor <= 0){ System.out.println("** ERROR : Number of processor cannot be less " + "than or equal to zero"); PrintError(); return; }/* End if.*/ if(nNoOfJobs <= 0){ System.out.println("** ERROR : Number of jobs cannot be less " + "than or equal to zero"); PrintError(); return; }/* End if.*/ if(nArrivalTimeInMin <= 0){ System.out.println("** ERROR : Arrival Time in minutes cannot be " + "less than or equal to zero"); PrintError(); return; }/* End if.*/ /******************************** END **********************************/ /* Stores the handle for all the processors in the system.*/ Dispatcher ProcessorList[] = new Dispatcher[nNoOfProcessor]; /* Create System required Job Pool and Scheduler Pool.*/ JobPool = new Vector(); SchedulerQueue = new Vector(); /* Create all the Jobs Needed and add it to the Job Pool which are moved into the system when their arrival time condition is meet.*/ CreateJobPool(nNoOfJobs,nArrivalTimeInMin); /* Create all the Dispatcher/Processor required for simulation. The ID's of Dispatcher will start from 1.*/ for(int nProCount=0; nProCount < nNoOfProcessor; nProCount++){ ProcessorList[nProCount] = new Dispatcher(nProCount+1); }/* End for.*/ /* Start the Global Logical Counter/Timer(GLC), the smallest unit of increment is 10 milli seconds. It's a long counter starts with 0. 1 indicates 00:00:00.01 i.e 10 milli seconds.*/ lGLC = 0; /* Till Dooms day i.e. till all the jobs are finished.*/ while(true){ CheckJobPool(lGLC,nNoOfJobs); /* Checks for Jobs in Job Pool.*/ CheckSchedulerPool(ProcessorList,nNoOfProcessor); int nCompCount = 0; /* Gives No Of Dispatcher Completed the Job.*/ int nJobCount = 0; /* Gives count of Number of Jobs completed.*/ /* Iterate through each processor and update the state of each processor. Upon return it will tell wether it has completed processing the jobs allocated to it.*/ for(int nLoop=0; nLoop < nNoOfProcessor; nLoop++){ if(ProcessorList[nLoop].UpdateDispatcher(lGLC)==false) nCompCount++; nJobCount += ProcessorList[nLoop].GetJobCompleteCount(); }/* End for.*/ /* When all dispatcher has completed working or all the Jobs have been processed then exit out of this loop.*/ if(nCompCount == nNoOfProcessor && nJobCount == nNoOfJobs){ System.out.println("All Jobs completed running."); DisplayStatistics(nNoOfProcessor, nNoOfJobs,lGLC,ProcessorList); break; }/* End if.*/ lGLC++; /* Increments by 10 milli seconds.*/ }/* End of Doom While.*/ }/* End of main.*/ /************************************************************************* * Creates the Job with arrival time based on the uniform distribution * over the arrival time. 50% of the jobs are estimated to take between * 1 to 10 seconds. 10% of the jobs take between 10 and 60 seconds. 30% * between 1 and 10 minutes. 10% of the jobs take between 10 minutes and * 3 hrs. * The priorities generated for the Job are Normal distribution centered * on 5 with standard deviation of 2. Highest priority being 1 and * lowest being 9. * The smallest unit of time is 10 milli seconds. */ static void CreateJobPool(int nNoOfJobs, int nArrivalTimeInMin){ long lArrivalTime = nArrivalTimeInMin * 60 * 100; /* Converted to smallest unit.*/ ProcessControlBlock PCB; /* Used to save temp PCB.*/ /* This generates a stream of pseudo-random numbers. It uses 48bit seed, which is modified using linear congrential formula.*/ Random ArrivalTime = new Random(); Random JobType = new Random(); Random Priority = new Random(); Random ExecTime = new Random(); float rArrivalTime; /* Stores the arrival time generated.*/ float rJobType; /* Stores to which the current generated Job belongs to.*/ double rPriority; /* Stores Priority of the Job.*/ float rExecTime; /* Stores the Execution time of the Job.*/ long lExecTime=0; /* Long time.*/ long lNewArrivalTime=0; /* Long Arrival Time.*/ int nPriority=0; /* Integer Value.*/ /* Till all the Jobs are created keep loooooooping.*/ for(int nJobGen=0; nJobGen < nNoOfJobs; nJobGen++){ /* They have uniform distribution.*/ rArrivalTime = ArrivalTime.nextFloat(); rJobType = JobType.nextFloat(); rExecTime = ExecTime.nextFloat(); /* Follows Standard Normal Distribution with mean @ 0 and standard deviation as 1.*/ nPriority = (int)Priority.nextGaussian()*2+5; /* 50% of the Jobs have to be in range from 1 sec to 9 seconds.*/ if(rJobType <= 0.50){ /* Generate Execution time in this slab.*/ lExecTime = (long)(rExecTime * 800 + 100); /* because 10 milli second is smallest unit of time.*/ } /* For 10% Jobs i.e from 50% to 60% they take execution time from 10 to 59 seconds.*/ if(rJobType > 0.50 && rJobType <= 0.60){ lExecTime = (long)(rExecTime * 5800 + 1000); }/* End if.*/ /* For 30% Jobs i.e from 60% to 90% have excution time from 1 min to 9 min 59 sec (60 seconds - 5999 seconds).*/ if(rJobType > 0.60 && rJobType <= 0.90){ lExecTime = (long)(rExecTime * 593900 + 6000); }/* End if.*/ /* For 10% Jobs from 90% to 100% the exection slab is from 10 min to 3 hr (600 seconds - 10800 seconds).*/ if(rJobType > 0.90 && rJobType <= 1.0){ lExecTime = (long)(rExecTime * 1020000 + 60000); }/* End if.*/ /* Make this uniform over the arrival time entered on the command line by the user.*/ lNewArrivalTime = (long)(rArrivalTime * lArrivalTime); /* We have to move the median to 5 and standard deviation to 2 of the standard normal distribution.*/ if(nPriority < 1) nPriority = 1; else if(nPriority > 9) nPriority = 9; PCB = new ProcessControlBlock(nJobGen+1,lExecTime,nPriority,lNewArrivalTime); JobPool.addElement(PCB); }/* End for.*/ }/* CreateJobPool.*/ /************************************************************************ * This function checks whether there are jobs at this instance of time * If so, then they will be moved into the Scheduler and printing the * message for it's arrival into the system. * * This moves into the Job Pool and picks up the PCB whoes arrival time * matches the Global Logical Counter value. Once, the job is selected * it is removed from the Job Pool. */ static void CheckJobPool(long lGLC,int nNoOfJobs){ ProcessControlBlock PCB; /* Each Process in the Job Pool.*/ TimeFormat Time = new TimeFormat(); for(int nJobPool=0; nJobPool < JobPool.size(); nJobPool++){ PCB = (ProcessControlBlock)JobPool.elementAt(nJobPool); if(PCB.GetArrivalTime() == lGLC){ /* If the timings match, then move it to the Scheduler Queue and print the message.*/ AddToScheduler(PCB,lGLC); PCB.thisJob.nJobID = nNoOfJobs - JobPool.size() +1; System.out.println("Job " + PCB.thisJob.nJobID + " arrived at time " + Time.formatTime(PCB.GetArrivalTime()) + " Priority: " + PCB.GetPriority() + ", Estimated Run Time: " + Time.formatTime(PCB.GetCurrentExecTime())); /* Remove this Job from the Job Pool.*/ JobPool.removeElementAt(nJobPool); break; }/* End if.*/ }/* End for.*/ }/* End of CheckJobPool.*/ /*********************************************************************** * This function will add the Job to Scheduler based on Shortest Job * First within the Priority Levels. This basically functions as a * short term scheduler. */ static void AddToScheduler(ProcessControlBlock PCB,long lGLC){ int nNoOfSchedulerJobs = SchedulerQueue.size(); int nPriority = PCB.GetPriority(); long lExecTime = PCB.GetCurrentExecTime(); int nQueueIndex=0; /* Fit the Job exactly in its position and once fitted, change the state of the Job.*/ for(nQueueIndex=0; nQueueIndex < nNoOfSchedulerJobs; nQueueIndex++){ ProcessControlBlock pcbTmp = (ProcessControlBlock)SchedulerQueue.elementAt(nQueueIndex); if((nPriority == pcbTmp.GetPriority() && lExecTime < pcbTmp.GetCurrentExecTime()) || nPriority < pcbTmp.GetPriority()) break; }/* End of for.*/ /* At this position add the Job in the Queue.*/ PCB.SetState(PCB.STATE_READY); PCB.SetCST(lGLC); PCB.SetEOT(-1); SchedulerQueue.insertElementAt(PCB,nQueueIndex); }/* End of AddToScheduler.*/ /*********************************************************************** * This function basically picks up the Job from the Scheduler Queue * and makes a check on the dispatchers/processor in the system whosever * is having the minimum wait time for the execution of the job. The Job * in hand is then transfered to the dispatcher with miniumum waiting * time. * * Picks only one Job at a time and puts it in the Dispatcher which * can process it faster. */ static void CheckSchedulerPool(Dispatcher ProcessorList[], int nNoOfProcessor){ int nSchJob = SchedulerQueue.size(); /* Get number of Jobs in the Scheduler.*/ if(nSchJob == 0) return; /* When there are no Jobs in the Scheduler.*/ ProcessControlBlock PCB = (ProcessControlBlock)SchedulerQueue.elementAt(0); /* Pick the first one always.*/ int nProIndex = 0; /* Points to the Processor that has minimum wait time in the system.*/ long lMinWaitTime = 99999999; /* Intialised to the larget wait time.*/ for(int nProCount=0; nProCount < nNoOfProcessor; nProCount++){ if(ProcessorList[nProCount].GiveWaitTime() < lMinWaitTime){ lMinWaitTime = ProcessorList[nProCount].GiveWaitTime(); nProIndex = nProCount; }/* End if.*/ }/* End for.*/ /* This is the Processor with minimum wait time.*/ ProcessorList[nProIndex].AddJobToQueue(PCB); /* Remove the Selected Job from the Queue.*/ SchedulerQueue.removeElementAt(0); }/* End of CheckSchedulerPool.*/ /*********************************************************************** * Displays statics of the System. The specs for this statistics is * as given on the website for project 1. */ static void DisplayStatistics(int nNoOfProcessor, int nNoOfJobs, long lGLC, Dispatcher[] DispatcherList){ long lBusyTime = 0; long lTotalFirstWaitTime=0; PriorityInfo PrTemp= new PriorityInfo(); PriorityInfo PrInfo[] = new PriorityInfo[10]; TimeFormat Time = new TimeFormat(); /* Initialise the Array.*/ for(int nIndex=0;nIndex<10;nIndex++) PrInfo[nIndex] = new PriorityInfo(); for(int nIndex = 0; nIndex < nNoOfProcessor; nIndex++){ lBusyTime = (lGLC - DispatcherList[nIndex].GetIdealTime()); lTotalFirstWaitTime+=DispatcherList[nIndex].GetTotalFirstWaitTime(); if(lBusyTime < 0 ) lBusyTime = 0; System.out.println("Processor " + DispatcherList[nIndex].nDispID + ": " + Time.formatPercent( (float)((lBusyTime/(float)lGLC)*100)) + "% busy"); for(int jIndex = 1; jIndex <= 9; jIndex++){ PrTemp = DispatcherList[nIndex].GetPriorityInformation(jIndex); PrInfo[jIndex].nJobCount +=PrTemp.nJobCount; PrInfo[jIndex].lJobWaitTime+=PrTemp.lJobWaitTime; PrInfo[jIndex].lCPUTime+=PrTemp.lCPUTime; PrInfo[jIndex].rCPUUtil+=PrTemp.rCPUUtil; PrInfo[jIndex].rIOUtil+=PrTemp.rIOUtil; PrInfo[jIndex].rWaitUtil+=PrTemp.rWaitUtil; PrInfo[jIndex].lTotalTime+=PrTemp.lTotalTime; }/* End for.*/ }/* End for.*/ System.out.println("The average job waited an average of " + Time.formatTime(lTotalFirstWaitTime/nNoOfJobs) + " before being serviced."); double rCPUUtil = 0.0; double rIOUtil = 0.0; double rWaitUtil = 0.0; for(int nIndex = 1; nIndex <= 9; nIndex++){ System.out.println("Priority " + nIndex + " : The " + PrInfo[nIndex].nJobCount + " Jobs waited " + Time.formatTime(PrInfo[nIndex].lJobWaitTime)+ ", " + Time.formatPercent( ((PrInfo[nIndex].lCPUTime/(float)PrInfo[nIndex].lTotalTime)*100)) + "% CPU."); rCPUUtil+=PrInfo[nIndex].rCPUUtil; rIOUtil+=PrInfo[nIndex].rIOUtil; rWaitUtil+=PrInfo[nIndex].rWaitUtil; }/* End for.*/ rCPUUtil = (rCPUUtil/(float)nNoOfJobs); rIOUtil = (rIOUtil/(float)nNoOfJobs); rWaitUtil = (rWaitUtil/(float)nNoOfJobs); System.out.println("The average job spent " + Time.formatPercent(rCPUUtil) + "% CPU, " + Time.formatPercent(rIOUtil) + "% I/O, " + Time.formatPercent(rWaitUtil) + "% waiting."); }/* End of DisplayStatistics.*/ /************************************************************************* * Prints Error Message. */ static void PrintError(){ System.out.println("Usage : java Scheduler "+ " "); }/* End of PrintError.*/ }/* End of Scheduler.*/