課程名稱︰即時系統 課程性質︰選修 課程教師︰郭大維 開課學院：電資學院 開課系所︰資工所、網媒所 考試日期（年月日）︰2013.01.08 考試時限（分鐘）：120 試題 : Fall 2012 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 = 115. (1) Please define the following terminologies (15pts): a. MLC Flash Memory Ans: Flash Memory in which every cell stores more than one bit of information. b. Dynamic Wear Leveling Ans: Only blocks of invalid pages are recycled, where wear leveling is to evenly distribute erases over blocks, and blocks have limited numbers of erasing. c. Configuration Selection Problems Ans: Given a set of configurations, choose a schedulable configuration. d. The Harmonic Base of a Process Set (Hint: Division Graph) Ans: The set of periods of the process set that could not be divided by any other period. e. The Wait Policy for Broadcast Commit in Optimistic Concurrency Control Ans: When T commits at its validation phase, T waits until any high-priority transaction H commits. If H commits, abort T; otherwise, T commits. (2) Please order the Polling Server, the Deferrable Server, the Total Bandwidth Server (TBS). and the Constant Utilization Server (CUS) in terms of the response time to the scheduling of sporadic tasks, for modest workloads (i.e., workloads close to but no larger than the server utilization). Which one of the four is the best in terms of the response time to the scheduling of sporadic tasks, for very heavy workloads (compared to the server utilization)? Which one might be the worst in terms of the response time to the scheduling of sporadic tasks, for light workloads (compared to the server utilization)? You must provide explanation to receive any credits. (16pts) Ans: (A) Deferrable Server < Total Bandwidth Server, Constant Utilization Server < Polling Server, where a < b means a is better than b. (B) Best for heavy workloads: Total Bandwidth Server because sporadic tasks get serviced even the server utilization is over its setup. (C) Worst for light workloads: Polling Server because the other 3 Servers are demand-based. (3) Consider a control system with the following communication graph and system requirements: ■ Sample x at 10 times per second. Then update u. ■ Sample y at 20 times per second. Then update u. Let each one of Function f_x, f_y, and f_s take 2 time units to execute. Please show me the pseudo code by creating tasks by "Decomposition by Critical Timing Constraints" and "Decomposition by Centralizing Concurrency Control". (12pts) x ┌─┐ x' ─→│fx├─┐ └─┘ │ └→┌─┐ u │fs├─→ ┌→└─┘ ┌─┐ │ ─→│fy├─┘ y └─┘ y' Ans: (A) Process XS activated by timer; attribute period = 10, deadline = 10; x = sensor_x(); x' = f_x(x); rendezvous S; end XS and Processes YS and S (B) Process XYS /* Define skip_y() */ activated by timer; attribute period = 10, deadline = 10 x = sensor_x(); x' = f_x(x); if not skip_y() then y = sensor_y(); y' = f_y(y); u = f_s(x', y') end XYS (4) Consider real-time disk scheduling. Please answer the following questions. You might provide explanation to receive any credits. (12pts) (A) Is SCAN better than the Shortest Seek Time First algorithm (SSTF) in meeting the deadlines of requests? (B) Consider a policy that always service the request with the highest priority p_i = f(d_i, b_i) = a*d_i + (1-a)*b_i, where 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. Suppose that we like to improve this policy by reducing the disk arm movements with the considerations of 3 requests at a time. What would you do? Ans: (A) Yes. SCAN is better because SSTF might cause the starvation of a request with any deadline. (B) One way is to group every 3 requests in the queue ordered by their priorities and then service each group by C-SCAN. (5) Consider flash memory management. Please answer the following questions. You might provide explanation to receive any credits. (24pts) (A) Why the write throughput of a flash-memory drive drops significantly when it is used for some time? (B) Why the read/program disturb becomes more and more serious recently? (C) FTL is a page-level address translation mechanism. Why it becomes less practical for current products? (D) What is the main challenge in doing wear leveling? (E) Why a block-level mapping mechanism, such as NFTL, usually has more erases (in the run time) than a page-level mapping mechanism does, such as FTL? (F) Please explain the Drain Disturb problem. Ans: (A) It is because garbage collection/erasing starts. (B) It is because flash memory chips become less reliable, and more cells are connected by a bit line or a word line. (C) It is because every page requires the mechanism to keep its mapping information such that the DRAM needs become enormous. (D) It is to know which blocks have less numbers of erasing so far. (E) It is because a block-level mapping mechanism usually has free pages in a to-be-recycled block. (F) Cells sharing a bit line are to be programmed so that their states might be lost, since electrons are tunneled from the floating gate through the gate oxide to the drain. (6) What are the ACID properties of database systems? (8pts) Ans: Atomicity, Consistency, Isolation, and Durability. (7) Compare a main-memory database and a disk-based database. Tell me two advantages of main-memory databases and one of the disadvantages. What would be the main difference in the index designs for these two kinds of databases? (16pts) Ans: (A) Advantages: predictable performance, high performance. Disadvantage: vulnerable in system failure. (B) A disk-based database must have shallow and big-fanout index designs. (8) RWPCP improves PCP by providing read and write locks, where PCP only supports exclusive locks. Please explain how RWPCP guarantees one priority inversion to a real-time transaction that might write data objects? Please prove why there is one priority inversion under 2VPCP. (12pts) Ans: (A) A read lock to a data object will set the RW Priority Ceiling to the highest priority of a writer such that no lower-priority reader can introduce more priority inversions to a potential writer. (B) A high-priority transaction T_H is blocked when its priority is no larger than the RW Priority Ceiling of any data object locked by any other transaction under 2VPCP. The first transaction that might obtain such a lock to block T_H must prevent any other to lock any data object in a mode to block T_H. --

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