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