CS202 Advanced Operating Systems (2020, Winter)

Instructor

Hung-Wei Tseng
email: htseng @ ucr.edu
Office Hours: WTh 1p-2p @ WCH 406

Teaching Assistant

Zhenxiao Qi
email: zqi020 @ ucr.edu
Office hours: TuF 4p-5p @ WCH 110

Other important links

Quizzes, Assignments, Gradeing: iLearn
Discussion Forum on Piazza: https://piazza.com/class/k53188n4ht71em
Podcasting: 

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
  • 20% Project
    We will have one coding project, using pure C programming language, throughout the quarter. It’s going to be a contest and you will win a prize over it!
  • 10% Class participation
    This class uses “peer instruction” and we REQUIRE each of you to download poll everywhere App or navigate/login to their website during the class
  • 10% reading quizzes
    We will have reading quizzes on iLearn!
  • 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.

Schedule and Slides


TopicReadingPreviewSlides DueNote
1/7/2020IntroIntroduction
1/9/2020 The Structure of Operating Systems and the Abstraction of Processes Arpaci-Dusseau Chapter 2, 4, 6 Virtualization/Process (Preview)Virtualization/Process
Demo		Reading Quiz #1
1/14/2020Design 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/16/2020Design 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 & MachReading Quiz #3
1/21/2020Processes & Threads Arpaci-Dusseau Chapter 5, 26, 27 Processes & Threads (Preview)Mach & Processes/ThreadsReading Quiz #4
1/23/2020Processes & Threads Arpaci-Dusseau Chapter 7, 28, 29, 30, 31 Processes & Threads

Demo
1/28/2020Processes/Threads Scheduling An experimental time-sharing system
Focusing on: The multi-level scheduling policy of the system		Process Scheduling (Preview)Basic Scheduling & MLQReading Quiz #5
1/30/2020Virtual memory 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

Arpaci-Dusseau Chapter 13, 15, 16, 18 		Virtual Memory
(Preview)		Process/Thread Scheduling & Virtual Memory
2/4/2020Virtual memory Arpaci-Dusseau Chapter 20, 21, 22 Virtual Memory (II)Reading Quiz #6
2/6/2020Virtual 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 		Swapping/VMS/MachVM
(Preview)		Swapping/VMS

Demo
2/11/2020Virtual 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? 		Page Replacement Policies (Preview)Page replacement policiesReading Quiz #7
2/13/2020File systems Arpaci-Dusseau Chapter 36, 37, 39, 40, 41 File System Basics (Preview)I/O & File System Basics
2/18/2020File systems A 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? 		File Systems: Case Studies (Preview)Fast File System & Log-structured File systemReading Quiz #8
2/20/2020Fast, 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. 		Flash SSD (Preview)Flash SSD & File System
2/25/2020CancelledMidterm Due
2/27/2020Networked & 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 & Google FS (Preview)NFS & GFSReading Quiz #9
3/3/2020Networked & 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 & WAS Project
3/5/2020Distributed 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?

Arpaci-Dusseau Appendix–Virtual machines		Google Search & Virtual Machine (Preview)Facebook Storage & Google Search Reading Quiz #10
3/10/2020Virtual machine
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?
Hints for computer system design
Focusing on:
1. How system design differs from algorithm design		Virtual Machines & Hints for Computer System Design & Final Exam Tips
3/12/2020Canceled
3/14/2020 8am
-3/15/2020 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? 

Xen and the Art of Virtualization
Focusing on: 
1. How Xen virtualize the hardware 
2. Why paravirtualization.?

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

When Poll is Better than Interrupt
Focusing on: When & why is polling better than interrupt

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)