微信服务号

微信订阅号

2025-4-9- 11
Home > Archive>Volume 26, Issue 12, 2015 >3223-3241. DOI:10.13328/j.cnki.jos.004853
PDF HTML XML Export Cite reminder
Rate-Monotonic Optimal Design Based on Tree-Like Linear Programming Search
Author:
Affiliation:

Fund Project:

National Natural Science Foundation of China (61170072); the National Science Foundation for Young Scientists of China under Grant (61303057); the CAS/SAFEA International Partnership Program for Creative Research Teams

  • Article
    • | |
  • Metrics
    • |
  • Reference [54]
    • |
  • Related [20]
    • | | |
  • Comments
    Abstract:

    Over the last four decades, a critical problem in real-time system is to improve the efficiency of the decision algorithm for the rate-monotonic(RM) scheduling. Nowadays researchers extend the decision problem to a generalized optimal design problem, that is, how to adjust the task execution time in the corresponding interval such that(1) the system is schedulable and(2) certain system performance(e.g. CPU utilization) is optimized. All the existing methods for solving this problem are to formulate the problem as the generalized constrained optimization problem(GCOP). However, these methods run very slowly and cannot be applied to the systems with large numbers of tasks. In this paper, a new method for solving the optimization problem is proposed. The method is called tree-like linear programming search(LPS). First, the problem is transformed into a GCOP. Next, the GCOP is partitioned into several linear programming sub-problems. Then, a linear programming search tree is constructed and the node of linear programming is solved by depth-first-search as the optimal solution. The experimental results illustrate that the new method can save 20%~70% of runtime comparing with other existing methods. This work also relates to the research areas of satisfiability modulo theories(SMT), and is expected to improve the efficiency for solving SMT problems.

    Reference
    [1] Mall R. Real-Time Systems:Theory and Practice. New Delhi:Pearson Education India, 2007.
    [2] Burchard A, Liebeherr J, Oh Y, Son SH. New strategies for assigning real-time tasks to multiprocessor systems. IEEE Trans. on Computers, 1995,44(12):1429-1442.[doi:10.1109/12.477248]
    [3] Wang YJ, Chen QP. On schedulability test of rate monotonic and its extendible algorithms. Ruan Jian Xue Bao/Journal of Software, 2004,15(6):799-814(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/15/799.htm
    [4] Liu CL, Layland JW. Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM, 1973, 20(1):46-61.[doi:10.1145/321738.321743]
    [5] Davis RI, Zabos A, Burns A. Efficient exact schedulability tests for fixed priority real-time systems. IEEE Trans. on Computers, 2008,57(9):1261-1276.[doi:10.1109/TC.2008.66]
    [6] Stankovic J, Spuri M, Ramamritham K, Buttazzo G. Deadline Scheduling for Real-Time Systems:EDF and Related Algorithms. Dordrecht:Kluwer Academic, 1998.
    [7] Bini E, Buttazzo G. A hyperbolic bound for the rate monotonic algorithm. In:Proc. of the 13th Euromicro Conf. on Real-Time Systems. Delft:IEEE Computer Society Press, 2001. 59-66.[doi:10.1109/EMRTS.2001.934000]
    [8] Kuo TW, Mok AK. Load adjustment inadaptivereal-time systems. In:Proc. of the 12th Real-Time Systems Symp. IEEE Computer Society Press, 1991. 160-170.[doi:10.1109/REAL.1991.160369]
    [9] Kuo TW, Liu YH, Lin KJ. Efficient on-line schedulability tests for priority driven real-time systems. In:Proc. of the 6th Real-Time Technology and Applications Symp. IEEE Computer Society Press, 2000. 4-13.[doi:10.1109/RTTAS.2000.852446]
    [10] Han CC, Lin KJ, Hou CJ. Distance-Constrained scheduling and its applications to real-time systems. IEEE Trans. on Computers, 1996,45(7):814-826.[doi:10.1109/12.508320]
    [11] Lauzac S, Melhem R, Mossé D. An efficient RMS admission control and its application to multiprocessor scheduling. In:Proc. of the 1st Merged Int'l Parallel Processing Symp. and Symp. on Parallel and Distributed Processing. IEEE Computer Society Press, 1998. 511-518.[doi:10.1109/IPPS.1998.669964]
    [12] Lauzac S, Melhem R, Mossé D. An improved rate-monotonic admission control and its applications. IEEE Trans. on Computers, 2003,52(3):337-350.[doi:10.1109/TC.2003.1183948]
    [13] Lu WC, Lin KJ, Wei HW, Shih WK. Rate monotonic schedulability tests using period-dependent conditions. Real-Time Systems, 2007,37(2):123-138.[doi:10.1007/s11241-007-9034-1]
    [14] Park DW, Natarajan S, Kanevsky A. Fixed-Priority scheduling of real-time systems using utilization bounds. Journal of Systems and Software, 1996,33(1):57-63.[doi:10.1016/0164-1212(95)00105-0]
    [15] Lee CG, Sha L, Peddi A. Enhanced utilization bounds for QoS management. IEEE Trans. on Computers, 2004,53(2):187-200.[doi:10.1109/TC.2004.1261828]
    [16] Lehoczky J, Sha L, Ding Y. The rate monotonic scheduling algorithm:Exact characterization and average case behavior. In:Proc. of the 10th IEEE Real Time Systems Symp. Santa Monica:IEEE Computer Society Press, 1989. 166-171.[doi:10.1109/REAL. 1989.63567]
    [17] Bini E, Buttazzo G. The space of rate monotonic schedulability. In:Proc. of the 23th IEEE Real-Time Systems Symp. IEEE Computer Society Press, 2002. 169-178.[doi:10.1109/REAL.2002.1181572]
    [18] Liu JX, Wang YJ, Cartmell M. An improved ratemonotonic schedulabilitytest algorithm. Ruan Jian Xue Bao/Journal of Software, 2005,16(1):89-100(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/16/89.htm
    [19] Min-Allah N, Khan SU, Wang X, Zomaya AY. Lowest priority first based feasibility analysis of real-time systems. Journal of Parallel and Distributed Computing, 2013,73(8):1066-1075.[doi:10.1016/j.jpdc.2013.03.016]
    [20] Audsley N, Burns A, Richardson M, Tindell K, Wellings AJ. Applying new scheduling theory to static priority preemptive scheduling. Software Engineering Journal, 1993,8(5):284-292.[doi:10.1049/sej.1993.0034]
    [21] Sjödin M, Hansson H. Improved response-time analysis calculations. In:Proc. of the 19th Real-Time Systems Symp. IEEE Computer Society Press, 1998. 399-408.[doi:10.1109/REAL.1998.739773]
    [22] Min-Allah N, Khan SU, Ghani N, Li J, Wang L, Bouvry P. A comparative study of rate monotonic schedulability tests. Journal of Supercomputing, 2012,59(3):1419-1430.[doi:10.1007/s11227-011-0554-z]
    [23] Díaz-Ramírez A, Mejía-Alvarez P, Leyva-del-Foyo LE. Comprehensive comparison of schedulability tests for uniprocessor ratemonotonic scheduling. Journal of Applied Research and Technology, 2013,11(3):408-436.[doi:10.1016/S1665-6423(13)71551-7]
    [24] Liu JX, Wang YJ, Wang Y, Xing JS, Zeng HT. Real-Time system design based on logic OR constrained optimization. Ruan Jian Xue Bao/Journal of Software, 2006,17(7):1641-1649(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/17/1641.htm
    [25] Chung JY, Liu JWS, Lin KJ. Scheduling periodic jobs that allow imprecise results. IEEE Trans. on Computers, 1990,39(9):1156-1174.[doi:10.1109/12.57057]
    [26] Liu JWS, Lin KJ, Shih WK, Yu ACS, Chung JY, Zhao W. Algorithms for scheduling imprecise computations. Computer, 1991, 24(5):58-68.[doi:10.1109/2.76287]
    [27] Dey JK, Kurose J, Towsley D. On-Line scheduling policies for a class of IRIS(increasing reward with increasing service) real-time tasks. IEEE Trans. on Computers, 1996,45(7):802-813.[doi:10.1109/12.508319]
    [28] Rajkumar R, Lee C, Lehoczky J, Siewiorek D. A resource allocation model for QoS management. In:Proc. of the 18th Real-Time Systems Symp. IEEE Computer Society Press, 1997. 298-307.[doi:10.1109/REAL.1997.641291]
    [29] Millan-Lopez V, Feng W, Liu JWS. Using the imprecise-computation technique for congestion control on a real-time traffic switching element. In:Proc. of the Int'l Conf. on Parallel and Distributed Systems. IEEE Computer Society Press, 1994. 202-208.[doi:10.1109/ICPADS.1994.590126]
    [30] Ramanathan P. Graceful degradation in real-time control applications using(m,k)-firm guarantee. In:Proc. of the 27th Annual Int'l Symp. on Fault-Tolerant Computing. IEEE Computer Society Press, 1997. 132-141.[doi:10.1109/FTCS.1997.614086]
    [31] Chen X, Cheng AMK. An imprecise algorithm for real-time compressed image and video transmission. In:Proc. of the 6th Int'l Conf. on Computer Communications and Networks. IEEE Computer Society Press, 1997. 390-397.[doi:10.1109/ICCCN.1997. 623341]
    [32] Feng WC, Liu JWS. Algorithms for scheduling real-time tasks with input error and end-to-end deadlines. IEEE Trans. on Software Engineering, 1997,23(2):93-106.[doi:10.1109/32.585499]
    [33] Hansson J, Son SH, Stankovic JA, Andler S. Dynamic transaction scheduling and real location in overloaded real-time database systems. In:Proc. of the 5th Int'l Conf. on Real-Time Computing Systems and Applications. IEEE Computer Society Press, 1998. 293-302.[doi:10.1109/RTCSA.1998.726430]
    [34] Min-Allah N, Khan SU, Wang Y. Optimal task execution times for periodic tasks using nonlinear constrained optimization. Journal of Supercomputing, 2012,59(3):1120-1138.[doi:10.1007/s11227-010-0506-z]
    [35] Wang Y, Lane DM. Solving a generalized constrained optimization problem with both logic AND and OR relationships by a mathematical transformation and its application to robot motion planning. IEEE Trans. on Systems, Man, and Cybernetics(Part C:Applications and Reviews), 2000,30(4):525-536.[doi:10.1109/5326.897079]
    [36] Boggs PT, Tolle JW. Sequential quadratic programming. Acta Numerica, 1995,4(1):1-51.
    [37] Byrd RH, Hribar ME, Nocedal J. An interior point algorithm for large-scale nonlinear programming. SIAM Journal on Optimization, 1999,9(4):877-900.[doi:10.1137/S1052623497325107]
    [38] Hillier F, Lieberman G. Introduction to Operations Research. McGraw-Hill, 2001.
    [39] Jenkyns T, Stephenson B. Fundamentals of Discrete Math for Computer Science. London:Springer-Verlag, 2012.[doi:10.1007/978- 1-4471-4069-6]
    [40] Wasserman L. All of Nonparametric Statistics, Vol.4. New York:Springer-Verlag, 2006.[doi:10.1007/0-387-30623-4]
    [41] Sheather SJ, Jones MC. A reliable data-based bandwidth selection method for kernel density estimation. Journal of the Royal Statistical Society(Series B:Methodological), 1991,53(3):683-690.
    [42] Raykar VC, Duraiswami R, Zhao LH. Fast computation of kernel estimators. Journal of Computational and Graphical Statistics, 2010,19(1):205-220.[doi:10.1198/jcgs.2010.09046]
    [43] Andrei N. On the complexity of MINOS package for linear programming. Studies in Informatics and Control, 2004,13(1):35-46.
    [44] TOMLAB. The TOMLAB optimization environment for fast and robust large-scale optimization in MATLAB. http://tomopt.com/tomlab/
    [45] De Moura L, Bjørner N. Satisfiability modulo theories:Introduction and applications. Communications of the ACM, 2011,54(9):69-77.[doi:10.1145/1995376.1995394]
    [46] Dutertre B, De Moura L. A fast linear-arithmetic solver for DPLL(T). In:Proc. of the 18th Int'l Conf. on Computer Aided Verification. Springer-Verlag, 2006. 81-94.[doi:10.1007/11817963_11]
    [47] Sebastiani R, Tomasi S. Optimization in SMT with LA(Q) cost functions. In:Proc. of the 6th Int'l Joint Conf. on Automated Reasoning. Springer-Verlag, 2012. 484-498.[doi:10.1007/978-3-642-31365-3_38]
    [48] Li Y, Albarghouthi A, Kincaid Z, Gurfinkel A, Chechik M. Symbolic optimization with SMT solvers. In:Proc. of the 41st Annual ACM SIGPLAN-SIGACT Symp. on Principles of programming languages. ACM Press, 2014. 607-618.[doi:10.1145/2535838. 2535857]
    [49] De Moura L, Bjørner N. Z3:An efficient SMT solver. In:Proc. of the Theory and Practice of Software, 14th Int'l Conf. on Tools and Algorithms for the Construction and Analysis of Systems. Springer-Verlag, 2008. 337-340.[doi:10.1007/978-3-540-78800- 3_24]
    [50] Dutertre B. Yices 2.2. In:Proc. of the 8th Int'l Joint Conf. on Automated Reasoning. Springer-Verlag, 2014. 737-744.[doi:10.1007/978-3-319-08867-9_49]
    附中文参考文献:
    [3] 王永吉,陈秋萍.单调速率及其扩展算法的可调度性判定.软件学报,2004,15(6):799-814. http://www.jos.org.cn/1000-9825/15/799.htm
    [18] 刘军祥,王永吉,Matthew Cartmell.一种改进的RM可调度性判定算法.软件学报,2005,16(1):89-100. http://www.jos.org.cn/1000-9825/16/89.htm
    [24] 刘军祥,王永吉,王源,邢建生,曾海涛.基于逻辑"或"约束优化的实时系统设计.软件学报,2006,17(7):1641-1649. http://www.jos.org.cn/1000-9825/17/1641.htm
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

陈力,王永吉,吴敬征,吕荫润.基于树状线性规划搜索的单调速率优化设计.软件学报,2015,26(12):3223-3241

Copy
Share
Article Metrics
  • Abstract:3682
  • PDF: 4875
  • HTML: 1358
  • Cited by: 0
History
  • Received:September 23,2014
  • Revised:April 14,2015
  • Online: December 04,2015
Links:Institute of Software, CASChina Computer FederationCASNSFC
You are the first2034066Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address：4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code：100190
Phone：010-62562563 Fax：010-62562533 Email：jos@iscas.ac.cn
Technical Support：Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063