Haskell: TVar hoạt động như thế nào?

Question

TVar hoạt động như thế nào? Từ những gì tôi đã đọc nó cố gắng để chạy tất cả các giao dịch ngay lập tức khi nhận được chúng, tuy nhiên, một giao dịch hoàn thành vô hiệu hóa các giao dịch hiện đang chạy khác, mà sau đó phải khởi động lại. Đây có phải là cách TVar hoạt động không?

Nếu đây là trường hợp, nếu có giao dịch 1ms giao dịch dài xảy ra sau mỗi 100ms, điều đó có nghĩa là giao dịch mất 200ms để xử lý sẽ không bao giờ hoàn thành?

Answer 1

Miễn là hai giao dịch truy cập riêng biệt TVars, cả hai có thể được cam kết đồng thời mà không làm mất hiệu lực lẫn nhau.

Chỉ cần để làm cho nó rõ ràng khi một giao dịch là bị vô hiệu, chúng ta hãy xem xét các tình huống sau:

1. Giả sử rằng t :: TVar Int được khởi tạo để 0 và được đọc qua readTVar t vào đầu của một giao dịch A.
2. Trong khi đó, trong một chủ đề khác, giao dịch B được bắt đầu trong đó writeTVar t 1 được thực thi. Giả sử rằng B cam kết trước A. Hệ thống STM sẽ kiểm tra xem có bất kỳ mâu thuẫn nào và kết luận rằng an toàn cho B để cam kết vào thời điểm này, vì vậy bây giờ writeTVar t 1 có hiệu lực.
3. Điều này, tuy nhiên, khiến giao dịch A bị vô hiệu do giá trị cũ 0 của t được đọc vào đầu A. (Nếu A được phép cam kết, chúng tôi sẽ nhận được một sự vi phạm của nguyên tố.)

Các giấy ban đầu [1] trên hệ thống STM Haskell (xem Sec 6.5) trả lời câu hỏi của bạn:

"nạn đói Ví dụ, một giao dịch chạy cho một thời gian rất dài có thể liên tục xung đột với các giao dịch ngắn hơn. Chúng tôi nghĩ rằng nạn đói có vẻ không xảy ra trong thực tế, nhưng chúng tôi không thể nói mà không có thêm kinh nghiệm.

[1] Tim Harris, Simon Marlow, Simon Peyton Jones và Maurice Herlihy. Hội nghị ACM về nguyên tắc và thực hành lập trình song song 2005 (PPoPP'05).

Answer 2

Nếu có giao dịch 1ms giao dịch dài xảy ra sau mỗi 100ms, điều đó có nghĩa là giao dịch mất 200ms để xử lý sẽ không bao giờ hoàn thành?

Giao dịch chỉ xung đột nếu chúng chạm vào cùng TVar s, vì vậy nếu một số giao dịch 1ms tránh tất cả các biến bị ảnh hưởng bởi giao dịch 200ms thì 200ms sẽ có thể hoàn thành. Hơn nữa, kể từ khi STM monad là khá nghiêm ngặt về những gì được cho phép bên trong (chỉ truy cập bộ nhớ và tính toán tinh khiết!) Nó rất khác thường để có sự chênh lệch giữa độ dài của giao dịch; thông thường, họ sẽ chỉ có một vài bộ nhớ đọc/ghi dài, và tất cả các IO và các tính toán khác sẽ được thực hiện bên ngoài giao dịch.Hơn nữa, cho dù một giao dịch cụ thể là bao giờ bị chặn bởi các giao dịch khác là một chút của một vấn đề lập kế hoạch; Tôi không chắc chắn 100% lập lịch trình hiện tại của GHC trông như thế nào, nhưng có vẻ hợp lý là nó có ưu tiên cho các giao dịch cũ hơn (hoặc tỷ lệ thất bại cao hơn).

Điều đó nói rằng, livelock là một vấn đề rất thực tế với STM, và là về ngấm ngầm và khó khăn để lý do về bế tắc trong việc triển khai đồng thời khóa truyền thống hơn.

TVar hoạt động như thế nào?

Có thể bạn sẽ thích this paper.