CIS 3130

CISC 3130
Data Structures
Applications — Queue

Radix Sort

Basic idea
- Have an array of queues (bins)-- one per possible digit
  - For decimal digits, there would be ten bins
  - The base is called the radix
- Extract rightmost digit of each number
  - 15 → 5, 1023 → 3, 90 → 0
- Place in corresponding bin
- Iterate through bins 0 to 9, placing numbers back into array
- Repeat with next digit, until we've processed all digits
- Resulting array is sorted
'Card sorter' sort

Why This Works

Placing the values in the bins corresponding to their last digit, does a gross ordering of the numbers by that digit
- i.e., numbers with a lower last digit come before those with a higher one (e.g. 251 will be in an earlier bin/queue than 5)
- When the numbers are then recollected from the bins and placed back into the array, the numbers with lower last digits will thus be placed before numbers with higher last digits
This order will persist when the next digit (the one to the left) is examined; and thus after two iterations, numbers with a lower value of their last two digits will be recollected into the array before those with a hight two digit value
Continuing in this vein means that when the last digit (i.e., the leftmost digit) is processed, the numbers will be recollected into the array by order of their digits

radixSort(a[])
	create an array of queues (bins), one per possible digit
	current digit position = rightmost position (1's position)
	while (there are more digit positions to process)
		for (i = 0 to last element)
			add a[i]'s digit in current digit position to corresponding bin
		
		(move the elements from the queues back into the array)
		for (i = 0 to the last bin)
			remove the elements from the bin and add them to the next element in the array 
			
		move current digit position one position over
	}

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Random;

public class RadixSorter {
	public static void main(String [] args) {
		int howMany = DEFAULT_HOW_MANY;;
		if (args.length == 1)
			howMany = Integer.parseInt(args[0]);
		
		Random random = new Random(SEED);

		int [] arr = new int[howMany];

		for (int i = 0; i < howMany; i++)
			arr[i] = random.nextInt(MAX_NUM);

		System.out.println("Original array:");
		for (int e : arr)
			System.out.print(e + "  ");
		System.out.println();
		System.out.println();
		
		sort(arr);

		System.out.println("Sorted array:");
		for (int e : arr)
			System.out.print(e + "  ");
		System.out.println();
	}

	public static void sort(int [] arr) {
		ArrayList<ArrayDeque<Integer>> radixQueues = new ArrayList<>();
		for (int i = 0; i < RADIX; i++)
			radixQueues.add(new ArrayDeque<>());
		
		int max = arr[0];
		for (int i = 1; i < arr.length; i++)
			if (arr[i] > max) max = arr[i];
		
		int divisor = 1;

		while (divisor <= max) {
			for (int e : arr) {
				int digit = (e / divisor) % RADIX;
				radixQueues.get(digit).add(e);
			}

			if (DEBUG) {
				System.out.println("After pass with divisor = " + divisor);
				for (ArrayDeque<Integer> q : radixQueues)
					System.out.println(q);
				System.out.println();
			}

			int index = 0;
			for (int i = 0; i < RADIX; i++)
				while (!radixQueues.get(i).isEmpty()) 
					arr[index++] = radixQueues.get(i).remove();
		
			if (DEBUG) {
				for (int e : arr)
					System.out.print(e + "  ");
				System.out.println();
				System.out.println();
			}
			divisor *= 10;
		}
	}

	static final int 
		SEED = 12345,
		RADIX = 10,
		MAX_NUM = 1000,
		DEFAULT_HOW_MANY = 20;

	static final boolean
		DEBUG = true;
}

Original array:
251  80  241  828  55  84  375  802  501  389  517  942  390  806  12  384  787  303  532  175  

After pass with divisor = 1
[80, 390]
[251, 241, 501]
[802, 942, 12, 532]
[303]
[84, 384]
[55, 375, 175]
[806]
[517, 787]
[828]
[389]

80  390  251  241  501  802  942  12  532  303  84  384  55  375  175  806  517  787  828  389  

After pass with divisor = 10
[501, 802, 303, 806]
[12, 517]
[828]
[532]
[241, 942]
[251, 55]
[]
[375, 175]
[80, 84, 384, 787, 389]
[390]

501  802  303  806  12  517  828  532  241  942  251  55  375  175  80  84  384  787  389  390  

After pass with divisor = 100
[12, 55, 80, 84]
[175]
[241, 251]
[303, 375, 384, 389, 390]
[]
[501, 517, 532]
[]
[787]
[802, 806, 828]
[942]

12  55  80  84  175  241  251  303  375  384  389  390  501  517  532  787  802  806  828  942  

Sorted array:
12  55  80  84  175  241  251  303  375  384  389  390  501  517  532  787  802  806  828  942

Efficiency of Radix Sort

Basic parameters
- Max d digits
- n numbers
Time efficiency
- O(d * n) = O(n)
Space efficiency
- Amount of memory required
- Elements are copied to the queue
- Efficiency = O(n)

Time Simulations

The Objective

Simulation of a system over the course of time

Operating system
- Job/process processing
- I/O processing
Commercial institution
- Supermarket
- Bank
Traffic control

Ways of Simulating Time

Running the clock
- Have a loop that iterates though the units of time
  - Each iteration of the loop represents on discrete, atomic moment of time
- The text does this
- Fairly simple and straightforward
- Not really practical and sort of boring
Event-driven
- Only deal with those points in time where something 'interesting' happens
- Jump ahead to next 'interesting' time

The Components

Some form of clock/timekeeper
- Duh!-- it's a time simulation, remember? :)
Random number generator
- Most simulations work with averages
  - average arrival, average time of service, average speed, etc
- We're going to use a very simple one
Queue(s)
- For the waiting jobs, I/O requests, customers, etc
- May be FIFO or priority queue
Event queue
- Priority queue
System parameters
- Use easily modifiable variables to hold values you may want to change for next run of simulation
  - Maximum jobs
  - Opening/closing times
  - Average rate of customer arrival
- Allows easy modification of the system for extensive study and analysis

The Basic Idea

Set the clock
Usually generate an initial event, placed on event queue
- Time of first job arrival
Have an event loop
- Removes next event from event queue
- Process the event
  - May involve creating an object (e.g. jobs) and placing it on a queue
  - May involve remove an object from a queue (e.g. a job terminating)
  - Processing an event often generates other events
    - Processing a job's arrival also entails generating the arrival time of the next job
  - Statistics are captured as simulation proceeds
    - Maximum waiting time
    - Maximum waiting jobs
Simulation terminates when event queue is empty
- At which point statistics are output

A Job-Scheduling Simulation

Overview

This queue application presents a fairly simple version of the job scheduling manager of an operating system. Jobs enter the system, execute and leave the system. As the simulation progresses, statistics are captured and maintained about the performance of the scheduling algorithm. The simulation is performed twice, once for a first-come, first-served (FCFS) scheduling algorithm, the second for a shortest-job-first (SJF).

What is a Simulation?

A simulation is nothing more than a representation of a real-life situation. Simulations are also sometimes called models as they model the situation. While our simulation is based in software, this is not always the case. For example, civil service personnel may carry out a simulation of a natural disaster to train themselves so that they are well prepared to deal with such emergencies. Astronauts are trained in tanks of water to simulate a weightless environment.

More and more however, when people think of simulations they are thinking of 'computer-driven' simulations. This is a program in which we focus on those areas of the real-life situation that we wish to study, representing them with data structures.

The passage of time is usually a key element of a simulation -- the simulation is run against a virtual clock marking the passage of time. Highly sophisticated simulations might use actual clocks and real time values, just as they might use specialized hardware (such as used in an aircraft simulator, or the real radar screens that might be used in a war game simulation). We will be writing a very primitive simulation, and will be satisfied with relatively primitive time and clock values.

Simulating the Passage of Time

There are two ways of performing a time-based simulation: running the clock, and by jumping to the next occurrence (event) of interest. In both cases, we have a loop which represents the passing of time. The difference is how the passing is performed and, in particular, what each iteration through the loop represents. In running the clock, each iteration through the loop represents the passing of one unit of time. We then check whether anything needs handling at the new time. Thus a simulation that lasts for 2 million units of time requires 2 millions loop iterations.

The second method jumps forward in time to the next event of interest. This is identical to the technique used in books, TV shows and movies. A movie about World War II, for example, does not last for the same 6 years that the actual war did-- rather only the events relevant to the plot are depicted with the action jumping from one event to the next rather than having a steadily ticking clock. In this model, a pass through the loop corresponds to a single event of interest. If the simulated interval is 2 million units but only 10 items of interest occurred, the loop iterates only ten times.

The Simulation Parameters

While it may be primitive, the simulation is also useful, and we might wish to simulate various environments, i.e., different arrival or execution length patterns, or different maximum number of jobs in the system. These values that control the character of the simulation are often called the simulation parameters. A sophisticated approach is to read them in from a file, or have a graphic user interface (GUI) with switches and dials that allows the user to dynamically interact and change those parameters. We will represent them using hard-coded constants. The parameters of our simulation are:

AVG_ARRIVAL_INTERVAL - the average time between arrivals.
AVG_EXECUTION_DURATION - the average time a job needs to execute.
TOTAL_JOBS - the total number of jobs the simulation should create.

The Structure of the System

Simulation Flow - The Event Queue

The simulation is driven of an event queue, i.e., a queue whose elements are events of interest to the simulation. The events of note are the arrival of jobs into the system, and the completion of jobs. You might initially think that the selection of a job to begin execution should also be an event, but indeed, a closer examination will show us why it isn't and furthermore, help shed light on the nature of the two actual events.

As discussed above, the arrival of a job is determined by the calculation of a random value whose average is specified by the AVG_ARRIVAL simulation parameter. Once we calculate that value (i.e., the time until the next arrival), we must keep track of it in order to know when the job is to be arriving. Similarly, once a job beings execution, its time of completion is also a function of a random value being generated, and again, we must keep track of that time. In contrast, the time at which a job begins execution is not a function of a randomly generated value; rather it occurs when the previously running job has completed and the job in question is the one selected by the scheduling algorithm to be the next one executed.

The above discussion can be expanded a bit to give us a better sense of the role of the event queue in the simulation:

The average arrival time is a value representing the average time between the arrival of jobs in the system. This implies that at the point a job arrives into the system, we can then schedule the arrival of the next job using our AVG_ARRIVAL parameter. In other words, the actual arrival of a job can be thought as triggering the event consisting of the arrival of the NEXT job.
When a job is scheduled for execution, we can calculate its time of completion (by adding the job's execution duration to the current time). Once the job completes, we can then select the next job for execution. In this case, it is the completion of one job that triggers the execution of the next.
The simulation begins by placing calculating the very first job arrival time and placing the corresponding event onto the event queue. As mentioned above all subsequent arrivals are triggered when the previous arrival occurs.
In a similar fashion, once the total number of jobs has been processed, no further arrivals are generated. Eventually all remaining jobs are executed (and subsequently completed), the event queue empties itself (no more arrivals, no more completions), and the simulation then terminates.

We see from this that for each event, we must keep track of:

The type of event: arrival or completion
The time of the event
Possibly other information related to the particular type of the event

One last point-- we will be processing the events in the order in which they occur, i.e., by their time-- an earlier event should be processed before a later one. The event queue is thus properly a timestamp-based priority queue rather than a FIFO.

The Job Queue

An arrival event signals a new job entering the system. Again, we are not concerned with any details of an actual program being run (i.e., we don't care what the program does, or what it's code is like); all we are concerned about is when it arrived, how long it will take to execute, how long it had to wait until it received it's turn to execute, i.e., properties of the job relevant to the simulation. Our notion of a job is thus restricted to these values. The notion of job arrival thus means nothing more than taking note of the current time, calculating how long the job will execute for (using the AVG_DURATION simulation parameter) and possibly assigning the job some sort of id for identification purposes (unnecessary in the strictest sense, but useful for debugging, tracking the jobs, and also for adding more realism to the simulation).

If when the job is created, there is no execution job (because there are no other jobs in the system), the job can be immediately executed; otherwise it must wait its turn — and that is the whole focus of the simulation — how jobs are selected. FCFS schedules the jobs for execution in order of arrival, and jobs in that simulation are placed on a FIFO queue. SJF on the other hand, schedule the shortest job present in the system first, and thus a priority queue is the proper choice to hold the jobs in that situation.

Working with Priority Queues

Priority queues by their very nature, impose an order on the elements (in order to discover and return the largest element). This, in turn requires that the elements be comparable, i.e., that there be some way to compare two objects of the element type and determine which is less than (or greater than) the other. The JCF requires priority queue requires that the element type of a priority queue implements the Comparable interface, which specifes a compareTo method. (As an aside, there is another way to provide a priority queue with a comparison facility for its element type; we may cover that later when we investigate the JCF in more detail).

As discussed above, the event queue is implemented as a priority queue (with the ordering based upon the time of the event). As per our discussion, the next item to be obtained from the event queue is the next event to occur (i.e., the one with the lowest time value), which fits in well with the JCF priority queue, which is a min priority queue. Similarly, the job queue for the SJF simulation is implemented using a min priority queue; this one prioritized according to the execution time.

Other Data Structures

In addition to the event queue and job queue, you will need structures for:

a job — id, arrival time, and length of job
an event &mdasj; time and type of event

You will also need to represent the time in some fashion, as well as keep track of the current time. In our minimal system (remember, we're here to show queue applications, the this has little to do with the queue manipulation itself) we will use an integer representing the elapsed time from the beginning of the simulation. We will also introduce a simple Clock class that represents the passing of time (it will use the elapsed time value as its instance variable to represent the current time of the clock).

The Random Number Generator

You will also have to generate random numbers with various ranges. The standard C library function, rand, returns numbers in the range 0..1. You might find it useful to create a function which produces integer-valued random numbers in a specified range.

A poor, unrealistic, but simple way to generate random numbers whose average is the value n is to generate a random number in the range 0 .. 2n.

The proper way to do this for such a simulation is to generate an exponential distribution to simulate what is called a Poisson process, i.e., where events occur at a constant average rate but independently of each other.

Revisiting The Control Flow

initialize the clock (probably to time 0)
generate the first arrival event: and place it onto the event queue 

while the event queue is not empty
	remove an event
	if the event is an arrival
		create a job
		if the job queue is empty, execute the new job; otherwise place it onto the job queue
		if we haven't reached the total number of jobs to be created, generate the next arrival event
			and place it onto the event queue
	else  // its a completion
		terminate the job (i.e., calculate and maintain any necessary statistics)
		if the job queue is not empty, remove the next job and execute it 

calculate and print the final statistics

execution of a job involves nothing more than creating a completion event for the job. The time of completion is calculated from the time at which execution begins and the execution length of the job.

The Statistics to be Captured

After the simulation, we print out the simulation parameters followed by the following statistics:

Time the simulation ended
Minimum and maximum execution times generated for the jobs
Maximum and minimum arrival intervals generated for the jobs
Average, minimum, and maximum waiting time for jobs.
Number of jobs that executed immediately

Running the Simulation

To get a sense of how the two scheduling policies (FCFS and SJF) act on the same data, one can:

use identical arrival/job data -- by pre-generating the value and saving them in one or more files or vectors
use the same initial seed to generate the same sequences
simply rely on the randomness of it all and the fact that the same simulation parameters are being used

The Implementation

The `Clock` Class

class Clock {
	void set(long newTime) {this.now = newTime;}
	long now() {return now;}
	void add(long interval) {now += interval;}
	public String toString() {return toString(now);}
	public static String toString(long time) {return String.format("%02d:%02d", time / 60, time % 60);}
	long now = 0;
}

Notes

The `Job` Class

class Job implements Comparable {
	Job(long arrivalTime, long serviceTime) {
		this.arrivalTime = arrivalTime;
		this.serviceTime = serviceTime;
		id = nextId++;
	}
	int getId()  {return id;}
	long getArrivalTime() {return arrivalTime;}
	long getServiceTime() {return serviceTime;}
	public int compareTo(Job job) {return Long.compare(serviceTime, job.serviceTime);}

	static void resetJobIds() {nextId = 1;}

	int id;
	long arrivalTime, serviceTime;
	static int nextId = 1;
}

Notes

The `Event` Class

class Event implements Comparable {
	enum Type {ARRIVAL, COMPLETION}
	Event(Type type, long time) {
		this.type = type;
		this.time = time;
	}
	Type getType() {return type;}
	boolean isArrival() {return type == Type.ARRIVAL;}
	long getTime() {return time;}

	public int compareTo(Event event) {return Long.compare(time, event.time);}

	public String toString() {return type + " at " + Clock.toString(time);}

	Type type;
	long time;
}

Notes

The `JobScheduling` Class

import java.util.*;

public class SchedulingSimulation {

	SchedulingSimulation(String policy, Queue jobQ, int maxJobs, int averageArrival, int averageService) {
		this.policy = policy;
		this.jobQ = jobQ;
		this.maxJobs = maxJobs;
		this.averageArrival = averageArrival;
		this.averageService = averageService;
	}

	void simulate() {
		long nextArrivalTime = RandGen.next(averageArrival);
		eventQ.add(new Event(Event.Type.ARRIVAL, systemClock.now() + nextArrivalTime));
		totalArrivalTime += nextArrivalTime;

		while (!eventQ.isEmpty()) {
			Event event = eventQ.remove();
			systemClock.set(event.getTime());
			if (DEBUG)
				System.out.println(systemClock + ": " +  " *** Event " + event + " occurs");


			switch (event.type) {
				case ARRIVAL: jobArrives(); break;
				case COMPLETION: jobCompleted(); break;
			}
		}

		System.out.println("\n\n");
		System.out.println("!!!!!!!!!!!!!!! Statistics !!!!!!!!!!!!!!");
		System.out.println("Scheduling policy: " + policy);
		System.out.println("Average arrival time: Expected: " + averageArrival + " Actual: " + ((double)totalArrivalTime / numJobs));
		System.out.println("Average service time: Expected: " + averageService + " Actual: " + ((double)totalServiceTime / numJobs));
		System.out.println("Maximum jobs on the queue at any point: " + maxJobsOnQueue);
		System.out.println("Maximum wait time for any job: " + maxWaitTime + " (job " + maxWaitJob + ")");
		System.out.println("Average waiting time: " + ((double)totalWaitTime / numJobs));
	}

	void jobArrives() {
		var serviceTime = RandGen.next(averageService);
		Job job = new Job(systemClock.now(), serviceTime);
		totalServiceTime += serviceTime;
		jobQ.add(job);

		if (TRACE) 
			System.out.println(systemClock + ": " + "Job " + job.getId() + " enters system with a service time of " + 
					Clock.toString(job.getServiceTime()) + ". Job queue now contains " + jobQ.size() + " jobs.");

		if (jobQ.size() > maxJobsOnQueue) maxJobsOnQueue = jobQ.size();

		numJobs++;
		if (numJobs != maxJobs) {
			int nextArrivalTime = RandGen.next(averageArrival);
			Event event = new Event(Event.Type.ARRIVAL, systemClock.now() + nextArrivalTime);
			eventQ.add(event);
			if (DEBUG) 
				System.out.println(systemClock + ": " + "scheduled " + event);
			totalArrivalTime += nextArrivalTime;
		}

		if (systemIsIdle()) selectJob();
	}

	void jobCompleted() {
		if (TRACE)
			System.out.println(systemClock + ": " + "Job " + currentJob.getId() + " completed");

		if (!jobQ.isEmpty()) 
			selectJob();
		else {
			currentJob = null;
			if (TRACE)
				System.out.println(systemClock + ": " + "!!!! System goes idle");
		}
	}

	void selectJob() {
		currentJob = jobQ.remove();

		if (TRACE)
			System.out.println(systemClock + ": " + "Job " + currentJob.getId() + " selected for execution");

		eventQ.add(new Event(Event.Type.COMPLETION, systemClock.now() + currentJob.getServiceTime()));

		if (DEBUG)
			System.out.println(systemClock + ": " + "Job " + currentJob.getId() + " scheduled for completion at " + (systemClock.now() + currentJob.getServiceTime()));

		totalWaitTime += systemClock.now() - currentJob.getArrivalTime();
		if (systemClock.now() - currentJob.getArrivalTime() > maxWaitTime) {
			maxWaitTime = systemClock.now() - currentJob.getArrivalTime();
			maxWaitJob = currentJob.getId();
		}
	}

	boolean systemIsIdle() {return currentJob == null;}

	public static void main(String [] args) {
		final int 
			MAX_JOBS = 1000,
			AVG_ARRIVAL = 3,
			AVG_SERVICE = 8;
		new SchedulingSimulation("FCFS", new ArrayDeque(), MAX_JOBS, AVG_ARRIVAL, AVG_SERVICE).simulate();
		System.out.println();
		System.out.println("===========================");
		System.out.println();
		Job.resetJobIds();
		new SchedulingSimulation("SJF", new PriorityQueue(), MAX_JOBS, AVG_ARRIVAL, AVG_SERVICE).simulate();
	}

	int maxJobs;

	int 
		averageArrival,
		averageService;

	int numJobs = 0;

	int
		maxJobsOnQueue = 0;
	
	long
		maxWaitTime = 0,
		totalArrivalTime = 0,
		totalServiceTime = 0,
		totalWaitTime = 0;

	int
		maxWaitJob = -1;

	String policy;

	Queue jobQ;
	Job currentJob;

	PriorityQueue eventQ = new PriorityQueue<>();
	Clock systemClock = new Clock();


	final static boolean TRACE = true;
	final static boolean DEBUG = false;
}

Notes

00:03: Job 1 enters system with a service time of 00:00. Job queue now contains 1 jobs.
00:03: Job 1 selected for execution
00:03: Job 2 enters system with a service time of 00:08. Job queue now contains 1 jobs.
00:03: Job 1 completed
00:03: Job 2 selected for execution
00:07: Job 3 enters system with a service time of 00:08. Job queue now contains 1 jobs.
00:09: Job 4 enters system with a service time of 00:03. Job queue now contains 2 jobs.
00:11: Job 2 completed
00:11: Job 3 selected for execution
00:14: Job 5 enters system with a service time of 00:02. Job queue now contains 2 jobs.
00:14: Job 6 enters system with a service time of 00:21. Job queue now contains 3 jobs.
00:14: Job 7 enters system with a service time of 00:05. Job queue now contains 4 jobs.
00:17: Job 8 enters system with a service time of 00:02. Job queue now contains 5 jobs.
00:17: Job 9 enters system with a service time of 00:08. Job queue now contains 6 jobs.
00:19: Job 3 completed
00:19: Job 4 selected for execution
00:22: Job 4 completed
00:22: Job 5 selected for execution
00:24: Job 10 enters system with a service time of 00:04. Job queue now contains 5 jobs.
00:24: Job 5 completed
00:24: Job 6 selected for execution
00:30: Job 11 enters system with a service time of 00:00. Job queue now contains 5 jobs.
00:34: Job 12 enters system with a service time of 00:10. Job queue now contains 6 jobs.
00:35: Job 13 enters system with a service time of 00:24. Job queue now contains 7 jobs.
00:39: Job 14 enters system with a service time of 00:01. Job queue now contains 8 jobs.
00:41: Job 15 enters system with a service time of 00:11. Job queue now contains 9 jobs.
00:45: Job 6 completed
00:45: Job 7 selected for execution
00:46: Job 16 enters system with a service time of 00:21. Job queue now contains 9 jobs.
00:50: Job 7 completed
00:50: Job 8 selected for execution
00:52: Job 17 enters system with a service time of 00:04. Job queue now contains 9 jobs.
00:52: Job 8 completed
00:52: Job 9 selected for execution
00:54: Job 18 enters system with a service time of 00:05. Job queue now contains 9 jobs.
00:55: Job 19 enters system with a service time of 00:00. Job queue now contains 10 jobs.
01:00: Job 9 completed
01:00: Job 10 selected for execution
01:02: Job 20 enters system with a service time of 00:13. Job queue now contains 10 jobs.
01:04: Job 10 completed
01:04: Job 11 selected for execution
01:04: Job 11 completed
01:04: Job 12 selected for execution
01:14: Job 12 completed
01:14: Job 13 selected for execution
01:38: Job 13 completed
01:38: Job 14 selected for execution
01:39: Job 14 completed
01:39: Job 15 selected for execution
01:50: Job 15 completed
01:50: Job 16 selected for execution
02:11: Job 16 completed
02:11: Job 17 selected for execution
02:15: Job 17 completed
02:15: Job 18 selected for execution
02:20: Job 18 completed
02:20: Job 19 selected for execution
02:20: Job 19 completed
02:20: Job 20 selected for execution
02:33: Job 20 completed
02:33: !!!! System goes idle



!!!!!!!!!!!!!!! Statistics !!!!!!!!!!!!!!
Scheduling policy: FCFS
Average arrival time: Expected: 3 Actual: 3.1
Average service time: Expected: 8 Actual: 7.5
Maximum jobs on the queue at any point: 10
Maximum wait time for any job: 85 (job 19)
Average waiting time: 38.7

===========================

00:01: Job 1 enters system with a service time of 00:00. Job queue now contains 1 jobs.
00:01: Job 1 selected for execution
00:01: Job 1 completed
00:01: !!!! System goes idle
00:03: Job 2 enters system with a service time of 00:05. Job queue now contains 1 jobs.
00:03: Job 2 selected for execution
00:03: Job 3 enters system with a service time of 00:05. Job queue now contains 1 jobs.
00:08: Job 2 completed
00:08: Job 3 selected for execution
00:13: Job 3 completed
00:13: !!!! System goes idle
00:21: Job 4 enters system with a service time of 00:03. Job queue now contains 1 jobs.
00:21: Job 4 selected for execution
00:22: Job 5 enters system with a service time of 00:02. Job queue now contains 1 jobs.
00:23: Job 6 enters system with a service time of 00:16. Job queue now contains 2 jobs.
00:24: Job 4 completed
00:24: Job 5 selected for execution
00:26: Job 5 completed
00:26: Job 6 selected for execution
00:33: Job 7 enters system with a service time of 00:01. Job queue now contains 1 jobs.
00:35: Job 8 enters system with a service time of 00:13. Job queue now contains 2 jobs.
00:37: Job 9 enters system with a service time of 00:09. Job queue now contains 3 jobs.
00:38: Job 10 enters system with a service time of 00:03. Job queue now contains 4 jobs.
00:41: Job 11 enters system with a service time of 00:04. Job queue now contains 5 jobs.
00:42: Job 6 completed
00:42: Job 7 selected for execution
00:43: Job 12 enters system with a service time of 00:52. Job queue now contains 5 jobs.
00:43: Job 7 completed
00:43: Job 10 selected for execution
00:44: Job 13 enters system with a service time of 00:03. Job queue now contains 5 jobs.
00:45: Job 14 enters system with a service time of 00:05. Job queue now contains 6 jobs.
00:46: Job 10 completed
00:46: Job 13 selected for execution
00:46: Job 15 enters system with a service time of 00:01. Job queue now contains 6 jobs.
00:46: Job 16 enters system with a service time of 00:04. Job queue now contains 7 jobs.
00:48: Job 17 enters system with a service time of 00:01. Job queue now contains 8 jobs.
00:49: Job 13 completed
00:49: Job 15 selected for execution
00:49: Job 18 enters system with a service time of 00:00. Job queue now contains 8 jobs.
00:50: Job 15 completed
00:50: Job 18 selected for execution
00:50: Job 19 enters system with a service time of 00:04. Job queue now contains 8 jobs.
00:50: Job 18 completed
00:50: Job 17 selected for execution
00:51: Job 17 completed
00:51: Job 19 selected for execution
00:52: Job 20 enters system with a service time of 00:08. Job queue now contains 7 jobs.
00:55: Job 19 completed
00:55: Job 16 selected for execution
00:59: Job 16 completed
00:59: Job 11 selected for execution
01:03: Job 11 completed
01:03: Job 14 selected for execution
01:08: Job 14 completed
01:08: Job 20 selected for execution
01:16: Job 20 completed
01:16: Job 9 selected for execution
01:25: Job 9 completed
01:25: Job 8 selected for execution
01:38: Job 8 completed
01:38: Job 12 selected for execution
02:30: Job 12 completed
02:30: !!!! System goes idle



!!!!!!!!!!!!!!! Statistics !!!!!!!!!!!!!!
Scheduling policy: SJF
Average arrival time: Expected: 3 Actual: 2.6
Average service time: Expected: 8 Actual: 6.95
Maximum jobs on the queue at any point: 8
Maximum wait time for any job: 55 (job 12)
Average waiting time: 11.9

!!!!!!!!!!!!!!! Statistics !!!!!!!!!!!!!!
Scheduling policy: FCFS
Average arrival time: Expected: 3 Actual: 2.549
Average service time: Expected: 8 Actual: 7.596
Maximum jobs on the queue at any point: 652
Maximum wait time for any job: 5044 (job 1000)
Average waiting time: 2422.079

===========================


!!!!!!!!!!!!!!! Statistics !!!!!!!!!!!!!!
Scheduling policy: SJF
Average arrival time: Expected: 3 Actual: 2.65
Average service time: Expected: 8 Actual: 7.639
Maximum jobs on the queue at any point: 279
Maximum wait time for any job: 7102 (job 74)
Average waiting time: 910.925

CISC 3130 Data Structures Applications — Queue

Radix Sort

Why This Works

Efficiency of Radix Sort

Time Simulations

The Objective

Ways of Simulating Time

The Components

The Basic Idea

A Job-Scheduling Simulation

Overview

What is a Simulation?

Simulating the Passage of Time

The Simulation Parameters

The Structure of the System

Simulation Flow - The Event Queue

The Job Queue

Working with Priority Queues

Other Data Structures

The Random Number Generator

Revisiting The Control Flow

The Statistics to be Captured

Running the Simulation

The Implementation

The Clock Class

The Job Class

The Event Class

The JobScheduling Class

Code related to this lecture

CISC 3130
Data Structures
Applications — Queue

The `Clock` Class

The `Job` Class

The `Event` Class

The `JobScheduling` Class