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

• 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.)

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.

(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?

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

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?

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

### 8 留言

1. #### Jackson

想請問 5 應該沒有要算機率，寫 13 次 page fault + 畫 page allocation 的圖應該就 ok ?
還有第 7 題 C-SCAN 的 distance 沒算往回的應該 ok ? 我是看周志遠老師 OS 課 他最後說的
https://youtu.be/tJhpntJNyO8?t=20m43s 感恩

• 文章作者的留言

#### mt

對～第五題寫次數跟畫圖就可以了！
第七題的話回程的distance要算還是不算其實上課也有提到是一個有爭議性的問題，所以沒有一個確切的規定（算或不算照理來說都可以），還是要看出題老師。不過從你傳的影片大概可以知道清大是不算的～

2. #### Jackson

請問 4(2) 應該是 2^32 bytes = 4 GB ? 感恩

3. #### yummy

第四題的第一小題問Page table size，請問如何知道一個 entry size 為 4B，是因為需紀錄 21-bit PPN 然後 round up to word 4B 嗎？

• 文章作者的留言

#### mt

大概是這樣沒錯～因為最少要21個bits我就假設4 bytes，考試的時候寫假設page table entry佔4 bytes應該就沒什麼問題了！

4. #### william

請問第二題第一小題是2+(20/10000)*1200 = 4.4嗎 ，您的算式2+(2/1000)*200 算出來不是4.4??