UW Operating Systems
  Qualifying Exam

Past exams

Reading list

Starting in Spring 2005, Networking has its own Qualifying Exam and; therefore, this material is no longer included in the OS Qualifying Exam.

Textbooks

One of the following:

• A. Silberschatz and P. B. Galvin, Operating Systems Concepts (Fourth Edition), Addison-Wesley, Reading, MA, 1994.
• A. Silberschatz and P. B. Galvin, Operating Systems Concepts (Fifth Edition), Addison-Wesley, Reading, MA, 1998.

Memory management

• Daley, R.C., and Dennis, J.B. Virtual Memory, Processes, and Sharing in MULTICS, Communications of the ACM, Vol. 11, No. 5, May 1968, pages 306-312. [paper]
• P. J. Denning. The Working Set Model of Program Behavior, Communications of the ACM, May 1968, pages 323-333. [paper]
• R. Carr and J. Hennessy. WSCLOCK - A Simple and Effective Algorithm for Virtual Memory Management, Proceedings of the Eighth ACM Symposium on Operating System Principles, December 1981, pages 87-95. [paper]
• O. Babaogul and W. Joy. Converting a Swap-Based System to do Paging in an Architecture Lacking Page-Reference Bits, Proceedings of the Eighth ACM Symposium on Operating System Principles, December 1981, pages 78-86. [paper]

Synchronization and communication

• C. A. R. Hoare, Communicating Sequential Processes, Communications of the ACM, August 1978, pages 666-677. [paper]
• B. W. Lampson and D. D. Redell, Experiences with Process and Monitors in Mesa, Communications of the ACM, February 1980, pages 105-117. [paper]
• T. E. Anderson, B. N. Bershad, E. D. Lazowska, and H. M. Levy, Scheduler Activations: Effective Kernel Suport for the User-Level Management of Parallelism, ACM Transactions on Computer Systems, February 1992, pages 53-79. [paper]
• Waldspurger, C.A. and Weihl, W.E. Lottery Scheduling: Flexible Proportional-Share Resource Mangement, Proceedings of the First Symposium on Operating Systems Design and Implementation, Monterey CA, November 1994, pages 1-11. [paper]
• Banga, G., Druschel, P,. Mogul, J. Resource Containers: A New Facility for Resource Management in Server Systems, Proceedings of the Third Symposium on Operating System Design and Implementation (OSDI-III), New Orleans, LA, February, 1999, pages 45-58. [paper]

Protection and security

• F. T. Gramp and R. H. Morris, UNIX Operating System Security, AT&T Bell Laboratories Technical Journal, October 1984, pages 1649-1672. [paper]
• A. K. Jones and W. A. Wulf, Towards the Design of Secure Systems, Software - Practice and Experience, 1975, pages 321-336. [paper]
• G. J. Popek and C. S. Kline, Encryption and Secure Computer Networks, ACM Computing Surveys, December 1979, pages 331-356. Only sections 1-3. [paper]
• J. G. Steiner, C. Neuman, and J. I. Schiller, Kerberos: A Authentication Service for Open Network Systems, USENIX 1988, February 1998, pages 191-202. [paper]
• B. Lampson, M. Abadi, M. Burrows, and E. Wobber, Authentication in Distributed Systems: Theory and Practice, Proceedings of the Thirteenth ACM Symposium on Operating Systems Principles, October 13-16, 1991, pages 165-182. [paper]

File systems

• M. K. McKusick, W. N. Joy, S. J. Leffler, and R. S. Fabry, A Fast File System for UNIX, ACM Transactions on Computer Systems, August 1984, pages 181-197. [paper]
• M. Rosenblum and J. K. Ousterhout, The Design and Implementation of a Log-Structured File System, Proccedings of the Thirteenth ACM Symposium on Operating System Principles, October 13-16, 1991, pages 1-15. [paper]
• J. H. Howard, M. L. Kazar, S. G. Menees, D.A. Nichols, M. Satyanarayanan, R. N. Sidebotham, and M. J. West, Scale and Performance in a Distributed File System, ACM Transactions on Computer Systems, February 1988, pages 51-81. [paper]
• B. Walker, G. Propek, R. English, C. Kline, and G. Thiel, The LOCUS Distributed Operating System, Proceedings of the Ninth ACM Symposium on Operating Systems Principles, October 10-13, 1983, pages 49-70. [paper]
• V. Srinivasan and J. C. Mogul, Spritely NFS: Experiements with cache-consistency protocols, Proceedings of the Twelfth ACM Symposium on Operating Systems Principles, December 3-6, 1989, pages 45-57. [paper]
• J. J. Kistler and M. Satyanarayanan, Disconnected Operation in the Coda File System, Proceedings of the Thirteenth ACM Symposium on Operating Systems Principles, October 13-16, 1991, pages 213-225. [paper]
• Vivek Pai, Peter Drushel, Willy Zwaenepoel, IO-Lite: A Unified I/O Buffering and Caching System, Third Symposium on Operating Design and Implementation (OSDI), New Orleans, February 1999. [paper]

Distributed systems

• A. D. Birrell, R. Levin, R. M. Needham, and M. D. Schroeder, Grapevine: An Exercise in Distributed Computing, Communications of the ACM, April 1982, pages 260-274. [paper]
• A. D Birrell and B. J Nelson, Implementing Remote Procedure Calls, ACM Transactions on Computer Systems, February 1984, pages 39-59. [paper]
• D. R Cheriton and W. Zwaenepoel, The Distributed V Kernel and its Performance for Diskless Workstations, Proceedings of the Ninth ACM Symposium on Operating Systems Principles, October 10-13, 1983, pages 128-139. [paper]
• K. Birman, A. Schiper, and P. Stephenson, Lightweight Causal and Atomic Group Multicast, ACM Transactions on Computer Systems, August 1991, pages 272-314. [paper]
• K. M. Chandy and L. Lamport, Distributed Snapshots: Determining Global States of Distributed Systems, ACM Transactions on Computer Systems, February 1985, pages 63-75. [paper]
• L. Lamport, Time, Clocks, and the Ordering of Events in a Distributed System, Communications of the ACM, July 1978, pages 558-564. [paper]
• M.L. Powell and B.P. Miller, Process Migration in DEMOS/MP, 9th Symposium on Operating Systems Principles, Bretton Woods, NH, October 1983, pages 110-119. [paper]

Kernels

• Edsger W. Dijkstra, The Structure of the "THE" Multiprogramming System, Communications of the ACM 11(5), May 1968. [paper]
• Per Brinch Hansen, The Nucleus of a Multiprogramming System, Communications of the ACM 13(4), April 1970. [paper]
• D. D. Redell, Y. K. Dalal, T. R. Horsley, H. C. Lauer, W. C. Lynch, P. R. McJones, H. G. Murray, and S. C. Purcell, Pilot: An Operating System for a Personal Computer, Communications of the ACM, February 1980, pages 81-92. [paper]
• H. Massalin and C. Pu, Theads and Input/Output in the Synthesis Kernel, Proceedings of the Twelfth ACM Symposim on Operating System Principles, December 3-6, 1989, pages 191-201. [paper]
• M. Young, A. Tevanian, R. Rashid, D. Golub, J. Eppinger, J. Chew, W. Bolosky, D. Black, and R. Baron, The Duality of Memory and Communication in the Implementation of a Multiprocessor Operating System, Proceedings of the Eleventh ACM Symposium on Operating System Principles, November 8-11, 1987, pages 63-76. [paper]
• Kaashoek, M. F., Engler, D., Ganger, G., Brice, H., Hunt, R., Mazires, D., Pinckney, T., Grimm, R., Jannotti, J., and Mackenzie, K. Application Performance and Flexibility on Exokernel Systems, The Proceedings of the Sixteenth ACM Symposium on Operating Systems Principles, Saint-Malo, France, October 1997, pages 52-65. [paper]
• Edouard Bugnion, Scott Devine, Mendel Rosenblum. Disco: Running Commodity Operating Systems on Scalable Multiprocessors, Proceedings of The Sixteenth Symposium on Operating Systems Principles, October 1997. [paper]

Reliability and recovery

• L. Lamport, R. Shostak, and M. Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems, July 1982, pages 382-401. [paper]
• J. H. Saltzer, D. P. Reed, and D. D. Clark, End-To-End Arguments in System Design, ACM Transactions on Computer Systems, November 1984, pages 277-288. [paper]
• D. A. Patterson, G. Gibson, and R. H. Katz, A Case for Redundant Arrays of Inexpensive Disks (RAID), Proceedings of the ACM SIGMOD International Conference on Management of Data, 1988, pages 109-116. [paper]

Experience and systems reports

• B. W. Lampson, Hints for Computer System Design, Proceedings of the Ninth ACM Symposium on Operating System Principles, October 10-13, 1983, pages 33-48. [paper]
• H. C. Lauer, Observations on the Development of an Operating System, Proceedings of the Eight ACM Symposium on Operating System Principles, December 1981, pages 30-36. [paper]

Copyrights

ACM