混合实时事务的延期单调速率调度算法及其可调度性分析

A Deferred Rate Monotonic Scheduling Algorithm and Schedulability Analysis for Hybrid Real-Time Transactions

对于含有实时和非实时两部分的混合实时应用 ,传统的单调速率调度算法 (RM)已不再适用 .为此 ,该文引入“混合实时事务”的概念 ,并针对这类事务提出一种延期单调速率调度算法 (DRM) ;着重分析了DRM算法对混合实时事务的可调度性 ;进行了实验测试与性能分析比较 .结果表明 ,事务集中混合实时事务占的比例越高 ,混合事务中非实时子事务占的比例越大 ,该算法的CPU使用率阈值就越高 ,且在各种情况下 ,DRM算法与RM算法相比性能都更优 ,最低情况也与之一样 .

For a kind of hybrid real time applications consisting of both real time and non real time parts, the traditional Rate Monotonic Scheduling Algorithm (RM) is no longer suitable. Therefore, based on the split transaction model, this paper introduces the concept of hybrid real time transaction, under which each transaction is divided into hard real time subtransaction(s) and non real time subtransaction(s). All of the hard real time subtransactions of hybrid transactions and other hard real time transactions together form a real time transaction set in the system, while all of the non real time subtransactions of hybrid transactions and other non real time transactions in the system compose the non real time transaction set. The transactions in the non real time set can expire without matter and thus may be scheduled with any scheduling algorithm. For the hybrid real time transactions, authors propose a new scheduling algorithm, called Deferred Rate Monotonic scheduling Algorithm (DRM). In the paper, the algorithm and the schedulability of the DRM for real time transactions with static priorities are discussed with emphases. Finally, the performance of the DRM algorithm is experimentally examined and compared with the RM algorithm based on the rate of CPU utilization in detail. The experiments show that in any case, the performance of the DRM algorithm is better than that of the RM algorithm for hybrid real time transactions,and even in the extreme case of full hard real time transactions,they are also the same.