Rights Creative Commons: Attribution 3.0 Hong Kong License This is a pre-published version Performance Guarantee for EDF under Overload

Abstract. Earliest deadline rst (edf) is a widely used algorithm for online deadline scheduling. It has been known for long that edf is optimal for scheduling an underloaded, single-processor system; recent results on the extra-resource anal-ysis of edf further revealed that edf when using moderately faster processors can achieve optimal performance in the underloaded, multi-processor setting. This pa-per initiates the extra-resource analysis of edf for overloaded systems, showing that edf supplemented with a simple form of admission control can provide a similar performance guarantee in both the single and multi-processor settings. Key words: online algorithms, extra-resource analysis, rm deadline scheduling, earli-est deadline rst.