Buy me a coffee
Concurrent: Mutex và Semaphore
Đây sẽ là một chuỗi bài viết của mình về Concurrent, và sẽ không tập trung vào một ngôn ngữ cụ thể nào cả. Trong bài viết đầu thì mình sẽ tập trung vào Mutex và Semaphore, đây có thể xem là 2 phương pháp truyền thống nhất để giải quyết bài toán Concurrent.
Concurrent là Parallel đúng không ta?
Thực sự thì trong văn nói bình thường, khi nói tới Thread hay Concurrent ta thường hiểu là nó chạy song song nên ta nghĩ rằng Concurrent là Parallel nhưng thực sự thì nó không hẳn là như vậy.
Parallel
Khi ta nói tới Parallel tức là ta nói tới một lệnh được chạy cùng lúc cho nhiều vùng nhớ tiêu biểu nhất ta phải kể tới SIMD, nghĩa là bạn đang load cùng lúc nhiều phần tử lên Register và chạy 1 lệnh cho tất cả các phần tử đó. Nên thực tế thì CPU không cần phải có nhiều Cores để chạy được Parallel mà quan trọng là có hỗ trợ lệnh để tính toán kiểu như vậy hay không mà thôi.
Concurrent
Còn đối với Concurrent là ta nói tới Thread, đây là những đoạn code gồm nhiều lệnh và chúng dùng chung một vùng nhớ. Thì rất khác với Parallel, nếu CPU chỉ có 1 Core nghĩa là tuy tạo nhiều Thread nhưng thực tế chúng vẫn chạy tuần tự bằng cơ chế Context Switch.
Nghĩa là trong lúc Thread đang chiếm hết 1 Core của CPU thì sau 1 khoản thời gian sẽ bị switch qua một Thread khác và Thread mới này sẽ lại chiếm hết 1 Core của CPU và cứ như thế. Vì vậy Concurrent với CPU 1 Core nó không hiệu quả lắm, trừ khi Thread phải đợi Network thì nó mới tránh bị Block thôi.
Chính vì vậy, nên nếu CPU có nhiều Core thì có chạy Concurrent nhanh hơn. Tuy vậy cần lưu ý, nếu ta tạo ra số Thread nhiều hơn số Core hoặc số Hyper-Threading của CPU thì ta sẽ lại cần tới Context Switch và tốc độ sẽ lại giảm (Context Switch sẽ cần sao lưu và load lệnh mới lên CPU nên chạy chậm). Nên Best Practice là ta giới hạn số Thread (Thread pool) bằng số Core hoặc Hyper-Threading của CPU.
Vấn đề của Thread
Chính vì nhiều Thread dùng chung một vùng nhớ, nên ta dẫn tới bài toán Race Condition. Ví dụ như khi 2 Thread cùng muốn ghi vào một vùng nhớ 2 giá trị khác nhau. Do chúng chạy cùng lúc kết hợp với cơ chế tối ưu code của ngôn ngữ, cơ chế phân việc của CPU và Context Switch, cơ bản là ta không thể dự đoán được giá trị nào sẽ được ghi vào trước và giá trị nào sẽ được ghi vào sau.
Semaphore
Đây là một phương pháp tương đối lâu đời để tiếp cận vấn đề này, với ý tưởng chính là dựa vào Signal để kiểm tra xem Thread có được phép tác động vào vùng nhớ hay không. Để đơn giản vấn đề, mình sẽ nói tới CPU 1 Core với cơ chế Context Switch giữa các Thread, đối với nhiều Core hơn cũng sẽ tương tự. Một điểm cần lưu ý là phương pháp này thường sẽ được implement ở OS (Kernel).
Binary Semaphore
Ở trong phương pháp này ta sẽ cần 2 hàm P() và V(), và chúng sẽ cùng truy cập vào một vùng nhớ được phần cứng hỗ trợ để luôn truy cập tuần tự. Vùng nhớ này ban đầu sẽ có giá trị 1. Khi Thread 1 bắt đầu sẽ gọi hàm P(), thì hàm này sẽ ghi vào vùng nhớ giá trị 0. Nếu CPU Context Switch tới một Thread khác lúc Thread 1 chưa gọi tới hàm V() thì nếu Thread này có gọi hàm P() sẽ bị dừng lại (Lock) và chờ tới khi vùng nhớ có giá trị thành 1. Sau đó CPU Context Switch lại Thread 1 và nó chạy tới hàm V() thì hàm này sẽ ghi vào vùng nhớ giá trị 1 và từ lúc này nếu CPU Context Switch tới bất kì Thread nào gọi hàm P() thì sẽ được chạy (Unlock).
Ý tưởng cơ bản của phương pháp này là sử dụng hàm P() nhằm Lock các Thread khác để đợi Thread hiện tại truy cập xong vào vùng nhớ. Sau đó để Unlock sẽ gọi hàm V().
Counting Semaphore
Phương pháp này tương tự như phương pháp trên nhưng thay vì giá trị ban đầu là 1 thì ta có thể cho nó là một giá trị n. Khi này mỗi khi hàm P() được gọi thì giá trị sẽ giảm đi 1 tới giá trị bằng 0 nghĩa là những Thread khác gọi P() sẽ phải đợi tới khi giá trị này lớn hơn 0.
Vấn đề
- Bởi vì các Thread đều có thể gọi hàm
V()nên sẽ xảy ra trường hợp, Thread 1 chưa chạy xong đã có 1 Thread khác gọi hàmV()khiếp cho các Thread đang bị Lock có thể truy cập vào được.
Mutex
Để giải quyết vấn đề trên Mutex có thêm một điều kiện đó là việc Unlock phải do đúng Thread nào gọi hàm Lock thực hiên (Ownership). Để làm được điều này Mutex không chỉ cần một giá trị là số mà phải cần cả một Object để lưu thông tin của Thread. Vì vậy nên cơ chế của Mutex tương đối giống Binary Semaphore nhưng có thêm Ownership. Tương tự như Semaphore phương pháp này cũng sẽ được implement ở OS (Kernel).
Vấn đề
- Đối với các tính toán đơn giản trong cùng vùng nhớ việc phải gọi tới OS ABI, khiến cho code chạy rất chậm.
Deadlock
Tuy cả 2 phương pháp trên đều phần nào giải quyết được bài toán về truy cập vùng nhớ trong Concurrent nhưng cũng vì sử dụng cơ chế Lock nên nếu người lập trình thực hiện sai sẽ dễ xảy ra hiện tượng Deadlock. Đây là khi hàm Unlock không bao giờ được gọi và tất cả các Thread đều đợi nhau.
Spinlock
Trong cả 2 cơ chế Semaphore và Mutex ta đều cần phải có hệ điều hành hỗ trợ trong việc Lock hoặc Unlock các Thread. Nên nếu người dùng muốn tự implement việc Lock một đoạn code lại thì sẽ cần phải sử dụng tới phương pháp Spinlock. Nghĩa là một vòng While chạy để check một biến điều kiện. Chính vì lý do này Spinlock thường sẽ hiệu quả đối với các đoạn code chạy nhanh nghĩa là nó sẽ xong trước khi bị CPU Context Switch.
Phương pháp này cũng cần thiết đối với các Thread không được phép lock hay sleep do chúng cũng cần handle những sự kiện khác trong hệ thống. Đối với những đoạn code chạy nhanh thì Spinlock sẽ chạy nhanh hơn Mutex do không cần gọi tới OS ABI.
Vấn đề
- Tuy không bị Deadlock nhưng việc chạy vòng While lại có thể đẫn tới Memory Leak nếu vòng While không bao giờ dừng.
- Ngoài ra lúc dùng Spinlock thì CPU cũng sẽ chạy rất nhiều dù trong Thread không thể truy cập vào vùng nhớ.
- Spinlock sẽ chỉ phù hợp với CPU có nhiều Core, và các Thread được phân bố đều trên các Core.
Atomic
Khác với những phương pháp ở trên Atomic không Lock Thread (Lock-Free), và để thực hiện được điều này, ta sẽ cần CPU hỗ trợ lệnh để thực hiện các phép toán Atomic. Vì lý do này nên Atomic chạy rất nhanh, nhanh hơn cả Spinlock do cần ít lệnh hơn và không cần phải Lock các Thread bằng vòng lặp tốn nhiều CPU.
Một điểm bạn cần lưu ý đó là CPU hỗ trợ rất hạn chế các kiểu dữ liệu nên Atomic chỉ không Lock Thread đối với các kiểu dữ liệu đó thôi. Còn lại các kiểu đữ liệu nâng cao hơn sẽ tùy thuộc cách implement của ngôn ngữ lập trình mà nó có thể Lock Thread hoặc không Lock Thread.
Beyond
- Một điểm mà ta ít để ý tới, đó là dù với phương pháp nào thì cơ chế chung đều là giải quyết việc vùng nhớ có thể bị thay đổi (mutable). Nhưng đối với Functional Language đa số vùng nhớ đều (immutable) nên sẽ không xảy ra trường hợp như vậy.
- Đôi khi bạn muốn cho phép nhiều Thread cùng read một vùng nhớ nhưng chỉ có một Thread được write vào vùng nhớ đó. (Read-Write lock).
- Đối với các cấu trúc dữ liệu như mảng hay link list, việc Lock cả một vùng nhớ lớn như vậy có thể rất lãng phí nên ta thường sẽ cố gắng tối giản hóa vùng nhớ cần phải Lock lại như một ô trong mảng hay các node liền kề trong link list.
Tổng kết
Đối với các phép tính đơn giản ta nên sử dụng Atomic, nếu phép tính phức tạp những đoạn code vẫn chạy nhanh thì ta có thể nghĩ tới Spinlock. Trong hầu hết trường hợp còn lại Mutex thường sẽ là lựa chọn đầu tiên khi nghĩ tới trừ khi bạn phải xử lý nhiều vùng nhớ cho nhiều Thread hoặc có lý do chính đáng để sử dụng Semaphore.