著者

小林 秀典 山﨑 信行

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌コンピューティングシステム(ACS) (ISSN:18827829)

巻号頁・発行日

vol.46, no.16, pp.69-84, 2005-12-15

参考文献数

27

---

インプリサイス計算モデルに基づくインプリサイスタスクは,その実行に十分な時間が割り当てられない場合でも,デッドラインまでに品質の低い結果を生成することができる.しかし,インプリサイスタスクの実行は任意の時点で中断される可能性があるため,共有資源へアクセスすることができないという欠点がある.本論文では,資源の最大占有時間が既知である環境において,インプリサイスタスクが共有資源へアクセス可能なスケジューリングアルゴリズムを提案する.本アルゴリズムは,システムに存在するスラックのプロセッサバンド幅をオフラインで算出し,スケジュール可能性を判断する.オンラインでは,付加部分に割当て可能な時間を動的に算出することで,実際に要求された資源アクセスが完了できることを確認する.提案したアルゴリズムを実時間オペレーティングシステムRT-Frontier に実装し,実用性を評価する.また,資源制約を持つインプリサイスタスクを用いた検証実験を行うことで,実時間性を満たした資源アクセスが可能であることを示す.The imprecise tasks, based on the imprecise computation model, can produce lower quality of result even when there is not enough time. However, the imprecise tasks cannot share resources, because they allow termination at any point in their optional parts. This paper proposes a scheduling algorithm that enables the imprecise tasks to share resources in systems where the maximum access duration of every resource is known. The offline part of this algorithm calculates the processor bandwidth of slack and checks the schedulability of the given task set. The online part schedules tasks in deadline order and calculates the remaining time for optional parts in order to verify whether requested accesses can be completed. We implement this algorithm on the RT-Frontier operating system to assess its practicability. Moreover, we conduct experiments using imprecise tasks with resource constraints to confirm that resources can be accessed without causing any timing violation.