[CS] 상호 배제

상호 배제 (Mutual Exclusion)

상호 배제는 공유 불가능한 자원의 동시 사용을 피하기 위해 사용되는 알고리즘입니다.

이는 임계 구역으로 불리는 코드 영역에 의해 구현되며, 하나의 프로세스가 공유 자원을 사용할 때 다른 프로세스의 접근을 막을 수 있도록 합니다.

 

상호 배제는 멀티 프로세스나 멀티 스레드의 동기화에 사용됩니다.

또한, 이는 교착 상태의 4가지 필요 조건 중 하나로서 교착 상태와 기아 상태가 발생할 수 있습니다.

• 교착 상태 (Deadlock) : 무한 대기
• 기아 상태 (Starvation) : 우선순위가 낮아 자원을 계속 할당받지 못하는 상태

 

임계 구역 (Critical Section)

임계 구역은 공유 자원에 접근하는 프로세스 내부의 코드 영역입니다.

어떤 프로세스가 이 영역을 수행 중일 때 다른 프로세스가 같은 영역을 수행한다면 문제가 발생할 수 있습니다.

따라서, 임계 구역은 한번에 하나의 프로세스만 이용하게끔 보장해야 합니다.

 

임계 구역의 문제를 해결하기 위해서는 아래 3가지 조건을 충족해야 합니다.

• 상호 배제 : 하나의 프로세스가 임계 구역에 들어가 있다면 다른 프로세스는 들어갈 수 없어야 합니다.
• 진행 : 임계 구역에 들어간 프로세스가 없는 상태에서 들어가려 하는 프로세스가 여러 개라면 어느 것이 들어갈지 결정해주어야 합니다.
• 한정 대기 : 다른 프로세스의 기아 상태를 방지하기 위해서, 한 번 임계 구역에 들어간 프로세스는 다음에 임계 구역에 들어갈 때 제한을 두어야 합니다.

이러한 임계 구역의 동시 접근을 해결하기 위한 방법으로 뮤텍스, 세마포어, 모니터 등이 있습니다.

 

뮤텍스 (Mutex)

• 다른 프로세스 간 동기화에 사용됩니다.
• 공유된 자원의 데이터를 여러 스레드가 접근하는 것을 막습니다.
• 임계 구역을 가진 스레드의 Running Time이 서로 겹치지 않게 단독적으로 실행되게 합니다.
  • 임계 구역에는 하나의 스레드만 접근 가능합니다.
  • 상태가 0 또는 1로, 이진 세마포어라고 부르기도 합니다.
• 다중 프로세스들의 공유 리소스에 대한 접근을 조율하기 위해 Locking과 Unlocking을 사용합니다.
  • 한 스레드가 임계 구역에 들어갈 때는 lock을 하고, 나올 때는 unlock을 합니다.
  • 키는 단 하나이므로 키를 소유한 스레드를 제외한 다른 스레드는 임계 구역 안 스레드의 작업에 간섭할 수 없습니다.

 

뮤텍스 알고리즘

1. 데커(Dekker) 알고리즘 

데커 알고리즘은 flag와 turn 변수를 통해 임계 구역에 들어갈 프로세스/스레드를 결정하는 알고리즘입니다.

• flag : 프로세스 중 누가 임계 구역에 진입할 것인지 나타내는 변수
• 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. 피터슨(Peterson) 알고리즘

피터슨 알고리즘은 데커 알고리즘과 유사하지만, 다른 프로세스/스레드에게 진입 기회를 양보하는 것에 차이가 있습니다.

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

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

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

 

3. 제과점(Bakery) 알고리즘

제과점 알고리즘은 여러 프로세스/스레드에 대한 처리가 가능한 알고리즘입니다.

가장 작은 수의 번호표를 가지고 있는 프로세스가 임계 구역에 진입하게 됩니다.

while (true) {
    isReady[i] = true; // 번호표 받을 준비
    number[i] = max(number[0], ... , number[n-1]) + 1; // 현재 실행 중인 프로세스 중에 가장 큰 번호 배정 
    isReady[i] = false; // 번호표 수령 완료
    
    for (j = 0; j < n; j++) { // 모든 프로세스 번호표 비교
        while (isReady[j]); // 비교 프로세스가 번호표 받을 때까지 대기
        while (number[j] && number[j] < number[i] && j < i);
        
        // 프로세스 j가 번호표 가지고 있어야 함
        // 프로세스 j의 번호표 < 프로세스 i의 번호표
    }
}

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

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

 

세마포어 (Semaphore)

• 뮤텍스가 임계 구역에 들어가는 스레드가 하나라면, 세마포어는 복수 개가 가능합니다.
• 공유 자원에 대해 동시에 접근할 수 있는 프로세스/스레드의 수를 변수로 제한합니다.
• 이는 운영체제나 커널에 실제로 저장되며, 각 프로세스는 이 값을 확인하고 변경할 수 있습니다.
• 뮤텍스와 마찬가지로 다른 프로세스 간 동기화에 사용됩니다.
• 세마포어는 wait과 signal을 통해 구현됩니다.
  • wait이 먼저 호출되어 임계 구역에 들어갈 수 있는지와 먼저 실행되어야 하는 프로세스가 실행되는지 확인합니다.
  • 조건에 만족하면 wait을 빠져나와 임계 구역으로 들어갑니다.
  • 이후 signal이 호출되어 임계 구역에서 빠져나왔음을 알립니다.

 

뮤텍스 vs 세마포어

뮤텍스와 세마포어는 흔히 "방과 열쇠"로 비유되곤 합니다. ​

 

사용자(프로세스)가 방(자원)에 들어가려 할 때,

뮤텍스는 방에 들어가기 위한 열쇠이고 세마포어는 빈 방의 열쇠의 개수입니다.

 

뮤텍스는 방이 하나 뿐인 집입니다.

한 사람이 빈 방에 대한 열쇠를 가지고 있어서 (제어권 획득)

방에 이미 들어갔다면 (Lock 설정)

그 사람이 나오기 전까지는 아무도 방에 들어갈 수 없습니다. (다른 프로세스/스레드는 대기)

그러다 방에 있던 사람이 나오면 (Lock 해제 = Unlock)

다른 사람이 열쇠를 건네받아 방에 들어갈 수 있게 됩니다. (대기 중이던 프로세스/스레드가 제어권 획득)

 

세마포어는 방이 여러 개 있는 집​입니다.

만약 방이 5개라면, 방에 들어가기 위한 열쇠도 5개입니다. (세마포어 값 = 5)

사람 한 명이 방에 들어갈 때마다 사용 가능한 방과 열쇠가 하나씩 줄어들고, 나오면 늘어납니다.

만약 5개의 방이 전부 사용 중이라면 (세마포어 값 = 0)

방에 들어간 사람이 나올 때 까지 기다려야 합니다. (wait)

그러다 방에 있던 사람이 나오면 (signal)

해당 방을 사용할 수 있게 됩니다. (대기 중이던 프로세스/스레드가 제어권 획득)

 

모니터 (Monitor)

• 하나의 프로세스 내의 다른 스레드 간 동기화에 사용됩니다.
• 모니터는 프레임워크나 라이브러리 그 자체에서 제공됩니다.
• 일련의 동기화 작업들이 캡슐화되어 있기 때문에 synchronized, wait(), notify() 등의 키워드를 통해 편하게 동기화할 수 있습니다.
• 즉, 모니터는 세마포어와는 달리 wait, signal 설정 없이 함수 앞에 synchronized를 붙여주기만 하면 상호 배제하여 작업을 수행할 수 있습니다.