검사와 지정
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
검사와 지정(Test-and-Set)은 하드웨어 및 소프트웨어에서 상호 배제를 구현하는 데 사용되는 원자적 연산이다. 하드웨어적으로는 DPRAM을 이용하여 두 개의 CPU가 공유 메모리에 접근할 때 발생할 수 있는 충돌을 방지하며, 소프트웨어적으로는 x86, IBM System/360 등의 아키텍처에서 제공되는 원자적 명령어를 활용하거나, 읽기-수정-쓰기 또는 비교-및-교환 명령어를 통해 구현된다. 검사 및 지정은 스핀락, 뮤텍스, 세마포어 등 다양한 동기화 메커니즘의 기초가 되며, 상호 배제 구현, 임계 구역 관리, 테스트 앤드 테스트-앤드-세트 프로토콜, 그리고 스핀락 구현에 활용된다. 성능 평가 지표로는 경합 없는 락 획득 지연 시간, 버스 트래픽, 공정성 및 저장 공간이 있으며, 테스트-앤-세트는 높은 버스 트래픽과 불공정성에서 낮은 점수를 받는다.
더 읽어볼만한 페이지
| 검사와 지정 | |
|---|---|
| 명령어 개요 | |
| 이름 | Test-and-Set (테스트 앤드 셋) |
| 종류 | CPU 명령어 |
| 기능 | 특정 메모리 위치의 값을 읽고, 해당 위치에 1을 설정하는 원자적 연산. 주로 상호 배제를 구현하기 위한 스핀락 등의 동기화 메커니즘에 사용됨. |
| 작동 방식 | |
| 원자성 | Test-and-Set 명령어는 인터럽트나 다른 프로세서의 접근 없이 **원자적으로** 실행됨. |
| 읽기 및 설정 | 명령어 실행 시, 지정된 메모리 위치의 현재 값을 읽어온 후, 즉시 해당 위치에 1을 씀. |
| 반환 값 | 명령어는 원래 메모리 위치에 저장되어 있던 값을 반환함. 이 값을 통해 스핀락 획득 여부 등을 판단할 수 있음. |
| 활용 | |
| 상호 배제 구현 | Test-and-Set 명령어는 스핀락을 구현하는 데 사용될 수 있음. 스핀락은 공유 자원에 대한 접근을 제어하는 간단한 락 메커니즘임. |
| 동기화 | 여러 프로세스 또는 스레드 간의 동기화를 위해 사용될 수 있음. Test-and-Set을 사용하여 임계 영역에 대한 접근을 제어하고 데이터 무결성을 유지할 수 있음. |
| 예시 (스핀락) | |
| 스핀락 획득 | Test-and-Set 명령어를 사용하여 락 변수의 값을 확인하고 1로 설정함. 반환 값이 0이면 락 획득 성공, 1이면 락 획득 실패를 의미함. |
| 스핀락 해제 | 락을 획득한 프로세스는 임계 영역 작업을 완료한 후, 락 변수를 0으로 설정하여 락을 해제함. |
| 장단점 | |
| 장점 | 구현이 간단하고 일부 아키텍처에서 효율적인 상호 배제를 제공함. |
| 단점 | 스핀락 구현 시, 락 획득 경쟁이 심할 경우 CPU 자원을 낭비할 수 있음 (busy-waiting). 우선 순위 역전 문제에 취약할 수 있음. |
| 참고 자료 | |
| 관련 연구 | Wait-free synchronization (Herlihy, 1991) The performance of spin lock alternatives for shared-money multiprocessors (Anderson, 1990) |
2. 하드웨어 구현
DPRAM을 이용한 검사 및 설정 명령은 다양한 방식으로 구현될 수 있다. 여기서는 두 개의 포트를 가진 DPRAM을 사용하는 두 가지 변형 예시를 설명한다. 이 방식은 두 개의 독립된 전자 부품(예: 두 개의 CPU)이 DPRAM 내의 모든 메모리 위치에 접근할 수 있도록 허용하는 구조를 기반으로 한다.
2. 1. DPRAM을 이용한 구현 (Variation 1)
DPRAM을 이용한 검사 및 지정 명령은 여러 방식으로 구현될 수 있다. 다음은 두 개의 포트를 가진 DPRAM을 사용하는 한 가지 예시이다. 이 DPRAM은 두 개의 독립된 전자 부품(예: 두 개의 CPU)이 DPRAM 내의 모든 메모리 위치에 접근할 수 있도록 한다.CPU 1이 테스트-앤드-세트(test-and-set) 명령을 실행하면, DPRAM은 먼저 해당 메모리 주소를 내부의 특별한 위치에 기록한다. 만약 이때 CPU 2가 동일한 메모리 위치에 대해 테스트-앤드-세트 명령을 실행하려고 하면, DPRAM은 내부 기록을 확인하고 CPU 2에게 BUSY 인터럽트를 발생시킨다. 이 인터럽트는 CPU 2에게 잠시 기다렸다가 다시 시도하라는 신호이며, 이는 인터럽트 메커니즘을 이용한 바쁜 대기(busy-waiting) 또는 스핀락(spinlock) 방식의 구현이다. 이 모든 과정은 하드웨어 수준에서 매우 빠르게 처리되므로 CPU 2의 대기 시간은 매우 짧다.
CPU 2의 접근 시도 여부와 관계없이, DPRAM은 CPU 1의 요청에 따라 테스트를 수행한다. 테스트 결과가 성공이면, DPRAM은 해당 메모리 위치의 값을 CPU 1이 지정한 값으로 설정(set)한다. 그 후 DPRAM은 CPU 1에 대한 내부 기록을 삭제하며, 이 시점부터 CPU 2는 해당 메모리 위치에 대한 테스트-앤드-세트 명령을 성공적으로 실행할 수 있게 된다.
2. 2. DPRAM을 이용한 구현 (Variation 2)
DPRAM을 이용한 검사 및 설정 명령은 여러 방식으로 작동할 수 있다. 다음은 두 개의 포트를 가진 DPRAM을 사용하는 두 번째 변형 예시이다. 이 DPRAM은 두 개의 개별 전자 부품(예: 두 개의 CPU)이 DPRAM 내의 모든 메모리 위치에 접근할 수 있도록 한다.# CPU 1이 특정 메모리 위치(예: '메모리 위치 A')에 쓰기 위해 테스트-앤-세트 명령을 실행한다.
# DPRAM은 즉시 해당 위치에 값을 쓰지 않는다. 대신, 현재 '메모리 위치 A'의 값을 임시로 특수한 레지스터에 저장하고, '메모리 위치 A'에는 특수한 '플래그 값'을 설정한다. 이는 해당 메모리 위치가 현재 처리 중임을 나타낸다.
# 만약 이 상태에서 CPU 2가 동일한 '메모리 위치 A'에 테스트-앤-세트 명령을 실행하면, DPRAM은 설정된 특수 플래그 값을 감지한다. 이 경우, DPRAM은 CPU 2에게 해당 메모리 위치가 사용 중임을 알리는 BUSY 인터럽트 신호를 보낸다.
# CPU 2의 접근 시도 여부와 관계없이, DPRAM은 이제 CPU 1의 테스트를 진행한다. 이 테스트는 특수 레지스터에 임시 저장된 기존 값과 CPU 1이 쓰려고 하는 새로운 값을 비교하는 과정이다.
# 테스트 결과에 따라 다음 두 가지 중 하나가 수행된다:
#* 테스트 성공 시: DPRAM은 '메모리 위치 A'에 CPU 1이 지정한 새로운 값을 쓴다.
#* 테스트 실패 시: DPRAM은 특수 레지스터에 저장해 두었던 원래 값을 '메모리 위치 A'로 다시 복원한다.
# 두 경우 모두 작업 완료 후 '메모리 위치 A'에 설정되었던 특수 플래그 값은 제거된다.
# 이제 '메모리 위치 A'는 다른 CPU(예: CPU 2)의 접근이 가능한 상태가 되며, CPU 2가 테스트-앤-세트 명령을 실행하면 성공적으로 처리될 수 있다.
3. 소프트웨어 구현
일부 명령어 집합 아키텍처는 하드웨어 수준에서 원자적인 검사와 지정 명령어를 직접 지원한다. 대표적인 예로는 x86[3], IBM System/360 및 그 후속 제품군(z/Architecture 포함)이 있다.[4]
만약 하드웨어에서 검사와 지정 명령어를 직접 지원하지 않는 경우에도, 읽기-수정-쓰기(Read-Modify-Write)나 비교-및-교환(Compare-and-Swap)과 같은 다른 원자적 명령어를 이용하여 동일한 기능을 구현할 수 있다.
검사와 지정 명령어의 핵심 원리는 원자성에 있다. 즉, 특정 메모리 위치의 값을 확인(검사)하고 새로운 값으로 변경(지정)하는 전체 과정이 중간에 다른 프로세스에 의해 중단되지 않고 한 번의 연산처럼 실행되어야 한다. 이를 통해 여러 프로세스나 스레드가 공유 자원에 동시에 접근하는 것을 제어하는 상호 배제 문제를 해결할 수 있다.
이러한 동작 원리는 의사 코드나 특정 프로그래밍 언어(예: C 언어) 코드로 설명될 수 있지만, 실제 원자성을 보장하기 위해서는 반드시 하드웨어의 지원이 필요하다. 소프트웨어만으로는 여러 프로세스가 동시에 메모리에 접근하는 상황에서 발생하는 경쟁 상태를 완벽하게 막기 어렵기 때문에, 코드 예시만으로는 불충분하며 하드웨어 구현이 필수적이다.
검사와 지정 명령어는 뮤텍스와 같은 동기화 메커니즘을 구현하는 데 사용될 수 있다. 가장 기본적인 구현 방식 중 하나는 스핀락인데, 이는 잠금을 얻을 때까지 계속 확인하는 방식이다. 하지만 이 방식은 멀티프로세서 환경에서 캐시 일관성 문제 등으로 인해 시스템 버스에 부하를 주어 비효율적일 수 있다.
3. 1. 의사 코드를 이용한 구현
테스트 앤드 세트(Test-and-set) 명령어는 불리언 값과 함께 사용될 때 아래 함수와 같은 논리로 동작한다. 이 함수 전체는 반드시 원자적으로 실행되어야 한다. 즉, 다른 프로세스가 함수 실행 중간에 개입하여 실행 중간 상태를 볼 수 없어야 한다. 이는 하드웨어 지원이 필수적이므로, 아래 코드는 테스트 앤드 세트의 동작 방식을 설명하기 위한 의사 코드 예시일 뿐이며, 실제로 이렇게 구현할 수는 없다.```text
'''function''' TestAndSet(boolean_ref lock) { // lock은 참조(reference)로 전달됨
boolean initial = lock;
lock = true;
'''return''' initial;
}
```
이 함수는 주어진 메모리 위치(`lock`)의 현재 값을 읽어 `initial` 변수에 저장한 뒤, 해당 메모리 위치의 값을 `true`로 설정하고, 원래 값(`initial`)을 반환한다. 이 모든 과정이 중단 없이 한 번에 이루어져야 한다.
C 언어에서는 다음과 같이 구현을 생각해볼 수 있다. 하지만 이 코드 역시 실제 원자성을 보장하지는 않으며, 설명 목적으로만 사용되어야 한다.
#define LOCKED 1
int test_and_set(int* lockPtr) {
int oldValue;
// -- 원자적 세그먼트 시작 --
// 아래 코드는 설명 목적으로만 사용되는 의사 코드임.
// 실제 컴파일 시 원자성, 공유 메모리 접근(캐시되지 않은 값),
// 컴파일러 최적화 방지 등 필요한 속성을 보장하지 않음.
oldValue = *lockPtr;
- lockPtr = LOCKED;
// -- 원자적 세그먼트 종료 --
return oldValue;
}
이 코드는 실제로는 원자적인 읽기-수정-쓰기(read-modify-write) 연산과 테스트(반환 값을 확인하는 것) 두 단계로 이루어진다는 것을 보여준다. 여기서 원자성이 필요한 부분은 읽기-수정-쓰기 과정이다. 값을 읽고 난 후, 그 값을 비교하는 테스트는 약간 지연되어도 결과에 영향을 주지 않는다.
테스트 앤드 세트 명령어를 이용하면 뮤텍스(Mutex)를 다음과 같이 구현할 수 있다.
```text
boolean lock = false; // 공유 잠금 변수, 초기값은 false (잠기지 않음)
'''function''' Critical() {
'''while''' (TestAndSet(lock) == true) {
// lock이 true를 반환하면 이미 다른 프로세스가 잠금을 획득한 상태.
// 잠금이 해제될 때까지 기다린다 (스핀).
skip;
}
// TestAndSet(lock)이 false를 반환하면 잠금을 획득한 것임.
// --- 임계 구역 시작 ---
// 이 부분은 한 번에 하나의 프로세스만 실행할 수 있다.
// 임계 구역 코드 실행
// --- 임계 구역 종료 ---
lock = false; // 임계 구역 작업 완료 후 잠금을 해제한다.
}
```
이 함수는 여러 프로세스에서 동시에 호출될 수 있지만, `TestAndSet`의 원자성 덕분에 임계 구역(critical section)에는 한 번에 단 하나의 프로세스만 진입할 수 있다. 위 예시는 스핀락 방식으로, `while` 루프를 반복 실행하며 잠금을 계속 확인한다. 이는 실제 멀티프로세서 환경에서는 잠금 변수에 대한 반복적인 읽기와 쓰기로 인해 캐시 일관성 문제를 유발하여 비효율적일 수 있다.
3. 2. C 언어를 이용한 구현
C 프로그래밍 언어에서 테스트-및-설정(Test-and-Set) 연산의 구현 예시는 다음과 같다.#define LOCKED 1
int test_and_set(int* lockPtr) {
int oldValue;
// -- 원자적 세그먼트 시작 --
// 아래 코드는 설명 목적으로 작성된 의사 코드이며,
// 실제 컴파일 시 원자성, 공유 메모리 접근(캐시되지 않은 값 사용),
// 컴파일러 최적화 방지 등 필요한 속성을 보장하지 않는다.
oldValue = *lockPtr;
- lockPtr = LOCKED;
// -- 원자적 세그먼트 종료 --
return oldValue;
}
이 코드는 테스트-및-설정 연산이 실제로는 원자적인 읽기-수정-쓰기(atomic read-modify-write) 연산과 테스트(test) 연산, 두 단계로 이루어짐을 보여준다. 여기서 중요한 점은 읽기-수정-쓰기 과정만이 원자적으로 실행되어야 한다는 것이다. 값을 읽어온 후, 그 값을 비교하는 테스트 연산은 즉시 이루어지지 않아도 결과에 영향을 주지 않는다. 왜냐하면 일단 값을 읽고 메모리에 새로운 값을 쓰는 과정(읽기-수정-쓰기)이 원자적으로 보장되면, 다른 프로세스가 그 사이에 끼어들 수 없기 때문이다. 따라서 읽어온 초기 값(`oldValue`)을 반환하고, 이 값을 이용한 테스트는 이후에 수행되어도 무방하다.
4. 상호 배제(Mutual Exclusion) 구현
상호 배제를 구현하는 방법 중 하나로 test-and-set 연산에 기반한 락(lock)을 사용하는 방식이 있다.[5][6] 이는 여러 프로세스나 스레드가 공유 자원에 동시에 접근하는 것을 막기 위한 기본적인 동기화 기법이다. 구체적인 구현 방식으로는 스핀락이나 어셈블리어 수준에서의 직접적인 명령어 활용 등이 있다.
4. 1. 스핀락(Spinlock) 구현 (의사 코드)
상호 배제를 구현하는 한 가지 방법으로 test-and-set 연산에 기반한 스핀락을 사용할 수 있다.[5][6] 다음은 C 언어를 이용한 간단한 구현 예시이다.volatile int lock = 0; // 공유 잠금 변수. 여러 프로세스/스레드에서 접근 가능.
void critical() {
// 스핀 락: test_and_set 함수를 이용해 잠금을 시도한다.
// test_and_set은 현재 lock 값을 반환하고 lock을 1로 설정하는 원자적 연산이다.
// 반환값이 1이면 이미 다른 곳에서 잠금을 사용 중이므로, 계속 루프를 돈다 (스핀).
// 반환값이 0이면 잠금 획득에 성공한 것이므로 루프를 빠져나온다.
while (test_and_set(&lock) == 1);
// --- 임계 구역 시작 ---
// 이 영역의 코드는 한 번에 오직 하나의 프로세스/스레드만 실행할 수 있다.
critical section
// --- 임계 구역 종료 ---
lock = 0; // 작업 완료 후 잠금을 해제하여 다른 프로세스/스레드가 사용할 수 있도록 한다.
}
위 코드에서 `lock` 변수는 여러 프로세서나 스레드가 공유하는 변수이다. `volatile` 키워드는 컴파일러가 `lock` 변수에 대한 접근을 임의로 최적화하는 것을 방지하기 위해 사용된다. 예를 들어, 컴파일러가 루프 내에서 `lock` 값이 변하지 않을 것이라 가정하고 최적화하거나, 레지스터에 캐시된 값을 계속 사용하는 것을 막는다. 하지만 `volatile` 키워드만으로는 모든 컴파일러와 CPU 아키텍처에서 메모리 작업의 순서나 가시성을 완벽히 보장하지는 못한다. 경우에 따라서는 명시적인 메모리 장벽 명령어가 필요할 수 있으므로, 사용하는 컴파일러와 플랫폼의 문서를 확인하는 것이 중요하다.
이 스핀락 방식은 여러 프로세스가 동시에 `critical()` 함수를 호출하더라도, 오직 하나만이 임계 구역에 진입할 수 있도록 보장한다. 그러나 잠금을 얻지 못한 나머지 프로세스들은 잠금을 얻을 때까지 `while` 루프를 반복 실행하며 CPU 자원을 계속 소모한다(이를 '바쁜 대기(busy-waiting)'라고 한다). 또한, 특정 프로세스가 잠금을 영원히 얻지 못하고 무한 루프에 빠질 가능성도 배제할 수 없다. 이는 스핀락이 기본적으로 공정성을 보장하지 않기 때문이며, 이러한 성능 및 공정성 문제는 성능 평가 섹션에서 더 자세히 다룬다.
불리언 값을 사용하는 `TestAndSet` 연산은 개념적으로 다음과 같은 함수처럼 동작한다고 볼 수 있다. 이 함수 전체는 반드시 아토믹하게 실행되어야 한다. 즉, 함수 실행 도중에 다른 프로세스의 간섭 없이 완료되어야 하며, 중간 상태가 외부에 노출되지 않아야 한다. 이러한 원자성은 일반적으로 하드웨어의 특별한 명령어 지원을 통해 보장된다.
function TestAndSet(boolean lock) { // lock은 참조(주소)로 전달된다고 가정
boolean initial = lock // 현재 lock 값을 읽는다.
lock = true // lock 값을 true (잠김 상태)로 설정한다.
return initial // 원래 lock 값을 반환한다. (잠금 설정 전의 값)
}
이 `TestAndSet` 함수를 이용하여 뮤텍스 (상호 배제 락)를 구현하면 다음과 같다.
boolean lock = false // 초기에는 잠겨있지 않은 상태 (false)
function Critical() {
// TestAndSet 함수를 호출한다.
// 만약 lock이 false였다면, initial 값은 false가 반환되고 lock은 true로 설정된다. while 조건이 거짓이 되어 루프를 빠져나간다.
// 만약 lock이 true였다면, initial 값은 true가 반환되고 lock은 계속 true로 유지된다. while 조건이 참이 되어 루프를 계속 돈다 (스핀).
while TestAndSet(lock)
skip // 아무 작업도 하지 않고 계속 잠금을 확인 (스핀)
// --- 임계 구역 시작 ---
critical section // 한 번에 하나의 프로세스만 이 곳에 도달 가능
// --- 임계 구역 종료 ---
lock = false // 임계 구역 작업 완료 후 잠금을 해제한다. (다른 프로세스가 진입할 수 있도록 false로 설정)
}
이 함수는 여러 프로세스에서 호출될 수 있지만, 임계 구역에는 한 번에 하나의 프로세스만 진입할 수 있음이 보장된다. 여기서 제시된 예는 `while` 루프에서 잠금 획득을 기다리며 계속 확인하는 전형적인 스핀락이다. 하지만 실제 멀티프로세서 환경에서는 잠금 변수를 반복적으로 읽고 쓰는 과정에서 캐시 일관성 문제로 인해 버스 트래픽이 증가하고 성능이 저하될 수 있다. 이 때문에 실제 시스템에서는 '테스트 앤드 테스트 앤드 세트(test-and-test-and-set)'와 같이 먼저 읽기 연산으로 잠금 상태를 확인하고, 잠금이 해제되었을 가능성이 있을 때만 쓰기 연산(TestAndSet)을 시도하여 캐시 효율성을 높이는 기법 등이 사용되기도 한다.
4. 2. 어셈블리 언어를 이용한 구현
상호 배제를 구현하는 한 가지 방법은 다음과 같이 test-and-set 기반 락[5][6]을 사용하는 것이다.enter_region: ; "점프 대상" 태그; 함수 진입점
tsl reg, flag ; Test and Set Lock (TSL); flag는
; 공유 변수; reg 레지스터로 복사되고
; flag는 원자적으로 1로 설정됨
cmp reg, #0 ; enter_region에서 flag가 0이었는가?
jnz enter_region ; reg가 0이 아니면 enter_region으로 점프; 즉,
; enter 시 flag가 0이 아니었음
ret ; 종료; 즉, enter 시 flag가 0이었음.
; 여기에 도달하면 tsl이 0이 아닌 값으로 설정했을 것임; 따라서
; flag와 관련된 자원을 획득했음
leave_region:
move flag, #0 ; flag에 0 저장
ret ; 호출자에게 반환
여기서
tsl은 원자적 명령어이고 flag는 잠금 변수이다. 프로세스는 잠금을 획득하지 않으면 반환되지 않는다.5. 테스트 앤드 테스트 앤드 세트 (Test and Test-and-Set)
기존의 테스트 앤드 세트 명령을 이용한 스핀락 구현은 명령 실행 시 원자적 메모리 접근으로 인해 버스가 잠기고 캐시가 무효화되어 시스템 성능에 부정적인 영향을 미칠 수 있다.
이러한 성능 저하 문제를 완화하기 위해 "테스트 앤드 테스트 앤드 세트" (Test and Test-and-Set) 락 프로토콜이 고안되었다. 이 방식의 핵심 아이디어는 스핀락 대기 중에는 일반적인 메모리 읽기 연산으로 락 상태를 확인하고(첫 번째 테스트), 락이 해제된 것으로 보일 때만 실제 원자적인 테스트 앤드 세트 명령을 사용하여 락 획득을 시도(두 번째 테스트 및 세트)하는 것이다. 이를 통해 테스트 앤드 세트 명령의 실행 횟수를 줄여 버스 잠금으로 인한 오버헤드를 감소시킨다.
5. 1. 의사 코드를 이용한 구현
테스트 앤드 세트 명령으로 스핀락을 구현하면, 명령 실행 시 원자적 메모리 접근으로 인해 버스가 잠기고 캐시가 무효화되어 성능에 좋지 않은 영향을 미칠 수 있다.이러한 성능 저하 문제를 줄이기 위해 "테스트 앤드 테스트 앤드 세트"라는 락 프로토콜이 사용된다. 이 방식의 핵심 아이디어는 스핀락 대기 중에는 테스트 앤드 세트 명령을 사용하지 않고, 락 획득이 성공할 것으로 예상될 때만 해당 명령을 사용하는 것이다. 아래는 의사 코드 예시이다.
''boolean'' locked := false ''// 공유 락 변수''
'''procedure''' EnterCritical() {
:'''while''' (locked == true) '''skip''' ''// 락이 해제된 것처럼 보일 때까지 일반 읽기로 스핀''
:'''while''' TestAndSet(locked) ''// 실제 원자적 락 연산 시도''
::'''while''' (locked == true) '''skip''' ''// 테스트 앤드 세트가 실패하면 락이 해제될 때까지 다시 대기''
}
락 해제 처리는 다음과 같다:
'''procedure''' ExitCritical() {
:locked := false
}
임계 구역에 진입하는 `EnterCritical` 절차에서는 먼저 일반적인 메모리 읽기 연산으로 락 변수(`locked`)를 확인하며 스핀한다. 락이 해제된 것으로 보일 때(`locked == false`) 비로소 `TestAndSet` 명령을 사용하여 실제 락 획득을 시도한다. 만약 다른 스레드가 먼저 락을 획득하여 `TestAndSet`이 실패하면, 다시 일반 읽기 연산으로 스핀하며 대기한다. 이 방식을 통해 `TestAndSet` 명령의 호출 횟수를 줄여 버스 잠금 횟수도 함께 감소시킨다.
만약 사용하는 프로그래밍 언어가 최소 평가 (short-circuit evaluation) 방식을 지원한다면, 락 획득 절차를 다음과 같이 더 간결하게 구현할 수도 있다:
'''procedure''' EnterCritical() {
:'''while''' ( locked == true '''or''' TestAndSet(locked) == true )
::'''skip''' ''// 락이 해제될 때까지 또는 락 획득에 성공할 때까지 스핀''
}
이 코드에서는 `locked`가 `true`이면 `TestAndSet` 함수는 호출되지 않는다 (최소 평가). `locked`가 `false`일 때만 `TestAndSet`이 호출되어 락 획득을 시도한다.
이러한 최적화 기법은 주로 시스템 프로그래밍 분야에서 유용하게 사용된다. 일반적인 애플리케이션 레벨의 병렬 처리에서는 이와 같은 방식을 사용하지 않는 것이 좋다. 때때로 이러한 구현 방식은 "이중 확인 락"(double-checked locking) 패턴과 유사하게 보일 수 있는데, 이는 특정 상황에서 문제를 일으킬 수 있는 안티 패턴 중 하나로 알려져 있다.
6. 성능 평가
일반적으로 락의 성능을 평가하는 주요 지표는 네 가지로, 경합 없는 락 획득 지연 시간, 버스 트래픽, 공정성, 저장 공간이다.[7]
테스트-앤-셋(Test-and-Set, TSL)은 이 중 버스 트래픽과 공정성 측면에서 성능이 낮게 평가된다.
예를 들어, 프로세서 P1이 락을 획득한 상태에서 프로세서 P2가 해당 락을 기다린다고 가정해 보자. P2는 락을 얻기 위해 계속해서 버스(컴퓨터 내 데이터 통로)를 사용하는 트랜잭션을 발생시킨다. 어떤 프로세서가 락을 획득하면, 동일한 락을 얻으려는 다른 모든 프로세서들은 락을 획득할 때까지 반복적으로 버스 트랜잭션을 일으키며 시도한다. 이 과정에서 테스트-앤-셋 방식은 버스 트래픽 요구량을 크게 증가시킨다. 이는 캐시 및 캐시 일관성 문제로 발생하는 다른 트래픽 처리 속도까지 늦추게 된다. 결국 실패한 락 획득 시도로 인해 버스가 포화 상태가 되어 전체 시스템 성능이 저하될 수 있다. 테스트 앤드 테스트-앤드-셋 방식은 락 획득 요청을 지속적으로 보내지 않으므로 TSL보다 개선된 방식으로 평가받는다.
공정성 측면에서는 락이 해제되었을 때 각 프로세서가 락을 획득할 공정한 기회를 얻는지가 중요하다. TSL 방식에서는 극단적인 경우 특정 프로세서가 기아 상태(starvation)에 빠질 수 있다. 즉, 락이 중간에 사용 가능해졌음에도 불구하고 오랫동안 락을 전혀 획득하지 못하는 불공정한 상황이 발생할 수 있다.
반면, TSL의 저장 공간 부담은 거의 없다. 단 하나의 락 변수만 필요하기 때문이다. 또한, 다른 프로세서와의 경합이 없는 상황에서의 락 획득 지연 시간도 짧은 편이다. 이는 하나의 원자적 명령어 실행과 분기 처리만으로 락 획득이 가능하기 때문이다.
7. 세마포어 구현
테스트 앤드 세트(Test-and-Set) 명령어를 사용하여 세마포어를 구현할 수 있다. 단일 프로세서 시스템에서는 이 기법 없이 단순히 인터럽트를 비활성화하는 것만으로도 세마포어 접근 제어가 가능하다. 그러나 여러 개의 프로세서가 있는 멀티 프로세서 시스템에서는 모든 프로세서에서 동시에 인터럽트를 비활성화하더라도, 이것만으로는 충분하지 않다. 인터럽트가 비활성화된 상태에서도 여러 프로세서가 동시에 같은 세마포어에 접근할 수 있기 때문이다. 이러한 문제를 해결하기 위해 멀티 프로세서 환경에서는 테스트 앤드 세트 명령어가 사용될 수 있다.
참조
[1]
논문
The performance of spin lock alternatives for shared-money multiprocessors
1990-01-01
[2]
논문
Wait-free synchronization
http://www.cs.brown.[...]
2007-05-20
[3]
웹사이트
BTS—Bit Test and Set
http://www.felixclou[...]
2016-11-21
[4]
웹사이트
IBM Knowledge Center
http://www.ibm.com/s[...]
2016-11-21
[5]
서적
Operating Systems: Three Easy Pieces
Arpaci-Dusseau Books
[6]
서적
Fundamentals of parallel computer architecture : multichip and multicore systems
[7]
서적
Fundamentals of Parallel Architecture
CRC Press
2016
[8]
서적
Operating System Principles
https://archive.org/[...]
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com