Coroutine

редактировать

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

Согласно Дональду Кнуту, Мелвин Конвей ввел термин сопрограмма в 1958 году, когда применил его к построению сборки программа. Первое опубликованное объяснение сопрограммы появилось позже, в 1963 году.

Содержание
  • 1 Сравнение с подпрограммами
  • 2 Сравнение с потоками
  • 3 Сравнение с генераторами
  • 4 Сравнение с взаимной рекурсией
  • 5 Распространенное использование
  • 6 языков программирования с собственной поддержкой
  • 7 Реализации
    • 7.1 Реализации для C
    • 7.2 Реализации для C ++
    • 7.3 Реализации для C #
    • 7.4 Реализации для Clojure
    • 7.5 Реализации для D
    • 7.6 Реализации для Java
    • 7.7 Реализации в JavaScript
    • 7.8 Реализации для Kotlin
    • 7.9 Реализации для Modula-2
    • 7.10 Реализация в Mono
    • 7.11 Реализация в.NET Framework как волокна
    • 7.12 Реализации для Perl
    • 7.13 Реализации для PHP
    • 7.14 Реализации для Python
    • 7.15 Реализации для Ruby
    • 7.16 Реализации для Rust
    • 7.17 Реализации для Scala
    • 7.18 Реализации для Scheme
    • 7.19 Реализации для Smalltalk
    • 7.20 Реализация Реализация для Swift
    • 7.21 для языка команд инструментов (Tcl)
    • 7.22 Реализации для Vala
    • 7.23 Реализации на языках ассемблера
  • 8 См. также
  • 9 Ссылки
  • 10 Дополнительная литература
  • 11 Внешние ссылки
Сравнение с подпрограммами

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

Любую подпрограмму можно преобразовать в сопрограмму, которая не вызывает 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), использующих эту или аналогичную модель.

Сравнение с взаимной рекурсией

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

Обычное использование

Сопрограммы полезны для реализации следующего:

  • Конечные автоматы внутри одной подпрограммы, где состояние определяется текущей точкой входа / выхода процедуры ; это может привести к более удобочитаемому коду по сравнению с использованием goto, а также может быть реализовано через взаимную рекурсию с хвостовыми вызовами.
  • Модель акторов параллелизма, например, в видеоиграх. У каждого актора есть свои собственные процедуры (это снова логически разделяет код), но они добровольно уступают управление центральному планировщику, который выполняет их последовательно (это форма совместной многозадачности ).
  • Генераторы, и эти полезны для потоков - в частности ввода / вывода - и для общего обхода структур данных.
  • Последовательные процессы обмена данными, где каждый подпроцесс является сопрограммой. Канальные входы / выходы и операции блокировки дают сопрограммы и планировщик разблокируют их при завершении событий. В качестве альтернативы, каждый подпроцесс может быть родительским для следующего за ним в конвейере данных (или предшествующего ему, и в этом случае шаблон может быть выражен как вложенные генераторы).
  • Обратная связь, обычно используемая в математическом программном обеспечении, в которой процедура, такая как решатель, интегральный вычислитель,... требует использования процесса для выполнения вычислений, таких как вычисление уравнения или подынтегральное выражение.
Языки программирования с родным вс pport

Сопрограммы возникли как метод языка ассемблера, но поддерживаются некоторыми языками программирования высокого уровня. Ранние примеры включают 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

Чтобы реализовать сопрограммы общего назначения, необходимо получить второй стек вызовов , что является функцией, не поддерживаемой напрямую 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 ++

  • TS сопрограмм C ++ (Техническая спецификация), стандарт расширений языка C ++ для бесстекового подмножества поведения, подобного сопрограммам, находится в стадии разработки. Visual C ++ и Clang уже поддерживают основные части пространства имен std :: experimental. Техническая спецификация сопрограмм
  • Boost.Coroutine - созданная Оливером Ковальке, это официальная выпущенная переносимая библиотека сопрограмм для boost, начиная с версии 1.53. Библиотека полагается на Boost.Context и поддерживает ARM, MIPS, PowerPC, SPARC и X86 в POSIX, Mac OS X и Windows.
  • Boost.Coroutine2 - также созданный Оливером Ковалке, модернизированная переносимая библиотека сопрограмм начиная с версии 1.59. Он использует преимущества C ++ 11, но устраняет поддержку симметричных сопрограмм.
  • Mordor - В 2010 году Mozy открыл исходный код библиотеки C ++, реализующей сопрограммы, с упором на их использование. абстрагировать асинхронный ввод-вывод в более знакомую последовательную модель.
  • CO2 - бесстековая сопрограмма на основе трюков препроцессора C ++ , обеспечивающая эмуляцию ожидания / выхода.
  • ScummVM - Проект ScummVM реализует облегченную версию бесстековых сопрограмм, основанную на статье Саймона Тэтхэма.
  • tonbit :: coroutine - C ++ 11 single.h asymmetric Реализация сопрограмм через ucontext / fiber
  • Сопрограммы появились в Clang в мае 2017 года, реализация libc ++ продолжается.
  • elle от Docker
  • oatpp-coroutines - Бестековые сопрограммы с планированием, разработанные для операций ввода-вывода с высоким уровнем параллелизма. Используется Oat ++ в эксперименте с 5 миллионами соединений WebSocket. Часть веб-инфраструктуры Oat ++.

Реализации для C #

  • MindTouch Dream - REST-инфраструктура MindTouch Dream предоставляет реализацию сопрограмм на основе итератора C # 2.0. pattern
  • Caliburn - платформа шаблонов экрана Caliburn для WPF использует итераторы C # 2.0 для упрощения программирования пользовательского интерфейса, особенно в асинхронных сценариях.
  • Библиотека Power Threading - Библиотека Power Threading реализует AsyncEnumerator, который предоставляет Упрощенная модель асинхронного программирования с использованием сопрограмм на основе итераторов.
  • Игровой движок Unity реализует сопрограммы.
  • Servelat Pieces - проект Servelat Pieces обеспечивает прозрачную асинхронность для служб Silverlight WCF и возможность асинхронно вызывать любой синхронный метод. Реализация основана на блоках итератора Coroutines Caliburn и итератора C #.
  • [9] -.NET 2.0+ Framework теперь предоставляет функциональность полукорутины (generator ) через шаблон итератора и yield ключевое слово.

C # 5.0 включает поддержку синтаксиса await.

Реализации для Clojure

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

Реализации для D

D реализуют сопрограммы в качестве стандартного библиотечного класса Fiber Генератор упрощает отображение функции волокна в качестве входного диапазона, делая любое волокно совместимым с существующими алгоритмами диапазонов.

Реализации для Java

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

  • Модифицированные JVM. Можно создать исправленную JVM для более естественной поддержки сопрограмм. Для JVM Да Винчи были созданы исправления.
  • Измененный байт-код. Функциональность сопрограмм возможна путем переписывания обычного байт-кода Java на лету или во время компиляции. Наборы инструментов включают Javaflow, Java Coroutines и Coroutines.
  • механизмы JNI для конкретных платформ. Они используют методы JNI, реализованные в библиотеках ОС или C для обеспечения функциональности JVM.
  • Абстракции потоков. Библиотеки сопрограмм, которые реализованы с использованием потоков, могут быть тяжелыми, хотя производительность будет зависеть от реализации потока JVM.

Реализации в JavaScript

  • node-fiber
    • Fibjs - fibjs - это среда выполнения JavaScript, построенная на базе Chrome Движок V8 JavaScript. fibjs использует fiber-switch, стиль синхронизации и неблокирующую модель ввода-вывода для создания масштабируемых систем.
  • Начиная с ECMAScript 2015, функциональность безстековых сопрограмм через «генераторы» и yield

Реализации для Kotlin

Kotlin реализует сопрограммы как часть собственной библиотеки.

Реализации для Modula-2

Modula-2, как определено Вирт реализует сопрограммы как часть стандартной библиотеки SYSTEM.

Процедура NEWPROCESS () заполняет контекст с учетом блока кода и пространства для стека в качестве параметров, а процедура TRANSFER () передает управление сопрограмме с учетом контекста сопрограммы в качестве параметра.

Реализация в Mono

Mono Common Language Runtime поддерживает продолжения, из которых могут быть построены сопрограммы.

Реализация в.NET Framework в виде волокон

Во время разработки .NET Framework 2.0 Microsoft расширила дизайн Common Language Runtime (CLR) хостинговые API для обработки планирования на основе волокна с прицелом на его использование в режиме волокна для сервера SQL. Перед выпуском поддержка перехвата переключения задач ICLRTask :: SwitchOut была удалена из-за нехватки времени. Следовательно, использование API-интерфейса волокна для переключения задач в настоящее время не является приемлемым вариантом в.NET Framework.

Реализации для Perl

Сопрограммы изначально реализованы во всех бэкэндах Raku.

Реализации для PHP

Реализации для Python

  • Python 2.5 реализует лучшую поддержку функций, подобных сопрограммам, на основе расширенных генераторов (PEP 342 )
  • Python 3.3 улучшает эту возможность, поддерживая делегирование субгенератору (PEP 380 )
  • Python 3.4 представляет комплексную структуру асинхронного ввода-вывода, стандартизованную в PEP 3156, которая включает сопрограммы, использующие делегирование субгенератора
  • Python 3.5 вводит явную поддержку сопрограмм с async / await синтаксис (PEP 0492 ).
  • Начиная с Python 3.7 async / await стал зарезервированным ключевым словом [10].
  • Eventlet
  • Greenlet
  • gevent
  • stackless python
  • Abandoned

Реализации для Ruby

Реализации для Rust

Существует библиотека для Rust, которая предоставляет сопрограммы. Генераторы - это экспериментальная функция, доступная в nightly rust, которая обеспечивает реализацию сопрограмм с async / await.

Реализации для Scala

Coroutines Scala - это реализация сопрограмм для Scala. Эта реализация представляет собой расширение уровня библиотеки, которое использует макросистему Scala для статического преобразования разделов программы в объекты сопрограмм. Таким образом, эта реализация не требует изменений в JVM, поэтому она полностью переносима между различными JVM и работает с альтернативными серверными модулями Scala, такими как Scala.js, который компилируется в JavaScript.

Coroutines Scala полагаются на макрос coroutine, который преобразует обычный блок кода в определение сопрограммы. Такое определение сопрограммы может быть вызвано с помощью операции call, которая создает экземпляр кадра сопрограммы. Кадр сопрограммы может быть возобновлен с помощью метода resume, который возобновляет выполнение тела сопрограммы до достижения ключевого слова yieldval, которое приостанавливает кадр сопрограммы. Scala Coroutines также предоставляют метод snapshot, который эффективно дублирует сопрограмму. Подробное описание сопрограмм Scala со снимками состояния появилось на ECOOP 2018 вместе с их формальной моделью.

реализациями для схемы

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

Реализации для Smalltalk

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

Реализации для Swift

  • SwiftCoroutine - библиотека сопрограмм Swift для iOS, macOS и Linux.

Реализация для языка команд инструментов (Tcl)

Начиная с версии 8.6, Инструмент Command Language поддерживает сопрограммы на основном языке.

Реализации для Vala

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

Реализации на языках ассемблера

Машинно-зависимые языки ассемблера часто предоставляют прямые методы для выполнения сопрограмм. Например, в MACRO-11, ассемблере семейства миникомпьютеров PDP-11, переключение «классической» сопрограммы осуществляется инструкцией «JSR PC, @ (SP) + ", который переходит к адресу, извлеченному из стека, и помещает текущий (то есть, адрес следующей ) инструкции в стек. На VAXenMacro-32 ) сопоставимая инструкция - «JSB @ (SP) +». Даже на Motorola 6809 есть инструкция «JSR [, S ++]»; обратите внимание на "++", так как 2 байта (адреса) выталкиваются из стека. Эта инструкция часто используется в (стандартном) 'мониторе' Assist 09.

См. Также
Ссылки
Дополнительная литература
Внешние ссылки
Последняя правка сделана 2021-05-15 12:59:18
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте