OPERATING SYSTEMS IICOMS E6118, Dept of Computer Science, Columbia University
General Info | Presentations/Reviews | Projects | Grades | Discussion | OS Resources

OPERATING SYSTEMS READING LIST
This course is based on the following collection of journal and conference papers that describe the history and state of the art in operating systems. Students are expected to read papers before the class in which they are presented and contribute to the class discussions. Papers which are not available online will be handed out in class. The papers are organized into three categories: (1) general reading papers which should be read on your own, (2) presentation papers which will be presented in class, and (3) reference papers, which are optional reading that you may find helpful for some of the presentation papers.

General Reading

  1. Bentley, Jon, "The Back of the Envelope," Communications of the ACM, Vol. 27, No. 3, March 1984, pp. 180-184.
  2. Bentley, Jon, "The Envelope is Back," Communications of the ACM, Vol. 29, No. 3, March 1986, pp. 176-182.
  3. Brooks, Frederick, "No Silver Bullet--Essence and Accidents of Software Engineering," IEEE Computer, Vol. 20, No. 7, April 1987, pp. 10-19.
  4. Levin, R. and Redell, D., "An Evaluation of the Ninth SOSP Submissions," Operating Systems Review, Vol. 17, No. 3, July 1983, pp. 35-40.
  5. Smith, Alan Jay, "The Task of the Referee," IEEE Computer, Vol. 23, No. 4, April 1990, pp. 65-71.
Presentation Papers
  1. 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.
  2. 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.
  3. Birrell, A.D. and Nelson, B.J., "Implementing Remote Procedure Calls," ACM Transactions on Computer Systems, Vol. 2, No. 1, February, 1984, pp. 39-59.
  4. Bugnion, E., Devine, S., and Rosenblum, M., "Disco: Running Commodity Operating Systems on Scalable Multiprocessors", Proceedings of the 16th ACM Symposium on Operating Systems Principles, Operating Systems Review, Vol. 31, No. 5, December 1997, pp. 143-156.
  5. Lowell, D., Chen, P., "Free Transactions with RioVista," The Proceedings of the Sixteenth ACM Symposium on Operating Systems Principles, Saint-Malo, France, October 1997, pp. 92-101.
  6. Corbató, F., Merwin-Daggett, F., and Daley, R. "An Experimental Time-Sharing System," AFIPS Conference Proceedings, 1962 Spring Joint Computer Conference, pp. 335-344.
  7. 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.
  8. Dijkstra, Edsger W., "The Structure of the `THE' Multiprogramming System," Communications of the ACM, Vol. 11, No. 5, May 1968, pp. 341-346.
  9. Ford, B., Back, G., Benson, G., Lepreau, J., Lin, A., Shivers, O., "The Flux OSKit: A Substrate for Kernel and Language Research," Proceedings of the Sixteenth ACM Symposium on Operating System Principles, St. Malo, France, October 1997, 38-51.
  10. Kaashoek, M. F., Engler, D., Ganger, G., Briceño, H., Hunt, R., Mazières, D., Pinckney, T., Grimm, R., Jannotti, J., and Mackenzie, K., "Application Performance and Flexibility on Exokernel Systems," The Proceedings of the Sixteenth ACM Symposium on Operating Systems Principles, Saint-Malo, France, October 1997, pp. 52-65.
  11. Lampson, B. W. and Redell, D. D., "Experiences with Processes and Monitors in Mesa", Communications of the ACM, Vol. 23, No. 2, February 1980, pp. 105-117.
  12. 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.
  13. McVoy, L., Staelin, C., "Lmbench: Portable Tools for Performance Analysis," Proceedings of the 1996 USENIX Technical Conference, San Diego, CA, January 1996, 279-295.
  14. Nieh, J. and Lam, M. S., "The Design, Implementation and Evaluation of SMART: A Scheduler for Multimedia Applications" Proceedings of the Sixteenth ACM Symposium on Operating Systems Principles, Saint-Malo, France, October 1997.
  15. Ousterhout, John K., Cherenson, Andrew R., Douglis, Frederick, Nelson, Michael N., and Welch, Brent B., "The Sprite Network Operating System," IEEE Computer, 21(2), February, 1988.
  16. Patterson, D., Gibson, G., and Katz, R., "A Case for Redundant Arrays of Inexpensive Disks (RAID)," Proceedings of the 1988 ACM SIGMOD Conference on Management of Data, Chicago IL, June 1988, 109-116
  17. Pike, R., Presotto, D., Dorward, S., Flandrena, B., Thompson, K., Trickey, H., and Winterbottom, P., "Plan 9 from Bell Labs," Computing Systems, 8(3), Summer 1995.
  18. Ritchie, D. M. and Thompson, K., "The UNIX Time-Sharing System", Communications of the ACM, Vol. 17, No. 7, July 1974, pp. 365-375.
  19. Rosenblum, M. and Ousterhout, J., "The Design and Implementation of a Log-Structured File System," ACM Transactions on Computer Systems, Vol. 10, No. 1, February 1992, pp. 26-52.
  20. Saltzer, J.H., Reed, D.P., and Clark, D.D., "End-To-End Arguments in System Design," ACM Transactions on Computer Systems, Vol. 2, No. 4, November 1984, pp. 277-288.
  21. Sandberg, R., Goldberg, D., Kleiman, S., Walsh, D., and Lyon, B., "Design and Implementation of the Sun Network Filesystem," Proceedings of the Summer 1985 USENIX Conference, Portland OR, June 1985, pp. 119-130.
  22. Satyanarayanan, M., Kistler, J.J., Kumar, P., Okasaki, M.E., Siegel, E.H., and Steere, D.C., "Coda: A Highly Available File System for a Distributed Workstation Environment," IEEE Transactions on Computers, Vol. 39, No. 4, April 1990.
  23. Schroeder, M. D., Birrell, A.D., and Needham, R. M., "Experience with Grapevine: The Growth of a Distributed System," ACM Transactions on Computer Systems, Vol. 2, No. 1, February 1984, pp. 3-23.
  24. Waldspurger, C.A. and Weihl, W.E., "Lottery Scheduling: Flexible Proportional-Share Resource Mangement," Proceedings of the First Symposium on Operating Systems Design and Implementation, Monterey CA, November 1994, pp. 1-11.
  25. Wilkes, J., Golding, R., Staelin, C., and Sullivan, T., "The HP AutoRAID Hierarchical Storage System," Proceedings of the Fifteenth Symposium on Operating Systems Principles, Copper Mountain, CO, December 1995, pp. 96-108.
  26. Wulf, W., Cohen, E., Corwin, W., Jones, A., Levin, R., Pierson, C., and Pollack, F. "HYDRA: The Kernel of a Multiprocessor Operating System," Communications of the ACM, 17(6), June 1974.
Reference Papers
  1. Anderson, T. E., Dahlin, M. D., Neefe, J. M., Patterson, D. A., Roselli, D.S., and Wang, R.Y., "Serverless Network File Systems," Proceedings of the Fifteenth Symposium on Operating Systems Principles, Copper Mountain, CO, December 1995, pp. 109-126.
  2. Baker, M., Hartman, J., Kupfer, M., Shirriff, K., and Ousterhout, J., "Measurements of a Distributed File System," Proceedings of the Thirteenth Symposium on Operating System Principles, Pacific Grove CA, October 1991, pp. 198-212.
  3. Banga, G., Druschel, P,. Mogul, J., "Resource Containers: A New Facility for Resource Management in Server Systems," Proceedings of the Third Symposium on Operating System Design and Implementation (OSDI-III), New Orleans, LA, February, 1999, 45-58.
  4. Bershad, B. N., "Practical Considerations for Non-Blocking Concurrent Objects", Proceedings of the 13th International Conference on Distributed Computing Systems, Pittsburgh, PA, May 1993, pp. 264-273.
  5. Bershad, B. N., Savage S., Pardyak, P., Sirer, E. G., Fiuczynski, M., Becker, D., Chambers, C., and Eggers, S., "Extensibility: Safety and Performance in the SPIN Operating System", Proceedings of the 15th ACM Symposium on Operating Systems Principles, Operating Systems Review, Vol. 29, No. 5, December 1995, pp. 267-284.
  6. 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.
  7. Brown, Aaron, Seltzer, Margo, "Operating System Benchmarking in the Wake of Lmbench: A Case Study of the Performance of NetBSD on the Intel x86 Architecture," Proceedings of the 1997 Sigmetrics Conference, Seattle, WA, June 1997, 214-224.
  8. Cao, P., Felton, E., Li, K., "Implementation and Performance of Application-Controlled File Caching," Proceedings of the First Symposium on Operating System Design and Implementation, Monterey, CA, November 1994, pp. 165-177.
  9. Chang, F., Gibson, G., "Automatic I/O Hint Generation through Speculative Execution," Proceedings of the Third Symposium on Operating System Design and Implementation (OSDI III), New Orleans, LA, February 1999, 1-14.
  10. Denning, D. E., amd Denning, P. J., "Data Security", Computing Surveys, Vol. 11, No. 3, September 1979, pp. 227-249.
  11. Ferrari, Domenico, "Considerations on the Insularity of Performance Evaluation," IEEE Transactions on Software Engineering, Vol. 12, No. 6, June 1986, pp. 678-683.
  12. Fotheringham, John, "Dynamic Storage Allocation in the Atlas Computer, Including an Automatic Use of a Backing Store," Communications of the ACM, Vol. 4, No. 10, October 1961, pp. 435-436.
  13. Goyal, Pawan, Guo, Xingang, and Vin, Harrick M., "A Hierarchical CPU Scheduler for Multimedia Operating Systems," Proceedings of the Second USENIX Symposium on Operating Systems Design and Implementation, Seattle, Washington, October 1996.
  14. Hagmann, Robert, "Reimplementing the Cedar File System Using Logging and Group Commit," Proceedings of the Eleventh Symposium on Operating Systems Principles, Austin TX, November 1987, pp. 155-162.
  15. Härtig, H., Hohmuth, M., Liedtke, J., Schönberg, S., and Wolter, J., "The Performance of m-Kernel-Based Systems," The Proceedings of the Sixteenth ACM Symposium on Operating Systems Principles, Saint-Malo, France, October 1997, pp. 66-77.
  16. Harty, K. and Cheriton, D. R., "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.
  17. Haskin, R., Malachi, Y., Sawdon, W., and Chan, G., "Recovery Management in QuickSilver," ACM Transactions of Computer Systems, Vol. 6, No. 1, February 1988, pp. 82-108.
  18. Hoare, C. A. R., "The Emperor's Old Clothes", Communications of the ACM, Vol. 24, No. 2, February 1981, pp. 75-83.
  19. Morris, J.H., Satyanarayanan, M., Conner, M.H., Howard, J.H., Rosenthal, D.S.H., and Smith, F.D., "ANDREW: A Distributed Personal Computing Environment," Communications of the ACM, Vol. 29, No. 3, March 1986, pp. 184-201.
    20. .
  20. Hutchinson, N., Peterson, L., Abbott, M., and O'Malley, S., "RPC in the x-Kernel: Evaluating New Design Techniques," Proceedings of the Twelfth Symposium on Operating Systems Principles, Litchfield Park, AZ, December 1989, pp. 91-101.
  21. Kilburn, T., Edwards, D.B.G., Lanigan, M.J., and Sumner, F.H., "One Level Storage System," IRE Transactions on Electronic Computers, Vol. 12, No. 2, April 1962, pp. 223-235.
  22. Kimbrel, T., Tomkins, A., Patterson, R., Bershad, B., Cao, P., Felten, E, Gibson, G., Karlin, A., Li, K., "A Trace-Driven Comparison of Algorithms for Parallel Prefetching and Caching," Proceedings of the Second Symposium on Operating Systems Design and Implementation, Seattle, WA, October1996, pp. 19-34.
  23. Lampson, Butler, "Hints for Computer System Design," Proceedings of the Ninth Symposium on Operating Systems Principles, Bretton Woods NH, October 1983, pp. 33-48.
  24. Lampson, B. W., "A Note on the Confinement Problem", Communications of the ACM, Vol. 16, No. 10, October 1973, pp. 613-615.
  25. Lauer, Hugh, "Observations on the Development of an Operating System," Proceedings of the Eighth Symposium on Operating Systems Principles, Pacific Grove CA, December 1981, pp. 30-36.
  26. Lauer, H. C. and Needham, R. M., "On the Duality of Operating System Structures", Proceedings of the Second International Symposium on Operating Systems, reprinted in Operating Systems Review, Vol. 13, No. 2, April 1979, pp. 3-19.
  27. Levy, H. and Lipman, P., "Virtual Memory Management in the VAX/VMS Operating System," IEEE Computer, Vol. 15, No. 3, March 1982, pp. 35-41.
  28. Mowry, T., Demke, A., Krieger, O., "Automatic Compiler-Inserted I/O Prefetching for Out-of-Core Applications," Proceedings of the Second Symposium on Operating System Design and Implementation, Seattle, WA, October 1996, pp. 3-17.
  29. Necula, G., Lee, P., "Safe Kernel Extensions Without Run-Time Checking," Proceedings of the Second Symposium on Operating System Design and Implementation, Seattle, WA, October 1996, pp. 229-243.
  30. 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.
  31. Ousterhout, J., Da Costa, H., Harrison, D., Kunze, J., Kupfer, M., and Thompson, J., "A Trace-Driven Analysis of the UNIX 4.2 BSD File System," Proceedings of the Tenth Symposium on Operating Systems Principles, Orcas Island WA, December 1985, pp. 15-24.
  32. Pai, V., Druschel, P., Zwaenepoel, "IO-Lite: A Unified I/O Buffering and Caching System," Proceedings of the Third Symposium on Operating System Design and Implementation (OSDI-III), New Orleans, LA, February 1999, 15-28.
  33. Patterson, R. H., Gibson, G. A., Ginting, E., Stodolsky, D., and Zelenka, J., "Informed Prefetching and Caching," Proceedings of the Fifteenth Symposium on Operating Systems Principles, Copper Mountain, CO, December 1995, pp. 79-95.
  34. Rashid, Rick F., "From RIG to Accent to Mach: The Evolution of a Network Operating System," Proceedings of the 1986 Fall Joint Computer Conference, pp. 1128-1137.
  35. Rashid, R., Tevanian, A., Young, M., Golub, D., Baron, R., Black, D., Bolosky, W., and Chew, J., "Machine-Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures," Proceedings of the Second International Conference on Architectural Support for Programming Languages and Operating Systems, Palo Alto CA, October 1987, pp. 31-39.
  36. Saltzer, J.H. and Gintell, J.W., "The Instrumentation of Multics," Communications of the ACM, Vol. 13, No. 8, August 1970, pp. 495-500.
  37. Shoch, J. F. and Hupp, J. A., "The `Worm' Programs--Early Experience with a Distributed Computation," Communications of the ACM, Vol. 25, No. 3, March 1982, pp. 172-180.
  38. Stonebraker, Michael, "Operating System Support for Database Management," Communications of the ACM, Vol. 24, No. 7, July 1981, pp. 412-418.
  39. Sweeney, A., Doucette, D., Hu, W., Anderson, C., Nishimoto, M., and Peck, G., "Scalability in the XFS File System," Proceedings of the Summer Usenix Conference, San Diego, CA, June 1996.
  40. Talluri, M., Hill M. D., and Y. A. Khalidi, "A New Page table for 64-bit Address Spaces", Proceedings of the 15th ACM Symposium on Operating Systems Principles, Operating Systems Review, Vol. 29, No. 5, December 1995, pp. 184-200.
  41. Thekkath, C., Mann, T., and Lee, E., "Frangipani: A Scalable Distributed File System," Proceedings of the Sixteenth ACM Symposium on Operating Systems Principles, Saint-Malo, France, October 1997, pp. 224-237.
  42. Vogels, W., "File System Usage in Windows NT 4.0", Proceedings of the 17th ACM Symposium on Operating Systems Principles, Operating Systems Review, Vol. 34, No. 5, December 1999, pp. 93-109.
  43. Wallach, D. S., Balfanz, D., Dean, D., and Felten, E. W., "Extensible Security Architecture for Java," Proceedings of the 16th ACM Symposium on Operating Systems Principles, Operating Systems Review, Vol. 31, No. 5, December 1997, pp. 116-128.

Jason Nieh, nieh@cs.columbia.edu