Deadline Assignment in a Distributed Soft Real Time System
- Assign local deadline to subtasks such that global deadline is met
- Soft real-time system (i.e., minimize number of deadlines that are missed)
- May not know how many computations ahead of times
- Computations may be complex and hard to predict task times
- Each subtask is submitted to some component, which may have local tasks that compete for resources with subtasks assigned there
- Subtask deadlines are assigned online (i.e., not known ahead of time); may depend on earlier subtasks, for example
- Scheduler at each component (or node) is independent of others. That is, each scheduler only decides based on the subtasks and deadlines that it has
- Components are unique; subtasks must be executed at a particular component and cannot be moved
- Network communication can be considered another task
- Ultimate deadline (UD): set subtask deadline equal to deadline of global task. Execution time of future subtasks are treated as slack for current subtask.
- Effective deadline (ED): deadline of global task minus total expected execution time of subtasks following the subtask. Slack of future subtasks treated as slack of current subtask.
- Equal slack (EQS): divide remaining slack equally among remaining subtasks
- Equal flexibility (EQF): divide remaining slack among subtasks in proportion to their predicted execution time
- All global tasks have fixed number of subtasks, m.
- k homogenous nodes in the system
- All nodes use earliest-deadline-first scheduling and there is no preemption
- Understand ratio of missed deadline under different loads and algorithms