megaOS - 4. Scheduler(스케줄러)

OS에서 가장 핵심이 되는 부분을 커널이라고 부르고, 그리고 그 커널안에서도 가장 중요한 부분을 굳이 말하라고 한다면 스케줄러일것이다.

스케줄러가 무엇인지 한줄로 요약한다면 여러 타스크들중에 어떤 타스크를 실행 시킬것인지 선택하여 그 타스크에게 CPU 점유권을 넘겨주는 기능을 수행하는 블럭이라 하겠다.

문제는 어떤 기준을 가지고 많은 타스크중에 하나를 선택할 것인가이다.  이러한 선택의 알고리듬의 차이가 각각의 RTOS의 특징이 되고 장단점이 되는 것이다.

이번 글에서는 megaOS의 스케줄러가 어떤식으로 동작되는지 설명하고, 스케줄러의 초기화 부분을 구현해 보도록 하겠다.

megaOS는 모두 8개의 우선순위(Priority)를 제공한다.  그러므로 각 타스크는 0~7 중에 하나의 우선순위 값을 가질 수 있다.  0이 가장 높은 우선 순위값이고, 7이 가장 낮은 우선순위값이다.  그러나 가장 낮은 우선순위인 7은 idle_task에서 사용하는 예약된 우선순위값이므로 가급적 일반적인 타스크는 우선순위 값으로 7을 사용하지 않는 것이 좋다.  따라서 실제로 일반 타스크가 사용할 수 있는 우선순위는 0~6 사이의 값을 가진다고 보면 된다.

각각의 타스크들은 동일한 우선 순위를 가질수 있다.  다른 우선 순위 간에는 선점형 방식으로 동작되지만 같은 우선 순위를 가진 타스크들끼리는 라운드 로빈 방식으로 동작된다.  즉, 이말은 하드웨어가 제공할 수 있는 만큼 생성할 수 있는 타스크의 수에 제한이 없다는 뜻이다.

megaOS는 우선 순위에 따른 타스크를 관리하기 위하여 run_list[]라는 list 배열을 사용한다.  타스크의 상태가 running 상태가 되면 run_list[] 배열중에 타스크의 우선 순위에 해당되는 배열에 타스크 link를 연결한다.

스케줄러는 run_list[] 배열을 차례로 하나씩 선택하여 list에 연결된 link의 개수를 조사하여 0이 아닌 list를 발견하면 거기에서 타스크 하나를 선택하여 CPU 점유권을 넘겨주면 된다.

그러나 이렇게 모든 list의 link count값을 조사하는 것은 다소 시간이 걸릴수 있으므로 sched_map이라는 변수를 사용하여 좀더 빨리 높은 우선 순위의 타스크를 선택할 수 있도록 하는 방법을 사용하게 되었다.

그림으로 표현하면 좀더 쉽게 이해할 수 있을것이다.

run_list[0]에 연결되는 타스크가 가장 우선순위가 높은것이고 run_list[7]에 연결된 idle_task가 가장 낮은 우선 순위를 가진다.

run_list에는 생성된 모든 타스크들이 연결되는 것이 아니고, 생성된 타스크 중에서 타스크의 상태가 running 상태인 타스크들만  run_list에 연결되도록 되어 있다.

위의 그림에 보이는 타스크들은 모두 running 상태의 타스크들인 것들이다.

그림에는 run_list[1], run_list[3], run_list[4], run_list[7]에 타스크가 연결되어 있는것을 알수 있다.

이 정보에 의하여 sched_map이라는 8비트 변수에, 링크가 되어 있는 run_list 배열 번호에 해당되는 비트 위치에 1의 값을 설정한다.  그럼 이제 sched_map의 낮은 비트에서부터 첫번째로 1이 되는 비트값의 위치를 찾아내고, 해당 위치의 run_list[] 배열을 선택하여 타스크 정보를 가지고 오면 비교적 쉽게 가장 높은 우선 순위의 타스크를 찾아 낼 수 있게 된다.

불행히도 AVR에는 변수값중에 첫번째로 1로 설정된 비트의 위치를 찾아주는 명령어가 없지만, ARM의 경우 "clz"라는 명령어가 있어 한클럭만에 첫번째로 나타나는 1의 위치를 바로 알 수 있다.

그럼, 이제 run_list[]와 sched_map을 초기화 하는 코드를 만들어 보기로 하겠다.

main() 함수에 os_start()를 추가한다.

int main(void) { arch_init(); board_init(); printf("\nmegaOS. [%s %s]\n",__DATE__,__TIME__); os_start(); while (1); }

커널 코드는 다른 소스코드와 따로 분리하기 위하여 kernel이라는 폴더를 만들어 그 안에 커널 소스코드를 만들기로 하겠다.

Solution Explorer창에서 megaOS를 마우스 오른쪽 버튼을 클릭하여 팝업 메뉴를 나타나게 한다음 Add > New Folder를 선택한 다음 kernel을 입력하여 "kernel" 폴더를 만든다.

kernel 폴더가 만들어 졌으면 os_sched.c 파일에 다음과 같은 코드를 입력한다.

#include <os.h> static struct list sched_list[OS_NR_PRIORITIES]; static uint8_t sched_map; static void sched_init(void) { int i; for (i=0; i<OS_NR_PRIORITIES; i++) { list_init(&sched_list[i]); } sched_map = 0; } static void os_init(void) { sched_init(); } void os_start(void) { os_init(); }

os.h 파일에는 다음과 같은 코드를 입력한다.

#define OS_NR_PRIORITIES 8 #define OS_MIN_PRIORITY (OS_NR_PRIORITIES - 1) #define OS_MAX_PRIORITY 0

이번글에서는 스케줄러의 초기화 부분만 구현하기로 하고 나머지는 차차 추가해 나가기로 하겠다.

megaOS.zip

심화 과정 목차