Futex के बिना इसका कोई मतलब नहीं

 (h4x0r.org)
4 पॉइंट द्वारा GN⁺ 2025-08-21 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • The Art of Multiprocessor Programming पाठ्यपुस्तक में futex की अवधारणा शामिल न होने पर अफसोस जताया गया है
  • Futex आधुनिक parallel programming में efficient synchronization का एक मुख्य building block है, और यह पारंपरिक System V आधारित lock की तुलना में बेहतर performance देता है
  • Futex में lock acquisition और wait/wake functionality को अलग किया जाता है, जिससे अनावश्यक system call और overhead कम होते हैं
  • Futex के आधार पर spinlock, mutex, recursive lock जैसे विभिन्न concurrency primitives को सीधे implement करने के उदाहरण और तकनीकें शामिल हैं
  • लेखक का कहना है कि पुस्तक में engineering practice के लिए जरूरी आधुनिक synchronization methods शामिल नहीं हैं, जो academia और industry के बीच की दूरी को दिखाता है

परिचय

  • Phil Eaton ने 'The Art of Multiprocessor Programming, 2nd Edition' book club शुरू किया
  • यह पुस्तक parallel programming के क्षेत्र में एक authoritative textbook मानी जाती है, लेकिन लेखक इसके व्यावहारिक उपयोगिता की कमी की ओर इशारा करता है
  • खासकर, चौथे वर्ष के undergraduate students और graduate students के लिए होने के बावजूद, इसमें futex जैसी मुख्य synchronization technique को शामिल न करने की आलोचना की गई है

Futex क्या है – और यह क्यों महत्वपूर्ण है

  • Futex का अर्थ “fast user space mutex” है, लेकिन वास्तव में यह mutex से अधिक आधुनिक lock implementation के लिए OS-supported synchronization primitive है
  • पहले ज़्यादातर lock, System V IPC semaphore के आधार पर implement किए जाते थे, जिनमें efficiency और scalability की सीमाएँ थीं
  • 2002 में Linux में futex आने के बाद, 1000 concurrent jobs वाले वातावरण में System V lock की तुलना में 20~120 गुना तेज performance देखा गया
  • Windows (2012) और macOS (2016) जैसे अन्य OS ने भी ऐसे ही mechanisms अपनाए
  • आज व्यापक रूप से इस्तेमाल होने वाले pthreads जैसे system libraries के lock, futex का उपयोग करते हैं

Futex कैसे काम करता है और यह अलग क्यों है

  • पारंपरिक semaphore में lock और waiting जुड़े होते थे, लेकिन futex lock acquisition और wait/wake को अलग करता है
  • इससे अनावश्यक delay और system call कम किए जा सकते हैं, और यदि lock release के समय कोई waiting thread न हो तो kernel में जाने की जरूरत नहीं पड़ती
  • Futex का wait call “किसी खास memory address का मान अपेक्षित स्थिति में हो तभी wait करना” संभव बनाता है, और timeout भी support करता है
  • Futex का wake call किसी खास memory address से जुड़ी internal wait list से इच्छित संख्या में threads को जगाता है
  • यह memory address के वास्तविक मान की पुष्टि मांगता है, जिससे स्थिति बदल चुकी होने पर अनावश्यक waiting रोकी जा सके

Futex का वास्तविक उपयोग – सीधे implementation

  • Futex एक low-level primitive है, इसलिए compiler और hardware की memory operation ordering issues को ध्यान में रखते हुए atomic data types का उपयोग किया जाता है
  • Linux में syscall के जरिए futex system call को सीधे बुलाना पड़ता है, जबकि macOS में __ulock interface का उपयोग होता है (हाल में आसान API भी जोड़ी गई है)
  • मूल रूप से futex wait सफलता पर 0 और विफलता पर error code (जैसे timeout) लौटाता है
  • Futex-आधारित मुख्य operations:
    • h4x0r_futex_wait_timespec() : expected value मिलने पर wait, timeout लागू किया जा सकता है
    • h4x0r_futex_wake() : 1 या सभी waiters को जगाना

Mutex/Spinlock/Recursive lock implementation के व्यावहारिक उदाहरण

Spinlock

  • lock का सबसे सरल रूप, जो केवल एक single bit (atomic_fetch_or) से काम करता है
  • lock मिलने तक infinite loop (“spin”) चलता है, लेकिन उच्च contention में CPU waste, गलत release, और recursive call पर deadlock का जोखिम जैसी संरचनात्मक समस्याएँ होती हैं

Hybrid mutex (‘unsafe’ mutex)

  • आमतौर पर पहले spinlock से कोशिश, और कुछ बार असफल होने पर futex पर स्विच करके efficient blocking implement किया जाता है
  • यदि कोई waiter न हो तो अनावश्यक system call से बचा जा सकता है, और waiters के लिए wake system call भी न्यूनतम रखे जा सकते हैं
  • कड़ी ownership verification या recursion handling न होने के कारण इसे “unsafe” कहा गया है

Waiter-counter mutex

  • एक bit lock state के लिए और बाकी waiter count के लिए उपयोग होती हैं, ताकि अनावश्यक wake system call कम किए जा सकें
  • इसमें भी ownership और recursion handling अभी नहीं है

Ownership management वाला mutex

  • pthread_t value के जरिए lock owner और state को स्पष्ट रूप से track किया जाता है, जिससे गलत unlock या recursive use की समस्या पकड़ी जा सके
  • lock acquisition, release और waiter management सभी को सख्ती से atomic operations से नियंत्रित किया जाता है

Recursive lock

  • प्रत्येक thread के लिए nesting count (depth) counter जोड़कर एक ही thread को nested lock acquisition की अनुमति दी जाती है
  • unlock पर depth कम होती है, और 0 होने पर वास्तविक unlock और wake किया जाता है
  • हर operation को atomic operations और सख्त ownership checks के साथ implement किया जाता है

बाकी चुनौतियाँ और वास्तविक engineering की स्थिति

  • यदि lock owner thread असामान्य रूप से बंद हो जाए या मर जाए, तो lock management के लिए अलग management list, termination callback आदि जैसी अतिरिक्त व्यवस्था चाहिए
  • inter-process shared mutex का उपयोग करते समय भी state changes को manage करने के लिए अतिरिक्त सावधानी चाहिए
  • POSIX RW lock में recursive nesting behavior परिभाषित नहीं है और implementation के अनुसार बदलता है, इसलिए व्यवहार में safety सुनिश्चित करना कठिन है
  • लेखक आलोचना करता है कि पुस्तक में वे concurrency issues शामिल नहीं हैं जो वास्तव में production में महत्वपूर्ण हैं (futex, recursive lock, async runtime आदि)

निष्कर्ष

  • 'The Art of Multiprocessor Programming' इतिहास या सैद्धांतिक दृष्टिकोण की ओर झुकी हुई है और आधुनिक parallel programming के महत्वपूर्ण practical ज्ञान को पर्याप्त रूप से नहीं समेटती
  • सिस्टम में वास्तव में काम करने वाले futex जैसे मुख्य synchronization building blocks को ठीक से न पढ़ाना, आने वाली पीढ़ी के लिए व्यावहारिक नुकसान का कारण बन सकता है
  • लेखक आधुनिक अवधारणाओं को शामिल करने और सामग्री को अधिक व्यावहारिक बनाने की जरूरत पर जोर देता है

संदर्भ सामग्री

  • पूरे code examples codeberg पर देखे जा सकते हैं

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2025-08-21
Hacker News राय

  • Windows में WaitForMultipleObjects नाम की एक सुविधा है, और Linux ने भी 5.16 (2021 के अंत) में Futex2 के साथ इसे जोड़ा
    संबंधित लिंक
    हाल में Futex2 में कई तरह के सुधार किए गए हैं
    आखिरकार NUMA सपोर्ट भी जोड़ दिया गया
    NUMA संबंधित लिंक1
    NUMA संबंधित लिंक2
    NUMA परफ़ॉर्मेंस के लिए बहुत महत्वपूर्ण तत्व है
    io_uring को 6.7 (2024) में futex पर लागू किया गया, जिससे postgresql aio परफ़ॉर्मेंस बेहतर करने में मदद मिली
    संबंधित लेख
    6.7 में Small requeue और single wait फीचर भी जोड़े गए
    संबंधित लिंक

    • Windows में WaitForMultipleObjects कोई नई जोड़ी गई सुविधा नहीं थी, यह शुरुआत से ही 30 साल से ज़्यादा समय से मौजूद है
      WaitForMultipleObjects, UNIX की तुलना में Windows NT का एक फ़ायदा था, लेकिन IBM PL/I में भी 1965 में इससे मिलता-जुलता फीचर था
      UNIX का 'wait' फ़ंक्शन IBM PL/I के 'wait' का एक सरल संस्करण था, और Multics से मिली कई अन्य सुविधाओं की तरह यह भी मूल मॉडल की तुलना में कमज़ोर था
      MS के WaitForSingleObject और WaitForMultipleObjects भी कुशल implementation नहीं थे, इसलिए अंततः Linux के futex के समकक्ष WaitOnAddress लाना पड़ा
      Linux futex की सीमाएँ हैं कि इसका आकार 32-bit तक सीमित है और यह एक समय में केवल एक event का इंतज़ार कर सकता है
      atomic bit operations का उपयोग करके कई events के लिए wait लागू किया जा सकता है, लेकिन यह कुशल नहीं है, इसलिए 32-bit आकार की समस्या और बड़ी हो जाती है
      'futex' में WaitForMultipleObjects के कुछ फ़ायदे जोड़ने की कोशिश स्वागतयोग्य है
      ऐसी कोशिश Windows की नकल नहीं है, बल्कि Microsoft से भी कहीं पुरानी, 50 साल से ज़्यादा समय से जानी-पहचानी एक क्लासिक तकनीक को फिर से लागू करना है

    • यह अफ़सोस की बात है कि अभी भी futex_swap फीचर नहीं है
      संबंधित चर्चा1
      संबंधित सामग्री2

    • Futex का WFMO(WaitForMultipleObjects) से संबंध नहीं है, बल्कि यह keyed events के अधिक समकक्ष है
      Linux में WFMO के बराबर functionality select/poll/epoll है

    • io_uring में futex सपोर्ट सचमुच बहुत अच्छा फीचर है
      इसे Ruby fibers के साथ काम करते समय mutex और queue implementation में इस्तेमाल किया गया
      सोर्स कोड देखें

  • किताब में साफ़ कहा गया है कि synchronization structures को खुद implement करने के बजाय library/language/system द्वारा दिए गए structures का इस्तेमाल करना चाहिए
    किताब का मुख्य फ़ोकस किसी खास platform पर नहीं, बल्कि concurrency के समग्र concepts पर है
    यह थोड़ा निराशाजनक है कि लेख लेखक ने इसे कुछ बढ़ा-चढ़ाकर टकराव वाले ढाँचे में लिखा
    यह लेख "TAoMP क्या नहीं कहता" जैसी सहयोगी दृष्टि से लिखा जाता तो बेहतर होता
    यह भी ध्यान देने योग्य है कि यह ब्लॉग नया है, Phil ने यह पोस्ट डाली, और Phil ने दूसरी पोस्टें भी promote कीं

    • वह लेख मैंने ही लिखा था, और किताब पढ़कर निराश होने की वजह से लिखा
      मुझे लगा कि अकादमिक और उद्योग, दोनों में, हमें वास्तव में काम आने वाली चीज़ें सीखने को नहीं मिलतीं
      इसलिए मंशा "चलो futex सीखें!" जैसी नहीं थी
      दरअसल मैं किताब से इतना निराश हुआ कि दूसरी पोस्टों को टालकर यह पहले लिख दी
      Phil के साथ पहले काम करने की वजह से संपर्क है, लेकिन अब तक मुझे लिखने और पाठक ढूँढ़ने में कोई खास कठिनाई नहीं हुई

    • पहले मैंने SysV style को dinosaur से भी तुलना न करने लायक कहा था, अब लगता है वह कुछ ज़्यादा कठोर था
      इस मामले में और विनम्रता की ज़रूरत है

  • futex की सबसे शानदार बात यह है कि इसका ढाँचा handle-less है
    यह syscall के ज़रिए allocation/free की ज़रूरत के बिना, kernel-आधारित memory watcher के रूप में बहुत उपयोगी बुनियादी behavior देता है
    अगर कोई waiting thread नहीं है तो सब कुछ साफ़-सुथरे ढंग से समेट जाता है, और contention न हो तो kernel को mutex के अस्तित्व का पता भी नहीं चलता
    मुझे यह जानने में दिलचस्पी है कि kernel futex को high performance के साथ कैसे manage करता है
    आज ही पहली बार futex2 के बारे में पता चला
    संबंधित दस्तावेज़

    • सही बात, और यह भी कि जब भी कोई thread lock पर block हो, तब kernel का malloc() बुलाकर data allocate करना हम नहीं चाहेंगे
      इसी से बचने के लिए कई OS हर thread बनते समय एक 'queue object' allocate कर देते हैं, और जब वह thread contested lock से टकराता है तो वही object उस lock से जोड़ दिया जाता है
      यानी lock से जुड़े queue objects की एक linked list बन जाती है, जिसमें कई threads जुड़े रहते हैं, और thread के wake होने पर वह एक object साथ ले जाता है
      thread समाप्त होने पर यह गारंटी नहीं होती कि उसे वही object वापस मिलेगा जो उसने शुरू में बनाया था; बीच में objects आपस में मिल जाते हैं
      solaris में सबसे पहले ऐसा ढाँचा (turnstile) लाया गया था, और BSDs ने भी यही तरीका अपनाया
      solaris internals देखें
      BSD pdf सामग्री

    • शुरुआती Unix kernel की wait queues भी इसी तरह की थीं

  • 2002 के मूल futex पेपर में futex की दक्षता स्पष्ट रूप से साबित की गई थी, और 1000 parallel tasks वाले टेस्ट में इसने sysv locks की तुलना में 20 से 120 गुना तेज़ परफ़ॉर्मेंस दिखाई
    लेकिन वास्तव में baseline sysv locks नहीं है
    व्यावहारिक रूप से, futex के बिना भी lock implementation में fast path पर आमतौर पर kernel entry नहीं होती, और केवल slow path पर ही kernel में wait के लिए जाना पड़ता है; futex का असली सुधार बस इतना है कि lock wait state दिखाने वाली user-space data structure का आकार छोटा हो गया
    दूसरे विकल्पों में thin locks (JVM में इस्तेमाल होने वाला तरीका), ParkingLot (पूरी तरह userland implementation) शामिल हैं, जो OS futex के बिना भी काम कर सकते हैं

    • मेरे अनुभव में, ज़्यादातर लोग वास्तव में काम में उपलब्ध बुनियादी primitives ही सीखते हैं, इसलिए ध्यान इस पर रहता है कि मेरी language की standard library क्या देती है
      यानी sysv से futex की ओर जो प्रवाह आया, वही प्रमुख है, और हाल में custom तरीक़े भी हैं, लेकिन मुख्यधारा futex ही है
      अगर कोई userland में अपना scheduler सीधे बनाए, तो अलग implementation संभव है, लेकिन ज़्यादातर लोग शायद file descriptors पर लिखने और queue खुद manage करने का रास्ता चुनेंगे
      मुझे संदेह है कि इससे वास्तव में कितना फ़ायदा होगा

    • व्यवहार में, कोई भी modern lock अंततः अंदर से futex ही इस्तेमाल करता है, अगर सपोर्ट मौजूद हो
      Linux पर futex सबसे कुशल waiting mechanism है, इसलिए slow (down) path में हमेशा futex इस्तेमाल करना बेहतर होता है
      language में thread.park() जैसी चीज़ें भी संभवतः futex के ऊपर ही चलती हैं

    • मैं जानना चाहता हूँ कि क्या JVM अब भी thin lock इस्तेमाल करता है
      मुझे पुराने references मिले थे जिनमें JVM के futex call करने की बात थी, इसलिए जानने की उत्सुकता है कि क्या वह thin lock पर migrate हुआ है
      Stack Overflow संबंधित चर्चा

  • [recursive locks] का वास्तविक implementation standards के बीच भी एकसमान नहीं है, और कई बार इसकी कठिनाई के कारण इसे परिभाषित ही नहीं किया गया
    यह रवैया काफ़ी निराशाजनक है
    मतलब, "OS या language implementer शायद feature X को ठीक से implement नहीं कर पाएँगे, तो बेहतर है कि application developer ही इसे खुद संभाले"
    अंततः downstream users के पास vendor बदलने के अलावा कोई ठोस विकल्प नहीं बचता

    • standards पर ज़रूरत से ज़्यादा बंधन लगाने से बेहतर implementations की संभावना बंद हो सकती है
      उदाहरण के लिए, C++ standard hash table और regex पर इतने बंधन हैं कि वे third-party विकल्पों की तुलना में बहुत धीमे हैं
      अगर किसी खास constraint (जैसे केवल chaining method की अनुमति) या feature guarantee को अनिवार्य कर दिया जाए, तो वैकल्पिक high-performance implementations रुक जाते हैं
      recursive rwlock में भी performance sacrifice करने या कम checking वाली implementations संभव हैं, इसलिए मुझे नहीं लगता कि अलग-अलग दिशाओं को रोकना चाहिए

    • निजी तौर पर मुझे लगता है कि recursive lock का उपयोग ही नहीं करना चाहिए, इसलिए उसके लिए standard support spec जोड़ने की खास ज़रूरत महसूस नहीं होती

    • अगर worse is better परिघटना के बारे में और जानना है, तो wiki देखिए
      मुझे यह खास पसंद नहीं, लेकिन यही व्यावहारिक वास्तविकता है

  • मुझे जिज्ञासा हुई कि Linux में futex केवल 32bit int तक ही सीमित क्यों है, इसलिए मैंने इसे खोजा
    64-bit सपोर्ट की चर्चा में Linus ने कहा था कि user space में 64-bit atomic इस्तेमाल करो और केवल निचले 32 bits को futex के लिए उपयोग करो
    लेकिन C/C++ में mixed-size atomic को undefined behavior माना जाता है, और वास्तव में glibc की semaphore implementation भी इसी तरह काम करती है
    एक 64-bit integer में high 32 को waiter count और low 32 को semaphore value के रूप में इस्तेमाल किया जाता है, और futex केवल निचले 32 bits पर लगाया जाता है
    मुझे जिज्ञासा है कि gcc में यह defined behavior है, या process boundary (kernel process) की वजह से मायने नहीं रखता, या फिर glibc भी undefined behavior ही इस्तेमाल कर रहा है

  • मैं Anthony Williams की C++ Concurrency in Action भी सुझाऊँगा, जो futex या synchronization primitives को सीधे implement करने के तरीक़ों को तो नहीं कवर करती, लेकिन memory ordering और lock-free structures के लिए ज़रूरी SMR जैसी, व्यवहारिक दुनिया के काफ़ी क़रीब चीज़ें बताती है
    अगर और hardware-केंद्रित नज़रिया चाहिए, तो Paul McKenney की मुफ़्त किताब "Is Parallel Programming Hard, And, If So, What Can You Do About It?" भी पढ़ने लायक है
    यह किताब भी futex को गहराई से नहीं बताती, लेकिन Ulrich Drepper की "Futexes Are Tricky" की ओर मार्गदर्शन करती है
    TAOMPP उच्च-स्तरीय concurrency concepts को अच्छे से समझाने के लिए उपयुक्त है; इसमें OS-स्तर के implementation details होना आवश्यक नहीं
    वैसे भी Peterson या bakery lock वास्तविक उपयोग में काम के नहीं हैं, लेकिन उनके proofs सीख लेने भर से व्यावहारिक concurrency algorithms समझने में बहुत मदद मिलती है

    • bakery lock spin lock के लिए अच्छा है और cache-friendly भी है
      reader/writer spin lock भी implement किया जा सकता है, लेकिन वह सख़्त FIFO होता है
      user space में bakery lock की spin wait के साथ futex जोड़ना संभव है, लेकिन बहुत अक्षम होगा
      futex को मूल रूप से इस तरह के उपयोग (spin wait) के लिए डिज़ाइन नहीं किया गया
      lock-free structures और hazard pointer, RCU* वगैरह भी अब भी tricky हैं
      wait-free hazard pointer वास्तव में बनाया जा सकता है
      *RCU के मामले में copy-on-write सहज लगता है, लेकिन updates ज़्यादा हों तो लागत बढ़ती है

  • जैसे Windows 8 में futex-जैसा फीचर जोड़ा गया, वैसे ही मूल Win32 critical section kernel semaphore-आधारित था
    लेकिन Vista में आए SRW lock की अंदरूनी संरचना कैसी है, यह जानने की उत्सुकता है

    • CRITICAL_SECTION और SRWLock दोनों में, यदि contention न हो, तो kernel entry नहीं होती
      SRWLock keyed event आधारित है, और CRITICAL_SECTION विफल होने पर भी on-demand kernel object बनाकर call करता है, फिर keyed event पर fallback करता है

  • 2014 के Linux futex implementation में Pinkie Pie द्वारा खोजी गई vulnerability में, requeue-once rule केवल futex_wait_requeue_pi को दिए गए futex पर ही अनुमत है
    A से B, और फिर B से C तक requeue संभव नहीं, लेकिन B से B पर फिर से reassign करना संभव है
    इस दौरान कुछ शर्तें पूरी होने पर cleanup function नहीं बुलाया जाता और pointer dangling स्थिति में रह जाता है
    संबंधित मामला देखा जा सकता है
    संबंधित इश्यू

  • कुछ लोग crashed thread के कारण data consistency की चिंता नहीं करते, लेकिन जब तक पूरा process नहीं मरता, lock cleanup की समस्या बनी रहती है
    इसके लिए एक समाधान robust lock है
    held futex list को kernel में register किया जाता है, और sys_set_robust_list के ज़रिए thread समाप्त होने पर उस bit को handle करके waiting side को wake किया जाता है

    • robust lock approach की सबसे बड़ी कमी यह है कि जिस resource की सुरक्षा lock कर रहा था, वह खुद पहले ही inconsistent स्थिति में हो सकता है
      अगर यह स्पष्ट न हो कि thread crash क्यों हुआ, तो data integrity बिगड़ चुकी हो सकती है और recovery असंभव हो सकती है
      इसलिए पूरे app को साथ में बंद कर देना अधिक व्यावहारिक हो सकता है
      robust lock के साथ cleanup/recovery capability अपने-आप में शानदार है, लेकिन शायद 95% engineers robust data structures को सही तरह से डिज़ाइन ही नहीं करेंगे
      4% के पास उसके लिए समय नहीं होगा, और केवल बाकी 1% ही इसका सही लाभ उठाकर सही implementation करेंगे

    • कई processes के बीच futex (cross-process state) इस्तेमाल करते समय, watchdog process हर process के लिए Unix domain socket (SOCK_STREAM या SOCK_SEQPACKET) खोलकर crash detect कर सकता है और per-process state को साफ़ कर सकता है

    • मैंने भी mutex की चर्चा को process boundary तक ही सीमित रखा, क्योंकि डर था कि बात बहुत गहराई में जाकर अंतहीन हो जाएगी