Войти
Coroutines - это компоненты компьютерной программы, которые обобщают подпрограммы для non -вытесняющая многозадачность, позволяющая приостанавливать и возобновлять выполнение. Сопрограммы хорошо подходят для реализации знакомых программных компонентов, таких как совместные задачи, исключения, циклы событий, итераторы, бесконечные перечисляет и трубы.
Согласно Дональду Кнуту, Мелвин Конвей ввел термин сопрограмма в 1958 году, когда применил его к построению сборки программа. Первое опубликованное объяснение сопрограммы появилось позже, в 1963 году.
Подпрограммы - это особые случаи сопрограмм. Когда подпрограммы вызываются, выполнение начинается с самого начала, а после выхода из подпрограммы оно завершается; экземпляр подпрограммы возвращается только один раз и не сохраняет состояние между вызовами. Напротив, сопрограммы могут завершиться путем вызова других сопрограмм, которые позже могут вернуться в точку, в которой они были вызваны в исходной сопрограмме; с точки зрения сопрограммы, это не выход, а вызов другой сопрограммы. Таким образом, экземпляр сопрограммы сохраняет состояние и варьируется между вызовами; одновременно может быть несколько экземпляров данной сопрограммы. Разница между вызовом другой сопрограммы посредством «уступки» ей и простым вызовом другой подпрограммы (которая затем также вернется в исходную точку) состоит в том, что связь между двумя сопрограммами, которые уступают дорогу каждой другой - не вызывающий-вызываемый, а симметричный.
Любую подпрограмму можно преобразовать в сопрограмму, которая не вызывает yield.
Вот простой пример того, как могут быть полезны сопрограммы. Предположим, у вас есть отношения потребитель-производитель, в которых одна процедура создает элементы и добавляет их в очередь, а другая удаляет элементы из очереди и использует их. Из соображений эффективности вы хотите добавлять и удалять сразу несколько элементов. Код может выглядеть так:
var q: = new queue сопрограмма произвести loopпока q не заполнено, создать несколько новых элементов добавить элементы для q дают для использования сопрограммы потребляют loopпока q не пусто удалить некоторые элементы из q использовать элементы yield для создания
Затем очередь полностью заполняется или опорожняется перед передачей управления другой сопрограмме с помощью команды yield. Дальнейшие вызовы сопрограмм начинаются сразу после выхода во внешнем цикле сопрограмм.
Хотя этот пример часто используется как введение в многопоточность, для этого не нужны два потока: оператор yield может быть реализован путем перехода непосредственно из одной процедуры в другую.
Сопрограммы очень похожи на потоки. Однако сопрограммы совместно многозадачны, тогда как потоки обычно преимущественно многозадачны. Это означает, что сопрограммы обеспечивают параллелизм, но не параллелизм. Преимущества сопрограмм перед потоками заключаются в том, что они могут использоваться в контексте жесткого реального времени (переключение между сопрограммами не требует каких-либо системных вызовов или любых блокирует вызовы вообще), нет необходимости в примитивах синхронизации, таких как мьютексы, семафоры и т. д. для защиты критических секций, и нет необходимости в поддержке из операционной системы.
Можно реализовать сопрограммы с использованием заранее запланированных потоков таким способом, который будет прозрачен для вызывающего кода, но некоторые из преимуществ (в частности, пригодность для работы в жестком реальном времени и относительная дешевизна переключения между их) будут потеряны.
Генераторы, также известные как полупрограммы, являются подмножеством сопрограмм. В частности, в то время как оба могут давать результат несколько раз, приостанавливая их выполнение и разрешая повторный вход в нескольких точках входа, они различаются способностью сопрограмм контролировать, где выполнение продолжается сразу после их выполнения, в то время как генераторы не могут, вместо этого передавая управление обратно вызывающей стороне генератора.. То есть, поскольку генераторы в основном используются для упрощения записи итераторов, оператор yieldв генераторе не определяет сопрограмму, к которой нужно перейти, а скорее передает значение обратно в родительский распорядок.
Тем не менее, все еще можно реализовать сопрограммы поверх средства генератора с помощью подпрограммы диспетчера верхнего уровня (по сути, трамплина ), которая явно передает управление дочернему элементу генераторы, идентифицированные токенами, переданными обратно от генераторов:
var q: = новая очередь
генератор производят loopпока q не заполнен новые элементы добавляют элементы в q yield потребляют
генератор потребляют loopпока q не пусто удалить некоторые элементы из q использовать элементы yield произвести
подпрограмму диспетчер var d: = новый словарь (генератор → итератор ) d [произвести]: = start произвести d [потреблять]: = start потреблять переменную ток: = производить цикл ток: = следующий d [текущий]
Число реализаций сопрограмм для языков с поддержкой генератора, но без собственных сопрограмм (например, Python до 2.5), использующих эту или аналогичную модель.
Использование сопрограмм для конечных автоматов или параллелизма аналогично использованию взаимной рекурсии с хвостовыми вызовами, поскольку в обоих случаях управлять изменениями в другой из набора подпрограмм. Однако сопрограммы более гибкие и в целом более эффективные. Поскольку сопрограммы выдают результат, а не возвращают, а затем возобновляют выполнение, а не перезапускаются с самого начала, они могут удерживать состояние, обе переменные (как в случае закрытия) и точку выполнения, и выходы не ограничиваются нахождением в хвостовой позиции; взаимно рекурсивные подпрограммы должны либо использовать общие переменные, либо передавать состояние в качестве параметров. Кроме того, каждый взаимно рекурсивный вызов подпрограммы требует нового кадра стека (если не реализовано устранение хвостового вызова ), в то время как передача управления между сопрограммами использует существующие контексты и может быть реализована просто путем перехода.
Сопрограммы полезны для реализации следующего:
Сопрограммы возникли как метод языка ассемблера, но поддерживаются некоторыми языками программирования высокого уровня. Ранние примеры включают Simula, Smalltalk и Modula-2. Более свежие примеры: Ruby, Lua, Julia и Go.
Поскольку продолжения могут использоваться для реализации сопрограмм, поддерживающие их языки программирования также могут довольно легко поддерживать сопрограммы.
По состоянию на 2003 год многие из самых популярных языков программирования, включая C и его производные, не имеют прямой поддержки сопрограмм в языке или их стандартных библиотеках. (Это в значительной степени из-за ограничений реализации подпрограммы на основе стека.) Исключением является библиотека C ++ Boost.Context, часть библиотек boost, который поддерживает подкачку контекста в ARM, MIPS, PowerPC, SPARC и x86 в POSIX, Mac OS X и Windows. Сопрограммы могут быть построены на Boost.Context.
В ситуациях, когда сопрограмма была бы естественной реализацией механизма, но недоступна, типичным ответом является использование замыкания - подпрограммы с переменными состояния (static переменные, часто логические флаги) для поддержания внутреннего состояния между вызовами и для передачи управления в нужную точку. Условные выражения в коде приводят к выполнению различных путей кода при последовательных вызовах на основе значений переменных состояния. Другой типичный ответ - реализовать явный конечный автомат в форме большого и сложного оператора switch или с помощью оператора goto, в частности, вычисляемого goto. Такие реализации считаются сложными для понимания и поддержки, а также побуждают к поддержке сопрограмм.
Потоки и, в меньшей степени, волокна, сегодня являются альтернативой сопрограммам в средах массового программирования. Потоки предоставляют средства для управления совместным взаимодействием в реальном времени при одновременном выполнении фрагментов кода. Потоки широко доступны в средах, поддерживающих C (и изначально поддерживаются на многих других современных языках), знакомы многим программистам и обычно хорошо реализованы, хорошо документированы и хорошо поддерживаются. Однако, поскольку они решают большую и сложную проблему, они включают в себя множество мощных и сложных средств и, соответственно, требуют сложного обучения. Таким образом, когда все, что нужно - это сопрограмма, использование потока может быть излишним.
Одно важное различие между потоками и сопрограммами заключается в том, что потоки обычно планируются с приоритетом, а сопрограммы - нет. Поскольку потоки могут быть перепланированы в любой момент и могут выполняться одновременно, программы, использующие потоки, должны быть осторожны с блокировкой. Напротив, поскольку сопрограммы могут быть перепланированы только в определенных точках программы и не выполняются одновременно, программы, использующие сопрограммы, часто могут полностью избежать блокировки. (Это свойство также упоминается как преимущество управляемого событиями или асинхронного программирования.)
Поскольку волокна планируются совместно, они обеспечивают идеальную основу для реализации сопрограмм, описанных выше. Однако системная поддержка волокон часто отсутствует по сравнению с поддержкой потоков.
Чтобы реализовать сопрограммы общего назначения, необходимо получить второй стек вызовов , что является функцией, не поддерживаемой напрямую C язык. Надежный (хотя и зависящий от платформы) способ добиться этого - использовать небольшое количество встроенной сборки для явного управления указателем стека во время первоначального создания сопрограммы. Это подход, рекомендованный Томом Даффом при обсуждении его относительных достоинств по сравнению с методом, используемым Protothreads. На платформах, которые предоставляют системный вызов POSIX, второй стек вызовов может быть получен путем вызова функции трамплина из обработчика сигналов для достижения той же цели в портативном C за счет некоторой дополнительной сложности. Библиотеки C, соответствующие POSIX или Single Unix Specification (SUSv3), предоставляли такие подпрограммы, как getcontext, setcontext, makecontext и swapcontext, но эти функции были объявлены устаревшими в POSIX 1.2008.
После получения второго стека вызовов одним из методов, перечисленных выше, функции setjmp и longjmp в стандартной библиотеке C могут быть используется для реализации переключений между сопрограммами. Эти функции сохраняют и восстанавливают, соответственно, указатель стека, программный счетчик, сохраненные вызываемым пользователем регистры и любое другое внутреннее состояние, требуемое ABI, так что возврат к сопрограмме после уступки восстанавливает все состояние, которое будет восстановлено при возврате из вызова функции. Минималистские реализации, которые не сочетаются с функциями setjmp и longjmp, могут достичь того же результата с помощью небольшого блока встроенной сборки, который меняет местами просто указатель стека и счетчик программы, и clobbers все остальные регистры. Это может быть значительно быстрее, поскольку setjmp и longjmp должны консервативно хранить все регистры, которые могут использоваться в соответствии с ABI, тогда как метод clobber позволяет компилятору сохранять (путем передачи в стек) только то, что он знает, что действительно используется.
Из-за отсутствия прямой языковой поддержки многие авторы написали свои собственные библиотеки для сопрограмм, которые скрывают вышеуказанные детали. Библиотека libtask Рассса Кокса - хороший пример этого жанра. Он использует контекстные функции, если они предоставлены встроенной библиотекой C; в противном случае он предоставляет свои собственные реализации для ARM, PowerPC, Sparc и x86. Другие известные реализации включают libpcl, coro, lthread, libCoroutine, libconcurrency, libcoro, ribs2, libdill., Libaco и libco.
В дополнение к общему подходу, описанному выше, было предпринято несколько попыток приблизить сопрограммы на C с комбинациями подпрограмм и макросов. Вклад Саймона Тэтхэма, основанный на устройстве Даффа, является ярким примером этого жанра и является основой для Protothreads и подобных реализаций. В дополнение к возражениям Даффа, собственные комментарии Татхама дают откровенную оценку ограничений этого подхода: «Насколько я знаю, это худшая часть взлома C, когда-либо встречавшаяся в серьезном производственном коде». Основные недостатки этого приближения заключаются в том, что при отсутствии поддержки отдельного кадра стека для каждой сопрограммы локальные переменные не сохраняются при выходе из функции, невозможно иметь несколько записей в функции, и управление может быть получено только из подпрограмма верхнего уровня.
C # 5.0 включает поддержку синтаксиса await.
Cloroutine - это сторонняя библиотека, обеспечивающая поддержку бесстековых сопрограмм в Clojure. Он реализован как макрос, статически разделяющий произвольный блок кода на произвольные вызовы var и выдающий сопрограмму как функцию с отслеживанием состояния.
D реализуют сопрограммы в качестве стандартного библиотечного класса Fiber Генератор упрощает отображение функции волокна в качестве входного диапазона, делая любое волокно совместимым с существующими алгоритмами диапазонов.
Есть несколько реализаций для сопрограмм в Java. Несмотря на ограничения, налагаемые абстракциями Java, JVM не исключает такой возможности. Используются четыре общих метода, но два нарушают переносимость байт-кода между совместимыми со стандартами JVM.
Kotlin реализует сопрограммы как часть собственной библиотеки.
Modula-2, как определено Вирт реализует сопрограммы как часть стандартной библиотеки SYSTEM.
Процедура NEWPROCESS () заполняет контекст с учетом блока кода и пространства для стека в качестве параметров, а процедура TRANSFER () передает управление сопрограмме с учетом контекста сопрограммы в качестве параметра.
Mono Common Language Runtime поддерживает продолжения, из которых могут быть построены сопрограммы.
Во время разработки .NET Framework 2.0 Microsoft расширила дизайн Common Language Runtime (CLR) хостинговые API для обработки планирования на основе волокна с прицелом на его использование в режиме волокна для сервера SQL. Перед выпуском поддержка перехвата переключения задач ICLRTask :: SwitchOut была удалена из-за нехватки времени. Следовательно, использование API-интерфейса волокна для переключения задач в настоящее время не является приемлемым вариантом в.NET Framework.
Сопрограммы изначально реализованы во всех бэкэндах Raku.
Существует библиотека для Rust, которая предоставляет сопрограммы. Генераторы - это экспериментальная функция, доступная в nightly rust, которая обеспечивает реализацию сопрограмм с async / await.
Coroutines Scala - это реализация сопрограмм для Scala. Эта реализация представляет собой расширение уровня библиотеки, которое использует макросистему Scala для статического преобразования разделов программы в объекты сопрограмм. Таким образом, эта реализация не требует изменений в JVM, поэтому она полностью переносима между различными JVM и работает с альтернативными серверными модулями Scala, такими как Scala.js, который компилируется в JavaScript.
Coroutines Scala полагаются на макрос coroutine, который преобразует обычный блок кода в определение сопрограммы. Такое определение сопрограммы может быть вызвано с помощью операции call, которая создает экземпляр кадра сопрограммы. Кадр сопрограммы может быть возобновлен с помощью метода resume, который возобновляет выполнение тела сопрограммы до достижения ключевого слова yieldval, которое приостанавливает кадр сопрограммы. Scala Coroutines также предоставляют метод snapshot, который эффективно дублирует сопрограмму. Подробное описание сопрограмм Scala со снимками состояния появилось на ECOOP 2018 вместе с их формальной моделью.
, поскольку схема обеспечивает полную поддержку для продолжений реализация сопрограмм почти тривиальна, требуя только поддержки очереди продолжений.
Поскольку в большинстве сред Smalltalk стек исполнения является первоклассным, сопрограммы могут быть реализованы без дополнительной библиотеки или поддержки виртуальных машин.
Начиная с версии 8.6, Инструмент Command Language поддерживает сопрограммы на основном языке.
Vala реализует встроенную поддержку сопрограмм. Они предназначены для использования с основным циклом Gtk, но могут использоваться и отдельно, если позаботиться о том, чтобы конечный обратный вызов никогда не приходился вызывать перед выполнением хотя бы одного yield.
Машинно-зависимые языки ассемблера часто предоставляют прямые методы для выполнения сопрограмм. Например, в MACRO-11, ассемблере семейства миникомпьютеров PDP-11, переключение «классической» сопрограммы осуществляется инструкцией «JSR PC, @ (SP) + ", который переходит к адресу, извлеченному из стека, и помещает текущий (то есть, адрес следующей ) инструкции в стек. На VAXen (в Macro-32 ) сопоставимая инструкция - «JSB @ (SP) +». Даже на Motorola 6809 есть инструкция «JSR [, S ++]»; обратите внимание на "++", так как 2 байта (адреса) выталкиваются из стека. Эта инструкция часто используется в (стандартном) 'мониторе' Assist 09.
