[PintOs] PROJECT1: THREADS 크래프톤정글 7주차

 

 

 

이번 주차는 카이스트에서 제공하는 'PintOs 구현하기' 입니다. 

 

 

카이스트에서 제공하는 핀토스 자료

Introduction · GitBook

 

 

Alarm Clock

1차 시도

 

아래 APPENDIX 항목에 스레드와 동기화 등에 대한 설명과 간단한 코드 예제가 있는데 그 중 모니터monitor라는 동기화 기법을 사용하려 했다.

이유는 모니터 설명에 자유로운 조건 변수 설명이 있었는데 

e.g. "some data has arrived for processing" or "over 10 seconds has passed since the user's last keystroke".

 

저 시간을 조건 변수로 설정할 수 있다는 설명에 꽂혔다...

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

	lock_acquire(&lock);
	while (start + ticks > timer_ticks()){
		cond_wait(&sleep, &lock);
	}
	cond_signal(&sleep, &lock);
	lock_release(&lock);
}

 

모니터를 사용해서 구현은 했는데, 구현하면서도 '아 이게 아닌데...'라는 생각이 들었다.

왜냐하면 이런 동기화 기법은 공유 자원을 무분별하게 변경하는 것을 막기 위한 기법인데 sleep은 어떤 스레드도 접근할 수 있어야 하고, 동시에 여러 스레드가 sleep할 수도 있어야 한다.

일단 시작한 거 test해보니 바로 'kunel.o faild'를 볼 수 있었다. 잘못된 접근이라는 생각이 들어서 오류를 고치기 보다 다른 접근 방법을 찾아야 한다고 생각했다.

 

 

매크로를 드디어! 이해했다...지금은 토->일 넘어가는 12시...이걸 이틀을 보고 이제 이해함 ㅎㅎ

list_entry(list_elem 스레드 리턴 받고 싶은 요소, struct thread, elem); 

이렇게 쓰면 해당 요소에서 메모리 접근을 해서 스레드 객체를 반환해주는 것이다~. 굿

 

 

2차 시도 - 좀 무식한 방법

sleep_list를 하나 만들어서 블락된 스레드들을 저장해두고 시간이 되면 깨워주는 방식으로 시도했다.

코드를 보면 알다시피 오버헤드가 꽤 발생하는 방식이다...

매 인터럽트마다 sleep list를 끝까지 순회해야 하니 시간도 오래 걸린다.

그래서인지 스택 오버플로우가 발생해 방식을 바꾸기로 했다... 이 시점에서 Pintos 관련 영상을 시청했다. 코드 설명보다는 가이드를 제시하는 내용이었다.

void thread_wakeup(void)
{ // time inturrupt 마다 호출
	if (list_empty(&sleep_req))
		return;

	struct list_elem *e = list_front(&sleep_req);

	while (e != NULL)
	{
		struct thread *victim = list_entry(e, struct thread, elem);

		if (victim->sleep > 0)
		{
			victim->sleep--;
			// printf("tid:%d  sleep:%d\n", victim->tid, victim->sleep);
		}
		if (victim->sleep == 0 && victim->status == THREAD_BLOCKED)
		{
			intr_disable();

			printf("wakeup id: %d and state:%d\n", victim->tid, victim->status); // block 2 run 0
			victim->status = THREAD_READY;

			list_push_back(&ready_list, &victim->elem);
			e = e->prev;
			list_remove(e->next);
		}

		if (e->next == NULL)
			break;
		e = list_next(e);
	}
}

 

 

 

 

최종 코드

 

  thread_sleep()

 

sleep 상태의 스레드들을 일어나기까지 남은 틱 수를 기준으로 정렬해 리스트에 넣어주었다.

또, 스레드 구조체에 스레드가 일어나야 하는 시간을 저장해 갖고 있도록 했다.

 

↓ 코드 확인

void thread_sleep(int64_t ticks)
{
    struct thread *curr = thread_current();
    enum intr_level old_level;

    old_level = intr_disable();
    if (curr != idle_thread)
    {
        curr->status = THREAD_BLOCKED;
        curr->wakeup_tick = ticks;
        list_insert_ordered(&sleep_list, &curr->elem, (list_less_func *)less, NULL);
    }
    schedule();
    intr_set_level(old_level);
}

이 때, list_insert_ordered()에서는 list_less_func 이라는 함수를 사용하는데 보조 함수를 기준으로 리스트를 정렬해준다.

정렬을 위한 함수를 만들어준뒤 함수 이름을 매개변수로 넣어주면 된다.

list_insert_ordered의 사용법을 익히는데도 시간이 좀 걸렸었다...마지막 aux 같은 경우 사용하지 않으면 그냥 NULL을 넣어주면 되는데, 어떤 걸 넣어야 하는지 고민을 하느라 시간을 조금 소모했다.

 

 

 

  thread_wakeup()

 

sleep_list가 정렬되었으니 리스트 맨 앞에 있는 스레드가 일어나야 하는지만 확인하면 된다.

반복 횟수가 확실히 줄어들었다.

 

↓ 코드 확인

void thread_wakeup(int64_t ticks)
{
    if (list_empty(&sleep_list))
        return;

    enum intr_level old_level;
    struct thread *to_wakeup = list_entry(list_front(&sleep_list), struct thread, elem);

    old_level = intr_disable();
    while (to_wakeup->wakeup_tick <= ticks)
    {
        list_pop_front(&sleep_list);
        list_insert_ordered(&ready_list, &to_wakeup->elem, (list_less_func *)priority, NULL);
        to_wakeup->status = THREAD_READY;
        if (list_empty(&sleep_list))
            return;
        to_wakeup = list_entry(list_front(&sleep_list), struct thread, elem);
    }

    intr_set_level(old_level);
}

priority 구현 전까지는 list_insert_ordered( ready_list ) 대신 list_push_back( ready_list )을 사용하면 된다.

 

 

 

 

Priority Scheduling

이제 우선순위에 따라 스레드들이 CPU를 선점할 수 있게 구현해야 한다.

 

여러 리스트들을 우선순위 기준으로 정렬해야 할 일이 많다.

tick 기준으로 sleep_list를 정렬했던 것처럼 priority를 기준으로 리스트를 정렬할 수 있게 함수를 먼저 만들어주었다.

 

  priority()

 

대단한 내용은 아니다. 스레드가 갖고 있는 우선순위를 기준으로 우선순위가 큰 스레드가 리스트의 앞으로 올 수 있게 작성하면 된다.

bool priority(const struct list_elem *a, const struct list_elem *b, void *aux)
{
	struct thread *ta = list_entry(a, struct thread, elem);
	struct thread *tb = list_entry(b, struct thread, elem);

	return ta->priority > tb->priority;
}

 

↓ 정렬 관련 트러블 슈팅

큰 문제는 아니었는데 변경하기 전에는 

return ta->priority >= tb->priority 였다.

뭐가 다르냐면 >와 >=다.

 

>= 일때는 같은 우선순위일 때, FIFO가 보장되지 않는다.

list_insert_ordered를 살펴보면 알 수 있지만, 정렬에 사용하는 함수의 return 값이 True일 경우, 그 자리에 요소를 삽입한다.

• >= 를 사용할 때, 나와 우선순위가 같은 요소가 리스트에 있다면 그 요소의 앞에 새로 들어온 요소가 위치하게 된다.
• > 를 사용할 때, 나와 우선순위가 같은 요소가 리스트에 있다면 그 요소의 뒤에 새로 들어온 요소가 위치하게 된다.

이 차이로 FIFO가 보장되는가의 여부가 달라지니 유의하면 좋겠다.

 

 

  Donation

 

기부 기능은 조금 복잡하다.

스레드들이 특정 자원을 두고 경쟁할 때, 우선순위 반전이 발생하지 않도록 기부를 사용한다.

 

만약 우선순위가 낮은 L 스레드가 A라는 자원을 갖고 있다고 하자.

이때 우선순위가 높은 H 스레드가 A를 원해 기다리고 있다.

 

우선순위가 중간인 M 스레드가 ready list에 있다면 L 스레드는 CPU를 M 스레드에게 양보해야 한다.

이 상황에서 우선순위 반전이 일어난다. 우선순위가 가장 높은 H 스레드가 CPU를 사용하지 못하는데 M 스레드가 CPU를 사용하는 상황...이런 상황을 막기 위해 기부 시스템을 구현해야 한다.

 

  thread

 

스레드 구조체에 original이라는 변수를 추가해 스레드가 기부받은 우선순위가 아닌 기존의 우선순위를 저장해둔다.

 

프로젝트를 구현하며 추가한 변수들은 다음과 같다.

struct thread
{
	int priority;			   /* Priority. */
	int original;

	struct lock *wait_on_lock;
	struct list donations; // 기부해준 스레드
    
    struct list_elem d_elem; // 기부리스트에서 사용할 elem
    
	int64_t wakeup_tick;  /* 쓰레드가 wake-up할 tick(local tick)*/
};

 

donations를 통해 나에게 우선순위를 기부한 스레드를 보관한다.

wait_on_lock은 내가 대기하고 있는 lock을 기억할 수 있게 추가했다.

 

 

  lock_acquire(), sema_down()

 

기부를 하는 위에서 설명했듯이 우선순위 반전이 일어나지 않게 하기 위해서.

그러려면 lock 등 자원을 갖고 있는 스레드는 lock을 기다리는 스레드들과 우선순위가 같아져야 한다.

 

void lock_acquire(struct lock *lock)

 

lock 구조체에는 lock holder를 통해 자원을 점유한 스레드를 저장한다.

만약 누군가 lock을 갖고 있고, 나는 대기해야 한다면 wait_on_lock에 해당 lock을 저장하고 waiting에 들어간다.

 

↓ 코드 확인

void lock_acquire(struct lock *lock)
{
	ASSERT(lock != NULL);
	ASSERT(!intr_context());
	ASSERT(!lock_held_by_current_thread(lock));

	if (lock->holder != NULL)
	{
		thread_current()->wait_on_lock = lock;
	}
	sema_down(&lock->semaphore);
	lock->holder = thread_current();
	if (thread_current()->wait_on_lock != NULL)
		thread_current()->wait_on_lock = NULL;
}

 

 

void sema_down(struct semaphore *sema)

 

sema는 자원을 기다리는 스레드 리스트가 존재한다.

자원을 기다리는 스레드를 우선순위로 정렬해 삽입해야 우선순위 기부를 할 때 편하게 이용할 수 있다.

 

한 가지 주의할 점은 lock을 사용할 때도 sema의 함수를 이용하기 때문에 두 가지 경우에 대해 다르게 관리를 해줘야 한다.

 

세마포어는 다른 스레드가 sema up을 해줄 수 있어 다른 스레드가 공유자원에 대해 접근할 수 있지만, 뮤텍스, lock은 lock을 소유한 스레드만이 lock release할 수 있다. 따라서 lock을 사용할 때만 기부 시스템을 호출하면 된다.

 

↓ 코드 확인

void sema_down(struct semaphore *sema)
{
	enum intr_level old_level;
	ASSERT(sema != NULL);
	ASSERT(!intr_context());
	old_level = intr_disable();
	while (sema->value == 0)
	{
		list_insert_ordered(&sema->waiters, &thread_current()->elem, larger, NULL);
		if (thread_current()->wait_on_lock != NULL)
			donate_priority(sema, thread_current()->wait_on_lock->holder);
		thread_block();
	}
	sema->value--;
	intr_set_level(old_level);
}

 

  donate_priority()

 

lock을 소유한 스레드의 우선순위를 lock을 기다리고 있는 스레드 중 가장 큰 우선순위를 가진 스레드의 우선순위로 변경해준다.

void donate_priority(struct list_elem *donor, struct thread *holder)
{
	list_insert_ordered(&holder->donations, donor, d_elem_priority, NULL);
	int dona_prio = list_entry(list_front(&holder->donations), struct thread, d_elem)->priority;
	if (holder->priority < dona_prio)
	{
		holder->priority = dona_prio;
	}
}

donate_priority()는 이후에 크게 변경이 되었는데 일반적인 상황이 아니라 chain처럼 줄줄이 자원을 원하는 상황에서는 기존의 코드로는 해결이 되지 않았다.

즉, 기부받고 있는 상황에서 나도 누군가에게 기부해야 하는 상황에 대한 처리가 필요했다.

새로 기부를 받고 나면, 내가 기다리고 있는 자원이 있는지 확인한다.

다른 자원에 대해 대기중이면, 대기중인 lock을 갖고 있는 스레드에게 변경된 내 우선순위를 부여한다.

 

아래 while문을 통해 chain처럼 연결된 스레드들의 맨 앞까지 이동하면서 우선순위를 맞춰준다.

void donate_priority(struct list_elem *donor, struct thread *holder)
{
	list_insert_ordered(&holder->donations, donor, d_elem_priority, NULL);
	int dona_prio = list_entry(list_front(&holder->donations), struct thread, d_elem)->priority;
	if (holder->priority < dona_prio)
	{
		holder->priority = dona_prio;
	}

	while (holder->wait_on_lock != NULL)
	{ // 다른 lock에 대해 기다리는 중이면
		holder = holder->wait_on_lock->holder;
		list_sort(&holder->donations, d_elem_priority, NULL);
		int dona_prio = list_entry(list_front(&holder->donations), struct thread, d_elem)->priority;
		if (holder->priority < dona_prio)
		{
			holder->priority = dona_prio;
		}
	}
}

 

 

 

  lock_release(), sema_up()

 

lock_release()에서는 갖고 있던 기부자 리스트를 정리해준다.

그냥 리스트를 삭제하는 게 아니라 wait_on_lock을 살펴야 한다. 왜냐하면 스레드는 lock을 여러 개 소유할 수도 있기 때문에 donate list가 여러 lock을 기다리는 스레드들로 형성될 수 있기 때문이다.

우선순위를 기부해준 스레드들을 순회하며 스레드가 기다리던 lock이 지금 release하려고하는 lock과 같은지 확인한다.

release한 lock을 기다리던 스레드들은 더 이상 우선순위를 기부할 필요가 없기에 기부 리스트에서 삭제한다.

void lock_release(struct lock *lock)
{
	ASSERT(lock != NULL);
	ASSERT(lock_held_by_current_thread(lock));


	if (!list_empty(&lock->holder->donations))
	{
		struct list_elem *e = list_front(&lock->holder->donations);
		while (e != NULL)
		{
			struct thread *t = list_entry(e, struct thread, d_elem);
			if (t->wait_on_lock == lock)
			{
				list_remove(&t->d_elem);
			}

			e = e->next;
			if (e->next == NULL)
				break;
		}
	}
	lock->holder = NULL;
	sema_up(&lock->semaphore);
}

 

sema_up()에서는 내 우선순위를 변경한다.

만약 donate list가 비었다면 original 우선순위로, 누군가 기부중이라면 그 중 가장 큰 우선순위로 변경.

그리고 waiting 중인 스레드 중 하나를 깨워 자원을 소유할 수 있게 해준다.

void sema_up(struct semaphore *sema)
{
	enum intr_level old_level;
	ASSERT(sema != NULL);
	old_level = intr_disable();
	if (!list_empty(&sema->waiters))
	{
		struct thread *curr = thread_current();
        
		if (!list_empty(&curr->donations)) 
		    curr->priority = list_entry(list_front(&curr->donations), struct thread, d_elem)->priority;
		else
		    thread_current()->priority = thread_current()->original;
        
		list_sort(&sema->waiters, priority, NULL);
		struct thread *popth = list_entry(list_pop_front(&sema->waiters), struct thread, elem);
		thread_unblock(popth);
	}
	sema->value++;
	thread_preempt();
	intr_set_level(old_level);
}

 

 

  condvar 관련 함수들

 

condition이라는 시스템은 semaphore elem이라는 구조체를 새로이 사용한다.

 

이 구조체에 priority를 저장할 수 있게 변수를 하나 추가했다.

struct semaphore_elem
{
	struct list_elem elem;		/* List element. */
	struct semaphore semaphore; /* This semaphore. */
	int priority;
};

 

 

 

void cond_wait(struct condition *cond, struct lock *lock)

 

cond_wait()은 condition 변수에 대해 대기하기 원할 때 호출하는 함수다.

 

void cond_wait(struct condition *cond, struct lock *lock)
{
	struct semaphore_elem waiter;
	ASSERT(cond != NULL);
	ASSERT(lock != NULL);
	ASSERT(!intr_context());
	ASSERT(lock_held_by_current_thread(lock));

	sema_init(&waiter.semaphore, 0);
	waiter.priority = lock->holder->priority;
	list_push_back(&cond->waiters, &waiter.elem);
	// list_insert_ordered(&cond->waiters, &waiter.elem, priority, NULL);
	lock_release(lock);
	sema_down(&waiter.semaphore);
	lock_acquire(lock);
}

 

  여담

주석 처리해둔 한 줄을 보면 list_insert_ordered를 사용할 때, 아래 semaphore_elem을 이용해 기존 priority 함수를 사용했다. 

priority()에서는 elem으로 스레드의 구조체를 가져와 우선순위 대소를 판별하는데 semaphore_elem으로 priority()를 사용하려 하다보니 정렬은 안 되고 이상한 값이 출력되었었다.

이 문제를 해결하는데에도 꽤 애먹었었다. thread->elem과 semaphore->elem이 다른 개체라는 것을 알아차리기까지 오래걸렸다. 바본가바...

 

 

void cond_signal(struct condition *cond, struct lock *lock)

cond_signal()은 cond에 대해 대기중인 리스트에서 첫 번째 요소에게 waiting이 끝났음을 알린다.

void cond_signal(struct condition *cond, struct lock *lock)
{
	ASSERT(cond != NULL);
	ASSERT(lock != NULL);
	ASSERT(!intr_context());
	ASSERT(lock_held_by_current_thread(lock));

	if (!list_empty(&cond->waiters))
	{ // 맨 앞의 요소에게 알림

		list_sort(&cond->waiters, cond_priority, NULL);
		sema_up(&list_entry(list_pop_front(&cond->waiters),
				struct semaphore_elem, elem)->semaphore);
	}
}

 

여기까지가 priority에 대한 구현이었다.

 

 

---

 

mlfqs

 

매크로 작성 및 변수 추가

ready_threads는 running, ready 상태 스레드의 개수이다. 우선순위 계산에 사용된다.

static int ready_threads;

#define FIXED (14)
#define ADD(x, y) ((x) + ((y) << FIXED)) // y = integer
#define SUB(x, y) ((x) - ((y) << FIXED))
#define MUL(x, y) ((((int64_t)(x)) * y) >> FIXED)
#define DIV(x, y) ((((int64_t)(x)) << FIXED) / y)
#define TOINT(x) (x >= 0) ? ((x + (FIXED >> 1)) >> FIXED) : ((x - (FIXED / 2)) / FIXED)
#define TOINT_ZERO(x) ((x) >> FIXED)
#define TOFIX(x) (x << FIXED)

 

매크로 작성은 깃북에 있는 걸 보고 그대로 작성하면 되고, 계산 함수 작성도 보고 하면 된다.

그러나 시간이 오래걸린다 ㅋㅋ 매크로를 적절하게 사용해야 하기 때문에 어떤 변수가 고정 소수점으로 유지되는지, 어떤 변수가 일반 정수로 사용되는지 잘 파악해야 한다.

 

코드로 예를 들면 thread_get_load_avg()의 경우 load_avg에 100을 곱한 값을 반환해야 한다.

이때 두 가지 방법이 있다.

아래 코드의 주석처럼 변수에 100을 단순히 곱해서 반환할 수도 있고,

매크로를 사용해서 곱셈을 하는 방법이다.

당연히 단순 곱셈은 제대로 된 값을 반환하지 못 한다...

int thread_get_load_avg(void)
{
	// return load_avg * 100;
	return TOINT(MUL(load_avg, TOFIX(100)));
}

 

 

void calc_load_avg()

 

마찬가지로 깃북을 보고 구현하면 된다.

주의할 점은 idle_thread는 ready_threads에 포함되면 안 된다는 것.

void calc_load_avg()
{
	ready_threads = list_size(&ready_list); // running, ready 상태의 스레드 갯수
	if (thread_current() != idle_thread)
	{
		ready_threads += 1;
	}
    load_avg = MUL((TOFIX(59) / 60), load_avg) + ((TOFIX(1) / 60)) * ready_threads;
}

 

  여담 

기존에는 유휴 스레드 판단할 때 thread_current()->name != "idle" 을 사용했다. 파이썬에 너무 익숙해져 있었다...

문자열을 비교할 때는 strcmp()를 사용해야 한다.

만약 이름으로 비교하고 싶다면 if (!strcmp(thread_current()->name, "idle"))을 사용하도록 하자.

 

 

int calc_one_priority(struct thread *t)

 

스레드의 우선순위를 계산해주는 함수

우선순위의 범위를 넘어서지 않도록 체크해야 한다. 우선순위의 범위는 0~63이다.

int calc_one_priority(struct thread *t)
{
    int priority = PRI_MAX - (TOINT_ZERO(t->recent_cpu) / 4) - (t->nice * 2);

    if (priority > PRI_MAX)
        priority = PRI_MAX;
    else if (priority < PRI_MIN)
        priority = PRI_MIN;
    return priority;
}

 

TOINT_ZERO를 사용한 이유는 깃북 설명을 보고 변경한 것이다.

' 결과는 가장 가까운 정수로 반내림(절사)해야 합니다.'

 

절사를 말한다는 걸 좀 늦게 알았다. 반내림이라고 하면 보통 .4 까지는 0으로 내린다고 생각하는데 여기서 말하는 round down은 소수점 아래는 모두 버린다는 뜻이다! 반내림과는 다른 뜻이니 주의해야한다.

 

 

마지막 트러블 슈팅은

running, ready 상태의 모든 스레드를 저장해둔 thread_list에 대한 내용이다.

thread_list에 스레드를 추가하는 부분이 thread_create()에 있었다. 그러나 main 스레드가 생성될 때는 thread_create()을 호출하지 않아 thread의 수가 모자라 agv 계산 등에 편차가 있었다.

그래서 list_push_back(thread_list) 함수를 모든 스레드를 생성할 때 호출되는 init_thread()로 옮겼다.

 

 

이렇게 Project 1을 끝낼 수 있었다. 

ALL PASS로 마무리할 수 있어서 굉장히 뿌듯했다 ㅎㅎ

 

project 1은 시작이 정말 어려웠다. 코드와 내장 함수들에 대한 파악과 인터럽트 시스템에 대한 파악이 동시에 이뤄졌기 때문에 이해가 빨리 되지는 않았다. 

그래도 alarm-clock 구현 이후에는 할 만 했고, mlfqs의 매크로 사용이 정말~ 어려웠다 ㅋㅋ 고정 소수점에 대해 제대로 이해해야 하기 때문에 고정 소수점 공부만 하루종일 했다. 

그래도 나름 재밌었다. 이런 구현 공부(?)가 재밌게 할 수 있는 것 같다.