課程名稱︰即時系統
課程性質︰選修
課程教師︰郭大維
開課學院：電資學院
開課系所︰資工所、網媒所
考試日期（年月日）︰2014.01.07
考試時限（分鐘）：120
試題 :
Fall 2013 Final-Exam (答案卷) RTS
Read each question over carefully several times. Answer all questions in the
space provided. The exam is two hours long. Total score = 106.
(1) Please define the following terminologies (24pts):
a. Decomposition by Distributed Concurrency Control (DCC) or Maximizing
Concurrent Process
Ans: Partition the required computation into as many processes as
possible so as to maximize the parallelism!
b. The Write Once Property of Flash Memory
Ans: No writing on the same page unless its residing block is erased.
c. Data Retention of Flash Memory
Ans: Electrons stored in a floating gate might be lost such that the
loss of electrons will sooner or later affect the charging status
of the gate.
d. Main-Memory Database
Ans: A database in which all of its data reside in the memory.
e. Conflict Serializability
Ans: The order of conflicting operations is as the same as that of a
serial schedule.
f. Broadcast Commit
Ans: When a transaction commits, it tells all the transactions that it
conflicts with so that they abort.
g. Backward Validation
Ans: The validation procedure is performed against recently committed
transactions.
h. Optimistic Concurrency Control
Ans: Three phases for each transaction execution. In the read phase,
transactions read from the database and write to their local space.
In the validation phase, serializability violation is checked up.
If it passes, the transaction can go to the write phase to commit
its writes to the database.
(2) For more precise schedulability tests, the divisibility of the periods of
tasks is considered such that two efficient schedulability tests were
presented in the class: (1) Suppose that K is the number of fundamental
frequencies (or called harmonic chains) for a set of N periodic tasks. The
least upper bound of utilization factor is K(2^(1/k) - 1). (2) Suppose
that the set of the (i-1) highest priority tasks, denoted as T_(i-1), is
schedulable, and R is the number of roots in the set of the i highest
priority tasks, denoted as T_i. T_i is schedulable if the total utilization
factor of T_i is no more than R(2^(1/R) - 1). Please answer the following
questions: (12pts)
(a) Which one of the two tests is better? Please provide us your argument
as a simple proof.
(b) The second test is extended to tasks of the Multiframe Model. Please
define the Multiframe model. What is an Accumulative Monotonic
Multiframe task?
Ans:
(a) The second test is better because the number of fundamental frequencies
is no smaller than the number of roots.
(b) A multifrarne real-time process t_i is a tuple (G_i, p_i), where G_i is
an array of N_i execution times ((c^0)_i, (c^1)_i, ... , (c^(N_i-1))_i)
for some N_i ≧ 1, and p_i is the period of t_i. An Accumulative
Monotonic Multiframe task must satisfy the following constraint:
j k mod N_i x+j k mod N_i
Σ C ≧ Σ C , 1≦x≦(N_i - 1), 1≦j≦(N_i - 1)
k=0 i k=x i
(3) Consider a control system with the following communication graph and system
requirements:
□ Sample x at 20 times per second. Then update u. │z
□ When z changes its value, update u within 40ms. ↓
┌─┐
Let each one of Function f_x, f_y, and f_s take │fz│
10ms to execute. Write the pseudo code by creating └┬┘
2 tasks by "Decomposition by Critical Timing │z'
Constraints" and then provide a Cyclic Executive ↓
schedule for the requirements. Explain that the x ┌─┐ x' ┌─┐ u
schedule could satisfy the second constraint by ─→│fx├─→│fs├─→
"Latency of K Time Unit" concept. (12pts) └─┘ └─┘
Ans:
(a) Task XS Task ZS
activated by timer; activated by z;
attribute period = 50ms, attribute deadline = 40ms
deadline = 50ms; z = sensor_z(); z' = f_z(z);
x = sensor_x(); x' = f_x(x); rendezvous S;
rendezvous S; end ZS
end XS
(b) X Z S Z S X Z S Z S
─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─────────
0 50 100
每40ms可看到ZS執行 (不論從什麼時候開始)
(4) Consider the following disk scheduling algorithms: SCAN, C-SCAN,
Shortest-seek-time-first (SSTF), and EDF. Please answer the following
questions. You might provide explanation to receive any credits. (20pts)
(A) Which one is starvation-free? (Hint: There could be one or more.)
(B) Which one might have the best throughput? Which one might have the
worst throughput?
(C) The combination of SSTF and EDF gives us a the weighted scheduling
algorithm that always service the request with the highest priority,
e.g., p_i = f(d_i, b_i) = a×d_i + (1-a)×b_i. Please show me how to
combine SCAN and EDF to have a real-time disk scheduling algorithm.
PS. a, d_i, and b_i are a design factor, the deadline, and the time that
the disk arm has to take to move from its current position to serve
the request, respectively.
Ans:
(A) SCAN and C-SCAN are starvation-free because the maximum response time
of SCAN and C-SCAN are bounded by one and a half of the round-trip
service time, respectively.
(B) SSFT might have the best throughput because of the smallest overheads.
EDF might have the worst throughput because it has the worst
throughput.
(C) (1) Classify requests into classes based on their EDF priorities.
(2) Service requests in the same class in terms of SCAN.
(3) Service classes in order of their priorities.
(5) Please answer the following questions for flash memory management. You
might provide explanation to receive any credits. (15pts)
(A) Compare a page-level address translation mechanism FTL and a
block-level mapping mechanism NFTL. Why the utilization of a
block-level mapping mechanism is usually worse than that of a
page-level address translation mechanism?
(B) Why static wear leveling is better than dynamic wear leveling?
(C) Please point out three different things between flash memory and phase
chance memory.
Ans:
(A) It is because garbage collection often starts when there are still
some free pages in a block for garbage collection.
(B) It is because static wear leveling can move cold data around regardless
of whether their blocks have any dead pages. In this way, erases can be
more evenly distributed over the entire flash memory space.
(C) PCM is bit-alterable, does not need erases, and byte-addressable.
(6) ACID stands for Atomicity, Consistency, Isolation, and Durability. Which
one of the properties is violated for the following example? You must
provide explanation. (8pts)
T1 (x=x-100, y=y+100) T2
r(x)
w(x)
r(x)
r(y)
r(y)
w(y)
Ans: Isolation is violated because dirty data are seen by T2, even though
Consistency is also an acceptable answer...
(7) With the absolute and write priority ceilings, RWPCP give read and write
locks different ceilings to block transactions in reading and writing data.
Please answer the following two questions: (15pts)
(a) Please give me the definitions of the absolute and write priority
ceilings under RWPCP.
(b) Please explain why there is no deadlock under RWPCP.
(c) Please define the Two-Version Read/Write Priority Ceiling Protocol.
Ans:
(A) The absolute priority ceiling = the highest priority of the transaction
might read or write the data object.
The write priority ceiling = the highest priority of the transaction
might write the data object.
(B) Proof: (1) first show that there is no chained blocking;
(2) Show that no deadlock exist of two transactions.
(C) There are working and consist versions for each data object. Writing
is to a working version with a write lock and then is followed by a
certify lock to copy the working version to its consistent version.
Reading is done to a consistent version. The rest follows the RWPCP by
having the absolute priority ceiling for a certify lock and the write
priority ceiling for read and write locks.