You are here: RTS-Portal>>Publications


Search Publications


An Efficient Method for Assigning Harmonic Periods to Hard Real-time Tasks with Period Ranges

Category: Conference
Author(s)Mitra Nasri, Gerhard Fohler
SourceEuromicro Conference on Real-Time Systems (ECRTS), IEEE Computer Society, pag.149-159.
Date Jul 2015


During the design phase of many real-time systems, designers often have a range of acceptable period values for which some levels of safety or quality of service are guaranteed. The choice of period values influences system schedulability and computational complexity of schedulability analysis, especially for the rate monotonic (RM) scheduling algorithm. It has been shown that RM guarantees 100% utilization if the periods are harmonic, i.e., each period is an integer multiple of shorter periods. In this paper, we address harmonic period assignment problem where each task has a given period range. We extend the results of our previous work and present an O(n2log(n)) algorithm (where n is the number of tasks) to verify necessary and sufficient conditions for the existence of a harmonic period assignment in cases where the previous solution has pseudo-polynomial computational complexity. We provide utilization bounds of the potential assignments as well as a heuristic algorithm to construct low utilization harmonic task sets. The efficiency of our period assignment algorithms has been evaluated in terms of acceptance ratio, task set utilization, data structure size, and the number of operations required for harmonic period assignment.


Upcoming Events
Currently no events
Latest News:
20.07.20 16:37
Our paper titled "Enabling Fog-based Industrial Robotics Systems" by Mohammed Shaik,...

17.07.20 12:25
Our paper titled "Distributed Decision-making for Safe and Secure Global Resource Management...

09.04.20 16:47
Dear students, things will run differently this semester, we are figuring out how we can...

All News