동기화

Ranccat·2024년 8월 6일
OS

Operating System

목록 보기
6/9

📖 본 글은 모든 내용을 "Operating System Concepts Ed.10"에서 인용합니다.

👋 동기화는 무엇일까?

하나의 시스템 안에 무수히 많은 쓰데드가 실행되고 있다.
그만큼 하나의 데이터가 여러 쓰레드로부터 접근되고, 수정되기도 한다.

💡 A race condition exists when access to shared data is not controlled, possibly resulting in corrupt data values.

공유 데이터에 대한 제어가 제대로 되지 않는다면 race condition (경쟁상태)이 발생할 수 있다.

💡 Process synchronization involves using tools that control access to shared data to avoid race condition.

프로세스 동기화가 각종 도구들을 활용하여 경쟁상태를 피하는 것이다.

단, 경쟁상태를 피하는 과정에서 데드락이 발생하지 않도록 주의해야 한다!

경쟁상태가 발생하는 코드 예시를 봐보자.
count라는 공유변수가 하나 존재하고, 초기값은 5로 세팅되어 있다.
이 변수를 동시에 2개의 프로세스가 전급한다고 가정한다.
프로세스1은 count++을, 프로세스2는 count--을 실행하는 로직이다.

코드를 어셈블리 기준으로 뜯어봐야 하는데, 편의상 보기 쉽게 작성하였다.

// 프로세스 1
register1 = count
register1 = register1 + 1 // Contect Switch
count = register1

// 프로세스 2
register2 = count
register2 = register2 - 1
count = register2

우선 프로세스1이 먼저 count에 접근하게 된다.
프로세스1에서 count 값인 5를 가져오고 register1에 저장한다.
후에 register1에 1을 더했기 때문에 register1에는 6이 저장되게 된다.
하지만 이 때, 인터럽트가 발생하여 문맥교환이 일어났다고 치자.

프로세스2가 같은 코드 영역으로 들어와서 count를 받아온다.
여기서 중요한건 count는 아직 5라는 값이 저장되어있다는 것이다!
register2에 5에 저장되고, 1을 뺀 다음, 다시 count에 저장한다.
여기까지 정리하면 count에는 4가 저장되어 있는 것이다.

다시 스케줄링이 되다가 프로세스1의 차례가 되었다.
아까 실행하지 못했던 마지막 코드를 실행해야 하는데, register2에는 6이 들어있다.
이 6을 count에다가 저장하고 코드는 마무리가 된다.

이제 시나리오가 끝이 났는데, 원래대로라면 count에 뭐가 저장되어야 하는가?
count++과 count--가 지나갔으니 그대로 5가 저장되어야 한다.
그러나, 방금 살펴봤듯이 6이 저장된 상태로 끝나는 경우가 생긴다!

💡 A situation like this, where several processes access and manipulate the same data concurrently and the outcome of the execution depends on the particular order in which the access takes place, is called a race condition.

이처럼 여러 프로세스의 실행 순서에 따라 결과값이 달라질 수 있는 것을 경쟁상태라 부른다.

1. 임계구역 (Critical Section)

💡 Consider a system consisting of n processes. Each process has a segment of code, called a critical section, in which the process may be accessing (and updating) data that is shared with at least one other process.

하나 이상의 프로세스가 접근하고 수정할 수 있는 데이터가 있는 코드의 영역을 임계구역이라고 한다.

💡 The critical-section problem is to design a protocol that the processes can use to synchronize their activity so as to cooperatively share data.

임계구역 문제는 프로세스간에 협동적으로 자원을 공유할 수 있게 프로토콜을 만드는 것이다.

💬 프로토콜은 행동 규약을 정의하는 "약속"이라고 보면 된다.

여기서 중요한 것은 임계구역이라는 말은 말그대로 "구역"을 뜻하는 말이다.
즉, 특정 공유 자원이 아닌 코드의 일부분을 지칭하는 말임을 명심하자!

임계 구역을 다루기 전에 영역을 조금 더 세분화 할 수가 있다.

임계 구역에 진입하기 위해 허락을 받는 곳이 entry section,
임계 구역에서 나올 때의 로직을 처리하는 곳이 exit section,
그 외의 모든 코드 영역을 remainder section이라고 한다.

이러한 임계구역을 해결하기 위한 방법은 다음 3가지 원칙을 지켜야 한다.

  1. Mutual exclustion (상호 배제)

    • 하나의 프로세스가 임계구역에 들어왔다면, 다른 프로세스는 들어올 수 없다.

  2. Progress (진행)

    • 어떠한 프로세스도 임계구역에 없지만, 들어가고 싶은 프로세스가 존재한다면,
      remainder구역에 있지 않은 프로세스만이 다음 입장 프로세스를 결정해야 한다.
    • 또한, 이 선택은 무기한으로 연장될 수 없어야 한다.

  3. Bounded waiting (유한 대기)

    • 어떠한 프로세스가 임계구역 입장을 신청하고 들어가기 전까지의 시간동안,
      그 영역에 다른 프로세스가 접근할 수 있는 횟수에 제한이 있어야 한다.
      (일정 횟수 안에는 신청한 프로세스가 들어갈 수 있어야 한다)

마지막으로, 커널에서의 경쟁상태를 특히 조심해야 한다는 것을 알아야 한다.
여러 프로세스가 동시에 fork()를 호출한다면, 서로 다른 프로세스가 같은 id를 가질 수도 있다.

그래서 커널에서의 임계구역 처리 방식이 크게 2가지가 있다.

우선 비선점형 커널 방식이 있는데, 말 그대로 프로세스가 커널 영역을 끝까지 실행하는 것이다.
커널 코드를 실행하는 동안만큼은 인터럽트를 허용하지 않는다.
이 방법은 경쟁상태를 아예 만들지 않는다는 강점이 있다.

다른 방식이 선점형 커널 방식인데, 비선점과 반대로 인터럽트를 허용하는 것이다.
아무리 커널이라도 프로세스는 도중에 CPU를 놓아주어야 한다.
이 방법은 아무래도 경쟁상태를 생성한다는 점에서 굉장히 위험하다.
심지어 SMP 아키텍처에서 구현하기도 꽤나 힘들다.

그러면 왜 굳이 선점형 커널을 사용해야만 할까?

바로 "반응성"이다.
만약 프로세스가 커널에 접근했는데, 하필 완료까지 오래 걸리는 코드라면?
사용자 입장에서는 컴퓨터가 먹통이 된 것처럼 느낄 수 있을 것이다.

결국 여러 프로세스를 동시에 실행시키는 것처럼 보이게 하는 "동시성"을 보장하기 위함이다.

2. 피터슨 해결법

피터슨 해결법 (Peterson's Solution)은 임계구역 문제를 해결하는 방법이다.
하드웨어의 도움 없이 소프트웨어적으로 해결하는 아이디어를 얻기 좋다.

단, 2개의 프로세스에 한해서만 가능 방식이니 실용성보다는 이론적으로 접근하도록 하자.

우선 코드를 보면서 하나씩 살펴보도록 하자.

// int turn;
// boolean flag[2];

while (true) {
	flag[i] = true;
    turn = j;
    while (flag[j] && turn == j)
    	;
    /* critical section */
    flag[i] = false;
    /* remainder section */
}

위의 코드에서 turn과 flag는 다른 어딘가에 선언된 변수들이다.

turn이 뜻하는 것은 임계구역으로 들어간 순서가 누구 차례인지 나타낸다.
flag는 해당 프로세스가 임계구역으로 들어갈 준비가 되어있는지를 나타낸다.

이 해결법에서의 키포인트는 "너먼저"이다.
i는 임계구역으로 들어가기 전, 본인의 flag를 세우고 상대의 turn으로 바꿔준다.
즉, 나는 준비 되어있지만 너 먼저 들어가라 라고 하는 것과 같다.

그렇다면 j프로세스가 임계구역을 나오면서 본인의 flag를 끄게 되는데,
i가 갇혀있는 while문 조건이 flase가 되면서 임계구역으로 들어가게 된다.

이런식으로 동작하게 되면, 임계구역 해결의 3원칙을 지킬 수가 있다.
1. while문에서 상대 프로세스의 입장 상태를 확인하여 상호 배제가 보장된다.
2. j프로세스가 i프로세스의 입장을 결정한다.
3. 어떤 프로세스든 무조건 다음 차례가 본인이다.

그러나, 이렇게 소프트웨어적으로 처리하는 것은 큰 문제가 있다.

💡 As mentioned at the beginning of this section, Peterson's solution is is not guaranteed to work on modern computer architectures for the primary reason that, to improve system performance, processors and/or compilers may reorder read and write operations that have no dependencies.

현대 컴퓨터에서 이 방법이 적절하지 않는 이유는, 컴파일러와 프로세서가 의존성이 없는 읽기/쓰기의 순서를 효율적이게 재배치할 수 있기 때문이다.

한마디로, flag와 turn을 수정하는 부분이 순서가 바뀌어서 엉망이 될 수 있다는 것이다.

그래서 임계구역 문제를 해결하기 위해서는 하드웨어의 도움이나 API가 필요하다.

3. 하드웨어 기능

앞서 말했듯이 software-based한 해결법은 실용성이 없다.
그래서 하드웨어 기능을 먼저 알아보고, 이 기능들을 활용한 API를 알아볼 예정이다.

메모리 베리어

💡 How a computer architecture determines what memory guarantees it will provide to an application program is known as its memory model.

컴퓨터 아키텍처는 메모리 모델에 따라 메모리의 보장성을 결정한다.

메모리 모델은 크게 2종류가 있다.

  1. Strongly ordered
    프로세서의 메모리 수정이 다른 프로세서에게 즉각적으로 반영된다.

  2. Weakly ordered
    프로세서의 메모리 수정이 즉각적으로 반영되지 않을 수 있다.

이러한 메모리에 대한 보장성은 프로세서의 타입마다 다를 수 있다.

하지만 OS는 어떻게든 임계구역을 해결하기 위해서 메모리의 수정을 즉각 반영할 필요가 있다.
그래서 등장하게 된 것이 memory barrier (또는 memory fence)이다.

💡 When a memory barrier instruction is performed, the system ensures that all loads and stores are completed before any subsequent load or store operations are performed.

메모리 베리어 명령이 실행된 경우, 다른 프로세스가 접근하기 전에 수정사항이 적용되어야 한다.

실제로 어떻게 사용되는지 간단한 예제 코드를 살펴보자.

while (!flag)
	memory_barrier();
print x;

메모리 베리어가 flag를 얻을 때까지 변수 x에 접근하지 못하도록 막는다.

그러나 이 명령어를 직접 사용하는 건 어디까지나 커널 개발자들의 역할이다.

하드웨어 명령어

현대의 많은 컴퓨터 시스템은 원자적으로 실행되는 함수를 제공한다.

test_and_set()

그 중 대표적인 test_and_set() 함수에 대해 먼저 알아보자.
우선 함수의 정의는 다음과 같은 모습이다.

boolean test_and_set(boolean *target) {
	boolean rv = *target;
    *target = true;
    
    return rv;
}

target의 boolean값을 rv에 저장을 해두고, target은 true로 바꿔준다.
이후, target의 바뀌기 전의 boolean 값을 return해준다.

다시 강조하지만, 위 함수는 원자성을 가지고 있다.
즉, uninterruptible이다!

만약 2개의 코어에서 동시에 위의 함수를 실행하고자 한다면,
랜덤한 순서로 "순차적으로" 실행이 된다.
한 코어에서 함수 실행을 완료해야만 다른 코어에서 함수 실행을 시작한다.

그래서 test_and_set() 함수가 대체 어디에 쓰이는가?
target에 lock을 인자로 전달하여 임계구역을 막아줄 수 있다.

do {
	while (test_and_set(&lock))
    	;
    /* critical section */
    lock = false;
    /* remainder section */
} while (true);

우선 lock의 기존 값이 false였다고 하자. (입장 가능 상태)
동시에 2개의 프로세스가 lock을 취득하고자 할 때,
함수가 원자적이므로 먼저 실행된 프로세스가 lock을 true로 바꾸고 본인은 false를 받는다.
false를 받았으므로 while문을 나와 임계구역으로 들어간다.

직후에 다른 코어에서 실행되던 프로세스가 lock을 넣어봤더니 true를 받게 된다.
다른 쓰레드가 lock을 사용하고 있다는 뜻이므로 while문에 갇히게 된다.

이런식으로 안전하게 lock을 다룰 수 있게 된다.

compare_and_swap() (CAS)

또다른 대표 함수로는 compare_and_swap() 명령어가 있다.

우선 함수의 정의를 보면서 분석해보자.

int compare_and_swap(int *value, int expected, int new_value) {
	int temp = *value;
    
    if (*value == expected)
    	*value = new_value;
    
    return temp;
}

인자로 총 3개를 건네게 되는데,
공유 변수 하나와 함께 예상 값과 교체하고자 하는 값을 전달한다.

temp에 value의 원래 값을 우선 저장을 해둔 다음,
해당 값이 예상 값과 같은 경우에만 교체하고자 하는 값으로 바꿔준다.
이후 value의 기존 값을 return해주게 된다.

마찬가지로 CAS가 lock을 어떻게 다루는지 예제 코드를 살펴보자.

while (true) {
	while (compare_and_swap(&lock, 0, 1) != 0)
    	;
     /* critical section */
     lock = 0;
     /* remainder section */
 }

사실 결과적으로는 test_and_set과 비슷하게 동작하는 셈이다.
lock을 넘겨주고, 사용되지 않았다는 0을 예상 값으로 넘겨준다.
그리고 예상대로 사용되지 않은 값이라면 본인이 사용하겠다는 의미로 1을 넘겨준다.

내부적으로는 lock이 0인 경우에만 0을 return함으로 입장이 가능하고,
예상대로 0이었다면 새로운 값인 1로 바꿔줌으로써 다른 프로세스의 입장을 막는다.

원자성(Atomic) 변수

사실 일반적으로는 CAS를 직접적으로 코드에 활용하지는 않는다.
대신, 원자 변수에 증감연산을 하는 함수 내부적으로 활용이 된다.

경쟁상태를 위에서 예시를 들었을 때, 단순 증감 연산에도 문제가 생기는 경우를 봤다.
그러한 상황을 막기 위해 원자 변수를 따로 만들어서 독자적인 증감 함수를 사용한다.

예를 들어서 int형 원자 변수에다가 단순히 1을 더하는 함수를 만든다고 치자.

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

위 코드의 포인트는 v의 값이 증가하지 않았다면 while문을 나오지 못한다는 것이다.
즉, 1이 잘 더해질때까지 계속해서 CAS를 실행해서 +1을 보장하게 된다.

4. 뮤텍스락 (Mutex Locks)

💡 Operating-system designers build higher-level software tools to solve the critical-section problem. The simplest of there tools is the mutex lock.

OS 디자이너들은 임계구역 문제를 해결하기 위해 high-level한 기능을 제공한다.
그 중 가장 간단한 형태의 툴이 바로 뮤텍스락이다.

💬 Mutex는 Mutual Exclusion (상호 배제)의 약자이다.

뮤텍스락은 작동방식이 논리적으로는 굉장히 간단하다.

  1. 입장 전에 acquire()을 통해 lock을 취득한다.
  2. 퇴장 시에 release()를 통해 lock을 내려놓는다.

이 과정에서 lock으로 쓰이는 것은 boolean 값인 available이다.

aquire()의 정의는 다음과 같다.

acquire() {
	while (!available)
    	; // busy wait
    available = false;
}

release()의 정의는 다음과 같다.

release() {
	available = true;
}

단, 저 함수 정의는 논리적인 정의일 뿐이다.
실제로는 위에서 본 CAS를 통해 원자적으로 구현되어야 한다.

또한, 위에서 제공된 예시에서의 while문을 보면,
acquire가 한번에 성공하지 못하면 busy waiting을 하는 것을 볼 수 있는데,
이러한 방식을 "spin lock"이라고 부른다

💬 while문 안에서 빙글빙글 돈다고 해서 "spin" lock이다.

참고로 spin lock 방식은 비효율적으로 보일 수 있지만,
문맥교환이 일어나지 않는다는 점에서 꽤 강점을 가질 수 있다.

멀티코어 환경에서는 다른 코어가 임계구역을 나갈때까지 기다렸다가 바로 들어가면 된다.

그러나 spin lock 대신 프로세스 자체를 재워버리는 방식을 사용하게 되면,
금방 들어갈 수 있었음에도 문맥교환이 일어나서 오버헤드가 발생할 수도 있다.

그래서 실제로는 많은 OS가 spin lock을 사용한다!

5. 세마포어 (Semaphores)

세마포어는 뮤텍스락에 비해 더 탄탄하고 세련된 방식을 사용한다.

💡 A semaphore S is an integer variable that, apart from initialization, is accessed only through two standard atomic operations: wait() and signal().

세마포어 정수값인 S는 원자함수인 wait()와 signal()로만 접근 가능하다.

wait()의 정의는 다음과 같다.

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

signal()의 정의는 다음과 같다.

signal(S) {
	S++;
}

뮤텍스락과 마찬가지로, 두 함수는 모두 원자적으로 작성되어야 한다!

여기도 마찬가지로 busy wait을 하고 있는데,
이를 해결하기 위한 방안은 조금 아래에서 알아보도록 하자.

카운팅 세마포어 & 이진 세마포어

카운팅 세마포어 (counting semaphore)는 범용적으로 사용될 수 있고,
이진 세마포어 (binary semaphore)는 오로지 0과 1만 사용한다.

💬 이진 세마포어의 경우에 뮤텍스락과 비슷하기 때문에 대신 사용되기도 한다.

카운팅 세마포어의 경우에 S를 허용하고자 하는 프로세스의 개수로 세팅한다.

예를 들어, 프로세스가 총 5개가 있는데, 3개만 허용하고 싶다면 S = 3로 설정한다.

프로세스는 들어올 때마다 wait() 함수를 호출하고,
그에 따라 S의 값이 1이 작아진다.

반대로 프로세스가 나갈 때에는 signal() 함수를 호출하고,
S의 값을 1씩 올린다. (최대 3까지만)

결국 S가 0이라면 더이상 프로세스가 임계구역으로 들어올 수 없다는 뜻이다.

세마포어 구현

앞서 다뤘던 busy wait을 보완하는 방식에 대해 알아보겠다.

wait()을 호출했을 때, semaphore가 0이라 입장할 수 없는 경우에는
프로세스가 자기 자신을 suspend하는 방식을 체택할 수 있다.
suspend는 프로세스를 일시 중단하여 waiting 상태로 보내는 것이다.

sleep() 함수를 호출하면 자기 자신을 suspend 할 수 있다.

그리고 다른 어떤 프로세스가 signal()을 호출하게 되면,
suspend한 프로세스 중 하나를 깨워서 입장시키는 방식을 사용할 수 있다.
그리고 깨어난 프로세스는 ready 큐로 가게 된다!

다른 프로세스를 깨우는 것은 wakeup() 함수로 가능하다.

이제 sleep()과 wakeup()을 사용하는 세마포어의 코드를 살펴보자.

typedef struct {
	int value;
    struct process *list;
} semaphore;

세마포어의 구조체는 다음과 같이 정의될 수 있다.
S를 담당하는 int형 value 하나와,
sleep()을 호출한 프로세스가 대기하는 별도의 리스트다.

이제 wait() 함수는 다음과 같은 pseudo 코드로 구현될 수 있다.

wait(semaphore *S) {
	S->value--;
    if (S->value < 0) {
    	add this process to S->list;
        sleep();
    }
}

조금 특이한 점은, S를 고려하지 않고 일단 -1을 해준 뒤에,
음수값이 된 경우에 스스로를 리스트에 추가하고 sleep()을 호출한다.

이제 signal() 함수의 pseudo 코드를 살펴보자.

signal(semaphore *S) {
	S->value++;
    if (S->value <= 0) {
    	remove a process P from S->list;
        wakeup(P);
    }
}

마찬가지로 일단 S에 1을 더한 뒤에 0보다 큰지 확인하다.
0보다 커진 경우에만 대기 큐에서 프로세스 하나를 깨워준다.

이렇게 S를 음수값으로 두면, 그 절댓값이 기다리는 프로세스의 개수이다!

그리고 list에 실제로 저장되는 것이 PCB이다.

참고로 PCB 큐의 구현 방식은 자유롭게 해도 상관없다.

오히려 제일 중요한 점은 함수를 반드시 원자적으로 구성해야 한다는 것!

6. 모니터 (Monitors)

열심히 뮤텍스락과 세마포어에 대해서 공부했지만, 사실 둘 다 위험성이 존재한다.
악의적인 코드 수정이나 개발자의 실수로 인해 쉽게 망가질 수 있기 때문이다.

그래서 보다 high-level하고 추상적인 장치가 필요함을 느꼈다.

Abstract Data Type (ADT)는 데이터를 다루는 함수들의 집합이다.
이 과정에서 함수의 구현 여부는 아무런 영향이 없다.

💡 A monitor type is an ADT that includes a set of programmer-defined operations that are provided with mutual exclusion within the monitor.

Monitor type은 상호 배제를 위해 존재하는 일종의 ADT이다.

모니터는 내부적으로 보관하는 변수에 상호배제를 보장해준다.
그 과정에서 세마포어를 사용하되, "조건"이라는 개념을 새로 도입한다.

생소한 개념이다 보니 아래의 추상화 그림을 보면서 이해해보자.

우선 가장 아래의 initialization code는 말 그대로 초기화 코드이니 넘어가고,
중요한건 위의 operations와 shared data이다.

shared data가 여러 프로세스가 동시에 접근할 수 있는 데이터이다.
모니터는 이를 잘 보관해주고 있고, 특정 함수를 통해서만 이 데이터에 접근할 수 있다.

그 특정 함수가 바로 operations에 정의되어있는 함수들이다.
공유변수에 대한 접근은 반드시 operations에 있는 함수들로만 가능하다.

마지막으로, condition이라고 하는 조건들은 개발자가 지정하는 것들이다.
모니터가 안전한 기능을 제공함과 동시에 맞춤형으로 사용 가능하게 해주는 결정적인 이유이다.

모든 프로세스는 data에 접근하기위한 "조건"을 만족시켜야 하며,
해당 조건을 만족하지 않았다면 그 조건에 대한 별도의 큐에서 대기한다.

조건이 x라고 한다면, x.wait()와 x.signal()을 통해서만 큐가 관리된다.

마찬가지로, 다른 조건인 y가 있다고 해도 x와 같은 방식으로 동작한다.

정리를 하자면, 모니터 내에 선언된 변수는 반드시 내부 함수로만 접근 가능하며,
해당 변수에 접근하기 전, 여러 조건을 통해 세련되게 관리할 수가 있다.

사실 모니터는 어디까지나 ADT이기 때문에, 구현체가 전부 다르다.
Java와 C#이 대표적으로 모니터를 지원하는 언어이니,
본인이 사용하는 언어의 라이브러리를 직접 확인해보는 것이 가장 좋다.

7. 활성 보장 (Liveness)

💡 Liveness refers to a set of properties that a system must satisfy to ensure that process make progress during their execution life cycle.

활성 보장이란 프로세스에 진전이 있음을 보장하기 위해 시스템이 갖춰야 할 속성이다.

한마디로, 프로세스가 비정상적으로 막히는 일이 없도록 하는 것이다.

아주 간단한 예시로 무한 루프가 있다.
알고리즘 문제를 해결할 때에도, 코드를 잘못 작성하여 루프를 빠져나가지 못하는 상황이 있다.
본래라면 로직을 잘 수행하여 루프를 나와 원하는 답을 도출했을 것이다.

이처럼 정상적이지 않게 코드에 진전이 없는 상황을 "활성 보장 실패"라고 한다.

이와 관련된 유명한 활성 보장 실패 시나리오가 2가지 있다.

교착상태 (Deadlock)

💡 The implementation of a semaphore with a waiting queue may result in a situation where two or more processes are waiting indefinitely for an event that can be caused only by one of the waiting processes. The event in question is the execution of a signal() operation. When such a state is reached, these processes are said to be deadlocked.

세마포어를 사용하게 되면, 2개 이상의 프로세스가 무기한으로 기다리는 상황이 발생할 수 있다.
signal() 함수가 호출되기를 기다리는데, 그 함수를 호출할 프로세스도 wait 상태인 경우가 그러하다.
이렇게 프로세스가 서로를 기다리는 상황을 "교착 상태"에 도달했다고 부른다.

이해하기 쉽게 코드를 보면서 보도록 하자.

P0이 wait(S)까지만 실행을 하고 interrupt가 발생했다고 치자.
그 다음, P1이 wait(Q)까지 실행을 하고 내려갔더니 S가 사용 불가능하다.
이렇게 되면 P1은 S가 사용이 불가능하고, P0은 Q를 사용 불가능하다!

이 현상을 끝내려면 둘 중 하나가 signal()을 호출을 해줘야 하는데,
signal()을 호출하려면 wait()을 통과해야 한다...

이처럼 서로가 서로의 세마포어를 기다리고 있는 상황이 데드락이다.

사실 데드락은 다음 챕터에서 구체적으로 다루고 해결 방안까지 다룰 것이다.
그러나 여기서 소개한 이유는, lock과의 연관성 때문이다.

lock을 안쓴다면 deadlock이 발생할 이유가 없다!

그럼에도 lock은 필수적임으로 deadlock이 발생할 수 밖에 없는데,
이를 해결하기 위해 많은 고민들이 있었고, 그걸 다음 챕터에서 배울 것이다.

우선순위 역전 (Priority Inversion)

우선순위 역전 현상을 우선순위 스케줄링을 하는 경우에 발생한다.
높은 우선순위의 프로세스가 낮은 프로세스의 lock을 기다리다가 실행이 늦어지는 현상이다.

사실 이 현상은 정의보다는 실제 예시를 들으며 이해하는 것이 더 빠르다.

우선순위가 높은 H와, 중간의 M, 그리고 낮은 L 프로세스가 있다고 하자.
(M이 실행되다가 H가 큐에 들어오면 H를 먼저 실행해야 한다)

L이 특정 자원에 접근하기 위해 세마포어인 S를 요청한다.
그러다가 H가 큐에 들어와서 H로 스케줄링된다.
그리고 H도 S가 필요한 상황이 왔는데, L이 들고있어서 기다려야 한다.
다시 L이 실행이 되고 S를 내려놓기 전, M 프로세스가 등장하여 스케줄링된다.
M은 세마포어는 필요없지만, 단순히 우선순위가 높다는 이유로 먼저 실행된다.
이런 상황에서 L은 세마포어를 놓을 타이밍을 뺏기고, 그로인해 H도 실행이 늦어진다.

이처럼 높은 우선순위를 가지는 프로세스임에도 불구하고,
세마포어와 우선순위 스케줄링 기법의 합작으로 인하여 실행이 늦어지는 것이 우선순위 역전이다.

이를 해결하기 위해서 우선순위 계승 프로토콜이 나오게 됐다.

L이 세마포어를 들 필요가 있는 경우, H의 우선순위를 잠시 빌리는 것이다!
그렇게 되면 L은 세마포어를 사용 후에 곧바로 내려놓을 수 있게 되고,
우선순위를 반납함과 동시에 M을 무시하고 H가 바로 실행된다.

이렇게 하면 우선순위 스케줄링의 정의대로 하면서 세마포어도 사용할 수 있다.

8. 동기화 3대 문제

이 챕터의 원래 이름은 "Classic Problems of Synchronization"이다.
그만큼 예전부터 현재까지 좋은 문제로 남아있다는 뜻이다.

실제로, 새로운 동기화 방식이 제안되면, 이 3대 문제로 검증을 하기도 한다!

Bounded-Buffer (유한 버퍼)

유한 버퍼 문제는 흔히 "생산자 소비자" 문제의 형태를 가지고 있다.
하나의 프로세스는 버퍼에 내용을 채우고, 다른 프로세스는 내용을 읽어서 버퍼를 비우는 것이다.

이 유형의 문제에 세마포어를 적용하여 어떻게 동기화를 하는지 알아보자.

우선, 다음과 같은 변수들이 선언되어있다고 하자.

int n; // max buffer size
semaphore mutex = 1; // binary semaphore
semaphore empty = n; // current size of empty buffer
semaphore full = 0; // current size of full buffer

n은 우선 버퍼의 사이즈를 할당하는 용으로만 사용된다.
mutex는 말그대로 이진 세마포어의 역할을 하기 위한 S이다.
full과 empty는 더했을 때 n이 되도록 빈 공간과 차있는 공간을 나타낸다.

💬 세마포어라고 해놓고 뮤텍스가 등장하는 이유가 뭘까?
이 부분이 헷갈릴 수 있는데, 뮤텍스는 뮤텍스락이 아니다!
어디까지나 mutex라는 단어는 "상호 배제"를 뜻하는 용어일 뿐이다.
사용하는 것은 semaphore가 맞고, 변수명을 mutex라고 지은 것이다.

이제 아래의 생산자 코드와 소비자 코드를 보고 분석해보자.

// producer
while (true) {
	// produce an item
    wait(empty);
    wait(mutex);
    // add produced item to the buffer
    signal(mutex);
    signal(full);
}
// consumer
while (true) {
	wait(full);
    wait(mutex);
    // remove an item from buffer
    signal(mutex);
    signal(empty);
    // consume the item
}

전체적인 구조가, 생산자는 소비자를 위해 full을 생성해주고,
소비자는 생산자를 위해 empty를 생성해주는 구조를 띈다.

Readers-Writers (읽기와 쓰기)

이번에는 조금 더 실생활에 가까운 문제를 얘기해보자.
데이터베이스가 존재하면, 데이터를 읽으려는 reader와 쓰려는 writer가 있을 것이다.
(DB를 공부했다면 각각을 트랜잭션이라고 생각해도 무리없다)

DB에서 과연 reader가 여러개라고 문제가 생길까?
전혀 그렇지 않다. 수정이 없다면 일관성을 해칠 일도 없을 테니까.

그런데 2개 이상의 writer가 데이터에 접근하거나,
또는 writer와 reader가 하나씩 들어가면 어떻게 될까?
전자는 직관적으로도 문제가 있음을 알 수 있고,
후자도 읽는 타이밍이 쓰기 전인지 후인지 보장이 되지 않아 문제가 된다.

참고로 이 읽기-쓰기 문제는 2가지 상황이 존재한다.

  1. 임계 구역에 들어간 것이 reader라면, 다른 reader들은 언제든지 들어간다.
    (즉, writer는 어떠한 reader도 없는 상황까지 기다린다)

  2. writer가 wait를 선언한 이후의 reader들은 writer를 대기한다.
    (즉, writer에게 높은 권한을 줘서 늦게 온 reader들을 쳐낸다)

사실 둘 다 썩 좋은 상황이 아닐 수 밖에 없다.
1번의 경우에는 writer가 기아현상을 겪게 되고,
2번의 경우에는 reader가 기아현상을 겪기 때문이다.

하지만 당장 이 챕터에서 중요한 건 기아현상을 방지하는 것이 아니다.
세마포어를 어떻게 걸어야 할지 고민하는 것이 중요하다.

그렇다면 1번 경우에서의 선언 변수부터 확인하자.

semaphore rw_mutex = 1;
semaphore mutex = 1;
int read_count = 0;

여기부터는 세마포어가 2개라서 헷갈릴 수 있다.
우선 read_count는 말그래도 임계 구역 내의 reader의 수이다.
그리고 이 read_count에 대한 접근을 막아주는 세마포어가 mutex이다.
rw_mutex가 실제로 writer가 하나만 들어갈 수 있게 막아주는 세마포어이다.

read_count 역시 경쟁 상태가 발생할 수 있기에 mutex가 필요하다.

그렇다면 이제 writer와 reader 코드를 보면서 직접 분석해보자.

// writer
while (true) {
	wait(rw_mutex);
    
    /* writing */
    
    signal(rw_mutex);
}
// reader
while (true) {
	wait(mutex);
    read_count++;
    if (read_count == 1)
    	wait(rw_mutex);
    signal(mutex);
    
    /* reading */
    
    wait(mutex);
    read_count--;
    if (read_count == 0)
    	signal(rw_mutex);
    signal(mutex);
}

💬 개인적으로 이 부분과 아래의 철학자 문제는 직접 고민해보는 것이 도움이 되는 것 같다.

Dining-Philosophers (식사하는 철학자)

5명의 철학자가 큰 테이블을 두고 모여서 식사를 하고자 한다.
그런데, 젓가락의 개수가 총 5개밖에 없다!
(밥을 먹으려면 2개의 젓가락으로 한 쌍을 만들어야 한다)

그래서 철학자와 젓가락의 배치가 아래처럼 되어버렸다.

  • 모든 철학자는 반드시 본인 양 옆의 젓가락만 사용하여 밥을 먹을 수 있다.
  • 남이 이미 들고 있는 젓가락을 뺏을 수는 없다.
  • 동시에 2개의 젓가락을 한 번에 들 수는 없다. (한쪽을 들고 나서야 다른쪽을 들 수 있다)
  • 젓가락을 2개 들고 난 후에 식사를 하고 나서 2개의 젓가락을 모두 내려놓는다.

철학자의 정확한 행동 요령은 아래 코드와 같다.

while (true) {
	wait(chopstick[i]);
    wait(chopstick[(i+1)%5];
    
    // eat
    
    signal(chopstick[i]);
    signal(chopstick[(i+1)%5];
	
    // think
}

위의 코드는 i번째 철학자의 코드이다.
그리고 i번째 젓가락은 chopstick 배열의 해당 index에 세마포어를 들고 있다.
i번째 철학자가 i번째 젓가락과 i+1번째 젓가락을 드는 걸 볼 수 있다.

이 문제에서도 마찬가지로 기아 현상에 대해서는 당장 신경 쓸 필요가 없다.
우선 교착상태가 발생하지 않게 하려면 어떤 해결법이 있는지 고민하면 된다.

사실 아주 유명한 해결법이 3개가 있다.
충분히 고민을 해본 뒤에 아래의 방법과 비교해보면 좋을 것 같다.

  • 철학자가 최대 4명만 앉을 수 있게 한다 (여분 젓가락을 하나 만드는 셈)
  • 양쪽의 젓가락이 있는 경우에만 젓가락을 집게 한다
  • 홀수번째 철학자들은 왼쪽 젓가락 먼저, 짝수번째 철학자들은 오른쪽 젓가락을 먼저 들게 한다.

위 3가지 방법이 어떻게 문제를 해결하는지 생각해보면서 챕터를 마무리하자.

🎯 마치며

동기화를 직접 하는 것은 굉장히 복잡하기 때문에 직접하는 것은 피하는 것이 좋아보인다.
각 프로그래밍 언어가 제공하는 라이브러리를 적극적으로 활용하는 것이 현명하다고 생각한다.

출처

Abraham Silberschatz, 『Operating System Concepts Ed.10』

profile
Ranccat
As a junior server programmer, I have a deep enthusiasm for computer science.
이전 포스트

스케줄링

다음 포스트

교착 상태 (Deadlock)

0개의 댓글