أساسيات فوتكس

Futex (futex - اختصار لـ "Fast userpace mutex") هي آلية اقترحها مطورو Linux من IBM في 2002 ودخلت النواة في نهاية 2003. كانت الفكرة الرئيسية هي توفير طريقة أكثر فعالية لمزامنة سلاسل رسائل المستخدم مع الحد الأدنى من المكالمات إلى نظام تشغيل kernel.

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

نقطة مهمة: Futexes هي أداة منخفضة المستوى إلى حد ما ؛ يجدر استخدامها مباشرة فقط عند تطوير المكتبات الأساسية ، مثل مكتبة C / C ++ القياسية. من غير المحتمل جدًا أنك ستحتاج إلى استخدام العملات الأجنبية في تطبيق منتظم.

الدافع

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

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

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

الاستخدام البسيط للفوتكس - التوقع والصحوة

تجمع دعوة نظام futex بين مجموعة متنوعة من الوظائف. لن نفكر في الخيارات المعقدة هنا (بعضها مفصل للغاية لدرجة أنه لم يتم وصفها حتى في الوثائق الرسمية) ، لكننا سنركز على العمليات FUTEX_WAIT و FUTEX_WAKE. سيكون الوصف في الوثائق الرسمية بمثابة قاعدة جيدة:

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

ببساطة ، إن futex عبارة عن بنية kernel تساعد كود المستخدم على مزامنة سلاسل المحادثات عند حدوث شيء ما. يمكن لبعض العمليات (أو سلاسل العمليات) انتظار الأحداث في مكالمة FUTEX_WAIT ، بينما يمكن للآخرين استدعاء هذه الأحداث باستخدام FUTEX_WAKE. يعمل الانتظار بكفاءة - يتم تعليق سلاسل الانتظار بواسطة النواة ولا تستخدم موارد المعالج حتى يتم إيقاظها عند وقوع حدث متوقع.

خصص وقتًا لقراءة الوثائق بالكامل. حسنًا ، أو على الأقل اقرأ الأقسام في FUTEX_WAIT و FUTEX_WAKE.

دعونا نلقي نظرة على مثال بسيط يوضح الاستخدام الأساسي للعملات الأجنبية لتنسيق عمل عمليتين.

عملية الطفل:

1. ينتظر 0xA في فتحة الذاكرة العامة
2. يكتب القيمة 0xB لهذه الفتحة

العملية الأم في الوقت الحالي:

1. يكتب قيمة 0xA إلى فتحة ذاكرة مشتركة
2. ينتظر ظهور 0xB فيه

مثل "المصافحة" بين عمليتين. هذا هو الرمز:

int main(int argc, char** argv) { int shm_id = shmget(IPC_PRIVATE, 4096, IPC_CREAT | 0666); if (shm_id < 0) { perror("shmget"); exit(1); } int* shared_data = shmat(shm_id, NULL, 0); *shared_data = 0; int forkstatus = fork(); if (forkstatus < 0) { perror("fork"); exit(1); } if (forkstatus == 0) { //   printf("child waiting for A\n"); wait_on_futex_value(shared_data, 0xA); printf("child writing B\n"); //  0xB         *shared_data = 0xB; wake_futex_blocking(shared_data); } else { //   printf("parent writing A\n"); //  0xA         *shared_data = 0xA; wake_futex_blocking(shared_data); printf("parent waiting for B\n"); wait_on_futex_value(shared_data, 0xB); // Wait for the child to terminate. wait(NULL); shmdt(shared_data); } return 0; } 

انتبه إلى مكالمات POSIX لتخصيص الذاكرة المشتركة بين العمليات. لم نتمكن من استخدام تخصيص الذاكرة المعتاد هنا ، حيث أن نفس عنوان المؤشرات في العمليات المختلفة سيشير بالفعل إلى كتل ذاكرة مختلفة (فريدة لكل عملية).

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

وإليك رمز دالة wait_on_futex_value:

 void wait_on_futex_value(int* futex_addr, int val) { while (1) { int futex_rc = futex(futex_addr, FUTEX_WAIT, val, NULL, NULL, 0); if (futex_rc == -1) { if (errno != EAGAIN) { perror("futex"); exit(1); } } else if (futex_rc == 0) { if (*futex_addr == val) { //    return; } } else { abort(); } } } 

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

دلالات Futex هي أشياء صعبة للغاية! سيتم إرجاع استدعاء FUTEX_WAIT على الفور إذا كانت القيمة في عنوان futex لا تساوي قيمة الوسيطة التي تم تمريرها. في حالتنا ، يمكن أن يحدث هذا إذا ذهبت العملية الفرعية للانتظار قبل أن يكتب الوالد القيمة 0xA في الفتحة. فيوتكس في هذه الحالة إرجاع القيمة EAGAIN.

وإليك رمز وظيفة wake_futex_blocking:

 void wake_futex_blocking(int* futex_addr) { while (1) { int futex_rc = futex(futex_addr, FUTEX_WAKE, 1, NULL, NULL, 0); if (futex_rc == -1) { perror("futex wake"); exit(1); } else if (futex_rc > 0) { return; } } } 

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

Futexes هي طوابير نواة للرمز المخصص.

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

هنا الرسم التخطيطي من مقالة "نظرة عامة وتحديث على الفوركس" على LWN:



في كود نواة لينكس ، يتم تنفيذ العقود الآجلة في ملف kernel / futex.c. تقوم النواة بتخزين جدول تجزئة حيث تكون المفاتيح عناوين - للعثور على قائمة الانتظار المطلوبة بسرعة وإضافة عملية الاتصال إليها. كل شيء ، بالطبع ، ليس بهذه البساطة - بعد كل شيء ، النواة نفسها تحتاج إلى مزامنة الوصول إلى البيانات في الداخل ، بالإضافة إلى دعم جميع أنواع الخيارات الإضافية لـ futeksov.

انتظر لفترة محدودة مع FUTEX_WAIT

يحتوي استدعاء نظام futex على معلمة مهلة تتيح للمستخدم تحديد المدة التي يكون فيها جاهزًا للانتظار. هنا مثال كامل حيث يتم تنفيذ ذلك ، ولكن هنا الجزء الرئيسي:

 printf("child waiting for A\n"); struct timespec timeout = {.tv_sec = 0, .tv_nsec = 500000000}; while (1) { unsigned long long t1 = time_ns(); int futex_rc = futex(shared_data, FUTEX_WAIT, 0xA, &timeout, NULL, 0); printf("child woken up rc=%d errno=%s, elapsed=%llu\n", futex_rc, futex_rc ? strerror(errno) : "", time_ns() - t1); if (futex_rc == 0 && *shared_data == 0xA) { break; } } 

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

باستخدام فوتكس لتنفيذ كائن المزامنة

بدأنا هذه المقالة بحقيقة أن العملات الأجنبية ذات فائدة عملية في تنفيذ كائنات التزامن ذات المستوى الأعلى. دعونا نحاول استخدامها (وكذلك الذرات) لتنفيذ كائن المزامنة التقليدي. يعتمد التنفيذ أدناه على الرمز الوارد في مقالة "Futexes are Tricky" التي كتبها Ulrich Drepper.

في هذا المثال ، أستخدم C ++ ، بشكل أساسي للقدرة على استخدام ذرات من معيار C ++ 11. يمكنك العثور على الكود الكامل هنا ، ولكن أهم جزء هو:

 class Mutex { public: Mutex() : atom_(0) {} void lock() { int c = cmpxchg(&atom_, 0, 1); // If the lock was previously unlocked, there's nothing else for us to do. // Otherwise, we'll probably have to wait. if (c != 0) { do { // If the mutex is locked, we signal that we're waiting by setting the // atom to 2. A shortcut checks is it's 2 already and avoids the atomic // operation in this case. if (c == 2 || cmpxchg(&atom_, 1, 2) != 0) { // Here we have to actually sleep, because the mutex is actually // locked. Note that it's not necessary to loop around this syscall; // a spurious wakeup will do no harm since we only exit the do...while // loop when atom_ is indeed 0. syscall(SYS_futex, (int*)&atom_, FUTEX_WAIT, 2, 0, 0, 0); } // We're here when either: // (a) the mutex was in fact unlocked (by an intervening thread). // (b) we slept waiting for the atom and were awoken. // // So we try to lock the atom again. We set teh state to 2 because we // can't be certain there's no other thread at this exact point. So we // prefer to err on the safe side. } while ((c = cmpxchg(&atom_, 0, 2)) != 0); } } void unlock() { if (atom_.fetch_sub(1) != 1) { atom_.store(0); syscall(SYS_futex, (int*)&atom_, FUTEX_WAKE, 1, 0, 0, 0); } } private: // 0 means unlocked // 1 means locked, no waiters // 2 means locked, there are waiters in lock() std::atomic<int> atom_; }; 

في هذا الكود ، تعد وظيفة cmpxhg غلافًا بسيطًا للاستخدام الأكثر ملاءمة للذرات:

 // An atomic_compare_exchange wrapper with semantics expected by the paper's // mutex - return the old value stored in the atom. int cmpxchg(std::atomic<int>* atom, int expected, int desired) { int* ep = &expected; std::atomic_compare_exchange_strong(atom, ep, desired); return *ep; } 

يحتوي مثال الرمز هذا على العديد من التعليقات التي توضح منطق عملياتها. لن يضر هذا ، لأن هناك خطرًا كبيرًا من رغبتك في كتابة نسخة أبسط قليلاً ، ولكنها غير صحيحة تمامًا. أما بالنسبة لهذا الرمز - فهو ليس مثاليًا في كل شيء. على سبيل المثال ، يحاول إجراء افتراض حول جهاز داخلي من النوع std :: atomic ، ويلقي محتوياته إلى int * للتمرير إلى مكالمة futex. هذا ليس هو الحال بشكل عام. يتم تجميع الرمز وتشغيله على Linux x64 ، ولكن ليس لدينا ضمان للتوافق مع الأنظمة الأساسية الأخرى. للحصول عليه ، نحتاج إلى إضافة طبقة تبعية منصة للذرات. نظرًا لأن هذا ليس موضوع هذه المقالة (وأيضًا لأنه من غير المحتمل جدًا أن تخلط العملات الأجنبية في نفس وحدة C ++) ، فسوف نحذف هذا التنفيذ. هذا مجرد عرض!

معاملات Glibc وأقفال منخفضة المستوى

لذلك وصلنا إلى النقطة التي تنفذ فيها glibc سلاسل POSIX ، جزء منها هو نوع pthread_mutex_t. كما قلت في بداية هذه المقالة ، فإن العقود الآجلة ليست هي الشيء الذي سيحتاجه المطور العادي. يتم استخدامها من قبل مكتبات وقت التشغيل أو شيء متخصص للغاية لتنفيذ بدائيات التزامن على مستوى أعلى. في هذا السياق ، من المثير للاهتمام النظر في تنفيذ كتيب بيانات معاهدة عدم انتشار الأسلحة النووية . في كود glibc ، هذا هو ملف nptl / pthread_mutex_lock.c.

الرمز معقد تمامًا بسبب الحاجة إلى دعم أنواع مختلفة من كائنات المزامنة ، ولكن يمكننا العثور على كتل مألوفة تمامًا إذا رغبت في ذلك. يمكنك أيضًا إلقاء نظرة على ملفات sysdeps / unix / sysv / linux / x86_64 / lowlevellock.h و nptl / lowlevellock.c. الرمز محير إلى حد ما ، ولكن لا يزال الجمع بين مكالمات المقارنة والتبادل وفوتكس أمرًا سهلاً.

يجب أن تفهم بالفعل التعليق الأولي لملف systeds / nptl / lowlevellock.h جيدًا:

 /* Low-level locks use a combination of atomic operations (to acquire and release lock ownership) and futex operations (to block until the state of a lock changes). A lock can be in one of three states: 0: not acquired, 1: acquired with no waiters; no other threads are blocked or about to block for changes to the lock state, >1: acquired, possibly with waiters; there may be other threads blocked or about to block for changes to the lock state. We expect that the common case is an uncontended lock, so we just need to transition the lock between states 0 and 1; releasing the lock does not need to wake any other blocked threads. If the lock is contended and a thread decides to block using a futex operation, then this thread needs to first change the state to >1; if this state is observed during lock release, the releasing thread will wake one of the potentially blocked threads. .. */ 

اذهب للعمل في سوق الفوركس

لا يستخدم Rantime Go libc (في معظم الحالات). وبالتالي ، لا يمكنها الاعتماد على تنفيذ سلاسل POSIX. بدلاً من ذلك ، يتصل مباشرة مكالمات النظام ذات المستوى الأدنى. هذا يجعلها مثال جيد على استخدام العملات الأجنبية. نظرًا لعدم وجود طريقة لاستدعاء pthread_mutex_t ، يجب عليك كتابة الاستبدال الخاص بك. دعونا نرى كيف يتم ذلك ، لنبدأ مع نوع sync.Mutex المرئي للمستخدم (في src / sync / mutex.go).

تحاول طريقة القفل من هذا النوع استخدام عملية المبادلة الذرية لالتقاط القفل بسرعة. إذا تبين أنك بحاجة إلى الانتظار ، فإنه يستدعي runtime_SemacquireMutex ، والذي يستدعي runtime.lock. تم تعريف هذه الوظيفة في src / runtime / lock_futex.go وتعلن العديد من الثوابت التي قد تبدو مألوفة لك:

 const ( mutex_unlocked = 0 mutex_locked = 1 mutex_sleeping = 2 ... ) // Possible lock states are mutex_unlocked, mutex_locked and mutex_sleeping. // mutex_sleeping means that there is presumably at least one sleeping thread. 

يحاول runtime.lock أيضًا التقاط القفل باستخدام وظيفة ذرية. هذا أمر منطقي ، حيث يتم استدعاء runtime.lock في العديد من أماكن وقت تشغيل Go ، ولكن يبدو لي أنه سيكون من الممكن تحسين الرمز بطريقة أو بأخرى عن طريق إزالة مكالمتين متتاليتين للوظيفة الذرية عند استدعاء runtime.lock من Mutex.lock.

إذا اتضح أنك بحاجة إلى الانتظار ، يتم استدعاء وظيفة futexsleep المعتمدة على النظام الأساسي ، والتي يتم تعريفها لنظام التشغيل Linux في ملف src / runtime / os_linux.go. تقوم هذه الوظيفة بإجراء استدعاء لنظام futex برمز FUTEX_WAIT_PRIVATE (في هذه الحالة ، هذا مناسب ، حيث أن وقت تشغيل Go يعيش في عملية واحدة).