An efficient schedulability condition for non-preemptive real-time systems at common scheduling points

详细信息    查看全文

• 作者：Saleh Alrashed ; Jamal Alhiyafi ; Aamir Shafi…
• 关键词：Real ; time systems ; Non ; preemptive scheduling ; Fixed ; priority scheduling ; Feasibility analysis ; Online schedulability tests
• 刊名：The Journal of Supercomputing
• 出版年：2016
• 出版时间：December 2016
• 年：2016
• 卷：72
• 期：12
• 页码：4651-4661
• 全文大小：467 KB
• 刊物类别：Computer Science
• 刊物主题：Programming Languages, Compilers and Interpreters
  Processor Architectures
  Computer Science, general
  
• 出版者：Springer Netherlands
• ISSN：1573-0484
• 卷排序：72

文摘

Earliest deadline first (EDF) scheduling algorithm is the most celebrated result for dynamic priority scheduling in real-time systems for both preemptive and non-preemptive cases. From complexity point of view, EDF is polynomial for preemptive scheduling of tasks; however, it becomes pseudo-polynomial under non-preemptive case. In this paper, we propose a technique that determines EDF feasibility of non-preemptive task set by analyzing schedulability of the lowest priority task at common scheduling points generated by all higher priority tasks in the task set. This adjustment results in improving the computational cost of an existing test from \(O(n^2 p_n/p_1)\) to \(O(p_n/p_1)\), where n is the number of tasks in the system, while \(p_n\) and \(p_1\) represent the task periods of largest and smallest periodic tasks respectively. With reduced computation cost, we understand that our technique has the potential to be intergraded with online systems for testing feasibility of a special class of real-time systems under non-preemptive case.