考試

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.

$$圖片請看原檔$$

參考解答:

mt

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):連結

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

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次想不太到是為什麼 辛苦版主~

    • 文章作者的留言

      mt

      嗨!這題的two-level是指讀取memory這個指令本身是indirect的,不是two-level的page table。所以應該是抓第一個指令的時候一次page fault,然後這個指令會先指到一個memory address再指到目標data的memory address(因為indirect),所以這邊有可能再發生兩次page faults~

發佈留言