※ [本文转录自 NTU-Exam 看板 #1JgaNs-d ] 作者: irritum (′・ω・‵) 看板: NTU-Exam 标题: [试题] 102下 郭大维 作业系统 期末考+解答 时间: Wed Jun 25 11:45:53 2014 课程名称︰作业系统 课程性质︰必修 课程教师︰郭大维 开课学院：电机资讯 开课系所︰资讯工程 考试日期（年月日）︰2014/6/18 考试时限（分钟）：150 是否需发放奖励金：是 （如未明确表示，则不予发放） 试题 : The eaam is 150 minutes long. The total score is 105 pts. Please read the questions carefully. 1. Terminologies (12pts). a. The Second Reader-Writers Problem Once a writer is ready, it performs its write asap! b. Binary Semaphore A semaphore is like a variable S being only accessible by two atomic operations : wait() and signal(). For a binary semophore, no matter how many times we signals it, the maximum value is 1. c. Memory Transaction A sequence of memory read-write operations that are atomic. d. Absolute Code (Hint : Binding Time) It refers to a program, where the binding times is at the compile time. 2. Please provide answers to the following problem: You must provide explanation to receive any credits. (8pts) a. Please provide the reason for the existence of the critical section problem. (Hint: Processes share variables.) (4pts) b. Suppose that there is no critical section problem for a set of processes. Is it possible to have a deadlock among the processes of the set? (Assumption: The only thing shared among processes are variables. No other resource sharing among the processes.) (4pts) a. It is because processes might share variables (or cooperate) such that some processes might update variables while others are reading or updating some of the variables. As a result, the outcome of their executions depends on the particular order of process scheduling. b. No, it is because the processes of the set have no sharing of any variables (and any resource) such that no locking-orientes behaviors could result in hold-and-wait. 3. Please explain the difference between the following requirments to a solution to the critical section problem: Progress and Bounded Waiting. (8pts) The progress requirement has two parts: (1) Only processes not in their remainder section can decide which will enter its critical section. (2) The section cannot be postponed indefinitely. The first part has nothing to do with the Bounded Waiting requirement, but the difference between the second part and the Bounded Waiting could be explained by one of the Peterson solutions (i.e., the first solution in the class) in which one process ends before the other such that the variable "turn" is not switched to the right status. 4. Please revise the following solution to the first reader-writers problem such that a writer only needs to wait for at most 5 readers. (8pts) ┌────────────┐ ┌────────────┐ │Writer: │ │Reader: │ │ wait(wrt); │ │ wait(mutex); │ │ ..... │ │ readcount++; │ │ writing is performed │ │ if(readcount == 1) │ ←≧5 │ ..... │ │ wait(wrt); │ │ signal(wrt); │ │ signal(mutex); │ └────────────┘ │ .....reading..... │ │ wait(mutex); │ │ readcount--; │ │ if(readcount == 0) │ │ signal(wrt); │ │ signal(mutex); │ └────────────┘ 5. Why the existence of a cycle in the Resource Allocation Graph of a process set denotes a deadlock, where each resource has one instatnce? (5pts) It is because the cycle shows the circular wait of the processes in the cycle. 6. Given the following snapshot of the system: Please determine whether there is currently a deadlock. (5pts) ┌─┬─────┬─────┬─────┐ │ │Allocation│Requests │Available │ │ │ A B C│ A B C│ A B C│ ├─┼─────┼─────┼─────┤ │P0│ 2 0 1│ 0 1 2│ 0 1 1│ ├─┼─────┼─────┼─────┤ │P1│ 1 1 1│ 2 0 1│ │ ├─┼─────┼─────┼─────┤ │P2│ 0 2 0│ 2 2 2│ │ ├─┼─────┼─────┼─────┤ │P3│ 0 0 2│ 0 1 1│ │ └─┴─────┴─────┴─────┘ No, there is a sequence <P3, P0, P1, P2> such that Finish[i] = true. 7. Please answer these questions for memory managment. You must provide explanation to receive any credits. (15pts) a. The Memory Management Unit (MMU) is responsible to the translation of a logical address into a physical address. Can MMU be implemented as software? (5pts) b. What is the advantage of Paging in terms of fragmentation, composed to Dynamic Partitions with Contiguous Allocation? (5pts) c. What is the advantage of Dynamic Partitions with Conguous Allocation in terms of the effective memory access time, compared to Paging? (5pts) a. No, because if would be too slow b. Paging can avoid external fragmentation and has only little internal fragmentation problem. c. The effective memory access time of Dynamic Partition is always the memory access time, while paging is slowed down to 2*memory access time without TLB. 8. Given the following reference string, which reference causes a page fault under the LRU 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) 3 1 0 2 3 0 4 5 0 6 0 6 ┌──────┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐ │ │ 3│ 1│ 0│ 2│ 3│ 0│ 4│ 5│ 0│ 6│ 0│ 6│ ├──────┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤ │ │ 3│ 3│ 3│ 2│ 2│ │ 4│ 4│ │ 6│ │ │ │frames │ │ 1│ 1│ 1│ 3│ h│ 3│ 5│ h│ 5│ h│ h│ │ │ │ │ 0│ 0│ 0│ │ 0│ 0│ │ 0│ │ │ ├──────┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┼─┤ │ │ │ │ │ 3│ 1│ │ 2│ 3│ │ 4│ │ │ │replacements│ │ │ │↓│↓│ │↓│↓│ │↓│ │ │ │ │ │ │ │ 2│ 3│ │ 4│ 5│ │ 6│ │ │ └──────┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘ 9. Given a computer system with a 52-bit virtual address, let the physical address be of 64-bit, and the system is only word-addressable, and every word is of 8 bytes. Assume that evrey page is of 8 KB with 8 bytes per page entry in the page table. Please answer the following questions : (23pts) a. What would be the maximum number of frames owned by a process? What is the maximum logical address space for a process in terms of bytes? (10pts) b. Suppose that TLB is adopted for paging, and there is only one level for paging. Let the memory access time and TLB access time be 100ns and 10ns, respectively. When the TLB hit ratio is 98%, what is the effective memory access time? (5pts) c. Suppose that we have multi-level paging. How many levels do we have in multi-level paging? What is the effective memory access time now (continued from the above subproblem)? (8pts) a. 2^42 pages ; 2^52 * 2^3 bytes b. EMAT = 2% * 210 + 98% * 110 , unit = ns c. 5 levels; EMAT = 2% * 610 + 98% * 110 10. For virtual memory management, the adopting of an inverted page table cane avoid storing the page table of every process in the main memory. One common way to eliminate lengthy table lookup time is to adopt the Hash Table. (16pts) a. Suppose that there is no page fault, no hash table miss or collision, and no TLB implementation, and the Hash Table is in the main memory. When the memory access time is 100ns, what is the effective memory access time because of the adopting of an inverted page table and the Hash Table? (6pts) b. Suppose that a miss in the Hash Table lookup also means a page fault (in memory access) and vice versa, and p is the probability of a page fault. ma is memory access time (i.e., 100ns), and pft is the page fault time for a page table retrieval OR a page retrieval (including its memory access). Please define the effective access time. (Hint: The effective memoy access time defined in the texbook is equal to (1 - p) * ma + p * pft, when there is no inverted page table). (10pts) a. 200ns b. (1 - p) * 2 * ma + p * (ma + 2 * pft) --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.112.217.52 ※ 文章网址: http://webptt.com/cn.aspx?n=bbs/NTU-Exam/M.1403667958.A.FA7.html

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