선형화가능성
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
선형화가능성은 1987년 허리히와 윙에 의해 무모순성 모델로 도입되었으며, 병렬로 실행되는 연산이 순차적으로 실행된 것처럼 보이도록 보장하는 일관성 모델이다. 선형화가능한 이력은 메서드 호출과 응답을 재배치하여 순차 이력을 만들 수 있으며, 이 순차 이력이 객체의 순차 정의에 어긋나지 않고, 원래 이력에서 응답 순서가 유지되어야 한다. 직렬화 가능성보다 더 강력한 제약 조건을 가지며, 각 연산이 특정 시점에 원자적으로 수행되는 것처럼 보이도록 보장한다. 선형화 가능성은 원자적 명령어, 임계 구역, 고수준 원자적 연산 등을 통해 달성될 수 있으며, 카운터와 같은 예제를 통해 그 개념을 설명할 수 있다.
더 읽어볼만한 페이지
- 일관성 모델 - 원자성
원자성은 분자를 구성하는 원자 수로, 분자는 원자성에 따라 단원자, 이원자, 삼원자 분자 등으로 나뉘며, 금속이나 탄소는 원자성이 2로 간주되고 단원자 분자의 원자성은 분자량을 원자량으로 나누어 계산한다. - 일관성 모델 - 캐시 일관성
캐시 일관성은 다중 프로세서 시스템에서 공유 메모리 데이터의 일관성을 유지하기 위해 읽기 및 쓰기 동작을 정의하며, 스누핑, 디렉터리 기반 방식 등의 메커니즘과 다양한 모델 및 프로토콜이 사용된다. - 동시성 제어 - 세마포어
세마포어는 데이크스트라가 고안한 정수 변수로, P/V 연산을 통해 자원 접근을 제어하고 동기화 문제를 해결하며, 계수 세마포어와 이진 세마포어로 나뉘어 멀티스레드 환경에서 자원 관리 및 스레드 동기화에 기여한다. - 동시성 제어 - 모니터 (동기화)
모니터는 공유 자원 접근을 제어하여 프로세스 간 동기화를 구현하는 프로그래밍 구조로, 뮤텍스 락, 조건 변수 등으로 구성되어 경쟁 상태를 방지하며 여러 프로그래밍 언어에서 지원된다. - 트랜잭션 처리 - 2단계 커밋 프로토콜
2단계 커밋 프로토콜은 분산 컴퓨팅 환경에서 트랜잭션의 원자성을 보장하는 분산 알고리즘으로, 조정자와 참가자로 구성되어 모든 참가자가 트랜잭션을 완료하거나 아무도 완료하지 못하도록 하며, 커밋 요청 및 커밋 단계를 거쳐 모든 참가자의 동의를 얻어야 커밋된다. - 트랜잭션 처리 - 온라인 트랜잭션 처리
온라인 트랜잭션 처리(OLTP)는 실시간 데이터베이스 트랜잭션 처리 방식으로, 가용성, 속도, 동시성, 내구성을 목표로 은행, 항공사, 전자 상거래 등에서 활용된다.
| 선형화가능성 |
|---|
2. 역사
선형화가능성은 1987년 허리히와 윙이 일관성 모델로 처음 소개하였다.[1] 기존의 원자성 개념은 "원자적인 연산은 동시 연산에 의해 중단될 수 없는(또는 중단되지 않는) 연산"과 같이 연산의 시작과 종료 시점이 모호하다는 문제점이 있었다.[1] 선형화 가능성은 이러한 정의를 더 제한하여 동시성 환경에서 연산의 순서를 명확하게 하였다.[1]
선형화가능성은 1987년 헐리히(Herlihy)와 윙(Wing)이 무모순성 모델로 제안하였다.[2] 원자적 연산은 다른 병행 연산에 의해 중단되지 않는 연산이지만, 연산의 시작과 종료 시점이 명확하지 않다는 한계가 있었다. 선형화 가능성은 이러한 정의를 더욱 엄격하게 만든 개념이다.
3. 수학적 정의
원자적 객체는 순차적인 정의를 통해 즉시 그리고 완벽하게 이해할 수 있으며, 병렬로 실행되는 연산들은 언제나 하나씩 차례대로 효과가 나타나는 것처럼 보인다. 즉, 어떠한 모순도 나타나지 않는다. 구체적으로, 선형화 가능성은 모든 연산에서 시스템의 불변량을 볼 수 있게 하고 이를 유지한다. 모든 연산이 개별적으로 불변량을 보존한다면, 시스템 전체적으로도 불변량이 유지된다.
실행 이력(History)실행 이력은 여러 스레드가 만들어낸 일련의 메서드 호출(invocation)과 응답(response)의 순서열이다. 각 메서드 호출은 그에 해당하는 응답을 가지며, 이를 통해 임의의 객체의 사용을 모델링할 수 있다.
예를 들어, 스레드 A와 B가 어떤 락(lock)을 획득하려 시도하고, 실패하면 백오프(backoff)하는 경우를 생각해 보자. 이는 두 스레드가 락 연산을 호출하고, 한 스레드는 "성공" 응답을, 다른 스레드는 "실패" 응답을 받는 것으로 모델링할 수 있다.A lock 메서드 호출 B lock 메서드 호출 A 실패 응답 B 성공 응답
순차 이력(Sequential History)순차 이력은 모든 메서드 호출이 즉시 응답을 받는 형태의 이력이다. 순차 이력은 병행성을 가지지 않으므로, 추론할 필요가 없다. 하지만 위에서 제시된 예시는 순차 실행이 아니므로(즉, 순차 이력이 아니므로) 추론이 필요하며, 이를 위해 선형화 가능성이 존재한다.
선형화 가능성의 조건어떤 이력이 선형화 가능하려면 다음 조건을 만족해야 한다.
처음 두 조건은 직렬화가능성과 동일하지만, 세 번째 조건은 선형화 가능성에만 해당하며, 헐리히와 윙의 주요 기여이다.[2]
예시를 통한 이해위에서 제시된 락 획득 예시를 두 가지 순서로 재배치해 보자.
| A lock 메서드 호출 | A 실패 응답 | B lock 메서드 호출 | B 성공 응답 |
이 경우, 객체가 잠기지 않았는데 A의 ''lock''이 실패하므로, 위에서 언급한 규칙 중 두 번째 규칙에 위배된다.
| B lock 메서드 호출 | B 성공 응답 | A lock 메서드 호출 | A 실패 응답 |
위와 같이 재배치하면 정확한 순차 이력이 된다. 여기서는 ''응답'' 뒤에 ''메서드 호출''이 있는 경우가 없기 때문에, ''lock''을 호출한 순서를 재배치하여 문제를 해결하였다.
3. 1. 선형화 가능성 vs. 직렬화 가능성
직렬화 가능성은 여러 트랜잭션이 동시에 실행될 때, 그 결과가 마치 트랜잭션들이 어떤 순서대로 하나씩 실행된 것과 동일하게 보이도록 보장하는 속성이다. 선형화 가능성은 직렬화 가능성보다 더 강력한 제약 조건을 가진다. 직렬화 가능성은 트랜잭션 간의 순서를 보장하지만, 선형화 가능성은 각 연산이 특정 시점에 원자적으로 수행되는 것처럼 보이도록 보장한다.[2]선형화 가능성은 개별 객체를 별도로 고려할 때 유리하다. 여러 객체가 선형화 가능하면 전체 시스템도 선형화 가능해지기 때문이다.
예를 들어, 두 개의 스레드 A와 B가 락(lock)을 통해 상호작용하는 경우를 생각해보자.
| A lock 호출 시작 | A 성공 응답(lock) | B unlock 호출 시작 | B 성공 응답(unlock) | A unlock 호출 시작 | A 성공 응답(unlock) |
이 이력은 선형화 가능하지 않다. 응답 순서를 유지하면서 동등한 다른 순차 이력으로 바꿀 수 없기 때문이다. 그러나 직렬화 가능성만 고려하면, B의 ''unlock''을 맨 앞으로 옮기고, 객체가 이력 시작에 이미 잠긴 상태라고 가정하여 재배치할 수 있다.
| B unlock 호출 시작 | B 성공 응답(unlock) | A lock 호출 시작 | A 성공 응답(lock) | A unlock 호출 시작 | A 성공 응답(unlock) |
A와 B 사이에 다른 통신이 없다면, 이는 가능하다.
다른 예시로, 다음과 같은 실행 이력이 있다고 하자.
| A가 lock을 호출함 | B가 lock을 호출함 | A가 "실패" 응답을 받음 | B가 "성공" 응답을 받음 |
이 이력은 순차적이지 않으므로 추론하기 어렵다. 선형화 가능성을 적용하여 다음과 같이 재정렬할 수 있다.
| B가 lock을 호출함 | B가 "성공" 응답을 받음 | A가 lock을 호출함 | A가 "실패" 응답을 받음 |
이 순차적 이력은 객체의 순차적 정의와 일치하므로 선형화 가능하다.
3. 2. 선형화 지점 (Linearization Point)
모든 함수 호출은 호출과 응답 사이의 특정 시점, 즉 선형화 지점에서 즉시 효과를 내는 것처럼 보이도록 정의할 수 있다.[2] 이 정의는 증명이 용이하고 직관적이며, "원자적"이라는 용어를 사용하게 된 배경이기도 하다.[2]선형화 지점에 대한 예시는 다음과 같다.
- compare-and-swap 기반 카운터: 첫 번째 (그리고 유일한) 성공적인 compare-and-swap 업데이트의 선형화 지점.
- 락 기반 카운터: 락이 유지되는 동안 (경쟁 가능한 작업이 실행되지 않기 때문).
4. 원자적 명령어
현대 프로세서는 잠금 및 락프리 및 웨이트프리 알고리즘 구현에 사용되는 다양한 원자적 명령어를 제공한다. 이러한 명령어는 컴파일러 및 운영 체제 작성자가 직접 사용하지만, 더 높은 수준의 언어에서는 바이트 코드 및 라이브러리 함수로 추상화된다.[3]
C 표준 및 SUSv3는 간단한 원자적 읽기 및 쓰기를 위해 `sig_atomic_t`를 제공하지만, 증가 또는 감소는 원자적으로 보장되지 않는다.[3] 더 복잡한 원자적 연산은 `stdatomic.h`를 제공하는 C11에서 사용할 수 있다. 컴파일러는 하드웨어 기능 또는 GCC의 libatomic과 같은 라이브러리를 사용하여 연산을 구현한다.[3]
ARM 명령어 세트는 `LDREX` 및 `STREX` 명령어를 제공하여 원자적 메모리 접근을 구현한다. 이 명령어들은 프로세서에서 구현된 독점 모니터를 사용하여 특정 주소에 대한 메모리 접근을 추적한다.[4] `LDREX` 및 `STREX` 호출 사이에 컨텍스트 스위치가 발생하면 `STREX`가 실패하고 연산을 다시 시도해야 한다.[4] 64비트 ARMv8-A 아키텍처에서는 바이트, 반 워드, 워드 및 더블 워드 크기에 대한 `LDXR` 및 `STXR` 명령어를 제공한다.[5]
많은 시스템은 원자적 비교-앤-스왑 명령어를 제공한다. 이는 메모리 위치에서 값을 읽고, 지정된 "기대값"과 비교하여, 일치하는 경우 "새로운" 값을 기록하고 성공 여부를 반환한다.
5. 고수준 원자적 연산
선형화 가능성을 달성하는 가장 쉬운 방법은 임계 구역에서 기본 연산 그룹을 실행하는 것이다. 독립적인 연산은 선형화 가능성을 위반하지 않는 한, 임계 구역을 겹치도록 할 수 있다. 이러한 접근 방식은 많은 잠금의 비용과 증가된 병렬 처리의 이점 사이에서 균형을 맞춘다.
또 다른 접근 방식은 하드웨어에서 제공하는 원자적 기본 요소를 사용하여 선형화 가능한 객체를 설계하는 것이다. 이는 사용 가능한 병렬 처리를 극대화하고 동기화 비용을 최소화할 수 있지만, 객체가 올바르게 동작함을 보여주는 수학적 증명이 필요하다.
트랜잭션 메모리는 임계 구역과 유사하게, 사용자가 다른 스레드와 격리되어 실행되어야 하는 순차 코드를 표시하고, 구현은 코드가 원자적으로 실행되도록 보장한다. Spring Framework를 사용할 때 메서드에 @Transactional을 주석 처리하면 모든 포함된 데이터베이스 상호 작용이 단일 데이터베이스 트랜잭션에서 발생하도록 보장한다. 트랜잭션 메모리는 한 단계 더 나아가 모든 메모리 상호 작용이 원자적으로 발생하도록 보장한다. 데이터베이스 트랜잭션과 마찬가지로 트랜잭션 구성, 특히 데이터베이스 및 인 메모리 트랜잭션과 관련하여 문제가 발생한다.
선형화 가능한 객체를 설계할 때 일반적인 주제는 전부 또는 전무 인터페이스를 제공하는 것이다. 즉, 연산이 완전히 성공하거나 실패하여 아무것도 수행하지 않는다. (ACID 데이터베이스는 이 원칙을 원자성이라고 한다.) 연산이 실패하면 (일반적으로 동시 연산으로 인해) 사용자는 다시 시도해야 하며, 일반적으로 다른 연산을 수행한다. 예를 들면 다음과 같다.
- 비교-및-교환은 해당 내용이 제공된 이전 값과 일치하는 경우에만 새 값을 위치에 쓴다. 사용자는 위치를 읽고, 쓸 새 값을 계산하고, CAS(비교-및-교환)로 쓴다. 값이 동시에 변경되면 CAS가 실패하고 사용자는 다시 시도한다.
- 로드-링크/저장-조건부는 이 패턴을 보다 직접적으로 인코딩한다. 사용자는 로드-링크로 위치를 읽고, 쓸 새 값을 계산하고, 저장-조건부로 쓴다. 값이 동시에 변경되면 SC(저장-조건부)가 실패하고 사용자는 다시 시도한다.
- 데이터베이스 트랜잭션에서 동시 연산(예: 교착 상태)으로 인해 트랜잭션을 완료할 수 없는 경우, 트랜잭션은 중단되고 사용자는 다시 시도해야 한다.
많은 시스템은 원자적 비교-및-교환 명령어를 제공한다. 이는 메모리 위치에서 값을 읽고, 해당 값을 사용자가 지정한 "기대값"과 비교하여, 두 값이 일치하는 경우 "새로운" 값을 기록하고 업데이트 성공 여부를 반환한다. 이를 이용하여 비원자 카운터 알고리즘을 수정할 수 있다.
6. 예제
선형화가능성이 보장되지 않는 비원자적 구현 예시를 통해 선형화 가능성을 설명할 수 있다.
두 개의 프로세스가 값이 0으로 초기화된 단일 카운터 객체에 접근하여 실행된다고 가정한다.
# 첫 번째 프로세스가 레지스터의 값을 0으로 읽는다.
# 첫 번째 프로세스가 값에 1을 더한다. 카운터의 값은 1이 되어야 하지만, 새로운 값을 레지스터에 다시 기록하기 전에 일시 중단될 수 있다. 그동안 두 번째 프로세스가 실행된다.
# 두 번째 프로세스가 레지스터의 값을 읽는다. 값은 여전히 0이다.
# 두 번째 프로세스가 값에 1을 더한다.
# 두 번째 프로세스가 새로운 값을 레지스터에 기록한다. 이제 레지스터의 값은 1이다.
두 번째 프로세스가 실행을 완료하고 첫 번째 프로세스가 중단된 지점부터 계속 실행된다.
# 첫 번째 프로세스가 레지스터에 1을 기록한다. 다른 프로세스가 이미 레지스터의 값을 1로 업데이트했다는 것을 알지 못한다.
위의 예에서 두 개의 프로세스가 증가 명령을 호출했지만 객체의 값은 0에서 1로 증가했을 뿐, 2로 증가해야 했다.[1] 이처럼 시스템이 선형화 가능하지 않으면 증가 연산 중 하나가 손실될 수 있다.[1]
위의 예는 데이터 구조 구현을 신중하게 고려해야 하며, 선형화 가능성이 시스템의 정확성에 어떤 영향을 미칠 수 있는지 보여준다.[1]
선형화 가능하거나 원자적인 카운터 객체를 구현하기 위해, 이전 구현을 수정하여 각 프로세스 Pi는 자체 레지스터 Ri를 사용하도록 한다.[1]
각 프로세스는 다음과 같은 알고리즘에 따라 증가시키고 읽는다.[1]
'''증가:'''[1]
# 레지스터 Ri의 값을 읽는다.
# 값에 1을 더한다.
# 새 값을 Ri에 다시 쓴다.
'''읽기:'''[1]
# 레지스터 R1, R2, ... Rn을 읽는다.
# 모든 레지스터의 합을 반환한다.
이 구현은 원래 구현의 문제를 해결한다. 이 시스템에서 증가 연산은 쓰기 단계에서 선형화된다. 증가 연산의 선형화 지점은 해당 연산이 새 값을 해당 레지스터 Ri에 쓸 때이다. 읽기 연산은 읽기에서 반환된 값이 각 레지스터 Ri에 저장된 모든 값의 합과 같을 때 시스템의 지점에 선형화된다.[1]
이는 간단한 예시이다. 실제 시스템에서는 연산이 더 복잡해질 수 있으며, 도입되는 오류는 매우 미묘할 수 있다. 예를 들어, 메모리에서 64비트 값을 읽는 것은 실제로 두 개의 순차적인 32비트 메모리 위치를 읽는 것으로 구현될 수 있다. 프로세스가 처음 32 비트만 읽었고, 두 번째 32 비트를 읽기 전에 메모리의 값이 변경되면 원래 값도 새 값도 아닌 혼합된 값을 갖게 된다.[1]
또한 프로세스가 실행되는 특정 순서에 따라 결과가 변경될 수 있으며, 이러한 오류를 감지, 재현 및 디버그하기 어렵게 만든다.[1]
6. 1. 카운터
여러 프로세스가 증가시킬 수 있는 간단한 카운터를 예로 들어 선형화 가능성을 설명할 수 있다.많은 일반적인 시스템에서 이벤트 발생 횟수를 추적하기 위해 카운터를 사용한다. 카운터 객체는 여러 프로세스에서 접근할 수 있으며, 다음과 같은 두 가지 연산을 가진다.
- '''증가''': 카운터에 저장된 값에 1을 더하고 확인 응답을 반환한다.
- '''읽기''': 카운터에 저장된 현재 값을 변경하지 않고 반환한다.
공유 레지스터를 사용하여 카운터 객체를 구현할 수 있다. 처음 시도하는(비원자적인) 구현은 선형화가능하지 않다. 이 구현은 다음과 같다.
'''증가'''
# 레지스터 R의 값을 읽는다.
# 값에 1을 더한다.
# 새로운 값을 레지스터 R에 다시 쓴다.
'''읽기'''
# 레지스터 R을 읽는다.
이 간단한 구현은 선형성을 보장할 수 없다. 예를 들어, 두 프로세스가 값이 0으로 초기화된 카운터 객체에 접근한다고 가정해 보자.
# 첫 번째 프로세스가 레지스터 값을 0으로 읽는다.
# 첫 번째 프로세스는 값에 1을 더해 카운터 값은 1이 되어야 하지만, 새로운 값을 레지스터에 쓰기 전에 중단(인터럽트)되고, 그 사이에 두 번째 프로세스가 실행된다.
# 두 번째 프로세스는 레지스터 값을 읽지만, 값은 아직 0이다.
# 두 번째 프로세스는 그 값에 1을 더한다.
# 두 번째 프로세스가 새로운 값을 레지스터에 쓰고, 레지스터의 값은 1이 된다.
두 번째 프로세스는 실행을 종료하고, 첫 번째 프로세스는 중단된 지점부터 실행을 재개한다.
# 첫 번째 프로세스는 다른 프로세스가 이미 레지스터 값을 1로 갱신했음을 알지 못하고, 레지스터에 1을 쓴다.
위의 예에서 두 프로세스는 증가 명령을 호출했지만, 객체의 값은 원래 0에서 2로 증가해야 하는데 1로만 증가했다. 시스템이 선형화를 보장할 수 없기 때문에 증가 연산 중 하나가 손실된 것이다.
이러한 문제를 해결하기 위해 각 프로세스 Pi가 고유한 레지스터 Ri를 사용하는 아토믹 카운터 객체를 구현할 수 있다. 각 프로세스는 다음 알고리즘에 따라 증가 및 읽기를 수행한다.
'''증가'''
# 레지스터 Ri의 값을 읽는다.
# 그 값에 1을 더한다.
# 새로운 값을 Ri로 되돌린다.
'''읽기'''
# 레지스터 R1, R2...Rn을 읽는다.
# 모든 레지스터의 합계를 반환한다.
이 구현에서는 증가 연산은 쓰기 단계에서 선형화된다. 증가 연산의 선형화 가능성 지점은 해당 연산이 레지스터 Ri에 새로운 값을 쓸 때이다. 읽기 연산은 읽기에 의해 반환된 값이 각 레지스터 Ri에 저장된 모든 값의 합계와 같을 때 시스템의 어느 시점에서 선형화된다.
실제 시스템에서는 연산이 더 복잡하고 오류도 미묘하다. 예를 들어, 64비트 값을 메모리에서 읽을 때 2개의 32비트 메모리 위치를 연속으로 읽는 경우가 있다. 프로세스가 첫 번째 32비트만 읽고 두 번째 32비트를 읽기 전에 메모리 내의 값이 변경되면, 원래 값도 아니고 새로운 값도 아닌 섞인 값을 갖게 된다.
참조
[1]
논문
The Computability of Relaxed Data Structures: Queues and Stacks as Examples
http://www.faculty.i[...]
[2]
논문
Linearizability: A Correctness Condition for Concurrent Objects
[3]
서적
The Linux Programming Interface
https://books.google[...]
No Starch Press
2018-09-07
[4]
웹사이트
ARM Synchronization Primitives Development Article
https://developer.ar[...]
[5]
웹사이트
ARMv8-A Synchronization primitives
https://documentatio[...]
2023-12-14
[6]
서적
Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing – PODC '04
ACM
[7]
논문
The Computability of Relaxed Data Structures: Queues and Stacks as Examples
http://www.faculty.i[...]
[8]
논문
Linearizability: A Correctness Condition for Concurrent Objects
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com