التزامن (علوم الحاسوب)

الموسوعة الحرة

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

تحفيز

لا تقتصر الحاجة إلى التزامن على أنظمة المعالجات المتعددة فحسب، بل تشمل جميع أنواع العمليات المتزامنة، حتى في أنظمة المعالج الواحد. فيما يلي بعض الاحتياجات الرئيسية للتزامن:

التفرعات والوصلات : عندما تصل مهمة إلى نقطة تفرع، تُقسّم إلى N مهمة فرعية، تُعالج بدورها بواسطة n مهمة. بعد معالجة كل مهمة فرعية، تنتظر حتى تنتهي جميع المهام الفرعية الأخرى من المعالجة. ثم تُدمج هذه المهام مجددًا وتغادر النظام. لذا، تتطلب البرمجة المتوازية التزامن، حيث تنتظر جميع العمليات المتوازية اكتمال عدة عمليات أخرى.

المنتج والمستهلك: في علاقة المنتج والمستهلك، تعتمد عملية المستهلك على عملية المنتج حتى يتم إنتاج البيانات اللازمة.

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

متطلبات

الشكل 1 : ثلاث عمليات تصل إلى مورد مشترك ( قسم حرج ) في وقت واحد.

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

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

الشكل 2 : عملية الوصول إلى مورد مشترك إذا كان متاحًا، بناءً على تقنية مزامنة معينة.

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

إلى جانب الاستبعاد المتبادل، تتناول عملية التزامن أيضًا ما يلي:

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

التقليل

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

مشاكل

فيما يلي بعض المشكلات الكلاسيكية المتعلقة بالتزامن:

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

التكاليف العامة

يمكن أن تؤثر تكاليف التزامن بشكل كبير على الأداء في بيئات الحوسبة المتوازية ، حيث قد تتكبد عملية دمج البيانات من عمليات متعددة تكاليف أعلى بكثير - غالبًا بمقدار ضعفين أو أكثر - من معالجة البيانات نفسها على خيط واحد، ويعود ذلك أساسًا إلى التكاليف الإضافية لآليات الاتصال والتزامن بين العمليات . [ 4 ] [ 5 ] [ 6 ]

مزامنة الأجهزة

توفر العديد من الأنظمة دعمًا للأجهزة لرمز القسم الحرج .

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

الدعم في لغات البرمجة

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

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

يستخدم إطار عمل .NET أيضًا أدوات التزامن الأساسية. [ 10 ] " صُمم التزامن ليكون تعاونيًا، مما يتطلب من كل سلسلة عمليات اتباع آلية التزامن قبل الوصول إلى الموارد المحمية للحصول على نتائج متسقة. يُعد كل من التأمين، والإشارة، وأنواع التزامن الخفيفة، وانتظار الدوران، والعمليات المتشابكة آليات مرتبطة بالتزامن في .NET." [ 11 ]

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

تطبيق

أقفال دوارة

من الطرق الفعّالة الأخرى لتنفيذ التزامن استخدامُ أقفال الدوران. قبل الوصول إلى أي مورد مشترك أو جزء من التعليمات البرمجية، يتحقق كل معالج من علامة. إذا كانت العلامة مُعاد ضبطها، يقوم المعالج بتعيينها ويستمر في تنفيذ الخيط. أما إذا كانت العلامة مُعيّنة (مُقفلة)، فستظل الخيوط تدور في حلقة وتتحقق باستمرار مما إذا كانت العلامة مُعيّنة أم لا. لا تكون أقفال الدوران فعّالة إلا إذا أُعيد ضبط العلامة في دورات أقل؛ وإلا فقد تؤدي إلى مشاكل في الأداء لأنها تُهدر العديد من دورات المعالج في الانتظار. [ 12 ]

الحواجز

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

وبالتالي، في مزامنة الحواجز بين عدة خيوط، ستكون هناك دائمًا بعض الخيوط التي ستنتظر خيوطًا أخرى، كما في المثال أعلاه، حيث يستمر الخيط 1 في انتظار الخيطين 2 و3. ويؤدي هذا إلى تدهور حاد في أداء العملية. [ 13 ]

يمكن تمثيل دالة انتظار تزامن الحاجز للخيط رقم i على النحو التالي:

(Wbarrier)i=f ((Tbarrier)i, (Rthread)i)

حيث يمثل Wbarrier وقت انتظار الخيط، ويمثل Tbarrier عدد الخيوط التي وصلت، ويمثل Rthread معدل وصول الخيوط. [ 14 ]

تُظهر التجارب أن 34% من إجمالي وقت التنفيذ يُقضى في انتظار الخيوط الأخرى الأبطأ. [ 13 ]

إشارات المرور

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

تسمح بعض الإشارات الثنائية (semaphores) بخيط أو عملية واحدة فقط في قسم التعليمات البرمجية. تُسمى هذه الإشارات الثنائية بالإشارات الثنائية، وهي تشبه إلى حد كبير التزامن المتبادل (Mutex). في هذه الحالة، إذا كانت قيمة الإشارة الثنائية تساوي 1، يُسمح للخيط بالوصول، وإذا كانت قيمتها تساوي 0، يُمنع الوصول. [ 15 ]

معاملة موزعة

في البنى القائمة على الأحداث ، يمكن تحقيق المعاملات المتزامنة من خلال استخدام نموذج الطلب والاستجابة ويمكن تنفيذه بطريقتين: [ 16 ]

الأسس الرياضية

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

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

لا تحتوي لغتا Java و Ada إلا على أقفال حصرية لأنهما تعتمدان على الخيوط وتعتمدان على تعليمات المعالج المقارنة والتبديل .

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

أمثلة

فيما يلي بعض الأمثلة على المزامنة فيما يتعلق بالمنصات المختلفة. [ 17 ]

في نظام التشغيل ويندوز

يوفر نظام التشغيل ويندوز ما يلي :

في لينكس

يوفر نظام لينكس ما يلي:

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

في سولاريس

يوفر نظام سولاريس ما يلي:

في Pthreads

Pthreads هي واجهة برمجة تطبيقات مستقلة عن النظام الأساسي توفر ما يلي:

  • الأقفال المتبادلة؛
  • متغيرات الحالة؛
  • أقفال القراءة والكتابة؛
  • أقفال الدوران؛
  • الحواجز .

انظر أيضاً

مراجع

  1. ↑ غرامولي، ف. (2015). أكثر مما قد ترغب بمعرفته عن التزامن: Synchrobench، قياس تأثير التزامن على الخوارزميات المتزامنة (ملف PDF) . وقائع ندوة ACM SIGPLAN العشرين حول مبادئ وممارسات البرمجة المتوازية. ACM. الصفحات 1-10 . 
  2. ↑ شينغشين، تشو، وتونغشيانغ غو، وشينغبينغ ليو (2014). "تقليل التزامن في حلول التكرار المتفرقة للحواسيب العملاقة الموزعة" . الحوسبة والرياضيات مع التطبيقات . 67 (1): 199-209 . doi : 10.1016/j.camwa.2013.11.008 . hdl : 10754/668399 .
  3. ↑ "معيار HPCG" .
  4. ↑ سيلبرشاتز، أبراهام؛ جالفين، بيتر ب.؛ غاني، جريج (29 يوليو 2008). مفاهيم أنظمة التشغيل . وايلي. ISBN 978-0470128725.
  5. ↑ تنظيم وتصميم الحاسوب، إصدار MIPS: واجهة الأجهزة/البرمجيات (سلسلة مورغان كوفمان في هندسة وتصميم الحاسوب) . مورغان كوفمان. 2013. ISBN 978-0124077263.
  6. ↑ البرمجة المتوازية: تقنيات وتطبيقات باستخدام محطات العمل الشبكية والحواسيب المتوازية . بيرسون. 2005. ISBN 978-0131405639.
  7. ↑ سيلبرشاتز، أبراهام؛ غاني، غريغ؛ غالفين، بيتر باير (11 يوليو 2008). "الفصل 6: مزامنة العمليات". مفاهيم أنظمة التشغيل ( الطبعة الثامنة). جون وايلي وأولاده. ISBN  978-0-470-12872-5.
  8. ↑ هينيسي، جون ل.؛ باترسون، ديفيد أ. (30 سبتمبر 2011). "الفصل 5: التوازي على مستوى الخيوط". هندسة الحاسوب: منهج كمي ( الطبعة الخامسة). مورغان كوفمان. ISBN  978-0-123-83872-8.
  9. ↑ "الأقفال الجوهرية والتزامن" . دروس جافا . أوراكل . تم الاطلاع عليه بتاريخ 10 نوفمبر 2023 .
  10. ↑ "نظرة عامة على أساسيات التزامن" . مايكروسوفت ليرن . مايكروسوفت. سبتمبر 2022. تم الاطلاع عليه في 10 نوفمبر 2023 .
  11. ↑ راوس، مارغريت (19 أغسطس 2011). "التزامن" . تيكوبيديا . تم الاسترجاع في 10 نوفمبر 2023 .
  12. ↑ ماسا، أنتوني (2003). تطوير البرمجيات المدمجة باستخدام ECos . بيرسون للتعليم. ISBN 0-13-035473-2.
  13. 1 2 مينغ، جينغلي؛ تشين، تيانتشو؛ بان، بينغ؛ ياو، جون؛ وو، مينغهوي (2014). "آلية تخمينية لمزامنة الحاجز". المؤتمر الدولي لهندسة الكهرباء والإلكترونيات (IEEE) لعام 2014 حول الحوسبة والاتصالات عالية الأداء، والندوة الدولية السادسة لهندسة الكهرباء والإلكترونيات (IEEE) لعام 2014 حول أمن وسلامة الفضاء الإلكتروني، والمؤتمر الدولي الحادي عشر لهندسة الكهرباء والإلكترونيات (IEEE) لعام 2014 حول البرمجيات والأنظمة المدمجة (HPCC، CSS، ICESS) . الصفحات 858-865 . doi : 10.1109/HPCC.2014.148 . ISBN  978-1-4799-6123-8.
  14. ↑ رحمن، محمد محمود (2012). "مزامنة العمليات في المعالجات متعددة النوى والمعالجات متعددة المعالجات". المؤتمر الدولي للمعلوماتية والإلكترونيات والرؤية (ICIEV) لعام 2012. الصفحات 554-559 . doi : 10.1109/ICIEV.2012.6317471 . ISBN  978-1-4673-1154-0. S2CID 8134329 . 
  15. ↑ لي، ياو، تشينغ، كارولين (2003). مفاهيم الوقت الحقيقي للأنظمة المدمجة . كتب CMP. ISBN 978-1578201242.{{cite book}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
  16. ↑ ريتشاردز، مارك (2020). أساسيات هندسة البرمجيات: منهج هندسي . دار نشر أورايلي ميديا. رقم ISBN 978-1492043454.
  17. ↑ سيلبرشاتز، أبراهام؛ غاني، غريغ؛ غالفين، بيتر باير (7 ديسمبر 2012). "الفصل 5: مزامنة العمليات". مفاهيم أنظمة التشغيل ( الطبعة التاسعة). جون وايلي وأولاده. ISBN  978-1-118-06333-0.
  18. ↑ "ما هو RCU، من حيث المبدأ؟ [ LWN.net ] " . lwn.net .
  19. ↑ "مجسات القفل التكيفية" . وثائق أوراكل .
  20. ↑ ماورو، جيم. "البوابات الدوارة وتوارث الأولوية - صن وورلد - أغسطس 1999" . sunsite.uakom.sk .
  • شنايدر، فريد ب. (1997). حول البرمجة المتزامنة . سبرينغر-فيرلاغ نيويورك، المحدودة. ISBN 978-0-387-94942-0.