课程名称︰即时系统
课程性质︰选修
课程教师︰郭大维
开课学院：电资学院
开课系所︰资工所、网媒所
考试日期（年月日）︰
考试时限（分钟）：120
试题 :
Spring 2008 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 = 107.
(1) Please define the following terminologies (24pts):
a. Durability in the ACID Property for DBMS
Ans: Durability: permanently committed updates.
b. An Execution Trace of a Processor
Ans: An execution trace of a processor is a mapping F from non-negative
integers to the set of nodes in a communication graph G plus a null
symbol φ such that F(i) = u if u is executed in the time interval
[i, i+1].
c. MLC Flash Memory
Ans: Each cell of MLC flash memory contains more than one bit
information.
d. Relative/Temporal Consistency
Ans: The ages of data read by a transaction are within a tolerable
length of time.
e. Query Transactions
Ans: A query transaction consists of only read operations.
f. C-SCAN in Disk Scheduling
Ans: Start at one end of the disk, and moves toward the other end,
servicing requests as it reaches each track, until it gets to the
other end of the disk. When the head reaches one end, it
immediately returns to the beginning of the disk.
g. The Data Retention Problem of Flash Memory
Ans: Electron stored in a floating gate might be lost such that the
loss of electrons will sooner or later affects the charging status
of the gate!
h. Dynamic Aborting Protocol (DAP)
Ans: When a lower priority transaction introduces excessive blocking
to a higher priority transaction, then higher priority transaction
will abort the lower priority transaction. DAP does run-time
calculation of tolerable blocking time.
(2) In the Graph-Based Model for system synthesis, what happens when a task
graph C is said being executed in the interval [t_1, t_2]. (6pts)
Ans: There is a multiset of functional-element (vertices) executions in
[t_1, t_2] which is consistent with the partial ordering C.
(3) Please explain why the number of priority inversion under RWPCP may be more
than one when there are more than one processors in the system? If PCP is
adopted (instead of RWPCP), can the number of priority inversion under PCP
be more than one? If 2VPCP is adopted (instead of RWPCP), can the number of
priority inversion under 2VPCP be more than one? You must explain why to
receive any credit. (15pts)
Ans:
a. The priority gap between the priority of a high-priority transaction
executing on a processor and the read write priority ceiling of the data
objects locked by the transaction.
b. No. The maximum number of priority inversion is one because the priority
ceiling of data objects locked by a transaction is no less than the
priority of the transaction.
c. Yes. The maximum number of priority inversion can be more than one
because of the same reason for Question 3.a.
(4) Please answer the following questions regarding flash memory: (12pts)
(a) Why garbage collection is needed for flash-memory storage systems?
(b) What is static wear-leveling?
(c) Why FTL is not feasible to large-capacity storage systems?
Ans:
(a) It is because of out-place updates.
(b) Static Wear Leveling does garbage collection over any block of flash
memory. It rewrites over another free page with erasing over any
blocks.
(c) It is because the adopting of a page-level address translation
mechanism by FTL needs a huge Address Translation Table.
(5) Consider system synthesis, where three methods are presented:
"Decomposition by Critical Timing Constraints" (CTC), "Decomposition by
Centralizing Concurrency Control" (CCC), and "Decomposition by Distributed
Concurrency Control" (DCC). In the presentations for real-time system
architectures, there are "Timeline", "Event-Driven Architecture", and
"Pipelined Architecture". Which one of the architectures is closest to CTC?
Which one of the architectures is closest to DCC? We must explain why in
order to receive any points. (12pts)
Ans:
■ Event-Driven Architecture = CTC
◆ "Decomposition by Critical Timing Constraints" (CTC) has a process
for each timing constraint, and it is triggered by the occurrence of
an event.
■ Pipelined Architecture = DCC
◆ DCC partition the required computation into as many processes as
possible, where schedulable tasks are triggered by I/O completion,
timer events, and inter-task messages, and the system can be
described as a set of pipelines of task invocations. Each task under
DCC is like a task in a pipelined architecture.
(6) Consider the history of the two transaction executions, where r_A(x) and
w_A(X) denote a read and a write by a transaction A. Please answer the
following questions. (16pts)
r_A(x), w_A(X), r_B(x), r_B(y), r_A(y), w_A(y)
(a) Regarding the ACID requirements of database systems, which one of them
is violated?
(b) Is it conflict-serializable? You must prove why it is or why it is not?
(c) Is it view-serializable? You must prove why it is or why it is not?
Ans:
(a) Isolation
(b) No. Show that there is a cycle in the serializability graph or the
non-existence of a swapping sequence of non-conflicting operations
toward a serial schedule.
(c) No. Since it is not conflict-serializable, it is not view-serializable.
(7) There are at most 64 tasks on uC/OS-II. uC/OS-II provides deterministic
execution time for task scheduling. What is the priority of the idle task
of uC/OS-II? It's source is open. Is it free for commercial usages? (6pts)
Ans:
a. 63
b. No!
(8) When real-time disk scheduling is considered, please answer the following
two questions: (12pts)
(a) Is the shortest-seek-time-first (SSTF) algorithm an optimal algorithm
in the maximizing the number of completed requests within any given
time interval. Assume that rotation delay does not cost any time, and
each disk request can be serviced with the same amount of time. (8pts)
(b) Suppose that there is a read/write head for each cylinder of a hard
disk. Assume that each disk request can be serviced with the same
amount of time. Please define a disk scheduling algorithm similar to
the SSTF algorithm. (4pts)
Ans:
(a) It is optimal because the service time of a request consists of its
seek time and transfer time. SSTF minimizes the total seek time of
requests.
(b) Always service the next subsequent request when the disk rotates.