作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程

• 体系结构与软件技术 • 上一篇    下一篇

基于跳表与布隆过滤器的混合关键任务调度方法

黄姝娟,容晓峰,肖锋,茹媛   

  1. (西安工业大学 计算机科学与工程学院,西安 710021)
  • 收稿日期:2016-02-24 出版日期:2017-01-15 发布日期:2017-01-13
  • 作者简介:黄姝娟(1975—),女,讲师、博士,主研方向为嵌入式与分布式计算;容晓峰,教授、博士;肖锋,副教授、博士;茹媛,讲师。
  • 基金资助:
    国家自然科学基金面上项目(61572392);陕西省工业科技攻关项目(2015GY031);陕西省教育厅基金(15JK1342);西安工业大学校长基金(XAGDXJJ14015)。

Hybrid Critical Task Scheduling Method Based on Skip List and Bloom Filter

HUANG Shujuan,RONG Xiaofeng,XIAO Feng,RU Yuan   

  1. (School of Computer Science and Engineering,Xi’an Technological University,Xi’an 710021,China)
  • Received:2016-02-24 Online:2017-01-15 Published:2017-01-13

摘要: 传统实时任务对共享数据的访问通常采用锁机制,该机制可能会引起死锁、优先级翻转以及CPU饥饿的现象。如果应用在混合关键系统中,可能会导致关键级别翻转。针对上述问题,提出一种跳表与布隆过滤器相结合的同步方法。该方法将混合关键任务的优先级调度队列采用跳表数据结构存储,实现该数据结构的无锁算法,并通过基于锁机制的布隆过滤器判断其是否已被调度执行。实验结果表明,与传统的基于锁机制的位图、堆结构以及ELB-trees的同步机制方法相比,该方法能减少死锁现象的发生和降低优先级翻转的几率,并且在关键级别翻转时,提升多核运行的效率。

关键词: 多核, 实时调度, 周期, 同步机制, 数据结构

Abstract: Traditional real-time tasks usually access the shared data using the lock mechanism.This lock synchronization mechanism may cause some phenomena such as deadlock,priority inversion and CPU starvation.It may also cause criticality inversion when used in the mixed-criticality system.So this paper proposes a new synchronization method that combines skip-list and Bloom filter for the mixed-criticality system.The skip-list is used as a shared priority queue and implemented with the lock-free algorithm and the Bloom filter based on the lock mechanism is used for querying if the task is scheduled.Experimental results show that the method has greatly reduced the phenomena of deadlock and priority inversion and increased the multi-core efficiency after the criticality inversed compared with the traditional lock mechanism and ELB-trees.

Key words: multi-core, real-time scheduling, cycle, synchronization mechanism, data structure

中图分类号: