A Practical Sub-Optimal Solution for the Dual Priority Scheduling Problem

Abstract : We consider uniprocessor platforms, the scheduling of synchronous implicit deadline periodic task sets and the dual priority scheme where each task is assigned two fixed priorities. That is, at run time each task starts executing using its primary priority and is promoted if not completed at an intermediate deadline. We present counter-intuitive examples illustrating how difficult this scheduling problemis. We propose a preprocessing approach to remove from the scheduling problem lowest priority viable tasks as defined by Audsley’s procedure. We revisit one solution called RM + RM conjectured optimal. We propose a procedure to compute promotion deadlines based on multiple simulations over an hyperperiod called FDMS. That solution has an exponential time complexity but an experimental success ratio of 100%. Then we propose a new sub-optimal solution to assign priorities called 1/RM + RM along with a very simple promotion deadline assignment scheme called RML for which no simulation are required, the procedure is simple and the success ratio is close to 99.99%. We show that the method is fast and scalable to very large task sets which makes it ideal for practical applications.
Document type :
Conference papers
Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-01804689
Contributor : Laurent George <>
Submitted on : Friday, June 1, 2018 - 9:21:22 AM
Last modification on : Wednesday, July 4, 2018 - 4:37:59 PM

Identifiers

  • HAL Id : hal-01804689, version 1

Citation

Tristan Fautrel, Laurent George, Joël Goossens, Damien Masson, Paul Rodriguez. A Practical Sub-Optimal Solution for the Dual Priority Scheduling Problem. 13th International Symposium on Industrial Embedded Systems (SIES'2018), Jun 2018, Gratz, Austria. ⟨hal-01804689⟩

Share

Metrics

Record views

192