Chapter 9, 10: Scheduler & Context Switching

Round Robin Algorithm

kernel/task.c

13 static uint32_t         sCurrent_tcb_index;
14 static KernelTcb_t      *Scheduler_round_robin_algorithm(void);
...
 52 //Basic Round Robin algorithm
 53 static KernelTcb_t*     Scheduler_round_robin_algorithm(void) {
 54  sCurrent_tcb_index++;
 55  sCurrent_tcb_index %= sAllocated_tcb_index;
 56  return &sTask_list[sCurrent_tcb_index];
 57 }

단순 ++ 연산을 통해 다음으로 스케줄링할 태스크의 ID를 구한다.
% 나머지 연산을 통해 sAllocated_tcb_index, 즉 현재 할당된 태스크의 총 갯수보다 스케줄링할 태스크의 ID가 높아지는것을 방지한다.

Context Switching

1. ARM 환경에서 컨텍스트(프로그램)이 실행되기 위해서 필요한것 ?
   -> R0~R12(범용 레지스터), PC(프로그램 카운터 레지스터) 등등의 레지스터
   따라서 컨텍스트 스위칭이란 이들을 Save 하고 Restore 하는 것.

2. 어느 기준으로 (언제?) 컨텍스트간 스위칭을 수행할 것인가 ?
   -> 선점형 멀티태스킹 시스템(타이머를 이용한 시분할 시스템) / 비선점형 멀티태스킹 시스템(yield 를 통한 태스크 명시적 스케줄링 시스템)
   우리는 비선점형 멀티태스킹, 즉 yield 를 통한 컨텍스트간 스위칭을 구현할 것임.

Scheduler

 17  KernelTcb_t    *sCurrent_tcb;
 18  KernelTcb_t    *sNext_tcb;
 19 void    Kernel_task_scheudler(void);
...
 60 void    Kernel_task_scheduler(void) {
 61   sCurrent_tcb  = &sTask_list[sCurrent_tcb_index];
 62   sNext_tcb     = Scheduler_round_robin_algorithm();
 63
 64   Kernel_task_context_switching(); //ASM routine, context switching to sNext_tcb from sCurrent_tcb;
 65 }

현재 실행 중인 tcb(task control block) 의 위치를 sCurrent_tcb 에 저장
RR 스케줄링 알고리즘에 의해 선택된 다음 태스크의 tcb 의 위치를 sNext_tcb 에 저장

Kernel_task_context_switching() 이라는 어셈블리 루틴을 통해 sCurrent_tcb -> sNext_tcb 로 스위칭

Switching

1. 현재 스택에 그대로 현재 컨텍스트를 백업

2. 컨텍스트가 백업됨에 따라 변경된 스택 포인터를 태스크 컨트롤 블록에 저장 (커널이 sp 를 쉽게 가져 올 수 있어야 복구 가능)

3. 스케줄링할 태스크 컨트롤 블록의 sp 값을 범용 레지스터 sp 에 작성

4. 백업시에 해당 sp 위치 바로 위에 컨텍스트를 백업해놨으므로, sp 에서부터 바로 컨텍스트를 레지스터에 복구

lib/switch.c

 1 #include "stdint.h"
  2 #include "stdbool.h"
  3 #include "armcpu.h"
  4 #include "switch.h"
  5
  6
  7 __attribute__((naked)) void Kernel_task_context_switching(void) {
  8   __asm__ ("B Save_context");
  9   __asm__ ("B Restore_context");
 10 }

_ attribute _(naked)는 컴파일러가 함수를 컴파일 할때 자동으로 만드는 스택 백업, 복구, 린턴 관련 어셈블리어를 생성하지 않게 하고 오직 내부에 코딩한 코드 자체만 그대로 남게 함.

ARM 인스트럭션 B 또한 LR 을 변경하지 않기 위해서 사용.

Context Backup

앞서 구현한 컨텍스트 자료 구조에 따라 스택 명령어의 순서를 조정해야 한다.

 10 typedef struct KernelTaskContext_t{
 11   uint32_t spsr;
 12   uint32_t r0_r12[13];
 13   uint32_t pc;
 14 } KernelTaskContext_t;

구조체의 변수는 메모리 값이 아래에서 위,
스택에서는 메모리 값이 위에서 아래로 저장됨.
따라서 순서를 정반대로 놓아야한다.

백업 함수 작성

lib/switch.c

12 __attribute__ ((naked)) void Save_context(void) {
 13   // save current task context into the current task stack
 14   __asm__ ("PUSH {lr}");
 15   __asm__ ("PUSH {r0, r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11, r12}");
 16   __asm__ ("MRS r0, cpsr");
 17   __asm__ ("PUSH {r0}");
 18
 19   // save current task stack pointer into the current TCB
 20   __asm__ ("LDR r0, =sCurrent_tcb"); //r0 = &sCurrent_tcb
 21   __asm__ ("LDR r0, [r0]");     //reference of the r0, which is sCurrent_tcb
 22   __asm__ ("STMIA r0!, {sp}");     //store sp to r0
 23 }

14: 먼저 현재 LR(Kernel_task_context_switching의 리턴 주소)를 pc 멤버 변수에 저장한다. 따라서 이 태스크가 다시 스케줄링을 받았을때 해당 리턴주소로 복귀할 수 있음.

15: 두번째, R0~R12 의 범용 레지스터를 백업한다.

16~17: 세번째, cspr 을 백업한다. R0 는 위에서 이미 백업해놨으므로 사용해도 문제없음.

여기까지 현재 스택에 컨텍스트를 저장하는 과정. 그후는 변경된 sp를 tcb에 작성해야한다.

20: sCurrent_tcb(포인터 변수) 의 주소를 읽어온다.

21: r0 은 현재 sCurrent_tcb 가 저장된 주소이기 때문에 [r0] 으로 태스크 컨트롤 블록의 온전한 메모리 위치를 읽어온다.

22: sp 를 r0 에 저장한다.

복구 함수 작성

복구 함수는 백업 함수의 정반대라고 생각하면 된다.

lib/switch.c

 26 __attribute__ ((naked)) void Restore_context(void) {
 27   // restore next task stack pointer from the next TCB
 28   __asm__ ("LDR r0, =sNext_tcb");
 29   __asm__ ("LDR r0, [r0]");
 30   __asm__ ("LDMIA r0!, {sp}");
 31
 32   // restore next task registers from the stack pointer
 33   __asm__ ("POP {r0}");
 34   __asm__ ("MSR cpsr, r0");
 35   __asm__ ("POP {r0, r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11, r12}");
 36   __asm__ ("POP {pc}");
 37 }

28~30: 백업 함수와 정반대로 먼저 tcb로부터 sp를 읽어온뒤,

33~36: 순서대로 레지스터에 복구한다.

yield 함수

앞서 언급했듯이, 우리는 태스크가 명시적으로 스케줄링을 수행하는 비선점형 스케줄링을 구현할 것이다.
태스크가 yield() 를 호출함으로써 스케줄링이 수행된다.

kernel/Kernel.c

  1 #include "stdint.h"
  2 #include "Kernel.h"
  3
  4 void Kernel_yield(void) {
  5   Kernel_task_scheduler();
  6 }
  7
  8 void Kernel_start(void) {
  9   Kernel_task_start();
 10 }

커널 시작하기

처음 스케줄러를 실행할때는 현재 동작중인 태스크가 없기 때문에 스케줄러가 동작하지 않는다.
따라서 최초로 스케줄링할대는 컨텍스트 백업을 하지 않아야 한다. 또한 0번 tcb 를 컨텍스트 복구 대상으로 삼는다.

 22 //Kernel Initialization for task
 23 void Kernel_task_init(void) {
 24   sAllocated_tcb_index = 0; 
 25   sCurrent_tcb_index = 0;
....
 67 void Kernel_task_start(void) { //Starting from sTask_list[0] to avoid storing Kernel garbage data. This routine is called only when the kernel is starting.
 68   sNext_tcb = &sTask_list[sCurrent_tcb_index];
 69   Restore_context();
 70 }

kernel/Kernel.h

 1 #ifndef KERNEL_KERNEL_H_
  2 #define KERNEL_KERNEL_H_
  3
  4 #include "task.h"
  5
  6 void Kernel_yield(void);
  7 void Kernel_start(void);
  8
  9 #endif