Advanced
Mixed Tasks Scheduling Using Improved Synthetic Utilization on Multiprocessor Systems
Mixed Tasks Scheduling Using Improved Synthetic Utilization on Multiprocessor Systems
Journal of the Korea Institute of Information and Communication Engineering. 2015. Feb, 19(2): 351-356
Copyright © 2015, The Korean Institute of Information and Commucation Engineering
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License(http://creativecommons.org/li-censes/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : October 23, 2014
  • Accepted : December 11, 2014
  • Published : February 28, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
석환 문
shmoon@yd.ac.kr

Abstract
다중프로세서 시스템에서 실시간 비주기 태스크 스케줄링 방법 중 하나인 합성 이용율 방법은 주기 태스크들을 고려하지 않고 단지 비주기 태스크들을 위한 스케줄링 방식이다. 하지만 실제로 비주기 태스크는 대부분의 경우에 주기 태스크와의 혼합된 형태로 스케줄링이 이루어지며, 주기 태스크의 스케줄링을 보장하면서 비주기 태스크의 스케줄링 가능성을 판단해야 한다. 본 논문에서는 다중프로세서 시스템에서 주기태스크와 비주기 태스크가 혼합된 태스크 집합을 개선된 합성 이용율을 이용하여 스케줄링하기 위한 방법을 제시하였으며, 기존의 비주기 서버를 이용하여 혼합 태스크 집합을 스케줄링 하는 방법보다 스케줄링 성능이 향상됨을 보였다.
Keywords
Ⅰ. 서 론
태스크의 수행결과의 정확성뿐만 아니라 처리시한의 제한인 종료시한(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 를 { T 1 , T 2 , T 3 Ti …}라 할 때, T 1 T 2 보다 먼저 도착(arrival)된 태스크라 가정 한다. 즉 Ti T i+1 보다 먼저 도착한 비주기 태스크 이다. 비주기 태스크 Ti 의 수행시간(execution time)을 Ci (>0), 도착시간(arrival time)을 Ai , 상대적 종료시간(relative deadline)을 Di (>0) (여기서 절대적 종료시간(absolute deadline) di Ai + Di 로서 정의된다.), m을 프로세서의 개수라 할 때 다중프로세서 시스템에서 임의의 시점 t에서의 비주기 태스크를 위한 합성 이용율 [8] 은 다음과 같이 정의한다.
PPT Slide
Lager Image
식(1)을 주기 태스크에 적용하기 위해서는 임의의 구간에서 합성 이용율을 계산할 수 있어야 한다. 그 이유는 주기 태스크는 매주기마다 인스턴스들이 도착되어 실행되기 때문에 각 주기의 구간 마다 스케줄링 가능성을 보장해주기 위해서이다. 먼저 특정 구간에서 비주기 태스크의 합성 이용율을 구하기 위해 m=1이라 가정하고, 현재 요청집합 S ( t )를 S ( t , t' )로 확장한다. S ( t , t' ) = Ti | Ai t' , Di > t 로 정의할 수 있으며 여기서 t t' 이다.
그림 1 은 특정구간에서의 현재 요청 집합에 대한 예제이다.
PPT Slide
Lager Image
[t,t']에서의 합성 이용율 Fig. 1 Synthetic Utilization at [t,t']
여기서 S ( t ) = { T 1 , T 2 , T 3 }이지만 S ( t , t' )은 S ( t , t' ) = { T 1 , T 2 , T 3 , T 4 }이다. 이러한 방법으로 특정 구간의 현재 요청 집합을 구하여 합성 이용율을 계산할 수 있다. 또한 S ( t , ∞)를 생각한다면, 시점 t 에서 그 이후의 모든 태스크들에 대해서 합성 이용율을 정의할 수있다. 주기 태스크를 비주기 태스크로 변환하면 합성 이용율을 적용할 수 있는데 주기 태스크 집합 Tp = { T 1 , T 2 , ⋯, Tn }에서 주기 태스크의 모든 인스턴스들을 비주기 태스크로 생각할 수 있다.
즉 주기 태스크의 임의의 인스턴스 Ti,j 는 도착시각이 Ak = Ai + ( j –1) Ti 이고, 종료시한이 dk = Ti 인 비주기 태스크 Tk 로 생각할 수 있다. 이 두 가지 방법을 이용하고, 비주기 태스크 집합 Ta 가 EDF에 의해 스케줄링 될 때 합성 이용율
PPT Slide
Lager Image
을 이용하여 다중프로세서 시스템에서 주기 태스크와 비주기 태스크가 혼합된 태스크 집합에 대해 합성 이용율을 적용할 수 있다. 프로세서의 개수 m = 1이고, 비주기 태스크 집합을 Ta , 주기 태스크 집합을 Tp (단, T = D ), 그리고 변환된 주기 태스크 집합을 Tp' 이라할 때 Ta Tp' 의 합집합을 Ts 라 하자. 비주기 태스크가 도착할 때 마다 모든 Ti Ts 에 대해 EDF에 의한 방식을 사용하므로 합성 이용율 UTs ( t , t' )≤1가 만족되면 비주기 태스크 Ti 는 스케줄링 가능하다. 하지만 이 방법은 모든 주기 태스크의 인스턴스에 대해 구간별로 모두 검사 해야 하므로 실제로는 불가능하다. 또한 구간 [t, t']에서 현재 시간을 t라 할 때 현재 시간 t부터 t'까지 태스크 정보를 변환된 주기 태스크는 알 수 있지만 비주기 태스크는 전혀 알 수 없기 때문에 구간을 이용한 방법은 실제 불가능하다.
하지만 주기 태스크와 비주기 태스와의 관계를 이용하면 이러한 문제를 해결할 수 있다. 주기 태스크 집합 Tp EDF에 의해 스케줄링 될 때 프로세서 이용율은
PPT Slide
Lager Image
이다. 또한 변환된 주기 태스크 Tp' 의 합성 이용율은
PPT Slide
Lager Image
로 표현된다. 이때 UTp' ( t , t' )≤ UTp 의 관계를 가진다. 즉, EDF 알고리즘에 의해 스케줄되는 원래의 주기 태스크의 프로세서 이용율은 비주기 태스크로서 변환되어 합성 이용율을 적용한 프로세서 이용율 보다 항상 크거나 같다.
다음 표 1 UTp' ( t , t' )≤ UTp 의 예이다. T 1 , T 4 는 비주기 태스크로 ( Ai , Ci , Di )가 각각 (1,3,11), (4,2,10) 이고 T 2 , T 3 은 주기 태스크로 ( Ai , Ci , Pi )가 각각 (3,2,7), (5,1,9) 이다. 여기서 Pi 태스크 Ti 의 주기다. 먼저
PPT Slide
Lager Image
를 구하면 변환된 주기 태스크 T 2 , T 3 에 대해 현재 요청집합은 S (2,4) = { T 2 }이므로
PPT Slide
Lager Image
이다.
혼합 태스크 집합Table. 1 Mixed Tasks Set
PPT Slide
Lager Image
혼합 태스크 집합 Table. 1 Mixed Tasks Set
또한
PPT Slide
Lager Image
이므로
PPT Slide
Lager Image
이다. 그러므로 UTp' < UTp 이다. 만일 주기 태스크 T 3 이 존재하지 않는다면
PPT Slide
Lager Image
이다. 그러므로 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 는 모든 비주기 태스크 Ti Q 에 대해 UTS ≤1을 만족하면 스케줄링 가능하다.
그림 2 에서처럼 EDF에 의한 주기 태스크의 이용율이 0.39이고, 임의의 시점 t에서 비주기 태스크의 이용율이 1-0.39를 넘지 않으면 주기 태스크 스케줄링을 보장하면서 비주기 태스크들도 스케줄링 가능하다. 이 방법은 앞에서 제시한 구간을 이용하는 방법처럼 모든 구간을 점검하지 않고 주기 태스크의 이용율을 이용해서 비주기 태스크와 주기 태스크가 혼합된 태스크 집합에 적용할 수 있다. 또한 합성 이용율을 [6] 에서 제시한 개선된 합성 이용율 방법을 사용하면 비주기 태스크들의 스케줄링 가능성이 증가하게 된다.
PPT Slide
Lager Image
구간 [2,4]에서 주기 태스크의 합성 이용율 Fig. 2 Periodic Tasks Synthetic Utilization at [2,4]
Ⅲ. 모의 실험
- 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 알고리즘의 경우 수행시간이 길고 우선순위가 낮은(종료시한이 긴) 태스크가 먼저 실행되고 수행시간이 짧고 우선순위가 높은(종료 시한이 짧은) 태스크가 나중에 도착하여 실행되면 높은 우선순위의 태스크들이 거절당하는 경우가 발생하기 때문이다.
PPT Slide
Lager Image
Tp = 0.3 인 경우 혼합 태스크 스케줄링 Fig. 3 Mixed Task Scheduling in Tp = 0.3
PPT Slide
Lager Image
Tp = 0.7 인 경우 혼합 태스크 스케줄링 Fig. 4 Mixed Task Scheduling in Tp = 0.7
그림 5 , 그림 6 , 그림 7 은 프로세서의 개수별로 다중 프로세서 시스템에서 합성이용율과 TBS 알고리즘의 워크로드별 변화로 워크로드별로 비교해 볼 때 합성이용율의 방법이 TBS 알고리즘 방법보다 더 많은 태스크 집합들을 스케줄링 가능하다는 것을 알 수 있다.
PPT Slide
Lager Image
m = 2인 경우 프로세서 이용율 Fig. 5 Processor Utilization in m = 2
PPT Slide
Lager Image
m = 16인 경우 프로세서 이용율 Fig. 6 Processor Utilization in m = 16
PPT Slide
Lager Image
m = 32인 경우 프로세서 이용율 Fig. 7 Processor Utilization in m = 32
Ⅳ. 결 론
다중 프로세서 시스템에서 비주기 태스크들을 스케줄링하는 경우 대부분의 알고리즘이 주기 태스크를 먼저 스케줄링 한 후 나머지 대역폭을 비주기 태스크에 할당하여 스케줄링하는 방법을 사용한다. 본 논문에서는 EDF 스케줄링 방식을 이용하여 비주기 태스크만을 스케줄링하는 합성 이용율 방법을 주기 태스크에 적용할 수 있도록 변경하였고, 이를 이용하여 주기 태스크와 비주기 태스크가 혼합된 태스크 집합들을 스케줄링 하는 방법을 제시하였다. 합성 이용율은 프로세서 이용율을 이용하기 때문에 스케줄링 가능성 여부를 빠르게 판단할 수 있다. 본 논문에서 제시한 다중 프로세서 시스템에서 주기 태스크와 비주기 태스크의 혼합 집합에 대한 스케줄링 가능성 여부는 주기 태스크의 이용율에 따라서 차이를 보이게 되는데 주기 태스크의 이용율이 높아지면 비주기 태스크가 사용할 수 있는 대역폭이 줄어들기 때문에 상대적으로 스케줄링 가능성이 줄어들게 된다. 주기 태스크의 이용율이 낮은 경우 다중프로세서 시스템에서 TBS 알고리즘과 본 논문에서 제시한 방법을 비교하면 약 20%정도 성능 차이를 보이며, 또한 워크로드에 따라 스케줄링 가능성이 다중프로세서 시스템에서 TBS 알고리즘보다 개선된 것을 볼 수 있었다. 본 논문에서는 다중 프로세서 환경에서 주기 태스크와 비주기 태스크의 혼합된 태스크 집합에서의 이용율 측정을 통한 스케줄링 가능성 여부를 판단하였지만 단일 코어, 다중 코어 시스템 환경에서 혼합 태스크 집합의 스케줄링 가능성 판단을 위한 연구가 필요하다.
BIO
문석환(Seok-Hwan Moon)
2001년 단국대학교 전자계산학과 이학석사
2009년 단국대학교 전자계산학과 이학박사
2006년 ~ 현재 영동대학교 임베디드소프트웨어학과 교수
※관심분야 : 실시간 스케줄링, 실시간 운영체제, 임베디드 시스템
References
Liu C. L. , Layland J. W. 1973 "Scheduling algorithms for multiprogramming in hard real time environment" Journal of the ACM 20 46 - 61    DOI : 10.1145/321738.321743
Chetto H. , Chetto M. 1989 "Some results of the earliest deadline first scheduling algorithm" IEEE Transactions on Software Engineering 15 (10) 1261 - 1268    DOI : 10.1109/TSE.1989.559777
Abdelzaher T. F. , Lu C. "Schedulability analysis and utilization bounds for highly scalable real-time services" in Proceedings of IEEE Real-Time Technology and Applications Symposium 2001
Abdelzaher T. F. , Sharma V. , Lu C. 2004 "A Utilization bound for aperiodic tasks and priority driven scheduling" IEEE Transactions on Computers 53 (3) 334 - 350    DOI : 10.1109/TC.2004.1261839
Abdelzaher T. F. , Sharma V. "A synthetic utilization bound for aperiodic tasks with resource requirements." in 15th Euromicro Conference on Real-Time Systems porto, Portugal July. 2003
Moon Seok-Hwan , Kim In-Guk 2008 “A Study on Improved Synthetic Utilization for Real-Time Aperiodic Tasks Scheduling" Journal of digital contents society 9 (3) 441 - 448
Kato Shinpei , Yamasaki Nobuyuki "Scheduling Periodic Tasks using Total Bandwidth Server on Multiprocessors" IEEE/IFIP International Conference Dec 2008 vol.1 82 - 89
Abdelzaher T. F. , Anderson B. , Jonsson J. , Sharma V. , Nguyen M. "The aperiodic multiprocessor utilization bound for liquid tasks." in Real-time and Embedded Technology and Applications Symposium San Jose, California September 2002
Bertogna Marko , Buttazzo Giorgio 2015 "Real-time Scheduling upon Heterogeneous Multiprocessors."Multiprocessor Scheduling for Real-Time Systems. Springer International Publishing 205 - 211