Làm thế nào để đọc/ghi khóa được thực hiện trong pthread?

Question

Chúng được triển khai như thế nào trong trường hợp pthreads. API đồng bộ hóa pthread nào họ sử dụng dưới mui xe? Một chút mã giả sẽ được đánh giá cao.

Answer 1

Tôi chưa thực hiện bất kỳ chương trình pthread nào trong một thời gian, nhưng khi tôi đã làm, tôi chưa bao giờ sử dụng khóa đọc/ghi POSIX. Vấn đề là hầu hết thời gian một mutex sẽ đủ: tức là. phần quan trọng của bạn là nhỏ, và khu vực không phải là hiệu suất rất quan trọng mà rào cản đôi là đáng lo ngại về.

Trong trường hợp hiệu suất là một vấn đề, thường sử dụng các hoạt động nguyên tử (thường có sẵn như là một phần mở rộng trình biên dịch) là một lựa chọn tốt hơn (tức là rào cản thêm là vấn đề, không phải kích thước của phần quan trọng).

Khi bạn loại bỏ tất cả các trường hợp này, bạn còn lại với các trường hợp mà bạn có yêu cầu về hiệu năng/công bằng/rw-bias cụ thể yêu cầu khóa thực sự đúng; và đó là khi bạn phát hiện ra rằng tất cả các thông số hiệu suất/công bằng có liên quan của POSIX rw-lock là không xác định và thực hiện cụ thể. Tại thời điểm này, bạn thường tốt hơn khi thực hiện của riêng bạn để bạn có thể đảm bảo các yêu cầu công bằng/rw-bias phù hợp được đáp ứng.

Thuật toán cơ bản là để đếm số lượng mỗi phần trong phần quan trọng và nếu chuỗi không được phép truy cập, hãy chuyển nó thành hàng đợi phù hợp để chờ. Hầu hết các nỗ lực của bạn sẽ được thực hiện sự công bằng/thiên vị thích hợp giữa phục vụ hai hàng đợi.

Mã giả giống như pthreads giống như C minh họa những gì tôi đang cố gắng nói.

struct rwlock { 
    mutex admin; // used to serialize access to other admin fields, NOT the critical section. 
    int count; // threads in critical section +ve for readers, -ve for writers. 
    fifoDequeue dequeue; // acts like a cond_var with fifo behaviour and both append and prepend operations. 
    void *data; // represents the data covered by the critical section. 
} 

void read(struct rwlock *rw, void (*readAction)(void *)) { 
    lock(rw->admin); 
    if (rw->count < 0) { 
    append(rw->dequeue, rw->admin); 
    } 
    while (rw->count < 0) { 
    prepend(rw->dequeue, rw->admin); // Used to avoid starvation. 
    } 
    rw->count++; 
    // Wake the new head of the dequeue, which may be a reader. 
    // If it is a writer it will put itself back on the head of the queue and wait for us to exit. 
    signal(rw->dequeue); 
    unlock(rw->admin); 

    readAction(rw->data); 

    lock(rw->admin); 
    rw->count--; 
    signal(rw->dequeue); // Wake the new head of the dequeue, which is probably a writer. 
    unlock(rw->admin); 
} 

void write(struct rwlock *rw, void *(*writeAction)(void *)) { 
    lock(rw->admin); 
    if (rw->count != 0) { 
    append(rw->dequeue, rw->admin); 
    } 
    while (rw->count != 0) { 
    prepend(rw->dequeue, rw->admin); 
    } 
    rw->count--; 
    // As we only allow one writer in at a time, we don't bother signaling here. 
    unlock(rw->admin); 

    // NOTE: This is the critical section, but it is not covered by the mutex! 
    //  The critical section is rather, covered by the rw-lock itself. 
    rw->data = writeAction(rw->data); 

    lock(rw->admin); 
    rw->count++; 
    signal(rw->dequeue); 
    unlock(rw->admin); 
} 

Điều gì đó giống như mã trên là điểm bắt đầu cho bất kỳ triển khai rwlock nào. Đưa ra một số suy nghĩ về bản chất của vấn đề của bạn và thay thế dequeue bằng logic thích hợp để xác định loại chủ đề nào sẽ được đánh thức tiếp theo. Nó được phổ biến để cho phép một số lượng hạn chế/thời gian của độc giả để nhảy vọt nhà văn hoặc ngược lại tùy thuộc vào ứng dụng.

Tất nhiên, ưu tiên chung của tôi là tránh toàn bộ khóa rw; nói chung bằng cách sử dụng một số kết hợp của các hoạt động nguyên tử, mutexes, STM, truyền thông điệp và các cấu trúc dữ liệu liên tục. Tuy nhiên có những lúc những gì bạn thực sự cần là một rw-lock, và khi bạn làm nó là hữu ích để biết cách họ làm việc, vì vậy tôi hy vọng điều này đã giúp.

EDIT - Để đối phó với (rất hợp lý) câu hỏi, nơi nào tôi chờ đợi trong pseudo-code trên:

tôi đã giả định rằng việc thực hiện dequeue chứa sự chờ đợi, vì vậy mà nơi nào đó trong append(dequeue, mutex) hoặc prepend(dequeue, mutex) có là một khối mã dọc theo các dòng:

while(!readyToLeaveQueue()) { 
    wait(dequeue->cond_var, mutex); 
} 

đó là lý do tại sao tôi chuyển qua các hoạt động xếp hàng có liên quan.

Answer 2

Mỗi lần triển khai có thể khác nhau, nhưng thông thường họ phải ưu tiên người đọc theo mặc định do yêu cầu của POSIX rằng chuỗi có thể lấy khóa đọc trên nhiều lần. Nếu họ ủng hộ nhà văn, thì bất cứ khi nào một nhà văn đang đợi, người đọc sẽ bế tắc trong lần thử đọc thứ hai trừ khi việc thực hiện có thể xác định người đọc đã có khóa đọc, nhưng cách duy nhất để xác định đó là lưu trữ danh sách tất cả các chủ đề giữ khóa đọc, điều này không hiệu quả về thời gian và yêu cầu về không gian.