Reading List: Advanced Operating Systems

Experience and advice

See Advice to systems researchers page.

Virtual memory, kernel structures, and extensibility

Historical perspective and futures

R. C. Daley and J. B. Dennis. Virtual Memory, Processes, and Sharing in MULTICS. Communications of the ACM, 11(5), May 1968, pp. 306-312
Jerome H. Saltzer. Protection and the Control of Information Sharing in Multics. Communications of the ACM 17(7), July 1974.
Per Brinch Hansen. The Nucleus of a Multiprogramming System. Communications of the ACM 13(4), April 1970
E. W. Dijkstra. The Structure of the "THE" Multiprogramming System. Communications of the ACM, 11(5), May 1968, pp. 341-346
D. M. Ritchie and K. Thompson. The UNIX Time-Sharing System. [ps] Communications of the ACM, 17(7), July 1974, pp. 365-375.
W. A. 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, 17(6), June 1974, pp. 337-345.
Mark Weiser, The computer for the 21st century, Scientific American, vol. 265, no. 3, September 1991, pp. 94-104. (Weiser's ubiquitous computing web page).

Virtual memory

H. M. Levy and P. H. Lipman. Virtual Memory Management in the VAX/VMS Operating Systems. IEEE Computer, 15(3), March 1982, pp. 35-41
Kieran Harty and David R. Cheriton. Application-Controlled Physical Memory using External Page-Cache Management. Proc. of the 5th International Conference on Architectural Support for Programming Languages and Operating Systems, 1992, pp. 187-197.
Andrew W. Appel and Kai Li. Virtual Memory Primitives for User Programs . Proc. of the 5th International Conference on Architectural Support for Programming Langauges and Operating Systems, 1992.
M. Satyanarayanan, Henry H. Mashburn, Puneet Kumar, David C. Steer, and James J. Kistler. Lightweight Recoverable Virtual Memory. Proceedings of the 14th ACM Symposium on Operating Systems Principles, December 1993.
Richard Rashid, Avadis Tevanian, Michael Young, David Golub, Robert Baron, David Black, William Bolosky, and Jonathan Chew. Machine-Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures . Proc. of the 2nd International Conference on Architectural Support for Programming Languages and Operating Systems, October 1987, pp. 31-39.
Kai Li and Paul Hudak. Memory Coherence in Shared Virtual Memory Systems. ACM Trans. on Computer Systems 7(4), November 1989, pp. 321-359.
Daniel Scales and Kourosh Gharachorloo. Towards Transparent and Efficient Software Distributed Shared Memory. Proc. of the 16th ACM Symp. on Operating Systems Principles, Oct. 1997, pp. 157-169.

Kernel structures and extensibility

H. Massalin and Calton Pu. Threads and Input/Output in the Synthesis Kernel. [ps] Proc. 12th SOSP, Operating Systems Review, 23(5), December 1989, pp. 191-201.
D. R. Engler, M. F. Kaashoek, and J. O'Toole Jr. Exokernel: An Operating System Architecture for Application-Level Resource Management. [ps] Proc. 15th SOSP, December 1995, pp. 251-266.
M. Frans Kaashoek, Dawson R. Engler, Gregory R. Ganger, Hector M. Briceno, Russell Hunt, David Mazieres, Thomas Pinckney, Robert Grimm, John Jannotti, and Kenneth Mackenzie. Application Performance and Flexibility on Exokernel Systems. Proc. of the 16th ACM. Symposium on Operating Systems Principles, October 1997.
E. Bugnion, S. Devine, and M. Rosenblum. Disco: Running Commodity Operating Systems on Scalable Multiprocessors. [ps] Proc. 16th SOSP, October 1997, pp. 143-156.

Threads, synchronization, and communication

Threads and concurrency

B. W. Lampson and D. D. Redell. Experience with Processes and Monitors in Mesa. Communications of the ACM, 23(2), February 1980, pp. 105-117.
A. D. Birrell. An Introduction to Programming with Threads. [ps] Tech. Rep. SRC-035, Digital Equipment Corporation, January 1989.
M. Herlihy. A Methodology for Implementing Highly Concurrent Data Structures. Proc. of the 2nd ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming, March 1990, pp. 197-206.

Communication

A. D. Birrell and B. J. Nelson. Implementing Remote Procedure Calls. ACM Transactions on Computer Systems, 2(1), February 1984, pp. 39-59.
K. Li and P. Hudak. Memory Coherence in Shared Virtual Memory Systems. ACM Trans. on Computer Systems 7(4), November 1989, pp. 321-359.
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. [ps] Proc. 11th SOSP, Operating Systems Review, 21(5), November 1987, pp. 63-76.
T. von Eicken, D. E. Culler, S. C. Goldstein, K. E. Schauser. Active Messages: A Mechanism for Integrated Communication and Computation. [ps] Proc. 19th ISCA, May 1992, pp. 256-266.

Scheduling

T. Anderson, B. Bershad, E. Lazowska, and H. Levy. Scheduler Activations: Effective Kernel Support for the User-Level Management of Parallelism. Proc. 13th SOSP, ACM Transactions on Computer Systems, 10(1), February 1992, pp. 95-109.
P. Goyal, X. Guo, and H.M. Vin. A Hierarchical CPU Scheduler for Multimedia Operating Systems. [ps] Proceedings of the Second Symposium on Operating Systems Design and Implementations (OSDI'96), Seattle, Washington, Pages 107-122, October 1996

Current topics

X. Qie, A. Bavier, L. Peterson, and S. Karlin. Scheduling Computations on a Software-Based Router. [ps] Proc. SIGMETRICS 2001, June 2001.
T. Spalink, S. Karlin, L. Peterson, and Y. Gottlieb. Building a Robust Software-Based Router Using Network Processors. [ps] Proc. 18th SOSP, October 2001

File Systems

Local performance

Chris Ruemmler and John Wilkes, An Introduction to Disk Drive Modeling. IEEE Computer, 27(3), pp 17--28, 1994
M. K. Mckusick, W. N. Joy, S. J. Leffler, and R. S. Fabry. A Fast File System for UNIX. [ps] ACM Transactions on Computer Systems, 2(3), August 1984, pp. 181-197.

Integrity

J. Gray, The Transaction Concept: Virtues and Limitations. VLDB 1981, pp. 144-154.
M. Rosenblum and J. Ousterhout. The Design and Implementation of a Log-Structured File System. [ps] ACM Transactions on Computer Systems, 10(1), February 1992, pp. 26-52.
G. Ganger, M.K. McKusick, C. Soules, and Y. Patt. Soft Updates: A Solution to the Metadata Update Problem in File Systems. ACM Transactions on Computer Systems, 18(2), pp. 127-153.

Modern local file systems

D. Hitz, J. Lau, M. Malcolm. File System Design for an NFS File Server Appliance. USENIX Winter Technical Conference, January 1994, pp. 235-246
Adam Sweeney, Doug Doucette, Wei Hu, Curtis Anderson, Mike Nishimoto, and Geoff Peck, Scalability in the XFS File System. [html] USENIX Technical Conference, January 1996.

RAID

P. Chen, E. Lee, G. Gibson, R. Katz, and D. Patterson. RAID: High-Performance, Reliable Secondary Storage. ACM Computing Surveys, 26(2), June 1994, pp. 145-188.
John Wilkes, Richard Golding, Carl Staelin, and Tim Sullivan. The HP AutoRAID Hierarchical Storage System. ACM Transactions on Computer Systems, Vol. 14, No. 1, February 1996, pages 108-136.

Distributed File systems, consistency

R. Sandberg, D. Goldberg, S. Kleiman, D. Walsh, and B. Lyon. Design and Implementation of the Sun Network Filesystem. Proc. USENIX Summer Conference, June 1985, pp. 119-130.
M. N. Nelson, B. B. Welch, and J. K. Ousterhout. Caching in the Sprite Network File System. [ps] ACM Transactions on Computer Systems, 6(1), February 1988, pp. 134-154.
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, 6(1), February 1988, pp. 51-81
H.T. Kung and J. Robinson. On Optimistic Methods for Concurrency Control. ACM Transactions on Database Systems, 6(2), June 1981, pp. 213-226.

Cluster file systems

T. E. Anderson, M. D. Dahlin, J. M. Neefe, D. A. Patterson, D. S. Roselli, and R. Y. Wang. Serverless Network File Systems. [ps] Proc. 15th SOSP, ACM Transactions on Computer Systems, 14(1), February 1996, pp. 41-79.
Chandramohan Thekkath, Timothy Mann, and Edward Lee. Frangipani: A Scalable Distributed File System. Proc. of the 16th ACM Symposium on Operating Systems Principles, October 1997, pages 224-237.
G. Gibson, D. Nagle, et. al, A Cost-Effective, High-Bandwidth Storage Architecture 8th Conf. on Architectural Support for Programming Languages and Operating Systems, October 1998, pp. 92-103

Replicated file systems

J. Kistler and M. Satyanarayanan. Disconnected Operation in the Coda File System. ACM Transactions on Computer Systems. Feb. 1992, 10(1), pp. 3-25.
B. Walker, G. Popek, R. English, C. Kline, and G. Thiel. The LOCUS Distributed Operating System. Proc. 9th SOSP, Operating Systems Review, 17(5), November 1983, pp. 49-70.
G. Kuenning and G. Popek. Automated Hoarding for Mobile Computers. Proc. of the 16th ACM Symposium on Operating Systems Principles, October 1997
K. Petersen, M. J. Spreitzer, D. B. Terry, M. M. Theimer, and A. J. Demers. Flexible Update Propagation for Weakly Consistent Replication [ps] Proceedings of the 16th ACM Symposium on Operating Systems Principles (SOSP-16), Saint Malo, France, October 5-8, 1997, pages 288-301.
D. B. Terry, M. M. Theimer, K. Petersen, A. J. Demers, M. J. Spreitzer, and C. Hauser. Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System Proceedings 15th Symposium on Operating Systems Principles (SOSP-15) , Copper Mountain, Colorado, December 1995, pages 172-183.
B. Terry, A. J. Demers, K. Petersen, M. J. Spreitzer, M. M. Theimer, and B. B. Welch. Session Guarantees for Weakly Consistent Replicated Data. [ps] Proceedings International Conference on Parallel and Distributed Information Systems (PDIS), Austin, Texas, September 1994, pages 140-149.

Security

Experience and failures

K. Thompson. Reflections on Trusting Trust. Communications of the ACM, 27(8), August 1984, pp. 761-763.
R. Anderson. Why Cryptosystems Fail. Communications of the ACM, 37(11), November 1994, pp. 32-40.
E. Spafford. Crisis and Aftermath. Communications of the ACM, 32(6), June 1989, pp. 678-687.

Engineering principles

J. Saltzer, M. Schroeder. The protection of information in computer systems [html], Proceedings of the IEEE, vol. 63, no. 9, September 1975, pp. 1278-130
Martin Abadi and Roger Needham, Prudent Engineering Practice for Cryptographic Protocols. Software Engineering vol. 22, no. 1, 1996, pp 6-15.

Authentication

M. Burrows and M. Abadi and R. Needham. A Logic of Authentication. ACM Transactions on Computer Systems, 8(1), Feb 1990 pp. 18--36.
Ronald Rivest and Butler Lampson. SDSI - A Simple Distributed Security Infrastructure [html]. 1996
Butler Lampson, Martin Abadi, Michael Burrows, and Edward Wobber. Authentication in Distributed Systems: Theory and Practise SOSP-91, full tech report
E. Belani, A. Vahdat, T. Anderson, and M. Dahlin. The CRISIS Wide Area Security Architecture. [ps] 1998 USENIX Security Symposium. Jan 1998.