Stanford Operating Systems Quals

2002 2001 2000 1999 1998 1997 1996 1995 1994 1993 1992

1993 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. Problem 1 (15 Points) You have been made chief software architect of a large software project. To encourage the development of reusable code, your design has application structured as a collection of libraries joined together by a small driver program. You have partitioned the application so that each library can and will be developed by a separate group. You give each group a detailed specification of the interface to their library and the interface to other libraries that they can use. The rsulting system will contain between 10 and 20 libraries.

Part way into the coding of the system, you hear a rumor that some of the groups are adding code to their library that will cause failures in the libraries of other groups. One technique you hear about is code that changes private data associated with another library causing the second library to de-reference a zeroed pointer when it is invoked. The goal of this mischief is to discredit other groups so their part of the implementation would be transferred to the mischievous group.

a) Describe a protection mechanism you could add to the system software to prevent the groups from sabotaging each other during the application's execution. The hardware available to you supports a ring protection scheme with a small (less than 5) number of rings. Be sure to include an estimate of the cost of adding this protection mechanism.

b) Will the protection mechanism you describe require changes to the inteerface you initially designed for the libraries? Would it be necessary to inform the library implementation groups about this new protection mechanism?
Problem 2 (15 Points) You have been put in charge of a group building a new operating system for a large-scale shared address space multiprocessor. The hardware is a NUMA machine with between two and 4096 processors each with 64 megabytes of memory. Access to non-local memory is a factor of ten slower than to local memory.

There is a dispute between the members of your team that ar working on the virtual memory system and the scheduler. The virtual memory designer claims that the virtual memory module should determine the placement of application pages in the distributed physical memories. The claim is that the scheduler should provide an interface by which the virtual memory module can provide hints on which processor processes should be executed. Ths hints would be based on where the virtual memory system has allocated the pages of a process.

The scheduler designer claims that the VM designer has it backwards; the scheduler should decide where processes should run. An interface to the virtual memory module should be provided so the scheduler can inform the virtual memory of where a process is to be run. The virtual memory system should then place applications in memory accordingly.

a) Describe the strengths and the weaknesses of each side of the argument.

b) As the group leader, what do you think would be the best solution to the dispute? Justify your answer.
Problem 3 (10 Points) Pushing the three keys CTRL, ALT, and DEL simultaneously on the console the machine running the operating system, Windows NT suspends any user processes reading from the console. The system then queries the user to see if the processes should be terminated or continued. When no user is logged into the console of a Windows NT machine, a login prompt can be activated by typing the CTRL, ALT, and DEL keys.

a) What do you think was the motivation behind having the login sequence activated by these keys?

b) Does the technique fully accomplish the motivation in part a) wants it to do? If so, how? If not, what would it take to make it work?
Problem 4 (10 Points) You are at a workshop on multimedia operating systems and the researchers there are divided into two camps. The first camp contains researchers who believe that multimedia such as audio and video will require special mechanisms and techniques be added to existing systems. They argue that existing mechanims and techniques are not sufficient to support multimedia. The second camp believes that the increasing power of computers means that existing operating system implementations and abstractions will support multimedia workloads with no problem. They believe that multimedia is not a problem if you have surplus compute power.

Which camp do you most agree with? Be sure to justify your answer.
Problem 5 (10 Points) Another dispute has arisen between two researchers on your operating system project. They both read a paper that says that the encryption key used by a pair of communicating processes should be changed frequently. Unfortunately, they can't seem to agree on what is meant by frequently. One researcher says that a timer should be associated with each key and when the timer expires a new key should be generated for the connection. The other researcher suggests that a byte counter be associated with each key and after a certain number of bytes have been encrypted with a key, it should be changed.

a) Which researcher (if any) do you think is right?

b) Both the researchers agreed they can do the exchange of a new key much faster if they use the existing key to encrypt the key exchange message. The alternative approach would require communication with an authenticated server using the same mechanism present to establish the initial key for the channel. What do you think of this idea for speeding the exchange of keys on an existing communication channel?

Maintained by Gurmeet Singh Manku