Job Scheduling Problem Homework Help, Assignment Help, Online Tutor, Tutoring

Submit Assignment

* *

Payment Online Assignment Help

Trigonometry Homework

Homework Help

sfsf

Job Scheduling Problem

Consider the problem of scheduling the execution of a set of tasks on a multiprocessor computing system that has a set of identical processors. Let P₁, P₂, …., P_n denote the n identical processors in a multiprocessor computing system. We assume that the execution of a task occupies one and only one processor. Moreover, since the processors are identical, a task can be executed on any one of the processors. Let (T_i) denote the execution time of task T_i, that is, the amount of time it takes to execute Ti on a processor. There is also a partial ordering relation ≤ specified over, such that for T_i ≠ T_j, T_i ≤ T_j if and only if the execution of task T_j cannot begin until the execution of task T_i has been completed. A partially ordered set in which the execution time of each task, is written next to the name of the task. An obvious interpretation can be given to our model of a set of tasks. Consider the tasks T₁, T₂, …., T_r to be subprograms of a larger program. Then T_i ≤ T_j might mean that subprogram T_j uses some of the data generated by subprogram T_i, so that execution of T_j must await the completion of T_i. For example, if a computer system is used on a space mission, task T_i might be a subprogram that estimates the total fuel consumption for midcourse adjustment. Clearly, we should complete T_i before executing T_j.

By scheduling a set of tasks on a multiprocessor computing system, we mean to specify for each task, T_j both the time interval within which it will be executed and the processor P_k on which execution will take place. An explicit generality, we assume that execution of the set begins at time t = 0). An explicit way to describe a schedule is a timing diagram. For example, the timing diagram of a schedule for execution of the set of tasks, on a three-processor computing system, Ø₁, Ø₂, Ø₃, Ø₄ denote periods within which a processor is left idle. For a given schedule, an idle period of a processor is defined to be a time interval within which the processors, and (Ø₁), (Ø₂), … to denote the lengths of the idle periods. Notice that in a given schedule a processor might be left idle either because there is no executable task at that time or because it is an intentional choice. Clearly, it is never necessary nor beneficial in a given schedule to leave all processors idle at the same time. On the other hand, it might be beneficial to leave some of the processors idle even though there are tasks that are executable at that time.