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

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.24.64.31 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1421980390.A.30F.html