J. Cent. South Univ. Technol. (2007)02-0266-05

DOI: 10.1007/s11771-007-0053-9                                                                                             

Application of predictive control scheduling method to

real-time periodic control tasks overrun

SHEN Qing(沈 青)^{1, 2}, GUI Wei-hua(桂卫华)¹, YANG Chun-hua(阳春华)¹, YANG Tie-jun(杨铁军)¹

(1. School of Information Science and Engineering , Central South University, Changsha 410083, China;

2. School of Basic Education for Officers, National University of Defense Technology, Changsha 410003, China)

Abstract: Based on the abort strategy of fixed periods, a novel predictive control scheduling methodology was proposed to efficiently solve overrun problems. By applying the latest control value in the prediction sequences to the control objective, the new strategy was expected to optimize the control system for better performance and yet guarantee the schedulability of all tasks under overrun. The schedulability of the real-time systems with p-period overruns was analyzed, and the corresponding stability criteria was given as well. The simulation results show that the new approach can improve the performance of control system compared to that of conventional abort strategy, it can reduce the overshoot and adjust time as well as ensure the schedulability and stability_.

Key words: real-time system; overrun; predictive control scheduling; stability                            

In multi-task control systems, some task jobs are likely to miss their deadlines due to overrun, furthermore resulting in the loss of control signals and the decline of control performance. How to handle overruns in real-time systems has attracted much attention. STANKOVIC et al^[1] and LU et al^[2] described an approach to increase the performance of a scheduling algorithm in unpredictable dynamic systems whose workloads cannot be accurately modeled. They used feedback control real-time scheduling to handle the deadline miss ratio and rejected jobs to keep the system not fully loaded. However, if too many control jobs are rejected, it would make the system out of control. ABDELZAHER et al^[3] proposed a mechanism for QoS negotiation as a way to ensure graceful degradation in a distributed pool of shared computing resources. Although the method provided flexibility in handling load variations caused by new task arrivals or hardware failures, transient execution overruns due to variable computation times cannot be handled locally without affecting the whole application. BUTTAZZO et al^[4] and SHEN et al^[5] presented a novel scheduling methodology for managing overrun conditions in real-time control applications. According to their elastic approach, task utilizations can be compressed through period variations to adapt a given workload. However, as task period has its bound, the compression of the task utilization has its limit as well. This technique affects the control performance to some degree. KOREN et al^[6] and RAMANATHAN^[7] investigated the scheduling systems that allowed to skip. But they didn’t consider the scheduling that guaranteed at least k out of n instantiations will be executed, and didn’t have the consideration to the task control performance influence. ABENI et al^[8] proposed the constant bandwidth server. CACCAMO et al^[9-10] proposed a variant of the constant bandwidth server. When a task experiences an overrun, the deadline is postponed by a period so that the schedulability of other tasks is not jeopardized. The main objective is to decrease the response latency of aperiodic tasks. CERVIN^[11] investigated three overrun strategies, i.e. abort, skip, and queue, and all were modeled as discrete­time jump linear systems and achieve enhancements control performance analyzed. All methods mentioned above can handle the overrun problems and in some respects, however all of them will degrade the control performance to a certain extent.

In this paper, based on the fixed period task abort strategy, a novel predictive control^[12] scheduling methodology was presented to overrun management. It allows us to fully utilize the processor for the better control performance and guarantee the schedulability of all tasks under overruns. Simulations show that the proposed scheme can improve the control system performance effectively.

2 Predictive control scheduling model and stability criteria  

The predictive control scheduling model based on RM^[13] and abort strategy was proposed. With task abort strategy used in the fixed period tasks, if the job execution time exceeds the sampling period, job is aborted due to overrun. Thus the control signal is not expected to be updated in the next sampling interval, which degrades the control performance.

Assuming that the upper bound of aborting signals is not greater than p. The key of the scheme is that an array with p  predictive control values^[14] ,,… at time kT  is added in the control depositing memory. When overrun occurs without signal output, the controller chooses the latest control value from the available control prediction sequence. The system expected performance can be guaranteed so long as the predictable values are basically correct.

2.1    Calculation of predictive control scheduling signals

A SISO(single-input single-output) discrete system was considered for the analysis. It is described as the following state space form:

               (1)

where  are the state, input, and output vectors of the system respectively;  are the system matrices. The state observer is designed as

    (2)

Assuming that the kth job of a period task has the following constraints: the task has to execute within its predefined period T, from time (k-1)T to time kT. In other words, the task has to complete before time kT. Then,

              (3)

where  is the state feedback matrix and   is the observer feedback matrix.

If the (k+1)th job is not finished before the deadline due to the interference or overrun processing occupied by other tasks, no control output is given in this period. The output predictive schedule control at time (k+1)T is determined by the sample value and the state predictive value at time kT, the design of the observer and output predictive control were calculated as follows:

    (4)

Correspondingly, if p task jobs are not finished before their deadlines due to overrun, there are no output controls in these periods, the output predictive control signals at time (k+1)T, (k+2)T, …, (k+p)T are determined by the sample value and the state predictive value at time kT:

(5)

2.2    Control signals scheduling

An array with p elements was assigned for each task, in each task’s kth period. Control output in current period as well as future predictive control scheduling outputs ,,… were calculated and put in the array. These values are updated at each task job execution.

When overrun occurs, the control algorithm is unable to complete within its deadline and no control output is produced, the predictive control signal in the array can be used instead. An example is illustrated in Fig.1, assuming T is the task period, there is no overrun in the first period, control output  as well as the predictive control outputs  and  can be computed,  and  are stored in the array of this task. In the second and third periods, task jobs can’t be completed before their deadlines because of overruns, no control outputs are produced in these two periods. If the conventional abort strategy is used, the system still outputs u₁, therefore degrading the system performance. In contrast, under the proposed predictive control scheme, the predictive control scheduling signals and  are sent to the plant as soon as the task jobs are unable to complete before their deadlines. Thus the better control performance is achieved.                                                                                                                                                                                                                                                                                                                                                                                                                                          

Fig.1 Task with two periods overrun

2.3    Schedulability analysis and stability criteria of predictive control scheduling model

For the predictive control scheduling scheme proposed in this paper, one of the key issues is the schedulability and stability of the system. System instability means the failure of the task scheduling. The stability of the system with the upper bound of p-period overruns was investigated as follows.

The necessary and sufficient condition of the closed-loop system stability is that its closed-loop poles are stable. From the predictive control obtained in the previous section, it is clear that:

      (6)

   (7)

(8)

Let

  (9)

             θ(p)=[θ ₁ θ₂]              (10)

where

Then, the closed-loop system can be written as

          (11)

Therefore, the closed-loop system is stable if and only if all eigenvalues of the matrix (10) are within the unit circle, where p is the only variable that affects the matrix eigenvalues, and p_max is the maximum value that still guarantees eigenvalues in the unit circle. The system is stable when p≤p_max, namely so long as the number of the overrun periods does not surpass p_max, the task set is schedulable.

3 Example

As an example, stabilizing control of a pendulum with the state space realization^[15] is considered as

Here, assuming that the initialization value is , the task cycle is 1 s, the execution time in a cycle is 0.5 s, the close-loop poles are .

3.1 Calculation of pendulum parameter p under schedulability and stability

From the matrix (10), the value p_max that guarantees the system’s stability is calculated according to the condition that the eigenvalues are all within the unit circle.

Enlarging the value p gradually, only when p=15, the eigenvalues appear outside the unit circle:

0.926 3+0.508 8 i

0.926 3-0.508 8 i

1.002 9+0.316 8 i

1.002 9-0.316 8 i

1.042 4+0.107 5 i

1.042 4-0.107 5 i

Therefore the system is stable with p_max=14, in this example, 14-period overruns cannot affect the system stability and the tasks schedulability.

3.2 Schedulability analysis of pendulum real-time system

For a single-task system, the control task occupies CPU alone, all task jobs can finish their executions before their deadlines, after several cycles of liberation, the pendulum angle tend to 0 (Fig.3), then the pendulum is in the equilibrium.

        Fig.2 Task jobs with periods overrun

φ=[φ₁ φ₂]              (12)

Fig.3 Pendulum system response with no period overrun

In a multi-task system, it is supposed that a perturbation as a task affects the system in the 6th and 7th periods of the pendulum work, the interference signal priority level is the highest, its task cycle is 0.8 s, and execution time is 0.5 s. The task set scheduling with RM strategy is illustrated in Fig.2, pendulum task jobs have not finished their executions by the ends of the 6th and 7th sampling periods in cause of high priority task’s preemption, no outputs are produced as well. As shown in Fig.4, overrun elongates the transition time of the pendulum and enlarges its oscillation times and amplitude. This shows that the performance index degrades due to the two missed outputs.

Fig.4 Pendulum system response with period overrun

With the predictive control scheduling method, when overrun occurs　(p=2)　in the 6th and 7th periods of the pendulum’s running, predictive control scheduling signals are used to replace the lost signals. The pendulum angle’s movement trajectory is shown in Fig.5. From Fig.5, it is clear that control performance is improved significantly.

Under this control scheme, the stability of the pendulum was investigated next. As p=2, from the matrix (10), the pendulum matrix (12) is described as follows:

Fig.5 Pendulum system response with period overrun under predictive control scheduling strategy

The eigenvalues of matrix (12) are

0

0

0.500 0+0.500 0 i

0.500 0-0.500 0 i

0.500 0+0.500 0 i

0.500 0-0.500 0 i

-0.000 4+0.000 4 i

-0.000 4-0.000 4 i

0.000 4+0.000 4 i

0.000 4-0.000 4 i

-0.000 0

0.000 0+0.000 0i

0.000 0-0.000 0i

0.000 0

They are all within the unit circle. Therefore, the closed-loop system is stable.

4 Conclusions

1) A kind of novel predictive control scheduling methodology based on abort strategy of fixed periods was proposed for managing overruns. The pre-calculated predictive control scheduling signal was used to replace lost control signal in overrun task periods, which ensures the stability and improves the control performance when the number of overrun periods is not greater than the upper-bound p_max.

2) The schedulability analysis and stability criteria of the real-time systems with p-period overruns were investigated.

3) Extra calculations are required for the model in each task job execution that calculated p-cycle predictive control scheduling signals. However, if p is limited in a certain bound, where it is reasonable in the system, the computational overhead is insignificant due to the simple computation. The additional occupancy CPU time is low, and the control performance is improved at the expense of little CPU resources consumption.

References

[1] STANKOVIC J A, LU C, SON S, et al. The case for feedback control real-time scheduling[C]// The 11th Euromicro Conference on Real-Time Systems (ECRTS99). York: Institute of Electrical and Electronics Engineers, 1999: 11-20.

[2] LU C, STANKOVIC J A, TAO G, et al. Design and evaluation of a feedback control EDF scheduling algorithm[C]// Proceedings of the IEEE Real-Time Systems Symposium. Phoenix: Institute of Electrical and Electronics Engineers, 1999: 56-67.

[3] ABDELZAHER T F, ATKINS E M, SHIN K G. QoS negotiation in real-time systems and its application to automated flight control[J]. IEEE Transactions on Computers, 2000, 49(11): 1170-1183.

[4] BUTTAZZO G, LIPARI G, ABENI L. Elastic task model for adaptive rate control[C]// Proceedings of the IEEE Real-Time Systems Symposium. Spain: Institute of Electrical and Electronics Engineers, 1998: 286-295.

[5] SHEN Q, GUI W H, HUO Y, et al. Flexible periodic task schedule model and control performance analysis[C]// International Conference on Sensing, Computing and Automation. Chongqing: Watam Press, 2006: 1953-1956.

[6] KOREN G, SHASHA D. Skip­over: algorithms and complexity for overloaded systems that allow skips[C]// Proceedings of the IEEE Real­Time Systems Symposium. Pisa: Institute of Electrical and Electronics Engineers, 1995: 110-117.

[7] RAMANATHAN P. Graceful degradation in real­time control application using (m,k)­firm guarantee[C]// Proceedings of the 27th Annual International Symposium on Fault-Tolerant Computing. Seattle: IEEE Computer Society, 1997: 132-141.

[8] ABENI L, BUTTAZZO G. Integrating multimedia applications in hard real­time systems[C]// Proceedings of the 19th IEEE Real­Time Systems Symposium. Madrid: Institute of Electrical and Electronics Engineers, 1998: 3-13.

[9] CACCAMO M, BUTTAZZO G, SHA L. Handling execution overruns in hard real­time control systems[J]. IEEE Transactions on Computers, 2002, 51(7): 835-849.

[10] CACCAMO M, BUTTAZZO G, SHA L. Capacity sharing for overrun control[C]// Proceedings of the IEEE Real-Time Systems Symposium. Orlando: Institute of Electrical and Electronics Engineers,2000: 295-304.

[11] CERVIN A. Analysis of overrun strategies in periodic control tasks[C]// Proceedings of the 16th IFAC World Congress. Prague: Elsevier, 2005.

[12] MACIEJOWSKI J M. Predictive Control with Constraints[M]. Harlow, UK: Prentice-Hall, 2002.

[13] LIU C, LAYLAND J. Scheduling algorithm for multi- programming in a hard real-time environment[J]. Journal of the ACM, 1973, 20(1): 46-61.

[14] LIU Guo-ping, XIA Y, REES D. Predictive control of networked systems with random delays[C]// Proceedings of the16th IFAC World Congress. Prague: Elsevier, 2005.

[15] HENRIKSSON D, CERVIN A, ?RZ?N K E. TrueTime: Simulation of control loops under shared computer resources[C]// Proceedings of the 15th IFAC World Congress on Automatic Control. Barcelona: Elsevier, 2002.

Foundation item: Project (60505018) supported by the National Natural Science Foundation of China

Received date: 2006-05-24; Accepted date: 2006-07-27

Corresponding author: SHEN qing , PhD ; Tel : + 86-731-8879261; E-mail : shenqing @public.cs.hn.cn

(Edited by LI Xiang-qun)