Scheduling of Centralized Control System Tasks Using Largest Error First Algorithm

Scheduling of Centralized Control System Tasks Using Largest Error First Algorithm

Nikhilbinoy C.

Department of Instrumentation and Control, N.S.S. College of Engineering (University of Calicut)

Retheep Raj

Department of Instrumentation and Control, N.S.S. College of Engineering (University of Calicut)

Abstract

Sampling and actuations are generally assumed to be synchronous and periodic, and a highly deterministic timing of an implementation is assumed. When a control algorithm is executed by a task or by a set of subtasks in a multitasking real-time system, these assumptions are not met, because real-time scheduling algorithms introduce jitter in task instance execution. Hence, jitter on task instances and deterministic timing needs of an implementation, lead to final implementations that can suffer degradation in the control system performance and even leads to instability in the system. Real-Time system for Control system with control tasks are scheduled by using the Largest Error First Scheduling Algorithm. It shows how the control information is used to schedule the tasks without the degradation of control system performance by reducing the number of deadline miss and deviation of sampling interval from the optimal sampling period.

Keywords- LEF scheduling, optimal period

1. Introduction

   Automatic control is becoming more and more important in this age of automation. In manufacturing processes it ensures that certain parameters, such as temperature, pressure, speed or voltage, take up specific constant values recognized as the optimum, or are maintained in a particular relationship to other variables. In other words, the duty of control engineering is to bring these parameters to certain pre- defined values (set-points), and to maintain them constant against all disturbing influences.

   The main problem with continuous time controllers is their implementation and modification. To implement a continuous time controller requires you to build an op-amp circuit with resistors, capacitors and inductors. To upgrade or change our continuous time controller, we need get out our soldering iron and get to work.

   In a digital control system, the controller is implemented on a microprocessor in software. The microprocessor is set to sample the output of the plant at a sample rate fS . The sampled output is then used, together with a digital reference, by the controller to generate a digital control signal every h second.

   Many control applications constitute real-time systems due to their strict timing constraints. Therefore, when implementing real-time computer controlled systems, we need to integrate control and real-time disciplines. But there is a gap between the above disciplines due to their different theoretical and practical backgrounds when dealing with real-time control systems.

   The usual way of building a real-time computer- controlled system is to first carry out control design and then its computer implementation. This staged procedure can lead to implementations that do not fulfil the stringent timing constraints that control applications require. On one hand, it is known that control theory assumes a highly deterministic, fixed sampling periods as needed. On the other hand, real- time scheduling algorithms introduce jitter in task- instance execution. This contradictory situation, jitter on task instances execution versus deterministic timing needs of an implementation, leads to final implementations that may cause degradation in the

   control system performance and even lead to instability in the system.

   Real-time systems are systems in which the correctness of a result not only depends on the logical correctness of the calculation but also upon the time at which the result is made available.

   Usually, real-time systems are used to control or interact with a physical system, where timing constraints are imposed by the environment. As a consequence, the correct behaviour of these systems depends not only on the result of the computation but also at which time the results are produced. Design of real-time systems must make sure that the system reacts to external events in a timely way.

2. Design of Real-Time System

Control theory assumes a highly deterministic, synchronous and fixed sampling periods. But CTU is handling more than one control task, leads to the violation of above assumption, because there is no order for execution of control tasks. Due to this strict timing constraint, real-time theory is integrated with control theory. But any attempt to increase the control performance leads to the decrease in the performance of real-time performance. On the other hand, real-time scheduling algorithms introduce jitters in task instance execution, which leads to the degradation of speed of performance and stability of the system.

Sharing of the status of the real-time system and control status between them during design will lead to better real-time performance of the system without any degradation in the controller performance. Therefore the objective of this project to design Large error first (LEF) scheduling algorithm to schedule the real-time tasks.

Control system operations are divided into the following:

Measurement and the analog-to-digital conversion of the input signal.

Conversion of this to digital number.

This value is compared to a reference value.

Resulting error is used to find-out the command or control output.

This output value is converted into analog signal and applied to the process.

Above control operations are grouped into three tasks:

Data output.

Control tasks are again splitted into two: mandatory part and optional part. Mandatory part is the basic control algorithm, whereas the optional part is the algorithm for improving the performance of the system. Mandatory part is meant to provide better performance and is skipped for satisfaction of hard real-time tasks deadline under tight scheduling. The execution of optional part is determined by the activity of remaining time and the demand for soft sporadic load.

1) LEF Scheduling Algorithm

Most of the real-time scheduling algorithms are based on open-loop strategies that do not take application demands (control goals) into account. This precludes the scheduler to dynamically adjust task executions in order to optimize control performance. To overcome this limitation, Large Error First (LEF) scheduling algorithm [3] is used in this project.

The LEF scheduling algorithm is an online scheduling policy that assigns priorities according to the continuous feedback information. The feedback information used between the scheduler and each controlled plant at any point in time is the error. Error is an instantaneous measure of each controlled plant.

Therefore the definition of the LEF scheduling policy is the following: at any given time, the plant with largest error, ei (defined as the difference between the desired measurement of the system and the actual measurement of the system) will be assigned the highest priority.

Figure1. LEF scheduling policy

Data acquisition task.

Control task (control algorithm); and

Figure 1 shows the LEF scheduling policy, where

e1 and e2 are the error of task 1 and task 2

respectively. Here task 2 which have the largest error have the highest priority and is scheduled first.

Let p , p and p are the period (also the relative deadline) of periodic tasks T1 , T2 and T3 respectively in the increasing order of period. Therefore, by usin LEF scheduling policy, the periodic tasks will meet its deadline if the periodic

tasks are satisfied by the equation (1).

For this reason, worst case execution time of a job is taken as the execution time of a task for scheduling and other real-time operations.

4) Selection of Period

1

1

Z transform of an open-loop transfer function of a

first order system Gs is given by

s

n

n

xi 1

min h

(1)

Gz

hz z 1

(2)

i1

j1,2,,n j

where h is the sampling period.

It is important to note that all tasks involved in this project are nonpreemptive, and all sporadic tasks have hard deadlines.

1. Selection of Real-Time Task Parameters

   Then the error transfer function sampled first order system is

   Ez Rz

   EZ

   (3)

   of a

   The parameters of real-time periodic tasks Ti are

   1 Gz

   usually represented by Ti hi , xi , Di ,i , where hi ,

   where Rz is the Z transform of the input signal

   xi , Di and i are the period, execution time,

   of the system. If the input signal is the step function,

   absolute deadline and phase of the periodic task

   then the Z transform of the input signal is

   respectively. If absolute deadline Di is equal to z

   period hi and phase i is equal to zero, then the

   Rz (4)

   z 1

   parameter representation of a task is given by Ti hi , xi .

   Therefore the error transfer function (equation 3) becomes

   The error ei is a parameter of real-time tasks in

   this project because LEF scheduling algorithm is used as the scheduling algorithm which uses controller

   Ez

   z

   (5)

   error to schedule the tasks. Therefore the parameter

   h

   representation of a task Ti

   to T h , x , e .

   is modified

   z

   h

   i i i i

   The inverse Z transform of

   Ez gives the error

   Even if the value of error ei

   is dynamically

   function, which is

   assigned by the plant, the selection of other parameters of real-time tasks is important.

   ek

   k

   (6)

2. Selection of Execution Time

Execution time xi is the amount of time required to complete the execution of a job when it executes alone. The actual amount of time required by a job to complete its execution may vary for many reasons. For the purpose of determining whether each job can always complete by its deadline, knowing the maximum execution time of each job often suffices.

h h

It can be seen from equation (6) that the value of sampling period will change the value of error. Also change in sampling period will change the measurement lag, and increase in measurement lag is directly proportional to the sampling period h . Minimizing these effects by considering the

Utilization factor given in equation (7) gives optimal sampling period.

• Some jobs of the periodic tasks missed its deadline due to the presence of jitters, non

real-time tasks, etc.

x1 x 2 x3 U (7)

SP

SP

p h 2 p

where USP is the specified utilization factor. Therefore the optimization problem is given by

Due to the execution of all periodic tasks, sporadic tasks and aperiodic tasks, it is found that the sampling interval between two successive samples of a periodic task is differing from the optimal sampling period. But it is required to reduce this deviation to reduce the increase in error of process

min

e 2 h , k h

variable.

3

3

i i

hi i1 k0

i

SP

SP

(8)

3

3

st

i1

xi U hi

Solving the sum of squared error function in equation (8) modifies the optimization problem into

3 2

i

i

min i hi

hi i1

2i hi

• h 2

(9)

3

3

st

i1

xi U hi

Figure 2. LEF schedule

SP

SP

The dual optimization problem of equation (9) using Lagrangian multiplier is given by

Jitter is reduced to a greater extend by removing unwanted programs and commands. It is not easy to make the real-time systems free from the execution of

• h

• h

non real-time tasks.

2

2

3

3

i

3 xi

L hi ,

i

2 h h 2 h

• USP

4. Conclusion

i1 i i i

i1 i

This paper presents Real-time System for

(10)

where is the Lagrangian multiplier.

Equation (10) gives optimal sampling period shown in Table 1.

Table 1 Optimal Sampling Period

1. Analysis

   Figure 2 shows the performance analysis of LEF schedule. In this section, the performance of real-time section is analyzed and the problems found are:

   Centralized control system. The goals achieved by this project are listed below.

   • Schedules the control tasks without any degradation in controller performance.

   • Controller tasks are executed as soon as it is released. That is the jitter is reduced.

   • Maintains the sampling interval between two samples of a control task close to the optimal sampling period.

   • Scheduler ensures negligible deadline miss.

A format sheet with the margins and placement guides is available as both Word and PDF files as

<format.doc> and <format.pdf>. It contains lines and boxes showing the margins and print areas. If you

hold it and your printed page up to the light, you can easily check your margins to see if your print area fits within the space allowed.

5. References

1. Ch. Salzmann, D. Gillet & P. Huguenin, Introduction to Real-Time Control using LabView with an Application to Distance Learning, International Journal Engineering Edition Vol 16, No 2, pp. 255-272, 2000.

2. Pedro Albertos & Alfons Crespo, Real-Time Control and Non-uniformly Sampled Systems.

3. Jose Yepez, Josep M. Fuertes & Pau Marti, The Large Error First (LEF) Scheduling Policy for Real-Time Control Systems.

4. Anton Cervin, Johan Eker, Bo Bernhardsson & Karl-Erik Arzen, Feedback-Feedforward Scheduling of Control Tasks, Real-Time Systems 2002.

5. Christopher L. Bryant, Neeraj J. Gandhi, Real-Time Data Acquisition and Control System for the Measurement of Motor and Neural Data, Journal of Neuroscience Methods 142 (2005) 193-200.

6. Martin Torngren, Fundamentals of Implementing Real- Time Control Applications in Distributed Computer Systems, Real-Time Systems, 14, 219-250 (1998).

7. Patricia Balbastre & Ismael Ripoll, Schedulability Analysis of Window-Constrained Execution Time Tasks for Real-Time Control, Proceedings of the 14th Euromicro Conference on Real-Time Systems.