Stanford Operating Systems Quals

2002 2001 2000 1999 1998 1997 1996 1995 1994 1993 1992

1992 Problem Set

The objective of the exam is to find out what you know about operating systems and to assess your ability to identify problems that arise in operatings systems and develop solutions to these problems. Note that several of these questions have many "right" answers so be sure that you provide justifications. State any assumptions you make when answering the questions. Problem 1 -- Virtual Memory and Compression (30 Points) You have been hired as an RA to investigate using compression in a virtual memory system to improve system performance. The motivation for the research is that a CPU can decompress a memory page significantly faster than it can read it from disk.

a) Describe what information or measurements you would need to make to do a quick (less than two weeks) feasibility study. Describe how you would use this information to decide whether to continue on with the research.

b) Assume that the idea still looks promising after the feasibility study. Sketch out a design for incorporating compression into a virtual memory system. Explain how the compression will interact with the existing data structures as freelist and page tables. Detail what additional data structures (if any) will be needed.

c) Identify the problem areas of your design. This should include the areas you are uncertain about and will need to study.

d) Describe what technique you will use to evaluate your design. Consider what information you would collect to convince others to incorporate your design into their systems.
Problem 2 -- Processes (10 Points) It has become popular lately to structure applications and operating systems using the client server model. Servers are often built with multiple threads of control (processes) in a single virtual address space. When a request arrives for a server, it is assigned to a thread to be processed. Mach and V are examples of systems that use this multi-threaded approach.

An alternative approach is to have a collection of single-threaded servers. Each server process has its own address space with a single thread of control. When a request arrives it is given to one of the servers to be processed. Some Unix-based servers use this approach.

a) List the advantages and disadvantages of each approach. Consider issues such as performance, scalability, reliability, and ease of programming.

b) Which of the approaches is better suited for the computer systems of the next five years? Justify your answer.
Problem 3 -- Kernel organization (10 Points) List the advantages and disadvantages of using a virtual machine operating system such as VM/370. Compare the virtual machine operating system technique with the micro-kernel technique used in operating systems such as Mach. Problem 4 -- Protection (10 Points) Operating systems that contain protection need some mechanism for amplifying the rights of a process under certain circumstances. A standard example of such a circumstance is the score file for a game program. When a user executes the game, the game code should be able to modify the score file. The user should not be able to modify the score file with an editor or any other program.

Describe and compare two (2) techniques used in operating systems to achieve this rights amplification.

Maintained by Gurmeet Singh Manku