Real-time scheduling of multiple segment tasks

Kamhing Ho, James H. Rice, Jaideep Srivastava

Research output: Contribution to journalConference articlepeer-review

1 Scopus citations


The authors study the problem of on-line non-preemptive scheduling of multiple segment real-time tasks. Task segments alternate between using CPU and I/O resources. A task model is proposed which encompasses a wider class of tasks than models proposed earlier. Total slack available to a task is modeled as a new kind of virtual resource which is spent while waiting in queues for service by physical resources. Instead of developing new scheduling algorithms, the authors develop a class of slack distribution policies which use varying degrees of information about task structure and device utilization to budget task slack. Slack distribution policies are shown to improve the performance of all scheduling algorithms studied. Two key observations are: (1) slack distribution is helpful beyond a certain threshold of task arrival rate, and (2) algorithms which normally perform poorly are helped to a greater degree by slack distribution. A study of various scheduling algorithms for a constant value function reveals that all of them favor tasks with a large number of small segments to tasks with a small number of large segments. It is shown that the Moore ordering algorithm is not optimal for multiple segment tasks.

Original languageEnglish (US)
Pages (from-to)680-686
Number of pages7
JournalProceedings - IEEE Computer Society's International Computer Software & Applications Conference
StatePublished - Dec 1 1990
EventProceedings of the 14th Annual International Computer Software and Applications Conference - COMPSAC 90 - Chicago, IL, USA
Duration: Oct 29 1990Nov 2 1990


Dive into the research topics of 'Real-time scheduling of multiple segment tasks'. Together they form a unique fingerprint.

Cite this