Linux CPU scheduler में “lazy preemption” लागू करने की लंबी यात्रा

 (lwn.net)
3 पॉइंट द्वारा GN⁺ 2024-10-20 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Linux kernel ने throughput और response time के बीच trade-off के लिए कई preemption modes बनाए रखे हैं, और Peter Zijlstra के नए patch set के साथ lazy preemption (PREEMPT_LAZY) पर चर्चा फिर से गंभीरता से शुरू हुई है
  • मौजूदा PREEMPT_NONE, PREEMPT_VOLUNTARY, PREEMPT_FULL, PREEMPT_RT में preemption की अनुमति का दायरा अलग-अलग है; preemption जितनी अधिक बार होगी, responsiveness उतनी बेहतर हो सकती है, लेकिन throughput और lock contention पर बोझ बढ़ता है
  • PREEMPT_LAZY TIF_NEED_RESCHED_LAZY flag के जरिए “rescheduling की जरूरत है, लेकिन तुरंत नहीं” दिखाता है, और अधिकतर preemption को timer tick तक टाल देता है
  • लंबी अवधि में non-real-time preemption modes को PREEMPT_LAZY और PREEMPT_FULL तक घटाने, और kernel में जगह-जगह मौजूद cond_resched() calls को अधिकतर हटाने की दिशा है
  • मौजूदा patch set को अभी और stabilization, call sites की समीक्षा और performance testing की जरूरत है; शुरुआती tests में PREEMPT_LAZY का throughput PREEMPT_VOLUNTARY से थोड़ा कम रहा

Linux kernel के मौजूदा preemption modes

  • मौजूदा kernel कई preemption modes देता है, जो यह नियंत्रित करते हैं कि चल रहा task किसी दूसरे task द्वारा कब preempt किया जा सकता है
    • PREEMPT_NONE: सबसे सरल mode, जिसमें चल रहे task के अपना time slice पूरा कर लेने पर ही preemption की अनुमति होती है
    • PREEMPT_VOLUNTARY: ऐसा mode जिसमें kernel के अंदर जरूरत पड़ने पर preempt किए जा सकने वाले कई points जोड़े गए हैं
    • PREEMPT_FULL: ऐसा mode जिसमें spinlock holding जैसे kernel द्वारा रोके गए sections को छोड़कर लगभग हर point पर preemption की अनुमति होती है
    • PREEMPT_RT: ऐसा mode जो preemption को अधिकतर चीजों से ऊपर प्राथमिकता देता है, और अधिकांश spinlock-holding code को भी preemptible बना देता है
  • preemption level ज्यादा होने पर mouse movement या reactor के आसन्न abnormal signal जैसे events पर तेज प्रतिक्रिया दी जा सकती है
  • इसके बदले, preemption ज्यादा बार होने पर लंबे समय तक चलने वाले CPU-intensive tasks का overall throughput घट सकता है और lock contention भी बढ़ सकता है
  • कई distributions kernel को PREEMPT_DYNAMIC pseudo-mode के साथ build करते हैं
    • Boot के समय ऊपर बताए गए तीन non-real-time modes में से एक चुना जा सकता है
    • Default PREEMPT_VOLUNTARY होता है
    • जिन systems में debugfs mounted है, वहां /sys/kernel/debug/sched/preempt पर मौजूदा mode देखा जा सकता है

cond_resched() की जरूरत क्यों पड़ी

  • PREEMPT_NONE और PREEMPT_VOLUNTARY kernel code execution के दौरान arbitrary preemption की अनुमति नहीं देते
  • अगर kernel के अंदर लंबे operations चलते रहें, तो उन systems में भी excessive latency हो सकती है जहां minimum latency सर्वोच्च प्राथमिकता नहीं है
  • इससे बचने के लिए लंबे समय तक चलने वाले loops में जगह-जगह cond_resched() calls जोड़ी गईं
    • हर call एक अतिरिक्त voluntary preemption point है
    • यह PREEMPT_NONE mode में भी काम करता है
    • kernel में ऐसी सैकड़ों calls हैं
  • यह तरीका एक heuristic है जो सिर्फ उन locations पर काम करता है जहां developers ने इसे डाला है
    • अनावश्यक calls हो सकती हैं
    • जहां call जरूरी है, वहां missing भी हो सकती है
    • scheduling decisions पूरे kernel code में फैले हुए structure में बदल जाते हैं

lazy preemption का मुख्य व्यवहार

  • kernel यह तय करते समय कई variables को साथ में देखता है कि मौजूदा task preempt किया जा सकता है या नहीं
  • उनमें TIF_NEED_RESCHED ऐसा flag है जो बताता है कि कोई ज्यादा priority वाला task CPU access का इंतजार कर रहा है
    • जब higher-priority task wake up होता है, तो currently running task पर यह flag set किया जा सकता है
    • अगर यह flag नहीं है, तो kernel को मौजूदा task को preempt करने की जरूरत नहीं है
  • kernel कई points पर TIF_NEED_RESCHED check करके मौजूदा task को preempt कर सकता है
    • scheduler का timer tick
    • system call के बाद user space में वापस लौटते समय
    • interrupt handler पूरा होने के समय
    • cond_resched() call
  • lazy preemption patch नया flag TIF_NEED_RESCHED_LAZY जोड़ता है
    • इसका मतलब है कि rescheduling की जरूरत है, लेकिन उसे जरूरी तौर पर तुरंत चलाने की जरूरत नहीं है
    • PREEMPT_LAZY mode में अधिकतर events TIF_NEED_RESCHED के बजाय यह नया flag set करते हैं
  • kernel से user space में लौटने वाले points पर, दोनों flags में से कोई भी set हो तो scheduler call होती है
  • voluntary preemption points और interrupt return path में सिर्फ TIF_NEED_RESCHED check किया जाता है

PREEMPT_LAZY से बनने वाला trade-off

  • PREEMPT_LAZY में kernel के अंदर अधिकतर events मौजूदा task को तुरंत preempt नहीं करते
  • इसके बजाय timer tick handler check करता है कि TIF_NEED_RESCHED_LAZY set है या नहीं
    • अगर set है, तो TIF_NEED_RESCHED भी set किया जाता है
    • इसके परिणामस्वरूप चल रहा task preempt किया जा सकता है
  • tasks आम तौर पर, जब तक वे voluntarily CPU नहीं छोड़ते, अपने time slice के करीब अवधि तक चलते हैं
    • उम्मीद है कि यह व्यवहार अच्छे throughput की ओर ले जाएगा
  • इस बदलाव से PREEMPT_LAZY भी PREEMPT_FULL की तरह लगभग हमेशा kernel preemption enabled स्थिति में चल सकता है
    • preemption counter अनुमति दे तो कभी भी preemption संभव है
    • अगर अन्य conditions रोकती नहीं हैं, तो लंबे समय तक चलने वाला kernel code भी preempt किया जा सकता है
  • जहां immediate preemption वास्तव में जरूरी है, वहां delay नहीं किया जाता
    • उदाहरण के लिए, अगर interrupt handling के परिणामस्वरूप real-time task runnable हो जाता है, तो TIF_NEED_RESCHED set किया जाता है
    • ऐसे में timer tick का इंतजार किए बिना लगभग तुरंत preemption हो जाती है
  • अगर सिर्फ TIF_NEED_RESCHED_LAZY set है, तो preemption नहीं होती
    • इसलिए PREEMPT_LAZY kernel, PREEMPT_FULL kernel की तुलना में running task को preempt करने की संभावना काफी कम रखता है

cond_resched() हटाने तक बाकी काम

  • लंबी अवधि का लक्ष्य non-real-time preemption modes को दो तक घटाना है
    • PREEMPT_LAZY
    • PREEMPT_FULL
  • PREEMPT_LAZY, PREEMPT_NONE और PREEMPT_VOLUNTARY के बीच की जगह लेगा और दोनों को replace करेगा
  • जब preemption लगभग कहीं भी संभव हो जाएगी, तो खास points पर अलग से voluntary preemption points जोड़ने की जरूरत घटेगी
  • फिलहाल cond_resched() calls बनी हुई हैं
    • जब तक PREEMPT_NONE और PREEMPT_VOLUNTARY मौजूद हैं, वे जरूरी हैं
    • lazy preemption को stabilize करते समय problems न हों, इसमें भी वे मदद करती हैं
  • मौजूदा patch set में cond_resched() सिर्फ TIF_NEED_RESCHED check करता है
    • इसके कारण PREEMPT_VOLUNTARY या PREEMPT_NONE में जिन स्थितियों में तुरंत preemption होती, उनमें से काफी cases delay हो सकते हैं
  • Steve Rostedt ने खास तौर पर पूछा कि अगर PREEMPT_VOLUNTARY में cond_resched() अपना पुराना अर्थ बनाए रखे, तो transition आसान हो सकता है या नहीं
  • Thomas Gleixner का मानना है कि सिर्फ TIF_NEED_RESCHED check करने का चुनाव सही है
    • क्योंकि इससे सभी cond_resched() calls की समीक्षा करनी पड़ेगी
    • जिन calls को lazy bit check की जरूरत नहीं है, उन्हें PREEMPT_LAZY लागू होने पर हटाया जा सकता है
    • जिन calls को lazy bit check की जरूरत है, वे बनी रहनी चाहिए
  • Gleixner का अनुमान है कि cond_resched() calls में से 5% से कम को ही TIF_NEED_RESCHED_LAZY check की जरूरत होगी
  • transition पूरा होने तक cond_resched() की सैकड़ों calls की समीक्षा करनी होगी, और अधिकतर को हटाना होगा
  • Ankur Arora का अलग patch set संबंधित details के कुछ हिस्सों को संबोधित करता है
  • व्यापक performance testing भी जरूरी है
    • Mike Galbraith के शुरुआती tests में lazy preemption का throughput PREEMPT_VOLUNTARY से थोड़ा कम रहा

अंतिम लक्ष्य

  • lazy preemption work के परिणामस्वरूप kernel थोड़ा और छोटा और सरल हो सकता है
  • लक्ष्य ऐसा kernel है जो scheduler-related calls को पूरे code में बिखेरने के बिना predictable latency दे सके
  • मौजूदा approach बेहतर solution लगती है, लेकिन उस स्थिति तक पहुंचने में अभी समय लगेगा

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

1 टिप्पणियां

 
GN⁺ 2024-10-20
Hacker News की राय

  • उम्मीद जगाने वाला लगता है। EEVDF की तरह यह मौजूदा स्थिति को सरल बनाते हुए सुधारने की दिशा में है, इसलिए इससे बेहतर करना मुश्किल होगा

  • समझ नहीं आता कि preemption level global mode क्यों है, किसी खास event की property क्यों नहीं। कुछ events को दूसरे events की तुलना में कम latency के साथ handle किया जाना चाहिए

    • event की priority का आकलन करने के लिए पहले CPU time चाहिए। मौजूदा CPU पर चल रहे process को interrupt करने के बाद ही वह आकलन संभव है
      इसलिए किसी event की अधिकतम priority भी इस बात से सीमित होती है कि program को context switch से गुजरने से पहले मिलने वाला time slice कितना छोटा हो सकता है। किसी भी तरह के event पर कम latency के साथ भरोसेमंद ढंग से react करने के लिए, सभी CPU-intensive programs को उस event के बहुत दुर्लभ होने पर भी हमेशा performance cost चुकानी पड़ेगी
    • यहां दो concepts हैं जिनमें आसानी से confusion हो सकता है। एक है कि process को कब preempt किया जा सकता है, और दूसरा है कि असल में preempt किया जाएगा या नहीं
      संभावित preemption points scheduler की property हैं, और यहां global mode के रूप में इसी पर चर्चा हो रही है। preemption points बढ़ने से स्वाभाविक रूप से process के असुविधाजनक समय पर preempt होने की संभावना बढ़ती है, लेकिन साथ ही priority को सही ढंग से reflect करने के मौके भी बढ़ते हैं। सवाल में जिस preemption level की बात है, यानी scheduler द्वारा दी जाने वाली priority, वह सचमुच process की property है और उसे configure भी किया जा सकता है। Linux का default scheduler भी priority वाले processes को ज्यादा time slice देता है और दूसरे processes को कम preempt करने की कोशिश करता है
    • लेख में बताया गया PREEMPT_VOLUNTARY कुछ हद तक उसी दिशा की कोशिश था, और अब इसे हटाया जा रहा है ऐसा माना जा सकता है
    • यह patch कुछ हद तक वही भूमिका निभाता है। https://lwn.net/ml/all/20241008144829.GG14587@noisy.programm... के अनुसार:
      SCHED_IDLE, SCHED_BATCH, SCHED_NORMAL/OTHER delayed preemption का उपयोग करते हैं, और FIFO, RR, DEADLINE पुराने Full behavior का उपयोग करते हैं
    • ऐसी system में programs के बीच खुद को महत्वपूर्ण बताकर priority मांगने की होड़ पैदा होने की संभावना काफी है। व्यवहार में बड़ी कंपनियों द्वारा “बेहतर” user experience के लिए इसका इस्तेमाल किए जाने की संभावना ज्यादा है
      इसलिए चल रही applications की संख्या कम से कम रखना, या ज्यादातर users को प्रभावित करने वाले छोटे-छोटे पलों को manually control करना महत्वपूर्ण है। CPU-intensive काम भी कई बार सचमुच efficient resource use से ज्यादा खराब code होने की संभावना रखता है। games में performance को priority देनी चाहिए, लेकिन multitasking के लिए system को ठप कर देने से बचाने वाला नाज़ुक balance चाहिए। वैसे भी यह मुख्य रूप से idle tasks के लिए है, इसलिए user को script में कई actions toggle करने के लिए simple commands देने से ज्यादा automation की जरूरत बहुत अधिक नहीं लगती

  • कहा गया है कि “मौजूदा kernel में चार modes हैं जो यह control करते हैं कि एक task को दूसरे task के लिए कब preempt किया जा सकता है”; जानना चाहता हूं कि यह kernel tasks के बारे में है या user tasks भी इसमें शामिल हैं

    • यह kernel code के बारे में है। user-space code हमेशा preemptible होता है

  • linked thread में जहां patch आया है, वहां numbers नहीं मिले। लगता है इस बदलाव की real-world potential दिखाने वाले कुछ initial benchmarks तो पहले से होने चाहिए थे, इसलिए उत्सुक हूं

    • लेख के अंत से दूसरे paragraph में है
      कहा गया है कि व्यापक performance testing की जरूरत है, Mike Galbraith ने शुरुआती काम शुरू किया है, और results में दिखा कि delayed preemption का throughput PREEMPT_VOLUNTARY से थोड़ा कम है
    • सोच रहा हूं कि ऐसी चीजों को benchmark कैसे किया जाना चाहिए। क्या कई processes को साथ चलाकर total run time के आधार पर sort करना चाहिए, या individual processes की latency measure करनी चाहिए

  • सोच रहा हूं कि scheduler kernel के बाकी code से कितना tightly coupled है
    उदाहरण के लिए, अगर scientific computing applications के लिए scheduler को काफी सरल बनाना चाहें जिन्हें preemption की बिल्कुल परवाह नहीं, तो क्या यह साफ और modular तरीके से संभव होगा? क्या सच में इसका फायदा भी होगा

    • अगर आप preemption को जितना हो सके घटाकर processes के एक set को चलाना चाहते हैं, जैसे HPC environment में, तो कुछ cores को isolated CPUs के रूप में set करके reboot करना और फिर taskset से jobs को सीधे वहां डालना सबसे मजबूत तरीका है
      हालांकि तब आपको jobs को सचमुच manually CPUs पर assign करना होगा, और सभी jobs के गलत CPU पर चढ़ जाने की स्थिति भी आसानी से बन सकती है। standard तरीका interrupt mask set करना है ताकि interrupts “work” CPUs पर न जाएं, और cpuset का उपयोग करके सिर्फ खास cgroup को दिए गए cpuset में चलने देना है
    • बहुत कम daemons वाले clean system पर, application को प्रति CPU thread एक operating-system thread के हिसाब से set करके और CPU pinning लगाकर उसे move न होने दें, तो लगभग 95% तक पहुंचा जा सकता है
      run list बहुत छोटी हो जाती है, इसलिए scheduler जो भी करे उसका असर काफी कम होगा। अगर application बहुत ज्यादा I/O नहीं करती तो interrupts भी ज्यादा नहीं होंगे। अगर tickless kernel इस्तेमाल कर सकें—आजकल यह अलग option है या default, पता नहीं—तो लंबे समय तक interrupts लगभग न के बराबर हो सकते हैं
    • आखिरी बार जब देखा था, तो यह surprisingly अच्छी तरह अलग किया हुआ था
      लेकिन इसे बहुत सरल बनाने की वजह bugs से बचना होगी, न कि अच्छी तरह configured default scheduler की तुलना में बहुत performance पाना। settings बहुत हैं, लेकिन उस तरफ bugs भी ज्यादा नहीं थे। भोलेपन से simplify करने पर अक्सर performance पाने के बजाय खोनी पड़ती है। अगर non-interactive system चला रहे हैं, तो सबसे आसान बदलाव process time quantum बढ़ाना है
    • मैं तो बस RT Linux इस्तेमाल करूंगा। इसका अपना basic scheduler होता है और kernel scheduler idle task के रूप में चलता है, जबकि real-time tasks की priority बाकी सब से ऊपर होती है