그래서 잠금 - 자유은 일부 스레드가 굶기지 만 전체 시스템이 진행된다는 보장이있는 경우입니다. 따라서 CAS 기반의 구현은 이러한 보장을 제공합니다.lock-free가 아닌 obstrap-free 알고리즘의 예는 무엇입니까?
obstruction-freedom은 다른 모든 스레드가 일시 중단 된 경우 하나의 스레드가 완료되는 것이 보장되는 경우입니다.
자물쇠가없는 obstrap-free 알고리즘의 간단한 예를 들려 줄 수 있습니까?
감사합니다.
초창기 저자 Herlihy가 012 년 5 월 1 일 전에 wait-freedom이라는 개념을 도입했을 때이 전체 사업을 시작한 문서를 읽는 것이 좋습니다.
잠금 자유와 방해 금지 사이의 핵심적인 차이점은 두 개 이상의 스레드가 실행 중일 때 진행이 보장되지 않는다는 것입니다 (단 하나만 실행중인 경우).
종이의 고기는 원하는대로 제공합니다. 잠금 해제 상태는 아니지만 자물쇠가없는 누출 방지 장치의 예입니다.
더 간단하게하기 위해 배열 기반 스택에 대해서도 같은 방식으로 작동하며 장애물이 없지만 잠글 수 없습니다.
스택의 0 개 이상의 요소가 배열의 시작 부분에 연속적으로 저장되고 나머지 모든 위치에 "null"요소가 뒤에 오는 스택을 상상해보십시오. 스택의 각 요소는 터플로 저장됩니다. (val, seq)입니다. 여기서 val은 사용자가 제공 한 값이고 seq은 알고리즘의 핵심 인 시퀀스 번호입니다 (또한 ABA 문제 은 피할 수 있음).
A[k] 위치에서) 제
널 요소 앞에 바로 (위치
A[k-1])을 소자 밀어. CAS를 사용하여
A[k-1]의 시퀀스 번호를 증가시키고 (요소는 변경되지 않음) 시도하고 성공할 경우
A[k] 위치의 null 요소 값을 동시에 바꾸고 시퀀스 번호를 증가시킵니다. 두 CAS 중 하나가 실패하면 다시 시도하십시오.
pop 알고리즘은 비슷하지만 반대 순서로 요소를 처리합니다 (주 요소의 시퀀스 번호를 증가시킨 다음 마지막 요소를 null로 만들고 시퀀스 번호를 증가 시킴).
이 구조의 정확성은 위의 종이에서 자세히 설명되어 있지만 기본적으로 성공적으로 증가 시키면 그 순간에도 여전히 목록의 마지막 요소이므로 모든 동시 레이싱 초기 CAS가 실패하게하여 "다음 번에 얻을 수있는"푸시 조작. 두 번째 CAS가 성공하면 요소를 성공적으로 추가했습니다.
동시 푸시 및 팝 조작으로 서로가 무한정 실패 할 수 있습니다. 밀어 넣기 스레드는 A[k-1]을 증가시키고 팝업은 A[k]을 증분 한 다음 다른 쪽의 증가분을 보면서 실패합니다. 린스하고 반복하십시오. 이것은 라이브 록의 예입니다.
하나의 스레드 만 실행중인 경우 문제가 사라지는 점에 유의하십시오. 이는 방해가없는 자유의 핵심 관찰입니다.
1
는 ... 그것은 또한 디큐의 전체 버전에 "랩 어라운드"문제를 피할 수 있지만, 나는 그것이 스택의 경우에서 일어나는 생각하지 않습니다.을 간단한 예제로 제공 할 수 있는지 확실하지 않습니다. 단순한 작업은 일반적으로 대기 시간이 없으며 (예 : RCU의 리더 측) 잠금이 필요하지 않으며 (예 : 라이브 록을 사용할 수없는 CAS 재시도 루프) 방해가 없어도됩니다.
성능이 좋지 않거나 경합이 낮고 실용적인 경우에도 중역에서 대기하는 작성자가 전체 대기열을 차단할 수있는 잠금없는 다중 기록기 다중 판독기 대기열을 분석하려면 Lock-free Progress Guarantees을 참조하십시오.
나는 스레드가 다른 스레드에 의해 부분적으로 완성 작업을 취소 할 수있는 경우 장애물이없는 잠금 무료하지 않고있는 것은에만 가능합니다 생각합니다. (따라서 다시 깨울 때 자체 작업을 취소하는 경우를 처리합니다.) 나는 틀릴 수도있다. 아마도 알 고가 비 블로킹 (non-blocking)은 가능하지만 락 프리 (lock-free)가 아닌 다른 방법이있을 수 있습니다.
이것은 내가 간단한을 고려할 것 아니지만, https://en.wikipedia.org/wiki/Non-blocking_algorithm는 말한다 :
어떤 장애물이없는 알고리즘은 데이터 구조에 "일관성 마커"한 쌍을 사용합니다. 데이터 구조를 읽는 프로세스는 먼저 하나의 일관성 마커를 읽은 다음 관련 데이터를 내부 버퍼로 읽어 들인 다음 다른 마커를 읽고 마커를 비교합니다. 두 마커가 동일하면 데이터가 일치합니다. 데이터 구조를 업데이트하는 다른 프로세스에 의해 읽기가 중단되면 마커가 동일하지 않을 수 있습니다. 이 경우, 프로세스는 내부 버퍼의 데이터를 버리고 다시 시도합니다.
경합에 대한 백 오프 알고리즘이 좋지 않으면이 문제가 생길 수 있습니다. 너무 많은 스레드가 그것에 망치로 쳐들어 서, 그들은 무엇이든하기 전에 끊임없이 서로를 취소 할 수 있습니다. 이것이 잠금이 풀리지 않는 이유입니다.
각 알고리즘마다 잠금이 필요없는 알고리즘이 전부입니다. (https://en.wikipedia.org/wiki/Non-blocking_algorithm). 예를 들어 방해받지 않는 원자 CAS를 사용하는 잠금없는 대기열에 대한 분석을 참조하십시오 (실제로는 매우 좋고 낮은 경쟁으로 잘 조정되지만). https://stackoverflow.com/questions/45907210/lock-free-progress-guarantees. –