SKEDSOFT

PERIODIC TASK MODEL: The periodic task model is a well-known deterministic workload model [LiLa]. With its various extensions, the model characterizes accurately many traditional hard real-time applications, such as digital control, real-time monitoring, and constant bit-rate voice/video transmission. Many scheduling algorithms based on this model have good performance and well-understood behavior. There are now methods and tools to support the design, analysis, and validation of real-time systems that can be accurately characterized by the model. For these reasons, we want to know it well and be able to use it proficiently.

Periods, Execution Times, and Phases of Periodic Tasks: In the periodic task model, each computation or data transmission that is executed repeatly at regular or semiregular time intervals in order to provide a function of the system on a continuing basis is modeled as a period task. Specifically, each periodic task, denoted by Ti , is a sequence of jobs. The period pi of the periodic task Ti is the minimum length of all time intervals between release times of consecutive jobs in Ti. Its execution time is the maximum execution time of all the jobs in it. With a slight abuse of the notation, we use ei to denote the execution time of the periodic task Ti , as well as that of all the jobs in it. At all times, the period and execution time of every periodic task in the system are known.

This definition of periodic tasks differs from the one often found in real-time systems literature. In many published works, the term periodic task refers to a task that is truly periodic, that is, interrelease times of all jobs in a periodic task are equal to its period. This definition has led to the common misconception that scheduling and validation algorithms based on the periodic task model are applicable only when every periodic task is truly periodic.

The accuracy of the periodic task model decreases with increasing jitter in release times and variations in execution times. So, a periodic task is an inaccurate model of the transmission of a variable bit-rate video, because of the large variation in the execution times of jobs (i.e., transmission times of individual frames). A periodic task is also an inaccurate model of the transmission of cells on a real-time connection through a switched network that does not do traffic shaping at every switch, because large release-time jitters are possible. We call the tasks in the system T1, T2, . . . , Tn.2 When it is necessary to refer to the individual jobs in a task Ti , we call them Ji,1, Ji,2 and so on, Ji,k being the kth job in Ti. When we want to talk about properties of individual jobs but are not interested in the tasks to which they belong, we also call the jobs J1, J2, and so on.

The release time ri,1 of the first job Ji,1 in each task Ti is called the phase of Ti. For the sake of convenience, we use φi to denote the phase of Ti , that is, φi = ri,1. In general, different tasks may have different phases. Some tasks are in phase, meaning that they have the same phase.

We use H to denote the least common multiple of pi for i = 1, 2, . . . n. A time interval of length H is called a hyperperiod of the periodic tasks. The (maximum) number N of jobs in each hyperperiod is equal to . The length of a hyperperiod of three periodic tasks with periods 3, 4, and 10 is 60. The total number N of jobs in the hyperperiod is 41. We call the ratio ui = ei /pi the utilization of the task Ti . ui is equal to the fraction of time a truly periodic task with period pi and execution time ei keeps a processor busy. It is an upper bound to the utilization of any task modeled by Ti. The total utilization U of all the tasks in the system is the sum of the utilizations of the individual tasks in it. So, if the execution times of the three periodic tasks are 1, 1, and 3, and their periods are 3, 4, and 10, respectively, then their utilizations are 0.33, 0.25 and 0.3. The total utilization of the tasks is 0.88; these tasks can keep a processor busy at most 88 percent of the time.

A job in Ti that is released at t must complete Di units of time after t ; Di is the (relative) deadline of the task Ti . We will omit the word “relative” except where it is unclear whether by deadline, we mean a relative or absolute deadline.We will often assume that for every task a job is released and becomes ready at the beginning of each period and must complete by the end of the period. In other words, Di is equal to pi for all n. This requirement is consistent with the throughput requirement that the system can keep up with all the work demanded of it at all times.

However, in general, Di can have an arbitrary value. In particular, it can be shorter than pi . Giving a task a short relative deadline is a way to specify that variations in the response times of individual jobs (i.e., jitters in their completion times) of the task must be sufficiently small. Sometimes, each job in a task may not be ready when it is released. (For example, when a computation job is released, its input data are first transferred to memory. Until this operation completes, the computation job is not ready.) The time between the ready time of each job and the end of the period is shorter than the period. Similarly, there may be some operation to perform after the job completes but before the next job is released. Sometimes, a job may be composed of dependent jobs that must be executed in sequence. A way to enforce the dependency relation among them is to delay the release of a job later in the sequence while advancing the deadline of a job earlier in the sequence. The relative deadlines of jobs may be shortened for these reasons as well