×

Optimizing path real-time logic for unified real-time system. (English) Zbl 1425.68049

Summary: By simply describing a classic weakly hard real-time system’s performance with the number of tasks meeting or missing deadlines, the system’s real-time characteristics cannot be expressed accurately and its reliability cannot be established. The path real-time logic (RTL) is used to determine the reliability of real-time systems; though desirable, it cannot be used as a tool to configure an optimized real-time system. This paper introduces the notion of optimizing path RTL, where integer constants of arithmetic inequality in path RTL are replaced by integer constants or integer variables. With further modifications, optimizing path RTL can not only determine the reliability of a real-time system, but also be used to optimize the system. Furthermore, a unified framework for hard, soft and weakly hard real-time system is established based on optimizing path RTL. The process of transforming a weakly hard real-time system into this unified framework is demonstrated. Moreover, this work proposes and proves a theorem that if the directed ring of a constraint graph contains all elements of behaviour specification (SP) and only SP, then its value must not be greater than zero. This theorem can be used to quickly determine the reliability and safety of a real-time system. A case study is presented to show the validity and reliability of optimizing path RTL and the unified real-time system.

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
03B44 Temporal logic
68M15 Reliability, testing and fault tolerance of networks and computer systems
68Q60 Specification and verification (program logics, model checking, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alves D, NetoDaniel AC, Valcrcel F, Felton R, Lopez JM (2014) A new generation of real-time systems in the JET tokamak. IEEE Trans Nucl Sci 61(2):711-719 · doi:10.1109/TNS.2014.2308923
[2] Andrei S, Cheng AMK (2009) Efficient verification and optimization of real-time logic-specified systems. IEEE Trans Comput 58(12):1640-1653 · Zbl 1368.68178 · doi:10.1109/TC.2009.79
[3] Andrei S, Chin WN (2004) Incremental satisfiability counting for real-time systems, real-time and embedded technology and applications symposium, 2004. In: Proceedings. RTAS 2004, 10th IEEE, 482-489
[4] Bernat G, Burns A, Llamos A (2001) Weakly hard real-time systems. IEEE Trans Comput 50(4):308-321 · Zbl 1392.68114 · doi:10.1109/12.919277
[5] Chen J-M, Song Y, Sun Y (2006) Research on constraint specification of weakly hard real-time system. J Softw 17(12):2601-2608 · Zbl 1113.68480 · doi:10.1360/jos172601
[6] Contreras I, Yiyi Jiang J, Hidalgo I, Nunez-Letamendia L (2012) Using GPU-CPU architecture to speed up a ga-based real-time system for trading the stock market. Soft Comput 16(2):203-215 · doi:10.1007/s00500-011-0714-3
[7] Duan Q, Zeng J, Chakrabarty K (2015) Real-time production scheduler for digital-print-service providers based on a dynamic incremental evolutionary algorithm. IEEE Trans Autom Sci Eng 12(2):701-715 · doi:10.1109/TASE.2014.2304177
[8] Hamdaoui M, Ramanathan P (1995) A dynamic priority assignment technique for streams with (m, k)-firm deadlines. IEEE Trans Comput 44(12):1443-1451 · Zbl 1068.68618 · doi:10.1109/12.477249
[9] Heitmeyer CL, Labaw BG (1993) A benchmark for comparing different approaches for specifying and verifying real-time systems. Naval Research Lab, Washington, DC
[10] Jahanian F, Mok AKL (1986) Safety analysis of timing properties in real-time systems. IEEE Trans Softw Eng 12:890-904 · doi:10.1109/TSE.1986.6313045
[11] Jahanian F, Mok AKL (1987) A Graph-theoretic approach for timing analysis and its implementation. IEEE Trans Comput 36:961-975 · Zbl 0618.68008 · doi:10.1109/TC.1987.5009519
[12] Jahanian F, Stuart DA (1988) A method for verifying properties of modechart specifications. In: Proceedngs of the ninth IEEE real-time systems symposium, 12-21 · Zbl 1392.68114
[13] Lorraine EPR, Cheng AMK (1999) Timing analysis of the X-38 space station crew return vehicle avionics. Real-time technology and applications symposium, 1999. In: Proceedings of the fifth IEEE, 255-264
[14] Meng FL, Zeng XJ (2013) A Stackelberg game-theoretic approach to optimal real-time pricing for the smart grid. Soft Comp 17(12):2365-2380 · Zbl 1325.91037 · doi:10.1007/s00500-013-1092-9
[15] Mok AK, Tsou DC, de Rooij RCM (1996) The MSP. RTL real-time scheduler synthesis tool. In: 17th IEEE real-time systems symposium, 118-128
[16] Neto AC, Sartori F, Piccolo F, Vitelli R, De Tommasi G, Zabeo L (2010) MARTe: a multiplatform real-time framework. IEEE Trans Nucl Sci 57(2):479-486 · doi:10.1109/TNS.2009.2037815
[17] Niu L, Xu J ((2012) Improving schedulability and energy performance for weakly hard real-time systems, performance computing and communications conference (IPCCC), 2012 IEEE 31st international, 41-50
[18] Quellec G, Lamard M, Cochener B, Cazuguel G (2015) Real-time task recognition in cataract surgery videos using adaptive spatiotemporal polynomials. IEEE Trans Med Imaging 34(4):877-887 · doi:10.1109/TMI.2014.2366726
[19] Sahuquillo J, Hassan H, Petit S, March JL, Duato J (2016) A dynamic execution time estimation model to save energy in heterogeneous multicores running periodic tasks. Future Gen Comput Syst 56:211-219
[20] Singh Y, Popli M, Shukla SSP (2012) Energy reduction in weakly hard real time systems. Recent advances in information technology (RAIT). 2012 1st international conference on 2012, 909-915
[21] Tsai TH, Fan LF, Chen YS, Yao TS (2016) Triple speed: energy-aware real-time task synchronization in homogeneous multi-core systems. IEEE Trans Comput 65(4):1297-1309 · Zbl 1360.68110 · doi:10.1109/TC.2015.2441704
[22] Wang F, Mok AK (1994) RTL and refutation by positive cycles. FME’94: industrial benefit of formal methods, 659-680
[23] West R, Zhang Y, Schwan K, Poellabauer C (2004) Dynamic window-constrained scheduling of real-time streams in media servers. IEEE Trans Comput 53(6):744-759 · doi:10.1109/TC.2004.10
[24] West R, Schwan K, Poellabauer C (1999) Scalable scheduling support for loss and delay constrained media streams, real-time technology and applications symposium, 1999. In: Proceedings of the fifth IEEE, 24-33 · Zbl 1199.68028
[25] Wu N, Zhou M (2012) Schedulability analysis and optimal scheduling of dual-arm cluster tools with residency time constraint and activity time variation. IEEE Trans Autom Sci Eng 9:203-209 · doi:10.1109/TASE.2011.2160452
[26] Wu T, Jin S, Chen J-M (2008) A weakly hard real-time schedule algorithm based on cutting down. J Softw 19(7):1837-1846 · Zbl 1199.68028 · doi:10.3724/SP.J.1001.2008.01837
[27] Zhu X, Chang H, Yi Y, Tao Q (2010) Constraint specification of weakly hard real-time systems based on smooth scheduling. Comput Sci 37(3):204-207
[28] Zhu X, Chang H, Yi Y (2012) Novel weakly hard real-time system based on path RTL. J Chin Comput Syst 33(8):1862-1867
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.