مخزن دائري

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

#تضمين <stdio.h> 

enum { N = 10 }; // حجم المخزن المؤقت الدائري       

int buffer [ N ]; // ملاحظة: يمكن تخزين (N - 1) عناصر فقط في وقت معين int writeIndx = 0 ; int readIndx = 0 ;   
   
    

int put ( int item ) { if (( writeIndx + 1 ) % N == readIndx ) { // المخزن المؤقت ممتلئ، تجنب التجاوز return 0 ; } buffer [ writeIndx ] = item ; writeIndx = ( writeIndx + 1 ) % N ; return 1 ; }    

         
  
     
      
  
    
        
   


int get ( int * value ) { if ( readIndx == writeIndx ) { // المخزن المؤقت فارغ return 0 ; }     

     
  
     
      
  

  * القيمة = المخزن المؤقت [ readIndx ]؛ readIndx = ( readIndx + 1 ) % N ؛ إرجاع 1 ؛ }  
        
   


int main () { // اختبار المخزن المؤقت الدائري int value = 1001 ; while ( put ( value ++ )); while ( get ( & value )) printf ( "read %d \n " , value ); return 0 ; }  

  
     
     
     
       
   

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

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

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

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

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

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

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

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

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

• CB في نواة لينكس
• CB في DSP
• قائمة الانتظار الدائرية في لغة سي Archived 2018-10-29 at the Wayback Machine

Original text

Rate this translation

Your feedback will be used to help improve Google Translate