Сопрограммы (корутины, coroutine) - что это?
1,00
р.
Что такое сопрограммы и зачем они нужны?
Ответ
Сопрограммы (корутины, coroutine) - это потоки исполнения кода, которые организуются поверх аппаратных (системных) потоков. Поток исполнения кода - это последовательность операций, которые выполняются друг за другом. В нужные моменты эта последовательность может быть приостановлена, и вместо нее может начать выполняться часть другой последовательности операций.
Системные потоки состоят из инструкций процессора, и на одном ядре процессора могут по очереди работать несколько системных потоков. Сопрограммы работают на более высоком уровне - несколько сопрограмм могут по очереди выполнять свой код на одном системном потоке. (В зависимости от реализации, сопрограмма может быть не привязана к конкретному системному потоку, а например выполнять свой код на пуле потоков).
В отличие от системных потоков, которые переключаются системой в произвольные моменты времени (вытесняющая многозадачность), сопрограммы переключаются вручную, в местах, указанных программистом (кооперативная многозадачность).
Обозначим операции над сопрограммой следующим образом:
handle = spawn(СП) - запуск сопрограммы, yield - приостановка текущей сопрограммы, resume(handle) - возобновление сопрограммы.
Возьмем две сопрограммы:
// СП1 | // СП2 { | { f1() | g1() f2() | yield yield | g2() f3() | g3() f4() | yield yield | g4() f5() | g5() } | }
Тогда, если на одном системном потоке запустить СП1, а затем СП2, то системный поток выполнит операции в следующем детерминированном порядке:
// Системный поток | Выполняемый код c1 = spawn(СП1) | f1() | f2() c2 = spawn(СП2) | g1() resume(c1) | f3() | f4() resume(c2) | g2() | g3() resume(c1) | f5() resume(c2) | g4() | g5()
Так как обе сопрограммы выполняются на одном системном потоке, то в них невозможны гонки данных, код между yield выполняется атомарно (в пределах этого системного потока).
Если же запустить каждую сопрограмму в отдельном системном потоке, то тогда они ничем не будут отличаться от обычных системных потоков - будут переключаться там, где скажет система, необходима синхронизация, чтобы не было гонок данных.
Асинхронные операции
Один из основных сценариев применения сопрограмм - это асинхронные операции, такие как ввод-вывод и анимации в UI. После начала асинхронной операции, сопрограмма может сделать yield и продолжиться уже после завершения этой операции. При этом системный поток, на котором она выполнялась, не засыпает вместе с сопрограммой, а остается свободен для других сопрограмм.
Традиционный асинхронный код подразумевает использование коллбеков, как параметров функции, так и вместе с future/promise:
async_write(buffer, callback) -- или -- async_write(buffer).then(callback)
Где callback - это функция, которая будет вызвана после окончания асинхронной записи. В качестве коллбека можно использовать лямбда-функцию, например, в синтаксисе С++:
async_write(buffer, [=]{ on_write_completed() })
Введем операцию handle = get_coroutine_handle() , которая будет выдавать хендл (контекст) сопрограммы в коде самой сопрограммы. Тогда внутри сопрограммы можно написать:
handle = get_coroutine_handle() async_write(buffer, [=]{ resume(handle) }) yield
Для удобства, во многих языках используют оператор await, который сокращает этот код до
await async_write(buffer)
Более подробный пример:
// Использование коллбеков | // Использование сопрограмм | Socket src, dst | void copy(Socket src, Socket dst) { byte buffer[1024] | byte buffer[1024] void copy() { | for ( ) { async_read(src, buffer, on_read) | int n = await async_read(src, buffer) } | if (n <= 0) return void on_read(int n) { | await async_write(dst, buffer, n) if (n <= 0) return | } async_write(dst, buffer, n, copy) | } } | <br>Генераторы
Другой сценарий использования сопрограмм - это "генераторы", сопрограммы, которые генерируют последовательности однотипных объектов, например, последовательности чисел:
generator fib() { int a = 0, b = 1 for ( ) { yield a a = a + b yield b b = a + b } }
int main() { generator g = fib() // печатаем первые 5 for (int i = 0 i != 5 ++i) { g.next() print(g.value()) } }
Здесь yield кроме остановки генератора также принимает значения, которые выдаются генератором.
Stackful реализации сопрограмм
Как следует из названия, stackful (стековые) сопрограммы - это сопрограммы, у которых есть свой стек, как и у системных потоков. Основное отличие таких сопрограмм от обычных системных потоков - это то, что они переключаются вручную. По сравнению со скоростью переключения системных потоков, переключение сопрограмм практически бесплатно (сотни тактов процессора). Однако, из-за того что для каждой сопрограммы надо выделять отдельный стек и прочие служебные структуры данных - их создание и существование не дешевле, чем создание системного потока.
В Windows stackful сопрограммы встроены в систему и называются Fibers (фиберы, волокна). Волокна привязаны к тому системному потоку, на котором они созданы, переключение (yield/resume) реализуется через функцию SwitchToFiber(fiber_handle).
Запуск stackful сопрограммы ничем не отличается от запуска обычного потока, и может выглядеть, например, так:
handle = SpawnCoroutine(CoroutineFunc, STACK_SIZE)
Наличие собственного стека позволяет делать yield из вложенных вызовов функций. Однако, т.к. stackful сопрограммы довольно дороги, их нельзя использовать для создания простых генераторов.
Stackless реализации сопрограмм
Stackless (безстековые) сопрограммы никак не зависят от операционной системы, и реализуются исключительно средствами компилятора: код сопрограммы переписывается в объект-конечный автомат, локальные переменные выделяются не на стеке, а становятся членами этого объекта.
// сопрограмма | // код, генерируемый компилятором generator fib() { | struct __fib { int a = 0, b = 1 | int a, b for ( ) { | int __result yield a | int __state = 0 a = a + b | void next() { yield b | for ( ) switch (__state) { b = a + b | case 0: a = 0 } | b = 1 } | case 3: __result = a | __state = 1 | return | case 1: a = a + b | __result = b | __state = 2 | return | case 2: b = a + b | __state = 3 | break // loop | } | } | int value() { return __result } | } | generator fib() { | return __fib() | }
В отличие от stackful сопрограмм, в сопрограмме без стека yield может быть только в ее теле. Нельзя сделать yield из функции, вызванной сопрограммой.
Создание безстековой сопрограммы - это создание объекта, хранящего ее состояние (__fib), и обычно выглядит как вызов функции:
generator gen = fib() gen.next() int val = gen.value()
Ответ
Сопрограммы (корутины, coroutine) - это потоки исполнения кода, которые организуются поверх аппаратных (системных) потоков. Поток исполнения кода - это последовательность операций, которые выполняются друг за другом. В нужные моменты эта последовательность может быть приостановлена, и вместо нее может начать выполняться часть другой последовательности операций.
Системные потоки состоят из инструкций процессора, и на одном ядре процессора могут по очереди работать несколько системных потоков. Сопрограммы работают на более высоком уровне - несколько сопрограмм могут по очереди выполнять свой код на одном системном потоке. (В зависимости от реализации, сопрограмма может быть не привязана к конкретному системному потоку, а например выполнять свой код на пуле потоков).
В отличие от системных потоков, которые переключаются системой в произвольные моменты времени (вытесняющая многозадачность), сопрограммы переключаются вручную, в местах, указанных программистом (кооперативная многозадачность).
Обозначим операции над сопрограммой следующим образом:
handle = spawn(СП) - запуск сопрограммы, yield - приостановка текущей сопрограммы, resume(handle) - возобновление сопрограммы.
Возьмем две сопрограммы:
// СП1 | // СП2 { | { f1() | g1() f2() | yield yield | g2() f3() | g3() f4() | yield yield | g4() f5() | g5() } | }
Тогда, если на одном системном потоке запустить СП1, а затем СП2, то системный поток выполнит операции в следующем детерминированном порядке:
// Системный поток | Выполняемый код c1 = spawn(СП1) | f1() | f2() c2 = spawn(СП2) | g1() resume(c1) | f3() | f4() resume(c2) | g2() | g3() resume(c1) | f5() resume(c2) | g4() | g5()
Так как обе сопрограммы выполняются на одном системном потоке, то в них невозможны гонки данных, код между yield выполняется атомарно (в пределах этого системного потока).
Если же запустить каждую сопрограмму в отдельном системном потоке, то тогда они ничем не будут отличаться от обычных системных потоков - будут переключаться там, где скажет система, необходима синхронизация, чтобы не было гонок данных.
Асинхронные операции
Один из основных сценариев применения сопрограмм - это асинхронные операции, такие как ввод-вывод и анимации в UI. После начала асинхронной операции, сопрограмма может сделать yield и продолжиться уже после завершения этой операции. При этом системный поток, на котором она выполнялась, не засыпает вместе с сопрограммой, а остается свободен для других сопрограмм.
Традиционный асинхронный код подразумевает использование коллбеков, как параметров функции, так и вместе с future/promise:
async_write(buffer, callback) -- или -- async_write(buffer).then(callback)
Где callback - это функция, которая будет вызвана после окончания асинхронной записи. В качестве коллбека можно использовать лямбда-функцию, например, в синтаксисе С++:
async_write(buffer, [=]{ on_write_completed() })
Введем операцию handle = get_coroutine_handle() , которая будет выдавать хендл (контекст) сопрограммы в коде самой сопрограммы. Тогда внутри сопрограммы можно написать:
handle = get_coroutine_handle() async_write(buffer, [=]{ resume(handle) }) yield
Для удобства, во многих языках используют оператор await, который сокращает этот код до
await async_write(buffer)
Более подробный пример:
// Использование коллбеков | // Использование сопрограмм | Socket src, dst | void copy(Socket src, Socket dst) { byte buffer[1024] | byte buffer[1024] void copy() { | for ( ) { async_read(src, buffer, on_read) | int n = await async_read(src, buffer) } | if (n <= 0) return void on_read(int n) { | await async_write(dst, buffer, n) if (n <= 0) return | } async_write(dst, buffer, n, copy) | } } | <br>Генераторы
Другой сценарий использования сопрограмм - это "генераторы", сопрограммы, которые генерируют последовательности однотипных объектов, например, последовательности чисел:
generator fib() { int a = 0, b = 1 for ( ) { yield a a = a + b yield b b = a + b } }
int main() { generator g = fib() // печатаем первые 5 for (int i = 0 i != 5 ++i) { g.next() print(g.value()) } }
Здесь yield кроме остановки генератора также принимает значения, которые выдаются генератором.
Stackful реализации сопрограмм
Как следует из названия, stackful (стековые) сопрограммы - это сопрограммы, у которых есть свой стек, как и у системных потоков. Основное отличие таких сопрограмм от обычных системных потоков - это то, что они переключаются вручную. По сравнению со скоростью переключения системных потоков, переключение сопрограмм практически бесплатно (сотни тактов процессора). Однако, из-за того что для каждой сопрограммы надо выделять отдельный стек и прочие служебные структуры данных - их создание и существование не дешевле, чем создание системного потока.
В Windows stackful сопрограммы встроены в систему и называются Fibers (фиберы, волокна). Волокна привязаны к тому системному потоку, на котором они созданы, переключение (yield/resume) реализуется через функцию SwitchToFiber(fiber_handle).
Запуск stackful сопрограммы ничем не отличается от запуска обычного потока, и может выглядеть, например, так:
handle = SpawnCoroutine(CoroutineFunc, STACK_SIZE)
Наличие собственного стека позволяет делать yield из вложенных вызовов функций. Однако, т.к. stackful сопрограммы довольно дороги, их нельзя использовать для создания простых генераторов.
Stackless реализации сопрограмм
Stackless (безстековые) сопрограммы никак не зависят от операционной системы, и реализуются исключительно средствами компилятора: код сопрограммы переписывается в объект-конечный автомат, локальные переменные выделяются не на стеке, а становятся членами этого объекта.
// сопрограмма | // код, генерируемый компилятором generator fib() { | struct __fib { int a = 0, b = 1 | int a, b for ( ) { | int __result yield a | int __state = 0 a = a + b | void next() { yield b | for ( ) switch (__state) { b = a + b | case 0: a = 0 } | b = 1 } | case 3: __result = a | __state = 1 | return | case 1: a = a + b | __result = b | __state = 2 | return | case 2: b = a + b | __state = 3 | break // loop | } | } | int value() { return __result } | } | generator fib() { | return __fib() | }
В отличие от stackful сопрограмм, в сопрограмме без стека yield может быть только в ее теле. Нельзя сделать yield из функции, вызванной сопрограммой.
Создание безстековой сопрограммы - это создание объекта, хранящего ее состояние (__fib), и обычно выглядит как вызов функции:
generator gen = fib() gen.next() int val = gen.value()
