Seminar: Operating System Classics

In the seminar "Operating System Classics", the students read, summarize and present "classic" operating system papers from the 1960s until today. Thereby, we will look at the different important aspects that make up the foundations of our modern computing world, from virtual memory, over file systems, to synchronization primitives. Only if we understand how previous generations of engineers have solved the problems of their times, we can develop new abstractions for the next generation of hardware.

Papers

In the seminar, you will choose one of these papers, read it, summarize it and present its core concepts to the group.

Operating System Architectures

• Fernando J. Corbató, Marjorie Merwin-Daggett, and Robert C. Daley. 1962. An experimental time-sharing system. In Proceedings of the May 1-3, 1962, spring joint computer conference (AIEE-IRE '62 (Spring)). Association for Computing Machinery, New York, NY, USA, 335–344. DOI:https://doi.org/10.1145/1460833.1460871
• D. R. Engler, M. F. Kaashoek, and J. O'Toole. 1995. Exokernel: an operating system architecture for application-level resource management. In Proceedings of the fifteenth ACM symposium on Operating systems principles (SOSP '95). Association for Computing Machinery, New York, NY, USA, 251–266. DOI:https://doi.org/10.1145/224056.224076
• Per Brinch Hansen. 1970. The nucleus of a multiprogramming system. Commun. ACM 13, 4 (April 1970), 238–241. DOI:https://doi.org/10.1145/362258.362278
• Hermann Härtig, Michael Hohmuth, Jochen Liedtke, Sebastian Schönberg, and Jean Wolter. 1997. The performance of μ-kernel-based systems. In Proceedings of the sixteenth ACM symposium on Operating systems principles (SOSP '97). Association for Computing Machinery, New York, NY, USA, 66–77. DOI:https://doi.org/10.1145/268998.266660
• Galen C. Hunt and James R. Larus. 2007. Singularity: rethinking the software stack. SIGOPS Oper. Syst. Rev. 41, 2 (April 2007), 37–49. DOI:https://doi.org/10.1145/1243418.1243424

Synchronization

• Leslie Lamport. 1978. Time, clocks, and the ordering of events in a distributed system Commun. ACM 21, 7 (July 1978), 558–565. DOI:https://doi.org/10.1145/359545.359563
• C. A. R. Hoare. 1974. Monitors: an operating system structuring concept. Commun. ACM 17, 10 (Oct. 1974), 549–557. DOI:https://doi.org/10.1145/355620.361161
• Hugh C. Lauer and Roger M. Needham. 1979. On the duality of operating system structures. SIGOPS Oper. Syst. Rev. 13, 2 (April 1979), 3–19. DOI:https://doi.org/10.1145/850657.850658

Memory Management

• A. Bensoussan, C. T. Clingen, and R. C. Daley. 1972. The Multics virtual memory: concepts and design. Commun. ACM 15, 5 (May 1972), 308–318. DOI:https://doi.org/10.1145/355602.361306
• Andrew W. Appel and Kai Li. 1991. Virtual memory primitives for user programs. In Proceedings of the fourth international conference on Architectural support for programming languages and operating systems (ASPLOS IV). Association for Computing Machinery, New York, NY, USA, 96–107. DOI:https://doi.org/10.1145/106972.106984
• Richard Rashid, Avadis Tevanian, Michael Young, David Golub, Robert Baron, David Black, William Bolosky, and Jonathan Chew. 1987. Machine-independent virtual memory management for paged uniprocessor and multiprocessor architectures. In Proceedings of the second international conference on Architectual support for programming languages and operating systems (ASPLOS II). IEEE Computer Society Press, Washington, DC, USA, 31–39. DOI:https://doi.org/10.1145/36206.36181
• Peter J. Denning. 1967. The working set model for program behavior. In Proceedings of the first ACM symposium on Operating System Principles (SOSP '67). Association for Computing Machinery, New York, NY, USA, 15.1–15.12. DOI:https://doi.org/10.1145/800001.811670

Scheduling

• Carl A. Waldspurger and William E. Weihl. 1994. Lottery scheduling: flexible proportional-share resource management. In Proceedings of the 1st USENIX conference on Operating Systems Design and Implementation (OSDI '94). USENIX Association, USA, 1–es.
• C. L. Liu and J. W. Layland: Scheduling Algoritms for Multiprogramming in a Hard-Real-Time Environment, Journal of ACM, Vol. 20, No. 1, January 1973.
• L. Sha, R. Rajkumar, and J. P. Lehoczky: Priority Inheritance Protocols: An Approach to Real-Time Synchronization, IEEE Transactions on Computers, Vol. 39, No. 9, September 1990.
• Robert Geist and Stephen Daniel. 1987. A continuum of disk scheduling algorithms. ACM Trans. Comput. Syst. 5, 1 (Feb. 1987), 77–92. DOI:https://doi.org/10.1145/7351.8929

The Multi-Core Challenge

• Edouard Bugnion, Scott Devine, Kinshuk Govil, and Mendel Rosenblum. 1997. Disco: running commodity operating systems on scalable multiprocessors. ACM Trans. Comput. Syst. 15, 4 (Nov. 1997), 412–447. DOI:https://doi.org/10.1145/265924.265903
• Paul E. Mckenney and John D. Slingwine. Read-Copy Update: Using Execution History to Solve Concurrency Problems, Parallel and Distributed Computing and Systems, Oct 1998.
• Andrew Baumann, Paul Barham, Pierre-Evariste Dagand, Tim Harris, Rebecca Isaacs, Simon Peter, Timothy Roscoe, Adrian Schüpbach, and Akhilesh Singhania. 2009. The multikernel: a new OS architecture for scalable multicore systems. In Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles (SOSP '09). Association for Computing Machinery, New York, NY, USA, 29–44. DOI:https://doi.org/10.1145/1629575.1629579
• David Wentzlaff and Anant Agarwal. 2009. Factored operating systems (fos): the case for a scalable operating system for multicores. SIGOPS Oper. Syst. Rev. 43, 2 (April 2009), 76–85. DOI:https://doi.org/10.1145/1531793.1531805

Filesystems and Storage

• R. C. Daley and P. G. Neumann. 1965. A general-purpose file system for secondary storage. In Proceedings of the November 30--December 1, 1965, fall joint computer conference, part I (AFIPS '65 (Fall, part I)). Association for Computing Machinery, New York, NY, USA, 213–229. DOI:https://doi.org/10.1145/1463891.1463915
• Mendel Rosenblum and John K. Ousterhout. 1992. The design and implementation of a log-structured file system. ACM Trans. Comput. Syst. 10, 1 (Feb. 1992), 26–52. DOI:https://doi.org/10.1145/146941.146943
• David A. Patterson, Garth Gibson, and Randy H. Katz. 1988. A case for redundant arrays of inexpensive disks (RAID). SIGMOD Rec. 17, 3 (June 1988), 109–116. DOI:https://doi.org/10.1145/971701.50214
• Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. 2003. The Google file system. SIGOPS Oper. Syst. Rev. 37, 5 (December 2003), 29–43. DOI:https://doi.org/10.1145/1165389.945450
• Marshall K McKusick, William N. Joy, Samuel J. Leffler, and Robert S. Fabry. 1983. A Fast File System for UNIX (Revised July 27, 1983). Technical Report. University of California at Berkeley, USA.

Virtualization

• Gerald J. Popek and Robert P. Goldberg. 1974. Formal requirements for virtualizable third generation architectures. Commun. ACM 17, 7 (July 1974), 412–421. DOI:https://doi.org/10.1145/361011.361073
• Paul Barham, Boris Dragovic, Keir Fraser, Steven Hand, Tim Harris, Alex Ho, Rolf Neugebauery, Ian Pratt, Andrew Warfield “Xen and the Art of Virtuaization”, Proceedings of the 19th ACM Symposium on Operating Systems Principles (2003).
• Carl A. Waldspurger. 2003. Memory resource management in VMware ESX server. SIGOPS Oper. Syst. Rev. 36, SI (Winter 2002), 181–194. DOI:https://doi.org/10.1145/844128.844146

Security and other Problems

• Gerwin Klein, Kevin Elphinstone, Gernot Heiser, June Andronick, David Cock, Philip Derrin, Dhammika Elkaduwe, Kai Engelhardt, Rafal Kolanski, Michael Norrish, Thomas Sewell, Harvey Tuch, and Simon Winwood. 2009. SeL4: formal verification of an OS kernel. In Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles (SOSP '09). Association for Computing Machinery, New York, NY, USA, 207–220. DOI:https://doi.org/10.1145/1629575.1629596
• Andy Chou, Junfeng Yang, Benjamin Chelf, Seth Hallem, and Dawson Engler. 2001. An empirical study of operating systems errors. SIGOPS Oper. Syst. Rev. 35, 5 (Dec. 2001), 73–88. DOI:https://doi.org/10.1145/502059.502042
• Karger, Paul A., and Roger R. Schell. "Multics security evaluation: Vulnerability analysis." 1974

Extensible Operating Systems

• B. N. Bershad, S. Savage, P. Pardyak, E. G. Sirer, M. E. Fiuczynski, D. Becker, C. Chambers, and S. Eggers. 1995. Extensibility safety and performance in the SPIN operating system. SIGOPS Oper. Syst. Rev. 29, 5 (Dec. 3, 1995), 267–283. DOI:https://doi.org/10.1145/224057.224077
• Simon Peter, Jialin Li, Irene Zhang, Dan R. K. Ports, Doug Woos, Arvind Krishnamurthy, Thomas Anderson, and Timothy Roscoe. 2015. Arrakis: The Operating System Is the Control Plane. ACM Trans. Comput. Syst. 33, 4, Article 11 (January 2016), 30 pages. DOI:https://doi.org/10.1145/2812806
• Pu, Calton, Henry Massalin, and John Ioannidis. "The synthesis kernel." Computing Systems 1.1 (1988): 11-32.

Evaluation

• SS22 • Seminar • Evaluation (PDF)

Anmeldung und weitere Infos

Für diese Veranstaltung ist eine Online-Anmeldung über Stud.IP erforderlich. Bitte registrieren Sie sich (falls noch nicht geschehen) für Stud.IP und tragen Sie sich dort in die entsprechende Veranstaltung ein.

Stud.IP Veranstaltungen