بافر چرخشی
بافِر چرخشی یا بافر حلقه‌ای یک ساختمان داده است که از یک حافظه میانگیر با حجم ثابت به گونه‌ای استفاده می‌کند که گویا ابتدا و انتهای آن به هم وصل شده‌اند. این ساختمان در ذخیره کردن روانه ی داده‌ها (داده‌های در حال دریافت) کمک می‌کند.
یکی از کاربردهای بافر چرخشی این است که نیازی نیست هنگامی که یکی از عناصر حذف شد، مکان بقیهٔ عناصر را تغییر دهیم. به عبارت دیگر، بافر چرخشی برای FIFO (خروج به ترتیب ورود) مناسب است در حالی که بافرهای معمولی برای LIFO (هر داده‌ای که آخر آمد، اول خارج می‌شود) مناسب هستند.
بافر چرخشی راهبرد خوبی برای اجرای یک صف با حجم ثابت است. باید برای صف ابتدا یک حجم مشخص کنیم، آنگاه بافر چرخشی کاملاً به صورت ایده‌آل رفتار خواهد کرد.
در بعضی مواقع، رونویسی یک بافر حلقوی می‌تواند برای مثال در مولتی مدیا (چندرسانه‌ای) استفاده شود. اگر این بافر به عنوان بافر احاطه شده در مسئله تولیدکننده-مصرف‌کننده استفاده شود، پس احتمالاً دلخواه مصرف‌کننده است (برای مثال یک مولد صوتی) که داده‌های قدیمی را رونویسی کند اگر مصرف‌کننده (برای مثال کارت صدا) نتواند به‌طور لحظه‌ای خودش را برساند و ادامه دهد همچنین خانواده LZ77 از الگوریتم‌های فشرده سازی بدون ازدست رفتن داده بر این فرض عمل می‌کند که رشته‌هایی که اخیراً بیشتر در جریان داده دید شده‌اند بیشتر احتمال دارند که به زودی در جریان رخ دهند. پیاده‌سازی این اخیرترین داده‌ها را در یک بافر حلقوی ذخیره می‌کند.
نخست، بافر چرخشی با طولی از پیش تعیین شده و خالی از داده شروع به کار می‌کند. برای نمونه، در اینجا یک بافر ۷ خانه‌ای می‌بینیم:
به عنوان مثال، عدد ۱ را در یکی از خانه‌های بافر قرار می‌دهیم (موقعیت اولین داده مهم نیست):
سپس برای نمونه اعداد ۲ و ۳ را به بافر اضافه می‌کنیم که آنگاه پس از ۱ قرار می‌گیرند:
اگر بخواهیم دو داده را از بافر حذف کنیم، قدیمی‌ترین داده‌ها حذف خواهند شد، برای نمونه در اینجا ۱ و ۲ حذف می‌شوند:
اگر بافر درون خود ۷ عنصر (به اندازهٔ ظرفیت خود) داشت، یعنی کاملاً پر شده‌است:
حال اگر بخواهیم دو دادهٔ تازه به بافر اضافه کنیم -درحالی که پر شده‌است- شروع به جای نوشتن (overwrite) قدیمی‌ترین داده‌ها می‌کند. برای مثال در اینجا اگر دو دادهٔ A و B را اضافه کنیم، جای ۳ و ۴ که قدیمی‌ترین داده‌ها هستند می‌آیند:
البته روتینی که بافر را مدیریت می‌کند می‌تواند جلوی جایگزین کردن داده‌های جدید را بگیرد و جای آن، یک ارور برگرداند یا یک مدیریت استثناء انجام دهد.
در نهایت، اگر بخواهیم داده‌ای را حذف کنیم، ۵ و ۶ خواهد بود، نه ۳ و ۴، چون اعداد ۳ و ۴ با A و B جایگزین شدند:
در مثال بالا حرفی از مکانیزم روش مدیریت بافر زده نشد.
در حالت کلی، بافر چرخشی چهار اشاره گر دارد:
همچنین در زبان‌هایی که در آن‌ها اشاره گر وجود ندارد می‌توان از یک بافر با حجم ثابت و دو عدد صحیح برای مشخص نمودن سر و ته بافر استفاده کرد.
چند نمونه برای توضیحات بالا (البته روش‌های نامگذاری اشاره گرها ممکن است متفاوت باشد، این فقط یک راه برای انجام آن است): در تصویر زیر یک بافر نیمه پر را می‌بینیم:
در تصویر زیر یک بافر پر را با دو عنصر جایگزین شده می‌بینیم، در این حالت اشاره گر نقطهٔ شروع نیز جلوتر رفته:
یک اِشکال کوچک تکیه کردن بر اشاره‌گرها یا شاخص‌های وابسته به ابتدا و انتهای داده این است که در صورتی که بافر کاملاً پر باشد، هر دو اشاره‌گر به یک عنصر اشاره می‌کنند:
این دقیقاً همان وضعیتی است وقتی که بافر خالی باشد:
برای حل این سردرگمی چندین راه حل وجود دارد:
این طرح همواره یک شکاف را تخصیص نیافته باقی می‌گذارد. یک بافر پر نهایتاً
مزیت آن: معایب آن:
این روش اشاره‌گر انتهایی را با یک شمارنده که تعداد آیتم‌های قابل خواندن در بافر را نگه می‌دارد، جایگزین می‌کند. این بدون هیچ ابهامی جواب می‌دهد زمانی که بافر پر یا خالی باشد و اجازه استفاده کامل از شکاف‌ها را می‌دهد.
تأثیر بر روی کارایی باید ناچیز باشد، از آنجایی که درست است این روش هزینه‌های نگهداری شمارنده و محاسبه شکاف انتها را بر روی write اضافه می‌کند ولی احتیاج به نگهداری اشاره‌گر انتهایی را حذف می‌کند و آزمون پر بودن را ساده می‌کند.
مزیت آن: معایب آن: نکته: وقتی از نشان‌بر در مدل تولیدکننده-مصرف‌کننده، استفاده می‌شود نشان بر به عنوان شمارنده پر شدن عمل می‌کند.
یک راه حل دیگر این است که تعداد دفعات بسته شدن هر اشاره‌گر خواندن و نوشتن را به خاطر بسپاریم و با مقایسه آن وضعیت پر یا خالی را تمایز دهیم. در واقع تنها زوج بودن عدد تعداد بسته شدن‌ها نیاز است، بنابراین کافیست که یک بیت اضافه نگه داریم. می‌توانید این را ببینید مثل این که بافر یک آینه محاری اضافه می‌کند و اشاره‌گرها یا به بافر نرمال یا به بافر معکوس در آینه اشاره می‌کنند:
به بالا نگاه کنید. آسان است وقتی که اشاره‌گرها (شامل آن پراهمیت‌ترین بیت اضافی) برابرند، بافر خالی است، درحالیکه اگر اشاره‌گرها تنها در یک بیت msb یا Most Significant Bit فرق کنند، بافر پر هست.
مزایای آن: معایب آن:
یک راه حل دیگر این است که تعداد آیتم‌های نوشته شده بر و خوانده شده از بافر حلقوی است. هردو شمارش ذخیره می‌شوند در یک متغیر صحیح علامت دار (مثبت و منفی) با محدودیت عددی بزرگتر از تعداد آیتم‌هایی که می‌توانند ذخیره شوند و مجازند آزادانه بسته شوند (به اشاره‌گر).
تفاوت نامنفی (قدرمطلق) write_count - read_count همیشه نمایانگر تعداد آیتم‌های قرار گرفته در بافر است که هنوز دریافت نشده‌اند. این می‌تواند بیانگر این باشد که بافر خالی است، نیمه پر است یا کاملاً پر است (بدون هدر دادن یک فضای ذخیره‌سازی) یا در حالت سرریزی.
مزیت آن: عیب آن:
این ممکن است که با استفاده از شاخص‌ها (index) به جای اشاره‌گرها راه حل قبلی را ارتقاء داد: شاخص‌ها می‌توانند تعداد خواندن/نوشتن‌ها را به حای ذخیره در حاشیه شروع بافر، در متغیرهای جداگانه‌ای مانند بالا ذخیره کنند که اکنون پاک می‌شوند و شاخص‌های وابسته در پرواز به دست می‌آید که با تقسیم عملیات پیمانه بر روی طول بافر بدست می‌آید.
مزیت آن: معایب آن: در کامپیوترهای دودویی هر دو عیب ظاهر می‌شوند اگر طول بافر توانی از دو باشد
یک راه حل دیگر این است که یک flag نگه داریم که نشانگر اینگه آخرین عملیات read بوده یا write. اگر دو اشاره‌گر یکسان بودند، flag نشان می‌دهد بافر پر است یا خالی: اگر آخرین عملیات write بود بافر باید پر باشد و بلعکس اگر read بود بافر باید خالی باشد.
مزایای آن: عیب آن:
این روش مشکل دور تا دوری (wrap-around) را حل می‌کند به وسیله تکه کردن بافر به یک بخش اولیه و یک بخش ثانویه. بخش ثانویه همیشه از ابتدای بافر شروع می‌شود و فعال نمی‌شود تا وقتی که بخش اولیه به انتهای بافر رسیده باشد. علاوه بر این اگر بخش اولیه از داده خالی باشد، بخش ثانویه تبدیل به بخش اولیه جدید می‌شود.
مزایای آن: معایب آن:
مقداری پیچیده‌تر وجود چندین اشاره‌گر خواندن روی یک بافر حلقوی است. این هنگامی مفید است که n ریسمان دارید که از یک بافر می‌خوانند، اما یک ریسمان روی بافر می‌نویسد.
خیلی پیچیده‌تر تکه‌های متفاوت از داده در یک بافر یکسان است. نویسنده نه تنها عناصر را بر روی بافر می‌نویسد بلکه آن عناصر را به قطعات نسبت می‌دهد.[نیازمند استناد]
خواننده نه تنها باید بتواند از بافر بخواند بلکه باید از مرزهای قطعات اطلاع کسب کند.
مثال: نویسنده اطلاعاتی را از فایل‌های کوچک می‌خواند و بر روی یک بافر یکسان ذخیره می‌کند. خواننده داده را می‌خواند، ولی نیاز دارد بداند کی و کدام فایل از موقعیت داده شده شروع می‌شوند.
شاید رایج‌ترین نسخه بافر حلقوی از بایت‌های ۸-بیتی به عنوان عنصر استفاده می‌کنند.
بعضی از پیاده‌سازی‌های بافر حلقوی از عناصر با اندازه ثابت که بزرگتر از بایت‌های ۸-بیتی اند استفاده می‌کنند — ۱۶-بیتی‌های صحیح برای بافرهای صوتی، سلول‌های ۵۳-بایتی ATM برای بافرهای مخابراتی و.. هرکدام پیوسته است و ترتیب داده صحیحی دارد، پس خواندن و نوشتن نرم‌افزاری این مقادیر می‌تواند سریع نر از نرم‌افزاری باشد که با مقادیر نامرتب و ناپیوسته سر و کار دارد.
بافر پینگ پونگی می‌تواند به عنوان یک باقر حلقوی خیلی خاص با دقیقاً دو عنصر بزرگ با اندازه ثابت در نظر گرفته شود
بافر بیپ (به انگلیسی: Bip Buffer) ساخت Simon Cooke یک بافر بسیار شبیه بافر حلقوی است، به جز آنکه همیشه بلوک پیوسته برمی‌گرداند (که می‌تواند طول متغیر داشته باشد)