ABSTRACT:
Mostly all real time scheduling algorithms are open loop algorithms. So it will not support all the real world problems. While algorithms such as Earliest Deadline Algorithms, Rate Monotonic and the spring scheduling algorithms are supporting comfortable important task set characteristics such as deadlines, precedence constraints, shared resource, jitter etc. Normally real time scheduling algorithms classified into two categories: static and dynamic. Static algorithm requires complete knowledge of task set and constraints whereas dynamic algorithm does not requires complete knowledge of task set. These two open loop algorithms works poorly in unpredictable dynamic systems. Normally all dynamic real world applications have insufficient resources and unpredictable work-load. So closed loop systems are suitable for facing this situation. The performance of CPU utilization is evaluated by using these algorithms into PID controller. Normally PID controller can provide stable control and it does not need any special analytical model. For dynamic system PID controller is suitable one. In this paper I present a feedback control real-time scheduling algorithms and its evaluation corresponding to PID controller with TORSCHE tool box where TORSCHE tool box is especially very much used for scheduling algorithms. TORSCHE (Time Optimisation, Resources, SCHEduling) Scheduling Toolbox for Matlab is a freely (GNU GPL) available toolbox developed at the Czech Technical University in Prague. Performance results demonstrate the effectiveness of the algorithm when execution time varies.
INTRODUCTION:
Based on the real time scheduling categories dynamic scheduling algorithms is suitable for unpredictable environments where as static algorithms need complete idea of the task set. Dynamic scheduling can be again classified into two categories: Resource Sufficient Environment and Resource Insufficient Environment. Resource sufficient environments requires sufficient resources is required for working. Earliest Deadline First(EDF) is an optimal dynamic scheduling algorithm in resource sufficient environments. EDF scheduling is most offer able one in real time scheduling.
All three algorithms must need complete knowledge of the task set what is going to be happening continuously. Those are not suitable for sudden variations in the real time situations. For example robotics, defenses, computational loading applications and other online changes applications. In all pervasive applications the input will receive from the sensors, it will not same predictable values always, it may be different unpredictable values also. For that situation these scheduling algorithms does not suitable.
The timing requirements is the another important problem. Because the timing requirement would be known and fixed. Always the open loop scheduling algorithms work with this fixed set of timing requirements. To solve these problems the only acceptable solution is feedback control real time scheduling.
KEY WORDS:
EDF: Earliest Deadline First, PID Controller: Proportional Integral Differential Controller, CPU: Control Processing Unit, RM: Rate Monotonic.
OVERVIEW:
The following architecture diagram is the basic architecture of feedback control system.
The architecture contains Controller, Actuators, Sensors, and Plant. The Controller which is used to controlled the variable. It has two input and one output. The two inputs are Set point, feedback. The Set point is used to the set the correct value of the controlled variable. The difference between the correct value of the controlled variable and the set point is the error.
Architecture of Feedback Control System:
The system is continuously monitor and compares the controlled variable to the set point which is known as the correct value to find the error. Based on the error value the controller calculates the required control value. The actuator is used to change the value of the manipulated variable of the system. Here the Scheduler as the PID controller. Because of the following reasons we choose PID control as the basic feedback control scheduling.
1. In control theory, the scheduling system is dynamic system
2. The PID controller does not need any analytic model.
3. Basic PID control can provide stable control in first and second order systems.
PID Controller:
In my project the PID controller is used to periodically monitors the controlled variable missratio and computes the CPU requested utilization.
The model for Feedback Control Scheduling:
The PID controller is used to help the scheduler as a stable one. It is normally done by
simulations. The Cp,Ci,Cd are the coefficients of PID controllers. The main parameters for the
simulations are 1. The SP is a constant sampling period 2.MissRatio the difference between the
system output and the controlled variable. 3.CPU’(Z) is the estimate CPU utilization. 4. CPU(Z)
is the actual CPU utilization. 5. ug(k) is the ratio of the actual total utilization to the estimation.
6. mrg(k) is the CPU utilization gain. 7. d(k) the disturbance. The estimated CPU utilization is
calculated by
CPU’(z) = ∆CPU’(z)/(z-1)
The actual requested utilization is calculated by
CPU(z) = ug(k)CPU’(z)
The missratio is calculated by
MissRatio(z) = mrg(k)CPU(z)-d(k)
Whereas the transfer function of the PID controller is:
H(z) = Cp + Ci/(z-1) + Cd(z-1)/z
The following diagram is the MATlab simulation model for calculating
missratio. The output is Fed back to the input to improve the CPU utilization and maintain less
missratio values.
Cp,Cd,Ci has taking as constant one value. ug(k),mrg(k) are both taking as different values and find the different missratio values. Based on this simulation we can justify the following things i.e., the estimated CPU utilization and the actual CPU utilization are approximately equal and there is no domino effect is happened. The coding for scheduling algorithms like EDF,RM are written by the TORSCHE toolbox. Then it is apply in to the controller to improve the CPU utilization. The comparative statement is shown by the graphical format. Compare to the two scheduling algorithms EDF scheduling algorithm could be proved as a good one.
CONCLUSION :
In this paper we are analyzing the closed loop real time scheduling systems. Based on this paper i can improve the CPU utilization and minimizing the missratio values. Because deadline missratio is directly controlled by the scheduler. The performances of two scheduling algorithms are taken and verified using TORSCHE scheduling toolbox. FC-EDF, Least and Latency scheduling algorithms are taken and compared in future. This paper mainly based on “Design and Evaluation of a Feedback Control EDF Scheduling Algorithm by Chenyang Lu, John A. Stankovic”. But I am using TORSCHE scheduling toolbox to shown the performance analysis.
References:
[1] B. Bouyssounouse, J. Sifakis, Embedded Systems Design: The ARTIST Roadmap for Research and Development, Springer, 2005.
[2] J. P. Loyall, “Emerging Trends in Adaptive Middleware and Its Application to Distributed Real-Time Embedded Systems”, Lecture Notes in Computer Science (LNCS), Vol. 2855, pp.20-34, 2003.
[3] K.-E. Årzén and A. Cervin, “Control and Embedded Computing: Survey of Research Directions”, Proc. 16th IFAC World Congress, Prague, Czech Republic, 2005.
[4] Feng Xia, Zhi Wang, and Youxian Sun, “Integrated Computation,Communication and control: Towards Next Revolution in Information Technology”, LNCS, Vol. 3356, pp.117-125, 2004.
[5] J. L. Hellerstein, “Challenges in Control Engineering of Computing Systems”, Proc. IEEE ACC, Massachusetts, July 2004, pp.1970-1979.
[6] Sha, L., T. Abdelzaher, K.-E. Årzén, T. Baker, A. Burns, G. Buttazzo, M. Caccamo, A. Cervin, J. Lehoczky, A. Mok, “Real-time scheduling theory: A historical perspective”, Real-time Systems, Vol.28, pp.101-155, 2004.
[7] C. Lu, J.A. Stankovic, G. Tao, S.H. Son, “Feedback control real-time scheduling: framework, modeling, and algorithms”, Real-time Systems, Vol.23, No.1/2, pp. 85-126, 2002.
[Abde98] T. F. Abdelzaher and Kang G. Shin, “End-host Architecture for QoS-Adaptive Communication” IEEE RTAS, June 1998.
[Becc99] G. Beccari, et. al., “Rate Modulation of Soft Real-Time Tasks in Autonomous Robot Control Systems”, EuroMicro Conference on Real-Time Systems, June 1999.
[Blev76] P. R. Blevins and C. V. Ramamoorthy, “Aspects of a dynamically adaptive operating systems”, IEEE Transactions on Computers, Vol. 25, No. 7, pp. 713-725, July 1976.
[Butt95] G. Buttazzo and J. A. Stankovic, “Adding Robustness in Dynamic Preemptive Scheduling”, Responsive Computer Systems: Steps Toward Fault-Tolerant Real-Time Systems (D. S. Fussell and M. Malek Ed.), Kluwer Academic Publishers, 1995.
[Gerb95] R. Gerber, S. Hong and M. Saksena, “Guaranteeing Real-Time Requirements with Resource-Based Calibration of Periodic Processes”, IEEE Transactions on Software Engineering, Vol. 21, No. 7, July 1995.
[Hari91] J. R. Haritsa, M. Livny and M. J. Carey, “Earliest Deadline Scheduling for Real-Time Database Systems”, IEEE RTSS, 1991.
[Jehu98] J. Jehuda and A. Israeli, “Automated Meta-Control for Adaptable Real-Time Software”, Real-Time Systems J., 14, 1998.
[Leho89] J. P. Lehoczky, L. Sha and Y. Ding, “The Rate Monotonic Scheduling Algorithm – Exact Characterization and Average Case Behavior”, IEEE RTSS, 1989.
[Li98] B. Li, K. Nahrstedt, “A Control Theoretical Model for Quality of Service Adaptations”, in IEEE International Workshop on Quality of Service, May 1998.
[Liu73] C. L. Liu and J. W. Layland, “Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment”, JACM, Vol. 20, No. 1, pp. 46-61, 1973.
TORSCHE Scheduling Toolbox for Matlab User’s Guide (Release 0.4.0).