We have seen in class how to define and implement a generic linked list. The spirit of this programming assignment is a little bit different. P06 presents a simple application of the linked lists in Scheduling Systems. In this assignment, you will write a specific JobScheduler class that uses a variant of a simple linked list to schedule arriving jobs according to a particular scheduling policy.

OBJECTIVES AND GRADING CRITERIA

The goals of this programming assignment are as follows:

Understand Linked List as an important Abstract Data Type (ADT).

Implement a specific Job Scheduler using a dynamic Linked List from scratch.

Understand applications of Linked List in scheduling systems

GETTING STARTED:

To get started, we will not use any pre-defined linked list data structure provided by Java or any other source. You should not use LinkedList or ArrayList classes from the Java standard library for instance. You must implement a custom version for the linked list from scratch following the following steps.

1. CREATING GENERIC INTERFACE WAITINGLISTADT

First, define a generic interface called WaitingListADT to include the following methods:

1 2 3 4 5 6 7 8 9 10 11 12 13 14

public void schedule(T newObject); // adds an item of type to the waiting list // according to a specific scheduling policy public boolean isEmpty(); // checks if the waiting list is empty // returns true if the waiting list empty // false otherwise public int size(); // returns the number of items in the waiting list public int clean(float cleaningTime); // removes the obsolete items from the waiting list public void clear(); // removes all the items in the waiting list public WaitingListADT duplicate(); // returns a new reference to a duplicate copy of the list

It is worth to note that the description of the specific behavior for methods schedule and clean is detailed in the Javadoc methods comments related to the class JobLList later in this assignment.

2. CREATING A JOBNODE CLASS

Our linked list should also have linked nodes, lets call them jobNodes. A JobNode represents a class that contains the following fields:

jobId: unique job identifier

arrivalTime: arrival time in seconds

userId: identifier of the user that created the job

priority: job priority

timeToLive: job Time To Live in seconds

description: job description

next: reference to the next job in the linked list

It is worth noting that every created new instance of JobNode should be assigned a unique identifier (jobId). The identifier for the first created JobNode object should be 1. Then, the next identifiers for the next created JobNode objects should be set in an incremental order. To do so, you can make use of the static variable jobCount that is initialized to zero and would be incremented inside the constructors defined for the JobNode class.

Please find in the following a sample for the JobNode class implementation to complete. Dont forget to:

define at least one constructor for this class,

define getters methods for every declared field and setters methods as needed, and

implement the copy method. Copy method returns a reference to a new copy of the current instance of JobNode (this). The copy of a JobNode should be a separate object that has the same values within its fields as the original. For instance, the number of created jobs should not be incremented after calling the copy method.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

/** * File Header COMES HERE */ /** * JavaDoc Class Header COMES HERE * */ public class JobNode { // Class Fields private static int jobCount = 0; // number of jobs already created // Object Fields private int jobId; // unique job identifier private float arrivalTime; // arrival time in seconds private int userId; // identifier of the user that created the job private int priority; // job priority private int timeToLive; // job Time To Live in seconds private String description; // job description private JobNode next; // reference to the next job in the linked list // Constructor using fields /** * Description of the constructor comes here * @param arrivalTime * @param userId * @param priority * @param ttl * @param description */ public JobNode(float arrivalTime, int userId, int priority, int ttl, String description) { // TODO implementation details come here } // You can overload your class by other constructors // TODO Add Getters and Setters Methods as needed /** * This method returns a new reference to a copy of the current JobNode * @return a new reference to a copy of this (instanceof JobNode) */ public JobNode copy() { // TODO Implementation details come here } }

3. CREATING A JOBLLIST CLASS

Now, you need to write a class called JobLList that implements the interface WaitingListADT . JobLList class represents a simple linked list of nodes of type JobNode.

1	public class JobLList implements WaitingListADT

Our JobLList class contains two fields:

head: head of the list

size: number of jobs in the list

While writing the JobLList Class, make sure to follow these directions:

While implementing methods declared in the WaitingListADT interface, you may use existing methods in the provided JobLList and JobNode classes, but you must not use any methods from java.util, any other Java libraries or any source. For instance, you can use the copy method of the JobNode class while implementing JobLList duplicate method. Further details related to how to implement schedule and clean methods are provided in the following steps.

Implement the schedule method according to the following policy:

1	public void schedule(JobNode newJob)

The newJob is added at the end of the list, if its priority equals 0

If the newJob has a higher priority (priority equals 1), then it should be added before all the already scheduled jobs of lower priority 0 and after the already scheduled jobs of the same priority 1.

3. Implement the clean method according to the following description:

1	public int clean(float cleaningTime)

At cleaningTime, all the obsolete jobs should be removed from the list. A job (here an isntanceof JobNode) is obsolete if: its arrivalTime + its timeToLive < cleaningTime

As output, clean method returns the number of cleaned jobs.

4. Make sure to update the size of the linked list after every operation that changes the lists contents in any way.

5. In your JobLList class, in addition to implementing all the functionalities supported by a WaitingListADT, make sure to

create a Constructor which constructs an empty list,

add the getters and setters methods as needed, and

add a toString() method that returns a string representation of this list which looks as follows when it is printed:

Job List is empty: false The size is:  job(s). job # :  (UID )  job # :  (UID )  ... job # :  (UID )  

For instance, if the List is empty, toString() method prints the list as follows:

Job List is empty: true The size is: 0 job(s). 

USING THE LINKED LIST:

Now, we will use this class to solve a scheduling problem.

4. CREATING A JOBSCHEDULER CLASS

Now, Lets implement our JobScheduler and test the implementation of the JobLList class.

JobScheduler is a class that contains one field:

jobList of type JobLList that represents the job waiting list.

Please complete the JobScheduler class as follows:

Make sure to define a constructor that creates an empty JobLList.

Add a getter method getJobList() that returns the reference to the jobList

JobScheduler contains also a method called startScheduling that performs the scheduling process of arriving jobs while parsing a given jobs trace file:

The jobs trace file contains fields representing data for each job in this order:

#arrival_time_in_seconds #user_id #priority #TimeToLive #Description 

Here is an example of trace file that you can use to run your test: jobs

In order to use it, you are invited to create a folder called files within your project folder in Eclipse: this can be done by right clicking your project in the Project Explorer and selecting New > Folder. Then download the trace file jobs and copy it into your new files folder: jobs.txt by right-clicking the links and selecting Save link as. If you dont see the files folder and the jobs file in Eclipse immediately, try right-clicking on your project folder and selecting Refresh.

It is worth noting that we consider in this assignment two priorities: 0 and 1 with priority of 1 as more important than that of 0.

startScheduling method performs the following instructions:

Starts reading in the jobs.txt file and parses its content line by line.

Cleans the list before adding the new arriving job, by calling the clean method of JobLList class. This method removes all obsolete jobs from the list with respect to the arriving time of the new one. So, all the old jobs which their arrival times + their TimeToLive (TTL) time are lower than the arriving time of the new job will be removed from the list.

Displays the number of cleaned jobs

Schedules every arriving job using the schedule method of JobLList class in a manner that the jobs that arrived earlier should be placed at the start of the list and you keep adding the jobs towards the end which have later start times. If a job with a higher priority( with a priority of 1) arrives, it should be placed before all the other jobs with the lower priority.

Prints the content of the list using toString method

The implementation for the method startScheduling is provided in the following. Please make sure to understand how it works.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73

/** * startScheduling method reads a trace file of name * tracefilename, parses its content line by line. * Each line represents data related to an arriving job, * Before scheduling any job (aka placing it in the list), * this method cleans the list and displays the number * of removed jobs. * @param tracefilename */ public void startScheduling(String tracefilename) { FileReader fr = null; // reference to a FileReader object BufferedReader br = null; // reference to a BufferedReader object try{ // Open the file String fileFolder = "files"; fr = new FileReader(fileFolder+ File.separatorChar + tracefilename); br = new BufferedReader(fr); String line = null; // Parse the content of the trace file line by line while( (line = br.readLine()) != null){ // extract the data related to the arriving job String[] contents = line.split(" "); float arrivalTime = Float.parseFloat(contents[0]); int userId = Integer.parseInt(contents[1]); int priority = Integer.parseInt(contents[2]); int timeToLive = Integer.parseInt(contents[3]); StringBuilder str = new StringBuilder(""); for(int i = 4; i < contents.length; i++){ str.append(contents[i]); str.append(" "); } String description = str.toString().trim(); //create a new job instanceof JobNode class JobNode objJob = new JobNode(arrivalTime, userId, priority, timeToLive, description); System.out.println("Job Waiting List Status at " + objJob.getArrivalTime() + "s"); System.out.println("*************************************"); // Before adding the new job, let's remove the obsolete jobs // in the list and display the number of cleaned jobs int cleanedJobCount = jobList.clean(arrivalTime); System.out.println(cleanedJobCount + " obsolete job(s) removed from the list."); // Schedule the created new job jobList.schedule(objJob); // add the new JobNode to the list // according to the scheduling policy System.out.println("Event: Job #" + objJob.getJobId() + " added to the list."); // Print the content of the list System.out.println(jobList.toString()); } br.close(); } catch(IOException e){ e.printStackTrace(); } finally { // close open resources if (br != null) try { br.close(); } catch(IOException e){ e.printStackTrace(); } } }

Finally, in order to test your jobScheduler, you can add the following lines of code to the Main method of JobScheduler class:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

// Display Welcome Message System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"); System.out.println(" Job Scheduler version 1.0"); System.out.println("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ "); // Create a JobScheduler object JobScheduler myJobScheduler = new JobScheduler(); // Print the list System.out.println("Initial Job Waiting List Status"); System.out.println("*******************************"); System.out.println(myJobScheduler.getJobList().toString()); // Parse the trace file and start scheduling simulation myJobScheduler.startScheduling("jobs.txt"); // Duplicate List JobLList copyJobList = (JobLList)myJobScheduler.getJobList().duplicate(); // Display Duplicated list content System.out.println("Duplicate List Status"); System.out.println("*********************"); System.out.println(copyJobList.toString()); // Clear the original list System.out.println("Clear Original List"); System.out.println("*******************"); myJobScheduler.getJobList().clear(); // Display the content of the original list System.out.println(myJobScheduler.getJobList().toString()); // END System.out.println(" -------- END Scheduling Simulation --------");

Here is an example of how the output of your program would look like when it runs:

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Job Scheduler version 1.0 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Initial Job Waiting List Status ******************************* Job List is empty: true The size is: 0 job(s). Job Waiting List Status at 1.25s ************************************* 0 obsolete job(s) removed from the list. Event: Job #1 added to the list. Job List is empty: false The size is: 1 job(s). job #1 : ALERT MESSAGE (UID 1) 1 Job Waiting List Status at 2.35s ************************************* 0 obsolete job(s) removed from the list. Event: Job #2 added to the list. Job List is empty: false The size is: 2 job(s). job #1 : ALERT MESSAGE (UID 1) 1 job #2 : PRINT document (UID 5) 0 Job Waiting List Status at 2.58s ************************************* 0 obsolete job(s) removed from the list. Event: Job #3 added to the list. Job List is empty: false The size is: 3 job(s). job #1 : ALERT MESSAGE (UID 1) 1 job #3 : EMERGENCY MESSAGE (UID 8) 1 job #2 : PRINT document (UID 5) 0 Job Waiting List Status at 3.49s ************************************* 1 obsolete job(s) removed from the list. Event: Job #4 added to the list. Job List is empty: false The size is: 3 job(s). job #3 : EMERGENCY MESSAGE (UID 8) 1 job #2 : PRINT document (UID 5) 0 job #4 : PRINT Lecture Notes (UID 6) 0 Job Waiting List Status at 4.67s ************************************* 2 obsolete job(s) removed from the list. Event: Job #5 added to the list. Job List is empty: false The size is: 2 job(s). job #5 : SECURITY ALERT (UID 15) 1 job #2 : PRINT document (UID 5) 0 Duplicate List Status ********************* Job List is empty: false The size is: 2 job(s). job #5 : SECURITY ALERT (UID 15) 1 job #2 : PRINT document (UID 5) 0 Clear Original List ******************* Job List is empty: true The size is: 0 job(s). -------- END Scheduling Simulation --------