0/1 제약조건을 갖는 부정확한 태스크들의 총오류를 최소화시키기 위한 개선된 온라인 알고리즘

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회논문지 : 시스템 및 이론 / 34권 / 10호 / 493 ~ 501페이지
· 저자명 : 송기현

초록

실시간시스템은 시간적으로 긴급한 태스크들을 융통성있게 스케쥴링해줄 수 있다. 총 오류를 최소화시키면서 0/1제약조건과 시간적제약조건들을 모두 만족시키는 대부분의 스케쥴링문제들은 선택적태스크들이 임의의 수행시간을 갖고 있을 때 NP-complete이다. Liu는 단일처리기상에서 0/1제약조건을 갖는 태스크들을 총 오류가 최소화되도록 스케쥴링시킬 수 있는 합리적인 전략을 제시하였다. 또한, 송 등은 다중처리기상에서 0/1제약조건을 갖는 태스크들을 총 오류가 최소화되도록 스케쥴링시킬 수 있는 합리적인 전략을 제시하였다. 그러나, 이러한 알고리즘들은 모두 오프라인 알고리즘들이다. 그런데, 온라인 스케쥴링에 있어서, NORA알고리즘은 부정확한 온라인 태스크 시스템상에서 최소의 총 오류를 갖는 스케쥴을 ?O을 수 있다. 이러한 NORA알고리즘에 있어서, EDF전략이 선택적스케쥴링에 적용되었다. 한편, 0/1제약조건을 갖는 태스크시스템에 있어서는, EDF스케쥴링이 총 오류가 최소화된다는 측면에서 최적이 아닐수도 있다. 더욱이, 선택적태스크들이 그들의 실행요구시간의 오름차순으로 스케쥴될 때, EDF전략이 적용된 NORA알고리즘이 최소의 총오류를 산출할 수 없을지도 모른다. 그러므로, 본 논문에서는, 0/1제약조건을 갖는 부정확한 태스크 시스템의 총오류를 최소화시키는 온라인 알고리즘이 제안되었다. 그리고나서, 제시된 알고리즘과 NORA 알고리즘 사이의 성능을 비교하기 위하여 여러 가지 실험들이 수행되었다. 두 알고리즘들 사이의 성능비교의 결과로서, 선택적태스크들이 그들의 실행요구시간들의 임의의 순서대로 스케쥴될 때는 제안된 알고리즘이 NORA알고리즘과 비슷한 총오류를 산출하지만 특별히 선택적태스크들이 그들의 실행요구시간들의 오름차순으로 스케쥴될 때는 제안된 알고리즘이 NORA알고리즘보다 더 적은 총오류를 산출할 수 있음이 밝혀졌다.

참고자료

· 없음