[컴퓨터구조#12-1] 동기화 (Synchronization) - Lock, Atomic exchange, LL-SC, Transactional Memory

참고: Computer Architecture: A Quantitative Approach (5th edition) - 5.5.

이번 글에서는 동기화에 대해 알아볼 것이다.

목차

1. Lock
2. Lock을 위한 하드웨어 지원: exch
3. Lock을 위한 하드웨어 지원: LL&SC
4. Transaction Memory

---

1. Lock

프로그래밍 시 Lock을 사용하는 이유는, 병렬 프로그램에서 *data race condition을 회피하기 위함이다. 

• *data race condition: 공유 메모리 시스템에서, 여러 쓰레드가 정해지지 않은 순서로 공유 메모리 위치에 접근하는 경우. 이때 적어도 하나의 접근은 쓰기인 경우.
• 예시) total_count가 global variable인 경우, 적절한 동기화 없이 모든 쓰레드가 total_count += local_count 를 실행하는 상황

고도로 병렬적이면서 정확하게 동기화된 프로그램을 작성하기란 매우 어렵다. 정확한 병렬 프로그램에서는, data race가 없는 상황, 즉 공유 데이터는 반드시 lock에 의해 보호받아야 한다.

Locking과 관련된 일반적인 문제들에는 priority inversion, lock convoying, deadlock 등이 있다. 또한, lock의 granularity도 중요한 이슈 중 하나이다.

Coarse-grained Lock

여러 프로세서가 공유하는 큰 데이터 구조에 대해 하나의 lock만 존재하는 경우. 이 데이터 구조는 모든 프로세서에 의해 사용되지 않을 수 있다. 프로그래밍하기는 간단하지만, 락 경합으로 인해 성능은 좋지 않다.

• 전체 데이터 구조에 lock → 정확하지만 느림
• 여러 쓰레드에 의한 가능한 어떤 간섭이든 회피할 수 있으므로, 정확성을 보장하기 쉽다.
• 하지만, 데이터에 한번에 하나의 쓰레드만 접근 가능하므로 병렬성이 제한된다.

예를 들면, accounts가 여러 쓰레드 간 공유되는 array라 가정하면 다음과 같은 상황이 coarse-grained lock이다.

struct acc_t accounts [MAX_ACCT]
acquire (lock);
if (accounts[id].balance >= amount) {
	accounts[id].balance -= amount;
    	give_cash();
 }
 release (lock);

Fine-grained Lock

큰 데이터 구조의 서로 다른 부분에 대해 많은 fine-grained lock이 존재하는 경우. 해당 데이터 구조의 서로 다른 부분들은 동시에 여러 프로세서에 의해 업데이트될 수 있다. 많은 락을 유지해야 하므로 프로그래밍이 어렵다.

• 공유 데이터 구조의 일부분을 lock → 더 병렬적이지만 프로그래밍이 어렵다.
• 한번에 한 프로세서에 의해 lock되는 부분이 적어지므로 더 빠르다.
• 하지만, 정확하게 만들기 어려워 실수할 가능성이 높고, 한 task에 여러 lock을 필요로 하는 경우 deadlock이 발생할 수 있다.

다음과 같은 상황이 예시가 될 수 있다. 위와 달리 단순히 acquire(lock)이 아닌 각 account에 대해 acquire(accounts[id].lock)이 된 것을 확인할 수 있다.

struct acc_t accounts [MAX_ACCT]
acquire (accounts[id].lock);
if (accounts[id].balance >= amount) {
	accounts[id].balance -= amount;
    	give_cash();
 }
 release (accounts[id].lock);

이러한 Fine-grained lock의 경우 몇 가지 어려움이 발생할 수 있다. 이에 대해 자세히 알아보자.

1) 한 task에 여러 개의 lock이 필요할 수 있다.

• 예를 들면, 다음과 같은 계좌 이체의 경우 accounts[id_from].lock, accoutns[id_to].lock 두 개의 lock이 필요하다.

acquire (accounts[id_from].lock);
acquire (accounts[id_to].lock);
if (accounts[id_from].balance >= amount) {
	accounts[id_from].balance -= amount;
    	accounts[id_to].balance += amount;
        }
release (accounts[id_from].lock);
release (accounts[id_to].lock);

2) 공유 자원에 대한 circular wait 상황인 deadlock이 발생할 수 있다.

• 예를 들어, 2개의 쓰레드가 다음과 같은 시나리오로 계좌이체 요청을 동시에 처리할 수 있다.
  • Thraed 0: id_from = 10, id_to = 20
  • Thread 1: id_from = 20, id_to = 10
  • 이 경우 deadlock이 발생하게 된다.

Thread 0	Thread 1
acquire (accounts[10].lock) // try acquire accounts[20].lock // waiting for accounts[20].lock	acquire (accounts[20].lock) // try acquire accounts[10].lock // waiting for accounts[10].lock

• 이러한 deadlock 상황을 피하는 방법 중 하나는, 모든 lock을 같은 순서로 획득하는 것이다.

id_first = min (id_from, id_to)
id_second = max (id_from, id_to)
acquire (accounts[id_first].lock);
acquire (accounts[id_second].lock);
if (accounts[id_from].balance >= amount) {
	accounts[id_from].balance -= amount;
	accounts[id_to].balance += amount;
}
release (accounts[id_second].lock)
release (accounts[id_first].lock)

3) 기타 다른 경우들: lock이 제대로 프로그램되지 않은 경우 race condition을 일으킬 수 있다, ....

공유 메모리에서의 lock

spin lock: 프로세서가 lock을 얻으려는 loop를 돌면서 계속해서 lock을 획득하려고 하는 것. lock variable 값이 0이면 free인 상태, 1이면 사용 중인 상태이다.

• lock acquire
  • lock variable은 R1이다.

lockit:	li	R2,#1		;R2에 1 저장
	lw	R3, 0(R1)	;R1값을 R3에 load var
	bnez	R3, lockit	;R3!=0이면 lock not free -> spin
	sw	R2,0(R1)	; lock acquire: R1에 1(=R2값) 저장

• lock release

sw	R0, 0(R1)	;R1에 0 저장

Atomic Load&Store의 필요성

아래와 같은 시나리오를 생각해 보자.

Thread 0	Thread 1
li R2,#1	li R2, #1
lw R3, 0(R1)	lw R3, 0(R1)
bnez R3, lockit	bnez R3, lockit
sw R2, 0(R1)
	sw R2, 0(R1)

두 쓰레드 모두 lock variable R1을 불러오고, 모두 R1에 1을 저장할 수 있다. 즉 두 쓰레드에서 동시에 lock varaible에 overwrite가 가능하며 lock 획득이 가능하다. 하지만, lock의 경우 load(lw)와 store(sw) 사이에 값이 바뀌면 안 된다. 따라서, 원자적인 load와 store가 필요하게 된다.

 

2. Lock을 위한 하드웨어 지원: exch

• Atomic exchange: 레지스터 안에 있는 값과 메모리 안에 있는 값을 교환한다. 이는 특별히 따로 존재하는 instruction이며, 같은 주소에 대한 메모리 접근에 의해 방해받지 않는다. (exchange operation은 나눠질 수 없으므로indivisible)
  • 값이 0이라면: synch. variable이 free
  • 값이 1이라면: synch. variable은 lock되어 있으며 사용 불가하다(unavailable)
    • 이 경우, 레지스터 값을 1로 설정하고 swap한다.
    • 레지스터 안의 새 값이 lock 획득의 성공여부를 결정한다. (0: 성공 / 1: 실패)
• Test-and-set: 값을 test하고 해당 test를 pass하면 값을 설정한다.
• Fetch-and-increment: 메모리 값을 리턴하고 atomically increment한다. (0: synch. var이 free)

atomic exchange를 사용하는 경우 lockit은 다음과 같이 구현될 수 있다. exch에서 R1에 1을 저장하고(R2에는 R1의 값이 들어가게 된다), 만약  bnez에서 기존 lock variable의 값(즉, R2에 저장된 값)이 0이 아니라면, 기존에 lock이 free가 아닌 상태였으므로 lock 획득에 실패해 다시 lockit으로 돌아가 spin하게 된다.

lockit:	li	R2, #1
	exch	R2, 0(R1)	;atomic exchange
	bnez	R2, lockit	;already locked?

*만약 여러 쓰레드가 같은 주소에 대해 atomic exchange를 실행한다면, exch는 atomic한 연산이므로 하드웨어 차원에서 해당 쓰레드들 간의 순서를 정해주게 된다.

**cache coherency가 있는 멀티프로세서에서는, full memory latency를 피하기 위해 메모리가 아닌 cache copy에 대해 spin하게 된다. 이러한 변수들에 대해서는 cache hit을 얻을 가능성이 높다.

하지만, exchange는 write을 포함한다. write은 다른 copy들을 모두 invalidate하므로, 이는 상당한 bus 트래픽을 생성한다. 이 문제점을 해결하기 위해, synch. var를 먼저 읽어오고, spin하는 동안에는 exch하지 않고, 변수가 바뀔 때만 exchange를 하도록 바꿀 수 있다(test and test&set).

try:		li	R2,#1
lockit:		lw	R3,0(R1)	; load var
		bnez	R3, lockit	; !=0 -> not free -> spin
        	exch	R2, 0(R1)	; atomic exchange
            	bnez	R2,try		; already locked?

여러 쓰레드가 동시에 exch를 실행할 수 있기 때문에, lw로 한번 확인한 후 exch를 실행하더라도 값이 제대로 바뀌지 않을 수 있다(bnez R2, try가 있는 이유). 하지만, 이렇게 함으로써 불필요한 spin을 많이 줄일 수 있다. 

 

3.Lock을 위한 하드웨어 지원: LL&SC

읽기와 쓰기를 하나의 명령어에서 한번에 처리하기 어려우므로, 대신 2개를 사용하는 방법이다.

⇒ Load Linked (load locked) & Store Conditional

• LL은 초기값을 리턴한다.
• SC는 atomicity를 위배하지 않을 때만 store를 수행한다. 성공하면 (LL이후로 동일한 메모리에 대한 다른 store가 없는 경우)1을, 실패하면 0을 리턴한다.

exch의 경우 항상 atomic하게 실행되지만, LL-SC는 atomicity에서 실패할 수 있지만 retry를 통해 이를 해결한다.

LL와 SC를 활용한 구현 예시는 다음과 같다.

(1) atomic swap

다음은 R4와 R1의 값을 swap하는 예시이다. R1은 R2에, R4는 R3에 임시 저장한다. 먼저 R3을 R1에 store conditional 수행한다. store가 성공하면 R1에는 R3의 값이, R3에는 성공을 나타내는 1이 저장된다. 아니라면 R3에는 0이 저장된다. store가 실패하면 try로 돌아가 해당 요청을 다시 수행한다. 만약 R3에서 R1으로의 store가 성공했다면, 마지막으로 R4에 R1의 복사본인 R2 값을 저장한다.

try:	mov	R3,R4		;move exchange value(R4->R3)
	ll	R2,0(R1)	;load linked
    	sc	R3,0(R1)	;R3->R1 store conditional: 성공하면 1/실패하면 0
    	beqz	R3,try		;store가 실패하면(R3=0이면) retry
    	mov	R4,R2		;load value를 R4에 저장(R2->R4)

(2) fetch-and-increment

R1 값을 1 증가시켜 R2에 저장하는 연산이다. 

try:	ll	R2,0(R1)	;load linked(R1->R2)
	addi	R2,R2,#1	;R2+=1
    	sc	R2,0(R1)	;store conditional(R2->R1)
        beqz	R2,try		;branch store fails(R2=0)

(3) Lock

LL은 어떤 bus 트래픽도 발생시키지 않는다. *daddui rt rs imm : rs+imm을 rt에 저장

lockit:	ll	R2,0(R1)	;load var(R1->R2)
	bnez	R2,lockit	;synch. var 값이 0이 아니면 spin
    	daddui	R2,R0,#1	;R0+1을 R2에 저장(lock value를 1로 업데이트. R0은 0)
        sc	R2,0(R1)	;store conditional(R2->R1)
        beqz	R2,lockit	;store 실패 시 retry

 

정리해보면, 원자적인 load & store를 구현하는 데에는 다음 두 가지 방법이 있다.

Atomic exchange (atomic load-and-store)	Load-locked & Store-conditional
▪ 하드웨어 내부적으로 수행되는 별도의 load와 store연산 (소  프트웨어에서는 하나의 명령어로 보인다) ▪ load는 다른 캐시를 invalidate한다. ▪ store가 완료될 때까지, 다른 캐시에 의한 invalidation은 잠시 멈춰 기다려야 한다. 즉, 해당 변수에 write하려는 다른 프로세서가 있다면 그들을 기다리도록 만든다.	▪ CPU는 가장 마지막 load-locked 주소만 기억하면 된다. ▪ 다른 프로세서에 의한 invaliation은 load-locked 주소를 0으로 세팅한다. ▪ store-conditional은 load-locked 주소가 0이면 실패한다. ▪ exch에 비해 구현하기 더 쉽다. ▪ 다른 코어에 의한 conflict invalidation(쓰기 요청)을 탐지할 수 있다.

 

(추가) 지난 학기 OS에서 나왔던 lock 관련 코드들

• Test-and-set: test(ptr에 의한 old value 리턴), set(리턴과 동시에 new value로 업데이트)

int TestAndSet(int *ptr, int new){
	int old = *ptr;
    	*ptr = new;
    	return old;
}

• Fetch-and-add(increment): old value 리턴과 동시에 1 증가시킴

int FetchAndAdd(int *ptr){
	int old = *ptr;
    	*ptr = old+1;
    	return old;
}

• Load-linked & store-conditional: lock이 사용 중이고 store가 실패하는 동안 spin

int LoadLinked(int *ptr) {
	return *ptr;
}

int StoreConditional(int *ptr, int value) {
	if (no one has updated *ptr since the LoadLinked to this address) {
    	*ptr = value;
        return 1;	// success
    }
    else {
    	return 0;	// fail
    }
}

void lock(lock_t *lock) {
	while (LoadLinked(&lock->flag)||!StoreConditional(&lock->flag,1)); // spin
}

 

4. Transaction Memory

lock variable은 실제 데이터를 포함하고 있지 않으며 단지 프로그램 실행을 정확하게 만들기 위해 사용된다. 하지만 많은 메모리와 캐시 공간을 소모하고, 이는 fine-grained lock일수록 더 심해진다. 또한, lock 획득 과정은 비싸다. lock을 위한 atomic swap, ll-sc 등은 costly operation이며, 쓰기 허가를 필요로 한다. 또한, 효율적인 병렬 프로그램은 많은 lock contention을 포함해선 안 된다. 대부분의 시간동안 lock은 아무 일도 하지 않는다.(한번에 하나의 쓰레드만 하나의 공유 위치에 접근하므로) 하지만 여전히 lock은 공유 위치를 보호하기 위해 획득되어야 한다.

→ 즉, lock은 flag와 같이 꼭 필요하긴 하지만 오버헤드가 크다는 특징을 갖고 있다.

이러한 문제를 해결하기 위해 대안으로 제시되는 것이 Transactional Memory이다.

• corase-grained lock의 프로그램 용이성과 fine-grained lock의 높은 병렬성의 장점을 모두 갖고 있다.
• 프로그래머에 의한 복잡한 lock 관리가 필요하지 않다. (→ scale이 쉽다.)
• HW transactional memory는 하드웨어가, SW transactional memory는 소프트웨어 라이브러리 및 런타임 시스템이 잠정적인 race condition을 확인하고 예방한다.
• (예시) 같은 주소에 대해 두 개의 트랜잭션이 동시에 conflict 발생 시, 해당 트랜잭션 중 하나는 자동으로 abort되고 하드웨어에서 자동으로 abort된 트랜잭션을 재시작한다. 하지만 TM에서는 conflict가 그렇게 자주 발생하지 않는다고 가정한다. 많은 트랜잭션들은 각각 데이터의 서로 다른 부분에 접근하기 때문이다.
• (구현) 다음과 같이 transaction 부분만 둘러싸서 표시하면 된다.

begin_transaction();
if (accounts[id].balance >= amount) {
	accounts[id].balance -= amount;
    	give_cash();
}
end_transaction();

트랜잭션은 하나의 atomic 단위로 실행되며, Serializability와 Atmoicity를 모두 갖고 있다.

• Serializability: 트랜잭션은 serially 실행되는 것처럼 보인다.
• Atomicity: 트랜잭션 레벨에서 원자적이며, commit되거나(make changes visible to all) abort거나(discard changes. 나중에 다시 retry) 둘 중 하나이다.

TM의 기본 연산들

Read Set	critical section 내에서 읽힌 shared address의 집합
Write Set	critical section 내에서 업데이트된 shared address의 집합
TM Begin	▪ 체크포인팅 (loacl register states) ▪ read set을 트래킹하기 시작 → 해당 set에 어떤 write이 발생하는지 확인 ▪ 모든 write을 locally 버퍼링 → 다른 프로세서에서는 아직 볼 수 없음
TM End	▪ read set을 확인해서 모든 데이터가 유효한지 확인 yes → 트랜잭션 commit: locally 버퍼링된 쓰기를 다른 프로세서에서도 볼 수 있도록 만든다.  no(=conflict 존재) →  트랜잭션 abort: 체크포인트 회복. (TM begin부터 다시 시작)
특징	lock이 없다. TM은 잠재적인 race condition을 확인하고 원자성이 위배된 경우 트랜잭션을 abort하고 retry한다. (즉, HW에 의해 actual conflict가 탐지된다.)
	address-levle에서 race condition을 확인할 수 있다. 즉, fine-grained checking이 가능하다.

캐시 기반 하드웨어 TM

• Read set 기억: 캐시 블록당 transaction read bit를 추가한다. 다른 프로세서에 의한 쓰기는 invaliation을 보내 abort를 trigger한다. 트랜잭션이 abort나 commit되는 경우 모든 read bit를 clear한다.
• Write set 버퍼링: copy를 clean하게 만든다.(만약 dirty라면 블록을 메모리에 write back한다.) commit되기 전까지는 업데이트는 다른 프로세서에 보이지 않는다.
• 트랜잭션 충돌: read set 내부의 블록들은 invalidate된다.