Name
Title | ||
|---|---|---|
Job vs. portioned partitioning for the earliest deadline first semi-partitioned scheduling |
Abstract | ||
|---|---|---|
In this paper, we focus on the semi-partitioned scheduling of sporadic tasks with constrained deadlines and identical processors. We study two cases of semi-partitioning: (i) the case where the worst case execution time (WCET) of a job can be portioned, each portion being executed on a dedicated processor, according to a static pattern of migration; (ii) the case where the jobs of a task are released on a processor, 1 time out of p, where p is an integer at most equal to the number of processors, according to a round-robin migration pattern. The first approach has been investigated in the state-of-the-art by migrating a job at its local deadline, computed from the deadline of the task it belongs to. We study several local deadline assignment heuristics (fair, based on processor utilization and based on the minimum acceptable local deadline for a job on a processor). In both cases, we propose feasibility conditions for the schedulability of sporadic tasks scheduled using earliest deadline first (EDF) semi-partitioned scheduling. We show that the load function used for global scheduling to establish the feasibility of sporadic task sets exhibits interesting properties in the semi-partitioning context. We carry out simulations to study the performance of the two approaches in terms of success rate and number of migrations, for platforms composed of four and eight processors. We compare the performance of these semi-partitioned heuristics with the performance of classical partitioned scheduling algorithms and with a global scheduling heuristic which is currently considered to have good performances. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.sysarc.2011.02.008 | Journal of Systems Architecture - Embedded Systems Design |
Keywords | Field | DocType |
global scheduling heuristic,performance evaluation,multiprocessor,dedicated processor,sporadic task,local deadline,global scheduling,deadline assignment,minimum acceptable local deadline,semi-partitioned scheduling,portioned partitioning,edf,portioned scheduling,earliest deadline,real-time,classical partitioned scheduling algorithm,local deadline assignment heuristics,worst case execution time,real time,earliest deadline first,scheduling algorithm | Fixed-priority pre-emptive scheduling,Multiprocessor scheduling,Fair-share scheduling,Computer science,Parallel computing,Real-time computing,Priority inversion,Least slack time scheduling,Rate-monotonic scheduling,Earliest deadline first scheduling,Dynamic priority scheduling,Distributed computing | Journal |
Volume | Issue | ISSN |
57 | 5 | Journal of Systems Architecture |
Citations | PageRank | References |
7 | 0.51 | 43 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Laurent George | 1 | 214 | 29.39 |
| Pierre Courbin | 2 | 34 | 2.42 |
| Yves Sorel | 3 | 247 | 23.94 |