UC Berkeley Operating System Prelims
Fall 2001

Papers and Comments (local links accessible only within the eecs domain)

Undergraduate Materials
1. Operating System Concepts, Fourth Edition. A. Silberschatz, and P.B. Galvin. Addison-Wesley, 1994.
2. Modern Operating Systems. A. Tanenbaum.
3. Computer Architecture: A Quantitative Approach. David Patterson, and John Hennessey. Morgan Kaufman, 1990.
4. Internetworking with TCP/IP, Second Edition. D.E. Comer. Prentice-Hall, 1991.
5. An Introduction to Programming with Threads. Research Report 35. Andrew Birrell. Digital Equipment Corporation Systems Research Center. 1991. [EC 7/2/2001]
6. Working Sets, Past and Present. Peter Denning. IEEE Transactions on Software Engineering. Vol. SE-6, No. 1 (January 1980), pp. 64-84.
7. Virtual Memory Management in the VAX/VMS Operating System. H.M. Levy, and P.H. Lipman. IEEE Computer. Vol. 15, No. 3 (March 1982), pp. 35-41.
8. Input/Output Optimizations and Disk Architectures: A Survey. Alan Jay Smith. Performance Evaluation. Vol. 1 (1981), pp. 104-117.
9. A Fast File System For UNIX. M.K. McKusick, W.N. Joy, S.J. Leffler, and R.S. Fabry. ACM Transactions on Computer Systems. Vol. 2, No. 3 (August 1984), pp. 181-197.
10. The Transaction Concept: Virtues and Limitations. Jim Gray. Proceedings of the Seventh International Conference on Very Large Data Bases. September 1981, pp. 144-154.
11. Recovery Techniques for Database Systems. J.S.M. Verhofstad. Computing Surveys. Vol. 10, No. 2 (June 1978), pp. 167-195.
12. Data Security. D.E. Denning, and P.J. Denning. Computing Surveys. Vol. 11, No. 3 (September 1979), pp. 227-249. [EC 8/8/2001]


Concurrency, Scheduling, and Synchronization (summary)
1. Lampson, B.W., and Redell, D.D. Experience with Processes and Monitors in Mesa. Communications of the ACM, Vol. 23, No. 2 (Feb 1980), pp. 105-117.
2. Threads and Input/Output in the Synthesis Kernel. H. Massalin, and C. Pu. Proceedings of the 12th ACM Symposium on Operating Systems Principles December 1989, pp. 191-200 [US 7/3/2001]
3. D.P. Anderson. Metascheduling for Continuous Media. ACM Transactions on Computer Systems. Vol. 11, No. 3 (August 1993), pp. 226-253.
4. Lottery Scheduling: Flexible Proportional Share Resource Management. C. Waldspurger, and W. Weihl. Proceedings of the First Symposium on Operating Systems Design and Implementation. November 1994, pp. 1-12 [US 7/5/2001]


Communication: Local and Remote (summary)
5. Implementing Remote Procedure Calls. A.D. Birrell, and B.J. Nelson. ACM Transactions on Computer Systems. Vol. 2, No. 1 (Feb 1984), pp. 39-59.
6. RPC in the x-Kernel: Evaluating New Design Techniques. L. Peterson, N. Hutchinson, S. O'Malley, and M. Abbott. Proceedings of the 12th ACM Symposium on Operating Systems Principles. December 1989, pp. 91-101.
7. Lightweight Remote Procedure Call. B.N. Bershad, T.E. Anderson, E.D. Lazowska, and H.M. Levy. ACM Transactions on Computer Systems. Vol. 8, No. 1 (Feb 1990), pp. 37-55. [Journal Version]
8. Active Messages: A Mechanism for Integrated Communication and Computation. T. von Eicken, D.E. Culler, S.C. Goldstein, and K.E. Schauser. Proceedings of the Nineteenth Annual International Symposium on Computer Architecture. May 1992, pp. 256-266. [US 7/3/2001]
9. Efficient Software-Based Fault Isolation. R. Wahbe, S. Lucco, T.E. Anderson, and S.L. Graham. Proceedings of the 14th ACM Symposium on Operating Systems Principles. December 1993, pp. 203-216.
10. Protocol Service Decomposition for High-Performance Networking. C. Maeda, and Brian N. Bershad. Proceedings of the 14th ACM Symposium on Operating Systems Principles. December 1993, pp. 244-255. [US 7/5/2001]
11. On the Self-Similar Nature of Ethernet Traffic. W. Leland, M. Taqqu, W. Willinger, and D. Wilson. Proceedings of SIGCOMM '93. September 1993, pp. 183-193.
12. How to Get Good Performance from the CM5 Data Network. E. Brewer, and B. Kuszmaul. Proceedings of the Eighth International Parallel Processing Symposium. April 1994, pp. 858-867.


File Systems (summary)
13. Design and Implementation of the Sun Network Filesystem. R. Sandberg, D. Goldberg, S. Kleiman, D. Walsh, and B. Lyon. USENIX Summer Conference Proceedings. June 1985, pp. 119-130.
14. Scale and Performance in a Distributed File System. J.H. Howard et al. ACM Transactions on Computer Systems. Vol. 6, No. 1 (Feb 1988), pp. 51-81. [US 7/11/2001]
15. Caching in the Sprite Network File System. M.N. Nelson, B.B. Welch, and J.K. Ousterhout. ACM Transactions on Computer Systems. Vol. 6, No. 1 (Feb 1988), pp. 134-154.
16. Measurements of a Distributed File System. M.G. Baker, J.H. Hartman, M.D. Kupfer, K.W. Shirriff, and J.K. Ousterhout. Proceedings of the 13th ACM Symposium on Operating Systems Principles. October 1991, pp. 198-212. [Correction letter]
17. The Design and Implementation of a Log-Structured File System. M. Rosenblum, and J.K. Ousterhout. ACM Transactions on Computer Systems. Vol. 10, No. 1 (Feb 1992), pp. 26-52. [US 7/13/2001]
18. Disconnected Operation in the Coda File System. J.J. Kistler, and M. Satyanarayanan. ACM Transactions on Computer Systems. Vol. 10, No. 1 (Feb 1992), pp. 3-25.
19. The Zebra Striped Network File System. John H. Hartman, and John K. Ousterhout. Proceedings of the 14th ACM Symposium on Operating Systems Principles. December 1993, pp. 29-43. [US 7/11/2001]
20. Extensible File Systems in Spring. Y.A. Khalidi, and M.N. Nelson. Proceedings of the 14th ACM Symposium on Operating Systems Principles. December 1993, pp. 1-14.
21. Cooperative Caching: Using Remote Client Memory to Improve File System Performance. M. Dahlin, T. Anderson, D. Patterson, and R. Wang. Proceedings of the First Symposium on Operating Systems Design and Implementation. November 1994, pp. 267-280.


Virtual Memory (summary)
22. Virtual Memory, Processes, and Sharing in MULTICS. Robert C. Daley, and Jack B. Dennis. Communications of the ACM. Vol. 11, No. 5 (May 1968), pp. 306-312.
23. The MULTICS Virtual Memory: Concepts and Design. A. Bensoussan, C. Clingen, and R. Daley. Communications of the ACM. Vol. 15, No. 5 (May 1972), pp. 308-318.
24. Machine-Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures. R.F. Rashid et al. IEEE Transactions on Computers. Vol. 37, No. 8 (August 1988), pp. 896-908.
25. The Duality of Memory and Communication in the Implementation of a Multiprocessor Operating System. Michael Young et al. Proceedings of the 11th ACM Symposium on Operating Systems Principles. November 1987, pp. 63-76.
26. Application-Controlled Physical Memory using External Page-Cache Management. K. Harty, and D.R. Cheriton. ACM Proceedings of the Fifth International Conference on Architectural Support for Programming Languages and Operating Systems. October 1992, pp. 187-199.


Multiprocessors (summary)
27. Memory Coherence in Shared Virtual Memory Systems. K. Li, and P. Hudak. ACM Transactions on Computer Systems. Vol. 7, No. 4 (November 1989), pp. 321-359.
28. Simple But Effective Techniques for NUMA Memory Management. W. Bolosky, R. Fitzgerald, and M. Scott. Proceedings of the 12th ACM Symposium on Operating Systems Principles. December 1989, pp. 19-31.
29. Scheduler Activations: Effective Kernel Support for the User-Level Management of Parallelism. T. Anderson, B. Bershad, E. Lazowska, and H. Levy. ACM Transactions on Computer Systems. Vol. 10, No. 1 (Feb 1992), pp. 53-79. [EC 7/30/2001]
30. Evaluation of Release Consistent Software Distributed Shared Memory on Emerging Network Technology. S. Dwarkadas, P. Keleher, A.L. Cox, and W. Zwaenepoel. Proceedings of the Twentieth Annual International Symposium on Computer Architecture. May 1993, pp. 144-155.


Distributed Systems (summary)
31. Time, Clocks, and the Ordering of Events in a Distributed System. L. Lamport. Communications of the ACM. Vol. 21, No. 7 (July 1978), pp. 558-565.
32. The "Worm" Programs-Early Experience with a Distributed Computation. John F. Shoch, and Jon A. Hupp. Communications of the ACM. Vol. 25, No. 3 (March 1982), pp. 172-180.
33. Grapevine: An Exercise in Distributed Computing. A.D. Birrell et al. Communications of the ACM. Vol. 25, No. 4 (April 1982), pp. 260-274.
34. Experience with Grapevine: The Growth of a Distributed System. M.D. Schroeder, A.D. Birrell, and R.M. Needham. ACM Transactions on Computer Systems. Vol. 2, No. 1 (Feb 1984), pp. 3-23.
35. Fine-Grained Mobility in the Emerald System. E. Jul, H. Levy, N. Hutchinson, and A. Black. ACM Transactions on Computer Systems. Vol. 6, No. 1 (Feb 1988), pp. 109-133.
36. Transparent Process Migration: Design Alternatives and the Sprite Implementation. Fred Douglis, and John Ousterhout. Software Practice and Experience. Vol. 21, No. 7 (August 1991), p. 757. [A recent survey paper on process migration]
37. Lightweight Causal and Atomic Group Multicast. K. Birman, A. Schiper, and P. Stephenson. ACM Transactions on Computer Systems. Vol. 9, No. 3 (August 1991), pp. 272-314. [some slides] [some more slides from here]
38. Understanding the Limitations of Causally and Totally Ordered Communication. David D. Cheriton, and Dale Skeen. Proceedings of the 14th ACM Symposium on Operating Systems Principles. December 1993, pp. 44-57.
39. Some Computer Science Issues in Ubiquitous Computing. M. Weiser. Communications of the ACM. Vol. 36, No. 7 (July 1993), pp. 75-84. [The Computer for the 21st Century]


Transactions, Recovery, and Fault-Tolerance (summary)
40. Operating System Support for Database Management. Michael Stonebraker. Communications of the ACM. Vol. 24, No. 7 (July 1981), pp. 412-418. [EC 8/2/2001]
41. A NonStop Kernel. Joel F. Bartlett. Proceedings of the 8th ACM Symposium on Operating Systems Principles. Operating Systems Review. Vol. 15, No. 5 (December 1981), pp. 22-29. [External Notes]
42. Recovery Management in QuickSilver. Roger Haskin, Yoni Malachi, Wayne Sawdon, and Gregory Chan. ACM Transactions on Computers. Vol. 6, No. 1 (Feb 1988), pp. 82-108.
43. Lightweight Recoverable Virtual Memory. M. Satyanarayanan, H.H. Mashburn, P. Kumar, D.C. Steere, and J.J. Kistler. ACM Transactions on Computer Systems. Vol. 12, No. 1 (Feb 1994), pp. 33-58.


Protection and Security (summary)
44. A Hardware Architecture for Implementing Protection Rings. M.D. Schroeder, and J.H. Saltzer. Communications of the ACM. Vol. 15, No. 3 (March 1972), pp. 157-170.
45. The Protection of Information in Computer Systems. Jerome H. Saltzer. Proceedings of the IEEE. Vol. 63, No. 9 (September 1975), pp. 1278-1308. [a copy with inline graphics] and [a copy with frames around the inline graphics]
46. Privacy and Authentication: An Introduction to Cryptography. Whitfield Diffie, and Martin Hellman. Proceedings of the IEEE. Vol. 67, No. 3 (March 1979), pp. 397-427.
47. Using Encryption for Authentication in Large Networks of Computers. R.M. Needham, and M.D. Schroeder. Communications of the ACM. Vol. 21, No. 12 (December 1978), pp. 993-999.
48. Kerberos: An Authentication Service for Open Network Systems. J.G. Steiner, C. Neuman, and J.I. Schiller. USENIX Winter Conference Proceedings. Feb 1988, pp. 191-202. [Kerberos home page] [Limitations of Kerberos Authentication System]
49. A Logic of Authentication. M. Burrows, M. Abadi, and R. Needham. ACM Transactions on Computer Systems. Vol. 8, No. 1 (Feb 1990), pp. 18-36. [DEC SRC publication]


Operating System Structure (summary)
50. The Structuring of Systems Using Upcalls. D.D. Clark. Proceedings of the 10th ACM Symposium on Operating Systems Principles. December 1985, pp. 171-180. [EC 8/17/2001]
51. Why Aren't Operating Systems Getting Faster as Fast as Hardware? J.K. Ousterhout. USENIX Summer Conference Proceedings. June 1990, pp. 247-256.
52. The Interaction of Architecture and Operating System Design. Thomas Anderson, Henry Levy, Brian Bershad, and Edward Lazowska. ACM Proceedings of the Fourth International Conference on Architectural Support for Programming Languages and Operating Systems. April 1991.
53. The Impact of Operating System Structure on Memory System Performance. J. Bradley Chen, and Brian N. Bershad. Proceedings of the 14th ACM Symposium on Operating Systems Principles. December 1993, pp. 120-133.
54. A Caching Model of Operating System Kernel Functionality. D. Cheriton, and K. Duda. Proceedings of the First Symposium on Operating Systems Design and Implementation. November 1994. [another copy (but the last page doesn't print for me)]


Specific Operating Systems (summary)
55. The Structure of the THE Multiprogramming System. E. Dijkstra. Communications of the ACM. Vol. 11, No. 5 (May 1968), pp. 341-346. [EC 8/19/2001]
56. Survey of Virtual Machine Research. Goldberg, R.P. IEEE Computer. Vol. 7, No. 6 (June 1974), pp. 34-45. [EC 8/19/2001]
57. HYDRA: The Kernel of a Multiprocessor Operating System. W. Wulf, E. Cohen, W. Corwin, A. Jones, R. Levin, C. Pierson, and F. Pollack Communications of the ACM. Vol. 17, No. 6 (June 1974), pp. 337-344.
58. UNIX Implementation. K. Thompson. The Bell System Technical Journal. Vol. 57, No. 6 (July-August 1978), Part 2, pp. 1931-1946. [CACM paper]
59. The V Distributed System, D. Cheriton. Communications of the ACM. Vol. 31, No. 3 (March 1988), pp. 314-333.
60. Amoeba: A Distributed Operating System for the 1990s. S.J. Mullender, G. van Rossum, A.S. Tanenbaum, R. van Renesse, and H. van Staveren. IEEE Computer. Vol. 23, No. 5 (May 1990), pp. 44-53.
61. Overview of the Chorus Distributed Operating System. M. Rozier et al. Proceedings of the USENIX Workshop on Micro-kernels and Other Kernel Architectures. April 1992, pp. 39-70.
62. Plan 9 from Bell Labs. Rob Pike, Dave Presotto, Ken Thompson, and Howard Trickey. Proceedings of the UKUUG Summer 1990 Conference. 1990. [A later paper]


Revealed Truth (summary)
63. The Emperor's Old Clothes. C.A.R. Hoare. Communications of the ACM. Vol. 24, No. 2 (Feb 1981), pp. 75-83.
64. Hints for Computer System Design. B.W. Lampson. Proceedings of the 9th ACM Symposium on Operating. Systems Principles. October 1983, pp. 33-48.

Other Resources