로드링크/스토어 조건부

Load-link/store-conditional

컴퓨터 과학에서 LL/SC(load-linked/store-conditional[1][2])는 동기화를 달성하기 위해 멀티스레딩에서 사용되는 명령어 쌍입니다.Load-link는 메모리 위치의 현재 값을 반환합니다.단, 같은 메모리 위치에 대한 후속 스토어 조건에서는 로드 링크 이후 해당 위치에 대한 업데이트가 발생하지 않은 경우에만 새로운 값이 저장됩니다.이것에 의해, 록 프리 아토믹 읽기-수정-쓰기 조작이 실장됩니다.

"로드 링크"는 로드 링크,[citation needed] 로드 [2]예약 및 로드 [citation needed]잠금이라고도 합니다.

LL/SC는 원래 Lawrence Livermore National Laboratory의 S-1 AAP[1] 멀티프로세서를 위해[citation needed] Jensen, Hagensen 및 Bringon에 의해 제안되었습니다.

LL/SC와 비교 및 스왑 비교

업데이트가 발생한 경우 load-link에 의해 판독된 값이 복원된 경우에도 store-conditional은 실패합니다.따라서 LL/SC 쌍은 읽기보다 강력하며, 그 후 Compare-and-Swap(CAS; 비교 및 스왑)이 계속됩니다.CAS는 오래된 값이 복원된 경우 업데이트를 검출하지 않습니다(ABA 문제 참조).

LL/SC의 실제 실장은 문제의 메모리 위치에 대한 동시 업데이트가 없는 경우에도 항상 성공하는 것은 아닙니다.컨텍스트 스위치, 다른 로드 링크, 심지어 (많은 플랫폼에서) 다른 로드 또는 스토어 동작 등2개의 동작 사이에 특별한 이벤트가 발생하면 스토어 조건부 동작이 충동적으로 실패합니다.메모리 버스를 통해 브로드캐스트되는 업데이트가 있는 경우 이전 구현은 실패합니다.이것은 많은 이론적인 LL/SC 알고리즘을 [3]깨기 때문에 연구자들에 의해 약한 LL/SC라고 불립니다.약점은 상대적인 것으로, 일부 알고리즘에서는 약한 실장을 사용할 수 있습니다.

LL/SC는 CAS보다 에뮬레이션이 어렵습니다.또한 코드 통과 싱글스텝 등 쌍으로 구성된 LL/SC 명령 간에 코드 실행을 중지하면 진행이 방해되어 디버깅이 [4]까다로워질 수 있습니다.

단, 어느 한쪽의 프리미티브가 다른 쪽, O(1) 및 대기 없는 방법으로 구현될 [5]수 있다는 점에서 LL/SC는 CAS와 동등합니다.

실장

LL/SC 명령은 다음에서 지원됩니다.

CPU에[which?] 따라서는, 액세스 전용의 주소를 기입 모드로 설정할 수 있습니다.

일반적으로 CPU는 캐시 라인 또는 기타 세분화 방식으로 로드 링크된 주소를 추적하여 캐시 라인의 모든 부분(다른 코어의 스토어 조건부 또는 일반 스토어)에 대한 수정이 스토어 조건부 장애를 일으키기에 충분하도록 합니다.

이들 플랫폼은 모두 약한 LL/SC를 제공합니다[clarification needed].파워PC 실장에서는 LL/SC 쌍이 로드를 랩할 수 있으며 다른 캐시 라인에 저장될 수도 있습니다(단, 이 접근법은 잘못된 캐시 라인 공유에 취약합니다).이를 통해 예를 들어 임의의 카운터 재사용을 통해 객체 그래프가 변경되었을 때 잠금 없는 참조 카운트를 구현할 수 있습니다(그렇지 않으면 DCAS가 이중 비교 및 스왑되어야 합니다).RISC-V는 제한된 길이의 LL/SC 시퀀스에 대해 궁극적인 진척을 보증합니다.

일부 ARM 실장에서는 플랫폼에 의존하는 블록이 8바이트에서 2048바이트 범위로 정의되어 있습니다.또한 LL과 SC 사이에 통상적인 메모리액세스가 있는 경우 특정 블록에서의 LL/SC 시행은 실패합니다.주소 공간 전체에 변경이 있을 경우 다른 ARM 구현이 실패합니다.전자의 실장이 가장 강력하고 실용적이다.

LL/SC는 로드 스토어 아키텍처를 설계할 때 CAS에 비해2가지 장점이 있습니다.설계 이념(및 파이프라인 아키텍처)에서 요구하는 대로 읽기와 쓰기는 별개의 명령입니다.또한 두 명령 모두 2개의 레지스터(주소와 값)만을 사용하여 실행할 수 있기 때문에 일반적인 2-oper 및 ISA에 자연스럽게 적합합니다.한편 CAS에서는 3개의 레지스터(주소, 오래된 값, 새로운 값)와 판독값과 기입값의 의존관계가 필요합니다.x86은 CISC 아키텍처이기 때문에 이 제약은 없습니다.단, 최신 칩은 CAS 명령어를 내부적으로 별도의 LL/SC 마이크로 오퍼레이션으로 변환하는 것이 좋습니다.

내선번호

하드웨어 LL/SC 구현에서는 일반적으로 LL/SC [6]쌍의 네스트는 허용되지 않습니다.네스트 LL/SC 기구는 MCAS 프리미티브(단어를 [7]분산시킬 수 있는 복수워드 CAS)를 제공하기 위해 사용할 수 있다.2013년에는 트레버 브라운, 페이스 엘렌, 에릭 Ruppert 소프트웨어에;[8]그들은 그것(실제로 색 나무)하나를 보인 종목 동시 2진 탐색 트리의 구현을 위해서 약간은 자바 개발 키트CAS-based 스킵 목록 implemen을 사용해 오고 있는 자동 코드 생성에 의존하는 다중 어드레스 LL/SC 연장(그들은 LLX/SCX라고 부른다)을 추진하였다.tation.[9]

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b "S-1 project". Stanford Computer Science wiki. 2018-11-30.
  2. ^ a b c Andrew Waterman; Krste Asanović, eds. (2017-05-07). "7.2 Load-Reserved/Store-Conditional Instructions". The RISC-V Instruction Set Manual, Volume 1: User-Level ISA, Version 2.2 (PDF).
  3. ^ Beckmann, Nathan. "Synchronization" (PDF). 15-740: Computer Architecture, Fall 2018. Carnegie Mellon University. Retrieved 23 April 2021.
  4. ^ Keno Fischer (2020-05-02). "Julia 1.5 Feature Preview: Time Traveling (Linux) Bug Reporting". Retrieved 2020-05-14.
  5. ^ James H. Anderson; Mark Moir (1995). "Universal constructions for multi-object operations". PODC '95 Proceedings of the fourteenth annual ACM symposium on Principles of distributed computing. ACM. pp. 184–193. doi:10.1145/224964.224985. ISBN 0-89791-710-3. 특히 표 1, 그림 1과 그림 2 및 섹션 2를 참조하십시오.
  6. ^ James R. Larus; Ravi Rajwar (2007). Transactional Memory. Morgan & Claypool. p. 55. ISBN 978-1-59829-124-7.
  7. ^ Keir Fraser (February 2004). Practical lock-freedom (PDF) (Technical report). University of Cambridge Computer Laboratory. p. 20. UCAM-CL-TR-579.
  8. ^ Brown, Trevor; Ellen, Faith; Ruppert, Eric (2013). "Pragmatic primitives for non-blocking data structures" (PDF). PODC '13 Proceedings of the 2013 ACM symposium on Principles of distributed computing. ACM. pp. 13–22. doi:10.1145/2484239.2484273. ISBN 978-1-4503-2065-8. 슬라이드도 참조
  9. ^ Trevor Brown; Faith Ellen; Eric Ruppert (2014). "A general technique for non-blocking trees" (PDF). PPoPP '14 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. ACM. pp. 329–342. doi:10.1145/2555243.2555267. ISBN 978-1-4503-2656-8.