메모리

컴퓨터에서 메모리는 CPU에게 있어 책상과 같은 역할이다. 우리가 공부를 할 때 책상에 필요한 것을 늘어놓는 것처럼 CPU도 그러하다. 우리가 손에 닿는 거리 만큼이 주소 공간이 된다. 팔이 길면 길수록 멀리 떨어질 건 잡을 수 있는 것처럼 더 많은 정보에 접근할 수 있다.

CPU는 메모리와 데이터를 주고 받을 때 버스라는 시스템을 이용한다. 이것은 도로와 같은 개념이다. 도로가 넓을 수록 교통량을 많이 수용할 수 있는 것처럼 버스의 대역폭이 클 수록 더 많은 데이터를 한꺼번에 읽을 수 있다. alignas에서 본 것처럼 정렬된 데이터는 - 즉 버스에 폭맞춤되면 전송 속도는 더 빨라진다. 추가의 패딩 바이트가 필요없기 때문이다.

https://en.wikipedia.org/wiki/System_bus#/media/File:Computer_system_bus.svg

운영체제는 어플리케이션를 실행할 때 로더를 이용해서 파일시스템에 있는 데이터를 메모리로 읽어들인다. 코드 영역, 상수 영역, 데이터 영역으로 나뉜다. 코드 영역에 대한 임의의 접근은 예외를 초래한다. 위험한 프로그램들은 프로그램 카운터나 스택 포인터를 조작해서 다음에 실행할 명령을 자신의 코드로 바꾼다. 이를 인젝션이라 한다. 따라서 애플리케이션은 해킹에 매우 취약했다. 현대 운영체제는 각각의 프로그램을 일종의 메모리 격벽에서 실행되도록 한다. 내부에서는 상대 주소로만 메모리를 취급할 수 있고 다른 프로그램이 가진 메모리 영역에 절대 접근할 수 없다. 이런 행위는 접근 위반 예외(access violation exception)을 불러일으킨다.

 

https://blog.f-secure.com/memory-injection-like-a-boss/

메모리는 프로그램의 실행 속도에 절대적인 영향을 미친다. 보통 CPU는 무시무시하게 빠르지만 데이터를 접근하는데 있어 병목은 흔한 일이다. 이를 피하기 위해 여러 단계의 메모리가 있다. 캐쉬 메모리로 일컬어지는 L1, L2 캐시, 그리고 램 영역이 있다. CPU는 L1에 있는 데이터로만 연산할 수 있다. 이것은 캐시 히트라는 용어로 요약된다. CPU가 특정한 데이터를 이미 캐시에 있는 경우를 일컫는다. L2는 CPU 내부에 있다. L1에 원하는 내용이 없으면 L2를 조회하고, CPU는 원할 경우 빠르게 복사할 수 있다. L 캐시들은 CPU 내부에 있고 이에 복사 비용이 저렴하다. 반면 램 영역은 CPU 외부에 있고 필요할 경우 버스를 이용해서 복사해야 한다. 이 과정은 L1, L2와는 비교할 수 없게 느리다. 이는 물리적인 위치 뿐아니라 컨트롤러 조작 등의 비용이 추가로 발생하기 때문이다. 쓰기 비용은 읽기보다 비싸고 대기해야 한다. 쓰기로 인한 중단(blocking)을 피하기 위해 별도의 버퍼(write buffer)에 쓰인다. 읽기는 빠르지만 별도의 버퍼는 의미가 없으며 완료 인터럽트가 발생할 때까지 처리는 지연된다.

https://cho001.tistory.com/138

프로그램은 소프트웨어 측면에서 메모리를 스택, 힙 영역으로 분류한다. 프로그램 실행 시에 갖는 일종의 버퍼인 스택 영역은 인접한 메모리 범위를 가진다. 여기에 함수 인수, 스텁(stub), 임시 변수가 저장된다. 캐시는 특정 영역을 한꺼번에 읽어들이므로 스택 영역은 보통 캐시에 포함된다. 따라서 이곳에 있는 메모리를 접근하도록 하면 속도가 향상된다. 힙 영역은 프로그램이 가질 수 있는 최대 메모리의 어느 곳이라도 주소로 지정할 수 있다. 따라서 대량의 메모리를 접근하는데 유용하지만 캐시는 비싸고 따라서 용량이 작아 모두 담을 수 없다. 게다가 페이지 폴트, 페이지 스왑으로 인한 OS 작업이 포함될 수 있고 무엇보다 캐시 미스를 자주 불러일으킨다. 왜냐하면 힙 이곳 저곳에 있는 데이터는 한꺼번에 캐시에 담을 수 없고 접근 시마다 캐시에 담는 행위를 반복해야 한다. 따라서 느리다. 이 비용은 꽤 크기 때문에 최적의 자료구조를 사용한다고 해도 마찬가지이다. stl의 컨테이너는 모두 힙 영역을 쓰기 때문에 스택 영역에 설정한 배열을 스캔하는 것이 빠른 경우가 흔하다. 물론 stl 설계자는 메모리 할당자를 외부에서 설정할 수 있게 했다. 이를 통해 스택 영역에서 할당 받을 수도 있다. 허나 스택이 가질 수 있는 메모리는 보통 작다. 게다가 넘칠 경우(stack overflow) 예외가 발생하고 이것은 표준 C++ 차원에서 해결할 수 없다.

https://stackoverflow.com/questions/32418750/stack-and-heap-locations-in-ram

최근에는 병렬 프로그래밍의 적극적인 도입으로 메모리 관리는 더욱 중요하다. 이는 멀티코어라는 하드웨어 특성 때문이다. CPU 클록 향상이 한계에 부딪힌 지금 코어 증가로 성능 향상의 방향이 바뀌었다. 이는 병렬 프로그래밍의 중요성이 더해졌음을 의미한다. 이로 인해 같은 메모리 주소를 여러 코어/스레드가 접근할 수 있어 적절히 관리해야 한다. 이를 피하는 쉬운 방법은 잠금으로 대표되는 동기화 처리이다. 허나 병렬 처리를 방해한다. 잠금이 풀릴 동안 대기해야 하기 때문이다. 따라서 이에 완화시킬 방법이 마련되어 있다. 먼저 알아둘 점은 CPU가 프로그래머가 작성한 코드를 순차적으로 실행하지 않는다는 것이다. 더 빠른 실행을 위해서 코드 위치를 재배치한다. 예를 들어 두 명령의 의존 관계가 없을 경우 CPU는 이들의 처리 순서를 임의로 바꿀 수 있다. 여기서 각각의 스레드가 같은 코드를 동시에 실행될 수 있음을 염두해야 한다. 쓰기가 있으면 필연적으로 경쟁(race)을 촉발한다. 그들의 실행 순서는 알 수 없고 잠금이 없다면 다른 스레드의 일이 마칠 때까지 기다리지 않으므로 작업이 섞이게 된다. 예를 들면 중간 결과를 쓴다는 것이 마지막으로 실행될 수 있다. 이런 것이 경주처럼 보이기 때문에 이런 용어로 표현된다.

이외에도 데드락 등의 위험성이 있지만 잠금은 사용하기 편리하여 널리 쓰인다. 허나 높은 비용이 있고, 스레드가 놀고 있는 걸 프로그래머가 참기는 어렵다. 따라서 무잠금(lock free) 프로그래밍 기법이 제시되었다. C11은 이를 위해 메모리 정렬을 위한 명령을 제공한다.  참고로 C++ 설계자는 이에 대한 경고를 수차례 날리고 있다. 이것이 극히 하드웨어 의존적이며 전문가의 영역이라는 점. 당신의 프로그램을 더 느리게 하는 걸 넘어 손상시킬 수도 있다는 것 등등. 허나 C++로 시스템 프로그래밍을 시도하지 않겠다면 뭘로 하겠는가? 그리고 전문가가 되기 위해 혼날 각오를 하자.

 

먼저 명령어가 재배치될 수 있는 경우의 수를 알아야 한다. 읽기 또는 쓰기 뿐이므로 다행히 4가지 밖에 되지 않는다.

• 읽기 - 읽기
• 읽기 - 쓰기
• 쓰기 - 읽기
• 쓰기 - 쓰기

경우의 수를 헤아리는 목적은 무엇인가? 이후 나열되는 메모리 정책들이 각각의 경우에 어떻게 행동하는지 헤아리기 위함이다. 메모리 정책은 왜 존재하는가? 우리는 동기화가 비용을 초래한다는 것을 알고 있다. 어떤 일을 마음내키는대로 하는 것과 정해진 순서를 지켜가며 하는 것과의 차이이다. 후자는 신경을 써야한다. 컴퓨터의 경우에는 자원을 써야한다. 그것이 CPU 클록이든 자성 비트의 변경이던지 마찬가지이다. 정책은 다음과 같다.

 

memory_order_relaxed

모든 종류의 명령이 섞일 수 있다. 다만 relaxed로 저장한 값들의 시간 순서는 보장된다. 그렇다고 그 값들을 순차적으로 읽을 수 있다는 의미는 아니다.  C++ 메모리 모델과 atomic 타입 연산들 슬라이드쉐어 125쪽에 아주 좋은 사례를 보여준다. 다음 코드도 참고하라.

// http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1525.htm

const int num_mailboxes = 32;
_Atomic volatile int mailbox[num_mailboxes];

void MailboxInspection(int my_id, void (*do_work)(int)) {
    for (int i = 0; i < num_mailboxes; i++) {
    	// mailbox의 적합성을 조회할 때는 순서가 중요하지 않다. 
        if (atomic_load_explicit(&mailbox[i],  memory_order_relaxed) == my_id) {
            // 명령어 재배치에 의해 do_work()가 검사문보다 위에 있을 수도 있다.
            // ...fence() 명령은 이런 일을 막아준다.
            atomic_thread_fence(memory_order_acquire); // prevent speculative reads in do_work [7.17.4.1]
            do_work(i);
        }
    }
}

memory_order_acquire

읽기 처리에 사용되며 해당 메모리 정책이 선언되면 후속되는 명령어들은 정책 선언 이전으로 배치되지 않는다. 이 명령은 memory_order_release와 짝이 된다. 해당 명령은 정책 선언 이후로 명령어를 재배치하지 않는다. 

atomic<int> Guard(0);
int Payload = 0;
...

void read_any() {
	for(...) {
      // 해당 정책 이후의 명령어는 이 선언 이전으로 재배치되지 않는다
      g = guard.load(memory_order_acquire);

      if(g) {
        // p는 항상 42가 담긴다
        p = Payload;
      }
    }
}

void write_any() {
  Payload = 42;
  // 해당 정책 이후의 명령어는 이 선언 이후로 재배치되지 않는다
  guard.store(1, memory_order_release);
}

 

memory_order_consume

역시 읽기 처리에 사용되며 consume을 통해 의존성이 생긴 명령들은 재배치하지 않는다. 아래 코드를 보자. atomic_load_explicit()를 호출할 때 memory_order_consume을 쓴다. insert_foo() 호출로 인해 해쉬 테이블에 항목이 추가되더라도 완벽하게 병렬 처리된다. 읽기 동작을 할 때 ...fence() 없이도 처리되며 거의 비용이 없다. memory_order_acquire와 마찬가지로  memory_order_release와 짝이 되어야 한다. 보통 의존성을 추적하는 일은 매우 번거롭기 때문에 이 명령을 쓰면 편리하다.

/*
http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1525.htm

무잠금으로 해시테이블에 읽기/쓰기한다
*/

enum { NUM_BUCKETS = 128; };

struct foo {
    _Atomic volatile struct foo *next;
    int key;
};
_Atomic volatile struct foo *hashtable[NUM_BUCKETS];

DEFINE_LOCK(foo_lock);

// key에 연관된 값을 찾아 돌려준다
int find_foo(int key) {
    struct foo *p;
    int retval;
    
    // RCU 구간에 들어왔음을 알린다. 자세한 건 RCU 포스팅 참조
    rcu_read_lock();
    // &hashtable[foo_hash(key)] 주소와 연관된 경우, 여기에 의존성을 가진 메모리는 안전하게 접근할 수 있다
    p = atomic_load_explicit(&hashtable[foo_hash(key)], memory_order_consume);
    while (p != NULL && p->key < key) {
        // Linux kernel: p = rcu_dereference(p-<next);
        // 탐색을 지속하려면 다음 포인터가 필요하다. 이때 다음 주소를 위와 마찬가지로 읽어들인다
        p = atomic_load_explicit(&p->next, memory_order_consume);
    }
    retval = p != NULL && p->key == key;
    // RCU 종료
    rcu_read_unlock();
    return retval;
}

// key 값을 저장한다
int insert_foo(int key) {
    struct foo *newp, *p;
    _Atomic volatile struct foo **plast;
    int retval = 0;
    // 스핀락이 acquire-release가 아니라면 락 아래의 명령이 위로 배치될 수도 있다!
    spin_lock(&foo_lock);   // assume acquire-release at minimum
    plast = &hashtable[foo_hash(key)];
    p = *plast;
    while (p != NULL && p->key < key) {
        p = p->next;
        plast = &p-<next;
    }
    if (p == NULL || p->key != key) {
        newp = malloc(sizeof(*newp));
        if (newp != NULL) {
            newp->key = key;
            newp->next = p;
            // release 이후의 명령을 함수 호출 이전으로 배치하지 않도록 한다
            // 이는 메모리에 값이 저장되기 전에 retval이 오염되지 않게 한다. 
            atomic_store_explicit(*plast, newp, memory_order_release);
            retval = 1;
        }
    }
    lock_release(&foo_lock);
    return retval;
}

memory_order_release

이 정책은 값을 저장할 때 쓰인다. 이것이 선언된 이후의 명령은 선언 이전으로 재배치되지 않기 때문이다.

 

memory_order_acq_rel

이 인자를 사용한 명령 이전과 이후의 명령들이 재배치되지 않는다. 

 

memory_order_seq_cst

C11 이전의 정렬 방식. 즉 모든 명령은 순차적으로 실행되며 프로그래머는 걱정할 일이 없다

 

먼저 아래 정책을 단순한 값 타입 이외에 적용하는 건 적절하지 않다. 즉 메모리 버스보다 큰 메모리를 점유하는 객체에게는 결국 뮤텍스 등 좀더 무거운 수단이 필요하다. 

 

 

?? 그런데 스레드가 여러 개일 때는? 읽어보기

https://www.slideshare.net/YiHsiuHsu/introduction-to-memory-order-consume
읽어보기

bartoszmilewski.com/2008/11/05/who-ordered-memory-fences-on-an-x86/

Who ordered memory fences on an x86?

https://en.cppreference.com/w/cpp/atomic/memory_order

std::memory_order - cppreference.com

https://preshing.com/20120612/an-introduction-to-lock-free-programming/

An Introduction to Lock-Free Programming

https://www.slideshare.net/seao/c-atomic
https://www.slideshare.net/YiHsiuHsu/introduction-to-memory-order-consume

http://15418.courses.cs.cmu.edu/spring2016/lecture/consistency/slide_025

RCU(Read Copy Update) -1- (Basic) – 문c 블로그 (dothome.co.kr)

RCU(Read Copy Update) -1- (Basic)

 

stackoverflow.com/questions/24057331/is-accessing-data-in-the-heap-faster-than-from-the-stack

Is accessing data in the heap faster than from the stack?

www.internalpointers.com/post/understanding-memory-ordering