Reference no: EM133125280
This assignment consists of two parts: (1) read and understand the referenced paper [1], and (2) write a program to implement the power-aware scheduling algorithm for sporadic tasks in this referenced paper (Algorithm STS).
A sporadic task is denoted by T = {a, c, d}, where a is the arrival time, c is the computation time, and d is the deadline. In this assignment, it is assumed that the speed/voltage of the system/processor running these tasks can be scaled in the interval (0, 1.0].
A scheduling decisionis made whenever any of the following two events occurs: (i) Event-1: a new sporadic task arrives and is accepted into the system by the acceptance test, and (ii) Event-2: the current task completes its execution. When an Event-1 occurs, the scheduler updates the optimal voltage schedule of the processor for all the tasks including this new one in the task queue. The variable voltage scheduling algorithm is shown as Algorithm STS in [1]. When an Event-2 occurs, the completed task is removed from the task queue and we execute the task at the head of the task queue following the current voltageschedule.
What you need to do when implementing the STS algorithm [1]:
Given an input - a set of sporadic tasks arriving dynamically, schedule the tasks in an online manner to (1) meet all deadlines or discard the newly arriving task if it would cause any accepted/uncompleted task to its deadline, including the new task itself; and (2) to schedule the tasks in optimal speeds in order to minimize the energy consumption.
Output: The complete task schedule and the optimal speed schedule.
What you will be given for the input is a file input.txt. You program needs to read the input from this file. In the file, the format of the inputis:
Number of tasks: N Task 1: [a c d]
Task 2: [a c d]
....
....
Task N: [a c d]
Here is an example of the file:
Number of tasks: 3 Task 1: [0 4 10]
Task 2: [3 5 9]
Task 3: [6 5 14]
Please note that the tasks are assumed to arrive dynamically, although the input file makes it looks like static. That is, your system does not know the task until it arrives. You can always assume tha tall tasks arrive and finish their works in [0,200]. There is no floating point number in the program and result, rounding the floating point numbers to integers appropriately if necessary.
Your report should contain:
1. Listing of your source code.
2. Explicit description of how to run your program, and how to add my testing input file into your project.
Turn-in requirements... Reference:
[1] I. Hong, M. Potkonjak, and M. B. Srivastava, "On-line scheduling of hard real-time tasks on variable voltage processor," Proc. Computer-Aided Design (ICCAD), pages 653-656, November 1998.
Attachment:- Scheduling algorithm.rar