Fall 1988 Operating Systems Page 1 of 3 _O_p_e_r_a_t_i_n_g _S_y_s_t_e_m_s _I_n_s_t_r_u_c_t_i_o_n_s: For the _B_R_E_A_D_T_H exam: Answer any 4 of questions 1-6. For the _D_E_P_T_H exam: Answer any 4 of questions 1-6 _a_n_d and 3 of questions 7-10. You are expected to spend about two hours on each half of the exam. _B_R_E_A_D_T_H _Q_U_E_S_T_I_O_N_S Breadth 1. Reentrant Code: Reentrant code is code that can be executed by more than one pro- cess at a time without interference. 1A. Name two things that might prevent code from being reentrant. 1B. A reentrant procedure could be shared by more than one pro- cess. Explain why it is easier to share a reentrant procedure using segmentation than paging. Breadth 2. Directory Structures: 2A. How could you simulate a multi-level directory structure with a single-level directory structure that allows arbitrarily long file names? To what extent would your simulation be imperfect? How would your answer change if file names are limited to 7 char- acters? 2A. Describe how this problem was handled in some existing sys- tem. Breadth 3. Polling vs. Signals: Control programs need to test conditions in the outside world that occur at arbitrary times, usually without waiting for one to occur. For example, a network server program must check for new connections while continuing to service existing clients, and a microprocessor-based motor control must check for control signals (e.g., stop!) while monitoring and adjusting the speed of a motor. 3A. Discuss the relative merits of polling for events vs. asyn- chronous notification that events have occurred. Consider perfor- mance issues and the impact on overall program structure. 3B. Discuss the impact of external events on process scheduling in an operating system. What happens when a program is waiting for more work to do? What if there are several different classes of events to wait for? 9 9 Fall 1988 Operating Systems Page 2 of 3 Breadth 4. Disk Layout: You are an engineer considering the rapid retrieval of digitized images from a disk sub-system. Images are 8 1/2 by 11 inches, with 300 dots (bits) per inch both vertically and horizontally. The proposed disk has sectors of 512 bytes, tracks of 20 sectors, _N surfaces of 250 tracks, average track-to-track seek times of 13 milliseconds, and the minimum seek time between adjacent tracks of 1 millisecond. The disk rotates 60 times a second. Your objec- tive is to retrieve a randomly selected image every two seconds. 4A. The physical layout on the disk of a digitized image must be carefully chosen to minimize access delays. Chose a layout and draw a sketch of (some of) the sectors, tracks, and surfaces of the disk, showing which block of the file each sector contains. What is the minimum value of _N needed for a single disk to achieve your objective? 4B. How long would it take to retrieve a digitized image if each block were stored on randomly chosen sectors? How long if succes- sive blocks were stored on the same track, but the tracks were chosen randomly? Breadth 5. Basic Protection Hardware: Architectural (hardware) features are needed to support an operat- ing system protected against buggy or malicious user programs (and protect programs against each other). 5A. List the types of physical resources to be protected, the architectural mechanisms used to protect them, and explain how each feature allows users efficient (unimpeded) access to their allotted resources while prohibiting access to unallocated resources. 5B. System calls allow users access to operating system code, for example, to perform operations on the file system. How do system calls limit the OS code that users can execute? While executing inside a system call, users have operating system powers. How must the OS code be written to prevent users from doing unauthor- ized things and avoid loopholes in the protection system? 5C. How do these protection mechanisms interact with the hardware interrupt system? What additional state must be saved or restored on an interrupt to ensure correctly protected operation? Breadth 6. Duality: 6A. How would you implement a service in a message-based, unipro- cessor operating system. Identify the components for: (1) clients, (2) servers, (3) requests, (4) server computation, (5) responses. Fall 1988 Operating Systems Page 3 of 3 6B. How would you implement a service in a monitor-based operat- ing system. Identify the components as in part A. 6C. How would each of these designs change for remote access to the service in a distributed system. 9 9 Fall 1988 Operating Systems Page 4 of 3 _D_E_P_T_H _Q_U_E_S_T_I_O_N_S Depth 7. Message Passing: Consider an OS with message passing, where the programmer cannot tell whether the sender/recipient is local or remote. After establishing a connection, the location of the recipient is tran- sparent to the program. In such a system, the OS kernel on each machine may or may not know how to send a message to a recipient on another machine. 7A. Outline the structure of the message passing mechanism for a system where the kernel DOES know about remote messages. Include the interface to a network providing reliable message transmis- sion. 7B. Repeat part A, for systems where the kernel NOT know about remote messages. If the kernel doesn't know about how to send remote messages, then who does know? (Hint: think about a com- munication server.) 7C. Describe the advantages and disadvantages of each of these approaches. Depth 8. Remote Procedure Call: Remote procedure call (RPC) is a form of interprocess communica- tion that is synchronous allows one client to contact one server. To build a reliable system, you might want to use replicated servers. In such a system, you would like to make a single RPC call and have the RPC mechanism automatically replicate the call to each server site. 8A. Outline the structure for a replicated RPC system and describe how it works. Include a description of locating server sites, dealing with responses from the multiple sites, failure detection, and ordering requests. 8B. Ethernet provides a broadcast facility. Does this help you in your design? Explain. Depth 9. Distributed virtual memory: In a shared-memory, multiprocessor system, several processes can simultaneously access the same page of memory. This is usually done by mapping the page into each processes address space. _D_i_s_- _t_r_i_b_u_t_e_d _v_i_r_t_u_a_l _m_e_m_o_r_y accomplishes the same function for proces- sors that are loosely-coupled (connected by a network, like Ether- net). 9A. Outline the structure of system that implements distributed virtual memory. How would integrate this into an existing paged Fall 1988 Operating Systems Page 5 of 3 virtual memory system, using conventional memory-management hardware? How are page faults handled? 9B. What is the problem with data consistency in such a system? How would you handle this problem? How are your consistency poli- cies affected by usage patterns? Depth 10. Inverted Page Table: An _i_n_v_e_r_t_e_d _p_a_g_e _t_a_b_l_e, which has one entry per page frame of phy- sical memory is an alternative to the standard page table organi- zation (with one entry per page of virtual space). Although the very first paging computer system (the Atlas) used inverted page tables they have not been used much since then. Recently however, there they have received more attention. For example, the IBM RT/PC uses inverted tables. 10A. What are the advantages and disadvantages of inverted page tables over ordinary tables? Be sure to consider such issues as space and time efficiency, and the impact of virtual and physical memory sizes. 10B. What trends in hardware technology are likely to make inverted page tables more or less attractive in the future? 9 9