Android Document  SDK old PDF 파일
Android SMP(7/7) - 부록:Android Atomic API
작성자
작성일 2011-05-02 (월) 20:00
ㆍ추천: 0  ㆍ조회: 10960      
IP: 121.xxx.76

 
 
 
목차
 
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. 부록
 
 

4. 부록(Appendix)



4.1 SMP 실패 예제
 

이 문서는 이론적으로 발생할 수 있는 “기이한” 많은 것들을 설명하고 있다. 만약 여러분이 이러한 이슈가
실제인지 확신이 없다면 실용적 예제가 유용할 수 있다.
 
Bill Pugh’s Java 메모리 모델 웹사이트( http://www.cs.umd.edu/~pugh/java/memoryModel/ )에
이것에 대한 약간의 테스트 프로그램이 있다. 하나의 흥미로운 테스트가 ReadAfterWrite.java 이다.
 
이것은 다음과 같다.


쓰레드 1

쓰레드 2

for (int i = 0; i < ITERATIONS; i++) {

a = i;

BB[i] = b;

}

for (int i = 0; i < ITERATIONS; i++) {

b = i;

AA[i] = a;

}

 
이곳에서 a와 b는 volatile int로 선언된다. 그리고 AA와 BB는 일반적인 integer 배열이다.
 
이것은 volatile에 값이 write된 이후에, 그 volatile에서의 다음 번 read가 새로운 값을 보게끔 VM 하는지를
알아보기 위한 시도를 한다. 테스트 코드는 이 loop를 백만 번 또는 그 정도 횟수로 실행한다.
그리고 그런 다음에 일관성이 없는 결과들을 검색한다.
 
실행의 끝나면, AA와 BB는 점차 증가하는 integer들로 채워 질 것이다. 쓰레드들은 예측할 수 있는 방식대로
번갈아 실행되지 않을 것이다. 하지만 우리는 배열의 내용물들간의 관계는 단언할 수 있다.
 
예제에 대해서, 다음과 같은 실행 조각을 고려해 봐라.

쓰레드 1

쓰레드 2

(initially a == 1534)

a = 1535

BB[1535] = 165

a = 1536

BB[1536] = 165

 

 

 

 

a = 1537

BB[1537] = 167

(initially b == 165)

 

 

 

 

b = 166

AA[166] = 1536

b = 167

AA[167] = 1536


 
(하나의 쓰레드의 결과가 다른 쓰레드에게 보여져야 할 때를 더욱 명확히 할 수 있도록 쓰레드가 바뀌는
것처럼 이것을 작성했다. 그러나 실제로 이런 경우는 없을 것이다.)
 
쓰레드 2 에서 AA[166]의 할당assignment을 살펴봐라. 우리는 쓰레드 2 가 166번째 반복iteration되었던
곳에서의 실제를 포착하고 있다. 쓰레드 1 은 1536번째 반복iteration에 있다는 것을 볼 수 있다.
그 다음으로 한 단계 더 나아가보면, 쓰레드 1 이 1537번째 반복iteration되는 시점에서, 쓰레드 1 쓰레드 2
166번째(또는 그 이후) 반복iteration되었음을 보았다는 것으로 여겨진다. BB[1537]은 167을 보유했다.
그러므로 이 결과는 수행된 결과를 보여주는 것이다.
 
이제 b에 volatile write 관측이 실패하는 것을 추측해 봐라.

쓰레드 1

쓰레드 2

(initially a == 1534)

a = 1535

BB[1535] = 165

a = 1536

BB[1536] = 165

 

 

 

 

a = 1537

BB[1537] = 165 // stale b

(initially b == 165)

 

 

 

 

b = 166

AA[166] = 1536

b = 167

AA[167] = 1536

 


이제, BB[1537]은 우리가 기대했던 것보다 더 작은 값인 165를 보유한다. 그러므로 우리는 문제를 알게 된다.
간단명료하기 표현하면, for i=166, BB[AA[i]+1] < i. 인 경우이다. (이것은 또한 쓰레드 2가 a에 write를
관측하는 것을 실패함을 캐치한다. 예를 들어, 만약 우리가 update를 놓치고 AA[166] = 1535를 할당하면,
우리는 BB[AA[166]+1] == 165를 얻게 될 것이다.)

 
만약 여러분이 SMP ARM 디바이스상의 Dalvik (안드로이드 3.0 Honeycomb 또는 그 이후)하에서 테스트
프로그램을 실행한다면, 그것은 결코 실패하지 않을 것이다. 만약 여러분이 a와 b의 선언에 volatile 워드를
제거한다면, 그것은 일관되게 실패할 것이다. 해당 프로그램은 VM이 a와 b 접근 시 순차적으로 일관된
정렬을 제공하는지를 살피기 위한 테스트이다. 그러므로 여러분은 오직 변수가 volatile일 때만 올바른
동작을 보게 될 것이다. (이것은 또한 여러분이 코드를 단일 프로세서에서 실행하거나 또는 그 밖의 어떤
것들이 CPU를 충분히 사용하고 있어서 커널이 테스트 쓰레드들을 별도의 코어들에 스케줄 하지 않고
실행될 때만 성공할 것이다.)

 
만약 수정된 테스트를 몇 번 수행한다면, 여러분은 항상 같은 곳에서 실패한다는 것을 알게 될 것이다.
해당 테스트는 일관되게 실패한다. 왜냐하면 그것이 오퍼레이션을 수백만 번을 수행해서 오직 단 한번의
순서가 바뀐 접근을 살피기 때문이다. 실제로, 실패는 빈번하지 않을 것이며 위치잡기도 어렵다.
이 테스트 프로그램은 만약 잘 풀린다면 깨진 VM에서도 매우 잘 성공할 것이다.


4.2 동기화 store 구현하기(Implementing Synchronization Stores)

 
(이것은 대부분의 프로그래머가 구현하게 되는 것은 아니다, 그러나 이러한 논의는 이해에 도움이 된다.)
 
일단 다시 Java에서 volatile 접근을 생각하자. 이전에 우리는 load 획득과 store 해제와 같은 유사한
것들을 참조했다. 그것은 시작점이었지 전체 이야기를 언급한 것은 아니었다.
 
우리는 Dekker의 알고리즘의 코드 조각을 가지고 시작한다. 초기에 flag1과 flag2 모두 false이다.


쓰레드 1

쓰레드 2

flag1 = true

if (flag2 == false)

critical-stuff

flag2 = true

if (flag1 == false)

critical-stuff


 
flag1과 flag2는 volatile boolean 필드로 선언되었다. load를 획득하는 것과 store를 해제하는 규칙은
알고리즘을 깨고 각각의 쓰레드에서 재정렬된 접근들을 허용할 것이다. 다행히도, JVM은 여기에서
비공식적으로 이야기 할 몇 가지를 가지고 있다.

  • volatile 필드에 write는 이어지는 모든 동일 필드의 read에 앞서 일어난다 happens-before.
    (예를 들어, 만약 하나의 쓰레드가 하나의 flag를 업데이트하고, 그런 다음에 다른 쓰레드가
    그 flag를 읽는다면, 그 reader가 해당 write를 보는 것이 보장된다는 의미이다.)
  • 모든 실행은 모든 volatile 필드 접근에 걸친 전체적 순서를 갖는다. 그 순서는 프로그램 순서와
    일치된다.
하나로 합쳐서 생각하면, 우리들의 예제에서 volatile 접근은 모든 쓰레드에 의해 프로그램 순서로
관측되어야 한다는 것을 이 규칙은 말하고 있다. 따라서, 우리는 critical-stuff을 동시에 실행하는
쓰레드를 결코 보지 못할 것이다.
이것에 대해 생각할 다른 면은 데이터 경쟁data race에 관한 것이다. 데이터 경쟁은 만약 동일
메모리 위치에 대하여, 서로 다른 쓰레드에 의해 두 개의 접근이 순서가 매겨지지 않는다면 일어난다.
적어도 그것들 중 하나는 메모리 위치에 저장한다. 그리고 적어도 그것들 중 하나는 동기화 액션이
아니다. 메모리 모델이 선언하는 것은 데이터 경쟁으로부터 자유로운 프로그램은 마치 순차적으로
일관된 기기machine에 의해 실행되는 것처럼 동작해야 한다는 것이다. flag1과 flag2가 모두
volatile이고, 그래서 volatile 접근이 동기화 액션으로 고려되기 때문에, 여기에서 데이터 경쟁은
존재하지 않으며, 이 코드는 순차적으로 일관된 방식으로 실행되어야 한다.
 
앞의 섹션에서 봤듯이, 우리는 두 개의 오퍼레이션 사이에 store/load 장벽을 삽입할 필요가 있다.
VM에서 volatile 접근에 대한 코드의 실행은 아래와 같이 보일 것이다.

volatile load

volatile store

reg = A

load/load + load/store barrier

 

store/store barrier

A = reg

store/load barrier

 
volatile load는 마치 load 획득과 같다. volatile store는 store 해제와 같다. 그러나 우리는 pre-store
장벽에서 load/store를 생략했다. 그리고 뒤쪽에 store/load를 추가했다.
 
하지만 우리가 실제로 보장할 것은, (쓰레드 1을 사용하는 예제에서) flag1 에 대한 write가 flag2의 read
전에 관측되는 것이다. 우리는 대신에 volatile load 전에 store/load 장벽을 세울 수 있다. 그리고 동일한
결과를 얻는다. 하지만 load는 store보다 수가 많기 때문에 그것에 store를 연계하는 것이 최선이다.
 
또한 원자적 오퍼레이션(예를 들어, ARM에서 LL/SC)을 사용해서 volatile store를 구현하고 store/load
장벽을 건너뛰는 것이 가능하다. 원자적 오퍼레이션은 필수적으로 타겟 주소에 대한 store/load 장벽을
제공한다.
 
(이것들 중 많은 것은 Dong Lee와 그의 “JSR-133 Cookbook for Compiler Writers” 페이지에 따른다)


4.3 안드로이드 Atomic API

 
이것은 2011년 1월, 3.0(Honeycomb)에 있는 내부 전용인 안드로이드의 atomic API의 스냅샷이다.
 
원래의 API는 멀티 쓰레드 단일 프로세서 환경을 위해 개발되었다. 함수 이름의 대부분은 SMP 업데이트가
만들어졌을 때 변화지 않았다. 업데이트의 목적은 기존의 소스 코드를 가능한 한 바꾸지 않고 SMP를
지원하도록 하는 것이다.
 
int32_t android_atomic_acquire_load(volatile const int32_t* addr);
int32_t android_atomic_release_load(volatile const int32_t* addr);
void android_atomic_acquire_store(int32_t value, volatile int32_t* addr);
void android_atomic_release_store(int32_t value, volatile int32_t* addr);
 
int32_t android_atomic_inc(volatile int32_t* addr);
int32_t android_atomic_dec(volatile int32_t* addr);
int32_t android_atomic_add(int32_t value, volatile int32_t* addr);
int32_t android_atomic_and(int32_t value, volatile int32_t* addr);
int32_t android_atomic_or(int32_t value, volatile int32_t* addr);
 
int android_atomic_acquire_cas(int32_t oldvalue, int32_t newvalue, volatile int32_t* addr);
int android_atomic_release_cas(int32_t oldvalue, int32_t newvalue, volatile int32_t* addr);
 
#define android_atomic_write android_atomic_release_store
#define android_atomic_cmpxchg android_atomic_release_cas
 
이것은 기본적인 32-bit load/store 오퍼레이션과 산술, 그리고 bitwise RMW 호출을 제공한다.
“releasing” 장벽을 제공하는 장벽 타입을 사용해서 명시적으로 어떤 것도 레벨화되지 않는다.
이 경우에 획득과 해제 변종들이 필요한 곳에, 장벽 타입이 함수에 추가되었다.
 
모든 addr 아규먼트는 volatile 로 선언되었다는 것에 주목하라. 이것은 함수가 inline으로 취급될 지라도,
컴파일러가 원자적 load/store 호출에서 사소한 오퍼레이션을 생략하지 못하게 할 것이다.
 
우리들의 CAS(compare-and-set) 오퍼레이션은 swap이 성공되면 0을 리턴한다.
이것은 “success”라기 보다는 차라리 boolean “failed” 지시를 만들어 낸다.
이 규약은 ARM STREX 명령어의 동작과 일치한다. 그러나 다른 원자적 함수 라이브러리들과는 다르다.
 
(Mac OS X 예제 같은) 어떤 시스템에서는 addr 아규먼트가 앞에 놓이고, (Win32 같은) 다른 것에서는
그것은 뒤에 놓인다.
 
여기에 64-bit 원자적 오퍼레이션의 정의는 없다. 왜냐하면 우리들의 이전 플랫폼에서 이것들을 지원한
것이 없었기 때문이다. ARM은 64-bit LL/SC 명령어를 ARMv6K까지는 지원하지 않는다. 이것은 G1류의
하드웨어보다 더 새로운 것이다.

 

읽기(Further Reading)

 
다음의 웹 페이지와 문서들은 더 깊고 넓은 영역을 다룬다. 보다 더 일반적으로 유용한 글들이 아래의
목록의 위쪽에 배치되었다.



Shared Memory Consistency Models:

A Tutorial Written in 1995 by Adve & Gharachorloo, this is a good place to start if you want to dive more deeply into memory consistency models.
www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf

Memory Barriers
Nice little article summarizing the issues.
http://en.wikipedia.org/wiki/Memory_barrier
Threads Basics
An introduction to multi-threaded programming in C++ and Java, by Hans Boehm. Excellent discussion of data races and basic synchronization methods.
http://www.hpl.hp.com/personal/Hans_Boehm/c++mm/threadsintro.html
Java Concurrency In Practice
Published in 2006, this book covers a wide range of topics in great detail. Highly recommended for anyone writing multi-threaded code in Java.
http://www.javaconcurrencyinpractice.com/
JSR-133 (Java Memory Model) FAQ
A gentle introduction to the Java memory model, including an explanation of synchronization, volatile variables, and construction of final fields.
http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html
Overview of package java.util.concurrent
The documentation for the java.util.concurrent package. Near the bottom of the page is a section entitled “Memory Consistency Properties” that explains the guarantees made by the various classes.
http://java.sun.com/javase/6/docs/api/java/util/concurrent/package-summary.html
Java Theory and Practice: Safe Construction Techniques in Java
This article examines in detail the perils of references escaping during object construction, and provides guidelines for thread-safe constructors.
http://www.ibm.com/developerworks/java/library/j-jtp0618.html
Java Theory and Practice: Managing Volatility
A nice article describing what you can and can’t accomplish with volatile fields in Java.
http://www.ibm.com/developerworks/java/library/j-jtp06197.html
The “Double-Checked Locking is Broken” Declaration
Bill Pugh’s detailed explanation of the various ways in which double-checked locking is broken. Includes C/C++ and Java.
http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
[ARM] Barrier Litmus Tests and Cookbook
A discussion of ARM SMP issues, illuminated with short snippets of ARM code. If you found the examples in this document too un-specific, or want to read the formal description of the DMB instruction, read this. Also describes the instructions used for memory barriers on executable code (possibly useful if you’re generating code on the fly).
http://infocenter.arm.com/help/topic/com.arm.doc.genc007826/Barrier_Litmus_Tests_and_Cookbook_A08.pdf
ISO/IEC JTC1 SC22 WG21 (C++ standards) 14882 (C++ programming language), chapter 29 (“Atomic operations library”)
Draft standard for C++ atomic operation features. Android doesn’t support these yet.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3090.pdf
ISO/IEC JTC1 SC22 WG14 (C standards) 9899 (C programming language) chapter 7.16 (“Atomics ”)
Draft standard for ISO/IEC 9899-201x C atomic operation features. Android doesn’t support these yet. (See also n1484 for errata.)
http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1425.pdf
Dekker’s algorithm
The “first known correct solution to the mutual exclusion problem in concurrent programming”. The wikipedia article has the full algorithm, with a discussion about how it would need to be updated to work with modern optimizing compilers and SMP hardware.
http://en.wikipedia.org/wiki/Dekker's_algorithm
Comments on ARM vs. Alpha and address dependencies
An e-mail on the arm-kernel mailing list from Catalin Marinas. Includes a nice summary of address and control dependencies.
http://linux.derkeiler.com/Mailing-Lists/Kernel/2009-05/msg11811.html
What Every Programmer Should Know About Memory
A very long and detailed article about different types of memory, particularly CPU caches, by Ulrich Drepper.
http://www.akkadia.org/drepper/cpumemory.pdf
Reasoning about the ARM weakly consistent memory model
This paper was written by Chong & Ishtiaq of ARM, Ltd. It attempts to describe the ARM SMP memory model in a rigorous but accessible fashion. The definition of “observability” used here comes from this paper.
http://portal.acm.org/ft_gateway.cfm?id=1353528&type=pdf&coll=&dl=&CFID=96099715&CFTOKEN=57505711
The JSR-133 Cookbook for Compiler Writers
Doug Lea wrote this as a companion to the JSR-133 (Java Memory Model) documentation. It goes much deeper into the details than most people will need to worry about, but it provides good fodder for contemplation.
http://g.oswego.edu/dl/jmm/cookbook.html
The Semantics of Power and ARM Multiprocessor Machine Code
If you prefer your explanations in rigorous mathematical form, this is a fine place to go next.
http://www.cl.cam.ac.uk/~pes20/weakmemory/draft-ppc-arm.pdf

 
전체 내용 보기 :
 
 
덧글 쓰기 0
3500
※ 회원등급 레벨 0 이상 읽기가 가능한 게시판입니다.