[운영체제] 동기화 도구들: 동기화를 위한 하드웨어 지원

 

메모리 장벽(Memory Barriers)

---

 

컴퓨터 아키텍처가 응용 프로그램에게 메모리를 어떻게 제공하는가에 대한 모델을 메모리 모델(memory model)이라고 한다.

 

메모리 모델은 일반적으로 다음 두 가지 중 하나에 속한다.

 

1. 강한 순서(strongly ordered):

한 프로세서의 메모리 변경 결과가 다른 모든 프로세서에 즉시 보인다.

 

2. 약한 순서(weakly ordered):

한 프로세서의 메모리 변경 결과가 다른 프로세서에 즉시 보이지 않는다.

 

 

 

메모리 모델은 프로세서 유형에 따라 다르므로 커널 개발 시 가정할 수 없다.

 

이를 해결하기 위해 컴퓨터 아키텍처는 메모리의 모든 변경 사항을 다른 모든 프로세서로 전파하는 명령어를 제공하여 다른 프로세서에서 실행 중인 스레드에 메모리 변경 사항이 보이는 것을 보장한다.

 

이러한 명령어를 메모리 장벽(memory barrier) 또는 메모리 펜스(memory fence)라고 한다.

 

메모리 장벽 명령어가 실행될 때, 시스템은 다음 명령어가 실행되기 전에 모든 적재나 저장이 완료되도록 한다.

 

이는 명령어가 재배치되더라도, 이후 명령 실행 전에 저장이 완료되고 그 결과가 모두에게 보인다.

 

예시)

 

 

 

 

Thread 1에서는 flag값이 x값보다 먼저 적재되도록 보장한다.

 

Thread 2에서는 x값이 flag 값보다 먼저 배정되도록 보장한다.

 

 

 

메모리 장벽을 통해 pertson의 해결 방법의 재배치 문제를 해결할 수 있다.

 

메모리 장벽은 매우 낮은 수준의 연산으로 일반적으로 커널 개발자만 사용한다.

 

 

 

 

 

 

하드웨어 명령어(Hardware Instructions)

---

 

현대의 많은 컴퓨터 시스템은 한 워드의 내용을 원자적으로 검사하고 변경하거나, 두 워드의 내용을 원자적으로 교환할 수 있는 특별한 하드웨어 명령어들을 제공한다.

(test_and_set() 명령어, compare_and_swap() 명령어)

 

원자적이라는 것은 인터럽트 되지 않는 하나의 단위로 실행된다는 것이다.

 

이런 명령어를 사용하여 임계구역 문제를 상대적으로 간단한 방식으로 해결할 수 있다.

 

 

 

- test_and_set() 명령어 (TAS instruction)

 

명령어가 원자적으로 실행된다.

 

즉, 다른 코어에서 이 명령어가 동시에 실행된다면 이들은 임의의 어떤 순서로 순차적으로 실행된다.

 

 

test_and_set 명령어의 정의

 

 

test_and_set() 명령어는 lock이 가능한지 현재 lock 상태를 반환해주고, lock을 true로 set 한다.

 

 

 

test_and_set 명령어를 이용한 상호 배제 구현

 

 

lock의 초기값 = false

 

두 프로세스를 동시에 실행할 때,

 

처음 실행하는 프로세스는 lock = false이므로 임계구역에 진입할 수 있다. 임계구역에 진입하면서 lock = 1로 바꿔준다.

 

두 번째로 실행하는 프로세스는 lock = true이므로 임계구역에 진입할 수 없다.

 

따라서 상호 배제를 만족한다.

 

 

 

- compare_and_swap() 명령어 (CAS instruction)

 

두 워드의 내용 교환에 기반을 둔 두 개의 워드에 대해 원자적인 연산을 수행한다.

 

 

compare_and_swap 명령어의 정의

 

 

compare_and_swap() 명령어는 lock이 가능한지 현재 lock 상태를 반환해주고, value == expected이면 value를 new_value 값으로 설정한다.

 

 

compare_and_swap 명령어를 이용한 상호 배제 구현

 

 

lock의 초기값 = 0

 

여러 프로세스가 동시에 실행될 때,

 

첫 프로세스는 lock = 0이므로 임계구역에 진입할 수 있다. 임계구역에 진입하면서 lock = 1로 바꿔준다.

 

나머지 프로세스는 lock = 1이므로 임계구역에 진입할 수 없다.

 

 

위 알고리즘은 상호 배제 조건은 만족시키지만, 계속 대기하는 프로세스가 생길 수 있으므로 한정된 대기 조건을 만족시키지 못한다.

 

임계구역 조건을 모두 만족하는 compare_and_swap() 명령어를 이용한 또 다른 알고리즘은 다음과 같다.

 

 

 

key = 0이거나 waiting[i] = false일 때, 프로세스가 임계구역에 진입할 수 있다.

 

이때, 오직 한 개의 프로세스가 key = 0이거나 waiting[i] = false이므로, 상호 배제가 보장된다.

 

 

임계구역을 떠나는 프로세스는 lock을 0으로 하거나 waiting[j]를 false로 set 한다. 

 

이는 임계구역으로 들어가고자 하는 프로세스를 진입하도록 만들어 주므로, 진행이 보장된다.

 

 

임계구역을 떠나는 프로세스는 waiting 배열을 순환하면서  진입 의사가 있는 첫 번째 프로세스가 임계구역에 들어가게 된다.

 

따라서 임계구역에 들어가고자 하는 프로세스는 최대 n-1회만 양보하면 임계구역에 들어갈 수 있으므로, 한정된 대기가 보장된다.

 

 

 

 

 

 

원자적 변수(Atomic Variables)

---

 

원자적 변수(atomic variable)는 int나 boolean과 같은 기본 데이터 타입에 대한 원자적인 연산을 제공한다.

 

이는 단일 변수가 갱신되는 동안 데이터 경쟁이 있을 때, 상호 배제를 보장한다.

 

 

 

대부분의 시스템은 원자적 변수에 접근하고 조작하기 위한 기능뿐만 아니라 특별한 원자적 데이터 유형을 제공한다.

 

이러한 함수는 종종 compare_and_swap() 연산을 이용해서 구현되기도 한다.

 

예시)

 

 

 

 

원자적 변수는 다음과 같은 상황에서 문제가 발생할 수 있다.

 

버퍼가 비어있고, 두 consumer가 count > 0을 기다리면 while 문을 돌고 있는 상황에서, 

 

producer가 버퍼에 하나의 항목을 입력하게 되면, 두 consumer  모두 루프를 빠져나와 데이터를 소비한다.

 

 

 

원자적 변수는 공유 데이터 한 개의 갱신에만 제한되는 경우가 많다.