(b) One guy said that he has invented a comparison-based sorting algorithm, called Supersort, with the worst-case running time of O(n). Do you think that Supersort is possible? Please give your reason.

(a) Please draw four Gantt charts to show the execution of all processes based on the following scheduling algorithms: First-come first-served (FCFS), round robin (RR with quantum = 1), shortest job first (SJF), and non-preemptive priority (where a smaller priority number indicates a higher priority).

(b) Calculate the turnaround time of each process in the four scheduling algorithms. 

(c) Which of the algorithms results in the minimum average waiting time? Note that you should give your calculation.

2.(a) What are the four conditions to result in a deadlock? Please detail each condition in your answer.

(b) Will a deadlock necessarily arise when any of the four conditions occur? Why or why not? Please explain your reason.

(a) Please explain what is demand paging?

(b) To support demand paging, what are the two types of hardware will you require? Note that you should give the functionality of each hardware.

(c) Suppose that you design demand paging for an operating system. Assume that the memory-access time is 200 nanoseconds and the average page-fault time is 75 microseconds. If you want the effective access time for demand paging no larger than 230 nanoseconds, what will be the expected page-fault rate? You need to give your calculation.

4. In a multimedia system, SCAN-EDF is a popular disk scheduling scheme. Suppose that you have the following file requests (request, deadline, cylinder): (A, 150, 25), (B, 201, 112), (C, 399,95), (D,94, 31), (E, 295, 185), (F, 78,85), (G, 165, 150), (H, 125, 101), (I, 300,85), (J, 210, 90). Considering that the disk head is currently on cylinder 49 and moving toward cylinder 50, please show how the disk head moves to satisfy all requests using SCAN-EDF.

5. Authentication is useful for proving that a message has not been modified during transmission. The message-authentication code and the digital-signature algorithm are two popular authentication solutions. Please explain how they operate.

110年 - 110 國立中山大學_碩士班招生考試_資工系(甲組)：作業系統與資料結構#104265

109年 - 109 國立中山大學_碩士班招生考試_資工系(甲組)：作業系統與資料結構#105756

108年 - 108 國立中山大學_碩士班招生考試_資工系(甲組#105764

107年 - 107 國立中山大學_碩士班招生考試_資工系(甲組)：作業系統與資料結構#105786

106年 - 106 國立中山大學_碩士班招生考試_資工系(甲組)：作業系統與資料結構#105790

105年 - 105 國立中山大學_碩士班招生考試_資工系(甲組)：作業系統與資料結構#105820

104年 - 104 國立中山大學_碩士班招生考試_資工系(甲組)：作業系統與資料結構#105852

103年 - 103 國立中山大學_碩士班招生考試_資工系(甲組)：作業系統與資料結構#105840

102年 - 102 國立中山大學_碩士班招生考試_資工系(甲組)：作業系統與資料結構#105882

101年 - 101 國立中山大學_碩士班招生考試_資工系(甲組)：作業系統與資料結構#105907