PintOS Project 1.2(2) - Priority Scheduling-Synchronization(정글사관학교 58일차 TIL)

1. 과제 개요: FIFO -> Priority Scheduling 기반으로 thread가 CPU 점유하도록 구현

현재 핀토스는 semaphore를 대기하고 있는 스레드 리스트인 waiters가 FIFO로 구현되어 있다고 한다. 이게 무슨 말인지부터 이해하도록 하자.

 

먼저 세마포어에 대해 간단히 짚고 넘어간다. 저번 과제 1.1에서 Process synchronization에 대해 간략하게 소개했다. 동시에 서로 다른 프로세스 혹은 스레드가 공유 자원에 접근하면 충돌이 발생하기 때문에 이를 막아줘야 한다. 이 공유 데이터가 존재하는 영역을 critical section(임계 구역)이라고 하며, 하나의 스레드가 여기에 들어와 작업하고 있으면 다른 애들은 바깥에서 줄 서서 기다리고 있어야 한다.

 

이를 해결하기 위해 추상화한 개념이 세마포어(semaphore)이다. 세마포어는 추상 자료형(ADT)으로, 정수 형태의 변수이며 두 가지 연산 - P연산(세마포어 변수 값을 획득)과 V연산(세마포어를 다 쓰고 반납) -으로 접근이 가능하다. 디테일한 건 아래에서 설명하겠다. 세마포어를 쓰는 이유는 공유 자원에 lock을 걸고/풀고 하는 것을 추상화하여 쉽게 접근하기 위함이다. 이 공유 데이터를 하나의 스레드가 획득/반납하는 걸 세마포어가 처리하게 하는 것이다. 이렇게 하면 사용자가 일일이 알고리즘을 짜는 게 아니라 세마포어를 이용해 프로그램을 하는 것.

다시 문제로 돌아온다. 이 세마포어를 처리하는 방식이 FIFO(FIrst In, First Out) 방식으로 구현되어 있다고 했다. 아래 그림 예시를 보자. 왼쪽은 FIFO 방식이며 오른쪽은 Priority Scheduling이다. x축이 시간, y축이 priority이다.

 

공통 부분부터 보자. 가장 아래 연두색 블록이 처음 lock을 받는다. 연두색 블록이 들어오는 시점을 기준으로는 이외에 어떤 블록도 없기 때문이다. 이후에 들어온 파란색 블록이 lock을 요청한다. 이때까지만 해도 waiters에는 동일하다. 이제 그 다음 블록인 연보라 블록부터 상황이 달라지는데, 왼쪽의 FIFO에서는 우선순위를 전혀 고려하지 않으니 자연스럽게 head 블록인 파란색 다음으로 연보라가 온다. 하지만 오른쪽 이미지에서는 Priority를 고려하기 때문에 head 블록으로 연보라가 오고 파란색 블록은 tail로 밀려난다. 그 다음 역시 왼쪽은 무조건 tail에 붙고 오른쪽에서는 우선순위를 고려해 적절한 위치를 찾아간다. 어디서 많이 보지 않았나? 바로 과제 1.2에서 썼던 list_insert_ordered()가 여기서도 쓰일 것이라는 게 보인다.

(좌) FIFO: 우선순위와 상관없이 먼저 들어온 파란 블록이 먼저 lock을 받음 / (우) Priority Scheduling: 우선순위가 가장 높은 연보라색이 가장 먼저 lock을 획득

 

2. 수정 및 추가 함수

위 함수들을 살펴보기 전에, 먼저 세마포어 구조체가 어떻게 생겼는지부터 보자.

 

struct semaphore

@/include/threads/synch.h

/* A counting semaphore. */
struct semaphore {
	unsigned value;             /* Current value. */
	struct list waiters;        /* List of waiting threads. */
};

세마포어 구조체 멤버에는 해당 자원의 개수를 나타내는 value와 이 자원을 기다리는 스레드가 줄 서있는 waiters 리스트가 들어있다. 이때, waiters 리스트에 매달려있는 애는 정확히 누구일까? 그냥 스레드인가? 그러면 이전에 스레드에서 갖고 있던 elem인가? 하지만 해당 elem은 스레드가 ready queue에 매달려 있기 위한 용도이므로, 세마포어를 위한 또다른 elem을 만들어줘야 한다. 따라서 세마포어 elem 구조체가 필요하다.

@/threads/synch.c

/* One semaphore in a list. */
struct semaphore_elem {
	struct list_elem elem;              /* List element. */
	struct semaphore semaphore;         /* This semaphore. */
};

 

이어서 다른 함수들까지 살펴본다.

 

sema_init()

void sema_init (struct semaphore *sema, unsigned value) {
	ASSERT (sema != NULL);

	sema->value = value;
	list_init (&sema->waiters); // waiters에 
}

세마포어를 초기화하는 함수. 주어진 value로 초기화하며 빈 waiters 리스트를 생성한 다음 곧장 해당 세마포어를 리스트의 첫째 자리에 넣는다.

 

sema_down(): 세마포어의 P연산. semaphore를 요청하고 획득했을 때 semaphore value 값을 1 낮춘다.

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_push_back (&sema->waiters, &thread_current ()->elem); // FIFO
    thread_block ();
    }
    sema->value--;
    intr_set_level (old_level);
}

세마포어의 P연산에 해당하는 sema_down(). 즉, 자원을 획득하는 연산이다. 현재 자원이 없는 상태라면(sema->value==0) while문을 돌면서 현재 스레드를 waiters 리스트의 맨 끝에 삽입한 다음 block 상태로 만들어 재운다. 자원이 생기면 sema->value >0이 되면서 while문을 종료하고 sema->value 값을 1 내린 뒤 해당 스레드가 자원을 획득할 수 있게 해준다. 이 과정에서 다른 인터럽트의 허용을 막는다.

 

waiters 리스트의 맨 끝에 삽입하는 것을 보아 FIFO로 구성되어 있는 것을 알 수 있다.

 

sema_up(): 세마포어의 V연산. critical section에서 작업을 마치고 semaphore 를 반환한 뒤 value 값을 1 올린다.

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

	ASSERT (sema != NULL);

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

세마포어의 V연산에 해당하는 sema_up(). 즉, 자원을 반납하는 연산이다. 현재 waiters 리스트에서 기다리고 있는 스레드가 있다면 리스트 맨 앞에 있는 스레드를 unblock시켜서 꺠운다. 그러면 기다리고 있던 스레드가 알아서 P연산으로 자원을 가져갈 것이다. 이 과정에서 인터럽트를 허용하지 않게 설정한다. 여기서 역시 waiters 리스트 맨 앞에서 First Out하는 것을 볼 수 있다.(list_pop_front).

 

여기서 cond_wait, cond_signal 함수가 나온다. 여기부터는 condition variable에 대해 이해할 필요가 있다.

 

Condition variable with monitor system

조건 변수를 뜻하는 condition variable은 모니터라는 추상 구조체에서 사용하는 변수이다. 내용이 조금 길어질 수 있는데, 모니터 개념부터 잡고 들어가자.

 

앞에서 정리했던 세마포어는 P, V 연산을 통해서 자원의 동기화를 지원한다. 이때, 프로그래머가 자칫 실수라도 하면 문제가 발생할 위험이 높다. 반면, 모니터는 프로그래밍 언어 차원에서 동시 접근과 관련한 공유 데이터 문제를 모니터가 자동으로 알아서 해결하게 해준다. 즉, 프로그래머의 부담을 확 줄인다는 장점이 있다.

 

공유 데이터에 접근할 때, 접근하는 코드와 공유 데이터를 모니터 안에 배치시킨다. 프로세스가 공유 데이터에 접근하려고 하면 모니터 안에 정의된 오퍼레이션을 이용해야만 가능하게 한다. 만약 공유 데이터에 동시 접근하려고 하면 모니터가 애초부터 막는다. 모니터 안에서 활동하는 프로세스가 하나만 있게 모니터가 제어하는 방식이다.

 

예시를 보자. 만약 프로세스 A가 공유 데이터에 작업하기 위해 모니터 안에 와서 프로세스를 실행하고 있다. 이때 다른 프로세스 B가 CPU를 선점해서 모니터에 접근하려고(=공유 데이터에 접근하려고) 하면 어떻게 될까? 프로세스 A가 모니터 접근 코드를 실행하는 도중에 CPU를 빼앗겼기 때문에 여전히 프로세스 A는 액티브 상태로 모니터 안에 남아 있다. 이 경우 다른 프로세스는 모니터에 접근하지 못하고 waiters 리스트에 줄을 선다.

 

그러면 이 프로세스들은 언제 모니터에 접근할 수 있을까? 모니터 내에서 액티브 상태인 프로세스 수가 0이 될 때이다. 즉, 모니터를 쓰고 있던 프로세스가 CPU를 얻어서 다 쓰고 나가거나, 혹은 이 프로세스가 모니터 내부에서 요건을 충족하지 못해 잠드는 상태로 변경된다면 그제야 모니터 밖에서 기다리던 프로세스가 안으로 슉 들어간다.

 

이렇게 하면 무슨 장점이 있을까? 기존의 세마포어에서는 lock 기능이 필요했지만, 여기서는 lock이 필요 없다. 모니터가 알아서 제어하기 때문에 프로그래머 입장에서 훨씬 수월하다. 그럼 어떻게 프로세스가 모니터 안에서 기다리고 접근하고를 통제하나? 바로 통제변수 condition variable을 통해서이다.

 

어떤 프로세스가 모니터 안에서 작업하다가 조건이 충족되지 않아 기다려야 한다면? 프로세스를 재운다. 이때, 어떤 조건이 충족되지 않아서 잠들었는지, 그 해당 조건을 변수로 둘 수 있는데 이것이 condition variable이다. 핀토스 상에서는 condition variable에 대한 인자를 받기는 하나 어떤 조건에 대한 변수인지를 받는지는 나와있지 않다. 즉, 어떤 상태로 잠들었는지는 여기서는 알 수 없으나 wait과 signal 함수로 condition 구조체 안에 정의되어 있는 waiters list 멤버 안에 스레드를 줄세운다. 이때, 아래 구현 파트에서 cond_wait()와 cond_signal()을 수정해 FIFO가 아닌 우선순위 순서로 삽입하도록 수정한다.

 

/* Condition variable. */
struct condition {
	struct list waiters;        /* List of waiting threads. */
};

 

에라이..내친 김에 lock까지 정리하고 구현 파트로 넘어간다. 과제 구현만 보고싶은 분들은 잽싸게 패쓰.

 

lock은 binary semaphore이다. 즉, 세마포어 value가 1로, 공유 자원에 접근 가능한 프로세스/스레드가 오직 하나 뿐이다. 이 경우에는 MUTEX를 만족한다. (여기서 MUTEX란, 상호 배제를 만족한다는 뜻으로 어떤 스레드가 오직 자신만이 특정 자원에 접근하는 것을 보장받는 상황을 의미한다. 뮤텍스는 일종의 상황 개념인데, 바이너리 세마포어와 같이 오직 하나만 들어갈 수 있고 나머지는 배제 당하는 바이너리 케이스에서 뮤텍스를 만족한다고 보면 되겠다. 그냥 "value가 1인 세마포어인 상황"이라고 생각하면 될듯). 

 

struct lock
{
	struct thread *holder; /* Thread holding lock */
	struct semaphore semaphore; /* Binary semaphore controlling access. */
};

 

3. Priority Scheduling-Synchronization 구현

 

sema_down(): list_push_back => list_insert_ordered()로 변경, 

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_push_back (&sema->waiters, &thread_current ()->elem); // FIFO
		
		/* project 1.3 Priority Scheduling & Sync */
		list_insert_ordered(&sema->waiters, &thread_current ()->elem, &cmp_priority, NULL);
		thread_block ();
	}
	sema->value--;
	intr_set_level (old_level);
}

기존에 FIFO로 삽입하는 list_push_back()을 제거하고 list_inser_ordered()로 수정했다. 이때, 우선순위를 비교하는 함수인 cmp_priority()를 cmp_sem_priority로 변경한다. 기존 cmp_priority는 스레드 내 구조체를 가지고 오지만 세마포어끼리는 세마포어 elem 구조체가 별도로 존재하기 때문에 이를 가지고서 스레드를 불러와야 한다. 기본 골조는 거의 비슷하다.

 

cmp_sem_priority()

 

semaphore_elem으로부터 각 semaphore_elem의 쓰레드 디스크립터를 획득한다. 이 쓰레드 디스크립터로 우리는 해당 스레드 자체를 가져올 수 있고, 그러면 그 스레드 내에 있는 priority 값 역시 들고 올 수 있다.

/* --- project 1.3 --- */

bool cmp_sem_priority (const struct list_elem *a, const struct list_elem *b, void *aux) {

	struct semaphore_elem * sa = list_entry(a, struct semaphore_elem, elem); 
	struct semaphore_elem * sb = list_entry(b, struct semaphore_elem, elem);
	

	struct list_elem *sa_e = list_begin(&(sa->semaphore.waiters));
	struct list_elem *sb_e = list_begin(&(sb->semaphore.waiters));

	struct thread *sa_t = list_entry(sa_e, struct thread, elem);
	struct thread *sb_t = list_entry(sb_e, struct thread, elem);
	return (sa_t->priority) > (sb_t->priority);

}

sa, sb는 세마포어 내 waiters 리스트에 줄 서있는 리스트 element a, b로부터 세마포어 element를 가리키는 변수이다. 이는 이전에 ready_list 내에 있는 list_elem이 thread와 연결되어 있던 것처럼 waiters 리스트 내 elem과 세마포어 elem이 서로 공유하는 구조라고 생각하면 되겠다. 아래 이미지에서 thread => semaphore, ready_list =>waiters.list라고 생각하자.

 

sema_up()

waiters list에 있는 스레드의 우선순위가 변경됐을 경우를 고려해 waiters list에 우선순위 기반으로 정렬하며 이를 위해 list_sort를 사용한다.(*if 문 아래서 중괄호 치는 것 주의. 별 거 아닌데 여기서 중괄호 안 치고 if문 아래 연속으로 코드치는 바람에 계속 에러가 났더라!)

 

이후에 ready_list에서 head에 있는 스레드의 우선순위가 더 높다면 현재 스레드가 해당 스레드에게 CPU를 양보해야 하니 이전 과제에서 추가했던 선점 기능인 test_max_priority() (우선순위를 기반으로 선점하는 기능)를 세마포어 자원을 해제(++;)한 뒤에 추가한다.

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

	ASSERT (sema != NULL);
	
	old_level = intr_disable ();
	if (!list_empty (&sema->waiters))
	// 중괄호 안 쳤던 게 문제였음...! 주의!
	{
		/* project 1.3 Priority Scheduling & Sync */
		list_sort(&sema->waiters, &cmp_priority, NULL);
		thread_unblock (list_entry (list_pop_front (&sema->waiters),
					struct thread, elem));
	}
	sema->value++;
	/* --- project 1.3 Priority Scheduling & Sync --- */
	test_max_priority();
	/* --- project 1.3 Priority Scheduling & Sync --- */
	intr_set_level (old_level);
}

 

cond_wait()

condition variable 내 waiters list에 스레드를 대기시키는 함수. 어떤 스레드 하나가 critical section에 들어가 있다면 lock에서는 하나의 스레드 이외의 나머지는 CS에 들어갈 수 없으며 바깥에서 줄서서 대기하고 있어야 한다. 이때, 줄서는 기준이 원래는 FIFO였다면 지금은 우선순위를 기반으로 줄을 세워주기로 수정해야 하니 list_insert_ordered를 쓴다. 이때, 줄 서 있는 애는 세마포어 내 semaphore elem이니 cmp_sem_priority()를 사용한다.

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);
	/* --- project 1.3 priority scheduling & sync 8--- */
	//list_push_back (&cond->waiters, &waiter.elem);
	list_insert_ordered(&cond->waiters, &waiter.elem, &cmp_sem_priority, NULL);
	/* --- project 1.3 priority scheduling & sync 8--- */
	lock_release (lock);
	sema_down (&waiter.semaphore);
	lock_acquire (lock);
}

 

cond_signal()

여기서는 중간에 우선순위가 바뀌었을 수 있으니 waiters list 내 우선순위를 점검하고(list_sort), 그 다음 리스트 맨 앞에 있는 우선순위가 가장 높은 스레드에 대해 sema_up을 실행한다.

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))
	{
		/* --- project 1.3 Priority scheduling & sync --- */
		list_sort(&cond->waiters, &cmp_sem_priority, NULL);
		/* --- project 1.3 Priority scheduling & sync --- */
		sema_up (&list_entry (list_pop_front (&cond->waiters),
					struct semaphore_elem, elem)->semaphore);
					}
}