Данные «Wait-free» в Haskell

Мне повезло, что реализация GHC TVar s равна lock-free, но не wait-free. Существуют ли какие-либо реализации, которые не доступны (например, пакет Hackage)?Данные «Wait-free» в Haskell

источник

2012-04-20 Clinton

На странице Википедии, кажется, что ждать-свобода является свойством алгоритма, а не структуры данных. –

@ Daniel: Возможно, это неправильное использование термина. Я имею в виду, что, обертывая все ваши данные в 'TVar', любой алгоритм блокируется. Я хотел бы знать, существует ли тип данных, который делает любой алгоритм без ожидания. – Clinton

Ваш вопрос: «Есть ли какие-либо реализации без ожидания?» немного неполна. STM (и, следовательно, TVar) довольно сложна и имеет встроенную поддержку в компилятор - вы не можете правильно ее построить с помощью примитивов Haskell.

Если вы ищете какой-либо контейнер данных, который допускает мутацию и может быть неблокирующим, то вы хотите, чтобы IORef s или MVar s (но они могут блокироваться, если значение не доступно).

источник

2012-04-20 03:01:12

Вы _can_ реализуете STM самостоятельно. В компилятор его не нужно жестко подключать. (Хотя, вероятно, это более эффективно.) См. Вопрос № 15 «The Monad Reader» для исходного кода. – MathematicalOrchid

'IORef' не может быть пустым и не будет блокироваться, как я понимаю. –

@ У Math Haskell нет никаких незакрепленных/CAS примитивов для истинного ATM afaik, поэтому я с удовольствием увижу MR, когда у меня будет время. –

Wait-freedom - термин от распределенных вычислений. Алгоритм без ожидания, если поток (или распределенный узел) способен корректно завершить работу, даже если все входные данные из других потоков задерживаются/теряются в любое время.

Если вам небезразлична последовательность, то вы не можете гарантировать свободу ожидания (при условии, что вы всегда хотите закончить правильно, то есть гарантировать доступность). Это следует из теоремы CAP [1], так как свобода ожидания по существу подразумевает допустимость разделов.

[1] http://en.wikipedia.org/wiki/CAP_theorem

источник

2012-04-20 07:44:23 Peter

Звучит как смешение терминов для меня. Как правило, «без ожидания» просто означает, что все потоки продвигаются вперед. Например (в C++, извините), функция 'inc' не будет ждать' std :: atomic i; void inc() {i ++; } 'потому что каждый поток, который входит, никогда не перестает развиваться. Контрастируйте это с помощью алгоритма блокировки (например, стека блокировки), который не требует блокировок и является атомарным, но только прогрессирует по одному потоку за раз (хотя из-за его высокой степени детализации быстрее в ситуациях с высокой нагрузкой) , – GManNickG

@GManNickG: Если вы просто рассматриваете 'inc()' как атомную операцию с нулевым временем, я согласен, 'inc()' будет без ожидания. Однако, если вы посмотрите, как фактически реализована атомарность 'inc()', она должна либо влечь за собой некоторую блокировку, либо некоторую форму «повторной попытки», чтобы гарантировать согласованность, поскольку существует вероятность того, что 2 потока прочитают одно и то же значение одновременно один из них пишет.Поэтому, если вы посмотрите на этот уровень, 'inc()' не будет ждать, потому что один из потоков должен перечитать значение перед тем, как идти вперед. – Peter

Справедливо, я сделал некоторые предположения, не указав. Но есть атомарность аппаратного уровня, которая на программном уровне блокируется и не требует отклика. – GManNickG

Данные «Wait-free» в Haskell

ответ

Смежные вопросы