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

摘要

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