교재를 어느정도 읽었고 본격적인 과제인 lottery scheduler 구현에 착수했다.

난수 생성기가 만만해보여 먼저 찾아봤다. 적당히 복붙해서 구현하려 했으나 균일성, 편향제거, 동시성, 병렬성등 고려해야 할게 많다는 사실을 새삼 깨달았다. 그동안 단일 스레드 환경에서 편하게 살았음을 실감했다.

현재의 스케쥴러 구현인 라운드 로빈 방식을 이해해볼겸 루프안에서 fork를 사용해 n개의 프로세스를 생성하는 간단한 코드를 작성했다.

프로세스가 기대와 달리 n개가 생성되는게 아닌, (말 그대로) 기하급수적으로 생성되어서 원인을 생각해봤다. fork는 프로세스를 처음부터 실행하는게 아니라 현재까지 실행된 상태를 복제하여 새로운 프로세스를 만들고, 자기자신의 프로세스도 계속해서 실행하기 때문이다.

그렇기 때문에 n개의 프로세스를 만들려면 fork를 부모 프로세스만 실행할 수 있도록 자식 프로세스는 원하는 작업을 실행하고 루프를 탈출시켜야 한다는 일종의 fork 사용에 대한 관례를 배웠다.

사실 책 앞에 다 나왔던 내용인데 대충 읽었더니 이렇게 멀리 돌아가는 고생을 하고 있다. ㅋㅋㅋ

scheduler 함수의 분석을 시작했다. scheduler는 컨텍스트 스위칭을 위해 swtch함수를 호출하는데, 이 함수는 어셈블리로 작성되어 있는지라 언제 리턴 되는지 더더욱 파악하기가 어려웠다. (사실 어셈블리가 아니었어도 파악하기는 쉽지 않았을거다.)

Claude Code에게 코드베이스 분석을 맡기고 몇가지 문답을 통해 타이머 인터럽트가 trap 핸들러를 호출하고, trap 핸들러가 yield->sched->swtch흐름으로 호출하여 scheduler함수로 돌아간다는 사실을 파악했다. 이 과정이 반복되며 프로세스는 순차 실행되고 그 사이사이에 scheduler가 교차 실행된다는 것을 알게 되었다.

책에 설명이 있긴 하지만 코드를 한땀한땀 분석했으면 오래 걸렸을텐데, Claude Code로 시간을 아낄 수 있었다. 예전엔 공부할 엄두가 안나던 것들이 LLM덕분에 조금은 가벼운 마음으로 시작해 볼 수 있게 되었다. 좋은 세상이다.

스케쥴러가 어떤 프로세스를 실행중인지 확인해보기 위해 컨텍스트 스위칭 대상이 되는 프로세스의 pid를 출력해봤다. 기본 구현은 라운드 로빈이기 때문에 순서대로 순환되며 출력 될거라 예상했지만 순서가 뒤섞여서 출력이 되었다. 원인은 CPUS 옵션을 주지 않으면 기본값이 3으로 설정되기 때문에 여러 스케쥴러가 동시에 실행되어서 그런 것이었다. CPUS를 1로 설정하자 기대한대로 순서대로 순환되어 출력하는 것을 확인하였다.

settickets, getpinfo를 구현하고 ps를 구현했다. pstat을 전역 변수로 두고 관리하려 했으나 proc, pstat을 각각 관리하면 복잡해 진다는 것을 깨달았다. 다른 스터디원분이 먼저 작성하신 코드를 참고하여 proc에 ticks를 추가하고 getpinfo 호출시 pstat을 만드는 방향으로 계획을 바꿨다. 유저 공간에서 시스템콜에 포인터를 넘기고, 그 포인터에 값을 채워받는 것을 구현하는게 난관이었는데 Claude Code가 해결해줘서 넘어갔다.

lottery scheduler를 구현했다. 이어서 스케쥴러가 정해진 티켓 비율만큼 프로세스를 실행하는지 테스트하는 프로그램을 작성하기 위해 계획을 세웠다. 자식 프로세스의 pid를 알면 일정 주기마다 getpinfo를 호출하여 프로세스가 실행된 tick을 구해 계산 할 수 있을 것이다. 그런데 부모 프로세스가 자식의 pid를 알려면 어떻게 해야하지? 여기서 갑자기 혼란이 생겼다.

fork의 반환값은 0이면 자식이고 0보다 크면 부모이다. 0보다 작다면 실패이다. 이것을 사용하면 포크를 실행한 부모 프로세스인지 포크로 만들어진 자식 프로세스인지 알 수 있다.

내가 혼란스러웠던 부분은 코드를 작성하는 입장에서 fork의 호출은 한 번이지만 이후 실행은 2개로 갈라져서 반환 값이 2개가 된다는 사실을 정확히 인지하지 못해서였다. 부모인지 자식인지 판단하는 코드를 나눠서 생각하지 못하고 오로지 부모 입장에서만 생각하다보니 0도 부모가 리턴 받는다고 착각을 했던 것이다.

이제 부모가 자식을 더 잘 알 수 있게 되었으니 마저 코딩을 하도록 해야겠다.

lottery scheduler 구현을 완료했다. https://github.com/JsonKim/xv6-riscv-for-ostep-with-twitter/pull/2 이제 stride 구현하러 가자.

스터디에 참여하고 계신 조교(?)님 께서 lottery scheduler 구현을 리뷰해주셨다. 혹시나 잘못 이해하고 구현한 부분이 있을까봐 걱정했는데, 리뷰해주신 덕분에 잘못된 부분은 없음을 확인했다. 더불어서 C로 코딩할때 유의해야 할 부분들을 배울 수 있었다.

stride 구현에 앞서 어떻게 동작하는건지 정리해봤다.

• 모든 프로세스는 각자의 '보폭(stride)'을 가진다.
• 스케쥴러가 프로세스를 실행시키면 해당 프로세스는 'stride'만큼의 '거리(pass)'를 이동한다.
• 스케쥴러는 항상 가장 '짧은 거리를 이동한(pass가 가장 작은)' 프로세스를 실행시킨다.
• 결과적으로 보폭이 작을수록 더 자주 실행된다.

몇가지 고려해야 할 것들이 떠올랐다.

• stride로 바뀌면 lottery와는 달리 더 자주 실행되어야 할 프로세스에 작은 값을 부여해야한다. 사용자 입장에서 좋은 방식인가?
• 신규 프로세스 실행 비율에 대한 공정성이 지켜지는지?
• pass가 누적되면 overflow 될 가능성은 없나?
• 가장 작은 pass를 찾는 효율적인 방법

그리고 다음과 같이 결정했다.

• 우선순위를 정하는 API인 setticket은 그대로 유지하자.
• tickets의 반비례되는 수인 stride를 만들기 위해 max_tickets(교재의 L)를 정한다.
  • stride = L / tickets
• 신규 프로세스에는 현재 실행중인 프로세스중에서 가장 작은 pass를 부여하여 공정성을 유지한다.
• pass를 uin64로 지정하고 max_tickets를 2^32로만 잡아도 최대 42.9억번 정도의 tick이 지나야 overflow가 발생한다. 지금은 고려하지 말자.
• 초기 구현은 선형탐색으로 단순하게 구현하고 이후 최적화를 하자.

https://github.com/JsonKim/xv6-riscv-for-ostep-with-twitter/pull/3 stride scheduler 의 구현을 완료했다. 이제 교재를 읽으러 가자.