Clojure lockfree có sử dụng thuật toán lockfree không?

Question

Tôi đang tiến bộ trong nhiệm vụ Clojure của mình (khoảng 80 vấn đề được giải quyết trên 4clojure.com) và tôi tiếp tục đọc và viết mã và cố gắng "làm cho nó".

Bây giờ tôi hơi bối rối bởi Clojure được thiết kế cho "đồng thời không khóa". Tôi biết tất cả quá tốt về deadlocks (như trong: "Tôi đã viết mã Java nghèo mà kết thúc trong deadlocks", không phải là trong "Tôi đang ở trong chuyên gia đồng thời"). Tôi cũng đã đọc:

Why is lockless concurrency such a big deal (in Clojure)?

Tôi nhận ra như thế nào tuyệt vời nó là chương trình Clojure không thể bế tắc. Nhưng tôi hơi bối rối: là một thành tích đạt được bằng cách thực hiện theo thuật toán lockfree mui xe hoặc có khả năng "deadlockable" được sử dụng, nhưng sử dụng đúng thực hiện đảm bảo không bao giờ bế tắc (mà bằng cách nào đó sẽ được "ẩn "để lập trình Clojure)?

Đã có một cuộc thảo luận gần đây về tin tức của hacker về thuật toán lockfree:

http://news.ycombinator.com/item?id=4103921

tham khảo những điều sau "thuật toán Lock-free" trang trên 1024cores.net:

http://www.1024cores.net/home/lock-free-algorithms

Tôi không hiểu mối quan hệ giữa bài viết này và cách thức đồng thời hoạt động theo Clojure.

Và nó khiến tôi hoàn toàn bối rối: khi tôi đang phát triển các chương trình đồng thời trong Clojure, điều đó có nghĩa là "khóa và thuật toán không khóa" không phải là vấn đề đối với tôi?

Answer 1

Nói chung Clojure tránh được vấn đề của khóa bởi xử lý đúng thời gian Trong thời gian nhiều hệ thống cho một đối tượng là một khái niệm rất lỏng lẻo vì một đối tượng ở thời gian 1 (trước khi cập nhật) được chỉnh sửa tại chỗ để trở thành đối tượng mà tại time-2 (sau khi cập nhật), trong quá trình đó nó là net đầu tiên hoặc thứ hai, vì vậy chúng tôi sử dụng khóa để đảm bảo nó chỉ hiển thị trước hoặc sau khi chuyển đổi này. Các khóa điều phối theo sau từ khóa này và deadlocks từ đó ...

Đó là sự kết hợp của các thuật toán, cấu trúc dữ liệu và thời gian.

Clojure thực hiện điều này bằng cách kết hợp cấu trúc dữ liệu không thay đổi, lập trình chức năng và mô hình thời gian phối hợp (refs, nguyên tử, tác nhân, v.v ...). Trong mô hình này một chức năng phải mất một cái gì đó và tạo ra phiên bản kế tiếp của nó trong khi vẫn giữ quá khứ quá lâu như bất cứ ai đang nhìn vào nó (cho đến khi GC được với nó)

• Immutable Cấu trúc dữ liệu: bộ sưu tập Clojure của rất dai dẳng trong ý nghĩa FP của từ. Các bản sao cũ "vẫn tồn tại" sau khi các phiên bản mới được tạo ra. theo cách này, các nhà quan sát không cần khóa các đồ vật bởi vì chúng sẽ không bao giờ thay đổi từ bên dưới chúng. Các phiên bản mới hơn có thể tồn tại dựa trên phiên bản mà họ đang xem mặc dù không có gì thay đổi bản sao của họ.

• Lập trình chức năng: Pure (hoặc gần như không có sự khác biệt) Chức năng lấy một bộ sưu tập tại một thời điểm và tạo phiên bản tiếp theo với chia sẻ trạng thái bên trong của chúng.Điều này cũng có nhiều lợi ích khác.

• Coordinated time: Khi nhiều đối tượng cần phải được điều phối, như trường hợp với bất kỳ hệ thống thú vị nào, thì mô hình thời gian của Clojure sẽ được phát. Có các cơ chế khác nhau cho các mục đích khác nhau. điều này có một khóa nội bộ được sử dụng để đếm số gia của thời gian để có chính xác một thời gian không, một thời gian một, và một lần N. Vì vậy, nó không phải là khóa chặt chẽ miễn phí. STM chứa ổ khóa mà bạn không bao giờ * cần phải tương tác với

---

* cũng ... gần như không bao giờ ;-)

Answer 2

Nếu bạn grep xung quanh nguồn Clojure, và đặc biệt là các Các tệp .java bạn sẽ tìm thấy một vài tham chiếu đến gói java.util.concurrent. Gói java.util.concurrent là đỉnh cao của hàng thập kỷ nghiên cứu về sự tương tranh của Doug Lea tại SUNY Oswego. Cụ thể, có các tham chiếu đến các lớp biến nguyên tử (ví dụ: AtomicReference) cho phép truy cập vào "so sánh và trao đổi" (còn được gọi là "so sánh và đặt" hoặc CAS) instruction. Lệnh CAS là một chút khó giải thích (tôi cung cấp một tham chiếu bên dưới) nhưng việc sử dụng CAS thích hợp là trọng tâm của thuật toán "khóa tự do" (ít nhất là trong thế giới Java). Khóa các thuật toán miễn phí cuối cùng dẫn đến thông lượng cao hơn và ít tranh chấp hơn cho các ứng dụng đồng thời cao; chính xác tên miền mà Clojure đang nhắm mục tiêu.

Để có cái nhìn sâu sắc về chủ đề này, hãy đọc Đồng thời Java trong thực tiễn bởi Brian Goetz. Xem thêm article bởi cùng một tác giả.

Là một lưu ý phụ, tôi luôn thấy khó sử dụng gói java.util.concurrent ngay cả khi nó phát triển. Nó chỉ cảm thấy quá thấp với tôi. Điều tuyệt vời về Clojure là nó cung cấp quyền truy cập vào thư viện đồng thời của chuyên gia đó nhưng thông qua việc trừu tượng hóa phần mềm giao tiếp phần mềm (STM) dễ sử dụng tuyệt vời. Đó thực sự là một thành tựu.