用Rust寫作業系統（四）——競爭條件與死鎖
一、概要說明
當多個任務訪問同一個資源（資料）是就會引發競爭條件問題，這不僅在程序間會出現，在作業系統和程序間也會出現。由競爭條件引發的問題很難復現和除錯，這也是其最困難的地方。本實驗的目的在於瞭解競爭條件和死鎖現象，並掌握處理這些問題的初步方法等。
二、實驗原理
1。 死鎖的出現與簡單處理表1展示了我們系統（當前狀態）如果在_start函式和中斷處理函式中都呼叫列印宏（println！）可能出現死鎖的情況。_start函式與中斷處理函式（interrupt_handler）之間因為競爭資源而可能出現死鎖。這是因為_start函式佔有WRITE 鎖且請求在CPU上執行，而中斷處理函式佔有CPU請求WRITE鎖，構成死鎖。
為了防止出現死鎖，一個簡單的辦法是在使用鎖時禁止中斷。但需要注意的是禁用中斷會增加中斷響應延遲，而中斷響應延遲一個非常重要的效能指標。所以只能在短時間內禁用中斷。
2。 競爭條件所謂競爭條件是指多程序併發訪問（操作）同一個資料時執行的結果依賴於程序之間執行的順序。參見教材第6章（第7版）
三、硬體中斷
1。 死鎖
現在核心中存在一種併發的情形：定時器中斷是非同步發生的，因此它們可以隨時中斷我們的_start函式。幸運的是，Rust的所有權系統可以在編譯時防止許多種型別的與併發相關的錯誤。但死鎖是一個值得注意的例外。如果一個執行緒試圖獲取一個永遠不會釋放的鎖，就會發生死鎖。這樣，執行緒將會無限期地處於掛起狀態。
• 當前我們的核心中已經可以引發死鎖。請注意，我們的println宏呼叫vga_buffer：：_print 函式，它使用自旋鎖來鎖定一個全域性的WRITER類。
它鎖定WRITER，呼叫write_fmt，並在函式的末尾隱式地解鎖。現在，我們設想一下，如果在WRITER被鎖定時觸發一箇中斷，同時相應的中斷處理程式也試圖列印一些東西。
由於WRITER已經被鎖定，所以中斷處理程式將會一直等待，直到它被釋放。但這種情況永遠不會發生，因為_start函式只有在中斷處理程式返回後才繼續執行。因此，整個系統就會掛起。
1） 引發死鎖
• 透過在 _start 函式末尾的迴圈中列印一些內容，我們很容易在核心中引發這樣的死鎖。
• 當我們在 QEMU 中執行它時，得到的輸出如下。
只有有限數量的連字元‘-’ 被列印，直到第一次定時器中斷髮生。接著系統掛起，因為定時器中斷處理程式試圖列印點時引發了死鎖。這就是為什麼我們在上面的輸出中看不到任何點的原因。
由於定時器中斷是非同步發生的，因此連字元的實際數量在兩次執行之間會有所不同。這種不確定性使得與併發相關的錯誤很難除錯。
2） 修復死鎖
• 為了避免這種死鎖，我們可以採取這樣的方案：只要互斥鎖Mutex是鎖定的，就可以禁用中斷。
without_interrupts 函式接受一個閉包（closure），並在無中斷的環境中執行。我們使用它來確保只要Mutex處於鎖定狀態，就不會發生中斷。現在執行核心，就可以看到它一直執行而不會掛起。（我們仍然無法看到任何點，但這是因為他們滾動過快。嘗試減慢列印速度，例如在迴圈中加上for_in 0。。10000{}）。
• 我們可以對序列列印函式進行相同的更改，以確保它不會發生死鎖。
值得注意的是，禁用中斷不應該成為一種通用的解決方案。這一方案的弊端是，它會延長最壞情況下的中斷等待時間，也就是系統對中斷做出反應之前的時間。因此，應該只在非常短的時間內禁用中斷。
2。 修復競爭條件
• 如果你執行cargo xtest，可能會看到test_println_output測試失敗。
• 這是由測試和定時器處理程式之間的競爭條件導致的。測試程式是這樣的。
測試將一個字串列印到VGA緩衝區，然後透過在緩衝區字元陣列buffer_chars上手動迭代來檢查輸出。出現競爭條件是因為定時器中斷處理程式可能在println和讀取螢幕字元之間執行。注意，這不是危險的資料競爭，Rust在編譯時完全避免了這種競爭。
• 要解決這個問題，我們需要在測試的整個持續時間內保持對WRITER的鎖定狀態，這樣定時器處理程式就不能在操作之間將。寫入螢幕。修復後的測試看起來像這樣。
我們做了下述改動：
• 顯式地使用lock（）方法來保證writer在整個測試期間都處於鎖定狀態。使用writeln宏替代println，這將會允許列印字元到已鎖定的writer中。
• 為避免再次出現死鎖，我們在測試期間禁用中斷。否則，在writer仍然處於鎖定狀態時，測試可能會中斷。
• 由於計時器中斷處理程式仍然可以在測試之前執行，因此我們在列印字串s之前再列印一個換行符‘\n’。這樣可以避免因計時器處理程式已經將一些‘。’字元列印到當前行而引起的測試失敗。
經過修改後，cargo xtest現在確實又成功了。
這是一個相對無害的競爭條件，它只會導致測試失敗。可以想象，由於其他競爭條件的不確定性，它們的除錯可能更加困難。幸運的是，Rust防止了資料競爭的出現，這是最嚴重的競爭條件，因為它們可以導致各種各樣的未定義行為，包括系統崩潰和靜默記憶體損壞。
3。 hlt指令
到目前為止，我們在_start和panic函式的末尾使用了一個簡單的空迴圈語句。這將導致CPU無休止地自旋，從而按預期工作。但是這種方法也是非常低效的，因為即使在沒有任何工作要做的情況下，CPU仍然會繼續全速執行。在執行核心時，您可以在任務管理器中看到這個問題：QEMU程序在整個過程中都需要接近100%的CPU。
• 我們真正想做的是讓CPU停下來，直到下一個中斷到達。這允許CPU進入休眠狀態，在這種狀態下它消耗的能量要少得多。hlt指令正是為此而生。讓我們使用它來建立一個節能的無限迴圈。
instructions：：hlt函式只是彙編指令的瘦包裝。這是安全的，因為它不可能危及記憶體安全。
• 現在，我們可以使用hlt_loop迴圈來代替_start和panic函式中的無限迴圈。
• 讓我們也更新一下lib。rs。
現在，用QEMU執行核心，我們會發現CPU使用率大大降低。
4。 鍵盤輸入
現在已經能夠處理來自外部裝置的中斷，我們終於可以新增對鍵盤輸入的支援。這將是我們與核心進行的第一次互動。
與硬體定時器一樣，鍵盤控制器也被設定為預設啟用。因此，當你按下一個鍵時，鍵盤控制器會向PIC傳送一箇中斷，然後由PIC將中斷轉發給CPU。CPU在IDT中查詢處理程式函式，但是相應的表項是空的。所以會引發雙重錯誤。
• 那麼，讓我們為鍵盤中斷新增一個處理程式函式。它和我們定義的定時器中斷處理程式非常相似，只是使用了一個不同的中斷型別碼。
如上文中的圖例所示，鍵盤使用了主PIC的第1條中斷控制線。這意味著中斷會以中斷型別碼33（1+偏移量32）的形式到達CPU。我們將這個索引作為新的Keyboard變體新增到InterruptIndex列舉中。我們不需要顯式指定這個值，因為它預設為前一個值加1，也就是33。在中斷處理程式中，我們輸出一個k並將中斷結束訊號傳送給中斷控制器。
現在看到，當我們按下一個鍵時，螢幕上會出現一個k。然而，這隻適用於按下的第一個鍵，即使我們繼續按鍵，也不會有更多的k出現在螢幕上。這是因為鍵盤控制器在我們讀取所謂的「鍵盤掃描碼（scancode）」之前不會發送另一箇中斷。
1） 讀取鍵盤掃描碼
要找出按了哪個鍵，需要查詢鍵盤控制器。我們可以透過讀取PS/2控制器的資料埠來實現這一點，該埠屬於I/O埠，編號為0x60。
• 我們使用 x86_64包提供的埠型別Port從鍵盤的資料埠讀取一個位元組。這個位元組就是「鍵盤掃描碼」，一個表示物理鍵按下/鬆開的數字。目前，我們還沒有對鍵盤掃描碼進行處理，只是把它列印到螢幕上。
上圖顯示了我正在慢慢地鍵入字串“123”。可以看到，相鄰物理鍵的鍵盤掃描碼也相鄰，而按下/鬆開物理鍵觸發的鍵盤掃描碼是不同的。但是我們如何將鍵盤掃描碼轉換為實際的按鍵操作呢？
2） 解釋鍵盤掃描碼
鍵盤掃描碼和物理鍵之間的對映有三種不同的標準，即所謂的「鍵盤掃描碼集」。這三者都可以追溯到早期IBM計算機的鍵盤：IBM XT、IBM 3270 PC和IBM AT。幸運地是，後來的計算機沒有繼續定義新的鍵盤掃描碼集的趨勢，而是對現有的集合進行模擬和擴充套件。時至今日，大多數鍵盤都可以配置為模擬這三種標準中的任何一組。
預設情況下，PS/2鍵盤模擬鍵盤掃描碼集1（「XT」）。在這個碼集中，每個鍵盤掃描碼的低7位位元組定義了物理鍵資訊，而最高有效位則定義了物理鍵狀態是按下（「0」）還是釋放（「1」）。原始的「IBM XT」鍵盤上沒有的鍵，如鍵盤上的enter鍵，會連續生成兩個鍵盤掃描碼： 0xe0轉義位元組和一個表示物理鍵的位元組。有關鍵盤掃描碼集1中的所有鍵盤掃描碼及其對應物理鍵的列表，請訪問OSDev Wiki。
• 要將鍵盤掃描碼轉換為按鍵操作，可以使用match語句。
上面的程式碼轉換數字鍵0-9的按鍵操作，並忽略所有其他鍵。它使用match語句為每個鍵盤掃描碼分配相應的字元或None。然後它使用if let來解構可選的key。透過在模式中使用相同的變數名key，我們可以隱藏前面的宣告，這是Rust中解構Option型別的常見模式。
• 現在我們可以往螢幕上寫數字了。
Ø
使用 pc-keyboard 庫實現鍵盤的主要鍵位的解析。
• 我們也可以用同樣的方式轉換其他按鍵操作。幸運的是，有一個名為pc-keyboard的包，專門用於翻譯鍵盤掃描碼集1和2中的鍵盤掃描碼，因此我們無須自己實現。要使用這個包，需要將它新增到Cargo。toml內，並匯入到lib。rs中。
• 現在我們可以使用這個包來重寫鍵盤中斷處理程式keyboard_interrupt_handler。
我們使用lazy_static宏來建立一個由互斥鎖保護的靜態物件Keyboard。我們使用美國鍵盤佈局初始化鍵盤，並採用鍵盤掃描碼集1。HandleControl引數允許將ctrl+［a-z］對映到 Unicode字元U+0001-U+001A。我們不想這樣做，所以使用Ignore選項來像處理普通鍵一樣處理ctrl鍵。
每當中斷髮生，我們鎖定互斥物件，從鍵盤控制器讀取鍵盤掃描碼並將其傳遞給 add_byte方法，後者將鍵盤掃描碼轉換為Option
為了解釋按鍵事件，我們將其傳遞給process_keyevent，該方法將按鍵事件轉換為字元。例如，根據是否按下shift鍵，將物理鍵a的按下事件轉換為對應的小寫字元或大寫字元。
• 有了這個修改過的中斷處理程式，我們就可以寫一些文字內容。
3） 配置鍵盤
我們也可以對PS/2鍵盤的某些方面進行配置，例如應該使用哪個鍵盤掃描碼集。我們不會在這裡討論它，因為這篇文章已經足夠長了，但是OSDev Wiki上有一篇關於可能的配置命令的概述。
Ø
不使用 pc-keyboard 庫實現鍵盤的主要鍵位的解析。
1） 將Scancode和鍵盤對應。
Ø 將extern “x86-interrupt” fn keyboard_interrupt_handler中使用了pc-keyboard庫的部分刪掉。
Ø 根據
https：//
wiki。osdev。org/PS/2_Key
board#Commands
中Scancode和鍵盤的對應關係，對key進行賦值並列印。
2） 實現按下“Shift”鍵進行大小寫切換。
• 定義全域性可變靜態變數flag。
• 按下Shift，flag=1，大寫模式；鬆開Shift，flag=0，小寫模式。
• 新增大寫模式和鍵盤的對應。
3） 實現按下“Caps”進行大小寫切換。
