# 同步,第 7 部分:讀者編寫器問題
> 原文:<https://github.com/angrave/SystemProgramming/wiki/Synchronization%2C-Part-7%3A-The-Reader-Writer-Problem>
## 什么是讀者作家問題?
想象一下,你有一個許多線程使用的鍵值映射數據結構。如果沒有寫入數據結構,多個線程應該能夠同時查找(讀取)值。作者不是那么合群 - 為了避免數據損壞,一次只有一個線程可以修改(`write`)數據結構(當時沒有讀者可能正在閱讀)。
這是 _ 讀寫器問題 _ 的一個例子。也就是說,我們如何有效地同步多個讀者和作者,以便多個讀者可以一起閱讀,但作家獲得獨家訪問?
下面顯示了不正確的嘗試(“lock”是`pthread_mutex_lock`的簡寫):
## 嘗試#1
|
```
read() {
lock(&m)
// do read stuff
unlock(&m)
}
```
|
```
write() {
lock(&m)
// do write stuff
unlock(&m)
}
```
|
至少我們的第一次嘗試不會遭受數據損壞(讀者必須在作家寫作時等待,反之亦然)!但讀者也必須等待其他讀者。那么讓我們嘗試另一種實現..
## 嘗試#2:
|
```
read() {
while(writing) {/*spin*/}
reading = 1
// do read stuff
reading = 0
}
```
|
```
write() {
while(reading || writing) {/*spin*/}
writing = 1
// do write stuff
writing = 0
}
```
|
我們的第二次嘗試遭遇競爭條件 - 想象兩個線程是否同時調用`read`和`write`(或兩者都稱為寫入)。兩個線程都可以繼續!其次,我們可以有多個讀者和多個作者,所以讓我們跟蹤讀者或作者的總數。這讓我們嘗試#3,
## 嘗試#3
請記住`pthread_cond_wait`執行 _ 三個 _ 動作。首先,它以原子方式解鎖互斥鎖然后休眠(直到它被`pthread_cond_signal`或`pthread_cond_broadcast`喚醒)。第三,喚醒線程必須在返回之前重新獲取互斥鎖。因此,實際上只有一個線程可以在 lock 和 unlock()方法定義的臨界區內運行。
下面的實現#3 確保如果有任何作者寫作,讀者將進入 cond_wait。
```c
read() {
lock(&m)
while (writing)
cond_wait(&cv, &m)
reading++;
/* Read here! */
reading--
cond_signal(&cv)
unlock(&m)
}
```
然而,只有一個讀者一次可以閱讀,因為候選人#3 沒有解鎖互斥鎖。更好的版本在閱讀之前解鎖:
```c
read() {
lock(&m);
while (writing)
cond_wait(&cv, &m)
reading++;
unlock(&m)
/* Read here! */
lock(&m)
reading--
cond_signal(&cv)
unlock(&m)
}
```
這是否意味著作者和閱讀可以同時讀寫?沒有!首先,請記住 cond_wait 要求線程在返回之前重新獲取互斥鎖。因此,一次只有一個線程可以在臨界區內執行代碼(用**標記)!
```c
read() {
lock(&m);
** while (writing)
** cond_wait(&cv, &m)
** reading++;
unlock(&m)
/* Read here! */
lock(&m)
** reading--
** cond_signal(&cv)
unlock(&m)
}
```
作家必須等待每個人。鎖定可確保相互排斥。
```c
write() {
lock(&m);
** while (reading || writing)
** cond_wait(&cv, &m);
** writing++;
**
** /* Write here! */
** writing--;
** cond_signal(&cv);
unlock(&m);
}
```
上面的候選人#3 也使用`pthread_cond_signal`;這只會喚醒一個線程。例如,如果許多讀者等待作者完成,那么只有一個睡覺的讀者會從他們的睡眠中醒來。讀寫器應該使用`cond_broadcast`,以便喚醒所有線程并檢查它們的 while 循環條件。
## 饑餓的作家
上面的候選人#3 患有饑餓。如果讀者經常到達,那么作家永遠無法繼續(“閱讀”計數永遠不會減少到零)。這被稱為 _ 饑餓 _,并將在重負荷下被發現。我們的解決方法是為作者實現有限等待。如果作家到了,他們仍然需要等待現有的讀者,但是未來的讀者必須被置于“握筆”中并等待作者完成。 “握筆”可以使用變量和條件變量來實現(這樣我們就可以在編寫完成后喚醒線程)。
我們的計劃是,當作家到來時,在等待當前讀者完成之前,記錄我們的寫作意圖(通過遞增計數器“作者”)。草繪如下 -
```c
write() {
lock()
writer++
while (reading || writing)
cond_wait
unlock()
...
}
```
當作家非零時,傳入的讀者將不被允許繼續。注意'作家'表示作家已到達,而'閱讀'和'寫'計數器表示有 _ 有效 _ 讀者或作者。
```c
read() {
lock()
// readers that arrive *after* the writer arrived will have to wait here!
while(writer)
cond_wait(&cv,&m)
// readers that arrive while there is an active writer
// will also wait.
while (writing)
cond_wait(&cv,&m)
reading++
unlock
...
}
```
## 嘗試#4
以下是我們對 Reader-Writer 問題的第一個解決方案。請注意,如果您繼續閱讀“Reader Writer 問題”,那么您會發現我們通過給予編寫者優先訪問鎖來解決“第二個 Reader Writer 問題”。該解決方案不是最佳的。然而,它滿足了我們原來的問題(N 個活躍的讀者,單個活躍的作家,如果有一個持續的讀者流,避免作家的饑餓)。
你能找出任何改進嗎?例如,你如何改進代碼,以便我們只喚醒讀者或一個作家?
```c
int writers; // Number writer threads that want to enter the critical section (some or all of these may be blocked)
int writing; // Number of threads that are actually writing inside the C.S. (can only be zero or one)
int reading; // Number of threads that are actually reading inside the C.S.
// if writing !=0 then reading must be zero (and vice versa)
reader() {
lock(&m)
while (writers)
cond_wait(&turn, &m)
// No need to wait while(writing here) because we can only exit the above loop
// when writing is zero
reading++
unlock(&m)
// perform reading here
lock(&m)
reading--
cond_broadcast(&turn)
unlock(&m)
}
writer() {
lock(&m)
writers++
while (reading || writing)
cond_wait(&turn, &m)
writing++
unlock(&m)
// perform writing here
lock(&m)
writing--
writers--
cond_broadcast(&turn)
unlock(&m)
}
```
- UIUC CS241 系統編程中文講義
- 0. 簡介
- #Informal 詞匯表
- #Piazza:何時以及如何尋求幫助
- 編程技巧,第 1 部分
- 系統編程短篇小說和歌曲
- 1.學習 C
- C 編程,第 1 部分:簡介
- C 編程,第 2 部分:文本輸入和輸出
- C 編程,第 3 部分:常見問題
- C 編程,第 4 部分:字符串和結構
- C 編程,第 5 部分:調試
- C 編程,復習題
- 2.進程
- 進程,第 1 部分:簡介
- 分叉,第 1 部分:簡介
- 分叉,第 2 部分:Fork,Exec,等等
- 進程控制,第 1 部分:使用信號等待宏
- 進程復習題
- 3.內存和分配器
- 內存,第 1 部分:堆內存簡介
- 內存,第 2 部分:實現內存分配器
- 內存,第 3 部分:粉碎堆棧示例
- 內存復習題
- 4.介紹 Pthreads
- Pthreads,第 1 部分:簡介
- Pthreads,第 2 部分:實踐中的用法
- Pthreads,第 3 部分:并行問題(獎金)
- Pthread 復習題
- 5.同步
- 同步,第 1 部分:互斥鎖
- 同步,第 2 部分:計算信號量
- 同步,第 3 部分:使用互斥鎖和信號量
- 同步,第 4 部分:臨界區問題
- 同步,第 5 部分:條件變量
- 同步,第 6 部分:實現障礙
- 同步,第 7 部分:讀者編寫器問題
- 同步,第 8 部分:環形緩沖區示例
- 同步復習題
- 6.死鎖
- 死鎖,第 1 部分:資源分配圖
- 死鎖,第 2 部分:死鎖條件
- 死鎖,第 3 部分:餐飲哲學家
- 死鎖復習題
- 7.進程間通信&amp;調度
- 虛擬內存,第 1 部分:虛擬內存簡介
- 管道,第 1 部分:管道介紹
- 管道,第 2 部分:管道編程秘密
- 文件,第 1 部分:使用文件
- 調度,第 1 部分:調度過程
- 調度,第 2 部分:調度過程:算法
- IPC 復習題
- 8.網絡
- POSIX,第 1 部分:錯誤處理
- 網絡,第 1 部分:簡介
- 網絡,第 2 部分:使用 getaddrinfo
- 網絡,第 3 部分:構建一個簡單的 TCP 客戶端
- 網絡,第 4 部分:構建一個簡單的 TCP 服務器
- 網絡,第 5 部分:關閉端口,重用端口和其他技巧
- 網絡,第 6 部分:創建 UDP 服務器
- 網絡,第 7 部分:非阻塞 I O,select()和 epoll
- RPC,第 1 部分:遠程過程調用簡介
- 網絡復習題
- 9.文件系統
- 文件系統,第 1 部分:簡介
- 文件系統,第 2 部分:文件是 inode(其他一切只是數據...)
- 文件系統,第 3 部分:權限
- 文件系統,第 4 部分:使用目錄
- 文件系統,第 5 部分:虛擬文件系統
- 文件系統,第 6 部分:內存映射文件和共享內存
- 文件系統,第 7 部分:可擴展且可靠的文件系統
- 文件系統,第 8 部分:從 Android 設備中刪除預裝的惡意軟件
- 文件系統,第 9 部分:磁盤塊示例
- 文件系統復習題
- 10.信號
- 過程控制,第 1 部分:使用信號等待宏
- 信號,第 2 部分:待處理的信號和信號掩碼
- 信號,第 3 部分:提高信號
- 信號,第 4 部分:信號
- 信號復習題
- 考試練習題
- 考試主題
- C 編程:復習題
- 多線程編程:復習題
- 同步概念:復習題
- 記憶:復習題
- 管道:復習題
- 文件系統:復習題
- 網絡:復習題
- 信號:復習題
- 系統編程笑話