1. [30%] Consider the following figure.

(1) What is the name of the TLB’s input (Symbol A in the figure)? (Hint: XXX address.)
(2) What is the name of the TLB’s output (Symbol B in the figure)?
(3) What is the name of this type of cache (with B as its input)? (Hint: XXX cache.)
(4) Does the cache aliasing occur in the cache design shown in the figure (Yes or No)? Explain your answer.
(5) “We could have a hit in the cache, and get a TLB miss and a page table miss.” Is the statement true (Yes or No)? Explain your answer.
(6) Consider the processor operating at 1GHz. The processor stalls during a cache miss and has the following properties: (i) a cache access time of 2 clock cycles for a hit, (ii) a miss penalty of 100 clock cycles, and (iii) a miss rate of 0.03 misses per instruction. Please compute the average memory access time.

(3) Physically addressed cache
(4) No. Since every logical address of different process will convert to different physical address and the design uses a physically addressed cache.
(5) No. Page table miss $\to$ data are not in memory $\to$ data are not in cache.
(6) $\text{AMAT = } (2 + 0.03 \times 100) \times 1 \text{ns} = 5 \text{ns}$

2. [10%] Assume the MIPS processor with 5 stages of the pipeline:

(i) IF for the instruction fetch stage,
(ii) ID for the instruction decode/register file read stage,
(iii) EX for the execution stage,
(iv) MEM for the memory access stage, and
(v) WB for the write-back stage.

I1: ADD R1, R2, R0

I2: LW  R2, 16(R1)

I3: LW  R1, 4(R3)

I4: SUB R5, R3, R4

(1) Find all data dependencies in the instruction sequence.
(2) Find all hazards in the instruction sequence for the processor with and without forwarding.
(3) Sometimes, even with forwarding, we would have to stall one stage for a data hazard. Fortunately the software technique, Reordering Code, would be adopted to avoid the pipeline stalls. Please state if the instruction sequence suffers from a data hazard that cannot be resolved by the forwarding (Yes or No). If your answer is Yes, please list your reordered code.

3. [10%] Determine whether each of the following statements is True (T) or False (F), and explain your answer.

(1) Strong scaling is not limited by Amdahl’s law.
(2) Both SMPs and message-passing computers rely on locks for synchronization.
(3) Multithreading technology in CPUs help reduce the memory latency.

4. [10%] When multiple processes need to cooperate, there is a choice between shared memory the inter-process communication (IPC). Compare and contrast these two techniques. Make sure to clarify the role of the operating system in each.

5. [10%] What is the cause of thrashing? How does the system detect thrashing? Once it detects thrashing, what can the system do to eliminate this problem?

(1) Thrashing occurs when the virtual memory of the system is overused, causing a constant state of paging and page-fault.
(2) CPU utilization: low, I/O paging disk: high.
(3) Decrease the degree of multi-programming.

6. [20%] Consider the following snapshot of a system:

(1) What is the content of the matrix Need?
(2) Is the system in a safe state? Why?
(3) If a request from process P1 arrives for (1, 3, 5, 1), can the request be granted immediately? Why?

(1)

Need
A B C D
0 6 4 2
0 4 1 0
0 0 0 2
0 7 5 0

(2) Yes, we found a safe sequence $P2 \to P1 \to P3 \to P4.$
(3) No, the request is more than the Need.

7. [10%] Assume we have a demand-paged memory. The page table is held in registers. It takes 8 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 70 percent of the time. What is the maximum acceptable page fault rate for an effective access time of no more than 200 nanoseconds?

4 留言

1. Jackson

安安，我想請問 3(2) 錯是因為都不需要 lock 就能實作嗎?
我當時想是 message passing 只要建立 communication link 就可以，所以不用 lock

• 文章作者的留言

mt

對喔～就是因為message passing不需要使用locks，而SMP的話是shared memory所以需要locks。

不好意思
我想請問2(3)
題目確切想問的意思
看不太懂他想表達的意思…

• 文章作者的留言

mt

2(3)在問上面的instruction sequence有沒有即使用了forwarding也無法解決的data hazard，如果有的話那請你把上面的instructions重新排序成可以用forwarding解決，但是這題題目給的順序就可以直接用forwarding解決了，所以答案是NO。