数据广播环境下实时调度理论及应用研究

Real-Time scheduling theory has developed dramatically in the past 40 years since Liu's seminal paper is published in 1973. In most research work on real-time scheduling theory, a fundamental assumption is that all critical resources must be accessed exclusively. However, we find that this assumption does not hold anymore for a class of novel real-time data broadcast applications in mobile computing environments. Particularly, real-time and non-real-time queries are able to access data items on the air non-exclusively. By distinguishing the key differences between traditional real-time scheduling and real-time data broadcast scheduling, we argue that several fundamental real-time scheduling problems need to be investigated, including the schedulability test of query sets and the design of new scheduling algorithms, the design and analysis of hybrid algorithms for real-time and non-real-time queries, and the extension of above problems in multi-channel data broadcast environments. With our research, not only the foundation for building real-life time-constrained data broadcast systems can be laid down, the traditional real-time scheduling theory will also be developed along an interesting new direction.

以C.L. Liu的奠基性论文为起点，实时调度理论已经发展了近40年。在几乎所有的实时调度研究中，一个最基本的假设是临界资源互斥访问--即实时任务需要互斥地访问CPU、I/O设备和核心数据结构等软硬件资源。然而，我们在研究移动计算环境下的实时数据广播调度问题时发现，临界资源互斥访问的假设在这类新应用中不再成立，实时和非实时查询可以共享地访问广播发送的数据资源。通过深入分析实时数据广播调度与传统实时任务调度的区别，我们抽象出资源可共享模型下几个重要的实时调度问题。本项目旨在对这一系列新问题进行研究，具体包括1)考虑资源共享特性的实时查询集可调度性判定及调度算法设计；2) 实时和非实时查询混合调度算法设计与分析; 3)实时查询集可调度性判定及相应调度算法在多频段广播环境下的扩展等。本项目的研究即是对传统实时调度理论的继承与发展，又为移动实时数据广播应用系统的构建提供了理论基础。

随着移动计算基础设施的日益普及，数据广播作为一种移动数据分发手段也得到了广泛的使用。在移动数据分发系统中，许多应用要求能够及时地获取数据，为此，本项目对有时间约束的移动数据分发应用所涉及到的关键理论与技术问题进行了研究。具体包括：设计了基于双曲线边界的多核（多频段）实时任务（查询）可调度性判定方法；设计了实时数据流系统中实时和非实时任务混合调度的调度算法；完成了实时数据流处理系统在多核平台上的扩展；设计实现了移动传感网中考虑能耗的数据分发和调度算法；设计了支持数据广播环境下Skyline查询数据组织和访问方法；设计了考虑数据隐私的数据分发策略等。项目组对研究得到的可调度性判定方法、实时任务调度策略等都分别进行了原型系统实现与实验验证，实验结果表明与现有技术相比，本项目所提出的新方法取得了更好的效果，例如新的判定边界可支持多达20%的新实时任务、数据流系统的多核扩展使得系统性能随着处理器核心的增加而相应递增。本项目的研究成果可以为移动数据分发系统的构建提供理论、算法和技术上的指导和借鉴。基于这些研究成果，项目组共发表英文论文共13篇，其中CCF A类论文2篇，CCF B类论文2篇，CCF C类论文6篇；发表包括《软件学报》在内的中文期刊论文共3篇。申请发明专利“一种支持多核平台下数据流处理的线程管理系统”一项，获得软件著作权一项。培养博士研究生2名，硕士研究生10名。