Jianjun Li, Jian-Jia Chen, Ming Xiong, Guohui Li

会议

会议名称： RTSS

举办地点：2011

所在页数：126-135

摘要

Deriving deadlines and periods of update transactions for maintaining timeliness and data freshness has long been recognized as an important problem in real-time database research. Despite years of active research, the state of the art only focuses on uniprocessor systems. In this paper, we take a first step of studying the workload-aware temporal consistency maintenance problem upon multiprocessor platforms. We consider the problem of how to partition a set of update transactions to m ≥ 2 processors to maintain the temporal consistency of real-time data objects under earliest deadline first (EDF) scheduling, while minimizing the total workload on m processors. Firstly, we only consider the feasibility aspect of the problem by proposing a polynomial time partitioning scheme, Temporal Consistency Partitioning (TCP), and formally showing that the resource augmentation bound of TCP is (3 - 1/m). Secondly, we address the partition problem globally by proposing a polynomial time heuristic, Density factor Balancing Fit (DBF), where density factor balancing plays a major role in producing workload-efficient partitionings. Finally, we evaluate the feasibility and workload performances of DBF versus other heuristics with comparable quality experimentally.

关键词

Real-Time Databases; Temporal Consistency;

 

 

Deadline and Period; Partitioning; Multiprocessor

[pdf]