SSSSpppprrrriiiinnnngggg 1111999999992222 OOOOppppeeeerrrraaaattttiiiinnnngggg SSSSyyyysssstttteeeemmmmssss PPPPaaaaggggeeee 1111 ooooffff 2222 _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 3 of ques- tions 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 _B_r_e_a_d_t_h _1. _D_i_s_k _A_l_l_o_c_a_t_i_o_n: Two common strategies for free space management on disks are _f_r_e_e _l_i_s_t_s and _b_i_t _m_a_p_s. (1a) One naive algorithm uses a simple linked list of free blocks. Each free block contains the disk address of the next block on the list. What's wrong with this strategy? How could you improve on it? (1b) Why might you prefer to use a bit-map strategy rather than a free list? What are the tradeoffs between the two stra- tegies? _B_r_e_a_d_t_h _2. _S_y_n_c_h_r_o_n_i_z_a_t_i_o_n: When Dijkstra introduced semaphores, there was already a closely related synchronization primitive in use called an _e_v_e_n_t variable. There are two operations on event variables: aaaawwwwaaaaiiiitttt(_e) always blocks the caller, while ccccaaaauuuusssseeee(_e) awakens the process that has been waiting the longest on event variable _e. If no process is blocked on _e, ccccaaaauuuusssseeee(_e) has no effect. (2a) Why are semaphores more convenient to use than event vari- ables? (2b) Event variables are very similar to _c_o_n_d_i_t_i_o_n variables in monitors. What is it about monitors that mitigates the prob- lems discussed in part (a)? (2c) Show how to implement semaphores using event variables, ordi- nary shared integer variables, and a test-and-set instruc- tion. _B_r_e_a_d_t_h _3. _M_e_d_i_u_m-_T_e_r_m _S_c_h_e_d_u_l_i_n_g (3a) Medium-term scheduling is primarily concerned with the management of which physical resource? (3b) A scheduler needs a _p_o_l_i_c_y to decide what to do, and a _m_e_c_h_a_n_i_s_m to do it with. What is the basic mechanism used by medium-term scheduling? SSSSpppprrrriiiinnnngggg 1111999999992222 OOOOppppeeeerrrraaaattttiiiinnnngggg SSSSyyyysssstttteeeemmmmssss PPPPaaaaggggeeee 2222 ooooffff 2222 (c) Describe a reasonable policy for medium-term scheduling of very large jobs when lots of small jobs also exist. _B_r_e_a_d_t_h _4. _S_e_c_u_r_i_t_y: Securely accessing a service across the network involves (1) authenticating the parties involved, and (2) having a private com- munication between the parties. (4a) Which of these two problems is addressed by the Needham and Schroeder protocol? Describe the protocol and how it solves the problem. (4b) How can you solve the remaining problem? _B_r_e_a_d_t_h _5. _M_e_s_s_a_g_e _P_a_s_s_i_n_g: Copying of buffers can be a major cost in sending messages, espe- cially when sending remote messages (i.e., messages sent from a process on one host to a process on another host. (5a) Where, in the course of sending a remote message, are mes- sages copied? (5b) How can you use the memory organization and memory mapping hardware to eliminate some of this copying? _B_r_e_a_d_t_h _6. _M_e_m_o_r_y _M_a_n_a_g_e_m_e_n_t: The WSclock algorithm (in part) is an approximation to Working Set. (6a) In what ways is the approximation more efficient to implement than pure Working Set? (6b) Under what conditions will WSclock provide a good approxima- tion of Working Set and what conditions will it provide a poor one? SSSSpppprrrriiiinnnngggg 1111999999992222 OOOOppppeeeerrrraaaattttiiiinnnngggg SSSSyyyysssstttteeeemmmmssss PPPPaaaaggggeeee 3333 ooooffff 2222 _D_E_P_T_H _Q_U_E_S_T_I_O_N_S _D_e_p_t_h _7. _N_e_t_w_o_r_k_i_n_g: Tanenbaum discusses two versions of sliding window protocols that he calls go back _n and selective repeat. However, he seems to be confusing two different dimensions in protocol design: receiver window size and ack semantics. The receiver window size is the amount of space the receiver has to buffer frames before passing them off to the higher layer; if the window size is 1, out-of- order frames are discarded. Ack semantics may be either _c_u_m_u_l_a_- _t_i_v_e or _i_n_d_i_v_i_d_u_a_l. A cumulative ack for frame _n acknowledges all frames with sequence numbers less than or equal to _n. An indivi- dual ack acknowledges only frame _n. Let _r be the round-trip delay, _t be the retransmission timeout (_t>_r), _f be the frame size in bits, and p be the data rate in bits/sec. Assume one-way data flow, with naked acks of insignifi- cant size. Calculate the total amount of channel capacity (in bits) wasted when a single frame is garbled in transmission under the following assumptions. (Assume the error rate is low enough that garbled frames are isolated events.) Justify your answers! (7a) Receiver window size is 1. (7b) Receiver window size is arbitrarily large and acks are cumu- lative. How big does the receiver window have to be to ensure maximum throughput and avoid dropping any frames other than the one that is garbled? Can the sender adjust its retransmission strategy to take advantage of the large receiver window if it knows about it? (7c) Receiver window size is arbitrarily large and acks are indi- vidual. _D_e_p_t_h _8. _V_i_r_t_u_a_l _M_a_c_h_i_n_e: To implement a virtual machine, all operations that access hardware resources must be _v_i_r_t_u_a_l_i_z_a_b_l_e. In user mode, the Motorola 68000 permitted read-only access to the status register, which contains the interrupt mask, the user/supervisor mode bit, and the trace bit, among other things. This was changed on the Motorola 68010 to deny all access to the status register during user mode. Attempting to access the status register in user mode causes a privilege violation exception (interrupt/trap). (8a) Explain why the change was necessary to support virtual machines. (8b) Describe how an OS running on a virtual machine would access the real status register. Include both hardware and virtual machine software operations. SSSSpppprrrriiiinnnngggg 1111999999992222 OOOOppppeeeerrrraaaattttiiiinnnngggg SSSSyyyysssstttteeeemmmmssss PPPPaaaaggggeeee 4444 ooooffff 2222 _D_e_p_t_h _9. _F_i_l_e _S_e_r_v_e_r_s File servers can improve performance by caching file contents. (9a) Files might be cached by blocks or by whole files. What are the advantages and disadvantages of each of these techniques. (9b) Describe three places (in either the client or server) that these caches can be used. Also describe the advantages of each type of caching. _D_e_p_t_h _1_0. _P_r_o_c_e_s_s _M_i_g_r_a_t_i_o_n A process migrates from the _o_l_d host to the _n_e_w host. (10a) In a message based operating system, after a process have migrated, messages sent to that process have to be sent to the new host. Describe two methods that processes who are currently communicating with the migrated process can use to find its new location. What are the advantages and disadvan- tages of these methods? (10b) If the difference between the clocks on the old and new host is large, what problems could this cause? How can you get around this problem?