課程名稱︰即時系統
課程性質︰選修
課程教師︰郭大維
開課學院：電資學院
開課系所︰資工所、網媒所
考試日期（年月日）︰2015.01.13
考試時限（分鐘）：120
試題 :
Fall 2014 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 = 109.
(1) Please define the following terminologies (15pts):
a. Fundamental Frequency (Hint: The least upper bound of utilization
factor K(2^(1/K) - 1))
Ans: The periods of processes from a fundamental frequency if the
periods can form a number sequence in an increasing order such that
the former number can divide the later one.
b. MLC (Multi-Level Cell) Flash Memory
Ans: Each cell of flash memory stores more than one bit of information.
c. Isolation in ACID
Ans: Invisibility for dirty data.
d. Optimistic Concurrency Control
Ans: The execution of a transaction has 3 stages: Read, validation, and
write stages. In the read stage, no write is performed on the
database. If a transaction passes the validation stage, it can go
to the write stage and commit. If there is a good chance to pass
the validation with serializability violation, then optimistic
concurrency control is preferred.
e. Wait Policy in Broadcast Commit
Ans: When T comes to its validation phase, and a higher priority
transaction H in conflict with T, then T waits until H commits.
If H commits, abort T; otherwise, commit T.
(2) Please answer the following questions in disk scheduling. You might provide
explanation to receive any credits. (15pts)
(A) Why EDF could have very bad performance in scheduling disk requests?
(B) Batch processing ideas are often adopted to improve disk performance,
such as SCAN and C-SCAN. In terms of the disk throughput, which one of
SCAN and C-SCAN might be the best when the disk is heavily loaded?
(C) Please explain why some file allocation methods, such as that under
indexed allocation (like Unix's), could result in bad disk performance?
Ans:
(A) It is because the rotation delay and seek latency are too large.
(B) SCAN might be better than C-SCAN because when the head reaches one end
under C-SCAN, it immediately returns to the beginning of the disk.
That is extra overheads.
(C) It is because the contents of a file will be scattered over different
tracks of a disk.
(3) A software automation strategy might consist of 3 stages: (1) Capture the
computational requirements of the application domain in terms of an
appropriate model. (2) Translate requirements specifications into an
instance of the domain-specific model for resource allocation analysis.
(3) Solve the well-defined optimization problems to minimize chosen
cost/risk criteria. Please answer the following questions: (14pts)
(A) Which one of the stages is for the "Decomposition by Distributed
Concurrency Control (DCC) or Maximizing Concurrent Process" presented
in the class?
(B) The "Decomposition by Centralizing Concurrency Control (CCC) or
Minimizing Inter-process Communication" tries to partition the
computation required by the timing constraints into sets, in which the
computation in each set is assigned to a periodic process. Please give
me two main advantages and one disadvantage of this approach?
Ans:
(a) The second stage.
(b) The advantage: (1) Efficiency is improved by eliminating substantial
redundant computations.
(2) With fewer processes and more independent process,
less inter-process communication may be required.
The disadvantage: Maintainability seems more difficult, especially when
some internal scheduling decision is implemented in a
process.
(4) Please answer the following questions for flash memory and phase change
memory. You might provide explanation to receive any credits. (20pts)
(A) Why there is a need to do garbage collection (of invalid pages) over
flash memory?
(B) Solid-State Disks (SSDs) are made of flash memory. There could be more
than one flash-memory chips per SSD. When hot and cold data are stored
on flash-memory chips, why we should avoid keeping hot data in one or
few flash-memory chips, instead of spreading hot data over chips?
Please give me two reasons. (Note that hot data might be read and/or
updated often).
(C) Phase change memory (PCM) and DRAM can both be read or written in
one-bit unit. Please give me two different characteristics of PCM and
DRAM.
Ans:
(A) It is because of the write once property of flash memory such that no
data can be written to a page unless its residing block is erased
first. It generates invalid pages for garbage collection.
(B) (1) If we keep storing hot data on few chips, it might generates
invalid pages on those chips because hot data might be updated
often. As a result, those chips are updated often and will he
broken soon.
(2) Chips of lots of hot data are accessed more often such that the
workloads among chips are not balanced.
(C) (1) PCM is non-volatile, but DRAM is volatile.
(2) The number of writes to a PCM cell is constrained, but there is no
limit to DRAM cell currently.
(3) PCM has different read and write speeds, but they are the same to
DRAM.
(5) Why View Serializability is the criteria acceptable to justify the
correctness of a schedule, instead of Final-State Serializability? (8pts)
Ans: It is because Final-State Serializability only guarantees the same
final results, as a serial schedule. It does not consider the view of
each transaction.
(6) Why we have better response-time predictability for a main-memory database
system, compared to a disk-based database system? Please give me three
reasons. (12pts)
Ans:
(1) No unpredictability problem of disk access time and page faults.
(2) Less contention due to a smaller transaction duration.
(3) Less contention due to a smaller lock granularity.
(7) RWPCP has absolute and write priority ceilings to implement read and write
locks and to guarantee one priority inversion for each transaction, while
PCP only has priority ceiling to implement exclusive locks, i.e., write
locks. Please answer the following three questions with explanation to get
any credit: (15pts)
(A) Please explain how to set the Read/Write Priority Ceiling (RWPL) of a
data item when the data item is locked in a read mode?
(B) When there are multiple processors, how to set the Read/Write Priority
Ceiling (RWPL) of a data item when the data item is locked in a read
mode by a process τ so as to guarantee one priority inversion
(as presented in the class)?
(C) The Two-Version Read/Write Priority Ceiling Protocol (2VPCP) further
extends RWPCP by having the working version and consistent version for
each data item, where the same definitions of absolute and write
priority ceilings are used. How 2VPCP set the Read/Write Priority
Ceiling (RWPL) of a data item when the data item is locked in a write
mode?
Ans:
(A) RWPL = write priority ceiling
(B) RWPL = max(write priority ceiling, the priority of τ)
(C) RWPL = write priority ceiling.
(8) Aborting gives a higher-priority transaction a chance to abort a
lower-priority transaction when the later might block the former for too
long. The Basic Aborting Protocol (BAP), the Table-Driven Aborting Protocol
(TAP), and the Dynamic Aborting Protocol (DAP) are presented. Please
explain how TAP improves BAP in the miss ratio of transaction executions?
Please explain how DAP improves BAP in the miss ratio of transaction
executions? (10pts)
Ans:
(A) TAP improves BAP because TAP considers the binary relationship between
any pair of transactions whether one can abort the other. In this way,
potentially less aborting occurs.
(B) DAP improves BAP because DAP considers the current tolerable blocking
time of a transaction based on the current load before some aborting
happens so that less unnecessary aborting occurs.