CS 523: Schedule and Readings (Tentative)

Fall 2021

Week 1

Week 2

Week 3

Week 4

Week 5

Week 6

Week 7

Week 8

Week 9

Week 10

Week 11

Week 12

Week 13

Fall Break

Week 14

Week 15

8/25
8/27

9/1
9/3

9/8
9/10

9/15
9/17

9/22
9/24

9/29
10/1

10/6
10/8

10/13
10/15

10/20
10/22

10/27
10/29

11/3
11/5

11/10
11/12

11/17
11/19

12/1
12/3

12/8

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

Course Overview

Wed
8/25

Course Overview (I)

Wed
8/27

Course Overview (II)

Historical Perspectives

Wed
9/1

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.

Fri
9/3

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)

Wed
9/8

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

Fri
9/10

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

Wed
9/15

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

Fri
9/17

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

Wed
9/22

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),

Proposal Reading Section

Fri
9/24

We will read and comment a few selected project proposals.

Hacker's Day

Wed
9/29

No class; hack your project.

Memory Management

Fri
10/1

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.

Wed
10/6

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

Fri
10/8

A. Basu, J. Gandhi, J. Chang, M. D. Hill, and M. M. Swift, Efficient Virtual Memory for Big Memory Servers, In Proceedings of the 40th Annual International Symposium on Computer Architecture (ISCA '13), June 2013.
- J. Gandhi, A. Basu, M. D Hill, and M. M. Swift, Efficient Memory Virtualization: Reducing Dimensionality of Nested Page Walks, In Proceedings of the 47th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-47), December 2014.
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.
- 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"

Wed
10/13

R. Bhargava, B. Serebrin, F. Spadini, and S. Manne, Accelerating Two-Dimensional Page Walks for Virtualized Systems, In Proceedings of the 13th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-XIII), March 2008.
J. Gandhi, M. D. Hill, M. M. Swift Agile Paging: Exceeding the Best of Nested and Shadow Paging, In Proceedings of the 43rd International Symposium on Computer Architecture (ISCA '16), June 2016.

Fri
10/15

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
10/20

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.

SOSP Party Preparation

Fri
10/22

How (and how not) to attend SOSP?

SOSP

Wed
10/27

Party time

Fri
10/29

Party time

Storage and File Systems

Wed
11/3

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.

Fri
11/5

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.

Wed
11/10

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.

Project Reading Section II

Fri
11/12

We will read and comment a few selected checkpoint-1 reports.

Distributed Systems

Wed
11/17

D. R. Cheriton and W. Zwaenepoel, The Distributed V Kernel and its Performance for Diskless Workstations, In Proceedings of the 9th Symposium on Operating Systems Principles (SOSP '83), November 1983.
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.
- A Brief Retrospective on the Sprite Network Operating System

Fri
11/19

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.

Reliability

Wed
12/1

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
12/3

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.

Closing

Wed
12/8

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.