Здравствуйте, vdimas, Вы писали:
V>Странно рассуждаешь. ))
V>В Spin-wait не происходит ничего, кроме удержания ресурсов процессора, а тут в очередь достоверно ставятся элементы, пока крутится цикл, просто они ставятся в других потоках. Т.е., блокировки очереди нет, именно поэтому lock-free.
Классический spin-wait — активное ожидание ресурса: в цикле проверяешь, когда же тебе наконец-то что-то станет доступно.
while ((local_i = atomic_load(&i)) == 0) {
/* do nothing - just keep checking over and over */
}
Посмотри внимательнее:
do {
node.Next = head.Next;
} while (!CAS(ref head.Next, node.Next, node));
Здесь CAS — это просто оптимизация того, насколько времени блокируется голова стека. Сама блокировка потока исполнения и блокировка элемента никуда не исчезает, просто хорошо оптимизирована за счёт реализации "в железе". Искренее считаю что это реализуемо и без аппаратного CAS (допустим префикс lock не работает и нет способа выставить сигнал lock на шину) — сами значения в памяти могут быть соответствующим "сигналом". Алгоритм Деккера и Решение Петтерсона вроде бы именно про это.
V>И если конкурирующий поток уйдёт в спячку через вытеснение, то очередь не останется надолго заблокированной, как оно было бы при защите обычной очереди мьютексом, если бы перед вытеснением поток завладел бы ресурсом.
Ты как будто про мьютекс пишешь: это его можно захватить, это он может принадлежать какому-то потоку после чего-нибудь типа WaitForSingleObject(). Многие вот так и попадают в эту ловушку мышления, рассуждая в парадигме "захватить ресурс". Однако задача-то в другом: выполнить участок кода атомарно, какое-то действие сделать атомарно. Если ты отбрасываешь парадигму "ресурс принадлежит потоку", стремясь только к тому чтобы выполнять отдельные действия атомарно (что есть изначальная цель), то такие алгоритмы получаются сами собой.
V>Зачастую это плохая практика.
V>При нужной расстановке приоритетов потоков выгодней уходить в спячку, чем крутить 10 GOTO 10.
Вот нифига подобного, не согласен: почти во всех гайдлайнах, и Best practсies говорится о том, что блокировка должна выставляться на минимально возможное время. Это то самое время, чтобы что-то атомарно сделать — чтоб данные консистентными оставались. Если строго следовать этим рекомендациям, то большая часть блокировок будет на время порядка десятка тактов процессора — именно столько действительно требуется чтобы обновить несколько участков памяти.
V>Например, в твоём цикле указан код писателя.
V>А что делать читателю в отсутствии данных?
В моём коде читателю при отсутствии данных не надо делать ничего: там речь про OnScreenDisplay — пока я не закончу формирование данных, показывать нечего — или предыдущее значение, или ничего. Мусор показывать бессмысленно.
Речь ведь про этот код, правильно?
try
{
LockMemory();
p_osdSlot.UpdateOSDslotText(p_newText);
}
finally
{
UnlockMemory();
}
Читатель, увидев m_rtssMemory->dwBusy, может идти дальше ничего не обновляя на экране — данные ещё не готовы.
V>Если же ядра унутре однопоточные, то PAUSE не делает аж ничего, это аналог NOP.
ВСЕ(!) ядра у современных интеловских процессоров МНОГОпоточные. Это проистекает из того, что все современные интеловские (и АМД'шные) процессоры суперскалярные — они имеют несколько конвейров (pipelines), и исполняют инструкции параллельно.
А кроме того, современные процессоры имеют блок предсказания ветвлений и спекулятивное исполнение — параллельно выполняют инструкции, которые теоретически могут оказаться следующими в потоке.
Тащемта это официальная рекомендация от Intel:
| | 1 |
| |
Use the PAUSE instruction in all spin wait loops. The PAUSE instruction de-pipelines the spin-wait loop to
prevent it from consuming execution resources excessively and consuming power needlessly.
When executing a spin-wait loop, the processor can suffer a severe performance penalty when exiting
the loop because it detects a possible memory order violation and flushes the core processor's pipeline.
The PAUSE instruction provides a hint to the processor that the code sequence is a spin-wait loop. The
processor uses this hint to avoid the memory order violation and prevent the pipeline flush. However, you
should try to keep spin-wait loops with PAUSE short. |
| | |
| | 2 |
| |
Branch optimizations have a significant impact on performance. By understanding the flow of branches
and improving their predictability, you can increase the speed of code significantly.
Optimizations that help branch prediction are:
• Keep code and data on separate pages. This is very important; see Section 3.6, “Optimizing Memory
Accesses,” for more information.
• Eliminate branches whenever possible.
• Arrange code to be consistent with the static branch prediction algorithm.
• Use the PAUSE instruction in spin-wait loops.
• Inline functions and pair up calls and returns.
• Unroll as necessary so that repeatedly-executed loops have sixteen or fewer iterations (unless this
causes an excessive code size increase).
• Separate branches so that they occur no more frequently than every three micro-ops where possible. |
| | |
| | 3 |
| |
The frequency and duration that a thread needs to synchronize with other threads depends application
characteristics. When a synchronization loop needs very fast response, applications may use a spin-wait
loop.
A spin-wait loop is typically used when one thread needs to wait a short amount of time for another
thread to reach a point of synchronization. A spin-wait loop consists of a loop that compares a synchronization variable with some pre-defined value. See Example 8-4(a).
On a modern microprocessor with a superscalar speculative execution engine, a loop like this results in
the issue of multiple simultaneous read requests from the spinning thread. These requests usually
execute out-of-order with each read request being allocated a buffer resource. On detection of a write by
a worker thread to a load that is in progress, the processor must guarantee no violations of memory
order occur. The necessity of maintaining the order of outstanding memory operations inevitably costs
the processor a severe penalty that impacts all threads.
This penalty occurs on the Pentium M processor, the Intel Core Solo and Intel Core Duo processors.
However, the penalty on these processors is small compared with penalties suffered on the Pentium 4
and Intel Xeon processors. There the performance penalty for exiting the loop is about 25 times more
severe.
On a processor supporting HT Technology, spin-wait loops can consume a significant portion of the
execution bandwidth of the processor. One logical processor executing a spin-wait loop can severely
impact the performance of the other logical processor. |
| | |
Это из Intel® 64 and IA-32 Architectures Optimization Reference Manual. Советую туда заглянуть — там много любопытного написано.
Да, я тут "многопоточность ядер" понимаю не как в Pentium-4, не про Hyper-Threading, не про SMT. Тем не менее исполнительных блоков у современных ядер процессоров более одного — в этом плане они "многопоточные".
