गोलाकार बफर

File:Circular buffer.svg

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

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

समीक्षा

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 को छोड़कर, वे पहले हटाए जाने वाले हैं।

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

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

वैकल्पिक रूप से, बफ़र को प्रबंधित करने वाले रूटीन डेटा को अधिलेखित होने से रोक सकते हैं और त्रुटि वापस कर सकते हैं या अपवाद बढ़ा सकते हैं। डेटा अधिलेखित किया गया है या नहीं, यह बफ़र रूटीन या गोलाकार बफ़र का उपयोग करने वाले एप्लिकेशन के शब्दार्थ पर निर्भर करता है।

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

उपयोग

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

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

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

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

File:Hardware circular buffer implementation patent us3979733 fig4.png

हार्डवेयर में गोलाकार बफर इम्प्लीमेंटेशन, यूएस पेटेंट 3979733, Fig4

एक सूचक (कंप्यूटर प्रोग्रामिंग) और तीन पूर्णांकों का उपयोग करके एक गोलाकार बफर लागू किया जा सकता है:

• मेमोरी में बफर स्टार्ट
• बफर क्षमता (लंबाई)
• बफर इंडेक्स में लिखें (अंत)
• बफर इंडेक्स से पढ़ें (प्रारंभ)

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

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

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

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

निम्नलिखित स्रोत कोड एक सी कार्यान्वयन है। फंक्शन 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;
}

अनुकूलन

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

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

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

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

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

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

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

बाहरी संबंध

• CircularBuffer at the Portland Pattern Repository
• Boost:

  Templated Circular Buffer Container: circular_buffer/base.hpp

  Synchronized Bounded Queue: sync_bounded_queue.hpp

• CB in Linux kernel
• CB in DSP
• Circular queue in C Archived 2018-10-29 at the Wayback Machine