다중프로세서 시스템에서 개선된 합성 이용율을 이용한 혼합 태스크 스케줄링

Mixed Tasks Scheduling Using Improved Synthetic Utilization on Multiprocessor Systems

  • cc icon
  • ABSTRACT

    다중프로세서 시스템에서 실시간 비주기 태스크 스케줄링 방법 중 하나인 합성 이용율 방법은 주기 태스크들을 고려하지 않고 단지 비주기 태스크들을 위한 스케줄링 방식이다. 하지만 실제로 비주기 태스크는 대부분의 경우에 주기 태스크와의 혼합된 형태로 스케줄링이 이루어지며, 주기 태스크의 스케줄링을 보장하면서 비주기 태스크의 스케줄링 가능성을 판단해야 한다. 본 논문에서는 다중프로세서 시스템에서 주기태스크와 비주기 태스크가 혼합된 태스크 집합을 개선된 합성 이용율을 이용하여 스케줄링하기 위한 방법을 제시하였으며, 기존의 비주기 서버를 이용하여 혼합 태스크 집합을 스케줄링 하는 방법보다 스케줄링 성능이 향상됨을 보였다.


    Synthetic utilization on multiprocessor system is not considered periodic tasks, except scheduling methods for aperiodic tasks where one of the real-time aperiodic tasks is a scheduling method. But really aperiodic tasks scheduling method is composed of mixed task types. Aperiodic task scheduling method guarantee an analysis of the schedualibility of aperiodic task. The set of mixed tasks periodic and aperiodic tasks scheduling method uses improved synthetic utilization that is presented in this paper. The new method shows that schedulability increases aperiodic server method.

  • KEYWORD

    실시간 스케줄링 , 비주기 태스크 , 혼합 태스크 , 합성 이용율 , 다중프로세서 시스템

  • Ⅰ. 서 론

    태스크의 수행결과의 정확성뿐만 아니라 처리시한의 제한인 종료시한(deadline)을 지키는 것을 요구하는 시스템을 실시간 시스템(real-time system)이라 한다. 이러한 실시간 시스템은 종료시한이 엄격하게 지켜져야 하는 경성 실시간(hard real-time) 시스템과 그렇지 않은 연성 실시간(soft real-time) 시스템으로 구분 할 수 있다. 또한 일정 시간마다 도착하여 반복적으로 실행되는 주기(periodic) 태스크와 도착 시간이 정해져 있지 않은 비주기(aperiodic) 태스크로 구분할 수 있다. 이제까지 제안된 스케줄링 알고리즘들 중에서 Rate Monotonic (RM)[1] 스케줄링 알고리즘은 고정 우선순위 기반 알고리즘들 중 최적이고, Earliest Deadline First(EDF) [1,2] 스케줄링 알고리즘은 동적 우선순위 알고리즘들 중 최적인데 이들은 모두 주기적 태스크 모델을 기본으로 하고 있다.

    최근에 제시된 프로세서 이용율을 이용한 합성 이용 율(synthetic utilization) 알고리즘은[3-5] 비주기 태스크로만 구성된 태스크 집합들을 스케줄링 하는 방법으로 제시되었으며, [6]에서는 개선된 합성 이용율을 통해 비주기 태스크들의 스케줄링 가능성을 증가시키는 방법이 연구되었다.

    주기와 비주기 태스크가 혼합되어 스케줄링되는 경우에는 주기 태스크의 스케줄링 가능성을 우선 보장하면서 비주기 서버를 이용하여 비주기 태스크들을 스케줄링한다. 비주기 태스크의 수행은 비주기 서버의 대역폭에 의해 제한되기 때문에 주기 태스크의 스케줄링에 영향을 주지 않으면서 비주기 태스크들을 스케줄링할 수 있다. 이러한 방법을 사용하는 알고리즘으로 다중프로세서 시스템에서 대역폭 서버(total bandwidth server, TBS)[7]를 이용하는 알고리즘이 있다. 또한 이기종의 다중프로세서 환경에서의 실시간 스케줄링 방법도 연구되었다[9]. 본 논문에서는 경성 실시간 시스템에서 EDF 스케줄링에 의해 비주기 태스크들만을 스케줄링 하는 합성 이용율 방법을 확장하여 주기와 비주기 태스크가 혼합된 경우의 태스크 스케줄링 방법을 제시하고, 다중프로세서 시스템에서TBS 알고리즘과 비교 분석하였다.

    본 논문은 2장에서 다중프로세서 시스템에서 비주기 태스크만을 대상으로 하는 합성 이용율을 기술한 후 이것을 확장하여 주기태스크와 비주기 태스크가 혼합된 태스크 집합들을 스케줄링 하는 방법을 제시한다. 3장에서는 모의실험 결과를 보이고, 마지막으로 4장에서는 결론 및 향후 연구 과제에 대하여 기술한다.

    Ⅱ. 다중프로세서 시스템에서의 혼합 태스크 스케줄링

    다중프로세서 시스템에서 기존의 합성 이용율 방법은 비주기 태스크들만을 고려하였기 때문에 주기태스크와 혼합된 태스크 집합에 적용하기 어려웠다. 합성 이용율을 이용하여 주기 태스크를 스케줄링하기 위해서는 주기 태스크를 고려한 구간에서 합성 이용율을 적용할 수 있어야 하고 주기 태스크를 비주기 태스크로 변환해야 한다.

    기존의 합성 이용율은 임의시간 t의 시점에서 프로세서의 이용율을 구하는 방법으로 t + 1과 같은 t 이후에 도착되는 태스크들에 대한 고려를 하지 않는다. 이러한 문제를 해결하기 위해 특정구간 [t,t']에서의 합성 이용율을 제시하고 이것을 확장하여 주기 태스크에 적용하였다.

    주기 태스크의 특성상, 앞으로 발생하는 인스턴스들의 도착을 미리 예측하여 이것을 이용율 계산에 적용할 수 있다면 주기 태스크들에 대해서도 합성 이용율을 이용한 스케줄링 기법을 제시할 수 있다.

    비주기 태스크 집합 Ta를 {T1, T2, T3Ti…}라 할 때, T1T2보다 먼저 도착(arrival)된 태스크라 가정 한다. 즉 TiTi+1보다 먼저 도착한 비주기 태스크 이다. 비주기 태스크 Ti의 수행시간(execution time)을 Ci(>0), 도착시간(arrival time)을 Ai, 상대적 종료시간(relative deadline)을 Di(>0) (여기서 절대적 종료시간(absolute deadline) diAi+Di로서 정의된다.), m을 프로세서의 개수라 할 때 다중프로세서 시스템에서 임의의 시점 t에서의 비주기 태스크를 위한 합성 이용율[8] 은 다음과 같이 정의한다.

    image

    식(1)을 주기 태스크에 적용하기 위해서는 임의의 구간에서 합성 이용율을 계산할 수 있어야 한다. 그 이유는 주기 태스크는 매주기마다 인스턴스들이 도착되어 실행되기 때문에 각 주기의 구간 마다 스케줄링 가능성을 보장해주기 위해서이다. 먼저 특정 구간에서 비주기 태스크의 합성 이용율을 구하기 위해 m=1이라 가정하고, 현재 요청집합 S(t)를 S(t,t')로 확장한다. S(t,t') = Ti|Ait' ,Di>t로 정의할 수 있으며 여기서 tt'이다.

    그림 1은 특정구간에서의 현재 요청 집합에 대한 예제이다.

    여기서 S(t) = {T1, T2, T3}이지만 S(t,t')은 S(t,t') = {T1, T2, T3, T4}이다. 이러한 방법으로 특정 구간의 현재 요청 집합을 구하여 합성 이용율을 계산할 수 있다. 또한 S(t, ∞)를 생각한다면, 시점 t 에서 그 이후의 모든 태스크들에 대해서 합성 이용율을 정의할 수있다. 주기 태스크를 비주기 태스크로 변환하면 합성 이용율을 적용할 수 있는데 주기 태스크 집합 Tp = {T1, T2, ⋯, Tn}에서 주기 태스크의 모든 인스턴스들을 비주기 태스크로 생각할 수 있다.

    즉 주기 태스크의 임의의 인스턴스 Ti,j는 도착시각이 Ak = Ai + (j–1) Ti 이고, 종료시한이 dk = Ti 인 비주기 태스크 Tk 로 생각할 수 있다. 이 두 가지 방법을 이용하고, 비주기 태스크 집합 Ta가 EDF에 의해 스케줄링 될 때 합성 이용율 을 이용하여 다중프로세서 시스템에서 주기 태스크와 비주기 태스크가 혼합된 태스크 집합에 대해 합성 이용율을 적용할 수 있다. 프로세서의 개수 m = 1이고, 비주기 태스크 집합을 Ta, 주기 태스크 집합을 Tp (단, T = D), 그리고 변환된 주기 태스크 집합을 Tp'이라할 때 TaTp'의 합집합을 Ts라 하자. 비주기 태스크가 도착할 때 마다 모든 TiTs에 대해 EDF에 의한 방식을 사용하므로 합성 이용율 UTs(t,t')≤1가 만족되면 비주기 태스크 Ti는 스케줄링 가능하다. 하지만 이 방법은 모든 주기 태스크의 인스턴스에 대해 구간별로 모두 검사 해야 하므로 실제로는 불가능하다. 또한 구간 [t, t']에서 현재 시간을 t라 할 때 현재 시간 t부터 t'까지 태스크 정보를 변환된 주기 태스크는 알 수 있지만 비주기 태스크는 전혀 알 수 없기 때문에 구간을 이용한 방법은 실제 불가능하다.

    하지만 주기 태스크와 비주기 태스와의 관계를 이용하면 이러한 문제를 해결할 수 있다. 주기 태스크 집합 Tp EDF에 의해 스케줄링 될 때 프로세서 이용율은 이다. 또한 변환된 주기 태스크 Tp'의 합성 이용율은 로 표현된다. 이때 UTp'(t,t')≤UTp의 관계를 가진다. 즉, EDF 알고리즘에 의해 스케줄되는 원래의 주기 태스크의 프로세서 이용율은 비주기 태스크로서 변환되어 합성 이용율을 적용한 프로세서 이용율 보다 항상 크거나 같다.

    다음 표 1UTp'(t,t')≤UTp의 예이다. T1, T4는 비주기 태스크로 (Ai, Ci, Di)가 각각 (1,3,11), (4,2,10) 이고 T2, T3은 주기 태스크로 (Ai, Ci, Pi)가 각각 (3,2,7), (5,1,9) 이다. 여기서 Pi 태스크 Ti의 주기다. 먼저 를 구하면 변환된 주기 태스크 T2, T3에 대해 현재 요청집합은 S(2,4) = {T2}이므로 이다.

    또한 이므로 이다. 그러므로 UTp' < UTp이다. 만일 주기 태스크 T3이 존재하지 않는다면 이다. 그러므로 UTp' = UTp이다. 또는 현재 요청 집합 구간이 S(2,6)으로 변경되더라도 UTp' = UTp이다. 즉, UTp' 는 최대 UTp값을 가질 수 있다. UTS가 EDF로 스케줄링 될 때 UTS = UTa + UTp'로 표현할 수 있고 UTp'는 최대 UTp를 가질 수 있으므로 UTS = UTa+UTp≤1이고 UTa≦1–UTp의 값을 가진다. 즉, 합성 이용율을 이용한 비주기 태스크가 1–UTp의 범위에서 프로세서 이용 율을 가진다면 스케줄링 가능하다. 정리하면 주기 태스크와 비주기 태스크의 혼합 집합 TS=Ta+Tp는 모든 비주기 태스크 TiQ에 대해 UTS≤1을 만족하면 스케줄링 가능하다.

    그림 2에서처럼 EDF에 의한 주기 태스크의 이용율이 0.39이고, 임의의 시점 t에서 비주기 태스크의 이용율이 1-0.39를 넘지 않으면 주기 태스크 스케줄링을 보장하면서 비주기 태스크들도 스케줄링 가능하다. 이 방법은 앞에서 제시한 구간을 이용하는 방법처럼 모든 구간을 점검하지 않고 주기 태스크의 이용율을 이용해서 비주기 태스크와 주기 태스크가 혼합된 태스크 집합에 적용할 수 있다. 또한 합성 이용율을 [6]에서 제시한 개선된 합성 이용율 방법을 사용하면 비주기 태스크들의 스케줄링 가능성이 증가하게 된다.

    Ⅲ. 모의 실험

       3.1. 모의실험 방법

    본 장에서는 주기 태스크와 비주기 태스크가 혼합된 태스크 집합을 다중프로세서 시스템의 TBS 알고리즘과 본 논문에서 제시한 방법을 이용하여 스케줄링 가능성 여부를 비교한다. 모의실험은 인텔 CPU CORE i5, 윈도우즈7 환경에서 실험 하였으며, 주기 태스크는 EDF 방법을 이용하여 주기 태스크의 이용율이 낮은 0.3과, 이용율이 높은 0.7인 경우로 나누어 실험하였다. 또한 비주기 태스크는 1000개를 랜덤하게 생성하여 주기 태스크와 함께 스케줄링 하였다.

    입력 워크로드는 비주기 태스크로서 모든 도착된 태스크들의 수행시간의 합과 태스크들이 도착한 시간구간의 비율로 표현할 수 있는데 실험 범위는 50%∼150%까지 10%씩 증가되는 시점에서 태스크들의 스케줄링 가능성을 측정하였다.

       3.2. 실험 결과

    그림 3, 그림 4는 m=2일 때 주기 태스크의 이용율이 0.3, 07인 경우 워크로드에 따른 비주기 태스크들의 스케줄링 가능성 여부를 보여주고 있다. 주기 태스크의 이용율이 높은 경우에, 그리고 워크로드가 큰 경우에는 다중프로세서 시스템에서 TBS와 본 논문에서 제시한 방법의 스케줄링 가능성이 큰 차이를 보이지 않지만 주기 태스크의 이용율이 낮은 경우에는 워크로드가 커지더라도 본 논문에서 제시한 방법이 다중프로세서 시스템에서 TBS에 의한 알고리즘에 비해 약 20%정도 스케 줄링 가능성이 향상된 것으로 나타난다. 그 이유는 다중프로세서 시스템에서 TBS 알고리즘의 경우 수행시간이 길고 우선순위가 낮은(종료시한이 긴) 태스크가 먼저 실행되고 수행시간이 짧고 우선순위가 높은(종료 시한이 짧은) 태스크가 나중에 도착하여 실행되면 높은 우선순위의 태스크들이 거절당하는 경우가 발생하기 때문이다.

    그림 5, 그림 6, 그림 7은 프로세서의 개수별로 다중 프로세서 시스템에서 합성이용율과 TBS 알고리즘의 워크로드별 변화로 워크로드별로 비교해 볼 때 합성이용율의 방법이 TBS 알고리즘 방법보다 더 많은 태스크 집합들을 스케줄링 가능하다는 것을 알 수 있다.

    Ⅳ. 결 론

    다중 프로세서 시스템에서 비주기 태스크들을 스케줄링하는 경우 대부분의 알고리즘이 주기 태스크를 먼저 스케줄링 한 후 나머지 대역폭을 비주기 태스크에 할당하여 스케줄링하는 방법을 사용한다. 본 논문에서는 EDF 스케줄링 방식을 이용하여 비주기 태스크만을 스케줄링하는 합성 이용율 방법을 주기 태스크에 적용할 수 있도록 변경하였고, 이를 이용하여 주기 태스크와 비주기 태스크가 혼합된 태스크 집합들을 스케줄링 하는 방법을 제시하였다. 합성 이용율은 프로세서 이용율을 이용하기 때문에 스케줄링 가능성 여부를 빠르게 판단할 수 있다. 본 논문에서 제시한 다중 프로세서 시스템에서 주기 태스크와 비주기 태스크의 혼합 집합에 대한 스케줄링 가능성 여부는 주기 태스크의 이용율에 따라서 차이를 보이게 되는데 주기 태스크의 이용율이 높아지면 비주기 태스크가 사용할 수 있는 대역폭이 줄어들기 때문에 상대적으로 스케줄링 가능성이 줄어들게 된다. 주기 태스크의 이용율이 낮은 경우 다중프로세서 시스템에서 TBS 알고리즘과 본 논문에서 제시한 방법을 비교하면 약 20%정도 성능 차이를 보이며, 또한 워크로드에 따라 스케줄링 가능성이 다중프로세서 시스템에서 TBS 알고리즘보다 개선된 것을 볼 수 있었다. 본 논문에서는 다중 프로세서 환경에서 주기 태스크와 비주기 태스크의 혼합된 태스크 집합에서의 이용율 측정을 통한 스케줄링 가능성 여부를 판단하였지만 단일 코어, 다중 코어 시스템 환경에서 혼합 태스크 집합의 스케줄링 가능성 판단을 위한 연구가 필요하다.

  • 1. Liu C. L., Layland J. W. 1973 "Scheduling algorithms for multiprogramming in hard real time environment" [Journal of the ACM] Vol.20 P.46-61 google doi
  • 2. Chetto H., Chetto M. 1989 "Some results of the earliest deadline first scheduling algorithm" [IEEE Transactions on Software Engineering] Vol.15 P.1261-1268 google doi
  • 3. Abdelzaher T. F., Lu C. 2001 "Schedulability analysis and utilization bounds for highly scalable real-time services" [in Proceedings of IEEE Real-Time Technology and Applications Symposium] google
  • 4. Abdelzaher T. F., Sharma V., Lu C. 2004 "A Utilization bound for aperiodic tasks and priority driven scheduling" [IEEE Transactions on Computers] Vol.53 P.334-350 google doi
  • 5. Abdelzaher T. F., Sharma V. July. 2003 "A synthetic utilization bound for aperiodic tasks with resource requirements." [in 15th Euromicro Conference on Real-Time Systems] google
  • 6. Moon Seok-Hwan, Kim In-Guk 2008 “A Study on Improved Synthetic Utilization for Real-Time Aperiodic Tasks Scheduling" [Journal of digital contents society] Vol.9 P.441-448 google
  • 7. Kato Shinpei, Yamasaki Nobuyuki Dec 2008 "Scheduling Periodic Tasks using Total Bandwidth Server on Multiprocessors" [IEEE/IFIP International Conference] P.82-89 google
  • 8. Abdelzaher T. F., Anderson B., Jonsson J., Sharma V., Nguyen M. September 2002 "The aperiodic multiprocessor utilization bound for liquid tasks." [in Real-time and Embedded Technology and Applications Symposium] google
  • 9. Bertogna Marko, Buttazzo Giorgio 2015 "Real-time Scheduling upon Heterogeneous Multiprocessors." Multiprocessor Scheduling for Real-Time Systems. P.205-211 google
  • [] 
  • [그림 1.] [t,t']에서의 합성 이용율
    [t,t']에서의 합성 이용율
  • [표 1.] 혼합 태스크 집합
    혼합 태스크 집합
  • [그림 2.] 구간 [2,4]에서 주기 태스크의 합성 이용율
    구간 [2,4]에서 주기 태스크의 합성 이용율
  • [그림 3.] Tp = 0.3 인 경우 혼합 태스크 스케줄링
    Tp = 0.3 인 경우 혼합 태스크 스케줄링
  • [그림 4.] Tp = 0.7 인 경우 혼합 태스크 스케줄링
    Tp = 0.7 인 경우 혼합 태스크 스케줄링
  • [그림 5.] m = 2인 경우 프로세서 이용율
    m = 2인 경우 프로세서 이용율
  • [그림 6.] m = 16인 경우 프로세서 이용율
    m = 16인 경우 프로세서 이용율
  • [그림 7.] m = 32인 경우 프로세서 이용율
    m = 32인 경우 프로세서 이용율