합의 수 n과 합의 수 무한의 차이

Question

책에 동시 프로그래밍:알고리즘, 원리 및 기초 Michel Raynal의 섹션 16.5.1, 정리 75에서는 다음과 같이 말합니다.

비교&교환 개체에는 무한한 합의 수가 있습니다.

섹션 16.5.2에서 Lemma 40은 다음과 같이 말합니다.

mem-to-mem-swap 객체 유형은 n개의 프로세스로 구성된 시스템에서 합의 번호 n을 갖습니다.

그런 다음 섹션 16.1에서 작성자는 Compare&swap과 men-to-mem-swap을 모두 합의 수가 무한한 개체로 테이블에 넣습니다.

그렇다면 합의 번호 n을 갖는 개체와 합의 번호 무한을 갖는 개체의 차이점은 무엇입니까?

Answer 1

객체의 합의 수는 대기 없이 그러한 객체 하나와 동기화할 수 있는 최대 동시 프로세스 수입니다(여기서는 대기가 없다는 의미에 대해서는 다루지 않겠습니다).예를 들어, 읽기 및 쓰기 작업만 있는 레지스터는 대기 없는 동기화에 전혀 도움이 되지 않으므로 합의 번호 1이 있습니다.테스트 및 설정 작업이 있는 레지스터는 대기 없이 두 프로세스를 동기화하는 데 사용할 수 있지만 3개 이상은 동기화할 수 없으므로 테스트 및 설정의 합의 수는 2입니다.

$n$-프로세스가 여러 레지스터에 원자적으로 쓸 수 있는 레지스터 할당은 최대 $2n-2$ 대기 시간 없이 동기화하는 프로세스가 있는 경우 $n$ 레지스터.더 많은 프로세스에는 더 많은 레지스터가 필요합니다.따라서 다음으로 구성된 객체의 합의 번호는 다음과 같습니다. $n$ 원자적으로 할당할 수 있는 레지스터는 다음과 같습니다. $2n-2$.

비교 및 교체 작업이 포함된 단일 레지스터는 대기 없이 모든 프로세스를 동기화하는 데 충분합니다.따라서 비교 및 ​​교환의 합의 수는 무한합니다.

Lemma 40은 mem-and-swap 객체가 시스템의 모든 프로세스의 대기 없는 동기화를 허용한다고 명시합니다. $n$ 동시 프로세스(수에 제한 없음) $n$.이는 임의의 숫자에 대해 $n$, mem-and-swap의 합의 수는 최소한 $n$.(합의 번호를 명시 ~이다 $n$ 시스템에서 $n$ 프로세스는 합의 수의 정의가 실제로 전체 프로세스 수에 의존하지 않기 때문에 약간 잘못된 이름입니다.) mem-and-swap의 합의 수는 최소한 $n$ 어떠한 것도 $n$, 그것은 무한합니다.

Raynal의 책이 아닌 다른 출처를 선호한다면 원본을 읽어보세요. Maurice Herlihy의 논문.