[OS] Mutex lock과 Semaphore

Mutex Lock과 Semaphore는 여러 동기화 알고리즘의 기반이 되는 추상화된 동기화 방식이다.

Mutex Lock

공유자원을 동시에 하나의 프로세스 또는 스레드가 사용할 수 있도록 동기화한다.
available 변수로 구성된다. 이는 자원 잠금 여부를 나타내는 것이다.
프로세스 A가 자원을 얻었으면, 무조건 프로세스 A에 의해서만 자원이 해제될 수 있다.

available : boolean // lock의 가용 여부
acquire() { // lock 획득
    while ( !available ) ; 
    available = false;
}
release() { // lock 반환
	available = true;
}

Semaphore

공유 자원을 여러 개의 프로세스 또는 스레드가 사용할 수 있도록 동기화한다.
가용한 자원 수, 자원 획득, 자원반납 연산으로 구성된다.
Semaphore는 Counting 버전과 Binary 버전으로 나뉘어진다.
Binary Semaphore는 S의 도메인을 0과 1로 두고 하나의 작업이 공유 자원에 접근할 수 있게한다. 이처럼 상호 배제하게 동작하여 Mutex(Mutual Exclusion)라고도 불린다.

S : integer // 가용한 자원의 수
wait(S) {
  	while (S <= 0) ;
  	S --;
}
signal(S) { // 공유 자원 반환
  	S ++;
}

Mutex Lock과 달리, 자원을 얻은 프로세스 A가 아닌 동일한 자원 사용 중인 프로세스 B 의해 자원이 해제될 수 있다.

Busy-waiting의 대안

각 동기화 방식의 코드를 보면 자원을 대기하기 위해서 while 반복문을 통해 busy-waiting을 한다.
따라서 CPU가 일을 하지않고 기다리기 때문에 큰 자원낭비가 발생할 수 있다.

이와 대비되는 방식인 block & wakeup 방식이 있다. 자원을 당장에 사용할 수 없다면 프로세스를 대기 상태로 만들고, 가용한 자원이 생기면 깨워서 작업을 이어서하는 방식이다.

두 방식 장단점이 있기 때문에, 각각 적합한 상황이 있을 것이다.
이를 위해 Context switching비용과 임계 영역 수행 시간을 비교하면 된다. 둘 중context switching 비용이 더 크다면 busy-waiting을 하는 게 나을 것이고 임계 영역 수행시간 비용이 더 크다면 block & wakeup 방식이 나을 것이다.

SpinLock?

상호배제적으로 동기화하면서 busy-waiting 방식으로 동작하는 것을 SpinLock이라 한다.
따라서 Mutex Lock을 busy-waiting 방식으로 구현한 것을 Spin lock이라고 부르기도한다.