課程名稱︰即時系統 課程性質︰選修 課程教師︰郭大維 開課學院：電資學院 開課系所︰資工所、網媒所 考試日期（年月日）︰ 考試時限（分鐘）：120 試題 : Spring 2008 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 = 107. (1) Please define the following terminologies (24pts): a. Durability in the ACID Property for DBMS Ans: Durability: permanently committed updates. b. An Execution Trace of a Processor Ans: An execution trace of a processor is a mapping F from non-negative integers to the set of nodes in a communication graph G plus a null symbol φ such that F(i) = u if u is executed in the time interval [i, i+1]. c. MLC Flash Memory Ans: Each cell of MLC flash memory contains more than one bit information. d. Relative/Temporal Consistency Ans: The ages of data read by a transaction are within a tolerable length of time. e. Query Transactions Ans: A query transaction consists of only read operations. f. C-SCAN in Disk Scheduling Ans: Start at one end of the disk, and moves toward the other end, servicing requests as it reaches each track, until it gets to the other end of the disk. When the head reaches one end, it immediately returns to the beginning of the disk. g. The Data Retention Problem of Flash Memory Ans: Electron 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! h. Dynamic Aborting Protocol (DAP) Ans: When a lower priority transaction introduces excessive blocking to a higher priority transaction, then higher priority transaction will abort the lower priority transaction. DAP does run-time calculation of tolerable blocking time. (2) In the Graph-Based Model for system synthesis, what happens when a task graph C is said being executed in the interval [t_1, t_2]. (6pts) Ans: There is a multiset of functional-element (vertices) executions in [t_1, t_2] which is consistent with the partial ordering C. (3) Please explain why the number of priority inversion under RWPCP may be more than one when there are more than one processors in the system? If PCP is adopted (instead of RWPCP), can the number of priority inversion under PCP be more than one? If 2VPCP is adopted (instead of RWPCP), can the number of priority inversion under 2VPCP be more than one? You must explain why to receive any credit. (15pts) Ans: a. The priority gap between the priority of a high-priority transaction executing on a processor and the read write priority ceiling of the data objects locked by the transaction. b. No. The maximum number of priority inversion is one because the priority ceiling of data objects locked by a transaction is no less than the priority of the transaction. c. Yes. The maximum number of priority inversion can be more than one because of the same reason for Question 3.a. (4) Please answer the following questions regarding flash memory: (12pts) (a) Why garbage collection is needed for flash-memory storage systems? (b) What is static wear-leveling? (c) Why FTL is not feasible to large-capacity storage systems? Ans: (a) It is because of out-place updates. (b) Static Wear Leveling does garbage collection over any block of flash memory. It rewrites over another free page with erasing over any blocks. (c) It is because the adopting of a page-level address translation mechanism by FTL needs a huge Address Translation Table. (5) Consider system synthesis, where three methods are presented: "Decomposition by Critical Timing Constraints" (CTC), "Decomposition by Centralizing Concurrency Control" (CCC), and "Decomposition by Distributed Concurrency Control" (DCC). In the presentations for real-time system architectures, there are "Timeline", "Event-Driven Architecture", and "Pipelined Architecture". Which one of the architectures is closest to CTC? Which one of the architectures is closest to DCC? We must explain why in order to receive any points. (12pts) Ans: ■ Event-Driven Architecture = CTC ◆ "Decomposition by Critical Timing Constraints" (CTC) has a process for each timing constraint, and it is triggered by the occurrence of an event. ■ Pipelined Architecture = DCC ◆ DCC partition the required computation into as many processes as possible, where schedulable tasks are triggered by I/O completion, timer events, and inter-task messages, and the system can be described as a set of pipelines of task invocations. Each task under DCC is like a task in a pipelined architecture. (6) Consider the history of the two transaction executions, where r_A(x) and w_A(X) denote a read and a write by a transaction A. Please answer the following questions. (16pts) r_A(x), w_A(X), r_B(x), r_B(y), r_A(y), w_A(y) (a) Regarding the ACID requirements of database systems, which one of them is violated? (b) Is it conflict-serializable? You must prove why it is or why it is not? (c) Is it view-serializable? You must prove why it is or why it is not? Ans: (a) Isolation (b) No. Show that there is a cycle in the serializability graph or the non-existence of a swapping sequence of non-conflicting operations toward a serial schedule. (c) No. Since it is not conflict-serializable, it is not view-serializable. (7) There are at most 64 tasks on uC/OS-II. uC/OS-II provides deterministic execution time for task scheduling. What is the priority of the idle task of uC/OS-II? It's source is open. Is it free for commercial usages? (6pts) Ans: a. 63 b. No! (8) When real-time disk scheduling is considered, please answer the following two questions: (12pts) (a) Is the shortest-seek-time-first (SSTF) algorithm an optimal algorithm in the maximizing the number of completed requests within any given time interval. Assume that rotation delay does not cost any time, and each disk request can be serviced with the same amount of time. (8pts) (b) Suppose that there is a read/write head for each cylinder of a hard disk. Assume that each disk request can be serviced with the same amount of time. Please define a disk scheduling algorithm similar to the SSTF algorithm. (4pts) Ans: (a) It is optimal because the service time of a request consists of its seek time and transfer time. SSTF minimizes the total seek time of requests. (b) Always service the next subsequent request when the disk rotates. --

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