代写priority queues、代做C/C++编程语言、代写C/C++、代做avionic留学生

日期：2019-04-12 09:45

Assignment Three

Objectives

Understand how the binomial heap-based priority queue works

Understand how to use priority queues to solve a problem

Admin

Marks 10 marks. Marking is based on the correctness and efficiency of your code. Your

code must be well commented.

Group? This assignment is completed individually.

Due Time 23:59:59pm Wednesday 17 April 2019.

Late Submissions Late submissions will not be accepted!

In this assignment, you will implement a binomial heap-based priority queue and solve a task

scheduling problem using priority queues.

Background

An embedded system is a computer system performing dedicated functions within a larger

mechanical or electrical system. Embedded systems range from portable devices such as

Google Glasses, to large stationary installations like traffic lights, factory controllers, and

complex systems like hybrid vehicles, and avionic. Typically, the software of an embedded

system consists of a set of tasks (threads) with timing constraints. Typical timing constraints

are release times and deadlines. A release time specifies the earliest time a task can start, and

a deadline is the latest time by which a task needs to finish. One major goal of embedded

system design is to find a feasible schedule for the task set such that all the timing constraints

are satisfied.

Task scheduler

We assume that the hardware platform of the target embedded systems is a single processor

with m identical cores, Core1, Core2, …, Corem. The task set V={v1, v2, …, vn} consists of n

independent, non-pre-emptible tasks. A non-pre-emptible task cannot be pre-empted by

another task during its execution, i.e., it runs to completion without being interrupted. Each

task vi (i=1, 2, …, n) has four attributes: a unique task name vi, an execution time ci, a release

time ri, and a deadline di (di>ri). All the execution times, the release times and deadlines are

non-negative integers. You need to design a task scheduler and implement it in C. Your task

scheduler uses EDF (Earliest Deadline First) heuristic to find a feasible schedule for a task set.

A schedule of a task set specifies when each task starts and on which core it is executed. A

feasible schedule is a schedule satisfying all the release time and deadline constraints.

The problem of finding a feasible schedule for this task scheduling problem is NP-complete. It

is widely believed that an NP-complete problem has no polynomial-time algorithm. However,

nobody can prove it.

First, we introduce two definitions: scheduling point and ready task.

A scheduling point is a time point at which a task can be scheduled on a core, In other

words, a scheduling point is either the release time or the completion time of a task.

A task vi (i=1, 2, …, n) is ready at a time t if tri holds.

The EDF scheduling heuristic works as follows:

At each scheduling point ti (ti?ti+1, i=1, 2, …), among all the ready tasks, find a task

with the smallest deadline, and schedule it on an idle core such that its start time is

minimized. Ties are broken arbitrarily.

Since this task scheduling problem is NP-complete, the EDF heuristic is not guaranteed to find

a feasible schedule even if a feasible schedule exists.

Example One

Consider a set S1 of 6 independent tasks whose release times and deadlines are shown in Table

1. The target processor has two identical cores. A feasible schedule of the task set by using

EDF scheduling strategy is shown in Figure 1.

Table 1: A set S1 of 6 tasks with individual release times and deadlines

Task Execution

time

Release time Deadline

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 v1 v3 v5

Core2 v2 v4 v6

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

Figure 1: A feasible schedule for S1

Example Two

Consider a set S2 of 6 independent tasks whose release times and deadlines are shown in Table

2. The target processor has two identical cores. A schedule of the task set by using EDF

scheduling strategy is shown in Figure 2. As we can see, in the schedule, v6 finishes at time 16

and thus misses its deadline. Therefore, the schedule is not feasible. However, a feasible

schedule, as shown in Figure 3, does exist.

Table 2: A set of tasks with individual release times and deadlines

Task Execution

time

Release time Deadline

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 v3 v5

Core2 v2 v4 v6

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

Figure 2: An infeasible schedule constructed by the EDF scheduling strategy

Core1 v1 v3 v6

Core2 v2 v4 v5

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

Figure 3: A feasible schedule for S2

The TaskScheduler function

You need to write a task scheduler function named TaskScheduler. A prototype of

TaskScheduler is shown as follows:

int TaskScheduler(char *file1, char *file2, int m) {};

This function gets a task set from a file named file1, constructs a feasible schedule for the task

set on a processor with m identical cores by using the EDF strategy, and writes the feasible

schedule to file2. If a feasible schedule is found, it returns 1. Otherwise, it returns 0.

Both file1 and file2 are text files. file1 contains a set of independent tasks each of which has a

name, an execution time, a release time and a deadline in that order. Task names, execution

times, release times and the deadlines are a string of digits between 0 and 9. All the release

times are non-negative integers, and all the execution times and the deadlines are natural

numbers. The format of file1 is as follows:

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

Two adjacent attributes (task name, execution time, release time and deadline) are separated

by one or more white space characters or a newline character. A sample file1 is shown here.

For simplicity, you may assume that all the task names in file1 are distinct. Therefore, you

don’t need to check for duplicates.

The TaskScheduler function needs to handle the following possible cases properly when

reading from file1 and writing to file2:

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.

3. The task attributes (task name, execution time, release time and deadline) of file1 do

not follow the formats as shown before. In this case, print “input error when reading

the attribute of the task X” and the program terminates, where X is the name of the

task with an incorrect attribute.

file2 has the following format:

v1 p1 t1 v2 p2 t2 … vn pn tn

where each vi (i=1, 2, …, n) is the task name, pi is the name of the core where vi is scheduled,

and ti is the start time of the task vi in the schedule. In file2, all the tasks must be sorted in

non-decreasing order of start times. A sample file2 is shown here.

Your task scheduler needs to use binomial heap-based priority queues. A priority queue has a

header which stores the number of tasks in the heap and other implementation dependent

information. The data type of a heap header is defined as follows:

typedef struct BinomialHeap{

int size; // count of tasks in the heap

… // you need to add additional fields here

} BinomialHeap;

Each node in the heap stores the priority (key) and the attributes of a task. The attributes of a

task include its name, execution time, release time and deadline. For simplicity, we use an

integer to denote the name of task.

The data type for heap nodes is defined as follows:

typedef struct HeapNode {

int key; // key of this task

int TaskName; // task name

int Etime; // execution time of the task

int Rtime; // release time of the task

int Dline; // deadline of the task

… // you need to add additional fields here

} HeapNode;

Therefore, you also need to implement the following functions of a binomial heap-based

priority queue:

1. void Insert(BinomialHeap *T, int k, int n, int c, int r, int d). This function inserts a new

task into a heap T, where k, n, c, r and d are the key, name, execution time, release

time, and deadline of the task, respectively.

2. HeapNode *RemoveMin(BinomialHeap *T). This function removes a task with the

smallest key from the heap T and returns the node containing the task.

3. int Min(BinomialHeap *T). This function returns the smallest key of all the tasks in the

heap T without modifying the heap T.

The prototypes of all the above-mentioned function and some other basic functions are

included in the template file MyTaskScheduler.c. In addition to the above functions, you

may add your own helper functions and fields (variables) to the file MyTaskScheduler.c.

Note that you must implement a binomial heap-based priority queue. Any other priority

queues are not acceptable.

Time complexity requirement

You need to include the time complexity analysis of each function 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 two binomial heap-based priority queues, one

priority queue with release times as keys and one priority queue with deadlines as keys).

There is no specific requirement on space complexity. However, try your best to make your

program space efficient.

When analysing the time complexity of your task scheduler, you can assume that the time

complexity of each function (insertion, deletion, removeMin and merge) on a binomial heap

is O(log n), where n is the number of tasks in the binomial heap.

How to submit your code?

a. Go to the Assignment page

b. Click on Assignment Specifications

c. Click on Make Submission

d. Submit your MyTaskScheduler.c file that contains all the code.

Plagiarism

This is an individual assignment. Each student will have to develop their own solution without

help from other people. In particular, it is not permitted to exchange code or pseudocode.

You are not allowed to use code developed by persons other than yourself. All work

submitted for assessment must be entirely your own work. We regard unacknowledged

copying of material, in whole or part, as an extremely serious offence. For further information,

see the Course Information.