1. [10%] Translate the beq instructions shown in the following code into an 32-bit binary instruction, provided that the opcode of beq is 0x04.

L1: add $8,$9, $10 add$8, $9,$10
beq $0,$9, L2
add $8,$9, $10 add$8, $9,$10
L2: add $9,$0, $9 參考解答：000100 00000 01001 0000000000000010 2. [10%] Assume a virtual memory addressing space of 16 Gbytes and a physical memory addressing space of 4 Gbytes. Let the size of a page be 4 Kbytes. What is the size of a page table in terms of the number of entries? 參考解答：4M entries 3. [15%] Consider a pipelined processor that executes the MIPS code shown in Figure 1 using the logic of hazard detection and data forwarding unit shown in Figure 2. If the MIPS code cannot be executes correctly, then how do we revise the logic shown in Figure 2 such that the code can be correctly executed? Figure 1: The MIPS code: add$10, $10,$5

add $10,$10, $6 add$10, $10,$7
Figure 2: The logic of hazard detection and data forwarding unit:

if (MEM/WB.RegWrite

and (MEM/WB.RegisterRd != 0)

and (EXE/MEM.RegisterRd = ID/EX.RegisterRs)

and (MEM/WB.RegisterRd = ID/EX.RegisterRs))

then ForwardA = 01

if (MEM/WB.RegWrite

and (MEM/WB.RegisterRd != 0)

and (EXE/MEM.RegisterRd = ID/EX.RegisterRt)

and (MEM/WB.RegisterRd = ID/EX.RegisterRt))

then ForwardB = 01

The logic should be revised as follows:

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

$$圖片請看原檔$$

5. [10%] Given a 10000-RPM disk with 80-MB/second bandwidth and 10-ms average seek time, please calculate the average time to read a 40-KB block from this disk.

6. [10%] On a virtual memory system, three frames are allocated to process P, one is used to accommodate the code page of P and the other two are used to accommodate the data pages of P. The pseudo code of P is shown below, and the following are assumed. First, data in the array A are stored in the row-major order, and each row of array A is stored in a virtual page. Second, the following code can be accommodated in a single page and there are no page faults for the code page accesses. Third, i, j, k are all stored in registers. Fourth, LRU is used as the page replacement policy for the data pages, and the two frames used to accommodate the data pages are initially empty. What is the page fault rate for the accesses to the array A?

int i, j, k;
int A[5,4];
k = obtain an integer from the input device;

for (i = 0; i < 5; i++)
for (j = 0; j < 4; j++)
{
if ((i == 0) && (j == 0))
A[i, j] = k;
else
A[i, j] = A[0, 0] + k;
}

7. [10%] Consider a system with 64 MB of physical memory, 1024 TLB entries, 32-bit physical address, 32-bit virtual addresses, and 4 KB physical page frames.

(a) What is the TLB reach?
(b) What is the maximum number of page table entries in the inverted page table if 10 processes are presented in the system?

(a) The memory size that TLB can access. TLB reach = TLB size $\times$ Page size.
(b) $2^{14}$ entries.

8. [20%] Consider the following set of (single-threaded) processes with different CPU burst time, arrival time, and priorities:

 Processes Burst Time (ms) Arrival Time (ms) Priorities P1 30 0 1 (lowest) P2 20 10 2 P3 50 20 3 P4 20 40 4 (highest)

(a) Assume that there is only one processor in the system and the context switch time is 1 ms. Moreover, the idle process is executed before the arrival of process P1. What is the waiting time of the processes under the preemptive SJF scheduling algorithm?
(b) Assume that there are two processors in the system (with a single run queue) and the context switch is 0 ms. What is the waiting time of the processes under the priority-based scheduling algorithm?

(a) P1: 23ms, P2: 1ms, P3: 55ms, P4: 14ms.
(b) P1: 10ms, P2: 0ms, P3: 0ms, P4: 0ms.

### 14 留言

1. #### daniel

想問第8題的B小題 P1: 35ms, P2: 0ms, P3: 10ms, P4: 0ms.是怎麼算的
我算出來是 P1: 10ms, P2: 0ms, P3: 0ms, P4: 0ms.

2. #### daniel

不好意思，我還想問第六題的5/39是怎麼算的?

• 文章作者的留言

#### mt

不好意思！第六題應該是8/39才對，除了A[0][0]的時候會access memory一次其他都會access memory兩次所以分母的部分是1+(2×19)=39，分子的部分則是因為總共page fault 8次，過程如下：
A[0]載入memory
A[1]載入memory
A[2]載入memory取代A[0]
A[0]載入memory取代A[1]
A[3]載入memory取代A[0]
A[0]載入memory取代A[2]
A[4]載入memory取代A[0]
A[0]載入memory取代A[3]

• #### 小吳

想問一下第六題的部分為什麼A[3]是取代A[0]不是A[2]呢？
依照LRU的話應該先取代A[2]吧？
不知道哪裡有理解錯

• 文章作者的留言

#### mt

A[2]雖然比A[0]還早載入memory，但是最後被用到的是A[2]，可以看下面這段程式碼：
A[i, j] = A[0, 0] + k;
先取得A[0, 0]的值後加上k然後assign給A[2, j]，希望這樣有解決你的問題。

3. #### 小O

想請問第 7 題 a是否要乘出來答案4MB?
還有b怎麼算的 感謝

• 文章作者的留言

#### mt

a小題沒錯是4MB，b小題是64MB/4KB喔。

感謝您

4. #### Jackson

你好，請問第2題是只要求 entry 數目，不是求 page table 大小嗎 ?
我求 page table size = (1 + 20) * 2^22 = 84 MB

• 文章作者的留言

#### mt

是求entries數目喔～題目最後有說in terms of the number of entries，而且資訊過少沒辦法知道每個entry要多大！

好的 感恩

5. #### Jackson

您好，我想請問一下，為什麼 第六題 是先讀 A[2] 再讀 A[0] ?

• 文章作者的留言

#### mt

應該是A[0]先讀再讀A[2]喔～所以A[3]載入memory的時候才會是取代A[0]而不是A[2]。