Scientific progress goes 'boink'

Ph.D. Candidate

Princeton University

Department of Computer Science

(link)

- 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.