※ [本文轉錄自 NTU-Exam 看板 #1LgXXQkA ] 作者: rod24574575 (天然呆) 看板: NTU-Exam 標題: [試題] 103下 郭大維 作業系統 期末考+解答 時間: Sat Jul 18 17:11:51 2015 課程名稱︰作業系統 課程性質︰必修 課程教師：郭大維 開課學院：電資學院 開課系所︰資工系 考試日期（年月日）︰2015.06.24 考試時限（分鐘）︰ 試題 : Operating Systems Final Exam Spring 2015 The exam is 150 minutes long. The total score is 102pts. Please read the questions carefully. 1. Terminologies (18pts). a. Starvation Ans: A process wait infinitely without receiving its requested resource! b. TLB Reach (Hint: Translation Look-aside Buffers is TLB) Ans: The address space that is covered by the TLB. c. Paged Segmentation (Hint: IA-32 Segmentation) Ans: Divide segments further into pages. That is, having Paging for each segment. d. Slab Allocation (Hint: Kernel Memory Allocation) Ans: The memory is partitioned into slabs, that are physically contiguous pages and contain objects. A cache is of one or more slabs. When an object is requested, it is allocated from a slab. e. Working Set Ans: The working set is an approximation of locality. f. Soft Link Ans: It is implemented as a file that contains a pathname. 2. There are 4 necessary conditions for deadlocks. Which necessary condition is to fail if we request every process to acquire all of its needed resources before it starts execution? Which necessary condition is to fail if every resource in a system is sharable at any time? (Hint: Deadlock Prevention) (8pts) Ans: (a) Hold and Wait (b) Mutual Exclusion. 3. Given the following snapshot of the system: Please determine whether the system is safe? If it is safe, you must show me one safe sequence. If not, show me that there is no safe sequence. (5pts) ┌─┬──────┬──────┬──────┐ │ │ Allocation │ Max │ Available │ │ │ A B C D │ A B C D │ A B C D │ ├─┼──────┼──────┼──────┤ │P0│ 1 2 0 1 │ 2 2 1 2 │ 0 1 1 1 │ ├─┼──────┼──────┼──────┤ │P1│ 1 0 0 2 │ 2 0 1 2 │ │ ├─┼──────┼──────┼──────┤ │P2│ 2 1 0 1 │ 2 2 1 2 │ │ ├─┼──────┼──────┼──────┤ │P3│ 2 0 1 1 │ 3 1 1 1 │ │ └─┴──────┴──────┴──────┘ Ans: Yes, there is a sequence <P2, P0, P1, P3>. 4. Address binding time could be at the compile time, loading time, or execution time. What is the address binding time for "Paging"? Will there be any external fragment for "Paging"? You must provide explanation to receive any points. (8pts) Ans: (a) execution time. (b) No external fragment because every process is partitioned into a number of pages to fit in frames of the physical memory. 5. Given the following reference string, which reference causes a page fault under the FIFO algorithm. Please also show us which page is replaced when a page replacement occurs? Suppose that we have 3 available frames, which are empty initially. (5pts) 1 2 3 2 1 5 0 2 3 0 1 4 5 Ans: ┌────────┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐ │Reference String│１│２│３│２│１│５│０│２│３│０│１│４│５│ └────────┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘ ┌────────┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐ │ Frame #1 │１│１│１│ │ │５│５│５│３│ │３│３│５│ ├────────┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤ │ Frame #2 │ │２│２│ │ │２│０│０│０│ │１│１│１│ ├────────┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤ │ Frame #3 │ │ │３│ │ │３│３│２│２│ │２│４│４│ └────────┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘ ┌────────┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐ │ Page │ │ │ │ │ │１│２│３│５│ │０│２│３│ │ Replacement │ │ │ │ │ │↓│↓│↓│↓│ │↓│↓│↓│ │ │ │ │ │ │ │５│０│２│３│ │１│４│５│ └────────┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘ 6. Please answer these questions for memory management. You must provide explanation to receive any credits. (20pts) a. Please compare "Paging" and "Segmentation" in terms of address translation. Please also give me one advantage and one disadvantage of Segmentation, compared to Paging. (10pts) b. What is the motivation in having an Inverted Page Table? (5pts) c. What is the minimum number of frames to execute an instruction ADD (A), (B), (C)? Note (X) is an indirect address. (5pts) Ans: (a) Paging: Page # + Offset; Segmentation: Segment # + Offset. For Address Translation, Segmentation must compare the offset with the segment size, and add the segment base address and the offset for the physical address, where Paging just replace the Page # with the Frame #. Segmentation Advantage: Logic unit per segment, disadvantage: external fragmentation (B) A page table tends to be big and does not correspond to the # of pages residing in the physical memory. We just keep one inverted page table for all processes in the system. (C) 7 frames 7. The performance of Demand Paging could be improved by reducing the page fault probability or the page fault service time. Does Page Buffering helps in reducing the page fault probability or the page fault service time? Do we reduce the page fault probability or the page fault service time if the system gives more frames to a process? You must provide explanation to receive any credits. (10pts) Ans: (a) the page fault service time because the system keeps a pool of free frames to page in needed pages asap. (b) the page fault probability because a reasonable page replacement algorithm will have less page faults. 8. The Second-Chance Algorithm is an LRU approximation algorithm. Please explain why the Second-Chance Algorithm could select the LRU page? (Or explain why recently or actively used pages will not be selected for page replacement.) (8pts) Ans: Actively used pages will often have their reference bits set by MMU so that the Second-Chance Algorithm will always skip them in victim page selection. 9. Please use Table of Open Files (per Process) and the System Open File Table to explain when a parent process and a child process can access the same file with the same file offset pointer. (5pts) Ans: It is because the Table of Open Files of the child process is copied from its parent process such that each corresponding entries points to the same one in the System Open File Table. 10. Given an x86-64 computer system with a 48-bit virtual address, let the system be only byte-addressable. Assume that every page is of 2KB with 8 bytes per page entry in the page table. Suppose that the frame number needs 7 bytes to store. Please answer the following questions: (21pts). a. What would be the maximum number of pages owned by a process? What is the number of frames owned by a process? (6pts) 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, where the above multi-level paging is used. 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) d. Suppose that demand paging is adopted. Let p be the probability of a page fault, and ma be set as 110ns for the memory access time. pft is the page fault time. When pft is 10ms, what is the probability of a page fault so that the effective access time will not be over 120ns. Note that 1ms = 10^(-3)s, 1ns = 10^(-9)s. (5pts) Ans: a. 2^37 pages; 2^37 frames b. 5 levels c. EMAT = (1 - 0.01) * 610 + 0.01 * 110, unit=ns. d. Solve p for 120 >= (1 - p) * 110 + p * pft --

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

※ 發信站: 批踢踢實業坊(ptt.cc) ※ 轉錄者: w4a2y4 (140.112.16.131), 06/16/2017 20:26:34 ※ 編輯: w4a2y4 (140.112.16.131), 06/21/2017 08:44:28