Книга: «Грокаем конкурентность»

image
В продолжение серии «Грокаем» — очередная новинка. В этот раз грокать мы собираемся конкурентность!

Представьте себе мир, в котором за развитием технологии угнаться сложнее, чем за гепардом, накачанным стимуляторами, а спрос на эффективное конкурентное программирование неудержимо растет. В этом мире разработчики сталкиваются с серьезной задачей: как создавать системы, которые способны справиться с колоссальными объемами данных и обрабатывать их достаточно проворно, чтобы удовлетворить неутолимые потребности пользователей? В этом мире конкурентность не только пленила умы, но и стала головоломкой, которую приходится разгадывать. И самое поразительное — в этом мире мы живем сегодня.
Читать отрывок.

Конкурентность позволяет эффективно выполнять компьютерные программы, разделяя их на задачи, которые можно запускать независимо. Такой подход помогает ускорить игровую графику, обучать большие модели искусственного интеллекта, быстро масштабировать веб-приложения, оптимизировать обработку больших данных и решать многие другие задачи. Работать с конкурентностью непросто, так что эта книга постепенно введет вас в курс дела, а помогут в этом интересные примеры, забавные иллюстрации и понятный код на Python.

Об авторе
Кирилл Бобров
опытный разработчик с непростым характером, который отлично разбирается в разработке и проектировании высоконагруженных приложений. Питая страсть к инженерии данных, он направляет усилия на то, чтобы реализовывать передовые практики инженерии данных для компаний по всему миру. А еще этот угрюмый тип выступает в образе симпатичного кота, который ведет популярный иллюстрированный техноблог

Причины купить «Грокаем конкурентность»:


• Новая книга серии «Грокаем»! Без сложной математики, технического жаргона и тяжеловесных научных рассуждений, только простые и доступные объяснения.
О книгах всей серии «Грокаем» написано в нашей статье.
image
Важной особенностью, объединяющей книги в серию «Грокаем» является нестандартные иллюстрации и понятные примеры, которые облегчают усвоение полученной информации. Эта книга — не типичное техническое пособие, в ней кроются занимательные истории и пасхалки, увлекающие читателей.

• Работать с конкурентностью непросто, так что книга постепенно введет вас в курс дела, а помогут в этом интересные примеры, забавные иллюстрации и понятный код на Python.
Необязательно иметь навыки конкурентного программирования и опыт работы с высокопроизводительными системами.

• Изучите приемы, с помощью которых сможете программировать многоядерные процессоры, графические процессоры и другие высокопроизводительные системы. Освоите паттерны, которые обеспечивают производительность, масштабируемость и гибкость.
Знания, которые вы получите, помогут ориентироваться в конкурентных фреймворках и разрабатывать масштабируемые решения в интересующей вас
области. Книга в некоторой степени восполняет нехватку доступных ресурсов по
этой теме; это подробное и доходчивое руководство для читателей, которые хотят
разобраться в понятиях конкурентности и асинхронности.

Отрывок из книги. Обедающие философы


Обедающие философы


Блокировки (мьютексы и семафоры) весьма сложны в использовании. Если применять их некорректно, работа приложения может нарушиться оттого, что блокировки устанавливаются, но не освобождаются, или блокировки, которые нужно установить, оказываются недоступными. Проблему синхронизации в ситуациях, когда несколько задач конкурируют за блокировки, можно проиллюстрировать с помощью задачи об обедающих философах, которую сформулировал Эдсгер Дейкстра в 1965 году. Этот пример часто служит стандартным тестовым сценарием, с помощью которого оцениваются методы синхронизации.

Пять молчаливых философов сидят за круглым столом перед блюдом с пельменями. Между каждой парой ближайших философов лежит палочка. Философы занимаются тем, что у них обычно получается лучше всего: они размышляют и едят.

Каждую палочку может держать только один философ, так что никто из них не может использовать палочку, которую в данный момент держит кто-то другой. После того как философ закончит есть, он должен положить обе палочки, чтобы их могли взять соседи. Философ может брать только те палочки, которые лежат справа и слева от него, может делать это только тогда, когда палочки доступны, и не может начать есть, пока не возьмет обе палочки.

image


Требуется разработать ритуал (алгоритм), чтобы каждый философ мог переключаться между двумя состояниями: он либо ест, либо размышляет. Предполагается, что ни один философ не знает, когда другие захотят есть или размышлять, — таким образом, у нас получается конкурентная система.

Взятие пельменей с блюда является критической секцией, и чтобы ее защитить, можно разработать процесс взаимоисключения, используя две палочки как мьютексы. Таким образом, когда философ хочет взять пельмень, он сначала берет палочку слева, если она доступна, и устанавливает для нее блокировку. Затем он берет палочку справа, если она доступна, и тоже устанавливает для нее блокировку. Теперь философ держит две палочки: значит, он находится в критической секции и может съесть пельмень. После этого он кладет на стол правую палочку, чтобы снять блокировку, а затем кладет левую палочку. Наконец, будучи философом, он возвращается к философским размышлениям.

В коде этот процесс выглядит так:

image


В этом коде поток Philosopher представляет одного философа. Он содержит его имя и два мьютекса, left_chopstick и right_chopstick, которые философ захватывает в указанном порядке.

Общая переменная dumplings представляет оставшиеся пельмени на общем блюде. В цикле while философы берут пельмени, пока они остаются на блюде. В цикле философ устанавливает блокировку сначала для левой, а потом для правой палочки. Затем, если на блюде еще остались пельмени, философ берет один из них, уменьшая переменную dumplings, и программа выводит количество оставшихся пельменей.

Философы переключаются между едой и размышлениями. Но поскольку они ведут себя как конкурентные задачи, ни один из них не знает, когда другие захотят есть или размышлять, что может вызвать затруднения. Давайте посмотрим, какие проблемы могут возникнуть при выполнении этого кода и как их можно решить.

Взаимные блокировки


Чтобы упростить объяснения в этом разделе, уменьшим количество философов до двух, сохранив исходный алгоритм:

# Chapter 9/deadlock/deadlock.py
if __name__ == "__main__":
    chopstick_a = LockWithName("Палочка A")
    chopstick_b = LockWithName("Палочка B")

    philosopher_1 = Philosopher("Философ 1", chopstick_a,
chopstick_b)
    philosopher_2 = Philosopher("Философ 2", chopstick_b,
chopstick_a)

    philosopher_1.start()
    philosopher_2.start()


Результат запуска программы выглядит примерно так:

Философ 1 ест пельмень. Осталось пельменей: 19
Философ 1 ест пельмень. Осталось пельменей: 18
Философ 2 ест пельмень. Осталось пельменей: 17

Философ 2 ест пельмень. Осталось пельменей: 9

Программа не завершается: она застревает на одном месте, а на блюде все еще остаются пельмени. Что происходит?

Допустим, первый философ проголодался, и он берет палочку A. В то же время второй философ тоже хочет перекусить и берет палочку B. Каждый поток удерживает одну из двух блокировок, которые ему нужны, но оба бесконечно ожидают, пока другой поток освободит оставшуюся блокировку.

Перед вами пример так называемой взаимной блокировки (deadlock). Эта ситуация заключается в том, что несколько задач ожидают ресурсов, которые заняты другими задачами, и ни одна из них не может продолжить выполнение. Программа навечно застревает в этом состоянии, поэтому ее приходится прерывать вручную.

Если запустить программу еще раз, она приведет к взаимной блокировке после другого количества пельменей — точное значение каждый раз зависит от того, как система планирует задачи.

image


Как и в случае с ситуацией гонки, вам может повезти, и вы никогда не столкнетесь с этой проблемой в своих приложениях. Но даже если взаимная блокировка может возникнуть хотя бы теоретически, ее стоит предотвратить. Опасность взаимной блокировки возникает каждый раз, когда задача пытается получить сразу несколько блокировок. Как избежать взаимных блокировок — типичная проблема в конкурентных программах, где критические секции кода защищаются с помощью мьютексов.

ПРИМЕЧАНИЕ Никогда не рассчитывайте на конкретный порядок выполнения. Если в программе выполняются несколько потоков, как это было в предыдущих примерах, то порядок их выполнения не детерминирован. Если для вас важно, в каком порядке выполняются потоки относительно друг друга, необходимо применить синхронизацию. Но если вам нужна оптимальная производительность, следует избегать синхронизации, насколько это возможно. В частности, стоит создавать задачи с высокой детализацией, которым не нужна синхронизация; это позволит ядрам обрабатывать каждую назначенную им задачу как можно быстрее.

Но давайте рассмотрим более правдоподобный пример — все-таки не каждый день приходится угощать философов пельменями. Представьте себе реальную систему: ваш домашний компьютер, на котором установлены два приложения — одно для видеоконференций (например, Zoom или Skype), а другое — для просмотра фильмов (например, Netflix или YouTube). Приложения предназначены для разных целей — одно позволяет общаться с коллегами или друзьями, а другое — смотреть любимое кино, но оба обращаются к одним и тем же подсистемам компьютера — в частности к экрану и аудиоустройству. Допустим, обеим программам понадобился доступ к экрану и звуку. Они выдают запросы одновременно, и ОС передает экран проигрывателю, а звук — видеочату. Обе программы блокируют полученный ресурс, а затем ожидают, пока освободится другой ресурс. И они будут ждать вечно, как и бедные философы! Взаимная блокировка не прекратится, если только ОС не предпримет радикальные меры — например, уничтожит один или несколько процессов или заставит их снять блокировку.

image


Решение с арбитром


Вернемся к задаче с философами. Чтобы предотвратить взаимную блокировку, можно предусмотреть, чтобы каждый философ мог взять либо две палочки, либо ни одной. Для этого проще всего добавить в систему арбитра, который отвечает за палочки (например, официанта). Чтобы взять палочку, философ сначала спрашивает разрешения у официанта. Официант дает разрешение только одному философу за раз, пока тот не возьмет обе палочки. В любой момент философ может вернуть палочку обратно.

image


Функции официанта можно реализовать с помощью еще одной блокировки:

image


И официант может выступать в качестве блокировки:

image


image


Поскольку это решение вводит новую центральную сущность (официанта), оно может ограничить конкурентность: если философ ест, а один из его соседей запрашивает палочки, то всем остальным философам придется ждать, пока этот запрос будет выполнен, даже если палочки им доступны. В реальной компьютерной системе арбитр делает практически то же самое, упорядочивая доступ со стороны потоков-исполнителей. Такой подход снижает уровень конкурентности, и это не самый эффективный вариант.

Решение с иерархией ресурсов


А что если установить приоритеты для блокировок, чтобы философы сначала пытались брать одну и ту же палочку? Тогда проблема взаимной блокировки не возникнет, потому что философы будут конкурировать за одну первую блокировку.

Оба философа должны договориться о том, что из двух палочек, которые они собираются использовать, палочку с бóльшим приоритетом всегда нужно брать первой. В нашем случае оба философа одновременно конкурируют за высокоприоритетную палочку. Когда один философ побеждает и берет ее, на столе остается только палочка с меньшим приоритетом. Поскольку философы согласились сначала брать высокоприоритетную палочку, второй философ не сможет взять оставшуюся. А у философа, который взял первую палочку, теперь есть доступ к палочке с меньшим приоритетом, так что он может начать есть обеими палочками. Гениально!

Назначим приоритеты для палочек. Допустим, палочка A имеет наивысший приоритет, а палочка B — следующий. Каждый философ всегда должен сначала брать палочку с бóльшим приоритетом.

image


В нашем коде философ 2 создавал проблему, когда брал палочку B до палочки A. Чтобы решить проблему, мы изменим порядок захвата палочек, не изменяя остальной код. Сначала берется палочка A, и только после этого — палочка B:

# Chapter 9/deadlock/deadlock_hierarchy.py
from lock_with_name import LockWithName

from deadlock import Philosopher

if __name__ == "__main__":
    chopstick_a = LockWithName("Палочка A")
    chopstick_b = LockWithName("Палочка B")

    philosopher_1 = Philosopher("Философ 1", chopstick_a,
chopstick_b)
    philosopher_2 = Philosopher("Философ 2", chopstick_a,
chopstick_b)

    philosopher_1.start()
    philosopher_2.start()


Если запустить программу после этих изменений, она отработает до конца без взаимных блокировок.

ПРИМЕЧАНИЕ Упорядочить блокировки не всегда возможно, если заранее неизвестно, какие блокировки могут понадобиться задаче. Чтобы предотвратить взаимные блокировки, можно использовать такие механизмы, как графы распределения ресурсов (RAG) и иерархии блокировок. RAG помогают выявлять и предотвращать циклы в отношениях между процессами и ресурсами. В некоторых языках программирования и фреймворках поддерживаются высокоуровневые примитивы синхронизации, которые упрощают управление блокировками. Тем не менее вам все равно потребуется тщательно проектировать и тестировать свой код, потому что эти методы не гарантируют полного устранения взаимных блокировок.

Еще один способ предотвратить взаимные блокировки — установить тайм-аут для попыток блокирования. Если в течение определенного периода времени задаче не удается успешно установить все необходимые блокировки, мы заставляем поток освободить все блокировки, которые он удерживает в данный момент. Однако это может создать другую проблему — активную блокировку.

Более подробно с книгой можно ознакомиться на сайте издательства.

По факту оплаты бумажной версии книги на e-mail высылается электронная книга.
Для Хаброжителей скидка 25% по купону — Конкурентность

© Habrahabr.ru