เส้นทางอันยาวไกลสู่การทำ “lazy preemption” ใน Linux CPU scheduler

 (lwn.net)
3 คะแนน โดย GN⁺ 2024-10-20 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • เคอร์เนล Linux ยังคงมี โหมด preemption หลายแบบเพื่อประนีประนอมระหว่าง throughput กับเวลาตอบสนอง และแพตช์ชุดใหม่ของ Peter Zijlstra ทำให้การถกเถียงเรื่อง lazy preemption (PREEMPT_LAZY) กลับมาจริงจังอีกครั้ง
  • PREEMPT_NONE, PREEMPT_VOLUNTARY, PREEMPT_FULL, PREEMPT_RT ที่มีอยู่เดิมมีขอบเขตการอนุญาตให้ preempt ต่างกัน ยิ่ง preempt บ่อย เวลาตอบสนองอาจดีขึ้น แต่ภาระต่อ throughput และการแย่ง lock ก็เพิ่มขึ้น
  • PREEMPT_LAZY ใช้แฟล็ก TIF_NEED_RESCHED_LAZY เพื่อระบุว่า “จำเป็นต้อง reschedule แต่ไม่ต้องทันที” และเลื่อน preemption ส่วนใหญ่ไปจนถึง timer tick
  • ในระยะยาว มีแนวทางจะลดโหมด preemption ที่ไม่ใช่ real-time เหลือ PREEMPT_LAZY กับ PREEMPT_FULL และลบ การเรียก cond_resched() ส่วนใหญ่ออกจากทั่วเคอร์เนล
  • แพตช์ชุดปัจจุบันยังต้องการการทำให้เสถียร การตรวจสอบจุดที่เรียกใช้ และการทดสอบประสิทธิภาพเพิ่มเติม โดยในการทดสอบช่วงแรก throughput ของ PREEMPT_LAZY ยังด้อยกว่า PREEMPT_VOLUNTARY เล็กน้อย

โหมด preemption เดิมของเคอร์เนล Linux

  • เคอร์เนลปัจจุบันมี โหมด preemption หลายแบบเพื่อควบคุมว่างานที่กำลังรันอยู่สามารถถูกงานอื่น preempt ได้เมื่อใด
    • PREEMPT_NONE: โหมดที่เรียบง่ายที่สุด อนุญาตให้ preempt เฉพาะเมื่องานที่กำลังรันใช้ time slice จนหมดแล้ว
    • PREEMPT_VOLUNTARY: โหมดที่เพิ่มจุดจำนวนมากภายในเคอร์เนลให้สามารถ preempt ได้เมื่อจำเป็น
    • PREEMPT_FULL: โหมดที่อนุญาตให้ preempt ได้เกือบทุกจุด ยกเว้นช่วงที่เคอร์เนลป้องกันไว้ เช่น ขณะถือ spinlock
    • PREEMPT_RT: โหมดที่ให้ความสำคัญกับ preemption เหนือสิ่งอื่นเกือบทั้งหมด และทำให้โค้ดที่ถือ spinlock ส่วนใหญ่ก็สามารถถูก preempt ได้
  • ระดับ preemption ที่สูงขึ้นช่วยให้ตอบสนองต่อเหตุการณ์ต่าง ๆ ได้เร็วขึ้น เช่น การขยับเมาส์ หรือสัญญาณความผิดปกติที่กำลังใกล้เข้ามาในเครื่องปฏิกรณ์
  • แต่เมื่อ preempt บ่อยขึ้น throughput โดยรวม ของงานที่ใช้ CPU หนักและรันนานอาจลดลง และการแย่ง lock ก็อาจเพิ่มขึ้น
  • ดิสโทรจำนวนมาก build เคอร์เนลด้วยโหมดเสมือน PREEMPT_DYNAMIC
    • สามารถเลือกหนึ่งในสามโหมดที่ไม่ใช่ real-time ข้างต้นได้ตอนบูต
    • ค่าเริ่มต้นคือ PREEMPT_VOLUNTARY
    • ในระบบที่ mount debugfs ไว้ สามารถดูโหมดปัจจุบันได้ที่ /sys/kernel/debug/sched/preempt

เหตุผลที่เคยต้องมี cond_resched()

  • PREEMPT_NONE และ PREEMPT_VOLUNTARY ไม่อนุญาตให้ preempt แบบสุ่มขณะรันโค้ดเคอร์เนล
  • หากมีงานยาว ๆ ต่อเนื่องภายในเคอร์เนล แม้ในระบบที่ latency ต่ำสุดไม่ใช่สิ่งสำคัญอันดับแรก ก็อาจเกิด ความหน่วงมากเกินไป ได้
  • เพื่อหลีกเลี่ยงสิ่งนี้ จึงมีการเพิ่มการเรียก cond_resched() ไว้ตามจุดต่าง ๆ ในลูปที่รันนาน
    • การเรียกแต่ละครั้งเป็นจุด voluntary preemption เพิ่มเติม
    • ทำงานได้แม้ในโหมด PREEMPT_NONE
    • ในเคอร์เนลมีการเรียกแบบนี้อยู่หลายร้อยจุด
  • วิธีนี้เป็น heuristic ที่ทำงานเฉพาะตำแหน่งที่นักพัฒนาใส่ไว้
    • อาจมีการเรียกที่ไม่จำเป็น
    • อาจไม่มีการเรียกในจุดที่จำเป็น
    • ทำให้การตัดสินใจด้าน scheduling กระจายไปทั่วโค้ดเคอร์เนล

กลไกหลักของ lazy preemption

  • เมื่อเคอร์เนลตัดสินว่างานปัจจุบันสามารถถูก preempt ได้หรือไม่ จะดูตัวแปรหลายตัวร่วมกัน
  • หนึ่งในนั้นคือ TIF_NEED_RESCHED ซึ่งเป็นแฟล็กที่บอกว่างานที่มี priority สูงกว่ากำลังรอใช้ CPU
    • เมื่องาน priority สูงตื่นขึ้นมา แฟล็กนี้อาจถูกตั้งบนงานที่กำลังรันอยู่
    • หากไม่มีแฟล็กนี้ เคอร์เนลก็ไม่จำเป็นต้อง preempt งานปัจจุบัน
  • เคอร์เนลสามารถตรวจสอบ TIF_NEED_RESCHED ได้ในหลายจุดเพื่อ preempt งานปัจจุบัน
    • timer tick ของ scheduler
    • ตอนกลับสู่ user space หลัง system call
    • ตอนจบ interrupt handler
    • การเรียก cond_resched()
  • แพตช์ lazy preemption เพิ่มแฟล็กใหม่ TIF_NEED_RESCHED_LAZY
    • หมายถึงจำเป็นต้อง reschedule แต่ไม่จำเป็นต้องทำทันที
    • ในโหมด PREEMPT_LAZY เหตุการณ์ส่วนใหญ่จะตั้งแฟล็กใหม่นี้แทน TIF_NEED_RESCHED
  • ณ จุดที่กลับจากเคอร์เนลไปยัง user space หากมีการตั้งแฟล็กใดแฟล็กหนึ่งในสองแฟล็กนี้ ก็จะนำไปสู่การเรียก scheduler
  • ส่วนจุด voluntary preemption และเส้นทางกลับจาก interrupt จะตรวจสอบเฉพาะ TIF_NEED_RESCHED

การประนีประนอมที่ PREEMPT_LAZY สร้างขึ้น

  • ใน PREEMPT_LAZY เหตุการณ์ส่วนใหญ่ภายในเคอร์เนลจะไม่ preempt งานปัจจุบันทันที
  • แต่ timer tick handler จะตรวจสอบว่า TIF_NEED_RESCHED_LAZY ถูกตั้งไว้หรือไม่
    • หากถูกตั้งไว้ ก็จะตั้ง TIF_NEED_RESCHED ด้วย
    • ผลคือ งานที่กำลังรันอยู่อาจถูก preempt ได้
  • โดยทั่วไป งานจะรันต่อไปเป็นเวลาที่ใกล้เคียงกับ time slice ของตัวเอง เว้นแต่จะยอมสละ CPU โดยสมัครใจ
    • คาดว่าพฤติกรรมนี้จะนำไปสู่ throughput ที่ดี
  • ด้วยการเปลี่ยนแปลงนี้ PREEMPT_LAZY ก็สามารถรันในสภาพที่ kernel preemption เปิดใช้งานอยู่แทบตลอดเวลาได้เหมือน PREEMPT_FULL
    • เมื่อ preemption counter อนุญาต ก็สามารถ preempt ได้ทุกเมื่อ
    • หากไม่มีเงื่อนไขอื่นมาขวาง โค้ดเคอร์เนลที่รันนานก็สามารถถูก preempt ได้เช่นกัน
  • ในกรณีที่จำเป็นต้อง preempt ทันทีจริง ๆ ก็จะไม่หน่วงไว้
    • เช่น หากผลจากการประมวลผล interrupt ทำให้งาน real-time พร้อมรัน ก็จะตั้ง TIF_NEED_RESCHED
    • กรณีนี้จะนำไปสู่การ preempt แทบจะทันทีโดยไม่รอ timer tick
  • หากมีเพียง TIF_NEED_RESCHED_LAZY ถูกตั้งไว้ จะไม่เกิด preemption
    • ดังนั้นเคอร์เนล PREEMPT_LAZY จึงมีโอกาส preempt งานที่กำลังรันอยู่น้อยกว่าเคอร์เนล PREEMPT_FULL มาก

งานที่ยังเหลือก่อนลบ cond_resched()

  • เป้าหมายระยะยาวคือการลดโหมด preemption ที่ไม่ใช่ real-time ให้เหลือ สองแบบ
    • PREEMPT_LAZY
    • PREEMPT_FULL
  • PREEMPT_LAZY จะอยู่ตรงกลางระหว่าง PREEMPT_NONE กับ PREEMPT_VOLUNTARY และมีแผนจะมาแทนที่ทั้งสอง
  • เมื่อ preemption ทำได้แทบทุกที่ ความจำเป็นในการเพิ่มจุด voluntary preemption เฉพาะตำแหน่งก็ลดลง
  • ปัจจุบันยังคงมีการเรียก cond_resched() อยู่
    • ยังจำเป็นตราบใดที่ PREEMPT_NONE และ PREEMPT_VOLUNTARY ยังมีอยู่
    • ยังช่วยป้องกันไม่ให้เกิดปัญหาระหว่างการทำให้ lazy preemption เสถียร
  • ในแพตช์ชุดปัจจุบัน cond_resched() ตรวจสอบเฉพาะ TIF_NEED_RESCHED
    • ด้วยเหตุนี้ สถานการณ์จำนวนมากที่ใน PREEMPT_VOLUNTARY หรือ PREEMPT_NONE จะถูก preempt ทันที อาจถูกหน่วงออกไป
  • Steve Rostedt ถามเป็นพิเศษว่า หาก cond_resched() ยังคงความหมายเดิมไว้ใน PREEMPT_VOLUNTARY จะช่วยให้การเปลี่ยนผ่านง่ายขึ้นหรือไม่
  • Thomas Gleixner เห็นว่าการเลือกตรวจสอบเฉพาะ TIF_NEED_RESCHED เป็นสิ่งที่ถูกต้อง
    • เพราะทำให้ต้องตรวจสอบการเรียก cond_resched() ทั้งหมด
    • การเรียกที่ไม่จำเป็นต้องตรวจสอบ lazy bit สามารถถูกลบออกได้เมื่อใช้ PREEMPT_LAZY
    • การเรียกที่จำเป็นต้องตรวจสอบ lazy bit ต้องคงไว้
  • Gleixner คาดว่าในบรรดาการเรียก cond_resched() ทั้งหมด จะมี น้อยกว่า 5% ที่ต้องตรวจสอบ TIF_NEED_RESCHED_LAZY
  • ก่อนการเปลี่ยนผ่านจะเสร็จสมบูรณ์ จำเป็นต้องตรวจสอบการเรียก cond_resched() หลายร้อยจุด และส่วนใหญ่ควรถูกลบออก
  • แพตช์ชุดแยกของ Ankur Arora จัดการรายละเอียดบางส่วนที่เกี่ยวข้อง
  • ยังต้องมีการทดสอบประสิทธิภาพในวงกว้างด้วย
    • ในการทดสอบช่วงแรกของ Mike Galbraith throughput ของ lazy preemption ยังด้อยกว่า PREEMPT_VOLUNTARY เล็กน้อย

เป้าหมายสุดท้าย

  • ผลจากงาน lazy preemption อาจทำให้เคอร์เนล เล็กลงและเรียบง่ายขึ้น อีกเล็กน้อย
  • เป้าหมายคือเคอร์เนลที่ให้ latency คาดการณ์ได้ โดยไม่ต้องกระจายการเรียกที่เกี่ยวกับ scheduler ไปทั่วโค้ด
  • แนวทางปัจจุบันดูเหมือนเป็นทางออกที่ดีกว่า แต่ยังต้องใช้เวลาอีกระยะกว่าจะไปถึงสภาพนั้น

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-10-20
ความคิดเห็นจาก Hacker News

  • ดูมีแววดี เป็นแนวทางที่ปรับปรุงไปพร้อมกับทำให้สถานะปัจจุบันเรียบง่ายขึ้นเหมือน EEVDF คงยากที่จะดีกว่านี้

  • สงสัยว่าทำไม ระดับการ preemption ถึงไม่ใช่คุณสมบัติของเหตุการณ์เฉพาะ แทนที่จะเป็นโหมดแบบ global เหตุการณ์บางอย่างควรถูกจัดการด้วย latency ที่ต่ำกว่าเหตุการณ์อื่น

    • หากจะประเมิน priority ของเหตุการณ์ ก็ต้องมี เวลา CPU ก่อน การประเมินนั้นทำได้ก็ต่อเมื่อ interrupt โปรเซสที่กำลังรันอยู่บน CPU ปัจจุบันแล้วเท่านั้น
      ดังนั้น priority สูงสุดที่เหตุการณ์หนึ่งจะมีได้ ก็ถูกจำกัดด้วย time slice ที่สั้นแค่ไหนที่โปรแกรมจะได้รับก่อนจะผ่าน context switch หากต้องการตอบสนองต่อเหตุการณ์ชนิดใดก็ตามด้วย latency ต่ำอย่างเสถียร โปรแกรมที่กิน CPU หนักทุกตัวก็ต้องจ่ายต้นทุนด้านประสิทธิภาพเสมอ ไม่ว่าเหตุการณ์นั้นจะเกิดขึ้นนาน ๆ ครั้งแค่ไหนก็ตาม
    • ตรงนี้มีสองแนวคิดที่สับสนกันได้ง่าย แนวคิดหนึ่งคือจุดที่โปรเซส สามารถถูก preempt ได้ และอีกแนวคิดคือจะถูก preempt จริงหรือไม่
      จุด preemption ที่เป็นไปได้เป็นคุณสมบัติของ scheduler และสิ่งที่พูดถึงในที่นี้ในฐานะโหมด global ก็คือเรื่องนี้ ยิ่งมีจุด preemption มากขึ้น ก็ย่อมเพิ่มโอกาสที่โปรเซสจะถูก preempt ในจังหวะที่ไม่สะดวก แต่ในขณะเดียวกันก็เพิ่มโอกาสที่จะสะท้อน priority ได้อย่างถูกต้องด้วย ระดับการ preemption ที่คำถามพูดถึง หรือก็คือ priority ที่ scheduler มอบให้นั้น เป็นคุณสมบัติของโปรเซสจริง และสามารถตั้งค่าได้ scheduler พื้นฐานของ Linux ก็ให้ time slice มากขึ้นแก่โปรเซสที่มี priority และพยายาม preempt โปรเซสอื่นให้น้อยลง
    • PREEMPT_VOLUNTARY ที่บทความอธิบายไว้ก็เป็นความพยายามไปในทิศทางนั้นอยู่พอสมควร และตอนนี้อาจมองได้ว่ากำลังถูกเลิกใช้
    • แพตช์นี้ทำหน้าที่แบบนั้นอยู่ระดับหนึ่ง ตามที่ https://lwn.net/ml/all/20241008144829.GG14587@noisy.programm... ระบุไว้:
      SCHED_IDLE, SCHED_BATCH, SCHED_NORMAL/OTHER ใช้ delayed preemption ส่วน FIFO, RR, DEADLINE ใช้พฤติกรรมแบบ Full เดิม
    • ระบบแบบนั้นมีแนวโน้มจะสร้างการแย่งกันระหว่างโปรแกรมที่ต่างก็อ้างว่าตัวเองสำคัญและเรียกร้อง priority ในทางปฏิบัติ บริษัทใหญ่ ๆ น่าจะนำไปใช้เพื่อประสบการณ์ผู้ใช้ที่ “ดีกว่า”
      ดังนั้นการลดจำนวนแอปพลิเคชันที่กำลังรันให้น้อยที่สุด หรือควบคุมด้วยมือสำหรับช่วงเวลาสั้น ๆ ที่ผู้ใช้ส่วนใหญ่เจอ จึงสำคัญกว่า บางครั้งงานที่กิน CPU หนักก็มีแนวโน้มจะเป็นโค้ดแย่มากกว่าการใช้ทรัพยากรอย่างมีประสิทธิภาพจริง ๆ ในเกมควรให้ความสำคัญกับประสิทธิภาพ แต่ก็ต้องมีสมดุลที่ละเอียดอ่อน ไม่ให้ระบบหยุดชะงักเพื่อรองรับ multitasking อย่างไรก็ตาม เรื่องนี้โดยหลักแล้วมีไว้สำหรับงาน idle จึงดูไม่จำเป็นต้อง automate มากไปกว่าการมีคำสั่งง่าย ๆ ให้ผู้ใช้ toggle การทำงานหลายอย่างจากสคริปต์ได้

  • ที่บอกว่า “ในเคอร์เนลปัจจุบันมีสี่โหมดที่ควบคุมได้ว่างานหนึ่งจะถูก preempt เพื่อให้อีกงานหนึ่งได้เมื่อใด” สงสัยว่านี่หมายถึง งานในเคอร์เนล หรือรวมงานฝั่งผู้ใช้ด้วย

    • พูดถึงโค้ดในเคอร์เนล โค้ดใน user space สามารถถูก preempt ได้เสมอ

  • หาเลขจากเธรดที่ลิงก์ซึ่งมีการส่งแพตช์ไม่เจอ น่าจะมี benchmark เบื้องต้น ที่แสดงศักยภาพในโลกจริงของการเปลี่ยนแปลงนี้แล้วบ้าง เลยสงสัย

    • อยู่ในย่อหน้าก่อนสุดท้ายของบทความ
      บอกว่าจำเป็นต้องมีการทดสอบประสิทธิภาพอย่างกว้างขวาง และ Mike Galbraith ได้เริ่มงานเบื้องต้นแล้ว โดยผลลัพธ์แสดงว่า throughput ของ delayed preemption ต่ำกว่า PREEMPT_VOLUNTARY เล็กน้อย
    • สงสัยว่าของแบบนี้ควร benchmark อย่างไร รันหลายโปรเซสพร้อมกันแล้วเรียงตามเวลารันรวม หรือควรวัด เวลาในการรอ ของแต่ละโปรเซส

  • สงสัยว่า scheduler ผูกกับโค้ดส่วนที่เหลือของเคอร์เนลแน่นแค่ไหน
    เช่น ถ้าอยากทำให้ scheduler เรียบง่ายลงมากสำหรับแอปพลิเคชันคำนวณเชิงวิทยาศาสตร์ที่ไม่สนใจ preemption เลย จะทำได้แบบสะอาดและเป็นโมดูลไหม และจะมีประโยชน์จริงหรือไม่

    • หากต้องการรันชุดโปรเซสโดยลด preemption ให้มากที่สุด เช่นในสภาพแวดล้อม HPC วิธีที่แรงที่สุดคือกำหนดบางคอร์ให้เป็น CPU ที่แยกไว้ แล้วรีบูต จากนั้นใช้ taskset ส่งงานขึ้นไปที่นั่นโดยตรง
      แต่เมื่อทำแบบนั้นก็ต้องกำหนดงานให้กับ CPU ด้วยมือจริง ๆ และเกิดกรณีที่งานทั้งหมดไปอยู่บน CPU ผิดตัวได้ง่าย วิธีมาตรฐานคือกำหนด interrupt mask เพื่อไม่ให้ interrupt ไปยัง CPU สำหรับ “งาน” และใช้ cpuset เพื่อให้เฉพาะ cgroup บางตัวเท่านั้นที่รันใน cpuset ที่กำหนด
    • บนระบบสะอาดที่แทบไม่มี daemon หากทำให้แอปพลิเคชันมีเธรดของระบบปฏิบัติการหนึ่งตัวต่อ CPU thread และทำ CPU pinning ไม่ให้ย้ายไปมา ก็น่าจะไปถึงได้ราว 95%
      เพราะ run list จะสั้นมาก ไม่ว่า scheduler จะทำอะไร ผลกระทบก็คงค่อนข้างเล็ก ถ้าแอปพลิเคชันไม่ได้ทำ I/O มาก ก็จะไม่มี interrupt มากนัก หากใช้เคอร์เนลแบบ tickless ได้ ซึ่งทุกวันนี้ไม่แน่ใจว่ายังเป็นตัวเลือกแยกหรือเป็นค่าเริ่มต้นแล้ว ก็อาจแทบไม่มี interrupt เป็นเวลานาน
    • ครั้งสุดท้ายที่ดู มันถูกแยกออกมาดีอย่างน่าประหลาดใจ
      แต่เหตุผลที่จะทำให้เรียบง่ายลงมาก ๆ คือเพื่อหลีกเลี่ยงบั๊ก ไม่ใช่เพราะจะได้ประสิทธิภาพเพิ่มมากเมื่อเทียบกับ scheduler พื้นฐานที่ตั้งค่าดีแล้ว มีการตั้งค่าเยอะก็จริง แต่ฝั่งนั้นก็ไม่ได้มีบั๊กมากนัก ถ้าทำให้เรียบง่ายแบบตรงไปตรงมา ส่วนใหญ่จะเสียประสิทธิภาพมากกว่าได้ หากรันระบบที่ไม่ใช่ interactive การเปลี่ยนที่ง่ายที่สุดคือเพิ่ม โควตาเวลา ของโปรเซส
    • ผมคงใช้ RT Linux ไปเลย มันมี scheduler พื้นฐานของตัวเอง และ kernel scheduler จะรันเป็นงาน idle โดยงาน real-time มี priority เหนือทุกอย่าง