课程名称︰即时系统
课程性质︰选修
课程教师︰郭大维
开课学院：电资学院
开课系所︰资工所、网媒所
考试日期（年月日）︰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