相対的タイミング制約と資源制約をもつ並列実時間システムのためのスケジューリング手法
スポンサーリンク
概要
- 論文の詳細を見る
本論文では, タスク間の相対的なタイミング制約と資源制約を扱える静的なスケジューリングアルゴリズムを提案する. 提案するアルゴリズムは, 二つの変数と一つの定数に関する任意の不等式によって記述されたタイミング制約を処理できる. このため, end-to-endのタイミング制約やタスク間の相対的なタイミング制約が課せられたさまざまなスケジューリング問題を解くことができる. あるNP完全なスケジューリング問題が本論文で対象とするスケジューリング問題に帰着する. 従って, この問題に対して効率的なアルゴリズムを得ることは一般に難しい. そのため, 一部の問題に対して多大な計算時間を必要とするが, 多くの問題に対して効率的に解を求めるヒューリスティックアルゴリズムを得ることを目標とした. その結果, 15個のタスクをスケジューリングする問題に対して, 3分間の計算時間で約80%の成功率を達成した.
- 1996-08-25
著者
関連論文
- 3T-1 斜面防災システムにおける耐障害性を考慮したP2Pレプリケーション手法(センサデータベースとコンテンツ,学生セッション,データベースとメディア)
- 移動端末を用いた災害情報システムにおけるDTNルーティング手法(モバイルP2P,ユビキタスネットワーク,アドホックネットワーク,センサネットワーク,一般)
- 無線センサネットワークの時刻同期と位置同定の統合化手法(ネットワーク)
- MANET環境におけるDHTを用いたデータベースの問合せ処理 (アドホックネットワーク)
- センサネットワークにおけるパーティクルフィルタを利用した物体追跡(モバイルP2P,ユビキタスネットワーク,アドホックネットワーク,センサネットワーク,一般)
- 2F-5 マイクロカーネルLavenderにおけるセキュリティ機構の導入
- 分散並列処理のためのプラットフォームLemuriaのWindows上での構成と性能評価
- 分散並列処理のためのプラットフォームLemuriaの評価
- 分散共有メモリサーバにおけるページ配送の効率化
- 分散並列処理のためのプラットフォーム Lemuria の構成
- 分散並列処理のためのプラットフォームLemuriaの構成
- マイクロカーネルLavenderにおける階層化インタフェース
- 分散共有メモリサーバの大規模データ処理への適用と評価
- マイクロカーネル上の分散共有メモリサーバの構成
- Machの外部ページャによる分散共有メモリサーバの評価
- Machの外部ページャによる分散共有メモリサーバとその応用
- 動的な構成変化に対応するセンサネットワークを用いたデバイス制御フレームワーク(モバイルP2P,ユビキタスネットワーク,アドホックネットワーク,センサネットワーク,一般)
- 2Z-5 センサネットワークにおける通信モジュール再利用のためのクロスレイヤ処理機構(センサネットワーク,学生セッション,ネットワーク)
- 1Q-8 アプリケーションの構造を視覚化するnesC用開発環境の提案(プログラミング言語・実装・支援,学生セッション,ソフトウェア科学・工学)
- 無線アドホック通信を利用したセンサネットワーク向け協調ストレージシステム(MBL-4【センサネットワーク】)
- センサノードの測位精度の向上を目的とするビーコンノードの選択アルゴリズム(MBL-1【位置情報の測位と利用】)
- センサノード向けOSにおける消費電力の低減のための協調型タスクスケジューリング(低消費電力)
- ファイルの特徴に基づくディスクキャッシュのヒット率の見積もりを用いた置換アルゴリズム(ストレージ)
- Privacy-Aware Data Object Containerによる細粒度データアクセス制御方式(セキュリティとプライバシー)
- ファイルの特徴に基づくディスクキャッシュのヒット率の見積もりを用いた置換アルゴリズム
- Privacy-Aware Data Object Container による細粒度データアクセス制御方式
- Privacy-Aware OS Salviaにおけるデータアクセス時のコンテキストに基づく適応的データ保護方式(オペレーティングシステム)
- 異種ネットワーク環境における適応的通信デバイス制御(UBI7:ネットワーク・デバイス制御)
- センサネットワークにおけるゲートウェイサービスの構成(UBI6:プラットフォーム・アーキテクチャ)
- オペレーティングシステムSalviaにおけるデータアクセス制御の記述モデル
- プライバシ保護を実現するオペレーティングシステムのファイルアクセス制御手法(ファイルシステム)
- プライバシ保護を実現するオペレーティングシステムにおけるコンテキスト管理手法(セキュリティ)
- データの拡散防止を実現するコンテキスト適応型ソフトウェア基盤(インターネットとセキュリティ)
- 分散トランザクションシステム IXI の設計と実現
- 異種ネットワーク環境における適応的通信デバイス制御(UBI7:ネットワーク・デバイス制御)
- センサネットワークにおけるゲートウェイサービスの構成(UBI6:プラットフォーム・アーキテクチャ)
- オペレーティングシステムSalviaにおけるデータアクセス制御の記述モデル
- オペレーティングシステムSalviaにおけるデータアクセス制御の記述モデル
- ユビキタス環境におけるトランザクション処理方式(実行環境)
- ネットワークデバイス切替え時における通信の継続手法(ネットワーク)
- ユビキタス環境におけるトランザクション処理方式
- ネットワークデバイス切替え時における通信の継続手法
- 分散オペレーティングシステムSolelcにおけるメモリ操作のトランザクション化による耐障害性向上手法(OS構成法)
- オブジェクト指向オペレーティングシステム Ozone におけるプロセス管理方式
- プログラム開発支援システムC++baseの構成
- 分散トランザクションシステムIXIにおける耐障害性機構
- 連続メディアのためのディスクスケジューリング機能を持つファイルシステムの実現
- ネットワーク利用率に基づいた予約方式による通信サーバの設計
- 分散トランザクションシステムIXIの設計と実現
- リライアブルなマイクロカーネルの実現について
- 分散オペレーティングシステムDM-2におけるメモリ管理部の実現
- 分散オペレーティングシステムDM-2におけるサイトの動的な追加及び切り離し方式
- 分散オペレーティングシステムDM-2におけるスレッドディストリビュータの実現
- 分散仮想記憶に基づくオペレーティングシステムDM-1におけるタスク・スレッドモデル
- 分散仮想記憶に基づくオペレーティングシステムDM-1の構成
- 分散オペレーティングシステムSolelcにおけるファイル管理機構の構成と性能評価(分散ファイルシステム)
- 次世代ワイヤレス通信を指向するオペレーティングシステムの提案
- リアルタイム環境に適用可能なUltra DMA転送機構の設計と実装
- 分散オペレーティングシステムSolelcにおけるシステムコール処理の分散化方式
- エージェント指向オペレーティングシステムAGにおけるリフレクティブエージェントの実現手法
- リアルタイム環境に適用可能なUltra DMA転送機構の設計と実装
- 分散オペレーティングシステム Solelc におけるシステムコール処理の分散化方式
- エージェント指向オペレーティングシステムAGにおけるリフレクティブエージェントの実現手法
- モジュールの共有に基づくプロセス間協調処理の効率化手法(特集:システムソフトウエアの新しい潮流)
- マイクロカーネルLavender上へのUNIXサーバの構築
- 2F-4 マイクロカーネルLavenderにおけるUNIXサーバの構成
- 2F-3 マイクロカーネルLavenderにおけるIPC機構とデバイスドライバの構成
- 2F-2 マイクロカーネルLavenderにおけるネームサーバの構築
- 2F-1 マイクロカーネルLavenderにおけるシステムサーバの処理方式
- 1F-6 リアルタイムOS R^2上への2レベルスケジューラの構築
- マイクロカーネルLavender上へのネットワークシステムサーバの構築
- マイクロカーネルLavender上のファイルシステムサーバの構築と応用
- マイクロカーネルLavenderにおけるプロセス管理方式
- マイクロカーネルLavenderにおける多段階スケジューリング機構
- マイクロカーネルLavenderにおけるIPC機構とデバイスドライバの構成
- マイクロカーネルLavenderにおけるスケジューラの構成
- マイクロカーネルLavenderの構成
- マイクロカーネルLavenderの構成
- マイクロカーネルLavenderにおけるメモリ管理部の構成
- マイクロカーネルLavenderにおけるプロセス管理部の構成
- ワークステーションの実時間処理への適用
- 無線センサネットワークの時刻同期における中継スケジューリング手法(ネットワーク)
- 大規模センサネットワークの持続的時刻同期手法(RFID・センサネットワーク,ホームネットワーク,オーバーレイネットワーク,RFID及び一般)
- 異種センサネットワーク混在環境下におけるマルチユーザを考慮した問い合わせの最適化手法(モバイル P2P,ユビキタスネットワーク,アドホックネットワーク,センサネットワーク,一般)
- 2ZB-7 センサネットワークにおけるイベント伝播のためのプロアクティブ型経路構築手法(ユビキタスネットワーク,学生セッション,ネットワーク,情報処理学会創立50周年記念)
- 3Z-3 センサデータの分散管理システムにおけるプロアクティブ転送・検索機構(アドホックネットワーク(1),学生セッション,ネットワーク,情報処理学会創立50周年記念)
- リアルタイムオペレーティングシステムEaselにおけるリアルタイムウィンドウシステム
- リアルタイムオペレーティングシステムEaselにおけるリアルタイムウィンドウシステム
- WMSNsにおける消費電力とQoSを考慮したハイブリッド型MACプロトコル(モバイル P2P,ユビキタスネットワーク,アドホックネットワーク,センサネットワーク,一般)
- 5ZA-1 移動端末とDTNルーティング手法を用いた災害情報システム(防災と情報,学生セッション,コンピュータと人間社会)
- 1L-9 MANETにおける物理ネットワークを考慮したオーバレイネットワーク構築手法(組込みとネットワーク,学生セッション,アーキテクチャ)
- 1L-7 センサ・アクチュエータノードにおけるプロセスの目的を考慮した資源割当て手法(組込みとネットワーク,学生セッション,アーキテクチャ)
- 5U-7 移動センシングのためのデータマイグレーション機構(センサネットワーク運用・制御,学生セッション,ネットワーク)
- 5U-6 センサノードの実行履歴を用いた負荷予測に基づくDVSとDMSによる協調型省電力手法(センサネットワーク運用・制御,学生セッション,ネットワーク)
- 5U-5 センサネットワークの長期運用を考慮した経路決定法(センサネットワーク運用・制御,学生セッション,ネットワーク)
- 1U-4 センサネットワークにおけるメタデータを用いた統一的問い合わせ手法(センサネットワークシステム,学生セッション,ネットワーク)
- 1U-3 センサノードの自律的な協調処理のためのイベントを用いた問合せ処理(センサネットワークシステム,学生セッション,ネットワーク)
- 1U-2 センサネットワークにおけるECA ルールを用いたデバイス制御手法(センサネットワークシステム,学生セッション,ネットワーク)
- 無線センサネットワークにおける時刻および位置の同時同定手法(センサネットワーク)
- ルールベースの問合せ処理機構による協調型センサネットワークの実現(センサネットワーク)