7.3: Adding an algorithm
- Last updated
- Jul 18, 2022
- Save as PDF
( \newcommand{\kernel}{\mathrm{null}\,}\)
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.
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.
- On the digraph or priority list, circle all tasks that are ready, meaning that all pre-requisite tasks have been completed.
- 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.
- 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.
- Repeat until all tasks have been scheduled.
Using our digraph from above, schedule it using the priority list below:
T1,T3,T4,T5,T6,T7,T8,T2,T9
Solution
Time 0: Mark ready tasks
Priority list: (T1),(T3),(T4),(T5),T6,T7,T8,T2,T9
We assign the first task, T1 to the first processor, P1, and the second ready task, T3, to the second processor. Making those assignments, we mark those tasks as in progress:
Priority list: (T1),(T3),(T4),(T5),T6,T7,T8,T2,T9
Schedule up to here:
We jump to the time when the next task completes, which is at time 2.
Time 2: Both processors complete their tasks. We mark those tasks as complete. With Task 1 complete, Task 2 becomes ready:
Priority list: (T1),(T3),(T4),(T5),T6,T7,T8,(T2),T9
We assign the next ready task on the list, T4 to P1, and T5 to P2.
Priority list: (T1),(T3),(T4),(T5),T6,T7,T8,(T2),T9
Time 3: Processor 1 has completed T4. Completing T4 does not make any other tasks ready (note that all the rest require that T2 be completed first).
Priority list: (T1),(T3),(T4),(T5),T6,T7,T8,(T2),T9
Since the next three tasks are not yet ready, we assign the next ready task, T2 to P1
Priority list: (T1),(T3),(T4),(T5),T6,T7,T8,(T2),T9
Time 3.5: Processor 1 has completed T2. Completing T2 causes T6 and T7 to become ready. We assign T6 to P1.
Priority list: (T1),(T3),(T4),(T5),(T6),(T7),T8,(T2),T9
Time 4: Both processors complete their tasks. The completion of T5 allows T8 to become ready. We assign T7 to P1 and T8 to P2.
Priority list: (T1),(T3),(T4),(T5),(T6),(T7),(T8),(T2),T9
Time 4.5: Both processors complete their tasks. T9 becomes ready, and is assigned to P1. There is no ready task for P2 to work on, so P2 idles.
Priority list: (T1),(T3),(T4),(T5),(T6),(T7),(T8),(T2),(T9)
With the last task completed, we have a completed schedule, with finishing time 5.5 days.
Using the digraph below, create a schedule using the priority list:
T1,T2,T3,T4,T5,T6,T7,T8,T9
- Answer
-
Time 0: Tasks 1, 4, and 7 are ready. Assign Tasks 1 and 4
Time 9: Task 4 completes. Only task 7 is ready; assign task 7
Time 10: Task 1 completes. Task 2 now ready. Assign task 2
Time 17: Task 2 completes. Nothing is ready. Processor 1 idles
Time 22: Task 7 completes. Tasks 5 and 8 are ready. Assign tasks 5 and 8
Time 26: Task 8 completes. Task 9 is ready. Assign task 9
Time 27: Task 5 completes. Tasks 3 and 6 are ready. Assign task 3
Time 31: Task 3 completes. Assign task 6
Time 35: Everything is done. Finishing time is 35 for this schedule.
It is important to note that the list processing algorithm itself does not influence the resulting schedule – the schedule is completely determined by the priority list followed. The list processing, while do-able by hand, could just as easily be executed by a computer. The interesting part of scheduling, then, is how to choose a priority list that will create the best possible schedule.
