SHPC 07 - Synchronization

Motivation

• 스레드 간 또는 프로세스 간 실행되는 순서를 정하기 위함
• 상호배제(Mutual Exclusion)를 달성하기 위해

Barrier

• Barrier가 있는 지점에 도달한 스레드는 실행을 중단하고 다른 모든 스레드가 같은 배리어에 도달하기를 기다린 다음 실행을 계속함
  • 내부적으로 thread count라는 공유변수가 있고, 호출될 때마다 +1을 하는 식으로 몇개가 배리어에 도달했는지 확인하는 방식으로 구현
  • 개인적으로 찾아봤는데 thread count에도 race가 발생할 수 있으므로 lock을 잘 걸어줘야 한다고
• 같은 함수(코드)를 동시에 실행할 때 흔하게 이용됨
  • SPMD

Note

include <pthread.h> #include <stdio.h> #define NUM_THREADS 4

pthread_mutex_t mutex; pthread_cond_t cond; int count = 0;

void barrier() { pthread_mutex_lock(&mutex); count++;

if (count == NUM_THREADS) { count = 0; // 다음 Barrier에서 사용할 수 있도록 초기화 pthread_cond_broadcast(&cond); // 모든 대기 중인 스레드에게 condition 만족됨을 알림 } else { pthread_cond_wait(&cond, &mutex); // 뮤텍스를 풀고 condition 만족될 때까지 대기 }

pthread_mutex_unlock(&mutex); }

Data Race

• 두 스레드가 변수 balance를 공유
• R1, R2는 각 스레드에 대해 로컬 변수
• 실행 순서가 어떻게 나올지 모른다.
  • 1200 or 1400

Condition

• 두 개 이상의 스레드가 같은 메모리 위치를 접근
• 하나의 쓰레드가 쓰기를 하고
• 그 위치가 동기화에 의해 보호되지 않을 때
  • mutex나 atomic 연산, 혹은 메모리 배리어와 같은 명시적인 동기화 메커니즘이 없을 때
  • 비지웨이팅으로는 만족되지 않는다
  • std::atomic / std::atomic의 memory_order

특징

• 엑세스 순서가 비결정적
  • 실행될 때마다 다른 결과가 출력됨
• 어떤 데이터 레이스는 의도적으로 사용됨
  • 아이러니하게도 동기화를 위해
  • e.g. 비지 웨이트 동기화, Lock-free 알고리즘
• 보통의 경우 버그이기 때문에 되도록이면 없애주는 게 좋다
• While a data race doesn’t always violate thread safety, it introduces a significant risk

Busy Wait Synchronization

• Data race의 condition이 만족된다
• done 변수의 경우: Thread 0과 Thread 1에서 접근하며, Thread 0에서 쓰기를 함
• data 변수의 경우: Thread 0과 Thread 1에서 접근하며, Thread 0에서 쓰기를 함

Thread Safety

• 두 개 이상의 스레드가 어떤 함수를 동시에 호출했을 때 그 함수가 항상 올바르게 동작하면 그 함수를 Thread Safe 하다고 함
  • Thread-safe library

Atomicity

• 한 묶음의 연산이 아토믹하다 == 모든 연산이 수행되거나 하나도 수행되지 않는 것 (all or nothing)
  • 부분적인 수행으로 인한 결과를 볼 수 없다
  • 중간에 다른 쓰레드의 연산이 끼어들지 않음

Mutual Exclusion

• 항상 많아야 하나의 스레드만 어떤 코드부분을 실행할 수 있을 때, 그 코드부분을 상호배제(mutual exclusion)적으로 실행된다고 함
• 상호배제를 통해 atomicity를 보장할 수 있음
• 어떤 코드부분을 동기화로 보호하여 아토믹하게 실행할 때, 그 코드부분을 critical section이라고 함
  • Lock, semaphore 등으로 달성

Lock

• Atomicity를 보장하기 위해 사용
• 두 개의 상태: locked / unlocked
• 두 개의 함수: lock(L) / unlock(L)
  • 하나의 스레드가 록을 걸고자 할 때 먼저 록이 걸려있는지 확인
  • 록이 걸려있면 록을 건 스레드가 록을 풀어주기를 기다린 후 록을 검
  • e.g. 화장실 갈때 열쇠 가져가는 것. 열쇠가 없으면 열쇠를 가진 사람이 돌아오기를 기다리고 가져가서 화장실을 씀
• 스레드를 이용한 병렬 프로그램의 동기화에 이용

Spinlocks

• Lock을 기다리는 쓰레드가 CPU를 놓지 않고 lock을 계속 확인하면서 풀릴 때까지 기다리는 것
  • Context switching이 일어나지 않기 때문에 짧은 락에 적합함
    • 짧게 기다리는 데에 context switching을 하고 다시 돌아오는 것, 즉 go down and up 은 비싸다
  • 단, CPU 사이클을 낭비하게 됨
  • Uniprocessor system에서는 사용할 수 없음
    • Spinlock을 사용한다는 것은 내가 루프를 도는 동안 다른 쓰레드가 나의 prerequisite을 달성시켜 줄 것을 기대하는 것. 근데 오직 하나의 코어를 님이 잡고 있으니, 그런 일은 절대 일어나지 않음
    • 물론 CPU 스케쥴링에 의해 preempt 되고 나서는 가능하겠지만 아무런 이득이 없음. 그냥 스케쥴링 타임을 낭비한 것
• 더 나은 버전: Sleeplock
  • Lock을 요청하는 쓰레드를 Block하고, lock이 풀렸을 때 ready queue에 집어넣는것
  • 이건 uniprocessor system에서도 사용 가능
  • 긴 lock에 대해 CPU 시간을 절약할 수 있음
  • OS가 개입하여 오버헤드가 큼
• Test and set instruction
  • Atomic instruction
  • 메모리 location(L)을 읽고 false이면 true로 만들고, false를 리턴 / 그렇지 않으면 true를 리턴. (이미 1이 있다는 것을 의미)
  • 락이 잡혀있으면 기다리고, 아니면 락을 잡는 코드 / 락을 푸는 코드
  • Cache가 있으면 문제가 생기기 때문에, test_and_set은 항상 메모리에 접근한다
    • 메모리는 바뀌었는데 캐시는 안바뀌었을 수 있기 때문
      • e.g. 쓰레드 두개가 서로다른 private cache를 쓰고있을 때
    • 항상 메모리에 접근하면 좋겠지만 그러면 메모리 bandwidth를 잡아먹음. 따라서 아래와 같이 약간의 최적화
      • 캐시 일관성 프로토콜이 동작하고 있다고 가정한다.

Pros and Cons of Locks

• 장점
  • 이해하기 쉽고 쓰기 쉬움
• 단점
  1. 데드록
  2. Priority inversion
     • 쓰레드 스케쥴링 측면에서, 우선순위가 낮은 쓰레드가 락을 잡으면(critical section에 들어가면), 중간에 높은 쓰레드가 CPU를 잡아도 낮은 쓰레드가 락을 잡고있기 때문에 아무것도 할 수 없는 경우
     • Critical section에 들어간 쓰레드는 context switch하지 말고 끝날때까지 CPU를 주자 같은 솔루션이 존재
       • 찾아보니 Priority Inheritance라고 부르는 것 같음
       • Critical section에 들어간 쓰레드에게 임시로 높은 priority를 주는 것
  3. 비싸다 : OS 개입, 캐시 동기화 등의 이유

Semaphores

• Semaphore S는 nonnegative integer value
• P, V 라는 atomic 함수 사용
  • P(S) : S>0 이면 S를 1 감소시킴, otherwise 조건이 만족될 때까지 block됨
  • V(S) : S를 1 증가시킴. S를 기다리는 쓰레드가 있으면 걔를 깨워줌
• 세마포어를 기다리는 쓰레드는 busy waiting을 하지 않음
  • block되고 나중에 깨워주니 sleep lock이라고도 볼 수 있을 듯

Binary Semaphore vs Counting Semaphore

• Binary semaphores
  • S가 0 혹은 1, 처음에는 1로 초기화됨
• Counting(General) semaphores
  • 항상 0 이상 정수

Mutual Exclusion using Semaphores

아래는 semaphore를 이용해 공유되는 atomic counter를 구현한 예제

Producer and Consumers

• 쓰레드의 종류를 두개로 나눠볼 수 있음
  • Producer - Data element를 생성하고 consumer에게 보내는 주체
  • Consumer - Data element를 받아서 계산을 수행하는 주체

Single Producer and Single Consumer

• Circular buffer
  • Circular queue를 이용해 자원을 관리
  • Producer는 tail에 데이터를 넣고, consumer는 head에서 데이터를 뺀다
  • 큐가 가득 차면 producer는 slot이 생기기를 기다리고, 큐가 비면 consumer는 data가 생기기를 기다림
  • 즉,
    • Producer는 slot에 대해 P operation(소모), element에 대해 V operation(생산)
    • Consumer는 반대로 slot에 대해 V, element에 대해 P 아래는 공유변수 count를 추가적으로 사용해서 버퍼의 크기를 추적하는 구현. 차이가 뭔지 잘 모르겠지만 더 잘 구현된 것 같음

void producer() {
	int lcount = 0;
	while(1) {
		data = produce();
		if (lcount == N) P(not_full);
		buffer(in) = data;
		P(S);
		count = count + 1;
		lcount = count;
		V(S);
		if (lcount == 1) V(not_empty);
		in = (in + 1) mod N;
	}
}

void consumer() {
	int lcount = 0;
	while(1) {
		if(lcount == 0) P(not_empty);
		data = buffer(out);
		P(S);
		count = count - 1;
		lcount = count;
		V(S);
		if (lcount == N-1) V(not_full);
		out = (out + 1) mod N;
		consume(data);
	}
}

Non-blocking Synchronization

• 하나 이상의 쓰레드가 중단되는 것이 다른 쓰레드의 진행을 막지 않는 것
• Critical section이 클때와 작을 때 어떤 장단점이 있을까? (Coarse-grained vs Fine-grained)
  • 작을때 병렬성이 늘어나나, 자주 synchronization(락을 걸고 락을 놓는것)을 해야 해서 오버헤드가 생긴다. trade-off존재
• 장점
  • No deadlock
  • No priority inversion
  • 성능저하가 심하지 않음(빠르다)
    • Context switching 없음
    • Page faults 없음
    • Cache miss 없음

Non-blocking Single Producer and Single Consumer

• in과 out, 버퍼는 공유변수
• Producer는 in을 업데이트하고 Consumer는 out을 업데이트
• Producer는 in에 쓰기를 하고, consumer는 읽기만 함. 반대로도 성립
  • 따라서 잘못 동작할 일은 없음. 잠시 잘못 스케쥴링돼서 루프를 한바퀴 더 돌수는 있겠지만
  • 단, in과 out에 대한 읽기와 쓰기가 원자적이라고 가정함. 원자적이라는 것은 A에서 B로 바뀔 때 관측자가 A 혹은 B 값만을 얻을 수 있다는 뜻

병렬화 시 고려사항

• 프로그램에 든 병렬성의 양
  • Amdahl의 법칙
  • 순차실행을 할 수 밖에 없는 부분에 의해 Speedup이 결정됨
• 로캘리티
  • 될 수 있으면 로컬 데이터를 이용하여 계산하는 것이 좋음(캐쉬를 잘 이용하도록)
  • 스레드나 프로세스 간 데이터의 이동에 시간이 걸림
• Load balancing
  • 각 스레드 또는 프로세스가 같은 양의 일을 하도록 일을 분배하는 것이 중요
  • 전체 실행 시간은 가장 늦게 일을 끝내는 스레드나 프로세스에 의해 결정됨
• 병렬화 오버헤드
  • 스레드나 프로세스를 시작하는 비용
  • 통신 비용
  • 동기화 비용
  • 병렬화를 위한 가외의 계산

---

확장성

Strong scaling

• 문제의 크기를 고정하고 프로세서의 수를 증가시키는 평가방식
• 고정된 문제 크기에 대해 처리 시간을 얼마나 줄일 수 있는가?
  • 병렬성 평가에 사용
• Amdahl’s law와 관계가 있다
• 실제 세계에서는 문제도 linear하게 증가함
• 프로세서 사이의 communication overhead도 linear하게 증가하기 때문에 달성하기 어렵다 (Weak 보다 더 어려움)

Weak scaling

• 프로세서의 수와 동시에 문제의 사이즈도 증가시키는 방식
• 작업 부하가 커져도 처리 시간을 유지할 수 있는가?
  • 병렬처리 시스템을 평가하는데에 사용
• Gustafson’s law와 관계가 깊다
  • $speedup=s+p\times N$
  • s는 sequential part 실행시간 비율
  • p는 parallel part 실행시간 비율
  • N은 프로세서의 수
  • 문제 크기가 늘어난다는 가정
• 마찬가지로 프로세서 사이의 communication overhead 증가하긴 하지만 strong scaling보다는 낫다

---

각 동기화 방법 비교

Barrier

장점

• 간단한 구현 단점
• 먼저 끝난 쓰레드가 다른 동작을 못하고 기다리기만 해야 하므로 비효율적일 수 있음

BusyWaiting

장점

• 간단한 구현
• Waiting time이 짧은 경우 context switching 비용이 없어 효율적이다 단점
• 리오더링이 되는 경우 원하는 대로 동작하지 않을 수 있다
• Waiting time이 긴 경우 대기중에도 CPU를 계속 사용하여 비효율적이다
• Uniprocessor에서 사용될 수 없다

SpinLock

장점

• Waiting time이 짧은 경우 context switching 비용이 없어 효율적이다 단점
• Waiting time이 긴 경우 대기중에도 CPU를 계속 사용하여 비효율적이다
• Uniprocessor에서 사용될 수 없다
• 데드록이 발생 가능
• Priority inversion 발생

Sleeplock

장점

• Waiting time이 긴 경우 대기중에도 CPU 낭비가 없어 효율적
• Uniprocessor에서 사용될 수 있다 단점
• Waiting time이 짧은 경우에도 OS의 개입(context switching 비용 등)이 있어 비효율적
• 데드록이 발생 가능
• Priority inversion 발생

Semaphores

장점

• 하나 이상의 쓰레드가 데이터에 동시에 접근 가능한 경우 유용하다 (e.g. producer - consumer)
• 세마포어를 기다리는 쓰레드는 busy waiting을 하지 않으니 waiting time이 긴 경우 효율적 단점
• 구현이 조금 더 복잡함
• 데드락 발생 가능
• Priority inversion 발생 가능

Non blocking

장점

• 데드록 없음
• Priority inversion 없음
• 성능저하가 심하지 않고 빠르다 (context switching 없기 때문) 단점
• 공유자원에 대해 원자적 연산을 사용해야 함
  • 아닌 경우 data race 발생
• 충돌 발생시 재시도 비용