106 中山資工所考古題詳解｜軟體考點分析

題型與配分

全卷 3 頁、10 題、100 分，不可使用計算機，全部是問答申論題。卷首註明：題目不清楚或需要做某些假設時，在答案開頭清楚說明假設。

作業系統佔 50 分（第 1 到 5 題），C 程式與資料結構佔 50 分（第 6 到 10 題）。

逐題考點

• 第 1 題（10%）｜一段用 Pthreads API 的 C 程式（行號只供參照），value 初值 101。主程式 fork 後，parent process waitpid 再印出 A = --value；child process 再 fork，其 parent process waitpid 後印出 B = value--；最內層再 fork 一次，接著建立執行 runner（把傳入的整數減 1）的 Pthread 並 pthread_join，之後 parent process waitpid 再印出 C = ++value、child process 印出 D = value++。寫出程式的輸出
• 第 2 題（10%）｜process 有 m 個 frame（一開始都是空的），page reference string 長度為 n、其中有 p 個不同的 page，對任何 replacement algorithm：(a) 5% page fault 次數的上界 (b) 5% page fault 次數的下界
• 第 3 題（10%）｜process 的 address space 有 2048 個 page，page table 放在記憶體，讀取 page table 一個字的開銷是 600 nsec，TLB 可存 64 組 (page, frame)，查詢要 100 nsec，要把平均開銷降到 200 nsec 以下，需要多高的 hit rate
• 第 4 題（10%）｜UNIX i-node 有 10 個 direct block 與 single、double、triple 三層 indirect block，pointer 8 bytes、block 8 KB：(a) 5% 允許的最小檔案大小（bytes） (b) 5% 允許的最大檔案大小（bytes）
• 第 5 題（10%）｜磁碟有 24000 個 cylinder，每個 cylinder 16 個 track、每軌 512 個 block，seek 每移動一個 cylinder 要 1 ms。若不把檔案的 block 放在一起，邏輯上連續的兩個 block 平均 seek 要 6 ms；若作業系統把相關 block 叢集起來，block 間平均距離縮為 2 個 cylinder、seek 時間降為 200 μs。rotational latency 3 ms、每 block 傳輸 10 μs：(a) 5% 讀取隨機放置的 300 個 block 的檔案要多久 (b) 5% 讀取叢集放置的 300 個 block 的檔案要多久
• 第 6 題（10%）｜用一行 C 宣告指向 array int a[256]; 的 pointer p，使 p[1] 是 a[0] 的別名、p[2] 是 a[1] 的別名，依此類推到 p[256] 是 a[255] 的別名
• 第 7 題（10%）｜Ackermann function A(m,n) 的定義：m = 0 時為 n+1，m > 0 且 n = 0 時為 A(m−1, 1)，m > 0 且 n > 0 時為 A(m−1, A(m, n−1))。卷面舉例寫 A(1,1) = 65533，問 A(2,3) 的值
• 第 8 題（10%）｜n = 2^m，寫出 recurrence relation T(n) = 1（n = 2）、T(n) = 2T(n/2) + 2（n > 2）的 closed form
• 第 9 題（10%）｜分析 QUICKSORT 在對手每隔一次就挑最好的 splitter（partitioning element）而不是最差的（好壞交替）時的行為，這個「對手」造成的執行時間
• 第 10 題（10%）｜把 (A+B)*(C+D-E)*F 轉成 prefix 與 postfix

作答時要注意的地方

1. 10 題各 10 分，卷面沒有標示倒扣。
2. 第 1 題的程式有行號，行號只供參照。
3. 第 3 題卷面沒有說 TLB 與 page table 是先後查還是同時查，110 年第 3 題、111 年第 6 題卷面有寫明。
4. 第 7 題卷面舉例寫 A(1,1) = 65533，109 年第 10 題同一個定義寫的是 A(4,1) = 65533。
5. 全卷不可使用計算機，第 4(b) 題的檔案大小與第 5 題的時間都要手算。

準備方向

• fork 與 Pthreads 的輸出（106 第 1 題），109 第 4 題也是 fork、waitpid 加 Pthread 的程式，110 第 1 題有 fork、pipe 與 exec。
• Page fault 次數（106 第 2 題），109 第 3 題、110 第 5 題考 2D array 的 page fault。
• TLB hit rate（106 第 3 題），110 第 3 題、111 第 6 題同型，同年硬體第 8 題也有。
• UNIX i-node（106 第 4 題），109 第 5 題、110 第 4 題、111 第 5 題也有。
• 磁碟讀檔時間（106 第 5 題），111 第 7 題同型，只換了 cylinder 數與時間參數。
• C pointer 與 array（106 第 6 題），111 第 1(a) 題考 pointer 算術。
• Ackermann function（106 第 7 題），109 第 10 題也有。
• recurrence 的 closed form（106 第 8 題），112 第 4 題、113 第 4 題、114 第 4 題要自行寫出 recurrence。
• Quicksort 的分析（106 第 9 題），107 第 5(5) 題考 quicksort 的最壞情況，108 第 1(4) 題、109 第 9 題、112 第 2 題、113 第 3 題、114 第 2 題、115 第 9 題也有排序。
• 運算式轉換（106 第 10 題），107 第 5(2) 題考 postfix 求值，108 第 1(1) 題考 prefix 轉 infix。