Embedded Hard Real-Time Systems Scheduling: An Unmanned Ground Vehicle Case Study

• Raimundo Barreto UFAM
• Marília Neves UFPE
• Eduardo Tavares UFPE
• Paulo Maciel UFPE

Resumo

Finding a hard real-time feasible schedule is not trivial since this problem is NP-hard in its general form. There are two general approaches for scheduling tasks: runtime and pre-runtime scheduling. For many cases, runtime methods do not find a feasible schedule even if such a schedule exists. Such situations often occurs when the design model imposes intertask relations, such as precedence and exclusion relations. The method proposed in this work finds a pre-runtime scheduling, provided that one exists, using state space exploration. The main problem with such methods is the space size, which can grow exponentially. This paper applies minimization methods on the state space, and presents a depth-first search method on a timed labeled transition system derived from the time Petri net model. This model is a compact and precise representation of tasks, their relations and constraints.

Referências

Abdelzaher, T. F. and Shin, K. G. (1997). Comments on a pre-run-time scheduling algorithm for hard real-time systems. IEEE Trans. Soft. Engineering, 23(9):599–600.

Abdelzaher, T. F. and Shin, K. G. (1999). Combined task and message scheduling in distributed real-time systems. IEEE Trans. Parallel and Distributed Systems, 10(11):1179–1191.

Altisen, K., Göbler, G., Pnueli, A., Sifakis, J., Tripakis, S., and Yovine, S. (1999). A framework for scheduler synthesis. IEEE Real-Time System Symposium, pages 154–163.

Barreto, R., Maciel, P., Neves, M., Tavares, E., and Lima, R. (2004). A novel approach for off-line multiprocessor scheduling in embedded hard real-time systems. In IFIP Working Conference on Distributed and Parallel Embedded Systems (DIPES’04). IFIP World Computer Congress.

Fohler, G. (1994). Flexibility in Statically Scheduled Hard Real-Time Systems. PhD thesis, Technische Universität Wien, Institut für Technische Informatik, Treitlstr. Vienna, Austria.

Godefroid, P. (1994). Partial Order Methods for the Verification of Concurrent Systems: An Approach to the State-Explosion Problem. PhD Thesis, University of Liege.

Merlin, P. and Faber, D. J. (1976). Recoverability of communication protocols: Implicatons of a theoretical study. IEEE Transactions on Communications, 24(9):1036–1043.

Mok, A. K. (1983). Fundamental Design Problems of Distributed Systems for the Hard-Real-Time Environment. PhD Thesis, Dept Electrical Engineering and Computer Science, MIT.

Murata, T. (1989). Petri nets: Properties, analysis and applications. Proc. IEEE, 77(4):541–580.

Shepard, T. and Gagné, J. A. (1991). A pre-run-time scheduling algorithm for hard real-time systems. IEEE Trans. Soft. Engineering, 17(7):669–677.

Sieh, L., Haniak, P., and Richardson, P. (2001). Implementing transient fault tolerance in embedded real-time systems. In IEEE Electronics and Information Technology Conference.

Valmari, A. (1998). The state explosion problem. LNCS: Lectures on Petri Nets I: Basic Models, 1491:429–528.

Weber, M. and Kindler, E. (2003). The petri net markup language. LNCS. Advances in Petri Nets. Petri Net Technology for Communication Based Systems, 2472.

Xu, D., He, X., and Deng, Y. (2002). Compositional schedulability analysis of real-time systems using time petri nets. IEEE Trans. Soft. Engineering, 28(10):984–996.

Xu, J. and Parnas, D. (1990). Scheduling processes with release times, deadlines, precedence, and exclusion relations. IEEE Trans. Soft. Engineering, 16(3):360–369.

Xu, J. and Parnas, D. (1993). On satisfying timing constraints in hard real-time systems. IEEE Trans. Soft. Engineering, 1(19):70–84.