LINUX.ORG.RU

История изменений

Исправление dissident, (текущая версия) :

у корутин нет шедулера,

Поправь меня, пожалуйста, если я что-то неверно понял.

У fiber’ов может быть шедулер (как и у безстэковых корутин, твоего «оксюморона», но это IMHO не имеет смысла, см. ниже), например, https://www.boost.org/doc/libs/1_65_1/libs/fiber/doc/html/fiber/scheduling.html. Имеется ввиду не то, что шедулер определяет, когда прервать fiber, что было бы вытесняющей многозадачностью (это определяет сам fiber, в точках вызова yield, что является кооперативной многозадачностью), а в том, что fiber’ы не нужно вручную «возобновлять» при помощи resume - их «возобновляет» шедулер (в случае если он есть и используется).

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

(с) https://stackoverflow.com/a/42042904

Но как в случае симметричных, так и даже несимметричных fiber’ов можно реализовать шедулер. Например в случае несимметричных корутин (тех, которые возвращают управление вызвавшему трэду) шедулер будет "resume"ить fiber’ы согласно какому-нибудь алгоритму в этом самом трэде, который можно будет выбрать, например, в простейшем случае это будет просто цикл:

queue<fiber_type> fibers;

while (!finished)
{

    while (fibers.empty() && !fibers)
    {   
        co_yield();
    }

    if (!finished)
    {
        fiber_type f = fibers.front();
        fibers.pop();
        f.resume();
    }
}

Или это будет, например, цикл с приоритетами:

struct fiber_type {
    int prio;
    ...
    void operator()() { ... }
};

struct greater_fib {
  bool operator()(const fiber_type& a, const fiber_type& b) const{
    return a.prio > b.prio;
  }
};

vector<fiber_type> fibers;
fibers.push_back(...);
fibers.push_back(...);
...

// sort by priorities
make_heap(fibers.begin(), fibers.end());

while (!finished)
{
    while (fibers.empty() && !fibers)
    {   
        co_yield();
    }

    // sort by priorities to keep fibers sorted in case any of the executed fiber
    // adds something to the heap (not effective, but this is just an example)
    make_heap(fibers.begin(), fibers.end());

    if (!finished)
    {
        fiber_type f = fibers.front();
        fibers.pop();
        f.resume();
    }
}

В случае безстэковых корутин компилятор при создании каждой корутины генерирует и создает при помощи new структуру (где хранятся, например, значения переменных в данный момент) для корутины (в принципе, не обязательно компилятор эту структуру генерирует, безстэковые корутины могут быть реализованы в качестве библиотеки, правда в этом случае необходимо будет вручную задать какие переменные в корутине нужно «запомнить» в структуре корутины и вручную реализовывать всю эту механику с их «запоминанием», так, например, безстэковые корутины реализованы в boost::asio, см., например, socket_ и buffer_ в примере https://www.boost.org/doc/libs/1_54_0/doc/html/boost_asio/overview/core/coroutine.html). При этом, поскольку структура для корутины одна, то нельзя сделать как-нибудь так:

coroutine_type coroutine
{
    int a, b;
    // do something async
    yield();
}

void function()
{
   coroutine_type cor coroutine();
   cor.resume();
}

await function();

Т.е. нельзя ожидать корутины на уровне выше, чем ее вызов, так как у безстэковых корутин тип возвращаемого результата (courotine_type в примере выше) является частью декларации корутины (в отличие от стэковой корутины) и при ее вызове динамически создается структура, содержащая в примере выше a и b, которая одна для всей корутины и не поддерживает стэка вызовов функций/корутин.

В Unity (как и в C++ STL!) именно такие безстэковые корутины. К ним можно прилепить шедулер (например простой цикл для данного трэда, который будет их сам вызывать (см. выше пример с queue и heap)), но у такой реализации ограниченные возможности именно потому, что передать управление «наверх» можно только из самой корутины, а не из промежуточной функции/функций.

Мне кажется, что в случае безстэковых корутин и хитроумного шедулера можно создать deadlock, даже несмотря на то, что трэд один, например трэд делает await cor1 и следом await cor2, обе cor1 и cor2 делают await cor3, которая делает await cor1 и await cor2. Такое вообще возможно? Я в ту сторону думаю? Ну т.е. мой вопрос: имеет ли право на существование шедулер для безстэковых корутин (повторюсь, под шедулером, я имею ввиду не выбор точек переключения (это задает программист вручную вставляя куда нужно yield()), а алгоритм выбора следующей корутины для «возобновления» (resume), например «простой цикл», «цикл с приоритетами» и т.п.).

Стэковые же корутины (они же fiber’ы) позволяют иметь граф вызовов функций, в котором фукнции где-то «внизу» вызывают корутины, а трэд, который «начинает» этот граф, может ждать не только на уровне вызова fiber’ов, но и выше. В такой реализации (стэковые корутины, они же fiber’ы) шедулер имеет смысл. Такие корутины (или правильнее fiber’ы или lightweight threads) реализованы например в boost::coroutine и boost::courotine2 (которые отличаются, например, тем, что в boost::coroutine2 нету симметричных корутин, но при этом обе эти библиотеки реализуют стэковые корутины, они же fiber’ы, они же lightweight threads).

Тот факт, что в C++ корутины безстэковые ограничивает их полезность. Так же, как, например, отсутствие then() у future сильно ограничивает применение future, т.е., например, нельзя написать так (этот пример с future не имеет отношение к корутинам, просто показывает, насколько в C++ то, что появляется - появляется поздно и не доделано по-человечески, как future’ы, так и корутины):

future<data_type f = async([]() {
    data_type d = long_process();
    return d;
});

f.then([](future<data_type> &f) {
    data_type d = f.get();
    d.use();
};

do_smth_in_parallel_with_long_process();

А придется городить бессмысленный огород как-нибудь так:

future<data_type> f = async([&f]() {
    data_type d = long_process();
    return d;
});

thread([]() {
    data_type d = f.get();
    d.use();
});

do_smth_in_parallel_with_long_process();

что проще реализовать вовсе без future:

void callback(data_type &d)
{
    d.use();
}

async([&f]() {
    data_type d = long_process();
    callback(d);
});

do_smth_in_parallel_with_long_process();   

что делает future практически бесполезными, так же и то, что корутины в C++ безстэковые тоже делает их использование просто синтактическим сахаром.

Так или иначе шедулер у корутин может быть, как у стэковых, так и у безстэковых (IMHO относительно шедулера у безстэковых корутин, см. вопрос выше про осмысленность шедулера для них и про deadlock), правда во-втором случае смысла в нем мало (IMHO). Стэковые же корутины иначе называются fiber’ами, иначе lightweight thread’ами, иначе, например, goroutine’ами (в Go), отсюда и путаница в терминах. То, что ты называешь трэдами, может быть как полноценными трэдами (или процессами), которые могут выполняться каждый своим CPU, так и fiber’ами, иначе lightweight thread’ами, иначе стэковыми корутинами, которые выполняются в том же трэде (и тем же CPU), но при этом обеспечивают кооперативную многозадачность в точках yield, при этом позволяют иметь шедулер, решающий какую корутину следующую возобновлять при помощи resume(), при этом позволяют иметь любой уровень вложенности функций/корутин) и делают использование шедулера для них чем-то, что имеет смысл.

То, что объединяет безстэковые и стэковые корутины - это то, что они выполняются в том же самом трэде (ну, в отличие, разве что от gotoutines в Go, которые могут быть «перенесены» в другой трэд (см. https://stackoverflow.com/a/19486183 наример), в случае вызова какой-нибудь goroutine’ой блокирующей I/O операции), а значит, как как в случае безстэковых так и стэковых корутин синхронизация (мутексы, семафоры и т.д.) не нужна.

Исправление dissident, :

у корутин нет шедулера,

Поправь меня, пожалуйста, если я что-то неверно понял.

У fiber’ов может быть шедулер (как и у безстэковых корутин, твоего «оксюморона», но это IMHO не имеет смысла, см. ниже), например, https://www.boost.org/doc/libs/1_65_1/libs/fiber/doc/html/fiber/scheduling.html. Имеется ввиду не то, что шедулер определяет, когда прервать fiber, что было бы вытесняющей многозадачностью (это определяет сам fiber, в точках вызова yield, что является кооперативной многозадачностью), а в том, что fiber’ы не нужно вручную «возобновлять» при помощи resume - их «возобновляет» шедулер (в случае если он есть и используется).

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

(с) https://stackoverflow.com/a/42042904

Но как в случае симметричных, так и даже несимметричных fiber’ов можно реализовать шедулер. Например в случае несимметричных корутин (тех, которые возвращают управление вызвавшему трэду) шедулер будет "resume"ить fiber’ы согласно какому-нибудь алгоритму в этом самом трэде, который можно будет выбрать, например, в простейшем случае это будет просто цикл:

queue<fiber_type> fibers;

while (!finished)
{

    while (fibers.empty() && !fibers)
    {   
        co_yield();
    }

    if (!finished)
    {
        fiber_type f = fibers.front();
        fibers.pop();
        f.resume();
    }
}

Или это будет, например, цикл с приоритетами:

struct fiber_type {
    int prio;
    ...
    void operator()() { ... }
};

struct greater_fib {
  bool operator()(const fiber_type& a, const fiber_type& b) const{
    return a.prio > b.prio;
  }
};

vector<fiber_type> fibers;
fibers.push_back(...);
fibers.push_back(...);
...

// sort by priorities
make_heap(fibers.begin(), fibers.end());

while (!finished)
{
    while (fibers.empty() && !fibers)
    {   
        co_yield();
    }

    // sort by priorities to keep fibers sorted in case any of the executed fiber
    // adds something to the heap (not effective, but this is just an example)
    make_heap(fibers.begin(), fibers.end());

    if (!finished)
    {
        fiber_type f = fibers.front();
        fibers.pop();
        f.resume();
    }
}

В случае безстэковых корутин компилятор при создании каждой корутины генерирует и создает при помощи new структуру (где хранятся, например, значения переменных в данный момент) для корутины (в принципе, не обязательно компилятор эту структуру генерирует, безстэковые корутины могут быть реализованы в качестве библиотеки, правда в этом случае необходимо будет вручную задать какие переменные в корутине нужно «запомнить» в структуре корутины и вручную реализовывать всю эту механику с их «запоминанием», так, например, безстэковые корутины реализованы в boost::asio, см., например, socket_ и buffer_ в примере https://www.boost.org/doc/libs/1_54_0/doc/html/boost_asio/overview/core/coroutine.html). При этом, поскольку структура для корутины одна, то нельзя сделать как-нибудь так:

coroutine_type coroutine
{
    int a, b;
    // do something async
    yield();
}

void function()
{
   coroutine_type cor coroutine();
   cor.resume();
}

await function();

Т.е. нельзя ожидать корутины на уровне выше, чем ее вызов, так как у безстэковых корутин тип возвращаемого результата (courotine_type в примере выше) является частью декларации корутины (в отличие от стэковой корутины) и при ее вызове динамически создается структура, содержащая в примере выше a и b, которая одна для всей корутины и не поддерживает стэка вызовов функций/корутин.

В Unity (как и в C++ STL!) именно такие безстэковые корутины. К ним можно прилепить шедулер (например простой цикл для данного трэда, который будет их сам вызывать (см. выше пример с queue и heap)), но у такой реализации ограниченные возможности именно потому, что передать управление «наверх» можно только из самой корутины, а не из промежуточной функции/функций.

Мне кажется, что в случае безстэковых корутин и хитроумного шедулера можно создать deadlock, даже несмотря на то, что трэд один, например трэд делает await cor1 и следом await cor2, обе cor1 и cor2 делают await cor3, которая делает await cor1 и await cor2. Такое вообще возможно? Я в ту сторону думаю? Ну т.е. мой вопрос: имеет ли право на существование шедулер для безстэковых корутин (повторюсь, под шедулером, я имею ввиду не выбор точек переключения (это задает программист вручную вставляя куда нужно yield()), а алгоритм выбора следующей корутины для «возобновления» (resume), например «простой цикл», «цикл с приоритетами» и т.п.).

Стэковые же корутины (они же fiber’ы) позволяют иметь граф вызовов функций, в котором фукнции где-то «внизу» вызывают корутины, а трэд, который «начинает» этот граф, может ждать не только на уровне вызова fiber’ов, но и выше. В такой реализации (стэковые корутины, они же fiber’ы) шедулер имеет смысл. Такие корутины (или правильнее fiber’ы или lightweight threads) реализованы например в boost::coroutine и boost::courotine2 (которые отличаются, например, тем, что в boost::coroutine2 нету симметричных корутин, но при этом обе эти библиотеки реализуют стэковые корутины, они же fiber’ы, они же lightweight threads).

Тот факт, что в C++ корутины безстэковые ограничивает их полезность. Так же, как, например, отсутствие then() у future сильно ограничивает применение future, т.е., например, нельзя написать так (этот пример с future не имеет отношение к корутинам, просто показывает, насколько в C++ то, что появляется - появляется поздно и не доделано по-человечески, как future’ы, так и корутины):

futuredata_type f = async([]() {
    data_type d = long_process();
    return d;
});

f.then([](future<data_type> &f) {
    data_type d = f.get();
    d.use();
};

do_smth_in_parallel_with_long_process();

А придется городить бессмысленный огород как-нибудь так:

future<data_type> f = async([&f]() {
    data_type d = long_process();
    return d;
});

thread([]() {
    data_type d = f.get();
    d.use();
});

do_smth_in_parallel_with_long_process();

что проще реализовать вовсе без future:

void callback(data_type &d)
{
    d.use();
}

async([&f]() {
    data_type d = long_process();
    callback(d);
});

do_smth_in_parallel_with_long_process();   

что делает future практически бесполезными, так же и то, что корутины в C++ безстэковые тоже делает их использование просто синтактическим сахаром.

Так или иначе шедулер у корутин может быть, как у стэковых, так и у безстэковых (IMHO относительно шедулера у безстэковых корутин, см. вопрос выше про осмысленность шедулера для них и про deadlock), правда во-втором случае смысла в нем мало (IMHO). Стэковые же корутины иначе называются fiber’ами, иначе lightweight thread’ами, иначе, например, goroutine’ами (в Go), отсюда и путаница в терминах. То, что ты называешь трэдами, может быть как полноценными трэдами (или процессами), которые могут выполняться каждый своим CPU, так и fiber’ами, иначе lightweight thread’ами, иначе стэковыми корутинами, которые выполняются в том же трэде (и тем же CPU), но при этом обеспечивают кооперативную многозадачность в точках yield, при этом позволяют иметь шедулер, решающий какую корутину следующую возобновлять при помощи resume(), при этом позволяют иметь любой уровень вложенности функций/корутин) и делают использование шедулера для них чем-то, что имеет смысл.

То, что объединяет безстэковые и стэковые корутины - это то, что они выполняются в том же самом трэде (ну, в отличие, разве что от gotoutines в Go, которые могут быть «перенесены» в другой трэд (см. https://stackoverflow.com/a/19486183 наример), в случае вызова какой-нибудь goroutine’ой блокирующей I/O операции), а значит, как как в случае безстэковых так и стэковых корутин синхронизация (мутексы, семафоры и т.д.) не нужна.

Исправление dissident, :

у корутин нет шедулера,

Поправь меня, пожалуйста, если я что-то неверно понял.

У fiber’ов может быть шедулер (как и у безстэковых корутин, твоего «оксюморона», но это IMHO не имеет смысла, см. ниже), например, https://www.boost.org/doc/libs/1_65_1/libs/fiber/doc/html/fiber/scheduling.html. Имеется ввиду не то, что шедулер определяет, когда прервать fiber, что было бы вытесняющей многозадачностью (это определяет сам fiber, в точках вызова yield, что является кооперативной многозадачностью), а в том, что fiber’ы не нужно вручную «возобновлять» при помощи resume - их «возобновляет» шедулер (в случае если он есть и используется).

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

(с) https://stackoverflow.com/a/42042904

Как в случае симметричных, так и несимметричных fiber’ов можно реализовать шедулер. Например в случае несимметричных корутин (тех, которые возвращают управление вызвавшему трэду) шедулер будет "resume"ить fiber’ы согласно какому-нибудь алгоритму в этом самом трэде, который можно будет выбрать, например, в простейшем случае это будет просто цикл:

queue<fiber_type> fibers;

while (!finished)
{

    while (fibers.empty() && !fibers)
    {   
        co_yield();
    }

    if (!finished)
    {
        fiber_type f = fibers.front();
        fibers.pop();
        f.resume();
    }
}

Или это будет, например, цикл с приоритетами:

struct fiber_type {
    int prio;
    ...
    void operator()() { ... }
};

struct greater_fib {
  bool operator()(const fiber_type& a, const fiber_type& b) const{
    return a.prio > b.prio;
  }
};

vector<fiber_type> fibers;
fibers.push_back(...);
fibers.push_back(...);
...

// sort by priorities
make_heap(fibers.begin(), fibers.end());

while (!finished)
{
    while (fibers.empty() && !fibers)
    {   
        co_yield();
    }

    // sort by priorities to keep fibers sorted in case any of the executed fiber
    // adds something to the heap (not effective, but this is just an example)
    make_heap(fibers.begin(), fibers.end());

    if (!finished)
    {
        fiber_type f = fibers.front();
        fibers.pop();
        f.resume();
    }
}

В случае безстэковых корутин компилятор при создании каждой корутины генерирует и создает при помощи new структуру (где хранятся, например, значения переменных в данный момент) для корутины (в принципе, не обязательно компилятор эту структуру генерирует, безстэковые корутины могут быть реализованы в качестве библиотеки, правда в этом случае необходимо будет вручную задать какие переменные в корутине нужно «запомнить» в структуре корутины и вручную реализовывать всю эту механику с их «запоминанием», так, например, безстэковые корутины реализованы в boost::asio, см., например, socket_ и buffer_ в примере https://www.boost.org/doc/libs/1_54_0/doc/html/boost_asio/overview/core/coroutine.html). При этом, поскольку структура для корутины одна, то нельзя сделать как-нибудь так:

coroutine_type coroutine
{
    int a, b;
    // do something async
    yield();
}

void function()
{
   coroutine_type cor coroutine();
   cor.resume();
}

await function();

Т.е. нельзя ожидать корутины на уровне выше, чем ее вызов, так как у безстэковых корутин тип возвращаемого результата (courotine_type в примере выше) является частью декларации корутины (в отличие от стэковой корутины) и при ее вызове динамически создается структура, содержащая в примере выше a и b, которая одна для всей корутины и не поддерживает стэка вызовов функций/корутин.

В Unity (как и в C++ STL!) именно такие безстэковые корутины. К ним можно прилепить шедулер (например простой цикл для данного трэда, который будет их сам вызывать (см. выше пример с queue и heap)), но у такой реализации ограниченные возможности именно потому, что передать управление «наверх» можно только из самой корутины, а не из промежуточной функции/функций.

Мне кажется, что в случае безстэковых корутин и хитроумного шедулера можно создать deadlock, даже несмотря на то, что трэд один, например трэд делает await cor1 и следом await cor2, обе cor1 и cor2 делают await cor3, которая делает await cor1 и await cor2. Такое вообще возможно? Я в ту сторону думаю? Ну т.е. мой вопрос: имеет ли право на существование шедулер для безстэковых корутин (повторюсь, под шедулером, я имею ввиду не выбор точек переключения (это задает программист вручную вставляя куда нужно yield()), а алгоритм выбора следующей корутины для «возобновления» (resume), например «простой цикл», «цикл с приоритетами» и т.п.).

Стэковые же корутины (они же fiber’ы) позволяют иметь граф вызовов функций, в котором фукнции где-то «внизу» вызывают корутины, а трэд, который «начинает» этот граф, может ждать не только на уровне вызова fiber’ов, но и выше. В такой реализации (стэковые корутины, они же fiber’ы) шедулер имеет смысл. Такие корутины (или правильнее fiber’ы или lightweight threads) реализованы например в boost::coroutine и boost::courotine2 (которые отличаются, например, тем, что в boost::coroutine2 нету симметричных корутин, но при этом обе эти библиотеки реализуют стэковые корутины, они же fiber’ы, они же lightweight threads).

Тот факт, что в C++ корутины безстэковые ограничивает их полезность. Так же, как, например, отсутствие then() у future сильно ограничивает применение future, т.е., например, нельзя написать так (этот пример с future не имеет отношение к корутинам, просто показывает, насколько в C++ то, что появляется - появляется поздно и не доделано по-человечески, как future’ы, так и корутины):

futuredata_type f = async([]() {
    data_type d = long_process();
    return d;
});

f.then([](future<data_type> &f) {
    data_type d = f.get();
    d.use();
};

do_smth_in_parallel_with_long_process();

А придется городить бессмысленный огород как-нибудь так:

future<data_type> f = async([&f]() {
    data_type d = long_process();
    return d;
});

thread([]() {
    data_type d = f.get();
    d.use();
});

do_smth_in_parallel_with_long_process();

что проще реализовать вовсе без future:

void callback(data_type &d)
{
    d.use();
}

async([&f]() {
    data_type d = long_process();
    callback(d);
});

do_smth_in_parallel_with_long_process();   

что делает future практически бесполезными, так же и то, что корутины в C++ безстэковые тоже делает их использование просто синтактическим сахаром.

Так или иначе шедулер у корутин может быть, как у стэковых, так и у безстэковых (IMHO относительно шедулера у безстэковых корутин, см. вопрос выше про осмысленность шедулера для них и про deadlock), правда во-втором случае смысла в нем мало (IMHO). Стэковые же корутины иначе называются fiber’ами, иначе lightweight thread’ами, иначе, например, goroutine’ами (в Go), отсюда и путаница в терминах. То, что ты называешь трэдами, может быть как полноценными трэдами (или процессами), которые могут выполняться каждый своим CPU, так и fiber’ами, иначе lightweight thread’ами, иначе стэковыми корутинами, которые выполняются в том же трэде (и тем же CPU), но при этом обеспечивают кооперативную многозадачность в точках yield, при этом позволяют иметь шедулер, решающий какую корутину следующую возобновлять при помощи resume(), при этом позволяют иметь любой уровень вложенности функций/корутин) и делают использование шедулера для них чем-то, что имеет смысл.

То, что объединяет безстэковые и стэковые корутины - это то, что они выполняются в том же самом трэде (ну, в отличие, разве что от gotoutines в Go, которые могут быть «перенесены» в другой трэд (см. https://stackoverflow.com/a/19486183 наример), в случае вызова какой-нибудь goroutine’ой блокирующей I/O операции), а значит, как как в случае безстэковых так и стэковых корутин синхронизация (мутексы, семафоры и т.д.) не нужна.

Исправление dissident, :

у корутин нет шедулера,

Поправь меня, пожалуйста, если я что-то неверно понял.

У fiber’ов может быть шедулер (как и у безстэковых корутин, твоего «оксюморона», но это IMHO не имеет смысла, см. ниже), например, https://www.boost.org/doc/libs/1_65_1/libs/fiber/doc/html/fiber/scheduling.html. Имеется ввиду не то, что шедулер определяет, когда прервать fiber, что было бы вытесняющей многозадачностью (это определяет сам fiber, в точках вызова yield, что является кооперативной многозадачностью), а в том, что fiber’ы не нужно вручную «возобновлять» при помощи resume - их «возобновляет» шедулер.

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

(с) https://stackoverflow.com/a/42042904

Как в случае симметричных, так и несимметричных fiber’ов можно реализовать шедулер. Например в случае несимметричных корутин (тех, которые возвращают управление вызвавшему трэду) шедулер будет "resume"ить fiber’ы согласно какому-нибудь алгоритму в этом самом трэде, который можно будет выбрать, например, в простейшем случае это будет просто цикл:

queue<fiber_type> fibers;

while (!finished)
{

    while (fibers.empty() && !fibers)
    {   
        co_yield();
    }

    if (!finished)
    {
        fiber_type f = fibers.front();
        fibers.pop();
        f.resume();
    }
}

Или это будет, например, цикл с приоритетами:

struct fiber_type {
    int prio;
    ...
    void operator()() { ... }
};

struct greater_fib {
  bool operator()(const fiber_type& a, const fiber_type& b) const{
    return a.prio > b.prio;
  }
};

vector<fiber_type> fibers;
fibers.push_back(...);
fibers.push_back(...);
...

// sort by priorities
make_heap(fibers.begin(), fibers.end());

while (!finished)
{
    while (fibers.empty() && !fibers)
    {   
        co_yield();
    }

    // sort by priorities to keep fibers sorted in case any of the executed fiber
    // adds something to the heap (not effective, but this is just an example)
    make_heap(fibers.begin(), fibers.end());

    if (!finished)
    {
        fiber_type f = fibers.front();
        fibers.pop();
        f.resume();
    }
}

В случае безстэковых корутин компилятор при создании каждой корутины генерирует и создает при помощи new структуру (где хранятся, например, значения переменных в данный момент) для корутины (в принципе, не обязательно компилятор эту структуру генерирует, безстэковые корутины могут быть реализованы в качестве библиотеки, правда в этом случае необходимо будет вручную задать какие переменные в корутине нужно «запомнить» в структуре корутины и вручную реализовывать всю эту механику с их «запоминанием», так, например, безстэковые корутины реализованы в boost::asio, см., например, socket_ и buffer_ в примере https://www.boost.org/doc/libs/1_54_0/doc/html/boost_asio/overview/core/coroutine.html). При этом, поскольку структура для корутины одна, то нельзя сделать как-нибудь так:

coroutine_type coroutine
{
    int a, b;
    // do something async
    yield();
}

void function()
{
   coroutine_type cor coroutine();
   cor.resume();
}

await function();

Т.е. нельзя ожидать корутины на уровне выше, чем ее вызов, так как у безстэковых корутин тип возвращаемого результата (courotine_type в примере выше) является частью декларации корутины (в отличие от стэковой корутины) и при ее вызове динамически создается структура, содержащая в примере выше a и b, которая одна для всей корутины и не поддерживает стэка вызовов функций/корутин.

В Unity (как и в C++ STL!) именно такие безстэковые корутины. К ним можно прилепить шедулер (например простой цикл для данного трэда, который будет их сам вызывать (см. выше пример с queue и heap)), но у такой реализации ограниченные возможности именно потому, что передать управление «наверх» можно только из самой корутины, а не из промежуточной функции/функций.

Мне кажется, что в случае безстэковых корутин и хитроумного шедулера можно создать deadlock, даже несмотря на то, что трэд один, например трэд делает await cor1 и следом await cor2, обе cor1 и cor2 делают await cor3, которая делает await cor1 и await cor2. Такое вообще возможно? Я в ту сторону думаю? Ну т.е. мой вопрос: имеет ли право на существование шедулер для безстэковых корутин (повторюсь, под шедулером, я имею ввиду не выбор точек переключения (это задает программист вручную вставляя куда нужно yield()), а алгоритм выбора следующей корутины для «возобновления» (resume), например «простой цикл», «цикл с приоритетами» и т.п.).

Стэковые же корутины (они же fiber’ы) позволяют иметь граф вызовов функций, в котором фукнции где-то «внизу» вызывают корутины, а трэд, который «начинает» этот граф, может ждать не только на уровне вызова fiber’ов, но и выше. В такой реализации (стэковые корутины, они же fiber’ы) шедулер имеет смысл. Такие корутины (или правильнее fiber’ы или lightweight threads) реализованы например в boost::coroutine и boost::courotine2 (которые отличаются, например, тем, что в boost::coroutine2 нету симметричных корутин, но при этом обе эти библиотеки реализуют стэковые корутины, они же fiber’ы, они же lightweight threads).

Тот факт, что в C++ корутины безстэковые ограничивает их полезность. Так же, как, например, отсутствие then() у future сильно ограничивает применение future, т.е., например, нельзя написать так (этот пример с future не имеет отношение к корутинам, просто показывает, насколько в C++ то, что появляется - появляется поздно и не доделано по-человечески, как future’ы, так и корутины):

futuredata_type f = async([]() {
    data_type d = long_process();
    return d;
});

f.then([](future<data_type> &f) {
    data_type d = f.get();
    d.use();
};

do_smth_in_parallel_with_long_process();

А придется городить бессмысленный огород как-нибудь так:

future<data_type> f = async([&f]() {
    data_type d = long_process();
    return d;
});

thread([]() {
    data_type d = f.get();
    d.use();
});

do_smth_in_parallel_with_long_process();

что проще реализовать вовсе без future:

void callback(data_type &d)
{
    d.use();
}

async([&f]() {
    data_type d = long_process();
    callback(d);
});

do_smth_in_parallel_with_long_process();   

что делает future практически бесполезными, так же и то, что корутины в C++ безстэковые тоже делает их использование просто синтактическим сахаром.

Так или иначе шедулер у корутин может быть, как у стэковых, так и у безстэковых (IMHO относительно шедулера у безстэковых корутин, см. вопрос выше про осмысленность шедулера для них и про deadlock), правда во-втором случае смысла в нем мало (IMHO). Стэковые же корутины иначе называются fiber’ами, иначе lightweight thread’ами, иначе, например, goroutine’ами (в Go), отсюда и путаница в терминах. То, что ты называешь трэдами, может быть как полноценными трэдами (или процессами), которые могут выполняться каждый своим CPU, так и fiber’ами, иначе lightweight thread’ами, иначе стэковыми корутинами, которые выполняются в том же трэде (и тем же CPU), но при этом обеспечивают кооперативную многозадачность в точках yield, при этом позволяют иметь шедулер, решающий какую корутину следующую возобновлять при помощи resume(), при этом позволяют иметь любой уровень вложенности функций/корутин) и делают использование шедулера для них чем-то, что имеет смысл.

То, что объединяет безстэковые и стэковые корутины - это то, что они выполняются в том же самом трэде (ну, в отличие, разве что от gotoutines в Go, которые могут быть «перенесены» в другой трэд (см. https://stackoverflow.com/a/19486183 наример), в случае вызова какой-нибудь goroutine’ой блокирующей I/O операции), а значит, как как в случае безстэковых так и стэковых корутин синхронизация (мутексы, семафоры и т.д.) не нужна.

Исправление dissident, :

у корутин нет шедулера,

Поправь меня, пожалуйста, если я где-то неверно понял/

У fiber’ов может быть шедулер (как и у безстэковых корутин, твоего «оксюморона», но это IMHO не имеет смысла, см. ниже), например, https://www.boost.org/doc/libs/1_65_1/libs/fiber/doc/html/fiber/scheduling.html. Имеется ввиду не то, что шедулер определяет, когда прервать fiber, что было бы вытесняющей многозадачностью (это определяет сам fiber, в точках вызова yield, что является кооперативной многозадачностью), а в том, что fiber’ы не нужно вручную «возобновлять» при помощи resume - их «возобновляет» шедулер.

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

(с) https://stackoverflow.com/a/42042904

Как в случае симметричных, так и несимметричных fiber’ов можно реализовать шедулер. Например в случае несимметричных корутин (тех, которые возвращают управление вызвавшему трэду) шедулер будет "resume"ить fiber’ы согласно какому-нибудь алгоритму в этом самом трэде, который можно будет выбрать, например, в простейшем случае это будет просто цикл:

queue<fiber_type> fibers;

while (!finished)
{

    while (fibers.empty() && !fibers)
    {   
        co_yield();
    }

    if (!finished)
    {
        fiber_type f = fibers.front();
        fibers.pop();
        f.resume();
    }
}

Или это будет, например, цикл с приоритетами:

struct fiber_type {
    int prio;
    ...
    void operator()() { ... }
};

struct greater_fib {
  bool operator()(const fiber_type& a, const fiber_type& b) const{
    return a.prio > b.prio;
  }
};

vector<fiber_type> fibers;
fibers.push_back(...);
fibers.push_back(...);
...

// sort by priorities
make_heap(fibers.begin(), fibers.end());

while (!finished)
{
    while (fibers.empty() && !fibers)
    {   
        co_yield();
    }

    // sort by priorities to keep fibers sorted in case any of the executed fiber
    // adds something to the heap (not effective, but this is just an example)
    make_heap(fibers.begin(), fibers.end());

    if (!finished)
    {
        fiber_type f = fibers.front();
        fibers.pop();
        f.resume();
    }
}

В случае безстэковых корутин компилятор при создании каждой корутины генерирует и создает при помощи new структуру (где хранятся, например, значения переменных в данный момент) для корутины (в принципе, не обязательно компилятор эту структуру генерирует, безстэковые корутины могут быть реализованы в качестве библиотеки, правда в этом случае необходимо будет вручную задать какие переменные в корутине нужно «запомнить» в структуре корутины и вручную реализовывать всю эту механику с их «запоминанием», так, например, безстэковые корутины реализованы в boost::asio, см., например, socket_ и buffer_ в примере https://www.boost.org/doc/libs/1_54_0/doc/html/boost_asio/overview/core/coroutine.html). При этом, поскольку структура для корутины одна, то нельзя сделать как-нибудь так:

coroutine_type coroutine
{
    int a, b;
    // do something async
    yield();
}

void function()
{
   coroutine_type cor coroutine();
   cor.resume();
}

await function();

Т.е. нельзя ожидать корутины на уровне выше, чем ее вызов, так как у безстэковых корутин тип возвращаемого результата (courotine_type в примере выше) является частью декларации корутины (в отличие от стэковой корутины) и при ее вызове динамически создается структура, содержащая в примере выше a и b, которая одна для всей корутины и не поддерживает стэка вызовов функций/корутин.

В Unity (как и в C++ STL!) именно такие безстэковые корутины. К ним можно прилепить шедулер (например простой цикл для данного трэда, который будет их сам вызывать (см. выше пример с queue и heap)), но у такой реализации ограниченные возможности именно потому, что передать управление «наверх» можно только из самой корутины, а не из промежуточной функции/функций.

Мне кажется, что в случае безстэковых корутин и хитроумного шедулера можно создать deadlock, даже несмотря на то, что трэд один, например трэд делает await cor1 и следом await cor2, обе cor1 и cor2 делают await cor3, которая делает await cor1 и await cor2. Такое вообще возможно? Я в ту сторону думаю? Ну т.е. мой вопрос: имеет ли право на существование шедулер для безстэковых корутин (повторюсь, под шедулером, я имею ввиду не выбор точек переключения (это задает программист вручную вставляя куда нужно yield()), а алгоритм выбора следующей корутины для «возобновления» (resume), например «простой цикл», «цикл с приоритетами» и т.п.).

Стэковые же корутины (они же fiber’ы) позволяют иметь граф вызовов функций, в котором фукнции где-то «внизу» вызывают корутины, а трэд, который «начинает» этот граф, может ждать не только на уровне вызова fiber’ов, но и выше. В такой реализации (стэковые корутины, они же fiber’ы) шедулер имеет смысл. Такие корутины (или правильнее fiber’ы или lightweight threads) реализованы например в boost::coroutine и boost::courotine2 (которые отличаются, например, тем, что в boost::coroutine2 нету симметричных корутин, но при этом обе эти библиотеки реализуют стэковые корутины, они же fiber’ы, они же lightweight threads).

Тот факт, что в C++ корутины безстэковые ограничивает их полезность. Так же, как, например, отсутствие then() у future сильно ограничивает применение future, т.е., например, нельзя написать так (этот пример с future не имеет отношение к корутинам, просто показывает, насколько в C++ то, что появляется - появляется поздно и не доделано по-человечески, как future’ы, так и корутины):

futuredata_type f = async([]() {
    data_type d = long_process();
    return d;
});

f.then([](future<data_type> &f) {
    data_type d = f.get();
    d.use();
};

do_smth_in_parallel_with_long_process();

А придется городить бессмысленный огород как-нибудь так:

future<data_type> f = async([&f]() {
    data_type d = long_process();
    return d;
});

thread([]() {
    data_type d = f.get();
    d.use();
});

do_smth_in_parallel_with_long_process();

что проще реализовать вовсе без future:

void callback(data_type &d)
{
    d.use();
}

async([&f]() {
    data_type d = long_process();
    callback(d);
});

do_smth_in_parallel_with_long_process();   

что делает future практически бесполезными, так же и то, что корутины в C++ безстэковые тоже делает их использование просто синтактическим сахаром.

Так или иначе шедулер у корутин может быть, как у стэковых, так и у безстэковых (IMHO относительно шедулера у безстэковых корутин, см. вопрос выше про осмысленность шедулера для них и про deadlock), правда во-втором случае смысла в нем мало (IMHO). Стэковые же корутины иначе называются fiber’ами, иначе lightweight thread’ами, иначе, например, goroutine’ами (в Go), отсюда и путаница в терминах. То, что ты называешь трэдами, может быть как полноценными трэдами (или процессами), которые могут выполняться каждый своим CPU, так и fiber’ами, иначе lightweight thread’ами, иначе стэковыми корутинами, которые выполняются в том же трэде (и тем же CPU), но при этом обеспечивают кооперативную многозадачность в точках yield, при этом позволяют иметь шедулер, решающий какую корутину следующую возобновлять при помощи resume(), при этом позволяют иметь любой уровень вложенности функций/корутин) и делают использование шедулера для них чем-то, что имеет смысл.

То, что объединяет безстэковые и стэковые корутины - это то, что они выполняются в том же самом трэде (ну, в отличие, разве что от gotoutines в Go, которые могут быть «перенесены» в другой трэд (см. https://stackoverflow.com/a/19486183 наример), в случае вызова какой-нибудь goroutine’ой блокирующей I/O операции), а значит, как как в случае безстэковых так и стэковых корутин синхронизация (мутексы, семафоры и т.д.) не нужна.

Исходная версия dissident, :

у корутин нет шедулера,

Поправь меня, пожалуйста, если я где-то неверно понял/

У fiber’ов может быть шедулер (как и у безстэковых корутин, твоего «оксюморона», но это IMHO не имеет смысла, см. ниже), например, https://www.boost.org/doc/libs/1_65_1/libs/fiber/doc/html/fiber/scheduling.html. Имеется ввиду не то, что шедулер определяет, когда прервать fiber, что было бы вытесняющей многозадачностью (это определяет сам fiber, в точках вызова yield, что является кооперативной многозадачностью), а в том, что fiber’ы не нужно вручную «возобновлять» при помощи resume - их «возобновляет» шедулер.

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

(с) https://stackoverflow.com/a/42042904

Как в случае симметричных, так и несимметричных fiber’ов можно реализовать шедулер. Например в случае несимметричных корутин (тех, которые возвращают управление вызвавшему трэду) шедулер будет "resume"ить fiber’ы согласно какому-нибудь алгоритму в этом самом трэде, который можно будет выбрать, например, в простейшем случае это будет просто цикл:

queue<fiber_type> fibers;

while (!finished)
{

    while (fibers.empty() && !fibers)
    {   
        co_yield();
    }

    if (!finished)
    {
        fiber_type f = fibers.front();
        fibers.pop();
        f.resume();
    }
}

Или это будет, например, цикл с приоритетами:

struct fiber_type {
    int prio;
    ...
    void operator()() { ... }
};

struct greater_fib {
  bool operator()(const fiber_type& a, const fiber_type& b) const{
    return a.prio > b.prio;
  }
};

vector<fiber_type> fibers;
fibers.push_back(...);
fibers.push_back(...);

// sort by priorities
make_heap(fibers.begin(), fibers.end());
...;

while (!finished)
{
    while (fibers.empty() && !fibers)
    {   
        co_yield();
    }

    // sort by priorities to keep fibers sorted in case any of
    // the executed fiber adds something to the heap (not
    // effective, but this is just an example)
    make_heap(fibers.begin(), fibers.end());

    if (!finished)
    {
        fiber_type f = fibers.front();
        fibers.pop();
        f.resume();
    }
}

В случае безстэковых корутин компилятор при создании каждой корутины генерирует и создает при помощи new структуру (где хранятся, например, значения переменных в данный момент) для корутины (в принципе, не обязательно компилятор эту структуру генерирует, безстэковые корутины могут быть реализованы в качестве библиотеки, правда в этом случае необходимо будет вручную задать какие переменные в корутине нужно «запомнить» в структуре корутины и вручную реализовывать всю эту механику с их «запоминанием», так, например, безстэковые корутины реализованы в boost::asio). При этом, поскольку структура для корутины одна, то нельзя сделать как-нибудь так:

coroutine_type coroutine
{
    int a, b;
    // do something async
    yield();
}

void function()
{
   coroutine_type cor coroutine();
   cor.resume();
}

await function();

Т.е. нельзя ожидать корутины на уровне выше, чем ее вызов, так как у безстэковых корутин тип возвращаемого результата является частью декларации корутины (в отличие от стэковой корутины) и при ее вызове динамически создается структура, содержащая в примере выше a и b, которая одна для всей корутины и не поддерживает стэка вызова функций/корутин.

В Unity (как и в C++ STL!) именно такие безстэковые корутины. К ним можно прилепить шедулер (например простой цикл для данного трэда, который будет их сам вызывать (см. выше пример с queue и heap)), но у такой реализации ограниченные возможности именно потому, что передать управление «наверх» можно только из самой корутины, а не из промежуточной функции/функций.

Мне кажется, что в случае безстэковых корутин и хитроумного шедулера легко создать deadlock, даже несмотря на то, что трэд один, например трэд делает await cor1 и следом await cor2, обе cor1 и cor2 делают await cor3, которая делает await cor1 и await cor2. Такое вообще возможно? Я в ту сторону думаю? Ну т.е. мой вопрос: имеет ли право на существование шедулер для безстэковых корутин (повторюсь, под шедулером, я имею ввиду не выбор точек переключения (это задает программист вручную вставляя куда нужно yield()), а алгоритм выбора следующей корутины для «возобновления» (resume), например «простой цикл», «цикл с приоритетами» и т.п.).

Стэковые же корутины (они же fiber’ы) позволяют иметь граф вызовов функций, в котором фукнции где-то «внизу» вызывают корутины, а трэд, который «начинает» этот граф, может ждать не только на уровне вызова fiber’ов, но и выше. В такой реализации (стэковые корутины, они же fiber’ы) шедулер имеет смысл. Такие корутины (или правильнее fiber’ы или lightweight threads) реализованы например в boost::coroutine и boost::courotine2 (которые отличаются, например, тем, что в boost::coroutine2 нету симметричных корутин, но при этом обе эти библиотеки реализуют стэковые корутины, они же fiber’ы, они же lightweight threads).

Тот факт, что в C++ корутины безстэковые ограничивает их полезность. Так же, как, например, отсутствие then() у future сильно ограничивает применение future, т.е., например, нельзя написать так (этот пример с future не имеет отношение к корутинам, просто показывает, насколько в C++ то, что появляется - появляется поздно и не доделано по-человечески, как future’ы, так и корутины):

futuredata_type f = async([]() {
    data_type d = long_process();
    return d;
});

f.then([](future<data_type> &f) {
    data_type d = f.get();
    d.use();
};

do_smth_in_parallel_with_long_process();

А придется городить бессмысленный огород как-нибудь так:

future<data_type> f = async([&f]() {
    data_type d = long_process();
    return d;
});

thread([]() {
    data_type d = f.get();
    d.use();
});

do_smth_in_parallel_with_long_process();

что проще реализовать вовсе без future:

void callback(data_type &d)
{
    d.use();
}

async([&f]() {
    data_type d = long_process();
    callback(d);
});

do_smth_in_parallel_with_long_process();   

что делает future практически бесполезными, так же и то, что корутины в C++ безстэковые тоже делает их использование просто синтактическим сахаром.

Так или иначе шедулер у корутин может быть, как у стэковых, так и у безстэковых (IMHO, см. вопрос выше про осмысленность шедулера для безстэковых корутин), правда во-втором случае смысла в нем мало (IMHO). Стэковые же корутины иначе называются fiber’ами, иначе lightweight thread’ами, иначе, например, goroutine’ами (в Go), отсюда и путаница в терминах. То, что ты называешь трэдами, может быть как полноценными трэдами (или процессами), которые могут выполняться каждый своим CPU, так и fiber’ами, иначе lightweight thread’ами, т.е. стэковыми корутинами, которые выполняются в том же трэде (и тем же CPU), но при этом обеспечивают кооперативную многозадачность в точках yield, при этом позволяют иметь шедулер, решающий какую коротину следующую возобновлять при помощи resume(), при этом позволяют иметь любой уровень вложенности функций/корутин) и делают использование шедулера для них чем-то, что имеет смысл.

То, что объединяет безстэковые и стэковые корутины - это то, что они выполняются в том же самом трэде (ну, в отличие, разве что от gotoutines в Go, которые могут быть «перенесены» в другой трэд https://stackoverflow.com/a/19486183, наример, в случае вызова какой-нибудь goroutine’ой блокирующей I/O операции)), а значит, как в случае безстэковых так и стэковых корутин синхронизация (мутексы, семафоры и т.д.) не нужна.