linux क्या एपोल(), ओ(1) में अपना काम करता है?



network-programming epoll (1)

विकिपीडिया कहता है

पुराने सिस्टम कॉल के विपरीत, जो O (n) पर काम करते हैं, Ooll में संचालित होता है (1) [2])।

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

हालाँकि, Linux-2.6.38 पर fs / eventpoll.c पर स्रोत कोड, लगता है कि यह आरबी के पेड़ को खोजने के लिए लागू किया गया है, जिसमें O (logN)

/*
 * 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)
{

वास्तव में, मैं किसी भी पुरुष पृष्ठ को एपोल की जटिलता () हे (1) कहते हुए नहीं देख सकता था। इसे O (1) के रूप में क्यों जाना जाता है?


एक बार ep_find देखने के बाद यह समझ में आता है। मैंने केवल इसके साथ कुछ मिनट बिताए हैं और मैं देखता हूं कि ep_find को केवल epoll_ctl कहा जाता है।

तो वास्तव में, जब आप डिस्क्रिप्टर ( EPOLL_CTL_ADD ) जोड़ते हैं तो महंगा ऑपरेशन किया जाता है। लेकिन वास्तविक काम करते समय ( epoll_wait ) यह नहीं है। आप केवल शुरुआत में डिस्क्रिप्टर जोड़ते हैं।

अंत में, यह epoll की जटिलता को पूछने के लिए पर्याप्त नहीं है, क्योंकि epoll प्रणाली कॉल नहीं है। आप epoll_ctl , epoll_wait आदि की व्यक्तिगत जटिलताओं को चाहते हैं।

अन्य सामान

से बचने और epoll उपयोग करने के अन्य कारण हैं। चयन का उपयोग करते समय, आपको पता नहीं है कि कितने वर्णनकर्ताओं को ध्यान देने की आवश्यकता है। तो आपको सबसे बड़ा और लूप का ट्रैक रखना चाहिए।

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 */
}




epoll