قائمة انتظار مؤشر ترابط متعددة الكبار في ج

Question

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

أحتاج الأشياء التالية:

• الإدراج الفعال والإزالة. أفترض أنه مثل أي قائمة انتظار أخرى O (1) من الممكن أن يكون هناك enqueueing و dequeueing.
• الذاكرة المخصصة ديناميكيا ، أي بنية مرتبطة. أحتاج إلى عدم امتلاك حد تعسفي لحجم قائمة الانتظار ، لذا فإن الصفيف ليس هو ما أبحث عنه.

تعديل: لا ينبغي أن تدور مؤشرات الترابط في قائمة انتظار فارغة ، حيث من المحتمل أن تكون هناك دقائق من الوقت مع عدم وجود كتابة ، مع رشقات قصيرة من أعداد كبيرة من الكتابة.

Answer 1

بالتأكيد ، هناك قوائم قوائم قفل. بناءً على ما قلته في التعليقات ، على الرغم من ذلك ، فإن الأداء هنا ليس حرجًا على الإطلاق ، نظرًا لأنك تقوم بإنشاء موضوع لكل كتابة على أي حال.

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

write:
    lock the mutex
    (optionally - check the cancel flag to prevent leaks of stuff on the list)
    add the event to the list
    signal the condition variable
    unlock the mutex

read:
   lock the mutex
   while (list is empty AND cancel is false):
       wait on the condition variable with the mutex
   if cancel is false:  // or "if list non-empty", depending on cancel semantics
       remove an event from the list
   unlock the mutex
   return event if we have one, else NULL meaning "cancelled"

cancel:
   lock the mutex
   set the cancel flag
   (optionally - dispose of anything on the list, since the reader will quit)
   signal the condition variable
   unlock the mutex

إذا كنت تستخدم قائمة بها عقد خارجية ، فقد ترغب في تخصيص الذاكرة خارج قفل Mutex ، فقط لتقليل الوقت الذي تمسك به. ولكن إذا قمت بتصميم الأحداث مع عقدة قائمة تدخلية ربما تكون أسهل.

تحرير: يمكنك أيضًا دعم العديد من القراء (مع عدم وجود ضمانات محمولة يحصل عليها المرء حدثًا معينًا) إذا قمت بتغيير "الإشارة" إلى "البث". على الرغم من أنك لا تحتاج إليها ، إلا أنها لا تكلف أي شيء أيضًا.

Answer 2

إذا لم تكن بحاجة إلى قائمة انتظار مجانية قفل ، فيمكنك فقط اختتام قائمة انتظار موجودة مع قفل.

Mutex myQueueLock;
Queue myQueue; 
void mtQueuePush(int value)
{
    lock(myQueueLock);
    queuePush(myQueue, value);
    unlock(myQueueLock);
}
int mtQueueNext()
{
    lock(myQueueLock);
    int value = queueFront(myQueue);
    queuePop(myQueue);
    unlock(myQueueLock);
    return value;
}

الشيء الوحيد بعد ذلك هو إضافة نوع من الاهتمام لـ mtqueuenext عندما تكون قائمة الانتظار فارغة.

تحرير: إذا كان لديك قارئ واحد ، كاتب واحد في قائمة الانتظار بدون قفل ، فأنت بحاجة فقط إلى قفل حول mtqueuepush ، لمنع العديد من الكتاب المتزامنين.

هناك طوور قارئ/كاتب واحد من القارئ ، يتم تنفيذ معظمها كطبقات قالب C ++. ومع ذلك ، قم بإجراء بحث Google وإذا لزم الأمر

Answer 3

http://www.liblfds.org

مكتبة بنية البيانات الخالية من القفل مكتوبة في C.

لديه قائمة انتظار M&S.

Answer 4

سأذهب لقوائم قائمة واحدة كاتبة واحدة (موضوع واحد لكل كاتب). ثم يمكنك التحقق هذه لكيفية الحصول على القارئ الوحيد لقراءة قوائم الانتظار المختلفة.