用戶:Cljbx/Readers–writers problem

計算機科學中讀者 - 編寫者問題是一種在並發常見的一種計算問題的例子。 問題至少有三種變體,計算機在處理多個線程同時嘗試訪問同一共享資源的情況。 有些線程可能會讀取資源而有些線程可能會寫入資源,該問題的限制條件是當一個進程對共享資源進行讀取或寫入時,另一個進程無法寫入它。 (它可以被兩個或更多的讀者進程在同一時間訪問,但只能被唯一的寫者進程訪問, 讀寫器鎖是一種解決一個或多個讀者 - 寫者問題的數據結構

基本的讀者-作家問題由庫爾圖瓦 et al.[1][2]第一次形式化並解決的。

例如:假設在一個班級只有一個佈告板,只有一個人可以進行編寫,與此同時,許多讀者可以稍後閱讀佈告板。

假設我們有一個受以上基本制約的共享內存區。 可以通過互斥鎖保證沒有兩個線程可以在同一時間訪問詞數據。 然而,這種解決方案是低效的,因為當讀者 R1 加鎖,然後另一個讀者 R2 請求訪問。 R2 將進行等待,無法在 R1 完成之前開始自己的讀操作;相反, R2 應該可以與R1一起讀數據,因為讀不會修改數據,所以並行讀取是安全的。 這是 第一個讀者-作家的問題, 讀者無需等候,當共享可以讀時。 這也被稱為 讀者的偏好,其解決方案:

semaphore resource=1;
semaphore rmutex=1;
readcount=0;

/*
   resource.P() is equivalent to wait(resource)
   resource.V() is equivalent to signal(resource)
   rmutex.P() is equivalent to wait(rmutex)
   rmutex.V() is equivalent to signal(rmutex)
*/

writer() {
    resource.P();          //Lock the shared file for a writer

    <CRITICAL Section>
    // Writing is done

    <EXIT Section>
    resource.V();          //Release the shared file for use by other readers. Writers are allowed if there are no readers requesting it.
}

reader() {
    rmutex.P();           //Ensure that no other reader can execute the <Entry> section while you are in it
    <CRITICAL Section>
    readcount++;          //Indicate that you are a reader trying to enter the Critical Section
    if (readcount == 1)   //Checks if you are the first reader trying to enter CS
        resource.P();     //If you are the first reader, lock the resource from writers. Resource stays reserved for subsequent readers
    <EXIT CRITICAL Section>
    rmutex.V();           //Release

    // Do the Reading

    rmutex.P();           //Ensure that no other reader can execute the <Exit> section while you are in it
    <CRITICAL Section>
    readcount--;          //Indicate that you are no longer needing the shared resource. One fewer reader
    if (readcount == 0)   //Checks if you are the last (only) reader who is reading the shared file
        resource.V();     //If you are last reader, then you can unlock the resource. This makes it available to writers.
    <EXIT CRITICAL Section>
    rmutex.V();           //Release
}


[[Category:并发性]] [[Category:有未审阅翻译的页面]]

  1. ^ 引用錯誤:沒有為名為courtois的參考文獻提供內容
  2. ^ Taubenfeld, Gadi. Synchronization Algorithms and Concurrent Programming. Pearson Education. 2006: 301.