# Linux kernel 面試考題 ###### tags: `Interview`,`linux` ## Process vs Thread ### Process * Process 意旨已經執行並且 load 到記憶體中的 Program * 由「memory space」,「thread」 * 不是基本執行單元，thread才是執行單元 * 需要資源（CPU, memory, file, io device）才能完成工作 ### Thread * 共享process資源(code, data, file) * 有自己的「stack」,「register」 ## Multi-Process vs Multi-Thread ### Multi-Process * 因為不同Process之間有各自的記憶體空間，所以不同Process之間需要溝通則透過系統函式 * 優:相同時間內可以完成較多工作 ### Multi-Thread * 當不同thread要操作同一個資料時，需要透過spin lock 或 mutex等機制來解決 * 優:相同工作可以在較短的時間內完成 ### overall * 速度方面 multi-process > multi-thread * 資源消耗方面 multi-process > multi-thread * 記憶體消耗方面 multi-process > multi-thread * 若程式當掉，則multi-thread會全滅，但multi-process則不一定 # Synchronization * critical section * 在同步的程式設計中，臨界區段指的是一個存取共享資源的程式片段，而這些共享資源又無法同時被多個執行緒存取的特性。 當有執行緒進入臨界區段時，其他執行緒或是行程必須等待，有一些同步的機制必須在臨界區段的進入點與離開點實現，以確保這些共享資源是被互斥或的使用，例如：semaphore. ## 硬體解決方法 ### spin lock * 其他process會busy waiting直到spin lock 解鎖 * 會disable kernel preemption * UP的spin lock基本上不存在，就只是做disable preemption而已 * 使用原則 * 如果使用spin lock時間很長，則不要用spin lock，基本上要在2個context switch結束 * 不能在spin lock裡面使用遞迴 * spin lock可以被interrupt打斷，所以要使用spin lock時要確保interrupt不會操作到同一個資料結構，如果不能保證則需disable interrupt(local interrupt->自己那顆CPU) * 或是用spin_lock_irq, spin_lock_irqsave * spin_lock_irq: 先disable interrupt再lock，離開的時候再enable intterrupt(少用，可能原本進來時interrupt就已經disable了，離開時會把本來關掉的intterrupt打開) * spin_lock_irqsave:會把intterrupt status存起來，離開時會變回原來的狀態 * read/write spin lock * 一個process寫，多個process讀 ## copy on write * 好處： * 減少分配和複製記憶體空間的延遲時間 * 減少不必要的資源分配 * 運作： * fork()之後，child process的記憶體空間會指向和parents process同一個位址，並設置為read-only，當開始執行並需要修改記憶體時，cpu會檢測到read-only而觸發page fault，並將修改的page複製一份 * exec()則是會完整建立一個記憶體空間給chile process ### semaphore & mutex * sleeping lock(把自己set to idle) * 沒有disable preemption * 把task放到wait queue * 適合用在需要lock很長時間的情況 * 不能在interrupt 裡面使用 * 不能hole spin lock在去hole semaphore(但是可以hole semaphore再hole spin lock) * mutex * semaphore的一個special case ### completion variables ### sequential locks ### interrupt disable ### preemptions disable ### memory barriers ## 軟體解決方法 * Peterson solution # Memory ## kernel space vs user space * kernel mode -> ring0 / user mode -> ring3 ### kernel space * kernel space的程式就可以透過machine code來操作cpu所管理的硬體資源 ### user space * 不能直接操作硬體資源，需要透過syscall # C ## stack vs Heap * https://blog.gtwang.org/programming/memory-layout-of-c-program/ ### stack * 用於靜態記憶體配置 * local variable, function call address ### heap * 用於動態記憶體配置 * malloc ## function call * https://hackmd.io/@dange/rk9xmgHKX?type=view * 疊一個stack frame ```asm= push rbp mov rsp, rbp sub ... ... add ... mov rbp, rsp pop rbp ret ``` ## function pointer * 好處： * 程式可讀性、維護 * 當有一個事件需要對應到很多個function時，不用寫很多if/else or switch case # programming concept ## recursive vs iteration * recursive * 優：程式簡潔、可讀性、較少記憶體空間 * 缺：執行時參數的存取費時、需要額外stack * iteration * 優：不需要額外stack、節省執行時間 * 缺：浪費記憶體空間、程式攏長、可讀性差 ## diff. linked list and array ### Array * 需要事先宣告大小 * 在compier時就宣告好空間，固定 * 記憶體空間是連續的 * 直接存取或隨機存取 * 使用的記憶體空間較少 ### link * 可以動態宣告 * 在run time時配置空間，有彈性 * 記憶體空間可以不連續 * 需要走訪每個節點才能取得資料 * 使用的記憶體空間較大(要多存指標)