क्या काम हमेशा सबसे उपयुक्त उपयोगकर्ता-स्तरीय थ्रेड शेड्यूलिंग एल्गोरिदम चोरी कर रहा है?

Question

मैं एक थ्रेड पूल के लिए विभिन्न शेड्यूलिंग एल्गोरिदम की जांच कर रहा हूं जिसे मैं कार्यान्वित कर रहा हूं। समस्या की प्रकृति के कारण मैं हल कर रहा हूं, मैं मान सकता हूं कि समानांतर में चल रहे कार्यों स्वतंत्र हैं और किसी भी नए कार्य को नहीं बढ़ाते हैं। कार्य विभिन्न आकारों का हो सकता है।

मैं स्थानीय नौकरी कतारों के लिए लॉक-फ्री डेक का उपयोग करके सबसे लोकप्रिय शेड्यूलिंग एल्गोरिदम "काम चोरी" के लिए तुरंत गया, और मैं इस दृष्टिकोण से अपेक्षाकृत खुश हूं। हालांकि मैं सोच रहा हूं कि क्या कोई आम मामला है जहां काम-चोरी सबसे अच्छा तरीका नहीं है।

इस विशेष समस्या के लिए मेरे पास प्रत्येक व्यक्तिगत कार्य के आकार का एक अच्छा अनुमान है। कार्य-चोरी इस जानकारी का उपयोग नहीं करती है और मैं सोच रहा हूं कि कोई शेड्यूलर है जो इस जानकारी के साथ काम-चोरी के मुकाबले बेहतर भार-संतुलन प्रदान करेगा (जाहिर है उसी दक्षता के साथ)।

एनबी। यह प्रश्न पिछले question से जुड़ा हुआ है।

Answer 1

मैं कार्यों को आगे वितरित करता हूं। उनके अनुमानित चलने वाले समय की जानकारी के साथ आप प्रत्येक धागे के लिए अलग-अलग कतारों में उन्हें वितरित कर सकते हैं।

कार्यों को वितरित करना मूल रूप से knapsack problem है, प्रत्येक कतार में एक ही समय लेना चाहिए।

आपको चलाने के दौरान कतारों को संशोधित करने के लिए आपको कुछ तर्क जोड़ना चाहिए। उदाहरण के लिए वास्तविक चलने वाले समय से निश्चित राशि से अनुमानित चलने का समय अलग होने के बाद पुन: वितरण होना चाहिए।

Answer 2

यह सच है कि कार्य-चोरी शेड्यूलर उस जानकारी का उपयोग नहीं करता है, लेकिन ऐसा इसलिए है क्योंकि यह सैद्धांतिक सीमाएं प्रदान करने के लिए इस पर निर्भर नहीं है (उदाहरण के लिए, यह स्मृति जो इसका उपयोग करती है, श्रमिकों के बीच अपेक्षित कुल संचार और यह भी संभावित समय एक पूरी तरह से सख्त गणना आप यहां पढ़ सकते हैं के रूप में निष्पादित करने के लिए: http://supertech.csail.mit.edu/papers/steal.pdf)

एक दिलचस्प पेपर (कि मैं तुम्हें उपयोग कर सकते हैं आशा: http://dl.acm.org/citation.cfm?id=2442538) वास्तव में घिरे निष्पादन समय का उपयोग करता औपचारिक सबूत प्रदान करने के लिए (जो बनने की कोशिश यथासंभव मूल कार्य-चोरी सीमाओं के करीब)।

और हां, ऐसे मामले हैं जिनमें कार्य-चोरी बेहतर प्रदर्शन नहीं करती है (उदाहरण के लिए, असंतुलित पेड़ की खोज और अन्य विशेष मामलों)। लेकिन उन मामलों के लिए, अनुकूलन किए गए हैं (उदाहरण के लिए केवल एक कार्य लेने के बजाय पीड़ित के डेक के आधे हिस्से की चोरी करके: http://dl.acm.org/citation.cfm?id=571876)।