موضوع مقاله: بافر چرخشی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # بافر چرخشی | مقدمه: اگرچه، از آنجایی که از لحاظ فیزیکی حافظه‌ای به صورت حلقه‌ای ساخته نشده، برای تشکیل آن باید مانند پایین یک عملیات خطی انجام گیرد. | ## بخش 1: بافر چرخشی | کاربردها یکی از کاربردهای بافر چرخشی این است که نیازی نیست هنگامی که یکی از عناصر حذف شد، مکان بقیهٔ عناصر را تغییر دهیم. به عبارت دیگر، بافر چرخشی برای FIFO (خروج به ترتیب ورود) مناسب است در حالی که بافرهای معمولی برای LIFO (هر داده‌ای که آخر آمد، اول خارج می‌شود) مناسب هستند. باید برای صف ابتدا یک حجم مشخص کنیم، آنگاه بافر چرخشی کاملاً به صورت ایده‌آل رفتار خواهد کرد. در بعضی مواقع، رونویسی یک بافر حلقوی می‌تواند برای مثال در مولتی مدیا (چندرسانه‌ای) استفاده شود. اگر این بافر به عنوان بافر احاطه شده در مسئله تولیدکننده-مصرف‌کننده استفاده شود، پس احتمالاً دلخواه مصرف‌کننده است (برای مثال یک مولد صوتی) که داده‌های قدیمی را رونویسی کند اگر مصرف‌کننده (برای مثال کارت صدا) نتواند به‌طور لحظه‌ای خودش را برساند و ادامه دهد همچنین خانواده LZ77 از الگوریتم‌های فشرده سازی بدون ازدست رفتن داده بر این فرض عمل می‌کند که رشته‌هایی که اخیراً بیشتر در جریان داده دید شده‌اند بیشتر احتمال دارند که به زودی در جریان رخ دهند. روش کار نخست، بافر چرخشی با طولی از پیش تعیین شده و خالی از داده شروع به کار می‌کند. برای نمونه، در اینجا یک بافر ۷ خانه‌ای می‌بینیم: 250px به عنوان مثال، عدد ۱ را در یکی از خانه‌های بافر قرار می‌دهیم (موقعیت اولین داده مهم نیست): 250px سپس برای نمونه اعداد ۲ و ۳ را به بافر اضافه می‌کنیم که آنگاه پس از ۱ قرار می‌گیرند: 250px اگر بخواهیم دو داده را از بافر حذف کنیم، قدیمی‌ترین داده‌ها حذف خواهند شد، برای نمونه در اینجا ۱ و ۲ حذف می‌شوند: 250px اگر بافر درون خود ۷ عنصر (به اندازهٔ ظرفیت خود) داشت، یعنی کاملاً پر شده‌است: 250px حال اگر بخواهیم دو دادهٔ تازه به بافر اضافه کنیم -درحالی که پر شده‌است- شروع به جای نوشتن (overwrite) قدیمی‌ترین داده‌ها می‌کند. برای مثال در اینجا اگر دو دادهٔ A و B را اضافه کنیم، جای ۳ و ۴ که قدیمی‌ترین داده‌ها هستند می‌آیند: 250px البته روتینی که بافر را مدیریت می‌کند می‌تواند جلوی جایگزین کردن داده‌های جدید را بگیرد و جای آن، یک ارور برگرداند یا یک مدیریت استثناء انجام دهد. در نهایت، اگر بخواهیم داده‌ای را حذف کنیم، ۵ و ۶ خواهد بود، نه ۳ و ۴، چون اعداد ۳ و ۴ با A و B جایگزین شدند: 250px مکانیزم بافر چرخشی در مثال بالا حرفی از مکانیزم روش مدیریت بافر زده نشد. نقاط شروع/پایان (سر/ته) در حالت کلی، بافر چرخشی چهار اشاره گر دارد: نشانگر محل واقعی بافر در حافظه نشانگر محل پایان بافر (یا همچنین: حجم بافر) نشانگر محل شروع داده‌ها (یا همچنین: مقدار داده‌های نوشته شده در بافر) نشانگر محل پایان داده‌ها (یا همچنین: مقدار داده‌های خوانده شده از بافر) همچنین در زبان‌هایی که در آن‌ها اشاره گر وجود ندارد می‌توان از یک بافر با حجم ثابت و دو عدد صحیح برای مشخص نمودن سر و ته بافر استفاده کرد. چند نمونه برای توضیحات بالا (البته روش‌های نامگذاری اشاره گرها ممکن است متفاوت باشد، این فقط یک راه برای انجام آن است): در تصویر زیر یک بافر نیمه پر را می‌بینیم: 250px در تصویر زیر یک بافر پر را با دو عنصر جایگزین شده می‌بینیم، در این حالت اشاره گر نقطهٔ شروع نیز جلوتر رفته: 250px مشکلات تمایز بافر پر و خالی یک اِشکال کوچک تکیه کردن بر اشاره‌گرها یا شاخص‌های وابسته به ابتدا و انتهای داده این است که در صورتی که بافر کاملاً پر باشد، هر دو اشاره‌گر به یک عنصر اشاره می‌کنند: 250px این دقیقاً همان وضعیتی است وقتی که بافر خالی باشد: 250px برای حل این سردرگمی چندین راه حل وجود دارد: همیشه یک شکاف را باز نگه دارید. باز نگه داشتن همیشگی یک شکاف این طرح همواره یک شکاف را تخصیص نیافته باقی می‌گذارد. اگر اشاره‌گر انتهایی (write) اشاره کند به شکاف ماقبل شکافی که اشاره‌گر ابتدایی (read) به آن اشاره می‌کرد، بافر پر است. معایب آن: یک شکاف از دست می‌رود، بنابراین این یک سازش بد است وقتی که اندازه بافر کوچک باشد یا شکاف بزرگ باشد یا در سخت‌افزار پیاده‌سازی شده باشد. | ## بخش 2: بافر چرخشی | بهره‌گیری از شمارنده پر شدن این روش اشاره‌گر انتهایی را با یک شمارنده که تعداد آیتم‌های قابل خواندن در بافر را نگه می‌دارد، جایگزین می‌کند. این بدون هیچ ابهامی جواب می‌دهد زمانی که بافر پر یا خالی باشد و اجازه استفاده کامل از شکاف‌ها را می‌دهد. تأثیر بر روی کارایی باید ناچیز باشد، از آنجایی که درست است این روش هزینه‌های نگهداری شمارنده و محاسبه شکاف انتها را بر روی write اضافه می‌کند ولی احتیاج به نگهداری اشاره‌گر انتهایی را حذف می‌کند و آزمون پر بودن را ساده می‌کند. مزیت آن: آزمون پر/خالی بودن آن ساده است معایب آن: شما به عملگر باقی‌مانده (ماژولو) برای خواندن و نوشتن نیاز دارید عملیات خواندن و نوشتن باید پهنه شمارنده را به اشتراک بگذارند، بنابراین به همگام سازی در وضعیت پردازش چند هسته‌ای نیاز دارد. نکته: وقتی از نشان‌بر در مدل تولیدکننده-مصرف‌کننده، استفاده می‌شود نشان بر به عنوان شمارنده پر شدن عمل می‌کند. معکوس سازی یک راه حل دیگر این است که تعداد دفعات بسته شدن هر اشاره‌گر خواندن و نوشتن را به خاطر بسپاریم و با مقایسه آن وضعیت پر یا خالی را تمایز دهیم. در واقع تنها زوج بودن عدد تعداد بسته شدن‌ها نیاز است، بنابراین کافیست که یک بیت اضافه نگه داریم. می‌توانید این را ببینید مثل این که بافر یک آینه محاری اضافه می‌کند و اشاره‌گرها یا به بافر نرمال یا به بافر معکوس در آینه اشاره می‌کنند: 500px به بالا نگاه کنید. نیازی به عملگر ماژولو (یا باقیمانده) نیست چشمه و چاهک داده می‌توانند سیاست‌های مستقلی از هم برای تعامل با یک بافر پر و سرریز پیاده‌سازی کنند درحالیکه قانونی را که تنها چشمه داده تعداد نوشتن و چاهک داده تعداد خواندن را تغییر می‌دهد، رعایت می‌کند. این می‌تواند منتهی به یک پیاده‌سازی ظریف و قدرتمند یک بافر حلقوی حتی در محیط پردازش چند هسته‌ای شود.[نیازمند استناد] معایب آن: شما به یک بیت اضافه برای اشاره‌گر read و write نیاز دارید شمارنده‌های خواندن/نوشتن یک راه حل دیگر این است که تعداد آیتم‌های نوشته شده بر و خوانده شده از بافر حلقوی است. هردو شمارش ذخیره می‌شوند در یک متغیر صحیح علامت دار (مثبت و منفی) با محدودیت عددی بزرگتر از تعداد آیتم‌هایی که می‌توانند ذخیره شوند و مجازند آزادانه بسته شوند (به اشاره‌گر). این می‌تواند بیانگر این باشد که بافر خالی است، نیمه پر است یا کاملاً پر است (بدون هدر دادن یک فضای ذخیره‌سازی) یا در حالت سرریزی. مزیت آن: چشمه و چاهک داده می‌توانند سیاست‌های مستقلی از هم برای تعامل با یک بافر پر و سرریز پیاده‌سازی کنند درحالیکه قانونی را که تنها چشمه داده تعداد نوشتن و چاهک داده تعداد خواندن را تغییر می‌دهد، رعایت می‌کند. این می‌تواند منتهی به یک پیاده‌سازی ظریف و قدرتمند یک بافر حلقوی حتی در محیط پردازش چند هسته‌ای شود. | ## بخش 3: بافر چرخشی | عیب آن: شما به دو متغیر اضافه نیاز دارید شاخص‌های مطلق این ممکن است که با استفاده از شاخص‌ها (index) به جای اشاره‌گرها راه حل قبلی را ارتقاء داد: شاخص‌ها می‌توانند تعداد خواندن/نوشتن‌ها را به حای ذخیره در حاشیه شروع بافر، در متغیرهای جداگانه‌ای مانند بالا ذخیره کنند که اکنون پاک می‌شوند و شاخص‌های وابسته در پرواز به دست می‌آید که با تقسیم عملیات پیمانه بر روی طول بافر بدست می‌آید. اگر شمارش بسته‌بندی ممکن باشد، منطق پیچیده‌ای می‌تواند نیاز شود اگر طول بافر مقسوم علیه ظرفیت شمارنده نباشد. در کامپیوترهای دودویی هر دو عیب ظاهر می‌شوند اگر طول بافر توانی از دو باشد ضبط آخرین عملیات یک راه حل دیگر این است که یک flag نگه داریم که نشانگر اینگه آخرین عملیات read بوده یا write. مزایای آن: تنها یک بیت واحد نیاز است که ذخیره شود (که می‌تواند مخصوصاً زمانی که الگوریتم به شکل سخت‌افزاری پیاده می‌شود مفید باشد) آزمون پر/خالی بودن ساده است عیب آن: شما به یک متغیر اضافه نیاز دارید عملیات]واندن و نوشتن باید flag را به اشتراک بگذارند، پس احتمالاً به یک همگام سازی در پردازش چند هسته‌ای نیاز می‌شود. تقسیم بافر به دو ناحیه این روش مشکل دور تا دوری (wrap-around) را حل می‌کند به وسیله تکه کردن بافر به یک بخش اولیه و یک بخش ثانویه. بخش ثانویه همیشه از ابتدای بافر شروع می‌شود و فعال نمی‌شود تا وقتی که بخش اولیه به انتهای بافر رسیده باشد. علاوه بر این اگر بخش اولیه از داده خالی باشد، بخش ثانویه تبدیل به بخش اولیه جدید می‌شود. چندین اشاره‌گر خواندن مقداری پیچیده‌تر وجود چندین اشاره‌گر خواندن روی یک بافر حلقوی است. این هنگامی مفید است که n ریسمان دارید که از یک بافر می‌خوانند، اما یک ریسمان روی بافر می‌نویسد. نویسنده نه تنها عناصر را بر روی بافر می‌نویسد بلکه آن عناصر را به قطعات نسبت می‌دهد.[نیازمند استناد] خواننده نه تنها باید بتواند از بافر بخواند بلکه باید از مرزهای قطعات اطلاع کسب کند. مثال: نویسنده اطلاعاتی را از فایل‌های کوچک می‌خواند و بر روی یک بافر یکسان ذخیره می‌کند. خواننده داده را می‌خواند، ولی نیاز دارد بداند کی و کدام فایل از موقعیت داده شده شروع می‌شوند. انواع شاید رایج‌ترین نسخه بافر حلقوی از بایت‌های ۸-بیتی به عنوان عنصر استفاده می‌کنند. بعضی از پیاده‌سازی‌های بافر حلقوی از عناصر با اندازه ثابت که بزرگتر از بایت‌های ۸-بیتی اند استفاده می‌کنند — ۱۶-بیتی‌های صحیح برای بافرهای صوتی، سلول‌های ۵۳-بایتی ATM برای بافرهای مخابراتی و.. | ## جمع‌بندی | هرکدام پیوسته است و ترتیب داده صحیحی دارد، پس خواندن و نوشتن نرم‌افزاری این مقادیر می‌تواند سریع نر از نرم‌افزاری باشد که با مقادیر نامرتب و ناپیوسته سر و کار دارد.