CSC 2227S: Topics in the Design and Implementation of Operating Systems
Papers
For each meeting, readings are assigned. Usually, the readings
will consist of two or three computer systems papers.
The papers selected for this course are either classic papers or papers from
recent top conferences.
You are
expected to read these papers thoroughly and summarize them
BEFORE
arriving at class on Wednesdays.
Each paper will be briefly presented by a student in the class, who will also
lead the discussion of that paper.
For each class meeting, we identify the topic and papers below; for
each, we also try to identify good sources for background reading and
for further investigation.
Electronic versions are linked where available (access will be denied
for IP addresses outside of UofT). When electronic versions are not available,
paper copies will be provided in class at least a week in advance.
(NOTE: This schedule is not set in stone. Some changes may be made to this
schedule during the term)
Week 1 - January 11: Welcome to CSC 2227
This first meeting will be largely organizational in nature. In it,
we will discuss how the class is going to work and what will be
covered. In addition, we will very rapidly recap stuff you should
already know, discussing what defines operating systems and
distributed systems and what makes them continue to be interesting
after all these years, and overviewing how the various topics in the
course fit together.
There are no readings for this week, but the following items are
intended to help you refresh your memory of operating systems. These are to help you prepare for the course and assess
your own knowledge of the pre-requisite material. Sample
solutions to the OS exam questions will be posted next week.
Week 2 - Early Systems
presented by Angela Demke Brown
Jan. 18
Read and provide summaries for the following papers:
- 1. The Structure of the "THE"-Multiprogramming System
Edsger. W. Dijkstra, Communications of the ACM, vol. 11, no. 5, May 1968, pp. 341-346.
- 2. The Nucleus of a Multiprogramming System
Per Brinch Hansen, Communications of the ACM,
vol. 13, no. 4, April 1970, pp. 238-241,250.
- 3. HYDRA: The Kernel of a Multiprocessor Operating System
W. Wulf, E. Cohen, W. Corwin, A. Jones, R.Levin, C. Pierson, F. Pollack, Communications of the ACM, vol. 17, no. 6, June 1974, pp. 337-345.
Additional suggested reading (to be added)
Week 3
Jan. 25 - No class.
Week 4
Feb. 1
Read and provide summaries for the following papers:
- 4. The Performance of Micro-kernel-based Systems
Hermann Härtig, Michael Hohmuth, Jochen Liedtke, Sebastian Schönberg, Jean Wolter,
in Proc. of the 16th ACM Symposium on Operating Systems Principles, Oct. 1997, pp. 66-77.
presentation by Eric LaForest
- 5. Application performance and flexibility on exokernel systems
M. Frans Kaashoek, Dawson R. Engler, Gregory R. Ganger, Hector M. Briceño, Russell Hunt, David Mazières, Thomas Pinckney, Robert Grimm, John Jannotti, Kenneth Mackenzie,
in Proc. of the 16th ACM Symposium on Operating Systems Principles, Oct. 1997, pp. 52-65.
Not presented. (snow day & no volunteers)
Additional suggested reading
There are a wide range of papers that address OS performance and
flexibility, many of them coming from the microkernel camp. A related
line of work looks at extending OS functionality by downloading code into
the kernel (we will be looking at one specific method for this later in the term).
- Background on exokernel: Exokernel: An Operating System Architecture for Application-Level Resource Management
Dawson R. Engler, M. Frans Kaashoek and James W. O'Toole, in Proc. of the 15th ACM Symposium on Operating Systems Principles, Dec. 1995, pp. 251-266.
- Flexibility in support of research: The Flux OSKit: a substrate for kernel and language research
Bryan Ford, Godmar Back, Greg Benson, Jay Lepreau, Albert Lin, and Olin Shivers, in Proc. of the 16th ACM Symposium on Operating Systems Principles, Oct. 1997, pp. 38-51.
- Protecting against bad kernel extensions: Dealing With Disaster: Surviving Misbehaved Kernel Extensions(ps)
Margo I. Seltzer, Yasuhiro Endo, Christopher Small, and Keith A. Smith, in Proc. of the 2nd Usenix Symposium on Operating System Design and Implementation, Oct. 1996, pp. 213-227.
- One of many Mach papers: The Duality of Memory and Communication
in the Implementation of a Multiprocessor Operating System
Michael Young, Avadis Tevanian, Richard Rashid, David Golub,
Jeffrey Eppinger, Jonathan Chew, William Bolosky, David Black,Robert Baron,
in Proc. of the 11th ACM Symposium on Operating Systems Principles, 1987, pp. 63-76.
Week 5 - Concurrency
Feb. 8
Read and provide summaries for the following papers:
- 6. The performance implications of thread management alternatives for shared-memory multiprocessors
Thomas E. Anderson, Edward D. Lazowska, Henry M. Levy,
in IEEE Transactions on Computers, vol. 38, no. 12, Dec. 1989, pp. 1631-1644.
presentation by Davor Capalija
- 7. Capriccio: scalable threads for internet services
Rob von Behren, Jeremy Condit, Feng Zhou, George C. Necula, Eric Brewer,
in Proc. of the 19th ACM Symposium on Operating Systems Principles, Oct. 2003, pp. 268-281.
presentation by Lee Chew
Additional suggested reading
The following items provide some additional background and perspectives
on the challenges of programming with threads:
Week 6 - OS Specialization and Non-blocking Synchronization.
Feb. 15
Read and provide summaries for the following papers:
Additional suggested reading
Feb. 18-22: Reading Week, No Classes
Week 7 - Scheduling and Resource Accounting
Feb. 29
Read and provide summaries for the following papers:
Additional suggested reading (to be added)
Week 8 - Local File Systems
Mar. 7
Read and provide summaries for the following papers:
- 12. Generalized file system dependencies
Christopher Frost, Mike Mammarella, Eddie Kohler, Andrew de los Reyes, Shant Hovsepian, Andrew Matsuoka and Lei Zhang, in Proc. of the 21st ACM Symposium on Operating Systems Principles, Oct. 2007, pp. 307-320.
presented by James Huang
- 13. Rethink the sync
Edmund B. Nightingale, Kaushik Veeraraghavan, Peter M. Chen and Jason Flinn, in Proc. of the 7th USENIX Symposium on Operating System Design and Implementation, Nov. 2006, pp. 1-14.
presented by Bogdan Simion
Additional suggested reading (to be added)
Week 9 - Distributed File Systems
Mar. 14
Read and provide summaries for the following papers:
- 14. Scale and Performance in a Distributed File System
J. Howard, M. Kazar, et. al, ACM Transactions on Computer Systems,
vol. 6, no. 1, February 1988, pp. 51-81.
presented by [available again]
- 15. Distributed Directory Service in the Farsite File System
John R. Douceur and Jon Howell, in Proc. of the 7th USENIX Symposium on Operating System Design and Implementation, Nov. 2006, pp. 321-324.
presented by Istemi Ekin Akkus
Additional suggested reading (to be added)
Week 10 - Virtualization
Mar. 20 - Reschedule to Thursday due to Good Friday
Read and provide summaries for the following papers:
- 16. Xen and the art of virtualization
P. Barham, B. Dragovic, K. Fraser, S. Hand, T. Harris, A. Ho, R. Neugebauer, I. Pratt, A. Warfield, in Proceedings of the 19th SOSP, 2003, pp. 164-177.
presented by Jonathan Deber
- 17. Memory Resource Management in VMware ESX Server
C. Waldspurger, in Proc. of the 5th Usenix Symposium on Operating System Design and Implementation, Dec. 2002, pp. 181-194.
presented by Adrian Popescu
Additional suggested reading (to be added)
Week 11 - Operating Systems for Multiprocessors
Mar. 28
Read and provide summaries for the following papers:
- 18. Tornado: Maximizing Locality and Concurrency in a Shared Memory Multiprocessor Operating System
Ben Gamsa, Orran Krieger, Jonathan Appavoo, and Michael Stumm, in Proc. of the 3rd Usenix Symposium on Operating System Design and Implementation, Feb. 1999, pp. 87-100.
presented by Jason Zebchuk
- 19. Cellular disco: resource management using virtual clusters on shared-memory multiprocessors
K. Govil, D. Teodosiu, Y. Huang, M. Rosenblum,
ACM Transactions on Computer Systems, vol. 18, no. 3, August 2000, pp. 229-262.
(Don't be intimidated by the length of this paper - its just the journal version
of the 16-page SOSP paper, which has larger fonts and pictures. Feel free to read the SOSP version if you prefer to carry less paper.)
presented by Jason Zebchuk
Additional suggested reading (to be added)
Week 12 - Languages and Systems
Apr. 4
Read and provide summaries for the following papers:
- 20. Bugs as deviant behavior: a general approach to inferring errors in systems code
D. Engler, D. Y. Chen, S. Hallem, A. Chou, B. Chelf,
in Proc. of the 19th ACM Symposium on Operating System Principles, Oct. 2001, pp. 57-72.
Quoting Dawson Engler: "This paper has some of my favorite ideas, though unfortunately I can't say the same for the writing."
presented by Jonathan Deber
- 21. Safe Kernel Extensions Without Run-Time Checking
G. Necula, P. Lee, in Proc. of the 2nd Usenix Symposium on Operating System Design and Implementation, Oct. 1996, pp. 229-243.
Winner of the 2006 ACM SIGOPS Hall of Fame Award for most influential paper appearing in OSDI at least 10 years in the past.
presented by Vivek Lakshmanan
Additional suggested reading (to be added)
Week 13 - More Languages and Systems
Apr. 11
Read and provide summaries for the following papers:
- 22. Extensibility safety and performance in the SPIN operating system
B. N. Bershad, S. Savage, P. Pardyak, E. G. Sirer, M. E. Fiuczynski, D. Becker, C. Chambers, S. Eggers,
in Proc. of the 15th ACM Symposium on Operating System Principles, Dec. 1995, pp. 267-283.
presented by Daniel Lupei
- 23. Language Support for Fast and Reliable Message-based Communication in Singularity OS
M. Fahndrich, M. Aiken, C. Hawblitzel, O. Hodson, G. Hunt, J. R. Larus, S. Levi,
in Proc. of the 2006 EuroSys Conference, April 2006, pp. 177-190.
presented by Istemi Ekin Akkus
Additional suggested reading (to be added)
Last modified: Thu Jan 11 23:22:20 EST 2008