RM算法与EDF算法

:2003-03-28:(1971—),,,、、、J2EE。翟鸿鸣(交通银行西安分行计算中心,陕西西安710004)　:。:,RM、DMEDF、LLFMLLF,,。:;;;:TP301.6　　　　　　:A　　　　　　　:1005-3751(2003)10-0099-03StudyofSchedulingAlgorithminRealTimeSystemonUninprocessorsZHAIHong-ming(Xi'anBranch,BankofCommunication,Xi'an710004,China)Abstract:Therealtimeschedulingalgorithmplaysanimportantruleintherealtimesystems.Thestatic-priorityschedulingalgorithmandthedynamic-priorityschedulingalgorithmaretwokindsofschedulingalgorithmsonuninprocessorsystems.Introducestheschedul-ingalgorithmsuchasRM,DM,EDF,LLFandMLLF,analysestheconditionandtheproblemforthesealgorithms.Keywords:realtimesystem;static-priority;dynamic-priority;schedulingalgorithm　　,。。,,,。,,,。RMDM[1,3],EDFELF[1,2],,MLLF。。1　,。{Ti}ni=1,Ti(ei,di,pi,ri),ei、di、Pi,、,ri,。ri,kTiK,di,k=ri,k+di。,。g(t){Ti}ni=1,g(t)=TiTit,g(t)=0t,。Tit:ri,k≤t≤ri,k+di。U(T),,,:U(T)=∑ni=1ei/pi,0≤U(T)≤1,U(T)=1,。2　:,,;:,,。,。13　10200310　　　　　　　　　　　　　　　　MicrocomputerDevelopment　　　　　　　　　　　　　　Vol.13　No.10Oct.20032.1　RMRMRatemonotonicscheduling。RM。,。RM,,,;,。,,,,。RM。1::T1=(1,3,3,0),T2=(1,4,4,0),T3=(1,5,5,0),RM。RM,,T1,T2,T3。1。图1　RM调度算法(1):t=0,,T1,,。t=1,T1,T2,t=2。t=2,T1T2,T3,T3t=3。t=3,T1,。,T3,,RM。,:U(T)=1/3+1/4+1/5=47/60,60,47,13。2::T1=(1,4,4,0),T2=(3,8,8,0),T3=(5,16,16,0),T4=(2,32,32,0),:。2。图2　RM调度算法(2),:U(T)=1/4+3/8+5/16+2/32=1,,。,RM,,。RM,,RM。RM,。2.2　DMDMDeadlinemonotonicscheduling,RM。DM,,,,,。:,,,。3::T1=(1,2,3,6),T2=(1,3,12,3),T3=(2,4,4,1),DM,,T1,T2,T3。3。图3　DM调度算法:t=0,,t=1,T3,T3t=1,t=3。t=3,T2,,t=4。t=4,,。t=5,T3,,t=6,T1,T3。t=7,T1,T3。DMRM,。RM,DM,。DM,,DMRM。3　3.1　EDFEDFEarliestdeadlinefirstscheduling,。EDF,EDF。EDF,:di(t)-t,·100·　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　13di(t)。,,,。EDF,,,,,。4::T1=(1,3,3,0),T2=(1,4,4,0),T3=(1,5,5,0),EDF。4。图4　EDF调度算法:t=0,,T1,,T1。t=1,T2T3,,T2,T2。t=3,T1,T1T3,,T3。3.2　MLLFLLFLeastlaxityfirst。LLFEDF,EDF,:di(t)-t,LLF,di(t)-t-ei(t)。MLLFmodifiedleastlaxity。MLLFEDFLLF,,:di(t)-t-f×ei(t),f01。,di(t)=ri+di　　　　　　　　　triri+t-ripi」pi+di　　　t≥riei(t)=0　　　　　　　　　　　　triei-∫tri+t-ripi」piχgiri(x)dx　　t≥rif=0,MLLFEDF,f=1,MLLFLLF。5:T1=(3,6,6,0),T2=(4,8,9,0),MLLF。f=1,LLF,MLLF。5。MLLFf01,　0:ml1(0)=6-0-1×3=3　　　ml2(0)=8-0-1×4=4　1:ml1(1)=6-1-1×2=3　ml2(1)=8-1-1×4=3　2:ml1(2)=6-2-1×1=3　ml2(2)=8-2-1×4=2　3:ml1(3)=6-3-1×1=2　ml2(3)=8-3-1×3=2　4:r1notactive　ml2(4)=8-4-1×3=1　5:r1notactive　ml2(4)=8-5-1×2=1　6:ml1(6)=12-6-1×3=3　ml2(6)=8-6-1×1=1　7:ml1(7)=12-7-1×3=2　r2notactive　8:ml1(8)=12-8-1×2=2　r2notactive　9:r1notactive　ml2(9)=17-9-1×4=4　10:r1notactive　ml2(10)=17-10-1×3=4　11:r1notactive　ml2(11)=17-11-1×2=4　12:ml1(6)=18-12-1×3=3　ml2(6)=17-12-1×1=4图5　MLLF调度算法,,。4　RMDM、EDFLLF,,,。:①,(),,。②,。,,。,,。,,,。:[1]　LiuCL,LaylandJW.SchedulingAlgorithmsforMultipro-gramminginaHard-Real-TimeEnvironment[J].JACM,1973,20(1):174-189.[2]　MokAK.FundamentalDesignProblemsofDistributedSys-temsfortheHard-Real-TimeEnvironment[D].PhD.The-sis,LaboratoryforComputerScience,MIT,Cambridge,Mass.,1983.[3]　JohnL,LuiSha,YeDing.TheRateMonotonicSchedulingAlgorithm:ExactCaseCharacterizationAndAverageCaseBe-havior[A].Proc.IEEEReal-TimeSystemsSymposium[C].[s.l.]:[s.n.],1989.166-171.·101·10　　　　　　　　　　　　　　: