PintOS Project 1 : Thread(Alarm Clock)

첫 번째 Thread 프로젝트에서는 Thread들이 어떻게 관리되는지, 외부 인터럽트를 통한 CPU scheduling, 인터럽트 비활성화를 통한 공유자원 접근에 대해서 알아야 했다. 

 

 

 

 

 

 

 

 

 

 

Thread의 상태는 4개로 분류 할 수 있다.
1. Running : Thread가 CPU를 점유하여 실행 중인 상태
2. Ready : Thread가 실행하기 위한 준비를 마친 상태 (cpu sheduler에 의해 실행될 예정)
3. Blocked(wait) : Thread가 어느정도의 CPU 점유를 한 후, 다른 Thread에게 CPU 점유를 양보한 상태
4. Dying : Thread가 자신의 할 일을 모두 마친 상태

 

 

이렇게 Thread의 상태는 인터럽트 또는 CPU 스케쥴링에 의해서 변경된다. 이 과정에서 중요한 것은 Thread는 공유 자원을 사용하기 때문에 경쟁조건(race condition)이 발생할 수 있고, 교착상태가 되어 무한루프를 도는 상황, 즉 동기화문제가 발생할 수 있다. 따라서 몇 가지 경우에는 인터럽트를 비활성화 시켜주고 작업을 진행해야 할 때가 필요하다. 동기화 문제를 해결함으로써 데이터의 일관성을 유지할 수 있으며, 프로그램의 성능을 향상 시킬 수 있다. 

 

CPU 스케줄러는 언제 스케줄링을 결정하는가 ?
1. 실행상태(running)에서 대기상태(blocked)로 전환(switching) 될 때
2. 실행상태(running)에서 준비상태(ready)로 전환(switching) 될 때
3. 대기상태(blocked)에서 준비상태(ready)로 전환(switching) 될 때
4. 종료될때(terminated)

1번과 4번 상황에서만 스케줄링이 발생하는 것을 비선점형(non-preemptive) 스케줄링이라고하고, 이외 모든 스케줄링은 선점형(preemptive) 스케줄링이라고한다.

 

 

선점형 스케쥴링 (preemptive scheduling)

현대 운영체제가 사용하고 있는 방식으로, 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 이를 강제로 뺏을 수 있는 방식. 알고리즘에 따라 강제로 중단시키고 다른 프로세스에 CPU를 할당하는 방식이다. 처리 시간이 매우 긴 프로세스의 CPU 사용 독점을 막을 수 있어 효율적인 운영이 가능하지만 잦은 컨텍스트 스위칭으로 인해 오버헤드가 커질 수 있다.

 

 

 

비선점형 스케쥴링  (Non - preemptive scheduling)

어떤 프로세스가 CPU를 점유하고 있다면 이를 뺏을 수 없는 방식. 강제로 프로세스를 중지하지 않는다. 따라서 문맥 교환 (Context switching)으로 인한 부하가 상대적으로 적지만 프로세스의 배치에 따라 효율성 차이가 많이 나게 된다.

 

 

 

---

 

 

 

 

skeleton 코드의 CPU scheduling은 busy wait 방식으로 되어 있다. busy wait이란 ready_list에서 Thread가 CPU 점유를 계속적으로 확인하는 방식이다. 따라서 잦은 context switching 으로 인한 비용이 크다. 

 

Thread A가 생성되어 현재 CPU를 점유하고 있다고 가정하자. 

Thread A 가 정해진 CPU 점유시간을 끝내고, 10초 후 다시 동작해야 한다. 그러면 A는 CPU 점유를 양보(yield) 한다. 따라서 ready_list의 마지막에 들어가고 자신의 차례를 기다려야 한다.

운영체제는 다음 할 일이 없는 CPU에게 ready_list에서 할 일을 찾아 시킨다. 이 때, ready_list에서 기다리고 있던 Thread A가 CPU점유를 하게 된다면, 아직 기다리는 시간이 지나지 않아 다시 CPU를 양보하게 된다.

이 과정에서, CPU는 계속적으로 점유되어 있지만 아무런 작업이 일어나지 않는다. 이를 busy wait이라고 하며, 이는 ready_list에서 CPU로 모든 정보를 넘겨주는 context switching 이 발생하여 비용이 너무 큰 작업이다. 이를 방지하기 위해 우리는 context switching이 최소한으로 발생하게 CPU 스케쥴링을 수정해야 한다.

 

 

---

 

 

 

 

 

따라서 수정된 CPU 스케쥴링의 아이디어는 

운영체제는 ready_list에 있는 Thread를 CPU에게 할당한다. 그렇다면 '기다리는 시간이 필요한 Thread를 CPU가 점유가 끝난 후, 바로 ready_list에 넣는 것이 아닌 wait_list에 넣고 기다리는 시간을 채워주면 되지 않을까? 이렇게 한다면 불필요한 context switching이 일어나지 않겠다' 라고 생각했다. 

추가적으로 wait_list에 Thread를 넣을 때는 각 Thread 기다리는 시간으로 정렬을 해야 FIFO 방법으로 꺼내기가 쉽다.

 

 

 

---

 

 

코드구현

c언어로 작성한 코드이기 때문에 전방선언을 해야함.

 

 

 

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

	// 추가한 요소 : 각 thread ticks
	int64_t  t_ticks;
    	
	struct intr_frame tf;               /* Information for switching */
	unsigned magic;  
    };

 

 

 

thread 를 blocked_list에서 기다리도록 하는 코드

// ~/threads/thread.c
// OS 의 인터럽트를 받아 running thread를 block 하는 함수
void
thread_add_to_blocked (int64_t ticks) {
	struct thread *curr = thread_current ();
	enum intr_level old_level;

	ASSERT (!intr_context ());
	old_level = intr_disable ();
	curr->t_ticks = ticks;
	if (curr != idle_thread)
		list_insert_ordered (&blocked_list, &curr->elem, thread_wakeup_tick_compare ,NULL);
		thread_block();
	intr_set_level (old_level);
}

 

 

// ~/threads/thread.c
// 두 스레드를 비교하여, 어느 스레드가 더 먼저 깨어나야 하는지를 판단하는 함수
bool 
thread_wakeup_tick_compare(const struct list_elem *a,const struct list_elem *b, void *aux UNUSED)
{
	struct thread *st_a = list_entry(a, struct thread, elem);
	struct thread *st_b = list_entry(b, struct thread, elem);
	return st_a->t_ticks < st_b->t_ticks;
}

 

 

// ~/devices/timer.c
// CPU sheduling 수정 전
void
timer_sleep (int64_t ticks) {
	int64_t start = timer_ticks ();

	ASSERT (intr_get_level () == INTR_ON);
    // busy_wait : yield 함수로 context_switching이 계속적으로 발생
	while (timer_elapsed (start) < ticks)
		thread_yield ();
}




// 수정 후
void
timer_sleep (int64_t ticks) {
	int64_t start = timer_ticks ();

	ASSERT (intr_get_level () == INTR_ON);
	// 현재 실행 중인 thread를 blocked_list에 추가하고 thread_block함수를 실행하여 
   	// CPU 효율 향상
	thread_add_to_blocked(start + ticks);
}

 

 

---

 

blocked_list에서 ready_list로 thread_unblock하는 코드

// ~/devices/timer.c

/* Timer interrupt handler. */
static void
timer_interrupt (struct intr_frame *args UNUSED) {
	/*
	thread_tick함수를 실행하면 idle이면 idle_tick +1 , 아니면 kernel_tick +1 하고 
   	만약 tick이 TIME SLICE=4보다 커지면 외부인터럽트를 실행해서 cpu점유를 양보해라고한다.
    */
	ticks++;
	thread_tick ();

	// 추가한 코드 : OS의 실행시간을 인자로 해당되는 thread를 찾아서 실행 준비시키기
	thread_wakeup(ticks);

}

 

 

// ~/threads/thread.c

void thread_wakeup(int64_t current_ticks)
{
	enum intr_level old_level;
	old_level = intr_disable(); // 인터럽트 비활성

	struct list_elem *curr_elem = list_begin(&blocked_list);
	while (curr_elem != list_end(&blocked_list))
	{
		struct thread *curr_thread = list_entry(curr_elem, struct thread, elem); // 현재 검사중인 elem의 스레드

		if (current_ticks >= curr_thread->t_ticks) // 깰 시간이 됐으면
		{
			curr_elem = list_remove(curr_elem); // sleep_list에서 제거, curr_elem에는 다음 elem이 담김
			thread_unblock(curr_thread);        // ready_list로 이동
		}
		else
			break;
	}
	intr_set_level(old_level); // 인터럽트 상태를 원래 상태로 변경
}