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.
- Synchronization:
The following algorithm, developed by Dekker, is the first known correct
software solution to the critical section problem for two processes. The
two processes, P0 and P1, share the following variables:
bool flag[2]; /* initially both flags are false */
int turn = 0 or 1;
The following program is for process Pi (i=0 or 1), with Pj (j=1 or 0)
being the other process:
for (;;) {
flag[i] = true;
while (flag[j])
if (turn==j) {
flag[i] = false;
while (turn==j); /* spin wait */
flag[i] = true;
}
...
critical section
...
turn = j;
flag[i] = false;
...
remainder section
...
}
Explain that the algorithm satisfies all three requirements (mutual
exclusion, progress, bounded waiting) for the critical section problem.
- 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?
- 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.
- Caching and prefetching:
Caching and prefetching are employed to improve file system performance.
Caching file content in memory can reduce disk I/O if the same content
is accessed again in the future. Prefetching allows large chunks of
disk I/O to be performed sequentially, which improves the disk I/O
throughput if prefetched content is eventually used.
- 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?
- The disk controller contains a fast-access buffer
that is independent of the host memory. The buffer can be
accessed at a much faster speed than the disk drive. The size of
the controller buffer is typically between 2MB and 8MB, which is
much smaller than the host memory size. In order to further
improve I/O efficiency, should this buffer be used for caching,
prefetching, or both? Explain your answer.
- 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.
- Reliability: Device drivers are probably the buggiest part of an
OS kernel since their developers (hired by device manufacturers) may not
be as nerdy as the core kernel developers.
- In order to prevent buggy drivers from overwriting other
parts of the kernel, we let each device driver have its own
kernel-level page table. A driver's page table makes
clear that it can only write to a designated set of pages. When the
CPU control transfers in and out of a driver, the kernel switches
page tables appropriately. Although this scheme can only protect
against buggy drivers, it is insufficient in dealing with malicious
drivers. Explain why.
- Other than overwriting other parts of the kernel, describe
another potential hazard that buggy (not malicious) drivers pose on the
rest of the operating system.
- The part of device drivers that uses privileged I/O
instructions or accesses privileged device registers must run in
kernel mode, but other parts may run in user mode. Running
parts of device drivers in user mode may improve the OS reliability.
Describe any performance problem with this scheme.
- 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.