NYCU [CSIC30015] Operating System Assignments reports

# NYCU [CSIC30015] Operating System by Prof. [Chun-Feng Wu](https://cfwu417.github.io/) # Assignment I - Compiling a Custom Linux Kernel & Implementing New System Calls ### I. Compiling a custom Linux Kernel  1. 首先確認好環境後，要設置RISC-V的架構，所以我們會需要先Set architecture and cross-compiler。 ```bash= echo 'export ARCH=riscv' >> ~/.bashrc echo 'export CROSS_COMPILE=riscv64-linux-gnu-' >> ~/.bashrc source ~/.bashrc ``` 2. 接下來就是設定Kernel，生成一份基準`.config`（只要做一次） ```bash= make defconfig ``` 3. 並利用`menuconfig`GUI設定工具，可以用它來修改一些 kernel 選項，並進入設定中的Local version更改版本成(`-os-student_ID`)，並把`Automatically append version...`的選項取消後，並存為.config後離開。(可以去`CONFIG_LOCALVERSION`檢查是否已有更改) ```bash= make menuconfig # General setup ---> # ( ) Local version - append to kernel release # [*] Automatically append version information to the version string ``` 4. 最後去查看Kernel的版本 ```bash= make kernelrelease ``` This will output something like: ``` -os-31455xxxx ``` >若是遇到suffix會加上奇怪的東西或是+號，可以用`echo "" > .scmversionc`後重新make kernelrelease即可解決。 > >會出現這個是因為 repo 在 Git 管理下沒有.scmversion，setlocalversion 會去跑了 git describe來幫你處理，然後當你執行 make kernelrelease後，內部會呼叫 scripts/setlocalversion 來幫你決定版本字尾，而.scmversion這個file會幫你跳過git和其他部分（priority : .scmversion > CONFIG_LOCALVERSION > CONFIG_LOCALVERSION_AUTO(Git 狀態)），並決定版本尾號要加什麼，啊這邊就加入空字串，讓他保持乾淨。 5.接下來就是去編譯kernel，並利用CPU可用核心數來進行平行編譯，最後成功後應該會能在`~/linux/arch/riscv/boot/Image`中看到輸出的Image ```bash= make -j$(nproc) ``` 6.因為Docker上跑的是X86的架構，所以無法直接跑在RISC_V Kernel，所以我們會需要QEMU來幫我們做模擬，讓我們可以Cross Compile，同時並透由docker cp來將所需要的`initramfs.cpio.gz`的root filesystem放在一起後執行： ```bash= qemu-system-riscv64 -nographic -machine virt \ -kernel linux/arch/riscv/boot/Image \ -initrd ./initramfs.cpio.gz \ -append "console=ttyS0 loglevel=3" ``` 7. 最後執行成功後會進入shell prompt之中，就可以使用uname -a 和 cat /proc/version來確認已經完成編譯好kernel了，結果應該如下： ![截圖 2025-09-28 15.43.03](https://hackmd.io/_uploads/SkBMvw82gl.png) ### Q&A: #### Q: What are the main differences between the RISC-V and x86 architectures? **ANS:** RISC-V 是一種精簡指令集（RISC）架構，指令格式統一、執行管線化容易、硬體實作簡單。 x86 則是複雜指令集（CISC）架構，指令長度不固定、支援許多歷史相容的複雜指令，硬體解碼與排程邏輯較複雜。 #### Q: Why do the architecture differences matter when building the kernel? What happens if you build the kernel without the correct RISC-V cross-compilation flag? **ANS:** 因為 Kernel 會根據目標架構產生不同的啟動程式、暫存器介面、系統呼叫表、記憶體管理模式。如果沒設`ARCH=riscv, CROSS_COMPILE=riscv64-linux-gnu-`Kernel 會被編成 x86 或其他架構版本，QEMU（riscv64）中無法開機，會直接卡住或顯示 illegal instruction。 #### Q: Why is Docker used in this assignment, and what advantages does it provide? Please list at least two of them. **ANS:** 1.提供一致且可重現的開發環境：所有人都使用相同的 compiler、QEMU、依賴套件版本，避免「我這環境可以跑彈你那環境做一樣的設置卻不行跑」的問題。 2.隔離宿主系統，避免污染或衝突：不會把 RISC-V 工具鏈、交叉編譯器或依賴套件裝到自己的 Ubuntu / macOS 裡。 3.方便複製與重啟：容器隨時可停止/刪除/重建，不怕配置錯誤。 ___ ### II. Implementing new System Calls 1. 首先宣告一下要加入的syscall, 在`include/linux/syscalls.h` 末尾附近加入： ```c= asmlinkage long sys_revstr(char __user *str, size_t n); asmlinkage long sys_tempbuf(int mode, void __user *data, size_t size); ``` 2. 並且在`include/uapi/asm-generic/unistd.h`的通用syscall table之中依照number加入新的syscall。 ```c= #define __NR_revstr 451 __SYSCALL(__NR_revstr, sys_revstr) #define __NR_tempbuf 452 __SYSCALL(__NR_tempbuf, sys_tempbuf) #undef __NR_syscalls // last one syscall number + 1 #define __NR_syscalls 453 ``` 3. 接下來就是實作 revstr_syscall.c，並放在linux/kernel/revstr_syscall.c。 This system call follows the standard copy-in / process / copy-out pattern used in the Linux kernel. Because the kernel cannot access user memory directly, it first allocates two kernel buffers (kbuf and revbuf), copies the string from user space, then reverses the content in a separate buffer, and finally copies the result back to user space. pr_info is used to log both the original and reversed string to the kernel ring buffer (dmesg). Memory is always freed before returning, and proper error codes (-ENOMEM, -EFAULT) are used for robustness. ```c= #include <linux/kernel.h> #include <linux/syscalls.h> #include <linux/uaccess.h> #include <linux/slab.h> SYSCALL_DEFINE2(revstr, char __user *, str, size_t, n) { char *kbuf, *revbuf; size_t i; kbuf = kmalloc(n + 1, GFP_KERNEL); if(!kbuf) return -ENOMEM; revbuf = kmalloc(n + 1, GFP_KERNEL); if(!revbuf) { kfree(kbuf); return -ENOMEM; } if(copy_from_user(kbuf, str, n)){ kfree(kbuf); kfree(revbuf); return -EFAULT; } kbuf[n] = '\0'; pr_info("The origin string = %s\n", kbuf); for(i = 0; i < n; i++) revbuf[i] = kbuf[n - i - 1]; revbuf[n] = '\0'; pr_info("The reversed string = %s\n", revbuf); if(copy_to_user(str, revbuf, n + 1)){ kfree(kbuf); kfree(revbuf); return -EFAULT; } kfree(kbuf); kfree(revbuf); return 0; } ``` 4. 接下來就是實作 revstr_syscall.c，並放在linux/kernel/revstr_syscall.c。 This system call keeps a persistent list of strings inside the kernel using the Linux list_head linked list structure. Each record is stored as a temp_node containing the string pointer and its length. - ADD mode: copy_from_user() transfers the user string into kernel memory. A new temp_node is allocated with kmalloc() and appended to the list using list_add_tail(). - REMOVE mode: The list is scanned using list_for_each_entry_safe(). If a matching string is found, it is removed with list_del() and its memory is freed. - PRINT mode: All stored records are concatenated into a kernel buffer separated by spaces, Logged with pr_info(), then copied back to the user buffer using copy_to_user(). All modifications to the list are protected using a spinlock, ensuring that concurrent system calls do not corrupt the list. In summary, the design follows copy-in → manage in kernel → copy-out with proper memory management and synchronization ```c= #include <linux/kernel.h> #include <linux/syscalls.h> #include <linux/uaccess.h> #include <linux/slab.h> #include <linux/list.h> #include <linux/spinlock.h> enum mode { PRINT = 0, ADD = 1, REMOVE = 2 }; struct temp_node { struct list_head link; char *s; size_t len; }; static LIST_HEAD(temp_list); static DEFINE_SPINLOCK(temp_lock); static int do_add_from_user(const void __user *data, size_t size) { struct temp_node *node; char *buf; if (!data || size == 0) return -EFAULT; buf = kmalloc(size + 1, GFP_KERNEL); if (!buf) return -ENOMEM; if (copy_from_user(buf, data, size)) { kfree(buf); return -EFAULT; } buf[size] = '\0'; node = kmalloc(sizeof(*node), GFP_KERNEL); if (!node) { kfree(buf); return -ENOMEM; } node->s = buf; node->len = size; spin_lock(&temp_lock); list_add_tail(&node->link, &temp_list); spin_unlock(&temp_lock); pr_info("[tempbuf] Added: %s\n", buf); return 0; } static int do_remove_match_user(const void __user *data, size_t size) { struct temp_node *pos, *n; char *key; if (!data || size == 0) return -EFAULT; key = kmalloc(size, GFP_KERNEL); if (!key) return -ENOMEM; if (copy_from_user(key, data, size)) { kfree(key); return -EFAULT; } spin_lock(&temp_lock); list_for_each_entry_safe(pos, n, &temp_list, link) { if (pos->len == size && !memcmp(pos->s, key, size)) { list_del(&pos->link); spin_unlock(&temp_lock); pr_info("[tempbuf] Removed: %.*s\n", (int)size, pos->s); kfree(pos->s); kfree(pos); kfree(key); return 0; } } spin_unlock(&temp_lock); kfree(key); return -ENOENT; } static ssize_t do_print_to_user(void __user *ubuf, size_t usize) { ssize_t written = 0; size_t need_space = 0; struct temp_node *pos; char *kbuf, *p; if (!ubuf || usize == 0) return -EFAULT; if (usize > 512) usize = 512; kbuf = kzalloc(usize, GFP_KERNEL); if (!kbuf) return -ENOMEM; p = kbuf; spin_lock(&temp_lock); list_for_each_entry(pos, &temp_list, link) { size_t add = pos->len + (need_space ? 1 : 0); if (written + add >= usize) break; if (need_space) { *p++ = ' '; written += 1; } memcpy(p, pos->s, pos->len); p += pos->len; written += pos->len; need_space = 1; } spin_unlock(&temp_lock); pr_info("[tempbuf] %s\n", kbuf); if (copy_to_user(ubuf, kbuf, written)) { kfree(kbuf); return -EFAULT; } kfree(kbuf); return written; } SYSCALL_DEFINE3(tempbuf, int, mode, void __user *, data, size_t, size) { switch (mode) { case ADD: return do_add_from_user(data, size); case REMOVE: return do_remove_match_user(data, size); case PRINT: return do_print_to_user(data, size); default: return -EINVAL; } } ``` 5.最後為了make kernel時能夠被編譯，在kernel/Makefile 末尾加： ```c= obj-y += revstr_syscall.o obj-y += tempbuf_syscall.o ``` 6.最後重新編譯kernel ```bash= make -j$(nproc) ``` 7.接下來利用riscv來編譯好TA給的兩個測試檔並把他們打包進initramfs.cpio.gz後進入QEMU，即可得到下面的結果。 ![截圖 2025-10-13 14.46.26](https://hackmd.io/_uploads/HyrgbQ5peg.png) ### Q&A: #### Q:What does the include/linux/syscalls.h do? **ANS:** 用來**宣告所有系統呼叫原型(sys_*)** 函式的標頭檔，能夠提供統一的函式宣告，確保不同架構（X86、ARM64、RISC-V 等）在編譯時都能找到正確的 sys_xxx()，同時也配合 `SYSCALL_DEFINE*` 巨集展開，讓系統呼叫能自動生成對應的 stub； #### Q:Explain the difference between a system call and a glibc library call, then give one example that maps a glibc function to the specific system call it ultimately invokes. **ANS:** System call 是使用者程式透過 CPU 指令（如 RISC-V 的 ecall）陷入 kernel，要求核心執行特權操作，例如讀寫檔案或建立行程。 glibc 函式呼叫則是使用者空間的包裝函式，有些會呼叫 system call，有些只是單純做格式處理或快取。 e.g. ```C= write(1, "Hello", 5); // glibc 函式 syscall(SYS_write, 1, "Hello", 5); // 實際進入系統呼叫 sys_write ``` #### Q:Explain the difference between static linking and dynamic linking **ANS:** 靜態連結是把所需要的函式庫在編譯時直接打包進執行檔，因此執行時不需要依賴外部的 .so 檔。好處是執行檔可獨立運行、不依賴環境，缺點是檔案較大。動態連結則在執行時由動態載入器（如 /lib/ld-linux-riscv64.so.1）載入共享函式庫。好處是節省空間、能共用記憶體，但若環境中缺少函式庫就會無法執行。 #### Q:In this assignment environment, why do we have to compile the test programs with the -static flag? What would happen if we omitted it? **ANS:** 因為QEMU 裡沒有 glibc 或動態載入器（dynamic loader）可以讓 ELF 程式載入共享函式庫，若是動態執行可能會出現以下： ```bash= -sh: ./test_tempbuf: not found // or error while loading shared libraries: libc.so.6: cannot open shared object file ``` 而加上-static，編譯器會把：glibc / syscall wrapper / C runtime（CRT）等等全部打包進一個獨立的 ELF 檔裡，這樣執行時就不需要 /lib 或 loader。 ### III.Patch - 產生 patch ```bash= cd linux git add -A git commit -m "Add sys_revstr and sys_tempbuf syscalls" git format-patch -n -o ~/HW1_314553040/ ``` - 匯出 kernel config ```bash= cp .config /home/ubuntu/HW1_<studentID>/ ``` #### Reference - https://dev.to/jasper/adding-a-system-call-to-the-linux-kernel-5-8-1-in-ubuntu-20-04-lts-2ga8 # Assignment II - Scheduling Policy Demonstration Program #### Describe how you implemented the program in detail. (10%) 我先用 `getopt` 解析四個參數：`-n` 決定要建立幾個執行緒、`-t` 決定每一輪忙等的秒數、`-s` 讀取每個執行緒的排程政策（以逗號分隔的 `NORMAL` 或 `FIFO`）、`-p` 讀取對應的即時優先序（`NORMAL` 用 `-1` ）。接著把整個行程和等一下要建立的所有執行緒都綁到 CPU0，目的是在單一顆 CPU 上觀察排程，不讓多核心並行或執行緒遷移把結果攪亂。為了讓大家在同一時間「同點起跑」，我建立一個 `pthread_barrier_t`，所有 worker 在開始前都先 `pthread_barrier_wait`，等人數到齊才一起放行。建立執行緒時，我用 `pthread_attr_setinheritsched(&attr, PTHREAD_EXPLICIT_SCHED)` 強制採用我指定的屬性，然後依 `-s/-p` 設定 `SCHED_OTHER` 或 `SCHED_FIFO`，其中 FIFO 的 `sched_priority` 會夾在 1~99 之間；`SCHED_OTHER` 的 `sched_priority` 依 POSIX 規範是 0。每個 worker 的主體是固定的三圈迴圈：印出 `Thread <id> is running`，`fflush(stdout)` 讓輸出立刻寫出，然後進入忙等函式等 `t` 秒。整體收尾就是 `pthread_join` 全部執行緒、銷毀 barrier、釋放配置的記憶體。這個實作刻意把變因壓到最低：同核、同時起跑、固定輸出格式，讓輸出順序主要反映出排程類別與優先序的差異。 #### Describe the results of ./sched_demo -n 3 -t 1.0 -s NORMAL,FIFO,FIFO -p -1,10,30 and what causes that. (10%) 這個案例有一個 `NORMAL` 和兩個 `FIFO`，而且兩個 FIFO 的優先序是 30 與 10。實際輸出會先看到優先序 30 的 FIFO 連續印三行，接著是優先序 10 的 FIFO 連續三行，最後才輪到 `NORMAL` 的那個執行緒把三行印完。原因是 Linux 的排程是分「類別階層」的：同一顆 CPU 上，只要即時類（`SCHED_FIFO/SCHED_RR`）有人可跑，就不會輪到一般類（`SCHED_NORMAL(CFS)`）。而在 FIFO 類裡又是完全看優先序且沒有time slicing，高優先序會一直佔著 CPU，除非被更高優先序搶走、自己阻塞、或主動讓出。我的程式不會阻塞也不會 `sched_yield`，所以會出現兩個 FIFO 依優先序各跑完三圈，最後才換 `NORMAL`。另外，我的忙等是用「Threads CPU time」計時（`CLOCK_THREAD_CPUTIME_ID`），被搶佔的期間不會前進，所以 `NORMAL` 的等候不會偷算進去，這更凸顯了 FIFO 的壓制效果。 #### Describe the results of ./sched_demo -n 4 -t 0.5 -s NORMAL,FIFO,NORMAL,FIFO -p -1,10,-1,30, and what causes that. (10%) 這個案例有兩個 `FIFO`（優先序 30 與 10）以及兩個 `NORMAL`。輸出會先是優先序 30 的 FIFO 連續三行，再來優先序 10 的 FIFO 連續三行；等到兩個 FIFO 都做完，系統中只剩下一般類，`SCHED_NORMAL` 的兩個執行緒就由 CFS 公平地分時，所以最後會看到兩個 `NORMAL` 的輸出交替出現，直到各自完成三行。誰先交替到誰不保證，但長期會平均。這個行為完全符合排程類別階層（RT 高於 CFS）與 FIFO 的「沒有time slicing、看優先序」的性質。如果系統的 RT 節流（`kernel.sched_rt_runtime_us`）沒有關閉，理論上 FIFO 可能在一個 period 內用完 RT 配額而被暫時throttle，這樣 `NORMAL` 也可能穿插在前半段，但在我把節流關掉或把 `runtime == period` 的設定下，就會是「兩個 FIFO 先跑完，兩個 NORMAL 最後交替」的乾淨狀況。 #### Describe how did you implement n-second-busy-waiting? (10%) 我不是用 `sleep()` 或 `nanosleep()`，因為那會把執行緒丟回睡眠狀態，完全偏離「Busy Waiting」的概念；而且那會以elapsed real time計算，包含被搶佔的空檔。我的作法是每個 worker 進入Busy Waiting函式時先讀一次 `clock_gettime(CLOCK_THREAD_CPUTIME_ID, &t0)`，之後在一個小迴圈裡做一點點無用處的東西（用 `volatile` 防止被最佳化拿掉），每迴圈讀一次 `CLOCK_THREAD_CPUTIME_ID` 計算「這個執行緒已經實際執行了多久」。只要累積的執行緒 CPU 時間還沒到目標秒數就持續空轉；一旦達標就離開。這種作法有兩個好處：第一，被更高優先序搶走 CPU 的期間不會被計入忙等秒數，觀察結果更純粹；第二，不需要額外的同步或睡眠呼叫，不會改變可執行狀態，排程器可以如實對這個執行緒做搶佔與選擇。 #### What does the kernel.sched_rt_runtime_us effect? If this setting is changed (eg. 500000, 950000, 1000000), what will happen?(10%) 這個參數搭配 `kernel.sched_rt_period_us`（通常是 1,000,000 微秒，也就是 1 秒）一起使用，用來限制同一顆 CPU 上「即時類」（FIFO/RR）在每個 period 裡最多能佔用多少 CPU 時間。系統預設常見是 `runtime_us = 950000`，意思是每秒內即時執行緒最多可以用到 0.95 秒，剩下 0.05 秒保留給一般類（CFS），避免整台機器被即時執行緒餓死。如果把 `runtime_us` 設為 `500000`，那在我的示範程式中，FIFO 會跑到配額用完後被Throttle，CFS 的 `NORMAL` 就會穿插在中間執行；設成 `950000`，CFS 偶爾可以插進來，但大多時候仍被 FIFO 壓著；設為 `1000000`（等於 period）幾乎等於不Throttle，在每秒內 FIFO 能一直佔著 CPU，只會在自己結束或被更高優先序 RT 搶走時才讓位；如果直接設為 `-1` 則是完全關閉Throttle，效果最接近教材上對 FIFO 的理想討論。因為這個機制會直接影響到系統服務是否還有機會跑，實務上只建議在受控的實驗環境（像我這次的 QEMU 系統）才把節流拉高或關閉，測完再恢復預設，避免把主機弄到沒反應。 ##### Reference: - https://www.kernel.org/doc/Documentation/scheduler/sched-rt-group.txt - https://stackoverflow.com/questions/64962044/testing-impact-of-kernel-sched-rt-runtime-us-in-linux-4-18-20 - https://jasonblog.github.io/note/linux_kernel/ff08_wu_ff09_ff1a_xia_ban_bu_ji_zhi_zhi_gong_zuo_d.html >[name=Cheng-En Dong][time=Mon, Nov 10, 2025 8:31 PM][color=#931984]

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.