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

В этом примере показан общий метод программирования под названием совместная проверка состояния, который я использовал на протяжении всей своей карьеры для решения большинства проблем параллелизма, с которыми я сталкивался. .

Я буду использовать Java для написания решения, чтобы подчеркнуть разницу между базовой моделью многопоточности Java, основанной на оригинальном предложении Дейкстры с использованием мониторов и семафоров, и более поздней моделью POSIX. В конце статьи есть перевод на C++17, чтобы лучше оценить различия между двумя языками.

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

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

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

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

Представленная здесь техника проверки общего состояния также решает эту тонкую проблему.

Предварительное условие: понимание примитивов POSIX.

Прежде чем представить метод проверки общего состояния, важно описать обоснование примитивов POSIX, лежащих в основе его потоковой модели.

Мьютекс

mutex POSIX — это устройство синхронизации, предназначенное для внесения неатомарных изменений в (возможно) общий набор данных, чтобы любой наблюдатель выглядел атомарно.

Хотя это достигается с помощью общего механизма, предотвращающего одновременный обход определенной последовательности кода параллельными агентами, крайне важно понимать, что это не назначение мьютекса (POSIX).

Семантика мьютекса POSIX следующая:

DATASET = <a certain set of data that can be access by multiple a
agents>
DATASET is in STATE A
mutex.lock();
Move DATASET to STATE B
mutex.unlock();
DATASET is in state B
<and/or>
mutex.lock();
STATE x = STATE OF DATASET
mutex.unlock();
DATASET was (recently) in state x

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

Переменная условия

Название «условная переменная» несколько неудачно и вводит в заблуждение; его можно лучше понять с помощью следующего определения:

Переменная условия POSIX — это устройство синхронизации, используемое для ожидания возможностинахождения набора данных в определенном желаемом состоянии и/или уведомления любого заинтересованного наблюдателя об этом может так оно и есть.

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

mutex.lock();
while(DATASET is not in state A)
   condition_variable(DATASET may be in state A).wait();
... possibly move DATASET to state B ...
mutex.unlock();
<and/or>
mutex.lock();
move DATASET to state A
mutex.unlock();
condition_variable(DATASET may be in state A).notify();

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

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

Совместная государственная инспекция

Техника проверки общего состояния состоит из следующих шагов:

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

Возвращаясь к нашему примеру, мы можем спросить: какую информацию каждый философ должен знать обо всех остальных за столом?

Кормление каждого философа

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

Набор данных

Нужно ли нам отслеживать только местную ситуацию или нам нужно более широкое понимание?

Способность философа действовать зависит от того, что хотят сделать его гости, по крайней мере, если мы хотим ввести некоторую справедливость. Если гость рядом с философом уже попросил приступить к еде, это следует учесть. Это переводится на каждую тройку философов: B должен знать, что хотят делать A и C, C должен знать, что должны делать B и D, и так далее, пока мы не достигнем A, которому нужно знать, что собираются делать X и B. , где X — последний философ.

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

Короче говоря, общий набор данных включает в себя:

  • Текущий статус занят/свободен всех стиков на столе.
  • Немного информации о готовности каждого философа начать есть и, справедливости ради, порядок, в котором они поднимали руку.

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

Предикаты

Все философы должны знать, если:

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

Мы зафиксируем эту ситуацию в одном предикате с именем canEat(philosopher), который сообщит данному философу, безопасно ли продолжать.

Условия

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

Давайте обсудим это

После завершения SSI мы можем смоделировать проблему как набор объектов в нашем коде. На это есть очень важная причина:

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

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

Ортогональное объектно-ориентированное программирование

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

Тяжелые палки

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

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

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

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

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

Пассивный официант

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

Теперь, поскольку стол подчиняется философам, а не его хозяину, как официанту-диктатору, философам необходимо вызвать методы на столе, чтобы начать ожидание и взять/сложить свои палочки; это вызывает проблему цикличности, поскольку таблица должна отчитываться перед философами. С должной осторожностью это было бы хорошо для многих языков программирования, языков, но имеет тенденцию вызывать некоторые неудобства в Java. Чтобы разорвать цикличность, вместо непосредственного использования класса таблицы философы будут взаимодействовать с абстрактным интерфейсом, называемым «обеденной поверхностью».

Утилита отображения

Чтобы визуализировать ситуацию в каждый момент, этот класс выводит статус философов в виде последовательности букв; T — «думать», E — «есть» и W — «ждать/хочу есть».

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

Бегущие философы

В этом упражнении делается попытка смоделировать решение проблемы обедающих философов так, как это можно было бы реализовать в большой программе; Итак, наши философы — это абстракция для тяжеловесных агентов, имеющих свои потоки и выполняющих случайную работу, пока не придет время приобретать или освобождать общие ресурсы. В частности, они могут think (строка 19), eat (строка 24) и run (строка 29).

Посмотрите, как их основной цикл состоит всего из 5 шагов, начиная со строки 32. Они уведомят стол, когда захотят поесть; этот вызов будет заблокирован до тех пор, пока они не смогут безопасно получить свои палочки (в строке 5 и 6), и после этого они смогут использовать их как угодно в eat. Это очень важный момент, о котором я расскажу позже.

Обратите внимание на оператор catch в строке 37; это семантика Java для понимания концепции прерываемых ожиданий. Если какие-либо другие агенты, скажем, основная программа, хотят, чтобы философ завершил свой поток, он пошлет запрос на прерывание, который будет удовлетворен генерацией InterruptedException как можно скорее, обычно во время ожидания.

Стол

Таблица отвечает за отслеживание состояния общего набора данных. Как уже было сказано, мы не являемся полностью самим набором данных, но класс Table по-прежнему отвечает за изменение статуса «занят/свободен» флешек, реализует приоритетную очередь и проверяет предикат ожидания.

Есть также некоторые утилиты; конструктор помогает мне рассадить Философов и дать им доступ к палочкам (в строках 16 и 60).

Наиболее важными аспектами этого класса являются mutex в строке 11, условие mayTryToEatNow в строке 12 и связанный с ним предикат canEat в строке 70.

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

Чтобы поднять палочки, философы должны записаться в очередь ожидания (строки 32–33), а когда они подтвердят, что могут продвигаться вперед, удалить себя из очереди и фактически пометить палочки как занятые. Поскольку это изменяет структуру очереди ожидания, рекомендуется снова сигнализировать об этом условии, чтобы позволить другим ожидающим агентам проверить, находятся ли они сейчас в начале списка и готовы ли они к работе.

Обратите внимание, как организованы строки 32–41. После блокировки мьютекса общее состояние, включающее список приоритетов, можно проверить (с помощью предиката) или изменить. Если предикат не проверен, мьютекс освобождается, а вызывающий поток приостанавливается, ожидая, пока кто-нибудь уведомит, что ситуация может быть изменена и ее необходимо переоценить.

После выхода из цикла в строке 38 наблюдающий поток может быть уверен, что набор данных находится в желаемом состоянии, поэтому он может фактически выполнить желаемые изменения. Мьютекс освобождается предложением finally, которое охватывает также ранние возвраты и выбросы исключений.

Все, что необходимо знать философу для прогресса, может быть определено предикатом canEat.

  • Если мы хотим обеспечить правильность, предикат можно ограничить строкой 71: проверять, только если свободны и левый, и правый джойстики.
  • Чтобы обеспечить справедливость и отсутствие голодания, мы добавляем проверку того, что философ будет первым в списке ожидания, в строке 72.
  • Чтобы обеспечить занятость, мы можем позволить агенту продолжать работу, если оба его соседних гостя также ожидают. Это делается в строке 73, проверяя, что ровно 2 философа с соседними идентификаторами уже находятся в списке ожидания.

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

Собираем все вместе

Теперь нам нужно написать только основной класс:

Все, что вы можете съесть, без мьютекса.

Я хотел бы указать на существенное преимущество этой модели перед другими: пока философы едят, они не держат в руках примитив синхронизации. т. е. они не удерживают заблокированными мьютексы или обнуленные семафоры.

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

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

Например, философ теперь может останавливаться во время фаз мышления или приема пищи или во время еды выполнять продолжительную операцию (звонить по телефону или ходить в туалет), не ставя под угрозу стабильность и правильность остальных действий. программа.

А теперь еще сложнее! Давайте на С++.

Перевод этой программы на C++ относительно прост. Основные отличия:

  • Автоматическое управление временем существования объекта вместо использования сборщика мусора.
  • Блокировка/разблокировка мьютекса через семантику защиты (RAII).
  • Отсутствие необходимости писать блок finally для безопасной разблокировки мьютексов.
  • Отсутствие семантики interrupt для ожиданий, что подразумевает необходимость управлять «добрыми» запросами на завершение.

Последняя проблема решается путем добавления переменной в общий набор данных, которая указывает запрос на прекращение работы всех агентов как можно скорее.

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

Обратите внимание, что canEat в строке 176 также включает проверку запроса на завершение. Объект Table теперь предлагает утилиту, помогающую философам есть или думать и уважать запросы на завершение: waitFor, строка 135.

Обратите также внимание, что у нас может быть несколько условных переменных в одном и том же наборе данных: поскольку terminate является его частью, и некоторым наблюдателям может быть интересно только узнать, изменилось ли это значение, в этом случае устанавливается новая условная переменная, и используется waitFor для преждевременного прерывания ожидания.

Я хотел бы также обратить внимание читателя на общие указатели, содержащие ссылку на палочки для еды в строке 74–75, и на то, как блокировка мьютекса захватывается и снимается автоматически с помощью семантики RAII/guard, например, в строках. 142 и 197.

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

Кроме того, модель не зависит от языка программирования, парадигмы и требований к дизайну. Будь то кодирование на Java, C, C#, C++, C++ и т. д. ; хорошо ли набор данных инкапсулирован в ООП-класс или распределен по нескольким объектам; Независимо от того, является ли общий набор данных просто коммуникационным буфером или списком сложных ресурсов, модель обеспечивает простое и элегантное решение большинства проблем параллелизма и основу для построения более сложных моделей параллельного программирования.