Here's my dents in the universe

pintos를 유랑하는 히치하이커를 위한 안내서 (Project 1)

0. 큰 그림

1) 코드를 읽어보자

핀토스 스타팅 포인트

처음 핀토스를 마주하면 어디에서부터 시작해야할지 몰라 난감할 것이다. 나 역시 그랬다. 핀토스의 모든 코드를 읽고 시작할 필요는 없다. Project 1, 2, 3, 4를 거치면서 어짜피 대부분의 코드를 읽게 될 것이다. 이해할 수 있는 것부터 하나씩 읽어나가면 된다. 처음에는 잘 이해가 가지 않아도, 읽은 코드의 양이 쌓일수록 모든 것이 한 번에 이해될 것이다. 모든 일이 그렇듯 아주 작은 것에서부터 시작하면 된다. 조급해할 필요 없다.

Project 1을 진행하는 데에 필요한 코드 파일의 수는 많지 않다. src/threads 폴더 내부의 thread.h, thread.c, synch.h, synch.c 파일을 주로 읽거나 수정하게 될 것이고, 이외에 src/devices 폴더 내부의 timer.h, time.c 를 읽게 될 것이다. 파일, 함수마다 주석이 달려있고, 거의 모든 코드가 define, enum 타입 선언 등으로 인터페이스화 되어있어 코드를 읽기가 매우 수월함을 알게될 것이다. (더불어, 월드클래스의 코드는 이렇게 관리된다는 것을 느낄 수 있다)

vscode 기능을 활용해 코드 쉽게 읽기

나는 vscode를 이용해 핀토스 프로젝트를 진행했다. vscode는 마이크로소프트가 개발한 텍스트에디터로 다양한 추가기능을 다운로드 받아 추가할 수 있는 것이 특징이다. 내가 핀토스 프로젝트를 진행하며 아주 많은 도움을 받았던 vscode의 유용한 기능들을 알아보자.

Go to definition Ctrl + click 키보드의 Ctrl 버튼을 클릭한 채로 함수의 이름을 클릭하면, 그 함수의 definition을 찾아 보여준다. 핀토스와 같이 수없이 파일과 함수가 있는 프로젝트를 진행하면서, ‘이 struct 내부에 어떤 변수가 있더라?’, ‘이 함수의 내부가 어떻게 구현되어 있더라?’ 궁금해지면 그때그때 파일을 검색할 필요없이 Ctrl + click을 통해 함수의 내부를 살펴보았다. 원래 위치로 돌아오고 싶을 때는 Alt + ← 로 돌아올 수 있다.

전체 검색 Ctrl + shift + F 핀토스 프로젝트 전체에서 검색 결과를 찾아준다. 특정 함수가 어떤 함수의 내부에서 호출되었는지 검사하고 싶을 때 사용했다. 특히 어떤 문자열을 드래그하고 ctrl + shift + F 를 키보드로 입력하면 따로 입력할 필요없이 바로 검색할 수 있어서 편리했다.

핀토스가 실행되는 과정

Pintos를 실행했을 때 동작하는 첫 모듈은 threads/loader.S에 있는 로더이다. PC BIOS는 메모리에 로더를 로드하고, 로더는 디스크에서 커널을 찾아 메모리에 로드한 다음, 시작 지점으로 점프한다. 커널은 init.c 내 main() 함수에서 BSS, thread, console 그리고 메모리 관련된 것들을 포함한 여러 초기화 과정을 수행한다. 커널은 thread_init() 함수에서 main thread로 지정되고 struct thread를 할당 받는다. main thread 또한 초기화를 마친 후, run_actions() -> run_tasks() -> run_test()를 통해 command line에서 지정해 주었던 테스트를 수행한다. 그리고 모두 마치고 리턴하면, shutdown() 및 thread_exit() 을 통해 main thread가 종료된다. 즉, 커널을 종료한다.

2) thread.c

thread의 구조

Pintos 내 thread의 데이터 구조는 “threads/thread.h”에 struct thread(아래 오른쪽 그림)로 정의되어 있다. 각 struct thread는 4KB 크기의 페이지(아래 왼쪽 그림)에 저장된다. 4KB의 페이지 내에서 struct thread 내 데이터들은 하단에 저장되고, 상단 공간에는 thread의 kernel stack이 저장된다. kernel stack은 위에서부터 아래 방향으로 쌓이게 된다.

그리고 위 구조로 인해 thread 및 kernel stack은 두 가지 특징을 가진다.

  1. Thread는 항상 1KB 미만이 되도록 해야 한다. 왜냐하면, 너무나 커질 경우 kernel stack이 자리할 수 없게 된다.
  2. Kernel stack 또한 무한정 커지도록 하면 안된다. 만약 stack이 넘친다면 thread 상태에 영향을 끼질 것이다. 그러므로 kernel function들은 non-static local variable을 stack에 쌓는데 있어서, 큰 struct data나 array를 위치시켜서는 안된다. 대신 dynamic allocation을 사용해야 한다.

만약 stack overflow 문제가 발생한다면, thread_current() 함수에서 failure가 발생하게 되는데, 이는 위 struct thread에서 정의된 magic 변수의 상태가 THREAD_MAGIC으로 변경되며 감지되고, 이에 의해서 overflow를 감지하여 오류를 발생시킨다. 또한 elem 변수는 두 가지의 목적을 가지는데, run queue의 변수이기도 하면서 semaphore wait list의 변수가 되기도 한다. 즉, 각각에 있어서 배타적으로 존재하면서, ready 상태의 thread가 run queue에 있도록 하고, 반면 block 상태의 thread는 semaphore wait list에 있도록 한다.

Thread 구조 초기화

Thread system은 thread.c 내 thread_init() 함수에서 초기화된다. tid_lock, ready_list, all_list가 초기화되며, 현재 thread의 상태는 THREAD_RUNNING으로 그리고 tid는 초기값으로 업데이트된다. 그리고 최초의 커널 thread를 main thread로 지정한다. all_list는 모든 프로세스를 최초로 scheduling이 되면서 이 리스트에 추가되고 종료 시 리스트에서 제거된다. ready_list는 THREAD_READY 상태의 프로세스들의 리스트로 ready 상태이지만 아직 실제로 동작 중이지 않은 프로세스에 해당한다. 초기화가 모두 완료되면 thread_start()가 실행되게 된다.

Thread scheduler 시작과 interrupt 활성화

Thread 시스템이 초기화되면 thread_start() 함수가 실행되게 된다. semaphore를 초기화하고, idle한 thread를 thread_create() 함수를 통해 생성한다. thread_create() 함수 내에서는 입력받은 매개변수를 바탕으로 thread 메모리를 할당하고 thread를 생성한다. 그리고 kernel_thread(), switch_entry(), switch_threads()를 위한 각각의 stack frame(kernel_thread_frame, switch_entry_frame, switch_threads_frame)을 생성한다. kernel_thread_frame은 해당 thread가 수행할 함수와 그 함수를 위한 보조 정보 그리고 thread가 저장을 필요로 하는 eip 레지스터를 담게 된다. 그리고 나머지 두 개의 stack frame은 해당 함수들이 저장을 필요로 하는 레지스터 정보를 담게 된다. 이 두 함수는 thread switching 시에 호출된다. thread_create() 함수가 종료되면, intr_enable() 함수가 실행되어 interrupt를 활성화하고 thread을 생성한다.

Thread switching

매 timer tick마다 timer interrupt handler에 의해 thread_tick() 함수가 실행된다. 이 함수는 interrupt context에서 실행되며, tick 단위로 실행되어야 하는 코드는 thread_tick() 함수 내에서 처리할 수 있다. 이 함수 내에서는 TIME_SLICE마다 해당 timer interrupt handling이 끝나면 thread_yield() 함수를 호출하여 thread switching이 발생하게 된다.

thread_yield() 함수는 interrupt context가 아닌, interrupt가 발생한 시점에 실행되고 있었던 thread의 context에서 실행된다. 현재 running thread를 ready_list에 삽입하고 ready status로 만든다. 그리고 schedule() 함수를 호출해 다음에 run 할 thread를 찾아 scheduling한다.

schedule() 함수는 현재 thread를 변수 cur에 기록하고, 다음에 실행할 thread를 next_thread_to_run() 함수를 통해 next 변수에 기록한다. 그 후에 둘을 비교한 후에 switch_threads() 함수를 통해 thread를 switching 한다. 후에 thread_schedule_tail() 함수를 통해 새 thread를 실행 중으로 표시한다.

3) Synch.c

세마포어 semaphore

semaphore는 concurrent system에서 여러 프로세스가 사용하는 공동 자원에 접근하는 프로세스의 수를 제한하기 위해 사용된다. 공동 자원에 접근하는 프로세스(스레드)는 세마포어를 down 시키고 공유 자원에 접근한다. 접근 가능한 프로세스 수를 초과한 경우(세마포어가 0) 프로세스를 blocked status로 바꾼다. 즉 wait해야한다는 소리이다.

struct semaphore 
  {
    unsigned value;             /* Current value. */
    struct list waiters;        /* List of waiting threads. */
};

semaphore는 2가지 연산이 가능하다.

  1. down(“P”): semaphore의 value가 양수이면 1 감소시킨다.
  2. up(“V”): semaphore의 value를 1 증가시키고, waiting thread가 있을 시 하나를 깨운다.

락 lock

lock은 semaphore의 특수한 한 형태이다. lock은 최초 value가 1로 설정되어 있다. lock은 file에 대한 동시접근을 하나의 thread로 제한할 때 유용하게 사용된다.

struct lock 
  {
    struct thread *holder;      /* Thread holding lock (for debugging). */
    struct semaphore semaphore; /* Binary semaphore controlling access. */
  };

lock은 semaphore와 마찬가지로 2가지 연산이 가능하다.

  1. release: semaphore의 up과 같은 연산
  2. acquire: semaphore의 down과 같은 연산

1. Alarm clock

기존 구현 방식

Thread를 sleep 시키기 위해 현재 timer_sleep() 함수는 while loop를 돌면서 주어진 ticks만큼 반복적으로 thread_yield() 함수를 호출한다. 이러한 loop 기반의 waiting은 (busy-waits)는 CPU 사이클의 낭비가 심하다. 또 timer tick보다 길게 interrupts를 off 해놓으면 timer tick을 잃어버릴 위험이 있다.

새로운 구현

기존 loop 기반에서 sleep/wake up 기반으로 구조를 변경한다. timer_sleep() 호출 시 thread를 ready_list에서 제거하고, sleep_list에 추가한다. 이후 wake up의 경우 timer interrupt가 발생 시 tick을 체크하여 시간이 다 된 thread는 sleep_list에서 삭제하고 ready_list에 추가한다.

2. Priority scheduling

기존 구현 방식

현 pintos의 thread scheduling 구현방식은 round-robin 방식으로 priority에 대한 고려가 되어있지 않다. 새로 create 되거나 blocked된 thread는 ready_list의 맨 뒤에 list_push_back되고 있고, 다음에 실행할 thread를 선택할 때에도 list_pop_front 함수를 통해 ready_list의 가장 앞 thread가 선택되고 있다. (ready_list가 비어있을 경우 idle thread를 실행한다)

semaphore 역시 struct 내부에 대기 thread를 저장해놓은 waiters 리스트가 있는데, 이 역시 sema_down()에서 list_push_back()으로 삽입되어, sema_up()에서 list_pop_front()로 꺼내진다(priority가 구현되어 있지 않다.)

새로운 구현

  1. Priority에 따른 우선순위 부여하기

Priority가 높은 thread가 새로 thread_create() 되거나, ready_list에 현재 running 중인 thread보다 높은 priority의 thread가 들어올 경우(thread_unblock, thread_yield 함수 호출 시), 현재 thread는 즉시 프로세서를 yield 할 수 있도록 한다. 이를 구현하는 함수인 check_highest_priority()를 구현하여 위 함수의 호출부분에 삽입한다.

  1. Priority inversion 문제를 해결하기

낮은 priority를 가진 thread가 lock을 release하는 과정에서 priority가 높은 thread가 낮은 thread를 기다려야 하는 priority inversion이 생길 수 있다. 이 경우 lock을 release하는 thread의 priority를 높은 priority의 thread와 같은 값으로 변경하는 방법으로 해결하는데, 이를 priority donation이라 부른다.

Priority donation을 위해서는 lock을 리스트로 관리할 필요가 있다. lock_list 자료구조를 thread struct 내부에 선언한다. Lock을 release한 이후에는 해당 thread는 다시 원래의 priority로 돌아와야 하므로 thread struct에 기존 priority를 저장해놓을 수 있는 변수 priority_before를 추가한다. Multiple donation의 경우 위 과정을 loop를 통해 반복함으로써 해결한다. 또 thread의 priority가 변화하는 경우(thread_set_priority) lock 소유 변화가 생길 수 있으므로 이때 priority_donation()함수를 수행해 donation 필요 유무를 검사한다.

3. Advanced scheduler

기존 구현 방식

Advanced scheduler의 경우 가이드를 참고하면, BSD scheduler와 유사한 Multi-Level Feedback Queue scheduler를 구현하여 시스템에서 실행 중인 작업에 대한 평균 응답 시간을 줄이는 것이 목표이다. 하지만 현재 Pintos에서는 이와 관련된 scheduler가 구현되지 않았다. 단지 main() 함수에서 parse_options() 함수가 실행되면서 인자를 받게 되는데, 이때 -mlfqs 인자를 받게 되면 thread_mlfqs 변수가 true로 설정되면서, multi-level feedback queue scheduler를 이용할 수 있도록 코드가 구성되어 있다.

새로운 구현

전체적으로 Pintos B. 4.4BSD Scheduler 내 내용을 바탕으로 새로운 구현을 설계하였다. 구현할 Multi-Level Feedback Queue schedulr의 목적은 실행 준비가 된 thread의 여러 queue를 유지하며, 각 queue는 다른 우선 순위의 thread를 보유한다. 주어진 시간에 scheduler는 우선 순쉬가 가장 높은 비어 있지 않은 queue를 선택하고, queue 내 thread를 선택한다. 우선 순위가 가장 높은 queue에 여러 thread가 포함된 경우 round robin 순서로 실행된다.

다음 공식들은 위와 같은 scheduler를 구현하는 데 필요한 계산을 요약합니다. 모든 thread는 제어 하에 -20에서 20 사이의 nice 값을 갖습니다. 각 thread는 또한 0(PRI_MIN)에서 63(PRI_MAX) 사이의 우선 순위를 가지며, 4 tick마다 다음 공식을 사용하여 다시 계산됩니다. nice 값은 처음 0으로 시작하고, 우선 순위를 낮춰야 할수록 큰 양수값을 가지게 됩니다.

우선 순위 = PRI_MAX-( recent_cpu / 4)-( nice * 2)

recent_cpu는 thread가 최근 수신한 CPU 시간을 측정한다. 각 timer tick에서 실행 중인 thread의 recent_cpu가 1씩 증가한다. 초당 한 번씩 모든 thread의 recent_cpu 가 다음과 같이 업데이트된다.

recent_cpu = (2 * load_avg) / (2 * load_avg + 1) * recent_cpu + nice

load_avg는 지난 1 분 동안 실행할 준비가 된 평균 thread 수를 추정한다. 부팅시 0으로 초기화되고 다음과 같이 초당 한 번씩 다시 계산된다.

load_avg = (59/60) * load_avg + (1/60) * ready_threads

여기서 ready_threads는 업데이트시 실행 중이거나 실행할 준비가 된 thread 수이다 (유휴 thread 제외).

위 공식들에서 priority, nice 및 ready_threads는 정수이지만 recent_cpu 및 load_avg는 실수이다. 불행히도 Pintos는 커널을 복잡하게 만들고 느리게 할 수 있기 때문에 커널에서 부동 소수점 산술을 지원하지 않는다. 따라서 이러한 실수 연산을 하는 함수도 추가하여 위 식을 계산할 수 있도록 해야 한다. 소수점 연산의 경우 fixed-point number representation을 이용하여 구현한다. 32 bit 내에 오른쪽 14 bkt를 소숫점으로 그리고 그 다음 17 bit를 정수로 제일 왼쪽에 sign bit로 정의한다. 그리고 integer를 fix-point로 혹은 fix-point를 integer로 변환하는 함수를 정의한다. 그리고 fixed-point끼리 더하기, 빼기, 곱하기 그리고 나누기 연산을 하는 함수를 추가한다.

위 내용은 2020 Fall, POSTECH CSED312 운영체제 수업에서 진행한 내용을 바탕으로 하였으며, 수업자료와 Stanford Pintos Guide에 기초를 두고 있습니다.