[04주차] 메모리 일관성

 

- CPU 주의점

 : 저번 시간 상호 배제에 이어 메모리 일관성 문제도 고려해야 함

 : 지금까지 프로그램은 공유 메모리에 대한 접근(읽기/쓰기)을 atomic하다고 가정함

 → 컴파일러가 제대로 기계어로 번역했다면

 → atomic : 메모리의 접근이 순간적으로 행해지며, 서로 겹치지 않고 실행 결과 순서가 정해지면, 모든 쓰레드에서 같은 순서로 보임

 → 그러나 PC에서의 메모리 접근은 atomic이 아님 (메모리에 쓴 순서대로 메모리의 내용이 관측되지 않음)

 

 

 : 0번 쓰레드도 false를 읽고 1번도 false를 읽음 

 : 저번 시간에 했던 피터슨 알고리즘에서 std::atomic_thread_fence(std::memory_order_seq_cst)를 제외한 경우 아래의 결과처럼 상호 배제가 깨짐

 

 → 컴파일 문제 없음. 메모리 문제. 순서대로 안읽음 (atomic하지 않다, volatile로 해결되지 않음 - CPU와 상관없음)

 → 99.995% atomic하지만, 0.005%정도는 atomic이 아님 (CPU 모델에 따라 수치는 다름)

 

atomic끼리만 순서를 맞춰주기에 자신 없음 둘다 atomic으로 해라

 

 : 메모리 접근이 atomic하지 않은 이유 → CPU 사기 

 1) Line Based Cache Sharing (라인 기반 캐시 공유) : 하나의 CPU가 메모리에 쓰기를 수행하면 다른 CPU가 동일한 캐시 라인을 가진 캐시의 내용을 무효화 할 가능성 존재

 2) Out of order (명령어 순서 변경) : 우선적으로 실행할 수 있는 것들은 미리 해버림

    메모리 접근이 순간적 X, 멀티코어에선 옆 코어의 Out of order이 관측됨

 3) write buffering (쓰기 버퍼링) 

 

 → 사기 안치면 실행 속도 느림

 → CPU는 프로그램을 순차적으로 실행하는 척만 함 (이를 도와주는 특수한 HW 존재)

 

const auto SIZE = 50000000;
volatile int x, y;
int trace_x[SIZE], trace_y[SIZE];

void ThreadFunc0()
{
	for (int i = 0; i < SIZE; i++) {
		x = i;
        // atomic_thread_fence(std::memory_oreder_seq_cst);
		trace_y[i] = y;
	}
}

void ThreadFunc1()
{
	for (int i = 0; i < SIZE; i++) {
		y = i;
        // atomic_thread_fence(std::memory_oreder_seq_cst);
		trace_x[i] = x;
	}
}

int main()
{
	std::thread t0{ ThreadFunc0 };
	std::thread t1{ ThreadFunc1 };

	t0.join();
	t1.join();

		int count = 0;
	for (int i = 0; i < SIZE; ++i)
		if (trace_x[i] == trace_x[i + 1])
			if (trace_y[trace_x[i]] == trace_y[trace_x[i] + 1]) {
				if (trace_y[trace_x[i]] != i) continue;
				count++;
			}
	cout << "Total Memory Inconsistency: " << count << endl;
}

 

 

: x, y - 쓰레드 간 공유되는 변수

 

: trace_x[SIZE], trace_y[SIZE] - 쓰레드에서 발생한 값들을 기록할 배열

: 서로 다른 쓰레드의 메모리를 읽고 쓰고 있다.

: count - 일관성 문제가 발생한 횟수를 저장할 변수

: if (trace_y[trace_x[i]] == trace_y[trace_x[i] + 1]) - 해당 값에 대응하는 trace_y 값도 같다면 count ++

: if (trace_y[trace_x[i]] != i) continue;   -   이전 인덱스와 다른 값이라면 카운트 하지 않고 다음으로 넘어감

: 주석을 풀면 결과는 0으로 나온다. atomic<int>를 사용해도 결과가 0이나 속도가 매우 저하됨.

 

 

 

- 메모리 일관성

 1) = 무모순성(Consistency) - 메모리가 순서대로 진행X,

 2) 강한 모델과 약한 모델이 있고 각각 허용되는 결과들을 제한하는 정도가 다름

 

 : 멀티쓰레드에서 공유 메모리 → 다른 코어에서 봤을 때 업데이트 순서가 틀릴 수 있으며 메모리의 내용이 한 순간에 업데이트 되지 않을 때도 존재함

 

→ 어떻게 해야 하는가? 

 1) 위의 상황을 감안하고 프로그래밍 → 너무 어렵다. 피터슨 알고리즘도 동작X

 2) 강제로 원하는 결과를 얻도록 한다 → 메모리 접근을 mutex 처리 → 성능 저하 

   혹은 atomic_thread_fence()명령어 → 찾은 위치가 완벽하다는 보장은?

 

→ 꼭 필요한 곳에 사용 atomic_thread_fence() 사용 혹은 공유 변수로 atomic한 메모리 사용

 앞 명령어들의 메모리 접근이 끝나기 전까지 뒤에 있는 명령어들의 메모리 접근을 막음

* 메모리에 대한 쓰기는 언젠가는 완료 된다.
* 자기 자신의 프로그램 실행 순서는 지켜진다.
* 캐시의 일관성은 지켜진다.
 - 한번 지워졌던 값이 다시 살아나지는 않는다.
 - 언젠가는 모든 코어가 동일한 값을 본다.
* 캐시라인 내부의 읽기/쓰기는 중간 값을 만들지 않는다.

 

 → atomic memory만 있으면 되는가? No.

 → 실제 사용 프로그램은 기본 자료형만을 갖고 개발 할 수 없음. 다양한 자료구조를 이용해야 한다.

 → atomic한 자료구조 필요 

  : 접근(메모리는 read, write)의 절대 순서가 모든 쓰레드에서 지켜지는 자료구조

 

 → atomic Memory를 사용하여 만든 자료구조가 atomic한가 ? No 

 → 일반 자료구조에 Lock (너무 느림), STL (CRASH), STL+LOCK (너무 느림)

 → Non-blocking 알고리즘이 효율적임( O() )

 

 

 

- Non-Blocking

 : 다른 쓰레드와 상관없이 진행됨 (ex. 공유메모리 읽기/쓰기 ...)

 

 : vs Blocking(블럭킹) - 다른 쓰레드 진행 상태에 따라 진행이 막힐 수 있음 (ex. Lock ...)

 : 블럭킹 알고리즘은 다음과 같은 문제가 있다.

 1) 성능 저하

 2) Priority Inversion : Lock을 공유하는 덜 중요한 작업들이 중요한 작업의 실행을 막는 현상 (Reader/Write Problem에서 자주 발생함)

 3) Convoying : Lock을 얻은 쓰레드가 스케쥴링에서 제외된 경우, lock을 기다리는 모든 쓰레드가 공회전 (코어보다 많은 수의 쓰레드를 생성했을 경우 자주 발생함 )

 

: Non-blocking  등급 : 쓰레드 사이 효율적 자료 교환을 위해서 꼭 필요

 1) 무대기 (wait-free) : 모든 메소드가 정해진 유한 단계에 실행을 마치며 멈춤 없는 프로그램을 실행함

 2) 무잠금 (lock-free) : 항상, 적어도 한 개의 메소드가 유한한 단계에 실행을 끝마침. 무대기면 무잠금이며 기아를 유발하기 도함. 성능을 위해 무대기 대신 무잠금 선택하기도 함.

 3) 제한된 무대기 : 유한하지만 쓰레드 개수에 비례한 유한일 수 있음

 4) 무간섭(obstruction-free) : 한 개를 제외한 모든 쓰레드가 멈추었을 때, 멈추지 않은 쓰레드의 메소드가 유한한 단계에 종료할 때. 충돌 중인 쓰레드를 잠깐 멈출 필요가 존재