CS202 Advanced Operating Systems

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:

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

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)