EDF 스케줄러 구현하기

Computer Science | 2024-04-29

과제 소개

학교 운영체제 과목의 PA3은 EDF Scheduler 구현하기 입니다. EDF(Earliest Deadline First) Scheduler는 Real-time System을 위한 스케줄러로, 말 그대로 데드라인이 가장 짧게 남은 프로세스를 가장 먼저 실행하도록 하는 스케줄러입니다.

Real-time System이란?

먼저 Real-time System이 무엇인지 알아보겠습니다. Real-time System에서는 시간에 민감한 작업들을 처리하기 위해 각 작업들을 정확한 시간 내에 수행하도록 합니다. 따라서 모든 작업들이 데드라인 전에 수행될 수 있도록 처리하는 시스템입니다.

EDF(Earliest Deadline First) Scheduler

EDF 스케줄러는 주어진 Real-time Process들을 데드라인 내에 실행할 수 있도록 하는 스케줄러입니다. 실행되어야 하는 데드라인이 가장 짧게 남은 프로세스가 가장 높은 우선순위를 가지도록 설계하는 Priority Scheduling의 한 방식이죠. 각 Real-time 프로세스는 $C_i$ 와 $T_i$, 두 개의 스케줄링 파라미터를 부여받습니다. $C_i$는 해당 프로세스가 실행되는데 필요한 최대 시간이고, $T_i$는 해당 작업을 반복해야 하는 주기를 나타냅니다. 예를 들어, 프로세스 1의 $(C_i, T_i)$가 $(1, 5)$로 주어진 경우, 시간 5마다 시간 1을 소모해서 프로세스 1을 수행해야 하는 것입니다. 따라서 다음과 같은 식이 성립해야 하죠.

$$ U = \sum_{i=1}^{n} \frac{C_i}{T_i} \leq 1 $$

더 자세한 정보는 EDF에서 찾아볼 수 있습니다.

Problem Specification

```
 int sched_setattr(int pid, int runtime, int period);
```
- 프로세스 pid를 Real-time Process로 만드는 시스템 콜입니다.
- runtime에 $C_i$, period에 $T_i$ 가 주어집니다.
```
 void sched_yield();
```
- 호출한 프로세스가 yield()를 실행하여 CPU를 양보할 수 있도록 합니다.
EDF scheduler 구현하기
- sched_setattr()을 통해 Real-time으로 설정된 프로세스를 EDF policy에 맞게 구현합니다.

xv6 scheduler 알아보기

우선 EDF scheduler를 xv6가 사용하고 있는 스케줄링 코드에 대해서 알아봐야 합니다. xv6는 Round Robin방식의 스케줄링을 사용합니다. 따라서 timer interrupt가 일어나서 커널을 깨우게 되면, 커널은 다음으로 실행할 수 있는 프로세스를 찾아서 실행하게 됩니다. 코드로 자세하게 살펴봅시다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// kernel/proc.c

void
scheduler(void)
{
  struct proc *p;
  struct cpu *c = mycpu();

  c->proc = 0;
  for(;;){
    // Avoid deadlock by ensuring that devices can interrupt.
    intr_on();

    for(p = proc; p < &proc[NPROC]; p++) {
      acquire(&p->lock);
      if(p->state == RUNNABLE) {
        // Switch to chosen process.  It is the process's job
        // to release its lock and then reacquire it
        // before jumping back to us.
        p->state = RUNNING;
        c->proc = p;
        swtch(&c->context, &p->context);

        // Process is done running for now.
        // It should have changed its p->state before coming back.
        c->proc = 0;
      }
      release(&p->lock);
    }
  }
}

우선 xv6는 시스템이 부팅되고 나서, scheduler() 라는 함수를 실행하도록 되어 있습니다. 이 함수는 무한루프를 돌고, 커널은 계속 이 함수를 실행하죠. 이 scheduler() 함수를 살펴보면, 무한루프를 돌면서 RUNNABLE 한 프로세스를 찾아 실행합니다. swtch() 함수를 통해 커널의 컨텍스트와 프로세스의 컨텍스트를 바꿔주면 프로세스가 실행되는 구조입니다. 이후 일정시간이 지난 뒤 timer interrupt가 발생하면 다시 swtch() 함수를 통해 커널 코드로 돌아오게 되면, 설정했던 c->proc을 0으로 바꿔주고 다음 RUNNABLE 프로세스를 찾아 실행합니다.

그렇다면 여기서 사용하는 swtch() 함수는 어떻게 컨텍스트를 바꿀까요? 다음의 코드를 살펴봅시다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
// kernel/proc.h

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;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# kernel/swtch.S

.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

우선 struct context 가 어떻게 생겼는지 확인할 필요가 있습니다. 이는 간단합니다. 다음의 코드를 살펴보면, context에는 return address와 stack pointer, 그리고 s0-s11의 callee-saved register가 저장됩니다. 그리고 CPU에서 이 레지스터들이 바뀐다는 것은 실행되는 프로세스가 달라진다는 것을 의미하게 됩니다.

scheduler() 함수에서는 swtch(&c->context, &p->context) 를 호출해서 컨텍스트를 스위치합니다. swtch() 함수는 kernel/swtch.S 파일에 어셈블리로 작성되어 있습니다. 첫 번째 파라미터인 a0에 실행중인 컨텍스트를 저장하고, 두 번째 파라미터인 a1에서 다음으로 실행될 컨텍스트를 불러옵니다.

EDF Scheduler 구현하기

우리는 이 RR 스케줄링 코드대신, EDF 스케줄링 코드를 구현해야 합니다. 따라서 struct proc에 다음과 같은 정보를 추가로 저장합니다.

1
2
3
4
5
6
7
8
9
// kernel/proc.h

struct proc {
    ...
    int runtime;
    int period;
    uint64 thisperiodstart;
    uint64 deadline;
}

runtime과 period는 sched_setattr() 로 전달받은 정보를 저장하고, thisperiodstart 에는 이번 주기의 시작 ticks 를, deadline 에는 이번 주기의 끝 ticks 를 저장하도록 합니다.

1. `sched_setattr()` 구현하기

먼저 sched_setattr() 시스템 콜을 구현해야 합니다. 해당 시스템 콜은 주어진 프로세스의 runtime과 period를 설정합니다. 그리고 해당 프로세스는 EDF 스케줄러에 의해 Real-time으로 스케줄링 될 것입니다. 따라서 다음과 같이 프로세스를 찾아서 추가한 field에 값을 설정할 수 있도록 하는 코드를 추가해주었습니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
// kernel/sysproc.c

uint64
sys_sched_setattr()
{
  ...
  // find process whose pid == pid
  // if found, goto found
  // else,
  return -1;

found:
  p->runtime = runtime;
  p->period = period;
  acquire(&tickslock);
  p->thisperiodstart = ticks;
  p->deadline = ticks + period;
  release(&tickslock);

  release(&p->lock);
  return 0;
}

2. `sched_yield()` 구현하기

다음은 sched_yield() 입니다. 이 함수는 Real-time process가 자신의 일을 마치고 나면 CPU를 양보할 수 있도록 하는 함수입니다. 따라서 이 함수가 불린다는 것은 Real-time process가 해당 주기에 해야할 일을 다 했다는 것을 나타내므로, 프로세스의 thisperiodstart와 deadline에 각각 주기인 period를 더해주고 CPU를 양보하도록 합니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
// kernel/sysproc.c

uint64
sys_sched_yield(void)
{
  struct proc *p = myproc();
  acquire(&p->lock);
  if (p->runtime != 0 || p->period != 0)  // check if real-time process
  {
    p->thisperiodstart += p->period;
    p->deadline += p->period;
  }
  release(&p->lock);

  yield();  // yield CPU

  return 0;
}

3. EDF 스케줄러 구현하기

이렇게 되면 모든 준비는 끝났습니다. EDF 스케줄러를 구현해봅시다. 해야할 일은 다음과 같습니다.

실행해야 하는 프로세스 중 deadline이 가장 빠른 프로세스 찾기
찾았다면 해당 프로세스 실행
찾지 못했다면 원래의 xv6처럼 RR 스케줄링

이를 코드로 구현하면 다음과 같습니다. find_earliest_deadline() 함수는 실행해야 하는 프로세스 중 deadline이 가장 빠른 프로세스를 리턴합니다. 찾지 못했다면 0을 리턴합니다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// kernel/proc.c

void
scheduler(void)
{
  struct proc *p;
  struct cpu *c = mycpu();
  int lastrun = 0;

  c->proc = 0;
  for(;;){
    // Avoid deadlock by ensuring that devices can interrupt.
    intr_on();

    for(p = proc; p < &proc[NPROC]; p++) {
      struct proc *edp = find_earlest_deadline(lastrun);
      if (edp != 0)
      {
        // If real-time process exists, run
        acquire(&edp->lock);
        edp->state = RUNNING;
        c->proc = edp;
        swtch(&c->context, &edp->context);

        c->proc = 0;
        lastrun = edp->pid;
        release(&edp->lock);
        p--;
        continue;
      }
      acquire(&p->lock);
      if(p->state == RUNNABLE && p->runtime == 0) {
        // Switch to chosen process.  It is the process's job
        // to release its lock and then reacquire it
        // before jumping back to us.
        p->state = RUNNING;
        c->proc = p;
        swtch(&c->context, &p->context);

        // Process is done running for now.
        // It should have changed its p->state before coming back.
        c->proc = 0;
        lastrun = p->pid;
      }
      release(&p->lock);
    }
  }
}

이렇게 실행해야 하는 Real-time process가 있다면 가장 데드라인이 빠른 순서대로 실행하고, 없다면 원래의 RR 스케줄링으로 프로세스를 실행할 수 있도록 하는 EDF 스케줄러를 xv6에 구현할 수 있습니다.

#OS #xv6 #CPU Scheduler