Computer Science Comprehensive Exam
Systems
May 29, 1996
This is a closed book exam. You have 1.5 hours to complete it.
Answer all of the questions. Be concise in your answers.
You will receive partial credit for partially correct answers, but
extraneous remarks may count against you.
- The physical page allocation for an application with the
reference string 012301401234, where 0, 1, 2, 3, and 4 are different virtual
memory pages, is increased from three to four, with
the idea of reducing the number of page faults.
If a first-in-first-out page replacement algorithm were used, will
this reduce the number of page faults? If not, what algorithm would you
use?
What is the characteristic of algorithms
that would result in a reduction (or at least a non-increase) in the number
of page faults regardless of the reference string, and are there any
drawbacks to their implementation.
- Design the process involved in an electronic funds transfer system.
Each process reads an input line specifying an amount of money, the
account to be credited, and the account to be debited. Once a lock
on an account has been acquired, it cannot be released without completing
the transaction. The process must lock both accounts, transfer the money,
and then release the locks when done, without resulting in deadlock.
- What are the hardware and software differences in the design of
a system for a Web server versus a supercomputer running applications
that have large computational requirements? For example, what
characteristics of the process subsystem, file system, and I/O
subsystems differ?
-
Checkpointing is the mechanism used to provide fault tolerance for
long running applications.
Checkpointing involves saving the complete program state on disk in
order to restore the application to the state at the time of the last
checkpoint, in the event of failure. Typically, checkpointing is done
periodically in order to reduce the amount of work lost. Describe
what needs to be saved during a checkpoint. What techniques would you
use in order to make the process efficient?