課程名稱︰即時系統 課程性質︰選修 課程教師︰郭大維 開課學院：電資學院 開課系所︰資工所、網媒所 考試日期（年月日）︰2012.11.13 考試時限（分鐘）：180 試題 : Fall 2011 Mid-Exam RTS Read each question over carefully several times. Answer all questions in the space provided. The exam is 180 minutes long. The total score is 102. (1) Please define the following terminologies (21pts): a. Achievable Utilization Factor Ans: The Achievable Utilization Factor α of a scheduling policy P is defined as follows: Any process set with total utilization factor no more than α is schedulable. b. Priority Ceiling Ans: Define a semaphore's priority ceiling as the priority of the highest priority process that may lock the semaphore. c. Partitioned Earliest Deadline First Scheduling Ans: Tasks are first partitioned over processors. EDF is then used to schedule tasks on each processor without task migration. d. Dynamic Power Management Ans: Dynamic power management tries to select an optimal power saving states with proper hardware support. e. Forbidden Region Ans: In a forbidden region, no task scheduling/dispatching should be done. f. The Instantaneous Utilization of a Sporadic Job S_(i, j) Ans: u_(i, j) = e_(i, j) / p_(i, j), where p_(i, j) denotes the release-time difference between S_(i, j) and S_(i, j+1). g. Polling Server Ans: A polling Server periodically checks up for the arrival of sporadic tasks. If there is any pending sporadic task, then the server services the pending tasks until its execution budget is used up. (2) Redundancy is often used to detect errors and mask failures. Please explain Time Redundancy. The storing of copies for each piece of data is Space Redundancy or Information Redundancy. Please give me the argument of your answer. (8pts) Ans: (A) Time Redundancy: repetition of a computation or communication. (B) It is Information Redundancy because extra information is kept (please give me your argument if you choose another one). (3) Please compare the Timeline (or Cyclic Executive) and Pipelined architectures in terms of life-cycle cost and predictability in run-time behavior. Given two procedures P1 and P2, where the execution frequencies of P1 and P2 are 20Hz and 25Hz. Please determine the largest possible granularity of the timer and the smallest size of the major cycle under the Timeline architecture. (10pts). Ans: (A) Timeline architecture is better than Pipelined architecture in terms of the predictability in run-time behavior. Pipelined architecture is better than Timeline architecture in terms of life-cycle cost. (B) The largest timer granularity could he 10ms. The smallest major cycle could be 200ms. (4) Please answer the following uniprocessor scheduling problems: You must provide explanation to receive any points. (15pts) (A) Consider the metric to minimize the sum of completion times, i.e., Sum(X_j), of a set {τ_1, ... , τ_n} of n tasks, where each τ_i has an execution time c_i and a deadline d_i, and X_i is the completion time of a task τ_i. Please provide the optimal and efficient scheduling algorithm to minimize the sum of completion times. (5pts) (B) Continue with the above Subproblem A. If the metric becomes the minimization of the weighted sum of completion times, i.e., Sum(w_j X_j) then do we have still an optimal and efficient scheduling algorithm? (5pts) (C) If the metric is to minimize the minimum number of tasks that miss their deadlines, is your optimal scheduling algorithm for the above Subproblem A still optimal? If yes, please tell me why. If not, give me an optimal algorithm. (5pts) Ans: (A) The smallest execution time first scheduling is an optimal algorithm. (B) There is no optimal and efficient scheduling algorithm because it is a NP-Hard problem. (C) It is not optimal. EDF is the optimal algorithm to minimize the minimum number of tasks that miss their deadlines. (5) In dynamic voltage scaling, we must satisfy the deadlines of tasks and, at the same time, minimize the energy consumption. Please answer the following questions: (12pts) (A) Suppose that dynamic voltage scaling is adopted with the Priority Inheritance Protocol. Please tell me whether (or when) we should increase the voltage of the processor when a lower-priority task blocks and has priority inheritance form a higher-priority task. You should give me your argument. (5pts) (B) Please briefly summarize the scheduling algorithm in "Frances Yao, Alan Demers, and Scott Shenker, "A Scheduling Model for Reduce CPU Energy", FOCS, 1995" that minimize the total energy consumption in executing a given set of tasks, where each task τ_i ∈ T requires c_i computation time at the normalized processor frequency 1 with an arrival time a_i and an absolute deadline constraint d_i. (Hint: the intensity of an interval) (7pts) Ans: (A) We should increase the voltage of the processor if the higher-priority task might miss its deadline because of the blocking. (B) (1) We first select jobs in an interval with the highest intensity and then use the earliest-deadline first scheduling for the jobs and running at the intensity as the frequency. (2) We then adjust the arrival times and deadlines of the remaining tasks by excluding the possibility to execute them at the chosen critical interval. (3) Run the algorithm for the revised input again until all jobs are selected. (6) The deadline modification technology lets the earliest deadline first algorithm (EDF) remain an optimal scheduling algorithm for independent periodic tasks. What will be the main problem in practice when we adopt the deadline modification technology for task scheduling during the run time? (6pts) Ans: The technology is a pseudo polynomial time approach. We might need to look into the future for an extended period in deadline modification. (7) Why a Total Bandwidth Server allows tasks to better utilize unused background time, compared to a Constant Utilization Server. Which one of a Total Bandwidth Server and a Constant Utilization Server has a higher possibility for starvation? You must provide explanation to receive any points. (10pts) Ans: (A) It is because when a sporadic job with execution time e arrives at time t to an empty queue, a Total Bandwidth Server will immediately set its deadline d and budget e_s for potential execution, but a Constant Utilization Server does nothing when t < d. (B) A Constant Utilization Server has a lower possibility for starvation because the current deadline of a Constant Bandwidth Server of size u_i is never more than (max e_i)/u_i from the current time such that the length of starvation suffered by any server is bounded by max_i((max e_i)/u_i), where u_i is the server size. (7) RMA: Consider the following process set with assigned priorities (Max: 1, Min: 4): (hint: use schedulability bound tests, completion time test, or schedulability point test. All critical sections are NESTED.) (20pts) ┌─────┬─────┬───────┬─────┬─────┐ │ │ T1 │ T2 │ T3 │ T4 │ ├─────┼─────┼───────┼─────┼─────┤ │ P_i │ 50 │ 120 │ 200 │ 300 │ │ │(periodic)│ (periodic) │(periodic)│(periodic)│ ├─────┼─────┼───────┼─────┼─────┤ │ C_i │ 10 │ 30 │ 45 │ 60 │ ├─────┼─────┼───────┼─────┼─────┤ │Semaphores│ S1(5) │ S1(5), S2(10)│ S2(20) │ S1(10) │ ├─────┼─────┼───────┼─────┼─────┤ │ deadline │ 50 │ 120 │ 180 │ 150 │ ├─────┼─────┼───────┼─────┼─────┤ │ priority │ 1 │ 4 │ 3 │ 2 │ └─────┴─────┴───────┴─────┴─────┘ (a) Consider periodic process set {T1, T2, T3, T4} without semaphore sharing, and the priorities of T1, T2, T3, and T4 be inversely proportional to their periods, i.e., T1 > t2 > T3 > T4. Show me which process is schedulable or unschedulable. (b) Consider periodic process set {T1, T2, T3, T4} without semaphore sharing, and the priorities of the tasks are as shown in the above table. Show me which process is schedulable or unschedulable. (c) Consider periodic process set {T1, T2, T3, T4} with semaphore sharing, and the priorities of the tasks are as shown in the above table. Show me which process is schedulable or unschedulable under the Priority Ceiling Protocol. Ans: (a) T1: 10 ≦ 50 => V T2: (10) + 30 = 40 ≦ 50 => V T3: (10*2 + 30) + 45 = 95 ≦ 100 => V T4: (10*3 + 30*2 + 45) + 60 = 195 ＞ 150 => X (b) T1: 10 ≦ 50 => V T2: (10*3 + 60 + 45) + 30 = 165 ＞ 120 => X T3: (10*3 + 60) + 45 = 135 ≦ 150 => V T4: (10*2) + 60 = 80 ≦ 100 => V (c) T1: 10 + 10 = 20 ≦ 50 => V T2: (10*3 + 60 + 45) + 30 = 165 ＞ 120 => X T3: (10*3 + 60) + 45 + 10 = 145 ≦ 150 => V T4: (10*2) + 60 + 5 = 85 ≦ 100 => V --

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