Вступление от переводчика. Позволю себе некоторое количество околофилософских замечаний перед десертом. В качестве же самого вкусного предлагаю Вашему вниманию попытку перевода-пересказа статьи "Writing a Generalized Concurrent Queue" by Herb Sutter. Первый номер Dr. Dobb's Journal попал мне в руки в далеком девяносто каком-то, наверное в девяносто третьем. Тогда, на буме проникновния IT в Россию этот журнал даже издавали у нас в переводе. Кроме прочего, в каждом номере бумажного издания публиковлась статья с подробным разбором алгоритма. Вот она, та, самая первая, прочитанная мной статья: "Fletcher's Checksum" by John Kodis. Ничего сверхъестественного, но это одна из тех вех, которая определила моё отношение к разработке эффективных алгоритмов. А именно: соображения целесообразности должны определять выбор используемого решения.
Две блокировки и неплохой результат.
В прошлом месяце я показал код свободной от блокировок (lock-free) очереди, пригодной к использованию с некоторыми ограничениями, а именно, для случая двух нитей: одного поставщика и одного потребителя. Полезно, но может оказатся не таким интересным, после того, как пик ликования минует. В этом месяце давайте решим проблему множетва поставщиков и множества потребителей в общем виде, на столько, на сколько это можно сделать параллельно. Код в этой статье будем проектировать исходя из четырёх простых идей.
Во-превых, мы будем использовать (эквивалент) двух блокировок: одной для управления поставщиками, другой, для управления потребителями. Кроме того, будем использовать атомарные переменные (C++0x atomic<>, Java/.NET volatile) напрямую, фактически реализуя цикл ожидания (spinlock), а не предоставляемые мютексы. Хотя это и означает, что алгоритм не полностью свободен от блокировок, тем не менее он позволяет множеству поставщиков и потребителей работать на столько одновременно, на сколько это возможно, минимизировав критический участок кода, обновляющий хвост и голову очереди.
Во-вторых, мы будем выделять память под элементы T в куче и работать с указателями на них, а не их значениями. Опытному разработчику параллельных алгоритмом подход может показаться ошибочным с первого взгляда, потому как процесс выделения памяти может привести к необходимости дополнителного перераспределения, а это, как известно, узкое горлышко современных менеджеров памяти. На самом деле, даже в системах имеющих проблемы с мастабируемостью выделения памяти, перевешивают преимущества масштабируемости и параллельной работы нитей потребителей, потому что мы можем вынести фактическое копирование значения T за пределы кода, обновляющего разделяемые данные.
Третье. Нам не хотелось бы делать поставщика ответственным за медленное удаление узлов, полученных потребителем с момента последнего его обращения, это отрицательно сказывается на производительности, добавляя гонку хвоста и головы и неоправданно задерживая освобождение узлов. Вместо этого ответственными за освобождение узлов сделаем конкретных потребителей, локализуя проблему.
В четвертых, мы хотим выполнить рекомендации, позволяющие двум переменным, не защищенные одним мьютексов и доступные двум нитям попасть в различные линии кэша, избежав ложного обмена (ping-ponging), ограничивающего производительность. В нашем случае, мы хотим довиться, что бы различные узлы (в частности первый и последний), первый и последний указатели списка, переменные producerLock и consumerLock, все они, попали в разные линии кэша.
Две блокировки и неплохой результат.
В прошлом месяце я показал код свободной от блокировок (lock-free) очереди, пригодной к использованию с некоторыми ограничениями, а именно, для случая двух нитей: одного поставщика и одного потребителя. Полезно, но может оказатся не таким интересным, после того, как пик ликования минует. В этом месяце давайте решим проблему множетва поставщиков и множества потребителей в общем виде, на столько, на сколько это можно сделать параллельно. Код в этой статье будем проектировать исходя из четырёх простых идей.
Во-превых, мы будем использовать (эквивалент) двух блокировок: одной для управления поставщиками, другой, для управления потребителями. Кроме того, будем использовать атомарные переменные (C++0x atomic<>, Java/.NET volatile) напрямую, фактически реализуя цикл ожидания (spinlock), а не предоставляемые мютексы. Хотя это и означает, что алгоритм не полностью свободен от блокировок, тем не менее он позволяет множеству поставщиков и потребителей работать на столько одновременно, на сколько это возможно, минимизировав критический участок кода, обновляющий хвост и голову очереди.
Во-вторых, мы будем выделять память под элементы T в куче и работать с указателями на них, а не их значениями. Опытному разработчику параллельных алгоритмом подход может показаться ошибочным с первого взгляда, потому как процесс выделения памяти может привести к необходимости дополнителного перераспределения, а это, как известно, узкое горлышко современных менеджеров памяти. На самом деле, даже в системах имеющих проблемы с мастабируемостью выделения памяти, перевешивают преимущества масштабируемости и параллельной работы нитей потребителей, потому что мы можем вынести фактическое копирование значения T за пределы кода, обновляющего разделяемые данные.
Третье. Нам не хотелось бы делать поставщика ответственным за медленное удаление узлов, полученных потребителем с момента последнего его обращения, это отрицательно сказывается на производительности, добавляя гонку хвоста и головы и неоправданно задерживая освобождение узлов. Вместо этого ответственными за освобождение узлов сделаем конкретных потребителей, локализуя проблему.
В четвертых, мы хотим выполнить рекомендации, позволяющие двум переменным, не защищенные одним мьютексов и доступные двум нитям попасть в различные линии кэша, избежав ложного обмена (ping-ponging), ограничивающего производительность. В нашем случае, мы хотим довиться, что бы различные узлы (в частности первый и последний), первый и последний указатели списка, переменные producerLock и consumerLock, все они, попали в разные линии кэша.
Комментариев нет:
Отправить комментарий