8/01/2006

OS Reading List @ Stanford

The following references cover the topics of which every researcher in operating systems should be aware. Students who read the following references and can apply the ideas presented in papers should do well on the Operating Systems part of the Systems Ph.D. Qualifying examination.
List last revised: 10/06/03
Links added: 01/26/06 by Brian D. Carlstrom



Operating System Structure
[Dijk68] Dijkstra, E.W., "The Structure of the THE Multiprogramming System" Communications of the ACM, Vol. 11, No. 5 (May 1968), 341-346. ACM PDF
[Ritc78] Ritchie, D.M., and Thompson, K., "The UNIX Time-Sharing System," The Bell System Technical Journal, Vol. 57, No. 6 (July-August 1978), Part 2, pp. 1905-1929. Author PDF
[Thom78] Thompson, K., "UNIX Implementation," The Bell System Technical Journal, Vol. 57, No. 6 (July-August 1978), Part 2, pp. 1931-1946. CiteSeer PDF
[Cher88] Cheriton, D.R., "The V Distributed System," Communications of the ACM, Vol. 31, No. 3 (March 1988), pp. 314-333. ACM PDF

Extending the Operating System
[Bers95] Bershad, B.N., Savage, S., Pardyak, P., Sirer, E.G., Fiuczunski, M., Becker, D., Chambers, C., and Eggers, S., "Extensibility: Safety and Performance in the SPIN Operating System," Proceedings of the 15th Symposium on Operating System Principles, December 1995, pp. 267-284. ACM PDF
[Engl95] Engler, D.R., Kaashoek, M.F., and O'Toole Jr., J., "Exokernel: an operating system architecture for application-specific resource management.", In Proceedings of the 15th Symposium on Operating System Principles, December 1995, pp. 251-266. ACM PDF
[Lied95] Liedtke, J., "On micro-kernel construction," In Proceedings of the 15th Symposium on Operating System Principles, December ACM PDF 1995.

Synchronization and Communication
[Lamp80] 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. ACM PDF
[Hoar78] Hoare, C.A.R., "Communicating Sequential Processes," Communications of the ACM, Vol. 21, No. 8 (Aug. 1978), pp. 666-677. ACM PDF
[Mass89] Massalin, H. and Pu, C., "Threads and Input/Output in the Synthesis Kernel," Proceedings of the 12th Symposium on Operating Systems Principles, December 1989, pp. 191-200. ACM PDF
[Coff71] Coffman, Jr., E.G., Elphick, M.J., and Shoshani, A., "System Deadlocks", Computing Surveys, Vol. 3, No. 2, June 1971, pp. 67-78. ACM PDF
[Bers93] Bershad, B.N., "Practical Considerations for Non-Blocking Concurrent Objects," Proceedings of the 13th International Conference on Distributed Computing Systems, May 1993. IEEE PDF
[Laue78] Lauer, H.C., and Needham, R. M., "On the Duality of Operating System Structures." Proc. Second International Symposium on Operating Systems, IRIA, October 1978, reprinted in Operating Systems Review, Vol. 13, No. 2, April 1979, pp. 3-19. ACM PDF
[Sava97] Savage, S., Burrows, M., Nelson, G., Sobalvarro, P., Anderson, T., "Eraser: A Dynamic Data Race Detector for Multi-Threaded Programs" SOSP '97. ACM PDF
[Mogu96] J. C. Mogul and K. K. Ramakrishnan. Eliminating receive livelock in an interrupt-driven kernel. In Proc. of the 1996 Usenix Technical Conference, pages 99--111, 1996. ACM PS

Virtual Memory
[Dale68] Daley, R.C., and Dennis, J.B., "Virtual Memory, Processes and Sharing in MULTICS," Communications of the ACM, Vol. 11, No. 5 (May 1968), pp. 306-312. ACM PDF
[Bens72] Bensoussan, A., Clingen, C.T., and Daley, R.C., "The MULTICS Virtual Memory: Concepts and Design," Communications of the ACM, Vol. 15, No. 5 (May 1972), pp. 308-318. ACM PDF
[Denn80] Denning, Peter J., "Working Sets, Past and Present," IEEE Transactions on Software Engineering, SE-6, 1 (January 1980), pp. 64-84. CiteSeer PDF
[Levy82] Levy, H.M., and Lipman, P.H., "Virtual Memory Management in the VAX/VMS Operating System," Computer, Vol. 15, No. 3 (March 1982), pp. 35-41. CS 240 PDF
[Hart92] Harty, K., and Cheriton, D., "Application-Controlled Physical Memory using External Page-Cache Management," Proceedings of the Fifth International Conference on Architectural Support for Programming Languages and Operating Systems, Boston, MA, October 1992, pp. 187-199. ACM PDF
[Bolo89] Bolosky, W., Fitzgerald, R., and Scott, M, "Simple But Effective Techniques for NUMA Memory Management." Proceedings of the 12th SOSP, Operating Systems Review, Vol. 23, No. 5, December 1989, pp. 19-31. ACM PDF
[Verg96] Verghese, B., Devine, S., Gupta, A., and Rosenblum, M., "Operating System Support for Improving Data Locality on CC-NUMA Compute servers," In Proceedings of the Seventh International Conference on Architectural Support for Programming Languages and Operating Systems, Cambridge, MA, 1996. ACM PDF
[Nav02] Navarro, J., Iyer, S., Druschel, P., Cox, A., "Practical, Transparent, Operating System Support for Superpages," Proceedings of USENIX OSDI 2002. ACM PDF
[Wald02] Waldspurger, C. Memory Resource Management in VMware ESX Server. Proceedings of USENIX OSDI 2002. ACM PDF

File Systems
[Smit81a] Smith, Alan Jay, "Input/Output Optimizations and Disk Architectures: A Survey," Performance Evaluation, Vol. 1, 1981, pp. 104-117. TBD TBD
[McKu84] McKusick, M.K., Joy, W.N., Leffler, S.J., and Fabry, R.S., "A Fast File System For UNIX," ACM Transactions on Computer Systems, Vol. 2, No. 3 (August 1984), pp. 181-197. ACM PDF
[Rose91] Rosenblum, M., and Ousterhout, J.K., "The Design and Implementation of a Log-Structured File System," ACM Transactions on Computer Systems, Vol. 10, No. 1 (February 1992), pp. 26-52. ACM PDF
[Kron86] Kronenberg, N.P., Levy, H.M., and Strecker, W.D., "VAXclusters: A Closely-Coupled Distributed System" ACM Transactions on Computer Systems Vol. 4, No. 2 (May 1986), pp. 130-146. ACM PDF
[Ritc74] Ritchie, D.M., and Thompson, K., "The UNIX Time-Sharing System." Communications of the ACM, Vol. 17, No. 7, July 1974, pp. 365-375. ACM PDF
[Klei86] Kleiman, S.R., "Vnodes: An Architecture for Multiple File System Types in Sun UNIX," Proceedings of the Summer Usenix Conference, Atlanta, GA, 1986. pp. 238-247. CiteSeer PDF
[Rose90] Rosenthal, D., "Evolving the Vnode Interface," Proceedings of the Summer Usenix Conference, Anaheim, CA, June 1990, pp. 107-117. CiteSeer PDF
[Hagm87] Hagmann, R., "Reimplementing the Cedar File System Using Logging and Group Commit," Proceedings of the 11th Symposium on Operating Systems Principles, Operating System Review, Vol. 21, No. 5, Nov. 1987, pp. 115-162. ACM PDF
[Sand85] Russel Sandberg and David Goldberg and Steve Kleiman and Dan Walsh and Bob Lyon, "Design and Implementation of the Sun Network Filesystem," Proc. Summer 1985 USENIX Conf. CiteSeer PDF
[Patt88] Patterson, D., Gibson, G. and Katz, R., `A Case for Redundant Arrays of Inexpensive Disks (RAID)', Proc. of 1988 ACM SIGMOD Conf. on Management of Data, Chicago, IL, June 1988. ACM PDF
[Ganger95] G. Ganger, Y. Patt, "Soft Updates: A Solution to the Metadata Update Problem in File Systems", Technical Report CSE-TR-254-95, University of Michigan, Ann Arbor, August 1995. ACM PDF

Transactions and Reliability
[Verh78] Verhofstad, J.S.M., "Recovery Techniques for Database Systems," Computing Surveys, Vol. 10, No. 2 (June 1978), pp. 167-195. ACM PDF
[Gray81] Gray, J., "The Transaction Concept: Virtues and Limitations," Proc. 7th International Conference on Very Large Data Bases, September 1981, pp. 144-154. CS 240 PDF
[Ston81] Stonebraker, M., "Operating System Support for Database Management," Communications of the ACM, Vol. 24, No. 7 (July 1981), pp. 412-418. ACM PDF
[Borg83] Borg, A., Blau, W., Graetsch, W., Herrmann, F., and Oberle, W., "Fault Tolerance Under UNIX," ACM Transactions on Computer Systems, Vol. 7, No. 1 (February 1989), pp. 1-24. ACM PDF
[Bart81] Bartlett, J., "A NonStop Kernel", Proceedings of the 8th SOSP, Operating Systems Review, Vol. 11, No. 5, November 1977, pp.23-31. ACM PDF
[Ston81] Stonebraker, M., DuBourdieux, D., Edwards, W., "Problems in Supporting Data Base Transactions in an Operating System Transaction Manager," Operating Systems Review, vol. 19, no. 1, January 1985, pp. 6-14. ACM PDF
[Hask88] Haskin, R., Malachi, Y., Sawdon, W., and Chan, G., "Recovery Management in QuickSilver." ACM Trans. on Computer Systems 6(1), February 1988, pp. 82-108. ACM PDF
[Chen96] Chen, P.M, Ng, W.T., Chandra, S., Aycock,C., Rajamani,G. Lowell,D., "The Rio File Cache: Surviving Operating System Crashes", Proceedings of the 1996 International Conference on Architectural Support for Programming Languages and Operating Systems, October 1996. ACM PDF
[Gray89] C. Gray and D. Cheriton, "Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Consistency." Proceedings of the 12th SOSP, December 1989 ACM PDF

Protection and Security
[Wulf74] Wulf, W. et al, "HYDRA: The Kernel of a Multiprocessor Operating System," Communications of the ACM, Vol. 17, No. 6 (June 1974), pp. 337-345. ACM PDF
[Salt75] Saltzer, Jerome H., "The Protection of Information in Computer Systems," Proceedings of the IEEE, Vol. 63, No. 9 (September 1975), pp. 1278-1308. IEEE PDF Author HTML
[Denn79] Denning, D.E. and Denning, P.J., "Data Security," Computing Surveys, Vol. 11, No. 3 (September 1979), pp. 227-249. ACM PDF
[Need78] Needham, R.M. and Schroeder, M.D., "Using Encryption for Authentication in Large Networks of Computers," Communications of the ACM, Vol. 21, No. 12 (December 1978), pp. 993-999. ACM PDF
[Burr90] Burrows, M., Abadi, M., and Needham, R., "A Logic of Authentication," ACM Transactions on Computer Systems, Vol. 8, No. 1 (February 1990), pp. 18-36. ACM PDF
[Lamp91] Lampson, B., Abadi, M., Burrows, M., and Wobber, E., "Authentication in Distributed Systems: Theory and Practice," Proceedings of the Thirteenth ACM Symposium on Operating Systems Principles, Operating Systems Review, Vol. 25, No. 5, Pacific Grove, California, October 1991, pp. 165-182. ACM PDF
[Morr79] Morris, R., and Thompson, K., "Password Security: A Case History," Communications of the ACM, Vol. 22, No. 11, November 1979, pp. 594-597. ACM PDF
[Lamp73] Butler W. Lampson, "A Note on the Confinement Problem," Communications of the ACM, Vol. 16, No. 10, October 1973, pp.613-615. ACM PDF
[Thom84] Thompson, K., "Reflections on Trusting Trust," Communication of the ACM, Vol. 27, No. 8, August 1984, pp. 761-763. ACM PDF
[Ande94] Anderson, R.J., "Why Cryptosystems Fail," Communications of the ACM, Vol. 37, No. 11, November 1994. ACM PDF
[Eng00] Dawson Engler, Benjamin Chelf, Andy Chou, and Seth Hallem. "Checking System Rules Using System-Specific, Programmer-Written Compiler Extensions." In Proceedings of the Fourth Symposium on Operating Systems Design and Implementation, San Diego, CA, October 2000 Usenix PDF

Multiprocessors
[Cart91] Carter, J.B., Bennett, J.K., and Zwaenepoel, W.. "Implementation and Performance of Munin," Proceedings of the 13th ACM Symposium on Operating Systems Principles, October 1991, pp. 152-164. ACM PDF
[And92] Anderson, T., Bershad, B., Lazowska, E., and Levy, H.. "Scheduler Activations: Effective Kernel Support for the User-Level Management of Parallelism," ACM Transactions on Computer Systems, Vol. 10, No. 1 (February 1992), pp. 53-79. ACM PDF
[Bugn97] E. Bugnion, S. Devine, and M. Rosenblum. "Disco: Running Commodity Operating Systems on Scalable Multiprocessor." In SOSP 16, October 1997. ACM PDF

Miscellaneous
[Sher72] Sherman, S.W., Baskett, F., and Browne, J.C., "Trace-Driven Modeling and Analysis of CPU Scheduling in a Multiprogramming System," Communications of the ACM, Vol. 15, No. 12 (December 1972). ACM PDF
[Gold74] Goldberg, R.P., "Survey of Virtual Machine Research," Computer, Vol. 7, No. 6 (June 1974), pp. 34-45. CiteSeer PDF
[Lamp83] Lampson, B.W., "Hints for Computer System Design," Proceedings of the 9th Symposium on Operating Systems Principles, October 1983, pp. 33-48. ACM PDF
[Bour78] Bourne, S. R., "The Unix Time-Sharing System: The Unix Shell.", Bell System Technical Journal, Vol. 57, No. 6, July-August 1978, pp. 1971-1990. TBD TBD
[Hoar81] Hoare, C.A.R., "The Emperor's Old Clothes", Communications of the ACM, Vol. 24, No. 2, February 1981, pp. 75-83. ACM PDF
[Laue81] Lauer, H.C., "Observations on the Development of an Operating System.", Proceedings of the 8th SOSP, Operating Systems Review, Vol. 15, No. 5, December 1981, pp. 30-36. ACM PDF
[Salt84] J. H. Saltzer, D.P. Reed and D. D. Clark, "End-to-End Arguments in System Design, " ACM Transactions on Computer Systems, vol. 2, no. 4, November 1984, pp. 277-288. ACM PDF

Specific operating systems
[Corb72] Corbato, F.J., Saltzer, J.H., and Clingen, C.T., "Multics - The first seven years", Proc. Spring Joint Computer Conference, AFIPS, May 1972, pp. 571-583. Author HTML
[Ausl81] Auslander, M.A., Larkin, D.C., and Scherr, A. L., "The Evolution of the MVS Operating System," IBM Journal of Research and Development, Vol. 25, No. 5, September 1981, pp. 471-482. IBM PDF
[Seaw79] Seawright, L.H., and MacKinnon, R.A., "VM/370: A study of multiplicity and usefulness", IBM Systems Journal Vol 18, No 1. 1979, pp. 4-17. IBM PDF
[Cust82] Custer, H., Inside Windows NT, Microsoft Press, 1992. CiteSeer books24x7

One of the best ways to understand operating systems concepts is to look at specific operating systems such as: UNIX [Ritc78], V[Cher88], Mach[Youn87], Multics[Corb72], OS/360 and MVS[Ausl81], Tandem NonStop[Bart81], VM/370[Seaw79], and Windows NT[Cust92].

No comments: