Cấu trúc dữ liệu chung đồng thời mà không bị deadlocks hoặc mất tài nguyên

Question

Gần đây tôi đã hỏi một số câu hỏi liên quan đến TVar và tôi vẫn lo ngại về livelock.

Vì vậy, tôi nghĩ về cấu trúc này:

1. Mỗi giao dịch được ưu tiên duy nhất (có lẽ được phân bổ theo thứ tự tạo).
2. Giao dịch cố gắng lấy khóa đọc/ghi trên dữ liệu mà họ truy cập. Đương nhiên, đọc đồng thời là okay, nhưng một khóa viết không bao gồm tất cả những người khác (cả đọc và viết).
3. Nói giao dịch A có ưu tiên cao hơn giao dịch B. Nếu A giữ khóa, B đợi, nhưng nếu B giữ khóa và A muốn, B sẽ khởi động từ khóa, A lấy nó và giao dịch B khởi động lại (như với TVar). Tuy nhiên, B vẫn giữ mức độ ưu tiên hiện tại cho việc thử lại.
4. Khi khóa được giải phóng và có các giao dịch đang chờ, nó sẽ chuyển đến giao dịch ưu tiên cao nhất và phần còn lại tiếp tục chờ.

Hệ thống này tôi tin rằng ngăn chặn deadlocks, nhưng cũng ngăn chặn nạn đói (không giống như TVar). Tôi đã tự hỏi nếu có ai đã thực hiện một hệ thống như vậy, vì nó có vẻ khá rõ ràng và tôi không muốn phát minh lại bánh xe.

Tất nhiên, cách tiếp cận này có thể dễ dàng được mở rộng để cho phép người dùng chỉ định mức độ ưu tiên.

Ưu tiên có thể là cặp (user_supplied_prio, auto_increment), với mức ưu tiên là user_supplied_prio, nhưng các tác vụ ưu tiên bằng nhau sẽ được giải quyết theo thứ tự FIFO.

Comment/Giải pháp:

Trên thực tế, khi tôi nghĩ về nó, những gì tôi mô tả đã tồn tại trong Haskell, chỉ đơn giản bằng cách sử dụng một IORef quấn quanh tất cả các dữ liệu, và chỉ sử dụng atomicModifyIORef. atomicModifyIORef sẽ đảm bảo các giao dịch được áp dụng theo thứ tự. Tuy nhiên, người ta có thể nghĩ rằng điều này có nghĩa là cấu trúc dữ liệu được tuần tự (tức là giới hạn hiệu quả cho một luồng) nhưng nó thực sự song song do sự lười biếng.

Để giải thích điều này, hãy xem xét hàm đắt tiền f. Chúng tôi sẽ áp dụng điều này cho một số Data.Map đến dữ liệu có khóa "foo".

Điều này thay thế (foo -> x) bằng (foo -> future(f x)). Chủ đề này sẽ tiếp tục tìm ra những gì thực tế là (f x), nhưng trong khi chờ đợi chúng ta có thể áp dụng g cho "bar". Vì áp dụng g vào "bar" không cần kết quả của "foo", chúng tôi có thể làm việc này cùng một lúc.

Không có deadlocks, không có đói, cuối cùng tất cả các giao dịch sẽ được xử lý (khoảng theo thứ tự nhận được).

Answer 1

Bạn có thể thiết lập chuỗi công nhân để xử lý tất cả yêu cầu theo cách xác định, vì vậy không ai bị bỏ đói. Chiến lược này sẽ có hiệu quả và miễn dịch hợp lý đối với livelock.

-- yes, this is a horrible name 
createManagerFactory :: a -> IO ((IO a), IO (((a -> a) -> IO a))) 

IO là một hành động an toàn và nhanh chóng truy vấn giá trị với hành động STM chỉ đọc. (a -> a) là một hàm thuần túy làm thay đổi giá trị, do đó ((a -> a) -> IO a) là một hành động có chức năng sửa đổi, an toàn sửa đổi giá trị và trả về giá trị mới.

Chạy một lần này để khởi tạo nhà máy.

(query, modifierFactory) <- createManagerVactory initValue 

Sau đó, cho mỗi chuỗi chạy điều này để tạo công cụ sửa đổi mới.

myModify <- modifierFactory 

createManagerFactory sẽ làm như sau:

• Tạo một TVar chứa initValue (gọi nó là valueTVar).
• Tạo một TVar chứa một bộ sưu tập trống của TVar (Hoặc là một (một -> a)) (gọi nó là modifyTVarCollection)
• trở lại (nguyên tử $ readTVar valueTVar) là 'truy vấn' gây
• trở lại một modifierFactory rằng biết về modifyTVarCollection

modifierFactory sẽ làm điều này:

• Tạo một TVar mới (Hoặc là một (a -> a)) (gọi nó là modifyTVar), khởi tạo nó thành một (Left một) với giá trị hiện tại của valueTVar và thêm nó vào modifyTVarCollection
• trả về một tác vụ bổ trợ tải (Phải (a -> a)) vào modifyTVar trong một hành động STM, sau đó thực hiện lại một hành động STM khác cho đến khi modifyTVar chứa a (Trái a) giá trị kết quả, sau đó trả về giá trị đó.

Các sợi nhân sẽ chạy vòng lặp này:

• Trong một hành động, lấy tất cả các TVars truy vấn từ modifyTVarCollection, và kiểm tra giá trị của họ. Nếu tất cả chúng đều chứa giá trị (Trái a), hãy thử lại (điều này sẽ chặn cho đến khi một số luồng khác đã tải tệp modifyTVar của chúng với hàm bổ trợ hoặc modifierFactory đã tạo một modifierTVar mới và thêm nó vào bộ sưu tập). Trả lại danh sách tất cả các sửa đổiTV có chứa Quyền (a -> a)
• Lặp lại tất cả các sửa đổi được trả về. Đối với mỗi TV, thực hiện tác vụ đọc chức năng sửa đổi, thực hiện sửa đổi một cách an toàn và đặt kết quả trở lại vào modifyTVar dưới dạng (Trái a)