Open Collections

Dynamic scheduling policies in a real-time main memory database system

University of British Columbia

In a real-time system, the overhead associated with scheduling algorithms can be a significant factor in the resulting schedule, in both normal and overload situations. This overhead may be due to the frequency of scheduling-algorithm invocations and to the execution time of the algorithm at each invocation. We investigate the trade-off in the dynamic scheduling of real-time tasks between the frequency at which the scheduling algorithm is invoked and the quality of the resulting schedules in terms of deadline compliance. We also look into the size of the task-set to which the scheduling policy is applied at every invocation. Furthermore, we study two overload management policies to improve the quality of resulting schedules in heavy load systems. We perform experimental evaluation of the algorithms in a real-time main memory database system. We propose a batching algorithm which, forms a batch of arrived tasks, then schedules and executes all tasks in a batch before considering other tasks that arrive in the mean time. The evaluation shows that our batching algorithms, also referred to as Batching Earliest Deadline First (BEDF) or Batching Least Slack First (BLSF) with respect to their used scheduling policy, EDF or LSF, outperform their non-batching counterparts under tighter time constraints. In this thesis, we also study the behavioral change of batching algorithms in overload conditions in comparison to normal load. We propose the Task Fusion (TF) overload management policy in order to avoid context switch overhead in heavy load situations. The other policy applied to the algorithms is a Not Tardy (NT) overload management policy, through which we improve the performance of EDF-based algorithms. Experiments show effective performance results due to employment of these overload management policies.

Thesis/Dissertation

application/pdf

2009-07-28

For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.

http://hdl.handle.net/2429/11412

Electrical and Computer Engineering

University of British Columbia

UBCV

DSpace