بافر چرخشی

بافِر چرخشی (به انگلیسی: Circular buffer) یا بافر حلقه‌ای (به انگلیسی: Ring buffer) یک ساختمان داده است که از یک حافظه میانگیر با حجم ثابت به گونه‌ای استفاده می‌کند که گویا ابتدا و انتهای آن به هم وصل شده‌اند. این ساختمان در ذخیره کردن روانه ی داده‌ها (داده‌های در حال دریافت) کمک می‌کند.

یک حلقه نمایانگر مفهوم بافر چرخشی. این تصویر نشان می‌دهد که بافر چرخشی در حقیقت پایانی ندارد. اگرچه، از آنجایی که از لحاظ فیزیکی حافظه‌ای به صورت حلقه‌ای ساخته نشده، برای تشکیل آن باید مانند پایین یک عملیات خطی انجام گیرد.

کاربردها

یکی از کاربردهای بافر چرخشی این است که نیازی نیست هنگامی که یکی از عناصر حذف شد، مکان بقیهٔ عناصر را تغییر دهیم. به عبارت دیگر، بافر چرخشی برای FIFO (خروج به ترتیب ورود) مناسب است در حالی که بافرهای معمولی برای LIFO (هر داده‌ای که آخر آمد، اول خارج می‌شود) مناسب هستند.

بافر چرخشی راهبرد خوبی برای اجرای یک صف با حجم ثابت است. باید برای صف ابتدا یک حجم مشخص کنیم، آنگاه بافر چرخشی کاملاً به صورت ایده‌آل رفتار خواهد کرد.

در بعضی مواقع، رونویسی یک بافر حلقوی می‌تواند برای مثال در مولتی مدیا (چندرسانه‌ای) استفاده شود. اگر این بافر به عنوان بافر احاطه شده در مسئله تولیدکننده-مصرف‌کننده استفاده شود، پس احتمالاً دلخواه مصرف‌کننده است (برای مثال یک مولد صوتی) که داده‌های قدیمی را رونویسی کند اگر مصرف‌کننده (برای مثال کارت صدا) نتواند به‌طور لحظه‌ای خودش را برساند و ادامه دهد همچنین خانواده LZ77 از الگوریتم‌های فشرده سازی بدون ازدست رفتن داده بر این فرض عمل می‌کند که رشته‌هایی که اخیراً بیشتر در جریان داده دید شده‌اند بیشتر احتمال دارند که به زودی در جریان رخ دهند. پیاده‌سازی این اخیرترین داده‌ها را در یک بافر حلقوی ذخیره می‌کند.

روش کار

نخست، بافر چرخشی با طولی از پیش تعیین شده و خالی از داده شروع به کار می‌کند. برای نمونه، در اینجا یک بافر ۷ خانه‌ای می‌بینیم:

به عنوان مثال، عدد ۱ را در یکی از خانه‌های بافر قرار می‌دهیم (موقعیت اولین داده مهم نیست):

سپس برای نمونه اعداد ۲ و ۳ را به بافر اضافه می‌کنیم که آنگاه پس از ۱ قرار می‌گیرند:

اگر بخواهیم دو داده را از بافر حذف کنیم، قدیمی‌ترین داده‌ها حذف خواهند شد، برای نمونه در اینجا ۱ و ۲ حذف می‌شوند:

اگر بافر درون خود ۷ عنصر (به اندازهٔ ظرفیت خود) داشت، یعنی کاملاً پر شده‌است:

حال اگر بخواهیم دو دادهٔ تازه به بافر اضافه کنیم -درحالی که پر شده‌است- شروع به جای نوشتن (overwrite) قدیمی‌ترین داده‌ها می‌کند. برای مثال در اینجا اگر دو دادهٔ A و B را اضافه کنیم، جای ۳ و ۴ که قدیمی‌ترین داده‌ها هستند می‌آیند:

البته روتینی که بافر را مدیریت می‌کند می‌تواند جلوی جایگزین کردن داده‌های جدید را بگیرد و جای آن، یک ارور برگرداند یا یک مدیریت استثناء انجام دهد.

در نهایت، اگر بخواهیم داده‌ای را حذف کنیم، ۵ و ۶ خواهد بود، نه ۳ و ۴، چون اعداد ۳ و ۴ با A و B جایگزین شدند:

مکانیزم بافر چرخشی

در مثال بالا حرفی از مکانیزم روش مدیریت بافر زده نشد.

نقاط شروع/پایان (سر/ته)

در حالت کلی، بافر چرخشی چهار اشاره گر دارد:

• نشانگر محل واقعی بافر در حافظه
• نشانگر محل پایان بافر (یا همچنین: حجم بافر)
• نشانگر محل شروع داده‌ها (یا همچنین: مقدار داده‌های نوشته شده در بافر)
• نشانگر محل پایان داده‌ها (یا همچنین: مقدار داده‌های خوانده شده از بافر)

همچنین در زبان‌هایی که در آن‌ها اشاره گر وجود ندارد می‌توان از یک بافر با حجم ثابت و دو عدد صحیح برای مشخص نمودن سر و ته بافر استفاده کرد.

چند نمونه برای توضیحات بالا (البته روش‌های نامگذاری اشاره گرها ممکن است متفاوت باشد، این فقط یک راه برای انجام آن است): در تصویر زیر یک بافر نیمه پر را می‌بینیم:

در تصویر زیر یک بافر پر را با دو عنصر جایگزین شده می‌بینیم، در این حالت اشاره گر نقطهٔ شروع نیز جلوتر رفته:

مشکلات

تمایز بافر پر و خالی

یک اِشکال کوچک تکیه کردن بر اشاره‌گرها یا شاخص‌های وابسته به ابتدا و انتهای داده این است که در صورتی که بافر کاملاً پر باشد، هر دو اشاره‌گر به یک عنصر اشاره می‌کنند:

این دقیقاً همان وضعیتی است وقتی که بافر خالی باشد:

برای حل این سردرگمی چندین راه حل وجود دارد:

• همیشه یک شکاف را باز نگه دارید.
• از یک شمارنده پر شدن برای تشخیص دو مورد استفاده کنید.
• از یک بیت آینه‌ای اضافه برای تشخیص دو مورد استفاده کنید.
• از شمارنده تعداد خواندن و نوشتن برای گرفتن شماره پر شدن استفاده کنید.
• از شاخص مطلق استفاده کنید.
• آخرین عملیات را ضبط کنید. بافر را به دو ناحیه تقسیم کنید.

باز نگه داشتن همیشگی یک شکاف

این طرح همواره یک شکاف را تخصیص نیافته باقی می‌گذارد. یک بافر پر نهایتاً

(۱ - اندازه) شکاف دارد. اگر هر دو اشاره‌گر به یک شکاف اشاره کنند، آن بافر خالی است. اگر اشاره‌گر انتهایی (write) اشاره کند به شکاف ماقبل شکافی که اشاره‌گر ابتدایی (read) به آن اشاره می‌کرد، بافر پر است.

مزیت آن:

• راه حل ساده و قدرتمند است.
  

معایب آن:

• یک شکاف از دست می‌رود، بنابراین این یک سازش بد است وقتی که اندازه بافر کوچک باشد یا شکاف بزرگ باشد یا در سخت‌افزار پیاده‌سازی شده باشد.
• آزمون پر بودن به عملگر باقی‌مانده (ماژولو) نیازمند است.

بهره‌گیری از شمارنده پر شدن

این روش اشاره‌گر انتهایی را با یک شمارنده که تعداد آیتم‌های قابل خواندن در بافر را نگه می‌دارد، جایگزین می‌کند. این بدون هیچ ابهامی جواب می‌دهد زمانی که بافر پر یا خالی باشد و اجازه استفاده کامل از شکاف‌ها را می‌دهد.

تأثیر بر روی کارایی باید ناچیز باشد، از آنجایی که درست است این روش هزینه‌های نگهداری شمارنده و محاسبه شکاف انتها را بر روی write اضافه می‌کند ولی احتیاج به نگهداری اشاره‌گر انتهایی را حذف می‌کند و آزمون پر بودن را ساده می‌کند.

مزیت آن:

• آزمون پر/خالی بودن آن ساده است
  

معایب آن:

• شما به عملگر باقی‌مانده (ماژولو) برای خواندن و نوشتن نیاز دارید
• عملیات خواندن و نوشتن باید پهنه شمارنده را به اشتراک بگذارند، بنابراین به همگام سازی در وضعیت پردازش چند هسته‌ای نیاز دارد.
  

نکته: وقتی از نشان‌بر در مدل تولیدکننده-مصرف‌کننده، استفاده می‌شود نشان بر به عنوان شمارنده پر شدن عمل می‌کند.

معکوس سازی

یک راه حل دیگر این است که تعداد دفعات بسته شدن هر اشاره‌گر خواندن و نوشتن را به خاطر بسپاریم و با مقایسه آن وضعیت پر یا خالی را تمایز دهیم. در واقع تنها زوج بودن عدد تعداد بسته شدن‌ها نیاز است، بنابراین کافیست که یک بیت اضافه نگه داریم. می‌توانید این را ببینید مثل این که بافر یک آینه محاری اضافه می‌کند و اشاره‌گرها یا به بافر نرمال یا به بافر معکوس در آینه اشاره می‌کنند:

به بالا نگاه کنید. آسان است وقتی که اشاره‌گرها (شامل آن پراهمیت‌ترین بیت اضافی) برابرند، بافر خالی است، درحالیکه اگر اشاره‌گرها تنها در یک بیت msb یا Most Significant Bit فرق کنند، بافر پر هست.

مزایای آن:

• آزمون پر/خالی بوردن ساده است.
• نیازی به عملگر ماژولو (یا باقیمانده) نیست
• چشمه و چاهک داده می‌توانند سیاست‌های مستقلی از هم برای تعامل با یک بافر پر و سرریز پیاده‌سازی کنند درحالیکه قانونی را که تنها چشمه داده تعداد نوشتن و چاهک داده تعداد خواندن را تغییر می‌دهد، رعایت می‌کند. این می‌تواند منتهی به یک پیاده‌سازی ظریف و قدرتمند یک بافر حلقوی حتی در محیط پردازش چند هسته‌ای شود.[نیازمند استناد]
  

معایب آن:

• شما به یک بیت اضافه برای اشاره‌گر read و write نیاز دارید

شمارنده‌های خواندن/نوشتن

یک راه حل دیگر این است که تعداد آیتم‌های نوشته شده بر و خوانده شده از بافر حلقوی است. هردو شمارش ذخیره می‌شوند در یک متغیر صحیح علامت دار (مثبت و منفی) با محدودیت عددی بزرگتر از تعداد آیتم‌هایی که می‌توانند ذخیره شوند و مجازند آزادانه بسته شوند (به اشاره‌گر).

تفاوت نامنفی (قدرمطلق) write_count - read_count همیشه نمایانگر تعداد آیتم‌های قرار گرفته در بافر است که هنوز دریافت نشده‌اند. این می‌تواند بیانگر این باشد که بافر خالی است، نیمه پر است یا کاملاً پر است (بدون هدر دادن یک فضای ذخیره‌سازی) یا در حالت سرریزی.

مزیت آن:

• چشمه و چاهک داده می‌توانند سیاست‌های مستقلی از هم برای تعامل با یک بافر پر و سرریز پیاده‌سازی کنند درحالیکه قانونی را که تنها چشمه داده تعداد نوشتن و چاهک داده تعداد خواندن را تغییر می‌دهد، رعایت می‌کند. این می‌تواند منتهی به یک پیاده‌سازی ظریف و قدرتمند یک بافر حلقوی حتی در محیط پردازش چند هسته‌ای شود.
  

عیب آن:

• شما به دو متغیر اضافه نیاز دارید

شاخص‌های مطلق

این ممکن است که با استفاده از شاخص‌ها (index) به جای اشاره‌گرها راه حل قبلی را ارتقاء داد: شاخص‌ها می‌توانند تعداد خواندن/نوشتن‌ها را به حای ذخیره در حاشیه شروع بافر، در متغیرهای جداگانه‌ای مانند بالا ذخیره کنند که اکنون پاک می‌شوند و شاخص‌های وابسته در پرواز به دست می‌آید که با تقسیم عملیات پیمانه بر روی طول بافر بدست می‌آید.

مزیت آن:

• به هیچ متغیر اضافه‌ای نیاز نیست.
  

معایب آن:

• هر دسترسی به یک عملگر ماژولو نیاز دارد.
• اگر شمارش بسته‌بندی ممکن باشد، منطق پیچیده‌ای می‌تواند نیاز شود اگر طول بافر مقسوم علیه ظرفیت شمارنده نباشد.
  

در کامپیوترهای دودویی هر دو عیب ظاهر می‌شوند اگر طول بافر توانی از دو باشد

ضبط آخرین عملیات

یک راه حل دیگر این است که یک flag نگه داریم که نشانگر اینگه آخرین عملیات read بوده یا write. اگر دو اشاره‌گر یکسان بودند، flag نشان می‌دهد بافر پر است یا خالی: اگر آخرین عملیات write بود بافر باید پر باشد و بلعکس اگر read بود بافر باید خالی باشد.

مزایای آن:

• تنها یک بیت واحد نیاز است که ذخیره شود (که می‌تواند مخصوصاً زمانی که الگوریتم به شکل سخت‌افزاری پیاده می‌شود مفید باشد)
• آزمون پر/خالی بودن ساده است
  

عیب آن:

• شما به یک متغیر اضافه نیاز دارید
• عملیات]واندن و نوشتن باید flag را به اشتراک بگذارند، پس احتمالاً به یک همگام سازی در پردازش چند هسته‌ای نیاز می‌شود.

تقسیم بافر به دو ناحیه

این روش مشکل دور تا دوری (wrap-around) را حل می‌کند به وسیله تکه کردن بافر به یک بخش اولیه و یک بخش ثانویه. بخش ثانویه همیشه از ابتدای بافر شروع می‌شود و فعال نمی‌شود تا وقتی که بخش اولیه به انتهای بافر رسیده باشد. علاوه بر این اگر بخش اولیه از داده خالی باشد، بخش ثانویه تبدیل به بخش اولیه جدید می‌شود.

مزایای آن:

• آزمون پر/خالی بودن ساده است.
• به عملگر ماژولو نیازی نیست
  

معایب آن:

• به یک پوینتر متغیر نیاز است.
• عملیات read و write پیچیده‌اند.

چندین اشاره‌گر خواندن

مقداری پیچیده‌تر وجود چندین اشاره‌گر خواندن روی یک بافر حلقوی است. این هنگامی مفید است که n ریسمان دارید که از یک بافر می‌خوانند، اما یک ریسمان روی بافر می‌نویسد.

بافر تکه شده

خیلی پیچیده‌تر تکه‌های متفاوت از داده در یک بافر یکسان است. نویسنده نه تنها عناصر را بر روی بافر می‌نویسد بلکه آن عناصر را به قطعات نسبت می‌دهد.[نیازمند استناد]

خواننده نه تنها باید بتواند از بافر بخواند بلکه باید از مرزهای قطعات اطلاع کسب کند.

مثال: نویسنده اطلاعاتی را از فایل‌های کوچک می‌خواند و بر روی یک بافر یکسان ذخیره می‌کند. خواننده داده را می‌خواند، ولی نیاز دارد بداند کی و کدام فایل از موقعیت داده شده شروع می‌شوند.

انواع

شاید رایج‌ترین نسخه بافر حلقوی از بایت‌های ۸-بیتی به عنوان عنصر استفاده می‌کنند.

بعضی از پیاده‌سازی‌های بافر حلقوی از عناصر با اندازه ثابت که بزرگتر از بایت‌های ۸-بیتی اند استفاده می‌کنند — ۱۶-بیتی‌های صحیح برای بافرهای صوتی، سلول‌های ۵۳-بایتی ATM برای بافرهای مخابراتی و.. هرکدام پیوسته است و ترتیب داده صحیحی دارد، پس خواندن و نوشتن نرم‌افزاری این مقادیر می‌تواند سریع نر از نرم‌افزاری باشد که با مقادیر نامرتب و ناپیوسته سر و کار دارد.

بافر پینگ پونگی می‌تواند به عنوان یک باقر حلقوی خیلی خاص با دقیقاً دو عنصر بزرگ با اندازه ثابت در نظر گرفته شود

بافر بیپ (به انگلیسی: Bip Buffer) ساخت Simon Cooke یک بافر بسیار شبیه بافر حلقوی است، به جز آنکه همیشه بلوک پیوسته برمی‌گرداند (که می‌تواند طول متغیر داشته باشد)

منابع

• CircularBuffer at the Portland Pattern Repository
• Circular buffer - boost.org
• http://www.dspguide.com/ch28/2.htm
• ویکی‌پدیا انگلیسی