Advanced
Real-Time Aperiodic Tasks Scheduling Using Improved Synthetic Utilization on Multiprocessor Systems
Real-Time Aperiodic Tasks Scheduling Using Improved Synthetic Utilization on Multiprocessor Systems
Journal of the Korea Institute of Information and Communication Engineering. 2014. Jan, 18(1): 97-102
Copyright © 2014, The Korea 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 : September 24, 2013
  • Accepted : November 13, 2013
  • Published : January 31, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
석환 문
shmoon@yd.ac.kr

Abstract
다중프로세서 시스템에서 임의의 시점에 비주기 태스크들의 스케줄링 가능성을 판단하기위한 알고리즘으로서 합성 이용율이 Abdelzaher등에 의해 제시되었는데, 이들은 임의의 시점에 합성이용율의 상한 값인 0.59를 넘지 않으면 비주기 태스크들이 스케줄링 가능 하다는 것을 증명 하였다. 하지만 이 방법은 비주기 태스크들의 프로세서 이용율 계산 시 태스크가 실제 모든 실행시간을 종료하여 더 이상의 실행시간을 갖지 않더라도 현재요청집합에 속해 있다면 실행시간과 종료시한을 합성 이용율에 포함하기 때문에 스케줄링 가능한 태스크들이 실행 불가능한 경우로 판단되는 문제점을 가지고 있다. 본 논문에서는 이러한 문제점을 해결하여 다중프로세서 시스템에서 더 많은 비주기 태스크들이 스케줄링 가능 하도록 개선된 합성 이용율 방법을 제시하였다.
Keywords
I. 서 론
실시간 시스템(real-time system)은 태스크의 수행 결과의 정확성뿐만 아니라 처리시한의 제한인 종료 시한(deadline)을 엄격하게 지키는 것이 요구되는 시스템을 말한다. 실시간 시스템에서 실행되는 태스크들은 일정 시간 마다 도착하여 반복적으로 실행되는 주기(periodic) 태스크와 도착 시간이 정해져 있지 않은 비주기(aperiodic) 태스크로 구분 할 수 있다. 본 논문에서는 합성 이용율을 기반으로 하여 다중프로세서 상에서 비주기 태스크들을 스케줄링 하는 기법을 다룬다.
이제까지 제안된 스케줄링 알고리즘들 중에서 Rate Monotonic (RM) [1] 스케줄링 알고리즘은 고정 우선순위 기반 알고리즘들 중 최적이고, Earliest Deadline First(EDF) [1 - 2] 스케줄링 알고리즘은 동적 우선순위 알고리즘들 중 최적인데 이들은 모두 주기적 태스크 모델을 기본으로 하고 있고, 프로세서 이용율을 이용하여 태스크들을 스케줄링 하는 방법이며, [3] 에서 제시한 방법은 최악의 경우 응답시간(worst case responsetime) [4] 를 이용하여 주기 태스크들의 스케줄링 가능성 여부를 판단하는 방법이다.
비주기 태스크에 대한 스케줄링 분석이 주기 태스크에 비하여 상대적으로 어려운 이유는 태스크가 도착하기 이전에는 태스크의 도착 시점, 수행 시간, 종료 시한을 주기 태스크처럼 미리 예측 할 수 없기 때문이다. 경성 실시간 비주기 태스크 스케줄링 방법으로는 연성 실시간 비주기 태스크에도 적용 가능한 슬랙(slack) 시간 분석을 통한 슬랙 스틸링 알고리즘 [5 - 6] 과 최근에 Abdelzaher등에 의해 제시 된 비주기 태스크들의 이용율 분석을 통한 합성 이용율 알고리즘 [7 - 10] 등이 있다.
본 논문의 구성은 2장에서 다중 프로세서 상에서의 합성 이용율과 이를 이용한 스케줄링 방법을 기술한 후 이의 문제점과 개선된 방법을 제시한다. 3장에서는 모의 실험결과를 보이고, 마지막으로 4장에서는 결론 및 향후 연구 과제에 대하여 기술한다.
II. 비주기 태스크 이용율
- 2.1. 다중프로세서에서의 합성 이용율
Abdelzaher등에 의해 제시된 합성 이용율 방법 [7] 은 경성 비주기 태스크 집합에 대하여 스케줄링 가능한 합성 이용율의 상한 값을 제시하였다. 또한 이를 이용하여 비주기 태스크가 도착했을 때 합성 이용율을 상한 값과 비교하여 도착한 비주기 태스크의 수락여부를 인정할 것인지, 거절할 것인지를 결정하게 된다.
비주기 태스크 집합 Ta 를 { T1 , T2 , T3 Ti ⋯ }라 할 때, T1 T2 보다 먼저 도착(arrival)된 태스크라 가정 한다. 즉 T1 T i+1 보다 먼저 도착한 비주기 태스크 이다. 비주기 태스크 Ti 의 수행시간(execution time)을 Ci (>0), 도착시간(arrival time)을 Ai , 상대적 종료시간(relative deadline)을 Di (>0) (여기서 절대적 종료시간(absolute deadline) di Ai + Di 로서 정의된다.), m을 프로세서의 개수라 할 때 다중프로세서 상에서 임의의 시점 t에서의 합성 이용율 [9] 은 다음과 같이 정의된다.
PPT Slide
Lager Image
식(1)은 Liu와 Layland가 정의한 주기태스크들의 스케줄링 알고리즘인 RM 스케줄링 알고리즘 [1] 을 다중 프로세서 상에서 비주기 태스크에 확장하여 정의하였다. 식(1)에서 현재요청집합(current invocation set) S ( t )는 임의의 시점 t를 기준으로 t이전에 도착한 태스크 중 아직 종료시한이 지나지 않은 태스크 집합을 나타내며 S ( t ) = { Ti | Ai t < Ai + Di } 로서 표현된다.
[9] 에서는 다중프로세서 상에서 임의의 시점 t에서의 합성 이용율 식(1)이 상한값인 0.59를 넘지 않으면 비주기 태스크가 스케줄링 가능하다는 것을 증명하였다. 또한 합성 이용율을 이용한 스케줄링 분석은 O (1)에 수행 할 수 있어 수락제어를 수행할 때 적합하다. 비주기 태스크들의 합성 이용율을 구하기 위해서는 임의의 시점 t에 대한 현재 요청 집합 S (t) 를 먼저 구해야한다.
다음은 t=3과 t=4에서 비주기 태스크 집합의 합성 이용율을 구하는 예제이다. 여기서 프로세서의 개수 m = 1이라고 가정 한다.
합성 이용율을 위한 비주기 태스크 집합Table. 1 Aperiodic Tasks Set for Synthetic Utilization
PPT Slide
Lager Image
합성 이용율을 위한 비주기 태스크 집합 Table. 1 Aperiodic Tasks Set for Synthetic Utilization
합성 이용율을 구하기 위해 먼저 현재 요청 집합을 구하면 S (3) = { T1 , T2 , T3 , T4 }이고, 이것을 식(1)에 적용하게 되면
PPT Slide
Lager Image
이다.
U (3) = 0.57 < 0.59 이므로 시점 t=3에 스케줄링 가능하다. 즉, 태스크 T4 가 시점 t=3에 도착했을 때 이미 도착된 모든 태스크들의 스케줄링 가능성을 보장하므로 T4 는 수락된다. 또한 t=4의 시점에서 합성 이용율을 구하게 되면 집합 S (4)도 변화가 없고 U (4)의 값도 변화가 없으므로 모든 태스크들은 스케줄링 가능하다.
PPT Slide
Lager Image
t=3에서의 현재요청집합 Fig. 1 Current Invocation set at t=3
하지만 모든 태스크들의 종료시한이 1만큼씩 줄어들게 되면
PPT Slide
Lager Image
이 되므로 상한 값 0.59를 넘게 되어 스케줄링 불가능한 상태가 된다. 이 때, S (4)의 태스크 중 태스크 T3 는 실행시간이 종료되었지만, 종료시한을 넘지 않았기 때문에 실제 시점 t=4이후에는 실행되지 않더라도 집합 S (4)에 속하게 되고 이용율 계산 시 C4 값이 불필요하게 합성 이용율에 함께 계산 된다. 또한 t=4 이후에는 실행시간이 C 1 = 1, C 2 = 1만큼만 실행하면 되지만, 합성 이용율에서는 S ( t )에 속하게 되면 모든 실행 시간을 포함하여 이용율을 계산하게 된다.
이러한 문제점으로 인해 특정시간 t에서의 합성 이용율은 계산할 때 t이후에 실제 스케줄링 가능하지만, 스케줄링 불가능하게 판단되는 경우가 발생하게 된다. 본 논문에서는 이러한 문제를 개선하여 스케줄링 가능성을 높이고자 한다.
- 2.2. 다중프로세서에서의 개선된 합성 이용율
임의의 시점 t에서 합성 이용율을 계산할 때 먼저 고려되어야 할 것은 시점 t이전에 도착하였으나 아직 시점 t이전에 종료시한을 넘기지 않은 비주기 태스크들의 집합, 즉, S ( t ) = { Ti | Ai t < Ai + Di }로서 표현 되는 현재 요청 집합 S ( t )의 원소에 해당하는 비주기 태스크들 을 찾는 것이다. 이러한 S ( t )에 속하는 비주기 태스크들 중 시점 t를 기준으로 먼저 도착 하였고, 종료시한은 넘지 않았지만, 시점 t이전에 실행시간을 모두 마친 태스크들이 포함될 수 있다. 이러한 태스크들은 임의의 시점 t이후부터 태스크의 종료시한까지 실제 프로세서를 이용하지 않지만 이용율 계산 시 실행 시간이 포함되는 문제점을 가지고 있다. 본 논문에서는 이러한 조건을 제거하여 합성 이용율을 계산한다. 개선된 현재 요청집합을 S' ( t ) = { Ti | Ai t < Ai + Di , t < Cie }로 표현하고 여기서 Cie 는 비주기 태스크 Ti 의 실행시간 Ci 의 종료시 점이다. Ci 의 종료시점은 고정 우선순위를 이용하기 때문에 계산해낼 수 있다.
또한 합성 이용율
PPT Slide
Lager Image
에서 Ci Di 값은 태스크 Ti S ( t ) 의 조건을 만족하여 S ( t )의 원소가 되면 항상 동일한 값을 가진다. 즉 시점 t가 증가하더라도 S ( t )에 속하면 항상 동일한 합성 이용율값을 가지게 되는데 이것은 시점 t이전에 이미 실행 완료된 태스크의 실행시간 값까지 합성 이용율에 포함되기 때문에 실제 남은 실행시간 값이 매우 작더라도 시점 t에서 스케줄링이 불가능하게 판단되는 경우가 발생할 수 있다. 이러한 문제를 개선하기 위해 Ci 값과 Di 값을 시점 t를 기준으로 하여 변경한 Ci Di 값을 이용하여 합성 이용율을 구한다.
시점 t를 기준으로 하여 태스크 Ti 의 실행을 마치기 위해 필요한 최대 수행시간 [11] 를 잉여 수행시간 ei,t 라 하고, 시점 t를 기준으로 하여 태스크 Ti 의 절대 종료시한 di 와 현재 시점 t와의 차이, 즉 di - t 를 리드시간(lead time) [12] Di,t 라고 정의하면 다중프로세서 상에서 임의의 시점 t에서의 합성 이용율은 다음과 같이 새롭게 표현할 수 있다.
PPT Slide
Lager Image
다음은 새롭게 정의된 S' , ei,t , Di,t 를 이용해서 개 선된 합성 이용율을 구하는 예제이다. 여기서 프로세서의 개수 m = 1이라고 가정 한다.
그림 2 에서처럼 시점 t=4에서 개선된 현재 요청 집합은 S ′(4) = { T 1 , T 2 , T 4 }이 된다. T 3 이 개선된 현재 요청 집합에서 제외된 이유는 t=4에서 종료시한은 지나지 않았지만, 실행시간이 모두 종료되었기 때문이다.
개선된 합성 이용율을 위한 비주기 태스크 집합Table. 2 Aperiodic Tasks Set for Improved Synthetic Utilization
PPT Slide
Lager Image
개선된 합성 이용율을 위한 비주기 태스크 집합 Table. 2 Aperiodic Tasks Set for Improved Synthetic Utilization
PPT Slide
Lager Image
t=4에서의 개선된 합성 이용율 Fig. 2 Improved Synthetic Utilization at t=4
식(2)를 이용하면 t=4에서의 개선된 합성 이용율은 다음과 같다.
PPT Slide
Lager Image
U (1), U (2)의 경우에는 S '( t )값의 변화는 없으나 시간 의 흐름에 따라 이용율이 변하게 되고, U (5), U (6), U (7)의 경우는 S '( t )값도 변하고, 이용율도 변하게 되어 U (1) = 0.488, U (2) = 0.448, U (5) = 0.257 U (6) = 0.181, U (7) = 0.1의 값을 가진다.
U (1)부터 U (7)까지의 합성 이용율을 비교해 보면 U (1)보다 U (7)이 더 낮은 이용율을 보이는데 이것은 이용율과 비례관계에 있는 실행 시간이 줄어들기 때문이다. 다른 비주기 태스크가 도착하여 수락 여부를 판단하는 경우에 시점 t=3 보다 시점 t=4에서 비주기 태스크가 수락될 가능성이 높아진다고 볼 수 있다. 예제처럼 재 정의된 S '( t ), ei,t , Di,t 를 이용하여 합성 이용율을 계산한 후 합성 이용율의 상한 값인 0.59와 비교하여 임의의 시점 t에 도착한 비주기 태스크의 수락 여부나, 이미 도착되어 실행 중인 비주기 태스크들의 합성 이용율을 이용하여 스케줄링 가능성 여부를 판단한다.
III. 모의 실험
- 3.1. 모의실험 방법
본 장에서는 모의실험을 통해 프로세서 개수의 변화에 따른 기존의 합성 이용율과 본 논문에서 제시한 방법을 비교한다. 모의실험에서는 도착시간( Ai ), 수행시간( Ci > 0), 상대적 종료시한( Di > 0)을 가지는 비주기 태스크 1000개를 랜덤하게 생성하고 임의의 시점 t에서의 기존의 합성 이용율과 본 논문에서 제시한 방법으로 구한 합성 이용율 값을 비교 하였다. 또한 아래와 같이 프로세서 개수별로 워크로드를 변화시키고, 기존의 합성 이용율과 개선된 방법에서의 합성 이용율 변화를 그래프로서 비교 하였다. Ci / min( di , Ti )로 표현되는 태스크 밀도는 일반적인 0.1로 하였고, 입력 워크로드는 모든 도착된 태스크들의 수행시간의 합과 태스크들이 도착한 시간구간의 비율로 표현할 수 있는데 실험 범위는 40% ~ 150%까지 10%씩 증가되는 시점에서 이용율을 측정 하였다.
- 3.2. 실험 결과
다음의 그림 3 그림 4 는 프로세서의 개수별 기존의 합성 이용율과 개선된 방법을 적용한 합성 이용율에 대한 워크로드의 변화에 따른 비주기 태스크들의 프로세서 이용율을 보여주고 있다.
PPT Slide
Lager Image
기존의 합성 이용율 Fig. 3 Synthetic Utilization
PPT Slide
Lager Image
개선된 합성 이용율 Fig. 4 Improved Synthetic Utilization
그림 3 에서 입력 워크로드가 클수록 프로세서의 개수에 따라 수락율의 많은 차이를 보인다. 그 이유는 입력워크로드가 크다는 의미는 시간구간에 비해 도착되는 비주기 태스크들이 많이 도착된다는 의미이므로 프로세서 이용율이 올라가기 때문이며, 또한 프로세서의 개수가 적을수록 이용율이 높아지기 때문이다. 실험결과에서도 볼 수 있듯이 기존 합성 이용율과 개선된 합성 이용율을 비교해 보면 개선된 방법의 합성 이용율이 좀더 낮은 이용율을 갖는다는 것을 알 수 있다.
그림 4 에서 개선된 합성 이용율은 그림 3 의 합성 이용율과 비교할 때 프로세서 개수의 변화와 워크로드의 변화에 따른 프로세서의 이용율의 차이가 크지 않게 나타난다. 그 이유는 기존의 합성 이용율에서는 임의의 시점 t에서 이용율을 측정할 때 태스크의 종료시한을 넘기지 않았다면 태스크의 실행이 완료 되었다 하더라도 실행시간을 이용율에 포함시키기 때문이다. 개선된 방법에서는 남은 실행시간만을 이용하여 프로세서 이용율을 계산하기 때문에 실제 임의의 시점 t에서 기존의 합성 이용율보다 개선된 합성 이용율의 값이 낮은 값을 가지는데, 이것은 이미 입력된 비주기 태스크들의 스케줄링을 보장하면서 시점 t에 입력되는 다른 비주기 태스크들의 수락율을 높일 수 있다는 의미를 가진다.
그림 5 , 그림 6 , 그림 7 은 프로세서의 개수별로 기존의 합성 이용율과 개선된 합성 이용율의 워크로드별 변화를 보여준다. 그림에서 보듯이 워크로드별로 비교해 볼 때 개선된 스케줄링 방법이 기존의 방법보다 더 많은 태스크 집합들을 스케줄링 가능하다는 것을 알 수 있다. 또한 m=2인 경우에 비해 m=16, m=32처럼 m의 개수가 커질수록 기존의 방법에 비해 성능이 우수하다는 것을 알 수 있다.
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
IV. 결 론
본 논문에서는 다중프로세서 시스템에서 시점 t에서 현재요청집합의 조건을 변화시켜 합성 이용율에 의한 프로세서 이용율을 개선함으로써 기존의 합성 이용율을 이용하면 스케줄링이 불가능하던 비주기 태스크들을 스케줄링 가능하게 하는 방법을 제시하였다. 또한 실험을 통해 개선된 스케줄링 방법이 프로세서 개수와 워크로드의 변화에 따른 프로세서 이용율이 기존의 방법보다 낮은 값을 갖는다는 것을 확인 하였으며, 이것은 더 많은 비주기 태스크들을 수락할 수 있다는 의미를 가진다.
본 논문에서는 다중프로세서 시스템에서 비주기 태스크만을 고려하여 임의의 시간에서의 합성 이용율을 통하여 스케줄링의 가능성 여부를 판단하였지만, 주기 태스크들과의 혼합된 태스크 집합에서의 이용율 측정을 통한 스케줄링 가능성 판단 여부 및 수락율에 대한 연구가 필요하다.
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
Kim In-Guk , Kim Dong-Yoon , Hong Man-pyo 1994 "Real-time scheduling of tasks that contain the external blocking intervals" Proceedings Second International Workshop on RTCSA '95 54 - 59
Wellings A. , Richardson M. , Burns A. , Audsley N. , Tindell K. "Applying new scheduling theory to static priority preemptive scheduling." Dept. of Computer Science, Univ. of York
Lehoczky J. P. , Ramos-Thuel S. 1992 "An optimal algorithm for scheduling soft-aperiodic tasks in fixedpriority preemtive systems" in Proceedings of the real- Time Systems Symposium 110 - 123
Thuel S. R. , Lehoczky J. P. 1995 "Algorithms for scheduling hard aperiodic tasks in fixed-priority systems using slack stealing" in Proceedings of IEEE Real-Time Systems Symposium 22 - 33
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. , Lu C. 2001 "Schedulability analysis and utilization bounds for highly scalable real-time services" in Proceedings of IEEE Real-Time Technology and Applications Symposium
Abdelzaher T. F. , Anderson B. , Jonsson J. , Sharma V. , Nguyen M. 2002 "The aperiodic multiprocessor utilization bound for liquid tasks." in Real-time and Embedded Technology and Applications Symposium
Abdelzaher T. F. , Sharma V. 2003 "A synthetic utilization bound for aperiodic tasks with resource requirements." in 15th Euromicro Conference on Real-Time Systems
Park J. , Ryu M. , Hong S. 2004 "Deterministic and statistical admission control for QoS-aware embedded systems" Journal of Embedded Computing 1 (1)
Lehoczky J. P. 1996 "Real-time queueing theory" in Proceedings of IEEE Real-Time Systems Symposium 186 - 195