課程名稱︰即時系統
課程性質︰選修
課程教師︰郭大維
開課學院：電資學院
開課系所︰資工所、網媒所
考試日期（年月日）︰2012.01.11
考試時限（分鐘）：120
試題 :
Fall 2011 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 = 110.
(1). Please define the following terminologies (24pts):
a. The Density of a Sporadic Job
Ans: The density of a sporadic job with an arrival time r_i, maximum
execution time e_i, and the absolute deadline d_i is
e_i / (d_i - r_i).
b. The Critical Instance of AM Multiframe Process
Ans: The critical instance of an AM multiframe process is the beginning
of the period when its peak execution time is requested
simultaneously with the peak execution times of all higher
priority processes.
c. Bulk Erasing of Flash Memory
Ans: Pages are erased in a block unit to recycle used but invalid
pages.
d. The Data Retention Problem of Flash Memory
Ans: Electrons 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.
e. A Query Transaction
Ans: A query transaction consists of only read operations.
f. Absolute/External Consistency
Ans: Data reflect the changing of the external environment.
g. Backward Validation:
Ans: The validation procedure is performed against recently committed
transactions.
h. Final-State Serializability:
Ans: Generate the same final state as a serial schedule does.
(2). Please compare the Total Bandwidth Server (TBS) and the Constant
Utilization Server (CUS) in terms of the possibility of starvation. Please
use their "Replenishment Rule" to explain it. Please define "fairness" for
a server design. (12pts)
Ans:
(A) Under the CUS, when a sporadic job with execution time e arrives at
time t to an empty queue, we do nothing if t < d; otherwise,
d = t + e / u_s, and e_s = e. Under the TBS, we simply set d to
(max(d, t) + e / u_s), and e_s = e. In other words, consider two
TBS's with their sizes both being equal to 0.5. TB1 remains
backlogged in (0, t), but TB2 is idle. Between t and 2t, jobs with
execution time less than t arrives and keep TB2 backlogged. As a
result, it is unfair in (t, 2t) for TB1 such that TB1 would suffer
from starvation in (t, 2t). It would not be the case for the CUS.
(B) The fraction time of the processor time in the interval attained by
each server that is backlogged throughout the interval is proportional
to the server size within some threshold.
(3). The Period Assignment Problem tries to choose a schedulable configuration
from a given set of adaptive processes (τ_i, {period-candidates},
utilization). The problem could be redefined as the Configuration
Selection Problem, in which we try to choose a schedulable configuration
{(τ_i, period, utilization)} form a given set of configurations (those
are derived from the set of adaptive processes). Please explain why the
existence of a solution to a Period Assignment Problem implies the
existence of a corresponding solution to the corresponding Configuration
Selection Problem. Please explain why the Period Assignment Problem is,
in general, more difficult than the Configuration Selection Problem.
(10pts)
Ans:
(A) The period of each task in a solution to a Period Assignment Problem
would form a schedule configuration solution together to the
corresponding Configuration Selection Problem.
(B) It is because the combination of period combination s of a Period
Assignment Problem implies a potentially exponentially growing number
of configurations of the Configuration Selection Problem.
(4). Three decomposition strategies are discussed in system synthesis:
"Decomposition by Critical Timing Constraints", "Decomposition by
Centralizing Concurrency Control", "Decomposition by Distributed
Concurrency Control". Which one is closer to the event-driven software
architecture? Which one is closer to the pipelined software architecture?
Which one is closer to the timeline software architecture? No explanation
is needed. (9pts)
Ans: (A) Decomposition by Critical Timing Constraints
(B) Decomposition by Distributed Concurrency Control
(C) Decomposition by Centralizing Concurrency Control
(5). Consider disk scheduling. Please answer the following questions: You might
provide explanation to receive any credits. (18pts)
(A) Why EDF, that always services a disk request with the most urgent
deadline, could not have a good performance in disk scheduling?
(B) Why the Shortest Seek Time First algorithm (SSTF) could not always
satisfy the deadline requirement of disk requests with deadlines?
(C) Suppose that a disk is heavily loaded with disk requests, is C-SCAN
still better than SCAN in terms of the average waiting time in
servicing disk requests.
Ans:
(A) It is because EDF does not consider the seek time overheads in disk
movement.
(B) It is because SSTF might cause the starvation of a request with any
deadline.
(C) Yes. it is because the average waiting time of C-SCAN is still a half
of the total time in one way of service (and one way of quick movement
of a disk head without any service), where average waiting time of
SCAN is still a half of the total time in two ways of services.
(6). In the design of the flash-translation layer for flash memory, we need to
maintain the mapping information of logical block addresses and physical
addresses because of the out-place update characteristics of flash memory.
Why a block-level address mapping design, such as NFTL, usually has a
worse flash-memory space utilization than a page-level address mapping
design such as FTL? Why static wear leveling could help to improve the
lifetime of flash memory, compared to dynamic wear leveling? (15pts)
Ans:
(A) Many blocks (such as replacement blocks of NFTL) are garbage-collected
before all of their pages written.
(B) It is because static wear leveling move data over any blocks, while
dynamic wear leveling only move data and recycles blocks with dead
pages. As a result, erases are more even distributed over block.
(7). Please explain what "Durability" means for the ACID properties of database
systems. What is the relationship between the concept of serializability
and the concept of "Durability"? (8pts)
Ans: (A) Durability: permanently committed updates.
(B) No relation.
(8). Please answer the following questions for the priority ceiling protocol
(PCP), read/write priority ceiling protocol (RWPCP), the two-version RWPCP
(2VPCP), the Basic Aborting Protocol (BAP): You must provide explanation
to receive any credit. (14pts)
(A) Please explain the extension part of RWPCP, compared to PCP. (4pts)
(B) Please explain the extension part of BAP, compared to PCP. (4pts)
(C) When 2VPCP is used in a multiprocessor environment, will the number of
priority inversion be more than one? (6pts)
Ans:
(A) Read and write locks are considered with write/absolute priority
ceilings are introduced.
(B) Higher priority processes now have an option to abort lower-priority
transactions that might introduce too much blocking time to
themselves.
(C) It could be an example similar to RWPCP.