लर्निंग लेटेंसी: क्युइंग थ्योरी

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

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

विलंबता की घटना को व्यवस्थित रूप से जांचना शुरू किया, जहां तक ​​मुझे पता है, कतारबद्ध प्रणालियों के आगमन के संबंध में - टेलीफोन संचार नेटवर्क। 1909 में A.K Erlang के काम के साथ कतार सिद्धांत शुरू हुआ, जिसमें उन्होंने दिखाया कि Poisson वितरण यादृच्छिक टेलीफोन यातायात के लिए लागू है। एरलैंग ने एक सिद्धांत विकसित किया जिसका उपयोग दशकों से टेलीफोन नेटवर्क को डिजाइन करने के लिए किया जाता है। सिद्धांत हमें सेवा से वंचित करने की संभावना निर्धारित करने की अनुमति देता है। सर्किट स्विच्ड चैनलों के साथ टेलीफोन नेटवर्क के लिए, यदि सभी चैनल व्यस्त हैं और कॉल नहीं किया जा सकता है, तो विफलता हुई। इस घटना की संभावना को नियंत्रित किया जाना था। मैं एक गारंटी चाहता था कि, उदाहरण के लिए, सभी कॉल का 95% सेवा की जाएगी। एर्लैंग के सूत्र यह निर्धारित करना संभव बनाते हैं कि कॉल की अवधि और संख्या ज्ञात होने पर इस गारंटी को पूरा करने के लिए कितने सर्वरों की आवश्यकता है। वास्तव में, यह कार्य केवल गुणवत्ता की गारंटी के बारे में है, और आज भी लोग इसी तरह की समस्याओं को हल करते हैं। लेकिन सिस्टम बहुत अधिक जटिल हो गए हैं। कतारबद्ध सिद्धांत की मुख्य समस्या यह है कि यह अधिकांश संस्थानों में नहीं पढ़ाया जाता है, और कुछ लोग सामान्य एम / एम / 1 कतार ( नीचे संकेतन देखें ) के बाहर के प्रश्न को समझते हैं, लेकिन यह अच्छी तरह से ज्ञात है कि इस प्रणाली की तुलना में जीवन बहुत अधिक जटिल है। इसलिए, मैं प्रस्ताव करता हूं, एम / एम / 1 को दरकिनार करते हुए, तुरंत सबसे दिलचस्प पर जाएं।

औसत मूल्य

यदि आप सिस्टम में संभाव्यता वितरण के बारे में पूर्ण ज्ञान प्राप्त करने का प्रयास नहीं करते हैं, लेकिन सरल प्रश्नों पर ध्यान केंद्रित करते हैं, तो आप दिलचस्प और उपयोगी परिणाम प्राप्त कर सकते हैं। उनमें से सबसे प्रसिद्ध, ज़ाहिर है, लिटिल का प्रमेय है । यह किसी भी इनपुट स्ट्रीम, किसी भी जटिलता के आंतरिक उपकरण और मनमाने ढंग से अनुसूचक के साथ एक प्रणाली पर लागू होता है। केवल आवश्यकता यह है कि सिस्टम स्थिर होना चाहिए: औसत प्रतिक्रिया समय और कतार की लंबाई मौजूद होनी चाहिए, फिर वे एक सरल अभिव्यक्ति से जुड़े होते हैं

$$

$$L = \ lambda W$$

जहाँ $$$एल$ - सिस्टम के माना भाग में औसत समय की संख्या [पीसी], $$$डब्ल्यू$ - औसत समय जिसके लिए अनुरोध सिस्टम के इस भाग से गुजरता है [s], $$$\ lambda$ - सिस्टम को अनुरोधों की प्राप्ति की गति [पीसी / एस]। प्रमेय की ताकत यह है कि इसे सिस्टम के किसी भी हिस्से पर लागू किया जा सकता है: कतार, निष्पादक, कतार + निष्पादक या संपूर्ण नेटवर्क। अक्सर इस प्रमेय का उपयोग लगभग इस तरह किया जाता है: "1Gbit / s स्ट्रीम हमारी ओर बह रही है, और हमने औसत प्रतिक्रिया समय मापा, और यह 10 एमएस है, इसलिए, औसतन हमारे पास उड़ान में 1.25 एमबी है।" तो, यह गणना सही नहीं है। अधिक सटीक रूप से, यह केवल तभी सही है जब सभी अनुरोधों का आकार बाइट्स में समान हो। लिटिल का प्रमेय टुकड़ों में प्रश्नों को गिनता है, बाइट्स में नहीं।

लिटिल के प्रमेय का उपयोग कैसे करें

गणित में, वास्तविक अंतर्दृष्टि प्राप्त करने के लिए साक्ष्य का अध्ययन करना अक्सर आवश्यक होता है। बस यही हाल है। लिटिल का प्रमेय इतना अच्छा है कि मैं यहां प्रमाण का एक स्केच देता हूं। आने वाले ट्रैफ़िक को फ़ंक्शन द्वारा वर्णित किया गया है $$$ए (टी)$ - उस समय लॉग किए गए अनुरोधों की संख्या $$$टी$ । उसी प्रकार $$$डी (टी)$ - उस समय लॉग आउट किए जाने वाले अनुरोधों की संख्या $$$टी$ । अनुरोध का प्रवेश (निकास) का क्षण अपने अंतिम बाइट की प्राप्ति (ट्रांसमिशन) का क्षण है। प्रणाली की सीमाओं को केवल समय के इन उदाहरणों द्वारा निर्धारित किया जाता है, इसलिए, प्रमेय व्यापक रूप से लागू होता है। यदि आप एक ही अक्ष में इन कार्यों के ग्राफ खींचते हैं, तो यह देखना आसान है $$$ए (टी) - डी (टी)$ सिस्टम में समय टी, और में अनुरोधों की संख्या है $$$W_n$ - nth अनुरोध का प्रतिक्रिया समय।

प्रमेय औपचारिक रूप से केवल 1961 में सिद्ध हुआ था, हालाँकि यह संबंध उससे बहुत पहले ही ज्ञात था।

वास्तव में, अगर सिस्टम के भीतर अनुरोधों को फिर से व्यवस्थित किया जा सकता है, तो सब कुछ थोड़ा और अधिक जटिल है, इसलिए सादगी के लिए हम मानते हैं कि ऐसा नहीं होता है। यद्यपि इस मामले में भी प्रमेय सत्य है। अब ग्राफ के बीच के क्षेत्र की गणना करते हैं। ऐसा करने के दो तरीके हैं। सबसे पहले, कॉलम के अनुसार - जैसा कि आमतौर पर अभिन्न लोग सोचते हैं। इस मामले में, यह पता चला है कि इंटीग्रांड टुकड़ों में कतार का आकार है। दूसरे, लाइन द्वारा लाइन - बस सभी अनुरोधों की विलंबता को जोड़ते हुए। यह स्पष्ट है कि दोनों गणना समान क्षेत्र देती हैं, इसलिए वे समान हैं। यदि इस समानता के दोनों हिस्सों को ,t से विभाजित किया जाता है, जिसके लिए हमने क्षेत्र की गणना की है, तो बाईं ओर हमारे पास औसत कतार की लंबाई होगी $$$एल$ (औसत की परिभाषा द्वारा)। दाईं ओर थोड़ा पेचीदा है। हमें अंश और हर में एन के अन्य अनुरोधों को जोड़ना होगा, तब हम सफल होंगे

$$

$$\ frac {\ sum W_i} {\ Delta t} = \ frac {\ sum W_i} {N} \ frac {N} {\ Delta t} = W \ lambda$$

यदि हम पर्याप्त रूप से बड़े ort या रोजगार की एक अवधि पर विचार करते हैं, तो किनारों पर प्रश्न हटा दिए जाते हैं और प्रमेय को सिद्ध किया जा सकता है।

यह कहना महत्वपूर्ण है कि प्रमाण में हमने किसी भी संभाव्यता के किसी भी वितरण का उपयोग नहीं किया है। वास्तव में, लिटिल का प्रमेय एक निर्धारक कानून है! इस तरह के कानूनों को ऑपरेशनल लॉ के कतार सिद्धांत में कहा जाता है। उन्हें सिस्टम के किसी भी हिस्से और विभिन्न यादृच्छिक चर के किसी भी वितरण पर लागू किया जा सकता है। ये कानून एक रचनाकार का निर्माण करते हैं जो नेटवर्क में औसत मूल्यों का विश्लेषण करने के लिए सफलतापूर्वक उपयोग किया जा सकता है। नुकसान यह है कि वे सभी केवल औसत पर लागू होते हैं और वितरण के बारे में कोई ज्ञान नहीं देते हैं।

इस सवाल पर लौटना कि लिटिल के प्रमेय को बाइट्स पर क्यों नहीं लागू किया जा सकता है, मान लीजिए $$$ए (टी)$ और $$$डी (टी)$ अब उन्हें टुकड़ों में नहीं, बल्कि बाइट्स में मापा जाता है। फिर, एक समान तर्क का संचालन करते हुए, हम इसके बजाय प्राप्त करते हैं $$$डब्ल्यू$ अजीब बात यह है कि बाइट्स की कुल संख्या से विभाजित क्षेत्र। यह अभी भी सेकंड है, लेकिन यह एक भारित औसत विलंबता का एक सा है जहां बड़े अनुरोधों को अधिक वजन मिलता है। इस मूल्य को बाइट की औसत विलंबता कहा जा सकता है - जो सामान्य रूप से तार्किक है, क्योंकि हमने टुकड़ों को बाइट्स के साथ बदल दिया है - लेकिन अनुरोध की विलंबता नहीं।

लिटिल के प्रमेय का कहना है कि अनुरोधों की एक निश्चित धारा के साथ, प्रतिक्रिया समय और सिस्टम में अनुरोधों की संख्या आनुपातिक है। यदि सभी अनुरोध समान दिखते हैं, तो शक्ति बढ़ने के बिना औसत प्रतिक्रिया समय को कम नहीं किया जा सकता है। यदि हम पहले से ही प्रश्नों के आकार को जानते हैं, तो हम उनके बीच के क्षेत्र को कम करने के लिए उन्हें फिर से चालू करने का प्रयास कर सकते हैं $$$ए (टी)$ और $$$डी (टी)$ और इसलिए औसत सिस्टम प्रतिक्रिया समय। इस विचार को जारी रखते हुए, हम यह साबित कर सकते हैं कि सबसे छोटा प्रसंस्करण समय और सबसे छोटा शेष प्रसंस्करण समय एल्गोरिदम क्रमशः एक सर्वर के लिए इसके साथ भीड़ की संभावना के बिना न्यूनतम औसत प्रतिक्रिया समय देते हैं। लेकिन एक साइड इफेक्ट है - बड़े अनुरोधों को अनिश्चित काल तक संसाधित नहीं किया जा सकता है। घटना को "भुखमरी" कहा जाता है और यह नियोजन की निष्पक्षता की अवधारणा के साथ निकटता से संबंधित है, जिसे पिछली निर्धारण पोस्ट से सीखा जा सकता है : मिथक और वास्तविकता ।

लिटिल के नियम को समझने से जुड़ा एक और आम जाल है। एक एकल-थ्रेडेड सर्वर है जो उपयोगकर्ता के अनुरोधों को पूरा करता है। मान लीजिए कि हमने किसी तरह एल को मापा - इस सर्वर के लिए कतार में औसत संख्या, और एस - सर्वर द्वारा एक अनुरोध के लिए औसत समय। अब एक नए आने वाले अनुरोध पर विचार करें। औसतन, वह L प्रश्नों को अपने आगे देखता है। उनमें से प्रत्येक की सेवा में औसतन S सेकंड लगता है। यह पता चला है कि औसत प्रतीक्षा समय $$$डब्ल्यू = एल एस$ । लेकिन प्रमेय द्वारा यह पता चला है कि $$$W = L / \ lambda$ । यदि हम भावों की बराबरी करते हैं, तो हम बकवास देखते हैं: $$$S = 1 / \ lambda$ । इस तर्क में क्या गलत है?

1. पहली चीज जो आपकी आंख को पकड़ती है: प्रमेय द्वारा प्रतिक्रिया समय एस पर निर्भर नहीं करता है। वास्तव में, यह करता है। यह सिर्फ इतना है कि औसत कतार की लंबाई पहले से ही इसे ध्यान में रखती है: जितनी तेजी से सर्वर, कतार की लंबाई और प्रतिक्रिया समय उतना ही कम होगा।
2. हम एक ऐसी प्रणाली पर विचार करते हैं जिसमें कतारें हमेशा के लिए जमा नहीं होती हैं, लेकिन नियमित रूप से रीसेट हो जाती हैं। इसका मतलब है कि सर्वर का उपयोग 100% से कम है और हम सभी आवक अनुरोधों को छोड़ देते हैं, और उसी औसत गति से जिसके साथ ये अनुरोध पहुंचे, जिसका अर्थ है कि औसत रूप से एकल अनुरोध को संसाधित करने में S सेकंड नहीं लगता है, लेकिन अधिक $$$1 / \ lambda$ सेकंड, बस क्योंकि कभी-कभी हम किसी भी अनुरोध को संसाधित नहीं करते हैं। तथ्य यह है कि नुकसान के बिना किसी भी स्थिर खुली प्रणाली में, थ्रूपुट सर्वर की गति पर निर्भर नहीं करता है, यह केवल इनपुट स्ट्रीम द्वारा निर्धारित किया जाता है।
3. यह धारणा कि आने वाला अनुरोध सिस्टम में समय-औसत संख्या अनुरोधों को देखता है, हमेशा सही नहीं होता है। काउंटरएक्सप्लांट: आने वाले अनुरोध समय-समय पर आते हैं, और हम अगले आने से पहले प्रत्येक अनुरोध को संसाधित करने का प्रबंधन करते हैं। वास्तविक समय प्रणालियों के लिए एक विशिष्ट तस्वीर। एक आवक अनुरोध हमेशा सिस्टम में शून्य अनुरोध देखता है, लेकिन औसतन सिस्टम में स्पष्ट रूप से शून्य से अधिक अनुरोध होते हैं। यदि अनुरोध पूरी तरह से यादृच्छिक समय पर आते हैं, तो वे वास्तव में "अनुरोधों की औसत संख्या देखते हैं । "
   
   
   
4. हमने इस बात पर ध्यान नहीं दिया कि एक निश्चित संभावना के साथ सर्वर में पहले से ही एक अनुरोध हो सकता है जिसे "विस्तारित" करने की आवश्यकता है। सामान्य स्थिति में, "सेवा के बाद" का औसत समय सेवा के प्रारंभिक समय से भिन्न होता है, और कभी-कभी, विरोधाभासी रूप से , यह बहुत लंबा हो सकता है। हम इस मुद्दे पर अंत में लौटेंगे जब हम माइक्रोबर्स्ट पर चर्चा करते हैं, देखते रहें।

तो, लिटिल के प्रमेय को बड़े और छोटे सिस्टम में, कतारों में, सर्वर पर और एकल प्रसंस्करण थ्रेड्स पर लागू किया जा सकता है। लेकिन इन सभी मामलों में, अनुरोधों को आमतौर पर एक या दूसरे तरीके से वर्गीकृत किया जाता है। विभिन्न उपयोगकर्ताओं के अनुरोध, विभिन्न प्राथमिकताओं के अनुरोध, विभिन्न स्थानों से आने वाले अनुरोध या विभिन्न प्रकार के अनुरोध। इस मामले में, कक्षाओं द्वारा एकत्रित जानकारी रोचक नहीं है। हां, मिश्रित अनुरोधों की औसत संख्या और उन सभी के लिए औसत प्रतिक्रिया समय फिर से आनुपातिक हैं। लेकिन क्या होगा अगर हम अनुरोधों के एक निश्चित वर्ग के लिए औसत प्रतिक्रिया समय जानना चाहते हैं? हैरानी की बात है, लिटिल के प्रमेय को प्रश्नों के एक विशिष्ट वर्ग पर लागू किया जा सकता है। इस मामले में, आपको लेने की आवश्यकता है $$$\ lambda$ वह दर जिस पर यह वर्ग अनुरोध करता है, सभी नहीं। एक के रूप में $$$एल$ और $$$डब्ल्यू$ - सिस्टम के जांच वाले हिस्से में इस वर्ग के अनुरोधों की संख्या और निवास समय का औसत मूल्य।

खुली और बंद प्रणाली

यह ध्यान देने योग्य है कि बंद सिस्टमों के लिए तर्क के "गलत" लाइन निष्कर्ष के लिए अग्रणी है $$$S = 1 / \ lambda$ सच निकलता है। बंद प्रणालियां वे प्रणालियां हैं जिनमें अनुरोध बाहर से नहीं आते हैं और बाहर नहीं जाते हैं, लेकिन अंदर प्रसारित होते हैं। या, अन्यथा, फीडबैक सिस्टम: जैसे ही अनुरोध सिस्टम को छोड़ता है, एक नया अनुरोध इसकी जगह लेता है। ये प्रणालियां इसलिए भी महत्वपूर्ण हैं क्योंकि किसी भी खुली प्रणाली को बंद प्रणाली में डूबे हुए माना जा सकता है। उदाहरण के लिए, आप साइट को एक खुली प्रणाली के रूप में मान सकते हैं, जिसमें साइट के संपूर्ण दर्शकों के साथ मिलकर एक बंद प्रणाली के रूप में अनुरोधों को लगातार डाला जाता है, संसाधित किया जाता है और वापस ले लिया जाता है या। तब वे आमतौर पर कहते हैं कि उपयोगकर्ताओं की संख्या निर्धारित है, और वे या तो अनुरोध के जवाब की प्रतीक्षा करते हैं या "सोचते हैं": उन्होंने अपना पेज प्राप्त कर लिया है और अभी तक लिंक पर क्लिक नहीं किया है। इस घटना में कि समय हमेशा शून्य होता है, सिस्टम को बैच सिस्टम भी कहा जाता है।

बंद सिस्टम के लिए लिटिल का नियम वैध है यदि बाहरी आवक की गति $$$\ lambda$ (वे एक बंद प्रणाली में नहीं हैं) सिस्टम बैंडविड्थ के साथ बदल देते हैं। यदि हम एक बैच सिस्टम में ऊपर चर्चा किए गए एकल-थ्रेडेड सर्वर को लपेटते हैं, तो हम प्राप्त करते हैं $$$S = 1 / \ lambda$ और 100% रीसाइक्लिंग। अक्सर सिस्टम पर इस तरह का एक नज़र अप्रत्याशित परिणाम देता है। 90 के दशक में, यह इंटरनेट का यह दृश्य उपयोगकर्ताओं के साथ एक एकल प्रणाली के रूप में एक साथ था जिसने घातीय के अलावा वितरण के अध्ययन को प्रोत्साहन दिया । हम आगे के वितरण पर चर्चा करेंगे, लेकिन यहाँ हम ध्यान दें कि उस समय लगभग हर जगह और हर जगह घातीय के रूप में माना जाता था, और यह भी कुछ औचित्य पाया गया था, और न केवल "अन्यथा बहुत जटिल" की भावना में एक बहाना। हालांकि, यह पता चला कि सभी व्यावहारिक रूप से महत्वपूर्ण वितरणों में समान रूप से लंबी पूंछ नहीं हैं, और वितरण पूंछ के ज्ञान की कोशिश की जा सकती है। लेकिन अभी के लिए, चलो औसत मूल्यों पर लौटते हैं।

सापेक्ष प्रभाव

मान लें कि हमारे पास एक खुली प्रणाली है: एक जटिल नेटवर्क या एक साधारण एकल-थ्रेडेड सर्वर - इससे कोई फर्क नहीं पड़ता। यदि हम अनुरोधों के आगमन को दोगुना कर देते हैं और उनके प्रसंस्करण की गति को आधा कर देते हैं, तो क्या होगा - उदाहरण के लिए, सभी सिस्टम घटकों की क्षमता को दोगुना करके? सिस्टम में उपयोग, थ्रूपुट, औसत अनुरोधों की औसत संख्या और औसत प्रतिक्रिया समय कैसे बदलेंगे? एकल-थ्रेडेड सर्वर के लिए, आप सूत्र लेने की कोशिश कर सकते हैं, उन्हें "माथे पर" लागू कर सकते हैं और परिणाम प्राप्त कर सकते हैं, लेकिन एक मनमाना नेटवर्क के साथ क्या करना है? सहज समाधान इस प्रकार है। मान लीजिए कि समय दोगुना हो गया है, तो हमारे "त्वरित संदर्भ प्रणाली" में सर्वरों की गति और अनुरोधों के प्रवाह में बदलाव नहीं हुआ; तदनुसार, त्वरित समय में सभी मापदंडों में पहले जैसे ही मान हैं। दूसरे शब्दों में, किसी भी प्रणाली के सभी "चलती भागों" का त्वरण घड़ी के त्वरण के बराबर है। अब हम मानों को एक सामान्य समय के साथ सिस्टम में बदल देंगे। आयामहीन मात्राएँ (उपयोग और अनुरोधों की औसत संख्या) नहीं बदलेगी। मान जिनके आयाम में पहली डिग्री के समय कारक शामिल हैं वे आनुपातिक रूप से भिन्न होते हैं। [अनुरोध / s] के थ्रूपुट को दोगुना किया जाएगा, और प्रतिक्रिया और प्रतीक्षा समय [s] आधा किया जाएगा।

इस परिणाम की दो तरह से व्याख्या की जा सकती है:

1. K समय से त्वरित होने वाली प्रणाली कार्य के प्रवाह को अधिक बार पचा सकती है, और औसत प्रतिक्रिया समय k समय कम के साथ।
2. हम कह सकते हैं कि शक्ति में परिवर्तन नहीं हुआ, लेकिन बस कार्यों के आकार में कई बार कमी आई। यह पता चला है कि हम सिस्टम को समान लोड भेज रहे हैं, लेकिन छोटे टुकड़ों में sawn। और ... ओह, एक चमत्कार! औसत प्रतिक्रिया समय कम हो गया है!

एक बार फिर, मैं ध्यान देता हूं कि यह व्यापक श्रेणी के सिस्टम के लिए सही है, न कि केवल एक साधारण सर्वर के लिए। व्यावहारिक दृष्टिकोण से, केवल दो समस्याएं हैं:

1. सिस्टम के सभी हिस्सों को आसानी से त्वरित नहीं किया जा सकता है। हम कुछ को प्रभावित नहीं कर सकते। उदाहरण के लिए, प्रकाश की गति।
2. सभी कार्यों को असीम रूप से छोटे और छोटे लोगों में विभाजित नहीं किया जा सकता है, क्योंकि जानकारी को एक बिट से कम के भागों में स्थानांतरित करने के लिए नहीं सीखा गया है।

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

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

वितरण

कतार लगाने का क्या कारण है? जाहिर है, सिस्टम में पर्याप्त क्षमता नहीं है, और अनुरोधों की अधिकता जमा हो रही है? सच नहीं है! कतारें उन प्रणालियों में भी उत्पन्न होती हैं जहां पर्याप्त संसाधन होते हैं। यदि पर्याप्त क्षमता नहीं है, तो सिस्टम, जैसा कि सिद्धांतकार कहते हैं, स्थिर नहीं है। कतार लगाने के दो मुख्य कारण हैं: अनुरोधों की अनियमितता और अनुरोधों के आकार की परिवर्तनशीलता। हमने पहले ही एक उदाहरण की जांच की है जिसमें इन दोनों कारणों को समाप्त कर दिया गया है: एक वास्तविक समय प्रणाली जहां समान आकार के अनुरोध समय-समय पर सख्ती से आते हैं। एक कतार कभी नहीं बनती। कतार में औसत प्रतीक्षा समय शून्य है। , , , . , .

A/S/k/K, A — , S — , k — , K — (, ). , M/M/1 : M (Markovian Memoryless) , . : $$$\lambda$ — — , : . M , μ . , , . , 4- . , , : G — (, , ), D — deterministic. C — D/D/1. , 1909 ., — M/D/1. — M/G/k k>1, M/G/1 1930-.

?

, , , , , . , . , failure rate . , , : , . failure rate function, . , «» , . , : , . , failure rate — , , - , — . , , , , , . « ».

Failure rate . — . Failure rate , , , . failure rate, , , . failure rate, , , . , , , software hardware? : ? . , , - . ? , — . ( failure rate) . « » .

, , failure rate, , , unix- . , .

RTMR , . LWTrace - . . , . , $$$\mathbf{P}\{S>x\}$ . , failure rate , , : .



$$$\mathbf{P}\{S>x\} = x^{-a}$ , — . , « », 80/20: , . . , . , RTMR -, , . $$$a=1.16$ , 80/20: 20% 80% .

, . . , , , - . , — . « » , « » — . : , ? , ( , ), . , 0 . , , $$$\mu N_1$ $$$\lambda N_0$ । , , — . . , . M/M/1 $$$\mathbf{P}\{Q=i\} = (1 - \rho) \rho^i$ जहाँ $$$\rho = \lambda / \mu$ - यह सर्वर का उपयोग है। कहानी का अंत। प्रस्तुति के दौरान, मैंने मान्यताओं की एक सभ्य मात्रा को याद किया और अवधारणाओं के प्रतिस्थापन के एक जोड़े को बनाया, लेकिन सार, मुझे आशा है, पीड़ित नहीं हुआ।

यह समझना महत्वपूर्ण है कि यह दृष्टिकोण केवल तभी काम करता है जब मशीन की वर्तमान स्थिति पूरी तरह से इसके आगे के व्यवहार को निर्धारित करती है, और यह कैसे इस राज्य में मिला की कहानी महत्वपूर्ण नहीं है। एक परिमित राज्य मशीन की रोजमर्रा की समझ के लिए, यह बिना कहे चला जाता है - आखिरकार, यह उसके लिए एक शर्त है। लेकिन एक स्टोकेस्टिक प्रक्रिया के लिए, यह इस प्रकार है कि सभी वितरण घातीय होना चाहिए, क्योंकि केवल उनके पास मेमोरी नहीं है - उनके पास लगातार विफलता दर है।

यह कहना भी महत्वपूर्ण है कि अगर हम संतुलन वितरण को जानते हैं तो सिस्टम के बारे में अन्य सभी जानकारी प्राप्त करना आसान है। सिस्टम में प्रश्नों की औसत संख्या इस वितरण का औसत है। औसत प्रतिक्रिया समय का पता लगाने के लिए, हम प्रश्नों की संख्या के लिए थोड़ा प्रमेय लागू करते हैं। प्रतिक्रिया समय का वितरण थोड़ा और अधिक मुश्किल है, लेकिन कुछ कार्यों में भी आप यह पता लगा सकते हैं $$$\ mathbf {P} \ {response \ _time> t \} = e ^ {- (\ mu- \ lambda) t}$ और औसत प्रतिक्रिया समय क्या है $$$1 / (\ mu- \ lambda)$ ।

असीमित प्रतिक्रिया समय

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

स्केलिंग और वारंटियाँ

अब जब हमारे पास सिस्टम का विश्लेषण करने का एक शक्तिशाली तरीका है, तो हम इसे विभिन्न कार्यों पर लागू करने और लाभों को प्राप्त करने का प्रयास कर सकते हैं। इस तरह 20 वीं शताब्दी के उत्तरार्ध में बड़े पैमाने पर सेवा का सिद्धांत विकसित हुआ। आइए समझने की कोशिश करें कि क्या हासिल किया गया था। शुरू करने के लिए, आइए हम उन कार्यों पर लौटते हैं, जिन्हें एर्लांग ने हल किया था। ये कार्य हैं एम / एम / के / के और के / एम / एम / के, जिसमें हम विफलता की संभावना को सीमित करना चाहेंगे। यह पता चला है कि उनके लिए मार्कोव श्रृंखला का निर्माण करना मुश्किल नहीं है। अंतर यह है कि जैसे-जैसे कार्यों को जोड़ा जाता है, एक रिवर्स संक्रमण की संभावना बढ़ जाती है, क्योंकि कार्यों को समानांतर में संसाधित किया जाना शुरू होता है, लेकिन जब कार्यों की संख्या सर्वरों की संख्या के बराबर हो जाती है, तो संतृप्ति होती है। इसके अलावा, M / M / k / k के लिए, नेटवर्क समाप्त होता है, ऑटोमेटन वास्तव में परिमित हो जाता है, और अंतिम राज्य में आने वाले सभी अनुरोधों को अस्वीकार कर दिया जाता है। इस घटना की संभावना बस उस संभावना के बराबर है जो हम अंतिम अवस्था में हैं।

एम / एम / के लिए, स्थिति अधिक जटिल है, अनुरोध पंक्तिबद्ध हैं, नए राज्य दिखाई देते हैं, लेकिन एक रिवर्स संक्रमण की संभावना नहीं बढ़ती है - सभी सर्वर पहले से ही काम कर रहे हैं। नेटवर्क अनंत हो जाता है, जैसा कि M / M / 1 के लिए है। वैसे, यदि सिस्टम में अनुरोधों की संख्या सीमित है, तो श्रृंखला में हमेशा राज्यों की एक सीमित संख्या होगी और एक रास्ता या कोई अन्य इसे हल किया जाएगा, जिसे अंतहीन चेन के बारे में नहीं कहा जा सकता है। बंद प्रणालियों में, श्रृंखलाएं हमेशा परिमित रहती हैं। एम / एम / के / के और के / एम / एम / के लिए वर्णित सर्किट को हल करते हुए, हम क्रमशः फॉर्मूला बी और एर्लांग सूत्र सी पर पहुंचते हैं। वे बल्कि भारी हैं, मैं उन्हें नहीं दूंगा, लेकिन उनकी मदद से आप अंतर्ज्ञान के विकास के लिए एक दिलचस्प परिणाम प्राप्त कर सकते हैं, जिसे स्क्वायर रूट स्टाफिंग नियम कहा जाता है। मान लीजिए कि प्रति सेकंड अनुरोधों के कुछ दिए गए इनपुट स्ट्रीम λ के साथ एक एम / एम / के सिस्टम है। मान लीजिए कि लोड कल तक दोगुना होना चाहिए। सवाल यह है: सर्वर की संख्या कैसे बढ़ाई जाए ताकि प्रतिक्रिया समय समान रहे? सर्वरों की संख्या को दोगुना करने की आवश्यकता है, है ना? यह बिल्कुल नहीं पता चला है। याद करें कि हमने पहले ही देख लिया है: यदि आप समय (सर्वर और लॉगिन) को आधा करके गति बढ़ाते हैं, तो औसत प्रतिक्रिया समय आधा घट जाता है। कई धीमे और एक तेज सर्वर एक ही चीज नहीं हैं, लेकिन फिर भी कंप्यूटिंग शक्ति समान है। विशेष रूप से, एम / एम / 1 के लिए, उदाहरण के लिए, प्रतिक्रिया समय "मुफ्त क्षमता" की मात्रा के विपरीत आनुपातिक है $$$\ mu - \ lambda$ और केवल इस वॉल्यूम से निर्धारित होता है। प्रवाह और प्रसंस्करण शक्ति दोनों को दोगुना करने पर, सिस्टम की मुक्त क्षमता दोगुनी हो जाती है: $$$2 \ mu - 2 \ lambda$ । ऐसा लग सकता है कि समस्या को हल करने के लिए आपको बस मुफ्त क्षमता को बचाने की आवश्यकता है, लेकिन एम / एम / के में प्रतिक्रिया समय पहले से ही अधिक जटिल एर्लांग सूत्र द्वारा निर्धारित किया गया है। यह पता चलता है कि उसी प्रतिक्रिया समय को बनाए रखने के लिए "व्यस्त सर्वर" की संख्या के वर्गमूल के अनुपात में नि: शुल्क क्षमता बनाए रखी जानी चाहिए। "व्यस्त सर्वर" की संख्या का अर्थ है उपयोग द्वारा गुणा किए गए सर्वरों की कुल संख्या: यह स्थिर संचालन के लिए आवश्यक सर्वरों की न्यूनतम संख्या है।

इस नियम का उपयोग करते हुए, कभी-कभी वे यह बताने का प्रयास करते हैं कि सर्वर के साथ क्लस्टर का विस्तार कैसे किया जाए। लेकिन इस भ्रम में न रहें कि कोई भी क्लस्टर M / M / k सिस्टम है। उदाहरण के लिए, यदि आपके इनपुट पर एक बैलेंसर है जो सर्वरों को कतारों में अनुरोध भेजता है, तो यह अब M / M / k नहीं है, क्योंकि M / M / k का तात्पर्य एक सामान्य कतार से है जिससे सर्वर रिक्वेस्ट तब निकालते हैं जब वे रिलीज़ होती हैं। लेकिन यह मॉडल उपयुक्त है, उदाहरण के लिए, एक सामान्य फीफो कतार के साथ थ्रेड पूल के लिए। हालांकि, इस मामले में भी, यह याद रखने योग्य है कि यह नियम उस मामले के लिए एक अनुमान है जब बहुत सारे थ्रेड होते हैं। वास्तव में, यदि आपके पास 10 से अधिक धागे हैं, तो आप सुरक्षित रूप से मान सकते हैं कि उनमें से बहुत सारे हैं। खैर, सर्वव्यापी घातांक वितरण के बारे में मत भूलना: सभी वितरणों की घातांकता को संभालने के बिना, नियम भी काम नहीं करता है।

नेटवर्क प्रतिक्रिया समय

अंततः, ब्याज की एक नेटवर्क M / M / k है जो कम से कम एक श्रृंखला में जुड़ा हुआ है, क्योंकि हम वितरित सिस्टम बनाते हैं। नेटवर्क का अध्ययन करने के लिए, मैं एक रचनाकार रखना चाहूंगा: ज्ञात तत्वों को ब्लॉकों में जोड़ने के लिए सरल और स्पष्ट नियम। नियंत्रण सिद्धांत में, उदाहरण के लिए, ऐसे ट्रांसफर फ़ंक्शन हैं, जिन्हें सीरियल या समानांतर कनेक्शन के साथ समझा जाता है। यहां, किसी भी नोड से आउटपुट स्ट्रीम में बहुत जटिल वितरण होता है, एम / एम / के अपवाद के साथ, जो कि प्रसिद्ध बर्क प्रमेय के अनुसार, एक स्वतंत्र पॉइसन स्ट्रीम का उत्पादन करता है। यह अपवाद, जैसा कि आप अनुमान लगा सकते हैं, मुख्य रूप से उपयोग किया जाता है।

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

1. संभाव्य रूटिंग एल्गोरिदम। नोड द्वारा दिया गया अनुरोध ज्ञात संभावना के साथ अगले यादृच्छिक रूप से चयन करता है। यह उतना बुरा नहीं है जितना यह लग सकता है, क्योंकि "अनुरोध वर्गों" का उपयोग करना संभव है: कहते हैं कि सभी वासियों के अनुरोध सर्वर नंबर 1 पर आते हैं, फिर सर्वर नंबर 2 पर और फिर नेटवर्क से बाहर जाते हैं, और पेटी के अनुरोध सर्वर नंबर 2 पर आते हैं। , और फिर समान संभावना के साथ सर्वर नंबर 1 या नंबर 3 पर जाएं और बाहर निकलें। यही है, सभी संक्रमणों को यादृच्छिक होने की आवश्यकता नहीं है, कुछ या सभी में 100% संभावना हो सकती है।
2. क्लेनक्रॉक की स्वतंत्रता का अनुमान। अनुरोध प्रसंस्करण समय अनुरोध के इतिहास या वर्ग पर निर्भर नहीं कर सकता है, लेकिन केवल सर्वर द्वारा निर्धारित किया जाता है, और जब अनुरोध फिर से उसी सर्वर से गुजरता है, तो इसे हर बार यादृच्छिक रूप से चुना जाता है। वास्तव में, विभिन्न सर्वरों में उपयोग किए जाने वाले अनुरोध के आकार को सेट करने का कोई तरीका नहीं है, और सेवा समय केवल सर्वर द्वारा निर्धारित किया जाता है। आप इस सीमा के आसपास जाने की कोशिश भी कर सकते हैं। इसके लिए, प्रायिकतात्मक रूटिंग का उपयोग आमतौर पर किया जाता है और एक लूप को उसी सर्वर पर कुछ संभावना के साथ वापस करने के लिए बनाया जाता है - जैसे कि वे अनुरोध को पुनः आरंभ करते हैं। मेरी राय में, यह एक अजीब चाल है, क्योंकि ऐसा अनुरोध कतार में फिर से प्रवेश करता है, और तुरंत नहीं किया जाता है, लेकिन कुछ कार्यों के लिए यह महत्वपूर्ण नहीं है।
3. Poisson इनपुट ट्रैफ़िक और सभी नोड्स पर घातीय सेवा समय।

जैक्सन नेटवर्क उदाहरण।

यह ध्यान देने योग्य है कि प्रतिक्रिया की उपस्थिति में, एक पॉइसन स्ट्रीम प्राप्त नहीं होती है, क्योंकि प्रवाह अन्योन्याश्रित होते हैं। प्रतिक्रिया नोड के आउटपुट में, एक गैर-पॉइसन स्ट्रीम भी प्राप्त की जाती है, और परिणामस्वरूप, सभी प्रवाह गैर-पॉइसन बन जाते हैं। हालांकि, एक आश्चर्यजनक तरीके से, यह पता चला है कि ये सभी गैर-पॉइज़न प्रवाह ठीक उसी तरह व्यवहार करते हैं जैसे उपरोक्त प्रतिबंधों से संतुष्ट होने पर पॉइसन प्रवाह (ओह, यह संभावना सिद्धांत)। और फिर दोबारा हमें एक उत्पाद-रूप समाधान मिलता है। ऐसे नेटवर्क को जैक्सन नेटवर्क कहा जाता है , वे फीडबैक प्रदान कर सकते हैं और इसलिए, किसी भी सर्वर पर कई विज़िट करते हैं। ऐसे अन्य नेटवर्क हैं जिनमें अधिक स्वतंत्रता की अनुमति है, लेकिन परिणामस्वरूप, नेटवर्क के संबंध में क्वीजिंग सिद्धांत की सभी महत्वपूर्ण विश्लेषणात्मक उपलब्धियां इनपुट और उत्पाद-रूप समाधान में पॉइज़न प्रवाह शामिल हैं, जो इस सिद्धांत की आलोचना का विषय बन गया और 90 के दशक में नेतृत्व किया। अन्य सिद्धांतों का विकास, और वास्तव में वितरण की आवश्यकता का अध्ययन और उनके साथ कैसे काम करना है।

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

कोई नहीं वितरण

जिन परिणामों के बारे में मैंने बात की, वे सभी घातीय वितरण से संबंधित थे, लेकिन मैंने यह भी उल्लेख किया है कि वास्तविक वितरण अलग हैं। एक भावना है कि यह पूरा सिद्धांत काफी बेकार है। यह पूरी तरह सच नहीं है। इस गणितीय उपकरण में अन्य वितरणों को एकीकृत करने का एक तरीका है, इसके अलावा, व्यावहारिक रूप से किसी भी वितरण, लेकिन यह हमें कुछ खर्च करेगा। कुछ दिलचस्प मामलों के अपवाद के साथ, एक स्पष्ट रूप में समाधान प्राप्त करने का अवसर खो जाता है, उत्पाद-रूप समाधान खो जाता है, और इसके साथ निर्माता: प्रत्येक समस्या को मार्कोव श्रृंखला का उपयोग करके पूरी तरह से खरोंच से हल किया जाना चाहिए। सिद्धांत के लिए यह एक बड़ी समस्या है, लेकिन व्यवहार में इसका मतलब केवल संख्यात्मक विधियों का अनुप्रयोग है और यह बहुत अधिक जटिल और वास्तविकता समस्याओं के करीब हल करना संभव बनाता है।

चरण विधि

विचार सरल है। मार्कोव श्रृंखला हमें एक राज्य के अंदर स्मृति रखने की अनुमति नहीं देती है, इसलिए सभी संक्रमणों के बीच समय के घातीय वितरण के साथ सभी संक्रमण यादृच्छिक होना चाहिए। लेकिन क्या होगा अगर राज्य को कई सबस्टेशनों में विभाजित किया जाए? यदि हम पूरी संरचना को मार्कोव श्रृंखला के रूप में रखना चाहते हैं, और हम वास्तव में चाहते हैं, तो सबस्टेशनों के बीच के बदलावों में एक घातांक वितरण होना चाहिए, क्योंकि हम जानते हैं कि ऐसी श्रृंखलाओं को कैसे हल किया जाए। यदि वे श्रृंखला में व्यवस्थित होते हैं, तो उप-अवस्थाओं को अक्सर चरण कहा जाता है, और विभाजन प्रक्रिया को चरण विधि कहा जाता है।

सबसे सरल उदाहरण है। अनुरोध को कई चरणों में संसाधित किया जाता है: पहला, उदाहरण के लिए, हम डेटाबेस से आवश्यक डेटा पढ़ते हैं, फिर हम कुछ गणना करते हैं, फिर हम डेटाबेस को परिणाम लिखते हैं। मान लीजिए कि इन तीनों चरणों में समय का समान घातांक वितरण है। तीनों चरणों के पारगमन समय का क्या वितरण एक साथ होता है? यह एर्लांग का वितरण है।



लेकिन क्या होगा अगर आप कई, कई छोटे समान चरण बनाते हैं? सीमा में, हम एक नियतात्मक वितरण प्राप्त करते हैं। यही है, एक श्रृंखला का निर्माण करके, आप वितरण की परिवर्तनशीलता को कम कर सकते हैं।

क्या परिवर्तनशीलता को बढ़ाना संभव है? आसानी से। एक चरण श्रृंखला के बजाय, हम वैकल्पिक श्रेणियों का उपयोग करते हैं, यादृच्छिक रूप से उनमें से एक का चयन करते हैं। एक उदाहरण है। लगभग सभी अनुरोधों को जल्दी से निष्पादित किया जाता है, लेकिन एक छोटा मौका है कि एक बड़ा अनुरोध आएगा, जिसमें एक लंबा समय लगता है। इस तरह के वितरण में विफलता की दर कम होगी। अब हम प्रतीक्षा करते हैं, अधिक संभावना यह है कि अनुरोध दूसरी श्रेणी में आया।



चरणों की विधि को विकसित करने के लिए जारी रखते हुए, सिद्धांतकारों ने पाया है कि वितरण का एक वर्ग है जिसके साथ आप किसी भी सटीकता के साथ मनमाने ढंग से गैर-नकारात्मक वितरण के साथ संपर्क कर सकते हैं! कॉक्सियन डिस्टिब्यूशन चरण विधि द्वारा बनाया गया है, केवल हमें सभी चरणों से गुजरने की आवश्यकता नहीं है, प्रत्येक चरण के बाद पूरा होने की कुछ संभावना है।



इस तरह के वितरण का उपयोग गैर-पॉइसन इनपुट स्ट्रीम उत्पन्न करने और गैर-घातीय सेवा समय बनाने के लिए दोनों किया जा सकता है। यहां, उदाहरण के लिए, सेवा समय के लिए एर्लांग वितरण के साथ एम / ई 2/1 प्रणाली के लिए मार्कोव श्रृंखला है। राज्य संख्याओं (एन, एस) की एक जोड़ी द्वारा निर्धारित किया जाता है, जहां एन कतार की लंबाई है, और एस उस चरण की संख्या है जहां सर्वर स्थित है: पहला या दूसरा। N और s के सभी संयोजन संभव हैं। आने वाले संदेश केवल n बदलते हैं, और चरणों के पूरा होने पर, वे दूसरे चरण के पूरा होने के बाद कतार की लंबाई को वैकल्पिक और घटाते हैं।

आपके पास माइक्रोबर्स्ट हैं!

क्या इसकी आधी क्षमता से भरी प्रणाली धीमी हो सकती है? पहले परीक्षण विषय के रूप में, हम एम / जी / 1 तैयार करते हैं। दिया गया: सेवा समय के इनलेट और मनमाने ढंग से वितरण में पॉइसन प्रवाह। संपूर्ण प्रणाली के माध्यम से एकल अनुरोध के मार्ग पर विचार करें। एक बेतरतीब ढंग से आने वाला अनुरोध अनुरोधों की औसत समय संख्या को अपने सामने कतार में देखता है $$$\ mathbf {E} [N_Q]$ । उनमें से प्रत्येक के लिए औसत प्रसंस्करण समय $$$\ mathbf {E} [S]$ । निपटान के बराबर संभावना के साथ $$$\ rho$ , सर्वर में एक और अनुरोध है, जो पहले समय में "सेवित" होना चाहिए $$$\ mathbf {E} [S_e]$ । संक्षेप में, हमें लगता है कि कतार में कुल प्रतीक्षा समय है $$$\ mathbf {E} [T_Q] = \ mathbf {E} [N_Q] \ mathbf {E} [S] + \ rho \ mathbf {E} [S_e]$ । लिटिल के प्रमेय द्वारा $$$\ mathbf {E} [N_Q] = \ lambda \ mathbf {E} [T_Q]$ ; संयोजन, हम प्राप्त करते हैं:

$$

$$\ mathbf {E} [T_Q] = \ frac {\ rho} {1- \ rho} \ mathbf {E} [S_e]$$

यही है, कतार में प्रतीक्षा समय दो कारकों द्वारा निर्धारित किया जाता है। पहला सर्वर उपयोग का प्रभाव है, और दूसरा सेवा के बाद के समय का औसत है। दूसरे कारक पर विचार करें। किसी बिंदु पर पहुंचने का अनुरोध $$$टी$ देखता है कि देखभाल के बाद समय लगता है $$$S_e (t)$ ।



औसत समय $$$\ mathbf {E} [S_e]$ फ़ंक्शन के औसत मूल्य से निर्धारित होता है $$$S_e (t)$ , वह है, कुल समय द्वारा विभाजित त्रिभुजों का क्षेत्र। यह स्पष्ट है कि हम अपने आप को एक "मध्य" त्रिभुज तक सीमित कर सकते हैं $$$\ mathbf {E} [S_e] = \ mathbf {E} [S ^ 2] / 2 \ mathbf {E} [S]$ । यह बहुत अप्रत्याशित है। हमने पाया है कि सेवा के बाद का समय न केवल सेवा समय के औसत मूल्य से निर्धारित होता है, बल्कि इसकी परिवर्तनशीलता द्वारा भी निर्धारित किया जाता है। स्पष्टीकरण सरल है। एक लंबे अंतराल में गिरने की संभावना $$$एस$ अधिक, यह वास्तव में इस अंतराल की अवधि एस के लिए आनुपातिक है। यह प्रसिद्ध प्रतीक्षा समय विरोधाभास, या निरीक्षण विरोधाभास की व्याख्या करता है। लेकिन वापस एम / जी / 1 के लिए। यदि आपने वह सब कुछ मिला लिया जो हमें मिला और परिवर्तनशीलता का उपयोग करके फिर से लिखना है $$$C ^ 2_S = \ mathbf {E} [S] / \ mathbf {E} [S] ^ 2$ प्रसिद्ध पोलकज़ेक-खिनचिन सूत्र प्राप्त करें :

$$

$$\ mathbf {E} [T_Q] = \ frac {\ rho} {1- \ rho} \ frac {\ mathbf {E} [S]} {2} (C ^ 2_S + 1)$$

यदि सबूत ने आपको ऊब दिया है, तो मुझे उम्मीद है कि यह व्यवहार में इसके आवेदन के परिणाम को प्रसन्न करेगा। हमने पहले ही RTMR में सेवा समय डेटा की जांच की है। लंबी पूंछ सिर्फ महान परिवर्तनशीलता के साथ उत्पन्न होती है, और इस मामले में $$$C ^ 2_S = 381$ । यह, आप देखते हैं, बहुत अधिक है $$$C ^ 2_S = 1$ घातांक वितरण के लिए। औसतन, सब कुछ सुपर फास्ट है: $$$\ mathbf {E} [S] = 263.792 μs$ । अब मान लीजिए कि RTMR को M / G / 1 सिस्टम द्वारा मॉडल किया गया है, और सिस्टम को अधिक लोड नहीं किया जाना चाहिए, निपटान $$$\ rho = 0.5$ । सूत्र में परिणत, हम प्राप्त करते हैं $$$\ mathbf {E} [T_Q] = 1 * (381 + 1) / 2 * 263.792 μs = 50 ms$ । माइक्रोबर्स्ट के कारण, यहां तक ​​कि इस तरह की एक तेज और कमज़ोर प्रणाली औसत रूप से घृणित हो सकती है। 50 एमएस के लिए, आप 6 बार हार्ड ड्राइव पर जा सकते हैं या, यदि आप भाग्यशाली हैं, यहां तक ​​कि किसी अन्य महाद्वीप पर डेटा सेंटर में भी! वैसे, जी / जी / 1 के लिए एक सन्निकटन है जो आने वाले ट्रैफ़िक की परिवर्तनशीलता को ध्यान में रखता है: यह ठीक वैसा ही दिखता है, केवल इसके बजाय $$$C ^ 2_S + 1$ यह दोनों किस्मों का योग है $$$C ^ 2_S + C ^ 2_A$ । कई सर्वरों के मामले में, चीजें बेहतर हैं, लेकिन कई सर्वरों का प्रभाव केवल पहले कारक को प्रभावित करता है। परिवर्तनशीलता का प्रभाव बना रहता है: $$$\ mathbf {E} [T_Q] ^ {G / G / k} b \ mathbf {E} [T_Q] ^ {M / M / k} (C ^ 2_S + C ^ 2_A$ ।

माइक्रोबर्स्ट क्या दिखते हैं? थ्रेड पूलों के संबंध में, ये ऐसे कार्य हैं जो तेजी से संचालित होते हैं, जो कि रीसाइक्लिंग शेड्यूल पर दिखाई नहीं देते हैं, और धीमी गति से अपने पीछे एक कतार बनाते हैं और पूल प्रतिक्रिया समय को प्रभावित करते हैं। सैद्धांतिक दृष्टिकोण से, ये वितरण की पूंछ से विशाल प्रश्न हैं। मान लें कि आपके पास 10 थ्रेड्स का एक पूल है, और आप ऑपरेटिंग समय और डाउनटाइम के मेट्रिक्स पर बनाए गए रीसाइक्लिंग शेड्यूल को देखते हैं, जो हर 15 सेकंड में एकत्र किए जाते हैं। सबसे पहले, आप यह नहीं देख सकते हैं कि एक धागा सभी पर लटका हुआ है, या कि सभी 10 धागे एक साथ एक दूसरे के लिए बड़े कार्य करते हैं, और फिर 14 सेकंड के लिए कुछ भी नहीं किया। 15 सेकंड का एक रिज़ॉल्यूशन 100% तक उपयोग की छलांग और 0% पर वापस जाने की अनुमति नहीं देता है, और प्रतिक्रिया में गिरावट होती है। , , 15 6 , .



, ( ) .

, RTMR SelfPing, ( 10 ), — . , 10 15 . , . , , 10 , , — . self-ping- CPU. , : , , . : , , . : . , 15- , — .

, , SelfPing , ? ? , LWTrace. , . -100 . . : ; — , , ; perf , , .

« », . , , . FIFO-. , , latency ( SPT SRPT). — . , , , . , « », .

, - product-form solution . M/ Cox /1/ PS . , (Coxian distribution) (Processor Sharing), , , . ? , . , , (. ) , , M/ M /1/ FIFO , , .

! , , , ! insensitivity property. , , , , . — M/M/∞. , . , product-form solution — BCMP .

. , (, ), , , ó . . निर्णय। $$$\mathbf{E}[T] = 1/3 \mathbf{E}[T_1] + 2/3 \mathbf{E}[T_2]$ । $$$\mathbf{E}[T_i] = 1/(\mu_i - \lambda_i)$ M/M/1/FCFS $$$\mathbf{E}[T] = 1/3 * 1/(3 - 3 * 1/3) + 2/3 * 1/(4 - 3*2/3) = 0.5$ ।

, , . , .

1. , , , computer science, . Performance Modeling and Design of Computer Systems: Queueing Theory in Action (2013). - , . ó — .
2. , , , , Robert B. Cooper. , .