Đa luồng nhanh hay chậm?

Đa luồng nhanh hay chậm?

Trong Khoa học Máy tính, luồng (thread) là đơn vị thực thi nhỏ nhất được quản lý một cách độc lập bởi bộ lập lịch của hệ điều hành. Bộ lập lịch này cho phép nhiều thread có thể chạy song song gọi là Đa luồng (Multithreading). Đây là một kỹ thuật quan trọng và được hầu hết ngôn ngữ lập trình hỗ trợ. Một lập trình viên sơ cấp cũng có thể dễ dàng khởi tạo hoặc sử dụng thread để xử lý dữ liệu một cách song song. Nhưng không phải ai cũng có thể trả lời câu hỏi tại sao multithreading chạy nhanh hơn single-threading? Bao nhiêu thread là đủ?

Cơ chế hoạt động của CPU cache

Cấu trúc của bộ vi xử lý (CPU) hiện đại với nhiều lõi (core) và vùng nhớ đệm[1]

 

Tốc độ của bộ nhớ rất chậm so với bộ vi xử lý, vì vậy để tăng tốc độ thực người ta thiết kế các bộ nhớ nhỏ hơn, nhanh hơn, gọi là vùng nhớ đệm (cache), gồm có 3 level: L1-L2-L3 ở gần CPU. Tốc độ của cache L1 có thể nhanh hơn 30 lần so với bộ nhớ chính. Vì dung lượng của các cache này không cao, nên chỉ những dữ liệu cần thiết nhất cho CPU mới được sao chép vào cache: các lệnh ở mức mã máy, dữ liệu nằm trong các biến và có cả các dữ liệu được chia sẻ giữa nhiều thread. Vì các cache L1-L2 của mỗi core là độc lập, nên dẫn tới 2 vấn đề lớn đối với multithreading: context switch của CPU và làm tươi (refresh) các dữ liệu dùng chung.

Context switch của CPU

Context switch[3] (đôi khi được gọi là process switch hoặc task switch) là quá trình lưu trữ trạng thái của CPU hoặc của một thread để có thể tiếp tục thực thi sau đó. Việc lưu trữ này cho phép nhiều tiến trình có thể cùng thực thi trên một CPU vật lý và là chức năng quan trọng của các hệ điều hành đa nhiệm. Context switch là một quá trình phức tạp, đòi hỏi nhiều bước như lưu trữ các thanh ghi (registers), lưu trữ trạng thái các cache… tùy thuộc vào từng loại CPU và hệ điều hành khác nhau. Ví dụ, đối với nhân Linux, context switch liên quan tới các thanh ghi (registers), con trỏ ngăn xếp (stack pointer) và con trỏ chương trình. Nếu context switch xảy ra giữa 2 thread thuộc 2 tiến trình (process) khác nhau sẽ phức tạp và tốn thời gian hơn.

Tiến trình của context switch (nguồn ghi trong hình)

Ngoài chi phí cho việc lưu trữ/phục hồi trạng thái của các thread, hệ điều hành cũng phải tốn chi phí cho bộ lập lịch (task scheduler) để chọn lựa thread tiếp theo được đưa vào xử lý.

Làm tươi các dữ liệu dùng chung

Các dữ liệu sau khi được sao chép sang các cache L1-L2 riêng biệt của từng core, khi một core làm thay đổi dữ liệu dùng chung thì các core khác không thể tự động cập nhật các thay đổi đó. Điều này dẫn đến yêu cầu phải có cơ chế chia sẻ hoặc thông báo giữa các core. Mỗi ngôn ngữ và hệ điều hành có cách thức xử lý khác nhau, nhưng tựu chung lại có thể phân loại thành mấy phương pháp:

Lock object: sử dụng một biến trung gian để cấp quyền thực thi cho từng thread, mỗi thread muốn được thực thi cần phải “chiếm quyền” (acquire) một cờ được định nghĩa trước, sau khi hoàn thành xử lý đối với dữ liệu dùng chung sẽ giải phóng (release) cờ để các thread khác có thể “chiếm quyền”. Như vậy tại mỗi thời điểm chỉ có một thread được quyền thay đổi dữ liệu dùng chung và các thread khác dễ dàng cập nhập dữ liệu mới nhất. Phương pháp này rất hiệu quả nhưng có 2 nhược điểm lớn. Đầu tiên là tất cả các thread muốn thay đổi (hoặc đơn giản chỉ muốn đọc) dữ liệu dùng chung sẽ bị treo lại (pending) cho đến khi chiếm được quyền thực thi, khiến cho các core phải thực hiện context switch để chọn các thread đã sẵn sàng thực thi khác. Thứ hai là dẫn tới tình trạng các thread chờ nhau thành một vòng tròn (deadlock) hoặc rất khó kiểm soát trình tự thực thi của các thread (race condition), dẫn tới các lỗi tiềm ẩn.

Các ngôn ngữ lập trình sử dụng lock object để tạo ra các cấu trúc dữ liệu chuyên biệt phức tạp hơn để quản lý các thread như Semaphore, Lock của Java hoặc Monitor, Mutex của .NET[4]. Các cấu trúc dữ liệu này cho phép lập trình viên dễ dàng thao tác với thread và đạt được hiệu năng cao hơn so với sử dụng các từ khóa có sẵn của ngôn ngữ lập trình (synchronized của Java và lock của .NET).

Memory barrier: sử dụng các lệnh đặc biệt của CPU để sắp xếp trình tự thực hiện các thao tác đọc - ghi giữa các CPU. Phương pháp này khá phức tạp và tùy thuộc mỗi loại CPU lại có cách thực hiện khác nhau. Ví dụ đơn giản nhất có lẽ là từ khóa volatile của Java, mỗi câu lệnh ghi dữ liệu vào biến được khai báo với từ khóa này sẽ luôn được thực hiện trước mọi yêu cầu đọc dữ liệu từ biến đó[6]

Ví dụ về memory barrier[5]

Chọn lựa giữa đơn luồng và đa luồng

Trên lý thuyết ta thấy đa luồng phức tạp và chạy chậm hơn đơn luồng, trên thực tế hướng tiếp cận đa luồng có thể tăng hiệu năng của hệ thống, nhưng điều này không phải lúc nào cũng đúng. Đối với các nghiệp vụ hay hệ thống cần tính toán số lượng lớn dữ liệu đã được nạp sẵn vào RAM thì đơn luồng luôn cho kết quả khả quan hơn như trên lý thuyết đã dự báo. Đối với các hệ thống cần dữ liệu thông qua các kênh "IO" (ổ cứng, card mạng, thiết bị ngoại vi) thì đa luồng sẽ dễ dàng cho hiệu năng vượt trội so với đơn luồng.

Điều này được giải thích bởi vì tốc độ của các thiết bị ngoại vi rất chậm so với RAM (và RAM rất chậm so với CPU), vì vậy khi CPU phải chờ dữ liệu được thiết bị ngoại vi thu thập đầy đủ (như nhận đủ các gói tin của một thông điệp TCP) sẽ rất lãng phí tài nguyên. Lúc này hệ điều hành nên nạp các thread khác đã có đầy đủ dữ liệu và sẵn sàng thực thi vào core để thực hiện. Các thư viện non-blocking IO áp dụng nguyên lý này rất hiệu quả, chỉ cần 1 thread để thu thập dữ liệu, sau đó chuyển cho nhiều thread khác xử lý. Có một ví dụ kinh điển khác là Node.JS, mặc dù chỉ sử dụng 1 thread (JavaScript là đơn luồng) nhưng có thể xử lý số lượng lớn request HTTP.

Quay trở lại với câu hỏi từ ban đầu: bao nhiêu thread là đủ? Không có một quy tắc cụ thể để xác định số thread mà hệ thống cần, dù sao thì cũng có vài quy tắc cơ bản:

  • Nếu hệ thống thiên về xử lý số liệu thì single-thread thường tối ưu hơn.
  • Nếu hệ thống có giao tiếp với thiết bị ngoại vi thì nên sử dụng các thư viện Non-blocking IO hoặc sử dụng multi-thread.
  • Cách dễ nhất để xác định là thay đổi số lượng thread được sử dụng và tiến hành kiểm tra hiệu năng hệ thống (stress test hoặc benchmark) với nhiều kịch bản khác nhau, qua vài lần thay đổi ta có thể xác định số lượng thread tối ưu.

---------------------------------------------

Nguồn tham khảo:

  1. http://www.aristeia.com/TalkNotes/ACCU2011_CPUCaches.pdf
  2. https://en.wikipedia.org/wiki/Context_switch
  3. http://www.linfo.org/context_switch.html
  4. https://docs.microsoft.com/en-us/dotnet/csharp/programming-guide/concepts/threading/thread-synchronization
  5. https://www.javaworld.com/article/2074990/java-concurrency/warning--threading-in-a-multiprocessor-world.html
  6. https://docs.oracle.com/javase/specs/jls/se8/html/jls-17.html#jls-17.4.5