※ [本文轉錄自 NTU-Exam 看板 #1KZIjikr ]
作者: rod24574575 (天然呆) 看板: NTU-Exam
標題: [試題] 101下 郭大維 作業系統 期中考+解答
時間: Sun Dec 14 14:17:14 2014
課程名稱︰作業系統
課程性質︰必修
課程教師︰郭大維
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰
考試時限（分鐘）：180
試題 :
Operating Systems
Mid-Term
Spring 2013
The exam is 180 minutes long. The total score is 110pts. Please read the
questions carefully.
1. Terminologies (24pts).
a. Hardware Interrupt
Ans: Services requests of I/O devices.
b. Virtual Machine
Ans: Virtual machine software provides an interface that is identical to
the underlying bare hardware.
c. Context Switch
Ans: It saves the state of the currently running process and loads the
state of the newly scheduled process.
d. A Full Duplex Pipe
Ans: A pipe that suppors two ways of message passing simultaneously.
e. Multilevel Queue Scheduling
Ans: Processes can be classified into different groups and permanently
assigned to one queue, where there are Inter-queue and intra-queue
scheduling policies.
f. Memory Stall
Ans: A phenomenon in which a processor waits for a significant amount of
time waiting for the data to become available.
g. Bounded Waiting (A Requirement of a Critical Section Solution)
Ans: A waiting process only waits for a bounded number of processes to
enter their critical sections.
h. Adaptive Mutex
Ans: A binary semaphore in which it is a spinlock if the lock-holding
thread is running; otherwise, blocking is used.
2. Please answer the following questions regarding the designs of operating
systems: (20pts)
a. What is the difference between multiprogramming and time sharing? (6pts)
b. Which one of the following memory unit is managed by the operating
systems: Registers, Cache, Main Memory, Disks (8pts)
c. Operating systems services include user interfaces. UNIX shells,
including the Boume shell and C shell, provide command interpreters.
Consider UNIX shells, please give me one command that is implemented as
some code inside the command interpreter and two commands that are
implemented by system programs? (6pts)
Ans: (a) Time sharing (or multitasking) is a logical extension of
multiprogramming, where CPU services each of ready tasks in a way
that every task receives CPU time in an interactive fashion.
(b) Main Memory and Disks.
(c) Inside an interpreter: umask, chdir, limit (C shall), ulimit -H
and -S (Bourne shell and KornShell)
System programs: rm, ls.
3. Message passing is a way for interprocess communication. Consider the
capacity of a link between two processes has zero capacity. Is the message
passing (between the two processes) synchronous or asynchronous? You must
provide explanation to receive any credits. (5pts)
Ans: It is synchronous because we can only have blocking sends and blocking
receives.
4. Please give me one occasion when a mid-term scheduler should run.
Can a short-term scheduler schedule the executions of user-level threads?
Can a short-term scheduler schedule the executions of a Java thread? (9pts)
Ans: (a) The remaining main memory is low or the CPU utilization is too
high.
(b) No.
(c) It depends on the thread library on the host system.
5. Consider signal handling for threads. Is a Division-By-Zero signal
synchronous or asynchronous? Should a Division-By-Zero signal be delivered
to every thread of its belonging process? (6pts)
Ans: (a) synchronous.
(b) No. It should be only sent to the thread that causes the signal.
6. Please answer the following questions for process scheduling. Explanation
is needed to receive any credit. (24pts)
a. For the Round-Robin Scheduling, what would be the preferred time slice
in general? (4pts)
b. For the Round-Robin Scheduling, shall we have a small time slice for a
better average turn around time? (4pts)
c. For the Priority Scheduling, how to avoid the starvation problem
(in which a low priority process can never be scheduled)? (4pts)
d. Please explain how a guest operating-system scheduling algorithm that
assumes a certain amount of progress in a given amount of time might be
negatively impacted by virtualization. (6pts)
e. For the evaluation of a scheduling algorithm, please give me two
difficulties in using the implementation method. (6pts)
Ans: (a) The time slice ≧ 80% CPU burst.
(b) No, a small time slice will increase the average turnaround time.
(c) An aging solution by increasing the priority of a process that
waits for a long time.
(d) It is because the virtualization software needs to schedule the
use of the physical CPUs among the virtual CPUs. A given amount of
the time slice might take much more than the time of the virtual
CPU time;
(e) cost in modifying the OS, user reaction to OS changes, and the
changing of the environment in which the algorithm is used.
7. Please explain the difference between the signal operation of a binary
semaphore and that of a condition variable (of a monitor). (5pts)
Ans: The signal operation of a condition variable resumes one suspended
process. If there is none, no effect is imposed.
8. Consider a barber shop in which there are two barbers. Each barber can
service exactly one customer at a time. Please use binary semaphores to
implement the request for the hair-cut service. (l2pts)
Ans: Use an integer C with initial value = 2 to indicate the number of
available barbers. Modify the wait() and signal() algorithms for the
implementations of counting semaphores for the solutions.
9. Consider the time-stamp protocol of Chapter 6, in which each process T_i is
given a time stamp TS(T_i), and each read/write operation must check it up
with the read and write timestamp of the accessed data object Q. Is it
possible to have any deadlock? You must provide your explanation. (5pts)
Ans: No deadlock because there is no hold-and-wait among processes.