| 1. |
- Afshar, Sara, et al.
(författare)
-
Semi-partitioning under a Blocking-Aware Task Allocation
- 2015
-
Ingår i: Proceedings - Real-Time Systems Symposium. - 9781467395076 ; , s. 379-379
-
Konferensbidrag (refereegranskat)abstract
- Semi-partitioned scheduling is a resource efficient scheduling approach compared to the conventional multiprocessor scheduling approaches in terms of system utilization and migration overhead. Semi-partitioned scheduling can better utilize processor bandwidth compared to the partitioned scheduling while introducing less overhead compared to the global scheduling. Various techniques have been proposed to schedule tasks in a semi-partitioned environment, however, they have used blockingagnostic allocation mechanisms in presence of resource sharing protocols. Since, the allocation mechanism can highly affect the system schedulability, in this paper we provide a blocking-aware allocation mechanism for semi-partitioned scheduling framework under a suspension-based resource sharing protocol. We have applied new heuristics for sorting the tasks in the algorithm that shows improvements upon system schedulability. Finally, we present our preliminary results.
|
|
| 2. |
- Davis, Rob, et al.
(författare)
-
Quantifying the Exact Sub-Optimality of Non-Preemptive Scheduling
- 2015
-
Ingår i: Proceedings - Real-Time Systems Symposium. - 9781467395076 ; , s. 96-106
-
Konferensbidrag (refereegranskat)abstract
- Fixed priority scheduling is used in many real-time systems; however, both preemptive and non-preemptive variants (FP-P and FP-NP) are known to be sub-optimal when compared to an optimal uniprocessor scheduling algorithm such as preemptive Earliest Deadline First (EDF-P). In this paper, we investigate the sub-optimality of fixed priority non-preemptive scheduling. Specifically, we derive the exact processor speed-up factor required to guarantee the feasibility under FP-NP (i.e. schedulablability assuming an optimal priority assignment) of any task set that is feasible under EDF-P. As a consequence of this work, we also derive a lower bound on the sub-optimality of non-preemptive EDF (EDF-NP), which since it matches a recently published upper bound gives the exact sub-optimality for EDF-NP. It is known that neither preemptive, nor non-preemptive fixed priority scheduling dominates the other, i.e., there are task sets that are feasible on a processor of unit speed under FP-P that are not feasible under FP-NP and vice-versa. Hence comparing these two algorithms, there are non-trivial speedup factors in both directions. We derive the exact speed-up factor required to guarantee the FP-NP feasibility of any FP-P feasible task set. Further, we derive upper and lower bounds on the speed-up factor required to guarantee FP-P feasibility of any FP-NP feasible task set. Empirical evidence suggests that the lower bound may be tight, and hence equate to the exact speed-up factor in this case.
|
|
| 3. |
|
|
| 4. |
|
|
