2026-08-03T00:50:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10757 2024-03-06T10:46:37Z ddc:004 open_access

Fast and Effective Multiframe-Task Parameter Assignment Via Concave Approximations of Demand Peng, Bo Fisher, Nathan Chantem, Thidapat generalized multiframe task model (GMF) generalized multiframe task model with parameter adaptation (GMF-PA) self-suspending tasks uniprocessor scheduling mixed-integer linear programming concave approximation linear programming Task parameters in traditional models, e.g., the generalized multiframe (GMF) model, are fixed after task specification time. When tasks whose parameters can be assigned within a range, such as the frame parameters in self-suspending tasks and end-to-end tasks, the optimal offline assignment towards schedulability of such parameters becomes important. The GMF-PA (GMF with parameter adaptation) model proposed in recent work allows frame parameters to be flexibly chosen (offline) in arbitrary-deadline systems. Based on the GMF-PA model, a mixed-integer linear programming (MILP)-based schedulability test was previously given under EDF scheduling for a given assignment of frame parameters in uniprocessor systems. Due to the NP-hardness of the MILP, we present a pseudo-polynomial linear programming (LP)-based heuristic algorithm guided by a concave approximation algorithm to achieve a feasible parameter assignment at a fraction of the time overhead of the MILP-based approach. The concave programming approximation algorithm closely approximates the MILP algorithm, and we prove its speed-up factor is (1+delta)^2 where delta > 0 can be arbitrarily small, with respect to the exact schedulability test of GMF-PA tasks under EDF. Extensive experiments involving self-suspending tasks (an application of the GMF-PA model) reveal that the schedulability ratio is significantly improved compared to other previously proposed polynomial-time approaches in medium and moderately highly loaded systems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bo Peng and Nathan Fisher and Thidapat Chantem 2019 Is Part Of LIPIcs, Volume 133, 31st Euromicro Conference on Real-Time Systems (ECRTS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ECRTS.2019.20 urn:nbn:de:0030-drops-107578 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2019.20 eng https://creativecommons.org/licenses/by/3.0/legalcode