Figure 3: System Snapshot at a Scheduling Point
h ei; ci; uii
. The task™s WCE (worst case execution) time is denoted as e i , its critical time (the time beyond which the task™s utility is non-positive) is c i , and u i is the task™s TUF.
We adapt the notion of processor load at time t , 1/2 ( t ), as defined in [1]:
1/2 i ( t ) =
Pc k · ci ek( t) c i ¡
; 1/2 J ( t ) = M AX i [ 1/2 i ( t )] :
t
Denoting as mi the memory requirements of the ith task, we calculate memory load of J at time t as:
1 J ( t ) =
Pn i =1 m i ( t ) M
; M = system memory
Denoting as S ( J ) all possible subsequences of tasks in J , 3/4 2 S ( J ) is therefore an ordered subset of tasks representing a schedule [2]. The memory load for a specific task sequence
is therefore: 1 3/4 ( t ) =
Pj 3/4 j i =1 m i ( t ) M where j
3/4 j
is the number of tasks in 3/4 , and mi( t) is the memory requirements, at time t, of the task at position i within the sequence. The schedule 3/4 is considered memory-feasible if 1 3/4 ( t ) ·
1, i.e., there is enough
memory for all tasks in 3/4 at time t .
Furthermore, we define the maximal theoretical utility, U M AX , to be: U M AX =
Pj
J j i =1 u i ( t o ) where: 8
j i ; i 2 f
1 ; : : : ; n g
: tci = t o i That is, the aggregate system-wide utility if all tasks in J were to complete execution at their respective optimal completion time. We define the aggregate utility of 3/4 to be the cumulative utility, at completion time, of its member tasks: U 3/4 =
3/4 j i =1 u i ( t c ) Our objective can then be defined as: MAXIMIZE 3/4 2
Pj
S ( J ) U 3/4 ;
given the constraints: 1/2 ( 3/4 ) ·
1 : Otherwise stated, we wish to find a time- and- memory-feasible subsequence of tasks that would yield the greatest aggregate utility.
1 and 1 ( 3/4 ) ·
The algorithm™s first step is to determine, based on its TUF, each task™s start time such that it completes yielding maximal utility: t c = t opt as depicted in Figure 3(a). The figure illustrates 4 individual tasks with their respective TUFs and remaining execution times. The scheduler™s composite view of the 4 contending tasks is depicted in Figure 3(b). The areas of overlap in the figure illustrate the CPU overload conditions and it can be observed that not all tasks may complete execution while gaining non-zero utility. This step greedily seeks to extract maximal utility values from each task.
Figure 4(a) depicts a set of tasks, corresponding to 187% CPU demand, arranged according to the outlined procedure. This establishes the initial ordering of tasks prior to application of any constraints. PUD (Potential Utility Density) for each task is calculated next. PUD is defined as a task™s utility-Figure 4: Drop-and-Shift
gain at completion, divided by its remaining execution time. This is depicted as the slope of the execution block in Figure 4.
The algorithm™s next step of fidrop-and-shiftfl identifies a time-feasible subset of the ready tasks. We employ a linear scan technique for this phase. Starting at t 0 (now), the scan line sweeps forward along the time axis (Figure 4(b)). It: (1) Does nothing if it only crosses one task; (2) Dropping all others, leaves only the highest PUD task if it crosses an overlapped area of two or more tasks; (3) Shifts left the first task it encounters if it crosses no task, or if a gap along the time line is created as a consequence of dropping a task in a contentious overlap area. The left shift of a task stops at its left neighbor™s boundary, or at t 0 if no left neighbor exists. Figure 4(c) illustrates, at scan conclusion, the final non-overlapping sequence of tasks against the backdrop of the original skyline. Please note that fidroppingfl a task does not imply discarding or terminating the task from the system. It merely denotes its no longer being considered for contention during the limited scope of the scan phase. We then check the remaining task sequence against the memory constraint and successively terminate tasks in ascending PUD order until the remaining subset is memory-feasible. We designate this ordering of tasks as our initial sequence 3/4 i , and its corresponding aggregate utility U i . Algorithm 1 outlines the scan phase.
Shifting the execution time of a task changes its time of completion, tc, and hence its utility yield. As tc is only shifted left, a task may complete execution sooner than expected, but never later, i.e., no deadlines misses. Shifting tc, however, does affect the task™s utility gain at completion time. Left shifting a t c in an interval where the TUF™s time rate of change is positive, yields lower than original utility. For example, should the execution block of the parabolic TUF in Figure 3(a) be shifted left, the task™s utility yield is lowered. The adverse impact of the left shift in this situation is a function of the degree of locality of the TUF™s maxima. In cases of moderate positive TUF time rate of change, the utility loss is likewise moderate. Most TUFs from the UA application domain, however, are non-increasing in time, hence unaffected by a left shift.
Given the infeasibility of exhaustively obtaining the optimal solution, greedy algorithms are often found to produce good approximations. However, this may not always be the case as certain task combinations can be overlooked. Various techniques, however, can be utilized to improve the quality of