[ OS ] 07. 프로세스 동기화 - 임계영역문제의 해결책 ? Mutex, Semaphore !

앞서 총 두 가지의 임계영역 문제의 솔루션을 알아보았다.

1. SW 솔루션 : Peterson's Algorithm
2. HW 솔루션 : "test-and-set" , "compare-and-swap" 을 이용한 Atomic Variable HW instruction이다.

이제 조금 더 SW에서 고급 레벨의 솔루션을 알아 볼 것이다.

1. Mutex (Binary Semaphore) : 가장 간단한 동기화 툴 (locking : 열쇠)
2. Semaphore(Counting Semaphore) : 더욱 편리하고 효과적
3. Monitor : 뮤텍스와 세마포어의 단점을 극복 --> Java에서 생각하는 locking은 모두 Monitor이다.

Lock

• 하드웨어 기반 해결책으로써, 동시에 공유 자원에 접근하는 것을 막기 위해 Critical Section 에 진입하는 프로세스는 Lock 을 획득하고 Critical Section 을 빠져나올 때, Lock 을 방출함으로써 동시에 접근이 되지 않도록 한다.

한계

• 다중처리기 환경에서는 시간적인 효율성 측면에서 적용할 수 없다.

---

Semaphores

• 신호기!
• 소프트웨어상에서 Critical Section 문제를 해결하기 위한 동기화 도구

OS 는 Counting/Binary 세마포를 구분한다

- Binary Semaphore

MUTEX 라고도 부르며, 상호배제의 (Mutual Exclusion)의 머릿글자를 따서 만들어졌다. 이름 그대로 0 과 1 사이의 값만 가능하며, 다중 프로세스들 사이의 Critical Section 문제를 해결하기 위해 사용한다.

acquire()와 release()를 atomically하게 구현한다. 이는 운영체제 커널을 만드는 사람이 compare_and_swap()과 같은 기능을 이용해 만들것이다.

하지만 뮤텍스도 단점이 있는데 Busy Waiting이라는 문제가 생긴다.

Busy Waiting이란 어떤 임계영역에 들어가기 위해 무한루프에 들어가게 되는 것을 말한다. 멀티 프로그래밍에서는 이것이 단점이 된다. 다른 프로세스가 생산적으로 쓸 수 있는 CPU 자원을 CPU 싸이클을 통해 쓸데 없이 낭비하게 되기 때문이다.

- Counting Semaphore

wait()와 signal()을 atomically하게 구현한다.

가용한 개수를 가진 자원 에 대한 접근 제어용으로 사용되며, 세마포는 그 가용한 자원의 개수(count) 로 초기화 된다. 자원을 사용하면 세마포가 감소(wait() :: count--), 반납하면 세마포가 증가(signal() :: count++) 한다.

count가 0일 때는 모든 리소스가 사용하고 있기 때문에 누군가가 반납하기 전까지 자원을 사용하지 못한다.

### 세마포어의 busy waiting 문제를 해결하는 방법 ###

굳이 세마포어가 무한루프를 돌지 않고 wait()로 suspend 시켜서 waiting queue에 대기하고 있다가, 다른 프로세스가 signal()을 호
출하면 다시 ready queue에 들어가도록 하면 busy waiting 문제를 해결할 수 있다.

Counting Semaphore를 쓴다 하더라도 (ex. int sum = 987) 변수 하나만으로는 상호배제를 피할 수 없다. 왜냐하면 각각의 세마포어는 각각의 instance를 취급해야 하기 때문에 int sum[n]으로 할당하여 각각의 세마포어에게 서로 다른 instance를 할당하여야 한다.

# Mutex vs Semaphore
- 세마포어는 뮤텍스가 될 수 있지만 뮤텍스는 세마포어가 될 수 없다.
- 세마포어는 소유할 수 없는 반면, 뮤텍스는 소유가 가능하며 소유주가 이에 대한 책임을 진다.
- 뮤텍스의 경우 뮤텍스를 소유하고 있는 스레드가 이 뮤텍스를 해제할 수 있다. 하지만 세마포어의 경우 이러한 세마포어를 소유하지 않는 스레드가 세마포어를 해제할 수 있다.
- 세마포어는 시스템 범위에 걸쳐 있고 파일 시스템 상의 파일 형태로 존재한다. 반면 뮤텍스는 프로세스 범위를 가지며 프로세스가 종료될 때 자동으로 clean up 된다.
- 가장 큰 차이점은 관리하는 동기화 대상의 갯수 이다.(뮤텍스는 오직 하나, 세마포어는 하나 이상)

Spin Lock

busy waiting을 하는 semaphore

스핀락은 말 그대로, 다른 스레드가 lock(열쇠)을 소유하고 있다면 그 lock(열쇠)이 반환될 때 까지 계속 확인하며 기다리는 것이다. "조금만 기다리면 바로 쓸 수 있는데 굳이 컨텍스트 스위칭으로 부하를 줄 필요가 있나?" 라는 컨셉으로 개발된 것으로 임계영역에 진입이 불가할 때 Context Switch를 하지 않고 잠시 루프를 돌면서 재시도를 하는 것이다.

Lock과 UnLock을 하는 과정이 매우 짧아서 락하는 경우가 드문경우 유용하게 사용할 수 있다. 특징을 알아보자.

• Lock을 얻을 수 없다면 계속해서 Lock을 확인하며 얻을 때까지 기다린다. 이른바 바쁘게 기다리는 busy waiting이다.
• 바쁘게 기다린다는 것은 무한 루프를 돌면서 최대한 다른 스레드에게 CPU를 양보치 않는 것이다.
• Lock이 곧 사용가능해 질경우 Context Switch를 줄여 CPU의 부담을 덜어준다. 하지만, 어떤 스레드가 Lock을 오랫동안 유지한다면 오히려 CPU 시간을 많이 소모할 가능성이 있다.
• 하나의 CPU나, 하나의 코어만 있는 경우에는 유용하지 않다. 이유는, 만약 다른 스레드가 Lock을 가지고 있고 그 스레드가 Lock을 풀어 주려면 싱글 CPU 시스템에서는 어차피 Context Swtich가 일어나야 하기 때문이다.
• 스핀락을 잘못 사용할 경우 CPU 사용을 100%로 만드는 상황이 발생하므로 주의해야 한다. 스핀락은 기본적으로 무한루프를 돌면서 Lock을 기다리므로 하나의 쓰레드가 Lock을 오래 가지고 있다면 다른 블락킹된 쓰레드는 busy waiting하게 되므로 CPU를 쓸데없이 낭비한다.

단점

• Busy Waiting(바쁜 대기)
  Spin lock이라고 불리는 Semaphore 초기 버전에서 Critical Section 에 진입해야하는 프로세스는 진입 코드를 계속 반복 실행해야 하며, CPU 시간을 낭비했었다. 이를 Busy Waiting이라고 부르며 특수한 상황이 아니면 비효율적이다. 일반적으로는 Semaphore에서 Critical Section에 진입을 시도했지만 실패한 프로세스에 대해 Block시킨 뒤, Critical Section에 자리가 날 때 다시 깨우는 방식을 사용한다. 이 경우 Busy waiting으로 인한 시간낭비 문제가 해결된다.

Deadlock(교착상태)

• 세마포가 Ready Queue 를 가지고 있고, 둘 이상의 프로세스가 Critical Section 진입을 무한정 기다리고 있고, Critical Section 에서 실행되는 프로세스는 진입 대기 중인 프로세스가 실행되야만 빠져나올 수 있는 상황을 지칭한다.