※ [本文轉錄自 NTU-Exam 看板 #1LVuZjda ] 作者: rod24574575 (天然呆) 看板: NTU-Exam 標題: [試題] 103下 郭大維 作業系統 期中考+解答 時間: Tue Jun 16 10:24:42 2015 課程名稱︰作業系統 課程性質︰選修 課程教師：郭大維 開課學院：電資學院 開課系所︰資工系 考試日期（年月日）︰2015.05.13 考試時限（分鐘）：180分鐘 試題 : Operating Systems Mid-Term Spring 2015 The exam is 180 minutes long. The total score is 108pts. Please read the questions carefully. 1. Terminologies (24pts). a. Buffering (Hint: It is not caching.) Ans: It means to keep data in a faster medium temporarily before moving them to a slower layer. b. Virtual Machine Ans: It provides an interface that is identical to the underlying bare hardware. c. System Generation (SYSGEN) Ans: The process to configure or generate an operating system for a one specific computer. d. Context Switch Ans: Save the state of the old process and load the state of the newly scheduled process. e. Remote Procedure Call (Hint: Message Passing) Ans: Senders are blocked until the receivers have received msgs and replied by reply msgs. (A way to abstract the procedure-call mechanism for use between systems with network connection.) f. Implicit Threading Ans: Transfer the creation and management of the threading from the application developers to compilers and run-time libraries. g. Earliest Deadline First Scheduling Ans: A dynamic-priority real-time process scheduling algorithm in which the priorities of processes are higher if their deadlines are closer. h. Race Condition Ans: A situation where the outcome of the execution depends on the particular order of process scheduling. 2. Please answer the following questions regarding the designs of operating systems: (22pts) a. An operating system could be considered as a resource allocator. Please list 3 resources managed by an operating systems. (6pts) b. Please explain what happens to the operating system when an interrupt arrives (until the interrupt is serviced). (4pts) c. Which one of the following instructions is a privileged instruction: Reading of the Timer, setting of the base register of the memory space of a process, increment the value of a CPU register by one. No explanation is needed. (6pts) d. Please explain what happens when a command-line user interface of Unix executes a command. (6pts) Ans: (a) CPU, files, memory. (b) Saving of the address of the interrupted instruction, determine the interrupt type (by polling or interrupt vector), call the corresponding handlers. (c) Setting of the base register of the memory space of a process. (d) Search the exec file which corresponds to the command; fork a process to execute the file. 3. Consider parameter passing to a system call. Give me the major advantage in having a register pointing to a memory block that stores all parameters, compared to having all parameters stored in registers? (5pts) Ans: The space needed to store all parameters is virtually unlimited. 4. The memory image of a Unix process might consist of a code segment, a data segment, a heap area, a user stack, a kernel stack, an environment variable area, and .u. Which one of the above is used when malloc() is invoked? When the kernel stack is used? (8pts) Ans: (a) heap (b) procedure invocation in the system mode. 5. Please explain how fork() works when a parent process invoke fork(). Please use the answer to the fork() invocation to explain the difference between fork() and vfork(). (10pts) Ans: (1) When a parent process invoke fork(), a duplication of the parent process is created for the resulted child process, where the parent process returns from fork() with the process ID of the created child process. The child process returns 0. (2) When a parent process invoke vfork(), a child process is created by using the process image of the parent process, including its code and data segments. However, the parent process stop temporarily until the child process invokes an execve()-like system call to start a new program or terminates. The child process can modify any contents of the data segment of the parent process. 6. In the multi-core age, threading is encouraged. Please answer the following questions: (8pts) a. For multiple cores, do we prefer kernel-level threads or user-level threads? Why? (3pts) b. There are also challenges in programming. Consider merge sorting, in which an unsorted list is divided into N sublists, each containing 1 element, and then we repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list. Please use the concept of task parallelism to execute the merge sort over N cores. (5pts) Ans: (a) Kernel-level threads are preferred because more than one threads could be running at the same time. (b) Each core is given a sublist of one element. We then group 2 adjacent cores and let one of the cores merge the sublists of the two cores. …… 7. Please answer the following questions for process scheduling. Explanation is needed to receive any credit. (15pts) a. Given 5 processes P1, P2, P3, P4, and P5 with CPU burst time 6, 5, 2, 10, 5, respectively. Suppose that the P1, P2, P3, P4, and P5 arrive at time 0, 3, 4, 2, and 5, respectively. What is the average waiting time in running the 5 processes under the Preemptive Shortest-Job-First Scheduling. (5pts) b. Consider Shortest-Job-First Scheduling and Round-Robin Scheduling. Please prove that the total waiting time in running all processes under Shortest-Job-First Scheduling is always no larger than that of Round-Robin Scheduling with time slice equal to 1 when all processes are ready at time 0? (5pts) c. Suppose that the variance of the waiting time is the criterion in process scheduling. Shall we have a small time slice for a better variance for Round-Robin Scheduling when all processes of the same CPU burst arrive at time 0? (5pts) Ans: (a) 31/5 (b) Yes. Proof... (c) Yes. Proof... 8. Please answer the following questions for process synchronization: (l6pts) a. Please compare the difference between a binary semaphore and a condition variable. (3pts) b. Please use Monitor to implement Consumer and Producer with a bounded buffer. (10pts) c. Please prove that your above solution satisfy the Progress requirement of the Critical Section Problem. (3pts) Ans: (A) signal invotion to a condition variable that has no pending process has no effect. (b) monitor ProducerConsumer { int nfull = 0; cond has_empty, has_full; producer() { if(nfull == N) wait(has_empty); ... // fill a slot ++nfull; signal(has_full); } consumer() { if(nfull == 0) wait(has_full); ... // empty a slot --nfull; signal(has_empty); } }; Two condition variables: ‧ has_empty: buffer has at least one empty slot ‧ has_full: buffer has at least one full slot nfull: number of filled slots ‧ Need to do our own counting for condition variables. (c) Skipped. --

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

※ 發信站: 批踢踢實業坊(ptt.cc) ※ 轉錄者: w4a2y4 (140.112.16.131), 05/01/2017 16:20:28