동기화와 교착상태

동기화는 공유 자원의 접근 순서를 조정한다. 임계 구역의 세 조건, 세마포어와 뮤텍스의 역할, 교착상태의 네 필요조건과 대응 전략을 구분하고 기본 자원 할당 표로 안전 상태를 판단한다.

그림으로 확인하기

좌우로 이동해 그림을 확인하세요.그림 크게 보기

공유 상태는 명령 단위가 아니라 실제 연산 단계로 추적한다

둘 이상의 실행 흐름이 같은 데이터를 읽거나 바꾸면 결과는 인터리빙(interleaving), 즉 연산 단계가 섞이는 순서에 따라 달라질 수 있다. 예를 들어 공유 변수 count가 10이고 두 스레드가 각각 count = count + 1을 한 번 실행한다고 하자.

count = count + 1은 개념적으로 다음 단계로 나눌 수 있다.

1. 메모리에서 현재 값을 읽는다.
2. 읽은 값에 1을 더한다.
3. 계산 결과를 메모리에 쓴다.

다음과 같이 섞이면 증가 연산을 두 번 수행했는데도 결과는 11이 된다.

두 스레드가 모두 같은 옛값을 읽은 뒤 각각 11을 기록하여 한 번의 갱신이 사라졌다. 이를 갱신 분실(lost update)이라고 한다. 소스 코드의 문장이 짧다는 사실은 실행의 원자성을 보장하지 않는다.

임계 구역 문제

임계 구역의 구조

임계 구역(critical section)은 공유 데이터나 공유 자원의 일관성을 깨뜨릴 수 있어 동시에 둘 이상의 실행 흐름이 수행하면 안 되는 코드 구역이다. 고전적인 프로세스 구조는 다음과 같이 나눈다.

repeat forever:
    진입 구역        // 임계 구역에 들어갈 권한을 얻음
    임계 구역        // 공유 상태를 읽거나 변경
    퇴출 구역        // 권한을 반환하고 대기자를 깨울 수 있음
    나머지 구역      // 공유 상태 보호가 필요하지 않은 작업

임계 구역을 크게 잡으면 안전성은 얻기 쉽지만 동시성이 줄고 대기 시간이 길어진다. 너무 작게 잡으면 서로 묶여야 할 확인과 갱신이 분리되어 경쟁 상태가 남는다. 핵심은 공유 불변식을 유지하는 최소한의 논리 단위를 보호하는 것이다.

임계 구역 해법의 세 조건

상호 배제(mutual exclusion)

한 실행 흐름이 임계 구역에 있으면 다른 실행 흐름은 같은 임계 구역에 들어갈 수 없어야 한다. 이는 잘못된 동시 접근을 막는 안전성 조건이다.

진행(progress)

임계 구역 안에 아무도 없고 진입을 원하는 실행 흐름이 있다면, 임계 구역 밖에서 다른 작업을 하는 실행 흐름 때문에 진입 결정이 무기한 미뤄져서는 안 된다. 단순히 번갈아 들어가도록 강제하는 엄격한 교대는 상대가 진입 의사가 없어도 자신의 차례가 아니면 기다리므로 진행 조건을 위반할 수 있다.

한정 대기(bounded waiting)

어떤 실행 흐름이 진입을 요청한 뒤 다른 실행 흐름이 먼저 들어갈 수 있는 횟수에 유한한 상한이 있어야 한다. 이 조건이 없으면 상호 배제와 전체 진행은 성립해도 특정 실행 흐름이 영원히 선택되지 않는 기아가 발생할 수 있다.

뮤텍스·세마포어·모니터

뮤텍스

뮤텍스(mutex)는 mutual exclusion에서 이름이 온 잠금 객체다. 일반적인 사용 흐름은 다음과 같다.

1. 임계 구역에 들어가기 전에 잠금을 획득한다.
2. 이미 다른 실행 흐름이 소유했다면 대기한다.
3. 공유 상태를 확인하고 변경한다.
4. 예외·조기 반환이 있어도 반드시 잠금을 해제한다.

lock(mutex)
try:
    공유 상태 확인과 변경
finally:
    unlock(mutex)

소유권이 있는 뮤텍스는 잠근 실행 흐름이 해제해야 한다. 다른 실행 흐름이 해제하면 오류이거나 정의되지 않은 동작이 될 수 있다. 재귀 뮤텍스는 같은 소유자가 여러 번 잠글 수 있지만 잠근 횟수만큼 해제해야 하며, 일반 뮤텍스가 자동으로 재귀적인 것은 아니다.

잠금을 얻은 채로 네트워크 응답, 사용자 입력, 긴 디스크 작업을 기다리면 다른 실행 흐름의 대기가 크게 늘어난다. 공유 상태를 보호하는 작업과 느린 외부 작업을 분리하는 것이 좋다.

세마포어의 P·V 연산

세마포어(semaphore)는 정수 카운터와 대기열을 이용하는 동기화 도구다. 전통적으로 다음 이름을 사용한다.

• P, wait, down, acquire: 허가 하나를 얻는다.
• V, signal, up, post, release: 허가 하나를 반환하거나 사건을 알린다.

개념적 동작은 다음과 같다. 값 검사와 변경은 원자적으로 이루어져야 한다.

wait(S):
    S에 사용 가능한 허가가 있으면 하나 감소하고 계속한다.
    없으면 대기열에서 잠든다.

signal(S):
    허가를 하나 추가한다.
    대기자가 있으면 정책에 따라 하나를 깨울 수 있다.

교재에 따라 대기자 수를 음수로 표현하는 내부 모델도 있지만, “사용 가능한 허가 수”라는 외부 의미는 0 이상으로 이해하면 된다. 내부 구현 표현과 추상적 의미를 섞지 않는다.

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

• 이진 세마포어(binary semaphore)는 사용 가능한 허가 수가 0 또는 1인 형태다.
• 카운팅 세마포어(counting semaphore)는 0 이상의 여러 허가를 표현하여 동일 자원 N개의 동시 사용량을 제한한다.

예를 들어 데이터베이스 연결을 동시에 3개까지만 사용하게 하려면 초기값 3인 카운팅 세마포어를 둘 수 있다. 사용자는 진입 전에 wait, 연결 반환 후 signal을 수행한다.

뮤텍스와 이진 세마포어는 같은가

값 범위만 보면 둘 다 0과 1일 수 있지만 의미와 올바른 사용법은 다르다. “상호 배제 잠금” 의도를 표현할 때는 보통 뮤텍스가 더 명확하다.

모니터

모니터(monitor)는 공유 데이터, 그 데이터를 조작하는 절차, 상호 배제 규칙과 조건 변수를 하나의 고수준 모듈로 묶은 구조다. 일반적으로 한 시점에 하나의 실행 흐름만 모니터의 활성 절차를 수행한다.

• 뮤텍스는 잠금 객체 자체다.
• 모니터는 공유 상태와 허용된 연산을 캡슐화한다.
• 조건 변수는 모니터 안에서 특정 상태 조건을 기다리는 데 사용한다.

언어와 런타임에 따라 통지한 실행 흐름이 계속 실행하는지, 깨운 실행 흐름에게 즉시 제어를 넘기는지의 세부 의미가 다를 수 있다. 따라서 시험의 일반 개념과 특정 언어 구현 규칙을 구분한다.

유한 버퍼 생산자-소비자 문제

크기가 N인 원형 버퍼를 여러 생산자와 소비자가 공유한다고 하자.

• empty = N: 비어 있는 칸 수
• full = 0: 채워진 칸 수
• mutex = 1: 버퍼 인덱스와 내용의 상호 배제

생산자:
    wait(empty)
    wait(mutex)
    버퍼에 항목 삽입
    signal(mutex)
    signal(full)

소비자:
    wait(full)
    wait(mutex)
    버퍼에서 항목 제거
    signal(mutex)
    signal(empty)

empty와 full은 자원 수와 작업 순서를 나타내고, mutex는 버퍼 조작의 상호 배제를 담당한다. 세 역할을 하나의 세마포어로 합치면 의미가 불명확해진다.

획득 순서도 중요하다. 생산자가 먼저 mutex를 얻은 뒤 empty를 기다리도록 바꾸면, 버퍼가 가득 찬 상태에서 생산자가 뮤텍스를 가진 채 잠들 수 있다. 소비자는 항목을 제거하려 해도 뮤텍스를 얻지 못하므로 모두 멈출 수 있다. 일반적으로 자원 존재 조건을 먼저 기다리고 실제 버퍼 임계 구역은 그다음 짧게 보호한다.

고전적인 동기화 문제의 초점

독자-작성자 문제는 읽기만 하는 작업끼리는 동시에 접근할 수 있지만 쓰는 동안에는 충돌하는 읽기·쓰기를 제한해야 한다는 문제이다. 특정 집단을 계속 우선하면 다른 집단에 기아가 생길 수 있다.

식사하는 철학자 문제는 각 작업이 여러 자원 중 일부만 확보한 채 나머지를 기다릴 때 생기는 교착상태를 설명한다. 자원 획득 순서를 통일하거나 동시에 시도할 작업 수를 제한하는 등의 방식으로 교착 조건을 끊을 수 있다.

교착상태의 개념과 네 필요조건

교착상태

교착상태는 집합 안의 각 프로세스나 스레드가 다른 구성원이 일으켜야 하는 사건 또는 반환해야 하는 자원을 기다려 집합 전체가 영구적으로 진행하지 못하는 상태다.

예를 들어 다음 순서가 발생하면 교착상태가 된다.

1. 스레드 A가 자원 X를 획득한다.
2. 스레드 B가 자원 Y를 획득한다.
3. A가 Y를 요청하고 기다린다.
4. B가 X를 요청하고 기다린다.
5. A와 B 모두 상대가 먼저 해제해야만 진행할 수 있다.

Coffman의 네 필요조건

네 조건은 모두 동시에 성립해야 교착상태가 가능하다. 그러나 시스템에서 네 조건이 성립할 수 있다는 사실만으로 특정 순간에 이미 교착상태라고 확정할 수는 없다. 예방은 이 조건 중 하나가 구조적으로 성립하지 않도록 만든다.

자원 종류와 인스턴스

자원 유형(resource type)은 프린터, 데이터베이스 연결, 잠금처럼 같은 종류를 묶은 개념이고, 인스턴스(instance)는 실제 개별 자원 수다.

• 프린터 유형에 장치가 1대이면 단일 인스턴스다.
• 연결 풀에 연결이 5개면 하나의 자원 유형에 인스턴스가 5개다.

자원 할당 그래프에서 순환의 의미는 자원 유형마다 인스턴스가 하나인지 여러 개인지에 따라 달라진다.

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

자원 할당 그래프

자원 할당 그래프(resource-allocation graph)는 프로세스와 자원의 관계를 방향 그래프로 표현한다.

• 프로세스 노드: 보통 원으로 표현
• 자원 유형 노드: 보통 사각형으로 표현
• 요청 간선 P → R: 프로세스 P가 자원 R을 기다림
• 할당 간선 R → P: 자원 R의 인스턴스가 프로세스 P에 할당됨

단일 인스턴스 자원만 있을 때는 그래프에 순환이 있으면 교착상태이고, 교착상태이면 순환이 있다. 즉 순환이 필요충분조건이다.

한 자원 유형에 인스턴스가 여러 개면 순환은 교착상태의 필요조건일 수 있지만 충분조건은 아니다. 순환에 포함되지 않은 여분 인스턴스가 어떤 프로세스를 완료시키고 자원을 반환하게 할 수 있기 때문이다.

대기 그래프

대기 그래프(wait-for graph)는 단일 인스턴스 자원 시스템에서 자원 노드를 제거하고 프로세스 사이의 대기 관계만 남긴다.

• Pi → Pj: Pi가 Pj가 가진 자원을 기다린다.
• 순환이 있으면 관련 프로세스가 교착상태다.

대기 그래프는 단일 인스턴스 자원에서 탐지에 유용하다. 다중 인스턴스 시스템은 단순한 프로세스 순환만으로 충분하지 않아 별도의 행렬 기반 탐지 알고리즘이 필요하다.

교착상태와 기아의 차이

교착상태에서는 서로가 가진 자원을 기다리는 작업 집합이 진행하지 못한다. 기아는 다른 작업이 계속 선택되어 특정 작업이 자원을 오래 얻지 못하는 상태이다. 기아가 있다고 반드시 자원 대기의 순환이 있는 것은 아니다. 우선순위에 따라 기다리는 시간이 길어질 때 에이징으로 우선순위를 높이는 방법은 기아 완화의 예이다.

같은 동작을 계속 반복하더라도 유효한 진전이 없다면 활성 교착(livelock)일 수 있다. 따라서 CPU를 사용하고 있다는 사실만으로 업무가 진전된다고 판단하지 않는다.

교착상태 대응 전략

전략 비교

운영체제가 모든 종류의 교착상태를 하나의 기법으로 해결하는 것은 아니다. 데이터베이스, 운영체제 커널, 응용 프로그램은 자원 특성과 복구 가능성에 따라 다른 전략을 선택한다.

예방: 네 조건 중 하나 끊기

실무에서 여러 잠금에 전역 순서를 부여하는 방식은 순환 대기를 직접 제거하므로 널리 사용된다. 예를 들어 모든 코드가 X를 먼저, Y를 나중에 획득한다면 X와 Y 사이의 반대 방향 순환은 만들어질 수 없다.

회피: 안전 상태 유지

회피는 네 조건을 허용하되, 각 요청을 승인한 이후에도 모든 프로세스가 어떤 순서로는 완료할 수 있는지 확인한다. 이를 위해 프로세스의 최대 자원 요구량을 미리 알아야 한다.

• 안전 상태: 모든 프로세스가 완료할 수 있는 순서가 적어도 하나 존재한다.
• 안전 순서: 각 프로세스가 현재 가용 자원과 앞선 프로세스가 반환한 자원으로 남은 요구를 충족하고 완료할 수 있는 순서다.
• 불안전 상태: 안전 순서가 없으며 향후 요청에 따라 교착상태가 발생할 수 있다.
• 교착상태: 현재 상태에서 관련 프로세스가 실제로 서로 기다려 진행할 수 없다.

따라서 다음 포함 관계를 기억한다.

교착상태이면 불안전 상태다.
불안전 상태라고 해서 반드시 현재 교착상태인 것은 아니다.
안전 상태에서는 적절한 순서를 따르면 교착상태를 피할 수 있다.

은행원 알고리즘의 핵심

은행원 알고리즘은 자원을 임시 할당한 뒤 모든 프로세스가 끝날 수 있는 안전 순서가 남는지 확인하는 교착상태 회피 방법이다. Need = Max − Allocation이며, 남은 필요량을 현재 가용량으로 충족할 수 있는 프로세스부터 완료한다고 가정하고 할당 자원을 반환한다. 모든 프로세스를 완료시킬 순서를 찾으면 안전하다. 불안전 상태가 이미 교착상태라는 뜻은 아니다. 필기 기본 학습에서는 예방·회피·탐지·회복의 차이를 먼저 구분한다.

사용하는 자료 구조

프로세스가 n개이고 자원 유형이 m개라고 하자.

계산식은 다음과 같다.

Need = Max - Allocation
Available = Total - 각 프로세스 Allocation의 열별 합

Need는 현재 당장 요청한 양이 아니라, 선언된 최대 요구량에서 이미 받은 양을 뺀 남은 최대 가능 요구량이다.

탐지와 회복의 기본

탐지는 이미 자원을 할당한 상태에서 교착상태가 존재하는지 검사하는 것이다. 회복은 관련 프로세스를 종료하거나 자원을 회수하고, 필요한 경우 이전 상태로 되돌려 다시 실행하는 것이다. 모든 자원을 안전하게 강제 회수할 수 있는 것은 아니다.

은행원 알고리즘은 회피 기법으로, 최대 요구량을 알아야 한다. 현재 가용 자원이 요청량 이상이라는 사실만으로 승인하지 않고 가상으로 할당한 이후에도 안전 순서가 존재하는지 검사한다. 불안전 상태는 이미 교착상태라는 뜻이 아니라, 모든 작업의 완료를 보장하는 안전 순서를 확인하지 못한 상태이다.