正如在圖2-1中所看到的那樣，文件子系統中的高層內核算法引用管理高速緩衝的算法。當它們試圖檢索一個塊時，由高層算法決定它們想要存取的邏輯設備號和塊號。舉例來說，正如在第4章將要看到的那樣，如果一個進程想要從一個文件中讀數據，則內核需判定哪一個文件系統包含該文件，以及該文件系統中的哪一塊包含該數據。當要從一個特定的磁盤塊上讀數據時，內核檢查是否該塊在緩衝區池中。如果不在，則分配給它一個空閒緩衝區。當要把數據寫到一個特定磁盤塊上時，內核檢查是否該塊在緩衝區池中。如果不在，則為那個塊分配一個空閒緩衝區。讀、寫磁盤塊的算法使用算法getblk（圖3-4）來對池中的緩衝區進行分配。
正如在圖2-1中所看到的那樣，文件子系統中的高層內核算法引用管理高速緩衝的算法。當它們試圖檢索一個塊時，由高層算法決定它們想要存取的邏輯設備號和塊號。舉例來說，正如在第4章將要看到的那樣，如果一個進程想要從一個文件中讀數據，則內核需判定哪一個文件系統包含該文件，以及該文件系統中的哪一塊包含該數據。當要從一個特定的磁盤塊上讀數據時，內核檢查是否該塊在緩衝區池中。如果不在，則分配給它一個空閒緩衝區。當要把數據寫到一個特定磁盤塊上時，內核檢查是否該塊在緩衝區池中。如果不在，則為那個塊分配一個空閒緩衝區。讀、寫磁盤塊的算法使用算法getblk（圖3-4）來對池中的緩衝區進行分配。
圖3-4 緩衝區分配算法
本節描述在算法getblk中內核把一個緩衝區分配給磁盤塊時可能出現的五種典型情況。
（1）內核發現該塊在它的散列隊列中，並且它的緩衝區是空閒的。
（2）內核在散列隊列中找不到該塊，因此，它從空閒表中分配一個緩衝區。
（3）內核在散列隊列中找不到該塊，並且，在試圖從空閒表中分配一個緩衝區（像第二種情況那樣）的時候，在空閒表中找到一個已標上了“延遲寫”標記的緩衝區。內核必須把“延遲寫”緩衝區的內容寫到磁盤上，並分配另一個緩衝區。
（4）內核在散列隊列中找不到該塊，並且空閒緩衝區表已空。
（5）內核在散列隊列中找到該塊，但它的緩衝區當前為忙。現在，讓我們更詳細地討論每種情況。
當根據設備號和塊號的組合在緩衝池中搜索一個塊時，內核找到含有該塊的散列隊列。它沿著緩衝區鏈表搜索散列隊列，直到（在第一種情況中）它找到了其設備號和塊號與所要搜索的設備號和塊號相匹配的緩衝區。內核檢查該緩衝區是否空閒。如果是，則將該緩衝區標記上“忙”以使其他進程[2]不能存取它。然後內核從空閒表上摘下該緩衝區，因為一個緩衝區不能既處於忙狀態又位於空閒表中。正如所見到的那樣，如果當緩衝區忙時其他進程企圖存取該塊，則它們去睡眠，直至該緩衝區被釋放時為止。圖3-5描繪了第一種情況。在那兒，內核在標記有“blkno 0 mod 4”的隊列上搜索第4塊。找到該緩衝區後，內核把它從空閒表中摘下，而將第5塊和第28塊相鄰接並留在空閒表上。
正如在圖2-1中所看到的那樣，文件子系統中的高層內核算法引用管理高速緩衝的算法。當它們試圖檢索一個塊時，由高層算法決定它們想要存取的邏輯設備號和塊號。舉例來說，正如在第4章將要看到的那樣，如果一個進程想要從一個文件中讀數據，則內核需判定哪一個文件系統包含該文件，以及該文件系統中的哪一塊包含該數據。當要從一個特定的磁盤塊上讀數據時，內核檢查是否該塊在緩衝區池中。如果不在，則分配給它一個空閒緩衝區。當要把數據寫到一個特定磁盤塊上時，內核檢查是否該塊在緩衝區池中。如果不在，則為那個塊分配一個空閒緩衝區。讀、寫磁盤塊的算法使用算法getblk（圖3-4）來對池中的緩衝區進行分配。
圖3-4 緩衝區分配算法
本節描述在算法getblk中內核把一個緩衝區分配給磁盤塊時可能出現的五種典型情況。
（1）內核發現該塊在它的散列隊列中，並且它的緩衝區是空閒的。
（2）內核在散列隊列中找不到該塊，因此，它從空閒表中分配一個緩衝區。
（3）內核在散列隊列中找不到該塊，並且，在試圖從空閒表中分配一個緩衝區（像第二種情況那樣）的時候，在空閒表中找到一個已標上了“延遲寫”標記的緩衝區。內核必須把“延遲寫”緩衝區的內容寫到磁盤上，並分配另一個緩衝區。
（4）內核在散列隊列中找不到該塊，並且空閒緩衝區表已空。
（5）內核在散列隊列中找到該塊，但它的緩衝區當前為忙。現在，讓我們更詳細地討論每種情況。
當根據設備號和塊號的組合在緩衝池中搜索一個塊時，內核找到含有該塊的散列隊列。它沿著緩衝區鏈表搜索散列隊列，直到（在第一種情況中）它找到了其設備號和塊號與所要搜索的設備號和塊號相匹配的緩衝區。內核檢查該緩衝區是否空閒。如果是，則將該緩衝區標記上“忙”以使其他進程[2]不能存取它。然後內核從空閒表上摘下該緩衝區，因為一個緩衝區不能既處於忙狀態又位於空閒表中。正如所見到的那樣，如果當緩衝區忙時其他進程企圖存取該塊，則它們去睡眠，直至該緩衝區被釋放時為止。圖3-5描繪了第一種情況。在那兒，內核在標記有“blkno 0 mod 4”的隊列上搜索第4塊。找到該緩衝區後，內核把它從空閒表中摘下，而將第5塊和第28塊相鄰接並留在空閒表上。
圖3-5 緩衝區分配的第一種情況
在繼續談另外幾種情況之前，讓我們考慮在把一個緩衝區分配了之後對它會發生什麼。內核可以把數據從磁盤讀至緩衝區，並進而操控它，或把數據寫到緩衝區，並且可能進而寫到磁盤上。內核把標有“忙”的緩衝區留在那裡，當它忙時，沒有別的進程能存取它以及改變它的內容，因此可保持該緩衝區中的數據的完整性。當內核結束使用該緩衝區時，按照算法brelse（圖3-6）釋放該緩衝區。它喚醒那些因該緩衝區忙而睡眠的進程，也喚醒
正如在圖2-1中所看到的那樣，文件子系統中的高層內核算法引用管理高速緩衝的算法。當它們試圖檢索一個塊時，由高層算法決定它們想要存取的邏輯設備號和塊號。舉例來說，正如在第4章將要看到的那樣，如果一個進程想要從一個文件中讀數據，則內核需判定哪一個文件系統包含該文件，以及該文件系統中的哪一塊包含該數據。當要從一個特定的磁盤塊上讀數據時，內核檢查是否該塊在緩衝區池中。如果不在，則分配給它一個空閒緩衝區。當要把數據寫到一個特定磁盤塊上時，內核檢查是否該塊在緩衝區池中。如果不在，則為那個塊分配一個空閒緩衝區。讀、寫磁盤塊的算法使用算法getblk（圖3-4）來對池中的緩衝區進行分配。
圖3-4 緩衝區分配算法
本節描述在算法getblk中內核把一個緩衝區分配給磁盤塊時可能出現的五種典型情況。
（1）內核發現該塊在它的散列隊列中，並且它的緩衝區是空閒的。
（2）內核在散列隊列中找不到該塊，因此，它從空閒表中分配一個緩衝區。
（3）內核在散列隊列中找不到該塊，並且，在試圖從空閒表中分配一個緩衝區（像第二種情況那樣）的時候，在空閒表中找到一個已標上了“延遲寫”標記的緩衝區。內核必須把“延遲寫”緩衝區的內容寫到磁盤上，並分配另一個緩衝區。
（4）內核在散列隊列中找不到該塊，並且空閒緩衝區表已空。
（5）內核在散列隊列中找到該塊，但它的緩衝區當前為忙。現在，讓我們更詳細地討論每種情況。
當根據設備號和塊號的組合在緩衝池中搜索一個塊時，內核找到含有該塊的散列隊列。它沿著緩衝區鏈表搜索散列隊列，直到（在第一種情況中）它找到了其設備號和塊號與所要搜索的設備號和塊號相匹配的緩衝區。內核檢查該緩衝區是否空閒。如果是，則將該緩衝區標記上“忙”以使其他進程[2]不能存取它。然後內核從空閒表上摘下該緩衝區，因為一個緩衝區不能既處於忙狀態又位於空閒表中。正如所見到的那樣，如果當緩衝區忙時其他進程企圖存取該塊，則它們去睡眠，直至該緩衝區被釋放時為止。圖3-5描繪了第一種情況。在那兒，內核在標記有“blkno 0 mod 4”的隊列上搜索第4塊。找到該緩衝區後，內核把它從空閒表中摘下，而將第5塊和第28塊相鄰接並留在空閒表上。
圖3-5 緩衝區分配的第一種情況
在繼續談另外幾種情況之前，讓我們考慮在把一個緩衝區分配了之後對它會發生什麼。內核可以把數據從磁盤讀至緩衝區，並進而操控它，或把數據寫到緩衝區，並且可能進而寫到磁盤上。內核把標有“忙”的緩衝區留在那裡，當它忙時，沒有別的進程能存取它以及改變它的內容，因此可保持該緩衝區中的數據的完整性。當內核結束使用該緩衝區時，按照算法brelse（圖3-6）釋放該緩衝區。它喚醒那些因該緩衝區忙而睡眠的進程，也喚醒
圖3-6 釋放緩衝區算法
因空閒表上沒有緩衝區而睡眠的那些進程。這兩類喚醒意味著被投入睡眠的那些進程現在可以使用釋放了的緩衝區了——雖然得到該緩衝區的第一個進程鎖上了它並且阻止其他進程得到它（見2.2節和2.4節）。內核把該緩衝區放到空閒表尾部，但是如果發生了一個I/O錯誤或者內核明確地在該緩衝區上標記上“舊”，則內核把該緩衝區放到空閒表頭部——本章的後面部分將看到這一點。現在，該緩衝區對於要索取它的所有進程都是空閒的。
正如當內核不再需要一個緩衝區時它引用算法brelse一樣，在處理一個磁盤中斷過程中，釋放用於往磁盤寫和從磁盤讀的異步I/O的緩衝區時，也要引用該算法。這將在3.4節看到。當操控空閒表時內核把處理機執行級提高以禁止磁盤中斷，從而防止了因嵌套調用brelse而引起的緩衝區指針的錯誤。如果當一個進程正在執行getblk時，一箇中斷處理程序引用brelse，則也會發生類似的壞結果。因此，在getblk中對全局有重要意義的地方也要提高處理機執行級。本章的練習詳細探討了這些情況。
在算法getblk中的第二種情況下，內核搜索應該包含該塊的那個散列隊列，但在那個散列隊列上找不到該塊。因為它不能“散列”在別處，所以該塊不可能在另一個散列隊列上，於是可以判定它不在高速緩衝中。因此，內核從空閒表中摘下第一個緩衝區。該緩衝區曾分配給另一個磁盤塊，並且也正在某個散列隊列上。如果該緩衝區沒有被標記上延遲寫（像隨後將要描述的那樣），則內核標記該緩衝區為忙，將它從當前所在的散列隊列中摘出，把該緩衝頭部的設備號和塊號重新指定為當前進程正在搜索的磁盤塊的設備號和塊號，並且把該緩衝區放到正確的散列隊列中。內核使用該緩衝區，但是並未記錄該緩衝區從前包含有另一個磁盤塊的數據。如果這時有一個進程搜索舊磁盤塊，則它在池中將找不到這個舊磁盤塊，它必須嚴格地按照前面所描述的那樣，從空閒表中為這個舊磁盤塊分配兩個新緩衝區。當內核結束對該緩衝區的使用時，它按如上所描述的那樣把該緩衝區釋放。例如，在圖3-7中，內核搜索第18塊但是在標有“blkno 2 mod 4”的散列隊列上沒有找到它，因此，內核從空閒表上摘下第一個緩衝區（第3塊），將它分配給第18塊，並把它放到適當的散列隊列中。
在算法getblk的第三種情況下，內核也必須從空閒表中分配一個緩衝區。然而，它發現從空閒表中摘下的緩衝區已被標記上“延遲寫”，因此，它必須在使用該緩衝區之前，將該緩衝區的內容寫到磁盤上。內核開始了一個往磁盤的異步寫，並且試圖從空閒表上分配另一個緩衝區。當異步寫完成時，內核把該緩衝區釋放，並把它放到空閒表頭部。在異步寫之前，該緩衝區已經從空閒表尾部出發遷移到了空閒表頭部。假使在異步寫之後，內核把該緩衝區放到空閒表尾部，則該緩衝區會做一次多餘的貫穿空閒表的移動，這就與最近最少使用算法相悖了。舉例來說，在圖3-8中，內核沒有找到第18塊，但是，當它試圖分配空閒表上的頭兩個緩衝區（每次一個）時，發現它們標記著延遲寫。內核把它們從空閒表中摘下，為這兩塊啟動往磁盤上寫的操作。內核分配空閒表上塊號為4的第三個緩衝區。它適當地重新對該緩衝區的設備號和塊號字段賦值，並且把該緩衝區——現在就是標記著第18塊的緩衝區放到它的新的散列隊列中。
正如在圖2-1中所看到的那樣，文件子系統中的高層內核算法引用管理高速緩衝的算法。當它們試圖檢索一個塊時，由高層算法決定它們想要存取的邏輯設備號和塊號。舉例來說，正如在第4章將要看到的那樣，如果一個進程想要從一個文件中讀數據，則內核需判定哪一個文件系統包含該文件，以及該文件系統中的哪一塊包含該數據。當要從一個特定的磁盤塊上讀數據時，內核檢查是否該塊在緩衝區池中。如果不在，則分配給它一個空閒緩衝區。當要把數據寫到一個特定磁盤塊上時，內核檢查是否該塊在緩衝區池中。如果不在，則為那個塊分配一個空閒緩衝區。讀、寫磁盤塊的算法使用算法getblk（圖3-4）來對池中的緩衝區進行分配。
圖3-4 緩衝區分配算法
本節描述在算法getblk中內核把一個緩衝區分配給磁盤塊時可能出現的五種典型情況。
（1）內核發現該塊在它的散列隊列中，並且它的緩衝區是空閒的。
（2）內核在散列隊列中找不到該塊，因此，它從空閒表中分配一個緩衝區。
（3）內核在散列隊列中找不到該塊，並且，在試圖從空閒表中分配一個緩衝區（像第二種情況那樣）的時候，在空閒表中找到一個已標上了“延遲寫”標記的緩衝區。內核必須把“延遲寫”緩衝區的內容寫到磁盤上，並分配另一個緩衝區。
（4）內核在散列隊列中找不到該塊，並且空閒緩衝區表已空。
（5）內核在散列隊列中找到該塊，但它的緩衝區當前為忙。現在，讓我們更詳細地討論每種情況。
當根據設備號和塊號的組合在緩衝池中搜索一個塊時，內核找到含有該塊的散列隊列。它沿著緩衝區鏈表搜索散列隊列，直到（在第一種情況中）它找到了其設備號和塊號與所要搜索的設備號和塊號相匹配的緩衝區。內核檢查該緩衝區是否空閒。如果是，則將該緩衝區標記上“忙”以使其他進程[2]不能存取它。然後內核從空閒表上摘下該緩衝區，因為一個緩衝區不能既處於忙狀態又位於空閒表中。正如所見到的那樣，如果當緩衝區忙時其他進程企圖存取該塊，則它們去睡眠，直至該緩衝區被釋放時為止。圖3-5描繪了第一種情況。在那兒，內核在標記有“blkno 0 mod 4”的隊列上搜索第4塊。找到該緩衝區後，內核把它從空閒表中摘下，而將第5塊和第28塊相鄰接並留在空閒表上。
圖3-5 緩衝區分配的第一種情況
在繼續談另外幾種情況之前，讓我們考慮在把一個緩衝區分配了之後對它會發生什麼。內核可以把數據從磁盤讀至緩衝區，並進而操控它，或把數據寫到緩衝區，並且可能進而寫到磁盤上。內核把標有“忙”的緩衝區留在那裡，當它忙時，沒有別的進程能存取它以及改變它的內容，因此可保持該緩衝區中的數據的完整性。當內核結束使用該緩衝區時，按照算法brelse（圖3-6）釋放該緩衝區。它喚醒那些因該緩衝區忙而睡眠的進程，也喚醒
圖3-6 釋放緩衝區算法
因空閒表上沒有緩衝區而睡眠的那些進程。這兩類喚醒意味著被投入睡眠的那些進程現在可以使用釋放了的緩衝區了——雖然得到該緩衝區的第一個進程鎖上了它並且阻止其他進程得到它（見2.2節和2.4節）。內核把該緩衝區放到空閒表尾部，但是如果發生了一個I/O錯誤或者內核明確地在該緩衝區上標記上“舊”，則內核把該緩衝區放到空閒表頭部——本章的後面部分將看到這一點。現在，該緩衝區對於要索取它的所有進程都是空閒的。
正如當內核不再需要一個緩衝區時它引用算法brelse一樣，在處理一個磁盤中斷過程中，釋放用於往磁盤寫和從磁盤讀的異步I/O的緩衝區時，也要引用該算法。這將在3.4節看到。當操控空閒表時內核把處理機執行級提高以禁止磁盤中斷，從而防止了因嵌套調用brelse而引起的緩衝區指針的錯誤。如果當一個進程正在執行getblk時，一箇中斷處理程序引用brelse，則也會發生類似的壞結果。因此，在getblk中對全局有重要意義的地方也要提高處理機執行級。本章的練習詳細探討了這些情況。
在算法getblk中的第二種情況下，內核搜索應該包含該塊的那個散列隊列，但在那個散列隊列上找不到該塊。因為它不能“散列”在別處，所以該塊不可能在另一個散列隊列上，於是可以判定它不在高速緩衝中。因此，內核從空閒表中摘下第一個緩衝區。該緩衝區曾分配給另一個磁盤塊，並且也正在某個散列隊列上。如果該緩衝區沒有被標記上延遲寫（像隨後將要描述的那樣），則內核標記該緩衝區為忙，將它從當前所在的散列隊列中摘出，把該緩衝頭部的設備號和塊號重新指定為當前進程正在搜索的磁盤塊的設備號和塊號，並且把該緩衝區放到正確的散列隊列中。內核使用該緩衝區，但是並未記錄該緩衝區從前包含有另一個磁盤塊的數據。如果這時有一個進程搜索舊磁盤塊，則它在池中將找不到這個舊磁盤塊，它必須嚴格地按照前面所描述的那樣，從空閒表中為這個舊磁盤塊分配兩個新緩衝區。當內核結束對該緩衝區的使用時，它按如上所描述的那樣把該緩衝區釋放。例如，在圖3-7中，內核搜索第18塊但是在標有“blkno 2 mod 4”的散列隊列上沒有找到它，因此，內核從空閒表上摘下第一個緩衝區（第3塊），將它分配給第18塊，並把它放到適當的散列隊列中。
在算法getblk的第三種情況下，內核也必須從空閒表中分配一個緩衝區。然而，它發現從空閒表中摘下的緩衝區已被標記上“延遲寫”，因此，它必須在使用該緩衝區之前，將該緩衝區的內容寫到磁盤上。內核開始了一個往磁盤的異步寫，並且試圖從空閒表上分配另一個緩衝區。當異步寫完成時，內核把該緩衝區釋放，並把它放到空閒表頭部。在異步寫之前，該緩衝區已經從空閒表尾部出發遷移到了空閒表頭部。假使在異步寫之後，內核把該緩衝區放到空閒表尾部，則該緩衝區會做一次多餘的貫穿空閒表的移動，這就與最近最少使用算法相悖了。舉例來說，在圖3-8中，內核沒有找到第18塊，但是，當它試圖分配空閒表上的頭兩個緩衝區（每次一個）時，發現它們標記著延遲寫。內核把它們從空閒表中摘下，為這兩塊啟動往磁盤上寫的操作。內核分配空閒表上塊號為4的第三個緩衝區。它適當地重新對該緩衝區的設備號和塊號字段賦值，並且把該緩衝區——現在就是標記著第18塊的緩衝區放到它的新的散列隊列中。
圖3-7 緩衝區分配的第二種情況
正如在圖2-1中所看到的那樣，文件子系統中的高層內核算法引用管理高速緩衝的算法。當它們試圖檢索一個塊時，由高層算法決定它們想要存取的邏輯設備號和塊號。舉例來說，正如在第4章將要看到的那樣，如果一個進程想要從一個文件中讀數據，則內核需判定哪一個文件系統包含該文件，以及該文件系統中的哪一塊包含該數據。當要從一個特定的磁盤塊上讀數據時，內核檢查是否該塊在緩衝區池中。如果不在，則分配給它一個空閒緩衝區。當要把數據寫到一個特定磁盤塊上時，內核檢查是否該塊在緩衝區池中。如果不在，則為那個塊分配一個空閒緩衝區。讀、寫磁盤塊的算法使用算法getblk（圖3-4）來對池中的緩衝區進行分配。
圖3-4 緩衝區分配算法
本節描述在算法getblk中內核把一個緩衝區分配給磁盤塊時可能出現的五種典型情況。
（1）內核發現該塊在它的散列隊列中，並且它的緩衝區是空閒的。
（2）內核在散列隊列中找不到該塊，因此，它從空閒表中分配一個緩衝區。
（3）內核在散列隊列中找不到該塊，並且，在試圖從空閒表中分配一個緩衝區（像第二種情況那樣）的時候，在空閒表中找到一個已標上了“延遲寫”標記的緩衝區。內核必須把“延遲寫”緩衝區的內容寫到磁盤上，並分配另一個緩衝區。
（4）內核在散列隊列中找不到該塊，並且空閒緩衝區表已空。
（5）內核在散列隊列中找到該塊，但它的緩衝區當前為忙。現在，讓我們更詳細地討論每種情況。
當根據設備號和塊號的組合在緩衝池中搜索一個塊時，內核找到含有該塊的散列隊列。它沿著緩衝區鏈表搜索散列隊列，直到（在第一種情況中）它找到了其設備號和塊號與所要搜索的設備號和塊號相匹配的緩衝區。內核檢查該緩衝區是否空閒。如果是，則將該緩衝區標記上“忙”以使其他進程[2]不能存取它。然後內核從空閒表上摘下該緩衝區，因為一個緩衝區不能既處於忙狀態又位於空閒表中。正如所見到的那樣，如果當緩衝區忙時其他進程企圖存取該塊，則它們去睡眠，直至該緩衝區被釋放時為止。圖3-5描繪了第一種情況。在那兒，內核在標記有“blkno 0 mod 4”的隊列上搜索第4塊。找到該緩衝區後，內核把它從空閒表中摘下，而將第5塊和第28塊相鄰接並留在空閒表上。
圖3-5 緩衝區分配的第一種情況
在繼續談另外幾種情況之前，讓我們考慮在把一個緩衝區分配了之後對它會發生什麼。內核可以把數據從磁盤讀至緩衝區，並進而操控它，或把數據寫到緩衝區，並且可能進而寫到磁盤上。內核把標有“忙”的緩衝區留在那裡，當它忙時，沒有別的進程能存取它以及改變它的內容，因此可保持該緩衝區中的數據的完整性。當內核結束使用該緩衝區時，按照算法brelse（圖3-6）釋放該緩衝區。它喚醒那些因該緩衝區忙而睡眠的進程，也喚醒
圖3-6 釋放緩衝區算法
因空閒表上沒有緩衝區而睡眠的那些進程。這兩類喚醒意味著被投入睡眠的那些進程現在可以使用釋放了的緩衝區了——雖然得到該緩衝區的第一個進程鎖上了它並且阻止其他進程得到它（見2.2節和2.4節）。內核把該緩衝區放到空閒表尾部，但是如果發生了一個I/O錯誤或者內核明確地在該緩衝區上標記上“舊”，則內核把該緩衝區放到空閒表頭部——本章的後面部分將看到這一點。現在，該緩衝區對於要索取它的所有進程都是空閒的。
正如當內核不再需要一個緩衝區時它引用算法brelse一樣，在處理一個磁盤中斷過程中，釋放用於往磁盤寫和從磁盤讀的異步I/O的緩衝區時，也要引用該算法。這將在3.4節看到。當操控空閒表時內核把處理機執行級提高以禁止磁盤中斷，從而防止了因嵌套調用brelse而引起的緩衝區指針的錯誤。如果當一個進程正在執行getblk時，一箇中斷處理程序引用brelse，則也會發生類似的壞結果。因此，在getblk中對全局有重要意義的地方也要提高處理機執行級。本章的練習詳細探討了這些情況。
在算法getblk中的第二種情況下，內核搜索應該包含該塊的那個散列隊列，但在那個散列隊列上找不到該塊。因為它不能“散列”在別處，所以該塊不可能在另一個散列隊列上，於是可以判定它不在高速緩衝中。因此，內核從空閒表中摘下第一個緩衝區。該緩衝區曾分配給另一個磁盤塊，並且也正在某個散列隊列上。如果該緩衝區沒有被標記上延遲寫（像隨後將要描述的那樣），則內核標記該緩衝區為忙，將它從當前所在的散列隊列中摘出，把該緩衝頭部的設備號和塊號重新指定為當前進程正在搜索的磁盤塊的設備號和塊號，並且把該緩衝區放到正確的散列隊列中。內核使用該緩衝區，但是並未記錄該緩衝區從前包含有另一個磁盤塊的數據。如果這時有一個進程搜索舊磁盤塊，則它在池中將找不到這個舊磁盤塊，它必須嚴格地按照前面所描述的那樣，從空閒表中為這個舊磁盤塊分配兩個新緩衝區。當內核結束對該緩衝區的使用時，它按如上所描述的那樣把該緩衝區釋放。例如，在圖3-7中，內核搜索第18塊但是在標有“blkno 2 mod 4”的散列隊列上沒有找到它，因此，內核從空閒表上摘下第一個緩衝區（第3塊），將它分配給第18塊，並把它放到適當的散列隊列中。
在算法getblk的第三種情況下，內核也必須從空閒表中分配一個緩衝區。然而，它發現從空閒表中摘下的緩衝區已被標記上“延遲寫”，因此，它必須在使用該緩衝區之前，將該緩衝區的內容寫到磁盤上。內核開始了一個往磁盤的異步寫，並且試圖從空閒表上分配另一個緩衝區。當異步寫完成時，內核把該緩衝區釋放，並把它放到空閒表頭部。在異步寫之前，該緩衝區已經從空閒表尾部出發遷移到了空閒表頭部。假使在異步寫之後，內核把該緩衝區放到空閒表尾部，則該緩衝區會做一次多餘的貫穿空閒表的移動，這就與最近最少使用算法相悖了。舉例來說，在圖3-8中，內核沒有找到第18塊，但是，當它試圖分配空閒表上的頭兩個緩衝區（每次一個）時，發現它們標記著延遲寫。內核把它們從空閒表中摘下，為這兩塊啟動往磁盤上寫的操作。內核分配空閒表上塊號為4的第三個緩衝區。它適當地重新對該緩衝區的設備號和塊號字段賦值，並且把該緩衝區——現在就是標記著第18塊的緩衝區放到它的新的散列隊列中。
圖3-7 緩衝區分配的第二種情況
圖3-8 緩衝區分配的第三種情況
第四種情況（圖 3-9）下，為進程A而動作著的內核沒有在它的散列隊列上找到該磁盤塊，因此，像第二種情況那樣，它試圖從空閒表上分配一個新的緩衝區。然而，在空閒表上已沒有緩衝區可供分配，因此，進程A去睡眠，直至另一進程執行算法brelse，釋放一個緩衝區。當內核調度到進程A時，它必須為該塊重新搜索散列隊列。它不能立即從空閒表中分配緩衝區，因為可能有多個進程正在等候空閒緩衝區，並且可能其中有一個進程已經把一個新的空閒緩衝區分配給進程A所尋找的目標磁盤塊了。因此，需要再次搜索該塊，保證僅僅一個緩衝區包含有該塊。圖3-10描繪了兩個進程間為一個空閒緩衝區而進行的競爭。
正如在圖2-1中所看到的那樣，文件子系統中的高層內核算法引用管理高速緩衝的算法。當它們試圖檢索一個塊時，由高層算法決定它們想要存取的邏輯設備號和塊號。舉例來說，正如在第4章將要看到的那樣，如果一個進程想要從一個文件中讀數據，則內核需判定哪一個文件系統包含該文件，以及該文件系統中的哪一塊包含該數據。當要從一個特定的磁盤塊上讀數據時，內核檢查是否該塊在緩衝區池中。如果不在，則分配給它一個空閒緩衝區。當要把數據寫到一個特定磁盤塊上時，內核檢查是否該塊在緩衝區池中。如果不在，則為那個塊分配一個空閒緩衝區。讀、寫磁盤塊的算法使用算法getblk（圖3-4）來對池中的緩衝區進行分配。
圖3-4 緩衝區分配算法
本節描述在算法getblk中內核把一個緩衝區分配給磁盤塊時可能出現的五種典型情況。
（1）內核發現該塊在它的散列隊列中，並且它的緩衝區是空閒的。
（2）內核在散列隊列中找不到該塊，因此，它從空閒表中分配一個緩衝區。
（3）內核在散列隊列中找不到該塊，並且，在試圖從空閒表中分配一個緩衝區（像第二種情況那樣）的時候，在空閒表中找到一個已標上了“延遲寫”標記的緩衝區。內核必須把“延遲寫”緩衝區的內容寫到磁盤上，並分配另一個緩衝區。
（4）內核在散列隊列中找不到該塊，並且空閒緩衝區表已空。
（5）內核在散列隊列中找到該塊，但它的緩衝區當前為忙。現在，讓我們更詳細地討論每種情況。
當根據設備號和塊號的組合在緩衝池中搜索一個塊時，內核找到含有該塊的散列隊列。它沿著緩衝區鏈表搜索散列隊列，直到（在第一種情況中）它找到了其設備號和塊號與所要搜索的設備號和塊號相匹配的緩衝區。內核檢查該緩衝區是否空閒。如果是，則將該緩衝區標記上“忙”以使其他進程[2]不能存取它。然後內核從空閒表上摘下該緩衝區，因為一個緩衝區不能既處於忙狀態又位於空閒表中。正如所見到的那樣，如果當緩衝區忙時其他進程企圖存取該塊，則它們去睡眠，直至該緩衝區被釋放時為止。圖3-5描繪了第一種情況。在那兒，內核在標記有“blkno 0 mod 4”的隊列上搜索第4塊。找到該緩衝區後，內核把它從空閒表中摘下，而將第5塊和第28塊相鄰接並留在空閒表上。
圖3-5 緩衝區分配的第一種情況
在繼續談另外幾種情況之前，讓我們考慮在把一個緩衝區分配了之後對它會發生什麼。內核可以把數據從磁盤讀至緩衝區，並進而操控它，或把數據寫到緩衝區，並且可能進而寫到磁盤上。內核把標有“忙”的緩衝區留在那裡，當它忙時，沒有別的進程能存取它以及改變它的內容，因此可保持該緩衝區中的數據的完整性。當內核結束使用該緩衝區時，按照算法brelse（圖3-6）釋放該緩衝區。它喚醒那些因該緩衝區忙而睡眠的進程，也喚醒
圖3-6 釋放緩衝區算法
因空閒表上沒有緩衝區而睡眠的那些進程。這兩類喚醒意味著被投入睡眠的那些進程現在可以使用釋放了的緩衝區了——雖然得到該緩衝區的第一個進程鎖上了它並且阻止其他進程得到它（見2.2節和2.4節）。內核把該緩衝區放到空閒表尾部，但是如果發生了一個I/O錯誤或者內核明確地在該緩衝區上標記上“舊”，則內核把該緩衝區放到空閒表頭部——本章的後面部分將看到這一點。現在，該緩衝區對於要索取它的所有進程都是空閒的。
正如當內核不再需要一個緩衝區時它引用算法brelse一樣，在處理一個磁盤中斷過程中，釋放用於往磁盤寫和從磁盤讀的異步I/O的緩衝區時，也要引用該算法。這將在3.4節看到。當操控空閒表時內核把處理機執行級提高以禁止磁盤中斷，從而防止了因嵌套調用brelse而引起的緩衝區指針的錯誤。如果當一個進程正在執行getblk時，一箇中斷處理程序引用brelse，則也會發生類似的壞結果。因此，在getblk中對全局有重要意義的地方也要提高處理機執行級。本章的練習詳細探討了這些情況。
在算法getblk中的第二種情況下，內核搜索應該包含該塊的那個散列隊列，但在那個散列隊列上找不到該塊。因為它不能“散列”在別處，所以該塊不可能在另一個散列隊列上，於是可以判定它不在高速緩衝中。因此，內核從空閒表中摘下第一個緩衝區。該緩衝區曾分配給另一個磁盤塊，並且也正在某個散列隊列上。如果該緩衝區沒有被標記上延遲寫（像隨後將要描述的那樣），則內核標記該緩衝區為忙，將它從當前所在的散列隊列中摘出，把該緩衝頭部的設備號和塊號重新指定為當前進程正在搜索的磁盤塊的設備號和塊號，並且把該緩衝區放到正確的散列隊列中。內核使用該緩衝區，但是並未記錄該緩衝區從前包含有另一個磁盤塊的數據。如果這時有一個進程搜索舊磁盤塊，則它在池中將找不到這個舊磁盤塊，它必須嚴格地按照前面所描述的那樣，從空閒表中為這個舊磁盤塊分配兩個新緩衝區。當內核結束對該緩衝區的使用時，它按如上所描述的那樣把該緩衝區釋放。例如，在圖3-7中，內核搜索第18塊但是在標有“blkno 2 mod 4”的散列隊列上沒有找到它，因此，內核從空閒表上摘下第一個緩衝區（第3塊），將它分配給第18塊，並把它放到適當的散列隊列中。
在算法getblk的第三種情況下，內核也必須從空閒表中分配一個緩衝區。然而，它發現從空閒表中摘下的緩衝區已被標記上“延遲寫”，因此，它必須在使用該緩衝區之前，將該緩衝區的內容寫到磁盤上。內核開始了一個往磁盤的異步寫，並且試圖從空閒表上分配另一個緩衝區。當異步寫完成時，內核把該緩衝區釋放，並把它放到空閒表頭部。在異步寫之前，該緩衝區已經從空閒表尾部出發遷移到了空閒表頭部。假使在異步寫之後，內核把該緩衝區放到空閒表尾部，則該緩衝區會做一次多餘的貫穿空閒表的移動，這就與最近最少使用算法相悖了。舉例來說，在圖3-8中，內核沒有找到第18塊，但是，當它試圖分配空閒表上的頭兩個緩衝區（每次一個）時，發現它們標記著延遲寫。內核把它們從空閒表中摘下，為這兩塊啟動往磁盤上寫的操作。內核分配空閒表上塊號為4的第三個緩衝區。它適當地重新對該緩衝區的設備號和塊號字段賦值，並且把該緩衝區——現在就是標記著第18塊的緩衝區放到它的新的散列隊列中。
圖3-7 緩衝區分配的第二種情況
圖3-8 緩衝區分配的第三種情況
第四種情況（圖 3-9）下，為進程A而動作著的內核沒有在它的散列隊列上找到該磁盤塊，因此，像第二種情況那樣，它試圖從空閒表上分配一個新的緩衝區。然而，在空閒表上已沒有緩衝區可供分配，因此，進程A去睡眠，直至另一進程執行算法brelse，釋放一個緩衝區。當內核調度到進程A時，它必須為該塊重新搜索散列隊列。它不能立即從空閒表中分配緩衝區，因為可能有多個進程正在等候空閒緩衝區，並且可能其中有一個進程已經把一個新的空閒緩衝區分配給進程A所尋找的目標磁盤塊了。因此，需要再次搜索該塊，保證僅僅一個緩衝區包含有該塊。圖3-10描繪了兩個進程間為一個空閒緩衝區而進行的競爭。
圖3-9 緩衝區分配的第四種情況
正如在圖2-1中所看到的那樣，文件子系統中的高層內核算法引用管理高速緩衝的算法。當它們試圖檢索一個塊時，由高層算法決定它們想要存取的邏輯設備號和塊號。舉例來說，正如在第4章將要看到的那樣，如果一個進程想要從一個文件中讀數據，則內核需判定哪一個文件系統包含該文件，以及該文件系統中的哪一塊包含該數據。當要從一個特定的磁盤塊上讀數據時，內核檢查是否該塊在緩衝區池中。如果不在，則分配給它一個空閒緩衝區。當要把數據寫到一個特定磁盤塊上時，內核檢查是否該塊在緩衝區池中。如果不在，則為那個塊分配一個空閒緩衝區。讀、寫磁盤塊的算法使用算法getblk（圖3-4）來對池中的緩衝區進行分配。
圖3-4 緩衝區分配算法
本節描述在算法getblk中內核把一個緩衝區分配給磁盤塊時可能出現的五種典型情況。
（1）內核發現該塊在它的散列隊列中，並且它的緩衝區是空閒的。
（2）內核在散列隊列中找不到該塊，因此，它從空閒表中分配一個緩衝區。
（3）內核在散列隊列中找不到該塊，並且，在試圖從空閒表中分配一個緩衝區（像第二種情況那樣）的時候，在空閒表中找到一個已標上了“延遲寫”標記的緩衝區。內核必須把“延遲寫”緩衝區的內容寫到磁盤上，並分配另一個緩衝區。
（4）內核在散列隊列中找不到該塊，並且空閒緩衝區表已空。
（5）內核在散列隊列中找到該塊，但它的緩衝區當前為忙。現在，讓我們更詳細地討論每種情況。
當根據設備號和塊號的組合在緩衝池中搜索一個塊時，內核找到含有該塊的散列隊列。它沿著緩衝區鏈表搜索散列隊列，直到（在第一種情況中）它找到了其設備號和塊號與所要搜索的設備號和塊號相匹配的緩衝區。內核檢查該緩衝區是否空閒。如果是，則將該緩衝區標記上“忙”以使其他進程[2]不能存取它。然後內核從空閒表上摘下該緩衝區，因為一個緩衝區不能既處於忙狀態又位於空閒表中。正如所見到的那樣，如果當緩衝區忙時其他進程企圖存取該塊，則它們去睡眠，直至該緩衝區被釋放時為止。圖3-5描繪了第一種情況。在那兒，內核在標記有“blkno 0 mod 4”的隊列上搜索第4塊。找到該緩衝區後，內核把它從空閒表中摘下，而將第5塊和第28塊相鄰接並留在空閒表上。
圖3-5 緩衝區分配的第一種情況
在繼續談另外幾種情況之前，讓我們考慮在把一個緩衝區分配了之後對它會發生什麼。內核可以把數據從磁盤讀至緩衝區，並進而操控它，或把數據寫到緩衝區，並且可能進而寫到磁盤上。內核把標有“忙”的緩衝區留在那裡，當它忙時，沒有別的進程能存取它以及改變它的內容，因此可保持該緩衝區中的數據的完整性。當內核結束使用該緩衝區時，按照算法brelse（圖3-6）釋放該緩衝區。它喚醒那些因該緩衝區忙而睡眠的進程，也喚醒
圖3-6 釋放緩衝區算法
因空閒表上沒有緩衝區而睡眠的那些進程。這兩類喚醒意味著被投入睡眠的那些進程現在可以使用釋放了的緩衝區了——雖然得到該緩衝區的第一個進程鎖上了它並且阻止其他進程得到它（見2.2節和2.4節）。內核把該緩衝區放到空閒表尾部，但是如果發生了一個I/O錯誤或者內核明確地在該緩衝區上標記上“舊”，則內核把該緩衝區放到空閒表頭部——本章的後面部分將看到這一點。現在，該緩衝區對於要索取它的所有進程都是空閒的。
正如當內核不再需要一個緩衝區時它引用算法brelse一樣，在處理一個磁盤中斷過程中，釋放用於往磁盤寫和從磁盤讀的異步I/O的緩衝區時，也要引用該算法。這將在3.4節看到。當操控空閒表時內核把處理機執行級提高以禁止磁盤中斷，從而防止了因嵌套調用brelse而引起的緩衝區指針的錯誤。如果當一個進程正在執行getblk時，一箇中斷處理程序引用brelse，則也會發生類似的壞結果。因此，在getblk中對全局有重要意義的地方也要提高處理機執行級。本章的練習詳細探討了這些情況。
在算法getblk中的第二種情況下，內核搜索應該包含該塊的那個散列隊列，但在那個散列隊列上找不到該塊。因為它不能“散列”在別處，所以該塊不可能在另一個散列隊列上，於是可以判定它不在高速緩衝中。因此，內核從空閒表中摘下第一個緩衝區。該緩衝區曾分配給另一個磁盤塊，並且也正在某個散列隊列上。如果該緩衝區沒有被標記上延遲寫（像隨後將要描述的那樣），則內核標記該緩衝區為忙，將它從當前所在的散列隊列中摘出，把該緩衝頭部的設備號和塊號重新指定為當前進程正在搜索的磁盤塊的設備號和塊號，並且把該緩衝區放到正確的散列隊列中。內核使用該緩衝區，但是並未記錄該緩衝區從前包含有另一個磁盤塊的數據。如果這時有一個進程搜索舊磁盤塊，則它在池中將找不到這個舊磁盤塊，它必須嚴格地按照前面所描述的那樣，從空閒表中為這個舊磁盤塊分配兩個新緩衝區。當內核結束對該緩衝區的使用時，它按如上所描述的那樣把該緩衝區釋放。例如，在圖3-7中，內核搜索第18塊但是在標有“blkno 2 mod 4”的散列隊列上沒有找到它，因此，內核從空閒表上摘下第一個緩衝區（第3塊），將它分配給第18塊，並把它放到適當的散列隊列中。
在算法getblk的第三種情況下，內核也必須從空閒表中分配一個緩衝區。然而，它發現從空閒表中摘下的緩衝區已被標記上“延遲寫”，因此，它必須在使用該緩衝區之前，將該緩衝區的內容寫到磁盤上。內核開始了一個往磁盤的異步寫，並且試圖從空閒表上分配另一個緩衝區。當異步寫完成時，內核把該緩衝區釋放，並把它放到空閒表頭部。在異步寫之前，該緩衝區已經從空閒表尾部出發遷移到了空閒表頭部。假使在異步寫之後，內核把該緩衝區放到空閒表尾部，則該緩衝區會做一次多餘的貫穿空閒表的移動，這就與最近最少使用算法相悖了。舉例來說，在圖3-8中，內核沒有找到第18塊，但是，當它試圖分配空閒表上的頭兩個緩衝區（每次一個）時，發現它們標記著延遲寫。內核把它們從空閒表中摘下，為這兩塊啟動往磁盤上寫的操作。內核分配空閒表上塊號為4的第三個緩衝區。它適當地重新對該緩衝區的設備號和塊號字段賦值，並且把該緩衝區——現在就是標記著第18塊的緩衝區放到它的新的散列隊列中。
圖3-7 緩衝區分配的第二種情況
圖3-8 緩衝區分配的第三種情況
第四種情況（圖 3-9）下，為進程A而動作著的內核沒有在它的散列隊列上找到該磁盤塊，因此，像第二種情況那樣，它試圖從空閒表上分配一個新的緩衝區。然而，在空閒表上已沒有緩衝區可供分配，因此，進程A去睡眠，直至另一進程執行算法brelse，釋放一個緩衝區。當內核調度到進程A時，它必須為該塊重新搜索散列隊列。它不能立即從空閒表中分配緩衝區，因為可能有多個進程正在等候空閒緩衝區，並且可能其中有一個進程已經把一個新的空閒緩衝區分配給進程A所尋找的目標磁盤塊了。因此，需要再次搜索該塊，保證僅僅一個緩衝區包含有該塊。圖3-10描繪了兩個進程間為一個空閒緩衝區而進行的競爭。
圖3-9 緩衝區分配的第四種情況
圖3-10 競爭緩衝區
最後一種情況（圖3-11）是複雜的，因為它牽涉幾個進程間的複雜關係。假設內核正在為進程A動作，搜索一個磁盤塊，並分配一個緩衝區，但是在釋放該緩衝區之前去睡眠了。舉例來說，如果進程A試圖讀一磁盤塊並且像第二種情況那樣分配了一個緩衝區，則當它等候從磁盤上的I/O傳輸完成時，它將去睡眠。當進程A睡眠時，假設內核調度到第二個進程B，B試圖存取那個緩衝區剛剛被進程A鎖上了的磁盤塊。進程B（進入第五種情況）將在散列隊列上找到那個上了鎖的塊。因為使用上著鎖的緩衝區是非法的，並且為一個磁盤塊分配第二個緩衝區也是非法的，所以進程B在緩衝區上打上“有需求”的標記，然後去睡眠，等候進程A釋放該緩衝區。
正如在圖2-1中所看到的那樣，文件子系統中的高層內核算法引用管理高速緩衝的算法。當它們試圖檢索一個塊時，由高層算法決定它們想要存取的邏輯設備號和塊號。舉例來說，正如在第4章將要看到的那樣，如果一個進程想要從一個文件中讀數據，則內核需判定哪一個文件系統包含該文件，以及該文件系統中的哪一塊包含該數據。當要從一個特定的磁盤塊上讀數據時，內核檢查是否該塊在緩衝區池中。如果不在，則分配給它一個空閒緩衝區。當要把數據寫到一個特定磁盤塊上時，內核檢查是否該塊在緩衝區池中。如果不在，則為那個塊分配一個空閒緩衝區。讀、寫磁盤塊的算法使用算法getblk（圖3-4）來對池中的緩衝區進行分配。
圖3-4 緩衝區分配算法
本節描述在算法getblk中內核把一個緩衝區分配給磁盤塊時可能出現的五種典型情況。
（1）內核發現該塊在它的散列隊列中，並且它的緩衝區是空閒的。
（2）內核在散列隊列中找不到該塊，因此，它從空閒表中分配一個緩衝區。
（3）內核在散列隊列中找不到該塊，並且，在試圖從空閒表中分配一個緩衝區（像第二種情況那樣）的時候，在空閒表中找到一個已標上了“延遲寫”標記的緩衝區。內核必須把“延遲寫”緩衝區的內容寫到磁盤上，並分配另一個緩衝區。
（4）內核在散列隊列中找不到該塊，並且空閒緩衝區表已空。
（5）內核在散列隊列中找到該塊，但它的緩衝區當前為忙。現在，讓我們更詳細地討論每種情況。
當根據設備號和塊號的組合在緩衝池中搜索一個塊時，內核找到含有該塊的散列隊列。它沿著緩衝區鏈表搜索散列隊列，直到（在第一種情況中）它找到了其設備號和塊號與所要搜索的設備號和塊號相匹配的緩衝區。內核檢查該緩衝區是否空閒。如果是，則將該緩衝區標記上“忙”以使其他進程[2]不能存取它。然後內核從空閒表上摘下該緩衝區，因為一個緩衝區不能既處於忙狀態又位於空閒表中。正如所見到的那樣，如果當緩衝區忙時其他進程企圖存取該塊，則它們去睡眠，直至該緩衝區被釋放時為止。圖3-5描繪了第一種情況。在那兒，內核在標記有“blkno 0 mod 4”的隊列上搜索第4塊。找到該緩衝區後，內核把它從空閒表中摘下，而將第5塊和第28塊相鄰接並留在空閒表上。
圖3-5 緩衝區分配的第一種情況
在繼續談另外幾種情況之前，讓我們考慮在把一個緩衝區分配了之後對它會發生什麼。內核可以把數據從磁盤讀至緩衝區，並進而操控它，或把數據寫到緩衝區，並且可能進而寫到磁盤上。內核把標有“忙”的緩衝區留在那裡，當它忙時，沒有別的進程能存取它以及改變它的內容，因此可保持該緩衝區中的數據的完整性。當內核結束使用該緩衝區時，按照算法brelse（圖3-6）釋放該緩衝區。它喚醒那些因該緩衝區忙而睡眠的進程，也喚醒
圖3-6 釋放緩衝區算法
因空閒表上沒有緩衝區而睡眠的那些進程。這兩類喚醒意味著被投入睡眠的那些進程現在可以使用釋放了的緩衝區了——雖然得到該緩衝區的第一個進程鎖上了它並且阻止其他進程得到它（見2.2節和2.4節）。內核把該緩衝區放到空閒表尾部，但是如果發生了一個I/O錯誤或者內核明確地在該緩衝區上標記上“舊”，則內核把該緩衝區放到空閒表頭部——本章的後面部分將看到這一點。現在，該緩衝區對於要索取它的所有進程都是空閒的。
正如當內核不再需要一個緩衝區時它引用算法brelse一樣，在處理一個磁盤中斷過程中，釋放用於往磁盤寫和從磁盤讀的異步I/O的緩衝區時，也要引用該算法。這將在3.4節看到。當操控空閒表時內核把處理機執行級提高以禁止磁盤中斷，從而防止了因嵌套調用brelse而引起的緩衝區指針的錯誤。如果當一個進程正在執行getblk時，一箇中斷處理程序引用brelse，則也會發生類似的壞結果。因此，在getblk中對全局有重要意義的地方也要提高處理機執行級。本章的練習詳細探討了這些情況。
在算法getblk中的第二種情況下，內核搜索應該包含該塊的那個散列隊列，但在那個散列隊列上找不到該塊。因為它不能“散列”在別處，所以該塊不可能在另一個散列隊列上，於是可以判定它不在高速緩衝中。因此，內核從空閒表中摘下第一個緩衝區。該緩衝區曾分配給另一個磁盤塊，並且也正在某個散列隊列上。如果該緩衝區沒有被標記上延遲寫（像隨後將要描述的那樣），則內核標記該緩衝區為忙，將它從當前所在的散列隊列中摘出，把該緩衝頭部的設備號和塊號重新指定為當前進程正在搜索的磁盤塊的設備號和塊號，並且把該緩衝區放到正確的散列隊列中。內核使用該緩衝區，但是並未記錄該緩衝區從前包含有另一個磁盤塊的數據。如果這時有一個進程搜索舊磁盤塊，則它在池中將找不到這個舊磁盤塊，它必須嚴格地按照前面所描述的那樣，從空閒表中為這個舊磁盤塊分配兩個新緩衝區。當內核結束對該緩衝區的使用時，它按如上所描述的那樣把該緩衝區釋放。例如，在圖3-7中，內核搜索第18塊但是在標有“blkno 2 mod 4”的散列隊列上沒有找到它，因此，內核從空閒表上摘下第一個緩衝區（第3塊），將它分配給第18塊，並把它放到適當的散列隊列中。
在算法getblk的第三種情況下，內核也必須從空閒表中分配一個緩衝區。然而，它發現從空閒表中摘下的緩衝區已被標記上“延遲寫”，因此，它必須在使用該緩衝區之前，將該緩衝區的內容寫到磁盤上。內核開始了一個往磁盤的異步寫，並且試圖從空閒表上分配另一個緩衝區。當異步寫完成時，內核把該緩衝區釋放，並把它放到空閒表頭部。在異步寫之前，該緩衝區已經從空閒表尾部出發遷移到了空閒表頭部。假使在異步寫之後，內核把該緩衝區放到空閒表尾部，則該緩衝區會做一次多餘的貫穿空閒表的移動，這就與最近最少使用算法相悖了。舉例來說，在圖3-8中，內核沒有找到第18塊，但是，當它試圖分配空閒表上的頭兩個緩衝區（每次一個）時，發現它們標記著延遲寫。內核把它們從空閒表中摘下，為這兩塊啟動往磁盤上寫的操作。內核分配空閒表上塊號為4的第三個緩衝區。它適當地重新對該緩衝區的設備號和塊號字段賦值，並且把該緩衝區——現在就是標記著第18塊的緩衝區放到它的新的散列隊列中。
圖3-7 緩衝區分配的第二種情況
圖3-8 緩衝區分配的第三種情況
第四種情況（圖 3-9）下，為進程A而動作著的內核沒有在它的散列隊列上找到該磁盤塊，因此，像第二種情況那樣，它試圖從空閒表上分配一個新的緩衝區。然而，在空閒表上已沒有緩衝區可供分配，因此，進程A去睡眠，直至另一進程執行算法brelse，釋放一個緩衝區。當內核調度到進程A時，它必須為該塊重新搜索散列隊列。它不能立即從空閒表中分配緩衝區，因為可能有多個進程正在等候空閒緩衝區，並且可能其中有一個進程已經把一個新的空閒緩衝區分配給進程A所尋找的目標磁盤塊了。因此，需要再次搜索該塊，保證僅僅一個緩衝區包含有該塊。圖3-10描繪了兩個進程間為一個空閒緩衝區而進行的競爭。
圖3-9 緩衝區分配的第四種情況
圖3-10 競爭緩衝區
最後一種情況（圖3-11）是複雜的，因為它牽涉幾個進程間的複雜關係。假設內核正在為進程A動作，搜索一個磁盤塊，並分配一個緩衝區，但是在釋放該緩衝區之前去睡眠了。舉例來說，如果進程A試圖讀一磁盤塊並且像第二種情況那樣分配了一個緩衝區，則當它等候從磁盤上的I/O傳輸完成時，它將去睡眠。當進程A睡眠時，假設內核調度到第二個進程B，B試圖存取那個緩衝區剛剛被進程A鎖上了的磁盤塊。進程B（進入第五種情況）將在散列隊列上找到那個上了鎖的塊。因為使用上著鎖的緩衝區是非法的，並且為一個磁盤塊分配第二個緩衝區也是非法的，所以進程B在緩衝區上打上“有需求”的標記，然後去睡眠，等候進程A釋放該緩衝區。
圖3-11 緩衝區分配的第五種情況
進程A將最終釋放該緩衝區並注意到該緩衝區有需求者。它喚醒在事件“緩衝區變為空閒”上睡眠的所有進程，其中包括進程B。當內核再次調度到進程B時，進程B必須證實該緩衝區是空閒的。另一進程C，可能一直等待同一個緩衝區；並且內核可能先於進程B而調度到C去運行；進程C可能已經去睡眠，而該緩衝區仍是上了鎖的。因此，進程B必須確認該塊真的是空閒的。
進程B也必須驗證該緩衝區是否包含著它原來請求的磁盤塊，因為可能會像第二種情況那樣，進程C已經把該緩衝區分配給另一塊了。當進程B執行時，它可能發現自己那時正等候著錯誤的緩衝區，因此必須再次搜索該磁盤塊；如果它自動地從空閒表中分配一個緩衝區，那麼將察覺不出另一個進程剛把一個緩衝區分配給該塊的可能性。
最後，進程B將找到它的塊，可能像第二種情況那樣從空閒表中分配一個新緩衝區。例如，在圖3-11中，一個正在搜索第99塊的進程在它的散列隊列上找到了它，但是該塊被標記為忙。該進程睡眠直至該塊變為空閒，並且隨後重新開始該算法。圖3-12描繪了對一個上了鎖的緩衝區進行的競爭。
正如在圖2-1中所看到的那樣，文件子系統中的高層內核算法引用管理高速緩衝的算法。當它們試圖檢索一個塊時，由高層算法決定它們想要存取的邏輯設備號和塊號。舉例來說，正如在第4章將要看到的那樣，如果一個進程想要從一個文件中讀數據，則內核需判定哪一個文件系統包含該文件，以及該文件系統中的哪一塊包含該數據。當要從一個特定的磁盤塊上讀數據時，內核檢查是否該塊在緩衝區池中。如果不在，則分配給它一個空閒緩衝區。當要把數據寫到一個特定磁盤塊上時，內核檢查是否該塊在緩衝區池中。如果不在，則為那個塊分配一個空閒緩衝區。讀、寫磁盤塊的算法使用算法getblk（圖3-4）來對池中的緩衝區進行分配。
圖3-4 緩衝區分配算法
本節描述在算法getblk中內核把一個緩衝區分配給磁盤塊時可能出現的五種典型情況。
（1）內核發現該塊在它的散列隊列中，並且它的緩衝區是空閒的。
（2）內核在散列隊列中找不到該塊，因此，它從空閒表中分配一個緩衝區。
（3）內核在散列隊列中找不到該塊，並且，在試圖從空閒表中分配一個緩衝區（像第二種情況那樣）的時候，在空閒表中找到一個已標上了“延遲寫”標記的緩衝區。內核必須把“延遲寫”緩衝區的內容寫到磁盤上，並分配另一個緩衝區。
（4）內核在散列隊列中找不到該塊，並且空閒緩衝區表已空。
（5）內核在散列隊列中找到該塊，但它的緩衝區當前為忙。現在，讓我們更詳細地討論每種情況。
當根據設備號和塊號的組合在緩衝池中搜索一個塊時，內核找到含有該塊的散列隊列。它沿著緩衝區鏈表搜索散列隊列，直到（在第一種情況中）它找到了其設備號和塊號與所要搜索的設備號和塊號相匹配的緩衝區。內核檢查該緩衝區是否空閒。如果是，則將該緩衝區標記上“忙”以使其他進程[2]不能存取它。然後內核從空閒表上摘下該緩衝區，因為一個緩衝區不能既處於忙狀態又位於空閒表中。正如所見到的那樣，如果當緩衝區忙時其他進程企圖存取該塊，則它們去睡眠，直至該緩衝區被釋放時為止。圖3-5描繪了第一種情況。在那兒，內核在標記有“blkno 0 mod 4”的隊列上搜索第4塊。找到該緩衝區後，內核把它從空閒表中摘下，而將第5塊和第28塊相鄰接並留在空閒表上。
圖3-5 緩衝區分配的第一種情況
在繼續談另外幾種情況之前，讓我們考慮在把一個緩衝區分配了之後對它會發生什麼。內核可以把數據從磁盤讀至緩衝區，並進而操控它，或把數據寫到緩衝區，並且可能進而寫到磁盤上。內核把標有“忙”的緩衝區留在那裡，當它忙時，沒有別的進程能存取它以及改變它的內容，因此可保持該緩衝區中的數據的完整性。當內核結束使用該緩衝區時，按照算法brelse（圖3-6）釋放該緩衝區。它喚醒那些因該緩衝區忙而睡眠的進程，也喚醒
圖3-6 釋放緩衝區算法
因空閒表上沒有緩衝區而睡眠的那些進程。這兩類喚醒意味著被投入睡眠的那些進程現在可以使用釋放了的緩衝區了——雖然得到該緩衝區的第一個進程鎖上了它並且阻止其他進程得到它（見2.2節和2.4節）。內核把該緩衝區放到空閒表尾部，但是如果發生了一個I/O錯誤或者內核明確地在該緩衝區上標記上“舊”，則內核把該緩衝區放到空閒表頭部——本章的後面部分將看到這一點。現在，該緩衝區對於要索取它的所有進程都是空閒的。
正如當內核不再需要一個緩衝區時它引用算法brelse一樣，在處理一個磁盤中斷過程中，釋放用於往磁盤寫和從磁盤讀的異步I/O的緩衝區時，也要引用該算法。這將在3.4節看到。當操控空閒表時內核把處理機執行級提高以禁止磁盤中斷，從而防止了因嵌套調用brelse而引起的緩衝區指針的錯誤。如果當一個進程正在執行getblk時，一箇中斷處理程序引用brelse，則也會發生類似的壞結果。因此，在getblk中對全局有重要意義的地方也要提高處理機執行級。本章的練習詳細探討了這些情況。
在算法getblk中的第二種情況下，內核搜索應該包含該塊的那個散列隊列，但在那個散列隊列上找不到該塊。因為它不能“散列”在別處，所以該塊不可能在另一個散列隊列上，於是可以判定它不在高速緩衝中。因此，內核從空閒表中摘下第一個緩衝區。該緩衝區曾分配給另一個磁盤塊，並且也正在某個散列隊列上。如果該緩衝區沒有被標記上延遲寫（像隨後將要描述的那樣），則內核標記該緩衝區為忙，將它從當前所在的散列隊列中摘出，把該緩衝頭部的設備號和塊號重新指定為當前進程正在搜索的磁盤塊的設備號和塊號，並且把該緩衝區放到正確的散列隊列中。內核使用該緩衝區，但是並未記錄該緩衝區從前包含有另一個磁盤塊的數據。如果這時有一個進程搜索舊磁盤塊，則它在池中將找不到這個舊磁盤塊，它必須嚴格地按照前面所描述的那樣，從空閒表中為這個舊磁盤塊分配兩個新緩衝區。當內核結束對該緩衝區的使用時，它按如上所描述的那樣把該緩衝區釋放。例如，在圖3-7中，內核搜索第18塊但是在標有“blkno 2 mod 4”的散列隊列上沒有找到它，因此，內核從空閒表上摘下第一個緩衝區（第3塊），將它分配給第18塊，並把它放到適當的散列隊列中。
在算法getblk的第三種情況下，內核也必須從空閒表中分配一個緩衝區。然而，它發現從空閒表中摘下的緩衝區已被標記上“延遲寫”，因此，它必須在使用該緩衝區之前，將該緩衝區的內容寫到磁盤上。內核開始了一個往磁盤的異步寫，並且試圖從空閒表上分配另一個緩衝區。當異步寫完成時，內核把該緩衝區釋放，並把它放到空閒表頭部。在異步寫之前，該緩衝區已經從空閒表尾部出發遷移到了空閒表頭部。假使在異步寫之後，內核把該緩衝區放到空閒表尾部，則該緩衝區會做一次多餘的貫穿空閒表的移動，這就與最近最少使用算法相悖了。舉例來說，在圖3-8中，內核沒有找到第18塊，但是，當它試圖分配空閒表上的頭兩個緩衝區（每次一個）時，發現它們標記著延遲寫。內核把它們從空閒表中摘下，為這兩塊啟動往磁盤上寫的操作。內核分配空閒表上塊號為4的第三個緩衝區。它適當地重新對該緩衝區的設備號和塊號字段賦值，並且把該緩衝區——現在就是標記著第18塊的緩衝區放到它的新的散列隊列中。
圖3-7 緩衝區分配的第二種情況
圖3-8 緩衝區分配的第三種情況
第四種情況（圖 3-9）下，為進程A而動作著的內核沒有在它的散列隊列上找到該磁盤塊，因此，像第二種情況那樣，它試圖從空閒表上分配一個新的緩衝區。然而，在空閒表上已沒有緩衝區可供分配，因此，進程A去睡眠，直至另一進程執行算法brelse，釋放一個緩衝區。當內核調度到進程A時，它必須為該塊重新搜索散列隊列。它不能立即從空閒表中分配緩衝區，因為可能有多個進程正在等候空閒緩衝區，並且可能其中有一個進程已經把一個新的空閒緩衝區分配給進程A所尋找的目標磁盤塊了。因此，需要再次搜索該塊，保證僅僅一個緩衝區包含有該塊。圖3-10描繪了兩個進程間為一個空閒緩衝區而進行的競爭。
圖3-9 緩衝區分配的第四種情況
圖3-10 競爭緩衝區
最後一種情況（圖3-11）是複雜的，因為它牽涉幾個進程間的複雜關係。假設內核正在為進程A動作，搜索一個磁盤塊，並分配一個緩衝區，但是在釋放該緩衝區之前去睡眠了。舉例來說，如果進程A試圖讀一磁盤塊並且像第二種情況那樣分配了一個緩衝區，則當它等候從磁盤上的I/O傳輸完成時，它將去睡眠。當進程A睡眠時，假設內核調度到第二個進程B，B試圖存取那個緩衝區剛剛被進程A鎖上了的磁盤塊。進程B（進入第五種情況）將在散列隊列上找到那個上了鎖的塊。因為使用上著鎖的緩衝區是非法的，並且為一個磁盤塊分配第二個緩衝區也是非法的，所以進程B在緩衝區上打上“有需求”的標記，然後去睡眠，等候進程A釋放該緩衝區。
圖3-11 緩衝區分配的第五種情況
進程A將最終釋放該緩衝區並注意到該緩衝區有需求者。它喚醒在事件“緩衝區變為空閒”上睡眠的所有進程，其中包括進程B。當內核再次調度到進程B時，進程B必須證實該緩衝區是空閒的。另一進程C，可能一直等待同一個緩衝區；並且內核可能先於進程B而調度到C去運行；進程C可能已經去睡眠，而該緩衝區仍是上了鎖的。因此，進程B必須確認該塊真的是空閒的。
進程B也必須驗證該緩衝區是否包含著它原來請求的磁盤塊，因為可能會像第二種情況那樣，進程C已經把該緩衝區分配給另一塊了。當進程B執行時，它可能發現自己那時正等候著錯誤的緩衝區，因此必須再次搜索該磁盤塊；如果它自動地從空閒表中分配一個緩衝區，那麼將察覺不出另一個進程剛把一個緩衝區分配給該塊的可能性。
最後，進程B將找到它的塊，可能像第二種情況那樣從空閒表中分配一個新緩衝區。例如，在圖3-11中，一個正在搜索第99塊的進程在它的散列隊列上找到了它，但是該塊被標記為忙。該進程睡眠直至該塊變為空閒，並且隨後重新開始該算法。圖3-12描繪了對一個上了鎖的緩衝區進行的競爭。
圖3-12 競爭一個上了鎖的緩衝區
緩衝區分配的算法必須是安全的：必須使進程不永遠睡眠，必須使它們最終能得到一個緩衝區。因為內核在系統調用執行期間分配緩衝區，並在返回之前釋放它們[3]，所以它保證等候緩衝區的所有進程都能醒來。在用戶態下的進程不直接控制內核緩衝區的分配，因此，它們不能故意地“霸佔”緩衝區。僅當內核等待著一個緩衝區與磁盤之間的I/O完成時，內核才失去對這個緩衝區的控制。可以想象，若一個磁盤驅動器是有問題的，造成它不能中斷CPU，這就使內核總是不能釋放該緩衝區。磁盤驅動程序必須對硬件發生這樣的情況進行監視，並返回一個錯誤給內核，說明磁盤工作不正常了。簡言之，內核能保證正在因一個緩衝區而睡眠的進程最終能被喚醒。
也可想象到這樣的情況是可能的：一個進程總也不能存取一個緩衝區。比如，在第四種情況下，如果幾個進程因等待一個緩衝區變為空閒而睡眠，內核不保證它們能按它們請求的次序獲得緩衝區。當一個緩衝區變為空閒時，一個進程可能繼續睡眠，也可能被喚醒，因為當其他進程首先獲得了對該緩衝區的控制權時，它只能再次去睡眠。從理論上說，這種情形可能會永遠繼續下去，但在實際上，由於系統中一般都配置了很多緩衝區，所以這是不成問題的。
本文摘自《UNIX操作系統設計》，雖然很老的一本書，但是堪稱經典。
正如在圖2-1中所看到的那樣，文件子系統中的高層內核算法引用管理高速緩衝的算法。當它們試圖檢索一個塊時，由高層算法決定它們想要存取的邏輯設備號和塊號。舉例來說，正如在第4章將要看到的那樣，如果一個進程想要從一個文件中讀數據，則內核需判定哪一個文件系統包含該文件，以及該文件系統中的哪一塊包含該數據。當要從一個特定的磁盤塊上讀數據時，內核檢查是否該塊在緩衝區池中。如果不在，則分配給它一個空閒緩衝區。當要把數據寫到一個特定磁盤塊上時，內核檢查是否該塊在緩衝區池中。如果不在，則為那個塊分配一個空閒緩衝區。讀、寫磁盤塊的算法使用算法getblk（圖3-4）來對池中的緩衝區進行分配。
圖3-4 緩衝區分配算法
本節描述在算法getblk中內核把一個緩衝區分配給磁盤塊時可能出現的五種典型情況。
（1）內核發現該塊在它的散列隊列中，並且它的緩衝區是空閒的。
（2）內核在散列隊列中找不到該塊，因此，它從空閒表中分配一個緩衝區。
（3）內核在散列隊列中找不到該塊，並且，在試圖從空閒表中分配一個緩衝區（像第二種情況那樣）的時候，在空閒表中找到一個已標上了“延遲寫”標記的緩衝區。內核必須把“延遲寫”緩衝區的內容寫到磁盤上，並分配另一個緩衝區。
（4）內核在散列隊列中找不到該塊，並且空閒緩衝區表已空。
（5）內核在散列隊列中找到該塊，但它的緩衝區當前為忙。現在，讓我們更詳細地討論每種情況。
當根據設備號和塊號的組合在緩衝池中搜索一個塊時，內核找到含有該塊的散列隊列。它沿著緩衝區鏈表搜索散列隊列，直到（在第一種情況中）它找到了其設備號和塊號與所要搜索的設備號和塊號相匹配的緩衝區。內核檢查該緩衝區是否空閒。如果是，則將該緩衝區標記上“忙”以使其他進程[2]不能存取它。然後內核從空閒表上摘下該緩衝區，因為一個緩衝區不能既處於忙狀態又位於空閒表中。正如所見到的那樣，如果當緩衝區忙時其他進程企圖存取該塊，則它們去睡眠，直至該緩衝區被釋放時為止。圖3-5描繪了第一種情況。在那兒，內核在標記有“blkno 0 mod 4”的隊列上搜索第4塊。找到該緩衝區後，內核把它從空閒表中摘下，而將第5塊和第28塊相鄰接並留在空閒表上。
圖3-5 緩衝區分配的第一種情況
在繼續談另外幾種情況之前，讓我們考慮在把一個緩衝區分配了之後對它會發生什麼。內核可以把數據從磁盤讀至緩衝區，並進而操控它，或把數據寫到緩衝區，並且可能進而寫到磁盤上。內核把標有“忙”的緩衝區留在那裡，當它忙時，沒有別的進程能存取它以及改變它的內容，因此可保持該緩衝區中的數據的完整性。當內核結束使用該緩衝區時，按照算法brelse（圖3-6）釋放該緩衝區。它喚醒那些因該緩衝區忙而睡眠的進程，也喚醒
圖3-6 釋放緩衝區算法
因空閒表上沒有緩衝區而睡眠的那些進程。這兩類喚醒意味著被投入睡眠的那些進程現在可以使用釋放了的緩衝區了——雖然得到該緩衝區的第一個進程鎖上了它並且阻止其他進程得到它（見2.2節和2.4節）。內核把該緩衝區放到空閒表尾部，但是如果發生了一個I/O錯誤或者內核明確地在該緩衝區上標記上“舊”，則內核把該緩衝區放到空閒表頭部——本章的後面部分將看到這一點。現在，該緩衝區對於要索取它的所有進程都是空閒的。
正如當內核不再需要一個緩衝區時它引用算法brelse一樣，在處理一個磁盤中斷過程中，釋放用於往磁盤寫和從磁盤讀的異步I/O的緩衝區時，也要引用該算法。這將在3.4節看到。當操控空閒表時內核把處理機執行級提高以禁止磁盤中斷，從而防止了因嵌套調用brelse而引起的緩衝區指針的錯誤。如果當一個進程正在執行getblk時，一箇中斷處理程序引用brelse，則也會發生類似的壞結果。因此，在getblk中對全局有重要意義的地方也要提高處理機執行級。本章的練習詳細探討了這些情況。
在算法getblk中的第二種情況下，內核搜索應該包含該塊的那個散列隊列，但在那個散列隊列上找不到該塊。因為它不能“散列”在別處，所以該塊不可能在另一個散列隊列上，於是可以判定它不在高速緩衝中。因此，內核從空閒表中摘下第一個緩衝區。該緩衝區曾分配給另一個磁盤塊，並且也正在某個散列隊列上。如果該緩衝區沒有被標記上延遲寫（像隨後將要描述的那樣），則內核標記該緩衝區為忙，將它從當前所在的散列隊列中摘出，把該緩衝頭部的設備號和塊號重新指定為當前進程正在搜索的磁盤塊的設備號和塊號，並且把該緩衝區放到正確的散列隊列中。內核使用該緩衝區，但是並未記錄該緩衝區從前包含有另一個磁盤塊的數據。如果這時有一個進程搜索舊磁盤塊，則它在池中將找不到這個舊磁盤塊，它必須嚴格地按照前面所描述的那樣，從空閒表中為這個舊磁盤塊分配兩個新緩衝區。當內核結束對該緩衝區的使用時，它按如上所描述的那樣把該緩衝區釋放。例如，在圖3-7中，內核搜索第18塊但是在標有“blkno 2 mod 4”的散列隊列上沒有找到它，因此，內核從空閒表上摘下第一個緩衝區（第3塊），將它分配給第18塊，並把它放到適當的散列隊列中。
在算法getblk的第三種情況下，內核也必須從空閒表中分配一個緩衝區。然而，它發現從空閒表中摘下的緩衝區已被標記上“延遲寫”，因此，它必須在使用該緩衝區之前，將該緩衝區的內容寫到磁盤上。內核開始了一個往磁盤的異步寫，並且試圖從空閒表上分配另一個緩衝區。當異步寫完成時，內核把該緩衝區釋放，並把它放到空閒表頭部。在異步寫之前，該緩衝區已經從空閒表尾部出發遷移到了空閒表頭部。假使在異步寫之後，內核把該緩衝區放到空閒表尾部，則該緩衝區會做一次多餘的貫穿空閒表的移動，這就與最近最少使用算法相悖了。舉例來說，在圖3-8中，內核沒有找到第18塊，但是，當它試圖分配空閒表上的頭兩個緩衝區（每次一個）時，發現它們標記著延遲寫。內核把它們從空閒表中摘下，為這兩塊啟動往磁盤上寫的操作。內核分配空閒表上塊號為4的第三個緩衝區。它適當地重新對該緩衝區的設備號和塊號字段賦值，並且把該緩衝區——現在就是標記著第18塊的緩衝區放到它的新的散列隊列中。
圖3-7 緩衝區分配的第二種情況
圖3-8 緩衝區分配的第三種情況
第四種情況（圖 3-9）下，為進程A而動作著的內核沒有在它的散列隊列上找到該磁盤塊，因此，像第二種情況那樣，它試圖從空閒表上分配一個新的緩衝區。然而，在空閒表上已沒有緩衝區可供分配，因此，進程A去睡眠，直至另一進程執行算法brelse，釋放一個緩衝區。當內核調度到進程A時，它必須為該塊重新搜索散列隊列。它不能立即從空閒表中分配緩衝區，因為可能有多個進程正在等候空閒緩衝區，並且可能其中有一個進程已經把一個新的空閒緩衝區分配給進程A所尋找的目標磁盤塊了。因此，需要再次搜索該塊，保證僅僅一個緩衝區包含有該塊。圖3-10描繪了兩個進程間為一個空閒緩衝區而進行的競爭。
圖3-9 緩衝區分配的第四種情況
圖3-10 競爭緩衝區
最後一種情況（圖3-11）是複雜的，因為它牽涉幾個進程間的複雜關係。假設內核正在為進程A動作，搜索一個磁盤塊，並分配一個緩衝區，但是在釋放該緩衝區之前去睡眠了。舉例來說，如果進程A試圖讀一磁盤塊並且像第二種情況那樣分配了一個緩衝區，則當它等候從磁盤上的I/O傳輸完成時，它將去睡眠。當進程A睡眠時，假設內核調度到第二個進程B，B試圖存取那個緩衝區剛剛被進程A鎖上了的磁盤塊。進程B（進入第五種情況）將在散列隊列上找到那個上了鎖的塊。因為使用上著鎖的緩衝區是非法的，並且為一個磁盤塊分配第二個緩衝區也是非法的，所以進程B在緩衝區上打上“有需求”的標記，然後去睡眠，等候進程A釋放該緩衝區。
圖3-11 緩衝區分配的第五種情況
進程A將最終釋放該緩衝區並注意到該緩衝區有需求者。它喚醒在事件“緩衝區變為空閒”上睡眠的所有進程，其中包括進程B。當內核再次調度到進程B時，進程B必須證實該緩衝區是空閒的。另一進程C，可能一直等待同一個緩衝區；並且內核可能先於進程B而調度到C去運行；進程C可能已經去睡眠，而該緩衝區仍是上了鎖的。因此，進程B必須確認該塊真的是空閒的。
進程B也必須驗證該緩衝區是否包含著它原來請求的磁盤塊，因為可能會像第二種情況那樣，進程C已經把該緩衝區分配給另一塊了。當進程B執行時，它可能發現自己那時正等候著錯誤的緩衝區，因此必須再次搜索該磁盤塊；如果它自動地從空閒表中分配一個緩衝區，那麼將察覺不出另一個進程剛把一個緩衝區分配給該塊的可能性。
最後，進程B將找到它的塊，可能像第二種情況那樣從空閒表中分配一個新緩衝區。例如，在圖3-11中，一個正在搜索第99塊的進程在它的散列隊列上找到了它，但是該塊被標記為忙。該進程睡眠直至該塊變為空閒，並且隨後重新開始該算法。圖3-12描繪了對一個上了鎖的緩衝區進行的競爭。
圖3-12 競爭一個上了鎖的緩衝區
緩衝區分配的算法必須是安全的：必須使進程不永遠睡眠，必須使它們最終能得到一個緩衝區。因為內核在系統調用執行期間分配緩衝區，並在返回之前釋放它們[3]，所以它保證等候緩衝區的所有進程都能醒來。在用戶態下的進程不直接控制內核緩衝區的分配，因此，它們不能故意地“霸佔”緩衝區。僅當內核等待著一個緩衝區與磁盤之間的I/O完成時，內核才失去對這個緩衝區的控制。可以想象，若一個磁盤驅動器是有問題的，造成它不能中斷CPU，這就使內核總是不能釋放該緩衝區。磁盤驅動程序必須對硬件發生這樣的情況進行監視，並返回一個錯誤給內核，說明磁盤工作不正常了。簡言之，內核能保證正在因一個緩衝區而睡眠的進程最終能被喚醒。
也可想象到這樣的情況是可能的：一個進程總也不能存取一個緩衝區。比如，在第四種情況下，如果幾個進程因等待一個緩衝區變為空閒而睡眠，內核不保證它們能按它們請求的次序獲得緩衝區。當一個緩衝區變為空閒時，一個進程可能繼續睡眠，也可能被喚醒，因為當其他進程首先獲得了對該緩衝區的控制權時，它只能再次去睡眠。從理論上說，這種情形可能會永遠繼續下去，但在實際上，由於系統中一般都配置了很多緩衝區，所以這是不成問題的。
本文摘自《UNIX操作系統設計》，雖然很老的一本書，但是堪稱經典。
UNIX操作系統設計
- Linux之父Linux Torvalds曾捧讀的經典著作
- UNIX操作系統經典著作，暢銷多年
- 深度剖析UNIX操作系統內核的內部數據結構、算法和UNIX系統的問題
本書以UNIX系統為背景，全面、系統地介紹了UNIX操作系統內核的內部數據結構和算法。本書首先對系統內核結構做了簡要介紹，然後分章節描述了文件系統、進程調度和存儲管理，並在此基礎上討論了UNIX系統的問題，如驅動程序接口、進程間通信與網絡等。在每章之後，還給出了大量富有啟發性和實際意義的題目。
目錄結構
- 第 1章 系統概貌
- 第 2章 內核導言
- 第3章 數據緩衝區高速緩衝
- 第4章 文件的內部表示
- 第5章 文件系統的系統調用
- 第6章 進程結構
- 第7章 進程控制
- 第8章 進程調度和時間
- 第9章 存儲管理策略
- 第 10章 輸入 輸出子系統
- 第 11章 進程間通信
- 第 12章 多處理機系統
- 第 13章 分佈式UNIX系統
- 附錄A 系統調用
- 索引
- 參考文獻