Параллельные структуры Данных на основе блокировок
Прежде чем оставить тему блокировок, мы сначала опишем, как использовать блокировки в некоторых распространенных структурах данных. Добавление блокировок в структуру данных, чтобы сделать ее пригодной для использования потоками, делает структуру потокобезопасной (threadsafe). Конечно, то, как именно добавляются такие блокировки, определяет как правильность, так и производительность структуры данных. И, таким образом, наша задача:
ЗАДАЧА: КАК ДОБАВИТЬ БЛОКИРОВКИ В СТРУКТУРЫ ДАННЫХ
Когда задана определенная структура данных, как мы должны добавлять к ней блокировки, чтобы она работала правильно? Кроме того, как нам добавить блокировки таким образом, чтобы структура данных обеспечивала высокую производительность, позволяя многим потокам получать доступ к структуре одновременно, т.е. конкурентно?
Конечно, нам будет трудно охватить все структуры данных или все методы добавления параллелизма, поскольку эта тема изучается годами, и (буквально) об этом опубликованы тысячи исследовательских работ. Таким образом, мы надеемся предоставить достаточное представление о требуемом типе мышления и направить вас к некоторым хорошим источникам материала для дальнейшего самостоятельного изучения. Мы сочли опрос Мойра и Шавита отличным источником информации [MS04].
29.1 Параллельные счетчики
Одной из простейших структур данных является счетчик. Это широко используемая структура с простым интерфейсом. Мы определяем простой неконкурентный счетчик на рисунке 29.1.
Простой, но не масштабируемый
Как вы можете видеть, несинхронизированный счетчик представляет собой тривиальную структуру данных, для реализации которой требуется небольшое количество кода. Теперь у нас есть следующая задача: как мы можем сделать этот код потокобезопасным? На рисунке 29.2 показано, как мы это делаем.
Этот параллельный счетчик прост и работает правильно. Фактически, он следует шаблону проектирования, общему для самых простых и базовых параллельных структур данных: он просто добавляет одну блокировку, которая устанавливается при вызове подпрограммы, которая манипулирует структурой данных, и освобождается при возвращении из вызова. Таким образом, это похоже на структуру данных, построенную с помощью мониторов [BH 73], где блокировки автоматически устанавливаются и снимаются при вызове и возврате методов объекта.
На этом этапе у вас есть работающая параллельная структура данных. Проблема, с которой вы можете столкнуться, заключается в производительности. Если ваша структура данных слишком медленная, вам придется сделать больше, чем просто добавить одну блокировку; таким образом, такая оптимизация, при необходимости, является темой остальной части главы. Обратите внимание, что если структура данных не слишком медленная, все готово! Не нужно делать что-то необычное, если сработает что-то простое.
Чтобы понять затраты на производительность простого подхода, мы запускаем тест, в котором каждый поток обновляет один общий счетчик фиксированное количество раз; затем мы меняем количество потоков. На рисунке 29.5 показано общее затраченное время при активном от одного до четырех потоков; каждый поток обновляет счетчик миллион раз. Этот эксперимент проводился на iMac с четырьмя процессорами Intel i5 с тактовой частотой 2,7 ГГц; при большем количестве активных процессоров мы надеемся увеличить общий объем работы за единицу времени.
Из верхней строки на рисунке (с пометкой "Precise") видно, что производительность синхронизированного счетчика плохо масштабируется. В то время как один поток может выполнить миллион обновлений счетчика за крошечное время (примерно 0,03 секунды), одновременное обновление счетчика двумя потоками миллион раз приводит к значительному замедлению (занимает более 5 секунд!). С увеличением количества потоков становится только хуже.
В идеале вы хотели бы, чтобы потоки выполнялись так же быстро на нескольких процессорах, как и один поток на одном. Достижение этой цели называется совершенным масштабированием (perfect scaling); несмотря на то, что выполняется больше работы, она выполняется параллельно, и, следовательно, время, затрачиваемое на выполнение задачи, не увеличивается.
Масштабируемый подсчет
Удивительно, но исследователи годами изучали, как создавать более масштабируемые счетчики [MS04]. Еще более удивительным является тот факт, что масштабируемые счетчики имеют значение, как показала недавняя работа по анализу производительности операционной системы [B + 10]; без масштабируемого подсчета некоторые рабочие нагрузки, работающие в Linux, страдают от серьезных проблем с масштабируемостью на многоядерных машинах.
Для решения этой проблемы было разработано множество методов. Мы опишем один подход, известный как приблизительный счетчик (approximate counter) [C06].
Приблизительный счетчик работает, предоставляя один логический счетчик с помощью множества локальных физических счетчиков, по одному на ядро процессора, а также одного глобального счетчика. В частности, на машине с четырьмя процессорами имеется четыре локальных счетчика и один глобальный. В дополнение к этим счетчикам существуют также блокировки: по одной для каждого локального* счетчика и по одной для глобального счетчика.
*Нам нужны локальные блокировки, потому что мы предполагаем, что на каждом ядре может быть более одного потока. Если бы вместо этого на каждом ядре выполнялся только один поток, локальная блокировка не потребовалась бы.
Основная идея приблизительного подсчета заключается в следующем. Когда поток, работающий на данном ядре, желает увеличить счетчик, он увеличивает свой локальный счетчик; доступ к этому локальному счетчику синхронизируется с помощью соответствующей локальной блокировки. Поскольку каждый процессор имеет свой собственный локальный счетчик, потоки между процессорами могут обновлять локальные счетчики без конфликтов, и, таким образом, обновления счетчика являются масштабируемыми.
Однако, чтобы поддерживать глобальный счетчик в актуальном состоянии (на случай, если поток захочет прочитать его значение), локальные значения периодически передаются глобальному счетчику путем получения глобальной блокировки и увеличения ее на значение локального счетчика; затем локальный счетчик сбрасывается до нуля.
Как часто происходит эта передача, определяется пороговым значением S. Чем меньше S, тем больше счетчик ведет себя как немасштабируемый счетчик выше; чем больше S, тем масштабируемее счетчик, но тем дальше глобальное значение может быть от фактического количества. Можно было бы просто получить все локальные блокировки и глобальную блокировку (в указанном порядке, чтобы избежать взаимоблокировки), чтобы получить точное значение, но это не масштабируемо.
Чтобы прояснить это, давайте рассмотрим пример (рис. 29.3).
В этом примере пороговое значение S равно 5, и на каждом из четырех процессоров есть потоки, обновляющие свои локальные счетчики L1 ... L4. Значение глобального счетчика (G) также отображается в трассировке с увеличением времени в сторону уменьшения. На каждом временном шаге локальный счетчик может увеличиваться; если локальное значение достигает порогового значения S, локальное значение передается глобальному счетчику и локальный счетчик сбрасывается.
Нижняя строка на рисунке 29.5 (помечена как "Approximate’) показывает производительность приблизительных счетчиков с пороговым значением S 1024. Производительность отличная; время, необходимое для обновления счетчика четыре миллиона раз на четырех процессорах, едва ли превышает время, необходимое для его обновления миллион раз на одном процессоре.
На рисунке 29.6 показана важность порогового значения S для четырех потоков, каждый из которых увеличивает счетчик в 1 миллион раз на четырех процессорах. Если S низкий, производительность низкая (но глобальный подсчет всегда достаточно точен); если S высокий, производительность отличная, но глобальный подсчет отстает (максимум на количество процессоров, умноженное на S). Этот компромисс между точностью и производительностью - это то, чего позволяют достичь приблизительные счетчики.
Грубый вариант приблизительного счетчика приведен на рисунке 29.4. Прочтите его или, еще лучше, проведите несколько экспериментов самостоятельно, чтобы лучше понять, как он работает.
СОВЕТ: БОЛЬШИЙ ПАРАЛЛЕЛИЗМ НЕ ОБЯЗАТЕЛЬНО ОЗНАЧАЕТ БОЛЬШУЮ СКОРОСТЬ
Если схема, которую вы разрабатываете, добавляет много накладных расходов (например, за счет частого получения и снятия блокировок вместо одного раза), тот факт, что она более параллельна, может быть не важен. Простые схемы, как правило, работают хорошо, особенно если они редко используют дорогостоящие процедуры. Добавление большего количества блокировок и усложнений может привести к вашему падению. Все это говорит о том, что есть один способ узнать необходимость в сложности наверняка: создать обе альтернативы (простую, но менее параллельную, и сложную, но более параллельную) и измерить, как они работают. В конце концов, вы не можете обманывать производительность; ваша идея либо быстрее, либо нет.
29.2 Конкурентный связный список
Рассмотрим более сложную структуру - связанный список. Давайте еще раз начнем с базового подхода. Для простоты мы опустим некоторые очевидные процедуры, которые мог бы иметь такой список, и просто сосредоточимся на одновременной вставке; мы оставим читателю подумать о поиске, удалении и так далее. На рисунке 29.7 показан код для этой элементарной структуры данных.
Как вы можете видеть в коде, код просто получает блокировку в процедуре вставки при входе и освобождает ее при выходе. Одна небольшая сложная проблема возникает, если malloc() выходит из строя (редкий случай); в этом случае код также должен снять блокировку перед сбоем вставки.
Было показано, что такой исключительный поток управления весьма подвержен ошибкам; недавнее исследование исправлений ядра Linux показало, что огромная доля ошибок (почти 40%) обнаруживается в таких редко используемых путях кода (действительно, это наблюдение вызвало некоторые из наших собственных исследований, в которых мы удалили все пути с нехваткой памяти из файловой системы Linux, что привело к более надежной системе [S +11]).
Таким образом, возникает проблема: можем ли мы переписать процедуры вставки и поиска, так чтобы они оставались корректными при одновременной вставке, но избежать случая, когда сбой также требует вызова разблокировки?
В данном случае ответ - да. В частности, мы можем немного изменить код, чтобы блокировка и разблокировка окружали только фактическую критическую секцию в коде вставки, и чтобы в коде поиска использовался общий путь выхода. Первое работает, потому что часть вставки на самом деле не нужно блокировать; предполагая, что malloc() сам по себе потокобезопасен, каждый поток может вызывать его, не беспокоясь об условиях гонки или других ошибках параллелизма. Только при обновлении общего списка необходимо удерживать блокировку. Подробные сведения об этих модификациях см. на рис. 29.8.
Что касается процедуры поиска, то это простое преобразование кода для перехода из основного цикла поиска в единственный вызов return. Такой подход уменьшает количество точек получения / снятия блокировки в коде и, таким образом, снижает вероятность случайного внесения ошибок (например, не разблокировать перед вызовом return) в код.
Масштабируемый связный список
Хотя у нас есть базовый параллельный связанный список, мы снова находимся в ситуации, когда он не особенно хорошо масштабируется. Один из методов, который исследователи изучили для обеспечения большего параллелизма в списке, - это так называемая блокировка "рука об руку" (hand-over-hand locking) (также известная как блокировочная связь a.k.a. lock coupling) [MS04].
Идея довольно проста. Вместо того, чтобы иметь одну блокировку для всего списка, вы вместо этого добавляете блокировку для каждого узла списка. При обходе списка код сначала захватывает блокировку следующего узла, а затем освобождает блокировку текущего узла (что вдохновляет название "передача из рук в руки").
СОВЕТ: БУДЬТЕ ОСТОРОЖНЫ С БЛОКИРОВКАМИ И ПОТОКОМ УПРАВЛЕНИЯ
Общий совет по проектированию, который полезен как в параллельном коде, так и в других местах, заключается в том, чтобы опасаться изменений потока управления, которые приводят к возврату функции, выходу или другим подобным ошибкам, которые останавливают выполнение функции. Поскольку многие функции начинаются с получения блокировки, выделения некоторой памяти или выполнения других подобных операций с сохранением состояния, при возникновении ошибок код должен отменить все состояние перед возвратом, что может привести к ошибкам. Таким образом, лучше всего структурировать код, чтобы свести к минимуму этот шаблон.
Концептуально hand-over-hand связанный список имеет некоторый смысл; он обеспечивает высокую степень параллелизма в операциях со списками. Однако на практике трудно сделать такую структуру быстрее, чем простой подход с одной блокировкой, поскольку накладные расходы на получение и снятие блокировок для каждого узла обхода списка являются непомерно высокими. Даже при очень больших списках и большом количестве потоков параллелизм, обеспечиваемый несколькими текущими обходами, вряд ли будет быстрее, чем просто захват одной блокировки, выполнение операции и ее освобождение. Возможно, стоило бы изучить какой-то гибрид (где вы захватываете новую блокировку через столько-то узлов).
29.3 Конкурентные очереди
Как вы уже знаете, всегда существует стандартный метод создания параллельной структуры данных: добавление большой блокировки. Для очереди мы пропустим этот подход, предполагая, что вы сможете это понять.
Вместо этого мы рассмотрим несколько более параллельную очередь, разработанную Майклом и Скоттом [MS98]. Структуры данных и код, используемые для этой очереди, показаны на рисунке 29.9.
Если вы внимательно изучите этот код, вы заметите, что есть две блокировки, одна для начала очереди и одна для хвоста. Цель этих двух блокировок - обеспечить параллелизм операций постановки в очередь и снятия с очереди. В общем случае, процедура enqueue использует только tail lock, а dequeue только head lock.
Один из трюков, используемых Майклом и Скоттом, заключается в добавлении фиктивного узла (выделенного в коде инициализации очереди); этот фиктивный узел позволяет разделять операции на "головные" и "хвостовые". Изучите код или, еще лучше, введите его, запустите и измерьте, чтобы глубоко понять, как он работает.
Очереди обычно используются в многопоточных приложениях. Однако используемый здесь тип очереди (только с блокировками) часто не полностью отвечает потребностям таких программ. Более полно разработанная ограниченная очередь, которая позволяет потоку ждать, если очередь пуста или чрезмерно заполнена, является предметом нашего интенсивного изучения в следующей главе, посвященной переменным условий. Следите за повествованием!
29.4 Конкурентная хеш-таблица
Мы заканчиваем наше обсуждение простой и широко применимой структурой параллельных данных - хэш-таблицей. Мы сосредоточимся на простой хэш-таблице, размер которой не изменяется; для обработки изменения размера требуется немного больше работы, которую мы оставляем в качестве упражнения для читателя (извините!).
Эта параллельная хэш-таблица (рис. 29.10) проста, построена с использованием параллельных списков, которые мы разработали ранее, и работает невероятно хорошо. Причина хорошей производительности заключается в том, что вместо одной блокировки для всей структуры он использует блокировку для каждого хэш-блока (каждый из которых представлен списком). Это позволяет выполнять множество одновременных операций.
На рисунке 29.11 показана производительность хэш-таблицы при одновременных обновлениях (от 10 000 до 50 000 одновременных обновлений из каждого из четырех потоков на одном и том же iMac с четырьмя процессорами). Также для сравнения показана производительность связанного списка (с одной блокировкой). Как вы можете видеть из графика, эта простая параллельная хэш-таблица великолепно масштабируется; связанный список, напротив, этого не делает.
29.5 Выводы
Мы представили выборку параллельных структур данных, от счетчиков до списков и очередей, и, наконец, до вездесущей и широко используемой хэш-таблицы. На этом пути мы усвоили несколько важных уроков: быть осторожными при получении и снятии блокировок в связи с изменениями потока управления; что увеличение параллелизма не обязательно повышает производительность; что проблемы с производительностью следует устранять только после их возникновения. Этот последний пункт, позволяющий избежать преждевременной оптимизации, имеет центральное значение для любого разработчика, ориентированного на производительность; нет смысла делать что-то быстрее, если это не улучшит общую производительность приложения.
Конечно, мы только немного поскребли тему высокопроизводительных структур данных. Смотрите отличный опрос Мойра и Шавита для получения дополнительной информации, а также ссылки на другие источники [MS04]. В частности, вас могут заинтересовать другие структуры (например, B-деревья); для получения этих знаний лучше всего использовать класс базы данных. Вам также может быть интересно узнать о методах, которые вообще не используют традиционные блокировки; такие неблокирующие структуры данных - это то, с чем мы познакомимся в главе об общих ошибках параллелизма, но, честно говоря, эта тема - целая область знаний, требующая большего изучения, чем возможно в этой скромной книге. Узнайте больше самостоятельно, если хотите (как всегда!).
СОВЕТ: ИЗБЕГАЙТЕ ПРЕЖДЕВРЕМЕННОЙ ОПТИМИЗАЦИИ (ЗАКОН КНУТА)
При создании параллельной структуры данных начните с самого простого подхода, который заключается в добавлении одной большой блокировки для обеспечения синхронизированного доступа. Поступая таким образом, вы, скорее всего, создадите правильную блокировку; если вы обнаружите, что она страдает от проблем с производительностью, вы можете ее усовершенствовать, сделав ее быстрой только в случае необходимости. Как классно сказал Кнут, “Преждевременная оптимизация - корень всего зла”.
Многие операционные системы использовали единую блокировку при первом переходе на многопроцессорные системы, включая SunOS и Linux. В последнем случае у этой блокировки даже было название - большая блокировка ядра (BKL). В течение многих лет этот простой подход был хорошим, но когда системы с несколькими процессорами стали нормой, одновременное использование только одного активного потока в ядре стало узким местом в производительности. Таким образом, наконец-то пришло время добавить оптимизацию улучшенного параллелизма в эти системы. В Linux был применен более простой подход: заменить одну блокировку многими. В Sun было принято более радикальное решение: создать совершенно новую операционную систему, известную как Solaris, которая с первого дня более фундаментально использует параллелизм. Прочтите книги по ядру Linux и Solaris для получения дополнительной информации об этих увлекательных системах [BC05, MM 00].
Ссылки
[B+10] “An Analysis of Linux Scalability to Many Cores” by Silas Boyd-Wickizer, Austin T. Clements, Yandong Mao, Aleksey Pesterev, M. Frans Kaashoek, Robert Morris, Nickolai Zeldovich . OSDI ’10, Vancouver, Canada, October 2010. A great study of how Linux performs on multicore machines, as well as some simple solutions. Includes a neat sloppy counter to solve one form of the scalable counting problem.
[BH73] “Operating System Principles” by Per Brinch Hansen. Prentice-Hall, 1973. Available: http://portal.acm.org/citation.cfm?id=540365. One of the first books on operating systems; certainly ahead of its time. Introduced monitors as a concurrency primitive
[BC05] “Understanding the Linux Kernel (Third Edition)” by Daniel P. Bovet and Marco Cesati. O’Reilly Media, November 2005. The classic book on the Linux kernel. You should read it.
[C06] “The Search For Fast, Scalable Counters” by Jonathan Corbet. February 1, 2006. Available: https://lwn.net/Articles/170003. LWN has many wonderful articles about the latest in Linux This article is a short description of scalable approximate counting; read it, and others, to learn more about the latest in Linux.
[L+13] “A Study of Linux File System Evolution” by Lanyue Lu, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau, Shan Lu. FAST ’13, San Jose, CA, February 2013. Our paper that studies every patch to Linux file systems over nearly a decade. Lots of fun findings in there; read it to see! The work was painful to do though; the poor graduate student, Lanyue Lu, had to look through every single patch by hand in order to understand what they did.
[MS98] “Nonblocking Algorithms and Preemption-safe Locking on by Multiprogrammed Sharedmemory Multiprocessors. ” M. Michael, M. Scott. Journal of Parallel and Distributed Computing, Vol. 51, No. 1, 1998 Professor Scott and his students have been at the forefront of concurrent algorithms and data structures for many years; check out his web page, numerous papers, or books to find out more.
[MS04] “Concurrent Data Structures” by Mark Moir and Nir Shavit. In Handbook of Data Structures and Applications (Editors D. Metha and S.Sahni). Chapman and Hall/CRC Press, 2004. Available: www.cs.tau.ac.il/˜shanir/concurrent-data-structures.pdf. A short but relatively comprehensive reference on concurrent data structures. Though it is missing some of the latest works in the area (due to its age), it remains an incredibly useful reference.
[MM00] “Solaris Internals: Core Kernel Architecture” by Jim Mauro and Richard McDougall. Prentice Hall, October 2000. The Solaris book. You should also read this, if you want to learn about something other than Linux.
[S+11] “Making the Common Case the Only Case with Anticipatory Memory Allocation” by Swaminathan Sundararaman, Yupu Zhang, Sriram Subramanian, Andrea C. Arpaci-Dusseau, Remzi H. Arpaci-Dusseau . FAST ’11, San Jose, CA, February 2011. Our work on removing possibly-failing allocation calls from kernel code paths. By allocating all potentially needed memory before doing any work, we avoid failure deep down in the storage stack.
