Operating Systems - Comprehensive Examination Syllabus

Revised 2/2006

The OS comps is a combination of undergraduate and graduate material covering a series of OS topics. For undergraduate material, when appropriate, each section begins with references to chapters from Modern Operating Systems by Andrew Tananbaum; other undergraduate OS textbooks will have the same material as well.

The graduate material draws upon readings from CSE 221. All papers are accessible online via a UCSD computer. To access the papers from a non-UCSD computer, use the campus web proxy with your web browser.

Historical Perspective

• Chapters 1, 14, and 15.
• E.W. Dijkstra, The Structure of the 'THE'-Multiprogramming System, Communications of the ACEm Vol.11, No.5, May 1968, pp.341-346.
• P.B. Hansen, The Nucleus of a Multiprogramming System, Communications of the ACM, Vol.13, No.4, April 1970, pp.238-241, 250.
• D.G. Bobrow, J.D. Burchfiel, D.L. Murphy, and R.S. Tomlinson, TENEX, a Paged Time Sharing System for the PDP-10, Communications of the ACM, Vol.15, No. 3, March 1972, pp. 135-143.
• W. Wulf, E. Cohen, W. Corwin, A. Jones, R. Levin, C. Pierson, and F. Pollack, HYDRA: The Kernel of a Multiprocessor Operating System, Communications of the ACM, Vol. 17, No. 6, June 1974, pp. 337-345.
• J. H. Saltzer, Protection and the Control of Information Sharing in Multics, Communications of the ACM, Vol. 17, No. 7, July 1974, pp. 388-402.
• D. M. Ritchie and K. Thompson, The UNIX Time-Sharing System, Communications of the ACM, Vol. 17, No. 7, July 1974, pp. 365-375.

Structure

• Sections 4.4 and 4.5.
• B. Lampson, "Protection", Operating Systems Review, Vol. 8, No. 1, January 1974, pp. 18-24.
• 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, Vol. 23, No. 2, February 1980, pp. 81-92.
• J. K. Ousterhout, D. A. Scelza, and P. S. Sindhu, Medusa: An Experiment in Distributed Operating Systems Structure, Communications of the ACM, Vol. 23, No. 2, February 1980, pp. 92-105.
• D.D. Clark, The Structuring of Systems using Upcalls, Proceedings of the 10th Symposium on Operating Systems Principles. pp. 171-180, December 1985.

Distribution

• Chapter 10
• D. R. Cheriton and W. Zwaenepoel, The Distributed V Kernel and its Performance for Diskless Workstations, Proceedings of the 9th Symposium on Operating Systems Principles, pp. 129-140, November 1983.
• J. K. Ousterhout, A. R. Cerenson, F. Douglis, M. N. Nelson, and B. B. Welch, The Sprite Network Operating System, IEEE Computer, Vol. 21, No. 2, February 1988, pp. 23-36.
• G. J. Popek, B. Walker, J. Chow, D. Edwards, C. Kline, G. Rudisin, and G. Theil, "LOCUS: A Network Transparent, High Reliability Distributed System", Proceedings of the 8th Symposium on Operating Systems Principles, pp. 160-168, December 1981.
• M. D. Schroeder, A. D. Birrell, and R. M. Needham, "Experience with Grapevine: The Growth of a Distributed System", ACM Transactions on Computer Systems, Vol. 2, No. 1, February 1984.

Synchronization

• Chapters 2 and 6.
• C. A. R. Hoare, "Monitors: An Operating System Structuring Concept," Communications of the ACM, Vol. 17, No. 10, October, 1974, pp. 549-557.
• B. W. Lampson and D. D. Redell, "Experience with Processes and Monitors in Mesa," Communications of the ACM, Vol. 23, No. 2, February 1980, pp. 105-117.

Scheduling

• Thomas E. Anderson, Brian N. Bershad, Edward D. Lazowska, Hanry M. Levy, "Scheduler Activations: Effective Kernel Support for the User-level Management of Parallelism", Proceedings of the 13th ACM Symposium on Operating Systems Principles, Sept. 1991, pp. 95-109.
• Carl A. Waldspurger and William E. Weihl, "Lottery Scheduling: Flexible Proportional-Share Resource Management". In Proceedings of the First USENIX Symposium on Operating System Design and Implementation, November, 1994.

Communication

• Chapter 10.
• A. D. Birrell and B. J. Nelson, "Implementing Remote Procedure Calls", ACM Transactions on Computer Systems, Vol. 2, No. 1, pp. 39-59, February 1984.
• B. N. Bershad, T. E. Anderson, E. D. Lazowska, and H. M. Levy, "Lightweight Remote Procedure Call", Proceedings of the 12th Symposium on Operating Systems Principles, pp. 102-113, December 1989.

Virtual Memory

• Chapter 3
• H. M. Levy and P. Lipman, "Virtual Memory Management in VAX/VMS", IEEE Computer, Vol. 15, No. 3, March 1982, pp.35-41.
• Richard Rashid, Avadis Tevanian, Michael Young, David Golub, Robert Baronn, David Black, William Bolosky, and Jonathan Chew, "Machine-Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures", Proceedings of the Second International Conference on Architectural Support for Programming Languages and Operating Systems, October 1987, pp. 31-39.

I/O and File Systems

• Sections 4.1 and 4.5, and Chapter 5.
• Marshall K. McKusick, William N. Joy, Samuel J. Leffler, and Robert S. Fabry, "A Fast File System for Unix", ACM Transactions on Computer Systems, 2(3), August 1984, pp. 181-197.
• Mendel Rosenblum and John K. Ousterhout, "The Design and Implementation of a Log-Structured File System", Proceedings of the 13th ACM Symposium on Operating Systems Principles, December 1991.
• Gregory R. Ganger, Marshall Kirk McKusick, Craig A.N. Soules, and Yale N. Patt. "Soft Updates: A Solution to the Metadata Update Problem in File Systems", ACM Transactions on Computer Systems, Vol. 18, No. 2, May 2000, Pages 127-153.
• P. M. Chen, W. T. Ng, S. Chandra, C. Aycock, G. Rajamni, and D. Lowell, "The Rio File Cache: Surviving Operating System Crashes", In Proceedings of the Seventh International Conference on Architectural Support for Programming Languages and Operating Systems, SIGPLAN Notices 31(9):74-83, September 1996.

Extensibility

• B. N. Bershad, S. Savage, P. Pardyak, E. G. Sirer, M. E. Fiuczynski, D. Becker, C. Chambers, S. Eggers, "Extensibility, Safety and Performance in the SPIN Operating System". Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles, December 1995, Copper Mountain, CO, pp. 267-283.
• M. F. Kaashoek, D. R. Engler, G. R. Ganger, H. M. Briceno, R. Hunt, D. Mazieres, T. Pinckney, R. Grimm, J. Jannotti and K. Machkenzie, "Application Performance and Flexibility on Exokernel Systems". In Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles, October 1997, St Malo, France, pp. 52-65.