[운영체제] Part 3 - 프로세스 동기화:: 동기화 도구들

서정범·2024년 2월 19일
OS
0

운영체제

목록 보기
7/16

협력적 프로세스는 시스템 내에서 실행 중인 다른 프로세스의 실행에 영향을 주거나 영향을 받는 프로세스입니다.

협력적 프로세스는 논리 주소 공간(즉, 코드 및 데이터)을 직접 공유하거나 공유 메모리 또는 메시지 전달을 통해서만 데이터를 공유할 수 있습니다. 그러나 공유 데이터를 동시에 접근하면 데이터의 일관성을 망칠 수 있습니다.

이를 위해서 추가적인 매커니즘이 요구됩니다.

1. 배경

앞에서 우리는 다중 처리기에 대해서 알아보았고, 다중 코어를 사용해서 여러 프로세스들을 병행하게 실행할 수 있다는 것을 알았습니다.

만약 서로 다른 프로세스 혹은 스레드들이 같은 데이터에 접근하여 값을 수정하려고 한다면 어떠한 일이 발생할까요?

예를 들어서, Count++와 Count--를 병행하게 실행했다고 가정해 봅시다.

문장 Count++는 다음과 같은 기계어로 구현될 수 있습니다.

register_1 = count
register_1 = register_1 + 1
count = register_1

여기서 register_1은 한 CPU만 접근할 수 있는(local) 레지스터 중 하나입니다. 마찬가지로, 문장 Count--는 다음과 같이 구현됩니다.

register_2 = count
register_2 = register_2 - 1
count = register_2

여기서 register_2 역시 한 CPU만 접근할 수 있는 레지스터 중 하나입니다. register_1과 register_2가 동일한 물리적 레지스터(이를테면, 누산기)이더라도, 이 레지스터의 내용은 인터럽트 처리기에 의하여 메모리에 보관되었다가 다시 적재됩니다.

만약, 해당 두 문장들이 병행하게 실행되어서 제시한 저수준의 문장들이 임의의 순서로 뒤섞여 실행된다면, 다음과 같은 상황이 초래될 수 있습니다.

T0: producer execute register_1 = count	{register_1 = 5}
T1: producer execute register_1 = register_1 + 1	{register_1 = 6}
T2: consumer execute register_2 = count	{register_2 = 5}
T3: consumer execute register_2 = register_2 - 1	{register_2 = 4}
T4: producer execute count = register_1	{count = 6}
T5: consumer execute count = register_2	{count = 4}

이처럼 동시에 여러 개의 프로세스가 동일한 자료를 접근하여 조작하고, 그 실행 결과가 접근이 발생한 특정 순서에 의존하는 상황을 경쟁 상태(race condition)이라고 합니다.

2. 임계구역 문제

임계구역(critical section)은 코드 부분을 포함하고 있고, 적어도 하나 이상의 다른 프로세스와 공유하는 데이터에 접근하고 갱신할 수 있는 영역을 의미합니다.

임계구역 안에서 실행될 수 있는 것은 하나의 프로세스입니다. 즉, 임계구역안으로 들어가기 위해서 프로세슨는 허가를 요청 받아 들어가야 하며, 처리를 한 후 허가를 반환해야 합니다.

따라서, 다음과 같이 구분할 수 있습니다.

진입 구역(entry section) -> 임계 구역(critical section) -> 퇴출 구역(exit section)

임계구역 문제에 대한 해결안은 다음의 세 가지 요구 조건을 충족해야 합니다.

  1. 상호 배제(mutual exclusion): 프로세스 PiP_i가 자기의 임계구역에서 실행된다면, 다른 프로세스들은 그들 자신의 임계구역에서 실행될 수 없습니다.
  2. 진행(progress): 임계구역에서 실행되는 프로세스가 없고 진입하려는 프로세스들이 있다면, 그 프로세스들 중에서 하나를 선택해야 하며, 이 선택은 무한정 연기될 수 없습니다.
  3. 한정된 대기(bounded waiting): 프로세스가 임계구역에 진입하려는 요청을 한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 그들 자신의 임계구역에 진입하도록 허용되는 횟수에 한계가 있어야 합니다.

이것은 커널에서도 자주 발생하는데 여러 인터럽트가 동시다발적으로 발생하여 같은 자원 혹은 처리를 실행할 경우에 발생할 수 있습니다.

만약 단일 코어 환경에서 공유 변수를 수정하는 동안 인터럽트가 발생하는 것을 막으려고 한다면 실행하는 동안 인터럽트의 발생을 막아버린다면 데이터의 일관성을 지킬 수 있을 것입니다.

하지만, 이것은 시스템의 효율성을 떨어뜨립니다. 무엇보다 다중 처리기 환경에서 시간적인 문제가 크게 작용합니다.

비선점형 커널을 사용함으로써 문제를 해결해보려고 할 수 있으나, 선점형 커널이 응답에 더 민첩하게 반응할 수 있고, 실시간 프로그래밍에 적합하여 결국 모든 문제가 해결되지는 않습니다.

3. Peterson의 해결안

Peterson의 해결안은 임계구역과 나머지 구역을 번갈아 가며 실행하는 두 개의 프로세스로 한정됩니다. 프로세스는 P0P_0과 P1P_1로 번호를 매깁니다. 편의상 PiP_i라고 표현하면 PjP_j는 다른 프로세스를 가리키고 jj는 1−i1 - i와 같게 됩니다.

다음 두 개의 데이터 항목을 공유합니다.

  • turn 변수: 두 프로세스 중 어느 하나가 우선적으로 임계 구역에 들어갈 수 있는 권한을 가지는지
  • flag 배열: 두 프로세스 각각의 의사(의도)를 표현

프로세스 PiP_i의 구조 예시 코드는 다음과 같습니다.

while(true) {
	flag[i] = true;
    turn = j;
    while (flag[j] && turn == j); // 상대방이 임계구역에 들어갈 의도가 있으며, turn이 상대방에게 있다면 "대기"
    
    /*	Critial Section	*/
    
   flag[i] = false;
   
   /*	ramainder section */
}

다음과 같은 로직대로 동작합니다.

  1. 프로세스는 자신의 flag를 turn로 설정하고, turn을 상대방에게 넘깁니다.
  2. 그리고 나서 프로세스는 두 조건이 모두 참이 될 때까지 대기합니다: 상대방의 flag가 true인 경우(즉, 상대방도 임계 구역에 들어가고자 하는 의도가 있음)와 turn이 상대방에게 있는 경우입니다. 이 두 조건이 참일 때, 현재 프로세스는 대기 상태에 머무릅니다.
  3. 상대방의 flag가 false이거나 turn이 자신에게 온 경우(즉, 상대방이 임계 구역에 들어가고자 하는 의도가 없거나, 상대방이 자신에게 우선 순위를 양보한 경우), 프로세는 임계 구역에 들어갈 수 있습니다.

해당 방식은 최신 컴퓨터 아키텍처에서 작동한다고 보장되지 않습니다. 주된 이유는 컴파일러가 종속성이 없는 읽기와 쓰기 작업을 재정렬할 수 있기 때문입니다.

예를 들어, 두 스레드 간에 공유되는 다음 데이터를 고려해보자.

boolean falg = false;
int x = 0;

여기서 Thread 1은 다음 명령문을 수행합니다.

while (!flag)
	;
print x;

그리고 Thread 2는 다음 명령문을 수행합니다.

x = 100;
flag = true;

변수 flag와 x 사이에 데이터 종속성이 없으므로 프로세서가 스레드 2의 명령어를 재정렬하여 x = 100을 배정하기 전에 flag가 true로 지정될 수 있습니다.

이러한 문제를 해결하기 위해서 메모리 배리어(memory barrier) 혹은 볼러타일(volatile) 키워드와 같은 매커니즘을 고려할 수 있습니다.

4. 동기화를 위한 하드웨어 지원

여기서 살펴볼 것은 3가지 입니다.

  • 메모리 장벽(Memory Barriers)
  • 하드웨어 명령어(Hardware Instructions)
  • 원자적 변수(Atomic Variables)

4.1 메모리 장벽

컴퓨터 아키텍처가 응용 프로그램에게 제공하는 메모리 접근 시 보장되는 사항을 결정한 방식을 메모리 모델이라고 합니다. 일반적으로 메모리 모델은 두 가지 범주 중 하나에 속합니다.

  1. 강한 순서. 한 프로세서의 메모리 변경 결과가 다른 모든 프로세서에 즉시 보임.
  2. 약한 순서. 한 프로세서의 메모리 변경 결과가 다른 프로세서에 즉시 보이지 않음.

메모리 변경의 가시성에 대한 문제를 해결하기 위해서 컴퓨터 아키텍처는 메모리의 모든 변경 사항을 다른 모든 프로세서로 전파하는 명령어를 제공하여 다른 프로세서에서 실행 중인 스레드에 메모리 변경 사힝이 보이는 것을 보장하는데 이러한 명령어를 메모리 장벽(memory barriers) 또는 메모리 펜스(memory fences)라고 합니다.

앞서 봤던 코드에 메모리 장벽 연산을 추가하면,

x = 100;
memory_barrier(); // 메모리 변경사항이 모든 스레드에게 가시적이도록 함
flag = true;

이렇게 사용할 경우 flag 값이 x 값보다 먼저 적재되도록 보장합니다.

메모리 장벽은 매우 낮은 수준의 연산으로 간주하며 일반적으로 상호 배제를 보장하는 특수 코드를 작성할 때 커널 개발자만 사용합니다.

4.2 하드웨어 명령어

많은 현대 기계들은 한 워드(word)의 내용을 검사하거나 변경하거나, 두 워드의 내용을 원자적으로 교환(swap)할 수 있는, 즉 인터럽트 되지 않는 하나의 단위로서, 특별한 하드웨어 명령어들을 제공합니다.

여기서는 두 가지 명령어에 대해서 설명을 하고 있습니다.

  • test_and_set()
  • compare_and_swap()

먼저, test_and_set()의 중요한 특징으로는 명령어가 원자적(automically)으로 실행된다는 점입니다.

다음은 원자적 test_and_set() 명령어의 코드를 보여줍니다.

boolean test_and_set(boolean *target) {
	boolean rv = *target;
    *target = true;
    
    return rv;
}
do {
	while (test_and_set(&lock))
    ;	/* do nothing */
    
    /* critical section */
    
    lock = false;
    
    /* remainder section */
} while (true);

CAS는 test_and_set() 명령어와 마찬가지로 두 개의 워드에 대해 원자적인 연산을 하지만 두 워드의 내용 교환에 기반을 둔 다른 기법을 사용합니다.

CAS는 3개의 피연산자를 대상으로 연산을 하며, 좀 더 세밀하게 로직을 제어할 수 있습니다. 코드는 아래와 같습니다.

int compare_and_swap(int *value, int expected, int new_value) {
	int temp = *value;
    
    if (*value == expected)
    	*value = new_value;
        
    return temp;
}
while (true) {
	while (compare_and_swap(&lock, 0, 1) != 0)
    	;	/* do nothing */
        
    /* critical section */
    
    lock = 0;
    
    /* remainder section */
}

*value는 해당 메모링 주소에 저장된 정수 값 자체를 의미한다.

함수 내에서 *value에 접근하거나 수정하는 것은, 이 포인터가 가리키는 메모리 위치에 접근하여 값을 읽거나 쓰는 것을 의미합니다.

위와 같이 CAS를 사용할 경우 상호 배재 조건은 만족시키지만 한정된 대기 조건을 만족시키지 못합니다. 아래의 코드는 한정된 대기 조건을 만족시키는 상호 배제 코드입니다.

while (true) {
	waiting[i] = true;
    key = 1;
    while (waiting[i] && key == 1)
    	key = compare_and_swap(&lock, 0, 1);
    waiting[i] = false;
    
    /* critical section */
    
    j = (i + 1) % n;
    while((j != i) && waiting[j])
    	j = (j + 1) % n;
        
    if (j == i)
    	lock = 0;
    else 
    	waiting[j] = false;
        
    /* remainder section */
}

해당 코드는 앞서 언급했던 3가지의 요구 조건을 충족합니다.

  • 상호 배제 - CAS
  • 진행 - lock 혹은 waiting[]
  • 한정된 대기 - 배열 순환

test_and_set()과 compare_and_swap()에 대해서 다루었는데, 가지고 있는 단점은 다음과 같습니다.

  • test_and_set(): test_and_set()을 사용한 스핀락 구현은 바쁜 대기(busy-wait) 상태에서 리소스를 낭비할 수 있습니다. CAS를 사용한 구현은 실패했을 때 대기하는 로직을 더 세밀하게 제어할 수 있습니다.
  • compare_and_swap(): CAS 연산은 ABA 문제에 취약할 수 있습니다. 이는 값 A가 다른 값 B로 변경되었다가 다시 A로 돌아가는 상황에서, CAS 연산은 메모리 위치 값이 여전히 expected 값과 동일하다고 판단하여 연산이 성공했다고 보고할 수 있지만, 사이에 다른 변경이 있었던 것을 감지하지 못합니다. test_and_set()은 이러한 문제를 고려하지 않으며, 단순히 락의 상태만 변경합니다.

4.3 원자적 변수

일반적으로 compare_and_swap() 명령어는 상호 배제를 제공하기 위해 직접 사용되지 않습니다. 오히려 임계구역 문제를 해결하는 다른 도구를 구축하기 위한 기본 구성요소로 사용됩니다.

그러한 도구 중 하나는 원자적 변수(atomic variable)로, 정수 및 부울과 같은 기본 데이터 유형에 대한 원자적 연산을 제공합니다.

예를 들어 다음 코드를 봐봅시다.

increment(&sequence);
void increment(atomic_int *v)
{
	int temp;
    
    do {
    	temp = *v;
    } while (temp != compare_and_swap(v, temp, temp+1));
}

원자적 변수는 원자적 갱신을 제공하지만 모든 상황에서 경쟁 조건을 완벽히 해결하지는 안습니다.

예를 들어서, 유한 버퍼 문제에서 count 변수를 원자적 정수로 정의한다고 해봅시다. count가 0인 상황에서 생산자가 버퍼에 하나의 항목을 입력한 경우, 카운트는 단지 1로 세트되었는데도 만약 접근하려고 하는 소비자가 2명 이상이라면 여러 소비자는 while 루프를 빠져나와 데이터를 소비할 수 있습니다.

따라서 이러한 race condition 문제를 해결하기 위해선 더 강력한 도구가 필요합니다.

5. Mutex Locks

상위 수준 소프트웨어 도구들 중에 가장 간단한 것이 mutex 락입니다.

mutex라는 용어는 Mutual exclusion의 약자입니다.

프로세스는 임계구역에 들어가기 전에 반드시 락을 획득해야 하고 임계구역을 빠져나올 때 락을 반환해야 합니다.

다음 코드 예시를 확인해 봅시다.

acquire() {
	while (!available)
    	; /* busy wait */
    available = false;
}
release() {
	available = true;
}
while (true) {
	// acquire lock
    
    	/* critical section */
        
    // relase lock
    
    	/* remainder section */        
}

이 방식의 단점은 바쁜 대기(busy waiting)을 해야한다는 점입니다. 프로세스가 임계구역에 있는 동안 임계구역에 들어가기를 원하는 다른 프로세스들은 acquire() 함수를 호출하는 반복문을 계속 실행해야 합니다.

이러한 mutex 락 유형을 스핀락(spinlock)이라고도 하는데, 락을 사용할 수 있을 때까지 프로세스가 "회전"하기 때문입니다. 만약, 문맥 교환하는데 상당한 시간이 소요된다고 하면 문맥 교환을 필요로 하지 않는 이 방식은 장점이 됩니다.

스핀락은 락이 짧은 기간 동안 유지될 때 다중 처리기 시스템에서 선택하는 락 기법으로 취급되빈다. 여기서 말하는 짧은 기간이라 함은 보통 문맥 교환을 두 번 하는 시간보다 짧은 경우를 의미하고 이러한 경우에 스핀락을 사용합니다.

6. 세마포어

세마포어(Semaphores)는 mutex와 유사하게 동작하지만 프로세스들이 자신들의 행동을 더 정교하게 동기화할 수 있는 방법을 제공합니다.

세마포어 S는 정수 변수로서, 초기화를 제외하고는 단지 두 개의 표준 원자적 연산 wait()와 signal()로만 접근할 수 있습니다.

두 연산의 정의는 다음과 같습니다.

wait(S) {
	while (S <= 0)
    	; // busy wait
    S--;
}
signal(S) {
	S++;
}

6.1 세마포어 사용법

운영체제는 종종 카운팅(counting)과 이진(binary) 세마포어를 구분합니다.

  • 카운팅 세마포어: 유한한 개수를 가진 자원 대한 접근을 제어하는 데 사용될 수 있습니다.
  • 이진 세마포어: 0과 1의 값만 가지며, mutex 락과 유사하게 동작합니다.

앞서 위에서 간단하게 봤던 세마포어의 구현도 바쁜 대기를 사용하고 있는데 이것의 단점을 극복하기 위해서 블록킹(blocking)이나 대기-통지(wait-notify) 매커니즘을 이용할 수 있습니다.

우선 전통적인 방식으로 CAS와 바쁜 대기를 사용한 코드를 살펴봅시다.

void acquire(semaphore *S) {
    while (true) {
        int value = S->value;
        if (value > 0 && compare_and_swap(&(S->value), value, value - 1)) {
            break; // 세마포어 획득 성공
        }
        // 여기에 blocking 코드 혹은 다른 최적화 방법 사용 가능
    }
}

void release(semaphore *S) {
    atomic_increment(&(S->value)); // S->value의 값을 안전하게 1 증가
}

6.2 세마포어 구현

좀 더 성능을 높이기 위해서 바쁜 대기 방식이 아닌 블로킹 대기와 조건 변수를 사용한 세마포어 구현을 살펴봅시다. POSIX 스레드 라이브러리(pthread)를 사용한 예시는 다음과 같습니다.

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct semaphore {
    int value;
    pthread_mutex_t mutex;
    pthread_cond_t cond;
} semaphore;

void semaphore_init(semaphore *s, int value) {
    s->value = value;
    pthread_mutex_init(&s->mutex, NULL);
    pthread_cond_init(&s->cond, NULL);
}

void semaphore_wait(semaphore *s) {
    pthread_mutex_lock(&s->mutex);
    while (s->value <= 0) {
        pthread_cond_wait(&s->cond, &s->mutex);
    }
    s->value--;
    pthread_mutex_unlock(&s->mutex);
}

void semaphore_signal(semaphore *s) {
    pthread_mutex_lock(&s->mutex);
    s->value++;
    pthread_cond_signal(&s->cond);
    pthread_mutex_unlock(&s->mutex);
}

void *worker(void *param) {
    semaphore *s = (semaphore *)param;

    printf("Trying to enter critical section...\n");
    semaphore_wait(s);
    printf("Entered critical section.\n");
    // Critical section code goes here.
    printf("Leaving critical section.\n");
    semaphore_signal(s);

    return NULL;
}

int main() {
    semaphore s;
    semaphore_init(&s, 1); // Initialize semaphore with value 1.

    pthread_t t1, t2;
    pthread_create(&t1, NULL, worker, &s);
    pthread_create(&t2, NULL, worker, &s);

    pthread_join(t1, NULL);
    pthread_join(t2, NULL);

    return 0;
}

코드를 살펴봅시다.

  • semaphore_init: 세마포어를 초기화하는 함수, 세마포어의 초기 값과 함께 뮤텍스 및 조건 변수도 초기화
  • semaphore_wait: 세마포어를 대기(획득)하는 함수, 세마포어의 값이 0 이하가 될 때까지 스레드를 블록, 조건 변수를 사용하여 대기 상태로 전환
  • semaphore_signal: 세마포어를 신호(해제)하는 함수, 세마포어의 값을 1 증가시키고, 대기 중인 스레드 중 하나를 깨웁니다.
  • worker: 실제 작업을 수행하는 스레드 함수, 임계 구역에 대한 접근을 제어

좀 더 구체적인 동작을 살펴보기 위해서 코드에서 사용하고 있는 pthread의 함수에 대해서 살펴봅시다.

pthread_cond_wait(&s -> cond, &s -> mutex)

  • 역할: pthread_cond_wait 함수는 스레드를 조건 변수 s->cond에 대해 대기 상태로 만듭니다. 이 함수는 두 개의 인자를 받습니다.
    • 대기할 조건 변수
    • 조건 변수를 사용하기 위해 잠금 해야하는 뮤텍스
  • 동작 방식: 이 함수는 뮤텍스 s->mutex를 자동으로 잠금 해제하고, 호출한 스레드를 대기 상태로 전환시킵니다. 그 후, 조건 변수에 대한 신호가 다른 스레드에 의해 전송될 때까지 스레드를 블록합니다. 신호를 받으면, 스레드는 다시 실행을 재개하기 전에 뮤텍스 s->mutex를 자동으로 잠금합니다.
  • 사용 목적: 특정 조건(예: 자원의 가용성)이 충족될 때까지 스레드를 안전하게 대기시키는 데 사용됩니다.

pthread_cond_signal(&s -> cond)

  • 역할: 대기 중인 스레드 중 하나에게 조건 변수 s -> cond에 대한 신호를 전송합니다. 이는 대기 중인 스레드가 조건 변수에 대해 대기 상태에서 벗어나 동작을 계속하도록 합니다.
  • 동작 방식: 이 함수를 호출하면, s -> cond에 대해 대기하고 있는 스레드 중 하나(있을 경우)가 깨어나게 됩니다. 이 스레드는 뮤텍스 s -> mutex를 잠금해야 다시 실행을 계속할 수 있습니다.
  • 사용 목적: 조건이 충족되었을 때 대기 중인 스레드를 깨우는 데 사용됩니다.

pthread_mutex_unlock(&s -> mutex)

  • 역할: 뮤텍스 s->mutex의 잠금을 해제합니다.
  • 동작 방식: 이 함수를 호출하면, 뮤텍스에 대한 잠금이 해제되어 다른 스레드가 뮤텍스를 획득할 수 있는 기회를 제공
  • 사용 목적: 뮤텍스로 보호되는 임계 구역의 작업을 완료한 후에, 다른 스레드가 임계 구역에 접근할 수 있도록 잠금을 해제하는 데 사용됩니다.

간단하게 정리하자면, 변수 S를 뮤텍스로 보호하여 원자적 접근을 하도록 하고, 세마포어 로직을 통해서 임계구역을 보호합니다.

7. 모니터

앞서 mutex와 세마포어를 사용하는 이유는 타이밍 오류로 인해서 잘못된 동작을 하는 상황을 피하기 위해서 사용한다고 했습니다. 하지만, 이러한 도구를 사용한다고 해서 무조건적으로 회피할 수 있는 것은 아닙니다.

예를 들어서, 다음과 같인 순수한 프로그래밍 오류 또는 비협조적인 프로그래머를 예시로 볼 수 있습니다.

signal(mutex);

	// critical section
    
wait(mutex)

혹은

wait(mutex);

	// critical section
    
wait(mutex);

물론 이러한 상황은 극단적으로 보일 수 있지만, 많은 코드들을 다루는 과정에서 실수가 발생할 수 있다는 것을 배제할 수는 없습니다. 따라서, 고급 언어 구조물 중 하나인 모니터(monitors)를 살펴볼 필요가 있습니다.

7.1 모니터 사용법

추상화된 데이터 형(abstract data type, ADT)은 데이터와 이 데이터를 조작하는 함수들의 집합을 하나의 단위로 묶어 보호합니다. 이때 함수의 구현은 ADT의 특정한 구현과는 독립적입니다.

모니터 형은 모니터 내부에서 상호 배제가 보장되는 프로그래머가 정의한 일련의 연산자 집합을 포함하는 ADT입니다.

간단하게 말하자면, 모니터라는 객체가 함수들을 감시하면서 해당 함수의 실행이 하나의 프로시저에서만 활성화 되어지도록 보장하는 것을 의미합니다. 

monitor monitor_name
{
	/* shared variable declarations */
    
    function P1 ( . . . ) {
     . . .
    }
    
    function P2 ( . . . ) {
     . . .
    }
    
    		.
            .
            .
    function Pn ( . . .) {
     . . .
    }
    
    initialization_code ( . . . ) {
     . . .
    }
}

부가적인 동기화 기법들이 정의가 되어야 하는데 condition이라는 구조물로 제공될 수 있습니다.

condition x, y;

x, y와 같은 변수들을 사용하여 wait(), signal() 함수들을 이용하면 되고 이후 코드들에 대한 설명들은 생략하겠습니다.

8. 라이브니스

라이브니스는 프로세스가 실행 수명주기 동안 진행되는 것을 보장하기 위해 시스템이 충족해야 하는 일련의 속성을 말합니다.

라이브니스 실패의 매우 간단한 예는 무한 루프입니다. 여기서는 라이브니스 실패로 이어질 수 있는 두 가지 상황에 대해 제시하고 있습니다.

  • 교착 상태(Deadlock)
  • 우선순위 역전(Priority Inversion)

우선 교착 상태를 살펴보는데, 두 시스템이 아래와 같이 설계되어 있다고 가정해 봅시다.

P0P_0P1P_1
wait(S);wait(Q);
wait(Q);wait(S);
. . .. . .
signal(S);signal(Q);
signal(Q);signal(S);

두 세마포어 변수 S,Q에 서로 다른 프로세스가 동시에 접근하는 상황으로 만약 동시에 실행해서 P0P_0이 wait(S);를 실행하였고, P1P_1이 wait(Q);를 실행했다면 두 프로세스는 교착 상태가 됩니다.

우선순위 역전은 높은 우선순위 프로세스가 현재 낮은 우선순위 프로세스 또는 연속된 낮은 우선순위 프로세스들에 의해 접근되고 있는 커널 데이터를 읽거나 변경할 필요가 있을 때 스케줄링이 어려움이 생기는 것을 의미합니다.

예를 들어서, 우선순위 L < M < H 순서인 L, M, H 세 개의 프로세스가 존재한다고 가정해봅시다.

프로세스 H가 세마포어 S가 필요하고, 이 자원은 현재 프로세스 L에 의해 접근되고 있는 상황입니다.

보통은 프로세스 H는 L이 자원의 사용을 마칠 때까지 기다리게 됩니다. 그러나 이 순간 프로세스 M이 실행 가능한 상태가 되고, 따라서 프로세스 L을 선점했다고 한다면 간접적으로 낮은 우선순위 프로세스(프로세스 M)는 프로세스 H가 L이 자원을 양도할 때 까지 기다려야 하는 시간에 영향을 주게 됩니다.

이러한 경우 우선순위 상속 프로토콜(priority-inheritance protocol)을 이용하여 해결할 수 있는데, 더 높은 우선순위 프로세스가 필요로 하는 자원에 접근하는 모든 프로세스는 문제가 된 자원이 사용이 끝날 때 까지 더 높은 우선순위를 상속받습니다.

자원 사용이 끝나면 원래 우선순위로 되돌아 갑니다.

9. 평가

여러 연산 방법을 봤기 때문에 어떠한 상황에 무엇을 사용할 지 정리를 해볼 필요가 있습니다.

원자적 정수는 기존 락보다 훨씬 가벼우며 일반적으로 카운터와 같은 공유 변수에 대한 단일 업데이트에는 mutex 락 또는 세마포어보다 더 적합하다.

락이 짧은 기간동안 유지될 때 다중 처리기 시스템에서 스핀락의 사용을 선호하는데 이러한 경우 mutex 락이 세마포어보다 간단하고 오버헤드가 적으므로 더 선호된다.

한정된 수의 자원에 대한 접근을 제어하는 것과 같은 일부 용도의 경우 카운트 세마포어가 mutex 락보다 더 적합하다.

유사하게, 일부 경우에 read-writer 락이 mutex 락보다 선호될 수 있습니다. reader는 여러 개일 수 있음을 허용할 수 있기 때문입니다.

모니터와 조건 변수와 같은 고급 도구를 사용하여 단순성과 사용 편의성의 이점을 가져갈 수도 있지만 상당한 오버헤드가 있을 수 있으며 구현에 따라 경합이 심한 상황에서는 확장성이 안좋을 수 있다는 점을 염두해두자.

참고한 자료

  • 운영체제[공룡책]
profile
서정범
개발정리블로그
이전 포스트

[운영체제] Part 2 - 프로세스 관리 :: CPU 스케줄링

다음 포스트

[운영체제] Part 3 - 프로세스 동기화:: 동기화 예제

0개의 댓글