كيف يمكنك تنفيذ ذاكرة المعاملات البرمجية؟

Question

فيما يتعلق بالتعليمات الذرية الفعلية ذات المستوى المنخفض وأسوار الذاكرة (أفترض أنها مستخدمة)، كيف يمكنك تنفيذ STM؟

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

أيضًا، هل يمكن لـ STM ببساطة اكتشاف "دخل مؤشر ترابط آخر إلى هذه المنطقة أثناء تنفيذ الحساب، وبالتالي فإن الحساب غير صالح" أو هل يمكنه بالفعل اكتشاف ما إذا كانت القيم المضطربة قد تم استخدامها (وبالتالي لحسن الحظ في بعض الأحيان قد يقوم خيطان بتنفيذ نفس القسم الحرج في وقت واحد دون الحاجة إلى التراجع)؟

Answer 1

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

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

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

وحل واحد هو استخدام الإصدارات. في كل مرة يتم تعديل كائن، يتم تحديث رقم الإصدار الخاص به. أثناء تشغيل هذه الصفقة، التحقق من صحة نسخة كل كائن الوصول إليها، ووعندما ترتكب هذه الصفقة، عليك التحقق من أن الكائنات <م> لا تزال صالحة. هذا المصادقة يمكن أن تكون المقارنة صحيحة بسيطة (إذا transaction_start_version >= object_version، والهدف من ذلك هو صالح)، لذلك يمكن القيام به بكفاءة إلى حد ما.

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

وهذا ما يبدو أيضا تشير إلى أن تماما مثل أي حل "قفل" الأخرى التي تريد أن تبقي مقاطع الهامة الخاصة بك صغيرة بقدر الإمكان (لتقليل احتمال حدوث صراع)، هل أنا على حق؟

والمرجح جدا. أعتقد أن بعض التطبيقات قد ذهب مسار افتراض / تتطلب كل شيء أن تكون هذه الصفقة، ولكن نعم، في معظم تطبيقات والمعاملات يتم وضع علامة خصيصا قطع من التعليمات البرمجية، ويعد يعمل معاملة، أكبر فرصة الصراع الذي قد يسبب المعاملات استرجاع.

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

وبالإضافة إلى ذلك، يمكن STM ببساطة كشف "دخل موضوع آخر هذا المجال في حين أن الحساب تم تنفيذ، وبالتالي فإن حساب غير صالح" أو يمكن فعلا اكتشاف ما إذا تم استخدام القيم مضروب (وبالتالي عن طريق الحظ في بعض الأحيان اثنين من المواضيع قد تنفيذ نفس حرجة القسم وقت واحد دون الحاجة إلى التراجع)؟

وهذا الأخير. نضع في اعتبارنا أن هذه الفكرة في TM هي حماية <م> بيانات بدلا من <م> كود .

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

Answer 2

قد يكون من الصعب حقًا قراءة بعض الأوراق، ولكن هناك اثنتين منها واضحة وموجزة للغاية وهي:

قفل المعاملات II، ديف دايس، أوري شاليف، نير شافيت الذي يصف خوارزمية STM "TL2" من حيث أي لغة.

تعؤل:ذاكرة المعاملات البرمجية غير الغازية في جافا، جاي كورلاند، نير شافيت، باسكال فيلبر وهو ما يشرح محول فئة وقت التحميل الذي يحول فئات جافا العادية إلى فئات في الذاكرة تحتوي على رمز ثانوي إضافي للقيام بـ STM.هذا ذو صلة بالسؤال حيث تشرح الورقة كيف يمكن تحويل الكود بدون STM ميكانيكيًا إلى كود يقوم بإجراء STM بأي لغة OO.

يتيح لك إطار عمل Deuce إضافة الخوارزمية الفعلية التي ترغب في استخدامها؛بما في ذلك خوارزمية TL2.نظرًا لأن إطار عمل Deuce هو Java، فإن المناقشة التالية تستخدم مصطلحات Java ولكنها تفترض فقط أنك تكتب بلغة OO.

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

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

إجابة واحدة مختصرة لكيفية عمل TL2 لـ STM هي "مسك الدفاتر" ثم استخدام أقفال الكتابة فقط في وقت الالتزام.اقرأ الورقة للحصول على التفاصيل الدقيقة ولكن مخطط فرشاة اللوحة هو كما يلي.كل خاصية يمكنك استخدامها في الكود الأصلي سيكون لها حرفي getter وsetter.في الكود المحول سيكون هناك أيضًا رقم إصدار للخاصية ورمز إضافي يضاف إلى getter وsetter.تحتاج إلى تسجيل إصدار كل سمة تقرأها ضمن المعاملة باعتبارها المعاملة "مجموعة القراءة".يمكنك القيام بذلك عن طريق مطالبة كل مُحصل بإضافة إصدار السمة التي تمت مشاهدتها إلى قائمة مرتبطة بمؤشر ترابط محلي.تحتاج أيضًا إلى تخزين عمليات الكتابة مؤقتًا كـ "مجموعة الكتابة" في مؤشر ترابط محلي حتى يتم الالتزام.لاحظ أن أساليب getter تحتاج إلى التحقق من قيمة مجموعة الكتابة Threadlocal وإرجاعها لحقل معين إذا كان لديك واحد.بهذه الطريقة ترى كتاباتك غير الملتزم بها في قراءاتك ولكن لن يراها أي موضوع آخر حتى تلتزم.

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

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

يوضح إطار عمل Deuce الموجود في المقالة أعلاه كيفية تغيير جميع حروف الحروف والمحددات الخاصة بك عن طريق حقن كود Java bytecode الجديد في فصولك الدراسية في وقت التحميل.يمكن أن تحتوي اللغات الأخرى على مترجم خاص أو معالج مسبق يقوم بنفس التحويل الميكانيكي للتعليمات البرمجية العادية إلى تعليمات برمجية ممكّنة لـ STM.على وجه التحديد مع Deuce، يمكن أن تحتوي كائنات التعليمات البرمجية المصدر الخاصة بك على أزواج أدوات ضبط بسيطة ولكن الفئات المحولة في وقت التشغيل تحتوي على أدوات ضبط getter التي تقوم بالأعمال الكتابية.

يعد تحويل الكود العادي إلى كود STM (خاصة في وقت التشغيل) أمرًا مثيرًا للاهتمام، ولكن إذا كنت بحاجة إلى كتابة بنية بيانات ممكّنة لـ STM، فلن تحتاج إلى أي صلصة سحرية.بدلاً من ذلك، قم فقط بإنشاء ملف Ref فئة مع أ get() و أ set(x) واجعل كل علاقة بين كائنات بنية البيانات الخاصة بك مكونة من Ref مقابض.في ال get و set من الخاص بك Ref فئة يمكنك القيام بأعمال الكتب Threadlocal.ثم يمكنك تنفيذ إصدار بسيط من "TL2" أو أي خوارزمية أخرى تعمل بشكل جيد مع هياكل البيانات الخاصة بك وتزامن القراءة مقابل الكتابة.

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

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

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

أيضًا ، يمكن أن تكتشف STM ببساطة "تم إدخال مؤشر ترابط آخر في هذه المنطقة أثناء تنفيذ الحساب ، وبالتالي فإن الحساب غير صالح" أو يمكنه اكتشاف ما إذا كان قد تم استخدام القيم المغطاة (وبالتالي الحظ في بعض الأحيان ، قد ينفذ موضوعان نفس القسم الحرج في وقت واحد بدونه بدونه تحتاج لتراجع)؟

نهج TL2 حيث أن كل ما يتعلق بالبيانات المقروءة أو المكتوبة لا يتعلق بالكود الذي يقوم بذلك.إنه ما تحصل عليه وتعيينه وما يهم؛وما إذا كان هناك أي خيط آخر يدوس على أصابع قدميك قبل مسح جميع الكتابات.كل ما هو مطلوب من الكود هو أن يكون لديك begin(), commit() و rollback() في منطق الأعمال لبدء المعاملة وإنهائها وإحباطها.حتى أنه يمكن إنشاء التعليمات البرمجية.باستخدام Java، يمكنك وضع علامة على الأساليب الخاصة بك باستخدام التعليق التوضيحي @Transactional على الأساليب، ثم إنشاء تعليمات برمجية تغلف استدعاءات الأسلوب الخاصة بك في محاولة/التقاط/أخيرًا تقوم بالبدء/الالتزام/التراجع كـ java اصطلاحي.يقوم Deuce بإدخال هذا المنطق في وقت تحميل الفصل.

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

Answer 3

يوصف تنفيذ STM الصورة GHC في القسم ستة من:

المعاملات الذاكرة Composable . تيم هاريس، سيمون مارلو، سيمون بيتون جونز، موريس هرليهي. PPoPP'05: ACM ندوة SIGPLAN على مبادئ وممارسات البرمجة المتوازية، شيكاغو، إلينوي، يونيو 2005

والجزء الخامس من:

الذاكرة المعاملات مع الثوابت البيانات . تيم هاريس، سيمون بيتون-جونز. مارس 2006 TRANSACT '06

Answer 4

وأقترح عليك مشاهدة هذا العرض: HTTP: // شبكة الاتصالات العالمية. infoq.com/presentations/Value-Identity-State-Rich-Hickey

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

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

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

Answer 5

إذا كنت تستخدم .NET Framework،

يمكنك الاطلاع على هذه التجربة

• .NET 4.0 STM.Net
  
• بودكاست .NET على STM.Net: دانا جروف ويوسي ليفانوني Talk STM