[CS] Kaist PintOS THREAD, Alarm clock #1

이 문서는 카이스트 핀토스 원유집 교수님의 강의를 참고하여 작성하였습니다.

이 문서는 카이스트 핀토스 프로젝트 가이드라인을 정리한 글입니다.

 

Part 1 : Threads

 

다음 세 가지를 구현한다.

1. Alarm clock

2. Priority scheduling

3. Advanced scheduler

 

#1 Alarm clock

timer_sleep

void timer_sleep (int64_t ticks) 
{
    int64_t start = timer_ticks ();

    while (timer_elapsed (start) < ticks) 
        thread_yield ();
}

start변수에 현재 시간을 저장한다.

timer_elapsed(time) : 들어온 인자로부터 얼마의 시간이 지났는지 반환한다.

이후 while 반복문에서 thread_yield() 함수를 실행한다.

 thread_yield()함수는 CPU를 해제하고 러닝타임을 계산해 while 조건문을 확인한다.

만약 timer_elapse()에서 반환된 값이 ticks보다 낮으면, 다시 CPU를 해제한다.

 

여기서 'CPU를 해제한다'는 뜻은 현재 연산중인 thread를 중지하고 레디 큐 맨 뒤로 보낸다는 뜻이다.

timer_sleep함수는 해당시간동안 sleep 상태로 다른 스레드의 준비상태와 실행 중 상태를 전환한다.

 

 

thread_yield

/* Yields the CPU.  The current thread is not put to sleep and
   may be scheduled again immediately at the scheduler's whim. */
void
thread_yield (void) {
	struct thread *curr = thread_current ();
	enum intr_level old_level;

	ASSERT (!intr_context ());

	old_level = intr_disable ();
	if (curr != idle_thread)
		list_push_back (&ready_list, &curr->elem);
	do_schedule (THREAD_READY);
	intr_set_level (old_level);
}

*curr : 현재 스레드 구조체에 대한 포인터를 얻는다.

old_level = intr_disble() : 인터럽트를 비활성화한다.

list_push_back(&ready_list, &curr->elem) : 현재 스레드를 레디 리스트의 끝으로 옮긴다.

do_schedule(THREAD_READY) : 현재 스레드의 상태를 스레드 준비상태로 변경한다. 그리고 context switch를 한다.

intr_set_level (old_level) : 비활성화한 인터럽트 수준을 다시 되돌린다.

 

구현해야 하는 것

01. sleep_list

static struct list sleep_list;

sleep list 정의하기.

'어디에 선언할 것인가? 또 언제 초기화할 것인가?'

 

02. thread 구조체 수정

/include/threads/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. */

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

 

각각의 스레드는 wake up 하기위한 시간을 가지고있어야 한다.

현재 thread 구조체에 없기때문에 수정해야한다. " alarm time to wake up "

 

local tick : 스레드에 저장되어야 하는 틱.

global tick : 프로세스가 실행된 이후의 시간. local 틱을 생성하고 비교하기위해 필요하다.

어느 시점에 초기화할 것인지가 중요하다.

 

 

위 두 작업을 통해 궁극적으로 기존 timer_sleep의 Busy waiting을 없애자.

void timer_sleep (int64_t ticks) 
{
    int64_t start = timer_ticks ();

    /*
    while (timer_elapsed (start) < ticks) 
       thread_yield ();
    */

    if(timer_elapsed (start) < ticks)
	thread_sleep(start + ticks); //implement by yourself
}

생각해볼 문제점 : if 조건문과 start 선언 중간에 context switching이 발생해서 if문이 무효화 될 수 있다.
이번 프로젝트에서는 이 부분을 채점하지 않겠지만, 좋은 프로그래머가 되기 위해서 고민해볼 것.

 

03. thread_sleep

thread.c

void thread_sleep(int64_t ticks){
  
  /* if the current thread is not idle thread,
	change the state of the caller thread to BLOCKED,
	store the local tick to wake up,
	update the global tick if necessary,
	and call schedule() */
  /* When you manipulate thread list, disable interrupt! */

}

Thread를 Sleep queue에 삽입하는 함수를 추가

timer interrupt가 체크하기 용이하게 해당 sleep queue는 시간순서에 따라 정렬되는 것이 좋다.

(만약, 정렬되어있지 않다면 모든 thread를 검사해야하기 때문에)

 

04. timer_interrupt

timer.c

static void timer_interrupt (struct intr_frame *args UNUSED)
{
    ticks++;
    thread_tick (); // update the cpu usage for running process

    /* code to add: 
	check sleep list and the global tick.
	find any threads to wake up,
	move them to the ready list if necessary.
	update the global tick.
	*/
}

매 tick에서, 어떤 스레드를 sleep queue 에서 wake up 시켜야하는지 체크하고 wake up 한다.

 

05. thread_init

thread.c

void
thread_init (void) {
	ASSERT (intr_get_level () == INTR_OFF);

	/* Reload the temporal gdt for the kernel
	 * This gdt does not include the user context.
	 * The kernel will rebuild the gdt with user context, in gdt_init (). */
	struct desc_ptr gdt_ds = {
		.size = sizeof (gdt) - 1,
		.address = (uint64_t) gdt
	};
	lgdt (&gdt_ds);

	/* Init the globla thread context */
	lock_init (&tid_lock);
	list_init (&ready_list);
	list_init (&destruction_req);

	/* Set up a thread structure for the running thread. */
	initial_thread = running_thread ();
	init_thread (initial_thread, "main", PRI_DEFAULT);
	initial_thread->status = THREAD_RUNNING;
	initial_thread->tid = allocate_tid ();
}

Sleep queue 자료 구조를 초기화하는 코드를 추가