Fun with Concurrency and Parallel programing các ứng dụng multi-threaded

Tôi chắc hầu hết các bạn đều biết và từng làm việc với thread, cùng với đó là các ứng dụng multi-threaded. Tuy nhiên không phải ai cũng hiểu rõ bản chất của thread. Thậm chí có nhiều bạn đã đi làm một vài năm và sử dụng thread thường xuyên vẫn mơ hồ rằng thread giúp ứng dụng chạy nhanh hơn vì nó giúp code chạy song song. Chương trình chạy chậm, cần nhanh hơn? Thêm thread. Chương trình cần làm nhiều tác vụ khác nhau? Thêm thread. Monitor thấy CPU 90% là rảnh rỗi (idle), bắt nó hoạt động tối ưu hơn? Thêm thread. NO, YOU ARE WRONG.

Để hiểu khi nào thì ứng dụng multi-threaded sẽ chạy nhanh hơn, khi nào việc tăng thread có hiệu quả, khi nào không, bạn cần hiểu rõ hai khái niệm concurrency programing và parallel programing. Đã có quá nhiều bài viết kĩ thuật về chủ đề này rồi và tôi không có ý định bổ sung thêm nữa. Hôm nay tôi muốn giới thiệu với các bạn chủ đề này thông qua một câu chuyện.

Câu chuyện cửa hàng trà sữa

Ở một thị trấn nọ có anh A quyết định mở một cửa hàng trà sữa. Tìm hiểu trên mạng, anh mua được một loại máy pha trà sữa ngon không kém gì người pha, mà lại sử dụng cực kỳ đơn giản, chỉ cần cho các nguyên liệu cần thiết vào, bấm nút là có ngay một cốc. Do ban đầu ít vốn anh chỉ mua một chiếc.

Chiếc máy cần có người vận hành và cửa hàng cũng cần có người bán hàng cho khách, anh thuê một nhân viên. Cửa hàng của anh có một ô cửa kính nhỏ để nhân viên bán hàng cho khách, khách hàng muốn mua sẽ order qua ô cửa này và đợi nhận trà. Nếu có nhiều khách hàng họ buộc phải xếp hàng theo hàng một, người phía trước chưa mua xong thì người phía sau chưa thể mua.

Ta có thể hình dung quá trình hoạt động bán trà sữa này như là một ứng dụng, cửa hàng như là một task (hay process). Chiếc máy pha trà kia là tài nguyên chung (chia sẻ) trong máy tính. Mỗi ô cửa đóng vai trò như là một thread thực thi. Các nhân viên đóng vai trò là CPU, mỗi nhân viên là một core. Các order từ khách hàng có thể coi như là các input, yêu cầu từ người dùng, hay các command. Mỗi nhân viên chỉ có thể phục vụ một khách hàng tại một ô cửa ở một thời điểm, tương tự như cách mỗi core CPU sẽ thực hiện tuần tự các lệnh.

Multi-threaded

Nhận thấy số khách đến mua trà quá đông và xếp hàng quá dài, anh A quyết định bổ sung thêm một ô cửa để khách đứng mua hàng, đó chính là multi-threaded. Tuy nhiên vì vẫn chỉ có một nhân viên, cậu này sẽ phải cùng lúc bán hàng cho khách ở cả hai ô cửa. Trong khi nhận yêu cầu từ ô cửa thứ nhất và chuẩn bị trà cho khách, cậu vẫn phải quay sang ô cửa thứ hai để phản hồi yêu cầu của khách hàng. Đây chính là concurrency programing.

Concurrency programing

Về cơ bản, nếu là khách hàng bạn sẽ cảm thấy cậu nhân viên này đang làm hai việc song song, bán hàng cho khách ở cả hai ô cửa. Trên thực tế thì cậu ta chỉ có thể bán hàng cho một khách tại một thời điểm mà thôi, khách ở cửa hàng còn lại vẫn phải đợi. Tuy nhiên vì cậu ta cứ liên tục quay sang cười và nói: “Anh thông cảm đợi em chút” với họ nên khách cảm thấy mình vẫn được đón tiếp và sẵn sàng đợi.

Context switching

Trong quá trình làm việc, vì làm nhiều việc một lúc dẫn tới cậu hay bị quên. Ví dụ khi đang chuẩn bị trà cho khách ở ô cửa thứ nhất, cậu nhận order của khách ở ô cửa còn lại. Sau khi đưa trà cho khách ở ô cửa thứ nhất, cậu nhận tiền rồi chưa kịp thối lại, cậu liền chuẩn bị trà cho khách ở ô cửa thứ hai luôn. Nhưng cậu lại quên mất order của khách ở ô cửa thứ hai và phải hỏi lại, thế là mất thêm một chút thời gian. Chuẩn bị trà ở ô cửa thứ hai xong, cậu mới quay lại thối tiền cho khách ở ô cửa thứ nhất. Nhưng cậu lại quên mất khách vừa đưa mình bao tiền =)). Cậu đành hỏi lại khách, dĩ nhiên là ăn chửi vì vừa quên và vì để khách đợi lâu. Mất thời gian vì những việc không cần thiết như hỏi lại khách, giải thích và xin lỗi… khiến thời gian phục vụ 2 cốc trà của cậu nhân viên này thậm chí lâu hơn cả so với khi cậu phục vụ tuần tự 2 khách ở cùng một ô cửa.

Ví dụ có vẻ không thực tế cho lắm nhưng đây là minh họa cho context switch. Việc chuyển qua lại liên tục giữa các thread tốn nhiều chi phí. Mỗi thread duy trì một danh sách các biến và trạng thái của riêng nó, mỗi khi CPU chuyển về một thread, nó cần phục hồi lại các trạng thái này. Việc này dẫn tới trong thực tế có những ứng dụng multi-threaded lại chậm hơn so với single-threaded.

Parallel programing

Nhận thấy khách hàng ngày càng đông và cậu nhân viên của mình có vẻ quá tải, anh A quyết định thuê thêm một nhân viên nữa. Mỗi nhân viên sẽ phụ trách việc bán hàng ở một ô cửa. Như mô tả ở trên, ta coi một nhân viên như là một core của CPU thì việc thuê thêm nhân viên giúp ta có một hệ thống multi-core.

Lúc này việc bán hàng mới thực sự diễn ra hoàn toàn đồng thời. Mỗi nhân viên phục vụ khách hàng của mình tại cùng một thời điểm mà không cần phải chờ đợi, phụ thuộc nhau. Không có chi phí cho context switch do mỗi nhân viên không cần phải quân tâm về công việc của nhân viên kia ở cửa còn lại. Đó chình là parallel programing.

Volatile variable in Java

Một số ví dụ và khái niệm ở phần này có thể chỉ đúng trong Java, bạn có thể bỏ qua nếu không quan tâm về Java.

Chiếc máy pha trà sữa mỗi ngày chỉ có thể pha được tối đa 100 cốc. Trong cửa hàng có một bảng nhỏ cho biết số cốc còn có thể pha được. Mỗi nhân viên sau khi bấm nút pha một cốc sẽ update số cốc còn lại vào bảng này. Mỗi khi khách hỏi, nhân viên phải nhìn lại bảng kia để biết còn trà bán hay không.

Để tiết kiệm thời gian, mỗi nhân viên sẽ nhớ số cốc còn có thể bán được bằng cách nhớ trong đầu thay vì đọc lại từ bảng. Mỗi lần bán một cốc, nhân viên sẽ giảm số cốc nhớ được ấy đi một. Tuy nhiên sẽ xảy ra trường hợp như sau: nhân viên thứ nhất lần cuối nhìn bảng nhớ rằng còn 10 cốc để bán, sau khi bán 5 cốc cậu ta nghĩ rằng còn 5 cốc nữa để bán và vẫn nhận order từ khách. Cậu không biết rằng trong khi mình bán 5 cốc thì cậu nhân viên còn lại cũng bán được 5 cốc. Vì chỉ nhớ trong đầu và không đọc lại cũng không cập nhật giá trị số cốc mới nhất của mình vào bảng, cả hai nhân viên đều tính toán sai số cốc trà còn lại.

Để ý rằng vấn đề này chỉ xảy ra nếu có từ hai nhân viên trở lên. Nếu chỉ có một nhân viên phục vụ ở cả hai cửa thì việc cậu ta nhớ số cốc trong đầu không hề ảnh hưởng gì mà còn giúp cho hiệu quả làm việc tốt hơn nhiều (không phải cập nhật lại bảng liên tục). Đây chính là vấn đề có thể xảy ra với ứng dụng multi-threaded khi chạy trên một hệ thống multi-core, khi hai hay nhiều thread chia sẻ tài nguyên chung.

Ở đây tài nguyên chung chính là số cốc trà còn lại, có thể coi như là một biến. Việc các nhân viên cố gắng nhớ số cốc còn lại trong đầu để tăng hiệu quả công việc chính là cách mà compiler đã làm để optimize code của bạn. Mỗi thread sẽ tìm cách copy các biến vào vùng nhớ CPU cache trong khi làm việc để tăng tốc độ xử lý thay vì đọc ghi trực tiếp vào vùng nhớ của biến đó trên RAM. Ở đây trí nhớ của 2 nhân viên đóng vai trò là CPU cache, chiếc bảng ghi số cốc trà còn lại đóng vai trò như bộ nhớ RAM.

Để giải quyết tình trạng này, anh A (chủ quán) yêu cầu mỗi nhân viên phải kiểm tra số cốc còn lại trên bảng trước khi nhận order và cập nhật lại giá trị mới vào bảng ngay sau khi nhận order từ khách. Lúc này quy trình sẽ là: kiểm tra số cốc còn lại trên bảng -> nhận order -> bấm nút pha trà -> cập nhật số cốc còn lại vào bảng. Số cốc trà còn lại trên bảng chính là một biến volatile.

Race condition và synchonize lock

Race condition

Mặc dù đã yêu cầu nhân viên phải cập nhật lại kết quả trên bảng trước và sau khi bán mỗi cốc, sai lệch vẫn xảy ra. Hãy xét ví dụ sau: nhân viên thứ nhất (gọi tắt là NV1) trước khi nhận order đã kiểm tra bảng và biết rằng còn 2 cốc trà để bán, theo đúng quy trình NV1 nhận order của khách và bấm nút pha trà. Trong lúc đấy nhân viên thứ hai (ở ô cửa khác, gọi tắt là NV2) cũng nhận order từ khách, vì NV1 chưa kịp cập nhật cốc trà mới nhất vừa bán được, NV2 kiểm tra bảng và cũng nghĩ rằng còn 2 cốc trà. Sau khi bấm nút, NV1 cập nhật vào bảng còn 1 cốc. Đến lượt NV2 vì vẫn nghĩ trong đầu rằng trước đó còn 2 cốc nên NV2 cũng cập nhật vào bảng còn 1 cốc mặc dù đúng ra thì phải là 0.

Nghe có vẻ không thực tiễn cho lắm vì vấn đề trên có thể giải quyết dễ dàng nếu nhân viên nhận thấy số trên bảng và số mình sắp cập nhật vào không hợp lí với nhau. Tuy nhiên đây chỉ là ví dụ mà tôi cố gắng để minh họa cho khái niệm race condition, vấn đề có thể xảy ra khi một hoặc nhiều threads cùng lúc cố gắng thay đổi một tài nguyên chia sẻ (giá trị trên bảng). Để cho thực tế hơn thì ta hãy cứ giả dụ rằng nhân viên rất vội nên không thể nào kiểm tra lại tính bất hợp lí giữa số trên bảng và số họ sắp ghi vào, tất cả những gì họ có thể làm là xóa số cũ đi và ghi lại số mà họ nghĩ là số cốc còn lại bây giờ ở trong đầu.

Locks and Synchronization

Để giải quyết triệt để tình trạng trên, anh A chủ quán nghĩ ra một cách. Sau khi nhân viên kiểm tra số cốc còn lại để bán trên bảng, nhân viên đó phải tìm cách lấy chiếc bút duy nhất để ghi được vào bảng trước khi nhận order từ khách. Nếu chiếc bút đã bị lấy bởi nhân viên khác, nhân viên này sẽ phải đợi cho tới khi chiếc bút được trả lại. Chỉ khi lấy được chiếc bút thì nhân viên mới được phép nhận order, ai đến trước thì sẽ lấy trước. Sau khi nhận order và bấm nút pha trà xong, nhân viên đang giữ chiếc bút cập nhật lại số cốc trà còn lại vào bảng và bắt buộc phải trả lại chiếc bút cho nhân viên khác đang chờ.

Lại tiếp tục là một ví dụ không thực tiễn lắm nhưng ta hãy tạm bỏ qua điều đó. Chiếc bút ở đây đóng vai trò như là lock hay mutex, nó bảo đảm rằng chỉ có một nhân viên được tác động vào giá trị trên bảng tại một thời điểm.

Rõ ràng cách trên giải quyết được vấn đề tranh chấp tài nguyên chung và ngăn chặn sai lệch nhưng lại khiến cho hiệu quả làm việc của quán giảm đi khi các nhân viên phải chờ đợi nhau để giành được quyền ghi vào bảng. Ngoài ra thao tác lấy chiếc bút, trả lại chiếc bút cũng khiến nhân viên tốn thêm thời gian. Đây cũng là vấn đề xảy ra khi bạn sử dụng lock trong các ứng dụng multi-threaded.

Hạn chế chia sẻ tài nguyên chung

Có một giải pháp không cần sử dụng lock mà vẫn có thể tránh được race condition là không sử dụng tài nguyên chia sẻ. Trong câu chuyện bán trà sữa, tài nguyên chia sẻ của chúng ta là chiếc bảng và chiếc máy pha trà. Bằng cách coi các tài nguyên này chỉ của riêng một nhân viên (tạm gọi NV1), các nhân viên khác khi muốn cập nhật giá trị số cốc còn lại trên bảng hay nhấn nút pha trà đều phải thông qua NV1 này. Các nhân viên sẽ giao tiếp với nhau thông qua lời nói. Hạn chế của phương pháp này là NV1 chỉ có thể làm mọi thứ tuần tự, nên việc các yêu cầu từ các nhân viên khác không thể được thực hiện ngay thời điểm họ đề nghị mà bắt buộc phải chờ đợi.

Giải pháp trên minh hoạ cho hoạt động của một số ứng dụng multi-threaded ngày nay khi giao tiếp giữa các thread hoàn toàn thông qua message, khi cần đọc ghi tài nguyên dùng chung sẽ được copy và gửi dưới dạng một message thay vì các thread tự đọc trực tiếp vào tài nguyên này. Điển hình cho cơ chế này là mô hình event-bus, mô hình channel để giao tiếp giữa các goroutine trong Golang, hay một số mô hình message-based sử dụng trong các ngôn ngữ dạng hướng hàm (functional programing)…

Multi-process

Nhờ quán đông khách, anh A kiếm được một số tiền lớn, anh quyết định mở rộng kinh doanh bằng cách mở thêm một cửa hàng khác ở phía đối diện cửa hàng cũ. Dĩ nhiên quán này cũng có một chiếc máy pha trà sữa riêng. Nhưng anh tính rằng cửa hàng mới này chưa chắc đã đông như cửa hàng cũ nên chỉ thuê trước một nhân viên mặc dù nó vẫn có hai ô cửa để bán.

Tuy nhiên mọi thứ vượt ngoài dự tính của anh ta khi quán thứ hai nhiều thời điểm còn đông khách hơn quán thứ nhất. Thế là những lúc đó anh phải điều một cậu nhân viên từ quán thứ nhất sang quán thứ hai để hỗ trợ, sau khi đỡ khách thì lại quay về quán thứ nhất. Rõ ràng việc chạy đi chạy lại thế này khiến năng suất làm việc của nhân viên này rất không hiệu quả. Đây vẫn là vấn đề của context switch, nhưng lúc này chi phí sẽ cao hơn nhiều so với khi nhân viên này chuyển qua lại giữa hai ô cửa.

Như đã giới thiệu ở phần đầu, nếu coi quá trình vận hành của quán như một tiến trình (process) thì việc mở và đưa vào hoạt động thêm quán thứ hai chính là multi-process (ở đây là của cùng một ứng dụng bán trà sữa). Ví dụ trên cho thấy rằng context switch để phục hồi trạng thái của process cao hơn nhiều so với thread.

Nếu bạn để ý thì ở quán thứ hai mới mở chúng ta có một chiếc máy pha trà sữa riêng. Tương tự với process, các process cũng không chia sẻ tài nguyên chung. Các vấn đề như race condition hay dead lock không xảy ra với multi-process. Nhược điểm là các process chạy hoàn toàn độc lập vì không chia sẻ tài nguyên chung. Nếu máy pha trà sữa ở quán thứ nhất đã pha đủ 100 cốc, không thể lấy trà từ quán thứ hai sang để đem bán (trong thực tế là có thể =]]).

CPU-bound IO-bound application

CPU-bound application

Tiếp tục với câu chuyện trên, quay trở lại thời điểm đầu khi mới mở quán và chỉ có một nhân viên với hai ô cửa. Tại sao nhận thấy rằng việc để một nhân viên phải làm việc với khách hàng ở cả hai cửa có thể làm giảm tốc độ bán hàng đi nhưng anh chủ quán vẫn làm. Vì nó giúp khách hàng cảm thấy mình sắp có cơ hội mua được hàng hơn. Nếu bạn nhìn thấy 2 hàng mỗi hàng 25 người bạn sẽ cảm thấy mình sẽ nhanh chóng mua được hàng hơn so với việc phải xếp vào 1 hàng 50 người? Tôi không chắc về điều này lắm nhưng với cá nhân tôi thì là thế. Thêm nữa mặc dù nhân viên không thể bán hai cốc trà cùng một lúc cho hai khách ở hai ô cửa nhưng ít ra có thể trả lời họ, khiến họ cảm thấy mình được phản hồi.

Dễ thấy, nếu bỏ qua các yếu tố khách quan, việc quán bán được nhiều hay ít cốc trà hoàn toàn phụ thuộc vào khả năng của nhân viên. Nếu cậu ta xử lý các khâu bấm nút pha trà, đóng gói, lấy ống hút, thu và trả lại tiền… nhanh chóng, số khách cậu ta đáp ứng được sẽ cao hơn so với một nhân viên làm các thao tác kia chậm hơn. Khả năng của mỗi nhân viên là giới hạn, vì thế trong trường hợp này việc cố gắng mở thêm các ô cửa không giúp gì trong việc tăng tốc bán hàng, quá nhiều ô cửa thậm chí khiến hiệu quả bị giảm đi.

Ta gọi các ứng dụng mà thời gian xử lý của nó phụ thuộc hoàn toàn vào khả năng của CPU như ứng dụng bán trà sữa này là CPU-bound application.

IO-bound application

Tuy nhiên, trong thực tế thì năng lực của nhân viên không phải là tất cả. Từ đầu tới giờ ta chưa nói nhiều tới chiếc máy pha trà. Chiếc máy này có thể đáp ứng được nhiều yêu cầu một lúc, tuy nhiên sẽ mất một khoảng thời gian t để pha được một cốc trà. Không có cách gì để giảm thời gian t này xuống. Nhân viên sau khi nhận order từ khách, bấm nút và phải chờ để máy pha xong trước khi đưa cho khách hàng và thu tiền. Vì ta quy định mỗi nhân viên chỉ phục vụ một khách ở một ô cửa tại một thời điểm, nên nhân viên không thể nhận order từ khách phía sau khi khách phía trước chưa nhận được trà. Nhân viên mất nhiều thời gian chết để chờ máy pha trà, đó chính là wait-for-IO.

Lúc này, việc mở thêm một ô cửa và để một nhân viên chịu trách nhiệm cho vài ô cửa lại trở nên hợp lí. Nhân viên sẽ nhận order từ ô cửa thứ nhất, bấm nút pha trà, nhưng thay vì đợi trà, cậu ta sẽ tranh thủ thời gian đó để nhận order từ ô cửa thứ hai. Khi nhận được tín hiệu trà đã xong, cậu quay lại đưa trà và nhận tiền cho khách ở ô cửa thứ nhất. Thời gian chờ để pha một cốc trà càng lâu thì việc mở thêm các ô cửa càng hiệu quả.

Tín hiệu báo trà xong ở đây gọi là interupt. Nếu bạn nào từng làm việc sâu với OS-level hoặc làm nhúng thì sẽ quen thuộc với khái niệm này. Quá trình chuyển qua lại giữa các threads, process của CPU gọi là scheduling, đây là một trong các bài toán nổi tiếng mà chắc các bạn đều nghe tới là “bài toán lập lịch CPU”. Trong thực tế các thuật toán cho quá trình này phức tạp hơn nhiều chứ không chỉ đơn giản là schedule khi có IO và ngắt (interupt). Đi sâu vào các khái niệm này vượt quá khuôn khổ của bài viết, các bạn có thể tự tìm hiểu thêm tại đây;

Ta gọi các ứng dụng mà thời gian xử lý phụ thuộc nhiều vào các thao tác IO như ví dụ trên là IO-bound application. Cũng từ ví dụ trên bạn có thể thấy rằng multi-threaded sẽ rất hiệu quả cho các ứng dụng làm việc nhiều với IO, muốn tận dụng tối đa hiệu năng của CPU.

Kết luận

Mặc dù bị ảnh hưởng bởi context switch nhưng multi-threaded và multi-process là cần thiết trong các multi-tasking operating system (hệ điều hành hỗ trợ đa nhiệm) từ khi CPU chỉ có một core cho tới các hệ thống multi-core hiện tại khi mà số lượng task cần thực hiện đồng thời luôn lớn hơn rất nhiều so với số core. Multi-tasking cũng giúp tối ưu hóa việc sử dụng CPU trong các ứng dụng IO-bound và bảo đảm responsive cho tất cả các task. Quan trọng vẫn là bạn hiểu và vận dụng được sao cho hiệu quả trong thực tế của mình mà thôi.