CS202 Advanced Operating Systems (2021, Winter)

Instructor

Hung-Wei Tseng
email: htseng @ ucr.edu
Office Hours: M 3p-4p, Th 9a-10a on Zoom

Other important links

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

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, 2015 (Version 0.90)  (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/2/2021. Do not expect any extension on the deadline! We’re in quarter systems.
    • Please check the project detail on GitHub.
  • 15% reading quizzes
    • We will have reading quizzes on iLearn!
    • 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 iLearn. 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, assignments, 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 check the project detail on GitHub

Schedule and Slides


TopicReadingPreviewSlides DueNote
1/5/2021IntroIntro
1/7/2021The Structure of Operating Systems and the Abstraction of Processes Arpaci-Dusseau Chapter 2, 4, 6 Process/Virtualization (Preview)Process/Virtualization

Demo (process virtualization)
Reading Quiz #1
1/12/2021Design Philosophy of Operating Systems The Structure of the ‘THE’-Multiprogramming System
Focusing on:
1. How “THE” structure the kernel/system?
2. The pros & cons of the proposed design
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
THE/HYDRA (Preview)THE/HYDRAReading Quiz #2
1/14/2021Design Philosophy of Operating SystemsThe UNIX Time-Sharing System
Focusing on:
1. What UNIX proposed
2. Protection
3. The process API
Mach: A New Kernel Foundation For UNIX Development
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
UNIX/Mach
(Preview)
UNIX

Demo (setuid)
Reading Quiz #3
1/19/2021Processes & Threads Arpaci-Dusseau Chapter 5, 26, 27 Processes/Mach/Threads
(Preview)
Process API/Mach

Demo my (shell)
Reading Quiz #4
1/21/2021Processes & Threads Arpaci-Dusseau Chapter 7, 28, 29, 30, 31 Mach & Threads (Preview)
1/26/2021Processes/Threads Scheduling An experimental time-sharing system
Focusing on: The multi-level scheduling policy of the system
Lottery Scheduling: Flexible Proportional-Share Resource Management.
Focusing on: Pros & Cons of Lottery
Scheduler Activations: Effective Kernel Support for the User-level Management of Parallelism 
Focusing on: 
1. The difference between kernel threads and user-level threads
2. What abstraction is proposed
Process/Thread Scheduling
(Preview)
Process/Thread SchedulingReading Quiz #5

Project Released
1/28/2021Virtual memory Arpaci-Dusseau Chapter 13, 15, 16, 18 Virtual Memory
(Preview)
Thread Scheduling & Virtual Memory
2/2/2021Virtual memory Arpaci-Dusseau Chapter 20, 21, 22 Virtual Memory (II)

Project (Video)
Project (Slides)
Reading Quiz #6
2/4/2021Virtual memory Virtual Memory Management in VAX/VMS
Focusing on:
1. What VAX/VMS proposed to address their design goals
2. The address mapping in VAX/VMS
Machine-Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures
Focusing on:
1. Why machine-independent VM
2. What they proposed to make VM machine-independent
VAX/VMS & Mach VM (Preview)VAX/VMS & Mach VM

Demo (Linux Kernel Memory)
2/9/2021Virtual memory Converting a Swap-Based System to do Paging in an Architecture Lacking Page-Reference Bits
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? 
WSCLOCK-A Simple and Effective Algorithm for Virtual Memory Management
Focusing on:
1. Why WSClock.
2. What is WS?
3. What is Clock?
4. What’s WSClock?
Clock and WS Clock (Preview)Clock and WSClock and Sample MidtermReading Quiz #7
2/11/2021No lecture: time for the midtermMidterm Due 2/15/2021
2/16/2021File systemsArpaci-Dusseau Chapter 36, 37, 39, 40, 41

When Poll is Better than Interrupt
Focusing on: When & why is polling better than interrupt
File system (Preview)The Basics of I/O & File Systems
2/18/2021 File systemsA Fast File System for Unix
Focusing on:
1. What are different between the old FS and FFS
2. Why they made such decisions

The Design and Implementation of a Log-Structured File System
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)FFS/LFSReading Quiz #8
2/23/2021Fast, non-volatile memory-based storage devices Arpaci-Dusseau Appendix–Flash-based SSDs

eNVy: a non-volatile, main memory storage system
Focusing on:
1. How flash memory technologies are different from conventional hard drives
2. How eNVy addresses the different nature of flash

Don’t stack your log on my log
Focusing on:
1. Why do we have multiple logs in modern computer systems?
2. What problems they cause and how to address the problem.
File Systems and Flash SSDs (Previews)Modern File Systems & Flash Memory
2/25/2021Networked & cloud storageArpaci-Dusseau Chapter 49

The Google File System
Focusing on:
1. What are different between GoogleFS and conventional FS
2. Why they made such decisions
NFS/GFS
(Preview)
NFS/GFS (Preview)Reading Quiz #9
3/2/2021Networked & cloud storageWindows Azure Storage: A Highly Available Cloud Storage Service with Strong Consistency
Focusing on:
1. Comparison between windows Azure Storage and GoogleFS
2. The consistency model in Windows Azure
f4: Facebook’s Warm BLOB Storage System
Focusing:
1. What’s the temperature of data
2. How they reduce overhead
WAS/F4 (Preview)GFS/WASProject
3/4/2021Distributed systems Web Search for a Planet: The Google Cluster Architecture
Focusing on: 
1. Why and how they use replications
2. How they use commodity parts?
Google Search
(Preview)
WAS/f4 (cont.)Reading Quiz #10
3/9/2021Virtual machine Arpaci-Dusseau Appendix–Virtual machines
A comparison of software and hardware techniques for x86 virtualization
Focusing on
1. How they achieve virtualization in x86
2. What supports the latest x86 provides for VMM?
Virtual Machines (Preview)F4/Google Search/Virtual Machine
3/11/2021Virtual machineXen and the Art of Virtualization
Focusing on: 
1. How Xen virtualize the hardware 
2. Why paravirtualization.?
Hints for computer system design
Focusing on:
1. How system design differs from algorithm design
Virtual Machines & Reflections
3/13/2021 8am
-3/17/2021
4pm
Final Exam

Optional:

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)