Thu
1/9 |
- E. W. Dijkstra, The Structure of the 'THE'-Multiprogramming System,
Communications of the ACM, Vol. 11, No. 5, May 1968, pp. 341-346.
(Additional historical background on semaphores
in Wikipedia.)
Q: Dijkstra explicitly states their goals
for the THE operating system. How do these goals compare to, say,
Microsoft's goals for the Windows operating system? Why do we no longer
build operating systems with the same goals as THE?
- P. B. Hansen, The
Nucleus of a Multiprogramming System, Communications of the ACM,
Vol. 13, No. 4, April 1970, pp. 238-241, 250.
Optional related paper on a deployment experience of RC 4000:
P. B. Hansen, The RC 4000 Real-Time Control System at Pulway, BIT 7, pp. 279-288, 1967.
Q: How does synchronization in the RC 4000 system compare with synchronization in the THE system?
|
Tue
1/14 |
- D. G. Bobrow, J. D. Burchfiel, D. L. Murphy, and R. S. Tomlinson,
TENEX, a Paged Time Sharing System for the PDP-10, Communications of
the ACM, Vol. 15, No. 3, March 1972, pp. 135-143.
Q: What features in TENEX are reminiscent of features in Unix (a later system)?
- W. Wulf, E. Cohen, W. Corwin, A. Jones, R. Levin, C. Pierson, and
F. Pollack, HYDRA: The Kernel of a Multiprocessor Operating System,
Communications of the ACM, Vol. 17, No. 6, June 1974, pp. 337-345.
Q: How is a Hydra procedure different from the procedures we are familiar with in a typical language and runtime environment?
|
Thu
1/16 |
- B. Lampson,
Protection, Operating
Systems Review, Vol. 8, No. 1, January 1974, pp. 18-24.
Q: What are the concepts in HYDRA that
correspond to Lampson's definitions of "Domain", "Object", and "Access
Matrix"? What about Multics?
- J. H. Saltzer, Protection and the Control of Information
Sharing in Multics, Communications of the ACM, Vol. 17, No. 7, July 1974,
pp. 388-402.
Optional Multics paper:
A. Bensoussan, C. T. Clingen, and R. C. Daley,
The Multics Virtual Memory: Concepts and Design,
Communications of the ACM, Vol 15, No. 5, May 1972, pp. 308-318.
Q: Compare and contrast protected subsystems in Multics with procedures in Hydra.
|
Tue
1/21 |
- D. M. Ritchie and K. Thompson, The UNIX Time-Sharing System,
Communications of the ACM, Vol. 17, No. 7, July 1974, pp. 365-375.
Q: What aspects of Unix as described in the 1974 paper do not survive
today, or have been considerably changed?
- R. Pike, D. Presotto, S. Dorward, B. Flandrena, K. Thompson, H. Trickey, and P. Winterbottom,
Plan 9 From Bell Labs,
USENIX Computing Systems, Vol. 8, No. 3, Summer 1995, pp. 221-254.
Q: What does it mean, "9P is really the core of the system; it is fair to say that the Plan 9 kernel is primarily a 9P multiplexer"?
|
Thu
1/23 |
- D. D. Redell, Y. K. Dalal, T. R. Horsley, H. C. Lauer,
W. C. Lynch, P. R. McJones, H. G. Murray, and S. C. Purcell, Pilot: An Operating System for a
Personal Computer, Communications of the ACM, Vol. 23, No. 2,
February 1980, pp. 81-92.
Q: How do the requirements of the Pilot
operating system differ from the systems we have read about so far,
and how does the design of Pilot reflect those
differences?
- Galen C. Hunt and James R. Larus.
Singularity: Rethinking the Software Stack,
ACM SIGOPS Operating Systems Review,
Vol. 41,
No. 2,
April 2007,
pages 37–49.
Q: How does the language-based approach
that Singularity takes compare and contrast with Pilot?
|
Tue
1/28 |
- C. A. R. Hoare, Monitors: An Operating System Structuring
Concept, Communications of the ACM, Vol. 17, No. 10, October, 1974,
pp. 549-557.
Q: What are "monitor invariant" I and "condition" B, and why are they
important in the discussion of monitors?
- B. W. Lampson and D. D. Redell, Experience with Processes and
Monitors in Mesa, Communications of the ACM, Vol. 23, No. 2, February
1980, pp. 105-117.
Q: Compare and contrast synchronization in Java with Hoare monitors
and Mesa monitors.
Optional related papers on a completely different kind of
synchronization known as wait-free or non-blocking synchronization:
For a formal treatment of wait-free synchronization, see Herlihy's
seminal paper:
Maurice
Herlihy, Wait-Free
Synchronization, ACM Transactions on Programming Languages and
Systems (TOPLAS), Vol. 13, No. 1, January 1991, pp. 124–149.
Linux uses a particular version called read-copy-update (RCU):
Paul E. McKenney, Dipankar Sarma, Andrea Arcangeli, Andi Kleen,
Orran Krieger, and Rusty
Russell. Read
Copy Update. In Proceedings of the Ottawa Linux
Symposium, June 2002, pp. 338–367.
And for an extensive bibliography on RCU through 2013, see
this Linux
RCU document.
|
Tue
2/4
|
- D. R. Cheriton and W. Zwaenepoel, The
Distributed V Kernel and its Performance for Diskless
Workstations, Proceedings of the 9th Symposium on Operating
Systems Principles, pp. 129-140, November 1983.
Q: What is the argument for diskless
workstations, and do you agree/disagree with the
argument?
- J. K. Ousterhout, A. R. Cerenson, F. Douglis,
M. N. Nelson, and B. B. Welch, The Sprite Network Operating
System, IEEE Computer, Vol. 21, No. 2, February 1988, pp. 23-36.
Optional historical retrospective:
J. K. Ousterhout,
Sprite Retrospective
Q: How do the caching policies in Sprite
differ from those in the V Kernel?
|
Thu
2/6 |
|
Tue
2/11 |
- H. Haertig, M. Hohmuth, J. Liedtke, S. Schoenberg, J. Wolter,
The Performance of Micro-Kernel- Based Systems, Proceedings
of the 16th Symposium on Operating Systems Principles, October 1997, pp. 66-77.
Optional related papers on hierarchical address spaces and formally verifying a microkernel:
J. Liedtke, On Micro-kernel Construction,
In Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles, December 1995, Copper Mountain Resort, Colorado, pp. 237-250.
G. Klein, K. Elphinstone, G. Heiser, J. Andronick, D. Cock, P. Derrin, D. Elkaduwe, K. Engelhardt, M. Norrish, R. Kolanski, T. Sewell, H. Tuch, S. Winwood,
seL4: Formal Verification of an OS Kernel,
In Proceedings of the 22nd ACM Symposium on Operating Systems Principles, October 2009, Big Sky Resort, MT, pp. 207-220.
Q: Compare and contrast the L4 microkernel with the RC4000 Nucleus
and the HYDRA kernel in terms of their goals to provide a basis
on which higher level OS functionality can be implemented.
- D. R. Engler, M. F. Kaashoek, and J. O'Toole Jr.,
Exokernel: An Operating System Architecture for Application-Level Resource Management,
In Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles, December 1995, Copper Mountain Resort, Colorado, pp. 251-266.
Q: Compare and contrast an exokernel with a microkernel.
Optional — the other Exokernel paper:
M. F. Kaashoek, D. R. Engler, G. R. Ganger, H. M. Briceno, R. Hunt, D. Mazieres, T. Pinckney, R. Grimm, J. Jannotti and K. Mackenzie, Application Performance and Flexibility on Exokernel Systems, In Proceedings of the Sixteenth ACM Symposium on Operating Systems Principles, October 1997, St. Malo, France, pp. 52-65.
Unikernels are a contemporary take on library operating systems (also see Mirage OS):
Anil Madhavapeddy, Richard Mortier, Charalampos Rotsos, David Scott, Balraj Singh, Thomas Gazagnaire, Steven Smith, Steven Hand and Jon Crowcroft,
Unikernels: Library Operating Systems for the Cloud, In Proceedings of
the 18th
International Conference on Architectural Support
for Programming Languages and Operating Systems
(ASPLOS), pp. 461–472, March 2013.
|
Thu
2/13 |
- R. J. Creasy, The Origin of the VM/370 Time-Sharing System, In IBM Journal of
Research and Development, 25(5):483-490, September 1981.
Q: What was VM/370's motivation for virtualizing the hardware?
- P. Barham, B. Dragovic, K. Fraser, S. Hand, T. Harris, A. Ho, R. Neugebauer, I. Pratt, and A. Warfield, Xen and the Art of Virtualization, In Proceedings of the 19th Symposium on Operating System Principles, October, 2003.
Q: Microkernels and virtual machine monitors are two different ways to
support the execution of multiple operating systems on modern
hardware. How does the microkernel approach in L4 compare and
constrast with the VMM approach in Xen?
Optional related paper describing VMware virtualization performance and comparing software versus hardware virtualization approaches (2006-era):
Keith Adams and Ole Agesen,
A Comparison of Software and Hardware Techniques for x86 Virtualization,
In Proceedings of the 12th International Conference on Architectural Support for Programming Languages and Operating Systems, October 2006, pp. 2–13.
Disco is the precursor to VMware, a company the authors later founded:
Edouard Bugnion, Scott Devine, Kinshuk Govil, Mendel
Rosenblum, Disco: Running
Commodity Operating Systems on Scalable Multiprocessors.
ACM Transactions on
Computer Systems, 15(4), November 1997, pp. 412–447.
|
Tue
2/18 |
|
Thu
2/20 |
- Thomas E. Anderson, Brian N. Bershad, Edward D. Lazowska, Henry M. Levy, Scheduler Activations: Effective Kernel Support for the User-level Management of Parallelism, Proceedings of the 13th ACM
Symposium on Operating Systems Principles, Sept. 1991, pp. 95-109.
Q: The goal of scheduler activations is to have the benefits of both user
and kernel threads without their limitations. What are the
limitations of user and kernel threads, and what are the benefits that
scheduler activations provide?
A modern incarnation of scheduler activations:
Henry Qin, Qian Li, Jacqueline Speiser, Peter Kraft and John
Ousterhout, Arachne:
Core-Aware Thread Management, In Proceedings of the Thirteenth
USENIX Symposium on Operating System Design and Implementation,
pp. 145–160,
October 2018.
Windows also supports a form of scheduler activations called User-mode
scheduling (UMS).
- Carl A. Waldspurger and William E. Weihl, Lottery Scheduling: Flexible Proportional-Share Resource Management. In Proceedings of the First USENIX Symposium on Operating System Design and Implementation, November, 1994.
Q: At a high level, as a mechanism how does lottery scheduling provide
modular resource management? Why can't the Unix scheduler provide a
similar kind of management?
Optional related papers on lottery scheduling:
David Petrou, John W. Milford, Garth A. Gibson, Implementing
Lottery Scheduling: Matching the Specializations in Traditional
Schedulers, In Proceedings of the USENIX Annual Technical Conference, 1999.
Carl A. Waldspurger and William E. Weihl, Stride Scheduling: Deterministic Proportional-Share Resource Management,
Technical Report: TM-528, MIT, Cambridge, MA, 1995.
|
Tue
2/25 |
-
A. D. Birrell and B. J. Nelson, Implementing Remote
Procedure Calls, ACM Transactions on Computer Systems, Vol. 2, No. 1,
pp. 39-59, February 1984.
Q: In what ways do the authors optimize connection management?
Optional reading on highly-optimized RPC for data center communication:
Anuj Kalia, Michael Kaminsky and David Andersen,
Datacenter RPCs can be General and Fast,
In Proceedings of the 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI), Boston, MA, Feb 2019.
and pointers to contemporary RPC and data wrangling packages:
Google RPC & Protocol Buffers,
Facebook Thrift, JSON-RPC/XML-RPC, SOAP.
-
Adam Belay, George Prekas, Ana Klimovic, Samuel Grossman, Christos
Kozyrakis, Edouard Bugnion,
IX:
A Protected Dataplane Operating System for High Throughput and Low
Latency, In Proceedings of the 11th USENIX Symposium on
Operating Systems Design and Implementation, October 2014,
49–65.
Optional reading on a microkernel architecture for user-level networking functionality:
Michael Marty, Marc de Kruijf, Jacob Adriaens, Christopher Alfeld,
Sean Bauer, Carlo Contavalli, Michael Dalton, Nandita Dukkipati,
William C. Evans, Steve Gribble, Nicholas Kidd, Roman Kononov, Gautam
Kumar, Carl Mauer, Emily Musick, Lena Olson, Erik Rubow, Michael Ryan,
Kevin Springborn, Paul Turner, Valas Valancius, Xi Wang and Amin
Vahdat,
Snap: a Microkernel Approach to Host Networking,
In Proceedings of the 27th ACM Symposium on Operating Systems Principles (SOSP), Huntsville, ON, Canada, October 2019.
|
Thu
2/27 |
- Marshall K. McKusick, William N. Joy, Samuel J. Leffler, and
Robert S. Fabry, A Fast File System for Unix, ACM Transactions on
Computer Systems, 2(3), August 1984, pp. 181-197.
Q: In FFS, reading is always at least as fast as writing.
In old UFS, writing was 50% faster. Why is this?
- Mendel Rosenblum and John K. Ousterhout, The
Design and Implementation of a Log-Structured File System,
Proceedings of the 13th ACM Symposium on Operating Systems Principles,
December 1991.
Q: When we want to read a block in LFS on disk, how do we figure out where it is?
|
Tue
3/3 |
|
Thu
3/5 |
- Sanjay Ghemawat, Howard Gobioff, Shun-Tak Leung,
The
Google File System, In Proceedings of the Nineteenth ACM
Symposium on Operating Systems Principles (SOSP), pp. 29–43,
October 2003.
Optional GFS retrospective:
Marshall Kirk McKusick and Sean Quinlan, GFS: Evolution on Fast-forward, ACM Queue, August 2009.
HDFS is an open-source distributed file system inspired by GFS:
Konstantin Shvachko, Hairong Kuang, Sanjay Radia and Robert Chansler,
The Hadoop Distributed File System,
In Proceedings of the 26th IEEE Symposium on Massive Storage Systems and Technologies (MSST), May 2010.
Windows Azure Storage is Microsoft's cloud storage system:
Brad Calder et al.,
Windows Azure Storage: A Highly Available
Cloud Storage Service with Strong Consistency, In
Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles
(SOSP), October 2011, pp. 143–157.
- Helgi Sigurbjarnarson, James Bornholt, Emina Torlak, and Xi Wang,
Push-Button Verification of File Systems
via Crash Refinement, In
Proceedings of the 12th Symposium on Operating Systems Design and Implementation (OSDI), pp. 1–16, November 2016.
|
Tue
3/10 |
-
Silas Boyd-Wickizer, Austin T. Clements, Yandong Mao, Aleksey Pesterev,
M. Frans Kaashoek, Robert Morris, and Nickolai Zeldovich.
An
Analysis of Linux Scalability to Many Cores
In Proceedings of the 9th
Symposium on Operating System Design & Implementation (OSDI), October
2010, Vancouver, BC, Canada, pp. 383–398.
As optional further reading, this group's first work was exploring
OS multicore scalability using an exokernel:
Silas Boyd-Wickizer, Haibo Chen, Rong Chen, Yandong Mao,
Frans Kaashoek, Robert Morris, Aleksey Pesterev, Lex Stein, Ming Wu,
Yuehua Dai, Yang Zhang, and Zheng Zhang.
Corey:
An Operating System for Many Cores. In Proceedings of the 8th
Symposium on Operating System Design & Implementation (OSDI),
October 2008, San Diego, California, pp. 43–57.
Then they framed OS multicore scalability in more
fundamental aspects:
Austin T. Clements, M. Frans Kaashoek, Nickolai Zeldovich, Robert Morris, Eddie Kohler,
The Scalable Commutativity Rule: Designing Scalable Software for Multicore Processors,
In
Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles
(SOSP), October 2013, pp. 1–17.
-
Amit Levy, Bradford Campbell, Branden Ghena, Daniel B Giffin, Pat Pannuto, Prabal Dutta, Philip Levis,
Multiprogramming a 64 kB Computer Safely and Efficiently,
In
Proceedings of the Twenty-Sixth ACM Symposium on Operating Systems Principles
(SOSP), October 2017, pp. 1–17.
|
Thu
3/12 |
- (Any of the following that strike your fancy)
-
Michael Vrable, Justin Ma, Jay Chen, David Moore, Erik VandeKieft,
Alex C. Snoeren, Geoffrey M. Voelker, and Stefan Savage,
Scalability,
Fidelity and Containment in the Potemkin Virtual Honeyfarm,
Proceedings of the 20th ACM Symposium on Operating Systems Principles
(SOSP), Brighton, UK, October 2005, pages 148-162.
-
Diwaker Gupta, Kenneth Yocum, Marvin McNett, Alex C. Snoeren, Amin Vahdat, and Geoffrey M. Voelker,
To Infinity and Beyond: Time-Warped Network Emulation, Proceedings of the 3rd ACM/USENIX Symposium on Networked Systems Design and Implementation (NSDI), San Jose, CA, May 2006, pages 87-100.
-
Diwaker Gupta, Kashi Vishwanath, and Amin Vahdat, DieCast: Testing Distributed Systems with an Accurate Scale
Model, Proceedings of the 5th ACM/USENIX Symposium on Networked
Systems Design and Implementation (NSDI), San Francisco, CA, April
2008.
-
Diwaker Gupta, Sangmin Lee, Michael Vrable, Stefan Savage, Alex
C. Snoeren, George Varghese, Geoffrey M. Voelker, and Amin
Vahdat, Difference
Engine: Harnessing Memory Redundancy in Virtual Machines,
Proceedings of the 8th ACM/USENIX Symposium on Operating System Design
and Implementation (OSDI), San Diego, CA, December 2008.
-
Michael Vrable, Stefan Savage, and Geoffrey M. Voelker.
Cumulus: Filesystem Backup to the Cloud,
ACM Transaction on Storage 5(4):1-28, December 2009.
-
Michael Vrable, Stefan Savage, and Geoffrey M. Voelker,
BlueSky: A Cloud-Backed File System for the Enterprise,
Proceedings of the 7th USENIX Conference on File and Storage Technologies (FAST), San Jose, CA, February 2012, pages 19:1-19:14.
-
He Liu, Feng Lu, Alex Forencich, Rishi Kapoor, Malveeka Tewari, Geoffrey M. Voelker, George Papen, Alex C. Snoeren, and George Porter,
Circuit Switching Under the Radar with REACToR,
Proceedings of the 11th ACM/USENIX Symposium on Networked Systems Design and Implementation (NSDI), Seattle, WA, April 2014, pages 1–15.
|