Real-Time Scheduling of Parallel Task Graphs With Critical Sections Across Different Vertices

All existing work on real-time scheduling of parallel task graph models with shared resources assumes that a critical section must be contained inside a single vertex. However, this assumption does not hold in many realistic parallel real-time software. In this work, we conduct the first study on real-time scheduling and analysis of parallel task graphs where critical sections are allowed to cross different vertices. We show that allowing this may potentially lead to deadlocks and the so-called resource unrelated blocking time problem. We formalize the conditions for the deadlocks and resource unrelated blocking time to happen, and propose two different solutions to address them and develop corresponding schedulability analysis techniques. We conduct comprehensive experiments to evaluate our method. The results indicate that there is a significant impact to the system schedulability when tasks incur deadlock and resource unrelated blocking. Moreover, the schedulability can benefit from the execution of workload in parallel with critical sections if tasks can be carefully designed so that all deadlocks and resource unrelated blocking time can be avoided, and our methods are efficient to determine the schedulability of systems where critical sections across different vertices exist.

Automated summary

Previous studies on real-time scheduling assumed that critical sections must be contained within a single vertex, but this assumption does not hold in realistic parallel real-time software. In this work, the authors conducted the first study on scheduling and analysis of parallel task graphs where critical sections can cross different vertices. The study showed that allowing this may lead to deadlocks and resource unrelated blocking time problems, and proposed two solutions to address them and develop corresponding schedulability analysis techniques.