Scheduling Constrained-Deadline Sporadic Parallel Tasks Considering Memory Contention.

摘要

Consider constrained-deadline sporadic tasks scheduled on a multiprocessor where (i) each task is characterized by its execution requirement, deadline, and minimum inter-arrival time, (ii) each task generates a sequence of jobs, (iii) the execution requirement of a job and its potential for parallel execution is described by one or many stages with a stage having one or many segments and different segments in the same stage can execute in parallel and a segment is only allowed to start execution if all segments of previous stages have finished execution, and (iv) there is contention for shared resources in the memory system (cache eviction, reordering in memory controller, memory bus contention). We present an algorithm that (i) performs schedulability testing for tasks scheduled with global-Earliest-Deadline-First (gEDF), (ii) configures the virtual-to-physical address translation so that a cache block fetched to the last-level cache by one task cannot be evicted by another task, (iii) configures the virtual-to-physical address translation to attempt to eliminate the extra execution time caused by the reordering effect in the memory controller and if this is not possible, then the reordering effect is considered in the schedulability analysis, and (iv) considers the effect of contention for the memory bus. Our solution is based on formulating this problem as a Mixed-Integer Linear Program (MILP). We have implemented a tool based on this theory and validated its output against measurements on a real computer.