스핀락, 뮤텍스, 세마포 - 특징과 차이점들

9 분 소요

쉬운 코드님의 영상 https://www.youtube.com/watch?v=gTkvX2Awj6g 를 듣고 정리

들어가기 앞서 용어정리

Race Condition(경쟁상태) :
여러 프로세스/스레드가 동시에 같은 데이터(공유자원)를 조작할 때 타이밍이나 접근 순서에 따라 결과가 달라질 수 있는 상황을 의미한다.
Synchronization(동기화) :
여러 프로세스/스레드를 동시에 실행해도 공유 데이터의 일관성을 유지하는 것을 의미한다.
Critical Section(임계영역) :
공유 데이터의 일관성을 보장하기 위해 하나의 프로세스/스레드만 진입해서 실행 가능한 영역을 의미한다.
이때 하나의 프로세스/스레드만 진입해서 실행 가능한 이 바로 Mutual Exclusion이다.

임계영역 문제를 해결하기 위한 세가지 조건

상호 배제(Mutual Exclusion)

한 프로세스가 임계구역에 들어가면 다른 프로세스는 임계구역에 들어갈 수 없다.
한정대기( Bounded wating)

어떤 프로세스도 임계구역 진입을 무한히 대기해서는 안된다. 즉 어떤 프로세스도 starvation을 해서는 안된다.
진행의 융퉁성(Progress )

한 프로세스가 다른 프로세스의 진행을 방해해서는 안된다. 즉 아무도 크리티컬 섹션을 사용하지 않는다면 크리티컬 섹션을 쓰길 원하는 다른 프로세스/스레드는 즉시 할당받을 수 있어야한다.

결론부터 말하면 스핀락, 뮤텍스, 세마포 모두 Criticial Section의 문제를 해결하기 위한 락 기법들이다.

락이란

do
{
    acquire lock
        critical section
    release lock
        remainder section
} while True

Mutual Exclusion( 하나의 프로세스 / 스레드만 진입해서 실행 가능한) 의 상태를 보장하기 위해서 사용하는 개념이다.
프로세스나 스레드가 acquire lock, 즉 락을 획득하기 위해 경합을 한다.
그 중에 락을 획득하는 것을 성공한 프로세스나 스레드만 크리티컬 섹션에 진입할 수 있다.
이후 크리티컬 섹션에서 볼 일을 모두 마친 프로세스/스레드는 release lock, 락을 반환하게 된다.

acquire lock,즉 요청을 구현하는 부분을 Entry Section, 크리티컬 섹션 수행 이후 release lock, 락을 푸는 구역을 exit section 이라고 부른다.

SpinLock

lock 변수: 여러 스레드들이 접근 가능한 락 변수이다
void critical() : 여러 스레드들이 접근하여 실행할 수 있는 함수이다. while loop를 통해 락을 얻으려 경합을 한다. 락을 획득한 스레드는 lock 변수를 1로 두고(락을 점유한다는 의미) 크리티컬 섹션에 진입해 공유 자원을 사용한다. 전부 사용한 후에 다시 락을 0으로 돌려놓는다(락을 반환한다는 의미).
Test_and_set(&lock) 함수: 하드웨어 차원에서 atomic한 실행이 보장되는 시스템 콜 의 일종이다. 공유되는 lock 변수에 대해 원래 가지고 있었단 값을 가져와서 그 값을 반환한다. 이때, 반환하기 직전에 *lockPtr = 1, 로 락 값을 다시 1로 돌려놓는다. 다시 말하면, test_and_set함수는 반드시 이전에 있었던 lock 값을 반환한다. 하지만 이전에 있었던 lock 값이 무엇이었던 간에 함수를 실행하고 나면 lock 값은 1이 되버린다.

위 상황에서 T1, T2 스레드 두개가 있다고 하자. 이 상황에서 T1이 먼저 critical()함수를 호출했다고 하자. 그러면 T1은 먼저 while문의 조건문을 검사하게 된다.

이 조건문에서 기존에 있었던 락 값은 0 이기 때문에 test_and_set 함수는 결과로 0을 반환하게 되고, 실제 락 값은 1로 바뀌게 된다.

T1 입장에서, while문의 조건문이 만족이 안되기 때문에,(test_and_set이 0을 반환) while 구간을 탈출하고 크리티컬 섹션을 사용하게 된다.

T1이 크리티컬 섹션을 사용하는 동안, T2가 critical() 함수를 실행했다고 하자.

이떄, lock 변수의 값은 1이다.(앞선 T1이 호출했던 Test_and_set 함수가 1로 바꿔놓음) 때문에 T2는 while문의 조건식을 만족하게 되고 test_and_set을 반복해서 실행하게된다.

-> 즉 스핀(spin) 뱅글뱅글 while문을 반복하면서, T1이 임계구역을 다 사용한 후 lock=0 코드를 실행하기까지 대기하게된다.

마침내 T1이 critical section을 모두 사용하고 그 다음 lock=0을 실행하는 순간, T2의 while문 조건이 불만족되게 되고 T2는 락을 획득하여 임계구역에 진입하게 된다.

test_and_set?

앞선 예제의 로직을 살펴보면 락이 critical section의 mutual exclusion을 만족시킬 수 없는 상황이 존재한다.

만일 T1, T2가 동시에 critical함수를 실행해서, 동시에 test_and_set을 실행하고, 동시에 int oldLock = *lockPtr 코드를 실행한다면, 두 스레드 모두 oldLock변수에 0을 읽어오게 될 것이다. 그렇게 된다면 동시에 두 스레드가 임계영역에 진입하게 될 것이고 이는 mutual exclusion을 보장하지 못하는 것 아닐까??

결론부터 얘기하자면 그렇지 않다. 앞서 말했다시피, test_and_set은 atomicity한 실행을 보장받는 CPU의 atomic 명령어이기 때문이다.

CPU atomic 명령어는 아래와 같은 특징들을 지닌다.

실행 중간에 간섭받거나 중단되지 않으며,
같은 메모리 영역에 대해 동시에 실행되지 않는다

따라서, 위에 우려했던 상황은 따라서 일어나지 않는다.

멀티코어 시스템에서, 두개의 프로세서가 두개의 스레드에서 동시에 critical()함수를 호출했다고 해도, 한 스레드가 미세한 차이로 먼저 test_and_set함수를 실행시키는 순간, CPU 차원에서 다른 스레드들의 test_and_set의 메모리영역(lock 변수)의 진입을 막아버린다.

뿐만아니라, 한 스레드가 test_and_set을 실행시키는 동안 context switch가 일어나 다른 스레드가 실행되는 일 자체도 역시 일어날 수 없다.

결론적으로 위의 스핀 락 로직은 하드웨어적으로 atomic한 실행이 보장받기 때문에 mutual exclusion을 보장할 수 있다.

스핀락의 소프트웨어적인 구현 - 피터슨 알고리즘

스핀락을 소프트웨어적으로 구현한 대표적인 알고리즘이 피터슨 알고리즘이다. 크리티컬 섹션 문제의 해결 조건 세가지인 Mutual Exclusive, bounded waiting, progress 조건을 모두 만족한다.

하지만 현대에는 잘 쓰이지 않는데 그 이유는 컴파일러의 발전때문이라고 한다. 현대 컴파일러는 컴파일시 코드 최적화를 진행하는데 그 과정 속에서 코드가 뭉개져버려 스핀락의 기능을 제대로 수행하지 못할 수 있기 때문이라고 한다.

스핀락의 단점

스핀락은 결국 크리티컬 섹션 진입을 위한 락을 획득할때까지, 반복해서 while문의 test_and_set을 실행시키면서 대기한다.

하지만 이 방식은 락 획득을 기다리는동안 CPU 프로세서, 메모리 등 시스템 자원을 낭비한다는 치명적인 단점이 존재한다.

Mutex

mutex -> lock()
... critical section
mutex -> unlock()

뮤텍스란?

마찬가지로 Mutual Exclusion( 하나의 프로세스 / 스레드만 진입해서 실행 가능한) 의 상태를 보장하기 위해서 사용하는 개념이다. 스핀락과 다른 점은 락을 획득하기 까지 CPU 자원을 사용하지 않고 휴식을 취하는 방식이라는 점이다.

여러 스레드들은 critical section 진입을 위해 mutex 객체의 lock()함수를 통해 락을 얻는 과정을 시도한다. 이때, 락이 만일 다른 스레드에 의해 점유되었다면, 스레드는 스핀락에서 때 처럼 busy wait을 하는 것이 아니라 자기 자신을 sleep 시키버린다.(CPU 스케쥴러의 block 큐에 넣어버림)

크리티컬 섹션을 다 사용한 스레드는 이후 unlock()함수를 통해 value값을 다시 1로 돌려놓거나,( 락을 release한다는 의미) 대기중인 다른 스레드(스케줄러 큐에서 대기하는)가 존재한다면 해당 스레드를 꺠우게 된다.

Mutex.value : 락을 대표하는 변수이다.

Mutex.guard: 락을 얻기 위해 일어날 수 있는 race_condition을 방지하기 위한 (guard) 변수이다. 앞선 스핀락에서처럼, test_and_set과 함께 사용된다.

달리 말하면 Mutex의 value 변수도 결국 크리티컬 섹션이라고 볼 수 있다. 즉 mutual exclusion을 위해 구현한 뮤텍스 클래스 내부에 존재하는 락을 대표하는(value 변수)가 임계영역에 해당하기 때문에 이 영역의 mutual exclusion을 보장하기 위해 사용하는 또 다른 lock이 바로 guard라고 볼 수 있겠다

다시 스레드 T1과 T2의 예제를 들어보자

T1 이 먼저 mutex:lock()을 실행.

guard를 취득하기 위해 경합을 하게 된다
guard를 취득한 T1 스레드는 스핀락을 탈출한다. T1는 진짜 락 값인 value값을 바꾸는 로직을 실행, 즉 락을 취득한다 (else구문 의 value = 0),, 락을 취득하고 나서 guard 값도 다시 0으로 바꾼다(else구문 의 guard = 0) 이후 임계영역에 진입하게 된다.
뒤 늦게 guard를 취득해서 value값을 확인하게 되는 T2는 value가 이미 0이므로 if문에 조건에 부합하게 된다. 자기 자신을 큐에 넣고 sleep상태에 빠지게 된다.

여기까지 진행하면 현재 상황은 T1이 크리티컬 섹션 사용중, T2는 스케줄러의 큐에서 sleep상태이다.

이후 T1이 크리티컬 섹션을 다 사용하고 나서, Mutex: unlock()이 실행된다.

마찬가지로 guard를 취득하기 위해 spinlock 경합을 한다. (unlock을 실행하는 순간 제 3의 스레드, T3가 lock()을 수행할 수도 있기 때문)
guard를 얻어 스핀락 while문을 탈출하게 되면, if문을 만나게 된다. T2가 대기중이므로 T2를 깨우고, 다시 guard를 0으로 돌려놓고 로직을 마친다.
깨어난 T2는 임계영역에 진입한다.

T2가 임계영역을 모두 쓰고나서 unlock()을 실행시키면, 이제는 아무도 대기하는 스레드가 없기 때문에 value를 1로 바꾸게 된다.

(만일 value가 0인상태라면 초입부의 progress 조건을 위반하게 됨)

뮤텍스 - 생각해볼 점

핵심은 두가지다.

busy wait 대기가 아닌 sleep상태의 대기를 수행한다. -> CPU cycle의 낭비를 최소화하기에 spin lock의 단점을 극복했다.
결국 뮤텍스의 구현 자체도 스핀 락을 사용한다는 점. -> 일정 기간 스핀 락을 사용한다.

의문점: 스핀락의 단점을 해결하기 위해 뮤텍스를 만들었는데 뮤텍스에서 조차도 스핀락을 사용한다??? 그렇다면 스핀락의 단점을 그대로 지니는 것이 아닌가?

헷갈릴 수 있다. 하지만 곰곰히 다시 생각해보면, 스핀락을 사용하는 뮤텍스가 단독 스핀락보다 훨씬 이득이다.

스핀락을 하는 기간은 매우 짧다. 오직 Guard 변수를 취득하기 위해 대기하는 과정일 뿐이다. guard는 스레드의 임계영역 단위의 lock 개념이 아니다. 진정한 스레드 단위의 임계영역 제어를 위한 락은 바로 value이다. guard는 이 value값에 접근하는 것을 막기 위한 매우 작은 개념의 락이다. 따라서, guard를 취득하기 위한 경합은 매우 짧은 시간이 소요되고 대부분의 waiting 은 sleept상태에서 이루어진다.

하지만 스핀락 단독으로 쓰인다면 락 자체가 1개이기에 계속 busy waiting을 하며 cpu 리소스를 잡아먹게 된다. 따라서 뮤텍스가 스핀락을 이용해 구현되었기 때문에 스핀락의 단점을 그대로 지닌다는 말은 성립되지 않는다. 정확히 말하면 뮤텍스 역시 스핀락의 단점인 busy wait을 하긴 하지만, spin lock 단독으로 쓰일 때에 비해 매우 적은 양이라고 할 수 있겠다.

뮤텍스 - 장단점

거의 모든 것에는 장단이 존재한다. 뮤텍스도 스핀락보다 항상 좋은 것은 아니다.

멀티 코어 환경이고,
critical section에서의 작업이 컨텍스트 스위칭보다 더 빨리 끝난다면 스핀락이 뮤텍스보다 더 이점이 있다!

크리티컬 섹션에서의 작업이 컨텍스트 스위칭보다 더 빨리 끝난다?

-> 뮤텍스에서 스레드가 대기할 때, 슬립 상태에 들어가게 되고, 대기가 끝나면 일어나게 된다.

이 잠들고 일어나는 과정, 즉 컨텍스트 스위칭에서 소요되는 오버헤드에 비해 크리티컬 섹션에서의 작업이 더 빠르게 끝난다면 뮤텍스보다는 스핀락을 쓰는게 당연히 더 효율적이다.

멀티코어환경??

-> 스핀락 방식은 한 스레드가 busy wait으로 기다리고 있을 때, 탈출하기 위해 락을 취득을 하려면 다른 스레드가 락을 놓아줘야만한다. 락을 취득한 다른 스레드를 진행시켜야만 락을 풀고 대기중인 스레드의 진행이 가능하다는 것인데 싱글 코어 환경에서는 결국 컨텍스트 스위칭을 통해서만 다른 스레드를 진행시킬 수 있다, 이는 결국 컨텍스트 스위치가 반드시 일어나야함을 뜻하기 때문에 스핀락 방식에 이점이 전혀 없다.

Semaphore

세마포란 signal mechanism을 가진, 하나 이상의 프로세스/스레드가 critical section에 접근 가능하도록 하는 장치를 의미한다.

뮤텍스와 로직은 동일하다. 마찬가지로 semaphore도 value를 통해 임계영역의 락을 구현하고, 이 value에 대한 접근을 보호하기 위한 (또다른 임계영역의 락) guard를 사용한다.

다른 부분은 바로 value 값으로 1 외에 모든 정수 값들을 갖는 것이 가능하다는 점이다.

왜 이렇게 바꿔주었을까? 세마포는 크리티컬 섹션에 동시에 프로세스/스레드가 두 개 이상 들어갈 수 있게 관리하는 장치다. 이때 들어갈 수 있는 프로세스/스레드 수는 처음에 설정한 value 값이 된다.

세마포도 오직 하나의 프로세스/스레드만 임계영역에 접근할 수 있도록 구현할 수 있따.(뮤텍스와 같다) value 초기 값을 1로 두면 된다.

value의 초기 값이 1인 세마포를 binary semaphore라고 하며 value 초기값이 1이상인 세마포는 counting semaphore라고 한다.

시그널 메커니즘이란?

세마포는 순서를 정해줄 때에도 사용이 가능하다.

위 그림의 상황은 두개의 프로세스가 세마포를 이용해 동기화를 구현한 상황이다.

왼쪽과 오른쪽 프로세스를 각가 P1, P2라 하자. 위 로직에서는 task 3는 반드시 task1,task2 가 끝난 후에 시작하게 된다.

P1의 task1이 P2의 task2보다 먼저 끝나는 경우

이 경우 P1은 먼저 signal()을 호출하게 되고 value 값이 1이 되게 된다. 이후 task2가완료되어 P2가 wait()을 실행시키면, value가 1이므로 바로 락을 획득하여 task3를 수행하게 된다.
P2의 task2가 P1의 task1 보다 먼저 끝나는 경우

이 경우 P2가 task2를 먼저 끝내고, semaphore-> wait()을 호출한다. 이때 value = 0이므로 락을 획득할 수 없기에 p2는 슬립 상태가 된다. 이후 task1이 완료되고 p1이 signal()을 호출하면 p2가 일어나고 task3를 수행하게 된다.

이처럼 세마포의 기능이 순서를 정해주는 성격이 있기 때문에 시그널 매커니즘이라고 한다. 시그널 메커니즘은 뮤텍스와 달리, 반드시 signal() wait()이 동일 프로세스/스레드 내에서 실행될 필요가 없다는 특징을 지닌다.

뮤텍스 vs 세마포

뮤텍스와 이진 세마포는 똑같은 것이 아닐까? ==> 아니다.

뮤텍스는 락을 가진 자만 락을 해제할 수 있지만, 세마포는 그렇지 않다. 세마포는 wait과 signal이 한 프로세스/스레드 내에서만 실행되지 않아도 된다.

뮤텍스 락은 락을 가진 프로세스/스레드에 종속되어버린다. (따라서 락을 기다리는 프로세스/스레드의 입장에서 누가 락을 풀어줄 수 있는지 예측이 가능하다)

세마포는 반대로 누구든지 락을 걸 수 있고 signal을 보낼 수 있다.

-> 락을 해체하는 주체가 다름

뮤텍스는 Priority inheritance 속성을 가진다. -> 스케쥴링 상황에서 pirority inversion 문제를 해결할 수 있다!

Priority Inversion 문제

예제를 보면, 세개의 프로세스가 시스템에서 수행되고 있다. p1이 우선순위가 가장 높고 p3가 우선순위가 가장 낮다. 어느 시점에서 p3가 자신의 코드의 특정 영역을 수행하다가, 여러개 프로세스가 임계 영역에 접근하게 되고 read write을 수행한다. 이때 만일 락을 건 상태로, p3가 자신의 할당 time을 다 써서 프로세스 스위치가 일어났다고 하자.

하필, 이후에 p1이 p3가 락을 걸어놓은 임계영역을 접근해야한다면 어떻게 될까? p1은 우선순위가 가장 높은데도 불구하고 block 상태가 되고 자신보다 한참 낮은 우선순위에 있는 p3가 락을 해제할때 까지 block을 할 수 밖에 없다. 다시말해 스케쥴러 상에서, p2,p3가 우선순위가 p1보다 낮은데도 불구하고 먼저 수행을 마치게 된다. 때문에 이런 문제를 priority inversion이라고 한다.

이 문제의 해결책 중 하나로 “ priority inheritance” solution가 존재하고 뮤텍스에 이 soultion이 적용되어있다. (세마포는 없음)

아까와 같은 상황에서, p1이 공유데이터에 접근할 때 p3에 의한 락이 있다면 p3의 우선순위를 순간적으로 먼저 높여준다(정확히 말하면 p1의 우선순위를 부여받는다). 이러면 p3가 우선적으로 수행되므로 걸었던 락이 p2수행을 기다릴 필요 없이 해제될 것이고, 락이 해제된 이후에는 다시 p1이 작업을 재게하고 이후에 p2가 수행하는 식으로 priority inversion 문제를 해결하고 이 우선순위를 상속시키는 개념이 바로 priority inheritance이다.

세마포는 priority inheritance 속성이 없다. 왜냐하면 세마포는 누가 락을 해제할지, 즉 누가 signal을 날릴지 정해지지 않았기 때문이다.

상호 배제만 필요하다면 뮤텍스를, 작업간의 실행 순서 동기화가 필요하다면 세마포를 사용하면 된다

비교	세마포	뮤텍스
동시 접근 여부	여러 프로세스/스레드가 임계영역에 동시에 접근 가능	한번에 한 프로세스만이 한 임계영역에 접근 가능
락의 해제	세마포 값은 락을 얻거나 해제하는 프로세스가 일치하지 않을 수 있음 락의 획득과 해체하는 주체가 다름	뮤텍스는 락을 획득 한 프로세스에 의해서만 해제가능 락의 획득과 해체를 하는 주체가 같음
Priority inheritence 속성	있음	없음
	시그널 메커니즘	락 메커니즘

Reference

https://www.youtube.com/watch?v=gTkvX2Awj6g 를 듣고 정리

Twitter Facebook LinkedIn

규눙