On earliest deadline first scheduling for temporal consistency maintenance |
| |
Authors: | Ming Xiong Qiong Wang Krithi Ramamritham |
| |
Affiliation: | (1) Bell Laboratories, Alcatel-Lucent, Murray Hill, USA;(2) India Institute of Technology Bombay, Powai, India |
| |
Abstract: | A real-time object is one whose state may become invalid with the passage of time. A temporal validity interval is associated
with the object state, and the real-time object is temporally consistent if its temporal validity interval has not expired. Clearly, the problem of maintaining temporal consistency of data is motivated
by the need for a real-time system to track its environment correctly. Hence, sensor transactions must be able to execute
periodically and also each instance of a transaction should perform the relevant data update before its deadline.
Unfortunately, the period and deadline assignment problem for periodic sensor transactions has not received the attention
that it deserves. An exception is the More-Less scheme, which uses the Deadline Monotonic (DM) algorithm for scheduling periodic sensor transactions. However, there is no work addressing this problem from the perspective
of dynamic priority scheduling. In this paper, we examine the problem of temporal consistency maintenance using the Earliest Deadline First (EDF) algorithm in three steps:
First, the problem is transformed to another problem with a sufficient (but not necessary) condition for feasibly assigning
periods and deadlines. An optimal solution for the problem can be found in linear time, and the resulting processor utilization is characterized and compared to a traditional approach. Second, an algorithm to
search for the optimal periods and deadlines is proposed. The problem can be solved for sensor transactions that require any
arbitrary deadlines. However, the optimal algorithm does not scale well when the problem size increases. Hence, thirdly, we
propose a heuristic search-based algorithm that is more efficient than the optimal algorithm and is capable of finding a solution
if one exists.
|
| |
Keywords: | Real-time databases Temporal consistency Earliest deadline first |
本文献已被 SpringerLink 等数据库收录! |
|