비어 있지 않은 경우 잠금 대기열에 대기열에 넣기

Question

http://www.boyet.com/articles/LockfreeQueue.html을 기반으로 비교 및 ​​교체를 사용하여 C에서 잠금 해제 대기열을 구현했습니다.

잘 작동하지만이 큐를 구현 한 락 프리 건너 뛰기 목록에 통합하려고합니다. 건너 뛰기 목록을 우선 순위 큐로 사용하고 있으며 우선 순위 충돌이있을 때 각 노드 내부의 잠금없는 큐를 사용하여 여러 값을 저장하려고합니다. 그러나 노드가 건너 뛰기 목록에서 관리되는 우선 순위 충돌을 감지 할 때 대기열이 비어 있지 않은 경우에만 항목을 대기열에 추가 할 수 있어야합니다.

대기열의 잠금 해제로 인해 실제로이 작업을 수행하는 방법이 확실하지 않습니다.

그래서 기본적으로 어떻게 원자적인 enqueue_if_not_empty 연산을 작성하겠습니까?

Answer 1

EDIT : 눈치 챘을 때, 필자는 꽤 반대되는 의미론을 지닌 함수를 썼다. 즉 빈 큐에 큐잉 만했다. 나는 그것을 반영하기 위해 이름을 고치고 누군가가 관심을 가지기 때문에 그대로두기로 결정했다. 그래서,이 질문에 대한 정답이 아니라 다른 이유 : 아래

---

참조 된 논문에서 큐 구현에 EnqueueIfEmpty()을 추가하는 시도를 발견하지 않는 한, 제발 downvote하지 않습니다. 나는 그것이 작동하는지 또는 심지어 컴파일 하는지를 검증하지 않았다. 기본 아이디어는 머리 바로 뒤에 새 노드를 삽입하고 머리글의 다음 문자가 null 인 경우 (빈 큐의 필수 조건 인 경우) 꼬리가 아닌 새 노드를 삽입하는 것입니다. 나는 꼬리와 동등한 머리에 대한 추가 검사를 남겼는데, 아마도 제거 될 수 있습니다.

public bool EnqueueIfEmpty(T item) { 
    // Return immediately if the queue is not empty. 
    // Possibly the first condition is redundant. 
    if (head!=tail || head.Next!=null) 
     return false; 

    SingleLinkNode<T> oldHead = null; 

    // create and initialize the new node 
    SingleLinkNode<T> node = new SingleLinkNode<T>(); 
    node.Item = item; 

    // loop until we have managed to update the tail's Next link 
    // to point to our new node 
    bool Succeeded = false; 
    while (head==tail && !Succeeded) { 

    // save the current value of the head 
    oldHead = head;   

    // providing that the tail still equals to head... 
    if (tail == oldHead) { 

     // ...and its Next field is null... 
     if (oldhead.Next == null) { 

     // ...try inserting new node right after the head. 
     // Do not insert at the tail, because that might succeed 
     // with a non-empty queue as well. 
     Succeeded = SyncMethods.CAS<SingleLinkNode<T>>(ref head.Next, null, node); 
     } 

     // if the head's Next field was non-null, another thread is 
     // in the middle of enqueuing a new node, so the queue becomes non-empty 
     else { 
     return false; 
     } 
    } 
    } 

    if (Succeeded) { 
    // try and update the tail field to point to our node; don't 
    // worry if we can't, another thread will update it for us on 
    // the next call to Enqueue() 
    SyncMethods.CAS<SingleLinkNode<T>>(ref tail, oldHead, node); 
    } 
    return Succeeded; 
} 

Answer 2

음, 인큐-IF-비어 있지 않음은 비교적 간단 것으로 보인다, 그러나 제한없이 : 그 꼬리에 삽입 완료 후, 그래서 다른 스레드가 동시에, 큐에서 이전의 모든 항목을 제거 할 수는 새 항목이 대기열의 첫 번째 항목 일 수 있습니다. 원자 비교 - 스왑 연산은 다른 필드 (변경 대기열에 넣기 tail.Next)에서 수행되기 때문에 대기열 제거는 head으로 진행됩니다.이 기능은 물론 Dequeue()에서도 복잡성이 더 커집니다. 통상의 방법에 Enqueue()

다음 변경 충분 :
1) 함수의 시작에서, 널되는 head.Next 확인하고, 만약 그렇다면, 대기열이 비어로 즉시 반환한다.
2) 삽입이 성공하기 전에 처음 비어 있지 않은 큐가 비게 될 경우 대기열에 넣기 시도가 중지되어야하는 경우 루프 조건에 head.Next!=null을 추가하십시오. 위와 같은 상황을 막을 수는 없지만 (공허함과 노드 삽입 사이의 시간차가 있기 때문에), 발생 가능성은 줄어 듭니다.
3) 함수가 끝날 때 새 노드가 성공적으로 대기열에 추가되면 꼬리를 앞 당깁니다 (Enqueue-If-Empty 응답 에서처럼).