CS 523: Schedule and Discussion

Course Overview

Wed 1/21

Course Overview

Historical Perspectives

Fri 1/23

E. W. Dijkstra, The Structure of the "THE"-Multiprogramming System, In Proceedings of the 1st ACM Symposium on Operating System Principles (SOSP '67), October 1967. P. B. Hansen, The Nucleus of a Multiprogramming System, Communications of the ACM, Vol. 13, No. 4, April 1970, pp. 238-241.

Wed 1/28

D. G. Bobrow, J. D. Burchfiel, D. L. Murphy, and R. S. Tomlinson, TENEX, a Paged Time Sharing System for the PDP-10, In Proceedings of the 3rd Annual Symposium on Operating Systems Principles (SOSP '71), October 1971. Additional historical background about PDP-10 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. H. M. Levy, Chapter 8: The Hydra System, Capability-Based Computer Systems, Digital Press, 1984. W. Wulf and C. G. Bell, C.mmp: a multi-mini-processor, In Proceedings of AFIPS Fall Joint Computing Conference, December 1972.

Fri 1/30

D. M. Ritchie and K. Thompson, The UNIX Time-Sharing System, In Proceedings of the 4th Annual Symposium on Operating Systems Principles (SOSP '73), October 1973. 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. Linux's History written by Linus Torvalds A. S. Tanenbaum, Lessons learned from 30 years of MINIX, Communications of the ACM, March 2016, Vol. 59 No. 3, Pages 70-78. The Tanenbaum–Torvalds Debate

Microkernel

Wed 2/4

H. Härtig, M. Hohmuth, J. Liedtke, S. Schönberg, and J. Wolter, The Performance of μ-Kernel-Based Systems, In Proceedings of the 16th Symposium on Operating Systems Principles (SOSP '97), October 1997. J. Liedtke, Improving IPC by Kernel Design, In Proceedings of the 14th ACM Symposium on Operating Systems Principles (SOSP '93), December 1993. J. Liedtke, On Micro-kernel Construction, In Proceedings of the 15th ACM Symposium on Operating Systems Principles (SOSP '95), December 1995. 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 (SOSP '09), October 2009. K. Elphinstone and G. Heiser, From L3 to seL4: What Have We Learnt in 20 Years of L4 Microkernels?, In Proceedings of the 24nd ACM Symposium on Operating Systems Principles (SOSP '13), November 2013.

Library OS

Fri 2/6

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 15th ACM Symposium on Operating Systems Principles (SOSP '95), December 1995. 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 16th ACM Symposium on Operating Systems Principles (SOSP '97), October 1997. C.-C. Tsai, D. E. Porter, and M. Vij, Graphene-SGX: A Practical Library OS for Unmodified Applications on SGX, In Proceedings of the 2017 USENIX Annual Technical Conference (USENIX ATC '17), July, 2017. A. Madhavapeddy, R. Mortier, C. Rotsos, D. Scott, B. Singh, T. Gazagnaire, S. Smith, S. Hand, and J. 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 '13), March 2013.

Synchronization

Wed 2/11

B. W. Lampson and D. D. Redell, Experience with Processes and Monitors in Mesa, In Proceedings of the 7th ACM Symposium on Operating Systems Principles (SOSP '79), December 1979. 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, In Proceedings of the 7th ACM Symposium on Operating Systems Principles (SOSP '79), December 1979. C. A. R. Hoare, Monitors: An Operating System Structuring Concept, Communications of the ACM, Vol. 17, No. 10, October 1974, pp. 549-557. C. A. R. Hoare, Communicating Sequential Processes, Communications of the ACM, Vol. 21, No. 8, August 1987, pp. 666-667. R. Pike, Concurrency is not parallelism, The Go Programming Language Blog.

Fri 2/13

M. Musuvathi, S. Qadeer, T. Ball, G. Basler, P. A. Nainar, and I. Neamtiu, Finding and Reproducing Heisenbugs in Concurrent Programs, In Proceedings of the 8th Symposium on Operating Systems Design and Implementation (OSDI '08), Dec. 2008. G. Li, S. Lu, M. Musuvathi, S. Nath, and R. Padhye, Efficient Scalable Thread-Safety-Violation Detection: Finding thousands of concurrency bugs during testing, In Proceedings of the ACM SIGOPS 27th Symposium on Operating Systems Principles (SOSP '19), Oct 2019. D.R. Jeong, Y. Choi, B. Lee, I. Shin, Y. Kwon, OZZ: Identifying Kernel Out-of-Order Concurrency Bugs with In-Vivo Memory Access Reordering, In Proceedings of the ACM SIGOPS 30th Symposium on Operating Systems Principles (SOSP '24), November 2024. S. Gong, D. Peng, D. Altınbüken, P. Fonseca, P. Maniatis, Snowcat: Efficient Kernel Concurrency Testing using a Learned Coverage Predictor, In Proceedings of the 29th Symposium on Operating Systems Principles (SOSP '23), November 2023. P. Fonseca, R. Rodrigues, B. B. Brandenburg SKI: Exposing Kernel Concurrency Bugs through Systematic Schedule Exploration, In Proceedings of the 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI '14), October 2014. J. Yang, H. Cui, J. Wu, Y. Tang, and G. Hu, Making Parallel Programs Reliable with Stable Multithreading, Communications of the ACM, March 2014, Vol. 57 No. 3, pp. 58-69. W. Xiong, S. Park, J. Zhang, Y. Zhou, and Z. Ma, Ad Hoc Synchronization Considered Harmful, In Proceedings of the 9th Symposium on Operating Systems Design and Implementation (OSDI '10), October 2010.

Scheduling

Wed 2/18

T. E. Anderson, B. N. Bershad, E. D. Lazowska, H. M. Levy, Scheduler Activations: Effective Kernel Support for the User-level Management of Parallelism, In Proceedings of the 13th ACM Symposium on Operating Systems Principles (SOSP '91), September 1991. J.T. Humphries, N. Natu, A. Chaugule, O. Weisse, B. Rhoden, J. Don, L. Rizzo, O. Rombakh, P.J. Turner, C. Kozyrakis, ghOSt: Fast and Flexible User-Space Delegation of Linux Scheduling, In Proceedings of the 28th ACM Symposium on Operating Systems Principles (SOSP '21), October 2021.

Fri 2/20

J-P. Lozi, B. Lepers, J. Funston, F. Gaud, V. Quéma, and A. Fedorova, The Linux Scheduler: a Decade of Wasted Cores, In Proceedings of the 11th European Conference on Computer Systems (EuroSys '16), April 2016. J. Lawall, K. Nishimura, and J-P. Lozi, Should We Balance? Towards Formal Verification of the Linux Kernel Scheduler, In Proceedings of the 31st Static Analysis Symposium, October 2024.

Memory Management

Wed 2/25

R. Rashid, A. Tevanian, M. Young, D. Golub, R. Baronn, D. Black, W. Bolosky, and J. Chew, Machine-Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures, In Proceedings of the 2nd International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '87), October 1987. C. D. Cranor and G. M. Parulkar, The UVM Virtual Memory System, In Proceedings of the 1999 USENIX Annual Technical Conference (USENIX ATC '99), Jun. 1999. H. M. Levy and P. Lipman, Virtual Memory Management in VAX/VMS Operating System, IEEE Computer, Vol. 15, No. 3, March 1982, pp. 35-41. A. Bensoussan, C. T. Clingen, and R. C. Daley, The Multics Virtual Memory: Concepts and Design, In Proceedings of the 2nd ACM Symposium on Operating Systems Principles (SOSP '69), October 1969.

Fri 2/27

D. Skarlatos, A. Kokolis, T. Xu, and J. Torrellas, Elastic Cuckoo Page Tables: Rethinking Virtual Memory Translation for Parallelism, In Proceedings of the 25th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS'20), March 2020. J. Stojkovic, D. Skarlatos, A. Kokolis, T. Xu, and J. Torrellas, Parallel Virtualized Memory Translation with Nested Elastic Cuckoo Page Tables, In Proceedings of the 27th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS'22), Feb. 2022. T. W. Barr, A. L. Cox, and S. Rixner, Translation Caching: Skip, Don’t Walk (the Page Table), In Proceedings of the 37th Annual International Symposium on Computer Architecture (ISCA '10), June 2010. M. Talluri, M. D. Hill, and Y. A. Khalidi, A New Page Table for 64-bit Address Spaces, In Proceedings of the 15th ACM Symposium on Operating Systems Principles (SOSP '95), December 1995. I. Yaniv and D. Tsafrir, Hash, Don't Cache (the Page Table), In Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science (SIGMETRICS '16), June 2016.

File Systems

Wed 3/4

M. Rosenblum and J. K. Ousterhout, The Design and Implementation of a Log-Structured File System, Proceedings of the 13th ACM Symposium on Operating Systems Principles (SOSP '91), December 1991. M. K. McKusick, W. N. Joy, S. J. Leffler, and R. S. Fabry, A Fast File System for Unix, ACM Transactions on Computer Systems, 2(3), August 1984, pp. 181-197. M. Seltzer, K. A. Smith, H. Balakrishnan, J. Chang, S. McMains, V. Padmanabhan, File System Logging Versus Clustering: A Performance Comparison, In Proceedings of USENIX 1995 Technical Conference, January 1995. The Ousterhout-Seltzer Debate A Critique of Seltzer's LFS Measurements A Response to Ousterhout's Critique of LFS Measurements A Response to Seltzer's Response V. Aurora, Log-structured file systems: There's one in every SSD, LWN.net, September 2009.

Fri 3/6

P. M. Chen, W. T. Ng, S. Chandra, C. Aycock, G. Rajamani, and D. Low, The Rio File Cache: Surviving Operating System Crashes, In Proceedings of the 7th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS VII), October 1996. G. R. Ganger, M. K. McKusick, C. A. N. Soules, and Y. N. Patt, Soft Updates: A Solution to the Metadata Update Problem in File Systems, ACM Transactions on Computer Systems (TOCS), Vol. 18, No. 2, May 2000, Pages 127-153.

Network

Wed 3/11

A. Belay, G. Prekas, A. Klimovic, S. Grossman, C. Kozyrakis, E. 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 (OSDI '14), October 2014. A. Belay, A. Bittau, A. Mashtizadeh, D. Terei, D. Mazières, and C. Kozyrakis, Dune: Safe User-level Access to Privileged CPU Features, In Proceedings of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI '12), October 2012. David R. Cheriton and Willy Zwaenepoel, The Distributed V Kernel and its Performance for Diskless Workstations, In Proceedings of the 9th ACM Symposium on Operating Systems Principles (SOSP '83), Oct. 1991. S. Peter, J. Li, I. Zhang, D.R.K. Ports, D. Woos, A. Krishnamurthy, T. Anderson, T. Roscoe, Arrakis: The Operating System is the Control Plane, In Proceedings of the 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI '14), October 2014. I. Zhang, A. Raybuck, P. Patel, K. Olynyk, J. Nelson, O.S.N. Leija, A. Martinez, J. Liu, A.K. Simpson, S. Jayakar, P.H. Penna, M. Demoulin, P. Choudhury, A. Badam, The Demikernel Datapath OS Architecture for Microsecond-scale Datacenter Systems, In Proceedings of the 28th ACM Symposium on Operating Systems Principles (SOSP '21), October 2021.

Fri 3/13

B. Rubin, S. Agarwal, Q. Cai, R. Agarwal, Fast & Safe IO Memory Protection, In Proceedings of the 30th ACM Symposium on Operating Systems Principles (SOSP '24), November 2024.

Virtual Machines

Wed 3/25

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 (SOSP '03), October 2003. K. Adams and O. 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 (ASPLOS '06), October 2006. E. Bugnion, S. Devine, and M. Rosenblum, Disco: Running Commodity Operating Systems on Scalable Multiprocessors , In Proceedings of the 16th ACM symposium on Operating systems principles (SOSP '97), October 1997.

Fri 3/27

J. Zhang, W. Jia, S. Chai, P. Liu, J. Kim, T. Xu, Direct Memory Translation for Virtualized Clouds, In Proceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '24), April 2024. J. Stojkovic, D. Skarlatos, A. Kokolis, T. Xu, J. Torrellas, Parallel Virtualized Memory Translation with Nested Elastic Cuckoo Page Tables, In Proceedings of the 27th ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '22), February 2022. M. Ben-Yehuda, M.D. Day, Z. Dubitzky, M. Factor, N. Har'El, A. Gordon, A. Liguori, O. Wasserman, B.-A. Yassour, The Turtles Project: Design and Implementation of Nested Virtualization, In 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI '10), October 2010.

Containers

Wed 4/1

E. Manco, C. Lupu, F. Schmidt, J. Mendes, S. Mendes, S. Sati, K. Yasukata, C. Raiciu, and F. Huici, My VM is Lighter (and Safer) than your Container, In Proceedings of the 26th Symposium on Operating Systems Principles (SOSP '17), October 2017. A. Agache, M. Brooker, A. Florescu, A. Iordache, A. Liguori, R. Neugebauer, P. Piwonka, and D. -M. Popa, Firecracker: Lightweight Virtualization for Serverless Applications, In Proceedings of the 17th USENIX Symposium on Networked Systems Design and Implementation (NSDI '20), Feb. 2020. Z. Shen, Z. Sun, G. -E. Sela, E. Bagdasaryan, C. Delimitrou, R. V. Renesse, and H. Weatherspoon, X-Containers: Breaking Down Barriers to Improve Performance and Isolation of Cloud-Native Containers, In Proceedings of the 24th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '19), April 2019. S. Soltesz, H. Pötzl, M. E. Fiuczynski, A. Bavier, and L. Peterson, Container-based Operating System Virtualization: A Scalable, High-performance Alternative to Hypervisors, In Proceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems (EuroSys '07), March 2007.

Fri 4/3

J. Stojkovic, T. Xu, H. Franke, J. Torrellas, MXFaaS: Resource Sharing in Serverless Environments for Parallelism and Efficiency, In Proceedings of the 50th Annual International Symposium on Computer Architecture (ISCA '23), June 2023. J. Stojkovic, T. Xu, H. Franke and J. Torrellas, SpecFaaS: Accelerating Serverless Applications with Speculative Function Execution, In Proceedings of 2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA '23), February 2023. J. Stojkovic, N. Iliakopoulou, T. Xu, H. Franke and J. Torrellas, EcoFaaS: Rethinking the Design of Serverless Environments for Energy Efficiency, In Proceedings of 2024 ACM/IEEE 51st Annual International Symposium on Computer Architecture (ISCA '24), June 2024.

Extensibility

Wed 4/8

B.N. Bershad, S. Savage, P. Pardyak, E.G. Sirer, M.E. Fiuczynski, D. Becker, C. Chambers, S. Eggers, Extensibility safety and performance in the SPIN operating system, In Proceedings of the 15th ACM Symposium on Operating Systems Principles (SOSP '95), December 1995. M I. Seltzer, Y. Endo, C. Small, K. A. Smith, Dealing With Disaster: Surviving Misbehaved Kernel Extensions, In Proceedings of the USENIX 2nd Symposium on Operating Systems Design and Implementation (OSDI '96), October 1996.

Fri 4/10

K. K. Dwivedi, R. Iyer, and S. Kashyap, Fast, Flexible, and Practical Kernel Extensions, In Proceedings of the 30th ACM Symposium on Operating Systems Principles (SOSP '24), Nov. 2024. J. Jia, R. Qin, M. Craun, E. Lukiyanov, A. Bansal, M. V. Le, H. Franke, H. Jamjoom, T. Xu, and D. Williams, Safe and usable kernel extension with Rex, arXiv:2502.18832, Feb. 2025.

Reliability

Wed 4/15

D. Engler, D. Y. Chen, S. Hallem, A. Chou, and B. Chelf, Bugs as Deviant Behavior: A General Approach to Inferring Errors in Systems Code, In Proceedings of the Eighteenth ACM Symposium on Operating Systems Principles (SOSP '01), October 2001. D. Engler, B. Chelf, A. Chou, and S. Hallem, Checking System Rules Using System-Specific, Programmer-Written Compiler Extensions, In Proceedings of the 4th Symposium on Operating System Design and Implementation (OSDI '00), October 2000. Z. Li, S. Lu, S. Myagmar, Y. Zhou, CP-Miner: A Tool for Finding Copy-paste and Related Bugs in Operating System Code, In Proceedings of the 6th Symposium on Opearting Systems Design and Implementation (OSDI '04), December 2004.

Fri 4/17

J. Bornholt, R. Joshi, V. Astrauskas, B. Cully, B. Kragl, S. Markle, K. Sauri, D. Schleit, G. Slatton, S. Tasiran, J. Van Geffen, A. Warfield, Using Lightweight Formal Methods to Validate a Key-Value Storage Node in Amazon S3, In Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles (SOSP '21), October 2021. C. Newcombe, T. Rath, F. Zhang, B. Munteanu, M. Brooker, and M. Deardeuff, How Amazon Web Services Uses Formal Methods, Communications of the ACM, Volume 58, Issue 4, pp. 66-73, Mar. 2015. T. Ridge, D. Sheets, T. Tuerk, A. Giugliano, A. Madhavapeddy, and P. Sewell, SibylFS: formal specification and oracle-based testing for POSIX and real-world file systems, In Proceedings of the 25th ACM Symposium on Operating Systems Principles (SOSP '15), Oct. 2015

Security

Wed 4/22

TBD

Fri 4/24

A. Baumann, M. Peinado, G. Hunt, Shielding Applications from an Untrusted Cloud with Haven, In Proceedings of the 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI '14), October 2014.

D.i.s.tri...buuuuuted Systems

Wed 4/29

J. Dean and S. Ghemawat, MapReduce: Simplified Data Processing on Large Clusters, In Proceedings of the 6th Symposium on Operating Systems Design and Implementation (OSDI '04), December 2004. P. Moritz, R. Nishihara, S. Wang, A. Tumanov, R. Liaw, E. Liang, M. Elibol, Z. Yang, W. Paul, M.I. Jordan, I. Stoica, Ray: A Distributed Framework for Emerging AI Applications, In Proceedings of the 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI '18), October 2018.

New Application

Fri 5/1

W. Kwon, Z. Li, S. Zhuang, Y. Sheng, L. Zheng, C.H. Yu, J. Gonzalez, H. Zhang, I. Stoica, Efficient Memory Management for Large Language Model Serving with PagedAttention, In Proceedings of the 29th Symposium on Operating Systems Principles (SOSP '23), October 2023.

The Future of OS

Wed 5/2

B. W. Lampson and H. E. Sturgis, Reflections on an Operating System Design, In Proceedings of the 5th ACM Symposium on Operating System Principles (SOSP '75), October 1975. B. W. Lampson, Hints for Computer System Design, In Proceedings of the 9th ACM Symposium on Operating Systems Principles (SOSP '83), October 1983. A. S. Tanenbaum and J. N. Herder, and H. Bos, Can We Make Operating Systems Reliable and Secure? IEEE Computer, Vol. 29, No. 5, pp. 44-51, May 2006. K. Thompson, Reflections on Trusting Trust, Communications of the ACM, Vol. 27, No. 8, August 1984, pp. 761-763.