Task Scheduling in Real-time System using Genetic Algorithm

カテゴリ: 部門大会

論文No: OS7-3

グループ名: 【C】平成16年電気学会電子・情報・システム部門大会講演論文集

発行日: 2004/09/02

タイトル(英語): Task Scheduling in Real-time System using Genetic Algorithm

著者名: 兪明連 (早稲田大学),玄 光男(早稲田大学)

著者名(英語): Myungryun Yoo(Waseda　University),Mituo Gen(Waseda　University)

キーワード: Real time system|Genetic algorithm

要約(日本語): Real-time systems are characterized by computational activities with timing constraints of submitted tasks. Real-time systems can be classified into two categories: Hard real-time system and Soft real-time system. In hard real-time system, the violation of timing constraints (deadline missing) of certain task could be catastrophic. The goal of scheduling algorithms for hard real time system is to meet all tasks’ deadlines and to keep the feasibility of scheduling through admission control. However, slight violence of deadlines is not so critical in soft real-time situation. In this paper, we present a new scheduling problem for soft real-time system based on genetic algorithm. Especially, we focused on scheduling for continuous media tasks that are periodic and preemptive. Objective of proposed scheduling algorithm is to minimize the variation of deadline missing frequency among tasks. Some drawbacks (i.e. low resource utilization and avoidable context switching overhead) of RM/EDF derived algorithms for soft real time systems could be fixed in proposed algorithm. We takes not only advantages of traditional approaches but plus side of GA, such as, high speed, parallel searching and high adaptability, The effectiveness of the proposed algorithm is shown through simulation studies.

PDFファイルサイズ: 6,994 Kバイト