实时系统调度算法的抢占控制模型与其遗传算法实现

《实时系统调度算法的抢占控制模型与其遗传算法实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、本人声研究成果除研究成果，的同志对本的谢意。本学位文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。(如作者和导师同意网上交流，请在下方签名：否则视为学位论文作者签名：乏厢之名导师签名：签字El期：勿防莎二仞签字目期：1勿勺苫．乙，1D7×≮觏＆雕糸不nL一、、、●j工●，东北大学硕士学位论文摘要实时系统调度算法的抢占控制模型及其遗传算法实现摘要嵌入式实时系统主要面向现实世界中与时间因素相关的应用需求，在工业控制

2、、航空航天和军事设备等众多领域里有着广泛的应用，它所关注的不仅是计算结果在逻辑上的正确性，而且还有输出结果时间上的及时性。另外，嵌入式实时系统的处理能力和内存容量往往是有限的，这需要调度算法能恰当地排列任务执行顺序，在保证系统可调度性的同时使用更少的资源。基于上述原因，本文首先根据实时系统的特点和需求对现有调度算法存在的缺点和不足进行分析，提出了一种基于非抢占时间片的抢占控制优化模型。该模型以任务的最差响应时间小于其时限作为任务可调度性判断的充要条件，因此该模型应该能够在保证任务可调度性的同时，使任务集合在执行期间发生的总抢占次

3、数最小，其结果就是既保证了任务集合的可调度性又降低了由于抢占而引起的资源开销。然后，使用遗传算法对优化模型进行了脱机实现。为了提高遗传搜索的效率，本文中遗传算法初始个体的设计采用了以次优值为启发性初值的方法。由于遗传运算过程中会产生非法解(即产生的任务抢占次数使整个任务集合不可调度)，本文采用了一种惩罚函数的方式来解决此问题。最后，本文通过实测对计算结果进行检验和分析。进行实验的软件平台为嵌入式实时操作系统WebitOS。通过在WebitOS上使用C语言编程将遗传算法计算出来的结果加以实现，同时创建大量的任务在不同调度算法下对其

4、进行检验。结果显示基于非抢占时间片的抢占控制优化模型确实能够在保证任务的可调度性、实时性的同时，有效减少不同调度算法下任务发生抢占的次数。关键词：实时系统；调度算法；抢占调度；非抢占调度；遗传算法；惩罚函数；时问片一Il—●东北大学硕士学位论文AbstractPreemptionControlModelofSchedulingAlgorithmforReal-TimeSystemsandGeneticAlgorithmImplementationAbstractEmbeddedreal-timesystemsmostlyface

5、totherealworldapplicationsthatrelativetothetimefactorandhavebeenextensivelyappliedinmanyfieldssuchasindustrycontrol，spaceflightandmilitaryequipments．Embeddedreal—timesystemsconcernnotonlylogicalcorrectnessbutalsothetimerequirementsoftheoutputresults．Furthermore，becau

6、seofthelimitationoftheprocessingabilityandthestoragecapacityoftheembeddedreal—timesystems，usuallyschedulingalgorithmmustcorrectlyarrangetheimplementationorderofthetasksandatthesametimeguaranteetheschedulabilityofthesystemusingfewerresources．Basingonabovereasons，inthi

7、sdissertationthedeficienciesandthedisadvantagesofthepopularschedulingalgorithmsarestudiedfirstandthenapreemptioncontrolmodelbasingonnon—preemptivetimesliceispresented．Thepreemptioncontrolmodelusestheconditionthattheworstcaseresponsetimeislessthanorequaltothedeadlineo

8、fthetaskasthenecessaryandsufficientconditionoftheschedulabilityofthetasks．Astheresult，themodelcanguaranteetheschedulabilityofthetas