課程名稱︰即時系統
課程性質︰選修
課程教師︰郭大維
開課學院：電資學院
開課系所︰資工所、網媒所
考試日期（年月日）︰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