<p>When modeling the dependencies of parallel real-time tasks using directed acyclic graphs (DAGs), the execution order of nodes is critical to meet stringent timing constraints. Traditional priority list scheduling algorithms rely on local heuristic information, overlooking the complex dependencies and parallelism between tasks. This leads to a longer makespan and conservative worst-case response time bound. To tackle this issue, this study proposes a priority list scheduling algorithm based on dependency-driven non-critical nodes parallelism factor. By deeply analyzing task dependencies, the algorithm optimizes the node execution order to maximize global parallelism, thereby reducing makespan. Additionally, it integrates two response time analysis methods to derive a tighter bound on response time, supporting scalability for multi-DAG task scenarios. Experimental results demonstrate that the proposed method significantly outperforms four similar algorithms across various task graph structures and parameter configurations.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Priority list scheduling algorithm for response time analysis optimization using dependency-driven non-critical nodes parallelism factor

  • Yian Zhu,
  • Jiaqi Wang,
  • Lian Li

摘要

When modeling the dependencies of parallel real-time tasks using directed acyclic graphs (DAGs), the execution order of nodes is critical to meet stringent timing constraints. Traditional priority list scheduling algorithms rely on local heuristic information, overlooking the complex dependencies and parallelism between tasks. This leads to a longer makespan and conservative worst-case response time bound. To tackle this issue, this study proposes a priority list scheduling algorithm based on dependency-driven non-critical nodes parallelism factor. By deeply analyzing task dependencies, the algorithm optimizes the node execution order to maximize global parallelism, thereby reducing makespan. Additionally, it integrates two response time analysis methods to derive a tighter bound on response time, supporting scalability for multi-DAG task scenarios. Experimental results demonstrate that the proposed method significantly outperforms four similar algorithms across various task graph structures and parameter configurations.