課程名稱︰即時系統 課程性質︰選修 課程教師︰郭大維 開課學院：電資學院 開課系所︰資工所、網媒所 考試日期（年月日）︰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. --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.48.23 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1423792527.A.894.html ※ 編輯: rod24574575 (111.250.48.23), 02/13/2015 09:57:11