Systems Qualifier - Spring 2001

Systems Area Questions for Qualifier

Spring 2001
Answer 6 of 9 questions:

Real-time Systems: An issue arising for real-time programs scheduled to meet deadlines is synchronization. First, describe the problem, assuming that multiple real-time programs, all subject to meeting deadlines, run on the same machine and share resources. Second, indicate at least one solution for this problem, assuming either rate-monotonic or deadline-based scheduling. Third, comment on the following assertion: 'There is no problem with synchronization when we use CPU Capacity Reserves'.

Object-based Operating Systems: First, for the technical part of this question, please address the following issue: 'Quality of Service' is an important issue that must be addressed for object-based operating systems (as well as non-object-based ones, of course). Explain how to separate the specification and then the implementation of the quality of service offered by a certain object from the object's class/type description and implementation. Then explain how that same separation may be done at runtime, such that the quality of service offered by an object may be adapted at runtime. Finally, comment on the following statement: 'Object-based operating systems are not important anymore, since everyone will use Windows and Unix anyway.'

(Read the entire question before starting to answer.) Program specialization is similar to partial evaluation. A generic program can be specialized when there are _invariants_ that make some sequence of instructions superfluous, since they always produce the same results at the end. The idea of program specialization is to replace the sequence of instructions with the result, thus improving program performance. The main difficulty in OS specialization is that there are _quasi-invariants_ that remain true almost all of the time, but that could be invalidated in rare situations.

In their SOSP'95 paper, Pu et al describe the specialization of the HP-UX file system. They specialize the read system call using the exclusive sequential access quasi-invariant, which is considered the most common case in Unix file systems. Give an example of quasi-invariant in another OS module that may improve system performance through specialization. Hint: I/O subsystems are easier candidates.

To guard against the rare cases when quasi-invariants may be invalidated, we need to insert _guards_ into the system when applying program specialization. For example, in the specialization of HP-UX read system call, they inserted guards into the open system call, which may invalidate the exclusive access quasi-invariant when a second process opens the same file. A less obvious guard is inserted into the dup system call, which may produce the same result. For the example of quasi-invariant you gave in sub-question (1.a), give two examples of places you need to guard against quasi-invariant invalidation. If you believe there is only one guard necessary, present an argument that you don't need any other guards.

Define informally what a recoverable schedule is. What is the main property that must hold?
If two-phase locking is used, when can write locks be released in a recoverable schedule? When is the earliest time that a read lock can be released? Please explain.
Let the memory-commit of a transaction T be the point when T's commit record is written to the in-memory log buffer. Let the disk-commit of T be the point when T's log record is flushed to disk. With so-called group commit, T's write locks are released after the in-memory commit. The client that submitted T is not notified of its commit until after the disk commits. Explain why a group commit system does not generate recoverable schedules. Explain why this is not a problem.
Advanced Part:
A transaction T modifies two files, X and Y, atomically. As it runs, T will generate three log records: LX: the log record for the X action, LY: the log record for the Y action, and LC: the log record for the commit record.
Below are four scenarios describing what is flushed out to disk and what is not.
1. Log records LX, LY, LC are flushed to disk; the new X page is flushed, but the Y page is not.
2. Only log record LX is flushed to disk; the new X and Y pages are flushed.
3. Only log records LX and LY are flushed to disk; the new X page is flushed, but the Y page is not.
4. Log records LX, LY, LC are flushed to disk; the new X and Y pages are flushed.
For each scenario, state if it could happen under a pure undo value logging scheme, a pure redo value logging scenario, an undo/redo value logging scheme, or if the scenario could never arise.

Optimizing for locality of reference is a big issue and both the compiler and the OS try to undertake locality optimizations. Consider the problem of paging and OS algorithm such as LRU for page replacement policy in the main memory. Show through an example why pure OS policy of LRU might not achieve desired locality of reference without compiler hints regarding the program behaviour. Why is it so? Show how you might be able to add compiler generated hints to improve LRU. Outline what kind of analysis you might have to undertake and what modifications in LRU/page tables/run time system might be needed. Reason regarding your answer through an example showing all the details.

The communication cost of implementing a certain abstraction or service in a distributed system depends on the assumptions that are made about the underlying system. For example, if message delivery times are bounded then more efficient solutions are possible for certain problems. Another parameter captures the assumption about the rates at which different processors run.
List the important system parameters that influence the cost of distributed implementations of services. Choose an example service (e.g., synchronization, distributed shared memory or caching file system) and illustrate how the protocols that implement it are influenced by the system parameters. If we want to build a fault-tolerant implementation, what assumptions are necessary about the system. For example, what assumptions should be made to build distributed transactions. Are these assumptions reasonable in practical systems? Discuss your answer.

Two well known approaches to performing state saving in Time Warp programs are called copy state saving and incremental state saving. Explain how each technique works, and compare these techniques in terms of efficiency. In particular, describe situations where one would yield better performance than the other, taking into consideration all aspects of the execution of a Time Warp program. Finally, compare these techniques in terms of ease of use from the perspective of the person developing simulation programs that are to execute on the Time Warp system.

In Birrel's paper that discusses secure communications using RPCs, a symmetric key algorithm is used for all encryption and decryption. The en/decryption of data provides authentication of the parties and confidentiality of data. A public key cryptographic algorithm is an algorithm that uses one key for encryption and a different key for the decryption. One of those keys, called a public key, is not considered sensitive and can be openly distributed. The other key, called a private key, is considered a secret. The private key cannot be computed from the public key.
Discuss the pros and cons of using public versus symmetric key cryptography.
How you would change the protocol described in Birrel's paper to use public key cryptography (perhaps combined with symmetric key cryptography)? What would be the pros and cons of this new protocol?

Any decent operating system ought to let you "freeze-dry" a running process to save it to disk for later, to migrate it to another platform or to e-mail it to your friends. DEC's TOPS-20 included such functionality to let you save your work when logging out. The Condor system includes a limited version of such functionality to permit processes to migrate among a network of workstations. Enumerate all the problems you'd need to solve to implement this functionality in general in a current operating system such as Linux or NT. Propose detailed solutions to each problem.