مرجع
آخر الزيارات

لغة التحقق الرسمية من أنظمة البرمجيات

3٬384 كلمة•0 مشاهدة•🗒️ منذ 3 أيام
باختصار: TLA + هي لغة مواصفات رسمية طورها Leslie Lamport . في هذه المقالة 32 قسماً: «التواصل بشأن العمليات المتسلسلة»، «[Key -> Val ∪ {NoVal}]» و«/\ missed[t] = {}» وغيرها.
المحتويات
  1. التواصل بشأن العمليات المتسلسلة
  2. [Key -> Val ∪ {NoVal}]
  3. /\ missed[t] = {}
  4. /\ tx' = tx \ {t}
  5. تاريخ
  6. /\ UNCHANGED
  7. الوحدات القياسية
  8. أمان
  9. /\ snapshotStore[t][k] \notin {NoVal, v}
  10. السلوك – سلسلة من الحالات
  11. فاحص النموذج
  12. Init == clock \in {0, 1}
  13. بيئة تطوير متكاملة
  14. /\ t \in tx
  15. CHOOSE v : v \notin Val
  16. نظام الإثبات
  17. /\ tx' = tx \ {t}
  18. /\ UNCHANGED
  19. Init /\ [][Next]_
  20. هياكل البيانات
  21. الحيوية
  22. /\ snapshotStore[t][k] /= NoVal
  23. /\ UNCHANGED store
  24. المشغلين
  25. TxLifecycle
  26. استخدام الصناعة
  27. /\ tx' = tx ∪ {t}
  28. الأمثلة
  29. /\ UNCHANGED
  30. اللغة
  31. /\ UNCHANGED
  32. /\ snapshotStore[t][k] = NoVal

على سبيل التعريف، TLA + هي لغة مواصفات رسمية طورها Leslie Lamport . تُستعمل لتصميم ونمذجة وتوثيق والتحقق من البرامج، خاصة الأنظمة المتزامنة والأنظمة المُوزعة . يُعتبر TLA + شيفرة زائفة قابلة للاختبار بشكل شامل، ويُشبه استخدامه برسم المخططات لأنظمة البرمجيات؛ TLA هو اختصار لـ Temporal Logic of Actions .في مجال التصميم والتوثيق، تؤدي لغة TLA + نفس دور المواصفات الفنية غير الرسمية.ومع ذلك، تُكتب مواصفات TLA +بلغة رسمية قائمة على المنطق والرياضيات، وتهدف دقة المواصفات المكتوبة بهذه اللغة إلى الكشف عن عيوب التصميم قبل البدء في تنفيذ النظام. ونتناول فيما يلي مزيدًا من التفاصيل.

وفي السياق ذاته، تم تقديم لغة TLA + في عام 1999، بعد عدة عقود من البحث في طرق التحقق من صحة الأنظمة المتزامنة. ومُنذ ذلك الحين، تَم تطوير مجموعة أدوات متكاملة تشمل بيئة تطوير متكاملة IDE ومدقق النموذج الموزع.في سنة 2009، تم إنشاء لغة البرمجة الشبيهة بالرمز PlusCal، وهي تنتقل إلى TLA + وهي مفيدة لتحديد الخوارزميات المتسلسلة. تم الإعلان عن TLA +2 في عام 2014، مما أدى إلى توسيع دعم اللغة لبناءات الإثبات. المرجع الحالي لـ TLA + هو The TLA + Hyperbook من تأليف Leslie Lamport.

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

التواصل بشأن العمليات المتسلسلة

  • سبيكة (لغة المواصفات)
  • الطريقة ب
  • منطق شجرة الحساب
  • بلس كال
  • المنطق الزمني
  • المنطق الزمني للأفعال
  • تدوين Z

[Key -> Val ∪ {NoVal}]

  • Init == \* The initial predicate.
  • /\ tx = {} \* The set of open transactions is initially empty.
  • /\ snapshotStore = \* All snapshotStore values are initially NoVal.
  • [t \in TxId |-> [k \in Key |-> NoVal
  • TypeInvariant == \* The type invariant.
  • /\ store \in Store
  • /\ tx \subseteq TxId
  • /\ snapshotStore \in [TxId -> Store]
  • /\ written \in [TxId -> SUBSET Key]
  • /\ missed \in [TxId -> SUBSET Key]

/\ missed[t] = {}

OpenTx(t) == \* Open a new transaction.

/\ t \notin tx

/\ tx' = tx \ {t}

/\ written' = [written EXCEPT ![t] = {}]

/\ missed' = [missed EXCEPT ![t] = {}]

تاريخ

وعلى صعيد آخر، تم تطوير المنطق الزمني الحديث بواسطةآرثر براير في سنة 1957، وكان يُعرف آنذاك بمنطق الزمن.

وفي هذا السياق، لامبورت يعمل في الوقت الحالي على إعداد مرجع محدّث للغة تحت عنوان TLA + "The TLA + Hyperbook". وهو عمل غير مكتمل متاح على موقعه الرسمي. كما يقوم Lamport كذلك بإنشاء دورة فيديو TLA + ، والتي تم وصفها فيها بأنها "عمل قيد التقدم يتكون من بداية سلسلة من محاضرات الفيديو لتعليم المبرمجين ومهندسي البرمجيات كيفية كتابة مواصفات TLA + بأنفسهم".

علاوةً على ذلك، وعلى الرغم من أن أمير بنويلي كان أول من درس بجدية تطبيقات المنطق الزمني في علوم الحاسوب ، فقد تكهن براير باستخدامه قبل ذلك بعقد كامل في عام 1967:

وفي هذا السياق، بحسب الامبورت، "كنتُ متأكدًا أن منطق الزمن مجرد هراء نظري لا يمكن أن تكون له أي تطبيقات عملية، لكنه بدا ممتعًا، فحضرتُ."

وعلى صعيد آخر، تتكوَّن مواصفات TLA في الغالب من رياضيات غير زمنية، وهو ما وجده لامبورت أقل تعقيدًا من المواصفات الزمنية البحتة. وقد وفَّر TLA أساسًا رياضيًا للغة المواصفات TLA + ، التي قُدِمت في الورقة البحثية "تحديد الأنظمة المتزامنة باستخدام TLA + " في عام 1999. وفي نفس العام، كتب يوان يو أداة التحقق النموذجي TLC الخاصة بمواصفات TLA + ؛ وقد استُخدامت TLC لاكتشاف أخطاء في بروتوكول تماسك ذاكرة المخبئية في معالج متعدد الأنوية تابع لشركة من Compaq .

ومن جهة أخرى، استمر العمل طوال ثمانينيات القرن العشرين، وبدأ لامبورت في نشر أوراقه البحثية حول المنطق الزمني للأفعال في سنة 1990؛ ومع ذلك، لم يتم تقديمه رسميًا حتى نشر "المنطق الزمني للأفعال" في عام 1994. لقد مكّن TLA من استخدام الإجراءات في الصيغ الزمنية، والتي بحسب ـ Lamport "توفر طريقة أنيقة لتنظيم وتنظيم كل الاستدلالات المستعملة في التحقق المتزامن من النظام."

في هذا الإطار، اطّلع لامبورت لأول مرة على منطق الزمن الخطي (LTL) الخاص بـ Pnueli أثناء ندوة في جامعة ستانفورد عام 1978 نظمتها سوزان أويكي .

من جانب آخر، نشر لامبورت كتابًا دراسيًا شاملًا حول TLA + في عام 2002، بعنوان "تحديد الأنظمة: لغة وأدوات TLA + لمهندسي البرمجيات". في سنة 2009، قدّم لغة PlusCal وتليها أداة إثبات المعروفة باسم TLA + proof (TLAPS) في عام 2012. تم الإعلان عن TLA +2 في عام 2014، حيث أضاف بعض التراكيب اللغوية الإضافية فضلًا عن زيادة الدعم داخل اللغة لنظام الإثبات بدرجة كبيرة.

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

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

ومن جهة أخرى، أثمر بحث لامبورت عن طريقة عملية لكتابة المواصفات عن ورقته البحثية عام 1983 بعنوان "تحديد وحدات البرمجة المتزامنة"، والتي قدّمت فكرة وصف تحولات الحالة على أنها دوال منطقية تعتمد على المتغيرات الأولية وغير الأولية.

ومن ناحية أخرى، أجرى بنويلي أبحاثًا حول استخدام المنطق الزمني في توصيف البرامج الحاسوبية، وقدم المنطق الزمني الخطي في عام 1977. أصبحت LTL أداة مهمة لتحليل البرامج المتزامنة، حيث تعبر بسهولة عن خصائص مثل الاستبعاد المتبادل والتحرر من الجمود .

من جانب آخر، في عام 1975،قدّم إد أشكروفت مفهوم "الثبات" في ورقته البحثية، بعنوان "إثبات العبارات حول البرامج المتوازية"، وهو المفهوم الذي استعمله لامبورت لتعميم طريقة فلويد في ورقته البحثية عام 1977 بعنوان "إثبات صحة برامج العمليات المتعددة". قدمت ورقة لامبورت كذلك السلامة والحيوية كتعميمات للصحة الجزئية والإنهاء على التوالي. تم استخدام هذه الطريقة للتحقق من أول خوارزمية لجمع القمامة المتزامنة في ورقة بحثية عام 1978 مع إدجر ديكسترا .

/\ UNCHANGED

ومن جهة أخرى، Add(t, k, v) == \* Using transaction t, add value v to the store under key k.

/\ t \in tx

الوحدات القياسية

ومن ناحية أخرى، الحقائب : وحدة للعمل مع مجموعات متعددة . يوفر نظائر تشغيل المجموعة البدائية والعد المكرر.

في هذا الإطار، FiniteSets : وحدة للعمل مع المجموعات المحدودة . يوفر مشغلي IsFiniteSet(S) و Cardinality(S) .

وفي هذا السياق، يتم استيراد الوحدات القياسية في TLA+ باستخدام عبارتي EXTENDS أو INSTANCE .

وفي هذا الصدد، تمتلك TLA + مجموعة من الوحدات القياسية التي تحتوي على المعاملات الشائعة. يتم توزيع هذه الوحدات من محلل الصياغة. ويستعمل مدقق النماذج TLC نسخًا مُنفذة بلغة Java لتحسين الأداء.

ومن جهة أخرى، الأعداد الطبيعية : تحدد الأعداد الطبيعية إلى جانب المتباينات والعمليات الحسابية.

من جانب آخر، TLC : توفر وظائف مفيدة للمواصفات التي تم فحصها بواسطة النموذج، مثل التسجيل والتأكيدات.

من جهة ثانية، التسلسلات : تحدد المشغلات على الثنائيات مثل Len(S) ، و Head(S) ، و Tail(S) ، و Append(S, E) ، و concatenation ، و filter .

الأدوات

  • الأعداد الصحيحة : تُعرَّف الأعداد الصحيحة .
  • الأعداد الحقيقية : تحدد الأعداد الحقيقية إلى جانب القسمة واللانهاية .
  • الوقت الحقيقي : يوفر تعريفات مفيدة في مواصفات النظام في الوقت الحقيقي .

أمان

في هذا الإطار، تهتم TLA + بتعريف مجموعة جميع السلوكيات الصحيحة للنظام. مثلًا، يمكن تحديد ساعة ذات بت واحد تدق بلا نهاية بين 0 و1 على النحو التالي:الساعة المتغيرة

/\ snapshotStore[t][k] \notin {NoVal, v}

/\ snapshotStore' = [snapshotStore EXCEPT ![t][k] = v]

/\ written' = [written EXCEPT ![t] = @ ∪ {k}]

السلوك – سلسلة من الحالات

  • الخطوة - زوج من الحالات المتتالية في السلوك
  • خطوة التأتأة - وهي خطوة لا تتغير فيها المتغيرات
  • علاقة الحالة التالية - علاقة تصف كيف يمكن للمتغيرات أن تتغير في أي خطوة
  • دالة الحالة - تعبير يحتوي على متغيرات وثوابت ليست علاقة حالة تالية
  • مسند الحالة – دالة حالة ذات قيمة منطقية
  • ثابت - مسند حالة صحيح في جميع الحالات التي يمكن الوصول إليها
  • الصيغة الزمنية - عبارة تحتوي على عبارات في المنطق الزمني

فاحص النموذج

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

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

Init == clock \in {0, 1}

وفي هذا السياق، 1 -> 0 -> 1 -> 0 -> 1 -> ...خصائص السلامة لساعة البت الواحد - أي مجموعة الحالات النظامية الممكن الوصول إليها - يتم وصفها بشكل مناسب بالمواصفات.

وفي السياق ذاته، المواصفة Spec هي صيغة زمنية تنص على أن جميع سلوكيات ساعة البت الواحد يجب أن تحقق بداية شرط Init وأن كل خطوة إما متطابقة مع Tick أو خطوات متقطعة. ومن بين هذه السلوكيات:0 -> 1 -> 0 -> 1 -> 0 -> ...

وفي هذا السياق، Spec == Init /\ [][Tick]_علاقة الحالة التالية Tick تحدد قيمة clock ′ (قيمة clock في الحالة التالية) إلى 1 إذا كانت clock تساوي 0، و0 إذا كانت clock تساوي 1.

في هذا الإطار، المتغير الشرطي Init يكون صحيحًا إذا كانت قيمة clock إما 0 أو 1.

Tick == IF clock = 0 THEN clock' = 1 ELSE clock' = 0

بيئة تطوير متكاملة

وفي هذا الصدد، بيئة تطوير متكاملة تم تنفيذها على منصة Eclipse . تتضمن محررًا مع تمييز الأخطاء والنحو ، فضلًا عن واجهة رسومية أمامية لعدة أدوات أخرى من TLA + :

  • مترجم LaTeX ، لتوليد مواصفات مطبوعة بشكل جميل .
  • مترجم PlusCal.
  • مدقق نموذج TLC.
  • نظام إثبات TLAPS.
  • يتم توزيع IDE في The TLA Toolbox .

ومن ناحية أخرى، محلل بناء الجملة SANY، الذي يقوم بتحليل المواصفات والتحقق منها بحثًا عن أخطاء بناء الجملة.

/\ t \in tx

  • /\ missed[t] ∩ written[t] = {} \* Detection of write-write conflicts.
  • /\ store' = \* Merge snapshotStore writes into store.
  • [k \in Key |-> IF k \in written[t] THEN snapshotStore[t][k] ELSE store[k

CHOOSE v : v \notin Val

Store == \* The set of all key-value stores.

نظام الإثبات

إضافةً إلى ذلك، نظام إثبات TLAPS لا يدعم في الوقت الحالي الاستدلال بالأعداد الحقيقية، ولا أغلب العمليات الزمنية. عادةً ما لا يستطيع إيزابيل وزينون إثبات التزامات الإثبات الحسابية، مما يتطلب استخدام مثبتات SMT. تم استخدام TLAPS لإثبات صحة Byzantine Paxos ، وهندسة أمان Memoir، ومكونات جدول التجزئة الموزع Pastry ، وخوارزمية إجماع Spire. يتم توزيعه بشكل منفصل عن باقي أدوات TLA + وهو برنامج حر يُوزع تحت ترخيص BSD . وقد وسع TLA +2 إلى حدّ كبير في دعم اللغة لبناءات الإثبات.

من جانب آخر، نظام إثبات TLA +،المعروف بـ TLAPS، يقوم بالتحقق الميكانيكي من البراهين المكتوبة بلغة TLA + . تم تطويره في المركز Microsoft Research - INRIA المشترك لإثبات صحة الخوارزميات المتزامنة والموزعة. لغة الإثبات مصممة لتكون مستقلة عن أي مُثبت نظريات محدد؛ حيثُ تُكتب البراهين بأسلوب تصريحي، وتُحوّل إلى التزامات فردية تُرسل إلى مُثبتات خلفية. المثبتات الخلفية الرئيسية هي Isabelle وZenon، مع الرجوع إلى حلول SMT CVC3 و Yices و Z3 . تتميز أدلة TLAPS بأنها منظمة بشكل هرمي، مما يسهل إعادة الهيكلة وتمكين التطوير غير الخطي: يمكن أن يبدأ العمل في الخطوات اللاحقة قبل التحقق من جميع الخطوات السابقة، ويتم تقسيم الخطوات الصعبة إلى خطوات فرعية أصغر. يعمل TLAPS بشكل جيد مع TLC، حيث يكتشف مدقق النموذج بسرعة الأخطاء الصغيرة قبل بدء التحقق. في المقابل، يمكن لـ TLAPS إثبات خصائص النظام التي تتجاوز قدرات فحص النموذج المحدود.

/\ tx' = tx \ {t}

كذلك، /\ missed' = \* Update the missed writes for other open transactions.

  • /\ written' = [written EXCEPT ![t] = {}]
  • Next == \* The next-state relation.
  • \/ \E t \in TxId : OpenTx(t)
  • \/ \E t \in tx : \E k \in Key : \E v \in Val : Add(t, k, v)
  • \/ \E t \in tx : \E k \in Key : \E v \in Val : Update(t, k, v)
  • \/ \E t \in tx : \E k \in Key : Remove(t, k)
  • \/ \E t \in tx : RollbackTx(t)
  • \/ \E t \in tx : CloseTx(t)
  • Spec == \* Initialize state with Init and transition with Next.

من جهة ثانية، [otherTx \in TxId |-> IF otherTx \in tx' THEN missed[otherTx] ∪ written[t] ELSE {}]

/\ UNCHANGED

إضافةً إلى ذلك، Update(t, k, v) == \* Using transaction t, update the value associated with key k to v.

/\ t \in tx

Init /\ [][Next]_

  • ----------------------------------------------------------------------------
  • THEOREM Spec => [](TypeInvariant /\ TxLifecycle)
  • انظر كذلك

هياكل البيانات

من جهة ثانية، البنية الأساسية للبيانات في TLA + هي المجموعة. تُنشأ المجموعات إما بالتعداد الصريح لعناصرها، أو من مجموعات أخرى باستخدام معاملات، أو بصيغة {x \in S : p} حيث p هو شرط على x ، أو بصيغة {e : x \in S} حيث e دالة على x . المجموعة الفارغة الفريدة تُمثَّل بـ {} .

كذلك، الوظائف في TLA + تُسنِد قيمة لكل عنصر في مجالها، والذي يكون مجموعة. التعبير [S -> T]يمثل مجموعة جميع الدوال التي يكون فيها f[ x ] منتمية إلى T ، لكل x في مجموعة المجال S.

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

وفي السياق ذاته، السجلات هِي نَوُع من الوظائف في TLA + . السجل [name |-> "John", age |-> 35] هو سجل يحتوي على الحقول name وage، ويمكن الوصول إليه باستخدام r.name و r.age .

من جهة ثانية، مثلًا، الدالة في TLA + Double[x \in Nat] == x*2 هي عنصر من المجموعة [Nat -> Nat] وبالتالي فإن العبارة Double \in [Nat -> Nat] هي عبارة صحيحة في TLA + . كما يمكن تعريف الوظائف باستخدام الصيغة [x \in S |-> e] لبعض التعبيرات e ، أو عن طريق تعديل وظيفة موجودة [f EXCEPT ![v 1 ] = v 2 ] .

كذلك، هذا السجل ينتمي إلى مجموعة السجلات المعرفة بالشكل [name : String, age : Nat] .

الحيوية

0 -> 0 -> 0 -> 0 -> 0 -> ...

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

وعلى صعيد آخر، 1 -> 1 -> 1 -> 1 -> 1 -> ...الساعة التي لا تدقّ ليست مفيدة، لذا يجب استبعاد هذه السلوكيات. إحدى الحلول هي تعطيل التوقف، لكن TLA + يشترط أن يكون التوقف ممكنًا دائمًا؛ تمثل خطوة التلعثم تغييرًا في جزء من النظام غير الموصوف في المواصفات، وهي مفيدة للتحسين . ولضمان أن عقارب الساعة يجب أن تدق في النهاية، يتم التأكيد على ضعف العدالة فيما يتعلق بـ Tick :Spec == Init /\ [][Tick]_ /\ WF_(Tick)العدالة الضعيفة بالنسبة لفعل معين تعني أنه إذا كان هذا الفعل ممكنًا بشكل مستمر، فلا بد أن يتم تنفيذه في نهاية المطاف. في حالة الإنصاف الضعيف في علامة التجزئة، يُسمح فقط بعدد محدود من خطوات التلعثم بين العلامات. يُطلق على هذه العبارة المنطقية الزمنية حول تيك اسم تأكيد الحيوية. بشكل عام، يجب أن يكون تأكيد الحيوية مغلقًا آليًا : لا ينبغي أن يقيد مجموعة الحالات التي يمكن الوصول إليها، بل مجموعة السلوكيات الممكنة فقط.

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

/\ snapshotStore[t][k] /= NoVal

/\ written' = [written EXCEPT ![t] = @ ∪ {k}]

/\ snapshotStore' = [snapshotStore EXCEPT ![t][k] = NoVal]

/\ UNCHANGED store

في هذا الإطار، CloseTx(t) == \* Close transaction t, merging writes into store.

المشغلين

تتضمن لغة TLA + ، على الرغم من عدم وجود دعم من الأدوات.

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

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

من جانب آخر، تشمل المشغلات الزمنية الأخرى العدل الضعيف والعادل القوي. إن العدالة الضعيفة WF e ( A ) تعني أنه إذا تم تمكين الإجراء A بشكل مستمر (أي بدون انقطاعات)، فيجب اتخاذه في النهاية. العدالة القوية SF e ( A ) تعني أنه إذا تم تمكين الإجراء A بشكل مستمر (بشكل متكرر، مع أو بدون انقطاعات)، فيجب اتخاذه في النهاية.

من جانب آخر، تعني أن العبارة P صحيحة بشكل متكرر إلى ما لا نهاية، أو أن يعني في النهاية أن P سوف يكون صحيحًا دائمًا.

كذلك، تحتوي لغة TLA + على مُشغلات زمنية مدمجة. تستعمل الصيغ الزمنية الرموز التالية: تعني أن العبارة P صحيحة دائمًا، و تعني أن P صحيح في النهاية. ويمكن دمج هذه المُشغّلات مثل:

TxLifecycle

في هذا الإطار، /\ \A t \in tx : \* If store != snapshot & we haven't written it, we must have missed a write.

وفي هذا السياق، \A k \in Key : (store[k] /= snapshotStore[t][k] /\ k \notin written[t]) => k \in missed[t]

  • /\ \A t \in TxId \ tx : \* Checks transactions are cleaned up after disposal.
  • /\ \A k \in Key : snapshotStore[t][k] = NoVal
  • /\ written[t] = {}

استخدام الصناعة

وفي هذا السياق، في شركة Microsoft ، تَمَ اكتشاف خطأ حرج في وحدة ذاكرة Xbox 360 أثناء عملية كتابة المواصفات باستخدام TLA + . استُخدام TLA + كذلك لكتابة براهين رسمية لصحة Byzantine Paxos ومكونات جدول التجزئة الموزع Pastry .

وعلى صعيد آخر، تستعمل Amazon Web Services تقنية TLA + منذ عام 2011. كشف التحقق من النماذج باستخدام TLA + عن أخطاء في DynamoDB و S3 و EBS ومدير القفل الموزع الداخلي؛ بعض هذه الأخطاء تطلّب تتبع حالة يتضمن 35 خطوة. كما استُخدم التحقق من النماذج للتحقق من صحة تحسينات متقدمة. فضلًا عن ذلك، وُجد أن مواصفات TLA + تحمل قيمة كبيرة كوثائق ومساعدات في التصميم.

ومن جهة أخرى، استعملت شركة Altreonic NV أداة TLA+ للتحقق من نموذج OpenComRTOS .

في هذا الإطار، استعملت Microsoft Azure تقنية TLA + لتصميم Cosmos DB ، وهي قاعدة بيانات موزعة عالميًا تدعم خمسة نماذج مختلفة للاتساق.

/\ tx' = tx ∪ {t}

/\ snapshotStore' = [snapshotStore EXCEPT ![t] = store]

الأمثلة

ومن ناحية أخرى، متجر القيمة الرئيسية مع عزل اللقطة :--------------------------- MODULE KeyValueStore ---------------------------

  • CONSTANTS Key, \* The set of all keys.
  • Val, \* The set of all values.
  • TxId \* The set of all transaction IDs.
  • VARIABLES store, \* A data store mapping keys to values.
  • tx, \* The set of open snapshot transactions.
  • snapshotStore, \* Snapshots of the store for each transaction.
  • written, \* A log of writes performed within each transaction.
  • missed \* The set of writes invisible to each transaction.
  • ----------------------------------------------------------------------------
  • NoVal == \* Choose something to represent the absence of a value.

/\ UNCHANGED

/\ t \in tx

من جانب آخر، RollbackTx(t) == \* Close the transaction without merging writes into store.

اللغة

الحالة - تعيين القيم للمتغيرات

كذلك، تُنظَّم مُواصفات TLA + فِي وحدات. حيث يمكن لكل وحدة النمطية أن تمتد أو تستورد وحدات أخرى لاستخدام وظائفها. على الرغم من أن معيار TLA + محدد في رموز رياضية منسقة، فإن أدوات TLA + الحالية تستعمل تعريفات رموز شبيهة بـ LaTeX في ASCII . يستعمل TLA + الكثير من المصطلحات التي تتطلب التعريف:

/\ UNCHANGED

/\ t \in tx

وفي هذا الصدد، Remove(t, k) == \* Using transaction t, remove key k from the store.

/\ snapshotStore[t][k] = NoVal

/\ written' = [written EXCEPT ![t] = @ ∪ {k}]

/\ snapshotStore' = [snapshotStore EXCEPT ![t][k] = v]

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

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