A sensor transaction scheduling algorithm for maintaining real-time data temporal validity
来源期刊:中南大学学报(英文版)2011年第6期
论文作者:白天 李国徽 刘云生
文章页码:2068 - 2073
Key words:temporal validity; real-time database; sensor transaction
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.
J. Cent. South Univ. Technol. (2011) 18: 2068-2073
DOI: 10.1007/s11771-011-0944-7
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 Xi at time t is temporally valid if its j-th sampling time ri,j plus its validity interval Vi is not less than t, i.e., ri,j + Vi ≥ t [3].
Consider a set of sensor transaction, Г={τi} (1≤i≤m) and a set of real-time data objects X ={Xi}(1≤i ≤m). Xi is associated with a validity interval Vi and updated by transaction τi with a computation time Ci. 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., Vi -Ci).
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 di,j+1 is obtained by Eq.(1):
di,j+1 = ri, j+Vi (1)
Then, the release time of τi,j+1 is derived backwards from di,j+1 as follows:
ri,j+1=di,j+1-Θi(ri,j+1, di,j+1)-Ci (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(ri,j+1, di,j+1), the schedule of all higher priority instances that are released before di,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 ri,j of τi,j is just derived by DS-FP. Let IHPS(τi,j) denote the set of higher priority instances that get at least one time slice in [ri,j, di,j]. If IHPS(τ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:
fk,l+1-Vk ≤ ri,j (3)
where fk,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 [ri,j, di,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, fk,l+1 may be smaller than dk,l+1. So, Eq.(1) can be rewritten as
fk,l+1≤rk,l+Vk (4)
Equation (4) must be enforced after the exchange. By replacing rk, l with ri, j and putting Vk 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 IHP(τ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 Tts in [r′i,j, di,j], then Tts 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 TEPR(τk,l) denote the earliest possible release time of τk,l in IHP(τ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 TEPR(τ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 di,j+1 should be computed. In addition, for each instance in IHP(τ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 Si(t1, t2) a part of the complete schedule Si constructed for Гi from time t1 to t2. If Si repeats Si(t1, t2) consecutively to infinity after t2 , then Si(t1, t2) is a repeating pattern of Si.
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, Si can be constructed by scheduling all instances of τi based on Si-1.
Obviously, there are repeating patterns for S1, for example, S1(V1, 2V1-C1).
Suppose that there are repeating patterns for Si-1, one of which is Si-1(t1,t2). Consider the instances of scheduling τi. There should be an instance τi,j whose release time before the time slice exchange, denoted as rbi,j, is in [t1, t2 ]. For an instance τi,k (k ≥ j), rbi,k should be in the time interval of Si-1(t1, t2) or a later repeating pattern. Let N denote the number of free time slices in the time interval of Si-1(t1, t2). There are just N values for the offset from rbi,k to the end of the corresponding repeating pattern. So there must be two instances τi,l and τi,s (j ≤li(rbi,l, di, l) is equal to Si(rbi,s, di,s) before and after the exchange. So Si(rbi,l, rbi,s) is a repeating pattern of Si. In fact, if we can find two instances τi,l and τi,s (j≤lbi,s - rbi,l) being a multiple of (t2 -t1), Si(rbi,l, rbi,s) is certainly a repeating pattern of Si. 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, Si-1(t1, t2) is a repeating pattern for Гi-1 and Ci-1(t1, t2) 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 Г1, 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
ri,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] ←(V1-C1, 2V1-2C1, V1-2C1);
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
di, j+1 ← ri, j+Vi ;
rbi, j +1=allocateTS (i, j+1, di, j+1);
if (rbi, j +1 =-1) then
report failure, abort;
elseif (rbi, 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
ri,j+1 ← DeferRT (i, j+1 , rbi, j+1), di,j+1);
j ←j+1;
repeat
In Algorithm 1, function allocateTS(i, j, di,j) tries to allocate Ci unassigned time slices to τi,j backwards from di,j. If the number of free time slices in [di,j-1, di,j] is less than Ci, Г 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 , rbi, j, di,j)
loop
et ←rbi, j,
for each (τk, lIHP(τi, j))
if (rbi, j)≥ TEPR(τk, l)) then
et ←max (et, lastTS(τk, l, di, j));
endif
if (rbi, j < et) then
exchange(et, rbi, j);
rbi, j← min (et , secondTS (τi, j));
else
return rbi, j ;
endif
repeat
Algorithm 2 defers the release time of τi,j by time exchange method. The last time slice of τk,l before di, j is obtained by Function lastTS (τk,l , di,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 τ1, τ2 and τ3. C1=1, V1=6; C2=2, V2=14; C3=2, V3=16. Figure 1 shows schedules produced by DS-FP and DS-EXC during time slice [10, 45], respectively. Since IHPS(τ3,1) contains τ2,1 and TEPR(τ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) ×fslack 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