Atomic operation

Computer Science에서 atomic operation 이라는 용어는 상당히 자주 접한다.

Wikipedia 에서 atomic [1] 을 찾아보면  Linearizability [2] 이라는 페이지로 redirection 해준다.

그리고 [2] 에서 내용을 (내 마음대로) 해석해보자면:

 

Multiprocessor system에서 여러 CPU들이 공유자원 (특히 메모리)에 접근 할 때, 접근 순서를 의도적 또는 비 의도적으로 직렬화하여 의도치 않는 결과를 피하는 operation 을 atomic operation이라 한다.

 

사실 atomic 이라는 뜻만 보면 원자처럼 쪼개질 수 없는 연산 또는 수행 이라고 할 수 있지만 Computer science에서는 단순히 원자처럼 작은 단위라는 뜻 말고도 Mutual Exclusive 의 의미도 포함하고 있는 것이다.

 

이 글에서는 ARM architecture에서 어떻게 atmoic operation을 지원해주고 있는지 알아볼 것이다.

 

ARMv8에서는 아래와 같은 방법으로 atmoic operation을 지원하고 있다.

• Load-Exclusive/Store-Exclusive instructions

• Atomic instructions

  • Atomic memory operation

  • Swap

  • Compare-and-Swap

Load-Exclusive/Store-Exclusive instructions

Load-Exclusive/Store-Exclusive 명령어는 ARMv8 Reference Manual [3] [4] 에 이렇게 설명되어 있다:

 

The Load-Exclusive instructions mark the physical address being accessed as an exclusive access. This exclusive access mark is checked by the Store-Exclusive instruction, permitting the construction of atomic read-modify-write operations on shared memory variables, semaphores, mutexes, and spinlocks.

 

해석해보자면, LDREX 명령어를 통해 메모리에서 Register로 data를 읽어오면, 해당 메모리 block (block의 size는 implementation defined이지만 B.2.9.3, Marking and the size of the marked memory block 에 설명 되어 있다)은

mutual exclusive하게 access 되어야 하는 메모리이다" 라고 표시가 되고, 정말 mutual exclusive하게 access가 되었는지는 STREX 명령어를 실행 할 때, 검증된다는 내용이다.

 

사실 우리가 메모리에서 어떤 주소의 값을 읽어오는 이유는 그냥 값을 확인할 수도 있겠지만, 대부분 읽어와서 그 값을 수정하여 다시 그 메모리에 쓰는 경우가 많고 그 행위를, read-modify-write operation 이라고 부른다. 이 때, read-modify-write 이 3개의 operation을 하나의 atomic하게 수행할 수가 없으니, write할 때, 이 모든 수행이 atmoic (다르게 말하면 mutual exclusive) operation 으로 성공했는지 아니면 실패 했는지 알려준다는 것이다. 그러므로 LDREX 와 STREX 명령어 두개는 항상 하나의 쌍으로 불려야 한다.

 

이 때, LDREX 명령어에 대해서 좀만 자세히 말하자면, LDREX 는 해당 메모리 블럭에 기존에 있는 TAG를 지우고 새로운 TAG (다른 CPU에서 만들어 놓은 TAG는 지우고, 지금 LDREX 명령어를 수행하고 있는 CPU만을 위한 TAG)를 남겨 놓는다. 따라서 LDREX를 마지막에 수행하는 CPU가 결국 해당 STREX를 성공할 수 있고, 전에 TAG를 만들어 놓은 CPU에서는 STREX 명령어를 실패 하게 되는것이다.

 

위 그림을 보면, CPU0가 먼저 LDREX 명령어를 수행해서 해당 메모리 block에 TAG를 생성해 놓았다. 그 다음에 CPU1에서 TAG를 생성하면서 기존에 다른 CPU를 위한 TAG는 지운다. 따라서 CPU0 의 STREX 명령어는 실패하고, CPU1의 STREX명령어만 성공하게 되어 shared object (memory)를 여러 CPU들로부터 atomic operation을 보장 할 수 있게 된다. 그러면 CPU0 입장에서는 STREX 명령어가 실패했음을 알고, 다시 LDREX부터 수행하거나, 나중에 하거나 등 결정 하면 된다 (소프트웨어를 어떻게 디자인했느냐에 따라 달라질 것).

 

그리고 ARMv8 Manual에서도 이러한 atmoic operation support를 통해 아래와 같은 simple lock sample code를 제공하고 있다:

<LOCK>

Px
	SEVL
 	; invalidates the WFE on the first loop iteration
	PRFM PSTL1KEEP, [X1]
 	; allocate into cache in unique state
Loop
	WFE
	LDAXR W5, [X1] 	; read lock with acquire
	CBNZ W5, Loop 	; check if 0
	STXR W5, W0, [X1] 	; attempt to store new value
	CBNZ W5, Loop 	; test if store succeeded and retry if not
	; loads and stores in the critical region can now be performed
    
<UNLOCK>
Px
	; loads and stores in the critical region
	STLR WZR, [X1] ; clear the lock

Atomic instructions

ARMv8.1 버전부터는 FEAT_LSE2, Large System Extensions v2 이라는 기능이 추가되었고, ID_AA64MMFR2_EL1.AT register를 통해 이 기능이 구현되어있는지 확인 할 수 있다. 이 기능으로 Hardware 적으로 Atomic operation을 지원하게 되었다. 일단 이 기능의 원리를 이해하려면 Load-Acquire 그리고 Store-Release 라는 ARMv8의 메모리 접근 Concpet에 대해서 이해할 필요가 있다.

• Load-Acquire
• Store-Release

간략히 설명하면, LDR 또는 STR 명령어를 수행하면서 자동적으로 memory barrier를 수행하여, 개발자로 하여금 DMB instruction을 고려하지 않아도 되도록 만든 개념이다.

또한 기존에 atomic operation을 구현하기 위해 등작하였던 Read-Modify-Write operation을 하나의 명령어로 만들었다는 것을 알고 있어야 한다.

Atomic memory operation

• LDADD: atomic add instruction w/o Acquire nor Release
• LDADDA: atomic add instruction with Acquire
• LDADDAL: atomic add instruction with Acquire and Release
• LDADDL: atomic add instruction with Release

Swap

• SWP: swap instruction w/o Acquire nor Release
• SWPA: swap instruction with Acquire
• SWPAL: swap instruction with Acquire and Release
• SWPL: swap instruction with Release

CAS (Compare-and-Swap)

• CAS: CAS w/o Acquire nor Release
• CASA: CAS with Acquire
• CASAL: CAS with Acquire and Release
• CASL

[1] en.wikipedia.org/w/index.php?title=Atomic_(computer_science)&redirect=no

Atomic (computer science) - Wikipedia

[2] en.wikipedia.org/wiki/Linearizability

Linearizability - Wikipedia

[3] ARM DDI 0487F.c, ID072120, C.3.2.5, Load/Store unprivileged