Browse Prior Art Database

PREEMPTIVE SCHEDULING OF PERIODIC, REAL-TIME TASKS

IP.com Disclosure Number: IPCOM000128157D
Original Publication Date: 1979-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 16 page(s) / 39K

Publishing Venue

Software Patent Institute

Related People

Joseph Y.-T. Leung: AUTHOR [+4]

Abstract

The problem of preemptively scheduling a set of periodic, real-time tasks is studied. The Slack-Time Algorithm which, at each instant of time, schedules that active task with the smallest slack-time is shown to be optimal for 1 processor. Algorithms are given to determine if a set of periodic, real-time tasks is feasible on 1 processor. The optimality of the Slack-Time Algorithm for m > I processors is also discussed.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 12% of the total text.

Page 1 of 16

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

PREEMPTIVE SCHEDULING OF PERIODIC, REAL-TIME TASKS*

Joseph Y.-T. Leung and M. L. Merrill

Department of Electrical Engineering and Computer Science Northwestern University No. 79- 06-FC-02 July, 1979

*This research was supported in part by the National Science Foundation under Grant MCS-79- 04898.

41,

Abstract

The problem of preemptively scheduling a set of periodic, real-time tasks is studied. The Slack- Time Algorithm which, at each instant of time, schedules that active task with the smallest slack- time is shown to be optimal for 1 processor. Algorithms are given to determine if a set of periodic, real-time tasks is feasible on 1 processor. The optimality of the Slack-Time Algorithm for m > I processors is also discussed.

Keywords and Phrases:

periodic real-time task., dynamic-priority preemptive scheduling, static-priority preemptive scheduling, optimal scheduling algorithm, deadline, slack-time.

1. Introduction

Computer systems are now being used for the control of a wide variety of r eal-time processes that arise in various fields of engineering and physical science. In many of these real~time applications, the computer is required to execute programs in response to periodic external signals and to guarantee that each such program be completely processed before the occurrence of a subsequent signal. Sequencing tasks in such an environment raises a number of challenging theoretical questions whose solutions have much practical significance. In this paper we shall address these issues and attempt to provide solutions for them.

We begin by characterizing a task in a real-time environment. A real-time task may be defined as a computation that must be executed peri-odically, with each computation of the task having a fixed deadline for completion. The deadline of a given computation can be no later than the time of the request for executing the next computation of the task. Each computation of the task requires the same amount of execution time and is requested periodically with a fixed peri,od. We define a real-time task system (or task system for short) as a system consisting of a set of n independent real-time tasks.

Northwestern University Page 1 Dec 31, 1979

Page 2 of 16

PREEMPTIVE SCHEDULING OF PERIODIC, REAL-TIME TASKS

A task system R will be-denoted by

(Equation Omitted)

where each

(Equation Omitted)

is a real-time task consisting of a periodic sequence of requests for execution of a computation such that (1) execution of the kth

(Equation Omitted)

computation is requested at time

(Equation Omitted)

is the period of

(Equation Omitted)

the kth computation requires ei units of execution time, and (3) the kth computation must be completed no later than the deadline

(Equation Omitted)

>The scheduling discipline we shall be concerned with is dynamic-priority preemptive scheduling, in which tasks with higher priorities always preempt tasks with lower ones. However...