프로세스 동기화와 교착상태

1. 경쟁상태와 임계구역

여러 실행 흐름이 공유 데이터를 동시에 읽고 수정할 때 실행 순서에 따라 결과가 달라지는 상황을 경쟁상태라고 한다. 공유 데이터를 변경하는 코드 구간이 임계구역이다.

올바른 임계구역 해결은 다음 조건을 만족해야 한다.

• 상호배제: 한 번에 하나만 임계구역 실행
• 진행: 임계구역이 비었다면 진입할 프로세스 선택이 무기한 지연되지 않음
• 한정 대기: 특정 프로세스가 무한히 기다리지 않음

2. 뮤텍스와 세마포어

뮤텍스

하나의 잠금 소유자가 임계구역에 진입하고 해제한다. 소유권 개념이 있으며 일반적으로 잠근 실행 흐름이 해제한다.

세마포어

정수 값과 원자적 연산으로 자원 수 또는 실행 순서를 제어한다.

• wait(P): 값이 가능하면 감소하고 진입, 아니면 대기
• signal(V): 값을 증가시키고 대기 중인 흐름을 깨울 수 있음
• 이진 세마포어: 0과 1
• 계수 세마포어: 여러 동일 자원 개수 관리

모니터

공유 데이터와 연산을 하나의 추상화 안에 묶고 한 번에 하나의 실행 흐름만 내부 코드를 실행하도록 언어·런타임이 지원한다. 조건변수로 특정 조건을 기다리고 알릴 수 있다.

3. 고전 동기화 문제

• 생산자-소비자: 버퍼의 공백·데이터 수와 상호배제를 함께 제어
• 독자-저자: 여러 읽기는 허용하되 쓰기는 배타적으로 수행
• 식사하는 철학자: 자원 획득 순서에 따라 교착상태 발생 가능

4. 교착상태

프로세스들이 서로가 가진 자원을 기다리며 더 이상 진행하지 못하는 상태이다. 다음 네 조건이 동시에 성립할 때 발생할 수 있다.

1. 상호배제
2. 점유와 대기
3. 비선점
4. 순환대기

5. 처리 방법

• 예방: 네 조건 중 하나를 구조적으로 깨뜨린다.
• 회피: 자원 요청 때 시스템이 안전상태를 유지하는지 확인한다. 은행원 알고리즘이 대표적이다.
• 탐지: 교착상태를 허용한 뒤 대기 그래프·자원 상태로 찾는다.
• 복구: 프로세스 종료, 자원 선점, 롤백 등을 수행한다.
• 무시: 발생 가능성이 낮고 처리 비용이 큰 경우 별도 알고리즘을 두지 않는다.

안전상태는 모든 프로세스가 완료할 수 있는 안전 순서가 존재하는 상태이다. 불안전 상태가 반드시 교착상태는 아니지만 교착상태로 진행할 가능성이 있다.

6. 교착상태·기아·라이브락

• 교착상태: 서로 기다리며 진행하지 못함
• 기아: 특정 실행 흐름이 계속 선택되지 못함
• 라이브락: 상태는 계속 바뀌지만 유효한 작업이 진행되지 않음

7. 원자성 상실을 실행 순서로 추적하기

공유 변수 count=5에 두 스레드가 각각 count++를 한 번 수행한다고 하자. count++는 기계 수준에서 읽기·증가·쓰기로 나뉠 수 있다.

T1: r1 ← count   # 5
T2: r2 ← count   # 5
T1: r1 ← r1+1    # 6
T2: r2 ← r2+1    # 6
T1: count ← r1   # 6
T2: count ← r2   # 6

정상 기대값 7이 아니라 6이 되는 lost update이다. 소스 한 줄이라는 이유만으로 원자적이라고 판단하면 안 된다.

8. 생산자-소비자 세마포어 의사코드

크기 N인 유한 버퍼에서는 자원 개수와 임계구역 보호를 분리한다.

semaphore empty = N
semaphore full  = 0
semaphore mutex = 1

producer:
  wait(empty)
  wait(mutex)
  put(item)
  signal(mutex)
  signal(full)

consumer:
  wait(full)
  wait(mutex)
  item = get()
  signal(mutex)
  signal(empty)

wait(mutex)를 먼저 실행한 뒤 wait(empty)에서 잠들면, 버퍼가 가득 찬 상황에서 소비자가 mutex를 얻지 못해 교착상태가 될 수 있다. 대기 순서까지 분석해야 한다.

9. 조건변수와 while 재검사

조건변수의 wait는 모니터 락을 원자적으로 놓고 잠든다. 깨어난 뒤에는 다른 스레드가 먼저 상태를 바꿨거나 허위 깨움이 있을 수 있으므로 보통 if가 아니라 while로 조건을 재검사한다.

with condition:
    while not queue:
        condition.wait()
    item = queue.pop(0)

조건변수는 상태 자체를 저장하는 세마포어 카운터와 동일하지 않다. 조건을 나타내는 실제 공유 상태가 별도로 필요하다.

10. 자원할당 그래프와 대기 그래프

자원 유형마다 인스턴스가 하나라면 자원할당 그래프의 사이클은 교착상태와 동치다. 여러 인스턴스가 있다면 사이클은 교착상태 가능성을 뜻할 뿐 충분조건은 아니다.

P1 → R2 → P2 → R1 → P1
요청  할당  요청  할당

단일 인스턴스에서는 위 사이클이 곧 교착상태다. 대기 그래프는 자원 노드를 제거하고 “P1이 P2가 가진 자원을 기다림”을 P1→P2로 표현한다.

11. 은행원 알고리즘 안전성 검사

각 프로세스의 Need = Max - Allocation을 계산한 뒤, 현재 Available 이하의 Need를 가진 프로세스를 완료시켜 할당 자원을 반납한다고 가정한다.

Available = 2
          Allocation  Max  Need
P1             1       3     2
P2             2       3     1
P3             1       4     3

P2 완료 후 Available=4, 이어 P1과 P3도 완료할 수 있으므로 안전 순서 예시는 P2→P1→P3이다. 안전 순서는 하나가 아닐 수 있다.

12. 교착상태 예방 설계 예

• 모든 락을 전역 순서대로 획득: 순환대기 제거
• 필요한 자원을 한꺼번에 요청: 점유와 대기 제거, 이용률 저하 가능
• 선점 가능한 자원은 필요 시 회수: 비선점 조건 완화
• 읽기 전용 공유 자원: 상호배제 불필요

실무적으로는 짧은 임계구역, 일관된 락 순서, 타임아웃, 락 계층 문서화가 중요하다.

13. 공정성과 진행성

스핀락은 대기 중 CPU를 소비하지만 락 보유 시간이 매우 짧고 수면·깨움 비용이 더 큰 다중 코어 상황에서 유리할 수 있다. 뮤텍스는 오래 기다릴 가능성이 있을 때 스레드를 재우는 구현이 일반적이다. 어떤 락이든 공정성이 보장되지 않으면 기아가 생길 수 있다.

최종 확인 문제

1. count++를 두 스레드가 한 번씩 수행해도 결과가 1만 증가할 수 있는 이유를 읽기·수정·쓰기 순서로 설명하시오.
2. 크기 5 생산자-소비자 버퍼의 초기 세마포어 empty, full, mutex 값을 쓰시오.
3. 조건변수 대기를 if보다 while로 감싸는 이유를 설명하시오.
4. 자원 유형마다 인스턴스가 하나일 때 자원할당 그래프에 사이클이 존재하면 무엇을 뜻하는가?
5. Available=1, P1의 Need=2, P2의 Need=1이며 P2의 Allocation=2일 때 먼저 완료 가능한 프로세스와 완료 후 Available을 구하시오.