A Task Model to Reduce Control Delays

Real-Time Systems, 27, 215±236, 2004 # 2004 Kluwer Academic Publishers. Manufactured in The Netherlands.

A Task Model to Reduce Control Delays PATRICIA BALBASTRE [email protected] ISMAEL RIPOLL [email protected] JOSEP VIDAL [email protected] ALFONS CRESPO [email protected] Department of Computer Engineering, Technical University of Valencia, Camino de Vera, 14, E-46071, Valencia, Spain Abstract. Industrial control applications are usually developed in two phases: control design and real-time system implementation. In the control design stage a regulator is obtained and later it is translated into an algorithm in the implementation phase. Traditionally, these two phases have been developed in separate ways. Recently, some works have pointed out the necessity of the integration of the control design and its implementation. One of these works reduce the delay variance of control tasks (de®ned as the control action interval (CAI) and data acquisition interval (DAI) parameters) splitting every task into three parts. The CAI reduction method highly reduces the delay variance and improves the control performance. This work shows how to evaluate these delays under static and dynamic scheduling policies. A new task model is proposed in order to reduce the CAI and DAI parameters, which implies an improvement in the control performance. The new task model will be implemented in a real process, and the experimental measurements will show how, effectively, the control performance is highly improved with the methods presented in this paper. Keywords: timing jitter, control design, schedulability analysis, multi-rate controllers

1.

Introduction

Industrial control applications are usually developed in two phases: control design and real-time system implementation. In the control design stage a regulator is obtained and later it is translated into an algorithm. In the implementation phase each control algorithm (in multi-loop control systems) becomes a control task running under some timing constraints. Under the assumption of preemptive scheduling and task deadlines equal to periods Liu and Layland (1973) proved that the rate monotonic algorithm is the optimal ®xed priority scheduling algorithm. In Lehoczky et al. (1989) necessary and suf®cient (exact) schedulability tests that can be used to determine the schedulability of any given periodic task set were developed. Other research efforts (Baruah et al., 1990; Ripoll et al., 1995, 1996) are in the way of making dynamic scheduling a robust and suitable solution to be integrated in real-time operating systems and to be used in control systems. Traditionally, control design and its real-time implementation have been developed in separate ways. For example, in the control design stage it is assumed that the platform will not affect the system execution, that is, it provides an ideal behavior. In the real-time implementation phase it is assumed that the worst case execution times (WCET) are known, the periods are ®xed, deadlines are hard, etc. (Isermann, 1989). However, neither of these assumptions have to be necessarily true.

216

BALBASTRE ET AL.

Recently, some works have pointed out the need to integrate the control design and its implementation. In Seto et al. (1998), a method to consider the period range of the tasks involved in a control design is proposed, as criteria to obtain an optimal use of the system resources. In this integrated approach, the implementation is tuned to execute the control tasks at the maximum frequency while ensuring the system schedulability. The result of this approach is a system with a high system (CPU) utilization. Another approach in MartõÂ et al. (2001) is based on the notion of compensations wherein controller parameters are adjusted at runtime for the presence of jitters. In Cervin and Ecker (2000) on-line scheduling is proposed for control tasks whose execution times can vary abruptly. The proposed solution attempts to keep the CPU utilization at a high level, avoid overload, and distribute the computing resources among the tasks. The approach in Crespo et al. (1999) was to reduce the delay variance in the delivering of the control action computed by the different tasks. For that purpose, each task is partitioned into an initial or acquisition part, a mandatory part for the algorithm evaluation and a ®nal part to deliver the action. Moreover, the average delay can be incorporated in the controller design. In this case, the target is the average degradation of control performances which is directly related to both the control effort and the delay. Thus, the scheduling policy distributes the control action interval among the different tasks in order to minimize this index. The remainder of this paper is organized as follows: An analysis of the in¯uence of delays in industrial control applications is presented in Section 2; a new task model is proposed in Section 3 in order to reduce control delays; in Sections 4, 5, and 6 the methodology is described for deadline monotonic (DM), earliest deadline ®rst (EDF) scheduling and shared resources, respectively; an academic example is shown in Section 7, and the method is proved in a real process in Section 8; ®nally, the conclusions and future work are presented in Section 9. 2.

Delay In¯uence in Control Applications

This section analyzes the in¯uences of delays in the control performance of an industrial application. Some examples will show how the control performance is degraded when the control action is not delivered at regular instants of time. To measure these delays, two parameters will be de®ned: CAI and DAI. With a simple example it will be shown how delays produce a degradation in the control performance. Let there be two processes (P1 and P2 ) with transfer functions G…s† ˆ 100/…s ‡ 6† and G…s† ˆ 100/…s ‡ 1†, and the same behavior is required for both processes. The ideal behavior is represented in Figure 1 (Y) while the real response is depicted in Figure 2. Tasks T1 and T2 control P1 and P2 processes, respectively, sending the control action. As it can be seen, P1 presents a better behavior than P2 , since its response is more similar to the ideal response. However, the response of the two processes should be the same. Therefore, some kind of interferences have produced the degradation of P2 . These interferences are related to the delays in the control system. A detailed study of delays depending on the kind of the controlled system can be found in Albertos et al. (2000b). A classi®cation of control system delays can also be found in Torngren (1998).

A TASK MODEL TO REDUCE CONTROL DELAYS

217

Figure 1. Expected response.

In control applications it is important that the control action and the data acquisition are executed at regular instants of time. However, preemptions and blocking due to task priorities and resource locking cause a non-periodic behavior. The CAI expresses the percentage variation of the control action of a task relative to its period. This measure gives information about the delay variation that a task will suffer in the control action delivery, and it allows us to compare the performances of a control system. The control action interval (CAI) of task Ti is denoted by CAIi ˆ

WCRTi

Pi

BCRTi

100

being WCRTi and BCRTi the worst and best response times of Ti , respectively.

Figure 2. Response of processes P1 and P2 .

218

BALBASTRE ET AL.

Table 1. Task parameters of the example.

T1 T2 T3 T4

C

D

P

CAI (%) DM

2 3 3 4

6 8 20 40

6 8 20 40

0 25 55 12.5

In a similar way, the data acquisition interval (DAI) of a task Ti is denoted by DAIi ˆ

WCATi

Pi

BCATi

100

being WCATi and BCATi the worst and best activation times of Ti , respectively. The DAI expresses the percentage variation of the sensor acquisition relative to its period. Intuitively, if the task Ti has the higher priority and it is executed under priority based scheduling, its DAI will be 0 since it will start to execute at the beginning of its period. The CAI of the same task will be also 0, and WCRTi ˆ BCRTi ˆ WCETi . To explain the meaning of the CAI parameter, an academic example is used. Consider the task set of Table 1. The chronogram of the tasks is depicted in Figure 3. As can be seen in the ®gure, T1 is always the highest priority task, according to DM policy. Therefore, T1 does not suffer preemption and consequently its CAI is 0%. On the other hand, the rest of the tasks are preempted by tasks with higher priority, so they suffer delays, which is seen in its CAI. Figure 4 shows the comparison between ®xed and variable delays. Fixed delays are, among others, compute times and offsets. These kind of delays, that cannot be reduced, have to be taken into account in the regulator design in order to be compensated. Variable delays are due to blockings and preemptions of other tasks. These are worst delays, since the regulator cannot compensate them. Therefore, the main goal is to reduce delays but, if it is not possible, at least the remaining delays have to be ®xed delays.

Figure 3. Task chronogram of the example.

A TASK MODEL TO REDUCE CONTROL DELAYS

219

Figure 4. Delay comparison.

3.

Task Model

This section describes the task model used to reduce the CAI and DAI parameters. To achieve this goal, the new model has to take into account the activities involving a control loop task, that are: 1.

Data acquisition: data from an external sensor is acquired.

2.

Computation of the control action: it corresponds to the regulator computation and should be executed as soon as possible. At the end of this part, the basic control action is ready to be sent to the actuators.

3.

Output the control action: must be done either as soon as possible or within a ®xed time interval.

The control computation can be divided into a mandatory part and one or more optional parts. The mandatory part gives a ®rst solution to the control problem. Optional parts try to improve the solution. Nevertheless, in this paper optional parts will not be considered. The set of the three activities is the control activity. Our control system will be made of n control activities a ˆ …a1 ; . . . ; an †. A control activity ai is de®ned as ai ˆ …Ci ; Di ; Pi ; Oi †, where Ci is the computation time expressed in terms of worst case (WCET), Di is the deadline, Pi is the period, and Oi is the offset. It is assumed that D i  Pi . In the new task model proposed in this work, every ai became in the following tasks: *

Tii . It corresponds to the data acquisition part of ai . It also can be mentioned as initial task of ai .

220

BALBASTRE ET AL.

*

Tim . It corresponds to the control action computation of ai . It also can be mentioned as mandatory task of ai .

*

Tif . It corresponds to the control action delivery of ai . It also can be mentioned as ®nal task of ai .

From now on, the ®rst subscript on any parameter denotes the task identi®er, and the second (if it exists, otherwise it is a control activity) denotes the part of the task (initial, mandatory or ®nal). The IMF (initial, mandatory and ®nal) task model proposed consists of 3n tasks t ˆ …T1i ; T1m ; T1f ; . . . ; Tni ; Tnm ; Tnf † with the following parameters: Tii ˆ …Cii ; Dii ; Pii ; Oii † Tim ˆ …Cim ; Dim ; Pim ; Oim † Tif ˆ …Cif ; Dif ; Pif ; Oif † With the new model, it is necessary to rede®ne the CAI and DAI parameters. Now, the ®nal task delivers the control action, and the data acquisition is executed by the initial task. Therefore, DAIi ˆ CAIi ˆ

4.

WCATii

Pi

WCRTif

BCATii BCRTif

Pi

100 100

CAI Reduction in DM Scheduling

This section presents the method to reduce CAI and DAI, under a ®xed-priority scheduling policy (DM). In the model presented in Section 3 task parameters are not speci®ed. Depending on the scheduling algorithms, task parameters can differ. Regarding the compute times (Figure 5): Ci ˆ Cii ‡ Cim ‡ Cif The rest of the parameters, as deadline, offset, priority and periods are now speci®ed. Priorities are grouped in three levels: *

Final tasks …Tif † are located in the highest priority block and inside the block, according to DM policy.

*

Initial tasks …Tii † are assigned to the second priority block and also assigned according to DM policy.

A TASK MODEL TO REDUCE CONTROL DELAYS

221

Figure 5. Task model under DM scheduling.

*

Mandatory …Tim † tasks are placed in the lowest priority block and also ordered by DM policy. If N corresponds to the priority level (Level 1, N ˆ 1, etc.), thus: Priorityi ˆ

N ‡ Di NDi

The priority assignment of initial and mandatory tasks ensures that these tasks will be executed in the right order: initial tasks before mandatory ones. Since ®nal tasks have the highest priority, an offset has to be applied to them, to maintain the correct order. In some cases, the mandatory task can complete its execution after the offset time calculated. In this case, the scheduler has to delay the start of the ®nal task until the end of the mandatory one. Another solution is to synchronize the mandatory and the ®nal task by means of a semaphore, so the ®nal task has to wait until the mandatory task unlocks the semaphore. Regarding periods and deadlines, they are equal to the associated activity control. Therefore, the task model under DM policy is as follows: Tii ˆ …Cii ; Di ; Pi ; 0† Tim ˆ …Cim ; Di ; Pi ; 0† Tif ˆ …Cif ; Di ; Pi ; Oif †

222

BALBASTRE ET AL.

4.1.

Feasibility Analysis

The new task set is schedulable with the proposed scheduling algorithm if Dim  WCRT0im where WCRT0im

&

X

ˆ Cim ‡

j [ hp…Tim

WCRT0im Cj Pj †

'

The ®nal part offset follows the next expression: Oif ˆ WCRT0im

WCRT0if

where WCRT0if

ˆ Cif ‡

X j [ hp…Tif

&

WCRT0if Cj Pj †

'

The value of WCRT0 represents the worst case response time of tasks when the system is scheduled by a simple priority driven scheduler (a scheduler that does not delay the ®nal task). The ®nal task offset is adjusted to minimize the absolute delay as well as the CAI. This task formulation ensures a ®xed delay of the control action and a small variable delay range for each task. The method is applied off-line, that is, according to the task model proposed, the ®nal task offset is calculated, as well as CAI and DAI parameters. These parameters are introduced in the regulator and ®nally the system is executed. This approach drastically reduces the CAI and it allows a better algorithm behavior. The control performance obtained with this task split is illustrated in Albertos et al. (2000a) and it shows how this performance is highly improved.

4.2.

CAI and DAI Values

With the IMF model, CAI and DAI are known in advance. Furthermore, CAI and DAI are highly reduced regarding the initial task model a. CAI and DAI are now: CAIi ˆ DAIi ˆ

WCRTif

BCRTif Pi

WCATii

Pi

BCATii

100 ˆ 100

Oif ‡ WCRT0if Pi

Oif

100 ˆ

WCRT0if 100 Pi

A TASK MODEL TO REDUCE CONTROL DELAYS

where BCATii ˆ

X

Cji …Pji ==Pi †

WCATii ˆ Cii ‡

X j [ hp…Tii

5.

223

&

WCATii Cj Pj †

'

CAI Reduction in EDF Scheduling

When a dynamic-priority scheduling policy is used (EDF), task parameters such as deadlines, priorities and offsets have to be recalculated. Figure 6 shows the criteria for the task parameters. As Figure 6 shows, initial and ®nal tasks have different deadlines than mandatory tasks, which have deadlines equal to the initial deadlines of the associated control activity. The IMF task model for EDF scheduling is: Tii ˆ …Cii ; Dii ; Pi ; 0† Tim ˆ …Cim ; Di ; Pi ; 0† Tif ˆ …Cif ; Dif ; Pi ; Oif † CAI and DAI minimization is accomplished by reducing deadlines of ®nal and initial tasks respectively, so ®nal and initial tasks will usually have higher priority than mandatory tasks. An iterative algorithm to compute the deadline of initial (DAI) and ®nal (CAI) tasks is proposed. This algorithm tries to ®nd the minimum CAI and DAI while not endangering the correct execution of the mandatory tasks. The algorithm computes the

Figure 6. Task split under EDF scheduling.

224

BALBASTRE ET AL.

WCRT of each ®nal part, following the algorithm described in Spuri (1996). Obviously, the WCRT obtained is less than or equal to the deadline of each ®nal task. In the next iteration these WCRT values will be used as deadlines for ®nal tasks, and the WCRT is again computed. Dkif ˆ WCRTkif

1

The algorithm loops until the WCRT of all the ®nal tasks is equal to their respective deadlines. When the ®nal task deadlines have been computed, the same iterative method has to be applied to obtain the initial task deadlines. Table 2 shows the pseudo-code to obtain the ®nal and initial task deadlines. The last deadline assigned to initial tasks is shorter than the corresponding mandatory task deadline. Therefore, initial tasks will be executed before mandatory ones when executed by a deadline driven scheduler. On the other hand, ®nal tasks have also shorter deadline than mandatory ones which causes undesirable behavior. Each ®nal task has to be delayed until the mandatory one has ®nished. This can be achieved by adding an offset to the ®nal task. This offset is the earliest time that the ®nal task can start its execution: 0 Oif ˆ WCRTim

5.1.

Cif

Feasibility Analysis

Using the worst case response time expression for the synchronous set, a is feasible if: Dim  WCRT0im where WCRT0im is the WCRT of Tim in a. Again, it can be assumed that if a0 is feasible, then a is also feasible (Ripoll et al., 1996). Table 2. Initial and ®nal deadlines. 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16.

Deadline algorithm: Input: t; begin // Final tasks deadlines CalculateWCRT(T); while …9i = Dif ! ˆ WCRTif † do for j:=1 to n do Dif ˆ WCRTif od; end while; // Initial tasks deadlines while …9i = Dii ! ˆ WCRTii † do for j:=1 to n do Dii ˆ WCRTii od; end while;

225

A TASK MODEL TO REDUCE CONTROL DELAYS

5.2.

CAI and DAI Values

The worst case response time of a ®nal task is determined by its deadline. Therefore, the CAI parameter follows the next expression: CAIi ˆ

WCRTif

BCRTif Pi

100 ˆ

Oif ‡ Dif Pi

Oif

ˆ

Dif 100 Pi

The best case activation time of an initial task is: BCATii ˆ

n X 1

Cji …Pji ==Pi †e…Dj 5Dii †

where n is the number of control activities and the function e return 1 if the condition in brackets is true, otherwise it returns 0. BCATii is the summatory function of computation times of higher priority tasks with period being multiple of Tii . DAI is obtained as: DAIi ˆ

6.

Dii

BCATii 100 Pi

Accounting for Shared Resources

Permitting shared resources is fundamental to the usefulness of scheduling techniques for the hard real-time application engineer. It is not clear how hard real-time systems could be designed and implemented without such resources (Audsley, 1991). Moreover, in control applications the control action delivery or the data acquisition use external devices that are shared between all the control tasks. These accesses must be managed in order to avoid con¯icts. However, neither of the works related to the integration of scheduling and control have considered resource sharing. In general, for hard real-time systems, establishing the schedulability of a set of tasks that require mutually exclusive access of some set of resources is an NP-hard problem. In Baker (1991) a general resource access protocol is proposed, the stack resource policy (SRP), which can be used with both ®xed and dynamic scheduling algorithms. The SRP scheduling rules state that a task is not allowed to start executing until its priority is the highest among the active tasks and its preemption level is greater than the system ceiling (Baker, 1991). The preemption level of a task Ti is de®ned as Pi ˆ 1=Di , being Di the task deadline. With the SRP a task that starts its execution will never be blocked until completion. It will only be preempted by higher priority tasks. Another interesting protocol is the ceiling semaphore protocol (CSP), in which a task, when granted a resource, sets its priority to the ceiling of that resource. This is in contrast to the ordinary PCP which only raises process priorities when a process actually blocks a higher priority process (Mok, 1983). Many resource control protocols have been proposed for uniprocessor systems. The most popular techniques are based upon the priority inheritance model proposed by Sha et al. (1990). In the priority inheritance protocol (PIP) when a task T is blocked, the task that has blocked T inherits its priority while using

226

BALBASTRE ET AL.

the resource. The main drawback of this protocol is that deadlock and chained blocking can occur. The priority ceiling protocol (PCP) (Sha et al., 1990) appears to avoid these two problems. In PCP a task T can only lock a resource if that resource, or any other locked resource, is not accessed by a task with higher priority than T. The maximum priority that a task can inherit is equal to the ceiling of the resource accessed. The ceiling of a resource is the highest priority of all tasks that could lock it. These two protocols used the rate monotonic (RM) algorithm (Liu and Layland, 1973). Regarding the schedulability test of systems with shared resources, Sha et al. (1990) states that a set of n periodic tasks can be scheduled by the RM policy if Vi

i ˆ 1::n

i X Cj Bi ‡  i…21=i P Pi jˆ1 j

1†

where Bk is the blocking factor, and it is the maximum time that a task can be blocked by lower priority tasks. It depends on the resource protocol. Another schedulability test based on the response time of tasks for ®xed priority scheduling was presented in Audsley et al. (1993), adapting the formulation made in Joseph and Pandya (1986) to take into account the blocking factor. Vi ˆ 1::n Ri  Di where X

&

RTi RTi ˆ Ci ‡ Bi ‡ Cj Pj j [ hp…i†

'

Moreover, the worst and best case response times will be useful for our purpose. So, we de®ne: *

WCRTi is the worst case response time of Ti in a system that does not use shared resources.

*

wcrti is the worst case response time of Ti in a system with shared resources.

*

BCRTi is the best case response time of Ti in a system that does not use shared resources.

*

bcrti is the best case response time of Ti in a system with shared resources.

The same de®nitions can be made with regard to the activation of tasks (WCAT, BCAT). Let be r a set of r resources and the task set t. Tasks can access to shared resources by means of critical sections. For a task TiR ,1 a critical section shi is de®ned as shi ˆ …rh ; thi ; whi †, where *

rh [ r is the resource accessed by the critical section.

A TASK MODEL TO REDUCE CONTROL DELAYS

*

thi is the earliest time rh , relative to the release time ri that TiR can enter rh .

*

whi is the worst case execution time of the critical section.

227

The set of critical sections accessed by Ti R is si , thus: si ˆ fshi g R R Therefore, the task set tR ˆ …T1iR ; T1m ; T1fR ; . . . ; TniR ; Tnm ; TnfR † with shared resources has the following characterization:

TiiR ˆ …Cii ; Dii ; Pii ; Oii ; sii † R Tim ˆ …Cim ; Dim ; Pim ; Oim ; sim †

TifR ˆ …Cif ; Dif ; Pif ; Oif ; sif † Using the SRP protocol, the blocking factor can be calculated as the longest critical section among those with a ceiling greater than or equal to the preemption level pi of TiR : Bi ˆ maxfwhi j …TiR 5TjR

thi † 6 pi  ceil…rh †g

where ceil…rh † is the ceiling of the resource rh , and it follows the expression: ceil…rh † ˆ max fpi j TiR accede a rh g i

We assume that initial and ®nal parts will share I/O devices to communicate with the process. It is also assumed that mandatory tasks do not communicate with the process, so these tasks will not share I/O Resources, but other resources, called general resources (Figure 7). It is also assumed that ®nal and initial tasks do not share general resources, mainly for two reasons: it can be assumed that ®nal and initial tasks only write and read data from external devices respectively. So, these tasks only communicate with the process to be controlled and they only use I/O resources. Even if ®nal or initial tasks update global data, these operations can be considered atomic instructions, so there is no need to protect these accesses. The second reason is that a main task will not be blocked by ®nal or initial tasks because main tasks always have lower priority than initial and ®nal tasks. To deal with the problem of considering shared resources, two subproblems will be analyzed: I/O resource sharing and general resource sharing.

Figure 7. Resource types.

228 6.1.

BALBASTRE ET AL.

I/O Resource Sharing

These type of resources will only be used by ®nal and initial tasks. Therefore: si ˆ shi ˆ frh ; 0; Ci g In this situation, initial tasks could be promoted to a higher priority level whenever they lock a resource. So, ®nal tasks will be blocked by initial tasks and by other ®nal tasks with lower priority (longer relative deadline). Initial tasks will only be blocked by other initial tasks with lower priority. To apply the CAI minimization method to deal with I/O resources two questions have to be considered: the schedulability test and the new offset applied to the ®nal task (and, consequently the new CAI and DAI). Regarding the schedulability condition, it is obvious that mandatory tasks will not suffer any blocking, since they do not share I/O resources. So, the WCRT of mandatory tasks will not change and the schedulability condition will remain as: Vi

WCRTim  Dim

As mandatory tasks do not share I/O resources, its WCRT will be the same as the wcrt in a system without resource sharing. The ®nal task offset is modi®ed by the ®nal task blocking factor. So, the offset applied to the ®nal task is: Oif ˆ WCRTim

wcrtif

where the WCRTkf is given by the next expression: & ' X wcrtif wcrtif ˆ Cif ‡ Bif ‡ Cj Pj j [ hp…if † Now, the CAI and DAI parameters are known off-line: CAIi ˆ DAIi ˆ

6.2.

wcrtif  100 Pi wcatii

Pi

bcatii

100

General Resource Sharing

These kinds of resources will be used by mandatory tasks. At the same time, it is supposed that ®nal and initial tasks share I/O Resources. A mandatory task that uses a General Resource can suffer blocking only by other mandatory tasks with lower priority.

A TASK MODEL TO REDUCE CONTROL DELAYS

229

As a consequence, response times of mandatory tasks will be greater. The new worst case response time has to take into account the blocking factor: & ' X wcrtim Cj wcrtim ˆ Cim ‡ Bim ‡ Pj j [ hp…im† and the new schedulability condition is: Vi

wcrtim  Dim

Since the response times of mandatory tasks are greater, ®nal tasks will have to wait until their mandatory tasks complete execution. So, the ®nal task offset has to be modi®ed, in order to maintain execution order. The new offset is: Oif ˆ wcrtim

wcrtif

It is important to note that CAI and DAI do not depend on mandatory tasks behavior. Even if the main tasks are blocked, the variable delay of the ®nal tasks will not change. However, an increase of the ®xed delay is expected, as the ®nal task offset is greater due to the main tasks blocking.

6.3.

The Blocking Factor

According to SRP, the maximum blocking time Bi for a task Ti can be calculated as the longest critical section among those with a ceiling greater than or equal to the preemption level of Ti . This blocking time affects the response time of task Ti . A property of SRP is that a task can not be blocked twice, that is, once it commences its execution, it can not be blocked again. If we consider a ®nal task, it can be preempted by other ®nal tasks with higher priorities. And it can be blocked by all the initial tasks, and ®nal tasks with lower priorities. Therefore, it is impossible that a ®nal task Tkf is blocked by an initial task Tji and preempted by the ®nal task Tjf . If a ®nal task Tkf is blocked by an initial task Tji , then Tkf will execute always before the mandatory task Tjm , and thus before the ®nal task Tjf . The same reasoning can be applied for initial tasks Tki . This can be used to reduce the calculated value for wcrtk . The algorithm for a task Tk is presented in Table 3. Table 3. Blocking factor algorithm. Let 1. 2. 3. 4. 5. 6.

fski g be the set of critical sections with ceil…rk †  pi of TiR . Bi ˆ max …wki † k If Bi ˆ Cji then If Bi > Cjf and Cjf contributes to wcrti then wcrti ˆ wcrti Cjf Else delete Cji of fski g. Go to 1. Else stop.

230 7.

BALBASTRE ET AL.

Example

As an example, consider the following task set in Table 4. All initial and ®nal tasks share the same I/O resource 1, while mandatory task 4 use two general resources (with identi®ers 2 and 3). Task 3 uses only general resource 3, while the other mandatory tasks use only General resource 2. A comparison will be made between the consideration of shared resources and the system without resource sharing. Figure 8 shows the CAI values when no resources are considered. The ®gure shows a comparison between the initial task model …a†, and the task model proposed …t†. As it can be seen, task T1 has originally no CAI, since it is the higher priority task. However, when the new task model is used, T1 has a CAI of 3%. This implies the reduction of other tasks delays. Figure 9 shows the same comparison, when shared resources are used. As it can be seen in the ®gure, task 4 has the same CAI and ®xed delay in both cases, since it is the lower priority task, and it will never be blocked. Therefore, the same behavior is expected with and without shared resources. Task T1 has some CAI in the two models. This is due to the blocking factor. The rest of the tasks present greater variable delays in the shared resource system. This increase is also due to the blocking factor of ®nal tasks. Moreover, the ®xed delay is also greater, in this case due to the blocking factor of mandatory tasks. Figure 10 shows values of variable delays relative to the period (CAI). The ®gure shows a comparison between shared and non-shared resources, in the original task set and in the proposed task set. 8.

Experimental Measurements

To illustrate the bene®ts of the proposed model, we have chosen an actual real-time control application: a robot arm. The robot has to move certain pieces on a canvas, pretending to be a chess player. At ®rst, the architecture was based on a comercial and closed operating system. In order to achieve more ¯exibility, the architecture was changed: the new architecture is based on a PC, external sensors, and actuators (encoder, DAC, ADC, dynamo, etc.). This allow us to choose the real-time operating system, the scheduling policy and, in general, an open and more ¯exible architecture. Table 4. Task parameters of the example. General resources

I/O resources

C

D

P

n

id

C

n

id

C

T1 T2 T3

5 8 10

27 30 45

27 32 50

1 1 1

1 1 1

2 3 3

1 1 1

T4

13

60

70

1

1

5

2

2 2 3 2 3

3 5 6 2 5

A TASK MODEL TO REDUCE CONTROL DELAYS

Figure 8. Delay comparison without shared resources.

Figure 9. Delay comparison with shared resources.

231

232

BALBASTRE ET AL.

Figure 10. CAI comparison between shared and non-shared resources.

The real-time operating system used is RTLinux (Barabanov and Yodaiken, 1996). Unlike other solutions to design a real-time operating system, RTLinux does not add or modify any system call to Linux. Instead of modifying the kernel of Linux to make it predictable, RTLinux gains control of the interrupts. Linux then shares the CPU with other tasks, more precisely Linux is the background task, and it runs only when no other RT-tasks are running. The system has three control tasks: the position control task, that implements the control algorithm of X, Y and Z axis position, the speed control task, that controls the speed of the robot arm, and the strength control task. The goal of the experiments is to evaluate the behavior of the position control task. The experiments have been made in the following way: *

Experiment 1 (Table 5): The position control task is assigned the highest priority.

*

Experiment 2 (Table 6): The position control task is assigned the lowest priority.

*

Experiment 3 (Table 7): The position control task is changed into the IMF model proposed in this work. Initial, mandatory and ®nal position tasks have less priority than speed and strength control tasks.

Table 5. Task parameters for Experiment 1.

Speed task Strength task Position task

C

D

P

Priority

10 40 10

30 80 100

30 80 100

2 3 1

233

A TASK MODEL TO REDUCE CONTROL DELAYS

Table 6. Task parameters for Experiment 2.

Speed task Strength task Position task

C

D

P

Priority

10 40 10

30 80 100

30 80 100

1 2 3

Table 7. Task parameters for Experiment 3.

Speed task Strength task 2 Initial position task Mandatory position task Final position task

C

D

P

Priority

10 40 2 6 2

30 80 100 100 100

30 80 100 100 100

1 2 4 5 3

Figure 11 shows the error position (in millimeters) in the Z axis of the robot arm, when the robot has to go down to pick up a piece, and then it goes up until it achieves the reference. The X and Y axis error have no relevance in this example, since the robot only moves in the Z direction. In the ®rst experiment, when the position task has the highest priority, there is some error until the new reference is achieved. But, in the second experiment, when it can be preempted by both speed and strength tasks, the error becomes greater, which results in a degraded response. On the contrary, when the IMF

Figure 11. Error position of the robot arm for the three experiments.

234

BALBASTRE ET AL.

task model proposed in this paper is implemented for the position control task (Experiment 3), the error is very similar to the Experiment 1. This means that the IMF model removes the negative effects of being the lowest priority task, that is, delays due to preemptions of other tasks have been reduced.

9.

Conclusions and Future Work

In recent years, the integration of control design and real-time scheduling has been pointed out. In control applications it is important that the control action and the data acquisition are executed at regular instants of time. However, preemptions and blocking due to task priorities and resource locking cause a non-periodic behavior. These delays due to the scheduler degrade the control performance of the system. To measure the delays two parameters have been de®ned: The CAI expresses the percentage variation of the control action of a task relative to its period, and the DAI expresses the percentage variation of the sensor acquisition also relative to its period. This work has shown how to evaluate these delays under static and dynamic scheduling policies. A new task model has been proposed in order to reduce the CAI and DAI parameters, which implies an improvement in the control performance. To con®rm the delay reduction achieved, the IMF task model has been implemented in a real process, and the experiments have shown how the control performance is highly improved. As further research, other kind of delays, such as communication delays between nodes in a distributed system, have to be considered in the model.

Acknowledgment This work was supported by the Spanish Government Research Of®ce (CICYT) under grant TAP-99-1226-C02.

Note 1. From now on, the superscript R will refer to the use of shared resources.

References Albertos, P., Crespo, A., Ripoll, I., ValleÂs, M., and Balbastre, P. 2000a. RT control scheduling to reduce control performance degrading. In Proceedings of the 39th IEEE Conference on Decision and Control. Albertos, P., Salgado, M., and Olivares, M. 2000b. Are delays in digital control implementation always bad? In Asian Control Conference, Shangai. Audsley, N. 1991. Resource Control for Hard Real-Time Systems: A Review. Technical Report YCS 159, University of York, Department of Computer Science.

A TASK MODEL TO REDUCE CONTROL DELAYS

235

Audsley, N., Burns, A., Tindell, K., Richardson, M., and Wellings, A. 1993. Applying new schedulability theory to static priority pre-emptive scheduling. Software Engineering Journal 8(5): 284±292. Baker, T. P. 1991. Stack-based scheduling of realtime processes. The Journal of Real-Time Systems 3(1): 67± 100. Barabanov, M., and Yodaiken, V. 1996. Real-time linux. Linux Journal. Baruah, S., Mok, A., and Rosier, L. 1990. Preemptively scheduling hard real-time sporadic tasks on one processor. In IEEE Real-Time Systems Symposium, pp. 182±190. Cervin, A., and Ecker, J. 2000. Feedback scheduling of control tasks. In Proceedings of the 39th IEEE Conference on Decision and Control. Crespo, A., Ripoll, I., and Albertos, P. 1999. Reducing delays in RT control: the control action interval. IFAC World Congress Beijing. Iserman, R. 1989. Digital Control Systems. Springer Verlag. Joseph, M., and Pandya, P. 1986. Finding response times in a real-time system. The Computer Journal 29(5): 390±395. Lehoczky, J., Sha, L., and Ding, Y. 1989. The rate monotonic scheduling algorithm: Exact characterization and average case behavior. In IEEE Real-Time Systems Symposium, pp. 166±171. Liu, C., and Layland, J. W. 1973. Scheduling algorithms for multiprogramming in a hard real-time environment. JACM 23: 46±68. MartõÂ, P., Fuertes, J. M., and Fohler, G. 2001. Jitter compensation for real-time control systems. In IEEE RealTime Systems Symposium. Mok, A. 1983. Fundamental Design Problems of Distributed Systems for the Hard Real-Time Environment. MIT/LCS/TR-297, Laboratory of Computer Science, MIT. Ripoll, I., Crespo, A., and GarciÂa-Fornes, A. 1995. An optimal algorithm for scheduling soft aperiodic tasks in dynamic-priority preemptive systems. IEEE Transactions on Software Engineering 23(6): 388±400. Ripoll, I., Crespo, A., and Mok, A. 1996. Improvement in feasibility testing for real-time tasks. Journal of RealTime Systems 11: 19±40. Seto, D., Lehoczky, J., and Sha, L. 1998. Task period selection and schedulability in real-time systems. In IEEE Real-Time Systems Symposium, pp. 188±198. Sha, L., Rajkumar, R., and Lehoczky, J. 1990. Priority inheritance protocols: an approach to real-time synchronisation. IEEE Transactions on Computers 39(9): 1175±1185. Spuri, M. 1996. Analysis of Deadline Scheduled Real-Time Systems. Rapport de Recherche RR-2772, INRIA, Le Chesnay Cede, France. Torngren, M. 1998. Fundamentals of implementing real-time control applications in distributed computer systems. The Journal of Real-Time Systems 14(3): 3±34.

Patricia Balbastre is an assistant professor of Computer Engineering. She graduated in Electronic Engineering at the Politechnical University of Valencia, Spain, in 1998, and gained her Ph.D. degree in Computer Science at the same university in 2002. Her main research interests include real-time operating systems, dynamic scheduling algorithms and real-time control.

236

BALBASTRE ET AL.

Ismael Ripoll received his B.S. degree in 1992, and a Ph.D. degree in Computer Science in 1996, both at the Polytechnic University of Valencia, Spain, where he is currently a Professor in the DISCA Department. His research interests include embedded and realtime operating systems.

Josep Vidal is currently a Ph.D. student on real-time systems at the Politechnical University of Valencia. He received the title of Computer Science Engineer in 2001 from the same university. Recently most of his work has been focused on RTLinux (controlling robots, kernel implementation).

Alfons Crespo is Professor of the Department of Computer Engineering of the Universidad PoliteÂcnica de Valencia, where he received his Ph.D. in Computer Science in 1984. He also held the position of Associate professor in 1986 and full Professor in 1991. He leads the group of InformaÂtica Industrial and has been responsible for several European and Spanish research projects. His main research interests include different aspects of the real-time systems (scheduling, hardware support, scheduling and control integration). He has published more than 60 papers in specialized journals and conferences in the area of real-time systems.