Lập trình đa xử lý: ngăn xếp không khóa

Question

Trong quá trình chuẩn bị cho kỳ thi sắp tới của Hệ thống đồng thời, tôi đang cố gắng hoàn thành một số câu hỏi từ cuốn sách "Nghệ thuật lập trình đa xử lý". Một câu hỏi được bugging tôi:

tập 129: Liệu nó có ý nghĩa để sử dụng cùng chia sẻ đối tượng backoff cho cả push và pop trong đối tượng LockFreeStack của chúng tôi? Làm thế nào chúng ta có thể cấu trúc backoff trong không gian và thời gian trong EliminationBackOffStack ?.

Câu hỏi này làm tôi nhớ vì điều đầu tiên đến với tâm trí của tôi là nó không có ý nghĩa bởi vì tất cả đối tượng ngược lại là thực hiện một quá trình chờ đợi, vậy tại sao không chia sẻ nó? Phần thứ hai của câu hỏi hoàn toàn eludes tôi và giúp đỡ bất kỳ được chào đón nhất.

Mã cho LockFreeStack:

public class LockFreeStack<T> { 

    AtomicReference<Node> top = new AtomicReference<Node>(null); 

    static final int MIN_DELAY = ...; 
    static final int MAX_DELAY = ...; 
    Backoff backoff = new Backoff(MIN_DELAY, MAX_DELAY); 

    protected boolean tryPush(Node node) { 
     Node oldTop = top.get(); 
     node.next = oldTop; 
     return(top.compareAndSet(oldTop, node)); 
    } 

    public void push(T value) { 
     Node node = new Node(value); 
     while (true) { 
      if (tryPush(node)) { 
       return; 
      } else { 
       backoff.backoff(); 
      } 
     } 
    } 

Answer 1

Không chắc chắn nếu bất kỳ lời huyên thuyên của tôi giúp nhưng tôi sẽ nhấn nút "Đăng" anyway.

Câu trả lời phụ thuộc vào việc triển khai backoff(). Vì mục tiêu ở đây là để tránh đồng bộ hóa, sẽ không có bất kỳ bộ nhớ cục bộ nào - có thể một số trong một số ThreadLocal. Nếu thuật toán backoff sử dụng một trình ngẫu nhiên, nó sẽ cần phải được reentrant là tốt. Vì vậy, rất có thể bạn là có thể để chia sẻ nó giữa pop và push - bây giờ bạn có muốn. Kể từ khi push và pop đều cố gắng thay đổi tham chiếu top, nó sẽ là tốt nếu backoff đưa ra các chuỗi kế tiếp các số khác nhau. Có tranh cãi xung quanh push hay pop hơn không? Chúng ta có cần phải tích cực hơn với một hoặc một phương pháp khác? Nếu đây là một ngăn xếp chung thì bạn sẽ không biết.

Xét về cách hoạt động của "cơ cấu lại", tôi cũng không chắc chắn. Bạn có thể sử dụng push hoặc pop thành công như một cơ hội để tăng tốc trở lại vào thời gian backoff? Làm thế nào về sự khác biệt giữa backoff ngẫu nhiên chờ đợi so với số nguyên tố trong một chuỗi được phân công bởi ThreadLocal?

Answer 2

Tiếp cận câu hỏi đầu tiên từ điểm đồng bộ hóa, tôi tin rằng sẽ có ý nghĩa khi cho phép đối tượng BackOff giống nhau cho cả hai lần nhấn và bật. Bất kể việc triển khai lớp này. Lý do cho điều này là nếu chúng ta có một ngăn xếp, chúng ta phải duy trì một trạng thái nhất quán trong việc loại bỏ và bổ sung các mục vào ngăn xếp. Tuy nhiên, nếu chúng ta chỉ nhìn trộm (nhìn vào phần tử đầu tiên hoặc trên cùng của chồng), chúng ta có thể có nhiều hơn một đối tượng BackOff xem nó như là lần đọc không được tạo khóa trên nguồn dữ liệu được đề cập. Câu hỏi thứ hai là yêu cầu mã được đăng cho lớp đó.

Answer 3

Sử dụng chế độ backoff bị giết trong trường hợp này.

Bất kỳ ứng dụng thế giới thực nào cũng phải dành nhiều thời gian xử lý các nút hơn là đẩy mọi thứ vào và tắt ngăn xếp. Các hoạt động ngăn xếp bằng cách so sánh nên rất ngắn. Nó sau đó hai chủ đề là rất khó để được truy cập vào ngăn xếp cùng một lúc. Tuy nhiên, nó sẽ xảy ra đôi khi, vì vậy bạn cần phải mã đó là chính xác.

public void push(T value) { 
    Node node = new Node(value); 
    while (!tryPush(node)) 
     backoff.backoff(); 
} 

IMHO: Có thể được rút ngắn xuống còn

public void push(T value) { 
    Node node = new Node(value); 
    while (!tryPush(node)); 
}