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.
參考解答:
(1) Virtual address
(2) Physical address
(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.
參考解答:(1) F (2) F (3) F
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.
參考解答:
Shared memory | IPC |
OS負責allocate memory | OS負責send and receive message |
Programmer須確保mutual exclusion | 無須擔心mutual exclusion |
速度較快(無須OS) | 速度較慢(須sys. call) |
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?
參考解答:$P \leq \dfrac{1}{164000}$
試題:連結
有任何問題,或想要完整解釋的,歡迎在下方留言唷!
Jackson
安安,我想請問 3(2) 錯是因為都不需要 lock 就能實作嗎?
我當時想是 message passing 只要建立 communication link 就可以,所以不用 lock
mt
對喔~就是因為message passing不需要使用locks,而SMP的話是shared memory所以需要locks。
RRO
不好意思
我想請問2(3)
題目確切想問的意思
看不太懂他想表達的意思…
mt
2(3)在問上面的instruction sequence有沒有即使用了forwarding也無法解決的data hazard,如果有的話那請你把上面的instructions重新排序成可以用forwarding解決,但是這題題目給的順序就可以直接用forwarding解決了,所以答案是NO。