다중 프로세서 실시간 시스템을 위한 그래프 기반 자원 재활용 알고리즘

이재동, 고건 · 1995

대부분의 실시간 시스템 스케줄링 알고리즘들은 태스크들의 최악의 수행시간을 가정하여 태스크들을 스케줄링한다. 자원 재활용(resource reclaiming)이란 태스크의 실제 수행시간이 스케줄링 시에 가정한 최악의 수행시간보다 짧을 때 사용되지 않은 시간을 정확하고 효율적으로 사용하는 문제이다. 본 논문에서는 자원요구 조건이 있는 동적 실시간 다중 프로세서 시스템에서의 더욱 효율적이고 새로운 자원 재활용을 위한 알고리즘을 제안하였다. 기존의 알고리즘들에서는 모든 자원이 동시에 일이 없는 (free) 시간만을 이용하므로 충분한 재활용이 되지 않았다. 그러나, 제안한 알고리즘에서는 재활용될 수 있는 시간이 적을 지라도 이것이 많은 태스크들의 스케줄 시각에 반영될 수 있도록 기존의 스케줄을 수정하므로써 재활용의 활용도를 높혔다. 스케줄을 수정하기 위하여 태스크들의 자원 충돌 관계와 스케줄 상의 수행 시작 시각을 반영한 재활용 그래프(reclaiming graph)를 정의하였으며, 알고리즘의 성능 평가를 위하여 시뮬레이션을 이용하여 기존의 알고리즘과 비교 분석하였다. 분석 결과, 기존의 알고리즘에 비하여 성능이 향상되었음을 알 수 있었다.

Cited by 1 works.

Authors