分级调度实时架构中处理器资源预设值的预借性
2018-01-03王华忠王文凯颜秉勇
王华忠, 王文凯, 颜秉勇
(华东理工大学化工过程先进控制和优化教育部重点实验室 上海 200237)
分级调度实时架构中处理器资源预设值的预借性
王华忠, 王文凯, 颜秉勇
(华东理工大学化工过程先进控制和优化教育部重点实验室 上海 200237)
分层多级自适应调度(AdHierSched)架构是Linux操作系统中的虚拟实时架构,在系统运行时,它通过监测各子系统对处理器资源的需求动态调整资源分配。本文在分级调度架构中提出了处理器资源预借机制(BBM),通过服务器间资源的动态分配达到处理器资源在各个实时系统中优化配置的目的,并针对AdHierSched架构中资源预设值的预借性进行设计和实现,通过静态任务和动态任务对该资源预设值预借控制器进行实验评估。实验结果表明:当AdHierSched架构伴随着处理器预借机制和资源调整机制同时运行时,内部运行任务整体的截止期限超出率减小。此外,资源预借性机制的添加导致的系统额外开销相比系统总的开销很小,表明该方案适合在实际分级调度实时系统内推广使用。
虚拟实时架构; 动态任务; 分级调度; 截止期限超出率; 资源预设值预借机制
系统虚拟技术的广泛应用使得实时操作系统(RTOSs)能够与Linux、Windows或者其他系统在同台机器上同时运行。当多个实时系统在虚拟系统中同时运行时,保持其各自建立时的时序属性不变显得尤为重要。通过运用分级调度(Hierarchical scheduling)技术可使组合后的各个系统相对安全地按照实时系统的时序要求进行运行[1]。同一硬件平台上CPU资源的分配方式严重影响着各系统性能的发挥,将CPU资源分为一系列分区并分配给各个实时系统是分级调度技术中资源分配的主要方式,通过将单个系统获得的CPU资源和其实际的需求进行比较和调整,可达到CPU资源在各个系统中的最优配置[2]。而单个系统实际资源需求是通过其内部任务的最坏情况执行时间(WCET)获得的,但在实际应用中有些实时任务的WCET不是先验已知的,例如视频解码器应用程序,其执行时间主要决定于输入视频包含的内容,因视频的不同会有显著的改变;依靠传感器来控制物理环境变化的控制任务,其对CPU需求也因环境的改变而改变。即使WCET是已知的,其值通常比平均执行时间大,若按照WCET对每个实时系统进行资源分配,必将导致处理器资源的浪费,而且任务偶尔超出截止期限的情况在大多数软实时系统中是可以接受的,所以在资源有限的嵌入式系统中过多分配CPU资源是极不可取的。
AdHierSched[3]架构具有在线监测任务资源需求的能力,从而解决了上述问题。该架构是一个将硬实时系统和软实时系统组合在一起的虚拟嵌入式实时系统,运用分级调度技术和基于服务器调度算法[4],不但能够为硬实时系统分配静态的CPU资源,而且可根据软实时系统运行时的实际需求而动态调整其获得的CPU资源[5]。分级调度架构(HSF)[6-8]运用CPU分区技术,将CPU资源分割成一定数量的区域,并将每个区域分配给架构中的子系统。架构内的全局调度器调度其内部所有子系统,每个子系统内包含一个调度其内部任务或其子系统的本地调度器。分级调度系统中采用何种方式分配处理器资源至关重要,目前虽有文献对分级调度架构中处理器资源分配领域做了研究,但对处理器资源借用机制的研究鲜有报道。本文针对该问题,提出了处理器资源预借适应机制,并将该机制运用于Linux内核可加载模块AdHierSched架构中,通过动态任务和静态任务对该机制进行评估,并对引入该机制而增加的额外开销进行分析。
1 分层多级调度架构
图1 AdHierSched架构框架图Fig.1 AdHierSched framework
2 分级调度实时架构中处理器资源预设值预借机制
2.1 服务器资源预借机制
2.2 资源预借机制触发时机的设计
因不明确任务的执行时间,服务器很难确定触发资源预借机制的时机,针对此问题,本文提出了一种新方法来告知服务器何时需要借用资源。动态任务τj的执行时间Cj未知,其截止期限与任务周期相等,当服务器没有系统资源时,其下面运行的任务因资源问题而暂停,直到该服务器资源得到补充才可以继续执行。任务截止期限与其停止时间tk之间的时间间隔为Δt,通过比较Δt与服务器周期的大小并检查该任务是否完成执行就可决定其是否会错过截止期限。如果Δt小于服务器周期,而且该任务还没有执行完,那么将不能在截止时间以前执行完。因为在服务器的资源没有得到补充前,该任务只能处于等待状态,当等待状态结束时,其已经超出截止期限。为确保任务能够在Δt时间内继续执行,服务器需要在结束当前周期前触发资源预借机制,从即将到来的下一个服务器周期中借一定数量的资源,进而维持任务能够继续执行。
图2 服务器预设资源以及任务执行时间在运行时的追踪图Fig.2 Example of server borrow budget and task execution tine
图3 触发资源预借机制时机实例图Fig.3 Example diagram of resource BBM
2.3 资源借用量的设计
在运行资源预借机制之前,通过计算系统总的可用带宽,可以获得系统内总的可用资源。因系统总的CPU带宽为1,所以总的CPU带宽减去系统应用占用的带宽即为可借用带宽,计算公式如下:
(1)
其中:Ufree为可借用带宽;Ui为服务器i所占用带宽。由系统CPU可借用带宽可计算出服务器在当前周期中最大可借资源值BMax,其计算公式如下:
BMax=UfreeTj
(2)
为了估计实际需要借用资源的量,本文运用自回归模型(Autoregressive (AR) model)[12]估计每个服务器周期中所需分配资源的量。自回归是变量对自身的回归,根据历史数据估计出相对准确的估计值,通过AR模型获得的估计值可用式(3)表述。
Bk+1=c+[θ1B1+θ2B2+…+θkBk]+ek
(3)
(4)
(5)
(6)
2.4 系统过载的处理
服务器获得系统分配的资源后,计算所得的借用资源θ有可能大于最大可借资源BMax,导致系统出现过载现象。为了避免该情形的发生,借用资源θ需要与最大可借资源BMax进行比较,当θ
3 实验设计与验证
3.1 实验环境配置
3.2 实验任务的选择和实验设计
运用动态任务和静态任务对AdHierSched架构进行评估,其中动态任务由两部分组成,一部分动态任务的执行时间由泊松分布随机产生,剩下的任务来自Mplayer音乐播放器程序。当播放音乐时,为了使AdHierSched架构能够收到Mplayer音乐播放器中的任务,Mplayer的源代码被稍微改动。在3种不同条件下进行实验:(1)架构仅伴随资源预借控制器运行;(2)架构仅伴随资源调节器运行;(3)架构同时伴随资源预借控制器和资源调节器运行。
3.3 实验结果
表1 任务和服务器参数表
3.3.2 多服务器多静态任务实验 本实验采用4个静态任务和3个服务器,详细参数见表2,服务器的重要性值与服务器的编号一致,即ζ0>ζ1>ζ2。图4示出了实验结果。实验表明,当AdHierSched在条件2下工作时,所有任务具有最低的DMR值;当任务在条件3下运行时,由于有过载发生,因服务器S0重要性值最高,系统为使其下面任务具有相对较低的DMR值,导致分配到服务器S2内的资源有所减少,造成任务τ3DMR值在此实验中有所增加。
表2 静态任务和服务器参数表
图4 多静态任务多服务器实验结果Fig.4 Multiple static tasks and severs experiment
3.3.3 单服务器单动态任务实验 本实验中,动态任务的执行时间在40～90 ms之间变化。任务和服务器的详细参数见表3。图5示出了本实验中任务执行时间的正态分布图。本实验共有20组,每组包含100个不同的执行时间。因动态任务的执行时间不同导致每组的DMR输出有所变化。图6所示为本次实验中服务器在不同运行条件下的最高、最低和平均截止期限超出率。实验结果表明,该架构在条件3下工作的表现性能最好,其平均DMR值仅为13%,运行在条件1和条件2下的平均DMR值分别为51%和19%。
表3 单服务器单动态任务实验
图5 动态任务的工作执行时间正态分布图Fig.5 Normal distribution of all the dynamic tasks
图6 单动态任务实验结果Fig.6 Single dynamic task deadline miss ratio experiment results
3.3.4 多服务器多动态任务实验 本实验采用5个动态任务和3个服务器,其详细参数见表4,实验结果见图7。由图7可知,当架构在条件1下运行时,每个服务器下面的任务都有错过截止期限的情况发生。然而当架构在条件2下运行时,其表现性能好于前者,各个任务的平均DMR值都有所下降;当架构在条件3下运行时,任务τ0、τ1和τ2的平均DMR值比在条件2时更低,但是任务τ3和τ4的DMR值反而有所增加,造成此情况是因有过载发生,所以系统根据各服务器的重要性值进行分配资源。因S0具有最高的重要性值,因此该架构以减少对服务器S1、S2资源分配为代价来提高τ0和τ1的DMR值,因此任务τ3和τ4的DMR值才会增加。
表4 多动态任务多服务器实验参数表
图7 多动态任务多服务器实验结果Fig.7 Multiple dynamic tasks and severs experiment
3.3.5 系统开销分析 去除Linux系统调度开销外,实验运行时系统内共有3种开销:(1)用来计算调度任务的分级调度开销;(2)资源预借控制器中用来计算和借用服务器资源的开销;(3)资源调控器中用来计算和调节服务器资源的开销。本文通过程序运行时的时间戳来测量开销。针对多服务器多动态任务的实验,当架构在条件3下运行时,3种开销所占的比例见图8。用来计算资源预借控制器和资源调控器的额外开销都很小,几乎相同,且3种开销的总和约为0.224 % CPU时间,故因添加资源预借控制器而添加的额外开销在实际应用中是可以接受的。
3.3.6 与分级调动架构中其他资源调节机制的比较 文献[13]通过采用反馈控制理论实现分级调度架构中处理器资源在子系统中的动态调整,反馈控制虽有很多优点,但当多个任务同时执行时,反馈控制器上的时滞问题严重,系统资源不能及时分配到相应的子系统中,因此执行任务的截止期限超
图8 条件3下系统开销实验Fig.8 Overhead experiment when the framework runs under condition 3
出率虽略有下降,但依然不是很理想;文献[14]在分级调度架构内采用模糊控制来调整CPU资源在子系统中的分配。模糊控制虽具有较强的鲁棒性和容错能力,但是由于分级架构内仅对资源信息进行模糊处理,导致架构内动态调整资源分配的能力不是很强。分级调度架构内CPU资源不同调节机制对比参见表5。
表5 分级调度架构内CPU资源不同调节机制对比
4 结 论
本文对分级调度实时系统内部的资源配置进行研究,提出了处理器资源预借机制,并在AdHierSched架构内对该机制进行研究、设计和实验验证。首先运用自回归模型为即将运行的服务器估计新的预设资源,然后通过运用实时系统中动态任务和静态任务来对该机制进行评估,实验结果表明:当AdHierSched架构伴随着处理器预借机制和资源调整机制同时运行时,内部运行任务整体的截止期限超出率减小,实时系统中资源的分配得到优化。此外,资源预借性机制的添加没有明显增加系统额外开销,因而本文提出的方案在分级调度实时应用系统中具有较高的实用价值。
[1] Chris Grujon.Gnu operating system[EB/OL].[2016-07-08].http://embedded-computing.com/articles/the-multiprocessor-multi-os-systems
[2] YAMAGUCHI A,NAKAMOTO Y,SATO K,etal.EDF-PStream:Earliest deadline first scheduling of preemptable data streams:Issues related to automotive applications[C]//2015 IEEE 21st International Conference on Embedded and Real-Time Computing Systems and Applications.Hong Kong,China,IEEE,2015:257-267.
[3] KHALILZAD N,BEHNAM M,NOLTE T.Multi-level adaptive hierarchical scheduling framework for composing real-time systems[C]//2013 IEEE 19th International Conference on Embedded and Real-Time Computing Systems and Applications.Taipei,China:IEEE,2013:320-329.
[4] LUCA M,GIUSEPPE L,PATRICIA B,etal.Iris:A new reclaiming algorithm for server-based real-time systems[C]//10th IEEE Real-Time and Embedded Technology and Applications Symposium.USA:IEEE,2004, 211-218.
[5] KHALILZAD N,BEHNAM M, NOLTE T.Implementation of the multi-level adaptive hierarchical scheduling framework[C]//9th Annual Workshop on Operating Systems Platforms for Embedded Real-Time Appllication.Paris,France:ACM,2013:11-19.
[6] BIONDI A,GIORGIO C B,MARKO B.Schedulability analysis of hierarchical real-time systems under shared resources[J].IEEE Transactions on Computers,2016,65(5):1593-1605.
[7] VAN DEN H,MARTIJN M H P,REINDER J.Budget allocations for hierarchical fixed-priority scheduling of sporadic tasks with deferred preemptions upon EDP resources[J].ACM SIGBED Review,2015,12(1):19-27.
[8] LUNNISS W,SEBASTIAN A,ROBERT I D.Accounting for cache related pre-emption delays in hierarchical scheduling with local EDF scheduler[J].Real-Time Systems,2014,52(2):13-16.
[9] INSIK S,LEE I.Periodic resource model for compositional real-time guarantees[C]// RTSS '03 Proceedings of the 24th IEEE International Real-Time Systems Symposium.USA:IEEE,2003:2-13.
[10] CHEN M S,HWANG C P,WANG H F.Analysis of the queue service probability for the EDF scheduling algorithm[C]//2016 30th International Conference on Advanced Information Networking and Applications Workshops (WAINA).Switzerland:IEEE Computer Society,2016:960-963.
[11] NATHAN F,DEWAN F.A bandwidth allocation scheme for compositional real-time systems with periodic resources[J].Real-Time Systems,2012,48(3):223-263.
[12] HIROTUGU A.Fitting autoregressive models for prediction[J].Annals of the Institute of Statistical Mathematics,1969,21(1):243-247.
[13] KHALILZAD N M,BEHNAM M,NOLTE T,etal.On adaptive hierarchical scheduling of real-time systems using a feedback controller[C]//3rd Workshop on Adaptive and Reconfigurable Embedded Systems (APRES’11).Chicago:[s.n.],2011:159-165.
[14] KHALILZAD N M,BEHNAM M,SPAMPINATO G,etal.Bandwidth adaptation in hierarchical scheduling using fuzzy controllers[C]//7th IEEE International Symposium on Industrial Embedded Systems (SIES’12).USA:IEEE,2012:148-157.
ResourceBorrowingMechanismBasedonHierarchicalSchedulingReal-TimeFramework
WANGHua-zhong,WANGWen-kai,YANBing-yong
(KeyLaboratoryofAdvancedControlandOptimizationforChemicalProcesses,MinistryofEducation,EastChinaUniversityofScienceandTechnology,Shanghai200237,China)
Multi-level adaptive hierarchical scheduling (AdHierSched) framework is a virtualized real-time framework in Linux operating system,which dynamically schedules the CPU partition sizes by monitoring the demand of every subsystem during running process.This paper presents a Budget Borrowing Mechanism (BBM) in hierarchical scheduling framework.The proposed BBM can dynamically assign the CPU resource between servers in real-time systems.Moreover,in AdHierSched framework,the proposed BBM is designed and implemented for dynamical adaptation the resource parameters.Both static and dynamic tasks are utilized to evaluate the budget borrowing controller.Experiment results show that while different tasks execute in the framework with the proposed BBM,the task’s deadline miss ratio is lower than those without using this mechanism.Compared with the total overhead of system,the extra overhead from budget borrowing calculation is very small.Hence,the proposed mechanism is suitable in actual applications.
virtualized real-time framework; dynamic task; hierarchical scheduling; deadline miss ratio; resource budget borrowing mechanism
1006-3080(2017)06-0837-07
10.14135/j.cnki.1006-3080.2017.06.013
2016-12-06
国家自然科学基金青年基金(51407078)
王华忠(1965-),男,副教授,主要研究方向为复杂工业过程建模、控制与故障诊断。E-mail:hzwang@ecust.edu.cn
TP316.2
A
