硕士论文-多媒体系统任务调度算法研究

华中科技大学硕士学位论文多媒体系统任务调度算法研究姓名：张炫申请学位级别：硕士专业：计算机系统结构指导教师：文远保20060510IIIAbstractWiththedevelopmentofmultimediacodingtechnology,alotofmultimediaapplicationswiththecharacteristicofstreamarepopular.Theseapplicationsneedtobeprocessedintherestrictedtime,forexample,soundandpicturecannotstopinthevideoconferencesystem.AndItisdifferentwithtraditionalreal-timeapplications,missingframesoccasionallywillnotcausethesevereresultinthekindofapplicationswhichjustdemandtheprobabilisticsuccessofthedataprocessfinishedintherestrictedtime.Sowecallthekindofapplicationsoftreal-timeapplication.Multimediastreamapplicationsneedthereal-timesupportfromthestorage,transmissionandCPU(CenterProcessingUnit)schedulinginthemultimediasystem.AndCPUisoneoftheimportantresourcesinthesystem.AgoodCPUtaskschedulingalgorithmcanofferlowdeadlinemissingpercentofthetasksandhighCPUutilization,whicharekeyfactorsforreal-timemultimediaapplication.Duetotraditionalwayoftime-sharingschedulingcannotsatisfythereal-timedemandofmultimediaapplication,thereal-timeschedulingalgorithmformultimediastreamwaspaidspecialattention.Inthepastresearch,majorschedulingwaysarepessimisticandoptimisticideawhicharebasedontraditionalperiodicmodel,periodicmultiframetaskmodelandheuristicscheduling.ButtherearesomeproblemssuchasnothavingexactschedulingconditionsorlowCPUutilization.Forsolvingtheaboveproblems,themultimediastreamtaskiscalledirregularperiodictask.Accordingtothenotion,theirregularperiodicmodelispresentedtotransformittoaperiodictaskandaburstingtask.Thetasksetisscheduledintheway,thatisperiodictaskscheduledbyRM(RateMonotonic)andburstingtaskbysporadicserver.Thewaynotonlyofferthehardreal-timeguaranteefortheperiodictask,butalsokeepthemissingdeadlinepercentoftheburstingtasklowtosatisfythesoftreal-timedemandsothatguaranteemultimediastreamtaskreal-time.Atthesametime,thesystemcanallowmoretaskstoenterandimprovetheCPUresourceutilization.Keywords:multimedia,real-time,taskscheduling,RateMonotonic,multimediastream?_____?“v”1(Hardreal-timeapplications)()(Best-effortapplications)(VOD)(Softreal-timeapplications)[1]CPUCPUCPUCPUCPU2WINDOWSNT/2000/XPUNIXCPU[2]64Kb/sADPCMAdaptiveDifferentialPulseCodeModulation(a)(b)0.25s330240Mbit[2]4CPUCPUWINDOWSNT/2000/XPUNIXCPU(VideoOnDemand,VOD)5[3]I/O315ms7200r/min3.4msI/OCPUCPUCPUCPU[4]Non-PreemptiveMode(PreemptiveMode)CPUCPU6CPU[5]CPUCPU1.2.2SVR4UNIXAT&TUNIXSVR4[6]7SVR40-1590-5960-99100-159UNIXSVR4rtproc.rt_pritsproc.rt_prirt_dptbl[]ts_dptbl[]SVR4LINUXLinuxUNIXUNIXLinuxLinux[7][8]Linuxpolicyprioritycounterrt_prioritypolicyFIFORRSCHED_OTHERpriority()counterpriority1rt_priorityLinuxpolicyLinuxcountercounterpolicy0-70counterlpolicycounter0counterLinuxFIFORRcounter8rt_prioritygoodness()goodness()1000+p-rt_priorityrt_priorityLinuxSVR4WindowsNT/2000/XPWindowsNT/2000/XP[9]321-1516-31SetThreadPriority()1631115115(15)SVR4WindowsNT/2000/XPSVR41.2.3SVR4UNIXLinuxWINDOWSNT/2000/XP9CPUSVR4[10]XCPUXCPU1022.12.111ISO/IECMPEGITUH[12-13]MPEGMovingPictureExpertsGroupMPEGMPEG-1MPEG-2MPEG-4MPEG-7[14]MPEG-11.5MbpsMPEG-2(TransportStream)MPEG-2MPEG-4[15-16]MPEG-4FineGranularScalable,FGS[17]ProgressFineGranularScalable,PFGSMPEG-7(MultimediaContentDescriptionInterface)[18]MPEG1MPEG4MPEG1MPEG1[19]MPEG130HzNTSC25HzPALMPEG13intra-picturesIpredictedpicturesPBidirectionally-predictivecodedB122.281I1P6BBIPIPPI3B2.2MPEG1BBIPBBBBB2.321IPBBIBBPBBPBBPBBPBBIBBPBBPBBPBBPBB123456789101112131415161718192021222324252627282930115I2.313302I8P20BIP2PBIPB4P1I1I4PB2.32.414237561089131112161415IPBBPBBPBBPBBIBB2.4MPEG1MPEG12.12.1MPEG1DCTDCTMCMPEG419992MPEG4V1.012MPEG4V2.0[20]MPEG4MPEG448006400bps176144MPEG414MPEG42.5MPEG4VO,VideoObjectVOVOVO3VOVODCTIDCT;MPEG42.5MPEG42.2.2HH.261H[21]H.261CIFCommonIntermediateFormatQCIFQuarterCIFQCIF157.5H.2612530CIFH.261ISDNCIF15QCIFH.261H.261H.261IP1I3PIP688(Block)(Macroblock)4(Y)2(CbCr)GOB(GroupofBlock)4HeaderH.261H.261ITU-TH.262H.263H.264H.264SliceH.264CAVLCCABACCABACCAVLC10%SliceH.264Exp-GolombCABACCAVLCH.264VLCCABACH.26416441616449082DC16164vertical,horizontal,DC,planechroma884vertical,horizontal,DC,planeDCH.2647H.2641/41/8H.264FMO44H.264DCTDCT44chroma1616DCT44DC224417HadamardH.26388DCTH.26444DCTHMPEG[22]MPEGMPEG2.6Intenet2.618MPEG-1VHSHDTV1.2Mbps20MbpsHDTV1.2Gbps2.22.2(Mbps)H.26124:10.064-2MPEG1100:11.2-2MPEG220-100:14-60(informationunits)MPEG(frame)40msMPEG2.7IPBIPBIBBPBBPBBPBBIMPEG192.7MPEG2.4MPEGH20CPUCPUCPUCPUCPUCPUSVR4UNIXWINDOWSNT/2000/XPCPUMPEGTT=(r,p,c,d)[23]rpccdd=piriprip3.1cr0pt3.121CPU3.2.1T(r,c,p,d)rTcTdT(Deadline)pTRM(RateMonotonic)[25]EDF(EarliestDeadlineFirst)[26]DM(DeadlineMonotonic)RMEDF[25],,,{()|1,2,...}iiiiiTTrcpdin===,(1,2,...)iidpin==221/1212...(21)nnncccnppp+++≤-(3.1)RM1212...1nncccppp+++≤(3.2)EDFTCPUic/ip1niiicp=∑CPUn1/lim(21)ln(2)0.693nnn→∞⎡⎤-=≈⎣⎦CPU69RM[27]RMEDFEDFRM[28]EDF{T}idiTCPUjTjTjdiTidjTiTiTEDF23RM{T}iTjTipjpiprjprprRMEDF2RMEDFic[29]icic∧CPUic∧/ipCPUCPUicic-24[30]3.3.1(C,P)CP30/33ms33ms3SQFSQFQ/SFSSQF=(icip)i=1,2,,nEDFCPU1niiicp=∑1CPU1EDF253.3.2nmCPUrt={rtiT|rtiT=(ir,ic,ip),i=1,2,,n}mt={mtiT|mtiT=(ir,ic,ip,iS,iQ,iF),i=1,2,