메모리 순서 지정

Memory ordering

메모리 순서는 CPU에 의한 컴퓨터 메모리에 대한 액세스 순서를 설명한다.이 용어는 컴파일러가 컴파일 시간 동안 생성한 메모리 순서 또는 런타임 동안 CPU에 의해 생성된 메모리 순서를 가리킬 수 있다.

현대의 마이크로프로세서에서, 메모리 순서는 CPU의 메모리 작업 순서 변경 능력을 특징으로 한다 – 그것은 순서가 맞지 않는 실행의 일종이다.메모리 재정렬은 캐시나 메모리 뱅크와 같은 다른 유형의 메모리의 버스 대역폭을 충분히 활용하는 데 사용될 수 있다.

대부분의 현대적인 유니프로세서 메모리 연산은 프로그램 코드에 의해 지정된 순서대로 실행되지 않는다.단일 스레드 프로그램에서는 모든 작업이 지정된 순서대로 실행된 것으로 보이며, 프로그래머에게는 순서가 맞지 않는 모든 실행이 숨겨져 있다. 그러나 멀티 스레드 환경에서는(또는 메모리 버스를 통해 다른 하드웨어와 인터페이스할 때) 이는 문제를 일으킬 수 있다.문제를 피하기 위해 이러한 경우에 기억장벽을 사용할 수 있다.

컴파일 시간 메모리 순서 지정

대부분의 프로그래밍 언어는 정의된 순서대로 문장을 실행하는 실행 쓰레드에 대한 개념을 가지고 있다.전통적인 컴파일러는 높은 수준의 표현을 기본 기계 수준에서 프로그램 카운터에 상대적인 일련의 낮은 수준의 지시로 변환한다.

실행 효과는 높은 수준의 프로그램 코드 내에서, 그리고 동시 프로그래밍에서 다른 스레드나 처리 요소에 의해 보이는 기계 수준에서, 또는 기계 상태에 대한 액세스와 함께 하드웨어 디버깅 보조장치를 사용할 때 디버깅하는 동안(이는 종종 CPU나 마이크로컨트롤러에 직접 내장된 지원)의 두 가지 수준에서 볼 수 있다.실행 상태의 정적 검사를 위해 코어 자체를 정지해도 계속 작동하는 실행 코어에서 떨어져 기능적으로 독립된 회로로서 oleer).컴파일 시간 메모리 순서는 전자와 관련이 있으며, 이러한 다른 견해와 관련이 없다.

프로그램 순서의 일반 문제

표현식 평가의 프로그램 순서 효과

컴파일하는 동안 하드웨어 지침은 고수준 코드에 지정된 것보다 더 세분화된 방식으로 생성되는 경우가 많다.절차적 프로그래밍에서 관찰할 수 있는 주요 효과는 명명된 변수에 새 값을 할당하는 것이다. 

합 = a + b + c; 인쇄(합);

인쇄 문장은 변수 합계에 할당되는 문장에 따르며, 따라서 인쇄 문장이 계산 변수를 참조할 때sum그것은 이 결과를 사전 실행 순서의 관찰 가능한 효과로 언급한다.프로그램 시퀀스 규칙에 의해 정의된 바와 같이 다음과 같은 경우print함수 호출 참조sum, 값sum변수에 대한 가장 최근에 실행된 할당 값이어야 함sum(이 경우 직전 진술).

기계 수준에서는 한 번의 명령으로 세 개의 숫자를 함께 추가할 수 있는 기계가 거의 없기 때문에 컴파일러는 이 표현을 두 개의 추가 작업으로 번역해야 할 것이다.프로그램 언어의 의미론에서 컴파일러가 표현을 좌우 순서로 번역하도록 제한한다면(예를 들어), 생성된 코드는 프로그래머가 원래 프로그램에 다음과 같은 문장을 쓴 것처럼 보일 것이다.

합 = a + b; 합 = 합 + c;

컴파일러가 추가의 연관 특성을 이용할 수 있도록 허용된 경우, 대신 다음을 생성할 수 있다.

합 = b + c; 합 = + 합;

컴파일러가 덧셈의 정류 특성을 이용할 수도 있는 경우, 대신 다음을 생성할 수 있다.

합 = a + c; 합 = 합 + b;

대부분의 프로그래밍 언어의 정수 데이터 유형은 정수 오버플로가 없는 경우 수학 정수에 대한 대수만을 따르고 대부분의 프로그래밍 언어에서 사용할 수 있는 부동 소수점 데이터 유형의 부동 소수점 산술은 반올림 효과에 있어 역호환적이지 않기 때문에 표현 순서의 효과가 반올림 효과에 나타나게 된다는 점에 유의하십시오.계산된 결과의 작은 차이(단, 작은 초기 차이는 더 긴 계산에 걸쳐 임의로 큰 차이로 분류될 수 있다.

프로그래머가 부동소수의 정수 오버플로나 반올림 효과를 우려하는 경우, 동일한 프로그램을 다음과 같이 원래의 높은 수준에서 코딩할 수 있다.

합 = a + b; 합 = 합 + c;

함수 호출과 관련된 프로그램 순서 효과

많은 언어가 문 경계선을 시퀀스 포인트로 취급하여, 다음 문장이 실행되기 전에 한 문장의 모든 효과를 완료하도록 강요한다.이것은 컴파일러가 표현된 명령어 순서에 해당하는 코드를 생성하도록 강제할 것이다.그러나 진술은 종종 더 복잡하고 내부 기능 호출을 포함할 수 있다. 

합 = f(a) + g(b) + h(c);

기계 수준에서 함수를 호출하는 것은 보통 함수 호출에 대한 스택 프레임을 설정하는 것을 포함하는데, 이것은 기계 메모리에 많은 읽기 및 쓰기를 포함한다.컴파일러는 대부분의 컴파일러 언어에서 함수 호출을 자유롭게 주문할 수 있다.f,g그리고h편리하다고 생각될 때, 프로그램 메모리 순서의 대규모 변경을 초래한다.순수한 기능 프로그래밍 언어에서 함수 호출은 가시적인 프로그램 상태에 부작용을 일으키는 것이 금지되며(반환 값 제외) 함수 호출 순서에 따른 기계 메모리 순서의 차이는 프로그램 의미론에는 중요하지 않을 것이다.절차 언어에서 호출된 함수는 I/O 작업을 수행하거나 글로벌 프로그램 범위에서 변수를 업데이트하는 등 부작용이 있을 수 있으며, 이 두 기능 모두 프로그램 모델로 가시적인 효과를 산출한다.

다시 말하지만, 이러한 효과와 관련된 프로그래머는 원래의 소스 프로그램을 표현하는데 있어 더 현학적인 것이 될 수 있다.

합 = f(a), 합 = 합 + g(b), 합 = 합 + 합 + h(c);

문 경계가 시퀀스 포인트로 정의된 프로그래밍 언어에서 함수는 호출한다.f,g그리고h이제 그 정확한 순서로 실행해야 한다.

메모리 순서의 특정 문제

포인터 식과 관련된 프로그램 순서 효과

이제 포인터를 지원하는 C 또는 C++와 같은 언어로 포인터 리디렉션으로 표현된 동일한 합계를 고려하십시오.

합 = *a + *b + *c;

표현식 평가*x"회의식"이라고 불리며, 현재 값으로 지정된 위치에서 메모리에서 읽는 것을 포함한다.x포인터에서 읽는 효과는 건축의 기억 모델에 의해 결정된다.표준 프로그램 저장소에서 읽을 때는 메모리 읽기 작업 순서에 따른 부작용이 없다.임베디드 시스템 프로그래밍에서는 읽기 및 쓰기가 메모리에 트리거하는 메모리 매핑된 I/O 또는 프로세서 작동 모드의 변경으로 인해 가시성이 매우 높은 부작용이 발생하는 것이 매우 일반적이다.위의 예를 들어, 이러한 부작용 없이 포인터가 일반 프로그램 메모리를 가리키고 있다고 가정해 보십시오.컴파일러는 이러한 읽기를 프로그램 순서대로 재주문할 수 있으며, 프로그램이 볼 수 있는 부작용은 없을 것이다.

할당된 값도 포인터가 간접적인 경우? 

*sum = *a + *b + *c;

여기서 언어 정의는 다음과 같이 컴파일러가 이것을 분해하는 것을 허용할 것 같지 않다.

// 컴파일러에 의해 다시 작성된 // 일반적으로 금지된 *sum = *a + *b; *sum = *sum + *c;

이것은 대부분의 경우 효율적이라고 볼 수 없으며 포인터 쓰기는 가시적 기계 상태에 잠재적인 부작용을 가지고 있다.컴파일러는 이 특별한 분할 변환이 허용되지 않기 때문에, 유일한 쓰기는sum값 식에서 세 개의 포인터 읽기를 논리적으로 따라야 한다.

그러나 프로그래머가 정수 오버플로의 가시적인 의미론에 대해 염려하고 다음과 같이 프로그램 레벨로 문장을 구분한다고 가정하자.

// 프로그래머가 직접 작성한 *sum = *a + *b; *sum = *sum + *c;

첫 번째 문은 두 개의 메모리 읽기를 인코딩하며, 첫 번째 쓰기 앞에 (어느 순서로든) 놓아야 한다.*sum. 두 번째 문은 (어느 순서로든) 두 개의 메모리 읽기를 인코딩하며, 두 번째 업데이트 전에 선행되어야 한다.*sum이렇게 하면 두 개의 추가 작업의 순서를 보장하지만 잠재적으로 주소 별칭 지정의 새로운 문제가 발생할 수 있다: 이러한 포인터 중 어떤 것도 잠재적으로 동일한 메모리 위치를 나타낼 수 있다.

예를 들어, 이 예에서 다음과 같이 가정해 보자.*c그리고*sum동일한 메모리 위치에 앨리어싱되고, 두 버전의 프로그램을 다시 쓰십시오.*sum두 사람 모두를 위해 서 있는 

*sum = *a + *b + *sum;

여기에는 문제가 없다.우리가 원래 썼던 것의 원래 가치.*c에 할당되어 있지 않다.*sum, 그리고 의 원래 가치도 그렇다.*sum애초에 이걸 덮어쓰게 된 거잖아 특별한 관심도 없어 

// *c 및 *sum 별칭 *sum = *a + *b; *sum = *sum + *sum;

의 원래 값*sum첫 번째 액세스 전에 덮어쓰게 되며, 대신 다음과 같은 대수학적 값을 얻는다.

// *sum = (*a + *b) + (*a + *b) + (*a + *b);

에 완전히 다른 값을 할당한다.*sum성명 재배열로 인해

앨리어싱 효과로 인해 포인터 표현식은 가시적인 프로그램 효과 없이 재배열하기 어렵다.일반적인 경우, 어떤 별칭도 유효하지 않을 수 있으므로 코드는 이전과 같이 정상적으로 실행되는 것으로 보인다.그러나 앨리어싱이 존재하는 에지 경우에는 심각한 프로그램 오류가 발생할 수 있다.이러한 에지 사례가 정상적인 실행에서 완전히 존재하지 않더라도 악의적인 적에게 앨리어싱이 존재하는 입력을 조작할 수 있는 문을 열어주며, 잠재적으로 컴퓨터 보안 악용으로 이어질 수 있다.

이전 프로그램의 안전한 재주문은 다음과 같다.

// 적절한 유형의 온도 = *a + *b; *sum = temp + *c;의 임시 로컬 변수 'properties'를 선언한다.

마지막으로 기능 호출이 추가된 간접 사례를 고려하십시오.

*sum = f(*a) + g(*b);

컴파일러가 평가하도록 선택할 수 있음*a그리고*b어느 한 기능 호출 전에, 그것은 다음의 평가를 연기할 수 있다.*b함수 호출이 끝날 때까지f또는 에 대한 평가를 연기할 수 있다.*a함수 호출이 끝날 때까지g.기능이 있는 경우f그리고g프로그램 가시적 측면 조작이 없는 경우, 세 가지 선택 모두 동일한 가시적 프로그램 효과를 가진 프로그램을 생성할 것이다.이 구현된 경우f또는g포인터로 앨리어싱할 수 있는 포인터 쓰기의 부작용 포함a또는b이 세 가지 선택은 서로 다른 가시적인 프로그램 효과를 생성하기 쉽다.

언어 사양에서의 메모리 순서

일반적으로 컴파일된 언어는 컴파일러가 컴파일 시 어떤 포인터가 잠재적으로 앨리어싱되고 어떤 포인터가 아닌지를 공식적으로 결정할 수 있을 정도로 충분히 상세하지 않다.가장 안전한 방법은 컴파일러가 모든 포인터가 항상 잠재적으로 별칭이 있다고 가정하는 것이다.이 정도의 보수적인 비관주의는 어떠한 별칭도 존재하지 않는다는 낙관적인 가정과 비교했을 때 무시무시한 성과를 내는 경향이 있다.

그 결과, C/C++와 같은 많은 고급 컴파일 언어들은 컴파일러가 가능한 최고 성능을 추구하기 위해 코드 재순서에서 낙관적인 가정을 할 수 있는 장소와, 컴파일러가 코드 rere에서 비관적인 가정을 할 필요가 있는 장소에 대해 복잡하고 정교한 의미 규격을 갖도록 진화되었다.의미적 위험을 피하도록 명령한다.

지금까지 현대 절차 언어에서 부작용의 가장 큰 종류는 메모리 쓰기 작업을 포함하므로, 메모리 순서 주변의 규칙은 프로그램 순서 의미론의 정의에서 지배적인 요소다.위의 함수 호출의 순서 변경은 다른 고려사항으로 보일 수 있지만, 이는 함수 호출을 생성하는 표현에서 메모리 연산과 상호 작용하는 호출된 함수 내부의 메모리 효과에 대한 우려로 보통 전환된다.

추가적인 어려움 및 복잡성

현재 상태에서의 최적화

현대의 컴파일러는 때때로 가시적인 프로그램 의미론적 결과에 영향을 미치지 않는 경우 재주문이 허용되는 현행 규칙을 통해 한 단계 더 나아가야 한다.이 규칙에 따르면, 번역된 코드의 운용 순서는 지정된 프로그램 순서와 크게 다를 수 있다.컴파일러가 그러한 별칭이 실제로 존재하는 경우(이는 일반적으로 정의되지 않은 동작을 나타내는 잘못된 형식의 프로그램으로 분류될 수 있음)에 별칭이 겹치지 않는 구별되는 포인터 표현에 대해 낙관적인 가정을 할 수 있는 경우, 공격적인 코드 최적화 변환의 부정적인 결과를 추측할 수 없다.s 코드 실행 또는 직접 코드 검사 전.정의되지 않은 행동의 영역은 거의 무한한 발현을 가지고 있다.

법률 컴파일러 최적화의 결과로 의미론이 잠재적으로 변경될 수 있는 잘못된 형식의 프로그램 작성을 피하기 위해 언어 사양을 참조하는 것은 프로그래머의 책임이다.Fortran은 전통적으로 시스템 프로그래밍 언어 C와 C++가 머지않아 프로그래머에게 이러한 문제를 인식해야 하는 부담이 크다.

일부 고급 언어는 포인터 구조를 완전히 제거하는데, 이 수준의 경계성과 세부 사항에 대한 관심이 전문 프로그래머들 사이에서도 안정적으로 유지되기에는 너무 높은 것으로 간주되기 때문이다.

메모리 순서 의미론의 완전한 파악은 전형적으로 이 주제 영역에서 가장 잘 알고 있는 전문 시스템 프로그래머들의 하위 집단들 사이에서도 불가사의한 전문화로 간주된다.대부분의 프로그래머들은 프로그래밍 전문지식의 정상적인 영역 내에서 이러한 이슈에 대한 적절한 실무적 파악에 만족한다.메모리 순서 의미론에서 전문화의 극한 끝에는 동시 컴퓨팅 모델을 지원하기 위해 소프트웨어 프레임워크를 작성하는 프로그래머들이 있다.

로컬 변수의 앨리어싱

이러한 변수에 대한 포인터가 야생으로 빠져나가는 경우 국부 변수에 앨리어싱이 없다고 가정할 수 없다는 점에 유의하십시오.

합 = f(&a) + g(a);

그 기능이 무엇인지 알 수 없다.f에 제공된 포인터가a, 기능이 있는 복사본을 전역 상태로 두는 것을 포함.g나중에 접근한다.가장 간단한 경우,f변수에 새 값을 쓴다.a, 이 표현을 실행 순서로 잘못 정의한다. f포인터 인수의 선언에 const 한정자를 적용하여 식을 잘 정의하여 표시함으로써 이를 현저하게 방지할 수 있다.따라서 C/C++의 현대 문화는 모든 실행 가능한 경우에서 기능적 논쟁 선언에 대한 순례자격을 제공하는 것에 다소 집착하게 되었다.

C와 C++의 내부 허용f위험한 편법으로 항상성 속성을 버리는 것.만약f이것은 위의 표현을 깨뜨릴 수 있는 방법으로, 포인터 인수 유형을 애초에 constance로 선언해서는 안 된다.

다른 고급 언어는 언어 자체 내에서 제공되는 이 보증을 위반할 루프홀이 없는 강력한 보증에 해당하는 선언 속성으로 기울어진다. 응용 프로그램이 다른 프로그래밍 언어로 작성된 라이브러리를 연결하면 모든 배팅이 이 언어 보증을 무효로 한다(비극적으로 간주됨).나쁜 디자인).

컴파일 시간 메모리 장벽 구현

참고 항목:메모리 장벽

이러한 장벽은 컴파일러가 컴파일 시간 동안 지시사항을 재정렬하는 것을 방지한다. 즉, 런타임 동안 CPU에 의한 재정렬을 방해하지 않는다.

  • 이러한 GNU 인라인 어셈블러 문에서는 GCC 컴파일러가 주변의 읽기 및 쓰기 명령을 다시 정렬하는 것을 금지한다.[1]
asm 휘발성" ::: "memory"; __asm___volativity__("":: "memory";
  • 이 C11/C++11 함수는 컴파일러가 주변의 읽기 및 쓰기 명령을 다시 정렬하는 것을 금지한다.[2]
atomic_operates_cq_rel;
__memory_properties
_ReadWriteBarrier()

복합장벽

많은 프로그래밍 언어에서 서로 다른 유형의 장벽이 다른 운영(부하, 저장, 원자 증가, 원자 비교 및 스왑 등)과 결합될 수 있으므로, 그것(또는 둘 다) 전후에 추가적인 메모리 장벽이 필요하지 않다.대상인 CPU 아키텍처에 따라 이러한 언어 구조는 하드웨어 메모리 주문 보증에 따라 특별 지침, 다중 지침(즉, 장벽 및 부하) 또는 일반 지침으로 변환된다.

런타임 메모리 순서 지정

대칭 다중 프로세서(SMP) 마이크로프로세서 시스템

SMP 시스템에는 몇 가지 메모리 일관성 모델이 있다.

  • 순차적 일관성(모든 읽기 및 모든 쓰기가 순서대로 있음)
  • 일관성 완화(일부 유형의 재주문 허용)
    • 로드 후 부하를 다시 정렬할 수 있음(캐시 일관성 개선, 확장 개선)
    • 스토어 후 재주문 가능
    • 스토어 후 재주문 가능
    • 로드 후 스토어를 다시 정렬할 수 있음
  • 약한 일관성(읽기 및 쓰기는 임의로 재순서되며 명시적 메모리 장벽에 의해서만 제한됨)

일부 CPU에서

  • 원자력은 부하와 저장소로 재주문할 수 있다.[6]
  • 특별한 명령어 캐시 플러시/재로드 지침 없이 자체 수정 코드가 실행되지 않도록 하는 일관성 없는 명령어 캐시 파이프라인이 있을 수 있다.
  • 종속하중은 재주문할 수 있다(Alpha 전용).프로세서가 이 재주문 후 일부 데이터에 대한 포인터를 가져오는 경우, 데이터 자체를 가져오지 않고 이미 캐시되었지만 아직 무효화되지 않은 오래된 데이터를 사용할 수 있다.이러한 완화를 허용하면 캐시 하드웨어가 간단하고 빨라지지만, 독자와 작성자의 메모리 장벽이 요구되게 된다.[7]Alpha 하드웨어(다중 프로세서 Alpha 21264 시스템 등)에서 다른 프로세서로 전송되는 캐시 라인 무효화는 종속 부하 간에 처리하도록 명시적으로 요청되지 않는 한 기본적으로 느리게 처리된다.알파 아키텍처 규격은 또한 다른 형태의 종속 부하 순서를 변경할 수 있도록 허용한다. 예를 들어 실제 포인터를 참조할 수 있기 전에 추측 데이터 판독을 사용한다.
일부 아키텍처에서[8][9] 메모리 순서 지정
유형 알파 ARMv7 MIPS RISC-V PA-RISC 파워 SPARC x86 [a] AMD64 IA-64 z/건축학
WMO TSO RMO PSO TSO
부하 후 재주문 가능 Y Y 에 달려 있다
실행		 Y Y Y Y Y
스토어 후 재주문 가능 Y Y Y Y Y Y Y
스토어 후 재주문 가능 Y Y Y Y Y Y Y Y
로드 후 스토어를 다시 정렬할 수 있음 Y Y Y Y Y Y Y Y Y Y Y Y Y
원자재를 부하로 재주문할 수 있음 Y Y Y Y Y Y
원자력은 상점과 함께 재주문될 수 있다. Y Y Y Y Y Y Y
종속 부하를 재주문할 수 있음 Y
일관성 없는 명령 캐시/파이프라인 Y Y Y Y Y Y Y Y Y Y
  1. ^ 이 열은 대부분의 x86 프로세서의 동작을 나타낸다.일부 희귀 전문 x86 프로세서(1998년경 제조된 IDT WinChip)는 'oostore' 메모리 순서가 약할 수 있다.[10]

RISC-V 메모리 순서 지정 모델:

WMO
약한 메모리 순서(기본값)
TSO
총 저장소 순서(Ztso 확장자에서만 지원)

SPARC 메모리 주문 모드:

TSO
총 스토어 순서(기본값)
RMO
느린 메모리 순서(최근 CPU에서는 지원되지 않음)
PSO
부분 저장소 순서(최근 CPU에서 지원되지 않음)

하드웨어 메모리 장벽 구현

참고 항목:메모리 장벽

SMP를 지원하는 많은 아키텍처들은 런타임 동안 읽기 및 쓰기를 플러시하는 특별한 하드웨어 지침을 가지고 있다. 

lfence(asm), void _mm_lfence(vms), void _mm_lfence(vms), void _mm_mfence(vms),[11] void _m_mfence(vms)[12]
동기화(asm)
동기화(asm)
mf (asm)
dcs(asm)
dmb (asm) dsb (asm) isb (asm)

하드웨어 메모리 장벽을 위한 컴파일러 지원

일부 컴파일러는 하드웨어 메모리 장벽 지침을 방출하는 빌트인을 지원한다.

참고 항목

참조

  1. ^ GCC 컴파일러-gcc.h 웨이백 머신에 2011-07-24 보관
  2. ^ "std::atomic_signal_fence". ccpreference.
  3. ^ ECC 컴파일러-intel.h 웨이백 머신에 2011-07-24 보관
  4. ^ Intel(R) C++ 컴파일러 본질 참조

    컴파일러가 데이터 액세스 명령을 예약하지 않는 장애물 생성컴파일러는 전역 데이터가 아닌 메모리 장벽에 걸쳐 레지스터의 로컬 데이터를 할당할 수 있다.
  5. ^ Visual C++ 언어 참조 _ReadWriteBarrier
  6. ^ 빅터 알레산드리니, 2015년공유 메모리 응용 프로그램 프로그래밍:멀티코어 애플리케이션 프로그래밍의 개념과 전략.엘스비에 사이언스 176 ISBN 978-0-12-803820-8
  7. ^ Kourosh Gharachorloo의 알파 프로세서 재주문
  8. ^ Paul McKenney에 의한 현대 마이크로프로세서의 메모리 주문
  9. ^ 메모리 장벽: 소프트웨어 해커를 위한 하드웨어 뷰, 그림 5(16페이지)
  10. ^ 표 1. "현대 마이크로프로세서의 메모리 순서, 파트 I"에서 나온 메모리 순서 요약
  11. ^ SFENCE — 저장 울타리
  12. ^ MFENCE — 메모리 펜스
  13. ^ 데이터 메모리 장벽, 데이터 동기화 장벽 및 명령 동기화 장벽.
  14. ^ 아토믹 빌딘스
  15. ^ "36793 – x86-64 does not get __sync_synchronize right".
  16. ^ 메모리배리어 매크로
  17. ^ Oracle Solaris Studio 12 업데이트 2를 사용한 멀티스레드 애플리케이션에서의 메모리 주문 처리: Part 2, 메모리 장벽 및 메모리 펜스 [1]

추가 읽기