Android Document  SDK old PDF 파일
Android SMP(1/7) - 이론:메모리 일관성 모델, 사례, 부록
작성자
작성일 2011-05-02 (월) 22:40
ㆍ추천: 0  ㆍ조회: 16645      
IP: 121.xxx.76
 
 
 

Android SMP


이 문서는 대칭적 멀티프로세서symmetric multiprocessor 시스템을 위한 C, C++,
Java 프로그램 언어 (이후부터는 번잡을 피하기 위해 간단하게 Java라고 부를 것이다)
코드를 작성할 때 제기되는 이슈들을 소개한다.


 
이 문서는 이와 같은 주제에 대한 완벽한 글은 아니며, 안드로이드 애플리케이션과
프레임워크 개발자들을 위한 입문서로서의 취지를 갖는다. 관심의 초점은 ARM CPU
아키텍처에 놓여 있다. 만약 급하다면, 아래의 이론 섹션을 건너뛰어 직접 사례 섹션을 보아도 좋다.
하지만 권장하지는 않는다.
 
 
목차
 
1. 도입
2. 이론
   2.1. 메모리 일관성 모델(Memory Consistency Models)
   2.2. 데이터 메모리 장벽(Data Memory Barriers)
   2.3. 원자적 오퍼레이션들(Atomic Operations)
3. 사례
   3.1. C에서 하지 말 것
   3.2. Java에서 하지 말 것.
   3.3. 해야 할 것
4. 부록
 
 

1. 도입

 

SMP는 Symmetric Multi-Processor의 약어이다. 이것은 두 개 또는 그 이상의 동일한 CPU 코어들이
메인 메모리에 대한 접근을 공유하는 디자인을 의미한다. 최근까지 모든 안드로이드 디바이스는 단일
프로세서였다.

 
모든 것이 그렇지는 않지만, 대부분의 안드로이드 디바이스는 다중 CPU를 가지고 있다.
하지만, 일반적으로 다중 CPU중 하나는 애플리케이션을 실행하기 위해 사용되며,
나머지 하나는 (예를 들어, 라디오radio와 같은) 다양한 디바이스 하드웨어 영역들을 관리한다.
이들 CPU들은 서로 다른 아키텍처일 수 있으며, 각각의 코어에서 실행되는 프로그램이 서로 통신하기 위해
메인 메모리를 사용할 수는 없다.
 
점점 더 많은 안드로이드 디바이스들이 SMP 디자인을 지원하게 될 것이며, 이것은 소프트웨어 개발자들에게
다소 더 복잡한 것들을 요구할 것이다. 멀티쓰레드multi-threaded 프로그램에서 여러분이 접할 수 있는
경쟁 조건race condition과 같은 것들은 두 개 또는 그 이상의 쓰레드들이 SMP상에서 서로 다른 코어에서
동시에 실행될 때 매우 심각해 진다. ARM상의 SMP 관련 작업은 x86에서의 SMP보다 더 많은 문제가 있다.
x86에서 철저하게 테스트된 코드가 ARM에서는 좋게 않게 깨질 수도 있다.
 
이 문서의 나머지 영역에서 그 이유가 설명될 것이며, 코드를 올바르게 동작시키기 위해 필요한 것이 무엇인지
설명될 것이다.

 

2. 이론

 

이 문서는 복잡한 주제를 빠른 속도로 검토해 나가는 높은 수준의 개요를 제공한다.
어떤 영역은 완전하지 않을 수 있을 것이다. 하지만 그것들 어떤 것도 잘못 이끌거나 틀린 것은 아닐 것이다.

 
이 주제에 대해 보다 철두철미한 논의 점들은 부록에 있는 더 읽기 섹션을 보라,
 
 

2.1 메모리 일관성 모델(Memory Consistency Models) 


“메모리 일관성 모델” 또는 가끔은 단순하게 “메모리 모델”이라 불리는 이것은, 하드웨어 아키텍처가 메모리
접근에 대해 보장해야 하는 것들을 의미한다. 예를 들어, 만약 여러분이 어드레스 A에 임의의 값을 write하고,
그런 다음에 어드레스 B에 임의의 값을 write 한다면, 이 모델은 모든 CPU 코어들이 write가 일어난 순서대로
보는 것을 보장할 것이다.

 
거의 모든 프로그래머들에게 익숙한 이 모델이 순차적 일관성sequential consistency이다.
이것은 다음과 같이 설명된다.
  • 모든 메모리 오퍼레이션은 한번에 하나씩 실행된다.
  • 단일 프로세서상의 모든 오퍼레이션은 프로세서의 프로그램에 서술된 순서대로 실행된다.
만약 작은 코드를 검토하고 이것이 순차적으로 일관된 CPU 아키텍처상에서 메모리에서 임의의 read와
write를 하는 것을 본다면, 여러분은 기대했던 순서대로 그러한 read와 write가 될 것이라는 것을 안다.
CPU가 실제로 명령어를 재정렬reordering하고 read와 write를 지연시키는 것은 가능하다.
하지만, 디바이스상에서 실행되는 코드가 CPU가 단순한 방식으로 명령어를 수행하는 것 이외에
어떤 것을 하게끔 할 방법은 없다. (우선은 메모리맵memorymapped 디바이스 드라이버는 무시한다.)
 
이러한 점들을 실증하기 위해, 일반적으로 리트머스 테스트라 불리는 작은 코드 조각을 고려해 보는 것이
유용하다. 이것은 프로그램 순서대로의 실행을 가정한다. 예를 들어 여기에서 나타난 명령들의 순서는
CPU가 그것들을 실행할 순서이다. 우리는 아직은 컴파일러에 의해 재정렬된 실행을 고려치 않는다.
 
여기에 두 개의 쓰레드에서 실행되는 코드를 갖는 간단한 예제가 있다.

쓰레드 1

쓰레드 2

A = 3

B = 5

reg0 = B

reg1 = A

 
이것과 이후의 모든 리트머스 예제들에서, 메모리 위치는 대문자(A, B, C)로 표기되며, CPU 레지스터는
reg로 시작한다. 모든 메모리는 초기에 0 이다. 명령어는 위에서 아래로 실행된다. 여기에서 쓰레드 1은
A 위치에 3을 store한다. 그런 다음에 B 위치에 5를 store한다. 쓰레드 2는 B 위치의 값을 reg0에 load한다.
그런 다음에 A 위치의 값을 reg1에 load한다.
(한편에서는 순서대로 쓰기를 하고 다른 한편에서는 읽기를 한다는 것에 주목하라.)
 
쓰레드 1과 쓰레드 2는 다른 CPU 코어에서 실행된다고 가정한다. 멀티 쓰레드 코드에 대해서 생각할 때
여러분은 항상 이러한 가정을 해야 한다.
 
순차적 일관성은 두 쓰레드 모두가 실행을 끝마친 이후, 레지스터가 다음과 같은 상태 중에 하나가 될 것을
보장한다.

reg0=5, reg1=3

가능 (쓰레드 1 먼저 실행)

reg0=0, reg1=0

가능 (쓰레드 2 먼저 실행)

reg0=0, reg1=3

가능 (동시 실행)

reg0=5, reg1=0

결코 불가능

 
A 에 store된 것을 보기 전에 B=5 라는 상황을 얻으려면, 적어도 read나 write 중 하나는 순서가 바뀌어야
할 것이다. 순차적으로 일관된 기기machine에서 그것은 일어날 수 없다.
 
x86과 ARM을 포함하는 대부분의 단일 프로세서는 순차적으로 일관된다. 하지만, x86과 ARM을 포함하는
대부분의 대부분의 SMP 시스템은 그렇지 않다.
 
 

2.1.1 프로세서 일관성(Processor Consistency)


 x86 SMP는 프로세서 일관성processor consistency을 제공하는데, 이것은 순차적 일관성보다 조금 더
약한 것이다. 그 아키텍처는 load는 다른 load에 대응해서 재정렬되지 않는다는 것과 store가 다른 store에
대응해서 재정렬되지 않는다는 것을 보장한다. 하지만 이것은 load 다음의 store가 기대했던 순서대로
관측될 것을 보장하지는 않는다.

 
상호배제mutual exclusion에 대한 Dekker의 알고리즘의 일부인 다음의 예제를 고려해라.

쓰레드 1

쓰레드 2

A = true

reg1 = B

if (reg1 == false)

critical-stuff

B = true

reg2 = A

if (reg2 == false)

critical-stuff


이 발상은 쓰레드 1 이 바쁘다는 것을 표시하기 위해 A를 사용하고, 쓰레드 2 는 B를 사용한다는 것이다.
쓰레드 1 은 A 에 true를 설정하고 그런 다음에 B가 true인지를 검토한다; 만약 B가 true가 아니라면,
쓰레드 1 은 안전하게 위험 구역critical section에 대한 배타적 접근을 한다고 가정할 수 있다. 쓰레드 2
유사한 것을 한다. (만약 쓰레드가 A와 B 모두 true인 것이 발견된다면, 공정함을 보장하기 위해
turn-take(번 갈아서 수행하는) 알고리즘이 사용된다.)

순차적으로 일관된 기기machine 상에서는 이것은 정확하게 동작한다. 하지만 x86과 ARM SMP 상에서의
쓰레드 1 에 의해 이루어 지는 A에 store와 B에서 load가 쓰레드 2 에서는 다른 순서에서 관측될 수 있다.
만약 그런 일이 발생했다면, 우리는 실제로 다음과 같은 순서를 실행하도록 했을 것이다. (아래의 빈 라인은
오퍼레이션의 명확한 순서를 강조하기 위해 삽입되었다.)

쓰레드 1

쓰레드 2

reg1 = B

 

 

A = true

if (reg1 == false)

critical-stuff

 

B = true

reg2 = A

 

if (reg2 == false)

critical-stuff


이것은 해당 쓰레드들이 위험 구역에서 동시에 코드를 실행하는 것을 가능하게 하는, reg1과 reg2 모두에
“false”가 지정되는 결과를 초래한다. 어떻게 이런 것이 발생할 수 있는가를 이해하기 위해서는, CPU 캐쉬에
대해 약간 아는 것이 필요하다.
 
 
2.1.2 CPU 캐쉬 동작(CPU Cache Behavior)
 
 
이것은 캐쉬 차제로든 또는 캐쉬 내부에 대한 것이든  상당한 주제이다. 하지만 이어지는 내용은 아주
단순한 개요이다.
(이 내용에 대한 동기motivation는 왜 SMP 시스템이 그렇게 동작하는지를 이해하는 것에
대한 약간의 기초를 제공한다.)
 
현대적 CPU는 프로세서와 메인 메모리 사이에 하나 또는 그 이상의 캐쉬를 가지고 있다. 이것들은
L1, L2 등으로 계층화되어 있다. 높은 숫자일수록 CPU에서 단계적으로 멀리 떨어져 있다. 캐쉬 메모리는
하드웨어에 크기와 비용을 가중시키며, 파워 소모를 증대시킨다. 그러므로 일반적으로 안드로이드
디바이스에서 사용되는 ARM CPU들은 소규모의 L1 캐쉬와 더 작은 L2/L3를 가지거나 아니면 L2/L3를
보유하지 않는다.
 
임의의 값을 L1 캐시에서 load하거나 그곳에 store하는 것은 매우 빠르다. 동일한 것을 메인 메모리에 
수행하는 것은 10~100배 더 느리다. 그러므로 CPU는 가능한 한 캐쉬를 사용한 오퍼레이션을 많이
시도할 것이다. 캐쉬에 대한 write 정책은 캐쉬에 write된 데이터가 메인 메모리에 전달되는 시점을
결정한다. write-through 캐시는 메모리에 즉시 write를 개시하며, 반면에 write-back 캐쉬는 write를
수행할 공간이 없을 때까지 기다릴 것이며, 그리고 나서 일부 항목을 메모리로 퇴출하게 된다. 두 가지
경우에 있어서, CPU는 저장된 과거의 명령어들을 계속 실행할 것이다. 아마도 해당 write가 메인
메모리에서 보이기 전에 명령어들을 수십 개는 수행할 것이다.
(write-through 캐쉬는 즉시 데이터를
메인 메모리로 전달하는 정책을 가지지만, 그것은 단지 write를 개시할 뿐이다. 그것은 write가 끝날 때까지
기다릴 필요가 없다.)
 
캐쉬 작동방식은 각각의 CPU 코어가 자신만의 private 캐쉬를 가지고 있을 때 이 논의와 연관된다. 하나의
단순한 모델에서, 캐시들은 서로 직접적으로 상호작용할 방법이 없다. 코어 #1의 캐쉬에 의해 보유된 값은
메인 메모리로부터 load 또는 store 없이는 코어 #2의 캐쉬와 공유되거나 그 곳에서 보일 수 없다.
메모리 접근에 대한 긴 지체latency는 쓰레드간의 상호작용을 부진하게 할 것이다. 그러므로 캐쉬가
데이터를 공유하는 방법을 정의하는 것이 필요하다. 이러한 공유는 캐쉬 일관성cache coherency이라
불린다. 그리고 일관성 규칙은 CPU 아키텍처의 캐쉬 일관성 모델cache consistency model에 의해 정의된다.
 
이것을 염두에 두고, 다시 Dekker의 예제로 돌아가자. 코어 1이 “A=1”을 수행할 때, 그 값은 코어 1의
캐쉬에 저장된다. 코어 2가 “if (A ==0)”을 수행할 때, 그것은 메인 메모리에서 읽혀지거나 또는 코어 2의
캐쉬에서 읽혀질 수 있다; 두 방법 모두 그것은 코어 1에 의해 수행된 store를 보지 못했을 것이다.

(이전에 있었던 “A”로부터의 load 때문에, “A”는 코어 2의 캐쉬에 있게 된다.)
 
순차적으로 일관되어야 하는 메모리 일관성 모델때문에, 코어 1은 “if(B ==0)”을 수행하기 전에 “A=1”을
다른 모든 코어가 인지하도록 기다려야 할 것이다. (엄격한 캐쉬 일관성 규칙을 통하거나 또는 모든 것이
메인 메모리에서 처리되도록 전체적으로 캐쉬를 비활성화함으로써.)
이것은 모든 store 오퍼레이션에
성능 불이익을 초래할 것이다. load 뒤에 오는 store 정렬에 대한 규칙을 느슨하게 하는 것은 성능을
개선한다. 그러나 소프트웨어 개발자에게 무거운 짐을 지운다.
 
프로세서 일관성 모델에 의해 만들어진 그 밖의 보장들을 만드는 것은 덜 비싸다. 예를 들어, 메모리
write가 순서가 바뀌어 관측되지 않도록 하기 위해, 단지 그 store가 제기된 동일한 순서로 다른 코어들에
배포되게만 하면 된다. 스토어 #2가 배포될 수 있기 전에 store #1의 배포가 끝나길 기다릴 필요는 없다.
단지 배포 #1이 끝나기 전에 배포 #2가 끝나지 않게만 하면 된다. 이것은 성능 버블을 방지한다.
 
보장들을 느슨하게 하는 것은 심지어는 더 나아가 CPU 최적화에 대한 추가적인 기회를 제공할 수도
있다. 그러나 코드가 프로그래머가 기대하지 않았던 방식으로 동작하는 더 많은 계기를 만들기도 한다.
 
추가적 주의사항 : CPU 캐쉬는 개별 바이트들을 처리하지 않는다. 데이터는 캐쉬 라인cache lines 으로
read 또는 write 된다; 많은 ARM CPU들에서 이것은 32byte이다. 만약 여러분이 메인 메모리의 위치에서
데이터를 read 한다면, 몇몇 인접한 값들을 또한 read 하게 될 것이다. 데이터를 write 하는 것은 캐쉬
라인이 메인 메모리로부터 read 되도록 하고 업데이트 되게끔 한다. 결과적으로, 여러분은 read 또는
write 의 파생효과로서 일반적인 알 수 없는 현상을 만드는 인접한 어떤 것들을  캐시에 load 되게 할 수 있다.
 
 

2.1.3 관측가능성(Observability)



더 나아가기 전에, load 또는 store를 “관측하는 것observing”이 의미하는 것을 더 철저한 방식으로
정의하는 것이 필요하다. 코어 1 이 “A=1”을 수행한다고 가정하자. 이 store는 CPU가 명령을 실행할 때
시작된다. 나중에 어떤 시점에서, 아마도 캐쉬 일관성 동작을 통해, 그 store는 코어 2에서 관측된다.
write-through 캐쉬에서 그 store가 메인 메모리에 도달하기 전까지는 그것이 실제로 완료되지는 않는다.
그러나 메모리 일관성 모델은 어떤 것이 완료될 때를 구술하지는 않는다. 단지 그것이 관측될 수 있을 때
만을 구술한다.

 
(메모리 맵 I/O 위치를 접근하는 커널 디바이스 드라이버에서, 어떤 것이 실제로 완료될 때를 아는 것은
매우 중요할 수 있다. 여기에서는 더 깊숙히 다루지 않는다.)
 
관측 가능성은 다음과 같이 정의될 수 있다.
  • “메모리 위치에 write된 값이 그 이후에 수행된 Pn의 read 결과 값으로 리턴될 때, 
    해당 write가 관측자 Pn에 의해 관측되었다고 일컬어 진다.
  • 메모리 위치에서 read된 값이 그 이후에 수행된 Pm의 write로부터 아무런 영향을 받지 않을 때, 
    해당 read는 관측자 Pm에 의해 관측되었다고 일컬어 진다.”
이것을 좀 더 편한 방법으로 설명하면 이렇게 될 것이다. (여기에서 “you”와 “I는 CPU 코어이다)
  • 당신이 write 했던 것을 내가 read 할 수 있을 때, 나는 당신의 write를 관측한 것이다.
  • 내가 당신이 read 한 값에 더 이상 영향을 미칠 수 없을 때, 나는 당신의 read를 관측한 것이다.
write를 관측하는 개념은 직관적이다; 하지만 read를 관측하는 것은 다소 직관적이지 않다. (걱정하지 마라.
여러분에게 그 직관성이 커질 것이다.)
 
이것을 염두에 두고, 이제 ARM에 대해 이야기할 준비가 되었다.
 
 
2.1.4 ARM 약한 정렬(Weak Ordering)

 
ARM SMP는 약한 메모리 일관성weak memory consistency 보증을 제공한다. 그것은 load 또는 store가
서로에 대해 정렬되는 것을 보장하지 않는다.


쓰레드 1

쓰레드 2

A = 41

B = 1 // “A 준비됨

loop_until (B == 1)

reg = A

 
모든 어드레스가 초기에 0 이다는 것을 상기하라. “loop_until” 명령어는 우리가 B에서 1을 read할 때까지
반복해서 B를 read한다. 이곳의 개념은 쓰레드 1 이 A를 업데이트할 때까지 쓰레드 2가 기다리는 것이다.
쓰레드 1 이 A를 설정하고 그런 다음에 B를 1로 설정하면 데이터를 사용할 수 있다는 것을 가리킨다.
 
x86 SMP상에서 이 작업은 보장된다. 쓰레드 2 는 프로그램 순서대로 쓰레드 1 에 의해 만들어진 store를
관측할 것이다. 그리고 쓰레드 1 은 프로그램 순서대로 쓰레드 2 의 load를 관측할 것이다.
 
ARM SMP상에서, 그 load와 store는 임의의 순서로 관측될 수 있다. 모든 코드가 실행된 이후에, reg가 0 을
보유하는 것이 가능하다. 또한 reg가 41 을 보유하는 것도 가능하다. 여러분이 명시적으로 순서를 정의하지
않는다면, 어떤 결과가 나올 지는 알수 없다.
 
(다른 시스템상에서의 경험들을 통해 이러한 것에 대해 말하자면, ARM 메모리 모델은 거의 대부분의
측면에서 PowerPC와 동일하다.)

계속 :  
이름아이콘 두근두근
2011-05-06 18:22
이게 바로 SMP 관련해서 보고 계신 자료였군요. 잘보겠습니다:)
들풀 와...제가 쪽글에서 이야기 했던 걸 기억하고 계시는군요..~ 대단하십니다. 두근두근 닉네임을 볼 때마다 전 heartbeat 기술이 자꾸 생각나는데..왜 그럴까요?ㅎㅎ 주말 잘 보내세요..~ 5/6 22:41
   
이름아이콘 들풀
2011-08-31 17:12
다시금 SMP가 무척 중요한 시대로 접어드는 듯 합니다.
좀 더 많은 검토가 필요한 문서겠습니다.~
   
 
덧글 쓰기 0
3500
※ 회원등급 레벨 0 이상 읽기가 가능한 게시판입니다.