هو القفل (الانتظار) مجانا ترتبط على نحو مضاعف قائمة ممكنة؟

Question

والمطلوب في هذه المسألة مع C # العلامة، ولكن إذا كان ذلك ممكنا، ينبغي أن يكون من الممكن في أي لغة.

هل من الممكن لتنفيذ قائمة مرتبطة مضاعف باستخدام عمليات متشابكة لتوفير عدم الانتظار قفل؟ أريد أن أدخل، إضافة وإزالة واضحة من دون انتظار.

Answer 1

وجوجل للبحث بسيطة سوف تكشف العديد من قفل خالية من الأوراق قائمة مرتبطة على نحو مضاعف.

ولكن، لأنها تستند إلى CAS الذرية (قارن والمبادلة).

وأنا لا أعرف كيف الذري العمليات في C # هي، ولكن وفقا لهذا الموقع

http://www.albahari.com/threading/part4.aspx

ويضمن

و# عمليات C فقط لتكون الذري للقراءة والكتابة حقل 32BIT و. لم يذكر CAS.

Answer 2

ونعم من الممكن، وهنا تنفيذ بلدي لمثل STL <لأ href = "https://github.com/Qarterd/Honeycomb/blob/master/src/common/Honey/Thread/LockFree/List.h" يختلط = "نوفولو noreferrer"> للقفل مجاني قائمة مرتبطة مضاعف في C ++.

نموذج التعليمات البرمجية التي يولد المواضيع بشكل عشوائي لأداء مكتب خدمات المشاريع على قائمة

وهذا يتطلب 64 بت مقارنة ومبادلة للعمل دون مشاكل ABA. هذه القائمة ليست ممكنة إلا بسبب مجانا قفل إدارة الذاكرة .

وراجع في المعايير في الصفحة 12 . أداء قائمة جداول خطيا مع عدد من المواضيع مع تزايد الخلاف. خوارزمية تدعم التوازي عن قبضة متصلتين، وذلك يزيد من حجم قائمة الخلاف يمكن أن تقلل.

Answer 3

وهنا هو <وأ href = "http://citeseer.ist.psu.edu/cache/papers/cs/32904/http:zSzzSzwww.cs.chalmers.sezSz~phszSzTechnicalReportszSzSunT04_Deque.pdf/sundell04lockfree.pdf" يختلط = "نوفولو noreferrer"> ورقة حيث discribes لقفل حرة قائمة مرتبطة doublly.

<اقتباس فقرة>   

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

وروس Bencina لديه بعض وصلات جيدة حقا أنا فقط وجدت مع أوراق عديدة للوexcamples شفرة المصدر ل "<لأ href =" http://www.audiomulch.com/~rossb/code/lockfree/ "يختلط =" noreferrer نوفولو "> بعض الملاحظات على خوارزميات قفل خالية وخالية من الانتظار ".

Answer 4

لا أعتقد أن هذا ممكن، منذ كنت الحاجة إلى تعيين مراجع متعددة في طلقة واحدة، وعمليات متشابكة تقتصر في وسعهم.

وعلى سبيل المثال، واتخاذ عملية الإضافة - إذا كنت إدخال العقدة B بين A و C، تحتاج إلى تعيين B-> المقبل، B-> سابق، A-> المقبل، وC-> سابق في واحدة الذري عملية. مشابك لا يمكن معالجة ذلك. الضبط المسبق عناصر B وحتى لا يساعد، لأن موضوع آخر يمكن أن تقرر القيام إدراج بينما كنت تستعد "B".

ويهمني التركيز أكثر على الحصول على تأمين كما غرامة الحبيبات ممكن في هذه الحالة، لا تحاول القضاء عليه.

Answer 5

وقراءة الحاشية - أنها تخطط لسحب ConcurrentLinkedList من 4.0 قبل الإصدار النهائي من VS2010

Answer 6

وكذلك لم تكن قد طلبت بالفعل كيفية القيام بذلك. ولكن بشرط يمكنك القيام CAS الذرية في ج # فمن الممكن تماما.

في الحقيقة أنا فقط العمل من خلال تنفيذ انتظار قائمة حرة مرتبطة بشكل مضاعف في C ++ الآن.

وهنا هو ورقة واصفا إياه. http://www.cse.chalmers.se/~tsigas/papers /Haakan-Thesis.pdf

وعرضا التي قد توفر لك أيضا بعض القرائن. http://www.ida.liu.se/ ~ chrke / دورات / MULTI / الشرائح / قفل Free_DoublyLinkedList.pdf

Answer 7

ومن الممكن أن يكتب قفل خوارزميات مجانية لل<م> جميع هياكل البيانات copyable على معظم أبنية [1]. ولكن من الصعب أن يكتب تلك الكفاءة.

وكتبت في من في قفل خالية من قائمة مرتبطة بشكل مضاعف عن طريق هاكان Sundell وPhilippas Tsigas للحصول على صافي. ملاحظة، أنه لا يدعم PopLeft الذري بسبب هذا المفهوم.

[1]: موريس هرليهي: استحالة والنتائج عالميتها لwait- freesynchronization (1988)

Answer 8

وFWIW، NET 4.0 هو إضافة ConcurrentLinkedList، وthreadsafe قائمة مرتبطة مضاعف في مساحة الاسم System.Collections.Concurrent. يمكنك قراءة الوثائق أو في <ل أ href = "http://blogs.msdn.com/pfxteam/archive/2009/03/04/9457880.aspx" يختلط = "نوفولو noreferrer"> بلوق وظيفة واصفا إياه.

Answer 9

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