공유 레지스터

분산 컴퓨팅에서 공유 메모리 시스템과 메시지 전달 시스템은 많이 연구되어 온 프로세스 간 통신의 두 가지 수단입니다.공유 메모리 시스템에서 프로세스는 공유 데이터 구조에 액세스하여 통신합니다.공유(읽기/쓰기) 레지스터는 값을 저장하는 공유 데이터 구조의 기본 유형으로 레지스터에 저장된 값을 반환하는 read와 저장된 값을 업데이트하는 write의 두 가지 연산이 있습니다.다른 유형의 공유 데이터 구조에는 읽기, 수정, 쓰기, 테스트 및 세트, 비교 및 스왑 등이 있습니다.동시에 액세스되는 메모리 위치를 레지스터라고 부르기도 합니다.

분류

레지스터는 동시에 액세스 했을 때 만족하는 일관성 조건, 보존 가능한 값의 도메인, 읽기 또는 쓰기 조작으로 액세스 할 수 있는 프로세스의 수에 따라 분류할 수 있으며, 그 결과 총 24개의 레지스터 ^[1]타입이 된다.

공유 레지스터 분류
일관성 조건	도메인	기입하다	읽어주세요
안전한 규칙적인. 원자핵의	바이너리 정수	싱글 라이터 멀티 라이터	싱글 스트로크 멀티플레이어

읽기와 쓰기가 동시에 발생하는 경우 읽기에서 반환되는 값이 고유하게 결정되지 않을 수 있습니다.Lamport는 안전 레지스터, 일반 레지스터 및 원자 ^[1]레지스터의 세 가지 유형의 레지스터를 정의했습니다.세이프 레지스터의 읽기 조작은, 기입 조작과 동시인 경우는 임의의 값을 반환할 수 있습니다.읽기 조작이 기입과 겹치지 않는 경우는, 최신의 기입 조작에 의해서 기입된 값을 반환합니다.일반 레지스터는 읽기 작업이 최근에 완료된 쓰기 작업 또는 중복된 쓰기 작업에 의해 기록된 값을 반환할 수 있다는 점에서 안전 레지스터와 다릅니다.원자 레지스터는 선형화 가능한 보다 강력한 조건을 만족시킨다.

레지스터는 읽기 또는 쓰기 작업으로 액세스할 수 있는 프로세스 수에 따라 특성이 지정될 수 있습니다.싱글 라이터(SW) 레지스터는 1개의 프로세스에서만 쓸 수 있으며 멀티 라이터(MW) 레지스터는 여러 프로세스에서 쓸 수 있습니다.마찬가지로 Single-Reader(SR; 싱글 리더) 레지스터는 한 프로세스에서만 읽을 수 있으며 Multiple-Reader(MR; 멀티 리더) 레지스터는 여러 프로세스에서 읽을 수 있습니다.SWSR 레지스터의 경우 라이터 프로세스와 리더 프로세스가 같을 필요는 없습니다.

구성

아래 그림은 비동기 메시지 전달 시스템에서 SWSR 레지스터 구현부터 SW Snapshot 객체를 사용한 MWMR 레지스터 구현까지의 단계별 구성을 보여줍니다.이러한 종류의 구성은 때때로 시뮬레이션 또는 ^[2]에뮬레이션이라고 불립니다.각 스테이지(3단계 제외)에서 오른쪽 오브젝트 타입은 왼쪽 오브젝트 타입으로 구현할 수 있습니다.각 단계(3단계 제외)의 구성은 다음과 같다.스냅샷 개체 구성에 대한 자세한 내용을 설명하는 기사가 있습니다.

\displaystyle {{\operatorname {Message-passing} \atop (MP) ~ System} -> [ { \ text { Stage 1 } ]SWSR~atomic->[][{\text{Stage 2}}]SWMR -> [ ][ { \ text { Stage 3 } ]SW~snapshot->[][{\text{Stage 4}}]MMR}}}

공유 레지스터 구성 단계

구현은 모든 실행에 대해 다음 두 가지 속성을 충족하는 선형화 순서가 있는 경우 선형화할 수 있습니다.

연산이 선형화 순서대로 순차적으로 이루어지면 동시 실행과 동일한 결과가 반환됩니다.
연산 op2가 시작되기 전에 연산 op1이 종료되면 선형화에서 연산 op1이 op2보다 우선한다.

메시지 전달 시스템에 원자성 SWSR 레지스터 구현

프로세스가 크래쉬 할 가능성이 있는 경우에도 SWSR 아토믹(선형화 가능) 레지스터는 비동기 메시지 전달 시스템에 실장할 수 있습니다.수신자에게 메시지를 전달하거나 로컬 명령을 실행하는 프로세스에는 시간 제한이 없습니다.즉, 프로세스는 응답이 느리거나 단순히 크래쉬하는 프로세스를 구별할 수 없습니다.

MP 시스템에서의 Atomic SWSR 레지스터 구현

Attiya, Bar-Noy 및^[3] Dolev가 제공하는 구현에는 n > $2f$ 가 $필요$ 합니다. $여기$ 서 n은 시스템 내 프로세스의 총수, $f$ 는 실행 중에 크래시할 수 있는 프로세스의 최대수입니다.알고리즘은 다음과 같습니다.

작가.

독자

모든 프로세스에 대한 WRITE(v) t++ 전송(v,t)은 확인 응답을 받을 때까지 대기합니다(n-f).

READ()는 모든 프로세스에 읽기 요청을 전송하여 응답(n-f)을 얻을 때까지 대기하며 t가 가장 큰 v를 선택합니다.

연산의 선형화 순서는 쓰기가 발생하는 순서대로 선형화하고 값이 반환되는 쓰기 뒤에 읽기를 삽입하는 것입니다.구현이 선형화 가능한지 확인할 수 있습니다.속성 2는 특히 op1이 write이고 op2가 read이고 read가 write 직후일 때 확인할 수 있습니다.우리는 모순으로 나타낼 수 있다.읽기에서 쓰기가 인식되지 않는다고 가정하고, 구현에 따라 n개의 프로세스 중 $크기 (n$ - f)의 2개의 분리된 세트가 있어야 합니다. $따라서$ 2 * ( $n$ - $f) n$ n은 n $2$ 2f로 $이어집니다$ .이것은 n > $2f$ 라는 $사실$ 과 모순됩니다.따라서 읽기는 해당 쓰기에서 쓴 값을 하나 이상 읽어야 합니다.

SWSR 레지스터로부터의 SWMR 레지스터 구현

SWMR 레지스터는 한 프로세스에서만 쓸 수 있지만 여러 프로세스에서 읽을 수 있습니다.

SWSR 레지스터를 이용한 SWMR 레지스터 구현
독자들 라이터	$R_{1}$	$R_{2}$	⋯	$R_{n}$
$R_{1}$	A[1,1]	A[1,2]	...	A[1,n]
$R_{2}$	A[2,1]	A[2,2]	...	A[2,n]
⋮	...	...	...	...
$R_{n}$	A[n,1]	A[n,2]	...	A[n,n]
$w$	A[n+1,1]	A[n+1,2]	...	A[n+1,n]

swMR 레지스터를 읽을 수 있는 프로세스의 수를 n으로 합니다. $R i$ , $0$ < $i nn$ 은 SWMR 레지스터의 리더를 참조합니다.W를 SWMR의 단일 라이터로 $합니다$ .오른쪽 그림은 n $(n +$ 1) $개$ 의 SWSR 레지스터 배열을 사용한SWMR 레지스터 구성을 나타내고 있습니다.어레이는 A로 $나타냅니다$ .각 SWSR $레지스터$ A $[i, j]$ 는 0 $< i4 n이면$ R에 $의해 i$ 쓰기 가능하며, i $= n$ + $1$ 이면 w에 $쓰기$ 가능하다. 각 SWSR $레지스터$ A $[i, j]$ 는 R에 $의해 j$ 읽힌다.읽기 및 쓰기의 실장은 다음과 같습니다.

작가.

w: WRITE(v)

j = i..n t++의 경우, A[n+1,j] 끝에 (v,t)를 씁니다.

독자들

$R i$ : READ()

k = 1..(n+1) (V[k],T[k] <- 모든 l, T[k] > = T[l] r <- V[k] t <- T[k] r <- T[k] t <- T[k]가 A[i,j]의 반환을 위해 (r,t)로 쓰도록 take k의 끝을 읽습니다.

연산의 t 값은 연산이 쓰는 t 값이며 연산은 t 값으로 선형화됩니다.쓰기와 읽기의 t-값이 같으면 읽기 전에 쓰기를 주문합니다.여러 판독치의 t값이 동일한 경우 시작 시간까지 정렬합니다.

소프트웨어 스냅샷 개체에서 MMR 레지스터 구현

크기 n의 SW Snapshot 객체를 사용하여 MMR 레지스터를 구성할 수 있습니다.

작가.	독자들
P_i: WRITE(WRITE)	P_i: READ()
(v1, t1), ..., (vn, tn) <- V.SCAN()은 t = max(t1, ..., tn) + 1V로 합니다.업데이트(i, (v, t))	검색 결과 타임스탬프가 가장 큰 V.SCAN 반환 값 (가장 큰 타임스탬프 오른쪽 페어를 사용하여 동점 해소)

선형화 순서는 다음과 같습니다.쓰기 작업을 t 값으로 정렬합니다.여러 쓰기의 t-값이 동일한 경우 앞에 작은 프로세스 ID를 사용하여 작업을 주문합니다.값이 반환되는 읽기 직후에 프로세스 ID별로 연결을 끊고, 그래도 동점일 경우 시작 시간별로 연결을 끊습니다.

「」를 참조해 주세요.

레퍼런스

^ ^a ^b Kshemkalyani, Ajay D.; Singhal, Mukesh (2008). Distributed computing : principles, algorithms, and systems. Cambridge: Cambridge University Press. pp. 435–437. ISBN 9780521876346.
^ Attiya, Hagit; Welch, Jennifer (Mar 25, 2004). Distributed computing: fundamentals, simulations, and advanced topics. John Wiley & Sons, Inc. ISBN 978-0-471-45324-6.
^ Attiya, Hagit; Bar-Noy, Amotz; Dolev, Danny (1990). "Sharing Memory Robustly in Message-passing Systems". Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing. PODC '90: 363–375. doi:10.1145/93385.93441. ISBN 089791404X.

[DCFSA-1] Kshemkalyani, Ajay D.; Singhal, Mukesh (2008). Distributed computing : principles, algorithms, and systems. Cambridge: Cambridge University Press. pp. 435–437. ISBN 9780521876346.

[2] Attiya, Hagit; Welch, Jennifer (Mar 25, 2004). Distributed computing: fundamentals, simulations, and advanced topics. John Wiley & Sons, Inc. ISBN 978-0-471-45324-6.

[3] Attiya, Hagit; Bar-Noy, Amotz; Dolev, Danny (1990). "Sharing Memory Robustly in Message-passing Systems". Proceedings of the Ninth Annual ACM Symposium on Principles of Distributed Computing. PODC '90: 363–375. doi:10.1145/93385.93441. ISBN 089791404X.

[1]

[2]

[3]

Search

공유 레지스터

네임스페이스

더

목차

분류

구성

메시지 전달 시스템에 원자성 SWSR 레지스터 구현

SWSR 레지스터로부터의 SWMR 레지스터 구현

소프트웨어 스냅샷 개체에서 MMR 레지스터 구현

「」를 참조해 주세요.

레퍼런스

Search

공유 레지스터

분류

구성

메시지 전달 시스템에 원자성 SWSR 레지스터 구현

SWSR 레지스터로부터의 SWMR 레지스터 구현

소프트웨어 스냅샷 개체에서 MMR 레지스터 구현

「 」를 참조해 주세요.

레퍼런스

「」를 참조해 주세요.