Mutex & Semaphore

뮤텍스와 세마포어의 차이점은 무엇인가요?

동시성 프로그래밍의 가장 큰 숙제는 ‘공유자원 관리’이다. 공유 자원을 안전하게 관리하기 위해서는 상호 배제를 달성하는 기법이 필요하다.

뮤텍스와 세마포어는 이를 위해 고안된 기법으로 서로 다른 방식으로 상호배제를 달성한다.

Mutex

1. 정의: 뮤텍스는 하나의 스레드만이 특정 자원에 접근할 수 있도록 보장하는 동기화 기법이다.
2. 소유권: 뮤텍스는 소유권 개념이 있다. 즉, 뮤텍스를 소유한 스레드만이 뮤텍스를 해제할 수 있다.
3. 사용 사례: 단일 자원을 보호해야 하는 경우에 주로 사용된다.
   • 예를 들어, 하나의 스레드만이 특정 데이터 구조에 접근하고 수정할 수 있도록 할 때 사용된다.
4. 기본 동작: 뮤텍스는 잠금을 걸고, 잠금을 해제하는 방식으로 동작한다. 한 스레드가 뮤텍스를 잠그면, 다른 스레드는 그 뮤텍스가 해제될 때까지 대기해야 한다.

Semaphore

1. 정의: 세마포어는 정수 값을 가지는 동기화 기법으로, 특정 자원에 접근할 수 있는 스레드의 수를 제어한다.
2. 소유권: 세마포어에는 소유권 개념이 없다. 즉, 세마포어를 기다리는 스레드와 해제하는 스레드가 다를 수 있다.
3. 사용 사례: 여러 개의 스레드가 접근할 수 있는 자원의 수를 제한해야 할 때 사용된다.
   • 예를 들어, 제한된 수의 데이터베이스 연결을 관리할 때 사용된다.
4. 기본 동작: 세마포어는 스레드의 상태에 따라 값을 증가시키거나 감소시킬 수 있으며 값이 1이상일 때는 접근이 가능하고 값이 0일 때는 접근이 불가능하다.
5. 타입: 세마포어에는 두 가지 타입이 있다.
   • 카운팅 세마포어: 세마포어의 값이 0 이상일 수 있으며, 자원의 개수를 나타낸다.
   • 바이너리 세마포어: 값이 0 또는 1만을 가지며, 이 경우 뮤텍스와 유사하게 동작한다.

이진 세마포어와 뮤텍스의 차이에 대해 설명해 주세요.

Binary Semaphore

이진 세마포어는 두 가지 상태만 가진다. 가용과 사용 중이다. 이진 세마포어는 0 또는 1의 값을 가지고 있으며, 자원이 사용 중이면 다른 태스크가 그 자원을 사용할 수 없도록 제어한다.

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

특성	이진 세마포어	뮤텍스
주요 목적	태스크 간의 동기화	상호 배제를 통해 공유 자원 보호
소유권	소유권 없음	소유권이 있으며, 뮤텍스를 획득한 태스크만 해제 가능
우선순위 상속	지원하지 않음	우선순위 상속 지원
사용 예	이벤트 신호나 플래그로 사용	공유 자원 보호

Lock을 얻기 위해 대기하는 프로세스들은 Spin Lock 기법을 사용할 수 있습니다. 이 방법의 장단점은 무엇인가요? 단점을 해결할 방법은 없을까요?

스핀락
Race Condition 상황에서 Lock이 반환될 때까지, 즉 Critical Section에 진입 가능할 때까지 프로세스가 재시도하며 대기하는 상태

Race Condition

• 멀티 프로세스 환경에서 프로세스가 수행되는 순서에 따라 결과값이 달라질 수 있는 상황이다.
• 이런 경쟁 상태를 야기하는 상황을 임계 구역에 동시에 여러 스레드가 접근한 상황이라고 정리할 수 있다.

Critical Section

• 여러 스레드 또는 프로세스가 공유 자원에 접근할 수 있는 코드 영역이다.
• 즉 코드 상에서 경쟁 상태가 발생할 수 있는 곳으로 둘 이상의 스레드가 동시에 접근하면 안 되는 구역이다.

즉 경쟁 상태를 방지하고 데이터의 일관성을 유지하기 위해 동기화 과정이 필요한데, 여기서 사용되는 것이 Lock이다.

여기서 스핀락은 스레드가 락을 얻을 때까지 무한 루프를 돌며 확인하는 동기화 매커니즘이다. 이러한 스핀락은 운영체제 스케줄링의 지원을 받지 않기 때문에, 해당 스레드에 대한 context switching이 일어나지 않는다는 특징이 있다.

Spin Lock

• 장점
  • 문맥 교환이 일어나지 않아 문맥 교환에 필요한 CPU 오버헤드를 줄일 수 있다
  • 락의 획득이 빠르다 (무한 루프를 돌아서)
• 단점
  • Busy waiting: 스핀락의 획득을 위해 CPU의 오버헤드가 발생할 수 있다 (무한루프를 도는 과정)
  • Starvation: 특정 프로세스나 스레드가 공유 자원을 오랫동안 점유하면 다른 작업들이 대기 상태에 갇힐 수 있다.

⇒ 스핀락은 임계 구역에서 작업이 빠르게 이루어져 스레드나 프로세스의 경합 상황이 짧을 때 유리하다

⇒ 스핀락은 여러 개의 CPU 코어가 존재할 떄 유용하다.

⇒ 트레이드 오프를 고려하여 경합 상황이 길거나 싱글 CPU일 때는 다른 동기화 매커니즘인 뮤텍스와 세마포어를 고려하자.

단점을 해결할 방법

1. 하이브리드 락: 스핀 락과 블로킹 락의 장점을 결합한 하이브리드 락을 사용한다.
   • 스레드가 일정 시간 동안 스핀을 시도하고, 그 후에도 락을 얻지 못하면 블록 상태로 전환되는데, 이는 짧은 대기 시간에는 스핀 락의 이점을 활용하고, 긴 대기 시간에는 CPU 자원을 절약할 수 있게 된다.
2. 적응형 스핀 락: 락의 사용 패턴에 따라 스핀 시간의 길이를 동적으로 조정하는 방법이다.
   • 락이 짧은 시간 내에 해제될 가능성이 높을 경우, 스핀 시간을 길게 하고, 그렇지 않으면 스핀 시간을 줄인다.
3. 우선 순위 상속: 우선 순위 역전 문제를 해결하기 위해 우선 순위 상속 기법을 사용한다.
   • 락을 소유한 스레드가 높은 우선 순위의 스레드로부터 락을 요청받으면, 락을 해제할 때까지 우선 순위가 일시적으로 상속된다.
4. CPU 휴식 명령어 사용: 스핀 락 루프 내에서 PAUSE 명령어와 같은 CPU 휴식 명령어를 사용하여 CPU 자원의 낭비를 줄인다.

뮤텍스와 세마포어 모두 커널이 관리하기 때문에, Lock을 얻고 방출하는 과정에서 시스템 콜을 호출해야 합니다. 이 방법의 장단점이 있을까요? 단점을 해결할 수 있는 방법은 없을까요?

시스템 콜을 통한 락 관리의 장점

1. 안정성: 커널에서 관리되기 때문에, 동기화 메커니즘이 안정적이고 신뢰성이 있다.
2. 공정성: 커널은 세마포어 등의 기법을 통해 공정한 자원 분배를 보장할 수 있다.
3. 우선 순위 관리: 커널 수준에서 우선 순위 상속 기법같은 우선 순위 역전 문제를 해결하기 위한 기법들을 효과적으로 적용할 수 있다.
4. 프로세스 간 동기화: 커널은 프로세스 간 동기화를 지원하기 때문에, 같은 시스템 내의 여러 프로세스가 동일한 락을 사용할 수 있다.

시스템 콜을 통한 락 관리의 단점

1. 오버헤드: 시스템 콜은 사용자 모드에서 커널 모드로 전환이 반복되며, 이로 인해 상당한 오버헤드가 발생할 수 있다.
2. 컨텍스트 스위칭: 락을 얻기 위해 블록될 경우, 컨텍스트 스위칭이 발생하여 추가적인 성능 저하가 발생할 수 있다.
3. 복잡성: 커널 수준에서 동기화를 관리하기 때문에, 구현과 유지보수가 복잡할 수 있다.

단점을 해결할 수 있는 방법

• 스핀 락: 간단한 경우에는 스핀 락을 사용하여 사용자 모드에서 락을 관리할 수 있다. 이는 시스템 콜의 오버헤드를 피할 수 있지만, 스핀 락의 단점을 해결해야 한다.
• 배리어 락: 사용자 모드에서 구현된 배리어를 사용하여 특정 조건이 만족될 때까지 대기하는 방식으로, 시스템 콜의 빈도를 줄일 수 있습니다
• Futex(Fast Userspace Mutexes): 리눅스에서 제공하며 사용자 모드에서 빠르게 락을 획득하고 해제할 수 있도록 설계된 메커니즘이다.
  • Futex는 락이 경쟁상태가 없을 때는 사용자 모드에서 처리하고, 있을 때만 커널 모드로 전환하여 처리하는데, 이는 시스템 콜의 오버헤드를 크게 줄여준다.
• 락 분할(Lock Splitting): 락을 세분화하여 여러 락으로 나누어 경합을 줄인다.
  • 예를 들어, 데이터 구조의 각 부분에 대해 별도의 락을 사용하는 방식이 있다.
• 락 스트리핑(Lock Stripping): 해시 테이블 등의 구조에서, 각 버킷에 별도의 락을 적용하여 경합을 줄이는 방식이다.