{"id":8628,"date":"2023-11-20T10:44:09","date_gmt":"2023-11-20T10:44:09","guid":{"rendered":"https:\/\/www.modernescpp.com\/?p=8628"},"modified":"2023-11-22T18:19:26","modified_gmt":"2023-11-22T18:19:26","slug":"coroutines-a-scheduler-for-tasks-by-dian-lun-li","status":"publish","type":"post","link":"https:\/\/www.modernescpp.com\/index.php\/coroutines-a-scheduler-for-tasks-by-dian-lun-li\/","title":{"rendered":"Coroutines: A Scheduler for Tasks by Dian-Lun Lin"},"content":{"rendered":"\n

The last post “A Concise Introduction to Coroutines by Dian-Lun Lin<\/a>” provide the theory. Today, Dian-Lun presents his single-threaded scheduler for C++ coroutines.<\/p>\n\n\n\n

\"\"<\/figure>\n\n\n\n

This post assumes you are familiar with the previous post “A Concise Introduction to Coroutines by Dian-Lun Lin<\/a>“.<\/p>\n\n\n\n

A Single-threaded Scheduler for C++ Coroutines<\/h2>\n\n\n\n

In this section, I implement a single-threaded scheduler to schedule coroutines. Let\u2019s begin with the interface:<\/p>\n\n\n\n

Task TaskA<\/span>(Scheduler&<\/span> sch) {\n  std::<\/span>cout <<<\/span> "Hello from TaskA<\/span>\\n<\/span>"<\/span>;\n  co_await sch.suspend();\n  std::<\/span>cout <<<\/span> "Executing the TaskA<\/span>\\n<\/span>"<\/span>;\n  co_await sch.suspend();\n  std::<\/span>cout <<<\/span> "TaskA is finished<\/span>\\n<\/span>"<\/span>;\n}\n\nTask TaskB<\/span>(Scheduler&<\/span> sch) {\n  std::<\/span>cout <<<\/span> "Hello from TaskB<\/span>\\n<\/span>"<\/span>;\n  co_await sch.suspend();\n  std::<\/span>cout <<<\/span> "Executing the TaskB<\/span>\\n<\/span>"<\/span>;\n  co_await sch.suspend();\n  std::<\/span>cout <<<\/span> "TaskB is finished<\/span>\\n<\/span>"<\/span>;\n}\n\n\nint<\/span> main<\/span>() {\n\n  Scheduler sch;\n\n  sch.emplace(TaskA(sch).get_handle());\n  sch.emplace(TaskB(sch).get_handle());\n\n  std::<\/span>cout <<<\/span> "Start scheduling...<\/span>\\n<\/span>"<\/span>;\n\n  sch.schedule();\n<\/pre><\/div>\n\n\n\n
Both TaskA <\/code>and TaskB <\/code>are coroutines. I construct a scheduler in the main function and place the two tasks (coroutine handles) into the scheduler. I then call schedule <\/code>to schedule the two tasks. A task is a coroutine object that is defined as follows:<\/p>\n\n\n\n
struct<\/span> Task {\n\n  struct<\/span> promise_type {\n    std::<\/span>suspend_always initial_suspend() noexcept { return<\/span> {}; }\n    std::<\/span>suspend_always final_suspend() noexcept { return<\/span> {}; }\n\n    Task get_return_object() { \n        return<\/span> std::<\/span>coroutine_handle<<\/span>promise_type>::<\/span>from_promise(*<\/span>this<\/span>); \n    }\n    void<\/span> return_void() {}\n    void<\/span> unhandled_exception() {}\n  };\n\n  Task(std::<\/span>coroutine_handle<<\/span>promise_type><\/span> handle):<\/span> handle{handle} {}\n\n  auto<\/span> get_handle() { return<\/span> handle; }\n\n  std::<\/span>coroutine_handle<<\/span>promise_type><\/span> handle;\n};\n<\/pre><\/div>\n\n\n\n
Note that I return std::suspend_always<\/code> in both initial_suspend <\/code>and final_suspend <\/code>functions. This is because I want to hand the entire coroutine execution over to the scheduler. Coroutines are executed only after I call schedule<\/code>. The scheduler is defined as follows:<\/p>\n\n\n\n
class<\/span> Scheduler<\/span> {\n\n  \/\/std::queue<std::coroutine_handle<>> _tasks;<\/span>\n  std::<\/span>stack<<\/span>std::<\/span>coroutine_handle<>><\/span> _tasks;\n\n  public:<\/span> \n\n    void<\/span> emplace<\/span>(std::<\/span>coroutine_handle<><\/span> task) {\n      _tasks.push(task);\n    }\n\n    void<\/span> schedule<\/span>() {\n      while<\/span>(!<\/span>_tasks.empty()) {\n        \/\/auto task = _tasks.front();<\/span>\n        auto<\/span> task =<\/span> _tasks.top();\n        _tasks.pop();\n        task.resume();\n\n        if<\/span>(!<\/span>task.done()) { \n          _tasks.push(task);\n        }\n        else<\/span> {\n          task.destroy();\n        }\n      }\n    }\n\n    auto<\/span> suspend<\/span>() {\n      return<\/span> std::<\/span>suspend_always{};\n    }\n};\n<\/pre><\/div>\n\n\n\n
In the scheduler, I store tasks into a stack. I implement emplace <\/code>method to allow users to push a task into the stack. In schedule <\/code>method, I keep popping a task from the stack. After resuming a task, I check if that task is done. If not, I push the task back to the stack for later scheduling. Otherwise, I destroy the finished task. After executing the program, the results are the following:<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
The scheduler stores tasks using a stack (last in, first out). Interestingly, if I replace the stack with the queue (first in, first out), the execution results become:<\/p>\n\n\n\n
\"\"<\/figure>\n\n\n\n
For completeness, here are both programs:<\/p>\n\n\n\n
\/\/ stackScheduler.cpp<\/span>\n\n#include <coroutine><\/span>\n#include <iostream><\/span>\n#include <stack><\/span>\n\n\nstruct<\/span> Task {\n\n  struct<\/span> promise_type {\n    std::<\/span>suspend_always initial_suspend() noexcept { return<\/span> {}; }\n    std::<\/span>suspend_always final_suspend() noexcept { return<\/span> {}; }\n\n    Task get_return_object() { \n        return<\/span> std::<\/span>coroutine_handle<<\/span>promise_type>::<\/span>from_promise(*<\/span>this<\/span>); \n    }\n    void<\/span> return_void() {}\n    void<\/span> unhandled_exception() {}\n  };\n\n  Task(std::<\/span>coroutine_handle<<\/span>promise_type><\/span> handle):<\/span> handle{handle} {}\n\n  auto<\/span> get_handle() { return<\/span> handle; }\n\n  std::<\/span>coroutine_handle<<\/span>promise_type><\/span> handle;\n};\n\nclass<\/span> Scheduler<\/span> {\n\n  std::<\/span>stack<<\/span>std::<\/span>coroutine_handle<>><\/span> _tasks;\n\n  public:<\/span> \n\n    void<\/span> emplace<\/span>(std::<\/span>coroutine_handle<><\/span> task) {\n      _tasks.push(task);\n    }\n\n    void<\/span> schedule<\/span>() {\n      while<\/span>(!<\/span>_tasks.empty()) {\n        auto<\/span> task =<\/span> _tasks.top();\n        _tasks.pop();\n        task.resume();\n\n        if<\/span>(!<\/span>task.done()) { \n          _tasks.push(task);\n        }\n        else<\/span> {\n          task.destroy();\n        }\n      }\n    }\n\n    auto<\/span> suspend<\/span>() {\n      return<\/span> std::<\/span>suspend_always{};\n    }\n};\n\n\nTask TaskA<\/span>(Scheduler&<\/span> sch) {\n  std::<\/span>cout <<<\/span> "Hello from TaskA<\/span>\\n<\/span>"<\/span>;\n  co_await sch.suspend();\n  std::<\/span>cout <<<\/span> "Executing the TaskA<\/span>\\n<\/span>"<\/span>;\n  co_await sch.suspend();\n  std::<\/span>cout <<<\/span> "TaskA is finished<\/span>\\n<\/span>"<\/span>;\n}\n\nTask TaskB<\/span>(Scheduler&<\/span> sch) {\n  std::<\/span>cout <<<\/span> "Hello from TaskB<\/span>\\n<\/span>"<\/span>;\n  co_await sch.suspend();\n  std::<\/span>cout <<<\/span> "Executing the TaskB<\/span>\\n<\/span>"<\/span>;\n  co_await sch.suspend();\n  std::<\/span>cout <<<\/span> "TaskB is finished<\/span>\\n<\/span>"<\/span>;\n}\n\n\nint<\/span> main<\/span>() {\n\n  std::<\/span>cout <<<\/span> '\\n'<\/span>;\n\n  Scheduler sch;\n\n  sch.emplace(TaskA(sch).get_handle());\n  sch.emplace(TaskB(sch).get_handle());\n\n  std::<\/span>cout <<<\/span> "Start scheduling...<\/span>\\n<\/span>"<\/span>;\n\n  sch.schedule();\n\n  std::<\/span>cout <<<\/span> '\\n'<\/span>;\n\n}\n<\/pre><\/div>\n\n\n\n
\/\/ queueScheduler.cpp<\/span>\n\n#include <coroutine><\/span>\n#include <iostream><\/span>\n#include <queue><\/span>\n\n\nstruct<\/span> Task {\n\n  struct<\/span> promise_type {\n    std::<\/span>suspend_always initial_suspend() noexcept { return<\/span> {}; }\n    std::<\/span>suspend_always final_suspend() noexcept { return<\/span> {}; }\n\n    Task get_return_object() { \n        return<\/span> std::<\/span>coroutine_handle<<\/span>promise_type>::<\/span>from_promise(*<\/span>this<\/span>); \n    }\n    void<\/span> return_void() {}\n    void<\/span> unhandled_exception() {}\n  };\n\n  Task(std::<\/span>coroutine_handle<<\/span>promise_type><\/span> handle):<\/span> handle{handle} {}\n\n  auto<\/span> get_handle() { return<\/span> handle; }\n\n  std::<\/span>coroutine_handle<<\/span>promise_type><\/span> handle;\n};\n\nclass<\/span> Scheduler<\/span> {\n\n  std::<\/span>queue<<\/span>std::<\/span>coroutine_handle<>><\/span> _tasks;\n\n  public:<\/span> \n\n    void<\/span> emplace<\/span>(std::<\/span>coroutine_handle<><\/span> task) {\n      _tasks.push(task);\n    }\n\n    void<\/span> schedule<\/span>() {\n      while<\/span>(!<\/span>_tasks.empty()) {\n        auto<\/span> task =<\/span> _tasks.front();\n        _tasks.pop();\n        task.resume();\n\n        if<\/span>(!<\/span>task.done()) { \n          _tasks.push(task);\n        }\n        else<\/span> {\n          task.destroy();\n        }\n      }\n    }\n\n    auto<\/span> suspend<\/span>() {\n      return<\/span> std::<\/span>suspend_always{};\n    }\n};\n\n\nTask TaskA<\/span>(Scheduler&<\/span> sch) {\n  std::<\/span>cout <<<\/span> "Hello from TaskA<\/span>\\n<\/span>"<\/span>;\n  co_await sch.suspend();\n  std::<\/span>cout <<<\/span> "Executing the TaskA<\/span>\\n<\/span>"<\/span>;\n  co_await sch.suspend();\n  std::<\/span>cout <<<\/span> "TaskA is finished<\/span>\\n<\/span>"<\/span>;\n}\n\nTask TaskB<\/span>(Scheduler&<\/span> sch) {\n  std::<\/span>cout <<<\/span> "Hello from TaskB<\/span>\\n<\/span>"<\/span>;\n  co_await sch.suspend();\n  std::<\/span>cout <<<\/span> "Executing the TaskB<\/span>\\n<\/span>"<\/span>;\n  co_await sch.suspend();\n  std::<\/span>cout <<<\/span> "TaskB is finished<\/span>\\n<\/span>"<\/span>;\n}\n\n\nint<\/span> main<\/span>() {\n\n  std::<\/span>cout <<<\/span> '\\n'<\/span>;\n\n  Scheduler sch;\n\n  sch.emplace(TaskA(sch).get_handle());\n  sch.emplace(TaskB(sch).get_handle());\n\n  std::<\/span>cout <<<\/span> "Start scheduling...<\/span>\\n<\/span>"<\/span>;\n\n  sch.schedule();\n\n  std::<\/span>cout <<<\/span> '\\n'<\/span>;\n\n}\n<\/pre><\/div>\n\n\n\n
What’s Next?<\/h2>\n\n\n\n
This blog post from  Dian-Lun Lin showed a straightforward scheduler for coroutines. I use Dian-Lun’s scheduler in my next post for further experiments.<\/p>\n","protected":false},"excerpt":{"rendered":"
The last post “A Concise Introduction to Coroutines by Dian-Lun Lin” provide the theory. Today, Dian-Lun presents his single-threaded scheduler for C++ coroutines. This post assumes you are familiar with the previous post “A Concise Introduction to Coroutines by Dian-Lun Lin“. A Single-threaded Scheduler for C++ Coroutines In this section, I implement a single-threaded scheduler […]<\/p>\n","protected":false},"author":21,"featured_media":8607,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[375],"tags":[445],"class_list":["post-8628","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-c-20","tag-coroutines"],"_links":{"self":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/8628","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/comments?post=8628"}],"version-history":[{"count":15,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/8628\/revisions"}],"predecessor-version":[{"id":8740,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/posts\/8628\/revisions\/8740"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media\/8607"}],"wp:attachment":[{"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/media?parent=8628"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/categories?post=8628"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.modernescpp.com\/index.php\/wp-json\/wp\/v2\/tags?post=8628"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}