Example - Multiprocessor Scheduling with precedence

The feasible interval (release Time and Deadline) of each task in the precedence graph is given next to its name. The execution time for T1,T2....T7 is respectively 2, 2, 3, 1, 1, 1, 3.

The priority is in the following order, T1>T2>T3...>T7 ( T1 being the highest priority and T7 being the Lowest Priority)

a) What is the minimum number of processors required for feasibility?

Answer
Single Processor

At time 0, T2 and T6 are ready, Since T2 is an independant task it can scheduled.

At time 1, T2 is running and T3,T5 and T6 are ready (but all are dependant tasks)

At time 2, T2 completes, T1, T3,T5 and T6 are ready (T1 is starting because of high priority)

At time 3, T1 is running,

At time 4, T1 completes, T3, T4, T5 and T6 are ready.. Here T3 is ready to execute because of high priority and as well it satisfies the precedence constraint.

At time 6, T7 is also ready along with T4, T5 and T6.

Except T5 all the tasks meets their deadlines.

So, having one processor is not a feasible schedule..

Let us try for two processors

Two Processors

In the above schedule, all the tasks meets their deadline (so this is a feasible schedule)

Ans: The minimum number of processors required by the above task set is 2.