[03주차] 멀티쓰레드 프로그래밍 주의사항 & 상호배제 알고리즘

 

- Data Race로 인한 오동작

 1) Data Race를 없애자 → Lock/Unlock → 성능 저하 → Data Race를 줄이자 → 알고리즘 재 작성 → 너무 어렵다

 2) Data Race를 고려한 프로그래밍을 하자 → ???

 

 

 

- 컴파일러 주의점

 : Data Race가 있는 줄 알고 있고, 실행 결과를 예측할 수 있으면 문제를 피할 수 있도록 프로그래밍 할 수 있지 않을까?

 

 아래 코드를 돌려보도록 하자.

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

void Reciver()
{
	while (false == g_ready)
		std::cout << "Recv: " << g_data << std::endl;
}

void Sender()
{
	std::this_thread::sleep_for(std::chrono::milliseconds(10));

	g_data = 999;
	g_ready = true;

}

int main()
{
	std::thread R{ Reciver };
	std::thread S{ Sender };

	R.join();
	S.join();
}

 

release 모드

 

→ 결과 값 : Ok(Debug모드), 엉터리(Release 모드), why??? 

→ 컴파일러 사기(변수 g_ready를 매 반복문마다 확인하지 않음 & 최적화 한다고 순서를 바꿔버림). 얘를 피하려면?

 1) lock/unlock을 사용한다.
 2) volatile을 사용하면 된다. → 얘만 쓰면 해결 안됨
 • 반드시 메모리를 읽고 쓴다.
 • 변수를 레지스터에 할당하지 않는다.
 • 읽고 쓰는 순서를 지킨다.

→ 어셈블리를 모르면 VS의 사기를 알 수 없다.

 

→ Lock을 사용해보자

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

void Reciver()
{
	srm.lock();
	while (false == g_ready) {
		srm.unlock();
		srm.lock();
	}
	std::cout << "Recv: " << g_data << std::endl;
	srm.unlock();
}

void Sender()
{
	std::this_thread::sleep_for(std::chrono::milliseconds(10));

	srm.lock();
	g_data = 999;
	g_ready = true;
	srm.unlock();
}

int main()
{
	std::thread R{ Reciver };
	std::thread S{ Sender };

	R.join();
	S.join();
}

 

 → 정상적인 값이 나온다

 

 

 → volatile을 적용함에도 이상한 값이 나올 수 있음. 대체 왜? : 어셈블리에서 확인해도 모르겠음.

 

 

 

- volatile 사용법 (고생이다...)

 : volatile int* a; → a* = 1; (volatile 적용, 프로그램 그대로 컴파일)  a = b; (컴파일 최적화 대상)

 : 포인터가 가리키는 데이터는 최적화하지 않고 그대로 컴파일 되나, 포인터 자체 값의 변경은 포함 대상 아님 

volatile int* a

 

 

 : int* volatile a; → a* = 1; (컴파일 최적화 대상)  a = b; (volatile 적용, 프로그램 그대로 컴파일)

 : 포인터 자체(가리키는 주소 값)를 변경하는 모든 작접에 최적화하지 않으나, 포인터가 가리키는 값은 최적화 대상

int* volatile a

 

 

 : 여러 개의 쓰레드가 공유하는 변수는 volatile을 사용해야 하는데, 이때 위치를 제대로 써줘야 한다.

 : volatile을 사용하면 컴파일러는 프로그래머가 지시한 대로 메모리에 접근함 (없으면 컴파일러는 싱글쓰레드 기준으로 최적화)

현재는 skip하나, CPU는 volatile을 모른다

(추측상 어셈블리 레벨에서 volatile 키워드의 존재를 인식하지 않는다는 것이지 않을까....)

 

 

 

- CPU 주의점 (상호배제 구현, 메모리 일관성 문제)

 : 상호배제(mutual exclusion) - 하나의 자원을 여러 스레드에서 동시에 사용해서 생기는 경우, 공유 자원을 업데이트 하는 부분은 한 번에 하나의 쓰레드만 실행할 수 있도록 함

 : 임계영역(Critical Section) - 프로그램 중 상호배제로 보호 받고 있는 구간, 오직 하나의 쓰레드만 실행 가능

 : 다른 쓰레드가 Lock을 통과했고 Unlock을 하기 전 → Unlock을 할 때까지 프로그램의 실행 대기 (멈춤)

 

1) 피터슨 알고리즘

 : 2개의 쓰레드 사이의 Lock과 Unlock을 구현하는 알고리즘

 : 매개변수로 쓰레드 ID 전달 받으며 값은 0과 1이라고 가정.

volatile int victim = 0;
volatile bool flag[2] = { false, false };
int sum;
std::mutex m1;

void Lock(int myID)
{
	int other = 1 - myID;
	flag[myID] = true;
	std::atomic_thread_fence(std::memory_order_seq_cst);
	victim = myID;
	while (flag[other] && victim == myID) {}
}

void Unlock(int myID)
{
	flag[myID] = false;
}

void thread_work(int thid)
{
	for (auto i = 0; i < 25000000; ++i) {
		Lock(thid);
		sum = sum + 2;
		Unlock(thid);
	}
}

int main()
{
	std::thread t1{ thread_work, 0 };
	std::thread t2{ thread_work, 1 };

	t1.join();
	t2.join();

	std::cout << "sum = " << sum << std::endl;
}

 

 

 : volatile로 선언 → 매 반복문마다 변수를 확인할 수 있게 함 & std::atomic_thread_fence(std::memory_order_seq_cst)를 사용하여 CPU가 순서를 바꾸는 것(Out-of-Other)을 막음

 : Out-of-other - CPU가 최적화를 통해 서로 의존성이 없다 생각하면 마음대로 바꾸는 현상

 

피터슨 알고리즘

 

 : 결과 → 빈번한 메모리 참조로 인한 성능 문제 & 실제 컴퓨터에서의 오동작(오락가락...) (다음 장에서 상세히 다룸)

 : 해결책 → mutex 사용 - 편리한 기능 제공하나 오버헤드로 인한 성능 문제 발생

 

 

 2) 빵집 알고리즘 ( 과제 1 )

 : N개의 쓰레드에서의 동기화 구현

constexpr int MAX = 8;

volatile int sum = 0;
volatile int label[MAX];
volatile bool flag[MAX];

mutex mtx;

void Thread_bakery_lock(int id, const int num_thread) {
	// flag = true이면 다른 스레드 접근 X
    flag[id] = true;
    // 현재 스레드의 label 설정, 가장 큰 값에 + 1 한 값으로 설정해 우선 순위 높임
    label[id] = 1 + *max_element(label, label + num_thread);
    // flag = false, 다른 스레드 접근 가능
    flag[id] = false;

    for (int other = 0; other < num_thread; ++other) {  // 스레드에 대해 반복
        while (flag[other]) {}  // 다른 스레드의 flag가 true인 동안 대기
        // 다른 스레드의 label이 0이 아니고, 다른 스레드의 label이 현재 스레드의 label보다 작거나 같은 경우
        // 또는 두 label이 같은 경우 다른 스레드의 id가 더 작은 경우에 대기 ( 우선 순위 높은 것부터 진입 )
        while (label[other] != 0 && (label[other] < label[id] || (label[other] == label[id] && other < id))) {}
    }
}

void Thread_bakery_unLock(int id) {
	// 락 해제
    label[id] = 0;
}

void Thread_work_bakery(int id, const int num_threads) {
    for (auto i = 0; i < 50000000 / num_threads; ++i) {
        Thread_bakery_lock(id, num_threads);
        sum += 2;
        Thread_bakery_unLock(id);
    }
}

void Thread_work_mutex(const int num_threads) {
    for (auto i = 0; i < 50000000 / num_threads; ++i) {
        mtx.lock();
        sum += 2;
        mtx.unlock();
    }
}

void Thread_work_noLock(const int num_threads) {
    for (auto i = 0; i < 50000000 / num_threads; ++i) {
        sum += 2;
    }
}

int main() {
    vector<int> num_threads_list = { 1, 2, 4, 8 };

    // Bakery 사용
    cout << ">> Bakery Algorithm" << endl;
    for (int num_threads : num_threads_list) {
        sum = 0;
        auto start_t = high_resolution_clock::now();
        vector<thread> threads;
        for (int i = 0; i < num_threads; ++i)
            threads.emplace_back(Thread_work_bakery, i, num_threads);
        for (auto& th : threads)
            th.join();
        auto exec_t = high_resolution_clock::now() - start_t;
        auto ms = duration_cast<milliseconds>(exec_t).count();

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

    // Mutex 사용
    cout << ">> Mutex 사용" << endl;
    for (int num_threads : num_threads_list) {
        sum = 0;
        auto start_t = high_resolution_clock::now();
        vector<thread> threads;
        for (int i = 0; i < num_threads; ++i)
            threads.emplace_back(Thread_work_mutex, num_threads);
        for (auto& th : threads)
            th.join();
        auto exec_t = high_resolution_clock::now() - start_t;
        auto ms = duration_cast<milliseconds>(exec_t).count();

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

    // No Lock
    cout << ">> No Lock" << endl;
    for (int num_threads : num_threads_list) {
        sum = 0;
        auto start_t = high_resolution_clock::now();
        vector<thread> threads;
        for (int i = 0; i < num_threads; ++i)
            threads.emplace_back(Thread_work_noLock, num_threads);
        for (auto& th : threads)
            th.join();
        auto exec_t = high_resolution_clock::now() - start_t;
        auto ms = duration_cast<milliseconds>(exec_t).count();

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