課程名稱︰即時系統
課程性質︰選修
課程教師︰郭大維
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2014.11.18
考試時限（分鐘）：150分鐘
試題 :
Fa11 2014 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 102.
(1). Please define the following terminologies (l5 pts):
a. Periodic Process
Ans: Periodic tasks have regular arrival times.
b. A Cyclic Executive Software Architecture
Ans: Operations are implemented as procedures, where the timer calls
each procedure in the list, and a major cycle consists of a
non-repeating set of minor cycles in calling procedures.
c. Deadline Monotonic Scheduling Algonthm
Ans: A job with a sma11er relative deadline has a higher priority.
d. Critical Instant
Ans: A critical instant of a process is an instant at which a request
of that process has the longest response time.
e. Forbidden Region
Ans: In a forbidden region, no scheduling of any process should he
done.
(2) Please explain why a computer system of heterogeneous architectures, e.g.,
one of a CPU, GPUs, and ASICs, is usually more energy-efficient than a
computer system of only a CPU or few homogeneous CPUs? Why a computer
system of multiple CPUs is usually more energy-efficient than a computer
system of only one powerful CPU. (10 pts)
Ans: (a) It is because CPU ASICs and GPU offer different degrees of
flexibility and pover efficiency in their designs so that
workloads can be partitioned to run among them for the best
energy efficiency.
(b) It is because the power function is convex such that having a
good parallelism of task executions among multiple CPUs can run
at a lower speed but have the same performance.
(3) Please answer the following questions in real-time process scheduling: You
must provide explanation to receive any points. (24 pts)
(a) Suppose that the Rate Monotonic Scheduling algorithm (RMS) is adopted
to schedule a real-time process set. Is it possible to observe any
idle time when a real-time process set fully utilizes a processor?
(b) Suppose that the Earliest Deadline First algorithm (EDF) is adopted to
schedule a real-time process set. Is it possible to observe any idle
time when a real-time process set fully utilizes a processor (that is,
any increasing of any process execution time will result in deadline
violation)?
(c) Please explain the definition of the least upper bound of utilization
factor, especially in why a process set with its utilization factor no
larger than the bound must be schedulable!
(d) When process synchronization is needed, why it is very important to
limit the number of priority inversions in real-time process
scheduling?
Ans:
(a) Yes, it is because the least upper bound of the utilization factor of
RMS is less than 100% when the number of processes is more than 2.
(b) No, it is because the least upper bound of the utilization factor of
EDF is 100%.
(c) Given a process set with its utilization lower than the bound, if the
process set is un-schedu1ab1e, then there must exist a process set
with an even lower utilization factor, and the process set fully
utilize the processor. It is a contradiction to the definition of the
bound.
(d) Giving an unlimited number of priority inversions to a process is not
possible to guarantee the schedulability of the process.
(4) Consider process synchronization by the Priority Ceiling Protocol. Please
explain to me why a higher-priority process can only be blocked by at most
one lower-priority process. (8 pts).
Ans: It is because when one lower-priority process locks a semaphore that
can block a higher-priority process, the semaphore locking will
prevent another lower-priority process to lock any semaphore before
the semaphore locking is gone.
(5) For energy-efficient real-time scheduling, we usually try to minimize the
energy consumption and, at the same time, to meet the deadlines of
processes. Please explain why we should try to run at a constant voltage
or speed to minimize the energy consumption? Please summarize the optimal
uniprocessor DVS scheduling algorithm presented in the class (by Frances
Yao, Alan Demers, and Scott Shenker, "A Scheduling Model for Reduce CPU
Energy", FOCS, 1995). (l5 pts).
Ans:
(a) Running at a constant voltage or speed can minimize the energy
consumption because the energy/power consumption function is a convex
function.
(b) The algorithm tries to compute the intensity function values of all
possible durations (YOU MUST DEFINE THE FUNCTION TO GET CREDITS). In
each iteration, the duration of the highest intensity function value
is picked up, and the processes in the duration are scheduled by EDF
and run at the speed of the intensity function value. Then the
duration and its processes are removed, while the ready time and
deadline of the rest processes are revised by taking away the
duration. The algorithm then repeats itself in finding the next
duration of the highest intensity function value until no process is
left.
(6) Total Bandwidth Servers and Sporadic Servers are servers designed for
dynamic-priority scheduling and fixed-priority scheduling, respectively.
When we have multiple Sporadic Servers running together, can we have the
same "starvation" problem as we have seen for Total Bandwidth Servers
(where all sporadic servers are guaranteed in the schedulability analysis)?
Why? How about "fairness" problem in running multiple Sporadic Servers
together? Why? (l0 pts)
Ans: Sporadic Servers would not have the starvation problem because
sporadic processes are guaranteed with budgets. No fairness problem
because no one can over-run for any budget.
(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.)
(20 pts)
┌─────┬─────┬───────┬───────┬─────┐
│ │ T1 │ T2 │ T3 │ T4 │
├─────┼─────┼───────┼───────┼─────┤
│ P_i │ 50 │ 120 │ 200 │ 280 │
│ │(periodic)│ (periodic) │ (periodic) │(periodic)│
├─────┼─────┼───────┼───────┼─────┤
│ C_i │ 10 │ 30 │ 50 │ 60 │
├─────┼─────┼───────┼───────┼─────┤
│Semaphores│ S1(5) │S1(15), S2(20)│S1(20), S2(10)│ S2(20) │
├─────┼─────┼───────┼───────┼─────┤
│ deadline │ 50 │ 110 │ 150 │ 280 │
├─────┼─────┼───────┼───────┼─────┤
│ priority │ 1 │ 3 │ 2 │ 4 │
└─────┴─────┴───────┴───────┴─────┘
(a) Consider periodic process set {T1, T2, T3, T4} without semaphore
sharing and without pre-period deadlines. Show me which process is
schedulable or unschedulable.
(b) Consider periodic process set {T1, T2, T3, T4} without semaphore
sharing but with pre-period deadline. Show me which process is
schedulable or unschedulable.
(c) Consider periodic process set {T1, T2, T3, T4} with semaphore sharing
and pre-period deadline. Show me which process is schedulable or
unschedulable under the priority inheritance protocol. Note that T1
does not lock S2.
Ans:
(a) {T1, T2, T3, T4} = {S, S, S, U}
(b) {T1, T2, T3, T4} = {S, S, S, U}
(c) {T1, T2, T3, T4} = {S, U, S, U}
{B1, B2, B3, B4} = {40, 20, 35, 0}