RTOSシミュレーションのための性能と移植性が高いスケジューラ

摘要

We propose a new task scheduling algorithm for timed-functional simulation of concurrent software tasks. The key features of our algorithm are its efficiency and portability: It attains efficiency by reducing the frequency of context-switching between concurrent tasks by exploiting a newly-developed 'switching-point determination' technique. It also provides a high-degree of portability in the sense that it only needs the underlying system to support a very small number of primitives. Our algorithm is presented in several different forms: First, we present it in a simple form, highlighting the efficiency feature. Then, we provide a 'portable' version for facilitating integration to existing simulation kernels. Succeedingly, we provide formal proofs of the correctness of the two versions and their equivalence. This way of algorithm certification makes a clear distinction between our approach and other similar efforts. Finally, we provide concrete implementations built on top of system-level design languages and show some results of evaluation.%システムレベル設計を対象としてソフトウェアタスクの遅延時間要求付き横能モデルのシミュレーションを行うためのスケジューリングアルゴリズムを提案する．アルゴリズムの主要な特長は高性能で移植性が高いことである．コンテクストスイッチの回数を大幅に減らすことによってシミュレーション時間を福縮する．またベースとなるシミュレーションプラットフォームが少数のプリミティブを提供していれば実装できるので移植性が高い．アルゴリズムをまず効率を示すための単純な形で示す．次に既存のシミュレーションプラットフォームに容易に統合できる移植性の高い形で示す．続いて2つの版の正当性と同値性の形式的な証明を行う．最後にシステムレベル設計言語での実現方法と評価結果を示す．