Operating Systems: Three Easy Pieces는 마지막에 실습 과제를 포함하고 있다. 예전에 책을 보기는 했지만 실습을 스킵했더니 놓치는 게 많았던 거 같아서 하나씩 진행해보려고 한다.

과제는 MIT에서 교육용으로 만든 RISC-V OS Xv6를 기반으로 진행된다.

Task

두번째 과제는 Xv6의 프로세스 스케쥴러 정책을 변경해보는 것이다.

과제에서는 추첨 스케쥴링 방식을 구현하도록 했지만 그 대신 조금 더 결정론적인 Stride 스케쥴링 방식으로 구현해보았다.

Xv6의 스케쥴링 코드 흐름

한 프로세서의 스케쥴러가 여러 유저 프로세스를 번갈아가며 스케쥴링하는 흐름을 살펴보려 한다.

일단 현재 실행되고 있는 유저 프로세스가 타이머 인터럽트를 받는 상황을 가정한다.

저번 과제에서 봤듯이 인터럽트가 발생하면 인터럽트 핸들러가 발생하여 커널 모드에서 usertrap을 실행하게 된다.

나중에 기존에 실행하던 코드 흐름으로 복귀하기 위해 유저 프로그램 카운터를 프로세스의 트랩프레임에 저장한다.

// usertrap()
...
p->trapframe->epc = r_sepc();
...

그 후 인터럽트 종류가 타이머 인터럽트였다면 yield함수를 호출한다.

yield함수에서는 프로세스의 state를 RUNNABLE로 변경한 후 CPU 제어권을 놓기 위해 sched를 호출한다.

// yield()
struct proc *p = myproc();
acquire(&p->lock);
p->state = RUNNABLE;
sched();
release(&p->lock);

sched는 여러 사전 조건을 확인한 후 swtch를 호출하여 스케쥴러 컨텍스트로 이동한다.

swtch호출로 ra 레지스터 값은 해당 호출 다음 줄의 코드 주소로 설정이 되고, 이 값은 프로세스의 컨텍스트에 저장된다. 그 후 스케쥴러의 컨텍스트를 레지스터로 담은 다음 ret를 실행하면 기존 스케쥴러 코드에서 sched호출이 리턴하게 된다.

스케쥴러 코드의 swtch가 리턴한 곳부터 코드를 보면 프로세스를 선택하고 컨텍스트 스위치하는 것의 반복임을 알 수 있다.

일반적으로 scheduler의 swtch호출과 sched의 swtch호출이 번갈아가면서 일어난다.

(fork로 allocproc가 호출된 경우 ra가 forkret의 주소로 변경되어 약간의 예외가 있을 수 있다.)

proc 구조체에 tickets 속성을 추가해준다. 보폭은 tickets값의 역수에 비례한다. 즉 tickets값이 클수록 더 자주 스케쥴링되는 경향이 있다.
proc 구조체에 pass 값을 추가해준다. 프로세스가 스케쥴링될 때마다 pass값을 추가해준다.
자식 프로세스의 pass값은 모든 프로세스의 pass값 중 가장 작은 값으로 설정하도록 했다.
- 부모 프로세스의 값을 그대로 설정하는 것과 어떤 것이 나을지 고민했었다.
- 일단 fork를 통해 새로 생성된 프로세스가 빠르게 응답하는 것이 사용성을 좋게 만드는 것이라 생각하여 가장 작은 pass값을 따라가도록 결정했다. 그렇게 하더라도 부모 프로세스와 최대 한 보폭 정도만 차이가 날 것이다. (한 보폭 이상 차이 났더라면 부모 프로세스가 가장 작은 pass값을 가졌음에도 스케쥴링되지 못했다는 것이므로 정책에 모순되는 상황)
마지막으로 스케쥴러에서는 모든 프로세스 중 가장 작은 pass 값을 가진 프로세스를 선택해서 스케쥴링하면 된다!