Я создаю симулятор дискретных событий, использующий методы Java и OO для моделирования некоторых планировщиков.
Я борюсь с генерацией новых событий ProcessArrival. Мой алгоритм выглядит так:
initialize ending condition to false
initialize system variables - create instances, etc.
initialize clock to zero
create and schedule an initial event - a ProcessArrival
while we have not processed n-events
set clock to next event time (by getting it from the Head of the EventQueue)
remove an event from EventQueue to process
if event is an arrival
create a new process and add it to scheduler's process ready queue
if scheduler is FCFS
we know completion time in advance, schedule a CompletionEvent
before we end the loop, create a new event - an arrival, with an arrival time = systemClock + a random exponential number.
Это не работает - если я не добавляю systemClock со случайной величиной (которая следует за экспоненциальным распределением), то часы иногда возвращаются назад, потому что время прибытия меньше, чем время часов. Если я добавлю его, все будет происходить последовательно, но у меня никогда не будет времени ожидания - процессы всегда приходят после завершения других процессов.
Я совершенно не понимаю, как это должно работать, и буду признателен за любые разъяснения! Когда я должен генерировать новое событие ProcessArrival, если не в конце цикла? Каким должно быть время начала процесса и как я могу избежать скачков часов назад во времени, если я генерирую события по одному? Было сказано не генерировать все события заранее.
Вот мой класс симулятора полностью:
public class Simulator {
public static void main(String[] args) {
if (args.length == 0 || args[0].toLowerCase().equals("help")) {
printProgramInstructions();
} else {
// initialize ending condition to false
boolean endingCondition = false;
// initialize system state variables
final int algorithmType = Integer.parseInt(args[0]);
final int lambda = Integer.parseInt(args[1]); // average rate of arrival
final float avgServiceTime = Float.parseFloat(args[2]);
final float quantumForRR = Float.parseFloat(args[3]);
// initialize simulation clock to 0
Clock simulationClock = new Clock();
simulationClock.setSimulationTime(0f);
System.out.println("System time at start is: " + simulationClock.getSimulationTime());
// schedule an initial event - create Event and add to EventQueue
Event initialEvent = new Event(EventType.ProcessArrival,simulationClock.getSimulationTime() + genexp(lambda));
EventQueue eventQueue = new EventQueue();
eventQueue.insertEvent(initialEvent);
// create the scheduling algorithm and the CPU to handle processes
SchedulingAlgorithm schedulingAlgorithm = createSchedulingAlgorithm(algorithmType);
CPU simulationCPU = new CPU();
int numProcessesHandled = 0;
// while we have not processed 10,000 Processes to completion,
// keep going and handle events in the EventQueue as needed
while (!endingCondition) {
// 1) Set Clock to EventTime
simulationClock.setSimulationTime(eventQueue.getSystemTimeFromHead());
System.out.println(">>> System time is now at: " + eventQueue.getSystemTimeFromHead());
// 3) Do/process next event and remove from EventQueue
Event eventToProcess = eventQueue.returnAndRemoveHeadEvent();
EventType eventToProcessType = eventToProcess.getEventType();
/* If event is:
* 1) an arrival: create a process and add it to the scheduler's queue
* 2) a completion: update the intermediate numbers needed for statistics
* have scheduler start executing next process in ReadyQueue if available
* and schedule completion event in the future if FCFS or RR because we know
* the completion times. FCFS is start time + burst time. RR is start time + quantum.
*/
if (eventToProcessType == EventType.ProcessArrival) {
System.out.println("---WE HAVE AN ARRIVAL---");
// create the "arriving" process
Process p = new Process();
p.setArrivalTime(eventToProcess.getEventTime()); // processArrivalTime = eventTime
//System.out.println("---------------");
System.out.println("Process arrived at: " + p.getArrivalTime());
p.setBurstTime(genexp(1/avgServiceTime));
p.setRemainingCpuTime(p.getBurstTime());
System.out.println("Process burst time is: " + p.getBurstTime());
// add new process to scheduler's ready queue
schedulingAlgorithm.myQueue.insertProcess(p);
if(algorithmType == SchedulerType.FCFS.getSchedulerType()) {
// Give CPU a process from the ready queue and set busy = true
// since this is FCFS, an arriving process' completion time is known in "advance"
// so schedule a completion event
if(simulationCPU.isBusy()) {
continue;
} else {
//remove proces from ready queue, give it to CPU
simulationCPU.setMyProcess(schedulingAlgorithm.getNextProcessForCPU());
simulationCPU.setBusy(true);
p.setStartTime(simulationClock.getSimulationTime()); // start process time
p.setWaitingTime(p.getStartTime() - p.getArrivalTime());
Event knownCompletion = new Event(EventType.ProcessCompletion,
p.getStartTime() + p.getBurstTime());
eventQueue.insertEvent(knownCompletion);
System.out.println("Process completion will be: " + knownCompletion.getEventTime() + "; " +
"current time is: " + simulationClock.getSimulationTime());
}
System.out.println("Process start time: " + p.getStartTime());
System.out.println("Process waited for: " + p.getWaitingTime());
} // end FCFS arrival handling
//TODO: if SRTF, check process running on CPU against Ready Queue
//TODO: if queue has process w/ remainingCpuTime less than that of the running process, preempt
} // end if to handle Process Arrivals
else if (eventToProcessType == EventType.ProcessCompletion) {
System.out.println("---WE HAVE A COMPLETION---");
/* When an event completes, set its remainingCpuTime to zero
* increment numProcessesHandled counter.
* Also the CPU is free to work on another process, so we must give it one
*/
numProcessesHandled++;
if(algorithmType == SchedulerType.FCFS.getSchedulerType()) {
simulationCPU.getMyProcess().setRemainingCpuTime(0f); // process is done
System.out.println("Completing process' remaining CPU time is: " + simulationCPU.getMyProcess().getRemainingCpuTime());
simulationCPU.setBusy(false);
simulationCPU.setMyProcess(schedulingAlgorithm.getNextProcessForCPU());
}
} // end else-if to handle Process Completions
else if (eventToProcessType == EventType.TimeSliceOccurrence) {
// TODO: logic to handle Round Robin Time slice occurrence event
}
// TODO: 3) Update statistics
// TODO: 4) Create new ProcessArrival Event
Event nextArrivalEvent = new Event(EventType.ProcessArrival,
simulationClock.getSimulationTime() + genexp(lambda));
eventQueue.insertEvent(nextArrivalEvent);
if (numProcessesHandled == 5) {
endingCondition = true;
System.out.println("We handled " + numProcessesHandled + " processes.");
}
} // end while
//TODO: 4) Generate and display statistical report
//TODO: generateStatistics()
//TODO: printStatistics()
} // end if-else args.length validation
} // end main
private static SchedulingAlgorithm createSchedulingAlgorithm(int algorithmType) {
SchedulingAlgorithm schedulingAlgorithm;//validate that algorithmType is in range (1,3)
if (algorithmType > 0 && algorithmType < 4) {
// create scheduler based on user defined type
// the scheduler will internally set its type and create its specific Process Ready Queue
if (algorithmType == SchedulerType.FCFS.getSchedulerType()) { // FCFS
schedulingAlgorithm = new FCFS();
}
else if (algorithmType == SchedulerType.SRTF.getSchedulerType()) { // SRTF
schedulingAlgorithm = new SRTF();
}
else { // RR
schedulingAlgorithm = new RR();
}
} else {
System.out.print("Please enter a valid value for the algorithm type, in range (1,3) inclusive.");
return null;
}
return schedulingAlgorithm;
}
/***
* This method prints usage instructions to the command line if the user does not specify any
* command line arguments or types the word 'help'
*/
private static void printProgramInstructions() {
System.out.println("Discrete event simulator for 3 scheduling algorithms. ");
System.out.println("Author: Borislav Sabotinov");
System.out.println("java -jar DiscreteEventSimulator.jar <scheduler_type> <lambda> <avg. svc time> <quantum>");
System.out.println("[scheduler_type] : value can be in the range (1,3) inclusive.");
System.out.println("\t1 - First Come First Served (FCFS) Scheduler");
System.out.println("\t2 - Shortest Remaining Time First (SRTF) Scheduler");
System.out.println("\t3 - Round Robin (RR) Scheduler - requires 4th argument defining a quantum value.");
System.out.println("[lambda] : average rate lambda that follows a Poisson process, to ensure exponential inter-arrival times.");
System.out.println("[avg. svc time] : the service time is chosen according to an exponential distribution with an average service time of this third argument");
System.out.println("[quantum] : optional argument only required for Round Robin (scheduler_type = 3). Defines the length of the quantum time slice.");
} // end printProgramInstructions
private static float urand() {
Random rand = new Random();
float value = rand.nextFloat();
//value = (float) (Math.round(value * 100.0f)/100.0f);
return value;
} // end urand
private static float genexp(float lambda) {
float u, x;
x = 0f;
while (x == 0) {
u = urand();
x = (float) ((-1f/lambda) * log(u));
}
return x;
} // end genexp
} // end class