Android Document  SDK old PDF 파일
Android SMP(3/7) - 이론:원자적 오퍼레이션
작성자
작성일 2011-05-02 (월) 22:10
ㆍ추천: 0  ㆍ조회: 10398      
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. 부록
 
 

 

2.3 원자적 오퍼레이션(Atomic Operations)

 
원자적 오퍼레이션은 일련의 단계들을 필요로 하는 오퍼레이션이 항상 단일 오퍼레이션인 것처럼 동작하게끔
보장한다. 예를 들어, 동시에 두 개의 쓰레드에 의해 동일한 변수에 비원자적non-atomic 증가(“++A”)가
실행되는 것을 생각해라.

쓰레드 1

쓰레드 2

reg = A

reg = reg + 1

A = reg

reg = A

reg = reg + 1

A = reg


만약 그 쓰레드들이 병렬로 위에서 아래로 실행된다면, 두 쓰레드 모두는 A에서 0을 load하고, 그것에
1을 증가시키고, 그리고 다시 store 하고, 최종 결과로 1을 남긴다. 만약 우리가 원자적 증가 오퍼레이션을
사용했다면, 최종 결과가 2가 되는 것이 보장될 것이다.

 

2.3.1 원자적 필수요소(Atomic Essentials)
 

ARM에서 32-bit 값을 load 하고 store 하는 것 같은 가장 필수적인 오퍼레이션들은, 32-bit 경계boundary
내에서 데이터가 정렬되는 한 본질적으로 원자적이다. 예를 들어 다음과 같다.


쓰레드 1

쓰레드 2

reg = 0x00000000

A = reg

reg = 0xffffffff

A = reg

 
CPU는 A가 0x00000000 또는 0xffffffff 을 보유할 것을 보장한다. 결코 0x0000ffff 또는 그 밖의 임의로 혼합된 
바이트들을 보유하지는 않을 것이다.

원자성 보장atomicity guarantee은 데이터가 정렬되지 않으면 상실된다. 잘못 정렬된 데이터는
캐쉬라인에 쪼개져 놓일 것이다. 그러므로 나머지 코어들은 쪼개진 절반이 독립적으로 업데이트되는 
것을 볼 수 있다. 중요하게, ARMv7 문서는 모든 바이트 접근, 16-bit 정렬 위치에 대한 16-bit 접근,
32-bit 위치에 대한 32-bit 접근에 대해 “단일 복사 원자성single-copy atomicity”을  제공한다고
표명하고 있다. 위치가 64-bit 정렬이면서 특수한 load/store 명령어가 사용되지 않는 경우에,
64-bit 접근은 원자적이지 않다. 멀티 쓰레드들이 기본타입primitive 배열 또는 묶음화된 구조체들에
비동기적 업데이트를 수행할 때 이 동작방식을 이해하는 것은 중요하다.
ARM 또는 x86에 32-bit 원자적 read 또는 원자적 write 함수들이 필요치 않다. 단지 간단한 load 또는 store만
하면 되는 완벽하게 이루어 진다.
 
메모리의 데이터에 대한 보다 더 복잡한 액션을 수행하는 오퍼레이션들은 총괄해서 read-modify-write(RMW)
명령어로 일컬어 진다. 왜냐하면 그것들은 데이터를 load하고, 임의의 방식으로 modify하고 그리고 다시
write하기 때문이다. CPU가 이것들을 구현하는 방식은 매우 광범위하다.
ARM은 “Load Linked / Store Conditional” 또는 LL/SC라 불리는 기법을 사용한다.
통상 linked 또는 locked load는 메모리에서 데이터를 read한다. 하지만 또한 물리적 메모리 주소를 
태깅함으로써 예약reservation 설정을 한다. 이러한 예약 설정은 다른 코어가 그 주소에 write를
시도할 때 제거된다. LL/SC를 수행하기 위해, 데이터는 예약 설정을 지닌 채로 read되고 modify 되며,
그리고 그런 다음에 데이터를 다시 write하기 위한 시도를 위해 조건적 store 명령어가 사용된다.
만약 예약 설정이 여전히 그 위치에 유효하다면, store는 성공한다; 그렇지 않다면 store는 실패한다.
LL/SC에 기초한 원자적 함수는 통상적으로 loop이다. 이것은 인터럽트를 사용하지 않고 그것이
달성될 때까지 전체 read-modify-write 순서를 재시도한다.
 
만약 이것이 이전 데이터에 오퍼레이션을 했다면, read-modify-write 오퍼레이션이 제대로 동작하지 않을
것이라는 것은 말할 필요도 없이 당연하다. 만약 두 개의 코어가 동일 주소에 원자적 증가를 수행한다면,
그리고 각각의 코어는 로컬 캐쉬에서 읽고 쓰기 때문에 그것 중 하나가 다른 것이 한 것을 볼 수 없다면,
그 오퍼레이션은 실제로 원자적이지 않다. CPU 캐쉬 일관성 규칙은 원자적 RMW 오퍼레이션들이 SMP
환경에서 원자적으로 남는 것을 가능하게 한다.
 
이것을 원자적 RMW 오퍼레이션이 메모리 장벽을 사용한다는 것을 의미하는 것으로 해석해서는 안 된다.
ARM에서 원자적인 것은 메모리 장벽 의미를 전혀 갖지 않는다. 단일 주소에 대한 일련의 원자적 RMW
오퍼레이션들은 다른 코어에서 프로그램 순서대로 관측될 것이지만, 원자적 비원자적 오퍼레이션들이
조합된 순서에 대해서는 어떠한 보장도 없다. [다른 주소에 대한 원자적 RMW 오퍼레이션들이 순서와
다르게 관측될 수 있는 지 여부에 대해 확신하지 마라. 순서와 다르게 관측될 수 있다고 가정하는 것이
가장 안전하다.]

 
종종 장벽과 원자적 오퍼레이션을 결합시키는 것이 타당하다. 다음 섹션은 이것을 더 자세히 설명한다.


2.3.2 원자적 + 장벽 결합(Atomic + Barrier Pairing)

 
통상적으로, 예제를 사용해서 논의를 실증하는 것이 유용하다. 우리는 spin lock이라 일컬어 지는 기본적인
상호 배제 원형mutual-exclusion primitive을 생각해 볼 것이다. (우리가 “lock” 이라고 말할) 메모리
주소는 초기에 0 을 보유한다고 여긴다. 하나의 쓰레드가 위험 구역critical section에서 코드를 실행하고자
할 때, 그것은 lock을 1 로 설정한다. 그리고 위험 구역내의 코드를 실행한다. 그런 다음에 다 실행했을 때
그것을 다시 0 으로 바꾼다. 만약 다른 쓰레드가 이미 lock을 1 로 설정했다면, 우리는 앉아서 lock 이 0 으로
바뀔 때까지 돈다spin.
 
이 작업을 하기 위해, 우리는 compare-and-swap이라 불리는 원자적 RMW 원형primitive을 사용한다.
그 함수는 메모리 주소, 기대했던 현재 값, 그리고 신규 값이라는 3개의 아규먼트를 갖는다. 만약 우리가
기대했던 값이 현재 메모리의 값과 일치한다면, 메모리의 값은 신규 값으로 대체된다. 그리고 기존 값이
리턴 된다. 만약 현재 값이 우리가 기대했던 것이 아니라면, 우리는 아무것도 변경하지 않는다. 이것에
작은 변화가 있는 것이 compare-and-set이라 일컬어 진다. 이것은 기존 값을 리턴하는 대신에 swap
성공 여부를 나타내는 boolean을 리턴한다. 두 가지 모두 우리가 필요한 것을 해 줄 것이다. 하지만
compared-and-set 예제가 조금 더 간단하다. 그래서 우리는 이것을 사용할 것이다. 그리고 그것을 이제
“CAS”라고 언급할 것이다.
 
(C와 같은 언어를 사용해서) spin lock 획득acquite은 아래와 같이 작성된다.
 

do {

success = atomic_cas(&lock, 0, 1)

} while (!success)

 

full_memory_barrier()

critical-section

 
만약 어떤 쓰레드가 lock을 보유하지 않고 있다면, 그 lock 값은 0 이 될 것이다. 그리고 CAS 오퍼레이션은
이제 우리가 lock을 가졌다는 것을 가리키기 위해 그것을 1 로 설정할 것이다. 만약 다른 쓰레드가 그것을
가지고 있다면, lock 값은 1 이 되어있을 것이다. 그리고 CAS 오퍼레이션은 실패할 것이다. 왜냐하면
기대했던 현재 값이 실제 현재 값과 일치하지 않기 때문이다. 우리는 루프를 돌면서 다시 시도한다.
(이 loop는 LL/SC 코드가 atomic_cas 함수 내에서 loop를 돌고 있지만, 그것 바깥에 있다는 것을 주목하라)
SMP상에서, spin lock은 작은 위험 구역을 보호할 때 유용한 방법이다. 만약 우리가 다른 쓰레드가
몇 개의 명령어들 수행하고 있고 그런 다음 그 lock을 해제한다는 것을 안다면, 우리는 차례를
기다리는 동안 몇 개의 사이클을 그냥 소진할 수 있다. 하지만, 만약 다른 쓰레드가 같은 코어에서
실행되는 일이 생긴다면, 그 다른 쓰레드가 (그것을 다른 코어로 옮기거나 또는 우리를 선점preempting
함으로써)
OS에 의해 다시 스케줄 될 때까지는 진도를 나갈 수 없기 때문에, 우리는 그저 시간을
낭비하게 된다. 제대로 된 spin lock 구현은 낙관적으로 생각했을 때 몇 번 회전한 후, 나머지
쓰레드가 끝날 때까지 기다리는 동안 sleep 하는 것을 가능하게 하는 (Linux의 futex와 같은) OS
원형에 의존할 것이다. 단일 프로세서상에서 여러분은 결코 spin을 원치 않는다. 번잡을 피하기
위해 우리는 이 모든 것을 무시하고 있다.
 
메모리 장벽은 다른 쓰레드가 위험 구역에서 임의의 load 또는 store를 관측하기 전에 lock 획득을 관측하게끔
하기 위해 필요하다. 그 장벽이 없이는, 그 lock이 보유되지 않는 한 메모리 접근은 관측될 수 없다.
 
여기에서 full_memory_barrier 호출은 실제로 두 개의 독립적 오퍼레이션을 한다. 첫째로, 그것은 CPU의
전제full 장벽 명령어를 제기한다. 두 번째로, 그것은 컴파일러에게 장벽 주변의 코드를 재정렬하는 것이
허용되지 않는다는 것을 지시한다. 이렇게 해서, 우리는 위험 구역 내의 어떤 것 이전에 atomic_cas 호출이
실행될 것이라는 것을 알 수 있다. 이 컴파일러 재정렬 장벽이 없다면, 컴파일러는 코드를 생성하는 방법에서
많은 자유를 갖는다. 그리고 컴파일 된 코드 안의 명령어의 순서는 소스 코드 안의 순서와 많이 다를 수 있다.
 
물론, 우리는 또한 lock 이 해제된 이후, 위험 구역에서 수행되는 어떤한 메모리 접근도 관측되지 않게끔
만들고자 한다. 간단한 spin lock 전체 버전이 있다.

do {

success = atomic_cas(&lock, 0, 1) // acquire

} while (!success)

 

full_memory_barrier()

 

critical-section

 

full_memory_barrier()

atomic_store(&lock, 0) // release


우리는 lock을 해제하기 바로 전에 두 번째 CPU/컴파일러 메모리 장벽을 바로 수행한다. 그러므로 위험
구역 내의 load와 store는 lock이 해제되기 전에만 관측된다.
 
앞에서 언급했듯이, atomic_store 오퍼레이션은 ARM과 x86 상의 간단한 설정이다.
원자적 RMW 오퍼레이션들과 달리, 우리는 다른 쓰레드가 이 값을 바로 보게끔 보장할 수는 없다.
그렇지만 문제는 안 된다. 왜냐하면 우리는 다른 쓰레드가 위험 구역에 진입하지 못하게 하는 것만 필요하기
때문이다. 다른 쓰레드는 store 0 을 관측할 때까지 밖에서 머무를 것이다. 만약 다른 쓰레드가 그것을
관측하는데 조금 걸린다면, 좀 더 오래 돌기는spin 하겠지만 여전히 올바르게 코드를 실행할 것이다.
[답을 못한 질문이 있다: 만약 우리가 원자적 store를 하기 위해 RMW 오퍼레이션을 사용했다면 다른
쓰레드가 우리가 lock을 해제하자마자 볼 수 있는가? ARM의 LL/SC 에서 캐쉬 일관성은 atomic_cas
load가 store를 최대한 빨리 관측하는 것을 의미하는가, 또는 값을 store하기 위해 LL/SC를 사용함으로
우리가 어떤 이득을 얻을 수 있는가? 나는 load-linked 명령어가 그 일관성 이슈를 관리한다는 가정에서,
우리가 이익을 볼 것이라고 생각지 않는다. 하지만 측정할 가치가 있을 것이다. CPU 구현들 간에
차이가 있을 것이다.]

 
원자적 오퍼레이션과 장벽 호출을 단일 함수로 결합하는 것이 안전하다. 이것은 또 다른 장점을 제공하는데,
조만간 확인할 수 있을 것이다.


2.3.3 획득과 해제(Acquire and Release)
 
 
spinlock을 획득acquire할 때는, 원자적 CAS를 수행하고 그런 뒤에 장벽을 놓는다. 반면 spinlock을
해제release할 때는 장벽을 세우고 그 뒤에 원자적 store 수행한다. 이것은 특별한 명명 규약에 영감을
준다: 장벽이 뒤에오는(수반되는) 오퍼레이션은 “획득acquiring” 오퍼레이션이다. 반면에 장벽이 앞에
오는 오퍼레이션은 “해제releasing” 오퍼레이션이다. (이름은 직관적이지 않기 때문에 spinlock 예제를
확고히 염두에 두고 수행하는 것이 현명하다.)

 
이것을 염두에 두고 spin lock 예제를 고치기:


do {

success = atomic_acquire_cas(&lock, 0, 1)

} while (!success)

 

critical-section

 

atomic_release_store(&lock, 0)

 
이것은 좀 더 간소하고 읽기 쉽다. 하지만 이렇게 하는 실제 이유(동기)는 이제 우리가 수행할 수 있게
되는 한 쌍의 최적화 때문이다.
 
먼저, atomic_release_store를 상기하라. 우리는 lock 워드에 0 을 store 하는 것이 그 위에 있는 위험
구역내의 임의의 load 또는 store 이후에 관측되게끔 하는 것이 필요하다. 바꿔 말해, 우리는 load/store와
store/store 장벽이 필요하다. 이전 섹션에서 우리는 x86 SMP에서는 이것들이 불필요하다는 것을 배웠다. 
- x86 SMP에선 오직 store/load 장벽만 요구된다. 그러므로 x86에서 atomic_release_store의 구현은
단순한 store를 수반되는 그저 컴파일러의 재정렬 장벽일 뿐이다. 어떤 CPU 장벽도 필요하지 않다.
 
두 번째 최적화는 (Itanium은 같은 몇몇 CPU들에는 장점이 될 수 있음에도 불구하고) 거의 컴파일러에
적용된다. 기본적 원리는 코드가 획득acquire과 해제release 장벽을 넘어서 이동할 수 있다는 것이다.
하지만 오직 한쪽 방향으로만 움직일 수 있다.

우리가 지역적으로locally 보이는 것과 전역적으로globally 보이는 혼합된 메모리 접근과 뿐만 아니라
약간의 여러 가지 종류의 연산을 가진다고 가정하자.

local1 = arg1 / 41

local2 = threadStruct->field2

threadStruct->field3 = local2

 

do {

success = atomic_acquire_cas(&lock, 0, 1)

} while (!success)

 

local5 = globalStruct->field5

globalStruct->field6 = local5

 

atomic_release_store(&lock, 0)

 
여기에서 우리는 두 개의 완전하게 독립된 오퍼레이션 집합을 본다. 첫 번째 집합은 threadlocal 데이터
구조체에 오퍼레이션 한다. 그러므로 우리는 다른 쓰레드와의 충돌을 고려하지 않는다. 두 번째 집합은
글로벌 데이터 구조체에 오퍼레이션 한다. 그것은 lock을 사용해서 보호되어야 한다.
 
원자적 오퍼레이션에서 전체full 컴파일러 재정렬 장벽은 프로그램 순서가 lock 경계들 사이에서 소스 코드
순서에 일치하게끔 할 것이다. 하지만, 컴파일러가 명령어를 끼우는 것을 허용하는 것은 성능을 개선하다.
메모리로부터 load는 느릴 수 있다. 하지만 CPU는 load가 완료될 때까지 기다렸다가 그 load의 결과를
필요로 하지 않는 명령어들은 계속 실행할 수 있다. 위의 코드는 대신 아래와 같이 작성되었다면 더 빨리
실행될 수 있다.

do {

success = atomic_acquire_cas(&lock, 0, 1)

} while (!success)

 

local2 = threadStruct->field2        

local5 = globalStruct->field5

local1 = arg1 / 41

threadStruct->field3 = local2

globalStruct->field6 = local5

 

atomic_release_store(&lock, 0)


우리는 약간 관련 없는 연산을 하는 두 개의 load를 시작한다. 그런 다음에 load를 이용할 명령어를 실행한다.
만약 정수 나누기가 하나의 load 보다 시간이 더 적게 걸린다면, 우리는 기본적으로 이것을 공짜로 얻는다.
따라서 이것은 CPU가 load가 끝나길 기다리면서 멈추는 기간 동안에 일어난다.
 
모든 오퍼레이션들이 위험 구역 내에서 일어나는 것에 주목하라. 어떤 threadStruct 오퍼레이션들도 현재
쓰레드 밖에서 보이지 않기 때문에, 우리가 여기서 마칠 때까지 그 밖의 어떤 것도 이것을 볼 수 없다.
그러므로 이것들이 발생할 때 틀림없이 상관없다.
 
일반적으로, 오퍼레이션을 위험 구역으로 옮기는 것은 항상 안전하다. 하지만 오퍼레이션을 위험 구역 밖으로
옮기는 것은 결로 안전하지 않다. 다른 방법으로 놓아라. 여러분은 코드를 획득acquire 장벽 아래로 옮길 수
있다. 그리고 해제release 장벽을 위로 옮길 수 있다. 만약 원자적 오퍼레이션들이 전체full 장벽을 사용했다면,
이런 종류의 이동은 가능하지 않을 것이다.
이전 시점으로 돌아가서, 우리는 x86에서 모든 load는 load를 획득하는 것이고, 그리고 모든 store는
store를 해제하는 것이라고 서술할 수 있다. 그 결과는 다음과 같다.
    • Load는 서로 간에 재정렬되지 않을 수 있다.
      여러분은 load를 다른 load의 획득 장벽 위로 옮길 수 없다.
    • Store는 서로 간에 재정렬되지 않을 수 있다.
      왜냐하면 여러분이 store를 다른 store의 해제 장벽 아래로 옮길 수 없기 때문이다.
    • Load에 수반되는 store는 재정렬 될 수 없다.
      왜냐하면 어떤 명령어도 그것을 참아낼 수 없기 때문이다.
    • Store에 수반되는 load는 재정렬될 수 있다.
      왜냐하면 각각의 명령어는 그 방향으로 다른 것을 넘어서 이동할 수 있기 때문이다.
따라서, 여러분은 오직 x86 XMP에서 store/load 장벽만 필요할 뿐이다.
획득acquire과 해제release를 사용해서 원자적 오퍼레이션들을 표시하는 것은 장벽이 원자적 오퍼레이션
이후 또는 이전에 실행되어야 하는 것만을 설명할 뿐만 아니라 컴파일러에게 허용되는 코드 재정렬 범위도
설명한다.

계속 :

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