مرحبا ، habrozhiteli! يتم اختيار لغة C ++ عندما تحتاج إلى إنشاء تطبيقات سريعة البرق حقًا. والمعالجة التنافسية عالية الجودة ستجعلها أسرع. تتيح لك الميزات الجديدة لـ C ++ 17 استخدام القوة الكاملة للبرمجة متعددة الخيوط لحل مشاكل معالجة الرسوم والتعلم الآلي بسهولة ، إلخ. أنتوني ويليامز ، خبير في المعالجة التنافسية ، ينظر في الأمثلة ويصف المهام العملية ، وكذلك أسرار المشاركة التي ستكون مفيدة للجميع في بما في ذلك المطورين الأكثر خبرة.
في الكتاب • نظرة عامة كاملة على ميزات C ++ 17. • إطلاق والتحكم في التدفق. • تزامن العمليات التنافسية. • تطوير كود المنافسة. • تصحيح تطبيقات ذات مؤشرات ترابط متعددة. الكتاب مناسب للمطورين ذوي المستوى المتوسط باستخدام C و C ++. تجربة البرمجة التنافسية غير مطلوبة.
تطوير كود المنافسة
8.1. طرق لتوزيع العمل بين المواضيع
تخيل أنك بحاجة إلى بناء منزل. للقيام بذلك ، سيكون عليك حفر حفرة الأساس ، وملء الأساس نفسه ، وإقامة الجدران ، وأنابيب الأنابيب والأسلاك الكهربائية ، إلخ. من الناحية النظرية ، مع المهارات الكافية ، يمكن القيام بكل شيء بشكل مستقل ، ولكن على الأرجح سيستغرق الكثير من الوقت ، وسوف تحتاج إلى التحول من وظيفة واحدة إلى واحد آخر. ولكن يمكنك استئجار مساعدين. بعد ذلك ، سيكون من الضروري اختيار عدد المساعدين الذين سيتم تعيينهم ، وتحديد ما يجب أن يكونوا قادرين عليه. يمكنك ، على سبيل المثال ، توظيف عاملين والعمل معهم. بعد ذلك ، ما زال عليك التبديل من عمل إلى آخر ، ولكن الآن ستنطلق الأمور بشكل أسرع ، حيث سيكون هناك المزيد من الفنانين.
يمكنك اختيار خيار آخر - استئجار فريق من المتخصصين ، مثل الحجارة والنجار والكهربائي والسباكة. سيعمل كل منهم في تخصصه الخاص ، لذلك ، حتى يمتلك السباك جبهة عمل ، سيجلس في وضع الخمول. ومع ذلك سوف تسير الأمور بشكل أسرع من ذي قبل ، حيث يوجد عدد أكبر من العمال ، وبينما يقوم كهربائي بإجراء الأسلاك في المطبخ ، يمكن للسباك الذهاب إلى الحمام. ولكن عندما لا يكون هناك عمل لأخصائي معين ، يتم الحصول على مزيد من التوقف. ومع ذلك ، يمكن الإشارة إلى أنه حتى مع أخذ فترة التوقف في الاعتبار ، يتحرك العمل بسرعة أكبر عندما يأتي المتخصصون إلى العمل ، بدلاً من فريق من العمال. لا يحتاج المتخصصون إلى تغيير الأدوات باستمرار ، وبالتأكيد سينفذ كل منهم مهمته بشكل أسرع من العامل. ما إذا كان هذا سيكون في الواقع يعتمد على الظروف المحددة: يتم تعلم كل شيء في الممارسة العملية.
حتى إذا كنت تضم متخصصين ، فلا يزال عليك اختيار عدد مختلف من العمال من مختلف التخصصات. ربما يكون من المنطقي استئجار عدد أكبر من عمال البناء على سبيل المثال. بالإضافة إلى ذلك ، يمكن أن يتغير تكوين فريقك والفعالية الكلية لعمله إذا كان عليك بناء العديد من المنازل في وقت واحد. حتى لو كان هناك القليل من العمل للسباك في منزل واحد ، ثم عند بناء العديد من المنازل في وقت واحد ، يمكن أن تؤخذ ليوم كامل. علاوة على ذلك ، إذا لم تكن مضطرًا لدفع أجور للمتخصصين عن التوقف ، فيمكنك تعيين فريق أكبر ، حتى إذا لم يتغير عدد الأشخاص الذين يعملون في وقت واحد.
لكن توقف عن الحديث عن البناء. ماذا كل هذا له علاقة مع المواضيع؟ ويمكنك تطبيق اعتبارات مماثلة عليها. يجب أن تقرر عدد مؤشرات الترابط التي يجب استخدامها والمهام التي يجب عليهم تنفيذها. هل نحن بحاجة إلى مؤشرات ترابط عالمية تؤدي العمل المطلوب في لحظة معينة ، أو مؤشرات ترابط متخصصة يتم تكييفها بشكل جيد مع شيء واحد فقط؟ أو ربما الأمر يستحق الجمع بين كليهما؟ يجب اتخاذ هذه القرارات بغض النظر عن أسباب موازاة البرنامج ، ويعتمد أداء وضوح الكود بشكل كبير على مدى نجاحها. لذلك ، من المهم للغاية تخيل الخيارات المتاحة من أجل اتخاذ قرار كفء عند تطوير بنية التطبيق. في هذا القسم ، سننظر في عدد من طرق توزيع المهام ، بدءًا من توزيع البيانات بين سلاسل الرسائل حتى يتم إنجاز أي عمل آخر.
8.1.1. توزيع البيانات بين المواضيع قبل المعالجة
أسهل الموازاة هي الخوارزميات البسيطة ، مثل std :: for_each ، التي تقوم بعمليات على كل عنصر من عناصر مجموعة البيانات. لموازنة هذه الخوارزمية ، يمكنك تعيين كل عنصر إلى أحد سلاسل عمليات المعالجة. في المستقبل ، عند النظر في مشكلات الأداء ، سيتضح أن أفضل خيار توزيع لتحقيق الأداء الأمثل يعتمد على خصائص بنية البيانات.
عند توزيع البيانات ، تكون أبسط الحالات هي عندما يتم تعيين أول عناصر N لتيار واحد ، وعناصر N التالية إلى أخرى ، وهكذا (الشكل 8.1) ، ولكن يمكن استخدام مخططات أخرى. بغض النظر عن طريقة توزيع البيانات ، يقوم كل مؤشر ترابط بمعالجة العناصر المعينة له فقط ، دون التفاعل مع مؤشرات الترابط الأخرى حتى ينتهي المعالجة.
يجب أن تكون البنية مألوفة لأي شخص
عمل مع البرمجة في
بيئات تمرير الرسائل (MPI أو
www.mpi-forum.org ) أو
بيئات OpenMP (http://www.openmp.org/): تنقسم المهمة إلى العديد من المهام التي يتم تنفيذها بالتوازي ، تعمل مهام سير العمل بشكل مستقل عن بعضها البعض ، ويتم جمع النتائج في المرحلة الأخيرة من المعلومات. تم استخدام هذا النهج في المثال مع دالة التجميع من القسم 2.4: كل من المهام المتوازية ومرحلة التخفيض هي التراكم. بالنسبة لخوارزمية for_each البسيطة ، فإن الخطوة الأخيرة مفقودة ، لأنه لا يوجد شيء يمكن تقليله.
تلعب حقيقة تعريف المزيج على أنه جوهر المرحلة النهائية دورًا مهمًا للغاية: تنفيذ أولي مماثل لتلك الموضحة في القائمة 2.9 سيؤدي هذا المزيج كمرحلة تسلسلية نهائية. ولكن في الغالب تكون هذه المرحلة متوازية أيضًا: التراكم هو عملية اختزال ، لذلك يمكن تغيير الكود في القائمة 2.9 للحصول على استدعاء متكرر لنفس الكود عندما يكون عدد سلاسل العمليات ، على سبيل المثال ، أكبر من الحد الأدنى لعدد العناصر التي يتم معالجتها بواسطة الخيط. يمكنك أيضًا فرض سير العمل على تنفيذ خطوات مجموعة التحديثات بمجرد أن يكمل كل منهم مهمته ، بدلاً من بدء سلاسل رسائل جديدة في كل مرة.
على الرغم من فعاليتها ، هذه التقنية ليست متعددة الاستخدامات. في بعض الأحيان لا يمكن تقسيم البيانات بدقة مقدمًا ، لأن تكوين كل جزء يصبح معروفًا فقط أثناء المعالجة. على وجه الخصوص ، يكون هذا واضحًا عند استخدام خوارزميات متكررة مثل Quicksort ، لذلك فهي تتطلب طريقة مختلفة.
8.1.2. توزيع البيانات العودية
تحتوي خوارزمية Quicksort على مرحلتين رئيسيتين: تقسيم البيانات إلى جزأين - كل شيء يأتي إلى أحد العناصر (المرجع) ، وكل شيء بعده بترتيب الفرز النهائي ، والفرز المتكرر لهذين النصفين. من المستحيل موازنته عن طريق تقسيم البيانات مبدئيًا ، لأنه من الممكن تحديد "النصف" الذي تقع فيه فقط أثناء معالجة العناصر. إذا كنت تنوي موازاة هذه الخوارزمية ، فأنت بحاجة إلى استخدام جوهر العودية. في كل مستوى من مستويات التكرار ، يتم إجراء المزيد والمزيد من المكالمات إلى الدالة quick_sort ، حيث يتعين عليك فرز كلا من تلك التي تكون أكبر من المرجع وتلك التي تكون أصغر منها. هذه المكالمات العودية مستقلة عن بعضها البعض لأنها تشير إلى مجموعات منفصلة من العناصر. لهذا السبب ، هم أول المرشحين للقدرة التنافسية. يظهر هذا التوزيع العودية في الشكل. 8.2.
تمت تلبية هذا التطبيق بالفعل في الفصل 4. بدلاً من إجراء نداءين متكررين للنصفين الأكبر والأصغر ، استخدمنا الدالة std :: async () ، التي تدير مهام غير متزامنة للنصف الأصغر في كل خطوة. نظرًا لاستخدام std :: async () ، كان على مكتبة مؤشرات الترابط C ++ أن تقرر متى تبدأ المهمة في سلسلة جديدة ، ومتى - في الوضع المتزامن.
هناك ظرف مهم واحد: عند فرز مجموعة بيانات كبيرة ، يؤدي بدء سلسلة رسائل جديدة لكل تكرار إلى زيادة سريعة في عدد مؤشرات الترابط. عند فحص مشكلات الأداء ، سيتم إظهار أن العديد من مؤشرات الترابط يمكنها إبطاء التطبيق. بالإضافة إلى ذلك ، مع مجموعة كبيرة من تدفق البيانات قد لا يكفي ببساطة. تبدو فكرة تقسيم المهمة بأكملها في مثل هذا العودية ناجحة جدًا ، ما عليك سوى مراقبة عدد الخيوط بعناية. في الحالات البسيطة ، تقوم الدالة std :: async () بمعالجة هذا ، ولكن هناك خيارات أخرى.
أحدها هو استخدام الدالة std :: thread :: hardware_concurrency () لتحديد عدد مؤشرات الترابط ، كما حدث في الإصدار الموازي للدالة cumulate () من القائمة 2.9. بعد ذلك ، بدلاً من بدء سلسلة رسائل جديدة لكل مكالمة متكررة ، يمكنك وضع الجزء المراد فرزه في مكدس آمن لمؤشر الترابط ، على سبيل المثال ، كما تمت مناقشته في الفصلين 6 و 7. إذا كان مؤشر الترابط لا يفعل شيئًا أو أنهى معالجة كل أجزاءه أو ينتظر فرز الجزء ، تأخذ جزء من المكدس وفرزها.
سرد 8.1 يوضح تنفيذ بسيط لهذه التكنولوجيا. كما هو الحال في معظم الأمثلة الأخرى ، فإنه يوضح فقط النية ، وليس رمزًا جاهزًا للاستخدام العملي. إذا كنت تستخدم برنامج التحويل البرمجي C ++ 17 وتدعمه مكتبتك ، فيجب عليك استخدام الخوارزميات المتوازية التي توفرها المكتبة القياسية وفقًا للأوصاف الواردة في الفصل 10.
القائمة 8.1. خوارزمية Quicksort متوازية تستخدم مجموعة من الأجزاء التي تنتظر الفرز
هنا ، تضع الدالة parallel_quick_sort
(19) الجزء الأكبر من المسؤوليات الوظيفية في فئة فارز
(1) ، والتي توفر طريقة سهلة لتجميع مجموعة الأجزاء غير المفرزة
(2) والعديد من مؤشرات الترابط
(3) . يتم تنفيذ العمل الرئيسي في وظيفة مكون do_sort
(9) ، والتي يشغلها تقسيم البيانات المعتاد
(10) . هذه المرة ، بدلاً من بدء تشغيل مؤشر ترابط جديد لكل جزء ، فإنه يدفع هذه القطعة على الحزمة (11) ويبدأ تشغيل مؤشر ترابط جديد فقط إذا كان هناك مورد معالج مجاني (12). نظرًا لأنه يمكن معالجة جزء ذي قيم أقل من الجزء المرجعي بواسطة دفق آخر ، يجب أن ننتظر استعداده
(13) . بحيث لا يضيع هذا الوقت (في حالة وجود خيط سن واحد أو أن جميع الخيط مشغول بالفعل) ، تتم محاولة لمعالجة الأجزاء من المكدس لفترة الانتظار هذه
(14) . تقوم دالة try_sort_chunk باسترداد جزء من الحزمة
(7) ، وفرزها
(8) ، وحفظ النتائج في وعد الوعد حتى يتمكنوا من تلقي الدفق الذي يضع هذه القطعة على المكدس
(15) .
الآن ، أصبحت سلاسل العمليات التي تم إطلاقها للتو في حلقة وحاول فرز الأجزاء من المكدس
(17) إذا لم يتم تعيين علامة end_of_data
(16) . بين عمليات التحقق ، فإنها تتخلى عن مورد الحوسبة لمؤشرات الترابط الأخرى حتى يتمكنوا من دفع عمل إضافي إلى المكدس. يعتمد عمل الكود من حيث ترتيب هذه المواضيع على إتلاف فئة فارزك
(4) . عندما يتم فرز جميع البيانات ، ستُرجع الدالة do_sort التحكم (حتى مع الحفاظ على نشاط مؤشرات الترابط المنفذة) ، سيعود مؤشر الترابط الرئيسي من parallel_quick_sort
(20) ويدمر كائن الفرز. سيقوم بتعيين علامة end_of_data
(5) وسينتظر مؤشرات الترابط لإنهاء العمل
(6). سيؤدي تعيين العلامة إلى إيقاف الحلقة في وظيفة مؤشرات الترابط (16).
باستخدام هذا الأسلوب ، ستختفي مشكلة العدد غير المحدود من سلاسل العمليات الملازمة لدالة spawn_task التي أطلقت السلسلة الجديدة ، وستختفي التبعية في مكتبة سلاسل رسائل C ++ ، التي تحدد عدد مؤشرات الترابط بالنسبة لك ، كما يحدث عند استخدام std :: async (). بدلاً من ذلك ، لمنع تبديل المهام كثيرًا ، يتم تقييد عدد مؤشرات الترابط بالقيمة التي يتم إرجاعها بواسطة الدالة std :: thread :: hardware_concurrency (). ولكن هناك مشكلة أخرى تنشأ: إدارة هذه التدفقات وتبادل البيانات بينها يعقد التعليمات البرمجية إلى حد كبير. بالإضافة إلى ذلك ، على الرغم من أن مؤشرات الترابط تقوم بمعالجة عناصر البيانات الفردية ، فإنها جميعًا تصل إلى المكدس ، وتضيف أجزاء جديدة إليه وتأخذ شظايا للمعالجة. يمكن لهذه المنافسة الشديدة أن تقلل من الأداء ، حتى لو تم استخدام مجموعة مكدسة خالية من الأقفال (وبالتالي ، غير محظورة) ، وسيتم قريباً النظر في أسباب ذلك.
هذا النهج هو إصدار خاص من تجمع مؤشرات الترابط - مجموعة من مؤشرات الترابط ، يستقبل كل منها عملًا من قائمة الوظائف المؤجلة ، ويقوم بتنفيذها ، ثم ينتقل إلى قائمة واحدة جديدة. تتم مناقشة بعض المشكلات المحتملة الكامنة في تجمع مؤشرات الترابط (بما في ذلك المنافسة عند الوصول إلى قائمة الأعمال) ، وطرق حلها في الفصل 9. عند توسيع نطاق التطبيق الذي تم إنشاؤه بحيث يعمل على عدة معالجات ، سنناقش هذا الفصل لاحقًا (انظر القسم الفرعي 8.2.1).
عند توزيع البيانات قبل المعالجة وفي الوضع العودي ، يُفترض أنها مثبتة مسبقًا ، وأن البحث جاري لتوزيعها. لكن هذا لا يحدث دائمًا: إذا تم إنشاء البيانات في الوضع الديناميكي أو من مصدر خارجي ، فهذا النهج لا يعمل. في هذه الحالة ، قد يكون من المنطقي توزيع العمل وفقًا لنوع المهمة ، وليس استنادًا إلى البيانات نفسها.
8.1.3. توزيع العمل حسب نوع المهمة
يعتمد توزيع العمل بين سلاسل الرسائل عن طريق تعيين كل منها (مقدمًا أو بشكل متكرر أثناء معالجة البيانات) أجزاء مختلفة من البيانات في أي حال على افتراض أن مؤشرات الترابط ستقوم بنفس العمل على كل قطعة. التوزيع البديل للعمل هو تخصص التدفقات ، حيث يؤدي كل منهما مهمة منفصلة ، حيث يقوم السباكون والكهربائيون بمهام مختلفة في بناء المنزل. يمكن أن تعمل التدفقات مع بيانات مختلفة أو مع نفس البيانات ، ولكن في الحالة الأخيرة ، فإنها تفعل ذلك لأغراض مختلفة.
ينشأ هذا التقسيم الغريب للعمل نتيجة لفصل المهام بمساعدة المنافسة: كل مؤشر ترابط لديه مهمة منفصلة ، والتي يؤديها بشكل مستقل عن التدفقات الأخرى. في بعض الأحيان ، يمكن لمؤشرات الترابط الأخرى توصيل البيانات إلى الدفق أو إنتاج أحداث ينبغي أن تستجيب لها ، ولكن بشكل عام ، يركز كل دفق على الأداء عالي الجودة لمهمة واحدة. هذا تصميم أساسي جيد ، حيث يجب أن تكون كل قطعة من التعليمات البرمجية مسؤولة عن شيء واحد.
توزيع العمل حسب نوع المهمة من أجل تقاسم المسؤولية
يجب أن يتعامل التطبيق المفرد مع التعارضات المرتبطة بمبدأ المسؤولية الفردية ، عندما يكون هناك العديد من المهام التي يجب القيام بها بشكل مستمر لفترة معينة ، أو يجب أن يتعامل التطبيق مع معالجة الأحداث الواردة في الوقت المناسب (على سبيل المثال ، يضغط المستخدم على مفتاح أو تصل البيانات عبر الشبكة) في وجود مهام غير مكتملة أخرى. في بيئة الحوسبة المفردة الترابط ، يجب عليك إنشاء تعليمة برمجية مستقلة لتشغيل جزء من المهمة A ، جزء من المهمة B ، للتحقق مما إذا كان المفتاح مضغوطًا ولا توجد حزم شبكة ، ثم يعود دوريًا إلى الجزء التالي من المهمة A. يؤدي هذا إلى تعقيد التعليمات البرمجية للتنفيذ المهام A بسبب الحاجة إلى الحفاظ على حالتها وإعادة التحكم بشكل دوري إلى الحلقة الرئيسية. إذا أضفت الكثير من المهام إلى الدورة ، فقد يتباطأ العمل بشكل ملحوظ وربما يلاحظ المستخدم رد فعل بطيئًا على ضربات المفاتيح. أنا متأكد من أن الجميع لاحظ المظاهر المتطرفة لموقف مماثل في بعض التطبيقات: لقد قمت بتعيين مهمة للتطبيق ، ولا تتفاعل الواجهة مع أي شيء حتى يتم الانتهاء منه.
هنا تأتي التدفقات على المسرح. إذا قمت بتشغيل كل مهمة في سلسلة رسائل منفصلة ، فيمكن لنظام التشغيل القيام بذلك بدلاً من ذلك. في التعليمات البرمجية للمهمة A ، يمكنك التركيز على إكمال المهمة دون القلق بشأن الحفاظ على الحالة والعودة إلى الحلقة الرئيسية ، أو حول مقدار الوقت الذي سيمر قبل حدوث ذلك. بمعنى أن نظام التشغيل سيوفر الحالة تلقائيًا وفي الوقت المناسب سوف يتحول إلى المهمة B أو C ، وإذا كان النظام الذي سيتم تشغيل البرنامج به عدة نوى أو معالجات ، فسيكون من الممكن تنفيذ المهام A و B. في وقت واحد رمز لمعالجة ضغطات المفاتيح أو الإيصالات يمكن الآن تنفيذ حزم الشبكة في الوقت المناسب ، وسيستفيد الجميع: سيتلقى المستخدم استجابة كافية من البرنامج ، وستحصل أنت كمطور على رمز مبسط ، حيث يمكن توجيه كل تدفق لأداء العمليات المتعلقة مباشرة بواجباته ، دون مزجها مع تدفق التحكم وتفاعل المستخدم.
صورة مثالية آخذة في الظهور. ولكن هل يمكن أن يتحول كل ذلك بهذه الطريقة؟ كما هو الحال دائما ، كل هذا يتوقف على الظروف المحددة. , . , . , , - . , - , . , . - , . , , - , , , . , , , .
. -, , . , , , . . . , , , , . , , — , , .
عند تقسيم العمل بين سلاسل الرسائل بناءً على نوع المهمة ، يجب ألا يقتصر الأمر على الخيارات المعزولة تمامًا. إذا كانت عدة مجموعات من بيانات الإدخال تتطلب نفس تسلسل العمليات المطبقة ، يمكن توزيع العمل بحيث يؤدي كل مؤشر ترابط مرحلة واحدة من التسلسل العام.توزيع تسلسل المهام بين المواضيع
, . : , , .
— . , , . , , , .
, 8.1.1, , . , .
, : , . , 20 , 3 . , . , , , , 12 , 24 — . . 20 . . . , , , , 12 . , 12 , . , : , , , , , . 3 12 .
, 9 , . . , , . 25 , — . , , : , 100 , , 1 , 100 , 1 100 . , , . , , , .
, , , , .
8.2. ,
, , . , , . , 16 , .
, — , , ( ), . , : ?
8.2.1. ?
( ) , . , , , . , . , . , , ( ) . , , , .
16- 16 : 16 . , 16 . , , ( ). , 16 , , , 1. (oversubscription).
, , C++11 (Standard Thread Library) std::thread::hardware_concurrency(). .
std::thread::hardware_concurrency() : - , , . , , std::thread::hardware_concurrency(), . std::async() , . .
, , , . — , , . , , , , C++. , std::async(), , , . , . , , std::thread::hardware_concurrency(), . , , , .
, . , , , , .
, — .
»يمكن الاطلاع على مزيد من المعلومات حول الكتاب على
موقع الناشر»
المحتويات»
مقتطفات25% —
C++عند دفع النسخة الورقية من الكتاب ، يتم إرسال كتاب إلكتروني عبر البريد الإلكتروني.