---
# System prepended metadata

title: NCTU OSDI Dicussion - Kernel Synchronization
tags: [OSDI]

---

# 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 上？