[Parallel Computing] (10) Synchronization

동기화(Synchronization)는 스레드 간이나 프로세서 간 실행되는 순서를 정하고, 상호 배제(Mutual Exclusion)를 달성하기 위하여 필요하다.
스레드 관점에서의 상호 배제(Mutual Exclusion)는 특정 스레드가 수행하고 있는 코드 부분을 다른 스레드가 수행할 수 없을 때, 즉 하나의 스레드만 해당 코드 영역을 수행할 수 있때를 의미한다.  
베리어는 일종의 동기화 포인트이다. 여러 스레드가 동시에 수행하고 있을 때, 스레드가 이 베리어를 만나면 실행을 멈추고, 다른 모든 스레드가 이 베리어가 도달할 때까지 기다린 다음에 다시 실행을 계속하게 된다. 일반적으로 SPMD(Same Program Mutiple Data)와 같이 같은 함수(코드)를 동시에 실행할 때 흔하게 이용된다.
Data Race는 두 개 이상의 스레드가 같은 메모리 위치를 액세스 하고, 그중의 하나의 스레드가 그 위치에 쓰기를 수행하고, 그 위치가 동기화에 의해 보호되지 않을 때 발생하는 것을 의미한다. 예를 들어 'A', 'B' 스레드가 변수 'X'를 접근하는 데, 'A'는 변수 X를 쓰고, 'B'는 변수 'X'를 읽는다고 하자. 동기화가 없다면 아래와 같이 여러 Case가 발생한다.  
1. A:: Write X -> B :: Read X
2. B:: Read X -> A :: Write X
두 Case가 서로 다른 결과를 보일 것이다. 이는 실행할 때마다 머신의 상태가 다르고, 그렇기 때문에 실행되는 순서는 매번 다르게 나타 날 수 있다. 그런데 이런 속성을 의도적으로 사용할 때가 있다. 특정 변수를 통해서 동기화를 수행하는 busy-wait 동기화, Lock-free 알고리즘의 그 예이다. 그렇지만 보통은 버그에 속한다.
busy-wait 동기화는 기능적인 측면에서 Producer와 Consumer로 나눌 수 있고, Producer는 동작을 수행하고, 동작이 완료되었다는 것을 특정 변수에 기록한다. Consumer는 계속 바쁘게(busy) 특정 변수의 값이 변경되었다는 것을 확인하면서 기다린다(wait).
  Thread safety는 특정 함수가 두 개 이상의 스레드가 어떤 함수를 동시에 호출했을 때, 그 함수가 항상 올바르게 동작한다는 것을 의미한다.
Atomicity는 분해할 수 없다는 의미로, 모든 연산이 수행되면 다 수행되거나(all) 수행되지 않으면 다 수행되지 않는 것(nothing)을 의미한다. 즉, 분해할 수 없으므로 연산 중간의 부분적인 수행에 대한 결과를 볼 수 없다. 이 Atomicity는 상호 배제(Mutual Exclusion)로 보장할 수 있다. 즉, 특정 코드 부분이 여러 스레드로 분해되지 않고, 한 개의 스레드에서만 실행될 때, 상호 배제적이며, 그 코드 영역은 Atomic 하게 수행된다. 그 코드 영역을 Critical section이라 한다.
하나의 스레드만 해당 코드 영역을 수행하게 하기 위하여 Lock을 사용한다. 간단히 말하면, 이 코드 영역은 이미 특정 스레드가 수행 중이니 다른 스레드는 수행할 수 없도록 잠그는 것이다.  Lock variable(L)를 이용하여 처리하고, locked, unlocked 두 가지 상태를 가진다. 또한, 두 개의 함수인 Lock을 수행하는 lock(L) 함수와 Lock을 푸는 unlock(L)를 가진다.
  일반적으로 unlock을 기다리는 스레드가 어떤 상태로 있을 지에 따라 두 가지로 나뉜다. 계속 기다리는 방법과 Sleep 모드로 진입하는 방법이 있다. 계속 기다리는 방법은 busy-wait 방식으로 Spinlocks이라고 한다.
Spinlocks은 lock이 풀릴 때까지 계속 기다리는 방법으로 lock이 풀리자마자 빠르게 수행될 수 있다. 계속 기다리므로 다른 스레드로의 전환(Context switching)에 대한 비용이 들지 않는다. 그러나 달리 생각하면, 계속 아무것도 안 하고 기다리므로 CPU Cycle를 손해 보고 있다. lock 함수에서 사용되는 Test and set Instruction은 Lock Variable(L) 값을 읽고, 값이 0이면 1로 쓴다. 읽고 쓰는 과정을 atomic instruction으로 만들어야 Lock Variable이 중간에 변경되는 것을 막을 수 있다. 그런데 Lock variable(L)을 메모리로부터 읽어오게 되면 큰 오버헤드가 발생한다. 이를 메모리가 아닌 캐시로부터 읽어와서 처리하고자 Cache coherenece 특성을 활용한다. 한 스레드가 자신의 Private Cache에 Lock variable(L)을 올려둔 상태에서 다른 스레드가 Lock variable(L)에 다른 값을 쓰게 되면, Cache coherence 정책에 따라 값이 변경된 것을 알 수 있고, 기존에 Private Cache에 저장되어 있는 값을 변경한다.  
Sleeplock 방식은 스레드가 CPU를 점유한 상태로 두지 않고, OS가 해당 스레드를 Sleep 모드로 변경하고, lock이 풀리면 다시 수행한다. 동시에 하나의 스레드만 처리하므로 하나의 processor state를 가지는 uniprocessor에서 사용가능하다. OS가 처리하므로 전환 속도가 느리다.
Lock을 이용한 동기화 방법은 생각하기 쉽고 사용하기도 쉽다. 그러나 상황에 따라 아무것도 진행하지 못하는 deadlock이 발생할 수도 있다. 예를 들어 두 개의 스레드(A, B)가 두 개의 Lock 변수(M, L)를 사용할 때 발생할 수 있다.  아래와 같이 'A' 스레드는 L -> M 순서로 Lock을 수행하고, 'B' 스레드는 M -> L 순서로 Lock을 수행한다고 가정하면, 각각 처음 Lock은 동시에 수행될 수 있다. 그런데, 그다음 Lock은 상대 스레드가 unlock 할 때까지 기다려야 하는데, 각 스레드 모두 unlock을 하지 않고 있다. 이 경우, 각 스레드는 unlock이 될 때까지 계속 기다리는 deadlock에 빠진다.
   A : L  -> M
   B : M -> L
Lock을 이용한 동기화 방법의 또 다른 단점은 Priority Inversion이 발생할 수 있다. 한 개의 Processor만 있는 경우, 하나의 스레드만 active 가능하므로 다른 스레드는 sleep 모드에 있다. 예를 들어 두 개의 스레드(T1, T2)가 존재하다고 가정하자. 그리고 T1은 T2보다 높은 Priority를 가지고 있다. 일정 시간 이후, T2는 Critical section에 진입하여 동작을 수행하고 있는데, 이때 T1이 동작가능한 상태가 되면, 스케쥴러는 T2는 멈추고 T1으로 수행하려고 한다. 그런데, T1이 자신의 Critical section으로 진입하려면 T2가 Lock을 풀어줄 때까지 기다려야 한다. 그런데 이때, T2보다 높고, T1보다 낮은 Priority를 가지는 스레드 T3가 들어오면, T2가 unlock을 수행하지 않았기 때문에 T1은 수행되지 못하고, T3가 수행될 수 있다. 이렇게 수행되다 보면 우선순위가 높은 T1이 늦게 수행될 수 있다.
또 다른 동기화 방법은 Semaphores이다. Semaphore는 'S'라는 항상 음수가 아닌 정수 값을 가지고 있다. Lock/Unlock과 비슷하게 P(S)/V(S)를 수행한다.(P와 V는 각각 try와 increment를 뜻하는 네덜란드어 Poberen과 Verhogen의 머릿글자라고 한다.) P(S)는 S가 0보다 크면 S 값을 감소시키고,  그렇지 않은 경우, S값이 0보다 클 때까지 대기한다. V(S)는 S값을 1 증가시키는 동작이며, S값이 0이 아닌 값이 되는 것을 여러 스레드가 기다린다 하더라도 하나의 스레드만 다시 시작할 수 있도록 한다. 이때, S값을 감소, 증가시키는 동작은 atomic 하다.  
Semaphores에 의해 suspend 된 스레드는 더 이상 busy-wait loop에서 변수를 체크하는 동작을 수행하지 않는다.
S값이 0 또는 1일 때는 Binary Semaphore, 1보다 큰 값을 가질 때는 Counting Semaphore라 한다.
둘 다 초기 값은 최대한 가질 수 있는 리소스 개수로 보통 표기한다.
SPMD에서 Semaphores를 사용하여 동기화를 수행할 수 있다. Semaphore 변수를 선언하고, atomic 하게 수행하기 원하는 코드 영역을 S/V 함수로 감싸주면 된다.
스레드를 사용하는 데 있어서, 데이터를 생성하는 Producer와 생성된 데이터를 사용하는 Consumer로 나눌 수 있다. 이런 경우, Binary Semaphore를 사용하면, Producer가 생성하고, Consumer가 사용하는데, Consumer 속도가 Producer보다 느리면 병목 현상이 발생한다. 이를 Buffer를 사용하여 병목 현상을 완화할 수 있다. 이때 사용되는 buffer의 종류는 circular buffer이며, 해당 buffer를 Control 하기 위해 Semaphore가 사용될 수 있다.
Counting Semaphore를 사용하면 slots 숫자와 elements 개수를 나타내는 두 개의 semaphore를 선언한다. 초기에 slots 값은 Buffer 크기로 지정하고, elements 값은 0으로 지정한다. producer는 slots 값을 보고 0보다 크면 P(slots)를 수행하여 slot 숫자를 줄이고, buffer에 elements를 저장한다. 그리고 V(elements)를 수행하여 elements 숫자를 증가시킨다. consumer는 elements 숫자를 보고 0보다 크면 P(elements)를 수행하여 elements 숫자를 줄이고, buffer에서 elements를 꺼내간다. 그리고 V(slots)를 수행하여 slots 숫자를 증가시킨다.
Binary Semaphore를 사용하면, empty 여부를 나타내는 not_empty, full 여부를 나타내는 not_full, elements 개수를 나타내는 count를 연산하는 코드를 보호하는 S Semaphore로 지정한다. Producer에서는 elements 개수를 나타내는 count를  증가시키고, Consumer는 감소시키는 코드 영역을 Critical section으로 지정하고 이를 S로 보호한다. 각 Producer와 Consumer는 내부의 Count를 두고, Empty/Full 여부를 체크할 수 있다. 이때 내부의 Counter는 critical section에서 global variable 'count'와 동기 한다.
Producer는 내부 Counter가 1이면 데이터를 buffer 넣고, Counter를 증가시키고, V(not_empty)를 이용하여 empty가 아니라고 알려준다. 그리고 내부의 Counter가 buffer 크기가 되었다면, not full 여부를 체크한다. P(not_full)로 not_full이 1이면 0으로 감소하고 buffer에 데이터를 입력한다.
Consumer는 내부 Counter가 0이면 empty가 아닌 것을 확인하고 꺼내야 하므로 P(not_empty)를 수행하여 not empty 여부를 기다린다. 내부 Counter가 하나의 buffer 공간만 있다고 하면(Buffer size -1)은 V(not_full)을 통해서 아직 Full은 아니라고 알려준다.  
조금 복잡하지만, 천천히 생각해 보면 이런 방식으로도 동작할 수 있음을 알 수 있다.
앞서 이야기한 방법들은 특정 스레드가 어떤 상태를 기다리면서 아무것도 하지 않다. 이는 낭비일 수 있다. 이렇게 특정 스레드의 동작을 막지 않고, 계속 진행하는 방식을 Non-blocking synchronization이라 한다. 이와 같은 방식으로 위의 예제를 다시 생각해 보자. Producer가 저장하는 위치(wptr)와 Consumer가 저장하는 위치(rptr)를 공유 변수로 지정해 보자. Producer는 buffer write를 수행하면서 wptr 값을 변경할 것이고, Consumer는 buffer read를 수행하면서 rptr 값을 변경할 것이다. 각각 Producer와 Consumer가  각 위치를 확인해서 wptr/rptr를 올바르게 업데이트를 한다고 생각해 보자. 각 위치는 공유 변수이기 때문에 서로 다른 값을 가질 수 있다. 케이스를 구분해서 살펴보면 아래와 같다. wptr의 경우, 0부터 3까지 숫자를 가질 수 있다. Producer가 3번의 write를 수행했지만, 1이라는 값을 읽어 오더라도 Consumer는 1개의 데이터가 있음을 알고 읽어 올 뿐 오동작하지는 않는다. 즉 쓰지 않았는 데, 쓰였다고 생각하는 경우는 없다는 것이다.  
wptr : 0 -> 1 -> 2 -> 3
rptr : 0 -> 1 -> 2 -> 3
반대 상황도 마찬가지이다. consumer가 3번의 read를 수행하여 buffer 자리가 3개가 남았지만, producer가 1이라는 값을 읽어 오더라도 Producer는 1개의 데이터를 더 쓸 수 있다고 생각할 뿐 오동작을 하지 않는다. 즉, 읽어 오지 않았는데, 읽었다고 생각하는 경우는 없다는 것이다.
이렇듯 non-blocking synchronization을 사용하면, 데드락도 없으며 priority inversion도 없다. 그리고 스레드 간의 switching, page faults(스레드가 멈출 때,  OS는 blocked state로 보내고 이와 관련된 메모리, 주소 테이블들을 클리어한다) 그리고 cache misses(마찬가지로 데이터도 클리어)와 같은 성능 하락에도 영향이 적다.
병렬화를 수행할 때 고려해야 할 사항이 있다. Amdahl의 법칙으로 얼마나 많은 병렬성을 가지고 있고, 이로 인하여 전체적인 성능 향상이 얼마나 되는 지를 파악해야 한다. 결국 순차 실행을 수행할 수밖에 없는 부분에서 Speed이 결정된다.
다음은 Locality이다. 병렬로 수행되더라도 가능하면 Cache를 잘 사용할 수 있도록 로컬 데이터를 이용하는 것이 좋다. 스레드나 프로세스 간에 데이터 이동에는 시간이 오래 걸린다.
그다음에는 Load balancing이다. 여러 스레드를 사용해서 진행하더라도 특정 스레드에만 연산이 집중되어 있는 경우, 해당 스레드로 인하여 전체 실행 시간이 결정된다. 그러므로 최대한 균등하게 연산을 배분한 것이 좋다.
추가적으로 병렬화를 수행할 때 필요한 추가 비용이다. 스레드/프로세스를 제어하기 위한 비용, 통신 비용, 동기화 비용, 병렬화를 위한 추가적인 계산을 고려해야 한다.
확장성(Scalability)은 더 많은 프로세서가 있으면 성능이 향상됨을 말한다. 하지만 앞서 이야기한 것처럼 병렬화를 하는 데 필요한 비용이 프로세서의 수에 따라 증가하므로 달성하기 어렵다.
Strong Scaling은 해결하고자 하는 문제는 한정하고, 프로세서의 수를 증가시키면서 성능을 파악하는 것이다. Amdalh's Law에 따라 병렬화를 수행할 수 있는 부분이 많으면 프로세서의 수를 증가시키면 성능도 같이 증가한다. 그러나 어느 순간 그 증가 폭이 커지지 않는다.
Weak Scaling은 해결하고자 하는 문제도 증기 시키고, 프로세스의 수도 증가시키면서 성능을 보는 것이다. 즉 프로세서 당 workload를 일정하게 설정한다. 이는 gustafson's law에 따라 순차적으로 실행하는 Portion s가 있고, p는 병렬화 가능한 Portion, N은 프로세서의 수라고 하면 아래와 같은 수식을 따른다.
Speedup = s + p*N