Deferrable Scheduling for Maintaining Real-Time Data Freshness: Algorithms, Analysis, and Results

The periodic update transaction model has been used to maintain the freshness (or temporal validity) of real-time data. Period and deadline assignment has been the main focus of past studies, such as the More-Less scheme [25], in which update transactions are guaranteed by the Deadline Monotonic scheduling algorithm [16] to complete by their deadlines. In this paper, we propose a deferrable scheduling algorithm for fixed-priority transactions, a novel approach for minimizing update workload while maintaining the temporal validity of real-time data. In contrast to prior work on maintaining data freshness periodically, update transactions follow an aperiodic task model in the deferrable scheduling algorithm. The deferrable scheduling algorithm exploits the semantics of temporal validity constraint of real-time data by judiciously deferring the sampling times of update transaction jobs as late as possible. We present a theoretical estimation of its processor utilization and a sufficient condition for its schedulability. Our experimental results verify the theoretical estimation of the processor utilization. We demonstrate through the experiments that the deferrable scheduling algorithm is an effective approach and it significantly outperforms the More-Less scheme in terms of reducing processor workload.

1 Introduction

Real-time and embedded systems are applied in many application domains that require timely processing of a massive amount of real-time data. Examples of real-time data include sensor data in sensor networks, positions of aircraft in air traffic control systems [14], and vehicle velocity in adaptive cruise control applications [6]. Such real-time data are typically managed in a real-time database system (RTDBS). Those data values are used to model the current status of entities in a system environment. However, real-time data are different from traditional data in that they have time semantics in which sampled values are valid only for a certain time interval [19], [18], [23]. The concept of temporal validity is used to define the correctness of real-time data [19]. A real-time data object is fresh (or temporally valid) if its value truly reflects the current status of the corresponding entity in the system environment. Each real-time data object is associated with a validity interval as the lifespan of the current data value defined based on the dynamic properties of the data object. A new data value needs to be installed into the database before the validity interval of the old value expires, that is, the old one becomes temporally invalid. Otherwise, the RTDBS cannot detect and respond to environmental changes in a timely manner. In recent years, there has been a tremendous amount of work devoted to this area [5], [1], [12], [14], [30], [19], [20], [21], [22], [26], [11], [25], [8].