프로세스 동기화 - 상호배제 기법

※ 해당 글은 기술 면접 대비 CS 핵심요약을 기반으로, 해당 책의 순서를 참고하여 작성하였습니다.

 

1. 멀티 스레드와 동기화

 

"만약 여러 스레드가 동시에 공유 자원에 접근하면 어떻게 될까?"

 

 

멀티 스레드는 스레드를 여러 개 생성하여 스레드들이 각자 다른 작업을 처리하도록 하는 것을 의미합니다.

멀티 스레드는 스레드간 힙, 데이터, 코드 영역을 공유하기 때문에 콘텍스트 스위칭의 오버헤드가 적고, IPC를 사용하지 않아도 된다는 장점이 있지만 스택 영역을 공유하기 때문에 여러 스레드가 동시에 자원에 접근하는 경우가 발생할 수 있습니다.

 

만약 여러 스레드가 동시에 공유 자원에 접근한다면, 접근하는 순서에 따라 결과 값이 달라질 수 있습니다.

이러한 현상을 경쟁 상태(race condition)이라고 하며 이 중 가장 대표적인 예가 너무 많은 우유 문제(too much milk problem)입니다.

출처 - ChatGPT

 

 

냉장고에 우유가 다 떨어져서 사야 한다고 가정해 봅시다.

1. 엄마가 냉장고에 우유가 없는 걸 확인한다.
2. 엄마가 우유를 사러 슈퍼마켓에 간다.
3. 엄마가 우유를 사러 간 사이 아빠가 냉장고에 우유가 없는 걸 확인한다.
4. 아빠가 우유를 사러 슈퍼마켓에 간다.
5. 우유가 2배 이벤트!

여기서 냉장고는 공유 자원, 엄마와 아빠는 각각 프로세스를 의미합니다.

우유가 0개에서 1개가 되는 걸 기대했지만 2개가 되어버리는 의도치 않은 결과를 초래하게 되었죠.

 

1.1 임계 영역

임계 영역은 공유 자원에 접근할 수 있고 접근 순서에 따라 결과가 달라지는 코드 영역입니다.

위의 예시에서는 냉장고에서 우유 유무를 파악하고 우유를 사 오는 과정이 해당됩니다.

임계 영역에서 경쟁 상태의 발생을 막기 위해서는 여러 프로세스가 공유 자원에 접근해도 데이터의 일관성이 유지되도록 프로세스 동기화가 이뤄져야 하는 겁니다.

• 상호배제 기법(mutual exclusive) : 어떤 프로세스가 임계 영역을 실행중일 때, 다른 프로세스가 임계 영역에 접근할 수 없다.
• 진행(progress) : 임계 영역을 실행 중인 프로세스가 없을 때 다른 프로세스가 임계 영역을 실행한다.
• 한정된 대기(bounded waiting) : 임계 영역에 접근을 요청했을 때 무한한 시간을 기다리지 않는다.

이 중 오늘 알아볼 것은 상호배제 기법의 뮤텍스와 세마포어에 대해 알아보겠습니다.

 

2. 뮤텍스

뮤텍스는 간단하게 말해서, 락을 가진 프로세스만이 공유 자원에 접근할 수 있게 하는 방법입니다.

뮤텍스와 세마포어를 이해하기 가장 좋은 예시 중 하나는 화장실 예(toilet example)가 있습니다.

 

뮤텍스의 작동 방식은 화장실과 화장실 열쇠가 하나뿐인 식당과 동일합니다.

출처 - 기술 면접 대비 CS 핵심요약

정말 간단한 예시입니다.

화장실(임계영역)에 먼저 들어간 프로세스가 화장실 열쇠(lock)를 돌려줄 때까지 다른 프로세스는 대기해야 하는 것이 바로 뮤텍스입니다.

프로세스가 락을 거는 특징 때문에 락킹 매커니즘(locking mechanism)이라 부르기도 합니다.

 

화장실에 들어가지 못한 프로세스는 반복해서 노크를 돌며 락이 풀렸는지 확인합니다.

이를 바쁜 대기(busy waiting)의 한 종류인 스핀락이라고 부릅니다.

프로세스가 대기 상태가 되지 않고 반복문을 돌며 자원의 사용 가능 여부를 확인하므로 프로세스가 빠르게 교체될 수 있다는 특징이 있죠.

 

그다음으로 뮤텍스가 가진 세 개의 알고리즘에 대해 알아보겠습니다.

2.1 데커(Dekker) 알고리즘

데커 알고리즘은 두 개의 스레드 사이에서 동기화를 보장하는 최초의 소프트웨어 기반 해결책입니다.

flag는 누가 CS(Critical Section)에 진입할 것인지 알리는 변수이고, turn은 누가 CS에 들어갈 차례인지 알리는 변수입니다.

작동 원리

1. 두 개의 스레드는 플래그 변수를 사용하여 자원을 사용하고 싶은지 표시합니다.
2. 한 스레드가 자원을 사용 중이면, 다른 스레드는 기다립니다.
3. 공정성을 보장하기 위해 턴(turn) 변수를 사용하여 번갈아가며 기회를 줍니다.

while(true) {
    flag[i] = true; // 프로세스 i가 임계 구역 진입 시도
    while(flag[j]) { // 프로세스 j가 현재 임계 구역에 있는지 확인
        if(turn == j) { // j가 임계 구역 사용 중이면
            flag[i] = false; // 프로세스 i 진입 취소
            while(turn == j); // turn이 j에서 변경될 때까지 대기
            flag[i] = true; // j turn이 끝나면 다시 진입 시도
        }
    }
}

// ------- 임계 구역 ---------

turn = j; // 임계 구역 사용 끝나면 turn을 넘김
flag[i] = false; // flag 값을 false로 바꿔 임계 구역 사용 완료를 알림

---

2.2 피터슨(Peterson) 알고리즘

데커의 알고리즘보다 개선된 버전으로, 두 개의 스레드 간 경쟁을 방지하면서 더 직관적인 구조를 가지고 있습니다.

데커의 알고리즘과 유사하지만 상대방에게 진입 기회를 양보한다는 차이가 있고 보다 더 간단하게 구현되었습니다.

작동 원리

1. 각 스레드는 flag 배열을 사용하여 자신의 의사를 표시합니다.
2. 스레드가 크리티컬 섹션에 들어가기 전, turn 변수를 사용하여 양보할 준비를 합니다.
3. 한 스레드가 실행 중이면, 다른 스레드는 대기합니다.

while(true) {
    flag[i] = true; // 프로세스 i가 임계 구역 진입 시도
    turn = j; // 다른 프로세스에게 진입 기회 양보
    while(flag[j] && turn == j)  // 다른 프로세스가 진입 시도하면 대기
}

// ------- 임계 구역 ---------

flag[i] = false; // flag 값을 false로 바꿔 임계 구역 사용 완료를 알림

---

2.3 램퍼드의 제과점(Lamport's Bakery) 알고리즘

데커와 피터슨이 두 개의 스레드에만 적용된다면, 베이커리 알고리즘은 여러 개의 스레드의 상호배제 문제를 해결한 알고리즘입니다.

이름에서도 알 수 있듯이, 이 알고리즘은 빵집에서 번호표를 뽑고 순서를 기다리는 방식을 모방했습니다.

프로세스에게 고유한 번호를 부여하고, 번호를 기준으로 우선순위를 정해 높은 우선순위 프로세스가 임계 구역에 진입합니다.

작동 원리

1. 각 스레드는 번호표를 뽑습니다.
2. 번호가 작은 스레드부터 차례대로 실행됩니다.
3. 동일한 번호를 뽑았을 경우, 스레드 ID를 비교하여 우선순위를 정합니다.

while(true) {
    isReady[i] = true; // 번호표 받을 준비
    number[i] = max(number[0~n-1]) + 1; // 현재 실행 중인 프로세스 중에 가장 큰 번호 배정 
    isReady[i] = false; // 번호표 수령 완료
    
    for(j = 0; j < n; j++) { // 모든 프로세스 번호표 비교
        while(isReady[j]); // 비교 프로세스가 번호표 받을 때까지 대기
        while(number[j] && number[j] < number[i] || (number[j] == number[i] && j < i));
        // 프로세스 j가 번호표 가지고 있고
        // 프로세스 j가 우선순위가 높거나(number[j] < number[i])
        // 우선순위가 동일한데 j가 i보다 작을경우
        // j가 임계 구역에서 나올때까지 대기
    }
}

// ------- 임계 구역 ---------

number[i] = 0; // 임계 구역 사용 종료

 

---

3. 세마포어

세마포어(Semaphore)는 공유 자원의 접근할 수 있는 프로세스의 수를 정해 접근을 제어하는 방법입니다.

이는 뮤텍스와 유사하지만, 더 확장된 개념으로 볼 수 있습니다.

출처 - 기술 면접 대비 CS 핵심요약

단순하게, 화장실의 개수가 늘어난 뮤텍스와 비슷하다고 생각해도 됩니다.

임계 영역에 접근할 수 있는 키 n개를 준비하고, 이 중 하나를 가진 프로세스만이 접근 가능합니다.

공유 자원에 접근한 프로세스가 접근을 해제하면 다른 프로세스에게 신호를 보내기 때문에 시그널링 매커니즘(signaling mechansim)이라고 부르기도 합니다.

작동 원리

세마포어는 기본적으로 정수 값(카운터)을 사용하여 접근 가능한 프로세스 수를 조절합니다.

• 세마포어 값이 1 이상일 경우, 공유 자원에 접근할 수 있습니다.
• 세마포어 값이 0 이하일 경우, 접근을 시도한 프로세스는 임계 영역에서 대기해야 합니다.
• 세마포어는 P 연산(Wait)과 V 연산(Signal)이라는 두 가지 연산을 사용하여 동작합니다.

P(S) {  // Wait 연산
    while(S <= 0);  // 자원이 없으면 대기
    S--;  // 자원을 사용
}

V(S) {  // Signal 연산
    S++;  // 자원을 반환
}

 

세마포어는 크게 이진 세마포어(Binary Semaphore)와 계수 세마포어(Counting Semaphore) 두 가지로 나뉩니다.

• 이진 세마포어 (Binary Semaphore)
  • 값이 0 또는 1만 가질 수 있어 뮤텍스와 유사하게 동작합니다.
  • 단, 소유권 개념이 없으므로 프로세스가 반드시 자신이 잠금 한 자원을 해제할 필요는 없습니다.
• 계수 세마포어 (Counting Semaphore)
  • 값이 0 이상의 정수를 가질 수 있어 여러 개의 프로세스가 공유 자원에 접근 가능합니다.

Q. 이진 세마포어랑 뮤텍스가 가지는 차이점이 정확히 뭔가요?🤔
A. 저도 사실 거의 비슷한 게 아닌가? 싶어 찾아봤는데 생각보다 차이점이 있더군요.
- 신호 전달 매커니즘 vs lock 매커니즘
- 여러 스레드가 동시에 획득가능 vs 한 번에 하나의 스레드만 획득가능
- 소유권 없음 vs 뮤텍스를 소유한 스레드만 잠금해제 가능
등의 차이점이 있습니다.

 

4. 뮤텍스 vs 세마포어

사용 방식	한 번에 하나의 스레드만 접근 가능 (lock/unlock 방식)	여러 개의 프로세스 또는 스레드가 제한된 개수의 자원 사용 가능
동작 방식	Lock을 건 프로세스만 Unlock할 수 있음	카운터 값을 증가/감소하며 자원 접근을 조절
소유권	소유권 개념 존재 (Lock을 걸면 해당 프로세스만 해제 가능)	소유권 없음 (다른 프로세스가 해제 가능)

 

---

출처

• https://blog.seongjun.kr/26-difference-between-binary-semaphore-and-mutex/
• https://velog.io/@dodozee/%EB%AE%A4%ED%85%8D%EC%8A%A4Mutex%EC%99%80-%EC%84%B8%EB%A7%88%ED%8F%AC%EC%96%B4Semaphore
• https://gyoogle.dev/blog/computer-science/operating-system/Semaphore%20&%20Mutex.html
• https://yoongrammer.tistory.com/61
• 기술 면접 대비 CS 핵심요약