مخزن مؤقت دائري

في علوم الحاسوب ، يُعرف المخزن المؤقت الدائري ، أو الطابور الدائري ، أو المخزن المؤقت الحلقي ، أو المخزن المؤقت الحلقي، بأنه بنية بيانات تستخدم مخزنًا مؤقتًا واحدًا ثابت الحجم كما لو كان متصلًا من طرف إلى طرف. تُسهّل هذه البنية تخزين تدفقات البيانات مؤقتًا . ^{[ 1 ]} وقد وُجدت تطبيقات مبكرة للمخزن المؤقت الدائري في الأجهزة. ^{[ 2 ] [ 3 ]}

يبدأ المخزن الدائري فارغًا وله طول محدد. يوضح الرسم التخطيطي أدناه مخزنًا مكونًا من 7 عناصر:

افترض أن الرقم 1 مكتوب في مركز مخزن مؤقت دائري (موقع البداية الدقيق غير مهم في المخزن المؤقت الدائري):

ثم افترض أنه تمت إضافة عنصرين آخرين إلى المخزن الدائري - 2 و 3 - واللذان يتم وضعهما بعد العنصر 1:

إذا أُزيل عنصران، فسيتم حذف أقدم قيمتين داخل المخزن الدائري. تستخدم المخازن الدائرية منطق FIFO ( الأول يدخل، الأول يخرج ). في المثال، كان العنصران 1 و2 أول من دخل المخزن الدائري، وهما أول من أُزيل، مما ترك العنصر 3 داخل المخزن. عند إزالة العناصر، ينتقل مؤشر القراءة فقط إلى العنصر التالي. تبقى العناصر المُزالة في المخزن، في انتظار استبدالها بعناصر جديدة.

إذا كان المخزن المؤقت يحتوي على 7 عناصر، فإنه يكون ممتلئًا تمامًا:

من خصائص المخزن المؤقت الدائري أنه عندما يمتلئ ويتم إجراء عملية كتابة لاحقة، فإنه يبدأ في استبدال البيانات الأقدم. في المثال الحالي، تمت إضافة عنصرين آخرين - A و B - وقاما باستبدال العنصرين 3 و 4.

بدلاً من ذلك، يمكن للبرامج التي تدير المخزن المؤقت منع الكتابة فوق البيانات وإرجاع خطأ أو إطلاق استثناء . ويعتمد تحديد ما إذا كانت البيانات ستُكتب فوق البيانات أم لا على دلالات برامج المخزن المؤقت أو التطبيق الذي يستخدم المخزن المؤقت الدائري.

وأخيرًا، إذا تمت إزالة عنصرين الآن، فإن ما سيتم إزالته ليس A وB، بل 5 و6 لأن 5 و6 هما الآن أقدم العناصر، مما ينتج عنه المخزن المؤقت مع:

تتمثل الميزة المفيدة للمخزن الدائري في أنه لا يحتاج إلى إعادة ترتيب عناصره عند استهلاك أحدها. (في حال استخدام مخزن غير دائري، فسيكون من الضروري إزاحة جميع العناصر عند استهلاك أحدها). بعبارة أخرى، يُعد المخزن الدائري مناسبًا تمامًا كمخزن FIFO ( الأول في الأول خارج )، بينما يُعد المخزن القياسي غير الدائري مناسبًا تمامًا كمخزن LIFO ( الأخير في الأول خارج ).

يُعد التخزين المؤقت الدائري استراتيجية تنفيذ جيدة لطابور ذي حجم أقصى ثابت. في حال اعتماد حجم أقصى للطابور، يصبح التخزين المؤقت الدائري خيارًا مثاليًا تمامًا؛ إذ تتم جميع عمليات الطابور في وقت ثابت. مع ذلك، يتطلب توسيع التخزين المؤقت الدائري إزاحة الذاكرة، وهو أمر مكلف نسبيًا. بالنسبة للطوابير التي تتوسع بشكل عشوائي، قد يُفضّل استخدام أسلوب القائمة المتصلة .

في بعض الحالات، يمكن استخدام مخزن مؤقت دائري للكتابة فوق البيانات القديمة، كما هو الحال في الوسائط المتعددة. إذا استُخدم هذا المخزن كمخزن مؤقت محدود في مشكلة المنتج والمستهلك، فمن المستحسن أن يقوم المنتج (مثل مولد الصوت) بالكتابة فوق البيانات القديمة إذا لم يتمكن المستهلك (مثل بطاقة الصوت ) من مواكبة التحديثات مؤقتًا. كذلك، تعتمد خوارزميات ضغط البيانات غير الفاقد للبيانات LZ77 على افتراض أن السلاسل النصية التي تظهر مؤخرًا في تدفق البيانات من المرجح أن تظهر قريبًا في نفس التدفق. وتخزن التطبيقات أحدث البيانات في مخزن مؤقت دائري.

يمكن تنفيذ المخزن المؤقت الدائري باستخدام مؤشر وأربعة أعداد صحيحة: ^{[ 4 ]}

• بدء التخزين المؤقت في الذاكرة
• سعة التخزين المؤقت (الطول)
• "الكتابة إلى" فهرس المخزن المؤقت (النهاية)
• "قراءة من" فهرس المخزن المؤقت (البداية)

تُظهر هذه الصورة مخزنًا مؤقتًا ممتلئًا جزئيًا بطول = 7:

تُظهر هذه الصورة مخزنًا مؤقتًا ممتلئًا بأربعة عناصر (من الرقم 1 إلى الرقم 4) تم استبدالها:

في البداية، يتم ضبط مؤشري النهاية والبداية على الصفر. تقوم عملية الكتابة في المخزن المؤقت الدائري بكتابة عنصر إلى موضع مؤشر النهاية، ثم يتم زيادة مؤشر النهاية إلى موضع المخزن المؤقت التالي. أما عملية القراءة من المخزن المؤقت الدائري فتقرأ عنصرًا من موضع مؤشر البداية، ثم يتم زيادة مؤشر البداية إلى موضع المخزن المؤقت التالي.

لا يكفي مؤشرا البداية والنهاية وحدهما للتمييز بين حالة امتلاء المخزن المؤقت أو فراغه مع استخدام جميع خاناته، ^{[ 5 ]} ولكنهما قد يكونان كافيين إذا كان الحد الأقصى لحجم المخزن المؤقت المستخدم هو الطول - 1. ^{[ 6 ]} في هذه الحالة، يكون المخزن المؤقت فارغًا إذا تساوى مؤشرا البداية والنهاية، وممتلئًا عندما يكون حجمه المستخدم هو الطول - 1. يتمثل حل آخر في استخدام عداد صحيح إضافي يتم زيادته عند عملية الكتابة وإنقاصه عند عملية القراءة. عندئذٍ، يعني التحقق من الفراغ اختبار أن العداد يساوي صفرًا، ويعني التحقق من الامتلاء اختبار أن العداد يساوي الطول. ^{[ 7 ]}

الكود المصدري التالي هو تطبيق بلغة C مع اختبار بسيط. تقوم الدالة put() بوضع عنصر في المخزن المؤقت، بينما تقوم الدالة get() بجلب عنصر منه. وتراعي كلتا الدالتين سعة المخزن المؤقت  .

#include <stdio.h>enum { N = 10 }; // حجم المخزن المؤقت الدائريint buffer [ N ]; // ملاحظة: لا يمكن تخزين سوى (N - 1) عنصرًا في وقت معين int writeIndx = 0 ; int readIndx = 0 ;دالة ` put` تأخذ وسيطين : ` item` و`item` . إذا كان ` readIndx` يساوي `WriteIndx + 1` ، فإن ` readIndx` يساوي ` N` . إذا كان `readIndx` يساوي `N`، فهذا يعني أن المخزن المؤقت ممتلئ، لذا يجب تجنب تجاوز سعته . وإلا ، يتم إرجاع القيمة 0. وإلا ، يتم تعيين `item` إلى `buffer [ writeIndx ]` ، ثم يتم تعيين `writeIndx` إلى ` WriteIndx + 1` ، ثم يتم إرجاع القيمة 1 .int get ( int * value ) { if ( readIndx == writeIndx ) { // المخزن المؤقت فارغ return 0 ; }* القيمة = المخزن المؤقت [ مؤشر القراءة ]؛ مؤشر القراءة = ( مؤشر القراءة + 1 ) % N ؛ إرجاع 1 ؛ }int main () { // اختبار المخزن المؤقت الدائري int value = 1001 ; while ( put ( value ++ )); while ( get ( & value )) printf ( "قراءة %d \n " , value ); return 0 ; }

يمكن تحسين أداء تطبيق المخزن المؤقت الدائري بربط المخزن المؤقت الأساسي بمنطقتين متجاورتين من الذاكرة الافتراضية . ^{[ 8 ]} (وبالطبع، يجب أن يساوي طول المخزن المؤقت الأساسي مضاعفًا لحجم صفحة النظام ). عندئذٍ، يمكن إجراء عمليات القراءة والكتابة من وإلى المخزن المؤقت الدائري بكفاءة أكبر عبر الوصول المباشر إلى الذاكرة؛ أما عمليات الوصول التي تتجاوز نهاية منطقة الذاكرة الافتراضية الأولى، فستعود تلقائيًا إلى بداية المخزن المؤقت الأساسي. وعندما ينتقل موضع القراءة إلى منطقة الذاكرة الافتراضية الثانية، يتم إنقاص كلا الموضعين - القراءة والكتابة - بمقدار طول المخزن المؤقت الأساسي.

ربما يكون الإصدار الأكثر شيوعًا من المخزن المؤقت الدائري هو الذي يستخدم بايتات 8 بت كعناصر.

تستخدم بعض تطبيقات المخزن المؤقت الدائري عناصر ذات طول ثابت أكبر من 8 بت بايت - أعداد صحيحة 16 بت لمخازن الصوت، وخلايا ATM 53 بايت لمخازن الاتصالات، وما إلى ذلك. كل عنصر متجاور وله محاذاة البيانات الصحيحة ، لذلك يمكن أن تكون قراءة البرامج وكتابتها لهذه القيم أسرع من البرامج التي تتعامل مع القيم غير المتجاورة وغير المحاذية.

يمكن اعتبار التخزين المؤقت من نوع بينغ بونغ مخزنًا مؤقتًا دائريًا متخصصًا للغاية يحتوي على عنصرين كبيرين ثابتي الطول بالضبط.

يُشبه المخزن المؤقت ثنائي الأجزاء (bip buffer) المخزن المؤقت الدائري إلى حد كبير، إلا أنه يُعيد دائمًا كتلًا متجاورة ذات أطوال متغيرة. وهذا يُوفر تقريبًا جميع مزايا كفاءة المخزن المؤقت الدائري مع الحفاظ على إمكانية استخدام المخزن المؤقت في واجهات برمجة التطبيقات التي تقبل الكتل المتجاورة فقط . ^{[ 9 ]}

تستخدم المخازن الدائرية المضغوطة ذات الحجم الثابت استراتيجية فهرسة بديلة تعتمد على نظرية الأعداد الأولية للحفاظ على تمثيل مضغوط ذي حجم ثابت لتسلسل البيانات بأكمله. ^{[ 10 ]}

• مخزن البيانات الدائري في مستودع أنماط بورتلاند
• يعزز:

  حاوية مخزن مؤقت دائري مُنمذج : circular_buffer/base.hpp

  قائمة انتظار محدودة متزامنة : sync_bounded_queue.hpp

• CB في نواة لينكس
• CB في DSP
• قائمة انتظار دائرية في لغة C، مؤرشفة بتاريخ 29 أكتوبر 2018 على موقع Wayback Machine.