期中考檢討 助教:鄧執中 實驗室:720A

1.(15%) 說明Linux有哪些Scheduling Policy以及不同的Policy的用途。 4-82. SCHED_FIFO：為 real-time scheduling policy，提供 First-in, first- out 的排程演算法。當一個 Process 在 FIFO 模式下，在 Kernel 的排程器 設為可運行時，將會立即先佔並插隊執行，比同樣系統優先權的其他一般 Process 還優先，除非還有系統優先權更高的 Process 正在佔用時間，否 則 FIFO Process 通常會優先佔用。FIFO Process若是使用sched_yield() 或是遭暫停而讓出CPU時間，將會被重新排在當時同優先權的最後，等待 其他同優先權的 Process 完畢後，再度被運行。所以SCHED_FIFO ，永遠 會有最大的機會被先執行。 SCHED_RR：為 real-time scheduling policy。被設定為 SCHED_RR 的 Process，基本上排程行為和 SCHED_FIFO 一樣，不同的是 Process 將被 Kernel 分配一個 timeslice 去限制時間，時間一但用盡，將會被暫停以讓 出 CPU。 SCHED_NORMAL：為普通的 Process 的預設排程，非 real-time scheduling policy。

2.(24%) 說明下圖8條狀態轉移路徑的過程。

(12%) 一個Process有下列的執行過程，說明各步驟分別是在User Space或Kernel Space。 Creation and Termination (Kernel Space) 兩個動作皆是以調用system code來完成 3-19: When a program executes a system call or triggers an exception, it enters kernel-space Executing user code (User Space) Invoking a system call (kernel-space) Handling an interrupt (kernel-space) 1-13: In kernel-space, in interrupt context, not associated with a process, handling an interrupt

4.(8%) 說明Linux Process的Sleeping與Waking Up的過程。 Whatever the case, the kernel behavior is the same 1.The task marks itself as sleeping: 標記自身為sleeping 2.Puts itself on a wait queue: 將自己放進wait queue 3.Removes itself from the red-black tree of runnable: 將自己從runnable 的 red- black tree 中移除 4.Calls schedule() to select a new process to execute: 呼叫schedule()去選擇一 個新的process來執行 Waking back up is the inverse: 1.The task is set as runnable: 設置自己為runnable 2.Removed from the wait queue: 將自己從wait queue移除 3.Added back to the red-black tree: 將自己加回red-black tree

5.(8%) 什麼是Kernel Preemption？什麼情況會發生？ 搶佔式核心是指一台電腦可以同時執行多個程序，並讓這些程序已搶佔的方式輪流 使用CPU。Linux系統以preempt_count來表示當前程序是否可被搶佔。 程序的thread_info引入了preempt_count 2. preempt_count為鎖的個數，當鎖的個數為0時代表可以被搶占。 何時發生: 1.一個程序在執行時若有一個更高優先權的程序出現，而原程序是處於允許搶佔的 狀態時，則原程序將會進入sleep狀態並讓更高優先權的程序使用CPU。 2.系統呼叫schedule()時也會發生Preemption(處理程序順序或是有程序sleep) 3.當中斷處理程序正在執行，返回kernel space之前

6.(10 pts) 說明下列 System Calls的用途。 A. sched_getscheduler(): 4-86: sched_getscheduler() system calls set and get a given process‘s scheduling policy and real-time priority B. waitpid(): 會讓程序暫停並等待子程序結束以及接收狀態值。 C. sched_setaffinity(): 4-88:The user, via sched_setaffinity(), can provide a different bitmask of any combination of one or more bits D. sched_yield(): 4-89:Linux provides the sched_yield() system call for a process to explicitly yield the processor to other waiting processes E. nice():Nice值是Linux作業系統中表示靜態優先級的數值。每個行程都有自己的 靜態優先級，優先級高的行程得以優先執行。Nice值的範圍是-20~+19， 擁有Nice值越大的行程的實際優先級越小（即Nice值為+19的行程優先級 最小，為-20的行程優先級最大），預設的Nice值是0。

7.(10 pts) 解釋下列名詞。 A. Copy-on-Write: 寫入時複製(Copy-on-write)是一個被使用在程式設計領域的最佳化策略。其基礎的觀 念是，如果有多個呼叫者(callers)同時要求相同資源，他們會共同取得相同的指標指向 相同的資源，直到某個呼叫者(caller)嘗試修改資源時，系統才會真正複製一個副本 (private copy)給該呼叫者。 B. Kernel Thread: kthread在背景執行扮演服務的角色，等待events發生。在等待的過程中，kthread會進 入sleep狀態，當事件發生的時候，kthread會被喚醒執行一些time-consuming的工作。 C. Scheduler Class: LINUX的排程器是以模組的方式運作，這些模組擁有不同的演算法處理不同型態的process， 模組的集合稱為Scheduler Class D. Perfect Multitasking: 假設現在有X個precess，一次搶占CPU的時間為5毫秒。Perfect Multitasking指的是處理器 能同時運行這些process X*5毫秒，並平均分配運行功率。

E. Wait Queue: Wait queue就是用來讓process sleep的 kernel API。 Process 被放到 wait queue 時的狀態為 TASK_INTERRUPTIBLE 或是 TASK_UNINTERRUPTIBLE。這個時候因為我們的 process 在睡覺了（被放到 wait queue），所以 scheduler 就會再由 ready queue 裡挑一個 process 來執行。

8. (5%) 下面程式的運作結果為何？理由為何？ 8. (5%) 下面程式的運作結果為何？理由為何？ Before the fork After the fork

9.(8%) Linux作業系統用什麼Structure表示一 Process？此外，如何找到此Structure。 在Linux Kernel 原始程式碼的檔案 include/linux/sched.h 中 define，Process 的 狀態結構被定義在 struct task_struct 之中。