# NCTU OSDI Dicussion - Kernel Synchronization ###### tags: `OSDI` * Kernel Preemptive * 多工的OS一定要支援user preemptive，一般說preemptive是指被切換的時間點在kernerl。 * kernel preemeptive難做是因為kernel會有很多共用的resource，然後就很容易壞掉。 * 而且因為這樣，其實kernel要做的事情很容易被切換去其他事情，但是這樣的OS在real time response會更好。就是一個tradoff啦。 * 但也因為這樣kernel會佔一些共用的resource，然後又被切走，所以kernel preemptive的OS會更容易產生deadlock。 * Deadlock * 雖然恐龍本說deadlock有4種條件。 * 但是在implement中，很難去檢查那4種條件。恐龍本沒有說錯，只是他主要是theory，跟implement有差距。 * Sleep lock * 把自己設成idle mode，然後call schedule。不是自己call `sleep()`。會等到有人離開critical section，把lock解開。然後那些人在等lock的人就會變成running mode。然後接下來需要這個resource的那些人就會去搶。但說搶也不恰當，主要是看誰被schedule到，就輪到誰。但是也只有一個人會進critical section，那些沒有搶到的人，只會再起來一下，然後發現還是沒有東西，又回去變成IDLE State。 * Spin lock * 如果在single core中有人執行spin lock，他就會當機。因為她就是一直在那邊轉。就算有interrupt。他處理完interrupt還是會回來這邊，然後，也不會有其他人去幫他把lock解開。就算在interrupt subrountine去幫他把lock解開，但是subrountine中使用到這個共用變數也還是要用spin lock啊，然後就沒有然後了。 * 在single core中，spin lock就紙是disable interrupt而已，他不會在那邊瘋狂轉轉轉。 * spin lock是給multi core用的啦，你就佔住一個core在那邊轉，反正會有其他core去把lock解開。 * lock * 開大絕，要操作protect資源就把interrupt關掉，但是你的performance效率差報。 * conntext switch * 是有一些principle去決定到底要用甚麼機制去lock。 * 但是你就是寫kernel的人，你要大概知道那個時間差。 * multiple core * 兩個cpu有沒有可能同時一起run一個指令？`test_and_set()` * 如果兩個都一起執行下去會怎樣？ * 兩個變數會在register會在memory中？ * 都在memory中。那兩個cpu都一起下指令到memory bus。 * 然後兩個就去搶memory bus。 * 但是memory bus就是一個共用的資源。 * memory bus就只會挑一個起來做事。 * 然後下一個人的test就會失敗。 * 都在register中，在自己的local cache中，然後需要的時候在寫回memory中。 * 這件事不會發生，因為CPU會規定tets_and_set指令一定要到memory中去處理。 * 這個問題有一點牽扯到硬體設計。 * Concurrency * True concurrency * 兩個CPU同時真的處理同一個東西。 * 兩個處理單元同時處理同一個東西。 * Pseudo Concurrency * 單一cpu而言就是分開跑。 * 但是hyper threading。必須把她當dual core在做。就必須當作true concurrency處理。 * Core v.s CPU * Core強調的是一個處理單元，一個在做事的東西。 * CPU會強調指一個硬體的東東，central process unit。一個CPU他可能對上OS模擬處兩個core的功能，讓OS以為有兩個。 --- * 在影片中提到當 semaphore 的 counter = 0 時，task 如果 call down function，require semaphore 會進入 sleep state，但什麼樣的情況 task 能離開 sleep state ? * 能透過 time out 離開 sleep state，並從 wait queue 中離開，雖然沒有 require 到 semaphore 並回傳 errno * semaphore wake up task * binary semaphore 似乎能包含 mutex 某些功能，但 mutex struct 中有 owner 設計又跟 semphore 不太一樣，那 mutex 會特別用在什麼樣的情況，而不用 binary semaphore? * 在 SMP 下 linux kernel 的 atomic operation 也是會考慮到不同 CPU cache 的問題嗎？ * Atomic operation需要硬體支援,那是不是沒有其他方法在某些機器上達成,需要有不同的kernel來實現? * 在單核處理器會因為lock而有priority的問題,再多核處理器是不是也有機率會發生? * [solved] 如果今天的cpu 確定只有單核 是不是可以把某些為了解決多核心的lock的功能去除 會比較快 * 現在 linux 之類的作業系統對於 dead lock 的態度是不理它嗎？ * [solved] 之前 lab 裡面有出現 ldxr 等指令，他在有用mmu轉換address的時候會有什麼不同嗎 * 在 microkernel 下 file system 之類的資源，還算是 share resource 嗎？因為那些 device driver 都跑在各自的 user mode，感覺就算不是 share resource 了？這樣 microkernel 還需要做 kernel synchronization 嗎？ * spin_lock disable preemption 的目的只是不希望其他 process 跑到相同位置之後浪費時間跑 spin 嗎？感覺既然都 lock 住了，不 disable preemption 也不會出現什麼問題(?) * spin_lock_irq 還需要 disable preemption 嗎？有可能在沒有 interrupt 的情況還是被 preempt 嗎？ * (Solve, ref: http://people.cs.pitt.edu/~ouyang/20150225-kernel-concurreny.html) * 為什麼spin_lock禁止kernel preemption呢? 其他thread若要嘗試改動shared data應該會被卡住不是嗎? * spin_lock在SMP的情況下，若是其他thread都不釋放資源，這個core是不是就不會被釋放掉一直在作loop? * [已解 yes 因此通常用在不會等太久的情況下] * 一般來說spin_lock都必須要包含disable interrupt，除非可以保證interrupt handler不會使用到spin_lock中的shared data，這樣理解對嗎? * 有atomic operation為什麼還要一般的計算，假設現在做add一定是希望計算的值照所希望的相加，用atomic可以保證這件事情正確，那為什麼要用有可能被干擾的方式做add * 為什麼real time比快速困難? (solve) * ISR什麼時候會用到share data，不能避免嗎? (solve) * spin lock 之後cpu沒資源會等，不能讓他先執行其他task嗎? (solve) * 我們如何確保多個cpu之間的spinlock,如何避免多個cpu同時執行同一個指令write同一個data(ex:true concurrency)？ * 課程中在評估要選擇哪種lock機制時，不斷以context switch時間為單位去評估長短。那一次context switch要多久？ * 在atomic operation中有AOMIC_INT, atomic_read，這兩個在展開assmbley會有甚麼操作嗎？為甚麼有atomic的需求？ * 在使用spin lock使用原則中，有提到lock the data, not the code。那lock the code是甚麼概念？還是根本沒有，全部都是lock data才對。 * (solved)這些lock 或是 atomic opertaion會混合使用或是類似巢狀的設計嗎? * (solved)單核心的spin lock, 為何會看到其他lock住的東西? * (solved)count for one的意思是只同時有一個thread操作變數，那這樣Semaphores會有同時存在多個thread操作同一個變數嗎? * 影片中提到 semaphores 的實作是把自己設定為 idle state 然後 timeout，把自己 schedule 掉，那請問是誰把他設回 busy state？是佔用資源的那個 process 在 unlock semaphores 的時候，會把他設定回 busy 嗎？ * 影片裡面提到 preemptive 可以避免一定的 deadlock，請問可以詳細說明一下嗎？ * 所以多核心的狀況下怎麼保證 atomic operation 有效，有使用些什麼額外的措施嗎？ * Atomic instruction 在單一 CPU 比較有用，所以在多 core 上就等於沒用了嗎 * [已解，https://www.kernel.org/doc/html/v4.10/core-api/atomic_ops.html] * Linux 的這些 atomic function 是基於 atomic instruction 嗎。 * [已解，看起來是的。Reference 同上] * 為什麼 exception handler 會建議用 semaphore，是因為有多個 exception handler 會共用同一個 resource，所以有 count 的概念嗎？ * 有個 process 進入 critical section ，並把 lock 設1 ，但在還沒有出來 critical section 時就被 kill 掉了，這樣 lock 是不是所有人都不能操作了。 * 如果有兩種interrupt handler會共用一種資料，那我可以只 mask 這兩種interrupt handler就好，而不關掉全部的interrupt？還是實務上這樣比較複雜，容易出錯？ * 影片中說到deadlock是不容易避免的，所以有時會需要手動kill掉（42min, 45s)，這是針對user program而言嗎？如果是kernel發生deadlock，這樣不就會電腦直接當掉了 * 影片中老師常以兩個context switch作為選擇lock的標準，但不同優先度的process執行的時間也不一定一樣，且資源會被lock的時間也不一定知道，那要怎麼決定使用的lock？ * 這裡的 global data 指的是所有可以 shared 的 variable？不管是不同的 process 間，或是 kernel code/interrupt 跟 user code 間，只要有兩個不同的人可能同時改到這個 variable 就算？ * spin lock 為了避免 interrupt 動到 shared data，必須 disable local interrupt，不是很懂 local interrupt 跟 global interrupt 差在哪？ * 為什麼 hold semaphore 之後還需要再 hold spin lock？我的理解是兩者的主要功能都是保護 shared data，差別是一個 sleep；一個 idle，不是很懂為什麼有需要同時做 semaphore 和 spin lock？ * 影片中提到 ISR 中可能會操作 shared data，造成 race condition。不過如果 ISR 也有做好 lock，是不是就不會有問題了？ * 想問在寫 kernel 的時候如何確定某個 lock 會在極短時間 (小於兩個 context switch) 被釋放，因使用 spin_lock？是否有什麼典型的使用情境？ * 影片中提到 ISR 中也可能會操作到 shared data，造成 race condition。不過如果 ISR 也有做好 lock，是不是就不會有問題了？ * 承上題，如果在 ISR 中不想用 lock 保護 shared data 是因為不想在跑 ISR 時可能會因為 access 被 lock 住的 shared data 而等待很久嗎？ * 老師說了如果會有 interrupt 打進來的話, 即使 ISR 本身不操作 shared data, 在做完 context switch 之後可能其他的 process 會進 kernel 去操作 shared data, 所以還是不安全, 可是不是已經把 shared data lock 住了嗎, 為什麼其他 process 進 kernel 可以操作 shared data? * 上課提到的 memory barrier, 看起來是一個 thread 內的保護機制, 那兩個 threads 之間有保護機制嗎? * hold spin lock 後不就在 spin 了嗎, 要怎麼再去 hold 一個 semaphore? * semaphore和mutex的差異，兩者的使用情境上會有甚麼不同呢? * https://stackoverflow.com/questions/62814/difference-between-binary-semaphore-and-mutex * mutex需由上鎖的thread自己解鎖，而semaphore則可以由其他的thread解開 * mutex只允許一個thread進入crtical section，semaphore則可以設定要讓多少thread進入 * mutex可以用來保護criticla section，而semaphore的功能比較像是: "當A執行到某一處時，去通知B可以開始執行了"這樣的機制。 * 總結來說，一般mutex只用於保護critical section。而semaphore則用於保護某variable，或者用於thread間的syncronize。 * 有點confuse memory barrier到底是一個可以在kernel call的function? 還是是一個用來告訴compiler不要去更改執行順序的keyword(類似volatile那樣?) * 硬體怎麼guarantee atomic operation? * Cache coherence? * https://stackoverflow.com/questions/14758088/how-are-atomic-operations-implemented-at-a-hardware-level * [solved] lock 除了讓 kernel 在奇怪的地方壞掉之外 是不是能藉此進行 kernel exploit? * [CVE-2019-18683 Linux kernel 內的 vivid driver (看起來是處理視訊串流的 driver) 因為 mutex lock 沒寫好造成 use-after-free 的 bug 發現的人用 kernel space UAF exploit 技巧成功提權 (利用 bug 從 user 權限變為 root 權限) https://a13xp0p0v.github.io/2020/02/15/CVE-2019-18683.html] * 之前Intel的處理器 shared cache 會被 side channel attack，atomic operation是否可以防範這種攻擊? * 應該不行，因為是 copy on write 和 branch prediction 的機制導致，不太算是 OS programmer 的問題 * 已知 preemptive kernel 仍然需要有 critical section 保護重要的資料結構(pseudo concurrency)，那 nonpreemptive kernel 是不是就完全不需要 kernel synchronization, 還是有例外的狀況? * 在 micro kernel 的架構下很多系統服務會被搬到 user level，那麼 OS programmer 該如何處理從 kernel level 搬到 user level 的 module 裡面的 synchronization，還是會傾向重寫? * 為何從io或sleep回來的process優先級會比較高？ * 若系統不幸進入dead lock會怎麼做？資源全部釋放掉嗎？ * （解決）鎖的種類 * 當使用spin_lock, resource已經被lock住了, 則會自己busy loop還是把自己schedule out? * : 使用spin_lock是在short period的時機, 所以在kernel code是利用 for infinite loop空轉, 直到拿到resource break離開並且是disable kernel preemption狀態 * 一個情境是, 假如在SMP的架構下, 2個core同時各自接收到interrupt, 是否會有interrupt互相影響到shared data的可能? 處理上是否會拋棄任一個interrupt？ * Non-preemptive Kernel 在 single core下 , Interrupt還是有可能會打進來, 所以也會可能有access shared data的問題? * : 在SMP下把interrupt關掉 , Disable Local interrupt * 有OS會解決發生的deadlock嗎，還是發生了都只能強制砍掉? * [solved] Mutex vs semaphore ? * (https://stackoverflow.com/questions/62814/difference-between-binary-semaphore-and-mutex/346678#346678) * OS自己也有可能產生Deadlock嗎? * 在kernel中有對呼叫spinlock後做無窮迴圈做檢查嗎?比如說kernel module編譯或是Insert階段?還是完全相信使用者知道自己在幹嘛? * 在cpu中實現test&set這種atomic operation instruction 需要甚麼效能上的犧牲嗎?為甚麼不要把指令都設計成atomic的就好(atomic add, ....etc)? * 所有的 lock variable 都是透過硬體的 atomic instruction 來確保只有一個 process 拿到 lock 嗎？ * 想問 Livelock 該如何解或是預防？ * 在 interrupt service routine 裡要用到shared variable時 , 是不是用 spinlock 較 mutex好嗎 ？ * Mutex 跟 binary semaphore 的差異? * 如果 cpu 沒有 atomic 的 instructions, 有辦法做 lock 的機制嗎？ * Atomic operation 為什麼只有對 int 的？ floating point 有對應的 atomic operations 嗎？ * read/write lock 當連續的reader 出現或是連續的 writer 出現時可能會造成對方starvation，如果我們在read/write lock 加入 counter 限制n次 reader/writer 進入後就必須釋放權限。這樣的設計會不會有問題 * 有什麽情境適合是用 read/write lock * 在multi-core 的環境下要如何確保，mutex 的更動可以即時的同步到其他的 core 上？