Presentations

本論文では，オンチップマルチプロセッサにおいて，周期タスクのリアルタイム性を保証しつつ，非周期タスクに対する応答時間をできる限り短縮するためのテンポラルマイグレーション手法を提案する．提案手法は，非周期タスクが到着したとき，そのプロセッサ上で優先度の高い周期タスクが実行されている場合には，リアルタイム性を保証できる範囲でそれらの周期タスクを一時的にほかのプロセッサにマイグレーションし，プロセッサ時間を非周期タスクに譲ることで応答性を向上させる．本論文では，提案手法を従来のシングルプロセッサ用Total Bandwidth Server （TBS）アルゴリズムと組み合わせたアルゴリズムを設計する．シミュレーションによる評価では，設計したアルゴリズムが，一時的なマイグレーションを行わない元来のTBS アルゴリズムに比べて，非周期タスクに対する応答性を劇的に向上できたことを示す．

This paper presents real-time scheduling techniques for reducing the response time of aperiodic tasks scheduled with real-time periodic tasks on multiprocessor systems. Two problems are addressed in this paper: (i) the scheduling of aperiodic tasks that can be dispatched to any processors when they arrive, and (ii) the scheduling of aperiodic tasks that must be executed on particular processors on which they arrive. In order to improve the responsiveness to both types of aperiodic tasks, efficient dispatching and migration algorithms are designed based on the Earliest Deadline First (EDF) algorithm and the Total Bandwidth Server (TBS) algorithm. The effectiveness of the designed algorithms is evaluated through simulation studies.

本論文では，与えられた時間制約のもとでCPU 資源を最大限に使用可能なリアルタイムLinuxの実現に向けて，Linux カーネル用リアルタイムスケジューリングモジュールを開発する．まず，高負荷状態における十分なリアルタイム性と予測可能性の提供を目的として，固定優先度の利点と動的優先度の利点を兼ね備えたスケジューリングアルゴリズムを提案する．提案アルゴリズムは理論的な性能の面で従来の固定優先度アルゴリズムと同等以上であることが保証され，Linux カーネルのスケジューラ実装に対する親和性も高いという利点がある．次に，拡張性の高いリアルタイムLinux の実現のために，カーネルの修正を最小限に抑え，新規のスケジューリングアルゴリズムをカーネルモジュールとして組み込むことを可能にするフレームワークを提案する．シミュレーションによる評価の結果，提案アルゴリズムは従来の固定優先度アルゴリズムよりも約10∼15%高いCPU 使用率でもリアルタイム性を保証できた．また，実機による評価の結果，開発したカーネルモジュールを組み込むことで，ネイティブなLinux に比べて高負荷状態における低優先度タスクのデッドラインミス率を最大で約70∼90%削減することができた．

This paper presents an EDF-based algorithm, called Earliest Deadline Deferrable Portion (EDDP), for efficient scheduling of recurrent real-time tasks on multiprocessor systems. The design of EDDP is based on the portioned scheduling technique which classifies each task into a fixed task or a migratable task. A fixed task is scheduled on the dedicated processor without migrations. A migratable task is meanwhile permitted to migrate between the particular two processors. In order to curb the cost of task migrations, EDDP makes at most M − 1 migratable tasks on M processors. The scheduling analysis derives the condition for a given task set to be schedulable. It is also proven that no tasks ever miss deadlines, if the system utilization does not exceed 65%. Beyond the theoretical analysis, the effectiveness of EDDP is evaluated through simulation studies. Simulation results show that EDDP achieves high system utilization with a small number of preemptions, compared with the traditional EDF-based algorithms.