Wait-свободная реализация очереди в JAVA

Question

Я пытался использовать уже написанный Wait свободной очереди на Алекс Коган и Эрез Петранк взяты из here, но столкнулись с проблемой. Я не могу понять, что именно нужно использовать в que() и deque() методов на странице 5 и 7 нить ID:

void enq(int value) { 
    long phase = maxPhase() + 1; // cf. Figure 3b 
    state.set(TID, new 
     OpDesc(phase, true, true, new Node(value, TID))); 
    help(phase); 
    help finish enq(); 
} 

И

int deq() throws EmptyException { 
    long phase = maxPhase() + 1; // cf. Figure 5a 
    state.set(TID, new OpDesc(phase, true, false, null)); 
    help(phase); 
    help finish deq(); 
    Node node = state.get(TID).node; 
    if (node == null) { 
     throw new EmptyException(); 
    } 
    return node.next.get().value; 
} 

Какой идентификатор потока должен использоваться?

Answer 1

В документе говорится, что TID является int в диапазоне [0, . . . , NUM THRDS−1]., поэтому он выглядит как присвоенный вручную номер.

Я не читал документ, поэтому я не знаю, существует ли строгое требование использовать только идентификатор, отвечающий этой спецификации. Существует метод long getId() на java.lang.Thread. См. Javadoc for Thread.getId():

Возвращает идентификатор этой темы. Идентификатор потока - это положительное длинное число, сгенерированное при создании этого потока. Идентификатор потока уникален и остается неизменным в течение всего срока его службы. Когда поток завершается, этот идентификатор потока может быть повторно использован.

Возможно, вы сможете использовать это вместо назначения TID.

Answer 2

Должен сказать, что я не убежден в том, что вы выбрали такую ​​реализацию нестандартной очереди, учитывая весь пакет параллелизма в JDK.

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

Во-вторых, измерение производительности в бумаге основано на динамически распределенной очереди; где фрагментация памяти и ошибка страницы будут основным ограничением производительности здесь. На самом деле, можно легко оценить длину очереди по нормальному случаю на peak arrival rate * peak lasting period и установить, чтобы очередь была статически распределена этой емкостью. Любой случай, который продюсер пытается поставить с полной очередью, можно просто приостановить (и вряд ли произойдет). Даже если такой сценарий случается, ограничение производительности парковки потоков обычно составляет 1 миллисекунду.

Если вы ищете задержку менее 1 миллисекунды в реальной производственной системе, Java, вероятно, не подходит для вас. Без правильного выравнивания памяти это очень сложно, если это возможно. Да LMAX сделал это с Disruptor, но IMHO только добавив некоторые пакеты управления памятью в JVM.

Итак, со всей практической перспективы вы должны либо использовать стандартные очереди в JDK, либо обратиться к Disruptor, либо использовать C/C++. Сама эта структура данных с недоказанной реализацией просто не является правильным выбором.