CS 523: Schedule and Readings (Tentative)

Fall 2020

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/26
8/28

9/2
9/4

9/9
9/11

9/16
9/18

9/23
9/25

9/30
10/2

10/7
10/9

10/14
10/16

10/21
10/23

10/28
10/30

11/4
11/6

11/11
11/13

11/18
11/20

12/2
12/4

12/9

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

Course Overview

Wed
8/26

Course Overview

Historical Perspectives

Fri
8/28

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
9/2

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
9/4

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

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
9/11

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. 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.
- A. Madhavapeddy and D. J. Scot, Unikernels: The Rise of the Virtual Library Operating System, Communications of the ACM, January 2014, Vol. 57 No. 1, pp. 61-69.
- The Mirage OS Project

Synchronization

Wed
9/16

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.

Fri
9/18

S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson, Eraser: A Dynamic Data Race Detector for Multi-Threaded Programs, In Proceedings of the 16th ACM Symposium on Operating Systems Principles (SOSP '97), October 1997.
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.

Proposal Reading Section

Wed
9/23

We will read and comment a few selected project proposals.

Fri
9/25

We will read and comment a few selected project proposals.

Scheduling

Wed
9/30

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

Fri
10/2

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

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

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 Machine and Container

Wed
10/14

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.

Fri
10/16

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.

Checkpoint-1 Presentation Section

Wed
10/21

You will deliver the Checkpoint-1 presentation.

Fri
10/23

You will deliver the Checkpoint-1 presentation.

Hack Day

Wed
10/28

Discuss your project with the team and the TAs.

Storage and File Systems

Fri
10/30

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.

Wed
11/4

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.

Fri
11/6

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.

Distributed Systems

Wed
11/11

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

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.

Project Reading Section III

Wed
11/18

We will read and comment a few selected project reports.

Fri
11/20

We will read and comment a few selected project reports.

Protection

Wed
12/2

B. Lampson, Protection, Operating Systems 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.

Reliability

Fri
12/4

Xudong Sun will lead the discussion.
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.

Closing

Wed
12/9

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.