浅谈实时数据流系统中调度算法的研究与实现

《浅谈实时数据流系统中调度算法的研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、东北大学硕士学位论文实时数据流系统中调度算法的研究与实现姓名：欧征宇申请学位级别：硕士专业：计算机软件与理论指导教师：于戈20051201东北大学硕士学位论文摘要实时数据流系统中调度算法的研究与实现摘要随着信息处理在通信、工业生产、商务处理等领域的广泛应用，数据已不仅仅拘泥于文件、数据库等传统的静态形式，一种连续、无界、不定速度的数据流已经出现在越来越多的应用领域，如：网络监控，传感器的数据处理，生产线管理，股市信息分析等。特别是在数字化、智能化的嵌入式系统中，需要对实时数据进行复杂、高效的分析和处理。对流

2、式数据的管理是这些应用领域的核心问题，由此兴起的支持高性能实时计算的流式数据管理技术正在成为数据库领域新的研究课题。在一些关键应用中，要求实时处理大量、连续到达、快速甚至爆发的数据流，在截止期内给出实时查询结果。由于系统资源(如CPU速度、内存容量等1限制，特别是在流爆发时，不可能实时处理完数据流上的所有数据，而是尽力处理尽可能多的流数据，以获得高质量的近似查询结果。提供数据流管理功能的系统称为数据流管理系统(datastreammanagementsystem，简称DSMS)，而调度策略是影响系统的整体性

3、能最为关键的因素之一。在动态爆发的数据流环境中，如何设计实时调度策略，保证应用的实时需求，并获取高质量的近似查询结果，成为目前学术界和产业界关注的热点问题。本文讨论了当有截止期实时约束以及存在有流爆发的数据流环境中，如何设计高效的固实时任务调度策略，以最小化截止期错失率(SDMR)的问题。首先给出了固实时模型定义，并提出批划分单位，作为准确划分批任务的依据。给出了一种基于Tjck的基本批任务调度方法，称为BasicTickScheduling(BTS)方法，有效降低了系统开销。但BTS方法以统计计算(如服务

4、开销、操作符选择度估计等)作为任务执行依据，可能导致无效的执行，并且不能适应于流速时变的流爆发特性。通过克服统计计算的不足并动态控制tick批大小、消除流速时变性造成的忙等待，进而提出了一种白适应的精确批处理策略，称为AdaptiveTiekScheduling(ATS)方法，实现了最小化SDMR。理论分析和实验表明，在目前所有的批处理调度策略中，ATs方法是最有效的。关键词：数据流；实时调度；截止期；tick东北夫学硕士学位论丈ResearchandImplementationofSchedulingSt

5、rategiesinReal-timeDataStreamsAbstractWithexplosiveapplicationsofinformationprocessingincommunication，industrymanufacturing，businessprocessingandmanyotherareas，moreandmoledatataketheformofcontinuousdatastreamsratherthanfinitestom_虹dataset．Especiallyinintel

6、ligentdigitalembeddedsystems，dataneedtobeefficientlyprocessedinrealtime，Indeedstreamdatamanagementisthekeyoftheseapplications，SOthedatastreammanagementtechnologyforhi曲一performancereal—timecomputationisbecominganewandpopulartopicindatabaseresearcharea．Manys

7、tream—basedapplicationsaredeadline—sensitiveapplications，inwhicheachqueryhasaspecificreal—timeperformanceexpectation．HoweveLduetotheresourcelimitation(suchasCPU，mainmemoryandSOom，especiallyoverburstingdatastreamcircumstance，itisimpossibleforthesystemtoproc

8、essalltheincomingdata．Usually,thesystemwilltrytoprocessasmanydataaspossibletoacquirehighqual磅queryanswers．Datastreammanagementsystems(DSMS)aredevelopedtoaddresstheseapplications．AndtheSchedulerisoneofthekeyco