Reinforcing Total Bandwidth Server with Multivalued WCET

As real-time embedded systems get more diverse and complicated, systems with different types of tasks (e.g., periodic and aperiodic tasks) are getting prevalent. In such systems, guaranteeing schedulability is important for hard periodic tasks while keeping response times of soft aperiodic requests short enough. Total Bandwidth Server (TBS) is one of the promising scheduling algorithms for hybrid task sets which include both periodic and aperiodic tasks. Basically, TBS follows the Earliest Deadline First algorithm, where tasks with earlier deadlines are prioritized for scheduling. This implies a promising opportunity for shortening response times of chosen tasks by assigning earlier deadlines. This paper describes a technique, stepwise deadline update, that moves deadlines earlier in the context of TBS. In this technique, a job execution is divided into two or more sub instances and each is given an individual deadline. The deadlines are calculated based on estimated execution times instead of a simple worst-case execution time (WCET). Considering that task's actual execution time is in most cases shorter than its WCET, that potentially improves such tasks responsiveness. For the estimated execution times of each task, this paper introduces multivalued WCET, a collection of possible and representative execution times of that task. The estimated execution times are obtained by static code analysis and abstract symbolic execution. The simulation-based evaluation shows that stepwise deadline update technique with multivalued WCET reduces average response times of aperiodic tasks. When the processor utilization is high, the reduction rate of aperiodic response times reaches 51.1% compared to traditional TBS, with negligible scheduling overhead.

As real-time embedded systems get more diverse and complicated, systems with different types of tasks (e.g., periodic and aperiodic tasks) are getting prevalent. In such systems, guaranteeing schedulability is important for hard periodic tasks while keeping response times of soft aperiodic requests short enough. Total Bandwidth Server (TBS) is one of the promising scheduling algorithms for hybrid task sets which include both periodic and aperiodic tasks. Basically, TBS follows the Earliest Deadline First algorithm, where tasks with earlier deadlines are prioritized for scheduling. This implies a promising opportunity for shortening response times of chosen tasks by assigning earlier deadlines. This paper describes a technique, stepwise deadline update, that moves deadlines earlier in the context of TBS. In this technique, a job execution is divided into two or more sub instances and each is given an individual deadline. The deadlines are calculated based on estimated execution times instead of a simple worst-case execution time (WCET). Considering that task's actual execution time is in most cases shorter than its WCET, that potentially improves such tasks responsiveness. For the estimated execution times of each task, this paper introduces multivalued WCET, a collection of possible and representative execution times of that task. The estimated execution times are obtained by static code analysis and abstract symbolic execution. The simulation-based evaluation shows that stepwise deadline update technique with multivalued WCET reduces average response times of aperiodic tasks. When the processor utilization is high, the reduction rate of aperiodic response times reaches 51.1% compared to traditional TBS, with negligible scheduling overhead.