Journal of Northeastern University Natural Science ›› 2019, Vol. 40 ›› Issue (3): 315-320.DOI: 10.12068/j.issn.1005-3026.2019.03.003

• Information & Control • Previous Articles     Next Articles

Response Time Analysis of Multiprocessor Systems for DAG Parallel Tasks Based on G-EDF

HAN Mei-ling, DENG Qing-xu, ZHANG Tian-yu, LIN Yu-han   

  1. School of Computer Science & Engineering, Northeastern University, Shenyang 110169, China.
  • Received:2018-01-22 Revised:2018-01-22 Online:2019-03-15 Published:2019-03-08
  • Contact: DENG Qing-xu
  • About author:-
  • Supported by:
    -

Abstract: Since the self-structure of the DAG(directed acyclic graph)task is not considered, the schedulability analysis of the DAG parallel task model based on G-EDF(global earliest deadline first)is very pessimistic. The response time analysis of the DAG task set under the G-EDF scheduling strategy in multiprocessor systems was studied in this paper. First, a more accurate carry-in workload estimation method was proposed for the execution of the carry-in task instance. Then a method for estimating the problem window workload of completion time was put forward based on the carry-in workload estimation method. Based on the two proposed methods, this paper proposed a response time analyzing method to derive a response time upper bound of each task. The experiments show that the proposed method outperforms the state-of-the-art method by at least 15% and at most 25%.

Key words: embedded real-time systems, multiprocessors, parallel tasks model, global scheduling, response time analysis

CLC Number: