課程名稱︰即時系統
課程性質︰選修
課程教師︰郭大維
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2011.12.07
考試時限（分鐘）：160分鐘
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
Fall 2011 Mid-Exam RTS
Read each question over carefully several time. Answer all question in the
space provided. The exam is 180 minutes long. The total score is 100.
(1) Please define the following terminologies (21 pts):
a. Firm Real-Time Process
Ans: A process that should be killed if it misses its deadline.
b. Active Replicates in Fault Tolerance Solutions
Ans: Each request is processed by all replicas, and their results are
"combined" to mask faults.
c. Time Drifting
Ans: The clock does not run at the exact speed, compared to the right
clock. It could be caused by some delay in the setting of a
one-shot timer.
d. A Run-Time Clairvoyant Scheduler
Ans: A run-time scheduler is clairvoyant if it has an oracle which can
predict with absolute certainty the future request times of all
processes.
e. Rate Monotonic Priority Assignment
Ans: The priority of a process is inversely proportional to its period.
f. Full Utilization of a Processor
Ans: For a given priority assignment, a process set fully utilizes the
processor if the priority assignment is feasible for the set and
if any increase in the run time of any processes in the set will
make the priority assignment infeasible.
g. Deferrable Server
Ans: When execution budget is used up, server execution drops to a
lower (background) priority until the budgeted execution time is
replenished.
(2) Consider the power function of a processor. What is the relationship
between the supply voltage and the power consumption? What is the
relationship between the supply voltage and the gate delay? What is the
relationship between the power consumption and the energy consumption?
(9pts)
Ans:
(A) Decreasing of V_dd reduces P quadratically.
(B) Reducing of V_dd increases the gate delay linearly.
(C) E = ∫P(t) dt
(3) The earliest deadline first scheduling algorithm (EDF) is an optimal
real-time scheduling algorithm for uniprocessor independent periodic
processes. Please answer the following questions: (18 pts)
(A) Please provide an argument on the optimality of EDF in the
minimization of the energy consumption for uniprocessor independent
periodic processes with voltage scaling support. Some argument proof
is needed. (10 pts)
(B) Partitioned EDF is to first partition tasks over processors and then
schedule tasks by EDF on each processor. Please define the Global EDF.
Is the Partitioned EDF always better than the Global EDF? Is the
Global EDF always better than the Partitioned EDF? No Explanation is
needed. (8 pts)
Ans:
(A) For periodic real-time tasks, running at constant speed with 100%
utilization under EDF has the minimum energy consumption while
satisfying the timing constraints.
(B) Global EDF always schedules the task with the earliest (absolute)
deadline to any available processor. Global EDF is not always better
than Partitioned EDF, and vice versa.
(4) There are three major approaches in the reducing of energy consumption:
Pipelining, parallelism, and out-of-order executions. The out-of-order
executions is realized by a popular VLIW architecture. Please explain how
we can use pipelining to reduce the energy consumption. Please explain
what a VLIW architecture is. (12 pts)
Ans:
(A) Let a task execution be partitioned into stages.
(B) VLIW refers to a CPU architecture designed to take advantage of
instruction level parallelism (ILP). The performance can be improved
by executing different sub-steps of sequential instructions
simultaneously (this is pipelining), or even executing multiple
instructions entirely simultaneously as in superscalar architectures.
(5) Consider the scheduling of a sporadic process with the worst-case
computation time C, the deadline D, and the minimum separation time P,
where P >= D. Please define the period, computation time, and the deadline
of a polling server to service the sporadic process. Please define the
budget and replenishment interval of a sporadic server to service the
sporadic process.
Ans:
(A) D≧D'≧C, C' = C, P' ≦ D - D' + 1 or P' = D/2, C' = C, D' = P'
(B) P' = P, C' = C
(6) Consider the blocking behavior in process synchronization. Please answer
the following question: You must provide explanation to receive any
credits.
(A) Why there is no chain blocking under the Highest Locker's Priority
Protocol? (5 pts)
(B) Let the Highest Locker's Priority Protocol be used with the concept of
priority inheritance. How many would the concept of priority
inheritance help the Highest Locker's Priority Protocol in the
reducing of the priority inversion time? (5 pts)
Ans:
(A) It is because the locking of a process over a semaphore S will prevent
any other higher priority task that arrives later and successfully
locks another semaphore where S might be locked by the higher priority
task.
(B) No help because no priority inheritance would be applied under the
Highest Locker's Priority Protocol.
(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.) (20 pts)
┌─────┬─────┬───────┬─────┬─────┐
│ │ T1 │ T2 │ T3 │ T4 │
├─────┼─────┼───────┼─────┼─────┤
│ P_i │ 80 │ 150 │ 200 │ 350 │
│ │(periodic)│ (periodic) │(periodic)│(periodic)│
├─────┼─────┼───────┼─────┼─────┤
│ C_i │ 20 │ 30 │ 60 │ 70 │
├─────┼─────┼───────┼─────┼─────┤
│Semaphores│ S1(10) │S2(10), S1(15)│ S1(20) │ S2(10) │
├─────┼─────┼───────┼─────┼─────┤
│ deadline │ 80 │ 140 │ 180 │ 350 │
├─────┼─────┼───────┼─────┼─────┤
│ priority │ 1 │ 3 │ 2 │ 4 │
└─────┴─────┴───────┴─────┴─────┘
(a) Consider periodic process set {T1, T2, T3, T4} without semaphore
sharing. Show me which process is schedulable or unschedulable.
(b) Consider periodic process set {T1, T2, T3, T4} with semaphore sharing.
Show me which process is schedulable or unschedulable under the
Highest Locker's Priority Protocol.
(c) 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 + 60) + 30 = 110 > 80
(20*2 + 60) + 30 = 130 ≦ 140 => V
T3: (20) + 60 = 80 ≦ 80 => V
T4: (20 + 30 + 60) + 70 = 180 > 80
(20*3 + 30*2 + 60) + 70 = 250 > 200
(20*4 + 30*2 + 60*2) + 70 = 330 > 300
(20*5 + 30*3 + 60*2) + 70 = 380 > 350 => X
(b) T1: 20 + 20 = 40 ≦ 80 => V
T2: (20 + 60) + 30 + 10 = 120 > 80
(20*2 + 60) + 30 + 10 = 140 ≦ 140 => V
T3: (20) + 60 + 15 = 95 > 80
(20*2) + 60 + 15 = 115 ≦ 160 => V
T4: 同(a)
(c) T1: 20 + 25 = 45 ≦ 80 => V
T2: (20 + 60) + 30 + 10 = 120 > 80
(20*2 + 60) + 30 + 10 = 140 ≦ 140 => V
T3: (20) + 60 + 25 = 105 > 80
(20*2) + 60 + 25 = 125 ≦ 160 => V
T4: 同(a)