====== Coroutine ====== * このページではコルーチンの概要，利点，実現方法を説明する ===== - 概要 ===== * この章ではコルーチンの概要を説明する * コルーチンとは，通常のルーチンの能力に加えて，**中断**(yield)と**再開**(resume)が可能なルーチンである ==== - ルーチンとは ==== * ルーチンとは，コンピュータの1つの機能を実現する命令群 (別名: 関数，プロシージャ，手続き) * 最初に実行されるルーチンを**メインルーチン**と呼ぶ * メインルーチンから呼び出されるルーチンを**サブルーチン**と呼ぶ * ルーチンは，必ずしも関数1つを意味するわけではなく，命令群そのものをルーチンと呼ぶ * ルーチンは，以下の能力を持つ * 外部から**開始**(entry)されることができる * 開始された後に，自らを**終了**(return)することができる (終了しなくてもいい=無限ループ) ==== - コルーチンとは ==== * コルーチンとは，以下の能力を持つルーチンである * 開始，あるいは，再開された後に，自らを**中断**(yield)することができる (中断しなくてもいい) * 中断された後に，外部から**再開**(resume)されることができる * コルーチンとは，**単なる言語機能の名前ではなく，中断/再開が可能な命令群を意味している** コルーチンは明らかに状態を持つが，果たしてルーチンと言ってしまっていいのだろうか．．． ===== - 利点 ===== * この章では，同時処理の代表的手段のスレッドと比較しながら，コルーチンの利点を説明する * 開始前あるいは中断後の複数のコルーチンを順番に開始・再開することで，スレッドより安全に，同時処理を実現することができる ==== - 同時処理の2つの方法 ==== * 複数のルーチンを同時に処理する，同時処理には主に2つの方法がある * **並行処理**(concurrency)は，複数のルーチンを同時に扱う(deal)こと * 例) 2列で並ぶ客を1台のレジで，2列から交互に，順番に1人ずつ対応する * 列=ルーチン / 客=不可分な命令 / レジ=プロセッサ * **並列処理**(parallelism)は，複数のルーチンを同時に実行(execute)すること * 例) 2列で並ぶ客を2台のレジで対応する * 並行処理は，消費リソースが少なく，全タスク完遂までの時間が長い * 並列処理は，消費リソースが多く，全タスク完遂までの時間が短い ==== - スレッドの性質 ==== * スレッド(=native thread)は，基本的に，並行処理の並列処理によって実行される * 例) 2台のレジそれぞれに2列，計4列で客が並ぶ * どの列(スレッド)をどのレジ(プロセッサ)にどのくらい処理させるかは，OSのスケジューラが決定し，実行させている * スケジューラは，プロセスの優先度などを考慮して次に処理する列(スレッド)を決定する * スケジューラは，レジに対して，客1人(1命令)を処理し終わったタイミングで，別の列(スレッド)を処理するように命令できる ==== - スレッドの問題 ==== * **排他制御**(mutual exclusion)をしなければ，**データ競合**(data race)や**競合状態**(race condition)が起こりうる * 実装が難しい，危険性が高い * データ競合や競合状態は，再現性が低く，原因特定も困難だから * 別ルーチンが同時処理されてはいけない全ての区間に対して排他制御を行わなければならないから (=**ブラックリスト的な対策**) * 排他制御の実行時コストが高い * (条件変数を使う場合) OSによるスレッドの切り替え(context switch)が発生し得るから * (spin lockの場合) busy loopが発生し得るから * **データ競合**(data race)は，あるルーチンが書き込み中に，他のルーチンが読み書きを行うことで，共有リソースが不正な状態をとる，あるいはそのように読み込まれてしまう現象． * **競合状態**(race condition)は，あるルーチンの振る舞いの正しさが，他ルーチンとの実行順序や実行タイミングに依存する状態． ==== - コルーチンによる解決 ==== * 開始前あるいは中断後の複数のコルーチンを順番に開始・再開することで，並行処理による同時処理を実現することができる * スレッドの同時処理よりも，**実装が容易**，**安全性が高い** * 「よくないこと」に対して**ホワイトリスト的な対策**ができるから * コルーチンでは，別ルーチンが__実行されてもいいタイミングを明示__する * スレッドでは，別ルーチンが__実行されてはいけないタイミングを明示__する * スレッドの同時処理よりも，**実行時コストが低い** * 排他制御を行わないため，busy loopもスレッドの切り替えも発生しないから * スレッドの同時処理よりも，**全ルーチンの完遂が遅い** * スレッドでは，他ルーチンの影響を受けないことが保証される最小の命令単位は，マシンコードにおける1命令 * コルーチンでは，最小の命令単位は，中断(yield)を用いてコルーチンの実装者が自由に決めることができる コルーチンを使った並行処理は，green thread / userland thread / fiber などと呼ばれることもある． ===== - 実装方法 ===== * この章では，コルーチンや，コルーチンを使った同時処理の実現方法を解説する ==== - コルーチンの実装 ==== * 一部の言語では，コルーチンを簡単に実現できる言語機能をサポートしている * C++20では，言語機能を使える([[https://cpprefjp.github.io/lang/cpp20/coroutines.html|リファレンス]]) * そのような言語機能がないプログラミング言語でも，自前で実装できる * Cでは，switchを使えば比較的楽に実装できる→[[https://wandbox.org/permlink/80sgDTYdveelfg69|wandbox]] * [[https://ja.wikipedia.org/wiki/Duff%27s_device|duff's device]]から着想を得た * そもそも，中断可能なルーチン(手続き)がコルーチンであるため，関数という形である必要はない * run()メソッド1つだけのstate patternクラスでも構わない ==== - コルーチンを使った並行処理の実装 ==== * コルーチンを使った並行処理を用いたシステムを実装する場合，サブシステムとして，最低限以下の要件を満たす**タスクキュー**が必要である * あらゆるタイミングで，あらゆるスレッドから，タスクを受け取ることができる * 現在実行されているタスクがない場合，受け取ったタスクを即座に実行しなければならない * 現在実行されているタスクがある場合，__そのタスクの終了後に__，受け取ったタスクを，受け取った順番に実行しなければならない * **全てのタスクの実行は，同一のスレッド上で行う** * 全てのタスク終了後に，次のタスクを受け取るまでsleepする * また，コルーチンは，以下の制約の下で，実装され，取り扱われなければならない * 全てのコルーチンは，タスクキューから開始あるいは再開されなければならない * 全てのコルーチンは，**その処理の中でブロッキングをしてはならない** * ブロッキング中は，同時処理されている他のすべてのルーチンの処理が滞ってしまうから * ブロッキングI/Oの代わりに，非同期I/Oを要求し，自らを中断する必要がある * 自身を中断するコルーチンは，**中断後に自身を再開する責務を持つ** * 非同期処理やサブコルーチンの完了を待つために自身を中断するならば，完了を知らせるコールバックから，「自身を再開させる」タスクをタスクキューへpushする * タスクキューは，スレッドにおけるOSのスケジューラと同等の役割を担っている * ただし，スケジューラとは異なり，**タスクキューはコルーチンを中断させることはできない** * コルーチンが中断される時は，コルーチン自らが中断した時だけである * これにより，意図しないタイミングでのルーチンの同時実行を防ぐことができる * また，スケジューラよりも**明らかに軽量，かつ，高速である** * スケジューラは，何百とあるスレッドの優先度や，属するプロセスの優先度，権限などを鑑みて次に処理するスレッドを決定し，スレッド切り替えまで行っている * 対して，タスクキューはただ単に受け取ったタスクを順番に実行するだけである タスクキューのタスクに対して，発火時間プロパティを持たせることで，JavaScriptの''setTimeout''のようなことが可能になる．その場合，タスクキューの実体は，発火時間を優先度とする優先度付きキューになり，発火時間を過ぎていないタスクだけが残った時は[最も直近の発火時間まで，あるいは，新しいタスクを受け取るまで]sleepする． //''std::priority_queue''が輝く貴重な瞬間//