CS 523: Schedule and Readings (Tentative)

Spring 2023

Week 1

Week 2

Week 3

Week 4

Week 5

Week 6

Week 7

Week 8

Spring Break

Week 9

Week 10

Week 11

Week 12

Week 13

Week 14

Week 15

1/18
1/20

1/25
1/27

2/1
2/3

2/8
2/10

2/15
2/17

2/22
2/24

3/1
3/3

3/8
3/10

3/22
3/24

3/29
3/31

4/5
4/7

4/12
4/14

4/19
4/21

4/26
4/28

5/3

This page conforms to the FERPA policy of disclosure of education records.

Course Overview

Wed
1/18

Course Overview

Historical Perspectives

Fri
1/20

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/25

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.

Unix and Plan 9 (and MINIX and Linux)

Fri
1/27

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/1

J. Liedtke, Improving IPC by Kernel Design, In Proceedings of the 14th ACM Symposium on Operating Systems Principles (SOSP '93), December 1993.
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, 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/3

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.
A. Baumann, M. Peinado, and 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.
- 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/8

C. A. R. Hoare, Monitors: An Operating System Structuring Concept, Communications of the ACM, Vol. 17, No. 10, October 1974, pp. 549-557.
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.
- 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.

Scheduling

Fri
2/10

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-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.
- C. A. Waldspurger and W. E. Weihl, Lottery Scheduling: Flexible Proportional-Share Resource Management, In Proceedings of the 1st USENIX Symposium on Operating System Design and Implementation (OSDI '94),

Memory Management (1)

Wed
2/15

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.
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.
- 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.

Guest Lecture: The Reliability of Cloud Infrastructures (Xudong Sun)

Fri
2/17

B. Burns, B. Grant, D. Oppenheimer, E. Brewer, and J. Wilke, Borg, Omega, and Kubernetes, Communications of the ACM, 59(5):50-57, May 2016.
X. Sun, W. Luo, J. T. Gu, A. Ganesan, R. Alagappan, M. Gasch, L. Suresh, and T. Xu, Automatic Reliability Testing for Cluster Management Controllers, In Proceedings of the 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI '22), July 2022.

Proposal Reading Section

Wed
2/22

We will read and discuss the project proposals.

Fri
2/24

We will read and discuss the project proposals.

Memory Management (2)

Wed
3/1

Y. Kwon, H. Yu, S. Peter, C. J. Rossbach, and E. Witchel, Coordinated and Efficient Huge Page Management with Ingens, In Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI '16), November 2016.
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.
- 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.
- J. Navarro, S. Iyer, P. Druschel, and A. Cox, Practical, transparent operating system support for superpages, In Proceedings of the 5th USENIX Symposium on Operating Systems Design and Implementation (OSDI '02), December 2002.
- A. Panwar, A. Prasad, and K. Gopinath, Making Huge Pages Actually Useful, In Proceedings of the 23rd International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '18), March 2018.

"Virtual Machines"

Fri
3/3

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.
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.
- 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.

Wed
3/8

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.

Storage and File Systems (1)

Fri
3/10

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. 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. 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
- V. Aurora, Log-structured file systems: There's one in every SSD, LWN.net, September 2009.

Checkpoint-1 Reading Section

Wed
3/22

We will read and discuss the checkpoint-1 report.

Fri
3/24

We will read and discuss the checkpoint-1 report.

Storage and File Systems (2)

Wed
3/29

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.
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.

"Cloud" Systems

Fri
3/31

L. A. Barroso, J. Dean, and U. Hölzle, Web Search for a Planet: The Google Cluster Architecture, IEEE Micro, March 2003, 23(2): 22–28.
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.

Wed
4/5

S. Ghemawat, H. Gobioff, and S-T. Leung, The Google File System, In Proceedings of the 19th ACM Symposium on Operating Systems Principles (SOSP '03), October 2003.
D. Beaver, S. Kumar, H. C. Li, J. Sobel, and P. Vajgel, Finding a needle in Haystack: Facebook’s photo storage, In Proceedings of the 9th Symposium on Operating Systems Design and Implementation (OSDI '10), October 2010.
- B. Calder et al., Windows Azure Storage: A Highly Available Cloud Storage Service with Strong Consistency, In Proceedings of the 23rd ACM Symposium on Operating Systems Principles (SOSP '11), October 2011.
- G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels, Dynamo: Amazon's Highly Available Key-value Store, In Proceedings of the 21st Symposium on Operating Systems Principles (SOSP '07), December 2007.

New Applications

Fri
4/7

M. Shahrad, R. Fonseca, I. Goiri, G. Chaudhry, P. Batum, J. Cooke, E. Laureano, C. Tresness, M. Russinovich, and R. Bianchini, Serverless in the Wild: Characterizing and Optimizing the Serverless Workload at a Large Cloud Provider, In Proceedings of the 2020 USENIX Annual Technical Conference (ATC '20), July, 2020.
J. Stojkovic, T. Xu, H. Franke, and J. Torrellas, SpecFaaS: Accelerating Serverless Applications with Speculative Function Execution, In Proceedings of the 29th IEEE International Symposium on High-Performance Computer Architecture (HPCA-29),Feb 2023.
- E. Jonas et al., Cloud Programming Simplified: A Berkeley View on Serverless Computing, Technical Report No. UCB/EECS-2019-3, Feb 2019.
- J. Schleier-Smith et al., What Serverless Computing Is and Should Become: The Next Phase of Cloud Computing, Communications of the ACM, May 2021, Vol. 64 No. 5, Pages 76-84.

Wed
4/12

M. Zaharia, M. Chowdhury, T. Das, A. Dave, J. Ma, M. McCauley, M. J. Franklin, S. Shenker, and I. Stoica, Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing, In Proceedings of the 9th USENIX Symposium on Networked Systems Design and Implementation (NSDI '12), Apr. 2012.
P. Moritz, R. Nishihara, S. Wang, A. Tumanov, R. Liaw, E. Liang, M. Elibol, Z. Yang, W. Paul, M. I. Jordan, and 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), Oct. 2018.

Fri
4/14

W. Enck, P. Gilbert, B. -G. Chun, L. P. Cox, J. Jung, P. McDaniel, and A. N. Sheth, TaintDroid: An Information-Flow Tracking System for Realtime Privacy, In Proceedings of the 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI '10), Oct. 2010.
P. Huang, T. Xu, X. Jin, and Y. Zhou, DefDroid: Towards a More Defensive Mobile OS Against Disruptive App Behavior, In Proceedings of the 14th International Conference on Mobile Systems, Applications, and Services (MobiSys '16), Jun 2016.

Reliability

Wed
4/19

M. Swift, B. N. Bershad, and H. M. Levy, Improving the Reliability of Commodity Operating Systems, In Proceedings of the 19th ACM Symposium on Operating Systems Principles (SOSP '03), October 2003.
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.

Protection

Fri
4/21

B. Lampson, Protection, SIGOPS Review, Vol. 8, No. 1, January 1974, pp. 18-24.
J. H. Saltzer and M. D. Schroeder, The Protection of Information in Computer Systems, In Proceedings of 4th ACM Symposium on Operating System Principles (SOSP '73), October 1973.

Project Reading Section II

Wed
4/26

We will read and comment the checkpoint-2 reports.

Fri
4/28

We will read and comment the checkpoint-2 reports.

Closing

Wed
5/3

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.