### Lab0 4 問題
> Linux 核心的 include/linux/list.h 裡頭實作的鏈結串列將結構體 list_head 嵌入到所需的結構體中，該用什麼巨集來得知鏈結串列**個別節點**的地址呢？
[Linux 核心原始程式碼巨集: container_of](https://hackmd.io/@sysprog/linux-macro-containerof)
> 考慮以下程式碼: char s[64]; 試問 s == &s 是否成立？搭配〈你所不知道的 C 語言：指標篇〉的描述，佐以 C 語言歸來解釋
Except when it is the operand of the sizeof operator or the unary & operator, or is a string literal used to initialize an array, an expression that has type ‘‘array of type’’ is converted to an expression with type ‘‘pointer to type’’ that points to the initial element of the array object and is not an lvalue. (C99 6.3.2.1)
Two pointers compare equal if and only if both are null pointers, both are pointers to the same object (including a pointer to an object and a subobject at its beginning) or function (C99 6.5.9)
> 參照「Linux 核心設計: 作業系統術語及概念」，在 Linux 核心哪個系統呼叫可建立 process 和 thread？
[UNIX 作業系統 fork/exec 系統呼叫的前世今生](https://hackmd.io/@sysprog/unix-fork-exec)
fork 的思想最終被 Linux 所繼承和發揚光大，一切又回歸到 Conway 在 1963 年提出的論文，並行多處理，終於在 Linux 的 ___ 系統呼叫得到落實:
> 參照「Linux 核心設計: 作業系統術語及概念」，Linux 核心發展的過程中多次向 Plan 9 借鏡，Linux 將 process 資訊當作檔案一般處理的機制稱為什麼？
[Linux 核心設計: 作業系統術語及概念](https://hackmd.io/@sysprog/linux-concepts)
Torvalds 不僅不孤單，藉由網際網路的協作，
締造出世界上最成功的開放原始碼專案，過程中好似「卡比」，
從其他作業系統「吸入」若干獨到能力，整理如下：
虛擬記憶體管理 (virtual memory management 或 MM)：
procfs:
TCP/IP
BPF (Berkeley Packet Filter):
9p:
lxc
### quiz_w1
[Optimized QuickSort — C Implementation (Non-Recursive)](https://alienryderflex.com/quicksort/)
> 2. STACK
> My implementation does not use the stack to store data. **Recursive** functions look neat and simple in part because they don’t have to have big arrays like my beg[] and end[]. But all they’re really doing is **using the stack as their own private array**. This is **much slower than** using a **real array**, and **could cause stack overflow on some systems**, crashing the app that called the quicksort. My implementation simply returns NO if this kind of failure occurs
# HW4
1. 在〈從 Revolution OS 看作業系統生態變化〉提及 Apple Safari 和 Google Chrome 網頁瀏覽器可追溯到最初程式碼的源頭是 KDE 計畫旗下的哪個子專案？
* [KHTML](https://www.youtube.com/watch?v=gPyrzvI7Mlc&t=4000s)
A: khtml
2. 考慮浮點數加法運算程式 float sum(float* val_arr, int nval) { float acc = 0.0f; for (int i = 0; i < nval; i++) acc += val_arr[i]; return acc; } 當第一個參數傳入 {1.0f, 2.0f, 3.0f, ..., 10000.0f } 所在的位址，第二個參數傳入 10000，該程式計算會得到較「梯形公式計算連續數值的總和」小的浮點數，試問該如何修正方可提高精確度？這手法稱為什麼？
* [Kahan](https://en.wikipedia.org/wiki/Kahan_summation_algorithm)
- A: Kahan summation algorithm
3. 在「並行程式設計: 排程器原理」提及可在使用者層級做到搶佔式的 coroutine，這需要 Linux 提供什麼機制？用英語簡述實作手法，以及為了達成搶佔特性，你該如何調整？？
A: To implement preemptive coroutines at the user level in Linux, the required mechanism provided by Linux involves using operating system **timer** interrupts which we use signals, specifically the SIGALRM signal, to simulate.
A: int x(int i, int k) { return (i < k && putchar(i + '0') && !x(i+1,k) || putchar(i + '0'); }
4. 已知 int x(int i, int k) { return (i < k && putchar(i + '0') && COND || putchar(i + '0'); } 在 x(1,3); printf("\n"); 使用情境會得到 12321 字串輸出，請補完 COND 敘述，使該程式運作符合預期。用最精簡的形式書寫程式碼，不要提交空白字元。
[案例分析：數列輸出](https://hackmd.io/@sysprog/c-prog/%2Fs%2FrJ8BOjGGl#%E6%A1%88%E4%BE%8B%E5%88%86%E6%9E%90%EF%BC%9A%E6%95%B8%E5%88%97%E8%BC%B8%E5%87%BA) A:
```c
int x(int i, int k) { return (i < k && putchar(i + '0') && !x(i+1,k)) || putchar(i + '0');
```
> 發現一定要讓左側為 0, 故使用 and 0 但是轉念一想, 既然是刻意要讓他錯誤, 為何不直接在遞迴程式前放 not 就好, 如此一來就會一直根據往上加的 i 執行 putchar(i + '0'), 直到 i+1 的值 !< k ,
由於 `or` 的左側都是否定, 所以接著就遞迴觸發各階層的 `or` 右側.
my:
```c
int x(int i, int k) { return (i < k && putchar(i + '0') && x(i+1,k)&&0) || putchar(i + '0');
```
5. 〈Linux 核心的紅黑樹〉提到 Linux 核心對於紅黑樹節點的定義是 struct rb_node { unsigned long __rb_parent_color; struct rb_node *rb_right; struct rb_node *rb_left; } __attribute__((aligned(sizeof(long)))); 也就是親代節點跟顏色一起宣告在 unsigned long 型態的結構體成員中，搭配 x86-64 ABI 規格，用英語解釋其運作原理。
[Linux 核心的紅黑樹](https://hackmd.io/@sysprog/linux-rbtree#%E7%B4%85%E9%BB%91%E6%A8%B9%E7%AF%80%E9%BB%9E)
A:
In the Linux kernel, the definition of a red-black tree node is structured such that the parent node pointer and color information are cleverly combined within a single unsigned long member named __rb_parent_color. This design exploits the characteristics of the x86-64 ABI specification, which defines how data is structured in memory and how functions interact at the binary level on x86-64 systems. By aligning the structure with the size of a long data type, typically 64 bits on x86-64 systems, the attribute((aligned(sizeof(long)))) directive ensures that the structure is aligned with the platform's memory layout requirements. This alignment is crucial for efficient memory access and proper interpretation of the parent pointer and color information stored within the __rb_parent_color member. The least significant bits of the unsigned long member are utilized to store the color information of the node, while the remaining bits store the pointer to the parent node. This design optimizes memory usage by reducing the memory footprint of each node and enables efficient operations on red-black trees within the Linux kernel, such as insertion, deletion, and traversal.
5. [<你所不知道的 C 語言：編譯器和最佳化原理篇>](https://hackmd.io/@sysprog/c-compiler-optimization)舉一段程式碼:
int main() { int a = 11, b = 13, c = 5566; int i, result; for (i = 0; i < 10000; i++) result = (a * b + i) / (a * c); return result; } 現在的編譯器最佳化可**消弭**原本的**迴圈和乘法、加法，和除法**等運算，最終得到非常簡潔的機械碼？是因為施加哪些一系列最佳化手法？請用英語回答。
:::info
最佳化來自對系統的認知
:::
```c
int main() {
int a = 11, b = 13, c = 5566;
int i, result;
for (i = 0; i < 10000; i++)
result = (a * b + i) / (a * c);
return result;
}
```
A:
The compiler's optimization techniques that can eliminate the loop and arithmetic operations by following optimization passes:
Constant Folding/ Constant Propagation: The compiler evaluates constant expressions at compile time. In this case, if a, b, and c are known at compile time, the expression (a * b) and (a * c) could be computed at compile time, reducing the number of runtime computations.
Loop Unrolling: The compiler may unroll the loop, which means it will generate multiple copies of the loop body in sequence, reducing the overhead of loop control instructions.
Integer mod optimization: The compiler may replace costly operations with less expensive ones. For instance, multiplication operations might be replaced with shift operations if the multiplicand is a power of 2.
Dead Code Elimination: If the result of the loop is not used outside of the loop, the compiler may eliminate the loop entirely, as well as any computations that are not needed.
By applying these and possibly other optimization techniques, the compiler can generate highly optimized machine code that efficiently computes the desired result without the need for explicit loops or arithmetic operations.
Sign in with Wallet
Connect another wallet