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

3. [15%] Define a benchmark to measure the performance of a file system. Justify your 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!$

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

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?

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.

### 2 留言

1. #### L

你好 關於第7題的A
我是這麼想的
因為它是2 level的
執行P的時候會先抓指令
此時Page Table Directory 一次Page fault
第二層的Page table一次Page fault
實際去Mem抓指令又一次
而Data方面Page Table Directory不會Page fault
第二層的Page table假設與指令的Page table不同 發生一次Page fault
實際去記憶體抓資料又發生一次Page fault
總共3+2=5次
這樣的過程請問是正確的嗎
3次想不太到是為什麼 辛苦版主～

• 文章作者的留言