mance than the other UA scheduling algorithms. Figure 7 depicts MSA™s comparative performance for the same set of tasks under 20% memory overload.
Furthermore, our experiments indicate that for a given CPU load, MSA performs better for a higher number of tasks, e.g., 50 tasks constituting an aggregate 140% CPU load, versus 20 tasks generating the same load level. The drop-and-shift mechanism is more likely to produce a better initial sequence under these conditions given the increased number of choices.
We believe MSA makes the following contributions:
Explicit Dynamic UA Memory Allocation S In absence of a memory-aware UA-scheduler, tasks are constrained to statically allocate memory up-front to ensure acquiring sufficient storage, else risk a detrimental mid-execution memory allocation failure. Static allocation, though definitive, is inefficient use of memory by large, initially mostly zero-filled object files. Indiscriminate servicing of allocation requests during overload conditions can also lead to disproportionately large areas of memory assigned to low PUD tasks. Taking into account the tasks™ TUFs, their current memory footprint, CPU demands, and allocation requests, MSA makes more sophisticated memory-aware scheduling decisions. This offers the UA application programmer the flexibility of explicit dynamic memory allocation with the assurance that a request will be serviced if it results in higher overall utility accrual.
Scalability S As a soft real-time UA scheduling algorithm, MSA degrades gracefully under increasing CPU load, thereby allowing the system to scale up. Making more efficient use of memory, MSA is well-suited for use in memory-constrained UA-governed embedded systems.
Pseudo-Greedy Approach S Whereas nearly all other UA-schedulers adopt a strictly greedy sequencing strategy, MSA™s use of the 0/1 knapsack techniques introduces a partial combinatoric element into an otherwise greedy approach.
[1] G. C. Buttazzo. Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications. Kluwer Academic Publishers, 1997.
[2] K. Chen and P. Muhlethaler. A scheduling algorithm for
tasks described by time value function. Journal of
Real-Time Systems, 10(3):293Œ312, 1996.
[3] R. K. Clark. Scheduling Dependent Real-Time Activities. PhD thesis, CMU, 1990. CMU-CS-90-155.
[4] E. D. Jensen. Async. decentralized rt comp. sys. In Real-Time Computing, Proc. of the NATO Advanced Study Inst. Verlag, Oct 1992.
[5] E. D. Jensen and B. Ravindran. Guest editor™s intro. to special section on async. rt distrib. sys. In Proc. of The IEEE Trans. on Comp., pages 881Œ882, Aug. 2002.
[6] C. D. Locke. Best-Effort Decision Making for Real-Time Scheduling. PhD thesis, CMU, 1986. CMU-CS-86-134.
[7] D. Maynard and et al. An example real-time command, control, and battle mgmt. appl. for alpha. Technical report, Dec 1988. Archons Proj. Tech Rprt 88121.
[8] S. Sahni. Approx. alg. for the 0/1 knapsack prob. Journal of the ACM (JACM), 22(1):115Œ124, 1975. [9] M. Singhal and N. G. Shivaratri. Advanced concepts in operating systems. McGraw-Hill Inc., 1994.
[10] P. Wilson, M. Johnstone, M. Neely, and D. Boles. Dynamic storage allocation: A survey and critical review. In Proc. Int. Wrkshp. on Mem. Mgmt., 1995.
100
Utility
Ratio
75
50
25
0
30
35
40
L100
125
150
175
40 Available
Memory
H%
H% L
CPU Load
45
50
Figure 5: Cumulative Performance Degradation
Figure 6: MSA Performance
ing CPU and memory load. Note that performance degradation begins as CPU load approaches 100%, as expected. Degradation under the same scheduler and CPU load profile, however, begins near 50% memory load in this case. The observed overhead is due to internal and external fragmentation of memory. The buddy system policy for memory allocation is often used in real-time systems due to its high performance [10]. Such fragmentation, however, is inevitable regardless of the allocation policy. External fragmentation can be alleviated by deferred heap compaction when CPU load drops below 100%.
Figure 6(a) illustrates the comparative performance of MSA and LBESA [6], the only other UA scheduling algorithm capable of handling arbitrary TUFs. Performance of MSA is compared to DASA [3], and CMA [2] using only rectangular TUFs in Figure 6(b). DASA, the overall highest performing UA scheduling algorithm is restricted to rectangular TUFs (hard deadlines) only. No memory constraints were imposed on the system for the performance depicted in Figure 6. During memory overload, however, MSA exhibits higher perfor-
Figure 7: MSA Performance (Memory Constraints)