Scheduling Cont.

Adding an algorithm

Up until now, we have been creating schedules by guess-and-check, which works well enough for small schedules, but would not work well with dozens or hundreds of tasks. To create a more procedural approach, we might begin by somehow creating a priority list. Once we have a priority list, we can begin scheduling using that list and the list processing algorithm.

priority list

A priority list is a list of tasks given in the order in which we desire them to be completed.

 

The List Processing Algorithm turns a priority list into a schedule.

How To: List Processing Algorithm

1. On the digraph or priority list, circle all tasks that are ready, meaning that all prerequisite tasks have been completed.
2. Assign to each available processor, in order, the first ready task. Mark the task as in progress, perhaps by putting a single line through the task.
3. Move forward in time until a task is completed. Mark the task as completed, perhaps by crossing out the task. If any new tasks become ready, mark them as such.
4. Repeat until all tasks have been scheduled.

 

Using our complete digraph for the car conversion we found earlier, let’s schedule the tasks using the priority list below:

[latex]\mathrm{T}_{1}, \mathrm{T}_{3}, \mathrm{T}_{4}, \mathrm{T}_{5}, \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, \mathrm{T}_{2}, \mathrm{T}_{9}[/latex]

Time 0: Mark ready tasks.

Priority list: [latex]({\mathrm{T}_{1}}), (\mathrm{T}_{3}), (\mathrm{T}_{4}), (\mathrm{T}_{5}), \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, \mathrm{T}_{2}, \mathrm{T}_{9}[/latex]

We assign the first task, [latex]\mathrm{T}_{1}[/latex] to the first processor, [latex]\mathrm{P}_{1}[/latex], and the second ready task, [latex]\mathrm{T}_{3}[/latex], to the second processor. Making those assignments, we mark those tasks as in progress:

Priority list: [latex]\cancel{(\mathrm{T}_{1})}, \cancel{(\mathrm{T}_{3})}, (\mathrm{T}_{4}), (\mathrm{T}_{5}), \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, \mathrm{T}_{2}, \mathrm{T}_{9}[/latex]

Schedule up to here:

 

We jump to the time when the next task completes, which is at time [latex]2[/latex].

Time 2: Both processors complete their tasks. We mark those tasks as complete. With Task [latex]1[/latex] complete, Task [latex]2[/latex] becomes ready:

Priority list: [latex]\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, (\mathrm{T}_{4}), (\mathrm{T}_{5}), \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, (\mathrm{T}_{2}), \mathrm{T}_{9}[/latex]

We assign the next ready task on the list, [latex]\mathrm{T}_{4}[/latex] to [latex]\mathrm{P}_{1}[/latex], and [latex]\mathrm{T}_{5}[/latex] to [latex]\mathrm{P}_{2}[/latex].

Priority list: [latex]\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \cancel{(\mathrm{T}_{4})}, \cancel{(\mathrm{T}_{5})}, \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, (\mathrm{T}_{2}), \mathrm{T}_{9}[/latex]

 

Time 3: Processor 1 has completed [latex]\mathrm{T}_{4}[/latex]. Completing [latex]\mathrm{T}_{4}[/latex] does not make any other tasks ready (note that all the rest require that [latex]\mathrm{T}_{2}[/latex] be completed first).

Priority list: [latex]\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \xcancel{(\mathrm{T}_{4})}, \cancel{(\mathrm{T}_{5})}, \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, (\mathrm{T}_{2}), \mathrm{T}_{9}[/latex]

Since the next three tasks are not yet ready, we assign the next ready task, [latex]\mathrm{T}_{2}[/latex] to [latex]\mathrm{P}_{1}[/latex].

Priority list: [latex]\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \xcancel{(\mathrm{T}_{4})}, \xcancel{(\mathrm{T}_{5})}, \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, \cancel{(\mathrm{T}_{2})}, \mathrm{T}_{9}[/latex]

 

Time 3.5: Processor [latex]1[/latex] has completed [latex]\mathrm{T}_{2}[/latex]. Completing [latex]\mathrm{T}_{2}[/latex] causes [latex]\mathrm{T}_{6}[/latex] and [latex]\mathrm{T}_{7}[/latex] to become ready. We assign [latex]\mathrm{T}_{6}[/latex] to [latex]\mathrm{P}_{1}[/latex].

Priority list: [latex]\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \xcancel{(\mathrm{T}_{4})}, \xcancel{(\mathrm{T}_{5})}, \cancel{(\mathrm{T}_{6})}, (\mathrm{T}_{7}), \mathrm{T}_{8}, \xcancel{(\mathrm{T}_{2})}, \mathrm{T}_{9}[/latex]

 

Time 4: Both processors complete their tasks. The completion of [latex]\mathrm{T}_{5}[/latex] allows [latex]\mathrm{T}_{8}[/latex] to become ready. We assign [latex]\mathrm{T}_{7}[/latex] to [latex]\mathrm{P}_{1}[/latex] and [latex]\mathrm{T}_{8}[/latex] to [latex]\mathrm{P}_{2}[/latex].

Priority list: [latex]\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \xcancel{(\mathrm{T}_{4})}, \xcancel{(\mathrm{T}_{5})}, \xcancel{(\mathrm{T}_{6})}, \cancel{(\mathrm{T}_{7})}, \cancel{(\mathrm{T}_{8})}, \xcancel{(\mathrm{T}_{2})}, \mathrm{T}_{9}[/latex]

 

Time 4.5: Both processors complete their tasks. [latex]\mathrm{T}_{9}[/latex] becomes ready, and is assigned to [latex]\mathrm{P}_{1}[/latex]. There is no ready task for [latex]\mathrm{P}_{2}[/latex] to work on, so [latex]\mathrm{P}_{2}[/latex] idles.

Priority list: [latex]\xcancel{(\mathrm{T}_{1})}, \xcancel{(\mathrm{T}_{3})}, \xcancel{(\mathrm{T}_{4})}, \xcancel{(\mathrm{T}_{5})}, \xcancel{(\mathrm{T}_{6})}, \xcancel{(\mathrm{T}_{7})}, \xcancel{(\mathrm{T}_{8})}, \xcancel{(\mathrm{T}_{2})}, \cancel{(\mathrm{T}_{9})}[/latex]

 

With the last task completed, we have a completed schedule, with finishing time [latex]5.5[/latex] days.

Using the digraph below, create a schedule using the priority list with two processors:

[latex]\mathrm{T}_{1}, \mathrm{T}_{2}, \mathrm{T}_{3}, \mathrm{T}_{4}, \mathrm{T}_{5}, \mathrm{T}_{6}, \mathrm{T}_{7}, \mathrm{T}_{8}, \mathrm{T}_{9}[/latex]

Show Solution

Time [latex]0[/latex]: Tasks [latex]1, 4,[/latex] and [latex]7[/latex] are ready. Assign Tasks [latex]1[/latex] and [latex]4[/latex].

Time [latex]9[/latex]: Task [latex]4[/latex] completes. Only task [latex]7[/latex] is ready; assign task [latex]7[/latex].

Time [latex]10[/latex]: Task [latex]1[/latex] completes. Task [latex]2[/latex] now ready. Assign task [latex]2[/latex].

Time [latex]17[/latex]: Task [latex]2[/latex] completes. Nothing is ready. Processor [latex]1[/latex] idles.

Time [latex]22[/latex]: Task [latex]7[/latex] completes. Tasks [latex]5[/latex] and [latex]8[/latex] are ready. Assign tasks [latex]5[/latex] and [latex]8[/latex].

Time [latex]26[/latex]: Task [latex]8[/latex] completes. Task [latex]9[/latex] is ready. Assign task [latex]9[/latex].

Time [latex]27[/latex]: Task [latex]5[/latex] completes. Tasks [latex]3[/latex] and [latex]6[/latex] are ready. Assign task [latex]3[/latex].

Time [latex]31[/latex]: Task [latex]3[/latex] completes. Assign task [latex]6[/latex].

Time [latex]35[/latex]: Everything is done. Finishing time is [latex]35[/latex] for this schedule.

There are other algorithms that can be used to create the priority list including, the decreasing time algorithm, the critical path algorithm, and the backflow algorithm. We will explore these algorithms in the Apply It section.