Multi Thread 공부 7일차 (Atomic)

21 Jun 2021

Reading time ~6 minutes

부끄럽게도 Non-Blocking 알고리즘을 하기 전에 Atomic을 공부를 안했다 허헣

메모리 일관성 문제

멀티스레드에서의 공유 메모리
- 다른 코어에서 보았을 때 업데이트 순서가 틀릴 수 있다.
- 메모리의 내용이 한 순간에 업데이트되지 않을 때도 있다.
일반적인 프로그래밍 방식으로는 멀티 스레드에서 안정적으로 돌아가는 프로그램을 만들 수 없다.

지금까지 나왔던 멀티스레드 프로그래밍을 하면 안되는 이유가 3개가 있었다.

컴파일러 최적화 문제 - C언어가 멀티스레드용 언어가 아니기 때문에 최적화를 하면서 우리 생각대로 컴파일을 하지 않았다. 그래서 Volatile을 사용해서 해결했다.
CPU - out of order / write buffer 문제 - CPU의 속도를 높이기 위한 이런 유용한 기법이 있어서 지금의 속도가 나오는 것이다. 그런데 이런 기법들이 멀티스레드르를 생각 안 하고 싱글코어 시절에 나온 기법이라는 것이 문제다. 멀티코어를 사용하는 멀티스레드에서 이런 기법을 사용하면 읽고 쓰는 순서가 엉망이 된다. 그래서 atomic_thread_fence라는 c++11의 기능을 써서 out of order write buffer 실행을 막아야 한다. 기능을 끄는 게 아니라, 명령어 앞 뒤로 실행 순서를 절대로 바꾸지 말라는 명령을 하는 것이다.
캐시 문제 - 캐시는 머티코어를 생각하지 않고 만든 것이다. 아무 생각없이 했다가는 멀티코어에서 데이터가 엉망이 된다. 그래서 인텔에서는 멀티코어를 만들 때 캐시에 여러 부가 장치를 덧붙였다. MESI같은 알 필요 없는 프로토콜로 캐시가 제대로 동작하게 했지만, 캐시라인에 걸치게 되면 결과가 중간값이 나오는 현상이 일어난다. 완전하지 않기 때문이다. 이걸 막는 방법은 조심하는 방법밖에 없다. 포인터를 쓸 때 조심하고, PRAGMA PACK 을 쓸때 조심해야 한다.

이 문제들을 피하면 완벽하게 할 수 있다. 하지만 volatile을 사용하면 느리고, cpu눈치는 항상 봐야하고 atomic_thread_fence이것도 느려지고, 캐시는 조심해서 2번 접근할 때 1번한면 성능은 좋아지만, 프로그래밍 난이도가 어려워진다.

대책

꼭 필요한 곳에 mfence사용
공유 변수 대신 atomic한 자료구조 사용

인텔은 아래 사항들을 엉키지 않도록 CPU를 만들었다(잠깐 나 AMD인데….)

메모리에 대한 쓰기는 언젠가는 완료된다.
- 메모리에 썼다. 그럼 언제 어떤 순서로 들어가는지는 정해지지 않지만, 언젠가는 반드시 들어간다.
자기 자신의 프로그램 순서는 지켜진다.
- 내가 섰으면 그 데이터는 반드시 읽힌다. 내가 봤을 때 내가 읽고 쓴 건 항상 올바르게 보인다.
캐시 일관성은 지켜진다.
- 메모리에 어떤 데이터를 쓰면 옛날 데이터는 지워진다.
캐시라인의 내부의 쓰기는 중간 값을 만들지 않는다.
- 캐시라인에 걸쳐지지만 않으면 -1을 쓰면 -1이 써지고 다른 값은 써지지 않는다.

허허 이 내용이 지켜진다 해도 어렵다 ㅠㅠ

Atomic

접근(메모리는 read, write)의 절대 순서가 모든 스레드에서 지켜지는 자료구조
프로그래머가 필요로 하는 자료구조
싱글코어에서는 모든 메모리가 atomic memory이다.

지금까지 싱글스레드 프로그램에서는 모든 명령어가 atomic 명령엉기 때문에 쓰면 서지고 읽으면 최근 값이 읽혔다. 하 지 만! 멀티 스레드에 오면서 이 atomic 이라는 개념이 중요해졌다. atomic메모리는 읽고 쓰는 순서가 모든 스레드에서 똑같은 순서로 보이는 메모리가 atomic메모리이다.

구현하는 방법은 mutex를 쓰면 atomic이다. fence를 써도 atomic이다. 하지만 이것들을 안써도 구현하는 방법이 있다. 이건 대학원 내용이므로.. ㅠㅠ

그래도 C++에서 atomic메모리가 구현되어 있다.

C++의 Atomic

#include <atomic>

atomic<int> a;
a.store(3);
int d = a.load();

SW로 구현 할 수도 있지만, 오버헤드가 커서 HW적인 방법으로 구현된다. A라는 int를 쓰고 싶은데 읽고 쓰는 순서를 cpu가 바꾸면 안 된다. 순서대로 읽고 쓰게 만들어야 겠다 하면 이렇게 하면 된다.

atomic이라고 하는 것과 타입을 넣어주면 순서대로 값이 넣어진다.

#include <atomic>
#include <memory>
#include <iostream>

using namespace std;

int main()
{
    atomic<int> a,b,l;
    int p;

    a.store(1, memory_order_release);
    b.store(2, memory_order_release);
    int c = a.load(memory_order_acquire);
    c = a.load(memory_order_seq_cst);
    b.store(3, memory_order_seq_cst);
}

이번에는 변수 말고 뭑가 많다.

memory_order_seq_cst 이게 atomic의 기본이다. 이걸 사용하면 atomic하게 된다.

Atomic

C++11에서의 Atomic 메모리 종류
- csq_cst : Sequential Consistency
- relexed : Relexed Consistency
- acquire / release : Release Consistency
다른 Consistency
- Quiescent Consistency
- Sequential Consistency
- Linearization 우리는 csq_cst 이걸 써야 하고 이게 기본이다.
atomic , atomic 사용해서 Peterson알고리즘 구현
그냥 구현했을 때, _asm mfence를 넣었을때 속도 비교

#include <iostream>
#include <thread>
#include <mutex>
#include <chrono>
#include <vector>
#include <atomic>

#define MAX 50000000

using namespace std;
using namespace std::chrono;

// 피터슨
volatile int sum;

atomic<int> victim = 0;
atomic<bool> flag[8] = { false };

void lock(int id)
{
	int order = 1 - id;
	flag[id] = true;
	victim = id;
	//atomic_thread_fence(memory_order_seq_cst);
	while ((flag[order] == true && victim == id));
}

void unlock(int id)
{
	flag[id] = false;
}

void Thread(int thread_count, int id)
{
	for (int i = 0; i < MAX / thread_count; i++)
	{
		lock(id);
		sum += 2;
		unlock(id);
	}
}

int main()
{
	for (int i = 1; i <= 8; i *= 2)
	{
		sum = 0;

		vector<thread> threads(i);
		steady_clock::time_point start_time = high_resolution_clock::now();

		for (int j = 0; j < i; j++)
		{
			threads[j] = thread{ Thread, i, j };
		}

		for (int j = 0; j < threads.size(); j++)
		{
			threads[j].join();
		}

		steady_clock::time_point end_time = high_resolution_clock::now();
		auto time = end_time - start_time;

		int result_time = duration_cast<milliseconds>(time).count();
		cout << "스레드 갯수 : " << i << endl;
		cout << "Sum : " << sum << endl;
		cout << "걸린 시간 : " << result_time << endl << "\n";
	}
}

스레드 갯수 : 1
Sum : 100000000
걸린 시간 : 2672

스레드 갯수 : 2
Sum : 99864274
걸린 시간 : 2467

atomic_thread_fence 사용

스레드 갯수 : 1
Sum : 100000000
걸린 시간 : 2756

스레드 갯수 : 2
Sum : 100000000
걸린 시간 : 3889

atomic 사용

atomic을 산언하면 flag를 읽을 때, 쓸 때마다 계속 스톨이 일어난다. 원래 atomic_thread_fence 했을때 루프때마다 한번 스톨이 생겼지만 flag에서 한버느 victim에서 한번 while에서 flag에서 한번 victim에서 한번 해서 총 네 번의 스톨로 늘어났다.

따라서 atomic을 너무 많이 사용하는게 더 느려지게 된다.

그래서 이제 atomic을 사용하면 컴파일러랑 cpu의 문제는 해결이 된다. 하지만 캐시 문제는 해결해주지 않는다. aomic한 int가 캐시라인에 걸쳐져 있으면 큰일난다. atomic한 int에 포인터를 했을 때 이런일이 많이 생긴다. 조심하자.

Atomic한 메모리만 있으면 되는가??
- NO 멈춰!!!!!!!
- 실제 상용 프로그램을 int, long, float 같은 기본 data type만으로 작성할 수 있는가?
- 실제 프로그매은 기본 data type을 사용하여 다양한 자료구조를 구축하여 사용한다.
  - queue, stack, binary tree, vector

이렇게 보고 atomic을 사용하면 컴파일이 안된다. 복잡한 자료구조는 atomic으로 못한다.

문제
- Atomic Memory를 사용해서 만든 자료구조는 atomic한가?
  - 항상 YES는 아니다.
- 효율적인 atomic자료구조가 필요하다.
  - 일반 자료구조에 lock을 사용하면
    - 느리다.
  - stl
    - 충돌!! 멈춰!!
  - 위에 두개를 합하변
    - 느리다.

원래 atomic한 자료구조가 필요하면 mutex를 쓰면 된다. 하지만 효율적인 atomic자료구조가 필요하다면 mutex를 쓰면 안된다. 그래서 나온게 non-blocking 알고리즘이다.

효율적인 구현
- lock이 없는 구현
  - 성능 저하의 주범이으로 없어야 한다.
    - Overhead
    - Critical Section
    - Priority Inversion
    - Convoying
- lock이 없다고 성능저하가 없을까?
  - 다른 스레드가 완료할때 까지 기다린다
    - 성능저하
  - 상대방 스레드의 행동에 의존적이지 않는 구현 방식이 필요하다.

일단 가장 중요하게 lock이 없어야 한다. 이게 말이 쉽지 진짜 제거 하려면 엄청난 문제들이 생겨난다.

그럼 mutex를 사용하지 않고 fence 나 volatile을 써야한다. 하지만 이것들을 사용해도 성능 저하가 있었다.

많은 사람들의 연구 결과에 따르면, mutex의 유무가 문제가 아니고, 프로그램 자체의 문제다. 옆의 스레드에서 뭘 해줄때까지 기다리는 프로그램이 있다고 하면 위 단점이 그대로 사라나기 때문에 성능 개선을 얻기 힘들다. 뭘 하든 다른 스레드를 조금이라도 기다리면 성능 저하가 일아넌다.

Blocking
- 다른 스레드의 진행상태에 따라 진행ㅇ ㅣ막힐 수 있다.
- 멀티스레드의 bottle neck이 생긴다.
- lock을 사용하면 블로킹
Non-Blocking
- 다른 스레드가 어떠한 일을 하던 상관없이 진행
  - 공유 메모리 읽기/쓰기, Atomic operation
Non-Bloking의 등급
- 무대기(wait-free)
  - 모든 메서드가 정해진 유한한 단계에 실행을 끝마침
  - 멈춤 없는 프로그램 진행
- 무잠금(lock-free)
  - 항상 적어도 한 개의 메서드가 유한한 단계에 실행을 끝마침
  - 무대기이면 무잠금이다.
  - 기아상태를 유발하기도 한다.
  - 성능을 위해서 무대기 대신 무잠금을 선택하기도 한다.

모든 메서드가 정해진 시간에 끝나는게 무대기로 가장 좋은 알고리즘이다.

그 다음에 무잠금으로 정해진 시간에 끝나는게 아니다. 같은 스레드가 같은 데이터를 돌린다.

논 블로킹 프로그램은 락의 단점을 없앤 프로그래밍 기법이다. 락을 사용하지 않아야 하고 사용하지 않는다고 해도 논블로킹이 되는게 아니다.

논블로킹은 atomic한 알고리즘이다. 효율적이게 멀티스레드 프로그램을 짜고 싶으면 논블로킹을 사용해야 한다.

Multi Thread