课程名称︰作业系统 课程性质︰必修 课程教师︰郭大维 开课学院：电资学院 开课系所︰资工系 考试日期（年月日）︰2012.6.20 考试时限（分钟）：150分钟 是否需发放奖励金：是 （如未明确表示，则不予发放） 试题： The exam is 150 minutes long. The total score is 112pts. Please read the questions carefully. 1. Terminologies (21pts). a. Condition Variable (Hint: Monitor) b. Stable Storage c. 50-Percent Rule for the First-Fit Algorithm (Hint: Dynamic Partitioning) d. Virtual Memory e. Lazy Swapper f. Network Information Service (NIS or Yellow Pages from SUN) g. Scan (or Elevator) Algorithm (Hint: Disk Scheduling) 2. Please answer the following question on process synchronization: (18pts) a. Synchronization hardware might make programming easier for process synchronization. Please explain why interrupt disabling works for uniprocessor environments to avoid the race condition. (6pts) b. There are three requirements for a solution to critical section problem. Please tell me which requirement might not be satisfied for solutions based on semaphores with priority-waiting queues. You must provide your arguments. (6pts) c. When the Two-Phase Locking protocol (2PL) is adopted for process synchronization, and there is only exclusive lock, can we have a deadlock? You must provide your arguments. (6pts) 3. Given the following snapshot of the system: Please determine whether there exists a safe sequence. (5pts) ┌─┬──────┬───────┬──────┐ │ │ Allocation │ Maximum Needs│ Available │ │ │ A B C │ A B C │ A B C │ ├─┼──────┼───────┼──────┤ │P0│ 0 1 2 │ 2 2 2 │ 0 1 1 │ ├─┼──────┼───────┼──────┤ │P1│ 2 1 0 │ 2 1 1 │ │ ├─┼──────┼───────┼──────┤ │P2│ 1 0 0 │ 1 1 2 │ │ ├─┼──────┼───────┼──────┤ │P3│ 0 1 0 │ 0 1 1 │ │ └─┴──────┴───────┴──────┘ 4. With binding at the compiling time, is it appropriate to have Paging? With binding at the loading time, is it appropriate to have Paging? You must provide explanation. (6pts) 5. Given a computer system with 64-bit virtual address and 8 bytes per page entry, let the physical address be of 48 bits, and the system is byte-addressable. Assume that every page is of 4KB. Please answer the following questions: (20pts). a. What is the maximum number of frames? (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. What the TLB hit ratio should be so that the effective memory access time would be no more than 120ns? (5pts) d. Continued with the previous question, What is the maximum number of entries for an inverted page table? (5pts) 6. Please answer the following questions for demand paging: (20pts) a. What is the maximum number of pages needed for the following instruction: Add (R1)+, -(R2), +(R3) (4pts) b. The effective access time is defined as (1 - p) * ma + p * pft, where p, ma, and pft are the probability of a page fault, the memory access time for paging, and the page fault time, respectively. Please give me two approaches to reduce the pft. Please give me two approaches to reduce p. (16pts) 7. Given the following reference string, which reference causes a page fault under the Second Chance (Clock) Algorithm. Please also show us which page is replaced when a page replacement occurs? Suppose that we have 3 available frames with 0, 1, and 3 as shown in the following graph, all reference bits are 0, and the selection pointer starts at Page 0. (10pts) 1 0 3 1 4 3 2 1 3 0 2 1 5 8. Modern operating system often only recognize few file types. Please give two advantages why file types are usually supported by applications, instead of the operating system. (8pts) 9. Give me one reason when we need scheduling in I/O subsystem, beside performance improvement. (4pts) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 61.230.115.230