Операции
Единственные операции, которые меня интересуют:
- Добавление нового элемента в коллекцию;
- Обход в любом порядке;
- Завершение коллекции, предотвращение добавления дополнительных элементов добавляется.
Применяются дополнительные ограничения:
- Обход не должен препятствовать добавлению новых элементов во время его выполнения; скорее, добавленные элементы должны быть включены в обход.
- После завершения обхода мне нужно атомарно проверить простое условие на основе результата, вычисленного для пройденных элементов, и, возможно, закрыть коллекцию для будущих добавлений.
- Атомарно означает, что ни один элемент не должен быть потерян; любые добавления, происходящие после завершения обхода, но до принятия решения должны дождаться результата этого решения.
- Операции добавления синхронно и атомарно информируют вызывающую сторону, если это удалось;
- Алгоритм свертывания/накопления элементов всегда один и тот же, т. е. мне не нужно заботиться о помехах между обходами. Не ожидается, что более одного потока будут пытаться пройти обход одновременно, но если это произойдет, он должен просто дождаться завершения другого, если необходимо, но
- Обработка результата обхода может происходить асинхронно, если это необходимо, то есть достаточно, чтобы вызов обхода асинхронно отправлял вызов на выполнение, если он запускается как можно скорее.
- Добавление может произойти в спорной среде; в этом случае все потоки не должны синхронизироваться при обновлении одного и того же состояния (например, ссылка на связанный список). Точнее, оптимистичная атомарная проверка и установка ссылки на неизменяемый список приемлема по умолчанию, но неудача слишком много раз глобально для каждой коллекции должна привести к использованию по умолчанию чего-то с меньшей синхронизацией (проблема не в атомарном обновлении ссылки, а в необходимости создания нового объекта; выполните дополнительную операцию между чтением и записью).
- Коллекция должен самонастраиваться; уровень параллелизма заранее неизвестен.
Грубо говоря, я представляю себе массив связанных списков, в котором потоки работают в корзине на основе хэша идентификатора потока, где размер массива может увеличиваться в зависимости от некоторого эвристического обнаружения конфликтов. Возможна ли вообще такая адаптация?
Чтобы лучше проиллюстрировать то, о чем я думаю, приведу очень неправильный псевдокод:
Код: Выделить всё
boolean add(Elem elem) {
if (closed())
return false
if (this.state == TRAVERSAL) //obviously a race condition
return beCarefulIGuess()
//The collection starts with a single bucket, but that number may increase
// based on atomicFailureInc() step.
Bucket bucket = getBucket()
Link list = bucket.list
Link newList = new Link(elem, list)
int state;
while ((state = atomicTestAndSet(bucket, list, newList) != SUCCESS) {
if (state == CLOSED) //Obviously, a race condition here...
return false
if (state == TRAVERSAL)
//???
if (state == TRAVERSAL_END)
//Do not add new elements when the traversal happening now finished,
// but did not made the decision if further adding is allowed.
wait()
list = bucket.list
newList.tail = list
atomicFailureInc()
//If some magical threshold is exceeded, the collection should convert
// to more buckets, but not necessarily now.
}
return true
}
Этот вопрос не требует наличия готовой библиотеки. Просто самый разумный способ удовлетворить эти требования. Может быть научная статья (цитирование по данной ссылке разрешено). Я не ожидаю, что кто-то внедрит это только ради моей выгоды, но предоставление описания структуры данных с ее инвариантами направит меня на правильный путь.
