COMS W4118 Operating Systems I

Spring 2022

W 4:10pm-6:40pm, 501 Northwest Corner Building (first two weeks on Zoom)
- CourseWorks open to whole Columbia first few weeks – search on Vergil
Two synchronous and in-person exams for all sections
- Exam 1: Wednesday Mar 9, 4:20pm
- Exam 2: Wednesday Apr 27, 4:20pm
(Exams can be switched to online format if necessary.)

All students in all sections MUST take the exams at those times. There are no make-up or alternate exams. If you cannot make any of those exams, please take the course next semester.
Instructor: Jae Woo Lee
Office hours:
- Jae’s office hours
- TA office hours
REQUIRED READING: ACADEMIC HONESTY POLICIES

HW due dates

F 1/21	HW0 due
Su 1/30	HW1 due
Su 2/13	HW3 due
W 2/23	HW4 Tabletop due
W 3/9	Exam 1
W 3/23	HW5 Fridge due
T 4/5	HW6 Freezer due
F 4/15	HW7 Farfetch’d due
W 4/27	Exam 2
~~R 5/5~~ F 5/6 (Hard Deadline)	HW8 Pantry due

Syllabus

1/19

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 1/21, 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, 1/30, 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 1/30
- Part A: Setup Debian Linux VM
- Part B: Linux Linked List

1/26

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

Recitation 2 - Sockets API and HTTP on CourseWorks Video Library
- Zoon session by Dave Dirnfeld and Kent Hall in Fall 2020
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
Please watch it 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 2/13
- Multi-Server
- Test web page & scripts

2/2, 2/9

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

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: Tabletop

Individual assignment, 100 points, due Wed 2/23
- Tabletop

2/16, 2/23

UNIX domain sockets (continued)

Reading:
- See above
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 Wed 3/23
- Fridge

3/2

Synchronization

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

3/9

Exam 1

3/16

Spring Break – No Class

3/23

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
- L17-linux-sched-class

HW6: Freezer

Group project, 250 points, due Tue 4/5
- Freezer

3/30

Introduction to Paging

Reading:
- OSTEP chapter 15
- OSTEP chapter 16 - skim
- OSTEP chapter 17 - optional
- OSTEP chapter 18
Lecture:
- L18-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:
- L19-TLB

HW7: Farfetch’d

Group project, 125 points, due Fri 4/15
- Farfetch’d

4/6

Virtual Memory Beyond Physical Memory

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

Storage Devices: HDD and SDD

Reading:
- OSTEP chapter 36 - optional
- OSTEP chapter 37 - optional
- OSTEP chapter 44 - optional
Lecture:
- L21-hdd-sdd

Block allocation methods & UNIX file system

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

4/13

UNIX file system (continued)

Lecture:
- L22-fs-1, slides 24–27

Journaling and log-structured file system

Reading:
- OSTEP chapter 42
- OSTEP chapter 43
Lecture:
- L23-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:
- L24-linux-vfs
- VFS diagram from this online book

HW8: Pantry

Group project, 250 points, due ~~Thu 5/5~~ Fri 5/6 (Hard Deadline)
- Pantry

4/20

Pantry Overview

Course wrap-up

L25-review

4/27

Exam 2

Last updated: 2022–05–04