# OS Concept ###### tags: `EMBEDDED_C` - [ ] Process && Thread (multi-thread) - [ ] race condition - [ ] critical section - [ ] OS(Kernel Space vs User Space) - [ ] concurrent vs parallism - [ ] mutex - [ ] semaphore - [ ] spinlock - [ ] Interrupt/Exception/ISR - [ ] priority inversion - [ ] deadlock - [ ] live lock and how to handle it - [ ] scheduler design - [ ] shared memory - [ ] memory leak - [ ] memory alignment - [ ] boot flow - [ ] Pooling VS Interrupt (Proc and Conf) >為什麼這樣設計 優點缺點比較 ## What's OS? ## Preocess VS. Thraed - One memory from one process can be shared to multiple threads - https://jtlearn.blogspot.com/2017/06/java-process-and-thread.html - Multiple threads in one process can communiate with shared memory - But we have to take care of race condition - The communication between processes needs IPC (inter-process communication) - [Inter-process_communication wiki](https://en.wikipedia.org/wiki/Inter-process_communication) - OS IPC example: [Linux Programming practice](https://github.com/LinEmsber/Linux_Programming) - The case study: 4 threads vs. 4 processes under 4 physical CPU cores - The 4 threads uses the same memory scope. The data comunication can be completed by global variable (shared memory) - But we have to avoid race condition - The 4 processes need to use IPC to complete the data communication ## How to handle thread conflicts? - Thread 1 (T1) and 2 (T2) are using the global variable *global_x* - The conflict secnario - 1. T1 read the global_x - 2. T2 read the global_x - 3. T1 write to the global_x - (Race condition occurs!!!) - 4. T2 witre to the global_x - How to slove race condition - [Peterson algorithm wiki](https://en.wikipedia.org/wiki/Peterson%27s_algorithm) - [can-someone-help-me-to-understand-how-petersons-solution-satisfy-no-starvation stackoverflow](https://stackoverflow.com/questions/58575638/can-someone-help-me-to-understand-how-petersons-solution-satisfy-no-starvation) - [Peterson’s Solution](https://www.youtube.com/watch?v=gYCiTtgGR5Q) - Ensure the operation of write after read can be completed by one specific thread - 1. T1 read to *global_x* - 2. T1 write to *global_x* - (Race condition does not occurs!!!) - 3. T2 read to *global_x* - 4. T2 witre to *global_x* - ![](https://i.imgur.com/W7uYJSo.png) - Use lock mechanism by hardware support - spin lock - https://stackoverflow.com/questions/54015398/aarch64-load-acquire-exclusive-vs-load-exclusive - mutex - Atomic operation - https://github.com/LinEmsber/Linux_Programming/blob/master/atomic/atomic_01.c process vs thread -> 共用stack thread conflicts -> lock Process: the unique memory page, like a container with only one thread, take more time to context switch, more effor to communicate with other process (IPC) thread: All the threads running within a process share the same address space, file descriptors, stack and other process related attributes. lightweight process, less time to context swith, efficient to communicate with other thread ## Multiple threads in the process should conduct context-switch - https://en.wikipedia.org/wiki/Context_switch - https://ithelp.ithome.com.tw/m/articles/10276907 - The context-switch implementation: - The function: arm64_context_switch - https://github.com/littlekernel/lk/blob/master/arch/arm64/asm.S - 6 The Base Procedure Call Standard - https://github.com/ARM-software/abi-aa/blob/main/aapcs64/aapcs64.rst#id46 - The system register: tpidr - https://developer.arm.com/documentation/ddi0595/2021-06/AArch64-Registers/TPIDR-EL0--EL0-Read-Write-Software-Thread-ID-Register?lang=en - Function call stack - https://youshaohua.com/post/simply-and-easily-understanding-function-call-stack-by-a-vision ### Kermel Space && User Space * #### Isolation #### isolation 其實就是最重要的概念,也就是說當user space crash的時候不會影響到Kernel的運作 > 之所以要區分kernel space以及user space, 一部分原因是因為我們希望作業系統可以壟斷所有的硬體操作, 讓一般的應用程式不能亂搞. Kernel space與user space的區別也可以看成是可存取的記憶體位置不同、可執行的指令集不同. > e.g1: 如何確保一個使用者不會霸佔資源不放呢(CPU/RAM等)? > e.g2: 如何確保一個使用者不會惡意更動作業系統內部的資料結構? > e.g3: 當執行多個程式的時候, 如何確保A程式不會干擾B程式呢(如更動對方的變數還是什麼的)? > e.g4: 怎麼確保硬體有被正確地操作呢? * [Referece_Video_jserv]() ## Process && Thread ### [Refernece Process Synchronization](https://hackmd.io/@Chang-Chia-Chi/OS-CH6) ### Thread 所擁有得 * Thread各自獨立擁有的部分： - Thread ID - Thread State - Program Counter - Register Set - Stack * Process內Thread間彼此共享的部分： - Code Section - Data Section - OS Resources ##### `Code Section+Data Section=Memory Space, Address Space, Heap Memory` ### Prcoess vs Thrad Process有 ***share memory*** ### multi-thread ## Race Condition 當多個 Processes 同時存取及操作 shared data 時，最終的值取決於最後一個完成執行的 Process，這個現象稱為 Race Condition 在 single-processor machine 中，我們可以 disable interrupt 或著使用 **Non-preemptive scheduling** 來達成同步，但在 User Program 中不可能使用，會影響整個系統的運作 通常將可能產生Race Condition的區域稱作**Critical Section**` ### How to avoid the Race condition? ### Critical Section >critical section是指程式碼中會存取到共享資源的區段，共享資源有很多種，像是共用裝置或是共用記憶體，最重要的是這個共享資源有無法被多人同時存取的特性。 > 所以若Critical Section允許被兩個執行緒以上執行的話，通常會採用 Semaphore 但相對帶來的副作用就是 Deadlock --- ## Concyrrency * [jserv_reference](https://hackmd.io/@sysprog/concurrency/https%3A%2F%2Fhackmd.io%2F%40sysprog%2FS1AMIFt0D) Concurrency 指程式架構，將程式拆開成多個可獨立運作的工作，像是驅動程式都可獨立運作，但不需要平行化。Parallelism 則指程式執行，同時執行多個程式。Concurrency 可能會用到 Parallelism，但不一定要用 Parallelism 才能實現 Concurrency。在 Concurrent 中，工作可拆分成「獨立執行」的部份，於是「可以」讓很多事情一起做，但「不一定」要真的同時做。但 Parallelism 著重規劃， 將能夠並行的程式，分配給不同硬體單元，使其同時執行。 接著 Synchronization (同步處理) 則確保多個執行單元運作並存取資源時，執行結果不會因為執行單元的時間先後的影響而導致錯誤。mutex 與 semaphore 的差別在於： 1. process 使用 mutex 時，process 的運作是持有 mutex，執行 CS 來存取資源，然後釋放 mutex。換言之，mutex 就像是資源的一把鎖：解鈴還須繫鈴人。 2. process 使用 semaphore 時，process 總是發出信號 (signal)，或者總是接收信號 (wait)，同一個 process 不會先後進行 signal 與 wait。換言之，process 要不擔任 producer，要不充當 consumer 的角色，不能兩者都是。semaphore 是為了保護 process 的執行同步正確。 --- ## MUTEX && SEMAPHORE Mutex 與 Semaphore 都是用在保護 critical section，確保多個 process 平行運作並存取資源時，執行結果不會因為執行程序的時間先後的影響而導致錯誤。 ## Mutex >指允許同一時間只有一個process可以存取某一塊資料 (有保護的功能), 只有鎖住的process才可以解鎖 (有owner概念) * 30s Mutex mutex是為了處理thread中的mutual exclusion還有避免unbounded priority inversion，在thread中資源是共享的，當不同thread要對global做存取時就可能出現問題，例如一個thread在更新變數而另一個在讀取。mutex就是一個lock，取得lock的thread可以存取，其他則不行，這種情況會一直到lock被釋放，不會知道有多少thread在等待，等待這件事是有跟無的差別。至於如何避免unbounded priority inversion，可以設置一個timer看如果某個thread取得lock過久就會將lock釋放，因此高priority的thread即可取得lock而不會造成低priority的thread拿著lock而高priority thread無法執行的情況。mutex是一把鑰匙，一個人拿了就可進入一個房間，出來的時候把鑰匙交給隊列的第一個。一般的用法是用於串行化對critical section代碼的訪問，保證這段代碼不會被並行的運行。（A mutex is really a semaphore with value 1.） ## Peiority Inversion in Mutex #### 概念解釋 > priority inversion for mutex 假設A,B,C 三個process 優先權 A>B>C, C握有lock，A在等lock造成優先權高的A等待C的情況，若此時B變為可執行的，則B會preempt process C，造成process A需要本來Prioruty比B高卻需要花時間等待B釋放priority，這種情況稱為unbounded priority inversion。 #### 解法 >發生這種情況是用priority inheritance protocol來解決，即暫時提高C的priority繼承A的priority，這樣就能阻止process B preempt，等C執行完時再放棄繼承priority，回復原本的priority。 ### --- ## Semaphore >類似計數器概念, 限制數量存取某一段資源 >比較特別的是可以a鎖b解 * 30s Semaphore semaphore是為了處理資源分配的問題，假設有一至多個資源且有數個process要進入critical section，這邊會使用semaphore去計數process的數量，當資源被釋放時則讓下一個process進入，所以他會有一個變數紀錄有多少剩餘資源或是多少process在等待，因此semaphore可以當作是一個counter。semaphore是一間可以容納N人的房間，如果人不滿就可以進去，如果人滿了，就要等待有人出來。對於N=1的情況，稱為binary semaphore。一般的用法是，用於限制對於某一資源的同時訪問。 * 60s Semaphore 關於semaphor我們可以講解得更詳細一點，semaphore value可用來表示可用資源的數目，可在初始化時將semaphore value設為可用資源的數目，然後，在使用資源時減1（wait函數或是sem_wait()），在釋放資源時加1（signal函數或是sem_post()）；若為負數時，表示資源不足，要存取共享資源的process或thread會被阻擋（block），需要等待semaphore value變為正整數時，才可存取共享資源。 ### Binary Semaphore > 沒有owner的概念, 任何的thread都可能lock(0)/unlock(1) #### [Semaphore VS Mutex](https://hackmd.io/@nKngvyhpQdGagg1V6GKLwA/Skh9Z2DpX?type=view) > (1)Ownership 的概念 (2)使用上本質的差異（資料保護或執行緒同步mutex適合用於保護critical section。而semaphore則用於保護某變量，或者同步 (3)Mutex 可以，但 Semaphore 所不能解決的問題 (e.g. priority inversion，recursive deadlock) ### Mutex vs Semaphore Mutex 與 Semaphore 是經常被混用的觀念(尤其是 binary semaphore = mutex 這種理解)，做為系統的開發者(雖然我還不是)，勢必需要釐清其中的差異。 對於 mutex 來說，**解鎖只能由上鎖的 thread 來完成**，經常使用的情境是對於資源的保護 / 互斥。 * e.g: 就像是對於一個房間，只存在一把鑰匙，拿到的人就可以進入房間，而其他的人必須排隊等待，直到那個人出來。 semaphore **可以由原本的 thread 或是另外一個 thread 解開**，因此可以讓數個 producer 與數個 consumer 在計數器的基礎上進行合作。**經常的使用情境是在兩個 thread 間的同步上**，當 thread 進行至某個點時，去通知 thread B 可以繼續往下執行。 另一個 mutex 與 binary semaphore 的差異在於， **mutex 的使用可能產生副作用: priority inversion** 假設有優先權從高至低的三個 thread T1、T2、T3，其中 T1 和 T3 需要一個由 mutex 保護的資源: 最開始沒有其他 thread 在運行，因此 T3 先執行並拿到 mutex T2 一段時間後產生，因為 T2 priority 較高，因此 interrupt 時排程器讓 T2 先執行 T1 一段時間後產生，因為 T1 priority 最高，理論上該由 T1 先執行，但是因為資源被 T3 佔用了，因此 CPU 只能先讓給 T2 執行，這就是 priority inversion 為此， mutex 實作中需要採用一些機制來防止 priority inversion。但是，因為 semaphore 是為了不同 thread 間同步而存在，實作上就不必為此煩惱。 ### binary semaphore與mutex的差異 在有的系統中binary semaphore與mutex是沒有差異的。在有的系統上，主要的差異是mutex一定要由獲得鎖的process來釋放。而semaphore可以由其它process釋放（這時的semaphore實際就是個原子的變量，大家可以加或減），因此semaphore可以用於process間同步。 semaphore的同步功能是所有系統都支持的，而mutex能否由其他process釋放則未定， > 因此建議mutex只用於保護critical section。 > 而semaphore則用於保護某變量，或者同步。 ### priority inversion for mutex 假設A,B,C 三個process 優先權 A>B>C, C握有lock，A在等lock造成優先權高的A等待C的情況，若此時B變為可執行的，則B會preempt process C，造成process A需要等待更久的時間，這種情況稱為unbounded priority inversion。 發生這種情況是用priority inheritance protocol來解決，即暫時提高C的priority繼承A的priority，這樣就能阻止process B preempt，等C執行完時再放棄繼承priority，回復原本的priority。 --- ## Spinlock(Hardware) > 類似計數器概念, 限制數量存取某一段資源 比較特別的是可以a鎖b解 > 單一處理器建議使用 Disable Interrupt > 多核心處理器 Busy Waiting???? ### [John Lin] Mutex SpinLock compared - The spin lock is implemetated in low-level exclusive instruction - https://github.com/littlekernel/lk/blob/master/arch/arm64/spinlock.S - https://developer.arm.com/documentation/100934/0100/Exclusive-access-instructions?lang=en - https://github.com/littlekernel/lk/blob/master/arch/riscv/spinlock.c - Need to know waht is trylock!!! - The mutex can laverage spin lock for easier to use - https://github.com/littlekernel/lk/blob/master/kernel/mutex.c ### Spinlock versus mutexes(Reference from Packet Linux Device Driver) [Reference](https://medium.com/@chinhung_liu/work-note-semaphore-mutex-spinlock-391bba4c161a) * Quick Note >Mutexes protect the process's critical resources, whereas >spinlocks protect the IRQ handler's critical sections * Detail >Mutexes put contenders to sleep until the lock is acquired, whereas spinlocks infinitely spin in a loop (consuming CPU) until the lock is acquired Because of the previous point, you can't hold spinlocks for a long time, since waiters will waste CPU time waiting for the lock, whereas a mutex can be held as long as the resource needs to be protected, since contenders are put to sleep in a wait queue When dealing with spinlocks, please keep in mind that preemption is disabled only for threads holding spinlocks, not for spinning waiters. #### semaphore vs spinlock > spin lock與semaphore的主要區別是spin lock是busy waiting，而semaphore是sleep 這邊以POSIX（Portable Operating System Interface）為例，semaphore的情況是，process在sem_wait()失敗時會進行context switch將cpu交出並改變process狀態進入睡眠（在某些RTOS還有wait_semaphore的state），然後排入waiting queue讓其他process可以執行，直到資源釋放原本process才會在放入run queue，這牽扯到process狀態的改變。 spinlock利用test and set這個指令看有沒有辦法取得lock，因為是指令層級的操作所以有辦法達到atomic（這種操作只要開始就會運行到結束，中間不會有context switch），當lock無法取得時會用polling的方式不斷嘗試，特別的地方是當他取得lock時，process將不會進入睡眠（沒有context switch），這有幾個好處 效能會比semaphore好，因為他不做context switch，process可以一直執行 在SMP（Symmetrical Multi-Processing）環境中，因為process不會進入睡眠，無法執行其他process或處理interrupt會將工作分擔給其他CPU（但在單CPU情況下就像是disable interrupt） spinlock與semaphore的主要區別是spinlock是busy-waiting，而semaphore是sleep。對於可以sleep的process來說，busy-waiting當然沒有意義。對於單CPU的系統，busy-waiting當然更沒意義（沒有CPU可以釋放鎖）。因此，只有多CPU的系統，才會用到spinlock。 Linux kernel的spinlock在非SMP的情況下，只是關irq（Interrupt Request），沒有別的操作，用於確保該段程序的運行不會被打斷。其實也就是類似mutex的作用，串行化對critical section的訪問。但是mutex不能保護中斷的打斷，也不能在中斷處理程序中被調用。而spinlock也一般沒有必要用於可以sleep的進程空間。 而又以mutex跟spinlock來比較，mutex的機制是當process無法鎖定mutex時，process會進入sleep，中間會需要付出context switch的代價。spinlock的機制是採用 busy-waiting，直到鎖定spinlock為止。依據兩者的特性，一般來說，在單核心的系統中，會採用mutex。而多核心，且critical section只耗用一小段時間的狀況下，適合使用spinlock。由於要預期應用情境下的lock狀況相當困難，現代的作業系統中也加入一些機制增加彈性，發展出了hybrid mutex與hybrid spinlock。當process無法鎖住hybrid mutex時，作業系統不會馬上讓process進入睡眠，而是以類似spinlock的方式busy-waiting一小段時間，確定真的無法鎖住 hybrid mutex，才讓 process 進入睡眠。而當process 無法鎖住hybrid spinlock時，作業系統會允許process進行busy-waiting。但超過某個時間限制，則會讓 process進入睡眠，讓其它thread運作。 --- ## Priority Inversion ### Proority Inversion in RTOS --- --- ## Interrupt, ISR - 處理器接受到硬體的訊號,提示發生了某個event,需要被注意到 可以稱之為Interrupt - Software Interrupt is triggered by software code Device要跟CPU要資源有主要兩種方式:(1)一種是CPU 來做Polling的動作,(2)另一種方法是IRQ --- ## Dead Lock - How to slove - --- ## shared memory --- ## Memory Leak --- ## Memory alignment --- ## what’s the different between `Virtual memory` & `Physical memory`? 虛擬記憶體是電腦系統記憶體管理的一種技術。它使得應用程式認為它擁有連續的可用的記憶體（一個連續完整的位址空間），而實際上，它通常是被分隔成多個實體記憶體碎片，還有部分暫時儲存在外部磁碟記憶體上，在需要時進行資料交換。與沒有使用虛擬記憶體技術的系統相比，使用這種技術的系統使得大型程式的編寫變得更容易，對真正的實體記憶體（例如RAM）的使用也更有效率。 ## Why we use virtual memory - 1. The uncontintous physical memroy region can be regarded as contintous virtual memory. - https://ithelp.ithome.com.tw/articles/10208891 - 2. We can protect the physical memory region. ### [Q] 分頁表(page table)把Virtual Memory分配到實體 * e.g:page fault * why? * 記憶體不夠大？希望記憶體是連續的而不是零碎的 * e.g 1:Linux CMA in Contiguous Memory Allocation # spin_lock in LinuxRT * spin_lock 在rt linux（配置了PREEMPT_RT）的时候可能會被preempt，實際底層可能是使用支持PI（優先權反轉）的mutex。 * raw_spinlock 即便是配置了PREEMPT_RT也要強制的spin。 * arch_spinlock spin lock是和architecture相關的。 ## Reference [SJSU FreeRTOS Embedded System](http://books.socialledge.com/) [FreeRTOS_CoursesSJSU](https://kaikailiu.cmpe.sjsu.edu/#) [群暉AND 其他統整](https://hikaru79109.wordpress.com/2017/08/10/%E7%BE%A4%E6%9A%89and-%E5%85%B6%E4%BB%96%E7%B5%B1%E6%95%B4/) [Work Note-semaphore/mutex/spinlock By Chin-Hung Liu](https://medium.com/@chinhung_liu/work-note-semaphore-mutex-spinlock-391bba4c161a) [link text](https:// "title")