Reading List for CS 331

      CS 331 Page

Questions for MapReduce, DryadLINQ:

1. Discuss how Map-Reduce systems handle node failures.
2. What are the advantages of DyadLINQ over MapReduce?

Questions for GFS:

1. Comparing with AFS, which system offers more reliability, AFS or GFS?

Questions for AFS:

1. Under what type of file access patterns, will AFS offer better performance than NFS?

Questions for NFS:

1. Briefly explain how caching is used to improve the performance of NFS.
2. What is a file handle in NFS?

Questions for RPC and LFS:

1. What does the binding process accomplish in RPC?
2. Why does LFS have worse read performance than FFS?

Questions for FFS and LFS:

1. What are the pros and cons of using large blocks.
2. Why does LFS have better write performance than FFS?

Questions for Disco :

1. Briefly explain the difference between `physical address' and `machine address' in Disco. Which of them is used in Disco system's TLB?

Questions for Resource Container and Lottery Scheduling:

1. Briefly explain the difference among `protection domain', `resource principal', and `execution/scheduling unit'.
2. Suppose we need to schedule applications with the same priority but different numbers of threads. What is the resource-container's solution to achieve fairness among these applications? What is the solution under lottery scheduling?

Questions for Scheduler Activation:

1. Compare user-level thread and kernel-level thread: name two advantages of user-level thread over kernel-level thread and two advantages of kernel-level thread over user-level thread.

Questions for Monitors:

1. Name one difference between the design of Hoare-Monitor and Mesa-Monitor.

Questions for Unix:

1. Give two examples of UNIX design that help the perfromance of disk file access.

Questions for Multics:

1. The virtual memory system of Multics used both segmentation and paging. What is the difference between a segment and a page?
2. When two processes share a segment, does that segment have the same segment-ID in the two processes?

Questions for Nucleus:


1. List three differences between the design concepts of THE and Nucleus.

Questions for THE:


1. Why did the designers enforce a strict, layered hierarchical structure for THE?
2. What type(s) of machine resources does the segment-controller manage in THE?




The paper list below may be out of date. Please refer to the papers on the class schedule.

• The Structure of the "THE" Multiprogramming System
  Edsger W. Dijkstra.
  Communications of the ACM 11(5), May 1968.


• The Nucleus of a Multiprogramming System
  Per Brinch Hansen
  Communications of the ACM 13(4), April 1970


• 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 UNIX Time-Sharing System
  Dennis M. Ritchie and Ken Thompson.
  Communications of the ACM 17(7), July 1974.


• Monitors: An Operating System Structuring Concept
  C.A.R. Hoare
  Communications of the ACM 17, 10, October 1974, pp. 549-557


• Experiences with Processes and Monitors in Mesa
  Butler W. Lampson, David D. Redell
  Communications of the ACM, 23 2, February 1980, pp. 105-117.


• TxLinux: Using and Managing Transactional Memory in an Operating System
  Christopher J. Rossbach, Owen S. Hofmann, Donald E. Porter, Hany E. Ramadan, Aditya Bhandari, Emmett Witchel
  Proceedings of the 21th ACM Symposium on Operating Systems Principles (SOSP '07), October 2007.


• (Optional/for-fun) lightweight robust futexes


• (Optional/for-fun) What really happened on Mars ?


• Eraser: A Dynamic Data Race Detector for Multithreaded Programs
  Stefan Savage, Michael Burrows, Greg Nelson, Patrick Sobalvarro, and Thomas Anderson
  Proceedings of the Sixteenth ACM Symposium on Operating Systems Principles (SOSP '97), October 1997.


• Deadlock Immunity: Enabling Systems To Defend Against Deadlocks
  Horatiu Jula, Daniel Tralamazza, Cristian Zamfir, George Candea
  Proceedings of the 8th USENIX Symposium on Operating Systems Design and Implementation (OSDI '08), December 2008.


• Finding and Reproducing Heisenbugs in Concurrent Programs
  Madan Musuvathi, Shaz Qadeer, Tom Ball, Gerard Basler, Piramanayagam Arumuga Nainar and Iulian Neamtiu
  Proceedings of the 8th USENIX Symposium on Operating Systems Design and Implementation (OSDI '08), December 2008.


• Scheduler Activations: Effective Kernel Support for the User-Level Management of Parallelism
  Thomas E. Anderson, Brian N. Bershad, Edward D. Lazowska, and Henry M. Levy
  Symposium on Operating Systems Principles (SOSP '91)


• Lottery Scheduling: Flexible Proportional-Share Resource Mangement
  Carl A. Waldspurger and William E. Weihl
  Proceedings of the First Symposium on Operating Systems Design and Implementation (OSDI '94), Monterey CA, November 1994, pp. 1-11.


• Resource Containers: A New Facility for Resource Management in Server Systems
  Gaurav Banga, Peter Druschel, and Jeffrey Mogul
  Proceedings of the Third Symposium on Operating System Design and Implementation (OSDI '99), New Orleans, LA, February, 1999, 45-58.


• Exterminate All Operating System Abstractions
  Dawson Engler and M. Frans Kaashoek
  Fifth Workshop on Hot Topics in Operating Systems (HotOS-V), Orcas Island, Washington, May, 1995


• Exokernel: An Operating System Architecture for Application-level Resource Management
  Dawson R. Engler, M. Frans Kaashoek, and James O'Toole Jr.
  In the Proceedings of the 15th ACM Symposium on Operating Systems Principles (SOSP '95), Copper Mountain Resort, Colorado, December 1995, pages 251-266.


• Application performance and flexibility on exokernel systems
  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
  In the Proceedings of the 16th ACM Symposium on Operating Systems Principles (SOSP '97)


• Memory Resource Management in VMWare ESX Server
  Carl A. Waldspurger
  Proceedings of the Fifth Symposium on Operating Systems Design and Implementation (OSDI '02)


• Disco: Running Commodity Operating Systems on Scalable Multiprocessors
  Edouard Bugnion, Scott Devine, Mendel Rosenblum.
  Proceedings of The Sixteenth Symposium on Operating Systems Principles (SOSP '97)


• Xen and the Art of Virtualization
  Paul Barham, Boris Dragovic, Keir Fraser, Steven Hand, Tim Harris, Alex Ho, Rolf Neugebauer, Ian Pratt, and Andrew Warfield.
  Proc. of the 19th ACM Symp. on Operating Systems Principles (SOSP '03), October 2003.


• Pilot: An Operating System for a Personal Computer
  David D. Redell, Yogen K. Dalal, Thomas R. Horsley, Hugh C. Lauer, William C. Lynch, Paul R. McJones, Hal G. Murray, and Stephen C. Purcell.
  Communications of the ACM 23(2), February 1980, pp. 81-92.


• A Fast File System for UNIX
  McKusick, M.K., Joy, W.N., Leffler, S.J., and Fabry, R.S.
  ACM Transactions on Computer Systems, Vol. 2, No. 3, August 1984, pp. 181-197.


• Implementing Remote Procedure Calls
  Andrew D. Birrell and Bruce Jay Nelson
  ACM Trans. on Computer Systems 2(1), February 1984, pp. 39-59.


• Design and Implementation of the Sun Network Filesystem
  Sandberg, R., Goldberg, D., Kleiman, S., Walsh, D., and Lyon, B.
  Proceedings of the Summer 1985 USENIX Conference, Portland OR, June 1985, pp. 119-130.
  For current NSF info, read Sun NFS details


• Scale and Performance in a Distributed File System
  John H. Howard, Michael L. Kazar, Sherri G. Menees, David A. Nichols, M. Satyanarayanan, Robert N. Sidebotham, and Michael J. West
  ACM Transactions on Computer Systems, Vol. 6, No. 1, February 1988, pp. 51-81


• A Case for Redundant Arrays of Inexpensive Disks (RAID)
  David A. Patterson, Garth Gibson, and Randy H. Katz
  Proceedings of the 1988 ACM SIGMOD Conference on Management of Data, Chicago IL, June 1988.


• The Byzantine Generals Problem
  Leslie Lamport, Robert Shostak, and Marshall Pease
  ACM Transactions on Programming Languages and Systems, July 1982, pages 382-401.


• ARIANE 5 Flight 501 Failure: Report by the Inquiry Board
  Jacques-Louis Lions, Lennart Lebeck, Jean-Luc Fauquembergue, Gilles Kahn, Wolfgang Kubbat, Stefan Levedag, Leonardo Mazzini, Didier Merle Thomson, Colin O'Halloran
  European Space Agency Report, Paris, July 1996.


• An Investigation of the Therac-25 Accidents
  Nancy Leveson and Clark S. Turner
  IEEE Computer, Vol. 26, No. 7, July 1993, pp. 18-41.


• Smashing The Stack For Fun And Profit
  Aleph One
  Phrack #49, November 1996.


• Fixing Races for Fun and Profit: How to use access(2)
  Drew Dean and Alan J. Hu
  Proceedings of the 13th conference on USENIX Security Symposium (Security '04), August 2004.


• Fixing Races for Fun and Profit: How to abuse atime
  Chris Karlof, Naveen Sastry, and David Wagner
  Proceedings of the 14th conference on USENIX Security Symposium (Security '05), August 2005.


• KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs
  Cristian Cadar, Daniel Dunbar, and Dawson Engler
  Proceedings of the 8th USENIX Symposium on Operating Systems Design and Implementation (OSDI '08), December 2008.


• Rx: Treating bugs as allergies---a safe method to survive software failure
  Feng Qin, Joe Tucek, Jagadeesan Sundaresan and Yuanyuan Zhou
  Proceedings of the 20th ACM Symposium on Operating Systems Principles (SOSP '05), October 2005.


• Flight Data Recorder: Monitoring Persistent-State Interactions to Improve Systems Management
  Chad Verbowski, Emre Kıcıman, Arunvijay Kumar, and Brad Daniels, Shan Lu, Juhan Lee, Yi-Min Wang, and Roussi Roussev
  Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation (OSDI '06), November 2006.


• Automatic Misconfiguration Troubleshooting with PeerPressure
  Helen J. Wang, John C. Platt, Yu Chen, Ruyun Zhang, and Yi-Min Wang
  Proceedings of the 6th USENIX Symposium on Operating Systems Design and Implementation (OSDI '04), December 2004.


• Safe Kernel Extensions Without Run-Time Checking
  George C. Necula and Peter Lee
  Proceedings of the Second USENIX Symposium on Operating Systems Design and Implementation (OSDI '96), October 1996.


• Bugs as deviant behavior: a general approach to inferring errors in systems code
  Dawson Engler, David Yu Chen, Seth Hallem, Andy Chou, and Benjamin Chelf
  Proceedings of the 18th ACM Symposium on Operating Systems Principles (SOSP '01), pages 57--72, Banff, Alberta, Canada, October 21--24, 2001.


• An empirical study of operating systems errors
  Andy Chou, Junfeng Yang, Benjamin Chelf, Seth Hallem, and Dawson Engler
  In Proceedings of the 18th ACM Symposium on Operating Systems Principles (SOSP '01), pages 73--88, October 2001.


• Checking System Rules Using System Specific, Programmer-Written Compiler Extensions
  Dawson Engler, Benjamin Chelf, Andy Chou, and Seth Hallem
  Proceedings of the Fourth Symposium on Operating Systems Design and Implementation (OSDI '00), San Diego, CA, October 2000.


• Kerberos: An Authentication Service for Open Network Systems
  J. G. Steiner, C. Neuman, J. I. Schiller
  USENIX '88, Dallas, TX, February 1988, pp. 191-202.
  Kerberos in Four Acts
  Kerberos Book