課程名稱︰即時系統 課程性質︰選修 課程教師︰郭大維 開課學院：電資學院 開課系所︰資工所、網媒所 考試日期（年月日）︰2014.01.07 考試時限（分鐘）：120 試題 : Fall 2013 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 = 106. (1) Please define the following terminologies (24pts): a. Decomposition by Distributed Concurrency Control (DCC) or Maximizing Concurrent Process Ans: Partition the required computation into as many processes as possible so as to maximize the parallelism! b. The Write Once Property of Flash Memory Ans: No writing on the same page unless its residing block is erased. c. Data Retention of Flash Memory Ans: Electrons stored in a floating gate might be lost such that the loss of electrons will sooner or later affect the charging status of the gate. d. Main-Memory Database Ans: A database in which all of its data reside in the memory. e. Conflict Serializability Ans: The order of conflicting operations is as the same as that of a serial schedule. f. Broadcast Commit Ans: When a transaction commits, it tells all the transactions that it conflicts with so that they abort. g. Backward Validation Ans: The validation procedure is performed against recently committed transactions. h. Optimistic Concurrency Control Ans: Three phases for each transaction execution. In the read phase, transactions read from the database and write to their local space. In the validation phase, serializability violation is checked up. If it passes, the transaction can go to the write phase to commit its writes to the database. (2) For more precise schedulability tests, the divisibility of the periods of tasks is considered such that two efficient schedulability tests were presented in the class: (1) Suppose that K is the number of fundamental frequencies (or called harmonic chains) for a set of N periodic tasks. The least upper bound of utilization factor is K(2^(1/k) - 1). (2) Suppose that the set of the (i-1) highest priority tasks, denoted as T_(i-1), is schedulable, and R is the number of roots in the set of the i highest priority tasks, denoted as T_i. T_i is schedulable if the total utilization factor of T_i is no more than R(2^(1/R) - 1). Please answer the following questions: (12pts) (a) Which one of the two tests is better? Please provide us your argument as a simple proof. (b) The second test is extended to tasks of the Multiframe Model. Please define the Multiframe model. What is an Accumulative Monotonic Multiframe task? Ans: (a) The second test is better because the number of fundamental frequencies is no smaller than the number of roots. (b) A multifrarne real-time process t_i is a tuple (G_i, p_i), where G_i is an array of N_i execution times ((c^0)_i, (c^1)_i, ... , (c^(N_i-1))_i) for some N_i ≧ 1, and p_i is the period of t_i. An Accumulative Monotonic Multiframe task must satisfy the following constraint: j k mod N_i x+j k mod N_i Σ C ≧ Σ C , 1≦x≦(N_i - 1), 1≦j≦(N_i - 1) k=0 i k=x i (3) Consider a control system with the following communication graph and system requirements: □ Sample x at 20 times per second. Then update u. │z □ When z changes its value, update u within 40ms. ↓ ┌─┐ Let each one of Function f_x, f_y, and f_s take │fz│ 10ms to execute. Write the pseudo code by creating └┬┘ 2 tasks by "Decomposition by Critical Timing │z' Constraints" and then provide a Cyclic Executive ↓ schedule for the requirements. Explain that the x ┌─┐ x' ┌─┐ u schedule could satisfy the second constraint by ─→│fx├─→│fs├─→ "Latency of K Time Unit" concept. (12pts) └─┘ └─┘ Ans: (a) Task XS Task ZS activated by timer; activated by z; attribute period = 50ms, attribute deadline = 40ms deadline = 50ms; z = sensor_z(); z' = f_z(z); x = sensor_x(); x' = f_x(x); rendezvous S; rendezvous S; end ZS end XS (b) X Z S Z S X Z S Z S ─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼───────── 0 50 100 每40ms可看到ZS執行 (不論從什麼時候開始) (4) Consider the following disk scheduling algorithms: SCAN, C-SCAN, Shortest-seek-time-first (SSTF), and EDF. Please answer the following questions. You might provide explanation to receive any credits. (20pts) (A) Which one is starvation-free? (Hint: There could be one or more.) (B) Which one might have the best throughput? Which one might have the worst throughput? (C) The combination of SSTF and EDF gives us a the weighted scheduling algorithm that always service the request with the highest priority, e.g., p_i = f(d_i, b_i) = a×d_i + (1-a)×b_i. Please show me how to combine SCAN and EDF to have a real-time disk scheduling algorithm. PS. a, d_i, and b_i are a design factor, the deadline, and the time that the disk arm has to take to move from its current position to serve the request, respectively. Ans: (A) SCAN and C-SCAN are starvation-free because the maximum response time of SCAN and C-SCAN are bounded by one and a half of the round-trip service time, respectively. (B) SSFT might have the best throughput because of the smallest overheads. EDF might have the worst throughput because it has the worst throughput. (C) (1) Classify requests into classes based on their EDF priorities. (2) Service requests in the same class in terms of SCAN. (3) Service classes in order of their priorities. (5) Please answer the following questions for flash memory management. You might provide explanation to receive any credits. (15pts) (A) Compare a page-level address translation mechanism FTL and a block-level mapping mechanism NFTL. Why the utilization of a block-level mapping mechanism is usually worse than that of a page-level address translation mechanism? (B) Why static wear leveling is better than dynamic wear leveling? (C) Please point out three different things between flash memory and phase chance memory. Ans: (A) It is because garbage collection often starts when there are still some free pages in a block for garbage collection. (B) It is because static wear leveling can move cold data around regardless of whether their blocks have any dead pages. In this way, erases can be more evenly distributed over the entire flash memory space. (C) PCM is bit-alterable, does not need erases, and byte-addressable. (6) ACID stands for Atomicity, Consistency, Isolation, and Durability. Which one of the properties is violated for the following example? You must provide explanation. (8pts) T1 (x=x-100, y=y+100) T2 r(x) w(x) r(x) r(y) r(y) w(y) Ans: Isolation is violated because dirty data are seen by T2, even though Consistency is also an acceptable answer... (7) With the absolute and write priority ceilings, RWPCP give read and write locks different ceilings to block transactions in reading and writing data. Please answer the following two questions: (15pts) (a) Please give me the definitions of the absolute and write priority ceilings under RWPCP. (b) Please explain why there is no deadlock under RWPCP. (c) Please define the Two-Version Read/Write Priority Ceiling Protocol. Ans: (A) The absolute priority ceiling = the highest priority of the transaction might read or write the data object. The write priority ceiling = the highest priority of the transaction might write the data object. (B) Proof: (1) first show that there is no chained blocking; (2) Show that no deadlock exist of two transactions. (C) There are working and consist versions for each data object. Writing is to a working version with a write lock and then is followed by a certify lock to copy the working version to its consistent version. Reading is done to a consistent version. The rest follows the RWPCP by having the absolute priority ceiling for a certify lock and the write priority ceiling for read and write locks. --

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