MILP-based Deadline Assignment for End-to-End Flows in Distributed Real-Time Systems
- Most real-time systems schedule subtasks by first calculating deadlines for subtasks and then scheduling subtasks using some real-time algorithm (e.g., EDF)
- Reduce how pessimistic (being too conservative (i.e., something can’t be scheduled when in fact it can)) algorithm is for admission control (schedulability analysis) by jointly considering deadline and priority assignment.
- Introduce ‘distributed generalized multiframe task model with parameter adaption’ (see below)
- Multiframe task model (MF) (link): a task that generates an infinite succession of frames where the ready times of consecutive frames is at least some P time units apart and the execution time of the ith frame is chosen cyclically from some vector of execution times E of length N (i.e., choose execution time i mod N). The deadline of each frame is equal to P time units after the ready time (implied deadline)
- Generalized multiframe task model (GMF) (link): same as above, but
- Assume that deadlines of frames can differ from the minimum separation
- The minimum separation between frames need not be the same
- Generalized multiframe task model with parameter adaptation (GMF-PA) (link): Consider a set of n GMF tasks on a uniprocessor system. Each task has its own period with execution times for each frame as well as upper / lower bounds for deadline and inter-arrival period. The frames execute in a cycle indefinitely.
- Distributed generalized multiframe task model with parameter adaption (dGMF-PA) (this paper): each task is now split into some number of virtual tasks that run on different processors. dGMF-PA reduces to GMF-PA if there is only one processor.