100成大資工計系[參考解答]

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.

參考解答：10ms + 3ms + 0.5ms = 13.5ms

---

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;
    }

參考解答：$\dfrac{8}{39}$

---

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.

---

試題(pdf)：連結

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