This schedule will likely change as the semester progresses. Please check frequently.

We will use portions of the following books:
  • "Operating Systems: Three Easy Pieces," Remzi Arpaci-Dusseau and Andrea Arpaci-Dusseau. Link (OS3)
  • "A Primer on Memory Consistency and Cache Coherence," Synthesis Lectures on Computer Architecture (Morgan and Claypool Publishers), Sorin, Hill, and Wood (SHW).
  • "Distributed Systems: Principles and Paradigms (2nd ed.)," Andrew S. Tanenbaum. (AST)
  • "Hadoop: A Definitive Guide" Tom White. (TW)
  • "Virtual Machines: Versatile Platforms for Systems and Processes (The Morgan Kaufmann Series in Computer Architecture and Design)," James Smith and Ravi Nair. (VM)
    Additionally, we will be using some research papers and online resources.

    Warning: Please exercise caution when using the notes I post on Angel. They may contain bugs (for which I take no responsibility) - they are just byproducts of my class preparation. They will certainly not contain all that is discussed in class. They are NOT a substitute for your own note-taking.

    Academic integrity: We will compare the code for your programming assignments with those of others. Cheating on a programming assignment will result in a grade F for all involved.

    Lec. no. Date Theme Specific topics Special remarks and announcements Reading material Pointers for further study
    1. 08/23 Introduction and overview Administration; course outline; recap of process v thread trade-offs Slides and notes posted on Angel Ch. 26 of OS3
    2. 08/25 Concurrency (1), advanced IO management Race conditions, classification of solution approaches, the mutual exclusion approach, progress conditions Notes posted on Angel, outline of Quiz 0 solutions posted on Angel Ch. 26 of OS3
    3. 08/30 Lock implementations (test&set, spinning/busy waiting, fetch&add/ticket lock) Notes posted on Angel Ch. 28 of OS3
    4. 09/01 Lock implementations (using FIFO queue to reduce spinning), deadlocks, simple examples of lock-free approaches Notes posted on Angel Ch. 28, portions of Ch. 29 and 32 of OS3
    5. 09/06 Non-blocking and asynchronous IO, event-driven programming PA1 release postponed! Ch. 33 of OS3
    6. 09/13 Preparation for programming assignments Tutorial on pthreads Slides posted on Angel; guest lecture by Neda Nasiriani (instructor on parental leave)
    7. 09/15 Tutorial on using Amazon EC2 instances Slides posted on Angel; guest lecture by Neda Nasiriani (instructor on parental leave)
    8. 09/20 Tutorial on basic programming tools Guest lecture by Zhixuan Huan (instructor on parental leave)
    9. 09/27 Concurrency (1)/IO Event-driven programming PA1 released!; notes posted on Angel Indicated portions of "Cooperative task management without manual stack management," Adya et al., USENIX 2002; indicated portions of "Flash: an efficient and portable web server," Pai et al., USENIX 1999 Node.js; "Scheduler activations: Effective kernel support for user-level management of parallelism," Anderson et al., ACM TOCS 10(1), 1992
    10. 09/29 event notification: select and RT signals Notes posted on Angel Indicated portions of "Scalability of Linux event-dispatch mechanisms," Chandra and Mosberger, USENIX 2001
    11. 10/04 Memory consistency, concurrency (2) Cache coherence Notes posted on Angel Ch. 2 of SHW
    12. 10/06 Memory consistency models (sequential and weak); lock implementations for uPs Notes posted on Angel Ch. 3.1-3.4 of SHW; "The performance of spin-lock alternatives for shared-memory multiprocessors," Anderson, IEEE TPDS 1(1), 1990 DSM implementations
    13. 10/11 Single machine Storage The crash consistency problem Notes posted on Angel; HW1 released (10/12) Ch. 42 of OS3
    14. 10/13 Journaling Notes posted on Angel Ch. 42 of OS3
    15. 10/25 Log-structured file systems Notes posted on Angel; HW1 due (in class) Ch. 43 of OS3
    E1. 10/26 Exam 1 073 Willard, 6:30-7:45pm
    16. 10/27 Distributed computing basics with case studies Lamport and vector clocks Notes posted on Angel; (10/29): PA1 due "Time, clocks, and ordering of events in a distributed system," Lamport, CACM 1978
    17. 11/01 Applications of logical time: distributed mutex, sequential consistency, crash fault tolerance via temporal redundancy - distributed snapshots Notes posted on Angel "Distributed snapshots: determining global states of distributed systems," Chandy and Lamport, ACM TOCS 1985
    18. 11/03 Consensus and examples; ACID and distributed commit (2PC) Notes posted on Angel Indicated portions of "Consensus on transaction commit," by Gray and Lamport
    19. 11/08 Crash fault tolerance via spatial redundancy - primary-backup, SMR, quorums, FLP PA2 released!
    20. 11/17 Last process standing, 2-General's, Byzantine failures and lower bound on number of replicas Notes posted on Angel Indicated portions of "Byzantine Generals Problem," Lamport, Shostak, and Pease, ACM TOPLAS 1982.
    21. 11/29 CAP and PACELC Notes posted on Angel; HW2+3 release date "Consistency tradeoffs in modern distributed database system design," Abadi, IEEE Comp. Soc., Feb. 2012
    22. 12/01 Causal and eventual consistency Notes posted on Angel "A short primer on causal consistency," Lloyd et al., ;login: Vol 38, No. 4, Aug 2013
    23. 12/06 Scheduling Single CPU or NIC scheduling: PF and MMF definitions, SFQ; Token bucket regulation Notes posted on Angel
    24. 12/07 Virtual machines Notes posted on Angel; Room 222 IST Chapters 1 and 8 of VM
    25. 12/08 Multi-processor scheduling: note on infeasibility of PF weights Notes posted on Angel; HW2+3 due (12/09)
    E2. 12/13 Exam 2 208 Ford Bldg., 2:30-4:20pm PA2 due (12/15)