프로젝트1. Threads
핀토스는 아직은 단일 프로세스로 진행된다.
main 함수라는 하나의 문맥 안에 멀티쓰레드로 프로그램을 실행한다.
즉, os는 여러 개의 쓰레드를 관리해야한다.
핀토스는 한 번에 하나의 스레드만을 실행하기 때문에 실행되는 스레드를 제외하고는 모두 비활성화된다. 다음 실행할 스레드를 결정하는 작업을 통틀어 스케줄링(scheduling)이라고 한다.
수정하지 않은 핀토스는 RR방식의 선점형 스케줄링을 사용한다.
1-1. Alarm Clock
1-1-1. 타이머 인터럽트
선점형 스케줄링을 위해서는 [[CSAPP#8-1. 예외상황|예외상황 Exception]]이 반드시 필요하다.
선점을 위해서는 예외상황 중에서도 비동기적으로 발생하는 인터럽트를 발생시켜야 한다.
선점이 필요한 특별한 상황인지를 파악하기 위해서 커널이 CPU를 점유해야만 하기 때문이다.
특별한 상황인지 파악하기 위해 인터럽트를 특별한 상황에만 발생시키려 하면 문제가 순환한다. 즉, 특별한 상황에만 인터럽트를 발생시킬 수 없다.
따라서 선점형 스케줄링을 위해서 컴퓨터는 주기적으로 인터럽트를 발생시킨다.
타이머 인터럽트는 [[CSAPP#8-1-2-1. 인터럽트 Interrupt|하드웨어 인터럽트]]의 일종이다.
하드웨어 타이머는 컴퓨터에 있는 물리적인 하드웨어 모듈로 일정한 주기(틱 ticks)[^1-1]마다 타이머 인터럽트 시그널을 생성한다.
타이머 인터럽트가 발생하면 프로세서는 예외 테이블에서 타이머 인터럽트 핸들러를 호출한다.
타이머 인터럽트 핸들러는 매 틱마다 수행해야 하는 동작을 수행하고 다시 유저 스레드로 돌려놓는다.
[^1-1]: 주기를 변경할 수 있는 타이머도 존재한다.
/* PintOS에서의 타이머 인터럽트 핸들러 */
static void
timer_interrupt (struct intr_frame *args UNUSED) {
ticks++;
thread_tick ();
}
/* Called by the timer interrupt handler at each timer tick.
Thus, this function runs in an external interrupt context. */
void
thread_tick (void) {
struct thread *t = thread_current ();
/* Update statistics. */
if (t == idle_thread)
idle_ticks++;
#ifdef USERPROG
else if (t->pml4 != NULL)
user_ticks++;
#endif
else
kernel_ticks++;
/* RR 방식의 선점형 스케줄러
매 틱마다 TIME_SLICE를 현재 스레드가 초과했는지를 확인하고
초과했다면 다음 스레드에 양보(yield)한다. */
if (++thread_ticks >= TIME_SLICE)
intr_yield_on_return ();
}핀토스에서는 매 틱마다 전체 시스템 틱(전역변수 ticks)를 증가시키고 thread_tick을 호출한다.
timer_interrupt에서 이 내용을 볼 수 있다.
1-1-2. Busy-wait
busy-wait은 스레드 대기 방식의 하나로
특정 조건이 충족될 때까지 CPU를 사용해 루프를 돌며 대기하는 방식이다.
/* Suspends execution for approximately TICKS timer ticks. */
void
timer_sleep (int64_t ticks) {
int64_t start = timer_ticks ();
ASSERT (intr_get_level () == INTR_ON);
while (timer_elapsed (start) < ticks)
thread_yield ();
}timer_sleep함수는 인자로 받은 값만큼의 틱동안 스레드를 대기시키는 함수이다.
thread_yield함수는 현재 스레드를 스레드 대기열 맨 마지막으로 보내고 다음 스레드를 실행시키는, 양보하는 함수이다.
thread_yield함수를 호출하지 않는다면 RR방식이라면 제한시간이 초과되면 다른 스레드에 넘겨줄 것이고 비선점형 방식이라면 계속 CPU 사용을 점유할 것이다.
이를 방지하기 위해 양보함수를 계속 호출하여 CPU 점유를 넘겨준다.
그러나 이 방식에는 두 가지 문제점이 있다.
- 일단 스레드 대기열에 자신을 등록해 두었다가 자신의 차례가 되면 시간을 확인하고 다음 스레에 양보한다. 이 과정에서 컨텍스트 스위치가 일어나며 리소스 낭비가 발생한다.
- 스레드 대기열이 비어있다면, idle 상태라면 while문을 반복하기 위해 모든 CPU 리소스를 사용하리소스를 낭비한다.
이런 문제를 해결하기 위해 정해진 시간을 초과하기 전까지는 대기열에 등록되지 않는 timer_sleep함수를 구현해야한다.
1-1-3. Sleep
sleep 방식은 정해진 시간동안 CPU 사용을 중단하는 방식이다.
즉 다시 깨어나기 전까지는 해당 스레드는 활성화되지 않으므로 다른 컨텍스트에서 시간을 확인하고 깨워줘야 한다.
어떤 스레드가 sleep을 사용할 지 모르므로 다른 스레드가 깨워주는 방식은 불가능하다.
깨어나는 시간이 틱으로 결정되므로 틱마다 작업을 수행하는 타이머 인터럽트 핸들러가 처리하는 것이 적절하다.
이를 구현하기 위해서는 일단 깨어날 시간을 저장하고 잠든 스레드를 기록하는 두 가지 기능이 필요하다.
1-1-3-1. 시간 저장
리눅스커널에서는 스레드를 생성하면
1. 시스템 콜을 처리하고(함수 스택같이)
2. 인터럽트가 발생했을 때 컨텍스트 전환을 위해
스레드별로 커널 스택이 제공된다.
커널스택은 [[가상메모리]]의 커널 영역에 저장되고, 커널스택에는 커널 모드에서의 스택 프레임과 스레드 정보가 저장된다.
(커널 스택은 그림기준 최상단 세그먼트에 저장된다.)
인터럽트 핸들러가 스레드를 깨울지 여부를 결정하기 위해선 잠든 스레드 별 깨어날 시간 정보가 필요하다.
이 정보는 커널 모드에서만 사용하므로 저장할 공간은 커널영역에, 그 중에서도 스레드마다 할당되는 커널스택의 스레드 정보에 저장하는 것이 적절해보인다.
struct thread {
/* Owned by thread.c. */
tid_t tid; /* Thread identifier. */
enum thread_status status; /* Thread state. */
char name[16]; /* Name (for debugging purposes). */
int priority; /* Priority. */
/* Shared between thread.c and synch.c. */
struct list_elem elem; /* List element. */
int64_t sleep_until; // 추가된 부분 /* Time to wake up(Ticks)*/
#ifdef USERPROG
/* Owned by userprog/process.c. */
uint64_t *pml4; /* Page map level 4 */
#endif
#ifdef VM
/* Table for whole virtual memory owned by thread. */
struct supplemental_page_table spt;
#endif
/* Owned by thread.c. */
struct intr_frame tf; /* Information for switching */
unsigned magic; /* Detects stack overflow. */
};코드는 핀토스에서 사용하는 스레드 정보 구조체이다.
sleep_until을 새로운 멤버로 추가하여 스레드가 깨어날 시간(틱)을 저장하도록 하였다.
이 스레드 정보 구조체에는 리스트를 통해서 접근할 수 있기 때문에 리스트 요소(elem) 포인터를 sleep_until에 대한 포인터로 변환해 접근해야 한다.
방법으로는 직접 elem에서 정해진 바이트 수 만큼을 이동하는 방식과 구조체의 포인터를 획득해 ->연산자로 접근하는 방식을 생각할 수 있다.
// 방법 1
struct list_elem_thread {
struct list_elem *prev; /* Previous list element. */
struct list_elem *next; /* Next list element. */
int64_t sleep_until; /* 순서는 struct thread에서와 같아야 한다 */
}
((struct list_elem *)elem)->sleep_until;
// 방법 2
(uint8_t *)elem + offset /* offset은 여기서 16(바이트) */
// 방법 3
list_entry(elem, struct thread, elem)->sleep_until;
// list_entry(LIST_ELEM, STRUCT, MEMBER)는 (STRUCT *) 자료형의 MEMBER 멤버인 LIST_ELEM을 받아서 STRUCT 포인터를 계산하는 매크로이다.방법 1, 방법 3같은 경우에는 나중에 구조체에 멤버를 추가할 경우에 불편해질 것 같아서 범용적으로 쓸 수 있을 것 같은 방법 2를 사용했다.
1-1-3-2. 잠든 스레드 리스트
(계속)
