210204 개발일지(59일차) - 운영체제(OS) 프로젝트 #1-4 : Priority Scheduling and(with) Synchronization(feat. 세마포어 = semaphore)

Priority Scheduling and(with) Synchronization

앞에서 봤듯, 우리는 이제 스레드들이 가지고 있는 우선순위에 따라 cpu를 점유할 수 있도록 만들어줬다.
현재의 스레드들은 아래와 같은 특성들을 갖는다.

비동기적(Asynchronous)

스레드(프로세스)들이 서로에 대해 모르는 상태

병행적(Concurrent)

여러 스레드(프로세스)들이 시스템 상에 존재

위의 특성들로 인해, 병행 수행 중인 비동기적 스레드(프로세스)들이 공유 자원(=공유 데이터, Critical data)에 동시에 접근할 때 문제가 될 수 있다.
※ 임계 영역(Critical Section) : 공유 데이터를 접근하는 코드 영역(code segment)

쉽게 말하면, 깃발은 하난데 여러 개의 스레드가 그 깃발을 차지하려는 상황이 발생할 수 있다는 말이다.
그 상황을 막기 위해, 둘 이상의 스레드(프로세스)가 동시에 critical section에 진입하는 것을 막는 상호배제(Mutual exclusion)를 해줘야 한다.

세마포어(semaphore)

상호배제(Mutual exclusion)를 위해 세마포어 개념을 사용할 것이다.
세마포어란 여러 프로세스/스레드가 공유된 자원의 데이터에 접근하는 것을 Signaling mechanism을 이용하여 통제하는 것을 말하며, 독일의 컴퓨터 사이언티스트인 Edsger Dijkstra가 고안하였다.
P()연산, V()연산을 활용해서 다양한 세마포어 방식으로 상호배제를 할 수 있지만, 이번 과제에서는 Binary semaphore를 활용해서 상호배제를 구현할 것이다.

Binary semaphore

위의 그림 상의 active 변수에 0, 1만 활용해서 상호배제 및 스레드(프로세스)들의 동기화를 해준다.
1 : 임계 지역을 실행 중인 스레드(프로세스)가 없어서 임계 지역을 통해 공유 데이터를 활용할 수 있는 상황
0 : 임계 지역을 실행 중인 스레드(프로세스)가 있어서 임계 지역을 통해 공유 데이터를 활용할 수 없는 상황
active 변수가 0일 때는, 공유 데이터 및 임계 지역에 접근하고자 하는 스레드(프로세스)들이 따로 대기하는 리스트에서 대기하도록 한다.

구현

세마포어 구조체

세마포어 구조체는 아래와 같다. 위의 active변수에 해당하는 value 변수에 0, 1을 활용하고 waiters라는 list에 대기 스레드(프로세스)를 대기시킨다.

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

sema_down() 함수

특정 스레드(프로세스)가 공유 데이터를 활용할 수 있는 상황인 value==1일 때는, 그 스레드가 임계 영역을 활용한다는 의미로(실제로 그 스레드가 cpu를 점유) sema_down()이라는 함수를 활용해서 value를 1→0으로 낮춰준다.

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, cmp_priority, NULL);		//waiters에 스레드들의 도착 순으로 넣어준다.
	    thread_block ();
	}
	sema->value--;
	intr_set_level (old_level);
}

sema_up() 함수

특정 스레드(프로세스)가 공유 데이터를 활용하고 나서, 더 이상 공유 데이터를 활용하지 않는 상황이 오면 sema_up() 함수를 활용해서 value를 0→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++;
    thread_yield();			// 다음 순서의 스레드가 cpu를 점유할 수 있도록
    intr_set_level (old_level);
}

위와 같이 스레드들의 비동기적, 병행적이라는 특성을 극복하기 위해 semaphore개념을 사용하여 동기화를 도와주었다. 그러나, 위의 코드 및 개념만으로는 우선순위 역전현상(Priority Inversion Problem)이 발생한다. 위에서 본 semaphore 구조체 안에 waiters list에 스레드들이 들어갈 때, 시간 순으로 들어가게 돼서 우선순위를 적용받지 못한다.
그 해결법을 다음 포스팅에서 알아보자. 그리고 project1을 끝내보자....
(위의 그림에서 "Lock"은 일단, 세마포어라고 생각하고 넘어가자)