CS 523: Schedule and Readings

Fall 2019

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

Week 14

Week 15

Week 16

8/28
8/30

9/4
9/6

9/11
9/13

9/18
9/20

9/25
9/27

10/2
10/4

10/9
10/11

10/16
10/18

10/23
10/25

10/30
11/1

11/6
11/8

11/13
11/15

11/20
11/22

Fall
Break

12/4
12/6

12/11

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

Course Overview

Wed
8/28

Course Overview

Historical Perspectives

Fri
8/30

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

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

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

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

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

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

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.

S. Park, Y. Zhou, W. Xiong, Z. Yin, R. Kaushik, K. H. Lee, and S. Lu, PRES: Probabilistic Replay with Execution Sketching on Multiprocessors, In Proceedings of the 22nd ACM Symposium on Operating Systems Principles (SOSP '09), October 2009.
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.

Wed
9/25

M. Herlihy and J. E. B. Moss, Transactional Memory: Architectural Support for Lock-free Data Structures, In Proceedings of the 20th Annual International Symposium on Computer Architecture (ISCA '93), May 1993.
- M. Herlihy, Wait-Free Synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), Vol. 13 No. 1, Jan. 1991, pp. 124-149.
C. J. Rossbach, O. S. Hofmann, D. E. Porter, H. E. Ramadan, A. Bhandari, and E. Witchel, TxLinux: Using and Managing Hardware Transactional Memory in an Operating System, In Proceedings of 21th ACM SIGOPS symposium on Operating Systems Principles (SOSP '07), October 2007.

Scheduling

Fri
9/27

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), November 1994.
- C. A. Waldspurger and W. E. Weihl, Stride Scheduling: Deterministic Proportional-Share Resource Management, Technical Memorandum MIT/LCS/TM-528, June 1995.
- D. Petrou, J. W. Milford, G. A. Gibson, Implementing Lottery Scheduling: Matching the Specializations in Traditional Schedulers, In Proceedings of the USENIX Annual Technical Conference, June 1999.
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.
- M. Jones, Inside the Linux 2.6 Completely Fair Scheduler, IBM Tutorial, September 2018.

Process and Thread

Wed
10/2

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. Litton, A. Vahldiek-Oberwagner, E. Elnikety, D. Garg, B. Bhattacharjee, and Peter Druschel, Light-weight Contexts: An OS Abstraction for Safety and Performance, In Proceedings of the 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI '16). November 2016.

Memory Management

Fri
10/4

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

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

Hack Day

Fri
10/11

Please focus on your Checkpoint #1

Memory Management (Cont.)

Wed
10/16

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

Virtualization

Fri
10/18

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

Wed
10/23

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

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.

Hack Day

Wed
10/30

Project, project, project!!

Storage and File Systems (Cont.)

Fri
11/1

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.
- M. K. McKusick and S. Quinlan, GFS: Evolution on Fast-forward, ACM Queue, August 2009.
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/6

J. Dean and S. Ghemawat, MapReduce: Simplified Data Processing on Large Clusters,, In Proceedings of the 6th Symposium on Operating System Design and Implementation (OSDI'04), December 2004.
F. Chang et al., BigTable: A Distributed Storage System for Structured Data, In Proceedings of the 7th Symposium on Operating System Design and Implementation (OSDI'06), November 2006.
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.
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.

Protection

Fri
11/8

B. Lampson, Protection, Operating Systems Review, Vol. 8, No. 1, January 1974, pp. 18-24.
J. H. Saltzer, Protection and the Control of Information Sharing in Multics , In Proceedings of 4th ACM Symposium on Operating System Principles (SOSP '73), October 1973.
- B. Lampson, Practical Principles for Computer Security, August 2006.
- B. Lampson, Perspectives on Security, SOSP History Day, October 2015.

Security (Guest Lecture)

Wed
11/13

Dimitrios Skarlatos

MicroScope: Enabling Microarchitectural Replay Attacks

Hack Day

Fri
11/15

Please focus on your Checkpoint #2

Reliability

Wed
11/20

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.
- A. Kadav, M. J. Renzelmann, and M. M. Swift, Tolerating Hardware Device Failures in Software, In Proceedings of the 22nd ACM Symposium on Operating Systems Principles (SOSP '09), October 2009.
- A. Kadav and M. M. Swift, Understanding Modern Device Drivers, In Proceedings of the 17th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '12), March, 2012.
- M. J. Renzelmann, A. Kadav, and M. M. Swift, SymDrive: Testing Drivers without Devices, In Proceedings of the 12th Symposium on Operating System Design and Implementation (OSDI '12), October 2012.
F. Qin, J. Tucek, J. Sundaresan and Y. Zhou, Rx: Treating Bugs As Allergies — A Safe Method to Survive Software Failures, In Proceedings of the 20th ACM Symposium on Operating Systems Principles (SOSP '05), October 2005.
- 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.

Office Hour

Fri
11/22

We will use the class as an office hour to discuss the course projects so that we know what to work on during the Fall break :)

Mobile Systems

Wed
12/4

Wenyu Wang will give us an overview of the Android mobile system.
W. Enck, P. Gilbert, B. G. Chun, L. P. Cox, J. Jung, P. McDaniel, A. N. Sheth, TaintDroid: An Information-Flow Tracking System for Realtime Privacy Monitoring on Smartphones, In Proceedings of the 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI '10), October 2010.
J. Andrus, C. Dall, A. V. Hof, O. Laadan, and J. Nieh, Cells: A Virtual Mobile Smartphone Architecture, In Proceedings of the 23th ACM Symposium on Operating Systems Principles (SOSP '11), October 2011.

Qual

Fri
12/6

P. Efstathopoulos, M. Krohn, S. VanDeBogart, C. Frey, D. Ziegler, E. Kohler, D. Mazieres, F. M. Kaashoek, and R. Morris, Labels and Event Processes in the Asbestos Operating System, In Proceedings of the 20th ACM Symposium on Operating System Principles (SOSP '05), October 2005.
J. Yang, P. Twohey, D. Engler, and M. Musuvathi, Using Model Checking to Find Serious File System Errors, In Proceedings of the 6th Symposium on Operating Systems Design and Implementation (OSDI '04), December 2004.

Closing

Wed
12/11

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.