Stanford Operating Systems Quals

2002 2001 2000 1999 1998 1997 1996 1995 1994 1993 1992

1994 Problem Set

The objective of the exam is to find out what you know about operating systems and to assess your ability to identify and develop solutions for problems that arise in operatings systems. Note that the questions have many "right" answers so be sure that you provide justifications. State any assumptions you make when answering the questions. Point form answers are acceptable. Problem 1 (18 Points) The MIPS R4000 microprocessor is a 64-bit RISC CPU with an unusual memory management unit (MMU). The MMU is implemented with a 64 entry fully-associative software reloaded TLB(*) that supports multiple page sizes. Each TLB entry contains a mask that defines the bits of the virtual page number used for comparison during a TLB lookup. By the appropriate setting of the mask bits when an entry is added to the TLB, a page size between 4 kilobytes and 16 megabytes can be selected. Having the mask in each TLB entry means that the hardware can support multiple different page sizes simultaneously. The only restriction on mappings is that no virtual address may map to mor than one TLB entry.

a) Describe the advantages of having multiple page sizes in a system.

b) Assuming that you want to exploit these advantages, describe the implementation challenges and potential disadvantages of using this feature.

c) If you were given the job of implementing a virtual memory system for a high-end compute server being designed with the R4000, describe how (if at all) you would use tihs variable-sized page support. Be sure to justify your answer.

(*) A software reloaded TLB is a virtual to physical mapping table in which misses in the table trap to the system software which is responsible for loading the needed translation into the table.
Problem 2 (?? Points) During the late 1970's and early 1980's, most computing in university computer science departments was done on an overloaded timeshared minicomputers such as the DEC VAX 11/780. During the late 1980's, many users abandoned these timeshared systems in favor of personal workstations that provided more CPU power than the VAX. Now, going into hte late 1990's, it appears that large multiprocessor compute servers can provide greater and more cost-efficient computing than the personal workstation.

Assume that you have been given the job of designing an operating system to run on these large time-shared multiprocessors of the late 1990's. One of the main challenges you face is to convince the old-timers that the return to time-sharing does not mean the return to overloaded timeshared systems. In particular, you determine that yuor system must be responsive enough to satisfy the expectations of users who have been using personal workstations for the last ten years.

Describe what resource allocation and scheduling mechanisms and policies you would employ in your system. Focus on the mechanisms and policies that differ from what was ued in the 1970's timesharing systems such as Unix. Be sure to indicate he problems that yuor new mechanism or policy is addressing.
Problem 3 (18 Points) Recently OS and database researchers have argued that users should be able to add code to their system to improve performance or functionality. For example, OS researchers have found that if a program were able to direct the virtual memory system to page in or out VM pages, the program can run in less memory. Similarly, database systems could allow user defined data types and access methods.

The addition of code to the operating system or database system exposes the system to errors or malicious behaviour in the added code. For example, a user could download code that corrupts or crashes the OS. Three potential solutions to this problem have been proposed:

1) Run all user added code in its own virtual memory address space. The operating system uses remote procedure call (RPC) to invoke the user's functions and the added code uses RPC to call the OS. Because it runs in its own address space, the added code can not read or modify any OS data or code.

2) Modify the user's object code so that every memory access instruction is proceeded by some code that checks the memory address to insure that the user is permitted to access it. This can be accomplished on a RISC processor by adding one or two instructions for ever load or store instruction in an object file.

3) The third option is to have the user write the extension code in a type-safe programming language. The type system of the language, enforced by the compiler, ensures that no unpermitted memory accesses can be performed.

Compare the advantages and disadvantages of these three approaches.
Problem 4 (?? Points) A file system's disk storage management component has the job of placing file descriptors and file data blocks on disk. File descriptors are the data structures that contain information about files such as size, modify date, data block locations, and protection information. There is a longstanding debate on how file descriptors and data blocks should be placed on disk. One side of the debate argues that all file descriptors should be placed in one separate portion of the disk while the other side argues that file descriptors should be placed with the data blocks of the file they describe. What are the advantages and disadvantages of these approaches.

Maintained by Gurmeet Singh Manku