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

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

Начнём

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

Поток — это легковесный процесс. У каждого процесса может быть один или несколько потоков — это минимальная единица выполнения внутри процесса.

Основные элементы потока:

• Стек (место, где хранятся временные данные),

• Регистры процессора (для хранения текущих вычислений),

• ID потока (идентификатор),

• Указатель на инструкцию, которая должна выполниться,

• Состояние потока (например, "готов к выполнению" или "ожидание").

Обычно потоки реализуются на уровне операционной системы (такие потоки называются потоками ядра), но у этого подхода есть недостатки:

1. Высокая стоимость переключения контекста:
   

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

2. Зависимость от ядра:
   

   • Если поток блокируется (например, ожидает завершения ввода-вывода), то ядро передаёт управление другому потоку. Эффективность работы зависит от того, насколько хорошо ядро управляет потоками.

3. Ограниченная масштабируемость:
   

   • Если процесс создаёт много потоков, это увеличивает нагрузку на операционную систему и её планировщик, что может привести к снижению производительности.

Для решения этих проблем были созданы потоки в пользовательском пространстве

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

Есть разные виды потоков в пользовательском пространстве, такие как fibers, green threads и корутины (именно о них пойдёт речь в этой статье).

Модель корутин поближе

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

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

Существуют три основные модели мультиплексирования потоков внутри пользовательского процесса: 1:1, 1:N, M:N. Основная идея этих моделей заключается в том, что они позволяют делить один поток операционной системы между несколькими потоками пользовательского пространства.

• Модель 1:1:

  Для каждого потока операционной системы создаётся один стек в пользовательском пространстве. Это означает, что количество потоков в пользовательском пространстве соответствует количеству потоков в операционной системе.

• Модель 1:N:

  Эта модель характеризуется наличием нескольких стеков в пользовательском пространстве при наличии только одного потока в операционной системе. Это позволяет нескольким потокам пользовательского пространства использовать один поток ОС.

• Модель M:N:

  В этой модели для N потоков в операционной системе создаётся M стеков в пользовательском пространстве. Это позволяет более гибко распределять ресурсы между потоками.

Существуют два основных подхода для реализации корутин: stackful и stackless.

1. Stackful корутины:

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

2. Stackless корутины:

   В отличие от stackful корутин, stackless корутины не имеют собственного стека. Их выполнение управляется как машина состояний (state machine), которую генерирует компилятор. Это выглядит так, как будто выполнение функции просто переключается между разными состояниями — например, между ожиданием данных и продолжением выполнения после их получения.

   На практике stackless корутины чаще всего реализуются через ключевые слова вроде async/await. Когда функция встречает await, она приостанавливается до тех пор, пока не будет готов результат, после чего продолжает выполнение.

Переключение между корутинами

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

Переключение между stackful корутинами

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

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

Переключение между stackless корутинами

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

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

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

Stackful корутины имеют свой собственный стек, как уже упоминалось ранее. Это значит, что на стек выделяется память, которая зависит от реализации, но в среднем составляет от 64 КБ до 1 МБ на корутину. Кроме того, необходимо учитывать дополнительные затраты на хранение регистров и адреса возврата. Однако по сравнению со стеком этот оверхед незначителен.

Для stackless корутин нужно сохранять только локальное состояние, что составляет примерно 2 КБ на корутину. У них нет ограничений в виде стека, что делает их очень легковесными.

Например, если взять систему, состоящую из 10 000 корутин, которые потребляют по 64 КБ на стек, то общее потребление памяти составит около 640 МБ. В то же время для stackless корутин общее потребление памяти будет около 20 МБ, в расчете, что они потребляют в среднем по 2 КБ памяти.

Немного о том, как реализован стек

Существует два основных подхода: фиксированный и динамический (сегментированный) стек.

1. Фиксированный стек

При использовании фиксированного стека каждая корутина выделяет фиксированный объём памяти во время своего создания. У этого стека предопределён максимальный размер, который остаётся неизменным на протяжении всей жизни корутины.

Преимущества:

• Простота реализации: не требуется дополнительная логика для увеличения или уменьшения стека по мере его использования.

Недостатки:

• Если размер стека выбран слишком большим, пользователь может не использовать всю выделенную память, тратя ресурсы впустую.

• Если размер стека слишком мал, существует риск переполнения, что может привести к сбою программы (крашу).

2. Динамический стек

В корутинах с динамическим (сегментированным) стеком его размер начинается с небольшого объёма и увеличивается по мере необходимости, выделяя дополнительную память. Новые сегменты памяти выделяются и связываются, когда требуется больше места в стеке.

Преимущества:

• Динамическое изменение размера позволяет экономнее распределять ресурсы системы.

Недостатки:

• Увеличивается сложность реализации логики выделения памяти.

• Возникает небольшой оверхед по производительности для инициализации новых сегментов.

• Проблема фрагментации: стек может сильно фрагментироваться, если состоит из множества маленьких сегментов, разбросанных по всей памяти.

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

Где используются корутины?

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

В этой таблице мы собрали топ-10 языков программирования и указали, какие типы корутин используются в каждом из них: stackfull или stackless. Это поможет вам лучше понять, как разные языки подходят к реализации корутин и какие преимущества они предлагают.

Заключение

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

Мы рассмотрели два основных типа корутин — stackful и stackless — и узнали об их характеристиках, преимуществах и недостатках. Stackful корутины, такие как goroutines в Go, предлагают богатые возможности благодаря своему динамическому стеку, в то время как stackless корутины, реализуемые в других языках, обеспечивают быстрые переключения между задачами с минимальными накладными расходами.

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