Written assignment #2
This assignment is meant to help you in the final review of the course.
You don't have to turn in this assignment (and we will not grade it even
if you do). We will not post the solution either. You are encouraged to
meet the instructor and the TAs for solutions to the problems or any
other questions you might have. Note that this set of questions are
not meant to be complete for your final exam preparation. In particular,
it does NOT replace the need of reviewing lecture notes and the textbook.
Also note that the final exam may contain materials covered before
the midterm exam.
- CPU scheduling:
Imagine two users: one launches short processes one by one while
the other launches long processes one by one. In a fair
scheduling environment, each user should acquire equal amount of
resource. Explain the differences in the degree to which the following
scheduling algorithms discriminate in favor of or against the
short-process user.
- Shortest-Job-First.
- First-Come-First-Serve.
- Round-Robin.
- Synchronization:
- Suppose a program has three threads and a shared counter as shown below:
int count = 10;
Semaphore sem = 1;
Thread1(...) Thread2(...) Thread3(...)
{ { {
// do something // do something // do something
sem.wait(); sem.wait(); sem.wait();
count ++; count --; printf(``%d'', count);
sem.signal(); sem.signal(); sem.signal();
} } }
Does this process suffer from a race condition? Justify your answer.
- Assume you have a hardware instruction, called
fetch_and_inc
,
that can read and increment a memory location in one atomic operation.
unsigned int fetch_and_inc(int *counter) {
atomically {
t = *counter; *counter = t+1; return t;
}
}
Assuming that each ordinary load or store instruction is also
atomic, does the availability of fetch_and_inc
make it
easier to solve the critical section problem? Show a solution or
explain why you can't do better than with load and store alone.
- Deadlock:
Consider a system consisting of m resources of the same type, being
shared by n processes. Resources can be requested and released by
processes only one at a time. Can a deadlock occur in this system if the
following two conditions hold?
- The maximum need of each process is between 1 and m resources;
- The sum of all maximum needs is less than m+n.
If so, show how. If not, explain why not.
- Paging:
Consider a reference string 1,2,3,4,2,5,6,2,3,2,1,6,7;
and a system with only 4 frames (all frames initially empty).
- How many page faults would occur with a FIFO replacement
scheme? What are the identities of pages in the frames when the
reference string has completed?
- How many page faults would occur with a perfect LRU
replacement scheme? What are the identities of pages in the frames
when the reference string has completed?
- Describe one possible implementation scheme for LRU.
- Would increasing the number of frames always decrease
the number of page faults for a particular reference string for FIFO?
for LRU?
- Caching and prefetching:
Caching and prefetching are employed to improve file system performance.
Prefetching is particularly effective for data accesses that follow
sequential access patterns. When the OS detects a sequential access
pattern, should it use an LRU replacement policy for prefetched pages in
I/O buffers? Explain why. Assume that the access time for a prefetched
page is initialized to its prefetch time. If LRU is a bad choice, what
replacement policy should the OS employ for those pages?
- Disk scheduling: Consider disk scheduling algorithms such as
FCFS (First-Come-First-Serve), SSTF (Shortest-Seek-Time-First), SCAN,
and C-SCAN (Circular Scan).
- Explain why SSTF scheduling favors middle cylinders over
the innermost and outermost cylinders.
- Explain why SCAN scheduling favors middle cylinders over
the innermost and outermost cylinders.
- Disk I/O requests are not usually uniformly distributed.
If about half of all requests are for a small contiguous subset of
cylinders, please discuss the efficiency (regardless of fairness) of
the above four disk scheduling algorithms (FCFS, SSTF, SCAN, and C-SCAN)
for this case.
- Under what circumstance would anticipatory scheduling
be helpful for improving disk I/O efficiency?
In anticipatory scheduling, the scheduler may choose to keep the disk
idle for a short period of time even if there is work to do. The
scheduler does so in anticipation of a new I/O request that would
require little seek overhead.
- Security:
In some secure systems, processes are only allowed to communicate
through well-monitored channels (e.g., sockets and pipes) and certain
information is prohibited from being passed to specific processes.
However, two collaborating processes may pass banned information through
covert channels. In one case, process A modulates its CPU usage in
well synchronized time slots. To pass a binary message ``010'', it will
stay idle for one time slot, spin like crazy for the next, and stay idle
for the third slot. Process B can learn the binary message by
checking CPU idleness at each time slot. Suggest a way to prevent such
CPU-modulating covert channel communications.
- Reliability:
In a multi-threaded server, an invalid memory access (an attempt to
access an invalid memory location) causes the whole server to crash.
Dr. Foobar proposes a scheme to improve server reliability in the
presence of invalid memory accesses. In his scheme, an invalid read
access returns some randomly generated data while an invalid write access
is simply discarded. In both cases, the server keeps running without
crashing. The goal is that although the thread that makes the invalid
memory access may not complete properly, other threads in the server will
not be affected. Describe at least two scenarios under which Dr.
Foobar's scheme will fail.
- Virtual machines: A virtual machine monitor (VM monitor) is a
piece of software that provides execution environments with an interface
identical to the bare hardware. These execution environments are called
virtual machines (VMs). An operating system and its user programs run
in each VM. A VM monitor may support multiple VMs. When it does so,
the VM monitor must allocate physical memory pages among those VMs. It
is possible that multiple VMs contain memory pages with exactly the same
content. One particular cause is that several VMs may run the same OS
and the read-only OS kernel code segment would be identical across those
VMs. It would save some memory space if we can let those VMs share a
single physical copy of identical memory pages.
- In order to support inter-VM page sharing, the VM monitor
needs to detect identical pages across VM boundaries. Please
describe how this may be detected when loading a new page into
memory. Efficiency must be considered.
- It is possible for a shared page to be modified by one
of the VMs, which would make the sharing invalid. Please describe
a mechanism to deal with such a problem.