बफ़र्स (अंगूठी) के सवाल पर

"यदि आपको वास्तुकला की विकास लागत अत्यधिक लगती है, तो विचार करें कि गलत वास्तुकला आपको कितना खर्च कर सकती है"

- मैं वास्तव में स्रोत को याद नहीं रख सकता

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

इतने लंबे समय पहले एक पोस्ट में जिसमें मैंने डांटा था मैंने एक घरेलू आरटीओएस के बारे में अपनी राय व्यक्त की थी, मैंने उल्लेख किया कि सुप्रसिद्ध (और कुछ खास पहलुओं में, बिल्कुल अद्भुत) mcucpp लाइब्रेरी में रिंग बफर के कार्यान्वयन को आदर्श नहीं माना जा सकता है। मैं अपनी बात समझाने और आदर्श (जहां तक ​​संभव हो वास्तविक दुनिया में) क्रियान्वयन की कल्पना करने की कोशिश करूंगा। नोट - आपके ध्यान में पेश किया गया पाठ "अधूरा" में कुछ समय के लिए रखा गया था, और फिर ऐसा सुविधाजनक मामला सामने आया।

हम एक परिधीय उपकरण के साथ काम करने के लिए एक पुस्तकालय विकसित करना जारी रख रहे हैं, और हम स्मृति प्रबंधन और बफरिंग के लिए कतार में हैं (हाँ, हम अभी भी तैयारी संचालन जारी रख रहे हैं, लेकिन उनके बिना किसी भी तरह से)। बफर्स ​​के आयोजन की आवश्यकता कहां से है और यह किस प्रकार का जानवर है? तथ्य यह है कि परिधि का एक महत्वपूर्ण हिस्सा सीमित गति है और ट्रांसमिशन प्रक्रिया, एक तरह से या किसी अन्य में शुरू की जा रही है, ट्रांसमिशन के लिए जानकारी का एक और हिस्सा बनाने की तुलना में एक निश्चित, और कभी-कभी बहुत महत्वपूर्ण समय लगता है। बेशक, यह समय बीतने से पहले, अगला प्रसारण नहीं किया जा सकता है और, तदनुसार, शुरू नहीं किया जा सकता है।

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

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

इसलिए, हम अभी भी प्रोग्राम बफर को कार्यान्वित करेंगे, जिसके लिए ऐसे बफर को व्यवस्थित करने के लिए FIFO विधि (अर्थात, कतार) का उपयोग करना स्वाभाविक होगा और कतार, दो बिंदुओं के साथ रिंग बफर पर सबसे अच्छी तरह से कार्यान्वित की जाती है। जब मैं "सर्वश्रेष्ठ" लिखता हूं, तो इसका मतलब यह नहीं है कि अन्य कार्यान्वयन (उदाहरण के लिए, एक संदर्भ कतार) असंभव है, या घातक के अलावा अन्य घातक दोष हैं। इस अभिव्यक्ति का अर्थ केवल यह है कि कार्यान्वयन बहुत जटिल और काफी प्रभावी नहीं होगा, हालांकि अन्य लोगों को इसके बारे में निर्विवाद फायदे हो सकते हैं, जिसके लिए उन्हें कुछ के लिए भुगतान करना होगा, क्योंकि DarZaNeBy।

चूंकि यह अत्यधिक संभावना नहीं है कि आपके एमके मॉडल में इस तरह के एक सामान्य-उद्देश्य वाले डिवाइस का हार्डवेयर कार्यान्वयन होगा (व्यक्तिगत परिधीय मॉड्यूल के पास अपने स्वयं के रिंग बफ़र हो सकते हैं, लेकिन इस पोस्ट के विषय से उनका कोई लेना-देना नहीं है), हमें रैखिक मेमोरी में रिंग बफर बनाना होगा (कार्यान्वयन पर) वेक्टर, यह, सामान्य रूप से, पता योग्य मेमोरी में एकमात्र प्राकृतिक वस्तु है), और इसके लिए, एक बफर इंडेक्स (या शायद दो इंडेक्स, लेकिन बाद में उस पर और अधिक) की आवश्यकता होगी। मेरी राय में, दो बिंदुओं (सूचकांकों) के साथ एक परिपत्र बफर एक वेक्टर पर एक कतार को लागू करने का एकमात्र स्वीकार्य तरीका है, लेकिन इस मुद्दे पर अलग-अलग दृष्टिकोण हैं और मैंने अपनी आँखों से "X1 = x2" की शैली में एक कार्यान्वयन देखा। x2 = x3; ... x8 = नया प्रतीक ", यदि आप करेंगे, तो मैं इस तरह के विदेशी पर विचार नहीं करूंगा। तथ्य यह है कि दिए गए टुकड़े को किसी विशिष्ट में मौजूद होने का अधिकार हो सकता है, बहुत सीमित स्थिति इसे सामान्य रूप से स्वीकार्य नहीं बनाती है।

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

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

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

चर का यह व्यवहार निम्नलिखित निर्माण का उपयोग करके लागू किया जा सकता है:

volatile int Counter = 0; Counter = (++Counter) % (Max+1); 

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

 int Counter=0; Counter = (Counter + 1) % (Max + 1); 

हमने एक गलती को समाप्त कर दिया है, और कोड (इसके बाद मेरा मतलब होगा कोड "कोड" का अर्थ है कि संकलक द्वारा उत्पन्न निष्पादन योग्य कोड) अधिक लंबा नहीं हो गया है और अब निष्पादित नहीं करता है (वास्तव में, यह तेजी से निष्पादित होता है, लेकिन केवल इसलिए क्योंकि पहले संस्करण में शब्द वाष्पशील का उपयोग इस मामले में पूरी तरह से बेमानी है), और यह कम स्पष्ट नहीं हो गया है (बल्कि, और भी स्पष्ट है, लेकिन यह स्वाद का मामला है)।

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

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

तो क्यों इस तरह के एक पूरी तरह से गलत दृष्टिकोण अभी भी बहुत बार मिलना संभव है। यहां दर्शकों से वे मुझे संकेत देते हैं कि यदि अधिकतम + 1 का मान, जो कि दो की शक्ति है, तो संकलक विभाजन ऑपरेशन के बजाय अनुमान लगाएगा, बिटकॉइन गुणा के संचालन को संबंधित मुखौटा (अधिकतम के बराबर) पर रख दें, जो बहुत तेज़ी से किया जाएगा और सबकुछ ठीक हो जाएगा।

मैं इस कथन से सहमत होता हूं और इस दृष्टिकोण को अपनाता हूं, यदि निम्न परिस्थितियों के लिए नहीं:

• यह केवल संकलित स्तर पर परिभाषित मच के लिए संभव है,
• यह तभी होता है जब अनुकूलन सक्षम हो,
• यह केवल तब होता है जब मच इस शर्त को पूरा करता है,
• यह सभी कार्डिनल प्रकारों के लिए नहीं होता है।

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

इसलिए, यदि हम एक मुखौटा के साथ तार्किक गुणन का उपयोग करना चाहते हैं (शेष की गणना का अनुकूलन करके प्राप्त किया गया है), तो हमें तदनुसार मॉड्यूल को फिर से लिखना चाहिए:

 typedef uint8_t Counter_t; typedef int8_t sCounter_t; static inline Counter_t NextCounter(const Counter_t Counter) { #if IS_POWER2(Max + 1) return (Counter + 1) & Max #else return (Counter + 1) % (Max + 1); #endif }; 

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

लेकिन पहले, पक्ष के लिए एक मामूली विचलन। हम दो की शक्ति के लिए एक चेक कैसे लागू कर सकते हैं (एक बाइनरी नंबर को {0} 1 {0}) के रूप में दर्शाया जा सकता है, जिसका हमने अभी उपयोग किया है


और हम कैसे सत्यापन को लागू कर सकते हैं कि एक संख्या बाइनरी नोटेशन में इकाइयों का एक सही क्रम {0} 1 {1} है - एक विकल्प स्पष्ट है

 #define IsRightSequence(N) IsPower2 ((N) + 1) 

और दूसरा तुच्छ है

 #define IsRightSequence(N) ( (((N) + 1) & (N)) == 0) 

ध्यान दें: मैं शानदार प्रमेय को याद रखने में मदद नहीं कर सकता, लेकिन "ट्रांसेंडेंटल डिग्री में एक ट्रान्सेंडैंटल संख्या हमेशा ट्रांसडेंटल होती है, जब तक कि कॉनसेप्ट स्पष्ट या तुच्छ न हो।"

और हम कैसे सत्यापित कर सकते हैं कि एक संख्या इकाइयों का एक क्रम है {0} 1 {1} {0}

 #define IsSequence(N) IsPower2( (N) ^ ((N) << 1)) 

और अंत में - कम से कम महत्वपूर्ण बिट का चयन कैसे करें (मुझे नहीं पता कि यह क्यों आवश्यक हो सकता है, लेकिन यह काम में आएगा)

 #define LowerBit(N) ((((N) - 1) ^ (N)) & (N)). 

लेकिन जो काम आ सकता है, वह उसने किया

 #define IsRightSequence(N) (IsSequence(N) && (LowerBit(N) == 1)) 

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

प्रोग्रामर्स के लिए एक अद्भुत पुस्तक, ट्रिक्स है, जहां आप उल्लिखित मैक्रोज़ और कई अन्य समान रूप से मज़ेदार और शिक्षाप्रद कार्य पा सकते हैं, मैं इसे पढ़ने की अत्यधिक सलाह देता हूं, खासकर क्योंकि इसमें बहुत सारे अक्षर नहीं हैं।

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

 static inline Counter_t NextCounter(const Counter_t Counter) { if ((Counter + 1) > Max) { return 0; } else { return Counter + 1; }; }; 

(जैसा कि आप पहले से ही समझते हैं, मैं मिस्र के कोष्ठकों का समर्थक हूं और इसके बारे में कुछ भी नहीं किया जाना है)।

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

आइए हम इस समाधान की कम्प्यूटेशनल जटिलता का मूल्यांकन करें - इसके अलावा एकता (1) और तुलना (2) हमेशा, फिर शून्य (1) (शायद ही कभी) या जोड़ना (1) (लगभग हमेशा) - जो 1 + 2 + 1 + Δ ~ 4 प्राथमिक देता है। संचालन और शून्य मेमोरी। यह संभव है कि सही मोड में एक अच्छा संकलक कुछ अनुकूलन करेगा और कोड निष्पादन समय को कम करेगा, लेकिन यह बेहतर है कि हम स्पष्ट रूप से करते हैं। यहाँ निम्नलिखित विकल्प है:

 static inline Counter_t NextCouner(const Counter_t Counter) { register sCounter_t Tmp; Tmp = (Counter + 1); if (Tmp > Max) { Tmp = 0; }; return Tmp; }; 

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

ध्यान दें कि मैंने if ( (Tmp = Counter + 1) > Max) निर्माण का उपयोग नहीं किया है, हालांकि इसमें संकलक को एक स्पष्ट निर्देश है कि वह निरर्थक स्थानान्तरण न करने का प्रयास करें। यह सबसे ज़बरदस्त रूप में स्वादिष्ट है, मुझे असाइनमेंट ऑपरेटर द्वारा लौटाए गए मूल्य पसंद नहीं है और इसका उपयोग करने से बचने की कोशिश करें। मैं इस मजबूत भावना का कारण नहीं बता सकता, फ्रायड के अनुसार, यह बचपन में सबसे अधिक मनोवैज्ञानिक आघात है। आधुनिक कंपाइलर अपने दम पर सरल अनुकूलन करने में काफी सक्षम हैं, और इसके अलावा, मैंने एक रजिस्टर क्वालिफायर भी जोड़ा है, इसलिए मेरे संस्करण के लिए कोड और सही एक (सी भाषा के दृष्टिकोण से) मेल खाएगा। फिर भी, मैं आपकी स्वतंत्रता को उस विधि का उपयोग करने के लिए सीमित नहीं करता हूं जो आपके लिए बेहतर लगती है।

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

 static inline Counter_t NextCouner(const Counter_t Counter) { register Counter_t Tmp; Tmp = (Counter - 1); if (Tmp < 0) { Tmp = ; }; return Tmp; }; 

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

एक और भी तेज समाधान है - बस काउंटर वैल्यू बढ़ाएँ (घटाएँ) और कुछ न करें, लेकिन यह केवल उस स्थिति में ही संभव है जब अधिकतम मूल्य उस मान के साथ मेल खाता है जो स्वीकृत प्रकार में सबसे अधिक प्रतिनिधि है। 8-बिट काउंटर के लिए (जो कि प्रकार uint8_t का है), यह 255 होगा, फिर हम सिर्फ काउंटर = काउंटर + 1 लिखते हैं और इसके लिए मेरा शब्द लेते हैं कि काउंटर + = 1 या ++ काउंटर लिखना पूरी तरह से वैकल्पिक है, हालांकि कई हैं और वे लिखेंगे और बिल्कुल सही होंगे। यदि हम पात्रों को बचाने की आवश्यकता के बारे में संस्करण पर गंभीरता से विचार नहीं करते हैं (चूंकि पहला विकल्प सबसे लंबा है), तो इसका कोई मतलब नहीं है, कम से कम अगर हम एआरएम या एवीआर आर्किटेक्चर के लिए एक कार्यक्रम लिख रहे हैं (दूसरों के लिए जो मैंने अभी जांच नहीं की थी, मुझे संदेह है कि परिणाम होगा जीसीसी संकलक के तहत एक ही) (लेखक समझता है कि वे एकीकृत प्रोग्रामिंग वातावरण के संपादक में कार्यक्रम लिख रहे हैं, यह अतीत से केवल एक भाषण क्रांति है जब कंप्यूटर बड़े और मेमोरी छोटे थे), और अनुकूलन के साथ किसी भी स्तर पर चालू हो गया, क्योंकि दिए गए कोड बिल्कुल समान होंगे।

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

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

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

खैर, संक्षेप में, संक्षेप में - हम रिंग इंडेक्स के साथ काम के विभिन्न कार्यान्वयनों को एक साथ लाएंगे और उनके गुणों का मूल्यांकन करेंगे।

कोष्ठक में दूसरी पंक्ति बफर आकार मान (256 से अधिक नहीं) की संख्या को दर्शाती है, जिसके लिए यह कार्यान्वयन उपलब्ध है, लेकिन हमारा मतलब है कि आकार 0 का एक बफर हमारे लिए रुचि नहीं रखता है।

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

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

इसलिए, हमने इंडेक्स के साथ काम करने के लिए सही मॉड्यूल (इनलाइन फ़ंक्शन का एक मजबूत नाम) बनाया, और अब हम रिंग बफर को लागू करना शुरू करने के लिए तैयार हैं।

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

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

सबसे पहले, सूचकांकों के बारे में - हम तुरंत ध्यान देते हैं कि ये सूचक हैं, न कि संकेत, हालांकि कभी-कभी मैंने खुद को ऐसा करने की अनुमति दी। ( ), ( )- , , , . ( 256 ), , , ( , 8 , , 4- ), , , ( , ).


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

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

(«, ») , . — 1) , 2) ( , ) 3) , , 4) 256 , 5) ( ), . , , , , .

, (, , ), 1 . :

 #define NeedOverflowControl YES typedef uint8_t Data_t; static Data_t BufferData[Max]; static Counter_t BufferWriteCounter=0, BufferReadCounter=BufferWriteCounter; void BufferWrite(const data_t Data) { BufferData[BuffWriteCounter] = Data; register counter_t Tmp = NextCount(BufferWriteCounter); #if (NeedOverflowControl == YES) if (Tmp == BufferReadCounter) {BufferOverflow();} else #endif { BufferWriteCounter = Tmp; } }; 

, , … , :

  inline int BufferIsEmpty(void) { return ( BufferReadCounter == BufferWriteCounter ); }; inline int BufferIsFull(void) { return ( BufferReadCounter == NextCounter(BufferWriteCounter) ); }; #define DataSizeIsSmaller (sizeof(data_t) < sizeof(counter_t)) data_t BufferRead(void) { #if DataSizeIsSmaller register data_t Tmp = BufferData[BufferReadCounter]; #else register counter_t Tmp = BufferReadCounter; #endif BufferReadCounter = NextCount(BufferReadCounter); #if DataSizeIsSmaller return Tmp; #else return BufferData[Tmp]; #endif }; 

, ( ) — , , , — , . , , , .

, , — , , , .

, ( )

1) ( — , , — , , ).
(, , )

2) — , .

:

3) और 4) समस्या को नजरअंदाज करें और दिखावा करें कि सब कुछ ठीक है ("मुस्कान और लहर")। वे खराब क्यों हैं - क्योंकि हम केवल यह दिखावा करते हैं कि सब कुछ ठीक है, वास्तव में, डिरिचलेट सिद्धांत (एन कोशिकाओं और एन + 1 पक्षियों की समस्या) का उल्लंघन नहीं किया जा सकता है और हम डेटा तत्व खो देते हैं, और दो तरीके क्यों हैं? हम

3) पिछले रिकॉर्ड किए गए डेटा तत्व को

खो सकते हैं, और हम 4) उन तत्वों को खो सकते हैं जो अभी तक स्थानांतरित नहीं हुए हैं।

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

— , ( , ),

5) — , , , , — , .

— , , .

, , , , , , , , , , , . , 4 , , . MRSW (Multi-Reader Single-Writer) «The Art of Mulpiprocessor Programming» ( , ) ( ) . — , , .

MRMW , «» (, , « » ). , , , , . , , , (, , — , , , ), .

, ( ) , . , , , , , , , .

 typedef uint8_t data_t; static data_t BufferData[Max]; static counter_t BufferWriteCounter=0, BufferReadCounter=WriteCounter; static int8_t BufferHaveData = 0; void BufferWrite(const data_t Data) { if ((BufferWriteCounter == BufferReadCounter) && (BufferHaveDataFlag == 1)) {BufferOverflow();} else { BufferData[BufferWriteCounter] = Data; BufferHaveDataFlag = 1; BufferWriteCounter = NextCounter(BufferWriteCounter); }; }; inline int BufferIsEmpty(void) { return ((BufferReadCounter==BufferWriteCounter) && (BufferHaveDataFlag == 0));}; data_t BufferRead(void) { register counter_t Tmp; Tmp = BufferReadCounter; BufferReadCounter = NextCount(BufferReadCounter); if (BufferReadCount == BufferWriteCounter) { BufferHaveDataFlag = 1; }; return BufferData[Tmp]; }; 

, , , , , .

, ( 0 1, , , ), , , , , , ( ), , ,


, , 0 1, . , , , 0 1. , , , , BufferFullFlag , BufferIsNotEmptyFlag . , KISS , , , , , « ».

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

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

PS और निष्कर्ष में, मुझे उल्लिखित लाइब्रेरी में क्या पसंद है, लेकिन उसी समय, घरेलू RTOS के लेखकों ने इसे बिना किसी संदेह के अपने कोड में ले लिया:

1. बफर के दो कार्यान्वयन दिए गए हैं - एक दो की शक्ति के आकार के लिए (मुझे आशा है कि मैंने दिखाया कि यह पूरी तरह से अनावश्यक है), और शेष मामलों के लिए दूसरा है, लेकिन आपको पेन के साथ संस्करण चुनना होगा, निश्चित रूप से, वे गलतियां नहीं करेंगे, हर जगह चेक हैं।
2. पूरी तरह से अनावश्यक तरीके बनाए गए हैं, जैसे कि अंतिम तत्व को हटाना या बफर तत्व से सीधे पहुंच।
3. डेटा बफर को एक पूर्णांक के साथ संरेखित किया जाता है।
4. डिग्री 2 के कार्यान्वयन में, अधिभोग दर की जांच करने में त्रुटि।
5. एक मनमाना आकार के कार्यान्वयन में, एक काउंटर
6. महत्वपूर्ण खंडों का आयोजन बिल्कुल नहीं किया जाता है, जो सही कार्यान्वयन में (दो सूचकांकों के साथ) बस जरूरत नहीं है, लेकिन कोई भी उनके बिना नहीं कर सकता है, इसके बजाय परमाणु संचालन का उपयोग स्पष्ट रूप से पर्याप्त नहीं है।
7. कुछ शैली लापरवाही, लाइनों की तरह
   
   

    return ((_writeCount - Atomic::Fetch(&_readCount)) & (size_type)~(_mask)) != 0; 

   
   विशेष रूप से इसकी दूसरी छमाही - यह वही है जो सी के लिए दोषी ठहराया गया है, और भाषा स्वयं को दोष नहीं है, यह केवल आपको अधिक समझने के बजाय इसे लिखने की अनुमति देता है
   
   

    size_type(~(_mask)) 

   
   लेकिन यह करने के लिए मजबूर नहीं।

पीपीएस मुझे उम्मीद है कि पुस्तकालय के लेखक इस आलोचना पर विचार करने के लिए सहमत हैं और उचित सुधार करेंगे।