OS Prelim Information

- Spring 1997-

Summaries and other information are available from the fall 1996 OS prelim page. Also see the fall 1997 OS prelim page.

Questions

1. [Smith] What must an OS for a real-time system do differently than a conventional OS?
2. [Brewer] What is a network computer, and what are its advantages over a PC? If there is a disk, what should it be used for? How would a typical large application (like Excel or Emacs) be run? How does Java fit in?
3. [Smith] What support could the OS provide for conserving power on a laptop?
4. [Brewer] What is wrong with RAID? (Small writes.) How has this problem been dealt with? (See Zebra and HP AutoRAID.)

Reading List

For each online paper, if there is already a stable copy in the cs.berkeley.edu domain, I just link to it. For more remote or less stable copies, I generally provide a link to a local copy, plus links to one or more remote pages (to show that I wasn't the first to put them on the web). I think copyright law allows me to make copies of papers for academic purposes. Access to local copies of papers is restricted to the cs.berkeley.edu domain. For papers available only as a hyperlinked tree of files, I don't provide a local copy.

For offline papers, the note "[RR]" indicates that the paper is available in the reading room (681 Soda). Please do not remove them from the reading room for more than a few minutes at a time (long enough to photocopy them), and put them back in the proper place.

The notes "[AMC]" provide links to summaries that I have written.

Undergraduate material

• Operating System Concepts, Fourth Edition
  A. Silberschatz, and P.B. Galvin
  Addison-Wesley, 1994

• Modern Operating Systems
  A. Tanenbaum

• Computer Architecture: A Quantitative Approach
  David Patterson, and John Hennessey
  MorganKaufman, 1990

• Internetworking with TCP/IP, Second Edition
  D.E. Comer
  Prentice-Hall, 1991
  [RR]

• An Introduction to Programming with Threads
  Research Report 35
  Andrew Birrell
  Digital Equipment Corporation Systems Research Center
  1991
  [source] [AMC]

• Working Sets, Past and Present
  Peter Denning
  IEEE Transactions on Software Engineering
  Vol. SE-6, No. 1 (January 1980), pp. 64-84
  [RR]

• 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
  [RR]

• Input/Output Optmizations and Disk Architectures: A Survey
  Alan Jay Smith
  Performance Evaluation
  Vol. 1 (1981), pp. 104-117

• 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

• The Transaction Concept: Virtues and Limitations
  Jim Gray
  Proceedings of the Seventh International Conference on Very Large Data Bases
  September 1981, pp. 144-154

• Recovery Techniques for Database Systems
  J.S.M. Verhofstad
  Computing Surveys
  Vol. 10, No. 2 (June 1978), pp. 167-195
  [RR]

• Data Security,
  D.E. Denning, and P.J. Denning
  Computing Surveys
  Vol. 11, No. 3 (September 1979), pp. 227-249
  [RR]

Concurrency, Scheduling and Synchronization

• Experience with Processes and Monitors in Mesa
  B.W. Lampson, and D.D. Redell
  Communications of the ACM
  Vol. 23, No. 2 (Feb 1980), pp. 105-117
  [RR]

• 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

• Metascheduling for Continuous Media
  D.P. Anderson
  ACM Transactions on Computer Systems
  Vol. 11, No. 3 (August 1993), pp. 226-253

• 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
  [source]

Communication: Local and Remote

• 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

• 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

• 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

• 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

• 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

• 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
  [source]

• On the Self-Similar Nature of Ethernet Traffic (pdf)
  W. Leland, M. Taqqu, W. Willinger, and D. Wilson
  Proceedings of SIGCOMM '93
  September 1993, pp. 183-193
  [source]

• 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
  [source]

File Systems

• 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
  [RR]

• 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

• 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

• 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

• 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

• 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
  [source]

• 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

• 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
  [source]

• 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
  [source]

Virtual Memory

• 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

• 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

• 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

• The Duality of Memory and Communication in the Implementation of a Multiprocessor Operating System
  Michael Young
  Proceedings of the 11th ACM Symposium on Operating Systems Principles
  November 1987, pp. 63-76
  [source]

• 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
  [source]

Multiprocessors

• 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

• 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

• 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

• 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
  [source]

Distributed Systems

• 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
  [RR]

• 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
  [RR]

• Grapevine: An Exercise in Distributed Computing
  A.D. Birrell et al.
  Communications of the ACM
  Vol. 25, No. 4 (April 1982), pp. 260-274
  [RR]

• 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

• 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

• 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
  [AMC]

• 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

• 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
  [source]

• Some Computer Science Issues in Ubiquitous Computing
  M. Weiser
  Communications of the ACM
  Vol. 36, No. 7 (July 1993), pp. 74-83
  [source]

Transactions, Recovery, and Fault-Tolerance

• Operating System Support for Database Management
  Michael Stonebraker
  Communications of the ACM
  Vol. 24, No. 7 (July 1981), pp. 412-418
  [RR]

• 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
  [RR]

• 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

• 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

• 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
  [RR]

• The Protection of Information in Computer Systems
  Jerome H. Saltzer
  Proceedings of the IEEE
  Vol. 63, No. 9 (September 1975), pp. 1278-1308

• 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

• 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
  [RR]

• 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
  [source] [source] [AMC]

• Other Kerberos papers
  (These are not on the reading list, but the previous paper does not cover the motivation, strengths, and weaknesses of the Kerberos protocol.)

• A Logic of Authentication (long version)
  M. Burrows, M. Abadi, and R. Needham
  ACM Transactions on Computer Systems
  Vol. 8, No. 1 (Feb 1990), pp. 18-36

Operating System Structure

• The Structuring of Systems Using Upcalls
  D.D. Clark
  Proceedings of the 10th ACM Symposium on Operating Systems Principles
  December 1985, pp. 171-180
  [RR]

• Why Aren't Operating Systems Getting Faster as Fast as Hardware?
  J.K. Ousterhout
  USENIX Summer Conference Proceedings
  June 1990, pp. 247-256

• 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
  [AMC]

• 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
  [source] [source] [source] [source]

• 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
  [source]

Specific Operating Systems

• The Structure of the THE Multiprogramming System
  E. Dijkstra
  Communications of the ACM
  Vol. 11, No. 5 (May 1968), pp. 341-346

• Survey of Virtual Machine Research
  Goldberg, R.P.
  IEEE Computer
  Vol. 7, No. 6 (June 1974), pp. 34-45

• 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
  [RR]

• UNIX Implementation
  K. Thompson
  The Bell System Technical Journal
  Vol. 57, No. 6 (July-August 1978), Part 2, pp. 1931-1946

• The V Distributed System,
  D. Cheriton
  Communications of the ACM
  Vol. 31, No. 3 (March 1988), pp. 314-333
  [RR]

• 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
  [source]

• 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
  [source]

• Plan 9 from Bell Labs (html)
  Rob Pike, Dave Presotto, Ken Thompson, and Howard Trickey
  Proceedings of the UKUUG Summer 1990 Conference
  1990
  [source]

• Plan 9, a Distributed System
  Rob Pike, Dave Presotto, Ken Thompson, and Howard Trickey
  [source]
  (This is not on the reading list, but is related to the previous paper.)

Removed from last semester's reading list:

• Extensibility, Safety, and Performance in the SPIN Operating System
  Brian Bershad, Stefan Savage, Przemyslaw Pardyak, Emin Gun Sirer, David Becker, Marc Fiuczynski, Craig Chambers, and Susan Eggers
  Proceedings of the 15th ACM Symposium on Operating System Principles
  pp. 267-284
  [source]

• Exokernel: An Operating System Architecture for Application-Level Resource Management
  Dawson R. Engler, M. Frans Kaashoek, and James O'Toole Jr.
  Proceedings of the 15th ACM Symposium on Operating Systems Principles
  December 1995
  [source]

Revealed Truth

• The Emperor's Old Clothes.
  C.A.R. Hoare
  Communications of the ACM
  Vol. 24, No. 2 (Feb 1981), pp. 75-83
  [source] [AMC]
  (I took the liberty of fixing typos and cleaning up the HTML.)

• Hints for Computer System Design,
  B.W. Lampson
  Proceedings of the 9th ACM Symposium on Operating Systems Principles
  October 1983, pp. 33-48

Removed from last semester's reading list:

• End-to-End Arguments in System Design