بافر چرخشی

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

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

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

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

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

در بعضی شرایط، مانند در رسانه ها، overwrite کردن بافر چرخشی میتواند مفید باشد.

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

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

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 - boost.org

ویکی‌پدیا انگلیسی