세마포어(Semaphore) & 뮤텍스(Mutex)

세마포어 (Semaphore)

공유된 자원에 여러 프로세스가 동시에 접근하면서 문제가 발생할 수 있다. 이때 공유된 자원의 데이터는 한 번에 하나의 프로세스만 접근할 수 있도록 제한을 둬야하는데, 이를 위해 나온 것이 바로 '세마포어'이다.

 

세마포어(Semaphore)는 운영체제에서 멀티프로그래밍 환경의 여러 프로세스나 스레드가 공유 자원에 동시에 접근하는 것을 제어하는 동기화(Synchronization) 기법이다. 자원에 접근할 수 있는 허용된 개수(정수 변수)를 설정하여 경쟁 상태(Race Condition)를 방지한다.

 

작동 원리

세마포어는 크게 두 가지 원자적 연산(중간에 다른 연산이 끼어들거나 중단되지 않고 '한 번에' 수행되는 쪼갤 수 없는 연산)으로 제어된다.

 

P 연산 (Wait / wait())

자원을 사용하기 위해 세마포어 값을 확인하고 1 감소시키는 연산이다. (값이 0보다 크면 자원을 할당하고, 0이면 자원이 생길 때까지 대기한다.)

V 연산 (Signal / signal())

자원 사용을 마치고 세마포어 값을 1 증가시켜 대기 중인 다른 프로세스에게 자원이 생겼음을 알리는 연산이다.

 

세마포어의 분류

가질 수 있는 값의 범위에 따라 두 가지로 나뉜다.

1. 이진 세마포어 (Binary Semaphore)

• 값이 0과 1만 가질 수 있는 세마포어이다.
• 1개의 자원만 제어할 수 있으며, 뮤텍스(Mutex)와 유사하게 작동한다.

2. 계수 세마포어 (Counting Semaphore)

• 0 이상의 제한 없는 정수 값을 가지는 세마포어이다.
• 제한된 개수(N개)만큼 동시에 자원에 접근하는 것을 허용할 때 사용한다.

뮤텍스 (Mutex)

임계 구역을 가진 스레드들의 실행시간이 서로 겹치지 않고 각각 단독으로 실행되게 하는 기술

 

해당 접근을 조율하기 위해 lock과 unlock을 사용한다.

• lock : 현재 임계 구역에 들어갈 권한을 얻어옴 ( 만약 다른 프로세스/스레드가 임계 구역 수행 중이면 종료할 때까지 대기 )
• unlock : 현재 임계 구역을 모두 사용했음을 알림. ( 대기 중인 다른 프로세스/스레드가 임계 구역에 진입할 수 있음 )

뮤텍스 전체 흐름

시간 →

Thread A
lock()
  │
  ├── Critical Section ──┐
  │                       │
unlock()                  │
                          │
Thread B                  │
lock() ── 대기 ───────────┘
             │
             ▼
         wakeup
             │
             ▼
          lock()
             │
             ▼
      Critical Section
             │
             ▼
          unlock()

 

Thread A가 lock을 획득하고 A는 임계 구역에 진입한다.

Thread B도 진입 시도하지만 A가 아직 작업 중이면 B는 Blocked 상태가 되고

A가 작업이 완료되면 운영체제가 B를 깨운다.

B가 lock을 획득하고 임계 구역에 진입한다.

 

뮤텍스 알고리즘

1. 데커 알고리즘

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로 바꿔 임계 구역 사용 완료를 알림

데커 알고리즘은 flag 조정, turn 조정, 반복문이 많아 구현이 복잡하다. 그래서 더 단순한 방법이 등장한다.

2. 피터슨 알고리즘

데커 알고리즘을 단순화한 버전이다. 상대방 프로세스/스레드에게 진입 기회를 양보하는 것에 차이가 있다.

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

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

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

둘 다 들어가고 싶다면 마지막으로 양보한 사람이 기다린다.

장점은 구현이 단순하지만 단점은 프로세스 2개만 가능하다는 것이다.

 

그래서 N개 프로세스로 확장한 알고리즘이 나온다.

3. 제과점 알고리즘

여러 프로세스/스레드에 대한 처리가 가능한 알고리즘이다. 가장 작은 수의 번호표를 가지고 있는 프로세스가 임계 구역에 진입한다.

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] && j < i);
        
        // 프로세스 j가 번호표 가지고 있어야 함
        // 프로세스 j의 번호표 < 프로세스 i의 번호표
    }
}

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

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

프로세스 개수 제한이 없지만 번호 비교 비용이 크다.

 

이 세 알고리즘 모두 while문의 Busy Waiting(Spin)을 사용한다.

즉, 계속 확인하면서 CPU를 소비한다.

현대 CPU는 멀티코어, 캐시, 메모리 재정렬 등이 있기 때문에 이 알고리즘을 그대로 적용하기 어렵다.

그래서 실제 운영체제는 

• Test-and-Set
• Compare-and-Swap(CAS)
• Mutex
• Semaphore
• Spinlock

같은 하드웨어 지원 동기화 기법을 사용한다.

 

참고 자료

https://gyoogle.dev/blog/computer-science/operating-system/Semaphore%20&%20Mutex.html

세마포어(Semaphore) & 뮤텍스(Mutex) | 👨🏻‍💻 Tech Interview

& Chatgpt