[Chapter 2. 명령어: 컴퓨터 언어] 데이터 경쟁 관계와 동기화, 동기화에 사용되는 하드웨어 명령어

* 본 글은 '컴퓨터 구조 및 설계: 하드웨어/소프트웨어 인터페이스(Computer Organization and Design: The Hardware/Software Interface) 5th edition'의 내용과 2021학년도 1학기에 수강한 '컴퓨터 구조' 과목 강의 내용을 함께 정리하여 작성하였습니다.

 

병렬성과 명령어: 동기화

---

데이터 경쟁 관계 (Data Race)

태스크가 서로 독립적일 때에는 병렬 처리가 쉽다. 하지만 태스크가 서로 협력해야 할 때에는 어떨까?

 

이때 협력이란, 자원으로 서로 공유한다는 것으로

보통 다른 태스크들이 읽어야 하는 새로운 값을 어떤 태스크들이 쓰는 것을 의미한다.

 

 

태스크가 협력해야 하는 상황에서는 데이터 경쟁관계(data race)의 위험이 크다.

 

예를 들어, 두 프로세서 P1과 P2가 메모리 구역을 공유하고 있다고 하자.

P1이 데이터를 읽어오고, P2가 데이터를 쓴다고 가정하면 P1과 P2의 수행 순서에 따라 데이터의 결괏값이 달라질 것이다.

 

이처럼 이벤트가 일어나는 순서에 따라 프로그램의 결과가 달라질 수 있는 상황을 데이터 경쟁관계라고 한다.

 

 

동기화 (Synchronizaiton)

데이터 경쟁관계를 피하기 위해서는 태스크들이 동기화되어야 하며,

이는 하드웨어의 지원이 필요하다.

 

컴퓨팅에 있어서 동기화 메커니즘은 일반적으로는 사용자 수준 소프트웨어 루틴에서 제공되는데,

이 소프트웨어 루틴들은 하드웨어가 제공하는 동기화 명령을 사용하고 있다.

 

 

멀티 프로세서에서 동기화를 구현하기 위해서는

메모리 주소에서 읽고 수정하는 것을 원소적으로(atomically) 처리할 능력을 가진 하드웨어 프리미티브(primitive)가 있어야 한다.

 

원자적으로 처리한다는 것은 메모리에서 읽고 쓰는 중간에 아무것도 끼어들 수 없게 한다는 것이다.

 

 

본서는 lock과 unlock 동기화 연산의 구현에 집중을 한다.

이들을 통해서 단 하나의 프로세서만이 작업할 수 있는 영역 즉, 임계 구역을 생성할 수 있다.

따라서 상호 배제(mutual exclusion)를 구현할 수 있는 것이다.

 

---

먼저 하드웨어 프리미티브 하나를 살펴보고, 이것이 기본 동기화 프리미티브 구축에 어떻게 사용되는지를 알아보자.

 

동기화 연산 구축을 위한 전형적인 연산은 원자적 교환(atomic exchange 또는 atomic swap)인데,

이 연산은 레지스터의 값을 메모리 값과 교환하는 것이다.

MIPS는 이를 위해 SWP 명령어를 갖고 있다.

 

 

이것을 기본 동기화 프리미티브 구축에 어떻게 사용하는지 보기 위해 간단한 lock을 만들어 보자.

 

lock은 0이면 사용 가능하고, 1이면 사용할 수 없음을 표시한다고 하자.

 

접근하는 프로세서는 자신만이 이 구역에 접근해야 하므로

레지스터에 있는 값 1과 메모리에 있는 lock을 맞바꿈으로써 lock을 1로 만들고자 할 것이다.

 

만약 맞바꾼 값이 1이라면 다른 프로세서가 이미 접근을 하고 있다는 의미이며,

맞바꾼 값이 0이라면 lock 값이 1로 바뀌어서 다른 프로세서는 접근하지 못하게 될 것이다.

 

여기서 핵심은 연산이 원소적으로 일어난다는 것이다.

즉, 교환은 나뉠 수 없는(indivisible) 것이라서 두 개의 동시 교환은 하드웨어에 의해 순서가 결정된다.

 

ll(load linked), sc(store conditional) 명령어

MIPS에는 동기화를 위한 두 가지 특수 명령어 쌍이 존재하는데,

바로 특수 적재 명령어 load linked와 특수 저장 명령어 store conditional이다.

 

ll rt, offset(rs)	# load linked
sc rt, offset(rs)	# store conditional

 

이 명령어 쌍은 순차적으로 사용된다.

 

만약 load linked 명령어에 의해 명시된 메모리 주소의 내용이

같은 주소에 대한 store conditional 명령어가 실행되기 전에 바뀐다면

store conditional 명령은 실패하게 된다.

 

store conditional 명령어는 레지스터 값을 메모리에 저장하고 동시에 그 레지스터 값을 1로 바꾸게 되면 성공이고,

만약 실패한다면 레지스터 값은 0이 된다.

 

load linked 명령어는 초깃값을 반환하고 store conditional은 성공할 때만 1을 반환하기 때문에

다음 명령어 시퀀스는 $s1의 내용이 가리키는 메모리 주소에 대해 원자적 교환을 구현하게 된다.

 

again: addi $t0, $zero, 1		# copy locked value
       ll   $t1, 0($s1) 		# load linked
       sc   $t0, 0($s1) 		# store conditional
       beq  $t0, $zero, again 		# branch if store fails
       add  $s4, $zero, $t1 		# put load value in $s4

 

ll 명령어와 sc 명령어 사이에 프로세서가 끼어들거나 메모리 값을 수정하는 경우에 sc는 $t0에 0을 반환하기 때문에

코드 시퀀스가 다시 실행하게 된다.

 

결국 이 시퀀스 끝에는 $s4의 내용과 $s1에 의해 명시된 주소의 메모리 사이에 원자적으로 교환이 이루어진다.

 

---

정리하자면,

load linked와 store conditional 같은 프리미티브를 사용하는 시점은 다음과 같다.

 

1.

병렬 프로그램에서 협력 관계에 있는 스레드들이 공유 데이터에 대한 읽고 쓰기를 적합하게 하기 위해 동기화가 필요할 때

 

2.

단일 프로세서에서 협력 관계에 있는 프로세스들이 공유 데이터를 읽고 쓰기 위해 동기화가 필요할 때