FiberTaskingLib
v2.0.4
هذه مكتبة لتمكين مؤشرات الترابط المتعددة القائمة على المهام. يسمح بتنفيذ الرسوم البيانية للمهام ذات التبعيات التعسفية. يتم تمثيل التبعيات كعدادات ذرية.
تحت الأغطية، يتم تنفيذ الرسم البياني للمهمة باستخدام الألياف، والتي بدورها يتم تشغيلها على مجموعة من الخيوط العاملة (خيط واحد لكل نواة وحدة المعالجة المركزية). يسمح هذا للمجدول بالانتظار على التبعيات دون تسلسل المهام أو تبديل السياق.
تم إنشاء هذه المكتبة لأول مرة كدليل على مفهوم الأفكار التي قدمها كريستيان جيرلينج في حديثه لعام 2015 في GDC بعنوان "موازنة محرك الكلاب المشاغب باستخدام الألياف".
عرض تقديمي مسجل مجاني لـ GDC Vault
الشرائح
# include " ftl/task_scheduler.h "
# include " ftl/wait_group.h "
# include < assert.h >
# include < stdint.h >
struct NumberSubset {
uint64_t start;
uint64_t end;
uint64_t total;
};
void AddNumberSubset (ftl::TaskScheduler *taskScheduler, void *arg) {
( void )taskScheduler;
NumberSubset *subset = reinterpret_cast <NumberSubset *>(arg);
subset-> total = 0 ;
while (subset-> start != subset-> end ) {
subset-> total += subset-> start ;
++subset-> start ;
}
subset-> total += subset-> end ;
}
/* *
* Calculates the value of a triangle number by dividing the additions up into tasks
*
* A triangle number is defined as:
* Tn = 1 + 2 + 3 + ... + n
*
* The code is checked against the numerical solution which is:
* Tn = n * (n + 1) / 2
*/
int main () {
// Create the task scheduler and bind the main thread to it
ftl::TaskScheduler taskScheduler;
taskScheduler. Init ();
// Define the constants to test
constexpr uint64_t triangleNum = 47593243ULL ;
constexpr uint64_t numAdditionsPerTask = 10000ULL ;
constexpr uint64_t numTasks = (triangleNum + numAdditionsPerTask - 1ULL ) / numAdditionsPerTask;
// Create the tasks
// FTL allows you to create Tasks on the stack.
// However, in this case, that would cause a stack overflow
ftl::Task *tasks = new ftl::Task[numTasks];
NumberSubset *subsets = new NumberSubset[numTasks];
uint64_t nextNumber = 1ULL ;
for ( uint64_t i = 0ULL ; i < numTasks; ++i) {
NumberSubset *subset = &subsets[i];
subset-> start = nextNumber;
subset-> end = nextNumber + numAdditionsPerTask - 1ULL ;
if (subset-> end > triangleNum) {
subset-> end = triangleNum;
}
tasks[i] = { AddNumberSubset, subset };
nextNumber = subset-> end + 1 ;
}
// Schedule the tasks
ftl::WaitGroup wg (&taskScheduler);
taskScheduler. AddTasks (numTasks, tasks, ftl::TaskPriority::Normal, &wg);
// FTL creates its own copies of the tasks, so we can safely delete the memory
delete[] tasks;
// Wait for the tasks to complete
wg. Wait ();
// Add the results
uint64_t result = 0ULL ;
for ( uint64_t i = 0 ; i < numTasks; ++i) {
result += subsets[i]. total ;
}
// Test
assert (triangleNum * (triangleNum + 1ULL ) / 2ULL == result);
( void )result;
// Cleanup
delete[] subsets;
// The destructor of TaskScheduler will shut down all the worker threads
// and unbind the main thread
return 0 ;
}للحصول على مقدمة رائعة عن الألياف والفكرة العامة، أقترح مشاهدة حديث كريستيان جيرلينج. يمكنك مشاهدته مجانًا (حتى وقت كتابة هذا التقرير) من قبو GDC. ومع ذلك، سأقدم لمحة عامة عن كيفية عمل هذه المكتبة أدناه:
تتكون الألياف من كومة ومساحة تخزين صغيرة للسجلات. إنه سياق تنفيذ خفيف الوزن للغاية يتم تشغيله داخل سلسلة رسائل. يمكنك التفكير في الأمر على أنه غلاف لخيط فعلي.
جمال الألياف هو أنه يمكنك التبديل بينها بسرعة كبيرة. في النهاية، يتكون المحول من حفظ السجلات، ثم تبديل مؤشر التنفيذ ومؤشر المكدس. يعد هذا أسرع بكثير من تبديل سياق مؤشر الترابط الكامل.
للإجابة على هذا السؤال، دعونا نقارنها بمكتبة أخرى متعددة المهام تعتمد على المهام: Intel's Threading Building Blocks. TBB هي مكتبة مهام مصقولة وناجحة للغاية. يمكنه التعامل مع الرسوم البيانية للمهام المعقدة حقًا ولديه جدولة ممتازة. ومع ذلك، دعونا نتخيل السيناريو:
تقوم المهمة "أ" بإنشاء المهام "ب" و"ج" و"د" وترسلها إلى المجدول
تقوم المهمة "أ" ببعض الأعمال الأخرى، ولكنها تصل بعد ذلك إلى التبعية: يجب الانتهاء من "ب" و"ج" و"د".
إذا لم ينتهوا، يمكننا أن نفعل شيئين:
تدور الانتظار / النوم
اطلب من المجدول مهمة جديدة وابدأ في تنفيذها
لنأخذ الطريق الثاني
لذلك يمنحنا المجدول المهمة G ونبدأ في التنفيذ
لكن المهمة G تنتهي بالحاجة إلى التبعية أيضًا، لذلك نطلب من المجدول مهمة جديدة أخرى
وآخر وآخر
في هذه الأثناء، اكتملت المهام B وC وD
من الناحية النظرية، يمكن متابعة المهمة "أ"، ولكنها مدفونة في المكدس أسفل المهام التي حصلنا عليها أثناء انتظارنا
الطريقة الوحيدة التي يمكننا من خلالها استئناف A هي الانتظار حتى تنحل السلسلة بأكملها مرة أخرى إليها، أو نعاني من تبديل السياق.
الآن، من الواضح أن هذا مثال مفتعل. وكما قلت أعلاه، لدى TBB برنامج جدولة رائع يعمل بجد للتخفيف من هذه المشكلة. ومع ذلك، يمكن للألياف أن تساعد في القضاء على المشكلة تمامًا من خلال السماح بالتبديل بين المهام بتكلفة زهيدة. وهذا يسمح لنا بعزل تنفيذ مهمة عن أخرى، مما يمنع تأثير "التسلسل" الموصوف أعلاه.
قائمة انتظار المهام - قائمة انتظار "عادية" للاحتفاظ بالمهام التي تنتظر تنفيذها. في الكود الحالي، توجد قائمة انتظار "ذات أولوية عالية"، وقائمة انتظار "ذات أولوية منخفضة".
تجمع الألياف - مجموعة من الألياف المستخدمة للتبديل إلى مهام جديدة أثناء انتظار المهمة الحالية على التبعية. الألياف تنفذ المهام
مؤشرات الترابط العاملة - 1 لكل نواة وحدة المعالجة المركزية المنطقية. هذه تعمل على تشغيل الألياف.
انتظار المهام - جميع الألياف / المهام التي تنتظر الوفاء بالتبعية. يتم تمثيل التبعيات باستخدام WaitGroups
يمكن إنشاء المهام على المكدس. إنها مجرد بنية بسيطة تحتوي على مؤشر دالة وقيمة void *arg اختيارية لتمريرها إلى الوظيفة:
struct Task {
TaskFunction Function;
void *ArgData;
};Task tasks[ 10 ];
for ( uint i = 0 ; i < 10 ; ++i) {
tasks[i] = {MyFunctionPointer, myFunctionArg};
}يمكنك جدولة مهمة للتنفيذ عن طريق استدعاء TaskScheduler::AddTasks()
ftl::WaitGroup wg (taskScheduler);
taskScheduler-> AddTasks ( 10 , tasks, ftl::TaskPriority::High, &wg);تتم إضافة المهام إلى قائمة الانتظار، ويمكن أن تبدأ سلاسل العمليات الأخرى (أو المهمة الحالية، عند الانتهاء من المهمة الحالية) في تنفيذها عندما يتم إخراجها من قائمة الانتظار.
يمكن لـ AddTasks اختياريًا أخذ مؤشر إلى WaitGroup. إذا قمت بذلك، ستتم زيادة قيمة WaitGroup حسب عدد المهام الموضوعة في قائمة الانتظار. في كل مرة تنتهي فيها مهمة ما، سيتم تقليل مجموعة الانتظار ذريًا. يمكنك استخدام هذه الوظيفة لإنشاء تبعيات بين المهام. يمكنك القيام بذلك باستخدام الوظيفة
void WaitGroup::Wait ();هذا هو المكان الذي تلعب فيه الألياف. إذا كانت قيمة WaitGroup == 0، فستُرجع الدالة بشكل تافه. إذا لم يكن الأمر كذلك، فسيقوم المجدول بنقل الألياف الحالية إلى قائمة الألياف المنتظرة في WaitGroup والحصول على ألياف جديدة من Fiber Pool . تنبثق الألياف الجديدة مهمة من قائمة انتظار المهام وتبدأ التنفيذ بها.
ولكن ماذا عن المهمة/الألياف التي قمنا بتخزينها في WaitGroup؟ ومتى سينتهي تنفيذه؟
عندما تصل قيمة WaitGroup إلى الصفر من التناقصات، فإننا نضيف جميع الألياف المنتظرة مرة أخرى إلى قائمة الانتظار في TaskScheduler. في المرة التالية التي يقوم فيها الخيط بتبديل الألياف (إما بسبب انتهاء الألياف الحالية، أو لأنها تسمى WaitGroup::Wait() )، سيتم التقاط المهمة الجاهزة واستئنافها من حيث توقفت.
بشكل عام، لا ينبغي عليك استخدام Mutexes في كود الألياف، وذلك لسببين:
إذا أخذت كائن المزامنة (mutex)، وقمت بالاتصال بـ WaitGroup::Wait()، عند استئناف Wait()، فقد يكون الكود الخاص بك موجودًا في مؤشر ترابط آخر. سيكون إلغاء تأمين كائن المزامنة (mutex) سلوكًا غير محدد، ومن المحتمل أن يؤدي إلى طريق مسدود
سيؤدي تزاحم Mutex إلى حظر سلاسل العمليات العاملة. وبما أننا عمومًا لا نفرط في اشتراك الخيوط في النوى، فإن هذا يترك النوى في وضع الخمول.
لحل هذه المشكلة، أنشأنا Fibtex. إنه ينفذ الواجهة القابلة للقفل القياسية، بحيث يمكنك استخدامها مع جميع الأغلفة المفضلة لديك (std::lock_guard، std::unique_lock، وما إلى ذلك) ويتم تنفيذها خلف الكواليس مع انتظار الألياف، لذلك إذا تم قفل Fibtex، يمكن للنادل قم بالتبديل إلى مهمة أخرى وقم بعمل قيم
عند استئناف الألياف بعد WaitGroup::Wait() أو Fibtex::lock()، ليس هناك ما يضمن أنها ستستأنف على نفس الخيط الذي كانت تعمل عليه عندما تم تعليقها. بالنسبة لمعظم التعليمات البرمجية، هذا جيد. ومع ذلك، لدى بعض المكتبات افتراضات قوية. على سبيل المثال، في DirectX، يجب عليك إرسال الإطار النهائي من نفس مؤشر الترابط الذي أنشأ سلسلة المبادلة. وبالتالي، ستحتاج بعض التعليمات البرمجية إلى ضمان استئناف الألياف على نفس الخيط الذي كانت تعمل فيه عند تعليقها. للقيام بذلك، يمكنك استخدام الوسيطة pinToCurrentThread . عند التعيين على true ، سيضمن المجدول أن الألياف المستأنفة ستعمل على نفس الخيط. هذه الوسيطة متاحة لـ WaitGroup::Wait() وFibtext::lock(). ملاحظة: يعد تثبيت مؤشر الترابط أكثر تكلفة من السلوك الافتراضي، ومن المحتمل أن يؤدي إلى استئناف أبطأ بكثير للمهمة المعنية (نظرًا لأنه يتطلب من مؤشر الترابط المثبت إنهاء المهمة التي يقوم بتشغيلها حاليًا). ولذلك، ينبغي استخدامه فقط إذا كان ذلك ضروريا حقا.
مترجم C++11
كميك 3.2 أو أكبر
قوس | ويندوز | لينكس | نظام التشغيل العاشر | دائرة الرقابة الداخلية | أندرويد |
ذراع | يحتاج إلى اختبار | مدعوم بالكامل | من الناحية النظرية | من الناحية النظرية | من الناحية النظرية |
الذراع_64 | يحتاج إلى اختبار | مدعوم بالكامل | يحتاج إلى اختبار | من الناحية النظرية | من الناحية النظرية |
x86 | مدعوم بالكامل | يحتاج إلى اختبار | يحتاج إلى اختبار | ||
x86_64 | مدعوم بالكامل | مدعوم بالكامل | مدعوم بالكامل |
FiberTaskingLib هو بناء CMake قياسي. ومع ذلك، للحصول على تعليمات مفصلة حول كيفية إنشاء المكتبة وتضمينها في مشروعك الخاص، راجع صفحة الوثائق.
المكتبة مرخصة بموجب ترخيص Apache 2.0. ومع ذلك، تقوم FiberTaskingLib بتوزيع واستخدام التعليمات البرمجية من مشاريع مفتوحة المصدر أخرى لها تراخيص خاصة بها:
تعزيز شوكة السياق: تعزيز الترخيص v1.0
Catch2: تعزيز الترخيص v1.0
المساهمات هي موضع ترحيب كبير. راجع صفحة المساهمة لمزيد من التفاصيل.
كان هذا التنفيذ شيئًا قمت بإنشائه لأنني اعتقدت أن العرض التقديمي الذي قدمه كريستيان كان مثيرًا للاهتمام حقًا وأردت استكشافه بنفسي. لا يزال الكود قيد التنفيذ وأود أن أسمع انتقاداتك حول كيفية تحسينه. سأستمر في العمل على هذا المشروع وتحسينه قدر الإمكان.
