KR101430077B1 - 멀티프로세서 장치에서의 스케줄링 방법 및 멀티프로세서 장치에서 가상 마감시간을 이용하여 태스크에 대한 우선순위를 결정하는 방법 - Google Patents

Abstract

멀티프로세서 장치에서의 스케줄링 방법은 태스크들이 생성되는 단계(510), 태스크들 중에 하나의 태스크 τ_a에 속하는 작업들이 다른 하나의 태스크 τ_b에 속하는 작업들보다 항상 높은 우선순위를 갖도록 태스크들에 상대적 가상 마감시간을 설정하여 태스크 우선순위를 결정하는 단계(520) 및 태스크에 속하는 작업들에 절대적 가상 마감시간을 설정하여 작업 우선순위를 결정하는 단계(530)를 포함한다.

Description

멀티프로세서 장치에서의 스케줄링 방법 및 멀티프로세서 장치에서 가상 마감시간을 이용하여 태스크에 대한 우선순위를 결정하는 방법{SCHEDULING METHOD IN MULTIPROCESSOR APPARATUS AND PRIORITY ASSIGNING METHOD USING PSEUDO-DEADLINE IN MULTIPROCESSOR APPARATUS}

이하 설명하는 기술은 멀티프로세서를 갖는 장치에서 태스크 내지 작업에 대한 우선순위를 부여하는 스케줄링 방법에 관한 것이다.

현재 멀티코어를 탑재한 실시간 임베디드 시스템은 점차 널리 사용되고 있는 추세이며, 이에 따라 실시간 임베디드 시스템에 대한 연구가 활발히 진행되고 있다. 실시간 시스템에서 각각 연속적으로 실시간 작업을 생성해 내는 각각의 실시간 태스크들에 대해, 실시간 스케줄링 알고리즘은 실시간 작업들에 대해 우선순위를 할당하여 이를 기반으로 스케줄링하게 된다. 이와 같은 실시간 시스템에 대한 연구는 대표적으로 두 가지에 대해 이루어진다. 실시간 태스크와 실시간 작업에 우선순위를 효과적으로 할당하여 마감 시간을 어기지 않게 하는 것이 목적인 실시간 스케줄링 알고리즘과 할당된 우선순위를 기반으로 스케줄링 될 때, 시스템이 마감 시간을 어기지 않을 것인지 분석하는 것이 목적인 실시간성(스케줄 가능성) 분석 기법이다.

우선순위를 기반으로 하는 실시간 스케줄링 알고리즘으로 대표적인 두 가지 종류의 스케줄링 알고리즘이 있다. 실시간 태스크에 우선순위를 할당하여 스케줄링하는 태스크 단위 우선순위 스케줄링 알고리즘(TFP), 실시간 태스크보다 더 작은 개념인 실시간 작업에 우선순위를 할당하여 스케줄링하는 작업 단위 우선순위 스케줄링 알고리즘(JFP: Job-level Fixed Priority)이다. 두 가지 스케줄링 알고리즘의 정의에 의해, 작업 단위 우선순위 스케줄링 알고리즘은 태스크 단위 우선순위 스케줄링 알고리즘이 일반화된 것이며, 더 세부적인 우선순위 할당이 가능하다.

태스크 단위 우선순위 스케줄링 알고리즘과 이를 지원하는 실시간성 분석 기법에 대해서는 활발한 연구가 진행된 반면(B. Andersson, S. Baruah, and J. Jonsson, "Static-priority scheduling on multiprocessors, in RTSS, 2001. 등 참고), 작업 단위 우선순위 스케줄링 알고리즘에 대해서는 진행된 연구가 미미한 실정이다. 작업 단위 우선순위 스케줄링 알고리즘이 태스크 단위 우선순위 스케줄링 알고리즘의 일반화된 것임에도 불구하고, 현재의 기술력으로는 태스크 단위 우선순위 스케줄링 알고리즘을 지원하는 정확도가 높은 강력한 실시간성 분석 기법들을 작업 단위 우선순위 스케줄링 알고리즘에 적용하는 것은 불가능하다. 이는 그러한 강력한 기술들이 최초에 태스크 단위 우선순위 스케줄링에만 적합하게끔 고안되었고 이를 작업 단위 우선순위 스케줄링에 적용가능 하게끔 하는 각각의 작업에 대해 효과적으로 우선순위를 할당하는 방법이 존재하지 않기 때문이다.

그러나 작업 레벨에서 동적 우선수위 부여 기법(JDP: Job-level Dynamic Priority)은 많은 연구가 진행되었다(G. Levin, S. Funk, C. Sadowski, I. Pye, and S. A. Brandt, "Dp-fair: A simple model for understanding optimal multiprocessor scheduling," in ECRTS, 2010. 등 참고).

JFP에 대한 연구가 부족하여 생기는 가장 치명적인 문제점은 각각의 작업에 우선순위를 할당하는 작업 단위 우선순위 스케줄링 알고리즘이 그 특성상, 태스크 단위 우선순위 스케줄링 알고리즘보다 선점(preemption) 과 이동(migration)과 같은 오버헤드를 더 많이 요구한다는 단점을 가지는 동시에, 상대적으로 정확도가 낮은, 성능이 떨어지는 실시간성 분석 기법들만이 사용 가능하게 된다는 것이다.

따라서, 더 세밀한 우선순위 할당이 가능함에도, 작업 단위 우선순위 스케줄링 알고리즘을 사용하는 실시간 시스템이 태스크 단위 우선순위 스케줄링 알고리즘을 사용하는 시스템보다 훨씬 더 낮은 성능을 보이게 된다.

이하 설명하는 기술은 종래 TFP에서 우선순위 부여를 위해 이용하던 기법을 JFP에 확장하여 스케줄링을 수행하는 방법을 제공하고자 한다.

이하 설명하는 기술은 태스크 세트를 일정한 서브 세트로 분할하여 서브 세트 사이의 관계가 TFP에서의 태스크 관계와 동일하게 하고자 한다. 이를 통해 TFP에 적용하던 우선순위 부여 기법 및 스케줄 가능성 분석 기법을 작업 레벨에서도 적용가능하게 하고자 한다.

이하 설명하는 기술의 해결과제는 이상에서 언급된 것들에 한정되지 않으며, 언급되지 아니한 다른 해결과제들은 아래의 기재로부터 당업자에게 명확하게 이해될 수 있을 것이다.

전술한 과제를 해결하기 위한 멀티프로세서 장치에서의 스케줄링 방법은 태스크들이 생성되는 단계, 태스크들 중에 하나의 태스크 τ_a에 속하는 작업들이 다른 하나의 태스크 τ_b에 속하는 작업들보다 항상 높은 우선순위를 갖도록 태스크들에 상대적 가상 마감시간을 설정하여 태스크 우선순위를 결정하는 단계 및 태스크에 속하는 작업들에 절대적 가상 마감시간을 설정하여 작업 우선순위를 결정하는 단계를 포함한다.

태스크 우선순위를 결정하는 단계는 τ_a 및 τ_b가 P_a ≤ P_b - D_b 조건을 만족하도록 상대적 가상마감시간을 설정한다. 여기서, P_a는 τ_a의 상대적 가상 마감시간, P_b는 τ_b의 상대적 가상 마감시간, D_b는 τ_b의 상대적 마감시간이다.

상대적 가상 마감시간은 태스크에 속한 작업이 생성되는 시간부터 작업의 절대적 가상 마감시간까지의 간격이고, 상대적 마감시간은 하나의 작업이 생성되는 시간부터 작업의 절대적 마감시간까지의 간격이다.

작업 우선순위를 결정하는 단계는 태스크들(τ_i)의 h 번째 작업(

)의 절대적 가상 마감시간(

)이

로 연산되며 가장 작은

를 갖는 작업에 가장 높은 우선순위를 부여한다. 여기서,

는

가 생성되는 시간이고, P_i는 τ_i의 상대적 마감시간이다.

태스크 우선순위를 결정하는 단계는 태스크들 중에 서로 다른 태스크인 τ_i 및 τ_k가 m개의 동일한 프로세서를 포함하는 멀티프로세서에서 다음 수학식과 같은 간섭 조건을 만족한다.

여기서,

는 본 발명의 스케줄링 방법에서 태스크 τ_i와 τ_k사이의 간섭, D_k는 태스크의 상대적인 마감시간, C_k는 태스크의 최악의 수행시간이다.

본 발명의 다른 측면에서 멀티프로세서 장치에서 가상 마감시간을 이용하여 태스크에 대한 우선순위를 결정하는 방법은 k 단계에서 태스크 세트를 우선순위가 결정된 서브세트(A(k)) 및 k 단계 이후에 우선순위를 결정해야 하는 서브세트(R(k))로 분할하는 단계, R(k)에서 가상 마감시간을 할당하기 위한 서브세트 S(k)를 결정하는 단계 및 S(k)에 대한 가상 마감시간을 할당하여 우선순위를 부여하는 단계를 포함한다.

A(k)와 R(k)는 A(k)에 속하는 태스크 τ_a 및 R(k)에 속하는 태스크 τ_r가 P_a ≤ P_r - D_r 조건을 만족하여, τ_a에 속하는 작업들이 τ_r에 속하는 작업들보다 높은 우선순위를 갖는다. 여기서, P_a는 τ_a의 상대적 가상 마감시간, P_r는 τ_r의 상대적 가상 마감시간, D_r는 τ_r의 상대적 마감시간이다.

S(k)를 결정하는 단계는 R(k)에 속하는 태스크들의 모든 조합을 검토하여 S(k)를 결정하되, S(k)에 속하는 태스크의 작업들이 모두 A(k)에 속하는 태스크 작업보다 우선순위가 높고, S(k)에 속하는 태스크의 작업들이 R(k)에 남아있는 태스크의 작업보다 우선순위가 낮도록 결정한다.

A(k)와 R(k)의 사이의 시간에 버퍼 영역 [Z^H(k), Z^L(k)]이 위치하고, 버퍼 영역 내에는 가상 마감시간이 할당되지 않는 멀티프로세서 장치에서 가상 마감시간을 이용한다.

S(k)를 결정하는 단계는 S(k)에 속하는 태스크들 중 서로 다른 태스크인 τ_i 및 τ_k가 m개의 동일한 프로세서를 포함하는 멀티프로세서에서 다음 수학식과 같은 간섭 조건을 만족한다.

여기서,

는 태스크 τ_i와 τ_k사이의 간섭, D_k는 태스크의 상대적인 마감시간, C_k는 태스크의 최악의 수행시간이다.

이하 설명하는 기술은 실시간 태스크에 가상의 데드라인을 할당하고 이를 이용하여 스케줄링하고 실시간 분석 기법들을 적용함으로써, 태스크 단위 우선순위 스케줄링 알고리즘에만 적용 가능하였던 실시간성 분석 기법들을 작업 단위 우선순위 스케줄링 알고리즘의 실시간성 분석 기법에도 적용 가능해지는 효과가 있다.

또한, 이하 설명하는 기술은 가상 데드라인을 최적으로 할당하는 방법을 이용하여, 기존의 실시간 기법들보다 훨씬 나은 성능을 보장하게 되는 효과가 있다.

마지막으로 이하 설명하는 기술은 가상 데드라인의 최적 할당 방법은 높은 시간 복잡도를 가지는 단점이 있는데 휴리스틱 할당 방법을 통하여 이보다 훨씬 낮은 시간 복잡도를 가지는 동시에 비슷한 성능을 보이게 되는 효과가 있다.

이하 설명하는 기술의 효과는 이상에서 언급된 것들에 한정되지 않으며, 언급되지 아니한 다른 효과들은 아래의 기재로부터 당업자에게 명확하게 이해될 수 있을 것이다.

도 1은 멀티프로세서 장치에서의 스케줄링 방법에 대한 개략적인 순서도의 예이다.
도 2는 어떤 두 개의 태스크 τ_a 및 τ_b가 P_a ≤ P_b - D_b 와 같은 조건을 만족해야만, 두 개의 태스크는 τ_a

τ_b와 같은 관계를 갖는 것을 설명한다.
도 3은 두 개의 태스크 세트 τ'와 τ''간의 관계와 각 태스크 세트에 속한 태스크들 τ_i 와 τ_j간의 관계를 도시한다.
도 4는 SPDF 기법에 대한 간섭 기반 분석에서 서로 다른 경우에 대한 최악의 경우를 도시한 예이다.
도 5는 멀티프로세서 장치에서 가상 마감시간을 이용하여 태스크에 대한 우선순위를 결정하는 방법에 대한 순서도의 예이다.
도 6은 OPDA의 k 단계에서 버퍼 영역의 예를 도시한다.

본 발명은 다양한 변경을 가할 수 있고 여러 가지 실시예를 가질 수 있는 바, 특정 실시예들을 도면에 예시하고 상세하게 설명하고자 한다. 그러나, 이는 본 발명을 특정한 실시 형태에 대해 한정하려는 것이 아니며, 본 발명의 사상 및 기술 범위에 포함되는 모든 변경, 균등물 내지 대체물을 포함하는 것으로 이해되어야 한다.

제1, 제2, A, B 등의 용어는 다양한 구성요소들을 설명하는데 사용될 수 있지만, 해당 구성요소들은 상기 용어들에 의해 한정되지는 않으며, 단지 하나의 구성요소를 다른 구성요소로부터 구별하는 목적으로만 사용된다. 예를 들어, 본 발명의 권리 범위를 벗어나지 않으면서 제1 구성요소는 제2 구성요소로 명명될 수 있고, 유사하게 제2 구성요소도 제1 구성요소로 명명될 수 있다. 및/또는 이라는 용어는 복수의 관련된 기재된 항목들의 조합 또는 복수의 관련된 기재된 항목들 중의 어느 항목을 포함한다.

본 명세서에서 사용되는 용어에서 단수의 표현은 문맥상 명백하게 다르게 해석되지 않는 한 복수의 표현을 포함하는 것으로 이해되어야 하고, "포함한다" 등의 용어는 설시된 특징, 개수, 단계, 동작, 구성요소, 부분품 또는 이들을 조합한 것이 존재함을 의미하는 것이지, 하나 또는 그 이상의 다른 특징들이나 개수, 단계 동작 구성요소, 부분품 또는 이들을 조합한 것들의 존재 또는 부가 가능성을 배제하지 않는 것으로 이해되어야 한다.

도면에 대한 상세한 설명을 하기에 앞서, 본 명세서에서의 구성부들에 대한 구분은 각 구성부가 담당하는 주기능 별로 구분한 것에 불과함을 명확히 하고자 한다. 즉, 이하에서 설명할 2개 이상의 구성부가 하나의 구성부로 합쳐지거나 또는 하나의 구성부가 보다 세분화된 기능별로 2개 이상으로 분화되어 구비될 수도 있다. 그리고 이하에서 설명할 구성부 각각은 자신이 담당하는 주기능 이외에도 다른 구성부가 담당하는 기능 중 일부 또는 전부의 기능을 추가적으로 수행할 수도 있으며, 구성부 각각이 담당하는 주기능 중 일부 기능이 다른 구성부에 의해 전담되어 수행될 수도 있음은 물론이다.

또, 방법 또는 동작 방법을 수행함에 있어서, 상기 방법을 이루는 각 과정들은 문맥상 명백하게 특정 순서를 기재하지 않은 이상 명기된 순서와 다르게 일어날 수 있다. 즉, 각 과정들은 명기된 순서와 동일하게 일어날 수도 있고 실질적으로 동시에 수행될 수도 있으며 반대의 순서대로 수행될 수도 있다.

이하에서는 도면을 참조하면서 본 발명에 관하여 구체적으로 설명하겠다.

한편 본 발명은 발명자가 공개한 논문 "Extending Task-level to Job-level Fixed Priority Assignment and Schedulability Analysis Using Pseudo-deadlines"(2012 IEEE 33rd Real-Time Systems Symposium, 2012.12)에 기재된 내용에 의해 더욱 자세하게 이해된다. 명세서에 기재되지 않은 내용은 발명자의 상기 논문을 참고하기 바란다.

본 발명은 m개의 동일한 프로세서를 포함하는 멀티프로세서 플랫폼에서 작동하는 글로벌 스케줄링(global scheduling) 기법에 관한 것이다. 먼저 본 발명의 구체적인 설명에 앞서서 설명에 사용되는 시스템 모델, 용어 등에 대해 설명하고자 한다.

본 발명에서는 지속적으로 상주하지 않고 간헐적으로 발생하는 태스크(task) 모델(τ)을 전제로 한다. 여기서 태스크 τ_i(τ_i∈τ)는 잠재적으로 무한하게 수행될 수 있는 연속적인 작업(job)일 수 있다. 본 발명의 태스크 모델은 ∀_i, C_i ≤ D_i ≤ T_i과 같은 제한 조건을 갖고, 하나의 작업은 병렬적으로 수행되지 못한다. 여기서, T_i는 작업 간 최소 간격시간(minimum inter-job separation), C_i는 최악의 수행 시간(worst-case execution time), D_i는 상대적인 마감시간(relative deadline)을 의미한다.

태스크의 밀집도(density)는 δ_i = C_i / D_i과 같이 정의되고, 시스템 밀집도는

와 같이 정의된다. 이하

를 태스크 τ_i의 h 번째 작업이고,

및

를 각각 태스트로부터 작업이 생산되는 시간(release time) 및 절대적 마감시간(absolute deadline)이라고 명명한다.

는

로 연산된다. 작업

의 스케줄링 윈도우(scheduling window)는 간격

로 정의된다. 두 개의 작업

및

이 같은 스케줄링 윈도우에 중첩되면 서로 경쟁관계라고 한다.

본 발명에서 설명하는 스케줄링 알고리즘을 SPDF(Smallest Pseudo-Deadline First)라고 명명한다. 각 작업 τ_i는 상대적 가상 마감시간(P_i, relative pseudo-deadline)이라고 불리는 태스크-레벨 파라미터를 갖는다.

작업

는 절대적 가상 마감시간(

)을 갖는다.

는

으로 결정된다. 본 발명에 대한 설명에서 가상 마감시간은 자연수 값을 갖는다고 가정한다. SPDF 알고리즘은 가장 낮은

를 갖는 작업에 가장 높은 우선순위를 부여하는 방식이다. SPDF는 JFP 스케줄링 알고리즘이고, 실제 마감시간 대신 가상 마감시간을 사용한다는 점을 제외하고 전통적인 EDF(Earliest Deadline First) 방식과 유사하다. 가상 마감시간은 실제 작업을 특성을 변경시키지 않고, 작업의 우선순위를 부여하기 위해 사용되는 변수이다.

SPDF 스케줄링 알고리즘

먼저 태스크 간 우선순위 관계를 정의한다. 태스크 쌍 τ_i 및 τ_k가 있다면, 다음과 같은 우선순위 관계가 가능하다.

Type A: 태스크 τ_i의 모든 작업들이 경쟁하는 태스크 τ_k의 작업들보다 우선순위가 높다면 태스크 τ_i가 다른 태스크 τ_k보다 "엄격하게 우선한다(strictly higher)"라고 하고 τ_i

τ_k과 같이 표기한다. 태스크 쌍에 대해 τ_i

τ_k과 같은 관계라면 Type A1이라고 하고, τ_i

τ_k과 같은 관계라면 Type A2라고 명명한다.

Type B: 태스크 의τ_i 어떤 작업들이 경쟁하는 태스크 τ_k의 작업들보다 우선순위가 높지만, 태스크 τ_i의 다른 작업들이 경쟁하는 태스크 τ_k의 작업들보다 우선순위가 낮다면, 두 개의 태스크 τ_i 및 τ_k가 "상호적(mutual)이다"라고 하고, τ_i

τ_k와 같이 표기한다.

도 1은 멀티프로세서 장치에서의 스케줄링 방법에 대한 개략적인 순서도의 예이다.

멀티프로세서 장치에서의 스케줄링 방법은 태스크들이 생성되는 단계(510), 태스크들 중에 하나의 태스크 τ_a에 속하는 작업들이 다른 하나의 태스크 τ_b에 속하는 작업들보다 항상 높은 우선순위를 갖도록 태스크들에 상대적 가상 마감시간을 설정하여 태스크 우선순위를 결정하는 단계(520) 및 태스크에 속하는 작업들에 절대적 가상 마감시간을 설정하여 작업 우선순위를 결정하는 단계(530)를 포함한다.

이하 본 발명의 SPDF 알고리즘에 대한 보조정리(lemma) 및 이에 대한 증명을 살펴본다.

Lemma 1: 어떤 두 개의 태스크 τ_a 및 τ_b가 P_a ≤ P_b - D_b 와 같은 조건을 만족해야만, 두 개의 태스크는 τ_a

τ_b와 같은 관계를 갖는다. Lemma 1에 대한 증명은 발명자가 공개한 논문 "Extending Task-level to Job-level Fixed Priority Assignment and Schedulability Analysis Using Pseudo-deadlines"에 기재되어 있다.

도 2는 어떤 두 개의 태스크 τ_a 및 τ_b가 P_a ≤ P_b - D_b 와 같은 조건을 만족해야만, 두 개의 태스크는 τ_a

τ_b와 같은 관계를 갖는 것을 설명한다. J_x는 태스크 τ_x에 속하는 어느 하나의 작업을 의미한다. Lemma 1은 어떤 태스크 세트에 대해서도 P_a ≤ P_b - D_b라면 SPDF는 τ_a

τ_b라는 우선순위 순서를 유지한다는 것을 보여준다.

Theorem 1: SPDF는 모든 TFP 알고리즘, EDF, EDF-US 및 fp-EDF보다 나은 알고리즘이다. 이에 대한 증명은 발명자가 공개한 논문 "Extending Task-level to Job-level Fixed Priority Assignment and Schedulability Analysis Using Pseudo-deadlines"에 기재되어 있다.

SPDF 스케줄 가능성 분석

본 발명에서 제안한 SPDF에 대한 스케줄 가능성을 분석해보고자 한다. 먼저 EDF 및 TFP 등 다양한 알고리즘에 대한 스케줄 가능성 조건에 대한 기초 도구로 사용되는 간섭 기반 분석(Interference-based Analysis)에 대래 간략하게 설명하고, 간섭 기반 분석의 성능을 향상시키는 DA-LC(Deadline Analysis with Limited Carry-in) 기법에 대해서도 설명하고자 한다. 마지막으로 간섭 기반 분석이 본 발명의 SPDF 알고리즘에 어떻게 적용되는 살펴보고자 한다.

1)간섭 기반 분석: 간격 [a,b)에서 태스크 τ_k에 대한 전체 간섭(total interference)은 태스크 τ_k가 실행될 수 있으나 우선순위가 더 높은 다른 작업 때문에 실행되지 못하는 모든 간격의 누적 길이이다. 여기서 전체 간섭은

로 표기된다.

간격 [a,b)에 존재하는 태스크 τ_k에 대한 태스크 τ_i의 간섭(

로 표기함)은 τ_k가 실행될 수 있으나 τ_i가 실행되고 있기 때문에 실행되지 않는 모든 간격의 누적 길이이다. 태스크는 m개의 다른 태스크가 실행되는 때에는 스케줄링되지 못하기 때문에,

와

의 관계는 M. Bertogna 등이 공개한 논문에 기재한 Lemma 3(M. Bertogna, M. Cirinei, and G. Lipari, "Improved schedulability analysis of EDF on multiprocessor platforms," in ECRTS, 2005.)로부터 추출되고 아래의 수학식 1과 같다.

는 τ_k의 작업들 중에 최대 전체 간섭을 받는 작업을 의미하고, τ_k의 작업에 대한 최악의 전체 간섭(

)은 다음의 수학식 2와 같이 표현된다.

수학식 2는 표기의 편리를 위해 아래의 수학식 3과 같이 정의한다.

상기 정의를 사용하여 종래의 연구는 글로벌 멀티프로세서 스케줄링 알고리즘의 정확한 스케줄 가능성 조건에 대해 연구하였다((M. Bertogna, M. Cirinei, and G. Lipari, "Improved schedulability analysis of EDF on multiprocessor platforms," in ECRTS, 2005. 및 M. Bertogna, M. Cirinei, and G. Lipari, "Schedulability analysis of global scheduling algorithms on multiprocessor platforms," IEEE Transactions on Parallel and Distributed Systems, vol. 20, pp. 553-566, 2009. 참조). 그 내용은 아래의 Lemma 2와 같다.

Lemma 2: 태스크 세트 τ는 모든 태스크 τ_k에 대하여 아래의 수학식 4의 조건을 만족해야 m개의 동일한 프로세서를 갖는 멀티프로세서에서 스케줄링 가능하다.

정확한

를 연산하기 어렵기 때문에 종래의 접근 방법은

의 상한을 유도하였다(T. P. Baker, "Multiprocessor EDF and deadline monotonic schedulability analysis," in RTSS, 2003. 등 참고).

2) DA - LC 분석 기법: 특정 간격 전에 생성되고, 그 간격 내에 마감시간을 갖는 작업은 캐리인(carry-in) 작업이라고 한다. DA-LC 분석 기법은 캐리인 작업의 최대 간섭을 연산하기 위해 도입되었다. DA-LC 분석 기법은 초기 EDF를 위해 개발되었다. 이후 TFP 스케줄링 알고리즘을 위해 연구되었다.

3) SPDF 에 대한 간섭 기반 분석: 전술한 바와 같이 작업 간 우선순위 관계는 A1, A2 및 B로 구분된다. 각각의 태스크 τ_i(≠τ_k)는 τ_k과의 관계에서 세 개의 세트 τ_k ^(A1), τ_k ^(A2) 및 τ_k ^(B) 중 하나에 속하게 된다. τ_i

τ_k이면 τ_k가 τ_k ^(A1)에 속하고, τ_i

τ_k이면 τ_k가 에 τ_k ^(A2)속하고, τ_i

τ_k이면 τ_k가 τ_k ^(B)에 속한다.

Type A1. 먼저

의 상한을 유도하는데 있어서 Type A1 경우를 살펴본다. 일반적으로 DA-LC 기법은 Type A 관계를 갖는 TFP에 적용된다. 이에 SPDF 스케줄링 기법에서도 Type A 관계를 갖는 태스크에 대해 DA-LC 분석을 사용할 수 있는지 검토하기로 한다.

도 3은 두 개의 태스크 세트 τ'와 τ''간의 관계와 각 태스크 세트에 속한 태스크들 τ_i 와 τ_j간의 관계를 도시한다. 태스크 세트 τ'와 τ''가 τ'

τ''인 관계라면, 태스크들 τ_i ∈ τ'과 태스크들인 τ_j ∈ τ''는 τ_i

τ_j이다. 도 3에서 τ₁와 τ₂는 τ₃, τ₄ 및 τ₅에 대해 엄격하게 우선(Type A1)한다.

이제 τ를 두 개의 서로 같은 요소를 공유하지 않는 서브 세트 τ_k ^(A*)와 τ_k ^(B*)를 분할한다. τ_k 관점에서 τ_k ^(B*)는 반드시 τ_k를 포함해야 하고, τ_k ^(A*)

τ_k ^(B*)이다. 이 관계는 τ_k ^(A*) ⊆ τ_k ^(B*)라고 정의되고, τ_k ^(A*)가 보다 나은 스케줄 가능성을 가질 가능성이 크다.

먼저 생성된 어떤 태스크 τ_b ∈ τ_k ^(B*)는 τ_k ^(B*)에 속하는 태스크 사이에서만 우선순위 변경이 가능하다. 그러나 τ_b의 우선순위를 변경하더라도 τ_k ^(A*) 및 τ_k ^(B*)사이의 우선순위 관계는 변동이 없다. 다음의 Lemma 3은 TFP에 적용되는 DA-LC 기법이 τ_k ^(A*)에 적용가능하다는 것을 보여준다.

Lemma 3: SPDF에서 길이

인 간격(interval)에서 τ_k ^(A*)에 속하는 태스크의 작업의 수행량은 τ_k ^(A*)에 속한 태스크의 캐리인 작업이 m-1개 이하인 경우에 최대가된다. Lemma 3에 대한 증명은 발명자가 공개한 논문 "Extending Task-level to Job-level Fixed Priority Assignment and Schedulability Analysis Using Pseudo-deadlines"에 기재된 바와 같다.

TFP에 적용하던 DA-LC 기법을 SPDF에도 적용하자면

연산을 위해 두 개의 서브 케이스를 고려해야 한다.

만약 τ_i ∈ τ_k ^(A1)가 생성시간과 τ_k의 마감시간 사이 간격에 캐리인 작업을 갖고 있다면,

는 길이 D_k인 간격에서 τ_i의 작업의 최대 실행(maximum execution)에 의해 상한이 결정된다. 간격의 길이를

이라고 일반화하면 아래의 수학식 5와 같이 표현된다.

도 4는 SPDF 기법에 대한 간섭 기반 분석에서 서로 다른 경우에 대한 최악의 경우를 도시한 예이다.

태스크 τ_i의 첫 번째 작업이 최대한 늦게 수행될수록 최대 실행에 의해 상한이 결정된다. 도 4(a)에 도시된 바와 같이 그 후 다른 작업들은 즉시 스케줄링된다.

한편 τ_i ∈ τ_k ^(A1)가 간격에 캐리인 작업을 갖지 않는다면,

는 D_k 길이인 간격에서 τ_i의 작업 중 캐리인 작업이 아닌 작업의 최대 수행시간에 의해 상한이 결정된다(

). 간격의 길이를

이라고 일반화하면 아래의 수학식 6과 같이 표현된다.

이 경우 도 4(b)에 도시된 바와 같이 모든 작업이 가능한 빨리 생성되고 스케줄링된다. 길이

> 0에 대하여

이다.

Type A2. Type A2 경우 τ_k는 τ_i로부터 간섭을 받지 않으므로,

= 0이다.

Type B. 이제 τ_i가 τ_k ^(B)에 속하는 경우

에 대한 상한을 유도하기로 한다. τ_i ∈ τ_k ^(B)의

가

와 간섭하는 경우(

가

보다 높은 우선순위 갖는 경우),

이다. 따라서 τ_k의 작업보다 높은 우선순위를 갖는 τ_i의 작업들이 수행되는 시간은 τ_i의 작업의 가상 마감시간이 τ_k의 작업과 동일한 경우 최대가 된다. 즉, τ_i의 작업의 생성 시간과 τ_k의 작업의 생성 시간은 도 4(c)에 도시된 바와 같이 P_k - P_i만큼 떨어져 있다.

이때

는

로 상한이 결정된다.

보다 상한이 크면 안되기 때문에

의 상한은 두 개의 상한 중 작은 것을 사용한다.

의 상한에 대한 내용을 정리한다. PDF의 스케줄 가능성 테스트를 위해 전술한 수학식 4을 사용했다. SPDF에서 SPDF의 상한은 아래의 수학식 7로 표현된다.

이므로, τ_i ∈ τ_k ^(A1)에서 SPDF의 안전한 스케줄 가능성 테스트는

를

에 대한 상한으로 사용하여 유도될 수 있다.

결론적으로 전술한 수학식 7과 Lemma 3을 고려하여, SPDF의 스케줄 가능성 테스트는 다음의 Theorem 2로 유도할 수 있다.

Theorem 2: 태스크 세트 τ는 만약 각 태스크 τ_k가 다음의 수학식 8의 조건을 만족한다면 m 개의 동일한 프로세서를 갖는 멀티프로세서에서 주어진 우선순위 할당

으로 SPDF 하에서 스케줄링 가능하다.

수학식 8의 좌변은 아래의 수학식 9로 상한이 결정된다. 이에 대한 자세한 증명은 발명자가 공개한 논문 "Extending Task-level to Job-level Fixed Priority Assignment and Schedulability Analysis Using Pseudo-deadlines"에 기재된 바와 같다.

최적의 가상 마감시간 할당

도 5는 멀티프로세서 장치에서 가상 마감시간을 이용하여 태스크에 대한 우선순위를 결정하는 방법에 대한 순서도의 예이다.

멀티프로세서 장치에서 가상 마감시간을 이용하여 태스크에 대한 우선순위를 결정하는 방법은 k 단계에서 태스크 세트를 우선순위가 결정된 서브세트(A(k)) 및 k 단계 이후에 우선순위를 결정해야 하는 서브세트(R(k))로 분할하는 단계(610), R(k)에서 가상 마감시간을 할당하기 위한 서브세트 S(k)를 결정하는 단계(620) 및 S(k)에 대한 가상 마감시간을 할당하여 우선순위를 부여하는 단계(630)를 포함한다. 이하 구체적인 설명을 한다.

본 발명은 어떤 태스크 세트 τ의 각 태스크(τ_i∈τ)에 대한 상대적 가상 마감시간(P_i)을 결정하여 상기 태스크 세트 τ가 전술한 Theorem 2에 주어진 SPDF 스케줄 가능성 테스트에 따라 스케줄링되게 하는 것이다.

먼저 TFP 스케줄링을 위한 OPA 알고리즘을 간략하게 살펴보고, OPA 알고리즘을 JFP 스케줄링에 확장가능한지 검토해본다. 마지막으로 OPA 알고리즘을 본 발명의 가상 마감시간에 적용한 OPDA(Optimal Pseudo-deadline assignment) 알고리즘을 설명한다.

1) TFP / OPA: OPA 알고리즘(R. Davis and A. Burns, "Priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems," in RTSS, 2009.)은 전체 태스크 세트 τ는 스케줄링이 가능하도록 반복적인 우선순위를 부여하여 각 개별 태스크에 우선순위를 부여한다.

k 번째 반복적인 단계에서, 태스크 세트 τ는 중복되지 않는 두 개의 서브 세트(A(k) 및 R(k))로 분할된다. A(k)는 k 단계 전에 우선순위가 부여된 태스크의 서브세트이고, R(k)는 k 단계 이후로 우선순위가 부여되는 나머지 태스크의 서브세트이다.

어떤 태스크 τ_e가 우선순위가 부여된 모든 태스크 τ_a ∈ A(k)보다 엄격하게 우선순위가 높고(τ_e

τ_a), 나머지 태스크 τ_r ∈ R(k)보다 엄격하게 우선순위가 낮다(τ_e

τ_r)는 전제하에 τ_e가 스케줄링이 가능하다면, τ_e는 k 단계에서 TFP-적격(TFP-eligible)이 있다. k 단계에서 OPA는 우선순위 부여가 가능한 태스크들 중 하나를 선택한다. 간략하게 설명을 위하여 다음과 같은 표기를 설명한다.

E(k)는 k 단계에서 선택할 수 있는 대상이 되는 태스크의 서브세트를 의미하고, S(k)는 k 단계에서 우선순위 부여를 위해 선택된 태스크의 서브세트를 의미한다(S(k) ⊆ E(k)).

TFP/OPA는 다음과 같은 특징이 있다. 첫째로, 가장 중요한 특징 중 하나는 알고리즘이 백트랙킹(back-tracking) 없이 점진적으로 진행된다는 것이다. 어떤 태스크 τ_s가 반복적 k 단계에서 선택되어도, 반복적인 다음 단계(k+1)에서 태스크 τ_s는 우선순위 부여 효과를 갖지 않는다. 이는 태스크 τ_s가 나머지 다른 태스크 τ_r ∈ R(k+1)보다 엄격하게 낮은 우선순위가 부여되기 때문이다. 둘째로, k 단계에서 오직 하나의 태스크 τ_e만이 적격이 있다고 가정하면, OPA는 반드시 나머지 모든 태스크 R(k)를 검색해서 적격이 있는 하나의 태스크 τ_e를 찾는다. 셋째로, k 단계에서 적격이 있는 복수의 태스크가 있다고 가정하면, k 단계에서 어떤 태스크가 선택되던지 문제되지 않는다. 이는 다른 적격 있는 태스크들이 다른 단계에서도 여전히 적격이 있는 상태이고 결국 이후 단계에서 우선순위 부여를 위해 선택되기 때문이다.

2) JFP 에 대한 OPA 적용가능성: OPA 알고리즘을 JFP 영역에 적용할 수 있는지 검토해본다. TFP와 JFP의 결정적인 차이 중 하나는 전술한 태스크 간 관계 Type B(상호적 관계)가 JFP에서만 유효하다는 것이다. OPA는 TFP를 대상으로 설계되었기 때문에 우선순위 부여에 있어서 Type B 관계를 고려하지 않는다. 따라서 OPA를 JFP로 확장하기 위해서는 Type B에 대한 문제가 해결되어야 한다.

설명을 위해 k 단계에서 TFP 적격이 있는 태스크가 없다고 가정해 본다. 각 태스크 τ_j ∈ R(k)가 남아있는 다른 모든 태스크와 Type A1 관계에 있다는 전제하면, τ_j에 스케줄링을 위한 우선순위 부여를 할 수 없다. 이 관계는 다음의 수학식으로 표현된다.

서로 Type B 관계인 경우에만 스케줄링되는 태스크 쌍 τ_p 및 τ_q가 있다고 가정한다. 이 관계는 다음의 수학식으로 표현할 수 있다.

이와 같은 경우라도, 스케줄링이 가능한 두 개의 태스크 τ_p 및 τ_q가에 작업 레벨의 우선순위 부여가 가능할 수 있다. 그러나, OPA는 반복적인 매 단계에서 하나의 태스크만을 찾기 때문에 우선순위 부여가 불가능하다.

결국 JFP는 Type B 관계인 태스크를 지원할 수 있고, TFP는 Type A 관계인 태스크만을 지원할 수 있다는 한계가 있다. 이에 다음과 같이 JFP 스케줄링을 위한 새로운 우선순위 부여 방식을 고안하게 되었다.

3) OPDA 알고리즘: TFP/OPA 알고리즘을 JFP에 확장한 OPDA(Optimal Pseudo-Deadline Assignment)을 설명한다. OPDA는 OPA의 기본적인 알고리즘을 따르면서 반복적으로 가상 마감시간을 부여한다(Algorithm 1 및 Algorithm 2).

OPDA는 반복전인 k 단계마다 태스크 세트 τ를 공통된 요소를 갖지 않는 두 개의 세트 A(k) 및 R(k)로 분할한다. 분할된 두 개의 세트는 서로 Type A 관계를 유지한다. A(k) 및 R(k) 사이의 강제적인 Type A 관계는 TFP/OPA와 같이 OPDA도 점진적으로 문제를 해결하게 한다(점진적으로 우선순위를 부여함). 반대로 TFP/OPA와 OPDA의 주요한 차이점은 A(k) 및 R(k) 사이의 Type A 관계를 만드는 방법 및 k 번째 단계에서 가상 마감시간을 할당하기 위한 S(k)에서 태스크를 선택하는 방법이다.

A(k) 및 R(k) 사이에 Type A 관계를 갖도록 하는 것이 점진적 우선순위를 부여하는데 중요하다. TFP 경우 서로 다른 태스크에 서로 다른 우선순위를 부여하여 두 개의 서브세트는 쉽게 Type A 관계가 된다. 그러나 JFP 경우 Type A 관계를 갖기 위해서는 두 개의 서브세트를 분할하는 별도의 방법이 필요하다.

전술한 바와 같이, SPDF 스케줄링은 만약 두 개의 태스크가 전술한 Lemma 1에서 요구하는 조건을 만족하면 그 두 개의 태스크는 Type A 관계를 갖는다. 따라서 A(k)에 속하는 모든 태스크 τ_a 및 R(k)에 속하는 모든 태스크 τ_r이 P_a≤P_r-D_r을 만족하도록 상대적인 가상 마감시간을 부여하여 A(k) 및 R(k)는 Type A 관계를 갖게 할 수 있다.

또한 OPDA는 가상 마감시간 할당의 과정에서 Type B 관계를 갖게 된다. 반복적인 매 단계마다 하나의 태스크에 우선순위를 부여하는 TFP/OPA와는 달리 OPDA는 하나의 단계에서 S(k)를 결정하기 위하여 서로 다른 복수의 태스크를 검색하고 서브세트 S(k)에서 태스크들에 대해 Type B 관계를 강제한다.

상기 Algorithm 1에 기재된 바와 같이, OPDA는 k 단계마다 남아 있는 태스크가 없을 때까지 반복적으로 서브세트 S(k)를 찾는다. 각 k 단계에서 가장 작은 크기 i의 서브세트 S(k)를 찾기 위하여 FIND-SUBSET(k,i)란 함수를 실행한다.

상기 Algorithm 2에 기재된 바와 같이, FIND-SUBSET(k,i)는 남아 있는 모든 태스크 R(k)로부터 크기 i인 모든 태스크의 조합(S(k))을 고려한다.

도 6은 OPDA의 k 단계에서 버퍼 영역의 예를 도시한다. 도 6에 도시된 바와 같이, S(k)에 속하는 i 크기 태스크는 A(k)에 속하는 각 태스크와 Type A1 관계를 갖고, S(k)에 속하는 태스크들은 서로 Type A 또는 Type B 관계를 갖고, S(k)에 속하는 태스크는 나머지 R(k)에 속하는 태스크와 Type A2 관계를 갖는다는 전제하에 S(k)에 속하는 크기 i 태스크의 각 조합은 전술한 Theorem 2에 따라 스케줄링이 가능하다.

A(k) 및 R(k) 사이에 Type A 관계 관계를 강제하기 위하여 OPDA는 A(k) 및 R(k) 사이에 버퍼 영역(pseudo-deadline buffer zone) [Z^H(k), Z^L(k)]을 도입한다. 이를 통해 어떤 태스크도 버퍼 영역에 가상 마감시간이 할당되지 못한다(Algorithm 2의 3-6 라인).

Lemma 1에 기술된 Type A 관계의 원칙에 따라 모든 할당된 태스크 τ_a ∈ A(k)는 Z^L(k) 보다 이른(수치적으로는 큰) 가상 마감시간을 갖고, 나머지 태스크 τ_r ∈ R(k+1)는 Z^H(k+1) 보다 늦은(수치적으로는 작은) 가상 마감시간을 갖는다(Algorithm 2의 8-9라인).

버퍼 영역 크기 maxD(k)는 Type A 관계하에 A(k)와 R(k)를 나눌 수 있을 정도로 큰 값을 갖는다. OPDA는 [Z^L(k+1), Z^H(k)]에 존재하는 적격이 있는 모든 태스크 τ_s ∈ S(k)에 대하여 가능한 가상 마감시간을 할당한다(Algorithm 2의 11-22라인).

알고리즘은 크기 i의 태스크 서브세트를 찾는다면 다음 반복 단계로 진행되고, 찾지 못한다면 크기가 하나 더 큰 서브세트의 조합에서 스케줄링 가능한 태스크 서브세트가 있는지 찾는다. 알고리즘은 서브세트의 크기를 하나씩 증가시키면서 조건을 만족하는 서브세트를 찾는다.

Theorem 3: OPDA 알고리즘은 Theorem 2의 SPDF 스케줄 가능성 테스트에 대하여 최적의 가상 마감시간을 할당하는 기법이다. 이에 대한 증명은 발명자가 공개한 논문에 기재한 바와 같다.

본 실시예 및 본 명세서에 첨부된 도면은 본 발명에 포함되는 기술적 사상의 일부를 명확하게 나타내고 있는 것에 불과하며, 본 발명의 명세서 및 도면에 포함된 기술적 사상의 범위 내에서 당업자가 용이하게 유추할 수 있는 변형 예와 구체적인 실시예는 모두 본 발명의 권리범위에 포함되는 것이 자명하다고 할 것이다.

Claims (10)

1. 멀티프로세서 장치에서의 스케줄링 방법에 있어서,
   태스크들(τ_i)이 생성되는 단계;
   상기 태스크들(τ_i) 중에 하나의 태스크 τ_a에 속하는 작업들이 다른 하나의 태스크 τ_b에 속하는 작업들보다 항상 높은 우선순위를 갖도록 상기 태스크들(τ_i)에 상대적 가상 마감시간을 설정하여 태스크 우선순위를 결정하는 단계; 및
   상기 태스크들(τ_i)에 속하는 작업들에 절대적 가상 마감시간을 설정하여 작업 우선순위를 결정하는 단계를 포함하는 멀티프로세서 장치에서의 스케줄링 방법.
2. 제1항에 있어서,
   상기 태스크 우선순위를 결정하는 단계는
   상기 τ_a 및 상기 τ_b가 P_a ≤ P_b - D_b 조건을 만족하도록 상기 상대적 가상마감시간을 설정하는 멀티프로세서 장치에서의 스케줄링 방법.
   (여기서, P_a는 τ_a의 상대적 가상 마감시간, P_b는 τ_b의 상대적 가상 마감시간, D_b는 τ_b의 상대적 마감시간임.)
3. 제2항에 있어서,
   상기 상대적 가상 마감시간은 상기 태스크에 속한 작업이 생성되는 시간부터 상기 작업의 절대적 가상 마감시간까지의 간격이고, 상기 상대적 마감시간은 하나의 작업이 생성되는 시간부터 상기 작업의 절대적 마감시간까지의 간격인 멀티프로세서 장치에서의 스케줄링 방법.
4. 제1항에 있어서,
   상기 작업 우선순위를 결정하는 단계는
   상기 태스크들(τ_i)의 h 번째 작업(

   

   )의 상기 절대적 가상 마감시간(

   

   )이

   

   로 연산되며 가장 작은

   

   를 갖는 작업에 가장 높은 우선순위를 부여하는 멀티프로세서 장치에서의 스케줄링 방법.
   (여기서,

   

   는 상기

   

   가 생성되는 시간이고, P_i는 상기 τ_i의 상대적 마감시간임.)
5. 제1항에 있어서,
   상기 태스크 우선순위를 결정하는 단계는
   상기 태스크들 중에 서로 다른 태스크인 τ_i 및 τ_k가 m개의 동일한 프로세서를 포함하는 멀티프로세서에서 다음 수학식과 같은 간섭 조건을 만족하는 멀티프로세서 장치에서의 스케줄링 방법.
   

   

   
   (여기서,

   

   는 본 발명의 스케줄링 방법에서 태스크 τ_i와 τ_k사이의 간섭, D_k는 태스크의 상대적인 마감시간, C_k는 태스크의 최악의 수행시간임)
6. 멀티프로세서 장치에서 태스크에 대한 우선순위를 결정하는 방법에 있어서,
   k 단계에서 태스크 세트를 우선순위가 결정된 서브세트(A(k)) 및 k 단계 이후에 우선순위를 결정해야 하는 서브세트(R(k))로 분할하는 단계;
   상기 R(k)에서 가상 마감시간을 할당하기 위한 서브세트 S(k)를 결정하는 단계; 및
   상기 S(k)에 속하는 태스크에 대해 서로 다른 가상 마감시간을 할당하여 우선순위를 부여하는 단계를 포함하되,
   상기 S(k)를 결정하는 단계는 상기 R(k)에 속하는 태스크들의 모든 조합을 검토하여 상기 S(k)를 결정하되, 상기 S(k)에 속하는 태스크의 작업들이 모두 상기 A(k)에 속하는 태스크 작업보다 우선순위가 높고, 상기 S(k)에 속하는 태스크의 작업들이 상기 R(k)에 남아있는 태스크의 작업보다 우선순위가 낮도록 결정하는 멀티프로세서 장치에서 가상 마감시간을 이용하여 태스크에 대한 우선순위를 결정하는 방법.
7. 제6항에 있어서,
   상기 A(k)와 상기 R(k)는
   상기 A(k)에 속하는 태스크 τ_a 및 상기 R(k)에 속하는 태스크 τ_r가 P_a ≤ P_r - D_r 조건을 만족하여, 상기 τ_a에 속하는 작업들이 상기 τ_r에 속하는 작업들보다 높은 우선순위를 갖는 멀티프로세서 장치에서 가상 마감시간을 이용하여 태스크에 대한 우선순위를 결정하는 방법.
   (여기서, P_a는 τ_a의 상대적 가상 마감시간, P_r는 τ_r의 상대적 가상 마감시간, D_r는 τ_r의 상대적 마감시간임.)
8. 삭제
9. 제6항에 있어서,
   상기 A(k)와 R(k)의 사이의 시간에 버퍼 영역이 위치하고, 상기 버퍼 영역 내에는 가상 마감시간이 할당되지 않는 멀티프로세서 장치에서 가상 마감시간을 이용하여 태스크에 대한 우선순위를 결정하는 방법.
10. 제6항에 있어서,
    상기 S(k)를 결정하는 단계는
    상기 S(k)에 속하는 태스크들 중 서로 다른 태스크인 τ_i 및 τ_k가 m개의 동일한 프로세서를 포함하는 멀티프로세서에서 다음 수학식과 같은 간섭 조건을 만족하는 멀티프로세서 장치에서 가상 마감시간을 이용하여 태스크에 대한 우선순위를 결정하는 방법.
    

    

    
    (여기서,

    

    는 태스크 τ_i와 τ_k사이의 간섭, D_k는 태스크의 상대적인 마감시간, C_k는 태스크의 최악의 수행시간임)

Images