課程名稱︰作業系統 課程性質︰大二必修 課程教師︰郭大維 開課學院：電機資訊學院 開課系所︰資訊工程學系 考試日期（年月日）︰2018/05/23 考試時限（分鐘）：180分鐘 試題 : Operating Systems Mid-Term Spring 2018s The exam is 180 minutes long. The total score is 112pts. Please read the questions carefully. 1. Terminologies (24pts). a. init (Hint: Booting; a UNIX process) A user process that initializes system processes, e.g., various daemons, login processes, after the kernel has been bootstrapped. b. Dual-Mode Operations (Hint: Mode Bit) Privileged and user-mode instructions, where privileged instructions are machine instructions that may cause harm. c. Memory Protection (Hint: Hardware Protection) Prevent a user program from modifying the code or data structures of either the OS or other users! d. A Modular Kernel A set of core components with characteristics: layer-like - modules; microkernel-like - the primary module. e. Asymmetric Addressing for Direct Communication In Direct Communication, sender must specify the receiver ID, but the receiver does not need to specify the sender ID. For example, Send(P, msg), Receive(id, msg). f. Remote Procedure Call (RPC) A way to abstract the procedure-call mechanism for use between systems with network connection. g. FIFOS of UNIX Named pipes of UNIX. It is a file in the file system and created by mkfifo(). It offers Half Dulex and Byte-Oriented Transmissions. h. Implicit Threading Transfer the creation and management of the threading from the application developers to compilers and run-time libraries. 2. For the implementation of the UNIX process control block PCB[], we have proc[] and .u, which contain different attributes for different purposes (e.g., those must be known regardless of whether the process is running). Which one is in the kernel or user address space? Are they both in the kernel or user address space? Which one of proc[] and .u signal disposition resides? Where thread-specific data/thread local storage will reside (in the kernel or user address space)? (8pts) (a) kernel address space: proc[]; user-address space: .u (b) .u: signal disposition (c) user address space 3. Please answer the following questions regarding operating systems: (21pts) a. When timing sharing appears as a feature for operating systems, please tell us two emerging features/subsystems, beside job synchronization. (6pts) b. Virtual machine software provides an interface that is identical to the underlying bare hardware. I/O over a virtual machine could be slow or fast, depenging on the implementations. Please give me a case in which I/O is fast, compared to I/O directly over physical devices. (5pts) c. There are operating sysrtem services, such as program executions, I/O operations, accounting, resource allocation, error detection. Which one is belonging to those for user convenience? Which one is belonging to those for system efficiency? (10pts) (a) one-line file systems, virtual memory, sophisticated CPU scheduling. (b) I/O can be fast over a hard disk when the correpsonding disk is implemented over DRAM by emulation. (c) user convenience: program executions, I/O operations, error detection; system efficiency: accounting, resource allocation 4. Multithreading is important for multi-core architectures. Please answer the following questions: (12pts) a. Task parallelism is one typical parallelism type. Please give one example for task parallelism. (5pts) b. Please provide two challenges in multicore programming. (4pts) c. Why the context switching costs of kernel-level threads is higher than that of user-level threads? (3pts) (a) Run merge sorting over cores by partitioning data. (b) Identifying Tasks - Dividing Activities, Balance, Data Splitting, Data Dependency, Testing and Debugging. (c) Context switching cost is little bit higher because the kernel must do the switching. 5. Compare preemptive scheduling and non-preemptive scheduling. Please answer the following questions: (21pts) a. In what circumstance, non-preemptive scheduling will be better than preemptive scheduling? (4pts) b. The selection of CPU scheduling algorithms should consider the scheduling criteria. If the high throughput is the criterion, which one is the best: Shortest job first, FIFO, and round-robin scheduling. You must provide answer to get credits. (6pts) c. Priority scheduling is a framework for scheduling. Please design a priority assignment formula that gives a lower priority to a job when it runs more time. (5pts) d. For Round-Robin Scheduling, if the lower average time turnaround time is the criterion, shall we prefer a lower time slice? Suppose that all jobs are ready at time 0. You must provide answer to get credits. (6pts) (a) Non-preemptive scheduling could be better than preemptive scheduling when all jobs are ready together at time 0. (b) Shortest job first. (c) priority = 1 / consumed-CPU-time (d) A lower time slice is bad to the low average turnaround time. 6. Processor Affinity is somehow against push migration. Please explain why. (6pts) It is because of the cost in cache repopulation. 7. Please explain the progress assumption concerns for virtualization. (6pts) It is assumed that a certain ammount of progress should be observed for a system in a given amount of time under virtualization. 8. Consider solutions to the Critical Section Problem. Please answer the following qusetions. (14pts) a. Consider a computing server to service jobs from three FIFO queues in a round robin way whenever there are jobs in any non-empty queues. Please use semaphores to implement your solution with some pseudo code. (6pts) b. What is the difference between a binary semaphore and a condition variable? (3pts) c. The Monitor-based implementation of the Dining Philosipher problem in the textbook implements the idea of two-chop-stick-per-time solution. Will it have the starvation problem? You must provide explanation to receive credits. (5pts) (a) We let, the dispatcher of each job queue to wait a shared semaphore whenever it has a pending job. Let the semaphore have a FIFO queue. (b) A condition variable has nothing happening to a signal request if no job is waiting for the variable. (c) Yes, the starvation problem happens to a philosipher whenever his two neighboring philosiphers take turn in eating while he is waiting. --

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