107成大資聯計系[參考解答]

1. [10%] Consider a multi-cycle, MIPS-like processor with the following 5 types of instructions.

• Load (5 cycles)
• Store (3 cycles)
• R-type (3 cycles)
• Branch (2 cycles)
• Jump (2 cycles)

(1) What is the CPI (Cycles Per Instruction) for the given program, which has 45%, 30%, 15%, 5%, and 5% of Load, Store, R-type, Branch and Jump instructions, respectively?
(2) What is the major method for this kind of processor to give commands to an I/O device? (Hint: To give commands to an I/O device, the processor should be able to address the device and supply commands.)

參考解答：(1) 3.8 (2) Memory-mapped I/O

---

2. [25%] While there are many advantages for adopting virtual machines in systems, running virtual machines on the systems could incur performance overhead. Please determine the system performance (CPI) with the performance parameters and application behavior listed below.

Base CPI	2
Privileged OS access per 10000 instructions	100
Performance impact to trap to the guest OS	20 cycles
Performance impact to trap to VMM	150 cycles
I/O access per 10000 instructions	20
I/O access time (includes time to trap to guest OS)	1200 cycles

(1) What is the CPI of the non-virtualized system?
(2) What is the CPI of the virtualized system?
(3) Based on the above results and the data listed in the table, please answer the question: “do I/O bound applications have a smaller impact from virtualization and explain why?”

參考解答：
(1) $2 + \dfrac{2}{1000} \times 1200 = 4.4$
(2) $2 + \dfrac{100}{10000} \times (20 + 150) + \dfrac{20}{10000} \times (1200 + 150) = 6.4$
(3) Yes, I/O traps usually often require long periods of execution time that can be performed in the guest OS, with only a small portion of that time needing to be spent in VMM. As such, the impact is less for I/O bound applications.

---

3. [15%] As I/O accesses often have a large impact on overall system performance, it is a common practice to reschedule the I/O accesses to hard disks to obtain better performance. Suppose the application generates three I/O Read operations on the three different logical block address in the sequence: (555, 22, 120). The access sequence is listed in the table and the physical locations of the logical block addresses are illustrated in the figure.

Please determine the best schedules that will deliver the minimal disk access time in different conditions.
(1) The OS could reschedule the I/O accesses to improve the performance. For example, OS reschedules the accesses in the sequence (22, 120, 555). Does the OS always deliver the best schedule given the logical block addresses? Why?
(2) What is the best sequence for the I/O accesses when the disk seek time is far larger than its rotational delay?
(3) What is the best sequence for the I/O accesses when the disk rotational delay is far larger than its seek time?

參考解答：
(1) No, because a scheduler which best serves random pattern disk activity will not provide the same performance under sequential activity.
(2) (120, 555, 22)
(3) (120, 22, 555)

---

4. [10%] Consider a computer with an address space of 32 bits, and a 2 Kb page size. What is the size of the page table (single level)? What is the maximal size of a program’s memory? Does it depend on the size of the pages?

參考解答：(1) 8MB (2) 4GB (3) No

---

5. [20%] Suppose that there are only 3 frames of physical memory, and a process accesses its page in the following order: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2. How many page faults would occur for the following two replacement algorithms? Please also show the detailed procedure to calculate the number of page faults. Remember that all frames are initially empty, so your first unique pages will cost one fault for each.

(a) FIFO
(b) LRU

參考解答：(a) 13 (b) 13

---

6. [10%] Consider a file system that uses inodes to represent files. Disk blocks are 4-KB in size and a pointer to a disk block requires 4 bytes. This file system has 12 direct disk blocks, plus single, double, and triple indirect disk blocks. What is the maximum size of a file that can be stored in this file system?

參考解答：$(12 + 2^{10} + 2^{20} + 2^{30}) \times 4 \text{KB}$

---

7. [10%] Suppose that a disk drive has 5000 cylinders, numbered 0 to 4999. The drive is currently serving a request at cylinder 143 (assume the previous request was at cylinder 125). The queue of pending requests, in FIFO order, is 76, 1470, 909, 968, 1509, 1020, 1750, 130. Starting from the current head position, what is the total distance (in cylinders) that the disk arm moves to satisfy all the pending requests, for each of the following disk-scheduling algorithms?

(a) SSTF
(b) C-SCAN

參考解答：(a) 1741 (b) 9985

---

試題(pdf)：連結

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