[TIL] pintOS : synchronization 우선순위 스케줄링 구현 (1)

이번 포스팅에서는 예전 포스팅에서 공부했던 Synchronization(동기화) 를 스케줄링에 맞게 코드를 수정하고

 

다음 포스팅에는 priority-donate라는 동기화 중 특정 상황의 솔루션을 적용해보겠다.

 

---

 

 

pintos에 있는 synchronization

 

pintos에는 synchronization을 지키기 위해 semaphore와 lock, cond(monitor)가 존재한다.

 

 

해당 로직들은 모두 구조체로

 

구조체의 구조를 타고 가 보면 최 하단에는 결국 semaphore 방식으로 임계영역의 동기화를 보장하도록 설계되어있다.

 

semaphore 구조체 안에서는 해당 임계구역에 진입하려고 시도했지만 block된 쓰레드를 모아두는 리스트를 가지고 있다.

 

synchronization을 위한 구조체들의 구조는 다음과 같다.

 

 

 

condition 안에는 list 가 존재하는데 그 리스트에 여러개의 세마포어가 담겨있다.

 

하나의 세마포어는 또 여러개의 thread가 담겨있고, 이는 정렬할 때 더 고차원의 정렬방식이 필요하게 된다.

 

또한 lock이라는 방식이 도입하면서

 

해당 락을 가진 쓰레드가 점유한 임계영역을 sema_down()을 통해 다른 쓰레드가 접근을 시도하면

 

임계영역의 세마포어 리스트에 담긴다.

 

---

 

Semaphore

동기화를 보장하기 위한 하단에서 가장 기본이 되는 'value를 이용한 동기화 방법'을 사용하는 것이 세마포어이다.

 

세마포어가 pintos에서 어떻게 사용되는지 확인해보기 위해 함수들을 살펴보자.

 

+ sema_down()

void
sema_down (struct semaphore *sema) {
	enum intr_level old_level;
	struct thread *curr = thread_current ();
	ASSERT (sema != NULL);
	ASSERT (!intr_context ());

	old_level = intr_disable ();
	while (sema->value == 0) {
		list_insert_ordered (&sema->waiters, &thread_current ()->elem, thread_more_priority,NULL);
		thread_block ();
	}
	sema->value--;
	intr_set_level (old_level);
}

 

 

해당 함수는 sema_down 함수이다.

 

원래 list_push_back()으로 fifo 방식으로 삽입되었지만

 

동기화에서도 나중에 sema_up()에서 우선순위가 가장 높은 쓰레드를 가장 먼저 ready_list로 빼주기 위해 정렬 삽입을 진행했다.

 

해당 함수는 while문 안에서 세마포어의 value를 통해 사용 가능한지 확인(value == 1 인지)하고 sema value --를 통해

 

동기화된 임계 영역으로 진입할 수 있게 설계되어 있다.

 

Q. 왜 while문을 통해서 진입을 막는가? 이렇게 하면 blocked list에 중복으로 들어가는 거 아닌가?

 

 

while문은 딱 한번만 돈다.

 

왜냐하면 sema_down() 함수의 while문 제일 마지막에 block 을 통해

현재 스레드(sema_down을 시도하는 스레드)는 block되면서 ready_list로 들어가지 않고 semaphore 리스트 안에 잠들게 되기 때문이다.

 

만약 sema_up()을 통해 임계영역을 사용하던 스레드가 사용이 끝났다면

그 순간 우선순위가 제일 높은 스레드는 semaphore_list에서 pop되어 ready_list로 들어간다.

 

그럼 그 pop된 semaphore의 value가 1이 되기를 기다린 쓰레드는 running 실행 차례가 되었을 때,

멈췄던 순간인 while문을 다시 돌게 된다.

 

그때, 만약에 ready_list로 들어갔지만 기다리는 도중 다른 RUN하는 쓰레드가 sema_down()으로 동일한 임계영역을 차지하면

 

불운하게도 그 쓰레드는 다시 세마포어 리스트에 잠드는 것을 반복해야 한다.

 

따라서 while문을 통해 block되었다가 ready로 돌아와 자기 차례에서 실행되었을 때

 

누군가 그 사이 다시 sema를 차지했는지 확인하기 위해 while문을 사용해야 한다.

 

+ sema_up()

void
sema_up (struct semaphore *sema) {
	enum intr_level old_level;

	ASSERT (sema != NULL);

	old_level = intr_disable ();
	if (!list_empty (&sema->waiters)){
		list_sort(&sema->waiters,thread_more_priority,NULL);
		struct thread *wait_thread = list_entry (list_pop_front (&sema->waiters),
					struct thread, elem);
		thread_unblock (wait_thread);
	}
		
	sema->value++;
	intr_set_level (old_level);

	check_running_priority();
}

 

이 함수는 sema_down()으로 임계영역을 차지하고 수행을 다 끝낸 쓰레드가

 

semaphore 영역을 사용할 수 있는 상태로 다시 되돌리기 위해 호출한다.

 

이때, 만약에 어떤 스레드가 sema_down으로 블록되어 기다리고 있다면

그 리스트 중 제일 높은 우선순위의 쓰레드를 꺼내 주어(unblock) ready_list로 넣는 작업을 진행하고 있다.

 

 

이후 맨 마지막에 check_running_priority()를 하는 이유를 깊게 이해해 보자.

 

임계 영역을 사용하려다 블록된 쓰레드는 현재 실행되고 있는 쓰레드보다 무조건 우선순위가 높았기 때문에

 

임계영역을 사용하는 쓰레드를 밀어내고 임계 영역 접근을 시도했을 것이다.

 

 

따라서 임계 영역을 점유하던 쓰레드가 임계 영역을 내려놓은 시점에서

 

ready_list로 돌아온 block 되었던 쓰레드는 현재 임계영역을 사용하던 쓰레드보다 우선순위가 높을 확률이 매우 높다.

(set_priority를 통해 현재 실행되고 있던 쓰레드의 우선순위가 높아지지 않았다면)

 

 

임계영역의 동기화를 지켜주기 위해 우선순위가 높아도 block되었지만 

 

내려놓는 순간 현재 쓰레드를 전환해줄 지 말지를 판단할 필요가 있다.

 

---

 

 

Condition

 

pintos의 컨디션은 Monitor를 구현해 놓은 동기화 기법이다.

 

Monitor 안에는 여러개의 Semaphore(임계 영역)이 존재할 수 있고,

 

각 Semaphore에는 여러개의 쓰레드가 사용하기 위해 block되어 대기하고 있을 수 있다.

 

 

+ cond_wait()

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);
	list_insert_ordered (&cond->waiters, &waiter.elem, sema_more_priority, NULL);
	lock_release (lock);
	sema_down (&waiter.semaphore);
	lock_acquire (lock);
}

 

위의 cond_wait() 함수는 현재 쓰레드가 들어와서 자체 sema block을 수행한다.

 

그 상황에서 누군가 다른 쓰레드가 cond_signal을 해줄 때 까지 기다린다.

 

따라서 상황의 순서는

 

1. 쓰레드 A의 cond_wait() 을 통한 자체 block

 

2. 쓰레드 B에서 해당 임계 영역을 A가 사용할 수 있는 상태로 변환한 뒤 cond_signal()을 통한 sema_up 수행

 

3. 쓰레드 A의 sema 진입

 

이 때, lock을 사용하는 이유는 sema_init 의 동기화를 보존하면서도

 

 B가 해당 임계 구역에서 작업을 끝내고 signal을 보낼 수 있게 사용하도록 잠시 lock을 release()를 한 뒤 대기한다.

 

 

해당 함수는 우선순위 방식으로 삽입 되지만 쓰레드 방식으로 삽입이 아니라 세마포어 단위로 삽입 되기 때문에 

 

정렬함수가 달라져야 한다.

 

 

+ bool sema_more_priority()

static bool
sema_more_priority (const struct list_elem *a_, const struct list_elem *b_,
            void *aux UNUSED) 
{
	const struct semaphore_elem *a = list_entry (a_, struct semaphore_elem , elem);
	const struct semaphore_elem *b = list_entry (b_, struct semaphore_elem , elem);
	if (list_empty(&a->semaphore.waiters)){
		return false;
	}
	else if (list_empty(&b->semaphore.waiters)) {
		return true;
	}
  	const struct thread *ta = list_entry (list_begin(&a->semaphore.waiters), struct thread, elem);
  	const struct thread *tb = list_entry (list_begin(&b->semaphore.waiters), struct thread, elem);
  
  	return ta->priority > tb->priority;
}

 

이 함수가 정렬법을 작성한 함수인데,

 

세마포어 a와 b를 비교할 때, 각 세마포어를 사용하기 위해 대기중인 쓰레드 중 가장 우선순위가 높은 head에 있는 쓰레드를 비교하여

 

세마포어 정렬을 수행했다.

 

 

 

+ cond_signal()

void
cond_signal (struct condition *cond, struct lock *lock UNUSED) {
	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,sema_more_priority,NULL);
		sema_up (&list_entry (list_pop_front (&cond->waiters),
					struct semaphore_elem, elem)->semaphore);
	}
}

 

이 함수로 cond_wait하고 있는 쓰레드의 작업을 할 수 있는 상태로 만들어 주기 위해 현재 쓰레드가 임계 영역에서 데이터를 수정해 놓고

 

기다리는 쓰레드에게 신호를 주어 이어 작업하도록 요청한다.

 

 

---

LOCK

 

마지막으로 동기화를 적용하는 lock 방식에 대해 확인 해 보자.

 

락은 특정 쓰레드가 임계구역을 사용하겠다고 선언할 때, lock 구조체에 그 쓰레드가 기억된다.

 

이후 동기화를 보장하는 것은 semaphore의 변수로 수행하는데,

 

락의 주인 스레드에게 기다리는 스레드가 우선순위를 donate하는 방식이 추가되어 이를 사용해야 한다.

 

 

이 이유는 임계영역을 동기화하는 메커니즘과 관련이 있다.

 

 

임계 영역을 쓰고 싶은 쓰레드들은 다른 쓰레드가 해당 임계영역을 차지하고 있다면

 

아무리 그 차지한 쓰레드가 우선순위가 낮더라도 해당 작업이 끝나기 전까진 기다려야 한다.

 

 

근데 만약 우선순위가 높으신 쓰레드가 기다리는데 해당 작업을 해야되는 쓰레드가 우선순위가 낮아서

 

다른 쓰레드에 의해 순위가 밀리면 우선순위가 높은 쓰레드는 계속 실행하지 못하는 모순이 발생한다.

 

따라서 우선순위가 높은 쓰레드가 임계영역을 사용하려고 기다린다면,

 

해당 임계영역을 사용 중인 쓰레드(lock의 주인)는 기다리는 쓰레드 중 가장 높은 우선순위를 물려받아 수행함으로써

 

위와 같은 상황을 해결할 수 있다.