A process algebraic approach to the schedulability analysis and workload abstraction of hierarchical real-time systems

Junkil Park, Insup Lee, Oleg Sokolsky, Dae Yon Hwang, Sojin Ahn, Jin Young Choi, Inhye Kang

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)


Real-time embedded systems have increased in complexity. As microprocessors become more powerful, the software complexity of real-time embedded systems has increased steadily. The requirements for increased functionality and adaptability make the development of real-time embedded software complex and error-prone. Component-based design has been widely accepted as a compositional approach to facilitate the design of complex systems. It provides a means for decomposing a complex system into simpler subsystems and composing the subsystems in a hierarchical manner. A system composed of real-time subsystems with hierarchy is called a hierarchical real-time system. This paper describes a process algebraic approach to schedulability analysis of hierarchical real-time systems. To facilitate modeling and analyzing hierarchical real-time systems, we conservatively extend an existing process algebraic theory based on ACSR-VP (Algebra of Communicating Shared Resources with Value-Passing) for the schedulability of real-time systems. We explain a method to model a resource model in ACSR-VP which may be partitioned for a subsystem. We also introduce schedulability relation to define the schedulability of hierarchical real-time systems and show that satisfaction checking of the relation is reducible to deadlock checking in ACSR-VP and can be done automatically by the tool support of VERSA (Verification, Execution and Rewrite System for ACSR). With the schedulability relation, we present algorithms for abstracting real-time system workloads.

Original languageEnglish
Pages (from-to)1-18
Number of pages18
JournalJournal of Logical and Algebraic Methods in Programming
Publication statusPublished - 2017 Nov

Bibliographical note

Publisher Copyright:
© 2017 Elsevier Inc.


  • ACSR
  • Hierarchical Scheduling
  • Process algebra
  • Real-time embedded systems

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Logic
  • Computational Theory and Mathematics


Dive into the research topics of 'A process algebraic approach to the schedulability analysis and workload abstraction of hierarchical real-time systems'. Together they form a unique fingerprint.

Cite this