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.

  1. 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.

  2. 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.

  3. 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?

  4. 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?

[UP] [CSGSA]