Bế tắc bế tắc

Question

Vì vậy, tôi gặp vấn đề khi sử dụng semaphore. Viết mã có 4 phòng và một số khách. Mỗi phòng đều có một số tiền nhất định cho số lượng khách truy cập mà họ có thể giữ. Vì vậy, vào một phòng đầy đủ sẽ kích hoạt một chờ đợi(). Các du khách không được rời khỏi phòng trước khi họ có thể vào phòng khác, vì vậy họ luôn ở trong phòng.

public class Semaphore { 

    private int placesLeft; 

    public Semaphore(int placesInRoom) { 
    this.placesLeft = placesInRoom; 
    } 

    public synchronized void acquire(Visitor visitor) { 
    Semaphore sem = visitor.getRoom().getSemaphore(); 

    try { 
     while (placesLeft <= 0) { 
     this.wait(); 
    } 

    } catch (InterruptedException e) {} 

    sem.release(); 
    placesLeft--; 
} 

public synchronized void release() { 
    placesLeft++; 
    this.notifyAll(); 
} 

Bế tắc xuất hiện khi 2 người đang cố gắng vào phòng của nhau. Cũng vì một số lý do, số lượng placesLeft không được phát hành đúng.

Vì vậy, tôi nên làm gì?

CHỈNH SỬA:

Bạn đang bận với thứ khác, làm mới câu hỏi. Sự cố không xảy ra do các phòng đầy, khóa các sự kiện khi person1 từ room1 muốn vào room2 và cùng một lúc person2 từ room2 muốn vào room1. Như tôi understant của nó một cái gì đó để làm với synchrozing có thể? Họ gặp khó khăn trước khi phát hành, vì vậy việc phát hành không được gọi. Như tôi hiểu một phòng accuire và phát hành không thể được gọi là cùng một thời gian. Vì vậy, cơ bản room1 semaphore phát hành không thể được gọi là cuz cùng một lúc accuire được gọi là, tương tự cho room2? Tôi là coder và đồng bộ hóa newbie chưa rõ ràng lắm. Loại bỏ đồng bộ hóa từ một hoặc không có vẻ như làm việc (cũng là sai lầm hoàn toàn).

Answer 1

Thêm danh sách khách truy cập hiện tại vào Room để bạn có thể đăng ký acquire với điều kiện khách truy cập đến từ phòng mà một trong những người cư ngụ trong phòng này đang chờ để vào. Bạn cũng sẽ cần thêm phòng mà khách truy cập đang chờ để nhập vào Visitor.

Room comingFrom = visitor.getRoom(); 
while (placesLeft <= 0) { 
    for (Visitor waiter : room.getVisitors()) { 
     if (waiter.getWaitingForRoom().equals(comingFrom) { 
      // swap the visitors without releasing/acquiring any semaphores and return 
     } 
    } 
    this.wait(); 
} 

Tôi không chắc chắn về logic để kiểm tra xem khách truy cập có đang chờ để vào cùng một phòng mà khách truy cập hiện tại sắp rời khỏi. Tôi không thể cho biết phòng nào room đại diện cho mã.

Answer 2

Thay vì thực hiện của riêng bạn, cách sử dụng java.util.concurrent.Semaphore được xây dựng vào Thư viện chuẩn Java?

Gói java.util.concurrent có số lượng lớn tutorial bao gồm Semaphores và nhiều cơ chế đồng bộ hóa hữu ích khác mà nó cung cấp.

Answer 3

Để trả lời câu hỏi của bạn, "Tôi nên làm gì?", Nếu bạn phát hiện bế tắc, hãy di chuyển một trong những Khách truy cập bị bế tắc đến bất kỳ phòng nào có không gian. Sau đó di chuyển anh ta đến căn phòng anh ta thực sự muốn. Điều này về cơ bản cho phép trao đổi mà không vi phạm bất kỳ quy tắc nào bên dưới.

1. Phòng không bao giờ phải chứa nhiều hơn du khách X
2. Một khách luôn ở đúng một phòng
3. Chỉ có một khách thể thay đổi phòng tại một thời điểm (mà thực sự là mấu chốt của vấn đề)

Ghi nhớ có khoảng một triệu chiến lược khóa semaphore ngoài đó ...

Answer 4

Bế tắc xảy ra khi có chu kỳ trong biểu đồ phụ thuộc. Khi 2 người đang cố gắng vào phòng của nhau, đây rõ ràng là một chu kỳ, và bế tắc là một hậu quả tự nhiên.

Tuy nhiên, bạn muốn xử lý các chu kỳ theo cách khác: khi chu kỳ xảy ra, mọi người đều di chuyển dọc theo chu kỳ (có thể có hơn 2 người trao đổi phòng).

Vì vậy, trước tiên bạn nên xác định xem chu trình có được tạo hay không và sau đó thay đổi vị trí của khách truy cập.

Answer 5

Hãy thử điều này:

public class Semaphore { 
    private final static Object LOCK = new Object(); 
    private int placesLeft; 

    public Semaphore(int placesInRoom) { 
    this.placesLeft = placesInRoom; 
    } 

    public void acquire(Visitor visitor) { 
     synchronized (LOCK) { 
      Semaphore sem = visitor.getRoom().getSemaphore(); 

      try { 
       while (placesLeft <= 0) { 
        LOCK.wait(); 
       } 
      } catch (InterruptedException e) {} 

     sem.release(); 
     placesLeft--; 
    } 
} 

public void release() { 
    synchronized(LOCK) { 
     placesLeft++; 
     LOCK.notifyAll(); 
    } 
} 

Mã cũ đồng bộ trên các trường hợp Semaphore cá nhân. Rất khó để ngăn chặn deadlocks, bởi vì phương thức acquire() của một cá thể gọi là release() của một cá thể khác. Cuộc gọi đến release() sau đó chặn nếu một luồng khác hiện đang thực hiện phương thức acquire() trên trường hợp khác đó. Nếu chuỗi thứ hai cuối cùng gọi release() trên ví dụ đầu tiên, bạn có bế tắc.

Tôi đã thay thế đồng bộ hóa trên các cá thể Semaphore riêng lẻ bằng cách đồng bộ hóa trên một đối tượng có tên là LOCK. Chuỗi thực hiện acquire() đã khóa màn hình của LOCK. Do đó, luồng này không bị chặn khi nó gọi phương thức release(). Do đó, phương pháp release() sẽ luôn chấm dứt. Điều này giải quyết bế tắc.

Answer 6

Vết khóa thường được giải quyết bằng hệ thống semaphore phân cấp. Điển hình khóa chết trông giống như

Process Một

getSemaphore('A'); 
getSemaphore('B'); 

Process B

getSemaphore('B'); 
getSemaphore('A'); 

Chỉ cần cho tất cả các quy trình để chọn A trước B. Điều này có thể được thực hiện bằng văn bản chức năng getSemaphore của bạn để thực thi các hệ thống phân cấp với xác nhận.

Đối với trường hợp cụ thể của bạn, điều này không giải quyết được vấn đề rất rõ ràng nhưng bạn có thể ngoại suy từ ý tưởng này.

Tạo hàng đợi di chuyển. Khi người dùng muốn thay đổi phòng, chức năng của bạn có thể trông giống như:

ChangeRoom(person, from, to) 
{ 
    getSemaphore('room_queue', 3200); 
    enqueue(room_queue, Object(person, from, to)); 
    releaseSemaphore('room_queue'); 
} 

"3200" là thời gian chờ semaphore. Nếu một quá trình bị gián đoạn sau khi truy vấn semaphore nó sẽ vẫn bế tắc hệ thống. Điều này cho thời gian chờ 1 giờ. Bạn có thể đặt nó thành giá trị logic 1 phút, 5 giây dựa trên sự ổn định của hệ thống. Sau đó, có một bộ xử lý hàng đợi mà chỉ cho phép một chuyển tại một thời điểm với một semaphore non-blocking

QueueProcessor() 
{ 
    getSemaphore('room_queue', 3200); 
    for (transition = dequeue(room_queue)) 
    { 
     if (getNonBlockingSemaphore(transition.to) 
     { 
      releaseSemaphore(transition.from); 
      getSemaphore(transition.to); 
     } 
     continue; 
    } 
    releaseSemaphore('room_queue'); 
    sleep(10); 
} 

Giấc ngủ giữ cho hình thức quá trình xếp hàng áp đảo bộ vi xử lý. Đặt nó vào một kiểm tra thích hợp. Bạn cũng có thể thiết lập các ngắt để kéo các mục hàng đợi chỉ khi một phòng có một khoảng trống được mở hoặc một quá trình chuyển đổi được thêm vào. Bằng cách này nếu một căn phòng đầy, nó sẽ không lãng phí thời gian để cố gắng vào nhưng mọi người sẽ có ít nhất một lần bắn vào ngay lập tức.

Điều này buộc phải chuyển đổi để có được semaphore hàng đợi trước khi họ có thể có được một semaphore phòng. Thiết lập hệ thống phân cấp miễn phí bế tắc. Một người dùng sẽ không bao giờ rời khỏi hàng đợi nếu một căn phòng đầy nhưng nó sẽ không bế tắc hệ thống.