$shibayu36->blog;

株式会社はてなでエンジニアをしています。プログラミングや読書のことなどについて書いています。

I/Oを多重化するためのシステムコール(select, poll, epoll, kqueue)

 サーバ周りの勉強していると、たまにselectとかepollとか言葉が出てきて、理解できてなかったので調べてみた。

I/Oの多重化

 例えばサーバ周りの実装を、特に何も考えずにやると、I/Oでブロッキングが発生し、一つのクライアントとしか通信できないということが起こります。これを解決するために

  • fork
  • threads
  • I/Oの多重化
  • 非同期I/O

といった方法があります。
 この中のI/Oの多重化を実装するためのシステムコールとして、select, poll, epoll, kqueueなどは実装されているようです。
 少し調べてみると、次のような記述のような機能をそれぞれが実装するようです。

プログラムで複数のファイルディスクリプタを監視し、 一つ以上のファイルディスクリプタがある種の I/O 操作の 「ready (準備ができた)」状態 (例えば、読み込み可能になった状態) になるまで待つことができる。

select

 selectの場合、次の特徴があります。

 ファイルディスクリプタを一つ一つ見に行かないといけないため、O(n)の計算量が必要となります。そのため、管理するファイルディスクリプタの数が増えるとパフォーマンスが落ちます。
 また管理できる数が限られているため、その数を超えるときには利用できません。
 次の記事を参考にしました。

poll

 pollは殆どselectと同じですが、次のような違いがあります。

 次の記事を参考にしました。
ファイルディスクリプタについて(5) ~多重I/O「Multiplex I/O」の種類の特徴、使い方
(2/4):CodeZine

Programming UNIX Sockets in C - Frequently Asked Questions: クライアントとサーバ(TCP/SOCK_STREAM)両方に関する質問

epoll

 epollの場合は次の特徴があります。

  • 管理できるディスクリプタの数は無制限
  • select, pollと違って、ディスクリプタの状態がkernel内で管理される
    • いちいちディスクリプタのセットをkernelに送る必要がない
    • kernelが管理しているので、全ループではなく、変わったものに対して通知できる

 上記の特徴からO(1)の計算量で計算できるようです。また、いちいちディスクリプタのセットを送らないので、その分早くなるようですね。
 次の記事を参考にしました。

kqueue

 BSD系のepoll??

まとめ

 以上の特徴により、I/O多重化をする場合、epollがよく使われているようですね。いまいちよくわからないので違っていれば、@shiba_yu36まで教えて下さい。
 その他の非同期I/Oとかforkとかthreadsの特徴も調べてみたいです。