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

في علوم الحاسوب ، تُعدّ ذاكرة المعاملات البرمجية ( STM ) آليةً للتحكم في التزامن ، تُشابه معاملات قواعد البيانات ، للتحكم في الوصول إلى الذاكرة المشتركة في الحوسبة المتزامنة . وهي بديلٌ للتزامن القائم على الأقفال . تُنفَّذ ذاكرة المعاملات البرمجية برمجياً، لا كمكوّن مادي. تحدث المعاملة في هذا السياق عندما يُنفِّذ جزءٌ من التعليمات البرمجية سلسلةً من عمليات القراءة والكتابة إلى الذاكرة المشتركة. تحدث هذه العمليات منطقياً في لحظةٍ زمنيةٍ واحدة؛ ولا تكون الحالات الوسيطة مرئيةً للمعاملات الأخرى (الناجحة). نشأت فكرة توفير دعمٍ مادي للمعاملات في ورقةٍ بحثيةٍ نُشرت عام 1986 من قِبَل توم نايت . ^{[ 1 ]} وقد شاع استخدام هذه الفكرة على يد موريس هيرليهي وج . إليوت ب. موس . ^{[ 2 ]} وفي عام 1995، وسّع نير شافيت ودان تويتو هذه الفكرة لتشمل ذاكرة المعاملات البرمجية فقط (STM). ^{[ 3 ]} منذ عام 2005، أصبح STM محورًا لبحوث مكثفة ^{[ 4 ]} ويتزايد الدعم للتطبيقات العملية.

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

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

مع ذلك، عمليًا، تعاني أنظمة إدارة الذاكرة قصيرة المدى (STM) من انخفاض في الأداء مقارنةً بالأنظمة الدقيقة القائمة على الأقفال، وذلك على عدد قليل من المعالجات (من 1 إلى 4 حسب التطبيق). ويعود ذلك أساسًا إلى العبء الإضافي المرتبط بصيانة سجل المعاملات والوقت المستغرق في إتمامها. وحتى في هذه الحالة، لا يكون الأداء عادةً أسوأ من ضعف الأداء في الأنظمة الأخرى. ^{[ 5 ]} ويرى مؤيدو أنظمة إدارة الذاكرة قصيرة المدى أن هذا الانخفاض في الأداء مبررٌ بالمزايا النظرية لهذه الأنظمة.

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

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

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

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

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

في عام 2005، وصف كلٌ من تيم هاريس، وسيمون مارلو ، وسيمون بيتون جونز ، وموريس هيرليهي نظام STM مبنيًا على لغة Concurrent Haskell، والذي يُمكّن من دمج العمليات الذرية العشوائية في عمليات ذرية أكبر، وهو مفهوم مفيد كان مستحيلاً مع البرمجة القائمة على الأقفال. ونقتبس من المؤلفين:

لعلّ الاعتراض الأساسي [...] هو أن البرامج القائمة على الأقفال لا يمكن دمجها : فقد تفشل الأجزاء الصحيحة عند دمجها. على سبيل المثال، لنفترض وجود جدول تجزئة يحتوي على عمليات إدراج وحذف آمنة للخيوط. الآن، لنفترض أننا نريد حذف عنصر واحد A من الجدول t1، وإدراجه في الجدول t2؛ ولكن يجب ألا تكون الحالة الوسيطة (التي لا يحتوي فيها أي من الجدولين على العنصر) مرئية للخيوط الأخرى. ما لم يتوقع مُنفِّذ جدول التجزئة هذه الحاجة، فلا توجد ببساطة طريقة لتلبية هذا الشرط. [...] باختصار، لا يمكن دمج العمليات الصحيحة بشكل فردي (الإدراج، الحذف) في عمليات صحيحة أكبر. — تيم هاريس وآخرون، "معاملات الذاكرة القابلة للتركيب"، القسم 2: الخلفية، صفحة 2 ^{[ 6 ]}

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

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

تم تطبيق هذا المخطط في مترجم لغة هاسكل غلاسكو .

تُمكّن البساطة المفاهيمية لـ STMs من عرضها للمبرمج باستخدام بنية لغوية بسيطة نسبيًا . وقد اقترح تيم هاريس وكير فريزر في بحثهما "دعم اللغة للمعاملات الخفيفة" فكرة استخدام المنطقة الحرجة الشرطية الكلاسيكية (CCR) لتمثيل المعاملات. في أبسط صورها، تُعدّ هذه المنطقة مجرد "كتلة ذرية"، وهي كتلة من التعليمات البرمجية التي تحدث منطقيًا في لحظة واحدة.

// إدراج عقدة في قائمة مرتبطة ثنائياً بشكل ذري newNode->prev = node; newNode->next = node->next; node->next->prev = newNode; node->next = newNode; }

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

تسمح شروط التحكم المركزية أيضًا بشرط الحماية ، الذي يمكّن المعاملة من الانتظار حتى يكون لديها عمل تقوم به:

atomic (queueSize > 0) { قم بإزالة العنصر من قائمة الانتظار واستخدمه }

إذا لم يتحقق الشرط، ينتظر مدير المعاملات حتى تُجري معاملة أخرى عملية تثبيت تؤثر على الشرط قبل إعادة المحاولة. يُعزز هذا الترابط المرن بين المنتجين والمستهلكين نمطية المعالجة مقارنةً بالإشارات الصريحة بين الخيوط. وقد طوّرت "معاملات الذاكرة القابلة للتركيب" ^{[ 6 ]} هذا المفهوم خطوةً أخرى من خلال أمر إعادة المحاولة (المذكور أعلاه)، والذي يُمكنه، في أي وقت، إيقاف المعاملة والانتظار حتى يتم تعديل قيمة قرأتها المعاملة سابقًا قبل إعادة المحاولة. على سبيل المثال:

ذري { إذا كان حجم قائمة الانتظار أكبر من صفر { قم بإزالة العنصر من قائمة الانتظار واستخدمه } آخر { إعادة المحاولة } }

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

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

يمكن تنفيذ STM كخوارزمية بدون تأمين أو باستخدام التأمين. ^{[ 7 ]} يوجد نوعان من أنظمة التأمين: في تأمين وقت المواجهة (Ennals وSaha وHarris)، تتم كتابة البيانات في الذاكرة عن طريق الحصول مؤقتًا على تأمين لموقع معين، ثم كتابة القيمة مباشرةً، وتسجيلها في سجل التراجع. أما تأمين وقت الالتزام، فيقوم بتأمين مواقع الذاكرة فقط خلال مرحلة الالتزام.

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

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

ذري { إذا كان (س ≠ ص) بينما (صحيح) { } }

ذري { x++; y++; }

بافتراض أن x = y مبدئيًا، فإن أيًا من العمليتين السابقتين لا تُغير هذا الثابت، ولكن من الممكن أن تقرأ العملية A قيمة x بعد تحديثها بواسطة العملية B، ثم تقرأ قيمة y قبل تحديثها بواسطة العملية B، مما يؤدي إلى دخولها في حلقة لا نهائية. تتمثل الاستراتيجية المعتادة للتعامل مع هذه المشكلة في اعتراض أي استثناءات خطيرة وإلغاء أي عملية غير صالحة.

إحدى طرق التعامل مع هذه المشكلات هي اكتشاف المعاملات التي تنفذ عمليات غير قانونية أو تفشل في الإنهاء وإلغائها بشكل نظيف؛ وهناك نهج آخر يتمثل في نظام قفل المعاملات .

• هاسكل جي إتش سي ^{[ 8 ]}
• C++ cpp_stm_free ^{[ 9 ]}
• تم نقل مراجع Clojure ، ^{[ 10 ]} إلى node-stm ^{[ 11 ]}
• اذهبوا إلى كشمير ^{[ 12 ]}
• Rust async-stm ^{[ 13 ]}
• سكالا زيو ^{[ 14 ]}
• OCaml Kcas ^{[ 15 ]}
• Kotlin arrow-fx-stm ^{[ 16 ]}