Publishing house Radiotekhnika

"Publishing house Radiotekhnika":
scientific and technical literature.
Books and journals of publishing houses: IPRZHR, RS-PRESS, SCIENCE-PRESS

Тел.: +7 (495) 625-9241


Chain blocking of tasks in real-time systems


V.V. Nikiforov – Dr. Sci. (Eng.), Professor, Leading Researcher, SPIIRAS V.I. Shkirtil – Ph. D. (Eng.), Associate Professor, Head of Laboratory, SPIIRAS

Software multitask applications for real-time systems shall be built in such a manner, that guaranty in-time task execution. A task which uses mutual resources may be blocked in the beginning of a code section, that realizes access to such resources (critical section). The blocking state is continued until the required resource is busy. In real-time systems the duration of task blocking state shall not cause excessively long response time for high priority tasks. In the case of use priority inheritance protocol the chain blocking may occur. The chain blocking means, that a waiting task is blocked by a set of tasks which are linked by chain of critical intervals dependencies. The paper proposes a method for description of dependencies between critical intervals in some tasks in the form of a directed multi-fraction graphs. Analysis of such multi-fraction graphs permits to find possible scenarios of the chain blocking and to estimate the chain blocking duration n the case of such scenarios.

  1. Liu C. L. and Layland J. W. Scheduling Algorithms for Multiprogramming in Hard Real-Time Environment // Journal of the ACM. 1973. V. 20. P. 46 – 61.
  2. T. Baker Multiprocessors EDF and Deadline Monotonic Schedulability Analysis. In Proceedings of 24 IEEE Real-Time Systems Symposium. 2003. R. 120 – 129.
  3. Nikiforov V. V. Vy'polnimost' prilozhenij real'nogo vremeni na mnogoyaderny'x proczessorax // Trudy' SPIIRAN. Pod red. R. M. Jusupova. Vy'p. 8. SPb.: Nauka. 2009. S. 255 – 284.
  4. Danilov M. V. Metody' planirovaniya vy'polneniya zadach v sistemax real'nogo vremeni // Programmny'e produkty' i sistemy'. 2001. № 4. S. 28 – 35.
  5. Nikiforov V. V., Pavlov V. A. Strukturny'e modeli dlya analiza mnogozadachny'x programmny'x sistem // Informaczionno-izmeritel'ny'e i upravlyayushhie sistemy'. 2011. № 9. S. 19 – 29.
  6. Nikiforov V. V., Shkirtil' V. I. Oczenka faktora blokirovaniya zadach v sistemax real'nogo vremeni na mnogoyaderny'x proczessorax // Trudy' SPIIRAN. Trudy' SPIIRAN. Pod red. R. M. Jusupova. Vy'p. 2 (25), SPb.: Nauka, 2013.
  7. Nikiforov V. V., Shkirtil' V. I. Sostavnoe blokirovanie vzaimosvyazanny'x zadach v sistemax na mnogoyaderny'x proczessorax // Izvestiya VUZov. Priborostroenie. 2012. № 1. S. 25 – 31.
  8. Nikiforov V. V., Shkirtil' V. I. Marshrutny'e seti – graficheskij formalizm predstavleniya struktury' programmny'x prilozhenij real'nogo vremeni // Trudy' SPIIRAN. Pod red. R. M. Jusupova. Vy'p. 14. SPb.: Nauka, 2010. S. 7 – 28.

June 24, 2020
May 29, 2020

© Издательство «РАДИОТЕХНИКА», 2004-2017            Тел.: (495) 625-9241                   Designed by [SWAP]Studio