課程名稱︰即時系統
課程性質︰選修
課程教師︰郭大維
開課學院：電資學院
開課系所︰資工所、網媒所
考試日期（年月日）︰2010.01.18
考試時限（分鐘）：120
試題 :
Fall 2009 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 = 100.
1. Please define the following terminologies: (24)
(a) Decomposition by Critical Time Constraints (CTC) in system synthesis:
Ans: Having a process for each timing constraint.
(b) Decomposition by Distributed Concurrency Control (DCC) in system
synthesis:
Ans: Partitioning the required computation into as many processes as
possible to maximize parallelism.
(c) Static Wear Leveling (SWL):
Ans: All physical blocks will be considered as possible candidates of
the victim block for space reclamation (also called garbage
collection).
(d) DC-erasing of a programmed cell of flash memory:
Ans: Some programmed cells might lose stored electrons via tunneling
through the interpoly dielectric and become erroneously erased
during the programming of another cell on the same word line (row).
(e) Forward validation:
Ans: The validation of a transaction is performed against all currently
executing transactions.
(f) Load shedding:
Ans: Kill less important processes (so as to make use of the available
computation resources in the optimal way).
(g) Wait-X policy:
Ans: A transaction T commits if less or equal to X% of the processes
that conflict with T have higher priority than T ; otherwise, T
waits. (Once a conflicting transaction T_H with higher priority
than T commits, T needs to be aborted.) It is often a good choice
that T = 50.
(h) Offspring set in schedulability analysis:
Ans: An offspring set of a periodic process T is a set of processes
whose periods divide the period of T.
2. Consider the potential operations over NAND flash memory, where Flash
Translation Layer (FTL) and Memory Technology Device (MTD) are the two
major layers for flash memory storage systems. Please answer the following
questions: (15)
(a) As a simple FTL implementation, BL associates each logical/virtual
block with a physical block. When the data of a given logical page is
written, they are written to the physical page with the same offset in
the physical block as the offset of the logical page in the
logical/virtual block, provided that the physical page is free.
Otherwise, a new physical block is allocated, and all the valid pages
in the original block are copied to the corresponding pages of the new
block. Please explain why BL might have low space utilization. Please
have comments on garbage collection activities of BL as well. (9)
(b) Please define Single-Level Cell (SLC) and Multi-Level Cell (MLC) flash
memory (3). Please compare SLC and MLC flash memory in terms of cost and
performance as well. (6)
Ans:
(a) The utilization of BL is low because the mapped physical block may be
nearly empty when a new physical block is needed. (This situation is
very possible for skewed access patterns, which reveals high degrees of
temporal locality and a small number of hot pages in the block are
updated frequently.) The garbage collection activities are triggered
frequently on each new block allocation.
(b) ‧ SLC flash memory stores a single bit, while MLC flash memory stores
more than 1 bit of data in each memory cell.
‧ SLC flash memory has higher cost and performance.
3. Please answer the following questions for disk scheduling. (18)
(a) Please compare the First-Come-First-Serve (FCFS),
Shortest-Seek-Time-First (SSTF), SCAN, and C-SCAN algorithms, in terms
of the response time variation, when the disk workload is very light
and when the disk workload is very heavy, respectively. Which algorithms
might cause starvation when the disk workload is very heavy? (14)
(b) Why is the Earliest Deadline First (EDF) not suitable for real-time
disk scheduling? (4)
Ans:
(a) ‧ Very light disk workload:
All the algorithms have similar variations of response time.
‧ Very heavy disk workload: SSTF > FCFS ～ SCAN > C-SCAN.
‧ Only SSTF might cause starvation.
(b) EDF does not consider the lengthy disk seek time and rotational delay
(also called latency delay).
4. Considering the correctness in concurrency control and database designs,
please answer the following questions. (21)
(a) What are the time complexities to determine whether a given schedule is
final-state, view, and conflict serializable, respectively? You only
need to answer "NP-Hard" or "not NP-Hard". (9)
(b) ACID stands for Atomicity, Consistency, Isolation, and Durability.
Which of ACID is/are related to serializability? You must provide
explanation to receive any credits. (8)
(c) When timing constraints are considered in real-time database systems,
define absolute consistency. (4)
Ans:
(a) ‧ Final-state serializable: "NP-Hard".
‧ View serializable: "NP-Hard".
‧ Conflict serializable: "P" or "not NP-Hard".
(b) ‧ Atomicity: unrelated.
‧ Consistency: related, because it determines the consistent state
transformation of database.
‧ Isolation: semantically related but technically unrelated, because
its violation may lead to the visibility of dirty data.
‧ Durability: unrelated.
(c) Data reflect the changings of the external environment.
5. Please explain how the Read/Write Priority Ceiling Protocol (RWPCP) resolves
read and write locks, compared to the Priority Ceiling Protocol (PCP). (8)
Ans:
‧ Locks are classified into read and write locks.
‧ Read locks can be shared, while write locks are exclusive; i.e., there
can be exactly one write lock, or multiple read locks for each data
object at any time.
‧ The write priority ceiling of a data object x is statically defined and
set as the highest priority of all the transactions that may write x.
‧ The absolute priority ceiling of a data object x is statically defined
and set as the highest priority of all the transactions that may read or
write x.
‧ The r/w priority ceiling of a data object x is dynamically defined, set,
and used as follows.
– All transactions that would like to read or write x must have a
priority strictly higher than the current r/w priority ceiling of x.
– If a transaction is allowed to read x, the r/w priority ceiling of x
is set to the write priority ceiling of x. This prevents any
transactions from writing x while still allowing higher priority
transactions to read x.
– If a transaction is allowed to write x, the r/w priority ceiling of x
is set to the absolute priority ceiling of x to prevent all other
transactions from reading or writing x.
6. Why is the predictability of the response time of transactions better in
main-memory database systems (than that in disk or flash memory database
systems)? (8)
Ans:
(a) Main memory databases have smaller transaction durations (Since main
memory is faster than disk).
(b) Main memory databases have have smaller lock granularities (Disk
databases have block (sector) as the data unit of locking).
(c) Main memory databases do not need disk accesses, which is affected by
the rotational delay (latency time) and seek time.
7. Locking is a major method for conservative concurrency control. Consider
the Two-Version Priority Ceiling Protocol (2VPCP) with the following
compatibility table. Suppose that every data object has only one
transaction that may update its value. Can we remove the Certify lock in
2VPCP? In other words, without modifying other parts of the protocol, is
it correct to remove Certify lock? You must provide either proof or
counterexample to receive any credits. (6)
Table 1: Compatibility Table of 2VPCP
────────────────────────
Lock already set Read Write Certify
────────────────────────
Read Request Granted Granted Blocked
Write Request Granted Blocked Blocked
Certify Request Blocked Blocked Blocked
────────────────────────
Ans: No. Without Certify lock, during the certification, there might be
some high priority transactions that erroneously read the
partially-updated data.