При участии Тима Перлса, Джошуа Блоха, Джозева Боубира, Дэвида Холмса и Дага Ли Параллельное программирование в java на
 Скачать 4.97 Mb.
|
|
Листинг 11.1 Последовательный доступ к очереди задач Время обработки одной задачи включает в себя не только время выполнения задачи, представленной экземпляром Runnable , но и время на извлечение задачи из совместно используемой рабочей очереди. Если рабочая очередь представляет собой реализацию LinkedBlockingQueue , операция извлечения задачи из очереди может блокироваться на меньшее время, чем при использовании синхронизированной реализации LinkedList , поскольку реализация LinkedBlockingQueue использует более масштабируемый алгоритм, но доступ к любой совместно используемой структуре данных фундаментально вводит в программу элемент сериализации. В этом примере также игнорируется другой распространенный источник последовательно выполняемого кода: обработка результатов. Все полезные вычисления порождают какой-то результат или вызывают побочные эффекты - в противном случае они могут быть исключены как мертвый код. Поскольку интерфейс Runnable не предоставляет возможности явной обработки результатов, выполнение этих задач должно приводить к возникновению каких-то побочных эффектов, например, запись результатов выполнения в файл лога или их помещение в структуру данных. Файлы логов и контейнеры результатов обычно совместно используются несколькими рабочими потоками и поэтому также являются источником источник последовательно выполняемого кода. Если вместо этого каждый поток будет поддерживать свои собственные структуры данных для хранения результатов, которые будут объединяться после выполнения всех задач, то окончательное слияние также будет являться источником последовательно выполняемого кода. У всех параллельных приложений есть некоторые источники последовательно выполняемого кода; если вы думаете, что у вашего кода их нет, посмотрите снова. 11.2.1 Пример: скрытое последовательное выполнение в фреймворках Чтобы увидеть, как последовательно выполняемый код может быть скрыт в структуре приложения, можно сравнить пропускную способность при добавлении потоков и определить различия в последовательном выполнении на основе наблюдаемых различий в масштабируемости. На рис. 11.2 демонстрируется результат выполнения простого приложения, в котором несколько потоков многократно удаляют элемент из общей очереди и обрабатывают его, аналогично примеру из листинга 11.1. Шаг обработки включает в себя только локальное, относительно потока, вычисление. Если поток обнаруживает, что очередь пуста, он помещает пакет новых элементов в очередь, чтобы другим потокам было что обрабатывать на следующей итерации. Доступ к совместно используемой очереди явным образом влечет за собой некоторую степень последовательного выполнения, но шаг обработки полностью распараллеливается, так как он не включает в себя совместно используемые данные. Рисунок 11.2 Сравнение реализаций очередей Кривые на рис. 11.2 позволяют сравнить пропускную способность для двух потокобезопасных реализаций очереди: реализации на основе LinkedList , обернутой реализацией synchronizedList , и реализации ConcurrentLinkedQueue Тесты проводились на 8-ядерной системе Sparc V880, под управлением ОС Solaris. Хотя каждый запуск представляет собой выполнение одинакового объема “работы”, мы видим, что простое изменение реализаций очередей может оказать Пропускная способность реализации ConcurrentLinkedQueue продолжает улучшаться, пока количество потоков не достигнет количества процессоров, а затем остается почти постоянной. С другой стороны, пропускная способность синхронизированной реализации LinkedList показывает некоторое улучшение до трех потоков, но затем падает по мере нарастания издержек синхронизации. К тому времени, когда количество потоков доберётся до четырех или пяти, конкуренция станет настолько тяжела, что каждая попытка доступа к блокировке очереди будет оспариваться, и в объёме всей пропускной способности начнёт доминировать переключение контекста. Различие в пропускной способности происходит от различных степеней последовательно выполняемого кода, в двух разных реализациях очередей. Синхронизированная реализация LinkedList защищает всё состояние очереди с помощью единственной блокировки, которая удерживается на протяжении вызовов методов offer или remove ; реализация ConcurrentLinkedQueue использует сложный алгоритм неблокирующей очереди (см. раздел 15.4.2 ), который использует атомарные ссылки для обновления отдельных указателей на ссылки. В одном случае - последовательно выполняется вставка или удаление; в другом случае - последовательно выполняется только обновление отдельных указателей. 11.2.2 Качественное применение закона Амдала Закон Амдала количественно определяет возможное ускорение, когда доступно больше вычислительных ресурсов, если мы можем точно оценить долю последовательно выполняемого кода. Хотя прямое измерение доли последовательно выполняемого кода может быть затруднено, закон Амдала всё же может быть полезен и без такого измерения. Поскольку наши ментальные модели находятся под влиянием окружающей нас среды, многие из нас привыкли думать, что многопроцессорная система, имеет два или четыре процессора, или, может быть (если у нас большой бюджет) несколько десятков таковых, потому что эта технология стала широкодоступна в последние годы. Но по мере того, как многоядерные процессоры станут популярнее, системы будут иметь сотни или даже тысячи процессоров 112 . Алгоритмы, которые кажутся масштабируемыми в четырех процессорной системе, могут иметь скрытые узкие места (bottlenecks) в масштабируемости, которые еще не были обнаружены. В процессе оценки алгоритма, размышление “с ограничениями” о том, что произойдет с сотнями или тысячами процессоров, может дать некоторое представление, где могут проявиться ограничения масштабирования. Например, в разделах 11.4.2 и 11.4.3 обсуждается два способа повышения детализации блокировок: разделение блокировок (разделение одной блокировки на две) и чередование блокировок (разделение одной блокировки на несколько блокировок). Глядя на них через призму закона Амдала, мы видим, что разделение блокировки на две части, не сильно приближает нас к использованию множества процессоров, но чередование блокировок кажется гораздо более перспективным, потому что размер набора полос (stripe) может быть увеличен по мере увеличения количества процессоров. (Конечно, оптимизация производительности всегда должна рассматриваться в свете фактических требований к производительности; в некоторых случаях, разделения блокировки на две части, для удовлетворения требований, может быть достаточно.) 112 Обновление рынка: на момент написания этой статьи Sun поставляет недорогие серверные системы на основе 8-ядерного процессора Niagara, а Azul поставляет высокопроизводительные серверные системы (96, 192 и 384-ядра) на основе 24-ядерного процессора Vega. 11.3 Затраты, вводимые потоками Однопоточные программы не требуют ни планирования, ни синхронизации и не нуждаются в использовании блокировок для сохранения согласованности структур данных. Планирование и координация взаимодействия между потоками требуют затрат производительности; для потоков, предлагающих повышение производительности, преимущества распараллеливания должны перевешивать затраты на обеспечение параллелизма. 11.3.1 Переключение контекста Если основной поток является единственным потоком, выполняемым по расписанию, он почти никогда не будет планироваться. С другой стороны, если количество выполняемых потоков больше, чем количество доступных ЦП, в конечном итоге ОС будет упреждать один поток, чтобы другой мог использовать ЦП. Это вызывает переключение контекста, которое требует сохранения контекста текущего потока и восстановления контекста выполнения нового запланированного потока. Переключение контекста операция не бесплатная; планирование потоков требует манипулирования совместно используемыми структурами данных в ОС и JVM. ОС и JVM используют те же процессоры, что и ваша программа; большее количество времени процессора, потраченного на JVM, и код ОС означает, что вашей программе будет доступно меньше времени. Но деятельность ОС и JVM - это не единственные затраты, возникающие при переключении контекста. Когда происходит переключение на новый поток, данные, в которых он нуждается, вряд ли будут доступны в локальном кэше процессора, таким образом, переключение контекста приведёт к шквалу промахов попадания в кэш, и потоки будут работать немного медленнее в том случае, если их выполнение будет запланировано впервые. Это одна из причин, по которой планировщики дают каждому выполняемому потоку определенный минимальный квант времени, даже когда многие другие потоки вынуждены ожидать: такой подход позволяет амортизировать затраты на переключение контекста и его последствия в течение более длительного времени непрерывного выполнения, улучшая общую пропускную способность (за счет некоторых затрат на отзывчивость). Когда поток блокируется из-за ожидания конкурирующей блокировки, JVM обычно его приостанавливает и позволяет ему выключиться. Если потоки блокируются часто, они не смогут использовать весь запланированный для выполнения квант времени. Программа, использующая множество блокировок (блокирующий ввод/вывод, ожидание конкурирующих блокировок или ожидание переменных условий), использует больше переключений контекста, чем та, что ограничена только ЦП, что увеличивает затраты на планирование и приводит к снижению пропускной способности. (Неблокирующие алгоритмы также могут помочь в снижении количества переключений контекста; см. главу 15 .) Фактические затраты на переключение контекста варьируется от платформы к платформе, но хорошее эмпирическое правило заключается в том, что переключение контекста, для большинства текущих процессоров, по затратам эквивалентно 5,000-10,000 тактам процессора или нескольким микросекундам. Команда vmstat в системах Unix и средство perfmon в системах Windows позволяют получить отчёт о количестве переключений контекста, и проценте времени, проведенном в ядре. Высокая загрузка ядра (более 10%) часто указывает на интенсивное планирование, которое может быть вызвано блокировками при выполнении операций ввода/вывода или конкуренцией за захват блокировок. 11.3.2 Синхронизация памяти Затраты производительности на синхронизацию берут своё начало из нескольких источников. Гарантии видимости, предоставляемые операторами synchronized и volatile , могут повлечь за собой использование специальных инструкций, называемых барьерами памяти (memory barriers), которые могут сбрасывать или аннулировать кэши, сбрасывать аппаратные буферы на запись и останавливать выполняющие конвейеры. Использование барьеров памяти также может иметь косвенные последствия для производительности, поскольку они препятствуют проведению оптимизаций, выполняемых компиляторами; большинство операций нельзя переупорядочить, когда используются барьеры памяти. При оценке влияния синхронизации на производительность, важно различать конкурентную (contended) и неконкурентную (uncontended) синхронизацию. Механизм synchronized оптимизирован для неконкурентного случая (оператор volatile всегда неконкурентен), и на момент написания этих строк, затраты на выполнение “кратчайшего варианта” неконкурентной синхронизации, для большинства систем, колеблются в пределах от 20 до 250 тактов процессора. Хотя это, конечно, не ноль, эффект необходимой, незапланированной синхронизации редко оказывает значимое влияние на общую производительность приложения, в свою очередь, альтернатива включает в себя угрозу безопасности и потенциальное обречение себя (или вашего преемника), в будущем, на очень болезненный поиск ошибок Современные среды JVM могут снижать затраты на случайную синхронизацию, проводя оптимизацию блокировок, за которые, как доказано, никогда не будет конкуренции. Если объект блокировки доступен только текущему потоку, среде JVM разрешено оптимизировать захват блокировки, поскольку нет никакого способа, которым другой поток мог бы синхронизироваться на той же самой блокировке. Например, захват блокировки, как показано в листинге 11.2, всегда может быть устранен средой JVM. synchronized (new Object()) { // do something } Листинг 11.2 Синхронизация, не оказывающая никакого эффекта. Не делайте так Более сложные среды JVM могут использовать последовательный анализ для определения того, что ссылка на локальный объект никогда не публикуется в куче и поэтому является локальной для потока. В методе getStoogeNames из листинга 11.3, единственной ссылкой на список является локальная переменная stooges , а переменные, ограниченные стеком, автоматически являются локальными для потока. Наивное выполнение метода getStoogeNames захватывает и освобождает блокировку на экземпляре Vector четыре раза, по одному разу для каждого вызова add или toString . Тем не менее, умный компилятор среды выполнения может встроить эти вызовы, а затем увидеть, что переменная stooges и её внутреннее состояние никогда не сбегают, и, следовательно, что все четыре захвата блокировок могут быть устранены 113 public String getStoogeNames() { List } Листинг 11.3 Кандидат на оптимизацию lock elision Даже без обращения к последовательному анализу, компиляторы также могут выполнять укрупнение блокировок, путём слияния соседних блоков synchronized с использованием одной и той же блокировки. В случае метода getStoogeNames , среда JVM, выполняющая укрупнение блокировки, может объединить три вызова метода add и вызов метода toString в один блок захвата и освобождения блокировки, используя эвристику относительных затрат на синхронизацию по сравнению с инструкциями внутри блока synchronized 114 Это не только снижает затраты на синхронизацию, но и предоставляет оптимизатору гораздо больший блок для работы, что, вероятно, позволяет выполнять и другие оптимизации. Не стоит чрезмерно беспокоиться о стоимости неконкурентной синхронизации. Базовый механизм уже достаточно быстр, и среды JVM могут выполнять дополнительные оптимизации, которые еще больше уменьшают или устраняют затраты. Вместо этого сосредоточьте усилия по оптимизации на тех областях, в которых фактически происходит конфликт блокировок. Синхронизация в одном потоке также может повлиять на производительность других потоков. Синхронизация создает трафик в шине совместно используемой памяти; эта шина имеет ограниченную пропускную способность и совместно используется всеми процессорами. Если потоки вынуждены конкурировать за пропускную способность синхронизации, все потоки, использующие синхронизацию, будут страдать. 115 11.3.3 Блокирование Неконкурирующая синхронизация может быть полностью обработана в среде JVM (Bacon et al., 1998); для конкурирующей синхронизации может потребоваться вмешательство ОС, что приводит к увеличению затрат. В случае, если блокировка конкурирующая, проигравший поток должен быть заблокирован. Среда JVM может реализовать блокировку или через spin-waiting (многократная попытка захвата блокировки, пока захват не завершится успехом) или путем приостановки (suspending) заблокированного потока средствами операционной системы. Что 113 Эта оптимизация компилятора, называемая lock elision, выполняется в IBM JVM и ожидается в HotSpot с Java 7. 114 Умный динамический компилятор может выяснить, что этот метод всегда возвращает одну и ту же строку, и после первого выполнения перекомпилировать метод getStoogeNames для простого возврата значения, полученного при первом выполнении. 115 Этот аспект иногда используется в спорах против использования неблокирующих алгоритмов без отката, потому что при тяжелой конкуренции неблокирующие алгоритмы генерируют больше синхронизирующего трафика, чем основанные на блокировках. См. Главу 15. является более эффективным, зависит от отношения между накладными расходами на переключение контекста и временем, в течение которого блокировка будет доступна; механизм spin-waiting предпочтительнее для короткого ожидания, а приостановка предпочтительнее для длительного ожидания. Некоторые среды JVM выбирают между обоими вариантами адаптивно, основывая своё решение на данных профилирования прошлых периодов ожидания, но большинство просто приостанавливают выполнение потоков, ожидающих блокировку. Приостановка потока, из-за того, что он не может получить блокировку, или из- за того, что он заблокирован в состоянии ожидания или заблокирован при выполнении операций ввода/вывода, влечёт за собой два дополнительных переключения контекста и всю сопровождающую активность операционной системы и кэша: блокированный поток выключается, прежде чем истечёт выделенный ему квант времени, и затем, позже, переключается обратно, когда блокировка или другой необходимый ресурс становятся доступны. (Блокировка из- за конфликта блокировок также приводит к затратам потока, удерживающего блокировку: когда он освобождает блокировку, он должен затем попросить ОС возобновить выполнение заблокированного потока.) 11.4 Уменьшение конкуренции за блокировку Мы видели, что последовательно выполняемый код ухудшает масштабируемость, а переключение контекста - производительность. Конкурирующая блокировка является причиной возникновения обоих случаев, поэтому уменьшение конкуренции может улучшить и производительность, и масштабируемость. Доступ к ресурсам, защищаемым монопольной блокировкой, строго последователен - одновременно только один поток может получить к ним доступ. Конечно, мы используем блокировки по уважительным причинам, таким как предотвращение повреждения данных, но эта безопасность имеет свою цену. Постоянная конкуренция за захват блокировки ограничивает масштабируемость. Основной угрозой масштабируемости в параллельных приложениях является монопольная блокировка ресурсов. Вероятность возникновения конкуренции за блокировку зависит от двух факторов: частоты захвата блокировки и времени её удержания после захвата 116 Если произведение этих факторов достаточно мало, то большинство попыток захвата блокировки не будет приводить к конкуренции, и конфликт блокировок не будет создавать значительных препятствий для масштабируемости. В том случае, если блокировка востребована достаточно сильно, потоки будут блокироваться в ожидании её; в крайнем случае, процессоры будут простаивать, даже если есть множество работы. Существует три способа уменьшения конкуренции за блокировку: • Сокращение времени, в течение которого удерживается блокировка; • Уменьшение частоты, с которой захватываются блокировки; или • Замена монопольных блокировок механизмами координации, обеспечивающими больший параллелизм. 116 Это следствие закона Литтла, являющегося результатом теории очередей, в которой говорится, что “среднее число клиентов в стабильной системе, равно их средней скорости прибытия, умноженной на их среднее время нахождения в системе”. (Маленький, 1961) |