حاجز (علوم الحاسوب)

📅 آخر تحديث: ٣ أغسطس ٢٠٢٦
✍️ نُشر في: ٣ أغسطس ٢٠٢٦
📷 يحتوي على 1 صور
الموسوعة الحرة

في الحوسبة المتوازية ، يُعد الحاجز أسلوبًا للتزامن . [ 1 ] يعني الحاجز لمجموعة من الخيوط أو العمليات في شفرة المصدر أن جميع الخيوط/العمليات تتوقف عند تلك النقطة ولا تتابع عملها حتى تصل جميع الخيوط/العمليات الأخرى إلى هذا الحاجز. [ 2 ]

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

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

تطبيق

لنأخذ المثال التالي لحاجز الخيوط. يتطلب حاجز الخيوط متغيرًا لتتبع العدد الإجمالي للخيوط التي دخلت الحاجز. [ 3 ] عند دخول عدد كافٍ من الخيوط الحاجز، يتم رفعه. كما يلزم استخدام آلية تزامن مثل mutex عند تطبيق حاجز الخيوط.

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

يمكن توضيح ذلك من خلال مثال C التالي باستخدام خيوط POSIX . [ 1 ]

#include <stdio.h> #include <pthread.h>#define TOTAL_THREADS 2 #define THREAD_BARRIERS_NUMBER 3typedef struct Barrier { pthread_mutex_t lock ; int barrier_count ; int thread_count ; } Barrier ;حاجز حاجز ؛void barrier_init ( ThreadBarrier * bar , pthread_mutexattr_t * attr , int count ) { pthread_mutex_init ( & ( bar -> lock ), attr ); bar -> barrier_count = count ; bar -> thread_count = 0 ; // تهيئة إجمالي عدد الخيوط إلى 0 }void barrier_wait ( Barrier * bar ) { if ( ! pthread_mutex_lock ( & ( bar -> lock ))) { bar -> total_thread ++ ; pthread_mutex_unlock ( & ( bar -> lock )); }بينما ( عدد الخيوط في الشريط < عدد الحواجز في الشريط ) { // تنفيذ حاجز الانتظار المشغول (عدم القيام بأي شيء حتى وصول عدد كافٍ من الخيوط) }إذا لم يتم تنفيذ الأمر `pthread_mutex_lock ( & ( bar- > lock )))` ، فسيتم إنقاص قيمة ` bar- > thread_count - ` بمقدار خيط واحد عند تجاوز حاجز الخيوط، ثم يتم فتح القفل باستخدام الأمر `pthread_mutex_unlock ( & ( bar- > lock )) ` .void barrier_destroy ( Barrier * bar ) { pthread_mutex_destroy ( & ( bar -> lock )); }void * thread_func ([[ maybe_unused ]] void * p ) { printf ( "الخيط ذو المعرف %ld ينتظر عند الحاجز، حيث أن عدد الخيوط العاملة غير كافٍ (%d) ... \n " , pthread_self (), THREAD_BARRIERS_NUMBER ); thread_barrier_wait ( & barrier ); printf ( "تم رفع الحاجز، الخيط ذو المعرف %ld يعمل الآن \n " , pthread_self ()); }int main () { pthread_t thread_ids [ TOTAL_THREADS ];thread_barrier_init ( & barrier , NULL , THREAD_BARRIERS_NUMBER ); for ( int i = 0 ; i < TOTAL_THREADS ; i ++ ) { pthread_create ( & thread_ids [ i ], NULL , thread_func , NULL ); }// بما أن الدالة pthread_join() تُوقف العملية حتى تنتهي جميع الخيوط المحددة، // ولا يوجد عدد كافٍ من الخيوط للانتظار عند الحاجز، فإن هذه العملية تُوقف for ( int i = 0 ; i < TOTAL_THREADS ; i ++ ) { pthread_join ( thread_ids [ i ], NULL ); }thread_barrier_destroy ( & barrier ); printf ( "تم رفع حاجز الخيوط \n " ); // لن يتم استدعاء هذا السطر لأن TOTAL_THREADS < THREAD_BARRIERS_NUMBER }

في هذا البرنامج، يتكون حاجز الخيط struct Barrierمن:

  • lockقفل تبادلي للخيوط في نظام POSIX
  • thread_countإجمالي عدد الخيوط في العملية
  • barrier_count: إجمالي عدد الخيوط المتوقع دخولها حاجز الخيوط حتى يمكن رفعه

بناءً على تعريف الحاجز، يتطلب التنفيذ وظيفة مثل تلك الموجودة thread_barrier_wait()في هذا البرنامج والتي "تراقب" العدد الإجمالي للخيوط في البرنامج من أجل رفع الحاجز.

thread_barrier_wait()في هذا البرنامج، سيتم حظر جميع استدعاءات الخيوط حتى THREAD_BARRIERS_NUMBERتصل الخيوط إلى حدّها الأقصى. ولأن الخيط الرئيسي محظور لعدم وجود ثلاثة خيوط، فلن يتم الوصول إلى السطر "تم رفع حدّ الخيوط" . نتيجة هذا البرنامج هي:

الخيط ذو المعرّف <thread_id, eg 139997337872128> ينتظر عند الحاجز، حيث لا يوجد عدد كافٍ من الخيوط قيد التشغيل (3 خيوط)... الخيط ذو المعرّف <thread_id, eg 139997329479424> ينتظر عند الحاجز، حيث لا يوجد عدد كافٍ من الخيوط قيد التشغيل (3 خيوط)...

يتم إنشاء خيطين فقط باستخدام thread_func()معالج وظيفة الخيط، والذي يستدعي thread_barrier_wait(&barrier)، بينما يتوقع حاجز الخيط استدعاء ثلاثة خيوط thread_barrier_wait()من أجل رفعه.

عند التغيير TOTAL_THREADSإلى 3، يتم رفع حاجز الخيط:

الخيط ذو المعرّف <معرّف الخيط، على سبيل المثال 140453108946688> ينتظر عند الحاجز، حيث أن عدد الخيوط العاملة غير كافٍ (3)... الخيط ذو المعرّف <معرّف الخيط، على سبيل المثال 140453117339392> ينتظر عند الحاجز، حيث أن عدد الخيوط العاملة غير كافٍ (3)... الخيط ذو المعرّف <معرّف الخيط، على سبيل المثال 140453100553984> ينتظر عند الحاجز، حيث أن عدد الخيوط العاملة غير كافٍ (3)... تم رفع الحاجز، الخيط ذو المعرّف <معرّف الخيط، على سبيل المثال 140453108946688> يعمل الآن. تم رفع الحاجز، الخيط ذو المعرّف <معرّف الخيط، على سبيل المثال 140453117339392> يعمل الآن. تم رفع الحاجز، الخيط ذو المعرّف <معرّف الخيط، على سبيل المثال 140453100553984> يعمل الآن. تم رفع حاجز الخيط.

حاجز مركزي لعكس الإحساس

إلى جانب إنقاص العدد الإجمالي للخيوط لكل خيط يجتاز حاجز الخيوط بنجاح، قد تستخدم حواجز الخيوط قيمًا معاكسة لتمييز حالة كل خيط على أنها ناجحة أو متوقفة. [ 4 ] على سبيل المثال، قد يشير الرقم 0 إلى التوقف عند الحاجز بينما يشير الرقم 1 إلى اجتياز الحاجز. [ 5 ] يُعرف هذا باسم "انعكاس الاتجاه" [ 1 ] ، كما هو موضح فيما يلي: [ 3 ] [ 6 ]

#include <stdio.h> #include <pthread.h>#define TOTAL_THREADS 2 #define THREAD_BARRIERS_NUMBER 3typedef struct Barrier { pthread_mutex_t lock ; int barrier_count ; int thread_count ; bool flag ; } Barrier ;حاجز حاجز ؛void barrier_init ( Barrier * bar , pthread_mutexattr_t * attr , int count ) { pthread_mutex_init ( & ( bar -> lock ), attr );bar- > thread_count = 0 ; bar- > barrier_count = count ; bar- > flag = false ; }void barrier_wait ( Barrier * barrier ) { thread_local bool local_flag = bar -> flag ; if ( ! pthread_mutex_lock ( & ( bar -> lock ))) { bar -> thread_count ++ ; local_sense = ! local_sense ; if ( bar -> thread_count == bar -> barrier_count ) { bar -> thread_count = 0 ; bar -> flag = local_flag ; pthread_mutex_unlock ( & ( bar -> lock )); } else { pthread_mutex_unlock ( & ( bar -> lock )); while ( bar -> flag != local_flag ) { // انتظر قيمة flag } } } }void barrier_destroy ( Barrier * bar ) { pthread_mutex_destroy ( & ( bar -> lock )); }void * thread_func ([[ maybe_unused ]] void * p ) { printf ( "الخيط ذو المعرف %ld ينتظر عند الحاجز، حيث أن عدد الخيوط العاملة غير كافٍ (%d) ... \n " , pthread_self (), THREAD_BARRIERS_NUMBER ); thread_barrier_wait ( & barrier ); printf ( "تم رفع الحاجز، الخيط ذو المعرف %ld يعمل الآن \n " , pthread_self ()); }int main () { pthread_t thread_ids [ TOTAL_THREADS ];thread_barrier_init ( & barrier , NULL , THREAD_BARRIERS_NUMBER ); for ( int i = 0 ; i < TOTAL_THREADS ; i ++ ) { pthread_create ( & thread_ids [ i ], NULL , thread_func , NULL ); }// بما أن الدالة pthread_join() تُوقف العملية حتى تنتهي جميع الخيوط المحددة، // ولا يوجد عدد كافٍ من الخيوط للانتظار عند الحاجز، فإن هذه العملية تُوقف for ( int i = 0 ; i < TOTAL_THREADS ; i ++ ) { pthread_join ( thread_ids [ i ], NULL ); }thread_barrier_destroy ( & barrier ); printf ( "تم رفع حاجز الخيوط \n " ); // لن يتم استدعاء هذا السطر لأن TOTAL_THREADS < THREAD_BARRIERS_NUMBER }

يقدم هذا الإصدار من تطبيق الحاجز المركزي السابق متغيرين جديدين: [ 1 ]

  • local_flag: قيمة منطقية محلية خاصة بالخيط للتحقق مما إذا كانت THREAD_BARRIERS_NUMBERالخيوط قد وصلت إلى الحاجز.
  • flag: علامة منطقية struct Barrierتشير إلى ما إذا كانت THREAD_BARRIERS_NUMBERالخيوط قد وصلت إلى الحاجز.

عندما يتوقف أحد الخيوط عند الحاجز، local_flagيتم عكس قيمة 's. [ 1 ] عندما يكون THREAD_BARRIERS_NUMBERعدد الخيوط المتوقفة عند حاجز الخيوط أقل من 1، فإن هذه الخيوط ستستمر في الانتظار بشرط barrier.flagألا تساوي 1 local_flag.

عندما يكون هناك عدد محدد THREAD_BARRIERS_NUMBERمن الخيوط التي تتوقف عند حاجز الخيوط، thread_countتتم إعادة تعيينها إلى 0 ويتم flagضبطها على local_flag.

حاجز الأشجار المدمج

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

فيك{\displaystyle k}- حاجز الشجرة، يتم تقسيم جميع الخيوط بالتساوي إلى مجموعات فرعية منك{\displaystyle k}تُجرى عمليات التزامن الأولى ضمن هذه المجموعات الفرعية. وبمجرد اكتمال التزامن في جميع المجموعات الفرعية، ينتقل أول خيط في كل مجموعة فرعية إلى مستوى ثانٍ لمزيد من التزامن. في المستوى الثاني، كما هو الحال في المستوى الأول، تُشكّل الخيوط مجموعات فرعية جديدة منك{\displaystyle k}تُزامَن الخيوط داخل المجموعات، حيث يُرسَل خيط واحد من كل مجموعة فرعية إلى المستوى التالي، وهكذا، حتى المستوى الأخير، حيث لا تحتاج سوى مجموعة فرعية واحدة إلى التزامن. بعد المستوى الأخير من التزامن، تُرسَل إشارة التحرير إلى المستويات العليا، وتجتاز جميع الخيوط الحاجز. [ 6 ] [ 7 ]

تنفيذ حاجز الأجهزة

يستخدم الحاجز المادي الأجهزة لتنفيذ نموذج الحاجز الأساسي المذكور أعلاه. [ 3 ]

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

وظائف حاجز سلاسل POSIX

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

  • pthread_barrier_init(): يهيئ حاجز الخيوط بعدد الخيوط اللازمة للانتظار عند الحاجز لرفعه. [ 9 ]
  • pthread_barrier_destroy(): يدمر حاجز الخيط ويحرر المورد. [ 9 ]
  • pthread_barrier_wait(): يحجب الخيط الحالي حتى يصل عدد الخيوط إلى العدد المحدد بواسطة pthread_barrier_init()استدعاءات pthread_barrier_wait()رفع الحاجز. [ 10 ]

يستخدم المثال التالي في لغة C باستخدام خيوط POSIX حواجز الخيوط لحظر جميع خيوط العملية الرئيسية، وبالتالي حظر العملية بأكملها.

#include <stdio.h> #include <pthread.h>#define TOTAL_THREADS 2 #define THREAD_BARRIERS_NUMBER 3pthread_barrier_t barrier ;void * thread_func ([[ maybe_unused ]] void * p ) { printf ( "الانتظار عند الحاجز بسبب عدم كفاية عدد الخيوط العاملة (%d) ... \n " , THREAD_BARRIERS_NUMBER ); pthread_barrier_wait ( & barrier ); printf ( "تم رفع الحاجز، الخيط ذو المعرف %ld يعمل الآن \n " , pthread_self ()); }int main () { pthread_t thread_ids [ TOTAL_THREADS ];pthread_barrier_init ( & barrier , NULL , THREAD_BARRIERS_NUMBER ); for ( int i = 0 ; i < TOTAL_THREADS ; i ++ ) { pthread_create ( & thread_ids [ i ], NULL , thread_func , NULL ); }// بما أن الدالة pthread_join() تُوقف العملية حتى تنتهي جميع الخيوط المحددة، // ولا يوجد عدد كافٍ من الخيوط للانتظار عند الحاجز، فإن هذه العملية موقوفة. for ( int i = 0 ; i < TOTAL_THREADS ; i ++ ) { pthread_join ( thread_ids [ i ], NULL ); } pthread_barrier_destroy ( & barrier ); printf ( "تم رفع حاجز الخيط \n " ); // لن يتم استدعاء هذا السطر لأن TOTAL_THREADS < THREAD_BARRIERS_NUMBER }

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

انتظار عند الحاجز لعدم كفاية عدد الخيوط العاملة (3)... انتظار عند الحاجز لعدم كفاية عدد الخيوط العاملة (3)...

يتم إنشاء خيطين فقط، كلاهما مع thread_func()معالج وظيفة الخيط، والذي يستدعي pthread_barrier_wait(&barrier)، بينما يتوقع حاجز الخيط استدعاء ثلاثة خيوط pthread_barrier_wait()من أجل رفعه.

عند التغيير TOTAL_THREADSإلى 3، يتم رفع حاجز الخيط:

جارٍ الانتظار عند الحاجز لعدم كفاية عدد الخيوط العاملة (3)... جارٍ الانتظار عند الحاجز لعدم كفاية عدد الخيوط العاملة (3)... جارٍ الانتظار عند الحاجز لعدم كفاية عدد الخيوط العاملة (3)... تم رفع الحاجز، الخيط ذو المعرف 140643372406528 يعمل الآن. تم رفع الحاجز، الخيط ذو المعرف 140643380799232 يعمل الآن. تم رفع الحاجز، الخيط ذو المعرف 140643389191936 يعمل الآن. تم رفع حاجز الخيط.

بما أن main()الدالة تُعامل كخيط (أي الخيط "الرئيسي" للعملية [ 11 ] )، فإن استدعاء الدالة pthread_barrier_wait()داخلها main()سيؤدي إلى حظر العملية بأكملها حتى تصل الخيوط الأخرى إلى الحاجز. في المثال التالي، باستخدام حواجز الخيوط مع الدالة pthread_barrier_wait()داخلها main()، يتم حظر الخيط الرئيسي لمدة 5 ثوانٍ أثناء انتظار وصول الخيطين "المنشأين حديثًا" إلى حاجز الخيوط.

#include <stdio.h> #include <pthreads.h>#define TOTAL_THREADS 2 #define THREAD_BARRIERS_NUMBER 3pthread_barrier_t barrier ;void * thread_func ([[ maybe_unused ]] void * p ) { printf ( "الانتظار عند الحاجز بسبب عدم كفاية عدد الخيوط العاملة (%d) ... \n " , THREAD_BARRIERS_NUMBER ); sleep ( 5 ); pthread_barrier_wait ( & barrier ); printf ( "تم رفع الحاجز، الخيط ذو المعرف %ld يعمل الآن \n " , pthread_self ()); }int main () { pthread_t thread_ids [ TOTAL_THREADS ];pthread_barrier_init ( & barrier , NULL , THREAD_BARRIERS_NUMBER ); for ( int i = 0 ; i < TOTAL_THREADS ; i ++ ) { pthread_create ( & thread_ids [ i ], NULL , thread_func , NULL ); }pthread_barrier_wait ( & barrier );printf ( "تم رفع حاجز الخيوط \n " ); // لن يتم استدعاء هذا السطر لأن TOTAL_THREADS < THREAD_BARRIERS_NUMBER pthread_barrier_destroy ( & barrier ); }

يتجنب هذا المثال استخدام pthread_join()انتظار اكتمال الخيطين "المنشأين حديثًا". ويستدعي دالة pthread_barrier_wait()داخلية main()لحظر الخيط الرئيسي، بحيث تبقى العملية متوقفة حتى ينتهي الخيطان من عملهما بعد انتظار 5 ثوانٍ.

انظر أيضاً

مراجع

  1. 1 2 3 4 5 "تطبيق العوائق" . جامعة كارنيجي ميلون. مؤرشف من الأصل بتاريخ 20 يناير 2018. تم الاطلاع عليه بتاريخ 2 أغسطس 2017 .
  2. 1 2 نظام تشغيل جنو. "تنفيذ pthread_barrier" . gnu.org . تم الاسترجاع في 2024-03-02 .
  3. 1 2 3 سوليهين، يان (2015-01-01). أساسيات بنية المعالجات متعددة النوى المتوازية ( الطبعة الأولى). تشابمان آند هول/سي آر سي. ISBN  978-1482211184.
  4. 1 2 كولر، ديفيد (1998). هندسة الحاسوب المتوازي: منهج الأجهزة/البرمجيات . جلف بروفيشنال. ISBN 978-1558603431.
  5. ↑ كولر، ديفيد (1998). هندسة الحواسيب المتوازية: منهج الأجهزة/البرمجيات . جلف بروفيشنال. ISBN 978-1558603431.
  6. 1 2 نانججودا، راماشاندرا؛ هيرنانديز، أوسكار؛ الأماكن القريبة : جين ، هاوكيانغ هـ. (2009-06-03). مولر، ماتياس S.؛ سوبينسكي، برونيس آر دي؛ تشابمان، باربرا م. (محرران). تطور OpenMP في عصر التوازي الشديد . ملاحظات محاضرة في علوم الكمبيوتر. سبرينغر برلين هايدلبرغ. ص 42 – 52. دوى : 10.1007/978-3-642-02303-3_4 . رقم ISBN  9783642022845.
  7. ↑ نيكولوبولوس، ديميتريوس س.؛ باباثيودورو، ثيودور س. (1999-01-01). "تقييم معماري كمي لخوارزميات وأنظمة التزامن على أنظمة ccNUMA". وقائع المؤتمر الدولي الثالث عشر للحوسبة الفائقة . ICS '99. نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM. الصفحات 319-328 . doi : 10.1145/305138.305209 . ISBN  978-1581131642S2CID 6097544. مؤرشف من الأصل بتاريخ 25-07-2017 . تم الاطلاع عليه بتاريخ 18-01-2019 . 
  8. ↑ NR Adiga، وآخرون. نظرة عامة على الحاسوب العملاق BlueGene/L. وقائع مؤتمر الشبكات والحوسبة عالية الأداء، 2002.
  9. 1 2 "pthread_barrier_init(), pthread_barrier_destroy()" . صفحة دليل لينكس . تم الاطلاع عليها بتاريخ 16-03-2024 .
  10. ↑ "pthread_barrier_wait()" . صفحة دليل لينكس . تم الاطلاع عليها بتاريخ 16-03-2024 .
  11. ↑ "كيفية الحصول على عدد العمليات والخيوط في برنامج مكتوب بلغة C؟" . stackoverflow . تم الاطلاع عليه بتاريخ 16-03-2024 .

"البرمجة المتوازية مع مزامنة الحاجز" . sourceallies.com . مارس 2012.