운영체제의 스케줄러를 C 를 통해 구현하는 방법을 소개한다. 스케줄러 자체가 복잡하므로 코드 분량의 압박이 조금 있지만 하나 하나 뜯어보면 크게 어렵지 않다. 함수 및 일부 라인에 주석을 달아 설명을 첨부하였다.

* 책에 나오는 코드를 한줄 한줄 해석하여 새로 작성하였기에 본래의 코드와는 다소 상의할 수 있습니다.

1. 소스코드

main.c

#include <stdbool.h>
#include <stdio.h>

#include <unistd.h>

#include "scheduler.h"

#define DECLARE_TEST_FUNC(NAME, START, END, INC, PREFIX)\
	void test_func_##NAME(void *context)		\
	{						\
		printf("Enter %s\n", __FUNCTION__);	\
							\
		for (int i = START; i < END; i += INC) {\
			printf(PREFIX "%5d\n", i);	\
			usleep(50000);			\
		}					\
							\
		printf("End of the %s\n", __FUNCTION__);\
	}					       /*
********************************************************/

DECLARE_TEST_FUNC(one, 0, 15, 1, "TASK 1: ")
DECLARE_TEST_FUNC(two, 500, 700, 10, "\t\tTASK 2: ")
DECLARE_TEST_FUNC(three, 1000, 1005, 1, "\t\t\t\tTASK 3: ")

int main(void)
{
	// 부모 태스크 생성
	thread_init();

	// 태스크 3 개 생성
	thread_create(test_func_one, NULL);
	thread_create(test_func_two, NULL);
	thread_create(test_func_three, NULL);

	// 부모 태스크 실행
	thread_wait();

	return 0;
}

main.c 코드는 thread_create() 라는 함수를 이용하여 세 개의 태스크를 생성하고 실행한다. 각각의 함수에 대해서는 아래의 코드를 통해 자세히 소개한다. 일단은 각각의 태스크가 순차적으로 스케줄링되어 실행되는 이미지를 머릿 속에 그리고 간다.

scheduler.h

#ifndef SCHEDULER_H__
#define SCHEDULER_H__

#define THREAD_STACKSIZE 1024

// 태스크 상태를 정의하는 열거형
enum task_status {
	TASK_STATUS_READY = 0,
	TASK_STATUS_RUN,
	TASK_STATUS_YIELD,
	TASK_STATUS_SLEEP,
	TASK_STATUS_KILL
};

/* [태스크 상태 구조체]
 *
 * $ 스택 메모리, 스택 포인터
 * $ 태스크 아이디, 태스크 상태
 * $ 이전 태스크, 다음 태스크 구조체 포인터
 */
struct task_info {
	unsigned long stack[THREAD_STACKSIZE];
	unsigned long sp;

	int task_id;
	enum task_status status;

	struct task_info *prev;
	struct task_info *next;
};

// 태스크 생성에 사용되는 callback 함수 원형 정의
typedef void (*task_func)(void *context);

// 쓰레드를 생성하는 thread_create 함수 정의
struct task_info *thread_create(task_func callback, void *context);

// etc.
void thread_init(void);
void thread_wait(void);
void thread_uninit(void);
void thread_switch(int);
void thread_kill(void);

#endif

scheduler.c

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>
#include <signal.h>
#include <setjmp.h>

#include <unistd.h>
#include <sys/wait.h>
#include <sys/time.h>

#include "scheduler.h"

// task switching 시 저장되어야 하는 정보
struct frame {
	// 플래그 레지스터, ARM 의 CPSR
	unsigned long flags;

	// Base stack pointer register
	unsigned long rbp;

	// Source and destination index register
	unsigned long rdi;
	unsigned long rsi;

	// 범용 레지스터(r[a~d]x)
	unsigned long rdx;
	unsigned long rcx;
	unsigned long rbx;
	unsigned long rax;

	// 콜백함수 등록
	unsigned long callback;
	unsigned long retaddr;
	unsigned long data;
};

// 현재 실행 중인 태스크를 관리하는 스케줄링 핸들러
struct sched_handler {
	int child_task;

	struct task_info *running_task;
	struct task_info *root_task;
} sched_handler;

struct task_info *task_get_running_task(void);
void task_insert(struct task_info *);
void task_delete(struct task_info *);
void task_next(void);
void scheduler(void);
void parent_task(void *);

// 새로운 태스크 생성
struct task_info *thread_create(task_func callback, void *context)
{
	struct task_info *task;
	struct frame *frame;

	task = malloc(sizeof(struct task_info));
	if (task == NULL)
		return NULL;

	memset(task, 0x00, sizeof(struct task_info));

	// 동적할당한 태스크의 스택 최하단을 (메모리 기준으론 최상단)
	// 태스크의 상태 정보 저장을 위한 공간으로 사용
	frame = (struct frame *) &(task->stack[
		THREAD_STACKSIZE - sizeof(struct frame)
	]);

	// 오버플로우 체크
	for (int i = 0; i < THREAD_STACKSIZE; i++)
		task->stack[i] = i;

	// 스택 프레임 초기화
	memset(frame, 0x00, sizeof(struct frame));
	frame->callback = (unsigned long) callback;
	frame->retaddr = (unsigned long) thread_kill;
	frame->data = (unsigned long) context;
	// rbp 에는 rax 멤버 변수의 주소를 저장, 그래야 callback 이 호출됨.
	// GDB 로 Assembly 코드를 보면 쉽게 이해 가능
	frame->rbp = (unsigned long) &frame->rax;

	task->sp = (unsigned long) frame;

	sched_handler.child_task++;
	task->task_id = sched_handler.child_task;
	task->status = TASK_STATUS_READY;

	task_insert(task);

	return task;
}

// 부모 태스크 생성
void thread_init(void)
{
	sched_handler.root_task = NULL;
	sched_handler.running_task = NULL;

	sched_handler.child_task = 0;

	thread_create(parent_task, NULL);
}

// 쓰레드 전환
static unsigned long spsave, sptmp;
void thread_switch(int unused)
{
	// 레지스터의 정보를 백업한다.
	asm(	"push %%rax	\n\t"
		"push %%rbx	\n\t"
		"push %%rcx	\n\t"
		"push %%rdx	\n\t"
		"push %%rsi	\n\t"
		"push %%rdi	\n\t"
		"push %%rbp	\n\t"
		"pushf		\n\t"
		"mov %%rsp, %0	": "=r" (spsave));

	// 실행 중인 태스크의 sp 를 저장
	sched_handler.running_task->sp = spsave;

	// running_task 를 다음에 실행될 태스크로 전환
	scheduler();

	// 다음 태스크의 stack pointer 를 sptmp 에 저장
	sptmp = sched_handler.running_task->sp;

	// 레지스터의 값을 실행될 태스크의 이전 정보로 복원
	asm(	"mov %0, %%rsp	\n\t"
		"popf		\n\t"
		"pop %%rbp	\n\t"
		"pop %%rdi	\n\t"
		"pop %%rsi	\n\t"
		"pop %%rdx	\n\t"
		"pop %%rcx	\n\t"
		"pop %%rbx	\n\t"
		"pop %%rax	\n\t"
		::"r" (sptmp));
}

// 다음에 실행될 태스크를 선택
void scheduler(void)
{
	struct task_info *task;

	task = task_get_running_task();
	switch (task->status) {
	case TASK_STATUS_RUN:
	case TASK_STATUS_SLEEP:
		break;

	case TASK_STATUS_KILL:
		task_delete(task);
		scheduler();
		break;

	case TASK_STATUS_YIELD:
		task->status = TASK_STATUS_RUN;
		break;

	case TASK_STATUS_READY:
		task->status = TASK_STATUS_RUN;
		break;
	}

	task_next();
}

// 쓰레드 대기, thread_join()
void thread_wait(void)
{
	parent_task(NULL);
}

// 현재 실행 중인 쓰레드를 죽임
void thread_kill(void)
{
	struct task_info *task;

	task = task_get_running_task();
	task->status = TASK_STATUS_KILL;

	thread_switch(0);
}

// empty function
void thread_uninit(void)
{
	return /* null statement */;
}

// 메인 태스크 실행.
void parent_task(void *context)
{
	struct sigaction act;
	sigset_t masksets;
	pid_t pid;

	sigemptyset(&masksets);
	act.sa_handler = thread_switch;
	act.sa_mask = masksets;
	act.sa_flags = SA_NODEFER;

	sigaction(SIGUSR1, &act, NULL);

	if ((pid = fork()) == 0) {
		// 자식 프로세스, 자식 프로세스는 부모 프로세스에게
		// 주기적으로 시그널을 던져서 등록된 signal handler 함수가
		// 호출될 수 있게 한다. (이 함수가 바로 thread_switch)
		// usleep 의 값을 늘이고 줄임으로 문맥 전환 시간을
		// 변경할 수 있다.
		while (true) {
			usleep(200000);
			kill(getppid(), SIGUSR1);
		}
	} else while (true) {
		// 부모 프로세스, 부모 프로세스는 태스크의 수가
		// 1 이 될 때까지 (본인만 남을 때까지) 대기한다.
		if (sched_handler.child_task == 1) {
			// 꾸준히 시그널을 날려주던 자식 태스크를 종료
			kill(pid, SIGINT);
			wait(NULL);
			break;
		}
	}
}

// 새로운 태스크 삽입
void task_insert(struct task_info *task)
{
	if (sched_handler.root_task == NULL) {
		sched_handler.root_task = task;
		sched_handler.running_task = task;
	} else {
		struct task_info *temp;

		temp = sched_handler.root_task;
		while (temp->next != NULL)
			temp = temp->next;

		temp->next = task;
		task->prev = temp;
	}
}

// 현재 실행 중인 태스크를 반환하는 함수
struct task_info *task_get_running_task(void)
{
	return sched_handler.running_task;
}

// 연결 리스트를 통해 현재 실행 중인 태스크를 다음으로 옮김
void task_next(void)
{
	struct task_info *temp;

	temp = sched_handler.running_task;
	if (temp->next != NULL)
		sched_handler.running_task = temp->next;
	else
		sched_handler.running_task = sched_handler.root_task;
}

// 인자로 전달된 태스크 구조체 할당 해제
void task_delete(struct task_info *task)
{
	struct task_info *temp = task->prev;

	printf("delete task %d\n", task->task_id - 1);

	if (sched_handler.root_task == task) {
		sched_handler.root_task = NULL;
		sched_handler.running_task = NULL;
		sched_handler.child_task = 0;
	} else {
		temp->next = task->next;

		if (task == sched_handler.running_task) {
			if (temp->next != NULL) {
				(task->next)->prev = temp;
				sched_handler.running_task = temp->next;
			} else {
				sched_handler.running_task = temp;
			}
		}

		sched_handler.child_task--;
	}

	free(task);
}

2. 코드 해석

코드 각 라인의 주석을 달아 상세히 설명하였으므로 해석은 생략합니다.

3. 실행 결과

출처

[책] 리눅스 커널 내부구조 (백승제, 최종무 저)
[책] C Programming: A Modern Approach 2/E (K.N.KING 저)