들어가며

안녕하세요 cpu scheduling2 글에서 보았듯이 cpu에서 돌아갈 프로세스를 선택하기 위해서 os는 스케줄러를 운영했습니다. 그리고 매우 다양한 종류의 스케줄러들이 있었죠.

이번에는 그러한 지식을 바탕으로 저의 커스텀 스케줄러를 xv6 운영체제 안에 넣어보려고 합니다.

이번에 적용할 스케줄러의 이름은 EDF(Earliest Deadline First) 스케줄러인데 EDF란 무엇이고, 기존 스케줄러 코드는 어떻게 구성되어있나 살펴본 뒤 EDF를 구현하는 과정을 살펴보겠습니다.

스케줄링 과정 알아보기

Real-time

EDF에 대해 다루기 이전에 Real-time system에 대해 말씀드리려고 합니다. Real-time system이란 특정 시간 제약 안에 입력에 대해 응답하는 시스템입니다. 특정 시간 제한이 있으므로 입력에 대해 실시간으로 반응한다고 볼 수 있는 것이죠.

저희는 이번 프로젝트에서 process를 real-time process와 non-real-time process로 나눌 것입니다. 여기서 real-time process란 period와 deadline값을 가지고 있어서, 그 프로세스가 시작된 시간으로부터 deadline이 지나기전까지 period만큼은 시간이 할당되어야함을 의미합니다.

이제 소개드릴 EDF 스케줄러란 real-time process에 대해 가장 deadline이 가까운 프로세스들부터 실행하는 스케줄러를 의미합니다. 물론 모든 real-time process는 non-real-time process보다 항상 우선합니다.

xv6의 스케줄러

xv6는 기본적으로 RR(Round robin)방식으로 스케줄러를 사용하고 있는데요, cpu scheduling 글에서 RR에 대해서 설명하였으니 따로 추가로 설명드리지는 않겠습니다.

그러면 스케줄링은 커널 안에서 실제로 어떻게 일어나는지 살펴보곘습니다.

스케줄링 발생과 처리

컴퓨터에서는 일정시간마다 timer interrupt가 발생하게됩니다. 이를 통해 일정 시간이 지났음을 알게되고, cpu를 사용중이던 프로세스에서 커널로 넘어오고, 스케줄러에 의해 다른 프로세스를 돌리게 됩니다.

이러한 timer interrupt역시 usertrap에서 처리됩니다. usertrap역시 xv6-Trap 글에서 소개를 드렸으니 아실 것입니다.

usertrap()을 살펴보면 맨 마지막 부분에 timer interrupt를 통해서 usertrap으로 들어왔을 경우 yield()를 호출하는 부분이 있습니다. 이 yield()함수가 바로 프로세스와 cpu 스케줄러 사이의 컨텍스트 스위칭이 일어나는 부분입니다.

void
usertrap(void)
{
  ...

  // give up the CPU if this is a timer interrupt.
  if(which_dev == 2)
    yield();

  usertrapret();
}

yield()에 대해서 좀 더 자세히 살펴보겠습니다.

yield() 안에서는 현재 프로세스의 상태를 RUNNABLE로 바꾼 뒤, sched() 함수를 호출합니다. sched()는 여러가지 체크를 한 뒤, swtch()를 통해 cpu에서 돌아갈 context를 교체합니다.

// Give up the CPU for one scheduling round.
void
yield(void)
{
  struct proc *p = myproc();
  acquire(&p->lock);
  p->state = RUNNABLE;
  sched();
  release(&p->lock);
}

void
sched(void)
{
  int intena;
  struct proc *p = myproc();

  if(!holding(&p->lock))
    panic("sched p->lock");
  if(mycpu()->noff != 1)
    panic("sched locks");
  if(p->state == RUNNING)
    panic("sched running");
  if(intr_get())
    panic("sched interruptible");

  intena = mycpu()->intena;
  swtch(&p->context, &mycpu()->context);
  mycpu()->intena = intena;
}

.globl swtch
swtch:
        sd ra, 0(a0)
        sd sp, 8(a0)
        sd s0, 16(a0)
        sd s1, 24(a0)
        sd s2, 32(a0)
        sd s3, 40(a0)
        sd s4, 48(a0)
        sd s5, 56(a0)
        sd s6, 64(a0)
        sd s7, 72(a0)
        sd s8, 80(a0)
        sd s9, 88(a0)
        sd s10, 96(a0)
        sd s11, 104(a0)

        ld ra, 0(a1)
        ld sp, 8(a1)
        ld s0, 16(a1)
        ld s1, 24(a1)
        ld s2, 32(a1)
        ld s3, 40(a1)
        ld s4, 48(a1)
        ld s5, 56(a1)
        ld s6, 64(a1)
        ld s7, 72(a1)
        ld s8, 80(a1)
        ld s9, 88(a1)
        ld s10, 96(a1)
        ld s11, 104(a1)
        
        ret

이 때, context란 아래와 같은 구조로 이루어져있는데, 컨텍스트 스위치가 될 때 보존되어야 할 레지스터 값들을 의미합니다.

struct context {
  uint64 ra;
  uint64 sp;

  // callee-saved
  uint64 s0;
  uint64 s1;
  uint64 s2;
  uint64 s3;
  uint64 s4;
  uint64 s5;
  uint64 s6;
  uint64 s7;
  uint64 s8;
  uint64 s9;
  uint64 s10;
  uint64 s11;
};

swthc()가 실행되면 mycpu->context에 저장되어있던 정보로 인해 특정 코드가 실행될 것입니다.

그리고 이 코드는 바로 scheduler()입니다. scheduler()는 말그대로 스케줄링 함수인데 컴퓨터가 시작될때 작동하기 시작해서 무한 루프를 돌고 있습니다.

그래서 언제든지 swtch()를 통해서 이 코드로 돌아오게되면 무한 루프가 다시 작동하고, 적당한 스케줄링을 하는 것이죠.

함수는 정말 간단하게 생겼는데요, 모든 process에 대해서 순회하면서, RUNNABLE한 프로세스가 있다면 그 프로세스를 골라서 다시 swtch()를 통해 그 프로세스를 실행시키는 역할만 합니다.

void
scheduler(void)
{
  struct proc *p;
  struct cpu *c = mycpu();
  struct proc *rtp;
  
  c->proc = 0;
  for(;;){
    intr_on();

	for(p = proc; p < &proc[NPROC]; p++) {
		acquire(&p->lock);
		if(p->state == RUNNABLE) {
			p->state = RUNNING;
			c->proc = p;
			swtch(&c->context, &p->context);
			c->proc = 0;
		}
		release(&p->lock);
	}
  }
}

EDF 적용하기

그러면 이 스케줄러에 어떻게 EDF를 적용할 수 있을까요?

우선 유저가 사용할 수 있는 시스템콜로 다음이 있다고 생각하겠습니다.

set_sched_attr(int pid, int period, int deadline)

이 시스템 콜은 특정 pid의 프로세스에 대해서 period, deadline을 설정해줍니다. 그래서 non-real-time이었다가도 이 시스템 콜로 인해 real-time process가 될 수 있는 것이죠.

real-time process가 존재하는 이상 scheduler()에서는 이 real-time process를 따로 처리를 해주어야할 것입니다.

그래서 저는 scehduler()의 프로세스 순회하는 부분의 코드를 다음과 같이 수정하였습니다.

기존의 스케줄러가 돌 때, 우선 rtp(real time process)를 찾습니다.

만약 현재 돌려야하는 rpt가 발견됐다면 무조건 그 rtp를 실행시킵니다.

그렇지 않다면 기존의 스케줄러 코드를 작동시켜서 원래의 RR 스케줄러처럼 돌아가게 하는 것이죠.

for(p = proc; p < &proc[NPROC]; p++) {
	while ((rtp = find_rtp()) != 0)
	{
		acquire(&rtp->lock);
		c->proc = rtp;
		swtch(&c->context, &rtp->context);
		c->proc = 0;
		release(&rtp->lock);
	}
	acquire(&p->lock);
	if(p->state == RUNNABLE && !p->runtime) {
		p->state = RUNNING;
		c->proc = p;
		swtch(&c->context, &p->context);
		c->proc = 0;
	}
	release(&p->lock);
}

마무리

이렇게 cpu scheduling2 글에서 배운 이론적인 내용에서 나아가 실제 운영체제의 스케줄링이 일어나는 방식을 분석해보고, 어떻게 새로운 스케줄러를 적용할 수 있는지 분석해보았습니다.

이제는 확실히 스케줄링이 어떻게 작동하는지 전체적인 과정을 이해할 수 있을 것 같습니다.