ถ้าไม่มี futex ก็ไม่มีความหมาย

 (h4x0r.org)
4 คะแนน โดย GN⁺ 2025-08-21 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • มีการตั้งข้อสังเกตว่าเป็นเรื่องน่าเสียดายที่ตำรา The Art of Multiprocessor Programming ไม่กล่าวถึงแนวคิด futex
  • Futex เป็นองค์ประกอบหลักของ การซิงโครไนซ์ที่มีประสิทธิภาพ ในการเขียนโปรแกรมแบบขนานสมัยใหม่ และให้ประสิทธิภาพดีกว่าล็อกแบบ System V เดิม
  • futex มีโครงสร้างที่ แยกการได้มาของล็อกออกจากการรอ/การปลุก เพื่อลด system call และ overhead ที่ไม่จำเป็น
  • มีตัวอย่างและคำอธิบายเทคนิคในการนำ futex ไปใช้สร้าง concurrency primitives หลากหลายแบบด้วยตนเอง เช่น spinlock, mutex, และ recursive lock
  • ผู้เขียนชี้ว่าหนังสือไม่ได้ครอบคลุม วิธีการซิงโครไนซ์สมัยใหม่ที่จำเป็นต่อการทำงานวิศวกรรมจริง สะท้อนช่องว่างระหว่างแวดวงวิชาการกับภาคปฏิบัติ

บทนำ

  • Phil Eaton เริ่มต้นชมรมอ่านหนังสือ 'The Art of Multiprocessor Programming, 2nd Edition'
  • แม้หนังสือเล่มนี้จะถูกมองว่าเป็นตำราทรงอิทธิพลในด้านการเขียนโปรแกรมแบบขนาน แต่ผู้เขียนชี้ถึง การขาดความเป็นประโยชน์เชิงปฏิบัติ ของเนื้อหา
  • โดยเฉพาะอย่างยิ่ง หนังสือระบุว่ามุ่งเป้าไปที่นักศึกษาปริญญาตรีปี 4 และนักศึกษาบัณฑิตศึกษา แต่กลับไม่กล่าวถึง futex ซึ่งเป็น เทคนิคการซิงโครไนซ์หลัก

futex คืออะไร – ทำไมจึงสำคัญ

  • futex ย่อมาจาก “fast user space mutex” แต่ในความเป็นจริงแล้วมันไม่ใช่ mutex โดยตรง หากเป็น primitive สำหรับการซิงโครไนซ์ที่ระบบปฏิบัติการสนับสนุน เพื่อใช้สร้างล็อกสมัยใหม่
  • ในอดีต ล็อกส่วนใหญ่สร้างบน semaphore ของ System V IPC ทำให้มี ข้อจำกัดด้านประสิทธิภาพและการขยายตัว
  • เมื่อ Linux นำ futex มาใช้ในปี 2002 ก็แสดงให้เห็นว่า เร็วกว่า System V lock ถึง 20~120 เท่าในสภาพแวดล้อมที่มีงานพร้อมกัน 1000 งาน
  • ระบบปฏิบัติการอื่นอย่าง Windows (ปี 2012) และ macOS (ปี 2016) ก็ได้นำกลไกคล้ายกันมาใช้
  • ปัจจุบัน ล็อกใน system library ที่ใช้งานแพร่หลายอย่าง pthreads ก็ใช้ futex

หลักการทำงานและจุดแตกต่างของ futex

  • semaphore แบบเดิมผูกการล็อกเข้ากับการรอ แต่ futex แยกการได้มาของล็อกออกจากการรอ/การปลุก
  • ด้วยเหตุนี้จึงลด ดีเลย์และ system call ที่ไม่จำเป็น ได้ และหากมั่นใจว่าไม่มีเธรดที่รออยู่ในตอนปลดล็อก ก็ไม่จำเป็นต้องเข้าสู่เคอร์เนล
  • การเรียก wait ของ futex จะทำให้ “รอเฉพาะเมื่อค่าที่ address หน่วยความจำหนึ่งอยู่ในสถานะที่ต้องการเท่านั้น” และยังรองรับ timeout
  • การเรียก wake ของ futex จะปลุกจำนวนเธรดตามต้องการจากรายการรอภายในที่ผูกกับ address หน่วยความจำหนึ่ง
  • มัน กำหนดให้ตรวจสอบค่าจริงของ address หน่วยความจำ เพื่อลดการรอที่ไม่จำเป็นเมื่อสถานะเปลี่ยนไปแล้ว

การใช้งาน futex ในทางปฏิบัติ – ลงมือสร้างเอง

  • futex เป็น primitive ระดับล่าง ดังนั้นจึงต้องใช้ชนิดข้อมูล atomic โดยคำนึงถึง ประเด็นลำดับการทำงานของหน่วยความจำจากคอมไพเลอร์และฮาร์ดแวร์
  • บน Linux ต้องเรียก futex system call โดยตรงผ่าน syscall ส่วนบน macOS ใช้อินเทอร์เฟซ __ulock (ปัจจุบันมี API ที่ใช้ง่ายกว่านี้เพิ่มเข้ามาแล้ว)
  • โดยพื้นฐานแล้ว การรอด้วย futex จะคืนค่า 0 เมื่อสำเร็จ และคืน error code เมื่อไม่สำเร็จ เช่น timeout
  • โอเปอเรชันหลักที่อิงกับ futex:
    • h4x0r_futex_wait_timespec() : รอเมื่อค่าที่คาดไว้ตรงกัน และสามารถกำหนด timeout ได้
    • h4x0r_futex_wake() : ปลุกผู้รอ 1 รายหรือทั้งหมด

ตัวอย่างใช้งานจริงของการสร้าง mutex/spinlock/recursive lock

spinlock

  • ล็อกแบบพื้นฐานที่สุด ทำงานด้วย บิตเดียว (atomic_fetch_or)
  • จะวนลูปไม่สิ้นสุด (“spin”) จนกว่าจะได้ล็อก แต่ในกรณีที่มีการแข่งขันสูงจะเกิด การสิ้นเปลือง CPU และยังมีปัญหาเชิงโครงสร้าง เช่น ปลดล็อกผิด และเสี่ยง deadlock เมื่อเรียกซ้ำแบบ recursive

hybrid mutex (‘unsafe’ mutex)

  • โดยทั่วไปจะ ลองด้วย spinlock ก่อน และหากล้มเหลวจำนวนหนึ่งครั้งจึงสลับไปใช้ futex เพื่อบล็อกอย่างมีประสิทธิภาพ
  • หากไม่มีผู้รอ ก็หลีกเลี่ยง system call ที่ไม่จำเป็นได้ และในกรณีมีผู้รอก็สามารถลดจำนวน wake system call ให้น้อยที่สุด
  • เนื่องจากยังขาดการตรวจสอบ ownership และการจัดการ recursive อย่างเคร่งครัด จึงใช้ชื่อว่า “unsafe”

mutex แบบนับจำนวนผู้รอ

  • ใช้หนึ่งบิตสำหรับสถานะล็อก และใช้บิตที่เหลือสำหรับ นับจำนวนผู้รอ เพื่อลด wake system call ที่ไม่จำเป็น
  • อย่างไรก็ตาม ยังไม่มีการจัดการ ownership และ recursive

mutex ที่รวมการจัดการ ownership

  • ใช้ค่า pthread_t เพื่อ ติดตามเจ้าของล็อกและสถานะได้อย่างชัดเจน ทำให้ตรวจจับปัญหาเมื่อ unlock ผิดหรือใช้งานแบบ recursive ได้
  • ทั้งการได้มาของล็อก การปลดล็อก และการจัดการผู้รอ ล้วนควบคุมด้วย atomic operation อย่างเคร่งครัด

recursive lock

  • เพิ่ม ตัวนับจำนวนการซ้อนกัน (depth) แยกตามเธรด เพื่อให้เธรดเดียวกันสามารถได้ล็อกซ้ำแบบซ้อนได้
  • เมื่อ unlock จะลดค่า depth และเมื่อเป็น 0 จึงปลดล็อกจริงพร้อมปลุกผู้รอ
  • แต่ละการทำงานถูกสร้างขึ้นด้วย atomic operation และการตรวจสอบ ownership อย่างเคร่งครัด

โจทย์ที่ยังเหลือและความเป็นจริงของงานวิศวกรรม

  • หากเธรดเจ้าของล็อกจบการทำงานอย่างผิดปกติหรือหยุดไป จะต้องมี รายการจัดการแยกต่างหาก, callback ตอนสิ้นสุด ฯลฯ เพิ่มเติมเพื่อดูแลล็อก
  • แม้แต่เมื่อใช้ mutex ที่แชร์ข้ามโปรเซส ก็ยังต้องคำนึงถึงการจัดการการเปลี่ยนแปลงสถานะเพิ่มเติม
  • POSIX RW lock ไม่ได้กำหนดพฤติกรรมการซ้อนแบบ recursive ไว้อย่างชัดเจน และยังต่างกันไปในแต่ละ implementation ทำให้รับประกันความปลอดภัยได้ยากในทางปฏิบัติ
  • ผู้เขียนวิจารณ์ว่าหนังสือไม่ได้รวม ประเด็น concurrency ที่สำคัญจริงในการใช้งานจริง (futex, recursive lock, async runtime ฯลฯ) ไว้ในหลักสูตร

บทสรุป

  • 'The Art of Multiprocessor Programming' เอนเอียงไปทางประวัติศาสตร์หรือทฤษฎี จนไม่สามารถถ่ายทอดความรู้ภาคปฏิบัติที่สำคัญของการเขียนโปรแกรมแบบขนานสมัยใหม่ได้อย่างเพียงพอ
  • หากไม่อธิบาย องค์ประกอบการซิงโครไนซ์หลักอย่าง futex ที่ระบบใช้งานจริงอย่างเหมาะสม ก็อาจก่อผลเสียในทางปฏิบัติต่อผู้เรียนรุ่นต่อไป
  • ผู้เขียนเน้นย้ำถึงความจำเป็นในการสะท้อนแนวคิดสมัยใหม่และเสริมเนื้อหาให้ใช้งานได้จริง

เอกสารอ้างอิง

  • ตัวอย่างโค้ดทั้งหมดดูได้ที่ codeberg

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

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

 
GN⁺ 2025-08-21
ความเห็นจาก Hacker News

  • Windows มีฟีเจอร์ชื่อ WaitForMultipleObjects และ Linux ก็ได้นำแนวคิดนี้มาใช้ผ่าน Futex2 ในเวอร์ชัน 5.16 (ปลายปี 2021)
    ลิงก์ที่เกี่ยวข้อง
    ช่วงหลังมานี้ Futex2 ได้รับการปรับปรุงหลายด้าน
    ในที่สุดก็มีการเพิ่มการรองรับ NUMA แล้ว
    ลิงก์เกี่ยวกับ NUMA 1
    ลิงก์เกี่ยวกับ NUMA 2
    NUMA เป็นองค์ประกอบที่สำคัญมากต่อประสิทธิภาพ
    io_uring ถูกนำมาใช้กับ futex ใน 6.7 (ปี 2024) ซึ่งช่วยเพิ่มประสิทธิภาพ AIO ของ postgresql
    บทความที่เกี่ยวข้อง
    ใน 6.7 ยังมีการเพิ่มฟีเจอร์ small requeue และ single wait ด้วย
    ลิงก์ที่เกี่ยวข้อง

    • Windows ไม่ได้เพิ่งเพิ่ม WaitForMultipleObjects แต่มีมาตั้งแต่แรกมากว่า 30 ปีแล้ว
      WaitForMultipleObjects เป็นข้อได้เปรียบของ Windows NT เมื่อเทียบกับ UNIX แต่ IBM PL/I ก็มีความสามารถคล้ายกันนี้ตั้งแต่ปี 1965 แล้ว
      ฟังก์ชัน wait ใน UNIX เป็นเวอร์ชันที่ลดทอนมาจาก wait ของ IBM PL/I และก็เหมือนกับหลายความสามารถที่รับทอดมาจาก Multics คืออ่อนกว่าต้นแบบเดิม
      WaitForSingleObject และ WaitForMultipleObjects ของ Microsoft เองก็ไม่ได้มี implementation ที่มีประสิทธิภาพนัก จนสุดท้ายต้องเพิ่ม WaitOnAddress ที่เทียบได้กับ futex ของ Linux
      Linux futex มีข้อจำกัดคือขนาด 32 บิต และรอได้เพียง event เดียว
      แม้จะสามารถใช้ atomic bit operation เพื่อทำการรอหลาย event ได้ แต่ก็ไม่มีประสิทธิภาพ ทำให้ปัญหาเรื่องขนาด 32 บิตยิ่งชัดเจนขึ้น
      จึงน่ายินดีที่มีความพยายามจะผสานข้อดีบางส่วนของ WaitForMultipleObjects เข้ากับ futex
      ความพยายามแบบนี้ไม่ใช่การเลียนแบบ Windows แต่เป็นการนำเทคนิคคลาสสิกที่เป็นที่รู้จักกันดีมากว่า 50 ปี และเก่าแก่กว่า Microsoft มาก กลับมาสร้างใหม่อีกครั้ง

    • ยังน่าเสียดายที่จนถึงตอนนี้ยังไม่มีฟีเจอร์ futex_swap
      ประเด็นถกเถียงที่เกี่ยวข้อง 1
      เอกสารอ้างอิง 2

    • Futex ไม่ได้เกี่ยวข้องกับ WFMO(WaitForMultipleObjects) แต่จริง ๆ แล้วเทียบได้กับ keyed events มากกว่า
      สิ่งที่เทียบกับ WFMO บน Linux คือ select/poll/epoll

    • การรองรับ futex ใน io_uring เป็นฟีเจอร์ที่ดีมากจริง ๆ
      ผมเคยนำไปใช้กับ Ruby fibers เพื่อทำ implementation ของ mutex และ queue
      ดูซอร์สโค้ด

  • หนังสือระบุไว้อยู่แล้วว่าควรใช้โครงสร้าง synchronization ที่มีให้จากไลบรารี/ภาษา/ระบบ แทนการลงมือเขียนเองโดยตรง
    จุดเน้นหลักของหนังสืออยู่ที่แนวคิด concurrency โดยรวม ไม่ใช่แพลตฟอร์มใดแพลตฟอร์มหนึ่งโดยเฉพาะ
    จึงน่าเสียดายที่ผู้เขียนบทความวางกรอบแบบเผชิญหน้าค่อนข้างเกินจริง
    บทความนี้น่าจะดีกว่านี้ถ้านำเสนอในมุมร่วมมือกันแบบ "สิ่งที่ TAoMP ไม่ได้พูดถึง"
    บล็อกนี้เพิ่งเปิดใหม่ Phil เป็นคนโพสต์บทความนี้ และ Phil ก็โปรโมตบทความอื่นด้วย ซึ่งดูสะดุดตาอยู่

    • ผมเป็นคนเขียนบทความนั้นเอง และเขียนมันหลังจากอ่านหนังสือแล้วรู้สึกผิดหวัง
      ผมรู้สึกว่าปัญหาคือทั้งในวงวิชาการและอุตสาหกรรม เราไม่ได้เรียนรู้สิ่งที่เอาไปใช้ได้จริงมากพอ
      ดังนั้นมันไม่ได้มีเจตนาแบบ "มาศึกษา futex กันเถอะ!"
      จริง ๆ คือผมผิดหวังกับหนังสือมากจนพักบทความอื่นไว้ แล้วเขียนชิ้นนี้ก่อน
      ผมเคยทำงานกับ Phil มาก่อนจึงยังมีความคุ้นเคยกันอยู่ แต่จนถึงตอนนี้ผมก็ไม่เคยมีปัญหาในการหาผู้อ่านให้บทความของตัวเอง

    • พอมาย้อนคิด ดูเหมือนส่วนที่ผมพูดประมาณว่า sysv style ไม่คู่ควรแม้แต่จะเอาไปเปรียบกับไดโนเสาร์จะรุนแรงเกินไป
      ตรงนี้คงต้องถ่อมตัวให้มากกว่านี้

  • สิ่งที่เจ๋งที่สุดของ futex คือมันเป็นโครงสร้างแบบ handle-less
    มันให้ primitive ที่มีประโยชน์มากในฐานะตัวเฝ้าดูหน่วยความจำฝั่งเคอร์เนล โดยไม่ต้องมีการ allocate/free ผ่าน syscall
    ถ้าไม่มีเธรดที่กำลังรอ ทุกอย่างก็ถูกเก็บกวาดอย่างเรียบร้อย และถ้าไม่มีการแย่งกัน เคอร์เนลก็จะไม่รับรู้ถึง mutex นั้นเลย
    ผมสงสัยว่ามีการวิเคราะห์เชิงลึกไหมว่าเคอร์เนลจัดการ futex ให้ประสิทธิภาพสูงได้อย่างไร
    วันนี้เป็นครั้งแรกที่ผมได้รู้จัก futex2
    เอกสารที่เกี่ยวข้อง

    • ใช่ และอีกอย่างหนึ่งคือเราไม่อยากให้มีการเรียก malloc() ในเคอร์เนลเพื่อจัดสรรข้อมูลทุกครั้งที่เธรดถูกบล็อกบนล็อก
      เพื่อหลีกเลี่ยงเรื่องนี้ OS หลายตัวจะจัดสรร 'queue object' ให้กับแต่ละเธรดตั้งแต่ตอนสร้างเธรด แล้วเมื่อเธรดนั้นเจอล็อกที่มีการแย่งกัน ก็จะเอาออบเจ็กต์นี้ไปผูกกับล็อกนั้น
      พูดอีกแบบคือจะมี queue object ในรูป linked list ของหลายเธรดที่เชื่อมกับล็อก และทุกครั้งที่เธรดถูกปลุกขึ้นมาก็จะหยิบออบเจ็กต์ออกไปทีละตัว
      ตอนเธรดจบการทำงาน ก็ไม่ได้มีการรับประกันว่าจะได้ออบเจ็กต์ตัวเดิมที่สร้างไว้ตอนแรกคืนมา เพราะออบเจ็กต์อาจสลับกันไปมาได้
      solaris เป็นระบบแรกที่นำโครงสร้างแบบนี้ (turnstile) มาใช้ และ BSD ต่าง ๆ ก็รับแนวทางนี้ไปใช้เช่นกัน
      ดู solaris internals
      เอกสาร PDF ของ BSD

    • wait queue ในเคอร์เนล Unix ยุคแรก ๆ ก็เป็นแบบนี้เหมือนกัน

  • ในงานวิจัย futex ต้นฉบับปี 2002 ก็พิสูจน์ประสิทธิภาพของ futex ไว้อย่างชัดเจนแล้ว โดยในการทดสอบกับงานขนาน 1000 task มันเร็วกว่า sysv lock ถึง 20–120 เท่า
    แต่ในทางปฏิบัติ baseline ไม่ใช่ sysv lock
    จริง ๆ แล้วเมื่อจะทำ implementation ของ lock ในสภาพแวดล้อมที่ไม่มี futex ส่วนใหญ่เส้นทางเร็วก็ไม่ต้องเข้าเคอร์เนลอยู่แล้ว และจะเข้าสู่เคอร์เนลเฉพาะเส้นทางช้าเพื่อรอเท่านั้น โดยจุดปรับปรุงของ futex ที่แท้จริงมีเพียงเรื่องการลดขนาดของโครงสร้างข้อมูลใน user space ที่ใช้บอกสถานะว่าล็อกกำลังมีคนรอ
    ทางเลือกอื่นอย่าง thin locks (แบบที่ใช้ใน JVM) หรือ ParkingLot (implementation แบบ userland ล้วน) ก็ทำงานได้โดยไม่ต้องมี futex จาก OS

    • จากประสบการณ์ของผม คนส่วนใหญ่มักเรียนรู้ primitive พื้นฐานที่มีให้ใช้ในงานจริงอยู่แล้ว ดังนั้นประเด็นที่สนใจจึงเป็นมาตรฐานไลบรารีของภาษาตัวเองมีอะไรให้ใช้บ้าง
      หรือก็คือกระแสหลักถูกขับเคลื่อนโดยการย้ายจาก sysv ไปเป็น futex และช่วงหลังแม้จะมีวิธี custom อยู่บ้าง แต่ futex ก็ยังเป็นกระแสหลัก
      ถ้าจะทำ userland scheduler เองก็อาจทำแบบอื่นได้ แต่ผมคิดว่าคนส่วนใหญ่น่าจะเลือกเขียนลง file descriptor แล้วจัดการคิวเองมากกว่า
      ผมยังสงสัยว่าวิธีแบบนั้นจะคุ้มแค่ไหน

    • ในความเป็นจริง lock สมัยใหม่แทบทุกชนิดสุดท้ายก็ใช้ futex ภายในอยู่ดี ถ้าระบบรองรับ
      เพราะบน Linux นั้น futex เป็นวิธีการรอที่มีประสิทธิภาพที่สุด ดังนั้นในเส้นทางช้า (down) ก็ควรใช้ futex เสมอ
      สิ่งอย่าง thread.park() ในภาษาต่าง ๆ เองก็น่าจะทำงานอยู่บน futex ในท้ายที่สุด

    • ผมสงสัยว่า JVM ยังใช้ thin lock อยู่หรือเปล่า
      ก่อนหน้านี้ผมเคยเจอข้อมูลอ้างอิงว่า JVM มีการเรียก futex เลยอยากรู้ว่ามันย้ายไปเป็น thin lock แล้วหรือไม่
      ประเด็นถกเถียงใน Stack Overflow

  • implementation จริงของ [recursive locks] นั้นไม่สอดคล้องกันแม้แต่ในบรรดามาตรฐานเอง และหลายกรณีก็ถึงขั้นไม่ยอมกำหนดไว้เลยเพราะมองว่าเป็นเรื่องยาก
    ท่าทีแบบนี้ค่อนข้างน่าหงุดหงิด
    มันเหมือนกับการบอกว่า "ในเมื่อคนทำ OS หรือคนทำภาษาอาจทำ feature X ได้ไม่ดี งั้นก็ปล่อยให้นักพัฒนาแอปไปจัดการเองแล้วกัน"
    สุดท้ายผู้ใช้ปลายน้ำก็แทบไม่มีทางออกอื่นนอกจากเปลี่ยน vendor

    • ถ้ามาตรฐานกำหนดข้อจำกัดมากเกินไป ก็อาจปิดทาง implementation ที่ดีกว่าได้
      ตัวอย่างเช่น hash table และ regular expression ในมาตรฐาน C++ ช้ากว่าของค่ายอื่นมากเพราะมีข้อจำกัดเยอะ
      ถ้ากำหนดข้อจำกัดเฉพาะเจาะจงมากไป (เช่น บังคับให้ใช้ chaining เท่านั้น) หรือบังคับการรับประกันบางอย่าง ก็จะกัน implementation ประสิทธิภาพสูงแบบอื่นออกไป
      recursive rwlock เองก็สามารถทำได้ทั้งแบบยอมแลกประสิทธิภาพหรือแบบตรวจสอบน้อยลง ดังนั้นผมไม่คิดว่าจำเป็นต้องปิดกั้นความเป็นไปได้หลาย ๆ ทาง

    • ส่วนตัวผมคิดว่า recursive lock ไม่ควรใช้ตั้งแต่แรกอยู่แล้ว เลยไม่รู้สึกว่าจำเป็นต้องใส่สเปกการรองรับมันลงในมาตรฐาน

    • ถ้าอยากเข้าใจปรากฏการณ์ worse is better มากขึ้น ลองดูในวิกิ
      ผมเองก็ไม่ได้ชอบมันนัก แต่ก็เป็นความจริงที่หลีกเลี่ยงได้ยาก

  • ผมสงสัยว่าทำไม futex บน linux ถึงมีข้อจำกัดว่ารองรับได้แค่ 32bit int เลยไปค้นดู
    ในการถกเรื่องการรองรับ 64 บิต Linus บอกว่าสามารถใช้ 64-bit atomic ใน user space แล้วใช้แค่ 32 บิตล่างกับ futex ก็ได้
    แต่ใน C/C++ นั้น mixed-size atomic ถือเป็น undefined behavior และ implementation semaphore ของ glibc เองก็ดูเหมือนจะทำแบบนั้น
    มันใช้ high 32 ของเลขจำนวนเต็ม 64 บิตเป็น waiter count และ low 32 เป็นค่า semaphore โดยให้ futex ใช้แค่ 32 บิตล่าง
    ผมเลยสงสัยว่าสำหรับ gcc นี่ถือเป็นพฤติกรรมที่นิยามไว้แล้วหรือไม่ หรือไม่เกี่ยวเพราะมีขอบเขตข้ามโปรเซส (เคอร์เนลโปรเซส) คั่นอยู่ หรือจริง ๆ แล้วแม้แต่ glibc ก็ใช้ undefined behavior เหมือนกัน

  • ผมขอแนะนำ C++ Concurrency in Action ของ Anthony Williams ด้วย แม้มันจะไม่ได้สอน futex หรือวิธีทำ implementation ของ synchronization primitive โดยตรง แต่ก็ครอบคลุมเรื่อง memory ordering และ SMR ที่จำเป็นต่อโครงสร้าง lock-free ซึ่งใกล้กับงานจริงมาก
    ถ้าต้องการมุมมองที่เน้นฮาร์ดแวร์มากขึ้น ก็ขอแนะนำหนังสือฟรีของ Paul McKenney ชื่อ "Is Parallel Programming Hard, And, If So, What Can You Do About It?"
    หนังสือเล่มนี้ก็ไม่ได้ลงลึกเรื่อง futex มากนัก แต่จะชี้ต่อไปยัง "Futexes Are Tricky" ของ Ulrich Drepper
    TAOMPP เหมาะกับการใช้ทำความเข้าใจแนวคิด concurrency ระดับสูง และไม่ใช่หนังสือที่จะลงรายละเอียด implementation ระดับ OS
    อย่างไรก็ดี แม้ Peterson หรือ bakery lock จะใช้จริงไม่ได้ แต่แค่เข้าใจการพิสูจน์ของมันก็ช่วยให้เข้าใจอัลกอริทึม concurrency ในโลกจริงได้มาก

    • bakery lock เหมาะกับ spin lock และเป็นมิตรกับแคช
      ยังสามารถทำ reader/writer spin lock ได้ด้วย แต่จะเป็น FIFO แบบเข้มงวด
      เราสามารถผูก futex เข้ากับการ spin wait ของ bakery lock ใน user space ได้ แต่ไม่มีประสิทธิภาพอย่างมาก
      futex ไม่ได้ถูกออกแบบมาเพื่อจุดประสงค์แบบนี้ตั้งแต่แรก
      โครงสร้าง lock-free, hazard pointer, RCU* เองก็ยัง tricky อยู่มาก
      แม้แต่ wait-free hazard pointer ก็ยังสามารถทำได้จริง
      *ในกรณีของ RCU นั้น copy-on-write เข้าใจได้ง่าย แต่ถ้ามีการอัปเดตบ่อย ต้นทุนก็จะสูงขึ้น

  • เช่นเดียวกับที่ Windows 8 เพิ่มสิ่งที่คล้าย futex เข้ามา เดิมที Win32 critical section ใช้เคอร์เนล semaphore เป็นฐาน
    แต่ผมสงสัยว่า SRW lock ที่เพิ่มเข้ามาใน Vista ใช้โครงสร้างแบบไหน

    • ทั้ง CRITICAL_SECTION และ SRWLock ต่างก็ไม่ต้องเข้าเคอร์เนลหากไม่มีการแย่งกัน
      SRWLock ใช้ keyed event เป็นฐาน ส่วน CRITICAL_SECTION จะสร้างเคอร์เนลออบเจ็กต์แบบ on-demand เมื่อเกิดความล้มเหลว แล้ว fallback ไปใช้ keyed event

  • ในช่องโหว่ของ implementation futex บน linux ปี 2014 ที่ Pinkie Pie ค้นพบ มีกฎ requeue-once ที่อนุญาตเฉพาะกับ futex ที่ส่งเข้าไปใน futex_wait_requeue_pi เท่านั้น
    จึงไม่สามารถ requeue จาก A ไป B แล้วจาก B ไป C ต่อได้ แต่สามารถชี้กลับจาก B ไป B ได้
    และในกรณีนี้มีบั๊กที่ทำให้ถ้าผ่านเงื่อนไขบางอย่างไปได้ ฟังก์ชัน cleanup จะไม่ถูกเรียก ส่งผลให้ pointer กลายเป็น dangling
    มีเคสตัวอย่างให้ดูได้
    ประเด็นที่เกี่ยวข้อง

  • บางคนอาจไม่กังวลเรื่องความถูกต้องของข้อมูลเมื่อมี crashed thread แต่ตราบใดที่ทั้งโปรเซสยังไม่ตาย ปัญหาเรื่องการ cleanup lock ก็ยังอยู่
    ทางออกสำหรับเรื่องนี้คือ robust lock
    โดยจะลงทะเบียนรายการ held futex ไว้กับเคอร์เนล และใช้ sys_set_robust_list เพื่อให้เมื่อเธรดจบการทำงาน เคอร์เนลจัดการ bit นั้นและปลุกฝั่งที่กำลังรอ (waiter) ขึ้นมา

    • ข้อเสียใหญ่ที่สุดของแนวทาง robust lock คือมีโอกาสสูงที่ resource ที่ล็อกนั้นปกป้องไว้จะอยู่ในสภาพ inconsistent ไปแล้ว
      ถ้าไม่รู้แน่ชัดว่าเธรดล้มเพราะอะไร ก็อาจเชื่อถือความสมบูรณ์ของข้อมูลไม่ได้ และกู้คืนไม่ได้จริง
      ดังนั้นในทางปฏิบัติ การทำให้ทั้งแอปตายไปพร้อมกันอาจสมเหตุสมผลกว่า
      ความสามารถด้าน cleanup/recovery ของ robust lock นั้นเท่มากก็จริง แต่ผมเดาว่าวิศวกร 95% คงไม่ได้ออกแบบโครงสร้างข้อมูลแบบ robust อย่างถูกต้อง
      อีก 4% อาจไม่มีเวลาทำ และเหลือเพียง 1% ที่ทำได้ถูกต้องและได้รับผลตอบแทนก้อนใหญ่จากมัน

    • เวลาใช้ futex ระหว่างหลายโปรเซส (สถานะข้ามโปรเซส) เราอาจใช้ watchdog process ที่เปิด Unix domain socket (SOCK_STREAM หรือ SOCK_SEQPACKET) แยกไว้ต่อโปรเซส เพื่อจับการ crash และจัดการสถานะรายโปรเซสได้

    • ที่ผมคุยเรื่อง mutex แค่ในขอบเขตโปรเซส ก็เพราะกลัวว่าถ้าลงลึกข้ามขอบเขตนี้ไปแล้ว การสนทนาจะไม่มีที่สิ้นสุด