101成大資工計系[參考解答]

1. [15%] Figure 1 shows the control of the multicycle MIPS processor. There are number of typos in the plot. Identify and correct the typos.

$$圖片請看原檔$$

參考解答：

---

2. [10%] Let registers \$s0 and \$s1 have the binary numbers 11111111111111111111111111111111 $_{two}$ and 00000000000000000000000000000001 $_{two}$ respectively. What are the values of registers \$t0 and \$t1 after executing the two instructions as follows:

slt  $t0, $s0, $s1

sltu $t1, $s0, $s1

參考解答：\$t0 = 1, \$t1 = 0.

---

3. [15%] Define a benchmark to measure the performance of a file system. Justify your benchmark.

參考解答：
常見的benchmark有：
1. File creation time
2. File mount time
3. Total free space
4. Touch file time
5. Find file time
6. Make dir time
7. Find dir time
8. Del dir time

---

4. [10%] Represent an interconnection network as a graph $G=(V,E),$ where $V$ is the set of nodes in the network $G$ and $E$ includes the edges connecting the nodes in $V.$ A path is an acyclic subgraph of $G.$ The length of a path in $G$ is the number of edges on the path. A shortest path between two distinct nodes $u, \, v \in V$ is a path with a minimum number of edges connecting $u$ and $v.$

(a) Let $G$ be a 16-node hypercube. Detail the topology of $G.$
(b) Consider any two distinct nodes $u, \, v \in V.$ How many shortest paths of length 4 are present in a 16-node hypercube?

參考解答：
(a) 略
(b) $4!$

---

5. [15%] Compared to monolithic kernels, which of the following are the advantage(s) of microkernels? Please briefly describe your answer.

(a) Higher performance
(b) More secure
(c) More reliable

參考解答：(b) and (c) are advantages for microkernels compared to monolithic kernels.

---

6. [15%] Assume we have a demand-paged memory. The page table is held in registers. It takes 10 milliseconds to service a page fault if an empty page is available or the replaced page is not modified, and 20 milliseconds if the replaced page is modified. Memory access time is 100 nanoseconds. Assume that the page to be replaced is modified 80 percent of the time. What is the maximum acceptable page-fault rate for an effective access time of no more than 200 nanoseconds?

參考解答：$P < \dfrac{1}{180000}$

---

7. [10%] Suppose that a machine provides instructions that can access memory locations using the two-level indirect addressing scheme. Assume that all of the pages of a process P are currently non-resident, the first instruction of P is a two-level indirect memory load operation, and the operating system is using a per-process frame allocation technique. In the following cases, what are the maximal numbers of page faults for the execution of the first instruction of P?

(a) P is allocated 20 pages
(b) P is allocated 2 pages

參考解答：
(a) 3
(b) $\infty$

---

8. [10%] What is the main advantage of the variation of linked allocation that uses a FAT (File Allocation Table) to chain together the blocks of a file?

參考解答：
1. We can use the whole disk block to store data.
2. Random access is provided.
3. Only FAT needs to be traversed in each file operation.

---

試題(pdf)：連結

有任何問題，或想要完整解釋的，歡迎在下方留言唷！