Back to search

University of British Columbia

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

Abstract

dc:description

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.

Degree

thesis:*
Name thesis:degree_name
Master of Applied Science - MASc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Electrical and Computer Engineering
Grantor dc:publisher
University of British Columbia
Year dc:date
2001

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Moghaddas, Maryam

Rights

dc:rights
Statement dc:rights
  • 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.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/11412

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Moghaddas, Maryam. Dynamic scheduling policies in a real-time main memory database system. master's thesis, University of British Columbia, 2001. http://hdl.handle.net/2429/11412