선점형 커널은 ISR 에서 복귀 한 후에 스케쥴러가 CPU 점유권을 최상위 우선순위를 갖는 테스크에게 넘겨준다고 했었습니다.

그!런!데!!!!!!

도대체 이놈의 스케쥴러가 어떻게 최상위 우선순위 Task 를 검출해 낼까요?

여러가지 알고리즘이 있을수 있지만, 제가 공부하는 uC/OS 에서 소개하는 알고리즘을 하나 소개해 드리지요 ㅋ

컴마스터인 신태민 교수님께서 OS 도입 초창기에 이 알고리즘을 보신 후에 감탄을 금치 못하셨다는 후문이 ㅋㅋ

우선순위가 255까지 있는 커널이 있다고 가정합니다.

낮은 숫자가 우선순위가 높다고 가정하고 가장 높은 우선순위를 찾아봅시다.

혹자는 이렇게 생각 할 수 도 있겠지요.

"야 그거 Ready 상태에 있는 Task 다 검색해서 정렬 쭈욱 한다음에 제일 높은 우선순위 찾으면 되는거 아냐?"

그렇게 해도 됩니다.

다만, 여기서 소개할려는 알고리즘이 굉장히 Simple 하고 멋있고 세련되고 빠른 방법이기에 소개하려는 것이지요 ㅋ

(1) 각 우선순위를 8열로 나누어 정렬한다
(2) OSRdyGrp 이라는 1byte 변수를 만들고, 이 변수의 각 비트는 각각의 행을 대표한다.
(3) 각 그룹의 8개의 Task 들 중에서 하나라도 Ready 상태가 되면 OSRdyGrp 의 해당 비트를 1 로 Set 한다.
     이 변수를 만들기위해 검색을 하는 과정에서 각 그룹별로도 각각의 우선순위에 해당하는 Task 가 Ready 상태이면 1, 아니면 0 으로 하여 OSRdyTble[] 이라는 배열의 맴버 변수들의 값을 채워 넣는다.


(4) 이렇게 해서 완성된 OSRdyGrp 라는 변수를 OSUnMapTlb[] 라는 LookUp Table 에 대입하여 값을 얻는다.


이 테이블은 0~255 의 숫자를 Binary 로 표시할때 제일 먼저 1이 나오는 bit 의 순서를 써 놓은 것이다.

(5) (4) 에서 나온 결과값을 OSRdyTlb[index] 의 index 값으로 사용하여 OSRdyTlb[index] 값을 얻어낸다.

(6) 다시 OSUnMabTlb[OSRdyTlb[index]] 로 다시 Look-Up Table 의 값을 얻어낸다.



(7) (4)에서 여러분이 얻어낸 값은 "몇번째 그룹에서 최고 우선순위를 갖는 Task 가 Ready 상태인가? " 이고
     (6)에서 여러분이 얻어낸 값은 "해당되는 그룹에서 몇번째 순서의 Task가 Ready 되어있는 상태중에 최고 우선순위인가?" 이다.


(8) 즉, Ready 상태에 있는 최고 우선순위를 최종적으로 알아내기 위해서는

( (4)번 결과 << 3 ) + (6)번 결과

이다. 여기서 좌로 3비트 쉬프트 시킨 이유를 그룹을 8개씩으로 끊어 놓았기 때문이다. (2의 3승)


이해가 되시나요??

한번 스윽 읽어보는것만으로는 잘 이해가 안되실 것입니다.
저도 직접 구현해보기 전에는 신기하기만 할 뿐이였으니까요 ㅋㅋ

포스팅전에 확실하게 이해하기 위해서 제가 방금 1시간을 투자해서 위의 알고리즘을 구현해보았습니다.


보이시나요? 잘 찾아내지요?

체크되어있는 것들이 Ready 상태입니다. ㅋ

하나도 체크가 안되어있으면 레디상태인 테스크가 없다라고 메시지가 뜹니다.

어떻게 아냐구요??

if (OSRdyGrp == 0) 겠지용?? ㅋㅋ

아래는 제가 C# 으로 간단하게 구현해 놓은 프로젝트 입니다.

참고하실분을 받아서 보시길 바랍니다.

Visual Studio 2010 SP1 으로 제작된 것이니, 프로젝트 안열리시는 분들은 그냥 .cs 파일에서 알고리즘만 간단하게 보시기 바랍니다.

따로 다중 클래스화 시키지 않았으니 무리없이 보실수 있을 것입니다.

그럼 바이바이

Posted by J.Bear