[05주차] 동기화 연산 & CAS

 

- Lock-free 자료구조

 : 여러 개의 쓰레드에서 동시에 호출했을 때에도 정해진 단위 시간마다 적어도 한 개의 호출이 완료되는 알고리즘

 : Non-blocking이 보장되어야 함

 : 알고리즘 내에 Lock이 있으면 당연히 Lock-free X, Lock이 없다고 해도 무조건 Lock-free인 것은 아님

 : Lock이 존재하는 경우 다른 쓰레드를 실행할 수 없어 싱글 쓰레드와 다를 바가 없음

 

 

 

 

 → wait-free를 유지하며, 메모리로 Atomic Memory를 만들 수 있는 알고리즘 존재?

 : 존재, 이 강의에서 생략.

 

 → wait-free를 유지하며, 기존 씽글 스레드 자료구조도 Atomic Memory를 사용해 멀티쓰레드 자료구조로 변환 가능?

 : 불가능하다. 나중에 자세히 다룸.

 : Atomic memory를 사용만해서는 논블로킹 자료구조를 만들 수 없음

 

 → wait-free를 유지하며, 일반적인 자료구조를 멀티쓰레드 자료구조로 변환하기 위해 Atomic-memory말고 무엇이 더
필요?

 : CompareAndSet() 연산이면 충분함

 

 

 

- CompareAndSet

 : 동기화 연산의 일종

 

 → 동기화 연산

  : 공유 메모리에 대한 연산 (한 word에 대한 연산 - 읽고 쓰기 등)

  : 다른 쓰레드와 통신하기 위한 기본 기능

  : CPU의 명령어로 구현 + Wait-free로 구현되어야 함 (그렇지 않으면 Non-Blocking 알고리즘에서 사용할 수 없음)

 

 • Load (wait-free)
 • Store (wait-free)
 • Lock/Unlock (blocking)
 • atomic_thread_fence (wait-free)
 • +=, fetch_and_add (wait-free)

 

 + CAS(Compare And Set, wait-free) 추가 필요

 : bool 메모리::CAS(expected, update)

 : 메모리의 값이 exptected면 update로 바꾸고 true, 만약 expected가 아니면 false를 return.

bool 메모리::CAS(expected, update)
{
 	if (메모리.value == expected) {
 	메모리.value = update; 
 	return true;
 	} else return false;
}

 

 : atomic의 load/store로 구현할 수 없음 - wait-free 조건 때문

 

→ CAS는 wait-free를 유지하며 일반적인 자료구조를 멀티쓰레드 자료구조로 어떻게 변환하는가? 

 : 모든 기존 자료구조를 wait-free multithread로 변환해주는 알고리즘이 존재

 : 현실 ) 비효율적

 : 효율적인 변환은 상당한 노력을 필요로 함

 

 

• 실제 CAS의 구현

 : atomic_compare_and_set 없고, atomic_compare_exchange를 대신 사용

 : 논블로킹 자료구조를 만드는 데 필수 연산

bool CAS(atomic_int *addr, int expected, int new_val)
{
 	return atomic_compare_exchange_strong(addr, &expected, new_val);
}

bool CAS(volatile int *addr, int expected, int new_val)
{
 	return atomic_compare_exchange_strong(reinterpret_cast<volatile atomic_int *>(addr),
    					&expected, new_val);
}

 

 

[ CAS를 이용한 lock과 unlock구현, 1억 만들기 프로그램 ]

volatile int X;
volatile int sum;
bool g_ready = false;
int g_data = 0;
std::mutex srm;

bool CAS(volatile int* addr, int expected, int new_value)
{
    return std::atomic_compare_exchange_strong(reinterpret_cast<volatile std::atomic_int*>(addr), &expected, new_value);
}

void cas_lock()
{
    while (false == CAS(&X, 0, 1));
}

// X = 1 누가 lock을 얻었다. 0이면 아무도 lock을 얻지 않았다.
void cas_unlock()
{
    X = 0;
}


void thread_func(int num_threads, int th_id)
{
	for (int i = 0; i < 500'0000 / num_threads; ++i){
		cas_lock();
		sum += 2;
		cas_unlock();
	}
}

int main()
{
	for (int num_threads = 1; num_threads <= 16; num_threads *= 2) {
		sum = 0;
		auto start_t = std::chrono::high_resolution_clock::now();
		std::vector<std::thread> threads;
		for (int i = 0; i < num_threads; ++i)
			threads.emplace_back(thread_func, num_threads, i);

		for (auto& th : threads)
			th.join();

		auto exec_t = std::chrono::high_resolution_clock::now() - start_t;
		auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(exec_t).count();

		std::cout << "Thread : " << num_threads << ", sum = " << sum << ", Time = " << ms << "ms" << std::endl;
	}
}

 

 

 

 : CAS를 실행할 때 오직 하나의 쓰레드에서만 true를 반환하면 됨

 : 쓰레드가 늘어날 수록 성능은 떨어진다, 왜?

 1) CAS를 실패했을 경우 계속해서 CAS 함 (mutex보다는 아니지만, 오버헤드가 존재한다)

 2) 쓰레드가 늘어나는 만큼 계속해서 CAS를 진행한다