- 임계구역 문제를 해결하기 위한 지원을 제공하는 세 가지 하드웨어 명령어를 제시
메모리 장벽(Memory Barriers)
메모리 모델
- 컴퓨터 아키텍처가 응용프로그램에게 제공하는 메모리 접근 시 보장되는 사항을 결정한 방식
- 일반적으로 두 가지 범주 중 하나에 속함
강한 순서 : 한 프로세서의 메모리 변경 결과가 다른 모든 프로세서에 즉시 보임약한 순서 : 한 프로세서의 메모리 변경 결과가 다른 프로세서에 즉시 보이지 않음
- 메모리 모델은 프로세서 유형에 따라 다름
→ 커널 개발자는 공유 메모리 다중 처리기에서 메모리 변경의 가시성에 대한 가정 불가
→ 이러한 문제를 해결하기 위해 메모리 장벽을 사용
메모리 장벽 : 메모리의 모든 변경 사항을 다른 모든 프로세서로 전파하는 명령어
- 이를 통해 다른 프로세서에서 실행 중인 스레드에 메모리 변경 사항이 보이는 것을 보장
- 메모리 펜스(memory fences)라고도 부름
- 메모리 장벽은 매우 낮은 수준의 연산으로 간주
- 일반적으로 상호 배제를 보장하는 특수 코드를 작성할 때 커널 개발자만 사용
메모리 장벽 실행 과정
- 메모리 장벽 명령어가 실행될 때, 시스템은 후속 적재 또는 저장 연산이 수행되기 전에
모든 적재 및 저장이 완료되도록 한다.
→ 명령이 재정렬 되더라도 메모리 장벽이 현재 실행 중이던 저장 작업이
메모리에서 완료되어 다른 프로세서에 보이도록 한다.
사용 예시
while(!flag)
memory_barrier(); // 메모리 배리어 실행
print x;
- flag 값이 x값보다 먼저 적재되도록 보장한다.
하드웨어 명령어(Hardware Instructions)
- 많은 현대 기계들은 word의 내용을 원자적으로 교환할 수 있는 특별한 하드웨어 명령어 제공
- 원자적이다 → 인터럽트 되지 않는 하나의 단위를 뜻함
- 이를 이용하여 임계구역 문제를 상대적으로 간단히 해결 가능
- 대표적으로
test_and_set()과 compare_and_swap() 명령어가 있음
test_and_set()
// 원자적 test_and_set() 명령어의 정의
boolean test_and_set(boolean *target){
boolean rv = *target;
*target = true;
return rv;
}
- 중요한 특징은 이 명령어가 원자적(atomically)으로 실행된다는 점
- 각자 다른 코어에서 해당 명령어 2개가 동시에 실행될 경우?
→ 임의의 순서로 순차적으로 실행될 것
- test_and_set() 명령어를 통해 상호 배제 구현 가능
do{
while(test_and_set(&lock)); // do nothing;
/* critical section */
lock = false;
/* remainder section */
} while(true);
compare_and_swap() - CAS
- test_and_set()과 마찬가지로 두 개의 워드에 대해 원자적인 연산을 함
But, 두 워드의 내용 고환에 기반을 둔 다른 기법을 사용
- CAS는 3개의 피연산자를 대상으로 연산을 함
// compare_and_swap() 명령어의 정의
int compare_and_swap(int *value, int expected, int new_value){
int temp = *value;
if(*value == expected) *value = new_value;
return temp;
}
- 피연산자 value는 오직 (*value == expected) 수식이 참일 때만 new_value로 지정됨
- 어떠한 경우에든 CAS 명령어는 언제나 value의 원래 값을 반환
- CAS를 사용한 상호 배제 구현
- 아래 알고리즘은 상호 배제 조건은 만족하지만 한정된 대기 조건은 만족하지 못함
- 과정
- 전역변수 lock이 선언되고 0으로 초기화된다.
- CAS를 호출한 첫 번째 프로세스는 lock을 1로 지정
→ 해당 프로세스는 임계구역으로 들어감
- 이후의 CAS 호출은 현재 lock의 값과 기댓값 0과 다르기 때문에 무한루프
→ 임계구역에 들어가지 못함
- 첫 번째 프로세스가 임계구역에 나오면서 lock = 0을 해야 임계구역에 들어갈 수 있음
while(true){
while(compare_and_swap(&lock,0,1) != 0); // do nothing
/* critical section */
lock = 0;
/* remainder section */
}
- 임계구역 조건을 모두 만족시키는 CAS 구현
- waiting 배열의 원소는 false로 초기화, lock은 0으로 초기화
- 해당 알고리즘이 상호 배제를 만족시키는 것을 증명하기 위한 조건
→ waiting [i] == false 또는 key == 0 이어야 함
- key == 0인 경우는 compare_and_swap() 명령어를 실행했을 때만 가능
- 상호 배제 보장 과정
- 처음으로 compare_and_swap()을 실행시키는 프로세스는 key == 0을 발견
- 다른 프로세스들은 모두 기다려야 함
→ waiting [i] = false가 되는 것은 다른 프로세스가 임계 구역을 떠날 때뿐
→ 단 1개의 waiting [i]만이 false로 지정 → 상호 배제가 보장
- 진행(progress) 보장
- 임계구역을 떠나는 프로세스는 lock을 0으로 하든지 waiting [j]를 false로 함
→ 임계 구역으로 들어가고자 하는 프로세스를 진입하게 만들어줌
- 한정된 대기 조건 만족 보장
- 한 프로세스가 임계 구역을 떠날 때 waiting 배열을 순환하면서 훑어본다.
- 임계 구역에 들어가고자 하는 프로세스는 최대 n-1회까지만 양보하면 됨
원자적 변수(Atomic Variables)
- 일반적으로 compare_and_swap() 명령어는 상호 배제를 제공하기 위해 직접 사용되진 않음
- 오히려 임계 구역 문제 해결하는 다른 도구 구축을 위한 기본 구성요소로 사용
→ 그러한 도구 중 하나가 원자적 변수
- 정수 및 boolean과 같은 기본 데이터 유형에 대한 원자적 연산을 제공
- 원자적 변수는 단일 변수에 대한 데이터 경쟁에 대해 상호 배제를 보장하는 데 사용될 수 있음
원자적 변수를 제공하는 시스템
- 원자적 변수를 접근하고 조작하는 기능 제공
- 특별한 원자적 데이터 유형 제공
- 종종 compare_and_swap() 연산을 사용해 구현
- 예 :
increment(&sequence)
원자적 변수의 한계
- 원자적 변수는 원자적 갱신을 제공하지만 모든 상황에서 경쟁 조건을 해결하진 않음
- 원자적 변수는 운영체제 및 병행 응용 프로그램에서 일반적으로 사용됨
→ But, 카운터 및 시퀀스 생성기와 같은 공유 데이터 한 개의 갱신에만 제한되는 경우가 잦음