PintOS Project1: Threads

Alarm Clock

카이스트 PintOS 공식 문서: https://casys-kaist.github.io/pintos-kaist/
PintOS 코드 참고용 깃허브: https://github.com/prkty/KJ_pintos

컴퓨터는 켜지고 나서부터 스레드를 관리하기 위해 틱(초당 100회로 10ms)이라는 단위마다 스레드를 효과적으로 관리합니다. PintOS에서도 해당 방법을 통해 스레드를 관리합니다. 오늘 구현해야되는 해당 코드에 대해서 작성하는 것입니다.

기본적으로 Busy Wait (바쁜 대기) 상태로 thread.c 의 thread_yield() 라는 함수를 통해 구현되어 있습니다. 그러나 해당 방식은 시스템의 자원을 많이 낭비하는 방식으로 개선하기 위한 방법을 Sleep and Wakeup 을 통해 다시 구현합니다.

본격적으로 코드를 작성하기 앞서…
device / timer.c 의 주석 내용과 init과 같은 주요 함수들은 완벽히 이해하는 것을 추천합니다. threads / thread.c 는 timer.c와 관련된 부분을 학습하여 주시고, 그 외에 thread.h 와 같은 부가적인 파일은 필요에 따라 확인하시는 것을 추천드립니다.

꿀팁: Visual Sutdio Code의 ‘Go to Definition’ 등의 4가지 기능을 유용하게 사용해보세요!
원래의 함수와 참조된 코드들을 통해 형식과 사용법을 터득할 수 있습니다.

Clock.c

Alarm Clock 과제와 관련된 제일 주력으로 수정하는 파일입니다. 이미 써져 있는 내용이 많아 생략하고 필요한 부분만 설명을 하겠습니다. 기본적으로 처음들어오는 모든 스레드는 sleep 상태로 전환됨을 인지하고 코딩하시면 좋습니다.

...
static struct list sleep_list;   //// 잠재울 리스트 선언

/* 8254 프로그래머블 인터벌 타이머(PIT)를 설정하여
   초당 PIT_FREQ 횟수를 인터럽트하고
   해당 인터럽트를 등록합니다. */
void
timer_init (void) {
	/* 8254 입력 주파수를 TIMER_FREQ로 나누면, 
	   가장 가까운 쪽으로 반올림됩니다. */
	uint16_t count = (1193180 + TIMER_FREQ / 2) / TIMER_FREQ;

	outb (0x43, 0x34);    /* CW: counter 0, LSB then MSB, mode 2, binary. */
	outb (0x40, count & 0xff);
	outb (0x40, count >> 8);

	intr_register_ext (0x20, timer_interrupt, "8254 Timer");  // 중요! 틱마다 타이머 인터럽트를 실행
	list_init(&sleep_list);    //// 초기화를 위해 사용 (쓰레기값 방지)
}
...

전체 변수 선언에 잠재울 리스트 선언을 위해 static struct list sleep_list; 를 추가하고, timer_init 함수에서 초기화를 위해 사용하기 위해 list_init(&sleep_list); 이 추가되어야 합니다.

wakeup_cmp 과 timer_sleep 함수

// 비교를 통해 sleep_list에 적절하게 정렬
bool wakeup_cmp (const struct list_elem *a, const struct list_elem *b, void *aux UNUSED) {
	struct thread *T_A = list_entry(a, struct thread, elem);
	struct thread *T_B = list_entry(b, struct thread, elem);
	
	if(T_A -> wakeup == T_B -> wakeup)
		return T_A -> priority > T_B -> priority;
	return T_A -> wakeup < T_B -> wakeup;
}

/* 대략적인 TICKS인 타이머 틱에 대한 실행을 일시 중지합니다. */
// 해당 코드의 문제점은 바쁜 대기로 리소스를 잡아 먹는다는 점이다.
// 해결을 위해서는 스레드 호출전까지 또는 일정 타이머 전까지 sleep 해야한다.
void
timer_sleep (int64_t ticks) {
	struct thread *curr = thread_current();
	curr -> start = timer_ticks();
	curr -> wakeup = timer_ticks() + ticks;

	ASSERT (intr_get_level () == INTR_ON);   // [오류] 현재 인터럽트가 ON이라면 함수 진행

	enum intr_level old_level = intr_disable ();  // 인터럽트 받지 않음 (밑의 과정중에 잘못됨을 방지)
	list_insert_ordered(&sleep_list, &(curr -> elem), wakeup_cmp, NULL);
	thread_block();
	intr_set_level (old_level);  // 인터럽트를 받음 (전단계로 복귀)
}

wakeup_cmp : 밑에 나오는 list_insert_ordered 에서 sleep_list 에 적절한 우선순위, wakeup 순위에 따라 정렬하기 위해 사용하는 함수 입니다.

timer_sleep : list_insert_ordered(&sleep_list, &(curr -> elem), wakeup_cmp, NULL); 을 통해 현재 스레드를 잠재우기 위해 다음 틱까지의 범위(깨울 틱)까지 구조체의 요소로 동봉해서 sleep_list 라는 잠자는 스레드가 있는 곳으로 보냅니다. thread_block(); 을 통해 잠재운 스레드를 블록처리(일시 사용 불가)합니다. 그러나 해당 과정 수행중에 꺼지거나 하는 잘못된 현상을 방지하기 위해 enum intr_level old_level = intr_disable (); 을 통해 인터럽트를 받지 않습니다. intr_set_level (old_level); 를 통해 다시 풀어줄 수 있습니다. 중간의 ASSERT는 오류를 대응하기 위한 코드입니다.

timer_interrupt 함수

/* 타이머 인터럽트 핸들러. */ 
static void
timer_interrupt (struct intr_frame *args UNUSED) {

	ticks++;
	thread_tick ();

	while(!(list_empty(&sleep_list))) {
	struct thread *T1 = list_entry(list_front(&sleep_list), struct thread, elem);

	if (T1 -> wakeup <= ticks) {
	list_pop_front(&sleep_list);
    thread_unblock(T1);
	}
	else
		break;
	}
}

timer_interrupt : 원래는 컴퓨터가 켜지고 나서 tick이 지나가는 시간을 ticks에 저장하는 함수입니다. 그러나 저희는 이러한 특성을 이용하여, tick이 지날때마다 스레드의 wakeup값(스레드의 누적 ticks 값)보다 ticks이 크거나 같은 스레드를 검사합니다. 검사후에는 sleep_list에서 pop을 하며 앞전에 블록(일시 사용 불가)했던 스레드를 사용 가능한 상태로 바꿉니다.

Thread.h

 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. */
	int64_t start;     //// 시작 시간
	int64_t wakeup;    //// 일어나는 시간

	/* Shared between thread.c and synch.c. */
	struct list_elem elem;              /* List element. */

#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. */
};

사실상 include / threads / thread.h 에서 추가 한부분은 두줄 입니다.

시작 시간을 스레드 구조체에 저장하기 위한 int64_t start; 와 스레드가 일어나는 시간을 저장하기 위한 int64_t wakeup; 입니다. 앞전에 이야기 했지만 clock.c 에서 sleep_list 에 일어날 시간을 저장하기 위한 용도로 헤더에 선언을 해주었습니다.

테스트하기

1. 전에 테스트했던 파일들을 삭제하기 위해 PintOS 최상위 폴더와 threads 폴더에서 make clean 합니다.
2. PintOS 최상위 폴더에서 source ./activate 를 수행합니다.
3. cd threads 를 통해 threads 폴더에서 make check 를 통해 전체 검사를 수행합니다.

이후에 버그나 어떤 이유에서 FAIL이 된다면 테스트 케이스 1개만 실행 가능합니다.

1. 먼저 threads 폴더에서 cd build 를 통해 폴더를 이동합니다.
2. make tests/threads/alarm-priority.result VERBOSE=1 .result 확장자에 원하는 테스트 케이스를 입력하면 됩니다.
3. 그러나 보통 threads 폴더에서 make check 하는 방식을 추천합니다.

다음과 같이 19 of 27 tests failed로 나오면 성공입니다.

많이 복잡하고 설명할 내용이 많지만, 디테일에 들어가면 정리할 내용이 너무 방대해집니다. 각자 푸는 방식이 다르니 어느정도에 참고만 하여 각자의 방식을 찾는 것이 중요하다고 생각합니다.

첫 문제부터 어려워서 솔직히 걱정이 됩니다. 그러나 끝까지 풀어낼 수 있도록 공부해보도록 하겠습니다.