A scheduling algorithm and utilization bound for uniform multiprocessors

Abstract

We present a new scheduling algorithm, U-LLREF, which is the first scheduling algorithmfor that is optimal for uniform multiprocessors. It is an extension of the LLREF algorithmfor identical multiprocessors. These algorithms attempt to emulate a fluid scheduling model,which executes all periodic tasks at a constant rate equal to their utilization. Like the LLREFalgorithm, U-LLREF generates schedules based on the fairness notion. It uses the Time andLocal execution time (TL) plane to describe fluid schedules and ensures the amount of workcompleted by each task remains close to the corresponding amount of work in the fluidschedule by monitoring task progress within TL planes.