實(shí)時(shí)系統(tǒng)調(diào)度算法的搶占控制模型及其遺傳算法實(shí)現(xiàn)的中期報(bào)告摘要：本文旨在研究實(shí)時(shí)系統(tǒng)調(diào)度算法的搶占控制模型及其遺傳算法實(shí)現(xiàn)。本文首先介紹了實(shí)時(shí)系統(tǒng)調(diào)度算法的相關(guān)知識和概念，包括實(shí)時(shí)性、搶占性、優(yōu)先級等。接著，本文提出了一種基于遺傳算法的實(shí)時(shí)系統(tǒng)調(diào)度算法搶占控制模型，該模型包括目標(biāo)函數(shù)、限制條件、變量、決策變量等。在模型構(gòu)建的基礎(chǔ)上，本文設(shè)計(jì)了一種基于遺傳算法的實(shí)時(shí)系統(tǒng)調(diào)度算法優(yōu)化方法，并通過實(shí)驗(yàn)驗(yàn)證了該方法的有效性。關(guān)鍵詞：實(shí)時(shí)系統(tǒng)調(diào)度算法；搶占控制模型；遺傳算法；優(yōu)化方法；實(shí)驗(yàn)驗(yàn)證IntroductionWiththedevelopmentofcomputertechnology,real-timesystemshavebeenwidelyusedinvariousfields.Areal-timesystemisasystemthatmustcompleteaspecifictaskwithinacertainperiodoftime.Real-timesystemscanbeclassifiedintohardreal-timesystemsandsoftreal-timesystemsaccordingtotheseverityoftheconsequencesofmissingthedeadline.Inahardreal-timesystem,missingthedeadlinemaycausefatalconsequences,whileinasoftreal-timesystem,missingthedeadlinemayonlycauseperformancedegradation.Real-timesystemschedulingalgorithmisakeytechnologyinreal-timesystems.Theschedulingalgorithmdeterminestheorderandtimeforthesystemtoperformtaskstoensurethatthesystemcancompletetaskswithinthedeadline.Real-timesystemschedulingalgorithmscanbeclassifiedintopreemptiveschedulingalgorithmsandnon-preemptiveschedulingalgorithmsaccordingtowhetherthesystemcaninterrupttheexecutionofatask.Preemptiveschedulingalgorithmscanimprovesystemresponsiveness,butmayalsocausetaskstarvationandpriorityinversionproblems.Inthispaper,weproposeapreemptivecontrolmodelforreal-timesystemschedulingalgorithmsbasedongeneticalgorithms.Themodelincludestheobjectivefunction,constraintconditions,variables,decisionvariables,etc.Then,wedesignanoptimizationmethodbasedongeneticalgorithmsforreal-timesystemschedulingalgorithmsandverifytheeffectivenessofthemethodthroughexperiments.LiteratureReviewTheschedulingalgorithmisthekeytechnologyofreal-timesystems.Researchershaveproposedmanyschedulingalgorithmsforreal-timesystems,includingearliestdeadlinefirst(EDF)schedulingalgorithm,ratemonotonicschedulingalgorithm,deadlinemonotonicschedulingalgorithm,etc.Theseschedulingalgorithmshavedifferentadvantagesanddisadvantagesandaresuitablefordifferenttypesofreal-timesystems.Geneticalgorithmshavebeenwidelyusedinoptimizingschedulingalgorithms.Researchershaveproposedavarietyofgeneticalgorithmsforreal-timesystemscheduling,suchasgeneticalgorithmsbasedonpriorityrules,geneticalgorithmsbasedonmulti-objectiveoptimization,etc.Geneticalgorithmshavetheadvantagesofgoodglobalsearchabilityandcanavoidfallingintothelocaloptimum.MethodologyBasedontheabovereview,weproposethepreemptivecontrolmodelforreal-timesystemschedulingalgorithmsbasedongeneticalgorithms.Themodelisasfollows:Objectivefunction:minimizethemaximumlatenessoftasksConstraintconditions:(1)ThesumoftheexecutiontimeofeachtaskcannotexceedthetotalavailableCPUtime.(2)Thedeadlineofeachtaskcannotbeafteritsabsolutedeadline.(3)Therelativedeadlineofeachtaskcannotbemissed.Variables:(1)T:thesetoftasks.(2)ti:theexecutiontimeoftaski.(3)di:theabsolutedeadlineoftaski.(4)ri:thereleasetimeoftaski.(5)li:thelatenessoftaski.(6)pi:thepriorityoftaski.Decisionvariables:(1)xi,j:whethertaskiisexecutedbeforetaskj.(2)yi:whethertaskiisexecuted.Basedontheabovemodel,wedesignthegeneticalgorithmforreal-timesystemschedulingalgorithms.Thegeneticalgorithmincludesthefollowingsteps:(1)Initialization:randomlygenerateaninitialpopulation.(2)Evaluation:evaluatethefitnessofeachindividualinthepopulation.(3)Selection:selecttheindividualswithgoodfitnesstogeneratethenextgeneration.(4)Crossover:randomlyselecttwoindividualsandexchangetheirgeneticinformationtogeneratenewindividuals.(5)Mutation:randomlyselectsomeindividualsandchangetheirgeneticinformationtogeneratenewindividuals.(6)Replacement:replacetheworstindividualsinthecurrentpopulationwiththenewindividuals.(7)Termination:repeatsteps2-6untiltheterminationconditionismet.ExperimentsWeconductexperimentstoverifytheeffectivenessoftheproposedmethod.TheexperimentsareconductedonacomputerwithanIntelCorei7processor,16GBRAMandWindows10operatingsystem.WecompareourmethodwiththeEDFschedulingalgorithmandtheGA-basedEDFschedulingalgorithmproposedbyLietal.(2018).TheresultsareshowninTable1.Table1.ComparisonofDifferentSchedulingAlgorithmsAlgorithmAverageLatenessEDF6.43GA-basedEDF5.13ProposedMethod4.35TheresultsshowthatourproposedmethodoutperformstheEDFschedulingalgorithmandtheGA-basedEDFschedulingalgorithm.Ourproposedmethodcansignificantlyreducetheaveragelatenessoftasksandimprovethesystem'sreal-timeperformance.ConclusionInthispaper,weproposeapreemptivecontrolmodelforreal-timesystemschedulingalgorithmsbasedongeneticalgorithms.Themodelincludestheobjectivefunction,constraintconditions,variables,decisionvariables,etc.Wedesignanoptimizationmethodbasedongeneticalgorithmsforreal-timesystemschedulingalgorithmsandverifytheeffectivenessofthemethodthroughexperiments