Scheduling of hard real-time multi-phase multi-thread (MPMT) periodic tasks

被引:15
作者
Courbin, Pierre [1 ]
Lupu, Irina [2 ]
Goossens, Joel [2 ]
机构
[1] ECE Paris, LACSC Lab, F-75015 Paris, France
[2] Univ Libre Bruxelles, PARTS Res Ctr, B-1050 Brussels, Belgium
关键词
Real-time systems; Parallel task; Fork-join; Scheduling; Gang; Feasibility interval; Periodic; Multiprocessor; Multi-phase multi-thread; Hierarchical scheduler; Global thread scheduler; SCHEDULABILITY;
D O I
10.1007/s11241-012-9173-x
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
In this paper we study the scheduling of parallel and real-time recurrent tasks on multiprocessor platforms. Firstly, we propose a new parallel task model which allows recurrent tasks to be composed of several phases, each one composed of several threads. Each thread requires a single processor for execution and can be scheduled simultaneously. We then propose an algorithm to transpose popular Fork-Join task model to our MPMT task model. Secondly, we define several kinds of real-time schedulers that can be applied to our parallel task model. We distinguish between two scheduling classes: Hierarchical schedulers and Global Thread schedulers. We present and prove correct an exact schedulability test for each class. Lastly, we also evaluate the performance of our scheduling paradigm in comparison with Gang scheduling by means of simulations. In this work we extend the work of Lupu and Goossens in Scheduling of hard real-time multi-thread periodic tasks (Real-Time and Network Systems, 2011) which considers mono-phase multi-thread task model. We extend their previous results to a Multi-Phase Multi-Thread task model.
引用
收藏
页码:239 / 266
页数:28
相关论文
共 23 条
[1]  
Audsley N.C., 1991, P 8 IEEE WORKSHOP RE, P133
[2]  
Baker T., 2007, Handbook of Realtime and Embedded Systems
[3]   Analysis of EDF schedulability on a multiprocessor [J].
Baker, TP .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2005, 16 (08) :760-768
[4]  
Bastoni Andrea., 2010, P 6 INT WORKSHOP OPE, P33
[5]  
Chandra R., 2001, Parallel programing in OpenMP, DOI DOI 10.5555/355074
[6]   Integrating job parallelism in real-time scheduling theory [J].
Collette, Sebastien ;
Cucu, Liliana ;
Goossens, Joel .
INFORMATION PROCESSING LETTERS, 2008, 106 (05) :180-187
[7]   Exact schedulability tests for real-time scheduling of periodic tasks on unrelated multiprocessor platforms [J].
Cucu-Grosjean, Liliana ;
Goossens, Joel .
JOURNAL OF SYSTEMS ARCHITECTURE, 2011, 57 (05) :561-569
[8]   MULTIPROCESSOR ONLINE SCHEDULING OF HARD-REAL-TIME TASKS [J].
DERTOUZOS, ML ;
MOK, AKL .
IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 1989, 15 (12) :1497-1506
[9]  
Feitelson D. G., 1996, Job Scheduling Strategies for Parallel Processing. IPPS '96 Workshop Proceedings, P89, DOI 10.1007/BFb0022289
[10]  
Goossens Joel., 2010, 18 INT C REAL TIME N, P189