The design of embedded real-time systems (RTS) is challenging due to the criticality of the timing constraints of these systems. Various informal and formal methods for RTS design have been proposed, both in the design space and the real-time execution at the hardware level, but many of these methods are not effective when the complexity of the system scales up. Here, we discuss a new method to integrate a modeling (and simulation) formalism that allows designing complex systems specifications for real-time constraints called Imprecise-DEVS (I-DEVS), and the mapping of such high-level models into a real-time task model. This method allows analyzing real-time constraints both at the high level of modeling as well as the low level of the tasks executed by the processing units and the Operating System. A new method to study the schedulability of the task models is proposed. The method provides a design analysis space from the model level, up to the individual tasks, with a focus on the schedulability of real-time constraints under transient overloading conditions.
FelderMPezzèM.A formal design notation for real-time systems. ACM T Softw Eng Meth2002; 11: 149–190.
3.
HaurIBéchennecJRouxO. Formal schedulability analysis based on multi-core RTOS model. In: 29th international conference on real-time networks and systems, Nantes, 7–9 April 2021, pp. 216–225. Nantes: Association for Computing Machinery.
4.
DavisRBurnsA.A survey of hard real-time scheduling for multiprocessor systems. ACM Comput Surv2011; 43: 1–44.
5.
DavisR.A review of fixed priority and EDF scheduling for hard real-time uniprocessor systems. ACM SIGBED Rev2014; 11: 8–19.
6.
MoallemiMWainerG. Designing an interface for real-time and embedded DEVS. In: Spring simulation multiconference (SpringSim ’10), Orlando, FL, 11–15 April 2010, pp. 1–8. San Diego, CA: Society for Computer Simulation International.
ZeiglerBPraehoferHKimT.Theory of modeling and simulation: integrating discrete event and continuous complex dynamic systems. 2nd ed.San Diego, CA: Academic Press, 2000.
9.
LiuJShihWLinK, et al. Imprecise computations. P IEEE1994; 82: 83–94.
10.
RamanathanP.Graceful degradation in real-time control applications using (m, k)-firm guarantee. In: IEEE 27th international symposium on fault tolerant computing, Seattle, WA, 24–27 June 1997, pp. 132–141. New York: IEEE.
11.
LinKNatarajanSLiuJ.Imprecise results: utilizing partial computations in real-time systems. In: IEEE 8th real-time systems symposium, San Jose, CA, 1–3 December 1987, pp. 210–217. New York: IEEE.
12.
LiuJLinKShihW, et al. Algorithms for scheduling imprecise computations. Computer1991; 24: 58–68.
13.
MoallemiMWainerG.I-DEVS: imprecise real-time and embedded DEVS modeling. In: Symposium on theory of modeling & simulation: DEVS integrative M&S symposium, Boston, MA, 3–7 April 2011, pp. 95–102. Boston, MA: The Society for Modeling and Simulation International.
14.
WainerGMoallemiM.Designing real-time systems using imprecise discrete-event system specifications. Softw: Pract Exper2020; 50: 1327–1344.
15.
ZhangFBurnsA.Schedulability analysis for real-time systems with EDF scheduling. IEEE T Comput2009; 58: 1250–1258.
RipollICrespoAMokA.Improvement in feasibility testing for real-time tasks. Real-Time Syst1996; 11: 19–39.
18.
WilhelmREngblomJErmedahlA, et al. The worst—case execution—time problem—overview of methods and survey of tools. ACM T Embed Comput S2008; 7: 1–53.
19.
AlshareefASarjoughianH. Simulation, model checking, and execution of activity models. arXiv:2105.11851v1 [cs.SE], 2021, https://arxiv.org/abs/2105.11851
20.
FersmanEPetterssonPYIW.Timed automata with asynchronous processes: schedulability and decidability. In: International conference on tools and algorithms for the construction and analysis of systems, Grenoble, 8–12 April 2002, pp. 67–82. Berlin: Springer.
21.
SaadawiHWainerG.Principles of DEVS models verification. Simul: T Soc Mod Sim2013; 89: 41–67.
22.
LiuCLaylandJ.Scheduling algorithms for multiprogramming in a hard-real-time environment. J ACM1973; 20: 46–61.
23.
KuoTChangLLiuY, et al. Efficient online schedulability tests for real-time systems. IEEE T Software Eng2003; 29: 734–751.
24.
ZhangFBurnsA.Schedulability analysis of EDF-scheduled embedded real-time systems with resource sharing. ACM T Embed Comput S2013; 12: 1–19.
25.
LeeHChoiJ.Constraint solving approach to schedulability analysis in real-time systems. IEEE Access2018; 6: 58418–58426.
26.
ShaLAbdelzaherTArzénK, et al. Real time scheduling theory: a historical perspective. Real-Time Syst2004; 28: 101–155.
27.
BurnsAWellingsA.Implementing analysable hard real-time sporadic tasks in Ada 9X. ACM Sigada Ada Lett1994; XIV: 38–49.
28.
ButtazzoG.Rate monotonic vs. EDF: judgment day. Real-Time Syst2005; 29: 5–26.
29.
RamamrithamKStankovicJ.Scheduling algorithms and operating systems support for real-time systems. P IEEE1994; 82: 55–67.
30.
BakerT.Multiprocessor EDF and deadline monotonic schedulability analysis. In: 24th IEEE real-time systems symposium, Cancun, Mexico, 5 December 2003, pp. 120–129. New York: IEEE.
31.
BernatGColinAPettersS. WCET analysis of probabilistic hard real-time systems. In: 23rd IEEE real-time systems symposium, Austin, TX, 3–5 December 2002, pp. 279–288. New York: IEEE.
32.
EdgarSBurnsA. Statistical analysis of WCET for scheduling. In: 22nd IEEE real-time systems symposium (RTSS 2001), London, 3–6 December 2001, pp. 215–224. New York: IEEE.
33.
BeckerMChakrabortyS. 21st international workshop on software and compilers for embedded systems. In: 21st international workshop on software and compilers for embedded systems, Sankt Goar, 28–30 May 2018, pp. 10–13. New York: Association for Computing Machinery.
34.
MengFSunHWangJ. Survey on estimation and optimization of worst-case execution time with energy consumption constraint. In: 12th international conference on computational intelligence and communication networks (CICN), Bhimtal, India, 25–26 September 2020, pp. 316–320. New York: IEEE.
35.
GunzelMvon der BruggenGChenJ.Suspension-aware earliest-deadline-first scheduling analysis. IEEE T Comput Aid D2020; 39: 4205–4216.
36.
SunYLipariG. A weak simulation relation for real-time schedulability analysis of global fixed priority scheduling using linear hybrid automata. In: 22nd international conference on real-time networks and systems, Versailles, 8–10 October 2014, pp. 35–44. New York: Association for Computing Machinery.
37.
GuoZBhuiyanALiuD, et al. Energy-efficient real-time scheduling of DAGs on clustered multi-core platforms. In: IEEE real-time and embedded technology and applications symposium (RTAS), Montreal, QC, Canada, 16–18 April 2019, pp. 156–168. New York: IEEE.
38.
JosephMPandyaP.Finding response times in a real-time system. Comput J1986; 29: 390–395.
39.
MoghadamMSaadatmandMBorgM, et al. Learning-based response time analysis in real-time embedded systems: a simulation-based approach. In: IEEE/ACM 1st international workshop on software qualities and their dependencies (SQUADE), Gothenburg, May 2018, pp. 21–24. New York: IEEE.
HuangLHouISapatnekarS, et al. Graceful degradation of low-criticality tasks in multiprocessor dual-criticality systems. In: 26th international conference on real-time networks and systems, Chasseneuil-du-Poitou, October 2018, pp. 159–169. New York: Association for Computing Machinery.
42.
StavrinidesGKaratzaH.Fault-tolerant gang scheduling in distributed real-time systems utilizing imprecise computations. SIMULATION2009; 85: 525–536.
43.
HuangLLiYSapatnekarS, et al. Using imprecise computing for improved non-preemptive real-time scheduling. In: 55th ACM/ESDA/IEEE design automation conference (DAC), San Francisco, CA, 24–28 June 2018, pp. 1–6. New York: IEEE.
44.
GuoCZhuCTayT.Design and simulation of a green broker with imprecise computation scheduling for energy-efficient large scale computing in clusters. J Emerg Trends Comput Inf Sci2013; 4: 900–907.
45.
EsmailiANazemiMPedramM.Energy-aware scheduling of task graphs with imprecise computations and end-to-end deadlines. ACM T Des Automat El2020; 25: 1–21.
46.
StavrinidesGKaratzaH.A cost-effective and QoS-aware approach to scheduling real-time workflow applications in PaaS and SaaS clouds. In: 3rd international conference on future internet of things and cloud, Rome, 24–26 August 2015, pp. 231–239. New York: IEEE.
47.
PazzagliaPSunYNataleM.Generalized weakly hard schedulability analysis for real-time periodic tasks. ACM T Embed Comput S2021; 20: 1–26.
48.
HongJSongHKimT, et al. A real-time discrete event system specification formalism for seamless real-time software development. Discrete Event Dyn S1997; 7: 355–375.
49.
MoallemiMWainerG.Modeling and simulation-driven development of embedded real-time systems. Simul Model Pract Th2013; 38: 115–131.
50.
MelloBWainerG.Scheduling predictability in I-DEVS by schedulability analysis. In: Symposium on theory of modeling and simulation, Pasadena, CA, 3–6 April 2016, pp. 1–8. New York: IEEE.
51.
ManolacheSElesPPengZ.Schedulability analysis of applications with stochastic task execution times. ACM T Embed Comput S2004; 3: 706–735.
52.
NasriMBaruahSFohlerG, et al. On the optimality of RM and EDF for non-preemptive real-time harmonic tasks. In: 22nd international conference on real-time networks and systems, Versailles, 8–10 October 2014, pp. 331–340. New York: Association for Computing Machinery.
53.
KimKKangWSagongB, et al. Efficient distributed simulation of hierarchical DEVS models: transforming model structure into a non-hierarchical one. In: 33rd annual simulation symposium (SS 2000), Washington, DC, 16–20 April 2000, pp. 227–233. New York: IEEE.
54.
ShangHWainerG. Dynamic structure DEVS: improving the real-time embedded systems simulation and design. In: 41st annual simulation symposium, Ottawa, ON, Canada, 13–16 April 2008, pp. 271–278. New York: IEEE.
55.
ChowAZeiglerBKimD. Abstract simulator for the parallel DEVS formalism. In: Fifth annual conference on AI, and planning in high autonomy systems, Gainesville, FL, 7–9 December 1994, pp. 157–163. New York: IEEE.
