COMP9024 Assignment 3-Task scheduler Solution

Background

Task scheduler

First, we introduce two definitions: scheduling point and ready task.
• A scheduling point is a time point at which a task is scheduled on a core.
• A task vi (i=1, 2, ,,, n) is ready at a time t if tri holds.

The EDF scheduling strategy works as follows:


Example One






Table 1: A set S1 of 6 tasks with individual release times and deadlines
v1 4 0 4
v2 4 1 5
v3 5 3 10
v4 6 4 11
v5 4 6 13
v6 5 6 18



Core1

Core2 v2

Time 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16



Example Two


Table 2: A set of tasks with individual release times and deadlines
v1 4 0 4
v2 4 1 5
v3 5 3 10
v4 6 4 11
v5 4 9 16
v6 5 10 15



Core1 v1

Core2 v2
Time 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16








Core1 v1

Core2 v2
Time 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16





The TaskScheduler class

You need to write a task scheduler class named TaskScheduler. A template of the TaskScheduler class is shown as follows.

public class TaskScheduler
{
…
static void scheduler(String file1, String file2, int m) {};
…
}

class ClassX {} /** Put all the additional classes you need here */
…

You can define any fields, constructors and methods within the TaskScheduler class. You can also define additional classes. You must put all the additional classes in the file Taskscheduler,java.



v1 c1 r1 d1 v2 c2 r2 d2 … vn cn rn dn



This method needs to handle all the possible cases properly when reading from file1 and writing to file2. All the possible cases are as follows:
1. file1 does not exist. In this case, print “file1 does not exist” and the program terminates.
2. file2 already exists. In this case, overwrite the old file2.

file2 has the following format:

v1 p1 t1 v2 p2 t2 … vn pn tn



Time complexity requirement

You need to include your time complexity analysis as comments in your program. The time complexity of your scheduler is required to be no higher than O(n*log n), where n is the number of tasks (Hints: use heap-based priority queues). You need to include the time complexity analysis of your task scheduler in the TaskScheduler class file as comments. There is no specific requirement on space complexity. However, try your best to make your program space efficient.

net.datastructures-4-0 package

You can use net.datastructures-4-0 where there is a heap-based priority queue class named HeapPriorityQue.java. Read through its code and understand how it works.

Restrictions

All the other data structures and algorithms that are not in net.datastructures-4-0 must be implemented in the TaskScheduler class. You are NOT allowed to use any sorting algorithms and priority queues provided by Java.

How to submit your code?

Follow this link: https://cgi.cse.unsw.edu.au/~give/Student/give.php. Do the following:
1. Use your z-pass to log in.
2. Select current session, COMP9024 and assn3.
3. Submit TaskScheduler.java.

Marking

Marking is also based on the correctness and efficiency of your code. Your code must be well commented.

The full mark of this assignment is 7 if the time complexity of your scheduler satisfies the abovementioned requirement. Otherwise, the full mark will be 0.