Không có futex thì chẳng có ý nghĩa gì

 (h4x0r.org)
4 điểm bởi GN⁺ 2025-08-21 | 1 bình luận | Chia sẻ qua WhatsApp
  • Giáo trình The Art of Multiprocessor Programming bị cho là đáng tiếc khi không đề cập đến khái niệm futex
  • Futex là thành phần cốt lõi của đồng bộ hóa hiệu quả trong lập trình song song hiện đại, cho hiệu năng vượt trội so với các khóa dựa trên System V trước đây
  • Futex có cấu trúc tách riêng việc giành khóa với chờ/đánh thức, nhờ đó giảm các system call và overhead không cần thiết
  • Bài viết gồm các ví dụ và kỹ thuật tự triển khai nhiều primitive đồng thời như spinlock, mutex, khóa đệ quy dựa trên futex
  • Tác giả chỉ ra khoảng cách giữa học thuật và thực tiễn khi cuốn sách không đề cập đến các phương pháp đồng bộ hóa hiện đại thiết yếu trong công việc kỹ sư thực tế

Giới thiệu

  • Phil Eaton bắt đầu câu lạc bộ đọc sách về The Art of Multiprocessor Programming, 2nd Edition
  • Cuốn sách này được xem là một giáo trình có thẩm quyền trong lĩnh vực lập trình song song, nhưng tác giả cho rằng nó thiếu tính thực dụng trong nội dung
  • Đặc biệt, dù nhắm đến sinh viên năm cuối đại học và học viên cao học, sách lại không đề cập đến futex, một kỹ thuật đồng bộ hóa cốt lõi, nên bị phê phán

Futex là gì – vì sao quan trọng

  • Futex là viết tắt của “fast user space mutex”, nhưng trên thực tế, thay vì là một mutex hoàn chỉnh, nó là primitive đồng bộ hóa được OS hỗ trợ để triển khai các loại khóa hiện đại
  • Trước đây, phần lớn khóa được triển khai dựa trên semaphore của System V IPC nên bị giới hạn về hiệu quả và khả năng mở rộng
  • Khi futex được đưa vào Linux năm 2002, nó cho thấy hiệu năng nhanh hơn 20–120 lần so với khóa System V trong môi trường 1000 tác vụ đồng thời
  • Các hệ điều hành khác như Windows (2012) và macOS (2016) cũng đưa vào các cơ chế tương tự
  • Ngày nay, các khóa trong thư viện hệ thống được dùng rộng rãi như pthreads đều sử dụng futex

Nguyên lý hoạt động và điểm khác biệt của futex

  • Semaphore truyền thống gộp khóa và chờ lại với nhau, còn futex tách riêng việc giành khóa với chờ/đánh thức
  • Nhờ vậy có thể giảm độ trễ và system call không cần thiết; khi mở khóa mà chắc chắn không có thread nào đang chờ thì không cần vào kernel
  • Lệnh chờ (wait) của futex chỉ cho phép “chờ khi giá trị tại một địa chỉ bộ nhớ cụ thể đúng với trạng thái mong muốn”, đồng thời hỗ trợ timeout
  • Lệnh đánh thức (wake) của futex sẽ đánh thức số lượng thread mong muốn từ danh sách chờ nội bộ gắn với một địa chỉ bộ nhớ cụ thể
  • Việc bắt buộc kiểm tra giá trị thực tại địa chỉ bộ nhớ giúp tránh chờ vô ích khi trạng thái đã thay đổi

Ứng dụng thực tế của futex – tự triển khai

  • Vì futex là primitive cấp thấp, cần dùng kiểu dữ liệu atomic để xử lý các vấn đề về thứ tự thao tác bộ nhớ của compiler và phần cứng
  • Trên Linux, phải gọi trực tiếp system call futex bằng syscall; trên macOS, dùng giao diện __ulock (gần đây đã có thêm API dễ dùng hơn)
  • Về cơ bản, lệnh chờ futex trả về 0 khi thành công, và mã lỗi khi thất bại (ví dụ timeout)
  • Các phép toán cốt lõi dựa trên futex:
    • h4x0r_futex_wait_timespec() : chờ khi giá trị kỳ vọng khớp, có thể áp dụng timeout
    • h4x0r_futex_wake() : đánh thức 1 hoặc toàn bộ waiter
    Quảng cáo

Ví dụ thực chiến về triển khai mutex/spinlock/khóa đệ quy

Spinlock

  • Dạng khóa đơn giản nhất, hoạt động chỉ bằng một bit duy nhất (atomic_fetch_or)
  • Nó lặp vô hạn (“spin”) cho đến khi lấy được khóa, nhưng trong tình huống tranh chấp cao sẽ lãng phí CPU, đồng thời có các vấn đề cấu trúc như mở khóa sai hoặc deadlock khi gọi đệ quy

Mutex lai (“unsafe” mutex)

  • Thông thường sẽ thử bằng spinlock trước, nếu thất bại sau một số lần nhất định thì chuyển sang futex để block hiệu quả
  • Nếu không có waiter thì có thể tránh system call không cần thiết, còn với waiter thì cũng giảm số lần gọi system call để đánh thức
  • Do chưa kiểm tra chặt chẽ quyền sở hữu hay xử lý đệ quy, nó được gọi là “unsafe”

Mutex có bộ đếm waiter

  • Một bit biểu thị trạng thái khóa, phần còn lại dùng để đếm số waiter, nhằm giảm các system call đánh thức không cần thiết
  • Tuy vậy vẫn chưa xử lý quyền sở hữu hay đệ quy
Quảng cáo

Mutex có quản lý quyền sở hữu

  • Dùng giá trị pthread_t để theo dõi rõ ràng chủ sở hữu khóa và trạng thái, từ đó phát hiện lỗi unlock sai hoặc sử dụng đệ quy
  • Việc lấy khóa, mở khóa và quản lý waiter đều được kiểm soát bằng các phép toán atomic nghiêm ngặt

Khóa đệ quy

  • Bổ sung bộ đếm độ lồng (depth) theo từng thread, cho phép cùng một thread lấy khóa lồng nhau
  • Khi unlock thì depth giảm; nếu về 0 thì mới thực hiện unlock thật sự và đánh thức waiter
  • Mỗi thao tác đều được triển khai bằng phép toán atomic và kiểm tra quyền sở hữu nghiêm ngặt

Những vấn đề còn lại và thực tế kỹ thuật

  • Nếu thread đang giữ khóa bị kết thúc bất thường/chết, cần danh sách quản lý riêng, callback khi kết thúc và các cơ chế bổ sung khác để quản lý khóa
  • Khi dùng mutex chia sẻ giữa các tiến trình, cũng cần thêm các cân nhắc để quản lý thay đổi trạng thái
  • Khóa đọc-ghi POSIX (RW lock) không định nghĩa hành vi lồng đệ quy một cách thống nhất và còn khác nhau tùy triển khai, nên trên thực tế khó bảo đảm an toàn
  • Tác giả phê phán việc những vấn đề đồng thời thật sự quan trọng trong thực chiến như futex, khóa đệ quy, runtime bất đồng bộ... không được đưa vào chương trình học

Kết luận

  • The Art of Multiprocessor Programming thiên về góc nhìn lịch sử hoặc lý thuyết, nên không truyền tải đầy đủ tri thức thực hành quan trọng của lập trình song song hiện đại
  • Nếu không trình bày đúng mức các thành phần đồng bộ hóa cốt lõi như futex vốn thực sự vận hành trong hệ thống, điều đó có thể gây hại thực tế cho thế hệ học viên sau này
  • Tác giả nhấn mạnh sự cần thiết phải cập nhật các khái niệm mới và bổ sung nội dung thực dụng

Tài liệu tham khảo

  • Có thể xem toàn bộ ví dụ mã tại codeberg

Bài viết liên quan

1 bình luận

 
GN⁺ 2025-08-21
Ý kiến Hacker News

  • Windows có tính năng WaitForMultipleObjects, và Linux cũng đã đưa vào tính năng này với Futex2 từ phiên bản 5.16 (cuối năm 2021)
    Liên kết liên quan
    Gần đây Futex2 đã nhận được nhiều cải tiến khác nhau
    Hỗ trợ NUMA cuối cùng cũng đã được bổ sung
    Liên kết NUMA 1
    Liên kết NUMA 2
    NUMA là một yếu tố rất quan trọng đối với hiệu năng
    io_uring được áp dụng cho futex trong 6.7 (năm 2024), giúp cải thiện hiệu năng aio của postgresql
    Bài viết liên quan
    Trong 6.7 cũng đã bổ sung các tính năng Small requeue và single wait
    Liên kết liên quan

    • Windows không phải mới bổ sung WaitForMultipleObjects, mà đã có nó ngay từ đầu hơn 30 năm trước
      WaitForMultipleObjects đúng là một ưu điểm của Windows NT so với UNIX, nhưng IBM PL/I cũng đã có tính năng tương tự từ năm 1965
      Hàm wait trong UNIX là một phiên bản được đơn giản hóa từ wait của IBM PL/I, và cũng như nhiều tính năng khác kế thừa từ Multics, nó yếu hơn mô hình gốc
      WaitForSingleObject và WaitForMultipleObjects của MS cũng không phải là cách triển khai hiệu quả, nên cuối cùng họ cũng phải đưa vào WaitOnAddress tương đương với futex của Linux
      Futex của Linux có giới hạn là kích thước 32 bit và chỉ có thể chờ một sự kiện duy nhất
      Có thể dùng phép toán bit nguyên tử để triển khai chờ nhiều sự kiện, nhưng cách đó không hiệu quả nên vấn đề kích thước 32 bit càng trở nên lớn hơn
      Việc cố gắng kết hợp một phần ưu điểm của WaitForMultipleObjects vào futex là điều đáng hoan nghênh
      Những nỗ lực như vậy không phải là bắt chước Windows, mà thực ra là tái hiện lại một kỹ thuật kinh điển đã được biết đến rõ ràng từ hơn 50 năm trước, còn lâu đời hơn cả Microsoft

    • Hơi tiếc là đến giờ vẫn chưa có tính năng futex_swap
      Thảo luận liên quan 1
      Tài liệu liên quan 2

    • Futex không liên quan tới WFMO(WaitForMultipleObjects), mà đúng hơn là tương đương với keyed events
      Trên Linux, tính năng tương ứng với WFMO là select/poll/epoll

    • Hỗ trợ futex trong io_uring thực sự là một tính năng rất hay
      Tôi đã dùng nó khi làm việc với Ruby fibers để triển khai mutex và queue
      Tham khảo mã nguồn

  • Cuốn sách nói rõ rằng thay vì tự triển khai các cấu trúc đồng bộ, hãy dùng các cấu trúc do library/ngôn ngữ/hệ thống cung cấp
    Trọng tâm chính của sách là các khái niệm concurrency tổng quát chứ không phải một nền tảng cụ thể
    Thật tiếc là tác giả bài viết đã dựng vấn đề theo kiểu đối đầu hơi quá
    Sẽ tốt hơn nếu bài này được viết theo góc nhìn mang tính cộng tác như "những gì TAoMP không nói tới"
    Đáng chú ý là blog này mới được lập, Phil đăng bài này lên, và Phil cũng đã quảng bá các bài viết khác

    • Tôi là người viết bài đó, và tôi viết vì thấy thất vọng khi đọc cuốn sách
      Tôi cảm thấy vấn đề là cả trong học thuật lẫn công nghiệp, người ta đều không học được những nội dung thực sự hữu ích trong thực tế
      Vì vậy ý định của tôi không phải kiểu "hãy tìm hiểu futex!"
      Thực sự là vì thất vọng với cuốn sách nên tôi đã hoãn các bài khác để viết bài này trước
      Tôi từng làm việc với Phil nên có quen biết, nhưng từ trước đến nay tôi vẫn luôn tìm được độc giả cho bài viết của mình mà không gặp khó khăn gì

    • Tôi nghĩ đoạn trước đây nói theo kiểu không còn gọi phong cách sysv là khủng long nữa thì đã hơi quá đáng
      Đó là chỗ cần thêm sự khiêm tốn

  • Điểm hay nhất của futex là nó có cấu trúc không cần handle
    Nó cung cấp một hành vi cơ bản rất hữu ích như một bộ theo dõi bộ nhớ ở mức kernel mà không cần cấp phát/giải phóng qua syscall
    Nếu không có thread nào đang chờ thì mọi thứ được dọn dẹp gọn gàng, và nếu không có tranh chấp thì kernel thậm chí không biết mutex đó tồn tại
    Tôi khá tò mò về phân tích chi tiết việc kernel quản lý futex hiệu năng cao như thế nào
    Hôm nay là lần đầu tôi biết đến futex2
    Tài liệu liên quan

    • Đúng vậy, ngoài ra cũng không ai muốn mỗi lần một thread bị block ở lock thì kernel lại phải gọi malloc() để cấp phát dữ liệu
      Để tránh điều này, nhiều hệ điều hành cấp phát sẵn một 'queue object' cho mỗi thread khi thread được tạo, rồi khi thread đó gặp lock có tranh chấp thì object này sẽ được gắn vào lock
      Tức là sẽ có các queue object theo dạng linked list gắn với lock từ nhiều thread, và mỗi lần thread được đánh thức thì nó lấy ra một object
      Không có gì đảm bảo rằng khi thread kết thúc nó sẽ lấy lại đúng object ban đầu mình đã tạo, vì các object có thể đã bị trộn lẫn giữa chừng
      Solaris là nơi đầu tiên đưa vào cấu trúc như vậy (turnstile), và các BSD cũng áp dụng cách này
      Tham khảo solaris internals
      Tài liệu PDF BSD

    • Các hàng đợi chờ trong kernel Unix thời kỳ đầu cũng theo kiểu này

  • Ngay trong bài báo futex gốc năm 2002, hiệu quả của futex đã được chứng minh rất rõ, với bài test 1000 tác vụ song song cho hiệu năng nhanh hơn 20~120 lần so với khóa sysv
    Nhưng trên thực tế, mốc so sánh (baseline) không phải là khóa sysv
    Trong thực tế, khi triển khai lock ở môi trường không có futex, phần lớn trường hợp đường nhanh sẽ không vào kernel, và chỉ ở đường chậm mới chuyển sang chờ trong kernel; điểm cải thiện duy nhất của futex là kích thước của cấu trúc dữ liệu vùng người dùng dùng để biểu thị trạng thái chờ khóa đã nhỏ hơn
    Các lựa chọn khác như thin locks (cách JVM dùng), ParkingLot (triển khai hoàn toàn ở userland) vẫn có thể hoạt động mà không cần futex của OS

    • Theo kinh nghiệm của tôi, đa số thực tế là học các primitive cơ bản được cung cấp sẵn trong môi trường làm việc, nên người ta sẽ tập trung vào việc standard library của ngôn ngữ mình cung cấp gì
      Nói cách khác, xu hướng chủ đạo là chuyển từ sysv sang futex, và gần đây tuy có các cách tự triển khai nhưng dòng chính vẫn là futex
      Nếu tự viết scheduler ở userland thì có thể sẽ tự triển khai cách khác, nhưng tôi nghĩ đa số vẫn sẽ dùng kiểu ghi vào file descriptor rồi tự quản lý queue
      Tôi hơi nghi ngờ không biết cách xử lý đó sẽ mang lại bao nhiêu lợi ích

    • Thực tế thì bất kỳ lock hiện đại nào cuối cùng bên trong cũng sẽ dùng futex (nếu được hỗ trợ)
      Vì trên Linux, futex là cách chờ hiệu quả nhất, nên ở đường chậm (down path) luôn nên dùng futex
      Những thứ như thread.park() trong ngôn ngữ cũng rất có khả năng hoạt động trên futex

    • Tôi tò mò không biết JVM có còn dùng thin lock hay không
      Trước đây tôi từng thấy tài liệu nói JVM gọi futex, nên muốn biết liệu nó đã chuyển sang thin lock hay chưa
      Thảo luận liên quan trên Stack Overflow

  • Cách triển khai thực tế của [recursive locks] không thống nhất ngay cả giữa các tiêu chuẩn, và nhiều nơi còn không định nghĩa luôn chỉ vì cho rằng điều này khó
    Cách làm như vậy khá bức bối
    Kiểu như "người triển khai OS hay ngôn ngữ có lẽ sẽ không làm được feature X cho tử tế, vậy cứ để lập trình viên ứng dụng tự xử lý"
    Kết quả là người dùng downstream gần như không còn lựa chọn nào ngoài việc đổi vendor

    • Nếu tiêu chuẩn áp quá nhiều ràng buộc thì có thể vô tình chặn mất khả năng có những cách triển khai tốt hơn
      Ví dụ, bảng băm và regex trong tiêu chuẩn C++ chậm hơn nhiều so với bên thứ ba vì có quá nhiều ràng buộc
      Nếu áp đặt các ràng buộc cụ thể (ví dụ bắt buộc chỉ dùng chaining) hoặc bảo đảm tính năng nhất định thì sẽ chặn các cách triển khai hiệu năng cao thay thế
      Với recursive rwlock cũng vậy, vì vẫn có thể có các cách triển khai chấp nhận hy sinh hiệu năng hoặc giảm mức kiểm tra, nên tôi nghĩ không cần phải khóa chặt các hướng đi khác nhau

    • Cá nhân tôi thấy recursive lock vốn dĩ đã là thứ không nên dùng, nên không cảm thấy cần phải đưa hẳn spec hỗ trợ nó vào tiêu chuẩn

    • Nếu muốn hiểu thêm về hiện tượng worse is better thì có thể xem trên wiki
      Tôi không thích lắm, nhưng đó là thực tế khó tránh

  • Tôi tò mò vì sao futex trên Linux lại bị giới hạn chỉ hỗ trợ 32bit int nên đã tìm hiểu thử
    Trong thảo luận về hỗ trợ 64 bit, Linus có nói rằng ở userland cứ dùng atomic 64 bit, rồi chỉ dùng 32 bit thấp làm futex là được
    Nhưng trong C/C++, mixed-size atomic được xem là undefined behavior, và trên thực tế triển khai semaphore của glibc cũng hoạt động theo cách đó
    Trong một số nguyên 64 bit, 32 bit cao được dùng làm waiter count, còn 32 bit thấp là giá trị semaphore, và futex chỉ dùng 32 bit thấp
    Tôi thắc mắc không biết với gcc đây có phải là hành vi được định nghĩa hay không, hay là nhờ có ranh giới tiến trình (kernel process) nên không sao, hoặc thậm chí glibc cũng đang dùng undefined behavior

  • Tôi cũng muốn giới thiệu C++ Concurrency in Action của Anthony Williams; tuy không nói về futex hay cách tự triển khai synchronization primitive, nhưng có bàn tới memory ordering và các nội dung sát thực tế hơn như SMR cần cho cấu trúc lock-free
    Nếu cần góc nhìn thiên về phần cứng hơn nữa thì có thể đọc miễn phí cuốn "Is Parallel Programming Hard, And, If So, What Can You Do About It?" của Paul McKenney
    Cuốn này cũng không đi sâu vào futex, nhưng có dẫn tới "Futexes Are Tricky" của Ulrich Drepper
    TAOMPP phù hợp để học tốt các khái niệm concurrency ở mức cao, còn chi tiết triển khai ở cấp độ OS thì không phải mục tiêu của nó
    Dù sao thì Peterson hay bakery lock tuy vô dụng trong thực tế, nhưng chỉ cần học cách chứng minh của chúng thôi cũng rất có ích cho việc hiểu các thuật toán đồng thời trong thực chiến

    • Bakery lock thì tốt cho spin lock và thân thiện với cache
      Cũng có thể triển khai reader/writer spin lock, nhưng sẽ là FIFO nghiêm ngặt
      Có thể nối futex vào kiểu spin wait của bakery lock trong user space, nhưng rất kém hiệu quả
      Futex vốn không được thiết kế cho mục đích này (chờ quay vòng)
      Các cấu trúc lock-free, hazard pointer, RCU*... cũng vẫn rất tricky
      Thậm chí còn có thể làm được wait-free hazard pointer trong thực tế
      *Với RCU, copy-on-write thì trực quan nhưng nếu cập nhật thường xuyên thì chi phí sẽ tăng lên

  • Cũng như Windows 8 đưa vào một thứ tương tự futex, ban đầu Win32 critical section vốn dựa trên semaphore của kernel
    Nhưng tôi tò mò không biết SRW lock được đưa vào từ Vista thì có cấu trúc như thế nào

    • Cả CRITICAL_SECTION lẫn SRWLock đều không vào kernel nếu không có tranh chấp
      SRWLock dựa trên keyed event, còn CRITICAL_SECTION khi thất bại sẽ tạo kernel object theo kiểu on-demand để gọi, rồi fallback sang keyed event

  • Trong lỗ hổng do Pinkie Pie phát hiện ở triển khai futex của Linux năm 2014, quy tắc requeue-once chỉ được cho phép với futex được truyền vào futex_wait_requeue_pi
    Không thể requeue từ A sang B rồi lại từ B sang C, nhưng có thể chỉ định lại từ B sang chính B
    Lúc này có một bug là nếu vượt qua một số điều kiện nhất định thì hàm cleanup sẽ không được gọi, khiến con trỏ rơi vào trạng thái dangling
    Có thể xem trường hợp liên quan tại đây
    Vấn đề liên quan

  • Có người không quá lo về tính toàn vẹn dữ liệu do thread bị crash, nhưng chừng nào toàn bộ process chưa chết thì vấn đề dọn dẹp lock vẫn còn
    Giải pháp cho việc này là robust lock
    Nó đăng ký danh sách các futex đang được giữ với kernel, rồi dùng sys_set_robust_list để khi thread kết thúc sẽ xử lý bit đó và đánh thức phía đang chờ (waiter)

    • Nhược điểm lớn nhất của robust lock là chính tài nguyên mà lock đó bảo vệ rất có thể đã ở trạng thái không nhất quán
      Nếu không biết chắc thread bị crash vì sao thì dữ liệu có thể đã mất toàn vẹn và không thể khôi phục
      Vì thế đôi khi giết luôn toàn bộ ứng dụng lại thực tế hơn
      Tính năng cleanup/recovery dùng robust lock tự nó rất hay, nhưng có lẽ 95% kỹ sư sẽ không thiết kế đúng được cả cấu trúc dữ liệu robust
      4% thì không có đủ thời gian để làm vậy, và chỉ còn 1% là làm đúng và được đền đáp xứng đáng

    • Khi dùng futex giữa nhiều process (trạng thái cross-process), có thể áp dụng cách một watchdog process mở Unix domain socket (SOCK_STREAM hoặc SOCK_SEQPACKET) cho từng process để phát hiện crash và dọn dẹp trạng thái theo từng process

    • Bản thân tôi cũng chỉ giới hạn thảo luận về mutex trong phạm vi ranh giới process vì lo rằng nếu đào sâu thêm thì sẽ không có điểm dừng