A REAL-TIME SCHEDULING ALGORITHM FOR TASKS WITH RESOURCE CONTENTION ON A MULTIPROCESSOR

Abstract

Our scheduling algorithm is based on a general model with timing and resource constraints which permits OR requests. In order to keep run-time costs low, we propose an algorithm that does not search the whole search space. This paper defines two measures, survivability and impact, for scheduling tasks conflicted for some resources. The survivability is a metric to show how urgent a task is, and how constrained it is by its resources. The impact of a resource for a task measures how much other tasks are influenced by the allocation of the resource to the task. Our scheduling algorithm uses the survivability to schedule tasks on multiple processors. After a task is picked out to be run in a time slice using the survivability, the least impact resources are allocated from several alternative resources.