Параллельное программирование *

В статье сформулированы некоторые проблемы информационных технологий (ИТ) и рассматривается подход к их решению, который может быть интересен разработчикам архитектур вычислительных систем и языков программирования, а также бизнесу в сфере ИТ. Но все они, исключая некоторых, вряд ли полагают, что тут есть проблемы, по крайней мере в том, о чём повествуется в этой статье, тем более что отрасль развивается более чем. Но, хотя некоторые проблемы и не осознаются, однако решать их «ползучим образом» уже давно и постепенно приходится. А можно бы сэкономить силы и средства, если решать их осознанно сполна и сразу.

Ни экономика, ни социальные коммуникации уже невозможны без использования развитых ИТ. Вот и рассмотрим, почему используемые сейчас технологии далее непригодны и на что их следует заменить. Автор будет признателен за конструктивное квалифицированное обсуждение и надеется узнать полезную информацию о современных решениях затронутых «проблем».

^{Theory is when you know everything but nothing works.
Practice is when everything works but no one knows why.
In distributed systems, theory and practice are combined:
nothing works and no one knows why.}

Чтобы доказать, что шутка в эпиграфе — абсолютная глупость, мы уже в третий раз проводим SPTDC (school on practice and theory of distributed computing). Об истории школы, её сооснователях Петре Кузнецове и Виталии Аксёнове, а также об участии JUG Ru Group в организации SPTDC мы уже рассказывали на Хабре. Поэтому сегодня — о школе в 2020 году, о лекциях и лекторах, а также об отличиях школы от конференции.

Школа SPTDC пройдёт с 6 по 9 июля 2020 года онлайн.

Все лекции будут на английском языке. Основные темы лекций: persistent concurrent computing, cryptographic tools for distributed systems, formal methods for verifying consensus protocols, consistency in large-scale systems, distributed machine learning.


Сразу догадались, в каком воинском звании персонажи на картинке? Я вас обожаю.

Здравствуйте, коллеги.

В рамках проработки темы С++20 нам в свое время попалась уже довольно старенькая (сентябрь 2018) статья из хаброблога «Яндекса», которая называется "Готовимся к С++20. Coroutines TS на реальном примере". Заканчивается она следующей весьма выразительной голосовалкой:



«Почему бы и нет», — решили мы и перевели статью Давида Пиларски (Dawid Pilarski) под названием «Coroutines introduction». Статья вышла чуть более года назад, но, надеемся, все равно покажется вам очень интересной.

18 апреля 2020 в Санкт-Петербурге и 16 мая в Москве пройдёт седьмая мини-конференция по платформе .NET CLRium #7. В этот раз мы будем и говорить и заниматься практикой многопоточного кода. Как и в прошлый раз, все доклады будут придерживаться единой линии повествования. В шестом CLRium мы поднаторели в теории и узнали много нового относительно планировщика потоков, блокировок и неблокирующих алгоритмов. В платформе .NET изучили контексты синхронизации, планировщики задач, как работают сами задачи, async/await и типичные ошибки при его использовании… Мы изучили вообще всё, чтобы уверенно начать заниматься практическими задачами.

В CLRium #7 мы перейдём к практике. Наша программа, наконец, окончательно готова: мы разработали матрицу докладов, которые построены так, что последующие доклады логически вытекают из предыдущих. А кроме самих докладов по желанию будет дана практическая работа на дом, в рамках которой вы приобретете опыт работы над задачами совместно: группами по несколько человек (контролируемых координатором).

В прошлом году в Санкт-Петербурге прошла первая конференция Hydra, посвящённая параллельным и распределённым системам. С докладами выступали лауреаты премии Дейкстры и премии Тьюринга (Лесли Лэмпорт, Морис Херлихи и Майкл Скотт), создатели компиляторов и языков программирования (C++, Go, Java, Kotlin), разработчики распределённых баз данных (Cassandra, CosmosDB, Yandex Database), а также создатели и исследователи алгоритмов и структур данных (CRDT, Paxos, wait-free data structures). В общем, на этом месте уже можно брать отпуск, сворачивать окно IDE, открывать плейлист на YouTube с лучшими докладами Hydra 2019 — и пусть task scheduler немного подождёт.

В общем, никогда такой конференции не было, и вот опять она случится. Снова с докладами на английском, потому что нет лучше языка, чтобы говорить о параллельных и распределённых вычислениях. Снова летом, 6-9 июля, потому что спикеры успевают исследовать и преподавать, например, в университетах Кембриджа, Рочестера и Санкт-Петербурга, и другое время года не для них.

На новой Гидре — более замысловатая программа, новые спикеры вместе с героями прошлого года, а также уже знакомое ощущение распределённого между участниками восторга от параллельного хардкора в трёх залах.

1. Вновь о корутинах

В предыдущей моей статье, уважаемый Хабр, я только лишь прикоснулся к проблемам познания современного программирования. Последовавшая дискуссия только подтвердила спонтанно возникшие опасения: источником разногласий сразу же стали пресловутые «теоретические основы». То, что их (разногласий) могло бы не быть или они носили бы другой характер основную массу «настоящих» программистов похоже не тревожит. Более того, возможно, особо и не интересует, т.к. у программистов стимулируется в основном один интерес — код, код и только код. Ну, почти «как доктор прописал» [1]…

Затрагивая в своих статья и комментариях тему корутин, я ни сном ни духом не предполагал насколько они в «нонешнем» тренде. Поражали, правда, «минусовки» моих комментов по поводу и без. За что, мол, ребята-программисты? Однако, как мне представляется, все прояснилось после прочтения статьи о только что утвержденном С++20 и перспективах его дальнейшего развития [2]. К моему изумлению, выяснилось, что корутины находятся в первых рядах настоящих и будущих новшеств моего любимого С++ (см. также библиотеку CppCoro).

Ну, скажите, можно ли серьезно и/или спокойно воспринимать чела, который, похоже, возомнил себя невесть кем? Попал, что называется! :(

Ниже представлена не простая расшифровка доклада с семинара CLRium, а переработанная версия для книги .NET Platform Architecture. Той её части, что относится к потокам.

Потоки и планирование потоков

Что такое поток? Давайте дадим краткое определение. По своей сути поток это:

• Средство параллельного относительно других потоков исполнения кода;
• Имеющего общий доступ ко всем ресурсам процесса.

Очень часто часто слышишь такое мнение, что потоки в .NET — они какие-то абсолютно свои. И наши .NET потоки являются чем-то более облегчённым чем есть в Windows. Но на самом деле потоки в .NET являются самыми обычными потоками Windows (хоть Windows thread id и скрыто так, что сложно достать). И если Вас удивляет, почему я буду рассказывать не-.NET вещи в хабе .NET, скажу вам так: если нет понимания этого уровня, можно забыть о хорошем понимании того, как и почему именно так работает код. Почему мы должны ставить volatile, использовать Interlocked и SpinWait. Дальше обычного lock дело не уйдёт. И очень даже зря.

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

Задача процессора — просто исполнять код. Поэтому с точки зрения процессора есть только один поток: последовательное исполнение команд. А задача операционной системы каким-либо образом менять поток т.о. чтобы эмулировать несколько потоков.

Прим. перев.: Содержимое этой статьи не совсем типично для нашего блога. Однако, как многим известно, etcd находится в самом сердце Kubernetes, из-за чего данное исследование, проведённое независимым консультантом в области надёжности, оказалось интересным и в среде инженеров, эксплуатирующих данную систему. Кроме того, оно интересно в разрезе того, как Open Source-проекты, уже зарекомендовавшие себя в production, совершенствуются даже на таком, весьма «низком», уровне.



Хранилище пар «ключ-значение» (KV) etcd представляет собой распределённую базу данных, основанную на алгоритме консенсуса Raft. В ходе анализа, проведенного в 2014 году, мы обнаружили, что etcd 0.4.1 по умолчанию была подвержена так называемым stale reads (операциям чтения, возвращающим старое, неактуальное значение из-за запаздывания синхронизации — прим. перев.). Мы решили вернуться к etcd (в этот раз — к версии 3.4.3), чтобы снова детально оценить ее потенциал в области надежности и безопасности.

1. Введение

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

1. Введение. Конкурентный корутинизм

Предыдущие статьи на тему автоматного программирования были всего лишь «цветочками». «Ягодкой» автоматного программирования, т.е. ради чего нужно им заниматься, является модель параллельных вычислений на базе модели конечных автоматов. Итак, поехали…

Стандарт С++ включил в свой состав долгожданную поддержку многопоточности [1]. Но не будем ни восхищаться этим, ни критиковать сей факт, т.к. работа с потоками отягощена таким множеством условий, оговорок и особенностей, что без реальных примеров, выявляющих проблемы многопоточности, обсуждение многопоточного программирования будет не только поспешным, но и достаточно предвзятым. Поэтому далее в основном не о потоках, а об автоматах, имея в виду, конечно, и первые.

---

Преамбула

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

В самый канун Нового года увидела свет новая версия главного инструмента Intel для разработчиков — Intel Parallel Studio XE 2020. Давайте воспользуемся этим поводом и посмотрим, чем живет сейчас всем известная «студия» и в какую сторону развивается.

В мире JVM про корутины знают в большей степени благодаря языку Kotlin и Project Loom. Хорошего описания принципа работы котлиновских корутин я не видел, а код библиотеки kotlin-coroutines совершенно не понятен неподготовленному человеку. По моему опыту, большинство людей знает о корутинах только то, что это "облегченные потоки", и что в котлине они работают через умную генерацию байткода. Таким был и я до недавнего времени. И мне пришла в голову идея, что раз корутины могут быть реализованы в байткоде, то почему бы не реализовать их в java. Из этой идеи, впоследствии, появилась небольшая и достаточно простая библиотека, в устройстве которой, я надеюсь, может разобраться практически любой разработчик. Подробности под катом.

Перевод главы 13 Параллелизм
из книги ‘Expert Python Programming’,
Second Edition
Michał Jaworski & Tarek Ziadé, 2016

Асинхронное программирование

В последние годы асинхронное программирование приобрело большую популярность. Python 3.5 наконец-то получил некоторые синтаксические функции, закрепляющие концепции асинхронных решений. Но это не значит, что асинхронное программирование стало возможным только начиная с Python 3.5. Многие библиотеки и фреймворки были предоставлены намного раньше, и большинство из них имеют происхождение в старых версиях Python 2. Существует даже целая альтернативная реализация Python, называемая Stackless (см. Главу 1 «Текущее состояние Python»), которая сосредоточена на этом едином подходе программирования. Для некоторых решений, таких как Twisted, Tornado или Eventlet, до сих пор существуют активные сообщества, и их действительно стоит знать. В любом случае, начиная с Python 3.5, асинхронное программирование стало проще, чем когда-либо прежде. Таким образом, ожидается, что его встроенные асинхронные функции заменят большую часть старых инструментов, или внешние проекты постепенно превратятся в своего рода высокоуровневые фреймворки, основанные на встроенных в Python.

Машина Тьюринга, как модель автоматных программ

1. Введение

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

Далее мы рассмотрим SWITCH-технологию проектирования автоматных программ, в которой с подобными процессами сталкиваешься сплошь и рядом. С одной стороны, она так изменила модель конечного автомата, что фактически вывела ее за рамки теории автоматов. А, с другой стороны, вводит в программирование понятия, которые с трудом воспринимаются программистами, а, порой, просто являются лишними, т.к. существуют более привычные аналоги из теории программ и практики программирования.

За основу обсуждения проблем автоматного программирования возьмем недавнюю лекцию Шалыто А.А. [1] и его «программные» статьи к определению парадигмы автоматного программирования [2, 3].

Каждый язык, поддерживающий параллельные (конкурентные, асинхронные) вычисления, нуждается в способе запуска кода параллельно. Вот примеры из разных API:

go myfunc();                                // Golang

pthread_create(&thread_id, NULL, &myfunc);  /* C with POSIX threads */

spawn(modulename, myfuncname, [])           % Erlang

threading.Thread(target=myfunc).start()     # Python with threads

asyncio.create_task(myfunc())               # Python with asyncio

Есть много вариантов нотации и терминологии, но одна семантика — запустить myfunc параллельно основной программе и продолжить родительский поток выполнения (англ. "Control Flow")

Многоядерные процессоры — обыденность. Рано или поздно любому программисту-практику придется зайти в лабиринт многопоточного программирования и встретиться с населяющими его «чудовищами». Поговорим о том, с чего начать такой путь и какие инструменты и подходы помогут выйти победителем. Я выступил с этим докладом перед будущими участниками круглогодичной стажировки Яндекса.


— Меня зовут Сева Миньков. Я работаю в отделе облачной инфраструктуры поискового департамента. Занимаюсь в основном бэкендом. Пишу на разных языках, но чаще всего это Java и языки, запускаемые на Java Virtual Machine (JVM).

Сегодня коротко расскажу о том, как я реализовывал семафор на основании объекта синхронизации «Событие».

Сначала пройдусь по определениям.

1. Что такое синхронизация и зачем она нужна?

Очевидно, что набор действий мы можем выполнять несколькими способами. Самые простые — последовательно и параллельно. Параллельности выполнения определенных действий можно достигнуть за счет запуска различных потоков (threads). Идея простая: назначаем каждому потоку какое-то элементарное (или не очень) действие и запускаем их в определенном порядке. Вообще говоря, запустить мы их можем и все одновременно — выигрыш по времени мы, конечно, получим. Это понятно: одно дело вывести 10 000 слов одно за другим, а другое дело одновременно выводить, например, 100 слов. 100-кратный выигрыш по времени (плюс-минус, без учета задержек и проч.). Но исходная задача может предполагать строгую последовательность действий.

Например:

• Открыть файл
• Записать текст в файл
• Закрыть файл

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

• Сгенерировать три последовательности случайных чисел
• Последовательно вывести их на экран

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

В общем, задачи на параллелизм могут быть самые разные и для синхронизации потоков нужен какой-то инструмент.

"Цветорасширитель для ZX-Spectrum" — так называлась статья, опубликованная в эхе fido7.zx.spectrum 3 августа 1997 года. Статья описывала идею решения одной из главных проблем платформы ZX-Spectrum — конфликта атрибутов (attribute clash). Публикация вызвала в то время определенный интерес, про технические детали и историю вопроса я и хотел бы рассказать.

Не буду залезать глубоко в технические подробности и просто структурно опишу идею и решение.

Совсем скоро, 29-30 ноября в Санкт-Петербурге и 06-07 декабря — в Москве мы запустим шестой семинар по .NET. На этот раз — по теме многопоточки и конкурентности. Мы уже писали об этом пару раз на Хабре, но сегодня есть отдельный повод для этого: на семинаре настоящий эксклюзив. Будет описана работа гибридного примитива синхронизации: Monitor. Да, всем привычная вещица достойна отдельного доклада. Ведь он в своей работе учитывает и частоту процессора и количество ядер, учитывает lock convoy/starvation и вообще, очень сложен.

А в конце статьи развлечения ради предложу пройти парочку QUIZов по многопоточке.