  Scheduling of constrained deadline sporadic task systems on multiprocessor
platforms is an area which has received much attention in the recent past. It
is widely believed that finding an optimal scheduler is hard, and therefore
most studies have focused on developing algorithms with good processor
utilization bounds. These algorithms can be broadly classified into two
categories: partitioned scheduling in which tasks are statically assigned to
individual processors, and global scheduling in which each task is allowed to
execute on any processor in the platform. In this paper we consider a third,
more general, approach called cluster-based scheduling. In this approach each
task is statically assigned to a processor cluster, tasks in each cluster are
globally scheduled among themselves, and clusters in turn are scheduled on the
multiprocessor platform. We develop techniques to support such cluster-based
scheduling algorithms, and also consider properties that minimize total
processor utilization of individual clusters. In the last part of this paper,
we develop new virtual cluster-based scheduling algorithms. For implicit
deadline sporadic task systems, we develop an optimal scheduling algorithm that
is neither Pfair nor ERfair. We also show that the processor utilization bound
of US-EDF{m/(2m-1)} can be improved by using virtual clustering. Since neither
partitioned nor global strategies dominate over the other, cluster-based
scheduling is a natural direction for research towards achieving improved
processor utilization bounds.
