Method to Evaluate Earliest Release Time of New Real-time Tasks

doi:10.19678/j.issn.1000-3428.0050021

计算机工程 ›› 2018, Vol. 44 ›› Issue (12): 62-67. doi: 10.19678/j.issn.1000-3428.0050021

Method to Evaluate Earliest Release Time of New Real-time Tasks

QIAN Guangming,SU Shen

College of Information Science and Engineering,Hunan Normal University,Changsha 410081,China

收稿日期:2018-01-08 出版日期:2018-12-15 发布日期:2018-12-15
作者简介:QIAN Guangming (1963—),male,professor,main research direction is appliaction in real-time and embedded systems;SU Shen,master.
基金资助:
Changsha Municipal Science and Technology Foundation (K15ZD053-43)

Method to Evaluate Earliest Release Time of New Real-time Tasks

QIAN Guangming,SU Shen

College of Information Science and Engineering,Hunan Normal University,Changsha 410081,China

Received:2018-01-08 Online:2018-12-15 Published:2018-12-15

摘要/Abstract

摘要：

In a periodic real-time system scheduled with the Earliest Deadline First (EDF) algorithm,it is necessary to compress some current tasks to avoid overloading if new task requests to run.Compressing a task means that its period is prolonged while its computation time keeps unchanged.An interesting problem is to find the earliest time to release new tasks without any deadline missing,that is,the earliest smooth insertion time.In this paper,a general frame to calculate the earliest time with multiple rounds of deadline checking is given,which shows that the checking can be done from the request time of the new tasks.A smart way is provided and proved,which takes the value of the Δ checking of the current round as the time step to the next.These techniques potentially reduce the amount of the calculation and the number of the rounds of the checking to get the earliest time.Simulation results are also given to support the conclusion.

关键词: total utilization, new tasks insertion, simple way, smart way, &Delta, checking

Abstract:

Key words: total utilization, new tasks insertion, simple way, smart way, &Delta, checking

中图分类号:

TP316.2

QIAN Guangming,SU Shen. Method to Evaluate Earliest Release Time of New Real-time Tasks[J]. 计算机工程, 2018, 44(12): 62-67.

QIAN Guangming,SU Shen. Method to Evaluate Earliest Release Time of New Real-time Tasks[J]. Computer Engineering, 2018, 44(12): 62-67.

http://www.ecice06.com/CN/Y2018/V44/I12/62

参考文献

［1］BUTTAZZO G C,LIPARI G,CACCAMO M,et al.Elastic scheduling for flexible workload management［J］.IEEE Transanctions on Computers,2002,51(3):289-302.
［2］BECCARI G,CASELLI S,ZANICHELLI F.A technique for adaptive scheduling of soft real-time tasks［J］.Real Time Systems,2005,30(3):187-215.
［3］BAMBAGINI M,MARINOIN M,AYDIN H,et al.Energy-aware scheduling for real-time systems:a survey［J］.ACM Transactions on Embedded Computing Systems,2016,15(1):1-7,34.
［4］ALBERS S.Energy-efficient algorithms［J］.Communications of the ACM,2010,53(5):86-96.
［5］LIU C L,LAYLAN J W.Scheduling algorithms for multiprogramming in a hard real-time environment［J］.Journal of the ACM,1973,20(1):40-61.
［6］QIAN G.An earlier time for inserting and/or accelerating tasks［J］.Real Time Systems,2009,41(3):181-194.
［7］BUTTAZZO G C,LIPARI G,ABENI L.Elastic task model for adaptive rate control［C］//Proceedings of IEEE Real-time Systems Symposium.Washington D.C.,USA:IEEE Press,1998:286-295.
［8］REAL J,CRESPO A.Mode change protocols for real-time systems:asurvey and a new proposal［J］.Real Time Systems,2004,26(2):161-197.
［9］AHMED M,FISHER N.Tractable schedulability analysis and resource allocation for real-time multi-modal systems［J］.ACM Transactions on Embedded Computing Systems,2014,13(2s):1-39.
［10］PEDRO P,BURNS A.Scheduabilty analysis for mode change［C］//Proceedings of 10th EUROMICRO Workshop on Real-Time Systems Symposium.Berlin,Germany:［s.n.］,1998:172-179.
［11］PILLAI P,SHIN K G.Real-time dynamic voltage scaling for low-power embedded operating systems［C］//Proceedings of 18th ACM Symposium Operating Systems Principles.New York,USA:ACM Press,2001:89-102.
［12］QIAN G.Research on transition process based on earliest deadline first algorithm［J］.Computer Engineering,2014,40(9):55-58.
［13］QIAN G,LIANG L.The research on the transition of the bandwidth transfer from multiple real-time tasks［J］.Computer Engineering,2017,43(12):292-302.
［14］JEFFAY K,STONE D L.Accounting for interrupt handling costs in dynamic priority task systems［C］//Proceedings of IEEE Real-Time Systems Symposium.Washington D.C.,USA:IEEE Press,1993:212-221.
［15］QIAN G,ZHOU Y.Research on bandwidth transfer of task pair based on earliest deadline first algorithm［J］.Computer Engineering,2016,42(4):65-69.

[1]	欧阳湘臻, 朱怡安, 李联, 史先琛. 一种安全关键的嵌入式实时操作系统内核设计[J]. 计算机工程, 2019, 45(7): 78-85.
[2]	朱怡安,黄林林,李联,罗殊彦. 多核平台下分区操作系统的安全关键任务调度方法[J]. 计算机工程, 2017, 43(12): 38-44.
[3]	梁浩,晏立,沈项军. 全局固定优先级实时调度算法分析[J]. 计算机工程, 2017, 43(12): 65-68.
[4]	钱光明,梁丽稳. 实时多任务带宽转让的过渡过程研究[J]. 计算机工程, 2017, 43(12): 292-295,302.
[5]	陈进朝,杜承烈. 单处理器平台下的严格周期任务可调度性判定[J]. 计算机工程, 2016, 42(5): 288-291.
[6]	桑磊,陆阳,俞磊. 基于贪心策略的EDF调度算法优化[J]. 计算机工程, 2015, 41(12): 96-100.
[7]	黄国兵,李瑞玲,李华丽,王琼. μC/OS-II任务优先级调度算法分析与改进[J]. 计算机工程, 2015, 41(8): 52-54,60.
[8]	姚武建, 施笑安, 周兴社. 嵌入式自适应实时资源管理[J]. 计算机工程, 2012, 38(9): 248-251.
[9]	罗晓敏, 涂时亮, 唐志强, 凌宇, 华明. 基于OSEK/VDX的RTOS设计与实现[J]. 计算机工程, 2012, 38(06): 247-249.
[10]	张健, 刘青昆, 王异奇, 周娇. Linux实时化方法的研究与实现[J]. 计算机工程, 2011, 37(11): 253-256.
[11]	王保胜, 马跃, 吴文江, 秦承刚, 丁万夫. RTAI混合任务调度器的设计与实现[J]. 计算机工程, 2010, 36(23): 240-242,245.
[12]	文俊浩;张雅洁;吴涛. 多任务并发调度在SDH网元中的应用[J]. 计算机工程, 2009, 35(20): 91-93.
[13]	李琪琪. 基于IPv6网络视频的嵌入式系统优化设计[J]. 计算机工程, 2009, 35(14): 255-257.
[14]	段星辉;代作晓. 嵌入式内核的任务上下文保护机制[J]. 计算机工程, 2009, 35(14): 20-21.
[15]	韩明峰;李小滨;郑永志. uC/OS-II内核超时等待机制的分析与改进[J]. 计算机工程, 2009, 35(7): 259-260,.

选择文件类型/文献管理软件名称

选择包含的内容

Method to Evaluate Earliest Release Time of New Real-time Tasks

Method to Evaluate Earliest Release Time of New Real-time Tasks

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

Method to Evaluate Earliest Release Time of New Real-time Tasks

Method to Evaluate Earliest Release Time of New Real-time Tasks

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价