RMに基づいたリアルタイムスケジューリングアルゴリズムの提案と可能性解析

西垣　公平  兪　明連  横山　孝典 

誌名
電子情報通信学会論文誌 D  Vol.J95-D  No.6  pp.1347-1355
発行日: 2012/06/01
Online ISSN: 1881-0225
Print ISSN: 1880-4535
論文種別: 論文
専門分野: ソフトウェアシステム
キーワード: 
マルチプロセッサ,  リアルタイムシステム,  スケジューリングアルゴリズム,  Rate Monotonic, 

本文: PDF(1.1MB)

あらまし: 
近年の組込みリアルタイムシステムではマルチプロセッサ技術の利用が一般化してきている．そのため，マルチプロセッサ環境においての最適なリアルタイムスケジューリングアルゴリズムが求められているが，まだ最適なアルゴリズムは確立されておらず，多くのアルゴリズムが研究されている．その一つに，シングルプロセッサ環境で最適なアルゴリズムであるRM (Rate Monotonic)をもとにしたスケジューリングアルゴリズムRMZL (RM until Zero Laxity)がある．本論文では，このRMZLを改良することで，オーバヘッドを減少させ，かつ高い並列性を実現するアルゴリズムLP-RMZL (Limited Preemptive-RMZL)を提案する．シミュレーション評価により，従来のRMをもとにしたアルゴリズムよりも提案アルゴリズムがコンテクストスイッチによるオーバヘッドを減少させ，高負荷な状態でも多くのタスクをスケジュール可能であることを示す．また，反応時間解析によるスケジュール可能性判定を行い，提案するアルゴリズムが高いスケジュール可能性を有していることを示す．