В Кремниевой долине есть один весьма своеобразный ресторанчик быстрого питания. Он работает круглосуточно и принимает по одному гостю за раз, ведь там всего один стол. Зато гамбургеры — просто потрясающие. Приходя, вы ждёте, пока стол не освободится. Затем вас приглашают, и, поскольку это Америка, вам задают бесконечную уйму вопросов о том, как готовить и подавать гамбургер.
Но не будем сегодня толковать о кулинарных изысках. В таких ресторанах нам интереснее система очередей. Если вам повезло прийти в ресторан, когда стол свободен и очереди нет, вас сразу посадят за столик. В противном случае вам вручат зуммер (таких «пищалок» у них великое множество!). С таким зуммером вы сможете спокойно бродить по округе, пока он не подаст сигнал. Тот, кто обслуживает гостей, следит, чтобы это делалось в порядке прибытия. Когда подойдёт ваша очередь, он отправит вам сигнал, вы вернётесь в ресторан, и вам найдут место. Продолжение — к старту нашего курса по Fullstack-разработке на Python.
Если вы к тому времени уже раздумали заказывать, зуммер можно вернуть. Это обычное дело: его заберут, глазом не моргнув. Даже если сигнал уже сработал, за стол пригласят следующего гостя. Если, конечно, вы не один в очереди. Вежливый гость не унесёт зуммер далеко, а честный управляющий не посадит других людей за столик вне очереди, даже если вы задержались.
Всё это — описание работы класса Lock. Прибытие гостя соответствует вызову метода acquire(), а его уход — вызову метода release(). Отменить свой заказ — значит отменить acquire() в процессе ожидания. Это можно сделать до или после срабатывания звукового сигнала, то есть операции отменяются до или после активации вызова со стороны Lock (но до возврата из метода acquire()).
Ресторанный бизнес можно расширить: нанять больше поваров и поставить больше столов. Но управляющий так и останется один, и суть его работы не изменится. Но поскольку теперь гостей можно размещать одновременно, вместо простой блокировки классом Lock теперь придётся использовать класс Semaphore.
Оказывается, что реализовывать примитивы синхронизации очень непросто. В случае библиотеки asyncio это несколько удивляет, ведь за раз можно выполнить только одну задачу, а переключение задач происходит только в await. С прошлого года справедливость распределения ресурсов (равнодоступность), а также корректность, семантика и производительность данного метода рассматриваются весьма критически. Три последних жалобы получены только в прошлом месяце. Мне, последнему уцелевшему на поле боя с метками эксперту по asyncio, пришлось спешно осмысливать идею семафоров.
Сравнение с рестораном пришлось очень кстати. Например, оно показывает разницу между числом свободных столов и числом гостей, столик которым можно найти сразу. Эта разница равна числу людей, которые ещё не вернули зуммеры управляющему.
Есть одна проблема с равнодоступностью. Если задача запрашивает release, а затем сразу пытается запросить acquire, она подвешивает другие задачи. Как будто уходящий гость вдруг разворачивается и снова садится за стол, опережая людей в очереди.
В библиотеке есть и такой баг — сохранение неправильного состояния Lock при отмене вызова acquire(). Как будто гость вернул сработавший зуммер, но отказался садиться за стол, чем ввёл управляющего в ступор.
Сравнение с рестораном помогает не везде: с последовательностью событий при отмене в asyncio всё сложно. В Python 3.11 мы дополнительно нагрузили операцию отмены двумя новыми асинхронными менеджерами контекста:
- Класс TaskGroup управляет группой родственных задач. При сбое одной из таких задач остальные отменяются, а менеджер контекста ожидает выхода всех задач.
- Функция timeout() задаёт время ожидания. По истечении этого времени задача отменяется.
И вот главная трудность отмены:
- Футура (объект класса
[Future](https://docs.python.org/3.12/library/asyncio-future.html#asyncio.Future)) может быть отменена в процессе ожидания. Тогда операцияawaitслетает и поднимает исключение CancelledError. - Но если ожидание футуры возвращает
CancelledError, нельзя полагать, что сама футура отменена! При этом футура уже может быть помечена, как имеющая результат (что уже не даёт её отменить), а задача может быть помечена как готовая к исполнению (runnable), однако другая задача (тоже готовая к исполнению) запустится первой и отменит эту. Спасибо пользователю Cyker Way за указание на этот крайний случай.
Полезно представлять, что у Future может быть 4 состояния:
- ожидание;
- готово, есть результат;
- готово, есть исключение;
- готово, но отменено.
Из состояния ожидания Future может перейти в любое другое состояние, после чего состояние останется неизменным. (вставьте здесь какую-нибудь симпатичную диаграмму состояний :-)).
Семафор (Semaphore) обслуживает ожидающие задачи в порядке поступления (FIFO). У него нет состояния исключения, но три других состояния у него присутствуют:
- ожидание: гость с ещё не сработавшим зуммером;
- есть результат: на зуммер гостя пришёл сигнал;
- отмена: гость сдал зуммер до получения сигнала.
В целях равнодоступности функция acquire() должна добавлять в конец очереди новый объект Future при каждой обнаруженной блокировке семафора. При этом крайняя слева (самая старая) футура должна маркироваться как содержащая результат при вызове функции release(), пока очередь не окажется пустой. Ошибка равнодоступности возникает, если acquire() избирает кратчайший путь при ненулевом level семафора (числе свободных столов). Этого не следует делать, когда в очереди есть футуры. Иными словами, мы иногда ошибочно усаживали вновь прибывших за свободные столики, пока другие ждали в очереди.
В чём, по-вашему, причина бага отмены? Я имею в виду сценарий, в котором у футуры есть готовый результат (зуммер сработал), но задача, ожидающая эту футуру, отменяется (гость отказался садиться).
Я с трудом представил себе состояние семафора с переменной level и очередью ожидающих футур FIFO. Непросто было и определить функцию locked(). Если бы level была общедоступной, пришлось бы повозиться и с её семантикой. В конце концов, я пришёл к следующим определениям:
- W — список ожидающих футур: [f для f в очереди
queue, у которых не вызвана f.done()] - R — список готовых футур, имеющих результат: [f для f в queue, у которых вызвана f.done(), но не f.cancelled()]
- C — список отменённых футур: [f для f в queue, у которых вызвана f.cancelled()]
А вот несколько инвариантов на их основе:
set(W + R + C) == set(queue)— все ожидающие, готовые и отменённые футуры.level >= len(R)— свободных столиков у нас должно быть не меньше, чем сработавших зуммеров в руках у гостей.- определение
locked()как(len(W) > 0илиlen(R) > 0илиlevel == 0) — чтобы сразу усадить гостя за стол, нужно, чтобы не было гостей с зуммерами, которые ждут сигнала; не было гостей со сработавшими зуммерами; хотя бы один стол был свободен.
В конце статьи даю вам ссылку на код текущей реализации такого семафора.
А мы научим работать с Python, чтобы вы прокачали карьеру или стали востребованным IT-специалистом:
Чтобы посмотреть все курсы, кликните по баннеру:
Data Science и Machine Learning
- Профессия Data Scientist
- Профессия Data Analyst
- Курс «Математика для Data Science»
- Курс «Математика и Machine Learning для Data Science»
- Курс по Data Engineering
- Курс «Machine Learning и Deep Learning»
- Курс по Machine Learning
Python, веб-разработка
- Профессия Fullstack-разработчик на Python
- Курс «Python для веб-разработки»
- Профессия Frontend-разработчик
- Профессия Веб-разработчик
Мобильная разработка
Java и C#
- Профессия Java-разработчик
- Профессия QA-инженер на JAVA
- Профессия C#-разработчик
- Профессия Разработчик игр на Unity
От основ — в глубину
А также
