生產者消費者問題與有界緩衝區
想像一條迴轉壽司輸送帶。廚師(生產者)把盤子放上帶子;食客(消費者)把盤子取下。帶子只容得下這麼多盤。帶子滿了,廚師就得等才能再放;帶子空了,食客就得等盤子出現。生產者消費者問題正是這個協調,而帶子就是有界緩衝區——一個固定大小的共享佇列,由生產者填滿、消費者抽空。它是把本領域一切串起來的經典範例。
有界緩衝區通常是一個當成環來用的固定大小陣列(環形緩衝區),帶有一個 head 索引、一個 tail 索引,以及一個記錄目前存放幾個項目的 count。三件同步機制維持它的正確。一把互斥鎖保護緩衝區的索引與 count,使生產者與消費者絕不會弄壞它們。一個「未滿」條件變數,讓生產者在 count == capacity 時等待,並由消費者取出一個項目後對它 signal。第二個「非空」條件變數,讓消費者在 count == 0 時等待,並由生產者加入一個項目後對它 signal。雙方都是:拿鎖、在 while 迴圈裡等到自己的條件成立、做那一個操作、對另一方 signal、解鎖。若改用兩個計數號誌來建,「空槽」初始為 capacity、「滿槽」初始為零:生產者 wait 空槽、post 滿槽;消費者 wait 滿槽、post 空槽。
這個樣式無所不在:執行緒池的工作佇列、一個抽走日誌訊息的記錄執行緒、把連線交給工人的網路伺服器、餵下一級的管線階段。把它做對,會操練到互斥鎖(保護共享索引)、條件變數或號誌(沒事做時阻塞,而不是忙等),以及「等待時搭配述語迴圈」的紀律。經典錯誤是忘了 while 迴圈(用 if 在偽喚醒與多消費者下會出錯)以及 signal 錯了條件變數。
生產者:lock(m); while (count == cap) cond_wait(¬Full, &m); buf[tail]=x; tail=(tail+1)%cap; count++; cond_signal(¬Empty); unlock(m);。消費者與它對稱,等在 notEmpty 上、並 signal notFull。
一個環形緩衝區、一把互斥鎖、兩個條件變數:給生產者的「未滿」與給消費者的「非空」。
當生產者或消費者不只一個時,醒來後你必須在 while 迴圈裡重新檢查述語——在 signal 與重新取得鎖之間,另一個執行緒可能已經把名額拿走了。用 cond_signal 喚醒一個共用的條件變數,也可能喚醒到錯誤類型的執行緒,所以要 signal 特定的條件、或謹慎使用 broadcast。