بافر چرخشی

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

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

کاربردها[ویرایش]

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

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

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

روش کار[ویرایش]

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

Circular buffer - empty.svg

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

Circular buffer - XX1XXXX.svg

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

Circular buffer - XX123XX.svg

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

Circular buffer - XXXX3XX.svg

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

Circular buffer - 6789345.svg

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

Circular buffer - 6789AB5.svg

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

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

Circular buffer - X789ABX.svg

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

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

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

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

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

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

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

Circular buffer - XX123XX with pointers.svg

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

Circular buffer - 6789AB5 with pointers.svg

مشکلات[ویرایش]

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

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

Circular buffer - 6789AB5 full.svg

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

Circular buffer - 6789AB5 empty.svg

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

باز نگه داشتن همیشگی یک شکاف[ویرایش]

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

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

مزیت آن:

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

معایب آن:

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

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

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

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

مزیت آن:

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

معایب آن:

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

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

معکوس سازی[ویرایش]

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

Circular buffer - mirror solution full and empty.png

به بالا نگاه کنید. آسان است وفتی که اشاره‌گرها (شامل آن پر اهیمت‌ترین بیت اضافی) برابرند، بافر خالی است، درحالیکه اگر اشاره‌گزها تنها در یک بیت 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 یک بافر بسیار شبیه بافر حلقوی است، به جز آنکه همیشه بلوک پیوسته برمی‌گرداند (که می‌تواند ظول متغیر داشته باشد)[۱]

منابع[ویرایش]