Я изучаю алгоритмы без блокировки (en-, de) очереди Майкла и Скотта . Проблема в том, что я не могу объяснить / понять (как и в статье, кроме комментариев в самом коде) пару строк.
Ставить:
enqueue(Q: pointer to queue_t, value: data type)
E1: node = new_node() // Allocate a new node from the free list
E2: node->value = value // Copy enqueued value into node
E3: node->next.ptr = NULL // Set next pointer of node to NULL
E4: loop // Keep trying until Enqueue is done
E5: tail = Q->Tail // Read Tail.ptr and Tail.count together
E6: next = tail.ptr->next // Read next ptr and count fields together
E7: if tail == Q->Tail // Are tail and next consistent?
// Was Tail pointing to the last node?
E8: if next.ptr == NULL
// Try to link node at the end of the linked list
E9: if CAS(&tail.ptr->next, next, <node, next.count+1>)
E10: break // Enqueue is done. Exit loop
E11: endif
E12: else // Tail was not pointing to the last node
// Try to swing Tail to the next node
E13: CAS(&Q->Tail, tail, <next.ptr, tail.count+1>)
E14: endif
E15: endif
E16: endloop
// Enqueue is done. Try to swing Tail to the inserted node
E17: CAS(&Q->Tail, tail, <node, tail.count+1>)
Зачем нужен E7? От этого зависит правильность? Или это просто оптимизация? Это if может завершиться ошибкой, если другой поток успешно выполнил E17 или D10 ниже (и изменил Q-> Tail), в то время как первый поток выполнил E5, но еще не E7. Но что, если E17 выполняется сразу после того, как первый поток выполняет E7?
edit : Доказывает ли это последнее предложение, что E7 не может быть больше, чем оптимизация? Моя интуиция заключается в том, что это делает , так как я привожу сценарий, в котором «очевидно», оператор if примет неверное решение, хотя алгоритм все равно должен работать правильно. Но тогда мы могли бы заменить условие if случайным условием, не влияя на правильность. Есть ли дыра в этом аргументе?
Dequeue:
dequeue(Q: pointer to queue_t, pvalue: pointer to data type): boolean
D1: loop // Keep trying until Dequeue is done
D2: head = Q->Head // Read Head
D3: tail = Q->Tail // Read Tail
D4: next = head.ptr->next // Read Head.ptr->next
D5: if head == Q->Head // Are head, tail, and next consistent?
D6: if head.ptr == tail.ptr // Is queue empty or Tail falling behind?
D7: if next.ptr == NULL // Is queue empty?
D8: return FALSE // Queue is empty, couldn't dequeue
D9: endif
// Tail is falling behind. Try to advance it
D10: CAS(&Q->Tail, tail, <next.ptr, tail.count+1>)
D11: else // No need to deal with Tail
// Read value before CAS
// Otherwise, another dequeue might free the next node
D12: *pvalue = next.ptr->value
// Try to swing Head to the next node
D13: if CAS(&Q->Head, head, <next.ptr, head.count+1>)
D14: break // Dequeue is done. Exit loop
D15: endif
D16: endif
D17: endif
D18: endloop
D19: free(head.ptr) // It is safe now to free the old node
D20: return TRUE // Queue was not empty, dequeue succeeded
Опять же, зачем нужен D5? Правильность или оптимизация? Я не уверен, какую «согласованность» дают эти тесты, поскольку кажется, что они могут стать непоследовательными сразу после успешного выполнения if.
Это похоже на стандартную технику. Может кто-нибудь объяснить мотивы этого? Мне кажется, что намерение состоит в том, чтобы избежать (дорогостоящего) CAS в тех немногих случаях, можно заметить, что он определенно потерпит неудачу, но за счет всегда делать дополнительное чтение, которое не должно быть слишком большим. дешевле самого себя (например, в Java, Q->Tail потребовалось бы быть энергозависимым, поэтому мы бы знали, что мы не просто читаем копию, кэшированную в регистре, но читаем реальную вещь, что будет переводиться при добавлении чтения к забору какой-то), так что я не уверен, что на самом деле здесь происходит ... спасибо.
edit Это было перенесено на Java, точнее в ConcurrentLinkedQueue , например. E7 - это строка 194, а D5 - это строка 212.