Tính toán song song
Bối cảnh > Race conditions, mutual exclusion, synchronization, và parallel slowdown

Công việc phụ trong một chương trình song song thường được gọi là threads. Một số kiến trúc máy tính song song sử dụng các phiên bản nhỏ và nhẹ hơn gọi là fibers, trong khi các phiên bản lớn được gọi là processes. Tuy nhiên, "threads" thường được chấp nhận như một thuật ngữ chung cho các công việc phụ. Threads sẽ phải thường xuyên cập nhật các biến được chia sẻ giữa chúng. Các chỉ lệnh giữa hai chương trình có thể được xen kẽ theo bất kỳ thứ tự nào. Ví dụ, xem chương trình sau đây:
| --- | --- |
Thread A: Thread B
1A: Read variable V: 1B: Read variable V
2A: Add 1 to variable V: 2B: Add 1 to variable V
3A Write back to variable V: 3B: Write back to variable V
Nếu chỉ lệnh 1B được thực hiện giữa 1A và 3A, hoặc nếu chỉ lệnh được thực hiện giữa 1B và 3B, chương trình sẽ tạo ra dữ liệu không chính xác. Đây được gọi là một race condition. Chương trình sẽ phải sử dụng khóa để cung cấp mutual exclusion. Khóa là một cấu trúc ngôn ngữ lập trình cho phép một thread kiểm soát một biến và ngăn ngừa các biến khác đọc hoặc ghi nó, cho đến khi biến đó được mở khóa. Thread giữ khóa có thể hoàn toàn thoải mái truy cập phần tới hạn của nó (phần của chương trình yêu cầu quyền truy cập chuyên biệt tới một số biến), và mở khóa các dữ liệu khi nó được hoàn tất. Vì vậy, để đảm bảo chương trình thực hiện chính xác, chương trình trên có thể được viết lại để sử dụng khóa:
| --- | --- |
Thread A: Thread B
1A: Lock variable V: 1B: Lock variable V
2A: Read variable V: 2B: Read variable V
3A: Add 1 to variable V: 3B: Add 1 to variable V
4A Write back to variable V: 4B: Write back to variable V
5A: Unlock variable V: 5B: Unlock variable V
Một thread sẽ khóa biến V thành công, trong khi các thread khác sẽ bị khóa lại—không thể truy cập cho đến khi V được mở khóa. Điều này đảm bảo chương trình được thực hiện đúng. Để đảm bảo chương trình thực hiện chính xác, khóa rất có thể sẽ làm chậm chương trình khi cần thiết.
Khóa nhiều biến bằng cách sử dụng phương pháp khóa non-atomic có khả năng tạo ra một deadlock. Một khóa atomic khóa nhiều biến cùng một lúc. Nếu nó không thể khóa một trong số các biến đó, nó sẽ không khóa biến nào. Nếu hai thread cùng khóa hai biến giống nhau bằng khóa non-atomic, có khả năng một thread sẽ khóa một biến và thread thứ hai sẽ khóa biến còn lại. Trong trường hợp này, không thread nào có thể hoàn tất, và kết quả là deadlock.
Nhiều chương trình song song yêu cầu các công việc phụ act in synchrony (thực hiện đồng bộ). Điều này đòi hỏi việc sử dụng một barrier (hàng rào). Những barrier thường được tạo ra bằng cách sử dụng khóa phần mềm. Một lớp của thuật toán, được gọi là lock-free and wait-free algorithms, hoàn toàn có thể tránh được việc sử dụng khóa và barrier. Tuy nhiên, cách tiếp cận này thường khó thực hiện và yêu cầu thiết kế cấu trúc dữ liệu một cách chính xác.
Không phải tất cả mọi song song hóa đều cho kết quả tăng tốc độ. Nói chung, khi một công việc được chia ra thành càng nhiều thread, thì thời gian những thread đó sử dụng để kết nối với nhau sẽ ngày càng tăng. Suy cho cùng, tổng chi phí từ việc kết nối vượt trội thời gian sử dụng để giải quyết vấn đề, và song song hóa hơn nữa (nghĩa là, tách khối lượng công việc thành nhiều thread hơn) sẽ là tăng hơn là giảm thời gian cần thiết để hoàn thành. Đây được gọi là parallel slowdown.