实时数据库系统中周期性事务调度算法的研究
|
摘要
实时数据库系统的目标就是使满足截止期限约束的事务数量为最大,因而支持优先考虑时间的事务调度是非常重要的。事务的实时调度方法是决定系统性能好坏的关键,而那些传统的确定性事务调度方法对以时间优先的应用来说是不足够的,确定性事务调度方法又不支持一定概率的事务作业错过截止期限。使用More-Less方法保证事务更新的数据对象的时序一致性是当前常用的方法。但是其过于悲观地使用最坏情况下的事务作业计算时间来执行调度使得系统资源利用率增大,从而减少了满足截止期限约束条件的事务作业执行的个数,最终导致了系统性能的下降。因此,为了优化系统性能,需要提供一种新方法同时支持实时性和可调度性,并且期望在事务执行时的系统资源利用率最低。
本文首先研究了实时数据库系统中的更新事务和实时数据的时间特性,给出了确定实时数据正确性的定义;然后分析和比较了传统的确定性更新事务调度算法。并在此基础上研究了基于延迟更新事务作业抽样时间以达到优化系统资源利用率的方法,讨论了取样周期和相对截止期限在进程调度中的时序关系,紧接着在软/固实时系统中引入概率统计的非确定性方法。最后结合可延迟调度算法,并通过概率统计方法来控制调度实时更新事务作业以保证实时数据的时序一致性,提出了一种既能更好地优化CPU资源利用率,同时又能保证实时更新事务请求的服务质量的新方法,并通过实验和理论分析证明了使用该方法可获得更优的系统性能。
The decisive performance of real-time database systems is to maximize the number of scheduled transactions that completed before their deadlines, so it is essential to schedule the transactions in supporting time-critical applications. The transaction’s real-time scheduling policies are the key factor to judge the RTDBS performance. However, the traditional certainty scheduling algorithms are not enough for prior-time applications, and it also does not support the situation that so few transactions in probability can miss their deadlines. Using the More-Less method to guarantee the objects updated by the transactions to be consistency is common usage nowadays. But the increased system resource utilization is made by the pessimistic way to use the worst-case computing time to schedule the transaction jobs, and the reduction in the number of scheduled transaction jobs which can satisfy the condition of their deadline constraints, eventually the decline in system performance is led. Therefore, in order to optimize the system performance, a new approach should be provided to support the temporal consistency for the objects and the scheduled-feature for transactions, while the minimum system resource utilization is also hoped in the processes of the transactions being scheduled.
In this paper, the time features of the updating transaction and real-time data of the RTDBS are discussed firstly, the real-time data correctness definition is present. Firstly, the traditional certainty scheduling algorithms of the updating transactions are analyzed and compared each other. Based on these studies, a way by deferring the job release time of updating transactions is studied carefully for optimizing the utilization of system resource. Secondly, the temporal relationship between the release time and the relative deadline in the schedued process is discussed. Thirdly, an uncertainty method based on probability statistic is introduced into the soft and solid real-time systems. After that, a new method is improved by putting the probability statistic theory into the original deferrable scheduling algorithms under the condition that the real-time data consistency is ensured, while the optimal resource utilization and the required QOS of the updating transactions can be satisfied in this method. Finally, both the experiment theory and results show that this method can show better system performance.
本文首先研究了实时数据库系统中的更新事务和实时数据的时间特性,给出了确定实时数据正确性的定义;然后分析和比较了传统的确定性更新事务调度算法。并在此基础上研究了基于延迟更新事务作业抽样时间以达到优化系统资源利用率的方法,讨论了取样周期和相对截止期限在进程调度中的时序关系,紧接着在软/固实时系统中引入概率统计的非确定性方法。最后结合可延迟调度算法,并通过概率统计方法来控制调度实时更新事务作业以保证实时数据的时序一致性,提出了一种既能更好地优化CPU资源利用率,同时又能保证实时更新事务请求的服务质量的新方法,并通过实验和理论分析证明了使用该方法可获得更优的系统性能。
The decisive performance of real-time database systems is to maximize the number of scheduled transactions that completed before their deadlines, so it is essential to schedule the transactions in supporting time-critical applications. The transaction’s real-time scheduling policies are the key factor to judge the RTDBS performance. However, the traditional certainty scheduling algorithms are not enough for prior-time applications, and it also does not support the situation that so few transactions in probability can miss their deadlines. Using the More-Less method to guarantee the objects updated by the transactions to be consistency is common usage nowadays. But the increased system resource utilization is made by the pessimistic way to use the worst-case computing time to schedule the transaction jobs, and the reduction in the number of scheduled transaction jobs which can satisfy the condition of their deadline constraints, eventually the decline in system performance is led. Therefore, in order to optimize the system performance, a new approach should be provided to support the temporal consistency for the objects and the scheduled-feature for transactions, while the minimum system resource utilization is also hoped in the processes of the transactions being scheduled.
In this paper, the time features of the updating transaction and real-time data of the RTDBS are discussed firstly, the real-time data correctness definition is present. Firstly, the traditional certainty scheduling algorithms of the updating transactions are analyzed and compared each other. Based on these studies, a way by deferring the job release time of updating transactions is studied carefully for optimizing the utilization of system resource. Secondly, the temporal relationship between the release time and the relative deadline in the schedued process is discussed. Thirdly, an uncertainty method based on probability statistic is introduced into the soft and solid real-time systems. After that, a new method is improved by putting the probability statistic theory into the original deferrable scheduling algorithms under the condition that the real-time data consistency is ensured, while the optimal resource utilization and the required QOS of the updating transactions can be satisfied in this method. Finally, both the experiment theory and results show that this method can show better system performance.
引文
[1]KAYAN E,ULUSOYO. An evaluation of Real-Time transaction management issues in mobile databasesystems[J].In:The Computer Journal,1999,42(6):501-510.
[2]Mehdi Amiri joo,Jorgen,Han song. QoS Control of Real-Time Data Services under Uncertain Workload[J]. IEEE transactions on computers, 2006,3(55):41-43.
[3]Paul J,Fortier. Real-Time database systems[M]. 北京:电子工业出版社,1999:50-70.
[4]Ramamritham K. Distributed and Parallel Databases[J]. Real-Timedatabases,1993,33(1):19 9-226.
[5]金宏,王强,王宏安,戴国忠.基于动态抢占阈值的实时调度[J].计算机研究与发展,2004,3:7 91-798.
[6]徐俊刚,戴国忠,王宏安.生产调度理论和方法研究综述[J].计算机研究与发展,2004,3(2):2 57-267.
[7]宴立.实时数据库中的时序一致性[J].江苏理工大学学报自然科学版,2001,9(7):103-112.
[8]张传林,梁碧宇.保证实时数据对象统计意义时序一致性的 QOS[J].计算机学报, 2006.6 (12):16-18.
[9]Sang H.Song, Rasikan David,Bhavani Thuraisingham.improving timeliness in real-time secure database systems[J].department of computer science-university of Virginia Charlo ttesville,1996,19(22903):P29-33.
[10]Abeni,G C Buttazzo.Integrating multimedia application sin hard real-time systems[J].Proc of IEEE Real-Time Sysems Symposium Madrid,1998,42(5): 4-13.
[11]Xiong M, Ramamritham K.Deriving deadlines and periods for real-time update tansactions[J]. Proceedings of the 20th IEEE Real-Time System Symposium Phoenix,1999,42(6):16-23.
[12]Gerber R,Hong S,Saksens M.Guaranteeing end-to-end timing constraints by calibrating inter-mediate processes[J].Proceedings of IEEE 15th Real-Time Systems Symposium,1994,65(4):192-203.
[13]Ho.S. Kuo T, Mok.A.K.. Similarity-based load adjustment for static Real-Time transaction systems[J].Proceedings of the 18th Real-Time Systems Symposium,San Francisco, CA, USA,1997:144.
[14]Song X..Liu J.W.S,.Maintaining temporal consistency:Pessimistic vs Optimisti concurrency control[J].In: IEEE Transactions on knowledge and Data-Engineering,1995,7(5):P786-796.
[15]Xiong M, Ramamritham K.,Stankovic J,A,Towsley D,Sivasankaran R..Scheduling: transacti ons with temporal constraints: Expliting data semantics[J].IEEE transactions on Knowledge and Data Engineering,2002,14(5):1155-1166.
[16]Ming Xiong, Song Han,Kam-Yiu Lam.A deferrable scheduling algorithm for real-time trans actions maintaining data freshness Real-Time Systems Symposium[J]. RTSS IEEE International Volume Issue,2005,12(6) :27-37.
[17]Kam-Yiu Lam, Ming Xiong, BiYu Liang,Yang Guo.Statistical quality of service guarantee f or temporal consistency of real-time data objects Real-Time Systems Symposium[J].Digital Object Identifier IEEE International Volume,2004,12(25):276–285.
[18]Xiong Ming,Lam Kam-Yiu, Liang Bi-Yu.Quality of service guarantee for temporal consisten cy of real-time objects[J].Proceedings of the 24th IEEE Real-time Symposium C ancun Mexico,2003,4(1):69-75.
[19]党德鹏,刘云生.一种维护实时数据库一致性的新方法[J].小型微型计算机系统,2002,2(23 ):189-191.
[20]李国徽,刘云生.实时数据库事务的正确性及实现算法.计算机研究与发展[J],2001,38(9): 1087-1091.
[21]刘云生,丁力.主动实时数据库的事务处理[J].微计算机应用,2007,2(15):103-105.
[22]胡侃,刘云生.传感器网络中协作实时数据库事务的提交控制[J].计算机学报,2007,6(38): 916-923.
[23]刘云生,郭芬,廖国琼.安全的乐观实时并发控制策略[J].微计算机应用,2006,4(24):503- 506.
[24]刘云生,吕志华.嵌入式实时垃圾回收机制的分析与实现[J].计算机工程与科学, 2006, 8(41):73-79.
[25]刘云生,李国徽,卢炎生.实时数据库的事务处理[J].计算机世界,1999,7(2):10-13.
[26]张晓芳,刘云生.一种支持时态数据的实时数据模型.计算机科学,2006,33(2):118-120.
[27]王强,徐俊刚,王宏安,戴国忠.一种新的基于优先级表的实时调度算法[J].电子学报,2004,2(12):376-382.
[28]王永炎,王强,王宏安,金宏,戴国忠.基于优先级表的实时调度算法及其实现[J].软件学报, 2004,15(3):360-369.
[29]王强.混合实时事务调度与并发控制研究[M].武汉:中国科学院软件研究,2003:70-82.
[30]C L Liu ,J Layland.Scheduling algorithms for multi-programming in a hard real-time environment[J]. Journal of the ACM,1973,3(20): 46-61.
[31]索涛.并行实时数据库事务处理研究[M].武汉:华中科技大,2003:23-29.
[32]陈明俊,钟昊.关于实时事务调度中的优先级反转[J].计算机工程与应用,2003,2(29):122- 124.
[33]淮晓永,邹勇,李明树.一种开放混合实时系统的开放自适应调度算法[J].软件学报,2004,15(4):487-496.
[34]李庆华,韩建军等.硬实时系统中基于软件容错的动态调度算法[J].软件学报,2005,1(46) :101-107.
[35]Ming Xiong, Song Han, K.Y.Lam, Deji Chen.Deferrable Scheduling for Maintaining Real-Time Data Freshness Algorithm Analysis and Results[J]. The University of Texas at Austin Department of Computer Sciences Report regular tech report,2007,9(81):33-46.
[36]吴炜炜,张有仁.基于概率的实时任务调度分析[J].计算机工程,2006,32(56258):279-290.
[37]许青林,李胜利,韩宗芬,庞丽萍,实时对象模型及其可调度性分析[J].华中理工大学学报,1998,3(26):117-121.
[38]Lehoczky JP,Sha L Et. a Fixed Priority Scheduling Theory for Hard Real-Time System s. Computing Scheduling and Resource Managenment,1991,2(78):4-10.
[39]冯艳红,王晶,王占峰.应用于实时系统的 DMS 算法可调度性分析[J].计算机与现代化,2008,1(12):1006-2475.
[40] 沈卓炜 . 不可抢占式 EDF 调度算法的可调度性分析 [J]. 计算机工程与应用 , 2006,9(23):14-16.
[41]Bhaskar Purimetla, Rajendran M. Sivasankaran Krithi Ramamritham Real-Time Databases[J].Issues and Applications ,1995,2(42):104-115.
[42]罗琼,张立臣.实时数据库中时态性与安全性的服务质量管理方法[J].微电子学与计算机, 2005,5(2):33-37.
[43]韩建军,李庆华.实时数据库中具有时态限制的事务调度算法[J].小型微型计算机系统,2005,7(2):118-125.
[2]Mehdi Amiri joo,Jorgen,Han song. QoS Control of Real-Time Data Services under Uncertain Workload[J]. IEEE transactions on computers, 2006,3(55):41-43.
[3]Paul J,Fortier. Real-Time database systems[M]. 北京:电子工业出版社,1999:50-70.
[4]Ramamritham K. Distributed and Parallel Databases[J]. Real-Timedatabases,1993,33(1):19 9-226.
[5]金宏,王强,王宏安,戴国忠.基于动态抢占阈值的实时调度[J].计算机研究与发展,2004,3:7 91-798.
[6]徐俊刚,戴国忠,王宏安.生产调度理论和方法研究综述[J].计算机研究与发展,2004,3(2):2 57-267.
[7]宴立.实时数据库中的时序一致性[J].江苏理工大学学报自然科学版,2001,9(7):103-112.
[8]张传林,梁碧宇.保证实时数据对象统计意义时序一致性的 QOS[J].计算机学报, 2006.6 (12):16-18.
[9]Sang H.Song, Rasikan David,Bhavani Thuraisingham.improving timeliness in real-time secure database systems[J].department of computer science-university of Virginia Charlo ttesville,1996,19(22903):P29-33.
[10]Abeni,G C Buttazzo.Integrating multimedia application sin hard real-time systems[J].Proc of IEEE Real-Time Sysems Symposium Madrid,1998,42(5): 4-13.
[11]Xiong M, Ramamritham K.Deriving deadlines and periods for real-time update tansactions[J]. Proceedings of the 20th IEEE Real-Time System Symposium Phoenix,1999,42(6):16-23.
[12]Gerber R,Hong S,Saksens M.Guaranteeing end-to-end timing constraints by calibrating inter-mediate processes[J].Proceedings of IEEE 15th Real-Time Systems Symposium,1994,65(4):192-203.
[13]Ho.S. Kuo T, Mok.A.K.. Similarity-based load adjustment for static Real-Time transaction systems[J].Proceedings of the 18th Real-Time Systems Symposium,San Francisco, CA, USA,1997:144.
[14]Song X..Liu J.W.S,.Maintaining temporal consistency:Pessimistic vs Optimisti concurrency control[J].In: IEEE Transactions on knowledge and Data-Engineering,1995,7(5):P786-796.
[15]Xiong M, Ramamritham K.,Stankovic J,A,Towsley D,Sivasankaran R..Scheduling: transacti ons with temporal constraints: Expliting data semantics[J].IEEE transactions on Knowledge and Data Engineering,2002,14(5):1155-1166.
[16]Ming Xiong, Song Han,Kam-Yiu Lam.A deferrable scheduling algorithm for real-time trans actions maintaining data freshness Real-Time Systems Symposium[J]. RTSS IEEE International Volume Issue,2005,12(6) :27-37.
[17]Kam-Yiu Lam, Ming Xiong, BiYu Liang,Yang Guo.Statistical quality of service guarantee f or temporal consistency of real-time data objects Real-Time Systems Symposium[J].Digital Object Identifier IEEE International Volume,2004,12(25):276–285.
[18]Xiong Ming,Lam Kam-Yiu, Liang Bi-Yu.Quality of service guarantee for temporal consisten cy of real-time objects[J].Proceedings of the 24th IEEE Real-time Symposium C ancun Mexico,2003,4(1):69-75.
[19]党德鹏,刘云生.一种维护实时数据库一致性的新方法[J].小型微型计算机系统,2002,2(23 ):189-191.
[20]李国徽,刘云生.实时数据库事务的正确性及实现算法.计算机研究与发展[J],2001,38(9): 1087-1091.
[21]刘云生,丁力.主动实时数据库的事务处理[J].微计算机应用,2007,2(15):103-105.
[22]胡侃,刘云生.传感器网络中协作实时数据库事务的提交控制[J].计算机学报,2007,6(38): 916-923.
[23]刘云生,郭芬,廖国琼.安全的乐观实时并发控制策略[J].微计算机应用,2006,4(24):503- 506.
[24]刘云生,吕志华.嵌入式实时垃圾回收机制的分析与实现[J].计算机工程与科学, 2006, 8(41):73-79.
[25]刘云生,李国徽,卢炎生.实时数据库的事务处理[J].计算机世界,1999,7(2):10-13.
[26]张晓芳,刘云生.一种支持时态数据的实时数据模型.计算机科学,2006,33(2):118-120.
[27]王强,徐俊刚,王宏安,戴国忠.一种新的基于优先级表的实时调度算法[J].电子学报,2004,2(12):376-382.
[28]王永炎,王强,王宏安,金宏,戴国忠.基于优先级表的实时调度算法及其实现[J].软件学报, 2004,15(3):360-369.
[29]王强.混合实时事务调度与并发控制研究[M].武汉:中国科学院软件研究,2003:70-82.
[30]C L Liu ,J Layland.Scheduling algorithms for multi-programming in a hard real-time environment[J]. Journal of the ACM,1973,3(20): 46-61.
[31]索涛.并行实时数据库事务处理研究[M].武汉:华中科技大,2003:23-29.
[32]陈明俊,钟昊.关于实时事务调度中的优先级反转[J].计算机工程与应用,2003,2(29):122- 124.
[33]淮晓永,邹勇,李明树.一种开放混合实时系统的开放自适应调度算法[J].软件学报,2004,15(4):487-496.
[34]李庆华,韩建军等.硬实时系统中基于软件容错的动态调度算法[J].软件学报,2005,1(46) :101-107.
[35]Ming Xiong, Song Han, K.Y.Lam, Deji Chen.Deferrable Scheduling for Maintaining Real-Time Data Freshness Algorithm Analysis and Results[J]. The University of Texas at Austin Department of Computer Sciences Report regular tech report,2007,9(81):33-46.
[36]吴炜炜,张有仁.基于概率的实时任务调度分析[J].计算机工程,2006,32(56258):279-290.
[37]许青林,李胜利,韩宗芬,庞丽萍,实时对象模型及其可调度性分析[J].华中理工大学学报,1998,3(26):117-121.
[38]Lehoczky JP,Sha L Et. a Fixed Priority Scheduling Theory for Hard Real-Time System s. Computing Scheduling and Resource Managenment,1991,2(78):4-10.
[39]冯艳红,王晶,王占峰.应用于实时系统的 DMS 算法可调度性分析[J].计算机与现代化,2008,1(12):1006-2475.
[40] 沈卓炜 . 不可抢占式 EDF 调度算法的可调度性分析 [J]. 计算机工程与应用 , 2006,9(23):14-16.
[41]Bhaskar Purimetla, Rajendran M. Sivasankaran Krithi Ramamritham Real-Time Databases[J].Issues and Applications ,1995,2(42):104-115.
[42]罗琼,张立臣.实时数据库中时态性与安全性的服务质量管理方法[J].微电子学与计算机, 2005,5(2):33-37.
[43]韩建军,李庆华.实时数据库中具有时态限制的事务调度算法[J].小型微型计算机系统,2005,7(2):118-125.