선점형 커널은 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
이제 슬슬 RTOS 의 핵심으로 들어가고 있습니다.

시작하기 전에 사진 한 컷! 이것은 현재 저의 입천장 사진입니다.

사실 요전 4일동은 39도가 넘는 고열에 시달리며 새해를 맞이했지용.

응급실에서 주사를 맞으면서 ㅋㅋ

태어나서 이렇게 짧은기간에 이렇게 많은 병원과 주사를 맞아본 기억이 없습니다.

그때 고열로 시달리다가 입천장이 다 헐어 버려서 지금 음식도 못먹고 허미.....

 

보이시나요. 헐어서 살이 다 벗겨지고 노랗게 염증도 생기고 ... ㅠㅠ
정말 이렇게 공부해서 어디다 쓰나, 무슨 부귀영화를 누리자고 이러나 싶기도 하지만 ㅋㅋ
일단 스케쥴러와 커널의 종류에 대해서는 공부해놓고 마저 생각합시다.

그럼 시! 작!

1. 스케쥴러

이름부터가 딱 직관적입니다. 스케쥴을 짜주는 놈이지요. 디스패처(Dispatcher) 라고도 하는데요, 이놈이
다음번에 실행할 테스크를 결정한답니다.
Context Switching 이 일어나기 위한 조건은 Interrupt Service Routine 이에요 ㅋ

왜 그러냐규요??

ISR 에 의해서 테스크는 자신의 CPU 점유권을 놓게 되지요~ 그것이 Tick ISR 이던, Timer ISR 이던 DMA ISR 이던 상관없이 말이에요~

그 이후에 CPU 점유율은 커널의 스케쥴러가 갖습니다.
어떤 형태의 커널인지에 따라 이 스케쥴러는 레디 상태에 있는 테스크 들로부터 다음에 서비스를 해줘야 할 테스크를 결정하게 됩니다. 대부분의 커널들은 우선순위가 높은 테스크에게 점유율을 넘기지용~ ㅋㅋ

스케쥴러~ 내 프로그램의 스마트한 교통 순경 정도로 생각해 두시면 좋을듯~~

2. 커널의 종류 : 비선점형 커널, 선점형 커널 로 나눌 수 있다.

(1) Non-preemptive Kernel (비 선점형 커널) 

 선점을 하지 않는 커널. 먼저 점령을 하지 않는 커널.

풀어쓰니 위와 같이 되는군요?? ㅋㅋ 먼저 점령을 하지 않는다. 뭐를? CPU 점유권을~

쉬운 개념인데 이름을 좀 아리까리 하게 지은것 같기도 해요 ㅋㅋㅋ

이전 포스트에서 커널의 종류를 나누는 기준은 ISR 후에 어떤 Task 로 CPU 점유권을 넘길것이냐에 대한
원칙이 무엇이냐에 따라 종류가 결정된다고 했었던 것 기억나시나요?

비 선점형 커널은, 무조건 ISR 로 뛰어들어가기전에 돌고 있던 Task 로 다시 CPU 점유권을 넘기는 커널입니다.
아무리 우선순위가 명박이 할애비 보다 높다고 해도 필요없어요 ㅋ 꿋꿋하게 원래 돌던 놈에게 다시 넘겨주조 ~ ㅋ

그럼 이 커널은 멀티태스킹을 언제하느냐???
태스크에서 자체적으로 자신의 CPU 점유권을 놓아야 합니다 ~ OS_Dly_wait(10) 같은 방식으로요 ~ ㅋㅋㅋ

 


그림으로 보니 한결 더 이해가 빠르지요?? ㅋㅋ

그럼 어떤 특징이 있을까용?

1. 인터럽트 지연시간이 짧습니다. (흠.. 개인적으로 저는 인터럽스 지연시간은 잘 모르겠고, 인터럽스 응답시간과 복귀시간이 짧다고 말하고 싶은데 빌딩블록에는 이렇게 써있네요 ... ㅠㅜ)
2. 테스크 레벨에서도 비재진입 함수를 사용할수 있습니다 (테스크 자신이 제어권을 넘겨주기 전에는 절대로 다른 테스크로 제어권이 넘어가지 않기 떄문에, 일 다하고 제어권을 넘기면 됨ㅋㅋ)
3. 테스크의 응답성이 떨어진다. (재수업게 졸라 수행시간이 긴 테스크가 돌고있다고 가정해보세요 ㅋㅋ 우선순위가 졸라 높은 테스크가 대기중인데 제어권이 넘어올 생각을 안한다면?? 후덜덜 ㅋㅋㅋ) 

초창기 리룩스 커널과 Window3.1 이 비선점형 커널이였습니다 ㅋ
그래서 한번 뻑나면 컴퓨터 전원을 끄는 것 밖에 방법이 없었지요 ~ ㅋㅋ

도대체 CPU 점유율을 뻇어올 방법이 없거등요 ㅋㅋㅋ 훗날 다 선점형 커널로 바뀌었지만 말이죠 ㅋ

하지만 반대로 프로그램을 정말 잘 짜놓았다면?? 굉장히 안정적으로 돌릴수 있는 커널은 비 선점형이 되겠지요 ㅋㅋ 

(2) Preemptive Kernel

선점형 커널 ㅋㅋ 

이제 감이 오시죠? ㅋㅋ

딱 반대입니다. ISR 로 부터 복귀할 때 스케쥴러는 최 우선순위를 갖는 테스크에게 씨피유 점유율을 넘깁니다 ㅋ

좀더 복잡한 로직으로 동작하지만 프로그램의 응답성이 굉장히 개선이 되겠지요?

최고 중요한놈부터 꾸준히 서비스를 할수 있어 지니까요 ㅋㅋ

선점형 커널에서는 최상위 우선순위 태스크가 언제 CPU 의 서비스를 받을수 있을지 알수 있습니다.

하지만, 그렇다 보니까 Critical Section , 비재진입 함수의 사용 등에서 문제점이 발생하지요 ㅋ

아직 일이 덜 끝난상태에서 나보다 중요한 놈에게 CPU 서비스가 넘어갔는데 같은 비재진입 함수를 콜해버리고이러면 데이터가 완전히 꼬여버리자나요 ㅋㅋ

그래서 상호 배제적으로 공유자원에 접근을 하기 위한 노력들이 일어납니다 ㅋ

총 4가지의 방법이 있는데요~ 그것은 다음에 다루도록 하구요 ㅋ 지금은 제목만 알려드릴게요

1. 인터럽트 Enable/Disable
2. Semaphore 의 사용
3. TAS (Test and Set)
4. Scheduler Lock/Unlock

의 방법을 이용해서 공유자원에 상호 배제적으로 접근할 수 있답니다 ㅋㅋ

아 이번 강의 너무 길어지네.

너도 다시 공부하고 정리하는거라서 시험공부도 되고 좋네요 ㅋ
이거 그대로 인쇄해서 읽어보면서 셤공부해야겠네 ㅋ
하다가 빼먹은거 있으면 나중에 보충설명 해 드릴게요 

일단 선점형 커널의 이벤트 그림 올려드립니당

 

Posted by J.Bear