An abstraction-refinement framework for priority-driven scheduling of static dataflow graphs

Static dataflow graphs are widely used to model concurrent real-time streaming applications. Though the state of the art usually advocates static-periodic scheduling of dataflow graphs over dynamic scheduling, the interest in dynamic (for instance, priority-driven) scheduling of dataflow graphs has been rekindled by the increasing use of virtualization technology and real-time operating systems to manage concurrent independent applications running on the same platform. This paper presents a sequence-based framework in which a large class of priority-driven schedules of dataflow graphs can be uniformly expressed and analyzed. Constructed schedules should be buffer-safe (i.e. no overflow/underflow exceptions over communication channels) even in the worst-case admission scenario of incoming applications and tasks. In addition, and to our knowledge for the first time, the paper formulates this scheduling theory in abstraction-refinement framework, to allow for the construction of feasible and buffer-safe priority-driven schedules based on mathematically sound approximations of physical time in priority-driven schedules.