※ [本文转录自 NTU-Exam 看板 #1KZKdhap ] 作者: rod24574575 (天然呆) 看板: NTU-Exam 标题: [试题] 101下 郭大维 作业系统 期末考+解答 时间: Sun Dec 14 16:27:20 2014 课程名称︰作业系统 课程性质︰必修 课程教师︰郭大维 开课学院：电资学院 开课系所︰资工系 考试日期（年月日）︰ 考试时限（分钟）：150 试题 : Operating Systems Final Exam Spring 2013 The exam is 150 minutes long. The total score is 108pts. Please read the questions carefully. 1. Terminologies (21pts). a. Deadlock Ans: A set of process is in a deadlock state when every process in the set is waiting for an event that can be caused by only another process in the set. b. Segmentation Ans: Segmentation is a memory management scheme that supports the user view of memory. c. Working Set (Hint: Thrashing and Frame Allocation) Ans: The working set is an approximation of a program's locality. d. Optimal Algorithm for Page Replacement (OPT) Ans: Replace the page that will not be used for the longest period of time. e. Hard Link (Hint: Acyclic-Graph Directory Ans: A hard link of a file name let its directory entry point to the i-node that describes the file's contents. f. Network-Attached Storage (NAS) Ans: Clients access NAS via a remote procedure call interface such as NFS (for UNIX) or CIFS (for Windows) where NAS has a file system running on it. g. Raw Disk Ans: A partition as a large sequential array of logical blocks. 2. Please provide one advantage and one disadvantage of a deadlock avoidance algorithm (such as the Banker's Algorithm), compared to a deadlock prevention algorithm (such as the one without "Hold-and-Wait"). (6pts) Ans: Advantage: Better resource utilization and/or better system throughput/performance. Dsadvantage: Processes must claim maximum usages of each resource. 3. Given the following snapshot of the system: Please determine whether the current state is safe. (5pts) ┌─┬──────┬───────┬──────┐ │ │ Allocation │Maximum Needs │ Available │ │ │ A B C D │ A B C D │ A B C D │ ├─┼──────┼───────┼──────┤ │P0│ 1 1 2 1 │ 3 1 2 1 │ 0 1 1 0 │ ├─┼──────┼───────┼──────┤ │P1│ 2 1 1 0 │ 2 0 1 1 │ │ ├─┼──────┼───────┼──────┤ │P2│ 1 1 0 1 │ 2 2 2 1 │ │ ├─┼──────┼───────┼──────┤ │P3│ 0 0 1 1 │ 0 1 1 1 │ │ └─┴──────┴───────┴──────┘ Ans: Yes, it is safe bcause there is one sequence is < P3, P1, P2, P0 >. 4. Please answer these questions for memory management. (l6pts) a. Consider the excution of a program by the Overlays method. Is the binding time at the compiling time, loading time, or execution time? (5pts) b. Most mid-term schedulers usually use paging in normal situations, instead of swapping. Please explain why "swapping" is not used by most mid-term schedulers until the number of available free pages falls under a safe threshold for some time. (5pts) c. Please provide two reasons why kernel memory allocation is separated from user-mode memory allocation, e.g., paging. (6pts) Ans: (a) Compiling time. (b) It is because swapping has a lot of cost in swapping in/out processes. That is why it is not used until it is urgent. (c) 1. The kernel might request memory of various sizes, that are often less than a page in size. 2. Certain hardware devices interact directly with physical memory, and the accesses memory must be in physically contiguous pages. 5. The effective access time is equal to (1 - p) * ma + p * pft, where p is the probability of a page fault, ma is memory access time for paging, and pft is the page fault time. Please explain the help of each of these methods in reducing the effective access time, with respect to the above formula (e.g., help on either p, ma, pft, or any 2 or 3 of them): (1) A LRU page replacement algorithm, (2) a good frame allocation algorithm, (3) Page Buffering with a pool of free frames, (4) Pre-paging, (5) a big TLB, (6) Inverted Page Table. You must provide explanation to receive any credit. (24pts) Ans: (1) p (2) p (3) pft (4) pft and/or p with proper explanation (5) ma (6) p because more memory space is saved that is originally used for page tables. 6. Given a computer system with a 32-bit virtua1 address and 4 bytes per page entry, let the physical address be of 24 bits, and the system is only word-addressable, and every word is of 4 bytes. Assume that every page is of 2KB. Please answer the following questions: (l5pts). a. What is the maximum number of pages per process? (5pts) b. Suppose that we have multi-level paging. How many levels do we have in multi-level paging? (5pts) c. Suppose that TLB is adopted for paging, and multi-level page tables are all in the main memory. Let the memory access time and TLB access time be 100ns and 10ns, respectively. When the TLB hit ratio is 99%, what is the effective memory access time? (5pts) Ans: a. 2^23 pages. b. 3 levels. c. EMAT = (1 - 0.99) * 410 + 0.99 * 110, unit = ns 7. What is the maximum number of pages needed for the following instruction: MVC x, y, 4 (4pts) Ans: 6 pages. 8. Given the following reference string, which reference causes a page fault under the Enhanced Second-Chance algorithm. Suppose that we have 4 available frames with Pages 0, 2, 5, and 3 as shown in the following graph, only the reference bit of Page 3 is 0 (others are 1), and the selection pointer starts at Page 2. Please also show us which page is replaced when a page replacement occurs? Let all pages be "not dirty" originally, and every following reference be write (and every dirty bit is not cleared once it is set in this case). (8pts) 5 0 1 4 2 4 3 3 Ans: init│ 5 0 1 4 2 4 3 3 ──┼──────────── 0 │ 0 0 0 0 0 0 3 3 │ 2 │ 2 2 2 4 4 4 4 4 │ 5 │ 5 5 5 5 2 2 2 2 │ 3 │ 3 3 1 1 1 1 1 1 换 换 换 换 3 2 5 0 9. Please explain why he execution of lseek() causes no I/O. (4pts) Ans: only modification of the file offset pointer in the system open file table. 10. Compared to the Shortest-seek-time-first (SSTF) Algorithm, give me one advantage of the Scan (or Elevator) Algorithm? (5pts) Ans: There is no starvation. --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 1.160.224.155 ※ 文章网址: http://webptt.com/cn.aspx?n=bbs/NTU-Exam/M.1418545643.A.933.html ※ 编辑: rod24574575 (140.112.16.189), 12/17/2014 19:45:04

※ 发信站: 批踢踢实业坊(ptt.cc) ※ 转录者: w4a2y4 (140.112.16.131), 06/16/2017 20:26:11