PintOS | Project1. Threads | 과제 소개

PintOS 프로젝트는 매우 방대하다... 과제 설명서만 해도 몇 페이지지?? 하여간 엄청나게 많은 분량이다. 그래서 과제설명서 중 핵심 내용을 따로 모아놔야 할 것 같다.

 

앞서간 정글 선배님들 덕분에 한글 번역본을 구할 수 있었다.👍👍 감사합니다 잘 써먹겠습니다....!

---

테스트 방법

/PintOS_lab/threads/build 디렉토리에서 컴파일 및 채점을 실행한다.

1. 전체를 컴파일하고 테스트하려면
   • make -> make check
2. 여러 테스트 케이스들을 개별적으로 테스트하려면
   • 예를 들어 alarm-multiple 이라는 테스트케이스를 수행하고 싶다면 make tests/threads/alarm-multiple.result
   • 이 명령은 alarm-multiple 테스트를 수행하고, 결과를 .result 라는 파일에 기록한다. 

 

만일 기존에 실행된 테스트 결과가 이미 최신 상태라면, make: 'tests/threads/alarm-multiple.result' is up to date. 라는 메시지가 출력된다. 기존의 모든 테스트를 clean하고 다시 컴파일하고 싶다면 make clean 한 뒤 다시 실행한다.

---

해야 할 일

0. 기존 코드 이해하기

먼저 과제에서 제공되는 쓰레드 시스템 코드를 읽고 이해합시다. Pintos에는 이미 쓰레드 생성, 쓰레드 종료, 쓰레드 간에 스위치를 하는 간단한 스케쥴러, 그리고 동기화 함수(semaphores, locks, condition variables, and optimization barriers)가 구현되어있습니다.

 

소스 코드의 각 부분들을 꼼꼼히 읽어보면서 무슨 일이 일어나고 있는지 확인해보세요. 원한다면 코드의 아무곳에나 printf()를 넣고 재컴파일 후 실행해서 어떤 일이 어떤 순서로 일어나는지 확인해보세요. 디버거에서 커널을 실행하고 궁금한 지점마다 breakpoint 를 지정하여 코드를 한 발짝씩 확인하고 데이터를 확인해보세요.

 

GDB 디버거를 사용해서 문맥교환에서 어떤 일이 일어나는 지를 천천히 추적해보세요.

 

1. Alarm Clock

과제 목표:
"Reimplement timer_sleep(), defined in devices/timer.c."
- Alarm: 호출한 프로세스를 정해진 시간 후에 다시 시작하는 커널 내부 함수
- 핀토스에서는 알람 기능이 Busy waiting을 이용하여 구현되어 있음
- 본 과제에서는, 해당 알람 기능을 sleep/wake up을 이용하여 다시 구현한다.

Busy waiting? 
- Thread가 CPU를 점유하면서 대기하고 있는 상태.
- CPU 자원이 낭비 되고, 소모 전력이 불필요하게 낭비될 수 있다.

수정해야 할 주요 파일
- thread/thread.*
- devices/timer.*

 

이미 잘 작동하는 timer_sleep()이 구현되어있지만 이는 busy wait 방식입니다. 즉 이는 계속해서 반복문을 돌면서 현재 시간을 확인하고 충분한 시간이 경과할 때까지 thread_yield()를 호출합니다. busy waiting 을 피하도록 다시 구현합니다

 

void timer_sleep (int64_t ticks);

 

timer가 적어도 x번 tick 할때까지 thread 호출의 실행을 일시 중단합니다. 시스템이 idle(다음 thread가 없는) 상태가 아니라면, thread가 정확히 x번의 tick이 발생한 직후에 wake up 할 필요가 없습니다. thread가 적절한 시간동안 대기 한 후 ready queue에 놓이게 해주세요.

 

timer_sleep()은 실시간으로 작동하는 thread에게 유용합니다. (예: 일초에 한번 깜빡이는 커서) timer_sleep()의 인자는 밀리초나 다른 단위가 아닌 타이머의 ticks으로 표현됩니다.

 

TIMER_FREQ 라는 초당 타이머 틱이 있습니다.(= 타이머 인터럽트는 초당 TIMER_FREQ회 발생.) 이 TIMER_FREQ는 devices.timer.h에 정의된 매크로 입니다. 기본값은 100(= 100Hz)이며, 값을 변경할 경우 많은 테스트 실패들이 실패할 수 있으므로 변경하지 않는 것이 좋습니다.

 

TIME_SLICE시간 조각당 틱이 있습니다 . 이 매크로는 threads/thread.c. 에 정의된 매크로입니다. 기본값은 4틱입니다. 이 값을 변경하면 많은 테스트가 실패할 가능성이 높으므로 이 값을 변경하지 않는 것이 좋습니다.

 

timer_msleep(), timer_usleep(), timer_nsleep()와 같이 밀리초, 마이크로초 또는 나노초 동안 sleep하는 별도의 함수가 존재하긴 합니다. 하지만 이 함수들은 필요시 자동으로 timer_sleep()을 호출합니다. 이 함수들은 수정할 필요가 없습니다. project 1에서 구현한 alarm clock 기능은 (프로젝트 4에서는 유용할 수는 있지만) 이후 프로젝트에서는 필요로 하지 않습니다.

 

 

2. Priority Scheduling

implement priority scheduling and priority donation in Pintos.

 

우선순위 스케줄링을 구현해봅시다. 현재 실행중인 쓰레드보다 높은 우선순위를 가진 쓰레드가 ready list에 추가되면 현재 쓰레드는 즉시 프로세서를 새 쓰레드에게 양보해야합니다. 마찬가지로 쓰레드가 락, 세마포어 또는 조건변수를 대기할 때, 우선순위가 가장 높은 대기 스레드를 먼저 깨워야합니다. 쓰레드는 언제든지 자신의 우선순위를 올리거나 내릴 수 있지만, 우선순위를 내렸을 때 해당 쓰레드의 우선순위가 가장 높은 우선순위가 아니게 된다면 CPU를 즉시 양보해야 합니다.

 

(조건 변수?: https://ju-hy.tistory.com/39)
Condition Variable이란?

Condition Variable은 특정 조건을 만족하기를 기다리는 변수라는 의미이다. 따라서 이를 이용하여 주로 thread간의 신호 전달을 위해 사용한다. 하나의 thread가 waiting 중이면 조건을 만족한 thread에서 변수를 바꾸고 signaling을 통해 깨우는 방식이다.

기본적으로 cond_wait()와 cond_signal() 함수를 사용하게 된다. 또한 wait와 signal 내부적으로 unlock()과 lock()이 각각 앞 뒤로 있기 때문에 외부를 lock()과 unlock()으로 감싸야 한다.

 

 

쓰레드 우선순위의 범위는 PRI_MIN(0) 부터 PRI_MAX(63)까지입니다. 숫자가 작을수록 우선순위가 낮으므로 우선순위 0이 가장 우선순위가 낮고, 우선순위 63이 가장 우선순위가 높습니다. 초기 쓰레드의 우선순위는 thread_create()에 대한 인수로 전달됩니다. 이때 다른 우선순위를 선택할 이유가 없으면 PRI_DEFAULT(31)를 사용하세요. PRI_ 매크로는 threads/thread.h에 정의되있고, 이 값들을 변경하면 안됩니다.

 

우선순위 스케줄링에서 중요한 사항은 “우선순위 역전(priority inversion)”입니다. 우선순위가 높은 쓰레드 H, 중간 M 그리고 낮은 L이 있다고 생각해보세요. 만약 L이 락을 갖고있어서 H가 L을 기다려야하고 M이 ready list에 있다면, H는 절대로 CPU를 사용하지 못할 것입니다. 왜냐면 낮은 우선순위의 스레드가 CPU시간을 얻지 못할 것이기 때문입니다. 이 문제에 대한 부분적으로 해결하는 방법은 L이 락을 갖는 동안 H가 L에게 우선순위를 기부(donate)한 다음, L이 잠금을 해제하면 (따라서 H가 획득) 이 기부를 회수하는 것입니다.

 

우선순위 기부를 구현해봅시다. 우선 우선순위의 기부가 필요한 모든 상황을 고려해야합니다. 하나의 쓰레드에 여러 우선순위가 기부되는 multiple donation 상황을 처리할 수 있어야 합니다. 또한 nested donation 즉 H가 M이 가진 락에서 대기하고있고, M은 L이 가진 락에서 대기하고 있다면 M과 L이 모두 H의 우선순위로 상승해야합니다. 필요하다면 8 단계와 같이 nested priority donation의 깊이에 대해 적당한 제한을 둘 수도 있습니다.

 

락에 대한 우선순위 기부(priority donation)를 구현해야 합니다. 다른 Pintos 동기화 생성자에 대한 우선순위 기부를 구현할 필요는 없습니다. 모든 경우에서 우선 순위 스케쥴링을 구현해야 합니다.

 

마지막으로 다음의 함수들을 구현하세요. 이 함수들은 쓰레드가 자신의 우선순위를 검사하고 수정하도록 합니다. 이러한 함수에 대한 골격은 threads/thread.c에 제공되어 있습니다.

 

void thread_set_priority(int new_priority)

현재 스레드의 우선순위를 새 우선순위로 설정합니다. 만약 현재 스레드의 우선순위가 더 이상 높지 않으면 우선순위를 양보합니다.

 

void thread_get_priority(int new_priority)

현재 스레드의 우선순위를 반환합니다. 우선 순위 기부가 있는 경우 더 높은 (기부된) 우선순위를 반환합니다.

 

스레드가 다른 스레드의 우선순위를 직접 수정하는 인터페이스를 제공할 필요는 없습니다. 우선순위 스케줄러는 이후 프로젝트에 사용되지 않습니다.

 

 

 

---

파일 구성 둘러보기

/threads 코드들 

 

init.{c, h}

:  커널을 초기화하는 커널의 메인 프로그램 입니다. 적어도 어떤 것들이 초기화되는지를 알기 위해 main() 함수를 살펴보세요. 여러분만의 초기화 코드를 추가하고 싶어질거에요. 

 

thread.{c, h}

: 기본적인 쓰레드 함수입니다. 이 프로젝트의 대부분의 작업은 이 파일에서 발생할것입니다. thread.h는 thread 구조체를 정의하는데, 4개의 프로젝트에서 모두 이 구조체를 수정하게 될겁니다

 

synch.{c, h}

: 기본적인 동기화 함수들 : semaphores, locks, condition variables, optimization barriers 입니다. 네 번의 프로젝트에서 모두 이 동기화를 사용해야 합니다.

 

/devices 코드들

(키보드, 타이머, 디스크 등) I/O 장치 interfacing 을 위한 소스코드들

 

timer.{c, h}

: 초당 100번 똑딱거리는 시스템 타이머입니다. 이번 프로젝트에서 이 코드를 수정하게 될 것입니다. 

 

partition.{c,h}

: 디스크의 파티션 구조를 이해하세요. 파티션 구조는 하나의 디스크를 독립적으로 사용할 수 있는 여러 개의 region(파티션)으로 나눕니다.

 

 

/lib 코드들

 

/kernel/list.{c,h}

: 이중 연결 리스트의 구현입니다. pintos 코드 전체에서 사용되고, 프로젝트1을 진행할 때 이 코드를 몇 군데에서 사용하는 게 좋을 겁니다. 시작하기 전에 이 코드를 한번 훑어보기를 추천합니다. 특히 헤더 파일의 주석들을 잘 보세요. 

 

 

 

 

 

---

Tips

 

적절한 동기화는 이러한 문제를 해결하는 데 있어 중요한 부분입니다. 모든 동기화 문제는 인터럽트를 끄면 쉽게 해결할 수 있습니다. 인터럽트가 꺼져 있는 동안에는 동시성이 없으므로 race condition이 발생할 가능성이 없습니다. 따라서 모든 동기화 문제를 이 방법으로 해결하고 싶을 수 있지만, 그렇게 하지 마세요. 대신 세마포어, lock, 조건 변수를 사용하여 대부분의 동기화 문제를 해결하세요.