Giải pháp Thuật toán Thứ hai cho Người đọc-Nhà văn

Question

Tôi đang có một thời gian thực sự khó hiểu về Thuật toán Thứ hai đối với vấn đề Người đọc-Nhà văn. Tôi hiểu khái niệm chung, rằng các nhà văn sẽ được ưu tiên hơn độc giả (độc giả có thể chết đói). Tôi thậm chí hiểu việc thực hiện biến có điều kiện của thuật toán này Reader/Writer Locks in C++. Tuy nhiên, semaphore & thực hiện mutex không có ý nghĩa với tôi. Đây là một ví dụ từ Wikipedia:

int readcount, writecount; (initial value = 0) 
semaphore mutex 1, mutex 2, mutex 3, w, r ; (initial value = 1) 

READER 
    P(mutex 3); 
    P(r); 
     P(mutex 1); 
     readcount := readcount + 1; 
     if readcount = 1 then P(w); 
     V(mutex 1); 
    V(r); 
    V(mutex 3); 

    reading is done 

    P(mutex 1); 
    readcount := readcount - 1; 
    if readcount = 0 then V(w); 
    V(mutex 1); 


WRITER 
    P(mutex 2); 
     writecount := writecount + 1; 
     if writecount = 1 then P(r); 
    V(mutex 2); 

    P(w); 
    writing is performed 
    V(w); 

    P(mutex 2); 
    writecount := writecount - 1; 
    if writecount = 0 then V(r); 
    V(mutex 2); 

[http://en.wikipedia.org/wiki/Readers-writers_problem][2] 

Tôi không hiểu ba ẩn dụ (mutex 3, r và mutex 1) là gì trong khóa đọc. Không phải là một semaphore đủ cho số đọc?

Answer 1

Hãy xem Concurrent Control with "Readers" and "Writers" by P.J. Courtois, F. Heymans, and D.L. Parnas, là tham chiếu cho mã tại Wikipedia. Nó giải thích tại sao tất cả các mutex đều cần thiết.

Answer 2

mutex 1 bảo vệ biến số readcount; mutext 2 bảo vệ writecount biến; mutex r bảo vệ hoạt động đọc và tắt tiếng w bảo vệ hoạt động viết.

1) Giả sử một nhà văn đi kèm trong:

Tín hiệu mutex 2 và gia writercount vào tài khoản cho nhà văn thêm (chính nó) Vì nó là quá trình duy nhất có thể thay đổi writercount (vì nó đang nắm giữ mutex 2), nó có thể kiểm tra an toàn cho dù đó là người viết duy nhất (writercount==1), nếu đúng, nó báo hiệu mutex r để bảo vệ người đọc không tham gia - các nhà văn khác (writercount > 1) có thể thưởng thức mutex r đang được báo hiệu.

Sau đó, người viết báo hiệu mutex w để bảo vệ các thay đổi của nó từ các tác giả (đồng thời) khác.

Tác giả cuối cùng (writecount==1) phát hành mutex r để cho phép người đọc thực hiện các tác vụ của họ.

2) Giả sử một độc giả do thỏa thuận hợp:

Tín hiệu mutex 3 để bảo vệ luận thiết lập của độc giả từ các độc giả khác; sau đó báo hiệu mutex r để bảo vệ từ các nhà văn khác (hãy nhớ rằng, r được báo hiệu trong khi các nhà văn đang hoạt động); sau đó báo hiệu số mutex 1 để bảo vệ số đọc (từ những người đọc khác có thể đang thoát) và nếu nó là người đọc đầu tiên (readercount == 1), hãy báo hiệu mutex w để bảo vệ người viết (hiện không bao gồm nhà văn thực hiện hoạt động của họ).

Reading thể được thực hiện song song, vì vậy không có bảo vệ là cần thiết từ các độc giả khác trong khi đọc (hãy nhớ, mutex w được tổ chức vào thời điểm này, vì vậy không intereference từ các nhà văn)

Sau đó, người đọc cuối cùng reset ghi mutex (w) để cho phép người viết.

---

Bí quyết có thể ngăn chặn nhà văn đói là nhà văn đặt ra như độc giả (khi tín hiệu mutex p), vì vậy có một cơ hội tốt của việc lên kế hoạch ngay cả khi có rất nhiều độc giả. Ngoài ra, mutex 3 ngăn không cho quá nhiều người đọc chờ đợi trên mutex r, do đó, người viết có cơ hội tốt để báo hiệu r khi họ đến.