XV6學習（10）鎖

• 2021 年 2 月 5 日
• 筆記
• os, xv6, 作業系統

在包括XV6的絕大部分作業系統都是多個任務交錯執行的。交錯的一個原因是多核硬體：多核電腦的多個CPU核心獨立執行計算，如XV6的RISC-V處理器。多個CPU核心共享物理記憶體，XV6利用這種共享來維護所有核心都會讀寫的數據結構。而這種共享會導致一個CPU在讀取某數據結構時，可能有另一個CPU正在對此數據進行更新；或者多個CPU同時更新同一個數據。如果不對這種並行訪問進行小心的設計，就可能會導致錯誤的結果產生或者損壞數據。即使是單核處理器，內核也可能會在多個執行緒之間進行切換，導致它們交錯運行。最後，如果中斷在錯誤的時間發生，設備中斷處理程式也可能會對數據造成損壞。並發一詞就是指由於多核並行、執行緒切換或中斷，導致多個指令流交錯執行。

內核中充滿了被並發訪問的數據。如兩個CPU可以同時調用kalloc，從而同時從空閑鏈表的中彈出空閑頁。內核設計者必須允許大量並發，因為並發可以提高系統的性能和響應速度。然而，系統設計者需要耗費很多精力來保證並發的正確性。有很多種方法可以寫出正確的程式碼，其中有一些比其他更容易推理。針對並發的正確性以及支援它們的抽象的策略被稱為並發控制技術。

XV6基於不用的情況使用了多種並發控制技術，並且還有更多技術可以使用。其中一個廣泛使用的技術就是鎖。鎖可以提供互斥性，保證同一時間只有一個CPU能夠持有鎖。如果程式設計師將共享數據與鎖進行關聯，在程式碼使用這些數據時就必須持有相應的鎖，這樣就可以保證同一時間只有一個CPU能使用該數據。儘管鎖是一種容易理解的並發控制機制，但鎖的缺點是其會降低性能，因為鎖將並發操作串列化。

競爭條件

假如兩個進程在不同的CPU上同時調用wait函數釋放子進程記憶體，導致在每個CPU上，內核都會調用kfree來釋放子進程的頁面。內核維護了一個空閑頁面鏈表，kalloc會pop一個頁面，而kfree會push一個頁面。為了最佳的性能，我們希望兩個父進程的kfree能夠並行執行而不需要等待另一個，但是在XV6的kfree實現中是不正確的。

一種競爭條件是指一個記憶體位置被並發訪問，並且至少一個訪問是寫入。競爭通常是bug的訊號，要麼更新發生丟失，要麼讀取到不完整的數據更新。競爭的結果取決於兩個CPU執行的實際時間以及對記憶體的操作如何被記憶體系統排序，這些會使得競爭導致的bug難以復現和調試。例如插入print語句來調試可能會改變執行的時間從而使得競爭消失。

struct element *list = 0;
struct lock listlock;

void
push(int data)
{
  struct element *l;
  l = malloc(sizeof *l);
  l->data = data;
  acquire(&listlock);
  l->next = list;
  list = l;
  release(&listlock);
}

當我們說鎖保護了數據，實際的意思是鎖保護了應用在數據上的一系列不變性。一個操作的正確性取決於操作開始時的不變性是否正確。操作可能會暫時違反不變性，但必須在在操作結束前恢復其不變性。例如對於鏈表，不變性時指頭指針指向第一個元素，且每一個元素的next域指向下一個元素。push操作的l->next = list會暫時破壞其不變性，使得頭指針並不是指向第一個元素。競爭條件發生因為在另一個CPU上的操作依賴於不變性，而這被暫時破壞了。鎖的使用可以保證在數據結構上一次只有一個CPU在臨界區執行，因此不會有CPU在不變性被破壞時執行操作。

可以認為鎖將並發的臨界區串列化使其一次只能執行一個，從而保護了不變性。也可以認為被鎖保護的臨界區對於其他臨界區來說是原子性的，因此每一個都只能看見一系列先前臨界區的完整修改，而永遠不會看見部分修改。

儘管鎖的正確使用可以使錯誤程式碼變正確，但鎖也限制了性能。例如當兩個進程同時調用kfree，鎖會將兩個調用串列化，將它們在不同的CPU上運行就不會獲得收益。在內核設計中一個大的挑戰就是避免鎖爭用。XV6在這方面做的很少，但是複雜的內核會通過特殊的方法組織數據結構和演算法來避免鎖爭用。例如內核會為每個內核維護一個獨立的空閑記憶體鏈表，只有噹噹前CPU的鏈表為空時才會去請求其他CPU的鏈表來獲取空閑記憶體。而其他的爭用可能需要更加複雜的設計。

鎖的位置同樣對性能影響很大。例如在push中可以將acquire放在更加前面，但這就會降低性能，因為malloc的調用也被串列化。

程式碼：鎖

XV6中有兩種鎖：自旋鎖和睡眠鎖。自旋鎖定義為struct spinlock，最重要的域就是locked，1代表被持有而0代表未被持有。理論上xv6可以通過下列程式碼來上鎖：

void
acquire(struct spinlock *lk) // does not work!
{
  for(;;) {
    if(lk->locked == 0) {
      lk->locked = 1;
      break;
    }
  }
}

然而不幸地是在多處理器上這種實現不會達到互斥。當兩個CPU同時對locked進行讀取並且結果為0時，它們都會獲得這個鎖，而這就會違反互斥的性質。因此我們需要第5第6行的執行原子化。

由於鎖的廣泛使用，多核處理器通常會提供該原子指令。在RISC-V中為amoswap r, a，該指令會交換r和a的值。該指令是原子性的，其會通過特殊硬體來防止其他CPU在讀寫時使用該記憶體地址。

XV6的acquire使用可移植的C庫函數__sync_lock_test_and_set，而其在底層是使用amoswap實現的。函數返回值是locked的舊值。acquire函數在循環中不停（自旋）調用swap直到其獲得鎖。每次循環將1swap到locked中，並判斷舊值是否為0，為0就說明獲取到了鎖，同時swap也將locked設置為了1。如果舊值為1，說明其他CPU持有鎖，而swap也並沒有改變locked的值。

當獲取到了鎖，acquire就會為了調試而記錄獲取鎖的CPU。lk->cpu域是被鎖保護的並且必須在獲取鎖後才能被改變。

release函數則與acquire相反；該函數清空cpu域並釋放鎖。理論上釋放只需要將locked域置0。而C語言標準運行編譯器使用多存儲指令來實現賦值，因此一條賦值語句可能不是原子的。因此，release使用C庫函數__sync_lock_release來進行原子性賦值。該函數底層也是通過amoswap指令實現。

程式碼：使用鎖

XV6在許多地方都使用鎖來避免競爭條件。kalloc和kfree是一個很好的例子。使用鎖的一個難點是決定要使用多少鎖以及每個鎖要保護哪些數據和不變性。這裡有幾個基本原則：首先當一個變數在被一個CPU寫入時，有其他CPU可以對其讀寫時，應該使用鎖來避免兩個操作重疊；第二，記住鎖所保護的不變性，如果一個不變性涉及多個記憶體位置，則所有的位置都需要被一個單獨的鎖來保護，從而保證不變性。

上述只說了鎖什麼時候是必要的而沒有鎖什麼時候是不必須的，而減少鎖的數量對效率來說是很重要的，因為鎖減少了並行。如果並行不是必須的，那麼可以只使用一個執行緒從而不必考慮鎖的問題。簡單內核可以在多處理器上只使用一個鎖，當進入內核態時獲取鎖，離開時釋放鎖（儘管系統調用如管道的讀和wait將會產生問題）。很多單處理器系統使用這種方法來在多處理器上運行，有的時候被成為「大內核鎖」。但是，這種方法破壞了並行性：一次只有一個CPU可以在內核中執行。如果內核要進行任何重計算任務，使用一系列的鎖會更加高效，內核可以同時在多個CPU上運行。

作為粗粒度鎖的例子，XV6的kalloc.c分配器只有一個被一個鎖保護的空閑鏈表。如果多個進程在不同CPU上同時嘗試申請頁面，那麼每一個都需要在acquire中自旋等待。自旋是在做無用功從而降低了性能。如果鎖的爭用浪費了大量時間，那麼可能就要通過改變分配器的設計來提高性能，使用多個空閑鏈表，每個鏈表單獨持有鎖，從而允許真正的並行分配。

作為細粒度鎖的例子，XV6對於每個文件都有一個單獨的鎖，因此操作不同文件的進程可以無需等待其他的文件的鎖。文件鎖模式的粒度可以變得更加的細，如果希望進程同時寫相同文件的不同區域。總而言之，鎖的粒度需要由性能度量以及鎖的複雜性的考慮來決定。

XV6中使用的鎖如下表所示：

死鎖和鎖順序

如果程式碼在內核中需要同時持有多個鎖，那麼有一點很重要，就是獲取鎖的順序要相同。如果順序不同，那麼就會有死鎖的風險。假設XV6中兩個程式碼路徑要獲取鎖A和B，但是路徑1先獲取A再獲取B，而另一條路徑先獲取B再獲取A。假設執行緒T1執行程式碼路徑1並獲取了鎖A，而執行緒T2執行路徑2並獲取了鎖B。那麼接下來T1會嘗試獲取獲取鎖B而T2會嘗試獲取鎖A。兩個獲取就肯定都會被阻塞，因為另一個執行緒持有需要的鎖，並且不會釋放直到它的acquire返回。為了避免這種死鎖，所有程式碼路徑必須以同樣的順序獲取鎖。對全局鎖獲取順序的需要意味著鎖實際上是每個函數規範的一部分：調用者必須以某種方式調用函數，使鎖按約定的順序被獲取。

XV6有很多長度為2的涉及每個進程的鎖的鎖順序鏈，因為在路徑上sleep函數會工作。例如consoleintr是處理輸入字元的中斷程式。當一個新行到達，任何等待控制台輸入的進程就會被喚醒。當調用wakeup時consoleintr持有cons.lock，而wakeup又會獲取等待進程的鎖來喚醒它。因此，避免全局死鎖的鎖順序包含cons.lock鎖必須在每個進程鎖之前被獲取的規則。文件系統程式碼包含XV6的最長的鎖鏈。例如創建文件需要同時獲取目錄上的鎖，新文件的inode的鎖，磁碟塊緩衝區的鎖，磁碟驅動的vdisk_lock以及調用進程的鎖。為了避免死鎖，文件系統程式碼通常要求以一定順序來獲取鎖。

遵守避免全局死鎖的順序可能會十分困難。有時候鎖順序會與程式結構的邏輯衝突，如模組M1調用模組M2，但是鎖順序要求M2的鎖在M1之前獲取。有時候也無法預知需要的鎖，可能獲取一個鎖之後才能直到下一個鎖是什麼。這種情況出現於在文件系統中根據路徑名連續查找模組以及wait和exit函數在進程表中查找子進程中。最後，死鎖的危險通常會限制鎖策略能夠使用多細粒度的鎖，越多的鎖就意味著越多死鎖的可能性。在內核實現中，避免死鎖通常是很重要的一部分。

鎖和中斷處理程式

XV6中有一些自旋鎖保護了會同時被執行緒和中斷處理程式使用的數據。例如clockintr定時器中斷處理程式可能會增加ticks當一個內核執行緒同時在sys_sleep函數中讀取ticks。tickslock鎖會將兩個訪問串列化。

自旋鎖和中斷的交互會帶來潛在的風險。假設sys_sleep持有鎖，並且CPU產生了一個定時器中斷。clockintr將會嘗試申請鎖，發現鎖被持有，於是等待其被釋放。在這種情況下，鎖將永遠不會被釋放：只有sys_sleep會釋放鎖，但是sys_sleep不會釋放鎖直到clockintr返回。因此CPU會進入死鎖狀態，並且其他需要該鎖的程式碼都會被凍結。

為了避免這種情況，如果一個自旋鎖在中斷處理程式中被使用，CPU必須在中斷允許時不會持有該鎖。XV6更加保守：當CPU申請任何鎖時，XV6總是會在該CPU上關閉中斷。中斷可能仍在其他CPU上發生，因此中斷的acquire可以等待一個執行緒釋放自旋鎖，只要不在同一個CPU上。

XV6會重新允許中斷當一個CPU不再持有自旋鎖，必須通過一些小的記錄來處理嵌套臨界區。acquire調用push_off而release調用pop_off來追蹤當前CPU的嵌套的層次。當計數器為0時，pop_off恢復最外層臨界區開始前的中斷允許狀態。intr_off和intr_on函數分別執行RISC-V的關和開中斷指令。

在acquire設置lk->locked之前調用push_off是非常重要的。如果兩者順序交換，就會有一個小窗口，此時鎖被獲取而中斷是允許的，如果不幸此時發生了中斷，就可能會使系統死鎖。相同的，release釋放鎖之後再調用pop_off也是很重要的。

指令和記憶體順序

自然地會認為程式以源程式碼語句出現的順序來執行程式。但在很多編譯器和CPU中，程式碼是亂序執行的從而來獲得更高的性能。如果一條指令需要很多個周期來完成，CPU可能會更早地發射指令，使其與其他指令重疊，從而避免CPU停頓。例如CPU可能注意到一串指令序列A和B不依賴彼此，CPU就可能會先執行指令B，因為其輸入比A的輸入更早就緒或者為了將A和B的執行重疊起來。編譯器也可能會進行類似的重排，通過先於源程式碼中之前的語句的指令發射一條語句的指令。

編譯器和CPU允許通過不會改變一串程式碼執行結果的規則來重排語句。然而，這些允許重排的規則會改變並發程式碼的結果，並且很容易在多處理器上導致錯誤的行為。CPU的排序規則被成為記憶體模型。

例如push的程式碼，如果CPU將第4行對應的store指令移動到release之後就會引起災難：

l = malloc(sizeof *l);
l->data = data;
acquire(&listlock);
l->next = list;
list = l;
release(&listlock);

如果這種重排發生了，這裡就會有一個窗口使得其他CPU可以獲取鎖並且更新list，但是看見的並不是初始的list->next。

為了告訴硬體和編譯器不要進行這種重拍，XV6在acquire和release中使用__sync_synchronize()。__sync_synchronize()是一個記憶體屏障：它告訴編譯器和CPU不要越過屏障重排load和store指令。XV6acquire和release的屏障在幾乎所有會出現問題的情況下強制保持順序，後面的章節會討論一些例外。

睡眠鎖

有時候XV6需要長時間持有一個鎖。例如文件系統在磁碟上讀寫文件內容時持有一個文件鎖，而這些磁碟操作會耗費數十毫秒。當其他進程要獲取鎖時，長時間持有自旋鎖會引起很大的浪費，因為申請的進程會長時間浪費CPU在自旋上。自旋鎖的另一個缺點就是當其保持自旋鎖時進程不會讓出CPU，我們希望當持有鎖的進程在等待磁碟時其他進程能使用CPU。當持有自旋鎖時讓出CPU是非法的，因為如果第二個執行緒嘗試獲取自旋鎖時，這可能會導致死鎖；因為acquire不會讓出CPU，第二個進程的自旋可能會阻止第一個執行緒運行和釋放鎖。當持有鎖時讓出CPU同樣違反了當自旋鎖被持有時中斷必須關閉的需求。因此我們需要一種當acquire等待時能讓出CPU以及允許持有鎖時讓出（和中斷）的鎖。

XV6提供了睡眠鎖這種鎖、acquiresleep使用下一章講到的技術使其在等待時會讓出CPU。在高層來看，睡眠鎖有一個被自旋鎖保護的locked域，而acquiresleep調用sleep會原子地讓出CPU並釋放自旋鎖。這使得其他執行緒可以在acquiresleep等待時執行。

因為睡眠鎖使中斷允許，因此它們不能被用在中斷處理程式中。因為acquiresleep會讓出CPU，睡眠鎖不能在自旋鎖保護的臨界區內使用（儘管自旋鎖可以在睡眠鎖保護的臨界區內使用）。

自旋鎖最好在短臨界區使用，因為等待它們會浪費CPU時間；睡眠鎖在長時間操作上表現更好。

真實作業系統

儘管並發原語和並行被研究了很多年，鎖編程仍然是十分有挑戰性的。最好是將鎖隱藏在更高級的結構如同步隊列中，儘管XV6沒有這樣做。如果你使用鎖來編程，最好使用工具來標識臨界區，因為很容易忽略需要獲得鎖的不變性。

大部分作業系統支援POSIX threads（pthreads），這允許用戶在不同CPU上並發運行多個執行緒。Pthreads支援用戶級別鎖和屏障等。Pthread的支援需要得到作業系統的支援。例如當一個pthread在系統調用中阻塞時，同一個進程的其他pthread應該能夠在這個CPU上運行。另一個例子是當一個pthread改變了進程的地址空間（如記憶體映射），內核應該安排其他運行相同進程的執行緒的CPU更新頁表硬體來映射地址空間上的修改。

是有可能不使用原子指令來實現鎖的，但是其代價非常高昂，並且大部分作業系統都是使用原子指令。

如果很多CPU嘗試同時獲取一個鎖時，鎖的代價是非常高昂的。如果一個CPU在本地cache中快取了一個鎖，其他CPU必須獲取這個鎖，之後原子指令會更新cache行，持有鎖必須將cache行從一個CPU的cache複製到其他CPU的cache，並且可能需要使cache行的其他所有內容失效。從另一個CPU的cache中獲取cache行的代價可能比從本地cache中獲取行要高几個數量級。

為了避免鎖相關的高昂代價，許多作業系統使用無鎖數據結構和演算法。如上文中提到的多個空閑記憶體鏈表。然而無鎖編程比鎖編程要更加複雜；例如必須考慮指令和記憶體重排。鎖編程已經很困難了，因此XV6避免了無鎖編程帶來的額外複雜性。