Department of Information Technology

Abstract 2007-06-12

Guan Nan and Wang Yi

Compared with preemptive scheduling, nonpreemptive scheduling has
received considerable less attention in the research community.
However, nonpreemtive scheduling is a topic of importance for several
reasons: (1) non-preemptive scheduling is widely used in industrial
embedded systems where tasks are often light-weight threads;
preemption may create too much overheads for context switch, (2) for
critical systems, the overhead of preemptive scheduling algorithms is
difficult to predict due to inter-task interference caused by caching
and pipelining, and (3) for multicore/multiprocessor platforms,
it seems that non-preemptive scheduling is a much more appealing technique
than for single-core platforms. Recently we have conducted simulation
experiments on the performance in terms of acceptance ratio, of
different scheduling policies on multiprocessors. To our surprise, the
performance of non-preemptive scheduling is very close to, or even
better than preemptive scheduling for a wide range of tasksets even
without considering the context switch overheads. This leads us to a
recent work on schedulability analysis for nonpreemptive scheduling on
multiprocessor platforms. Based on Baruah's work,
we have proposed a new schedulability test bound for non-preemtive scheduling.
Our test condition overcomes the drawback in Baruah's test which rejects a taskset
only if it contains a task whose computation time is larger than the minimal deadline of
the taskset. Experiments also show that our test condition has a better
performance in terms of acceptance ratio comparing with previous work
e.g. Baruah's test condition.

Updated  2008-06-02 17:03:49 by Jonathan Mörndal.