從頭開始實施互斥鎖

Question

可以說我正在編寫一個操作系統。我不是騙子，所以我從最底層開始。過了一段時間你有進程，先發制人的調度程序和Malloc。現在你需要互斥體和信號量。

這是一個代碼，它可以專門鎖定互斥鎖，或者專門增加或減少信號量。可以說我有這個代碼。

然後你會得到下一步：採取互斥體。讓我們說我們有兩個進程，爭取一個互斥體。在B可以觸摸它之前，進程A是第一個並且搶佔該互斥體。所以現在B必須等待。我的問題具體是關於處理等待階段。我可以看到以下選項：

1. 保持過程B上的調度和每次得到一個時間片，它會檢查它是否可以鎖定互斥的時間。如果沒有，重新安排並等待下一個時間片。這種方法看起來非常完美，除了浪費CPU時間而無法執行任何操作。
2. 介紹一個新進程，稱他爲Kernel。他是無所不知的人，可以接觸到所有事物。如果一個進程無法鎖定互斥鎖，它就會進入等待狀態，並且不會有更多的時間片。如果進程釋放互斥量，它會通知內核，內核將在稍後獲得時間片。在它的時間片中，它搜索等待互斥量的進程。等待此互斥鎖的優先級最高的進程將被喚醒。
3. 再次假設一個進程如果無法獲得互斥量就會進入WAIT：在互斥量釋放時，釋放互斥量的進程必須通過進程列表並查看哪些進程正在等待互斥量。然後它喚醒最高優先級的那個。我不喜歡這個，因爲我真的不想讓任何進程寫訪問內存的任何部分。我計劃使用MPU來防止這種情況，檢測段錯誤等。如果我實現這種方法，我將更加難以正確地實現MPU部分。

這就是我所能看到的。我最喜歡2，但它仍然感覺像很多開銷。我很想聽聽你對這個問題的意見：你如何實現等待鎖定互斥鎖被釋放？

更多背景：我實際上是在Cortex M4 CPU上實現操作系統。我知道我將無法擊敗freeRTOS等。它關於學習體驗。

Answer 1

通常，這是發生了什麼：

線程A試圖通過使系統調用引用它來獲取互斥。沒有其他線程擁有互斥鎖，因此它的調用成功。 A運行在..

線程B嘗試通過使系統調用引用它來獲取互斥鎖。互斥體被採用，所以B被從正在運行的線程列表中取出並插入到互斥體結構中的隊列中。內核返回到準備好的其他線程。線程B現在是死代碼和堆棧。

線程A通過創建引用它的系統調用來釋放互斥鎖。互斥線程隊列被檢查以查看它是否有條目，並且它已經。線程B從隊列中彈出並添加到就緒線程列表中。調度程序/調度程序決定在覈心上運行哪一組就緒線程。線程B可以在這個集合中，這取決於調度器算法和所有其他線程上存儲的狀態數據。線程B可以直接在另一個內核上運行，而不是線程A，它可以立即搶佔線程A（它將從運行變爲就緒），或者它可能根本無法運行，因爲可用內核正在用於運行其他更高級別的線程。

不需要'內核進程'，只需要內核代碼和數據。

不需要'時間片'。 Timeslices與此功能無關。

'搜索進程等待互斥'是一個隊列彈出，O（1）。評論後

編輯：

「這意味着每一個進程可以訪問相關 調度所有記憶」

不是所有的時間，因爲系統調用更改爲內核狀態然後回來。用戶狀態的線程不需要對內核內存進行無限制的訪問。

你需要互斥體或信號燈開始等待互斥或 信號量（以保證隊列的線程安全）。

不。通常情況下，移動容器之間的線程意味着刪除並只插入一個指向線程控制塊的指針。這樣的操作非常快，偶爾的爭用可以通過原子自旋鎖，中斷禁用或更復雜的涉及內核通信驅動程序的序列化/保護機制來避免。