(19) 대한민국특허청(KR) (12) 공개특허공보(A)
(11) 공개번호 10-2013-0050661 (43) 공개일자 2013년05월16일 (51) 국제특허분류(Int. Cl.)
G06F 9/50 (2006.01) G06F 9/46 (2006.01) (21) 출원번호 10-2011-0115854
(22) 출원일자 2011년11월08일 심사청구일자 없음
(71) 출원인
한국전자통신연구원
대전광역시 유성구 가정로 218 (가정동) (72) 발명자
김상철
경상북도 경산시 백천동 571-1 부영초록마을 101 동 1504호
우덕균
대전광역시 서구 대덕대로 415, 106동 602호 (만 년동, 상아아파트)
(뒷면에 계속) (74) 대리인
특허법인우인 전체 청구항 수 : 총 8 항
(54) 발명의 명칭 실시간 운영체제에서 태스크 스케줄링 방법
(57) 요 약
본 발명은 임베디드 시스템에 탑재되는 실시간 운영체제(RTOS)에서 태스크 스케줄링 방법에 관한 것으로서, 프로 그래머에게 태스크에 대한 CPU 예약을 가능하게 하는 태스크 스케줄링 방법에 관한 것이다. 이러한 본 발명에 따 른 실시간 운영체제에서 태스크 스케줄링 방법은, 스케줄링 시점이 되면 대기 큐에 존재하는 태스크들 중에 가장 높은 우선순위가 미리 정해진 K인지 판단하는 단계; 가장 높은 우선순위가 K라고 판단되면 예약 기반 스케줄러를 적용하여 스케줄링하는 단계; 및 가장 높은 우선순위가 K가 아니라고 판단되면 우선순위 기반 스케줄러를 적용하 여 스케줄링하는 단계; 를 포함하며, 상기 대기 큐에 존재하는 태스크들 중에 우선순위가 K인 태스크는 생성될 때 인자로서 받은 유휴 CPU 예약 할당량 정보를 포함한다.
대 표 도
- 도2(72) 발명자 신규상
대전광역시 유성구 배울2로 42, 507동 1302호 (관 평동, 대덕테크노밸리5단지아파트)
마평수
대전광역시 유성구 하기동 송림마을아파트 107동 1403호
김선태
대전광역시 유성구 하기동 송림마을 5단지 507동 1503호
특허청구의 범위
청구항 1스케줄링 시점이 되면 대기 큐에 존재하는 태스크들 중에 가장 높은 우선순위가 미리 정해진 K인지 판단하는 단 계;
가장 높은 우선순위가 K라고 판단되면 예약 기반 스케줄러를 적용하여 스케줄링하는 단계; 및
가장 높은 우선순위가 K가 아니라고 판단되면 우선순위 기반 스케줄러를 적용하여 스케줄링하는 단계;
를 포함하며,
상기 대기 큐에 존재하는 태스크들 중에 우선순위가 K인 태스크는 생성될 때 인자로서 받은 유휴 CPU 예약 할당 량 정보를 포함하고 있는 것을 특징으로 하는 실시간 운영체제에서 태스크 스케줄링 방법.
청구항 2
제 1 항에 있어서, 상기 스케줄링 시점은 새로운 태스크가 대기 큐에 들어오거나, 현재 실행하던 태스크가 종료 되거나, 타이머가 만료된 때인 것을 특징으로 하는 실시간 운영체제에서 태스크 스케줄링 방법.
청구항 3
제 1 항에 있어서, 상기 예약 기반 스케줄러를 적용하여 스케줄링하는 단계는,
라운드(round) 시간이 설정되어 있지 않은 경우에 1 라운드에 대한 시간을 설정하는 단계;
우선순위가 K인 태스크들 중에서 유휴 CPU 예약 할당량 정보를 가지는 태스크들의 집합 TCPU와, 유휴 CPU 예약 할당량 정보를 가지지 않는 태스크들의 집합 TG를 설정하는 단계; 및
상기 TCPU에 속하는 태스크에 유휴 CPU를 할당한 후에, 상기 TG에 속하는 태스크에 휴유 CPU를 할당하는 단계;
를 포함하며,
상기 유휴 CPU는 우선순위가 K보다 높은 태스크의 CPU 점유율을 제외하고 우선순위가 K인 태스크들이 사용할 수 있는 남은 CPU의 양인 것을 특징으로 하는 실시간 운영체제에서 태스크 스케줄링 방법.
청구항 4
제 3 항에 있어서, 상기 TCPU에 속하는 태스크를 할당하는 단계는,
상기 TCPU에 속한 태스크 중에서 유휴 CPU 예약 할당량 값이 가장 높은 태스크를 선택하는 단계;
상기 선택 단계에서 선택된 태스크에 대해 타이머 값을 유휴 CPU 예약 할당량 값과 동일하도록 설정하는 단계;
상기 선택 단계에서 선택된 태스크를 실행하는 단계;
상기 선택 단계에서 선택된 태스크의 실행이 타이머가 만료되기 전에 끝났다면, 라운드 시간에서 태스크의 실행 시간을 제하고 타이머 작동을 중지시킨 후에 해당 태스크를 TCPU에서 제거하고, 반면에 상기 선택 단계에서 선택 된 태스크의 실행이 끝나기 전에 타이머가 만료되었다면, 라운드 시간에서 해당 태스크의 유휴 CPU 예약 할당량 값을 제하고 타이머 작동을 중지시킨 후에 해당 태스크를 TCPU에서 제거하는 단계; 및
스케줄링을 수행한 후에, TCPU에 태스크가 존재하는지 판단하여, 존재하면 선택하는 단계부터 차례로 다시 수행 하고, 존재하지 않으면 종료하는 단계;
를 포함하는 것을 특징으로 하는 실시간 운영체제에서 태스크 스케줄링 방법.
청구항 5
제 4 항에 있어서, TCPU에 속한 태스크 중에서 유휴 CPU 예약 할당량 값 CPU(ti)이 가장 높은 태스크를 선택하는 단계에서, CPU(ti) 값이 동일한 태스크가 두 개 이상이면 임의로 한 태스크를 선택하는 것을 특징으로 하는 실 시간 운영체제에서 태스크 스케줄링 방법.
청구항 6
제 4 항에 있어서, 상기 TG에 속하는 태스크에 휴유 CPU를 할당하는 단계는, 상기 TG에 속하는 태스크들 중에 첫 번째 태스크를 선택하는 단계;
라운드 시간이 미리 정해진 값 p보다 크거나 p와 동일하면 타이머 값을 p로 설정하고, 라운드 시간이 p보다 작 으면 타이머 값을 라운드 시간과 동일하도록 설정하는 단계;
상기 첫 번째 태스크 선택 단계에서 선택된 태스크를 실행하는 단계;
상기 첫 번째 태스크 선택 단계에서 선택된 태스크의 실행이 타이머가 만료되기 전에 끝났다면, 라운드 시간에 서 태스크의 실행 시간을 제하고 타이머의 작동을 중지시킨 후에 해당 태스크를 TG에서 제거하고, 반면에 상기 첫 번째 태스크 선택 단계에서 선택된 태스크의 실행이 끝나기 전에 타이머가 만료되었다면, 라운드 시간에서 p 를 빼고 해당 태스크는 TG의 마지막에 배치하는 단계; 및
스케줄링을 수행한 후에, TG에 태스크가 존재하는지 판단하여, 존재하면 상기 첫번째 태스크 선택 단계부터 차례 로 다시 수행하고, 존재하지 않으면 종료하는 단계;
를 포함하는 것을 특징으로 하는 실시간 운영체제에서 태스크 스케줄링 방법.
청구항 7
제 6 항에 있어서, 상기 첫 번째 태스크 선택 단계에서 선택된 태스크를 실행하는 단계를 수행하는 도중에 K보 다 높은 우선순위의 태스크가 대기 큐로 들어오는 경우에는, K보다 높은 우선순위의 태스크를 먼저 실행한 후에 복귀하여 실행하는 것을 특징으로 하는 실시간 운영체제에서 태스크 스케줄링 방법.
청구항 8
제 7 항에 있어서, 상기 첫 번째 태스크 선택 단계에서 선택된 태스크를 실행하는 단계를 수행하는 도중에 K보 다 높은 우선순위의 태스크가 대기 큐로 들어오는 경우에는 타이머 값을 임시로 다른 변수에 저장했다가 이후에 복귀할 때 상기 변수에 저장된 값을 복귀시키는 것을 특징으로 하는 실시간 운영체제에서 태스크 스케줄링 방법.
명 세 서 기 술 분 야
본 발명은 임베디드 시스템에 탑재되는 실시간 운영체제(RTOS)에서 태스크 스케줄링 방법에 관한 것으로서, 프 [0001]
로그래머에게 태스크에 대한 CPU 예약을 가능하게 하는 태스크 스케줄링 방법에 관한 것이다.
배 경 기 술
임베디드 시스템에서 탑재되는 대부분의 실시간 운영체제에서는 우선순위를 기반으로 하는 선점형 태스크 스케 [0002]
줄링 방법을 적용한다. 그리고, 우선순위가 동일한 경우에는 먼저 도착한 태스크를 먼저 실행하는 라운드로빈 태스크 스케줄링 방법을 적용한다. 이와 같이 선점형 라운드로빈 태스크 스케줄링 방식은 프로그래머에게 직관 적인 형태이기 때문에 보편적으로 많이 사용되어 왔다.
하지만, 우선순위 기반의 스케줄링 방식이 항상 최고의 해결책은 아니다. 특히, 높은 우선순위의 태스크의 실행 [0003]
시간이 매우 길면 낮은 우선순위의 태스크는 높은 우선순위의 태스크의 실행이 끝날 때까지 기다려야하므로 낮 은 우선순위의 태스크는 실행되지 않을 가능성이 있다. 프로그램을 작성하다 보면 태스크의 실행 시간이 길어지 는 경우가 생기며 심지어 무한 루프를 수행하는 경우도 발생한다. 따라서, 프로그래머는 긴급하게 실행해야 하
는 경우를 제외하고는 태스크의 우선순위를 정하는 것 자체가 그다지 반가운 것은 아니다.
우선순위 기반의 문제점을 해결하기 위하여 고안된 것이 라운드로빈 스케줄링이다. 시간 분할을 통해서 태스크 [0004]
들의 수행시간이 길어지거나 블록(block)되더라도 각 태스크들이 실행될 수 있는 기회를 균등하게 제공한다. 이 경우에 태스크의 수가 n개이고 n개가 라운드로빈 형태로 수행된다면 1개의 태스크의 CPU 점유율은 1/n이 되므로, CPU를 유용하게 사용할 수 없는 문제점이 있다.
발명의 내용 해결하려는 과제
본 발명은 상기와 같은 종래의 문제점을 해결하기 위한 것으로서, 본 발명의 목적은 태스크 스케줄링을 함에 있 [0005]
어서 태스크 우선순위가 다른 경우에는 우선순위 기반의 스케줄링을 적용하고 태스크 우선순위가 동일한 경우에 는 시간분할 기반의 스케줄링을 적용하고 CPU 할당 비율을 지정(예약)하는 경우에는 가능한 그만큼 할당받을 수 있도록 함으로써, 프로그래머에게 더 많은 스케줄링 자유도를 주는 것이다.
과제의 해결 수단
상기와 같은 목적을 달성하기 위한 실시간 운영체제에서 태스크 스케줄링 방법은, 스케줄링 시점이 되면 대기 [0006]
큐에 존재하는 태스크들 중에 가장 높은 우선순위가 미리 정해진 K인지 판단하는 단계; 가장 높은 우선순위가 K 라고 판단되면 예약 기반 스케줄러를 적용하여 스케줄링하는 단계; 및 가장 높은 우선순위가 K가 아니라고 판단 되면 우선순위 기반 스케줄러를 적용하여 스케줄링하는 단계; 를 포함하며, 상기 대기 큐에 존재하는 태스크들 중에 우선순위가 K인 태스크는 생성될 때 인자로서 받은 유휴 CPU 예약 할당량 정보를 포함하고 있는 것을 특징 으로 한다.
발명의 효과
상기와 같은 본 발명은, 태스크 스케줄링을 함에 있어서 태스크 우선순위가 다른 경우에는 우선순위 기반의 스 [0007]
케줄링을 적용하고 태스크 우선순위가 동일한 경우에는 시간분할 기반의 스케줄링을 적용하고 CPU 할당 비율을 예약하는 경우에는 가능한 그만큼 할당받을 수 있도록 함으로써, 프로그래머에게 더 많은 스케줄링 자유도를 줄 수 있는 효과가 있다. 따라서, 본 발명은 실시간 태스크의 경우에 CPU 사용을 프로그래머가 제어할 수 있게 함 으로써 연성 실시간 응용을 구현하는데 기존의 스케줄링 방식보다 유리한 효과가 있다.
도면의 간단한 설명
도 1은 본 발명의 바람직한 실시예에 따른 실시간 운영체제에서 태스크 스케줄링 방법에 있어서 우선순위 K인 [0008]
태스크에 대한 유휴 CPU의 양을 설명하기 위한 도면.
도 2는 본 발명의 바람직한 실시예에 따른 실시간 운영체제에서 태스크 스케줄링 방법의 전체 알고리즘을 도시 한 도면.
도 3은 본 발명의 바람직한 실시예에 따른 실시간 운영체제에서 태스크 스케줄링 방법에 있어서 1 라운드의 예 를 도시한 도면.
도 4는 본 발명의 바람직한 실시예에 따른 실시간 운영체제에서 태스크 스케줄링 방법에 있어서 TCPU에 속한 태 스크를 할당하는 알고리즘을 도시한 도면.
도 5는 본 발명의 바람직한 실시예에 따른 실시간 운영체제에서 태스크 스케줄링 방법에 있어서 TG에 속한 태스 크를 할당하는 알고리즘을 도시한 도면.
도 6은 본 발명의 바람직한 실시예에 따른 실시간 운영체제에서 태스크 스케줄링 방법에 있어서 TK에 속한 태스
크 실행 도중에 우선순위가 K보다 더 높은 태스크가 들어올 경우에 대하여 설명하기 위한 도면.
도 7a와 도 7b는 본 발명의 바람직한 실시예에 따른 실시간 운영체제에서 태스크 스케줄링 방법에 따른 예약 기 반 스케줄링을 수행할 때와 그렇지 않을 때를 비교하기 위한 도면.
발명을 실시하기 위한 구체적인 내용
이하, 첨부한 도면을 참조하여 본 발명의 바람직한 실시예에 따른 실시간 운영체제에서 태스크 스케줄링 방법에 [0009]
대하여 설명한다.
본 발명에 대한 구체적인 설명에 앞서, 기본 가정에 대하여 설명하면 다음과 같다.
[0010]
● 기본 가정 [0011]
1) 운영체제는 여러 개의 우선순위를 제공하며, 모든 태스크는 우선순위를 갖고있다. 우선순위가 높은 태스크는 [0012]
우선순위가 낮은 태스크보다 실행 순위가 우위에 있다. 우선순위가 X인 태스크들의 집합을 Tx라고 정의한다. 특 정 태스크 ti의 우선순위 값을 Prio(ti), ti∈Tx로 표기한다. 본 발명 전체에서, 우선순위 값이 큰 것이 우선순 위가 높다고 가정한다(Positive 방식).
2) 운영체제가 제공하는 우선순위 중에서 특정 1개의 우선순위(예를 들어 K)는 여러 개의 태스크를 가질 수 있 [0013]
으며, K를 제외한 나머지 우선순위들은 1개의 태스크만을 가질 수 있다.
3) 우선 순위 K는 여러 개의 태스크를 가지며(Tk={T1,...,Tn}), 동일한 우선순위 태스크들은 시간 분할 방식으로 [0014]
실행된다.
4) 태스크는 한번 실행되면 언젠가는 종료되는 one-time-execution 형태가 있으며, 영원히 끝나지 않고 계속 실 [0015]
행되는 forever-loop 형태가 있다.
5) 시스템에서 대부분의 태스크들은 우선 순위가 K이며, 몇몇 긴급한 태스크들은 우선순위가 K보다 높다. 긴급 [0016]
한 태스크들은 one-time-execution 형태이다.
6) 우선순위가 K보다 높은 태스크들의 CPU 점유율의 합을 Z(%)라고 하면 우선순위가 K인 태스크들이 사용할 수 [0017]
있는 유휴 CPU의 양은 (100-Z)(%)이다. 이것을 K에 대한 유휴 CPU 양이라 정의한다.
참고) 우선순위가 K인 태스크들이 사용할 수 있는 남은 CPU의 양을 유휴 CPU 양이라고 정의한다. 이와 같은 유 [0018]
휴 CPU 양은 도 1의 "우선순위 K보다 높은 태스크의 CPU 점유율" 부분을 제외한 부분이다. 앞으로, 유휴 CPU 할 당량은 이 유휴 CPU 양을 100% 기준으로 하여 계산한다. 즉, 유휴 CPU 할당량이 30%이면 실제로는 0.3*(100- Z)가 된다. 여기서, Z(%)는 우선순위 K보다 높은 태스크들의 CPU 점유율의 합이다.
7) 스케줄링(문맥교환) 시점은 스케줄링 타이머가 만료될 때와 태스크가 종료될 때와 새로운 태스크가 활성화될 [0019]
때와 태스크 실행 중 명시적으로 스케줄링 명령어를 호출할 때이다.
● 태스크 생성 [0020]
1) 태스크는 생성될 때 우선순위와 유휴 CPU 예약 할당량을 인자로 받는다. 우선순위가 K가 아닐 경우에는 이 [0021]
유휴 CPU 예약 할당량은 반드시 NULL이어야 하며, 우선순위가 K일 경우에는 유휴 CPU 예약 할당향을 10(%), 20(%)와 같이 인자를 줄 수 있고, 만일 예약이 필요치 않을 경우에는 0을 줄 수 있다.
예1) task_create(tid1, stack_size, priority = K, 10) ← 10% 예약 [0022]
예2) task_create(tid2, stack_size, priority = K+1, 0) ← 예약 불필요 [0023]
예3) task_create(tid3, stack_size, priority = K, 0) ← 예약 불필요 [0024]
2) 우선순위 K인 태스크에 대해 유휴 CPU 예약 할당량은 0보다 크고 100보다 작거나 같은 정수 값이다. 우선순 [0025]
위 K인 태스크들의 모든 유휴 CPU 예약 할당량의 합은 100(%)를 넘으면 안 된다. 특정 태스크 ti의 유휴 CPU 예 약 할당량은 CPU(ti), ti∈tk로 표기한다.
● 본 발명의 전체 알고리즘 [0026]
본 발명에 따른 실시간 운영체제에서 태스크 스케줄링 방법의 전체 알고리즘은 도 2와 같다. 대상 태스크는 스 [0027]
케줄링 시점에서 현재 실행 중인 태스크와 준비중인 태스크들의 집합이다. 스케줄링 시점은 스케줄링이 되는 순 간을 의미하는 것으로서, 새로운 태스크가 대기 큐에 들어오거나 현재 실행하던 태스크가 종료되거나 또는 (시 간 분할 기반 스케줄링에서) 시간 만료 타이머가 만료될 때이다.
스케줄링 시점이 되면, 일단 대기 큐(Ready Queue)에 존재하는 태스크들 중에 가장 높은 우선순위를 조사하여 [0028]
그것이 K인지를 살핀다.(S101, S102)
만약, 가장 높은 우선순위가 K가 아니라면 우선순위 기반 선점형 스케줄러를 적용한 후에 스케줄링을 한다. 이 [0029]
경우에는 같은 우선순위를 갖는 여러 개의 태스크가 존재하지 않기 때문에, 대상 태스크들 중에서 가장 높은 우 선 순위의 태스크를 CPU에 할당하면 된다.( ) 여기서, ti는 대상 태스크들 중에서 가장 높 은 우선순위 태스크이다.(S103, S105)
반면에, 만약 가장 높은 우선순위가 K라면 예약 기반 스케줄러를 적용한 후에 스케줄링을 한다.(S104, S105) 예 [0030]
약 기반 스케줄러와 관련해서 상세히 설명하면 다음과 같다.
이하에서 설명함에 있어서, TK에 속한 태스크 중에서 유휴 CPU 예약 할당량을 갖는 태스크들의 집합을 TCPU, 유휴 [0031]
CPU 예약 할당량을 가지지 않는 태스크들의 집합을 TG라 하겠다.(TCPU,TG⊂TK, TCPU∪TG=TK, TCPU∩TG=Ø).
TK에 속한 태스크들을 스케줄링하기 위해 일정한 간격으로 시간 분할을 한다. 시간 분할은 시스템에서 제공하는 [0032]
시간 만료 타이머를 이용하여 수행이 가능하다.
예약 기반의 스케줄링을 위해서 1 라운드(round)를 설정한다. 1 라운드는 유휴 CPU 양을 예약할 때 고려하는 윈 [0033]
도우이다. 1 라운드는 특정한 시간 값으로 설정할 수 있으나, 리눅스 운영체제의 스케줄링 문맥교환 시간을 고 려해 보았을 때 도 3처럼 100[ms]가 바람직하다.
● 예약 기반 스케줄링에서 초기화 과정 [0034]
1) 라운드 시간이 설정되어 있지 않은 경우에, 1 라운드에 대한 시간을 설정한다.(도 4의 S201) [0035]
2) TCPU,TG를 설정한다.
[0036]
초기화 과정 후에는, TCPU에 속한 태스크를 1 라운드에 할당하고, 이후에 TG에 속한 태스크를 할당한다. 이하에서 [0037]
는, TCPU에 속한 태스크를 할당하는 알고리즘을 도 4를 참조하여 설명하고, TG에 속한 태스크를 할당하는 알고리 즘을 도 5를 참조하여 설명한다. 이하에서 TCPU에 속한 태스크를 할당하는 알고리즘을 설명함에 있어서 설명의 편의를 위하여 라운드 시간이 100[ms]인 경우를 예로 하였으나, 본 발명이 이에 한정되는 것은 아니다.
● TCPU에 속한 태스크를 할당하는 알고리즘 [0038]
먼저, TCPU에 속한 태스크 중에서 유휴 CPU 예약 할당량 CPU(ti) 값이 가장 높은 태스크를 선택한다. 만일 [0039]
CPU(ti) 값이 동일한 태스크가 여러 개이면 그 중에서 임의로 한 태스크(ti∈TCPU)를 선택한다.(도 4의 S202) 다음으로, 타이머를 설정한다(Ttimer=CPU(ti)). 타이머는 1[ms]가 지날 때마다 1씩 감소한다.(S203)
[0040]
다음으로, 태스크 ti(ti∈TCPU)를 실행한다.(S204) [0041]
다음으로, 타이머가 만료되기 전에 할당된 태스크의 실행이 끝났다면, 라운드 시간에서 태스크의 실행 시간을 [0042]
제하고 타이머 작동을 중지시킨다. 즉, Tround'=Tround-(CPU(ti)-ttimer)으로 설정한다. 그리고, TCPU에서 태스크를 제 거한다(즉, TCPU'=TCPU-{ti}). 이후에, 스케줄링을 수행하여 다른 태스크를 실행한다.(S205, S206, S209, S210, S211)
반면에, 태스크의 실행이 끝나기 전에 타이머가 만료되었다면, 유휴 CPU 예약 할당량을 모두 사용하였다는 의미 [0043]
이므로 Tround'=Tround-CPU(ti)가 되며, TCPU에서 태스크를 제거한다(즉, TCPU'=TCPU-{ti}). 그리고, 타이머의 작동을 중지시킨다. 이후에, 스케줄링을 수행하여 다른 태스크를 실행한다.(S207, S208, S209, S210, S211)
다음으로, TCPU에 태스크가 존재하는지 판단하여(S212), TCPU에 태스크가 존재하지 않을 때까지 상술한 단계들을 [0044]
반복한다.
상술한 단계들을 통하여 TCPU에 속한 태스크를 모두 할당하고 난 후에 Tround>0인 경우에는 남은 시간만큼 TG에 속 [0045]
한 태스크를 할당하는 것이 가능하다. TG에 속한 태스크는 리스트형태로 되어 있다고 가정하고 각 태스크를 할당 하는 알고리즘에 대하여 도 5를 참조하여 설명하면 다음과 같다. 이때, 각 태스크가 사용할 수 있는 최대 시간 은 10[ms]라고 가정한다.
● TG에 속한 태스크를 할당하는 알고리즘 [0046]
먼저, TG에 속한 태스크 중에 첫 번째 태스크 ti(ti∈TCPU)를 선택한다.(S301) [0047]
다음으로, 타이머를 설정한다. 이때, Tround≥10이면 Ttimer=10으로 설정하고, Tround<10이면 Ttimer=Tround로 [0048]
설정한다. 타이머는 1[ms]가 지날때마다 1씩 감소한다.(S302) 다음으로, 태스크 ti(ti∈TG)를 실행한다.(S303)
[0049]
다음으로, 타이머가 만료되기 전에 할당된 태스크의 실행이 끝났다면, 라운드 시간에서 태스크의 실행 시간을 [0050]
제하고(즉, Tround'=Tround-(10-Ttimer)), TG에서 태스크를 제거하고(즉, TG'=TG-{ti}), 타이머의 작동을 중지시킨다.
이후에, 스케줄링을 수행한다.(S304, S305, S308, S309, S310)
반면에, 태스크의 실행이 끝나기 전에 타이머가 만료되었다면, 태스크 실행 가능 시간 10[ms]를 모두 사용하였 [0051]
다는 의미이므로 Tround'=Tround-10가 되며, Ti는 TG 리스트에서 맨 마지막에 붙는다. 이후에, 타이머의 작동을 중 지시키고, 스케줄링을 수행한다.(S206, S307, S308, S309, S310)
다음으로, TG에 태스크가 존재하는지 판단하여(S311), TG에 태스크가 존재하는 한 Tround=0이 될 때까지 상술한 [0052]
단계들을 반복 수행하며, Tround=0이 되면 다음 라운드가 시작되게 된다. 할당되지 못한 태스크들은 다음 라운드 에서 할당될 수 있다.
그리고, Tround>0이지만 TG에 태스크가 존재하지 않는 경우에는, Ttimer=Tround로 설정하고 스케줄링을 수행하며, 더 [0053]
낮은 우선순위의 태스크에게 CPU 제어권을 넘겨준다. 타이머가 완료되고 Tround=0이 되면 다음 라운드가 시작되게 된다.
●TK에 속한 태스크 실행 도중에 K보다 더 높은 우선순위의 태스크가 들어올 경우 [0054]
우선순위가 K보다 높은 태스크가 들어오면 우선순위 기반 스케줄러가 적용되어 우선순위가 K보다 높은 태스크가 [0055]
먼저 실행된다.
우선순위가 K보다 높은 우선순위의 태스크가 모두 실행된 후에 다시 우선순위가 K인 태스크로 복귀할 시에는 타 [0056]
이머 값에 세심하게 신경 써야 한다. 즉, 도 6과 같이, 우선순위가 더 높은 태스크가 들어와서 스케줄링이 일어 날 때, Ttimer값을 임시로 다른 변수에 저장했다가(X=Ttimer) 다시 복귀할 때 그 값을 복귀시킨다(Ttimer=X). 또한, 인터럽트가 발생하면 인터럽트 처리가 끝날 때까지 Ttimer값은 정지해야 한다.
이하, 본 발명의 이해를 돕기 위해 예제를 제시한다. 아래에 제시하는 예제를 통해서 본 발명에서와 같이 예약 [0057]
기반 스케줄링을 수행할 때(도 7a)와 종래의 경우와 같이 예약 기반 스케줄링을 수행하지 않았을 때(도 7b)의 비교 결과를 알 수 있다.
예제) TK={t1, t2, t3, t4, t5}이고, t1은 오디오 태스크, t2는 비디오 태스크, t3은 시스템 모니터링 태스크, t4
[0058]
는 이벤트 대기 태스크, t5는 패킷 송수신 태스크이며, TCPU={t1, t2}, TG={t3, t4, t5}, CPU(t1)=30, CPU(t2)=20, TK의 태스크들은 실행이 끝나지 않는(forever-loop) 태스크들이라고 가정한다. TCPU의 태스크들인 t1, t2는 실시 간 태스크들이며, TG의 태스크들인 t3, t4, t5는 비실시간 태스크들이다.
도 7a 및 도 7b를 참조하면, 본 발명에서와 같이 예약 기반 스케줄링을 수행할 경우에는 t1을 40[ms]만큼 수행 [0059]
하는데 110[ms]가 걸리지만, 종래의 경우와 같이 라운드 로빈 스케줄링을 수행할 경우에는 t1을 40[ms]만큼 수 행하는데 160[ms]가 걸린다. 이와 같이, 실시간 태스크는 원하는 마감 시간 내에 태스크를 수행하는 것이 목적
이므로 예약 기반 스케줄링 방식을 사용하면 실시간 태스크의 원하는 마감시간 및 수행시간을 맞출 가능성을 높 일 수 있다.
