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

세마포어 (Semaphore)

상호 배제(mutual exclusion)를 위한 동기화 기법 중 하나로, 공유 자원에 대한 접근을 제어하는 데 사용된다.

세마포어는 동시에 여러 개의 스레드나 프로세스가 접근할 수 있는 임계 영역(critical section)의 동시 접근을 제어하고 조절하는 역할을 한다.

Java에서는 'java.util.concurrent.Semaphore' 클래스를 사용하여 세마포어를 구현할 수 있다.

세마포어의 연산

세마포어는 일반적으로 정수형 변수로 표현되며, 세마포어 값은 0이상의 값을 가진다.

1. P (Proberen 또는 Wait Operation)

• 세마포어 값을 1감소시키고, 만약 값이 음수가 되면 해당 스레드나 프로세스를 대기 상태로 전환한다. 
• 이 연산은 세마포어에 대한 접근을 시도하는 스레드나 프로세스가 해당 자원을 얻을 때까지 기다리는 역할을 한다.

2. V (Verhogen 또는 Signal Operation)

• 세마포어 값을 1증가시키고, 만약 값이 0이하라면 대기 중인 스레드나 프로세스 중 하나를 깨워 실행 상태로 전환시킨다.
• 이 연산은 세마포어를 사용한 작업이 완료되어 해당 자원을 반환할 때 호출된다.

뮤텍스 (Mutex)

상호 배제(mutual exclusion)를 위한 동기화 기법 중 하나로, 공유 자원에 대한 접근을 제어하는 데 사용된다.

일반적으로 뮤텍스는 운영 체제나 프로그래밍 언어에서 제공되는 라이브러리 함수를 통해 사용된다. 예를 들어, Java에서는 'synchronized' 키워드를 사용하여 뮤텍스를 구현할 수 있다.

뮤텍스의 연산

뮤텍스 연산은 일반적으로 원자적(atomic)으로 수행되어야 한다. 이는 뮤텍스 연산이 간섭 없이 독립적으로 수행되도록 보장함을 의미한다. 원자적 연산은 다른 스레드나 프로세스의 동작에 영향을 주지 않고, 중간에 중단되거나 중간 상태로 남지 않도록 보잔된다.

1. Lock

• 뮤텍스를 획득하는 연산
• 뮤텍스를 획득한 스레드 또는 프로세스는 임계 영역에 진입할 수 있다.
• Lock 연산은 일반적으로 임계 영역 진입 전에 호출된다.
• 만약 뮤텍스가 이미 다른 스레드나 프로세스에 의해 획득되었다면, 호출한 스레드는 뮤텍스가 해제될 때까지 대기하게 된다.

2. Unlock

• 뮤텍스를 해제하는 연산
• Lock 연산에 의해 획득된 뮤텍스를 해당 스레드 또는 프로세스가 사용을 마친 후에 반드시 해제해야 한다.
• Unlock 연산은 임계 영역을 빠져나온 직후에 호출되어야 한다.
• 이후 다른 스레드나 프로세스가 뮤텍스를 획득할 수 있게 된다.

뮤텍스 알고리즘

1. Peterson's Algorithm

• 피터슨 알고리즘은 1061년에 고안된 뮤텍스 알고리즘으로, 두 개의 스레드 간의 상호 배제를 위해 사용된다.
• 동작 원리
  • 두 개의 스레드는 'turn'이라는 변수와 'flag' 배열을 공유한다. 'turn' 변수는 현재 상호 배제의 차례를 나타내고, 'flag' 배열은 스레드의 상태를 나타낸다.
  • 스레드는 자신의 상태를 'flag[threadId] = true' 로 설정하고, 'turn'이 자신의 차례가 될 때까지 대기한다.
  • 상대 스레드가 동작 중이면 'turn'이 상대의 차례일 것이고, 상대 스레드의 상태가 참('flag[1-threadId] == true')인 동안 대기한다.
  • 상대 스레드가 동작을 마치고 자신의 차례를 양보하면('turn != threadId') 상태를 'false'로 설정하고 상호 배제를 획득한다.
    
    

2. Dekker's Algorithm

• 데커 알고리즘은 피터슨 알고리즘보다 일반적인 형태로 1065년에 고안된 뮤텍스 알고리즘이다.
• 동작 원리
  • 두 개의 스레드는 turn이라는 변수와 flag 배열을 공유한다. turn 변수는 현재 상호 배제의 차례를 나타내고, flag 배열은 스레드의 상태를 나타낸다.
  • 스레드는 자신의 상태를 flag[threadId] = true 로 설정하고, 상대 스레드의 차례를 기다린다. 자신의 차례일 때까지 반복적으로 기다린다.
  • 자신의 차례가 되면, 상대 스레드의 차례를 기다리는 동안 대기하지 않고 상호 배제를 획득한다.
  • 상호 배제를 사용한 작업을 완료하면 자신의 상태를 flag[threadId] = false 로 설정하고, 상대 스레드에게 차례를 양보한다.
    
    

3. Bakery Algorithm

• 제과점 알고리즘은 피터슨과 데커 알고리즘보다 일반적인 형태로, 피터슨이 고안한 알고리즘이다.
• 제과점 알고리즘은 여러 개의 스레드 간의 상호 배제를 위해 사용된다.
• 동작 원리
  • 각 스레드는 번호를 가지고 있으며, 번호가 작은 스레드일수록 우선순위가 높다.
  • 모든 스레드는 상태를 나타내는 choosing 배열과 번호를 나타내는 number 배열을 가지고 있다.
  • 스레드는 번호를 선택하기 위해 가장 작은 번호를 찾아서 number 배열에 저장하고, choosing 배열을 설정하여 다른 스레드가 번호를 선택하는 동안 대기한다.
  • 번호 선택이 완료되면 choosing 배열을 false로 설정하고, 모든 다른 스레드의 번호와 우선순위를 비교하여 상호 배제를 얻는다.
  • 상호 배제를 사용한 작업을 완료하면 number 배열을 초기화하여 다른 스레드가 다시 번호를 선택할 수 있도록 한다.

 

뮤텍스와 세마포어의 차이점

• 세마포어는 공유 자원에 세마포어의 변수만큼의 프로세스 또는 스레드가 접근할 수 있다. 반면 뮤텍스는 오직 1개만의 프로세스 또는 스레드만 공유자원에 접근할 수 있다.
• 세마포어는 현재 수행중인 프로세스가 아닌 다른 프로세스가 세마포어를 해제할 수 있다. 뮤텍스는 락을 획득한 프로세스만이 그 락을 해제할 수 있다.

따라서 뮤텍스는 임계 영역에 들어갈 수 있는 스레드가 하나뿐인 경우에 적합하고, 여러 스레드가 동시에 접근할 수 있는 임계 영역을 관리할 때는 허용 가능한 접근 개수를 조절하여 동시성을 제어하고, 스레드 간의 작업을 조율하는 세마포어가 유용하다.