초기호출시간이 지정된 실시간 주기적 태스크의 단일 프로세서 시스템 상에서의 비선점적 스케쥴링
길아라, 정의훈, 맹승렬 · 한국정보과학회 학술발표논문집 · 1996
단일 프로세서 시스템에서 초기호출시간이 지정된 주기적 태스크를 비선점적 스케쥴링하는 문제는 NP-hard문제로 알려져 있다. 본 논문에서는 초기호출시간이 지정된 주기적 태스크의 스케쥴링 성공율을 향상시키기 위하여 새로운 스케쥴링 전략과 새로운 스케쥴링 알고리즘을 제안하고 이들의 성능 분석을 위한 모의실험 결과를 보인다. 본 논문에서 제안하는 스케쥴링 전략은 우선, 태스크들의 주기와 초기호출시간을 이용하여 두 개의 스케쥴링 경계시간을 계산하고, 이들을 이용하여 주어진 문제를 각각 다른 시간구간 내에서 실행가능한 스케쥴을 찾는 두 개의 부-문제로 나눈다. 또한, 스케쥴링 경계시간점들의 효율적인 계산을 위한 각 태스크의 초기호출시간과 주기간의 합수를 찾는다. 본 논문에서 제안하는 스케쥴링 알고리즘은 최소 마감시간 우선 (earliest-deadline-first) 정책에 기반한 휴리스틱을 사용하여 주어진 시간구간 내에서 초기호출시간이 지정된 주기적 태스크 집합의 스케쥴링 성공율을 향상시킨다. 즉, 선택한 태스크의 스케쥴링 전에 다른 태스크들의 마감시간 초과 발생을 예상하여 스케쥴링 순서를 변경하므로써 마감시간 초과 발생을 회피한다. 결국, 제안된 알고리즘은 주어진 시간구간 내에서 최소 마감시간 우선 알고리즘으로 스케쥴링 가능한 태스크 집합에 대해서는 항상 실행가능한 시케쥴을 찾을 수 있다. 끝으로, 모의실험 결과로써 제안된 스케쥴링 전략 및 스케쥴링 알고리즘의 향상된 성능을 나타내 보인다.
Cited by 0 works.