# 作業系統 ## 什麼是作業系統? 作業系統是一種特別的軟體，它為使用者和電腦硬體層之間溝通的媒介。主要目的為: 1. **系統資源的管理** - 讓使用者可以有良好的體驗(Ex: 不會卡頓) 2. **提供硬體抽象層** (system call & API) - 可以使開發者在進行開發時可以不需知道其硬體邏輯，增加開發效率 3. **多工處理及保護機制** - 可供多個使用者安全地同時操作系統，同時不會發現到彼此的存在 (互不干擾，保護每個user) ## Process和Thread Process: 為正在執行的程式實例，一個Process包含了text、data、bss、heap、stack以及它的內存空間。Process之間互相隔離，不同Process不能直接訪問對方的內存。 Thread: CPU能夠調度的基本單位。多個threads可以共享同一個process的資源。threads的allocation以及context switch都比processe更加節省資源。 - All threads that belong to the same process share the same - <font color="#ff0000">**Code**</font> segment - <font color="#ff0000">**Data**</font> segment (global variable) - <font color="#ff0000">**OS**</font> resources - Linux commands: fork()，execlp()，wait() - But each thread has its own <font color="#ff0000">**thread control block**</font> - <font color="#ff0000">Thread ID</font> - <font color="#ff0000">Program counter</font> - <font color="#ff0000">Register set</font> - <font color="#ff0000">Stack</font> (local variable) - commands: pthread/JAVA libraries, Linux threads(since there is no process concept in Linux) - 執行blocking operation時，Process可能會整個擋住，但multithreading不一定 - 但multithreading要注意synchronization ## 舉例Interprocess communication 由於OS的保護機制，processes之間沒辦法直接進行溝通 - Message Passing: 第一個process把data傳入OS的memory中，第二個process再從OS的memory拿取data - 傳入和讀取OS的memory需要system call - Shared Memory: 多個processes共享同一段memory來進行data交換。 - 需要事先請OS配置記憶體 $\Rightarrow$ system call - 要注意sychronization問題 - Pipes: 一個進程將數據寫入管道，另一個進程讀取。例子：Unix中的管道。 ## Race condition, Deadlock ### Race condition - ==多個processes/threads同時存取操作shared variable，導致shared variable最後的結果會可能會出現預料外的錯誤 (即結果會隨實際的instruction順序決定)== - Critical section: 會操作到shared variable的code segment - 解決方案: - Mutex - Semaphore - Atomic instructions - Monitor :::spoiler Minimum Example ```c= int count = 3; void thread1(void) { count++; return; } void thread2(void) { count--; return; } int main (void) { createThread(thread1); createThread(thread2); return; } ``` 而`count++`的assembly code為 ``` mov ax count add ax 1 mov count ax ``` 若thread1在執行時突然發生context switch: ```bash # thread 1 mov ax count # ax = 3 add ax 1 # ax = 4 # context switch to thread 2 mov bx count # bx = 3 sub ax 1 # bx = 2 mov count bx # count = 2 # context switch to thread 1 moc count ax # count = 4 ``` ::: ### Deadlock - ==多個持有資源的processes在等待彼此的processes釋放資源，導致程式停滯不前== - 造成deadlock的四個條件: 1. Mutual exclusion: 一次只有一個process可以占用資源 2. Hold & wait: Process在持有資源的同時也在等待其他process釋放資源 3. No preemption: Process的資源無法被搶斷 4. Circular wait: 持有且等待資源釋放的關係形成一個閉迴圈 記憶: ==MHCN (魔物獵人中文版)== :::spoiler Minimum Example ```c= pthread_mutex mutex1; pthread_mutex mutex2; void thread1(void) { lock(&mutex1); lock(&mutex2); // critical section unlock(&mutex2); unlock(&mutex1); return; } void thread2(void) { lock(&mutex2); lock(&mutex1); // critical section unlock(&mutex1); unlock(&mutex2); return; } int main (void) { createThread(thread1); createThread(thread2); return; } ``` 若thread1持有mutex1且thread2持有mutex2，deadlock會發生 ::: - 解決方案: **打破deadlock四大必要條件，但是實務上很難辦到** - 目前做法: 找出可能會出現deadlock的情況，並避免它或是回復 - 若每種resource只有一個: Resource-allocation graph algorithm $\Rightarrow$ Cycle detection :::spoiler ![image](https://hackmd.io/_uploads/Hy4PohW8T.png =48%x)![image](https://hackmd.io/_uploads/BkAbEhWUp.png =40%x) - 紫色線代表未來可能會使用這個資源 - 當資源request真的發生，紫色線轉為綠色線並改變方向 - 若出現cycle，代表deadlock發生 ::: - 若每種resource有多個: Banker's algorithm :::spoiler Ex: Available resuorce (A, B, C) = (3, 3, 2) ![image](https://hackmd.io/_uploads/SyVr8-f86.png) 利用目前的allocation、Max allocation以及Available resuorce來檢查是否存在safety allocation sequence。只有當safety allocation sequence存在(這裡存在{P1, P3, P4, P2, P0})，這個allocation request會被批准 ::: - 若deadlock已經發生: - Terminate process: 打破等待cycle - Rollback: 回復上一個動作 ## Mutex, Semaphore, Spinlock, Monitor 四者都為一種同步機制，為了防止race condition發生 ### Mutex - ==屬於pthread library==，為shared variable - 保證了只有一個thread可以進入他的critical section (使用pthread_mutex_lock()和pthread_mutex_unlock()) - 通常會配合condition variable進行thread之間的通信 - wait(&cond, &mutex)會讓thread進入睡眠並釋放mutex，防止busy waiting ### Semaphore - ==屬於POSIX standard API==，為unsigned integer typed shared variable - **==故semaphore可被thread以外的程式存取==** - ==只可經由 **wait()** 和 **signal()** 兩個 **atomic operations** 來存取semaphore== - 故使用上==相比需要依附於thread的mutex有更多自由性== - 相較mutex可以處理更generalize的問題 - Semaphore初始化時可以設大於等於1的數字 - wait()和signal()實作可分為 (**請確保這些實作為atomic!**): - Busy waiting實作 (Spinlock) - Non-busy waiting實作 (Sleep & Wake syscalls) ### Spinlock - 利用==busy waiting==來保護critical section，通常用semaphore實作 - 若semaphore <= 0，則不斷while循環檢查直到有可用的semaphore - ==適合較短critical section的場景==，有速度快的優點 ### Monitor - 為high-level structure，類似C++中class的概念，將shared variables和method封裝以提供開發者更安全的操作 - Java和C#本身就有內建monitor structure - 通常使用mutex和condition variable來實作 - monitor本身確保了同時間只有一個process可以執行 monitor 中的程式碼，其他processes必須在睡眠狀態 - 故==monitor只能進行一個process中的threads的synchronization== - mutex可以進行跨process的threads synchronization - monitor可以保證mutual exclusion，但不能保證沒有deadlock - Overhead會比mutex稍高一些 ## Mutex跟binary semaphore有差別嗎? - 所屬差異: - Mutex: 屬於pthread library - Binary semaphore: 屬於POSIX standard API，但不屬於pthread library - 用途差異: - Mutex: 保護critical section，解決synchronization問題 - Binary semaphore: 除了保護critical section也可以作為事件通知(signaling)作為interprocess同步機制 - 擁有權差異: - Mutex: 操作時必須有對應的thread(上鎖以及釋放) - Binary semaphore: 不需要依附thread也可以直接透過wait()和signal()操作 - 安全性: - Mutex: 皆從pthread library提供的介面操作，安全性較高 - Binary semaphore: Semaphore控制邏輯由開發者自己決定，安全性較低 - 缺點: - Mutex: 有priority inheritance特性，即高priority的thread在睡眠時會保證最少的睡眠時間 $\Rightarrow$ Starvation for low-priority threads - Semaphore: 會有priority inversion的問題 (e.g., Mars pathfinder priority inversion) ## Compile/Load/Run time binding - **Compile time binding**: Object file中symbol table的==symbols為absolute addresses== - 若process的記憶體位址改變了，則需要重新compile - **Load time binding**: Object file中symbol table的==symbols為relocatable addresses== - 若process的記憶體位址改變了，只需要重新load程式，不需要recompile - **Run time binding**: Object file中symbol table的==symbols為virtual addresses== - 連loader在load進memory時也不知道實際的physical address $\Rightarrow$ User和CPU從頭到尾都在處理virtual address - Symbol的physical address一直到run time階段時才會知道，並透過MMU來達成 ## Virtual address, Physical address - Virtual memory: ==**程式和CPU**== 看到的記憶體位址 - Physical memory: 資料在記憶體中的實際位址，只有 ==**OS和存儲單元本身**== 可見 ## Virtual Address如何轉成Physical Address ### Paging - 將memory均勻平分 $\Rightarrow$ Frames - 將Program(virrual memory)均勻平分 $\Rightarrow$ Pages - Physical address為page對應到 Page table的physical address再加上page offset ### Segmentation - 基於program中各個section的大小來區分segments - Physical address為segment對應到 Segmentation table的physical address再加上offset ## What's the advantage of virtual memory? - 隔離：每個process有自己的虛擬地址空間，process間相互隔離，避免了互相影響。 - 擴充記憶體容量：可以執行其記憶體大小比實際物理內存更大的process。 - multiprogramming: 可以讓多個程式同時運作，增加整體系統效率 - 但如果有過多process同時執行，page replacement太過頻繁 $\Rightarrow$ Thrashing - 內存保護：可以防止process越界訪問未分配的內存。 ## Cache, MMU, TLB Cache（快取）: - 為一種儲存單元。它複製了CPU最近所操作的instructions或data。若CPU接下來請求的instruciton或data cache中已經有擁有，則CPU會直接調用cache中的instruction或data MMU（Memory Management Unit）: - CPU要從memory索取資料時需要經過的硬體。將CPU發送的virtual address轉換成physical address，即記憶體的實際位址。通常會配合page table達成 TLB（Translation Lookaside Buffer）: - 是MMU中的一部分，存儲最近使用的virtual address到physical address的映射，用於提高地址轉換的效率。 :::spoiler 圖示 ![image](https://hackmd.io/_uploads/H11MuY7Ia.png) ::: ## Compiler和Linker各自做哪些事情？ Compiler（編譯器）：將高級語言源代碼轉換為低級語言（如匯編或機器代碼），處理語法、語義分析、優化等。 Linker（鏈接器）：將編譯後的目標代碼（.o或.obj文件）與庫文件鏈接成可執行文件，解決外部符號的引用問題，並進行地址重定位。 ## Static linking和dynamic linking的差別 Static Linking（靜態鏈接）: 編譯時將所有代碼和庫打包成一個可執行文件。優點是執行時不需要額外的庫支持，但生成的文件較大，且庫的更新需要重新編譯。 Dynamic Linking（動態鏈接）: 在執行時將庫文件動態地加載進來，這樣可以減少可執行文件的大小，並且庫更新不需要重新編譯。 ## Demand paging 1. CPU想執行virtual memory中的某一個page $\Rightarrow$ 透過MMU和page table得到physical address 2. 若page table沒有對應virtual address的資訊 $\Rightarrow$ Page fault 3. OS收到page fault trap後檢查CPU要的page是否真的存在於disk 4. 若instruciton真的存在在disk，將該page從disk load到memory，並更新page table - 若memory中沒有可用的frame $\Rightarrow$ Page replacement 5. 把program counter回調到執行instruction前 6. 重新執行一次instruction ## 從assembly的角度說明function call和interrupt發生時會有哪些行為 Function Call（函數調用）: 呼叫方將返回地址（即函數調用後要執行的地址）壓入堆疊。 呼叫方將參數傳遞給被調用函數。 跳轉到被調用函數的地址。 被調用函數執行完畢後，通過彈出返回地址並跳回到呼叫方繼續執行。 Interrupt（中斷）: 當中斷發生時，處於執行狀態的程序會被暫停，並將當前狀態（如寄存器、程序計數器）保存在堆疊中。 跳轉到中斷處理程序。 中斷處理完畢後，恢復被中斷程序的狀態，繼續執行。 ## 請詳細說明booting process 1. **初始程序載入** 當機器上電或重啟時，CPU 會從一個預定義的記憶體地址讀取指令。這個地址通常位於 ROM 或固件（Firmware）中，存放著第一段執行的 bootstrap 程式碼。這個步驟確保系統一啟動時便能運行基本的引導程序。 2. **硬體診斷（POST）** 啟動程式會執行一系列硬體診斷程序，稱為電源自檢（POST），用來檢查基本硬體（如 CPU、記憶體、輸入輸出系統等）的狀態和完整性，確保系統在繼續執行前處於正確運作狀態。 3. **讀取 Boot Block** 啟動程式內包含一段代碼，用於從disk上固定位置讀取一個區塊（boot block）。這個區塊通常包含了更多的啟動程式碼或者是完整的啟動加載器（bootloader）的一部分。這個步驟可以看作是一個「鏈式啟動」過程，即最初的程式碼逐步加載更多功能，以便最終能夠加載操作系統。 4. **載入作業系統內核** 一旦完整的啟動加載器被載入並執行，它將遍歷文件系統來定位作業系統的內核，將該內核載入到記憶體中，並將控制權交給它，由作業系統接管後續工作。 --- # C++ What is OOP? 為什麼要設計OO? 什麼是RAII?舉例哪些地方有用到RAII?什麼情況下不適合使用RAII? Pass by value和pass by reference的差別？ Pass pointer to function是pass by value還是pass by reference？ 用delete去釋放malloc出來的東西，以及用free去釋放new出來的東西，會發生什麼事情? const放在class method parameter list後面，const修飾的對象是什麼? ```c class bar { public: void func() const { // do something } }; ``` # 軟韌C考題 ## 什麼是static, extern, volatile, restrict, inline, union, structure? ### static & extern 這兩個存儲類別修飾符決定了變數的生命週期以及其linkage特性 - **extern**: - 被extern修飾的變數具有external linkage(可被其他translation unit引用) - 告知compiler這個變數存在，但不用為它配置記憶體。開發者必須要在其他translation unit對該變數定義，linker才可以正常連結 - 在compile時就已經配置記憶體(data section) - **static**: - 被static修飾的變數具有internal linkage(無法被其他translation unit引用) - 在compile時就已經配置記憶體(data section)，且只會被初始化一次，生命週期始於程式啟動，終於整隻程式結束 - static還可細分成: - **Local static variable**: 只能被該scope中的成員存取。適合讓函式在被反覆呼叫時能夠記住上一次的結果，封裝性比global variable好，不會污染全域命名空間。 - **`.c`檔中的Global static variable/function**: 只能被該檔案中的成員存取。適合用於不作為介面公開給開發者的輔助變數/函數，增加隱蔽性，同時在其他檔案可以有相同名字的變數/函數，避免命名衝突 - **`.h`檔中的Global static variable/function**: ==**極不推薦使用。**== 若`.h`檔中的Global static variable/function被多個translation units include的話，則這些variable/function會在每個translation unit被分配一個獨立且互不相干的副本，出現code bloat的現象 - 例外: **static inline functions**必須實作在`.h`檔中 - ==static變數在C語言中不可宣告在 structure 和 union 中！== ### volatile - 這個修飾詞告訴compiler這個變數的值可能會因為外部因素在意料外的時候改變，故compiler要確保每次讀去這個變數的值時必須直接從記憶體讀取 ### restrict - 這個修飾詞只能用在pointer上。它告訴compiler這個pointer是唯一一個指向該data的pointer，故compiler可以對其進行優化。restrict 並不「自動」檢查或保證唯一性，它僅僅是提供給compiler一個潛在的優化線索，真正是否唯一仍由開發者保證。 ### inline - 這個修飾詞會"建議"compiler在編譯的時侯針對這個function直接展開，省去跳轉的開銷。但是是否展開仍然由compiler決定 - 通常會配合static在header file定義 - 和#define的不同是: - #define必定展開，inline則取決於compiler - #define在preprocessing stage展開，inline則是在compile stage展開(如果compiler要展開的話) ### union - 這個資料結構讓不同型態的資料共用同一塊記憶體空間，以便在某一時刻只保存其中一個成員的值 - ==**但是共用記憶體會有data overwrite的風險**==。詳見 **<a href="https://hackmd.io/lsrtnPlRSwG6ugjix1-Jiw#Union-overwrite" target="_self">Union overwrite</a>** - 適合用於有明確mutual exclusive的情況 - union的大小為最大的union成員的大小，但實際上會受到data alignment影響 ### structure - 這個資料結構將不同型態的資料打包在一起，提高了程式的封裝性和可讀性 - 和union不同的是structure會同時儲存所有成員的值 - structure大小會受到data alignment影響，基本上為data alignment的對齊單位的倍數 ## a++ 和 ++a 熟不熟operator precedence?Prefix/Postfix ++/-- 和dereference一起出現的時候，會發生什麼事情? ```c #include <stdio.h> int main() { char s[] = "0123456"; char *p = s; printf("%c\n",*p++); // ? printf("%c\n",*(p++)); // ? printf("%c\n",(*p)++); // ? printf("%c\n",*++p); // ? printf("%c\n",*(++p)); // ? printf("%c\n",++*p); // ? printf("%c\n",++(*p)); // ? printf("%s\n",s); // ??????? printf("p at [%d]\n", (int)(p - s)); // p at [?] return 0; } ``` 結果: ``` 0 1 2 (s = "0133456") 3 4 5 (s = "0133556") 6 (s = "0133656") 0133656 p at [4] (注意\n) ``` ++a 和 ++a 的assembly code ![image](https://hackmd.io/_uploads/Hk30qx-A1l.png) 回答下列問題: ```c int a = 1; printf("%d\n", a+++++a); printf("%d\n", ++a+++a); printf("%d\n", ++a+a++); printf("%d\n", a+++a++); ``` ::: spoiler 結果(用暫存器層級的角度思考): 1. `a+++++a` - ==先處理a+==+，a的值存到eax暫存器 => mov eax, dword ptr[a] => eax = 1 - 將eax的值加一並把結果存放在edx暫存器 => ==eax = 1==, edx = 2 - 將edx的值送回a，完成a++ => mov dword ptr[a], edx => ==a = 2== - ==處理++a==，a的值存到ecx暫存器 => mov ecx, dword ptr[a] => ecx = 2 - 將ecx的值加一 => add ecx, 1 => ==ecx = 3== - 把ecx的值送回a，完成++a => mov dword ptr[a], ecx => ==a = 3== - 將eax和ecx相加，結果即為`a+++++a` => add eax, ecx => eax = 4 ==**printf結果為4，而a = 3**== 2. `++a+++a` - ==處理左邊的++a==，a的值存到eax暫存器 => mov eax, dword ptr[a] => eax = 3 - 將eax的值加一 => add eax, 1 => ==eax = 4== - 把eax的值送回a，完成++a => mov dword ptr[a], eax => ==a = 4== - ==處理右邊的++a==，a的值存到ecx暫存器 => mov ecx, dword ptr[a] => ecx = 4 - 將ecx的值加一 => add ecx, 1 => ==ecx = 5== - 把ecx的值送回a，完成++a => mov dword ptr[a], eax => ==a = 5== - 將eax和ecx相加，結果即為`++a+++a` => add eax, ecx => eax = 9 ==**printf結果為9，而a = 5** (但是Clang/GCC編譯器下的結果是10)== 3. `++a+a++` - ==先處理a++==，a的值存到eax暫存器 => mov eax, dword ptr[a] => eax = 5 - 將eax的值加一 => add eax, 1 => ==eax = 6== - 將eax的值送回a，完成++a => mov dword ptr[a], eax => ==a = 6== - ==處理a++==，a的值存到ecx暫存器 => mov ecx, dword ptr[a] => ecx = 6 - 將ecx的值加一並把結果存放在edx暫存器 => ==ecx = 6==, edx = 7 - 將edx的值送回a，完成a++ => mov dword ptr[a], edx => ==a = 7== - 將eax和ecx相加，結果即為`++a+a++` => add eax, ecx => eax = 12 ==**printf結果為12，而a = 7** (但是Clang/GCC編譯器下的結果是13)== 4. `a+++a++` - ==處理左邊的a++==，a的值存到eax暫存器 => mov eax, dword ptr[a] => eax = 7 - 將eax的值加一並把結果存放在edx暫存器 => ==eax = 7==, edx = 8 - 將edx的值送回a，完成++a => mov dword ptr[a], edx => ==a = 8== - ==處理右邊的a++==，a的值存到ecx暫存器 => mov eax, dword ptr[a] => ecx = 8 - 將ecx的值加一並把結果存放在edx暫存器 => ==ecx = 8==, edx = 9 - 將edx的值送回a，完成++a => mov dword ptr[a], edx => ==a = 9== - 將eax和ecx相加，結果即為`a+++a++` => add eax, ecx => eax = 15 ==**printf結果為15，而a = 9**== ::: ## 寫一個程式判斷一個系統是little endian還是big endian ```c #include <stdio.h> int main(void) { unsigned int i = 1; char *c = (char *)&i; if (*c == 1) { printf("Little Endian\n"); } else { printf("Big Endian\n"); } return 0; } ``` :::spoiler Little/Big Endian 假設有一個 32 位整數 `int a = 0x12345678`。 Little Endian: ```c 地址： [0] [1] [2] [3] 數值： 0x78 0x56 0x34 0x12 ``` Little endian要特別注意的是若要從記憶體讀取data，則要 ==**從high address往low address來讀取**== ，數值才會正確! Big Endian: ```c 地址： [0] [1] [2] [3] 數值： 0x12 0x34 0x56 0x78 ``` :bulb: 請問: ```clike int a = 0x12345678; short *i = &a; printf("%d", *(int *)(i + 1)); // 假設a以外的地址值都是0 ``` Little endian: `0x00001234` Big endian: `0x56780000` ::: 熟不熟union和struct?什麼是#pragma pack()?struct內同時有不同大小的變數，不同宣告的順序下，一個struct的大小會有什麼變化? ```c #pragma pack(1) typedef struct A_ { int a; char c; double d; }pack_1; #pragma pack(2) typedef struct B_ { int a; char c; double d; }pack_2; #pragma pack(4) typedef struct C_ { int a; char c; double d; }pack_4; #pragma pack(8) typedef struct D_ { int a; char c1; char c2; double d; }pack_8_1; #pragma pack(8) typedef struct E_ { char c1; double d; int a; char c2; }pack_8_2; int main() { printf("%lu\n", sizeof(pack_1)); // ??? printf("%lu\n", sizeof(pack_2)); // ??? printf("%lu\n", sizeof(pack_4)); // ??? printf("%lu\n", sizeof(pack_8_1)); // ??? printf("%lu\n", sizeof(pack_8_2)); // ??? return 0; } ``` 結果: ``` 13 14 16 16 24 ``` ## Auto typecasting ```c #include <stdio.h> #define TOTAL_ELEMENTS (sizeof(array) / sizeof(array[0])) int array[] = {1, 2, 3, 4, 5, 6, 7}; int main(void) { int i; for(i = -1; i <= (TOTAL_ELEMENTS-2); i++) printf("%d\n", array[i+1]); return 0; } ``` 結果: 什麼都沒有 因為: 1. sizeof()的回傳型別為size_t(可能為 uint32_t 或 uint64_t) 2. 當同時針對signed和unsigned變數進行處理時，==**signed變數會自動轉換成unsigned型別！**== 3. 故`i <= (TOTAL_ELEMENTS-2)`事實上會變成`4,294,967,295 <= 5`(如果是32位元電腦)，第一次迴圈條件即不滿足，故輸出什麼都沒有 ## Union overwrite ```c #include <stdio.h> struct A { unsigned short a1; unsigned short a2; unsigned short a3; }; union B { unsigned long long b1; struct A b2; }; int main() { union B uu; printf("%I64u\n", sizeof(uu)); // 8 bytes due to long long uu.b1 = 0xffffffffffffffff; uu.b2.a1 = 0x1234; uu.b2.a2 = 0x5678; uu.b2.a3 = 0xabcd; printf("%I64x\n", uu.b1); // ? *(&(uu.b2.a3) + 1) = 0xeeee; printf("%I64x\n", uu.b1); // ? return 0; } ``` 結果: - For little endian systems: ``` 8 0xffffffffffffffff 0xffffabcd56781234 0xeeeeabcd56781234 ``` ``` Data alignment: low high -- -- -- -- -- -- -- -- ff ff ff ff ff ff ff ff Before overwrite 34 12 78 56 cd ab ff ff After first overwrite 34 12 78 56 cd ab ee ee After second overwrite -- -- -- -- -- -- -- -- ``` - For big endian systems: ``` 8 0xffffffffffffffff 0x12345678abcdffff 0x12345678abcdeeee ``` ``` Data alignment: low high -- -- -- -- -- -- -- -- ff ff ff ff ff ff ff ff Before overwrite 12 34 56 78 ab cd ff ff After first overwrite 12 34 56 78 ab cd ee ee After second overwrite -- -- -- -- -- -- -- -- ``` Array換個type來讀，會發生什麼事情? ```c short arr[] = {0x1111, 0x2222, 0x3333, 0x4444, 0x5555, 0x6666}; int a = ((int*)arr + 1)[1]; // a = 0x? int b = ((int*)(arr + 2))[1]; // b = 0x? int d = ((int*)(arr + 1))[1]; // d = 0x? int c = *(int*)(arr + 3); // c = 0x? int e = (arr + 1)[1]; // e = 0x? int f = *(short*)((int*)arr + 1); // f = 0x? int g = ((short*)((int*)arr + 1))[0]; // g = 0x? int h = ((short*)((int*)arr + 1))[1]; // h = 0x? ``` 結果: ``` Big endian: Little endian: a = 0x55556666 a = 0x66665555 b = 0x55556666 b = 0x66665555 d = 0x44445555 d = 0x55554444 c = 0x44445555 c = 0x55554444 e = 0x3333 e = 0x3333 f = 0x3333 f = 0x3333 g = 0x3333 g = 0x3333 h = 0x4444 h = 0x4444 ``` ## Bitwise操作 怎麼算一個數值的binary有幾個1?交換變數值?字母大小寫轉換? ### Kernighan’s Algorithm: 算one-bit最佳演算法 Time complexity: O(k), k為one-bit數量 ```c int countOne (int a) { int count = 0; while (a != 0) { n &= (n - 1); count++; } } ``` ### Swap ```c void swap (int *a, int *b) { if (a == b) return; // 一定要有這行，否則若a, b位址相同會出錯! *a ^= *b; *b ^= *a; *a ^= *b; } ``` 若用macro實作: ```c #define SWAP_PTR(a, b) \ do { \ if ((a) != (b)) { \ *(a) ^= *(b); \ *(b) ^= *(a); \ *(a) ^= *(b); \ } \ } while (0) ``` 注意do while最後面沒有加分號! ### Uppercase/Lowercase conversion ```c char charCaseConversion (char a) { return ( a ^ (1 << 5) ); } ``` ### Reverse data 將`0x12345678`反轉成`0x87654321` ```c uint32_t reverse32(uint32_t data) { uint32_t r_data = 0; uint32_t mask = 0xF; for (int i = 0; i < 8; i++) { uint32_t masked_data = (data >> (4 * i)) & mask; r_data |= masked_data << ((7 - i) * 4); } return r_data; } ``` 十進位版本(與bit-wise無關): ```c= unsigned int reverseDec(unsigned int data) { unsigned int r_data = 0; while (data != 0) { int remainder = data % 10; r_data = (r_data * 10) + remainder; data /= 10; } return r_data; } ``` ## 用中英文說明複雜的declaration ```c int **p; // 1. p是... int a[10]; // 2. a是... int *p[10]; // 3. p是... int (*p)[10]; // 4. p是... int (*p)(int); // 5. p是... int (*p[10])(int); // 6. p是... ``` 1. p是指標，它指向了一個指向整數的指標 (p is a pointer that points to a pointer that points to an integer) 2. a是長度為10的陣列，陣列裡面都是整數 (a is an array of 10 integers) 3. p是長度為10的陣列，陣列裡面都是指向整數的指標 (p is an array of 10 integer pointers) 4. p是指標，它指向了一個長度為10的陣列，陣列裡面都是整數 (p is a pointer that points to an array of 10 integers) 5. p是指標，它指向了一個函數，這個函數以int作為輸入，以int作為輸出 (p is a pointer that points to a function that takes an integer as input and returns an integer) 6. p是長度為10的陣列，陣列裡面都是指向函數的指標，這些函數以int作為輸入，以int作為輸出 (p is an array of 10 function pointers, each of which takes integer as input and returns an integer) 熟不熟const修飾?哪些相等?哪些pointer本身是const? ```c const int * a; int const * b; int * const c; int const * const d; ``` - \*a是const，a本身可以修改 - \*b是const，b本身可以修改 - c是const pointer，\*c可以修改 - d是const pointer，\*d也不可以修改 ## 各種Singly linked list的操作 insert at head/tail, remove node, reverse linked list, merge two sorted list, find middle element of list。假想自己被問到這些問題，有沒有辦法直接寫出code？有沒有辦法處理corner caes? - [21. Merge Two Sorted Lists](https://hackmd.io/9ro2Og84SXWEmwU3nC8-ig) - [141. Linked List Cycle](https://hackmd.io/BHrrwCWxRiCxJ2bglnj4uQ) - [206. Reverse Linked List](https://hackmd.io/wK5DwHeQRmqy-7Ql72sHVw) - [876. Middle of the Linked List](https://hackmd.io/sVog-NGkT0WFvbdZOuz8Bg) ## MACRO ### Short-circuit evaluation ```c= #include <stdio.h> #define GET_MAX(a, b, mask) (a&mask) > (b&mask) ? (a&mask) : (b&mask) int main() { unsigned short i = 12; unsigned short j = 9; printf("%d\n", GET_MAX(i++,++j, 0x7)); // ? printf("i=%d j=%d\n", i, j); // ? return 0; } ``` 經過define文本替換後，第6行變成: `printf("%d\n", (i++&0x7) > (++j&0x7) ? (i++&0x7) : (++j&0x7));` `(i++&0x7)`的結果是(0d12 & 0x7) = (0b1100 & 0b0111) = 0b0100, i變成13 `(++j&0x7)`的結果是(0d10 & 0x7) = (0b1010 & 0b0111) = 0b0010, j變成10 Condition為true，接下來執行?後面的(i++&0x7) `(i++&0x7)`的結果是(0d13 & 0x7) = (0b1101 & 0b0111) = 0b0101, i變成14 結果: ``` 5 i=14 j=10 ``` :::info - Short-circuit evaluation: - (A && B)假如A已經是false就不會evaluate B - (A || B)假如A已經是true就不會evaluate B - condition ? exprA : exprB，假如condition是true就不會執行 exprB，同理，若condition是false就不會執行 exprA。 - Short-circuit evaluation可能的陷阱: ```c if (1 || f()) { /* do stuff... */ } ``` 這種情況 ==**f 函數不會被執行到！**== - Bit-wise operators (`&, |, ^`) 沒有這個特性 ::: ```c unsigned short i = 12; unsigned short j = 9; #define GET_MAX(a,b) a > b ? a : b printf("%d\n", GET_MAX(i++,++j)); // ?? printf("i=%d j=%d\n", i, j); // i=?? j=?? ``` 結果: ``` 13 i=14 j=10 ``` 找質數寫出來並分析時間、空間複雜度。 Sieve of Eratosthenes演算法: ```c int *findPrimes(int n) { int *table = (int *)malloc(sizeof(int) * (n + 1)); table[0] = 0, table[1] = 0; for (int i = 2; i <= n; i++) table[i] = 1; for (int i = 2; i * i <= n; i++) { if (table[i]) { for (int p = i * i; p <= n; p += i) { table[p] = 0; } } } return table; } int main() { int n = 100; int *primes = findPrimes(n); printf("["); for (int i = 0; i < n; i++) { if (primes[i]) printf ("%d, ", i); } printf("\b\b]\n"); return 0; } ``` Time complexity: $O(n\log \log n)$ Space complexity: $O(n)$ Fibonacci：用Loop和Recursion實作；怎麼不用loop讓Fibonacci數列無窮的印下去？ Recursion: ```c int Fibonacci (int n) { if (n <= 0) { return 0; } else if (n == 1) { return 1; } return Fibonacci(n - 1) + Fibonacci(n - 2); } int main (void) { int terms = 10; printf("%d", Fibonacci(terms)); return 0; } ``` Recursive的方式為一棵binary tree: ``` F(10) / \ F(9) F(8) / \ / \ F(8) F(7) F(7) F(6) ... ... ... ... ``` Time complexity: O($2^n$) Space complexity O(n): tree 的深度 Loop: ```c int Fibonacci (int n) { int acc = 1, temp = 0; if (n <= 0) return 0; printf("%d\n", acc); for (int i = 1; i < n; i++) { acc += temp; temp = acc - temp; printf("%d\n", acc); } return acc; } int main (void) { int terms = 10; printf("%d", Fibonacci(terms)); return 0; } ``` Time complexity: O(n) Space complexity O(1) Infinite print ```c void Fibonacci (unsigned long long a, unsigned long long b) { printf("%llu\n", b); sleep(1); Fibonacci(b, a + b); return; } int main (void) { Fibonacci(0, 1); return 0; } ``` # 計算機組織 ## 解釋pipeline 每條指令必須完成所有步驟後，才能開始下一條，導致處理器許多硬體單元閒置，浪費週期。 Pipeline將指令執行過程切分為若干階段，不同指令可同時在不同階段並行工作，大幅提升資源利用率與整體指令吞吐量。 現代簡化 RISC 處理器常見的五個階段如下： 1. **IF** (Instruction Fetch)：取指令 2. **ID** (Instruction Decode & Register Fetch)：解碼並讀取暫存器 3. **EX** (Execute / Address Calculation)：執行運算或計算記憶體位址 4. **MEM** (Memory Access)：存取資料記憶體 5. **WB** (Write Back)：將結果寫回暫存器 但是pipeline可能會出現hazard: 1. 結構冒險（Structural Hazard） - 原因：不同指令同時競爭同一硬體資源（例如單一記憶體埠或單一 ALU）。 - 解法：增設多組單位（多埠記憶體、額外 ALU），或在調度時插入停頓。 2. 資料冒險（Data Hazard） - RAW（Read After Write）：後一指令讀取暫存器資料，但前一指令尚未寫回。 - WAR、WAW：在 in‑order pipeline 中較罕見，多出現在亂序執行。 - 解法： - Forwarding（旁路）：直接把 EX/MEM 或 MEM/WB 階段的結果轉送到 ID/EX 階段所需輸入。 - Stall（停頓）：在 ID 階段插入 NOP，直到資料可用為止。 3. 控制冒險（Control Hazard / Branch Hazard） - 原因：分支指令需決定跳轉方向及目標，若延遲太久，後續指令流水線必須停頓或取錯指令。 - 解法： - 靜態分支預測：例如「always not taken」或依指令型別預測。 - 動態分支預測：使用歷史資訊（1-bit、2-bit 分支預測器、分支目標緩衝器 BTB）。 - 延遲分支（Delayed Branch）：編譯器填入可無害執行的指令於分支後面。