Skip to content

CS202 Advanced Operating Systems (2022, Winter)

Time: TuTh 2p-3:20p

Live at Materials Sci and Engineering | Room 103
You may also find us on YouTube

Instructor

Hung-Wei Tseng
email: htseng @ ucr.edu
Office Hours: MTu 11a-12p (Please check Google Calendar events for detail)

Teaching Assistant

Yu-Chia Liu
e-mail: yliu719 @ ucr.edu
Office Hours: W 2p-3p & F 11a-12p (Please check Google Calendar events for detail)

Quizzes, Assignments, Grading: eLearn
Discussion Forum on Piazza: https://piazza.com/class/kxgldzml6k71g2
Youtube Channel: https://www.youtube.com/profusagi

Calendar

Course Overview

This course will describe the principles of designing operating systems. Topics include multithreading, synchronization, scheduling, virtual memory, and distributed systems including clusters. This course will be based on textbook & paper readings, paper discussions, projects, a final exam and in-class participation. The purpose of this course is to teach computer software system structures from a design point of view. We will look at different structuring techniques, and we will examine their usage in both important historical systems and in modern systems. In addition to learning about different system structures and different operating systems, you will learn:

  • How to read a research paper in an objective manner.
  • How to articulate your understanding of and insights into a research paper.
  • How to synthesize research themes and topics across multiple papers.
  • How to apply paper ideas into real systems.

Textbook

Operating Systems: Three Easy Pieces
Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau
Arpaci-Dusseau Books March, 2018 (Version 1.00)  (free online textbook at http://pages.cs.wisc.edu/~remzi/OSTEP/)

Grading

  • 40% Final
  • 20% Midterm
    We will have a take-home midterm
  • 25% Project
    • We will have one coding project, using pure C programming language, throughout the quarter. It’s due 3/3/2022. Do not expect any extension on the deadline! We’re in quarter systems.
    • Please check the project detail on https://github.com/hungweitseng/CS202-MMA/
  • 15% reading quizzes
    • We will have reading quizzes on eLearn!
    • Class participation (Zoom-poll Based), update every 4-5 lectures, count as 4 reading quizzes.
      • This class uses “peer instruction” and we encourage you to participate in Live Zoom sessions
      • You need to answer at least 50% of the poll questions to receive full credits on the class participation
  • Additional notes about grades in this course
    • Your score will be available on eLearn. Your final grade is the weighted average of these grades.
      We do our best to record grades accurately, but you should double-check.
    • Late submission: We do not accept any late submission, including quiz and projects.
    • Errors in grading: If you feel there has been an error in how an assignment or test was graded, you have one week from when the assignment is return to bring it to our attention. You must submit (via email to the instructor and the appropriate TAs) a written description of the problem. Neither I nor the TAs will discuss regrades without receiving an email from you about it first. For arithmetic errors (adding up points etc.) you do not need to submit anything in writing, but the one week limit still applies.
    • For exams: We do not regrade on a single problem. We will re-grade your whole test. The one week regrading window still applies.
    • Final grades: The final grading will be based on relative ranking of students in the class instead of absolute scale of grades. If you have a problem with your final grade in the course, send me email and we can set up an appointment to discuss it.

Project

Please visit the following link for the most update information regarding the project. We don’t answer questions related to the project during lectures. Please use office hours instead. Thanks for your understanding.

https://github.com/hungweitseng/CS202-MMA/blob/main/README.md

Schedule and Slides


TopicReadingPreviewSlides DueNote
1/4/2022Intro1 Introduction
1/6/2022The Structure of Operating Systems and the Abstraction of Processes – Arpaci-Dusseau Chapter 2, 4, 6 2 Fundamentals of OS

Demo		Reading Quiz #1
1/11/2022Design Philosophy of Operating Systems – E. W. Dijkstra. The Structure of the ‘THE’-Multiprogramming System. Communications of the ACM, Vol. 11, No. 5, May 1968, pp. 341-346.
Focusing on:
1. How “THE” structure the kernel/system?
2. The pros & cons of the proposed design
– P. B. Hansen. The Nucleus of a Multiprogramming System, Communications of the ACM, Vol. 13, No. 4, April 1970, pp. 238-241, 250.
Focusing on:
1. How “Nucleus” structure the system?
2. How does synchronization in the RC 4000 system compare with synchronization in the THE system?		THE/Nucleus (Preview)3 THE/NucleusReading Quiz #2
1/13/2022Design Philosophy of Operating Systems– D. M. Ritchie and K. Thompson. The UNIX Time-Sharing System, Communications of the ACM, Vol. 17, No. 7, July 1974, pp. 365-375.
Focusing on:
1. What UNIX proposed
2. Protection
3. The process API
UNIX/Mach (Preview)4 UNIX/Mach

Demo (setuid)

Demo (Shell)		Reading Quiz #3
1/18/2022Processes & Threads – Arpaci-Dusseau Chapter 5, 26–315 Mach/ThreadsReading Quiz #4
1/20/2022Processes & Threads– Accetta, Mike, Robert Baron, William Bolosky, David Golub, Richard Rashid, Avadis Tevanian, and Michael Young. Mach: A New Kernel Foundation For UNIX Development. Proc. USENIX Summer Conference, Atlanta, GA, 1986, pp. 93-112.
Focusing on: 
1. The structure of Mach kernel and compare it with other papers you read so far.
2. Tasks and threads
3. You may skip Section 4 and 5 for now — we will read another paper on this later		Synchronization (Preview)6 Mach/Threads/Synchronization

Demo (Thread Creation Overhead)
1/25/2022Synchronization– Maurice Herlihy, Wait-Free Synchronization, ACM Transactions on Programming Languages and Systems (TOPLAS), Vol. 13, No. 1, January 1991, pp. 124–149.
– Paul E. McKenney, Joel Fernandes, and Silas Boyd-Wickizer. RCU Usage In the Linux Kernel: Eighteen Years Later. ACM SIGOPS Operating Systems Review Vol. 54, No. 1, August 2020, pp. 47–63.
– (Optional) Paul E. McKenney, Dipankar Sarma, Andrea Arcangeli, Andi Kleen, Orran Krieger, and Rusty Russell. Read Copy Update. In Proceedings of the Ottawa Linux Symposium, June 2002, pp. 338–367.		7 SynchronizationReading Quiz #5
1/27/2022Virtual memory – Arpaci-Dusseau Chapter 7
– Corbató, Fernando J., Marjorie Merwin-Daggett, and Robert C. Daley. An experimental time-sharing system. In Proceedings of the May 1-3, 1962, spring joint computer conference (pp. 335-344).
Focusing on: The multi-level scheduling policy of the system
– Carl A. Waldspurger and William E. Weihl. Lottery Scheduling: Flexible Proportional-Share Resource Management. The First USENIX Symposium on Operating System Design and Implementation (OSDI), November, 1994.
Focusing on: Pros & Cons of Lottery
– 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.
– (Optional) Thomas E. Anderson, Brian N. Bershad, Edward D. Lazowska, Henry M. Levy. Scheduler Activations: Effective Kernel Support for the User-level Management of Parallelism. Proceedings of the 13th ACM Symposium on Operating Systems Principles (SOSP), Sept. 1991, pp. 95-109. 
Focusing on: 
1. The difference between kernel threads and user-level threads
2. What abstraction is proposed

Arpaci-Dusseau Chapter 13, 15, 16, 18 		Scheduling (Preview)8 Scheduling
2/1/2022Virtual memory Arpaci-Dusseau Chapter 20, 21, 22 Virtual Memory (Preview)9 Virtual Memory (1)Reading Quiz #6
2/3/2022Virtual memory – H. M. Levy and P. Lipman. Virtual Memory Management in VAX/VMS. IEEE Computer, Vol. 15, No. 3, March 1982, pp.35-41.
Focusing on:
1. What VAX/VMS proposed to address their design goals
2. The address mapping in VAX/VMS
– Richard Rashid, Avadis Tevanian, Michael Young, David Golub, Robert Baronn, David Black, William Bolosky, and Jonathan Chew. Machine-Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures. The Second International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), October 1987, pp. 31-39.
Focusing on:
1. Why machine-independent VM
2. What they proposed to make VM machine-independent 		VMS/Mach VM
(Preview)		10 The VM of VMS and Mach/Sample Midterm
2/8/2022Virtual memory – O. Babaoglu and W. Joy. Converting a Swap-Based System to do Paging in an Architecture Lacking Page-Reference Bits. Eighth ACM Symposium on Operating System Principles (SOSP), December 1981, 78-86.
Focusing on:
1. The page replacement policy and why this policy.
2. How they make the policy machine independent.
3. Why and What’s vfork? 
– R. Carr and J. Hennessy. WSCLOCK-A Simple and Effective Algorithm for Virtual Memory Management. Eighth ACM Symposium on Operating System Principles (SOSP), December 1981, 87-95.
Focusing on:
1. Why WSClock.
2. What is WS?
3. What is Clock?
4. What’s WSClock? 		11 Page Replacement Policies in Modern OSsReading Quiz #7
2/10/2022MidtermMidterm
Solution
2/15/2022File systems– Arpaci-Dusseau Chapter 36, 37, 39, 40, 41

– Jisoo Yang, Dave B. Minturn, and Frank Hady. When Poll is Better than Interrupt. 10th USENIX Conference on File and Storage Technologies (FAST 12).
Focusing on: When & why is polling better than interrupt		File Systems (Preview)12 Basics of I/O and File SystemsReading Quiz #8
2/17/2022 File systems– Marshall K. McKusick, William N. Joy, Samuel J. Leffler, and Robert S. Fabry. A Fast File System for Unix. ACM Transactions on Computer Systems, 2(3), August 1984, pp. 181-197.
Focusing on:
1. What are different between the old FS and FFS
2. Why they made such decisions

– Mendel Rosenblum and John K. Ousterhout. The Design and Implementation of a Log-Structured File System. The 13th ACM Symposium on Operating Systems Principles (SOSP), December 1991.
Focusing on:
1. Why we want log-structured file systems
2. What’s a log file system and How does it work?		FFS/LFS (Preview)13 FFS/LFS
2/22/2022Fast, non-volatile memory-based storage devices – Arpaci-Dusseau Appendix–Flash-based SSDs

– Michael Wu and Willy Zwaenepoel. eNVy: a non-volatile, main memory storage system. The sixth international conference on Architectural support for programming languages and operating systems (ASPLOS).
Focusing on:
1. How flash memory technologies are different from conventional hard drives
2. How eNVy addresses the different nature of flash

– Jingpei Yang, Ned Plasson, Greg Gillis, Nisha Talagala, and Swaminathan Sundararaman. Don’t stack your log on my log. 2nd Workshop on Interactions of NVM/Flash with Operating Systems and Workloads (INFLOW 14).
Focusing on:
1. Why do we have multiple logs in modern computer systems?
2. What problems they cause and how to address the problem.		Flash SSD/Log on Log (Preview)14 Extent File Systems/Flash SSD/Log on Log

Demo		Reading Quiz #9
2/24/2022Networked & cloud storage– Arpaci-Dusseau Chapter 49

– Sanjay Ghemawat, Howard Gobioff, Shun-Tak Leung. The Google File System. Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles (SOSP), October 2003, pp. 29–43.
Focusing on:
1. What are different between GoogleFS and conventional FS
2. Why they made such decisions 		Networked/Cloud Storage — NFS, Google FS, Azure, F4 (Preview)15 NFS/GFS
3/1/2022Networked & cloud storage– Brad Calder et al. Windows Azure Storage: A Highly Available Cloud Storage Service with Strong Consistency. Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles (SOSP), October 2011, pp. 143–157.
Focusing on:
1. Comparison between windows Azure Storage and GoogleFS
2. The consistency model in Windows Azure 		16 GFS/WASReading Quiz #10
3/3/2022Distributed systems – Subramanian Muralidhar et al. f4: Facebook’s Warm BLOB Storage System. 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI).
Focusing:
1. What’s the temperature of data
2. How they reduce overhead
– Luiz André Barroso, Jeffrey Dean, and Urs Hölzle. Web Search for a Planet: The Google Cluster Architecture. IEEE Micro, March 2003, 23(2): 22–28.
Focusing on: 
1. Why and how they use replications
2. How they use commodity parts? 		17 WAS/f4Project
3/8/2022Virtual machine – Arpaci-Dusseau Appendix–Virtual machines
– Keith Adams and Ole Agesen. A comparison of software and hardware techniques for x86 virtualization. The 12th international conference on Architectural support for programming languages and operating systems (ASPLOS).
Focusing on
1. How they achieve virtualization in x86
2. What supports the latest x86 provides for VMM?		Google Search (Preview)
Virtual Machine
(Preview)		18 Google Search/Virtual MachinesReading Quiz #11
3/10/2022Virtual machine– 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. The 19th Symposium on Operating System Principles (SOSP), October, 2003.
Focusing on: 
1. How Xen virtualize the hardware 
2. Why paravirtualization.?
– B. W. Lampson. Hints for computer system design. The Ninth ACM Symposium on Operating System Principles (SOSP), October 1983, pp. 33-48.
Focusing on:
1. How system design differs from algorithm design		19 Virtual Machines (cont.)/Hints for Computer System Design
3/11/2022– 3/17/2022Final ExamPart I: time limited — you can pick any 80-minute slot within this period to complete a set of multiple choice questions with explanations as well as free answer questions. For anyone who uses this class to fulfill the comprehensive exam purpose, those questions will be included in this part.

Part II: time unlimited — you can take the whole week to complete this set of “open-ended” questions. As they are open-ended, this set of questions will not have standard answers. They have some flavors of interview questions on system design and I believe it’s a very good training for you. You will need to reference papers you’ve read in this quarter or read more papers to support your thoughts.

Optional:

HYDRA: The Kernel of a Multiprocessor Operating System
Focusing on:
1. How “HYDRA” structure the kernel/system?
2. The pros & cons of the proposed design

Implementing Global Memory Management in a Workstation Cluster
Focusing on:
1. Why global memory management and what’s their goal?
2. How they take advantages from using idle resource (e.g. the policy)?

The Distributed V Kernel and its Performance for Diskless Workstations
Focusing on: What V uses IPC for and why?

The Sprite Network Operating System
Focusing on:
1. What’s RPC? Why do we need RPC for Sprite?
2. What changes Sprite made to UNIX? 

IX: A Protected Dataplane Operating System for High Throughput and Low Latency (2014)
Hints for computer system design
Focusing on:
1. How system design differs from algorithm design

Translation Caching: Skip, Don’t Walk (the Page Table)
Focusing on: 
1. the design of x86 page tables. 
2. Why we need PTCs

Monitors: An Operating System Structuring Concept
(Focus on 
1. what’s monitor
2. monitors v.s. semaphores)

Experience with Processes and Monitors in Mesa 
(Focus on 
1. the difference of Mesa’s monitor and the original monitor paper
2. why Mesa made such changes)