※ [本文转录自 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.