동기화 (mutex, Semaphore, monitor)

동기화의 필요성

 

멀티스레딩으로 갯수를 세는 상황을 가정해보자.

int target=0;을 2개의 스레드에서 50번씩 target++; 즉 값을 1씩 100번 늘리려고 한다.

target++;라는 연산을 어셈블리로 생각해보면

 

1. LOAD target R1   //메모리에 있는 변수의 값을 레지스터로 불러서

2. R1 = R1 + 1         // 레지스터에 불러온 값에 1을 더한 다음

3. STORE R1 taget // 레지스터에 있는 계산 결과를 다시 메모리에 저장한다.

 

고급언어로 적을 때에는 atomic 한 연산으로 보이지만 실제 작동은 그렇지 않다.

스레드 T1이 target이 0일때의 값을 읽어서 2번 과정을 통해 레지스터 R1에서 0+1 연산을 진행하는 도중

스레드 T2가 1번의 LOAD를 수행한다면, T1이 연산한 것을 STORE 하기 이전이므로 0을 읽어들이기에

target++; 연산은 두번 수행됐지만 T1도 1을 저장하고 T2도 1을 저장하여 target 변수에는 1이 저장된 상태다.

 

이를 방지하기 위해서 mutual exclusive하게 작동해야 하는 부분을 critical section으로 지정하여

 한 스레드가 critical section에 들어가기 전 lock을 부여받고 그동안 타 스레드는 받지 못하도록 처리해야 한다.

 

 

 

lock 처리 방법

 

spin lock. (계속확인)

critical section에 들어가기 전, 타 스레드가 들어가있는지 확인한다 ( while(test_and_set(&lock)); )

다른 스레드가 들어가있어서 불가능하다면 계속 대기하고, 그렇지않다면 들어가면서 체크해둔다.

test_and_set 메서드는 기계어로 atomic 한 작업이기 때문에 스레드들이 동시에 진입할 가능성은 없다.

lock 변수는 volatile로 선언하여 변화가 바로 메모리에 저장되도록 함.

lock이 길어질 경우 타 스레드가 계속 확인을 시도하며 cpu를 점유하고 비효율적이다.(Busy-Waiting)

 

뮤텍스 (안되면 sleep)

lock을 부여받지 못한다면 대기 큐에 들어가고 sleep 하고 있는다.

변수를 하나 더 도입해 guard와 value(락 여부) 로 판단

race condition으로 guard를 얻는다. 그상태에서 타 스레드가 lock을 갖고 있다면 대기큐에 자신을 넣어두고 sleep하며 특정 상황 전까지는 lock을 또 얻으려는 시도를 하지 않는다.

unlock() 시에는 대기 큐가 비어있지 않다면 sleep중인 다른 스레드를 호출해서 깨워준다.

 

멀티코어 환경이며, critical section에서의 작업이 컨텍스트 스위칭보다 빠르게 이루어진다면

spin lock이 더 유리한 상황이다.

sleep과 깨우는 과정 모두 컨텍스트 스위칭이 필요하기에

한 코어에서 한 스레드가 작업중이고 다른 코어에선 다른 스레드가 계속 lock 체크를 하고 있다면

unlock 하자마자 바로 다른 코어의 스레드가 작업을 시작할 수 있는데

뮤텍스 방식으로 접근하게되면 컨텍스트 스위칭이 발생하게 된다.

 

하지만 싱글코어 환경이라면 spin lock에서 문 계속 두드려도

컨텍스트스위칭 된 후에 unlock 될 수 있으므로 비효율적이다.

 

Semaphore

뮤텍스에서는 lock이 true 혹은 false다. 단 하나의 스레드만 동시에 취득 가능

Semaphore에서는 lock 취득 수를 정하여 lock을 int로 관리 해 value가 몇인지에 따라 부여한다.

즉 몇개의 스레드가 동시에 critical section에 진입할 수 있는지 관리한다.

1개까지면 binary Semaphore, 2개이상이면 counting Semaphore

 

Semaphore에서 unlock은 signal이라고 하는데, 뮤텍스에서 lock을 취득한 스레드만 unlock 할 수 있는것과 대비되어

semaphore에서 signal은 다른 스레드가 호출 가능하다.

task1, task2 등 각 작업과 Semaphore의 wait, signal 호출을 순서를 지정해 작업의 순서를 지정하는 것도 가능하다.

methodA는 task1을 바로 실행하고 signal을 보내는 메서드

methodB는 wait 확인 후 task2를 수행한다면

처음 semaphore에서 value가 0인 상태로 시작 시 

 

methodA가 먼저 실행되면 task1 실행 후 signal에 의해 value가 1이 되고 methodB에서 wait으로 value-- 후

task2를 실행하는 1->2 순서를 보장할 수 있고

 

methodB가 먼저 실행되더라도 value가 0이므로 wait하고 methodA에서 task1을 실행 후 signal이 날아와야 실행 가능.

1->2를 보장할 수 있다.

 

 

뮤텍스는 lock을 가진자만 락을 해제하지만 Semaphore은 wait와 signal의 주체가 다를 수 있기에

뮤텍스와 binary Semaphore은 다르다.

뮤텍스의 lock은 그 스레드에 소속된다.

 

뮤텍스에는 priority inheritance 개념이 존재한다.

프로세스들의 우선순위에 따라 스케줄링이 되어있을 텐데

lock 취득 경합에 의해 우선순위가 낮은 프로세스가 lock을 먼저 받게 된다면 

time slice등에 의해 컨텍스트 스위칭이 발생할 때 lock을 쥔 프로세스의 순서가 되는 시점이 늦어질 것이고

우선순위는 높지만 lock을 얻지 못한 프로세스는 lock을 쥔 프로세스에 종속되어 아무것도 할 수 없어진다.

이를 방지하기 위해 lock을 쥔 프로세스에 더 높은 우선순위를 가진 프로세스가 종속되면

lock을 쥔 프로세스의 우선순위를 그만큼 높여준다.

(sleep 중인 프로세스는 signal 전에 cpu time을 할당받지 않는다)

 

 

모니터

뮤텍스에 waiting queue를 추가한 시스템이다.

mutual exclusive를 보장하기 위한 lock이 존재한다. lock을 다른 스레드가 갖고 있는 상황이면 entry queue에서 대기하고, 그 스레드가 unlock 될 때 entry queue의 스레드를 깨워준다.

lock을 얻었다고 해서 바로 critical section에 접근할 수 있는것은 아닌데

lock을 얻으면 특정 조건을 검사해서 그 조건을 만족해야 접근할 수 있다.

그 조건을 만족하지 않는다면 해당 조건에 맞는 waiting queue에 삽입된다.

조건을 만족한다면 critical section의 작업을 수행하고, 해당 작업이 마쳐짐으로서 waiting queue에 있는 다른 스레드의 조건이 만족될 수 있으므로 해당 부분에 해당하는 조건변수의 queue에 있는 스레드를 깨워준다. 그로 인해 깨어난 스레드는 lock을 부여받을 수 있다면 받고 다시 조건을 검사해야 한다.