减少周期性任务抢占与迁移的实时多核系统调度算法

《减少周期性任务抢占与迁移的实时多核系统调度算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号TP311学校代码10590UDC004密级公开深圳大学硕士学位论文减少周期性任务抢占与迁移的实时多核系统调度算法李宏岗学位类别工程硕士专业学位专业名称软件工程学院（系、所）计算机与软件学院指导教师冯禹洪原创性声明本人郑重声明：所呈交的学位论文减少周期性任务抢占与迁移的实时多核系统调度算法是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写过的作品或成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律结果由本人承担。论文作者签名：日期：年月日减少周

2、期性任务抢占与迁移的实时多核系统调度算法摘要近年来，实时系统被广泛应用在航空航天、医疗器械以及汽车电子等许多行业，与此同时，随着半导体产业生产工艺的不断革新，多核CPU已经占据绝大部份市场。而实时调度算法是实时系统的核心组成部分之一，这样，研究在多核CPU上的实时调度问题就成为一个非常重要的问题，现在的基于多核的实时调度算法如EKG（EDFwithtasksplittingandkprocessorsinagroup）算法和DP-WRAP（DeadlinePartitioningWrap）算法提高了多核同质CPU上调度周期性任务时的CPU利用率，但是，

3、这些算法仍然存在任务的迁移(migration)和抢占(preemption)次数过多的问题，这使得系统整体调度开销仍然很大以致系统性能下降。为了降低任务迁移和任务抢占次数以进一步提高系统性能，我们在现行DP_WRAP算法按任务截止时间划分时间片和CPU利用率计算方式的基础上，结合EDF调度算法的任务优先级排序技术，提出了D2_EDF算法，该算法采用资源预分配技术，在多核CPU的每一个核上，提前为将要执行的任务分配处理时间，并在每个新任务到来之前的间隙时间内，使用EDF算法在每个CPU核上去调度已分配的任务。D2_EDF算法保留了DP-WRAP算法时间

4、片数量相对较少和CPU利用率高的优点，并改进了DP-WRAP算法根据要执行任务的当前状态来反应的思想，其所用到的资源预分配技术使得该调度算法能够根据要执行任务的未来状态提前作好规划，从理论上讲，D2_EDF算法运行周期性任务将会带来相对较少的任务迁移和任务抢占次数，而在调度开销方面，D2_EDF算法与DP_WRAP，EKG等算法相比，相差不大，所以D2_EDF算法可以在保证实时性的前提下，进一步降低系统总体开销以满足用户的需要。为了评估D2_EDF算法的性能，我们开发了模拟器RTSchedulerSimCore，该模拟器使用Python语言开发，并利用

5、SimPy等相关Python开源库来模拟周期性任务在多核同质CPU上的调度，同时该模拟器具有较好的扩展性，通过添加相应的CPU参数，该模拟器可扩展到多核同构CPU平台上，并且其可以利用PyQT4等相关Python开源库来添加友好的用户界面。为了产生测试所需的任务集，我们使用了RandFixedSum算法。经过在模拟器上的运行结果表明，对在多核同质CPU上，使用D2_EDF算法去调度的周期性任务，在其调度过程中所产生的任务迁移与抢占次数，与现行DP_WRAP，EKG调I减少周期性任务抢占与迁移的实时多核系统调度算法度算法相比，均有明显的降低。关键词：ED

6、F；多核；实时调度；DP-WRAP；SimPyIISchedulingPeriodicTasksonRealtimeMulti-coreSystemswithLessPreemptionsandMigrationsAbstractInrecentyears,real-timesystemshavebeenwidelyappliedinmanyareas,e.g.aerospace,medicalinstruments,vehiclesandsoon.Atthesametime,withtherevolutionofsemiconductorproduc

7、tiontechnologies,multi-coreCPUshavegainedmostofthemarketshare.Theschedulingalgorithmisoneofthekeycomponentsofreal-timesystems,andhowtoimprovethereal-timeschedulingperformanceinmulti-coreCPUhasattractedmuchresearchattention.Existingmulti-coreschedulingalgorithms,e.g.EKGandDP-WRAP

8、,haveimprovedtheutilizationrateofmulti-coreCPUf