Operating Systems Comps Reading List

Winter 2006 Revision

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 Tanenbaum; 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 ACM, 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," In 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." In 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.

faculty-sysnet@cs.ucsd.edu