※ [本文转录自 NTU-Exam 看板 #1NQf-lUj ] 作者: jim841019g (逆转魂) 看板: NTU-Exam 标题: [试题] 104下 郭大维 作业系统 期中考+解答 时间: Wed Jun 22 22:24:44 2016 课程名称︰作业系统 课程性质︰必修 课程教师︰郭大维 开课学院：电资学院 开课系所︰资工系 考试日期（年月日）︰2016.05.11 考试时限（分钟）： 试题 : Operating Systems Midterm Spring 2016s The Exam is 180 minutes long. The total score is 105pts. Please read the questions carefully. 1.Terminologies(24pts) a. Software Interrupts It is, in general, caused by software execution, e.g. signals,invalid memory access, division by zero, system calls. b. Performance Tuning A procedure that seeks to improve performance by removing bottlenecks. c. Mid-Term Scheduler Swap processes in and out to control the degree of multiprogramming. d. FIFOS of UNIX Named pipes. e. Asynchronous Signal An asynchronous signal usually reports some asynchronous event outside the program, e.g., ^C or time expiration. f. Push Migration (Hint:Load Balancing) A specific task periodically checks for imbalance and migrates tasks. g. Coarse-Grained Multithreading of Hardware Threads Coarse-grained multithreading only switches to issue instructions from another thread when the current executing thread cause some long latency events. h. Analytic Evaluation Take a particular predetermined workload and defines the performance of each algorithm for that workload 2. Please answer the following questions regarding operating systems:(20pts) a. Please compare the difference between interrupt handling by a generic handler and interrupt vector in terms of the mechanism and the response performance. (6pts) b. Please compare the difference between the terms "time sharing" and "multiprogramming". (4pts) c. One of the most challenging parts in the implementations of a virtual machine is to satisfy the assumption of a certain amount of progress in a given amount of time. Please explain the challenge.(6pts) d. Parameter passing is an important issue in the implementation of command interpreters. Please explain how a command interpreter of Unix passes parameters to the running process of a command issued on the command interpreter. (4pts) Ans: (a) mechanism: a generic handler finds out the interupt type and invokes the corresponding procedure but the interrupt vector lets the corresponding procedure directly invoked though checking up of the interrupt vector; performance: interrupt vector is faster. (b) Time sharing is a logical extension of multiprogramming in which CPU time is quickly switching among tasks to share time. (c) You can use the example in the class when two virtual cores share a physical core, in which a task must run for 2ms for every 5ms, but its virtual machine might not receive any service within a 5ms time window (d) It can be done by using one of the exec() system calls. 3. Consider process states: New, Ready, Running, Waiting, and Terminated. Please explain how a state makes a transition to another state, where there is only one processor.12(pts) Ans:same in the CH3 p.6 4. Message passing is one major way for interprocess communication. What is the main difficulty in using symmetric addressing for direct communication? For indirect communication, small messages are sent from a sender to a receiver usually by message copying. How to reduce system overheads in-sending large messages to a receiver?(8pts) Ans: (a) process naming (or modularity) (b) remapping of addressing space. 5. For multicore programming, there could be data parallelism or task parallelism. Please explain how to use data parallelism to find the largest integer of a given set of integers.(5pts) Ans: First split data over N cores, and let each core find the largest integer of its given integers. Then let one core find the largest integers among the latgest integers found on each core. 6. Please answer the following questions for process scheduling. Explanation is needed to receive any credit. (15pts) a. Is the First-Come, First-Served Scheduling (FIFO) a non-preemptive or preemptive scheduling algorithm? Why? (4pts) b. Given 4 processes P1,P2,P3, and P4 with CPU burst time 5,2,4, and6, respectively. Suppose that the P1,P2,P3,and P4 all arrive at time 0. What is the average waiting time in running the 4 processes under the Round-Robin Scheduling with the time slice equal to 3? (5pts) c. Longest-Job-First Scheduling always schedules the process of the longest CPU burst first. When all processes arrive at time 0, does Longest-Job-First Scheduling have the largest average turnaround time? (6pts) Ans: (a) It is non-preemptive because the running process will not volunteer to give up its CPU until it stops. (b) (No answer) (C) Yes.... Proof by swapping of process with larger and smaller CPU bursts... 7. Consider the intersection of the following two roads, where cars can go from each of the four directions. There is a stop sign for each direction so that every car must stop at the intersection and wait for any car that arrives earlier at the intersection to leave first. a. Please use semaphores to implement your solution with some pseudo code. (10pts) b. Please prove that your above solution satisfy the three requirements of the Critical Section Problem. (6pts) c. Could you revise your solution so that an ambulance can always go first? (5pts) ┌───┐ ┌───┐ │ │↓ │ │ └───┘ └───┘ ← → ┌───┐ ┌───┐ │ │ ↑│ │ └───┘ └───┘ Ans: (a) and (b) Assumtion: Semaphores with a FIFO queue (c) Let the ambulance has the priority in the waiting queue. --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.112.16.147 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/NTU-Exam/M.1466605487.A.7AD.html ※ 编辑: jim841019g (140.112.16.147), 06/22/2016 22:26:31 ※ 编辑: jim841019g (140.112.16.147), 06/22/2016 22:27:11

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