[PintOS] Project1: Part1 Alarm clock

Alarm clock

Part 1: 프로젝트 소개

이 프로젝트에서는 최소한의 기능을 갖춘 스레드 시스템을 제공한다. 우리가 해야할 것은 동기화 문제를 더 잘 이해하기 위해 이 시스템의 기능을 확장하는 것이다. 이 할당을 위해 주로 디렉토리에서 작업하고 측면의 디렉토리에서 일부 작업을 수행한다. 컴파일은 디렉토리에서 수행되어야한다. 이 프로젝트에 대한 설명을 읽기 전에 최소한 재료 동기화를 훑어봐야 한다.

기본 개념

tick

• 프로그램에서 시간을 세는 단위. device/timer.h에서 TIMER_FREQ의 값이 100으로 저장되어 있는데, 이 의미는 1초당 tick이 100번 돈다는 의미이다. 즉 1tick은 100분의 1초(10ms).

timer

• 컴퓨터에 내장되어 있는 하드웨어이다. 일정 시간 단위를 세고, 그 단위마다 CUP에 timer interrupt를 날린다. 현재 TIME_SLICE는 4 tick으로 설정되어 있다. 해당 TIME_SLICE가 지나면 그 다음 스레드에 CPU 주도권을 넘긴다.

현재 상황 : busy waiting 방식으로 구현

• 매번 ready list를 돌면서 자기가 CPU를 사용해야 하는 타이밍이 되었을 때마다 time_elpsed로 시간을 체크하고 다른 스레드로 yield한다.

sleep 시켜줄 스레드 A를 대상으로 인자로 넣어준 ticks만큼 시간이 지났는지 체크한다. A가 CPU 주도권을 잡아 코드를 매 줄 실행시킬 때마다 이를 확인해 주어야 한다. 따라서 효율성 면에서 굉장히 떨어진다.

timer_sleep() 함수

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

	ASSERT (intr_get_level () == INTR_ON); // 현재 인터럽트 상태가 인터럽트 허용이 아니면 종료.
	while (timer_elapsed (start) < ticks)
		thread_yield ();
}

• 시작 시간의 tick 값을 start 변수에 기록한다
• 현재 인터럽트 상태가 허용으로 되어 있는지를 체크한다(디버깅 용).
• 맨 처음 sleep시킨 순간(start)부터 지금까지의 tick 수를 체크(timer_elapsed())한다. 우리가 인자로 넣어준 ticks 값보다 작다면 thread_yield()를 통해 다른 스레드에게 CPU 주도권을 양보하고, 다시 ready_list 맨뒤로 이동한다.
• 만약 yield를 통해 CPU 주도권을 다른 스레드에게 넘겼다면 거기서 코드가 멈춰있는다. 그러다 다시 ready_list에서 CPU 주도권을 가지게 되면 멈춰던 곳에서부터 다시 whlie 문을 돌기 시작한다.

현재 구현되어 있는 thread_yield()

• ist_push_back으로 해당 스레드를 ready_list의 맨 뒤로 넣어주고 do_schedule로 다음 ready_list의 스레드(만약 스레드가 비어 있다면 idle 스레드)를 RUNNIG상태로 변경하고 CPU 주도권을 넘겨준다.(thread_launch).

/* 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 ();  // 인터럽트를 disable한다.

	// 만약 현재 스레드가 idle 스레드가 아니라면 ready queue에 다시 담는다.
	// idle 스레드라면 담지 않는다. 어차피 static으로 선언되어 있어, 필요할 때 불러올 수 있다.
	if (curr != idle_thread)
		list_push_back (&ready_list, &curr->elem);
	do_schedule (THREAD_READY);
	intr_set_level (old_level);
}

프로젝트1 : 개선 방안

애초에 sleep되어야 할 스레드들도 모두 READY상태로 ready list에 담겨져 있는 게 문제이다. 매번 ready list를 돌면서 자기가 CPU를 사용해야 하는 타이밍이 되었을 때마다 time_elapsed로 시간을 체크하고 매번 다른 스레드로 yield해 주어야 한다.

sleep 상태에 있는 프로세스들을 ready list에 넣지 않고 따로 sleep list라는 리스트에 저장시킨다.

1. struct thread 개선

스레드 구조체 안에 sleep할 시 깨워줘야 하는 시각을 집어넣는다. 현재 20tick이고 앞으로 80tick 후에 깨워야 한다면, 20 + 80 = 100tick이라는 값을 저장해 줄 변수가 필요하다.

include/threads/thread.h/struct thread

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

...

	/* wakeup tick : 깨어나야 할 tick(시각) */
	int64_t wakeup_tick;

...

}

2. sleep_list 만들기

threads/thread.c

/* sleep 상태의 스레드들을 저장하는 리스트 */
static struct list sleep_list;

threads/thread.c/thread_init()

main() 함수에서 호출된다. 맨 처음 스레드와 관련된 구조체들과 main 스레드를 초기화해준다.

void thread_init (void) {

...
/* Init the global thread context */
	lock_init (&tid_lock);
	list_init (&ready_list);
	list_init (&destruction_req);
	list_init (&sleep_list);     // sleep 스레드들을 연결해놓은 리스트를 초기화한다.
	next_tick_to_awake = INT64_MAX;

}

3. 스레드를 재우는 함수 thread_sleep() 구현

sleep 해줄 스레드를 sleep list에 추가하고 status를 THREAD_BLOCKED으로 만들어준다.

이 때 idle thread를 sleep시켜준다면 CPU가 실행 상태를 유지할 수 없어 종료되므로 예외처리를 해 주어야 한다.

thread/thread.c/thread_sleep()

void thread_sleep(int64_t ticks) {
	/* 현재 스레드가 idle 스레드가 아닐경우 thread의 상태를 BLOCKED로 바꾸고 깨어나야 할 ticks을 저장,
	   슬립 큐에 삽입하고, awake함수가 실행되어야 할 tick값을 update */
	/* 현재 스레드를 슬립 큐에 삽입한 후에 스케줄한다. */
	/* 해당 과정중에는 인터럽트를 받아들이지 않는다. */

	struct thread *t = thread_current();
	enum intr_level old_level;
    
	ASSERT(!intr_context());
	old_level = intr_disable();
	if (t != idle_thread) {
		t->time_to_wakeup = ticks;
		if (MIN_alarm_time > ticks)	{
			MIN_alarm_time = ticks;
		}
		list_push_back(&sleep_list, &t->elem);
	}

	do_schedule(THREAD_BLOCKED);
	intr_set_level(old_level);
}

thread/thread.c/thread_block()

스레드를 block(sleep)한다. thread_unblock() 함수에 의해서만 block이 해제된다. 무조건 인터럽트가 불가능한 상황에서 실행되어야 한다. synchronization primitives 활용해보기

void thread_block(void)
{
	ASSERT(!intr_context());
	ASSERT(intr_get_level() == INTR_OFF);
	thread_current()->status = THREAD_BLOCKED;
	schedule();
}

4. 스레드를 깨우는 함수 thread_awake() 구현

sleep list에 잠자고 있는 스레드를 깨운다. 즉, sleep list에서 제거한 후 ready list에 넣어준다. status 역시 바꿔준다.

thread/thread.c/thread_awake()

sleep list를 순회하면서 인자로 받은 ticks보다 wakeup_tick이 작은 스레드들(깨울 시간이 된 스레드들)을 깨운 후 ready list에 넣어준다.

만약 해당 스레드가 아직 깨울 시간이 되지 않았다면 다음 스레드로 넘어간다. 이 때, 해당 스레드의 tick이 최소 tick인지를 확인한 후 next_tick_to_awake를 업데이트한다.

void thread_awake(int64_t ticks) {
	struct thread *t;
	struct list_elem *now = list_begin(&sleep_list);
	int64_t new_MIN = INT64_MAX;

	/* sleep list를 전부 순회하며
	   알람시간이 다 된 스레드를 unblock 해준다. */
	while (now != list_tail(&sleep_list)) {
		/* list_entry return값 = thread 구조체 */
		t = list_entry(now, struct thread, elem);

		/* 현재 스레드가 알람 시간이 다 되었다면 깨운다. */
		if (t->time_to_wakeup <= ticks) {
			now = list_remove(&t->elem);
			thread_unblock(t);
		}
		/* 현재 스레드가 아직 더 자야한다면 다음 스레드로 now를 갱신한다. */
		else {
			now = list_next(now);
			/* 필요하다면 전체 sleep list의 MIN 값을 갱신한다. */
			if (new_MIN > t->time_to_wakeup) {
				new_MIN = t->time_to_wakeup;
			}
		}
	}
	MIN_alarm_time = new_MIN;
}

• list_entry(리스트의 원소, 원소가 담겨 있던 struct의 종류, MEMBER)
  • 어떤 리스트의 원소가 담겨 있는 구조체의 시작 주소를 반환한다.
  • 리스트의 원소의 주소-구조체 내에서 그 원소의 상대 주소 = 구조체의 시작 주소

/* Converts pointer to list element LIST_ELEM into a pointer to
   the structure that LIST_ELEM is embedded inside.  Supply the
   name of the outer structure STRUCT and the member name MEMBER
   of the list element.  See the big comment at the top of the
   file for an example. */
#define list_entry(LIST_ELEM, STRUCT, MEMBER)           \
	((STRUCT *) ((uint8_t *) &(LIST_ELEM)->next - offsetof (STRUCT, MEMBER.next)))

• include/lib/user/stddef.h/offsetof( 구조체의 종류, 구조체 안의 멤버 )
  • 한 구조체 내의 멤버(메소드 혹은 변수)의 상대적 거리를 구한다.
  • 구조체의 시작 주소를 0으로 두었을 때 입력받은 멤버의 주소를 구할 수 있다.

#define offsetof(TYPE, MEMBER) ((size_t) &(((TYPE *) 0)->MEMBER))

5. timer_sleep()과 timer_interrupt() 수정

devices/timer.c/timer_sleep( )

해당 ticks 동안 해당 스레드를 잠재운다.

void timer_sleep(int64_t ticks) {
	thread_sleep(timer_ticks() + ticks);
}

devices/timer.c/timer_interrupt( )

매 tick마다 해당 tick에 깨워야 할 스레드들을 깨워줄 것이다. 이 때, 매 tick마다 깨우기보단 MIN_alarm_time와 비교하여 깨워야 할 스레드가 sleep_list에 있을 경우에만 깨우는 것이 효율적이다.

static void
timer_interrupt(struct intr_frame *args UNUSED)
{
	ticks++;
	thread_tick();
	
	if (MIN_alarm_time <= ticks) {
		thread_awake(ticks);
	}
}

결과

threads/build에서 pintos -- -q run alarm-multiple 명령어를 사용하면 결과를 볼 수 있다.

기존에는 idle_ticks가 0이었다. 다시 말해 CPU가 노는 시간이 없고 모두 다 sleeping하는 스레드들을 관리하느라 쉬지 않지 않고 일을 했다는 뜻, 새로 sleep_list를 만들고 block한 스레드들을 그 곳에 넣어둠으로써 CPU에게 여유를 줄 수 있다.

연관 함수

• timer_ticks( )
  • 현재 진행되고 있는 tick의 값을 리턴한다.
• intr_disable( )
  • 인터럽트를 disable 하기 전 인터럽트 허용 유무를 old_level에 저장한다. 그 후 인터럽트를 disable하고 disable하기 전 인터럽트 상황을 리턴한다.
• intr_get_level( )
  • 지금 인터럽트가 허용되어 있는 상태인지 disabled 되어 있는 상태인지 체크한다. 만약 인터럽트가 허용되어 있으면 INTR_ON(1)을, 인터럽트가 disabled 되어 있으면 INTR_OFF(0)을 리턴한다.
• intr_set_levle( )
  • 인자로 넣어준 상태에 맞게 인터럽트 상태를 바꿔준다.
• timer_elapsed( )
  • 인자로 넣어준 값과 tick으로부터 얼마만큼 tick이 흘렀는지를 리턴한다.

PintOS Project1 GIthub 주소 PintOS