58

ウィキペディアは言う

O（n）で動作する古いシステムコールとは異なり、epollはO（1）で動作します[2]）。

http://en.wikipedia.org/wiki/Epoll

ただし、Linux-2.6.38のfs / eventpoll.cのソースコードは、O（logN）を持つ検索用のRBツリーで実装されているようです。

/*
 * Search the file inside the eventpoll tree. The RB tree operations
 * are protected by the "mtx" mutex, and ep_find() must be called with
 * "mtx" held.
 */
static struct epitem *ep_find(struct eventpoll *ep, struct file *file, int fd)
{

実際、epoll（）の複雑さはO（1）であると言っているmanページは見当たりませんでした。なぜそれはO（1）として知られているのですか？

4

1 に答える 1

27

を探したら、これは理にかなっていますep_find。私はそれで数分しか過ごしませんでした、そして私は見るep_findだけでによって呼ばれepoll_ctlます。

したがって、実際、記述子（EPOLL_CTL_ADD）を追加すると、コストのかかる操作が実行されます。しかし、実際の作業を行う場合（epoll_wait）はそうではありません。最初に記述子を追加するだけです。

結論として、システムコールepollがないため、の複雑さを尋ねるだけでは不十分です。などの個々のepoll複雑さが必要です。epoll_ctlepoll_wait

他のもの

selectを避けて使用する理由は他にもありますepoll。selectを使用する場合、注意が必要な記述子の数がわかりません。したがって、最大のものを追跡し、それにループする必要があります。

rc = select(...);
/* check rc */
for (s = 0; s <= maxfd; s++) {
    if (FD_ISSET(s)) {
        /* ... */
    }
}

今でepollはかなりきれいになっています：

nfds = epoll_wait(epollfd, events, MAX_EVENTS, -1);
/* check nfds */
for (n = 0; n < nfds; ++n) {
    /* events[n].data.fd needs attention */
}
于 2011-06-25T09:55:25.653 に答える