COMS W4118 Operating Systems I

Fall 2020

W 4:10pm-6:40pm
Instructor: Jae Woo Lee
Office hours:
- Jae’s office hours
- TA office hours
REQUIRED READING: ACADEMIC HONESTY POLICIES

Exam dates

Two online but synchronous exams

Wed 10/28, 4:10pm: Midterm exam
Wed 12/23, 4:10pm: Final exam

There are no make-up or altenate exams. If you cannot make any of those exams, please take the course next semester.

HW due dates

F 9/11	HW0 due
Su 9/20	HW1 due
Su 10/4	HW3 due
Su 10/11	HW4 due
Su 10/25	HW5 Fridge due
W 10/28	Midterm exam
Su 11/15	HW6 Freezer due
Su 11/22	HW7 Cabinet due
~~Su 12/13~~ W 12/16 (hard deadline)	HW8 Pantry due
W 12/23	Final exam

Syllabus

9/9

Course overview and logistics

Lecture:
- L00-overview
Assignments:
1. Subscribe to 4118 ListServ – see L00 above for detail
2. Read the following two documents:
  - http://www.cs.columbia.edu/education/honesty
  - http://www.cs.columbia.edu/~jae/honesty.html
3. HW0 (50 points, individual assignment) – due Fri 9/11, 11:59pm
  
  Send me an email containing:
  - Subject: “[4118] hw0-UNI” – without quotes, sole space before hw0, UNI replaced with your actual UNI in lowercase
  - Your name, major & school program, year – ex) Jae Woo Lee, Physics, Columbia College, class of 1994
  - Your pledge – see http://www.cs.columbia.edu/~jae/honesty.html
  - CS classes taken and/or other programming background
  - Optionally anything else you want to let me know
  - Optionally attach a picture of you, but please reduce image file size to about 100KB
4. HW1 (100 points, individual assignment) – due Sun, 9/20, 11:59pm
  - see details below
5. Reading assignment:
  - APUE: chapter 1, 2.3, 2.4
  - OSTEP: chapter 2
  - LKD: chapter 1
6. Start forming your group of three people

Introduction to UNIX

Lecture:
- L01-unix-intro

HW1: VM Setup & Linux Linked List

Individual assignment, 100 points, due Sun 9/20
- Part A: Setup Debian Linux VM
- Part B: Linux Linked List

9/16

Linux System Overview

Lecture:
- L02-boot-to-panic
- Source code

UNIX File I/O

Reading:
- APUE 3.1 - 3.13
- APUE 8.1 - 8.10
Lecture:
- L03-file-io
- Source code

HW2

There is no HW2
- Just like Windows 9 :)
- A couple of years ago, I removed one of the earlier assignments. Instead of shifting the rest of the assignments by one, I decided to skip HW2 to make it easier on the teaching staff.

Recitation: Sockets API and HTTP 1.0 in preparation for HW3

Kent and Dave will hold an online recitation:
- Tue 9/22, 5:40–6:55pm
- Zoom link will be sent out later
- It will be recorded and uploaded to the same place that has other recitation videos.
Topics covered:
- Sockets API by walking through a basic web server code
- HTTP 1.0 protocol by connecting to the web sever using nc
Files:
- Test web page
Attendance optional, but you should attend if:
- you don’t know sockets API
- you don’t know HTTP 1.0
- you don’t know how to use netcat (nc)
References:
- Beej’s Guide to Network Programming
- HTTP Made Really Easy
- APUE, Chapter 16

HW3: Multi-Server

Group assignment, 150 points, due Sun 10/4
- Multi-Server
- Test web page & scripts

9/23

Signals I

Reading:
- APUE 10.1 - 10.6 (skim signal descriptions in 10.2)
Lecture:
- L04-signals-1
- Source code

Interprocess communication in UNIX

Reading:
- APUE 15.2
- APUE 7.6 - 7.7
- APUE 7.8: a little bit off-topic, so optional
- APUE 14.8: read page 525–527, skim or skip the rest
- APUE 15.9: skim or skip page 571–575, read page 576–578
- APUE 15.10
Lecture:
- L05-ipc
- Source code

9/30

Signals II

Reading:
- APUE 9.4 - 9.6: skim, just to get a sense of what are process group, session, and controlling terminal
- APUE 10.8 - 10.9
- APUE 10.10: you can skip pages 340–341 & 343 (but interesting read if you know setjmp() / longjmp() or willing to find out)
- APUE 10.11 - 10.13
- APUE 10.14: skip page 352–353
Lecture:
- L06-signals-2
- Source code

POSIX threads

Reading:
- APUE 11.1 - 11.4
- APUE 11.5: read page 388–393; skip the rest of 11.5
- APUE 11.6: read up to (and including) 11.6.6
Lecture:

Nonblocking I/O and I/O multiplexing

Reading:
- APUE 14.2
- APUE 14.4.0 (i.e., page 500–501)
- APUE 14.4.1
Lecture:
- L08-adv-io
- Source code

UNIX domain sockets

Reading:
- APUE 17.1
- APUE 17.2: pages 631–633 are optional, but recommended
- APUE 17.2.1
- APUE 17.3: pages 637–641 are optional, but recommended
- APUE 17.4: read 642–643, skip the rest
Lecture:
- L09-domain-sockets
- Source code

HW4: Linux System Calls

Individual assignment, 100 points, due Sun 10/11
- Linux System Calls

10/7, 10/14

UNIX domain sockets (review) & Summary of UNIX IPC

Lecture:
- L09-domain-sockets
- Source code

Linux system calls

Reading:
- OSTEP chapter 4 (previously assigned)
- OSTEP chapter 6 (previously assigned)
- LKD chapter 2
- LKD chapter 3: skim pages 37–40
- LKD chapter 5
Lecture:
- L10-syscall

Run queues & Wait queues, Interrupts, Spin Locks

Reading:
- On wait queues: LKD pages 57 - 64 (before Real-Time Scheduling Policies)
- On interrupts: LKD chapter 7
- On kernel locks: LKD chapter 10: pages 183 (from Spin Locks) - 202
Lecture:
- L11-run-wait-queues
- L12-interrupt-spinlock

HW5: Fridge

Group project, 200 points, due Sun 10/25
- Fridge

10/21

Synchronization

Reading:
- OSTEP chapter 28 (sections 28.9, 28.10, 28.11, and 28.15 are optional)
- OSTEP chapter 30
- OSTEP chapter 31
- Read java.lang.Object API doc about wait(), notify(), notifyAll() if you haven’t already
Lecture:
- L13-synchro-1
- L14-synchro-2

10/28

Midterm Exam

11/4

Scheduling algorithms

Reading:
- OSTEP chapters 7, 8
Lecture:
- L15-scheduling-1

Scheduling in Linux

Reading:
- OSTEP chapters 9, 10
- LKD chapter 4:
  - pages 42 (Linux’s Process Scheduler) - 50
  - optional, but recommended: pages 50 - 56
  - pages 57 - 64: previously assigned, but read again
  - pages 64 - 67
Lecture:
- L16-scheduling-2

HW6: Freezer

Group project, 250 points, due Sun 11/15
- Freezer

11/11

Introduction to Paging

Reading:
- OSTEP chapter 15
- OSTEP chapter 16 - skim
- OSTEP chapter 17 - optional
- OSTEP chapter 18
Lecture:
- L17-paging-intro

Paging in x86 and TLB

Reading:
- pages 25–26 from http://pdos.csail.mit.edu/6.828/2012/xv6/book-rev7.pdf
- optional, if you’re curious about segmentation in x86: http://duartes.org/gustavo/blog/post/memory-translation-and-segmentation/
- OSTEP chapter 19
Lecture:
- L18-TLB

HW7: Cabinet

Group project, 100 points, due Sun 11/22
- Cabinet

11/18

Virtual Memory Beyond Physical Memory

Reading:
- OSTEP chapter 21
- OSTEP chapter 22
Lecture:
- L19-virt-mem

Disks – Optional topic – will be covered briefly

Reading:
- OSTEP chapter 36 - optional
- OSTEP chapter 37 - optional
Lecture:
- L20-disk

Block allocation methods & UNIX file system

Reading:
- OSTEP chapter 40
- APUE 4.14, 4.15
- OSTEP chapter 41
Lecture:
- L21-fs-1

HW8: Pantry

Group project, 250 points, due Sun 12/13
- Pantry

12/2

Journaling and log-structured file system

Reading:
- OSTEP chapter 42
- OSTEP chapter 43
Lecture:
- L22-fs-2

Linux file system architecture

Reading:
- LKD chapter 13
- LKD chapter 14: pages 289 - 294
- See HW8 Part 2 for more resources you can read and reference.
Lecture:
- L23-linux-vfs

12/9

gVisor: Rewriting Linux as a Userspace Application in Go

Guest lecture by Dean Deng from Google (and a former OS student!)
- Duration: about 1 hour
- Abstract: gVisor is an userspace-level implementation of the Linux kernel that allows users to run their applications in a secure yet efficient virtualized environment. This talk will discuss how gVisor works, how it stands out from traditional approaches to virtualization (VMs and containers), and the challenges we have faced while building it.

Course wrap-up

L24-review

Last updated: 2020–12–09