Application #4

Using ArrayDeque and PriorityQueue classes from java.util write a program to simulate job scheduling in an operating system.

Jobs are generated at random times.

Each job is given:

a random priority from 1 to 4, where 1 is the highest priority

a random amount of time to complete its execution.

Jobs do not begin execution and run to completion, but instead share the processor. The operating system executes a job for a fixed unit of time called a time slice. At the end of the time slice, the current jobs execution is suspended, and the job is placed back on the priority queue, where it waits for its next share of processor time. The job having the highest priority is then removed from the priority queue and executed for the time slice.

When a job is first generated, it will begin executing immediately if the processor is free. Otherwise it will be placed on the priority queue.

Since the job scheduling can be done not only by the priority but also by some other attributes add ability to run the simulation in two modes:

1. where jobs are ordered by their priority (compareTo)

2. where jobs are ordered by their timeLeft (need to implement Comparator)

SchedulingSimulation constructor would take a parameter which will indicate the priority queue ordering: SORT_BY_PRIORITY or SORT_BY_LENGTH

Job class has implementation of compareTo method, so it must be declared as:

public class Job implements Comparable

With compareTo method implemented, we can create PriorityQueue that organizes entries by the natural ordering as follow:

this.waitingJobs = new PriorityQueue();

To create a PriorityQueue that organizes elements NOT by the natural ordering we need to implement compare method that is defined by the Comparator interface. We can create appropriate PriorityQueue utilizing annonymous inner class as follow:

this.waitingJobs = new PriorityQueue(new Comparator()

{

public int compare(Job job1, Job job2)

{

return job1.getTimeLeft() - job2.getTimeLeft();

}

});

In the attached sample run the simulation constants were set as follow:

TIME_SLICE_PER_JOB = 3;

SIMULATION_DURATION = 100;

JOB_PROBABILITY = 30;

JOB_PRIORITY = 4;

JOB_MIN_TIME = 1;

JOB_MAX_TIME = 5;

Sample Run #1:

***STARTING THE SIMULATION WITH PRIORITY MODE SET TO SORT_BY_PRIORITY***

Time Marker 0 waiting: 0

executing: NONE

created: Job #1 priority(1) created at 0, time left 4

Time Marker 1 waiting: 0

executing: Job #1 priority(1) created at 0, time left 4

Time Marker 2 waiting: 0

executing: Job #1 priority(1) created at 0, time left 3

created: Job #2 priority(2) created at 2, time left 5

Time Marker 3 waiting: 1

executing: Job #1 priority(1) created at 0, time left 2

Time Marker 4 waiting: 1

executing: Job #1 priority(1) created at 0, time left 1

completed: Job #1 at time 4

Time Marker 5 waiting: 0

executing: Job #2 priority(2) created at 2, time left 5

created: Job #3 priority(3) created at 5, time left 2

Time Marker 6 waiting: 1

executing: Job #2 priority(2) created at 2, time left 4

created: Job #4 priority(3) created at 6, time left 2

Time Marker 7 waiting: 2

executing: Job #2 priority(2) created at 2, time left 3

Time Marker 8 waiting: 2

executing: Job #2 priority(2) created at 2, time left 2

Time Marker 9 waiting: 2

executing: Job #2 priority(2) created at 2, time left 1

completed: Job #2 at time 9

Time Marker 10 waiting: 1

executing: Job #3 priority(3) created at 5, time left 2

created: Job #5 priority(3) created at 10, time left 2

Time Marker 11 waiting: 2

executing: Job #3 priority(3) created at 5, time left 1

created: Job #6 priority(3) created at 11, time left 3

completed: Job #3 at time 11

Time Marker 12 waiting: 2

executing: Job #4 priority(3) created at 6, time left 2

Time Marker 13 waiting: 2

executing: Job #4 priority(3) created at 6, time left 1

completed: Job #4 at time 13

Time Marker 14 waiting: 1

executing: Job #6 priority(3) created at 11, time left 3

Time Marker 15 waiting: 1

executing: Job #6 priority(3) created at 11, time left 2

*************** Final Report: ***************

Active jobs:

Job #36 priority(1) created at 97, time left 2

Job #37 priority(2) created at 99, time left 4

Job #17 priority(3) created at 50, time left 2

Job #25 priority(3) created at 60, time left 2

Job #30 priority(3) created at 76, time left 4

Job #12 priority(4) created at 37, time left 2

Job #18 priority(4) created at 51, time left 5

Job #31 priority(4) created at 77, time left 5

Job #21 priority(4) created at 56, time left 2

Job #20 priority(4) created at 53, time left 4

Job #27 priority(4) created at 65, time left 4

Job #34 priority(4) created at 85, time left 3

The number of jobs currently executing is 12

The number of completed jobs is 25

The total number of jobs is 37

The average time left for unfinished jobs is 3.42

**