트레이버 스택

Treiber stack

Treiber 스택알고리즘은 세밀한 동시성 프리미티브 비교 및 [1]스왑을 사용하는 확장 가능한 잠금 프리 스택입니다.R. Kent Treiber는 1986년 그의 기사 "Systems Programming:평행주의에 대처하다.[2]

기본원칙

알고리즘의 기본 원칙은 추가하려는 항목이 작업을 시작한 이후 추가된 유일한 항목임을 알고 있을 때에만 스택에 새로운 항목을 추가하는 것입니다.이는 Compare-and-Swap을 사용하여 이루어집니다.항목을 스택에 푸시하려면 먼저 스택의 맨 위(오래된 헤드)를 가져와서 새 항목 뒤에 배치하여 새 헤드를 만듭니다.그런 다음 이전 헤드를 현재 헤드와 비교합니다.두 개의 헤드가 일치할 경우 오래된 헤드를 새 헤드로 바꿀 수 있습니다. 일치하지 않을 경우 다른 스레드가 항목을 스택에 추가했음을 의미하므로 이 경우 다시 시도해야 합니다.

스택에서 항목을 팝업할 때 항목을 반환하기 전에 작업이 시작된 후 다른 스레드가 새 항목을 추가하지 않았는지 확인해야 합니다.

정확성

일부 언어(특히 가비지 컬렉션이 없는 언어)에서는 Treiber 스택이 ABA 문제에 걸릴 수 있습니다.스택에서 요소를 삭제하려고 하는 프로세스(아래 팝 루틴에서 비교 및 설정되기 직전)에는 다른 프로세스에서 헤드가 동일하지만 두 번째 요소는 다르도록 스택을 변경할 수 있습니다.비교 및 스왑을 통해 스택의 헤드가 스택 내의 오래된 두 번째 요소로 설정되며 전체 데이터 구조가 혼합됩니다.단, Java 런타임에 의해 제공되는 강력한 보증(새로 작성된 에일리어스가 없는 오브젝트 참조가 도달 가능한 다른 오브젝트와 동일한 것은 불가능) 때문에 이 페이지의 Java 버전은 이 문제에 해당되지 않습니다.

문제가 있는 일련의 이벤트는 매우 드물기 때문에 ABA 등의 장애 테스트는 매우 어려울 수 있습니다.모델 체크는 이러한 문제를 발견하는 훌륭한 방법입니다.예를 들어 "통신 시스템의 모델링 및 분석"[3]의 연습 7.3.3을 참조하십시오.

Java의 예

다음은 Java Concurrency in Practice에 의해 제공되는 Java에서의 Treiber Stack 구현입니다.

수입품 java.concurrent.atomic 입니다.*;  수입품 net.jcip.informations.*;  /** * Concurrent Stack * * Treiber 알고리즘을 사용한 논블로킹 스택 * * @author Brian Goetz와 Tim Peierls */ @Thread Safe 일반의 학급 Concurrent Stack(동시 스택) < >E> {     아토믹 레퍼런스< >노드< >E>> 정상 = 신규 아토믹 레퍼런스< >노드< >E>>();      일반의 공백 밀다(E 아이템) {         노드< >E> new Head = 신규 노드< >E>(아이템);         노드< >E> old Head(올드헤드);         하다 {             old Head(올드헤드) = 정상.얻다();             new Head.다음 분. = old Head(올드헤드);         } 하는 동안에 (!정상.compareAndSet(비교 & 세트)(old Head(올드헤드), new Head));     }      일반의 E 팝() {         노드< >E> old Head(올드헤드);         노드< >E> new Head;         하다 {             old Head(올드헤드) = 정상.얻다();             한다면 (old Head(올드헤드) == 무효)                 돌아가다 무효;             new Head = old Head(올드헤드).다음 분.;         } 하는 동안에 (!정상.compareAndSet(비교 & 세트)(old Head(올드헤드), new Head));         돌아가다 old Head(올드헤드).아이템;     }      사적인 정적인 학급 노드 < >E> {         일반의 최종 E 아이템;         일반의 노드< >E> 다음 분.;          일반의 노드(E 아이템) {             이것..아이템 = 아이템;         }     } }

레퍼런스

  1. ^ Hendler, D., Shavit, N. 및 Yerushalmi, L., 2004, June.스케일러블 록프리 스택알고리즘알고리즘과 아키텍처의 병렬성에 관한 제16회 연례 ACM 심포지엄의 속행 (p. 206-215).ACM.
  2. ^ 트리버, R.K., 1986년시스템 프로그래밍:병렬에 대처하다.International Business Machines Incorporated, Thomas J. Watson Research Center.
  3. ^ J.F. 그루트와 M.R. 무사비.통신 시스템의 모델링 및 분석.MIT 프레스 2014.
  4. ^ Jcip.net. (2016년)[2016년 5월 13일 이용 가능] http://jcip.net/listings/ConcurrentStack.java 。