課程名稱︰即時系統 課程性質︰選修 課程教師︰郭大維 開課學院：電資學院 開課系所︰資工所、網媒所 考試日期（年月日）︰2013.11.05 考試時限（分鐘）：150 試題 : Fa11 2013 Mid-Exam (答案卷) RTS Read each question over carefully several times. Answer all questions in the space provided. The exam is 150 minutes long. The total score is 111. (1) Please define the following terminologies (21pts): a. Hard Real-Time Process Ans: It is catastrophic if some deadline of a hard real-time process is missed. b. An Event-Driver Software Architecture Ans: Schedulable tasks are triggered by I/O completion and timer events. c. Global Fixed Job-Priority (FJP) Scheduling Ans: The relative priorities of jobs are fixed when jobs arrive, and any job can be scheduled on any available processor. d. The Multiprocessor Anomaly Reported by Graham in 1976 Ans: Given a set of processes being optimally scheduled on a multiprocessor system, changing the priority list, increasing the number of processors, reducing execution times, or weakening the precedence constraints can increase the schedule length. e. VLIW Architecture Ans: VLIW refers to a CPU architecture designed to take advantage of instruction level parallelism (ILP). The performance can he improved by executing different sub-steps of sequential instructions simultaneously (this is pipelining), or even executing multiple instructions entirely simultaneously as in superscalar architectures. f. Critical Voltage in Energy-Efficient Task Scheduling Ans: Consider Dynamic Voltage Scheduling and Dynamic Power Management together, it is the lowest voltage to run a task at a constant speed to minimize the energy consumption. g. The Intensity Function in the DVS Algorithm by Frances Yao, Alan Demers, and Scott Shenker, "A Scheduling Model for Reduce CPU Energy", FOCS, 1995 Ans: The total amount of execution time that must be execute in a time duration divided by the duration length. (2) Please answer the following questions in process synchronization: You must provide explanation to receive any points. (20pts) (a) Compare the Priority Inheritance Protocol, the Priority Ceiling Protocol, the Highest Locker's Priority Protocol, and the No Preemption Protocol in terms of the maximum number of priority inversion per process, chain-blocking avoidance, and deadlock-freeness (e.g., The No-Preemption Protocol is deadlock-free). (No Explanation is needed) (b) Which one is the most conservative protocol such that a process is more likely to be blocked by lower priority process? (c) Please give me an argument why the No-Preemption Protocol is deadlock-free? Ans: (A) ┌───────┬─────┬──┬────────┬───────┐ │ │ PIP │ PCP│Highest Locker's│ No Preemption│ │ │ │ │ Priority │ │ ├───────┼─────┼──┼────────┼───────┤ │Max # of PI │ Max(n, m)│ 1 │ 1 │ 1 │ ├───────┼─────┼──┼────────┼───────┤ │Deadlock │ Yes │ No │ No │ No │ ├───────┼─────┼──┼────────┼───────┤ │Chain-Blocking│ Yes │ No │ No │ No │ └───────┴─────┴──┴────────┴───────┘ (B) No Preemption Protocol. (C) There is no hold and wait. (3) Please define the term "Least Upper Bound of Utilization Factor". Furthermore, the Least Upper Bound of Utilization Factor of the earliest deadline first algorithm (EDF) is 100%. Obviously, the Least Upper Bound of Utilization Factor of the rate monotonic scheduling algorithm (RMS) that is n(2^(1/n) - 1) is, in general, much less than 100%. Please give me two situations in which RMS is preferred. (10pts) Ans: (A) The least upper bound of utilization factor of a scheduling policy is a real number such that for any process set Π, U(Π) no more than the number implies the schedulability of the process set Π. (B) It is when we prefer stability and the handling of transient overloads, or when we must consider the required relationship between interrupts (and even processes). (4) Consider dynamic voltage scaling. Why running a process at a constant speed can save more energy than running at two or more speeds? (5pts) Ans: It is because the power function is a convex function. (5) Consider the scheduling of sporadic processes. Please answer the following questions: You must provide explanation to receive any points. (20pts) (a) In terms of "fairness", why Constant Utilization Servers could be better than Total Bandwidth Servers? (b) In terms of "average response time", why Sporadic Servers are better than Polling Servers? (c) In terms of "Achievable Utilization Factor", why Deferrable Servers are worse than Sporadic Servers? (d) Consider the service of a sporadic process with a hard deadline 10ms, the minimum separation time 100ms, and the worst-case execution time 3ms. Please define the period and computation time budget for a polling server, a deferrable server, and a sporadic server. Suppose the three servers could be of the highest priority in the system. Ans: (a) It is because TBS will utilize idle time for its process service such that the deadline of its pending process might be pushed forwarded with limitation. (b) It is because Sporadic Servers are of on-demand services. (c) It is because under Deferrable Servers, a lower priority process might see much more demands from the service/computation requests of Deferrable Servers within its ready time and deadline. (d) a polling server (C = 3ms, P = 5ms), a deferrable server (3ms, 100ms), and a sporadic server (3ms, 100ms). (6) Why the algorithm presented in the class that does deadline revision for a process set is a pseudo-polynomial-time algorithm? (5pts) Ans: First, the number of scheduling blocks processed by the deadline is related to the LCM of process periods. (7) RMA: Consider the following process set with the assigned priorities (Max: 1, Min: 4): (hint: use schedulability bound tests, completion time test, or schedulability point test. All critical sections are NESTED.) (30pts) ┌─────┬─────┬───────┬───────┬─────┐ │ │ T1 │ T2 │ T3 │ T4 │ ├─────┼─────┼───────┼───────┼─────┤ │ P_i │ 80 │ 100 │ 150 │ 200 │ │ │(periodic)│ (periodic) │ (periodic) │(periodic)│ ├─────┼─────┼───────┼───────┼─────┤ │ C_i │ 20 │ 25 │ 30 │ 30 │ ├─────┼─────┼───────┼───────┼─────┤ │Semaphores│ S2(10) │ S1(10), S2(6)│S1(10), S2(15)│ S1(20) │ ├─────┼─────┼───────┼───────┼─────┤ │ deadline │ 35 │ 90 │ 140 │ 180 │ ├─────┼─────┼───────┼───────┼─────┤ │ priority │ 1 │ 2 │ 4 │ 3 │ └─────┴─────┴───────┴───────┴─────┘ (a) Consider periodic process set {T1, T2, T3, T4} without semaphore sharing and pre-period deadlines. Show me which process is schedulable or unschedulable. (b) Consider periodic process set {T1, T2, T3, T4} without semaphore sharing. Show me which process is schedulable or unschedulable. (c) Consider periodic process set {T1, T2, T3, T4} with semaphore sharing. Show me which process is schedulable or unschedulable under the priority ceiling protocol. (d) Consider periodic process set {T1, T2, T3, T4} with semaphore sharing. Show me which process is schedulable or unschedulable under the priority inheritance protocol. Ans: (a) T1: 20 ≦ 80 => V T2: (20) + 25 = 45 ≦ 80 => V T3: (20*2 + 25*2 + 30) + 30 = 150 ≦ 150 => V T4: (20 + 25) + 30 = 75 ≦ 80 => V (b) T1: 20 ≦ 35 => V T2: (20) + 25 = 45 ≦ 80 => V T3: (20*2 + 25*2 + 30) + 30 = 150 ＞ 140 => X T4: (20 + 25) + 30 = 75 ≦ 80 => V (c) B1 = 15, B2 = 20, B3 = 0, B4 = 10 T1: 20 + B1 = 35 ≦ 35 => V T2: (20*2) + 25 + B2 = 85 ≦ 90 => V T3: (20*2 + 25*2 + 30) + 30 + B3 = 150 ＞ 140 => X T4: (20*2 + 25*2) + 30 + B4 = 130 ≦ 160 => V (d) B1 = 6 + 20 = 26, B2 = 20 + 15 = 35, B3 = 0, B4 = 10 T1: 20 + B1 = 46 ＞ 35 => X T2: (20*2) + 25 + B2 = 100 ＞ 90 => X T3: (20*2 + 25*2 + 30) + 30 + B3 = 150 ＞ 140 => X T4: (20*2 + 25*2) + 30 + B4 = 130 ≦ 160 => V --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.49.194 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1421723410.A.D34.html