Algorithm 1: Linear Scan (Drop-and-Shift)
Input: 3/4 M AX : Sequence of all tasks in J yielding UMAX sorted by ts
Output: 3/4 out : Time-feasible task subsequence
CurrentT ask á
J i 2
J j
Algorithm 2: The MSA algorithm
Input: J : Unordered set of all tasks in the system
Output: 3/4 f inal : Task sequence(schedule) to be dispatched in order
begin
t sj = t sM IN
while CurrentT ask = ;
do
N ext á
( CurrentT ask !
N ext )
Initialization: 3/4 f inal = ; 1 8
if N ext = ;
then break
if CurrentT ask:t c > N ext:t s then
j i 2
J : Determine t opt
2 Sort Jbyts(suchthattc= topt):
3/4 M AX = j i 2
J ; 8
( j > i ) : t si ·
t sj
/* overlap */
if CurrentT ask:P ersistent then
/* Persistent tasks always stay */
drop N ext continue
if CurrentT ask:P U D > N ext:P U D then drop N ext
else
/* drop & shift */
± t = N ext:t s ¡
CurrentT ask:t s
drop CurrentT ask
N ext:t s = N ext:t s ¡
3 Sort J by PUD:
3/4 PUD = ji 2
J ; 8
( j > i ) : P U D i ¸
P U D j
4 for (all p -combinations, p = 0 ; 1 ; : : : ; k ) do
Designate the p tasks persistent: 8
i 2
p : ( j i 2
U M AX ) á
persistent
3/4 out = LinearScan( U M AX )
while 1 3/4out > 1 do
Terminate the lowest PUD task: 3/4 out = 3/4 out ¡ f
j z g
:
± t
8 j i 2
3/4 out : P U D ji ¸
P U D jz
N ext:t c = N ext:t c ¡
± t
CurrentT ask á
N ext
3/4 f inal = M AX [ 3/4 out ; 3/4 f inal ]
else end
/* No overlap, shift */
± t = N ext:t s ¡
CurrentT ask:t c
N ext:t s = N ext:t s ¡
± t
N ext:t c = N ext:t c ¡
± t
CurrentT ask á
(step 1 of Algorithm 2) is therefore O ( n ) in time. Steps 2 and
3 of MSA are to sort by ts and PUD respectively. Each sort
is done in O ( n log n ) complexity. There are ( n
p ) combinations
. Step 4 of MSA is therefore executed
N ext
the initial greedy solution. One such method is outlined in [8]
for the classic 0/1 knapsack problem where an initial greedy
solution is evaluated for possible improvements using a partial combinatoric technique. For each p -combination of items,
( k
p ) ; p 2 f
0 ; : : : ; k g
; ( k ·
n ), the combination is indiscriminately placed in the knapsack (if it fits), while the remaining
for each p 2 f
0 ; 1 ; : : : ; k g
Pk p =0 (
n p ) times. The summation is dominated by the term ( n k ) with a time complexity of O ( kn k ). The for loop of step 4, therefore, executes O ( kn k ) times. The LinearScan step inside the for loop executes in O ( n ) time as it moves across the sorted list of tasks. The composite complexity of step 4 is thus O ( kn k + 1 ). As step 4 dominates the entire algorithm, the overall time complexity of MSA is O ( kn k + 1 ).
( n ¡
p ) items are successively fit-tested for inclusion, in descending profit density order. Compared to a greedy placement strategy, the solution quality generally improves with increasing k as more sets of combinations are iteratively evaluated. As k approaches n , this method becomes an exhaustive search, unsuitable for our purposes of on-line scheduling. It is, however, demonstrated in [8] that improved results can be obtained even for small k . We adapt this technique for use in our schedule construction. It is shown in the next section that MSA has a computational complexity of O ( kn k + 1 ). We limit k to 3 in our adaptation as an O ( n 4 ) algorithm approaches the limit of suitability for on-line scheduling, even for small n .
There are
Pk p =0 ( n p ) p -combinations for any k . For each instance of the p -combinations, we designate the corresponding p member tasks as fipersistent.fl The p -combination is then checked for time and memory feasibility and rejected if found infeasible. We then proceed normally with the scan phase of the algorithm. A persistent task, in this context, is defined to be one that always survives contention with a non-persistent task (regardless of PUD) during the scan phase. Contention amongst persistent tasks, should they arise, are resolved greed-ily based on PUD. For each of the 1 through k -permutations, the algorithm proceeds to produce a schedule, taking task persistency into account. Of the resulting set of schedules, the one with the highest aggregate utility is selected as the final schedule. MSA™s high-level pseudo code is outlined in Algorithm 2.
The TUF of a task provides a closed-form description of its utility as a function of time. Gained utility at completion time, as well as t opt , is derived in constant time for each task. The initial step of the algorithm, determination of t opt for each task
The scheduler invariably incurs some overhead as it requires CPU cycles to construct a schedule, update the appropriate system level data structures, perform context switches, etc. The overhead is insignificant if the tasks™ timing constraints are orders of magnitude higher than the scheduler™s time requirements. However, under relatively tight timing constraints and CPU overload conditions with no cycles to spare, the adverse effect of the scheduler overhead is more pronounced.
MSA calculates the system load, 1/2 , at the time of invocation and can dynamically adjust its overhead accordingly. Given its O ( kn k + 1 ) time complexity, the algorithm™s overhead can be adjusted with k . We limit k to 3 so that an upper bound of O ( n 4 ) is imposed on the scheduler. Also, a lower bound of O ( n log n ) (dominated by the sort steps) can be achieved at k = 0. As k ranges in value between 0 and 3, the quality of the resulting schedule is affected.
MSA was implemented over a middleware scheduling framework designed to accommodate UA schedulers in a standard POSIX real-time environmentS in this case, over QNX RTOS. Furthermore, we utilized an instrumented kernel to measure performance and scheduler overhead. The instrumented kernel generates a post-processed trace delineating kernel activity for a specific time period. As such, thread execution times were measured at the same level of precision seen by the kernel.
Figure 5 illustrates the system-wide performance degradation (measured in terms of accrued utility ratio) with increas-