Page 347 - DSP Integrated Circuits

332 Chapter 7 DSP System Design

The list of sorted processes is searched repeatedly for a process that can be
assigned to the first resource. Such a process must have a lifetime that does not
overlap the lifetimes of processes already assigned to this resource. The search for
such processes is continued until we reach the end of the list. Then all processes
that can be assigned to this resource have been assigned. This procedure for
assigning processes is repeated for a new resource until all processes in the list
have been assigned to a resource. The left-edge algorithm is based on the heuristic
rule that processes with longer lifetimes should be assigned first. The left-edge
algorithm is described in Box 7.7.

1. Sort the processes into a list according to their starting times. Begin
the list with the process having the longest lifetime if the schedule is
cyclic. Processes with the same starting time are sorted with the
longest lifetime first. Let i = 1.
2. Assign the first process in the list to a free resource i, determine its
finishing time, and remove it from the list.
3. Search the list for the first process that has
(a) a starting time equal to, or later than, the finishing time for the
previously assigned process; and
(b)a finishing time that is no later than the starting time for the first
process selected in step 2.
4. If the search in step 3 fails then
if there are processes left in the list then
let i <r- i + 1 and repeat from step 2
else
Stop
end if;
else
assign the process to resource i, determine its finishing time,
remove it from the list, and repeat from step 3.
end if;

Box 7.7 The left-edge algorithm

EXAMPLE 7.10

Figure 7.69 shows a schedule for a set of similar processes that shall be assigned
to a set of homogeneous resources.
The first step is to sort the processes according to their starting time. The list
of sorted processes is illustrated in Figure 7.70. To the first resource we begin by
first assigning process A. The next process that can be assigned to this resource
must have a starting time later than 5 and a finishing time earlier than 0 (15).
Process B is the first such process in the list. No more processes can be assigned to
the first resource.
To the second resource we assign process E. The next process that can be
assigned to this resource must have a starting time later than 9 and a finishing