스핀락(spinlock) 뮤텍스(mutex) 세마포(semaphore)

임계 영역

공유 데이터의 일관성을 유지하기 위해, 하나의 프로세스/스레드만 진입할 수 있는 코드 영역!!

Q. 그럼 어떻게 하나의 프로세스/스레드만 진입(mutual exclusive)시킬까?

A. Lock을 활용!

참고로, lock은 모든 프로세스/스레드에서 동시 접근이 가능해야 하기에, 전역(global)으로 선언을 해야 한다.

while(test_and_set(&lock) == 1) ;    -> lock==1인 동안에는 무한 루프를 계속 돌며, critical section에 진입하기 못하게 한

다. (mutual exclusive 해결)

( 위 코드에서 만약 T1이 Critical Section 도중에 context switching이 일어났다고 해도, 다른 프로세스/스레드들은 T1이 다시 재실행되어 Critical Section 코드를 다 끝내지 전까지는 진입을 하지 못한다.)

 

 Q. 이런 의문이 들 수가 있다. 만약 2개의 스레드 T1, T2가 while(...) 부분을 동시에 실행시키면, 둘 다 동시에 critical section 영역에 집입할 수가 있는 것 아니냐??

A. Nope!! 위와 같은 문제는 cpu level에서 해결해 준다. 

test_and_set(&lock)은 사실 cpu level에서 아래 2가지의 도움을 받는다.

1. 실행 중에 간섭받지 않고, 중단되지 않는다.( 멀티 코어 환경에서도 1개의 스레드만 실행이 된다.)

2. 같은 메모리 영역(test_and_set의  매개변수)에 대해 동시에 실행되지 않는다.

-> 만약 2개의 스레드가 test_and_set()을 동일한 매개변수에 대해서(lock) 동시에 호출을 한다 할지라도, cpu level에서 자

동으로 먼저 1개의 스레드를 실행시키고 나머지 1개의 스레드를 실행시키도록 동기화를 시킨다. 

그러므로, 2개의 스레드가 while(...) 부분을 동시에 실행할 수는 없다. 

 

스핀락(spinLock) : 위와 같이 lock을 가질 수 있을 떄까지 반복해서 시도하는 것. 

만약 T1스레드가 Critical Section에 있을 때, T2 쓰레드는 계속해서 while(..)을 실행하려고 할 것이다.

이것은 굉장한 cpu 낭비이다. 

그래서 나온 것이 뮤텍스(Mutex) 알고리즘이다. 

뮤텍스(Mutex) : 먼저 선점하고 있는 스레드가 있을 경우, 스레드를 큐(Queue)에 넣어서, 선점하고 있는 스레드의 실행이 끝날 때까지 대기하게 한다.

 미리 선점하고 있는 스레드가 있다면, 나머지 스레드들은 lock이 풀릴 때까지 아무런 실행을 하지 않고, Queue에서 대기!

Q. Mutex가 항상 SpinLock보다 좋을까?

A. 항상 그렇지는 않다. 

멀티 코어 환경에서 스피락 상황에서의 T1의 실행 시간이 뮤텍스 상황에서의 T1의 실행 시간보다 짧으면, 스핀락이 더 유

리하다.

왜냐하면, 뮤텍스에서 T1의 실행이 끝나게 되면 곧바로 T2를 깨우는 과정에서 Context Switching이 생기나,

스핀락은 멀티코어 환경에서 T1이 끝나면, 다른 코어에서 T2이 Context Switching 없이 바로 T2가 실행되기에 훨씬 빠르

다. 

 

세마포어(semaphore) : signal mechanism을 가진 하나 이상의 프로세스/스레드가 criticla section에 접근 가능하도록 하는

장치. 

 

binary semephore vs counting semaphore

binary semaphore  : value가 1인 semaphore

counting semaphore : value가 2이상인 semaphore

-> 세마포어에 대한 설명은 아래 링크의 비유가 와닿는다. 

https://worthpreading.tistory.com/90

뮤텍스(Mutex)와 세마포어(Semaphore)의 차이

 

Q. 세마포어는 Signal Mechanism을 가진다는 것이 무슨 말일까? 아래의 예제를 보자. 

 

 

2개의 코어A,B가 있다고 하자. 

코어 A는 P1, 코어 B는 P2를 각각 실행을 한다고 하자.

이때 만약, task3를 반드시 task1보다 먼저 실행시켜야 한다고 가정을 해보자. 

이때에는 어떤 경우에도 task3이 task1보다 나중에 실행이 된다.

1] semaphore->signal()이 semaphore->wait()보다 먼저 실행된 경우

semaphore->wait실행 시점에서 value 1이므로, value를 0으로 바꾼 뒤에. task3을 실행

2]semaphore->wait()가 semaphore->signal()보다 먼저 실행된 경우

semaphore->wait실행 시점에서 value 0이므로, P2를 큐에 집어 넣는다.

task1이 끝나고, semaphore->signal에 의해서 value가 1로 되어서, 큐에 대기하고 있는 P2가 깨어자 TASK3이 실행됨. 

 

Mutex != Binary Semaphore

1.

Mutex는 하나의 프로세스/스레드에서 반드시 lock, unlock()이 일어난다.즉, lock을 가진 프로세스/스레드만이 lock을 unlock을 할 수가 있다. 

Binary Semaphore는 위 그림에서도 봤듯이 서로 다른 프로세스/스레드에서 signal, wait()가 실행이 될 수가 있다.

2.

Mutex는 priority inheritance 속성을 가지지만, 세마포아는 가지지 않는다. 

 

priority inheritance 

뮤텍스는 lock을 가진 프로세스/스레드만이 lock을 해제할수 있다고 배웠다.

CPU 스케줄러에는 Prioriy 스케줄러가 있다. 

이때 p1이 p2보다 우선순위가 높다고 가정해보자.

만약, 위 상황에서 p2가 먼저 실행이 되어, lock을 취득하자마자 p2의 실행이 종료가 되었다고 해보자.

그럼 p1은 우선순위가 높음에도 불구하고, p2가 lock을 해제할 때까지 아무것도 못한다. 

이때, 뮤텍스는 이를 해결하기 위하여 p2의 우선순위를 p1만큼 올려서 빨리 실행을 시켜, lock을 해제하게 만들어서 우선

순위가 높은 p1을 실행시키려고 한다. 

이러한 속성을 prioriy inheritance라고 한다. 

그러나 세마포아는 어떤 프로세스/스레드가 먼저 signal()을 날릴지 알 수가 없기 때문이다.