Test-and-Set được sử dụng để làm gì?

Question

Sau khi đọc bài kiểm tra và đặt Wikipedia entry, tôi vẫn còn câu hỏi "Bộ kiểm tra và tập hợp sẽ được sử dụng để làm gì?"

Tôi nhận thấy rằng bạn có thể sử dụng nó để triển khai Mutex (như được mô tả trong wikipedia), nhưng sử dụng những ứng dụng nào khác?

Answer 1

Bạn sử dụng nó bất kỳ lúc nào bạn muốn ghi dữ liệu vào bộ nhớ sau khi thực hiện một số công việc và đảm bảo một luồng khác chưa ghi đè điểm đến kể từ khi bạn bắt đầu. Rất nhiều lock/mutex-free algorithms mang biểu mẫu này.

Answer 2

Về cơ bản, việc sử dụng nó là chính xác đối với các mutex, do tầm quan trọng to lớn của nguyên tử. Đó là nó. Kiểm tra và đặt là một hoạt động có thể được thực hiện với hai hướng dẫn khác, không nguyên tử và nhanh hơn (nguyên tử mang chi phí phần cứng khi sử dụng hệ thống đa xử lý), vì vậy thông thường bạn sẽ không sử dụng nó vì các lý do khác.

Answer 3

Ví dụ tốt là "tăng".

Giả sử hai chủ đề thực thi a = a + 1. Nói a bắt đầu bằng giá trị 100. Nếu cả hai chủ đề đang chạy cùng một lúc (đa lõi), cả hai đều sẽ tải a là 100, tăng lên 101 và lưu trữ lại số đó trong a. Sai rồi!

Với thử nghiệm và đặt, bạn đang nói "Đặt a thành 101, nhưng chỉ khi hiện tại có giá trị 100." Trong trường hợp này, một chủ đề sẽ vượt qua bài kiểm tra đó nhưng bài khác sẽ thất bại. Trong trường hợp lỗi, luồng có thể thử lại toàn bộ câu lệnh, lần này là a là 101. Sự thành công.

này thường là nhanh hơn so với sử dụng một mutex vì:

1. Hầu hết thời gian đó không phải là một tình trạng chủng tộc, vì vậy việc cập nhật xảy ra mà không cần phải mua một số loại mutex.
2. Ngay cả trong khi va chạm, một luồng không bị chặn, và nhanh hơn đối với các luồng khác chỉ cần quay và thử lại hơn là nó sẽ tự treo trong dòng cho một số mutex.

Answer 4

Được sử dụng khi bạn cần nhận giá trị được chia sẻ, làm điều gì đó với nó và thay đổi giá trị, giả sử một chủ đề khác chưa thay đổi nó.

Để sử dụng thực tế, lần cuối tôi nhìn thấy nó đang được triển khai các hàng đợi đồng thời (hàng đợi có thể được đẩy/mở bởi nhiều luồng mà không cần ẩn dụ hoặc mutex).

Tại sao bạn sử dụng TestAndSet thay vì một mutex? Bởi vì nó thường đòi hỏi ít chi phí hơn một mutex. Khi một mutex yêu cầu sự can thiệp của hệ điều hành, một TestAndSet có thể được thực hiện như một lệnh nguyên tử duy nhất trên CPU. Khi chạy trong môi trường song song với 100 chủ đề, một mutex duy nhất trong một phần quan trọng của mã có thể gây tắc nghẽn nghiêm trọng.

Answer 5

Hãy tưởng tượng bạn đang viết đơn đăng ký ngân hàng và đơn đăng ký của bạn có yêu cầu rút 10 bảng Anh (có, tôi là tiếng Anh;)) từ tài khoản. Vì vậy, bạn cần phải đọc số dư tài khoản hiện tại vào một biến địa phương, trừ rút tiền và sau đó viết số dư trở lại bộ nhớ.

Tuy nhiên, nếu khác, yêu cầu đồng thời xảy ra giữa bạn đọc giá trị và bạn viết nó ra sao? Có khả năng kết quả của yêu cầu đó sẽ bị ghi đè hoàn toàn bởi lần đầu tiên và số dư tài khoản sẽ không chính xác.

Kiểm tra và đặt sẽ giúp chúng tôi khắc phục sự cố đó bằng cách kiểm tra xem giá trị ghi đè của bạn có phải là giá trị bạn nghĩ không. Trong trường hợp này, bạn có thể kiểm tra số dư là giá trị ban đầu mà bạn đã đọc. Vì nó là nguyên tử, nó không bị gián đoạn nên không ai có thể kéo tấm thảm ra từ dưới bạn giữa đọc và viết.

Một cách khác để khắc phục sự cố tương tự là lấy ra một khóa trên vị trí bộ nhớ. Thật không may, ổ khóa là rất khó khăn để có được quyền, khó có lý do về, có vấn đề khả năng mở rộng và hành xử xấu khi đối mặt với thất bại, vì vậy họ không phải là một giải pháp lý tưởng (nhưng chắc chắn thực tế). Các phương pháp thử nghiệm và thiết lập tạo thành cơ sở của một số Kỷ niệm Giao dịch Phần mềm, cho phép mọi giao dịch thực hiện đồng thời một cách lạc quan, với chi phí cho việc chuyển chúng trở lại nếu chúng xung đột.