課程名稱︰作業系統
課程性質︰選修
課程教師：郭大維
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰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