J. Cent. South Univ. Technol. (2011) 18: 2068-2073

DOI: 10.1007/s11771-011-0944-7

A sensor transaction scheduling algorithm for

maintaining real-time data temporal validity

BAI Tian(白天), LI Guo-hui(李国徽), LIU Yun-sheng(刘云生)

College of Computer Science and Technology, Huazhong University of Science and Technology,Wuhan 430074, China

? Central South University Press and Springer-Verlag Berlin Heidelberg 2011

Abstract: A new scheduling algorithm called deferrable scheduling with time slice exchange (DS-EXC) was proposed to maintain the temporal validity of real-time data. In DS-EXC, the time slice exchange method was designed to further defer the release time of transaction instances derived by the deferrable scheduling algorithm (DS-FP). In this way, more CPU time would be left for lower priority transactions and other transactions. In order to minimize the scheduling overhead, an off-line scheme was designed. In particular, the schedule for a transaction set is generated off-line until a repeating pattern is found, and then the pattern is used to construct the schedule on-line. The performance of DS-EXC was evaluated by sets of experiments. The results show that DS-EXC outperforms DS-FP in terms of increasing schedulable ratio. It also provides better performance under mixed workloads.

Key words: temporal validity; real-time database; sensor transaction

1 Introduction

Many application domains, such as air traffic management and process control, require processing real-time data [1-2]. These data are usually managed by a real-time database system (RTDBs). They model the current status of entities in the external environment and their values will become invalid with the passage of time. Associated with each data, the object value is a temporal validity interval [3-4] during which it is valid, i.e., it is considered to truly reflect the current status of the corresponding entity. The temporal validity constraint of real-time data requires that their values should be valid at any time so that the managing systems can detect and respond to the environmental changes immediately.

In recent years, there are a large amount of literatures in this area [2, 5, 6-14]. Most of them assumed that the validity constraints were already preserved and focused on other aspects. For example, the concept of data-deadline and a scheduling algorithm based on it were proposed to satisfy deadlines of transactions [7]. The author assumed that the freshness of real-time data was maintained by periodic transactions. The on-demand scheduling algorithm was proposed to enforce derived data freshness [10]. The freshness of base data was just assumed to be preserved by updates with fixed frequencies.

Studies on scheduling sensor transactions to maintain the temporal validity constraint are much less [2, 5, 13-14]. The Half-Half (HH) scheme [2] and the More-Less (ML) scheme [13] adopt the periodic transaction model. In HH, the update period and relative deadline of a transaction are both set to be half of its validity interval. In ML, the worst-case response time of a transaction is computed. If it is less than half of the validity interval, ML sets it as the relative deadline of the transaction. The period is set to be the difference of the validity interval and the relative deadline. The DS-FP algorithm [5, 14] defers the release time of transaction instances as late as possible without violating the temporal validity. It is shown that DS-FP can schedule more transaction sets and generate lower update workloads than ML and HH.

This work presents the deferrable scheduling algorithm with time slice exchange (DS-EXC). In DS-EXC, the release time of each transaction instance is first derived by the method in DS-FP, and then further deferred by a new method, the time slice exchange method. As a result, more CPU time can be left to lower priority transactions and other types of transactions. In order to minimize the scheduling overhead, DS-EXC generates the schedule for a transaction set off-line until a repeating pattern is found, and then uses this pattern to construct the schedule on-line.

2 Background

Definition 1: A real-time data object X_i at time t is temporally valid if its j-th sampling time r_i,j plus its validity interval V_i is not less than t, i.e., r_i,j + V_i ≥ t [3].

Consider a set of sensor transaction, Г={τ_i} (1≤i≤m) and a set of real-time data objects X ={X_i}(1≤i ≤m). X_i is associated with a validity interval V_i and updated by transaction τ_i with a computation time C_i. It is assumed that validity intervals and computation times are integers. Jitter between sampling time and release time of a transaction instance is zero. Transactions are preemptive and all preemption costs are ignored. τ_i has a higher priority than τ_j if i < j.

Both ML and DS-FP are fixed-priority scheduling algorithms (HH can be considered as a special case of ML). They assign priorities to transactions based on shortest validity first (SVF) scheme, i.e., in the inverse order of validity length, ties are resolved in favor of transactions with less slacks (i.e., V_i -C_i).

DS-FP algorithm is briefly reviewed here. The idea of DS-FP is to defer the release time of subsequent instance of a transaction instance as late as possible while still guaranteeing the validity constraint. To achieve this purpose, for an instance τ_i,j+1, its absolute deadline d_i,j+1 is obtained by Eq.(1):

d_i,j+1 = r_{i, j}+V_i                                                                                          (1)

Then, the release time of τ_i,j+1 is derived backwards from d_i,j+1 as follows:

r_i,j+1=d_i,j+1-Θ_i(r_i,j+1, d_i,j+1)-C_i                                         (2)

where Θ_i(a,b) denotes the cumulative processor demand required by higher priority instances during time interval [a, b). Note that before the computation of Θ_i(r_i,j+1, d_i,j+1), the schedule of all higher priority instances that are released before d_i,j+1 needs to be computed.

3 Deferrable scheduling with time slice exchange

3.1 Time slice exchange

It is considered that the release time r_i,j  of τ_i,j is just derived by DS-FP. Let I_HPS(τ_i,j) denote the set of higher priority instances that get at least one time slice in [r_i,j, d_i,j]. If I_HPS(τ_i,j) contains an instance τ_k,l whose release time of next instance τ_k,l+1 has been derived by DS-FP at this time and τ_k,l+1 satisfies the following condition:

f_k,l+1-V_k ≤ r_i,j                                                                   (3)

where f_k,l+1  is the actual finish time of τ_k,l+1. Then, the release time of τ_i,j  can be deferred by exchanging a time slice of τ_{k, l} in [r_i,j, d_i,j] with the first time slice of τ_i,j, that is, the time slice allocated to τ_{k, l} is now allocated to τ_{i, j}  and the time slice to τ_{i, j}  is now allocated to τ_{k, l}.

This exchange is justified as follows. At first, the release time of τ_{k, l+1} is derived before the exchange, so its subsequent instances (include itself) are not affected by the exchange. Secondly, the validity constraint is preserved by Eq.(3). It is obvious that Eq.(1) guarantees the constraint before the exchange for τ_k,l and τ_k,l+1. Due to the preemption of higher priority instances, f_k,l+1 may be smaller than d_k,l+1. So, Eq.(1) can be rewritten as

f_k,l+1≤r_k,l+V_k                                                                    (4)

Equation (4) must be enforced after the exchange. By replacing r_{k, l} with r_{i, j} and putting V_k to the left side, Eq.(3) is obtained. As a result, the exchange defers the release time of τ_i,j and has no impact on the schedule of  τ_k. The separation between τ_i,j-1 and τ_i,j becomes larger, the release time of subsequent instances of τ_i,j may also be deferred when being derived later, and then the workload of τ_i is reduced. The reduction of workload of τ_i leaves more CPU time to lower priority transactions and gives them more chances to satisfy their validity constraints. The update workload would be lower (on the average) than that of DS-FP.

After the first exchange, τ_i,j may continue to do exchanges with instances in I_HP(τ_i,j) to further defer its release time (without any impact on these instances and their subsequent instances). If the release time of an instance is earlier than current release time r′_i,j of τ_i,j, and it also has a time slice T_ts in [r′_i,j, d_i,j], then T_ts can be exchanged with first time slice of τ_i,j no matter whether the schedule information of its next instance has been computed or not.

In general, let T_EPR(τ_k,l) denote the earliest possible release time of τ_k,l in I_HP(τ_i,j) which is defined as follows:

          (5)

Suppose that the release time of τ_i,j after m exchanges (m≥0) is  then  can be further deferred if T_EPR(τ_k,l)≤ts≤d_i,j, where T_ts is a time slice assigned to τ_k,l.

3.2 DS-EXC algorithm

The idea of DS-EXC is using time slice exchange method to defer the release time of instances derived by DS-FP. In particular, two rules are used to schedule instances:

1) The release time of a transaction instance τ_i,j is first derived by Eq.(1) and Eq.(2) as in DS-FP, then deferred by time slice exchange method.

2) Before deriving the release time of τ_i,j, the schedule information of all higher priority instances that are released before d_i,j+1 should be computed. In addition, for each instance in I_HP(τ_i,j), the schedule information of its next instance should also be computed. This gives τ_i,j more chances to execute the first exchange.

HAN et al [14] proved if Г can be scheduled by DS-FP, then there are repeating patterns in the constructed schedule. By using a modified method, the existence of repeating patterns in a successful DS-EXC schedule is proved in this work, then an off-line schedule method is given.

Let Г_i denote the first i (1≤i≤m) transactions of Г (Г is ordered in ascent order of validity interval lengths) and S_i(t₁, t₂) a part of the complete schedule S_i constructed for Г_i from time t₁ to t₂. If S_i repeats S_i(t₁, t₂) consecutively to infinity after t₂ , then S_i(t₁, t₂) is a repeating pattern of S_i.

Theorem 1: If DS-EXC can schedule Г successfully, then there are repeating patterns in the constructed schedule.

Proof: According to the schedule rules of DS-EXC, the schedule for Г can be constructed gradually from the lowest priority transaction to the highest priority transaction. In particular, S_i can be constructed by scheduling all instances of τ_i based on S_i-1.

Obviously, there are repeating patterns for S₁, for example, S₁(V₁, 2V₁-C₁).

Suppose that there are repeating patterns for S_i-1, one of which is S_i-1(t₁,t₂). Consider the instances of scheduling τ_i. There should be an instance τ_i,j whose release time before the time slice exchange, denoted as r^b_i,j, is in [t₁, t₂ ]. For an instance τ_i,k (k ≥ j), r^b_i,k should be in the time interval of S_i-1(t₁, t₂) or a later repeating pattern. Let N denote the number of free time slices in the time interval of S_i-1(t₁, t₂). There are just N values for the offset from r^b_i,k to the end of the corresponding repeating pattern. So there must be two instances τ_i,l and τ_i,s (j ≤li(r^b_i,l, d_{i, l}) is equal to S_i(r^b_i,s, d_i,s) before and after the exchange. So S_i(r^b_i,l, r^b_i,s) is a repeating pattern of S_i. In fact, if we can find two instances τ_i,l and τ_i,s (j≤lb_i,s - r^b_i,l) being a multiple of (t₂ -t₁), S_i(r^b_i,l, r^b_i,s) is certainly a repeating pattern of S_i. Therefore, the theorem is proven.

The following corollary can be obtained from Theorem 1.

Corollary 1: Suppose that Г_i-1 can be scheduled by DS-EXC, S_i-1(t₁, t₂) is a repeating pattern for Г_i-1 and C_i-1(t₁, t₂) is the number of allocated time slices in the pattern, if Г_i can also be scheduled by DS-EXC, then

                                                 (6)

The proof of Theorem 1 suggests an off-line schedule method, that is, starting from Г₁, we try to find a repeating pattern of Г_i based on the repeating pattern of Г_i-1. This process continues until a repeating pattern of Г is found or an instance is found unschedulable. This pattern and the segment of S before the first pattern are then used to schedule Г on-line (see Algorithm 1).

Algorithm 1: DS-EXC

r_i,0 ← 0 (1 ≤ i ≤ m );

P[i] ←(0, 0, 0) (2 ≤ i ≤ m); // P[i] records

//the start time, the end time and the number

//of free time slices of pattern of Г_i.

P[1] ←(V₁-C₁, 2V₁-2C₁, V₁-2C₁);

for i =2 to m do

if Eq.(6) is not hold for P[i-1] and τ_i, report failure, abort;

j ← 0;

firstStart = 0; // firstStart records the first

//possible instance that starts the pattern.

loop

d_{i, j+1} ← r_{i, j}+V_i ;

r^b_{i, j +1}=allocateTS (i, j+1, d_{i, j+1});

if (r^b_{i, j +1} =-1) then

report failure, abort;

elseif (r^b_{i, j +1}>P[i-1]. start and

findStart=0)

firstStart = j+1;

elseif ( j+1= P[i-1]. free+ firstStart)

P[i] ← findPattern (firstStart, j+1);

break;

endif

r_i,j+1 ← DeferRT (i, j+1 , r^b_{i, j+1}), d_i,j+1);

j ←j+1;

repeat

In Algorithm 1, function allocateTS(i, j, d_i,j) tries to allocate C_i unassigned time slices to τ_i,j backwards from d_i,j. If the number of free time slices in [d_i,j-1, d_i,j] is less than C_i, Г can be scheduled by DS-EXC. Function findPattern (l,k) finds the repeating pattern of Г_i using the method in the Proof of Theorem 1.

Algorithm 2: DeferRT (i , j , r^b_{i, j}, d_i,j)

loop

et ←r^b_{i, j},

for each (τ_{k, l}I_HP(τ_{i, j}))

if (r^b_{i, j})≥ T_EPR(τ_{k, l})) then

et ←max (et, lastTS(τ_{k, l}, d_{i, j}));

endif

if (r^b_{i, j} < et) then

exchange(et, r^b_{i, j});

r^b_{i, j}← min (et , secondTS (τ_{i, j}));

else

return r^b_{i, j} ;

endif

repeat

Algorithm 2 defers the release time of τ_i,j by time exchange method. The last time slice of τ_k,l before d_{i, j} is obtained by Function lastTS (τ_k,l , d_i,j). Function secondTS (τ_i,j) gets the second earliest assigned time slice of τ_i,j. Algorithm 2 stops when no exchange can be done.

Suppose that there are three sensor transactions τ₁, τ₂ and τ₃. C₁=1, V₁=6; C₂=2, V₂=14; C₃=2, V₃=16. Figure 1 shows schedules produced by DS-FP and DS-EXC during time slice [10, 45], respectively. Since I_HPS(τ_3,1) contains τ_2,1 and T_EPR(τ_2,1) is 11, time slice 13 allocated for τ_2,1 can be exchanged with time slice 11 for τ_3,1 to defer the release time of τ_3,1. The release time of τ_3,2 and τ_3,3 are also deferred, although their time slices cannot be exchanged with other higher priority instances.

Fig.1 Comparison of schedules between DS-FP and DS-EXC

In fact, if a transaction set can be scheduled by ML, then it can surely be scheduled by DS-EXC. This can be proved by a modified method described in Ref.[3]. The key is to show that, if we reassign each instances the “original” time slices (those allocated to an instance before the exchange), the separation between two consecutive instances of a transaction scheduled by DS-EXC, is larger than the period of this transaction computed by ML. It is easy to see that the update workload is lower than that of ML.

4 Performance evaluation

4.1 Simulation model and parameters

Two sets of experiments have been executed to compare the performance of DS-EXC against DS-FP. The first set compared the schedulable ratios of two algorithms. For a set of m transaction sets, its schedulable ratio (SR) is defined as (n/m), where n is the number of schedulable transaction set. The schedulable ratio is measured with respect to the utilization of    the transaction set. For a transaction set Г sized m, its

utilization is defined as  where  is the

individual utilization of τ_i (1≤ i ≤ m) in Г. The second set studied the performances of DS-EXC and DS-FP under mixed transaction workloads, that is, a set of sensor transactions plus a set of triggered transactions. The performance metrics in this set are the missed deadline ratio (MDR) and the average response time (ART) of triggered transactions.

Consider a single CPU main memory RTDBs. Each data object has just one version. Triggered transactions will access a set of real-time data objects to make decisions. Sensor transactions are scheduled by DS-EXC or DS-FP. Triggered transactions are scheduled by the earliest deadline first (EDF) scheme if the missed deadline ratio is measured, otherwise the “first come, first service (FCFS)” scheme is adopted. Sensor transactions are assigned higher priorities than triggered transactions. A triggered transaction should read temporal valid real-time data objects, but the values of these objects need not be valid when the transaction commits. This requirement is more practical since the value of an object may be changed several times during the execution of a triggered transaction. Table 1 gives parameters and their settings. For a triggered transaction T, let a(T) denote its arrive time and e(T) its estimated execution time, and its absolute deadline d(T) is set as follows:

d(T)= a(T) + e(T) ×f_{slack factor}

Table 1 Parameters and settings

4.2 Comparison of schedulable ratio

Given the utilization of a transaction set, the individual utilization of each transaction in the set is obtained by the UUniFast algorithm [15]. The validity interval length of a transaction is chosen from [500,    2 000] uniformly, then its computation time is derived based on its utilization and validity interval.

Figure 2 shows the schedulable ratios of DS-EXC and DS-FP when the size of a transaction set is fixed at 100. Here, the utilization ratio of a single transaction set is increased from 60% to 90% with the step length being 2.5%, and 300 transaction sets are generated in each step. It is observed that the schedulable ratio of DS-EXC is higher than DS-FP when the utilization ratio is larger than about 67.5% and less than about 87.5%. This is because DS-EXC leaves more CPU time to lower priority transactions by using the time slice exchange method, thus an instance scheduled by DS-EXC has more chances to find sufficient free time slices. It is also observed that both DS-EXC and DS-FP can schedule nearly all transaction sets when the utilization ratio is less than about 60%. In this case, however, DS-EXC is still better than DS-FP due to its low run-time cost. When the utilization ratio exceeds 90%, both algorithms are unable to schedule any transaction set. Experiments for transaction sets sized 50 and 150 show similar results.

Fig.2 Comparison of SR between DS-EXC and DS-FP at different utilization ratios

Figure 3 shows the result when the utilization is fixed at 75%. Here, the size of a transaction set is increased from 50 to 200, and in each step 300 transaction sets are generated. It can be seen that the schedulable ratio of DS-EXC (around 80%) is higher than DS-FP (around 64%) despite the increase of the transaction set size.

Fig.3 Comparison of SR between DS-EXC and DS-FP at different transaction set sizes

4.3 Comparison under mixed workloads

Figure 4 shows that the missed deadline ratio (MDR) of triggered transactions under DS-EXC is lower than that under DS-FP. Here, the utilization of a sensor transaction set is fixed at 67.5%, the arrival rate of triggered transactions is increased from 4 to 24 transactions per second. This is because DS-EXC leaves more free time slices to triggered transactions, thus a triggered transaction has more chances to finish before its deadline.

Fig.4 Comparison of MDR between DS-EXC and DS-FP at different transaction arrival rate

We have also inplemented experiments by fixing the arrival rate of triggered transactions at 8 transactions per second and increasing the utilization of a sensor transaction set from 60% to 80%. Higher utilization ratios are not considered since most CPU time will be occupied by sensor transactions under these conditions. The comparison is shown in Fig.5. It is observed that the missed deadline ratio of triggered transactions under DS-EXC is lower than that under DS-FP. The missed deadline ratio under both algorithms increases as the utilization of the sensor transaction set increases.

Fig.5 Comparison of MDR between DS-EXC and DS-FP at different utilization ratio

In Fig.6, the average response time (ART) of triggered transactions under DS-EXC is smaller than that under DS-FP. Here, the triggered transactions have no deadline. The utilization ratio of a transaction set is fixed at 65% and the arrival rate of triggered transactions is increased from 3 to 15. The main reason is that DS-EXC can provide more free time slices to triggered transactions.

Fig.6 Comparison of ART between DS-EXC and DS-FP at different transaction arrival rate

5 Conclusions

1) A new scheduling algorithm called deferrable scheduling with time slice exchange (DS-EXC) is proposed. DS-EXC uses the time slice exchange method to further defer the release time of transaction instances derived by DS-FP, thus can leave more CPU time to lower priority transactions and other transactions. In order to minimize the scheduling overhead, DS-EXC generates the schedule of a transaction set off-line until a repeating pattern is found, and then uses this pattern to schedule the transactions on-line.

2) Experiments show that DS-EXC performs better than DS-FP in schedulable ratio. In addition, it can improve the performance of triggered transactions (the missed deadline ratio and the average response time in the experiments) under mixed workloads.

References

[1] GOUD G, SHARMA N, RAMAMRITHAM K, MALEWAR S. Efficient real-time support for automotive applications: A case study [C]// Proceedings of the 12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications. Washington, DC: IEEE Computer Society, 2006: 335-341.

[2] HO Shao-juen, KUO Tei-wei, MOK A K. Similarity-based load adjustment for real-time data-intensive applications [C]// Proceedings of the 18th IEEE Real-Time Systems Symposium. Washington, DC: IEEE Computer Society, 1997: 144-153.

[3] RAMAMRITHAM K. Real-time databases [J]. Distributed and Parallel Databases, 1993, 1(2): 199-226.

[4] STANKOVIC J A,SON S, HANSSON J. Misconception about real-time databases [J]. Computer, 1999, 32(6): 29-36.

[5] XIONG Ming, HAN Song, LAM Kam-yiu, CHEN De-ji. Deferrable scheduling for maintaining real-time data freshness: Algorithms, analysis, and results [J]. IEEE Transactions on Computers, 2008, 57(7): 952-964.

[6] AMIRIJOO M, HANSSON J, SON S H. Speci?cation and management of QoS in real-time databases supporting imprecise computations [J]. IEEE Transactions on Computers, 2006, 55(3): 304-319.

[7] XIONG Ming, SIVASANKARAN R, STANKOVIC J A, RAMAMRITHAM K, TOWSLEY D. Scheduling transactions with temporal constraints: exploiting data semantics [J]. IEEE Transactions on Knowledge and Data Engineering, 2002, 14(5): 1155-1166.

[8] KANG K D, SON S H, STANKOVIC J A. Managing deadline miss ratio and sensor data freshness in real-time databases [J]. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(10): 1200-1216.

[9] SONG Xiao-hui, LIU J W S. Maintaining temporal consistency: Pessimistic versus optimistic concurrency control [J]. IEEE Transactions on Knowledge and Data Engineering , 1995, 7(5): 786-796.

[10] GUSTAFSSON T, HANSSON J. Dynamic on-demand updating of data in real-time database systems [C]// Proceedings of the 2004 ACM Symposium on Applied Computing. New York: ACM, 2004: 846-853.

[11] LUNDBERG L. Utilization based schedulability bounds for age constraint process sets in real-time system [J]. Real-Time Systems, 2002, 23(3): 273-295.

[12] XIONG Ming, LIANG Bi-yu, LAM Kam-Yiu, GUO Yang. Quality of service guarantee for temporal consistency of real-time transactions [J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(8): 1097-1110.

[13] XIONG Ming, RAMAMRITHAM K. Deriving deadlines and periods for real-time update transactions [J]. IEEE Transactions on Computers, 2004, 53(5): 567-583.

[14] HAN Song, CHEN De-ji, XIONG Ming, MOK A K. A schedulability analysis of deferrable scheduling using patterns [C]// Proceedings of the 2008 Euromicro Conference on Real-Time Systems. Washington D C: IEEE Computer Society, 2008: 45-57.

[15] BINI E, BUTTAZZO G. Measuring the performance of schedulability tests [J]. Real-Time Systems, 2005, 30(1/2): 129-154.

(Edited by DENG Lü-xiang)

Foundation item: Project(60873030) supported by the National Natural Science Foundation of China

Received date: 2011-05-19; Accepted date: 2011-09-13

Corresponding author: BAI Tian, PhD Candidate; Tel: +86-13762082666; E-mail: baitiannobel@yahoo.com.cn