| 講演名 | 2007/3/9 マルチプロセッサにおけるスケジュール可能性を向上するための動的優先度スケジューリングアルゴリズム(スケジューリング,組込技術とネットワークに関するワークショップETNET2007) 加藤 真平, 山崎 信行, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 近年,組込み実時間システムにおいてもマルチプロセッサの利用が主流になりつつある.しかしながら,マルチプロセッサにおける実時間スケジューリングは複雑であることが知られている.一般的に,高いスケジュール可能性を実現できる洗練されたスケジューリングアルゴリズムでは多くのコンテキストスイッチやタスクマイグレーションが発生し,それらのオーバーヘッドによる実用性の低下が問題となる.一方で,単純なアルゴリズムでは高いスケジュール可能性を実現することはできない.そこで,本論文では,高いスケジュール可能性を実現できる実用的な動的優先度スケジューリングアルゴリズムを提案する.提案アルゴリズムは新しいスケジューリング方式に基づいており,従来のスケジューリング方式に基づくあらゆるアルゴリズムのスケジュール可能なシステム利用率の上限が高々50%であるのに対して,その上限を73% に向上できる.評価では,実際のスケジュールにおいても,提案アルゴリズムが既存のアルゴリズムよりも多くのタスクをスケジュール可能であることを示す. |
| 抄録(英) | Recent embedded real-time systems tend to be realized by a multiprocessor system. However it is known to be complicated to realize real-time scheduling on multiprocessors. In general, scheduling algorithms with high schedulability generate a number of context switches and task migrations that incur a significant overhead. Because of the overhead, those algorithms are often considered not to be practical. Meanwhile simple algorithms cannot improve the schedulability. This paper proposes a practical dynamic-priority scheduling algorithm with high schedulability. Our algorithm is based on a new scheduling scheme and achieves 73% of the least upper bound of the schedulable utilization, whereas any algorithm based on the existing scheduling scheme achieves at most 50%. The evaluation shows that our algorithm also outperforms the existing algorithms in the real schedule point of view. |
| キーワード(和) | 実時間システム / 動的優先度スケジューリング / スケジュール可能性解析 / マルチプロセッサ |
| キーワード(英) | Real-Time Systems / Dynamic-Priority Scheduling / Schedulability Analysis / Multiprocessor Systems |
| 資料番号 | CPSY2006-92,,DC2006-106 |
| 発行日 |
| 研究会情報 | |
| 研究会 | DC |
|---|---|
| 開催期間 | 2007/3/9(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Dependable Computing (DC) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | マルチプロセッサにおけるスケジュール可能性を向上するための動的優先度スケジューリングアルゴリズム(スケジューリング,組込技術とネットワークに関するワークショップETNET2007) |
| サブタイトル（和） | |
| タイトル（英） | A Dynamic-Priority Scheduling Algorithm for Improving the Schedulability on Multiprocessors |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 実時間システム / Real-Time Systems |
| キーワード(2)（和/英） | 動的優先度スケジューリング / Dynamic-Priority Scheduling |
| キーワード(3)（和/英） | スケジュール可能性解析 / Schedulability Analysis |
| キーワード(4)（和/英） | マルチプロセッサ / Multiprocessor Systems |
| 第 1 著者 氏名（和/英） | 加藤 真平 / Shinpei KATO |
| 第 1 著者 所属（和/英） | 慶應義塾大学 Keio University |
| 第 2 著者 氏名（和/英） | 山崎 信行 / Nobuyuki YAMASAKI |
| 第 2 著者 所属（和/英） | 慶應義塾大学 Keio University |
| 発表年月日 | 2007/3/9 |
| 資料番号 | CPSY2006-92,,DC2006-106 |
| 巻番号（vol） | vol.106 |
| 号番号（no） | 604 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |