# 7.3: Adding an algorithm

- Page ID
- 34213

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:

\(\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}\)

**Solution**

**Time 0**: Mark ready tasks

Priority list: \(({\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}\)

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

Priority list: \(\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}\)

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: \(\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}\)

We assign the next ready task on the list, \(\mathrm{T}_{4}\) to \(\mathrm{P}_{1}\), and \(\mathrm{T}_{5}\) to \(\mathrm{P}_{2}\).

Priority list: \(\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}\)

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

Priority list: \(\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}\)

Since the next three tasks are not yet ready, we assign the next ready task, \(\mathrm{T}_{2}\) to \(\mathrm{P}_{1}\)

Priority list: \(\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}\)

**Time 3.5**: Processor 1 has completed \(\mathrm{T}_{2}\). Completing \(\mathrm{T}_{2}\) causes \(\mathrm{T}_{6}\) and \(\mathrm{T}_{7}\) to become ready. We assign \(\mathrm{T}_{6}\) to \(\mathrm{P}_{1}\).

Priority list: \(\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}\)

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

Priority list: \(\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}\)

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

Priority list: \(\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})}\)

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:

\(\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}\)

**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.