गोलाकार बफर: Difference between revisions

From Vigyanwiki
(Text)
No edit summary
 
(4 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{Short description|A circular shaped buffer shown while obtaining data}}
{{Short description|A circular shaped buffer shown while obtaining data}}
[[Image:Circular buffer.svg|thumb|200px|संकल्पनात्मक रूप से एक गोलाकार बफ़र दिखा रहा एक छल्ला। यह दृष्टि से दिखाता है कि बफर का कोई वास्तविक अंत नहीं है और यह बफर के चारों ओर लूप कर सकता है। हालाँकि, चूंकि मेमोरी को कभी भी रिंग के रूप में भौतिक रूप से नहीं बनाया जाता है, आमतौर पर एक रैखिक प्रतिनिधित्व का उपयोग किया जाता है जैसा कि नीचे किया गया है।]][[कंप्यूटर विज्ञान]] में, एक गोलाकार बफर, गोलाकार कतार, चक्रीय बफर या रिंग बफर एक [[डेटा संरचना]] है जो एक एकल, निश्चित आकार के [[बफर (कंप्यूटर विज्ञान)|बफर]] का उपयोग करता है जैसे कि यह एंड-टू-एंड से जुड़ा हो। यह संरचना [[आकड़ों का प्रवाह|आकड़ों के प्रवाह]] को बफ़र करने के लिए स्वयं को आसानी से '''उधार''' देती है।<ref>{{citation|title=Operating Systems: Three Easy Pieces [Chapter: Condition Variables, figure 30.13]|url=http://pages.cs.wisc.edu/~remzi/OSTEP/threads-cv.pdf|
[[Image:Circular buffer.svg|thumb|200px|संकल्पनात्मक रूप से एक गोलाकार बफ़र, एक छल्ला दिखा रहा। यह दृष्टि से दिखाता है कि बफर का कोई वास्तविक अंत नहीं है और यह बफर के चारों ओर लूप कर सकता है। हालाँकि, चूंकि मेमोरी को कभी भी रिंग के रूप में भौतिक रूप से नहीं बनाया जाता है, प्रायः एक रैखिक प्रतिनिधित्व का उपयोग किया जाता है जैसा कि नीचे किया गया है।]][[कंप्यूटर विज्ञान]] में, एक गोलाकार बफर, गोलाकार कतार, चक्रीय बफर या रिंग बफर एक [[डेटा संरचना]] है जो एक एकल, निश्चित आकार के [[बफर (कंप्यूटर विज्ञान)|बफर]] का उपयोग करता है जैसे कि यह एंड-टू-एंड से जुड़ा हो। यह संरचना [[आकड़ों का प्रवाह|आकड़ों के प्रवाह]] को बफ़र करने के लिए स्वयं को आसानी से किराये पर देती है।<ref>{{citation|title=Operating Systems: Three Easy Pieces [Chapter: Condition Variables, figure 30.13]|url=http://pages.cs.wisc.edu/~remzi/OSTEP/threads-cv.pdf|
publisher=Arpaci-Dusseau Books|date=2014|first1=Remzi H.|last1=Arpaci-Dusseau|first2=Andrea C.|last2=Arpaci-Dusseau}}</ref> हार्डवेयर में शुरुआती सर्कुलर बफर कार्यान्वयन थे।<ref>{{cite web|last1=Hartl|first1=Johann|title=Impulswiederholer - टेलीफोन एक्सचेंज (वीडियो)|url=https://www.youtube.com/watch?v=_xI9tXi-UNs|publisher=Youtube|access-date=15 December 2021}}</ref><ref>{{cite web|last1=Fraser|first1=Alexander Gibson|title=US patent 3979733 Digital data communications system packet switch|url=https://patents.google.com/patent/US3979733A/en|publisher=US States Patent|access-date=15 December 2021}}</ref>
publisher=Arpaci-Dusseau Books|date=2014|first1=Remzi H.|last1=Arpaci-Dusseau|first2=Andrea C.|last2=Arpaci-Dusseau}}</ref> हार्डवेयर में शुरुआती गोलाकार बफर कार्यान्वयन थे।<ref>{{cite web|last1=Hartl|first1=Johann|title=Impulswiederholer - टेलीफोन एक्सचेंज (वीडियो)|url=https://www.youtube.com/watch?v=_xI9tXi-UNs|publisher=Youtube|access-date=15 December 2021}}</ref><ref>{{cite web|last1=Fraser|first1=Alexander Gibson|title=US patent 3979733 Digital data communications system packet switch|url=https://patents.google.com/patent/US3979733A/en|publisher=US States Patent|access-date=15 December 2021}}</ref>




== सिंहावलोकन ==
== समीक्षा ==
[[File:Circular Buffer Animation.gif|400px|thumbnail|एक 24-बाइट कीबोर्ड सर्कुलर बफर। जब राइट पॉइंटर रीड पॉइंटर तक पहुँचने वाला होता है - क्योंकि माइक्रोप्रोसेसर प्रतिक्रिया नहीं दे रहा है - बफर कीस्ट्रोक रिकॉर्ड करना बंद कर देता है। कुछ कंप्यूटरों पर एक बीप बजाया जाएगा।]]एक गोलाकार बफर पहले खाली शुरू होता है और इसकी एक निर्धारित लंबाई होती है। नीचे दिए गए आरेख में एक 7-तत्व बफ़र है:
[[File:Circular Buffer Animation.gif|400px|thumbnail|एक 24-बाइट कीबोर्ड गोलाकार बफर। जब राइट पॉइंटर रीड पॉइंटर तक पहुँचने वाला होता है - क्योंकि माइक्रोप्रोसेसर प्रतिक्रिया नहीं दे रहा है - बफर कीस्ट्रोक रिकॉर्ड करना बंद कर देता है। कुछ कंप्यूटरों पर एक बीप बजाया जाएगा।]]एक गोलाकार बफर पहले खाली प्रारम्भहोता है और इसकी एक निर्धारित लंबाई होती है। नीचे दिए गए आरेख में एक 7-तत्व बफ़र है:


:[[Image:Circular buffer - empty.svg|250px]]मान लें कि 1 एक गोलाकार बफर के केंद्र में लिखा गया है (गोलाकार बफर में सटीक प्रारंभिक स्थान महत्वपूर्ण नहीं है):
:[[Image:Circular buffer - empty.svg|250px]]मान लें कि 1 एक गोलाकार बफर के केंद्र में लिखा गया है (गोलाकार बफर में सटीक प्रारंभिक स्थान महत्वपूर्ण नहीं है):


:[[Image:Circular buffer - XX1XXXX.svg|250px]]फिर मान लें कि सर्कुलर बफर में दो और तत्व जोड़े गए हैं - 2 और 3 - जो 1 के बाद रखे जाते हैं:
:[[Image:Circular buffer - XX1XXXX.svg|250px]]फिर मान लें कि गोलाकार बफर में दो और तत्व जोड़े गए हैं - 2 और 3 - जो 1 के बाद रखे जाते हैं:


:[[Image:Circular buffer - XX123XX.svg|250px]]यदि दो तत्वों को हटा दिया जाता है, तो वृत्ताकार बफ़र के अंदर के दो सबसे पुराने मान हटा दिए जाएंगे। सर्कुलर बफ़र्स FIFO (पहले अंदर, पहले बाहर) तर्क का उपयोग करते हैं। उदाहरण में, 1 और 2 सर्कुलर बफर में प्रवेश करने वाले पहले थे, वे पहले हटाए जाने वाले हैं, बफर के अंदर 3 को छोड़कर।
:[[Image:Circular buffer - XX123XX.svg|250px]]यदि दो तत्वों को हटा दिया जाता है, तो वृत्ताकार बफ़र के अंदर के दो सबसे पुराने मान हटा दिए जाएंगे। गोलाकार बफ़र्स FIFO (पहला अंदर, पहला बाहर) तर्क का उपयोग करते हैं। उदाहरण में, 1 और 2 गोलाकार बफर में प्रवेश करने वाले पहले थे, बफर के अंदर 3 को छोड़कर, वे पहले हटाए जाने वाले हैं।


:[[Image:Circular buffer - XXXX3XX.svg|250px]]यदि बफ़र में 7 तत्व हैं, तो यह पूरी तरह से भरा हुआ है:
:[[Image:Circular buffer - XXXX3XX.svg|250px]]यदि बफ़र में 7 तत्व हैं, तो यह पूरी तरह से भरा हुआ है:


:[[Image:Circular buffer - 6789345.svg|250px]]सर्कुलर बफर की एक विशेषता यह है कि जब यह भर जाता है और बाद में राइट किया जाता है, तो यह सबसे पुराने डेटा को ओवरराइट करना शुरू कर देता है। वर्तमान उदाहरण में, दो और तत्व - ए और बी - जोड़े गए हैं और वे 3 और 4 को ओवरराइट करते हैं:
:[[Image:Circular buffer - 6789345.svg|250px]]गोलाकार बफर की एक विशेषता यह है कि जब यह भर जाता है और बाद में राइट किया जाता है, तो यह सबसे पुराने डेटा को अधिलेखित करना प्रारम्भ कर देता है। वर्तमान उदाहरण में, दो और तत्व - ए और बी - जोड़े गए हैं और वे 3 और 4 को अधिलेखित करते हैं:


:[[Image:Circular buffer - 6789AB5.svg|250px]]वैकल्पिक रूप से, बफ़र को प्रबंधित करने वाले रूटीन डेटा को अधिलेखित होने से रोक सकते हैं और त्रुटि वापस कर सकते हैं या अपवाद हैंडलिंग बढ़ा सकते हैं। डेटा ओवरराइट किया गया है या नहीं, यह बफ़र रूटीन या सर्कुलर बफ़र का उपयोग करने वाले एप्लिकेशन के शब्दार्थ पर निर्भर करता है।
:[[Image:Circular buffer - 6789AB5.svg|250px]]वैकल्पिक रूप से, बफ़र को प्रबंधित करने वाले रूटीन डेटा को अधिलेखित होने से रोक सकते हैं और त्रुटि वापस कर सकते हैं या अपवाद बढ़ा सकते हैं। डेटा अधिलेखित किया गया है या नहीं, यह बफ़र रूटीन या गोलाकार बफ़र का उपयोग करने वाले एप्लिकेशन के शब्दार्थ पर निर्भर करता है।


अंत में, यदि दो तत्वों को अब हटा दिया जाता है तो जो लौटाया जाएगा वह 3 और 4 नहीं बल्कि ए और बी है क्योंकि ए और बी ने 3 और 4 को अधिलेखित कर दिया है जिससे बफर उत्पन्न होता है:
अंत में, यदि दो तत्वों को अब हटा दिया जाता है तो जो लौटाया जाएगा वह 3 और 4 नहीं बल्कि ए और बी है क्योंकि ए और बी ने 3 और 4 को अधिलेखित कर दिया है जिससे बफर उत्पन्न होता है:
Line 24: Line 24:


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


सर्कुलर बफ़रिंग एक [[कतार (डेटा संरचना)]] के लिए एक अच्छी कार्यान्वयन रणनीति बनाता है जिसने अधिकतम आकार तय किया है। यदि कतार के लिए अधिकतम आकार अपनाया जाना चाहिए, तो एक गोलाकार बफर पूरी तरह से आदर्श कार्यान्वयन है; सभी कतार संचालन निरंतर समय हैं। हालाँकि, एक सर्कुलर बफ़र का विस्तार करने के लिए शिफ्टिंग मेमोरी की आवश्यकता होती है, जो तुलनात्मक रूप से महंगा है। मनमाने ढंग से कतारों का विस्तार करने के लिए, इसके बजाय एक [[लिंक्ड सूची]] दृष्टिकोण को प्राथमिकता दी जा सकती है।
गोलाकार बफ़रिंग एक [[कतार (डेटा संरचना)|कतार]] के लिए एक अच्छी कार्यान्वयन रणनीति बनाता है जिसने अधिकतम आकार तय किया है। यदि कतार के लिए अधिकतम आकार अपनाया जाना चाहिए, तो एक गोलाकार बफर पूरी तरह से आदर्श कार्यान्वयन है; सभी कतार संचालन निरंतर समय हैं। हालाँकि, एक गोलाकार बफ़र का विस्तार करने के लिए शिफ्टिंग मेमोरी की आवश्यकता होती है, जो तुलनात्मक रूप से मूल्यवान है। स्वेच्छतः ढंग से कतारों का विस्तार करने के लिए, इसके बदले एक [[लिंक्ड सूची]] दृष्टिकोण को प्राथमिकता दी जा सकती है।


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


== गोलाकार बफर यांत्रिकी ==
== गोलाकार बफर यांत्रिकी ==
:[[Image:Hardware_circular_buffer_implementation_patent_us3979733_fig4.png|250px|thumb|हार्डवेयर में सर्कुलर बफर इम्प्लीमेंटेशन, US पेटेंट 3979733, Fig4]]एक [[सूचक (कंप्यूटर प्रोग्रामिंग)]] और तीन पूर्णांकों का उपयोग करके एक गोलाकार बफर लागू किया जा सकता है:
:[[Image:Hardware_circular_buffer_implementation_patent_us3979733_fig4.png|250px|thumb|हार्डवेयर में गोलाकार बफर इम्प्लीमेंटेशन, यूएस पेटेंट 3979733, Fig4]]एक [[सूचक (कंप्यूटर प्रोग्रामिंग)]] और तीन पूर्णांकों का उपयोग करके एक गोलाकार बफर लागू किया जा सकता है:
* मेमोरी में बफर स्टार्ट
* मेमोरी में बफर स्टार्ट
* बफर क्षमता (लंबाई)
* बफर क्षमता (लंबाई)
Line 39: Line 39:
यह छवि लंबाई = 7 के साथ आंशिक रूप से पूर्ण बफ़र दिखाती है:
यह छवि लंबाई = 7 के साथ आंशिक रूप से पूर्ण बफ़र दिखाती है:


:[[Image:Circular buffer - XX123XX with pointers.svg|250px]]यह छवि चार तत्वों (संख्या 1 से 4) के साथ एक पूर्ण बफर दिखाती है जिसे ओवरराइट किया गया है:
:[[Image:Circular buffer - XX123XX with pointers.svg|250px]]यह छवि चार तत्वों (संख्या 1 से 4) के साथ एक पूर्ण बफर दिखाती है जिसे अधिलेखित किया गया है:


:[[Image:Circular buffer - 6789AB5 with pointers.svg|250px]]शुरुआत में इंडेक्स एंड और स्टार्ट 0 पर सेट होते हैं। सर्कुलर बफर राइट ऑपरेशन एक एलिमेंट को एंड इंडेक्स पोजीशन में लिखता है और एंड इंडेक्स को अगले बफर पोजीशन में बढ़ा दिया जाता है। सर्कुलर बफर रीड ऑपरेशन स्टार्ट इंडेक्स पोजीशन से एक एलिमेंट को पढ़ता है और स्टार्ट इंडेक्स को अगले बफर पोजीशन में बढ़ा दिया जाता है।
:[[Image:Circular buffer - 6789AB5 with pointers.svg|250px]]प्रारम्भ में इंडेक्स एंड और स्टार्ट 0 पर सेट होते हैं। गोलाकार बफर राइट ऑपरेशन एक एलिमेंट को एंड इंडेक्स पोजीशन में लिखता है और एंड इंडेक्स को अगले बफर पोजीशन में बढ़ा दिया जाता है। गोलाकार बफर रीड ऑपरेशन स्टार्ट इंडेक्स पोजीशन से एक एलिमेंट को पढ़ता है और स्टार्ट इंडेक्स को अगले बफर पोजीशन में बढ़ा दिया जाता है।


सभी बफर स्लॉट्स का उपयोग करते हुए बफर को पूर्ण या खाली स्थिति बताने के लिए स्टार्ट और एंड इंडेक्स पर्याप्त नहीं हैं,<ref>{{cite web|last1=Chandrasekaran|first1=Siddharth|title=Implementing Circular/Ring Buffer in Embedded C|url=https://embedjournal.com/implementing-circular-buffer-embedded-c/|website=Embed Journal|publisher=EmbedJournal Team|access-date=14 August 2017|archive-url=https://web.archive.org/web/20170211031659/http://embedjournal.com/implementing-circular-buffer-embedded-c/|archive-date=11 February 2017|url-status=live|date=2014-05-16}}</ref> लेकिन अगर बफर में केवल लंबाई का अधिकतम उपयोग किया जा सकता है - 1।<ref>[https://www.kernel.org/doc/Documentation/circular-buffers.txt#:~:text=A%20circular%20buffer%20is%20a,next%20item%20in%20the%20buffer Circular buffers] kernel.org</ref> इस मामले में, बफर खाली है यदि उपयोग में आकार लंबाई -1 होने पर प्रारंभ और अंत अनुक्रमणिका बराबर और पूर्ण होती है।
सभी बफर स्लॉट्स का उपयोग करते हुए बफर को पूर्ण या खाली स्थिति बताने के लिए प्रारंभिक और अंतिम इंडेक्स पर्याप्त नहीं हैं,<ref>{{cite web|last1=Chandrasekaran|first1=Siddharth|title=Implementing Circular/Ring Buffer in Embedded C|url=https://embedjournal.com/implementing-circular-buffer-embedded-c/|website=Embed Journal|publisher=EmbedJournal Team|access-date=14 August 2017|archive-url=https://web.archive.org/web/20170211031659/http://embedjournal.com/implementing-circular-buffer-embedded-c/|archive-date=11 February 2017|url-status=live|date=2014-05-16}}</ref> लेकिन अगर बफर में केवल लंबाई- 1 का अधिकतम उपयोग किया जा सकता है ।<ref>[https://www.kernel.org/doc/Documentation/circular-buffers.txt#:~:text=A%20circular%20buffer%20is%20a,next%20item%20in%20the%20buffer Circular buffers] kernel.org</ref> इस स्थिति में, बफर खाली है यदि उपयोग में आकार लंबाई -1 होने पर प्रारंभ और अंत इंडेक्स बराबर और पूर्ण होती है। एक अन्य उपाय यह है कि एक और पूर्णांक संख्या हो जो एक राइट ऑपरेशन में बढ़ाई जाती है और एक रीड ऑपरेशन में घट जाती है। फिर शून्यता की जाँच का अर्थ है परीक्षण गणना 0 के बराबर है और पूर्णता की जाँच का अर्थ है परीक्षण गणना लंबाई के बराबर है।<ref>{{cite web |title=ArrayQueue: An Array-Based Queue |url=http://opendatastructures.org/ods-python/2_3_ArrayQueue_Array_Based_.html |website=Open Data Structures (in pseudocode) |first=Pat |last=Morin|author-link= Pat Morin |access-date=7 November 2015 |archive-url=https://web.archive.org/web/20150831023453/http://opendatastructures.org/ods-python/2_3_ArrayQueue_Array_Based_.html |archive-date=31 August 2015 |url-status=live }}</ref>
एक अन्य उपाय यह है कि एक और पूर्णांक संख्या हो जो एक लेखन ऑपरेशन में बढ़ाई जाती है और एक रीड ऑपरेशन में घट जाती है। फिर शून्यता की जाँच का अर्थ है परीक्षण गणना 0 के बराबर है और पूर्णता की जाँच का अर्थ है परीक्षण गणना लंबाई के बराबर है।<ref>{{cite web |title=ArrayQueue: An Array-Based Queue |url=http://opendatastructures.org/ods-python/2_3_ArrayQueue_Array_Based_.html |website=Open Data Structures (in pseudocode) |first=Pat |last=Morin|author-link= Pat Morin |access-date=7 November 2015 |archive-url=https://web.archive.org/web/20150831023453/http://opendatastructures.org/ods-python/2_3_ArrayQueue_Array_Based_.html |archive-date=31 August 2015 |url-status=live }}</ref>
 
निम्नलिखित स्रोत कोड एक सी कार्यान्वयन है। फंक्शन पुट () एक आइटम को बफर में रखता है, फंक्शन गेट () बफर से एक आइटम प्राप्त करता है:
निम्नलिखित स्रोत कोड एक सी कार्यान्वयन है। फंक्शन put() एक आइटम को बफर में रखता है, फंक्शन get() बफर से एक आइटम प्राप्त करता है:


<syntaxhighlight lang="c">
<syntaxhighlight lang="c">
Line 70: Line 70:


== अनुकूलन ==
== अनुकूलन ==
[[ आभासी मेमोरी ]] के दो सन्निहित क्षेत्रों के लिए अंतर्निहित बफर [[Mmap]] द्वारा एक सर्कुलर-बफर कार्यान्वयन को अनुकूलित किया जा सकता है।<ref>{{cite web |title=mikeash.com: Friday Q&A 2012-02-17: Ring Buffers and Mirrored Memory: Part II |author=Mike Ash |work=mikeash.com |date=2012-02-17 |access-date=2019-01-10 |url=https://www.mikeash.com/pyblog/friday-qa-2012-02-17-ring-buffers-and-mirrored-memory-part-ii.html |archive-url=https://web.archive.org/web/20190111054903/https://www.mikeash.com/pyblog/friday-qa-2012-02-17-ring-buffers-and-mirrored-memory-part-ii.html |archive-date=2019-01-11 |url-status=live }}</ref>{{Disputed inline|talk=Talk:Circular_buffer#Optimization|date=January 2022}} (स्वाभाविक रूप से, अंतर्निहित बफ़र की लंबाई तब सिस्टम के [[पृष्ठ (कंप्यूटिंग)]] के कुछ गुणकों के बराबर होनी चाहिए।) सर्कुलर बफ़र से पढ़ना और लिखना तब प्रत्यक्ष मेमोरी एक्सेस के माध्यम से अधिक दक्षता के साथ किया जा सकता है; वे एक्सेस जो पहले वर्चुअल-मेमोरी क्षेत्र के अंत से परे हैं, स्वचालित रूप से अंतर्निहित बफर की शुरुआत में लपेटे जाएंगे। जब रीड ऑफ़सेट को दूसरे वर्चुअल-मेमोरी क्षेत्र में उन्नत किया जाता है, तो ऑफ़सेट-पढ़ना और लिखना-दोनों अंतर्निहित बफर की लंबाई से कम हो जाते हैं।
[[ आभासी मेमोरी | वर्चुअल मेमोरी]] के दो सन्निहित क्षेत्रों के लिए अंतर्निहित बफर [[Mmap|मैप]] द्वारा एक गोलाकार-बफर कार्यान्वयन को अनुकूलित किया जा सकता है।<ref>{{cite web |title=mikeash.com: Friday Q&A 2012-02-17: Ring Buffers and Mirrored Memory: Part II |author=Mike Ash |work=mikeash.com |date=2012-02-17 |access-date=2019-01-10 |url=https://www.mikeash.com/pyblog/friday-qa-2012-02-17-ring-buffers-and-mirrored-memory-part-ii.html |archive-url=https://web.archive.org/web/20190111054903/https://www.mikeash.com/pyblog/friday-qa-2012-02-17-ring-buffers-and-mirrored-memory-part-ii.html |archive-date=2019-01-11 |url-status=live }}</ref>{{Disputed inline|talk=Talk:Circular_buffer#Optimization|date=January 2022}} (स्वाभाविक रूप से, अंतर्निहित बफ़र की लंबाई तब सिस्टम के [[पृष्ठ (कंप्यूटिंग)|पृष्ठ]] के कुछ गुणकों के बराबर होनी चाहिए।) गोलाकार बफ़र से पढ़ना और लिखना तब प्रत्यक्ष मेमोरी एक्सेस के माध्यम से अधिक दक्षता के साथ किया जा सकता है; वे एक्सेस जो पहले वर्चुअल-मेमोरी क्षेत्र के अंत से परे हैं, स्वचालित रूप से अंतर्निहित बफर की प्रारम्भ में लपेटे जाएंगे। जब रीड ऑफ़सेट को दूसरे वर्चुअल-मेमोरी क्षेत्र में उन्नत किया जाता है, तो ऑफ़सेट-पढ़ना और लिखना-दोनों अंतर्निहित बफर की लंबाई से कम हो जाते हैं।


== निश्चित-लंबाई-तत्व और सन्निहित-ब्लॉक गोलाकार बफर ==
== निश्चित-लंबाई-तत्व और सन्निहित-ब्लॉक गोलाकार बफर ==
सर्कुलर बफर का शायद सबसे आम संस्करण तत्वों के रूप में 8-बिट बाइट्स का उपयोग करता है।
गोलाकार बफर का संभवतः सबसे सामान्य संस्करण तत्वों के रूप में 8-बिट बाइट्स का उपयोग करता है।


सर्कुलर बफ़र के कुछ कार्यान्वयन निश्चित-लंबाई वाले तत्वों का उपयोग करते हैं जो 8-बिट बाइट्स से बड़े होते हैं - ऑडियो बफ़र्स के लिए 16-बिट पूर्णांक, टेलीकॉम बफ़र्स के लिए 53-बाइट [[ अतुल्यकालिक अंतरण विधा ]] सेल, आदि। प्रत्येक आइटम सन्निहित है और सही डेटा है संरेखण, इसलिए सॉफ़्टवेयर इन मानों को पढ़ना और लिखना उन सॉफ़्टवेयर की तुलना में तेज़ हो सकता है जो गैर-सन्निहित और गैर-संरेखित मानों को संभालते हैं।
गोलाकार बफ़र के कुछ कार्यान्वयन निश्चित-लंबाई वाले तत्वों का उपयोग करते हैं जो 8-बिट बाइट्स से बड़े होते हैं - ऑडियो बफ़र्स के लिए 16-बिट पूर्णांक, टेलीकॉम बफ़र्स के लिए 53-बाइट[[ अतुल्यकालिक अंतरण विधा | एटीएम]] सेल, आदि। प्रत्येक आइटम सन्निहित है और सही डेटा संरेखण है, इसलिए इन मानों को पढ़ना और लिखना उन सॉफ़्टवेयर की तुलना में तेज़ हो सकता है जो गैर-सन्निहित और गैर-संरेखित मानों को संभालते हैं।


[[पिंग-पोंग बफर]] को दो बड़े निश्चित-लंबाई वाले तत्वों के साथ एक बहुत ही विशिष्ट गोलाकार बफ़र माना जा सकता है।
[[पिंग-पोंग बफर]] को दो बड़े निश्चित-लंबाई वाले तत्वों के साथ एक बहुत ही विशिष्ट गोलाकार बफ़र माना जा सकता है।


बिप बफ़र (द्विपक्षीय बफ़र) एक गोलाकार बफ़र के समान है, सिवाय इसके कि यह हमेशा सन्निहित ब्लॉक लौटाता है जो चर लंबाई हो सकता है। यह एपीआई में उपयोग किए जाने वाले बफर की क्षमता को बनाए रखते हुए एक गोलाकार बफर के लगभग सभी दक्षता लाभ प्रदान करता है जो केवल सन्निहित ब्लॉकों को स्वीकार करता है।<ref name="cooke">Simon Cooke (2003), [http://www.codeproject.com/Articles/3479/The-Bip-Buffer-The-Circular-Buffer-with-a-Twist "The Bip Buffer - The Circular Buffer with a Twist"]</ref>
बिप बफ़र (द्विपक्षीय बफ़र) एक गोलाकार बफ़र के समान है, इसे छोड़कर यह हमेशा सन्निहित ब्लॉक लौटाता है जो चर लंबाई हो सकता है। यह एपीआई में उपयोग किए जाने वाले बफर की क्षमता को बनाए रखते हुए एक गोलाकार बफर के लगभग सभी दक्षता लाभ प्रदान करता है जो केवल सन्निहित ब्लॉकों को स्वीकार करता है।<ref name="cooke">Simon Cooke (2003), [http://www.codeproject.com/Articles/3479/The-Bip-Buffer-The-Circular-Buffer-with-a-Twist "The Bip Buffer - The Circular Buffer with a Twist"]</ref>
 
संपूर्ण डेटा अनुक्रम के एक निश्चित आकार के संकुचित प्रतिनिधित्व को बनाए रखने के लिए निश्चित आकार के संकुचित गोलाकार बफ़र प्राथमिक संख्या सिद्धांत पर आधारित एक वैकल्पिक अनुक्रमण रणनीति का उपयोग करते हैं।<ref name="gunther">{{cite journal|last1=Gunther|first1=John C.|title=Algorithm 938: Compressing circular buffers|journal=ACM Transactions on Mathematical Software|date=March 2014|volume=40|issue=2|pages=1–12|doi=10.1145/2559995|s2cid=14682572 }}</ref>
संपूर्ण डेटा अनुक्रम के एक निश्चित आकार के संकुचित प्रतिनिधित्व को बनाए रखने के लिए निश्चित आकार के संकुचित गोलाकार बफ़र प्राथमिक संख्या सिद्धांत पर आधारित एक वैकल्पिक अनुक्रमण रणनीति का उपयोग करते हैं।<ref name="gunther">{{cite journal|last1=Gunther|first1=John C.|title=Algorithm 938: Compressing circular buffers|journal=ACM Transactions on Mathematical Software|date=March 2014|volume=40|issue=2|pages=1–12|doi=10.1145/2559995|s2cid=14682572 }}</ref>




Line 97: Line 99:


{{Data structures}}
{{Data structures}}
[[Category: स्मृति]] [[Category: सरणियों]]


[[Category: Machine Translated Page]]
[[Category:All accuracy disputes]]
[[Category:Articles with disputed statements from January 2022]]
[[Category:Articles with invalid date parameter in template]]
[[Category:Collapse templates]]
[[Category:Created On 02/05/2023]]
[[Category:Created On 02/05/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists]]
[[Category:Pages with script errors]]
[[Category:Sidebars with styles needing conversion]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates generating microformats]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that are not mobile friendly]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:Webarchive template wayback links]]
[[Category:Wikipedia metatemplates]]
[[Category:सरणियों]]
[[Category:स्मृति]]

Latest revision as of 11:24, 17 May 2023

File:Circular buffer.svg
संकल्पनात्मक रूप से एक गोलाकार बफ़र, एक छल्ला दिखा रहा। यह दृष्टि से दिखाता है कि बफर का कोई वास्तविक अंत नहीं है और यह बफर के चारों ओर लूप कर सकता है। हालाँकि, चूंकि मेमोरी को कभी भी रिंग के रूप में भौतिक रूप से नहीं बनाया जाता है, प्रायः एक रैखिक प्रतिनिधित्व का उपयोग किया जाता है जैसा कि नीचे किया गया है।

कंप्यूटर विज्ञान में, एक गोलाकार बफर, गोलाकार कतार, चक्रीय बफर या रिंग बफर एक डेटा संरचना है जो एक एकल, निश्चित आकार के बफर का उपयोग करता है जैसे कि यह एंड-टू-एंड से जुड़ा हो। यह संरचना आकड़ों के प्रवाह को बफ़र करने के लिए स्वयं को आसानी से किराये पर देती है।[1] हार्डवेयर में शुरुआती गोलाकार बफर कार्यान्वयन थे।[2][3]


समीक्षा

File:Circular Buffer Animation.gif
एक 24-बाइट कीबोर्ड गोलाकार बफर। जब राइट पॉइंटर रीड पॉइंटर तक पहुँचने वाला होता है - क्योंकि माइक्रोप्रोसेसर प्रतिक्रिया नहीं दे रहा है - बफर कीस्ट्रोक रिकॉर्ड करना बंद कर देता है। कुछ कंप्यूटरों पर एक बीप बजाया जाएगा।

एक गोलाकार बफर पहले खाली प्रारम्भहोता है और इसकी एक निर्धारित लंबाई होती है। नीचे दिए गए आरेख में एक 7-तत्व बफ़र है:

File:Circular buffer - empty.svgमान लें कि 1 एक गोलाकार बफर के केंद्र में लिखा गया है (गोलाकार बफर में सटीक प्रारंभिक स्थान महत्वपूर्ण नहीं है):
File:Circular buffer - XX1XXXX.svgफिर मान लें कि गोलाकार बफर में दो और तत्व जोड़े गए हैं - 2 और 3 - जो 1 के बाद रखे जाते हैं:
File:Circular buffer - XX123XX.svgयदि दो तत्वों को हटा दिया जाता है, तो वृत्ताकार बफ़र के अंदर के दो सबसे पुराने मान हटा दिए जाएंगे। गोलाकार बफ़र्स FIFO (पहला अंदर, पहला बाहर) तर्क का उपयोग करते हैं। उदाहरण में, 1 और 2 गोलाकार बफर में प्रवेश करने वाले पहले थे, बफर के अंदर 3 को छोड़कर, वे पहले हटाए जाने वाले हैं।
Circular buffer - XXXX3XX.svgयदि बफ़र में 7 तत्व हैं, तो यह पूरी तरह से भरा हुआ है:
Circular buffer - 6789345.svgगोलाकार बफर की एक विशेषता यह है कि जब यह भर जाता है और बाद में राइट किया जाता है, तो यह सबसे पुराने डेटा को अधिलेखित करना प्रारम्भ कर देता है। वर्तमान उदाहरण में, दो और तत्व - ए और बी - जोड़े गए हैं और वे 3 और 4 को अधिलेखित करते हैं:
File:Circular buffer - 6789AB5.svgवैकल्पिक रूप से, बफ़र को प्रबंधित करने वाले रूटीन डेटा को अधिलेखित होने से रोक सकते हैं और त्रुटि वापस कर सकते हैं या अपवाद बढ़ा सकते हैं। डेटा अधिलेखित किया गया है या नहीं, यह बफ़र रूटीन या गोलाकार बफ़र का उपयोग करने वाले एप्लिकेशन के शब्दार्थ पर निर्भर करता है।

अंत में, यदि दो तत्वों को अब हटा दिया जाता है तो जो लौटाया जाएगा वह 3 और 4 नहीं बल्कि ए और बी है क्योंकि ए और बी ने 3 और 4 को अधिलेखित कर दिया है जिससे बफर उत्पन्न होता है:

File:Circular buffer - X789ABX.svg

उपयोग

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

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

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

गोलाकार बफर यांत्रिकी

हार्डवेयर में गोलाकार बफर इम्प्लीमेंटेशन, यूएस पेटेंट 3979733, Fig4
एक सूचक (कंप्यूटर प्रोग्रामिंग) और तीन पूर्णांकों का उपयोग करके एक गोलाकार बफर लागू किया जा सकता है:
  • मेमोरी में बफर स्टार्ट
  • बफर क्षमता (लंबाई)
  • बफर इंडेक्स में लिखें (अंत)
  • बफर इंडेक्स से पढ़ें (प्रारंभ)

यह छवि लंबाई = 7 के साथ आंशिक रूप से पूर्ण बफ़र दिखाती है:

File:Circular buffer - XX123XX with pointers.svgयह छवि चार तत्वों (संख्या 1 से 4) के साथ एक पूर्ण बफर दिखाती है जिसे अधिलेखित किया गया है:
Circular buffer - 6789AB5 with pointers.svgप्रारम्भ में इंडेक्स एंड और स्टार्ट 0 पर सेट होते हैं। गोलाकार बफर राइट ऑपरेशन एक एलिमेंट को एंड इंडेक्स पोजीशन में लिखता है और एंड इंडेक्स को अगले बफर पोजीशन में बढ़ा दिया जाता है। गोलाकार बफर रीड ऑपरेशन स्टार्ट इंडेक्स पोजीशन से एक एलिमेंट को पढ़ता है और स्टार्ट इंडेक्स को अगले बफर पोजीशन में बढ़ा दिया जाता है।

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

निम्नलिखित स्रोत कोड एक सी कार्यान्वयन है। फंक्शन put() एक आइटम को बफर में रखता है, फंक्शन get() बफर से एक आइटम प्राप्त करता है: 

#define BUFLEN 3

int buf[BUFLEN];   /* array to be treated as circular buffer of BUFLEN integers */
int end = 0;       /* write index */
int start = 0;     /* read index */

void put(int item)
{
    buf[end++] = item;
    end %= BUFLEN;
}

int get()
{
    int item = buf[start++];
    start %= BUFLEN;
    return item;
}


अनुकूलन

वर्चुअल मेमोरी के दो सन्निहित क्षेत्रों के लिए अंतर्निहित बफर मैप द्वारा एक गोलाकार-बफर कार्यान्वयन को अनुकूलित किया जा सकता है।[7][disputed – discuss] (स्वाभाविक रूप से, अंतर्निहित बफ़र की लंबाई तब सिस्टम के पृष्ठ के कुछ गुणकों के बराबर होनी चाहिए।) गोलाकार बफ़र से पढ़ना और लिखना तब प्रत्यक्ष मेमोरी एक्सेस के माध्यम से अधिक दक्षता के साथ किया जा सकता है; वे एक्सेस जो पहले वर्चुअल-मेमोरी क्षेत्र के अंत से परे हैं, स्वचालित रूप से अंतर्निहित बफर की प्रारम्भ में लपेटे जाएंगे। जब रीड ऑफ़सेट को दूसरे वर्चुअल-मेमोरी क्षेत्र में उन्नत किया जाता है, तो ऑफ़सेट-पढ़ना और लिखना-दोनों अंतर्निहित बफर की लंबाई से कम हो जाते हैं।

निश्चित-लंबाई-तत्व और सन्निहित-ब्लॉक गोलाकार बफर

गोलाकार बफर का संभवतः सबसे सामान्य संस्करण तत्वों के रूप में 8-बिट बाइट्स का उपयोग करता है।

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

पिंग-पोंग बफर को दो बड़े निश्चित-लंबाई वाले तत्वों के साथ एक बहुत ही विशिष्ट गोलाकार बफ़र माना जा सकता है।

बिप बफ़र (द्विपक्षीय बफ़र) एक गोलाकार बफ़र के समान है, इसे छोड़कर यह हमेशा सन्निहित ब्लॉक लौटाता है जो चर लंबाई हो सकता है। यह एपीआई में उपयोग किए जाने वाले बफर की क्षमता को बनाए रखते हुए एक गोलाकार बफर के लगभग सभी दक्षता लाभ प्रदान करता है जो केवल सन्निहित ब्लॉकों को स्वीकार करता है।[8]

संपूर्ण डेटा अनुक्रम के एक निश्चित आकार के संकुचित प्रतिनिधित्व को बनाए रखने के लिए निश्चित आकार के संकुचित गोलाकार बफ़र प्राथमिक संख्या सिद्धांत पर आधारित एक वैकल्पिक अनुक्रमण रणनीति का उपयोग करते हैं।[9]


संदर्भ

  1. ↑ Arpaci-Dusseau, Remzi H.; Arpaci-Dusseau, Andrea C. (2014), Operating Systems: Three Easy Pieces [Chapter: Condition Variables, figure 30.13] (PDF), Arpaci-Dusseau Books
  2. ↑ Hartl, Johann. "Impulswiederholer - टेलीफोन एक्सचेंज (वीडियो)". Youtube. Retrieved 15 December 2021.
  3. ↑ Fraser, Alexander Gibson. "US patent 3979733 Digital data communications system packet switch". US States Patent. Retrieved 15 December 2021.
  4. ↑ Chandrasekaran, Siddharth (2014-05-16). "Implementing Circular/Ring Buffer in Embedded C". Embed Journal. EmbedJournal Team. Archived from the original on 11 February 2017. Retrieved 14 August 2017.
  5. ↑ Circular buffers kernel.org
  6. ↑ Morin, Pat. "ArrayQueue: An Array-Based Queue". Open Data Structures (in pseudocode). Archived from the original on 31 August 2015. Retrieved 7 November 2015.
  7. ↑ Mike Ash (2012-02-17). "mikeash.com: Friday Q&A 2012-02-17: Ring Buffers and Mirrored Memory: Part II". mikeash.com. Archived from the original on 2019-01-11. Retrieved 2019-01-10.
  8. ↑ Simon Cooke (2003), "The Bip Buffer - The Circular Buffer with a Twist"
  9. ↑ Gunther, John C. (March 2014). "Algorithm 938: Compressing circular buffers". ACM Transactions on Mathematical Software. 40 (2): 1–12. doi:10.1145/2559995. S2CID 14682572.


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=गोलाकार_बफर&oldid=161251’